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 74typedef 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. */ 87static 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). */ 94static inline int 95_bit_offset(int _bit) 96{ 97 return (_bit % _BITSTR_BITS); 98} 99 100/* Mask for the bit within its long. */ 101static inline bitstr_t 102_bit_mask(int _bit) 103{ 104 return (1UL << _bit_offset(_bit)); 105} 106 107static 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 120static inline bitstr_t * 121bit_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 126static inline bitstr_t * 127bit_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? */ 138static inline int 139bit_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. */ 145static inline void 146bit_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 */ 152static inline void 153bit_clear(bitstr_t *_bitstr, int _bit) 154{ 155 _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit); 156} 157 158/* Set bits start ... stop inclusive in bit string. */ 159static inline void 160bit_nset(bitstr_t *_bitstr, int _start, int _stop) 161{ 162 bitstr_t *_stopbitstr; 163 164 _stopbitstr = _bitstr + _bit_idx(_stop); 165 _bitstr += _bit_idx(_start); 166 167 if (_bitstr == _stopbitstr) { 168 *_bitstr |= _bit_make_mask(_start, _stop); 169 } else { 170 *_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1); 171 while (++_bitstr < _stopbitstr) 172 *_bitstr = _BITSTR_MASK; 173 *_stopbitstr |= _bit_make_mask(0, _stop); 174 } 175} 176 177/* Clear bits start ... stop inclusive in bit string. */ 178static inline void 179bit_nclear(bitstr_t *_bitstr, int _start, int _stop) 180{ 181 bitstr_t *_stopbitstr; 182 183 _stopbitstr = _bitstr + _bit_idx(_stop); 184 _bitstr += _bit_idx(_start); 185 186 if (_bitstr == _stopbitstr) { 187 *_bitstr &= ~_bit_make_mask(_start, _stop); 188 } else { 189 *_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1); 190 while (++_bitstr < _stopbitstr) 191 *_bitstr = 0; 192 *_stopbitstr &= ~_bit_make_mask(0, _stop); 193 } 194} 195 196/* Find the first bit set in bit string at or after bit start. */ 197static inline void 198bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result) 199{ 200 bitstr_t *_curbitstr; 201 bitstr_t *_stopbitstr; 202 bitstr_t _test; 203 int _value, _offset; 204 205 if (_start >= _nbits) { 206 *_result = -1; 207 return; 208 } 209 210 if (_nbits > 0) { 211 _curbitstr = _bitstr + _bit_idx(_start); 212 _stopbitstr = _bitstr + _bit_idx(_nbits - 1); 213 214 _test = *_curbitstr; 215 if (_bit_offset(_start) != 0) 216 _test &= _bit_make_mask(_start, _BITSTR_BITS - 1); 217 while (_test == 0 && _curbitstr < _stopbitstr) 218 _test = *(++_curbitstr); 219 220 _offset = ffsl(_test); 221 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1; 222 if (_offset == 0 || _value >= _nbits) 223 _value = -1; 224 } else { 225 _value = -1; 226 } 227 *_result = _value; 228} 229 230/* Find the first bit clear in bit string at or after bit start. */ 231static inline void 232bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result) 233{ 234 bitstr_t *_curbitstr; 235 bitstr_t *_stopbitstr; 236 bitstr_t _test; 237 int _value, _offset; 238 239 if (_start >= _nbits) { 240 *_result = -1; 241 return; 242 } 243 244 if (_nbits > 0) { 245 _curbitstr = _bitstr + _bit_idx(_start); 246 _stopbitstr = _bitstr + _bit_idx(_nbits - 1); 247 248 _test = *_curbitstr; 249 if (_bit_offset(_start) != 0) 250 _test |= _bit_make_mask(0, _start - 1); 251 while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr) 252 _test = *(++_curbitstr); 253 254 _offset = ffsl(~_test); 255 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1; 256 if (_offset == 0 || _value >= _nbits) 257 _value = -1; 258 } else { 259 _value = -1; 260 } 261 *_result = _value; 262} 263 264/* Find the first bit set in bit string. */ 265static inline void 266bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result) 267{ 268 bit_ffs_at(_bitstr, /*start*/0, _nbits, _result); 269} 270 271/* Find the first bit clear in bit string. */ 272static inline void 273bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result) 274{ 275 bit_ffc_at(_bitstr, /*start*/0, _nbits, _result); 276} 277 278/* Find contiguous sequence of at least size set bits at or after start */ 279static inline void 280bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, 281 int *_result) 282{ 283 bitstr_t *_curbitstr; 284 bitstr_t _test; 285 int _value, _offset, _logsize, _b; 286 287 if (_start + _size > _nbits || _nbits <= 0) { 288 *_result = -1; 289 return; 290 } 291 292 _logsize = fls(_size - 1); 293 _value = _start; 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) { 299 if (_test != 0) { 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) 303 break; 304 /* Shrink-left every 0-area in _test by size-1 bits. */ 305 _b = _logsize; 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 : 310 ffsl(~_test) - 1; 311 _value = (_curbitstr - _bitstr) * _BITSTR_BITS + 312 _offset; 313 /* If there's insufficient space left, give up. */ 314 if (_value + _size > _nbits) { 315 _value = -1; 316 break; 317 } 318 } 319 if (_offset + _size <= (int)_BITSTR_BITS) 320 break; 321 } 322 *_result = _value; 323} 324 325/* Find contiguous sequence of at least size cleared bits at or after start */ 326static inline void 327bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size, 328 int *_result) 329{ 330 bitstr_t *_curbitstr; 331 bitstr_t _test; 332 int _value, _offset, _logsize, _b; 333 334 if (_start + _size > _nbits || _nbits <= 0) { 335 *_result = -1; 336 return; 337 } 338 339 _logsize = fls(_size - 1); 340 _value = _start; 341 _curbitstr = _bitstr + _bit_idx(_start); 342 _test = *_curbitstr; 343 if (_bit_offset(_start) != 0) 344 _test |= _bit_make_mask(0, _start - 1); 345 for (_offset = 0;; _offset -= _BITSTR_BITS, _test = *++_curbitstr) { 346 if (_test != 0) { 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) 350 break; 351 /* Shrink-left every 0-area in _test by size-1 bits. */ 352 _b = _logsize; 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 : 357 ffsl(~_test) - 1; 358 _value = (_curbitstr - _bitstr) * _BITSTR_BITS + 359 _offset; 360 /* If there's insufficient space left, give up. */ 361 if (_value + _size > _nbits) { 362 _value = -1; 363 break; 364 } 365 } 366 if (_offset + _size <= (int)_BITSTR_BITS) 367 break; 368 } 369 *_result = _value; 370} 371 372/* Find contiguous sequence of at least size set bits in bit string */ 373static inline void 374bit_ffs_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result) 375{ 376 bit_ffs_area_at(_bitstr, /*start*/0, _nbits, _size, _result); 377} 378 379/* Find contiguous sequence of at least size cleared bits in bit string */ 380static inline void 381bit_ffc_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result) 382{ 383 bit_ffc_area_at(_bitstr, /*start*/0, _nbits, _size, _result); 384} 385 386/* Count the number of bits set in a bitstr of size _nbits at or after _start */ 387static inline void 388bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result) 389{ 390 bitstr_t *_curbitstr, mask; 391 int _value = 0, curbitstr_len; 392 393 if (_start >= _nbits) 394 goto out; 395 396 _curbitstr = _bitstr + _bit_idx(_start); 397 _nbits -= _BITSTR_BITS * _bit_idx(_start); 398 _start -= _BITSTR_BITS * _bit_idx(_start); 399 400 if (_start > 0) { 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); 405 _curbitstr++; 406 _nbits -= _BITSTR_BITS; 407 } 408 while (_nbits >= (int)_BITSTR_BITS) { 409 _value += __bitcountl(*_curbitstr); 410 _curbitstr++; 411 _nbits -= _BITSTR_BITS; 412 } 413 if (_nbits > 0) { 414 mask = _bit_make_mask(0, _bit_offset(_nbits - 1)); 415 _value += __bitcountl(*_curbitstr & mask); 416 } 417 418out: 419 *_result = _value; 420} 421 422#endif /* _SYS_BITSTRING_H_ */ 423