tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

XorShift128PlusRNG.h (4402B)

      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