1/*- 2 * SPDX-License-Identifier: BSD-3-Clause 3 * 4 * Copyright (c) 1989, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * This code is derived from software contributed to Berkeley by 8 * Paul Vixie. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 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. 21 * 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 32 * SUCH DAMAGE. 33 * 34 * Copyright (c) 2014 Spectra Logic Corporation 35 * All rights reserved. 36 * 37 * Redistribution and use in source and binary forms, with or without 38 * modification, are permitted provided that the following conditions 39 * are met: 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. 48 * 49 * NO WARRANTY 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. 61 */ 62#ifndef _SYS_BITSTRING_H_ 63#define _SYS_BITSTRING_H_ 64 65#ifdef _KERNEL 66#include <sys/libkern.h> 67#include <sys/malloc.h> 68#endif 69 70#include <sys/types.h> 71 72typedef unsigned long bitstr_t; 73 74/*---------------------- Private Implementation Details ----------------------*/ 75#define _BITSTR_MASK (~0UL) 76#define _BITSTR_BITS (sizeof(bitstr_t) * 8) 77 78/* round up x to the next multiple of y if y is a power of two */ 79#define _bit_roundup2(x, y) \ 80 (((size_t)(x) + (y) - 1) & ~((size_t)(y) - 1)) 81 82/* bitstr_t in bit string containing the bit. */ 83static inline size_t 84_bit_idx(size_t _bit) 85{ 86 return (_bit / _BITSTR_BITS); 87} 88 89/* bit number within bitstr_t at _bit_idx(_bit). */ 90static inline size_t 91_bit_offset(size_t _bit) 92{ 93 return (_bit % _BITSTR_BITS); 94} 95 96/* Mask for the bit within its long. */ 97static inline bitstr_t 98_bit_mask(size_t _bit) 99{ 100 return (1UL << _bit_offset(_bit)); 101} 102 103static inline bitstr_t 104_bit_make_mask(size_t _start, size_t _stop) 105{ 106 return ((_BITSTR_MASK << _bit_offset(_start)) & 107 (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1))); 108} 109 110/*----------------------------- Public Interface -----------------------------*/ 111/* Number of bytes allocated for a bit string of nbits bits */ 112#define bitstr_size(_nbits) (_bit_roundup2((_nbits), _BITSTR_BITS) / 8) 113 114/* Allocate a bit string initialized with no bits set. */ 115#ifdef _KERNEL 116static inline bitstr_t * 117bit_alloc(size_t _nbits, struct malloc_type *type, int flags) 118{ 119 return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO)); 120} 121#else 122static inline bitstr_t * 123bit_alloc(size_t _nbits) 124{ 125 return ((bitstr_t *)calloc(bitstr_size(_nbits), 1)); 126} 127#endif 128 129/* Allocate a bit string on the stack */ 130#define bit_decl(name, nbits) \ 131 ((name)[bitstr_size(nbits) / sizeof(bitstr_t)]) 132 133/* Is bit N of bit string set? */ 134static inline int 135bit_test(const bitstr_t *_bitstr, size_t _bit) 136{ 137 return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0); 138} 139 140/* Set bit N of bit string. */ 141static inline void 142bit_set(bitstr_t *_bitstr, size_t _bit) 143{ 144 _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit); 145} 146 147/* clear bit N of bit string name */ 148static inline void 149bit_clear(bitstr_t *_bitstr, size_t _bit) 150{ 151 _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit); 152} 153 154/* Are bits in [start ... stop] in bit string all 0 or all 1? */ 155static inline int 156bit_ntest(const bitstr_t *_bitstr, size_t _start, size_t _stop, int _match) 157{ 158 const bitstr_t *_stopbitstr; 159 bitstr_t _mask; 160 161 _mask = (_match == 0) ? 0 : _BITSTR_MASK; 162 _stopbitstr = _bitstr + _bit_idx(_stop); 163 _bitstr += _bit_idx(_start); 164 165 if (_bitstr == _stopbitstr) 166 return (0 == ((*_bitstr ^ _mask) & 167 _bit_make_mask(_start, _stop))); 168 if (_bit_offset(_start) != 0 && 169 0 != ((*_bitstr++ ^ _mask) & 170 _bit_make_mask(_start, _BITSTR_BITS - 1))) 171 return (0); 172 if (_bit_offset(_stop) == _BITSTR_BITS - 1) 173 ++_stopbitstr; 174 while (_bitstr < _stopbitstr) { 175 if (*_bitstr++ != _mask) 176 return (0); 177 } 178 return (_bit_offset(_stop) == _BITSTR_BITS - 1 || 179 0 == ((*_stopbitstr ^ _mask) & _bit_make_mask(0, _stop))); 180} 181 182/* Set bits start ... stop inclusive in bit string. */ 183static inline void 184bit_nset(bitstr_t *_bitstr, size_t _start, size_t _stop) 185{ 186 bitstr_t *_stopbitstr; 187 188 _stopbitstr = _bitstr + _bit_idx(_stop); 189 _bitstr += _bit_idx(_start); 190 191 if (_bitstr == _stopbitstr) { 192 *_bitstr |= _bit_make_mask(_start, _stop); 193 } else { 194 if (_bit_offset(_start) != 0) 195 *_bitstr++ |= _bit_make_mask(_start, _BITSTR_BITS - 1); 196 if (_bit_offset(_stop) == _BITSTR_BITS - 1) 197 ++_stopbitstr; 198 while (_bitstr < _stopbitstr) 199 *_bitstr++ = _BITSTR_MASK; 200 if (_bit_offset(_stop) != _BITSTR_BITS - 1) 201 *_stopbitstr |= _bit_make_mask(0, _stop); 202 } 203} 204 205/* Clear bits start ... stop inclusive in bit string. */ 206static inline void 207bit_nclear(bitstr_t *_bitstr, size_t _start, size_t _stop) 208{ 209 bitstr_t *_stopbitstr; 210 211 _stopbitstr = _bitstr + _bit_idx(_stop); 212 _bitstr += _bit_idx(_start); 213 214 if (_bitstr == _stopbitstr) { 215 *_bitstr &= ~_bit_make_mask(_start, _stop); 216 } else { 217 if (_bit_offset(_start) != 0) 218 *_bitstr++ &= ~_bit_make_mask(_start, _BITSTR_BITS - 1); 219 if (_bit_offset(_stop) == _BITSTR_BITS - 1) 220 ++_stopbitstr; 221 while (_bitstr < _stopbitstr) 222 *_bitstr++ = 0; 223 if (_bit_offset(_stop) != _BITSTR_BITS - 1) 224 *_stopbitstr &= ~_bit_make_mask(0, _stop); 225 } 226} 227 228/* Find the first '_match'-bit in bit string at or after bit start. */ 229static inline ssize_t 230bit_ff_at_(bitstr_t *_bitstr, size_t _start, size_t _nbits, int _match) 231{ 232 bitstr_t *_curbitstr; 233 bitstr_t *_stopbitstr; 234 bitstr_t _mask; 235 bitstr_t _test; 236 ssize_t _value; 237 238 if (_start >= _nbits || _nbits <= 0) 239 return (-1); 240 241 _curbitstr = _bitstr + _bit_idx(_start); 242 _stopbitstr = _bitstr + _bit_idx(_nbits - 1); 243 _mask = _match ? 0 : _BITSTR_MASK; 244 245 _test = _mask ^ *_curbitstr; 246 if (_bit_offset(_start) != 0) 247 _test &= _bit_make_mask(_start, _BITSTR_BITS - 1); 248 while (_test == 0 && _curbitstr < _stopbitstr) 249 _test = _mask ^ *(++_curbitstr); 250 251 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + ffsl(_test) - 1; 252 if (_test == 0 || 253 (_bit_offset(_nbits) != 0 && (size_t)_value >= _nbits)) 254 _value = -1; 255 return (_value); 256} 257#define bit_ff_at(_bitstr, _start, _nbits, _match, _resultp) \ 258 *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), (_match)) 259 260/* Find the first bit set in bit string at or after bit start. */ 261#define bit_ffs_at(_bitstr, _start, _nbits, _resultp) \ 262 *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), 1) 263 264/* Find the first bit clear in bit string at or after bit start. */ 265#define bit_ffc_at(_bitstr, _start, _nbits, _resultp) \ 266 *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), 0) 267 268/* Find the first bit set in bit string. */ 269#define bit_ffs(_bitstr, _nbits, _resultp) \ 270 *(_resultp) = bit_ff_at_((_bitstr), 0, (_nbits), 1) 271 272/* Find the first bit clear in bit string. */ 273#define bit_ffc(_bitstr, _nbits, _resultp) \ 274 *(_resultp) = bit_ff_at_((_bitstr), 0, (_nbits), 0) 275 276/* Find contiguous sequence of at least size '_match'-bits at or after start */ 277static inline ssize_t 278bit_ff_area_at_(bitstr_t *_bitstr, size_t _start, size_t _nbits, size_t _size, 279 int _match) 280{ 281 bitstr_t *_curbitstr, _mask, _test; 282 size_t _last, _shft, _maxshft; 283 ssize_t _value; 284 285 if (_start + _size > _nbits || _nbits <= 0) 286 return (-1); 287 288 _mask = _match ? _BITSTR_MASK : 0; 289 _maxshft = _bit_idx(_size - 1) == 0 ? _size : (int)_BITSTR_BITS; 290 _value = _start; 291 _curbitstr = _bitstr + _bit_idx(_start); 292 _test = ~(_BITSTR_MASK << _bit_offset(_start)); 293 for (_last = _size - 1, _test |= _mask ^ *_curbitstr; 294 !(_bit_idx(_last) == 0 && 295 (_test & _bit_make_mask(0, _last)) == 0); 296 _last -= _BITSTR_BITS, _test = _mask ^ *++_curbitstr) { 297 if (_test == 0) 298 continue; 299 /* Shrink-left every 0-area in _test by maxshft-1 bits. */ 300 for (_shft = _maxshft; _shft > 1 && (_test & (_test + 1)) != 0; 301 _shft = (_shft + 1) / 2) 302 _test |= _test >> _shft / 2; 303 /* Find the start of the first 0-area in _test. */ 304 _last = ffsl(~(_test >> 1)); 305 _value = (_curbitstr - _bitstr) * _BITSTR_BITS + _last; 306 /* If there's insufficient space left, give up. */ 307 if (_value + _size > _nbits) { 308 _value = -1; 309 break; 310 } 311 _last += _size - 1; 312 /* If a solution is contained in _test, success! */ 313 if (_bit_idx(_last) == 0) 314 break; 315 /* A solution here needs bits from the next word. */ 316 } 317 return (_value); 318} 319#define bit_ff_area_at(_bitstr, _start, _nbits, _size, _match, _resultp) \ 320 *(_resultp) = bit_ff_area_at_(_bitstr, _start, _nbits, _size, _match); 321 322/* Find contiguous sequence of at least size set bits at or after start */ 323#define bit_ffs_area_at(_bitstr, _start, _nbits, _size, _resultp) \ 324 *(_resultp) = bit_ff_area_at_((_bitstr), (_start), (_nbits), (_size), 1) 325 326/* Find contiguous sequence of at least size cleared bits at or after start */ 327#define bit_ffc_area_at(_bitstr, _start, _nbits, _size, _resultp) \ 328 *(_resultp) = bit_ff_area_at_((_bitstr), (_start), (_nbits), (_size), 0) 329 330/* Find contiguous sequence of at least size set bits in bit string */ 331#define bit_ffs_area(_bitstr, _nbits, _size, _resultp) \ 332 *(_resultp) = bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 1) 333 334/* Find contiguous sequence of at least size cleared bits in bit string */ 335#define bit_ffc_area(_bitstr, _nbits, _size, _resultp) \ 336 *(_resultp) = bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 0) 337 338/* Count the number of bits set in a bitstr of size _nbits at or after _start */ 339static inline ssize_t 340bit_count_(bitstr_t *_bitstr, size_t _start, size_t _nbits) 341{ 342 bitstr_t *_curbitstr, mask; 343 size_t curbitstr_len; 344 ssize_t _value = 0; 345 346 if (_start >= _nbits) 347 return (0); 348 349 _curbitstr = _bitstr + _bit_idx(_start); 350 _nbits -= _BITSTR_BITS * _bit_idx(_start); 351 _start -= _BITSTR_BITS * _bit_idx(_start); 352 353 if (_start > 0) { 354 curbitstr_len = (int)_BITSTR_BITS < _nbits ? 355 (int)_BITSTR_BITS : _nbits; 356 mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1)); 357 _value += __bitcountl(*_curbitstr & mask); 358 _curbitstr++; 359 if (_nbits < _BITSTR_BITS) 360 return (_value); 361 _nbits -= _BITSTR_BITS; 362 } 363 while (_nbits >= (int)_BITSTR_BITS) { 364 _value += __bitcountl(*_curbitstr); 365 _curbitstr++; 366 _nbits -= _BITSTR_BITS; 367 } 368 if (_nbits > 0) { 369 mask = _bit_make_mask(0, _bit_offset(_nbits - 1)); 370 _value += __bitcountl(*_curbitstr & mask); 371 } 372 373 return (_value); 374} 375#define bit_count(_bitstr, _start, _nbits, _resultp) \ 376 *(_resultp) = bit_count_((_bitstr), (_start), (_nbits)) 377 378/* Traverse all set bits, assigning each location in turn to iter */ 379#define bit_foreach_at(_bitstr, _start, _nbits, _iter) \ 380 for ((_iter) = bit_ff_at_((_bitstr), (_start), (_nbits), 1); \ 381 (_iter) != -1; \ 382 (_iter) = bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 1)) 383#define bit_foreach(_bitstr, _nbits, _iter) \ 384 bit_foreach_at(_bitstr, /*start*/0, _nbits, _iter) 385 386/* Traverse all unset bits, assigning each location in turn to iter */ 387#define bit_foreach_unset_at(_bitstr, _start, _nbits, _iter) \ 388 for ((_iter) = bit_ff_at_((_bitstr), (_start), (_nbits), 0); \ 389 (_iter) != -1; \ 390 (_iter) = bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 0)) 391#define bit_foreach_unset(_bitstr, _nbits, _iter) \ 392 bit_foreach_unset_at(_bitstr, /*start*/0, _nbits, _iter) 393 394#endif /* _SYS_BITSTRING_H_ */ 395