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 * 3. 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 MERCHANTABILITY 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$
61 */
62 #ifndef _SYS_FREEBSD_BITSTRING_H_
63 #define _SYS_FREEBSD_BITSTRING_H_
64
65 #include <sys/types.h>
66 #include <sys/malloc.h>
67
68 /*
69 * Begin: Ad hoc definitions from FreeBSD sys/sys/types.h
70 */
71
72 /*
73 * Population count algorithm using SWAR approach
74 * - "SIMD Within A Register".
75 */
76 static __inline __uint16_t
__bitcount16(__uint16_t _x)77 __bitcount16(__uint16_t _x)
78 {
79
80 _x = (_x & 0x5555) + ((_x & 0xaaaa) >> 1);
81 _x = (_x & 0x3333) + ((_x & 0xcccc) >> 2);
82 _x = (_x + (_x >> 4)) & 0x0f0f;
83 _x = (_x + (_x >> 8)) & 0x00ff;
84 return (_x);
85 }
86
87 static __inline __uint32_t
__bitcount32(__uint32_t _x)88 __bitcount32(__uint32_t _x)
89 {
90
91 _x = (_x & 0x55555555) + ((_x & 0xaaaaaaaa) >> 1);
92 _x = (_x & 0x33333333) + ((_x & 0xcccccccc) >> 2);
93 _x = (_x + (_x >> 4)) & 0x0f0f0f0f;
94 _x = (_x + (_x >> 8));
95 _x = (_x + (_x >> 16)) & 0x000000ff;
96 return (_x);
97 }
98
99 #ifdef __LP64__
100 static __inline __uint64_t
__bitcount64(__uint64_t _x)101 __bitcount64(__uint64_t _x)
102 {
103
104 _x = (_x & 0x5555555555555555) + ((_x & 0xaaaaaaaaaaaaaaaa) >> 1);
105 _x = (_x & 0x3333333333333333) + ((_x & 0xcccccccccccccccc) >> 2);
106 _x = (_x + (_x >> 4)) & 0x0f0f0f0f0f0f0f0f;
107 _x = (_x + (_x >> 8));
108 _x = (_x + (_x >> 16));
109 _x = (_x + (_x >> 32)) & 0x000000ff;
110 return (_x);
111 }
112
113 #define __bitcountl(x) __bitcount64((unsigned long)(x))
114 #else
115 static __inline __uint64_t
__bitcount64(__uint64_t _x)116 __bitcount64(__uint64_t _x)
117 {
118
119 return (__bitcount32(_x >> 32) + __bitcount32(_x));
120 }
121
122 #define __bitcountl(x) __bitcount32((unsigned long)(x))
123 #endif
124 #define __bitcount(x) __bitcount32((unsigned int)(x))
125 /*
126 * End: Ad hoc definitions from FreeBSD sys/sys/types.h
127 */
128
129 typedef unsigned long bitstr_t;
130
131 /*---------------------- Private Implementation Details ----------------------*/
132 #define _BITSTR_MASK (~0UL)
133 #define _BITSTR_BITS (sizeof(bitstr_t) * 8)
134
135 /* round up x to the next multiple of y if y is a power of two */
136 #define _bit_roundup2(x, y) \
137 (((size_t)(x) + (y) - 1) & ~((size_t)(y) - 1))
138
139 /* bitstr_t in bit string containing the bit. */
140 static inline size_t
_bit_idx(size_t _bit)141 _bit_idx(size_t _bit)
142 {
143 return (_bit / _BITSTR_BITS);
144 }
145
146 /* bit number within bitstr_t at _bit_idx(_bit). */
147 static inline size_t
_bit_offset(size_t _bit)148 _bit_offset(size_t _bit)
149 {
150 return (_bit % _BITSTR_BITS);
151 }
152
153 /* Mask for the bit within its long. */
154 static inline bitstr_t
_bit_mask(size_t _bit)155 _bit_mask(size_t _bit)
156 {
157 return (1UL << _bit_offset(_bit));
158 }
159
160 static inline bitstr_t
_bit_make_mask(size_t _start,size_t _stop)161 _bit_make_mask(size_t _start, size_t _stop)
162 {
163 return ((_BITSTR_MASK << _bit_offset(_start)) &
164 (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1)));
165 }
166
167 /*----------------------------- Public Interface -----------------------------*/
168 /* Number of bytes allocated for a bit string of nbits bits */
169 #define bitstr_size(_nbits) (_bit_roundup2((_nbits), _BITSTR_BITS) / 8)
170
171 /* Allocate a bit string initialized with no bits set. */
172 #ifdef _KERNEL
173 static inline bitstr_t *
bit_alloc(size_t _nbits,struct malloc_type * type,int flags)174 bit_alloc(size_t _nbits, struct malloc_type *type, int flags)
175 {
176 return ((bitstr_t *)kmalloc(bitstr_size(_nbits), type, flags | M_ZERO));
177 }
178 #else
179 static inline bitstr_t *
bit_alloc(size_t _nbits)180 bit_alloc(size_t _nbits)
181 {
182 return ((bitstr_t *)calloc(bitstr_size(_nbits), 1));
183 }
184 #endif
185
186 /* Allocate a bit string on the stack */
187 #define bit_decl(name, nbits) \
188 ((name)[bitstr_size(nbits) / sizeof(bitstr_t)])
189
190 /* Is bit N of bit string set? */
191 static inline int
bit_test(const bitstr_t * _bitstr,size_t _bit)192 bit_test(const bitstr_t *_bitstr, size_t _bit)
193 {
194 return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0);
195 }
196
197 /* Set bit N of bit string. */
198 static inline void
bit_set(bitstr_t * _bitstr,size_t _bit)199 bit_set(bitstr_t *_bitstr, size_t _bit)
200 {
201 _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit);
202 }
203
204 /* clear bit N of bit string name */
205 static inline void
bit_clear(bitstr_t * _bitstr,size_t _bit)206 bit_clear(bitstr_t *_bitstr, size_t _bit)
207 {
208 _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
209 }
210
211 /* Are bits in [start ... stop] in bit string all 0 or all 1? */
212 static inline int
bit_ntest(const bitstr_t * _bitstr,size_t _start,size_t _stop,int _match)213 bit_ntest(const bitstr_t *_bitstr, size_t _start, size_t _stop, int _match)
214 {
215 const bitstr_t *_stopbitstr;
216 bitstr_t _mask;
217
218 _mask = (_match == 0) ? 0 : _BITSTR_MASK;
219 _stopbitstr = _bitstr + _bit_idx(_stop);
220 _bitstr += _bit_idx(_start);
221
222 if (_bitstr == _stopbitstr)
223 return (0 == ((*_bitstr ^ _mask) &
224 _bit_make_mask(_start, _stop)));
225 if (_bit_offset(_start) != 0 &&
226 0 != ((*_bitstr++ ^ _mask) &
227 _bit_make_mask(_start, _BITSTR_BITS - 1)))
228 return (0);
229 if (_bit_offset(_stop) == _BITSTR_BITS - 1)
230 ++_stopbitstr;
231 while (_bitstr < _stopbitstr) {
232 if (*_bitstr++ != _mask)
233 return (0);
234 }
235 return (_bit_offset(_stop) == _BITSTR_BITS - 1 ||
236 0 == ((*_stopbitstr ^ _mask) & _bit_make_mask(0, _stop)));
237 }
238
239 /* Set bits start ... stop inclusive in bit string. */
240 static inline void
bit_nset(bitstr_t * _bitstr,size_t _start,size_t _stop)241 bit_nset(bitstr_t *_bitstr, size_t _start, size_t _stop)
242 {
243 bitstr_t *_stopbitstr;
244
245 _stopbitstr = _bitstr + _bit_idx(_stop);
246 _bitstr += _bit_idx(_start);
247
248 if (_bitstr == _stopbitstr) {
249 *_bitstr |= _bit_make_mask(_start, _stop);
250 } else {
251 if (_bit_offset(_start) != 0)
252 *_bitstr++ |= _bit_make_mask(_start, _BITSTR_BITS - 1);
253 if (_bit_offset(_stop) == _BITSTR_BITS - 1)
254 ++_stopbitstr;
255 while (_bitstr < _stopbitstr)
256 *_bitstr++ = _BITSTR_MASK;
257 if (_bit_offset(_stop) != _BITSTR_BITS - 1)
258 *_stopbitstr |= _bit_make_mask(0, _stop);
259 }
260 }
261
262 /* Clear bits start ... stop inclusive in bit string. */
263 static inline void
bit_nclear(bitstr_t * _bitstr,size_t _start,size_t _stop)264 bit_nclear(bitstr_t *_bitstr, size_t _start, size_t _stop)
265 {
266 bitstr_t *_stopbitstr;
267
268 _stopbitstr = _bitstr + _bit_idx(_stop);
269 _bitstr += _bit_idx(_start);
270
271 if (_bitstr == _stopbitstr) {
272 *_bitstr &= ~_bit_make_mask(_start, _stop);
273 } else {
274 if (_bit_offset(_start) != 0)
275 *_bitstr++ &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
276 if (_bit_offset(_stop) == _BITSTR_BITS - 1)
277 ++_stopbitstr;
278 while (_bitstr < _stopbitstr)
279 *_bitstr++ = 0;
280 if (_bit_offset(_stop) != _BITSTR_BITS - 1)
281 *_stopbitstr &= ~_bit_make_mask(0, _stop);
282 }
283 }
284
285 /* Find the first '_match'-bit in bit string at or after bit start. */
286 static inline ssize_t
bit_ff_at_(bitstr_t * _bitstr,size_t _start,size_t _nbits,int _match)287 bit_ff_at_(bitstr_t *_bitstr, size_t _start, size_t _nbits, int _match)
288 {
289 bitstr_t *_curbitstr;
290 bitstr_t *_stopbitstr;
291 bitstr_t _mask;
292 bitstr_t _test;
293 ssize_t _value;
294
295 if (_start >= _nbits || _nbits <= 0)
296 return (-1);
297
298 _curbitstr = _bitstr + _bit_idx(_start);
299 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
300 _mask = _match ? 0 : _BITSTR_MASK;
301
302 _test = _mask ^ *_curbitstr;
303 if (_bit_offset(_start) != 0)
304 _test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
305 while (_test == 0 && _curbitstr < _stopbitstr)
306 _test = _mask ^ *(++_curbitstr);
307
308 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + ffsl(_test) - 1;
309 if (_test == 0 ||
310 (_bit_offset(_nbits) != 0 && (size_t)_value >= _nbits))
311 _value = -1;
312 return (_value);
313 }
314 #define bit_ff_at(_bitstr, _start, _nbits, _match, _resultp) \
315 *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), (_match))
316
317 /* Find the first bit set in bit string at or after bit start. */
318 #define bit_ffs_at(_bitstr, _start, _nbits, _resultp) \
319 *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), 1)
320
321 /* Find the first bit clear in bit string at or after bit start. */
322 #define bit_ffc_at(_bitstr, _start, _nbits, _resultp) \
323 *(_resultp) = bit_ff_at_((_bitstr), (_start), (_nbits), 0)
324
325 /* Find the first bit set in bit string. */
326 #define bit_ffs(_bitstr, _nbits, _resultp) \
327 *(_resultp) = bit_ff_at_((_bitstr), 0, (_nbits), 1)
328
329 /* Find the first bit clear in bit string. */
330 #define bit_ffc(_bitstr, _nbits, _resultp) \
331 *(_resultp) = bit_ff_at_((_bitstr), 0, (_nbits), 0)
332
333 /* Find contiguous sequence of at least size '_match'-bits at or after start */
334 static inline ssize_t
bit_ff_area_at_(bitstr_t * _bitstr,size_t _start,size_t _nbits,size_t _size,int _match)335 bit_ff_area_at_(bitstr_t *_bitstr, size_t _start, size_t _nbits, size_t _size,
336 int _match)
337 {
338 bitstr_t *_curbitstr, _mask, _test;
339 size_t _last, _shft, _maxshft;
340 ssize_t _value;
341
342 if (_start + _size > _nbits || _nbits <= 0)
343 return (-1);
344
345 _mask = _match ? _BITSTR_MASK : 0;
346 _maxshft = _bit_idx(_size - 1) == 0 ? _size : (int)_BITSTR_BITS;
347 _value = _start;
348 _curbitstr = _bitstr + _bit_idx(_start);
349 _test = ~(_BITSTR_MASK << _bit_offset(_start));
350 for (_last = _size - 1, _test |= _mask ^ *_curbitstr;
351 !(_bit_idx(_last) == 0 &&
352 (_test & _bit_make_mask(0, _last)) == 0);
353 _last -= _BITSTR_BITS, _test = _mask ^ *++_curbitstr) {
354 if (_test == 0)
355 continue;
356 /* Shrink-left every 0-area in _test by maxshft-1 bits. */
357 for (_shft = _maxshft; _shft > 1 && (_test & (_test + 1)) != 0;
358 _shft = (_shft + 1) / 2)
359 _test |= _test >> _shft / 2;
360 /* Find the start of the first 0-area in _test. */
361 _last = ffsl(~(_test >> 1));
362 _value = (_curbitstr - _bitstr) * _BITSTR_BITS + _last;
363 /* If there's insufficient space left, give up. */
364 if (_value + _size > _nbits) {
365 _value = -1;
366 break;
367 }
368 _last += _size - 1;
369 /* If a solution is contained in _test, success! */
370 if (_bit_idx(_last) == 0)
371 break;
372 /* A solution here needs bits from the next word. */
373 }
374 return (_value);
375 }
376 #define bit_ff_area_at(_bitstr, _start, _nbits, _size, _match, _resultp) \
377 *(_resultp) = bit_ff_area_at_(_bitstr, _start, _nbits, _size, _match);
378
379 /* Find contiguous sequence of at least size set bits at or after start */
380 #define bit_ffs_area_at(_bitstr, _start, _nbits, _size, _resultp) \
381 *(_resultp) = bit_ff_area_at_((_bitstr), (_start), (_nbits), (_size), 1)
382
383 /* Find contiguous sequence of at least size cleared bits at or after start */
384 #define bit_ffc_area_at(_bitstr, _start, _nbits, _size, _resultp) \
385 *(_resultp) = bit_ff_area_at_((_bitstr), (_start), (_nbits), (_size), 0)
386
387 /* Find contiguous sequence of at least size set bits in bit string */
388 #define bit_ffs_area(_bitstr, _nbits, _size, _resultp) \
389 *(_resultp) = bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 1)
390
391 /* Find contiguous sequence of at least size cleared bits in bit string */
392 #define bit_ffc_area(_bitstr, _nbits, _size, _resultp) \
393 *(_resultp) = bit_ff_area_at_((_bitstr), 0, (_nbits), (_size), 0)
394
395 /* Count the number of bits set in a bitstr of size _nbits at or after _start */
396 static inline ssize_t
bit_count_(bitstr_t * _bitstr,size_t _start,size_t _nbits)397 bit_count_(bitstr_t *_bitstr, size_t _start, size_t _nbits)
398 {
399 bitstr_t *_curbitstr, mask;
400 size_t curbitstr_len;
401 ssize_t _value = 0;
402
403 if (_start >= _nbits)
404 return (0);
405
406 _curbitstr = _bitstr + _bit_idx(_start);
407 _nbits -= _BITSTR_BITS * _bit_idx(_start);
408 _start -= _BITSTR_BITS * _bit_idx(_start);
409
410 if (_start > 0) {
411 curbitstr_len = (int)_BITSTR_BITS < _nbits ?
412 (int)_BITSTR_BITS : _nbits;
413 mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1));
414 _value += __bitcountl(*_curbitstr & mask);
415 _curbitstr++;
416 if (_nbits < _BITSTR_BITS)
417 return (_value);
418 _nbits -= _BITSTR_BITS;
419 }
420 while (_nbits >= (int)_BITSTR_BITS) {
421 _value += __bitcountl(*_curbitstr);
422 _curbitstr++;
423 _nbits -= _BITSTR_BITS;
424 }
425 if (_nbits > 0) {
426 mask = _bit_make_mask(0, _bit_offset(_nbits - 1));
427 _value += __bitcountl(*_curbitstr & mask);
428 }
429
430 return (_value);
431 }
432 #define bit_count(_bitstr, _start, _nbits, _resultp) \
433 *(_resultp) = bit_count_((_bitstr), (_start), (_nbits))
434
435 /* Traverse all set bits, assigning each location in turn to iter */
436 #define bit_foreach_at(_bitstr, _start, _nbits, _iter) \
437 for ((_iter) = bit_ff_at_((_bitstr), (_start), (_nbits), 1); \
438 (_iter) != -1; \
439 (_iter) = bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 1))
440 #define bit_foreach(_bitstr, _nbits, _iter) \
441 bit_foreach_at(_bitstr, /*start*/0, _nbits, _iter)
442
443 /* Traverse all unset bits, assigning each location in turn to iter */
444 #define bit_foreach_unset_at(_bitstr, _start, _nbits, _iter) \
445 for ((_iter) = bit_ff_at_((_bitstr), (_start), (_nbits), 0); \
446 (_iter) != -1; \
447 (_iter) = bit_ff_at_((_bitstr), (_iter) + 1, (_nbits), 0))
448 #define bit_foreach_unset(_bitstr, _nbits, _iter) \
449 bit_foreach_unset_at(_bitstr, /*start*/0, _nbits, _iter)
450
451 #endif /* _SYS_FREEBSD_BITSTRING_H_ */
452