• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/macros.h"
9 
10 namespace v8 {
11 namespace base {
12 
13 // -----------------------------------------------------------------------------
14 // RandomNumberGenerator
15 
16 // This class is used to generate a stream of pseudo-random numbers. The class
17 // uses a 64-bit seed, which is passed through MurmurHash3 to create two 64-bit
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 
25 // 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
27 // return identical sequences of numbers.
28 // 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
30 // using v8::V8::SetEntropySource(), which provides reasonable entropy, see:
31 // https://code.google.com/p/v8/issues/detail?id=2905
32 // This class is neither reentrant nor threadsafe.
33 
34 class RandomNumberGenerator final {
35  public:
36   // EntropySource is used as a callback function when V8 needs a source of
37   // entropy.
38   typedef bool (*EntropySource)(unsigned char* buffer, size_t buflen);
39   static void SetEntropySource(EntropySource entropy_source);
40 
41   RandomNumberGenerator();
RandomNumberGenerator(int64_t seed)42   explicit RandomNumberGenerator(int64_t seed) { SetSeed(seed); }
43 
44   // Returns the next pseudorandom, uniformly distributed int value from this
45   // random number generator's sequence. The general contract of |NextInt()| is
46   // that one int value is pseudorandomly generated and returned.
47   // All 2^32 possible integer values are produced with (approximately) equal
48   // probability.
NextInt()49   V8_INLINE int NextInt() WARN_UNUSED_RESULT {
50     return Next(32);
51   }
52 
53   // Returns a pseudorandom, uniformly distributed int value between 0
54   // (inclusive) and the specified max value (exclusive), drawn from this random
55   // number generator's sequence. The general contract of |NextInt(int)| is that
56   // one int value in the specified range is pseudorandomly generated and
57   // returned. All max possible int values are produced with (approximately)
58   // equal probability.
59   int NextInt(int max) WARN_UNUSED_RESULT;
60 
61   // Returns the next pseudorandom, uniformly distributed boolean value from
62   // this random number generator's sequence. The general contract of
63   // |NextBoolean()| is that one boolean value is pseudorandomly generated and
64   // returned. The values true and false are produced with (approximately) equal
65   // probability.
NextBool()66   V8_INLINE bool NextBool() WARN_UNUSED_RESULT {
67     return Next(1) != 0;
68   }
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() 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() 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   // Override the current ssed.
88   void SetSeed(int64_t seed);
89 
initial_seed()90   int64_t initial_seed() const { return initial_seed_; }
91 
92   // Static and exposed for external use.
ToDouble(uint64_t state0,uint64_t state1)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.
XorShift128(uint64_t * state0,uint64_t * state1)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:
114   static const int64_t kMultiplier = V8_2PART_UINT64_C(0x5, deece66d);
115   static const int64_t kAddend = 0xb;
116   static const int64_t kMask = V8_2PART_UINT64_C(0xffff, ffffffff);
117 
118   int Next(int bits) WARN_UNUSED_RESULT;
119 
120   static uint64_t MurmurHash3(uint64_t);
121 
122   int64_t initial_seed_;
123   uint64_t state0_;
124   uint64_t state1_;
125 };
126 
127 }  // namespace base
128 }  // namespace v8
129 
130 #endif  // V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_
131