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