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