uuidgen/token.c

   1 /*
   2 ** Copyright (C) 1998-1999 Greg Stein. All Rights Reserved.
   3 **
   4 ** By using this file, you agree to the terms and conditions set forth in
   5 ** the LICENSE.html file which can be found at the top level of the mod_dav
   6 ** distribution or at http://www.webdav.org/mod_dav/license-1.html.
   7 **
   8 ** Contact information:
   9 **   Greg Stein, PO Box 3151, Redmond, WA, 98073
  10 **   gstein@lyra.org, http://www.webdav.org/mod_dav/
  11 */
  12
  13 /*
  14 ** DAV opaquelocktoken scheme implementation
  15 **
  16 ** Written 5/99 by Keith Wannamaker, wannamak@us.ibm.com
  17 ** Adapted from ISO/DCE RPC spec and a former Internet Draft
  18 ** by Leach and Salz:
  19 ** http://www.ics.uci.edu/pub/ietf/webdav/uuid-guid/draft-leach-uuids-guids-01
  20 **
  21 ** Portions of the code are covered by the following license:
  22 **
  23 ** Copyright (c) 1990- 1993, 1996 Open Software Foundation, Inc.
  24 ** Copyright (c) 1989 by Hewlett-Packard Company, Palo Alto, Ca. &
  25 ** Digital Equipment Corporation, Maynard, Mass.
  26 ** Copyright (c) 1998 Microsoft.
  27 ** To anyone who acknowledges that this file is provided "AS IS"
  28 ** without any express or implied warranty: permission to use, copy,
  29 ** modify, and distribute this file for any purpose is hereby
  30 ** granted without fee, provided that the above copyright notices and
  31 ** this notice appears in all source code copies, and that none of
  32 ** the names of Open Software Foundation, Inc., Hewlett-Packard
  33 ** Company, or Digital Equipment Corporation be used in advertising
  34 ** or publicity pertaining to distribution of the software without
  35 ** specific, written prior permission.  Neither Open Software
  36 ** Foundation, Inc., Hewlett-Packard Company, Microsoft, nor Digital Equipment
  37 ** Corporation makes any representations about the suitability of
  38 ** this software for any purpose.
  39 */
  40
  41 #include <string.h>
  42 #include <stdio.h>
  43 #include <stdlib.h>
  44 #include <time.h>
  45
  46 #include "md5.h"
  47 #include "token.h"
  48
  49 #ifdef WIN32
  50 #include <windows.h>
  51 #else
  52 #include <sys/types.h>
  53 #include <sys/time.h>
  54 #include <sys/sysinfo.h>
  55 #endif
  56
  57 /* set the following to the number of 100ns ticks of the actual resolution of
  58    your system's clock */
  59 #define UUIDS_PER_TICK 1024
  60
  61 /* Set this to what your compiler uses for 64 bit data type */
  62 #ifdef WIN32
  63 #define unsigned64_t unsigned __int64
  64 #define I64(C) C
  65 #else
  66 #define unsigned64_t unsigned long long
  67 #define I64(C) C##LL
  68 #endif
  69
  70 typedef unsigned64_t uuid_time_t;
  71
  72 const uuid_t null_locktoken = {0};
  73
  74 static void format_uuid_v1(uuid_t * uuid, unsigned16 clockseq, uuid_time_t timestamp, uuid_node_t node);
  75 static void get_current_time(uuid_time_t * timestamp);
  76 static unsigned16 true_random(void);
  77 static void get_pseudo_node_identifier(uuid_node_t *node);
  78 static void get_system_time(uuid_time_t *uuid_time);
  79 static void get_random_info(unsigned char seed[16]);
  80
  81
  82 /* dav_create_opaquelocktoken - generates a UUID version 1 token.
  83  *   Clock_sequence and node_address set to pseudo-random
  84  *   numbers during init.
  85  *
  86  *   Should postpend pid to account for non-seralized creation?
  87  */
  88 int create_token(uuid_state *st, uuid_t *u)
  89 {
  90     uuid_time_t timestamp;
  91
  92     get_current_time(&timestamp);
  93     format_uuid_v1(u, st->cs, timestamp, st->node);
  94
  95     return 1;
  96 }
  97
  98 /*
  99  * dav_create_uuid_state - seed UUID state with pseudorandom data
 100  */
 101 void create_uuid_state(uuid_state *st)
 102 {
 103     st->cs = true_random();
 104     get_pseudo_node_identifier(&st->node);
 105 }
 106
 107 /*
 108  * dav_format_opaquelocktoken - generates a text representation
 109  *    of an opaquelocktoken
 110  */
 111 void format_token(char *target, const uuid_t *u)
 112 {
 113   sprintf(target, "%08lx-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x",
 114           u->time_low, u->time_mid, u->time_hi_and_version,
 115           u->clock_seq_hi_and_reserved, u->clock_seq_low,
 116           u->node[0], u->node[1], u->node[2],
 117           u->node[3], u->node[4], u->node[5]);
 118 }
 119
 120 /* convert a pair of hex digits to an integer value [0,255] */
 121 static int dav_parse_hexpair(const char *s)
 122 {
 123     int result;
 124     int temp;
 125
 126     result = s[0] - '0';
 127     if (result > 48)
 128         result = (result - 39) << 4;
 129     else if (result > 16)
 130         result = (result - 7) << 4;
 131     else
 132         result = result << 4;
 133
 134     temp = s[1] - '0';
 135     if (temp > 48)
 136         result |= temp - 39;
 137     else if (temp > 16)
 138         result |= temp - 7;
 139     else
 140         result |= temp;
 141
 142     return result;
 143 }
 144
 145 /* dav_parse_locktoken:  Parses string produced from
 146  *    dav_format_opaquelocktoken back into a uuid_t
 147  *    structure.  On failure, return DAV_IF_ERROR_PARSE,
 148  *    else DAV_IF_ERROR_NONE.
 149  */
 150 int parse_token(const char *char_token, uuid_t *bin_token)
 151 {
 152     int i;
 153
 154     for (i = 0; i < 36; ++i) {
 155         char c = char_token[i];
 156         if (!isxdigit(c) &&
 157             !(c == '-' && (i == 8 || i == 13 || i == 18 || i == 23)))
 158             return -1;
 159     }
 160     if (char_token[36] != '\0')
 161         return -1;
 162
 163     bin_token->time_low =
 164         (dav_parse_hexpair(&char_token[0]) << 24) |
 165         (dav_parse_hexpair(&char_token[2]) << 16) |
 166         (dav_parse_hexpair(&char_token[4]) << 8) |
 167         dav_parse_hexpair(&char_token[6]);
 168
 169     bin_token->time_mid =
 170         (dav_parse_hexpair(&char_token[9]) << 8) |
 171         dav_parse_hexpair(&char_token[11]);
 172
 173     bin_token->time_hi_and_version =
 174         (dav_parse_hexpair(&char_token[14]) << 8) |
 175         dav_parse_hexpair(&char_token[16]);
 176
 177     bin_token->clock_seq_hi_and_reserved = dav_parse_hexpair(&char_token[19]);
 178     bin_token->clock_seq_low = dav_parse_hexpair(&char_token[21]);
 179
 180     for (i = 6; i--;)
 181         bin_token->node[i] = dav_parse_hexpair(&char_token[i*2+24]);
 182
 183     return -1;
 184 }
 185
 186 /* dav_compare_opaquelocktoken:
 187  *    < 0 : a < b
 188  *   == 0 : a = b
 189  *    > 0 : a > b
 190  */
 191 int compare_token(const uuid_t a, const uuid_t b)
 192 {
 193     return memcmp(&a, &b, sizeof(uuid_t));
 194 }
 195
 196 /* format_uuid_v1 -- make a UUID from the timestamp, clockseq, and node ID */
 197 static void format_uuid_v1(uuid_t * uuid, unsigned16 clock_seq,
 198                            uuid_time_t timestamp, uuid_node_t node)
 199 {
 200     /* Construct a version 1 uuid with the information we've gathered
 201      * plus a few constants. */
 202     uuid->time_low = (unsigned long)(timestamp & 0xFFFFFFFF);
 203     uuid->time_mid = (unsigned short)((timestamp >> 32) & 0xFFFF);
 204     uuid->time_hi_and_version = (unsigned short)((timestamp >> 48) & 0x0FFF);
 205     uuid->time_hi_and_version |= (1 << 12);
 206     uuid->clock_seq_low = clock_seq & 0xFF;
 207     uuid->clock_seq_hi_and_reserved = (clock_seq & 0x3F00) >> 8;
 208     uuid->clock_seq_hi_and_reserved |= 0x80;
 209     memcpy(&uuid->node, &node, sizeof uuid->node);
 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 less than 100ns. */
 214 static void get_current_time(uuid_time_t * timestamp)
 215 {
 216     uuid_time_t         time_now;
 217     static uuid_time_t  time_last;
 218     static unsigned16   uuids_this_tick;
 219     static int          inited = 0;
 220
 221     if (!inited) {
 222         get_system_time(&time_now);
 223         uuids_this_tick = UUIDS_PER_TICK;
 224         inited = 1;
 225     };
 226
 227     while (1) {
 228         get_system_time(&time_now);
 229
 230         /* if clock reading changed since last UUID generated... */
 231         if (time_last != time_now) {
 232             /* reset count of uuids gen'd with this clock reading */
 233             uuids_this_tick = 0;
 234             break;
 235         };
 236         if (uuids_this_tick < UUIDS_PER_TICK) {
 237             uuids_this_tick++;
 238             break;
 239         };        /* going too fast for our clock; spin */
 240     };    /* add the count of uuids to low order bits of the clock reading */
 241
 242     *timestamp = time_now + uuids_this_tick;
 243 }
 244
 245 /* true_random -- generate a crypto-quality random number.
 246    This sample doesn't do that. */
 247 static unsigned16 true_random(void)
 248 {
 249     uuid_time_t time_now;
 250
 251     get_system_time(&time_now);
 252     time_now = time_now/UUIDS_PER_TICK;
 253     srand((unsigned int)(((time_now >> 32) ^ time_now)&0xffffffff));
 254
 255     return rand();
 256 }
 257
 258 /* This sample implementation generates a random node ID   *
 259  * in lieu of a system dependent call to get IEEE node ID. */
 260 static void get_pseudo_node_identifier(uuid_node_t *node)
 261 {
 262     unsigned char seed[16];
 263
 264     get_random_info(seed);
 265     seed[0] |= 0x80;
 266     memcpy(node, seed, sizeof(*node));
 267 }
 268
 269 /* system dependent call to get the current system time.
 270    Returned as 100ns ticks since Oct 15, 1582, but resolution may be
 271    less than 100ns.  */
 272
 273 #ifdef WIN32
 274
 275 static void get_system_time(uuid_time_t *uuid_time)
 276 {
 277     ULARGE_INTEGER time;
 278
 279     GetSystemTimeAsFileTime((FILETIME *)&time);
 280
 281     /* NT keeps time in FILETIME format which is 100ns ticks since
 282        Jan 1, 1601.  UUIDs use time in 100ns ticks since Oct 15, 1582.
 283        The difference is 17 Days in Oct + 30 (Nov) + 31 (Dec)
 284        + 18 years and 5 leap days.    */
 285
 286     time.QuadPart +=
 287         (unsigned __int64) (1000*1000*10)       // seconds
 288         * (unsigned __int64) (60 * 60 * 24)       // days
 289         * (unsigned __int64) (17+30+31+365*18+5); // # of days
 290     *uuid_time = time.QuadPart;
 291 }
 292
 293 static void get_random_info(unsigned char seed[16])
 294 {
 295     MD5_CTX c;
 296     struct {
 297         MEMORYSTATUS m;
 298         SYSTEM_INFO s;
 299         FILETIME t;
 300         LARGE_INTEGER pc;
 301         DWORD tc;
 302         DWORD l;
 303         char hostname[MAX_COMPUTERNAME_LENGTH + 1];
 304
 305     } r;
 306
 307     MD5Init(&c);    /* memory usage stats */
 308     GlobalMemoryStatus(&r.m);    /* random system stats */
 309     GetSystemInfo(&r.s);    /* 100ns resolution (nominally) time of day */
 310     GetSystemTimeAsFileTime(&r.t);    /* high resolution performance counter */
 311     QueryPerformanceCounter(&r.pc);    /* milliseconds since last boot */
 312     r.tc = GetTickCount();
 313     r.l = MAX_COMPUTERNAME_LENGTH + 1;
 314
 315     GetComputerName(r.hostname, &r.l );
 316     MD5Update(&c, (const unsigned char *) &r, sizeof(r));
 317     MD5Final(seed, &c);
 318 }
 319
 320 #else /* WIN32 */
 321
 322 static void get_system_time(uuid_time_t *uuid_time)
 323 {
 324     struct timeval tp;
 325
 326     gettimeofday(&tp, (struct timezone *)0);
 327
 328     /* Offset between UUID formatted times and Unix formatted times.
 329        UUID UTC base time is October 15, 1582.
 330        Unix base time is January 1, 1970.      */
 331     *uuid_time = (tp.tv_sec * 10000000) + (tp.tv_usec * 10) +
 332         I64(0x01B21DD213814000);
 333 }
 334
 335 static void get_random_info(unsigned char seed[16])
 336 {
 337     MD5_CTX c;
 338     /* Leech & Salz use Linux-specific struct sysinfo;
 339      * replace with pid/tid for portability (in the spirit of mod_unique_id) */
 340     struct {
 341         /* Add thread id here, if applicable, when we get to pthread or apr */
 342         pid_t pid;
 343         struct timeval t;
 344         char hostname[257];
 345
 346     } r;
 347
 348     MD5Init(&c);
 349     r.pid = getpid();
 350     gettimeofday(&r.t, (struct timezone *)0);
 351     gethostname(r.hostname, 256);
 352     MD5Update(&c, (const unsigned char *)&r, sizeof(r));
 353     MD5Final(seed, &c);
 354 }
 355
 356 #endif /* WIN32 */