From: Mathieu Baudier Date: Sat, 22 Jan 2022 13:03:42 +0000 (+0100) Subject: Working UUID factory X-Git-Tag: argeo-commons-2.3.5~75 X-Git-Url: https://git.argeo.org/?p=lgpl%2Fargeo-commons.git;a=commitdiff_plain;h=fe1ca8a0124a593a07055a06e639f2d97e0d63dd Working UUID factory --- diff --git a/org.argeo.api.acr/src/org/argeo/api/acr/uuid/AbstractUuidFactory.java b/org.argeo.api.acr/src/org/argeo/api/acr/uuid/AbstractUuidFactory.java deleted file mode 100644 index 7dbd85011..000000000 --- a/org.argeo.api.acr/src/org/argeo/api/acr/uuid/AbstractUuidFactory.java +++ /dev/null @@ -1,500 +0,0 @@ -package org.argeo.api.acr.uuid; - -import static java.lang.System.Logger.Level.DEBUG; - -import java.lang.System.Logger; -import java.net.InetAddress; -import java.net.NetworkInterface; -import java.net.SocketException; -import java.net.UnknownHostException; -import java.nio.charset.StandardCharsets; -import java.security.MessageDigest; -import java.security.NoSuchAlgorithmException; -import java.security.SecureRandom; -import java.time.Duration; -import java.time.LocalDateTime; -import java.time.ZoneOffset; -import java.util.BitSet; -import java.util.Objects; -import java.util.Random; -import java.util.UUID; -import java.util.concurrent.atomic.AtomicInteger; - -/** - * Static utilities to simplify and extend usage of {@link UUID}. Only the RFC - * 4122 variant (also known as Leach–Salz variant) is supported. - * - * @see https://datatracker.ietf.org/doc/html/rfc4122 - */ -public class AbstractUuidFactory { - /** Nil UUID (00000000-0000-0000-0000-000000000000). */ - public final static UUID NIL_UUID = UUID.fromString("00000000-0000-0000-0000-000000000000"); - - /** Start of the Gregorian time, used by time-based UUID. */ - public final static LocalDateTime GREGORIAN_START = LocalDateTime.of(1582, 10, 15, 0, 0, 0); - - /** - * Standard DNS namespace ID for type 3 or 5 UUID (as defined in Appendix C of - * RFC4122). - */ - public final static UUID NS_DNS = UUID.fromString("6ba7b810-9dad-11d1-80b4-00c04fd430c8"); - /** - * Standard URL namespace ID for type 3 or 5 UUID (as defined in Appendix C of - * RFC4122). - */ - public final static UUID NS_URL = UUID.fromString("6ba7b811-9dad-11d1-80b4-00c04fd430c8"); - /** - * Standard OID namespace ID (typically an LDAP type) for type 3 or 5 UUID (as - * defined in Appendix C of RFC4122). - */ - public final static UUID NS_OID = UUID.fromString("6ba7b812-9dad-11d1-80b4-00c04fd430c8"); - /** - * Standard X500 namespace ID (typically an LDAP DN) for type 3 or 5 UUID (as - * defined in Appendix C of RFC4122). - */ - public final static UUID NS_X500 = UUID.fromString("6ba7b814-9dad-11d1-80b4-00c04fd430c8"); - - /* - * INTERNAL STATIC UTILITIES - */ - private final static Logger logger = System.getLogger(AbstractUuidFactory.class.getName()); - - private final static long MOST_SIG_VERSION1 = (1l << 12); - private final static long LEAST_SIG_RFC4122_VARIANT = (1l << 63); - private final static int MAX_CLOCKSEQUENCE = 16384; - - private final static SecureRandom SECURE_RANDOM; - private final static Random UNSECURE_RANDOM; - private final static byte[] HARDWARE_ADDRESS; - - private final static AtomicInteger CLOCK_SEQUENCE; - - /** A start timestamp to which {@link System#nanoTime()}/100 can be added. */ - private final static long START_TIMESTAMP; - - static { - SECURE_RANDOM = new SecureRandom(); - UNSECURE_RANDOM = new Random(); - CLOCK_SEQUENCE = new AtomicInteger(SECURE_RANDOM.nextInt(MAX_CLOCKSEQUENCE)); - HARDWARE_ADDRESS = getHardwareAddress(); - - long nowVm = System.nanoTime() / 100; - Duration duration = Duration.between(GREGORIAN_START, LocalDateTime.now(ZoneOffset.UTC)); - START_TIMESTAMP = (duration.getSeconds() * 10000000 + duration.getNano() / 100) - nowVm; - } - - /* - * TIME-BASED (version 1) - */ - - private static byte[] getHardwareAddress() { - InetAddress localHost; - try { - localHost = InetAddress.getLocalHost(); - try { - NetworkInterface nic = NetworkInterface.getByInetAddress(localHost); - return nic.getHardwareAddress(); - } catch (SocketException e) { - return null; - } - } catch (UnknownHostException e) { - return null; - } - - } - - private synchronized static long nextClockSequence() { - int i = CLOCK_SEQUENCE.incrementAndGet(); - while (i < 0 || i >= MAX_CLOCKSEQUENCE) { - CLOCK_SEQUENCE.set(SECURE_RANDOM.nextInt(MAX_CLOCKSEQUENCE)); - i = CLOCK_SEQUENCE.incrementAndGet(); - } - return (long) i; - } - - public static UUID timeUUIDwithRandomNode() { - long timestamp = START_TIMESTAMP + System.nanoTime() / 100; - return timeUUID(timestamp, SECURE_RANDOM); - } - - public static UUID timeUUIDwithUnsecureRandomNode() { - long timestamp = START_TIMESTAMP + System.nanoTime() / 100; - return timeUUID(timestamp, UNSECURE_RANDOM); - } - - public static UUID timeUUID(long timestamp, Random random) { - byte[] node = new byte[6]; - random.nextBytes(node); - node[0] = (byte) (node[0] | 1); - long clockSequence = nextClockSequence(); - return timeUUID(timestamp, clockSequence, node); - } - - public static UUID timeUUID() { - long timestamp = START_TIMESTAMP + System.nanoTime() / 100; - return timeUUID(timestamp); - } - - public static UUID timeUUID(long timestamp) { - if (HARDWARE_ADDRESS == null) - return timeUUID(timestamp, SECURE_RANDOM); - long clockSequence = nextClockSequence(); - return timeUUID(timestamp, clockSequence, HARDWARE_ADDRESS); - } - - public static UUID timeUUID(long timestamp, NetworkInterface nic) { - byte[] node; - try { - node = nic.getHardwareAddress(); - } catch (SocketException e) { - throw new IllegalStateException("Cannot get hardware address", e); - } - long clockSequence = nextClockSequence(); - return timeUUID(timestamp, clockSequence, node); - } - - public static UUID timeUUID(LocalDateTime time, long clockSequence, byte[] node) { - Duration duration = Duration.between(GREGORIAN_START, time); - // Number of 100 ns intervals in one second: 1000000000 / 100 = 10000000 - long timestamp = duration.getSeconds() * 10000000 + duration.getNano() / 100; - return timeUUID(timestamp, clockSequence, node); - } - - public static UUID timeUUID(long timestamp, long clockSequence, byte[] node) { - Objects.requireNonNull(node, "Node array cannot be null"); - if (node.length < 6) - throw new IllegalArgumentException("Node array must be at least 6 bytes long"); - - long mostSig = MOST_SIG_VERSION1 // base for version 1 UUID - | ((timestamp & 0xFFFFFFFFL) << 32) // time_low - | (((timestamp >> 32) & 0xFFFFL) << 16) // time_mid - | ((timestamp >> 48) & 0x0FFFL);// time_hi_and_version - - long leastSig = LEAST_SIG_RFC4122_VARIANT // base for Leach–Salz UUID - | (((clockSequence & 0x3F00) >> 8) << 56) // clk_seq_hi_res - | ((clockSequence & 0xFF) << 48) // clk_seq_low - | (node[0] & 0xFFL) // - | ((node[1] & 0xFFL) << 8) // - | ((node[2] & 0xFFL) << 16) // - | ((node[3] & 0xFFL) << 24) // - | ((node[4] & 0xFFL) << 32) // - | ((node[5] & 0xFFL) << 40); // - UUID uuid = new UUID(mostSig, leastSig); - - // tests - assert uuid.node() == BitSet.valueOf(node).toLongArray()[0]; - assert uuid.timestamp() == timestamp; - assert uuid.clockSequence() == clockSequence - : "uuid.clockSequence()=" + uuid.clockSequence() + " clockSequence=" + clockSequence; - assert uuid.version() == 1; - assert uuid.variant() == 2; - return uuid; - } - - /* - * NAME BASED (version 3 and 5) - */ - - public final static String MD5 = "MD5"; - public final static String SHA1 = "SHA1"; - - public static UUID nameUUIDv5(UUID namespace, String name) { - Objects.requireNonNull(namespace, "Namespace cannot be null"); - Objects.requireNonNull(name, "Name cannot be null"); - return nameUUIDv5(namespace, name.getBytes(StandardCharsets.UTF_8)); - } - - public static UUID nameUUIDv5(UUID namespace, byte[] name) { - byte[] bytes = sha1(toBytes(namespace), name); - bytes[6] &= 0x0f; - bytes[6] |= 0x50;// v5 - bytes[8] &= 0x3f; - bytes[8] |= 0x80;// variant 1 - UUID result = fromBytes(bytes, 0); - return result; - } - - public static UUID nameUUIDv3(UUID namespace, String name) { - Objects.requireNonNull(namespace, "Namespace cannot be null"); - Objects.requireNonNull(name, "Name cannot be null"); - return nameUUIDv3(namespace, name.getBytes(StandardCharsets.UTF_8)); - } - - public static UUID nameUUIDv3(UUID namespace, byte[] name) { - byte[] arr = new byte[name.length + 16]; - copyBytes(namespace, arr, 0); - System.arraycopy(name, 0, arr, 16, name.length); - return UUID.nameUUIDFromBytes(arr); - } - - static byte[] sha1(byte[]... bytes) { - try { - MessageDigest digest = MessageDigest.getInstance(SHA1); - for (byte[] arr : bytes) - digest.update(arr); - byte[] checksum = digest.digest(); - return checksum; - } catch (NoSuchAlgorithmException e) { - throw new UnsupportedOperationException("SHA1 is not avalaible", e); - } - } - - /* - * RANDOM v4 - */ - public static UUID unsecureRandomUUID() { - byte[] arr = new byte[16]; - UNSECURE_RANDOM.nextBytes(arr); - arr[6] &= 0x0f; - arr[6] |= 0x40;// v4 - arr[8] &= 0x3f; - arr[8] |= 0x80;// variant 1 - return fromBytes(arr); - } - - /* - * UTILITIES - */ - /** - * Convert bytes to an UUID. Byte array must not be null and be exactly of - * length 16. - */ - public static UUID fromBytes(byte[] data) { - Objects.requireNonNull(data, "Byte array must not be null"); - if (data.length != 16) - throw new IllegalArgumentException("Byte array as length " + data.length); - return fromBytes(data, 0); - } - - /** - * Convert bytes to an UUID, starting to read the array at this offset. - */ - public static UUID fromBytes(byte[] data, int offset) { - Objects.requireNonNull(data, "Byte array cannot be null"); - long msb = 0; - long lsb = 0; - for (int i = offset; i < 8 + offset; i++) - msb = (msb << 8) | (data[i] & 0xff); - for (int i = 8 + offset; i < 16 + offset; i++) - lsb = (lsb << 8) | (data[i] & 0xff); - return new UUID(msb, lsb); - } - - public static byte[] toBytes(UUID uuid) { - Objects.requireNonNull(uuid, "UUID cannot be null"); - long msb = uuid.getMostSignificantBits(); - long lsb = uuid.getLeastSignificantBits(); - return toBytes(msb, lsb); - } - - public static void copyBytes(UUID uuid, byte[] arr, int offset) { - Objects.requireNonNull(uuid, "UUID cannot be null"); - long msb = uuid.getMostSignificantBits(); - long lsb = uuid.getLeastSignificantBits(); - copyBytes(msb, lsb, arr, offset); - } - - /** - * Converts an UUID to a binary string (list of 0 and 1), with a separator to - * make it more readable. - */ - public static String toBinaryString(UUID uuid, int charsPerSegment, char separator) { - String binaryString = toBinaryString(uuid); - StringBuilder sb = new StringBuilder(128 + (128 / charsPerSegment)); - for (int i = 0; i < binaryString.length(); i++) { - if (i != 0 && i % charsPerSegment == 0) - sb.append(separator); - sb.append(binaryString.charAt(i)); - } - return sb.toString(); - } - - /** Converts an UUID to a binary string (list of 0 and 1). */ - public static String toBinaryString(UUID uuid) { - String most = zeroTo64Chars(Long.toBinaryString(uuid.getMostSignificantBits())); - String least = zeroTo64Chars(Long.toBinaryString(uuid.getLeastSignificantBits())); - String binaryString = most + least; - assert binaryString.length() == 128; - return binaryString; - } - - private static String zeroTo64Chars(String str) { - assert str.length() <= 64; - if (str.length() < 64) { - StringBuilder sb = new StringBuilder(64); - for (int i = 0; i < 64 - str.length(); i++) - sb.append('0'); - sb.append(str); - return sb.toString(); - } else - return str; - } - - /** - * Converts an UUID hex representation without '-' to the standard form (with - * '-'). - */ - public static String compactToStd(String compact) { - if (compact.length() != 32) - throw new IllegalArgumentException( - "Compact UUID '" + compact + "' has length " + compact.length() + " and not 32."); - StringBuilder sb = new StringBuilder(36); - for (int i = 0; i < 32; i++) { - if (i == 8 || i == 12 || i == 16 || i == 20) - sb.append('-'); - sb.append(compact.charAt(i)); - } - String std = sb.toString(); - assert std.length() == 36; - assert UUID.fromString(std).toString().equals(std); - return std; - } - - /** - * Converts an UUID hex representation without '-' to an {@link UUID}. - */ - public static UUID fromCompact(String compact) { - return UUID.fromString(compactToStd(compact)); - } - - /** To a 32 characters hex string without '-'. */ - public static String toCompact(UUID uuid) { - return toHexString(toBytes(uuid)); - } - - public static boolean isRandom(UUID uuid) { - return uuid.version() == 4; - } - - public static boolean isTimeBased(UUID uuid) { - return uuid.version() == 1; - } - - public static boolean isTimeBasedRandom(UUID uuid) { - if (uuid.version() == 1) { - BitSet node = BitSet.valueOf(new long[] { uuid.node() }); - return node.get(0); - } else - return false; - } - - public static boolean isNameBased(UUID uuid) { - return uuid.version() == 3 || uuid.version() == 5; - } - - final private static char[] hexArray = "0123456789abcdef".toCharArray(); - - /** Convert two longs to a byte array with length 16. */ - public static byte[] toBytes(long long1, long long2) { - byte[] result = new byte[16]; - for (int i = 0; i < 8; i++) - result[i] = (byte) ((long1 >> ((7 - i) * 8)) & 0xff); - for (int i = 8; i < 16; i++) - result[i] = (byte) ((long2 >> ((15 - i) * 8)) & 0xff); - return result; - } - - public static void copyBytes(long long1, long long2, byte[] arr, int offset) { - assert arr.length >= 16 + offset; - for (int i = offset; i < 8 + offset; i++) - arr[i] = (byte) ((long1 >> ((7 - i) * 8)) & 0xff); - for (int i = 8 + offset; i < 16 + offset; i++) - arr[i] = (byte) ((long2 >> ((15 - i) * 8)) & 0xff); - } - - /** Converts a byte array to an hex String. */ - public static String toHexString(byte[] bytes) { - char[] hexChars = new char[bytes.length * 2]; - for (int j = 0; j < bytes.length; j++) { - int v = bytes[j] & 0xFF; - hexChars[j * 2] = hexArray[v >>> 4]; - hexChars[j * 2 + 1] = hexArray[v & 0x0F]; - } - return new String(hexChars); - } - - /** Singleton. */ - private AbstractUuidFactory() { - } - - /* - * SMOKE TESTS - */ - - static boolean smokeTests() throws AssertionError { - - // warm up a bit before measuring perf and logging it - int warmUpCycles = 10; - // int warmUpCycles = 10000000; - if (logger.isLoggable(DEBUG)) - for (int i = 0; i < warmUpCycles; i++) { - UUID.randomUUID(); - unsecureRandomUUID(); - timeUUID(); - timeUUIDwithRandomNode(); - nameUUIDv5(NS_DNS, "example.org"); - nameUUIDv3(NS_DNS, "example.org"); - } - - long begin; - - { - begin = System.nanoTime(); - UUID uuid = UUID.randomUUID(); - long duration = System.nanoTime() - begin; - assert isRandom(uuid); - logger.log(DEBUG, () -> uuid.toString() + " in " + duration + " ns, isRandom=" + isRandom(uuid)); - } - - { - begin = System.nanoTime(); - UUID uuid = unsecureRandomUUID(); - long duration = System.nanoTime() - begin; - assert isRandom(uuid); - logger.log(DEBUG, () -> uuid.toString() + " in " + duration + " ns, isRandom=" + isRandom(uuid)); - } - - { - begin = System.nanoTime(); - UUID uuid = timeUUID(); - long duration = System.nanoTime() - begin; - assert isTimeBased(uuid); - logger.log(DEBUG, - () -> uuid.toString() + " in " + duration + " ns, isTimeBasedRandom=" + isTimeBasedRandom(uuid)); - } - - { - begin = System.nanoTime(); - UUID uuid = timeUUIDwithRandomNode(); - long duration = System.nanoTime() - begin; - assert isTimeBasedRandom(uuid); - logger.log(DEBUG, - () -> uuid.toString() + " in " + duration + " ns, isTimeBasedRandom=" + isTimeBasedRandom(uuid)); - } - - { - begin = System.nanoTime(); - UUID uuid = nameUUIDv5(NS_DNS, "example.org"); - long duration = System.nanoTime() - begin; - assert isNameBased(uuid); - // uuidgen --sha1 --namespace @dns --name example.org - assert "aad03681-8b63-5304-89e0-8ca8f49461b5".equals(uuid.toString()); - logger.log(DEBUG, () -> uuid.toString() + " in " + duration + " ns, isNameBased=" + isNameBased(uuid)); - } - - { - begin = System.nanoTime(); - UUID uuid = nameUUIDv3(NS_DNS, "example.org"); - long duration = System.nanoTime() - begin; - assert isNameBased(uuid); - // uuidgen --md5 --namespace @dns --name example.org - assert "04738bdf-b25a-3829-a801-b21a1d25095b".equals(uuid.toString()); - logger.log(DEBUG, () -> uuid.toString() + " in " + duration + " ns, isNameBased=" + isNameBased(uuid)); - } - return AbstractUuidFactory.class.desiredAssertionStatus(); - } - - public static void main(String[] args) { - smokeTests(); - } -} diff --git a/org.argeo.api.acr/src/org/argeo/api/acr/uuid/ConcurrentTimeUuidState.java b/org.argeo.api.acr/src/org/argeo/api/acr/uuid/ConcurrentTimeUuidState.java new file mode 100644 index 000000000..bf4039678 --- /dev/null +++ b/org.argeo.api.acr/src/org/argeo/api/acr/uuid/ConcurrentTimeUuidState.java @@ -0,0 +1,153 @@ +package org.argeo.api.acr.uuid; + +import java.security.NoSuchAlgorithmException; +import java.security.SecureRandom; +import java.time.Clock; +import java.time.Duration; +import java.time.Instant; +import java.util.Objects; + +/** + * A simple base implementation of {@link TimeUuidState}, which maintains + * different clock sequences for each thread. + */ +public class ConcurrentTimeUuidState implements TimeUuidState { + /** The maximum possible value of the clocksequence. */ + private final static int MAX_CLOCKSEQUENCE = 16384; + + private final byte[] nodeId = new byte[6]; + private final ThreadLocal holder; + + private final Instant startInstant; + private final long startTimeStamp; + + private final Clock clock; + private final boolean useClockForMeasurement; + + private final SecureRandom secureRandom; + + public ConcurrentTimeUuidState(byte[] nodeId, int offset, SecureRandom secureRandom, Clock clock) { + useClockForMeasurement = clock != null; + this.clock = clock != null ? clock : Clock.systemUTC(); + + Objects.requireNonNull(secureRandom); + this.secureRandom = secureRandom; + if (nodeId != null) { + // copy array in case it should change in the future + if (offset + 6 > nodeId.length) + throw new IllegalArgumentException( + "Node id array is too small: " + nodeId.length + ", offset=" + offset); + System.arraycopy(nodeId, offset, this.nodeId, 0, 6); + } else { + this.secureRandom.nextBytes(this.nodeId); + assert TimeUuidState.isNoMacAddressNodeId(this.nodeId); + } + + // compute the start reference + startInstant = Instant.now(this.clock); + long nowVm = nowVm(); + Duration duration = Duration.between(TimeUuidState.GREGORIAN_START, startInstant); + startTimeStamp = durationToUuidTimestamp(duration) - nowVm; + + // initalise a state per thread + holder = new ThreadLocal<>() { + + @Override + protected Holder initialValue() { + Holder value = new Holder(); + value.lastTimestamp = startTimeStamp; + value.clockSequence = newClockSequence(); + System.arraycopy(ConcurrentTimeUuidState.this.nodeId, 0, value.nodeId, 0, 6); + return value; + } + }; + } + + /* + * TIME OPERATIONS + */ + + public long useTimestamp() { + long previousTimestamp = holder.get().lastTimestamp; + long now = computeNow(); + + // rare case where we are sooner + // (e.g. if system time has changed in between and we use the clock) + if (previousTimestamp > now) { + long newClockSequence = newClockSequence(); + for (int i = 0; i < 64; i++) { + if (newClockSequence != holder.get().clockSequence) + break; + newClockSequence = newClockSequence(); + } + if (newClockSequence != holder.get().clockSequence) + throw new IllegalStateException("Cannot change clock sequence"); + holder.get().clockSequence = newClockSequence; + } + + // very unlikely case where it took less than 100ns between both + if (previousTimestamp == now) { + try { + Thread.sleep(0, 100); + } catch (InterruptedException e) { + // silent + } + now = computeNow(); + assert previousTimestamp != now; + } + holder.get().lastTimestamp = now; + return now; + } + + protected long computeNow() { + if (useClockForMeasurement) { + Duration duration = Duration.between(TimeUuidState.GREGORIAN_START, Instant.now(clock)); + return durationToUuidTimestamp(duration); + } else { + return startTimeStamp + nowVm(); + } + } + + private long nowVm() { + return System.nanoTime() / 100; + } + + protected long durationToUuidTimestamp(Duration duration) { + return (duration.getSeconds() * 10000000 + duration.getNano() / 100); + } + + protected SecureRandom initSecureRandom() { + SecureRandom secureRandom; + try { + secureRandom = SecureRandom.getInstanceStrong(); + } catch (NoSuchAlgorithmException e) { + secureRandom = new SecureRandom(); + } + return secureRandom; + } + + /* + * STATE OPERATIONS + */ + + protected long newClockSequence() { + return secureRandom.nextInt(ConcurrentTimeUuidState.MAX_CLOCKSEQUENCE); + } + + /* + * ACCESSORS + */ + + @Override + public byte[] getNodeId() { + byte[] arr = new byte[6]; + System.arraycopy(holder.get().nodeId, 0, arr, 0, 6); + return arr; + } + + @Override + public long getClockSequence() { + return holder.get().clockSequence; + } + +} diff --git a/org.argeo.api.acr/src/org/argeo/api/acr/uuid/SimpleUuidFactory.java b/org.argeo.api.acr/src/org/argeo/api/acr/uuid/SimpleUuidFactory.java new file mode 100644 index 000000000..629e10435 --- /dev/null +++ b/org.argeo.api.acr/src/org/argeo/api/acr/uuid/SimpleUuidFactory.java @@ -0,0 +1,398 @@ +package org.argeo.api.acr.uuid; + +import static java.lang.System.Logger.Level.DEBUG; +import static java.lang.System.Logger.Level.WARNING; + +import java.lang.System.Logger; +import java.net.InetAddress; +import java.net.NetworkInterface; +import java.net.SocketException; +import java.net.UnknownHostException; +import java.security.DrbgParameters; +import java.security.MessageDigest; +import java.security.NoSuchAlgorithmException; +import java.security.SecureRandom; +import java.time.Clock; +import java.time.Duration; +import java.time.temporal.Temporal; +import java.util.Objects; +import java.util.Random; +import java.util.UUID; + +/** + * Simple implementation of an {@link UuidFactory}, which can be used as a base + * class for more optimised implementations. + * + * @see https://datatracker.ietf.org/doc/html/rfc4122 + */ +public class SimpleUuidFactory implements UuidFactory { + private final static Logger logger = System.getLogger(SimpleUuidFactory.class.getName()); +// private final static int MAX_CLOCKSEQUENCE = 16384; + + private SecureRandom secureRandom; + private final byte[] hardwareAddress; + +// private final AtomicInteger clockSequence; + + /** A start timestamp to which {@link System#nanoTime()}/100 can be added. */ +// private final long startTimeStamp; + + private final TimeUuidState macAddressTimeUuidState; + private final TimeUuidState defaultTimeUuidState; + + public SimpleUuidFactory(byte[] nodeId, int offset, Clock clock) { + try { + secureRandom = SecureRandom.getInstance("DRBG", + DrbgParameters.instantiation(256, DrbgParameters.Capability.PR_AND_RESEED, "UUID".getBytes())); + } catch (NoSuchAlgorithmException e) { + try { + logger.log(DEBUG, "DRBG secure random not found, using strong"); + secureRandom = SecureRandom.getInstanceStrong(); + } catch (NoSuchAlgorithmException e1) { + logger.log(WARNING, "No strong secure random was found, using default"); + secureRandom = new SecureRandom(); + } + } + +// clockSequence = new AtomicInteger(secureRandom.nextInt(MAX_CLOCKSEQUENCE)); + hardwareAddress = getHardwareAddress(); + + macAddressTimeUuidState = hardwareAddress != null + ? new ConcurrentTimeUuidState(hardwareAddress, 0, secureRandom, clock) + : null; + defaultTimeUuidState = nodeId != null ? new ConcurrentTimeUuidState(nodeId, offset, secureRandom, clock) + : macAddressTimeUuidState != null ? macAddressTimeUuidState + // we use random as a last resort + : new ConcurrentTimeUuidState(null, -1, secureRandom, clock); + + // GREGORIAN_START = ZonedDateTime.of(1582, 10, 15, 0, 0, 0, 0, ZoneOffset.UTC); +// Duration duration = Duration.between(TimeUuidState.GREGORIAN_START, Instant.now()); +// long nowVm = System.nanoTime() / 100; +// startTimeStamp = (duration.getSeconds() * 10000000 + duration.getNano() / 100) - nowVm; + } + + /* + * TIME-BASED (version 1) + */ + + private final static long MOST_SIG_VERSION1 = (1l << 12); + private final static long LEAST_SIG_RFC4122_VARIANT = (1l << 63); + + protected UUID timeUUID(long timestamp, long clockSequence, byte[] node, int offset) { + Objects.requireNonNull(node, "Node array cannot be null"); + if (node.length < offset + 6) + throw new IllegalArgumentException("Node array must be at least 6 bytes long"); + + long mostSig = MOST_SIG_VERSION1 // base for version 1 UUID + | ((timestamp & 0xFFFFFFFFL) << 32) // time_low + | (((timestamp >> 32) & 0xFFFFL) << 16) // time_mid + | ((timestamp >> 48) & 0x0FFFL);// time_hi_and_version + + long leastSig = LEAST_SIG_RFC4122_VARIANT // base for Leach–Salz UUID + | (((clockSequence & 0x3F00) >> 8) << 56) // clk_seq_hi_res + | ((clockSequence & 0xFF) << 48) // clk_seq_low + | (node[offset] & 0xFFL) // + | ((node[offset + 1] & 0xFFL) << 8) // + | ((node[offset + 2] & 0xFFL) << 16) // + | ((node[offset + 3] & 0xFFL) << 24) // + | ((node[offset + 4] & 0xFFL) << 32) // + | ((node[offset + 5] & 0xFFL) << 40); // + UUID uuid = new UUID(mostSig, leastSig); + + // tests +// assert uuid.node() == BitSet.valueOf(node).toLongArray()[0]; + //assert uuid.node() == longFromBytes(node); + assert uuid.timestamp() == timestamp; + assert uuid.clockSequence() == clockSequence + : "uuid.clockSequence()=" + uuid.clockSequence() + " clockSequence=" + clockSequence; + assert uuid.version() == 1; + assert uuid.variant() == 2; + return uuid; + } + + @Override + public UUID timeUUIDwithMacAddress() { + if (macAddressTimeUuidState == null) + throw new UnsupportedOperationException("No MAC address is available"); +// long timestamp = startTimeStamp + System.nanoTime() / 100; + return timeUUID(macAddressTimeUuidState.useTimestamp(), macAddressTimeUuidState.getClockSequence(), + macAddressTimeUuidState.getNodeId(), 0); + } + +// public UUID timeUUID(long timestamp, Random random) { +// byte[] node = new byte[6]; +// random.nextBytes(node); +// node[0] = (byte) (node[0] | 1); +//// long clockSequence = nextClockSequence(); +// return timeUUID(timestamp, macAddressTimeUuidState.getClockSequence(), node, 0); +// } + + @Override + public UUID timeUUID() { +// long timestamp = startTimeStamp + System.nanoTime() / 100; +// return timeUUID(timeUuidState.useTimestamp()); +// } +// +// public UUID timeUUID(long timestamp) { +// if (hardwareAddress == null) +// return timeUUID(timestamp, secureRandom); +// long clockSequence = nextClockSequence(); + return timeUUID(defaultTimeUuidState.useTimestamp(), defaultTimeUuidState.getClockSequence(), + defaultTimeUuidState.getNodeId(), 0); + } + +// public UUID timeUUID(long timestamp, NetworkInterface nic) { +// byte[] node; +// try { +// node = nic.getHardwareAddress(); +// } catch (SocketException e) { +// throw new IllegalStateException("Cannot get hardware address", e); +// } +//// long clockSequence = nextClockSequence(); +// return timeUUID(timestamp, macAddressTimeUuidState.getClockSequence(), node, 0); +// } + + public UUID timeUUID(Temporal time, long clockSequence, byte[] node) { + Duration duration = Duration.between(TimeUuidState.GREGORIAN_START, time); + // Number of 100 ns intervals in one second: 1000000000 / 100 = 10000000 + long timestamp = duration.getSeconds() * 10000000 + duration.getNano() / 100; + return timeUUID(timestamp, clockSequence, node, 0); + } + + private static byte[] getHardwareAddress() { + InetAddress localHost; + try { + localHost = InetAddress.getLocalHost(); + try { + NetworkInterface nic = NetworkInterface.getByInetAddress(localHost); + return nic.getHardwareAddress(); + } catch (SocketException e) { + return null; + } + } catch (UnknownHostException e) { + return null; + } + + } + +// private synchronized long nextClockSequence() { +// int i = clockSequence.incrementAndGet(); +// while (i < 0 || i >= MAX_CLOCKSEQUENCE) { +// clockSequence.set(secureRandom.nextInt(MAX_CLOCKSEQUENCE)); +// i = clockSequence.incrementAndGet(); +// } +// return (long) i; +// } + + /* + * NAME BASED (version 3 and 5) + */ + +// private final static String MD5 = "MD5"; + private final static String SHA1 = "SHA1"; + + @Override + public UUID nameUUIDv5(UUID namespace, byte[] name) { + Objects.requireNonNull(namespace, "Namespace cannot be null"); + Objects.requireNonNull(name, "Name cannot be null"); + + byte[] bytes = sha1(toBytes(namespace), name); + bytes[6] &= 0x0f; + bytes[6] |= 0x50;// v5 + bytes[8] &= 0x3f; + bytes[8] |= 0x80;// variant 1 + UUID result = fromBytes(bytes, 0); + return result; + } + + @Override + public UUID nameUUIDv3(UUID namespace, byte[] name) { + Objects.requireNonNull(namespace, "Namespace cannot be null"); + Objects.requireNonNull(name, "Name cannot be null"); + + byte[] arr = new byte[name.length + 16]; + copyBytes(namespace, arr, 0); + System.arraycopy(name, 0, arr, 16, name.length); + return UUID.nameUUIDFromBytes(arr); + } + + static byte[] sha1(byte[]... bytes) { + try { + MessageDigest digest = MessageDigest.getInstance(SHA1); + for (byte[] arr : bytes) + digest.update(arr); + byte[] checksum = digest.digest(); + return checksum; + } catch (NoSuchAlgorithmException e) { + throw new UnsupportedOperationException("SHA1 is not avalaible", e); + } + } + + /* + * RANDOM v4 + */ + @Override + public UUID randomUUID(Random random) { + byte[] arr = new byte[16]; + random.nextBytes(arr); + arr[6] &= 0x0f; + arr[6] |= 0x40;// v4 + arr[8] &= 0x3f; + arr[8] |= 0x80;// variant 1 + return fromBytes(arr); + } + + @Override + public UUID randomUUID() { + return randomUUID(secureRandom); + // return UuidFactory.super.randomUUID(); + } + + /* + * UTILITIES + */ + /** + * Convert bytes to an UUID. Byte array must not be null and be exactly of + * length 16. + */ + protected UUID fromBytes(byte[] data) { + Objects.requireNonNull(data, "Byte array must not be null"); + if (data.length != 16) + throw new IllegalArgumentException("Byte array as length " + data.length); + return fromBytes(data, 0); + } + + /** + * Convert bytes to an UUID, starting to read the array at this offset. + */ + protected UUID fromBytes(byte[] data, int offset) { + Objects.requireNonNull(data, "Byte array cannot be null"); + long msb = 0; + long lsb = 0; + for (int i = offset; i < 8 + offset; i++) + msb = (msb << 8) | (data[i] & 0xff); + for (int i = 8 + offset; i < 16 + offset; i++) + lsb = (lsb << 8) | (data[i] & 0xff); + return new UUID(msb, lsb); + } + + protected long longFromBytes(byte[] data) { + long msb = 0; + for (int i = 0; i < data.length; i++) + msb = (msb << 8) | (data[i] & 0xff); + return msb; + } + + protected byte[] toBytes(UUID uuid) { + Objects.requireNonNull(uuid, "UUID cannot be null"); + long msb = uuid.getMostSignificantBits(); + long lsb = uuid.getLeastSignificantBits(); + return toBytes(msb, lsb); + } + + protected void copyBytes(UUID uuid, byte[] arr, int offset) { + Objects.requireNonNull(uuid, "UUID cannot be null"); + long msb = uuid.getMostSignificantBits(); + long lsb = uuid.getLeastSignificantBits(); + copyBytes(msb, lsb, arr, offset); + } + + /** + * Converts an UUID to a binary string (list of 0 and 1), with a separator to + * make it more readable. + */ + public static String toBinaryString(UUID uuid, int charsPerSegment, char separator) { + String binaryString = toBinaryString(uuid); + StringBuilder sb = new StringBuilder(128 + (128 / charsPerSegment)); + for (int i = 0; i < binaryString.length(); i++) { + if (i != 0 && i % charsPerSegment == 0) + sb.append(separator); + sb.append(binaryString.charAt(i)); + } + return sb.toString(); + } + + /** Converts an UUID to a binary string (list of 0 and 1). */ + public static String toBinaryString(UUID uuid) { + String most = zeroTo64Chars(Long.toBinaryString(uuid.getMostSignificantBits())); + String least = zeroTo64Chars(Long.toBinaryString(uuid.getLeastSignificantBits())); + String binaryString = most + least; + assert binaryString.length() == 128; + return binaryString; + } + + private static String zeroTo64Chars(String str) { + assert str.length() <= 64; + if (str.length() < 64) { + StringBuilder sb = new StringBuilder(64); + for (int i = 0; i < 64 - str.length(); i++) + sb.append('0'); + sb.append(str); + return sb.toString(); + } else + return str; + } + + /** + * Converts an UUID hex representation without '-' to the standard form (with + * '-'). + */ + public static String compactToStd(String compact) { + if (compact.length() != 32) + throw new IllegalArgumentException( + "Compact UUID '" + compact + "' has length " + compact.length() + " and not 32."); + StringBuilder sb = new StringBuilder(36); + for (int i = 0; i < 32; i++) { + if (i == 8 || i == 12 || i == 16 || i == 20) + sb.append('-'); + sb.append(compact.charAt(i)); + } + String std = sb.toString(); + assert std.length() == 36; + assert UUID.fromString(std).toString().equals(std); + return std; + } + + /** + * Converts an UUID hex representation without '-' to an {@link UUID}. + */ + public static UUID fromCompact(String compact) { + return UUID.fromString(compactToStd(compact)); + } + + /** To a 32 characters hex string without '-'. */ + public String toCompact(UUID uuid) { + return toHexString(toBytes(uuid)); + } + + final private static char[] hexArray = "0123456789abcdef".toCharArray(); + + /** Convert two longs to a byte array with length 16. */ + public static byte[] toBytes(long long1, long long2) { + byte[] result = new byte[16]; + for (int i = 0; i < 8; i++) + result[i] = (byte) ((long1 >> ((7 - i) * 8)) & 0xff); + for (int i = 8; i < 16; i++) + result[i] = (byte) ((long2 >> ((15 - i) * 8)) & 0xff); + return result; + } + + public static void copyBytes(long long1, long long2, byte[] arr, int offset) { + assert arr.length >= 16 + offset; + for (int i = offset; i < 8 + offset; i++) + arr[i] = (byte) ((long1 >> ((7 - i) * 8)) & 0xff); + for (int i = 8 + offset; i < 16 + offset; i++) + arr[i] = (byte) ((long2 >> ((15 - i) * 8)) & 0xff); + } + + /** Converts a byte array to an hex String. */ + public static String toHexString(byte[] bytes) { + char[] hexChars = new char[bytes.length * 2]; + for (int j = 0; j < bytes.length; j++) { + int v = bytes[j] & 0xFF; + hexChars[j * 2] = hexArray[v >>> 4]; + hexChars[j * 2 + 1] = hexArray[v & 0x0F]; + } + return new String(hexChars); + } +} diff --git a/org.argeo.api.acr/src/org/argeo/api/acr/uuid/TimeUuidState.java b/org.argeo.api.acr/src/org/argeo/api/acr/uuid/TimeUuidState.java new file mode 100644 index 000000000..d883b8d85 --- /dev/null +++ b/org.argeo.api.acr/src/org/argeo/api/acr/uuid/TimeUuidState.java @@ -0,0 +1,58 @@ +package org.argeo.api.acr.uuid; + +import java.time.Instant; +import java.time.ZoneOffset; +import java.time.ZonedDateTime; + +/** + * The state of a time based UUID generator, as described and discussed in + * section 4.2.1 of RFC4122. + * + * @see https://datatracker.ietf.org/doc/html/rfc4122#section-4.2.1 + */ +public interface TimeUuidState { + + /** Start of the Gregorian time, used by time-based UUID (v1). */ + final static Instant GREGORIAN_START = ZonedDateTime.of(1582, 10, 15, 0, 0, 0, 0, ZoneOffset.UTC).toInstant(); + + byte[] getNodeId(); + + long useTimestamp(); + + long getClockSequence(); + + static boolean isNoMacAddressNodeId(byte[] nodeId) { + return (nodeId[0] & 1) != 0; + } + + static class Holder { + byte[] nodeId = new byte[6]; + long lastTimestamp; + long clockSequence; + + public byte[] getNodeId() { + return nodeId; + } + + public void setNodeId(byte[] nodeId) { + this.nodeId = nodeId; + } + + public long getLastTimestamp() { + return lastTimestamp; + } + + public void setLastTimestamp(long lastTimestamp) { + this.lastTimestamp = lastTimestamp; + } + + public long getClockSequence() { + return clockSequence; + } + + public void setClockSequence(long clockSequence) { + this.clockSequence = clockSequence; + } + + } +} diff --git a/org.argeo.api.acr/src/org/argeo/api/acr/uuid/UuidFactory.java b/org.argeo.api.acr/src/org/argeo/api/acr/uuid/UuidFactory.java new file mode 100644 index 000000000..eb46c302d --- /dev/null +++ b/org.argeo.api.acr/src/org/argeo/api/acr/uuid/UuidFactory.java @@ -0,0 +1,120 @@ +package org.argeo.api.acr.uuid; + +import static java.nio.charset.StandardCharsets.UTF_8; + +import java.util.Random; +import java.util.UUID; +import java.util.function.Supplier; + +/** + * A provider of RFC 4122 {@link UUID}s. Only the RFC 4122 variant (also known + * as Leach–Salz variant) is supported. The default, returned by the + * {@link Supplier#get()} method MUST be a v4 UUID (random). + * + * @see UUID + * @see https://datatracker.ietf.org/doc/html/rfc4122 + */ +public interface UuidFactory extends Supplier { + /* + * TIME-BASED (version 1) + */ + + UUID timeUUID(); + + UUID timeUUIDwithMacAddress(); + + /* + * NAME BASED (version 3 and 5) + */ + + UUID nameUUIDv5(UUID namespace, byte[] name); + + UUID nameUUIDv3(UUID namespace, byte[] name); + + default UUID nameUUIDv5(UUID namespace, String name) { + if (name == null) + throw new IllegalArgumentException("Name cannot be null"); + return nameUUIDv5(namespace, name.getBytes(UTF_8)); + } + + default UUID nameUUIDv3(UUID namespace, String name) { + if (name == null) + throw new IllegalArgumentException("Name cannot be null"); + return nameUUIDv3(namespace, name.getBytes(UTF_8)); + } + + /* + * RANDOM v4 + */ + UUID randomUUID(Random random); + + default UUID randomUUID() { + return UUID.randomUUID(); + } + + @Override + default UUID get() { + return randomUUID(); + } + + /* + * STANDARD UUIDs + */ + + /** Nil UUID (00000000-0000-0000-0000-000000000000). */ + final static UUID NIL_UUID = UUID.fromString("00000000-0000-0000-0000-000000000000"); + /** + * Standard DNS namespace ID for type 3 or 5 UUID (as defined in Appendix C of + * RFC4122). + */ + final static UUID NS_DNS = UUID.fromString("6ba7b810-9dad-11d1-80b4-00c04fd430c8"); + /** + * Standard URL namespace ID for type 3 or 5 UUID (as defined in Appendix C of + * RFC4122). + */ + final static UUID NS_URL = UUID.fromString("6ba7b811-9dad-11d1-80b4-00c04fd430c8"); + /** + * Standard OID namespace ID (typically an LDAP type) for type 3 or 5 UUID (as + * defined in Appendix C of RFC4122). + */ + final static UUID NS_OID = UUID.fromString("6ba7b812-9dad-11d1-80b4-00c04fd430c8"); + /** + * Standard X500 namespace ID (typically an LDAP DN) for type 3 or 5 UUID (as + * defined in Appendix C of RFC4122). + */ + final static UUID NS_X500 = UUID.fromString("6ba7b814-9dad-11d1-80b4-00c04fd430c8"); + + /* + * UTILITIES + */ + + static boolean isRandom(UUID uuid) { + return uuid.version() == 4; + } + + static boolean isTimeBased(UUID uuid) { + return uuid.version() == 1; + } + + /** + * Whether this UUID is time based but was not generated from an IEEE 802 + * address, as per Section 4.5 of RFC4122. + * + * @see https://datatracker.ietf.org/doc/html/rfc4122#section-4.5 + */ + static boolean isTimeBasedWithMacAddress(UUID uuid) { + if (uuid.version() == 1) { + return (uuid.node() & 1L) == 0; + } else + return false; + } + + static boolean isNameBased(UUID uuid) { + return uuid.version() == 3 || uuid.version() == 5; + } + + /* + * DEFAULT + */ + final static UuidFactory DEFAULT = new SimpleUuidFactory(null, -1, null); +}