From owner-dev-commits-src-branches@freebsd.org Mon Aug 23 22:26:21 2021 Return-Path: Delivered-To: dev-commits-src-branches@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id 07AE3672BBB; Mon, 23 Aug 2021 22:26:21 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4Gtmzw5wwtz3NN8; Mon, 23 Aug 2021 22:26:20 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id A62491C540; Mon, 23 Aug 2021 22:26:20 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 17NMQKj0014859; Mon, 23 Aug 2021 22:26:20 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 17NMQK6e014858; Mon, 23 Aug 2021 22:26:20 GMT (envelope-from git) Date: Mon, 23 Aug 2021 22:26:20 GMT Message-Id: <202108232226.17NMQK6e014858@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Vladimir Kondratyev Subject: git: 8f559509a22b - stable/13 - bitstring(3): Add bitstring traversal macros. MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: wulf X-Git-Repository: src X-Git-Refname: refs/heads/stable/13 X-Git-Reftype: branch X-Git-Commit: 8f559509a22ba8725fa6ec50eca32313e5841fe2 Auto-Submitted: auto-generated X-BeenThere: dev-commits-src-branches@freebsd.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Commits to the stable branches of the FreeBSD src repository List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 23 Aug 2021 22:26:21 -0000 The branch stable/13 has been updated by wulf: URL: https://cgit.FreeBSD.org/src/commit/?id=8f559509a22ba8725fa6ec50eca32313e5841fe2 commit 8f559509a22ba8725fa6ec50eca32313e5841fe2 Author: Vladimir Kondratyev AuthorDate: 2021-08-16 20:18:58 +0000 Commit: Vladimir Kondratyev CommitDate: 2021-08-23 22:23:10 +0000 bitstring(3): Add bitstring traversal macros. The macro bit_foreach() traverses all set bits in the bitstring in the forward direction, assigning each location in turn to variable. The macro bit_foreach_at() traverses all set bits in the bitstring in the forward direction at or after the zero-based bit index, assigning each location in turn to variable. The bit_foreach_unset() and bit_foreach_unset_at() macros which traverses unset bits are implemented for completeness. Reviewed by: asomers, dougm (cherry picked from commit 14a4d6d01335dd233023834e05897377cb70d52a) --- share/man/man3/bitstring.3 | 46 ++++++++- sys/sys/bitstring.h | 16 ++++ tests/sys/sys/bitstring_test.c | 207 +++++++++++++++++++++++++++++++++++++++++ 3 files changed, 268 insertions(+), 1 deletion(-) diff --git a/share/man/man3/bitstring.3 b/share/man/man3/bitstring.3 index 20f5bae24d4d..e5be67a89e4f 100644 --- a/share/man/man3/bitstring.3 +++ b/share/man/man3/bitstring.3 @@ -58,7 +58,7 @@ .\" @(#)bitstring.3 8.1 (Berkeley) 7/19/93 .\" $FreeBSD$ .\" -.Dd November 18, 2019 +.Dd August 8, 2021 .Dt BITSTRING 3 .Os .Sh NAME @@ -106,6 +106,10 @@ .Fn bit_ffc_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int *value" .Ft void .Fn bit_ffs_area_at "bitstr_t *name" "int start" "int nbits" "int size" "int *value" +.Fn bit_foreach "bitstr_t *name" "int nbits" "int var" +.Fn bit_foreach_at "bitstr_t *name" "int start" "int nbits" "int var" +.Fn bit_foreach_unset "bitstr_t *name" "int nbits" "int var" +.Fn bit_foreach_unset_at "bitstr_t *name" "int start" "int nbits" "int var" .Ft void .Fn bit_nclear "bitstr_t *name" "int start" "int stop" .Ft void @@ -327,6 +331,46 @@ bits referenced by at or after the zero-based bit index .Fa start . .Pp +The macro +.Fn bit_foreach +traverses all set bits in the array of +.Fa nbits +referenced by +.Fa name +in the forward direction, assigning each location in turn to +.Fa var . +.Pp +The macro +.Fn bit_foreach_at +traverses all set bits in the array of +.Fa nbits +referenced by +.Fa name +in the forward direction at or after the zero-based bit index +.Fa start , +assigning each location in turn to +.Fa var . +.Pp +The macro +.Fn bit_foreach_unset +traverses all unset bits in the array of +.Fa nbits +referenced by +.Fa name +in the forward direction, assigning each location in turn to +.Fa var . +.Pp +The macro +.Fn bit_foreach_unset_at +traverses all unset bits in the array of +.Fa nbits +referenced by +.Fa name +in the forward direction at or after the zero-based bit index +.Fa start , +assigning each location in turn to +.Fa var . +.Pp The arguments in bit string macros are evaluated only once and may safely have side effects. .Sh EXAMPLES diff --git a/sys/sys/bitstring.h b/sys/sys/bitstring.h index 97b841bbdda6..f898a2392be6 100644 --- a/sys/sys/bitstring.h +++ b/sys/sys/bitstring.h @@ -419,4 +419,20 @@ out: *_result = _value; } +/* Traverse all set bits, assigning each location in turn to iter */ +#define bit_foreach_at(_bitstr, _start, _nbits, _iter) \ + for (bit_ffs_at((_bitstr), (_start), (_nbits), &(_iter)); \ + (_iter) != -1; \ + bit_ffs_at((_bitstr), (_iter) + 1, (_nbits), &(_iter))) +#define bit_foreach(_bitstr, _nbits, _iter) \ + bit_foreach_at(_bitstr, /*start*/0, _nbits, _iter) + +/* Traverse all unset bits, assigning each location in turn to iter */ +#define bit_foreach_unset_at(_bitstr, _start, _nbits, _iter) \ + for (bit_ffc_at((_bitstr), (_start), (_nbits), &(_iter)); \ + (_iter) != -1; \ + bit_ffc_at((_bitstr), (_iter) + 1, (_nbits), &(_iter))) +#define bit_foreach_unset(_bitstr, _nbits, _iter) \ + bit_foreach_unset_at(_bitstr, /*start*/0, _nbits, _iter) + #endif /* _SYS_BITSTRING_H_ */ diff --git a/tests/sys/sys/bitstring_test.c b/tests/sys/sys/bitstring_test.c index 8fdc68ecf68e..c891a98645f8 100644 --- a/tests/sys/sys/bitstring_test.c +++ b/tests/sys/sys/bitstring_test.c @@ -601,6 +601,209 @@ BITSTRING_TC_DEFINE(bit_count) } +BITSTRING_TC_DEFINE(bit_foreach) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i, set_bit; + + /* Empty bitstr */ + memset(bitstr, 0x00, bitstr_size(nbits)); + bit_foreach (bitstr, nbits, set_bit) { + atf_tc_fail("bit_foreach_%d_%s_%s: Failed at location %d", + nbits, "clear", memloc, set_bit); + } + + /* Full bitstr */ + i = 0; + memset(bitstr, 0xFF, bitstr_size(nbits)); + bit_foreach(bitstr, nbits, set_bit) { + ATF_REQUIRE_MSG(set_bit == i, + "bit_foreach_%d_%s_%s: Failed on turn %d at location %d", + nbits, "set", memloc, i, set_bit); + i++; + } + ATF_REQUIRE_MSG(i == nbits, + "bit_foreach_%d_%s_%s: Invalid number of turns %d", + nbits, "set", memloc, i); + + /* Alternating bitstr, starts with 0 */ + i = 0; + memset(bitstr, 0xAA, bitstr_size(nbits)); + bit_foreach(bitstr, nbits, set_bit) { + ATF_REQUIRE_MSG(set_bit == i * 2 + 1, + "bit_foreach_%d_%s_%d_%s: " + "Failed on turn %d at location %d", + nbits, "alternating", 0, memloc, i, set_bit); + i++; + } + ATF_REQUIRE_MSG(i == nbits / 2, + "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d", + nbits, "alternating", 0, memloc, i); + + /* Alternating bitstr, starts with 1 */ + i = 0; + memset(bitstr, 0x55, bitstr_size(nbits)); + bit_foreach(bitstr, nbits, set_bit) { + ATF_REQUIRE_MSG(set_bit == i * 2, + "bit_foreach_%d_%s_%d_%s: " + "Failed on turn %d at location %d", + nbits, "alternating", 1, memloc, i, set_bit); + i++; + } + ATF_REQUIRE_MSG(i == (nbits + 1) / 2, + "bit_foreach_%d_%s_%d_%s: Invalid number of turns %d", + nbits, "alternating", 1, memloc, i); +} + +BITSTRING_TC_DEFINE(bit_foreach_at) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i, s, e, set_bit; + + /* Invalid _start value */ + memset(bitstr, 0xFF, bitstr_size(nbits)); + bit_foreach_at(bitstr, nbits, nbits, set_bit) { + atf_tc_fail("bit_foreach_at_%d_%s_%s: Failed at location %d", + nbits, "invalid_start", memloc, set_bit); + } + + /* Varying start location */ + memset(bitstr, 0xAA, bitstr_size(nbits)); + for (s = 0; s < nbits; s++) { + i = 0; + bit_foreach_at(bitstr, s, nbits, set_bit) { + ATF_REQUIRE_MSG(set_bit == (i + s / 2) * 2 + 1, + "bit_foreach_at_%d_%s_%d_%s: " + "Failed on turn %d at location %d", + nbits, "vary_start", s, memloc, i, set_bit); + i++; + } + ATF_REQUIRE_MSG(i == nbits / 2 - s / 2, + "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d", + nbits, "vary_start", s, memloc, i); + } + + /* Varying end location */ + memset(bitstr, 0xAA, bitstr_size(nbits)); + for (e = 0; e < nbits; e++) { + i = 0; + bit_foreach_at(bitstr, 0, e, set_bit) { + ATF_REQUIRE_MSG(set_bit == i * 2 + 1, + "bit_foreach_at_%d_%s_%d_%s: " + "Failed on turn %d at location %d", + nbits, "vary_end", e, memloc, i, set_bit); + i++; + } + ATF_REQUIRE_MSG(i == e / 2, + "bit_foreach_at_%d_%s_%d_%s: Invalid number of turns %d", + nbits, "vary_end", e, memloc, i); + } +} + +BITSTRING_TC_DEFINE(bit_foreach_unset) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i, unset_bit; + + /* Empty bitstr */ + i = 0; + memset(bitstr, 0, bitstr_size(nbits)); + bit_foreach_unset(bitstr, nbits, unset_bit) { + ATF_REQUIRE_MSG(unset_bit == i, + "bit_foreach_unset_%d_%s_%s: " + "Failed on turn %d at location %d", + nbits, "clear", memloc, i, unset_bit); + i++; + } + ATF_REQUIRE_MSG(i == nbits, + "bit_foreach_unset_%d_%s_%s: Invalid number of turns %d", + nbits, "set", memloc, i); + + /* Full bitstr */ + memset(bitstr, 0xFF, bitstr_size(nbits)); + bit_foreach_unset(bitstr, nbits, unset_bit) { + atf_tc_fail("bit_foreach_unset_%d_%s_%s: " + "Failed at location %d", + nbits, "set", memloc, unset_bit); + } + + /* Alternating bitstr, starts with 0 */ + i = 0; + memset(bitstr, 0xAA, bitstr_size(nbits)); + bit_foreach_unset(bitstr, nbits, unset_bit) { + ATF_REQUIRE_MSG(unset_bit == i * 2, + "bit_foreach_unset_%d_%s_%d_%s: " + "Failed on turn %d at location %d", + nbits, "alternating", 0, memloc, i, unset_bit); + i++; + } + ATF_REQUIRE_MSG(i == (nbits + 1) / 2, + "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d", + nbits, "alternating", 0, memloc, i); + + /* Alternating bitstr, starts with 1 */ + i = 0; + memset(bitstr, 0x55, bitstr_size(nbits)); + bit_foreach_unset(bitstr, nbits, unset_bit) { + ATF_REQUIRE_MSG(unset_bit == i * 2 + 1, + "bit_foreach_unset_%d_%s_%d_%s: " + "Failed on turn %d at location %d", + nbits, "alternating", 1, memloc, i, unset_bit); + i++; + } + ATF_REQUIRE_MSG(i == nbits / 2, + "bit_foreach_unset_%d_%s_%d_%s: Invalid number of turns %d", + nbits, "alternating", 1, memloc, i); +} + +BITSTRING_TC_DEFINE(bit_foreach_unset_at) +/* bitstr_t *bitstr, int nbits, const char *memloc */ +{ + int i, s, e, unset_bit; + + /* Invalid _start value */ + memset(bitstr, 0, bitstr_size(nbits)); + bit_foreach_unset_at(bitstr, nbits, nbits, unset_bit) { + atf_tc_fail("bit_foreach_unset_at_%d_%s_%s: " + "Failed at location %d", + nbits, "invalid_start", memloc, unset_bit); + } + + /* Varying start location */ + memset(bitstr, 0xAA, bitstr_size(nbits)); + for (s = 0; s < nbits; s++) { + i = 0; + bit_foreach_unset_at(bitstr, s, nbits, unset_bit) { + ATF_REQUIRE_MSG(unset_bit == (i + (s + 1) / 2) * 2, + "bit_foreach_unset_at_%d_%s_%d_%s: " + "Failed on turn %d at location %d", + nbits, "vary_start", s, memloc, i, unset_bit); + i++; + } + ATF_REQUIRE_MSG(i == (nbits + 1) / 2 - (s + 1) / 2, + "bit_foreach_unset_at_%d_%s_%d_%s: " + "Invalid number of turns %d", + nbits, "vary_start", s, memloc, i); + } + + /* Varying end location */ + memset(bitstr, 0xAA, bitstr_size(nbits)); + for (e = 0; e < nbits; e++) { + i = 0; + bit_foreach_unset_at(bitstr, 0, e, unset_bit) { + ATF_REQUIRE_MSG(unset_bit == i * 2, + "bit_foreach_unset_at_%d_%s_%d_%s: " + "Failed on turn %d at location %d", + nbits, "vary_end", e, memloc, i, unset_bit); + i++; + } + ATF_REQUIRE_MSG(i == (e + 1) / 2, + "bit_foreach_unset_at_%d_%s_%d_%s: " + "Invalid number of turns %d", + nbits, "vary_end", e, memloc, i); + } +} + ATF_TP_ADD_TCS(tp) { @@ -619,6 +822,10 @@ ATF_TP_ADD_TCS(tp) BITSTRING_TC_ADD(tp, bit_count); BITSTRING_TC_ADD(tp, bit_ffs_area_no_match); BITSTRING_TC_ADD(tp, bit_ffc_area_no_match); + BITSTRING_TC_ADD(tp, bit_foreach); + BITSTRING_TC_ADD(tp, bit_foreach_at); + BITSTRING_TC_ADD(tp, bit_foreach_unset); + BITSTRING_TC_ADD(tp, bit_foreach_unset_at); return (atf_no_error()); }