ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/SplittableRandom.java
(Generate patch)

Comparing jsr166/src/main/java/util/SplittableRandom.java (file contents):
Revision 1.16 by dl, Tue Aug 13 17:13:57 2013 UTC vs.
Revision 1.24 by dl, Mon Oct 7 10:54:27 2013 UTC

# Line 25 | Line 25
25  
26   package java.util;
27  
28 < import java.net.InetAddress;
28 > import java.net.NetworkInterface;
29   import java.util.concurrent.atomic.AtomicLong;
30 import java.util.Spliterator;
30   import java.util.function.IntConsumer;
31   import java.util.function.LongConsumer;
32   import java.util.function.DoubleConsumer;
# Line 39 | Line 38 | import java.util.stream.DoubleStream;
38   /**
39   * A generator of uniform pseudorandom values applicable for use in
40   * (among other contexts) isolated parallel computations that may
41 < * generate subtasks. Class SplittableRandom supports methods for
41 > * generate subtasks. Class {@code SplittableRandom} supports methods for
42   * producing pseudorandom numbers of type {@code int}, {@code long},
43   * and {@code double} with similar usages as for class
44   * {@link java.util.Random} but differs in the following ways:
# Line 77 | Line 76 | import java.util.stream.DoubleStream;
76   *
77   * </ul>
78   *
79 + * <p>Instances of {@code SplittableRandom} are not cryptographically
80 + * secure.  Consider instead using {@link java.security.SecureRandom}
81 + * in security-sensitive applications. Additionally,
82 + * default-constructed instances do not use a cryptographically random
83 + * seed unless the {@linkplain System#getProperty system property}
84 + * {@code java.util.secureRandomSeed} is set to {@code true}.
85 + *
86   * @author  Guy Steele
87   * @author  Doug Lea
88   * @since   1.8
89   */
90 < public class SplittableRandom {
90 > public final class SplittableRandom {
91  
92      /*
93       * Implementation Overview.
# Line 101 | Line 107 | public class SplittableRandom {
107       * Methods nextLong, nextInt, and derivatives do not return the
108       * sequence (seed) values, but instead a hash-like bit-mix of
109       * their bits, producing more independently distributed sequences.
110 <     * For nextLong, the mix64 bit-mixing function computes the same
111 <     * value as the "64-bit finalizer" function in Austin Appleby's
112 <     * MurmurHash3 algorithm.  See
113 <     * http://code.google.com/p/smhasher/wiki/MurmurHash3 , which
114 <     * comments: "The constants for the finalizers were generated by a
115 <     * simple simulated-annealing algorithm, and both avalanche all
116 <     * bits of 'h' to within 0.25% bias." The mix32 function is
111 <     * equivalent to (int)(mix64(seed) >>> 32), but faster because it
112 <     * omits a step that doesn't contribute to result.
110 >     * For nextLong, the mix64 function is based on David Stafford's
111 >     * (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html)
112 >     * "Mix13" variant of the "64-bit finalizer" function in Austin
113 >     * Appleby's MurmurHash3 algorithm (see
114 >     * http://code.google.com/p/smhasher/wiki/MurmurHash3). The mix32
115 >     * function is based on Stafford's Mix04 mix function, but returns
116 >     * the upper 32 bits cast as int.
117       *
118       * The split operation uses the current generator to form the seed
119       * and gamma for another SplittableRandom.  To conservatively
120       * avoid potential correlations between seed and value generation,
121 <     * gamma selection (method nextGamma) uses the "Mix13" constants
122 <     * for MurmurHash3 described by David Stafford
123 <     * (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html)
124 <     * To avoid potential weaknesses in bit-mixing transformations, we
125 <     * restrict gammas to odd values with at least 12 and no more than
126 <     * 52 bits set.  Rather than rejecting candidates with too few or
127 <     * too many bits set, method nextGamma flips some bits (which has
128 <     * the effect of mapping at most 4 to any given gamma value).
125 <     * This reduces the effective set of 64bit odd gamma values by
126 <     * about 2<sup>14</sup>, a very tiny percentage, and serves as an
121 >     * gamma selection (method mixGamma) uses different
122 >     * (Murmurhash3's) mix constants.  To avoid potential weaknesses
123 >     * in bit-mixing transformations, we restrict gammas to odd values
124 >     * with at least 24 0-1 or 1-0 bit transitions.  Rather than
125 >     * rejecting candidates with too few or too many bits set, method
126 >     * mixGamma flips some bits (which has the effect of mapping at
127 >     * most 4 to any given gamma value).  This reduces the effective
128 >     * set of 64bit odd gamma values by about 2%, and serves as an
129       * automated screening for sequence constant selection that is
130       * left as an empirical decision in some other hashing and crypto
131       * algorithms.
# Line 134 | Line 136 | public class SplittableRandom {
136       * avalanching.
137       *
138       * The default (no-argument) constructor, in essence, invokes
139 <     * split() for a common "seeder" SplittableRandom.  Unlike other
140 <     * cases, this split must be performed in a thread-safe manner, so
141 <     * we use an AtomicLong to represent the seed rather than use an
142 <     * explicit SplittableRandom. To bootstrap the seeder, we start
143 <     * off using a seed based on current time and host. This serves as
144 <     * a slimmed-down (and insecure) variant of SecureRandom that also
145 <     * avoids stalls that may occur when using /dev/random.
139 >     * split() for a common "defaultGen" SplittableRandom.  Unlike
140 >     * other cases, this split must be performed in a thread-safe
141 >     * manner, so we use an AtomicLong to represent the seed rather
142 >     * than use an explicit SplittableRandom. To bootstrap the
143 >     * defaultGen, we start off using a seed based on current time and
144 >     * network interface address unless the java.util.secureRandomSeed
145 >     * property is set. This serves as a slimmed-down (and insecure)
146 >     * variant of SecureRandom that also avoids stalls that may occur
147 >     * when using /dev/random.
148       *
149       * It is a relatively simple matter to apply the basic design here
150       * to use 128 bit seeds. However, emulating 128bit arithmetic and
# Line 153 | Line 157 | public class SplittableRandom {
157       */
158  
159      /**
160 <     * The initial gamma value for (unsplit) SplittableRandoms. Must
161 <     * be odd with at least 12 and no more than 52 bits set. Currently
158 <     * set to the golden ratio scaled to 64bits.
160 >     * The golden ratio scaled to 64bits, used as the initial gamma
161 >     * value for (unsplit) SplittableRandoms.
162       */
163 <    private static final long INITIAL_GAMMA = 0x9e3779b97f4a7c15L;
163 >    private static final long GOLDEN_GAMMA = 0x9e3779b97f4a7c15L;
164  
165      /**
166       * The least non-zero value returned by nextDouble(). This value
167       * is scaled by a random value of 53 bits to produce a result.
168       */
169 <    private static final double DOUBLE_UNIT = 1.0 / (1L << 53);
169 >    private static final double DOUBLE_UNIT = 0x1.0p-53; // 1.0 / (1L << 53);
170  
171      /**
172       * The seed. Updated only via method nextSeed.
# Line 184 | Line 187 | public class SplittableRandom {
187      }
188  
189      /**
190 <     * Computes MurmurHash3 64bit mix function.
190 >     * Computes Stafford variant 13 of 64bit mix function.
191       */
192      private static long mix64(long z) {
193 <        z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;
194 <        z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L;
195 <        return z ^ (z >>> 33);
193 >        z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L;
194 >        z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL;
195 >        return z ^ (z >>> 31);
196      }
197  
198      /**
199 <     * Returns the 32 high bits of mix64(z) as int.
199 >     * Returns the 32 high bits of Stafford variant 4 mix64 function as int.
200       */
201      private static int mix32(long z) {
202 <        z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;
203 <        return (int)(((z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L) >>> 32);
202 >        z = (z ^ (z >>> 33)) * 0x62a9d9ed799705f5L;
203 >        return (int)(((z ^ (z >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32);
204      }
205  
206      /**
207       * Returns the gamma value to use for a new split instance.
208       */
209 <    private static long nextGamma(long z) {
210 <        z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L; // Stafford "Mix13"
211 <        z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL;
212 <        z = (z ^ (z >>> 31)) | 1L; // force to be odd
213 <        int n = Long.bitCount(z);  // ensure enough 0 and 1 bits
214 <        return (n < 12 || n > 52) ? z ^ 0xaaaaaaaaaaaaaaaaL : z;
209 >    private static long mixGamma(long z) {
210 >        z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL; // MurmurHash3 mix constants
211 >        z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L;
212 >        z = (z ^ (z >>> 33)) | 1L;                  // force to be odd
213 >        int n = Long.bitCount(z ^ (z >>> 1));       // ensure enough transitions
214 >        return (n < 24) ? z ^ 0xaaaaaaaaaaaaaaaaL : z;
215      }
216  
217      /**
# Line 221 | Line 224 | public class SplittableRandom {
224      /**
225       * The seed generator for default constructors.
226       */
227 <    private static final AtomicLong seeder =
225 <        new AtomicLong(mix64((((long)hashedHostAddress()) << 32) ^
226 <                             System.currentTimeMillis()) ^
227 <                       mix64(System.nanoTime()));
227 >    private static final AtomicLong defaultGen = new AtomicLong(initialSeed());
228  
229 <    /**
230 <     * Returns hash of local host IP address, if available; else 0.
231 <     */
232 <    private static int hashedHostAddress() {
233 <        try {
234 <            return InetAddress.getLocalHost().hashCode();
235 <        } catch (Exception ex) {
236 <            return 0;
237 <        }
229 >    private static long initialSeed() {
230 >        String pp = java.security.AccessController.doPrivileged(
231 >                new sun.security.action.GetPropertyAction(
232 >                        "java.util.secureRandomSeed"));
233 >        if (pp != null && pp.equalsIgnoreCase("true")) {
234 >            byte[] seedBytes = java.security.SecureRandom.getSeed(8);
235 >            long s = (long)(seedBytes[0]) & 0xffL;
236 >            for (int i = 1; i < 8; ++i)
237 >                s = (s << 8) | ((long)(seedBytes[i]) & 0xffL);
238 >            return s;
239 >        }
240 >        long h = 0L;
241 >        try {
242 >            Enumeration<NetworkInterface> ifcs =
243 >                    NetworkInterface.getNetworkInterfaces();
244 >            boolean retry = false; // retry once if getHardwareAddress is null
245 >            while (ifcs.hasMoreElements()) {
246 >                NetworkInterface ifc = ifcs.nextElement();
247 >                if (!ifc.isVirtual()) { // skip fake addresses
248 >                    byte[] bs = ifc.getHardwareAddress();
249 >                    if (bs != null) {
250 >                        int n = bs.length;
251 >                        int m = Math.min(n >>> 1, 4);
252 >                        for (int i = 0; i < m; ++i)
253 >                            h = (h << 16) ^ (bs[i] << 8) ^ bs[n-1-i];
254 >                        if (m < 4)
255 >                            h = (h << 8) ^ bs[n-1-m];
256 >                        h = mix64(h);
257 >                        break;
258 >                    }
259 >                    else if (!retry)
260 >                        retry = true;
261 >                    else
262 >                        break;
263 >                }
264 >            }
265 >        } catch (Exception ignore) {
266 >        }
267 >        return (h ^ mix64(System.currentTimeMillis()) ^
268 >                mix64(System.nanoTime()));
269      }
270  
271      // IllegalArgumentException messages
# Line 361 | Line 392 | public class SplittableRandom {
392       * @param seed the initial seed
393       */
394      public SplittableRandom(long seed) {
395 <        this(seed, INITIAL_GAMMA);
395 >        this(seed, GOLDEN_GAMMA);
396      }
397  
398      /**
# Line 370 | Line 401 | public class SplittableRandom {
401       * of those of any other instances in the current program; and
402       * may, and typically does, vary across program invocations.
403       */
404 <    public SplittableRandom() { // emulate seeder.split()
405 <        this.gamma = nextGamma(this.seed = seeder.addAndGet(INITIAL_GAMMA));
404 >    public SplittableRandom() { // emulate defaultGen.split()
405 >        long s = defaultGen.getAndAdd(2 * GOLDEN_GAMMA);
406 >        this.seed = mix64(s);
407 >        this.gamma = mixGamma(s + GOLDEN_GAMMA);
408      }
409  
410      /**
# Line 389 | Line 422 | public class SplittableRandom {
422       * @return the new SplittableRandom instance
423       */
424      public SplittableRandom split() {
425 <        long s = nextSeed();
393 <        return new SplittableRandom(s, nextGamma(s));
425 >        return new SplittableRandom(nextLong(), mixGamma(nextSeed()));
426      }
427  
428      /**
# Line 406 | Line 438 | public class SplittableRandom {
438       * Returns a pseudorandom {@code int} value between zero (inclusive)
439       * and the specified bound (exclusive).
440       *
441 <     * @param bound the bound on the random number to be returned.  Must be
410 <     *        positive.
441 >     * @param bound the upper bound (exclusive).  Must be positive.
442       * @return a pseudorandom {@code int} value between zero
443       *         (inclusive) and the bound (exclusive)
444       * @throws IllegalArgumentException if {@code bound} is not positive
# Line 459 | Line 490 | public class SplittableRandom {
490       * Returns a pseudorandom {@code long} value between zero (inclusive)
491       * and the specified bound (exclusive).
492       *
493 <     * @param bound the bound on the random number to be returned.  Must be
463 <     *        positive.
493 >     * @param bound the upper bound (exclusive).  Must be positive.
494       * @return a pseudorandom {@code long} value between zero
495       *         (inclusive) and the bound (exclusive)
496       * @throws IllegalArgumentException if {@code bound} is not positive
# Line 504 | Line 534 | public class SplittableRandom {
534       * (inclusive) and one (exclusive).
535       *
536       * @return a pseudorandom {@code double} value between zero
537 <     * (inclusive) and one (exclusive)
537 >     *         (inclusive) and one (exclusive)
538       */
539      public double nextDouble() {
540          return (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT;
# Line 514 | Line 544 | public class SplittableRandom {
544       * Returns a pseudorandom {@code double} value between 0.0
545       * (inclusive) and the specified bound (exclusive).
546       *
547 <     * @param bound the bound on the random number to be returned.  Must be
518 <     *        positive.
547 >     * @param bound the upper bound (exclusive).  Must be positive.
548       * @return a pseudorandom {@code double} value between zero
549       *         (inclusive) and the bound (exclusive)
550       * @throws IllegalArgumentException if {@code bound} is not positive
# Line 533 | Line 562 | public class SplittableRandom {
562       * origin (inclusive) and bound (exclusive).
563       *
564       * @param origin the least value returned
565 <     * @param bound the upper bound
565 >     * @param bound the upper bound (exclusive)
566       * @return a pseudorandom {@code double} value between the origin
567       *         (inclusive) and the bound (exclusive)
568       * @throws IllegalArgumentException if {@code origin} is greater than
# Line 594 | Line 623 | public class SplittableRandom {
623  
624      /**
625       * Returns a stream producing the given {@code streamSize} number
626 <     * of pseudorandom {@code int} values, each conforming to the
627 <     * given origin and bound.
626 >     * of pseudorandom {@code int} values from this generator and/or one split
627 >     * from it; each value conforms to the given origin (inclusive) and bound
628 >     * (exclusive).
629       *
630       * @param streamSize the number of values to generate
631 <     * @param randomNumberOrigin the origin of each random value
632 <     * @param randomNumberBound the bound of each random value
631 >     * @param randomNumberOrigin the origin (inclusive) of each random value
632 >     * @param randomNumberBound the bound (exclusive) of each random value
633       * @return a stream of pseudorandom {@code int} values,
634 <     *         each with the given origin and bound
634 >     *         each with the given origin (inclusive) and bound (exclusive)
635       * @throws IllegalArgumentException if {@code streamSize} is
636       *         less than zero, or {@code randomNumberOrigin}
637       *         is greater than or equal to {@code randomNumberBound}
# Line 620 | Line 650 | public class SplittableRandom {
650  
651      /**
652       * Returns an effectively unlimited stream of pseudorandom {@code
653 <     * int} values, each conforming to the given origin and bound.
653 >     * int} values from this generator and/or one split from it; each value
654 >     * conforms to the given origin (inclusive) and bound (exclusive).
655       *
656       * @implNote This method is implemented to be equivalent to {@code
657       * ints(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}.
658       *
659 <     * @param randomNumberOrigin the origin of each random value
660 <     * @param randomNumberBound the bound of each random value
659 >     * @param randomNumberOrigin the origin (inclusive) of each random value
660 >     * @param randomNumberBound the bound (exclusive) of each random value
661       * @return a stream of pseudorandom {@code int} values,
662 <     *         each with the given origin and bound
662 >     *         each with the given origin (inclusive) and bound (exclusive)
663       * @throws IllegalArgumentException if {@code randomNumberOrigin}
664       *         is greater than or equal to {@code randomNumberBound}
665       */
# Line 678 | Line 709 | public class SplittableRandom {
709  
710      /**
711       * Returns a stream producing the given {@code streamSize} number of
712 <     * pseudorandom {@code long} values, each conforming to the
713 <     * given origin and bound.
712 >     * pseudorandom {@code long} values from this generator and/or one split
713 >     * from it; each value conforms to the given origin (inclusive) and bound
714 >     * (exclusive).
715       *
716       * @param streamSize the number of values to generate
717 <     * @param randomNumberOrigin the origin of each random value
718 <     * @param randomNumberBound the bound of each random value
717 >     * @param randomNumberOrigin the origin (inclusive) of each random value
718 >     * @param randomNumberBound the bound (exclusive) of each random value
719       * @return a stream of pseudorandom {@code long} values,
720 <     *         each with the given origin and bound
720 >     *         each with the given origin (inclusive) and bound (exclusive)
721       * @throws IllegalArgumentException if {@code streamSize} is
722       *         less than zero, or {@code randomNumberOrigin}
723       *         is greater than or equal to {@code randomNumberBound}
# Line 704 | Line 736 | public class SplittableRandom {
736  
737      /**
738       * Returns an effectively unlimited stream of pseudorandom {@code
739 <     * long} values, each conforming to the given origin and bound.
739 >     * long} values from this generator and/or one split from it; each value
740 >     * conforms to the given origin (inclusive) and bound (exclusive).
741       *
742       * @implNote This method is implemented to be equivalent to {@code
743       * longs(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}.
744       *
745 <     * @param randomNumberOrigin the origin of each random value
746 <     * @param randomNumberBound the bound of each random value
745 >     * @param randomNumberOrigin the origin (inclusive) of each random value
746 >     * @param randomNumberBound the bound (exclusive) of each random value
747       * @return a stream of pseudorandom {@code long} values,
748 <     *         each with the given origin and bound
748 >     *         each with the given origin (inclusive) and bound (exclusive)
749       * @throws IllegalArgumentException if {@code randomNumberOrigin}
750       *         is greater than or equal to {@code randomNumberBound}
751       */
# Line 727 | Line 760 | public class SplittableRandom {
760  
761      /**
762       * Returns a stream producing the given {@code streamSize} number of
763 <     * pseudorandom {@code double} values, each between zero
764 <     * (inclusive) and one (exclusive).
763 >     * pseudorandom {@code double} values from this generator and/or one split
764 >     * from it; each value is between zero (inclusive) and one (exclusive).
765       *
766       * @param streamSize the number of values to generate
767       * @return a stream of {@code double} values
# Line 746 | Line 779 | public class SplittableRandom {
779  
780      /**
781       * Returns an effectively unlimited stream of pseudorandom {@code
782 <     * double} values, each between zero (inclusive) and one
783 <     * (exclusive).
782 >     * double} values from this generator and/or one split from it; each value
783 >     * is between zero (inclusive) and one (exclusive).
784       *
785       * @implNote This method is implemented to be equivalent to {@code
786       * doubles(Long.MAX_VALUE)}.
# Line 763 | Line 796 | public class SplittableRandom {
796  
797      /**
798       * Returns a stream producing the given {@code streamSize} number of
799 <     * pseudorandom {@code double} values, each conforming to the
800 <     * given origin and bound.
799 >     * pseudorandom {@code double} values from this generator and/or one split
800 >     * from it; each value conforms to the given origin (inclusive) and bound
801 >     * (exclusive).
802       *
803       * @param streamSize the number of values to generate
804 <     * @param randomNumberOrigin the origin of each random value
805 <     * @param randomNumberBound the bound of each random value
804 >     * @param randomNumberOrigin the origin (inclusive) of each random value
805 >     * @param randomNumberBound the bound (exclusive) of each random value
806       * @return a stream of pseudorandom {@code double} values,
807 <     * each with the given origin and bound
807 >     *         each with the given origin (inclusive) and bound (exclusive)
808       * @throws IllegalArgumentException if {@code streamSize} is
809 <     * less than zero
809 >     *         less than zero
810       * @throws IllegalArgumentException if {@code randomNumberOrigin}
811       *         is greater than or equal to {@code randomNumberBound}
812       */
# Line 790 | Line 824 | public class SplittableRandom {
824  
825      /**
826       * Returns an effectively unlimited stream of pseudorandom {@code
827 <     * double} values, each conforming to the given origin and bound.
827 >     * double} values from this generator and/or one split from it; each value
828 >     * conforms to the given origin (inclusive) and bound (exclusive).
829       *
830       * @implNote This method is implemented to be equivalent to {@code
831       * doubles(Long.MAX_VALUE, randomNumberOrigin, randomNumberBound)}.
832       *
833 <     * @param randomNumberOrigin the origin of each random value
834 <     * @param randomNumberBound the bound of each random value
833 >     * @param randomNumberOrigin the origin (inclusive) of each random value
834 >     * @param randomNumberBound the bound (exclusive) of each random value
835       * @return a stream of pseudorandom {@code double} values,
836 <     * each with the given origin and bound
836 >     *         each with the given origin (inclusive) and bound (exclusive)
837       * @throws IllegalArgumentException if {@code randomNumberOrigin}
838       *         is greater than or equal to {@code randomNumberBound}
839       */

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines