1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2017 Intel Corporation. |
4 | ** Contact: https://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the test suite of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:GPL-EXCEPT$ |
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 General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU |
19 | ** General Public License version 3 as published by the Free Software |
20 | ** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT |
21 | ** included in the packaging of this file. Please review the following |
22 | ** information to ensure the GNU General Public License requirements will |
23 | ** be met: https://www.gnu.org/licenses/gpl-3.0.html. |
24 | ** |
25 | ** $QT_END_LICENSE$ |
26 | ** |
27 | ****************************************************************************/ |
28 | |
29 | #include <QtTest> |
30 | #include <qlinkedlist.h> |
31 | #include <qobject.h> |
32 | #include <qrandom.h> |
33 | #include <qvector.h> |
34 | #include <private/qrandom_p.h> |
35 | |
36 | #include <algorithm> |
37 | #include <random> |
38 | |
39 | #if !QT_CONFIG(getentropy) && (defined(Q_OS_BSD4) || defined(Q_OS_WIN)) |
40 | # define HAVE_FALLBACK_ENGINE |
41 | #endif |
42 | |
43 | #define COMMA , |
44 | #define QVERIFY_3TIMES(statement) \ |
45 | do {\ |
46 | if (!static_cast<bool>(statement))\ |
47 | if (!static_cast<bool>(statement))\ |
48 | if (!QTest::qVerify(static_cast<bool>(statement), #statement, "3rd try", __FILE__, __LINE__))\ |
49 | return;\ |
50 | } while (0) |
51 | |
52 | // values chosen at random |
53 | static const quint32 RandomValue32 = 0x4d1169f1U; |
54 | static const quint64 RandomValue64 = Q_UINT64_C(0x3ce63161b998aa91); |
55 | static const double RandomValueFP = double(0.3010463714599609); |
56 | |
57 | static void setRNGControl(uint v) |
58 | { |
59 | #ifdef QT_BUILD_INTERNAL |
60 | qt_randomdevice_control.storeRelaxed(newValue: v); |
61 | #else |
62 | Q_UNUSED(v); |
63 | #endif |
64 | } |
65 | |
66 | class tst_QRandomGenerator : public QObject |
67 | { |
68 | Q_OBJECT |
69 | |
70 | public slots: |
71 | void cleanup() { setRNGControl(0); } |
72 | |
73 | private slots: |
74 | void basics(); |
75 | void knownSequence(); |
76 | void discard(); |
77 | void copying(); |
78 | void copyingGlobal(); |
79 | void copyingSystem(); |
80 | void systemRng(); |
81 | void securelySeeding(); |
82 | |
83 | void generate32_data(); |
84 | void generate32(); |
85 | void generate64_data() { generate32_data(); } |
86 | void generate64(); |
87 | void quality_data() { generate32_data(); } |
88 | void quality(); |
89 | void fillRangeUInt_data() { generate32_data(); } |
90 | void fillRangeUInt(); |
91 | void fillRangeULong_data() { generate32_data(); } |
92 | void fillRangeULong(); |
93 | void fillRangeULLong_data() { generate32_data(); } |
94 | void fillRangeULLong(); |
95 | void generateUInt_data() { generate32_data(); } |
96 | void generateUInt(); |
97 | void generateULLong_data() { generate32_data(); } |
98 | void generateULLong(); |
99 | void generateNonContiguous_data() { generate32_data(); } |
100 | void generateNonContiguous(); |
101 | |
102 | void bounded_data(); |
103 | void bounded(); |
104 | void boundedQuality_data() { generate32_data(); } |
105 | void boundedQuality(); |
106 | |
107 | void generateReal_data() { generate32_data(); } |
108 | void generateReal(); |
109 | void qualityReal_data() { generate32_data(); } |
110 | void qualityReal(); |
111 | |
112 | void seedStdRandomEngines(); |
113 | void stdUniformIntDistribution_data(); |
114 | void stdUniformIntDistribution(); |
115 | void stdGenerateCanonical_data() { generateReal_data(); } |
116 | void stdGenerateCanonical(); |
117 | void stdUniformRealDistribution_data(); |
118 | void stdUniformRealDistribution(); |
119 | void stdRandomDistributions(); |
120 | }; |
121 | |
122 | // The first 20 results of the sequence: |
123 | static const quint32 defaultRngResults[] = { |
124 | 853323747U, 2396352728U, 3025954838U, 2985633182U, 2815751046U, |
125 | 340588426U, 3587208406U, 298087538U, 2912478009U, 3642122814U, |
126 | 3202916223U, 799257577U, 1872145992U, 639469699U, 3201121432U, |
127 | 2388658094U, 1735523408U, 2215232359U, 668106566U, 2554687763U |
128 | }; |
129 | |
130 | |
131 | using namespace std; |
132 | QT_WARNING_DISABLE_GCC("-Wfloat-equal" ) |
133 | QT_WARNING_DISABLE_CLANG("-Wfloat-equal" ) |
134 | |
135 | struct RandomGenerator : public QRandomGenerator |
136 | { |
137 | RandomGenerator(uint control) |
138 | : QRandomGenerator(control ? |
139 | QRandomGenerator(control & RandomDataMask) : |
140 | *QRandomGenerator::global()) |
141 | { |
142 | setRNGControl(control); |
143 | } |
144 | }; |
145 | |
146 | void tst_QRandomGenerator::basics() |
147 | { |
148 | // default constructible |
149 | QRandomGenerator rng; |
150 | |
151 | // copyable && movable |
152 | rng = rng; |
153 | rng = std::move(rng); |
154 | |
155 | // 64-bit |
156 | QRandomGenerator64 rng64; |
157 | rng64 = rng64; |
158 | rng64 = std::move(rng64); |
159 | |
160 | // 32- and 64-bit should be interchangeable: |
161 | rng = rng64; |
162 | rng64 = rng; |
163 | rng = std::move(rng64); |
164 | rng64 = std::move(rng); |
165 | |
166 | rng = QRandomGenerator64::securelySeeded(); |
167 | rng64 = QRandomGenerator::securelySeeded(); |
168 | |
169 | // access global |
170 | QRandomGenerator *global = QRandomGenerator::global(); |
171 | QRandomGenerator globalCopy = *global; |
172 | globalCopy = *global; |
173 | QRandomGenerator64 *global64 = QRandomGenerator64::global(); |
174 | QRandomGenerator64 globalCopy64 = *global64; |
175 | globalCopy64 = *global64; |
176 | |
177 | // access system |
178 | QRandomGenerator *system = QRandomGenerator::system(); |
179 | QRandomGenerator systemRng = *system; |
180 | systemRng = *system; |
181 | |
182 | QRandomGenerator64 *system64 = QRandomGenerator64::system(); |
183 | QRandomGenerator64 systemRng64 = *system64; |
184 | systemRng64 = *system64; |
185 | |
186 | Q_STATIC_ASSERT(std::is_same<decltype(rng64.generate()) COMMA quint64>::value); |
187 | Q_STATIC_ASSERT(std::is_same<decltype(system64->generate()) COMMA quint64>::value); |
188 | } |
189 | |
190 | void tst_QRandomGenerator::knownSequence() |
191 | { |
192 | QRandomGenerator rng; |
193 | for (quint32 x : defaultRngResults) |
194 | QCOMPARE(rng(), x); |
195 | |
196 | // should work again if we reseed it |
197 | rng.seed(); |
198 | for (quint32 x : defaultRngResults) |
199 | QCOMPARE(rng(), x); |
200 | } |
201 | |
202 | void tst_QRandomGenerator::discard() |
203 | { |
204 | QRandomGenerator rng; |
205 | rng.discard(z: 1); |
206 | QCOMPARE(rng(), defaultRngResults[1]); |
207 | |
208 | rng.discard(z: 9); |
209 | QCOMPARE(rng(), defaultRngResults[11]); |
210 | } |
211 | |
212 | void tst_QRandomGenerator::copying() |
213 | { |
214 | QRandomGenerator rng1; |
215 | QRandomGenerator rng2 = rng1; |
216 | QCOMPARE(rng1, rng2); |
217 | |
218 | quint32 samples[20]; |
219 | rng1.fillRange(buffer&: samples); |
220 | |
221 | // not equal anymore |
222 | QVERIFY(rng1 != rng2); |
223 | |
224 | // should produce the same sequence, whichever it was |
225 | for (quint32 x : samples) |
226 | QCOMPARE(rng2(), x); |
227 | |
228 | // now they should compare equal again |
229 | QCOMPARE(rng1, rng2); |
230 | } |
231 | |
232 | void tst_QRandomGenerator::copyingGlobal() |
233 | { |
234 | QRandomGenerator &global = *QRandomGenerator::global(); |
235 | QRandomGenerator copy = global; |
236 | QCOMPARE(copy, global); |
237 | QCOMPARE(global, copy); |
238 | |
239 | quint32 samples[20]; |
240 | global.fillRange(buffer&: samples); |
241 | |
242 | // not equal anymore |
243 | QVERIFY(copy != global); |
244 | |
245 | // should produce the same sequence, whichever it was |
246 | for (quint32 x : samples) |
247 | QCOMPARE(copy(), x); |
248 | |
249 | // equal again |
250 | QCOMPARE(copy, global); |
251 | QCOMPARE(global, copy); |
252 | } |
253 | |
254 | void tst_QRandomGenerator::copyingSystem() |
255 | { |
256 | QRandomGenerator &system = *QRandomGenerator::system(); |
257 | QRandomGenerator copy = system; |
258 | QRandomGenerator copy2 = copy; |
259 | copy2 = copy; |
260 | QCOMPARE(system, copy); |
261 | QCOMPARE(copy, copy2); |
262 | |
263 | quint32 samples[20]; |
264 | copy2.fillRange(buffer&: samples); |
265 | |
266 | // they still compre equally |
267 | QCOMPARE(system, copy); |
268 | QCOMPARE(copy, copy2); |
269 | |
270 | // should NOT produce the same sequence, whichever it was |
271 | int sameCount = 0; |
272 | for (quint32 x : samples) |
273 | sameCount += (copy() == x); |
274 | QVERIFY(sameCount < 20); |
275 | |
276 | QCOMPARE(system, copy); |
277 | QCOMPARE(copy, copy2); |
278 | } |
279 | |
280 | void tst_QRandomGenerator::systemRng() |
281 | { |
282 | QRandomGenerator *rng = QRandomGenerator::system(); |
283 | rng->generate(); |
284 | rng->generate64(); |
285 | rng->generateDouble(); |
286 | rng->bounded(highest: 100); |
287 | rng->bounded(highest: 100U); |
288 | |
289 | #ifdef QT_BUILD_INTERNAL |
290 | quint32 setpoint = std::numeric_limits<int>::max(); |
291 | ++setpoint; |
292 | quint64 setpoint64 = quint64(setpoint) << 32 | setpoint; |
293 | setRNGControl(SetRandomData | setpoint); |
294 | |
295 | QCOMPARE(rng->generate(), setpoint); |
296 | QCOMPARE(rng->generate64(), setpoint64); |
297 | QCOMPARE(rng->generateDouble(), ldexp(setpoint64, -64)); |
298 | QCOMPARE(rng->bounded(100), 50); |
299 | #endif |
300 | } |
301 | |
302 | void tst_QRandomGenerator::securelySeeding() |
303 | { |
304 | QRandomGenerator rng1 = QRandomGenerator::securelySeeded(); |
305 | QRandomGenerator rng2 = QRandomGenerator::securelySeeded(); |
306 | |
307 | quint32 samples[20]; |
308 | rng1.fillRange(buffer&: samples); |
309 | |
310 | // should NOT produce the same sequence, whichever it was |
311 | int sameCount = 0; |
312 | for (quint32 x : samples) |
313 | sameCount += (rng2() == x); |
314 | QVERIFY(sameCount < 20); |
315 | } |
316 | |
317 | void tst_QRandomGenerator::generate32_data() |
318 | { |
319 | QTest::addColumn<uint>(name: "control" ); |
320 | QTest::newRow(dataTag: "fixed" ) << (RandomValue32 & RandomDataMask); |
321 | QTest::newRow(dataTag: "global" ) << 0U; |
322 | #ifdef QT_BUILD_INTERNAL |
323 | if (qHasHwrng()) |
324 | QTest::newRow(dataTag: "hwrng" ) << uint(UseSystemRNG); |
325 | QTest::newRow(dataTag: "system" ) << uint(UseSystemRNG | SkipHWRNG); |
326 | # ifdef HAVE_FALLBACK_ENGINE |
327 | QTest::newRow("system-fallback" ) << uint(UseSystemRNG | SkipHWRNG | SkipSystemRNG); |
328 | # endif |
329 | #endif |
330 | } |
331 | |
332 | void tst_QRandomGenerator::generate32() |
333 | { |
334 | QFETCH(uint, control); |
335 | RandomGenerator rng(control); |
336 | |
337 | for (int i = 0; i < 4; ++i) { |
338 | QVERIFY_3TIMES([&] { |
339 | quint32 value = rng.generate(); |
340 | return value != 0 && value != RandomValue32; |
341 | }()); |
342 | } |
343 | |
344 | // and should hopefully be different from repeated calls |
345 | for (int i = 0; i < 4; ++i) |
346 | QVERIFY_3TIMES(rng.generate() != rng.generate()); |
347 | } |
348 | |
349 | void tst_QRandomGenerator::generate64() |
350 | { |
351 | QFETCH(uint, control); |
352 | RandomGenerator rng(control); |
353 | |
354 | QVERIFY_3TIMES(rng.generate64() > std::numeric_limits<quint32>::max()); |
355 | for (int i = 0; i < 4; ++i) { |
356 | QVERIFY_3TIMES([&] { |
357 | quint64 value = rng.generate64(); |
358 | return value != 0 && value != RandomValue32 && value != RandomValue64; |
359 | }()); |
360 | } |
361 | |
362 | // and should hopefully be different from repeated calls |
363 | for (int i = 0; i < 4; ++i) |
364 | QVERIFY_3TIMES(rng.generate64() != rng.generate64()); |
365 | for (int i = 0; i < 4; ++i) |
366 | QVERIFY_3TIMES(rng.generate() != quint32(rng.generate64())); |
367 | for (int i = 0; i < 4; ++i) |
368 | QVERIFY_3TIMES(rng.generate() != (rng.generate64() >> 32)); |
369 | } |
370 | |
371 | void tst_QRandomGenerator::quality() |
372 | { |
373 | enum { |
374 | BufferSize = 2048, |
375 | BufferCount = BufferSize / sizeof(quint32), |
376 | |
377 | // if the distribution were perfect, each byte in the buffer would |
378 | // appear exactly: |
379 | PerfectDistribution = BufferSize / (UCHAR_MAX + 1), |
380 | |
381 | // The chance of a value appearing N times above its perfect |
382 | // distribution is the same as it appearing N times in a row: |
383 | // N Probability |
384 | // 1 100% |
385 | // 2 0.390625% |
386 | // 3 15.25 in a million |
387 | // 4 59.60 in a billion |
388 | // 8 5.421e-20 |
389 | // 16 2.938e-39 |
390 | |
391 | AcceptableThreshold = 4 * PerfectDistribution, |
392 | FailureThreshold = 16 * PerfectDistribution |
393 | }; |
394 | Q_STATIC_ASSERT(FailureThreshold > AcceptableThreshold); |
395 | |
396 | QFETCH(uint, control); |
397 | if (control & RandomDataMask) |
398 | return; |
399 | RandomGenerator rng(control); |
400 | |
401 | int histogram[UCHAR_MAX + 1]; |
402 | memset(s: histogram, c: 0, n: sizeof(histogram)); |
403 | |
404 | { |
405 | // test the quality of the generator |
406 | quint32 buffer[BufferCount]; |
407 | memset(s: buffer, c: 0xcc, n: sizeof(buffer)); |
408 | generate_n(first: buffer, n: +BufferCount, gen: [&] { return rng.generate(); }); |
409 | |
410 | quint8 *ptr = reinterpret_cast<quint8 *>(buffer); |
411 | quint8 *end = ptr + sizeof(buffer); |
412 | for ( ; ptr != end; ++ptr) |
413 | histogram[*ptr]++; |
414 | } |
415 | |
416 | for (uint i = 0; i < sizeof(histogram)/sizeof(histogram[0]); ++i) { |
417 | int v = histogram[i]; |
418 | if (v > AcceptableThreshold) |
419 | qDebug() << i << "above threshold:" << v; |
420 | QVERIFY2(v < FailureThreshold, QByteArray::number(i)); |
421 | } |
422 | qDebug() << "Average:" << (std::accumulate(first: begin(arr&: histogram), last: end(arr&: histogram), init: 0) / (1. * (UCHAR_MAX + 1))) |
423 | << "(expected" << int(PerfectDistribution) << "ideally)" |
424 | << "Max:" << *std::max_element(first: begin(arr&: histogram), last: end(arr&: histogram)) |
425 | << "at" << std::max_element(first: begin(arr&: histogram), last: end(arr&: histogram)) - histogram |
426 | << "Min:" << *std::min_element(first: begin(arr&: histogram), last: end(arr&: histogram)) |
427 | << "at" << std::min_element(first: begin(arr&: histogram), last: end(arr&: histogram)) - histogram; |
428 | } |
429 | |
430 | template <typename T> void fillRange_template() |
431 | { |
432 | QFETCH(uint, control); |
433 | RandomGenerator rng(control); |
434 | |
435 | for (int i = 0; i < 4; ++i) { |
436 | QVERIFY_3TIMES([&] { |
437 | T value[1] = { RandomValue32 }; |
438 | rng.fillRange(value); |
439 | return value[0] != 0 && value[0] != RandomValue32; |
440 | }()); |
441 | } |
442 | |
443 | for (int i = 0; i < 4; ++i) { |
444 | QVERIFY_3TIMES([&] { |
445 | T array[2] = {}; |
446 | rng.fillRange(array); |
447 | return array[0] != array[1]; |
448 | }()); |
449 | } |
450 | |
451 | if (sizeof(T) > sizeof(quint32)) { |
452 | // just to shut up a warning about shifting uint more than the width |
453 | enum { Shift = sizeof(T) / 2 * CHAR_BIT }; |
454 | QVERIFY_3TIMES([&] { |
455 | T value[1] = { }; |
456 | rng.fillRange(value); |
457 | return quint32(value[0] >> Shift) != quint32(value[0]); |
458 | }()); |
459 | } |
460 | |
461 | // fill in a longer range |
462 | auto longerArrayCheck = [&] { |
463 | T array[32]; |
464 | memset(array, 0, sizeof(array)); |
465 | rng.fillRange(array); |
466 | if (sizeof(T) == sizeof(RandomValue64) |
467 | && find(begin(array), end(array), RandomValue64) != end(array)) |
468 | return false; |
469 | return find(begin(array), end(array), 0) == end(array) && |
470 | find(begin(array), end(array), RandomValue32) == end(array); |
471 | }; |
472 | QVERIFY_3TIMES(longerArrayCheck()); |
473 | } |
474 | |
475 | void tst_QRandomGenerator::fillRangeUInt() { fillRange_template<uint>(); } |
476 | void tst_QRandomGenerator::fillRangeULong() { fillRange_template<ulong>(); } |
477 | void tst_QRandomGenerator::fillRangeULLong() { fillRange_template<qulonglong>(); } |
478 | |
479 | template <typename T> void generate_template() |
480 | { |
481 | QFETCH(uint, control); |
482 | RandomGenerator rng(control); |
483 | |
484 | // almost the same as fillRange, but limited to 32 bits |
485 | for (int i = 0; i < 4; ++i) { |
486 | QVERIFY_3TIMES([&] { |
487 | T value[1] = { RandomValue32 }; |
488 | QRandomGenerator().generate(begin(value), end(value)); |
489 | return value[0] != 0 && value[0] != RandomValue32 |
490 | && value[0] <= numeric_limits<quint32>::max(); |
491 | }()); |
492 | } |
493 | |
494 | // fill in a longer range |
495 | auto longerArrayCheck = [&] { |
496 | T array[72] = {}; // at least 256 bytes |
497 | QRandomGenerator().generate(begin(array), end(array)); |
498 | return find_if(begin(array), end(array), [&](T cur) { |
499 | return cur == 0 || cur == RandomValue32 || |
500 | cur == RandomValue64 || cur > numeric_limits<quint32>::max(); |
501 | }) == end(array); |
502 | }; |
503 | QVERIFY_3TIMES(longerArrayCheck()); |
504 | } |
505 | |
506 | void tst_QRandomGenerator::generateUInt() { generate_template<uint>(); } |
507 | void tst_QRandomGenerator::generateULLong() { generate_template<qulonglong>(); } |
508 | |
509 | void tst_QRandomGenerator::generateNonContiguous() |
510 | { |
511 | QFETCH(uint, control); |
512 | RandomGenerator rng(control); |
513 | |
514 | std::list<quint64> list(8); |
515 | auto longerArrayCheck = [&] { |
516 | QRandomGenerator().generate(begin: list.begin(), end: list.end()); |
517 | return find_if(first: list.begin(), last: list.end(), pred: [&](quint64 cur) { |
518 | return cur == 0 || cur == RandomValue32 || |
519 | cur == RandomValue64 || cur > numeric_limits<quint32>::max(); |
520 | }) == list.end(); |
521 | }; |
522 | QVERIFY_3TIMES(longerArrayCheck()); |
523 | } |
524 | |
525 | void tst_QRandomGenerator::bounded_data() |
526 | { |
527 | #ifndef QT_BUILD_INTERNAL |
528 | QSKIP("Test only possible in developer builds" ); |
529 | #endif |
530 | |
531 | QTest::addColumn<uint>(name: "control" ); |
532 | QTest::addColumn<quint32>(name: "sup" ); |
533 | QTest::addColumn<quint32>(name: "expected" ); |
534 | |
535 | auto newRow = [&](quint32 val, quint32 sup) { |
536 | // calculate the scaled value |
537 | quint64 scaled = val; |
538 | scaled <<= 32; |
539 | scaled /= sup; |
540 | unsigned shifted = unsigned(scaled); |
541 | Q_ASSERT(val < sup); |
542 | Q_ASSERT((shifted & RandomDataMask) == shifted); |
543 | |
544 | unsigned control = SetRandomData | shifted; |
545 | QTest::addRow(format: "%u,%u" , val, sup) << control << sup << val; |
546 | }; |
547 | |
548 | // useless: we can only generate zeroes: |
549 | newRow(0, 1); |
550 | |
551 | newRow(25, 200); |
552 | newRow(50, 200); |
553 | newRow(75, 200); |
554 | } |
555 | |
556 | void tst_QRandomGenerator::bounded() |
557 | { |
558 | QFETCH(uint, control); |
559 | QFETCH(quint32, sup); |
560 | QFETCH(quint32, expected); |
561 | RandomGenerator rng(control); |
562 | |
563 | quint32 value = rng.bounded(highest: sup); |
564 | QVERIFY(value < sup); |
565 | QCOMPARE(value, expected); |
566 | |
567 | int ivalue = rng.bounded(highest: sup); |
568 | QVERIFY(ivalue < int(sup)); |
569 | QCOMPARE(ivalue, int(expected)); |
570 | |
571 | // confirm only the bound now |
572 | setRNGControl(control & (SkipHWRNG|SkipSystemRNG|UseSystemRNG)); |
573 | value = rng.bounded(highest: sup); |
574 | QVERIFY(value < sup); |
575 | |
576 | value = rng.bounded(lowest: sup / 2, highest: 3 * sup / 2); |
577 | QVERIFY(value >= sup / 2); |
578 | QVERIFY(value < 3 * sup / 2); |
579 | |
580 | ivalue = rng.bounded(lowest: -int(sup), highest: int(sup)); |
581 | QVERIFY(ivalue >= -int(sup)); |
582 | QVERIFY(ivalue < int(sup)); |
583 | |
584 | // wholly negative range |
585 | ivalue = rng.bounded(lowest: -int(sup), highest: 0); |
586 | QVERIFY(ivalue >= -int(sup)); |
587 | QVERIFY(ivalue < 0); |
588 | } |
589 | |
590 | void tst_QRandomGenerator::boundedQuality() |
591 | { |
592 | enum { Bound = 283 }; // a prime number |
593 | enum { |
594 | BufferCount = Bound * 32, |
595 | |
596 | // if the distribution were perfect, each byte in the buffer would |
597 | // appear exactly: |
598 | PerfectDistribution = BufferCount / Bound, |
599 | |
600 | // The chance of a value appearing N times above its perfect |
601 | // distribution is the same as it appearing N times in a row: |
602 | // N Probability |
603 | // 1 100% |
604 | // 2 0.390625% |
605 | // 3 15.25 in a million |
606 | // 4 59.60 in a billion |
607 | // 8 5.421e-20 |
608 | // 16 2.938e-39 |
609 | |
610 | AcceptableThreshold = 4 * PerfectDistribution, |
611 | FailureThreshold = 16 * PerfectDistribution |
612 | }; |
613 | Q_STATIC_ASSERT(FailureThreshold > AcceptableThreshold); |
614 | |
615 | QFETCH(uint, control); |
616 | if (control & RandomDataMask) |
617 | return; |
618 | RandomGenerator rng(control); |
619 | |
620 | int histogram[Bound]; |
621 | memset(s: histogram, c: 0, n: sizeof(histogram)); |
622 | |
623 | { |
624 | // test the quality of the generator |
625 | QVector<quint32> buffer(BufferCount, 0xcdcdcdcd); |
626 | generate(first: buffer.begin(), last: buffer.end(), gen: [&] { return rng.bounded(highest: Bound); }); |
627 | |
628 | for (quint32 value : qAsConst(t&: buffer)) { |
629 | QVERIFY(value < Bound); |
630 | histogram[value]++; |
631 | } |
632 | } |
633 | |
634 | for (unsigned i = 0; i < sizeof(histogram)/sizeof(histogram[0]); ++i) { |
635 | int v = histogram[i]; |
636 | if (v > AcceptableThreshold) |
637 | qDebug() << i << "above threshold:" << v; |
638 | QVERIFY2(v < FailureThreshold, QByteArray::number(i)); |
639 | } |
640 | |
641 | qDebug() << "Average:" << (std::accumulate(first: begin(arr&: histogram), last: end(arr&: histogram), init: 0) / qreal(Bound)) |
642 | << "(expected" << int(PerfectDistribution) << "ideally)" |
643 | << "Max:" << *std::max_element(first: begin(arr&: histogram), last: end(arr&: histogram)) |
644 | << "at" << std::max_element(first: begin(arr&: histogram), last: end(arr&: histogram)) - histogram |
645 | << "Min:" << *std::min_element(first: begin(arr&: histogram), last: end(arr&: histogram)) |
646 | << "at" << std::min_element(first: begin(arr&: histogram), last: end(arr&: histogram)) - histogram; |
647 | } |
648 | |
649 | void tst_QRandomGenerator::generateReal() |
650 | { |
651 | QFETCH(uint, control); |
652 | RandomGenerator rng(control); |
653 | |
654 | for (int i = 0; i < 4; ++i) { |
655 | QVERIFY_3TIMES([&] { |
656 | qreal value = rng.generateDouble(); |
657 | return value >= 0 && value < 1 && value != RandomValueFP; |
658 | }()); |
659 | } |
660 | |
661 | // and should hopefully be different from repeated calls |
662 | for (int i = 0; i < 4; ++i) |
663 | QVERIFY_3TIMES(rng.generateDouble() != rng.generateDouble()); |
664 | } |
665 | |
666 | void tst_QRandomGenerator::qualityReal() |
667 | { |
668 | QFETCH(uint, control); |
669 | if (control & RandomDataMask) |
670 | return; |
671 | RandomGenerator rng(control); |
672 | |
673 | enum { |
674 | SampleSize = 16000, |
675 | |
676 | // Expected value: sample size times proportion of the range: |
677 | PerfectOctile = SampleSize / 8, |
678 | PerfectHalf = SampleSize / 2, |
679 | |
680 | // Variance is (1 - proportion of range) * expected; sqrt() for standard deviations. |
681 | // Should usually be within twice that and almost never outside four times: |
682 | RangeHalf = 252, // floor(4 * sqrt((1 - 0.5) * PerfectHalf)) |
683 | RangeOctile = 167 // floor(4 * sqrt((1 - 0.125) * PerfectOctile)) |
684 | }; |
685 | |
686 | double data[SampleSize]; |
687 | std::generate(first: std::begin(arr&: data), last: std::end(arr&: data), gen: [&rng] { return rng.generateDouble(); }); |
688 | |
689 | int aboveHalf = 0; |
690 | int belowOneEighth = 0; |
691 | int aboveSevenEighths = 0; |
692 | for (double x : data) { |
693 | aboveHalf += x >= 0.5; |
694 | belowOneEighth += x < 0.125; |
695 | aboveSevenEighths += x >= 0.875; |
696 | |
697 | // these are strict requirements |
698 | QVERIFY(x >= 0); |
699 | QVERIFY(x < 1); |
700 | } |
701 | |
702 | qInfo(msg: "Halfway distribution: %.1f - %.1f" , 100. * aboveHalf / SampleSize, 100 - 100. * aboveHalf / SampleSize); |
703 | qInfo(msg: "%.1f below 1/8 (expected 12.5%% ideally)" , 100. * belowOneEighth / SampleSize); |
704 | qInfo(msg: "%.1f above 7/8 (expected 12.5%% ideally)" , 100. * aboveSevenEighths / SampleSize); |
705 | |
706 | QVERIFY(aboveHalf < PerfectHalf + RangeHalf); |
707 | QVERIFY(aboveHalf > PerfectHalf - RangeHalf); |
708 | QVERIFY(aboveSevenEighths < PerfectOctile + RangeOctile); |
709 | QVERIFY(aboveSevenEighths > PerfectOctile - RangeOctile); |
710 | QVERIFY(belowOneEighth < PerfectOctile + RangeOctile); |
711 | QVERIFY(belowOneEighth > PerfectOctile - RangeOctile); |
712 | } |
713 | |
714 | template <typename Engine> void seedStdRandomEngine() |
715 | { |
716 | { |
717 | QRandomGenerator &rd = *QRandomGenerator::system(); |
718 | Engine e(rd); |
719 | QVERIFY_3TIMES(e() != 0); |
720 | |
721 | e.seed(rd); |
722 | QVERIFY_3TIMES(e() != 0); |
723 | } |
724 | { |
725 | QRandomGenerator64 &rd = *QRandomGenerator64::system(); |
726 | Engine e(rd); |
727 | QVERIFY_3TIMES(e() != 0); |
728 | |
729 | e.seed(rd); |
730 | QVERIFY_3TIMES(e() != 0); |
731 | } |
732 | } |
733 | |
734 | void tst_QRandomGenerator::seedStdRandomEngines() |
735 | { |
736 | seedStdRandomEngine<std::default_random_engine>(); |
737 | seedStdRandomEngine<std::minstd_rand0>(); |
738 | seedStdRandomEngine<std::minstd_rand>(); |
739 | seedStdRandomEngine<std::mt19937>(); |
740 | seedStdRandomEngine<std::mt19937_64>(); |
741 | seedStdRandomEngine<std::ranlux24_base>(); |
742 | seedStdRandomEngine<std::ranlux48_base>(); |
743 | seedStdRandomEngine<std::ranlux24>(); |
744 | seedStdRandomEngine<std::ranlux48>(); |
745 | } |
746 | |
747 | void tst_QRandomGenerator::stdUniformIntDistribution_data() |
748 | { |
749 | #ifndef QT_BUILD_INTERNAL |
750 | QSKIP("Test only possible in developer builds" ); |
751 | #endif |
752 | |
753 | QTest::addColumn<uint>(name: "control" ); |
754 | QTest::addColumn<quint32>(name: "max" ); |
755 | |
756 | auto newRow = [&](quint32 max) { |
757 | #ifdef QT_BUILD_INTERNAL |
758 | if (qHasHwrng()) |
759 | QTest::addRow(format: "hwrng:%u" , max) << uint(UseSystemRNG) << max; |
760 | QTest::addRow(format: "system:%u" , max) << uint(UseSystemRNG | SkipHWRNG) << max; |
761 | # ifdef HAVE_FALLBACK_ENGINE |
762 | QTest::addRow("system-fallback:%u" , max) << uint(UseSystemRNG | SkipHWRNG | SkipSystemRNG) << max; |
763 | # endif |
764 | #endif |
765 | QTest::addRow(format: "global:%u" , max) << 0U << max; |
766 | }; |
767 | |
768 | // useless: we can only generate zeroes: |
769 | newRow(0); |
770 | |
771 | newRow(1); |
772 | newRow(199); |
773 | newRow(numeric_limits<quint32>::max()); |
774 | } |
775 | |
776 | void tst_QRandomGenerator::stdUniformIntDistribution() |
777 | { |
778 | QFETCH(uint, control); |
779 | QFETCH(quint32, max); |
780 | RandomGenerator rng(control); |
781 | |
782 | { |
783 | QRandomGenerator rd; |
784 | { |
785 | std::uniform_int_distribution<quint32> dist(0, max); |
786 | quint32 value = dist(rd); |
787 | QVERIFY(value >= dist.min()); |
788 | QVERIFY(value <= dist.max()); |
789 | } |
790 | if ((3 * max / 2) > max) { |
791 | std::uniform_int_distribution<quint32> dist(max / 2, 3 * max / 2); |
792 | quint32 value = dist(rd); |
793 | QVERIFY(value >= dist.min()); |
794 | QVERIFY(value <= dist.max()); |
795 | } |
796 | |
797 | { |
798 | std::uniform_int_distribution<quint64> dist(0, quint64(max) << 32); |
799 | quint64 value = dist(rd); |
800 | QVERIFY(value >= dist.min()); |
801 | QVERIFY(value <= dist.max()); |
802 | } |
803 | { |
804 | std::uniform_int_distribution<quint64> dist(max / 2, 3 * quint64(max) / 2); |
805 | quint64 value = dist(rd); |
806 | QVERIFY(value >= dist.min()); |
807 | QVERIFY(value <= dist.max()); |
808 | } |
809 | } |
810 | |
811 | { |
812 | QRandomGenerator64 rd; |
813 | { |
814 | std::uniform_int_distribution<quint32> dist(0, max); |
815 | quint32 value = dist(rd); |
816 | QVERIFY(value >= dist.min()); |
817 | QVERIFY(value <= dist.max()); |
818 | } |
819 | if ((3 * max / 2) > max) { |
820 | std::uniform_int_distribution<quint32> dist(max / 2, 3 * max / 2); |
821 | quint32 value = dist(rd); |
822 | QVERIFY(value >= dist.min()); |
823 | QVERIFY(value <= dist.max()); |
824 | } |
825 | |
826 | { |
827 | std::uniform_int_distribution<quint64> dist(0, quint64(max) << 32); |
828 | quint64 value = dist(rd); |
829 | QVERIFY(value >= dist.min()); |
830 | QVERIFY(value <= dist.max()); |
831 | } |
832 | { |
833 | std::uniform_int_distribution<quint64> dist(max / 2, 3 * quint64(max) / 2); |
834 | quint64 value = dist(rd); |
835 | QVERIFY(value >= dist.min()); |
836 | QVERIFY(value <= dist.max()); |
837 | } |
838 | } |
839 | } |
840 | |
841 | void tst_QRandomGenerator::stdGenerateCanonical() |
842 | { |
843 | QFETCH(uint, control); |
844 | RandomGenerator rng(control); |
845 | |
846 | for (int i = 0; i < 4; ++i) { |
847 | QVERIFY_3TIMES([&] { |
848 | qreal value = std::generate_canonical<qreal COMMA 32>(rng); |
849 | return value > 0 && value < 1 && value != RandomValueFP; |
850 | }()); |
851 | } |
852 | |
853 | // and should hopefully be different from repeated calls |
854 | for (int i = 0; i < 4; ++i) |
855 | QVERIFY_3TIMES(std::generate_canonical<qreal COMMA 32>(rng) != |
856 | std::generate_canonical<qreal COMMA 32>(rng)); |
857 | } |
858 | |
859 | void tst_QRandomGenerator::stdUniformRealDistribution_data() |
860 | { |
861 | #ifndef QT_BUILD_INTERNAL |
862 | QSKIP("Test only possible in developer builds" ); |
863 | #endif |
864 | |
865 | QTest::addColumn<uint>(name: "control" ); |
866 | QTest::addColumn<double>(name: "min" ); |
867 | QTest::addColumn<double>(name: "sup" ); |
868 | |
869 | auto newRow = [&](double min, double sup) { |
870 | #ifdef QT_BUILD_INTERNAL |
871 | if (qHasHwrng()) |
872 | QTest::addRow(format: "hwrng:%g-%g" , min, sup) << uint(UseSystemRNG) << min << sup; |
873 | QTest::addRow(format: "system:%g-%g" , min, sup) << uint(UseSystemRNG | SkipHWRNG) << min << sup; |
874 | # ifdef HAVE_FALLBACK_ENGINE |
875 | QTest::addRow("system-fallback:%g-%g" , min, sup) << uint(UseSystemRNG | SkipHWRNG | SkipSystemRNG) << min << sup; |
876 | # endif |
877 | #endif |
878 | QTest::addRow(format: "global:%g-%g" , min, sup) << 0U << min << sup; |
879 | }; |
880 | |
881 | newRow(0, 0); // useless: we can only generate zeroes |
882 | newRow(0, 1); // canonical |
883 | newRow(0, 200); |
884 | newRow(0, numeric_limits<quint32>::max() + 1.); |
885 | newRow(0, numeric_limits<quint64>::max() + 1.); |
886 | newRow(-1, 1.6); |
887 | } |
888 | |
889 | void tst_QRandomGenerator::stdUniformRealDistribution() |
890 | { |
891 | QFETCH(uint, control); |
892 | QFETCH(double, min); |
893 | QFETCH(double, sup); |
894 | RandomGenerator rng(control & (SkipHWRNG|SkipSystemRNG|UseSystemRNG)); |
895 | |
896 | { |
897 | QRandomGenerator rd; |
898 | { |
899 | std::uniform_real_distribution<double> dist(min, sup); |
900 | double value = dist(rd); |
901 | QVERIFY(value >= dist.min()); |
902 | if (min != sup) |
903 | QVERIFY(value < dist.max()); |
904 | } |
905 | } |
906 | |
907 | { |
908 | QRandomGenerator64 rd; |
909 | { |
910 | std::uniform_real_distribution<double> dist(min, sup); |
911 | double value = dist(rd); |
912 | QVERIFY(value >= dist.min()); |
913 | if (min != sup) |
914 | QVERIFY(value < dist.max()); |
915 | } |
916 | } |
917 | } |
918 | |
919 | template <typename Generator> void stdRandomDistributions_template() |
920 | { |
921 | Generator rd; |
922 | |
923 | std::bernoulli_distribution()(rd); |
924 | |
925 | std::binomial_distribution<quint32>()(rd); |
926 | std::binomial_distribution<quint64>()(rd); |
927 | |
928 | std::negative_binomial_distribution<quint32>()(rd); |
929 | std::negative_binomial_distribution<quint64>()(rd); |
930 | |
931 | std::poisson_distribution<int>()(rd); |
932 | std::poisson_distribution<qint64>()(rd); |
933 | |
934 | std::normal_distribution<qreal>()(rd); |
935 | |
936 | { |
937 | std::discrete_distribution<int> discrete{0, 1, 1, 10000, 2}; |
938 | QVERIFY(discrete(rd) != 0); |
939 | QVERIFY_3TIMES(discrete(rd) == 3); |
940 | } |
941 | } |
942 | |
943 | void tst_QRandomGenerator::stdRandomDistributions() |
944 | { |
945 | // just a compile check for some of the distributions, besides |
946 | // std::uniform_int_distribution and std::uniform_real_distribution (tested |
947 | // above) |
948 | |
949 | stdRandomDistributions_template<QRandomGenerator>(); |
950 | stdRandomDistributions_template<QRandomGenerator64>(); |
951 | } |
952 | |
953 | QTEST_APPLESS_MAIN(tst_QRandomGenerator) |
954 | |
955 | #include "tst_qrandomgenerator.moc" |
956 | |