author | Jim Blandy <jimb@mozilla.com> |
Wed, 13 Jan 2016 12:46:40 -0800 | |
changeset 279836 | 9092fd77df19045999fb34c6db1744475c283e82 |
parent 279835 | 24e0645f9c31e717586e287adb863e5c3f68c2f3 |
child 279837 | f001a01c85d7979a9b9e44ee198587a772b06f46 |
push id | 70241 |
push user | jblandy@mozilla.com |
push date | Thu, 14 Jan 2016 00:28:10 +0000 |
treeherder | mozilla-inbound@9092fd77df19 [default view] [failures only] |
perfherder | [talos] [build metrics] [platform microbench] (compared to previous push) |
reviewers | Waldo |
bugs | 1239479 |
milestone | 46.0a1 |
first release with | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
last release without | nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
|
--- a/mfbt/XorShift128PlusRNG.h +++ b/mfbt/XorShift128PlusRNG.h @@ -28,52 +28,64 @@ namespace non_crypto { * That paper says: * * In particular, we propose a tightly coded xorshift128+ generator that * does not fail systematically any test from the BigCrush suite of TestU01 * (even reversed) and generates 64 pseudorandom bits in 1.10 ns on an * Intel(R) Core(TM) i7-4770 CPU @3.40GHz (Haswell). It is the fastest * generator we are aware of with such empirical statistical properties. * + * The stream of numbers produced by this method repeats every 2**128 - 1 calls + * (i.e. never, for all practical purposes). Zero appears 2**64 - 1 times in + * this period; all other numbers appear 2**64 times. Additionally, each *bit* + * in the produced numbers repeats every 2**128 - 1 calls. + * * This generator is not suitable as a cryptographically secure random number * generator. */ class XorShift128PlusRNG { uint64_t mState[2]; public: /* * Construct a xorshift128+ pseudo-random number stream using |aInitial0| and - * |aInitial1| as the initial state. These may not both be zero; ideally, they - * should have an almost even mix of zero and one bits. + * |aInitial1| as the initial state. These MUST NOT both be zero. + * + * If the initial states contain many zeros, for a few iterations you'll see + * many zeroes in the generated numbers. It's suggested to seed a SplitMix64 + * generator <http://xorshift.di.unimi.it/splitmix64.c> and use its first two + * outputs to seed xorshift128+. */ XorShift128PlusRNG(uint64_t aInitial0, uint64_t aInitial1) { setState(aInitial0, aInitial1); } - /* Return a pseudo-random 64-bit number. */ + /** + * Return a pseudo-random 64-bit number. + */ uint64_t next() { /* * The offsetOfState*() methods below are provided so that exceedingly-rare * callers that want to observe or poke at RNG state in C++ type-system- * ignoring means can do so. Don't change the next() or nextDouble() * algorithms without altering code that uses offsetOfState*()! */ uint64_t s1 = mState[0]; const uint64_t s0 = mState[1]; mState[0] = s0; s1 ^= s1 << 23; mState[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26); return mState[1] + s0; } /* - * Return a pseudo-random floating-point value in the range [0, 1). - * More precisely, choose an integer in the range [0, 2**53) and - * divide it by 2**53. + * Return a pseudo-random floating-point value in the range [0, 1). More + * precisely, choose an integer in the range [0, 2**53) and divide it by + * 2**53. Given the 2**128 - 1 period noted above, the produced doubles are + * all but uniformly distributed in this range. */ double nextDouble() { /* * Because the IEEE 64-bit floating point format stores the leading '1' bit * of the mantissa implicitly, it effectively represents a mantissa in the * range [0, 2**53) in only 52 bits. FloatingPoint<double>::kExponentShift * is the width of the bitfield in the in-memory format, so we must add one * to get the mantissa's range.