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 35 namespace bitset_detail {
36 37 /** Count the number of bits set in an unsigned integer type. */
38 template<typename I>
39 unsigned 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. */
62 template<typename I>
63 class 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 118 public:
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. */
228 template<typename I, unsigned N>
229 class 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 };
251 /** Iterator type returned by begin(), which efficiently iterates all 1 positions. */
252 class Iterator
253 {
254 friend class MultiIntBitSet;
255 const std::array<I, N>* m_ptr; /**< Pointer to array to fetch bits from. */
256 I m_val; /**< The remaining bits of (*m_ptr)[m_idx]. */
257 unsigned m_pos; /**< The last reported position. */
258 unsigned m_idx; /**< The index in *m_ptr currently being iterated over. */
259 constexpr Iterator(const std::array<I, N>& ref) noexcept : m_ptr(&ref), m_idx(0)
260 {
261 do {
262 m_val = (*m_ptr)[m_idx];
263 if (m_val) {
264 m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
265 break;
266 }
267 ++m_idx;
268 } while(m_idx < N);
269 }
270 271 public:
272 /** Do not allow external code to construct an Iterator. */
273 Iterator() = delete;
274 // Copying is allowed.
275 constexpr Iterator(const Iterator&) noexcept = default;
276 constexpr Iterator& operator=(const Iterator&) noexcept = default;
277 /** Test whether we are done (can only compare with IteratorEnd). */
278 friend constexpr bool operator==(const Iterator& a, const IteratorEnd&) noexcept
279 {
280 return a.m_idx == N;
281 }
282 /** Progress to the next 1 bit (only if != IteratorEnd). */
283 constexpr Iterator& operator++() noexcept
284 {
285 Assume(m_idx < N);
286 m_val &= m_val - I{1U};
287 if (m_val == 0) {
288 while (true) {
289 ++m_idx;
290 if (m_idx == N) break;
291 m_val = (*m_ptr)[m_idx];
292 if (m_val) {
293 m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
294 break;
295 }
296 }
297 } else {
298 m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS;
299 }
300 return *this;
301 }
302 /** Get the current bit position (only if != IteratorEnd). */
303 constexpr unsigned operator*() const noexcept
304 {
305 Assume(m_idx < N);
306 return m_pos;
307 }
308 };
309 310 public:
311 /** Construct an all-zero bitset. */
312 constexpr MultiIntBitSet() noexcept : m_val{} {}
313 /** Copy construct a bitset. */
314 constexpr MultiIntBitSet(const MultiIntBitSet&) noexcept = default;
315 /** Copy assign a bitset. */
316 constexpr MultiIntBitSet& operator=(const MultiIntBitSet&) noexcept = default;
317 /** Set a bit to 1. */
318 void constexpr Set(unsigned pos) noexcept
319 {
320 Assume(pos < MAX_SIZE);
321 m_val[pos / LIMB_BITS] |= I{1U} << (pos % LIMB_BITS);
322 }
323 /** Set a bit to the specified value. */
324 void constexpr Set(unsigned pos, bool val) noexcept
325 {
326 Assume(pos < MAX_SIZE);
327 m_val[pos / LIMB_BITS] = (m_val[pos / LIMB_BITS] & ~I(I{1U} << (pos % LIMB_BITS))) |
328 (I{val} << (pos % LIMB_BITS));
329 }
330 /** Construct a bitset from a list of values. */
331 constexpr MultiIntBitSet(std::initializer_list<unsigned> ilist) noexcept : m_val{}
332 {
333 for (auto pos : ilist) Set(pos);
334 }
335 /** Set a bitset to a list of values. */
336 constexpr MultiIntBitSet& operator=(std::initializer_list<unsigned> ilist) noexcept
337 {
338 m_val.fill(0);
339 for (auto pos : ilist) Set(pos);
340 return *this;
341 }
342 /** Set a bit to 0. */
343 void constexpr Reset(unsigned pos) noexcept
344 {
345 Assume(pos < MAX_SIZE);
346 m_val[pos / LIMB_BITS] &= ~I(I{1U} << (pos % LIMB_BITS));
347 }
348 /** Retrieve a bit at the given position. */
349 bool constexpr operator[](unsigned pos) const noexcept
350 {
351 Assume(pos < MAX_SIZE);
352 return (m_val[pos / LIMB_BITS] >> (pos % LIMB_BITS)) & 1U;
353 }
354 /** Construct a bitset with the singleton pos. */
355 static constexpr MultiIntBitSet Singleton(unsigned pos) noexcept
356 {
357 Assume(pos < MAX_SIZE);
358 MultiIntBitSet ret;
359 ret.m_val[pos / LIMB_BITS] = I{1U} << (pos % LIMB_BITS);
360 return ret;
361 }
362 /** Construct a bitset with bits 0..count-1 (inclusive) set to 1. */
363 static constexpr MultiIntBitSet Fill(unsigned count) noexcept
364 {
365 Assume(count <= MAX_SIZE);
366 MultiIntBitSet ret;
367 if (count) {
368 unsigned i = 0;
369 while (count > LIMB_BITS) {
370 ret.m_val[i++] = I(~I{0});
371 count -= LIMB_BITS;
372 }
373 ret.m_val[i] = I(~I{0}) >> (LIMB_BITS - count);
374 }
375 return ret;
376 }
377 /** Return the number of bits that this object holds. */
378 static constexpr unsigned Size() noexcept { return MAX_SIZE; }
379 /** Compute the number of 1 bits in the bitset. */
380 unsigned constexpr Count() const noexcept
381 {
382 unsigned ret{0};
383 for (I v : m_val) ret += PopCount(v);
384 return ret;
385 }
386 /** Check if all bits are 0. */
387 bool constexpr None() const noexcept
388 {
389 for (auto v : m_val) {
390 if (v != 0) return false;
391 }
392 return true;
393 }
394 /** Check if any bits are 1. */
395 bool constexpr Any() const noexcept { return !None(); }
396 /** Return an object that iterates over all 1 bits (++ and * only allowed when != end()). */
397 Iterator constexpr begin() const noexcept { return Iterator(m_val); }
398 /** Return a dummy object to compare Iterators with. */
399 IteratorEnd constexpr end() const noexcept { return IteratorEnd(); }
400 /** Find the first element (requires Any()). */
401 unsigned constexpr First() const noexcept
402 {
403 unsigned p = 0;
404 while (m_val[p] == 0) {
405 ++p;
406 Assume(p < N);
407 }
408 return std::countr_zero(m_val[p]) + p * LIMB_BITS;
409 }
410 /** Find the last element (requires Any()). */
411 unsigned constexpr Last() const noexcept
412 {
413 unsigned p = N - 1;
414 while (m_val[p] == 0) {
415 Assume(p > 0);
416 --p;
417 }
418 return std::bit_width(m_val[p]) - 1 + p * LIMB_BITS;
419 }
420 /** Set this object's bits to be the binary OR between respective bits from this and a. */
421 constexpr MultiIntBitSet& operator|=(const MultiIntBitSet& a) noexcept
422 {
423 for (unsigned i = 0; i < N; ++i) {
424 m_val[i] |= a.m_val[i];
425 }
426 return *this;
427 }
428 /** Set this object's bits to be the binary AND between respective bits from this and a. */
429 constexpr MultiIntBitSet& operator&=(const MultiIntBitSet& a) noexcept
430 {
431 for (unsigned i = 0; i < N; ++i) {
432 m_val[i] &= a.m_val[i];
433 }
434 return *this;
435 }
436 /** Set this object's bits to be the binary AND NOT between respective bits from this and a. */
437 constexpr MultiIntBitSet& operator-=(const MultiIntBitSet& a) noexcept
438 {
439 for (unsigned i = 0; i < N; ++i) {
440 m_val[i] &= ~a.m_val[i];
441 }
442 return *this;
443 }
444 /** Set this object's bits to be the binary XOR between respective bits from this and a. */
445 constexpr MultiIntBitSet& operator^=(const MultiIntBitSet& a) noexcept
446 {
447 for (unsigned i = 0; i < N; ++i) {
448 m_val[i] ^= a.m_val[i];
449 }
450 return *this;
451 }
452 /** Check whether the intersection between two sets is non-empty. */
453 constexpr bool Overlaps(const MultiIntBitSet& a) const noexcept
454 {
455 for (unsigned i = 0; i < N; ++i) {
456 if (m_val[i] & a.m_val[i]) return true;
457 }
458 return false;
459 }
460 /** Return an object with the binary AND between respective bits from a and b. */
461 friend constexpr MultiIntBitSet operator&(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
462 {
463 MultiIntBitSet r;
464 for (unsigned i = 0; i < N; ++i) {
465 r.m_val[i] = a.m_val[i] & b.m_val[i];
466 }
467 return r;
468 }
469 /** Return an object with the binary OR between respective bits from a and b. */
470 friend constexpr MultiIntBitSet operator|(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
471 {
472 MultiIntBitSet r;
473 for (unsigned i = 0; i < N; ++i) {
474 r.m_val[i] = a.m_val[i] | b.m_val[i];
475 }
476 return r;
477 }
478 /** Return an object with the binary AND NOT between respective bits from a and b. */
479 friend constexpr MultiIntBitSet operator-(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
480 {
481 MultiIntBitSet r;
482 for (unsigned i = 0; i < N; ++i) {
483 r.m_val[i] = a.m_val[i] & ~b.m_val[i];
484 }
485 return r;
486 }
487 /** Return an object with the binary XOR between respective bits from a and b. */
488 friend constexpr MultiIntBitSet operator^(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept
489 {
490 MultiIntBitSet r;
491 for (unsigned i = 0; i < N; ++i) {
492 r.m_val[i] = a.m_val[i] ^ b.m_val[i];
493 }
494 return r;
495 }
496 /** Check if bitset a is a superset of bitset b (= every 1 bit in b is also in a). */
497 constexpr bool IsSupersetOf(const MultiIntBitSet& a) const noexcept
498 {
499 for (unsigned i = 0; i < N; ++i) {
500 if (a.m_val[i] & ~m_val[i]) return false;
501 }
502 return true;
503 }
504 /** Check if bitset a is a subset of bitset b (= every 1 bit in a is also in b). */
505 constexpr bool IsSubsetOf(const MultiIntBitSet& a) const noexcept
506 {
507 for (unsigned i = 0; i < N; ++i) {
508 if (m_val[i] & ~a.m_val[i]) return false;
509 }
510 return true;
511 }
512 /** Check if bitset a and bitset b are identical. */
513 friend constexpr bool operator==(const MultiIntBitSet& a, const MultiIntBitSet& b) noexcept = default;
514 /** Swap two bitsets. */
515 friend constexpr void swap(MultiIntBitSet& a, MultiIntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
516 };
517 518 } // namespace bitset_detail
519 520 // BitSet dispatches to IntBitSet or MultiIntBitSet as appropriate for the requested minimum number
521 // of bits. Use IntBitSet up to 32-bit, or up to 64-bit on 64-bit platforms; above that, use a
522 // MultiIntBitSet of size_t.
523 template<unsigned BITS>
524 using BitSet = std::conditional_t<(BITS <= 32), bitset_detail::IntBitSet<uint32_t>,
525 std::conditional_t<(BITS <= std::numeric_limits<size_t>::digits), bitset_detail::IntBitSet<size_t>,
526 bitset_detail::MultiIntBitSet<size_t, CeilDiv(BITS, size_t{std::numeric_limits<size_t>::digits})>>>;
527 528 #endif // BITCOIN_UTIL_BITSET_H
529