Home | History | Annotate | Download | only in utils 
      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 void RandomNumberGenerator::SetEntropySource(EntropySource source) {
     25   LockGuard<Mutex> lock_guard(entropy_mutex.Pointer());
     26   entropy_source = source;
     27 }
     28 
     29 
     30 RandomNumberGenerator::RandomNumberGenerator() {
     31   // Check if embedder supplied an entropy source.
     32   { LockGuard<Mutex> lock_guard(entropy_mutex.Pointer());
     33     if (entropy_source != NULL) {
     34       int64_t seed;
     35       if (entropy_source(reinterpret_cast<unsigned char*>(&seed),
     36                          sizeof(seed))) {
     37         SetSeed(seed);
     38         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   FILE* fp = fopen("/dev/urandom", "rb");
     55   if (fp != NULL) {
     56     int64_t seed;
     57     size_t n = fread(&seed, sizeof(seed), 1, fp);
     58     fclose(fp);
     59     if (n == 1) {
     60       SetSeed(seed);
     61       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   int64_t seed = Time::NowFromSystemTime().ToInternalValue() << 24;
     74   seed ^= TimeTicks::HighResolutionNow().ToInternalValue() << 16;
     75   seed ^= TimeTicks::Now().ToInternalValue() << 8;
     76   SetSeed(seed);
     77 #endif  // V8_OS_CYGWIN || V8_OS_WIN
     78 }
     79 
     80 
     81 int RandomNumberGenerator::NextInt(int max) {
     82   DCHECK_LT(0, max);
     83 
     84   // Fast path if max is a power of 2.
     85   if (IS_POWER_OF_TWO(max)) {
     86     return static_cast<int>((max * static_cast<int64_t>(Next(31))) >> 31);
     87   }
     88 
     89   while (true) {
     90     int rnd = Next(31);
     91     int val = rnd % max;
     92     if (rnd - val + (max - 1) >= 0) {
     93       return val;
     94     }
     95   }
     96 }
     97 
     98 
     99 double RandomNumberGenerator::NextDouble() {
    100   XorShift128(&state0_, &state1_);
    101   return ToDouble(state0_, state1_);
    102 }
    103 
    104 
    105 int64_t RandomNumberGenerator::NextInt64() {
    106   XorShift128(&state0_, &state1_);
    107   return bit_cast<int64_t>(state0_ + state1_);
    108 }
    109 
    110 
    111 void RandomNumberGenerator::NextBytes(void* buffer, size_t buflen) {
    112   for (size_t n = 0; n < buflen; ++n) {
    113     static_cast<uint8_t*>(buffer)[n] = static_cast<uint8_t>(Next(8));
    114   }
    115 }
    116 
    117 
    118 int RandomNumberGenerator::Next(int bits) {
    119   DCHECK_LT(0, bits);
    120   DCHECK_GE(32, bits);
    121   XorShift128(&state0_, &state1_);
    122   return static_cast<int>((state0_ + state1_) >> (64 - bits));
    123 }
    124 
    125 
    126 void RandomNumberGenerator::SetSeed(int64_t seed) {
    127   if (seed == 0) seed = 1;
    128   initial_seed_ = seed;
    129   state0_ = MurmurHash3(bit_cast<uint64_t>(seed));
    130   state1_ = MurmurHash3(state0_);
    131 }
    132 
    133 
    134 uint64_t RandomNumberGenerator::MurmurHash3(uint64_t h) {
    135   h ^= h >> 33;
    136   h *= V8_UINT64_C(0xFF51AFD7ED558CCD);
    137   h ^= h >> 33;
    138   h *= V8_UINT64_C(0xC4CEB9FE1A85EC53);
    139   h ^= h >> 33;
    140   return h;
    141 }
    142 
    143 }  // namespace base
    144 }  // namespace v8
    145