// Copyright 2013 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #include "src/base/utils/random-number-generator.h" #include <stdio.h> #include <stdlib.h> #if defined(V8_OS_STARBOARD) #include "starboard/system.h" #endif // V8_OS_STARBOARD #include <algorithm> #include <new> #include "src/base/bits.h" #include "src/base/macros.h" #include "src/base/platform/mutex.h" #include "src/base/platform/time.h" #include "src/base/platform/wrappers.h" namespace v8 { namespace base { static LazyMutex entropy_mutex = LAZY_MUTEX_INITIALIZER; static RandomNumberGenerator::EntropySource entropy_source = nullptr; // static void RandomNumberGenerator::SetEntropySource(EntropySource source) { MutexGuard lock_guard(entropy_mutex.Pointer()); entropy_source = source; } RandomNumberGenerator::RandomNumberGenerator() { // Check if embedder supplied an entropy source. { MutexGuard lock_guard(entropy_mutex.Pointer()); if (entropy_source != nullptr) { int64_t seed; if (entropy_source(reinterpret_cast<unsigned char*>(&seed), sizeof(seed))) { SetSeed(seed); return; } } } #if V8_OS_CYGWIN || V8_OS_WIN // Use rand_s() to gather entropy on Windows. See: // https://code.google.com/p/v8/issues/detail?id=2905 unsigned first_half, second_half; errno_t result = rand_s(&first_half); DCHECK_EQ(0, result); result = rand_s(&second_half); DCHECK_EQ(0, result); USE(result); SetSeed((static_cast<int64_t>(first_half) << 32) + second_half); #elif V8_OS_DARWIN || V8_OS_FREEBSD || V8_OS_OPENBSD // Despite its prefix suggests it is not RC4 algorithm anymore. // It always succeeds while having decent performance and // no file descriptor involved. int64_t seed; arc4random_buf(&seed, sizeof(seed)); SetSeed(seed); #elif V8_OS_STARBOARD SetSeed(SbSystemGetRandomUInt64()); #else // Gather entropy from /dev/urandom if available. FILE* fp = base::Fopen("/dev/urandom", "rb"); if (fp != nullptr) { int64_t seed; size_t n = fread(&seed, sizeof(seed), 1, fp); base::Fclose(fp); if (n == 1) { SetSeed(seed); return; } } // We cannot assume that random() or rand() were seeded // properly, so instead of relying on random() or rand(), // we just seed our PRNG using timing data as fallback. // This is weak entropy, but it's sufficient, because // it is the responsibility of the embedder to install // an entropy source using v8::V8::SetEntropySource(), // which provides reasonable entropy, see: // https://code.google.com/p/v8/issues/detail?id=2905 int64_t seed = Time::NowFromSystemTime().ToInternalValue() << 24; seed ^= TimeTicks::Now().ToInternalValue(); SetSeed(seed); #endif // V8_OS_CYGWIN || V8_OS_WIN } int RandomNumberGenerator::NextInt(int max) { DCHECK_LT(0, max); // Fast path if max is a power of 2. if (bits::IsPowerOfTwo(max)) { return static_cast<int>((max * static_cast<int64_t>(Next(31))) >> 31); } while (true) { int rnd = Next(31); int val = rnd % max; if (std::numeric_limits<int>::max() - (rnd - val) >= (max - 1)) { return val; } } } double RandomNumberGenerator::NextDouble() { XorShift128(&state0_, &state1_); return ToDouble(state0_); } int64_t RandomNumberGenerator::NextInt64() { XorShift128(&state0_, &state1_); return base::bit_cast<int64_t>(state0_ + state1_); } void RandomNumberGenerator::NextBytes(void* buffer, size_t buflen) { for (size_t n = 0; n < buflen; ++n) { static_cast<uint8_t*>(buffer)[n] = static_cast<uint8_t>(Next(8)); } } static std::vector<uint64_t> ComplementSample( const std::unordered_set<uint64_t>& set, uint64_t max) { std::vector<uint64_t> result; result.reserve(max - set.size()); for (uint64_t i = 0; i < max; i++) { if (!set.count(i)) { result.push_back(i); } } return result; } std::vector<uint64_t> RandomNumberGenerator::NextSample(uint64_t max, size_t n) { CHECK_LE(n, max); if (n == 0) { return std::vector<uint64_t>(); } // Choose to select or exclude, whatever needs fewer generator calls. size_t smaller_part = static_cast<size_t>( std::min(max - static_cast<uint64_t>(n), static_cast<uint64_t>(n))); std::unordered_set<uint64_t> selected; size_t counter = 0; while (selected.size() != smaller_part && counter / 3 < smaller_part) { uint64_t x = static_cast<uint64_t>(NextDouble() * max); CHECK_LT(x, max); selected.insert(x); counter++; } if (selected.size() == smaller_part) { if (smaller_part != n) { return ComplementSample(selected, max); } return std::vector<uint64_t>(selected.begin(), selected.end()); } // Failed to select numbers in smaller_part * 3 steps, try different approach. return NextSampleSlow(max, n, selected); } std::vector<uint64_t> RandomNumberGenerator::NextSampleSlow( uint64_t max, size_t n, const std::unordered_set<uint64_t>& excluded) { CHECK_GE(max - excluded.size(), n); std::vector<uint64_t> result; result.reserve(max - excluded.size()); for (uint64_t i = 0; i < max; i++) { if (!excluded.count(i)) { result.push_back(i); } } // Decrease result vector until it contains values to select or exclude, // whatever needs fewer generator calls. size_t larger_part = static_cast<size_t>( std::max(max - static_cast<uint64_t>(n), static_cast<uint64_t>(n))); // Excluded set may cause that initial result is already smaller than // larget_part. while (result.size() != larger_part && result.size() > n) { size_t x = static_cast<size_t>(NextDouble() * result.size()); CHECK_LT(x, result.size()); std::swap(result[x], result.back()); result.pop_back(); } if (result.size() != n) { return ComplementSample( std::unordered_set<uint64_t>(result.begin(), result.end()), max); } return result; } int RandomNumberGenerator::Next(int bits) { DCHECK_LT(0, bits); DCHECK_GE(32, bits); XorShift128(&state0_, &state1_); return static_cast<int>((state0_ + state1_) >> (64 - bits)); } void RandomNumberGenerator::SetSeed(int64_t seed) { initial_seed_ = seed; state0_ = MurmurHash3(base::bit_cast<uint64_t>(seed)); state1_ = MurmurHash3(~state0_); CHECK(state0_ != 0 || state1_ != 0); } uint64_t RandomNumberGenerator::MurmurHash3(uint64_t h) { h ^= h >> 33; h *= uint64_t{0xFF51AFD7ED558CCD}; h ^= h >> 33; h *= uint64_t{0xC4CEB9FE1A85EC53}; h ^= h >> 33; return h; } } // namespace base } // namespace v8