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