include/QtCore/qrandom.h

0001 // Copyright (C) 2020 Intel Corporation.
0002 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0003
0004 #ifndef QRANDOM_H
0005 #define QRANDOM_H
0006
0007 #include <QtCore/qalgorithms.h>
0008 #include <algorithm>    // for std::generate
0009 #include <random>       // for std::mt19937
0010
0011 #ifdef min
0012 #  undef min
0013 #endif
0014 #ifdef max
0015 #  undef max
0016 #endif
0017
0018 QT_BEGIN_NAMESPACE
0019
0020 class QRandomGenerator
0021 {
0022     // restrict the template parameters to unsigned integers 32 bits wide or larger
0023     template <typename UInt> using IfValidUInt =
0024         typename std::enable_if<std::is_unsigned<UInt>::value && sizeof(UInt) >= sizeof(uint), bool>::type;
0025 public:
0026     QRandomGenerator(quint32 seedValue = 1)
0027         : QRandomGenerator(&seedValue, 1)
0028     {}
0029     template <qsizetype N> QRandomGenerator(const quint32 (&seedBuffer)[N])
0030         : QRandomGenerator(seedBuffer, seedBuffer + N)
0031     {}
0032     QRandomGenerator(const quint32 *seedBuffer, qsizetype len)
0033         : QRandomGenerator(seedBuffer, seedBuffer + len)
0034     {}
0035     Q_CORE_EXPORT QRandomGenerator(std::seed_seq &sseq) noexcept;
0036     Q_CORE_EXPORT QRandomGenerator(const quint32 *begin, const quint32 *end);
0037
0038     // copy constructor & assignment operator (move unnecessary)
0039     Q_CORE_EXPORT QRandomGenerator(const QRandomGenerator &other);
0040     Q_CORE_EXPORT QRandomGenerator &operator=(const QRandomGenerator &other);
0041
0042     ~QRandomGenerator() = default;
0043
0044     friend Q_CORE_EXPORT bool operator==(const QRandomGenerator &rng1, const QRandomGenerator &rng2);
0045     friend bool operator!=(const QRandomGenerator &rng1, const QRandomGenerator &rng2)
0046     {
0047         return !(rng1 == rng2);
0048     }
0049
0050     quint32 generate()
0051     {
0052         return quint32(_fillRange(nullptr, 1));
0053     }
0054
0055     quint64 generate64()
0056     {
0057         return _fillRange(nullptr, sizeof(quint64) / sizeof(quint32));
0058     }
0059
0060     double generateDouble()
0061     {
0062         // IEEE 754 double precision has:
0063         //   1 bit      sign
0064         //  10 bits     exponent
0065         //  53 bits     mantissa
0066         // In order for our result to be normalized in the range [0, 1), we
0067         // need exactly 53 bits of random data. Use generate64() to get enough.
0068         quint64 x = generate64();
0069         quint64 limit = Q_UINT64_C(1) << std::numeric_limits<double>::digits;
0070         x >>= std::numeric_limits<quint64>::digits - std::numeric_limits<double>::digits;
0071         return double(x) / double(limit);
0072     }
0073
0074     double bounded(double highest)
0075     {
0076         return generateDouble() * highest;
0077     }
0078
0079     quint32 bounded(quint32 highest)
0080     {
0081         quint64 value = generate();
0082         value *= highest;
0083         value /= (max)() + quint64(1);
0084         return quint32(value);
0085     }
0086
0087     quint32 bounded(quint32 lowest, quint32 highest)
0088     {
0089         Q_ASSERT(highest > lowest);
0090         return bounded(highest - lowest) + lowest;
0091     }
0092
0093     int bounded(int highest)
0094     {
0095         Q_ASSERT(highest > 0);
0096         return int(bounded(0U, quint32(highest)));
0097     }
0098
0099     int bounded(int lowest, int highest)
0100     {
0101         return bounded(highest - lowest) + lowest;
0102     }
0103
0104     quint64 bounded(quint64 highest);
0105
0106     quint64 bounded(quint64 lowest, quint64 highest)
0107     {
0108         Q_ASSERT(highest > lowest);
0109         return bounded(highest - lowest) + lowest;
0110     }
0111
0112     qint64 bounded(qint64 highest)
0113     {
0114         Q_ASSERT(highest > 0);
0115         return qint64(bounded(quint64(0), quint64(highest)));
0116     }
0117
0118     qint64 bounded(qint64 lowest, qint64 highest)
0119     {
0120         return bounded(highest - lowest) + lowest;
0121     }
0122
0123     // these functions here only to help with ambiguous overloads
0124     qint64 bounded(int lowest, qint64 highest)
0125     {
0126         return bounded(qint64(lowest), qint64(highest));
0127     }
0128     qint64 bounded(qint64 lowest, int highest)
0129     {
0130         return bounded(qint64(lowest), qint64(highest));
0131     }
0132
0133     quint64 bounded(unsigned lowest, quint64 highest)
0134     {
0135         return bounded(quint64(lowest), quint64(highest));
0136     }
0137     quint64 bounded(quint64 lowest, unsigned highest)
0138     {
0139         return bounded(quint64(lowest), quint64(highest));
0140     }
0141
0142     template <typename UInt, IfValidUInt<UInt> = true>
0143     void fillRange(UInt *buffer, qsizetype count)
0144     {
0145         _fillRange(buffer, count * sizeof(UInt) / sizeof(quint32));
0146     }
0147
0148     template <typename UInt, size_t N, IfValidUInt<UInt> = true>
0149     void fillRange(UInt (&buffer)[N])
0150     {
0151         _fillRange(buffer, N * sizeof(UInt) / sizeof(quint32));
0152     }
0153
0154     // API like std::seed_seq
0155     template <typename ForwardIterator>
0156     void generate(ForwardIterator begin, ForwardIterator end)
0157     {
0158         std::generate(begin, end, [this]() { return generate(); });
0159     }
0160
0161     void generate(quint32 *begin, quint32 *end)
0162     {
0163         _fillRange(begin, end - begin);
0164     }
0165
0166     // API like std:: random engines
0167     typedef quint32 result_type;
0168     result_type operator()() { return generate(); }
0169     void seed(quint32 s = 1) { *this = { s }; }
0170     void seed(std::seed_seq &sseq) noexcept { *this = { sseq }; }
0171     Q_CORE_EXPORT void discard(unsigned long long z);
0172     static constexpr result_type min() { return (std::numeric_limits<result_type>::min)(); }
0173     static constexpr result_type max() { return (std::numeric_limits<result_type>::max)(); }
0174
0175     static inline Q_DECL_CONST_FUNCTION QRandomGenerator *system();
0176     static inline Q_DECL_CONST_FUNCTION QRandomGenerator *global();
0177     static inline QRandomGenerator securelySeeded();
0178
0179 protected:
0180     enum System {};
0181     QRandomGenerator(System);
0182
0183 private:
0184     Q_CORE_EXPORT quint64 _fillRange(void *buffer, qptrdiff count);
0185
0186     struct InitialRandomData {
0187         quintptr data[16 / sizeof(quintptr)];
0188     };
0189     friend InitialRandomData qt_initial_random_value() noexcept;
0190     friend class QRandomGenerator64;
0191     struct SystemGenerator;
0192     struct SystemAndGlobalGenerators;
0193     using RandomEngine = std::mersenne_twister_engine<quint32,
0194         32,624,397,31,0x9908b0df,11,0xffffffff,7,0x9d2c5680,15,0xefc60000,18,1812433253>;
0195
0196     union Storage {
0197         uint dummy;
0198         RandomEngine twister;
0199         RandomEngine &engine() { return twister; }
0200         const RandomEngine &engine() const { return twister; }
0201
0202         static_assert(std::is_trivially_destructible<RandomEngine>::value,
0203                           "std::mersenne_twister not trivially destructible as expected");
0204         constexpr Storage();
0205     };
0206     uint type;
0207     Storage storage;
0208 };
0209
0210 class QRandomGenerator64 : public QRandomGenerator
0211 {
0212     QRandomGenerator64(System);
0213 public:
0214     // unshadow generate() overloads, since we'll override.
0215     using QRandomGenerator::generate;
0216     quint64 generate() { return generate64(); }
0217
0218     typedef quint64 result_type;
0219     result_type operator()() { return generate64(); }
0220
0221 #ifndef Q_QDOC
0222     QRandomGenerator64(quint32 seedValue = 1)
0223         : QRandomGenerator(seedValue)
0224     {}
0225     template <qsizetype N> QRandomGenerator64(const quint32 (&seedBuffer)[N])
0226         : QRandomGenerator(seedBuffer)
0227     {}
0228     QRandomGenerator64(const quint32 *seedBuffer, qsizetype len)
0229         : QRandomGenerator(seedBuffer, len)
0230     {}
0231     QRandomGenerator64(std::seed_seq &sseq) noexcept
0232         : QRandomGenerator(sseq)
0233     {}
0234     QRandomGenerator64(const quint32 *begin, const quint32 *end)
0235         : QRandomGenerator(begin, end)
0236     {}
0237     QRandomGenerator64(const QRandomGenerator &other) : QRandomGenerator(other) {}
0238
0239     void discard(unsigned long long z)
0240     {
0241         Q_ASSERT_X(z * 2 > z, "QRandomGenerator64::discard",
0242                    "Overflow. Are you sure you want to skip over 9 quintillion samples?");
0243         QRandomGenerator::discard(z * 2);
0244     }
0245
0246     static constexpr result_type min() { return (std::numeric_limits<result_type>::min)(); }
0247     static constexpr result_type max() { return (std::numeric_limits<result_type>::max)(); }
0248     static Q_DECL_CONST_FUNCTION Q_CORE_EXPORT QRandomGenerator64 *system();
0249     static Q_DECL_CONST_FUNCTION Q_CORE_EXPORT QRandomGenerator64 *global();
0250     static Q_CORE_EXPORT QRandomGenerator64 securelySeeded();
0251 #endif // Q_QDOC
0252 };
0253
0254 inline quint64 QRandomGenerator::bounded(quint64 highest)
0255 {
0256     // Implement an algorithm similar to libc++'s uniform_int_distribution:
0257     // loop around getting a random number, mask off any bits that "highest"
0258     // will never need, then check if it's higher than "highest". The number of
0259     // times the loop will run is unbounded but the probability of terminating
0260     // is better than 1/2 on each iteration. Therefore, the average loop count
0261     // should be less than 2.
0262
0263     const int width = qCountLeadingZeroBits(highest - 1);
0264     const quint64 mask = (quint64(1) << (std::numeric_limits<quint64>::digits - width)) - 1;
0265     quint64 v;
0266     do {
0267         v = generate64() & mask;
0268     } while (v >= highest);
0269     return v;
0270 }
0271
0272 inline QRandomGenerator *QRandomGenerator::system()
0273 {
0274     return QRandomGenerator64::system();
0275 }
0276
0277 inline QRandomGenerator *QRandomGenerator::global()
0278 {
0279     return QRandomGenerator64::global();
0280 }
0281
0282 QRandomGenerator QRandomGenerator::securelySeeded()
0283 {
0284     return QRandomGenerator64::securelySeeded();
0285 }
0286
0287 QT_END_NAMESPACE
0288
0289 #endif // QRANDOM_H