sys/sys/bitstring.h

   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  * 4. 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 MERCHANTIBILITY 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_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 /* Set bits start ... stop inclusive in bit string. */
 157 static inline void
 158 bit_nset(bitstr_t *_bitstr, int _start, int _stop)
 159 {
 160         bitstr_t *_stopbitstr;
 161
 162         _stopbitstr = _bitstr + _bit_idx(_stop);
 163         _bitstr += _bit_idx(_start);
 164
 165         if (_bitstr == _stopbitstr) {
 166                 *_bitstr |= _bit_make_mask(_start, _stop);
 167         } else {
 168                 *_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1);
 169                 while (++_bitstr < _stopbitstr)
 170                         *_bitstr = _BITSTR_MASK;
 171                 *_stopbitstr |= _bit_make_mask(0, _stop);
 172         }
 173 }
 174
 175 /* Clear bits start ... stop inclusive in bit string. */
 176 static inline void
 177 bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
 178 {
 179         bitstr_t *_stopbitstr;
 180
 181         _stopbitstr = _bitstr + _bit_idx(_stop);
 182         _bitstr += _bit_idx(_start);
 183
 184         if (_bitstr == _stopbitstr) {
 185                 *_bitstr &= ~_bit_make_mask(_start, _stop);
 186         } else {
 187                 *_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
 188                 while (++_bitstr < _stopbitstr)
 189                         *_bitstr = 0;
 190                 *_stopbitstr &= ~_bit_make_mask(0, _stop);
 191         }
 192 }
 193
 194 /* Find the first bit set in bit string at or after bit start. */
 195 static inline void
 196 bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
 197 {
 198         bitstr_t *_curbitstr;
 199         bitstr_t *_stopbitstr;
 200         bitstr_t _test;
 201         int _value, _offset;
 202
 203         if (_nbits > 0) {
 204                 _curbitstr = _bitstr + _bit_idx(_start);
 205                 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
 206
 207                 _test = *_curbitstr;
 208                 if (_bit_offset(_start) != 0)
 209                         _test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
 210                 while (_test == 0 && _curbitstr < _stopbitstr)
 211                         _test = *(++_curbitstr);
 212
 213                 _offset = ffsl(_test);
 214                 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
 215                 if (_offset == 0 || _value >= _nbits)
 216                         _value = -1;
 217         } else {
 218                 _value = -1;
 219         }
 220         *_result = _value;
 221 }
 222
 223 /* Find the first bit clear in bit string at or after bit start. */
 224 static inline void
 225 bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
 226 {
 227         bitstr_t *_curbitstr;
 228         bitstr_t *_stopbitstr;
 229         bitstr_t _test;
 230         int _value, _offset;
 231
 232         if (_nbits > 0) {
 233                 _curbitstr = _bitstr + _bit_idx(_start);
 234                 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
 235
 236                 _test = *_curbitstr;
 237                 if (_bit_offset(_start) != 0)
 238                         _test |= _bit_make_mask(0, _start - 1);
 239                 while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr)
 240                         _test = *(++_curbitstr);
 241
 242                 _offset = ffsl(~_test);
 243                 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
 244                 if (_offset == 0 || _value >= _nbits)
 245                         _value = -1;
 246         } else {
 247                 _value = -1;
 248         }
 249         *_result = _value;
 250 }
 251
 252 /* Find the first bit set in bit string. */
 253 static inline void
 254 bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result)
 255 {
 256         bit_ffs_at(_bitstr, /*start*/0, _nbits, _result);
 257 }
 258
 259 /* Find the first bit clear in bit string. */
 260 static inline void
 261 bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result)
 262 {
 263         bit_ffc_at(_bitstr, /*start*/0, _nbits, _result);
 264 }
 265
 266 /* Count the number of bits set in a bitstr of size _nbits at or after _start */
 267 static inline void
 268 bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
 269 {
 270         bitstr_t *_curbitstr, mask;
 271         int _value = 0, curbitstr_len;
 272
 273         if (_start >= _nbits)
 274                 goto out;
 275
 276         _curbitstr = _bitstr + _bit_idx(_start);
 277         _nbits -= _BITSTR_BITS * _bit_idx(_start);
 278         _start -= _BITSTR_BITS * _bit_idx(_start);
 279
 280         if (_start > 0) {
 281                 curbitstr_len = (int)_BITSTR_BITS < _nbits ?
 282                                 (int)_BITSTR_BITS : _nbits;
 283                 mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1));
 284                 _value += __bitcountl(*_curbitstr & mask);
 285                 _curbitstr++;
 286                 _nbits -= _BITSTR_BITS;
 287         }
 288         while (_nbits >= (int)_BITSTR_BITS) {
 289                 _value += __bitcountl(*_curbitstr);
 290                 _curbitstr++;
 291                 _nbits -= _BITSTR_BITS;
 292         }
 293         if (_nbits > 0) {
 294                 mask = _bit_make_mask(0, _bit_offset(_nbits - 1));
 295                 _value += __bitcountl(*_curbitstr & mask);
 296         }
 297
 298 out:
 299         *_result = _value;
 300 }
 301
 302 #endif  /* _SYS_BITSTRING_H_ */