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 <new>
      11             : 
      12             : #include "src/base/macros.h"
      13             : #include "src/base/platform/mutex.h"
      14             : #include "src/base/platform/time.h"
      15             : 
      16             : namespace v8 {
      17             : namespace base {
      18             : 
      19             : static LazyMutex entropy_mutex = LAZY_MUTEX_INITIALIZER;
      20             : static RandomNumberGenerator::EntropySource entropy_source = NULL;
      21             : 
      22             : 
      23             : // static
      24           0 : void RandomNumberGenerator::SetEntropySource(EntropySource source) {
      25             :   LockGuard<Mutex> lock_guard(entropy_mutex.Pointer());
      26           0 :   entropy_source = source;
      27           0 : }
      28             : 
      29             : 
      30       77383 : RandomNumberGenerator::RandomNumberGenerator() {
      31             :   // Check if embedder supplied an entropy source.
      32             :   { LockGuard<Mutex> lock_guard(entropy_mutex.Pointer());
      33       77383 :     if (entropy_source != NULL) {
      34             :       int64_t seed;
      35           0 :       if (entropy_source(reinterpret_cast<unsigned char*>(&seed),
      36             :                          sizeof(seed))) {
      37           0 :         SetSeed(seed);
      38           0 :         return;
      39             :       }
      40             :     }
      41             :   }
      42             : 
      43             : #if V8_OS_CYGWIN || V8_OS_WIN
      44             :   // Use rand_s() to gather entropy on Windows. See:
      45             :   // https://code.google.com/p/v8/issues/detail?id=2905
      46             :   unsigned first_half, second_half;
      47             :   errno_t result = rand_s(&first_half);
      48             :   DCHECK_EQ(0, result);
      49             :   result = rand_s(&second_half);
      50             :   DCHECK_EQ(0, result);
      51             :   SetSeed((static_cast<int64_t>(first_half) << 32) + second_half);
      52             : #else
      53             :   // Gather entropy from /dev/urandom if available.
      54       77383 :   FILE* fp = fopen("/dev/urandom", "rb");
      55       77383 :   if (fp != NULL) {
      56             :     int64_t seed;
      57             :     size_t n = fread(&seed, sizeof(seed), 1, fp);
      58       77383 :     fclose(fp);
      59       77383 :     if (n == 1) {
      60       77383 :       SetSeed(seed);
      61       77383 :       return;
      62             :     }
      63             :   }
      64             : 
      65             :   // We cannot assume that random() or rand() were seeded
      66             :   // properly, so instead of relying on random() or rand(),
      67             :   // we just seed our PRNG using timing data as fallback.
      68             :   // This is weak entropy, but it's sufficient, because
      69             :   // it is the responsibility of the embedder to install
      70             :   // an entropy source using v8::V8::SetEntropySource(),
      71             :   // which provides reasonable entropy, see:
      72             :   // https://code.google.com/p/v8/issues/detail?id=2905
      73           0 :   int64_t seed = Time::NowFromSystemTime().ToInternalValue() << 24;
      74           0 :   seed ^= TimeTicks::HighResolutionNow().ToInternalValue() << 16;
      75           0 :   seed ^= TimeTicks::Now().ToInternalValue() << 8;
      76           0 :   SetSeed(seed);
      77             : #endif  // V8_OS_CYGWIN || V8_OS_WIN
      78             : }
      79             : 
      80             : 
      81    67061672 : int RandomNumberGenerator::NextInt(int max) {
      82             :   DCHECK_LT(0, max);
      83             : 
      84             :   // Fast path if max is a power of 2.
      85    67061672 :   if (IS_POWER_OF_TWO(max)) {
      86     2005966 :     return static_cast<int>((max * static_cast<int64_t>(Next(31))) >> 31);
      87             :   }
      88             : 
      89             :   while (true) {
      90             :     int rnd = Next(31);
      91    66058690 :     int val = rnd % max;
      92    66058690 :     if (rnd - val + (max - 1) >= 0) {
      93             :       return val;
      94             :     }
      95             :   }
      96             : }
      97             : 
      98             : 
      99      133107 : double RandomNumberGenerator::NextDouble() {
     100             :   XorShift128(&state0_, &state1_);
     101      133107 :   return ToDouble(state0_, state1_);
     102             : }
     103             : 
     104             : 
     105           0 : int64_t RandomNumberGenerator::NextInt64() {
     106             :   XorShift128(&state0_, &state1_);
     107           0 :   return bit_cast<int64_t>(state0_ + state1_);
     108             : }
     109             : 
     110             : 
     111      706764 : void RandomNumberGenerator::NextBytes(void* buffer, size_t buflen) {
     112    19013490 :   for (size_t n = 0; n < buflen; ++n) {
     113    36613452 :     static_cast<uint8_t*>(buffer)[n] = static_cast<uint8_t>(Next(8));
     114             :   }
     115      706764 : }
     116             : 
     117             : 
     118   590091509 : int RandomNumberGenerator::Next(int bits) {
     119             :   DCHECK_LT(0, bits);
     120             :   DCHECK_GE(32, bits);
     121             :   XorShift128(&state0_, &state1_);
     122   675459908 :   return static_cast<int>((state0_ + state1_) >> (64 - bits));
     123             : }
     124             : 
     125             : 
     126      215906 : void RandomNumberGenerator::SetSeed(int64_t seed) {
     127      215906 :   initial_seed_ = seed;
     128      215906 :   state0_ = MurmurHash3(bit_cast<uint64_t>(seed));
     129      431812 :   state1_ = MurmurHash3(~state0_);
     130      215906 :   CHECK(state0_ != 0 || state1_ != 0);
     131      215906 : }
     132             : 
     133             : 
     134           0 : uint64_t RandomNumberGenerator::MurmurHash3(uint64_t h) {
     135      431812 :   h ^= h >> 33;
     136      431812 :   h *= V8_UINT64_C(0xFF51AFD7ED558CCD);
     137      431812 :   h ^= h >> 33;
     138      431812 :   h *= V8_UINT64_C(0xC4CEB9FE1A85EC53);
     139      431812 :   h ^= h >> 33;
     140           0 :   return h;
     141             : }
     142             : 
     143             : }  // namespace base
     144             : }  // namespace v8