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