[cvs] / jsr166 / src / main / java / util / SplittableRandom.java Repository:
ViewVC logotype

Diff of /jsr166/src/main/java/util/SplittableRandom.java

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.20, Sat Aug 24 06:20:15 2013 UTC revision 1.21, Thu Sep 19 23:19:43 2013 UTC
# Line 26  Line 26 
26  package java.util;  package java.util;
27    
28  import java.security.SecureRandom;  import java.security.SecureRandom;
29  import java.net.InetAddress;  import java.net.NetworkInterface;
30    import java.util.Enumeration;
31  import java.util.concurrent.atomic.AtomicLong;  import java.util.concurrent.atomic.AtomicLong;
32  import java.util.function.IntConsumer;  import java.util.function.IntConsumer;
33  import java.util.function.LongConsumer;  import java.util.function.LongConsumer;
# Line 108  Line 109 
109       * Methods nextLong, nextInt, and derivatives do not return the       * Methods nextLong, nextInt, and derivatives do not return the
110       * sequence (seed) values, but instead a hash-like bit-mix of       * sequence (seed) values, but instead a hash-like bit-mix of
111       * their bits, producing more independently distributed sequences.       * their bits, producing more independently distributed sequences.
112       * For nextLong, the mix64 bit-mixing function computes the same       * For nextLong, the mix64 function is based on David Stafford's
113       * value as the "64-bit finalizer" function in Austin Appleby's       * (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html)
114       * MurmurHash3 algorithm.  See       * "Mix13" variant of the "64-bit finalizer" function in Austin
115       * http://code.google.com/p/smhasher/wiki/MurmurHash3 , which       * Appleby's MurmurHash3 algorithm See
116       * comments: "The constants for the finalizers were generated by a       * http://code.google.com/p/smhasher/wiki/MurmurHash3 . The mix32
117       * simple simulated-annealing algorithm, and both avalanche all       * function is based on Stafford's Mix04 mix function, but returns
118       * bits of 'h' to within 0.25% bias." The mix32 function is       * the upper 32 bits cast as int.
      * equivalent to (int)(mix64(seed) >>> 32), but faster because it  
      * omits a step that doesn't contribute to result.  
119       *       *
120       * The split operation uses the current generator to form the seed       * The split operation uses the current generator to form the seed
121       * and gamma for another SplittableRandom.  To conservatively       * and gamma for another SplittableRandom.  To conservatively
122       * avoid potential correlations between seed and value generation,       * avoid potential correlations between seed and value generation,
123       * gamma selection (method nextGamma) uses the "Mix13" constants       * gamma selection (method mixGamma) uses different
124       * for MurmurHash3 described by David Stafford       * (Murmurhash3's) mix constants.  To avoid potential weaknesses
125       * (http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html)       * in bit-mixing transformations, we restrict gammas to odd values
126       * To avoid potential weaknesses in bit-mixing transformations, we       * with at least 24 0-1 or 1-0 bit transitions.  Rather than
127       * restrict gammas to odd values with at least 12 and no more than       * rejecting candidates with too few or too many bits set, method
128       * 52 bits set.  Rather than rejecting candidates with too few or       * mixGamma flips some bits (which has the effect of mapping at
129       * too many bits set, method nextGamma flips some bits (which has       * most 4 to any given gamma value).  This reduces the effective
130       * the effect of mapping at most 4 to any given gamma value).       * set of 64bit odd gamma values by about 2%, and serves as an
      * This reduces the effective set of 64bit odd gamma values by  
      * about 2<sup>14</sup>, a very tiny percentage, and serves as an  
131       * automated screening for sequence constant selection that is       * automated screening for sequence constant selection that is
132       * left as an empirical decision in some other hashing and crypto       * left as an empirical decision in some other hashing and crypto
133       * algorithms.       * algorithms.
# Line 141  Line 138 
138       * avalanching.       * avalanching.
139       *       *
140       * The default (no-argument) constructor, in essence, invokes       * The default (no-argument) constructor, in essence, invokes
141       * split() for a common "seeder" SplittableRandom.  Unlike other       * split() for a common "defaultGen" SplittableRandom.  Unlike
142       * cases, this split must be performed in a thread-safe manner, so       * other cases, this split must be performed in a thread-safe
143       * we use an AtomicLong to represent the seed rather than use an       * manner, so we use an AtomicLong to represent the seed rather
144       * explicit SplittableRandom. To bootstrap the seeder, we start       * than use an explicit SplittableRandom. To bootstrap the
145       * off using a seed based on current time and host unless the       * defaultGen, we start off using a seed based on current time and
146       * java.util.secureRandomSeed property is set. This serves as a       * network interface address unless the java.util.secureRandomSeed
147       * slimmed-down (and insecure) variant of SecureRandom that also       * property is set. This serves as a slimmed-down (and insecure)
148       * avoids stalls that may occur when using /dev/random.       * 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       * It is a relatively simple matter to apply the basic design here
152       * to use 128 bit seeds. However, emulating 128bit arithmetic and       * to use 128 bit seeds. However, emulating 128bit arithmetic and
# Line 161  Line 159 
159       */       */
160    
161      /**      /**
162       * The initial gamma value for (unsplit) SplittableRandoms. Must       * The golden ratio scaled to 64bits, used as the initial gamma
163       * be odd with at least 12 and no more than 52 bits set. Currently       * value for (unsplit) SplittableRandoms.
      * set to the golden ratio scaled to 64bits.  
164       */       */
165      private static final long INITIAL_GAMMA = 0x9e3779b97f4a7c15L;      private static final long GOLDEN_GAMMA = 0x9e3779b97f4a7c15L;
166    
167      /**      /**
168       * The least non-zero value returned by nextDouble(). This value       * The least non-zero value returned by nextDouble(). This value
169       * is scaled by a random value of 53 bits to produce a result.       * 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);      private static final double DOUBLE_ULP = 1.0 / (1L << 53);
172    
173      /**      /**
174       * The seed. Updated only via method nextSeed.       * The seed. Updated only via method nextSeed.
# Line 192  Line 189 
189      }      }
190    
191      /**      /**
192       * Computes MurmurHash3 64bit mix function.       * Computes Stafford variant 13 of 64bit mix function.
193       */       */
194      private static long mix64(long z) {      private static long mix64(long z) {
195          z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;          z *= 0xbf58476d1ce4e5b9L;
196          z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L;          z = (z ^ (z >>> 32)) * 0x94d049bb133111ebL;
197          return z ^ (z >>> 33);          return z ^ (z >>> 32);
198        }
199    
200        private static long xmix64(long z) {
201            z *= 0xbf58476d1ce4e5b9L;
202            z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL;
203            return z ^ (z >>> 31);
204      }      }
205    
206      /**      /**
207       * Returns the 32 high bits of mix64(z) as int.       * Returns the 32 high bits of Stafford variant 4 mix64 function as int.
208       */       */
209      private static int mix32(long z) {      private static int mix32(long z) {
210          z = (z ^ (z >>> 33)) * 0xff51afd7ed558ccdL;          z *= 0x62a9d9ed799705f5L;
211          return (int)(((z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L) >>> 32);          return (int)(((z ^ (z >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32);
212      }      }
213    
214      /**      /**
215       * Returns the gamma value to use for a new split instance.       * Returns the gamma value to use for a new split instance.
216       */       */
217      private static long nextGamma(long z) {      private static long mixGamma(long z) {
218          z = (z ^ (z >>> 30)) * 0xbf58476d1ce4e5b9L; // Stafford "Mix13"          z *= 0xff51afd7ed558ccdL;                   // MurmurHash3 mix constants
219          z = (z ^ (z >>> 27)) * 0x94d049bb133111ebL;          z = (z ^ (z >>> 33)) * 0xc4ceb9fe1a85ec53L;
220          z = (z ^ (z >>> 31)) | 1L; // force to be odd          z = (z ^ (z >>> 33)) | 1L;                  // force to be odd
221          int n = Long.bitCount(z);  // ensure enough 0 and 1 bits          int n = Long.bitCount(z ^ (z >>> 1));       // ensure enough transitions
222          return (n < 12 || n > 52) ? z ^ 0xaaaaaaaaaaaaaaaaL : z;          return (n < 24) ? z ^ 0xaaaaaaaaaaaaaaaaL : z;
223      }      }
224    
225      /**      /**
# Line 229  Line 232 
232      /**      /**
233       * The seed generator for default constructors.       * The seed generator for default constructors.
234       */       */
235      private static final AtomicLong seeder = new AtomicLong(initialSeed());      private static final AtomicLong defaultGen = new AtomicLong(initialSeed());
236    
237      private static long initialSeed() {      private static long initialSeed() {
238          try {  // ignore exceptions in accessing/parsing properties          String pp = java.security.AccessController.doPrivileged(
239              String pp = System.getProperty                  new sun.security.action.GetPropertyAction(
240                  ("java.util.secureRandomSeed");                          "java.util.secureRandomSeed"));
241              if (pp != null && pp.equalsIgnoreCase("true")) {              if (pp != null && pp.equalsIgnoreCase("true")) {
242                  byte[] seedBytes = java.security.SecureRandom.getSeed(8);                  byte[] seedBytes = java.security.SecureRandom.getSeed(8);
243                  long s = (long)(seedBytes[0]) & 0xffL;                  long s = (long)(seedBytes[0]) & 0xffL;
# Line 242  Line 245 
245                      s = (s << 8) | ((long)(seedBytes[i]) & 0xffL);                      s = (s << 8) | ((long)(seedBytes[i]) & 0xffL);
246                  return s;                  return s;
247              }              }
248          } catch (Exception ignore) {          long h = 0L;
         }  
         int hh = 0; // hashed host address  
249          try {          try {
250              hh = InetAddress.getLocalHost().hashCode();              Enumeration<NetworkInterface> ifcs =
251                    NetworkInterface.getNetworkInterfaces();
252                boolean retry = false; // retry once if getHardwareAddress is null
253                while (ifcs.hasMoreElements()) {
254                    NetworkInterface ifc = ifcs.nextElement();
255                    if (!ifc.isVirtual()) { // skip fake addresses
256                        byte[] bs = ifc.getHardwareAddress();
257                        if (bs != null) {
258                            int n = bs.length;
259                            int m = Math.min(n >>> 1, 4);
260                            for (int i = 0; i < m; ++i)
261                                h = (h << 16) ^ (bs[i] << 8) ^ bs[n-1-i];
262                            if (m < 4)
263                                h = (h << 8) ^ bs[n-1-m];
264                            h = mix64(h);
265                            break;
266                        }
267                        else if (!retry)
268                            retry = true;
269                        else
270                            break;
271                    }
272                }
273          } catch (Exception ignore) {          } catch (Exception ignore) {
274          }          }
275          return (mix64((((long)hh) << 32) ^ System.currentTimeMillis()) ^          return (h ^ mix64(System.currentTimeMillis()) ^
276                  mix64(System.nanoTime()));                  mix64(System.nanoTime()));
277      }      }
278    
# Line 358  Line 381 
381       * @return a pseudorandom value       * @return a pseudorandom value
382       */       */
383      final double internalNextDouble(double origin, double bound) {      final double internalNextDouble(double origin, double bound) {
384          double r = (nextLong() >>> 11) * DOUBLE_UNIT;          double r = (nextLong() >>> 11) * DOUBLE_ULP;
385          if (origin < bound) {          if (origin < bound) {
386              r = r * (bound - origin) + origin;              r = r * (bound - origin) + origin;
387              if (r >= bound) // correct for rounding              if (r >= bound) // correct for rounding
# Line 377  Line 400 
400       * @param seed the initial seed       * @param seed the initial seed
401       */       */
402      public SplittableRandom(long seed) {      public SplittableRandom(long seed) {
403          this(seed, INITIAL_GAMMA);          this(seed, GOLDEN_GAMMA);
404      }      }
405    
406      /**      /**
# Line 386  Line 409 
409       * of those of any other instances in the current program; and       * of those of any other instances in the current program; and
410       * may, and typically does, vary across program invocations.       * may, and typically does, vary across program invocations.
411       */       */
412      public SplittableRandom() { // emulate seeder.split()      public SplittableRandom() { // emulate defaultGen.split()
413          this.gamma = nextGamma(this.seed = seeder.addAndGet(INITIAL_GAMMA));          long s = defaultGen.getAndAdd(2*GOLDEN_GAMMA);
414            this.seed = mix64(s);
415            this.gamma = mixGamma(s + GOLDEN_GAMMA);
416      }      }
417    
418      /**      /**
# Line 405  Line 430 
430       * @return the new SplittableRandom instance       * @return the new SplittableRandom instance
431       */       */
432      public SplittableRandom split() {      public SplittableRandom split() {
433          long s = nextSeed();          return new SplittableRandom(nextLong(), mixGamma(nextSeed()));
         return new SplittableRandom(s, nextGamma(s));  
434      }      }
435    
436      /**      /**
# Line 521  Line 545 
545       *         (inclusive) and one (exclusive)       *         (inclusive) and one (exclusive)
546       */       */
547      public double nextDouble() {      public double nextDouble() {
548          return (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT;          return (mix64(nextSeed()) >>> 11) * DOUBLE_ULP;
549      }      }
550    
551      /**      /**
# Line 536  Line 560 
560      public double nextDouble(double bound) {      public double nextDouble(double bound) {
561          if (!(bound > 0.0))          if (!(bound > 0.0))
562              throw new IllegalArgumentException(BadBound);              throw new IllegalArgumentException(BadBound);
563          double result = (mix64(nextSeed()) >>> 11) * DOUBLE_UNIT * bound;          double result = (mix64(nextSeed()) >>> 11) * DOUBLE_ULP * bound;
564          return (result < bound) ?  result : // correct for rounding          return (result < bound) ?  result : // correct for rounding
565              Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1);              Double.longBitsToDouble(Double.doubleToLongBits(bound) - 1);
566      }      }

Legend:
Removed from v.1.20  
changed lines
  Added in v.1.21

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8