1//
2// Copyright 2015 The ANGLE Project Authors. All rights reserved.
3// Use of this source code is governed by a BSD-style license that can be
4// found in the LICENSE file.
5//
6// bitset_utils:
7// Bitset-related helper classes, such as a fast iterator to scan for set bits.
8//
9
10#ifndef COMMON_BITSETITERATOR_H_
11#define COMMON_BITSETITERATOR_H_
12
13#include <stdint.h>
14
15#include <bitset>
16
17#include "common/angleutils.h"
18#include "common/debug.h"
19#include "common/mathutil.h"
20#include "common/platform.h"
21
22namespace angle
23{
24
25template <size_t N, typename BitsT, typename ParamT = std::size_t>
26class BitSetT final
27{
28 public:
29 class Reference final
30 {
31 public:
32 ~Reference() {}
33 Reference &operator=(bool x)
34 {
35 mParent->set(mBit, x);
36 return *this;
37 }
38 explicit operator bool() const { return mParent->test(mBit); }
39
40 private:
41 friend class BitSetT;
42
43 Reference(BitSetT *parent, ParamT bit) : mParent(parent), mBit(bit) {}
44
45 BitSetT *mParent;
46 ParamT mBit;
47 };
48
49 class Iterator final
50 {
51 public:
52 Iterator(const BitSetT &bits);
53 Iterator &operator++();
54
55 bool operator==(const Iterator &other) const;
56 bool operator!=(const Iterator &other) const;
57 ParamT operator*() const;
58
59 // These helper functions allow mutating an iterator in-flight.
60 // They only operate on later bits to ensure we don't iterate the same bit twice.
61 void resetLaterBit(std::size_t index)
62 {
63 ASSERT(index > mCurrentBit);
64 mBitsCopy.reset(index);
65 }
66
67 void setLaterBit(std::size_t index)
68 {
69 ASSERT(index > mCurrentBit);
70 mBitsCopy.set(index);
71 }
72
73 private:
74 std::size_t getNextBit();
75
76 BitSetT mBitsCopy;
77 std::size_t mCurrentBit;
78 };
79
80 BitSetT();
81 constexpr explicit BitSetT(BitsT value);
82
83 BitSetT(const BitSetT &other);
84 BitSetT &operator=(const BitSetT &other);
85
86 bool operator==(const BitSetT &other) const;
87 bool operator!=(const BitSetT &other) const;
88
89 constexpr bool operator[](ParamT pos) const;
90 Reference operator[](ParamT pos) { return Reference(this, pos); }
91
92 bool test(ParamT pos) const;
93
94 bool all() const;
95 bool any() const;
96 bool none() const;
97 std::size_t count() const;
98
99 constexpr std::size_t size() const { return N; }
100
101 BitSetT &operator&=(const BitSetT &other);
102 BitSetT &operator|=(const BitSetT &other);
103 BitSetT &operator^=(const BitSetT &other);
104 BitSetT operator~() const;
105
106 BitSetT &operator&=(BitsT value);
107 BitSetT &operator|=(BitsT value);
108 BitSetT &operator^=(BitsT value);
109
110 BitSetT operator<<(std::size_t pos) const;
111 BitSetT &operator<<=(std::size_t pos);
112 BitSetT operator>>(std::size_t pos) const;
113 BitSetT &operator>>=(std::size_t pos);
114
115 BitSetT &set();
116 BitSetT &set(ParamT pos, bool value = true);
117
118 BitSetT &reset();
119 BitSetT &reset(ParamT pos);
120
121 BitSetT &flip();
122 BitSetT &flip(ParamT pos);
123
124 unsigned long to_ulong() const { return static_cast<unsigned long>(mBits); }
125 BitsT bits() const { return mBits; }
126
127 Iterator begin() const { return Iterator(*this); }
128 Iterator end() const { return Iterator(BitSetT()); }
129
130 private:
131 constexpr static BitsT Bit(ParamT x)
132 {
133 return (static_cast<BitsT>(1) << static_cast<size_t>(x));
134 }
135 // Produces a mask of ones up to the "x"th bit.
136 constexpr static BitsT Mask(std::size_t x)
137 {
138 return ((Bit(static_cast<ParamT>(x - 1)) - 1) << 1) + 1;
139 }
140
141 BitsT mBits;
142};
143
144template <size_t N>
145class IterableBitSet : public std::bitset<N>
146{
147 public:
148 IterableBitSet() {}
149 IterableBitSet(const std::bitset<N> &implicitBitSet) : std::bitset<N>(implicitBitSet) {}
150
151 class Iterator final
152 {
153 public:
154 Iterator(const std::bitset<N> &bits);
155 Iterator &operator++();
156
157 bool operator==(const Iterator &other) const;
158 bool operator!=(const Iterator &other) const;
159 unsigned long operator*() const { return mCurrentBit; }
160
161 // These helper functions allow mutating an iterator in-flight.
162 // They only operate on later bits to ensure we don't iterate the same bit twice.
163 void resetLaterBit(std::size_t index)
164 {
165 ASSERT(index > mCurrentBit);
166 mBits.reset(index - mOffset);
167 }
168
169 void setLaterBit(std::size_t index)
170 {
171 ASSERT(index > mCurrentBit);
172 mBits.set(index - mOffset);
173 }
174
175 private:
176 unsigned long getNextBit();
177
178 static constexpr size_t BitsPerWord = sizeof(uint32_t) * 8;
179 std::bitset<N> mBits;
180 unsigned long mCurrentBit;
181 unsigned long mOffset;
182 };
183
184 Iterator begin() const { return Iterator(*this); }
185 Iterator end() const { return Iterator(std::bitset<N>(0)); }
186};
187
188template <size_t N>
189IterableBitSet<N>::Iterator::Iterator(const std::bitset<N> &bitset)
190 : mBits(bitset), mCurrentBit(0), mOffset(0)
191{
192 if (mBits.any())
193 {
194 mCurrentBit = getNextBit();
195 }
196 else
197 {
198 mOffset = static_cast<unsigned long>(rx::roundUp(N, BitsPerWord));
199 }
200}
201
202template <size_t N>
203ANGLE_INLINE typename IterableBitSet<N>::Iterator &IterableBitSet<N>::Iterator::operator++()
204{
205 ASSERT(mBits.any());
206 mBits.set(mCurrentBit - mOffset, 0);
207 mCurrentBit = getNextBit();
208 return *this;
209}
210
211template <size_t N>
212bool IterableBitSet<N>::Iterator::operator==(const Iterator &other) const
213{
214 return mOffset == other.mOffset && mBits == other.mBits;
215}
216
217template <size_t N>
218bool IterableBitSet<N>::Iterator::operator!=(const Iterator &other) const
219{
220 return !(*this == other);
221}
222
223template <size_t N>
224unsigned long IterableBitSet<N>::Iterator::getNextBit()
225{
226 // TODO(jmadill): Use 64-bit scan when possible.
227 static constexpr std::bitset<N> wordMask(std::numeric_limits<uint32_t>::max());
228
229 while (mOffset < N)
230 {
231 uint32_t wordBits = static_cast<uint32_t>((mBits & wordMask).to_ulong());
232 if (wordBits != 0)
233 {
234 return gl::ScanForward(wordBits) + mOffset;
235 }
236
237 mBits >>= BitsPerWord;
238 mOffset += BitsPerWord;
239 }
240 return 0;
241}
242
243template <size_t N, typename BitsT, typename ParamT>
244BitSetT<N, BitsT, ParamT>::BitSetT() : mBits(0)
245{
246 static_assert(N > 0, "Bitset type cannot support zero bits.");
247 static_assert(N <= sizeof(BitsT) * 8, "Bitset type cannot support a size this large.");
248}
249
250template <size_t N, typename BitsT, typename ParamT>
251constexpr BitSetT<N, BitsT, ParamT>::BitSetT(BitsT value) : mBits(value & Mask(N))
252{}
253
254template <size_t N, typename BitsT, typename ParamT>
255BitSetT<N, BitsT, ParamT>::BitSetT(const BitSetT &other) : mBits(other.mBits)
256{}
257
258template <size_t N, typename BitsT, typename ParamT>
259BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator=(const BitSetT &other)
260{
261 mBits = other.mBits;
262 return *this;
263}
264
265template <size_t N, typename BitsT, typename ParamT>
266bool BitSetT<N, BitsT, ParamT>::operator==(const BitSetT &other) const
267{
268 return mBits == other.mBits;
269}
270
271template <size_t N, typename BitsT, typename ParamT>
272bool BitSetT<N, BitsT, ParamT>::operator!=(const BitSetT &other) const
273{
274 return mBits != other.mBits;
275}
276
277template <size_t N, typename BitsT, typename ParamT>
278constexpr bool BitSetT<N, BitsT, ParamT>::operator[](ParamT pos) const
279{
280 return test(pos);
281}
282
283template <size_t N, typename BitsT, typename ParamT>
284bool BitSetT<N, BitsT, ParamT>::test(ParamT pos) const
285{
286 return (mBits & Bit(pos)) != 0;
287}
288
289template <size_t N, typename BitsT, typename ParamT>
290bool BitSetT<N, BitsT, ParamT>::all() const
291{
292 ASSERT(mBits == (mBits & Mask(N)));
293 return mBits == Mask(N);
294}
295
296template <size_t N, typename BitsT, typename ParamT>
297bool BitSetT<N, BitsT, ParamT>::any() const
298{
299 ASSERT(mBits == (mBits & Mask(N)));
300 return (mBits != 0);
301}
302
303template <size_t N, typename BitsT, typename ParamT>
304bool BitSetT<N, BitsT, ParamT>::none() const
305{
306 ASSERT(mBits == (mBits & Mask(N)));
307 return (mBits == 0);
308}
309
310template <size_t N, typename BitsT, typename ParamT>
311std::size_t BitSetT<N, BitsT, ParamT>::count() const
312{
313 return gl::BitCount(mBits);
314}
315
316template <size_t N, typename BitsT, typename ParamT>
317BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator&=(const BitSetT &other)
318{
319 mBits &= other.mBits;
320 return *this;
321}
322
323template <size_t N, typename BitsT, typename ParamT>
324BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator|=(const BitSetT &other)
325{
326 mBits |= other.mBits;
327 return *this;
328}
329
330template <size_t N, typename BitsT, typename ParamT>
331BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator^=(const BitSetT &other)
332{
333 mBits = mBits ^ other.mBits;
334 return *this;
335}
336
337template <size_t N, typename BitsT, typename ParamT>
338BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator~() const
339{
340 return BitSetT<N, BitsT, ParamT>(~mBits & Mask(N));
341}
342
343template <size_t N, typename BitsT, typename ParamT>
344BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator&=(BitsT value)
345{
346 mBits &= value;
347 return *this;
348}
349
350template <size_t N, typename BitsT, typename ParamT>
351BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator|=(BitsT value)
352{
353 mBits |= value & Mask(N);
354 return *this;
355}
356
357template <size_t N, typename BitsT, typename ParamT>
358BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator^=(BitsT value)
359{
360 mBits ^= value & Mask(N);
361 return *this;
362}
363
364template <size_t N, typename BitsT, typename ParamT>
365BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator<<(std::size_t pos) const
366{
367 return BitSetT<N, BitsT, ParamT>((mBits << pos) & Mask(N));
368}
369
370template <size_t N, typename BitsT, typename ParamT>
371BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator<<=(std::size_t pos)
372{
373 mBits = (mBits << pos & Mask(N));
374 return *this;
375}
376
377template <size_t N, typename BitsT, typename ParamT>
378BitSetT<N, BitsT, ParamT> BitSetT<N, BitsT, ParamT>::operator>>(std::size_t pos) const
379{
380 return BitSetT<N, BitsT, ParamT>(mBits >> pos);
381}
382
383template <size_t N, typename BitsT, typename ParamT>
384BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::operator>>=(std::size_t pos)
385{
386 mBits = ((mBits >> pos) & Mask(N));
387 return *this;
388}
389
390template <size_t N, typename BitsT, typename ParamT>
391BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::set()
392{
393 mBits = Mask(N);
394 return *this;
395}
396
397template <size_t N, typename BitsT, typename ParamT>
398BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::set(ParamT pos, bool value)
399{
400 if (value)
401 {
402 mBits |= Bit(pos) & Mask(N);
403 }
404 else
405 {
406 reset(pos);
407 }
408 return *this;
409}
410
411template <size_t N, typename BitsT, typename ParamT>
412BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::reset()
413{
414 mBits = 0;
415 return *this;
416}
417
418template <size_t N, typename BitsT, typename ParamT>
419BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::reset(ParamT pos)
420{
421 mBits &= ~Bit(pos);
422 return *this;
423}
424
425template <size_t N, typename BitsT, typename ParamT>
426BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::flip()
427{
428 mBits ^= Mask(N);
429 return *this;
430}
431
432template <size_t N, typename BitsT, typename ParamT>
433BitSetT<N, BitsT, ParamT> &BitSetT<N, BitsT, ParamT>::flip(ParamT pos)
434{
435 mBits ^= Bit(pos) & Mask(N);
436 return *this;
437}
438
439template <size_t N, typename BitsT, typename ParamT>
440BitSetT<N, BitsT, ParamT>::Iterator::Iterator(const BitSetT &bits) : mBitsCopy(bits), mCurrentBit(0)
441{
442 if (bits.any())
443 {
444 mCurrentBit = getNextBit();
445 }
446}
447
448template <size_t N, typename BitsT, typename ParamT>
449ANGLE_INLINE typename BitSetT<N, BitsT, ParamT>::Iterator &BitSetT<N, BitsT, ParamT>::Iterator::
450operator++()
451{
452 ASSERT(mBitsCopy.any());
453 mBitsCopy.reset(static_cast<ParamT>(mCurrentBit));
454 mCurrentBit = getNextBit();
455 return *this;
456}
457
458template <size_t N, typename BitsT, typename ParamT>
459bool BitSetT<N, BitsT, ParamT>::Iterator::operator==(const Iterator &other) const
460{
461 return mBitsCopy == other.mBitsCopy;
462}
463
464template <size_t N, typename BitsT, typename ParamT>
465bool BitSetT<N, BitsT, ParamT>::Iterator::operator!=(const Iterator &other) const
466{
467 return !(*this == other);
468}
469
470template <size_t N, typename BitsT, typename ParamT>
471ParamT BitSetT<N, BitsT, ParamT>::Iterator::operator*() const
472{
473 return static_cast<ParamT>(mCurrentBit);
474}
475
476template <size_t N, typename BitsT, typename ParamT>
477std::size_t BitSetT<N, BitsT, ParamT>::Iterator::getNextBit()
478{
479 if (mBitsCopy.none())
480 {
481 return 0;
482 }
483
484 return gl::ScanForward(mBitsCopy.mBits);
485}
486
487template <size_t N>
488using BitSet32 = BitSetT<N, uint32_t>;
489
490// ScanForward for 64-bits requires a 64-bit implementation.
491#if defined(ANGLE_IS_64_BIT_CPU)
492template <size_t N>
493using BitSet64 = BitSetT<N, uint64_t>;
494#endif // defined(ANGLE_IS_64_BIT_CPU)
495
496namespace priv
497{
498
499template <size_t N, typename T>
500using EnableIfBitsFit = typename std::enable_if<N <= sizeof(T) * 8>::type;
501
502template <size_t N, typename Enable = void>
503struct GetBitSet
504{
505 using Type = IterableBitSet<N>;
506};
507
508// Prefer 64-bit bitsets on 64-bit CPUs. They seem faster than 32-bit.
509#if defined(ANGLE_IS_64_BIT_CPU)
510template <size_t N>
511struct GetBitSet<N, EnableIfBitsFit<N, uint64_t>>
512{
513 using Type = BitSet64<N>;
514};
515#else
516template <size_t N>
517struct GetBitSet<N, EnableIfBitsFit<N, uint32_t>>
518{
519 using Type = BitSet32<N>;
520};
521#endif // defined(ANGLE_IS_64_BIT_CPU)
522
523} // namespace priv
524
525template <size_t N>
526using BitSet = typename priv::GetBitSet<N>::Type;
527
528} // namespace angle
529
530template <size_t N, typename BitsT, typename ParamT>
531inline angle::BitSetT<N, BitsT, ParamT> operator&(const angle::BitSetT<N, BitsT, ParamT> &lhs,
532 const angle::BitSetT<N, BitsT, ParamT> &rhs)
533{
534 angle::BitSetT<N, BitsT, ParamT> result(lhs);
535 result &= rhs.bits();
536 return result;
537}
538
539template <size_t N, typename BitsT, typename ParamT>
540inline angle::BitSetT<N, BitsT, ParamT> operator|(const angle::BitSetT<N, BitsT, ParamT> &lhs,
541 const angle::BitSetT<N, BitsT, ParamT> &rhs)
542{
543 angle::BitSetT<N, BitsT, ParamT> result(lhs);
544 result |= rhs.bits();
545 return result;
546}
547
548template <size_t N, typename BitsT, typename ParamT>
549inline angle::BitSetT<N, BitsT, ParamT> operator^(const angle::BitSetT<N, BitsT, ParamT> &lhs,
550 const angle::BitSetT<N, BitsT, ParamT> &rhs)
551{
552 angle::BitSetT<N, BitsT, ParamT> result(lhs);
553 result ^= rhs.bits();
554 return result;
555}
556
557#endif // COMMON_BITSETITERATOR_H_
558