1/* $OpenBSD: bitstring.h,v 1.7 2024/08/26 11:52:54 bluhm 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 register int __tbit = (bit); \
75 ((name)[_bit_byte(__tbit)] & _bit_mask(__tbit)); \
76})
77
78 /* set bit N of bitstring name */
79#define bit_set(name, bit) do { \
80 register int __sbit = (bit); \
81 ((name)[_bit_byte(__sbit)] |= _bit_mask(__sbit)); \
82} while(0)
83
84 /* clear bit N of bitstring name */
85#define bit_clear(name, bit) do { \
86 register int __cbit = (bit); \
87 ((name)[_bit_byte(__cbit)] &= ~_bit_mask(__cbit)); \
88} while(0)
89
90 /* clear bits start ... stop in bitstring */
91#define bit_nclear(name, start, stop) do { \
92 register bitstr_t *__name = (name); \
93 register int __start = (start), __stop = (stop); \
94 while (__start <= __stop) { \
95 bit_clear(__name, __start); \
96 __start++; \
97 } \
98} while(0)
99
100 /* set bits start ... stop in bitstring */
101#define bit_nset(name, start, stop) do { \
102 register bitstr_t *__name = (name); \
103 register int __start = (start), __stop = (stop); \
104 while (__start <= __stop) { \
105 bit_set(__name, __start); \
106 __start++; \
107 } \
108} while(0)
109
110 /* find first bit clear in name */
111#define bit_ffc(name, nbits, value) do { \
112 register bitstr_t *__name = (name); \
113 register int __bit, __nbits = (nbits), __value = -1; \
114 for (__bit = 0; __bit < __nbits; ++__bit) \
115 if (!bit_test(__name, __bit)) { \
116 __value = __bit; \
117 break; \
118 } \
119 *(value) = __value; \
120} while(0)
121
122 /* find first bit set in name */
123#define bit_ffs(name, nbits, value) do { \
124 register bitstr_t *__name = (name); \
125 register int __bit, __nbits = (nbits), __value = -1; \
126 for (__bit = 0; __bit < __nbits; ++__bit) \
127 if (bit_test(__name, __bit)) { \
128 __value = __bit; \
129 break; \
130 } \
131 *(value) = __value; \
132} while(0)
133
134#endif /* !_BITSTRING_H_ */