From 5a90adaf2fc3c161be32ae61ca063e82f1b8fa46 Mon Sep 17 00:00:00 2001 From: "jvanverth@google.com" Date: Fri, 8 Feb 2013 17:13:09 +0000 Subject: [PATCH] Add Random unit tests. https://codereview.appspot.com/7306066/ git-svn-id: http://skia.googlecode.com/svn/trunk@7670 2bbb7eff-a529-9590-31e7-b0007b416f81 --- gyp/tests.gyp | 1 + tests/RandomTest.cpp | 196 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 197 insertions(+) create mode 100644 tests/RandomTest.cpp diff --git a/gyp/tests.gyp b/gyp/tests.gyp index 10e99d2..082336f 100644 --- a/gyp/tests.gyp +++ b/gyp/tests.gyp @@ -77,6 +77,7 @@ '../tests/PointTest.cpp', '../tests/PremulAlphaRoundTripTest.cpp', '../tests/QuickRejectTest.cpp', + '../tests/RandomTest.cpp', '../tests/Reader32Test.cpp', '../tests/ReadPixelsTest.cpp', '../tests/ReadWriteAlphaTest.cpp', 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(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) -- 2.7.4