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