mfbt/tests/TestXorShift128PlusRNG.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
   5  * You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include <math.h>
   8
   9 #include "mozilla/Assertions.h"
  10 #include "mozilla/PodOperations.h"
  11 #include "mozilla/XorShift128PlusRNG.h"
  12
  13 using mozilla::non_crypto::XorShift128PlusRNG;
  14
  15 static void TestDumbSequence() {
  16   XorShift128PlusRNG rng(1, 4);
  17
  18   // Calculated by hand following the algorithm given in the paper. The upper
  19   // bits are mostly zero because we started with a poor seed; once it has run
  20   // for a while, we'll get an even mix of ones and zeros in all 64 bits.
  21   MOZ_RELEASE_ASSERT(rng.next() == 0x800049);
  22   MOZ_RELEASE_ASSERT(rng.next() == 0x3000186);
  23   MOZ_RELEASE_ASSERT(rng.next() == 0x400003001145);
  24
  25   // Using ldexp here lets us write out the mantissa in hex, so we can compare
  26   // them with the results generated by hand.
  27   MOZ_RELEASE_ASSERT(rng.nextDouble() ==
  28                      ldexp(static_cast<double>(0x1400003105049), -53));
  29   MOZ_RELEASE_ASSERT(rng.nextDouble() ==
  30                      ldexp(static_cast<double>(0x2000802e49146), -53));
  31   MOZ_RELEASE_ASSERT(rng.nextDouble() ==
  32                      ldexp(static_cast<double>(0x248300468544d), -53));
  33 }
  34
  35 static size_t Population(uint64_t n) {
  36   size_t pop = 0;
  37
  38   while (n > 0) {
  39     n &= n - 1;  // Clear the rightmost 1-bit in n.
  40     pop++;
  41   }
  42
  43   return pop;
  44 }
  45
  46 static void TestPopulation() {
  47   XorShift128PlusRNG rng(698079309544035222ULL, 6012389156611637584ULL);
  48
  49   // Give it some time to warm up; it should tend towards more
  50   // even distributions of zeros and ones.
  51   for (size_t i = 0; i < 40; i++) rng.next();
  52
  53   for (size_t i = 0; i < 40; i++) {
  54     size_t pop = Population(rng.next());
  55     MOZ_RELEASE_ASSERT(24 <= pop && pop <= 40);
  56   }
  57 }
  58
  59 static void TestSetState() {
  60   static const uint64_t seed[2] = {1795644156779822404ULL,
  61                                    14162896116325912595ULL};
  62   XorShift128PlusRNG rng(seed[0], seed[1]);
  63
  64   const size_t n = 10;
  65   uint64_t log[n];
  66
  67   for (size_t i = 0; i < n; i++) log[i] = rng.next();
  68
  69   rng.setState(seed[0], seed[1]);
  70
  71   for (size_t i = 0; i < n; i++) MOZ_RELEASE_ASSERT(log[i] == rng.next());
  72 }
  73
  74 static void TestDoubleDistribution() {
  75   XorShift128PlusRNG rng(0xa207aaede6859736, 0xaca6ca5060804791);
  76
  77   const size_t n = 100;
  78   size_t bins[n];
  79   mozilla::PodArrayZero(bins);
  80
  81   // This entire file runs in 0.006s on my laptop. Generating
  82   // more numbers lets us put tighter bounds on the bins.
  83   for (size_t i = 0; i < 100000; i++) {
  84     double d = rng.nextDouble();
  85     MOZ_RELEASE_ASSERT(0.0 <= d && d < 1.0);
  86     bins[(int)(d * n)]++;
  87   }
  88
  89   for (size_t i = 0; i < n; i++) {
  90     MOZ_RELEASE_ASSERT(900 <= bins[i] && bins[i] <= 1100);
  91   }
  92 }
  93
  94 int main() {
  95   TestDumbSequence();
  96   TestPopulation();
  97   TestSetState();
  98   TestDoubleDistribution();
  99
 100   return 0;
 101 }