1// Copyright (c) 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#ifndef BITCOIN_UTIL_BITSET_H
6#define BITCOIN_UTIL_BITSET_H
7
8#include <util/check.h>
9#include <util/overflow.h>
10
11#include <array>
12#include <bit>
13#include <cstdint>
14#include <limits>
15#include <type_traits>
16
17/* This file provides data types similar to std::bitset, but adds the following functionality:
18 *
19 * - Efficient iteration over all set bits (compatible with range-based for loops).
20 * - Efficient search for the first and last set bit (First() and Last()).
21 * - Efficient set subtraction: (a - b) implements "a and not b".
22 * - Efficient non-strict subset/superset testing: IsSubsetOf() and IsSupersetOf().
23 * - Efficient set overlap testing: a.Overlaps(b)
24 * - Efficient construction of set containing 0..N-1 (S::Fill).
25 * - Efficient construction of a single set (S::Singleton).
26 * - Construction from initializer lists.
27 *
28 * Other differences:
29 * - BitSet<N> is a bitset that supports at least N elements, but may support more (Size() reports
30 *   the actual number). Because the actual number is unpredictable, there are no operations that
31 *   affect all positions (like std::bitset's operator~, flip(), or all()).
32 * - Various other unimplemented features.
33 */
34
35namespace bitset_detail {
36
37/** Count the number of bits set in an unsigned integer type. */
38template<typename I>
39unsigned inline constexpr PopCount(I v)
40{
41    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
42    constexpr auto BITS = std::numeric_limits<I>::digits;
43    // Algorithms from https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation.
44    // These seem to be faster than std::popcount when compiling for non-SSE4 on x86_64.
45    if constexpr (BITS <= 32) {
46        v -= (v >> 1) & 0x55555555;
47        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
48        v = (v + (v >> 4)) & 0x0f0f0f0f;
49        if constexpr (BITS > 8) v += v >> 8;
50        if constexpr (BITS > 16) v += v >> 16;
51        return v & 0x3f;
52    } else {
53        static_assert(BITS <= 64);
54        v -= (v >> 1) & 0x5555555555555555;
55        v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
56        v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f;
57        return (v * uint64_t{0x0101010101010101}) >> 56;
58    }
59}
60
61/** A bitset implementation backed by a single integer of type I. */
62template<typename I>
63class IntBitSet
64{
65    // Only binary, unsigned, integer, types allowed.
66    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
67    /** The maximum number of bits this bitset supports. */
68    static constexpr unsigned MAX_SIZE = std::numeric_limits<I>::digits;
69    /** Integer whose bits represent this bitset. */
70    I m_val;
71    /** Internal constructor with a given integer as contents. */
72    IntBitSet(I val) noexcept : m_val{val} {}
73    /** Dummy type to return using end(). Only used for comparing with Iterator. */
74    class IteratorEnd
75    {
76        friend class IntBitSet;
77        constexpr IteratorEnd() = default;
78    public:
79        constexpr IteratorEnd(const IteratorEnd&) = default;
80    };
81    /** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
82    class Iterator
83    {
84        friend class IntBitSet;
85        I m_val; /**< The original integer's remaining bits. */
86        unsigned m_pos; /** Last reported 1 position (if m_pos != 0). */
87        constexpr Iterator(I val) noexcept : m_val(val), m_pos(0)
88        {
89            if (m_val != 0) m_pos = std::countr_zero(m_val);
90        }
91    public:
92        /** Do not allow external code to construct an Iterator. */
93        Iterator() = delete;
94        // Copying is allowed.
95        constexpr Iterator(const Iterator&) noexcept = default;
96        constexpr Iterator& operator=(const Iterator&) noexcept = default;
97        /** Test whether we are done (can only compare with IteratorEnd). */
98        constexpr friend bool operator==(const Iterator& a, const IteratorEnd&) noexcept
99        {
100            return a.m_val == 0;
101        }
102        /** Progress to the next 1 bit (only if != IteratorEnd). */
103        constexpr Iterator& operator++() noexcept
104        {
105            Assume(m_val != 0);
106            m_val &= m_val - I{1U};
107            if (m_val != 0) m_pos = std::countr_zero(m_val);
108            return *this;
109        }
110        /** Get the current bit position (only if != IteratorEnd). */
111        constexpr unsigned operator*() const noexcept
112        {
113            Assume(m_val != 0);
114            return m_pos;
115        }
116    };
117
118public:
119    /** Construct an all-zero bitset. */
120    constexpr IntBitSet() noexcept : m_val{0} {}
121    /** Copy construct a bitset. */
122    constexpr IntBitSet(const IntBitSet&) noexcept = default;
123    /** Construct from a list of values. */
124    constexpr IntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val(0)
125    {
126        for (auto pos : ilist) Set(pos);
127    }
128    /** Copy assign a bitset. */
129    constexpr IntBitSet& operator=(const IntBitSet&) noexcept = default;
130    /** Assign from a list of positions (which will be made true, all others false). */
131    constexpr IntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
132    {
133        m_val = 0;
134        for (auto pos : ilist) Set(pos);
135        return *this;
136    }
137    /** Construct a bitset with the singleton i. */
138    static constexpr IntBitSet Singleton(unsigned i) noexcept
139    {
140        Assume(i < MAX_SIZE);
141        return IntBitSet(I(1U) << i);
142    }
143    /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
144    static constexpr IntBitSet Fill(unsigned count) noexcept
145    {
146        IntBitSet ret;
147        Assume(count <= MAX_SIZE);
148        if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count);
149        return ret;
150    }
151    /** Set a bit to 1. */
152    constexpr void Set(unsigned pos) noexcept
153    {
154        Assume(pos < MAX_SIZE);
155        m_val |= I{1U} << pos;
156    }
157    /** Set a bit to the specified value. */
158    constexpr void Set(unsigned pos, bool val) noexcept
159    {
160        Assume(pos < MAX_SIZE);
161        m_val = (m_val & ~I(I{1U} << pos)) | (I(val) << pos);
162    }
163    /** Set a bit to 0. */
164    constexpr void Reset(unsigned pos) noexcept
165    {
166        Assume(pos < MAX_SIZE);
167        m_val &= ~I(I{1U} << pos);
168    }
169    /** Retrieve a bit at the given position. */
170    constexpr bool operator[](unsigned pos) const noexcept
171    {
172        Assume(pos < MAX_SIZE);
173        return (m_val >> pos) & 1U;
174    }
175    /** Compute the number of 1 bits in the bitset. */
176    constexpr unsigned Count() const noexcept { return PopCount(m_val); }
177    /** Return the number of bits that this object holds. */
178    static constexpr unsigned Size() noexcept { return MAX_SIZE; }
179    /** Check if all bits are 0. */
180    constexpr bool None() const noexcept { return m_val == 0; }
181    /** Check if any bits are 1. */
182    constexpr bool Any() const noexcept { return !None(); }
183    /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
184    constexpr Iterator begin() const noexcept { return Iterator(m_val); }
185    /** Return a dummy object to compare Iterators with. */
186    constexpr IteratorEnd end() const noexcept { return IteratorEnd(); }
187    /** Find the first element (requires Any()). */
188    constexpr unsigned First() const noexcept
189    {
190        Assume(m_val != 0);
191        return std::countr_zero(m_val);
192    }
193    /** Find the last element (requires Any()). */
194    constexpr unsigned Last() const noexcept
195    {
196        Assume(m_val != 0);
197        return std::bit_width(m_val) - 1;
198    }
199    /** Set this object's bits to be the binary AND between respective bits from this and a. */
200    constexpr IntBitSet& operator|=(const IntBitSet& a) noexcept { m_val |= a.m_val; return *this; }
201    /** Set this object's bits to be the binary OR between respective bits from this and a. */
202    constexpr IntBitSet& operator&=(const IntBitSet& a) noexcept { m_val &= a.m_val; return *this; }
203    /** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
204    constexpr IntBitSet& operator-=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; }
205    /** Set this object's bits to be the binary XOR between respective bits from this as a. */
206    constexpr IntBitSet& operator^=(const IntBitSet& a) noexcept { m_val ^= a.m_val; return *this; }
207    /** Check if the intersection between two sets is non-empty. */
208    constexpr bool Overlaps(const IntBitSet& a) const noexcept { return m_val & a.m_val; }
209    /** Return an object with the binary AND between respective bits from a and b. */
210    friend constexpr IntBitSet operator&(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & b.m_val); }
211    /** Return an object with the binary OR between respective bits from a and b. */
212    friend constexpr IntBitSet operator|(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val | b.m_val); }
213    /** Return an object with the binary AND NOT between respective bits from a and b. */
214    friend constexpr IntBitSet operator-(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & ~b.m_val); }
215    /** Return an object with the binary XOR between respective bits from a and b. */
216    friend constexpr IntBitSet operator^(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val ^ b.m_val); }
217    /** Check if bitset a and bitset b are identical. */
218    friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default;
219    /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
220    constexpr bool IsSupersetOf(const IntBitSet& a) const noexcept { return (a.m_val & ~m_val) == 0; }
221    /** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
222    constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
223    /** Swap two bitsets. */
224    friend constexpr void swap(IntBitSet& a, IntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
225};
226
227/** A bitset implementation backed by N integers of type I. */
228template<typename I, unsigned N>
229class MultiIntBitSet
230{
231    // Only binary, unsigned, integer, types allowed.
232    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
233    // Cannot be empty.
234    static_assert(N > 0);
235    /** The number of bits per integer. */
236    static constexpr unsigned LIMB_BITS = std::numeric_limits<I>::digits;
237    /** Number of elements this set type supports. */
238    static constexpr unsigned MAX_SIZE = LIMB_BITS * N;
239    // No overflow allowed here.
240    static_assert(MAX_SIZE / LIMB_BITS == N);
241    /** Array whose member integers store the bits of the set. */
242    std::array<I, N> m_val;
243    /** Dummy type to return using end(). Only used for comparing with Iterator. */
244    class IteratorEnd
245    {
246        friend class MultiIntBitSet;
247        constexpr IteratorEnd() = default;
248    public:
249        constexpr IteratorEnd(const IteratorEnd&) = default;
250    };