random.h

Go to the documentation of this file.

// Copyright (c) 2009-2010 Satoshi Nakamoto
// Copyright (c) 2009-2016 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
#ifndef BITCOIN_RANDOM_H
#define BITCOIN_RANDOM_H
 
#include <crypto/chacha20.h>
#include <crypto/common.h>
#include <span.h>
#include <uint256.h>
#include <util/check.h>
 
#include <bit>
#include <cassert>
#include <chrono>
#include <concepts>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>
 
void RandomInit();
 
void RandAddPeriodic() noexcept;
 
void RandAddEvent(const uint32_t event_info) noexcept;
 
void GetRandBytes(Span<uint8_t> bytes) noexcept;
 
void GetStrongRandBytes(Span<uint8_t> bytes) noexcept;
 
// Forward declaration of RandomMixin, used in RandomNumberGenerator concept.
template <typename T> class RandomMixin;
 
template <typename T>
concept RandomNumberGenerator = requires(T &rng, Span<std::byte> s) {
    // A random number generator must provide rand64().
    { rng.rand64() } noexcept -> std::same_as<uint64_t>;
    // A random number generator must derive from RandomMixin, which adds other
    // rand* functions.
    requires std::derived_from<std::remove_reference_t<T>,
                               RandomMixin<std::remove_reference_t<T>>>;
};
 
template <typename T>
concept StdChronoDuration = requires {
    []<class Rep, class Period>(
        std::type_identity<std::chrono::duration<Rep, Period>>) {
    }(std::type_identity<T>());
};
 
double MakeExponentiallyDistributed(uint64_t uniform) noexcept;
 
template <typename T> class RandomMixin {
private:
    uint64_t bitbuf{0};
    int bitbuf_size{0};
 
    RandomNumberGenerator auto &Impl() noexcept {
        return static_cast<T &>(*this);
    }
 
protected:
    constexpr void FlushCache() noexcept {
        bitbuf = 0;
        bitbuf_size = 0;
    }
 
public:
    constexpr RandomMixin() noexcept = default;
 
    // Do not permit copying or moving an RNG.
    RandomMixin(const RandomMixin &) = delete;
    RandomMixin &operator=(const RandomMixin &) = delete;
    RandomMixin(RandomMixin &&) = delete;
    RandomMixin &operator=(RandomMixin &&) = delete;
 
    uint64_t randbits(int bits) noexcept {
        Assume(bits <= 64);
        // Requests for the full 64 bits are passed through.
        if (bits == 64) {
            return Impl().rand64();
        }
        uint64_t ret;
        if (bits <= bitbuf_size) {
            // If there is enough entropy left in bitbuf, return its bottom bits
            // bits.
            ret = bitbuf;
            bitbuf >>= bits;
            bitbuf_size -= bits;
        } else {
            // If not, return all of bitbuf, supplemented with the (bits -
            // bitbuf_size) bottom bits of a newly generated 64-bit number on
            // top. The remainder of that generated number becomes the new
            // bitbuf.
            uint64_t gen = Impl().rand64();
            ret = (gen << bitbuf_size) | bitbuf;
            bitbuf = gen >> (bits - bitbuf_size);
            bitbuf_size = 64 + bitbuf_size - bits;
        }
        // Return the bottom bits bits of ret.
        return ret & ((uint64_t{1} << bits) - 1);
    }
 
    template <int Bits> uint64_t randbits() noexcept {
        static_assert(Bits >= 0 && Bits <= 64);
        if constexpr (Bits == 64) {
            return Impl().rand64();
        } else {
            uint64_t ret;
            if (Bits <= bitbuf_size) {
                ret = bitbuf;
                bitbuf >>= Bits;
                bitbuf_size -= Bits;
            } else {
                uint64_t gen = Impl().rand64();
                ret = (gen << bitbuf_size) | bitbuf;
                bitbuf = gen >> (Bits - bitbuf_size);
                bitbuf_size = 64 + bitbuf_size - Bits;
            }
            constexpr uint64_t MASK = (uint64_t{1} << Bits) - 1;
            return ret & MASK;
        }
    }
 
    template <std::integral I> I randrange(I range) noexcept {
        static_assert(std::numeric_limits<I>::max() <=
                      std::numeric_limits<uint64_t>::max());
        Assume(range > 0);
        uint64_t maxval = range - 1U;
        int bits = std::bit_width(maxval);
        while (true) {
            uint64_t ret = Impl().randbits(bits);
            if (ret <= maxval) {
                return ret;
            }
        }
    }
 
    void fillrand(Span<std::byte> span) noexcept {
        while (span.size() >= 8) {
            uint64_t gen = Impl().rand64();
            WriteLE64(UCharCast(span.data()), gen);
            span = span.subspan(8);
        }
        if (span.size() >= 4) {
            uint32_t gen = Impl().rand32();
            WriteLE32(UCharCast(span.data()), gen);
            span = span.subspan(4);
        }
        while (span.size()) {
            span[0] = std::byte(Impl().template randbits<8>());
            span = span.subspan(1);
        }
    }
 
    template <std::integral I> I rand() noexcept {
        static_assert(std::numeric_limits<I>::max() <=
                      std::numeric_limits<uint64_t>::max());
        static constexpr auto BITS =
            std::bit_width(uint64_t(std::numeric_limits<I>::max()));
        static_assert(std::numeric_limits<I>::max() ==
                      std::numeric_limits<uint64_t>::max() >> (64 - BITS));
        return I(Impl().template randbits<BITS>());
    }
 
    template <BasicByte B = uint8_t>
    std::vector<B> randbytes(size_t len) noexcept {
        std::vector<B> ret(len);
        Impl().fillrand(MakeWritableByteSpan(ret));
        return ret;
    }
 
    uint32_t rand32() noexcept { return Impl().template randbits<32>(); }
 
    uint160 rand160() noexcept {
        uint160 ret;
        Impl().fillrand(MakeWritableByteSpan(ret));
        return ret;
    }
 
    uint256 rand256() noexcept {
        uint256 ret;
        Impl().fillrand(MakeWritableByteSpan(ret));
        return ret;
    }
 
    bool randbool() noexcept { return Impl().template randbits<1>(); }
 
    template <typename Tp>
    Tp rand_uniform_delay(const Tp &time,
                          typename Tp::duration range) noexcept {
        return time + rand_uniform_duration<Tp>(range);
    }
 
    template <typename Chrono>
        requires StdChronoDuration<typename Chrono::duration>
    typename Chrono::duration
    rand_uniform_duration(typename Chrono::duration range) noexcept {
        using Dur = typename Chrono::duration;
        return range.count() > 0
                   ? /* interval [0..range) */ Dur{Impl().randrange(
                         range.count())}
               : range.count() < 0
                   ? /* interval (range..0] */ -Dur{Impl().randrange(
                         -range.count())}
                   :
                   /* interval [0..0] */ Dur{0};
    };
 
    template <StdChronoDuration Dur>
    Dur randrange(typename std::common_type_t<Dur> range) noexcept
    // Having the compiler infer the template argument from the function
    // argument is dangerous, because the desired return value generally has a
    // different type than the function argument. So std::common_type is used to
    // force the call site to specify the type of the return value.
    {
        return Dur{Impl().randrange(range.count())};
    }
 
    std::chrono::microseconds
    rand_exp_duration(std::chrono::microseconds mean) noexcept {
        using namespace std::chrono_literals;
        auto unscaled = MakeExponentiallyDistributed(Impl().rand64());
        return std::chrono::duration_cast<std::chrono::microseconds>(
            unscaled * mean + 0.5us);
    }
 
    // Compatibility with the UniformRandomBitGenerator concept
    typedef uint64_t result_type;
    static constexpr uint64_t min() noexcept { return 0; }
    static constexpr uint64_t max() noexcept {
        return std::numeric_limits<uint64_t>::max();
    }
    inline uint64_t operator()() noexcept { return Impl().rand64(); }
};
 
class FastRandomContext : public RandomMixin<FastRandomContext> {
private:
    bool requires_seed;
    ChaCha20 rng;
 
    void RandomSeed() noexcept;
 
public:
    explicit FastRandomContext(bool fDeterministic = false) noexcept;
 
    explicit FastRandomContext(const uint256 &seed) noexcept;
 
    void Reseed(const uint256 &seed) noexcept;
 
    uint64_t rand64() noexcept {
        if (requires_seed) {
            RandomSeed();
        }
        std::array<std::byte, 8> buf;
        rng.Keystream(buf);
        return ReadLE64(UCharCast(buf.data()));
    }
 
    void fillrand(Span<std::byte> output) noexcept;
};
 
class InsecureRandomContext : public RandomMixin<InsecureRandomContext> {
    uint64_t m_s0;
    uint64_t m_s1;
 
    [[nodiscard]] constexpr static uint64_t
    SplitMix64(uint64_t &seedval) noexcept {
        uint64_t z = (seedval += 0x9e3779b97f4a7c15);
        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
        return z ^ (z >> 31);
    }
 
public:
    constexpr explicit InsecureRandomContext(uint64_t seedval) noexcept
        : m_s0(SplitMix64(seedval)), m_s1(SplitMix64(seedval)) {}
 
    constexpr void Reseed(uint64_t seedval) noexcept {
        FlushCache();
        m_s0 = SplitMix64(seedval);
        m_s1 = SplitMix64(seedval);
    }
 
    constexpr uint64_t rand64() noexcept {
        uint64_t s0 = m_s0, s1 = m_s1;
        const uint64_t result = std::rotl(s0 + s1, 17) + s0;
        s1 ^= s0;
        m_s0 = std::rotl(s0, 49) ^ s1 ^ (s1 << 21);
        m_s1 = std::rotl(s1, 28);
        return result;
    }
};
 
inline uint256 GetRandHash() noexcept {
    uint256 hash;
    GetRandBytes(hash);
    return hash;
}
 
template <typename I, RandomNumberGenerator R>
void Shuffle(I first, I last, R &&rng) {
    while (first != last) {
        size_t j = rng.randrange(last - first);
        if (j) {
            using std::swap;
            swap(*first, *(first + j));
        }
        ++first;
    }
}
 
bool Random_SanityCheck();
 
#endif // BITCOIN_RANDOM_H