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