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
27TEST(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
40TEST(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
54TEST(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
70TEST(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
92TEST(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
112TEST(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
154TEST(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
192TEST(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
232TEST(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
256TEST(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
272TEST(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
288TEST(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
306TEST(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
324TEST(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
352TEST(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
380TEST(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
394TEST(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
408TEST(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