1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
// Copyright 2013 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_
#define V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_
#include <unordered_set>
#include <vector>
#include "src/base/base-export.h"
#include "src/base/macros.h"
namespace v8 {
namespace base {
// -----------------------------------------------------------------------------
// RandomNumberGenerator
// This class is used to generate a stream of pseudo-random numbers. The class
// uses a 64-bit seed, which is passed through MurmurHash3 to create two 64-bit
// state values. This pair of state values is then used in xorshift128+.
// The resulting stream of pseudo-random numbers has a period length of 2^128-1.
// See Marsaglia: http://www.jstatsoft.org/v08/i14/paper
// And Vigna: http://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf
// NOTE: Any changes to the algorithm must be tested against TestU01.
// Please find instructions for this in the internal repository.
// If two instances of RandomNumberGenerator are created with the same seed, and
// the same sequence of method calls is made for each, they will generate and
// return identical sequences of numbers.
// This class uses (probably) weak entropy by default, but it's sufficient,
// because it is the responsibility of the embedder to install an entropy source
// using v8::V8::SetEntropySource(), which provides reasonable entropy, see:
// https://code.google.com/p/v8/issues/detail?id=2905
// This class is neither reentrant nor threadsafe.
class V8_BASE_EXPORT RandomNumberGenerator final {
public:
// EntropySource is used as a callback function when V8 needs a source of
// entropy.
using EntropySource = bool (*)(unsigned char* buffer, size_t buflen);
static void SetEntropySource(EntropySource entropy_source);
RandomNumberGenerator();
explicit RandomNumberGenerator(int64_t seed) { SetSeed(seed); }
// Returns the next pseudorandom, uniformly distributed int value from this
// random number generator's sequence. The general contract of |NextInt()| is
// that one int value is pseudorandomly generated and returned.
// All 2^32 possible integer values are produced with (approximately) equal
// probability.
V8_INLINE int NextInt() V8_WARN_UNUSED_RESULT { return Next(32); }
// Returns a pseudorandom, uniformly distributed int value between 0
// (inclusive) and the specified max value (exclusive), drawn from this random
// number generator's sequence. The general contract of |NextInt(int)| is that
// one int value in the specified range is pseudorandomly generated and
// returned. All max possible int values are produced with (approximately)
// equal probability.
int NextInt(int max) V8_WARN_UNUSED_RESULT;
// Returns the next pseudorandom, uniformly distributed boolean value from
// this random number generator's sequence. The general contract of
// |NextBoolean()| is that one boolean value is pseudorandomly generated and
// returned. The values true and false are produced with (approximately) equal
// probability.
V8_INLINE bool NextBool() V8_WARN_UNUSED_RESULT { return Next(1) != 0; }
// Returns the next pseudorandom, uniformly distributed double value between
// 0.0 and 1.0 from this random number generator's sequence.
// The general contract of |NextDouble()| is that one double value, chosen
// (approximately) uniformly from the range 0.0 (inclusive) to 1.0
// (exclusive), is pseudorandomly generated and returned.
double NextDouble() V8_WARN_UNUSED_RESULT;
// Returns the next pseudorandom, uniformly distributed int64 value from this
// random number generator's sequence. The general contract of |NextInt64()|
// is that one 64-bit int value is pseudorandomly generated and returned.
// All 2^64 possible integer values are produced with (approximately) equal
// probability.
int64_t NextInt64() V8_WARN_UNUSED_RESULT;
// Fills the elements of a specified array of bytes with random numbers.
void NextBytes(void* buffer, size_t buflen);
// Returns the next pseudorandom set of n unique uint64 values smaller than
// max.
// n must be less or equal to max.
std::vector<uint64_t> NextSample(uint64_t max,
size_t n) V8_WARN_UNUSED_RESULT;
// Returns the next pseudorandom set of n unique uint64 values smaller than
// max.
// n must be less or equal to max.
// max - |excluded| must be less or equal to n.
//
// Generates list of all possible values and removes random values from it
// until size reaches n.
std::vector<uint64_t> NextSampleSlow(
uint64_t max, size_t n,
const std::unordered_set<uint64_t>& excluded =
std::unordered_set<uint64_t>{}) V8_WARN_UNUSED_RESULT;
// Override the current ssed.
void SetSeed(int64_t seed);
int64_t initial_seed() const { return initial_seed_; }
// Static and exposed for external use.
static inline double ToDouble(uint64_t state0) {
// Exponent for double values for [1.0 .. 2.0)
static const uint64_t kExponentBits = uint64_t{0x3FF0000000000000};
uint64_t random = (state0 >> 12) | kExponentBits;
return base::bit_cast<double>(random) - 1;
}
// Static and exposed for external use.
static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
uint64_t s1 = *state0;
uint64_t s0 = *state1;
*state0 = s0;
s1 ^= s1 << 23;
s1 ^= s1 >> 17;
s1 ^= s0;
s1 ^= s0 >> 26;
*state1 = s1;
}
static uint64_t MurmurHash3(uint64_t);
private:
static const int64_t kMultiplier = 0x5'deec'e66d;
static const int64_t kAddend = 0xb;
static const int64_t kMask = 0xffff'ffff'ffff;
int Next(int bits) V8_WARN_UNUSED_RESULT;
int64_t initial_seed_;
uint64_t state0_;
uint64_t state1_;
};
} // namespace base
} // namespace v8
#endif // V8_BASE_UTILS_RANDOM_NUMBER_GENERATOR_H_
|
