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(mask128, 0, max_set), true);
78    EXPECT_EQ(BITSET_TEST_RANGE(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(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 
122    EXPECT_EQ(BITSET_TEST_RANGE(mask128, 0, 31), true);
123    EXPECT_EQ(BITSET_TEST_RANGE(mask128, 32, 63), true);
124    EXPECT_EQ(BITSET_TEST_RANGE(mask128, 64, 95), true);
125    EXPECT_EQ(BITSET_TEST_RANGE(mask128, 96, 127), true);
126    for (int i = 0; i < 128; i++) {
127       EXPECT_EQ(BITSET_TEST(mask128, i), true);
128    }
129 }
130 
TEST(bitset,test_and)131 TEST(bitset, test_and)
132 {
133    BITSET_DECLARE(r, 128);
134    BITSET_DECLARE(a, 128);
135    BITSET_DECLARE(b, 128);
136    BITSET_ZERO(r);
137    BITSET_ZERO(a);
138    BITSET_ZERO(b);
139 
140    BITSET_AND(r, a, b);
141    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
142    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
143    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
144    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
145 
146 
147    BITSET_SET_RANGE_INSIDE_WORD(a, 32, 63);
148    BITSET_SET_RANGE_INSIDE_WORD(b, 96, 127);
149    BITSET_AND(r, a, b);
150 
151    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
152    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
153    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
154    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
155 
156 
157    BITSET_SET(a, 80);
158    BITSET_SET(b, 80);
159    BITSET_AND(r, a, b);
160 
161    EXPECT_EQ(BITSET_TEST(r, 80), true);
162 
163    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
164    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
165    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), true);
166    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
167 }
168 
TEST(bitset,test_or)169 TEST(bitset, test_or)
170 {
171    BITSET_DECLARE(r, 128);
172    BITSET_DECLARE(a, 128);
173    BITSET_DECLARE(b, 128);
174    BITSET_ZERO(r);
175    BITSET_ZERO(a);
176    BITSET_ZERO(b);
177 
178    BITSET_OR(r, a, b);
179    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
180    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
181    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
182    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
183 
184 
185    BITSET_SET_RANGE_INSIDE_WORD(a, 32, 63);
186    BITSET_SET_RANGE_INSIDE_WORD(b, 96, 127);
187    BITSET_OR(r, a, b);
188 
189    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
190    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
191    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
192    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), true);
193 
194 
195    BITSET_SET(a, 80);
196    BITSET_OR(r, a, b);
197    EXPECT_EQ(BITSET_TEST(r, 80), true);
198 
199    BITSET_SET(b, 81);
200    BITSET_OR(r, a, b);
201    EXPECT_EQ(BITSET_TEST(r, 81), true);
202 
203    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
204    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
205    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), true);
206    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), true);
207 }
208 
TEST(bitset,test_not)209 TEST(bitset, test_not)
210 {
211    BITSET_DECLARE(r, 128);
212    BITSET_ZERO(r);
213 
214    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
215    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
216    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
217    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
218 
219    BITSET_NOT(r);
220    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), true);
221    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
222    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), true);
223    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), true);
224 
225    BITSET_CLEAR_RANGE(r, 32, 63);
226    BITSET_NOT(r);
227    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
228    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
229    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
230    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
231 }
232 
TEST(bitset,test_shr_zero)233 TEST(bitset, test_shr_zero)
234 {
235    BITSET_DECLARE(r, 128);
236 
237    BITSET_ZERO(r);
238    BITSET_SET(r, 127);
239 
240    BITSET_SHR(r, 0);
241 
242    EXPECT_EQ(BITSET_TEST(r, 127), true);
243    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
244    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
245    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
246    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), true);
247 }
248 
TEST(bitset,test_shl_zero)249 TEST(bitset, test_shl_zero)
250 {
251    BITSET_DECLARE(r, 128);
252 
253    BITSET_ZERO(r);
254    BITSET_SET(r, 0);
255 
256    BITSET_SHL(r, 0);
257 
258    EXPECT_EQ(BITSET_TEST(r, 0), true);
259    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), true);
260    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
261    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
262    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
263 }
264 
TEST(bitset,test_shr_walking_bit)265 TEST(bitset, test_shr_walking_bit)
266 {
267    BITSET_DECLARE(r, 128);
268 
269    BITSET_ZERO(r);
270    BITSET_SET(r, 127);
271 
272    for (int i = 127; i >= 0; i--) {
273       EXPECT_EQ(BITSET_TEST(r, i), true);
274       BITSET_SHR(r, 1);
275    }
276 
277    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
278    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
279    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
280    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
281 }
282 
TEST(bitset,test_shl_walking_bit)283 TEST(bitset, test_shl_walking_bit)
284 {
285    BITSET_DECLARE(r, 128);
286 
287    BITSET_ZERO(r);
288    BITSET_SET(r, 0);
289 
290    for (unsigned int i = 0; i < 128; i++) {
291       EXPECT_EQ(BITSET_TEST(r, i), true);
292       BITSET_SHL(r, 1);
293    }
294 
295    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
296    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
297    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), false);
298    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
299 }
300 
TEST(bitset,test_shr_multiple_words)301 TEST(bitset, test_shr_multiple_words)
302 {
303    BITSET_DECLARE(r, 128);
304 
305    BITSET_ZERO(r);
306    BITSET_SET(r, 127);
307    BITSET_SHR(r, 50);
308 
309    EXPECT_EQ(BITSET_TEST(r, 127), false);
310    EXPECT_EQ(BITSET_TEST(r, 77), true);
311 
312 
313    BITSET_ZERO(r);
314    BITSET_SET(r, 127);
315    BITSET_SHR(r, 80);
316 
317    EXPECT_EQ(BITSET_TEST(r, 127), false);
318    EXPECT_EQ(BITSET_TEST(r, 47), true);
319 
320 
321    BITSET_ZERO(r);
322    BITSET_SET(r, 127);
323    BITSET_SHR(r, 126);
324 
325    EXPECT_EQ(BITSET_TEST(r, 127), false);
326    EXPECT_EQ(BITSET_TEST(r, 1), true);
327 }
328 
TEST(bitset,test_shl_multiple_words)329 TEST(bitset, test_shl_multiple_words)
330 {
331    BITSET_DECLARE(r, 128);
332 
333    BITSET_ZERO(r);
334    BITSET_SET(r, 0);
335    BITSET_SHL(r, 50);
336 
337    EXPECT_EQ(BITSET_TEST(r, 0), false);
338    EXPECT_EQ(BITSET_TEST(r, 50), true);
339 
340 
341    BITSET_ZERO(r);
342    BITSET_SET(r, 0);
343    BITSET_SHL(r, 80);
344 
345    EXPECT_EQ(BITSET_TEST(r, 0), false);
346    EXPECT_EQ(BITSET_TEST(r, 80), true);
347 
348 
349    BITSET_ZERO(r);
350    BITSET_SET(r, 0);
351    BITSET_SHL(r, 126);
352 
353    EXPECT_EQ(BITSET_TEST(r, 0), false);
354    EXPECT_EQ(BITSET_TEST(r, 126), true);
355 }
356 
TEST(bitset,test_shr_two_words)357 TEST(bitset, test_shr_two_words)
358 {
359    BITSET_DECLARE(r, 64);
360 
361    BITSET_ZERO(r);
362    BITSET_SET(r, 63);
363    BITSET_SHR(r, 50);
364 
365    EXPECT_EQ(BITSET_TEST(r, 63), false);
366    EXPECT_EQ(BITSET_TEST(r, 13), true);
367    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), true);
368    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), false);
369 }
370 
TEST(bitset,test_shl_two_words)371 TEST(bitset, test_shl_two_words)
372 {
373    BITSET_DECLARE(r, 64);
374 
375    BITSET_ZERO(r);
376    BITSET_SET(r, 0);
377    BITSET_SHL(r, 50);
378 
379    EXPECT_EQ(BITSET_TEST(r, 0), false);
380    EXPECT_EQ(BITSET_TEST(r, 50), true);
381    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
382    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
383 }
384 
TEST(bitset,test_setrange_across_word_boundary)385 TEST(bitset, test_setrange_across_word_boundary)
386 {
387    BITSET_DECLARE(r, 128);
388    BITSET_ZERO(r);
389 
390    BITSET_SET_RANGE(r, 62, 65);
391 
392    EXPECT_EQ(BITSET_TEST_RANGE(r, 0, 31), false);
393    EXPECT_EQ(BITSET_TEST_RANGE(r, 32, 63), true);
394    EXPECT_EQ(BITSET_TEST_RANGE(r, 64, 95), true);
395    EXPECT_EQ(BITSET_TEST_RANGE(r, 96, 127), false);
396 
397    EXPECT_EQ(BITSET_TEST(r, 61), false);
398 
399    for (int i = 62; i <= 65; i++)
400       EXPECT_EQ(BITSET_TEST(r, i), true);
401 
402    EXPECT_EQ(BITSET_TEST(r, 66), false);
403 }
404