src/base/utils/random-number-generator.cc

   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   return ((static_cast<int64_t>(Next(26)) << 27) + Next(27)) /
 101       static_cast<double>(static_cast<int64_t>(1) << 53);
 102 }
 103
 104
 105 int64_t RandomNumberGenerator::NextInt64() {
 106   uint64_t lo = bit_cast<unsigned>(Next(32));
 107   uint64_t hi = bit_cast<unsigned>(Next(32));
 108   return lo | (hi << 32);
 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
 119 int RandomNumberGenerator::Next(int bits) {
 120   DCHECK_LT(0, bits);
 121   DCHECK_GE(32, bits);
 122   // Do unsigned multiplication, which has the intended modulo semantics, while
 123   // signed multiplication would expose undefined behavior.
 124   uint64_t product = static_cast<uint64_t>(seed_) * kMultiplier;
 125   // Assigning a uint64_t to an int64_t is implementation defined, but this
 126   // should be OK. Use a static_cast to explicitly state that we know what we're
 127   // doing. (Famous last words...)
 128   int64_t seed = static_cast<int64_t>((product + kAddend) & kMask);
 129   seed_ = seed;
 130   return static_cast<int>(seed >> (48 - bits));
 131 }
 132
 133
 134 void RandomNumberGenerator::SetSeed(int64_t seed) {
 135   initial_seed_ = seed;
 136   seed_ = (seed ^ kMultiplier) & kMask;
 137 }
 138
 139 }  // namespace base
 140 }  // namespace v8