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