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