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(); |

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. |

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. |

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 | |

108 | int64_t initial_seed() const { return initial_seed_; } |

109 | |

110 | // Static and exposed for external use. |

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. |

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 = V8_2PART_UINT64_C(0x5, deece66d); |

134 | static const int64_t kAddend = 0xb; |

135 | static const int64_t kMask = V8_2PART_UINT64_C(0xffff, ffffffff); |

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 |