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 {}
QRandomGenerator(const quint32 (& seedBuffer)[N])65 template <qsizetype N> QRandomGenerator(const quint32 (&seedBuffer)[N])
66 : QRandomGenerator(seedBuffer, seedBuffer + N)
67 {}
QRandomGenerator(const quint32 * seedBuffer,qsizetype len)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
generate()84 quint32 generate()
85 {
86 quint32 ret;
87 fillRange(&ret, 1);
88 return ret;
89 }
90
generate64()91 quint64 generate64()
92 {
93 quint32 buf[2];
94 fillRange(buf);
95 return buf[0] | (quint64(buf[1]) << 32);
96 }
97
generateDouble()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
bounded(double highest)112 double bounded(double highest)
113 {
114 return generateDouble() * highest;
115 }
116
bounded(quint32 highest)117 quint32 bounded(quint32 highest)
118 {
119 quint64 value = generate();
120 value *= highest;
121 value /= (max)() + quint64(1);
122 return quint32(value);
123 }
124
bounded(quint32 lowest,quint32 highest)125 quint32 bounded(quint32 lowest, quint32 highest)
126 {
127 Q_ASSERT(highest > lowest);
128 return bounded(highest - lowest) + lowest;
129 }
130
bounded(int highest)131 int bounded(int highest)
132 {
133 Q_ASSERT(highest > 0);
134 return int(bounded(0U, quint32(highest)));
135 }
136
bounded(int lowest,int highest)137 int bounded(int lowest, int highest)
138 {
139 return bounded(highest - lowest) + lowest;
140 }
141
142 template <typename UInt, IfValidUInt<UInt> = true>
fillRange(UInt * buffer,qsizetype count)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>
fillRange(UInt (& buffer)[N])149 void fillRange(UInt (&buffer)[N])
150 {
151 _fillRange(buffer, buffer + N);
152 }
153
154 // API like std::seed_seq
155 template <typename ForwardIterator>
generate(ForwardIterator begin,ForwardIterator end)156 void generate(ForwardIterator begin, ForwardIterator end)
157 {
158 std::generate(begin, end, [this]() { return generate(); });
159 }
160
generate(quint32 * begin,quint32 * end)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;
operator()168 result_type operator()() { return generate(); }
169 void seed(quint32 s = 1) { *this = { s }; }
seed(std::seed_seq & sseq)170 void seed(std::seed_seq &sseq) noexcept { *this = { sseq }; }
171 Q_CORE_EXPORT void discard(unsigned long long z);
min()172 static Q_DECL_CONSTEXPR result_type min() { return std::numeric_limits<result_type>::min(); }
max()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;
engine()196 RandomEngine &engine() { return twister; }
engine()197 const RandomEngine &engine() const { return twister; }
198 #else
199 std::aligned_storage<sizeof(RandomEngine), Q_ALIGNOF(RandomEngine)>::type buffer;
engine()200 RandomEngine &engine() { return reinterpret_cast<RandomEngine &>(buffer); }
engine()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;
generate()218 quint64 generate() { return generate64(); }
219
220 typedef quint64 result_type;
operator()221 result_type operator()() { return generate64(); }
222
223 #ifndef Q_QDOC
224 QRandomGenerator64(quint32 seedValue = 1)
QRandomGenerator(seedValue)225 : QRandomGenerator(seedValue)
226 {}
QRandomGenerator64(const quint32 (& seedBuffer)[N])227 template <qsizetype N> QRandomGenerator64(const quint32 (&seedBuffer)[N])
228 : QRandomGenerator(seedBuffer)
229 {}
QRandomGenerator64(const quint32 * seedBuffer,qsizetype len)230 QRandomGenerator64(const quint32 *seedBuffer, qsizetype len)
231 : QRandomGenerator(seedBuffer, len)
232 {}
QRandomGenerator64(std::seed_seq & sseq)233 QRandomGenerator64(std::seed_seq &sseq) noexcept
234 : QRandomGenerator(sseq)
235 {}
QRandomGenerator64(const quint32 * begin,const quint32 * end)236 QRandomGenerator64(const quint32 *begin, const quint32 *end)
237 : QRandomGenerator(begin, end)
238 {}
QRandomGenerator64(const QRandomGenerator & other)239 QRandomGenerator64(const QRandomGenerator &other) : QRandomGenerator(other) {}
240
discard(unsigned long long z)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
min()248 static Q_DECL_CONSTEXPR result_type min() { return std::numeric_limits<result_type>::min(); }
max()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
system()256 inline QRandomGenerator *QRandomGenerator::system()
257 {
258 return QRandomGenerator64::system();
259 }
260
global()261 inline QRandomGenerator *QRandomGenerator::global()
262 {
263 return QRandomGenerator64::global();
264 }
265
securelySeeded()266 QRandomGenerator QRandomGenerator::securelySeeded()
267 {
268 return QRandomGenerator64::securelySeeded();
269 }
270
271 QT_END_NAMESPACE
272
273 #endif // QRANDOM_H
274