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