1d3d1dd3eSPeeter Must /*-
2d3d1dd3eSPeeter Must * Copyright (c) 1989, 1993
3d3d1dd3eSPeeter Must * The Regents of the University of California. All rights reserved.
4d3d1dd3eSPeeter Must *
5d3d1dd3eSPeeter Must * This code is derived from software contributed to Berkeley by
6d3d1dd3eSPeeter Must * Paul Vixie.
7d3d1dd3eSPeeter Must *
8d3d1dd3eSPeeter Must * Redistribution and use in source and binary forms, with or without
9d3d1dd3eSPeeter Must * modification, are permitted provided that the following conditions
10d3d1dd3eSPeeter Must * are met:
11d3d1dd3eSPeeter Must * 1. Redistributions of source code must retain the above copyright
12d3d1dd3eSPeeter Must * notice, this list of conditions and the following disclaimer.
13d3d1dd3eSPeeter Must * 2. Redistributions in binary form must reproduce the above copyright
14d3d1dd3eSPeeter Must * notice, this list of conditions and the following disclaimer in the
15d3d1dd3eSPeeter Must * documentation and/or other materials provided with the distribution.
16d3d1dd3eSPeeter Must * 3. Neither the name of the University nor the names of its contributors
17d3d1dd3eSPeeter Must * may be used to endorse or promote products derived from this software
18d3d1dd3eSPeeter Must * without specific prior written permission.
19d3d1dd3eSPeeter Must *
20d3d1dd3eSPeeter Must * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21d3d1dd3eSPeeter Must * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22d3d1dd3eSPeeter Must * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23d3d1dd3eSPeeter Must * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24d3d1dd3eSPeeter Must * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25d3d1dd3eSPeeter Must * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26d3d1dd3eSPeeter Must * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27d3d1dd3eSPeeter Must * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28d3d1dd3eSPeeter Must * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29d3d1dd3eSPeeter Must * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30d3d1dd3eSPeeter Must * SUCH DAMAGE.
31d3d1dd3eSPeeter Must *
32d3d1dd3eSPeeter Must * Copyright (c) 2014 Spectra Logic Corporation
33d3d1dd3eSPeeter Must * All rights reserved.
34d3d1dd3eSPeeter Must *
35d3d1dd3eSPeeter Must * Redistribution and use in source and binary forms, with or without
36d3d1dd3eSPeeter Must * modification, are permitted provided that the following conditions
37d3d1dd3eSPeeter Must * are met:
38d3d1dd3eSPeeter Must * 1. Redistributions of source code must retain the above copyright
39d3d1dd3eSPeeter Must * notice, this list of conditions, and the following disclaimer,
40d3d1dd3eSPeeter Must * without modification.
41d3d1dd3eSPeeter Must * 2. Redistributions in binary form must reproduce at minimum a disclaimer
42d3d1dd3eSPeeter Must * substantially similar to the "NO WARRANTY" disclaimer below
43d3d1dd3eSPeeter Must * ("Disclaimer") and any redistribution must be conditioned upon
44d3d1dd3eSPeeter Must * including a substantially similar Disclaimer requirement for further
45d3d1dd3eSPeeter Must * binary redistribution.
46d3d1dd3eSPeeter Must *
47d3d1dd3eSPeeter Must * NO WARRANTY
48d3d1dd3eSPeeter Must * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
49d3d1dd3eSPeeter Must * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
50df052c2aSSascha Wildner * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
51d3d1dd3eSPeeter Must * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
52d3d1dd3eSPeeter Must * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
53d3d1dd3eSPeeter Must * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
54d3d1dd3eSPeeter Must * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
55d3d1dd3eSPeeter Must * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
56d3d1dd3eSPeeter Must * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
57d3d1dd3eSPeeter Must * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
58d3d1dd3eSPeeter Must * POSSIBILITY OF SUCH DAMAGES.
59d3d1dd3eSPeeter Must *
60d3d1dd3eSPeeter Must * $FreeBSD$
61d3d1dd3eSPeeter Must */
62d3d1dd3eSPeeter Must #ifndef _SYS_FREEBSD_BITSTRING_H_
63d3d1dd3eSPeeter Must #define _SYS_FREEBSD_BITSTRING_H_
64d3d1dd3eSPeeter Must
65d3d1dd3eSPeeter Must #include <sys/types.h>
66*a162a738SMichael Neumann #include <sys/malloc.h>
67d3d1dd3eSPeeter Must
68d3d1dd3eSPeeter Must /*
69d3d1dd3eSPeeter Must * Begin: Ad hoc definitions from FreeBSD sys/sys/types.h
70d3d1dd3eSPeeter Must */
71d3d1dd3eSPeeter Must
72d3d1dd3eSPeeter Must /*
73d3d1dd3eSPeeter Must * Population count algorithm using SWAR approach
74d3d1dd3eSPeeter Must * - "SIMD Within A Register".
75d3d1dd3eSPeeter Must */
76d3d1dd3eSPeeter Must static __inline __uint16_t
__bitcount16(__uint16_t _x)77d3d1dd3eSPeeter Must __bitcount16(__uint16_t _x)
78d3d1dd3eSPeeter Must {
79d3d1dd3eSPeeter Must
80d3d1dd3eSPeeter Must _x = (_x & 0x5555) + ((_x & 0xaaaa) >> 1);
81d3d1dd3eSPeeter Must _x = (_x & 0x3333) + ((_x & 0xcccc) >> 2);
82d3d1dd3eSPeeter Must _x = (_x + (_x >> 4)) & 0x0f0f;
83d3d1dd3eSPeeter Must _x = (_x + (_x >> 8)) & 0x00ff;
84d3d1dd3eSPeeter Must return (_x);
85d3d1dd3eSPeeter Must }
86d3d1dd3eSPeeter Must
87d3d1dd3eSPeeter Must static __inline __uint32_t
__bitcount32(__uint32_t _x)88d3d1dd3eSPeeter Must __bitcount32(__uint32_t _x)
89d3d1dd3eSPeeter Must {
90d3d1dd3eSPeeter Must
91d3d1dd3eSPeeter Must _x = (_x & 0x55555555) + ((_x & 0xaaaaaaaa) >> 1);
92d3d1dd3eSPeeter Must _x = (_x & 0x33333333) + ((_x & 0xcccccccc) >> 2);
93d3d1dd3eSPeeter Must _x = (_x + (_x >> 4)) & 0x0f0f0f0f;
94d3d1dd3eSPeeter Must _x = (_x + (_x >> 8));
95d3d1dd3eSPeeter Must _x = (_x + (_x >> 16)) & 0x000000ff;
96d3d1dd3eSPeeter Must return (_x);
97d3d1dd3eSPeeter Must }
98d3d1dd3eSPeeter Must
99d3d1dd3eSPeeter Must #ifdef __LP64__
100d3d1dd3eSPeeter Must static __inline __uint64_t
__bitcount64(__uint64_t _x)101d3d1dd3eSPeeter Must __bitcount64(__uint64_t _x)
102d3d1dd3eSPeeter Must {
103d3d1dd3eSPeeter Must
104d3d1dd3eSPeeter Must _x = (_x & 0x5555555555555555) + ((_x & 0xaaaaaaaaaaaaaaaa) >> 1);
105d3d1dd3eSPeeter Must _x = (_x & 0x3333333333333333) + ((_x & 0xcccccccccccccccc) >> 2);
106d3d1dd3eSPeeter Must _x = (_x + (_x >> 4)) & 0x0f0f0f0f0f0f0f0f;
107d3d1dd3eSPeeter Must _x = (_x + (_x >> 8));
108d3d1dd3eSPeeter Must _x = (_x + (_x >> 16));
109d3d1dd3eSPeeter Must _x = (_x + (_x >> 32)) & 0x000000ff;
110d3d1dd3eSPeeter Must return (_x);
111d3d1dd3eSPeeter Must }
112d3d1dd3eSPeeter Must
113d3d1dd3eSPeeter Must #define __bitcountl(x) __bitcount64((unsigned long)(x))
114d3d1dd3eSPeeter Must #else
115d3d1dd3eSPeeter Must static __inline __uint64_t
__bitcount64(__uint64_t _x)116d3d1dd3eSPeeter Must __bitcount64(__uint64_t _x)
117d3d1dd3eSPeeter Must {
118d3d1dd3eSPeeter Must
119d3d1dd3eSPeeter Must return (__bitcount32(_x >> 32) + __bitcount32(_x));
120d3d1dd3eSPeeter Must }
121d3d1dd3eSPeeter Must
122d3d1dd3eSPeeter Must #define __bitcountl(x) __bitcount32((unsigned long)(x))
123d3d1dd3eSPeeter Must #endif
124d3d1dd3eSPeeter Must #define __bitcount(x) __bitcount32((unsigned int)(x))
125d3d1dd3eSPeeter Must /*
126d3d1dd3eSPeeter Must * End: Ad hoc definitions from FreeBSD sys/sys/types.h
127d3d1dd3eSPeeter Must */
128d3d1dd3eSPeeter Must
129d3d1dd3eSPeeter Must typedef unsigned long bitstr_t;
130d3d1dd3eSPeeter Must
131d3d1dd3eSPeeter Must /*---------------------- Private Implementation Details ----------------------*/
132d3d1dd3eSPeeter Must #define _BITSTR_MASK (~0UL)
133d3d1dd3eSPeeter Must #define _BITSTR_BITS (sizeof(bitstr_t) * 8)
134d3d1dd3eSPeeter Must
135*a162a738SMichael Neumann /* round up x to the next multiple of y if y is a power of two */
136*a162a738SMichael Neumann #define _bit_roundup2(x, y) \
137*a162a738SMichael Neumann (((size_t)(x) + (y) - 1) & ~((size_t)(y) - 1))
138d3d1dd3eSPeeter Must
139d3d1dd3eSPeeter Must /* bitstr_t in bit string containing the bit. */
140*a162a738SMichael Neumann static inline size_t
_bit_idx(size_t _bit)141*a162a738SMichael Neumann _bit_idx(size_t _bit)
142d3d1dd3eSPeeter Must {
143d3d1dd3eSPeeter Must return (_bit / _BITSTR_BITS);
144d3d1dd3eSPeeter Must }
145d3d1dd3eSPeeter Must
146d3d1dd3eSPeeter Must /* bit number within bitstr_t at _bit_idx(_bit). */
147*a162a738SMichael Neumann static inline size_t
_bit_offset(size_t _bit)148*a162a738SMichael Neumann _bit_offset(size_t _bit)
149d3d1dd3eSPeeter Must {
150d3d1dd3eSPeeter Must return (_bit % _BITSTR_BITS);
151d3d1dd3eSPeeter Must }
152d3d1dd3eSPeeter Must
153d3d1dd3eSPeeter Must /* Mask for the bit within its long. */
154d3d1dd3eSPeeter Must static inline bitstr_t
_bit_mask(size_t _bit)155*a162a738SMichael Neumann _bit_mask(size_t _bit)
156d3d1dd3eSPeeter Must {
157d3d1dd3eSPeeter Must return (1UL << _bit_offset(_bit));
158d3d1dd3eSPeeter Must }
159d3d1dd3eSPeeter Must
160d3d1dd3eSPeeter Must static inline bitstr_t
_bit_make_mask(size_t _start,size_t _stop)161*a162a738SMichael Neumann _bit_make_mask(size_t _start, size_t _stop)
162d3d1dd3eSPeeter Must {
163d3d1dd3eSPeeter Must return ((_BITSTR_MASK << _bit_offset(_start)) &
164d3d1dd3eSPeeter Must (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1)));
165d3d1dd3eSPeeter Must }
166d3d1dd3eSPeeter Must
167d3d1dd3eSPeeter Must /*----------------------------- Public Interface -----------------------------*/
168d3d1dd3eSPeeter Must /* Number of bytes allocated for a bit string of nbits bits */
169*a162a738SMichael Neumann #define bitstr_size(_nbits) (_bit_roundup2((_nbits), _BITSTR_BITS) / 8)
170d3d1dd3eSPeeter Must
171d3d1dd3eSPeeter Must /* Allocate a bit string initialized with no bits set. */
172d3d1dd3eSPeeter Must #ifdef _KERNEL
173d3d1dd3eSPeeter Must static inline bitstr_t *
bit_alloc(size_t _nbits,struct malloc_type * type,int flags)174*a162a738SMichael Neumann bit_alloc(size_t _nbits, struct malloc_type *type, int flags)
175d3d1dd3eSPeeter Must {
176d3d1dd3eSPeeter Must return ((bitstr_t *)kmalloc(bitstr_size(_nbits), type, flags | M_ZERO));
177d3d1dd3eSPeeter Must }
178d3d1dd3eSPeeter Must #else
179d3d1dd3eSPeeter Must static inline bitstr_t *
bit_alloc(size_t _nbits)180*a162a738SMichael Neumann bit_alloc(size_t _nbits)
181d3d1dd3eSPeeter Must {
182d3d1dd3eSPeeter Must return ((bitstr_t *)calloc(bitstr_size(_nbits), 1));
183d3d1dd3eSPeeter Must }
184d3d1dd3eSPeeter Must #endif
185d3d1dd3eSPeeter Must
186d3d1dd3eSPeeter Must /* Allocate a bit string on the stack */
187d3d1dd3eSPeeter Must #define bit_decl(name, nbits) \
188d3d1dd3eSPeeter Must ((name)[bitstr_size(nbits) / sizeof(bitstr_t)])
189d3d1dd3eSPeeter Must
190d3d1dd3eSPeeter Must /* Is bit N of bit string set? */
191d3d1dd3eSPeeter Must static inline int
bit_test(const bitstr_t * _bitstr,size_t _bit)192*a162a738SMichael Neumann bit_test(const bitstr_t *_bitstr, size_t _bit)
193d3d1dd3eSPeeter Must {
194d3d1dd3eSPeeter Must return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0);
195d3d1dd3eSPeeter Must }
196d3d1dd3eSPeeter Must
197d3d1dd3eSPeeter Must /* Set bit N of bit string. */
198d3d1dd3eSPeeter Must static inline void
bit_set(bitstr_t * _bitstr,size_t _bit)199*a162a738SMichael Neumann bit_set(bitstr_t *_bitstr, size_t _bit)
200d3d1dd3eSPeeter Must {
201d3d1dd3eSPeeter Must _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit);
202d3d1dd3eSPeeter Must }
203d3d1dd3eSPeeter Must
204d3d1dd3eSPeeter Must /* clear bit N of bit string name */
205d3d1dd3eSPeeter Must static inline void
bit_clear(bitstr_t * _bitstr,size_t _bit)206*a162a738SMichael Neumann bit_clear(bitstr_t *_bitstr, size_t _bit)
207d3d1dd3eSPeeter Must {
208d3d1dd3eSPeeter Must _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
209d3d1dd3eSPeeter Must }
210d3d1dd3eSPeeter Must
211*a162a738SMichael Neumann /* Are bits in [start ... stop] in bit string all 0 or all 1? */
212*a162a738SMichael Neumann static inline int
bit_ntest(const bitstr_t * _bitstr,size_t _start,size_t _stop,int _match)213*a162a738SMichael Neumann bit_ntest(const bitstr_t *_bitstr, size_t _start, size_t _stop, int _match)
214*a162a738SMichael Neumann {
215*a162a738SMichael Neumann const bitstr_t *_stopbitstr;
216*a162a738SMichael Neumann bitstr_t _mask;
217*a162a738SMichael Neumann
218*a162a738SMichael Neumann _mask = (_match == 0) ? 0 : _BITSTR_MASK;
219*a162a738SMichael Neumann _stopbitstr = _bitstr + _bit_idx(_stop);
220*a162a738SMichael Neumann _bitstr += _bit_idx(_start);
221*a162a738SMichael Neumann
222*a162a738SMichael Neumann if (_bitstr == _stopbitstr)
223*a162a738SMichael Neumann return (0 == ((*_bitstr ^ _mask) &
224*a162a738SMichael Neumann _bit_make_mask(_start, _stop)));
225*a162a738SMichael Neumann if (_bit_offset(_start) != 0 &&
226*a162a738SMichael Neumann 0 != ((*_bitstr++ ^ _mask) &
227*a162a738SMichael Neumann _bit_make_mask(_start, _BITSTR_BITS - 1)))
228*a162a738SMichael Neumann return (0);
229*a162a738SMichael Neumann if (_bit_offset(_stop) == _BITSTR_BITS - 1)
230*a162a738SMichael Neumann ++_stopbitstr;
231*a162a738SMichael Neumann while (_bitstr < _stopbitstr) {
232*a162a738SMichael Neumann if (*_bitstr++ != _mask)
233*a162a738SMichael Neumann return (0);
234*a162a738SMichael Neumann }
235*a162a738SMichael Neumann return (_bit_offset(_stop) == _BITSTR_BITS - 1 ||
236*a162a738SMichael Neumann 0 == ((*_stopbitstr ^ _mask) & _bit_make_mask(0, _stop)));
237*a162a738SMichael Neumann }
238*a162a738SMichael Neumann
239d3d1dd3eSPeeter Must /* Set bits start ... stop inclusive in bit string. */
240d3d1dd3eSPeeter Must static inline void
bit_nset(bitstr_t * _bitstr,size_t _start,size_t _stop)241*a162a738SMichael Neumann bit_nset(bitstr_t *_bitstr, size_t _start, size_t _stop)
242d3d1dd3eSPeeter Must {
243d3d1dd3eSPeeter Must bitstr_t *_stopbitstr;
244d3d1dd3eSPeeter Must
245d3d1dd3eSPeeter Must _stopbitstr = _bitstr + _bit_idx(_stop);
246d3d1dd3eSPeeter Must _bitstr += _bit_idx(_start);
247d3d1dd3eSPeeter Must
248d3d1dd3eSPeeter Must if (_bitstr == _stopbitstr) {
249d3d1dd3eSPeeter Must *_bitstr |= _bit_make_mask(_start, _stop);
250d3d1dd3eSPeeter Must } else {
251*a162a738SMichael Neumann if (_bit_offset(_start) != 0)
252*a162a738SMichael Neumann *_bitstr++ |= _bit_make_mask(_start, _BITSTR_BITS - 1);
253*a162a738SMichael Neumann if (_bit_offset(_stop) == _BITSTR_BITS - 1)
254*a162a738SMichael Neumann ++_stopbitstr;
255*a162a738SMichael Neumann while (_bitstr < _stopbitstr)
256*a162a738SMichael Neumann *_bitstr++ = _BITSTR_MASK;
257*a162a738SMichael Neumann if (_bit_offset(_stop) != _BITSTR_BITS - 1)
258d3d1dd3eSPeeter Must *_stopbitstr |= _bit_make_mask(0, _stop);
259d3d1dd3eSPeeter Must }
260d3d1dd3eSPeeter Must }
261d3d1dd3eSPeeter Must
262d3d1dd3eSPeeter Must /* Clear bits start ... stop inclusive in bit string. */
263d3d1dd3eSPeeter Must static inline void
bit_nclear(bitstr_t * _bitstr,size_t _start,size_t _stop)264*a162a738SMichael Neumann bit_nclear(bitstr_t *_bitstr, size_t _start, size_t _stop)
265d3d1dd3eSPeeter Must {
266d3d1dd3eSPeeter Must bitstr_t *_stopbitstr;
267d3d1dd3eSPeeter Must
268d3d1dd3eSPeeter Must _stopbitstr = _bitstr + _bit_idx(_stop);
269d3d1dd3eSPeeter Must _bitstr += _bit_idx(_start);
270d3d1dd3eSPeeter Must
271d3d1dd3eSPeeter Must if (_bitstr == _stopbitstr) {
272d3d1dd3eSPeeter Must *_bitstr &= ~_bit_make_mask(_start, _stop);
273d3d1dd3eSPeeter Must } else {
274*a162a738SMichael Neumann if (_bit_offset(_start) != 0)
275*a162a738SMichael Neumann *_bitstr++ &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
276*a162a738SMichael Neumann if (_bit_offset(_stop) == _BITSTR_BITS - 1)
277*a162a738SMichael Neumann ++_stopbitstr;
278*a162a738SMichael Neumann while (_bitstr < _stopbitstr)
279*a162a738SMichael Neumann *_bitstr++ = 0;
280*a162a738SMichael Neumann if (_bit_offset(_stop) != _BITSTR_BITS - 1)
281d3d1dd3eSPeeter Must *_stopbitstr &= ~_bit_make_mask(0, _stop);
282d3d1dd3eSPeeter Must }
283d3d1dd3eSPeeter Must }
284d3d1dd3eSPeeter Must
285*a162a738SMichael Neumann /* Find the first '_match'-bit in bit string at or after bit start. */
286*a162a738SMichael Neumann static inline ssize_t
bit_ff_at_(bitstr_t * _bitstr,size_t _start,size_t _nbits,int _match)287*a162a738SMichael Neumann bit_ff_at_(bitstr_t *_bitstr, size_t _start, size_t _nbits, int _match)
288d3d1dd3eSPeeter Must {
289d3d1dd3eSPeeter Must bitstr_t *_curbitstr;
290d3d1dd3eSPeeter Must bitstr_t *_stopbitstr;
291*a162a738SMichael Neumann bitstr_t _mask;
292d3d1dd3eSPeeter Must bitstr_t _test;
293*a162a738SMichael Neumann ssize_t _value;
294d3d1dd3eSPeeter Must
295*a162a738SMichael Neumann if (_start >= _nbits || _nbits <= 0)
296*a162a738SMichael Neumann return (-1);
297*a162a738SMichael Neumann
298d3d1dd3eSPeeter Must _curbitstr = _bitstr + _bit_idx(_start);
299d3d1dd3eSPeeter Must _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
300*a162a738SMichael Neumann _mask = _match ? 0 : _BITSTR_MASK;
301d3d1dd3eSPeeter Must
302*a162a738SMichael Neumann _test = _mask ^ *_curbitstr;
303d3d1dd3eSPeeter Must if (_bit_offset(_start) != 0)
304d3d1dd3eSPeeter Must _test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
305d3d1dd3eSPeeter Must while (_test == 0 && _curbitstr < _stopbitstr)
306*a162a738SMichael Neumann _test = _mask ^ *(++_curbitstr);
307d3d1dd3eSPeeter Must
308*a162a738SMichael Neumann _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + ffsl(_test) - 1;
309*a162a738SMichael Neumann if (_test == 0 ||
310*a162a738SMichael Neumann (_bit_offset(_nbits) != 0 && (size_t)_value >= _nbits))
311d3d1dd3eSPeeter Must _value = -1;
312*a162a738SMichael Neumann return (_value);
313d3d1dd3eSPeeter Must }
314*a162a738SMichael Neumann #define bit_ff_at(_bitstr, _start, _nbits, _match, _resultp) \
315*a162a738SMichael Neumann *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), (_match))
316*a162a738SMichael Neumann
317*a162a738SMichael Neumann /* Find the first bit set in bit string at or after bit start. */
318*a162a738SMichael Neumann #define bit_ffs_at(_bitstr, _start, _nbits, _resultp) \
319*a162a738SMichael Neumann *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), 1)
320d3d1dd3eSPeeter Must
321d3d1dd3eSPeeter Must /* Find the first bit clear in bit string at or after bit start. */
322*a162a738SMichael Neumann #define bit_ffc_at(_bitstr, _start, _nbits, _resultp) \
323*a162a738SMichael Neumann *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), 0)
324d3d1dd3eSPeeter Must
325d3d1dd3eSPeeter Must /* Find the first bit set in bit string. */
326*a162a738SMichael Neumann #define bit_ffs(_bitstr, _nbits, _resultp) \
327*a162a738SMichael Neumann *(_resultp) = bit_ff_at_((_bitstr), 0, (_nbits), 1)
328d3d1dd3eSPeeter Must
329d3d1dd3eSPeeter Must /* Find the first bit clear in bit string. */
330*a162a738SMichael Neumann #define bit_ffc(_bitstr, _nbits, _resultp) \
331*a162a738SMichael Neumann *(_resultp) = bit_ff_at_((_bitstr), 0, (_nbits), 0)
332*a162a738SMichael Neumann
333*a162a738SMichael Neumann /* Find contiguous sequence of at least size '_match'-bits at or after start */
334*a162a738SMichael Neumann static inline ssize_t
bit_ff_area_at_(bitstr_t * _bitstr,size_t _start,size_t _nbits,size_t _size,int _match)335*a162a738SMichael Neumann bit_ff_area_at_(bitstr_t *_bitstr, size_t _start, size_t _nbits, size_t _size,
336*a162a738SMichael Neumann int _match)
337d3d1dd3eSPeeter Must {
338*a162a738SMichael Neumann bitstr_t *_curbitstr, _mask, _test;
339*a162a738SMichael Neumann size_t _last, _shft, _maxshft;
340*a162a738SMichael Neumann ssize_t _value;
341*a162a738SMichael Neumann
342*a162a738SMichael Neumann if (_start + _size > _nbits || _nbits <= 0)
343*a162a738SMichael Neumann return (-1);
344*a162a738SMichael Neumann
345*a162a738SMichael Neumann _mask = _match ? _BITSTR_MASK : 0;
346*a162a738SMichael Neumann _maxshft = _bit_idx(_size - 1) == 0 ? _size : (int)_BITSTR_BITS;
347*a162a738SMichael Neumann _value = _start;
348*a162a738SMichael Neumann _curbitstr = _bitstr + _bit_idx(_start);
349*a162a738SMichael Neumann _test = ~(_BITSTR_MASK << _bit_offset(_start));
350*a162a738SMichael Neumann for (_last = _size - 1, _test |= _mask ^ *_curbitstr;
351*a162a738SMichael Neumann !(_bit_idx(_last) == 0 &&
352*a162a738SMichael Neumann (_test & _bit_make_mask(0, _last)) == 0);
353*a162a738SMichael Neumann _last -= _BITSTR_BITS, _test = _mask ^ *++_curbitstr) {
354*a162a738SMichael Neumann if (_test == 0)
355*a162a738SMichael Neumann continue;
356*a162a738SMichael Neumann /* Shrink-left every 0-area in _test by maxshft-1 bits. */
357*a162a738SMichael Neumann for (_shft = _maxshft; _shft > 1 && (_test & (_test + 1)) != 0;
358*a162a738SMichael Neumann _shft = (_shft + 1) / 2)
359*a162a738SMichael Neumann _test |= _test >> _shft / 2;
360*a162a738SMichael Neumann /* Find the start of the first 0-area in _test. */
361*a162a738SMichael Neumann _last = ffsl(~(_test >> 1));
362*a162a738SMichael Neumann _value = (_curbitstr - _bitstr) * _BITSTR_BITS + _last;
363*a162a738SMichael Neumann /* If there's insufficient space left, give up. */
364*a162a738SMichael Neumann if (_value + _size > _nbits) {
365*a162a738SMichael Neumann _value = -1;
366*a162a738SMichael Neumann break;
367d3d1dd3eSPeeter Must }
368*a162a738SMichael Neumann _last += _size - 1;
369*a162a738SMichael Neumann /* If a solution is contained in _test, success! */
370*a162a738SMichael Neumann if (_bit_idx(_last) == 0)
371*a162a738SMichael Neumann break;
372*a162a738SMichael Neumann /* A solution here needs bits from the next word. */
373*a162a738SMichael Neumann }
374*a162a738SMichael Neumann return (_value);
375*a162a738SMichael Neumann }
376*a162a738SMichael Neumann #define bit_ff_area_at(_bitstr, _start, _nbits, _size, _match, _resultp) \
377*a162a738SMichael Neumann *(_resultp) = bit_ff_area_at_(_bitstr, _start, _nbits, _size, _match);
378*a162a738SMichael Neumann
379*a162a738SMichael Neumann /* Find contiguous sequence of at least size set bits at or after start */
380*a162a738SMichael Neumann #define bit_ffs_area_at(_bitstr, _start, _nbits, _size, _resultp) \
381*a162a738SMichael Neumann *(_resultp) = bit_ff_area_at_((_bitstr), (_start), (_nbits), (_size), 1)
382*a162a738SMichael Neumann
383*a162a738SMichael Neumann /* Find contiguous sequence of at least size cleared bits at or after start */
384*a162a738SMichael Neumann #define bit_ffc_area_at(_bitstr, _start, _nbits, _size, _resultp) \
385*a162a738SMichael Neumann *(_resultp) = bit_ff_area_at_((_bitstr), (_start), (_nbits), (_size), 0)
386*a162a738SMichael Neumann
387*a162a738SMichael Neumann /* Find contiguous sequence of at least size set bits in bit string */
388*a162a738SMichael Neumann #define bit_ffs_area(_bitstr, _nbits, _size, _resultp) \
389*a162a738SMichael Neumann *(_resultp) = bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 1)
390*a162a738SMichael Neumann
391*a162a738SMichael Neumann /* Find contiguous sequence of at least size cleared bits in bit string */
392*a162a738SMichael Neumann #define bit_ffc_area(_bitstr, _nbits, _size, _resultp) \
393*a162a738SMichael Neumann *(_resultp) = bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 0)
394d3d1dd3eSPeeter Must
395d3d1dd3eSPeeter Must /* Count the number of bits set in a bitstr of size _nbits at or after _start */
396*a162a738SMichael Neumann static inline ssize_t
bit_count_(bitstr_t * _bitstr,size_t _start,size_t _nbits)397*a162a738SMichael Neumann bit_count_(bitstr_t *_bitstr, size_t _start, size_t _nbits)
398d3d1dd3eSPeeter Must {
399d3d1dd3eSPeeter Must bitstr_t *_curbitstr, mask;
400*a162a738SMichael Neumann size_t curbitstr_len;
401*a162a738SMichael Neumann ssize_t _value = 0;
402d3d1dd3eSPeeter Must
403d3d1dd3eSPeeter Must if (_start >= _nbits)
404*a162a738SMichael Neumann return (0);
405d3d1dd3eSPeeter Must
406d3d1dd3eSPeeter Must _curbitstr = _bitstr + _bit_idx(_start);
407d3d1dd3eSPeeter Must _nbits -= _BITSTR_BITS * _bit_idx(_start);
408d3d1dd3eSPeeter Must _start -= _BITSTR_BITS * _bit_idx(_start);
409d3d1dd3eSPeeter Must
410d3d1dd3eSPeeter Must if (_start > 0) {
411d3d1dd3eSPeeter Must curbitstr_len = (int)_BITSTR_BITS < _nbits ?
412d3d1dd3eSPeeter Must (int)_BITSTR_BITS : _nbits;
413d3d1dd3eSPeeter Must mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1));
414d3d1dd3eSPeeter Must _value += __bitcountl(*_curbitstr & mask);
415d3d1dd3eSPeeter Must _curbitstr++;
416*a162a738SMichael Neumann if (_nbits < _BITSTR_BITS)
417*a162a738SMichael Neumann return (_value);
418d3d1dd3eSPeeter Must _nbits -= _BITSTR_BITS;
419d3d1dd3eSPeeter Must }
420d3d1dd3eSPeeter Must while (_nbits >= (int)_BITSTR_BITS) {
421d3d1dd3eSPeeter Must _value += __bitcountl(*_curbitstr);
422d3d1dd3eSPeeter Must _curbitstr++;
423d3d1dd3eSPeeter Must _nbits -= _BITSTR_BITS;
424d3d1dd3eSPeeter Must }
425d3d1dd3eSPeeter Must if (_nbits > 0) {
426d3d1dd3eSPeeter Must mask = _bit_make_mask(0, _bit_offset(_nbits - 1));
427d3d1dd3eSPeeter Must _value += __bitcountl(*_curbitstr & mask);
428d3d1dd3eSPeeter Must }
429d3d1dd3eSPeeter Must
430*a162a738SMichael Neumann return (_value);
431d3d1dd3eSPeeter Must }
432*a162a738SMichael Neumann #define bit_count(_bitstr, _start, _nbits, _resultp) \
433*a162a738SMichael Neumann *(_resultp) = bit_count_((_bitstr), (_start), (_nbits))
434*a162a738SMichael Neumann
435*a162a738SMichael Neumann /* Traverse all set bits, assigning each location in turn to iter */
436*a162a738SMichael Neumann #define bit_foreach_at(_bitstr, _start, _nbits, _iter) \
437*a162a738SMichael Neumann for ((_iter) = bit_ff_at_((_bitstr), (_start), (_nbits), 1); \
438*a162a738SMichael Neumann (_iter) != -1; \
439*a162a738SMichael Neumann (_iter) = bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 1))
440*a162a738SMichael Neumann #define bit_foreach(_bitstr, _nbits, _iter) \
441*a162a738SMichael Neumann bit_foreach_at(_bitstr, /*start*/0, _nbits, _iter)
442*a162a738SMichael Neumann
443*a162a738SMichael Neumann /* Traverse all unset bits, assigning each location in turn to iter */
444*a162a738SMichael Neumann #define bit_foreach_unset_at(_bitstr, _start, _nbits, _iter) \
445*a162a738SMichael Neumann for ((_iter) = bit_ff_at_((_bitstr), (_start), (_nbits), 0); \
446*a162a738SMichael Neumann (_iter) != -1; \
447*a162a738SMichael Neumann (_iter) = bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 0))
448*a162a738SMichael Neumann #define bit_foreach_unset(_bitstr, _nbits, _iter) \
449*a162a738SMichael Neumann bit_foreach_unset_at(_bitstr, /*start*/0, _nbits, _iter)
450d3d1dd3eSPeeter Must
451d3d1dd3eSPeeter Must #endif /* _SYS_FREEBSD_BITSTRING_H_ */
452