1 /* 2 ** Copyright (c) 1990- 1993, 1996 Open Software Foundation, Inc. 3 ** Copyright (c) 1989 by Hewlett-Packard Company, Palo Alto, Ca. & 4 ** Digital Equipment Corporation, Maynard, Mass. 5 ** Copyright (c) 1998 Microsoft. 6 ** To anyone who acknowledges that this file is provided "AS IS" 7 ** without any express or implied warranty: permission to use, copy, 8 ** modify, and distribute this file for any purpose is hereby 9 ** granted without fee, provided that the above copyright notices and 10 ** this notice appears in all source code copies, and that none of 11 ** the names of Open Software Foundation, Inc., Hewlett-Packard 12 ** Company, or Digital Equipment Corporation be used in advertising 13 ** or publicity pertaining to distribution of the software without 14 ** specific, written prior permission. Neither Open Software 15 ** Foundation, Inc., Hewlett-Packard Company, Microsoft, nor Digital Equipment 16 ** Corporation makes any representations about the suitability of 17 ** this software for any purpose. 18 */ 19 20#include <string.h> 21#include <stdio.h> 22#include <stdlib.h> 23#include <time.h> 24#include <netinet/in.h> 25#include "sysdep.h" 26#include "uuid.h" 27 28/* 29 various forward declarations 30 */ 31static int read_state( unsigned16 * clockseq, 32 uuid_time_t * timestamp, 33 uuid_node_t * node ); 34static void write_state( unsigned16 clockseq, 35 uuid_time_t timestamp, 36 uuid_node_t node ); 37static void format_uuid_v1( uuid_upnp * uid, 38 unsigned16 clockseq, 39 uuid_time_t timestamp, 40 uuid_node_t node ); 41static void format_uuid_v3( uuid_upnp * uid, 42 unsigned char hash[16] ); 43static void get_current_time( uuid_time_t * timestamp ); 44static unsigned16 true_random( void ); 45 46/*-----------------------------------------------------------------------------*/ 47/* 48 uuid_create -- generator a UUID 49 */ 50int 51uuid_create( uuid_upnp * uid ) 52{ 53 uuid_time_t timestamp, 54 last_time; 55 unsigned16 clockseq; 56 uuid_node_t node; 57 uuid_node_t last_node; 58 int f; 59 60 /* 61 acquire system wide lock so we're alone 62 */ 63 UUIDLock( ); 64 65 /* 66 get current time 67 */ 68 get_current_time( ×tamp ); 69 70 /* 71 get node ID 72 */ 73 get_ieee_node_identifier( &node ); 74 75 /* 76 get saved state from NV storage 77 */ 78 f = read_state( &clockseq, &last_time, &last_node ); 79 80 /* 81 if no NV state, or if clock went backwards, or node ID changed 82 (e.g., net card swap) change clockseq 83 */ 84 if( !f || memcmp( &node, &last_node, sizeof( uuid_node_t ) ) ) 85 clockseq = true_random( ); 86 else if( timestamp < last_time ) 87 clockseq++; 88 89 /* 90 stuff fields into the UUID 91 */ 92 format_uuid_v1( uid, clockseq, timestamp, node ); 93 94 /* 95 save the state for next time 96 */ 97 write_state( clockseq, timestamp, node ); 98 99 UUIDUnlock( ); 100 return ( 1 ); 101}; 102 103/*-----------------------------------------------------------------------------*/ 104void 105uuid_unpack( uuid_upnp * u, 106 char *out ) 107{ 108 109 sprintf( out, 110 "%8.8x-%4.4x-%4.4x-%2.2x%2.2x-%2.2x%2.2x%2.2x%2.2x%2.2x%2.2x", 111 ( unsigned int )u->time_low, u->time_mid, 112 u->time_hi_and_version, u->clock_seq_hi_and_reserved, 113 u->clock_seq_low, u->node[0], u->node[1], u->node[2], 114 u->node[3], u->node[4], u->node[5] ); 115 116 *( out + 36 ) = '\0'; 117 118}; 119 120/*-----------------------------------------------------------------------------*/ 121/* 122 format_uuid_v1 -- make a UUID from the timestamp, clockseq, 123 and node ID 124 */ 125void 126format_uuid_v1( uuid_upnp * uid, 127 unsigned16 clock_seq, 128 uuid_time_t timestamp, 129 uuid_node_t node ) 130{ 131 /* 132 Construct a version 1 uuid with the information we've gathered 133 * plus a few constants. 134 */ 135 uid->time_low = ( unsigned long )( timestamp & 0xFFFFFFFF ); 136 uid->time_mid = ( unsigned short )( ( timestamp >> 32 ) & 0xFFFF ); 137 uid->time_hi_and_version = ( unsigned short )( ( timestamp >> 48 ) & 138 0x0FFF ); 139 uid->time_hi_and_version |= ( 1 << 12 ); 140 uid->clock_seq_low = clock_seq & 0xFF; 141 uid->clock_seq_hi_and_reserved = ( clock_seq & 0x3F00 ) >> 8; 142 uid->clock_seq_hi_and_reserved |= 0x80; 143 memcpy( &uid->node, &node, sizeof uid->node ); 144}; 145 146/*-----------------------------------------------------------------------------*/ 147/* 148 data type for UUID generator persistent state 149 */ 150typedef struct { 151 uuid_time_t ts; /* saved timestamp */ 152 uuid_node_t node; /* saved node ID */ 153 unsigned16 cs; /* saved clock sequence */ 154} uuid_state; 155 156static uuid_state st; 157static int stateInited = 0; 158 159/*-----------------------------------------------------------------------------*/ 160/* 161 read_state -- read UUID generator state from non-volatile store 162 */ 163int 164read_state( unsigned16 * clockseq, 165 uuid_time_t * timestamp, 166 uuid_node_t * node ) 167{ 168 169 if( !stateInited ) { 170 return 0; 171 }; 172 173 *clockseq = st.cs; 174 *timestamp = st.ts; 175 *node = st.node; 176 return 1; 177}; 178 179/*-----------------------------------------------------------------------------*/ 180/* 181 write_state -- save UUID generator state back to non-volatile 182 storage 183 */ 184void 185write_state( unsigned16 clockseq, 186 uuid_time_t timestamp, 187 uuid_node_t node ) 188{ 189 static uuid_time_t next_save; 190 191 if( !stateInited ) { 192 next_save = timestamp; 193 stateInited = 1; 194 }; 195 196 /* 197 always save state to volatile shared state 198 */ 199 st.cs = clockseq; 200 st.ts = timestamp; 201 st.node = node; 202 if( timestamp >= next_save ) { 203 /* 204 schedule next save for 10 seconds from now 205 */ 206 next_save = timestamp + ( 10 * 10 * 1000 * 1000 ); 207 }; 208}; 209 210/*-----------------------------------------------------------------------------*/ 211/* 212 get-current_time -- get time as 60 bit 100ns ticks since whenever. 213 Compensate for the fact that real clock resolution is 214 less than 100ns. 215 */ 216void 217get_current_time( uuid_time_t * timestamp ) 218{ 219 uuid_time_t time_now; 220 static uuid_time_t time_last; 221 static unsigned16 uuids_this_tick; 222 static int inited = 0; 223 224 if( !inited ) { 225 get_system_time( &time_now ); 226 uuids_this_tick = UUIDS_PER_TICK; 227 inited = 1; 228 }; 229 230 while( 1 ) { 231 get_system_time( &time_now ); 232 233 /* 234 if clock reading changed since last UUID generated... 235 */ 236 if( time_last != time_now ) { 237 /* 238 reset count of uuids gen'd with this clock reading 239 */ 240 uuids_this_tick = 0; 241 break; 242 }; 243 244 if( uuids_this_tick < UUIDS_PER_TICK ) { 245 uuids_this_tick++; 246 break; 247 }; 248 /* 249 going too fast for our clock; spin 250 */ 251 }; 252 253 /* 254 add the count of uuids to low order bits of the clock reading 255 */ 256 *timestamp = time_now + uuids_this_tick; 257 time_last = *timestamp; 258}; 259 260/*-----------------------------------------------------------------------------*/ 261/* 262 true_random -- generate a crypto-quality random number. 263 This sample doesn't do that. 264 */ 265static unsigned16 266true_random( void ) 267{ 268 static int inited = 0; 269 uuid_time_t time_now; 270 271 if( !inited ) { 272 get_system_time( &time_now ); 273 time_now = time_now / UUIDS_PER_TICK; 274 srand( ( unsigned int )( ( ( time_now >> 32 ) ^ time_now ) & 275 0xffffffff ) ); 276 inited = 1; 277 }; 278 279 return ( rand( ) ); 280} 281 282/*-----------------------------------------------------------------------------*/ 283/* 284 uuid_create_from_name -- create a UUID using a "name" from a "name space" 285 */ 286void 287uuid_create_from_name( uuid_upnp * uid, /* resulting UUID */ 288 289 uuid_upnp nsid, /* UUID to serve as context, so identical 290 names from different name spaces generate 291 different UUIDs */ 292 293 void *name, /* the name from which to generate a UUID */ 294 295 int namelen /* the length of the name */ 296 ) 297{ 298 MD5_CTX c; 299 unsigned char hash[16]; 300 uuid_upnp net_nsid; /* context UUID in network byte order */ 301 302 /* 303 put name space ID in network byte order so it hashes the same 304 no matter what endian machine we're on 305 */ 306 net_nsid = nsid; 307 net_nsid.time_low=htonl( net_nsid.time_low ); 308 net_nsid.time_mid=htons( net_nsid.time_mid ); 309 net_nsid.time_hi_and_version =htons( net_nsid.time_hi_and_version ); 310 311 MD5Init( &c ); 312 MD5Update( &c, &net_nsid, sizeof( uuid_upnp ) ); 313 MD5Update( &c, name, namelen ); 314 MD5Final( hash, &c ); 315 316 /* 317 the hash is in network byte order at this point 318 */ 319 format_uuid_v3( uid, hash ); 320}; 321 322/*-----------------------------------------------------------------------------*/ 323/* 324 format_uuid_v3 -- make a UUID from a (pseudo)random 128 bit number 325 */ 326void 327format_uuid_v3( uuid_upnp * uid, 328 unsigned char hash[16] ) 329{ 330 /* 331 Construct a version 3 uuid with the (pseudo-)random number 332 * plus a few constants. 333 */ 334 335 memcpy( uid, hash, sizeof( uuid_upnp ) ); 336 337 /* 338 convert UUID to local byte order 339 */ 340 uid->time_low=ntohl( uid->time_low ); 341 uid->time_mid=ntohs( uid->time_mid ); 342 uid->time_hi_and_version=ntohs( uid->time_hi_and_version ); 343 344 /* 345 put in the variant and version bits 346 */ 347 uid->time_hi_and_version &= 0x0FFF; 348 uid->time_hi_and_version |= ( 3 << 12 ); 349 uid->clock_seq_hi_and_reserved &= 0x3F; 350 uid->clock_seq_hi_and_reserved |= 0x80; 351}; 352 353/*-----------------------------------------------------------------------------*/ 354/* 355 uuid_compare -- Compare two UUID's "lexically" and return 356 -1 u1 is lexically before u2 357 0 u1 is equal to u2 358 1 u1 is lexically after u2 359 360 Note: lexical ordering is not temporal ordering! 361 */ 362int 363uuid_compare( uuid_upnp * u1, 364 uuid_upnp * u2 ) 365{ 366 int i; 367 368#define CHECK(f1, f2) if (f1 != f2) return f1 < f2 ? -1 : 1; 369 CHECK( u1->time_low, u2->time_low ); 370 CHECK( u1->time_mid, u2->time_mid ); 371 CHECK( u1->time_hi_and_version, u2->time_hi_and_version ); 372 CHECK( u1->clock_seq_hi_and_reserved, u2->clock_seq_hi_and_reserved ); 373 CHECK( u1->clock_seq_low, u2->clock_seq_low ) 374 for( i = 0; i < 6; i++ ) { 375 if( u1->node[i] < u2->node[i] ) 376 return -1; 377 if( u1->node[i] > u2->node[i] ) 378 return 1; 379 } 380 381 return 0; 382}; 383