svn commit: r356306 - in stable/12: share/man/man3 sys/sys tests/sys/sys
Eric Joyner
erj at FreeBSD.org
Thu Jan 2 23:16:29 UTC 2020
Author: erj
Date: Thu Jan 2 23:16:27 2020
New Revision: 356306
URL: https://svnweb.freebsd.org/changeset/base/356306
Log:
MFC r354977: bitstring: add functions to find contiguous set/unset bit sequences
This MFC also includes extra commits that improve on the original:
r355032: bitstring: Fix error messages in tests for area functions
r355377: Improve bit_ffc_area and bit_ffs_area_at implementation
r355400: bitstring: avoid gcc -Wsign-compare
Sponsored by: Intel Corporation
Modified:
stable/12/share/man/man3/bitstring.3
stable/12/sys/sys/bitstring.h
stable/12/sys/sys/param.h
stable/12/tests/sys/sys/bitstring_test.c
Directory Properties:
stable/12/ (props changed)
Modified: stable/12/share/man/man3/bitstring.3
==============================================================================
--- stable/12/share/man/man3/bitstring.3 Thu Jan 2 23:07:45 2020 (r356305)
+++ stable/12/share/man/man3/bitstring.3 Thu Jan 2 23:16:27 2020 (r356306)
@@ -58,7 +58,7 @@
.\" @(#)bitstring.3 8.1 (Berkeley) 7/19/93
.\" $FreeBSD$
.\"
-.Dd May 23, 2016
+.Dd Nov 18, 2019
.Dt BITSTRING 3
.Os
.Sh NAME
@@ -70,6 +70,10 @@
.Nm bit_ffs ,
.Nm bit_ffc_at ,
.Nm bit_ffs_at ,
+.Nm bit_ffc_area ,
+.Nm bit_ffs_area ,
+.Nm bit_ffc_area_at ,
+.Nm bit_ffs_area_at ,
.Nm bit_nclear ,
.Nm bit_nset ,
.Nm bit_set ,
@@ -95,6 +99,14 @@
.Ft void
.Fn bit_ffs_at "bitstr_t *name" "int start" "int nbits" "int *value"
.Ft void
+.Fn bit_ffc_area "bitstr_t *name" "int nbits" "int size" "int *value"
+.Ft void
+.Fn bit_ffs_area "bitstr_t *name" "int nbits" "int size" "int *value"
+.Ft void
+.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"
+.Ft void
.Fn bit_nclear "bitstr_t *name" "int start" "int stop"
.Ft void
.Fn bit_nset "bitstr_t *name" "int start" "int stop"
@@ -223,6 +235,82 @@ bits referenced by
at or after the zero-based bit index
.Fa start .
If no bits are set after
+.Fa start ,
+the location referenced by
+.Fa value
+is set to \-1.
+.Pp
+The
+.Fn bit_ffc_area
+function stores in the location referenced by
+.Fa value
+the zero-based number of the first bit beginning a sequence of unset bits of
+at least
+.Fa size
+unset bits in the array of
+.Fa nbits
+bits referenced by
+.Fa name .
+If no sequence of contiguous unset bits of the specified
+.Fa size
+can be found, the location referenced by
+.Fa value
+is set to \-1.
+.Pp
+The
+.Fn bit_ffs_area
+function stores in the location referenced by
+.Fa value
+the zero-based number of the first bit beginning a sequence of set bits of
+at least
+.Fa size
+set bits in the array of
+.Fa nbits
+bits referenced by
+.Fa name .
+If no sequence of contiguous set bits of the specified
+.Fa size
+can be found, the location referenced by
+.Fa value
+is set to \-1.
+.Pp
+The
+.Fn bit_ffc_area_at
+function stores in the location referenced by
+.Fa value
+the zero-based number of the first bit beginning a sequence of unset bits of
+at least
+.Fa size
+unset bits in the array of
+.Fa nbits
+bits referenced by
+.Fa name ,
+at or after the zero-based bit index
+.Fa start .
+If no sequence of contiguous unset bits of the specified
+.Fa size
+can be found at or after
+.Fa start ,
+the location referenced by
+.Fa value
+is set to \-1.
+.Pp
+The
+.Fn bit_ffs_area_at
+function stores in the location referenced by
+.Fa value
+the zero-based number of the first bit beginning a sequence of set bits of
+at least
+.Fa size
+set bits in the array of
+.Fa nbits
+bits referenced by
+.Fa name ,
+at or after the zero-based bit index
+.Fa start .
+If no sequence of contiguous set bits of the specified
+.Fa size
+can be found at or after
.Fa start ,
the location referenced by
.Fa value
Modified: stable/12/sys/sys/bitstring.h
==============================================================================
--- stable/12/sys/sys/bitstring.h Thu Jan 2 23:07:45 2020 (r356305)
+++ stable/12/sys/sys/bitstring.h Thu Jan 2 23:16:27 2020 (r356306)
@@ -275,6 +275,114 @@ bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result)
bit_ffc_at(_bitstr, /*start*/0, _nbits, _result);
}
+/* Find contiguous sequence of at least size set bits at or after start */
+static inline void
+bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
+ int *_result)
+{
+ bitstr_t *_curbitstr;
+ bitstr_t _test;
+ int _value, _offset, _logsize, _b;
+
+ if (_start + _size > _nbits || _nbits <= 0) {
+ *_result = -1;
+ return;
+ }
+
+ _logsize = fls(_size - 1);
+ _value = _start;
+ _curbitstr = _bitstr + _bit_idx(_start);
+ _test = ~*_curbitstr;
+ if (_bit_offset(_start) != 0)
+ _test |= _bit_make_mask(0, _start - 1);
+ for (_offset = 0;; _offset -= _BITSTR_BITS, _test = ~*++_curbitstr) {
+ if (_test != 0) {
+ /* If leading 0s in _test can finish 0-area, stop. */
+ if (_offset + _size < (int)_BITSTR_BITS &&
+ (_test & _bit_make_mask(0, _offset + _size)) == 0)
+ break;
+ /* Shrink-left every 0-area in _test by size-1 bits. */
+ _b = _logsize;
+ while ((_test & (_test + 1)) != 0 && _b-- > 0)
+ _test |= _test >> (((_size - 1) >> _b) + 1) / 2;
+ /* Find the start of the first 0-area in _test. */
+ _offset = (~_test == 0) ? (int)_BITSTR_BITS :
+ ffsl(~_test) - 1;
+ _value = (_curbitstr - _bitstr) * _BITSTR_BITS +
+ _offset;
+ /* If there's insufficient space left, give up. */
+ if (_value + _size > _nbits) {
+ _value = -1;
+ break;
+ }
+ }
+ if (_offset + _size <= (int)_BITSTR_BITS)
+ break;
+ }
+ *_result = _value;
+}
+
+/* Find contiguous sequence of at least size cleared bits at or after start */
+static inline void
+bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
+ int *_result)
+{
+ bitstr_t *_curbitstr;
+ bitstr_t _test;
+ int _value, _offset, _logsize, _b;
+
+ if (_start + _size > _nbits || _nbits <= 0) {
+ *_result = -1;
+ return;
+ }
+
+ _logsize = fls(_size - 1);
+ _value = _start;
+ _curbitstr = _bitstr + _bit_idx(_start);
+ _test = *_curbitstr;
+ if (_bit_offset(_start) != 0)
+ _test |= _bit_make_mask(0, _start - 1);
+ for (_offset = 0;; _offset -= _BITSTR_BITS, _test = *++_curbitstr) {
+ if (_test != 0) {
+ /* If leading 0s in _test can finish 0-area, stop. */
+ if (_offset + _size < (int)_BITSTR_BITS &&
+ (_test & _bit_make_mask(0, _offset + _size)) == 0)
+ break;
+ /* Shrink-left every 0-area in _test by size-1 bits. */
+ _b = _logsize;
+ while ((_test & (_test + 1)) != 0 && _b-- > 0)
+ _test |= _test >> (((_size - 1) >> _b) + 1) / 2;
+ /* Find the start of the first 0-area in _test. */
+ _offset = (~_test == 0) ? (int)_BITSTR_BITS :
+ ffsl(~_test) - 1;
+ _value = (_curbitstr - _bitstr) * _BITSTR_BITS +
+ _offset;
+ /* If there's insufficient space left, give up. */
+ if (_value + _size > _nbits) {
+ _value = -1;
+ break;
+ }
+ }
+ if (_offset + _size <= (int)_BITSTR_BITS)
+ break;
+ }
+ *_result = _value;
+}
+
+/* Find contiguous sequence of at least size set bits in bit string */
+static inline void
+bit_ffs_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
+{
+ bit_ffs_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
+}
+
+/* Find contiguous sequence of at least size cleared bits in bit string */
+static inline void
+bit_ffc_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
+{
+ bit_ffc_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
+}
+
/* Count the number of bits set in a bitstr of size _nbits at or after _start */
static inline void
bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
Modified: stable/12/sys/sys/param.h
==============================================================================
--- stable/12/sys/sys/param.h Thu Jan 2 23:07:45 2020 (r356305)
+++ stable/12/sys/sys/param.h Thu Jan 2 23:16:27 2020 (r356306)
@@ -60,7 +60,7 @@
* in the range 5 to 9.
*/
#undef __FreeBSD_version
-#define __FreeBSD_version 1201506 /* Master, propagated to newvers */
+#define __FreeBSD_version 1201507 /* Master, propagated to newvers */
/*
* __FreeBSD_kernel__ indicates that this system uses the kernel of FreeBSD,
Modified: stable/12/tests/sys/sys/bitstring_test.c
==============================================================================
--- stable/12/tests/sys/sys/bitstring_test.c Thu Jan 2 23:07:45 2020 (r356305)
+++ stable/12/tests/sys/sys/bitstring_test.c Thu Jan 2 23:16:27 2020 (r356306)
@@ -321,6 +321,169 @@ BITSTRING_TC_DEFINE(bit_ffc_at)
nbits, memloc, nbits + 3, found_clear_bit);
}
+BITSTRING_TC_DEFINE(bit_ffc_area_no_match)
+/* bitstr_t *bitstr, int nbits, const char *memloc */
+{
+ int found_clear_bits;
+
+ memset(bitstr, 0xFF, bitstr_size(nbits));
+ bit_ffc_area(bitstr, nbits, 2, &found_clear_bits);
+ ATF_REQUIRE_EQ_MSG(-1, found_clear_bits,
+ "bit_ffc_area_%d_%s: Failed all set bits.", nbits, memloc);
+}
+
+BITSTRING_TC_DEFINE(bit_ffs_area_no_match)
+/* bitstr_t *bitstr, int nbits, const char *memloc */
+{
+ int found_clear_bits;
+
+ memset(bitstr, 0, bitstr_size(nbits));
+ bit_ffs_area(bitstr, nbits, 2, &found_clear_bits);
+ ATF_REQUIRE_EQ_MSG(-1, found_clear_bits,
+ "bit_ffs_area_%d_%s: Failed all clear bits.", nbits, memloc);
+}
+
+ATF_TC_WITHOUT_HEAD(bit_ffs_area);
+ATF_TC_BODY(bit_ffs_area, tc)
+{
+ const int nbits = 72;
+ bitstr_t bit_decl(bitstr, nbits) = {};
+ int location;
+
+ bit_set(bitstr, 5);
+ bit_set(bitstr, 6);
+
+ location = 0;
+ bit_ffs_area(bitstr, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(-1, location,
+ "bit_ffs_area: found location of size 3 when only 2 bits are set");
+
+ bit_set(bitstr, 7);
+
+ location = 0;
+ bit_ffs_area(bitstr, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(5, location,
+ "bit_ffs_area: failed to find location of size 3");
+
+ bit_set(bitstr, 8);
+
+ location = 0;
+ bit_ffs_area(bitstr, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(5, location,
+ "bit_ffs_area: failed to find location of size 3");
+
+ location = 0;
+ bit_ffs_area_at(bitstr, 2, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(5, location,
+ "bit_ffs_area_at: failed to find location of size 3");
+
+ location = 0;
+ bit_ffs_area_at(bitstr, 6, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(6, location,
+ "bit_ffs_area_at: failed to find location of size 3");
+
+ location = 0;
+ bit_ffs_area_at(bitstr, 8, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(-1, location,
+ "bit_ffs_area_at: found invalid location");
+
+ bit_set(bitstr, 69);
+ bit_set(bitstr, 70);
+ bit_set(bitstr, 71);
+
+ location = 0;
+ bit_ffs_area_at(bitstr, 8, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(69, location,
+ "bit_ffs_area_at: failed to find location of size 3");
+
+ location = 0;
+ bit_ffs_area_at(bitstr, 69, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(69, location,
+ "bit_ffs_area_at: failed to find location of size 3");
+
+ location = 0;
+ bit_ffs_area_at(bitstr, 70, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(-1, location,
+ "bit_ffs_area_at: found invalid location");
+
+ location = 0;
+ bit_ffs_area_at(bitstr, 72, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(-1, location,
+ "bit_ffs_area_at: found invalid location");
+}
+
+ATF_TC_WITHOUT_HEAD(bit_ffc_area);
+ATF_TC_BODY(bit_ffc_area, tc)
+{
+ const int nbits = 80;
+ bitstr_t bit_decl(bitstr, nbits) = {};
+ int location;
+
+ /* set all bits */
+ memset(bitstr, 0xFF, bitstr_size(nbits));
+
+ bit_clear(bitstr, 7);
+ bit_clear(bitstr, 8);
+
+ location = 0;
+ bit_ffc_area(bitstr, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(-1, location,
+ "bit_ffc_area: found location of size 3 when only 2 bits are set");
+
+ bit_clear(bitstr, 9);
+
+ location = 0;
+ bit_ffc_area(bitstr, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(7, location,
+ "bit_ffc_area: failed to find location of size 3");
+
+ bit_clear(bitstr, 10);
+
+ location = 0;
+ bit_ffc_area(bitstr, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(7, location,
+ "bit_ffc_area: failed to find location of size 3");
+
+ location = 0;
+ bit_ffc_area_at(bitstr, 2, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(7, location,
+ "bit_ffc_area_at: failed to find location of size 3");
+
+ location = 0;
+ bit_ffc_area_at(bitstr, 8, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(8, location,
+ "bit_ffc_area_at: failed to find location of size 3");
+
+ location = 0;
+ bit_ffc_area_at(bitstr, 9, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(-1, location,
+ "bit_ffc_area_at: found invalid bit location");
+
+ bit_clear(bitstr, 77);
+ bit_clear(bitstr, 78);
+ bit_clear(bitstr, 79);
+
+ location = 0;
+ bit_ffc_area_at(bitstr, 12, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(77, location,
+ "bit_ffc_area_at: failed to find location of size 3");
+
+ location = 0;
+ bit_ffc_area_at(bitstr, 77, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(77, location,
+ "bit_ffc_area_at: failed to find location of size 3");
+
+ location = 0;
+ bit_ffc_area_at(bitstr, 78, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(-1, location,
+ "bit_ffc_area_at: found invalid location");
+
+ location = 0;
+ bit_ffc_area_at(bitstr, 85, nbits, 3, &location);
+ ATF_REQUIRE_EQ_MSG(-1, location,
+ "bit_ffc_area_at: found invalid location");
+}
+
BITSTRING_TC_DEFINE(bit_nclear)
/* bitstr_t *bitstr, int nbits, const char *memloc */
{
@@ -441,6 +604,8 @@ ATF_TP_ADD_TCS(tp)
ATF_TP_ADD_TC(tp, bitstr_in_struct);
ATF_TP_ADD_TC(tp, bitstr_size);
+ ATF_TP_ADD_TC(tp, bit_ffc_area);
+ ATF_TP_ADD_TC(tp, bit_ffs_area);
BITSTRING_TC_ADD(tp, bit_set);
BITSTRING_TC_ADD(tp, bit_clear);
BITSTRING_TC_ADD(tp, bit_ffs);
@@ -450,6 +615,8 @@ ATF_TP_ADD_TCS(tp)
BITSTRING_TC_ADD(tp, bit_nclear);
BITSTRING_TC_ADD(tp, bit_nset);
BITSTRING_TC_ADD(tp, bit_count);
+ BITSTRING_TC_ADD(tp, bit_ffs_area_no_match);
+ BITSTRING_TC_ADD(tp, bit_ffc_area_no_match);
return (atf_no_error());
}
More information about the svn-src-all
mailing list