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
SetEntropySource(EntropySource source)24 void RandomNumberGenerator::SetEntropySource(EntropySource source) {
25 LockGuard<Mutex> lock_guard(entropy_mutex.Pointer());
26 entropy_source = source;
27 }
28
29
RandomNumberGenerator()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
NextInt(int max)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
NextDouble()99 double RandomNumberGenerator::NextDouble() {
100 XorShift128(&state0_, &state1_);
101 return ToDouble(state0_, state1_);
102 }
103
104
NextInt64()105 int64_t RandomNumberGenerator::NextInt64() {
106 XorShift128(&state0_, &state1_);
107 return bit_cast<int64_t>(state0_ + state1_);
108 }
109
110
NextBytes(void * buffer,size_t buflen)111 void 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
Next(int bits)118 int 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
SetSeed(int64_t seed)126 void 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
MurmurHash3(uint64_t h)134 uint64_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