1// Copyright (C) 2020 Intel Corporation.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QRANDOM_H
5#define QRANDOM_H
6
7#include <QtCore/qalgorithms.h>
8#include <algorithm> // for std::generate
9#include <random> // for std::mt19937
10
11#ifdef min
12# undef min
13#endif
14#ifdef max
15# undef max
16#endif
17
18QT_BEGIN_NAMESPACE
19
20class QRandomGenerator
21{
22 // restrict the template parameters to unsigned integers 32 bits wide or larger
23 template <typename UInt> using IfValidUInt =
24 typename std::enable_if<std::is_unsigned<UInt>::value && sizeof(UInt) >= sizeof(uint), bool>::type;
25public:
26 QRandomGenerator(quint32 seedValue = 1)
27 : QRandomGenerator(&seedValue, 1)
28 {}
29 template <qsizetype N> QRandomGenerator(const quint32 (&seedBuffer)[N])
30 : QRandomGenerator(seedBuffer, seedBuffer + N)
31 {}
32 QRandomGenerator(const quint32 *seedBuffer, qsizetype len)
33 : QRandomGenerator(seedBuffer, seedBuffer + len)
34 {}
35 Q_CORE_EXPORT QRandomGenerator(std::seed_seq &sseq) noexcept;
36 Q_CORE_EXPORT QRandomGenerator(const quint32 *begin, const quint32 *end);
37
38 // copy constructor & assignment operator (move unnecessary)
39 Q_CORE_EXPORT QRandomGenerator(const QRandomGenerator &other);
40 Q_CORE_EXPORT QRandomGenerator &operator=(const QRandomGenerator &other);
41
42 ~QRandomGenerator() = default;
43
44 friend Q_CORE_EXPORT bool operator==(const QRandomGenerator &rng1, const QRandomGenerator &rng2);
45 friend bool operator!=(const QRandomGenerator &rng1, const QRandomGenerator &rng2)
46 {
47 return !(rng1 == rng2);
48 }
49
50 quint32 generate()
51 {
52 return quint32(_fillRange(buffer: nullptr, count: 1));
53 }
54
55 quint64 generate64()
56 {
57 return _fillRange(buffer: nullptr, count: sizeof(quint64) / sizeof(quint32));
58 }
59
60 double generateDouble()
61 {
62 // IEEE 754 double precision has:
63 // 1 bit sign
64 // 10 bits exponent
65 // 53 bits mantissa
66 // In order for our result to be normalized in the range [0, 1), we
67 // need exactly 53 bits of random data. Use generate64() to get enough.
68 quint64 x = generate64();
69 quint64 limit = Q_UINT64_C(1) << std::numeric_limits<double>::digits;
70 x >>= std::numeric_limits<quint64>::digits - std::numeric_limits<double>::digits;
71 return double(x) / double(limit);
72 }
73
74 double bounded(double highest)
75 {
76 return generateDouble() * highest;
77 }
78
79 quint32 bounded(quint32 highest)
80 {
81 quint64 value = generate();
82 value *= highest;
83 value /= (max)() + quint64(1);
84 return quint32(value);
85 }
86
87 quint32 bounded(quint32 lowest, quint32 highest)
88 {
89 Q_ASSERT(highest > lowest);
90 return bounded(highest: highest - lowest) + lowest;
91 }
92
93 int bounded(int highest)
94 {
95 Q_ASSERT(highest > 0);
96 return int(bounded(lowest: 0U, highest: quint32(highest)));
97 }
98
99 int bounded(int lowest, int highest)
100 {
101 return bounded(highest: highest - lowest) + lowest;
102 }
103
104 quint64 bounded(quint64 highest);
105
106 quint64 bounded(quint64 lowest, quint64 highest)
107 {
108 Q_ASSERT(highest > lowest);
109 return bounded(highest: highest - lowest) + lowest;
110 }
111
112 qint64 bounded(qint64 highest)
113 {
114 Q_ASSERT(highest > 0);
115 return qint64(bounded(lowest: quint64(0), highest: quint64(highest)));
116 }
117
118 qint64 bounded(qint64 lowest, qint64 highest)
119 {
120 return bounded(highest: highest - lowest) + lowest;
121 }
122
123 // these functions here only to help with ambiguous overloads
124 qint64 bounded(int lowest, qint64 highest)
125 {
126 return bounded(lowest: qint64(lowest), highest: qint64(highest));
127 }
128 qint64 bounded(qint64 lowest, int highest)
129 {
130 return bounded(lowest: qint64(lowest), highest: qint64(highest));
131 }
132
133 quint64 bounded(unsigned lowest, quint64 highest)
134 {
135 return bounded(lowest: quint64(lowest), highest: quint64(highest));
136 }
137 quint64 bounded(quint64 lowest, unsigned highest)
138 {
139 return bounded(lowest: quint64(lowest), highest: quint64(highest));
140 }
141
142 template <typename UInt, IfValidUInt<UInt> = true>
143 void fillRange(UInt *buffer, qsizetype count)
144 {
145 _fillRange(buffer, count: count * sizeof(UInt) / sizeof(quint32));
146 }
147
148 template <typename UInt, size_t N, IfValidUInt<UInt> = true>
149 void fillRange(UInt (&buffer)[N])
150 {
151 _fillRange(buffer, count: N * sizeof(UInt) / sizeof(quint32));
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(buffer: begin, count: end - begin);
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 constexpr result_type min() { return (std::numeric_limits<result_type>::min)(); }
173 static 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
179protected:
180 enum System {};
181 QRandomGenerator(System);
182
183private:
184 Q_CORE_EXPORT quint64 _fillRange(void *buffer, qptrdiff count);
185
186 struct InitialRandomData {
187 quintptr data[16 / sizeof(quintptr)];
188 };
189 friend InitialRandomData qt_initial_random_value() noexcept;
190 friend class QRandomGenerator64;
191 struct SystemGenerator;
192 struct SystemAndGlobalGenerators;
193 using RandomEngine = std::mersenne_twister_engine<quint32,
194 32,624,397,31,0x9908b0df,11,0xffffffff,7,0x9d2c5680,15,0xefc60000,18,1812433253>;
195
196 union Storage {
197 uint dummy;
198 RandomEngine twister;
199 RandomEngine &engine() { return twister; }
200 const RandomEngine &engine() const { return twister; }
201
202 static_assert(std::is_trivially_destructible<RandomEngine>::value,
203 "std::mersenne_twister not trivially destructible as expected");
204 constexpr Storage();
205 };
206 uint type;
207 Storage storage;
208};
209
210class QRandomGenerator64 : public QRandomGenerator
211{
212 QRandomGenerator64(System);
213public:
214 // unshadow generate() overloads, since we'll override.
215 using QRandomGenerator::generate;
216 quint64 generate() { return generate64(); }
217
218 typedef quint64 result_type;
219 result_type operator()() { return generate64(); }
220
221#ifndef Q_QDOC
222 QRandomGenerator64(quint32 seedValue = 1)
223 : QRandomGenerator(seedValue)
224 {}
225 template <qsizetype N> QRandomGenerator64(const quint32 (&seedBuffer)[N])
226 : QRandomGenerator(seedBuffer)
227 {}
228 QRandomGenerator64(const quint32 *seedBuffer, qsizetype len)
229 : QRandomGenerator(seedBuffer, len)
230 {}
231 QRandomGenerator64(std::seed_seq &sseq) noexcept
232 : QRandomGenerator(sseq)
233 {}
234 QRandomGenerator64(const quint32 *begin, const quint32 *end)
235 : QRandomGenerator(begin, end)
236 {}
237 QRandomGenerator64(const QRandomGenerator &other) : QRandomGenerator(other) {}
238
239 void discard(unsigned long long z)
240 {
241 Q_ASSERT_X(z * 2 > z, "QRandomGenerator64::discard",
242 "Overflow. Are you sure you want to skip over 9 quintillion samples?");
243 QRandomGenerator::discard(z: z * 2);
244 }
245
246 static constexpr result_type min() { return (std::numeric_limits<result_type>::min)(); }
247 static constexpr result_type max() { return (std::numeric_limits<result_type>::max)(); }
248 static Q_DECL_CONST_FUNCTION Q_CORE_EXPORT QRandomGenerator64 *system();
249 static Q_DECL_CONST_FUNCTION Q_CORE_EXPORT QRandomGenerator64 *global();
250 static Q_CORE_EXPORT QRandomGenerator64 securelySeeded();
251#endif // Q_QDOC
252};
253
254inline quint64 QRandomGenerator::bounded(quint64 highest)
255{
256 // Implement an algorithm similar to libc++'s uniform_int_distribution:
257 // loop around getting a random number, mask off any bits that "highest"
258 // will never need, then check if it's higher than "highest". The number of
259 // times the loop will run is unbounded but the probability of terminating
260 // is better than 1/2 on each iteration. Therefore, the average loop count
261 // should be less than 2.
262
263 const int width = qCountLeadingZeroBits(v: highest - 1);
264 const quint64 mask = (quint64(1) << (std::numeric_limits<quint64>::digits - width)) - 1;
265 quint64 v;
266 do {
267 v = generate64() & mask;
268 } while (v >= highest);
269 return v;
270}
271
272inline QRandomGenerator *QRandomGenerator::system()
273{
274 return QRandomGenerator64::system();
275}
276
277inline QRandomGenerator *QRandomGenerator::global()
278{
279 return QRandomGenerator64::global();
280}
281
282QRandomGenerator QRandomGenerator::securelySeeded()
283{
284 return QRandomGenerator64::securelySeeded();
285}
286
287QT_END_NAMESPACE
288
289#endif // QRANDOM_H
290

source code of qtbase/src/corelib/global/qrandom.h