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/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/platform/mutex.h"
     14 #include "src/platform/time.h"
     15 
     16 namespace v8 {
     17 namespace internal {
     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   ASSERT_EQ(0, result);
     49   result = rand_s(&second_half);
     50   ASSERT_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   ASSERT_LE(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   return ((static_cast<int64_t>(Next(26)) << 27) + Next(27)) /
    101       static_cast<double>(static_cast<int64_t>(1) << 53);
    102 }
    103 
    104 
    105 void RandomNumberGenerator::NextBytes(void* buffer, size_t buflen) {
    106   for (size_t n = 0; n < buflen; ++n) {
    107     static_cast<uint8_t*>(buffer)[n] = static_cast<uint8_t>(Next(8));
    108   }
    109 }
    110 
    111 
    112 int RandomNumberGenerator::Next(int bits) {
    113   ASSERT_LT(0, bits);
    114   ASSERT_GE(32, bits);
    115   // Do unsigned multiplication, which has the intended modulo semantics, while
    116   // signed multiplication would expose undefined behavior.
    117   uint64_t product = static_cast<uint64_t>(seed_) * kMultiplier;
    118   // Assigning a uint64_t to an int64_t is implementation defined, but this
    119   // should be OK. Use a static_cast to explicitly state that we know what we're
    120   // doing. (Famous last words...)
    121   int64_t seed = static_cast<int64_t>((product + kAddend) & kMask);
    122   seed_ = seed;
    123   return static_cast<int>(seed >> (48 - bits));
    124 }
    125 
    126 
    127 void RandomNumberGenerator::SetSeed(int64_t seed) {
    128   seed_ = (seed ^ kMultiplier) & kMask;
    129 }
    130 
    131 } }  // namespace v8::internal
    132