1139825Simp/*- 21539Srgrimes * Copyright (c) 1989, 1993 31539Srgrimes * The Regents of the University of California. All rights reserved. 41539Srgrimes * 51539Srgrimes * This code is derived from software contributed to Berkeley by 61539Srgrimes * Paul Vixie. 71539Srgrimes * 81539Srgrimes * Redistribution and use in source and binary forms, with or without 91539Srgrimes * modification, are permitted provided that the following conditions 101539Srgrimes * are met: 111539Srgrimes * 1. Redistributions of source code must retain the above copyright 121539Srgrimes * notice, this list of conditions and the following disclaimer. 131539Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141539Srgrimes * notice, this list of conditions and the following disclaimer in the 151539Srgrimes * documentation and/or other materials provided with the distribution. 161539Srgrimes * 4. Neither the name of the University nor the names of its contributors 171539Srgrimes * may be used to endorse or promote products derived from this software 181539Srgrimes * without specific prior written permission. 191539Srgrimes * 201539Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211539Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221539Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231539Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241539Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251539Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261539Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271539Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281539Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291539Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301539Srgrimes * SUCH DAMAGE. 311539Srgrimes * 32299090Sasomers * Copyright (c) 2014 Spectra Logic Corporation 33299090Sasomers * All rights reserved. 34299090Sasomers * 35299090Sasomers * Redistribution and use in source and binary forms, with or without 36299090Sasomers * modification, are permitted provided that the following conditions 37299090Sasomers * are met: 38299090Sasomers * 1. Redistributions of source code must retain the above copyright 39299090Sasomers * notice, this list of conditions, and the following disclaimer, 40299090Sasomers * without modification. 41299090Sasomers * 2. Redistributions in binary form must reproduce at minimum a disclaimer 42299090Sasomers * substantially similar to the "NO WARRANTY" disclaimer below 43299090Sasomers * ("Disclaimer") and any redistribution must be conditioned upon 44299090Sasomers * including a substantially similar Disclaimer requirement for further 45299090Sasomers * binary redistribution. 46299090Sasomers * 47299090Sasomers * NO WARRANTY 48299090Sasomers * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 49299090Sasomers * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 50299090Sasomers * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR 51299090Sasomers * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 52299090Sasomers * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 53299090Sasomers * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 54299090Sasomers * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 55299090Sasomers * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 56299090Sasomers * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 57299090Sasomers * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 58299090Sasomers * POSSIBILITY OF SUCH DAMAGES. 59299090Sasomers * 6066872Sdwmalone * $FreeBSD$ 611539Srgrimes */ 62116306Sphk#ifndef _SYS_BITSTRING_H_ 63116306Sphk#define _SYS_BITSTRING_H_ 641539Srgrimes 65299090Sasomers#ifdef _KERNEL 66299090Sasomers#include <sys/libkern.h> 67299090Sasomers#include <sys/malloc.h> 68299090Sasomers#endif 691539Srgrimes 70300544Sasomers#include <sys/types.h> 71300544Sasomers 72299090Sasomerstypedef unsigned long bitstr_t; 731539Srgrimes 74299090Sasomers/*---------------------- Private Implementation Details ----------------------*/ 75299090Sasomers#define _BITSTR_MASK (~0UL) 76299090Sasomers#define _BITSTR_BITS (sizeof(bitstr_t) * 8) 771539Srgrimes 78302180Sasomers#ifdef roundup2 79302180Sasomers#define _bit_roundup2 roundup2 80302180Sasomers#else 81302180Sasomers#define _bit_roundup2(x, y) (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */ 82302180Sasomers#endif 83302180Sasomers 84299090Sasomers/* bitstr_t in bit string containing the bit. */ 85299090Sasomersstatic inline int 86299090Sasomers_bit_idx(int _bit) 87299090Sasomers{ 88299090Sasomers return (_bit / _BITSTR_BITS); 89299090Sasomers} 901539Srgrimes 91299090Sasomers/* bit number within bitstr_t at _bit_idx(_bit). */ 92299090Sasomersstatic inline int 93299090Sasomers_bit_offset(int _bit) 94299090Sasomers{ 95299090Sasomers return (_bit % _BITSTR_BITS); 96299090Sasomers} 971539Srgrimes 98299090Sasomers/* Mask for the bit within its long. */ 99299090Sasomersstatic inline bitstr_t 100299090Sasomers_bit_mask(int _bit) 101299090Sasomers{ 102299090Sasomers return (1UL << _bit_offset(_bit)); 103299090Sasomers} 104299090Sasomers 105299090Sasomersstatic inline bitstr_t 106299090Sasomers_bit_make_mask(int _start, int _stop) 107299090Sasomers{ 108299090Sasomers return ((_BITSTR_MASK << _bit_offset(_start)) & 109299090Sasomers (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1))); 110299090Sasomers} 111299090Sasomers 112299090Sasomers/*----------------------------- Public Interface -----------------------------*/ 113302180Sasomers/* Number of bytes allocated for a bit string of nbits bits */ 114302180Sasomers#define bitstr_size(_nbits) (_bit_roundup2(_nbits, _BITSTR_BITS) / 8) 115299090Sasomers 116299090Sasomers/* Allocate a bit string initialized with no bits set. */ 117299090Sasomers#ifdef _KERNEL 118299090Sasomersstatic inline bitstr_t * 119299090Sasomersbit_alloc(int _nbits, struct malloc_type *type, int flags) 120299090Sasomers{ 121299090Sasomers return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO)); 122299090Sasomers} 123299090Sasomers#else 124299090Sasomersstatic inline bitstr_t * 125299090Sasomersbit_alloc(int _nbits) 126299090Sasomers{ 127299090Sasomers return ((bitstr_t *)calloc(bitstr_size(_nbits), 1)); 128299090Sasomers} 129299090Sasomers#endif 130299090Sasomers 131302180Sasomers/* Allocate a bit string on the stack */ 1321539Srgrimes#define bit_decl(name, nbits) \ 133299090Sasomers ((name)[bitstr_size(nbits) / sizeof(bitstr_t)]) 1341539Srgrimes 135299090Sasomers/* Is bit N of bit string set? */ 136299090Sasomersstatic inline int 137299090Sasomersbit_test(const bitstr_t *_bitstr, int _bit) 138299090Sasomers{ 139299090Sasomers return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0); 140299090Sasomers} 1411539Srgrimes 142299090Sasomers/* Set bit N of bit string. */ 143299090Sasomersstatic inline void 144299090Sasomersbit_set(bitstr_t *_bitstr, int _bit) 145299090Sasomers{ 146299090Sasomers _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit); 147299090Sasomers} 1481539Srgrimes 149299090Sasomers/* clear bit N of bit string name */ 150299090Sasomersstatic inline void 151299090Sasomersbit_clear(bitstr_t *_bitstr, int _bit) 152299090Sasomers{ 153299090Sasomers _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit); 154299090Sasomers} 1551539Srgrimes 156299090Sasomers/* Set bits start ... stop inclusive in bit string. */ 157299090Sasomersstatic inline void 158299090Sasomersbit_nset(bitstr_t *_bitstr, int _start, int _stop) 159299090Sasomers{ 160299090Sasomers bitstr_t *_stopbitstr; 1611539Srgrimes 162299090Sasomers _stopbitstr = _bitstr + _bit_idx(_stop); 163299090Sasomers _bitstr += _bit_idx(_start); 1641539Srgrimes 165299090Sasomers if (_bitstr == _stopbitstr) { 166299090Sasomers *_bitstr |= _bit_make_mask(_start, _stop); 167299090Sasomers } else { 168299090Sasomers *_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1); 169299090Sasomers while (++_bitstr < _stopbitstr) 170299090Sasomers *_bitstr = _BITSTR_MASK; 171299090Sasomers *_stopbitstr |= _bit_make_mask(0, _stop); 172299090Sasomers } 173299090Sasomers} 1741539Srgrimes 175299090Sasomers/* Clear bits start ... stop inclusive in bit string. */ 176299090Sasomersstatic inline void 177299090Sasomersbit_nclear(bitstr_t *_bitstr, int _start, int _stop) 178299090Sasomers{ 179299090Sasomers bitstr_t *_stopbitstr; 1801539Srgrimes 181299090Sasomers _stopbitstr = _bitstr + _bit_idx(_stop); 182299090Sasomers _bitstr += _bit_idx(_start); 183299090Sasomers 184299090Sasomers if (_bitstr == _stopbitstr) { 185299090Sasomers *_bitstr &= ~_bit_make_mask(_start, _stop); 186299090Sasomers } else { 187299090Sasomers *_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1); 188299090Sasomers while (++_bitstr < _stopbitstr) 189299090Sasomers *_bitstr = 0; 190299090Sasomers *_stopbitstr &= ~_bit_make_mask(0, _stop); 191299090Sasomers } 192299090Sasomers} 193299090Sasomers 194299090Sasomers/* Find the first bit set in bit string at or after bit start. */ 195299090Sasomersstatic inline void 196299090Sasomersbit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result) 197299090Sasomers{ 198299090Sasomers bitstr_t *_curbitstr; 199299090Sasomers bitstr_t *_stopbitstr; 200299090Sasomers bitstr_t _test; 201299090Sasomers int _value, _offset; 202299090Sasomers 203299090Sasomers if (_nbits > 0) { 204299090Sasomers _curbitstr = _bitstr + _bit_idx(_start); 205299090Sasomers _stopbitstr = _bitstr + _bit_idx(_nbits - 1); 206299090Sasomers 207299090Sasomers _test = *_curbitstr; 208299090Sasomers if (_bit_offset(_start) != 0) 209299090Sasomers _test &= _bit_make_mask(_start, _BITSTR_BITS - 1); 210299090Sasomers while (_test == 0 && _curbitstr < _stopbitstr) 211299090Sasomers _test = *(++_curbitstr); 212300539Sasomers 213299090Sasomers _offset = ffsl(_test); 214299090Sasomers _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1; 215299090Sasomers if (_offset == 0 || _value >= _nbits) 216299090Sasomers _value = -1; 217299090Sasomers } else { 218299090Sasomers _value = -1; 219299090Sasomers } 220299090Sasomers *_result = _value; 221299090Sasomers} 222299090Sasomers 223299090Sasomers/* Find the first bit clear in bit string at or after bit start. */ 224299090Sasomersstatic inline void 225299090Sasomersbit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result) 226299090Sasomers{ 227299090Sasomers bitstr_t *_curbitstr; 228299090Sasomers bitstr_t *_stopbitstr; 229299090Sasomers bitstr_t _test; 230299090Sasomers int _value, _offset; 231299090Sasomers 232299090Sasomers if (_nbits > 0) { 233299090Sasomers _curbitstr = _bitstr + _bit_idx(_start); 234299090Sasomers _stopbitstr = _bitstr + _bit_idx(_nbits - 1); 235299090Sasomers 236299090Sasomers _test = *_curbitstr; 237299090Sasomers if (_bit_offset(_start) != 0) 238299090Sasomers _test |= _bit_make_mask(0, _start - 1); 239299090Sasomers while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr) 240299090Sasomers _test = *(++_curbitstr); 241300539Sasomers 242299090Sasomers _offset = ffsl(~_test); 243299090Sasomers _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1; 244299090Sasomers if (_offset == 0 || _value >= _nbits) 245299090Sasomers _value = -1; 246299090Sasomers } else { 247299090Sasomers _value = -1; 248299090Sasomers } 249299090Sasomers *_result = _value; 250299090Sasomers} 251299090Sasomers 252299090Sasomers/* Find the first bit set in bit string. */ 253299090Sasomersstatic inline void 254299090Sasomersbit_ffs(bitstr_t *_bitstr, int _nbits, int *_result) 255299090Sasomers{ 256299090Sasomers bit_ffs_at(_bitstr, /*start*/0, _nbits, _result); 257299090Sasomers} 258299090Sasomers 259299090Sasomers/* Find the first bit clear in bit string. */ 260299090Sasomersstatic inline void 261299090Sasomersbit_ffc(bitstr_t *_bitstr, int _nbits, int *_result) 262299090Sasomers{ 263299090Sasomers bit_ffc_at(_bitstr, /*start*/0, _nbits, _result); 264299090Sasomers} 265299090Sasomers 266300539Sasomers/* Count the number of bits set in a bitstr of size _nbits at or after _start */ 267300539Sasomersstatic inline void 268300539Sasomersbit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result) 269300539Sasomers{ 270300539Sasomers bitstr_t *_curbitstr, mask; 271300539Sasomers int _value = 0, curbitstr_len; 272300539Sasomers 273300539Sasomers if (_start >= _nbits) 274300539Sasomers goto out; 275300539Sasomers 276300539Sasomers _curbitstr = _bitstr + _bit_idx(_start); 277300539Sasomers _nbits -= _BITSTR_BITS * _bit_idx(_start); 278300539Sasomers _start -= _BITSTR_BITS * _bit_idx(_start); 279300539Sasomers 280300539Sasomers if (_start > 0) { 281300539Sasomers curbitstr_len = (int)_BITSTR_BITS < _nbits ? 282300539Sasomers (int)_BITSTR_BITS : _nbits; 283300539Sasomers mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1)); 284300539Sasomers _value += __bitcountl(*_curbitstr & mask); 285300539Sasomers _curbitstr++; 286300539Sasomers _nbits -= _BITSTR_BITS; 287300539Sasomers } 288300539Sasomers while (_nbits >= (int)_BITSTR_BITS) { 289300539Sasomers _value += __bitcountl(*_curbitstr); 290300539Sasomers _curbitstr++; 291300539Sasomers _nbits -= _BITSTR_BITS; 292300539Sasomers } 293300539Sasomers if (_nbits > 0) { 294300539Sasomers mask = _bit_make_mask(0, _bit_offset(_nbits - 1)); 295300539Sasomers _value += __bitcountl(*_curbitstr & mask); 296300539Sasomers } 297300539Sasomers 298300539Sasomersout: 299300539Sasomers *_result = _value; 300300539Sasomers} 301300539Sasomers 302299090Sasomers#endif /* _SYS_BITSTRING_H_ */ 303