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
31 // Basic test of various bitset functionalities
TYPED_TEST(BitSetTest,Basic)32 TYPED_TEST(BitSetTest, Basic)
33 {
34 EXPECT_EQ(TypeParam::Zero().bits(), 0u);
35
36 TypeParam mBits = this->mBits;
37 EXPECT_FALSE(mBits.all());
38 EXPECT_FALSE(mBits.any());
39 EXPECT_TRUE(mBits.none());
40 EXPECT_EQ(mBits.count(), 0u);
41
42 // Set every bit to 1.
43 for (size_t i = 0; i < mBits.size(); ++i)
44 {
45 mBits.set(i);
46
47 EXPECT_EQ(mBits.all(), i + 1 == mBits.size());
48 EXPECT_TRUE(mBits.any());
49 EXPECT_FALSE(mBits.none());
50 EXPECT_EQ(mBits.count(), i + 1);
51 }
52
53 // Reset every other bit to 0.
54 for (size_t i = 0; i < mBits.size(); i += 2)
55 {
56 mBits.reset(i);
57
58 EXPECT_FALSE(mBits.all());
59 EXPECT_TRUE(mBits.any());
60 EXPECT_FALSE(mBits.none());
61 EXPECT_EQ(mBits.count(), mBits.size() - i / 2 - 1);
62 }
63
64 // Flip all bits.
65 for (size_t i = 0; i < mBits.size(); ++i)
66 {
67 mBits.flip(i);
68
69 EXPECT_FALSE(mBits.all());
70 EXPECT_TRUE(mBits.any());
71 EXPECT_FALSE(mBits.none());
72 EXPECT_EQ(mBits.count(), mBits.size() / 2 + (i % 2 == 0));
73 }
74
75 // Make sure the bit pattern is what we expect at this point.
76 for (size_t i = 0; i < mBits.size(); ++i)
77 {
78 EXPECT_EQ(mBits.test(i), i % 2 == 0);
79 EXPECT_EQ(static_cast<bool>(mBits[i]), i % 2 == 0);
80 }
81
82 // Test that flip, set and reset all bits at once work.
83 mBits.flip();
84 EXPECT_FALSE(mBits.all());
85 EXPECT_TRUE(mBits.any());
86 EXPECT_FALSE(mBits.none());
87 EXPECT_EQ(mBits.count(), mBits.size() / 2);
88 EXPECT_EQ(mBits.first(), 1u);
89
90 mBits.set();
91 EXPECT_TRUE(mBits.all());
92 EXPECT_TRUE(mBits.any());
93 EXPECT_FALSE(mBits.none());
94 EXPECT_EQ(mBits.count(), mBits.size());
95 EXPECT_EQ(mBits.first(), 0u);
96
97 mBits.reset();
98 EXPECT_FALSE(mBits.all());
99 EXPECT_FALSE(mBits.any());
100 EXPECT_TRUE(mBits.none());
101 EXPECT_EQ(mBits.count(), 0u);
102 }
103
104 // Test of gaps detection
TYPED_TEST(BitSetTest,Gaps)105 TYPED_TEST(BitSetTest, Gaps)
106 {
107 // Test and cache all bitsets with no gaps
108 std::vector<TypeParam> gaplessValues;
109 for (size_t i = 0; i <= TypeParam::size(); ++i)
110 {
111 EXPECT_FALSE(TypeParam::Mask(i).hasGaps());
112 gaplessValues.push_back(TypeParam::Mask(i));
113 }
114
115 // Explicitly check all 8-bit masks
116 for (size_t i = 0; i < 256; ++i)
117 {
118 const TypeParam bits = TypeParam(i);
119 const bool notFound =
120 std::find(gaplessValues.begin(), gaplessValues.end(), bits) == std::end(gaplessValues);
121 EXPECT_EQ(bits.hasGaps(), notFound);
122 }
123 }
124
125 // Test that BitSetT's initializer list constructor works correctly.
TYPED_TEST(BitSetTest,InitializerList)126 TYPED_TEST(BitSetTest, InitializerList)
127 {
128 TypeParam bits = TypeParam{
129 2, 5, 6, 9, 10,
130 };
131
132 for (size_t i = 0; i < bits.size(); ++i)
133 {
134 if (i == 2 || i == 5 || i == 6 || i == 9 || i == 10)
135 {
136 EXPECT_TRUE(bits[i]) << i;
137 }
138 else
139 {
140 EXPECT_FALSE(bits[i]) << i;
141 }
142 }
143 }
144
145 // Test bitwise operations
TYPED_TEST(BitSetTest,BitwiseOperators)146 TYPED_TEST(BitSetTest, BitwiseOperators)
147 {
148 TypeParam mBits = this->mBits;
149 // Use a value that has a 1 in the 12th bit, to make sure masking to exactly 12 bits does not
150 // have an off-by-one error.
151 constexpr uint32_t kSelfValue = 0x9E4;
152 constexpr uint32_t kOtherValue = 0xC6A;
153
154 constexpr uint32_t kMask = (1 << 12) - 1;
155 constexpr uint32_t kSelfMaskedValue = kSelfValue & kMask;
156 constexpr uint32_t kOtherMaskedValue = kOtherValue & kMask;
157
158 constexpr uint32_t kShift = 3;
159 constexpr uint32_t kSelfShiftedLeft = kSelfMaskedValue << kShift & kMask;
160 constexpr uint32_t kSelfShiftedRight = kSelfMaskedValue >> kShift & kMask;
161
162 mBits |= kSelfValue;
163 typename TestFixture::BitSet other(kOtherValue);
164 typename TestFixture::BitSet anded(kSelfMaskedValue & kOtherMaskedValue);
165 typename TestFixture::BitSet ored(kSelfMaskedValue | kOtherMaskedValue);
166 typename TestFixture::BitSet xored(kSelfMaskedValue ^ kOtherMaskedValue);
167
168 EXPECT_EQ(mBits.bits(), kSelfMaskedValue);
169 EXPECT_EQ(other.bits(), kOtherMaskedValue);
170
171 EXPECT_EQ(mBits & other, anded);
172 EXPECT_EQ(mBits | other, ored);
173 EXPECT_EQ(mBits ^ other, xored);
174
175 EXPECT_NE(mBits, other);
176 EXPECT_NE(anded, ored);
177 EXPECT_NE(anded, xored);
178 EXPECT_NE(ored, xored);
179
180 mBits &= other;
181 EXPECT_EQ(mBits, anded);
182
183 mBits |= ored;
184 EXPECT_EQ(mBits, ored);
185
186 mBits ^= other;
187 mBits ^= anded;
188 EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfValue));
189
190 EXPECT_EQ(mBits << kShift, typename TestFixture::BitSet(kSelfShiftedLeft));
191 EXPECT_EQ(mBits >> kShift, typename TestFixture::BitSet(kSelfShiftedRight));
192
193 mBits <<= kShift;
194 EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfShiftedLeft));
195 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
196
197 mBits = typename TestFixture::BitSet(kSelfValue);
198 mBits >>= kShift;
199 EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfShiftedRight));
200 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
201
202 mBits |= kSelfMaskedValue;
203 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
204 mBits ^= kOtherMaskedValue;
205 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
206 }
207
208 // Test BitSetT::Mask
TYPED_TEST(BitSetTest,Mask)209 TYPED_TEST(BitSetTest, Mask)
210 {
211 // Test constexpr usage
212 TypeParam bits = TypeParam::Mask(0);
213 EXPECT_EQ(bits.bits(), 0u);
214
215 bits = TypeParam::Mask(1);
216 EXPECT_EQ(bits.bits(), 1u);
217
218 bits = TypeParam::Mask(2);
219 EXPECT_EQ(bits.bits(), 3u);
220
221 bits = TypeParam::Mask(TypeParam::size());
222 EXPECT_EQ(bits.bits(), (1u << TypeParam::size()) - 1);
223
224 // Complete test
225 for (size_t i = 0; i < TypeParam::size(); ++i)
226 {
227 bits = TypeParam::Mask(i);
228 EXPECT_EQ(bits.bits(), (1u << i) - 1);
229 }
230 }
231
232 // Tests removing bits from the iterator during iteration.
TYPED_TEST(BitSetTest,ResetLaterBits)233 TYPED_TEST(BitSetTest, ResetLaterBits)
234 {
235 TypeParam bits;
236 std::set<size_t> expectedValues;
237 for (size_t i = 1; i < TypeParam::size(); i += 2)
238 {
239 expectedValues.insert(i);
240 }
241
242 for (size_t i = 1; i < TypeParam::size(); ++i)
243 bits.set(i);
244
245 // Remove the even bits
246 TypeParam resetBits;
247 for (size_t i = 2; i < TypeParam::size(); i += 2)
248 {
249 resetBits.set(i);
250 }
251
252 std::set<size_t> actualValues;
253
254 for (auto iter = bits.begin(), end = bits.end(); iter != end; ++iter)
255 {
256 if (*iter == 1)
257 {
258 iter.resetLaterBits(resetBits);
259 }
260
261 actualValues.insert(*iter);
262 }
263
264 EXPECT_EQ(expectedValues, actualValues);
265 }
266
267 template <typename T>
268 class BitSetIteratorTest : public testing::Test
269 {
270 protected:
271 T mStateBits;
272 typedef T BitSet;
273 };
274
275 using BitSetIteratorTypes = ::testing::Types<BitSet<40>, BitSet64<40>>;
276 TYPED_TEST_SUITE(BitSetIteratorTest, BitSetIteratorTypes);
277
278 // Simple iterator test.
TYPED_TEST(BitSetIteratorTest,Iterator)279 TYPED_TEST(BitSetIteratorTest, Iterator)
280 {
281 TypeParam mStateBits = this->mStateBits;
282 std::set<size_t> originalValues;
283 originalValues.insert(2);
284 originalValues.insert(6);
285 originalValues.insert(8);
286 originalValues.insert(35);
287
288 for (size_t value : originalValues)
289 {
290 mStateBits.set(value);
291 }
292
293 std::set<size_t> readValues;
294 for (size_t bit : mStateBits)
295 {
296 EXPECT_EQ(1u, originalValues.count(bit));
297 EXPECT_EQ(0u, readValues.count(bit));
298 readValues.insert(bit);
299 }
300
301 EXPECT_EQ(originalValues.size(), readValues.size());
302 }
303
304 // Ensure lsb->msb iteration order.
TYPED_TEST(BitSetIteratorTest,IterationOrder)305 TYPED_TEST(BitSetIteratorTest, IterationOrder)
306 {
307 TypeParam mStateBits = this->mStateBits;
308 const std::array<size_t, 8> writeOrder = {20, 25, 16, 31, 10, 14, 36, 19};
309 const std::array<size_t, 8> fetchOrder = {10, 14, 16, 19, 20, 25, 31, 36};
310
311 for (size_t value : writeOrder)
312 {
313 mStateBits.set(value);
314 }
315 EXPECT_EQ(writeOrder.size(), mStateBits.count());
316
317 size_t i = 0;
318 for (size_t bit : mStateBits)
319 {
320 EXPECT_EQ(fetchOrder[i], bit);
321 i++;
322 }
323 EXPECT_EQ(fetchOrder.size(), mStateBits.count());
324 }
325
326 // Test an empty iterator.
TYPED_TEST(BitSetIteratorTest,EmptySet)327 TYPED_TEST(BitSetIteratorTest, EmptySet)
328 {
329 TypeParam mStateBits = this->mStateBits;
330 // We don't use the FAIL gtest macro here since it returns immediately,
331 // causing an unreachable code warning in MSVS
332 bool sawBit = false;
333 for (size_t bit : mStateBits)
334 {
335 sawBit = true;
336 ANGLE_UNUSED_VARIABLE(bit);
337 }
338 EXPECT_FALSE(sawBit);
339 }
340
341 // Test iterating a result of combining two bitsets.
TYPED_TEST(BitSetIteratorTest,NonLValueBitset)342 TYPED_TEST(BitSetIteratorTest, NonLValueBitset)
343 {
344 TypeParam mStateBits = this->mStateBits;
345 typename TestFixture::BitSet otherBits;
346
347 mStateBits.set(1);
348 mStateBits.set(2);
349 mStateBits.set(3);
350 mStateBits.set(4);
351
352 otherBits.set(0);
353 otherBits.set(1);
354 otherBits.set(3);
355 otherBits.set(5);
356
357 std::set<size_t> seenBits;
358
359 typename TestFixture::BitSet maskedBits = (mStateBits & otherBits);
360 for (size_t bit : maskedBits)
361 {
362 EXPECT_EQ(0u, seenBits.count(bit));
363 seenBits.insert(bit);
364 EXPECT_TRUE(mStateBits[bit]);
365 EXPECT_TRUE(otherBits[bit]);
366 }
367
368 EXPECT_EQ((mStateBits & otherBits).count(), seenBits.size());
369 }
370
371 // Test bit assignments.
TYPED_TEST(BitSetIteratorTest,BitAssignment)372 TYPED_TEST(BitSetIteratorTest, BitAssignment)
373 {
374 TypeParam mStateBits = this->mStateBits;
375 std::set<size_t> originalValues;
376 originalValues.insert(2);
377 originalValues.insert(6);
378 originalValues.insert(8);
379 originalValues.insert(35);
380
381 for (size_t value : originalValues)
382 {
383 (mStateBits[value] = false) = true;
384 }
385
386 for (size_t value : originalValues)
387 {
388 EXPECT_TRUE(mStateBits.test(value));
389 }
390 }
391
392 // Tests adding bits to the iterator during iteration.
TYPED_TEST(BitSetIteratorTest,SetLaterBit)393 TYPED_TEST(BitSetIteratorTest, SetLaterBit)
394 {
395 TypeParam mStateBits = this->mStateBits;
396 std::set<size_t> expectedValues = {0, 1, 3, 5, 6, 7, 9, 35};
397 mStateBits.set(0);
398 mStateBits.set(1);
399
400 std::set<size_t> actualValues;
401
402 for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
403 {
404 if (*iter == 1)
405 {
406 iter.setLaterBit(3);
407 iter.setLaterBit(5);
408 }
409 if (*iter == 5)
410 {
411 iter.setLaterBit(6);
412 iter.setLaterBit(7);
413 iter.setLaterBit(9);
414 iter.setLaterBit(35);
415 }
416
417 actualValues.insert(*iter);
418 }
419
420 EXPECT_EQ(expectedValues, actualValues);
421 }
422
423 // Tests removing bit from the iterator during iteration.
TYPED_TEST(BitSetIteratorTest,ResetLaterBit)424 TYPED_TEST(BitSetIteratorTest, ResetLaterBit)
425 {
426 TypeParam mStateBits = this->mStateBits;
427 std::set<size_t> expectedValues = {1, 3, 5, 7, 9};
428
429 for (size_t index = 1; index <= 9; ++index)
430 mStateBits.set(index);
431
432 std::set<size_t> actualValues;
433
434 for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
435 {
436 if (*iter == 1)
437 {
438 iter.resetLaterBit(2);
439 iter.resetLaterBit(4);
440 iter.resetLaterBit(6);
441 iter.resetLaterBit(8);
442 }
443
444 actualValues.insert(*iter);
445 }
446
447 EXPECT_EQ(expectedValues, actualValues);
448 }
449
450 // Tests adding bitsets to the iterator during iteration.
TYPED_TEST(BitSetIteratorTest,SetLaterBits)451 TYPED_TEST(BitSetIteratorTest, SetLaterBits)
452 {
453 TypeParam mStateBits = this->mStateBits;
454 std::set<size_t> expectedValues = {1, 2, 3, 4, 5, 7, 9};
455 mStateBits.set(1);
456 mStateBits.set(2);
457 mStateBits.set(3);
458
459 TypeParam laterBits;
460 laterBits.set(4);
461 laterBits.set(5);
462 laterBits.set(7);
463 laterBits.set(9);
464
465 std::set<size_t> actualValues;
466
467 for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
468 {
469 if (*iter == 3)
470 {
471 iter.setLaterBits(laterBits);
472 }
473
474 EXPECT_EQ(actualValues.count(*iter), 0u);
475 actualValues.insert(*iter);
476 }
477
478 EXPECT_EQ(expectedValues, actualValues);
479 }
480
481 template <typename T>
482 class BitSetArrayTest : public testing::Test
483 {
484 protected:
485 T mBitSet;
486 };
487
488 using BitSetArrayTypes =
489 ::testing::Types<BitSetArray<65>, BitSetArray<128>, BitSetArray<130>, BitSetArray<511>>;
490 TYPED_TEST_SUITE(BitSetArrayTest, BitSetArrayTypes);
491
492 // Basic test of various BitSetArray functionalities
TYPED_TEST(BitSetArrayTest,BasicTest)493 TYPED_TEST(BitSetArrayTest, BasicTest)
494 {
495 TypeParam &mBits = this->mBitSet;
496
497 EXPECT_FALSE(mBits.all());
498 EXPECT_FALSE(mBits.any());
499 EXPECT_TRUE(mBits.none());
500 EXPECT_EQ(mBits.count(), 0u);
501 EXPECT_EQ(mBits.bits(0), 0u);
502
503 // Verify set on a single bit
504 mBits.set(45);
505 for (auto bit : mBits)
506 {
507 EXPECT_EQ(bit, 45u);
508 }
509
510 EXPECT_EQ(mBits.first(), 45u);
511 EXPECT_EQ(mBits.last(), 45u);
512
513 mBits.reset(45);
514
515 // Set every bit to 1.
516 for (size_t i = 0; i < mBits.size(); ++i)
517 {
518 mBits.set(i);
519
520 EXPECT_EQ(mBits.all(), i + 1 == mBits.size());
521 EXPECT_TRUE(mBits.any());
522 EXPECT_FALSE(mBits.none());
523 EXPECT_EQ(mBits.count(), i + 1);
524 }
525
526 // Reset odd bits to 0.
527 for (size_t i = 1; i < mBits.size(); i += 2)
528 {
529 mBits.reset(i);
530
531 EXPECT_FALSE(mBits.all());
532 EXPECT_TRUE(mBits.any());
533 EXPECT_FALSE(mBits.none());
534 EXPECT_EQ(mBits.count(), mBits.size() - i / 2 - 1);
535 }
536
537 // Make sure the bit pattern is what we expect at this point.
538 // All even bits should be set
539 for (size_t i = 0; i < mBits.size(); ++i)
540 {
541 EXPECT_EQ(mBits.test(i), i % 2 == 0);
542 EXPECT_EQ(static_cast<bool>(mBits[i]), i % 2 == 0);
543 }
544
545 // Reset everything.
546 mBits.reset();
547 EXPECT_FALSE(mBits.all());
548 EXPECT_FALSE(mBits.any());
549 EXPECT_TRUE(mBits.none());
550 EXPECT_EQ(mBits.count(), 0u);
551
552 // Test intersection logic
553 TypeParam testBitSet;
554 testBitSet.set(1);
555 EXPECT_EQ(testBitSet.bits(0), (1ul << 1ul));
556 testBitSet.set(3);
557 EXPECT_EQ(testBitSet.bits(0), (1ul << 1ul) | (1ul << 3ul));
558 testBitSet.set(5);
559 EXPECT_EQ(testBitSet.bits(0), (1ul << 1ul) | (1ul << 3ul) | (1ul << 5ul));
560 EXPECT_FALSE(mBits.intersects(testBitSet));
561 mBits.set(3);
562 EXPECT_TRUE(mBits.intersects(testBitSet));
563 mBits.set(4);
564 EXPECT_TRUE(mBits.intersects(testBitSet));
565 mBits.reset(3);
566 EXPECT_FALSE(mBits.intersects(testBitSet));
567 testBitSet.set(4);
568 EXPECT_TRUE(mBits.intersects(testBitSet));
569
570 // Test that flip works.
571 // Reset everything.
572 mBits.reset();
573 EXPECT_EQ(mBits.count(), 0u);
574 mBits.flip();
575 EXPECT_EQ(mBits.count(), mBits.size());
576
577 // Test operators
578
579 // Assignment operators - "=", "&=", "|=" and "^="
580 mBits.reset();
581 mBits = testBitSet;
582 for (auto bit : testBitSet)
583 {
584 EXPECT_TRUE(mBits.test(bit));
585 }
586
587 mBits &= testBitSet;
588 for (auto bit : testBitSet)
589 {
590 EXPECT_TRUE(mBits.test(bit));
591 }
592 EXPECT_EQ(mBits.count(), testBitSet.count());
593
594 mBits.reset();
595 mBits |= testBitSet;
596 for (auto bit : testBitSet)
597 {
598 EXPECT_TRUE(mBits.test(bit));
599 }
600
601 mBits ^= testBitSet;
602 EXPECT_TRUE(mBits.none());
603
604 // Bitwise operators - "&", "|" and "^"
605 std::set<std::size_t> bits1 = {0, 45, 60};
606 std::set<std::size_t> bits2 = {5, 45, 50, 63};
607 std::set<std::size_t> bits1Andbits2 = {45};
608 std::set<std::size_t> bits1Orbits2 = {0, 5, 45, 50, 60, 63};
609 std::set<std::size_t> bits1Xorbits2 = {0, 5, 50, 60, 63};
610 std::set<std::size_t> actualValues;
611 TypeParam testBitSet1;
612 TypeParam testBitSet2;
613
614 for (std::size_t bit : bits1)
615 {
616 testBitSet1.set(bit);
617 }
618 for (std::size_t bit : bits2)
619 {
620 testBitSet2.set(bit);
621 }
622
623 EXPECT_EQ(testBitSet1.first(), 0u);
624 EXPECT_EQ(testBitSet1.last(), 60u);
625
626 EXPECT_EQ(testBitSet2.first(), 5u);
627 EXPECT_EQ(testBitSet2.last(), 63u);
628
629 actualValues.clear();
630 for (auto bit : (testBitSet1 & testBitSet2))
631 {
632 actualValues.insert(bit);
633 }
634 EXPECT_EQ(bits1Andbits2, actualValues);
635
636 actualValues.clear();
637 for (auto bit : (testBitSet1 | testBitSet2))
638 {
639 actualValues.insert(bit);
640 }
641 EXPECT_EQ(bits1Orbits2, actualValues);
642
643 actualValues.clear();
644 for (auto bit : (testBitSet1 ^ testBitSet2))
645 {
646 actualValues.insert(bit);
647 }
648 EXPECT_EQ(bits1Xorbits2, actualValues);
649
650 // Relational operators - "==" and "!="
651 EXPECT_FALSE(testBitSet1 == testBitSet2);
652 EXPECT_TRUE(testBitSet1 != testBitSet2);
653
654 // Unary operators - "~" and "[]"
655 mBits.reset();
656 mBits = ~testBitSet;
657 for (auto bit : mBits)
658 {
659 EXPECT_FALSE(testBitSet.test(bit));
660 }
661 EXPECT_EQ(mBits.count(), (mBits.size() - testBitSet.count()));
662
663 mBits.reset();
664 for (auto bit : testBitSet)
665 {
666 mBits[bit] = true;
667 }
668 for (auto bit : mBits)
669 {
670 EXPECT_TRUE(testBitSet.test(bit));
671 }
672 }
673
674 // Test that BitSetArray's initializer list constructor works correctly.
TEST(BitSetArrayTest,InitializerList)675 TEST(BitSetArrayTest, InitializerList)
676 {
677 BitSetArray<500> bits = BitSetArray<500>{
678 0, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132, 143, 154, 165,
679 176, 187, 198, 209, 220, 231, 242, 253, 264, 275, 286, 297, 308, 319, 330, 341,
680 352, 363, 374, 385, 396, 407, 418, 429, 440, 451, 462, 473, 484, 495,
681 };
682
683 for (size_t i = 0; i < bits.size(); ++i)
684 {
685 if (i % 11 == 0)
686 {
687 EXPECT_TRUE(bits[i]) << i;
688 }
689 else
690 {
691 EXPECT_FALSE(bits[i]) << i;
692 }
693 }
694 }
695
696 // Test that BitSetArray's constructor with uint64_t.
TYPED_TEST(BitSetArrayTest,ConstructorWithUInt64)697 TYPED_TEST(BitSetArrayTest, ConstructorWithUInt64)
698 {
699 uint64_t value = 0x5555555555555555;
700 TypeParam testBitSet(value);
701 for (size_t i = 0; i < testBitSet.size(); ++i)
702 {
703 if (i < sizeof(uint64_t) * 8 && (value & (0x1ull << i)))
704 {
705 EXPECT_TRUE(testBitSet.test(i));
706 }
707 else
708 {
709 EXPECT_FALSE(testBitSet.test(i));
710 }
711 }
712 }
713
714 // Test iteration over BitSetArray where there are gaps
TYPED_TEST(BitSetArrayTest,IterationWithGaps)715 TYPED_TEST(BitSetArrayTest, IterationWithGaps)
716 {
717 TypeParam &mBits = this->mBitSet;
718
719 // Test iterator works with gap in bitset.
720 std::set<size_t> bitsToBeSet = {0, mBits.size() / 2, mBits.size() - 1};
721 for (size_t bit : bitsToBeSet)
722 {
723 mBits.set(bit);
724 }
725 std::set<size_t> bitsActuallySet = {};
726 for (size_t bit : mBits)
727 {
728 bitsActuallySet.insert(bit);
729 }
730 EXPECT_EQ(bitsToBeSet, bitsActuallySet);
731 EXPECT_EQ(mBits.count(), bitsToBeSet.size());
732 mBits.reset();
733 }
734
735 // Test BitSetArray::Mask
TYPED_TEST(BitSetArrayTest,Mask)736 TYPED_TEST(BitSetArrayTest, Mask)
737 {
738 // Test constexpr usage
739 TypeParam bits = TypeParam::Mask(0);
740 for (size_t i = 0; i < bits.size(); ++i)
741 {
742 EXPECT_FALSE(bits[i]) << i;
743 }
744
745 bits = TypeParam::Mask(1);
746 for (size_t i = 0; i < bits.size(); ++i)
747 {
748 if (i < 1)
749 {
750 EXPECT_TRUE(bits[i]) << i;
751 }
752 else
753 {
754 EXPECT_FALSE(bits[i]) << i;
755 }
756 }
757
758 bits = TypeParam::Mask(2);
759 for (size_t i = 0; i < bits.size(); ++i)
760 {
761 if (i < 2)
762 {
763 EXPECT_TRUE(bits[i]) << i;
764 }
765 else
766 {
767 EXPECT_FALSE(bits[i]) << i;
768 }
769 }
770
771 bits = TypeParam::Mask(TypeParam::size());
772 for (size_t i = 0; i < bits.size(); ++i)
773 {
774 EXPECT_TRUE(bits[i]) << i;
775 }
776
777 // Complete test
778 for (size_t i = 0; i < TypeParam::size(); ++i)
779 {
780 bits = TypeParam::Mask(i);
781 for (size_t j = 0; j < bits.size(); ++j)
782 {
783 if (j < i)
784 {
785 EXPECT_TRUE(bits[j]) << j;
786 }
787 else
788 {
789 EXPECT_FALSE(bits[j]) << j;
790 }
791 }
792 }
793 }
794
795 template <typename T>
796 class BitSetArrayIteratorTest : public testing::Test
797 {
798 protected:
799 T mStateBits;
800 typedef T BitSet;
801 };
802
803 using BitSetArrayIteratorTypes = ::testing::Types<BitSetArray<90>, BitSetArray<200>>;
804 TYPED_TEST_SUITE(BitSetArrayIteratorTest, BitSetArrayIteratorTypes);
805
806 // Simple iterator test.
TYPED_TEST(BitSetArrayIteratorTest,Iterator)807 TYPED_TEST(BitSetArrayIteratorTest, Iterator)
808 {
809 TypeParam mStateBits = this->mStateBits;
810 std::set<size_t> originalValues;
811 originalValues.insert(2);
812 originalValues.insert(6);
813 originalValues.insert(8);
814 originalValues.insert(35);
815 if (TypeParam::size() > 70)
816 {
817 originalValues.insert(70);
818 }
819 if (TypeParam::size() > 181)
820 {
821 originalValues.insert(181);
822 }
823
824 for (size_t value : originalValues)
825 {
826 mStateBits.set(value);
827 }
828
829 std::set<size_t> readValues;
830 for (size_t bit : mStateBits)
831 {
832 EXPECT_EQ(1u, originalValues.count(bit));
833 EXPECT_EQ(0u, readValues.count(bit));
834 readValues.insert(bit);
835 }
836
837 EXPECT_EQ(originalValues.size(), readValues.size());
838 }
839
840 // Ensure lsb->msb iteration order.
TYPED_TEST(BitSetArrayIteratorTest,IterationOrder)841 TYPED_TEST(BitSetArrayIteratorTest, IterationOrder)
842 {
843 TypeParam mStateBits = this->mStateBits;
844 const std::array<size_t, 8> writeOrder = {20, 25, 16, 31, 10, 14, 36, 19};
845 const std::array<size_t, 8> fetchOrder = {10, 14, 16, 19, 20, 25, 31, 36};
846
847 for (size_t value : writeOrder)
848 {
849 mStateBits.set(value);
850 }
851 EXPECT_EQ(writeOrder.size(), mStateBits.count());
852
853 size_t i = 0;
854 for (size_t bit : mStateBits)
855 {
856 EXPECT_EQ(fetchOrder[i], bit);
857 i++;
858 }
859 EXPECT_EQ(fetchOrder.size(), mStateBits.count());
860 }
861
862 // Test an empty iterator.
TYPED_TEST(BitSetArrayIteratorTest,EmptySet)863 TYPED_TEST(BitSetArrayIteratorTest, EmptySet)
864 {
865 TypeParam mStateBits = this->mStateBits;
866 // We don't use the FAIL gtest macro here since it returns immediately,
867 // causing an unreachable code warning in MSVS
868 bool sawBit = false;
869 for (size_t bit : mStateBits)
870 {
871 sawBit = true;
872 ANGLE_UNUSED_VARIABLE(bit);
873 }
874 EXPECT_FALSE(sawBit);
875 }
876
877 // Test iterating a result of combining two bitsets.
TYPED_TEST(BitSetArrayIteratorTest,NonLValueBitset)878 TYPED_TEST(BitSetArrayIteratorTest, NonLValueBitset)
879 {
880 TypeParam mStateBits = this->mStateBits;
881 typename TestFixture::BitSet otherBits;
882
883 mStateBits.set(1);
884 mStateBits.set(2);
885 mStateBits.set(3);
886 mStateBits.set(4);
887
888 otherBits.set(0);
889 otherBits.set(1);
890 otherBits.set(3);
891 otherBits.set(5);
892
893 std::set<size_t> seenBits;
894
895 typename TestFixture::BitSet maskedBits = (mStateBits & otherBits);
896 for (size_t bit : maskedBits)
897 {
898 EXPECT_EQ(0u, seenBits.count(bit));
899 seenBits.insert(bit);
900 EXPECT_TRUE(mStateBits[bit]);
901 EXPECT_TRUE(otherBits[bit]);
902 }
903
904 EXPECT_EQ((mStateBits & otherBits).count(), seenBits.size());
905 }
906
907 // Test bit assignments.
TYPED_TEST(BitSetArrayIteratorTest,BitAssignment)908 TYPED_TEST(BitSetArrayIteratorTest, BitAssignment)
909 {
910 TypeParam mStateBits = this->mStateBits;
911 std::set<size_t> originalValues;
912 originalValues.insert(2);
913 originalValues.insert(6);
914 originalValues.insert(8);
915 originalValues.insert(35);
916 if (TypeParam::size() > 70)
917 {
918 originalValues.insert(70);
919 }
920 if (TypeParam::size() > 181)
921 {
922 originalValues.insert(181);
923 }
924
925 for (size_t value : originalValues)
926 {
927 (mStateBits[value] = false) = true;
928 }
929
930 for (size_t value : originalValues)
931 {
932 EXPECT_TRUE(mStateBits.test(value));
933 }
934 }
935
936 // Tests adding bits to the iterator during iteration.
TYPED_TEST(BitSetArrayIteratorTest,SetLaterBit)937 TYPED_TEST(BitSetArrayIteratorTest, SetLaterBit)
938 {
939 TypeParam mStateBits = this->mStateBits;
940 std::set<size_t> expectedValues = {0, 1, 3, 5, 6, 7, 9, 35};
941 if (TypeParam::size() > 64)
942 {
943 expectedValues.insert(64);
944 }
945 if (TypeParam::size() > 199)
946 {
947 expectedValues.insert(199);
948 }
949
950 mStateBits.set(0);
951 mStateBits.set(1);
952
953 std::set<size_t> actualValues;
954
955 for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
956 {
957 if (*iter == 1)
958 {
959 iter.setLaterBit(3);
960 iter.setLaterBit(5);
961 }
962 if (*iter == 5)
963 {
964 iter.setLaterBit(6);
965 iter.setLaterBit(7);
966 iter.setLaterBit(9);
967 iter.setLaterBit(35);
968 }
969 if (*iter == 35 && TypeParam::size() > 64)
970 {
971 iter.setLaterBit(64);
972 }
973 if (*iter == 64 && TypeParam::size() > 199)
974 {
975 iter.setLaterBit(199);
976 }
977
978 actualValues.insert(*iter);
979 }
980
981 EXPECT_EQ(expectedValues, actualValues);
982 }
983
984 // Tests removing bit from the iterator during iteration.
TYPED_TEST(BitSetArrayIteratorTest,ResetLaterBit)985 TYPED_TEST(BitSetArrayIteratorTest, ResetLaterBit)
986 {
987 TypeParam mStateBits = this->mStateBits;
988 std::set<size_t> expectedValues;
989 for (size_t index = 1; index < TypeParam::size(); index += 2)
990 {
991 expectedValues.insert(index);
992 }
993
994 for (size_t index = 1; index < TypeParam::size(); ++index)
995 mStateBits.set(index);
996
997 std::set<size_t> actualValues;
998
999 for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
1000 {
1001 if (*iter == 1)
1002 {
1003 for (size_t index = 2; index < TypeParam::size(); index += 2)
1004 {
1005 iter.resetLaterBit(index);
1006 }
1007 }
1008
1009 actualValues.insert(*iter);
1010 }
1011
1012 EXPECT_EQ(expectedValues, actualValues);
1013 }
1014
1015 // Tests adding bitsets to the iterator during iteration.
TYPED_TEST(BitSetArrayIteratorTest,SetLaterBits)1016 TYPED_TEST(BitSetArrayIteratorTest, SetLaterBits)
1017 {
1018 TypeParam mStateBits = this->mStateBits;
1019 std::set<size_t> expectedValues = {1, 2, 3, 4, 5, 7, 9};
1020 mStateBits.set(1);
1021 mStateBits.set(2);
1022 mStateBits.set(3);
1023
1024 TypeParam laterBits;
1025 laterBits.set(4);
1026 laterBits.set(5);
1027 laterBits.set(7);
1028 laterBits.set(9);
1029
1030 if (TypeParam::size() > 71)
1031 {
1032 expectedValues.insert(71);
1033 laterBits.set(71);
1034 }
1035 if (TypeParam::size() > 155)
1036 {
1037 expectedValues.insert(155);
1038 laterBits.set(155);
1039 }
1040
1041 std::set<size_t> actualValues;
1042
1043 for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
1044 {
1045 if (*iter == 3)
1046 {
1047 iter.setLaterBits(laterBits);
1048 }
1049
1050 EXPECT_EQ(actualValues.count(*iter), 0u);
1051 actualValues.insert(*iter);
1052 }
1053
1054 EXPECT_EQ(expectedValues, actualValues);
1055 }
1056
1057 // Unit test for angle::Bit
TEST(Bit,Test)1058 TEST(Bit, Test)
1059 {
1060 EXPECT_EQ(Bit<uint32_t>(0), 1u);
1061 EXPECT_EQ(Bit<uint32_t>(1), 2u);
1062 EXPECT_EQ(Bit<uint32_t>(2), 4u);
1063 EXPECT_EQ(Bit<uint32_t>(3), 8u);
1064 EXPECT_EQ(Bit<uint32_t>(31), 0x8000'0000u);
1065 EXPECT_EQ(Bit<uint64_t>(63), static_cast<uint64_t>(0x8000'0000'0000'0000llu));
1066 }
1067
1068 // Unit test for angle::BitMask
TEST(BitMask,Test)1069 TEST(BitMask, Test)
1070 {
1071 EXPECT_EQ(BitMask<uint32_t>(1), 1u);
1072 EXPECT_EQ(BitMask<uint32_t>(2), 3u);
1073 EXPECT_EQ(BitMask<uint32_t>(3), 7u);
1074 EXPECT_EQ(BitMask<uint32_t>(31), 0x7FFF'FFFFu);
1075 EXPECT_EQ(BitMask<uint32_t>(32), 0xFFFF'FFFFu);
1076 EXPECT_EQ(BitMask<uint64_t>(63), static_cast<uint64_t>(0x7FFF'FFFF'FFFF'FFFFllu));
1077 EXPECT_EQ(BitMask<uint64_t>(64), static_cast<uint64_t>(0xFFFF'FFFF'FFFF'FFFFllu));
1078 }
1079 } // anonymous namespace
1080