--- jsr166/src/main/java/util/SplittableRandom.java 2013/08/24 06:06:53 1.19 +++ jsr166/src/main/java/util/SplittableRandom.java 2014/12/02 12:17:38 1.25 @@ -25,8 +25,6 @@ package java.util; -import java.security.SecureRandom; -import java.net.InetAddress; import java.util.concurrent.atomic.AtomicLong; import java.util.function.IntConsumer; import java.util.function.LongConsumer; @@ -88,7 +86,7 @@ import java.util.stream.DoubleStream; * @author Doug Lea * @since 1.8 */ -public class SplittableRandom { +public final class SplittableRandom { /* * Implementation Overview. @@ -108,29 +106,25 @@ public class SplittableRandom { * Methods nextLong, nextInt, and derivatives do not return the * sequence (seed) values, but instead a hash-like bit-mix of * their bits, producing more independently distributed sequences. - * For nextLong, the mix64 bit-mixing function computes the same - * value as the "64-bit finalizer" function in Austin Appleby's - * MurmurHash3 algorithm. See - * http://code.google.com/p/smhasher/wiki/MurmurHash3 , which - * comments: "The constants for the finalizers were generated by a - * simple simulated-annealing algorithm, and both avalanche all - * bits of 'h' to within 0.25% bias." The mix32 function is - * equivalent to (int)(mix64(seed) >>> 32), but faster because it - * omits a step that doesn't contribute to result. + * For nextLong, the mix64 function is based on David Stafford's + * (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html) + * "Mix13" variant of the "64-bit finalizer" function in Austin + * Appleby's MurmurHash3 algorithm (see + * http://code.google.com/p/smhasher/wiki/MurmurHash3). The mix32 + * function is based on Stafford's Mix04 mix function, but returns + * the upper 32 bits cast as int. * * The split operation uses the current generator to form the seed * and gamma for another SplittableRandom. To conservatively * avoid potential correlations between seed and value generation, - * gamma selection (method nextGamma) uses the "Mix13" constants - * for MurmurHash3 described by David Stafford - * (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html) - * To avoid potential weaknesses in bit-mixing transformations, we - * restrict gammas to odd values with at least 12 and no more than - * 52 bits set. Rather than rejecting candidates with too few or - * too many bits set, method nextGamma flips some bits (which has - * the effect of mapping at most 4 to any given gamma value). - * This reduces the effective set of 64bit odd gamma values by - * about 214, a very tiny percentage, and serves as an + * gamma selection (method mixGamma) uses different + * (Murmurhash3's) mix constants. To avoid potential weaknesses + * in bit-mixing transformations, we restrict gammas to odd values + * with at least 24 0-1 or 1-0 bit transitions. Rather than + * rejecting candidates with too few or too many bits set, method + * mixGamma flips some bits (which has the effect of mapping at + * most 4 to any given gamma value). This reduces the effective + * set of 64bit odd gamma values by about 2%, and serves as an * automated screening for sequence constant selection that is * left as an empirical decision in some other hashing and crypto * algorithms. @@ -141,14 +135,14 @@ public class SplittableRandom { * avalanching. * * The default (no-argument) constructor, in essence, invokes - * split() for a common "seeder" SplittableRandom. Unlike other - * cases, this split must be performed in a thread-safe manner, so - * we use an AtomicLong to represent the seed rather than use an - * explicit SplittableRandom. To bootstrap the seeder, we start - * off using a seed based on current time and host unless the - * SecureRandomSeed property is set. This serves as a - * slimmed-down (and insecure) variant of SecureRandom that also - * avoids stalls that may occur when using /dev/random. + * split() for a common "defaultGen" SplittableRandom. Unlike + * other cases, this split must be performed in a thread-safe + * manner, so we use an AtomicLong to represent the seed rather + * than use an explicit SplittableRandom. To bootstrap the + * defaultGen, we start off using a seed based on current time + * unless the java.util.secureRandomSeed property is set. This + * serves as a slimmed-down (and insecure) variant of SecureRandom + * that also avoids stalls that may occur when using /dev/random. * * It is a relatively simple matter to apply the basic design here * to use 128 bit seeds. However, emulating 128bit arithmetic and @@ -161,17 +155,16 @@ public class SplittableRandom { */ /** - * The initial gamma value for (unsplit) SplittableRandoms. Must - * be odd with at least 12 and no more than 52 bits set. Currently - * set to the golden ratio scaled to 64bits. + * The golden ratio scaled to 64bits, used as the initial gamma + * value for (unsplit) SplittableRandoms. */ - private static final long INITIAL_GAMMA = 0x9e3779b97f4a7c15L; + private static final long GOLDEN_GAMMA = 0x9e3779b97f4a7c15L; /** * The least non-zero value returned by nextDouble(). This value * is scaled by a random value of 53 bits to produce a result. */ - private static final double DOUBLE_UNIT = 1.0 / (1L << 53); + private static final double DOUBLE_UNIT = 0x1.0p-53; // 1.0 / (1L << 53); /** * The seed. Updated only via method nextSeed. @@ -192,31 +185,31 @@ public class SplittableRandom { } /** - * Computes MurmurHash3 64bit mix function. + * Computes Stafford variant 13 of 64bit mix function. */ private static long mix64(long z) { - z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL; - z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L; - return z ^ (z >>> 33); + z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L; + z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL; + return z ^ (z >>> 31); } /** - * Returns the 32 high bits of mix64(z) as int. + * Returns the 32 high bits of Stafford variant 4 mix64 function as int. */ private static int mix32(long z) { - z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL; - return (int)(((z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L) >>> 32); + z = (z ^ (z >>> 33)) * 0x62a9d9ed799705f5L; + return (int)(((z ^ (z >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32); } /** * Returns the gamma value to use for a new split instance. */ - private static long nextGamma(long z) { - z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L; // Stafford "Mix13" - z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL; - z = (z ^ (z >>> 31)) | 1L; // force to be odd - int n = Long.bitCount(z); // ensure enough 0 and 1 bits - return (n < 12 || n > 52) ? z ^ 0xaaaaaaaaaaaaaaaaL : z; + private static long mixGamma(long z) { + z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL; // MurmurHash3 mix constants + z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L; + z = (z ^ (z >>> 33)) | 1L; // force to be odd + int n = Long.bitCount(z ^ (z >>> 1)); // ensure enough transitions + return (n < 24) ? z ^ 0xaaaaaaaaaaaaaaaaL : z; } /** @@ -229,27 +222,20 @@ public class SplittableRandom { /** * The seed generator for default constructors. */ - private static final AtomicLong seeder = new AtomicLong(initialSeed()); + private static final AtomicLong defaultGen = new AtomicLong(initialSeed()); private static long initialSeed() { - try { // ignore exceptions in accessing/parsing properties - String pp = System.getProperty - ("java.util.secureRandomSeed"); - if (pp != null && pp.equalsIgnoreCase("true")) { - byte[] seedBytes = java.security.SecureRandom.getSeed(8); - long s = (long)(seedBytes[0]) & 0xffL; - for (int i = 1; i < 8; ++i) - s = (s << 8) | ((long)(seedBytes[i]) & 0xffL); - return s; - } - } catch (Exception ignore) { - } - int hh = 0; // hashed host address - try { - hh = InetAddress.getLocalHost().hashCode(); - } catch (Exception ignore) { + String pp = java.security.AccessController.doPrivileged( + new sun.security.action.GetPropertyAction( + "java.util.secureRandomSeed")); + if (pp != null && pp.equalsIgnoreCase("true")) { + byte[] seedBytes = java.security.SecureRandom.getSeed(8); + long s = (long)(seedBytes[0]) & 0xffL; + for (int i = 1; i < 8; ++i) + s = (s << 8) | ((long)(seedBytes[i]) & 0xffL); + return s; } - return (mix64((((long)hh) << 32) ^ System.currentTimeMillis()) ^ + return (mix64(System.currentTimeMillis()) ^ mix64(System.nanoTime())); } @@ -377,7 +363,7 @@ public class SplittableRandom { * @param seed the initial seed */ public SplittableRandom(long seed) { - this(seed, INITIAL_GAMMA); + this(seed, GOLDEN_GAMMA); } /** @@ -386,8 +372,10 @@ public class SplittableRandom { * of those of any other instances in the current program; and * may, and typically does, vary across program invocations. */ - public SplittableRandom() { // emulate seeder.split() - this.gamma = nextGamma(this.seed = seeder.addAndGet(INITIAL_GAMMA)); + public SplittableRandom() { // emulate defaultGen.split() + long s = defaultGen.getAndAdd(2 * GOLDEN_GAMMA); + this.seed = mix64(s); + this.gamma = mixGamma(s + GOLDEN_GAMMA); } /** @@ -405,8 +393,7 @@ public class SplittableRandom { * @return the new SplittableRandom instance */ public SplittableRandom split() { - long s = nextSeed(); - return new SplittableRandom(s, nextGamma(s)); + return new SplittableRandom(nextLong(), mixGamma(nextSeed())); } /**