Line data Source code
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 0 : void RandomNumberGenerator::SetEntropySource(EntropySource source) {
26 : MutexGuard lock_guard(entropy_mutex.Pointer());
27 0 : entropy_source = source;
28 0 : }
29 :
30 :
31 82222 : RandomNumberGenerator::RandomNumberGenerator() {
32 : // Check if embedder supplied an entropy source.
33 : {
34 : MutexGuard lock_guard(entropy_mutex.Pointer());
35 82222 : if (entropy_source != nullptr) {
36 : int64_t seed;
37 0 : if (entropy_source(reinterpret_cast<unsigned char*>(&seed),
38 : sizeof(seed))) {
39 0 : SetSeed(seed);
40 0 : 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 82222 : FILE* fp = fopen("/dev/urandom", "rb");
57 82222 : if (fp != nullptr) {
58 : int64_t seed;
59 : size_t n = fread(&seed, sizeof(seed), 1, fp);
60 82222 : fclose(fp);
61 82222 : if (n == 1) {
62 82222 : SetSeed(seed);
63 82222 : 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 0 : int64_t seed = Time::NowFromSystemTime().ToInternalValue() << 24;
76 0 : seed ^= TimeTicks::HighResolutionNow().ToInternalValue() << 16;
77 0 : seed ^= TimeTicks::Now().ToInternalValue() << 8;
78 0 : SetSeed(seed);
79 : #endif // V8_OS_CYGWIN || V8_OS_WIN
80 : }
81 :
82 :
83 55605989 : int RandomNumberGenerator::NextInt(int max) {
84 : DCHECK_LT(0, max);
85 :
86 : // Fast path if max is a power of 2.
87 55605989 : if (bits::IsPowerOfTwo(max)) {
88 2354810 : return static_cast<int>((max * static_cast<int64_t>(Next(31))) >> 31);
89 : }
90 :
91 : while (true) {
92 : int rnd = Next(31);
93 54428585 : int val = rnd % max;
94 54428585 : if (std::numeric_limits<int>::max() - (rnd - val) >= (max - 1)) {
95 : return val;
96 : }
97 : }
98 : }
99 :
100 :
101 185344 : double RandomNumberGenerator::NextDouble() {
102 : XorShift128(&state0_, &state1_);
103 185344 : return ToDouble(state0_);
104 : }
105 :
106 :
107 72943 : int64_t RandomNumberGenerator::NextInt64() {
108 : XorShift128(&state0_, &state1_);
109 145886 : return bit_cast<int64_t>(state0_ + state1_);
110 : }
111 :
112 :
113 2570504 : void RandomNumberGenerator::NextBytes(void* buffer, size_t buflen) {
114 1294052972 : for (size_t n = 0; n < buflen; ++n) {
115 2582964936 : static_cast<uint8_t*>(buffer)[n] = static_cast<uint8_t>(Next(8));
116 : }
117 2570504 : }
118 :
119 444429 : static std::vector<uint64_t> ComplementSample(
120 : const std::unordered_set<uint64_t>& set, uint64_t max) {
121 : std::vector<uint64_t> result;
122 444429 : result.reserve(max - set.size());
123 24887538 : for (uint64_t i = 0; i < max; i++) {
124 24443109 : if (!set.count(i)) {
125 12332655 : result.push_back(i);
126 : }
127 : }
128 444429 : return result;
129 : }
130 :
131 555534 : std::vector<uint64_t> RandomNumberGenerator::NextSample(uint64_t max,
132 : size_t n) {
133 555534 : CHECK_LE(n, max);
134 :
135 555534 : 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 1111050 : std::min(max - static_cast<uint64_t>(n), static_cast<uint64_t>(n)));
142 555525 : std::unordered_set<uint64_t> selected;
143 :
144 : size_t counter = 0;
145 4267870 : while (selected.size() != smaller_part && counter / 3 < smaller_part) {
146 3156820 : uint64_t x = static_cast<uint64_t>(NextDouble() * max);
147 3156820 : CHECK_LT(x, max);
148 :
149 : selected.insert(x);
150 3156820 : counter++;
151 : }
152 :
153 555525 : if (selected.size() == smaller_part) {
154 555500 : if (smaller_part != n) {
155 222210 : 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 25 : return NextSampleSlow(max, n, selected);
162 : }
163 :
164 888874 : std::vector<uint64_t> RandomNumberGenerator::NextSampleSlow(
165 : uint64_t max, size_t n, const std::unordered_set<uint64_t>& excluded) {
166 888874 : CHECK_GE(max - excluded.size(), n);
167 :
168 : std::vector<uint64_t> result;
169 888874 : result.reserve(max - excluded.size());
170 :
171 29220908 : for (uint64_t i = 0; i < max; i++) {
172 28332034 : if (!excluded.count(i)) {
173 27109780 : 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 1777748 : 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 9332974 : while (result.size() != larger_part && result.size() > n) {
185 3333176 : size_t x = static_cast<size_t>(NextDouble() * result.size());
186 3333176 : CHECK_LT(x, result.size());
187 :
188 : std::swap(result[x], result.back());
189 : result.pop_back();
190 : }
191 :
192 888874 : if (result.size() != n) {
193 : return ComplementSample(
194 444438 : std::unordered_set<uint64_t>(result.begin(), result.end()), max);
195 : }
196 : return result;
197 : }
198 :
199 412056306 : int RandomNumberGenerator::Next(int bits) {
200 : DCHECK_LT(0, bits);
201 : DCHECK_GE(32, bits);
202 : XorShift128(&state0_, &state1_);
203 1759144764 : return static_cast<int>((state0_ + state1_) >> (64 - bits));
204 : }
205 :
206 :
207 223262 : void RandomNumberGenerator::SetSeed(int64_t seed) {
208 223262 : initial_seed_ = seed;
209 223262 : state0_ = MurmurHash3(bit_cast<uint64_t>(seed));
210 446524 : state1_ = MurmurHash3(~state0_);
211 223262 : CHECK(state0_ != 0 || state1_ != 0);
212 223262 : }
213 :
214 :
215 348 : uint64_t RandomNumberGenerator::MurmurHash3(uint64_t h) {
216 446872 : h ^= h >> 33;
217 446872 : h *= uint64_t{0xFF51AFD7ED558CCD};
218 446872 : h ^= h >> 33;
219 446872 : h *= uint64_t{0xC4CEB9FE1A85EC53};
220 446872 : h ^= h >> 33;
221 348 : return h;
222 : }
223 :
224 : } // namespace base
225 : } // namespace v8
|
