Index: stable/12/share/man/man3/bitstring.3 =================================================================== --- stable/12/share/man/man3/bitstring.3 (revision 356305) +++ stable/12/share/man/man3/bitstring.3 (revision 356306) @@ -1,277 +1,365 @@ .\" Copyright (c) 1989, 1991, 1993 .\" The Regents of the University of California. All rights reserved. .\" .\" This code is derived from software contributed to Berkeley by .\" Paul Vixie. .\" Redistribution and use in source and binary forms, with or without .\" modification, are permitted provided that the following conditions .\" are met: .\" 1. Redistributions of source code must retain the above copyright .\" notice, this list of conditions and the following disclaimer. .\" 2. Redistributions in binary form must reproduce the above copyright .\" notice, this list of conditions and the following disclaimer in the .\" documentation and/or other materials provided with the distribution. .\" 3. Neither the name of the University nor the names of its contributors .\" may be used to endorse or promote products derived from this software .\" without specific prior written permission. .\" .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" .\" Copyright (c) 2014,2016 Spectra Logic Corporation .\" All rights reserved. .\" .\" Redistribution and use in source and binary forms, with or without .\" modification, are permitted provided that the following conditions .\" are met: .\" 1. Redistributions of source code must retain the above copyright .\" notice, this list of conditions, and the following disclaimer, .\" without modification. .\" 2. Redistributions in binary form must reproduce at minimum a disclaimer .\" substantially similar to the "NO WARRANTY" disclaimer below .\" ("Disclaimer") and any redistribution must be conditioned upon .\" including a substantially similar Disclaimer requirement for further .\" binary redistribution. .\" .\" NO WARRANTY .\" THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS .\" "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT .\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR .\" A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT .\" HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, .\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING .\" IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE .\" POSSIBILITY OF SUCH DAMAGES. .\" .\" @(#)bitstring.3 8.1 (Berkeley) 7/19/93 .\" $FreeBSD$ .\" -.Dd May 23, 2016 +.Dd Nov 18, 2019 .Dt BITSTRING 3 .Os .Sh NAME .Nm bit_alloc , .Nm bit_clear , .Nm bit_count , .Nm bit_decl , .Nm bit_ffc , .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 , .Nm bit_test , .Nm bitstr_size .Nd bit-string manipulation functions and macros .Sh SYNOPSIS .In bitstring.h .Ft bitstr_t * .Fn bit_alloc "int nbits" .Ft void .Fn bit_decl "bitstr_t *name" "int nbits" .Ft void .Fn bit_clear "bitstr_t *name" "int bit" .Ft void .Fn bit_count "bitstr_t *name" "int count" "int nbits" "int *value" .Ft void .Fn bit_ffc "bitstr_t *name" "int nbits" "int *value" .Ft void .Fn bit_ffs "bitstr_t *name" "int nbits" "int *value" .Ft void .Fn bit_ffc_at "bitstr_t *name" "int start" "int nbits" "int *value" .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" .Ft void .Fn bit_set "bitstr_t *name" "int bit" .Ft int .Fn bitstr_size "int nbits" .Ft int .Fn bit_test "bitstr_t *name" "int bit" .Sh DESCRIPTION These macros operate on strings of bits. .Pp The function .Fn bit_alloc returns a pointer of type .Dq Fa "bitstr_t *" to sufficient space to store .Fa nbits bits, or .Dv NULL if no space is available. If successful, the returned bit string is initialized with all bits cleared. .Pp The macro .Fn bit_decl declares a bit string with sufficient space to store .Fa nbits bits. .Fn bit_decl may be used to include statically sized bit strings in structure definitions or to create bit strings on the stack. Users of this macro are responsible for initialization of the bit string, typically via a global initialization of the containing struct or use of the .Fn bit_nset or .Fn bin_nclear functions. .Pp The macro .Fn bitstr_size returns the number of bytes necessary to store .Fa nbits bits. This is useful for copying bit strings. .Pp The functions .Fn bit_clear and .Fn bit_set clear or set the zero-based numbered bit .Fa bit , in the bit string .Ar name . .Pp The .Fn bit_nset and .Fn bit_nclear functions set or clear the zero-based numbered bits from .Fa start through .Fa stop in the bit string .Ar name . .Pp The .Fn bit_test function evaluates to non-zero if the zero-based numbered bit .Fa bit of bit string .Fa name is set, and zero otherwise. .Pp The function .Fn bit_ffc stores in the location referenced by .Fa value the zero-based number of the first bit not set in the array of .Fa nbits bits referenced by .Fa name . If all bits are set, the location referenced by .Fa value is set to \-1. .Pp The .Fn bit_ffs function stores in the location referenced by .Fa value the zero-based number of the first bit set in the array of .Fa nbits bits referenced by .Fa name . If no bits are set, the location referenced by .Fa value is set to \-1. .Pp The function .Fn bit_ffc_at stores in the location referenced by .Fa value the zero-based number of the first bit not set in the array of .Fa nbits bits referenced by .Fa name , at or after the zero-based bit index .Fa start . If all bits at or after .Fa start are set, the location referenced by .Fa value is set to \-1. .Pp The .Fn bit_ffs_at function stores in the location referenced by .Fa value the zero-based number of the first bit set in the array of .Fa nbits bits referenced by .Fa name , 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 is set to \-1. .Pp The .Fn bit_count function stores in the location referenced by .Fa value the number of bits set in the array of .Fa nbits bits referenced by .Fa name , at or after the zero-based bit index .Fa start . .Pp The arguments in bit string macros are evaluated only once and may safely have side effects. .Sh EXAMPLES .Bd -literal -offset indent #include #include \&... #define LPR_BUSY_BIT 0 #define LPR_FORMAT_BIT 1 #define LPR_DOWNLOAD_BIT 2 \&... #define LPR_AVAILABLE_BIT 9 #define LPR_MAX_BITS 10 make_lpr_available() { bitstr_t bit_decl(bitlist, LPR_MAX_BITS); ... bit_nclear(bitlist, 0, LPR_MAX_BITS - 1); ... if (!bit_test(bitlist, LPR_BUSY_BIT)) { bit_clear(bitlist, LPR_FORMAT_BIT); bit_clear(bitlist, LPR_DOWNLOAD_BIT); bit_set(bitlist, LPR_AVAILABLE_BIT); } } .Ed .Sh SEE ALSO .Xr malloc 3 , .Xr bitset 9 .Sh HISTORY The .Nm bitstring functions first appeared in .Bx 4.4 . Index: stable/12/sys/sys/bitstring.h =================================================================== --- stable/12/sys/sys/bitstring.h (revision 356305) +++ stable/12/sys/sys/bitstring.h (revision 356306) @@ -1,314 +1,422 @@ /*- * SPDX-License-Identifier: BSD-3-Clause * * Copyright (c) 1989, 1993 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by * Paul Vixie. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * Copyright (c) 2014 Spectra Logic Corporation * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions, and the following disclaimer, * without modification. * 2. Redistributions in binary form must reproduce at minimum a disclaimer * substantially similar to the "NO WARRANTY" disclaimer below * ("Disclaimer") and any redistribution must be conditioned upon * including a substantially similar Disclaimer requirement for further * binary redistribution. * * NO WARRANTY * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGES. * * $FreeBSD$ */ #ifndef _SYS_BITSTRING_H_ #define _SYS_BITSTRING_H_ #ifdef _KERNEL #include #include #endif #include typedef unsigned long bitstr_t; /*---------------------- Private Implementation Details ----------------------*/ #define _BITSTR_MASK (~0UL) #define _BITSTR_BITS (sizeof(bitstr_t) * 8) #ifdef roundup2 #define _bit_roundup2 roundup2 #else #define _bit_roundup2(x, y) (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */ #endif /* bitstr_t in bit string containing the bit. */ static inline int _bit_idx(int _bit) { return (_bit / _BITSTR_BITS); } /* bit number within bitstr_t at _bit_idx(_bit). */ static inline int _bit_offset(int _bit) { return (_bit % _BITSTR_BITS); } /* Mask for the bit within its long. */ static inline bitstr_t _bit_mask(int _bit) { return (1UL << _bit_offset(_bit)); } static inline bitstr_t _bit_make_mask(int _start, int _stop) { return ((_BITSTR_MASK << _bit_offset(_start)) & (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1))); } /*----------------------------- Public Interface -----------------------------*/ /* Number of bytes allocated for a bit string of nbits bits */ #define bitstr_size(_nbits) (_bit_roundup2(_nbits, _BITSTR_BITS) / 8) /* Allocate a bit string initialized with no bits set. */ #ifdef _KERNEL static inline bitstr_t * bit_alloc(int _nbits, struct malloc_type *type, int flags) { return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO)); } #else static inline bitstr_t * bit_alloc(int _nbits) { return ((bitstr_t *)calloc(bitstr_size(_nbits), 1)); } #endif /* Allocate a bit string on the stack */ #define bit_decl(name, nbits) \ ((name)[bitstr_size(nbits) / sizeof(bitstr_t)]) /* Is bit N of bit string set? */ static inline int bit_test(const bitstr_t *_bitstr, int _bit) { return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0); } /* Set bit N of bit string. */ static inline void bit_set(bitstr_t *_bitstr, int _bit) { _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit); } /* clear bit N of bit string name */ static inline void bit_clear(bitstr_t *_bitstr, int _bit) { _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit); } /* Set bits start ... stop inclusive in bit string. */ static inline void bit_nset(bitstr_t *_bitstr, int _start, int _stop) { bitstr_t *_stopbitstr; _stopbitstr = _bitstr + _bit_idx(_stop); _bitstr += _bit_idx(_start); if (_bitstr == _stopbitstr) { *_bitstr |= _bit_make_mask(_start, _stop); } else { *_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1); while (++_bitstr < _stopbitstr) *_bitstr = _BITSTR_MASK; *_stopbitstr |= _bit_make_mask(0, _stop); } } /* Clear bits start ... stop inclusive in bit string. */ static inline void bit_nclear(bitstr_t *_bitstr, int _start, int _stop) { bitstr_t *_stopbitstr; _stopbitstr = _bitstr + _bit_idx(_stop); _bitstr += _bit_idx(_start); if (_bitstr == _stopbitstr) { *_bitstr &= ~_bit_make_mask(_start, _stop); } else { *_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1); while (++_bitstr < _stopbitstr) *_bitstr = 0; *_stopbitstr &= ~_bit_make_mask(0, _stop); } } /* Find the first bit set in bit string at or after bit start. */ static inline void bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result) { bitstr_t *_curbitstr; bitstr_t *_stopbitstr; bitstr_t _test; int _value, _offset; if (_start >= _nbits) { *_result = -1; return; } if (_nbits > 0) { _curbitstr = _bitstr + _bit_idx(_start); _stopbitstr = _bitstr + _bit_idx(_nbits - 1); _test = *_curbitstr; if (_bit_offset(_start) != 0) _test &= _bit_make_mask(_start, _BITSTR_BITS - 1); while (_test == 0 && _curbitstr < _stopbitstr) _test = *(++_curbitstr); _offset = ffsl(_test); _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1; if (_offset == 0 || _value >= _nbits) _value = -1; } else { _value = -1; } *_result = _value; } /* Find the first bit clear in bit string at or after bit start. */ static inline void bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result) { bitstr_t *_curbitstr; bitstr_t *_stopbitstr; bitstr_t _test; int _value, _offset; if (_start >= _nbits) { *_result = -1; return; } if (_nbits > 0) { _curbitstr = _bitstr + _bit_idx(_start); _stopbitstr = _bitstr + _bit_idx(_nbits - 1); _test = *_curbitstr; if (_bit_offset(_start) != 0) _test |= _bit_make_mask(0, _start - 1); while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr) _test = *(++_curbitstr); _offset = ffsl(~_test); _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1; if (_offset == 0 || _value >= _nbits) _value = -1; } else { _value = -1; } *_result = _value; } /* Find the first bit set in bit string. */ static inline void bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result) { bit_ffs_at(_bitstr, /*start*/0, _nbits, _result); } /* Find the first bit clear in bit string. */ static inline void 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) { bitstr_t *_curbitstr, mask; int _value = 0, curbitstr_len; if (_start >= _nbits) goto out; _curbitstr = _bitstr + _bit_idx(_start); _nbits -= _BITSTR_BITS * _bit_idx(_start); _start -= _BITSTR_BITS * _bit_idx(_start); if (_start > 0) { curbitstr_len = (int)_BITSTR_BITS < _nbits ? (int)_BITSTR_BITS : _nbits; mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1)); _value += __bitcountl(*_curbitstr & mask); _curbitstr++; _nbits -= _BITSTR_BITS; } while (_nbits >= (int)_BITSTR_BITS) { _value += __bitcountl(*_curbitstr); _curbitstr++; _nbits -= _BITSTR_BITS; } if (_nbits > 0) { mask = _bit_make_mask(0, _bit_offset(_nbits - 1)); _value += __bitcountl(*_curbitstr & mask); } out: *_result = _value; } #endif /* _SYS_BITSTRING_H_ */ Index: stable/12/sys/sys/param.h =================================================================== --- stable/12/sys/sys/param.h (revision 356305) +++ stable/12/sys/sys/param.h (revision 356306) @@ -1,365 +1,365 @@ /*- * SPDX-License-Identifier: BSD-3-Clause * * Copyright (c) 1982, 1986, 1989, 1993 * The Regents of the University of California. All rights reserved. * (c) UNIX System Laboratories, Inc. * All or some portions of this file are derived from material licensed * to the University of California by American Telephone and Telegraph * Co. or Unix System Laboratories, Inc. and are reproduced herein with * the permission of UNIX System Laboratories, Inc. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * @(#)param.h 8.3 (Berkeley) 4/4/95 * $FreeBSD$ */ #ifndef _SYS_PARAM_H_ #define _SYS_PARAM_H_ #include #define BSD 199506 /* System version (year & month). */ #define BSD4_3 1 #define BSD4_4 1 /* * __FreeBSD_version numbers are documented in the Porter's Handbook. * If you bump the version for any reason, you should update the documentation * there. * Currently this lives here in the doc/ repository: * * head/en_US.ISO8859-1/books/porters-handbook/versions/chapter.xml * * scheme is: Rxx * 'R' is in the range 0 to 4 if this is a release branch or * X.0-CURRENT before releng/X.0 is created, otherwise 'R' is * 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, * which by definition is always true on FreeBSD. This macro is also defined * on other systems that use the kernel of FreeBSD, such as GNU/kFreeBSD. * * It is tempting to use this macro in userland code when we want to enable * kernel-specific routines, and in fact it's fine to do this in code that * is part of FreeBSD itself. However, be aware that as presence of this * macro is still not widespread (e.g. older FreeBSD versions, 3rd party * compilers, etc), it is STRONGLY DISCOURAGED to check for this macro in * external applications without also checking for __FreeBSD__ as an * alternative. */ #undef __FreeBSD_kernel__ #define __FreeBSD_kernel__ #if defined(_KERNEL) || defined(IN_RTLD) #define P_OSREL_SIGWAIT 700000 #define P_OSREL_SIGSEGV 700004 #define P_OSREL_MAP_ANON 800104 #define P_OSREL_MAP_FSTRICT 1100036 #define P_OSREL_SHUTDOWN_ENOTCONN 1100077 #define P_OSREL_MAP_GUARD 1200035 #define P_OSREL_WRFSBASE 1200041 #define P_OSREL_CK_CYLGRP 1200046 #define P_OSREL_VMTOTAL64 1200054 #define P_OSREL_MAJOR(x) ((x) / 100000) #endif #ifndef LOCORE #include #endif /* * Machine-independent constants (some used in following include files). * Redefined constants are from POSIX 1003.1 limits file. * * MAXCOMLEN should be >= sizeof(ac_comm) (see ) */ #include #define MAXCOMLEN 19 /* max command name remembered */ #define MAXINTERP PATH_MAX /* max interpreter file name length */ #define MAXLOGNAME 33 /* max login name length (incl. NUL) */ #define MAXUPRC CHILD_MAX /* max simultaneous processes */ #define NCARGS ARG_MAX /* max bytes for an exec function */ #define NGROUPS (NGROUPS_MAX+1) /* max number groups */ #define NOFILE OPEN_MAX /* max open files per process */ #define NOGROUP 65535 /* marker for empty group set member */ #define MAXHOSTNAMELEN 256 /* max hostname size */ #define SPECNAMELEN 63 /* max length of devicename */ /* More types and definitions used throughout the kernel. */ #ifdef _KERNEL #include #include #ifndef LOCORE #include #include #endif #ifndef FALSE #define FALSE 0 #endif #ifndef TRUE #define TRUE 1 #endif #endif #ifndef _KERNEL /* Signals. */ #include #endif /* Machine type dependent parameters. */ #include #ifndef _KERNEL #include #endif #ifndef DEV_BSHIFT #define DEV_BSHIFT 9 /* log2(DEV_BSIZE) */ #endif #define DEV_BSIZE (1<>PAGE_SHIFT) #endif /* * btodb() is messy and perhaps slow because `bytes' may be an off_t. We * want to shift an unsigned type to avoid sign extension and we don't * want to widen `bytes' unnecessarily. Assume that the result fits in * a daddr_t. */ #ifndef btodb #define btodb(bytes) /* calculates (bytes / DEV_BSIZE) */ \ (sizeof (bytes) > sizeof(long) \ ? (daddr_t)((unsigned long long)(bytes) >> DEV_BSHIFT) \ : (daddr_t)((unsigned long)(bytes) >> DEV_BSHIFT)) #endif #ifndef dbtob #define dbtob(db) /* calculates (db * DEV_BSIZE) */ \ ((off_t)(db) << DEV_BSHIFT) #endif #define PRIMASK 0x0ff #define PCATCH 0x100 /* OR'd with pri for tsleep to check signals */ #define PDROP 0x200 /* OR'd with pri to stop re-entry of interlock mutex */ #define NZERO 0 /* default "nice" */ #define NBBY 8 /* number of bits in a byte */ #define NBPW sizeof(int) /* number of bytes per word (integer) */ #define CMASK 022 /* default file mask: S_IWGRP|S_IWOTH */ #define NODEV (dev_t)(-1) /* non-existent device */ /* * File system parameters and macros. * * MAXBSIZE - Filesystems are made out of blocks of at most MAXBSIZE bytes * per block. MAXBSIZE may be made larger without effecting * any existing filesystems as long as it does not exceed MAXPHYS, * and may be made smaller at the risk of not being able to use * filesystems which require a block size exceeding MAXBSIZE. * * MAXBCACHEBUF - Maximum size of a buffer in the buffer cache. This must * be >= MAXBSIZE and can be set differently for different * architectures by defining it in . * Making this larger allows NFS to do larger reads/writes. * * BKVASIZE - Nominal buffer space per buffer, in bytes. BKVASIZE is the * minimum KVM memory reservation the kernel is willing to make. * Filesystems can of course request smaller chunks. Actual * backing memory uses a chunk size of a page (PAGE_SIZE). * The default value here can be overridden on a per-architecture * basis by defining it in . * * If you make BKVASIZE too small you risk seriously fragmenting * the buffer KVM map which may slow things down a bit. If you * make it too big the kernel will not be able to optimally use * the KVM memory reserved for the buffer cache and will wind * up with too-few buffers. * * The default is 16384, roughly 2x the block size used by a * normal UFS filesystem. */ #define MAXBSIZE 65536 /* must be power of 2 */ #ifndef MAXBCACHEBUF #define MAXBCACHEBUF MAXBSIZE /* must be a power of 2 >= MAXBSIZE */ #endif #ifndef BKVASIZE #define BKVASIZE 16384 /* must be power of 2 */ #endif #define BKVAMASK (BKVASIZE-1) /* * MAXPATHLEN defines the longest permissible path length after expanding * symbolic links. It is used to allocate a temporary buffer from the buffer * pool in which to do the name expansion, hence should be a power of two, * and must be less than or equal to MAXBSIZE. MAXSYMLINKS defines the * maximum number of symbolic links that may be expanded in a path name. * It should be set high enough to allow all legitimate uses, but halt * infinite loops reasonably quickly. */ #define MAXPATHLEN PATH_MAX #define MAXSYMLINKS 32 /* Bit map related macros. */ #define setbit(a,i) (((unsigned char *)(a))[(i)/NBBY] |= 1<<((i)%NBBY)) #define clrbit(a,i) (((unsigned char *)(a))[(i)/NBBY] &= ~(1<<((i)%NBBY))) #define isset(a,i) \ (((const unsigned char *)(a))[(i)/NBBY] & (1<<((i)%NBBY))) #define isclr(a,i) \ ((((const unsigned char *)(a))[(i)/NBBY] & (1<<((i)%NBBY))) == 0) /* Macros for counting and rounding. */ #ifndef howmany #define howmany(x, y) (((x)+((y)-1))/(y)) #endif #define nitems(x) (sizeof((x)) / sizeof((x)[0])) #define rounddown(x, y) (((x)/(y))*(y)) #define rounddown2(x, y) ((x)&(~((y)-1))) /* if y is power of two */ #define roundup(x, y) ((((x)+((y)-1))/(y))*(y)) /* to any y */ #define roundup2(x, y) (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */ #define powerof2(x) ((((x)-1)&(x))==0) /* Macros for min/max. */ #define MIN(a,b) (((a)<(b))?(a):(b)) #define MAX(a,b) (((a)>(b))?(a):(b)) #ifdef _KERNEL /* * Basic byte order function prototypes for non-inline functions. */ #ifndef LOCORE #ifndef _BYTEORDER_PROTOTYPED #define _BYTEORDER_PROTOTYPED __BEGIN_DECLS __uint32_t htonl(__uint32_t); __uint16_t htons(__uint16_t); __uint32_t ntohl(__uint32_t); __uint16_t ntohs(__uint16_t); __END_DECLS #endif #endif #ifndef _BYTEORDER_FUNC_DEFINED #define _BYTEORDER_FUNC_DEFINED #define htonl(x) __htonl(x) #define htons(x) __htons(x) #define ntohl(x) __ntohl(x) #define ntohs(x) __ntohs(x) #endif /* !_BYTEORDER_FUNC_DEFINED */ #endif /* _KERNEL */ /* * Scale factor for scaled integers used to count %cpu time and load avgs. * * The number of CPU `tick's that map to a unique `%age' can be expressed * by the formula (1 / (2 ^ (FSHIFT - 11))). The maximum load average that * can be calculated (assuming 32 bits) can be closely approximated using * the formula (2 ^ (2 * (16 - FSHIFT))) for (FSHIFT < 15). * * For the scheduler to maintain a 1:1 mapping of CPU `tick' to `%age', * FSHIFT must be at least 11; this gives us a maximum load avg of ~1024. */ #define FSHIFT 11 /* bits to right of fixed binary point */ #define FSCALE (1<> (PAGE_SHIFT - DEV_BSHIFT)) #define ctodb(db) /* calculates pages to devblks */ \ ((db) << (PAGE_SHIFT - DEV_BSHIFT)) /* * Old spelling of __containerof(). */ #define member2struct(s, m, x) \ ((struct s *)(void *)((char *)(x) - offsetof(struct s, m))) /* * Access a variable length array that has been declared as a fixed * length array. */ #define __PAST_END(array, offset) (((__typeof__(*(array)) *)(array))[offset]) #endif /* _SYS_PARAM_H_ */ Index: stable/12/tests/sys/sys/bitstring_test.c =================================================================== --- stable/12/tests/sys/sys/bitstring_test.c (revision 356305) +++ stable/12/tests/sys/sys/bitstring_test.c (revision 356306) @@ -1,455 +1,622 @@ /*- * Copyright (c) 2014 Spectra Logic Corporation * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions, and the following disclaimer, * without modification. * 2. Redistributions in binary form must reproduce at minimum a disclaimer * substantially similar to the "NO WARRANTY" disclaimer below * ("Disclaimer") and any redistribution must be conditioned upon * including a substantially similar Disclaimer requirement for further * binary redistribution. * * NO WARRANTY * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGES. * * $FreeBSD$ */ #include #include #include #include typedef void (testfunc_t)(bitstr_t *bstr, int nbits, const char *memloc); static void bitstring_run_stack_test(testfunc_t *test, int nbits) { bitstr_t bit_decl(bitstr, nbits); test(bitstr, nbits, "stack"); } static void bitstring_run_heap_test(testfunc_t *test, int nbits) { bitstr_t *bitstr = bit_alloc(nbits); test(bitstr, nbits, "heap"); } static void bitstring_test_runner(testfunc_t *test) { const int bitstr_sizes[] = { 0, 1, _BITSTR_BITS - 1, _BITSTR_BITS, _BITSTR_BITS + 1, 2 * _BITSTR_BITS - 1, 2 * _BITSTR_BITS, 1023, 1024 }; for (unsigned long i = 0; i < nitems(bitstr_sizes); i++) { bitstring_run_stack_test(test, bitstr_sizes[i]); bitstring_run_heap_test(test, bitstr_sizes[i]); } } #define BITSTRING_TC_DEFINE(name) \ ATF_TC_WITHOUT_HEAD(name); \ static testfunc_t name ## _test; \ \ ATF_TC_BODY(name, tc) \ { \ bitstring_test_runner(name ## _test); \ } \ \ static void \ name ## _test(bitstr_t *bitstr, int nbits, const char *memloc) #define BITSTRING_TC_ADD(tp, name) \ do { \ ATF_TP_ADD_TC(tp, name); \ } while (0) ATF_TC_WITHOUT_HEAD(bitstr_in_struct); ATF_TC_BODY(bitstr_in_struct, tc) { struct bitstr_containing_struct { bitstr_t bit_decl(bitstr, 8); } test_struct; bit_nclear(test_struct.bitstr, 0, 8); } ATF_TC_WITHOUT_HEAD(bitstr_size); ATF_TC_BODY(bitstr_size, tc) { size_t sob = sizeof(bitstr_t); ATF_CHECK_EQ(0, bitstr_size(0)); ATF_CHECK_EQ(sob, bitstr_size(1)); ATF_CHECK_EQ(sob, bitstr_size(sob * 8)); ATF_CHECK_EQ(2 * sob, bitstr_size(sob * 8 + 1)); } BITSTRING_TC_DEFINE(bit_set) /* bitstr_t *bitstr, int nbits, const char *memloc */ { memset(bitstr, 0, bitstr_size(nbits)); for (int i = 0; i < nbits; i++) { bit_set(bitstr, i); for (int j = 0; j < nbits; j++) { ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 1 : 0, "bit_set_%d_%s: Failed on bit %d", nbits, memloc, i); } bit_clear(bitstr, i); } } BITSTRING_TC_DEFINE(bit_clear) /* bitstr_t *bitstr, int nbits, const char *memloc */ { int i, j; memset(bitstr, 0xFF, bitstr_size(nbits)); for (i = 0; i < nbits; i++) { bit_clear(bitstr, i); for (j = 0; j < nbits; j++) { ATF_REQUIRE_MSG(bit_test(bitstr, j) == (j == i) ? 0 : 1, "bit_clear_%d_%s: Failed on bit %d", nbits, memloc, i); } bit_set(bitstr, i); } } BITSTRING_TC_DEFINE(bit_ffs) /* bitstr_t *bitstr, int nbits, const char *memloc */ { int i; int found_set_bit; memset(bitstr, 0, bitstr_size(nbits)); bit_ffs(bitstr, nbits, &found_set_bit); ATF_REQUIRE_MSG(found_set_bit == -1, "bit_ffs_%d_%s: Failed all clear bits.", nbits, memloc); for (i = 0; i < nbits; i++) { memset(bitstr, 0xFF, bitstr_size(nbits)); if (i > 0) bit_nclear(bitstr, 0, i - 1); bit_ffs(bitstr, nbits, &found_set_bit); ATF_REQUIRE_MSG(found_set_bit == i, "bit_ffs_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_set_bit); } } BITSTRING_TC_DEFINE(bit_ffc) /* bitstr_t *bitstr, int nbits, const char *memloc */ { int i; int found_clear_bit; memset(bitstr, 0xFF, bitstr_size(nbits)); bit_ffc(bitstr, nbits, &found_clear_bit); ATF_REQUIRE_MSG(found_clear_bit == -1, "bit_ffc_%d_%s: Failed all set bits.", nbits, memloc); for (i = 0; i < nbits; i++) { memset(bitstr, 0, bitstr_size(nbits)); if (i > 0) bit_nset(bitstr, 0, i - 1); bit_ffc(bitstr, nbits, &found_clear_bit); ATF_REQUIRE_MSG(found_clear_bit == i, "bit_ffc_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_clear_bit); } } BITSTRING_TC_DEFINE(bit_ffs_at) /* bitstr_t *bitstr, int nbits, const char *memloc */ { int i; int found_set_bit; memset(bitstr, 0xFF, bitstr_size(nbits)); for (i = 0; i < nbits; i++) { bit_ffs_at(bitstr, i, nbits, &found_set_bit); ATF_REQUIRE_MSG(found_set_bit == i, "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_set_bit); } memset(bitstr, 0, bitstr_size(nbits)); for (i = 0; i < nbits; i++) { bit_ffs_at(bitstr, i, nbits, &found_set_bit); ATF_REQUIRE_MSG(found_set_bit == -1, "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_set_bit); } memset(bitstr, 0x55, bitstr_size(nbits)); for (i = 0; i < nbits; i++) { bit_ffs_at(bitstr, i, nbits, &found_set_bit); if (i == nbits - 1 && (nbits & 1) == 0) { ATF_REQUIRE_MSG(found_set_bit == -1, "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_set_bit); } else { ATF_REQUIRE_MSG(found_set_bit == i + (i & 1), "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_set_bit); } } memset(bitstr, 0xAA, bitstr_size(nbits)); for (i = 0; i < nbits; i++) { bit_ffs_at(bitstr, i, nbits, &found_set_bit); if (i == nbits - 1 && (nbits & 1) != 0) { ATF_REQUIRE_MSG(found_set_bit == -1, "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_set_bit); } else { ATF_REQUIRE_MSG( found_set_bit == i + ((i & 1) ? 0 : 1), "bit_ffs_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_set_bit); } } /* Pass a start value beyond the size of the bit string */ bit_ffs_at(bitstr, nbits, nbits, &found_set_bit); ATF_REQUIRE_MSG(found_set_bit == -1, "bit_ffs_at_%d_%s: Failed with high start value of %d, Result %d", nbits, memloc, nbits, found_set_bit); bit_ffs_at(bitstr, nbits + 3, nbits, &found_set_bit); ATF_REQUIRE_MSG(found_set_bit == -1, "bit_ffs_at_%d_%s: Failed with high start value of %d, Result %d", nbits, memloc, nbits + 3, found_set_bit); } BITSTRING_TC_DEFINE(bit_ffc_at) /* bitstr_t *bitstr, int nbits, const char *memloc */ { int i, found_clear_bit; memset(bitstr, 0, bitstr_size(nbits)); for (i = 0; i < nbits; i++) { bit_ffc_at(bitstr, i, nbits, &found_clear_bit); ATF_REQUIRE_MSG(found_clear_bit == i, "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_clear_bit); } memset(bitstr, 0xFF, bitstr_size(nbits)); for (i = 0; i < nbits; i++) { bit_ffc_at(bitstr, i, nbits, &found_clear_bit); ATF_REQUIRE_MSG(found_clear_bit == -1, "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_clear_bit); } memset(bitstr, 0x55, bitstr_size(nbits)); for (i = 0; i < nbits; i++) { bit_ffc_at(bitstr, i, nbits, &found_clear_bit); if (i == nbits - 1 && (nbits & 1) != 0) { ATF_REQUIRE_MSG(found_clear_bit == -1, "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_clear_bit); } else { ATF_REQUIRE_MSG( found_clear_bit == i + ((i & 1) ? 0 : 1), "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_clear_bit); } } memset(bitstr, 0xAA, bitstr_size(nbits)); for (i = 0; i < nbits; i++) { bit_ffc_at(bitstr, i, nbits, &found_clear_bit); if (i == nbits - 1 && (nbits & 1) == 0) { ATF_REQUIRE_MSG(found_clear_bit == -1, "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_clear_bit); } else { ATF_REQUIRE_MSG(found_clear_bit == i + (i & 1), "bit_ffc_at_%d_%s: Failed on bit %d, Result %d", nbits, memloc, i, found_clear_bit); } } /* Pass a start value beyond the size of the bit string */ bit_ffc_at(bitstr, nbits, nbits, &found_clear_bit); ATF_REQUIRE_MSG(found_clear_bit == -1, "bit_ffc_at_%d_%s: Failed with high start value, Result %d", nbits, memloc, found_clear_bit); bit_ffc_at(bitstr, nbits + 3, nbits, &found_clear_bit); ATF_REQUIRE_MSG(found_clear_bit == -1, "bit_ffc_at_%d_%s: Failed with high start value of %d, Result %d", 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 */ { int i, j; int found_set_bit; int found_clear_bit; for (i = 0; i < nbits; i++) { for (j = i; j < nbits; j++) { memset(bitstr, 0xFF, bitstr_size(nbits)); bit_nclear(bitstr, i, j); bit_ffc(bitstr, nbits, &found_clear_bit); ATF_REQUIRE_MSG( found_clear_bit == i, "bit_nclear_%d_%d_%d%s: Failed with result %d", nbits, i, j, memloc, found_clear_bit); bit_ffs_at(bitstr, i, nbits, &found_set_bit); ATF_REQUIRE_MSG( (j + 1 < nbits) ? found_set_bit == j + 1 : -1, "bit_nset_%d_%d_%d%s: Failed with result %d", nbits, i, j, memloc, found_set_bit); } } } BITSTRING_TC_DEFINE(bit_nset) /* bitstr_t *bitstr, int nbits, const char *memloc */ { int i, j; int found_set_bit; int found_clear_bit; for (i = 0; i < nbits; i++) { for (j = i; j < nbits; j++) { memset(bitstr, 0, bitstr_size(nbits)); bit_nset(bitstr, i, j); bit_ffs(bitstr, nbits, &found_set_bit); ATF_REQUIRE_MSG( found_set_bit == i, "bit_nset_%d_%d_%d%s: Failed with result %d", nbits, i, j, memloc, found_set_bit); bit_ffc_at(bitstr, i, nbits, &found_clear_bit); ATF_REQUIRE_MSG( (j + 1 < nbits) ? found_clear_bit == j + 1 : -1, "bit_nset_%d_%d_%d%s: Failed with result %d", nbits, i, j, memloc, found_clear_bit); } } } 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) { 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); BITSTRING_TC_ADD(tp, bit_ffc); BITSTRING_TC_ADD(tp, bit_ffs_at); 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); + BITSTRING_TC_ADD(tp, bit_ffs_area_no_match); + BITSTRING_TC_ADD(tp, bit_ffc_area_no_match); return (atf_no_error()); } Index: stable/12 =================================================================== --- stable/12 (revision 356305) +++ stable/12 (revision 356306) Property changes on: stable/12 ___________________________________________________________________ Modified: svn:mergeinfo ## -0,0 +0,1 ## Merged /head:r354977,355032,355377,355400