Merge bitcoin/bitcoin#30160: util: add BitSet

47f705b33fc1381d96c99038e2110e6fe2b2f883 tests: add fuzz tests for BitSet (Pieter Wuille)
59a6df6bd584701f820ad60a10d9d477bf0236b5 util: add BitSet (Pieter Wuille)

Pull request description:

  Extracted from #30126.

  This introduces the `BitSet` data structure, inspired by `std::bitset`, but with a few features that cannot be implemented on top without efficiency loss:
  * Finding the first set bit (`First`)
  * Finding the last set bit (`Last`)
  * Iterating over all set bits (`begin` and `end`).

  And a few other operators/member functions that help readability for #30126:
  * `operator-` for set subtraction
  * `Overlaps()` for testing whether intersection is non-empty
  * `IsSupersetOf()` for testing (non-strict) supersetness
  * `IsSubsetOf()` for testing (non-strict) subsetness
  * `Fill()` to construct a set with all numbers from 0 to n-1, inclusive
  * `Singleton()` to construct a set with one specific element.

  Everything is tested through a simulation-based fuzz test that compares the behavior with normal `std::bitset` equivalent operations.

ACKs for top commit:
  instagibbs:
    ACK https://github.com/bitcoin/bitcoin/pull/30160/commits/47f705b33fc1381d96c99038e2110e6fe2b2f883
  achow101:
    ACK 47f705b33fc1381d96c99038e2110e6fe2b2f883
  cbergqvist:
    re-ACK 47f705b33fc1381d96c99038e2110e6fe2b2f883
  theStack:
    Code-review ACK 47f705b33fc1381d96c99038e2110e6fe2b2f883

Tree-SHA512: e451bf4b801f193239ee434b6b614f5a2ac7bb49c70af5aba24c2ac0c54acbef4672556800e4ac799ae835632bdba716209c5ca8c37433a6883dab4eb7cd67c1

4 files changed, 845 insertions, 0 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index abbc5cdc1f..a69daeae2d 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -292,6 +292,7 @@ BITCOIN_CORE_H = \
   util/batchpriority.h \
   util/bip32.h \
   util/bitdeque.h \
+  util/bitset.h \
   util/bytevectorhash.h \
   util/chaintype.h \
   util/check.h \
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 8a638ec690..bde62a1502 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -294,6 +294,7 @@ test_fuzz_fuzz_SOURCES = \
  test/fuzz/bech32.cpp \
  test/fuzz/bip324.cpp \
  test/fuzz/bitdeque.cpp \
+ test/fuzz/bitset.cpp \
  test/fuzz/block.cpp \
  test/fuzz/block_header.cpp \
  test/fuzz/blockfilter.cpp \
diff --git a/src/test/fuzz/bitset.cpp b/src/test/fuzz/bitset.cpp
new file mode 100644
index 0000000000..98fcddfb8d
--- /dev/null
+++ b/src/test/fuzz/bitset.cpp
@@ -0,0 +1,316 @@
+// Copyright (c) The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <span.h>
+#include <test/fuzz/util.h>
+#include <test/util/xoroshiro128plusplus.h>
+#include <util/bitset.h>
+
+#include <bitset>
+#include <vector>
+
+namespace {
+
+/** Pop the first byte from a Span<const uint8_t>, and return it. */
+uint8_t ReadByte(Span<const uint8_t>& buffer)
+{
+    if (buffer.empty()) return 0;
+    uint8_t ret = buffer.front();
+    buffer = buffer.subspan(1);
+    return ret;
+}
+
+/** Perform a simulation fuzz test on BitSet type S. */
+template<typename S>
+void TestType(Span<const uint8_t> buffer)
+{
+    /** This fuzz test's design is based on the assumption that the actual bits stored in the
+     *  bitsets and their simulations do not matter for the purpose of detecting edge cases, thus
+     *  these are taken from a deterministically-seeded RNG instead. To provide some level of
+     *  variation however, pick the seed based on the buffer size and size of the chosen bitset. */
+    XoRoShiRo128PlusPlus rng(buffer.size() + 0x10000 * S::Size());
+
+    using Sim = std::bitset<S::Size()>;
+    // Up to 4 real BitSets (initially 2).
+    std::vector<S> real(2);
+    // Up to 4 std::bitsets with the same corresponding contents.
+    std::vector<Sim> sim(2);
+
+    /* Compare sim[idx] with real[idx], using all inspector operations. */
+    auto compare_fn = [&](unsigned idx) {
+        /* iterators and operator[] */
+        auto it = real[idx].begin();
+        unsigned first = S::Size();
+        unsigned last = S::Size();
+        for (unsigned i = 0; i < S::Size(); ++i) {
+            bool match = (it != real[idx].end()) && *it == i;
+            assert(sim[idx][i] == real[idx][i]);
+            assert(match == real[idx][i]);
+            assert((it == real[idx].end()) != (it != real[idx].end()));
+            if (match) {
+                ++it;
+                if (first == S::Size()) first = i;
+                last = i;
+            }
+        }
+        assert(it == real[idx].end());
+        assert(!(it != real[idx].end()));
+        /* Any / None */
+        assert(sim[idx].any() == real[idx].Any());
+        assert(sim[idx].none() == real[idx].None());
+        /* First / Last */
+        if (sim[idx].any()) {
+            assert(first == real[idx].First());
+            assert(last == real[idx].Last());
+        }
+        /* Count */
+        assert(sim[idx].count() == real[idx].Count());
+    };
+
+    LIMITED_WHILE(buffer.size() > 0, 1000) {
+        // Read one byte to determine which operation to execute on the BitSets.
+        int command = ReadByte(buffer) % 64;
+        // Read another byte that determines which bitsets will be involved.
+        unsigned args = ReadByte(buffer);
+        unsigned dest = ((args & 7) * sim.size()) >> 3;
+        unsigned src = (((args >> 3) & 7) * sim.size()) >> 3;
+        unsigned aux = (((args >> 6) & 3) * sim.size()) >> 2;
+        // Args are in range for non-empty sim, or sim is completely empty and will be grown
+        assert((sim.empty() && dest == 0 && src == 0 && aux == 0) ||
+            (!sim.empty() &&  dest < sim.size() && src < sim.size() && aux < sim.size()));
+
+        // Pick one operation based on value of command. Not all operations are always applicable.
+        // Loop through the applicable ones until command reaches 0 (which avoids the need to
+        // compute the number of applicable commands ahead of time).
+        while (true) {
+            if (dest < sim.size() && command-- == 0) {
+                /* Set() (true) */
+                unsigned val = ReadByte(buffer) % S::Size();
+                assert(sim[dest][val] == real[dest][val]);
+                sim[dest].set(val);
+                real[dest].Set(val);
+                break;
+            } else if (dest < sim.size() && command-- == 0) {
+                /* Reset() */
+                unsigned val = ReadByte(buffer) % S::Size();
+                assert(sim[dest][val] == real[dest][val]);
+                sim[dest].reset(val);
+                real[dest].Reset(val);
+                break;
+            } else if (dest < sim.size() && command-- == 0) {
+                /* Set() (conditional) */
+                unsigned val = ReadByte(buffer) % S::Size();
+                assert(sim[dest][val] == real[dest][val]);
+                sim[dest].set(val, args >> 7);
+                real[dest].Set(val, args >> 7);
+                break;
+            } else if (sim.size() < 4 && command-- == 0) {
+                /* Construct empty. */
+                sim.resize(sim.size() + 1);
+                real.resize(real.size() + 1);
+                break;
+            } else if (sim.size() < 4 && command-- == 0) {
+                /* Construct singleton. */
+                unsigned val = ReadByte(buffer) % S::Size();
+                std::bitset<S::Size()> newset;
+                newset[val] = true;
+                sim.push_back(newset);
+                real.push_back(S::Singleton(val));
+                break;
+            } else if (dest < sim.size() && command-- == 0) {
+                /* Make random. */
+                compare_fn(dest);
+                sim[dest].reset();
+                real[dest] = S{};
+                for (unsigned i = 0; i < S::Size(); ++i) {
+                    if (rng() & 1) {
+                        sim[dest][i] = true;
+                        real[dest].Set(i);
+                    }
+                }
+                break;
+            } else if (dest < sim.size() && command-- == 0) {
+                /* Assign initializer list. */
+                unsigned r1 = rng() % S::Size();
+                unsigned r2 = rng() % S::Size();
+                unsigned r3 = rng() % S::Size();
+                compare_fn(dest);
+                sim[dest].reset();
+                real[dest] = {r1, r2, r3};
+                sim[dest].set(r1);
+                sim[dest].set(r2);
+                sim[dest].set(r3);
+                break;
+            } else if (!sim.empty() && command-- == 0) {
+                /* Destruct. */
+                compare_fn(sim.size() - 1);
+                sim.pop_back();
+                real.pop_back();
+                break;
+            } else if (sim.size() < 4 && src < sim.size() && command-- == 0) {
+                /* Copy construct. */
+                sim.emplace_back(sim[src]);
+                real.emplace_back(real[src]);
+                break;
+            } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+                /* Copy assign. */
+                compare_fn(dest);
+                sim[dest] = sim[src];
+                real[dest] = real[src];
+                break;
+            } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+                /* swap() function. */
+                swap(sim[dest], sim[src]);
+                swap(real[dest], real[src]);
+                break;
+            } else if (sim.size() < 4 && command-- == 0) {
+                /* Construct with initializer list. */
+                unsigned r1 = rng() % S::Size();
+                unsigned r2 = rng() % S::Size();
+                sim.emplace_back();
+                sim.back().set(r1);
+                sim.back().set(r2);
+                real.push_back(S{r1, r2});
+                break;
+            } else if (dest < sim.size() && command-- == 0) {
+                /* Fill() + copy assign. */
+                unsigned len = ReadByte(buffer) % S::Size();
+                compare_fn(dest);
+                sim[dest].reset();
+                for (unsigned i = 0; i < len; ++i) sim[dest][i] = true;
+                real[dest] = S::Fill(len);
+                break;
+            } else if (src < sim.size() && command-- == 0) {
+                /* Iterator copy based compare. */
+                unsigned val = ReadByte(buffer) % S::Size();
+                /* In a first loop, compare begin..end, and copy to it_copy at some point. */
+                auto it = real[src].begin(), it_copy = it;
+                for (unsigned i = 0; i < S::Size(); ++i) {
+                    if (i == val) it_copy = it;
+                    bool match = (it != real[src].end()) && *it == i;
+                    assert(match == sim[src][i]);
+                    if (match) ++it;
+                }
+                assert(it == real[src].end());
+                /* Then compare from the copied point again to end. */
+                for (unsigned i = val; i < S::Size(); ++i) {
+                    bool match = (it_copy != real[src].end()) && *it_copy == i;
+                    assert(match == sim[src][i]);
+                    if (match) ++it_copy;
+                }
+                assert(it_copy == real[src].end());
+                break;
+            } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+                /* operator|= */
+                compare_fn(dest);
+                sim[dest] |= sim[src];
+                real[dest] |= real[src];
+                break;
+            } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+                /* operator&= */
+                compare_fn(dest);
+                sim[dest] &= sim[src];
+                real[dest] &= real[src];
+                break;
+            } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+                /* operator-= */
+                compare_fn(dest);
+                sim[dest] &= ~sim[src];
+                real[dest] -= real[src];
+                break;
+            } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+                /* operator^= */
+                compare_fn(dest);
+                sim[dest] ^= sim[src];
+                real[dest] ^= real[src];
+                break;
+            } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+                /* operator| */
+                compare_fn(dest);
+                sim[dest] = sim[src] | sim[aux];
+                real[dest] = real[src] | real[aux];
+                break;
+            } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+                /* operator& */
+                compare_fn(dest);
+                sim[dest] = sim[src] & sim[aux];
+                real[dest] = real[src] & real[aux];
+                break;
+            } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+                /* operator- */
+                compare_fn(dest);
+                sim[dest] = sim[src] & ~sim[aux];
+                real[dest] = real[src] - real[aux];
+                break;
+            } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+                /* operator^ */
+                compare_fn(dest);
+                sim[dest] = sim[src] ^ sim[aux];
+                real[dest] = real[src] ^ real[aux];
+                break;
+            } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
+                /* IsSupersetOf() and IsSubsetOf() */
+                bool is_superset = (sim[aux] & ~sim[src]).none();
+                bool is_subset = (sim[src] & ~sim[aux]).none();
+                assert(real[src].IsSupersetOf(real[aux]) == is_superset);
+                assert(real[src].IsSubsetOf(real[aux]) == is_subset);
+                assert(real[aux].IsSupersetOf(real[src]) == is_subset);
+                assert(real[aux].IsSubsetOf(real[src]) == is_superset);
+                break;
+            } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
+                /* operator== and operator!= */
+                assert((sim[src] == sim[aux]) == (real[src] == real[aux]));
+                assert((sim[src] != sim[aux]) == (real[src] != real[aux]));
+                break;
+            } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
+                /* Overlaps() */
+                assert((sim[src] & sim[aux]).any() == real[src].Overlaps(real[aux]));
+                assert((sim[src] & sim[aux]).any() == real[aux].Overlaps(real[src]));
+                break;
+            }
+        }
+    }
+    /* Fully compare the final state. */
+    for (unsigned i = 0; i < sim.size(); ++i) {
+        compare_fn(i);
+    }
+}
+
+} // namespace
+
+FUZZ_TARGET(bitset)
+{
+    unsigned typdat = ReadByte(buffer) % 8;
+    if (typdat == 0) {
+        /* 16 bits */
+        TestType<bitset_detail::IntBitSet<uint16_t>>(buffer);
+        TestType<bitset_detail::MultiIntBitSet<uint16_t, 1>>(buffer);
+    } else if (typdat == 1) {
+        /* 32 bits */
+        TestType<bitset_detail::MultiIntBitSet<uint16_t, 2>>(buffer);
+        TestType<bitset_detail::IntBitSet<uint32_t>>(buffer);
+    } else if (typdat == 2) {
+        /* 48 bits */
+        TestType<bitset_detail::MultiIntBitSet<uint16_t, 3>>(buffer);
+    } else if (typdat == 3) {
+        /* 64 bits */
+        TestType<bitset_detail::IntBitSet<uint64_t>>(buffer);
+        TestType<bitset_detail::MultiIntBitSet<uint64_t, 1>>(buffer);
+        TestType<bitset_detail::MultiIntBitSet<uint32_t, 2>>(buffer);
+        TestType<bitset_detail::MultiIntBitSet<uint16_t, 4>>(buffer);
+    } else if (typdat == 4) {
+        /* 96 bits */
+        TestType<bitset_detail::MultiIntBitSet<uint32_t, 3>>(buffer);
+    } else if (typdat == 5) {
+        /* 128 bits */
+        TestType<bitset_detail::MultiIntBitSet<uint64_t, 2>>(buffer);
+        TestType<bitset_detail::MultiIntBitSet<uint32_t, 4>>(buffer);
+    } else if (typdat == 6) {
+        /* 192 bits */
+        TestType<bitset_detail::MultiIntBitSet<uint64_t, 3>>(buffer);
+    } else if (typdat == 7) {
+        /* 256 bits */
+        TestType<bitset_detail::MultiIntBitSet<uint64_t, 4>>(buffer);
+    }
+}
diff --git a/src/util/bitset.h b/src/util/bitset.h
new file mode 100644
index 0000000000..6f9e808c37
--- /dev/null
+++ b/src/util/bitset.h
@@ -0,0 +1,527 @@
+// Copyright (c) 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_UTIL_BITSET_H
+#define BITCOIN_UTIL_BITSET_H
+
+#include <util/check.h>
+
+#include <array>
+#include <bit>
+#include <cstdint>
+#include <limits>
+#include <type_traits>
+
+/* This file provides data types similar to std::bitset, but adds the following functionality:
+ *
+ * - Efficient iteration over all set bits (compatible with range-based for loops).
+ * - Efficient search for the first and last set bit (First() and Last()).
+ * - Efficient set subtraction: (a - b) implements "a and not b".
+ * - Efficient non-strict subset/superset testing: IsSubsetOf() and IsSupersetOf().
+ * - Efficient set overlap testing: a.Overlaps(b)
+ * - Efficient construction of set containing 0..N-1 (S::Fill).
+ * - Efficient construction of a single set (S::Singleton).
+ * - Construction from initializer lists.
+ *
+ * Other differences:
+ * - BitSet<N> is a bitset that supports at least N elements, but may support more (Size() reports
+ *   the actual number). Because the actual number is unpredictable, there are no operations that
+ *   affect all positions (like std::bitset's operator~, flip(), or all()).
+ * - Various other unimplemented features.
+ */
+
+namespace bitset_detail {
+
+/** Count the number of bits set in an unsigned integer type. */
+template<typename I>
+unsigned inline constexpr PopCount(I v)
+{
+    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
+    constexpr auto BITS = std::numeric_limits<I>::digits;
+    // Algorithms from https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation.
+    // These seem to be faster than std::popcount when compiling for non-SSE4 on x86_64.
+    if constexpr (BITS <= 32) {
+        v -= (v >> 1) & 0x55555555;
+        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
+        v = (v + (v >> 4)) & 0x0f0f0f0f;
+        if constexpr (BITS > 8) v += v >> 8;
+        if constexpr (BITS > 16) v += v >> 16;
+        return v & 0x3f;
+    } else {
+        static_assert(BITS <= 64);
+        v -= (v >> 1) & 0x5555555555555555;
+        v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
+        v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f;
+        return (v * uint64_t{0x0101010101010101}) >> 56;
+    }
+}
+
+/** A bitset implementation backed by a single integer of type I. */
+template<typename I>
+class IntBitSet
+{
+    // Only binary, unsigned, integer, types allowed.
+    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
+    /** The maximum number of bits this bitset supports. */
+    static constexpr unsigned MAX_SIZE = std::numeric_limits<I>::digits;
+    /** Integer whose bits represent this bitset. */
+    I m_val;
+    /** Internal constructor with a given integer as contents. */
+    IntBitSet(I val) noexcept : m_val{val} {}
+    /** Dummy type to return using end(). Only used for comparing with Iterator. */
+    class IteratorEnd
+    {
+        friend class IntBitSet;
+        constexpr IteratorEnd() = default;
+    public:
+        constexpr IteratorEnd(const IteratorEnd&) = default;
+    };
+    /** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
+    class Iterator
+    {
+        friend class IntBitSet;
+        I m_val; /**< The original integer's remaining bits. */
+        unsigned m_pos; /** Last reported 1 position (if m_pos != 0). */
+        constexpr Iterator(I val) noexcept : m_val(val), m_pos(0)
+        {
+            if (m_val != 0) m_pos = std::countr_zero(m_val);
+        }
+    public:
+        /** Do not allow external code to construct an Iterator. */
+        Iterator() = delete;
+        // Copying is allowed.
+        constexpr Iterator(const Iterator&) noexcept = default;
+        constexpr Iterator& operator=(const Iterator&) noexcept = default;
+        /** Test whether we are done (can only compare with IteratorEnd). */
+        constexpr friend bool operator==(const Iterator& a, const IteratorEnd&) noexcept
+        {
+            return a.m_val == 0;
+        }
+        /** Progress to the next 1 bit (only if != IteratorEnd). */
+        constexpr Iterator& operator++() noexcept
+        {
+            Assume(m_val != 0);
+            m_val &= m_val - I{1U};
+            if (m_val != 0) m_pos = std::countr_zero(m_val);
+            return *this;
+        }
+        /** Get the current bit position (only if != IteratorEnd). */
+        constexpr unsigned operator*() const noexcept
+        {
+            Assume(m_val != 0);
+            return m_pos;
+        }
+    };
+
+public:
+    /** Construct an all-zero bitset. */
+    constexpr IntBitSet() noexcept : m_val{0} {}
+    /** Copy construct a bitset. */
+    constexpr IntBitSet(const IntBitSet&) noexcept = default;
+    /** Construct from a list of values. */
+    constexpr IntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val(0)
+    {
+        for (auto pos : ilist) Set(pos);
+    }
+    /** Copy assign a bitset. */
+    constexpr IntBitSet& operator=(const IntBitSet&) noexcept = default;
+    /** Assign from a list of positions (which will be made true, all others false). */
+    constexpr IntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
+    {
+        m_val = 0;
+        for (auto pos : ilist) Set(pos);
+        return *this;
+    }
+    /** Construct a bitset with the singleton i. */
+    static constexpr IntBitSet Singleton(unsigned i) noexcept
+    {
+        Assume(i < MAX_SIZE);
+        return IntBitSet(I(1U) << i);
+    }
+    /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
+    static constexpr IntBitSet Fill(unsigned count) noexcept
+    {
+        IntBitSet ret;
+        Assume(count <= MAX_SIZE);
+        if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count);
+        return ret;
+    }
+    /** Set a bit to 1. */
+    constexpr void Set(unsigned pos) noexcept
+    {
+        Assume(pos < MAX_SIZE);
+        m_val |= I{1U} << pos;
+    }
+    /** Set a bit to the specified value. */
+    constexpr void Set(unsigned pos, bool val) noexcept
+    {
+        Assume(pos < MAX_SIZE);
+        m_val = (m_val & ~I(I{1U} << pos)) | (I(val) << pos);
+    }
+    /** Set a bit to 0. */
+    constexpr void Reset(unsigned pos) noexcept
+    {
+        Assume(pos < MAX_SIZE);
+        m_val &= ~I(I{1U} << pos);
+    }
+    /** Retrieve a bit at the given position. */
+    constexpr bool operator[](unsigned pos) const noexcept
+    {
+        Assume(pos < MAX_SIZE);
+        return (m_val >> pos) & 1U;
+    }
+    /** Compute the number of 1 bits in the bitset. */
+    constexpr unsigned Count() const noexcept { return PopCount(m_val); }
+    /** Return the number of bits that this object holds. */
+    static constexpr unsigned Size() noexcept { return MAX_SIZE; }
+    /** Check if all bits are 0. */
+    constexpr bool None() const noexcept { return m_val == 0; }
+    /** Check if any bits are 1. */
+    constexpr bool Any() const noexcept { return !None(); }
+    /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
+    constexpr Iterator begin() const noexcept { return Iterator(m_val); }
+    /** Return a dummy object to compare Iterators with. */
+    constexpr IteratorEnd end() const noexcept { return IteratorEnd(); }
+    /** Find the first element (requires Any()). */
+    constexpr unsigned First() const noexcept
+    {
+        Assume(m_val != 0);
+        return std::countr_zero(m_val);
+    }
+    /** Find the last element (requires Any()). */
+    constexpr unsigned Last() const noexcept
+    {
+        Assume(m_val != 0);
+        return std::bit_width(m_val) - 1;
+    }
+    /** Set this object's bits to be the binary AND between respective bits from this and a. */
+    constexpr IntBitSet& operator|=(const IntBitSet& a) noexcept { m_val |= a.m_val; return *this; }
+    /** Set this object's bits to be the binary OR between respective bits from this and a. */
+    constexpr IntBitSet& operator&=(const IntBitSet& a) noexcept { m_val &= a.m_val; return *this; }
+    /** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
+    constexpr IntBitSet& operator-=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; }
+    /** Set this object's bits to be the binary XOR between respective bits from this as a. */
+    constexpr IntBitSet& operator^=(const IntBitSet& a) noexcept { m_val ^= a.m_val; return *this; }
+    /** Check if the intersection between two sets is non-empty. */
+    constexpr bool Overlaps(const IntBitSet& a) const noexcept { return m_val & a.m_val; }
+    /** Return an object with the binary AND between respective bits from a and b. */
+    friend constexpr IntBitSet operator&(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & b.m_val); }
+    /** Return an object with the binary OR between respective bits from a and b. */
+    friend constexpr IntBitSet operator|(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val | b.m_val); }
+    /** Return an object with the binary AND NOT between respective bits from a and b. */
+    friend constexpr IntBitSet operator-(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & ~b.m_val); }
+    /** Return an object with the binary XOR between respective bits from a and b. */
+    friend constexpr IntBitSet operator^(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val ^ b.m_val); }
+    /** Check if bitset a and bitset b are identical. */
+    friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default;
+    /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
+    constexpr bool IsSupersetOf(const IntBitSet& a) const noexcept { return (a.m_val & ~m_val) == 0; }
+    /** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
+    constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
+    /** Swap two bitsets. */
+    friend constexpr void swap(IntBitSet& a, IntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
+};
+
+/** A bitset implementation backed by N integers of type I. */
+template<typename I, unsigned N>
+class MultiIntBitSet
+{
+    // Only binary, unsigned, integer, types allowed.
+    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
+    // Cannot be empty.
+    static_assert(N > 0);
+    /** The number of bits per integer. */
+    static constexpr unsigned LIMB_BITS = std::numeric_limits<I>::digits;
+    /** Number of elements this set type supports. */
+    static constexpr unsigned MAX_SIZE = LIMB_BITS * N;
+    // No overflow allowed here.
+    static_assert(MAX_SIZE / LIMB_BITS == N);
+    /** Array whose member integers store the bits of the set. */
+    std::array<I, N> m_val;
+    /** Dummy type to return using end(). Only used for comparing with Iterator. */
+    class IteratorEnd
+    {
+        friend class MultiIntBitSet;
+        constexpr IteratorEnd() = default;
+    public:
+        constexpr IteratorEnd(const IteratorEnd&) = default;
+    };
+    /** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
+    class Iterator
+    {
+        friend class MultiIntBitSet;
+        const std::array<I, N>* m_ptr; /**< Pointer to array to fetch bits from. */
+        I m_val; /**< The remaining bits of (*m_ptr)[m_idx]. */
+        unsigned m_pos; /**< The last reported position. */
+        unsigned m_idx; /**< The index in *m_ptr currently being iterated over. */
+        constexpr Iterator(const std::array<I, N>& ref) noexcept : m_ptr(&ref), m_idx(0)
+        {
+            do {
+                m_val = (*m_ptr)[m_idx];
+                if (m_val) {
+                    m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
+                    break;
+                }
+                ++m_idx;
+            } while(m_idx < N);
+        }
+
+    public:
+        /** Do not allow external code to construct an Iterator. */
+        Iterator() = delete;
+        // Copying is allowed.
+        constexpr Iterator(const Iterator&) noexcept = default;
+        constexpr Iterator& operator=(const Iterator&) noexcept = default;
+        /** Test whether we are done (can only compare with IteratorEnd). */
+        friend constexpr bool operator==(const Iterator& a, const IteratorEnd&) noexcept
+        {
+            return a.m_idx == N;
+        }
+        /** Progress to the next 1 bit (only if != IteratorEnd). */
+        constexpr Iterator& operator++() noexcept
+        {
+            Assume(m_idx < N);
+            m_val &= m_val - I{1U};
+            if (m_val == 0) {
+                while (true) {
+                    ++m_idx;
+                    if (m_idx == N) break;
+                    m_val = (*m_ptr)[m_idx];
+                    if (m_val) {
+                        m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
+                        break;
+                    }
+                }
+            } else {
+                m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
+            }
+            return *this;
+        }
+        /** Get the current bit position (only if != IteratorEnd). */
+        constexpr unsigned operator*() const noexcept
+        {
+            Assume(m_idx < N);
+            return m_pos;
+        }
+    };
+
+public:
+    /** Construct an all-zero bitset. */
+    constexpr MultiIntBitSet() noexcept : m_val{} {}
+    /** Copy construct a bitset. */
+    constexpr MultiIntBitSet(const MultiIntBitSet&) noexcept = default;
+    /** Copy assign a bitset. */
+    constexpr MultiIntBitSet& operator=(const MultiIntBitSet&) noexcept = default;
+    /** Set a bit to 1. */
+    void constexpr Set(unsigned pos) noexcept
+    {
+        Assume(pos < MAX_SIZE);
+        m_val[pos / LIMB_BITS] |= I{1U} << (pos % LIMB_BITS);
+    }
+    /** Set a bit to the specified value. */
+    void constexpr Set(unsigned pos, bool val) noexcept
+    {
+        Assume(pos < MAX_SIZE);
+        m_val[pos / LIMB_BITS] = (m_val[pos / LIMB_BITS] & ~I(I{1U} << (pos % LIMB_BITS))) |
+                                 (I{val} << (pos % LIMB_BITS));
+    }
+    /** Construct a bitset from a list of values. */
+    constexpr MultiIntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val{}
+    {
+        for (auto pos : ilist) Set(pos);
+    }
+    /** Set a bitset to a list of values. */
+    constexpr MultiIntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
+    {
+        m_val.fill(0);
+        for (auto pos : ilist) Set(pos);
+        return *this;
+    }
+    /** Set a bit to 0. */
+    void constexpr Reset(unsigned pos) noexcept
+    {
+        Assume(pos < MAX_SIZE);
+        m_val[pos / LIMB_BITS] &= ~I(I{1U} << (pos % LIMB_BITS));
+    }
+    /** Retrieve a bit at the given position. */
+    bool constexpr operator[](unsigned pos) const noexcept
+    {
+        Assume(pos < MAX_SIZE);
+        return (m_val[pos / LIMB_BITS] >> (pos % LIMB_BITS)) & 1U;
+    }
+    /** Construct a bitset with the singleton pos. */
+    static constexpr MultiIntBitSet Singleton(unsigned pos) noexcept
+    {
+        Assume(pos < MAX_SIZE);
+        MultiIntBitSet ret;
+        ret.m_val[pos / LIMB_BITS] = I{1U} << (pos % LIMB_BITS);
+        return ret;
+    }
+    /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
+    static constexpr MultiIntBitSet Fill(unsigned count) noexcept
+    {
+        Assume(count <= MAX_SIZE);
+        MultiIntBitSet ret;
+        if (count) {
+            unsigned i = 0;
+            while (count > LIMB_BITS) {
+                ret.m_val[i++] = ~I{0};
+                count -= LIMB_BITS;
+            }
+            ret.m_val[i] = I(~I{0}) >> (LIMB_BITS - count);
+        }
+        return ret;
+    }
+    /** Return the number of bits that this object holds. */
+    static constexpr unsigned Size() noexcept { return MAX_SIZE; }
+    /** Compute the number of 1 bits in the bitset. */
+    unsigned constexpr Count() const noexcept
+    {
+        unsigned ret{0};
+        for (I v : m_val) ret += PopCount(v);
+        return ret;
+    }
+    /** Check if all bits are 0. */
+    bool constexpr None() const noexcept
+    {
+        for (auto v : m_val) {
+            if (v != 0) return false;
+        }
+        return true;
+    }
+    /** Check if any bits are 1. */
+    bool constexpr Any() const noexcept { return !None(); }
+    /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
+    Iterator constexpr begin() const noexcept { return Iterator(m_val); }
+    /** Return a dummy object to compare Iterators with. */
+    IteratorEnd constexpr end() const noexcept { return IteratorEnd(); }
+    /** Find the first element (requires Any()). */
+    unsigned constexpr First() const noexcept
+    {
+        unsigned p = 0;
+        while (m_val[p] == 0) {
+            ++p;
+            Assume(p < N);
+        }
+        return std::countr_zero(m_val[p]) + p * LIMB_BITS;
+    }
+    /** Find the last element (requires Any()). */
+    unsigned constexpr Last() const noexcept
+    {
+        unsigned p = N - 1;
+        while (m_val[p] == 0) {
+            Assume(p > 0);
+            --p;
+        }
+        return std::bit_width(m_val[p]) - 1 + p * LIMB_BITS;
+    }
+    /** Set this object's bits to be the binary OR between respective bits from this and a. */
+    constexpr MultiIntBitSet& operator|=(const MultiIntBitSet& a) noexcept
+    {
+        for (unsigned i = 0; i < N; ++i) {
+            m_val[i] |= a.m_val[i];
+        }
+        return *this;
+    }
+    /** Set this object's bits to be the binary AND between respective bits from this and a. */
+    constexpr MultiIntBitSet& operator&=(const MultiIntBitSet& a) noexcept
+    {
+        for (unsigned i = 0; i < N; ++i) {
+            m_val[i] &= a.m_val[i];
+        }
+        return *this;
+    }
+    /** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
+    constexpr MultiIntBitSet& operator-=(const MultiIntBitSet& a) noexcept
+    {
+        for (unsigned i = 0; i < N; ++i) {
+            m_val[i] &= ~a.m_val[i];
+        }
+        return *this;
+    }
+    /** Set this object's bits to be the binary XOR between respective bits from this and a. */
+    constexpr MultiIntBitSet& operator^=(const MultiIntBitSet& a) noexcept
+    {
+        for (unsigned i = 0; i < N; ++i) {
+            m_val[i] ^= a.m_val[i];
+        }
+        return *this;
+    }
+    /** Check whether the intersection between two sets is non-empty. */
+    constexpr bool Overlaps(const MultiIntBitSet& a) const noexcept
+    {
+        for (unsigned i = 0; i < N; ++i) {
+            if (m_val[i] & a.m_val[i]) return true;
+        }
+        return false;
+    }
+    /** Return an object with the binary AND between respective bits from a and b. */
+    friend constexpr MultiIntBitSet operator&(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
+    {
+        MultiIntBitSet r;
+        for (unsigned i = 0; i < N; ++i) {
+            r.m_val[i] = a.m_val[i] & b.m_val[i];
+        }
+        return r;
+    }
+    /** Return an object with the binary OR between respective bits from a and b. */
+    friend constexpr MultiIntBitSet operator|(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
+    {
+        MultiIntBitSet r;
+        for (unsigned i = 0; i < N; ++i) {
+            r.m_val[i] = a.m_val[i] | b.m_val[i];
+        }
+        return r;
+    }
+    /** Return an object with the binary AND NOT between respective bits from a and b. */
+    friend constexpr MultiIntBitSet operator-(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
+    {
+        MultiIntBitSet r;
+        for (unsigned i = 0; i < N; ++i) {
+            r.m_val[i] = a.m_val[i] & ~b.m_val[i];
+        }
+        return r;
+    }
+    /** Return an object with the binary XOR between respective bits from a and b. */
+    friend constexpr MultiIntBitSet operator^(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
+    {
+        MultiIntBitSet r;
+        for (unsigned i = 0; i < N; ++i) {
+            r.m_val[i] = a.m_val[i] ^ b.m_val[i];
+        }
+        return r;
+    }
+    /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
+    constexpr bool IsSupersetOf(const MultiIntBitSet& a) const noexcept
+    {
+        for (unsigned i = 0; i < N; ++i) {
+            if (a.m_val[i] & ~m_val[i]) return false;
+        }
+        return true;
+    }
+    /** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
+    constexpr bool IsSubsetOf(const MultiIntBitSet& a) const noexcept
+    {
+        for (unsigned i = 0; i < N; ++i) {
+            if (m_val[i] & ~a.m_val[i]) return false;
+        }
+        return true;
+    }
+    /** Check if bitset a and bitset b are identical. */
+    friend constexpr bool operator==(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept = default;
+    /** Swap two bitsets. */
+    friend constexpr void swap(MultiIntBitSet& a, MultiIntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
+};
+
+} // namespace bitset_detail
+
+// BitSet dispatches to IntBitSet or MultiIntBitSet as appropriate for the requested minimum number
+// of bits. Use IntBitSet up to 32-bit, or up to 64-bit on 64-bit platforms; above that, use a
+// MultiIntBitSet of size_t.
+template<unsigned BITS>
+using BitSet = std::conditional_t<(BITS <= 32), bitset_detail::IntBitSet<uint32_t>,
+               std::conditional_t<(BITS <= std::numeric_limits<size_t>::digits), bitset_detail::IntBitSet<size_t>,
+               bitset_detail::MultiIntBitSet<size_t, (BITS + std::numeric_limits<size_t>::digits - 1) / std::numeric_limits<size_t>::digits>>>;
+
+#endif // BITCOIN_UTIL_BITSET_H