Add bit_count to the bitstring(3) api

Add a bit_count function, which efficiently counts the number of bits set in
a bitstring.

sys/sys/bitstring.h
tests/sys/sys/bitstring_test.c
share/man/man3/bitstring.3
	Add bit_alloc

sys/kern/subr_unit.c
	Use bit_count instead of a naive counting loop in check_unrhdr, used
	when INVARIANTS are enabled. The userland test runs about 6x faster
	in a generic build, or 8.5x faster when built for Nehalem, which has
	the POPCNT instruction.

sys/sys/param.h
	Bump __FreeBSD_version due to the addition of bit_alloc

UPDATING
	Add a note about the ABI incompatibility of the bitstring(3)
	changes, as suggested by lidl.

Suggested by:	gibbs
Reviewed by:	gibbs, ngie
MFC after:	9 days
X-MFC-With:	299090, 300538
Relnotes:	yes
Sponsored by:	Spectra Logic Corp
Differential Revision:	https://reviews.freebsd.org/D6255

1 files changed, 62 insertions, 0 deletions

diff --git a/tests/sys/sys/bitstring_test.c b/tests/sys/sys/bitstring_test.c
index d096552..f80115a 100644
--- a/tests/sys/sys/bitstring_test.c
+++ b/tests/sys/sys/bitstring_test.c
@@ -342,6 +342,67 @@ BITSTRING_TC_DEFINE(bit_nset)
 	}
 }
 
+BITSTRING_TC_DEFINE(bit_count)
+/* bitstr_t *bitstr, int nbits, const char *memloc */
+{
+	int result, s, e, expected;
+
+	/* Empty bitstr */
+	memset(bitstr, 0, bitstr_size(nbits));
+	bit_count(bitstr, 0, nbits, &result);
+	ATF_CHECK_MSG(0 == result,
+			"bit_count_%d_%s_%s: Failed with result %d",
+			nbits, "clear", memloc, result);
+
+	/* Full bitstr */
+	memset(bitstr, 0xFF, bitstr_size(nbits));
+	bit_count(bitstr, 0, nbits, &result);
+	ATF_CHECK_MSG(nbits == result,
+			"bit_count_%d_%s_%s: Failed with result %d",
+			nbits, "set", memloc, result);
+
+	/* Invalid _start value */
+	memset(bitstr, 0xFF, bitstr_size(nbits));
+	bit_count(bitstr, nbits, nbits, &result);
+	ATF_CHECK_MSG(0 == result,
+			"bit_count_%d_%s_%s: Failed with result %d",
+			nbits, "invalid_start", memloc, result);
+	
+	/* Alternating bitstr, starts with 0 */
+	memset(bitstr, 0xAA, bitstr_size(nbits));
+	bit_count(bitstr, 0, nbits, &result);
+	ATF_CHECK_MSG(nbits / 2 == result,
+			"bit_count_%d_%s_%d_%s: Failed with result %d",
+			nbits, "alternating", 0, memloc, result);
+
+	/* Alternating bitstr, starts with 1 */
+	memset(bitstr, 0x55, bitstr_size(nbits));
+	bit_count(bitstr, 0, nbits, &result);
+	ATF_CHECK_MSG((nbits + 1) / 2 == result,
+			"bit_count_%d_%s_%d_%s: Failed with result %d",
+			nbits, "alternating", 1, memloc, result);
+
+	/* Varying start location */
+	memset(bitstr, 0xAA, bitstr_size(nbits));
+	for (s = 0; s < nbits; s++) {
+		expected = s % 2 == 0 ? (nbits - s) / 2 : (nbits - s + 1) / 2;
+		bit_count(bitstr, s, nbits, &result);
+		ATF_CHECK_MSG(expected == result,
+				"bit_count_%d_%s_%d_%s: Failed with result %d",
+				nbits, "vary_start", s, memloc, result);
+	}
+
+	/* Varying end location */
+	memset(bitstr, 0xAA, bitstr_size(nbits));
+	for (e = 0; e < nbits; e++) {
+		bit_count(bitstr, 0, e, &result);
+		ATF_CHECK_MSG(e / 2 == result,
+				"bit_count_%d_%s_%d_%s: Failed with result %d",
+				nbits, "vary_end", e, memloc, result);
+	}
+
+}
+
 ATF_TP_ADD_TCS(tp)
 {
 
@@ -354,6 +415,7 @@ ATF_TP_ADD_TCS(tp)
 	BITSTRING_TC_ADD(tp, bit_ffc_at);
 	BITSTRING_TC_ADD(tp, bit_nclear);
 	BITSTRING_TC_ADD(tp, bit_nset);
+	BITSTRING_TC_ADD(tp, bit_count);
 
 	return (atf_no_error());
 }