Branch data Line data Source code
# 1 : : // Copyright (c) 2017-2020 The Bitcoin Core developers
# 2 : : // Distributed under the MIT software license, see the accompanying
# 3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
# 4 : :
# 5 : : #include <random.h>
# 6 : :
# 7 : : #include <test/util/setup_common.h>
# 8 : :
# 9 : : #include <boost/test/unit_test.hpp>
# 10 : :
# 11 : : #include <algorithm>
# 12 : : #include <random>
# 13 : :
# 14 : : BOOST_FIXTURE_TEST_SUITE(random_tests, BasicTestingSetup)
# 15 : :
# 16 : : BOOST_AUTO_TEST_CASE(osrandom_tests)
# 17 : 2 : {
# 18 : 2 : BOOST_CHECK(Random_SanityCheck());
# 19 : 2 : }
# 20 : :
# 21 : : BOOST_AUTO_TEST_CASE(fastrandom_tests)
# 22 : 2 : {
# 23 : : // Check that deterministic FastRandomContexts are deterministic
# 24 : 2 : g_mock_deterministic_tests = true;
# 25 : 2 : FastRandomContext ctx1(true);
# 26 : 2 : FastRandomContext ctx2(true);
# 27 : :
# 28 [ + + ]: 22 : for (int i = 10; i > 0; --i) {
# 29 : 20 : BOOST_CHECK_EQUAL(GetRand(std::numeric_limits<uint64_t>::max()), uint64_t{10393729187455219830U});
# 30 : 20 : BOOST_CHECK_EQUAL(GetRandInt(std::numeric_limits<int>::max()), int{769702006});
# 31 : 20 : BOOST_CHECK_EQUAL(GetRandMicros(std::chrono::hours{1}).count(), 2917185654);
# 32 : 20 : BOOST_CHECK_EQUAL(GetRandMillis(std::chrono::hours{1}).count(), 2144374);
# 33 : 20 : }
# 34 : 2 : BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
# 35 : 2 : BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
# 36 : 2 : BOOST_CHECK_EQUAL(ctx1.rand64(), ctx2.rand64());
# 37 : 2 : BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
# 38 : 2 : BOOST_CHECK(ctx1.randbytes(17) == ctx2.randbytes(17));
# 39 : 2 : BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
# 40 : 2 : BOOST_CHECK_EQUAL(ctx1.randbits(7), ctx2.randbits(7));
# 41 : 2 : BOOST_CHECK(ctx1.randbytes(128) == ctx2.randbytes(128));
# 42 : 2 : BOOST_CHECK_EQUAL(ctx1.rand32(), ctx2.rand32());
# 43 : 2 : BOOST_CHECK_EQUAL(ctx1.randbits(3), ctx2.randbits(3));
# 44 : 2 : BOOST_CHECK(ctx1.rand256() == ctx2.rand256());
# 45 : 2 : BOOST_CHECK(ctx1.randbytes(50) == ctx2.randbytes(50));
# 46 : :
# 47 : : // Check that a nondeterministic ones are not
# 48 : 2 : g_mock_deterministic_tests = false;
# 49 [ + + ]: 22 : for (int i = 10; i > 0; --i) {
# 50 : 20 : BOOST_CHECK(GetRand(std::numeric_limits<uint64_t>::max()) != uint64_t{10393729187455219830U});
# 51 : 20 : BOOST_CHECK(GetRandInt(std::numeric_limits<int>::max()) != int{769702006});
# 52 : 20 : BOOST_CHECK(GetRandMicros(std::chrono::hours{1}) != std::chrono::microseconds{2917185654});
# 53 : 20 : BOOST_CHECK(GetRandMillis(std::chrono::hours{1}) != std::chrono::milliseconds{2144374});
# 54 : 20 : }
# 55 : 2 : {
# 56 : 2 : FastRandomContext ctx3, ctx4;
# 57 : 2 : BOOST_CHECK(ctx3.rand64() != ctx4.rand64()); // extremely unlikely to be equal
# 58 : 2 : }
# 59 : 2 : {
# 60 : 2 : FastRandomContext ctx3, ctx4;
# 61 : 2 : BOOST_CHECK(ctx3.rand256() != ctx4.rand256());
# 62 : 2 : }
# 63 : 2 : {
# 64 : 2 : FastRandomContext ctx3, ctx4;
# 65 : 2 : BOOST_CHECK(ctx3.randbytes(7) != ctx4.randbytes(7));
# 66 : 2 : }
# 67 : 2 : }
# 68 : :
# 69 : : BOOST_AUTO_TEST_CASE(fastrandom_randbits)
# 70 : 2 : {
# 71 : 2 : FastRandomContext ctx1;
# 72 : 2 : FastRandomContext ctx2;
# 73 [ + + ]: 128 : for (int bits = 0; bits < 63; ++bits) {
# 74 [ + + ]: 126126 : for (int j = 0; j < 1000; ++j) {
# 75 : 126000 : uint64_t rangebits = ctx1.randbits(bits);
# 76 : 126000 : BOOST_CHECK_EQUAL(rangebits >> bits, 0U);
# 77 : 126000 : uint64_t range = ((uint64_t)1) << bits | rangebits;
# 78 : 126000 : uint64_t rand = ctx2.randrange(range);
# 79 : 126000 : BOOST_CHECK(rand < range);
# 80 : 126000 : }
# 81 : 126 : }
# 82 : 2 : }
# 83 : :
# 84 : : /** Does-it-compile test for compatibility with standard C++11 RNG interface. */
# 85 : : BOOST_AUTO_TEST_CASE(stdrandom_test)
# 86 : 2 : {
# 87 : 2 : FastRandomContext ctx;
# 88 : 2 : std::uniform_int_distribution<int> distribution(3, 9);
# 89 [ + + ]: 202 : for (int i = 0; i < 100; ++i) {
# 90 : 200 : int x = distribution(ctx);
# 91 : 200 : BOOST_CHECK(x >= 3);
# 92 : 200 : BOOST_CHECK(x <= 9);
# 93 : :
# 94 : 200 : std::vector<int> test{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
# 95 : 200 : std::shuffle(test.begin(), test.end(), ctx);
# 96 [ + + ]: 2200 : for (int j = 1; j <= 10; ++j) {
# 97 : 2000 : BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
# 98 : 2000 : }
# 99 : 200 : Shuffle(test.begin(), test.end(), ctx);
# 100 [ + + ]: 2200 : for (int j = 1; j <= 10; ++j) {
# 101 : 2000 : BOOST_CHECK(std::find(test.begin(), test.end(), j) != test.end());
# 102 : 2000 : }
# 103 : 200 : }
# 104 : 2 : }
# 105 : :
# 106 : : /** Test that Shuffle reaches every permutation with equal probability. */
# 107 : : BOOST_AUTO_TEST_CASE(shuffle_stat_test)
# 108 : 2 : {
# 109 : 2 : FastRandomContext ctx(true);
# 110 : 2 : uint32_t counts[5 * 5 * 5 * 5 * 5] = {0};
# 111 [ + + ]: 24002 : for (int i = 0; i < 12000; ++i) {
# 112 : 24000 : int data[5] = {0, 1, 2, 3, 4};
# 113 : 24000 : Shuffle(std::begin(data), std::end(data), ctx);
# 114 : 24000 : int pos = data[0] + data[1] * 5 + data[2] * 25 + data[3] * 125 + data[4] * 625;
# 115 : 24000 : ++counts[pos];
# 116 : 24000 : }
# 117 : 2 : unsigned int sum = 0;
# 118 : 2 : double chi_score = 0.0;
# 119 [ + + ]: 6252 : for (int i = 0; i < 5 * 5 * 5 * 5 * 5; ++i) {
# 120 : 6250 : int i1 = i % 5, i2 = (i / 5) % 5, i3 = (i / 25) % 5, i4 = (i / 125) % 5, i5 = i / 625;
# 121 : 6250 : uint32_t count = counts[i];
# 122 [ + + ][ + + ]: 6250 : if (i1 == i2 || i1 == i3 || i1 == i4 || i1 == i5 || i2 == i3 || i2 == i4 || i2 == i5 || i3 == i4 || i3 == i5 || i4 == i5) {
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# [ + + ][ + + ]
# 123 : 6010 : BOOST_CHECK(count == 0);
# 124 : 6010 : } else {
# 125 : 240 : chi_score += ((count - 100.0) * (count - 100.0)) / 100.0;
# 126 : 240 : BOOST_CHECK(count > 50);
# 127 : 240 : BOOST_CHECK(count < 150);
# 128 : 240 : sum += count;
# 129 : 240 : }
# 130 : 6250 : }
# 131 : 2 : BOOST_CHECK(chi_score > 58.1411); // 99.9999% confidence interval
# 132 : 2 : BOOST_CHECK(chi_score < 210.275);
# 133 : 2 : BOOST_CHECK_EQUAL(sum, 12000U);
# 134 : 2 : }
# 135 : :
# 136 : : BOOST_AUTO_TEST_SUITE_END()
|