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
11namespace v8 {
12namespace 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
35class 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  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    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  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    uint64_t random = ((state0 + state1) & kMantissaMask) | kExponentBits;
99    return bit_cast<double>(random) - 1;
100  }
101
102  // Static and exposed for external use.
103  static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
104    uint64_t s1 = *state0;
105    uint64_t s0 = *state1;
106    *state0 = s0;
107    s1 ^= s1 << 23;
108    s1 ^= s1 >> 17;
109    s1 ^= s0;
110    s1 ^= s0 >> 26;
111    *state1 = s1;
112  }
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_
132