Home | History | Annotate | Download | only in utils 
      1 // Copyright 2013 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 #include "utils/random-number-generator.h"
     29 
     30 #include <cstdio>
     31 #include <cstdlib>
     32 
     33 #include "flags.h"
     34 #include "platform/mutex.h"
     35 #include "platform/time.h"
     36 #include "utils.h"
     37 
     38 namespace v8 {
     39 namespace internal {
     40 
     41 static LazyMutex entropy_mutex = LAZY_MUTEX_INITIALIZER;
     42 static RandomNumberGenerator::EntropySource entropy_source = NULL;
     43 
     44 
     45 // static
     46 void RandomNumberGenerator::SetEntropySource(EntropySource source) {
     47   LockGuard<Mutex> lock_guard(entropy_mutex.Pointer());
     48   entropy_source = source;
     49 }
     50 
     51 
     52 RandomNumberGenerator::RandomNumberGenerator() {
     53   // Check --random-seed flag first.
     54   if (FLAG_random_seed != 0) {
     55     SetSeed(FLAG_random_seed);
     56     return;
     57   }
     58 
     59   // Check if embedder supplied an entropy source.
     60   { LockGuard<Mutex> lock_guard(entropy_mutex.Pointer());
     61     if (entropy_source != NULL) {
     62       int64_t seed;
     63       if (entropy_source(reinterpret_cast<unsigned char*>(&seed),
     64                          sizeof(seed))) {
     65         SetSeed(seed);
     66         return;
     67       }
     68     }
     69   }
     70 
     71 #if V8_OS_CYGWIN || V8_OS_WIN
     72   // Use rand_s() to gather entropy on Windows. See:
     73   // https://code.google.com/p/v8/issues/detail?id=2905
     74   unsigned first_half, second_half;
     75   errno_t result = rand_s(&first_half);
     76   ASSERT_EQ(0, result);
     77   result = rand_s(&second_half);
     78   ASSERT_EQ(0, result);
     79   SetSeed((static_cast<int64_t>(first_half) << 32) + second_half);
     80 #else
     81   // Gather entropy from /dev/urandom if available.
     82   FILE* fp = fopen("/dev/urandom", "rb");
     83   if (fp != NULL) {
     84     int64_t seed;
     85     size_t n = fread(&seed, sizeof(seed), 1, fp);
     86     fclose(fp);
     87     if (n == 1) {
     88       SetSeed(seed);
     89       return;
     90     }
     91   }
     92 
     93   // We cannot assume that random() or rand() were seeded
     94   // properly, so instead of relying on random() or rand(),
     95   // we just seed our PRNG using timing data as fallback.
     96   // This is weak entropy, but it's sufficient, because
     97   // it is the responsibility of the embedder to install
     98   // an entropy source using v8::V8::SetEntropySource(),
     99   // which provides reasonable entropy, see:
    100   // https://code.google.com/p/v8/issues/detail?id=2905
    101   int64_t seed = Time::NowFromSystemTime().ToInternalValue() << 24;
    102   seed ^= TimeTicks::HighResolutionNow().ToInternalValue() << 16;
    103   seed ^= TimeTicks::Now().ToInternalValue() << 8;
    104   SetSeed(seed);
    105 #endif  // V8_OS_CYGWIN || V8_OS_WIN
    106 }
    107 
    108 
    109 int RandomNumberGenerator::NextInt(int max) {
    110   ASSERT_LE(0, max);
    111 
    112   // Fast path if max is a power of 2.
    113   if (IsPowerOf2(max)) {
    114     return static_cast<int>((max * static_cast<int64_t>(Next(31))) >> 31);
    115   }
    116 
    117   while (true) {
    118     int rnd = Next(31);
    119     int val = rnd % max;
    120     if (rnd - val + (max - 1) >= 0) {
    121       return val;
    122     }
    123   }
    124 }
    125 
    126 
    127 double RandomNumberGenerator::NextDouble() {
    128   return ((static_cast<int64_t>(Next(26)) << 27) + Next(27)) /
    129       static_cast<double>(static_cast<int64_t>(1) << 53);
    130 }
    131 
    132 
    133 void RandomNumberGenerator::NextBytes(void* buffer, size_t buflen) {
    134   for (size_t n = 0; n < buflen; ++n) {
    135     static_cast<uint8_t*>(buffer)[n] = static_cast<uint8_t>(Next(8));
    136   }
    137 }
    138 
    139 
    140 int RandomNumberGenerator::Next(int bits) {
    141   ASSERT_LT(0, bits);
    142   ASSERT_GE(32, bits);
    143   int64_t seed = (seed_ * kMultiplier + kAddend) & kMask;
    144   seed_ = seed;
    145   return static_cast<int>(seed >> (48 - bits));
    146 }
    147 
    148 
    149 void RandomNumberGenerator::SetSeed(int64_t seed) {
    150   seed_ = (seed ^ kMultiplier) & kMask;
    151 }
    152 
    153 } }  // namespace v8::internal
    154