1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2017 Intel Corporation. |
4 | ** Contact: https://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the QtCore module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and The Qt Company. For licensing terms |
14 | ** and conditions see https://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at https://www.qt.io/contact-us. |
16 | ** |
17 | ** GNU Lesser General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
19 | ** General Public License version 3 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 3 requirements |
23 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |
24 | ** |
25 | ** GNU General Public License Usage |
26 | ** Alternatively, this file may be used under the terms of the GNU |
27 | ** General Public License version 2.0 or (at your option) the GNU General |
28 | ** Public license version 3 or any later version approved by the KDE Free |
29 | ** Qt Foundation. The licenses are as published by the Free Software |
30 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |
31 | ** included in the packaging of this file. Please review the following |
32 | ** information to ensure the GNU General Public License requirements will |
33 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |
34 | ** https://www.gnu.org/licenses/gpl-3.0.html. |
35 | ** |
36 | ** $QT_END_LICENSE$ |
37 | ** |
38 | ****************************************************************************/ |
39 | |
40 | #ifndef QRANDOM_H |
41 | #define QRANDOM_H |
42 | |
43 | #include <QtCore/qglobal.h> |
44 | #include <algorithm> // for std::generate |
45 | #include <random> // for std::mt19937 |
46 | |
47 | #ifdef min |
48 | # undef min |
49 | #endif |
50 | #ifdef max |
51 | # undef max |
52 | #endif |
53 | |
54 | QT_BEGIN_NAMESPACE |
55 | |
56 | class QRandomGenerator |
57 | { |
58 | // restrict the template parameters to unsigned integers 32 bits wide or larger |
59 | template <typename UInt> using IfValidUInt = |
60 | typename std::enable_if<std::is_unsigned<UInt>::value && sizeof(UInt) >= sizeof(uint), bool>::type; |
61 | public: |
62 | QRandomGenerator(quint32 seedValue = 1) |
63 | : QRandomGenerator(&seedValue, 1) |
64 | {} |
65 | template <qsizetype N> QRandomGenerator(const quint32 (&seedBuffer)[N]) |
66 | : QRandomGenerator(seedBuffer, seedBuffer + N) |
67 | {} |
68 | QRandomGenerator(const quint32 *seedBuffer, qsizetype len) |
69 | : QRandomGenerator(seedBuffer, seedBuffer + len) |
70 | {} |
71 | Q_CORE_EXPORT QRandomGenerator(std::seed_seq &sseq) noexcept; |
72 | Q_CORE_EXPORT QRandomGenerator(const quint32 *begin, const quint32 *end); |
73 | |
74 | // copy constructor & assignment operator (move unnecessary) |
75 | Q_CORE_EXPORT QRandomGenerator(const QRandomGenerator &other); |
76 | Q_CORE_EXPORT QRandomGenerator &operator=(const QRandomGenerator &other); |
77 | |
78 | friend Q_CORE_EXPORT bool operator==(const QRandomGenerator &rng1, const QRandomGenerator &rng2); |
79 | friend bool operator!=(const QRandomGenerator &rng1, const QRandomGenerator &rng2) |
80 | { |
81 | return !(rng1 == rng2); |
82 | } |
83 | |
84 | quint32 generate() |
85 | { |
86 | quint32 ret; |
87 | fillRange(&ret, 1); |
88 | return ret; |
89 | } |
90 | |
91 | quint64 generate64() |
92 | { |
93 | quint32 buf[2]; |
94 | fillRange(buf); |
95 | return buf[0] | (quint64(buf[1]) << 32); |
96 | } |
97 | |
98 | double generateDouble() |
99 | { |
100 | // IEEE 754 double precision has: |
101 | // 1 bit sign |
102 | // 10 bits exponent |
103 | // 53 bits mantissa |
104 | // In order for our result to be normalized in the range [0, 1), we |
105 | // need exactly 53 bits of random data. Use generate64() to get enough. |
106 | quint64 x = generate64(); |
107 | quint64 limit = Q_UINT64_C(1) << std::numeric_limits<double>::digits; |
108 | x >>= std::numeric_limits<quint64>::digits - std::numeric_limits<double>::digits; |
109 | return double(x) / double(limit); |
110 | } |
111 | |
112 | double bounded(double highest) |
113 | { |
114 | return generateDouble() * highest; |
115 | } |
116 | |
117 | quint32 bounded(quint32 highest) |
118 | { |
119 | quint64 value = generate(); |
120 | value *= highest; |
121 | value /= (max)() + quint64(1); |
122 | return quint32(value); |
123 | } |
124 | |
125 | quint32 bounded(quint32 lowest, quint32 highest) |
126 | { |
127 | Q_ASSERT(highest > lowest); |
128 | return bounded(highest - lowest) + lowest; |
129 | } |
130 | |
131 | int bounded(int highest) |
132 | { |
133 | Q_ASSERT(highest > 0); |
134 | return int(bounded(0U, quint32(highest))); |
135 | } |
136 | |
137 | int bounded(int lowest, int highest) |
138 | { |
139 | return bounded(highest - lowest) + lowest; |
140 | } |
141 | |
142 | template <typename UInt, IfValidUInt<UInt> = true> |
143 | void fillRange(UInt *buffer, qsizetype count) |
144 | { |
145 | _fillRange(buffer, buffer + count); |
146 | } |
147 | |
148 | template <typename UInt, size_t N, IfValidUInt<UInt> = true> |
149 | void fillRange(UInt (&buffer)[N]) |
150 | { |
151 | _fillRange(buffer, buffer + N); |
152 | } |
153 | |
154 | // API like std::seed_seq |
155 | template <typename ForwardIterator> |
156 | void generate(ForwardIterator begin, ForwardIterator end) |
157 | { |
158 | std::generate(begin, end, [this]() { return generate(); }); |
159 | } |
160 | |
161 | void generate(quint32 *begin, quint32 *end) |
162 | { |
163 | _fillRange(begin, end); |
164 | } |
165 | |
166 | // API like std:: random engines |
167 | typedef quint32 result_type; |
168 | result_type operator()() { return generate(); } |
169 | void seed(quint32 s = 1) { *this = { s }; } |
170 | void seed(std::seed_seq &sseq) noexcept { *this = { sseq }; } |
171 | Q_CORE_EXPORT void discard(unsigned long long z); |
172 | static Q_DECL_CONSTEXPR result_type min() { return std::numeric_limits<result_type>::min(); } |
173 | static Q_DECL_CONSTEXPR result_type max() { return std::numeric_limits<result_type>::max(); } |
174 | |
175 | static inline Q_DECL_CONST_FUNCTION QRandomGenerator *system(); |
176 | static inline Q_DECL_CONST_FUNCTION QRandomGenerator *global(); |
177 | static inline QRandomGenerator securelySeeded(); |
178 | |
179 | protected: |
180 | enum System {}; |
181 | QRandomGenerator(System); |
182 | |
183 | private: |
184 | Q_CORE_EXPORT void _fillRange(void *buffer, void *bufferEnd); |
185 | |
186 | friend class QRandomGenerator64; |
187 | struct SystemGenerator; |
188 | struct SystemAndGlobalGenerators; |
189 | using RandomEngine = std::mersenne_twister_engine<quint32, |
190 | 32,624,397,31,0x9908b0df,11,0xffffffff,7,0x9d2c5680,15,0xefc60000,18,1812433253>; |
191 | |
192 | union Storage { |
193 | uint dummy; |
194 | #ifdef Q_COMPILER_UNRESTRICTED_UNIONS |
195 | RandomEngine twister; |
196 | RandomEngine &engine() { return twister; } |
197 | const RandomEngine &engine() const { return twister; } |
198 | #else |
199 | std::aligned_storage<sizeof(RandomEngine), Q_ALIGNOF(RandomEngine)>::type buffer; |
200 | RandomEngine &engine() { return reinterpret_cast<RandomEngine &>(buffer); } |
201 | const RandomEngine &engine() const { return reinterpret_cast<const RandomEngine &>(buffer); } |
202 | #endif |
203 | |
204 | Q_STATIC_ASSERT_X(std::is_trivially_destructible<RandomEngine>::value, |
205 | "std::mersenne_twister not trivially destructible as expected" ); |
206 | Q_DECL_CONSTEXPR Storage(); |
207 | }; |
208 | uint type; |
209 | Storage storage; |
210 | }; |
211 | |
212 | class QRandomGenerator64 : public QRandomGenerator |
213 | { |
214 | QRandomGenerator64(System); |
215 | public: |
216 | // unshadow generate() overloads, since we'll override. |
217 | using QRandomGenerator::generate; |
218 | quint64 generate() { return generate64(); } |
219 | |
220 | typedef quint64 result_type; |
221 | result_type operator()() { return generate64(); } |
222 | |
223 | #ifndef Q_QDOC |
224 | QRandomGenerator64(quint32 seedValue = 1) |
225 | : QRandomGenerator(seedValue) |
226 | {} |
227 | template <qsizetype N> QRandomGenerator64(const quint32 (&seedBuffer)[N]) |
228 | : QRandomGenerator(seedBuffer) |
229 | {} |
230 | QRandomGenerator64(const quint32 *seedBuffer, qsizetype len) |
231 | : QRandomGenerator(seedBuffer, len) |
232 | {} |
233 | QRandomGenerator64(std::seed_seq &sseq) noexcept |
234 | : QRandomGenerator(sseq) |
235 | {} |
236 | QRandomGenerator64(const quint32 *begin, const quint32 *end) |
237 | : QRandomGenerator(begin, end) |
238 | {} |
239 | QRandomGenerator64(const QRandomGenerator &other) : QRandomGenerator(other) {} |
240 | |
241 | void discard(unsigned long long z) |
242 | { |
243 | Q_ASSERT_X(z * 2 > z, "QRandomGenerator64::discard" , |
244 | "Overflow. Are you sure you want to skip over 9 quintillion samples?" ); |
245 | QRandomGenerator::discard(z * 2); |
246 | } |
247 | |
248 | static Q_DECL_CONSTEXPR result_type min() { return std::numeric_limits<result_type>::min(); } |
249 | static Q_DECL_CONSTEXPR result_type max() { return std::numeric_limits<result_type>::max(); } |
250 | static Q_DECL_CONST_FUNCTION Q_CORE_EXPORT QRandomGenerator64 *system(); |
251 | static Q_DECL_CONST_FUNCTION Q_CORE_EXPORT QRandomGenerator64 *global(); |
252 | static Q_CORE_EXPORT QRandomGenerator64 securelySeeded(); |
253 | #endif // Q_QDOC |
254 | }; |
255 | |
256 | inline QRandomGenerator *QRandomGenerator::system() |
257 | { |
258 | return QRandomGenerator64::system(); |
259 | } |
260 | |
261 | inline QRandomGenerator *QRandomGenerator::global() |
262 | { |
263 | return QRandomGenerator64::global(); |
264 | } |
265 | |
266 | QRandomGenerator QRandomGenerator::securelySeeded() |
267 | { |
268 | return QRandomGenerator64::securelySeeded(); |
269 | } |
270 | |
271 | QT_END_NAMESPACE |
272 | |
273 | #endif // QRANDOM_H |
274 | |