bitstring.h revision 1539
11539Srgrimes/* 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 * 3. All advertising materials mentioning features or use of this software 171539Srgrimes * must display the following acknowledgement: 181539Srgrimes * This product includes software developed by the University of 191539Srgrimes * California, Berkeley and its contributors. 201539Srgrimes * 4. Neither the name of the University nor the names of its contributors 211539Srgrimes * may be used to endorse or promote products derived from this software 221539Srgrimes * without specific prior written permission. 231539Srgrimes * 241539Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 251539Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 261539Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 271539Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 281539Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 291539Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 301539Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 311539Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 321539Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 331539Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 341539Srgrimes * SUCH DAMAGE. 351539Srgrimes * 361539Srgrimes * @(#)bitstring.h 8.1 (Berkeley) 7/19/93 371539Srgrimes */ 381539Srgrimes 391539Srgrimes#ifndef _BITSTRING_H_ 401539Srgrimes#define _BITSTRING_H_ 411539Srgrimes 421539Srgrimestypedef unsigned char bitstr_t; 431539Srgrimes 441539Srgrimes/* internal macros */ 451539Srgrimes /* byte of the bitstring bit is in */ 461539Srgrimes#define _bit_byte(bit) \ 471539Srgrimes ((bit) >> 3) 481539Srgrimes 491539Srgrimes /* mask for the bit within its byte */ 501539Srgrimes#define _bit_mask(bit) \ 511539Srgrimes (1 << ((bit)&0x7)) 521539Srgrimes 531539Srgrimes/* external macros */ 541539Srgrimes /* bytes in a bitstring of nbits bits */ 551539Srgrimes#define bitstr_size(nbits) \ 561539Srgrimes ((((nbits) - 1) >> 3) + 1) 571539Srgrimes 581539Srgrimes /* allocate a bitstring */ 591539Srgrimes#define bit_alloc(nbits) \ 601539Srgrimes (bitstr_t *)calloc(1, \ 611539Srgrimes (unsigned int)bitstr_size(nbits) * sizeof(bitstr_t)) 621539Srgrimes 631539Srgrimes /* allocate a bitstring on the stack */ 641539Srgrimes#define bit_decl(name, nbits) \ 651539Srgrimes (name)[bitstr_size(nbits)] 661539Srgrimes 671539Srgrimes /* is bit N of bitstring name set? */ 681539Srgrimes#define bit_test(name, bit) \ 691539Srgrimes ((name)[_bit_byte(bit)] & _bit_mask(bit)) 701539Srgrimes 711539Srgrimes /* set bit N of bitstring name */ 721539Srgrimes#define bit_set(name, bit) \ 731539Srgrimes (name)[_bit_byte(bit)] |= _bit_mask(bit) 741539Srgrimes 751539Srgrimes /* clear bit N of bitstring name */ 761539Srgrimes#define bit_clear(name, bit) \ 771539Srgrimes (name)[_bit_byte(bit)] &= ~_bit_mask(bit) 781539Srgrimes 791539Srgrimes /* clear bits start ... stop in bitstring */ 801539Srgrimes#define bit_nclear(name, start, stop) { \ 811539Srgrimes register bitstr_t *_name = name; \ 821539Srgrimes register int _start = start, _stop = stop; \ 831539Srgrimes register int _startbyte = _bit_byte(_start); \ 841539Srgrimes register int _stopbyte = _bit_byte(_stop); \ 851539Srgrimes if (_startbyte == _stopbyte) { \ 861539Srgrimes _name[_startbyte] &= ((0xff >> (8 - (_start&0x7))) | \ 871539Srgrimes (0xff << ((_stop&0x7) + 1))); \ 881539Srgrimes } else { \ 891539Srgrimes _name[_startbyte] &= 0xff >> (8 - (_start&0x7)); \ 901539Srgrimes while (++_startbyte < _stopbyte) \ 911539Srgrimes _name[_startbyte] = 0; \ 921539Srgrimes _name[_stopbyte] &= 0xff << ((_stop&0x7) + 1); \ 931539Srgrimes } \ 941539Srgrimes} 951539Srgrimes 961539Srgrimes /* set bits start ... stop in bitstring */ 971539Srgrimes#define bit_nset(name, start, stop) { \ 981539Srgrimes register bitstr_t *_name = name; \ 991539Srgrimes register int _start = start, _stop = stop; \ 1001539Srgrimes register int _startbyte = _bit_byte(_start); \ 1011539Srgrimes register int _stopbyte = _bit_byte(_stop); \ 1021539Srgrimes if (_startbyte == _stopbyte) { \ 1031539Srgrimes _name[_startbyte] |= ((0xff << (_start&0x7)) & \ 1041539Srgrimes (0xff >> (7 - (_stop&0x7)))); \ 1051539Srgrimes } else { \ 1061539Srgrimes _name[_startbyte] |= 0xff << ((_start)&0x7); \ 1071539Srgrimes while (++_startbyte < _stopbyte) \ 1081539Srgrimes _name[_startbyte] = 0xff; \ 1091539Srgrimes _name[_stopbyte] |= 0xff >> (7 - (_stop&0x7)); \ 1101539Srgrimes } \ 1111539Srgrimes} 1121539Srgrimes 1131539Srgrimes /* find first bit clear in name */ 1141539Srgrimes#define bit_ffc(name, nbits, value) { \ 1151539Srgrimes register bitstr_t *_name = name; \ 1161539Srgrimes register int _byte, _nbits = nbits; \ 1171539Srgrimes register int _stopbyte = _bit_byte(_nbits), _value = -1; \ 1181539Srgrimes for (_byte = 0; _byte <= _stopbyte; ++_byte) \ 1191539Srgrimes if (_name[_byte] != 0xff) { \ 1201539Srgrimes _value = _byte << 3; \ 1211539Srgrimes for (_stopbyte = _name[_byte]; (_stopbyte&0x1); \ 1221539Srgrimes ++_value, _stopbyte >>= 1); \ 1231539Srgrimes break; \ 1241539Srgrimes } \ 1251539Srgrimes *(value) = _value; \ 1261539Srgrimes} 1271539Srgrimes 1281539Srgrimes /* find first bit set in name */ 1291539Srgrimes#define bit_ffs(name, nbits, value) { \ 1301539Srgrimes register bitstr_t *_name = name; \ 1311539Srgrimes register int _byte, _nbits = nbits; \ 1321539Srgrimes register int _stopbyte = _bit_byte(_nbits), _value = -1; \ 1331539Srgrimes for (_byte = 0; _byte <= _stopbyte; ++_byte) \ 1341539Srgrimes if (_name[_byte]) { \ 1351539Srgrimes _value = _byte << 3; \ 1361539Srgrimes for (_stopbyte = _name[_byte]; !(_stopbyte&0x1); \ 1371539Srgrimes ++_value, _stopbyte >>= 1); \ 1381539Srgrimes break; \ 1391539Srgrimes } \ 1401539Srgrimes *(value) = _value; \ 1411539Srgrimes} 1421539Srgrimes 1431539Srgrimes#endif /* !_BITSTRING_H_ */ 144