blob: 8d93d87df6cd7fafbfc11630244b7865217bb580 [file] [log] [blame]
jvanverth@google.com5a90ada2013-02-08 17:13:09 +00001/*
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.com5a90ada2013-02-08 17:13:09 +00008#include "SkRandom.h"
9#include "SkTSort.h"
tfarina@chromium.org8f6884a2014-01-24 20:56:26 +000010#include "Test.h"
jvanverth@google.com5a90ada2013-02-08 17:13:09 +000011
jvanverth@google.com897f4622013-02-08 18:28:47 +000012static bool anderson_darling_test(double p[32]) {
jvanverth@google.com5a90ada2013-02-08 17:13:09 +000013 // 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.com897f4622013-02-08 18:28:47 +000034static bool chi_square_test(int bins[256], int e) {
jvanverth@google.com5a90ada2013-02-08 17:13:09 +000035 // 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.com897f4622013-02-08 18:28:47 +000051static double normal_cdf(double z) {
jvanverth@google.com5a90ada2013-02-08 17:13:09 +000052 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.com897f4622013-02-08 18:28:47 +000059static void test_random_byte(skiatest::Reporter* reporter, int shift) {
jvanverth@google.com5a90ada2013-02-08 17:13:09 +000060 int bins[256];
61 memset(bins, 0, sizeof(int)*256);
62
commit-bot@chromium.orge0e7cfe2013-09-09 20:09:12 +000063 SkRandom rand;
jvanverth@google.com5a90ada2013-02-08 17:13:09 +000064 for (int i = 0; i < 256*10000; ++i) {
65 bins[(rand.nextU() >> shift) & 0xff]++;
66 }
skia.committer@gmail.com86267192013-02-09 07:05:02 +000067
jvanverth@google.com5a90ada2013-02-08 17:13:09 +000068 REPORTER_ASSERT(reporter, chi_square_test(bins, 10000));
69}
70
jvanverth@google.com897f4622013-02-08 18:28:47 +000071static void test_random_float(skiatest::Reporter* reporter) {
jvanverth@google.com5a90ada2013-02-08 17:13:09 +000072 int bins[256];
73 memset(bins, 0, sizeof(int)*256);
74
commit-bot@chromium.orge0e7cfe2013-09-09 20:09:12 +000075 SkRandom rand;
jvanverth@google.com5a90ada2013-02-08 17:13:09 +000076 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.com86267192013-02-09 07:05:02 +000094// "strings" of 16 bits in length, shifting the string and adding a new bit with each
jvanverth@google.com5a90ada2013-02-08 17:13:09 +000095// iteration. We track the numbers generated. The ones that we don't generate will
skia.committer@gmail.com86267192013-02-09 07:05:02 +000096// have a normal distribution with mean ~24108 and standard deviation ~127. By
jvanverth@google.com5a90ada2013-02-08 17:13:09 +000097// 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.com86267192013-02-09 07:05:02 +0000100// The original test used 26 bit strings, but is somewhat slow. This version uses 16
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000101// bits which is less rigorous but much faster to generate.
jvanverth@google.com897f4622013-02-08 18:28:47 +0000102static double test_single_gorilla(skiatest::Reporter* reporter, int shift) {
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000103 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.orge0e7cfe2013-09-09 20:09:12 +0000110 SkRandom rand;
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000111 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) {
122 value <<= 1;
123 unsigned int rnd = rand.nextU();
124 value |= ((rnd >> shift) & 0x1);
125
126 int index = value & (kNumEntries-1);
127 SkASSERT(index < kNumEntries);
jvanverth@google.com024e5232013-02-14 13:20:35 +0000128 int entry_shift = (value >> (kWordWidth-5)) & 0x1f;
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000129 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.com86267192013-02-09 07:05:02 +0000143 double z = ((kN-total)-kMean)/kStandardDeviation;
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000144
skia.committer@gmail.com86267192013-02-09 07:05:02 +0000145 // compute probability from normal distibution CDF
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000146 double p = normal_cdf(z);
147
jvanverth@google.com024e5232013-02-14 13:20:35 +0000148 REPORTER_ASSERT(reporter, 0.01 < p && p < 0.99);
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000149 return p;
150}
151
jvanverth@google.com897f4622013-02-08 18:28:47 +0000152static void test_gorilla(skiatest::Reporter* reporter) {
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000153
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.com86267192013-02-09 07:05:02 +0000158
jvanverth@google.com024e5232013-02-14 13:20:35 +0000159 REPORTER_ASSERT(reporter, anderson_darling_test(p));
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000160}
161
jvanverth@google.com897f4622013-02-08 18:28:47 +0000162static void test_range(skiatest::Reporter* reporter) {
commit-bot@chromium.orge0e7cfe2013-09-09 20:09:12 +0000163 SkRandom rand;
skia.committer@gmail.com86267192013-02-09 07:05:02 +0000164
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000165 // 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.orge4fafb12013-12-12 21:11:12 +0000180DEF_TEST(Random, reporter) {
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000181 // 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.com7cacbbd2013-02-08 18:44:27 +0000189 test_gorilla(reporter);
jvanverth@google.com5a90ada2013-02-08 17:13:09 +0000190
191 test_range(reporter);
192}