Add Random unit tests.
https://codereview.appspot.com/7306066/
git-svn-id: http://skia.googlecode.com/svn/trunk@7670 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/tests/RandomTest.cpp b/tests/RandomTest.cpp
new file mode 100644
index 0000000..ce75bf3
--- /dev/null
+++ b/tests/RandomTest.cpp
@@ -0,0 +1,196 @@
+
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Test.h"
+#include "SkRandom.h"
+#include "SkTSort.h"
+
+bool anderson_darling_test(double p[32]) {
+ // Min and max Anderson-Darling values allowable for k=32
+ const double kADMin32 = 0.202; // p-value of ~0.1
+ const double kADMax32 = 3.89; // p-value of ~0.99
+
+ // sort p values
+ SkTQSort<double>(p, p + 31);
+
+ // and compute Anderson-Darling statistic to ensure these are uniform
+ double s = 0.0;
+ for(int k = 0; k < 32; k++) {
+ double v = p[k]*(1.0 - p[31-k]);
+ if (v < 1.0e-30) {
+ v = 1.0e-30;
+ }
+ s += (2.0*(k+1)-1.0)*log(v);
+ }
+ double a2 = -32.0 - 0.03125*s;
+
+ return (kADMin32 < a2 && a2 < kADMax32);
+}
+
+bool chi_square_test(int bins[256], int e) {
+ // Min and max chisquare values allowable
+ const double kChiSqMin256 = 206.3179; // probability of chance = 0.99 with k=256
+ const double kChiSqMax256 = 311.5603; // probability of chance = 0.01 with k=256
+
+ // compute chi-square
+ double chi2 = 0.0;
+ for (int j = 0; j < 256; ++j) {
+ double delta = bins[j] - e;
+ chi2 += delta*delta/e;
+ }
+
+ return (kChiSqMin256 < chi2 && chi2 < kChiSqMax256);
+}
+
+// Approximation to the normal distribution CDF
+// From Waissi and Rossin, 1996
+double normal_cdf(double z) {
+ double t = ((-0.0004406*z*z* + 0.0418198)*z*z + 0.9)*z;
+ t *= -1.77245385091; // -sqrt(PI)
+ double p = 1.0/(1.0 + exp(t));
+
+ return p;
+}
+
+void test_random_byte(skiatest::Reporter* reporter, int shift) {
+ int bins[256];
+ memset(bins, 0, sizeof(int)*256);
+
+ SkMWCRandom rand;
+ for (int i = 0; i < 256*10000; ++i) {
+ bins[(rand.nextU() >> shift) & 0xff]++;
+ }
+
+ REPORTER_ASSERT(reporter, chi_square_test(bins, 10000));
+}
+
+void test_random_float(skiatest::Reporter* reporter) {
+ int bins[256];
+ memset(bins, 0, sizeof(int)*256);
+
+ SkMWCRandom rand;
+ for (int i = 0; i < 256*10000; ++i) {
+ float f = rand.nextF();
+ REPORTER_ASSERT(reporter, 0.0f <= f && f < 1.0f);
+ bins[(int)(f*256.f)]++;
+ }
+ REPORTER_ASSERT(reporter, chi_square_test(bins, 10000));
+
+ double p[32];
+ for (int j = 0; j < 32; ++j) {
+ float f = rand.nextF();
+ REPORTER_ASSERT(reporter, 0.0f <= f && f < 1.0f);
+ p[j] = f;
+ }
+ REPORTER_ASSERT(reporter, anderson_darling_test(p));
+}
+
+// This is a test taken from tuftests by Marsaglia and Tsang. The idea here is that
+// we are using the random bit generated from a single shift position to generate
+// "strings" of 16 bits in length, shifting the string and adding a new bit with each
+// iteration. We track the numbers generated. The ones that we don't generate will
+// have a normal distribution with mean ~24108 and standard deviation ~127. By
+// creating a z-score (# of deviations from the mean) for one iteration of this step
+// we can determine its probability.
+//
+// The original test used 26 bit strings, but is somewhat slow. This version uses 16
+// bits which is less rigorous but much faster to generate.
+double test_single_gorilla(skiatest::Reporter* reporter, int shift) {
+ const int kWordWidth = 16;
+ const double kMean = 24108.0;
+ const double kStandardDeviation = 127.0;
+ const int kN = (1 << kWordWidth);
+ const int kNumEntries = kN >> 5; // dividing by 32
+ unsigned int entries[kNumEntries];
+
+ SkMWCRandom rand;
+ memset(entries, 0, sizeof(unsigned int)*kNumEntries);
+ // pre-seed our string value
+ int value = 0;
+ for (int i = 0; i < kWordWidth-1; ++i) {
+ value <<= 1;
+ unsigned int rnd = rand.nextU();
+ value |= ((rnd >> shift) & 0x1);
+ }
+
+ // now make some strings and track them
+ for (int i = 0; i < kN; ++i) {
+ value <<= 1;
+ unsigned int rnd = rand.nextU();
+ value |= ((rnd >> shift) & 0x1);
+
+ int index = value & (kNumEntries-1);
+ SkASSERT(index < kNumEntries);
+ int entry_shift = (value >> (kWordWidth-5)) & 0x3f;
+ entries[index] |= (0x1 << entry_shift);
+ }
+
+ // count entries
+ int total = 0;
+ for (int i = 0; i < kNumEntries; ++i) {
+ unsigned int entry = entries[i];
+ while (entry) {
+ total += (entry & 0x1);
+ entry >>= 1;
+ }
+ }
+
+ // convert counts to normal distribution z-score
+ double z = ((kN-total)-kMean)/kStandardDeviation;
+
+ // compute probability from normal distibution CDF
+ double p = normal_cdf(z);
+
+ REPORTER_ASSERT(reporter, 0.01 < p && p < 0.99);
+ return p;
+}
+
+void test_gorilla(skiatest::Reporter* reporter) {
+
+ double p[32];
+ for (int bit_position = 0; bit_position < 32; ++bit_position) {
+ p[bit_position] = test_single_gorilla(reporter, bit_position);
+ }
+
+ REPORTER_ASSERT(reporter, anderson_darling_test(p));
+}
+
+void test_range(skiatest::Reporter* reporter) {
+ SkMWCRandom rand;
+
+ // just to make sure we don't crash in this case
+ (void) rand.nextRangeU(0, 0xffffffff);
+
+ // check a case to see if it's uniform
+ int bins[256];
+ memset(bins, 0, sizeof(int)*256);
+ for (int i = 0; i < 256*10000; ++i) {
+ unsigned int u = rand.nextRangeU(17, 17+255);
+ REPORTER_ASSERT(reporter, 17 <= u && u <= 17+255);
+ bins[u - 17]++;
+ }
+
+ REPORTER_ASSERT(reporter, chi_square_test(bins, 10000));
+}
+
+static void TestRandom(skiatest::Reporter* reporter) {
+ // check uniform distributions of each byte in 32-bit word
+ test_random_byte(reporter, 0);
+ test_random_byte(reporter, 8);
+ test_random_byte(reporter, 16);
+ test_random_byte(reporter, 24);
+
+ test_random_float(reporter);
+
+ test_gorilla(reporter);
+
+ test_range(reporter);
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("Random", RandomTestClass, TestRandom)