Line data Source code
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();
43 60781 : 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.
50 : V8_INLINE int NextInt() WARN_UNUSED_RESULT {
51 13963277 : 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.
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 :
91 : int64_t initial_seed() const { return initial_seed_; }
92 :
93 : // Static and exposed for external use.
94 33807360 : 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 33940467 : uint64_t random = ((state0 + state1) & kMantissaMask) | kExponentBits;
99 33940467 : return bit_cast<double>(random) - 1;
100 : }
101 :
102 : // Static and exposed for external use.
103 33807360 : static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
104 709400375 : uint64_t s1 = *state0;
105 709400375 : uint64_t s0 = *state1;
106 709400375 : *state0 = s0;
107 709400375 : s1 ^= s1 << 23;
108 709400375 : s1 ^= s1 >> 17;
109 709400375 : s1 ^= s0;
110 709400375 : s1 ^= s0 >> 26;
111 709400375 : *state1 = s1;
112 33807360 : }
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_
|
