util: add BitSet #30160

sipa commented at 3:42 PM on May 23, 2024: member

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.

DrahtBot commented at 3:42 PM on May 23, 2024: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	instagibbs, cbergqvist, theStack, achow101
Concept ACK	hebasto

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#30126 (Low-level cluster linearization code by sipa)
#29625 (Several randomness improvements by sipa)
#28676 ([WIP] Cluster mempool implementation by sdaftuar)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label Utils/log/libs on May 23, 2024

sipa force-pushed on May 23, 2024

in src/util/bitset.h:144 in a12b4052da outdated

 139 | +    /** Compute the number of 1 bits in the bitset. */
 140 | +    constexpr unsigned Count() const noexcept { return PopCount(m_val); }
 141 | +    /** Return the number of bits that this object holds. */
 142 | +    static constexpr unsigned Size() noexcept { return MAX_SIZE; }
 143 | +    /** Set a bit to 1. */
 144 | +    constexpr void Set(unsigned pos) noexcept { m_val |= I{1U} << pos; }

theuni commented at 7:55 PM on May 23, 2024:

std::bitset throws for these if pos is out of range.

Maybe add Assume()s? Or were you trying to keep the header self-contained?

sipa commented at 3:37 PM on May 24, 2024:

Done.

in src/util/bitset.h:172 in a12b4052da outdated

 167 | +    /** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
 168 | +    constexpr IntBitSet& operator/=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; }
 169 | +    /** Set this object's bits to be the binary XOR between respective bits from this as a. */
 170 | +    constexpr IntBitSet& operator^=(const IntBitSet& a) noexcept { m_val ^= a.m_val; return *this; }
 171 | +    /** Check if the intersection between two sets is non-empty. */
 172 | +    friend constexpr bool operator&&(const IntBitSet& a, const IntBitSet& b) noexcept { return a.m_val & b.m_val; }

theuni commented at 8:03 PM on May 23, 2024:

I know you like dense code, but...

I suspect function names would make reviewing uses of this easier than operators. Especially for the non-obvious ones like && that std::bitset doesn't support.

I know that personally I'd have an easier time reviewing a.intersects(b).

sipa commented at 3:37 PM on May 24, 2024:

Replaced with Overlaps().

in src/util/bitset.h:525 in aeef8a4dcf outdated

 456 | +// BitSet dispatches to IntBitSet or MultiIntBitSet as appropriate for the requested minimum number
 457 | +// of bits.
 458 | +template<unsigned BITS>
 459 | +using BitSet = std::conditional_t<(BITS <= 32), bitset_detail::IntBitSet<uint32_t>,
 460 | +               std::conditional_t<(BITS <= std::numeric_limits<size_t>::digits), bitset_detail::IntBitSet<size_t>,
 461 | +               bitset_detail::MultiIntBitSet<size_t, (BITS + std::numeric_limits<size_t>::digits - 1) / std::numeric_limits<size_t>::digits>>>;

cbergqvist commented at 8:44 AM on May 24, 2024:

Have you considered using __int128, __int256 etc when available, before falling back to MultiIntBitSet? Maybe something for a follow-up PR.

sipa commented at 12:21 PM on May 28, 2024:

I have not benchmarked this, but I have a hard time imagining how that can be faster, as common hardware doesn't have general-purpose registers bigger than size_t, so __int128 operations get simulated using multiple variables anyway. Some architectures do have vector extensions (SSE, AVX, ...) which introduce native 128-, 256-, or 512-bit registers, but those generally only support operations of units up to 32 to 64 bits in them (including leading-zero counting, or popcount, which we need here).

cbergqvist commented at 12:50 PM on May 28, 2024:

I'd consider SSE supporting CPUs quite common. Seems like using such instructions can offer efficiency gains but are sufficiently complex to write papers about - https://stackoverflow.com/a/42675620, something for the future maybe.

in src/util/bitset.h:372 in aeef8a4dcf outdated

 304 | +            unsigned i = 0;
 305 | +            while (count > LIMB_BITS) {
 306 | +                ret.m_val[i++] = ~I{0};
 307 | +                count -= LIMB_BITS;
 308 | +            }
 309 | +            ret.m_val[i] = I(~I{0}) >> (LIMB_BITS - count);

cbergqvist commented at 10:05 AM on May 24, 2024:

nit: Superfluous I()

sipa commented at 12:25 PM on May 28, 2024:

I don't believe this is superfluous. If I is smaller than an int (e.g. I = uint16_t) then ~I{0} undergoes integer promotion to int, and right-shifting that would sign-extend, which would incorrect here. The I(...) around it forces it to be unsigned before the right-shift.

cbergqvist commented at 12:41 PM on May 29, 2024:

Added std::conditional_t<(BITS <= 16), bitset_detail::IntBitSet<uint16_t>, ... and removed the I(), wrote unit test in bc36241f5a0a23d16645155eb819e94b0db2813e, and it indeed proves you are correct. Right now it cannot occur since IntBitSet<uint32_t> is the smallest we go, but better not to leave loaded footguns lying around.

$ src/test/test_bitcoin -t bitset_tests
...
Running 1 test case...
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [1 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [2 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [3 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [4 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [5 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [6 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [7 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [8 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [9 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [10 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [11 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [12 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [13 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [14 != 16]
test/bitset_tests.cpp(18): error: in "bitset_tests/bitset_test_15": check std::popcount(sim) == set.Count() has failed [15 != 16]

</details>

sipa force-pushed on May 24, 2024

in src/util/bitset.h:212 in 797ea9aca0 outdated

 207 | +    /** Return an object with the binary XOR between respective bits from a and b. */
 208 | +    friend constexpr IntBitSet operator^(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val ^ b.m_val); }
 209 | +    /** Check if bitset a and bitset b are identical. */
 210 | +    friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default;
 211 | +    /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
 212 | +    friend constexpr bool operator>=(const IntBitSet& a, const IntBitSet& b) noexcept { return (b.m_val & ~a.m_val) == 0; }

theuni commented at 2:17 PM on May 24, 2024:

.Subset() and .Superset()?

Without these comments, I would have to guess at the meanings (and I would have guessed wrong).

sipa commented at 3:38 PM on May 24, 2024:

Replaced with IsSubsetOf() and IsSupersetOf().

sipa force-pushed on May 24, 2024

sipa force-pushed on May 25, 2024

hebasto added the label Needs CMake port on May 27, 2024

in src/util/bitset.h:393 in beb535680b outdated

 388 | +    IteratorEnd constexpr end() const noexcept { return IteratorEnd(); }
 389 | +    /** Find the first element (requires Any()). */
 390 | +    unsigned constexpr First() const noexcept
 391 | +    {
 392 | +        unsigned p = 0;
 393 | +        while (m_val[p] == 0) ++p;

theStack commented at 11:01 AM on May 28, 2024:

It's a bit scary that MultiIntBitSet::{First,Last} lead to buffer over/under-reads if no bit is set. I understand that we wouldn't want to do assert for Any in production for performance reasons, but it's maybe worth it do it for debug builds, e.g. with somethink like the ASSERT_IF_DEBUG construct used in src/span.h.

sipa commented at 12:39 PM on May 28, 2024:

I've added Assume()s in First() and Last() to avoid this.

in src/util/bitset.h:247 in 3bc131a85c outdated

 242 | +        friend class MultiIntBitSet;
 243 | +        const std::array<I, N>* m_ptr; /**< Pointer to array to fetch bits from. */
 244 | +        I m_val; /**< The remaining bits of (*m_ptr)[m_idx]. */
 245 | +        unsigned m_pos; /**< The last reported position. */
 246 | +        unsigned m_idx; /**< The index in *m_ptr currently being iterated over. */
 247 | +        constexpr Iterator(const std::array<I, N>* ptr) noexcept : m_ptr(ptr), m_idx(0)

cbergqvist commented at 11:13 AM on May 28, 2024:

nit: ptr could be passed as a reference to signify non-nullness. (But the member still needs to be a pointer). Not at all significant as it is a private function.

sipa commented at 12:39 PM on May 28, 2024:

Done.

cbergqvist commented at 11:52 AM on May 28, 2024: contributor

Looked at 3bc131a85ce826aa171f0328c014ea51b8740fed

Concept: Bummer that std::countr_zero and std::countl_zero aren't implemented for std::bitset. And for iterating it seems like one would be using std::vector<bool> and hoping for the best in terms of implementation. So makes sense to introduce BitSet.

Summary still mentions operator/ instead of operator-.

(Fuzz-code is too new to me to comment).

theStack commented at 12:20 PM on May 28, 2024: contributor

Concept ACK

sipa force-pushed on May 28, 2024

sipa force-pushed on May 29, 2024

sipa commented at 3:46 PM on May 29, 2024: member

Added additional Assume()s to prevent operator++ on iterators past the end:

--- a/src/util/bitset.h
+++ b/src/util/bitset.h
@@ -101,6 +101,7 @@ class IntBitSet
         /** 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;
@@ -272,6 +273,7 @@ class MultiIntBitSet
         /** 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) {

in src/test/fuzz/bitset.cpp:32 in 18ec3fc0bd outdated

  23 | +
  24 | +/** Perform a simulation fuzz test on BitSet type S. */
  25 | +template<typename S>
  26 | +void TestType(Span<const uint8_t> buffer)
  27 | +{
  28 | +    XoRoShiRo128PlusPlus rng(buffer.size() + 0x10000 * S::Size());

instagibbs commented at 3:30 PM on May 30, 2024:

can you motivate this seed in a comment?

sipa commented at 3:57 PM on June 4, 2024:

Done, let me know if this is better.

instagibbs commented at 1:38 PM on June 5, 2024:

perfect thanks

in src/test/fuzz/bitset.cpp:78 in 18ec3fc0bd outdated

  67 | +    LIMITED_WHILE(buffer.size() > 0, 1000) {
  68 | +        int command = ReadByte(buffer) % 64;
  69 | +        unsigned args = ReadByte(buffer);
  70 | +        unsigned dest = ((args & 7) * sim.size()) >> 3;
  71 | +        unsigned src = (((args >> 3) & 7) * sim.size()) >> 3;
  72 | +        unsigned aux = (((args >> 6) & 3) * sim.size()) >> 2;

instagibbs commented at 4:41 PM on May 30, 2024:

If this is true, this helps my understanding of the code to follow, knowing that each loop below will eventually terminate.

        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()));

sipa commented at 3:57 PM on June 4, 2024:

Added.

in src/util/bitset.h:192 in a1a0c4c2bc outdated

 185 | +    constexpr Iterator begin() const noexcept { return Iterator(m_val); }
 186 | +    /** Return a dummy object to compare Iterators with. */
 187 | +    constexpr IteratorEnd end() const noexcept { return IteratorEnd(); }
 188 | +    /** Find the first element (requires Any()). */
 189 | +    constexpr unsigned First() const noexcept { return std::countr_zero(m_val); }
 190 | +    /** Find the last element (requires Any()). */

instagibbs commented at 6:40 PM on May 30, 2024:

Could we add Assume()/Assert()s rather than comments here and above?

sipa commented at 3:57 PM on June 4, 2024:

Done.

in src/util/bitset.h:38 in a1a0c4c2bc outdated

  33 | +
  34 | +namespace bitset_detail {
  35 | +
  36 | +/** Count the number of bits set in an unsigned integer type. */
  37 | +template<typename I>
  38 | +unsigned inline constexpr PopCount(I v)

instagibbs commented at 7:30 PM on June 3, 2024:

did you consider using std::popcount instead?

sipa commented at 3:58 PM on June 4, 2024:

Yes; but on GCC/stdlibc++, std::popcount just uses __builtin_popcount, which in benchmarks seems to perform worse than the code here. The I've updated the comment to reflect that (it was written before the C++20 switch which introduced std::popcount).

instagibbs commented at 3:59 PM on June 4, 2024:

figured as much based on my investigation thanks

in src/test/fuzz/bitset.cpp:73 in 18ec3fc0bd outdated

  68 | +        int command = ReadByte(buffer) % 64;
  69 | +        unsigned args = ReadByte(buffer);
  70 | +        unsigned dest = ((args & 7) * sim.size()) >> 3;
  71 | +        unsigned src = (((args >> 3) & 7) * sim.size()) >> 3;
  72 | +        unsigned aux = (((args >> 6) & 3) * sim.size()) >> 2;
  73 | +        // Loop until command reaches 0. This way, every iteration will cause one operation

instagibbs commented at 2:49 PM on June 4, 2024:

I like the comment in the VecDeque PR better if you'd care to just copy it here: https://github.com/bitcoin/bitcoin/pull/30161/commits/ecb278bb19c53b007380e262fa86d809255eeb49#diff-1f28310f089eac74210ecbc0db2083279282ade962dc464bd31448480dc5563dR59

sipa commented at 3:58 PM on June 4, 2024:

Done. Credit to @glozow.

hebasto commented at 2:54 PM on June 4, 2024: member

Concept ACK.

sipa force-pushed on Jun 4, 2024

instagibbs commented at 5:19 PM on June 4, 2024: member

concept ACK

requested changes were included, will continue review

git range-diff master 18ec3fc c99063e

in src/util/bitset.h:65 in c99063e902 outdated

  60 | +/** A bitset implementation backed by a single integer of type I. */
  61 | +template<typename I>
  62 | +class IntBitSet
  63 | +{
  64 | +    // Only binary, unsigned, integer, types allowed.
  65 | +    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);

cbergqvist commented at 7:21 PM on June 6, 2024:

Why not use the ability to put the descriptions inside the static_assert()s here and elsewhere?

    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2,
        "Only binary, unsigned, integer, types allowed.");

sipa commented at 7:34 PM on June 6, 2024:

I think the condition is sufficiently self-descriptive that this isn't really needed (the compiler error emitted will report the line causing it anyway). And I still like to have a comment on all top-level statements/definitions inside a class, even if it's trivial, just for organization purposes.

cbergqvist approved

cbergqvist commented at 7:29 PM on June 6, 2024: contributor

ACK c99063e902c810dde1742696b3140610120d391c

(Ran git range-diff 3bc131a~2..3bc131a c99063e~2..c99063e).

DrahtBot requested review from instagibbs on Jun 6, 2024

DrahtBot requested review from theStack on Jun 6, 2024

DrahtBot requested review from hebasto on Jun 6, 2024

in src/util/bitset.h:128 in 9aff4cb944 outdated

 123 | +            m_val |= I{1U} << i;
 124 | +        }
 125 | +    }
 126 | +    /** Copy assign a bitset. */
 127 | +    constexpr IntBitSet& operator=(const IntBitSet&) noexcept = default;
 128 | +    /** Assign a list of values. */

instagibbs commented at 2:49 PM on June 7, 2024:

    /** Assign from a list of positional values. */

sipa commented at 5:13 PM on June 7, 2024:

Done.

in src/test/fuzz/bitset.cpp:62 in c99063e902 outdated

  57 | +        assert(it == real[idx].end());
  58 | +        assert(!(it != real[idx].end()));
  59 | +        /* Any / None */
  60 | +        assert(sim[idx].any() == real[idx].Any());
  61 | +        assert(sim[idx].none() == real[idx].None());
  62 | +        /* First */

instagibbs commented at 3:17 PM on June 7, 2024:

        /* First / Last */

sipa commented at 5:13 PM on June 7, 2024:

Done.

in src/util/bitset.h:223 in 9aff4cb944 outdated

 220 | +    /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
 221 | +    constexpr bool IsSupersetOf(const IntBitSet& a) const noexcept { return (a.m_val & ~m_val) == 0; }
 222 | +    /** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
 223 | +    constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
 224 | +    /** Swap two bitsets. */
 225 | +    friend constexpr void swap(IntBitSet& a, IntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }

instagibbs commented at 3:37 PM on June 7, 2024:

lacks coverage?

my local coverage generation is kinda screwed up, but fuzz coverage should be computed :pray:

sipa commented at 5:13 PM on June 7, 2024:

Added coverage for the swap function in the fuzz test.

in src/util/bitset.h:134 in 9aff4cb944 outdated

 129 | +    constexpr IntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
 130 | +    {
 131 | +        m_val = 0;
 132 | +        for (auto i : ilist) {
 133 | +            Assume(i < MAX_SIZE);
 134 | +            m_val |= I{1U} << i;

instagibbs commented at 3:46 PM on June 7, 2024:

Set(i)?

sipa commented at 5:13 PM on June 7, 2024:

Done.

in src/util/bitset.h:123 in 9aff4cb944 outdated

 118 | +    /** Construct from a list of values. */
 119 | +    constexpr IntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val(0)
 120 | +    {
 121 | +        for (auto i : ilist) {
 122 | +            Assume(i < MAX_SIZE);
 123 | +            m_val |= I{1U} << i;

instagibbs commented at 3:46 PM on June 7, 2024:

Set(i)

sipa commented at 5:13 PM on June 7, 2024:

Done.

in src/util/bitset.h:166 in 9aff4cb944 outdated

 163 | +    }
 164 | +    /** Set a bit to 0. */
 165 | +    constexpr void Reset(unsigned pos) noexcept
 166 | +    {
 167 | +        Assume(pos < MAX_SIZE);
 168 | +        m_val &= ~I(I{1U} << pos);

instagibbs commented at 3:49 PM on June 7, 2024:

maybe just use conditional Set?

sipa commented at 5:02 PM on June 7, 2024:

I haven't benchmarked or investigated compiled code, but I want to give the compiler every opportunity to use the simpler operation here (the conditional Set is more complex, and inlining will hopefully strength-reduce it, but I prefer not counting on that).

in src/util/bitset.h:342 in 9aff4cb944 outdated

 333 | +        m_val.fill(0);
 334 | +        for (auto i : ilist) Set(i);
 335 | +        return *this;
 336 | +    }
 337 | +    /** Set a bit to 0. */
 338 | +    void constexpr Reset(unsigned pos) noexcept

instagibbs commented at 3:49 PM on June 7, 2024:

maybe just use conditional Set?

sipa commented at 5:14 PM on June 7, 2024:

Same reasoning as here

in src/util/bitset.h:350 in 9aff4cb944 outdated

 345 | +    {
 346 | +        Assume(pos < MAX_SIZE);
 347 | +        return (m_val[pos / LIMB_BITS] >> (pos % LIMB_BITS)) & 1U;
 348 | +    }
 349 | +    /** Construct a bitset with the singleton i. */
 350 | +    static constexpr MultiIntBitSet Singleton(unsigned i) noexcept

instagibbs commented at 3:50 PM on June 7, 2024:

stick with pos for arg names?

sipa commented at 5:14 PM on June 7, 2024:

Done.

in src/util/bitset.h:390 in 9aff4cb944 outdated

 385 | +            if (v != 0) return false;
 386 | +        }
 387 | +        return true;
 388 | +    }
 389 | +    /** Check if any bits are 1. */
 390 | +    bool constexpr Any() const noexcept

instagibbs commented at 3:53 PM on June 7, 2024:

just check !None()?

sipa commented at 5:14 PM on June 7, 2024:

Done.

instagibbs changes_requested

instagibbs commented at 4:07 PM on June 7, 2024: member

c99063e902c810dde1742696b3140610120d391c seems to need swap fuzz coverage

rest of comments are nits

DrahtBot requested review from instagibbs on Jun 7, 2024

sipa force-pushed on Jun 7, 2024

in src/util/bitset.h:110 in 1e08ba37e7 outdated

 105 | +            m_val &= m_val - I{1U};
 106 | +            if (m_val != 0) m_pos = std::countr_zero(m_val);
 107 | +            return *this;
 108 | +        }
 109 | +        /** Get the current bit position (only if != IteratorEnd). */
 110 | +        constexpr const unsigned& operator*() const noexcept { return m_pos; }

theStack commented at 12:06 AM on June 10, 2024:

nit: same as done in operator++, could add Assume(m_val != 0) here as well (both for IntBitSet and MultiIntBitSet iterators)

sipa commented at 11:55 AM on June 10, 2024:

Done.

theStack commented at 12:15 AM on June 10, 2024: contributor

Reviewed 1e08ba37e7b5d9b083c938d90526f8fabbe1c799 so far, the code looks correct to me. Planning to review and run the fuzz test tomorrow.

util: add BitSet

This adds a bitset module that implements a BitSet<N> class, a variant
of std::bitset with a few additional features that cannot be implemented
in a wrapper without performance loss (specifically, finding first and
last bit set, or iterating over all set bits).

59a6df6bd5

tests: add fuzz tests for BitSet 47f705b33f

sipa force-pushed on Jun 10, 2024

sipa commented at 11:56 AM on June 10, 2024: member

Made a few small changes still:

@@ -107,7 +107,11 @@ class IntBitSet
             return *this;
         }
         /** Get the current bit position (only if != IteratorEnd). */
-        constexpr const unsigned& operator*() const noexcept { return m_pos; }
+        constexpr unsigned operator*() const noexcept
+        {
+            Assume(m_val != 0);
+            return m_pos;
+        }
     };
 
 public:
@@ -231,6 +235,8 @@ class MultiIntBitSet
     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. */
@@ -293,7 +299,11 @@ class MultiIntBitSet
             return *this;
         }
         /** Get the current bit position (only if != IteratorEnd). */
-        constexpr const unsigned& operator*() const noexcept { return m_pos; }
+        constexpr unsigned operator*() const noexcept
+        {
+            Assume(m_idx < N);
+            return m_pos;
+        }
     };
 
 public:

instagibbs commented at 1:26 PM on June 10, 2024: member

ACK https://github.com/bitcoin/bitcoin/pull/30160/commits/47f705b33fc1381d96c99038e2110e6fe2b2f883

swap coverage added, some of the nits taken, and a couple Assume()s added

reviewed via git range-diff master c99063e 47f705b

DrahtBot requested review from cbergqvist on Jun 10, 2024

DrahtBot requested review from theStack on Jun 10, 2024

cbergqvist approved

cbergqvist commented at 1:44 PM on June 10, 2024: contributor

re-ACK 47f705b33fc1381d96c99038e2110e6fe2b2f883

Used same range-diff as instagibbs.

theStack approved

theStack commented at 4:12 PM on June 10, 2024: contributor

Code-review ACK 47f705b33fc1381d96c99038e2110e6fe2b2f883

achow101 commented at 9:18 PM on June 11, 2024: member

ACK 47f705b33fc1381d96c99038e2110e6fe2b2f883

achow101 merged this on Jun 11, 2024

achow101 closed this on Jun 11, 2024

hebasto commented at 6:55 AM on July 14, 2024: member

Ported to the CMake-based build system in https://github.com/hebasto/bitcoin/pull/264.

hebasto removed the label Needs CMake port on Jul 14, 2024

bitcoin locked this on Jul 14, 2025