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