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 <gtest/gtest.h>
11
12 #include "common/bitset_utils.h"
13
14 using namespace angle;
15
16 namespace
17 {
18 template <typename T>
19 class BitSetTest : public testing::Test
20 {
21 protected:
22 T mBits;
23 typedef T BitSet;
24 };
25
26 using BitSetTypes = ::testing::Types<BitSet<12>, BitSet32<12>, BitSet64<12>>;
27 TYPED_TEST_SUITE(BitSetTest, BitSetTypes);
28
TYPED_TEST(BitSetTest,Basic)29 TYPED_TEST(BitSetTest, Basic)
30 {
31 TypeParam mBits = this->mBits;
32 EXPECT_FALSE(mBits.all());
33 EXPECT_FALSE(mBits.any());
34 EXPECT_TRUE(mBits.none());
35 EXPECT_EQ(mBits.count(), 0u);
36
37 // Set every bit to 1.
38 for (size_t i = 0; i < mBits.size(); ++i)
39 {
40 mBits.set(i);
41
42 EXPECT_EQ(mBits.all(), i + 1 == mBits.size());
43 EXPECT_TRUE(mBits.any());
44 EXPECT_FALSE(mBits.none());
45 EXPECT_EQ(mBits.count(), i + 1);
46 }
47
48 // Reset every other bit to 0.
49 for (size_t i = 0; i < mBits.size(); i += 2)
50 {
51 mBits.reset(i);
52
53 EXPECT_FALSE(mBits.all());
54 EXPECT_TRUE(mBits.any());
55 EXPECT_FALSE(mBits.none());
56 EXPECT_EQ(mBits.count(), mBits.size() - i / 2 - 1);
57 }
58
59 // Flip all bits.
60 for (size_t i = 0; i < mBits.size(); ++i)
61 {
62 mBits.flip(i);
63
64 EXPECT_FALSE(mBits.all());
65 EXPECT_TRUE(mBits.any());
66 EXPECT_FALSE(mBits.none());
67 EXPECT_EQ(mBits.count(), mBits.size() / 2 + (i % 2 == 0));
68 }
69
70 // Make sure the bit pattern is what we expect at this point.
71 for (size_t i = 0; i < mBits.size(); ++i)
72 {
73 EXPECT_EQ(mBits.test(i), i % 2 == 0);
74 EXPECT_EQ(static_cast<bool>(mBits[i]), i % 2 == 0);
75 }
76
77 // Test that flip, set and reset all bits at once work.
78 mBits.flip();
79 EXPECT_FALSE(mBits.all());
80 EXPECT_TRUE(mBits.any());
81 EXPECT_FALSE(mBits.none());
82 EXPECT_EQ(mBits.count(), mBits.size() / 2);
83
84 mBits.set();
85 EXPECT_TRUE(mBits.all());
86 EXPECT_TRUE(mBits.any());
87 EXPECT_FALSE(mBits.none());
88 EXPECT_EQ(mBits.count(), mBits.size());
89
90 mBits.reset();
91 EXPECT_FALSE(mBits.all());
92 EXPECT_FALSE(mBits.any());
93 EXPECT_TRUE(mBits.none());
94 EXPECT_EQ(mBits.count(), 0u);
95
96 // Test that out-of-bound sets don't modify the bitset
97 constexpr uint32_t kMask = (1 << 12) - 1;
98
99 EXPECT_EQ(mBits.set(12).bits() & ~kMask, 0u);
100 EXPECT_EQ(mBits.set(13).bits() & ~kMask, 0u);
101 EXPECT_EQ(mBits.flip(12).bits() & ~kMask, 0u);
102 EXPECT_EQ(mBits.flip(13).bits() & ~kMask, 0u);
103 }
104
TYPED_TEST(BitSetTest,BitwiseOperators)105 TYPED_TEST(BitSetTest, BitwiseOperators)
106 {
107 TypeParam mBits = this->mBits;
108 // Use a value that has a 1 in the 12th and 13th bits, to make sure masking to exactly 12 bits
109 // does not have an off-by-one error.
110 constexpr uint32_t kSelfValue = 0xF9E4;
111 constexpr uint32_t kOtherValue = 0x5C6A;
112
113 constexpr uint32_t kMask = (1 << 12) - 1;
114 constexpr uint32_t kSelfMaskedValue = kSelfValue & kMask;
115 constexpr uint32_t kOtherMaskedValue = kOtherValue & kMask;
116
117 constexpr uint32_t kShift = 3;
118 constexpr uint32_t kSelfShiftedLeft = kSelfMaskedValue << kShift & kMask;
119 constexpr uint32_t kSelfShiftedRight = kSelfMaskedValue >> kShift & kMask;
120
121 mBits |= kSelfValue;
122 typename TestFixture::BitSet other(kOtherValue);
123 typename TestFixture::BitSet anded(kSelfMaskedValue & kOtherMaskedValue);
124 typename TestFixture::BitSet ored(kSelfMaskedValue | kOtherMaskedValue);
125 typename TestFixture::BitSet xored(kSelfMaskedValue ^ kOtherMaskedValue);
126
127 EXPECT_EQ(mBits.bits(), kSelfMaskedValue);
128 EXPECT_EQ(other.bits(), kOtherMaskedValue);
129
130 EXPECT_EQ(mBits & other, anded);
131 EXPECT_EQ(mBits | other, ored);
132 EXPECT_EQ(mBits ^ other, xored);
133
134 EXPECT_NE(mBits, other);
135 EXPECT_NE(anded, ored);
136 EXPECT_NE(anded, xored);
137 EXPECT_NE(ored, xored);
138
139 mBits &= other;
140 EXPECT_EQ(mBits, anded);
141
142 mBits |= ored;
143 EXPECT_EQ(mBits, ored);
144
145 mBits ^= other;
146 mBits ^= anded;
147 EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfValue));
148
149 EXPECT_EQ(mBits << kShift, typename TestFixture::BitSet(kSelfShiftedLeft));
150 EXPECT_EQ(mBits >> kShift, typename TestFixture::BitSet(kSelfShiftedRight));
151
152 mBits <<= kShift;
153 EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfShiftedLeft));
154 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
155
156 mBits = typename TestFixture::BitSet(kSelfValue);
157 mBits >>= kShift;
158 EXPECT_EQ(mBits, typename TestFixture::BitSet(kSelfShiftedRight));
159 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
160
161 mBits |= kSelfMaskedValue;
162 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
163 mBits ^= kOtherMaskedValue;
164 EXPECT_EQ(mBits.bits() & ~kMask, 0u);
165 }
166
167 template <typename T>
168 class BitSetIteratorTest : public testing::Test
169 {
170 protected:
171 T mStateBits;
172 typedef T BitSet;
173 };
174
175 using BitSetIteratorTypes = ::testing::Types<BitSet<40>, BitSet64<40>>;
176 TYPED_TEST_SUITE(BitSetIteratorTest, BitSetIteratorTypes);
177
178 // Simple iterator test.
TYPED_TEST(BitSetIteratorTest,Iterator)179 TYPED_TEST(BitSetIteratorTest, Iterator)
180 {
181 TypeParam mStateBits = this->mStateBits;
182 std::set<size_t> originalValues;
183 originalValues.insert(2);
184 originalValues.insert(6);
185 originalValues.insert(8);
186 originalValues.insert(35);
187
188 for (size_t value : originalValues)
189 {
190 mStateBits.set(value);
191 }
192
193 std::set<size_t> readValues;
194 for (size_t bit : mStateBits)
195 {
196 EXPECT_EQ(1u, originalValues.count(bit));
197 EXPECT_EQ(0u, readValues.count(bit));
198 readValues.insert(bit);
199 }
200
201 EXPECT_EQ(originalValues.size(), readValues.size());
202 }
203
204 // Test an empty iterator.
TYPED_TEST(BitSetIteratorTest,EmptySet)205 TYPED_TEST(BitSetIteratorTest, EmptySet)
206 {
207 TypeParam mStateBits = this->mStateBits;
208 // We don't use the FAIL gtest macro here since it returns immediately,
209 // causing an unreachable code warning in MSVS
210 bool sawBit = false;
211 for (size_t bit : mStateBits)
212 {
213 sawBit = true;
214 ANGLE_UNUSED_VARIABLE(bit);
215 }
216 EXPECT_FALSE(sawBit);
217 }
218
219 // Test iterating a result of combining two bitsets.
TYPED_TEST(BitSetIteratorTest,NonLValueBitset)220 TYPED_TEST(BitSetIteratorTest, NonLValueBitset)
221 {
222 TypeParam mStateBits = this->mStateBits;
223 typename TestFixture::BitSet otherBits;
224
225 mStateBits.set(1);
226 mStateBits.set(2);
227 mStateBits.set(3);
228 mStateBits.set(4);
229
230 otherBits.set(0);
231 otherBits.set(1);
232 otherBits.set(3);
233 otherBits.set(5);
234
235 std::set<size_t> seenBits;
236
237 typename TestFixture::BitSet maskedBits = (mStateBits & otherBits);
238 for (size_t bit : maskedBits)
239 {
240 EXPECT_EQ(0u, seenBits.count(bit));
241 seenBits.insert(bit);
242 EXPECT_TRUE(mStateBits[bit]);
243 EXPECT_TRUE(otherBits[bit]);
244 }
245
246 EXPECT_EQ((mStateBits & otherBits).count(), seenBits.size());
247 }
248
249 // Test bit assignments.
TYPED_TEST(BitSetIteratorTest,BitAssignment)250 TYPED_TEST(BitSetIteratorTest, BitAssignment)
251 {
252 TypeParam mStateBits = this->mStateBits;
253 std::set<size_t> originalValues;
254 originalValues.insert(2);
255 originalValues.insert(6);
256 originalValues.insert(8);
257 originalValues.insert(35);
258
259 for (size_t value : originalValues)
260 {
261 (mStateBits[value] = false) = true;
262 }
263
264 for (size_t value : originalValues)
265 {
266 EXPECT_TRUE(mStateBits.test(value));
267 }
268 }
269
270 // Tests adding bits to the iterator during iteration.
TYPED_TEST(BitSetIteratorTest,SetLaterBit)271 TYPED_TEST(BitSetIteratorTest, SetLaterBit)
272 {
273 TypeParam mStateBits = this->mStateBits;
274 std::set<size_t> expectedValues = {1, 3, 5, 7, 9};
275 mStateBits.set(1);
276
277 std::set<size_t> actualValues;
278
279 for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
280 {
281 if (*iter == 1)
282 {
283 iter.setLaterBit(3);
284 iter.setLaterBit(5);
285 iter.setLaterBit(7);
286 iter.setLaterBit(9);
287 }
288
289 actualValues.insert(*iter);
290 }
291
292 EXPECT_EQ(expectedValues, actualValues);
293 }
294
295 // Tests removing bits from the iterator during iteration.
TYPED_TEST(BitSetIteratorTest,ResetLaterBit)296 TYPED_TEST(BitSetIteratorTest, ResetLaterBit)
297 {
298 TypeParam mStateBits = this->mStateBits;
299 std::set<size_t> expectedValues = {1, 3, 5, 7, 9};
300
301 for (size_t index = 1; index <= 9; ++index)
302 mStateBits.set(index);
303
304 std::set<size_t> actualValues;
305
306 for (auto iter = mStateBits.begin(), end = mStateBits.end(); iter != end; ++iter)
307 {
308 if (*iter == 1)
309 {
310 iter.resetLaterBit(2);
311 iter.resetLaterBit(4);
312 iter.resetLaterBit(6);
313 iter.resetLaterBit(8);
314 }
315
316 actualValues.insert(*iter);
317 }
318
319 EXPECT_EQ(expectedValues, actualValues);
320 }
321 } // anonymous namespace
322