/work/obj-fuzz/dist/include/mozilla/XorShift128PlusRNG.h
Line | Count | Source (jump to first uncovered line) |
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 | 27 | XorShift128PlusRNG(uint64_t aInitial0, uint64_t aInitial1) { |
58 | 27 | setState(aInitial0, aInitial1); |
59 | 27 | } |
60 | | |
61 | | /** |
62 | | * Return a pseudo-random 64-bit number. |
63 | | */ |
64 | | MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW |
65 | 76 | uint64_t next() { |
66 | 76 | /* |
67 | 76 | * The offsetOfState*() methods below are provided so that exceedingly-rare |
68 | 76 | * callers that want to observe or poke at RNG state in C++ type-system- |
69 | 76 | * ignoring means can do so. Don't change the next() or nextDouble() |
70 | 76 | * algorithms without altering code that uses offsetOfState*()! |
71 | 76 | */ |
72 | 76 | uint64_t s1 = mState[0]; |
73 | 76 | const uint64_t s0 = mState[1]; |
74 | 76 | mState[0] = s0; |
75 | 76 | s1 ^= s1 << 23; |
76 | 76 | mState[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26); |
77 | 76 | return mState[1] + s0; |
78 | 76 | } |
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 | 0 | double nextDouble() { |
87 | 0 | /* |
88 | 0 | * Because the IEEE 64-bit floating point format stores the leading '1' bit |
89 | 0 | * of the mantissa implicitly, it effectively represents a mantissa in the |
90 | 0 | * range [0, 2**53) in only 52 bits. FloatingPoint<double>::kExponentShift |
91 | 0 | * is the width of the bitfield in the in-memory format, so we must add one |
92 | 0 | * to get the mantissa's range. |
93 | 0 | */ |
94 | 0 | static constexpr int kMantissaBits = |
95 | 0 | mozilla::FloatingPoint<double>::kExponentShift + 1; |
96 | 0 | uint64_t mantissa = next() & ((UINT64_C(1) << kMantissaBits) - 1); |
97 | 0 | return double(mantissa) / (UINT64_C(1) << kMantissaBits); |
98 | 0 | } |
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 | 27 | void setState(uint64_t aState0, uint64_t aState1) { |
106 | 27 | MOZ_ASSERT(aState0 || aState1); |
107 | 27 | mState[0] = aState0; |
108 | 27 | mState[1] = aState1; |
109 | 27 | } |
110 | | |
111 | 0 | static size_t offsetOfState0() { |
112 | 0 | return offsetof(XorShift128PlusRNG, mState[0]); |
113 | 0 | } |
114 | 0 | static size_t offsetOfState1() { |
115 | 0 | return offsetof(XorShift128PlusRNG, mState[1]); |
116 | 0 | } |
117 | | }; |
118 | | |
119 | | } // namespace non_crypto |
120 | | } // namespace mozilla |
121 | | |
122 | | #endif // mozilla_XorShift128Plus_h |