【C】根据UUID的标准（部分）造一个简单易用的标准UUID生成器

0xAA55

UUID（Universally unique identifier，宇宙唯一标识符，也叫GUID，Globally unique identifier，地球唯一标识符，虽说后者这个名字是微软起的）是用来给东西起名的（虽说也有其它作用）。典型例子，Windows的COM架构的每个类都有个自己的字符串名字和UUID名字，用来确定这个类是谁。一个典型的UUID看起来是这个样子的：

    123e4567-e89b-12d3-a456-426655440000
    xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

它其实是一个128bit的数值，用十六进制来表示（字节顺序为LE），并且中间插入了一些横杠以便于阅读和比对。那么它是如何保证它的“宇宙惟一性”呢？其实，一个UUID的数值虽然看起来随机，但它是有结构的，而且有不同的版本。

版本1
从概念上来说，UUID的原始版本使用计算机MAC地址和1970年以来以百纳秒为单位的时间戳来表示空间中的单个点（计算机）和时间（间隔的数量）。理论上碰撞几率为零。

然而这个计划被喷了，因为它“不透明”。它暴露了生成UUID的机器和它所执行的时间。虽说只要MAC地址不重复，它就能确保惟一性，但MAC地址可以被修改，而且现代计算机的执行速度足以在相同的时间戳内连续生成多个相同的UUID。

攻击者可以通过利用这个漏洞，来预测之后可能会生成的UUID，然后占用它。

版本2
近似于版本1，但前4个字节被替换成了POSIX的用户UID或GID，而剩余部分的时间戳则被替换成了时钟序列（通常是clock()的返回值）。取样源现在是“本地域”。

然而，版本2并未在UUID规范中被明确定义，因此并未由所有UUID生成器实现。

版本3
通过一个给定的名称、未指定命名空间的名称、域名、URL等玩意儿的MD5值来派生出UUID。版本3 UUID的格式为xxxxxxxx-xxxx-3xxx-yxxx-xxxxxxxxxxxx，其中x是任意十六进制数位，y则是8、9、a、b的其中一个。根据规范，版本3存在向后兼容性，且如果向后兼容性并不重要的话，更偏向于使用SHA-1（即版本5）。

要生成一个版本3的UUID，先取得其命名空间的UUID，转换为十六进制表示的字符串，然后在尾部追加字符串的名称，再把一整个字符串用MD5进行哈希处理，得到一个128位的MD5值。再修改其中的4个bit来提示其版本号（0011表示版本3），以及把y的位置的高2bit设为10b来使y的值为8、9、a、b的其中一个。

命名空间
上文提到的所谓命名空间，它自身也是UUID。任何UUID都可以作为版本3或5的UUID的命名空间。

版本4
由RFC 4122（“Leach-Salz”）定义，它的特点是主要取决于（伪）随机数。除了4位版本号和2位保留位，其余122位都被用伪随机数作为数据源来填充。它的格式是xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx，类似于版本3。其中的y是8、9、a、b中的一个。

版本5
和版本3类似，除了版本号是5，以及哈希算法是SHA-1而非MD5。注意SHA-1的长度是160位，解决长度问题的办法是将其截断为128位。


我随手写了一个版本4的C语言代码用于生成UUID。其中我使用了各种方式尽可能获得更多熵来生成更加随机的伪随机数。不过，随机数序列依然是可预测的。我只是用了一个包含熵比较多的随机数种子而已。

1. #include<stdint.h>
   
2. #include<stdlib.h>
   
3. #include<time.h>
   
4. 
   
5. void gen_uuid(void *puuid)
   
6. {
   
7.         uint32_t *u = puuid;
   
8.         time_t t = time(NULL); // 时间戳
   
9.         clock_t c = clock(); // 时钟值
   
10.         uint64_t rs64 = t ^ (size_t)u ^ c ^ u[0] ^ u[1] ^ u[2] ^ u[3] ^ rand(); // 随机数种子（作为参数的那个指针的值也拿来用）
    
11.        
    
12.         // 折叠随机数种子为32位
    
13.         srand((rs64 >> 32) ^ rs64);
    
14. 
    
15.         // 产生16个8bit随机数。由于不同C库的rand()取值范围不同，这里只截取其低8位确保安全
    
16.         u[0] = ((uint32_t)rand() & 0xFFU) | (((uint32_t)rand() & 0xFFU) << 8) | (((uint32_t)rand() & 0xFFU) << 16) | (((uint32_t)rand() & 0xFFU) << 24);
    
17.         u[2] = ((uint32_t)rand() & 0xFFU) | (((uint32_t)rand() & 0xFFU) << 8) | (((uint32_t)rand() & 0xFFU) << 16) | (((uint32_t)rand() & 0xFFU) << 24);
    
18.         u[1] = ((uint32_t)rand() & 0xFFU) | (((uint32_t)rand() & 0xFFU) << 8) | (((uint32_t)rand() & 0xFFU) << 16) | (((uint32_t)rand() & 0xFFU) << 24);
    
19.         u[3] = ((uint32_t)rand() & 0xFFU) | (((uint32_t)rand() & 0xFFU) << 8) | (((uint32_t)rand() & 0xFFU) << 16) | (((uint32_t)rand() & 0xFFU) << 24);
    
20. 
    
21.         // 插入4位版本号、2位的保留位
    
22.         u[1] &= 0x0FFF3FFF;
    
23.         u[1] |= 0x40008000;
    
24. }

复制代码

参考资料：

https://en.wikipedia.org/wiki/Universally_unique_identifier
https://stackoverflow.com/questi ... uuid-version-to-use
https://ipfs.io/ipfs/QmXoypizjW3 ... que_identifier.html

唐凌

发一个Windows内核里的UUID创建函数，代码来自WRK v1.2（对应32位Windows Server 2003，64位Windows XP）。

1. NTSTATUS
   
2. ExUuidCreate(
   
3.     OUT UUID *Uuid
   
4.     )
   
5. 
   
6. /*++
   
7. 
   
8. Routine Description:
   
9. 
   
10.     This routine creates a DCE UUID and returns it in the caller's
    
11.     buffer.
    
12. 
    
13. Arguments:
    
14. 
    
15.     Uuid - will receive the UUID.
    
16. 
    
17. Return Value:
    
18. 
    
19.     STATUS_SUCCESS is returned if the service is successfully executed.
    
20. 
    
21.     STATUS_RETRY is returned if we're unable to reserve a range of
    
22.         UUIDs.  This will occur if system clock hasn't advanced
    
23.         and the allocator is out of cached values.
    
24. 
    
25. --*/
    
26. 
    
27. {
    
28.     NTSTATUS Status = STATUS_SUCCESS;
    
29. 
    
30.     UUID_GENERATE  *UuidGen = (UUID_GENERATE *) Uuid;
    
31.     ULONGLONG       Time;
    
32.     LONG            Delta;
    
33. 
    
34.     PAGED_CODE();
    
35. 
    
36.     //
    
37.     // Get a value from the cache.  If the cache is empty, we'll fill
    
38.     // it and retry.  The first time cache will be empty.
    
39.     //
    
40. 
    
41.     for(;;) {
    
42. 
    
43.         // Get the highest value in the cache (though it may not
    
44.         // be available).
    
45.         Time = ExpUuidCachedValues.Time;
    
46. 
    
47.         // Copy the static info into the UUID.  We can't do this later
    
48.         // because the clock sequence could be updated by another thread.
    
49. 
    
50.         *(PULONG)&UuidGen->ClockSeqHiAndReserved =
    
51.             *(PULONG)&ExpUuidCachedValues.ClockSeqHiAndReserved;
    
52.         *(PULONG)&UuidGen->NodeId[2] =
    
53.             *(PULONG)&ExpUuidCachedValues.NodeId[2];
    
54. 
    
55.         // See what we need to subtract from Time to get a valid GUID.
    
56.         Delta = InterlockedDecrement(&ExpUuidCachedValues.AllocatedCount);
    
57. 
    
58.         if (Time != ExpUuidCachedValues.Time) {
    
59. 
    
60.             // If our captured time doesn't match the cache then another
    
61.             // thread already took the lock and updated the cache. We'll
    
62.             // just loop and try again.
    
63.             continue;
    
64.             }
    
65. 
    
66.         // If the cache hadn't already run dry, we can break out of this retry
    
67.         // loop.
    
68.         if (Delta >= 0) {
    
69.             break;
    
70.             }
    
71. 
    
72.         //
    
73.         // Allocate a new block of Uuids.
    
74.         //
    
75. 
    
76.         // Take the cache lock
    
77.         KeEnterCriticalRegion();
    
78.         ExAcquireFastMutexUnsafe(&ExpUuidLock);
    
79. 
    
80.         // If the cache has already been updated, try again.
    
81.         if (Time != ExpUuidCachedValues.Time) {
    
82.             // Release the lock
    
83.             ExReleaseFastMutexUnsafe(&ExpUuidLock);
    
84.             KeLeaveCriticalRegion();
    
85.             continue;
    
86.             }
    
87. 
    
88.         // Update the cache.
    
89.         Status = ExpUuidGetValues( &ExpUuidCachedValues );
    
90. 
    
91.         if (Status != STATUS_SUCCESS) {
    
92.             // Release the lock
    
93.             ExReleaseFastMutexUnsafe(&ExpUuidLock);
    
94.             KeLeaveCriticalRegion();
    
95.             return(Status);
    
96.             }
    
97. 
    
98.         // The sequence number may have been dirtied, see if it needs
    
99.         // to be saved.  If there's an error, we'll ignore it and
    
100.         // retry on a future call.
     
101. 
     
102.         ExpUuidSaveSequenceNumberIf();
     
103. 
     
104.         // Release the lock
     
105.         ExReleaseFastMutexUnsafe(&ExpUuidLock);
     
106.         KeLeaveCriticalRegion();
     
107. 
     
108.         // Loop
     
109.         }
     
110. 
     
111.     // Adjust the time to that of the next available UUID.
     
112.     Time -= Delta;
     
113. 
     
114.     // Finish filling in the UUID.
     
115. 
     
116.     UuidGen->TimeLow = (ULONG) Time;
     
117.     UuidGen->TimeMid = (USHORT) (Time >> 32);
     
118.     UuidGen->TimeHiAndVersion = (USHORT)
     
119.         (( (USHORT)(Time >> (32+16))
     
120.         & UUID_TIME_HIGH_MASK) | UUID_VERSION);
     
121. 
     
122.     ASSERT(Status == STATUS_SUCCESS);
     
123. 
     
124.     if (ExpUuidCacheValid == CACHE_LOCAL_ONLY) {
     
125.         Status = RPC_NT_UUID_LOCAL_ONLY;
     
126.         }
     
127. 
     
128.     return(Status);
     
129. }

复制代码

Ink_Hin_fifteen

第一次了解这个东西。

陈布衣

微软起的名字还行x 笑了