Line data Source code
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 0 : void RandomNumberGenerator::SetEntropySource(EntropySource source) {
25 : LockGuard<Mutex> lock_guard(entropy_mutex.Pointer());
26 0 : entropy_source = source;
27 0 : }
28 :
29 :
30 77383 : RandomNumberGenerator::RandomNumberGenerator() {
31 : // Check if embedder supplied an entropy source.
32 : { LockGuard<Mutex> lock_guard(entropy_mutex.Pointer());
33 77383 : if (entropy_source != NULL) {
34 : int64_t seed;
35 0 : if (entropy_source(reinterpret_cast<unsigned char*>(&seed),
36 : sizeof(seed))) {
37 0 : SetSeed(seed);
38 0 : 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 77383 : FILE* fp = fopen("/dev/urandom", "rb");
55 77383 : if (fp != NULL) {
56 : int64_t seed;
57 : size_t n = fread(&seed, sizeof(seed), 1, fp);
58 77383 : fclose(fp);
59 77383 : if (n == 1) {
60 77383 : SetSeed(seed);
61 77383 : 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 0 : int64_t seed = Time::NowFromSystemTime().ToInternalValue() << 24;
74 0 : seed ^= TimeTicks::HighResolutionNow().ToInternalValue() << 16;
75 0 : seed ^= TimeTicks::Now().ToInternalValue() << 8;
76 0 : SetSeed(seed);
77 : #endif // V8_OS_CYGWIN || V8_OS_WIN
78 : }
79 :
80 :
81 67061672 : int RandomNumberGenerator::NextInt(int max) {
82 : DCHECK_LT(0, max);
83 :
84 : // Fast path if max is a power of 2.
85 67061672 : if (IS_POWER_OF_TWO(max)) {
86 2005966 : return static_cast<int>((max * static_cast<int64_t>(Next(31))) >> 31);
87 : }
88 :
89 : while (true) {
90 : int rnd = Next(31);
91 66058690 : int val = rnd % max;
92 66058690 : if (rnd - val + (max - 1) >= 0) {
93 : return val;
94 : }
95 : }
96 : }
97 :
98 :
99 133107 : double RandomNumberGenerator::NextDouble() {
100 : XorShift128(&state0_, &state1_);
101 133107 : return ToDouble(state0_, state1_);
102 : }
103 :
104 :
105 0 : int64_t RandomNumberGenerator::NextInt64() {
106 : XorShift128(&state0_, &state1_);
107 0 : return bit_cast<int64_t>(state0_ + state1_);
108 : }
109 :
110 :
111 706764 : void RandomNumberGenerator::NextBytes(void* buffer, size_t buflen) {
112 19013490 : for (size_t n = 0; n < buflen; ++n) {
113 36613452 : static_cast<uint8_t*>(buffer)[n] = static_cast<uint8_t>(Next(8));
114 : }
115 706764 : }
116 :
117 :
118 590091509 : int RandomNumberGenerator::Next(int bits) {
119 : DCHECK_LT(0, bits);
120 : DCHECK_GE(32, bits);
121 : XorShift128(&state0_, &state1_);
122 675459908 : return static_cast<int>((state0_ + state1_) >> (64 - bits));
123 : }
124 :
125 :
126 215906 : void RandomNumberGenerator::SetSeed(int64_t seed) {
127 215906 : initial_seed_ = seed;
128 215906 : state0_ = MurmurHash3(bit_cast<uint64_t>(seed));
129 431812 : state1_ = MurmurHash3(~state0_);
130 215906 : CHECK(state0_ != 0 || state1_ != 0);
131 215906 : }
132 :
133 :
134 0 : uint64_t RandomNumberGenerator::MurmurHash3(uint64_t h) {
135 431812 : h ^= h >> 33;
136 431812 : h *= V8_UINT64_C(0xFF51AFD7ED558CCD);
137 431812 : h ^= h >> 33;
138 431812 : h *= V8_UINT64_C(0xC4CEB9FE1A85EC53);
139 431812 : h ^= h >> 33;
140 0 : return h;
141 : }
142 :
143 : } // namespace base
144 : } // namespace v8
|