src/third_party/skia/tests/RandomTest.cpp

   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
   8 #include "SkRandom.h"
   9 #include "SkTSort.h"
  10 #include "Test.h"
  11
  12 static bool anderson_darling_test(double p[32]) {
  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
  34 static bool chi_square_test(int bins[256], int e) {
  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
  51 static double normal_cdf(double z) {
  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
  59 static void test_random_byte(skiatest::Reporter* reporter, int shift) {
  60     int bins[256];
  61     memset(bins, 0, sizeof(int)*256);
  62
  63     SkRandom rand;
  64     for (int i = 0; i < 256*10000; ++i) {
  65         bins[(rand.nextU() >> shift) & 0xff]++;
  66     }
  67
  68     REPORTER_ASSERT(reporter, chi_square_test(bins, 10000));
  69 }
  70
  71 static void test_random_float(skiatest::Reporter* reporter) {
  72     int bins[256];
  73     memset(bins, 0, sizeof(int)*256);
  74
  75     SkRandom rand;
  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
  94 // "strings" of 16 bits in length, shifting the string and adding a new bit with each
  95 // iteration. We track the numbers generated. The ones that we don't generate will
  96 // have a normal distribution with mean ~24108 and standard deviation ~127. By
  97 // creating a z-score (# of deviations from the mean) for one iteration of this step
  98 // we can determine its probability.
  99 //
 100 // The original test used 26 bit strings, but is somewhat slow. This version uses 16
 101 // bits which is less rigorous but much faster to generate.
 102 static double test_single_gorilla(skiatest::Reporter* reporter, int shift) {
 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
 110     SkRandom rand;
 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) {
 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);
 128         int entry_shift = (value >> (kWordWidth-5)) & 0x1f;
 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
 143     double z = ((kN-total)-kMean)/kStandardDeviation;
 144
 145     // compute probability from normal distibution CDF
 146     double p = normal_cdf(z);
 147
 148     REPORTER_ASSERT(reporter, 0.01 < p && p < 0.99);
 149     return p;
 150 }
 151
 152 static void test_gorilla(skiatest::Reporter* reporter) {
 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     }
 158
 159     REPORTER_ASSERT(reporter, anderson_darling_test(p));
 160 }
 161
 162 static void test_range(skiatest::Reporter* reporter) {
 163     SkRandom rand;
 164
 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
 180 DEF_TEST(Random, reporter) {
 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
 189     test_gorilla(reporter);
 190
 191     test_range(reporter);
 192 }