jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2013 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 8 | #include "SkRandom.h" |
| 9 | #include "SkTSort.h" |
tfarina@chromium.org | 8f6884a | 2014-01-24 20:56:26 +0000 | [diff] [blame] | 10 | #include "Test.h" |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 11 | |
jvanverth@google.com | 897f462 | 2013-02-08 18:28:47 +0000 | [diff] [blame] | 12 | static bool anderson_darling_test(double p[32]) { |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 13 | // Min and max Anderson-Darling values allowable for k=32 |
| 14 | const double kADMin32 = 0.202; // p-value of ~0.1 |
| 15 | const double kADMax32 = 3.89; // p-value of ~0.99 |
| 16 | |
| 17 | // sort p values |
| 18 | SkTQSort<double>(p, p + 31); |
| 19 | |
| 20 | // and compute Anderson-Darling statistic to ensure these are uniform |
| 21 | double s = 0.0; |
| 22 | for(int k = 0; k < 32; k++) { |
| 23 | double v = p[k]*(1.0 - p[31-k]); |
| 24 | if (v < 1.0e-30) { |
| 25 | v = 1.0e-30; |
| 26 | } |
| 27 | s += (2.0*(k+1)-1.0)*log(v); |
| 28 | } |
| 29 | double a2 = -32.0 - 0.03125*s; |
| 30 | |
| 31 | return (kADMin32 < a2 && a2 < kADMax32); |
| 32 | } |
| 33 | |
jvanverth@google.com | 897f462 | 2013-02-08 18:28:47 +0000 | [diff] [blame] | 34 | static bool chi_square_test(int bins[256], int e) { |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 35 | // Min and max chisquare values allowable |
| 36 | const double kChiSqMin256 = 206.3179; // probability of chance = 0.99 with k=256 |
| 37 | const double kChiSqMax256 = 311.5603; // probability of chance = 0.01 with k=256 |
| 38 | |
| 39 | // compute chi-square |
| 40 | double chi2 = 0.0; |
| 41 | for (int j = 0; j < 256; ++j) { |
| 42 | double delta = bins[j] - e; |
| 43 | chi2 += delta*delta/e; |
| 44 | } |
| 45 | |
| 46 | return (kChiSqMin256 < chi2 && chi2 < kChiSqMax256); |
| 47 | } |
| 48 | |
| 49 | // Approximation to the normal distribution CDF |
| 50 | // From Waissi and Rossin, 1996 |
jvanverth@google.com | 897f462 | 2013-02-08 18:28:47 +0000 | [diff] [blame] | 51 | static double normal_cdf(double z) { |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 52 | double t = ((-0.0004406*z*z* + 0.0418198)*z*z + 0.9)*z; |
| 53 | t *= -1.77245385091; // -sqrt(PI) |
| 54 | double p = 1.0/(1.0 + exp(t)); |
| 55 | |
| 56 | return p; |
| 57 | } |
| 58 | |
jvanverth@google.com | 897f462 | 2013-02-08 18:28:47 +0000 | [diff] [blame] | 59 | static void test_random_byte(skiatest::Reporter* reporter, int shift) { |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 60 | int bins[256]; |
| 61 | memset(bins, 0, sizeof(int)*256); |
| 62 | |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 63 | SkRandom rand; |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 64 | for (int i = 0; i < 256*10000; ++i) { |
| 65 | bins[(rand.nextU() >> shift) & 0xff]++; |
| 66 | } |
skia.committer@gmail.com | 8626719 | 2013-02-09 07:05:02 +0000 | [diff] [blame] | 67 | |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 68 | REPORTER_ASSERT(reporter, chi_square_test(bins, 10000)); |
| 69 | } |
| 70 | |
jvanverth@google.com | 897f462 | 2013-02-08 18:28:47 +0000 | [diff] [blame] | 71 | static void test_random_float(skiatest::Reporter* reporter) { |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 72 | int bins[256]; |
| 73 | memset(bins, 0, sizeof(int)*256); |
| 74 | |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 75 | SkRandom rand; |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 76 | for (int i = 0; i < 256*10000; ++i) { |
| 77 | float f = rand.nextF(); |
| 78 | REPORTER_ASSERT(reporter, 0.0f <= f && f < 1.0f); |
| 79 | bins[(int)(f*256.f)]++; |
| 80 | } |
| 81 | REPORTER_ASSERT(reporter, chi_square_test(bins, 10000)); |
| 82 | |
| 83 | double p[32]; |
| 84 | for (int j = 0; j < 32; ++j) { |
| 85 | float f = rand.nextF(); |
| 86 | REPORTER_ASSERT(reporter, 0.0f <= f && f < 1.0f); |
| 87 | p[j] = f; |
| 88 | } |
| 89 | REPORTER_ASSERT(reporter, anderson_darling_test(p)); |
| 90 | } |
| 91 | |
| 92 | // This is a test taken from tuftests by Marsaglia and Tsang. The idea here is that |
| 93 | // we are using the random bit generated from a single shift position to generate |
skia.committer@gmail.com | 8626719 | 2013-02-09 07:05:02 +0000 | [diff] [blame] | 94 | // "strings" of 16 bits in length, shifting the string and adding a new bit with each |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 95 | // iteration. We track the numbers generated. The ones that we don't generate will |
skia.committer@gmail.com | 8626719 | 2013-02-09 07:05:02 +0000 | [diff] [blame] | 96 | // have a normal distribution with mean ~24108 and standard deviation ~127. By |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 97 | // creating a z-score (# of deviations from the mean) for one iteration of this step |
| 98 | // we can determine its probability. |
| 99 | // |
skia.committer@gmail.com | 8626719 | 2013-02-09 07:05:02 +0000 | [diff] [blame] | 100 | // The original test used 26 bit strings, but is somewhat slow. This version uses 16 |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 101 | // bits which is less rigorous but much faster to generate. |
jvanverth@google.com | 897f462 | 2013-02-08 18:28:47 +0000 | [diff] [blame] | 102 | static double test_single_gorilla(skiatest::Reporter* reporter, int shift) { |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 103 | const int kWordWidth = 16; |
| 104 | const double kMean = 24108.0; |
| 105 | const double kStandardDeviation = 127.0; |
| 106 | const int kN = (1 << kWordWidth); |
| 107 | const int kNumEntries = kN >> 5; // dividing by 32 |
| 108 | unsigned int entries[kNumEntries]; |
| 109 | |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 110 | SkRandom rand; |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 111 | memset(entries, 0, sizeof(unsigned int)*kNumEntries); |
| 112 | // pre-seed our string value |
| 113 | int value = 0; |
| 114 | for (int i = 0; i < kWordWidth-1; ++i) { |
| 115 | value <<= 1; |
| 116 | unsigned int rnd = rand.nextU(); |
| 117 | value |= ((rnd >> shift) & 0x1); |
| 118 | } |
| 119 | |
| 120 | // now make some strings and track them |
| 121 | for (int i = 0; i < kN; ++i) { |
caryclark | 3127c99 | 2015-12-09 12:02:30 -0800 | [diff] [blame^] | 122 | value = SkLeftShift(value, 1); |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 123 | unsigned int rnd = rand.nextU(); |
| 124 | value |= ((rnd >> shift) & 0x1); |
| 125 | |
| 126 | int index = value & (kNumEntries-1); |
| 127 | SkASSERT(index < kNumEntries); |
jvanverth@google.com | 024e523 | 2013-02-14 13:20:35 +0000 | [diff] [blame] | 128 | int entry_shift = (value >> (kWordWidth-5)) & 0x1f; |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 129 | entries[index] |= (0x1 << entry_shift); |
| 130 | } |
| 131 | |
| 132 | // count entries |
| 133 | int total = 0; |
| 134 | for (int i = 0; i < kNumEntries; ++i) { |
| 135 | unsigned int entry = entries[i]; |
| 136 | while (entry) { |
| 137 | total += (entry & 0x1); |
| 138 | entry >>= 1; |
| 139 | } |
| 140 | } |
| 141 | |
| 142 | // convert counts to normal distribution z-score |
skia.committer@gmail.com | 8626719 | 2013-02-09 07:05:02 +0000 | [diff] [blame] | 143 | double z = ((kN-total)-kMean)/kStandardDeviation; |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 144 | |
skia.committer@gmail.com | 8626719 | 2013-02-09 07:05:02 +0000 | [diff] [blame] | 145 | // compute probability from normal distibution CDF |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 146 | double p = normal_cdf(z); |
| 147 | |
jvanverth@google.com | 024e523 | 2013-02-14 13:20:35 +0000 | [diff] [blame] | 148 | REPORTER_ASSERT(reporter, 0.01 < p && p < 0.99); |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 149 | return p; |
| 150 | } |
| 151 | |
jvanverth@google.com | 897f462 | 2013-02-08 18:28:47 +0000 | [diff] [blame] | 152 | static void test_gorilla(skiatest::Reporter* reporter) { |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 153 | |
| 154 | double p[32]; |
| 155 | for (int bit_position = 0; bit_position < 32; ++bit_position) { |
| 156 | p[bit_position] = test_single_gorilla(reporter, bit_position); |
| 157 | } |
skia.committer@gmail.com | 8626719 | 2013-02-09 07:05:02 +0000 | [diff] [blame] | 158 | |
jvanverth@google.com | 024e523 | 2013-02-14 13:20:35 +0000 | [diff] [blame] | 159 | REPORTER_ASSERT(reporter, anderson_darling_test(p)); |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 160 | } |
| 161 | |
jvanverth@google.com | 897f462 | 2013-02-08 18:28:47 +0000 | [diff] [blame] | 162 | static void test_range(skiatest::Reporter* reporter) { |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 163 | SkRandom rand; |
skia.committer@gmail.com | 8626719 | 2013-02-09 07:05:02 +0000 | [diff] [blame] | 164 | |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 165 | // just to make sure we don't crash in this case |
| 166 | (void) rand.nextRangeU(0, 0xffffffff); |
| 167 | |
| 168 | // check a case to see if it's uniform |
| 169 | int bins[256]; |
| 170 | memset(bins, 0, sizeof(int)*256); |
| 171 | for (int i = 0; i < 256*10000; ++i) { |
| 172 | unsigned int u = rand.nextRangeU(17, 17+255); |
| 173 | REPORTER_ASSERT(reporter, 17 <= u && u <= 17+255); |
| 174 | bins[u - 17]++; |
| 175 | } |
| 176 | |
| 177 | REPORTER_ASSERT(reporter, chi_square_test(bins, 10000)); |
| 178 | } |
| 179 | |
tfarina@chromium.org | e4fafb1 | 2013-12-12 21:11:12 +0000 | [diff] [blame] | 180 | DEF_TEST(Random, reporter) { |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 181 | // check uniform distributions of each byte in 32-bit word |
| 182 | test_random_byte(reporter, 0); |
| 183 | test_random_byte(reporter, 8); |
| 184 | test_random_byte(reporter, 16); |
| 185 | test_random_byte(reporter, 24); |
| 186 | |
| 187 | test_random_float(reporter); |
| 188 | |
humper@google.com | 7cacbbd | 2013-02-08 18:44:27 +0000 | [diff] [blame] | 189 | test_gorilla(reporter); |
jvanverth@google.com | 5a90ada | 2013-02-08 17:13:09 +0000 | [diff] [blame] | 190 | |
| 191 | test_range(reporter); |
| 192 | } |