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   * 3. All advertising materials mentioning features or use of this software
 17   *    must display the following acknowledgement:
 18   *	This product includes software developed by the University of
 19   *	California, Berkeley and its contributors.
 20   * 4. Neither the name of the University nor the names of its contributors
 21   *    may be used to endorse or promote products derived from this software
 22   *    without specific prior written permission.
 23   *
 24   * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 25   * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 26   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 27   * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 28   * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 29   * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 30   * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 31   * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 32   * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 33   * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 34   * SUCH DAMAGE.
 35   *
 36   * $FreeBSD$
 37   */
 38  
 39  #ifndef _BITSTRING_H_
 40  #define	_BITSTRING_H_
 41  
 42  typedef	unsigned char bitstr_t;
 43  
 44  /* internal macros */
 45  				/* byte of the bitstring bit is in */
 46  #define	_bit_byte(bit) \
 47  	((bit) >> 3)
 48  
 49  				/* mask for the bit within its byte */
 50  #define	_bit_mask(bit) \
 51  	(1 << ((bit)&0x7))
 52  
 53  /* external macros */
 54  				/* bytes in a bitstring of nbits bits */
 55  #define	bitstr_size(nbits) \
 56  	(((nbits) + 7) >> 3)
 57  
 58  				/* allocate a bitstring */
 59  #define	bit_alloc(nbits) \
 60  	(bitstr_t *)calloc((size_t)bitstr_size(nbits), sizeof(bitstr_t))
 61  
 62  				/* allocate a bitstring on the stack */
 63  #define	bit_decl(name, nbits) \
 64  	((name)[bitstr_size(nbits)])
 65  
 66  				/* is bit N of bitstring name set? */
 67  #define	bit_test(name, bit) \
 68  	((name)[_bit_byte(bit)] & _bit_mask(bit))
 69  
 70  				/* set bit N of bitstring name */
 71  #define	bit_set(name, bit) \
 72  	((name)[_bit_byte(bit)] |= _bit_mask(bit))
 73  
 74  				/* clear bit N of bitstring name */
 75  #define	bit_clear(name, bit) \
 76  	((name)[_bit_byte(bit)] &= ~_bit_mask(bit))
 77  
 78  				/* clear bits start ... stop in bitstring */
 79  #define	bit_nclear(name, start, stop) do { \
 80  	bitstr_t *_name = (name); \
 81  	int _start = (start), _stop = (stop); \
 82  	int _startbyte = _bit_byte(_start); \
 83  	int _stopbyte = _bit_byte(_stop); \
 84  	if (_startbyte == _stopbyte) { \
 85  		_name[_startbyte] &= ((0xff >> (8 - (_start&0x7))) | \
 86  				      (0xff << ((_stop&0x7) + 1))); \
 87  	} else { \
 88  		_name[_startbyte] &= 0xff >> (8 - (_start&0x7)); \
 89  		while (++_startbyte < _stopbyte) \
 90  			_name[_startbyte] = 0; \
 91  		_name[_stopbyte] &= 0xff << ((_stop&0x7) + 1); \
 92  	} \
 93  } while (0)
 94  
 95  				/* set bits start ... stop in bitstring */
 96  #define	bit_nset(name, start, stop) do { \
 97  	bitstr_t *_name = (name); \
 98  	int _start = (start), _stop = (stop); \
 99  	int _startbyte = _bit_byte(_start); \
100  	int _stopbyte = _bit_byte(_stop); \
101  	if (_startbyte == _stopbyte) { \
102  		_name[_startbyte] |= ((0xff << (_start&0x7)) & \
103  				    (0xff >> (7 - (_stop&0x7)))); \
104  	} else { \
105  		_name[_startbyte] |= 0xff << ((_start)&0x7); \
106  		while (++_startbyte < _stopbyte) \
107  	    		_name[_startbyte] = 0xff; \
108  		_name[_stopbyte] |= 0xff >> (7 - (_stop&0x7)); \
109  	} \
110  } while (0)
111  
112  				/* find first bit clear in name */
113  #define	bit_ffc(name, nbits, value) do { \
114  	bitstr_t *_name = (name); \
115  	int _byte, _nbits = (nbits); \
116  	int _stopbyte = _bit_byte(_nbits - 1), _value = -1; \
117  	if (_nbits > 0) \
118  		for (_byte = 0; _byte <= _stopbyte; ++_byte) \
119  			if (_name[_byte] != 0xff) { \
120  				bitstr_t _lb; \
121  				_value = _byte << 3; \
122  				for (_lb = _name[_byte]; (_lb&0x1); \
123  				    ++_value, _lb >>= 1); \
124  				break; \
125  			} \
126  	if (_value >= nbits) \
127  		_value = -1; \
128  	*(value) = _value; \
129  } while (0)
130  
131  				/* find first bit set in name */
132  #define	bit_ffs(name, nbits, value) do { \
133  	bitstr_t *_name = (name); \
134  	int _byte, _nbits = (nbits); \
135  	int _stopbyte = _bit_byte(_nbits - 1), _value = -1; \
136  	if (_nbits > 0) \
137  		for (_byte = 0; _byte <= _stopbyte; ++_byte) \
138  			if (_name[_byte]) { \
139  				bitstr_t _lb; \
140  				_value = _byte << 3; \
141  				for (_lb = _name[_byte]; !(_lb&0x1); \
142  				    ++_value, _lb >>= 1); \
143  				break; \
144  			} \
145  	if (_value >= nbits) \
146  		_value = -1; \
147  	*(value) = _value; \
148  } while (0)
149  
150  #endif /* !_BITSTRING_H_ */