BrowserPRNGTester.cpp

// Tests Safari and Chromium's PRNG for experiment bucketing bias.

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <cmath>
#include <ctime>

#define MyRandom() (arc4random() % ((unsigned)RAND_MAX + 1))

class PRNG {
  public:
    virtual double random() = 0;
    virtual int randomInt(int max) {
      return int(floor(random() * max));
    }
    virtual ~PRNG() {}
};

// Google Chrome's RNG.
class ChromiumRandom: public PRNG {
  public:
    ChromiumRandom(unsigned rngstate_[2]) {
      rngstate[0] = rngstate_[0];
      rngstate[1] = rngstate_[1];
    }

    double random() {
      unsigned r0 = (MathImul(18273, rngstate[0] & 0xFFFF) + (rngstate[0] >> 16)) | 0;
      rngstate[0] = r0;
      unsigned r1 = (MathImul(36969, rngstate[1] & 0xFFFF) + (rngstate[1] >> 16)) | 0;
      rngstate[1] = r1;
      unsigned x = ((r0 << 16) + (r1 & 0xFFFF)) | 0;
      // Note: The Chromium code is in Javascript and uses the calculations in the commented return below.
      // Division by 0x100000000 through multiplication by reciprocal.
      // return (x < 0 ? (x + 0x100000000) : x) * 2.3283064365386962890625e-10;
      return x / (UINT_MAX + 1.0);
    }

  private:
    unsigned rngstate[2];

    unsigned MathImul(unsigned a, unsigned b) {
      return a * b;
    }
};

// Webkit(Safari)'s RNG.
class WeakRandom: public PRNG {
  public:
    WeakRandom(unsigned seed)
    {
      initializeSeed(seed);
    }

    virtual double random()
    {
      return advance() / (UINT_MAX + 1.0);
    }

  private:
    unsigned advance()
    {
      m_high = (m_high << 16) + (m_high >> 16);
      m_high += m_low;
      m_low += m_high;
      return m_high;
    }

    void initializeSeed(unsigned seed)
    {
      m_low = seed ^ 0x49616E42;
      m_high = seed;
    }

    unsigned m_low;
    unsigned m_high;
};

class PRNGFactory {
 public:
  PRNGFactory() {}
  virtual PRNG *make() = 0;
  virtual ~PRNGFactory() {}
};

class SafariPRNGFactory: public PRNGFactory {
 public:
  PRNG *make() {
    // Reseed for each test to simulate distributed environment, i.e. bucketing performed on end users running on
    // different browsers.
    long int seed = MyRandom();
    return new WeakRandom(seed);
  }
};

class ChromiumPRNGFactory: public PRNGFactory {
 public:
  PRNG *make() {
    // Reseed for each test to simulate distributed environment, i.e. bucketing performed on end users running on
    // different browsers.
    unsigned seed[] = {MyRandom(), MyRandom()};
    return new ChromiumRandom(seed);
  }
};


// Runs bucketing trials.
// Skips skipInitial number of random values.
// Ignores ignorePercentage of trials.
void runTests(int skipInitial, int ignorePercentage, PRNGFactory *prngMaker) {
  const int NUM_TRIALS = 100000;
  // Simulate bucketing into Original and Variation #1.
  int buckets[2] = {0, 0};
  int numNotIgnored = 0;
  for (int i=0; i < NUM_TRIALS; ++i) {
    PRNG *prng = prngMaker->make();
    for (int j=0; j < skipInitial; ++j) { prng->random(); }
    if (ignorePercentage > prng->randomInt(100)) {
      continue;
    }

    ++numNotIgnored;
    double rval = prng->random();
    assert(0 < rval && rval < 1);
    // Bucket with 50 - 50 distribution into Original and Variation #1.
    if (rval < 0.5) {
      buckets[0]++;
    } else {
      buckets[1]++;
    }
    delete prng;
  }

  printf("Of %d tests, %d ignored, %d not ignored\n", NUM_TRIALS, NUM_TRIALS - numNotIgnored, numNotIgnored);
  printf("Bucket counts %d %d, ratio = %f\n", buckets[0], buckets[1], float(buckets[0])/buckets[1]);
  printf("\n\n");
}

int main(int argc, char **argv) {
  int ignorePercentage = 50;
  if (argc > 1) {
    ignorePercentage = atoi(argv[1]);
  }
  int skipInitial = 0;
  if (argc > 2) {
    skipInitial = atoi(argv[2]);
  }
  printf("Chromium tests:\n");
  PRNGFactory *prngChromium = new ChromiumPRNGFactory;
  runTests(skipInitial, ignorePercentage, prngChromium);

  printf("Safari tests:\n");
  PRNGFactory *prngSafari = new SafariPRNGFactory;
  runTests(skipInitial, ignorePercentage, prngSafari);

  delete prngChromium;
  delete prngSafari;
  
  return 0;
}