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 pseudorandom numbers. The class | 16 // This class is used to generate a stream of pseudo-random numbers. The class |
17 // uses a 48-bit seed, which is modified using a linear congruential formula. | 17 // uses a 64-bit seed, which is passed through MurmurHash3 to create two 64-bit |
18 // (See Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1.) | 18 // state values. This pair of state values is then used in xorshift128+. |
| 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 |
19 // If two instances of RandomNumberGenerator are created with the same seed, and | 25 // If two instances of RandomNumberGenerator are created with the same seed, and |
20 // the same sequence of method calls is made for each, they will generate and | 26 // the same sequence of method calls is made for each, they will generate and |
21 // return identical sequences of numbers. | 27 // return identical sequences of numbers. |
22 // This class uses (probably) weak entropy by default, but it's sufficient, | 28 // This class uses (probably) weak entropy by default, but it's sufficient, |
23 // because it is the responsibility of the embedder to install an entropy source | 29 // because it is the responsibility of the embedder to install an entropy source |
24 // using v8::V8::SetEntropySource(), which provides reasonable entropy, see: | 30 // using v8::V8::SetEntropySource(), which provides reasonable entropy, see: |
25 // https://code.google.com/p/v8/issues/detail?id=2905 | 31 // https://code.google.com/p/v8/issues/detail?id=2905 |
26 // This class is neither reentrant nor threadsafe. | 32 // This class is neither reentrant nor threadsafe. |
27 | 33 |
28 class RandomNumberGenerator final { | 34 class RandomNumberGenerator final { |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
76 int64_t NextInt64() WARN_UNUSED_RESULT; | 82 int64_t NextInt64() WARN_UNUSED_RESULT; |
77 | 83 |
78 // Fills the elements of a specified array of bytes with random numbers. | 84 // Fills the elements of a specified array of bytes with random numbers. |
79 void NextBytes(void* buffer, size_t buflen); | 85 void NextBytes(void* buffer, size_t buflen); |
80 | 86 |
81 // Override the current ssed. | 87 // Override the current ssed. |
82 void SetSeed(int64_t seed); | 88 void SetSeed(int64_t seed); |
83 | 89 |
84 int64_t initial_seed() const { return initial_seed_; } | 90 int64_t initial_seed() const { return initial_seed_; } |
85 | 91 |
| 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 |
86 private: | 113 private: |
87 static const int64_t kMultiplier = V8_2PART_UINT64_C(0x5, deece66d); | 114 static const int64_t kMultiplier = V8_2PART_UINT64_C(0x5, deece66d); |
88 static const int64_t kAddend = 0xb; | 115 static const int64_t kAddend = 0xb; |
89 static const int64_t kMask = V8_2PART_UINT64_C(0xffff, ffffffff); | 116 static const int64_t kMask = V8_2PART_UINT64_C(0xffff, ffffffff); |
90 | 117 |
91 int Next(int bits) WARN_UNUSED_RESULT; | 118 int Next(int bits) WARN_UNUSED_RESULT; |
92 | 119 |
| 120 static uint64_t MurmurHash3(uint64_t); |
| 121 |
93 int64_t initial_seed_; | 122 int64_t initial_seed_; |
94 int64_t seed_; | 123 uint64_t state0_; |
| 124 uint64_t state1_; |
95 }; | 125 }; |
96 | 126 |
97 } // namespace base | 127 } // namespace base |
98 } // namespace v8 | 128 } // namespace v8 |
99 | 129 |
100 #endif // V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_ | 130 #endif // V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_ |
OLD | NEW |