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