V8 API Reference, 7.2.502.16 (for Deno 0.2.4)
random-number-generator.cc
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 #include "src/base/utils/random-number-generator.h"
6 
7 #include <stdio.h>
8 #include <stdlib.h>
9 
10 #include <algorithm>
11 #include <new>
12 
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"
17 
18 namespace v8 {
19 namespace base {
20 
21 static LazyMutex entropy_mutex = LAZY_MUTEX_INITIALIZER;
22 static RandomNumberGenerator::EntropySource entropy_source = nullptr;
23 
24 // static
25 void RandomNumberGenerator::SetEntropySource(EntropySource source) {
26  MutexGuard lock_guard(entropy_mutex.Pointer());
27  entropy_source = source;
28 }
29 
30 
31 RandomNumberGenerator::RandomNumberGenerator() {
32  // Check if embedder supplied an entropy source.
33  {
34  MutexGuard lock_guard(entropy_mutex.Pointer());
35  if (entropy_source != nullptr) {
36  int64_t seed;
37  if (entropy_source(reinterpret_cast<unsigned char*>(&seed),
38  sizeof(seed))) {
39  SetSeed(seed);
40  return;
41  }
42  }
43  }
44 
45 #if V8_OS_CYGWIN || V8_OS_WIN
46  // Use rand_s() to gather entropy on Windows. See:
47  // https://code.google.com/p/v8/issues/detail?id=2905
48  unsigned first_half, second_half;
49  errno_t result = rand_s(&first_half);
50  DCHECK_EQ(0, result);
51  result = rand_s(&second_half);
52  DCHECK_EQ(0, result);
53  SetSeed((static_cast<int64_t>(first_half) << 32) + second_half);
54 #else
55  // Gather entropy from /dev/urandom if available.
56  FILE* fp = fopen("/dev/urandom", "rb");
57  if (fp != nullptr) {
58  int64_t seed;
59  size_t n = fread(&seed, sizeof(seed), 1, fp);
60  fclose(fp);
61  if (n == 1) {
62  SetSeed(seed);
63  return;
64  }
65  }
66 
67  // We cannot assume that random() or rand() were seeded
68  // properly, so instead of relying on random() or rand(),
69  // we just seed our PRNG using timing data as fallback.
70  // This is weak entropy, but it's sufficient, because
71  // it is the responsibility of the embedder to install
72  // an entropy source using v8::V8::SetEntropySource(),
73  // which provides reasonable entropy, see:
74  // https://code.google.com/p/v8/issues/detail?id=2905
75  int64_t seed = Time::NowFromSystemTime().ToInternalValue() << 24;
76  seed ^= TimeTicks::HighResolutionNow().ToInternalValue() << 16;
77  seed ^= TimeTicks::Now().ToInternalValue() << 8;
78  SetSeed(seed);
79 #endif // V8_OS_CYGWIN || V8_OS_WIN
80 }
81 
82 
83 int RandomNumberGenerator::NextInt(int max) {
84  DCHECK_LT(0, max);
85 
86  // Fast path if max is a power of 2.
87  if (bits::IsPowerOfTwo(max)) {
88  return static_cast<int>((max * static_cast<int64_t>(Next(31))) >> 31);
89  }
90 
91  while (true) {
92  int rnd = Next(31);
93  int val = rnd % max;
94  if (rnd - val + (max - 1) >= 0) {
95  return val;
96  }
97  }
98 }
99 
100 
101 double RandomNumberGenerator::NextDouble() {
102  XorShift128(&state0_, &state1_);
103  return ToDouble(state0_);
104 }
105 
106 
107 int64_t RandomNumberGenerator::NextInt64() {
108  XorShift128(&state0_, &state1_);
109  return bit_cast<int64_t>(state0_ + state1_);
110 }
111 
112 
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));
116  }
117 }
118 
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++) {
124  if (!set.count(i)) {
125  result.push_back(i);
126  }
127  }
128  return result;
129 }
130 
131 std::vector<uint64_t> RandomNumberGenerator::NextSample(uint64_t max,
132  size_t n) {
133  CHECK_LE(n, max);
134 
135  if (n == 0) {
136  return std::vector<uint64_t>();
137  }
138 
139  // Choose to select or exclude, whatever needs fewer generator calls.
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;
143 
144  size_t counter = 0;
145  while (selected.size() != smaller_part && counter / 3 < smaller_part) {
146  uint64_t x = static_cast<uint64_t>(NextDouble() * max);
147  CHECK_LT(x, max);
148 
149  selected.insert(x);
150  counter++;
151  }
152 
153  if (selected.size() == smaller_part) {
154  if (smaller_part != n) {
155  return ComplementSample(selected, max);
156  }
157  return std::vector<uint64_t>(selected.begin(), selected.end());
158  }
159 
160  // Failed to select numbers in smaller_part * 3 steps, try different approach.
161  return NextSampleSlow(max, n, selected);
162 }
163 
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);
167 
168  std::vector<uint64_t> result;
169  result.reserve(max - excluded.size());
170 
171  for (uint64_t i = 0; i < max; i++) {
172  if (!excluded.count(i)) {
173  result.push_back(i);
174  }
175  }
176 
177  // Decrease result vector until it contains values to select or exclude,
178  // whatever needs fewer generator calls.
179  size_t larger_part = static_cast<size_t>(
180  std::max(max - static_cast<uint64_t>(n), static_cast<uint64_t>(n)));
181 
182  // Excluded set may cause that initial result is already smaller than
183  // larget_part.
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());
187 
188  std::swap(result[x], result.back());
189  result.pop_back();
190  }
191 
192  if (result.size() != n) {
193  return ComplementSample(
194  std::unordered_set<uint64_t>(result.begin(), result.end()), max);
195  }
196  return result;
197 }
198 
199 int RandomNumberGenerator::Next(int bits) {
200  DCHECK_LT(0, bits);
201  DCHECK_GE(32, bits);
202  XorShift128(&state0_, &state1_);
203  return static_cast<int>((state0_ + state1_) >> (64 - bits));
204 }
205 
206 
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);
212 }
213 
214 
215 uint64_t RandomNumberGenerator::MurmurHash3(uint64_t h) {
216  h ^= h >> 33;
217  h *= uint64_t{0xFF51AFD7ED558CCD};
218  h ^= h >> 33;
219  h *= uint64_t{0xC4CEB9FE1A85EC53};
220  h ^= h >> 33;
221  return h;
222 }
223 
224 } // namespace base
225 } // namespace v8
Definition: libplatform.h:13