1/* $OpenBSD: bitstring.h,v 1.5 2003/06/02 19:34:12 millert Exp $ */
2/* $NetBSD: bitstring.h,v 1.5 1997/05/14 15:49:55 pk Exp $ */
3
4/*
5 * Copyright (c) 1989, 1993
6 * The Regents of the University of California. All rights reserved.
7 *
8 * This code is derived from software contributed to Berkeley by
9 * Paul Vixie.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 *
35 * @(#)bitstring.h 8.1 (Berkeley) 7/19/93
36 */
37
38#ifndef _BITSTRING_H_
39#define _BITSTRING_H_
40
41/* modified for SV/AT and bitstring bugfix by M.R.Murphy, 11oct91
42 * bitstr_size changed gratuitously, but shorter
43 * bit_alloc spelling error fixed
44 * the following were efficient, but didn't work, they've been made to
45 * work, but are no longer as efficient :-)
46 * bit_nclear, bit_nset, bit_ffc, bit_ffs
47 */
48typedef unsigned char bitstr_t;
49
50/* internal macros */
51 /* byte of the bitstring bit is in */
52#define _bit_byte(bit) \
53 ((bit) >> 3)
54
55 /* mask for the bit within its byte */
56#define _bit_mask(bit) \
57 (1 << ((bit)&0x7))
58
59/* external macros */
60 /* bytes in a bitstring of nbits bits */
61#define bitstr_size(nbits) \
62 (((nbits) + 7) >> 3)
63
64 /* allocate a bitstring */
65#define bit_alloc(nbits) \
66 (bitstr_t *)calloc((size_t)bitstr_size(nbits), sizeof(bitstr_t))
67
68 /* allocate a bitstring on the stack */
69#define bit_decl(name, nbits) \
70 ((name)[bitstr_size(nbits)])
71
72 /* is bit N of bitstring name set? */
73#define bit_test(name, bit) \
74 ((name)[_bit_byte(bit)] & _bit_mask(bit))
75
76 /* set bit N of bitstring name */
77#define bit_set(name, bit) \
78 ((name)[_bit_byte(bit)] |= _bit_mask(bit))
79
80 /* clear bit N of bitstring name */
81#define bit_clear(name, bit) \
82 ((name)[_bit_byte(bit)] &= ~_bit_mask(bit))
83
84 /* clear bits start ... stop in bitstring */
85#define bit_nclear(name, start, stop) do { \
86 register bitstr_t *_name = name; \
87 register int _start = start, _stop = stop; \
88 while (_start <= _stop) { \
89 bit_clear(_name, _start); \
90 _start++; \
91 } \
92} while(0)
93
94 /* set bits start ... stop in bitstring */
95#define bit_nset(name, start, stop) do { \
96 register bitstr_t *_name = name; \
97 register int _start = start, _stop = stop; \
98 while (_start <= _stop) { \
99 bit_set(_name, _start); \
100 _start++; \
101 } \
102} while(0)
103
104 /* find first bit clear in name */
105#define bit_ffc(name, nbits, value) do { \
106 register bitstr_t *_name = name; \
107 register int _bit, _nbits = nbits, _value = -1; \
108 for (_bit = 0; _bit < _nbits; ++_bit) \
109 if (!bit_test(_name, _bit)) { \
110 _value = _bit; \
111 break; \
112 } \
113 *(value) = _value; \
114} while(0)
115
116 /* find first bit set in name */
117#define bit_ffs(name, nbits, value) do { \
118 register bitstr_t *_name = name; \
119 register int _bit, _nbits = nbits, _value = -1; \
120 for (_bit = 0; _bit < _nbits; ++_bit) \
121 if (bit_test(_name, _bit)) { \
122 _value = _bit; \
123 break; \
124 } \
125 *(value) = _value; \
126} while(0)
127
128#endif /* !_BITSTRING_H_ */
129