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