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

1 files changed, 316 insertions, 0 deletions

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);
+    }
+}