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