OLD | NEW |
---|---|
1 // Copyright 2013 the V8 project authors. All rights reserved. | 1 // Copyright 2013 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
44 FLAG_random_seed = static_cast<int>(kRandomSeeds[n]); | 44 FLAG_random_seed = static_cast<int>(kRandomSeeds[n]); |
45 v8::Isolate::CreateParams create_params; | 45 v8::Isolate::CreateParams create_params; |
46 create_params.array_buffer_allocator = CcTest::array_buffer_allocator(); | 46 create_params.array_buffer_allocator = CcTest::array_buffer_allocator(); |
47 v8::Isolate* i = v8::Isolate::New(create_params); | 47 v8::Isolate* i = v8::Isolate::New(create_params); |
48 v8::base::RandomNumberGenerator& rng = | 48 v8::base::RandomNumberGenerator& rng = |
49 *reinterpret_cast<Isolate*>(i)->random_number_generator(); | 49 *reinterpret_cast<Isolate*>(i)->random_number_generator(); |
50 CHECK_EQ(kRandomSeeds[n], rng.initial_seed()); | 50 CHECK_EQ(kRandomSeeds[n], rng.initial_seed()); |
51 i->Dispose(); | 51 i->Dispose(); |
52 } | 52 } |
53 } | 53 } |
54 | |
55 | |
56 // The test below originates from Dart/Fletch with the following license: | |
57 | |
58 // Copyright (c) 2015, the Fletch project authors. | |
59 // All rights reserved. | |
60 // | |
61 // Redistribution and use in source and binary forms, with or without | |
62 // modification, are permitted provided that the following conditions are met: | |
63 // | |
64 // * Redistributions of source code must retain the above copyright notice, this | |
65 // list of conditions and the following disclaimer. | |
66 // | |
67 // * Redistributions in binary form must reproduce the above copyright notice, | |
68 // this list of conditions and the following disclaimer in the documentation | |
69 // and/or other materials provided with the distribution. | |
70 // | |
71 // * Neither the name of Google Inc. nor the names of its | |
72 // contributors may be used to endorse or promote products derived from | |
73 // this software without specific prior written permission. | |
74 // | |
75 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | |
76 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
77 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
78 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | |
79 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | |
80 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | |
81 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | |
82 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | |
83 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
84 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | |
85 // POSSIBILITY OF SUCH DAMAGE. | |
erikcorry
2015/11/24 13:45:14
You don't need this. It's written by me for Googl
Yang
2015/11/24 13:46:55
And... removed.
| |
86 | |
87 // Chi squared for getting m 0s out of n bits. | |
88 double ChiSquared(int m, int n) { | |
89 double ys_minus_np1 = (m - n / 2.0); | |
90 double chi_squared_1 = ys_minus_np1 * ys_minus_np1 * 2.0 / n; | |
91 double ys_minus_np2 = ((n - m) - n / 2.0); | |
92 double chi_squared_2 = ys_minus_np2 * ys_minus_np2 * 2.0 / n; | |
93 return chi_squared_1 + chi_squared_2; | |
94 } | |
95 | |
96 | |
97 // Test for correlations between recent bits from the PRNG, or bits that are | |
98 // biased. | |
99 TEST(RandomBitCorrelations) { | |
100 FLAG_random_seed = 31415926; | |
101 LocalContext env; | |
102 v8::Isolate* isolate = env->GetIsolate(); | |
103 v8::HandleScope scope(isolate); | |
104 const char* source = | |
105 "(function() {" | |
106 " return (Math.random() * Math.pow(2, 32)) >>> 0;" | |
107 "})"; | |
108 v8::Local<v8::Context> context = isolate->GetCurrentContext(); | |
109 v8::Local<v8::Function> random_fun = v8::Local<v8::Function>::Cast( | |
110 CompileRun(context, source).ToLocalChecked()); | |
111 v8::Local<v8::Value> undefined = v8::Undefined(isolate); | |
112 | |
113 #ifdef DEBUG | |
114 const int kHistory = 2; | |
115 const int kRepeats = 1000; | |
116 #else | |
117 const int kHistory = 8; | |
118 const int kRepeats = 10000; | |
119 #endif | |
120 uint32_t history[kHistory]; | |
121 // The predictor bit is either constant 0 or 1, or one of the bits from the | |
122 // history. | |
123 for (int predictor_bit = -2; predictor_bit < 32; predictor_bit++) { | |
124 // The predicted bit is one of the bits from the PRNG. | |
125 for (int random_bit = 0; random_bit < 32; random_bit++) { | |
126 // The predicted bit is taken from the previous output of the PRNG. | |
127 for (int ago = 0; ago < kHistory; ago++) { | |
128 // We don't want to check whether each bit predicts itself. | |
129 if (ago == 0 && predictor_bit == random_bit) continue; | |
130 | |
131 // Enter the new random value into the history | |
132 for (int i = ago; i >= 0; i--) { | |
133 v8::HandleScope scope(isolate); | |
134 history[i] = random_fun->Call(context, undefined, 0, NULL) | |
135 .ToLocalChecked() | |
136 ->Uint32Value(context) | |
137 .FromJust(); | |
138 } | |
139 | |
140 // Find out how many of the bits are the same as the prediction bit. | |
141 int m = 0; | |
142 for (int i = 0; i < kRepeats; i++) { | |
143 v8::HandleScope scope(isolate); | |
144 uint32_t random = random_fun->Call(context, undefined, 0, NULL) | |
145 .ToLocalChecked() | |
146 ->Uint32Value(context) | |
147 .FromJust(); | |
148 for (int j = ago - 1; j >= 0; j--) history[j + 1] = history[j]; | |
149 history[0] = random; | |
150 | |
151 int predicted; | |
152 if (predictor_bit >= 0) { | |
153 predicted = (history[ago] >> predictor_bit) & 1; | |
154 } else { | |
155 predicted = predictor_bit == -2 ? 0 : 1; | |
156 } | |
157 int bit = (random >> random_bit) & 1; | |
158 if (bit == predicted) m++; | |
159 } | |
160 | |
161 // Chi squared analysis for k = 2 (2, states: same/not-same) and one | |
162 // degree of freedom (k - 1). | |
163 double chi_squared = ChiSquared(m, kRepeats); | |
164 if (chi_squared > 24) { | |
165 int percent = static_cast<int>(m * 100.0 / kRepeats); | |
166 if (predictor_bit < 0) { | |
167 PrintF("Bit %d is %d %d%% of the time\n", random_bit, | |
168 predictor_bit == -2 ? 0 : 1, percent); | |
169 } else { | |
170 PrintF("Bit %d is the same as bit %d %d ago %d%% of the time\n", | |
171 random_bit, predictor_bit, ago, percent); | |
172 } | |
173 } | |
174 | |
175 // For 1 degree of freedom this corresponds to 1 in a million. We are | |
176 // running ~8000 tests, so that would be surprising. | |
177 CHECK(chi_squared <= 24); | |
178 | |
179 // If the predictor bit is a fixed 0 or 1 then it makes no sense to | |
180 // repeat the test with a different age. | |
181 if (predictor_bit < 0) break; | |
182 } | |
183 } | |
184 } | |
185 } | |
OLD | NEW |