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  * $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 /* Set bits start ... stop inclusive in bit string. */
 159 static inline void
 160 bit_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. */
 178 static inline void
 179 bit_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. */
 197 static inline void
 198 bit_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. */
 231 static inline void
 232 bit_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. */
 265 static inline void
 266 bit_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. */
 272 static inline void
 273 bit_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 */
 279 static inline void
 280 bit_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 */
 326 static inline void
 327 bit_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 */
 373 static inline void
 374 bit_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 */
 380 static inline void
 381 bit_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 */
 387 static inline void
 388 bit_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
 418 out:
 419         *_result = _value;
 420 }
 421
 422 #endif  /* _SYS_BITSTRING_H_ */