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( &timestamp );
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