bitstring.h revision 66872 
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: head/include/bitstring.h 66872 2000-10-09 12:34:51Z dwmalone $
37 */
38
39#ifndef _BITSTRING_H_
40#define	_BITSTRING_H_
41
42typedef	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	register bitstr_t *_name = (name); \
81	register int _start = (start), _stop = (stop); \
82	register int _startbyte = _bit_byte(_start); \
83	register 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	register bitstr_t *_name = (name); \
98	register int _start = (start), _stop = (stop); \
99	register int _startbyte = _bit_byte(_start); \
100	register 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	register bitstr_t *_name = (name); \
115	register int _byte, _nbits = (nbits); \
116	register 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	register bitstr_t *_name = (name); \
134	register int _byte, _nbits = (nbits); \
135	register 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_ */
151