1 // Copyright 2013 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_ 6 #define V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_ 7 8 #include <unordered_set> 9 #include <vector> 10 11 #include "src/base/base-export.h" 12 #include "src/base/macros.h" 13 14 namespace v8 { 15 namespace base { 16 17 // ----------------------------------------------------------------------------- 18 // RandomNumberGenerator 19 20 // This class is used to generate a stream of pseudo-random numbers. The class 21 // uses a 64-bit seed, which is passed through MurmurHash3 to create two 64-bit 22 // state values. This pair of state values is then used in xorshift128+. 23 // The resulting stream of pseudo-random numbers has a period length of 2^128-1. 24 // See Marsaglia: http://www.jstatsoft.org/v08/i14/paper 25 // And Vigna: http://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf 26 // NOTE: Any changes to the algorithm must be tested against TestU01. 27 // Please find instructions for this in the internal repository. 28 29 // If two instances of RandomNumberGenerator are created with the same seed, and 30 // the same sequence of method calls is made for each, they will generate and 31 // return identical sequences of numbers. 32 // This class uses (probably) weak entropy by default, but it's sufficient, 33 // because it is the responsibility of the embedder to install an entropy source 34 // using v8::V8::SetEntropySource(), which provides reasonable entropy, see: 35 // https://code.google.com/p/v8/issues/detail?id=2905 36 // This class is neither reentrant nor threadsafe. 37 38 class V8_BASE_EXPORT RandomNumberGenerator final { 39 public: 40 // EntropySource is used as a callback function when V8 needs a source of 41 // entropy. 42 using EntropySource = bool (*)(unsigned char* buffer, size_t buflen); 43 static void SetEntropySource(EntropySource entropy_source); 44 45 RandomNumberGenerator(); RandomNumberGenerator(int64_t seed)46 explicit RandomNumberGenerator(int64_t seed) { SetSeed(seed); } 47 48 // Returns the next pseudorandom, uniformly distributed int value from this 49 // random number generator's sequence. The general contract of |NextInt()| is 50 // that one int value is pseudorandomly generated and returned. 51 // All 2^32 possible integer values are produced with (approximately) equal 52 // probability. NextInt()53 V8_INLINE int NextInt() V8_WARN_UNUSED_RESULT { return Next(32); } 54 55 // Returns a pseudorandom, uniformly distributed int value between 0 56 // (inclusive) and the specified max value (exclusive), drawn from this random 57 // number generator's sequence. The general contract of |NextInt(int)| is that 58 // one int value in the specified range is pseudorandomly generated and 59 // returned. All max possible int values are produced with (approximately) 60 // equal probability. 61 int NextInt(int max) V8_WARN_UNUSED_RESULT; 62 63 // Returns the next pseudorandom, uniformly distributed boolean value from 64 // this random number generator's sequence. The general contract of 65 // |NextBoolean()| is that one boolean value is pseudorandomly generated and 66 // returned. The values true and false are produced with (approximately) equal 67 // probability. NextBool()68 V8_INLINE bool NextBool() V8_WARN_UNUSED_RESULT { return Next(1) != 0; } 69 70 // Returns the next pseudorandom, uniformly distributed double value between 71 // 0.0 and 1.0 from this random number generator's sequence. 72 // The general contract of |NextDouble()| is that one double value, chosen 73 // (approximately) uniformly from the range 0.0 (inclusive) to 1.0 74 // (exclusive), is pseudorandomly generated and returned. 75 double NextDouble() V8_WARN_UNUSED_RESULT; 76 77 // Returns the next pseudorandom, uniformly distributed int64 value from this 78 // random number generator's sequence. The general contract of |NextInt64()| 79 // is that one 64-bit int value is pseudorandomly generated and returned. 80 // All 2^64 possible integer values are produced with (approximately) equal 81 // probability. 82 int64_t NextInt64() V8_WARN_UNUSED_RESULT; 83 84 // Fills the elements of a specified array of bytes with random numbers. 85 void NextBytes(void* buffer, size_t buflen); 86 87 // Returns the next pseudorandom set of n unique uint64 values smaller than 88 // max. 89 // n must be less or equal to max. 90 std::vector<uint64_t> NextSample(uint64_t max, 91 size_t n) V8_WARN_UNUSED_RESULT; 92 93 // Returns the next pseudorandom set of n unique uint64 values smaller than 94 // max. 95 // n must be less or equal to max. 96 // max - |excluded| must be less or equal to n. 97 // 98 // Generates list of all possible values and removes random values from it 99 // until size reaches n. 100 std::vector<uint64_t> NextSampleSlow( 101 uint64_t max, size_t n, 102 const std::unordered_set<uint64_t>& excluded = 103 std::unordered_set<uint64_t>{}) V8_WARN_UNUSED_RESULT; 104 105 // Override the current ssed. 106 void SetSeed(int64_t seed); 107 initial_seed()108 int64_t initial_seed() const { return initial_seed_; } 109 110 // Static and exposed for external use. ToDouble(uint64_t state0)111 static inline double ToDouble(uint64_t state0) { 112 // Exponent for double values for [1.0 .. 2.0) 113 static const uint64_t kExponentBits = uint64_t{0x3FF0000000000000}; 114 uint64_t random = (state0 >> 12) | kExponentBits; 115 return bit_cast<double>(random) - 1; 116 } 117 118 // Static and exposed for external use. XorShift128(uint64_t * state0,uint64_t * state1)119 static inline void XorShift128(uint64_t* state0, uint64_t* state1) { 120 uint64_t s1 = *state0; 121 uint64_t s0 = *state1; 122 *state0 = s0; 123 s1 ^= s1 << 23; 124 s1 ^= s1 >> 17; 125 s1 ^= s0; 126 s1 ^= s0 >> 26; 127 *state1 = s1; 128 } 129 130 static uint64_t MurmurHash3(uint64_t); 131 132 private: 133 static const int64_t kMultiplier = 0x5'deec'e66d; 134 static const int64_t kAddend = 0xb; 135 static const int64_t kMask = 0xffff'ffff'ffff; 136 137 int Next(int bits) V8_WARN_UNUSED_RESULT; 138 139 int64_t initial_seed_; 140 uint64_t state0_; 141 uint64_t state1_; 142 }; 143 144 } // namespace base 145 } // namespace v8 146 147 #endif // V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_ 148