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 | |
37 | namespace 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. |
41 | class WeakRandom final { |
42 | WTF_MAKE_FAST_ALLOCATED; |
43 | public: |
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 | |
109 | private: |
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 | |
126 | using WTF::WeakRandom; |
127 | |