File: XorShift128PlusRNG.h

package info (click to toggle)
icedove 1:45.8.0-3~deb8u1
  • links: PTS, VCS
  • area: main
  • in suites: jessie
  • size: 1,488,584 kB
  • ctags: 1,068,813
  • sloc: cpp: 4,801,496; ansic: 1,929,291; python: 379,296; java: 252,018; xml: 173,182; asm: 146,741; sh: 89,229; makefile: 23,462; perl: 16,380; objc: 4,088; yacc: 1,841; lex: 1,222; exp: 499; php: 437; lisp: 228; awk: 152; pascal: 116; sed: 51; ruby: 47; csh: 31; ada: 16
file content (109 lines) | stat: -rw-r--r-- 3,737 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/* -*- 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.
 *
 * 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 may not both be zero; ideally, they
   * should have an almost even mix of zero and one bits.
   */
  XorShift128PlusRNG(uint64_t aInitial0, uint64_t aInitial1) {
    setState(aInitial0, aInitial1);
  }

  /* Return a pseudo-random 64-bit number. */
  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.
   */
  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 MOZ_CONSTEXPR_VAR 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