Update draft-leach-uuids-guids-01.txt with rfc4122.txt
Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
diff --git a/debian/control b/debian/control
index 25b639a..9c510ef 100644
--- a/debian/control
+++ b/debian/control
@@ -81,13 +81,8 @@
Replaces: e2fsprogs (<< 1.34-1)
Architecture: any
Description: universally unique id library
- libuuid generates and parses 128-bit universally unique id's (UUID's),
- using a standard which is blessed by both Microsoft and DCE, and is
- being proposed as an internet standard. See the internet-draft:
- .
- draft-leach-uuids-guids-01.txt
- .
- for more information.
+ libuuid generates and parses 128-bit universally unique id's (UUID's).
+ See RFC 4122 for more information.
Package: libuuid1-udeb
Section: debian-installer
@@ -97,13 +92,8 @@
Replaces: libuuid1
Architecture: any
Description: universally unique id library
- libuuid generates and parses 128-bit universally unique id's (UUID's),
- using a standard which is blessed by both Microsoft and DCE, and is
- being proposed as an internet standard. See the internet-draft:
- .
- draft-leach-uuids-guids-01.txt
- .
- for more information.
+ libuuid generates and parses 128-bit universally unique id's (UUID's).
+ See RFC 4122 for more information.
.
This is a minimal package for debian-installer.
@@ -114,13 +104,8 @@
Replaces: e2fslibs-dev (<< 1.15)
Architecture: any
Description: universally unique id library - headers and static libraries
- libuuid generates and parses 128-bit universally unique id's (UUID's),
- using a standard which is blessed by both Microsoft and DCE, and is
- being proposed as an internet standard. See the internet-draft:
- .
- draft-leach-uuids-guids-01.txt
- .
- for more information.
+ libuuid generates and parses 128-bit universally unique id's (UUID's).
+ See RFC 4122 for more information.
.
This package contains the development environment for the uuid library.
diff --git a/debian/rules b/debian/rules
index 4448418..3b121e3 100755
--- a/debian/rules
+++ b/debian/rules
@@ -343,7 +343,7 @@
$(INSTALL) -d ${debdir}/uuid-dev/usr/share/doc/libuuid${UUID_SOVERSION}
if test -f /etc/lsb-release && \
grep -q DISTRIB_ID=Ubuntu /etc/lsb-release; then \
- $(INSTALL) -p -m 0644 doc/draft-leach-uuids-guids-01.txt \
+ $(INSTALL) -p -m 0644 doc/rfc4122.txt \
${debdir}/uuid-dev/usr/share/doc/libuuid${UUID_SOVERSION}; \
fi
diff --git a/doc/draft-leach-uuids-guids-01.txt b/doc/draft-leach-uuids-guids-01.txt
deleted file mode 100644
index d611d06..0000000
--- a/doc/draft-leach-uuids-guids-01.txt
+++ /dev/null
@@ -1,1708 +0,0 @@
-
-
-
-
-
-
-Network Working Group Paul J. Leach, Microsoft
-INTERNET-DRAFT Rich Salz, Certco
-<draft-leach-uuids-guids-01.txt>
-Category: Standards Track
-Expires August 4, 1998 February 4, 1998
-
-
-
- UUIDs and GUIDs
-
-STATUS OF THIS MEMO
-
- This document is an Internet-Draft. Internet-Drafts are working
- documents of the Internet Engineering Task Force (IETF), its areas,
- and its working groups. Note that other groups may also distribute
- working documents as Internet-Drafts.
-
- Internet-Drafts are draft documents valid for a maximum of six months
- and may be updated, replaced, or obsoleted by other documents at any
- time. It is inappropriate to use Internet-Drafts as reference
- material or to cite them other than as "work in progress".
-
- To learn the current status of any Internet-Draft, please check the
- "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
- Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
- munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
- ftp.isi.edu (US West Coast).
-
- Distribution of this document is unlimited. Please send comments to
- the authors or the CIFS mailing list at <cifs@discuss.microsoft.com>.
- Discussions of the mailing list are archived at
- <URL:http://discuss.microsoft.com/archives/index.
-
-
-ABSTRACT
-
- This specification defines the format of UUIDs (Universally Unique
- IDentifier), also known as GUIDs (Globally Unique IDentifier). A UUID
- is 128 bits long, and if generated according to the one of the
- mechanisms in this document, is either guaranteed to be different
- from all other UUIDs/GUIDs generated until 3400 A.D. or extremely
- likely to be different (depending on the mechanism chosen). UUIDs
- were originally used in the Network Computing System (NCS) [1] and
- later in the Open Software Foundation's (OSF) Distributed Computing
- Environment [2].
-
- This specification is derived from the latter specification with the
- kind permission of the OSF.
-
-
-Table of Contents
-
-1. Introduction .......................................................3
-
-
-[Page 1]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
-2. Motivation .........................................................3
-
-3. Specification ......................................................3
-
- 3.1 Format............................................................4
-
- 3.1.1 Variant......................................................4
-
- 3.1.2 UUID layout..................................................5
-
- 3.1.3 Version......................................................5
-
- 3.1.4 Timestamp....................................................6
-
- 3.1.5 Clock sequence...............................................6
-
- 3.1.6 Node.........................................................7
-
- 3.1.7 Nil UUID.....................................................7
-
- 3.2 Algorithms for creating a time-based UUID.........................7
-
- 3.2.1 Basic algorithm..............................................7
-
- 3.2.2 Reading stable storage.......................................8
-
- 3.2.3 System clock resolution......................................8
-
- 3.2.4 Writing stable storage.......................................9
-
- 3.2.5 Sharing state across processes...............................9
-
- 3.2.6 UUID Generation details......................................9
-
- 3.3 Algorithm for creating a name-based UUID.........................10
-
- 3.4 Algorithms for creating a UUID from truly random or pseudo-random
- numbers .............................................................11
-
- 3.5 String Representation of UUIDs...................................12
-
- 3.6 Comparing UUIDs for equality.....................................12
-
- 3.7 Comparing UUIDs for relative order...............................13
-
- 3.8 Byte order of UUIDs..............................................13
-
-4. Node IDs when no IEEE 802 network card is available ...............14
-
-5. Obtaining IEEE 802 addresses ......................................15
-
-6. Security Considerations ...........................................15
-
-7. Acknowledgements ..................................................15
-
- Leach, Salz expires Aug 1998 [Page 2]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
-8. References ........................................................15
-
-9. Authors' addresses ................................................16
-
-10.Notice ............................................................16
-
-11.Full Copyright Statement ..........................................16
-
-Appendix A _ UUID Sample Implementation...............................17
-
-Appendix B _ Sample output of utest...................................27
-
-Appendix C _ Some name space IDs......................................27
-
-
-
-
-1. Introduction
-
- This specification defines the format of UUIDs (Universally Unique
- IDentifiers), also known as GUIDs (Globally Unique IDentifiers). A
- UUID is 128 bits long, and if generated according to the one of the
- mechanisms in this document, is either guaranteed to be different
- from all other UUIDs/GUIDs generated until 3400 A.D. or extremely
- likely to be different (depending on the mechanism chosen).
-
-
-2. Motivation
-
- One of the main reasons for using UUIDs is that no centralized
- authority is required to administer them (beyond the one that
- allocates IEEE 802.1 node identifiers). As a result, generation on
- demand can be completely automated, and they can be used for a wide
- variety of purposes. The UUID generation algorithm described here
- supports very high allocation rates: 10 million per second per
- machine if you need it, so that they could even be used as
- transaction IDs.
-
- UUIDs are fixed-size (128-bits) which is reasonably small relative to
- other alternatives. This fixed, relatively small size lends itself
- well to sorting, ordering, and hashing of all sorts, storing in
- databases, simple allocation, and ease of programming in general.
-
-
-3. Specification
-
- A UUID is an identifier that is unique across both space and time,
- with respect to the space of all UUIDs. To be precise, the UUID
- consists of a finite bit space. Thus the time value used for
- constructing a UUID is limited and will roll over in the future
- (approximately at A.D. 3400, based on the specified algorithm). A
- UUID can be used for multiple purposes, from tagging objects with an
- extremely short lifetime, to reliably identifying very persistent
- objects across a network.
-
- Leach, Salz expires Aug 1998 [Page 3]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- The generation of UUIDs does not require that a registration
- authority be contacted for each identifier. Instead, it requires a
- unique value over space for each UUID generator. This spatially
- unique value is specified as an IEEE 802 address, which is usually
- already available to network-connected systems. This 48-bit address
- can be assigned based on an address block obtained through the IEEE
- registration authority. This section of the UUID specification
- assumes the availability of an IEEE 802 address to a system desiring
- to generate a UUID, but if one is not available section 4 specifies a
- way to generate a probabilistically unique one that can not conflict
- with any properly assigned IEEE 802 address.
-
-
-3.1 Format
-
- In its most general form, all that can be said of the UUID format is
- that a UUID is 16 octets, and that some bits of octet 8 of the UUID
- called the variant field (specified in the next section) determine
- finer structure.
-
-
-3.1.1 Variant
- The variant field determines the layout of the UUID. That is, the
- interpretation of all other bits in the UUID depends on the setting
- of the bits in the variant field. The variant field consists of a
- variable number of the msbs of octet 8 of the UUID.
-
- The following table lists the contents of the variant field.
-
- Msb0 Msb1 Msb2 Description
-
- 0 - - Reserved, NCS backward compatibility.
-
- 1 0 - The variant specified in this document.
-
- 1 1 0 Reserved, Microsoft Corporation backward
- compatibility
-
- 1 1 1 Reserved for future definition.
-
-
-
- Other UUID variants may not interoperate with the UUID variant
- specified in this document, where interoperability is defined as the
- applicability of operations such as string conversion and lexical
- ordering across different systems. However, UUIDs allocated according
- to the stricture of different variants, though they may define
- different interpretations of the bits outside the variant field, will
- not result in duplicate UUID allocation, because of the differing
- values of the variant field itself.
-
- The remaining fields described below (version, timestamp, etc.) are
- defined only for the UUID variant noted above.
-
-
- Leach, Salz expires Aug 1998 [Page 4]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
-3.1.2 UUID layout
- The following table gives the format of a UUID for the variant
- specified herein. The UUID consists of a record of 16 octets. To
- minimize confusion about bit assignments within octets, the UUID
- record definition is defined only in terms of fields that are
- integral numbers of octets. The fields are in order of significance
- for comparison purposes, with "time_low" the most significant, and
- "node" the least significant.
-
- Field Data Type Octet Note
- #
-
- time_low unsigned 32 0-3 The low field of the
- bit integer timestamp.
-
- time_mid unsigned 16 4-5 The middle field of the
- bit integer timestamp.
-
- time_hi_and_version unsigned 16 6-7 The high field of the
- bit integer timestamp multiplexed
- with the version number.
-
- clock_seq_hi_and_rese unsigned 8 8 The high field of the
- rved bit integer clock sequence
- multiplexed with the
- variant.
-
- clock_seq_low unsigned 8 9 The low field of the
- bit integer clock sequence.
-
- node unsigned 48 10-15 The spatially unique
- bit integer node identifier.
-
-
-
-
-3.1.3 Version
- The version number is in the most significant 4 bits of the time
- stamp (time_hi_and_version).
-
- The following table lists currently defined versions of the UUID.
-
- Msb0 Msb1 Msb2 Msb3 Version Description
-
- 0 0 0 1 1 The time-based version
- specified in this
- document.
-
- 0 0 1 0 2 Reserved for DCE
- Security version, with
- embedded POSIX UIDs.
-
- 0 0 1 1 3 The name-based version
- specified in this
-
- Leach, Salz expires Aug 1998 [Page 5]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- document
-
- 0 1 0 0 4 The randomly or pseudo-
- randomly generated
- version specified in
- this document
-
-
-3.1.4 Timestamp
- The timestamp is a 60 bit value. For UUID version 1, this is
- represented by Coordinated Universal Time (UTC) as a count of 100-
- nanosecond intervals since 00:00:00.00, 15 October 1582 (the date of
- Gregorian reform to the Christian calendar).
-
- For systems that do not have UTC available, but do have local time,
- they MAY use local time instead of UTC, as long as they do so
- consistently throughout the system. This is NOT RECOMMENDED, however,
- and it should be noted that all that is needed to generate UTC, given
- local time, is a time zone offset.
-
- For UUID version 3, it is a 60 bit value constructed from a name.
-
- For UUID version 4, it is a randomly or pseudo-randomly generated 60
- bit value.
-
-
-3.1.5 Clock sequence
- For UUID version 1, the clock sequence is used to help avoid
- duplicates that could arise when the clock is set backwards in time
- or if the node ID changes.
-
- If the clock is set backwards, or even might have been set backwards
- (e.g., while the system was powered off), and the UUID generator can
- not be sure that no UUIDs were generated with timestamps larger than
- the value to which the clock was set, then the clock sequence has to
- be changed. If the previous value of the clock sequence is known, it
- can be just incremented; otherwise it should be set to a random or
- high-quality pseudo random value.
-
- Similarly, if the node ID changes (e.g. because a network card has
- been moved between machines), setting the clock sequence to a random
- number minimizes the probability of a duplicate due to slight
- differences in the clock settings of the machines. (If the value of
- clock sequence associated with the changed node ID were known, then
- the clock sequence could just be incremented, but that is unlikely.)
-
- The clock sequence MUST be originally (i.e., once in the lifetime of
- a system) initialized to a random number to minimize the correlation
- across systems. This provides maximum protection against node
- identifiers that may move or switch from system to system rapidly.
- The initial value MUST NOT be correlated to the node identifier.
-
- For UUID version 3, it is a 14 bit value constructed from a name.
-
-
- Leach, Salz expires Aug 1998 [Page 6]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- For UUID version 4, it is a randomly or pseudo-randomly generated 14
- bit value.
-
-
-3.1.6 Node
- For UUID version 1, the node field consists of the IEEE address,
- usually the host address. For systems with multiple IEEE 802
- addresses, any available address can be used. The lowest addressed
- octet (octet number 10) contains the global/local bit and the
- unicast/multicast bit, and is the first octet of the address
- transmitted on an 802.3 LAN.
-
- For systems with no IEEE address, a randomly or pseudo-randomly
- generated value may be used (see section 4). The multicast bit must
- be set in such addresses, in order that they will never conflict with
- addresses obtained from network cards.
-
- For UUID version 3, the node field is a 48 bit value constructed from
- a name.
-
- For UUID version 4, the node field is a randomly or pseudo-randomly
- generated 48 bit value.
-
-
-3.1.7 Nil UUID
- The nil UUID is special form of UUID that is specified to have all
- 128 bits set to 0 (zero).
-
-
-3.2 Algorithms for creating a time-based UUID
-
- Various aspects of the algorithm for creating a version 1 UUID are
- discussed in the following sections. UUID generation requires a
- guarantee of uniqueness within the node ID for a given variant and
- version. Interoperability is provided by complying with the specified
- data structure.
-
-
-3.2.1 Basic algorithm
- The following algorithm is simple, correct, and inefficient:
-
- . Obtain a system wide global lock
-
- . From a system wide shared stable store (e.g., a file), read the
- UUID generator state: the values of the time stamp, clock sequence,
- and node ID used to generate the last UUID.
-
- . Get the current time as a 60 bit count of 100-nanosecond intervals
- since 00:00:00.00, 15 October 1582
-
- . Get the current node ID
-
-
-
-
- Leach, Salz expires Aug 1998 [Page 7]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- . If the state was unavailable (non-existent or corrupted), or the
- saved node ID is different than the current node ID, generate a
- random clock sequence value
-
- . If the state was available, but the saved time stamp is later than
- the current time stamp, increment the clock sequence value
-
- . Format a UUID from the current time stamp, clock sequence, and node
- ID values according to the structure in section 3.1 (see section
- 3.2.6 for more details)
-
- . Save the state (current time stamp, clock sequence, and node ID)
- back to the stable store
-
- . Release the system wide global lock
-
- If UUIDs do not need to be frequently generated, the above algorithm
- may be perfectly adequate. For higher performance requirements,
- however, issues with the basic algorithm include:
-
- . Reading the state from stable storage each time is inefficient
-
- . The resolution of the system clock may not be 100-nanoseconds
-
- . Writing the state to stable storage each time is inefficient
-
- . Sharing the state across process boundaries may be inefficient
-
- Each of these issues can be addressed in a modular fashion by local
- improvements in the functions that read and write the state and read
- the clock. We address each of them in turn in the following sections.
-
-
-3.2.2 Reading stable storage
- The state only needs to be read from stable storage once at boot
- time, if it is read into a system wide shared volatile store (and
- updated whenever the stable store is updated).
-
- If an implementation does not have any stable store available, then
- it can always say that the values were unavailable. This is the least
- desirable implementation, because it will increase the frequency of
- creation of new clock sequence numbers, which increases the
- probability of duplicates.
-
- If the node ID can never change (e.g., the net card is inseparable
- from the system), or if any change also reinitializes the clock
- sequence to a random value, then instead of keeping it in stable
- store, the current node ID may be returned.
-
-
-3.2.3 System clock resolution
- The time stamp is generated from the system time, whose resolution
- may be less than the resolution of the UUID time stamp.
-
-
- Leach, Salz expires Aug 1998 [Page 8]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- If UUIDs do not need to be frequently generated, the time stamp can
- simply be the system time multiplied by the number of 100-nanosecond
- intervals per system time interval.
-
- If a system overruns the generator by requesting too many UUIDs
- within a single system time interval, the UUID service MUST either:
- return an error, or stall the UUID generator until the system clock
- catches up.
-
- A high resolution time stamp can be simulated by keeping a count of
- how many UUIDs have been generated with the same value of the system
- time, and using it to construction the low-order bits of the time
- stamp. The count will range between zero and the number of 100-
- nanosecond intervals per system time interval.
-
- Note: if the processors overrun the UUID generation frequently,
- additional node identifiers can be allocated to the system, which
- will permit higher speed allocation by making multiple UUIDs
- potentially available for each time stamp value.
-
-
-3.2.4 Writing stable storage
- The state does not always need to be written to stable store every
- time a UUID is generated. The timestamp in the stable store can be
- periodically set to a value larger than any yet used in a UUID; as
- long as the generated UUIDs have time stamps less than that value,
- and the clock sequence and node ID remain unchanged, only the shared
- volatile copy of the state needs to be updated. Furthermore, if the
- time stamp value in stable store is in the future by less than the
- typical time it takes the system to reboot, a crash will not cause a
- reinitialization of the clock sequence.
-
-
-3.2.5 Sharing state across processes
- If it is too expensive to access shared state each time a UUID is
- generated, then the system wide generator can be implemented to
- allocate a block of time stamps each time it is called, and a per-
- process generator can allocate from that block until it is exhausted.
-
-
-3.2.6 UUID Generation details
- UUIDs are generated according to the following algorithm:
-
- - Determine the values for the UTC-based timestamp and clock sequence
- to be used in the UUID, as described above.
-
- - For the purposes of this algorithm, consider the timestamp to be a
- 60-bit unsigned integer and the clock sequence to be a 14-bit
- unsigned integer. Sequentially number the bits in a field, starting
- from 0 (zero) for the least significant bit.
-
- - Set the time_low field equal to the least significant 32-bits (bits
- numbered 0 to 31 inclusive) of the time stamp in the same order of
- significance.
-
- Leach, Salz expires Aug 1998 [Page 9]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- - Set the time_mid field equal to the bits numbered 32 to 47
- inclusive of the time stamp in the same order of significance.
-
- - Set the 12 least significant bits (bits numbered 0 to 11 inclusive)
- of the time_hi_and_version field equal to the bits numbered 48 to 59
- inclusive of the time stamp in the same order of significance.
-
- - Set the 4 most significant bits (bits numbered 12 to 15 inclusive)
- of the time_hi_and_version field to the 4-bit version number
- corresponding to the UUID version being created, as shown in the
- table in section 3.1.3.
-
- - Set the clock_seq_low field to the 8 least significant bits (bits
- numbered 0 to 7 inclusive) of the clock sequence in the same order of
- significance.
-
- - Set the 6 least significant bits (bits numbered 0 to 5 inclusive)
- of the clock_seq_hi_and_reserved field to the 6 most significant bits
- (bits numbered 8 to 13 inclusive) of the clock sequence in the same
- order of significance.
-
- - Set the 2 most significant bits (bits numbered 6 and 7) of the
- clock_seq_hi_and_reserved to 0 and 1, respectively.
-
- - Set the node field to the 48-bit IEEE address in the same order of
- significance as the address.
-
-
-3.3 Algorithm for creating a name-based UUID
-
- The version 3 UUID is meant for generating UUIDs from "names" that
- are drawn from, and unique within, some "name space". Some examples
- of names (and, implicitly, name spaces) might be DNS names, URLs, ISO
- Object IDs (OIDs), reserved words in a programming language, or X.500
- Distinguished Names (DNs); thus, the concept of name and name space
- should be broadly construed, and not limited to textual names. The
- mechanisms or conventions for allocating names from, and ensuring
- their uniqueness within, their name spaces are beyond the scope of
- this specification.
-
- The requirements for such UUIDs are as follows:
-
- . The UUIDs generated at different times from the same name in the
- same namespace MUST be equal
-
- . The UUIDs generated from two different names in the same namespace
- should be different (with very high probability)
-
- . The UUIDs generated from the same name in two different namespaces
- should be different with (very high probability)
-
- . If two UUIDs that were generated from names are equal, then they
- were generated from the same name in the same namespace (with very
- high probability).
-
- Leach, Salz expires Aug 1998 [Page 10]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- The algorithm for generating the a UUID from a name and a name space
- are as follows:
-
- . Allocate a UUID to use as a "name space ID" for all UUIDs generated
- from names in that name space
-
- . Convert the name to a canonical sequence of octets (as defined by
- the standards or conventions of its name space); put the name space
- ID in network byte order
-
- . Compute the MD5 [3] hash of the name space ID concatenated with the
- name
-
- . Set octets 0-3 of time_low field to octets 0-3 of the MD5 hash
-
- . Set octets 0-1 of time_mid field to octets 4-5 of the MD5 hash
-
- . Set octets 0-1 of time_hi_and_version field to octets 6-7 of the
- MD5 hash
-
- . Set the clock_seq_hi_and_reserved field to octet 8 of the MD5 hash
-
- . Set the clock_seq_low field to octet 9 of the MD5 hash
-
- . Set octets 0-5 of the node field to octets 10-15 of the MD5 hash
-
- . Set the 2 most significant bits (bits numbered 6 and 7) of the
- clock_seq_hi_and_reserved to 0 and 1, respectively.
-
- . Set the 4 most significant bits (bits numbered 12 to 15 inclusive)
- of the time_hi_and_version field to the 4-bit version number
- corresponding to the UUID version being created, as shown in the
- table above.
-
- . Convert the resulting UUID to local byte order.
-
-
-3.4 Algorithms for creating a UUID from truly random or pseudo-random
-numbers
-
- The version 4 UUID is meant for generating UUIDs from truly-random or
- pseudo-random numbers.
-
- The algorithm is as follows:
-
- . Set the 2 most significant bits (bits numbered 6 and 7) of the
- clock_seq_hi_and_reserved to 0 and 1, respectively.
-
- . Set the 4 most significant bits (bits numbered 12 to 15 inclusive)
- of the time_hi_and_version field to the 4-bit version number
- corresponding to the UUID version being created, as shown in the
- table above.
-
-
-
- Leach, Salz expires Aug 1998 [Page 11]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- . Set all the other bits to randomly (or pseudo-randomly) chosen
- values.
-
- Here are several possible ways to generate the random values:
-
- . Use a physical source of randomness: for example, a white noise
- generator, radioactive decay, or a lava lamp.
-
- . Use a cryptographic strength random number generator.
-
-
-3.5 String Representation of UUIDs
-
- For use in human readable text, a UUID string representation is
- specified as a sequence of fields, some of which are separated by
- single dashes.
-
- Each field is treated as an integer and has its value printed as a
- zero-filled hexadecimal digit string with the most significant digit
- first. The hexadecimal values a to f inclusive are output as lower
- case characters, and are case insensitive on input. The sequence is
- the same as the UUID constructed type.
-
- The formal definition of the UUID string representation is provided
- by the following extended BNF:
-
- UUID = <time_low> "-" <time_mid> "-"
- <time_high_and_version> "-"
- <clock_seq_and_reserved>
- <clock_seq_low> "-" <node>
- time_low = 4*<hexOctet>
- time_mid = 2*<hexOctet>
- time_high_and_version = 2*<hexOctet>
- clock_seq_and_reserved = <hexOctet>
- clock_seq_low = <hexOctet>
- node = 6*<hexOctet
- hexOctet = <hexDigit> <hexDigit>
- hexDigit =
- "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
- | "a" | "b" | "c" | "d" | "e" | "f"
- | "A" | "B" | "C" | "D" | "E" | "F"
-
- The following is an example of the string representation of a UUID:
-
- f81d4fae-7dec-11d0-a765-00a0c91e6bf6
-
-3.6 Comparing UUIDs for equality
-
- Consider each field of the UUID to be an unsigned integer as shown in
- the table in section 3.1. Then, to compare a pair of UUIDs,
- arithmetically compare the corresponding fields from each UUID in
- order of significance and according to their data type. Two UUIDs are
- equal if and only if all the corresponding fields are equal.
-
-
- Leach, Salz expires Aug 1998 [Page 12]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- Note: as a practical matter, on many systems comparison of two UUIDs
- for equality can be performed simply by comparing the 128 bits of
- their in-memory representation considered as a 128 bit unsigned
- integer. Here, it is presumed that by the time the in-memory
- representation is obtained the appropriate byte-order
- canonicalizations have been carried out.
-
-
-3.7 Comparing UUIDs for relative order
-
- Two UUIDs allocated according to the same variant can also be ordered
- lexicographically. For the UUID variant herein defined, the first of
- two UUIDs follows the second if the most significant field in which
- the UUIDs differ is greater for the first UUID. The first of a pair
- of UUIDs precedes the second if the most significant field in which
- the UUIDs differ is greater for the second UUID.
-
-
-3.8 Byte order of UUIDs
-
- UUIDs may be transmitted in many different forms, some of which may
- be dependent on the presentation or application protocol where the
- UUID may be used. In such cases, the order, sizes and byte orders of
- the UUIDs fields on the wire will depend on the relevant presentation
- or application protocol. However, it is strongly RECOMMENDED that
- the order of the fields conform with ordering set out in section 3.1
- above. Furthermore, the payload size of each field in the application
- or presentation protocol MUST be large enough that no information
- lost in the process of encoding them for transmission.
-
- In the absence of explicit application or presentation protocol
- specification to the contrary, a UUID is encoded as a 128-bit object,
- as follows: the fields are encoded as 16 octets, with the sizes and
- order of the fields defined in section 3.1, and with each field
- encoded with the Most Significant Byte first (also known as network
- byte order).
-
- 0 1 2 3
- 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- | time_low |
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- | time_mid | time_hi_and_version |
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- |clk_seq_hi_res | clk_seq_low | node (0-1) |
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- | node (2-5) |
- +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
-
-
-
-
-
-
-
- Leach, Salz expires Aug 1998 [Page 13]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
-4. Node IDs when no IEEE 802 network card is available
-
- If a system wants to generate UUIDs but has no IEE 802 compliant
- network card or other source of IEEE 802 addresses, then this section
- describes how to generate one.
-
- The ideal solution is to obtain a 47 bit cryptographic quality random
- number, and use it as the low 47 bits of the node ID, with the most
- significant bit of the first octet of the node ID set to 1. This bit
- is the unicast/multicast bit, which will never be set in IEEE 802
- addresses obtained from network cards; hence, there can never be a
- conflict between UUIDs generated by machines with and without network
- cards.
-
- If a system does not have a primitive to generate cryptographic
- quality random numbers, then in most systems there are usually a
- fairly large number of sources of randomness available from which one
- can be generated. Such sources are system specific, but often
- include:
-
- - the percent of memory in use
- - the size of main memory in bytes
- - the amount of free main memory in bytes
- - the size of the paging or swap file in bytes
- - free bytes of paging or swap file
- - the total size of user virtual address space in bytes
- - the total available user address space bytes
- - the size of boot disk drive in bytes
- - the free disk space on boot drive in bytes
- - the current time
- - the amount of time since the system booted
- - the individual sizes of files in various system directories
- - the creation, last read, and modification times of files in various
- system directories
- - the utilization factors of various system resources (heap, etc.)
- - current mouse cursor position
- - current caret position
- - current number of running processes, threads
- - handles or IDs of the desktop window and the active window
- - the value of stack pointer of the caller
- - the process and thread ID of caller
- - various processor architecture specific performance counters
- (instructions executed, cache misses, TLB misses)
-
- (Note that it precisely the above kinds of sources of randomness that
- are used to seed cryptographic quality random number generators on
- systems without special hardware for their construction.)
-
- In addition, items such as the computer's name and the name of the
- operating system, while not strictly speaking random, will help
- differentiate the results from those obtained by other systems.
-
- The exact algorithm to generate a node ID using these data is system
- specific, because both the data available and the functions to obtain
-
- Leach, Salz expires Aug 1998 [Page 14]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- them are often very system specific. However, assuming that one can
- concatenate all the values from the randomness sources into a buffer,
- and that a cryptographic hash function such as MD5 [3] is available,
- then any 6 bytes of the MD5 hash of the buffer, with the multicast
- bit (the high bit of the first byte) set will be an appropriately
- random node ID.
-
- Other hash functions, such as SHA-1 [4], can also be used. The only
- requirement is that the result be suitably random _ in the sense that
- the outputs from a set uniformly distributed inputs are themselves
- uniformly distributed, and that a single bit change in the input can
- be expected to cause half of the output bits to change.
-
-
-5. Obtaining IEEE 802 addresses
-
- At the time of writing, the following URL
-
- http://standards.ieee.org/db/oui/forms/
-
- contains information on how to obtain an IEEE 802 address block. At
- the time of writing, the cost is $1250 US.
-
-
-6. Security Considerations
-
- It should not be assumed that UUIDs are hard to guess; they should
- not be used as capabilities.
-
-
-7. Acknowledgements
-
- This document draws heavily on the OSF DCE specification for UUIDs.
- Ted Ts'o provided helpful comments, especially on the byte ordering
- section which we mostly plagiarized from a proposed wording he
- supplied (all errors in that section are our responsibility,
- however).
-
-
-8. References
-
- [1] Lisa Zahn, et. al., Network Computing Architecture, Prentice
- Hall, Englewood Cliffs, NJ, 1990
-
- [2] DCE: Remote Procedure Call, Open Group CAE Specification C309
- ISBN 1-85912-041-5 28cm. 674p. pbk. 1,655g. 8/94
-
- [3] R. Rivest, RFC 1321, "The MD5 Message-Digest Algorithm",
- 04/16/1992.
-
- [4] NIST FIPS PUB 180-1, "Secure Hash Standard," National Institute
- of Standards and Technology, U.S. Department of Commerce, DRAFT, May
- 31, 1994.
-
-
- Leach, Salz expires Aug 1998 [Page 15]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
-9. Authors' addresses
-
- Paul J. Leach
- Microsoft
- 1 Microsoft Way
- Redmond, WA, 98052, U.S.A.
- paulle@microsoft.com
- Tel. 425 882 8080
- Fax. 425 936 7329
-
- Rich Salz
- 100 Cambridge Park Drive
- Cambridge MA 02140
- salzr@certco.com
- Tel. 617 499 4075
- Fax. 617 576 0019
-
-
-10. Notice
-
- The IETF takes no position regarding the validity or scope of any
- intellectual property or other rights that might be claimed to
- pertain to the implementation or use of the technology described in
- this document or the extent to which any license under such rights
- might or might not be available; neither does it represent that it
- has made any effort to identify any such rights. Information on the
- IETF's procedures with respect to rights in standards-track and
- standards-related documentation can be found in BCP-11. Copies of
- claims of rights made available for publication and any assurances of
- licenses to be made available, or the result of an attempt made to
- obtain a general license or permission for the use of such
- proprietary rights by implementors or users of this specification can
- be obtained from the IETF Secretariat.
-
- The IETF invites any interested party to bring to its attention any
- copyrights, patents or patent applications, or other proprietary
- rights which may cover technology that may be required to practice
- this standard. Please address the information to the IETF Executive
- Director.
-
-
-11. Full Copyright Statement
-
- Copyright (C) The Internet Society 1997. All Rights Reserved.
-
- This document and translations of it may be copied and furnished to
- others, and derivative works that comment on or otherwise explain it
- or assist in its implementation may be prepared, copied, published
- and distributed, in whole or in part, without restriction of any
- kind, provided that the above copyright notice and this paragraph are
- included on all such copies and derivative works. However, this
- document itself may not be modified in any way, such as by removing
- the copyright notice or references to the Internet Society or other
- Internet organizations, except as needed for the purpose of
-
- Leach, Salz expires Aug 1998 [Page 16]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- developing Internet standards in which case the procedures for
- copyrights defined in the Internet Standards process must be
- followed, or as required to translate it into languages other than
- English.
-
- The limited permissions granted above are perpetual and will not be
- revoked by the Internet Society or its successors or assigns.
-
- This document and the information contained herein is provided on an
- "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
- TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
- BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
- HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
- MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
-
-
- Appendix A _ UUID Sample Implementation
-
- This implementation consists of 5 files: uuid.h, uuid.c, sysdep.h,
- sysdep.c and utest.c. The uuid.* files are the system independent
- implementation of the UUID generation algorithms described above,
- with all the optimizations described above except efficient state
- sharing across processes included. The code has been tested on Linux
- (Red Hat 4.0) with GCC (2.7.2), and Windows NT 4.0 with VC++ 5.0. The
- code assumes 64 bit integer support, which makes it a lot clearer.
-
- All the following source files should be considered to have the
- following copyright notice included:
-
- copyrt.h
-
- /*
- ** Copyright (c) 1990- 1993, 1996 Open Software Foundation, Inc.
- ** Copyright (c) 1989 by Hewlett-Packard Company, Palo Alto, Ca. &
- ** Digital Equipment Corporation, Maynard, Mass.
- ** Copyright (c) 1998 Microsoft.
- ** To anyone who acknowledges that this file is provided "AS IS"
- ** without any express or implied warranty: permission to use, copy,
- ** modify, and distribute this file for any purpose is hereby
- ** granted without fee, provided that the above copyright notices and
- ** this notice appears in all source code copies, and that none of
- ** the names of Open Software Foundation, Inc., Hewlett-Packard
- ** Company, or Digital Equipment Corporation be used in advertising
- ** or publicity pertaining to distribution of the software without
- ** specific, written prior permission. Neither Open Software
- ** Foundation, Inc., Hewlett-Packard Company, Microsoft, nor Digital
- Equipment
- ** Corporation makes any representations about the suitability of
- ** this software for any purpose.
- */
-
-
- uuid.h
-
-
- Leach, Salz expires Aug 1998 [Page 17]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- #include "copyrt.h"
- #undef uuid_t
- typedef struct _uuid_t {
- unsigned32 time_low;
- unsigned16 time_mid;
- unsigned16 time_hi_and_version;
- unsigned8 clock_seq_hi_and_reserved;
- unsigned8 clock_seq_low;
- byte node[6];
- } uuid_t;
-
- /* uuid_create -- generate a UUID */
- int uuid_create(uuid_t * uuid);
-
- /* uuid_create_from_name -- create a UUID using a "name"
- from a "name space" */
- void uuid_create_from_name(
- uuid_t * uuid, /* resulting UUID */
- uuid_t nsid, /* UUID to serve as context, so identical
- names from different name spaces generate
- different UUIDs */
- void * name, /* the name from which to generate a UUID */
- int namelen /* the length of the name */
- );
-
- /* uuid_compare -- Compare two UUID's "lexically" and return
- -1 u1 is lexically before u2
- 0 u1 is equal to u2
- 1 u1 is lexically after u2
- Note: lexical ordering is not temporal ordering!
- */
- int uuid_compare(uuid_t *u1, uuid_t *u2);
-
- uuid.c
-
- #include "copyrt.h"
- #include <string.h>
- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- #include "sysdep.h"
- #include "uuid.h"
-
- /* various forward declarations */
- static int read_state(unsigned16 *clockseq, uuid_time_t *timestamp,
- uuid_node_t * node);
- static void write_state(unsigned16 clockseq, uuid_time_t timestamp,
- uuid_node_t node);
- static void format_uuid_v1(uuid_t * uuid, unsigned16 clockseq,
- uuid_time_t timestamp, uuid_node_t node);
- static void format_uuid_v3(uuid_t * uuid, unsigned char hash[16]);
- static void get_current_time(uuid_time_t * timestamp);
- static unsigned16 true_random(void);
-
-
- Leach, Salz expires Aug 1998 [Page 18]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- /* uuid_create -- generator a UUID */
- int uuid_create(uuid_t * uuid) {
- uuid_time_t timestamp, last_time;
- unsigned16 clockseq;
- uuid_node_t node;
- uuid_node_t last_node;
- int f;
-
- /* acquire system wide lock so we're alone */
- LOCK;
-
- /* get current time */
- get_current_time(×tamp);
-
- /* get node ID */
- get_ieee_node_identifier(&node);
-
- /* get saved state from NV storage */
- f = read_state(&clockseq, &last_time, &last_node);
-
- /* if no NV state, or if clock went backwards, or node ID changed
- (e.g., net card swap) change clockseq */
- if (!f || memcmp(&node, &last_node, sizeof(uuid_node_t)))
- clockseq = true_random();
- else if (timestamp < last_time)
- clockseq++;
-
- /* stuff fields into the UUID */
- format_uuid_v1(uuid, clockseq, timestamp, node);
-
- /* save the state for next time */
- write_state(clockseq, timestamp, node);
-
- UNLOCK;
- return(1);
- };
-
- /* format_uuid_v1 -- make a UUID from the timestamp, clockseq,
- and node ID */
- void format_uuid_v1(uuid_t * uuid, unsigned16 clock_seq, uuid_time_t
- timestamp, uuid_node_t node) {
- /* Construct a version 1 uuid with the information we've gathered
- * plus a few constants. */
- uuid->time_low = (unsigned long)(timestamp & 0xFFFFFFFF);
- uuid->time_mid = (unsigned short)((timestamp >> 32) & 0xFFFF);
- uuid->time_hi_and_version = (unsigned short)((timestamp >> 48) &
- 0x0FFF);
- uuid->time_hi_and_version |= (1 << 12);
- uuid->clock_seq_low = clock_seq & 0xFF;
- uuid->clock_seq_hi_and_reserved = (clock_seq & 0x3F00) >> 8;
- uuid->clock_seq_hi_and_reserved |= 0x80;
- memcpy(&uuid->node, &node, sizeof uuid->node);
- };
-
-
- Leach, Salz expires Aug 1998 [Page 19]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- /* data type for UUID generator persistent state */
- typedef struct {
- uuid_time_t ts; /* saved timestamp */
- uuid_node_t node; /* saved node ID */
- unsigned16 cs; /* saved clock sequence */
- } uuid_state;
-
- static uuid_state st;
-
- /* read_state -- read UUID generator state from non-volatile store */
- int read_state(unsigned16 *clockseq, uuid_time_t *timestamp,
- uuid_node_t *node) {
- FILE * fd;
- static int inited = 0;
-
- /* only need to read state once per boot */
- if (!inited) {
- fd = fopen("state", "rb");
- if (!fd)
- return (0);
- fread(&st, sizeof(uuid_state), 1, fd);
- fclose(fd);
- inited = 1;
- };
- *clockseq = st.cs;
- *timestamp = st.ts;
- *node = st.node;
- return(1);
- };
-
- /* write_state -- save UUID generator state back to non-volatile
- storage */
- void write_state(unsigned16 clockseq, uuid_time_t timestamp,
- uuid_node_t node) {
- FILE * fd;
- static int inited = 0;
- static uuid_time_t next_save;
-
- if (!inited) {
- next_save = timestamp;
- inited = 1;
- };
- /* always save state to volatile shared state */
- st.cs = clockseq;
- st.ts = timestamp;
- st.node = node;
- if (timestamp >= next_save) {
- fd = fopen("state", "wb");
- fwrite(&st, sizeof(uuid_state), 1, fd);
- fclose(fd);
- /* schedule next save for 10 seconds from now */
- next_save = timestamp + (10 * 10 * 1000 * 1000);
- };
- };
-
- Leach, Salz expires Aug 1998 [Page 20]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
-
- /* get-current_time -- get time as 60 bit 100ns ticks since whenever.
- Compensate for the fact that real clock resolution is
- less than 100ns. */
- void get_current_time(uuid_time_t * timestamp) {
- uuid_time_t time_now;
- static uuid_time_t time_last;
- static unsigned16 uuids_this_tick;
- static int inited = 0;
-
- if (!inited) {
- get_system_time(&time_now);
- uuids_this_tick = UUIDS_PER_TICK;
- inited = 1;
- };
-
- while (1) {
- get_system_time(&time_now);
-
- /* if clock reading changed since last UUID generated... */
- if (time_last != time_now) {
- /* reset count of uuids gen'd with this clock reading */
- uuids_this_tick = 0;
- break;
- };
- if (uuids_this_tick < UUIDS_PER_TICK) {
- uuids_this_tick++;
- break;
- };
- /* going too fast for our clock; spin */
- };
- /* add the count of uuids to low order bits of the clock reading */
- *timestamp = time_now + uuids_this_tick;
- };
-
- /* true_random -- generate a crypto-quality random number.
- This sample doesn't do that. */
- static unsigned16
- true_random(void)
- {
- static int inited = 0;
- uuid_time_t time_now;
-
- if (!inited) {
- get_system_time(&time_now);
- time_now = time_now/UUIDS_PER_TICK;
- srand((unsigned int)(((time_now >> 32) ^ time_now)&0xffffffff));
- inited = 1;
- };
-
- return (rand());
- }
-
-
-
- Leach, Salz expires Aug 1998 [Page 21]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- /* uuid_create_from_name -- create a UUID using a "name" from a "name
- space" */
- void uuid_create_from_name(
- uuid_t * uuid, /* resulting UUID */
- uuid_t nsid, /* UUID to serve as context, so identical
- names from different name spaces generate
- different UUIDs */
- void * name, /* the name from which to generate a UUID */
- int namelen /* the length of the name */
- ) {
- MD5_CTX c;
- unsigned char hash[16];
- uuid_t net_nsid; /* context UUID in network byte order */
-
- /* put name space ID in network byte order so it hashes the same
- no matter what endian machine we're on */
- net_nsid = nsid;
- htonl(net_nsid.time_low);
- htons(net_nsid.time_mid);
- htons(net_nsid.time_hi_and_version);
-
- MD5Init(&c);
- MD5Update(&c, &net_nsid, sizeof(uuid_t));
- MD5Update(&c, name, namelen);
- MD5Final(hash, &c);
-
- /* the hash is in network byte order at this point */
- format_uuid_v3(uuid, hash);
- };
-
- /* format_uuid_v3 -- make a UUID from a (pseudo)random 128 bit number
- */
- void format_uuid_v3(uuid_t * uuid, unsigned char hash[16]) {
- /* Construct a version 3 uuid with the (pseudo-)random number
- * plus a few constants. */
-
- memcpy(uuid, hash, sizeof(uuid_t));
-
- /* convert UUID to local byte order */
- ntohl(uuid->time_low);
- ntohs(uuid->time_mid);
- ntohs(uuid->time_hi_and_version);
-
- /* put in the variant and version bits */
- uuid->time_hi_and_version &= 0x0FFF;
- uuid->time_hi_and_version |= (3 << 12);
- uuid->clock_seq_hi_and_reserved &= 0x3F;
- uuid->clock_seq_hi_and_reserved |= 0x80;
- };
-
- /* uuid_compare -- Compare two UUID's "lexically" and return
- -1 u1 is lexically before u2
- 0 u1 is equal to u2
- 1 u1 is lexically after u2
-
- Leach, Salz expires Aug 1998 [Page 22]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- Note: lexical ordering is not temporal ordering!
- */
- int uuid_compare(uuid_t *u1, uuid_t *u2)
- {
- int i;
-
- #define CHECK(f1, f2) if (f1 != f2) return f1 < f2 ? -1 : 1;
- CHECK(u1->time_low, u2->time_low);
- CHECK(u1->time_mid, u2->time_mid);
- CHECK(u1->time_hi_and_version, u2->time_hi_and_version);
- CHECK(u1->clock_seq_hi_and_reserved, u2->clock_seq_hi_and_reserved);
- CHECK(u1->clock_seq_low, u2->clock_seq_low)
- for (i = 0; i < 6; i++) {
- if (u1->node[i] < u2->node[i])
- return -1;
- if (u1->node[i] > u2->node[i])
- return 1;
- }
- return 0;
- };
-
- sysdep.h
-
- #include "copyrt.h"
- /* remove the following define if you aren't running WIN32 */
- #define WININC 0
-
- #ifdef WININC
- #include <windows.h>
- #else
- #include <sys/types.h>
- #include <sys/time.h>
- #include <sys/sysinfo.h>
- #endif
-
- /* change to point to where MD5 .h's live */
- /* get MD5 sample implementation from RFC 1321 */
- #include "global.h"
- #include "md5.h"
-
- /* set the following to the number of 100ns ticks of the actual
- resolution of
- your system's clock */
- #define UUIDS_PER_TICK 1024
-
- /* Set the following to a call to acquire a system wide global lock
- */
- #define LOCK
- #define UNLOCK
-
- typedef unsigned long unsigned32;
- typedef unsigned short unsigned16;
- typedef unsigned char unsigned8;
- typedef unsigned char byte;
-
- Leach, Salz expires Aug 1998 [Page 23]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
-
- /* Set this to what your compiler uses for 64 bit data type */
- #ifdef WININC
- #define unsigned64_t unsigned __int64
- #define I64(C) C
- #else
- #define unsigned64_t unsigned long long
- #define I64(C) C##LL
- #endif
-
-
- typedef unsigned64_t uuid_time_t;
- typedef struct {
- char nodeID[6];
- } uuid_node_t;
-
- void get_ieee_node_identifier(uuid_node_t *node);
- void get_system_time(uuid_time_t *uuid_time);
- void get_random_info(char seed[16]);
-
-
- sysdep.c
-
- #include "copyrt.h"
- #include <stdio.h>
- #include "sysdep.h"
-
- /* system dependent call to get IEEE node ID.
- This sample implementation generates a random node ID
- */
- void get_ieee_node_identifier(uuid_node_t *node) {
- char seed[16];
- FILE * fd;
- static inited = 0;
- static uuid_node_t saved_node;
-
- if (!inited) {
- fd = fopen("nodeid", "rb");
- if (fd) {
- fread(&saved_node, sizeof(uuid_node_t), 1, fd);
- fclose(fd);
- }
- else {
- get_random_info(seed);
- seed[0] |= 0x80;
- memcpy(&saved_node, seed, sizeof(uuid_node_t));
- fd = fopen("nodeid", "wb");
- if (fd) {
- fwrite(&saved_node, sizeof(uuid_node_t), 1, fd);
- fclose(fd);
- };
- };
- inited = 1;
- };
-
- Leach, Salz expires Aug 1998 [Page 24]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- *node = saved_node;
- };
-
- /* system dependent call to get the current system time.
- Returned as 100ns ticks since Oct 15, 1582, but resolution may be
- less than 100ns.
- */
- #ifdef _WINDOWS_
-
- void get_system_time(uuid_time_t *uuid_time) {
- ULARGE_INTEGER time;
-
- GetSystemTimeAsFileTime((FILETIME *)&time);
-
- /* NT keeps time in FILETIME format which is 100ns ticks since
- Jan 1, 1601. UUIDs use time in 100ns ticks since Oct 15, 1582.
- The difference is 17 Days in Oct + 30 (Nov) + 31 (Dec)
- + 18 years and 5 leap days.
- */
-
- time.QuadPart +=
- (unsigned __int64) (1000*1000*10) // seconds
- * (unsigned __int64) (60 * 60 * 24) // days
- * (unsigned __int64) (17+30+31+365*18+5); // # of days
-
- *uuid_time = time.QuadPart;
-
- };
-
- void get_random_info(char seed[16]) {
- MD5_CTX c;
- typedef struct {
- MEMORYSTATUS m;
- SYSTEM_INFO s;
- FILETIME t;
- LARGE_INTEGER pc;
- DWORD tc;
- DWORD l;
- char hostname[MAX_COMPUTERNAME_LENGTH + 1];
- } randomness;
- randomness r;
-
- MD5Init(&c);
- /* memory usage stats */
- GlobalMemoryStatus(&r.m);
- /* random system stats */
- GetSystemInfo(&r.s);
- /* 100ns resolution (nominally) time of day */
- GetSystemTimeAsFileTime(&r.t);
- /* high resolution performance counter */
- QueryPerformanceCounter(&r.pc);
- /* milliseconds since last boot */
- r.tc = GetTickCount();
- r.l = MAX_COMPUTERNAME_LENGTH + 1;
-
- Leach, Salz expires Aug 1998 [Page 25]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- GetComputerName(r.hostname, &r.l );
- MD5Update(&c, &r, sizeof(randomness));
- MD5Final(seed, &c);
- };
- #else
-
- void get_system_time(uuid_time_t *uuid_time)
- {
- struct timeval tp;
-
- gettimeofday(&tp, (struct timezone *)0);
-
- /* Offset between UUID formatted times and Unix formatted times.
- UUID UTC base time is October 15, 1582.
- Unix base time is January 1, 1970.
- */
- *uuid_time = (tp.tv_sec * 10000000) + (tp.tv_usec * 10) +
- I64(0x01B21DD213814000);
- };
-
- void get_random_info(char seed[16]) {
- MD5_CTX c;
- typedef struct {
- struct sysinfo s;
- struct timeval t;
- char hostname[257];
- } randomness;
- randomness r;
-
- MD5Init(&c);
- sysinfo(&r.s);
- gettimeofday(&r.t, (struct timezone *)0);
- gethostname(r.hostname, 256);
- MD5Update(&c, &r, sizeof(randomness));
- MD5Final(seed, &c);
- };
-
- #endif
-
- utest.c
-
- #include "copyrt.h"
- #include "sysdep.h"
- #include <stdio.h>
- #include "uuid.h"
-
- uuid_t NameSpace_DNS = { /* 6ba7b810-9dad-11d1-80b4-00c04fd430c8 */
- 0x6ba7b810,
- 0x9dad,
- 0x11d1,
- 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8
- };
-
-
-
- Leach, Salz expires Aug 1998 [Page 26]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- /* puid -- print a UUID */
- void puid(uuid_t u);
-
- /* Simple driver for UUID generator */
- void main(int argc, char **argv) {
- uuid_t u;
- int f;
-
- uuid_create(&u);
- printf("uuid_create() -> "); puid(u);
-
- f = uuid_compare(&u, &u);
- printf("uuid_compare(u,u): %d\n", f); /* should be 0 */
- f = uuid_compare(&u, &NameSpace_DNS);
- printf("uuid_compare(u, NameSpace_DNS): %d\n", f); /* s.b. 1 */
- f = uuid_compare(&NameSpace_DNS, &u);
- printf("uuid_compare(NameSpace_DNS, u): %d\n", f); /* s.b. -1 */
-
- uuid_create_from_name(&u, NameSpace_DNS, "www.widgets.com", 15);
- printf("uuid_create_from_name() -> "); puid(u);
- };
-
- void puid(uuid_t u) {
- int i;
-
- printf("%8.8x-%4.4x-%4.4x-%2.2x%2.2x-", u.time_low, u.time_mid,
- u.time_hi_and_version, u.clock_seq_hi_and_reserved,
- u.clock_seq_low);
- for (i = 0; i < 6; i++)
- printf("%2.2x", u.node[i]);
- printf("\n");
- };
-
-Appendix B _ Sample output of utest
-
- uuid_create() -> 7d444840-9dc0-11d1-b245-5ffdce74fad2
- uuid_compare(u,u): 0
- uuid_compare(u, NameSpace_DNS): 1
- uuid_compare(NameSpace_DNS, u): -1
- uuid_create_from_name() -> e902893a-9d22-3c7e-a7b8-d6e313b71d9f
-
-Appendix C _ Some name space IDs
-
- This appendix lists the name space IDs for some potentially
- interesting name spaces, as initialized C structures and in the
- string representation defined in section 3.5
-
- uuid_t NameSpace_DNS = { /* 6ba7b810-9dad-11d1-80b4-00c04fd430c8 */
- 0x6ba7b810,
- 0x9dad,
- 0x11d1,
- 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8
- };
-
-
- Leach, Salz expires Aug 1998 [Page 27]
-
-
- Internet-Draft UUIDs and GUIDs (DRAFT) 02/04/98
-
-
- uuid_t NameSpace_URL = { /* 6ba7b811-9dad-11d1-80b4-00c04fd430c8 */
- 0x6ba7b811,
- 0x9dad,
- 0x11d1,
- 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8
- };
-
- uuid_t NameSpace_OID = { /* 6ba7b812-9dad-11d1-80b4-00c04fd430c8 */
- 0x6ba7b812,
- 0x9dad,
- 0x11d1,
- 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8
- };
-
- uuid_t NameSpace_X500 = { /* 6ba7b814-9dad-11d1-80b4-00c04fd430c8 */
- 0x6ba7b814,
- 0x9dad,
- 0x11d1,
- 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8
- };
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
diff --git a/doc/rfc4122.txt b/doc/rfc4122.txt
new file mode 100644
index 0000000..31ceaab
--- /dev/null
+++ b/doc/rfc4122.txt
@@ -0,0 +1,1795 @@
+
+
+
+
+
+
+Network Working Group P. Leach
+Request for Comments: 4122 Microsoft
+Category: Standards Track M. Mealling
+ Refactored Networks, LLC
+ R. Salz
+ DataPower Technology, Inc.
+ July 2005
+
+
+ A Universally Unique IDentifier (UUID) URN Namespace
+
+Status of This Memo
+
+ This document specifies an Internet standards track protocol for the
+ Internet community, and requests discussion and suggestions for
+ improvements. Please refer to the current edition of the "Internet
+ Official Protocol Standards" (STD 1) for the standardization state
+ and status of this protocol. Distribution of this memo is unlimited.
+
+Copyright Notice
+
+ Copyright (C) The Internet Society (2005).
+
+Abstract
+
+ This specification defines a Uniform Resource Name namespace for
+ UUIDs (Universally Unique IDentifier), also known as GUIDs (Globally
+ Unique IDentifier). A UUID is 128 bits long, and can guarantee
+ uniqueness across space and time. UUIDs were originally used in the
+ Apollo Network Computing System and later in the Open Software
+ Foundation's (OSF) Distributed Computing Environment (DCE), and then
+ in Microsoft Windows platforms.
+
+ This specification is derived from the DCE specification with the
+ kind permission of the OSF (now known as The Open Group).
+ Information from earlier versions of the DCE specification have been
+ incorporated into this document.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Leach, et al. Standards Track [Page 1]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+Table of Contents
+
+ 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
+ 2. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . 3
+ 3. Namespace Registration Template . . . . . . . . . . . . . . . 3
+ 4. Specification . . . . . . . . . . . . . . . . . . . . . . . . 5
+ 4.1. Format. . . . . . . . . . . . . . . . . . . . . . . . . . 5
+ 4.1.1. Variant. . . . . . . . . . . . . . . . . . . . . . 6
+ 4.1.2. Layout and Byte Order. . . . . . . . . . . . . . . 6
+ 4.1.3. Version. . . . . . . . . . . . . . . . . . . . . . 7
+ 4.1.4. Timestamp. . . . . . . . . . . . . . . . . . . . . 8
+ 4.1.5. Clock Sequence . . . . . . . . . . . . . . . . . . 8
+ 4.1.6. Node . . . . . . . . . . . . . . . . . . . . . . . 9
+ 4.1.7. Nil UUID . . . . . . . . . . . . . . . . . . . . . 9
+ 4.2. Algorithms for Creating a Time-Based UUID . . . . . . . . 9
+ 4.2.1. Basic Algorithm. . . . . . . . . . . . . . . . . . 10
+ 4.2.2. Generation Details . . . . . . . . . . . . . . . . 12
+ 4.3. Algorithm for Creating a Name-Based UUID. . . . . . . . . 13
+ 4.4. Algorithms for Creating a UUID from Truly Random or
+ Pseudo-Random Numbers . . . . . . . . . . . . . . . . . . 14
+ 4.5. Node IDs that Do Not Identify the Host. . . . . . . . . . 15
+ 5. Community Considerations . . . . . . . . . . . . . . . . . . . 15
+ 6. Security Considerations . . . . . . . . . . . . . . . . . . . 16
+ 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16
+ 8. Normative References . . . . . . . . . . . . . . . . . . . . . 16
+ A. Appendix A - Sample Implementation . . . . . . . . . . . . . . 18
+ B. Appendix B - Sample Output of utest . . . . . . . . . . . . . 29
+ C. Appendix C - Some Name Space IDs . . . . . . . . . . . . . . . 30
+
+1. Introduction
+
+ This specification defines a Uniform Resource Name namespace for
+ UUIDs (Universally Unique IDentifier), also known as GUIDs (Globally
+ Unique IDentifier). A UUID is 128 bits long, and requires no central
+ registration process.
+
+ The information here is meant to be a concise guide for those wishing
+ to implement services using UUIDs as URNs. Nothing in this document
+ should be construed to override the DCE standards that defined UUIDs.
+
+ There is an ITU-T Recommendation and ISO/IEC Standard [3] that are
+ derived from earlier versions of this document. Both sets of
+ specifications have been aligned, and are fully technically
+ compatible. In addition, a global registration function is being
+ provided by the Telecommunications Standardisation Bureau of ITU-T;
+ for details see <http://www.itu.int/ITU-T/asn1/uuid.html>.
+
+
+
+
+
+Leach, et al. Standards Track [Page 2]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+2. Motivation
+
+ One of the main reasons for using UUIDs is that no centralized
+ authority is required to administer them (although one format uses
+ IEEE 802 node identifiers, others do not). As a result, generation
+ on demand can be completely automated, and used for a variety of
+ purposes. The UUID generation algorithm described here supports very
+ high allocation rates of up to 10 million per second per machine if
+ necessary, so that they could even be used as transaction IDs.
+
+ UUIDs are of a fixed size (128 bits) which is reasonably small
+ compared to other alternatives. This lends itself well to sorting,
+ ordering, and hashing of all sorts, storing in databases, simple
+ allocation, and ease of programming in general.
+
+ Since UUIDs are unique and persistent, they make excellent Uniform
+ Resource Names. The unique ability to generate a new UUID without a
+ registration process allows for UUIDs to be one of the URNs with the
+ lowest minting cost.
+
+3. Namespace Registration Template
+
+ Namespace ID: UUID
+ Registration Information:
+ Registration date: 2003-10-01
+
+ Declared registrant of the namespace:
+ JTC 1/SC6 (ASN.1 Rapporteur Group)
+
+ Declaration of syntactic structure:
+ A UUID is an identifier that is unique across both space and time,
+ with respect to the space of all UUIDs. Since a UUID is a fixed
+ size and contains a time field, it is possible for values to
+ rollover (around A.D. 3400, depending on the specific algorithm
+ used). A UUID can be used for multiple purposes, from tagging
+ objects with an extremely short lifetime, to reliably identifying
+ very persistent objects across a network.
+
+ The internal representation of a UUID is a specific sequence of
+ bits in memory, as described in Section 4. To accurately
+ represent a UUID as a URN, it is necessary to convert the bit
+ sequence to a string representation.
+
+ Each field is treated as an integer and has its value printed as a
+ zero-filled hexadecimal digit string with the most significant
+ digit first. The hexadecimal values "a" through "f" are output as
+ lower case characters and are case insensitive on input.
+
+
+
+
+Leach, et al. Standards Track [Page 3]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ The formal definition of the UUID string representation is
+ provided by the following ABNF [7]:
+
+ UUID = time-low "-" time-mid "-"
+ time-high-and-version "-"
+ clock-seq-and-reserved
+ clock-seq-low "-" node
+ time-low = 4hexOctet
+ time-mid = 2hexOctet
+ time-high-and-version = 2hexOctet
+ clock-seq-and-reserved = hexOctet
+ clock-seq-low = hexOctet
+ node = 6hexOctet
+ hexOctet = hexDigit hexDigit
+ hexDigit =
+ "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9" /
+ "a" / "b" / "c" / "d" / "e" / "f" /
+ "A" / "B" / "C" / "D" / "E" / "F"
+
+ The following is an example of the string representation of a UUID as
+ a URN:
+
+ urn:uuid:f81d4fae-7dec-11d0-a765-00a0c91e6bf6
+
+ Relevant ancillary documentation:
+ [1][2]
+ Identifier uniqueness considerations:
+ This document specifies three algorithms to generate UUIDs: the
+ first leverages the unique values of 802 MAC addresses to
+ guarantee uniqueness, the second uses pseudo-random number
+ generators, and the third uses cryptographic hashing and
+ application-provided text strings. As a result, the UUIDs
+ generated according to the mechanisms here will be unique from all
+ other UUIDs that have been or will be assigned.
+
+ Identifier persistence considerations:
+ UUIDs are inherently very difficult to resolve in a global sense.
+ This, coupled with the fact that UUIDs are temporally unique
+ within their spatial context, ensures that UUIDs will remain as
+ persistent as possible.
+
+ Process of identifier assignment:
+ Generating a UUID does not require that a registration authority
+ be contacted. One algorithm requires a unique value over space
+ for each generator. This value is typically an IEEE 802 MAC
+ address, usually already available on network-connected hosts.
+ The address can be assigned from an address block obtained from
+ the IEEE registration authority. If no such address is available,
+
+
+
+Leach, et al. Standards Track [Page 4]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ or privacy concerns make its use undesirable, Section 4.5
+ specifies two alternatives. Another approach is to use version 3
+ or version 4 UUIDs as defined below.
+
+ Process for identifier resolution:
+ Since UUIDs are not globally resolvable, this is not applicable.
+
+ Rules for Lexical Equivalence:
+ Consider each field of the UUID to be an unsigned integer as shown
+ in the table in section Section 4.1.2. Then, to compare a pair of
+ UUIDs, arithmetically compare the corresponding fields from each
+ UUID in order of significance and according to their data type.
+ Two UUIDs are equal if and only if all the corresponding fields
+ are equal.
+
+ As an implementation note, equality comparison can be performed on
+ many systems by doing the appropriate byte-order canonicalization,
+ and then treating the two UUIDs as 128-bit unsigned integers.
+
+ UUIDs, as defined in this document, can also be ordered
+ lexicographically. For a pair of UUIDs, the first one follows the
+ second if the most significant field in which the UUIDs differ is
+ greater for the first UUID. The second precedes the first if the
+ most significant field in which the UUIDs differ is greater for
+ the second UUID.
+
+ Conformance with URN Syntax:
+ The string representation of a UUID is fully compatible with the
+ URN syntax. When converting from a bit-oriented, in-memory
+ representation of a UUID into a URN, care must be taken to
+ strictly adhere to the byte order issues mentioned in the string
+ representation section.
+
+ Validation mechanism:
+ Apart from determining whether the timestamp portion of the UUID
+ is in the future and therefore not yet assignable, there is no
+ mechanism for determining whether a UUID is 'valid'.
+
+ Scope:
+ UUIDs are global in scope.
+
+4. Specification
+
+4.1. Format
+
+ The UUID format is 16 octets; some bits of the eight octet variant
+ field specified below determine finer structure.
+
+
+
+
+Leach, et al. Standards Track [Page 5]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+4.1.1. Variant
+
+ The variant field determines the layout of the UUID. That is, the
+ interpretation of all other bits in the UUID depends on the setting
+ of the bits in the variant field. As such, it could more accurately
+ be called a type field; we retain the original term for
+ compatibility. The variant field consists of a variable number of
+ the most significant bits of octet 8 of the UUID.
+
+ The following table lists the contents of the variant field, where
+ the letter "x" indicates a "don't-care" value.
+
+ Msb0 Msb1 Msb2 Description
+
+ 0 x x Reserved, NCS backward compatibility.
+
+ 1 0 x The variant specified in this document.
+
+ 1 1 0 Reserved, Microsoft Corporation backward
+ compatibility
+
+ 1 1 1 Reserved for future definition.
+
+ Interoperability, in any form, with variants other than the one
+ defined here is not guaranteed, and is not likely to be an issue in
+ practice.
+
+4.1.2. Layout and Byte Order
+
+ To minimize confusion about bit assignments within octets, the UUID
+ record definition is defined only in terms of fields that are
+ integral numbers of octets. The fields are presented with the most
+ significant one first.
+
+ Field Data Type Octet Note
+ #
+
+ time_low unsigned 32 0-3 The low field of the
+ bit integer timestamp
+
+ time_mid unsigned 16 4-5 The middle field of the
+ bit integer timestamp
+
+ time_hi_and_version unsigned 16 6-7 The high field of the
+ bit integer timestamp multiplexed
+ with the version number
+
+
+
+
+
+Leach, et al. Standards Track [Page 6]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ clock_seq_hi_and_rese unsigned 8 8 The high field of the
+ rved bit integer clock sequence
+ multiplexed with the
+ variant
+
+ clock_seq_low unsigned 8 9 The low field of the
+ bit integer clock sequence
+
+ node unsigned 48 10-15 The spatially unique
+ bit integer node identifier
+
+ In the absence of explicit application or presentation protocol
+ specification to the contrary, a UUID is encoded as a 128-bit object,
+ as follows:
+
+ The fields are encoded as 16 octets, with the sizes and order of the
+ fields defined above, and with each field encoded with the Most
+ Significant Byte first (known as network byte order). Note that the
+ field names, particularly for multiplexed fields, follow historical
+ practice.
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | time_low |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | time_mid | time_hi_and_version |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ |clk_seq_hi_res | clk_seq_low | node (0-1) |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | node (2-5) |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+4.1.3. Version
+
+ The version number is in the most significant 4 bits of the time
+ stamp (bits 4 through 7 of the time_hi_and_version field).
+
+ The following table lists the currently-defined versions for this
+ UUID variant.
+
+ Msb0 Msb1 Msb2 Msb3 Version Description
+
+ 0 0 0 1 1 The time-based version
+ specified in this document.
+
+ 0 0 1 0 2 DCE Security version, with
+ embedded POSIX UIDs.
+
+
+
+Leach, et al. Standards Track [Page 7]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ 0 0 1 1 3 The name-based version
+ specified in this document
+ that uses MD5 hashing.
+
+ 0 1 0 0 4 The randomly or pseudo-
+ randomly generated version
+ specified in this document.
+
+ 0 1 0 1 5 The name-based version
+ specified in this document
+ that uses SHA-1 hashing.
+
+ The version is more accurately a sub-type; again, we retain the term
+ for compatibility.
+
+4.1.4. Timestamp
+
+ The timestamp is a 60-bit value. For UUID version 1, this is
+ represented by Coordinated Universal Time (UTC) as a count of 100-
+ nanosecond intervals since 00:00:00.00, 15 October 1582 (the date of
+ Gregorian reform to the Christian calendar).
+
+ For systems that do not have UTC available, but do have the local
+ time, they may use that instead of UTC, as long as they do so
+ consistently throughout the system. However, this is not recommended
+ since generating the UTC from local time only needs a time zone
+ offset.
+
+ For UUID version 3 or 5, the timestamp is a 60-bit value constructed
+ from a name as described in Section 4.3.
+
+ For UUID version 4, the timestamp is a randomly or pseudo-randomly
+ generated 60-bit value, as described in Section 4.4.
+
+4.1.5. Clock Sequence
+
+ For UUID version 1, the clock sequence is used to help avoid
+ duplicates that could arise when the clock is set backwards in time
+ or if the node ID changes.
+
+ If the clock is set backwards, or might have been set backwards
+ (e.g., while the system was powered off), and the UUID generator can
+ not be sure that no UUIDs were generated with timestamps larger than
+ the value to which the clock was set, then the clock sequence has to
+ be changed. If the previous value of the clock sequence is known, it
+ can just be incremented; otherwise it should be set to a random or
+ high-quality pseudo-random value.
+
+
+
+
+Leach, et al. Standards Track [Page 8]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ Similarly, if the node ID changes (e.g., because a network card has
+ been moved between machines), setting the clock sequence to a random
+ number minimizes the probability of a duplicate due to slight
+ differences in the clock settings of the machines. If the value of
+ clock sequence associated with the changed node ID were known, then
+ the clock sequence could just be incremented, but that is unlikely.
+
+ The clock sequence MUST be originally (i.e., once in the lifetime of
+ a system) initialized to a random number to minimize the correlation
+ across systems. This provides maximum protection against node
+ identifiers that may move or switch from system to system rapidly.
+ The initial value MUST NOT be correlated to the node identifier.
+
+ For UUID version 3 or 5, the clock sequence is a 14-bit value
+ constructed from a name as described in Section 4.3.
+
+ For UUID version 4, clock sequence is a randomly or pseudo-randomly
+ generated 14-bit value as described in Section 4.4.
+
+4.1.6. Node
+
+ For UUID version 1, the node field consists of an IEEE 802 MAC
+ address, usually the host address. For systems with multiple IEEE
+ 802 addresses, any available one can be used. The lowest addressed
+ octet (octet number 10) contains the global/local bit and the
+ unicast/multicast bit, and is the first octet of the address
+ transmitted on an 802.3 LAN.
+
+ For systems with no IEEE address, a randomly or pseudo-randomly
+ generated value may be used; see Section 4.5. The multicast bit must
+ be set in such addresses, in order that they will never conflict with
+ addresses obtained from network cards.
+
+ For UUID version 3 or 5, the node field is a 48-bit value constructed
+ from a name as described in Section 4.3.
+
+ For UUID version 4, the node field is a randomly or pseudo-randomly
+ generated 48-bit value as described in Section 4.4.
+
+4.1.7. Nil UUID
+
+ The nil UUID is special form of UUID that is specified to have all
+ 128 bits set to zero.
+
+4.2. Algorithms for Creating a Time-Based UUID
+
+ Various aspects of the algorithm for creating a version 1 UUID are
+ discussed in the following sections.
+
+
+
+Leach, et al. Standards Track [Page 9]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+4.2.1. Basic Algorithm
+
+ The following algorithm is simple, correct, and inefficient:
+
+ o Obtain a system-wide global lock
+
+ o From a system-wide shared stable store (e.g., a file), read the
+ UUID generator state: the values of the timestamp, clock sequence,
+ and node ID used to generate the last UUID.
+
+ o Get the current time as a 60-bit count of 100-nanosecond intervals
+ since 00:00:00.00, 15 October 1582.
+
+ o Get the current node ID.
+
+ o If the state was unavailable (e.g., non-existent or corrupted), or
+ the saved node ID is different than the current node ID, generate
+ a random clock sequence value.
+
+ o If the state was available, but the saved timestamp is later than
+ the current timestamp, increment the clock sequence value.
+
+ o Save the state (current timestamp, clock sequence, and node ID)
+ back to the stable store.
+
+ o Release the global lock.
+
+ o Format a UUID from the current timestamp, clock sequence, and node
+ ID values according to the steps in Section 4.2.2.
+
+ If UUIDs do not need to be frequently generated, the above algorithm
+ may be perfectly adequate. For higher performance requirements,
+ however, issues with the basic algorithm include:
+
+ o Reading the state from stable storage each time is inefficient.
+
+ o The resolution of the system clock may not be 100-nanoseconds.
+
+ o Writing the state to stable storage each time is inefficient.
+
+ o Sharing the state across process boundaries may be inefficient.
+
+ Each of these issues can be addressed in a modular fashion by local
+ improvements in the functions that read and write the state and read
+ the clock. We address each of them in turn in the following
+ sections.
+
+
+
+
+
+Leach, et al. Standards Track [Page 10]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+4.2.1.1. Reading Stable Storage
+
+ The state only needs to be read from stable storage once at boot
+ time, if it is read into a system-wide shared volatile store (and
+ updated whenever the stable store is updated).
+
+ If an implementation does not have any stable store available, then
+ it can always say that the values were unavailable. This is the
+ least desirable implementation because it will increase the frequency
+ of creation of new clock sequence numbers, which increases the
+ probability of duplicates.
+
+ If the node ID can never change (e.g., the net card is inseparable
+ from the system), or if any change also reinitializes the clock
+ sequence to a random value, then instead of keeping it in stable
+ store, the current node ID may be returned.
+
+4.2.1.2. System Clock Resolution
+
+ The timestamp is generated from the system time, whose resolution may
+ be less than the resolution of the UUID timestamp.
+
+ If UUIDs do not need to be frequently generated, the timestamp can
+ simply be the system time multiplied by the number of 100-nanosecond
+ intervals per system time interval.
+
+ If a system overruns the generator by requesting too many UUIDs
+ within a single system time interval, the UUID service MUST either
+ return an error, or stall the UUID generator until the system clock
+ catches up.
+
+ A high resolution timestamp can be simulated by keeping a count of
+ the number of UUIDs that have been generated with the same value of
+ the system time, and using it to construct the low order bits of the
+ timestamp. The count will range between zero and the number of
+ 100-nanosecond intervals per system time interval.
+
+ Note: If the processors overrun the UUID generation frequently,
+ additional node identifiers can be allocated to the system, which
+ will permit higher speed allocation by making multiple UUIDs
+ potentially available for each time stamp value.
+
+4.2.1.3. Writing Stable Storage
+
+ The state does not always need to be written to stable store every
+ time a UUID is generated. The timestamp in the stable store can be
+ periodically set to a value larger than any yet used in a UUID. As
+ long as the generated UUIDs have timestamps less than that value, and
+
+
+
+Leach, et al. Standards Track [Page 11]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ the clock sequence and node ID remain unchanged, only the shared
+ volatile copy of the state needs to be updated. Furthermore, if the
+ timestamp value in stable store is in the future by less than the
+ typical time it takes the system to reboot, a crash will not cause a
+ reinitialization of the clock sequence.
+
+4.2.1.4. Sharing State Across Processes
+
+ If it is too expensive to access shared state each time a UUID is
+ generated, then the system-wide generator can be implemented to
+ allocate a block of time stamps each time it is called; a per-
+ process generator can allocate from that block until it is exhausted.
+
+4.2.2. Generation Details
+
+ Version 1 UUIDs are generated according to the following algorithm:
+
+ o Determine the values for the UTC-based timestamp and clock
+ sequence to be used in the UUID, as described in Section 4.2.1.
+
+ o For the purposes of this algorithm, consider the timestamp to be a
+ 60-bit unsigned integer and the clock sequence to be a 14-bit
+ unsigned integer. Sequentially number the bits in a field,
+ starting with zero for the least significant bit.
+
+ o Set the time_low field equal to the least significant 32 bits
+ (bits zero through 31) of the timestamp in the same order of
+ significance.
+
+ o Set the time_mid field equal to bits 32 through 47 from the
+ timestamp in the same order of significance.
+
+ o Set the 12 least significant bits (bits zero through 11) of the
+ time_hi_and_version field equal to bits 48 through 59 from the
+ timestamp in the same order of significance.
+
+ o Set the four most significant bits (bits 12 through 15) of the
+ time_hi_and_version field to the 4-bit version number
+ corresponding to the UUID version being created, as shown in the
+ table above.
+
+ o Set the clock_seq_low field to the eight least significant bits
+ (bits zero through 7) of the clock sequence in the same order of
+ significance.
+
+
+
+
+
+
+
+Leach, et al. Standards Track [Page 12]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ o Set the 6 least significant bits (bits zero through 5) of the
+ clock_seq_hi_and_reserved field to the 6 most significant bits
+ (bits 8 through 13) of the clock sequence in the same order of
+ significance.
+
+ o Set the two most significant bits (bits 6 and 7) of the
+ clock_seq_hi_and_reserved to zero and one, respectively.
+
+ o Set the node field to the 48-bit IEEE address in the same order of
+ significance as the address.
+
+4.3. Algorithm for Creating a Name-Based UUID
+
+ The version 3 or 5 UUID is meant for generating UUIDs from "names"
+ that are drawn from, and unique within, some "name space". The
+ concept of name and name space should be broadly construed, and not
+ limited to textual names. For example, some name spaces are the
+ domain name system, URLs, ISO Object IDs (OIDs), X.500 Distinguished
+ Names (DNs), and reserved words in a programming language. The
+ mechanisms or conventions used for allocating names and ensuring
+ their uniqueness within their name spaces are beyond the scope of
+ this specification.
+
+ The requirements for these types of UUIDs are as follows:
+
+ o The UUIDs generated at different times from the same name in the
+ same namespace MUST be equal.
+
+ o The UUIDs generated from two different names in the same namespace
+ should be different (with very high probability).
+
+ o The UUIDs generated from the same name in two different namespaces
+ should be different with (very high probability).
+
+ o If two UUIDs that were generated from names are equal, then they
+ were generated from the same name in the same namespace (with very
+ high probability).
+
+ The algorithm for generating a UUID from a name and a name space are
+ as follows:
+
+ o Allocate a UUID to use as a "name space ID" for all UUIDs
+ generated from names in that name space; see Appendix C for some
+ pre-defined values.
+
+ o Choose either MD5 [4] or SHA-1 [8] as the hash algorithm; If
+ backward compatibility is not an issue, SHA-1 is preferred.
+
+
+
+
+Leach, et al. Standards Track [Page 13]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ o Convert the name to a canonical sequence of octets (as defined by
+ the standards or conventions of its name space); put the name
+ space ID in network byte order.
+
+ o Compute the hash of the name space ID concatenated with the name.
+
+ o Set octets zero through 3 of the time_low field to octets zero
+ through 3 of the hash.
+
+ o Set octets zero and one of the time_mid field to octets 4 and 5 of
+ the hash.
+
+ o Set octets zero and one of the time_hi_and_version field to octets
+ 6 and 7 of the hash.
+
+ o Set the four most significant bits (bits 12 through 15) of the
+ time_hi_and_version field to the appropriate 4-bit version number
+ from Section 4.1.3.
+
+ o Set the clock_seq_hi_and_reserved field to octet 8 of the hash.
+
+ o Set the two most significant bits (bits 6 and 7) of the
+ clock_seq_hi_and_reserved to zero and one, respectively.
+
+ o Set the clock_seq_low field to octet 9 of the hash.
+
+ o Set octets zero through five of the node field to octets 10
+ through 15 of the hash.
+
+ o Convert the resulting UUID to local byte order.
+
+4.4. Algorithms for Creating a UUID from Truly Random or
+ Pseudo-Random Numbers
+
+ The version 4 UUID is meant for generating UUIDs from truly-random or
+ pseudo-random numbers.
+
+ The algorithm is as follows:
+
+ o Set the two most significant bits (bits 6 and 7) of the
+ clock_seq_hi_and_reserved to zero and one, respectively.
+
+ o Set the four most significant bits (bits 12 through 15) of the
+ time_hi_and_version field to the 4-bit version number from
+ Section 4.1.3.
+
+ o Set all the other bits to randomly (or pseudo-randomly) chosen
+ values.
+
+
+
+Leach, et al. Standards Track [Page 14]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ See Section 4.5 for a discussion on random numbers.
+
+4.5. Node IDs that Do Not Identify the Host
+
+ This section describes how to generate a version 1 UUID if an IEEE
+ 802 address is not available, or its use is not desired.
+
+ One approach is to contact the IEEE and get a separate block of
+ addresses. At the time of writing, the application could be found at
+ <http://standards.ieee.org/regauth/oui/pilot-ind.html>, and the cost
+ was US$550.
+
+ A better solution is to obtain a 47-bit cryptographic quality random
+ number and use it as the low 47 bits of the node ID, with the least
+ significant bit of the first octet of the node ID set to one. This
+ bit is the unicast/multicast bit, which will never be set in IEEE 802
+ addresses obtained from network cards. Hence, there can never be a
+ conflict between UUIDs generated by machines with and without network
+ cards. (Recall that the IEEE 802 spec talks about transmission
+ order, which is the opposite of the in-memory representation that is
+ discussed in this document.)
+
+ For compatibility with earlier specifications, note that this
+ document uses the unicast/multicast bit, instead of the arguably more
+ correct local/global bit.
+
+ Advice on generating cryptographic-quality random numbers can be
+ found in RFC1750 [5].
+
+ In addition, items such as the computer's name and the name of the
+ operating system, while not strictly speaking random, will help
+ differentiate the results from those obtained by other systems.
+
+ The exact algorithm to generate a node ID using these data is system
+ specific, because both the data available and the functions to obtain
+ them are often very system specific. A generic approach, however, is
+ to accumulate as many sources as possible into a buffer, use a
+ message digest such as MD5 [4] or SHA-1 [8], take an arbitrary 6
+ bytes from the hash value, and set the multicast bit as described
+ above.
+
+5. Community Considerations
+
+ The use of UUIDs is extremely pervasive in computing. They comprise
+ the core identifier infrastructure for many operating systems
+ (Microsoft Windows) and applications (the Mozilla browser) and in
+ many cases, become exposed to the Web in many non-standard ways.
+
+
+
+
+Leach, et al. Standards Track [Page 15]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ This specification attempts to standardize that practice as openly as
+ possible and in a way that attempts to benefit the entire Internet.
+
+6. Security Considerations
+
+ Do not assume that UUIDs are hard to guess; they should not be used
+ as security capabilities (identifiers whose mere possession grants
+ access), for example. A predictable random number source will
+ exacerbate the situation.
+
+ Do not assume that it is easy to determine if a UUID has been
+ slightly transposed in order to redirect a reference to another
+ object. Humans do not have the ability to easily check the integrity
+ of a UUID by simply glancing at it.
+
+ Distributed applications generating UUIDs at a variety of hosts must
+ be willing to rely on the random number source at all hosts. If this
+ is not feasible, the namespace variant should be used.
+
+7. Acknowledgments
+
+ This document draws heavily on the OSF DCE specification for UUIDs.
+ Ted Ts'o provided helpful comments, especially on the byte ordering
+ section which we mostly plagiarized from a proposed wording he
+ supplied (all errors in that section are our responsibility,
+ however).
+
+ We are also grateful to the careful reading and bit-twiddling of Ralf
+ S. Engelschall, John Larmouth, and Paul Thorpe. Professor Larmouth
+ was also invaluable in achieving coordination with ISO/IEC.
+
+8. Normative References
+
+ [1] Zahn, L., Dineen, T., and P. Leach, "Network Computing
+ Architecture", ISBN 0-13-611674-4, January 1990.
+
+ [2] "DCE: Remote Procedure Call", Open Group CAE Specification C309,
+ ISBN 1-85912-041-5, August 1994.
+
+ [3] ISO/IEC 9834-8:2004 Information Technology, "Procedures for the
+ operation of OSI Registration Authorities: Generation and
+ registration of Universally Unique Identifiers (UUIDs) and their
+ use as ASN.1 Object Identifier components" ITU-T Rec. X.667,
+ 2004.
+
+ [4] Rivest, R., "The MD5 Message-Digest Algorithm ", RFC 1321, April
+ 1992.
+
+
+
+
+Leach, et al. Standards Track [Page 16]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ [5] Eastlake, D., 3rd, Schiller, J., and S. Crocker, "Randomness
+ Requirements for Security", BCP 106, RFC 4086, June 2005.
+
+ [6] Moats, R., "URN Syntax", RFC 2141, May 1997.
+
+ [7] Crocker, D. and P. Overell, "Augmented BNF for Syntax
+ Specifications: ABNF", RFC 2234, November 1997.
+
+ [8] National Institute of Standards and Technology, "Secure Hash
+ Standard", FIPS PUB 180-1, April 1995,
+ <http://www.itl.nist.gov/fipspubs/fip180-1.htm>.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Leach, et al. Standards Track [Page 17]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+Appendix A. Appendix A - Sample Implementation
+
+ This implementation consists of 5 files: uuid.h, uuid.c, sysdep.h,
+ sysdep.c and utest.c. The uuid.* files are the system independent
+ implementation of the UUID generation algorithms described above,
+ with all the optimizations described above except efficient state
+ sharing across processes included. The code has been tested on Linux
+ (Red Hat 4.0) with GCC (2.7.2), and Windows NT 4.0 with VC++ 5.0.
+ The code assumes 64-bit integer support, which makes it much clearer.
+
+ All the following source files should have the following copyright
+ notice included:
+
+copyrt.h
+
+/*
+** Copyright (c) 1990- 1993, 1996 Open Software Foundation, Inc.
+** Copyright (c) 1989 by Hewlett-Packard Company, Palo Alto, Ca. &
+** Digital Equipment Corporation, Maynard, Mass.
+** Copyright (c) 1998 Microsoft.
+** To anyone who acknowledges that this file is provided "AS IS"
+** without any express or implied warranty: permission to use, copy,
+** modify, and distribute this file for any purpose is hereby
+** granted without fee, provided that the above copyright notices and
+** this notice appears in all source code copies, and that none of
+** the names of Open Software Foundation, Inc., Hewlett-Packard
+** Company, Microsoft, or Digital Equipment Corporation be used in
+** advertising or publicity pertaining to distribution of the software
+** without specific, written prior permission. Neither Open Software
+** Foundation, Inc., Hewlett-Packard Company, Microsoft, nor Digital
+** Equipment Corporation makes any representations about the
+** suitability of this software for any purpose.
+*/
+
+
+uuid.h
+
+#include "copyrt.h"
+#undef uuid_t
+typedef struct {
+ unsigned32 time_low;
+ unsigned16 time_mid;
+ unsigned16 time_hi_and_version;
+ unsigned8 clock_seq_hi_and_reserved;
+ unsigned8 clock_seq_low;
+ byte node[6];
+} uuid_t;
+
+
+
+
+Leach, et al. Standards Track [Page 18]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+/* uuid_create -- generate a UUID */
+int uuid_create(uuid_t * uuid);
+
+/* uuid_create_md5_from_name -- create a version 3 (MD5) UUID using a
+ "name" from a "name space" */
+void uuid_create_md5_from_name(
+ uuid_t *uuid, /* resulting UUID */
+ uuid_t nsid, /* UUID of the namespace */
+ void *name, /* the name from which to generate a UUID */
+ int namelen /* the length of the name */
+);
+
+/* uuid_create_sha1_from_name -- create a version 5 (SHA-1) UUID
+ using a "name" from a "name space" */
+void uuid_create_sha1_from_name(
+
+ uuid_t *uuid, /* resulting UUID */
+ uuid_t nsid, /* UUID of the namespace */
+ void *name, /* the name from which to generate a UUID */
+ int namelen /* the length of the name */
+);
+
+/* uuid_compare -- Compare two UUID's "lexically" and return
+ -1 u1 is lexically before u2
+ 0 u1 is equal to u2
+ 1 u1 is lexically after u2
+ Note that lexical ordering is not temporal ordering!
+*/
+int uuid_compare(uuid_t *u1, uuid_t *u2);
+
+
+uuid.c
+
+#include "copyrt.h"
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include "sysdep.h"
+#include "uuid.h"
+
+/* various forward declarations */
+static int read_state(unsigned16 *clockseq, uuid_time_t *timestamp,
+ uuid_node_t *node);
+static void write_state(unsigned16 clockseq, uuid_time_t timestamp,
+ uuid_node_t node);
+static void format_uuid_v1(uuid_t *uuid, unsigned16 clockseq,
+ uuid_time_t timestamp, uuid_node_t node);
+
+
+
+Leach, et al. Standards Track [Page 19]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+static void format_uuid_v3or5(uuid_t *uuid, unsigned char hash[16],
+ int v);
+static void get_current_time(uuid_time_t *timestamp);
+static unsigned16 true_random(void);
+
+/* uuid_create -- generator a UUID */
+int uuid_create(uuid_t *uuid)
+{
+ uuid_time_t timestamp, last_time;
+ unsigned16 clockseq;
+ uuid_node_t node;
+ uuid_node_t last_node;
+ int f;
+
+ /* acquire system-wide lock so we're alone */
+ LOCK;
+ /* get time, node ID, saved state from non-volatile storage */
+ get_current_time(×tamp);
+ get_ieee_node_identifier(&node);
+ f = read_state(&clockseq, &last_time, &last_node);
+
+ /* if no NV state, or if clock went backwards, or node ID
+ changed (e.g., new network card) change clockseq */
+ if (!f || memcmp(&node, &last_node, sizeof node))
+ clockseq = true_random();
+ else if (timestamp < last_time)
+ clockseq++;
+
+ /* save the state for next time */
+ write_state(clockseq, timestamp, node);
+
+ UNLOCK;
+
+ /* stuff fields into the UUID */
+ format_uuid_v1(uuid, clockseq, timestamp, node);
+ return 1;
+}
+
+/* format_uuid_v1 -- make a UUID from the timestamp, clockseq,
+ and node ID */
+void format_uuid_v1(uuid_t* uuid, unsigned16 clock_seq,
+ uuid_time_t timestamp, uuid_node_t node)
+{
+ /* Construct a version 1 uuid with the information we've gathered
+ plus a few constants. */
+ uuid->time_low = (unsigned long)(timestamp & 0xFFFFFFFF);
+ uuid->time_mid = (unsigned short)((timestamp >> 32) & 0xFFFF);
+ uuid->time_hi_and_version =
+
+
+
+Leach, et al. Standards Track [Page 20]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ (unsigned short)((timestamp >> 48) & 0x0FFF);
+ uuid->time_hi_and_version |= (1 << 12);
+ uuid->clock_seq_low = clock_seq & 0xFF;
+ uuid->clock_seq_hi_and_reserved = (clock_seq & 0x3F00) >> 8;
+ uuid->clock_seq_hi_and_reserved |= 0x80;
+ memcpy(&uuid->node, &node, sizeof uuid->node);
+}
+
+/* data type for UUID generator persistent state */
+typedef struct {
+ uuid_time_t ts; /* saved timestamp */
+ uuid_node_t node; /* saved node ID */
+ unsigned16 cs; /* saved clock sequence */
+} uuid_state;
+
+static uuid_state st;
+
+/* read_state -- read UUID generator state from non-volatile store */
+int read_state(unsigned16 *clockseq, uuid_time_t *timestamp,
+ uuid_node_t *node)
+{
+ static int inited = 0;
+ FILE *fp;
+
+ /* only need to read state once per boot */
+ if (!inited) {
+ fp = fopen("state", "rb");
+ if (fp == NULL)
+ return 0;
+ fread(&st, sizeof st, 1, fp);
+ fclose(fp);
+ inited = 1;
+ }
+ *clockseq = st.cs;
+ *timestamp = st.ts;
+ *node = st.node;
+ return 1;
+}
+
+/* write_state -- save UUID generator state back to non-volatile
+ storage */
+void write_state(unsigned16 clockseq, uuid_time_t timestamp,
+ uuid_node_t node)
+{
+ static int inited = 0;
+ static uuid_time_t next_save;
+ FILE* fp;
+
+
+
+
+Leach, et al. Standards Track [Page 21]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ if (!inited) {
+ next_save = timestamp;
+ inited = 1;
+ }
+
+ /* always save state to volatile shared state */
+ st.cs = clockseq;
+ st.ts = timestamp;
+ st.node = node;
+ if (timestamp >= next_save) {
+ fp = fopen("state", "wb");
+ fwrite(&st, sizeof st, 1, fp);
+ fclose(fp);
+ /* schedule next save for 10 seconds from now */
+ next_save = timestamp + (10 * 10 * 1000 * 1000);
+ }
+}
+
+/* get-current_time -- get time as 60-bit 100ns ticks since UUID epoch.
+ Compensate for the fact that real clock resolution is
+ less than 100ns. */
+void get_current_time(uuid_time_t *timestamp)
+{
+ static int inited = 0;
+ static uuid_time_t time_last;
+ static unsigned16 uuids_this_tick;
+ uuid_time_t time_now;
+
+ if (!inited) {
+ get_system_time(&time_now);
+ uuids_this_tick = UUIDS_PER_TICK;
+ inited = 1;
+ }
+
+ for ( ; ; ) {
+ get_system_time(&time_now);
+
+ /* if clock reading changed since last UUID generated, */
+ if (time_last != time_now) {
+ /* reset count of uuids gen'd with this clock reading */
+ uuids_this_tick = 0;
+ time_last = time_now;
+ break;
+ }
+ if (uuids_this_tick < UUIDS_PER_TICK) {
+ uuids_this_tick++;
+ break;
+ }
+
+
+
+Leach, et al. Standards Track [Page 22]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ /* going too fast for our clock; spin */
+ }
+ /* add the count of uuids to low order bits of the clock reading */
+ *timestamp = time_now + uuids_this_tick;
+}
+
+/* true_random -- generate a crypto-quality random number.
+ **This sample doesn't do that.** */
+static unsigned16 true_random(void)
+{
+ static int inited = 0;
+ uuid_time_t time_now;
+
+ if (!inited) {
+ get_system_time(&time_now);
+ time_now = time_now / UUIDS_PER_TICK;
+ srand((unsigned int)
+ (((time_now >> 32) ^ time_now) & 0xffffffff));
+ inited = 1;
+ }
+
+ return rand();
+}
+
+/* uuid_create_md5_from_name -- create a version 3 (MD5) UUID using a
+ "name" from a "name space" */
+void uuid_create_md5_from_name(uuid_t *uuid, uuid_t nsid, void *name,
+ int namelen)
+{
+ MD5_CTX c;
+ unsigned char hash[16];
+ uuid_t net_nsid;
+
+ /* put name space ID in network byte order so it hashes the same
+ no matter what endian machine we're on */
+ net_nsid = nsid;
+ net_nsid.time_low = htonl(net_nsid.time_low);
+ net_nsid.time_mid = htons(net_nsid.time_mid);
+ net_nsid.time_hi_and_version = htons(net_nsid.time_hi_and_version);
+
+ MD5Init(&c);
+ MD5Update(&c, &net_nsid, sizeof net_nsid);
+ MD5Update(&c, name, namelen);
+ MD5Final(hash, &c);
+
+ /* the hash is in network byte order at this point */
+ format_uuid_v3or5(uuid, hash, 3);
+}
+
+
+
+Leach, et al. Standards Track [Page 23]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+void uuid_create_sha1_from_name(uuid_t *uuid, uuid_t nsid, void *name,
+ int namelen)
+{
+ SHA_CTX c;
+ unsigned char hash[20];
+ uuid_t net_nsid;
+
+ /* put name space ID in network byte order so it hashes the same
+ no matter what endian machine we're on */
+ net_nsid = nsid;
+ net_nsid.time_low = htonl(net_nsid.time_low);
+ net_nsid.time_mid = htons(net_nsid.time_mid);
+ net_nsid.time_hi_and_version = htons(net_nsid.time_hi_and_version);
+
+ SHA1_Init(&c);
+ SHA1_Update(&c, &net_nsid, sizeof net_nsid);
+ SHA1_Update(&c, name, namelen);
+ SHA1_Final(hash, &c);
+
+ /* the hash is in network byte order at this point */
+ format_uuid_v3or5(uuid, hash, 5);
+}
+
+/* format_uuid_v3or5 -- make a UUID from a (pseudo)random 128-bit
+ number */
+void format_uuid_v3or5(uuid_t *uuid, unsigned char hash[16], int v)
+{
+ /* convert UUID to local byte order */
+ memcpy(uuid, hash, sizeof *uuid);
+ uuid->time_low = ntohl(uuid->time_low);
+ uuid->time_mid = ntohs(uuid->time_mid);
+ uuid->time_hi_and_version = ntohs(uuid->time_hi_and_version);
+
+ /* put in the variant and version bits */
+ uuid->time_hi_and_version &= 0x0FFF;
+ uuid->time_hi_and_version |= (v << 12);
+ uuid->clock_seq_hi_and_reserved &= 0x3F;
+ uuid->clock_seq_hi_and_reserved |= 0x80;
+}
+
+/* uuid_compare -- Compare two UUID's "lexically" and return */
+#define CHECK(f1, f2) if (f1 != f2) return f1 < f2 ? -1 : 1;
+int uuid_compare(uuid_t *u1, uuid_t *u2)
+{
+ int i;
+
+ CHECK(u1->time_low, u2->time_low);
+ CHECK(u1->time_mid, u2->time_mid);
+
+
+
+Leach, et al. Standards Track [Page 24]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ CHECK(u1->time_hi_and_version, u2->time_hi_and_version);
+ CHECK(u1->clock_seq_hi_and_reserved, u2->clock_seq_hi_and_reserved);
+ CHECK(u1->clock_seq_low, u2->clock_seq_low)
+ for (i = 0; i < 6; i++) {
+ if (u1->node[i] < u2->node[i])
+ return -1;
+ if (u1->node[i] > u2->node[i])
+ return 1;
+ }
+ return 0;
+}
+#undef CHECK
+
+
+sysdep.h
+
+#include "copyrt.h"
+/* remove the following define if you aren't running WIN32 */
+#define WININC 0
+
+#ifdef WININC
+#include <windows.h>
+#else
+#include <sys/types.h>
+#include <sys/time.h>
+#include <sys/sysinfo.h>
+#endif
+
+#include "global.h"
+/* change to point to where MD5 .h's live; RFC 1321 has sample
+ implementation */
+#include "md5.h"
+
+/* set the following to the number of 100ns ticks of the actual
+ resolution of your system's clock */
+#define UUIDS_PER_TICK 1024
+
+/* Set the following to a calls to get and release a global lock */
+#define LOCK
+#define UNLOCK
+
+typedef unsigned long unsigned32;
+typedef unsigned short unsigned16;
+typedef unsigned char unsigned8;
+typedef unsigned char byte;
+
+/* Set this to what your compiler uses for 64-bit data type */
+#ifdef WININC
+
+
+
+Leach, et al. Standards Track [Page 25]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+#define unsigned64_t unsigned __int64
+#define I64(C) C
+#else
+#define unsigned64_t unsigned long long
+#define I64(C) C##LL
+#endif
+
+typedef unsigned64_t uuid_time_t;
+typedef struct {
+ char nodeID[6];
+} uuid_node_t;
+
+void get_ieee_node_identifier(uuid_node_t *node);
+void get_system_time(uuid_time_t *uuid_time);
+void get_random_info(char seed[16]);
+
+
+sysdep.c
+
+#include "copyrt.h"
+#include <stdio.h>
+#include "sysdep.h"
+
+/* system dependent call to get IEEE node ID.
+ This sample implementation generates a random node ID. */
+void get_ieee_node_identifier(uuid_node_t *node)
+{
+ static inited = 0;
+ static uuid_node_t saved_node;
+ char seed[16];
+ FILE *fp;
+
+ if (!inited) {
+ fp = fopen("nodeid", "rb");
+ if (fp) {
+ fread(&saved_node, sizeof saved_node, 1, fp);
+ fclose(fp);
+ }
+ else {
+ get_random_info(seed);
+ seed[0] |= 0x01;
+ memcpy(&saved_node, seed, sizeof saved_node);
+ fp = fopen("nodeid", "wb");
+ if (fp) {
+ fwrite(&saved_node, sizeof saved_node, 1, fp);
+ fclose(fp);
+ }
+ }
+
+
+
+Leach, et al. Standards Track [Page 26]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ inited = 1;
+ }
+
+ *node = saved_node;
+}
+
+/* system dependent call to get the current system time. Returned as
+ 100ns ticks since UUID epoch, but resolution may be less than
+ 100ns. */
+#ifdef _WINDOWS_
+
+void get_system_time(uuid_time_t *uuid_time)
+{
+ ULARGE_INTEGER time;
+
+ /* NT keeps time in FILETIME format which is 100ns ticks since
+ Jan 1, 1601. UUIDs use time in 100ns ticks since Oct 15, 1582.
+ The difference is 17 Days in Oct + 30 (Nov) + 31 (Dec)
+ + 18 years and 5 leap days. */
+ GetSystemTimeAsFileTime((FILETIME *)&time);
+ time.QuadPart +=
+
+ (unsigned __int64) (1000*1000*10) // seconds
+ * (unsigned __int64) (60 * 60 * 24) // days
+ * (unsigned __int64) (17+30+31+365*18+5); // # of days
+ *uuid_time = time.QuadPart;
+}
+
+/* Sample code, not for use in production; see RFC 1750 */
+void get_random_info(char seed[16])
+{
+ MD5_CTX c;
+ struct {
+ MEMORYSTATUS m;
+ SYSTEM_INFO s;
+ FILETIME t;
+ LARGE_INTEGER pc;
+ DWORD tc;
+ DWORD l;
+ char hostname[MAX_COMPUTERNAME_LENGTH + 1];
+ } r;
+
+ MD5Init(&c);
+ GlobalMemoryStatus(&r.m);
+ GetSystemInfo(&r.s);
+ GetSystemTimeAsFileTime(&r.t);
+ QueryPerformanceCounter(&r.pc);
+ r.tc = GetTickCount();
+
+
+
+Leach, et al. Standards Track [Page 27]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+ r.l = MAX_COMPUTERNAME_LENGTH + 1;
+ GetComputerName(r.hostname, &r.l);
+ MD5Update(&c, &r, sizeof r);
+ MD5Final(seed, &c);
+}
+
+#else
+
+void get_system_time(uuid_time_t *uuid_time)
+{
+ struct timeval tp;
+
+ gettimeofday(&tp, (struct timezone *)0);
+
+ /* Offset between UUID formatted times and Unix formatted times.
+ UUID UTC base time is October 15, 1582.
+ Unix base time is January 1, 1970.*/
+ *uuid_time = ((unsigned64)tp.tv_sec * 10000000)
+ + ((unsigned64)tp.tv_usec * 10)
+ + I64(0x01B21DD213814000);
+}
+
+/* Sample code, not for use in production; see RFC 1750 */
+void get_random_info(char seed[16])
+{
+ MD5_CTX c;
+ struct {
+ struct sysinfo s;
+ struct timeval t;
+ char hostname[257];
+ } r;
+
+ MD5Init(&c);
+ sysinfo(&r.s);
+ gettimeofday(&r.t, (struct timezone *)0);
+ gethostname(r.hostname, 256);
+ MD5Update(&c, &r, sizeof r);
+ MD5Final(seed, &c);
+}
+
+#endif
+
+utest.c
+
+#include "copyrt.h"
+#include "sysdep.h"
+#include <stdio.h>
+#include "uuid.h"
+
+
+
+Leach, et al. Standards Track [Page 28]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+uuid_t NameSpace_DNS = { /* 6ba7b810-9dad-11d1-80b4-00c04fd430c8 */
+ 0x6ba7b810,
+ 0x9dad,
+ 0x11d1,
+ 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8
+};
+
+/* puid -- print a UUID */
+void puid(uuid_t u)
+{
+ int i;
+
+ printf("%8.8x-%4.4x-%4.4x-%2.2x%2.2x-", u.time_low, u.time_mid,
+ u.time_hi_and_version, u.clock_seq_hi_and_reserved,
+ u.clock_seq_low);
+ for (i = 0; i < 6; i++)
+ printf("%2.2x", u.node[i]);
+ printf("\n");
+}
+
+/* Simple driver for UUID generator */
+void main(int argc, char **argv)
+{
+ uuid_t u;
+ int f;
+
+ uuid_create(&u);
+ printf("uuid_create(): "); puid(u);
+
+ f = uuid_compare(&u, &u);
+ printf("uuid_compare(u,u): %d\n", f); /* should be 0 */
+ f = uuid_compare(&u, &NameSpace_DNS);
+ printf("uuid_compare(u, NameSpace_DNS): %d\n", f); /* s.b. 1 */
+ f = uuid_compare(&NameSpace_DNS, &u);
+ printf("uuid_compare(NameSpace_DNS, u): %d\n", f); /* s.b. -1 */
+ uuid_create_md5_from_name(&u, NameSpace_DNS, "www.widgets.com", 15);
+ printf("uuid_create_md5_from_name(): "); puid(u);
+}
+
+Appendix B. Appendix B - Sample Output of utest
+
+ uuid_create(): 7d444840-9dc0-11d1-b245-5ffdce74fad2
+ uuid_compare(u,u): 0
+ uuid_compare(u, NameSpace_DNS): 1
+ uuid_compare(NameSpace_DNS, u): -1
+ uuid_create_md5_from_name(): e902893a-9d22-3c7e-a7b8-d6e313b71d9f
+
+
+
+
+
+Leach, et al. Standards Track [Page 29]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+Appendix C. Appendix C - Some Name Space IDs
+
+ This appendix lists the name space IDs for some potentially
+ interesting name spaces, as initialized C structures and in the
+ string representation defined above.
+
+ /* Name string is a fully-qualified domain name */
+ uuid_t NameSpace_DNS = { /* 6ba7b810-9dad-11d1-80b4-00c04fd430c8 */
+ 0x6ba7b810,
+ 0x9dad,
+ 0x11d1,
+ 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8
+ };
+
+ /* Name string is a URL */
+ uuid_t NameSpace_URL = { /* 6ba7b811-9dad-11d1-80b4-00c04fd430c8 */
+ 0x6ba7b811,
+ 0x9dad,
+ 0x11d1,
+ 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8
+ };
+
+ /* Name string is an ISO OID */
+ uuid_t NameSpace_OID = { /* 6ba7b812-9dad-11d1-80b4-00c04fd430c8 */
+ 0x6ba7b812,
+ 0x9dad,
+ 0x11d1,
+ 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8
+ };
+
+ /* Name string is an X.500 DN (in DER or a text output format) */
+ uuid_t NameSpace_X500 = { /* 6ba7b814-9dad-11d1-80b4-00c04fd430c8 */
+ 0x6ba7b814,
+ 0x9dad,
+ 0x11d1,
+ 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8
+ };
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Leach, et al. Standards Track [Page 30]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+Authors' Addresses
+
+ Paul J. Leach
+ Microsoft
+ 1 Microsoft Way
+ Redmond, WA 98052
+ US
+
+ Phone: +1 425-882-8080
+ EMail: paulle@microsoft.com
+
+
+ Michael Mealling
+ Refactored Networks, LLC
+ 1635 Old Hwy 41
+ Suite 112, Box 138
+ Kennesaw, GA 30152
+ US
+
+ Phone: +1-678-581-9656
+ EMail: michael@refactored-networks.com
+ URI: http://www.refactored-networks.com
+
+
+ Rich Salz
+ DataPower Technology, Inc.
+ 1 Alewife Center
+ Cambridge, MA 02142
+ US
+
+ Phone: +1 617-864-0455
+ EMail: rsalz@datapower.com
+ URI: http://www.datapower.com
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Leach, et al. Standards Track [Page 31]
+
+RFC 4122 A UUID URN Namespace July 2005
+
+
+Full Copyright Statement
+
+ Copyright (C) The Internet Society (2005).
+
+ This document is subject to the rights, licenses and restrictions
+ contained in BCP 78, and except as set forth therein, the authors
+ retain all their rights.
+
+ This document and the information contained herein are provided on an
+ "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
+ OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
+ ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
+ INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
+ INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
+ WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
+
+Intellectual Property
+
+ The IETF takes no position regarding the validity or scope of any
+ Intellectual Property Rights or other rights that might be claimed to
+ pertain to the implementation or use of the technology described in
+ this document or the extent to which any license under such rights
+ might or might not be available; nor does it represent that it has
+ made any independent effort to identify any such rights. Information
+ on the procedures with respect to rights in RFC documents can be
+ found in BCP 78 and BCP 79.
+
+ Copies of IPR disclosures made to the IETF Secretariat and any
+ assurances of licenses to be made available, or the result of an
+ attempt made to obtain a general license or permission for the use of
+ such proprietary rights by implementers or users of this
+ specification can be obtained from the IETF on-line IPR repository at
+ http://www.ietf.org/ipr.
+
+ The IETF invites any interested party to bring to its attention any
+ copyrights, patents or patent applications, or other proprietary
+ rights that may cover technology that may be required to implement
+ this standard. Please address the information to the IETF at ietf-
+ ipr@ietf.org.
+
+Acknowledgement
+
+ Funding for the RFC Editor function is currently provided by the
+ Internet Society.
+
+
+
+
+
+
+
+Leach, et al. Standards Track [Page 32]
+
diff --git a/util/debian.exclude b/util/debian.exclude
index d663b73..2be83f1 100644
--- a/util/debian.exclude
+++ b/util/debian.exclude
@@ -10,4 +10,4 @@
.exclude-file
po/stamp-cat-id
po/cat-id-tbl.c
-doc/draft-leach-uuids-guids-01.txt
+doc/rfc4122.txt