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