| /* |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| */ |
| |
| package org.apache.axiom.util; |
| |
| import java.net.URI; |
| import java.net.URISyntaxException; |
| import java.security.SecureRandom; |
| import java.util.Random; |
| import java.util.UUID; |
| |
| /** |
| * Contains utility methods to generate unique IDs of various kinds. |
| * <p> |
| * Depending on the requested type of ID, this class will either use |
| * {@link UUID#randomUUID()} (or an equivalent algorithm) |
| * or its own unique ID generator. This implementation |
| * generates unique IDs based on the assumption that the following triplet is |
| * unique: |
| * <ol> |
| * <li>The thread ID. |
| * <li>The timestamp in milliseconds when the first UID is requested by the |
| * thread. |
| * <li>A per thread sequence number that is incremented each time a UID is |
| * requested by the thread. |
| * </ol> |
| * <p> |
| * Considering that these three numbers are represented as <code>long</code> |
| * values, these assumptions are correct because: |
| * <ul> |
| * <li>The probability that two different threads with the same ID exist in the |
| * same millisecond interval is negligibly small. |
| * <li>One can expect that no thread will ever request more than 2^64 UIDs |
| * during its lifetime. |
| * </ul> |
| * <p> |
| * Before building an ID from this triplet, the implementation will XOR the |
| * three values with random values calculated once when the class is loaded. |
| * This transformation preserves the uniqueness of the calculated triplet and |
| * serves several purposes: |
| * <ul> |
| * <li>It reduces the probability that the same ID is produces by two different |
| * systems, i.e. it increases global uniqueness. |
| * <li>It adds entropy, i.e. it makes an individual ID appear as random. Indeed, |
| * without the XOR transformation, a hexadecimal representation of the triplet |
| * would in general contain several sequences of '0'. |
| * <li>It prevents the implementation from leaking information about the system |
| * state. |
| * </ul> |
| */ |
| public final class UIDGenerator { |
| private static final long startTimeXorOperand; |
| private static final long threadIdXorOperand; |
| private static final long seqXorOperand; |
| |
| private static final SecureRandom secureRandom = new SecureRandom(); |
| |
| /** |
| * Array of 16 caches that contain random bytes fetched from {@link #secureRandom} and that are |
| * used to compute UUIDs. These caches are used to reduce the number of calls to |
| * {@link SecureRandom#nextBytes(byte[])}. The cache used by a given thread is determined by the |
| * thread ID. Multiple caches are used to reduce contention between threads. |
| */ |
| private static final UUIDCache[] uuidCaches; |
| |
| static { |
| Random rand = new Random(); |
| threadIdXorOperand = rand.nextLong(); |
| startTimeXorOperand = rand.nextLong(); |
| seqXorOperand = rand.nextLong(); |
| uuidCaches = new UUIDCache[16]; |
| for (int i=0; i<16; i++) { |
| uuidCaches[i] = new UUIDCache(); |
| } |
| } |
| |
| /** |
| * Thread local that holds the triplet described in the Javadoc of this |
| * class. Note that we use a simple array here (instead of our own class) |
| * to avoid class loader leaks (see AXIOM-354). |
| */ |
| private static final ThreadLocal<long[]> triplet = new ThreadLocal<long[]>() { |
| @Override |
| protected long[] initialValue() { |
| long[] values = new long[3]; |
| values[0] = Thread.currentThread().getId() ^ threadIdXorOperand; |
| values[1] = System.currentTimeMillis() ^ startTimeXorOperand; |
| return values; |
| } |
| }; |
| |
| private UIDGenerator() {} |
| |
| private static void writeReverseLongHex(long value, StringBuilder buffer) { |
| for (int i=0; i<16; i++) { |
| int n = (int)(value >> (4*i)) & 0xF; |
| writeNibble(n, buffer); |
| } |
| } |
| |
| private static void writeNibble(int n, StringBuilder buffer) { |
| buffer.append((char)(n < 10 ? '0' + n : 'a' + n - 10)); |
| } |
| |
| /** |
| * Generate a unique ID as hex value and add it to the given buffer. Note |
| * that with respect to the triplet, the order of nibbles is reversed, i.e. |
| * the least significant nibble of the sequence is written first. This makes |
| * comparing two IDs for equality more efficient. |
| * |
| * @param buffer |
| */ |
| private static void generateHex(StringBuilder buffer) { |
| long[] values = triplet.get(); |
| writeReverseLongHex(values[2]++ ^ seqXorOperand, buffer); |
| writeReverseLongHex(values[1], buffer); |
| writeReverseLongHex(values[0], buffer); |
| } |
| |
| /** |
| * Generates a unique ID suitable for usage as a MIME content ID. |
| * <p> |
| * RFC2045 (MIME) specifies that the value of the {@code Content-ID} header |
| * must match the {@code msg-id} production, which is defined by RFC2822 as |
| * follows: |
| * <pre> |
| * msg-id = [CFWS] "<" id-left "@" id-right ">" [CFWS] |
| * id-left = dot-atom-text / no-fold-quote / obs-id-left |
| * id-right = dot-atom-text / no-fold-literal / obs-id-right |
| * dot-atom-text = 1*atext *("." 1*atext) |
| * atext = ALPHA / DIGIT / "!" / "#" / "$" / "%" / "&" |
| * / "'" / "*" / "+" / "-" / "/" / "=" / "?" |
| * / "^" / "_" / "`" / "{" / "|" / "}" / "~"</pre> |
| * In addition, RFC2392 specifies that when used in an URL with scheme |
| * "cid:", the content ID must be URL encoded. Since not all implementations |
| * handle this correctly, any characters considered "unsafe" in an URL (and |
| * requiring encoding) should be avoided in a content ID. |
| * <p> |
| * This method generates content IDs that satisfy these requirements. It |
| * guarantees a high level of uniqueness, but makes no provisions to |
| * guarantee randomness. The implementation is thread safe, but doesn't use |
| * synchronization. |
| * |
| * @return The generated content ID. Note that this value does not include |
| * the angle brackets of the {@code msg-id} production, but only |
| * represents the bare content ID. |
| */ |
| public static String generateContentId() { |
| StringBuilder buffer = new StringBuilder(); |
| generateHex(buffer); |
| buffer.append("@apache.org"); |
| return buffer.toString(); |
| } |
| |
| /** |
| * Generates a MIME boundary. |
| * <p> |
| * Valid MIME boundaries are defined by the following production in RFC2046: |
| * <pre> |
| * boundary := 0*69<bchars> bcharsnospace |
| * bchars := bcharsnospace / " " |
| * bcharsnospace := DIGIT / ALPHA / "'" / "(" / ")" / |
| * "+" / "_" / "," / "-" / "." / |
| * "/" / ":" / "=" / "?"</pre> |
| * <p> |
| * It should be noted that the boundary in general will also appear as a parameter in the |
| * content type of the MIME package. According to RFC2045 (which defines the |
| * {@code Content-Type} header), it will require quoting if it contains characters from |
| * the following production: |
| * <pre> |
| * tspecials := "(" / ")" / "<" / ">" / "@" / |
| * "," / ";" / ":" / "\" / <"> / |
| * "/" / "[" / "]" / "?" / "="</pre> |
| * <p> |
| * This method produces a boundary that doesn't contain any of these characters and |
| * therefore doesn't need to be quoted. To avoid accidental collisions, the returned value |
| * is unique and doesn't overlap with any other type of unique ID returned by methods in |
| * this class. The implementation is thread safe, but doesn't use synchronization. |
| * |
| * @return the generated MIME boundary |
| */ |
| public static String generateMimeBoundary() { |
| StringBuilder buffer = new StringBuilder("MIMEBoundary_"); |
| generateHex(buffer); |
| return buffer.toString(); |
| } |
| |
| /** |
| * Generate a general purpose unique ID. The returned value is the hexadecimal representation of |
| * a 192 bit value, i.e. it is 48 characters long. The implementation guarantees a high level of |
| * uniqueness, but makes no provisions to guarantee randomness. It is thread safe, but doesn't |
| * use synchronization. |
| * <p> |
| * The fact that this method doesn't guarantee randomness implies that the generated IDs are |
| * predictable and must not be used in contexts where this would cause a security vulnerability. |
| * In particular, this method should <b>not</b> be used to generate the following kind of IDs: |
| * <ul> |
| * <li>Session IDs. |
| * <li>Message IDs used in WS-Addressing. |
| * </ul> |
| * |
| * @return the generated unique ID |
| */ |
| public static String generateUID() { |
| StringBuilder buffer = new StringBuilder(48); |
| generateHex(buffer); |
| return buffer.toString(); |
| } |
| |
| /** |
| * Generate a URN with {@code uuid} NID (namespace identifier). These URNs have the following |
| * form: {@code urn:uuid:dae6fae1-93df-4824-bc70-884c9edb5973}. The UUID is generated using |
| * a cryptographically strong pseudo random number generator. |
| * |
| * @return the generated URN |
| */ |
| public static String generateURNString() { |
| StringBuilder urn = new StringBuilder(45); |
| urn.append("urn:uuid:"); |
| UUIDCache cache = uuidCaches[(int)Thread.currentThread().getId() & 0xF]; |
| synchronized (cache) { |
| boolean fill; |
| int position = cache.position; |
| byte[] randomBytes = cache.randomBytes; |
| if (randomBytes == null) { |
| cache.randomBytes = randomBytes = new byte[4096]; |
| fill = true; |
| } else if (position == 4096) { |
| position = 0; |
| fill = true; |
| } else { |
| fill = false; |
| } |
| if (fill) { |
| secureRandom.nextBytes(cache.randomBytes); |
| } |
| writeHex(randomBytes[position], urn); |
| writeHex(randomBytes[position+1], urn); |
| writeHex(randomBytes[position+2], urn); |
| writeHex(randomBytes[position+3], urn); |
| urn.append('-'); |
| writeHex(randomBytes[position+4], urn); |
| writeHex(randomBytes[position+5], urn); |
| urn.append('-'); |
| writeHex((byte)(randomBytes[position+6] & 0x0F | 0x40), urn); |
| writeHex(randomBytes[position+7], urn); |
| urn.append('-'); |
| writeHex((byte)(randomBytes[position+8] & 0x3F | 0x80), urn); |
| writeHex(randomBytes[position+9], urn); |
| urn.append('-'); |
| writeHex(randomBytes[position+10], urn); |
| writeHex(randomBytes[position+11], urn); |
| writeHex(randomBytes[position+12], urn); |
| writeHex(randomBytes[position+13], urn); |
| writeHex(randomBytes[position+14], urn); |
| writeHex(randomBytes[position+15], urn); |
| cache.position = position+16; |
| } |
| return urn.toString(); |
| } |
| |
| private static void writeHex(byte b, StringBuilder buffer) { |
| writeNibble(b >> 4 & 0xF, buffer); |
| writeNibble(b & 0xF, buffer); |
| } |
| |
| /** |
| * Generate a URN with {@code uuid} NID (namespace identifier). This method does the |
| * same as {@link #generateURNString()}, but returns a {@link URI} object. |
| * |
| * @return the generated URN |
| */ |
| public static URI generateURN() { |
| try { |
| return new URI(generateURNString()); |
| } catch (URISyntaxException ex) { |
| // If we ever get here, then if would mean that there is something badly broken... |
| throw new Error(ex); |
| } |
| } |
| } |
