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
39typedef void (testfunc_t)(bitstr_t *bstr, int nbits, const char *memloc);
40
41static void
42bitstring_run_stack_test(testfunc_t *test, int nbits)
43{
44	bitstr_t bit_decl(bitstr, nbits);
45
46	test(bitstr, nbits, "stack");
47}
48
49static void
50bitstring_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
58static void
59bitstring_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)				\
80ATF_TC_WITHOUT_HEAD(name);					\
81static testfunc_t name ## _test;				\
82								\
83ATF_TC_BODY(name, tc)						\
84{								\
85	bitstring_test_runner(name ## _test);			\
86}								\
87								\
88static void							\
89name ## _test(bitstr_t *bitstr, int nbits, const char *memloc)
90
91#define	BITSTRING_TC_ADD(tp, name)				\
92do {								\
93	ATF_TP_ADD_TC(tp, name);				\
94} while (0)
95
96ATF_TC_WITHOUT_HEAD(bitstr_in_struct);
97ATF_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
106ATF_TC_WITHOUT_HEAD(bitstr_size);
107ATF_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
117BITSTRING_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
135BITSTRING_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
154BITSTRING_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
177BITSTRING_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
200BITSTRING_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
263BITSTRING_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
325BITSTRING_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
359BITSTRING_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
393ATF_TC_WITHOUT_HEAD(bit_ffs_area);
394ATF_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
477ATF_TC_WITHOUT_HEAD(bit_ffc_area);
478ATF_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
549BITSTRING_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
576BITSTRING_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
603BITSTRING_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
664BITSTRING_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
718BITSTRING_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
763BITSTRING_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
819BITSTRING_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 */
877ATF_TC_WITHOUT_HEAD(bitstr_large);
878ATF_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
952ATF_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