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 <lars.knoll@qt.io>

3 files changed, 235 insertions, 8 deletions

diff --git a/src/corelib/global/qrandom.cpp b/src/corelib/global/qrandom.cpp
index 9a6e781b99..d12d8cd287 100644
--- a/src/corelib/global/qrandom.cpp
+++ b/src/corelib/global/qrandom.cpp
@@ -876,7 +876,8 @@ inline QRandomGenerator::SystemGenerator &QRandomGenerator::SystemGenerator::sel
     \a highest (exclusive). The same result may also be obtained by using
     \l{http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution}{\c std::uniform_int_distribution}
     with parameters 0 and \c{highest - 1}. That class can also be used to obtain
-    quantities larger than 32 bits.
+    quantities larger than 32 bits; for 64 bits, the 64-bit bounded() overload
+    can be used too.
 
     For example, to obtain a value between 0 and 255 (inclusive), one would write:
 
@@ -905,6 +906,45 @@ inline QRandomGenerator::SystemGenerator &QRandomGenerator::SystemGenerator::sel
  */
 
 /*!
+    \fn quint64 QRandomGenerator::bounded(quint64 highest)
+    \overload
+
+    Generates one random 64-bit quantity in the range between 0 (inclusive) and
+    \a highest (exclusive). The same result may also be obtained by using
+    \l{http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution}{\c std::uniform_int_distribution<quint64>}
+    with parameters 0 and \c{highest - 1}.
+
+    Note that this function cannot be used to obtain values in the full 64-bit
+    range of \c{quint64}. Instead, use generate64().
+
+    \note This function is implemented as a loop, which depends on the random
+    value obtained. On the long run, on average it should loop just under 2
+    times, but if the random generator is defective, this function may take
+    considerably longer to execute.
+
+    \sa generate(), generate64(), generateDouble()
+ */
+
+/*!
+    \fn qint64 QRandomGenerator::bounded(qint64 highest)
+    \overload
+
+    Generates one random 64-bit quantity in the range between 0 (inclusive) and
+    \a highest (exclusive). \a highest must be positive.
+
+    Note that this function cannot be used to obtain values in the full 64-bit
+    range of \c{qint64}. Instead, use generate64() and cast to qint64 or instead
+    use the unsigned version of this function.
+
+    \note This function is implemented as a loop, which depends on the random
+    value obtained. On the long run, on average it should loop just under 2
+    times, but if the random generator is defective, this function may take
+    considerably longer to execute.
+
+    \sa generate(), generate64(), generateDouble()
+ */
+
+/*!
     \fn quint32 QRandomGenerator::bounded(quint32 lowest, quint32 highest)
     \overload
 
@@ -943,6 +983,60 @@ inline QRandomGenerator::SystemGenerator &QRandomGenerator::SystemGenerator::sel
  */
 
 /*!
+    \fn quint64 QRandomGenerator::bounded(quint64 lowest, quint64 highest)
+    \overload
+
+    Generates one random 64-bit quantity in the range between \a lowest
+    (inclusive) and \a highest (exclusive). The \a highest parameter must be
+    greater than \a lowest.
+
+    The same result may also be obtained by using
+    \l{http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution}{\c std::uniform_int_distribution<quint64>}
+    with parameters \a lowest and \c{\a highest - 1}.
+
+    Note that this function cannot be used to obtain values in the full 64-bit
+    range of \c{quint64}. Instead, use generate64().
+
+    \note This function is implemented as a loop, which depends on the random
+    value obtained. On the long run, on average it should loop just under 2
+    times, but if the random generator is defective, this function may take
+    considerably longer to execute.
+
+    \sa generate(), generate64(), generateDouble()
+ */
+
+/*!
+    \fn qint64 QRandomGenerator::bounded(qint64 lowest, qint64 highest)
+    \overload
+
+    Generates one random 64-bit quantity in the range between \a lowest
+    (inclusive) and \a highest (exclusive), both of which may be negative, but
+    \a highest must be greater than \a lowest.
+
+    Note that this function cannot be used to obtain values in the full 64-bit
+    range of \c{qint64}. Instead, use generate64() and cast to qint64.
+
+    \note This function is implemented as a loop, which depends on the random
+    value obtained. On the long run, on average it should loop just under 2
+    times, but if the random generator is defective, this function may take
+    considerably longer to execute.
+
+    \sa generate(), generate64(), generateDouble()
+ */
+
+/*!
+    \fn qint64 QRandomGenerator::bounded(int lowest, qint64 highest)
+    \fn qint64 QRandomGenerator::bounded(qint64 lowest, int highest)
+    \fn quint64 QRandomGenerator::bounded(unsigned lowest, quint64 highest)
+    \fn quint64 QRandomGenerator::bounded(quint64 lowest, unsigned highest)
+    \overload
+
+    This function exists to help with overload resolution when the types of the
+    parameters don't exactly match. They will promote the smaller type to the
+    type of the larger one and call the correct overload.
+ */
+
+/*!
     \fn QRandomGenerator *QRandomGenerator::system()
     \threadsafe
 
diff --git a/src/corelib/global/qrandom.h b/src/corelib/global/qrandom.h
index 29cb24d1f5..d6b8bd742e 100644
--- a/src/corelib/global/qrandom.h
+++ b/src/corelib/global/qrandom.h
@@ -40,7 +40,7 @@
 #ifndef QRANDOM_H
 #define QRANDOM_H
 
-#include <QtCore/qglobal.h>
+#include <QtCore/qalgorithms.h>
 #include <algorithm>    // for std::generate
 #include <random>       // for std::mt19937
 
@@ -135,6 +135,44 @@ public:
         return bounded(highest - lowest) + lowest;
     }
 
+    quint64 bounded(quint64 highest);
+
+    quint64 bounded(quint64 lowest, quint64 highest)
+    {
+        Q_ASSERT(highest > lowest);
+        return bounded(highest - lowest) + lowest;
+    }
+
+    qint64 bounded(qint64 highest)
+    {
+        Q_ASSERT(highest > 0);
+        return qint64(bounded(quint64(0), quint64(highest)));
+    }
+
+    qint64 bounded(qint64 lowest, qint64 highest)
+    {
+        return bounded(highest - lowest) + lowest;
+    }
+
+    // these functions here only to help with ambiguous overloads
+    qint64 bounded(int lowest, qint64 highest)
+    {
+        return bounded(qint64(lowest), qint64(highest));
+    }
+    qint64 bounded(qint64 lowest, int highest)
+    {
+        return bounded(qint64(lowest), qint64(highest));
+    }
+
+    quint64 bounded(unsigned lowest, quint64 highest)
+    {
+        return bounded(quint64(lowest), quint64(highest));
+    }
+    quint64 bounded(quint64 lowest, unsigned highest)
+    {
+        return bounded(quint64(lowest), quint64(highest));
+    }
+
     template <typename UInt, IfValidUInt<UInt> = true>
     void fillRange(UInt *buffer, qsizetype count)
     {
@@ -249,6 +287,24 @@ public:
 #endif // Q_QDOC
 };
 
+inline quint64 QRandomGenerator::bounded(quint64 highest)
+{
+    // Implement an algorithm similar to libc++'s uniform_int_distribution:
+    // loop around getting a random number, mask off any bits that "highest"
+    // will never need, then check if it's higher than "highest". The number of
+    // times the loop will run is unbounded but the probability of terminating
+    // is better than 1/2 on each iteration. Therefore, the average loop count
+    // should be less than 2.
+
+    const int width = qCountLeadingZeroBits(highest - 1);
+    const quint64 mask = (quint64(1) << (std::numeric_limits<quint64>::digits - width)) - 1;
+    quint64 v;
+    do {
+        v = generate64() & mask;
+    } while (v >= highest);
+    return v;
+}
+
 inline QRandomGenerator *QRandomGenerator::system()
 {
     return QRandomGenerator64::system();
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 <typename UInt> static void boundedQuality_template()
 {
-    enum { Bound = 283 };       // a prime number
-    enum {
+    using Int = std::make_signed_t<UInt>;
+    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<quint32> buffer(BufferCount, 0xcdcdcdcd);
+        UInt filler = 0xcdcdcdcd;
+        if (sizeof(filler) > sizeof(quint32))
+            filler |= filler << (std::numeric_limits<UInt>::digits / 2);
+        QVector<UInt> 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<quint32>();
+}
+
+void tst_QRandomGenerator::bounded64Quality()
+{
+    boundedQuality_template<quint64>();
+}
+
+void tst_QRandomGenerator::bounded64_data()
+{
+#ifndef QT_BUILD_INTERNAL
+    QSKIP("Test only possible in developer builds");
+#endif
+
+    QTest::addColumn<uint>("control");
+    QTest::addColumn<quint64>("sup");
+    QTest::addColumn<quint64>("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);