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