From 21d39168170c6833512c4a5f53985272741bd7e7 Mon Sep 17 00:00:00 2001 From: Thiago Macieira Date: Wed, 16 Sep 2020 17:01:03 -0700 Subject: QRandomGenerator: add 64-bit bounded() versions Unlike the 32-bit version, we can't go to a bigger integer type to do the multiplication with. So instead accept looping. Both libstdc++ and libc++ implement std::uniform_int_distribution this way anyway, but in a far more complex way. There is no looping if the "highest" is a power of two. The worst-case scenario is when "highest" is one past a power of two (like 65). In that case, we'll loop until the number is in range. Since all bits have equal probability of being zero or one, there's a 50-50 chance that the most significant useful bit will be set[*], in which case we'll need to loop and we again get the same probability. So on average, we only need two iterations to get an acceptable result. [*] There's also a possibility that the other bits are such that the number is still in range. For 65, we'd need the other 5 bits to be zero (64 is a valid result), but the probability of that is only 1/2^5 = 3.125%. The bigger "highest" is, the closer we get to zero, so approximate by saying that never happens and instead calculate that the most significant useful bit is the controlling one. [ChangeLog][QtCore][QRandomGenerator] Added 64-bit versions of the bounded() functions. They are useful in conjunction with Qt 6's 64-bit container sizes, so code that used to call bounded(list.size()) in Qt 5 will continue to compile and work in Qt 6. Fixes: QTBUG-86318 Change-Id: I3eb349b832c14610895efffd16356927fe78fd02 Reviewed-by: Lars Knoll --- .../qrandomgenerator/tst_qrandomgenerator.cpp | 89 ++++++++++++++++++++-- 1 file changed, 83 insertions(+), 6 deletions(-) (limited to 'tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp') diff --git a/tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp b/tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp index 0c453cd0e5..9f4abb367a 100644 --- a/tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp +++ b/tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp @@ -102,6 +102,10 @@ private slots: void bounded(); void boundedQuality_data() { generate32_data(); } void boundedQuality(); + void bounded64_data(); + void bounded64(); + void bounded64Quality_data() { generate32_data(); } + void bounded64Quality(); void generateReal_data() { generate32_data(); } void generateReal(); @@ -567,7 +571,7 @@ void tst_QRandomGenerator::bounded() QVERIFY(value < sup); QCOMPARE(value, expected); - int ivalue = rng.bounded(sup); + int ivalue = rng.bounded(int(sup)); QVERIFY(ivalue < int(sup)); QCOMPARE(ivalue, int(expected)); @@ -590,10 +594,11 @@ void tst_QRandomGenerator::bounded() QVERIFY(ivalue < 0); } -void tst_QRandomGenerator::boundedQuality() +template static void boundedQuality_template() { - enum { Bound = 283 }; // a prime number - enum { + using Int = std::make_signed_t; + constexpr Int Bound = 283; // a prime number + enum : Int { BufferCount = Bound * 32, // if the distribution were perfect, each byte in the buffer would @@ -625,10 +630,13 @@ void tst_QRandomGenerator::boundedQuality() { // test the quality of the generator - QList buffer(BufferCount, 0xcdcdcdcd); + UInt filler = 0xcdcdcdcd; + if (sizeof(filler) > sizeof(quint32)) + filler |= filler << (std::numeric_limits::digits / 2); + QVector buffer(BufferCount, filler); generate(buffer.begin(), buffer.end(), [&] { return rng.bounded(Bound); }); - for (quint32 value : qAsConst(buffer)) { + for (UInt value : qAsConst(buffer)) { QVERIFY(value < Bound); histogram[value]++; } @@ -649,6 +657,75 @@ void tst_QRandomGenerator::boundedQuality() << "at" << std::min_element(begin(histogram), end(histogram)) - histogram; } +void tst_QRandomGenerator::boundedQuality() +{ + boundedQuality_template(); +} + +void tst_QRandomGenerator::bounded64Quality() +{ + boundedQuality_template(); +} + +void tst_QRandomGenerator::bounded64_data() +{ +#ifndef QT_BUILD_INTERNAL + QSKIP("Test only possible in developer builds"); +#endif + + QTest::addColumn("control"); + QTest::addColumn("sup"); + QTest::addColumn("expected"); + + auto newRow = [&](unsigned val, unsigned sup) { + Q_ASSERT((val & ~RandomDataMask) == 0); + + unsigned control = SetRandomData | val; + QTest::addRow("%u,%u", val, sup) << control << quint64(sup) << quint64(val); + }; + + // useless: we can only generate zeroes: + newRow(0, 1); + + newRow(0x10, 200); + newRow(0x20, 200); + newRow(0x80, 200); +} + +void tst_QRandomGenerator::bounded64() +{ + QFETCH(uint, control); + QFETCH(quint64, sup); + QFETCH(quint64, expected); + RandomGenerator rng(control); + + quint64 value = rng.bounded(sup); + QVERIFY(value < sup); + QCOMPARE(value, expected); + + qint64 ivalue = rng.bounded(qint64(sup)); + QVERIFY(ivalue < int(sup)); + QCOMPARE(ivalue, int(expected)); + + // confirm only the bound now + setRNGControl(control & (SkipHWRNG|SkipSystemRNG|UseSystemRNG)); + value = rng.bounded(sup); + QVERIFY(value < sup); + + value = rng.bounded(sup / 2, 3 * sup / 2); + QVERIFY(value >= sup / 2); + QVERIFY(value < 3 * sup / 2); + + ivalue = rng.bounded(-qint64(sup), qint64(sup)); + QVERIFY(ivalue >= -qint64(sup)); + QVERIFY(ivalue < qint64(sup)); + + // wholly negative range + ivalue = rng.bounded(-qint64(sup), qint64(0)); + QVERIFY(ivalue >= -qint64(sup)); + QVERIFY(ivalue < 0); +} + void tst_QRandomGenerator::generateReal() { QFETCH(uint, control); -- cgit v1.2.3