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>

1 files changed, 57 insertions, 1 deletions

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();