bitstring.h revision 299090 
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 * 4. Neither the name of the University nor the names of its contributors
17 *    may be used to endorse or promote products derived from this software
18 *    without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 * Copyright (c) 2014 Spectra Logic Corporation
33 * All rights reserved.
34 *
35 * Redistribution and use in source and binary forms, with or without
36 * modification, are permitted provided that the following conditions
37 * are met:
38 * 1. Redistributions of source code must retain the above copyright
39 *    notice, this list of conditions, and the following disclaimer,
40 *    without modification.
41 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
42 *    substantially similar to the "NO WARRANTY" disclaimer below
43 *    ("Disclaimer") and any redistribution must be conditioned upon
44 *    including a substantially similar Disclaimer requirement for further
45 *    binary redistribution.
46 *
47 * NO WARRANTY
48 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
49 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
50 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
51 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
52 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
53 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
54 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
55 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
56 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
57 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
58 * POSSIBILITY OF SUCH DAMAGES.
59 *
60 * $FreeBSD: head/sys/sys/bitstring.h 299090 2016-05-04 22:34:11Z asomers $
61 */
62#ifndef _SYS_BITSTRING_H_
63#define	_SYS_BITSTRING_H_
64
65#ifdef _KERNEL
66#include <sys/libkern.h>
67#include <sys/malloc.h>
68#endif
69
70typedef	unsigned long bitstr_t;
71
72/*---------------------- Private Implementation Details ----------------------*/
73#define	_BITSTR_MASK (~0UL)
74#define	_BITSTR_BITS (sizeof(bitstr_t) * 8)
75
76/* bitstr_t in bit string containing the bit. */
77static inline int
78_bit_idx(int _bit)
79{
80	return (_bit / _BITSTR_BITS);
81}
82
83/* bit number within bitstr_t at _bit_idx(_bit). */
84static inline int
85_bit_offset(int _bit)
86{
87	return (_bit % _BITSTR_BITS);
88}
89
90/* Mask for the bit within its long. */
91static inline bitstr_t
92_bit_mask(int _bit)
93{
94	return (1UL << _bit_offset(_bit));
95}
96
97static inline bitstr_t
98_bit_make_mask(int _start, int _stop)
99{
100	return ((_BITSTR_MASK << _bit_offset(_start)) &
101	    (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1)));
102}
103
104/*----------------------------- Public Interface -----------------------------*/
105/* Number of bytes consumed by a bit string of nbits bits */
106#define	bitstr_size(_nbits) \
107	(((_nbits) + _BITSTR_BITS - 1) / 8)
108
109/* Allocate a bit string initialized with no bits set. */
110#ifdef _KERNEL
111static inline bitstr_t *
112bit_alloc(int _nbits, struct malloc_type *type, int flags)
113{
114	return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO));
115}
116#else
117static inline bitstr_t *
118bit_alloc(int _nbits)
119{
120	return ((bitstr_t *)calloc(bitstr_size(_nbits), 1));
121}
122#endif
123
124/* Allocate a bit string on the stack with no bits set. */
125#define	bit_decl(name, nbits) \
126	((name)[bitstr_size(nbits) / sizeof(bitstr_t)])
127
128/* Is bit N of bit string set? */
129static inline int
130bit_test(const bitstr_t *_bitstr, int _bit)
131{
132	return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0);
133}
134
135/* Set bit N of bit string. */
136static inline void
137bit_set(bitstr_t *_bitstr, int _bit)
138{
139	_bitstr[_bit_idx(_bit)] |= _bit_mask(_bit);
140}
141
142/* clear bit N of bit string name */
143static inline void
144bit_clear(bitstr_t *_bitstr, int _bit)
145{
146	_bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
147}
148
149/* Set bits start ... stop inclusive in bit string. */
150static inline void
151bit_nset(bitstr_t *_bitstr, int _start, int _stop)
152{
153	bitstr_t *_stopbitstr;
154
155	_stopbitstr = _bitstr + _bit_idx(_stop);
156	_bitstr += _bit_idx(_start);
157
158	if (_bitstr == _stopbitstr) {
159		*_bitstr |= _bit_make_mask(_start, _stop);
160	} else {
161		*_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1);
162		while (++_bitstr < _stopbitstr)
163	    		*_bitstr = _BITSTR_MASK;
164		*_stopbitstr |= _bit_make_mask(0, _stop);
165	}
166}
167
168/* Clear bits start ... stop inclusive in bit string. */
169static inline void
170bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
171{
172	bitstr_t *_stopbitstr;
173
174	_stopbitstr = _bitstr + _bit_idx(_stop);
175	_bitstr += _bit_idx(_start);
176
177	if (_bitstr == _stopbitstr) {
178		*_bitstr &= ~_bit_make_mask(_start, _stop);
179	} else {
180		*_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
181		while (++_bitstr < _stopbitstr)
182			*_bitstr = 0;
183		*_stopbitstr &= ~_bit_make_mask(0, _stop);
184	}
185}
186
187/* Find the first bit set in bit string at or after bit start. */
188static inline void
189bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
190{
191	bitstr_t *_curbitstr;
192	bitstr_t *_stopbitstr;
193	bitstr_t _test;
194	int _value, _offset;
195
196	if (_nbits > 0) {
197		_curbitstr = _bitstr + _bit_idx(_start);
198		_stopbitstr = _bitstr + _bit_idx(_nbits - 1);
199
200		_test = *_curbitstr;
201		if (_bit_offset(_start) != 0)
202			_test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
203		while (_test == 0 && _curbitstr < _stopbitstr)
204			_test = *(++_curbitstr);
205
206		_offset = ffsl(_test);
207		_value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
208		if (_offset == 0 || _value >= _nbits)
209			_value = -1;
210	} else {
211		_value = -1;
212	}
213	*_result = _value;
214}
215
216/* Find the first bit clear in bit string at or after bit start. */
217static inline void
218bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
219{
220	bitstr_t *_curbitstr;
221	bitstr_t *_stopbitstr;
222	bitstr_t _test;
223	int _value, _offset;
224
225	if (_nbits > 0) {
226		_curbitstr = _bitstr + _bit_idx(_start);
227		_stopbitstr = _bitstr + _bit_idx(_nbits - 1);
228
229		_test = *_curbitstr;
230		if (_bit_offset(_start) != 0)
231			_test |= _bit_make_mask(0, _start - 1);
232		while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr)
233			_test = *(++_curbitstr);
234
235		_offset = ffsl(~_test);
236		_value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
237		if (_offset == 0 || _value >= _nbits)
238			_value = -1;
239	} else {
240		_value = -1;
241	}
242	*_result = _value;
243}
244
245/* Find the first bit set in bit string. */
246static inline void
247bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result)
248{
249	bit_ffs_at(_bitstr, /*start*/0, _nbits, _result);
250}
251
252/* Find the first bit clear in bit string. */
253static inline void
254bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result)
255{
256	bit_ffc_at(_bitstr, /*start*/0, _nbits, _result);
257}
258
259#endif	/* _SYS_BITSTRING_H_ */
260