mfbt/tests/TestXorShift128PlusRNG.cpp
author Kris Maglione <maglione.k@gmail.com>
Mon, 28 Jan 2019 17:51:05 -0800
changeset 513684 d6528b01b83d071af1b6133a19d4050d7d0647ea
parent 507657 09c71a7cf75aeaf2963050e315276fb9a866fd62
permissions -rw-r--r--
Bug 1514594: Follow-up: Fix pageloader talos tests. r=bustage

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this file,
 * You can obtain one at http://mozilla.org/MPL/2.0/. */

#include <math.h>

#include "mozilla/Assertions.h"
#include "mozilla/PodOperations.h"
#include "mozilla/XorShift128PlusRNG.h"

using mozilla::non_crypto::XorShift128PlusRNG;

static void TestDumbSequence() {
  XorShift128PlusRNG rng(1, 4);

  // Calculated by hand following the algorithm given in the paper. The upper
  // bits are mostly zero because we started with a poor seed; once it has run
  // for a while, we'll get an even mix of ones and zeros in all 64 bits.
  MOZ_RELEASE_ASSERT(rng.next() == 0x800049);
  MOZ_RELEASE_ASSERT(rng.next() == 0x3000186);
  MOZ_RELEASE_ASSERT(rng.next() == 0x400003001145);

  // Using ldexp here lets us write out the mantissa in hex, so we can compare
  // them with the results generated by hand.
  MOZ_RELEASE_ASSERT(rng.nextDouble() ==
                     ldexp(static_cast<double>(0x1400003105049), -53));
  MOZ_RELEASE_ASSERT(rng.nextDouble() ==
                     ldexp(static_cast<double>(0x2000802e49146), -53));
  MOZ_RELEASE_ASSERT(rng.nextDouble() ==
                     ldexp(static_cast<double>(0x248300468544d), -53));
}

static size_t Population(uint64_t n) {
  size_t pop = 0;

  while (n > 0) {
    n &= n - 1;  // Clear the rightmost 1-bit in n.
    pop++;
  }

  return pop;
}

static void TestPopulation() {
  XorShift128PlusRNG rng(698079309544035222ULL, 6012389156611637584ULL);

  // Give it some time to warm up; it should tend towards more
  // even distributions of zeros and ones.
  for (size_t i = 0; i < 40; i++) rng.next();

  for (size_t i = 0; i < 40; i++) {
    size_t pop = Population(rng.next());
    MOZ_RELEASE_ASSERT(24 <= pop && pop <= 40);
  }
}

static void TestSetState() {
  static const uint64_t seed[2] = {1795644156779822404ULL,
                                   14162896116325912595ULL};
  XorShift128PlusRNG rng(seed[0], seed[1]);

  const size_t n = 10;
  uint64_t log[n];

  for (size_t i = 0; i < n; i++) log[i] = rng.next();

  rng.setState(seed[0], seed[1]);

  for (size_t i = 0; i < n; i++) MOZ_RELEASE_ASSERT(log[i] == rng.next());
}

static void TestDoubleDistribution() {
  XorShift128PlusRNG rng(0xa207aaede6859736, 0xaca6ca5060804791);

  const size_t n = 100;
  size_t bins[n];
  mozilla::PodArrayZero(bins);

  // This entire file runs in 0.006s on my laptop. Generating
  // more numbers lets us put tighter bounds on the bins.
  for (size_t i = 0; i < 100000; i++) {
    double d = rng.nextDouble();
    MOZ_RELEASE_ASSERT(0.0 <= d && d < 1.0);
    bins[(int)(d * n)]++;
  }

  for (size_t i = 0; i < n; i++) {
    MOZ_RELEASE_ASSERT(900 <= bins[i] && bins[i] <= 1100);
  }
}

int main() {
  TestDumbSequence();
  TestPopulation();
  TestSetState();
  TestDoubleDistribution();

  return 0;
}