UUIDGenerator


1   /**
2    * Redistribution and use of this software and associated documentation
3    * ("Software"), with or without modification, are permitted provided
4    * that the following conditions are met:
5    *
6    * 1. Redistributions of source code must retain copyright
7    *    statements and notices.  Redistributions must also contain a
8    *    copy of this document.
9    *
10   * 2. Redistributions in binary form must reproduce the
11   *    above copyright notice, this list of conditions and the
12   *    following disclaimer in the documentation and/or other
13   *    materials provided with the distribution.
14   *
15   * 3. The name "Exolab" must not be used to endorse or promote
16   *    products derived from this Software without prior written
17   *    permission of Intalio.  For written permission,
18   *    please contact info@exolab.org.
19   *
20   * 4. Products derived from this Software may not be called "Exolab"
21   *    nor may "Exolab" appear in their names without prior written
22   *    permission of Intalio. Exolab is a registered
23   *    trademark of Intalio.
24   *
25   * 5. Due credit should be given to the Exolab Project
26   *    (http://www.exolab.org/).
27   *
28   * THIS SOFTWARE IS PROVIDED BY INTALIO AND CONTRIBUTORS
29   * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
30   * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
31   * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
32   * INTALIO OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
33   * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
34   * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
35   * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36   * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
37   * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
38   * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
39   * OF THE POSSIBILITY OF SUCH DAMAGE.
40   *
41   * Copyright 1999-2004 (C) Intalio Inc. All Rights Reserved.
42   *
43   * $Id: UUIDGenerator.java,v 1.1 2004/11/26 01:50:35 tanderson Exp $
44   */
45  
46  package org.exolab.jms.common.uuid;
47  
48  import java.security.SecureRandom  ;
49  import java.util.HashSet  ;
50  import java.util.Random  ;
51  
52  
53  /**
54   * Universally Unique Identifier (UUID) generator.
55   * <p>
56   * A UUID is an identifier that is unique across both space and time,
57   * with respect to the space of all UUIDs. A UUID can be used for
58   * objects with an extremely short lifetime, and to reliably identifying
59   * very persistent objects across a network. UUIDs are 128 bit values
60   * and encoded as 36 character identifiers.
61   * <p>
62   * This generator produces time-based UUIDs based on the varient
63   * specified in a February 4, 1998 IETF draft.
64   * <p>
65   * Unprefixed identifiers are generated by calling {@link #create()
66   * create}. A method is also provided to create prefixed identifiers.
67   * Prefixed identifiers are useful for logging and associating
68   * identifiers to application objects.
69   * <p>
70   * To assure that identifiers can be presisted, identifiers must be
71   * kept within the limit of {@link #MAXIMUM_LENGTH} characters.
72   * This includes both prefixed identifiers and identifiers created
73   * by the application. The {@link #trim trim} method can be used to
74   * trim an identifier to the maximum allowed length. If an* identifier
75   * was generated with no prefix, or with the maximum supported prefix
76   * legnth, the identifier is guaranteed to be short enough and this
77   * method is not required.
78   * <p>
79   * Convenience methods are also provided for converting an identifier
80   * to and from an array of bytes. The conversion methods assume that
81   * the identifier is a prefixed or unprefixed encoding of the byte
82   * array as pairs of hexadecimal digits.
83   * <p>
84   * The UUID specification prescribes the following format for
85   * representing UUIDs. Four octets encode the low field of the time
86   * stamp, two octects encode the middle field of the timestamp,
87   * and two octets encode the high field of the timestamp with the
88   * version number. Two octets encode the clock sequence number and
89   * six octets encode the unique node identifier.
90   * <p>
91   * The timestamp is a 60 bit value holding UTC time as a count of 100
92   * nanosecond intervals since October 15, 1582. UUIDs generated in
93   * this manner are guaranteed not to roll over until 3400 AD.
94   * <p>
95   * The clock sequence is used to help avoid duplicates that could arise
96   * when the clock is set backward in time or if the node ID changes.
97   * Although the system clock is guaranteed to be monotonic, the system
98   * clock is not guaranteed to be monotonic across system failures.
99   * The UUID cannot be sure that no UUIDs were generated with timestamps
100  * larger than the current timestamp.
101  * <p>
102  * If the clock sequence can be determined at initialization, it is
103  * incremented by one, otherwise it is set to a random number.
104  * The clock sequence MUST be originally (i.e. once in the lifetime
105  * of a system) initialized to a random number to minimize the
106  * correlation across systems. The initial value must not be correlated
107  * to the node identifier.
108  * <p>
109  * The node identifier must be unique for each UUID generator.
110  * This is accomplished using the IEEE 802 network card address.
111  * For systems with multiple IEEE 802 addresses, any available address
112  * can be used. For systems with no IEEE address, a 47 bit random value
113  * is used and the multicast bit is set so it will never conflict with
114  * addresses obtained from network cards.
115  * <p>
116  * The UUID state consists of the node identifier and clock sequence.
117  * The state need only be read once when the generator is initialized,
118  * and the clock sequence must be incremented and stored back. If the
119  * UUID state cannot be read and updated, a random number is used.
120  * <p>
121  * The UUID generator is thread-safe.
122  * <p>
123  * This class originally came from Tyrex: http://tyrex.sourceforge.net
124  *
125  * @author <a HREF="mailto:arkin@intalio.com">Assaf Arkin</a>
126  * @version $Revision: 1.1 $ $Date: 2004/11/26 01:50:35 $
127  */
128 public final class UUIDGenerator {
129 
130     /**
131      /**
132      * The identifier resolution in bytes. Identifiers are 16-byte
133      * long, or 128 bits. Without a prefix, an identifier can be
134      * represented as 36 hexadecimal digits and hyphens.
135      * (4 hyphens are used in the UUID format)
136      */
137     public static final int RESOLUTION_BYTES = 16;
138 
139 
140     /**
141      * The maximum length of an identifier in textual form.
142      * Prefixed identifiers and application identifiers must be
143      * less or equal to the maximum length to allow persistence.
144      * This maximum length is 64 characters.
145      */
146     public static final int MAXIMUM_LENGTH = 64;
147 
148 
149     /**
150      * The maximum length of an identifier prefix. Identifiers
151      * created using {@link #create(String) create(String)} with
152      * a prefix that is no longer than the maximum prefix size
153      * are guaranteed to be within the maximum length allowed
154      * and need not be trimmed.
155      */
156     public static final int MAXIMUM_PREFIX = 28;
157 
158 
159     /**
160      * The variant value determines the layout of the UUID. This
161      * variant is specified in the IETF February 4, 1998 draft.
162      * Used for character octets.
163      */
164     private static final int UUID_VARIANT_OCTET = 0x08;
165 
166 
167     /**
168      * The variant value determines the layout of the UUID. This
169      * variant is specified in the IETF February 4, 1998 draft.
170      * Used for byte array.
171      */
172     private static final int UUID_VARIANT_BYTE = 0x80;
173 
174 
175     /**
176      * The version identifier for a time-based UUID. This version
177      * is specified in the IETF February 4, 1998 draft. Used for
178      * character octets.
179      */
180     private static final int UUID_VERSION_CLOCK_OCTET = 0x01;
181 
182 
183     /**
184      * The version identifier for a time-based UUID. This version
185      * is specified in the IETF February 4, 1998 draft. Used for
186      * byte array.
187      */
188     private static final int UUID_VERSION_CLOCK_BYTE = 0x10;
189 
190 
191     /**
192      * The version identifier for a name-based UUID. This version
193      * is specified in the IETF February 4, 1998 draft. Used for
194      * character octets.
195      */
196     private static final int UUID_VERSION_NAME_OCTET = 0x03;
197 
198 
199     /**
200      * The version identifier for a name-based UUID. This version
201      * is specified in the IETF February 4, 1998 draft. Used for
202      * byte array.
203      */
204     private static final int UUID_VERSION_NAME_BYTE = 0x30;
205 
206 
207     /**
208      * The version identifier for a random-based UUID. This version
209      * is specified in the IETF February 4, 1998 draft. Used for
210      * character octets.
211      */
212     private static final int UUID_VERSION_RANDOM_CLOCK = 0x04;
213 
214 
215     /**
216      * The version identifier for a random-based UUID. This version
217      * is specified in the IETF February 4, 1998 draft. Used for
218      * byte array.
219      */
220     private static final int UUID_VERSION_RANDOM_BYTE = 0x40;
221 
222 
223     /**
224      * The difference between Java clock and UUID clock. Java clock
225      * is base time is January 1, 1970. UUID clock base time is
226      * October 15, 1582.
227      */
228     private static final long JAVA_UUID_CLOCK_DIFF = 0x0b1d069b5400L;
229 
230 
231     /**
232      * Efficient mapping from 4 bit value to lower case hexadecimal digit.
233      */
234     private final static char[] HEX_DIGITS = new char[]{
235         '0', '1', '2', '3', '4', '5', '6', '7',
236         '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
237 
238 
239     /**
240      * The number of UUIDs that can be generated per clock tick.
241      * UUID assumes a clock tick every 100 nanoseconds. The actual
242      * clock ticks are measured in milliseconds and based on the
243      * sync-every property of the clock. The product of these two
244      * values is used to set this variable.
245      */
246     private static int _uuidsPerTick;
247 
248 
249     /**
250      * The number of UUIDs generated in this clock tick. This counter
251      * is reset each time the clock is advanced a tick. When it reaches
252      * the maximum number of UUIDs allowed per tick, we block until the
253      * clock advances.
254      */
255     private static int _uuidsThisTick;
256 
257 
258     /**
259      * The last clock. Whenever the clock changes, we record the last clock
260      * to identify when we get a new clock, or when we should increments
261      * the UUIDs per tick counter.
262      */
263     private static long _lastClock;
264 
265 
266     /**
267      * The clock sequence. This is randomly initialised, and is made of
268      * four hexadecimal digits.
269      */
270     private static char[] _clockSeqOctet;
271 
272 
273     /**
274      * The clock sequence. The clock sequence is obtained from the UUID
275      * properties and incremented by one each time we boot, or is
276      * generated randomaly if missing in the UUID properties. The clock
277      * sequence is made of two bytes.
278      */
279     private static byte[] _clockSeqByte;
280 
281 
282     /**
283      * The node identifier. The node identifier is obtained from the
284      * UUID properties, or is generated if missing in the UUID properties.
285      * The node identifier is made of twelve hexadecimal digits.
286      */
287     private static char[] _nodeIdentifierOctet;
288 
289 
290     /**
291      * The node identifier. The node identifier is obtained from the
292      * UUID properties, or is generated if missing in the UUID properties.
293      * The node identifier is made of six bytes.
294      */
295     private static byte[] _nodeIdentifierByte;
296 
297 
298     /**
299      * Creates and returns a new identifier.
300      *
301      * @return An identifier
302      */
303     public static String   create() {
304         return String.valueOf(createTimeUUIDChars());
305     }
306 
307 
308     /**
309      * Creates and returns a new prefixed identifier.
310      * <p>
311      * This method is equivalent to <code>prefix + create()</code>.
312      *
313      * @param prefix The prefix to use
314      * @return A prefixed identifier
315      */
316     public static String   create(String   prefix) {
317         StringBuffer   buffer;
318 
319         if (prefix == null) {
320             throw new IllegalArgumentException  ("Argument 'prefix' is null");
321         }
322         buffer = new StringBuffer  (MAXIMUM_LENGTH - MAXIMUM_PREFIX + prefix.length());
323         buffer.append(prefix);
324         buffer.append(createTimeUUIDChars());
325         return buffer.toString();
326     }
327 
328 
329     /**
330      * Creates and returns a new identifier.
331      *
332      * @return An identifier
333      */
334     public static byte[] createBinary() {
335         return createTimeUUIDBytes();
336     }
337 
338 
339     /**
340      * Converts a prefixed identifier into a byte array. An exception
341      * is thrown if the identifier does not match the excepted textual
342      * encoding.
343      * <p>
344      * The format for the identifier is <code>prefix{nn|-}*</code>:
345      * a prefix followed by a sequence of bytes, optionally separated
346      * by hyphens. Each byte is encoded as a pair of hexadecimal digits.
347      *
348      * @param prefix The identifier prefix
349      * @param identifier The prefixed identifier
350      * @return The identifier as an array of bytes
351      * @throws InvalidIDException The identifier does not begin with
352      * the prefix, or does not consist of a sequence of hexadecimal
353      * digit pairs, optionally separated by hyphens
354      */
355     public static byte[] toBytes(String   prefix, String   identifier)
356         throws InvalidIDException {
357 
358         int index;
359         char digit;
360         byte nibble;
361         byte[] bytes;
362         byte[] newBytes;
363 
364         if (identifier == null) {
365             throw new IllegalArgumentException  ("Argument identifier is null");
366         }
367         if (prefix == null) {
368             throw new IllegalArgumentException  ("Argument prefix is null");
369         }
370         if (!identifier.startsWith(prefix)) {
371             throw new InvalidIDException(
372                 "Invalid identifier: expected prefix " + prefix
373                 + "in identifier " + identifier);
374         }
375 
376         index = 0;
377         bytes = new byte[(identifier.length() - prefix.length()) / 2];
378         for (int i = prefix.length(); i < identifier.length(); ++i) {
379             digit = identifier.charAt(i);
380             if (digit == '-') {
381                 continue;
382             }
383             if (digit >= '0' && digit <= '9') {
384                 nibble = (byte) ((digit - '0') << 4);
385             } else if (digit >= 'A' && digit <= 'F') {
386                 nibble = (byte) ((digit - ('A' - 0x0A)) << 4);
387             } else if (digit >= 'a' && digit <= 'f') {
388                 nibble = (byte) ((digit - ('a' - 0x0A)) << 4);
389             } else {
390                 throw new InvalidIDException(
391                     "character " + String.valueOf(digit)
392                     + " encountered, expected hexadecimal digit in identifier "
393                     + identifier);
394             }
395             ++i;
396             if (i == identifier.length()) {
397                 throw new InvalidIDException(
398                     "Invalid identifier: odd number of hexadecimal digits in "
399                     + "identifier " + identifier);
400             }
401             digit = identifier.charAt(i);
402             if (digit >= '0' && digit <= '9') {
403                 nibble = (byte) (nibble | (digit - '0'));
404             } else if (digit >= 'A' && digit <= 'F') {
405                 nibble = (byte) (nibble | (digit - ('A' - 0x0A)));
406             } else if (digit >= 'a' && digit <= 'f') {
407                 nibble = (byte) (nibble | (digit - ('a' - 0x0A)));
408             } else {
409                 throw new InvalidIDException(
410                     "character " + String.valueOf(digit)
411                     + " encountered, expected hexadecimal digit in identifier "
412                     + identifier);
413             }
414             bytes[index] = nibble;
415             ++index;
416         }
417         if (index == bytes.length) {
418             return bytes;
419         }
420         newBytes = new byte[index];
421         while (index-- > 0) {
422             newBytes[index] = bytes[index];
423         }
424         return newBytes;
425     }
426 
427 
428     /**
429      * Converts an identifier into a byte array. An exception is
430      * thrown if the identifier does not match the excepted textual
431      * encoding.
432      * <p>
433      * The format for the identifier is <code>{nn|-}*</code>:
434      * a sequence of bytes, optionally separated by hyphens.
435      * Each byte is encoded as a pair of hexadecimal digits.
436      *
437      * @param identifier The identifier
438      * @return The identifier as an array of bytes
439      * @throws InvalidIDException The identifier does not consist
440      * of a sequence of hexadecimal digit pairs, optionally separated
441      * by hyphens
442      */
443     public static byte[] toBytes(String   identifier) throws InvalidIDException {
444         int index;
445         char digit;
446         byte nibble;
447         byte[] bytes;
448         byte[] newBytes;
449 
450         if (identifier == null) {
451             throw new IllegalArgumentException  ("Argument identifier is null");
452         }
453         index = 0;
454         bytes = new byte[identifier.length() / 2];
455         for (int i = 0; i < identifier.length(); ++i) {
456             digit = identifier.charAt(i);
457             if (digit == '-')
458                 continue;
459             if (digit >= '0' && digit <= '9')
460                 nibble = (byte) ((digit - '0') << 4);
461             else if (digit >= 'A' && digit <= 'F')
462                 nibble = (byte) ((digit - ('A' - 0x0A)) << 4);
463             else if (digit >= 'a' && digit <= 'f')
464                 nibble = (byte) ((digit - ('a' - 0x0A)) << 4);
465             else {
466                 throw new InvalidIDException(
467                     "character " + String.valueOf(digit)
468                     + " encountered, expected hexadecimal digit in identifier "
469                     + identifier);
470             }
471             ++i;
472             if (i == identifier.length()) {
473                 throw new InvalidIDException(
474                     "Invalid identifier: odd number of hexadecimal digits in "
475                     + "identifier " + identifier);
476             }
477             digit = identifier.charAt(i);
478             if (digit >= '0' && digit <= '9')
479                 nibble = (byte) (nibble | (digit - '0'));
480             else if (digit >= 'A' && digit <= 'F')
481                 nibble = (byte) (nibble | (digit - ('A' - 0x0A)));
482             else if (digit >= 'a' && digit <= 'f')
483                 nibble = (byte) (nibble | (digit - ('a' - 0x0A)));
484             else {
485                 throw new InvalidIDException(
486                     "character " + String.valueOf(digit)
487                     + " encountered, expected hexadecimal digit in identifier "
488                     + identifier);
489             }
490             bytes[index] = nibble;
491             ++index;
492         }
493         if (index == bytes.length)
494             return bytes;
495         newBytes = new byte[index];
496         while (index-- > 0)
497             newBytes[index] = bytes[index];
498         return newBytes;
499     }
500 
501 
502     /**
503      * Converts a byte array into a prefixed identifier.
504      * <p>
505      * The format for the identifier is <code>prefix{nn|-}*</code>:
506      * a prefix followed by a sequence of bytes, optionally separated
507      * by hyphens. Each byte is encoded as a pair of hexadecimal digits.
508      *
509      * @param prefix The identifier prefix
510      * @param byte An array of bytes
511      * @return A string representation of the identifier
512      */
513     public static String   fromBytes(String   prefix, byte[] bytes) {
514         StringBuffer   buffer;
515 
516         if (prefix == null)
517             throw new IllegalArgumentException  ("Argument prefix is null");
518         if (bytes == null || bytes.length == 0)
519             throw new IllegalArgumentException  ("Argument bytes is null or an empty array");
520         buffer = new StringBuffer  (prefix);
521         for (int i = 0; i < bytes.length; ++i) {
522             buffer.append(HEX_DIGITS[(bytes[i] & 0xF0) >> 4]);
523             buffer.append(HEX_DIGITS[(bytes[i] & 0x0F)]);
524         }
525         return buffer.toString();
526     }
527 
528 
529     /**
530      * Converts a byte array into an identifier.
531      * <p>
532      * The format for the identifier is <code>{nn|-}*</code>: a sequence
533      * of bytes, optionally separated by hyphens. Each byte is encoded as
534      * a pair of hexadecimal digits.
535      *
536      * @param bytes An array of bytes
537      * @return A string representation of the identifier
538      */
539     public static String   fromBytes(byte[] bytes) {
540         StringBuffer   buffer;
541 
542         if (bytes == null || bytes.length == 0)
543             throw new IllegalArgumentException  ("Argument bytes is null or an empty array");
544         buffer = new StringBuffer  ();
545         for (int i = 0; i < bytes.length; ++i) {
546             buffer.append(HEX_DIGITS[(bytes[i] & 0xF0) >> 4]);
547             buffer.append(HEX_DIGITS[(bytes[i] & 0x0F)]);
548         }
549         return buffer.toString();
550     }
551 
552 
553     /**
554      * Truncates an identifier so that it does not extend beyond
555      * {@link #MAXIMUM_LENGTH} characters in length.
556      *
557      * @param identifier An identifier
558      * @return An identifier trimmed to {@link #MAXIMUM_LENGTH} characters
559      */
560     public static String   trim(String   identifier) {
561         if (identifier == null)
562             throw new IllegalArgumentException  ("Argument identifier is null");
563         if (identifier.length() > MAXIMUM_LENGTH)
564             return identifier.substring(0, MAXIMUM_LENGTH);
565         return identifier;
566     }
567 
568 
569     /**
570      * Returns a time-based UUID as a character array. The UUID
571      * identifier is always 36 characters long.
572      *
573      * @return A time-based UUID
574      */
575     public static char[] createTimeUUIDChars() {
576         long clock;
577         char[] chars;
578         long nextClock;
579 
580         // Acquire lock to assure synchornized generation
581         synchronized (UUID.class) {
582             clock = Clock.clock();
583             while (true) {
584                 if (clock > _lastClock) {
585                     // Since we are using the clock interval for the UUID space,
586                     // we must make sure the next clock provides sufficient
587                     // room so UUIDs do not roll over.
588                     nextClock = _lastClock + (_uuidsThisTick / 100);
589                     if (clock <= nextClock)
590                         clock = Clock.synchronize();
591                     if (clock > nextClock) {
592                         // Clock reading changed since last UUID generated,
593                         // reset count of UUIDs generated with this clock.
594                         _uuidsThisTick = 0;
595                         _lastClock = clock;
596                         // Adjust UUIDs per tick in case the clock sleep ticks
597                         // have changed.
598                         _uuidsPerTick = Clock.getUnsynchTicks() * 100;
599                         break;
600                     }
601                 }
602 
603                 if (_uuidsThisTick + 1 < _uuidsPerTick) {
604                     // Clock did not advance, but able to create more UUIDs
605                     // for this clock, proceed.
606                     ++_uuidsThisTick;
607                     break;
608                 }
609 
610                 // Running out of UUIDs for the current clock tick, must
611                 // wait until clock advances. Possible that clock did not
612                 // advance in background, so try to synchronize it first.
613                 clock = Clock.synchronize();
614                 if (clock <= _lastClock) {
615                     // if (Configuration.verbose)
616                     //Logger.tyrex.debug(Messages.message("tyrex.uuid.fastHolding"));
617                     while (clock <= _lastClock) {
618                         // UUIDs generated too fast, suspend for a while.
619                         try {
620                             Thread.currentThread().sleep(Clock.getUnsynchTicks());
621                         } catch (InterruptedException   except) {
622                         }
623                         clock = Clock.synchronize();
624                     }
625                 }
626             }
627 
628             // Modify Java clock (milliseconds) to UUID clock (100 nanoseconds).
629             // Add the count of uuids to low order bits of the clock reading,
630             // assuring we get a unique clock.
631             clock = (_lastClock + JAVA_UUID_CLOCK_DIFF) * 100 + _uuidsThisTick;
632 
633             chars = new char[36];
634             // Add the low field of the clock (4 octets)
635             chars[0] = HEX_DIGITS[(int) ((clock >> 28) & 0x0F)];
636             chars[1] = HEX_DIGITS[(int) ((clock >> 24) & 0x0F)];
637             chars[2] = HEX_DIGITS[(int) ((clock >> 20) & 0x0F)];
638             chars[3] = HEX_DIGITS[(int) ((clock >> 16) & 0x0F)];
639             chars[4] = HEX_DIGITS[(int) ((clock >> 12) & 0x0F)];
640             chars[5] = HEX_DIGITS[(int) ((clock >> 8) & 0x0F)];
641             chars[6] = HEX_DIGITS[(int) ((clock >> 4) & 0x0F)];
642             chars[7] = HEX_DIGITS[(int) (clock & 0x0F)];
643             chars[8] = '-';
644             // Add the medium field of the clock (2 octets)
645             chars[9] = HEX_DIGITS[(int) ((clock >> 44) & 0x0F)];
646             chars[10] = HEX_DIGITS[(int) ((clock >> 40) & 0x0F)];
647             chars[11] = HEX_DIGITS[(int) ((clock >> 36) & 0x0F)];
648             chars[12] = HEX_DIGITS[(int) ((clock >> 32) & 0x0F)];
649             chars[13] = '-';
650             // Add the high field of the clock multiplexed with version number (2 octets)
651             chars[14] = HEX_DIGITS[(int) (((clock >> 60) & 0x0F) | UUID_VERSION_CLOCK_OCTET)];
652             chars[15] = HEX_DIGITS[(int) ((clock >> 56) & 0x0F)];
653             chars[16] = HEX_DIGITS[(int) ((clock >> 52) & 0x0F)];
654             chars[17] = HEX_DIGITS[(int) ((clock >> 48) & 0x0F)];
655             chars[18] = '-';
656             // Add the clock sequence and version identifier (2 octets)
657             chars[19] = _clockSeqOctet[0];
658             chars[20] = _clockSeqOctet[1];
659             chars[21] = _clockSeqOctet[2];
660             chars[22] = _clockSeqOctet[3];
661             chars[23] = '-';
662             // Add the node identifier (6 octets)
663             chars[24] = _nodeIdentifierOctet[0];
664             chars[25] = _nodeIdentifierOctet[1];
665             chars[26] = _nodeIdentifierOctet[2];
666             chars[27] = _nodeIdentifierOctet[3];
667             chars[28] = _nodeIdentifierOctet[4];
668             chars[29] = _nodeIdentifierOctet[5];
669             chars[30] = _nodeIdentifierOctet[6];
670             chars[31] = _nodeIdentifierOctet[7];
671             chars[32] = _nodeIdentifierOctet[8];
672             chars[33] = _nodeIdentifierOctet[9];
673             chars[34] = _nodeIdentifierOctet[10];
674             chars[35] = _nodeIdentifierOctet[11];
675         }
676         return chars;
677     }
678 
679 
680     /**
681      * Returns a time-based UUID as a character array. The UUID
682      * identifier is always 16 bytes long.
683      *
684      * @return A time-based UUID
685      */
686     public static byte[] createTimeUUIDBytes() {
687         long clock;
688         byte[] bytes;
689         long nextClock;
690 
691         // Acquire lock to assure synchronized generation
692         synchronized (UUIDGenerator.class) {
693             clock = Clock.clock();
694             while (true) {
695                 if (clock > _lastClock) {
696                     // Since we are using the clock interval for the UUID
697                     // space, we must make sure the next clock provides
698                     // sufficient room so UUIDs do not roll over.
699                     nextClock = _lastClock + (_uuidsThisTick / 100);
700                     if (clock <= nextClock) {
701                         clock = Clock.synchronize();
702                     }
703                     if (clock > nextClock) {
704                         // Clock reading changed since last UUID generated,
705                         // reset count of UUIDs generated with this clock.
706                         _uuidsThisTick = 0;
707                         _lastClock = clock;
708                         // Adjust UUIDs per tick in case the clock sleep ticks
709                         // have changed.
710                         _uuidsPerTick = Clock.getUnsynchTicks() * 100;
711                         break;
712                     }
713                 }
714 
715                 if (_uuidsThisTick + 1 < _uuidsPerTick) {
716                     // Clock did not advance, but able to create more UUIDs
717                     // for this clock, proceed.
718                     ++_uuidsThisTick;
719                     break;
720                 }
721 
722                 // Running out of UUIDs for the current clock tick, must
723                 // wait until clock advances. Possible that clock did not
724                 // advance in background, so try to synchronize it first.
725                 clock = Clock.synchronize();
726                 if (clock <= _lastClock) {
727                     // if (Configuration.verbose)
728                     // Logger.tyrex.debug(Messages.message("tyrex.uuid.fastHolding"));
729                     while (clock <= _lastClock) {
730                         // UUIDs generated too fast, suspend for a while.
731                         try {
732                             Thread.currentThread().sleep(Clock.getUnsynchTicks());
733                         } catch (InterruptedException   ignore) {
734                         }
735                         clock = Clock.synchronize();
736                     }
737                 }
738             }
739 
740             // Modify Java clock (milliseconds) to UUID clock (100 nanoseconds).
741             // Add the count of uuids to low order bits of the clock reading,
742             // assuring we get a unique clock.
743             clock = (_lastClock + JAVA_UUID_CLOCK_DIFF) * 100 + _uuidsThisTick;
744 
745             bytes = new byte[16];
746             // Add the low field of the clock (4 octets)
747             bytes[0] = (byte) ((clock >> 24) & 0xFF);
748             bytes[1] = (byte) ((clock >> 16) & 0xFF);
749             bytes[2] = (byte) ((clock >> 8) & 0xFF);
750             bytes[3] = (byte) (clock & 0xFF);
751             // Add the medium field of the clock (2 octets)
752             bytes[4] = (byte) ((clock >> 40) & 0xFF);
753             bytes[5] = (byte) ((clock >> 32) & 0xFF);
754             // Add the high field of the clock multiplexed with version
755             // number (2 octets)
756             bytes[6] = (byte) (((clock >> 60) & 0xFF)
757                 | UUID_VERSION_CLOCK_BYTE);
758             bytes[7] = (byte) ((clock >> 48) & 0xFF);
759             // Add the clock sequence and version identifier (2 octets)
760             bytes[8] = _clockSeqByte[0];
761             bytes[9] = _clockSeqByte[1];
762             // Add the node identifier (6 octets)
763             bytes[10] = _nodeIdentifierByte[0];
764             bytes[11] = _nodeIdentifierByte[1];
765             bytes[12] = _nodeIdentifierByte[2];
766             bytes[13] = _nodeIdentifierByte[3];
767             bytes[14] = _nodeIdentifierByte[4];
768             bytes[15] = _nodeIdentifierByte[5];
769         }
770         return bytes;
771     }
772 
773 
774     /**
775      * Returns true if the UUID was created on this machine.
776      * Determines the source of the UUID based on the node
777      * identifier.
778      *
779      * @param uuid The UUID as a byte array
780      * @return True if created on this machine
781      */
782     public static boolean isLocal(byte[] uuid) {
783         if (uuid == null)
784             throw new IllegalArgumentException  ("Argument uuid is null");
785         if (uuid.length != 16)
786             return false;
787         return (uuid[10] == _nodeIdentifierByte[0] &&
788             uuid[11] == _nodeIdentifierByte[1] &&
789             uuid[12] == _nodeIdentifierByte[2] &&
790             uuid[13] == _nodeIdentifierByte[3] &&
791             uuid[14] == _nodeIdentifierByte[4] &&
792             uuid[15] == _nodeIdentifierByte[5]);
793     }
794 
795     /**
796      * Initialise the generator
797      * <p>
798      * This method generates the node identifier and clock sequence, and
799      * sets {@link #_uuidsPerTick} to the number of UUIDs allowed per clock
800      * tick.
801      */
802     private static void initialize() {
803         // Random random = new SecureRandom();
804         Random   random = new Random  ();
805         String   nodeIdString;
806         long nodeIdLong;
807         String   seqString;
808         int seqInt;
809 
810         // Generate the node identifier, as we can't determine the IEEE 802
811         // address of the local host.
812         // As a result, it must have bit 48 set.
813         nodeIdLong = random.nextLong();
814         nodeIdLong = nodeIdLong | (1 << 47);
815 
816         // Generate the clock sequence
817         seqInt = random.nextInt(1 << 12);
818         seqInt = seqInt & 0x1FFF;
819 
820         // Convert clock sequence to 4 hexadecimal digits
821         _clockSeqOctet = new char[4];
822         _clockSeqOctet[0] = HEX_DIGITS[(int) ((seqInt >> 12) & 0x0F)];
823         _clockSeqOctet[1] = HEX_DIGITS[(int) ((seqInt >> 8) & 0x0F)];
824         _clockSeqOctet[2] = HEX_DIGITS[(int) ((seqInt >> 4) & 0x0F)];
825         _clockSeqOctet[3] = HEX_DIGITS[(int) (seqInt & 0x0F)];
826 
827         _clockSeqByte = new byte[2];
828         _clockSeqByte[0] = (byte) ((seqInt >> 8) & 0xFF);
829         _clockSeqByte[1] = (byte) (seqInt & 0xFF);
830 
831         // Need to mask UUID variant on clock sequence
832         _clockSeqOctet[0] = HEX_DIGITS[(int) ((seqInt >> 12) & 0x0F)
833             | UUID_VARIANT_OCTET];
834         _clockSeqByte[0] = (byte) (((seqInt >> 8) & 0xFF)
835             | UUID_VARIANT_BYTE);
836 
837         // Convert node identifier to 12 hexadecimal digits
838         _nodeIdentifierOctet = new char[12];
839         for (int i = 0; i < 12; ++i) {
840             _nodeIdentifierOctet[i] =
841                 HEX_DIGITS[(int) ((nodeIdLong >> ((11 - i) * 4)) & 0x0F)];
842         }
843         _nodeIdentifierByte = new byte[6];
844         for (int i = 0; i < 6; ++i) {
845             _nodeIdentifierByte[i] =
846                 (byte) ((nodeIdLong >> ((5 - i) * 8)) & 0xFF);
847         }
848 
849         // The number of UUIDs allowed per tick depends on the number of
850         // ticks between each advance of the clock, adjusted for 100
851         // nanosecond precision.
852         _uuidsPerTick = Clock.getUnsynchTicks() * 100;
853     }
854 
855     static {
856         initialize();
857         // This makes sure we miss at least one clock tick, just to be safe.
858         _uuidsThisTick = _uuidsPerTick;
859         _lastClock = Clock.clock();
860     }
861 
862 
863     public static void main(String  [] args) {
864         long clock;
865         HashSet   hash;
866         String   id;
867         int count = 1000000;
868 
869         for (int i = 0; i < 10; ++i) {
870             System.out.println(create());
871         }
872         clock = System.currentTimeMillis();
873         hash = new HashSet  (count / 100, 100);
874         for (int i = 0; i < count; ++i) {
875             if ((i % 10000) == 0)
876                 System.out.println("Checked " + i);
877             id = create();
878             if (hash.contains(id))
879                 System.out.println("Duplicate id " + id);
880             else
881                 hash.add(id);
882         }
883         clock = System.currentTimeMillis() - clock;
884         System.out.println("Generated " + count + " UUIDs in " + clock + "ms");
885     }
886 
887     /**
888      * An exception indicating the identifier is invalid and
889      * cannot be converted into an array of bytes.
890      */
891     public static class InvalidIDException extends Exception   {
892 
893         public InvalidIDException(String   message) {
894             super(message);
895         }
896     }
897 
898 }
899
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags