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.17 by jsr166, Tue Aug 13 23:34:47 2013 UTC vs.
Revision 1.22 by dl, Fri Sep 20 09:38:07 2013 UTC

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

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines