1 /*
2 * Copyright © 2019 Red Hat
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21 * IN THE SOFTWARE.
22 */
23
24 #include <gtest/gtest.h>
25 #include "util/bitset.h"
26
TEST(bitset,sizes)27 TEST(bitset, sizes)
28 {
29 EXPECT_EQ(sizeof(BITSET_WORD), 4);
30
31 BITSET_DECLARE(mask32, 32);
32 BITSET_DECLARE(mask64, 64);
33 BITSET_DECLARE(mask128, 128);
34
35 EXPECT_EQ(sizeof(mask32), 4);
36 EXPECT_EQ(sizeof(mask64), 8);
37 EXPECT_EQ(sizeof(mask128), 16);
38 }
39
TEST(bitset,test_set_clear)40 TEST(bitset, test_set_clear)
41 {
42 BITSET_DECLARE(mask128, 128);
43 BITSET_ZERO(mask128);
44
45 for (int i = 0; i < 128; i++) {
46 EXPECT_EQ(BITSET_TEST(mask128, i), false);
47 BITSET_SET(mask128, i);
48 EXPECT_EQ(BITSET_TEST(mask128, i), true);
49 BITSET_CLEAR(mask128, i);
50 EXPECT_EQ(BITSET_TEST(mask128, i), false);
51 }
52 }
53
TEST(bitset,test_set_ones)54 TEST(bitset, test_set_ones)
55 {
56 BITSET_DECLARE(mask128, 128);
57 BITSET_ONES(mask128);
58
59 EXPECT_EQ(BITSET_FFS(mask128), 1);
60
61 for (int i = 0; i < 128; i++) {
62 EXPECT_EQ(BITSET_TEST(mask128, i), true);
63 BITSET_CLEAR(mask128, i);
64 EXPECT_EQ(BITSET_TEST(mask128, i), false);
65 BITSET_SET(mask128, i);
66 EXPECT_EQ(BITSET_TEST(mask128, i), true);
67 }
68 }
69
TEST(bitset,test_basic_range)70 TEST(bitset, test_basic_range)
71 {
72 BITSET_DECLARE(mask128, 128);
73 BITSET_ZERO(mask128);
74
75 const int max_set = 15;
76 BITSET_SET_RANGE_INSIDE_WORD(mask128, 0, max_set);
77 EXPECT_EQ(BITSET_TEST_RANGE_INSIDE_WORD(mask128, 0, max_set), true);
78 EXPECT_EQ(BITSET_TEST_RANGE_INSIDE_WORD(mask128, max_set + 1, max_set + 15), false);
79 for (int i = 0; i < 128; i++) {
80 if (i <= max_set)
81 EXPECT_EQ(BITSET_TEST(mask128, i), true);
82 else
83 EXPECT_EQ(BITSET_TEST(mask128, i), false);
84 }
85 BITSET_CLEAR_RANGE(mask128, 0, max_set);
86 EXPECT_EQ(BITSET_TEST_RANGE_INSIDE_WORD(mask128, 0, max_set), false);
87 for (int i = 0; i < 128; i++) {
88 EXPECT_EQ(BITSET_TEST(mask128, i), false);
89 }
90 }
91
TEST(bitset,test_bitset_ffs)92 TEST(bitset, test_bitset_ffs)
93 {
94 BITSET_DECLARE(mask128, 128);
95 BITSET_ZERO(mask128);
96
97 EXPECT_EQ(BITSET_FFS(mask128), 0);
98
99 BITSET_SET(mask128, 14);
100 EXPECT_EQ(BITSET_FFS(mask128), 15);
101
102 BITSET_SET(mask128, 28);
103 EXPECT_EQ(BITSET_FFS(mask128), 15);
104
105 BITSET_CLEAR(mask128, 14);
106 EXPECT_EQ(BITSET_FFS(mask128), 29);
107
108 BITSET_SET_RANGE_INSIDE_WORD(mask128, 14, 18);
109 EXPECT_EQ(BITSET_FFS(mask128), 15);
110 }
111
TEST(bitset,test_range_bits)112 TEST(bitset, test_range_bits)
113 {
114 BITSET_DECLARE(mask128, 128);
115 BITSET_ZERO(mask128);
116
117 BITSET_SET_RANGE_INSIDE_WORD(mask128, 0, 31);
118 BITSET_SET_RANGE_INSIDE_WORD(mask128, 32, 63);
119 BITSET_SET_RANGE_INSIDE_WORD(mask128, 64, 95);
120 BITSET_SET_RANGE_INSIDE_WORD(mask128, 96, 127);
121 for (int i = 0; i < 128; i++) {
122 EXPECT_EQ(BITSET_TEST(mask128, i), true);
123 }
124
125 BITSET_ZERO(mask128);
126 BITSET_SET_RANGE(mask128, 20, 80);
127 for (int i = 0; i <= 19; i++)
128 EXPECT_EQ(BITSET_TEST(mask128, i), false);
129 for (int i = 20; i <= 80; i++)
130 EXPECT_EQ(BITSET_TEST(mask128, i), true);
131 for (int i = 81; i <= 127; i++)
132 EXPECT_EQ(BITSET_TEST(mask128, i), false);
133
134 BITSET_ZERO(mask128);
135 BITSET_SET(mask128, 20);
136 BITSET_SET(mask128, 80);
137 EXPECT_EQ(BITSET_TEST_RANGE(mask128, 0, 128), true);
138 EXPECT_EQ(BITSET_TEST_RANGE(mask128, 0, 19), false);
139 EXPECT_EQ(BITSET_TEST_RANGE(mask128, 21, 79), false);
140 EXPECT_EQ(BITSET_TEST_RANGE(mask128, 81, 127), false);
141 EXPECT_EQ(BITSET_TEST_RANGE(mask128, 0, 79), true);
142 EXPECT_EQ(BITSET_TEST_RANGE(mask128, 21, 128), true);
143
144 BITSET_ONES(mask128);
145 BITSET_CLEAR_RANGE(mask128, 20, 80);
146 for (int i = 0; i <= 19; i++)
147 EXPECT_EQ(BITSET_TEST(mask128, i), true);
148 for (int i = 20; i <= 80; i++)
149 EXPECT_EQ(BITSET_TEST(mask128, i), false);
150 for (int i = 81; i <= 127; i++)
151 EXPECT_EQ(BITSET_TEST(mask128, i), true);
152 }
153
TEST(bitset,test_and)154 TEST(bitset, test_and)
155 {
156 BITSET_DECLARE(r, 128);
157 BITSET_DECLARE(a, 128);
158 BITSET_DECLARE(b, 128);
159 BITSET_ZERO(r);
160 BITSET_ZERO(a);
161 BITSET_ZERO(b);
162
163 BITSET_AND(r, a, b);
164 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
165 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
166 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
167 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
168
169
170 BITSET_SET_RANGE_INSIDE_WORD(a, 32, 63);
171 BITSET_SET_RANGE_INSIDE_WORD(b, 96, 127);
172 BITSET_AND(r, a, b);
173
174 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
175 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
176 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
177 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
178
179
180 BITSET_SET(a, 80);
181 BITSET_SET(b, 80);
182 BITSET_AND(r, a, b);
183
184 EXPECT_EQ(BITSET_TEST(r, 80), true);
185
186 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
187 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
188 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), true);
189 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
190 }
191
TEST(bitset,test_or)192 TEST(bitset, test_or)
193 {
194 BITSET_DECLARE(r, 128);
195 BITSET_DECLARE(a, 128);
196 BITSET_DECLARE(b, 128);
197 BITSET_ZERO(r);
198 BITSET_ZERO(a);
199 BITSET_ZERO(b);
200
201 BITSET_OR(r, a, b);
202 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
203 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
204 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
205 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
206
207
208 BITSET_SET_RANGE_INSIDE_WORD(a, 32, 63);
209 BITSET_SET_RANGE_INSIDE_WORD(b, 96, 127);
210 BITSET_OR(r, a, b);
211
212 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
213 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
214 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
215 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), true);
216
217
218 BITSET_SET(a, 80);
219 BITSET_OR(r, a, b);
220 EXPECT_EQ(BITSET_TEST(r, 80), true);
221
222 BITSET_SET(b, 81);
223 BITSET_OR(r, a, b);
224 EXPECT_EQ(BITSET_TEST(r, 81), true);
225
226 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
227 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
228 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), true);
229 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), true);
230 }
231
TEST(bitset,test_not)232 TEST(bitset, test_not)
233 {
234 BITSET_DECLARE(r, 128);
235 BITSET_ZERO(r);
236
237 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
238 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
239 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
240 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
241
242 BITSET_NOT(r);
243 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), true);
244 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
245 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), true);
246 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), true);
247
248 BITSET_CLEAR_RANGE(r, 32, 63);
249 BITSET_NOT(r);
250 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
251 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
252 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
253 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
254 }
255
TEST(bitset,test_shr_zero)256 TEST(bitset, test_shr_zero)
257 {
258 BITSET_DECLARE(r, 128);
259
260 BITSET_ZERO(r);
261 BITSET_SET(r, 127);
262
263 BITSET_SHR(r, 0);
264
265 EXPECT_EQ(BITSET_TEST(r, 127), true);
266 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
267 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
268 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
269 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), true);
270 }
271
TEST(bitset,test_shl_zero)272 TEST(bitset, test_shl_zero)
273 {
274 BITSET_DECLARE(r, 128);
275
276 BITSET_ZERO(r);
277 BITSET_SET(r, 0);
278
279 BITSET_SHL(r, 0);
280
281 EXPECT_EQ(BITSET_TEST(r, 0), true);
282 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), true);
283 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
284 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
285 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
286 }
287
TEST(bitset,test_shr_walking_bit)288 TEST(bitset, test_shr_walking_bit)
289 {
290 BITSET_DECLARE(r, 128);
291
292 BITSET_ZERO(r);
293 BITSET_SET(r, 127);
294
295 for (int i = 127; i >= 0; i--) {
296 EXPECT_EQ(BITSET_TEST(r, i), true);
297 BITSET_SHR(r, 1);
298 }
299
300 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
301 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
302 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
303 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
304 }
305
TEST(bitset,test_shl_walking_bit)306 TEST(bitset, test_shl_walking_bit)
307 {
308 BITSET_DECLARE(r, 128);
309
310 BITSET_ZERO(r);
311 BITSET_SET(r, 0);
312
313 for (unsigned int i = 0; i < 128; i++) {
314 EXPECT_EQ(BITSET_TEST(r, i), true);
315 BITSET_SHL(r, 1);
316 }
317
318 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
319 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
320 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
321 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
322 }
323
TEST(bitset,test_shr_multiple_words)324 TEST(bitset, test_shr_multiple_words)
325 {
326 BITSET_DECLARE(r, 128);
327
328 BITSET_ZERO(r);
329 BITSET_SET(r, 127);
330 BITSET_SHR(r, 50);
331
332 EXPECT_EQ(BITSET_TEST(r, 127), false);
333 EXPECT_EQ(BITSET_TEST(r, 77), true);
334
335
336 BITSET_ZERO(r);
337 BITSET_SET(r, 127);
338 BITSET_SHR(r, 80);
339
340 EXPECT_EQ(BITSET_TEST(r, 127), false);
341 EXPECT_EQ(BITSET_TEST(r, 47), true);
342
343
344 BITSET_ZERO(r);
345 BITSET_SET(r, 127);
346 BITSET_SHR(r, 126);
347
348 EXPECT_EQ(BITSET_TEST(r, 127), false);
349 EXPECT_EQ(BITSET_TEST(r, 1), true);
350 }
351
TEST(bitset,test_shl_multiple_words)352 TEST(bitset, test_shl_multiple_words)
353 {
354 BITSET_DECLARE(r, 128);
355
356 BITSET_ZERO(r);
357 BITSET_SET(r, 0);
358 BITSET_SHL(r, 50);
359
360 EXPECT_EQ(BITSET_TEST(r, 0), false);
361 EXPECT_EQ(BITSET_TEST(r, 50), true);
362
363
364 BITSET_ZERO(r);
365 BITSET_SET(r, 0);
366 BITSET_SHL(r, 80);
367
368 EXPECT_EQ(BITSET_TEST(r, 0), false);
369 EXPECT_EQ(BITSET_TEST(r, 80), true);
370
371
372 BITSET_ZERO(r);
373 BITSET_SET(r, 0);
374 BITSET_SHL(r, 126);
375
376 EXPECT_EQ(BITSET_TEST(r, 0), false);
377 EXPECT_EQ(BITSET_TEST(r, 126), true);
378 }
379
TEST(bitset,test_shr_two_words)380 TEST(bitset, test_shr_two_words)
381 {
382 BITSET_DECLARE(r, 64);
383
384 BITSET_ZERO(r);
385 BITSET_SET(r, 63);
386 BITSET_SHR(r, 50);
387
388 EXPECT_EQ(BITSET_TEST(r, 63), false);
389 EXPECT_EQ(BITSET_TEST(r, 13), true);
390 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), true);
391 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
392 }
393
TEST(bitset,test_shl_two_words)394 TEST(bitset, test_shl_two_words)
395 {
396 BITSET_DECLARE(r, 64);
397
398 BITSET_ZERO(r);
399 BITSET_SET(r, 0);
400 BITSET_SHL(r, 50);
401
402 EXPECT_EQ(BITSET_TEST(r, 0), false);
403 EXPECT_EQ(BITSET_TEST(r, 50), true);
404 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
405 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
406 }
407
TEST(bitset,test_setrange_across_word_boundary)408 TEST(bitset, test_setrange_across_word_boundary)
409 {
410 BITSET_DECLARE(r, 128);
411 BITSET_ZERO(r);
412
413 BITSET_SET_RANGE(r, 62, 65);
414
415 EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
416 EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
417 EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), true);
418 EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
419
420 EXPECT_EQ(BITSET_TEST(r, 61), false);
421
422 for (int i = 62; i <= 65; i++)
423 EXPECT_EQ(BITSET_TEST(r, i), true);
424
425 EXPECT_EQ(BITSET_TEST(r, 66), false);
426 }
427