bitset_test.cpp revision 7ec681f3 
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(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
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
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
131TEST(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
169TEST(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
209TEST(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
233TEST(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
249TEST(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
265TEST(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
283TEST(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
301TEST(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
329TEST(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
357TEST(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
371TEST(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
385TEST(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