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