mfbt/XorShift128PlusRNG.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* The xorshift128+ pseudo-random number generator. */
   8
   9 #ifndef mozilla_XorShift128Plus_h
  10 #define mozilla_XorShift128Plus_h
  11
  12 #include "mozilla/Assertions.h"
  13 #include "mozilla/Attributes.h"
  14 #include "mozilla/FloatingPoint.h"
  15
  16 #include <inttypes.h>
  17
  18 namespace mozilla {
  19 namespace non_crypto {
  20
  21 /*
  22  * A stream of pseudo-random numbers generated using the xorshift+ technique
  23  * described here:
  24  *
  25  * Vigna, Sebastiano (2014). "Further scramblings of Marsaglia's xorshift
  26  * generators". arXiv:1404.0390 (http://arxiv.org/abs/1404.0390)
  27  *
  28  * That paper says:
  29  *
  30  *     In particular, we propose a tightly coded xorshift128+ generator that
  31  *     does not fail systematically any test from the BigCrush suite of TestU01
  32  *     (even reversed) and generates 64 pseudorandom bits in 1.10 ns on an
  33  *     Intel(R) Core(TM) i7-4770 CPU @3.40GHz (Haswell). It is the fastest
  34  *     generator we are aware of with such empirical statistical properties.
  35  *
  36  * The stream of numbers produced by this method repeats every 2**128 - 1 calls
  37  * (i.e. never, for all practical purposes). Zero appears 2**64 - 1 times in
  38  * this period; all other numbers appear 2**64 times. Additionally, each *bit*
  39  * in the produced numbers repeats every 2**128 - 1 calls.
  40  *
  41  * This generator is not suitable as a cryptographically secure random number
  42  * generator.
  43  */
  44 class XorShift128PlusRNG {
  45   uint64_t mState[2];
  46
  47  public:
  48   /*
  49    * Construct a xorshift128+ pseudo-random number stream using |aInitial0| and
  50    * |aInitial1| as the initial state.  These MUST NOT both be zero.
  51    *
  52    * If the initial states contain many zeros, for a few iterations you'll see
  53    * many zeroes in the generated numbers.  It's suggested to seed a SplitMix64
  54    * generator <http://xorshift.di.unimi.it/splitmix64.c> and use its first two
  55    * outputs to seed xorshift128+.
  56    */
  57   XorShift128PlusRNG(uint64_t aInitial0, uint64_t aInitial1) {
  58     setState(aInitial0, aInitial1);
  59   }
  60
  61   /**
  62    * Return a pseudo-random 64-bit number.
  63    */
  64   MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
  65   uint64_t next() {
  66     /*
  67      * The offsetOfState*() methods below are provided so that exceedingly-rare
  68      * callers that want to observe or poke at RNG state in C++ type-system-
  69      * ignoring means can do so. Don't change the next() or nextDouble()
  70      * algorithms without altering code that uses offsetOfState*()!
  71      */
  72     uint64_t s1 = mState[0];
  73     const uint64_t s0 = mState[1];
  74     mState[0] = s0;
  75     s1 ^= s1 << 23;
  76     mState[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26);
  77     return mState[1] + s0;
  78   }
  79
  80   /*
  81    * Return a pseudo-random floating-point value in the range [0, 1). More
  82    * precisely, choose an integer in the range [0, 2**53) and divide it by
  83    * 2**53. Given the 2**128 - 1 period noted above, the produced doubles are
  84    * all but uniformly distributed in this range.
  85    */
  86   double nextDouble() {
  87     /*
  88      * Because the IEEE 64-bit floating point format stores the leading '1' bit
  89      * of the mantissa implicitly, it effectively represents a mantissa in the
  90      * range [0, 2**53) in only 52 bits. FloatingPoint<double>::kExponentShift
  91      * is the width of the bitfield in the in-memory format, so we must add one
  92      * to get the mantissa's range.
  93      */
  94     static constexpr int kMantissaBits =
  95       mozilla::FloatingPoint<double>::kExponentShift + 1;
  96     uint64_t mantissa = next() & ((UINT64_C(1) << kMantissaBits) - 1);
  97     return double(mantissa) / (UINT64_C(1) << kMantissaBits);
  98   }
  99
 100   /*
 101    * Set the stream's current state to |aState0| and |aState1|. These must not
 102    * both be zero; ideally, they should have an almost even mix of zero and one
 103    * bits.
 104    */
 105   void setState(uint64_t aState0, uint64_t aState1) {
 106     MOZ_ASSERT(aState0 || aState1);
 107     mState[0] = aState0;
 108     mState[1] = aState1;
 109   }
 110
 111   static size_t offsetOfState0() {
 112     return offsetof(XorShift128PlusRNG, mState[0]);
 113   }
 114   static size_t offsetOfState1() {
 115     return offsetof(XorShift128PlusRNG, mState[1]);
 116   }
 117 };
 118
 119 } // namespace non_crypto
 120 } // namespace mozilla
 121
 122 #endif // mozilla_XorShift128Plus_h