2 * SPDX-License-Identifier: BSD-3-Clause
4 * Copyright (c) 1989, 1993
5 * The Regents of the University of California. All rights reserved.
7 * This code is derived from software contributed to Berkeley by
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * Copyright (c) 2014 Spectra Logic Corporation
35 * All rights reserved.
37 * Redistribution and use in source and binary forms, with or without
38 * modification, are permitted provided that the following conditions
40 * 1. Redistributions of source code must retain the above copyright
41 * notice, this list of conditions, and the following disclaimer,
42 * without modification.
43 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
44 * substantially similar to the "NO WARRANTY" disclaimer below
45 * ("Disclaimer") and any redistribution must be conditioned upon
46 * including a substantially similar Disclaimer requirement for further
47 * binary redistribution.
50 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
51 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
52 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
53 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
54 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
55 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
56 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
57 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
58 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
59 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
60 * POSSIBILITY OF SUCH DAMAGES.
64 #ifndef _SYS_BITSTRING_H_
65 #define _SYS_BITSTRING_H_
68 #include <sys/libkern.h>
69 #include <sys/malloc.h>
72 #include <sys/types.h>
74 typedef unsigned long bitstr_t;
76 /*---------------------- Private Implementation Details ----------------------*/
77 #define _BITSTR_MASK (~0UL)
78 #define _BITSTR_BITS (sizeof(bitstr_t) * 8)
81 #define _bit_roundup2 roundup2
83 #define _bit_roundup2(x, y) (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */
86 /* bitstr_t in bit string containing the bit. */
90 return (_bit / _BITSTR_BITS);
93 /* bit number within bitstr_t at _bit_idx(_bit). */
97 return (_bit % _BITSTR_BITS);
100 /* Mask for the bit within its long. */
101 static inline bitstr_t
104 return (1UL << _bit_offset(_bit));
107 static inline bitstr_t
108 _bit_make_mask(int _start, int _stop)
110 return ((_BITSTR_MASK << _bit_offset(_start)) &
111 (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1)));
114 /*----------------------------- Public Interface -----------------------------*/
115 /* Number of bytes allocated for a bit string of nbits bits */
116 #define bitstr_size(_nbits) (_bit_roundup2(_nbits, _BITSTR_BITS) / 8)
118 /* Allocate a bit string initialized with no bits set. */
120 static inline bitstr_t *
121 bit_alloc(int _nbits, struct malloc_type *type, int flags)
123 return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO));
126 static inline bitstr_t *
127 bit_alloc(int _nbits)
129 return ((bitstr_t *)calloc(bitstr_size(_nbits), 1));
133 /* Allocate a bit string on the stack */
134 #define bit_decl(name, nbits) \
135 ((name)[bitstr_size(nbits) / sizeof(bitstr_t)])
137 /* Is bit N of bit string set? */
139 bit_test(const bitstr_t *_bitstr, int _bit)
141 return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0);
144 /* Set bit N of bit string. */
146 bit_set(bitstr_t *_bitstr, int _bit)
148 _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit);
151 /* clear bit N of bit string name */
153 bit_clear(bitstr_t *_bitstr, int _bit)
155 _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
158 /* Set bits start ... stop inclusive in bit string. */
160 bit_nset(bitstr_t *_bitstr, int _start, int _stop)
162 bitstr_t *_stopbitstr;
164 _stopbitstr = _bitstr + _bit_idx(_stop);
165 _bitstr += _bit_idx(_start);
167 if (_bitstr == _stopbitstr) {
168 *_bitstr |= _bit_make_mask(_start, _stop);
170 *_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1);
171 while (++_bitstr < _stopbitstr)
172 *_bitstr = _BITSTR_MASK;
173 *_stopbitstr |= _bit_make_mask(0, _stop);
177 /* Clear bits start ... stop inclusive in bit string. */
179 bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
181 bitstr_t *_stopbitstr;
183 _stopbitstr = _bitstr + _bit_idx(_stop);
184 _bitstr += _bit_idx(_start);
186 if (_bitstr == _stopbitstr) {
187 *_bitstr &= ~_bit_make_mask(_start, _stop);
189 *_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
190 while (++_bitstr < _stopbitstr)
192 *_stopbitstr &= ~_bit_make_mask(0, _stop);
196 /* Find the first bit set in bit string at or after bit start. */
198 bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
200 bitstr_t *_curbitstr;
201 bitstr_t *_stopbitstr;
205 if (_start >= _nbits) {
211 _curbitstr = _bitstr + _bit_idx(_start);
212 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
215 if (_bit_offset(_start) != 0)
216 _test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
217 while (_test == 0 && _curbitstr < _stopbitstr)
218 _test = *(++_curbitstr);
220 _offset = ffsl(_test);
221 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
222 if (_offset == 0 || _value >= _nbits)
230 /* Find the first bit clear in bit string at or after bit start. */
232 bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
234 bitstr_t *_curbitstr;
235 bitstr_t *_stopbitstr;
239 if (_start >= _nbits) {
245 _curbitstr = _bitstr + _bit_idx(_start);
246 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
249 if (_bit_offset(_start) != 0)
250 _test |= _bit_make_mask(0, _start - 1);
251 while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr)
252 _test = *(++_curbitstr);
254 _offset = ffsl(~_test);
255 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
256 if (_offset == 0 || _value >= _nbits)
264 /* Find the first bit set in bit string. */
266 bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result)
268 bit_ffs_at(_bitstr, /*start*/0, _nbits, _result);
271 /* Find the first bit clear in bit string. */
273 bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result)
275 bit_ffc_at(_bitstr, /*start*/0, _nbits, _result);
278 /* Find contiguous sequence of at least size set bits at or after start */
280 bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
283 bitstr_t *_curbitstr;
285 int _value, _offset, _logsize, _b;
287 if (_start + _size > _nbits || _nbits <= 0) {
292 _logsize = fls(_size - 1);
294 _curbitstr = _bitstr + _bit_idx(_start);
295 _test = ~*_curbitstr;
296 if (_bit_offset(_start) != 0)
297 _test |= _bit_make_mask(0, _start - 1);
298 for (_offset = 0;; _offset -= _BITSTR_BITS, _test = ~*++_curbitstr) {
300 /* If leading 0s in _test can finish 0-area, stop. */
301 if (_offset + _size < (int)_BITSTR_BITS &&
302 (_test & _bit_make_mask(0, _offset + _size)) == 0)
304 /* Shrink-left every 0-area in _test by size-1 bits. */
306 while ((_test & (_test + 1)) != 0 && _b-- > 0)
307 _test |= _test >> (((_size - 1) >> _b) + 1) / 2;
308 /* Find the start of the first 0-area in _test. */
309 _offset = (~_test == 0) ? (int)_BITSTR_BITS :
311 _value = (_curbitstr - _bitstr) * _BITSTR_BITS +
313 /* If there's insufficient space left, give up. */
314 if (_value + _size > _nbits) {
319 if (_offset + _size <= (int)_BITSTR_BITS)
325 /* Find contiguous sequence of at least size cleared bits at or after start */
327 bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
330 bitstr_t *_curbitstr;
332 int _value, _offset, _logsize, _b;
334 if (_start + _size > _nbits || _nbits <= 0) {
339 _logsize = fls(_size - 1);
341 _curbitstr = _bitstr + _bit_idx(_start);
343 if (_bit_offset(_start) != 0)
344 _test |= _bit_make_mask(0, _start - 1);
345 for (_offset = 0;; _offset -= _BITSTR_BITS, _test = *++_curbitstr) {
347 /* If leading 0s in _test can finish 0-area, stop. */
348 if (_offset + _size < (int)_BITSTR_BITS &&
349 (_test & _bit_make_mask(0, _offset + _size)) == 0)
351 /* Shrink-left every 0-area in _test by size-1 bits. */
353 while ((_test & (_test + 1)) != 0 && _b-- > 0)
354 _test |= _test >> (((_size - 1) >> _b) + 1) / 2;
355 /* Find the start of the first 0-area in _test. */
356 _offset = (~_test == 0) ? (int)_BITSTR_BITS :
358 _value = (_curbitstr - _bitstr) * _BITSTR_BITS +
360 /* If there's insufficient space left, give up. */
361 if (_value + _size > _nbits) {
366 if (_offset + _size <= (int)_BITSTR_BITS)
372 /* Find contiguous sequence of at least size set bits in bit string */
374 bit_ffs_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
376 bit_ffs_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
379 /* Find contiguous sequence of at least size cleared bits in bit string */
381 bit_ffc_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
383 bit_ffc_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
386 /* Count the number of bits set in a bitstr of size _nbits at or after _start */
388 bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
390 bitstr_t *_curbitstr, mask;
391 int _value = 0, curbitstr_len;
393 if (_start >= _nbits)
396 _curbitstr = _bitstr + _bit_idx(_start);
397 _nbits -= _BITSTR_BITS * _bit_idx(_start);
398 _start -= _BITSTR_BITS * _bit_idx(_start);
401 curbitstr_len = (int)_BITSTR_BITS < _nbits ?
402 (int)_BITSTR_BITS : _nbits;
403 mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1));
404 _value += __bitcountl(*_curbitstr & mask);
406 _nbits -= _BITSTR_BITS;
408 while (_nbits >= (int)_BITSTR_BITS) {
409 _value += __bitcountl(*_curbitstr);
411 _nbits -= _BITSTR_BITS;
414 mask = _bit_make_mask(0, _bit_offset(_nbits - 1));
415 _value += __bitcountl(*_curbitstr & mask);
422 #endif /* _SYS_BITSTRING_H_ */