diff options
author | Thiago Macieira <thiago.macieira@intel.com> | 2017-04-13 00:16:07 -0700 |
---|---|---|
committer | Thiago Macieira <thiago.macieira@intel.com> | 2017-06-12 06:14:34 +0000 |
commit | 593f022515da8a834b358b5a57779afff619b3e7 (patch) | |
tree | 1624efc58e91582e19f4f4f64686b067451cfeb9 | |
parent | 267edbec198a0cedbf7bed4c3c5fa93c1dbc86bd (diff) |
Long live QRandomGenerator
This class provides a reasonably-secure random number generator that
does not need seeding. That is quite unlike qrand(), which requires a
seed and is low-quality (definitely not secure).
This class is also like std::random_device, but better. It provides an
operator() like std::random_device, but unlike that, it also provides a
way to fill a buffer with random data, not just one 32-bit quantity.
It's also stateless.
Finally, it also implements std::seed_seq-like generate(). It obeys the
standard requirement of the range (32-bit) but not that of the algorithm
(if you wanted that, you'd use std::seed_seq itself). Instead,
generate() fills with pure random data.
Change-Id: Icd0e0d4b27cb4e5eb892fffd14b4e3ba9ea04da8
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
-rw-r--r-- | src/corelib/global/global.pri | 3 | ||||
-rw-r--r-- | src/corelib/global/qglobal.cpp | 10 | ||||
-rw-r--r-- | src/corelib/global/qrandom.cpp | 727 | ||||
-rw-r--r-- | src/corelib/global/qrandom.h | 154 | ||||
-rw-r--r-- | src/corelib/global/qrandom_p.h | 78 | ||||
-rw-r--r-- | tests/auto/corelib/global/global.pro | 1 | ||||
-rw-r--r-- | tests/auto/corelib/global/qrandomgenerator/qrandomgenerator.pro | 4 | ||||
-rw-r--r-- | tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp | 700 |
8 files changed, 1673 insertions, 4 deletions
diff --git a/src/corelib/global/global.pri b/src/corelib/global/global.pri index f162dd95dd..b95cdaa014 100644 --- a/src/corelib/global/global.pri +++ b/src/corelib/global/global.pri @@ -21,6 +21,8 @@ HEADERS += \ global/qisenum.h \ global/qtypetraits.h \ global/qflags.h \ + global/qrandom.h \ + global/qrandom_p.h \ global/qhooks_p.h \ global/qversiontagging.h @@ -34,6 +36,7 @@ SOURCES += \ global/qfloat16.cpp \ global/qoperatingsystemversion.cpp \ global/qlogging.cpp \ + global/qrandom.cpp \ global/qhooks.cpp VERSIONTAGGING_SOURCES = global/qversiontagging.cpp diff --git a/src/corelib/global/qglobal.cpp b/src/corelib/global/qglobal.cpp index c2c9ea4e67..a718689064 100644 --- a/src/corelib/global/qglobal.cpp +++ b/src/corelib/global/qglobal.cpp @@ -3502,7 +3502,7 @@ Q_GLOBAL_STATIC(AndroidRandomStorage, randomTLS) if two threads call qsrand(1) and subsequently call qrand(), the threads will get the same random number sequence. - \sa qrand() + \sa qrand(), QRandomGenerator */ void qsrand(uint seed) { @@ -3553,10 +3553,12 @@ void qsrand(uint seed) \c <stdlib.h>), the next number in the current sequence of pseudo-random integers. - Use \c qsrand() to initialize the pseudo-random number generator with - a seed value. + Use \c qsrand() to initialize the pseudo-random number generator with a + seed value. Seeding must be performed at least once on each thread. If that + step is skipped, then the sequence will be pre-seeded with a constant + value. - \sa qsrand() + \sa qsrand(), QRandomGenerator */ int qrand() { diff --git a/src/corelib/global/qrandom.cpp b/src/corelib/global/qrandom.cpp new file mode 100644 index 0000000000..74fdf9f318 --- /dev/null +++ b/src/corelib/global/qrandom.cpp @@ -0,0 +1,727 @@ +/**************************************************************************** +** +** Copyright (C) 2017 Intel Corporation. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +// for rand_s +#define _CRT_RAND_S + +#include "qrandom.h" +#include "qrandom_p.h" + +#if QT_HAS_INCLUDE(<random>) +# include <random> +#endif + +#ifdef Q_OS_UNIX +# include <fcntl.h> +# include <private/qcore_unix_p.h> +#else +# include <qt_windows.h> + +// RtlGenRandom is not exported by its name in advapi32.dll, but as SystemFunction036 +// See https://msdn.microsoft.com/en-us/library/windows/desktop/aa387694(v=vs.85).aspx +// Implementation inspired on https://hg.mozilla.org/mozilla-central/file/722fdbff1efc/security/nss/lib/freebl/win_rand.c#l146 +// Argument why this is safe to use: https://bugzilla.mozilla.org/show_bug.cgi?id=504270 +extern "C" { +DECLSPEC_IMPORT BOOLEAN WINAPI SystemFunction036(PVOID RandomBuffer, ULONG RandomBufferLength); +} +#endif + +QT_BEGIN_NAMESPACE + +namespace { +#ifdef Q_OS_UNIX +class SystemRandom +{ + static QBasicAtomicInt s_fdp1; // "file descriptor plus 1" + static int openDevice(); + SystemRandom() {} + ~SystemRandom(); +public: + enum { EfficientBufferFill = true }; + static qssize_t fillBuffer(void *buffer, qssize_t count); +}; +QBasicAtomicInt SystemRandom::s_fdp1 = Q_BASIC_ATOMIC_INITIALIZER(0); + +SystemRandom::~SystemRandom() +{ + int fd = s_fdp1.loadAcquire() - 1; + if (fd >= 0) + qt_safe_close(fd); +} + +int SystemRandom::openDevice() +{ + int fd = s_fdp1.loadAcquire() - 1; + if (fd != -1) + return fd; + + fd = qt_safe_open("/dev/urandom", O_RDONLY); + if (fd == -1) + fd = qt_safe_open("/dev/random", O_RDONLY | O_NONBLOCK); + if (fd == -1) { + // failed on both, set to -2 so we won't try again + fd = -2; + } + + int opened_fdp1; + if (s_fdp1.testAndSetOrdered(0, fd + 1, opened_fdp1)) { + if (fd >= 0) { + static const SystemRandom closer; + Q_UNUSED(closer); + } + return fd; + } + + // failed, another thread has opened the file descriptor + if (fd >= 0) + qt_safe_close(fd); + return opened_fdp1 - 1; +} + +qssize_t SystemRandom::fillBuffer(void *buffer, qssize_t count) +{ + int fd = openDevice(); + if (Q_UNLIKELY(fd < 0)) + return 0; + + qint64 n = qt_safe_read(fd, buffer, count); + return qMax<qssize_t>(n, 0); // ignore any errors +} +#endif // Q_OS_UNIX + +#if defined(Q_OS_WIN) && !defined(Q_OS_WINRT) +class SystemRandom +{ +public: + enum { EfficientBufferFill = true }; + static qssize_t fillBuffer(void *buffer, qssize_t count) + { + auto RtlGenRandom = SystemFunction036; + return RtlGenRandom(buffer, ULONG(count)) ? count: 0; + } +}; +#elif defined(Q_OS_WINRT) +class SystemRandom +{ +public: + enum { EfficientBufferFill = false }; + static qssize_t fillBuffer(void *, qssize_t) + { + // always use the fallback + return 0; + } +}; +#endif // Q_OS_WINRT +} // unnamed namespace + +#if defined(Q_OS_WIN) +static void fallback_update_seed(unsigned) {} +static void fallback_fill(quint32 *ptr, qssize_t left) Q_DECL_NOTHROW +{ + // on Windows, rand_s is a high-quality random number generator + // and it requires no seeding + std::generate(ptr, ptr + left, []() { + unsigned value; + rand_s(&value); + return value; + }); +} +#elif QT_HAS_INCLUDE(<chrono>) +static QBasicAtomicInteger<unsigned> seed = Q_BASIC_ATOMIC_INITIALIZER(0U); +static void fallback_update_seed(unsigned value) +{ + // Update the seed to be used for the fallback mechansim, if we need to. + // We can't use QtPrivate::QHashCombine here because that is not an atomic + // operation. A simple XOR will have to do then. + seed.fetchAndXorRelaxed(value); +} + +static void fallback_fill(quint32 *ptr, qssize_t left) Q_DECL_NOTHROW +{ + Q_ASSERT(left); + + // this is highly inefficient, we should save the generator across calls... + std::mt19937 generator(seed.load()); + std::generate(ptr, ptr + left, generator); + + fallback_update_seed(*ptr); +} +#else +static void fallback_update_seed(unsigned) {} +static Q_NORETURN void fallback_fill(quint32 *, qssize_t) +{ + qFatal("Random number generator failed and no high-quality backup available"); +} +#endif + +static void fill_internal(quint32 *buffer, qssize_t count) +{ + if (Q_UNLIKELY(uint(qt_randomdevice_control) & SetRandomData)) { + uint value = uint(qt_randomdevice_control) & RandomDataMask; + std::fill_n(buffer, count, value); + return; + } + + qssize_t filled = 0; + if (uint(qt_randomdevice_control) & SkipSystemRNG) == 0) { + qssize_t bytesFilled = + SystemRandom::fillBuffer(buffer + filled, (count - filled) * qssize_t(sizeof(*buffer))); + filled += bytesFilled / qssize_t(sizeof(*buffer)); + } + if (filled) + fallback_update_seed(*buffer); + + if (Q_UNLIKELY(filled != count)) { + // failed to fill the entire buffer, try the faillback mechanism + fallback_fill(buffer + filled, count - filled); + } +} + +static Q_NEVER_INLINE void fill(void *buffer, void *bufferEnd) +{ + struct ThreadState { + enum { + DesiredBufferByteSize = 32, + BufferCount = DesiredBufferByteSize / sizeof(quint32) + }; + quint32 buffer[BufferCount]; + int idx = BufferCount; + }; + + // Verify that the pointers are properly aligned for 32-bit + Q_ASSERT(quintptr(buffer) % sizeof(quint32) == 0); + Q_ASSERT(quintptr(bufferEnd) % sizeof(quint32) == 0); + + quint32 *ptr = reinterpret_cast<quint32 *>(buffer); + quint32 * const end = reinterpret_cast<quint32 *>(bufferEnd); + +#if defined(Q_COMPILER_THREAD_LOCAL) + if (SystemRandom::EfficientBufferFill && (end - ptr) < ThreadState::BufferCount + && uint(qt_randomdevice_control) == 0) { + thread_local ThreadState state; + qssize_t itemsAvailable = ThreadState::BufferCount - state.idx; + + // copy as much as we already have + qssize_t itemsToCopy = qMin(qssize_t(end - ptr), itemsAvailable); + memcpy(ptr, state.buffer + state.idx, size_t(itemsToCopy) * sizeof(*ptr)); + ptr += itemsToCopy; + + if (ptr != end) { + // refill the buffer and try again + fill_internal(state.buffer, ThreadState::BufferCount); + state.idx = 0; + + itemsToCopy = end - ptr; + memcpy(ptr, state.buffer + state.idx, size_t(itemsToCopy) * sizeof(*ptr)); + ptr = end; + } + + // erase what we copied and advance +# ifdef Q_OS_WIN + // Microsoft recommends this + SecureZeroMemory(state.buffer + state.idx, size_t(itemsToCopy) * sizeof(*ptr)); +# else + // We're quite confident the compiler will not optimize this out because + // we're writing to a thread-local buffer + memset(state.buffer + state.idx, 0, size_t(itemsToCopy) * sizeof(*ptr)); +# endif + state.idx += itemsToCopy; + } +#endif // Q_COMPILER_THREAD_LOCAL && !QT_BOOTSTRAPPED + + if (ptr != end) { + // fill directly in the user buffer + fill_internal(ptr, end - ptr); + } +} + +/** + \class QRandomGenerator + \inmodule QtCore + \since 5.10 + + \brief The QRandomGenerator class allows one to obtain random values from a + high-quality, seed-less Random Number Generator. + + QRandomGenerator may be used to generate random values from a high-quality + random number generator. Unlike qrand(), QRandomGenerator does not need to be + seeded. That also means it is not possible to force it to produce a + reliable sequence, which may be needed for debugging. + + The class can generate 32-bit or 64-bit quantities, or fill an array of + those. The most common way of generating new values is to call the get32(), + get64() or fillRange() functions. One would use it as: + + \code + quint32 value = QRandomGenerator::get32(); + \endcode + + Additionally, it provides a floating-point function getReal() that returns + a number in the range [0, 1) (that is, inclusive of zero and exclusive of + 1). There's also a set of convenience functions that facilitate obtaininga + random number in a bounded, integral range. + + \section1 Frequency and entropy exhaustion + + QRandomGenerator does not need to be seeded and instead uses operating system + or hardware facilities to generate random numbers. On some systems and with + certain hardware, those facilities are true Random Number Generators. + However, if they are true RNGs, those facilities have finite entropy source + and thus may fail to produce any results if the entropy pool is exhausted. + + If that happens, first the operating system then QRandomGenerator will fall + back to Pseudo Random Number Generators of decreasing qualities (Qt's + fallback generator being the simplest). Therefore, QRandomGenerator should + not be used for high-frequency random number generation, lest the entropy + pool become empty. As a rule of thumb, this class should not be called upon + to generate more than a kilobyte per second of random data (note: this may + vary from system to system). + + If an application needs true RNG data in bulk, it should use the operating + system facilities (such as \c{/dev/random} on Unix systems) directly and + wait for entropy to become available. If true RNG is not required, + applications should instead use a PRNG engines and can use QRandomGenerator to + seed those. + + \section1 Standard C++ Library compatibility + + QRandomGenerator is modeled after + \c{\l{http://en.cppreference.com/w/cpp/numeric/random/random_device}{std::random_device}} + and may be used in almost all contexts that the Standard Library can. + QRandomGenerator attempts to use either the same engine that backs + \c{std::random_device} or a better one. Note that \c{std::random_device} is + also allowed to fail if the source entropy pool becomes exhausted, in which + case it will throw an exception. QRandomGenerator never throws, but may abort + program execution instead. + + Like the Standard Library class, QRandomGenerator can be used to seed Standard + Library deterministic random engines from \c{<random>}, such as the + Mersenne Twister. Unlike \c{std::random_device}, QRandomGenerator also + implements the API of + \c{\l{http://en.cppreference.com/w/cpp/numeric/random/seed_seq}{std::seed_seq}}, + allowing it to seed the deterministic engines directly. + + The following code can be used to create and seed the + implementation-defined default deterministic PRNG, then use it to fill a + block range: + + \code + QRandomGenerator rd; + std::default_random_engine rng(rd); + std::generate(block.begin(), block.end(), rng); + + // equivalent to: + for (auto &v : block) + v = rng(); + \endcode + + QRandomGenerator is also compatible with the uniform distribution classes + \c{std::uniform_int_distribution} and \c{std:uniform_real_distribution}, as + well as the free function \c{std::generate_canonical}. For example, the + following code may be used to generate a floating-point number in the range + [1, 2.5): + + \code + QRandomGenerator64 rd; + std::uniform_real_distribution dist(1, 2.5); + return dist(rd); + \endcode + + Note the use of the QRandomGenerator64 class instead of QRandomGenerator to + obtain 64 bits of random data in a single call, though it is not required + to make the algorithm work (the Standard Library functions will make as + many calls as required to obtain enough bits of random data for the desired + range). + + \sa QRandomGenerator64, qrand() + */ + +/** + \fn QRandomGenerator::QRandomGenerator() + \internal + Defaulted constructor, does nothing. + */ + +/** + \typedef QRandomGenerator::result_type + + A typedef to the type that operator()() returns. That is, quint32. + + \sa operator()() + */ + +/** + \fn result_type QRandomGenerator::operator()() + + Generates a 32-bit random quantity and returns it. + + \sa QRandomGenerator::get32(), QRandomGenerator::get64() + */ + +/** + \fn double QRandomGenerator::entropy() const + + Returns the estimate of the entropy in the random generator source. + + This function exists to comply with the Standard Library requirements for + \c{\l{http://en.cppreference.com/w/cpp/numeric/random/random_device}{std::random_device}} + but it does not and cannot ever work. It is not possible to obtain a + reliable entropy value in a shared entropy pool in a multi-tasking system, + as other processes or threads may use that entropy. Any value non-zero + value that this function could return would be obsolete by the time the + user code reached it. + + Since QRandomGenerator attempts to use a hardware Random Number Generator, + this function always returns 0.0. + */ + +/** + \fn result_type QRandomGenerator::min() + + Returns the minimum value that QRandomGenerator may ever generate. That is, 0. + + \sa max(), QRandomGenerator64::max() + */ + +/** + \fn result_type QRandomGenerator::max() + + Returns the maximum value that QRandomGenerator may ever generate. That is, + \c {std::numeric_limits<result_type>::max()}. + + \sa min(), QRandomGenerator64::max() + */ + +/** + \fn void QRandomGenerator::generate(ForwardIterator begin, ForwardIterator end) + + Generates 32-bit quantities and stores them in the range between \a begin + and \a end. This function is equivalent to (and is implemented as): + + \code + std::generate(begin, end, []() { return get32(); }); + \endcode + + This function complies with the requirements for the function + \c{\l{http://en.cppreference.com/w/cpp/numeric/random/seed_seq/generate}{std::seed_seq::generate}}, + which requires unsigned 32-bit integer values. + + Note that if the [begin, end) range refers to an area that can store more + than 32 bits per element, the elements will still be initialized with only + 32 bits of data. Any other bits will be zero. To fill the range with 64 bit + quantities, one can write: + + \code + std::generate(begin, end, []() { return get64(); }); + \endcode + + If the range refers to contiguous memory (such as an array or the data from + a QVector), the fillRange() function may be used too. + + \sa fillRange() + */ + +/** + \fn void QRandomGenerator::generate(quint32 *begin, quint32 *end) + \overload + \internal + + Same as the other overload, but more efficiently fills \a begin to \a end. + */ + +/** + \fn void QRandomGenerator::fillRange(UInt *buffer, qssize_t count) + + Generates \a count 32- or 64-bit quantities (depending on the type \c UInt) + and stores them in the buffer pointed by \a buffer. This is the most + efficient way to obtain more than one quantity at a time, as it reduces the + number of calls into the Random Number Generator source. + + For example, to fill a vector of 16 entries with random values, one may + write: + + \code + QVector<quint32> vector; + vector.resize(16); + QRandomGenerator::fillRange(vector.data(), vector.size()); + \endcode + + \sa generate() + */ + +/** + \fn void QRandomGenerator::fillRange(UInt (&buffer)[N}) + + Generates \c N 32- or 64-bit quantities (depending on the type \c UInt) and + stores them in the \a buffer array. This is the most efficient way to + obtain more than one quantity at a time, as it reduces the number of calls + into the Random Number Generator source. + + For example, to fill generate two 32-bit quantities, one may write: + + \code + quint32 array[2]; + QRandomGenerator::fillRange(array); + \endcode + + It would have also been possible to make one call to get64() and then split + the two halves of the 64-bit value. + + \sa generate() + */ + +/** + \fn qreal QRandomGenerator::getReal() + + Generates one random qreal in the canonical range [0, 1) (that is, + inclusive of zero and exclusive of 1). + + This function is equivalent to: + \code + QRandomGenerator64 rd; + return std::generate_canonical<qreal, std::numeric_limits<qreal>::digits>(rd); + \endcode + + The same may also be obtained by using + \c{\l{http://en.cppreference.com/w/cpp/numeric/random/uniform_real_distribution}{std::uniform_real_distribution}} + with parameters 0 and 1. + + \sa get32(), get64(), bounded() + */ + +/** + \fn qreal QRandomGenerator::bounded(qreal sup) + + Generates one random qreal in the range between 0 (inclusive) and \a + sup (exclusive). This function is equivalent to and is implemented as: + + \code + return getReal() * sup; + \endcode + + \sa getReal(), bounded() + */ + +/** + \fn quint32 QRandomGenerator::bounded(quint32 sup) + \overload + + Generates one random 32-bit quantity in the range between 0 (inclusive) and + \a sup (exclusive). The same result may also be obtained by using + \c{\l{http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution}{std::uniform_int_distribution}} + with parameters 0 and \c{sup - 1}. That class can also be used to obtain + quantities larger than 32 bits. + + For example, to obtain a value between 0 and 255 (inclusive), one would write: + + \code + quint32 v = QRandomGenerator::bounded(256); + \endcode + + Naturally, the same could also be obtained by masking the result of get32() + to only the lower 8 bits. Either solution is as efficient. + + Note that this function cannot be used to obtain values in the full 32-bit + range of quint32. Instead, use get32(). + + \sa get32(), get64(), getReal() + */ + +/** + \fn quint32 QRandomGenerator::bounded(int sup) + \overload + + Generates one random 32-bit quantity in the range between 0 (inclusive) and + \a sup (exclusive). \a sup must not be negative. + + Note that this function cannot be used to obtain values in the full 32-bit + range of int. Instead, use get32() and cast to int. + + \sa get32(), get64(), getReal() + */ + +/** + \fn quint32 QRandomGenerator::bounded(quint32 min, quint32 sup) + \overload + + Generates one random 32-bit quantity in the range between \a min (inclusive) + and \a sup (exclusive). The same result may also be obtained by using + \c{\l{http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution}{std::uniform_int_distribution}} + with parameters \a min and \c{\a sup - 1}. That class can also be used to + obtain quantities larger than 32 bits. + + For example, to obtain a value between 1000 (incl.) and 2000 (excl.), one + would write: + + \code + quint32 v = QRandomGenerator::bounded(1000, 2000); + \endcode + + + Note that this function cannot be used to obtain values in the full 32-bit + range of quint32. Instead, use get32(). + + \sa get32(), get64(), getReal() + */ + +/** + \fn quint32 QRandomGenerator::bounded(int min, int sup) + \overload + + Generates one random 32-bit quantity in the range between \a min + (inclusive) and \a sup (exclusive), both of which may be negative. + + Note that this function cannot be used to obtain values in the full 32-bit + range of int. Instead, use get32() and cast to int. + + \sa get32(), get64(), getReal() + */ + +/** + \class QRandomGenerator64 + \inmodule QtCore + \since 5.10 + + \brief The QRandomGenerator64 class allows one to obtain 64-bit random values + from a high-quality, seed-less Random Number Generator. + + QRandomGenerator64 is a simple adaptor class around QRandomGenerator, making the + QRandomGenerator::get64() function the default for operator()(), instead of the + function that returns 32-bit quantities. This class is intended to be used + in conjunction with Standard Library algorithms that need 64-bit quantities + instead of 32-bit ones. + + In all other aspects, the class is the same. Please refer to + QRandomGenerator's documentation for more information. + + \sa QRandomGenerator +*/ + +/** + \fn QRandomGenerator64::QRandomGenerator64() + \internal + Defaulted constructor, does nothing. + */ + +/** + \typedef QRandomGenerator64::result_type + + A typedef to the type that operator()() returns. That is, quint64. + + \sa operator()() + */ + +/** + \fn result_type QRandomGenerator64::operator()() + + Generates a 64-bit random quantity and returns it. + + \sa QRandomGenerator::get32(), QRandomGenerator::get64() + */ + +/** + \fn double QRandomGenerator64::entropy() const + + Returns the estimate of the entropy in the random generator source. + + This function exists to comply with the Standard Library requirements for + \c{\l{http://en.cppreference.com/w/cpp/numeric/random/random_device}{std::random_device}} + but it does not and cannot ever work. It is not possible to obtain a + reliable entropy value in a shared entropy pool in a multi-tasking system, + as other processes or threads may use that entropy. Any value non-zero + value that this function could return would be obsolete by the time the + user code reached it. + + Since QRandomGenerator64 attempts to use a hardware Random Number Generator, + this function always returns 0.0. + */ + +/** + \fn result_type QRandomGenerator64::min() + + Returns the minimum value that QRandomGenerator64 may ever generate. That is, 0. + + \sa max(), QRandomGenerator::max() + */ + +/** + \fn result_type QRandomGenerator64::max() + + Returns the maximum value that QRandomGenerator64 may ever generate. That is, + \c {std::numeric_limits<result_type>::max()}. + + \sa min(), QRandomGenerator::max() + */ + +/** + Generates one 32-bit random value and returns it. + + \sa get64(), getReal() + */ +quint32 QRandomGenerator::get32() +{ + quint32 ret; + fill(&ret, &ret + 1); + return ret; +} + +/** + Generates one 64-bit random value and returns it. + + \sa get32(), getReal(), QRandomGenerator64 + */ +quint64 QRandomGenerator::get64() +{ + quint64 ret; + fill(&ret, &ret + 1); + return ret; +} + +/** + \internal + + Fills the range pointed by \a buffer and \a bufferEnd with 32-bit random + values. The buffer must be correctly aligned. + */ +void QRandomGenerator::fillRange_helper(void *buffer, void *bufferEnd) +{ + fill(buffer, bufferEnd); +} + +QT_END_NAMESPACE diff --git a/src/corelib/global/qrandom.h b/src/corelib/global/qrandom.h new file mode 100644 index 0000000000..3bede87fa6 --- /dev/null +++ b/src/corelib/global/qrandom.h @@ -0,0 +1,154 @@ +/**************************************************************************** +** +** Copyright (C) 2017 Intel Corporation. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QRANDOM_H +#define QRANDOM_H + +#include <QtCore/qglobal.h> +#include <algorithm> // for std::generate + +QT_BEGIN_NAMESPACE + +class QRandomGenerator +{ + // restrict the template parameters to unsigned integers 32 bits wide or larger + template <typename UInt> using IfValidUInt = + typename std::enable_if<std::is_unsigned<UInt>::value && sizeof(UInt) >= sizeof(uint), bool>::type; +public: + QRandomGenerator() = default; + + static Q_CORE_EXPORT quint32 get32(); + static Q_CORE_EXPORT quint64 get64(); + static qreal getReal() + { + const int digits = std::numeric_limits<qreal>::digits; + if (digits < std::numeric_limits<quint32>::digits) { + // use get32() + return qreal(get32()) / ((max)() + qreal(1.0)); + } else { + // use get64() + // we won't have enough bits for a __float128 though + return qreal(get64()) / ((std::numeric_limits<quint64>::max)() + qreal(1.0)); + } + } + + static qreal bounded(qreal sup) + { + return getReal() * sup; + } + + static quint32 bounded(quint32 sup) + { + quint64 value = get32(); + value *= sup; + value /= (max)() + quint64(1); + return quint32(value); + } + + static int bounded(int sup) + { + return int(bounded(quint32(sup))); + } + + static quint32 bounded(quint32 min, quint32 sup) + { + return bounded(sup - min) + min; + } + + static int bounded(int min, int sup) + { + return bounded(sup - min) + min; + } + + template <typename UInt, IfValidUInt<UInt> = true> + static void fillRange(UInt *buffer, qssize_t count) + { + fillRange_helper(buffer, buffer + count); + } + + template <typename UInt, size_t N, IfValidUInt<UInt> = true> + static void fillRange(UInt (&buffer)[N]) + { + fillRange_helper(buffer, buffer + N); + } + + // API like std::seed_seq + template <typename ForwardIterator> + void generate(ForwardIterator begin, ForwardIterator end) + { + std::generate(begin, end, &QRandomGenerator::get32); + } + + void generate(quint32 *begin, quint32 *end) + { + fillRange_helper(begin, end); + } + + // API like std::random_device + typedef quint32 result_type; + result_type operator()() { return get32(); } + double entropy() const Q_DECL_NOTHROW { return 0.0; } + static Q_DECL_CONSTEXPR result_type min() { return (std::numeric_limits<result_type>::min)(); } + static Q_DECL_CONSTEXPR result_type max() { return (std::numeric_limits<result_type>::max)(); } + +private: + Q_DISABLE_COPY(QRandomGenerator) + static Q_CORE_EXPORT void fillRange_helper(void *buffer, void *bufferEnd); +}; + +class QRandomGenerator64 +{ +public: + QRandomGenerator64() = default; + + // API like std::random_device + typedef quint64 result_type; + result_type operator()() { return QRandomGenerator::get64(); } + double entropy() const Q_DECL_NOTHROW { return 0.0; } + static Q_DECL_CONSTEXPR result_type min() { return (std::numeric_limits<result_type>::min)(); } + static Q_DECL_CONSTEXPR result_type max() { return (std::numeric_limits<result_type>::max)(); } + +private: + Q_DISABLE_COPY(QRandomGenerator64) +}; + + +QT_END_NAMESPACE + +#endif // QRANDOM_H diff --git a/src/corelib/global/qrandom_p.h b/src/corelib/global/qrandom_p.h new file mode 100644 index 0000000000..6ac2904e1b --- /dev/null +++ b/src/corelib/global/qrandom_p.h @@ -0,0 +1,78 @@ +/**************************************************************************** +** +** Copyright (C) 2017 Intel Corporation. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QRANDOM_P_H +#define QRANDOM_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include "qglobal_p.h" + +QT_BEGIN_NAMESPACE + +enum QRandomGeneratorControl { + SkipMemfill = 1, + SkipSystemRNG = 2, + SkipHWRNG = 4, + SetRandomData = 8, + + // 28 bits + RandomDataMask = 0xfffffff0 +}; + +#if defined(QT_BUILD_INTERNAL) && defined(QT_BUILD_CORE_LIB) +Q_CORE_EXPORT QBasicAtomicInteger<uint> qt_randomdevice_control = Q_BASIC_ATOMIC_INITIALIZER(0U); +#elif defined(QT_BUILD_INTERNAL) +extern Q_CORE_EXPORT QBasicAtomicInteger<uint> qt_randomdevice_control; +#else +enum { qt_randomdevice_control = 0 }; +#endif + +QT_END_NAMESPACE + +#endif // QRANDOM_P_H diff --git a/tests/auto/corelib/global/global.pro b/tests/auto/corelib/global/global.pro index b4cc8035e6..139e073644 100644 --- a/tests/auto/corelib/global/global.pro +++ b/tests/auto/corelib/global/global.pro @@ -7,6 +7,7 @@ SUBDIRS=\ qnumeric \ qfloat16 \ qrand \ + qrandomgenerator \ qlogging \ qtendian \ qglobalstatic \ diff --git a/tests/auto/corelib/global/qrandomgenerator/qrandomgenerator.pro b/tests/auto/corelib/global/qrandomgenerator/qrandomgenerator.pro new file mode 100644 index 0000000000..0307b0c1eb --- /dev/null +++ b/tests/auto/corelib/global/qrandomgenerator/qrandomgenerator.pro @@ -0,0 +1,4 @@ +CONFIG += testcase +TARGET = tst_qrandomgenerator +QT = core-private testlib +SOURCES = tst_qrandomgenerator.cpp diff --git a/tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp b/tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp new file mode 100644 index 0000000000..1909f4879f --- /dev/null +++ b/tests/auto/corelib/global/qrandomgenerator/tst_qrandomgenerator.cpp @@ -0,0 +1,700 @@ +/**************************************************************************** +** +** Copyright (C) 2017 Intel Corporation. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the test suite of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:GPL-EXCEPT$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3 as published by the Free Software +** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include <QtTest> +#include <qlinkedlist.h> +#include <qobject.h> +#include <qrandom.h> +#include <qvector.h> +#include <private/qrandom_p.h> + +#include <algorithm> +#if QT_HAS_INCLUDE(<random>) +# include <random> +#endif + +#if QT_HAS_INCLUDE(<random>) || defined(Q_OS_WIN) +# define HAVE_FALLBACK_ENGINE +#endif + +#define COMMA , +#define QVERIFY_3TIMES(statement) \ + do {\ + if (!QTest::qVerify(static_cast<bool>(statement), #statement, "1st try", __FILE__, __LINE__))\ + if (!QTest::qVerify(static_cast<bool>(statement), #statement, "2nd try", __FILE__, __LINE__))\ + if (!QTest::qVerify(static_cast<bool>(statement), #statement, "3rd try", __FILE__, __LINE__))\ + return;\ + } while (0) + +// values chosen at random +static const quint32 RandomValue32 = 0x4d1169f1U; +static const quint64 RandomValue64 = Q_UINT64_C(0x3ce63161b998aa91); +static const double RandomValueFP = double(0.3010463714599609f); + +static void setRNGControl(uint v) +{ +#ifdef QT_BUILD_INTERNAL + qt_randomdevice_control.store(v); +#else + Q_UNUSED(v); +#endif +} + +class tst_QRandomGenerator : public QObject +{ + Q_OBJECT + +public slots: + void cleanup() { setRNGControl(0); } + +private slots: + void get32_data(); + void get32(); + void get64_data() { get32_data(); } + void get64(); + void quality_data() { get32_data(); } + void quality(); + void fillRangeUInt_data() { get32_data(); } + void fillRangeUInt(); + void fillRangeULong_data() { get32_data(); } + void fillRangeULong(); + void fillRangeULLong_data() { get32_data(); } + void fillRangeULLong(); + void generateUInt_data() { get32_data(); } + void generateUInt(); + void generateULLong_data() { get32_data(); } + void generateULLong(); + void generateNonContiguous_data() { get32_data(); } + void generateNonContiguous(); + + void bounded_data(); + void bounded(); + void boundedQuality_data() { get32_data(); } + void boundedQuality(); + + void getReal_data() { get32_data(); } + void getReal(); + + void seedStdRandomEngines(); + void stdUniformIntDistribution_data(); + void stdUniformIntDistribution(); + void stdGenerateCanonical_data() { getReal_data(); } + void stdGenerateCanonical(); + void stdUniformRealDistribution_data(); + void stdUniformRealDistribution(); + void stdRandomDistributions(); +}; + +using namespace std; +QT_WARNING_DISABLE_GCC("-Wfloat-equal") +QT_WARNING_DISABLE_CLANG("-Wfloat-equal") + +void tst_QRandomGenerator::get32_data() +{ + QTest::addColumn<uint>("control"); + QTest::newRow("default") << 0U; +#ifdef QT_BUILD_INTERNAL + QTest::newRow("direct") << uint(SkipMemfill); + QTest::newRow("system") << uint(SkipHWRNG); +# ifdef HAVE_FALLBACK_ENGINE + QTest::newRow("fallback") << uint(SkipHWRNG | SkipSystemRNG); +# endif +#endif +} + +void tst_QRandomGenerator::get32() +{ + QFETCH(uint, control); + setRNGControl(control); + + for (int i = 0; i < 4; ++i) { + QVERIFY_3TIMES([] { + quint32 value = QRandomGenerator::get32(); + return value != 0 && value != RandomValue32; + }()); + } + + // and should hopefully be different from repeated calls + for (int i = 0; i < 4; ++i) + QVERIFY_3TIMES(QRandomGenerator::get32() != QRandomGenerator::get32()); +} + +void tst_QRandomGenerator::get64() +{ + QFETCH(uint, control); + setRNGControl(control); + + for (int i = 0; i < 4; ++i) { + QVERIFY_3TIMES([] { + quint64 value = QRandomGenerator::get32(); + return value != 0 && value != RandomValue32 && value != RandomValue64; + }()); + } + + // and should hopefully be different from repeated calls + for (int i = 0; i < 4; ++i) + QVERIFY_3TIMES(QRandomGenerator::get64() != QRandomGenerator::get64()); + for (int i = 0; i < 4; ++i) + QVERIFY_3TIMES(QRandomGenerator::get32() != quint32(QRandomGenerator::get64())); + for (int i = 0; i < 4; ++i) + QVERIFY_3TIMES(QRandomGenerator::get32() != (QRandomGenerator::get64() >> 32)); +} + +void tst_QRandomGenerator::quality() +{ + enum { + BufferSize = 2048, + BufferCount = BufferSize / sizeof(quint32), + + // if the distribution were perfect, each byte in the buffer would + // appear exactly: + PerfectDistribution = BufferSize / (UCHAR_MAX + 1), + + // The chance of a value appearing N times above its perfect + // distribution is the same as it appearing N times in a row: + // N Probability + // 1 100% + // 2 0.390625% + // 3 15.25 in a million + // 4 59.60 in a billion + // 8 5.421e-20 + // 16 2.938e-39 + + AcceptableThreshold = 4 * PerfectDistribution, + FailureThreshold = 16 * PerfectDistribution + }; + Q_STATIC_ASSERT(FailureThreshold > AcceptableThreshold); + + QFETCH(uint, control); + setRNGControl(control); + + int histogram[UCHAR_MAX + 1]; + memset(histogram, 0, sizeof(histogram)); + + { + // test the quality of the generator + quint32 buffer[BufferCount]; + memset(buffer, 0xcc, sizeof(buffer)); + generate_n(buffer, +BufferCount, [] { return QRandomGenerator::get32(); }); + + quint8 *ptr = reinterpret_cast<quint8 *>(buffer); + quint8 *end = ptr + sizeof(buffer); + for ( ; ptr != end; ++ptr) + histogram[*ptr]++; + } + + for (uint i = 0; i < sizeof(histogram)/sizeof(histogram[0]); ++i) { + int v = histogram[i]; + if (v > AcceptableThreshold) + qDebug() << i << "above threshold:" << v; + QVERIFY2(v < FailureThreshold, QByteArray::number(i)); + } + qDebug() << "Average:" << (std::accumulate(begin(histogram), end(histogram), 0) / (1. * (UCHAR_MAX + 1))) + << "(expected" << int(PerfectDistribution) << "ideally)" + << "Max:" << *std::max_element(begin(histogram), end(histogram)) + << "at" << std::max_element(begin(histogram), end(histogram)) - histogram + << "Min:" << *std::min_element(begin(histogram), end(histogram)) + << "at" << std::min_element(begin(histogram), end(histogram)) - histogram; +} + +template <typename T> void fillRange_template() +{ + QFETCH(uint, control); + setRNGControl(control); + + for (int i = 0; i < 4; ++i) { + QVERIFY_3TIMES([] { + T value[1] = { RandomValue32 }; + QRandomGenerator::fillRange(value); + return value[0] != 0 && value[0] != RandomValue32; + }()); + } + + for (int i = 0; i < 4; ++i) { + QVERIFY_3TIMES([] { + T array[2] = {}; + QRandomGenerator::fillRange(array); + return array[0] != array[1]; + }()); + } + + if (sizeof(T) > sizeof(quint32)) { + // just to shut up a warning about shifting uint more than the width + enum { Shift = sizeof(T) / 2 * CHAR_BIT }; + QVERIFY_3TIMES([] { + T value[1] = { }; + QRandomGenerator::fillRange(value); + return quint32(value[0] >> Shift) != quint32(value[0]); + }()); + } + + // fill in a longer range + auto longerArrayCheck = [] { + T array[32]; + memset(array, 0, sizeof(array)); + QRandomGenerator::fillRange(array); + if (sizeof(T) == sizeof(RandomValue64) + && find(begin(array), end(array), RandomValue64) != end(array)) + return false; + return find(begin(array), end(array), 0) == end(array) && + find(begin(array), end(array), RandomValue32) == end(array); + }; + QVERIFY_3TIMES(longerArrayCheck()); +} + +void tst_QRandomGenerator::fillRangeUInt() { fillRange_template<uint>(); } +void tst_QRandomGenerator::fillRangeULong() { fillRange_template<ulong>(); } +void tst_QRandomGenerator::fillRangeULLong() { fillRange_template<qulonglong>(); } + +template <typename T> void generate_template() +{ + QFETCH(uint, control); + setRNGControl(control); + + // almost the same as fillRange, but limited to 32 bits + for (int i = 0; i < 4; ++i) { + QVERIFY_3TIMES([] { + T value[1] = { RandomValue32 }; + QRandomGenerator().generate(begin(value), end(value)); + return value[0] != 0 && value[0] != RandomValue32 + && value[0] <= numeric_limits<quint32>::max(); + }()); + } + + // fill in a longer range + auto longerArrayCheck = [] { + T array[32] = {}; + QRandomGenerator().generate(begin(array), end(array)); + return find_if(begin(array), end(array), [](T cur) { + return cur == 0 || cur == RandomValue32 || + cur == RandomValue64 || cur > numeric_limits<quint32>::max(); + }) == end(array); + }; + QVERIFY_3TIMES(longerArrayCheck()); +} + +void tst_QRandomGenerator::generateUInt() { generate_template<uint>(); } +void tst_QRandomGenerator::generateULLong() { generate_template<qulonglong>(); } + +void tst_QRandomGenerator::generateNonContiguous() +{ + QFETCH(uint, control); + setRNGControl(control); + + QLinkedList<quint64> list = { 0, 0, 0, 0, 0, 0, 0, 0 }; + auto longerArrayCheck = [&] { + QRandomGenerator().generate(list.begin(), list.end()); + return find_if(list.begin(), list.end(), [](quint64 cur) { + return cur == 0 || cur == RandomValue32 || + cur == RandomValue64 || cur > numeric_limits<quint32>::max(); + }) == list.end(); + }; + QVERIFY_3TIMES(longerArrayCheck()); +} + +void tst_QRandomGenerator::bounded_data() +{ +#ifndef QT_BUILD_INTERNAL + QSKIP("Test only possible in developer builds"); +#endif + + QTest::addColumn<uint>("control"); + QTest::addColumn<quint32>("sup"); + QTest::addColumn<quint32>("expected"); + + auto newRow = [](quint32 val, quint32 sup) { + // calculate the scaled value + quint64 scaled = val; + scaled <<= 32; + scaled /= sup; + unsigned shifted = unsigned(scaled); + Q_ASSERT(val < sup); + Q_ASSERT((shifted & RandomDataMask) == shifted); + + unsigned control = SetRandomData | shifted; + QTest::addRow("%u,%u", val, sup) << control << sup << val; + }; + + // useless: we can only generate zeroes: + newRow(0, 1); + + newRow(25, 200); + newRow(50, 200); + newRow(75, 200); +} + +void tst_QRandomGenerator::bounded() +{ + QFETCH(uint, control); + QFETCH(quint32, sup); + QFETCH(quint32, expected); + setRNGControl(control); + + quint32 value = QRandomGenerator::bounded(sup); + QVERIFY(value < sup); + QCOMPARE(value, expected); + + int ivalue = QRandomGenerator::bounded(sup); + QVERIFY(ivalue < int(sup)); + QCOMPARE(ivalue, int(expected)); + + // confirm only the bound now + setRNGControl(control & (SkipHWRNG|SkipSystemRNG|SkipMemfill)); + value = QRandomGenerator::bounded(sup); + QVERIFY(value < sup); + + value = QRandomGenerator::bounded(sup / 2, 3 * sup / 2); + QVERIFY(value >= sup / 2); + QVERIFY(value < 3 * sup / 2); + + ivalue = QRandomGenerator::bounded(-int(sup), int(sup)); + QVERIFY(ivalue >= -int(sup)); + QVERIFY(ivalue < int(sup)); + + // wholly negative range + ivalue = QRandomGenerator::bounded(-int(sup), 0); + QVERIFY(ivalue >= -int(sup)); + QVERIFY(ivalue < 0); +} + +void tst_QRandomGenerator::boundedQuality() +{ + enum { Bound = 283 }; // a prime number + enum { + BufferCount = Bound * 32, + + // if the distribution were perfect, each byte in the buffer would + // appear exactly: + PerfectDistribution = BufferCount / Bound, + + // The chance of a value appearing N times above its perfect + // distribution is the same as it appearing N times in a row: + // N Probability + // 1 100% + // 2 0.390625% + // 3 15.25 in a million + // 4 59.60 in a billion + // 8 5.421e-20 + // 16 2.938e-39 + + AcceptableThreshold = 4 * PerfectDistribution, + FailureThreshold = 16 * PerfectDistribution + }; + Q_STATIC_ASSERT(FailureThreshold > AcceptableThreshold); + + QFETCH(uint, control); + setRNGControl(control); + + int histogram[Bound]; + memset(histogram, 0, sizeof(histogram)); + + { + // test the quality of the generator + QVector<quint32> buffer(BufferCount, 0xcdcdcdcd); + generate(buffer.begin(), buffer.end(), [] { return QRandomGenerator::bounded(Bound); }); + + for (quint32 value : qAsConst(buffer)) { + QVERIFY(value < Bound); + histogram[value]++; + } + } + + for (unsigned i = 0; i < sizeof(histogram)/sizeof(histogram[0]); ++i) { + int v = histogram[i]; + if (v > AcceptableThreshold) + qDebug() << i << "above threshold:" << v; + QVERIFY2(v < FailureThreshold, QByteArray::number(i)); + } + + qDebug() << "Average:" << (std::accumulate(begin(histogram), end(histogram), 0) / qreal(Bound)) + << "(expected" << int(PerfectDistribution) << "ideally)" + << "Max:" << *std::max_element(begin(histogram), end(histogram)) + << "at" << std::max_element(begin(histogram), end(histogram)) - histogram + << "Min:" << *std::min_element(begin(histogram), end(histogram)) + << "at" << std::min_element(begin(histogram), end(histogram)) - histogram; +} + +void tst_QRandomGenerator::getReal() +{ + QFETCH(uint, control); + setRNGControl(control); + + for (int i = 0; i < 4; ++i) { + QVERIFY_3TIMES([] { + qreal value = QRandomGenerator::getReal(); + return value > 0 && value < 1 && value != RandomValueFP; + }()); + } + + // and should hopefully be different from repeated calls + for (int i = 0; i < 4; ++i) + QVERIFY_3TIMES(QRandomGenerator::getReal() != QRandomGenerator::getReal()); +} + +template <typename Engine> void seedStdRandomEngine() +{ + QRandomGenerator rd; + Engine e(rd); + QVERIFY_3TIMES(e() != 0); + + e.seed(rd); + QVERIFY_3TIMES(e() != 0); +} + +void tst_QRandomGenerator::seedStdRandomEngines() +{ +#if !QT_HAS_INCLUDE(<random>) + QSKIP("<random> not found"); +#else + seedStdRandomEngine<std::default_random_engine>(); + seedStdRandomEngine<std::minstd_rand0>(); + seedStdRandomEngine<std::minstd_rand>(); + seedStdRandomEngine<std::mt19937>(); + seedStdRandomEngine<std::mt19937_64>(); + seedStdRandomEngine<std::ranlux24_base>(); + seedStdRandomEngine<std::ranlux48_base>(); + seedStdRandomEngine<std::ranlux24>(); + seedStdRandomEngine<std::ranlux48>(); +#endif +} + +void tst_QRandomGenerator::stdUniformIntDistribution_data() +{ +#ifndef QT_BUILD_INTERNAL + QSKIP("Test only possible in developer builds"); +#endif + + QTest::addColumn<uint>("control"); + QTest::addColumn<quint32>("max"); + + auto newRow = [](quint32 max) { + QTest::addRow("default:%u", max) << 0U << max; + QTest::addRow("direct:%u", max) << uint(SkipMemfill) << max; + QTest::addRow("system:%u", max) << uint(SkipHWRNG) << max; + #ifdef HAVE_FALLBACK_ENGINE + QTest::addRow("fallback:%u", max) << uint(SkipHWRNG | SkipSystemRNG) << max; + #endif + }; + + // useless: we can only generate zeroes: + newRow(0); + + newRow(1); + newRow(199); + newRow(numeric_limits<quint32>::max()); +} + +void tst_QRandomGenerator::stdUniformIntDistribution() +{ +#if !QT_HAS_INCLUDE(<random>) + QSKIP("<random> not found"); +#else + QFETCH(uint, control); + QFETCH(quint32, max); + setRNGControl(control & (SkipHWRNG|SkipSystemRNG|SkipMemfill)); + + { + QRandomGenerator rd; + { + std::uniform_int_distribution<quint32> dist(0, max); + quint32 value = dist(rd); + QVERIFY(value >= dist.min()); + QVERIFY(value <= dist.max()); + } + if ((3 * max / 2) > max) { + std::uniform_int_distribution<quint32> dist(max / 2, 3 * max / 2); + quint32 value = dist(rd); + QVERIFY(value >= dist.min()); + QVERIFY(value <= dist.max()); + } + + { + std::uniform_int_distribution<quint64> dist(0, quint64(max) << 32); + quint64 value = dist(rd); + QVERIFY(value >= dist.min()); + QVERIFY(value <= dist.max()); + } + { + std::uniform_int_distribution<quint64> dist(max / 2, 3 * quint64(max) / 2); + quint64 value = dist(rd); + QVERIFY(value >= dist.min()); + QVERIFY(value <= dist.max()); + } + } + + { + QRandomGenerator64 rd; + { + std::uniform_int_distribution<quint32> dist(0, max); + quint32 value = dist(rd); + QVERIFY(value >= dist.min()); + QVERIFY(value <= dist.max()); + } + if ((3 * max / 2) > max) { + std::uniform_int_distribution<quint32> dist(max / 2, 3 * max / 2); + quint32 value = dist(rd); + QVERIFY(value >= dist.min()); + QVERIFY(value <= dist.max()); + } + + { + std::uniform_int_distribution<quint64> dist(0, quint64(max) << 32); + quint64 value = dist(rd); + QVERIFY(value >= dist.min()); + QVERIFY(value <= dist.max()); + } + { + std::uniform_int_distribution<quint64> dist(max / 2, 3 * quint64(max) / 2); + quint64 value = dist(rd); + QVERIFY(value >= dist.min()); + QVERIFY(value <= dist.max()); + } + } +#endif +} + +void tst_QRandomGenerator::stdGenerateCanonical() +{ +#if !QT_HAS_INCLUDE(<random>) + QSKIP("<random> not found"); +#else + QFETCH(uint, control); + setRNGControl(control); + + for (int i = 0; i < 4; ++i) { + QVERIFY_3TIMES([] { + QRandomGenerator rd; + qreal value = std::generate_canonical<qreal COMMA 32>(rd); + return value > 0 && value < 1 && value != RandomValueFP; + }()); + } + + // and should hopefully be different from repeated calls + QRandomGenerator rd; + for (int i = 0; i < 4; ++i) + QVERIFY_3TIMES(std::generate_canonical<qreal COMMA 32>(rd) != + std::generate_canonical<qreal COMMA 32>(rd)); +#endif +} + +void tst_QRandomGenerator::stdUniformRealDistribution_data() +{ +#ifndef QT_BUILD_INTERNAL + QSKIP("Test only possible in developer builds"); +#endif + + QTest::addColumn<uint>("control"); + QTest::addColumn<double>("min"); + QTest::addColumn<double>("sup"); + + auto newRow = [](double min, double sup) { + QTest::addRow("default:%g-%g", min, sup) << 0U << min << sup; + QTest::addRow("direct:%g-%g", min, sup) << uint(SkipMemfill) << min << sup; + QTest::addRow("system:%g-%g", min, sup) << uint(SkipHWRNG) << min << sup; + #ifdef HAVE_FALLBACK_ENGINE + QTest::addRow("fallback:%g-%g", min, sup) << uint(SkipHWRNG | SkipSystemRNG) << min << sup; + #endif + }; + + newRow(0, 0); // useless: we can only generate zeroes + newRow(0, 1); // canonical + newRow(0, 200); + newRow(0, numeric_limits<quint32>::max() + 1.); + newRow(0, numeric_limits<quint64>::max() + 1.); + newRow(-1, 1.6); +} + +void tst_QRandomGenerator::stdUniformRealDistribution() +{ +#if !QT_HAS_INCLUDE(<random>) + QSKIP("<random> not found"); +#else + QFETCH(uint, control); + QFETCH(double, min); + QFETCH(double, sup); + setRNGControl(control & (SkipHWRNG|SkipSystemRNG|SkipMemfill)); + + { + QRandomGenerator rd; + { + std::uniform_real_distribution<double> dist(min, sup); + double value = dist(rd); + QVERIFY(value >= dist.min()); + if (min != sup) + QVERIFY(value < dist.max()); + } + } + + { + QRandomGenerator64 rd; + { + std::uniform_real_distribution<double> dist(min, sup); + double value = dist(rd); + QVERIFY(value >= dist.min()); + if (min != sup) + QVERIFY(value < dist.max()); + } + } +#endif +} + +void tst_QRandomGenerator::stdRandomDistributions() +{ +#if !QT_HAS_INCLUDE(<random>) + QSKIP("<random> not found"); +#else + // just a compile check for some of the distributions, besides + // std::uniform_int_distribution and std::uniform_real_distribution (tested + // above) + + QRandomGenerator rd; + + std::bernoulli_distribution()(rd); + + std::binomial_distribution<quint32>()(rd); + std::binomial_distribution<quint64>()(rd); + + std::negative_binomial_distribution<quint32>()(rd); + std::negative_binomial_distribution<quint64>()(rd); + + std::poisson_distribution<int>()(rd); + std::poisson_distribution<qint64>()(rd); + + std::normal_distribution<qreal>()(rd); + + { + std::discrete_distribution<int> discrete{0, 1, 1, 10000, 2}; + QVERIFY(discrete(rd) != 0); + QVERIFY_3TIMES(discrete(rd) == 3); + } +#endif +} + +QTEST_APPLESS_MAIN(tst_QRandomGenerator) + +#include "tst_qrandomgenerator.moc" |