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_MSG(
563 found_clear_bit == i,
564 "bit_nclear_%d_%d_%d%s: Failed with result %d",
565 nbits, i, j, memloc, found_clear_bit);
566
567 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
568 ATF_REQUIRE_MSG(
569 (j + 1 < nbits) ? found_set_bit == j + 1 : -1,
570 "bit_nset_%d_%d_%d%s: Failed with result %d",
571 nbits, i, j, memloc, found_set_bit);
572 }
573 }
574 }
575
BITSTRING_TC_DEFINE(bit_nset)576 BITSTRING_TC_DEFINE(bit_nset)
577 /* bitstr_t *bitstr, int nbits, const char *memloc */
578 {
579 int i, j;
580 int found_set_bit;
581 int found_clear_bit;
582
583 for (i = 0; i < nbits; i++) {
584 for (j = i; j < nbits; j++) {
585 memset(bitstr, 0, bitstr_size(nbits));
586 bit_nset(bitstr, i, j);
587
588 bit_ffs(bitstr, nbits, &found_set_bit);
589 ATF_REQUIRE_MSG(
590 found_set_bit == i,
591 "bit_nset_%d_%d_%d%s: Failed with result %d",
592 nbits, i, j, memloc, found_set_bit);
593
594 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
595 ATF_REQUIRE_MSG(
596 (j + 1 < nbits) ? found_clear_bit == j + 1 : -1,
597 "bit_nset_%d_%d_%d%s: Failed with result %d",
598 nbits, i, j, memloc, found_clear_bit);
599 }
600 }
601 }
602
BITSTRING_TC_DEFINE(bit_count)603 BITSTRING_TC_DEFINE(bit_count)
604 /* bitstr_t *bitstr, int nbits, const char *memloc */
605 {
606 int result, s, e, expected;
607
608 /* Empty bitstr */
609 memset(bitstr, 0, bitstr_size(nbits));
610 bit_count(bitstr, 0, nbits, &result);
611 ATF_CHECK_MSG(0 == result,
612 "bit_count_%d_%s_%s: Failed with result %d",
613 nbits, "clear", memloc, result);
614
615 /* Full bitstr */
616 memset(bitstr, 0xFF, bitstr_size(nbits));
617 bit_count(bitstr, 0, nbits, &result);
618 ATF_CHECK_MSG(nbits == result,
619 "bit_count_%d_%s_%s: Failed with result %d",
620 nbits, "set", memloc, result);
621
622 /* Invalid _start value */
623 memset(bitstr, 0xFF, bitstr_size(nbits));
624 bit_count(bitstr, nbits, nbits, &result);
625 ATF_CHECK_MSG(0 == result,
626 "bit_count_%d_%s_%s: Failed with result %d",
627 nbits, "invalid_start", memloc, result);
628
629 /* Alternating bitstr, starts with 0 */
630 memset(bitstr, 0xAA, bitstr_size(nbits));
631 bit_count(bitstr, 0, nbits, &result);
632 ATF_CHECK_MSG(nbits / 2 == result,
633 "bit_count_%d_%s_%d_%s: Failed with result %d",
634 nbits, "alternating", 0, memloc, result);
635
636 /* Alternating bitstr, starts with 1 */
637 memset(bitstr, 0x55, bitstr_size(nbits));
638 bit_count(bitstr, 0, nbits, &result);
639 ATF_CHECK_MSG((nbits + 1) / 2 == result,
640 "bit_count_%d_%s_%d_%s: Failed with result %d",
641 nbits, "alternating", 1, memloc, result);
642
643 /* Varying start location */
644 memset(bitstr, 0xAA, bitstr_size(nbits));
645 for (s = 0; s < nbits; s++) {
646 expected = s % 2 == 0 ? (nbits - s) / 2 : (nbits - s + 1) / 2;
647 bit_count(bitstr, s, nbits, &result);
648 ATF_CHECK_MSG(expected == result,
649 "bit_count_%d_%s_%d_%s: Failed with result %d",
650 nbits, "vary_start", s, memloc, result);
651 }
652
653 /* Varying end location */
654 memset(bitstr, 0xAA, bitstr_size(nbits));
655 for (e = 0; e < nbits; e++) {
656 bit_count(bitstr, 0, e, &result);
657 ATF_CHECK_MSG(e / 2 == result,
658 "bit_count_%d_%s_%d_%s: Failed with result %d",
659 nbits, "vary_end", e, memloc, result);
660 }
661
662 }
663
BITSTRING_TC_DEFINE(bit_foreach)664 BITSTRING_TC_DEFINE(bit_foreach)
665 /* bitstr_t *bitstr, int nbits, const char *memloc */
666 {
667 int i, set_bit;
668
669 /* Empty bitstr */
670 memset(bitstr, 0x00, bitstr_size(nbits));
671 bit_foreach (bitstr, nbits, set_bit) {
672 atf_tc_fail("bit_foreach_%d_%s_%s: Failed at location %d",
673 nbits, "clear", memloc, set_bit);
674 }
675
676 /* Full bitstr */
677 i = 0;
678 memset(bitstr, 0xFF, bitstr_size(nbits));
679 bit_foreach(bitstr, nbits, set_bit) {
680 ATF_REQUIRE_MSG(set_bit == i,
681 "bit_foreach_%d_%s_%s: Failed on turn %d at location %d",
682 nbits, "set", memloc, i, set_bit);
683 i++;
684 }
685 ATF_REQUIRE_MSG(i == nbits,
686 "bit_foreach_%d_%s_%s: Invalid number of turns %d",
687 nbits, "set", memloc, i);
688
689 /* Alternating bitstr, starts with 0 */
690 i = 0;
691 memset(bitstr, 0xAA, bitstr_size(nbits));
692 bit_foreach(bitstr, nbits, set_bit) {
693 ATF_REQUIRE_MSG(set_bit == i * 2 + 1,
694 "bit_foreach_%d_%s_%d_%s: "
695 "Failed on turn %d at location %d",
696 nbits, "alternating", 0, memloc, i, set_bit);
697 i++;
698 }
699 ATF_REQUIRE_MSG(i == nbits / 2,
700 "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d",
701 nbits, "alternating", 0, memloc, i);
702
703 /* Alternating bitstr, starts with 1 */
704 i = 0;
705 memset(bitstr, 0x55, bitstr_size(nbits));
706 bit_foreach(bitstr, nbits, set_bit) {
707 ATF_REQUIRE_MSG(set_bit == i * 2,
708 "bit_foreach_%d_%s_%d_%s: "
709 "Failed on turn %d at location %d",
710 nbits, "alternating", 1, memloc, i, set_bit);
711 i++;
712 }
713 ATF_REQUIRE_MSG(i == (nbits + 1) / 2,
714 "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d",
715 nbits, "alternating", 1, memloc, i);
716 }
717
BITSTRING_TC_DEFINE(bit_foreach_at)718 BITSTRING_TC_DEFINE(bit_foreach_at)
719 /* bitstr_t *bitstr, int nbits, const char *memloc */
720 {
721 int i, s, e, set_bit;
722
723 /* Invalid _start value */
724 memset(bitstr, 0xFF, bitstr_size(nbits));
725 bit_foreach_at(bitstr, nbits, nbits, set_bit) {
726 atf_tc_fail("bit_foreach_at_%d_%s_%s: Failed at location %d",
727 nbits, "invalid_start", memloc, set_bit);
728 }
729
730 /* Varying start location */
731 memset(bitstr, 0xAA, bitstr_size(nbits));
732 for (s = 0; s < nbits; s++) {
733 i = 0;
734 bit_foreach_at(bitstr, s, nbits, set_bit) {
735 ATF_REQUIRE_MSG(set_bit == (i + s / 2) * 2 + 1,
736 "bit_foreach_at_%d_%s_%d_%s: "
737 "Failed on turn %d at location %d",
738 nbits, "vary_start", s, memloc, i, set_bit);
739 i++;
740 }
741 ATF_REQUIRE_MSG(i == nbits / 2 - s / 2,
742 "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d",
743 nbits, "vary_start", s, memloc, i);
744 }
745
746 /* Varying end location */
747 memset(bitstr, 0xAA, bitstr_size(nbits));
748 for (e = 0; e < nbits; e++) {
749 i = 0;
750 bit_foreach_at(bitstr, 0, e, set_bit) {
751 ATF_REQUIRE_MSG(set_bit == i * 2 + 1,
752 "bit_foreach_at_%d_%s_%d_%s: "
753 "Failed on turn %d at location %d",
754 nbits, "vary_end", e, memloc, i, set_bit);
755 i++;
756 }
757 ATF_REQUIRE_MSG(i == e / 2,
758 "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d",
759 nbits, "vary_end", e, memloc, i);
760 }
761 }
762
BITSTRING_TC_DEFINE(bit_foreach_unset)763 BITSTRING_TC_DEFINE(bit_foreach_unset)
764 /* bitstr_t *bitstr, int nbits, const char *memloc */
765 {
766 int i, unset_bit;
767
768 /* Empty bitstr */
769 i = 0;
770 memset(bitstr, 0, bitstr_size(nbits));
771 bit_foreach_unset(bitstr, nbits, unset_bit) {
772 ATF_REQUIRE_MSG(unset_bit == i,
773 "bit_foreach_unset_%d_%s_%s: "
774 "Failed on turn %d at location %d",
775 nbits, "clear", memloc, i, unset_bit);
776 i++;
777 }
778 ATF_REQUIRE_MSG(i == nbits,
779 "bit_foreach_unset_%d_%s_%s: Invalid number of turns %d",
780 nbits, "set", memloc, i);
781
782 /* Full bitstr */
783 memset(bitstr, 0xFF, bitstr_size(nbits));
784 bit_foreach_unset(bitstr, nbits, unset_bit) {
785 atf_tc_fail("bit_foreach_unset_%d_%s_%s: "
786 "Failed at location %d",
787 nbits, "set", memloc, unset_bit);
788 }
789
790 /* Alternating bitstr, starts with 0 */
791 i = 0;
792 memset(bitstr, 0xAA, bitstr_size(nbits));
793 bit_foreach_unset(bitstr, nbits, unset_bit) {
794 ATF_REQUIRE_MSG(unset_bit == i * 2,
795 "bit_foreach_unset_%d_%s_%d_%s: "
796 "Failed on turn %d at location %d",
797 nbits, "alternating", 0, memloc, i, unset_bit);
798 i++;
799 }
800 ATF_REQUIRE_MSG(i == (nbits + 1) / 2,
801 "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d",
802 nbits, "alternating", 0, memloc, i);
803
804 /* Alternating bitstr, starts with 1 */
805 i = 0;
806 memset(bitstr, 0x55, bitstr_size(nbits));
807 bit_foreach_unset(bitstr, nbits, unset_bit) {
808 ATF_REQUIRE_MSG(unset_bit == i * 2 + 1,
809 "bit_foreach_unset_%d_%s_%d_%s: "
810 "Failed on turn %d at location %d",
811 nbits, "alternating", 1, memloc, i, unset_bit);
812 i++;
813 }
814 ATF_REQUIRE_MSG(i == nbits / 2,
815 "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d",
816 nbits, "alternating", 1, memloc, i);
817 }
818
BITSTRING_TC_DEFINE(bit_foreach_unset_at)819 BITSTRING_TC_DEFINE(bit_foreach_unset_at)
820 /* bitstr_t *bitstr, int nbits, const char *memloc */
821 {
822 int i, s, e, unset_bit;
823
824 /* Invalid _start value */
825 memset(bitstr, 0, bitstr_size(nbits));
826 bit_foreach_unset_at(bitstr, nbits, nbits, unset_bit) {
827 atf_tc_fail("bit_foreach_unset_at_%d_%s_%s: "
828 "Failed at location %d",
829 nbits, "invalid_start", memloc, unset_bit);
830 }
831
832 /* Varying start location */
833 memset(bitstr, 0xAA, bitstr_size(nbits));
834 for (s = 0; s < nbits; s++) {
835 i = 0;
836 bit_foreach_unset_at(bitstr, s, nbits, unset_bit) {
837 ATF_REQUIRE_MSG(unset_bit == (i + (s + 1) / 2) * 2,
838 "bit_foreach_unset_at_%d_%s_%d_%s: "
839 "Failed on turn %d at location %d",
840 nbits, "vary_start", s, memloc, i, unset_bit);
841 i++;
842 }
843 ATF_REQUIRE_MSG(i == (nbits + 1) / 2 - (s + 1) / 2,
844 "bit_foreach_unset_at_%d_%s_%d_%s: "
845 "Invalid number of turns %d",
846 nbits, "vary_start", s, memloc, i);
847 }
848
849 /* Varying end location */
850 memset(bitstr, 0xAA, bitstr_size(nbits));
851 for (e = 0; e < nbits; e++) {
852 i = 0;
853 bit_foreach_unset_at(bitstr, 0, e, unset_bit) {
854 ATF_REQUIRE_MSG(unset_bit == i * 2,
855 "bit_foreach_unset_at_%d_%s_%d_%s: "
856 "Failed on turn %d at location %d",
857 nbits, "vary_end", e, memloc, i, unset_bit);
858 i++;
859 }
860 ATF_REQUIRE_MSG(i == (e + 1) / 2,
861 "bit_foreach_unset_at_%d_%s_%d_%s: "
862 "Invalid number of turns %d",
863 nbits, "vary_end", e, memloc, i);
864 }
865 }
866
867 /*
868 * Perform various tests on large bit strings. We can't simply add larger
869 * sizes to bitstring_runner as most of the existing tests are exhaustive
870 * and would take forever to run for large values of nbits.
871 *
872 * On 32-bit platforms, we use nbits = SSIZE_MAX (2147483647) bits, which
873 * is the largest we can hope to support; on 64-bit platforms, we use
874 * nbits = INT_MAX + 30 (2147483677), which is small enough to be
875 * practicable yet large enough to reveal arithmetic overflow bugs.
876 */
877 ATF_TC_WITHOUT_HEAD(bitstr_large);
ATF_TC_BODY(bitstr_large,tc)878 ATF_TC_BODY(bitstr_large, tc)
879 {
880 size_t nbits = INT_MAX < SSIZE_MAX ? (size_t)INT_MAX + 30 : SSIZE_MAX;
881 size_t early = 5, late = nbits - 5;
882 ssize_t fc, fs;
883 bitstr_t *b;
884
885 /* Check for overflow in size calculation */
886 ATF_REQUIRE(nbits >= (size_t)INT_MAX);
887 ATF_REQUIRE(bitstr_size(nbits) >= nbits / 8);
888
889 /* Allocate the bit string */
890 ATF_REQUIRE(b = bit_alloc(nbits));
891
892 /* Check that we allocated enough */
893 ATF_REQUIRE(malloc_usable_size(b) >= bitstr_size(nbits));
894
895 /* Check ffc, ffs on all-zeroes string */
896 bit_ffc(b, nbits, &fc);
897 ATF_CHECK_EQ(0L, fc);
898 bit_ffs(b, nbits, &fs);
899 ATF_CHECK_EQ(-1L, fs);
900
901 /* Set, test, and clear an early bit */
902 bit_set(b, early);
903 bit_ffs(b, nbits, &fs);
904 ATF_CHECK_EQ((ssize_t)early, fs);
905 ATF_CHECK_EQ(0, bit_test(b, early - 1));
906 ATF_CHECK(bit_test(b, early) != 0);
907 ATF_CHECK_EQ(0, bit_test(b, early + 1));
908 bit_clear(b, early);
909 ATF_CHECK_EQ(0, bit_test(b, early));
910
911 /* Set, test, and clear an early bit range */
912 bit_nset(b, early - 1, early + 1);
913 bit_ffs(b, nbits, &fs);
914 ATF_CHECK_EQ((ssize_t)early - 1, fs);
915 ATF_CHECK_EQ(0, bit_test(b, early - 2));
916 ATF_CHECK(bit_test(b, early - 1));
917 ATF_CHECK(bit_test(b, early));
918 ATF_CHECK(bit_test(b, early + 1));
919 ATF_CHECK_EQ(0, bit_test(b, early + 2));
920 bit_nclear(b, early - 1, early + 1);
921 ATF_CHECK_EQ(0, bit_test(b, early - 1));
922 ATF_CHECK_EQ(0, bit_test(b, early));
923 ATF_CHECK_EQ(0, bit_test(b, early + 1));
924
925 /* Set, test, and clear a late bit */
926 bit_set(b, late);
927 bit_ffs(b, nbits, &fs);
928 ATF_CHECK_EQ((ssize_t)late, fs);
929 ATF_CHECK_EQ(0, bit_test(b, late - 1));
930 ATF_CHECK(bit_test(b, late) != 0);
931 ATF_CHECK_EQ(0, bit_test(b, late + 1));
932 bit_clear(b, late);
933 ATF_CHECK_EQ(0, bit_test(b, late));
934
935 /* Set, test, and clear a late bit range */
936 bit_nset(b, late - 1, late + 1);
937 bit_ffs(b, nbits, &fs);
938 ATF_CHECK_EQ((ssize_t)late - 1, fs);
939 ATF_CHECK_EQ(0, bit_test(b, late - 2));
940 ATF_CHECK(bit_test(b, late - 1));
941 ATF_CHECK(bit_test(b, late));
942 ATF_CHECK(bit_test(b, late + 1));
943 ATF_CHECK_EQ(0, bit_test(b, late + 2));
944 bit_nclear(b, late - 1, late + 1);
945 ATF_CHECK_EQ(0, bit_test(b, late - 1));
946 ATF_CHECK_EQ(0, bit_test(b, late));
947 ATF_CHECK_EQ(0, bit_test(b, late + 1));
948
949 free(b);
950 }
951
ATF_TP_ADD_TCS(tp)952 ATF_TP_ADD_TCS(tp)
953 {
954
955 ATF_TP_ADD_TC(tp, bitstr_in_struct);
956 ATF_TP_ADD_TC(tp, bitstr_size);
957 ATF_TP_ADD_TC(tp, bit_ffc_area);
958 ATF_TP_ADD_TC(tp, bit_ffs_area);
959 BITSTRING_TC_ADD(tp, bit_set);
960 BITSTRING_TC_ADD(tp, bit_clear);
961 BITSTRING_TC_ADD(tp, bit_ffs);
962 BITSTRING_TC_ADD(tp, bit_ffc);
963 BITSTRING_TC_ADD(tp, bit_ffs_at);
964 BITSTRING_TC_ADD(tp, bit_ffc_at);
965 BITSTRING_TC_ADD(tp, bit_nclear);
966 BITSTRING_TC_ADD(tp, bit_nset);
967 BITSTRING_TC_ADD(tp, bit_count);
968 BITSTRING_TC_ADD(tp, bit_ffs_area_at_all_or_nothing);
969 BITSTRING_TC_ADD(tp, bit_ffc_area_at_all_or_nothing);
970 BITSTRING_TC_ADD(tp, bit_foreach);
971 BITSTRING_TC_ADD(tp, bit_foreach_at);
972 BITSTRING_TC_ADD(tp, bit_foreach_unset);
973 BITSTRING_TC_ADD(tp, bit_foreach_unset_at);
974 ATF_TP_ADD_TC(tp, bitstr_large);
975
976 return (atf_no_error());
977 }
978