1 /*- 2 * Copyright (c) 1989, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Paul Vixie. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 * 32 * Copyright (c) 2014 Spectra Logic Corporation 33 * All rights reserved. 34 * 35 * Redistribution and use in source and binary forms, with or without 36 * modification, are permitted provided that the following conditions 37 * are met: 38 * 1. Redistributions of source code must retain the above copyright 39 * notice, this list of conditions, and the following disclaimer, 40 * without modification. 41 * 2. Redistributions in binary form must reproduce at minimum a disclaimer 42 * substantially similar to the "NO WARRANTY" disclaimer below 43 * ("Disclaimer") and any redistribution must be conditioned upon 44 * including a substantially similar Disclaimer requirement for further 45 * binary redistribution. 46 * 47 * NO WARRANTY 48 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 49 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 50 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 51 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 52 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 53 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 54 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 55 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 56 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 57 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 58 * POSSIBILITY OF SUCH DAMAGES. 59 * 60 * $FreeBSD$ 61 */ 62 #ifndef _SYS_FREEBSD_BITSTRING_H_ 63 #define _SYS_FREEBSD_BITSTRING_H_ 64 65 #include <sys/types.h> 66 #include <sys/malloc.h> 67 68 /* 69 * Begin: Ad hoc definitions from FreeBSD sys/sys/types.h 70 */ 71 72 /* 73 * Population count algorithm using SWAR approach 74 * - "SIMD Within A Register". 75 */ 76 static __inline __uint16_t 77 __bitcount16(__uint16_t _x) 78 { 79 80 _x = (_x & 0x5555) + ((_x & 0xaaaa) >> 1); 81 _x = (_x & 0x3333) + ((_x & 0xcccc) >> 2); 82 _x = (_x + (_x >> 4)) & 0x0f0f; 83 _x = (_x + (_x >> 8)) & 0x00ff; 84 return (_x); 85 } 86 87 static __inline __uint32_t 88 __bitcount32(__uint32_t _x) 89 { 90 91 _x = (_x & 0x55555555) + ((_x & 0xaaaaaaaa) >> 1); 92 _x = (_x & 0x33333333) + ((_x & 0xcccccccc) >> 2); 93 _x = (_x + (_x >> 4)) & 0x0f0f0f0f; 94 _x = (_x + (_x >> 8)); 95 _x = (_x + (_x >> 16)) & 0x000000ff; 96 return (_x); 97 } 98 99 #ifdef __LP64__ 100 static __inline __uint64_t 101 __bitcount64(__uint64_t _x) 102 { 103 104 _x = (_x & 0x5555555555555555) + ((_x & 0xaaaaaaaaaaaaaaaa) >> 1); 105 _x = (_x & 0x3333333333333333) + ((_x & 0xcccccccccccccccc) >> 2); 106 _x = (_x + (_x >> 4)) & 0x0f0f0f0f0f0f0f0f; 107 _x = (_x + (_x >> 8)); 108 _x = (_x + (_x >> 16)); 109 _x = (_x + (_x >> 32)) & 0x000000ff; 110 return (_x); 111 } 112 113 #define __bitcountl(x) __bitcount64((unsigned long)(x)) 114 #else 115 static __inline __uint64_t 116 __bitcount64(__uint64_t _x) 117 { 118 119 return (__bitcount32(_x >> 32) + __bitcount32(_x)); 120 } 121 122 #define __bitcountl(x) __bitcount32((unsigned long)(x)) 123 #endif 124 #define __bitcount(x) __bitcount32((unsigned int)(x)) 125 /* 126 * End: Ad hoc definitions from FreeBSD sys/sys/types.h 127 */ 128 129 typedef unsigned long bitstr_t; 130 131 /*---------------------- Private Implementation Details ----------------------*/ 132 #define _BITSTR_MASK (~0UL) 133 #define _BITSTR_BITS (sizeof(bitstr_t) * 8) 134 135 /* round up x to the next multiple of y if y is a power of two */ 136 #define _bit_roundup2(x, y) \ 137 (((size_t)(x) + (y) - 1) & ~((size_t)(y) - 1)) 138 139 /* bitstr_t in bit string containing the bit. */ 140 static inline size_t 141 _bit_idx(size_t _bit) 142 { 143 return (_bit / _BITSTR_BITS); 144 } 145 146 /* bit number within bitstr_t at _bit_idx(_bit). */ 147 static inline size_t 148 _bit_offset(size_t _bit) 149 { 150 return (_bit % _BITSTR_BITS); 151 } 152 153 /* Mask for the bit within its long. */ 154 static inline bitstr_t 155 _bit_mask(size_t _bit) 156 { 157 return (1UL << _bit_offset(_bit)); 158 } 159 160 static inline bitstr_t 161 _bit_make_mask(size_t _start, size_t _stop) 162 { 163 return ((_BITSTR_MASK << _bit_offset(_start)) & 164 (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1))); 165 } 166 167 /*----------------------------- Public Interface -----------------------------*/ 168 /* Number of bytes allocated for a bit string of nbits bits */ 169 #define bitstr_size(_nbits) (_bit_roundup2((_nbits), _BITSTR_BITS) / 8) 170 171 /* Allocate a bit string initialized with no bits set. */ 172 #ifdef _KERNEL 173 static inline bitstr_t * 174 bit_alloc(size_t _nbits, struct malloc_type *type, int flags) 175 { 176 return ((bitstr_t *)kmalloc(bitstr_size(_nbits), type, flags | M_ZERO)); 177 } 178 #else 179 static inline bitstr_t * 180 bit_alloc(size_t _nbits) 181 { 182 return ((bitstr_t *)calloc(bitstr_size(_nbits), 1)); 183 } 184 #endif 185 186 /* Allocate a bit string on the stack */ 187 #define bit_decl(name, nbits) \ 188 ((name)[bitstr_size(nbits) / sizeof(bitstr_t)]) 189 190 /* Is bit N of bit string set? */ 191 static inline int 192 bit_test(const bitstr_t *_bitstr, size_t _bit) 193 { 194 return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0); 195 } 196 197 /* Set bit N of bit string. */ 198 static inline void 199 bit_set(bitstr_t *_bitstr, size_t _bit) 200 { 201 _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit); 202 } 203 204 /* clear bit N of bit string name */ 205 static inline void 206 bit_clear(bitstr_t *_bitstr, size_t _bit) 207 { 208 _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit); 209 } 210 211 /* Are bits in [start ... stop] in bit string all 0 or all 1? */ 212 static inline int 213 bit_ntest(const bitstr_t *_bitstr, size_t _start, size_t _stop, int _match) 214 { 215 const bitstr_t *_stopbitstr; 216 bitstr_t _mask; 217 218 _mask = (_match == 0) ? 0 : _BITSTR_MASK; 219 _stopbitstr = _bitstr + _bit_idx(_stop); 220 _bitstr += _bit_idx(_start); 221 222 if (_bitstr == _stopbitstr) 223 return (0 == ((*_bitstr ^ _mask) & 224 _bit_make_mask(_start, _stop))); 225 if (_bit_offset(_start) != 0 && 226 0 != ((*_bitstr++ ^ _mask) & 227 _bit_make_mask(_start, _BITSTR_BITS - 1))) 228 return (0); 229 if (_bit_offset(_stop) == _BITSTR_BITS - 1) 230 ++_stopbitstr; 231 while (_bitstr < _stopbitstr) { 232 if (*_bitstr++ != _mask) 233 return (0); 234 } 235 return (_bit_offset(_stop) == _BITSTR_BITS - 1 || 236 0 == ((*_stopbitstr ^ _mask) & _bit_make_mask(0, _stop))); 237 } 238 239 /* Set bits start ... stop inclusive in bit string. */ 240 static inline void 241 bit_nset(bitstr_t *_bitstr, size_t _start, size_t _stop) 242 { 243 bitstr_t *_stopbitstr; 244 245 _stopbitstr = _bitstr + _bit_idx(_stop); 246 _bitstr += _bit_idx(_start); 247 248 if (_bitstr == _stopbitstr) { 249 *_bitstr |= _bit_make_mask(_start, _stop); 250 } else { 251 if (_bit_offset(_start) != 0) 252 *_bitstr++ |= _bit_make_mask(_start, _BITSTR_BITS - 1); 253 if (_bit_offset(_stop) == _BITSTR_BITS - 1) 254 ++_stopbitstr; 255 while (_bitstr < _stopbitstr) 256 *_bitstr++ = _BITSTR_MASK; 257 if (_bit_offset(_stop) != _BITSTR_BITS - 1) 258 *_stopbitstr |= _bit_make_mask(0, _stop); 259 } 260 } 261 262 /* Clear bits start ... stop inclusive in bit string. */ 263 static inline void 264 bit_nclear(bitstr_t *_bitstr, size_t _start, size_t _stop) 265 { 266 bitstr_t *_stopbitstr; 267 268 _stopbitstr = _bitstr + _bit_idx(_stop); 269 _bitstr += _bit_idx(_start); 270 271 if (_bitstr == _stopbitstr) { 272 *_bitstr &= ~_bit_make_mask(_start, _stop); 273 } else { 274 if (_bit_offset(_start) != 0) 275 *_bitstr++ &= ~_bit_make_mask(_start, _BITSTR_BITS - 1); 276 if (_bit_offset(_stop) == _BITSTR_BITS - 1) 277 ++_stopbitstr; 278 while (_bitstr < _stopbitstr) 279 *_bitstr++ = 0; 280 if (_bit_offset(_stop) != _BITSTR_BITS - 1) 281 *_stopbitstr &= ~_bit_make_mask(0, _stop); 282 } 283 } 284 285 /* Find the first '_match'-bit in bit string at or after bit start. */ 286 static inline ssize_t 287 bit_ff_at_(bitstr_t *_bitstr, size_t _start, size_t _nbits, int _match) 288 { 289 bitstr_t *_curbitstr; 290 bitstr_t *_stopbitstr; 291 bitstr_t _mask; 292 bitstr_t _test; 293 ssize_t _value; 294 295 if (_start >= _nbits || _nbits <= 0) 296 return (-1); 297 298 _curbitstr = _bitstr + _bit_idx(_start); 299 _stopbitstr = _bitstr + _bit_idx(_nbits - 1); 300 _mask = _match ? 0 : _BITSTR_MASK; 301 302 _test = _mask ^ *_curbitstr; 303 if (_bit_offset(_start) != 0) 304 _test &= _bit_make_mask(_start, _BITSTR_BITS - 1); 305 while (_test == 0 && _curbitstr < _stopbitstr) 306 _test = _mask ^ *(++_curbitstr); 307 308 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + ffsl(_test) - 1; 309 if (_test == 0 || 310 (_bit_offset(_nbits) != 0 && (size_t)_value >= _nbits)) 311 _value = -1; 312 return (_value); 313 } 314 #define bit_ff_at(_bitstr, _start, _nbits, _match, _resultp) \ 315 *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), (_match)) 316 317 /* Find the first bit set in bit string at or after bit start. */ 318 #define bit_ffs_at(_bitstr, _start, _nbits, _resultp) \ 319 *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), 1) 320 321 /* Find the first bit clear in bit string at or after bit start. */ 322 #define bit_ffc_at(_bitstr, _start, _nbits, _resultp) \ 323 *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), 0) 324 325 /* Find the first bit set in bit string. */ 326 #define bit_ffs(_bitstr, _nbits, _resultp) \ 327 *(_resultp) = bit_ff_at_((_bitstr), 0, (_nbits), 1) 328 329 /* Find the first bit clear in bit string. */ 330 #define bit_ffc(_bitstr, _nbits, _resultp) \ 331 *(_resultp) = bit_ff_at_((_bitstr), 0, (_nbits), 0) 332 333 /* Find contiguous sequence of at least size '_match'-bits at or after start */ 334 static inline ssize_t 335 bit_ff_area_at_(bitstr_t *_bitstr, size_t _start, size_t _nbits, size_t _size, 336 int _match) 337 { 338 bitstr_t *_curbitstr, _mask, _test; 339 size_t _last, _shft, _maxshft; 340 ssize_t _value; 341 342 if (_start + _size > _nbits || _nbits <= 0) 343 return (-1); 344 345 _mask = _match ? _BITSTR_MASK : 0; 346 _maxshft = _bit_idx(_size - 1) == 0 ? _size : (int)_BITSTR_BITS; 347 _value = _start; 348 _curbitstr = _bitstr + _bit_idx(_start); 349 _test = ~(_BITSTR_MASK << _bit_offset(_start)); 350 for (_last = _size - 1, _test |= _mask ^ *_curbitstr; 351 !(_bit_idx(_last) == 0 && 352 (_test & _bit_make_mask(0, _last)) == 0); 353 _last -= _BITSTR_BITS, _test = _mask ^ *++_curbitstr) { 354 if (_test == 0) 355 continue; 356 /* Shrink-left every 0-area in _test by maxshft-1 bits. */ 357 for (_shft = _maxshft; _shft > 1 && (_test & (_test + 1)) != 0; 358 _shft = (_shft + 1) / 2) 359 _test |= _test >> _shft / 2; 360 /* Find the start of the first 0-area in _test. */ 361 _last = ffsl(~(_test >> 1)); 362 _value = (_curbitstr - _bitstr) * _BITSTR_BITS + _last; 363 /* If there's insufficient space left, give up. */ 364 if (_value + _size > _nbits) { 365 _value = -1; 366 break; 367 } 368 _last += _size - 1; 369 /* If a solution is contained in _test, success! */ 370 if (_bit_idx(_last) == 0) 371 break; 372 /* A solution here needs bits from the next word. */ 373 } 374 return (_value); 375 } 376 #define bit_ff_area_at(_bitstr, _start, _nbits, _size, _match, _resultp) \ 377 *(_resultp) = bit_ff_area_at_(_bitstr, _start, _nbits, _size, _match); 378 379 /* Find contiguous sequence of at least size set bits at or after start */ 380 #define bit_ffs_area_at(_bitstr, _start, _nbits, _size, _resultp) \ 381 *(_resultp) = bit_ff_area_at_((_bitstr), (_start), (_nbits), (_size), 1) 382 383 /* Find contiguous sequence of at least size cleared bits at or after start */ 384 #define bit_ffc_area_at(_bitstr, _start, _nbits, _size, _resultp) \ 385 *(_resultp) = bit_ff_area_at_((_bitstr), (_start), (_nbits), (_size), 0) 386 387 /* Find contiguous sequence of at least size set bits in bit string */ 388 #define bit_ffs_area(_bitstr, _nbits, _size, _resultp) \ 389 *(_resultp) = bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 1) 390 391 /* Find contiguous sequence of at least size cleared bits in bit string */ 392 #define bit_ffc_area(_bitstr, _nbits, _size, _resultp) \ 393 *(_resultp) = bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 0) 394 395 /* Count the number of bits set in a bitstr of size _nbits at or after _start */ 396 static inline ssize_t 397 bit_count_(bitstr_t *_bitstr, size_t _start, size_t _nbits) 398 { 399 bitstr_t *_curbitstr, mask; 400 size_t curbitstr_len; 401 ssize_t _value = 0; 402 403 if (_start >= _nbits) 404 return (0); 405 406 _curbitstr = _bitstr + _bit_idx(_start); 407 _nbits -= _BITSTR_BITS * _bit_idx(_start); 408 _start -= _BITSTR_BITS * _bit_idx(_start); 409 410 if (_start > 0) { 411 curbitstr_len = (int)_BITSTR_BITS < _nbits ? 412 (int)_BITSTR_BITS : _nbits; 413 mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1)); 414 _value += __bitcountl(*_curbitstr & mask); 415 _curbitstr++; 416 if (_nbits < _BITSTR_BITS) 417 return (_value); 418 _nbits -= _BITSTR_BITS; 419 } 420 while (_nbits >= (int)_BITSTR_BITS) { 421 _value += __bitcountl(*_curbitstr); 422 _curbitstr++; 423 _nbits -= _BITSTR_BITS; 424 } 425 if (_nbits > 0) { 426 mask = _bit_make_mask(0, _bit_offset(_nbits - 1)); 427 _value += __bitcountl(*_curbitstr & mask); 428 } 429 430 return (_value); 431 } 432 #define bit_count(_bitstr, _start, _nbits, _resultp) \ 433 *(_resultp) = bit_count_((_bitstr), (_start), (_nbits)) 434 435 /* Traverse all set bits, assigning each location in turn to iter */ 436 #define bit_foreach_at(_bitstr, _start, _nbits, _iter) \ 437 for ((_iter) = bit_ff_at_((_bitstr), (_start), (_nbits), 1); \ 438 (_iter) != -1; \ 439 (_iter) = bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 1)) 440 #define bit_foreach(_bitstr, _nbits, _iter) \ 441 bit_foreach_at(_bitstr, /*start*/0, _nbits, _iter) 442 443 /* Traverse all unset bits, assigning each location in turn to iter */ 444 #define bit_foreach_unset_at(_bitstr, _start, _nbits, _iter) \ 445 for ((_iter) = bit_ff_at_((_bitstr), (_start), (_nbits), 0); \ 446 (_iter) != -1; \ 447 (_iter) = bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 0)) 448 #define bit_foreach_unset(_bitstr, _nbits, _iter) \ 449 bit_foreach_unset_at(_bitstr, /*start*/0, _nbits, _iter) 450 451 #endif /* _SYS_FREEBSD_BITSTRING_H_ */ 452