random-number-generator.cc revision 13e2dadd00298019ed862f2b2fc5068bba730bcf 
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
16namespace v8 {
17namespace base {
18
19static LazyMutex entropy_mutex = LAZY_MUTEX_INITIALIZER;
20static RandomNumberGenerator::EntropySource entropy_source = NULL;
21
22
23// static
24void RandomNumberGenerator::SetEntropySource(EntropySource source) {
25  LockGuard<Mutex> lock_guard(entropy_mutex.Pointer());
26  entropy_source = source;
27}
28
29
30RandomNumberGenerator::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
81int 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
99double RandomNumberGenerator::NextDouble() {
100  XorShift128(&state0_, &state1_);
101  return ToDouble(state0_, state1_);
102}
103
104
105int64_t RandomNumberGenerator::NextInt64() {
106  XorShift128(&state0_, &state1_);
107  return bit_cast<int64_t>(state0_ + state1_);
108}
109
110
111void 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
118int 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
126void RandomNumberGenerator::SetSeed(int64_t seed) {
127  initial_seed_ = seed;
128  state0_ = MurmurHash3(bit_cast<uint64_t>(seed));
129  state1_ = MurmurHash3(~state0_);
130  CHECK(state0_ != 0 || state1_ != 0);
131}
132
133
134uint64_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