RandomTest.cpp File Reference

#include "include/core/SkTypes.h"
#include "include/private/base/SkMath.h"
#include "src/base/SkRandom.h"
#include "src/base/SkTSort.h"
#include "tests/Test.h"
#include <cmath>
#include <cstring>

Go to the source code of this file.

Functions
static bool	anderson_darling_test (double p[32])
static bool	chi_square_test (int bins[256], int e)
static double	normal_cdf (double z)
static void	test_random_byte (skiatest::Reporter *reporter, int shift)
static void	test_random_float (skiatest::Reporter *reporter)
static double	test_single_gorilla (skiatest::Reporter *reporter, int shift)
static void	test_gorilla (skiatest::Reporter *reporter)
static void	test_range (skiatest::Reporter *reporter)
	DEF_TEST (Random, reporter)

Function Documentation

anderson_darling_test()

static bool anderson_darling_test ( double  p[32] )

static

Definition at line 17 of file RandomTest.cpp.

                                                {
    // 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<double>(p, p + 32);
 
    // 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);
}

chi_square_test()

static bool chi_square_test ( int  bins[256], int  e  )

static

Definition at line 39 of file RandomTest.cpp.

                                                  {
    // 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);
}

DEF_TEST()

DEF_TEST	(	Random	,
		reporter
	)

Definition at line 185 of file RandomTest.cpp.

                           {
    // 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);
}

normal_cdf()

static double normal_cdf ( double  z )

static

Definition at line 56 of file RandomTest.cpp.

                                   {
    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;
}

test_gorilla()

static void test_gorilla ( skiatest::Reporter *  reporter )

static

Definition at line 157 of file RandomTest.cpp.

                                                     {
 
    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));
}

test_random_byte()

static void test_random_byte ( skiatest::Reporter *  reporter, int  shift  )

static

Definition at line 64 of file RandomTest.cpp.

                                                                    {
    int bins[256];
    memset(bins, 0, sizeof(int)*256);
 
    SkRandom rand;
    for (int i = 0; i < 256*10000; ++i) {
        bins[(rand.nextU() >> shift) & 0xff]++;
    }
 
    REPORTER_ASSERT(reporter, chi_square_test(bins, 10000));
}

test_random_float()

static void test_random_float ( skiatest::Reporter *  reporter )

static

Definition at line 76 of file RandomTest.cpp.

                                                          {
    int bins[256];
    memset(bins, 0, sizeof(int)*256);
 
    SkRandom 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));
}

test_range()

static void test_range ( skiatest::Reporter *  reporter )

static

Definition at line 167 of file RandomTest.cpp.

                                                   {
    SkRandom 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));
}

test_single_gorilla()

static double test_single_gorilla ( skiatest::Reporter *  reporter, int  shift  )

static

Definition at line 107 of file RandomTest.cpp.

                                                                         {
    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];
 
    SkRandom 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 = SkLeftShift(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)) & 0x1f;
        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;
}