2 * Copyright (c) 2014 Spectra Logic Corporation
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions, and the following disclaimer,
10 * without modification.
11 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
12 * substantially similar to the "NO WARRANTY" disclaimer below
13 * ("Disclaimer") and any redistribution must be conditioned upon
14 * including a substantially similar Disclaimer requirement for further
15 * binary redistribution.
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
26 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
27 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGES.
32 #include <sys/param.h>
34 #include <bitstring.h>
39 typedef void (testfunc_t)(bitstr_t *bstr, int nbits, const char *memloc);
42 bitstring_run_stack_test(testfunc_t *test, int nbits)
44 bitstr_t bit_decl(bitstr, nbits);
46 test(bitstr, nbits, "stack");
50 bitstring_run_heap_test(testfunc_t *test, int nbits)
52 bitstr_t *bitstr = bit_alloc(nbits);
54 test(bitstr, nbits, "heap");
58 bitstring_test_runner(testfunc_t *test)
60 const int bitstr_sizes[] = {
72 for (unsigned long i = 0; i < nitems(bitstr_sizes); i++) {
73 bitstring_run_stack_test(test, bitstr_sizes[i]);
74 bitstring_run_heap_test(test, bitstr_sizes[i]);
78 #define BITSTRING_TC_DEFINE(name) \
79 ATF_TC_WITHOUT_HEAD(name); \
80 static testfunc_t name ## _test; \
82 ATF_TC_BODY(name, tc) \
84 bitstring_test_runner(name ## _test); \
88 name ## _test(bitstr_t *bitstr, int nbits, const char *memloc)
90 #define BITSTRING_TC_ADD(tp, name) \
92 ATF_TP_ADD_TC(tp, name); \
95 ATF_TC_WITHOUT_HEAD(bitstr_in_struct);
96 ATF_TC_BODY(bitstr_in_struct, tc)
98 struct bitstr_containing_struct {
99 bitstr_t bit_decl(bitstr, 8);
102 bit_nclear(test_struct.bitstr, 0, 8);
105 ATF_TC_WITHOUT_HEAD(bitstr_size);
106 ATF_TC_BODY(bitstr_size, tc)
108 size_t sob = sizeof(bitstr_t);
110 ATF_CHECK_EQ(0, bitstr_size(0));
111 ATF_CHECK_EQ(sob, bitstr_size(1));
112 ATF_CHECK_EQ(sob, bitstr_size(sob * 8));
113 ATF_CHECK_EQ(2 * sob, bitstr_size(sob * 8 + 1));
116 BITSTRING_TC_DEFINE(bit_set)
117 /* bitstr_t *bitstr, int nbits, const char *memloc */
119 memset(bitstr, 0, bitstr_size(nbits));
121 for (int i = 0; i < nbits; i++) {
124 for (int j = 0; j < nbits; j++) {
125 ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 1 : 0,
126 "bit_set_%d_%s: Failed on bit %d",
130 bit_clear(bitstr, i);
134 BITSTRING_TC_DEFINE(bit_clear)
135 /* bitstr_t *bitstr, int nbits, const char *memloc */
139 memset(bitstr, 0xFF, bitstr_size(nbits));
140 for (i = 0; i < nbits; i++) {
141 bit_clear(bitstr, i);
143 for (j = 0; j < nbits; j++) {
144 ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 0 : 1,
145 "bit_clear_%d_%s: Failed on bit %d",
153 BITSTRING_TC_DEFINE(bit_ffs)
154 /* bitstr_t *bitstr, int nbits, const char *memloc */
159 memset(bitstr, 0, bitstr_size(nbits));
160 bit_ffs(bitstr, nbits, &found_set_bit);
161 ATF_REQUIRE_MSG(found_set_bit == -1,
162 "bit_ffs_%d_%s: Failed all clear bits.", nbits, memloc);
164 for (i = 0; i < nbits; i++) {
165 memset(bitstr, 0xFF, bitstr_size(nbits));
167 bit_nclear(bitstr, 0, i - 1);
169 bit_ffs(bitstr, nbits, &found_set_bit);
170 ATF_REQUIRE_MSG(found_set_bit == i,
171 "bit_ffs_%d_%s: Failed on bit %d, Result %d",
172 nbits, memloc, i, found_set_bit);
176 BITSTRING_TC_DEFINE(bit_ffc)
177 /* bitstr_t *bitstr, int nbits, const char *memloc */
182 memset(bitstr, 0xFF, bitstr_size(nbits));
183 bit_ffc(bitstr, nbits, &found_clear_bit);
184 ATF_REQUIRE_MSG(found_clear_bit == -1,
185 "bit_ffc_%d_%s: Failed all set bits.", nbits, memloc);
187 for (i = 0; i < nbits; i++) {
188 memset(bitstr, 0, bitstr_size(nbits));
190 bit_nset(bitstr, 0, i - 1);
192 bit_ffc(bitstr, nbits, &found_clear_bit);
193 ATF_REQUIRE_MSG(found_clear_bit == i,
194 "bit_ffc_%d_%s: Failed on bit %d, Result %d",
195 nbits, memloc, i, found_clear_bit);
199 BITSTRING_TC_DEFINE(bit_ffs_at)
200 /* bitstr_t *bitstr, int nbits, const char *memloc */
205 memset(bitstr, 0xFF, bitstr_size(nbits));
206 for (i = 0; i < nbits; i++) {
207 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
208 ATF_REQUIRE_MSG(found_set_bit == i,
209 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
210 nbits, memloc, i, found_set_bit);
213 memset(bitstr, 0, bitstr_size(nbits));
214 for (i = 0; i < nbits; i++) {
215 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
216 ATF_REQUIRE_MSG(found_set_bit == -1,
217 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
218 nbits, memloc, i, found_set_bit);
221 memset(bitstr, 0x55, bitstr_size(nbits));
222 for (i = 0; i < nbits; i++) {
223 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
224 if (i == nbits - 1 && (nbits & 1) == 0) {
225 ATF_REQUIRE_MSG(found_set_bit == -1,
226 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
227 nbits, memloc, i, found_set_bit);
229 ATF_REQUIRE_MSG(found_set_bit == i + (i & 1),
230 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
231 nbits, memloc, i, found_set_bit);
235 memset(bitstr, 0xAA, bitstr_size(nbits));
236 for (i = 0; i < nbits; i++) {
237 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
238 if (i == nbits - 1 && (nbits & 1) != 0) {
239 ATF_REQUIRE_MSG(found_set_bit == -1,
240 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
241 nbits, memloc, i, found_set_bit);
244 found_set_bit == i + ((i & 1) ? 0 : 1),
245 "bit_ffs_at_%d_%s: Failed on bit %d, Result %d",
246 nbits, memloc, i, found_set_bit);
250 /* Pass a start value beyond the size of the bit string */
251 bit_ffs_at(bitstr, nbits, nbits, &found_set_bit);
252 ATF_REQUIRE_MSG(found_set_bit == -1,
253 "bit_ffs_at_%d_%s: Failed with high start value of %d, Result %d",
254 nbits, memloc, nbits, found_set_bit);
256 bit_ffs_at(bitstr, nbits + 3, nbits, &found_set_bit);
257 ATF_REQUIRE_MSG(found_set_bit == -1,
258 "bit_ffs_at_%d_%s: Failed with high start value of %d, Result %d",
259 nbits, memloc, nbits + 3, found_set_bit);
262 BITSTRING_TC_DEFINE(bit_ffc_at)
263 /* bitstr_t *bitstr, int nbits, const char *memloc */
265 int i, found_clear_bit;
267 memset(bitstr, 0, bitstr_size(nbits));
268 for (i = 0; i < nbits; i++) {
269 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
270 ATF_REQUIRE_MSG(found_clear_bit == i,
271 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
272 nbits, memloc, i, found_clear_bit);
275 memset(bitstr, 0xFF, bitstr_size(nbits));
276 for (i = 0; i < nbits; i++) {
277 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
278 ATF_REQUIRE_MSG(found_clear_bit == -1,
279 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
280 nbits, memloc, i, found_clear_bit);
283 memset(bitstr, 0x55, bitstr_size(nbits));
284 for (i = 0; i < nbits; i++) {
285 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
286 if (i == nbits - 1 && (nbits & 1) != 0) {
287 ATF_REQUIRE_MSG(found_clear_bit == -1,
288 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
289 nbits, memloc, i, found_clear_bit);
292 found_clear_bit == i + ((i & 1) ? 0 : 1),
293 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
294 nbits, memloc, i, found_clear_bit);
298 memset(bitstr, 0xAA, bitstr_size(nbits));
299 for (i = 0; i < nbits; i++) {
300 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
301 if (i == nbits - 1 && (nbits & 1) == 0) {
302 ATF_REQUIRE_MSG(found_clear_bit == -1,
303 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
304 nbits, memloc, i, found_clear_bit);
306 ATF_REQUIRE_MSG(found_clear_bit == i + (i & 1),
307 "bit_ffc_at_%d_%s: Failed on bit %d, Result %d",
308 nbits, memloc, i, found_clear_bit);
312 /* Pass a start value beyond the size of the bit string */
313 bit_ffc_at(bitstr, nbits, nbits, &found_clear_bit);
314 ATF_REQUIRE_MSG(found_clear_bit == -1,
315 "bit_ffc_at_%d_%s: Failed with high start value, Result %d",
316 nbits, memloc, found_clear_bit);
318 bit_ffc_at(bitstr, nbits + 3, nbits, &found_clear_bit);
319 ATF_REQUIRE_MSG(found_clear_bit == -1,
320 "bit_ffc_at_%d_%s: Failed with high start value of %d, Result %d",
321 nbits, memloc, nbits + 3, found_clear_bit);
324 BITSTRING_TC_DEFINE(bit_ffc_area_no_match)
325 /* bitstr_t *bitstr, int nbits, const char *memloc */
327 int found_clear_bits;
329 memset(bitstr, 0xFF, bitstr_size(nbits));
330 bit_ffc_area(bitstr, nbits, 2, &found_clear_bits);
331 ATF_REQUIRE_EQ_MSG(-1, found_clear_bits,
332 "bit_ffc_area_%d_%s: Failed all set bits.", nbits, memloc);
335 BITSTRING_TC_DEFINE(bit_ffs_area_no_match)
336 /* bitstr_t *bitstr, int nbits, const char *memloc */
338 int found_clear_bits;
340 memset(bitstr, 0, bitstr_size(nbits));
341 bit_ffs_area(bitstr, nbits, 2, &found_clear_bits);
342 ATF_REQUIRE_EQ_MSG(-1, found_clear_bits,
343 "bit_ffs_area_%d_%s: Failed all clear bits.", nbits, memloc);
346 ATF_TC_WITHOUT_HEAD(bit_ffs_area);
347 ATF_TC_BODY(bit_ffs_area, tc)
349 const int nbits = 72;
350 bitstr_t bit_decl(bitstr, nbits);
353 memset(bitstr, 0, bitstr_size(nbits));
359 bit_ffs_area(bitstr, nbits, 3, &location);
360 ATF_REQUIRE_EQ_MSG(-1, location,
361 "bit_ffs_area: found location of size 3 when only 2 bits are set");
366 bit_ffs_area(bitstr, nbits, 3, &location);
367 ATF_REQUIRE_EQ_MSG(5, location,
368 "bit_ffs_area: failed to find location of size 3");
373 bit_ffs_area(bitstr, nbits, 3, &location);
374 ATF_REQUIRE_EQ_MSG(5, location,
375 "bit_ffs_area: failed to find location of size 3");
378 bit_ffs_area_at(bitstr, 2, nbits, 3, &location);
379 ATF_REQUIRE_EQ_MSG(5, location,
380 "bit_ffs_area_at: failed to find location of size 3");
383 bit_ffs_area_at(bitstr, 6, nbits, 3, &location);
384 ATF_REQUIRE_EQ_MSG(6, location,
385 "bit_ffs_area_at: failed to find location of size 3");
388 bit_ffs_area_at(bitstr, 8, nbits, 3, &location);
389 ATF_REQUIRE_EQ_MSG(-1, location,
390 "bit_ffs_area_at: found invalid location");
397 bit_ffs_area_at(bitstr, 8, nbits, 3, &location);
398 ATF_REQUIRE_EQ_MSG(69, location,
399 "bit_ffs_area_at: failed to find location of size 3");
402 bit_ffs_area_at(bitstr, 69, nbits, 3, &location);
403 ATF_REQUIRE_EQ_MSG(69, location,
404 "bit_ffs_area_at: failed to find location of size 3");
407 bit_ffs_area_at(bitstr, 70, nbits, 3, &location);
408 ATF_REQUIRE_EQ_MSG(-1, location,
409 "bit_ffs_area_at: found invalid location");
412 bit_ffs_area_at(bitstr, 72, nbits, 3, &location);
413 ATF_REQUIRE_EQ_MSG(-1, location,
414 "bit_ffs_area_at: found invalid location");
417 ATF_TC_WITHOUT_HEAD(bit_ffc_area);
418 ATF_TC_BODY(bit_ffc_area, tc)
420 const int nbits = 80;
421 bitstr_t bit_decl(bitstr, nbits);
425 memset(bitstr, 0xFF, bitstr_size(nbits));
427 bit_clear(bitstr, 7);
428 bit_clear(bitstr, 8);
431 bit_ffc_area(bitstr, nbits, 3, &location);
432 ATF_REQUIRE_EQ_MSG(-1, location,
433 "bit_ffc_area: found location of size 3 when only 2 bits are set");
435 bit_clear(bitstr, 9);
438 bit_ffc_area(bitstr, nbits, 3, &location);
439 ATF_REQUIRE_EQ_MSG(7, location,
440 "bit_ffc_area: failed to find location of size 3");
442 bit_clear(bitstr, 10);
445 bit_ffc_area(bitstr, nbits, 3, &location);
446 ATF_REQUIRE_EQ_MSG(7, location,
447 "bit_ffc_area: failed to find location of size 3");
450 bit_ffc_area_at(bitstr, 2, nbits, 3, &location);
451 ATF_REQUIRE_EQ_MSG(7, location,
452 "bit_ffc_area_at: failed to find location of size 3");
455 bit_ffc_area_at(bitstr, 8, nbits, 3, &location);
456 ATF_REQUIRE_EQ_MSG(8, location,
457 "bit_ffc_area_at: failed to find location of size 3");
460 bit_ffc_area_at(bitstr, 9, nbits, 3, &location);
461 ATF_REQUIRE_EQ_MSG(-1, location,
462 "bit_ffc_area_at: found invalid bit location");
464 bit_clear(bitstr, 77);
465 bit_clear(bitstr, 78);
466 bit_clear(bitstr, 79);
469 bit_ffc_area_at(bitstr, 12, nbits, 3, &location);
470 ATF_REQUIRE_EQ_MSG(77, location,
471 "bit_ffc_area_at: failed to find location of size 3");
474 bit_ffc_area_at(bitstr, 77, nbits, 3, &location);
475 ATF_REQUIRE_EQ_MSG(77, location,
476 "bit_ffc_area_at: failed to find location of size 3");
479 bit_ffc_area_at(bitstr, 78, nbits, 3, &location);
480 ATF_REQUIRE_EQ_MSG(-1, location,
481 "bit_ffc_area_at: found invalid location");
484 bit_ffc_area_at(bitstr, 85, nbits, 3, &location);
485 ATF_REQUIRE_EQ_MSG(-1, location,
486 "bit_ffc_area_at: found invalid location");
489 BITSTRING_TC_DEFINE(bit_nclear)
490 /* bitstr_t *bitstr, int nbits, const char *memloc */
496 for (i = 0; i < nbits; i++) {
497 for (j = i; j < nbits; j++) {
498 memset(bitstr, 0xFF, bitstr_size(nbits));
499 bit_nclear(bitstr, i, j);
501 bit_ffc(bitstr, nbits, &found_clear_bit);
503 found_clear_bit == i,
504 "bit_nclear_%d_%d_%d%s: Failed with result %d",
505 nbits, i, j, memloc, found_clear_bit);
507 bit_ffs_at(bitstr, i, nbits, &found_set_bit);
509 (j + 1 < nbits) ? found_set_bit == j + 1 : -1,
510 "bit_nset_%d_%d_%d%s: Failed with result %d",
511 nbits, i, j, memloc, found_set_bit);
516 BITSTRING_TC_DEFINE(bit_nset)
517 /* bitstr_t *bitstr, int nbits, const char *memloc */
523 for (i = 0; i < nbits; i++) {
524 for (j = i; j < nbits; j++) {
525 memset(bitstr, 0, bitstr_size(nbits));
526 bit_nset(bitstr, i, j);
528 bit_ffs(bitstr, nbits, &found_set_bit);
531 "bit_nset_%d_%d_%d%s: Failed with result %d",
532 nbits, i, j, memloc, found_set_bit);
534 bit_ffc_at(bitstr, i, nbits, &found_clear_bit);
536 (j + 1 < nbits) ? found_clear_bit == j + 1 : -1,
537 "bit_nset_%d_%d_%d%s: Failed with result %d",
538 nbits, i, j, memloc, found_clear_bit);
543 BITSTRING_TC_DEFINE(bit_count)
544 /* bitstr_t *bitstr, int nbits, const char *memloc */
546 int result, s, e, expected;
549 memset(bitstr, 0, bitstr_size(nbits));
550 bit_count(bitstr, 0, nbits, &result);
551 ATF_CHECK_MSG(0 == result,
552 "bit_count_%d_%s_%s: Failed with result %d",
553 nbits, "clear", memloc, result);
556 memset(bitstr, 0xFF, bitstr_size(nbits));
557 bit_count(bitstr, 0, nbits, &result);
558 ATF_CHECK_MSG(nbits == result,
559 "bit_count_%d_%s_%s: Failed with result %d",
560 nbits, "set", memloc, result);
562 /* Invalid _start value */
563 memset(bitstr, 0xFF, bitstr_size(nbits));
564 bit_count(bitstr, nbits, nbits, &result);
565 ATF_CHECK_MSG(0 == result,
566 "bit_count_%d_%s_%s: Failed with result %d",
567 nbits, "invalid_start", memloc, result);
569 /* Alternating bitstr, starts with 0 */
570 memset(bitstr, 0xAA, bitstr_size(nbits));
571 bit_count(bitstr, 0, nbits, &result);
572 ATF_CHECK_MSG(nbits / 2 == result,
573 "bit_count_%d_%s_%d_%s: Failed with result %d",
574 nbits, "alternating", 0, memloc, result);
576 /* Alternating bitstr, starts with 1 */
577 memset(bitstr, 0x55, bitstr_size(nbits));
578 bit_count(bitstr, 0, nbits, &result);
579 ATF_CHECK_MSG((nbits + 1) / 2 == result,
580 "bit_count_%d_%s_%d_%s: Failed with result %d",
581 nbits, "alternating", 1, memloc, result);
583 /* Varying start location */
584 memset(bitstr, 0xAA, bitstr_size(nbits));
585 for (s = 0; s < nbits; s++) {
586 expected = s % 2 == 0 ? (nbits - s) / 2 : (nbits - s + 1) / 2;
587 bit_count(bitstr, s, nbits, &result);
588 ATF_CHECK_MSG(expected == result,
589 "bit_count_%d_%s_%d_%s: Failed with result %d",
590 nbits, "vary_start", s, memloc, result);
593 /* Varying end location */
594 memset(bitstr, 0xAA, bitstr_size(nbits));
595 for (e = 0; e < nbits; e++) {
596 bit_count(bitstr, 0, e, &result);
597 ATF_CHECK_MSG(e / 2 == result,
598 "bit_count_%d_%s_%d_%s: Failed with result %d",
599 nbits, "vary_end", e, memloc, result);
607 ATF_TP_ADD_TC(tp, bitstr_in_struct);
608 ATF_TP_ADD_TC(tp, bitstr_size);
609 ATF_TP_ADD_TC(tp, bit_ffc_area);
610 ATF_TP_ADD_TC(tp, bit_ffs_area);
611 BITSTRING_TC_ADD(tp, bit_set);
612 BITSTRING_TC_ADD(tp, bit_clear);
613 BITSTRING_TC_ADD(tp, bit_ffs);
614 BITSTRING_TC_ADD(tp, bit_ffc);
615 BITSTRING_TC_ADD(tp, bit_ffs_at);
616 BITSTRING_TC_ADD(tp, bit_ffc_at);
617 BITSTRING_TC_ADD(tp, bit_nclear);
618 BITSTRING_TC_ADD(tp, bit_nset);
619 BITSTRING_TC_ADD(tp, bit_count);
620 BITSTRING_TC_ADD(tp, bit_ffs_area_no_match);
621 BITSTRING_TC_ADD(tp, bit_ffc_area_no_match);
623 return (atf_no_error());