FreeBSD/Linux Kernel Cross Reference
sys/sys/bitstring.h
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 * $FreeBSD$
63 */
64 #ifndef _SYS_BITSTRING_H_
65 #define _SYS_BITSTRING_H_
66
67 #ifdef _KERNEL
68 #include <sys/libkern.h>
69 #include <sys/malloc.h>
70 #endif
71
72 #include <sys/types.h>
73
74 typedef unsigned long bitstr_t;
75
76 /*---------------------- Private Implementation Details ----------------------*/
77 #define _BITSTR_MASK (~0UL)
78 #define _BITSTR_BITS (sizeof(bitstr_t) * 8)
79
80 #ifdef roundup2
81 #define _bit_roundup2 roundup2
82 #else
83 #define _bit_roundup2(x, y) (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */
84 #endif
85
86 /* bitstr_t in bit string containing the bit. */
87 static inline int
88 _bit_idx(int _bit)
89 {
90 return (_bit / _BITSTR_BITS);
91 }
92
93 /* bit number within bitstr_t at _bit_idx(_bit). */
94 static inline int
95 _bit_offset(int _bit)
96 {
97 return (_bit % _BITSTR_BITS);
98 }
99
100 /* Mask for the bit within its long. */
101 static inline bitstr_t
102 _bit_mask(int _bit)
103 {
104 return (1UL << _bit_offset(_bit));
105 }
106
107 static inline bitstr_t
108 _bit_make_mask(int _start, int _stop)
109 {
110 return ((_BITSTR_MASK << _bit_offset(_start)) &
111 (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1)));
112 }
113
114 /*----------------------------- Public Interface -----------------------------*/
115 /* Number of bytes allocated for a bit string of nbits bits */
116 #define bitstr_size(_nbits) (_bit_roundup2(_nbits, _BITSTR_BITS) / 8)
117
118 /* Allocate a bit string initialized with no bits set. */
119 #ifdef _KERNEL
120 static inline bitstr_t *
121 bit_alloc(int _nbits, struct malloc_type *type, int flags)
122 {
123 return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO));
124 }
125 #else
126 static inline bitstr_t *
127 bit_alloc(int _nbits)
128 {
129 return ((bitstr_t *)calloc(bitstr_size(_nbits), 1));
130 }
131 #endif
132
133 /* Allocate a bit string on the stack */
134 #define bit_decl(name, nbits) \
135 ((name)[bitstr_size(nbits) / sizeof(bitstr_t)])
136
137 /* Is bit N of bit string set? */
138 static inline int
139 bit_test(const bitstr_t *_bitstr, int _bit)
140 {
141 return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0);
142 }
143
144 /* Set bit N of bit string. */
145 static inline void
146 bit_set(bitstr_t *_bitstr, int _bit)
147 {
148 _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit);
149 }
150
151 /* clear bit N of bit string name */
152 static inline void
153 bit_clear(bitstr_t *_bitstr, int _bit)
154 {
155 _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
156 }
157
158 /* Set bits start ... stop inclusive in bit string. */
159 static inline void
160 bit_nset(bitstr_t *_bitstr, int _start, int _stop)
161 {
162 bitstr_t *_stopbitstr;
163
164 _stopbitstr = _bitstr + _bit_idx(_stop);
165 _bitstr += _bit_idx(_start);
166
167 if (_bitstr == _stopbitstr) {
168 *_bitstr |= _bit_make_mask(_start, _stop);
169 } else {
170 *_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1);
171 while (++_bitstr < _stopbitstr)
172 *_bitstr = _BITSTR_MASK;
173 *_stopbitstr |= _bit_make_mask(0, _stop);
174 }
175 }
176
177 /* Clear bits start ... stop inclusive in bit string. */
178 static inline void
179 bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
180 {
181 bitstr_t *_stopbitstr;
182
183 _stopbitstr = _bitstr + _bit_idx(_stop);
184 _bitstr += _bit_idx(_start);
185
186 if (_bitstr == _stopbitstr) {
187 *_bitstr &= ~_bit_make_mask(_start, _stop);
188 } else {
189 *_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
190 while (++_bitstr < _stopbitstr)
191 *_bitstr = 0;
192 *_stopbitstr &= ~_bit_make_mask(0, _stop);
193 }
194 }
195
196 /* Find the first bit set in bit string at or after bit start. */
197 static inline void
198 bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
199 {
200 bitstr_t *_curbitstr;
201 bitstr_t *_stopbitstr;
202 bitstr_t _test;
203 int _value, _offset;
204
205 if (_start >= _nbits) {
206 *_result = -1;
207 return;
208 }
209
210 if (_nbits > 0) {
211 _curbitstr = _bitstr + _bit_idx(_start);
212 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
213
214 _test = *_curbitstr;
215 if (_bit_offset(_start) != 0)
216 _test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
217 while (_test == 0 && _curbitstr < _stopbitstr)
218 _test = *(++_curbitstr);
219
220 _offset = ffsl(_test);
221 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
222 if (_offset == 0 || _value >= _nbits)
223 _value = -1;
224 } else {
225 _value = -1;
226 }
227 *_result = _value;
228 }
229
230 /* Find the first bit clear in bit string at or after bit start. */
231 static inline void
232 bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
233 {
234 bitstr_t *_curbitstr;
235 bitstr_t *_stopbitstr;
236 bitstr_t _test;
237 int _value, _offset;
238
239 if (_start >= _nbits) {
240 *_result = -1;
241 return;
242 }
243
244 if (_nbits > 0) {
245 _curbitstr = _bitstr + _bit_idx(_start);
246 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
247
248 _test = *_curbitstr;
249 if (_bit_offset(_start) != 0)
250 _test |= _bit_make_mask(0, _start - 1);
251 while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr)
252 _test = *(++_curbitstr);
253
254 _offset = ffsl(~_test);
255 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
256 if (_offset == 0 || _value >= _nbits)
257 _value = -1;
258 } else {
259 _value = -1;
260 }
261 *_result = _value;
262 }
263
264 /* Find the first bit set in bit string. */
265 static inline void
266 bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result)
267 {
268 bit_ffs_at(_bitstr, /*start*/0, _nbits, _result);
269 }
270
271 /* Find the first bit clear in bit string. */
272 static inline void
273 bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result)
274 {
275 bit_ffc_at(_bitstr, /*start*/0, _nbits, _result);
276 }
277
278 /* Find contiguous sequence of at least size set bits at or after start */
279 static inline void
280 bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
281 int *_result)
282 {
283 bitstr_t *_curbitstr;
284 bitstr_t _test;
285 int _value, _offset, _logsize, _b;
286
287 if (_start + _size > _nbits || _nbits <= 0) {
288 *_result = -1;
289 return;
290 }
291
292 _logsize = fls(_size - 1);
293 _value = _start;
294 _curbitstr = _bitstr + _bit_idx(_start);
295 _test = ~*_curbitstr;
296 if (_bit_offset(_start) != 0)
297 _test |= _bit_make_mask(0, _start - 1);
298 for (_offset = 0;; _offset -= _BITSTR_BITS, _test = ~*++_curbitstr) {
299 if (_test != 0) {
300 /* If leading 0s in _test can finish 0-area, stop. */
301 if (_offset + _size < (int)_BITSTR_BITS &&
302 (_test & _bit_make_mask(0, _offset + _size)) == 0)
303 break;
304 /* Shrink-left every 0-area in _test by size-1 bits. */
305 _b = _logsize;
306 while ((_test & (_test + 1)) != 0 && _b-- > 0)
307 _test |= _test >> (((_size - 1) >> _b) + 1) / 2;
308 /* Find the start of the first 0-area in _test. */
309 _offset = (~_test == 0) ? (int)_BITSTR_BITS :
310 ffsl(~_test) - 1;
311 _value = (_curbitstr - _bitstr) * _BITSTR_BITS +
312 _offset;
313 /* If there's insufficient space left, give up. */
314 if (_value + _size > _nbits) {
315 _value = -1;
316 break;
317 }
318 }
319 if (_offset + _size <= (int)_BITSTR_BITS)
320 break;
321 }
322 *_result = _value;
323 }
324
325 /* Find contiguous sequence of at least size cleared bits at or after start */
326 static inline void
327 bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
328 int *_result)
329 {
330 bitstr_t *_curbitstr;
331 bitstr_t _test;
332 int _value, _offset, _logsize, _b;
333
334 if (_start + _size > _nbits || _nbits <= 0) {
335 *_result = -1;
336 return;
337 }
338
339 _logsize = fls(_size - 1);
340 _value = _start;
341 _curbitstr = _bitstr + _bit_idx(_start);
342 _test = *_curbitstr;
343 if (_bit_offset(_start) != 0)
344 _test |= _bit_make_mask(0, _start - 1);
345 for (_offset = 0;; _offset -= _BITSTR_BITS, _test = *++_curbitstr) {
346 if (_test != 0) {
347 /* If leading 0s in _test can finish 0-area, stop. */
348 if (_offset + _size < (int)_BITSTR_BITS &&
349 (_test & _bit_make_mask(0, _offset + _size)) == 0)
350 break;
351 /* Shrink-left every 0-area in _test by size-1 bits. */
352 _b = _logsize;
353 while ((_test & (_test + 1)) != 0 && _b-- > 0)
354 _test |= _test >> (((_size - 1) >> _b) + 1) / 2;
355 /* Find the start of the first 0-area in _test. */
356 _offset = (~_test == 0) ? (int)_BITSTR_BITS :
357 ffsl(~_test) - 1;
358 _value = (_curbitstr - _bitstr) * _BITSTR_BITS +
359 _offset;
360 /* If there's insufficient space left, give up. */
361 if (_value + _size > _nbits) {
362 _value = -1;
363 break;
364 }
365 }
366 if (_offset + _size <= (int)_BITSTR_BITS)
367 break;
368 }
369 *_result = _value;
370 }
371
372 /* Find contiguous sequence of at least size set bits in bit string */
373 static inline void
374 bit_ffs_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
375 {
376 bit_ffs_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
377 }
378
379 /* Find contiguous sequence of at least size cleared bits in bit string */
380 static inline void
381 bit_ffc_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
382 {
383 bit_ffc_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
384 }
385
386 /* Count the number of bits set in a bitstr of size _nbits at or after _start */
387 static inline void
388 bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
389 {
390 bitstr_t *_curbitstr, mask;
391 int _value = 0, curbitstr_len;
392
393 if (_start >= _nbits)
394 goto out;
395
396 _curbitstr = _bitstr + _bit_idx(_start);
397 _nbits -= _BITSTR_BITS * _bit_idx(_start);
398 _start -= _BITSTR_BITS * _bit_idx(_start);
399
400 if (_start > 0) {
401 curbitstr_len = (int)_BITSTR_BITS < _nbits ?
402 (int)_BITSTR_BITS : _nbits;
403 mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1));
404 _value += __bitcountl(*_curbitstr & mask);
405 _curbitstr++;
406 _nbits -= _BITSTR_BITS;
407 }
408 while (_nbits >= (int)_BITSTR_BITS) {
409 _value += __bitcountl(*_curbitstr);
410 _curbitstr++;
411 _nbits -= _BITSTR_BITS;
412 }
413 if (_nbits > 0) {
414 mask = _bit_make_mask(0, _bit_offset(_nbits - 1));
415 _value += __bitcountl(*_curbitstr & mask);
416 }
417
418 out:
419 *_result = _value;
420 }
421
422 #endif /* _SYS_BITSTRING_H_ */
Cache object: 788f1dda6e0524976745db2f5402bd50
|