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