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 final {
42 WTF_MAKE_FAST_ALLOCATED;
43public:
44 WeakRandom(unsigned seed = cryptographicallyRandomNumber())
45 {
46 setSeed(seed);
47 }
48
49 void setSeed(unsigned seed)
50 {
51 m_seed = seed;
52
53 // A zero seed would cause an infinite series of zeroes.
54 if (!seed)
55 seed = 1;
56
57 m_low = seed;
58 m_high = seed;
59 advance();
60 }
61
62 unsigned seed() const { return m_seed; }
63
64 double get()
65 {
66 uint64_t value = advance() & ((1ULL << 53) - 1);
67 return value * (1.0 / (1ULL << 53));
68 }
69
70 unsigned getUint32()
71 {
72 return static_cast<unsigned>(advance());
73 }
74
75 unsigned getUint32(unsigned limit)
76 {
77 if (limit <= 1)
78 return 0;
79 uint64_t cutoff = (static_cast<uint64_t>(std::numeric_limits<unsigned>::max()) + 1) / limit * limit;
80 for (;;) {
81 uint64_t value = getUint32();
82 if (value >= cutoff)
83 continue;
84 return value % limit;
85 }
86 }
87
88 static unsigned lowOffset() { return OBJECT_OFFSETOF(WeakRandom, m_low); }
89 static unsigned highOffset() { return OBJECT_OFFSETOF(WeakRandom, m_high); }
90
91 static constexpr uint64_t nextState(uint64_t x, uint64_t y)
92 {
93 x ^= x << 23;
94 x ^= x >> 17;
95 x ^= y ^ (y >> 26);
96 return x;
97 }
98
99 static constexpr uint64_t generate(unsigned seed)
100 {
101 if (!seed)
102 seed = 1;
103 uint64_t low = seed;
104 uint64_t high = seed;
105 high = nextState(low, high);
106 return low + high;
107 }
108
109private:
110 uint64_t advance()
111 {
112 uint64_t x = m_low;
113 uint64_t y = m_high;
114 m_low = y;
115 m_high = nextState(x, y);
116 return m_high + m_low;
117 }
118
119 unsigned m_seed;
120 uint64_t m_low;
121 uint64_t m_high;
122};
123
124} // namespace WTF
125
126using WTF::WeakRandom;
127