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