Date: Thu, 2 Jan 2020 23:16:28 +0000 (UTC) From: Eric Joyner <erj@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-12@freebsd.org Subject: svn commit: r356306 - in stable/12: share/man/man3 sys/sys tests/sys/sys Message-ID: <202001022316.002NGSIw041103@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
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()); }
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?202001022316.002NGSIw041103>