1 /*-
2 * Copyright (c) 2014 Spectra Logic Corporation
3 * Copyright (c) 2023 Klara, Inc.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions, and the following disclaimer,
11 * without modification.
12 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
13 * substantially similar to the "NO WARRANTY" disclaimer below
14 * ("Disclaimer") and any redistribution must be conditioned upon
15 * including a substantially similar Disclaimer requirement for further
16 * binary redistribution.
17 *
18 * NO WARRANTY
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
27 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
28 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGES.
30 */
31
32 #include <sys/param.h>
33
34 #include <bitstring.h>
35 #include <malloc_np.h>
36
37 #include <atf-c.h>
38
39 typedef void (testfunc_t)(bitstr_t *bstr, int nbits, const char *memloc);
40
41 static void
bitstring_run_stack_test(testfunc_t * test,int nbits)42 bitstring_run_stack_test(testfunc_t *test, int nbits)
43 {
44 bitstr_t bit_decl(bitstr, nbits);
45
46 test(bitstr, nbits, "stack");
47 }
48
49 static void
bitstring_run_heap_test(testfunc_t * test,int nbits)50 bitstring_run_heap_test(testfunc_t *test, int nbits)
51 {
52 bitstr_t *bitstr = bit_alloc(nbits);
53
54 test(bitstr, nbits, "heap");
55 free(bitstr);
56 }
57
58 static void
bitstring_test_runner(testfunc_t * test)59 bitstring_test_runner(testfunc_t *test)
60 {
61 const int bitstr_sizes[] = {
62 0,
63 1,
64 _BITSTR_BITS - 1,
65 _BITSTR_BITS,
66 _BITSTR_BITS + 1,
67 2 * _BITSTR_BITS - 1,
68 2 * _BITSTR_BITS,
69 1023,
70 1024
71 };
72
73 for (unsigned long i = 0; i < nitems(bitstr_sizes); i++) {
74 bitstring_run_stack_test(test, bitstr_sizes[i]);
75 bitstring_run_heap_test(test, bitstr_sizes[i]);
76 }
77 }
78
79 #define BITSTRING_TC_DEFINE(name) \
80 ATF_TC_WITHOUT_HEAD(name); \
81 static testfunc_t name ## _test; \
82 \
83 ATF_TC_BODY(name, tc) \
84 { \
85 bitstring_test_runner(name ## _test); \
86 } \
87 \
88 static void \
89 name ## _test(bitstr_t *bitstr, int nbits, const char *memloc)
90
91 #define BITSTRING_TC_ADD(tp, name) \
92 do { \
93 ATF_TP_ADD_TC(tp, name); \
94 } while (0)
95
96 ATF_TC_WITHOUT_HEAD(bitstr_in_struct);
ATF_TC_BODY(bitstr_in_struct,tc)97 ATF_TC_BODY(bitstr_in_struct, tc)
98 {
99 struct bitstr_containing_struct {
100 bitstr_t bit_decl(bitstr, 8);
101 } test_struct;
102
103 bit_nclear(test_struct.bitstr, 0, 8);
104 }
105
106 ATF_TC_WITHOUT_HEAD(bitstr_size);
ATF_TC_BODY(bitstr_size,tc)107 ATF_TC_BODY(bitstr_size, tc)
108 {
109 size_t sob = sizeof(bitstr_t);
110
111 ATF_CHECK_EQ(0, bitstr_size(0));
112 ATF_CHECK_EQ(sob, bitstr_size(1));
113 ATF_CHECK_EQ(sob, bitstr_size(sob * 8));
114 ATF_CHECK_EQ(2 * sob, bitstr_size(sob * 8 + 1));
115 }
116
BITSTRING_TC_DEFINE(bit_set)117 BITSTRING_TC_DEFINE(bit_set)
118 /* bitstr_t *bitstr, int nbits, const char *memloc */
119 {
120 memset(bitstr, 0, bitstr_size(nbits));
121
122 for (int i = 0; i < nbits; i++) {
123 bit_set(bitstr, i);
124
125 for (int j = 0; j < nbits; j++) {
126 ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 1 : 0,
127 "bit_set_%d_%s: Failed on bit %d",
128 nbits, memloc, i);
129 }
130
131 bit_clear(bitstr, i);
132 }
133 }
134
BITSTRING_TC_DEFINE(bit_clear)135 BITSTRING_TC_DEFINE(bit_clear)
136 /* bitstr_t *bitstr, int nbits, const char *memloc */
137 {
138 int i, j;
139
140 memset(bitstr, 0xFF, bitstr_size(nbits));
141 for (i = 0; i < nbits; i++) {
142 bit_clear(bitstr, i);
143
144 for (j = 0; j < nbits; j++) {
145 ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 0 : 1,
146 "bit_clear_%d_%s: Failed on bit %d",
147 nbits, memloc, i);
148 }
149
150 bit_set(bitstr, i);
151 }
152 }
153
BITSTRING_TC_DEFINE(bit_ffs)154 BITSTRING_TC_DEFINE(bit_ffs)
155 /* bitstr_t *bitstr, int nbits, const char *memloc */
156 {
157 int i;
158 int found_set_bit;
159
160 memset(bitstr, 0, bitstr_size(nbits));
161 bit_ffs(bitstr, nbits, &found_set_bit);
162 ATF_REQUIRE_MSG(found_set_bit == -1,
163 "bit_ffs_%d_%s: Failed all clear bits.", nbits, memloc);
164
165 for (i = 0; i < nbits; i++) {
166 memset(bitstr, 0xFF, bitstr_size(nbits));
167 if (i > 0)
168 bit_nclear(bitstr, 0, i - 1);
169
170 bit_ffs(bitstr, nbits, &found_set_bit);
171 ATF_REQUIRE_MSG(found_set_bit == i,
172 "bit_ffs_%d_%s: Failed on bit %d, Result %d",
173 nbits, memloc, i, found_set_bit);
174 }
175 }
176
BITSTRING_TC_DEFINE(bit_ffc)177 BITSTRING_TC_DEFINE(bit_ffc)
178 /* bitstr_t *bitstr, int nbits, const char *memloc */
179 {
180 int i;
181 int found_clear_bit;
182
183 memset(bitstr, 0xFF, bitstr_size(nbits));
184 bit_ffc(bitstr, nbits, &found_clear_bit);
185 ATF_REQUIRE_MSG(found_clear_bit == -1,
186 "bit_ffc_%d_%s: Failed all set bits.", nbits, memloc);
187
188 for (i = 0; i < nbits; i++) {
189 memset(bitstr, 0, bitstr_size(nbits));
190 if (i > 0)
191 bit_nset(bitstr, 0, i - 1);
192
193 bit_ffc(bitstr, nbits, &found_clear_bit);
194 ATF_REQUIRE_MSG(found_clear_bit == i,
195 "bit_ffc_%d_%s: Failed on bit %d, Result %d",
196 nbits, memloc, i, found_clear_bit);
197 }
198 }
199
BITSTRING_TC_DEFINE(bit_ffs_at)200 BITSTRING_TC_DEFINE(bit_ffs_at)
201 /* bitstr_t *bitstr, int nbits, const char *memloc */
202 {
203 int i;
204 int found_set_bit;
205
206 memset(bitstr, 0xFF, bitstr_size(nbits));
207 for (i = 0; i < nbits; i++) {
208 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
209 ATF_REQUIRE_MSG(found_set_bit == i,
210 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
211 nbits, memloc, i, found_set_bit);
212 }
213
214 memset(bitstr, 0, bitstr_size(nbits));
215 for (i = 0; i < nbits; i++) {
216 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
217 ATF_REQUIRE_MSG(found_set_bit == -1,
218 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
219 nbits, memloc, i, found_set_bit);
220 }
221
222 memset(bitstr, 0x55, bitstr_size(nbits));
223 for (i = 0; i < nbits; i++) {
224 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
225 if (i == nbits - 1 && (nbits & 1) == 0) {
226 ATF_REQUIRE_MSG(found_set_bit == -1,
227 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
228 nbits, memloc, i, found_set_bit);
229 } else {
230 ATF_REQUIRE_MSG(found_set_bit == i + (i & 1),
231 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
232 nbits, memloc, i, found_set_bit);
233 }
234 }
235
236 memset(bitstr, 0xAA, bitstr_size(nbits));
237 for (i = 0; i < nbits; i++) {
238 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
239 if (i == nbits - 1 && (nbits & 1) != 0) {
240 ATF_REQUIRE_MSG(found_set_bit == -1,
241 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
242 nbits, memloc, i, found_set_bit);
243 } else {
244 ATF_REQUIRE_MSG(
245 found_set_bit == i + ((i & 1) ? 0 : 1),
246 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
247 nbits, memloc, i, found_set_bit);
248 }
249 }
250
251 /* Pass a start value beyond the size of the bit string */
252 bit_ffs_at(bitstr, nbits, nbits, &found_set_bit);
253 ATF_REQUIRE_MSG(found_set_bit == -1,
254 "bit_ffs_at_%d_%s: Failed with high start value of %d, Result %d",
255 nbits, memloc, nbits, found_set_bit);
256
257 bit_ffs_at(bitstr, nbits + 3, nbits, &found_set_bit);
258 ATF_REQUIRE_MSG(found_set_bit == -1,
259 "bit_ffs_at_%d_%s: Failed with high start value of %d, Result %d",
260 nbits, memloc, nbits + 3, found_set_bit);
261 }
262
BITSTRING_TC_DEFINE(bit_ffc_at)263 BITSTRING_TC_DEFINE(bit_ffc_at)
264 /* bitstr_t *bitstr, int nbits, const char *memloc */
265 {
266 int i, found_clear_bit;
267
268 memset(bitstr, 0, bitstr_size(nbits));
269 for (i = 0; i < nbits; i++) {
270 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
271 ATF_REQUIRE_MSG(found_clear_bit == i,
272 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
273 nbits, memloc, i, found_clear_bit);
274 }
275
276 memset(bitstr, 0xFF, bitstr_size(nbits));
277 for (i = 0; i < nbits; i++) {
278 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
279 ATF_REQUIRE_MSG(found_clear_bit == -1,
280 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
281 nbits, memloc, i, found_clear_bit);
282 }
283
284 memset(bitstr, 0x55, bitstr_size(nbits));
285 for (i = 0; i < nbits; i++) {
286 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
287 if (i == nbits - 1 && (nbits & 1) != 0) {
288 ATF_REQUIRE_MSG(found_clear_bit == -1,
289 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
290 nbits, memloc, i, found_clear_bit);
291 } else {
292 ATF_REQUIRE_MSG(
293 found_clear_bit == i + ((i & 1) ? 0 : 1),
294 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
295 nbits, memloc, i, found_clear_bit);
296 }
297 }
298
299 memset(bitstr, 0xAA, bitstr_size(nbits));
300 for (i = 0; i < nbits; i++) {
301 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
302 if (i == nbits - 1 && (nbits & 1) == 0) {
303 ATF_REQUIRE_MSG(found_clear_bit == -1,
304 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
305 nbits, memloc, i, found_clear_bit);
306 } else {
307 ATF_REQUIRE_MSG(found_clear_bit == i + (i & 1),
308 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
309 nbits, memloc, i, found_clear_bit);
310 }
311 }
312
313 /* Pass a start value beyond the size of the bit string */
314 bit_ffc_at(bitstr, nbits, nbits, &found_clear_bit);
315 ATF_REQUIRE_MSG(found_clear_bit == -1,
316 "bit_ffc_at_%d_%s: Failed with high start value, Result %d",
317 nbits, memloc, found_clear_bit);
318
319 bit_ffc_at(bitstr, nbits + 3, nbits, &found_clear_bit);
320 ATF_REQUIRE_MSG(found_clear_bit == -1,
321 "bit_ffc_at_%d_%s: Failed with high start value of %d, Result %d",
322 nbits, memloc, nbits + 3, found_clear_bit);
323 }
324
BITSTRING_TC_DEFINE(bit_ffc_area_at_all_or_nothing)325 BITSTRING_TC_DEFINE(bit_ffc_area_at_all_or_nothing)
326 /* bitstr_t *bitstr, int nbits, const char *memloc */
327 {
328 int found;
329
330 memset(bitstr, 0, bitstr_size(nbits));
331 if (nbits % _BITSTR_BITS != 0)
332 bit_nset(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1);
333
334 for (int start = 0; start < nbits; start++) {
335 for (int size = 1; size < nbits - start; size++) {
336 bit_ffc_area_at(bitstr, start, nbits, size, &found);
337 ATF_REQUIRE_EQ_MSG(start, found,
338 "bit_ffc_area_at_%d_%s: "
339 "Did not find %d clear bits at %d",
340 nbits, memloc, size, start);
341 }
342 }
343
344 memset(bitstr, 0xff, bitstr_size(nbits));
345 if (nbits % _BITSTR_BITS != 0)
346 bit_nclear(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1);
347
348 for (int start = 0; start < nbits; start++) {
349 for (int size = 1; size < nbits - start; size++) {
350 bit_ffc_area_at(bitstr, start, nbits, size, &found);
351 ATF_REQUIRE_EQ_MSG(-1, found,
352 "bit_ffc_area_at_%d_%s: "
353 "Found %d clear bits at %d",
354 nbits, memloc, size, start);
355 }
356 }
357 }
358
BITSTRING_TC_DEFINE(bit_ffs_area_at_all_or_nothing)359 BITSTRING_TC_DEFINE(bit_ffs_area_at_all_or_nothing)
360 /* bitstr_t *bitstr, int nbits, const char *memloc */
361 {
362 int found;
363
364 memset(bitstr, 0, bitstr_size(nbits));
365 if (nbits % _BITSTR_BITS != 0)
366 bit_nset(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1);
367
368 for (int start = 0; start < nbits; start++) {
369 for (int size = 1; size < nbits - start; size++) {
370 bit_ffs_area_at(bitstr, start, nbits, size, &found);
371 ATF_REQUIRE_EQ_MSG(-1, found,
372 "bit_ffs_area_at_%d_%s: "
373 "Found %d set bits at %d",
374 nbits, memloc, size, start);
375 }
376 }
377
378 memset(bitstr, 0xff, bitstr_size(nbits));
379 if (nbits % _BITSTR_BITS != 0)
380 bit_nclear(bitstr, nbits, roundup2(nbits, _BITSTR_BITS) - 1);
381
382 for (int start = 0; start < nbits; start++) {
383 for (int size = 1; size < nbits - start; size++) {
384 bit_ffs_area_at(bitstr, start, nbits, size, &found);
385 ATF_REQUIRE_EQ_MSG(start, found,
386 "bit_ffs_area_at_%d_%s: "
387 "Did not find %d set bits at %d",
388 nbits, memloc, size, start);
389 }
390 }
391 }
392
393 ATF_TC_WITHOUT_HEAD(bit_ffs_area);
ATF_TC_BODY(bit_ffs_area,tc)394 ATF_TC_BODY(bit_ffs_area, tc)
395 {
396 const int nbits = 72;
397 bitstr_t bit_decl(bitstr, nbits);
398 int location;
399
400 memset(bitstr, 0, bitstr_size(nbits));
401
402 bit_nset(bitstr, 5, 6);
403
404 location = 0;
405 bit_ffs_area(bitstr, nbits, 3, &location);
406 ATF_REQUIRE_EQ_MSG(-1, location,
407 "bit_ffs_area: found location of size 3 when only 2 bits are set");
408 ATF_REQUIRE_EQ_MSG(0, bit_ntest(bitstr, 5, 7, 1),
409 "bit_ntest: found location of size 3 when only 2 bits are set");
410
411 bit_set(bitstr, 7);
412
413 location = 0;
414 bit_ffs_area(bitstr, nbits, 3, &location);
415 ATF_REQUIRE_EQ_MSG(5, location,
416 "bit_ffs_area: failed to find location of size 3 %d", location);
417 ATF_REQUIRE_EQ_MSG(1, bit_ntest(bitstr, 5, 7, 1),
418 "bit_ntest: failed to find all 3 bits set");
419
420 bit_set(bitstr, 8);
421
422 location = 0;
423 bit_ffs_area(bitstr, nbits, 3, &location);
424 ATF_REQUIRE_EQ_MSG(5, location,
425 "bit_ffs_area: failed to find location of size 3");
426
427 location = 0;
428 bit_ffs_area_at(bitstr, 2, nbits, 3, &location);
429 ATF_REQUIRE_EQ_MSG(5, location,
430 "bit_ffs_area_at: failed to find location of size 3");
431
432 location = 0;
433 bit_ffs_area_at(bitstr, 6, nbits, 3, &location);
434 ATF_REQUIRE_EQ_MSG(6, location,
435 "bit_ffs_area_at: failed to find location of size 3");
436
437 location = 0;
438 bit_ffs_area_at(bitstr, 8, nbits, 3, &location);
439 ATF_REQUIRE_EQ_MSG(-1, location,
440 "bit_ffs_area_at: found invalid location");
441
442 bit_nset(bitstr, 69, 71);
443
444 location = 0;
445 bit_ffs_area_at(bitstr, 8, nbits, 3, &location);
446 ATF_REQUIRE_EQ_MSG(69, location,
447 "bit_ffs_area_at: failed to find location of size 3");
448
449 location = 0;
450 bit_ffs_area_at(bitstr, 69, nbits, 3, &location);
451 ATF_REQUIRE_EQ_MSG(69, location,
452 "bit_ffs_area_at: failed to find location of size 3");
453
454 location = 0;
455 bit_ffs_area_at(bitstr, 70, nbits, 3, &location);
456 ATF_REQUIRE_EQ_MSG(-1, location,
457 "bit_ffs_area_at: found invalid location");
458
459 location = 0;
460 bit_ffs_area_at(bitstr, 72, nbits, 3, &location);
461 ATF_REQUIRE_EQ_MSG(-1, location,
462 "bit_ffs_area_at: found invalid location");
463
464 bit_nset(bitstr, 59, 67);
465
466 location = 0;
467 bit_ffs_area(bitstr, nbits, 9, &location);
468 ATF_REQUIRE_EQ_MSG(59, location,
469 "bit_ffs_area: failed to find location of size 9");
470
471 location = 0;
472 bit_ffs_area(bitstr, nbits, 10, &location);
473 ATF_REQUIRE_EQ_MSG(-1, location,
474 "bit_ffs_area: found invalid location");
475 }
476
477 ATF_TC_WITHOUT_HEAD(bit_ffc_area);
ATF_TC_BODY(bit_ffc_area,tc)478 ATF_TC_BODY(bit_ffc_area, tc)
479 {
480 const int nbits = 80;
481 bitstr_t bit_decl(bitstr, nbits);
482 int location;
483
484 /* set all bits */
485 memset(bitstr, 0xFF, bitstr_size(nbits));
486
487 bit_clear(bitstr, 7);
488 bit_clear(bitstr, 8);
489
490 location = 0;
491 bit_ffc_area(bitstr, nbits, 3, &location);
492 ATF_REQUIRE_EQ_MSG(-1, location,
493 "bit_ffc_area: found location of size 3 when only 2 bits are set");
494
495 bit_clear(bitstr, 9);
496
497 location = 0;
498 bit_ffc_area(bitstr, nbits, 3, &location);
499 ATF_REQUIRE_EQ_MSG(7, location,
500 "bit_ffc_area: failed to find location of size 3");
501
502 bit_clear(bitstr, 10);
503
504 location = 0;
505 bit_ffc_area(bitstr, nbits, 3, &location);
506 ATF_REQUIRE_EQ_MSG(7, location,
507 "bit_ffc_area: failed to find location of size 3");
508
509 location = 0;
510 bit_ffc_area_at(bitstr, 2, nbits, 3, &location);
511 ATF_REQUIRE_EQ_MSG(7, location,
512 "bit_ffc_area_at: failed to find location of size 3");
513
514 location = 0;
515 bit_ffc_area_at(bitstr, 8, nbits, 3, &location);
516 ATF_REQUIRE_EQ_MSG(8, location,
517 "bit_ffc_area_at: failed to find location of size 3");
518
519 location = 0;
520 bit_ffc_area_at(bitstr, 9, nbits, 3, &location);
521 ATF_REQUIRE_EQ_MSG(-1, location,
522 "bit_ffc_area_at: found invalid bit location");
523
524 bit_clear(bitstr, 77);
525 bit_clear(bitstr, 78);
526 bit_clear(bitstr, 79);
527
528 location = 0;
529 bit_ffc_area_at(bitstr, 12, nbits, 3, &location);
530 ATF_REQUIRE_EQ_MSG(77, location,
531 "bit_ffc_area_at: failed to find location of size 3");
532
533 location = 0;
534 bit_ffc_area_at(bitstr, 77, nbits, 3, &location);
535 ATF_REQUIRE_EQ_MSG(77, location,
536 "bit_ffc_area_at: failed to find location of size 3");
537
538 location = 0;
539 bit_ffc_area_at(bitstr, 78, nbits, 3, &location);
540 ATF_REQUIRE_EQ_MSG(-1, location,
541 "bit_ffc_area_at: found invalid location");
542
543 location = 0;
544 bit_ffc_area_at(bitstr, 85, nbits, 3, &location);
545 ATF_REQUIRE_EQ_MSG(-1, location,
546 "bit_ffc_area_at: found invalid location");
547 }
548
BITSTRING_TC_DEFINE(bit_nclear)549 BITSTRING_TC_DEFINE(bit_nclear)
550 /* bitstr_t *bitstr, int nbits, const char *memloc */
551 {
552 int i, j;
553 int found_set_bit;
554 int found_clear_bit;
555
556 for (i = 0; i < nbits; i++) {
557 for (j = i; j < nbits; j++) {
558 memset(bitstr, 0xFF, bitstr_size(nbits));
559 bit_nclear(bitstr, i, j);
560
561 bit_ffc(bitstr, nbits, &found_clear_bit);
562 ATF_REQUIRE_INTEQ_MSG(i, found_clear_bit,
563 "bit_nclear_%d_%d_%d%s: Failed with result %d",
564 nbits, i, j, memloc, found_clear_bit);
565
566 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
567 ATF_REQUIRE_INTEQ_MSG((j + 1 < nbits) ? j + 1 : -1,
568 found_set_bit,
569 "bit_nset_%d_%d_%d%s: Failed with result %d",
570 nbits, i, j, memloc, found_set_bit);
571 }
572 }
573 }
574
BITSTRING_TC_DEFINE(bit_nset)575 BITSTRING_TC_DEFINE(bit_nset)
576 /* bitstr_t *bitstr, int nbits, const char *memloc */
577 {
578 int i, j;
579 int found_set_bit;
580 int found_clear_bit;
581
582 for (i = 0; i < nbits; i++) {
583 for (j = i; j < nbits; j++) {
584 memset(bitstr, 0, bitstr_size(nbits));
585 bit_nset(bitstr, i, j);
586
587 bit_ffs(bitstr, nbits, &found_set_bit);
588 ATF_REQUIRE_INTEQ_MSG(i, found_set_bit,
589 "bit_nset_%d_%d_%d%s: Failed with result %d",
590 nbits, i, j, memloc, found_set_bit);
591
592 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
593 ATF_REQUIRE_INTEQ_MSG((j + 1 < nbits) ? j + 1 : -1,
594 found_clear_bit,
595 "bit_nset_%d_%d_%d%s: Failed with result %d",
596 nbits, i, j, memloc, found_clear_bit);
597 }
598 }
599 }
600
BITSTRING_TC_DEFINE(bit_count)601 BITSTRING_TC_DEFINE(bit_count)
602 /* bitstr_t *bitstr, int nbits, const char *memloc */
603 {
604 int result, s, e, expected;
605
606 /* Empty bitstr */
607 memset(bitstr, 0, bitstr_size(nbits));
608 bit_count(bitstr, 0, nbits, &result);
609 ATF_CHECK_MSG(0 == result,
610 "bit_count_%d_%s_%s: Failed with result %d",
611 nbits, "clear", memloc, result);
612
613 /* Full bitstr */
614 memset(bitstr, 0xFF, bitstr_size(nbits));
615 bit_count(bitstr, 0, nbits, &result);
616 ATF_CHECK_MSG(nbits == result,
617 "bit_count_%d_%s_%s: Failed with result %d",
618 nbits, "set", memloc, result);
619
620 /* Invalid _start value */
621 memset(bitstr, 0xFF, bitstr_size(nbits));
622 bit_count(bitstr, nbits, nbits, &result);
623 ATF_CHECK_MSG(0 == result,
624 "bit_count_%d_%s_%s: Failed with result %d",
625 nbits, "invalid_start", memloc, result);
626
627 /* Alternating bitstr, starts with 0 */
628 memset(bitstr, 0xAA, bitstr_size(nbits));
629 bit_count(bitstr, 0, nbits, &result);
630 ATF_CHECK_MSG(nbits / 2 == result,
631 "bit_count_%d_%s_%d_%s: Failed with result %d",
632 nbits, "alternating", 0, memloc, result);
633
634 /* Alternating bitstr, starts with 1 */
635 memset(bitstr, 0x55, bitstr_size(nbits));
636 bit_count(bitstr, 0, nbits, &result);
637 ATF_CHECK_MSG((nbits + 1) / 2 == result,
638 "bit_count_%d_%s_%d_%s: Failed with result %d",
639 nbits, "alternating", 1, memloc, result);
640
641 /* Varying start location */
642 memset(bitstr, 0xAA, bitstr_size(nbits));
643 for (s = 0; s < nbits; s++) {
644 expected = s % 2 == 0 ? (nbits - s) / 2 : (nbits - s + 1) / 2;
645 bit_count(bitstr, s, nbits, &result);
646 ATF_CHECK_MSG(expected == result,
647 "bit_count_%d_%s_%d_%s: Failed with result %d",
648 nbits, "vary_start", s, memloc, result);
649 }
650
651 /* Varying end location */
652 memset(bitstr, 0xAA, bitstr_size(nbits));
653 for (e = 0; e < nbits; e++) {
654 bit_count(bitstr, 0, e, &result);
655 ATF_CHECK_MSG(e / 2 == result,
656 "bit_count_%d_%s_%d_%s: Failed with result %d",
657 nbits, "vary_end", e, memloc, result);
658 }
659
660 }
661
BITSTRING_TC_DEFINE(bit_foreach)662 BITSTRING_TC_DEFINE(bit_foreach)
663 /* bitstr_t *bitstr, int nbits, const char *memloc */
664 {
665 int i, set_bit;
666
667 /* Empty bitstr */
668 memset(bitstr, 0x00, bitstr_size(nbits));
669 bit_foreach (bitstr, nbits, set_bit) {
670 atf_tc_fail("bit_foreach_%d_%s_%s: Failed at location %d",
671 nbits, "clear", memloc, set_bit);
672 }
673
674 /* Full bitstr */
675 i = 0;
676 memset(bitstr, 0xFF, bitstr_size(nbits));
677 bit_foreach(bitstr, nbits, set_bit) {
678 ATF_REQUIRE_MSG(set_bit == i,
679 "bit_foreach_%d_%s_%s: Failed on turn %d at location %d",
680 nbits, "set", memloc, i, set_bit);
681 i++;
682 }
683 ATF_REQUIRE_MSG(i == nbits,
684 "bit_foreach_%d_%s_%s: Invalid number of turns %d",
685 nbits, "set", memloc, i);
686
687 /* Alternating bitstr, starts with 0 */
688 i = 0;
689 memset(bitstr, 0xAA, bitstr_size(nbits));
690 bit_foreach(bitstr, nbits, set_bit) {
691 ATF_REQUIRE_MSG(set_bit == i * 2 + 1,
692 "bit_foreach_%d_%s_%d_%s: "
693 "Failed on turn %d at location %d",
694 nbits, "alternating", 0, memloc, i, set_bit);
695 i++;
696 }
697 ATF_REQUIRE_MSG(i == nbits / 2,
698 "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d",
699 nbits, "alternating", 0, memloc, i);
700
701 /* Alternating bitstr, starts with 1 */
702 i = 0;
703 memset(bitstr, 0x55, bitstr_size(nbits));
704 bit_foreach(bitstr, nbits, set_bit) {
705 ATF_REQUIRE_MSG(set_bit == i * 2,
706 "bit_foreach_%d_%s_%d_%s: "
707 "Failed on turn %d at location %d",
708 nbits, "alternating", 1, memloc, i, set_bit);
709 i++;
710 }
711 ATF_REQUIRE_MSG(i == (nbits + 1) / 2,
712 "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d",
713 nbits, "alternating", 1, memloc, i);
714 }
715
BITSTRING_TC_DEFINE(bit_foreach_at)716 BITSTRING_TC_DEFINE(bit_foreach_at)
717 /* bitstr_t *bitstr, int nbits, const char *memloc */
718 {
719 int i, s, e, set_bit;
720
721 /* Invalid _start value */
722 memset(bitstr, 0xFF, bitstr_size(nbits));
723 bit_foreach_at(bitstr, nbits, nbits, set_bit) {
724 atf_tc_fail("bit_foreach_at_%d_%s_%s: Failed at location %d",
725 nbits, "invalid_start", memloc, set_bit);
726 }
727
728 /* Varying start location */
729 memset(bitstr, 0xAA, bitstr_size(nbits));
730 for (s = 0; s < nbits; s++) {
731 i = 0;
732 bit_foreach_at(bitstr, s, nbits, set_bit) {
733 ATF_REQUIRE_MSG(set_bit == (i + s / 2) * 2 + 1,
734 "bit_foreach_at_%d_%s_%d_%s: "
735 "Failed on turn %d at location %d",
736 nbits, "vary_start", s, memloc, i, set_bit);
737 i++;
738 }
739 ATF_REQUIRE_MSG(i == nbits / 2 - s / 2,
740 "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d",
741 nbits, "vary_start", s, memloc, i);
742 }
743
744 /* Varying end location */
745 memset(bitstr, 0xAA, bitstr_size(nbits));
746 for (e = 0; e < nbits; e++) {
747 i = 0;
748 bit_foreach_at(bitstr, 0, e, set_bit) {
749 ATF_REQUIRE_MSG(set_bit == i * 2 + 1,
750 "bit_foreach_at_%d_%s_%d_%s: "
751 "Failed on turn %d at location %d",
752 nbits, "vary_end", e, memloc, i, set_bit);
753 i++;
754 }
755 ATF_REQUIRE_MSG(i == e / 2,
756 "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d",
757 nbits, "vary_end", e, memloc, i);
758 }
759 }
760
BITSTRING_TC_DEFINE(bit_foreach_unset)761 BITSTRING_TC_DEFINE(bit_foreach_unset)
762 /* bitstr_t *bitstr, int nbits, const char *memloc */
763 {
764 int i, unset_bit;
765
766 /* Empty bitstr */
767 i = 0;
768 memset(bitstr, 0, bitstr_size(nbits));
769 bit_foreach_unset(bitstr, nbits, unset_bit) {
770 ATF_REQUIRE_MSG(unset_bit == i,
771 "bit_foreach_unset_%d_%s_%s: "
772 "Failed on turn %d at location %d",
773 nbits, "clear", memloc, i, unset_bit);
774 i++;
775 }
776 ATF_REQUIRE_MSG(i == nbits,
777 "bit_foreach_unset_%d_%s_%s: Invalid number of turns %d",
778 nbits, "set", memloc, i);
779
780 /* Full bitstr */
781 memset(bitstr, 0xFF, bitstr_size(nbits));
782 bit_foreach_unset(bitstr, nbits, unset_bit) {
783 atf_tc_fail("bit_foreach_unset_%d_%s_%s: "
784 "Failed at location %d",
785 nbits, "set", memloc, unset_bit);
786 }
787
788 /* Alternating bitstr, starts with 0 */
789 i = 0;
790 memset(bitstr, 0xAA, bitstr_size(nbits));
791 bit_foreach_unset(bitstr, nbits, unset_bit) {
792 ATF_REQUIRE_MSG(unset_bit == i * 2,
793 "bit_foreach_unset_%d_%s_%d_%s: "
794 "Failed on turn %d at location %d",
795 nbits, "alternating", 0, memloc, i, unset_bit);
796 i++;
797 }
798 ATF_REQUIRE_MSG(i == (nbits + 1) / 2,
799 "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d",
800 nbits, "alternating", 0, memloc, i);
801
802 /* Alternating bitstr, starts with 1 */
803 i = 0;
804 memset(bitstr, 0x55, bitstr_size(nbits));
805 bit_foreach_unset(bitstr, nbits, unset_bit) {
806 ATF_REQUIRE_MSG(unset_bit == i * 2 + 1,
807 "bit_foreach_unset_%d_%s_%d_%s: "
808 "Failed on turn %d at location %d",
809 nbits, "alternating", 1, memloc, i, unset_bit);
810 i++;
811 }
812 ATF_REQUIRE_MSG(i == nbits / 2,
813 "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d",
814 nbits, "alternating", 1, memloc, i);
815 }
816
BITSTRING_TC_DEFINE(bit_foreach_unset_at)817 BITSTRING_TC_DEFINE(bit_foreach_unset_at)
818 /* bitstr_t *bitstr, int nbits, const char *memloc */
819 {
820 int i, s, e, unset_bit;
821
822 /* Invalid _start value */
823 memset(bitstr, 0, bitstr_size(nbits));
824 bit_foreach_unset_at(bitstr, nbits, nbits, unset_bit) {
825 atf_tc_fail("bit_foreach_unset_at_%d_%s_%s: "
826 "Failed at location %d",
827 nbits, "invalid_start", memloc, unset_bit);
828 }
829
830 /* Varying start location */
831 memset(bitstr, 0xAA, bitstr_size(nbits));
832 for (s = 0; s < nbits; s++) {
833 i = 0;
834 bit_foreach_unset_at(bitstr, s, nbits, unset_bit) {
835 ATF_REQUIRE_MSG(unset_bit == (i + (s + 1) / 2) * 2,
836 "bit_foreach_unset_at_%d_%s_%d_%s: "
837 "Failed on turn %d at location %d",
838 nbits, "vary_start", s, memloc, i, unset_bit);
839 i++;
840 }
841 ATF_REQUIRE_MSG(i == (nbits + 1) / 2 - (s + 1) / 2,
842 "bit_foreach_unset_at_%d_%s_%d_%s: "
843 "Invalid number of turns %d",
844 nbits, "vary_start", s, memloc, i);
845 }
846
847 /* Varying end location */
848 memset(bitstr, 0xAA, bitstr_size(nbits));
849 for (e = 0; e < nbits; e++) {
850 i = 0;
851 bit_foreach_unset_at(bitstr, 0, e, unset_bit) {
852 ATF_REQUIRE_MSG(unset_bit == i * 2,
853 "bit_foreach_unset_at_%d_%s_%d_%s: "
854 "Failed on turn %d at location %d",
855 nbits, "vary_end", e, memloc, i, unset_bit);
856 i++;
857 }
858 ATF_REQUIRE_MSG(i == (e + 1) / 2,
859 "bit_foreach_unset_at_%d_%s_%d_%s: "
860 "Invalid number of turns %d",
861 nbits, "vary_end", e, memloc, i);
862 }
863 }
864
865 /*
866 * Perform various tests on large bit strings. We can't simply add larger
867 * sizes to bitstring_runner as most of the existing tests are exhaustive
868 * and would take forever to run for large values of nbits.
869 *
870 * On 32-bit platforms, we use nbits = SSIZE_MAX (2147483647) bits, which
871 * is the largest we can hope to support; on 64-bit platforms, we use
872 * nbits = INT_MAX + 30 (2147483677), which is small enough to be
873 * practicable yet large enough to reveal arithmetic overflow bugs.
874 */
875 ATF_TC_WITHOUT_HEAD(bitstr_large);
ATF_TC_BODY(bitstr_large,tc)876 ATF_TC_BODY(bitstr_large, tc)
877 {
878 size_t nbits = INT_MAX < SSIZE_MAX ? (size_t)INT_MAX + 30 : SSIZE_MAX;
879 size_t early = 5, late = nbits - 5;
880 ssize_t fc, fs;
881 bitstr_t *b;
882
883 /* Check for overflow in size calculation */
884 ATF_REQUIRE(nbits >= (size_t)INT_MAX);
885 ATF_REQUIRE(bitstr_size(nbits) >= nbits / 8);
886
887 /* Allocate the bit string */
888 ATF_REQUIRE(b = bit_alloc(nbits));
889
890 /* Check that we allocated enough */
891 ATF_REQUIRE(malloc_usable_size(b) >= bitstr_size(nbits));
892
893 /* Check ffc, ffs on all-zeroes string */
894 bit_ffc(b, nbits, &fc);
895 ATF_CHECK_EQ(0L, fc);
896 bit_ffs(b, nbits, &fs);
897 ATF_CHECK_EQ(-1L, fs);
898
899 /* Set, test, and clear an early bit */
900 bit_set(b, early);
901 bit_ffs(b, nbits, &fs);
902 ATF_CHECK_EQ((ssize_t)early, fs);
903 ATF_CHECK_EQ(0, bit_test(b, early - 1));
904 ATF_CHECK(bit_test(b, early) != 0);
905 ATF_CHECK_EQ(0, bit_test(b, early + 1));
906 bit_clear(b, early);
907 ATF_CHECK_EQ(0, bit_test(b, early));
908
909 /* Set, test, and clear an early bit range */
910 bit_nset(b, early - 1, early + 1);
911 bit_ffs(b, nbits, &fs);
912 ATF_CHECK_EQ((ssize_t)early - 1, fs);
913 ATF_CHECK_EQ(0, bit_test(b, early - 2));
914 ATF_CHECK(bit_test(b, early - 1));
915 ATF_CHECK(bit_test(b, early));
916 ATF_CHECK(bit_test(b, early + 1));
917 ATF_CHECK_EQ(0, bit_test(b, early + 2));
918 bit_nclear(b, early - 1, early + 1);
919 ATF_CHECK_EQ(0, bit_test(b, early - 1));
920 ATF_CHECK_EQ(0, bit_test(b, early));
921 ATF_CHECK_EQ(0, bit_test(b, early + 1));
922
923 /* Set, test, and clear a late bit */
924 bit_set(b, late);
925 bit_ffs(b, nbits, &fs);
926 ATF_CHECK_EQ((ssize_t)late, fs);
927 ATF_CHECK_EQ(0, bit_test(b, late - 1));
928 ATF_CHECK(bit_test(b, late) != 0);
929 ATF_CHECK_EQ(0, bit_test(b, late + 1));
930 bit_clear(b, late);
931 ATF_CHECK_EQ(0, bit_test(b, late));
932
933 /* Set, test, and clear a late bit range */
934 bit_nset(b, late - 1, late + 1);
935 bit_ffs(b, nbits, &fs);
936 ATF_CHECK_EQ((ssize_t)late - 1, fs);
937 ATF_CHECK_EQ(0, bit_test(b, late - 2));
938 ATF_CHECK(bit_test(b, late - 1));
939 ATF_CHECK(bit_test(b, late));
940 ATF_CHECK(bit_test(b, late + 1));
941 ATF_CHECK_EQ(0, bit_test(b, late + 2));
942 bit_nclear(b, late - 1, late + 1);
943 ATF_CHECK_EQ(0, bit_test(b, late - 1));
944 ATF_CHECK_EQ(0, bit_test(b, late));
945 ATF_CHECK_EQ(0, bit_test(b, late + 1));
946
947 free(b);
948 }
949
ATF_TP_ADD_TCS(tp)950 ATF_TP_ADD_TCS(tp)
951 {
952
953 ATF_TP_ADD_TC(tp, bitstr_in_struct);
954 ATF_TP_ADD_TC(tp, bitstr_size);
955 ATF_TP_ADD_TC(tp, bit_ffc_area);
956 ATF_TP_ADD_TC(tp, bit_ffs_area);
957 BITSTRING_TC_ADD(tp, bit_set);
958 BITSTRING_TC_ADD(tp, bit_clear);
959 BITSTRING_TC_ADD(tp, bit_ffs);
960 BITSTRING_TC_ADD(tp, bit_ffc);
961 BITSTRING_TC_ADD(tp, bit_ffs_at);
962 BITSTRING_TC_ADD(tp, bit_ffc_at);
963 BITSTRING_TC_ADD(tp, bit_nclear);
964 BITSTRING_TC_ADD(tp, bit_nset);
965 BITSTRING_TC_ADD(tp, bit_count);
966 BITSTRING_TC_ADD(tp, bit_ffs_area_at_all_or_nothing);
967 BITSTRING_TC_ADD(tp, bit_ffc_area_at_all_or_nothing);
968 BITSTRING_TC_ADD(tp, bit_foreach);
969 BITSTRING_TC_ADD(tp, bit_foreach_at);
970 BITSTRING_TC_ADD(tp, bit_foreach_unset);
971 BITSTRING_TC_ADD(tp, bit_foreach_unset_at);
972 ATF_TP_ADD_TC(tp, bitstr_large);
973
974 return (atf_no_error());
975 }
976