Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 1 | // Copyright 2013 the V8 project authors. All rights reserved. |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 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 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 28 | #include "src/v8.h" |
| 29 | #include "test/cctest/cctest.h" |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 30 | |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 31 | #include "src/base/utils/random-number-generator.h" |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 32 | |
| 33 | using namespace v8::internal; |
| 34 | |
| 35 | |
| 36 | static const int64_t kRandomSeeds[] = {-1, 1, 42, 100, 1234567890, 987654321}; |
| 37 | |
| 38 | |
| 39 | TEST(RandomSeedFlagIsUsed) { |
| 40 | for (unsigned n = 0; n < arraysize(kRandomSeeds); ++n) { |
| 41 | FLAG_random_seed = static_cast<int>(kRandomSeeds[n]); |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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); |
Ben Murdoch | b8a8cc1 | 2014-11-26 15:28:44 +0000 | [diff] [blame] | 45 | v8::base::RandomNumberGenerator& rng = |
| 46 | *reinterpret_cast<Isolate*>(i)->random_number_generator(); |
| 47 | CHECK_EQ(kRandomSeeds[n], rng.initial_seed()); |
| 48 | i->Dispose(); |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 49 | } |
Steve Block | a7e24c1 | 2009-10-30 11:49:00 +0000 | [diff] [blame] | 50 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 51 | |
| 52 | |
| 53 | // Chi squared for getting m 0s out of n bits. |
| 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. |
| 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 |