sys/sys/bitstring.h

   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_ */