V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
random-number-generator.h
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  typedef bool (*EntropySource)(unsigned char* buffer, size_t buflen);
43  static void SetEntropySource(EntropySource entropy_source);
44 
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_
Definition: libplatform.h:13