1/****************************************************************************
2**
3** Copyright (C) 2020 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/qalgorithms.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
54QT_BEGIN_NAMESPACE
55
56class 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;
61public:
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 return _fillRange(nullptr, 1);
87 }
88
89 quint64 generate64()
90 {
91 return _fillRange(nullptr, sizeof(quint64) / sizeof(quint32));
92 }
93
94 double generateDouble()
95 {
96 // IEEE 754 double precision has:
97 // 1 bit sign
98 // 10 bits exponent
99 // 53 bits mantissa
100 // In order for our result to be normalized in the range [0, 1), we
101 // need exactly 53 bits of random data. Use generate64() to get enough.
102 quint64 x = generate64();
103 quint64 limit = Q_UINT64_C(1) << std::numeric_limits<double>::digits;
104 x >>= std::numeric_limits<quint64>::digits - std::numeric_limits<double>::digits;
105 return double(x) / double(limit);
106 }
107
108 double bounded(double highest)
109 {
110 return generateDouble() * highest;
111 }
112
113 quint32 bounded(quint32 highest)
114 {
115 quint64 value = generate();
116 value *= highest;
117 value /= (max)() + quint64(1);
118 return quint32(value);
119 }
120
121 quint32 bounded(quint32 lowest, quint32 highest)
122 {
123 Q_ASSERT(highest > lowest);
124 return bounded(highest - lowest) + lowest;
125 }
126
127 int bounded(int highest)
128 {
129 Q_ASSERT(highest > 0);
130 return int(bounded(0U, quint32(highest)));
131 }
132
133 int bounded(int lowest, int highest)
134 {
135 return bounded(highest - lowest) + lowest;
136 }
137
138 quint64 bounded(quint64 highest);
139
140 quint64 bounded(quint64 lowest, quint64 highest)
141 {
142 Q_ASSERT(highest > lowest);
143 return bounded(highest - lowest) + lowest;
144 }
145
146 qint64 bounded(qint64 highest)
147 {
148 Q_ASSERT(highest > 0);
149 return qint64(bounded(quint64(0), quint64(highest)));
150 }
151
152 qint64 bounded(qint64 lowest, qint64 highest)
153 {
154 return bounded(highest - lowest) + lowest;
155 }
156
157 // these functions here only to help with ambiguous overloads
158 qint64 bounded(int lowest, qint64 highest)
159 {
160 return bounded(qint64(lowest), qint64(highest));
161 }
162 qint64 bounded(qint64 lowest, int highest)
163 {
164 return bounded(qint64(lowest), qint64(highest));
165 }
166
167 quint64 bounded(unsigned lowest, quint64 highest)
168 {
169 return bounded(quint64(lowest), quint64(highest));
170 }
171 quint64 bounded(quint64 lowest, unsigned highest)
172 {
173 return bounded(quint64(lowest), quint64(highest));
174 }
175
176 template <typename UInt, IfValidUInt<UInt> = true>
177 void fillRange(UInt *buffer, qsizetype count)
178 {
179 _fillRange(buffer, count * sizeof(UInt) / sizeof(quint32));
180 }
181
182 template <typename UInt, size_t N, IfValidUInt<UInt> = true>
183 void fillRange(UInt (&buffer)[N])
184 {
185 _fillRange(buffer, N * sizeof(UInt) / sizeof(quint32));
186 }
187
188 // API like std::seed_seq
189 template <typename ForwardIterator>
190 void generate(ForwardIterator begin, ForwardIterator end)
191 {
192 std::generate(begin, end, [this]() { return generate(); });
193 }
194
195 void generate(quint32 *begin, quint32 *end)
196 {
197 _fillRange(begin, end - begin);
198 }
199
200 // API like std:: random engines
201 typedef quint32 result_type;
202 result_type operator()() { return generate(); }
203 void seed(quint32 s = 1) { *this = { s }; }
204 void seed(std::seed_seq &sseq) noexcept { *this = { sseq }; }
205 Q_CORE_EXPORT void discard(unsigned long long z);
206 static constexpr result_type min() { return std::numeric_limits<result_type>::min(); }
207 static constexpr result_type max() { return std::numeric_limits<result_type>::max(); }
208
209 static inline Q_DECL_CONST_FUNCTION QRandomGenerator *system();
210 static inline Q_DECL_CONST_FUNCTION QRandomGenerator *global();
211 static inline QRandomGenerator securelySeeded();
212
213protected:
214 enum System {};
215 QRandomGenerator(System);
216
217private:
218 Q_CORE_EXPORT quint64 _fillRange(void *buffer, qptrdiff count);
219
220 friend class QRandomGenerator64;
221 struct SystemGenerator;
222 struct SystemAndGlobalGenerators;
223 using RandomEngine = std::mersenne_twister_engine<quint32,
224 32,624,397,31,0x9908b0df,11,0xffffffff,7,0x9d2c5680,15,0xefc60000,18,1812433253>;
225
226 union Storage {
227 uint dummy;
228#ifdef Q_COMPILER_UNRESTRICTED_UNIONS
229 RandomEngine twister;
230 RandomEngine &engine() { return twister; }
231 const RandomEngine &engine() const { return twister; }
232#else
233 std::aligned_storage<sizeof(RandomEngine), alignof(RandomEngine)>::type buffer;
234 RandomEngine &engine() { return reinterpret_cast<RandomEngine &>(buffer); }
235 const RandomEngine &engine() const { return reinterpret_cast<const RandomEngine &>(buffer); }
236#endif
237
238 static_assert(std::is_trivially_destructible<RandomEngine>::value,
239 "std::mersenne_twister not trivially destructible as expected");
240 constexpr Storage();
241 };
242 uint type;
243 Storage storage;
244};
245
246class QRandomGenerator64 : public QRandomGenerator
247{
248 QRandomGenerator64(System);
249public:
250 // unshadow generate() overloads, since we'll override.
251 using QRandomGenerator::generate;
252 quint64 generate() { return generate64(); }
253
254 typedef quint64 result_type;
255 result_type operator()() { return generate64(); }
256
257#ifndef Q_QDOC
258 QRandomGenerator64(quint32 seedValue = 1)
259 : QRandomGenerator(seedValue)
260 {}
261 template <qsizetype N> QRandomGenerator64(const quint32 (&seedBuffer)[N])
262 : QRandomGenerator(seedBuffer)
263 {}
264 QRandomGenerator64(const quint32 *seedBuffer, qsizetype len)
265 : QRandomGenerator(seedBuffer, len)
266 {}
267 QRandomGenerator64(std::seed_seq &sseq) noexcept
268 : QRandomGenerator(sseq)
269 {}
270 QRandomGenerator64(const quint32 *begin, const quint32 *end)
271 : QRandomGenerator(begin, end)
272 {}
273 QRandomGenerator64(const QRandomGenerator &other) : QRandomGenerator(other) {}
274
275 void discard(unsigned long long z)
276 {
277 Q_ASSERT_X(z * 2 > z, "QRandomGenerator64::discard",
278 "Overflow. Are you sure you want to skip over 9 quintillion samples?");
279 QRandomGenerator::discard(z * 2);
280 }
281
282 static constexpr result_type min() { return std::numeric_limits<result_type>::min(); }
283 static constexpr result_type max() { return std::numeric_limits<result_type>::max(); }
284 static Q_DECL_CONST_FUNCTION Q_CORE_EXPORT QRandomGenerator64 *system();
285 static Q_DECL_CONST_FUNCTION Q_CORE_EXPORT QRandomGenerator64 *global();
286 static Q_CORE_EXPORT QRandomGenerator64 securelySeeded();
287#endif // Q_QDOC
288};
289
290inline quint64 QRandomGenerator::bounded(quint64 highest)
291{
292 // Implement an algorithm similar to libc++'s uniform_int_distribution:
293 // loop around getting a random number, mask off any bits that "highest"
294 // will never need, then check if it's higher than "highest". The number of
295 // times the loop will run is unbounded but the probability of terminating
296 // is better than 1/2 on each iteration. Therefore, the average loop count
297 // should be less than 2.
298
299 const int width = qCountLeadingZeroBits(highest - 1);
300 const quint64 mask = (quint64(1) << (std::numeric_limits<quint64>::digits - width)) - 1;
301 quint64 v;
302 do {
303 v = generate64() & mask;
304 } while (v >= highest);
305 return v;
306}
307
308inline QRandomGenerator *QRandomGenerator::system()
309{
310 return QRandomGenerator64::system();
311}
312
313inline QRandomGenerator *QRandomGenerator::global()
314{
315 return QRandomGenerator64::global();
316}
317
318QRandomGenerator QRandomGenerator::securelySeeded()
319{
320 return QRandomGenerator64::securelySeeded();
321}
322
323QT_END_NAMESPACE
324
325#endif // QRANDOM_H
326