--- jsr166/src/main/java/util/SplittableRandom.java 2013/08/13 23:34:47 1.17 +++ jsr166/src/main/java/util/SplittableRandom.java 2013/09/20 09:38:07 1.22 @@ -25,9 +25,10 @@ package java.util; -import java.net.InetAddress; +import java.security.SecureRandom; +import java.net.NetworkInterface; +import java.util.Enumeration; import java.util.concurrent.atomic.AtomicLong; -import java.util.Spliterator; import java.util.function.IntConsumer; import java.util.function.LongConsumer; import java.util.function.DoubleConsumer; @@ -39,7 +40,7 @@ import java.util.stream.DoubleStream; /** * A generator of uniform pseudorandom values applicable for use in * (among other contexts) isolated parallel computations that may - * generate subtasks. Class SplittableRandom supports methods for + * generate subtasks. Class {@code SplittableRandom} supports methods for * producing pseudorandom numbers of type {@code int}, {@code long}, * and {@code double} with similar usages as for class * {@link java.util.Random} but differs in the following ways: @@ -77,6 +78,13 @@ import java.util.stream.DoubleStream; * * * + *

Instances of {@code SplittableRandom} are not cryptographically + * secure. Consider instead using {@link java.security.SecureRandom} + * in security-sensitive applications. Additionally, + * default-constructed instances do not use a cryptographically random + * seed unless the {@linkplain System#getProperty system property} + * {@code java.util.secureRandomSeed} is set to {@code true}. + * * @author Guy Steele * @author Doug Lea * @since 1.8 @@ -101,29 +109,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. @@ -134,13 +138,15 @@ 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. 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 and + * network interface address 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 @@ -153,17 +159,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_ULP = 1.0 / (1L << 53); /** * The seed. Updated only via method nextSeed. @@ -184,31 +189,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 *= 0xbf58476d1ce4e5b9L; + z = (z ^ (z >>> 32)) * 0x94d049bb133111ebL; + return z ^ (z >>> 32); } /** - * 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 *= 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 *= 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; } /** @@ -221,20 +226,48 @@ public class SplittableRandom { /** * The seed generator for default constructors. */ - private static final AtomicLong seeder = - new AtomicLong(mix64((((long)hashedHostAddress()) << 32) ^ - System.currentTimeMillis()) ^ - mix64(System.nanoTime())); + private static final AtomicLong defaultGen = new AtomicLong(initialSeed()); - /** - * Returns hash of local host IP address, if available; else 0. - */ - private static int hashedHostAddress() { + private static long initialSeed() { + 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; + } + long h = 0L; try { - return InetAddress.getLocalHost().hashCode(); - } catch (Exception ex) { - return 0; + Enumeration ifcs = + NetworkInterface.getNetworkInterfaces(); + boolean retry = false; // retry once if getHardwareAddress is null + while (ifcs.hasMoreElements()) { + NetworkInterface ifc = ifcs.nextElement(); + if (!ifc.isVirtual()) { // skip fake addresses + byte[] bs = ifc.getHardwareAddress(); + if (bs != null) { + int n = bs.length; + int m = Math.min(n >>> 1, 4); + for (int i = 0; i < m; ++i) + h = (h << 16) ^ (bs[i] << 8) ^ bs[n-1-i]; + if (m < 4) + h = (h << 8) ^ bs[n-1-m]; + h = mix64(h); + break; + } + else if (!retry) + retry = true; + else + break; + } + } + } catch (Exception ignore) { } + return (h ^ mix64(System.currentTimeMillis()) ^ + mix64(System.nanoTime())); } // IllegalArgumentException messages @@ -342,7 +375,7 @@ public class SplittableRandom { * @return a pseudorandom value */ final double internalNextDouble(double origin, double bound) { - double r = (nextLong() >>> 11) * DOUBLE_UNIT; + double r = (nextLong() >>> 11) * DOUBLE_ULP; if (origin < bound) { r = r * (bound - origin) + origin; if (r >= bound) // correct for rounding @@ -361,7 +394,7 @@ public class SplittableRandom { * @param seed the initial seed */ public SplittableRandom(long seed) { - this(seed, INITIAL_GAMMA); + this(seed, GOLDEN_GAMMA); } /** @@ -370,8 +403,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); } /** @@ -389,8 +424,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())); } /** @@ -406,8 +440,7 @@ public class SplittableRandom { * Returns a pseudorandom {@code int} value between zero (inclusive) * and the specified bound (exclusive). * - * @param bound the bound on the random number to be returned. Must be - * positive. + * @param bound the upper bound (exclusive). Must be positive. * @return a pseudorandom {@code int} value between zero * (inclusive) and the bound (exclusive) * @throws IllegalArgumentException if {@code bound} is not positive @@ -459,8 +492,7 @@ public class SplittableRandom { * Returns a pseudorandom {@code long} value between zero (inclusive) * and the specified bound (exclusive). * - * @param bound the bound on the random number to be returned. Must be - * positive. + * @param bound the upper bound (exclusive). Must be positive. * @return a pseudorandom {@code long} value between zero * (inclusive) and the bound (exclusive) * @throws IllegalArgumentException if {@code bound} is not positive @@ -504,18 +536,17 @@ public class SplittableRandom { * (inclusive) and one (exclusive). * * @return a pseudorandom {@code double} value between zero - * (inclusive) and one (exclusive) + * (inclusive) and one (exclusive) */ public double nextDouble() { - return (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT; + return (mix64(nextSeed()) >>> 11) * DOUBLE_ULP; } /** * Returns a pseudorandom {@code double} value between 0.0 * (inclusive) and the specified bound (exclusive). * - * @param bound the bound on the random number to be returned. Must be - * positive. + * @param bound the upper bound (exclusive). Must be positive. * @return a pseudorandom {@code double} value between zero * (inclusive) and the bound (exclusive) * @throws IllegalArgumentException if {@code bound} is not positive @@ -523,7 +554,7 @@ public class SplittableRandom { public double nextDouble(double bound) { if (!(bound > 0.0)) throw new IllegalArgumentException(BadBound); - double result = (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT * bound; + double result = (mix64(nextSeed()) >>> 11) * DOUBLE_ULP * bound; return (result < bound) ? result : // correct for rounding Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1); } @@ -533,7 +564,7 @@ public class SplittableRandom { * origin (inclusive) and bound (exclusive). * * @param origin the least value returned - * @param bound the upper bound + * @param bound the upper bound (exclusive) * @return a pseudorandom {@code double} value between the origin * (inclusive) and the bound (exclusive) * @throws IllegalArgumentException if {@code origin} is greater than @@ -594,14 +625,15 @@ public class SplittableRandom { /** * Returns a stream producing the given {@code streamSize} number - * of pseudorandom {@code int} values, each conforming to the - * given origin and bound. + * of pseudorandom {@code int} values from this generator and/or one split + * from it; each value conforms to the given origin (inclusive) and bound + * (exclusive). * * @param streamSize the number of values to generate - * @param randomNumberOrigin the origin of each random value - * @param randomNumberBound the bound of each random value + * @param randomNumberOrigin the origin (inclusive) of each random value + * @param randomNumberBound the bound (exclusive) of each random value * @return a stream of pseudorandom {@code int} values, - * each with the given origin and bound + * each with the given origin (inclusive) and bound (exclusive) * @throws IllegalArgumentException if {@code streamSize} is * less than zero, or {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} @@ -620,15 +652,16 @@ public class SplittableRandom { /** * Returns an effectively unlimited stream of pseudorandom {@code - * int} values, each conforming to the given origin and bound. + * int} values from this generator and/or one split from it; each value + * conforms to the given origin (inclusive) and bound (exclusive). * * @implNote This method is implemented to be equivalent to {@code * ints(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}. * - * @param randomNumberOrigin the origin of each random value - * @param randomNumberBound the bound of each random value + * @param randomNumberOrigin the origin (inclusive) of each random value + * @param randomNumberBound the bound (exclusive) of each random value * @return a stream of pseudorandom {@code int} values, - * each with the given origin and bound + * each with the given origin (inclusive) and bound (exclusive) * @throws IllegalArgumentException if {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} */ @@ -678,14 +711,15 @@ public class SplittableRandom { /** * Returns a stream producing the given {@code streamSize} number of - * pseudorandom {@code long} values, each conforming to the - * given origin and bound. + * pseudorandom {@code long} values from this generator and/or one split + * from it; each value conforms to the given origin (inclusive) and bound + * (exclusive). * * @param streamSize the number of values to generate - * @param randomNumberOrigin the origin of each random value - * @param randomNumberBound the bound of each random value + * @param randomNumberOrigin the origin (inclusive) of each random value + * @param randomNumberBound the bound (exclusive) of each random value * @return a stream of pseudorandom {@code long} values, - * each with the given origin and bound + * each with the given origin (inclusive) and bound (exclusive) * @throws IllegalArgumentException if {@code streamSize} is * less than zero, or {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} @@ -704,15 +738,16 @@ public class SplittableRandom { /** * Returns an effectively unlimited stream of pseudorandom {@code - * long} values, each conforming to the given origin and bound. + * long} values from this generator and/or one split from it; each value + * conforms to the given origin (inclusive) and bound (exclusive). * * @implNote This method is implemented to be equivalent to {@code * longs(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}. * - * @param randomNumberOrigin the origin of each random value - * @param randomNumberBound the bound of each random value + * @param randomNumberOrigin the origin (inclusive) of each random value + * @param randomNumberBound the bound (exclusive) of each random value * @return a stream of pseudorandom {@code long} values, - * each with the given origin and bound + * each with the given origin (inclusive) and bound (exclusive) * @throws IllegalArgumentException if {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} */ @@ -727,8 +762,8 @@ public class SplittableRandom { /** * Returns a stream producing the given {@code streamSize} number of - * pseudorandom {@code double} values, each between zero - * (inclusive) and one (exclusive). + * pseudorandom {@code double} values from this generator and/or one split + * from it; each value is between zero (inclusive) and one (exclusive). * * @param streamSize the number of values to generate * @return a stream of {@code double} values @@ -746,8 +781,8 @@ public class SplittableRandom { /** * Returns an effectively unlimited stream of pseudorandom {@code - * double} values, each between zero (inclusive) and one - * (exclusive). + * double} values from this generator and/or one split from it; each value + * is between zero (inclusive) and one (exclusive). * * @implNote This method is implemented to be equivalent to {@code * doubles(Long.MAX_VALUE)}. @@ -763,16 +798,17 @@ public class SplittableRandom { /** * Returns a stream producing the given {@code streamSize} number of - * pseudorandom {@code double} values, each conforming to the - * given origin and bound. + * pseudorandom {@code double} values from this generator and/or one split + * from it; each value conforms to the given origin (inclusive) and bound + * (exclusive). * * @param streamSize the number of values to generate - * @param randomNumberOrigin the origin of each random value - * @param randomNumberBound the bound of each random value + * @param randomNumberOrigin the origin (inclusive) of each random value + * @param randomNumberBound the bound (exclusive) of each random value * @return a stream of pseudorandom {@code double} values, - * each with the given origin and bound + * each with the given origin (inclusive) and bound (exclusive) * @throws IllegalArgumentException if {@code streamSize} is - * less than zero + * less than zero * @throws IllegalArgumentException if {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} */ @@ -790,15 +826,16 @@ public class SplittableRandom { /** * Returns an effectively unlimited stream of pseudorandom {@code - * double} values, each conforming to the given origin and bound. + * double} values from this generator and/or one split from it; each value + * conforms to the given origin (inclusive) and bound (exclusive). * * @implNote This method is implemented to be equivalent to {@code * doubles(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}. * - * @param randomNumberOrigin the origin of each random value - * @param randomNumberBound the bound of each random value + * @param randomNumberOrigin the origin (inclusive) of each random value + * @param randomNumberBound the bound (exclusive) of each random value * @return a stream of pseudorandom {@code double} values, - * each with the given origin and bound + * each with the given origin (inclusive) and bound (exclusive) * @throws IllegalArgumentException if {@code randomNumberOrigin} * is greater than or equal to {@code randomNumberBound} */