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