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 "src/v8.h"
29 #include "test/cctest/cctest.h"
30
31 #include "src/base/utils/random-number-generator.h"
32
33 using namespace v8::internal;
34
35
36 static const int64_t kRandomSeeds[] = {-1, 1, 42, 100, 1234567890, 987654321};
37
38
TEST(RandomSeedFlagIsUsed)39 TEST(RandomSeedFlagIsUsed) {
40 for (unsigned n = 0; n < arraysize(kRandomSeeds); ++n) {
41 FLAG_random_seed = static_cast<int>(kRandomSeeds[n]);
42 v8::Isolate::CreateParams create_params;
43 create_params.array_buffer_allocator = CcTest::array_buffer_allocator();
44 v8::Isolate* i = v8::Isolate::New(create_params);
45 v8::base::RandomNumberGenerator& rng =
46 *reinterpret_cast<Isolate*>(i)->random_number_generator();
47 CHECK_EQ(kRandomSeeds[n], rng.initial_seed());
48 i->Dispose();
49 }
50 }
51
52
53 // Chi squared for getting m 0s out of n bits.
ChiSquared(int m,int n)54 double ChiSquared(int m, int n) {
55 double ys_minus_np1 = (m - n / 2.0);
56 double chi_squared_1 = ys_minus_np1 * ys_minus_np1 * 2.0 / n;
57 double ys_minus_np2 = ((n - m) - n / 2.0);
58 double chi_squared_2 = ys_minus_np2 * ys_minus_np2 * 2.0 / n;
59 return chi_squared_1 + chi_squared_2;
60 }
61
62
63 // Test for correlations between recent bits from the PRNG, or bits that are
64 // biased.
RandomBitCorrelation(int random_bit)65 void RandomBitCorrelation(int random_bit) {
66 FLAG_random_seed = 31415926;
67 v8::Isolate::CreateParams create_params;
68 create_params.array_buffer_allocator = CcTest::array_buffer_allocator();
69 v8::Isolate* isolate = v8::Isolate::New(create_params);
70 Isolate* i_isolate = reinterpret_cast<Isolate*>(isolate);
71 v8::base::RandomNumberGenerator* rng = i_isolate->random_number_generator();
72 #ifdef DEBUG
73 const int kHistory = 2;
74 const int kRepeats = 1000;
75 #else
76 const int kHistory = 8;
77 const int kRepeats = 10000;
78 #endif
79 uint32_t history[kHistory];
80 // The predictor bit is either constant 0 or 1, or one of the bits from the
81 // history.
82 for (int predictor_bit = -2; predictor_bit < 32; predictor_bit++) {
83 // The predicted bit is one of the bits from the PRNG.
84 for (int ago = 0; ago < kHistory; ago++) {
85 // We don't want to check whether each bit predicts itself.
86 if (ago == 0 && predictor_bit == random_bit) continue;
87
88 // Enter the new random value into the history
89 for (int i = ago; i >= 0; i--) {
90 history[i] = bit_cast<uint32_t>(rng->NextInt());
91 }
92
93 // Find out how many of the bits are the same as the prediction bit.
94 int m = 0;
95 for (int i = 0; i < kRepeats; i++) {
96 v8::HandleScope scope(isolate);
97 uint32_t random = bit_cast<uint32_t>(rng->NextInt());
98 for (int j = ago - 1; j >= 0; j--) history[j + 1] = history[j];
99 history[0] = random;
100
101 int predicted;
102 if (predictor_bit >= 0) {
103 predicted = (history[ago] >> predictor_bit) & 1;
104 } else {
105 predicted = predictor_bit == -2 ? 0 : 1;
106 }
107 int bit = (random >> random_bit) & 1;
108 if (bit == predicted) m++;
109 }
110
111 // Chi squared analysis for k = 2 (2, states: same/not-same) and one
112 // degree of freedom (k - 1).
113 double chi_squared = ChiSquared(m, kRepeats);
114 if (chi_squared > 24) {
115 int percent = static_cast<int>(m * 100.0 / kRepeats);
116 if (predictor_bit < 0) {
117 PrintF("Bit %d is %d %d%% of the time\n", random_bit,
118 predictor_bit == -2 ? 0 : 1, percent);
119 } else {
120 PrintF("Bit %d is the same as bit %d %d ago %d%% of the time\n",
121 random_bit, predictor_bit, ago, percent);
122 }
123 }
124
125 // For 1 degree of freedom this corresponds to 1 in a million. We are
126 // running ~8000 tests, so that would be surprising.
127 CHECK(chi_squared <= 24);
128
129 // If the predictor bit is a fixed 0 or 1 then it makes no sense to
130 // repeat the test with a different age.
131 if (predictor_bit < 0) break;
132 }
133 }
134 isolate->Dispose();
135 }
136
137
138 #define TEST_RANDOM_BIT(BIT) \
139 TEST(RandomBitCorrelations##BIT) { RandomBitCorrelation(BIT); }
140
141 TEST_RANDOM_BIT(0)
142 TEST_RANDOM_BIT(1)
143 TEST_RANDOM_BIT(2)
144 TEST_RANDOM_BIT(3)
145 TEST_RANDOM_BIT(4)
146 TEST_RANDOM_BIT(5)
147 TEST_RANDOM_BIT(6)
148 TEST_RANDOM_BIT(7)
149 TEST_RANDOM_BIT(8)
150 TEST_RANDOM_BIT(9)
151 TEST_RANDOM_BIT(10)
152 TEST_RANDOM_BIT(11)
153 TEST_RANDOM_BIT(12)
154 TEST_RANDOM_BIT(13)
155 TEST_RANDOM_BIT(14)
156 TEST_RANDOM_BIT(15)
157 TEST_RANDOM_BIT(16)
158 TEST_RANDOM_BIT(17)
159 TEST_RANDOM_BIT(18)
160 TEST_RANDOM_BIT(19)
161 TEST_RANDOM_BIT(20)
162 TEST_RANDOM_BIT(21)
163 TEST_RANDOM_BIT(22)
164 TEST_RANDOM_BIT(23)
165 TEST_RANDOM_BIT(24)
166 TEST_RANDOM_BIT(25)
167 TEST_RANDOM_BIT(26)
168 TEST_RANDOM_BIT(27)
169 TEST_RANDOM_BIT(28)
170 TEST_RANDOM_BIT(29)
171 TEST_RANDOM_BIT(30)
172 TEST_RANDOM_BIT(31)
173
174 #undef TEST_RANDOM_BIT
175