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