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_unittest:
7 // Tests bitset helpers and custom classes.
8 //
9
10 #include <array>
11
12 #include <gtest/gtest.h>
13
14 #include "common/bitset_utils.h"
15
16 using namespace angle;
17
18 namespace
19 {
20 template <typename T>
21 class BitSetTest : public testing::Test
22 {
23 protected:
24 T mBits;
25 typedef T BitSet;
26 };
27
28 using BitSetTypes = ::testing::Types<BitSet<12>, BitSet32<12>, BitSet64<12>>;
29 TYPED_TEST_SUITE(BitSetTest, BitSetTypes);
30
TYPED_TEST(BitSetTest,Basic)31 TYPED_TEST(BitSetTest, Basic)
32 {
33 EXPECT_EQ(TypeParam::Zero().bits(), 0u);
34
35 TypeParam mBits = this->mBits;
36 EXPECT_FALSE(mBits.all());
37 EXPECT_FALSE(mBits.any());
38 EXPECT_TRUE(mBits.none());
39 EXPECT_EQ(mBits.count(), 0u);
40
41 // Set every bit to 1.
42 for (size_t i = 0; i < mBits.size(); ++i)
43 {
44 mBits.set(i);
45
46 EXPECT_EQ(mBits.all(), i + 1 == mBits.size());
47 EXPECT_TRUE(mBits.any());
48 EXPECT_FALSE(mBits.none());
49 EXPECT_EQ(mBits.count(), i + 1);
50 }
51
52 // Reset every other bit to 0.
53 for (size_t i = 0; i < mBits.size(); i += 2)
54 {
55 mBits.reset(i);
56
57 EXPECT_FALSE(mBits.all());
58 EXPECT_TRUE(mBits.any());
59 EXPECT_FALSE(mBits.none());
60 EXPECT_EQ(mBits.count(), mBits.size() - i / 2 - 1);
61 }
62
63 // Flip all bits.
64 for (size_t i = 0; i < mBits.size(); ++i)
65 {
66 mBits.flip(i);
67
68 EXPECT_FALSE(mBits.all());
69 EXPECT_TRUE(mBits.any());
70 EXPECT_FALSE(mBits.none());
71 EXPECT_EQ(mBits.count(), mBits.size() / 2 + (i % 2 == 0));
72 }
73
74 // Make sure the bit pattern is what we expect at this point.
75 for (size_t i = 0; i < mBits.size(); ++i)
76 {
77 EXPECT_EQ(mBits.test(i), i % 2 == 0);
78 EXPECT_EQ(static_cast<bool>(mBits[i]), i % 2 == 0);
79 }
80
81 // Test that flip, set and reset all bits at once work.
82 mBits.flip();
83 EXPECT_FALSE(mBits.all());
84 EXPECT_TRUE(mBits.any());
85 EXPECT_FALSE(mBits.none());
86 EXPECT_EQ(mBits.count(), mBits.size() / 2);
87 EXPECT_EQ(mBits.first(), 1u);
88
89 mBits.set();
90 EXPECT_TRUE(mBits.all());
91 EXPECT_TRUE(mBits.any());
92 EXPECT_FALSE(mBits.none());
93 EXPECT_EQ(mBits.count(), mBits.size());
94 EXPECT_EQ(mBits.first(), 0u);
95
96 mBits.reset();
97 EXPECT_FALSE(mBits.all());
98 EXPECT_FALSE(mBits.any());
99 EXPECT_TRUE(mBits.none());
100 EXPECT_EQ(mBits.count(), 0u);
101 }
102
TYPED_TEST(BitSetTest,BitwiseOperators)103 TYPED_TEST(BitSetTest, BitwiseOperators)
104 {
105 TypeParam mBits = this->mBits;
106 // Use a value that has a 1 in the 12th bit, to make sure masking to exactly 12 bits does not
107 // have an off-by-one error.
108 constexpr uint32_t kSelfValue = 0x9E4;
109 constexpr uint32_t kOtherValue = 0xC6A;
110
111 constexpr uint32_t kMask = (1 << 12) - 1;
112 constexpr uint32_t kSelfMaskedValue = kSelfValue & kMask;
113 constexpr uint32_t kOtherMaskedValue = kOtherValue & kMask;
114
115 constexpr uint32_t kShift = 3;
116 constexpr uint32_t kSelfShiftedLeft = kSelfMaskedValue << kShift & kMask;
117 constexpr uint32_t kSelfShiftedRight = kSelfMaskedValue >> kShift & kMask;
118
119 mBits |= kSelfValue;
120 typename TestFixture::BitSet other(kOtherValue);
121 typename TestFixture::BitSet anded(kSelfMaskedValue & kOtherMaskedValue);
122 typename TestFixture::BitSet ored(kSelfMaskedValue | kOtherMaskedValue);
123 typename TestFixture::BitSet xored(kSelfMaskedValue ^ kOtherMaskedValue);
124
125 EXPECT_EQ(mBits.bits(), kSelfMaskedValue);
126 EXPECT_EQ(other.bits(), kOtherMaskedValue);
127
128 EXPECT_EQ(mBits & other, anded);
129 EXPECT_EQ(mBits | other, ored);
130 EXPECT_EQ(mBits ^ other, xored);
131
132 EXPECT_NE(mBits, other);
133 EXPECT_NE(anded, ored);
134 EXPECT_NE(anded, xored);
135 EXPECT_NE(ored, xored);
136
137 mBits &= other;
138 EXPECT_EQ(mBits, anded);
139
140 mBits |= ored;
141 EXPECT_EQ(mBits, ored);
142
143 mBits ^= other;
144 mBits ^= anded;
145 EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfValue));
146
147 EXPECT_EQ(mBits << kShift, typename TestFixture::BitSet(kSelfShiftedLeft));
148 EXPECT_EQ(mBits >> kShift, typename TestFixture::BitSet(kSelfShiftedRight));
149
150 mBits <<= kShift;
151 EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfShiftedLeft));
152 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
153
154 mBits = typename TestFixture::BitSet(kSelfValue);
155 mBits >>= kShift;
156 EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfShiftedRight));
157 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
158
159 mBits |= kSelfMaskedValue;
160 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
161 mBits ^= kOtherMaskedValue;
162 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
163 }
164
165 template <typename T>
166 class BitSetIteratorTest : public testing::Test
167 {
168 protected:
169 T mStateBits;
170 typedef T BitSet;
171 };
172
173 using BitSetIteratorTypes = ::testing::Types<BitSet<40>, BitSet64<40>>;
174 TYPED_TEST_SUITE(BitSetIteratorTest, BitSetIteratorTypes);
175
176 // Simple iterator test.
TYPED_TEST(BitSetIteratorTest,Iterator)177 TYPED_TEST(BitSetIteratorTest, Iterator)
178 {
179 TypeParam mStateBits = this->mStateBits;
180 std::set<size_t> originalValues;
181 originalValues.insert(2);
182 originalValues.insert(6);
183 originalValues.insert(8);
184 originalValues.insert(35);
185
186 for (size_t value : originalValues)
187 {
188 mStateBits.set(value);
189 }
190
191 std::set<size_t> readValues;
192 for (size_t bit : mStateBits)
193 {
194 EXPECT_EQ(1u, originalValues.count(bit));
195 EXPECT_EQ(0u, readValues.count(bit));
196 readValues.insert(bit);
197 }
198
199 EXPECT_EQ(originalValues.size(), readValues.size());
200 }
201
202 // Ensure lsb->msb iteration order.
TYPED_TEST(BitSetIteratorTest,IterationOrder)203 TYPED_TEST(BitSetIteratorTest, IterationOrder)
204 {
205 TypeParam mStateBits = this->mStateBits;
206 const std::array<size_t, 8> writeOrder = {20, 25, 16, 31, 10, 14, 36, 19};
207 const std::array<size_t, 8> fetchOrder = {10, 14, 16, 19, 20, 25, 31, 36};
208
209 for (size_t value : writeOrder)
210 {
211 mStateBits.set(value);
212 }
213 EXPECT_EQ(writeOrder.size(), mStateBits.count());
214
215 size_t i = 0;
216 for (size_t bit : mStateBits)
217 {
218 EXPECT_EQ(fetchOrder[i], bit);
219 i++;
220 }
221 EXPECT_EQ(fetchOrder.size(), mStateBits.count());
222 }
223
224 // Test an empty iterator.
TYPED_TEST(BitSetIteratorTest,EmptySet)225 TYPED_TEST(BitSetIteratorTest, EmptySet)
226 {
227 TypeParam mStateBits = this->mStateBits;
228 // We don't use the FAIL gtest macro here since it returns immediately,
229 // causing an unreachable code warning in MSVS
230 bool sawBit = false;
231 for (size_t bit : mStateBits)
232 {
233 sawBit = true;
234 ANGLE_UNUSED_VARIABLE(bit);
235 }
236 EXPECT_FALSE(sawBit);
237 }
238
239 // Test iterating a result of combining two bitsets.
TYPED_TEST(BitSetIteratorTest,NonLValueBitset)240 TYPED_TEST(BitSetIteratorTest, NonLValueBitset)
241 {
242 TypeParam mStateBits = this->mStateBits;
243 typename TestFixture::BitSet otherBits;
244
245 mStateBits.set(1);
246 mStateBits.set(2);
247 mStateBits.set(3);
248 mStateBits.set(4);
249
250 otherBits.set(0);
251 otherBits.set(1);
252 otherBits.set(3);
253 otherBits.set(5);
254
255 std::set<size_t> seenBits;
256
257 typename TestFixture::BitSet maskedBits = (mStateBits & otherBits);
258 for (size_t bit : maskedBits)
259 {
260 EXPECT_EQ(0u, seenBits.count(bit));
261 seenBits.insert(bit);
262 EXPECT_TRUE(mStateBits[bit]);
263 EXPECT_TRUE(otherBits[bit]);
264 }
265
266 EXPECT_EQ((mStateBits & otherBits).count(), seenBits.size());
267 }
268
269 // Test bit assignments.
TYPED_TEST(BitSetIteratorTest,BitAssignment)270 TYPED_TEST(BitSetIteratorTest, BitAssignment)
271 {
272 TypeParam mStateBits = this->mStateBits;
273 std::set<size_t> originalValues;
274 originalValues.insert(2);
275 originalValues.insert(6);
276 originalValues.insert(8);
277 originalValues.insert(35);
278
279 for (size_t value : originalValues)
280 {
281 (mStateBits[value] = false) = true;
282 }
283
284 for (size_t value : originalValues)
285 {
286 EXPECT_TRUE(mStateBits.test(value));
287 }
288 }
289
290 // Tests adding bits to the iterator during iteration.
TYPED_TEST(BitSetIteratorTest,SetLaterBit)291 TYPED_TEST(BitSetIteratorTest, SetLaterBit)
292 {
293 TypeParam mStateBits = this->mStateBits;
294 std::set<size_t> expectedValues = {0, 1, 3, 5, 6, 7, 9, 35};
295 mStateBits.set(0);
296 mStateBits.set(1);
297
298 std::set<size_t> actualValues;
299
300 for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
301 {
302 if (*iter == 1)
303 {
304 iter.setLaterBit(3);
305 iter.setLaterBit(5);
306 }
307 if (*iter == 5)
308 {
309 iter.setLaterBit(6);
310 iter.setLaterBit(7);
311 iter.setLaterBit(9);
312 iter.setLaterBit(35);
313 }
314
315 actualValues.insert(*iter);
316 }
317
318 EXPECT_EQ(expectedValues, actualValues);
319 }
320
321 // Tests removing bits from the iterator during iteration.
TYPED_TEST(BitSetIteratorTest,ResetLaterBit)322 TYPED_TEST(BitSetIteratorTest, ResetLaterBit)
323 {
324 TypeParam mStateBits = this->mStateBits;
325 std::set<size_t> expectedValues = {1, 3, 5, 7, 9};
326
327 for (size_t index = 1; index <= 9; ++index)
328 mStateBits.set(index);
329
330 std::set<size_t> actualValues;
331
332 for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
333 {
334 if (*iter == 1)
335 {
336 iter.resetLaterBit(2);
337 iter.resetLaterBit(4);
338 iter.resetLaterBit(6);
339 iter.resetLaterBit(8);
340 }
341
342 actualValues.insert(*iter);
343 }
344
345 EXPECT_EQ(expectedValues, actualValues);
346 }
347
348 // Tests adding bitsets to the iterator during iteration.
TYPED_TEST(BitSetIteratorTest,SetLaterBits)349 TYPED_TEST(BitSetIteratorTest, SetLaterBits)
350 {
351 TypeParam mStateBits = this->mStateBits;
352 std::set<size_t> expectedValues = {1, 2, 3, 4, 5, 7, 9};
353 mStateBits.set(1);
354 mStateBits.set(2);
355 mStateBits.set(3);
356
357 TypeParam laterBits;
358 laterBits.set(4);
359 laterBits.set(5);
360 laterBits.set(7);
361 laterBits.set(9);
362
363 std::set<size_t> actualValues;
364
365 for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
366 {
367 if (*iter == 3)
368 {
369 iter.setLaterBits(laterBits);
370 }
371
372 EXPECT_EQ(actualValues.count(*iter), 0u);
373 actualValues.insert(*iter);
374 }
375
376 EXPECT_EQ(expectedValues, actualValues);
377 }
378
379 template <typename T>
380 class BitSetArrayTest : public testing::Test
381 {
382 protected:
383 T mBitSet;
384 };
385
386 using BitSetArrayTypes =
387 ::testing::Types<BitSetArray<65>, BitSetArray<128>, BitSetArray<130>, BitSetArray<511>>;
388 TYPED_TEST_SUITE(BitSetArrayTest, BitSetArrayTypes);
389
TYPED_TEST(BitSetArrayTest,BasicTest)390 TYPED_TEST(BitSetArrayTest, BasicTest)
391 {
392 TypeParam &mBits = this->mBitSet;
393
394 EXPECT_FALSE(mBits.all());
395 EXPECT_FALSE(mBits.any());
396 EXPECT_TRUE(mBits.none());
397 EXPECT_EQ(mBits.count(), 0u);
398 EXPECT_EQ(mBits.bits(0), 0u);
399
400 // Verify set on a single bit
401 mBits.set(45);
402 for (auto bit : mBits)
403 {
404 EXPECT_EQ(bit, 45u);
405 }
406
407 EXPECT_EQ(mBits.first(), 45u);
408 EXPECT_EQ(mBits.last(), 45u);
409
410 mBits.reset(45);
411
412 // Set every bit to 1.
413 for (size_t i = 0; i < mBits.size(); ++i)
414 {
415 mBits.set(i);
416
417 EXPECT_EQ(mBits.all(), i + 1 == mBits.size());
418 EXPECT_TRUE(mBits.any());
419 EXPECT_FALSE(mBits.none());
420 EXPECT_EQ(mBits.count(), i + 1);
421 }
422
423 // Reset odd bits to 0.
424 for (size_t i = 1; i < mBits.size(); i += 2)
425 {
426 mBits.reset(i);
427
428 EXPECT_FALSE(mBits.all());
429 EXPECT_TRUE(mBits.any());
430 EXPECT_FALSE(mBits.none());
431 EXPECT_EQ(mBits.count(), mBits.size() - i / 2 - 1);
432 }
433
434 // Make sure the bit pattern is what we expect at this point.
435 // All even bits should be set
436 for (size_t i = 0; i < mBits.size(); ++i)
437 {
438 EXPECT_EQ(mBits.test(i), i % 2 == 0);
439 EXPECT_EQ(static_cast<bool>(mBits[i]), i % 2 == 0);
440 }
441
442 // Reset everything.
443 mBits.reset();
444 EXPECT_FALSE(mBits.all());
445 EXPECT_FALSE(mBits.any());
446 EXPECT_TRUE(mBits.none());
447 EXPECT_EQ(mBits.count(), 0u);
448
449 // Test intersection logic
450 TypeParam testBitSet;
451 testBitSet.set(1);
452 EXPECT_EQ(testBitSet.bits(0), (1ul << 1ul));
453 testBitSet.set(3);
454 EXPECT_EQ(testBitSet.bits(0), (1ul << 1ul) | (1ul << 3ul));
455 testBitSet.set(5);
456 EXPECT_EQ(testBitSet.bits(0), (1ul << 1ul) | (1ul << 3ul) | (1ul << 5ul));
457 EXPECT_FALSE(mBits.intersects(testBitSet));
458 mBits.set(3);
459 EXPECT_TRUE(mBits.intersects(testBitSet));
460 mBits.set(4);
461 EXPECT_TRUE(mBits.intersects(testBitSet));
462 mBits.reset(3);
463 EXPECT_FALSE(mBits.intersects(testBitSet));
464 testBitSet.set(4);
465 EXPECT_TRUE(mBits.intersects(testBitSet));
466
467 // Test that flip works.
468 // Reset everything.
469 mBits.reset();
470 EXPECT_EQ(mBits.count(), 0u);
471 mBits.flip();
472 EXPECT_EQ(mBits.count(), mBits.size());
473
474 // Test operators
475
476 // Assignment operators - "=", "&=", "|=" and "^="
477 mBits.reset();
478 mBits = testBitSet;
479 for (auto bit : testBitSet)
480 {
481 EXPECT_TRUE(mBits.test(bit));
482 }
483
484 mBits &= testBitSet;
485 for (auto bit : testBitSet)
486 {
487 EXPECT_TRUE(mBits.test(bit));
488 }
489 EXPECT_EQ(mBits.count(), testBitSet.count());
490
491 mBits.reset();
492 mBits |= testBitSet;
493 for (auto bit : testBitSet)
494 {
495 EXPECT_TRUE(mBits.test(bit));
496 }
497
498 mBits ^= testBitSet;
499 EXPECT_TRUE(mBits.none());
500
501 // Bitwise operators - "&", "|" and "^"
502 std::set<std::size_t> bits1 = {0, 45, 60};
503 std::set<std::size_t> bits2 = {5, 45, 50, 63};
504 std::set<std::size_t> bits1Andbits2 = {45};
505 std::set<std::size_t> bits1Orbits2 = {0, 5, 45, 50, 60, 63};
506 std::set<std::size_t> bits1Xorbits2 = {0, 5, 50, 60, 63};
507 std::set<std::size_t> actualValues;
508 TypeParam testBitSet1;
509 TypeParam testBitSet2;
510
511 for (std::size_t bit : bits1)
512 {
513 testBitSet1.set(bit);
514 }
515 for (std::size_t bit : bits2)
516 {
517 testBitSet2.set(bit);
518 }
519
520 EXPECT_EQ(testBitSet1.first(), 0u);
521 EXPECT_EQ(testBitSet1.last(), 60u);
522
523 EXPECT_EQ(testBitSet2.first(), 5u);
524 EXPECT_EQ(testBitSet2.last(), 63u);
525
526 actualValues.clear();
527 for (auto bit : (testBitSet1 & testBitSet2))
528 {
529 actualValues.insert(bit);
530 }
531 EXPECT_EQ(bits1Andbits2, actualValues);
532
533 actualValues.clear();
534 for (auto bit : (testBitSet1 | testBitSet2))
535 {
536 actualValues.insert(bit);
537 }
538 EXPECT_EQ(bits1Orbits2, actualValues);
539
540 actualValues.clear();
541 for (auto bit : (testBitSet1 ^ testBitSet2))
542 {
543 actualValues.insert(bit);
544 }
545 EXPECT_EQ(bits1Xorbits2, actualValues);
546
547 // Relational operators - "==" and "!="
548 EXPECT_FALSE(testBitSet1 == testBitSet2);
549 EXPECT_TRUE(testBitSet1 != testBitSet2);
550
551 // Unary operators - "~" and "[]"
552 mBits.reset();
553 mBits = ~testBitSet;
554 for (auto bit : mBits)
555 {
556 EXPECT_FALSE(testBitSet.test(bit));
557 }
558 EXPECT_EQ(mBits.count(), (mBits.size() - testBitSet.count()));
559
560 mBits.reset();
561 for (auto bit : testBitSet)
562 {
563 mBits[bit] = true;
564 }
565 for (auto bit : mBits)
566 {
567 EXPECT_TRUE(testBitSet.test(bit));
568 }
569 }
570
TYPED_TEST(BitSetArrayTest,IterationWithGaps)571 TYPED_TEST(BitSetArrayTest, IterationWithGaps)
572 {
573 TypeParam &mBits = this->mBitSet;
574
575 // Test iterator works with gap in bitset.
576 std::set<size_t> bitsToBeSet = {0, mBits.size() / 2, mBits.size() - 1};
577 for (size_t bit : bitsToBeSet)
578 {
579 mBits.set(bit);
580 }
581 std::set<size_t> bitsActuallySet = {};
582 for (size_t bit : mBits)
583 {
584 bitsActuallySet.insert(bit);
585 }
586 EXPECT_EQ(bitsToBeSet, bitsActuallySet);
587 EXPECT_EQ(mBits.count(), bitsToBeSet.size());
588 mBits.reset();
589 }
590
591 // Unit test for angle::Bit
TEST(Bit,Test)592 TEST(Bit, Test)
593 {
594 EXPECT_EQ(Bit<uint32_t>(0), 1u);
595 EXPECT_EQ(Bit<uint32_t>(1), 2u);
596 EXPECT_EQ(Bit<uint32_t>(2), 4u);
597 EXPECT_EQ(Bit<uint32_t>(3), 8u);
598 EXPECT_EQ(Bit<uint32_t>(31), 0x8000'0000u);
599 EXPECT_EQ(Bit<uint64_t>(63), static_cast<uint64_t>(0x8000'0000'0000'0000llu));
600 }
601
602 // Unit test for angle::BitMask
TEST(BitMask,Test)603 TEST(BitMask, Test)
604 {
605 EXPECT_EQ(BitMask<uint32_t>(1), 1u);
606 EXPECT_EQ(BitMask<uint32_t>(2), 3u);
607 EXPECT_EQ(BitMask<uint32_t>(3), 7u);
608 EXPECT_EQ(BitMask<uint32_t>(31), 0x7FFF'FFFFu);
609 EXPECT_EQ(BitMask<uint32_t>(32), 0xFFFF'FFFFu);
610 EXPECT_EQ(BitMask<uint64_t>(63), static_cast<uint64_t>(0x7FFF'FFFF'FFFF'FFFFllu));
611 EXPECT_EQ(BitMask<uint64_t>(64), static_cast<uint64_t>(0xFFFF'FFFF'FFFF'FFFFllu));
612 }
613 } // anonymous namespace
614