1/*
2 * Copyright (C) 2009, 2015 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 *
25 * Vigna, Sebastiano (2014). "Further scramblings of Marsaglia's xorshift
26 * generators". arXiv:1404.0390 (http://arxiv.org/abs/1404.0390)
27 *
28 * See also https://en.wikipedia.org/wiki/Xorshift.
29 */
30
31#pragma once
32
33#include <limits.h>
34#include <wtf/CryptographicallyRandomNumber.h>
35#include <wtf/StdLibExtras.h>
36
37namespace WTF {
38
39// The code used to generate random numbers are inlined manually in JIT code.
40// So it needs to stay in sync with the JIT one.
41class WeakRandom {
42public:
43 WeakRandom(unsigned seed = cryptographicallyRandomNumber())
44 {
45 setSeed(seed);
46 }
47
48 void setSeed(unsigned seed)
49 {
50 m_seed = seed;
51
52 // A zero seed would cause an infinite series of zeroes.
53 if (!seed)
54 seed = 1;
55
56 m_low = seed;
57 m_high = seed;
58 advance();
59 }
60
61 unsigned seed() const { return m_seed; }
62
63 double get()
64 {
65 uint64_t value = advance() & ((1ULL << 53) - 1);
66 return value * (1.0 / (1ULL << 53));
67 }
68
69 unsigned getUint32()
70 {
71 return static_cast<unsigned>(advance());
72 }
73
74 unsigned getUint32(unsigned limit)
75 {
76 if (limit <= 1)
77 return 0;
78 uint64_t cutoff = (static_cast<uint64_t>(std::numeric_limits<unsigned>::max()) + 1) / limit * limit;
79 for (;;) {
80 uint64_t value = getUint32();
81 if (value >= cutoff)
82 continue;
83 return value % limit;
84 }
85 }
86
87 static unsigned lowOffset() { return OBJECT_OFFSETOF(WeakRandom, m_low); }
88 static unsigned highOffset() { return OBJECT_OFFSETOF(WeakRandom, m_high); }
89
90 static constexpr uint64_t nextState(uint64_t x, uint64_t y)
91 {
92 x ^= x << 23;
93 x ^= x >> 17;
94 x ^= y ^ (y >> 26);
95 return x;
96 }
97
98 static constexpr uint64_t generate(unsigned seed)
99 {
100 if (!seed)
101 seed = 1;
102 uint64_t low = seed;
103 uint64_t high = seed;
104 high = nextState(low, high);
105 return low + high;
106 }
107
108private:
109 uint64_t advance()
110 {
111 uint64_t x = m_low;
112 uint64_t y = m_high;
113 m_low = y;
114 m_high = nextState(x, y);
115 return m_high + m_low;
116 }
117
118 unsigned m_seed;
119 uint64_t m_low;
120 uint64_t m_high;
121};
122
123} // namespace WTF
124
125using WTF::WeakRandom;
126