mfbt/XorShift128PlusRNG.h
author Petru Lingurar <petru.lingurar@softvision.ro>
Fri, 21 Dec 2018 08:56:47 +0000
changeset 501492 65621d0fe1262af0643cec37c23b2d9ec42588ad
parent 461868 0ac335714eb84703979c29503305fd82c035eec0
child 508163 6f3709b3878117466168c40affa7bca0b60cf75b
permissions -rw-r--r--
Bug 1513938 - Enforce a Bundle size limit and drop `privateSession` if exceeds it. r=JanH, a=jcristau The `privateSession` key would normally allow persisting the Private Browsing session across OOMs in Activity's Bundle. We need to do that to avoid storing private, sensible data on disk like we do with the normal browsing session. In some cases `privateSession` would contain a lot of data which, along with other possible concurrent transactions could overflow Binder's buffer which has a limited fixed size, currently 1Mb. To avoid this, we will drop `privateSession` from the Bundle if the resulting size is greater than a _speculative_ size of 300KBs which would mean that in the case of an OOM all Private Browsing state would be lost. Bug 1515592 is filed to investigate for a better solution. Differential Revision: https://phabricator.services.mozilla.com/D15067

/* -*- 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/. */

/* The xorshift128+ pseudo-random number generator. */

#ifndef mozilla_XorShift128Plus_h
#define mozilla_XorShift128Plus_h

#include "mozilla/Assertions.h"
#include "mozilla/Attributes.h"
#include "mozilla/FloatingPoint.h"

#include <inttypes.h>

namespace mozilla {
namespace non_crypto {

/*
 * A stream of pseudo-random numbers generated using the xorshift+ technique
 * described here:
 *
 * Vigna, Sebastiano (2014). "Further scramblings of Marsaglia's xorshift
 * generators". arXiv:1404.0390 (http://arxiv.org/abs/1404.0390)
 *
 * That paper says:
 *
 *     In particular, we propose a tightly coded xorshift128+ generator that
 *     does not fail systematically any test from the BigCrush suite of TestU01
 *     (even reversed) and generates 64 pseudorandom bits in 1.10 ns on an
 *     Intel(R) Core(TM) i7-4770 CPU @3.40GHz (Haswell). It is the fastest
 *     generator we are aware of with such empirical statistical properties.
 *
 * The stream of numbers produced by this method repeats every 2**128 - 1 calls
 * (i.e. never, for all practical purposes). Zero appears 2**64 - 1 times in
 * this period; all other numbers appear 2**64 times. Additionally, each *bit*
 * in the produced numbers repeats every 2**128 - 1 calls.
 *
 * This generator is not suitable as a cryptographically secure random number
 * generator.
 */
class XorShift128PlusRNG {
  uint64_t mState[2];

 public:
  /*
   * Construct a xorshift128+ pseudo-random number stream using |aInitial0| and
   * |aInitial1| as the initial state.  These MUST NOT both be zero.
   *
   * If the initial states contain many zeros, for a few iterations you'll see
   * many zeroes in the generated numbers.  It's suggested to seed a SplitMix64
   * generator <http://xorshift.di.unimi.it/splitmix64.c> and use its first two
   * outputs to seed xorshift128+.
   */
  XorShift128PlusRNG(uint64_t aInitial0, uint64_t aInitial1) {
    setState(aInitial0, aInitial1);
  }

  /**
   * Return a pseudo-random 64-bit number.
   */
  MOZ_NO_SANITIZE_UNSIGNED_OVERFLOW
  uint64_t next() {
    /*
     * The offsetOfState*() methods below are provided so that exceedingly-rare
     * callers that want to observe or poke at RNG state in C++ type-system-
     * ignoring means can do so. Don't change the next() or nextDouble()
     * algorithms without altering code that uses offsetOfState*()!
     */
    uint64_t s1 = mState[0];
    const uint64_t s0 = mState[1];
    mState[0] = s0;
    s1 ^= s1 << 23;
    mState[1] = s1 ^ s0 ^ (s1 >> 17) ^ (s0 >> 26);
    return mState[1] + s0;
  }

  /*
   * Return a pseudo-random floating-point value in the range [0, 1). More
   * precisely, choose an integer in the range [0, 2**53) and divide it by
   * 2**53. Given the 2**128 - 1 period noted above, the produced doubles are
   * all but uniformly distributed in this range.
   */
  double nextDouble() {
    /*
     * Because the IEEE 64-bit floating point format stores the leading '1' bit
     * of the mantissa implicitly, it effectively represents a mantissa in the
     * range [0, 2**53) in only 52 bits. FloatingPoint<double>::kExponentShift
     * is the width of the bitfield in the in-memory format, so we must add one
     * to get the mantissa's range.
     */
    static constexpr int kMantissaBits =
      mozilla::FloatingPoint<double>::kExponentShift + 1;
    uint64_t mantissa = next() & ((UINT64_C(1) << kMantissaBits) - 1);
    return double(mantissa) / (UINT64_C(1) << kMantissaBits);
  }

  /*
   * Set the stream's current state to |aState0| and |aState1|. These must not
   * both be zero; ideally, they should have an almost even mix of zero and one
   * bits.
   */
  void setState(uint64_t aState0, uint64_t aState1) {
    MOZ_ASSERT(aState0 || aState1);
    mState[0] = aState0;
    mState[1] = aState1;
  }

  static size_t offsetOfState0() {
    return offsetof(XorShift128PlusRNG, mState[0]);
  }
  static size_t offsetOfState1() {
    return offsetof(XorShift128PlusRNG, mState[1]);
  }
};

} // namespace non_crypto
} // namespace mozilla

#endif // mozilla_XorShift128Plus_h