OLD | NEW |
1 // Copyright 2013 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_ | 5 #ifndef V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_ |
6 #define V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_ | 6 #define V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_ |
7 | 7 |
8 #include "src/base/macros.h" | 8 #include "src/base/macros.h" |
9 | 9 |
10 namespace v8 { | 10 namespace v8 { |
11 namespace base { | 11 namespace base { |
12 | 12 |
13 // ----------------------------------------------------------------------------- | 13 // ----------------------------------------------------------------------------- |
14 // RandomNumberGenerator | 14 // RandomNumberGenerator |
15 | 15 // |
16 // This class is used to generate a stream of pseudo-random numbers. The class | 16 // This class is used to generate a stream of pseudorandom numbers. The class |
17 // uses a 64-bit seed, which is passed through MurmurHash3 to create two 64-bit | 17 // uses a 48-bit seed, which is modified using a linear congruential formula. |
18 // state values. This pair of state values is then used in xorshift128+. | 18 // (See Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1.) |
19 // The resulting stream of pseudo-random numbers has a period length of 2^128-1. | |
20 // See Marsaglia: http://www.jstatsoft.org/v08/i14/paper | |
21 // And Vigna: http://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf | |
22 // NOTE: Any changes to the algorithm must be tested against TestU01. | |
23 // Please find instructions for this in the internal repository. | |
24 | |
25 // If two instances of RandomNumberGenerator are created with the same seed, and | 19 // If two instances of RandomNumberGenerator are created with the same seed, and |
26 // the same sequence of method calls is made for each, they will generate and | 20 // the same sequence of method calls is made for each, they will generate and |
27 // return identical sequences of numbers. | 21 // return identical sequences of numbers. |
28 // This class uses (probably) weak entropy by default, but it's sufficient, | 22 // This class uses (probably) weak entropy by default, but it's sufficient, |
29 // because it is the responsibility of the embedder to install an entropy source | 23 // because it is the responsibility of the embedder to install an entropy source |
30 // using v8::V8::SetEntropySource(), which provides reasonable entropy, see: | 24 // using v8::V8::SetEntropySource(), which provides reasonable entropy, see: |
31 // https://code.google.com/p/v8/issues/detail?id=2905 | 25 // https://code.google.com/p/v8/issues/detail?id=2905 |
32 // This class is neither reentrant nor threadsafe. | 26 // This class is neither reentrant nor threadsafe. |
33 | 27 |
34 class RandomNumberGenerator final { | 28 class RandomNumberGenerator final { |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
82 int64_t NextInt64() WARN_UNUSED_RESULT; | 76 int64_t NextInt64() WARN_UNUSED_RESULT; |
83 | 77 |
84 // Fills the elements of a specified array of bytes with random numbers. | 78 // Fills the elements of a specified array of bytes with random numbers. |
85 void NextBytes(void* buffer, size_t buflen); | 79 void NextBytes(void* buffer, size_t buflen); |
86 | 80 |
87 // Override the current ssed. | 81 // Override the current ssed. |
88 void SetSeed(int64_t seed); | 82 void SetSeed(int64_t seed); |
89 | 83 |
90 int64_t initial_seed() const { return initial_seed_; } | 84 int64_t initial_seed() const { return initial_seed_; } |
91 | 85 |
92 // Static and exposed for external use. | |
93 static inline double ToDouble(uint64_t state0, uint64_t state1) { | |
94 // Exponent for double values for [1.0 .. 2.0) | |
95 static const uint64_t kExponentBits = V8_UINT64_C(0x3FF0000000000000); | |
96 static const uint64_t kMantissaMask = V8_UINT64_C(0x000FFFFFFFFFFFFF); | |
97 uint64_t random = ((state0 + state1) & kMantissaMask) | kExponentBits; | |
98 return bit_cast<double>(random) - 1; | |
99 } | |
100 | |
101 // Static and exposed for external use. | |
102 static inline void XorShift128(uint64_t* state0, uint64_t* state1) { | |
103 uint64_t s1 = *state0; | |
104 uint64_t s0 = *state1; | |
105 *state0 = s0; | |
106 s1 ^= s1 << 23; | |
107 s1 ^= s1 >> 17; | |
108 s1 ^= s0; | |
109 s1 ^= s0 >> 26; | |
110 *state1 = s1; | |
111 } | |
112 | |
113 private: | 86 private: |
114 static const int64_t kMultiplier = V8_2PART_UINT64_C(0x5, deece66d); | 87 static const int64_t kMultiplier = V8_2PART_UINT64_C(0x5, deece66d); |
115 static const int64_t kAddend = 0xb; | 88 static const int64_t kAddend = 0xb; |
116 static const int64_t kMask = V8_2PART_UINT64_C(0xffff, ffffffff); | 89 static const int64_t kMask = V8_2PART_UINT64_C(0xffff, ffffffff); |
117 | 90 |
118 int Next(int bits) WARN_UNUSED_RESULT; | 91 int Next(int bits) WARN_UNUSED_RESULT; |
119 | 92 |
120 static uint64_t MurmurHash3(uint64_t); | |
121 | |
122 int64_t initial_seed_; | 93 int64_t initial_seed_; |
123 uint64_t state0_; | 94 int64_t seed_; |
124 uint64_t state1_; | |
125 }; | 95 }; |
126 | 96 |
127 } // namespace base | 97 } // namespace base |
128 } // namespace v8 | 98 } // namespace v8 |
129 | 99 |
130 #endif // V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_ | 100 #endif // V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_ |
OLD | NEW |