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
SetEntropySource(EntropySource source)46 void RandomNumberGenerator::SetEntropySource(EntropySource source) {
47 LockGuard<Mutex> lock_guard(entropy_mutex.Pointer());
48 entropy_source = source;
49 }
50
51
RandomNumberGenerator()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
NextInt(int max)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
NextDouble()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
NextBytes(void * buffer,size_t buflen)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
Next(int bits)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
SetSeed(int64_t seed)149 void RandomNumberGenerator::SetSeed(int64_t seed) {
150 seed_ = (seed ^ kMultiplier) & kMask;
151 }
152
153 } } // namespace v8::internal
154