Home | History | Annotate | Download | only in tests
      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 }
    193