5 #include "src/base/utils/random-number-generator.h" 13 #include "src/base/bits.h" 14 #include "src/base/macros.h" 15 #include "src/base/platform/mutex.h" 16 #include "src/base/platform/time.h" 21 static LazyMutex entropy_mutex = LAZY_MUTEX_INITIALIZER;
22 static RandomNumberGenerator::EntropySource entropy_source =
nullptr;
25 void RandomNumberGenerator::SetEntropySource(EntropySource source) {
26 MutexGuard lock_guard(entropy_mutex.Pointer());
27 entropy_source = source;
31 RandomNumberGenerator::RandomNumberGenerator() {
34 MutexGuard lock_guard(entropy_mutex.Pointer());
35 if (entropy_source !=
nullptr) {
37 if (entropy_source(reinterpret_cast<unsigned char*>(&seed),
45 #if V8_OS_CYGWIN || V8_OS_WIN 48 unsigned first_half, second_half;
49 errno_t result = rand_s(&first_half);
51 result = rand_s(&second_half);
53 SetSeed((static_cast<int64_t>(first_half) << 32) + second_half);
56 FILE* fp = fopen(
"/dev/urandom",
"rb");
59 size_t n = fread(&seed,
sizeof(seed), 1, fp);
75 int64_t seed = Time::NowFromSystemTime().ToInternalValue() << 24;
76 seed ^= TimeTicks::HighResolutionNow().ToInternalValue() << 16;
77 seed ^= TimeTicks::Now().ToInternalValue() << 8;
79 #endif // V8_OS_CYGWIN || V8_OS_WIN 83 int RandomNumberGenerator::NextInt(
int max) {
87 if (bits::IsPowerOfTwo(max)) {
88 return static_cast<int>((max *
static_cast<int64_t>(Next(31))) >> 31);
94 if (rnd - val + (max - 1) >= 0) {
101 double RandomNumberGenerator::NextDouble() {
102 XorShift128(&state0_, &state1_);
103 return ToDouble(state0_);
107 int64_t RandomNumberGenerator::NextInt64() {
108 XorShift128(&state0_, &state1_);
109 return bit_cast<
int64_t>(state0_ + state1_);
113 void RandomNumberGenerator::NextBytes(
void* buffer,
size_t buflen) {
114 for (
size_t n = 0; n < buflen; ++n) {
115 static_cast<uint8_t*
>(buffer)[n] = static_cast<uint8_t>(Next(8));
119 static std::vector<uint64_t> ComplementSample(
120 const std::unordered_set<uint64_t>&
set, uint64_t max) {
121 std::vector<uint64_t> result;
122 result.reserve(max -
set.size());
123 for (uint64_t
i = 0;
i < max;
i++) {
131 std::vector<uint64_t> RandomNumberGenerator::NextSample(uint64_t max,
136 return std::vector<uint64_t>();
140 size_t smaller_part =
static_cast<size_t>(
141 std::min(max - static_cast<uint64_t>(n), static_cast<uint64_t>(n)));
142 std::unordered_set<uint64_t> selected;
145 while (selected.size() != smaller_part && counter / 3 < smaller_part) {
146 uint64_t x =
static_cast<uint64_t
>(NextDouble() * max);
153 if (selected.size() == smaller_part) {
154 if (smaller_part != n) {
155 return ComplementSample(selected, max);
157 return std::vector<uint64_t>(selected.begin(), selected.end());
161 return NextSampleSlow(max, n, selected);
164 std::vector<uint64_t> RandomNumberGenerator::NextSampleSlow(
165 uint64_t max,
size_t n,
const std::unordered_set<uint64_t>& excluded) {
166 CHECK_GE(max - excluded.size(), n);
168 std::vector<uint64_t> result;
169 result.reserve(max - excluded.size());
171 for (uint64_t
i = 0;
i < max;
i++) {
172 if (!excluded.count(
i)) {
179 size_t larger_part =
static_cast<size_t>(
180 std::max(max - static_cast<uint64_t>(n), static_cast<uint64_t>(n)));
184 while (result.size() != larger_part && result.size() > n) {
185 size_t x =
static_cast<size_t>(NextDouble() * result.size());
186 CHECK_LT(x, result.size());
188 std::swap(result[x], result.back());
192 if (result.size() != n) {
193 return ComplementSample(
194 std::unordered_set<uint64_t>(result.begin(), result.end()), max);
199 int RandomNumberGenerator::Next(
int bits) {
202 XorShift128(&state0_, &state1_);
203 return static_cast<int>((state0_ + state1_) >> (64 - bits));
207 void RandomNumberGenerator::SetSeed(
int64_t seed) {
208 initial_seed_ = seed;
209 state0_ = MurmurHash3(bit_cast<uint64_t>(seed));
210 state1_ = MurmurHash3(~state0_);
211 CHECK(state0_ != 0 || state1_ != 0);
215 uint64_t RandomNumberGenerator::MurmurHash3(uint64_t h) {
217 h *= uint64_t{0xFF51AFD7ED558CCD};
219 h *= uint64_t{0xC4CEB9FE1A85EC53};