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