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