Line data Source code
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 647 : XorShift128PlusRNG(uint64_t aInitial0, uint64_t aInitial1) {
58 647 : setState(aInitial0, aInitial1);
59 647 : }
60 :
61 : /**
62 : * Return a pseudo-random 64-bit number.
63 : */
64 1652 : uint64_t next() {
65 : /*
66 : * The offsetOfState*() methods below are provided so that exceedingly-rare
67 : * callers that want to observe or poke at RNG state in C++ type-system-
68 : * ignoring means can do so. Don't change the next() or nextDouble()
69 : * algorithms without altering code that uses offsetOfState*()!
70 : */
71 1652 : uint64_t s1 = mState[0];
72 1652 : const uint64_t s0 = mState[1];
73 1652 : mState[0] = s0;
74 1652 : s1 ^= s1 << 23;
75 1652 : mState[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26);
76 1652 : return mState[1] + s0;
77 : }
78 :
79 : /*
80 : * Return a pseudo-random floating-point value in the range [0, 1). More
81 : * precisely, choose an integer in the range [0, 2**53) and divide it by
82 : * 2**53. Given the 2**128 - 1 period noted above, the produced doubles are
83 : * all but uniformly distributed in this range.
84 : */
85 7 : double nextDouble() {
86 : /*
87 : * Because the IEEE 64-bit floating point format stores the leading '1' bit
88 : * of the mantissa implicitly, it effectively represents a mantissa in the
89 : * range [0, 2**53) in only 52 bits. FloatingPoint<double>::kExponentShift
90 : * is the width of the bitfield in the in-memory format, so we must add one
91 : * to get the mantissa's range.
92 : */
93 : static constexpr int kMantissaBits =
94 : mozilla::FloatingPoint<double>::kExponentShift + 1;
95 7 : uint64_t mantissa = next() & ((UINT64_C(1) << kMantissaBits) - 1);
96 7 : return double(mantissa) / (UINT64_C(1) << kMantissaBits);
97 : }
98 :
99 : /*
100 : * Set the stream's current state to |aState0| and |aState1|. These must not
101 : * both be zero; ideally, they should have an almost even mix of zero and one
102 : * bits.
103 : */
104 647 : void setState(uint64_t aState0, uint64_t aState1) {
105 647 : MOZ_ASSERT(aState0 || aState1);
106 647 : mState[0] = aState0;
107 647 : mState[1] = aState1;
108 647 : }
109 :
110 0 : static size_t offsetOfState0() {
111 0 : return offsetof(XorShift128PlusRNG, mState[0]);
112 : }
113 0 : static size_t offsetOfState1() {
114 0 : return offsetof(XorShift128PlusRNG, mState[1]);
115 : }
116 : };
117 :
118 : } // namespace non_crypto
119 : } // namespace mozilla
120 :
121 : #endif // mozilla_XorShift128Plus_h
|
