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

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