119304Speter/* 219304Speter * Copyright (c) 1989, 1993 319304Speter * The Regents of the University of California. All rights reserved. 419304Speter * 519304Speter * This code is derived from software contributed to Berkeley by 619304Speter * Paul Vixie. 719304Speter * 819304Speter * Redistribution and use in source and binary forms, with or without 919304Speter * modification, are permitted provided that the following conditions 1019304Speter * are met: 1119304Speter * 1. Redistributions of source code must retain the above copyright 1219304Speter * notice, this list of conditions and the following disclaimer. 1319304Speter * 2. Redistributions in binary form must reproduce the above copyright 1419304Speter * notice, this list of conditions and the following disclaimer in the 1519304Speter * documentation and/or other materials provided with the distribution. 1619304Speter * 3. All advertising materials mentioning features or use of this software 1719304Speter * must display the following acknowledgement: 1819304Speter * This product includes software developed by the University of 1919304Speter * California, Berkeley and its contributors. 2019304Speter * 4. Neither the name of the University nor the names of its contributors 2119304Speter * may be used to endorse or promote products derived from this software 2219304Speter * without specific prior written permission. 2319304Speter * 2419304Speter * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 2519304Speter * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 2619304Speter * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2719304Speter * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2819304Speter * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2919304Speter * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 3019304Speter * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 3119304Speter * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 3219304Speter * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 3319304Speter * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 3419304Speter * SUCH DAMAGE. 3519304Speter * 3619304Speter * @(#)bitstring.h 8.1 (Berkeley) 7/19/93 3719304Speter */ 3819304Speter 3919304Speter#ifndef _BITSTRING_H_ 4019304Speter#define _BITSTRING_H_ 4119304Speter 4219304Spetertypedef unsigned char bitstr_t; 4319304Speter 4419304Speter/* internal macros */ 4519304Speter /* byte of the bitstring bit is in */ 4619304Speter#define _bit_byte(bit) \ 4719304Speter ((bit) >> 3) 4819304Speter 4919304Speter /* mask for the bit within its byte */ 5019304Speter#define _bit_mask(bit) \ 5119304Speter (1 << ((bit)&0x7)) 5219304Speter 5319304Speter/* external macros */ 5419304Speter /* bytes in a bitstring of nbits bits */ 5519304Speter#define bitstr_size(nbits) \ 5619304Speter ((((nbits) - 1) >> 3) + 1) 5719304Speter 5819304Speter /* allocate a bitstring */ 5919304Speter#define bit_alloc(nbits) \ 6019304Speter (bitstr_t *)calloc(1, \ 6119304Speter (unsigned int)bitstr_size(nbits) * sizeof(bitstr_t)) 6219304Speter 6319304Speter /* allocate a bitstring on the stack */ 6419304Speter#define bit_decl(name, nbits) \ 6519304Speter (name)[bitstr_size(nbits)] 6619304Speter 6719304Speter /* is bit N of bitstring name set? */ 6819304Speter#define bit_test(name, bit) \ 6919304Speter ((name)[_bit_byte(bit)] & _bit_mask(bit)) 7019304Speter 7119304Speter /* set bit N of bitstring name */ 7219304Speter#define bit_set(name, bit) \ 7319304Speter (name)[_bit_byte(bit)] |= _bit_mask(bit) 7419304Speter 7519304Speter /* clear bit N of bitstring name */ 7619304Speter#define bit_clear(name, bit) \ 7719304Speter (name)[_bit_byte(bit)] &= ~_bit_mask(bit) 7819304Speter 7919304Speter /* clear bits start ... stop in bitstring */ 8019304Speter#define bit_nclear(name, start, stop) { \ 8119304Speter register bitstr_t *_name = name; \ 8219304Speter register int _start = start, _stop = stop; \ 8319304Speter register int _startbyte = _bit_byte(_start); \ 8419304Speter register int _stopbyte = _bit_byte(_stop); \ 8519304Speter if (_startbyte == _stopbyte) { \ 8619304Speter _name[_startbyte] &= ((0xff >> (8 - (_start&0x7))) | \ 8719304Speter (0xff << ((_stop&0x7) + 1))); \ 8819304Speter } else { \ 8919304Speter _name[_startbyte] &= 0xff >> (8 - (_start&0x7)); \ 9019304Speter while (++_startbyte < _stopbyte) \ 9119304Speter _name[_startbyte] = 0; \ 9219304Speter _name[_stopbyte] &= 0xff << ((_stop&0x7) + 1); \ 9319304Speter } \ 9419304Speter} 9519304Speter 9619304Speter /* set bits start ... stop in bitstring */ 9719304Speter#define bit_nset(name, start, stop) { \ 9819304Speter register bitstr_t *_name = name; \ 9919304Speter register int _start = start, _stop = stop; \ 10019304Speter register int _startbyte = _bit_byte(_start); \ 10119304Speter register int _stopbyte = _bit_byte(_stop); \ 10219304Speter if (_startbyte == _stopbyte) { \ 10319304Speter _name[_startbyte] |= ((0xff << (_start&0x7)) & \ 10419304Speter (0xff >> (7 - (_stop&0x7)))); \ 10519304Speter } else { \ 10619304Speter _name[_startbyte] |= 0xff << ((_start)&0x7); \ 10719304Speter while (++_startbyte < _stopbyte) \ 10819304Speter _name[_startbyte] = 0xff; \ 10919304Speter _name[_stopbyte] |= 0xff >> (7 - (_stop&0x7)); \ 11019304Speter } \ 11119304Speter} 11219304Speter 11319304Speter /* find first bit clear in name */ 11419304Speter#define bit_ffc(name, nbits, value) { \ 11519304Speter register bitstr_t *_name = name; \ 11619304Speter register int _byte, _nbits = nbits; \ 11719304Speter register int _stopbyte = _bit_byte(_nbits), _value = -1; \ 11819304Speter for (_byte = 0; _byte <= _stopbyte; ++_byte) \ 11919304Speter if (_name[_byte] != 0xff) { \ 12019304Speter _value = _byte << 3; \ 12119304Speter for (_stopbyte = _name[_byte]; (_stopbyte&0x1); \ 12219304Speter ++_value, _stopbyte >>= 1); \ 12319304Speter break; \ 12419304Speter } \ 12519304Speter *(value) = _value; \ 12619304Speter} 12719304Speter 12819304Speter /* find first bit set in name */ 12919304Speter#define bit_ffs(name, nbits, value) { \ 13019304Speter register bitstr_t *_name = name; \ 13119304Speter register int _byte, _nbits = nbits; \ 13219304Speter register int _stopbyte = _bit_byte(_nbits), _value = -1; \ 13319304Speter for (_byte = 0; _byte <= _stopbyte; ++_byte) \ 13419304Speter if (_name[_byte]) { \ 13519304Speter _value = _byte << 3; \ 13619304Speter for (_stopbyte = _name[_byte]; !(_stopbyte&0x1); \ 13719304Speter ++_value, _stopbyte >>= 1); \ 13819304Speter break; \ 13919304Speter } \ 14019304Speter *(value) = _value; \ 14119304Speter} 14219304Speter 14319304Speter#endif /* !_BITSTRING_H_ */ 144