source: rtems-libbsd/freebsd/sys/sys/bitstring.h @ fb2aa6e

55-freebsd-126-freebsd-12
Last change on this file since fb2aa6e was fb2aa6e, checked in by Kevin Kirspel <kevin-kirspel@…>, on 05/17/17 at 12:40:32

Add bitcount inlinesfor RTEMS. These are found in FREEBSDs types.h

  • Property mode set to 100644
File size: 9.0 KB
Line 
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 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$
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#ifdef __rtems__
72#include <machine/bitstring.h>
73#endif /* __rtems__ */
74
75typedef unsigned long bitstr_t;
76
77/*---------------------- Private Implementation Details ----------------------*/
78#define _BITSTR_MASK (~0UL)
79#define _BITSTR_BITS (sizeof(bitstr_t) * 8)
80
81#ifdef roundup2
82#define        _bit_roundup2 roundup2
83#else
84#define        _bit_roundup2(x, y)        (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */
85#endif
86
87/* bitstr_t in bit string containing the bit. */
88static inline int
89_bit_idx(int _bit)
90{
91        return (_bit / _BITSTR_BITS);
92}
93
94/* bit number within bitstr_t at _bit_idx(_bit). */
95static inline int
96_bit_offset(int _bit)
97{
98        return (_bit % _BITSTR_BITS);
99}
100
101/* Mask for the bit within its long. */
102static inline bitstr_t
103_bit_mask(int _bit)
104{
105        return (1UL << _bit_offset(_bit));
106}
107
108static inline bitstr_t
109_bit_make_mask(int _start, int _stop)
110{
111        return ((_BITSTR_MASK << _bit_offset(_start)) &
112            (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1)));
113}
114
115/*----------------------------- Public Interface -----------------------------*/
116/* Number of bytes allocated for a bit string of nbits bits */
117#define bitstr_size(_nbits) (_bit_roundup2(_nbits, _BITSTR_BITS) / 8)
118
119/* Allocate a bit string initialized with no bits set. */
120#ifdef _KERNEL
121static inline bitstr_t *
122bit_alloc(int _nbits, struct malloc_type *type, int flags)
123{
124        return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO));
125}
126#else
127static inline bitstr_t *
128bit_alloc(int _nbits)
129{
130        return ((bitstr_t *)calloc(bitstr_size(_nbits), 1));
131}
132#endif
133
134/* Allocate a bit string on the stack */
135#define bit_decl(name, nbits) \
136        ((name)[bitstr_size(nbits) / sizeof(bitstr_t)])
137
138/* Is bit N of bit string set? */
139static inline int
140bit_test(const bitstr_t *_bitstr, int _bit)
141{
142        return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0);
143}
144
145/* Set bit N of bit string. */
146static inline void
147bit_set(bitstr_t *_bitstr, int _bit)
148{
149        _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit);
150}
151
152/* clear bit N of bit string name */
153static inline void
154bit_clear(bitstr_t *_bitstr, int _bit)
155{
156        _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
157}
158
159/* Set bits start ... stop inclusive in bit string. */
160static inline void
161bit_nset(bitstr_t *_bitstr, int _start, int _stop)
162{
163        bitstr_t *_stopbitstr;
164
165        _stopbitstr = _bitstr + _bit_idx(_stop);
166        _bitstr += _bit_idx(_start);
167
168        if (_bitstr == _stopbitstr) {
169                *_bitstr |= _bit_make_mask(_start, _stop);
170        } else {
171                *_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1);
172                while (++_bitstr < _stopbitstr)
173                        *_bitstr = _BITSTR_MASK;
174                *_stopbitstr |= _bit_make_mask(0, _stop);
175        }
176}
177
178/* Clear bits start ... stop inclusive in bit string. */
179static inline void
180bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
181{
182        bitstr_t *_stopbitstr;
183
184        _stopbitstr = _bitstr + _bit_idx(_stop);
185        _bitstr += _bit_idx(_start);
186
187        if (_bitstr == _stopbitstr) {
188                *_bitstr &= ~_bit_make_mask(_start, _stop);
189        } else {
190                *_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
191                while (++_bitstr < _stopbitstr)
192                        *_bitstr = 0;
193                *_stopbitstr &= ~_bit_make_mask(0, _stop);
194        }
195}
196
197/* Find the first bit set in bit string at or after bit start. */
198static inline void
199bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
200{
201        bitstr_t *_curbitstr;
202        bitstr_t *_stopbitstr;
203        bitstr_t _test;
204        int _value, _offset;
205
206        if (_nbits > 0) {
207                _curbitstr = _bitstr + _bit_idx(_start);
208                _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
209
210                _test = *_curbitstr;
211                if (_bit_offset(_start) != 0)
212                        _test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
213                while (_test == 0 && _curbitstr < _stopbitstr)
214                        _test = *(++_curbitstr);
215
216                _offset = ffsl(_test);
217                _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
218                if (_offset == 0 || _value >= _nbits)
219                        _value = -1;
220        } else {
221                _value = -1;
222        }
223        *_result = _value;
224}
225
226/* Find the first bit clear in bit string at or after bit start. */
227static inline void
228bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
229{
230        bitstr_t *_curbitstr;
231        bitstr_t *_stopbitstr;
232        bitstr_t _test;
233        int _value, _offset;
234
235        if (_nbits > 0) {
236                _curbitstr = _bitstr + _bit_idx(_start);
237                _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
238
239                _test = *_curbitstr;
240                if (_bit_offset(_start) != 0)
241                        _test |= _bit_make_mask(0, _start - 1);
242                while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr)
243                        _test = *(++_curbitstr);
244
245                _offset = ffsl(~_test);
246                _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
247                if (_offset == 0 || _value >= _nbits)
248                        _value = -1;
249        } else {
250                _value = -1;
251        }
252        *_result = _value;
253}
254
255/* Find the first bit set in bit string. */
256static inline void
257bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result)
258{
259        bit_ffs_at(_bitstr, /*start*/0, _nbits, _result);
260}
261
262/* Find the first bit clear in bit string. */
263static inline void
264bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result)
265{
266        bit_ffc_at(_bitstr, /*start*/0, _nbits, _result);
267}
268
269/* Count the number of bits set in a bitstr of size _nbits at or after _start */
270static inline void
271bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
272{
273        bitstr_t *_curbitstr, mask;
274        int _value = 0, curbitstr_len;
275
276        if (_start >= _nbits)
277                goto out;
278
279        _curbitstr = _bitstr + _bit_idx(_start);
280        _nbits -= _BITSTR_BITS * _bit_idx(_start);
281        _start -= _BITSTR_BITS * _bit_idx(_start);
282
283        if (_start > 0) {
284                curbitstr_len = (int)_BITSTR_BITS < _nbits ?
285                                (int)_BITSTR_BITS : _nbits;
286                mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1));
287                _value += __bitcountl(*_curbitstr & mask);
288                _curbitstr++;
289                _nbits -= _BITSTR_BITS;
290        }
291        while (_nbits >= (int)_BITSTR_BITS) {
292                _value += __bitcountl(*_curbitstr);
293                _curbitstr++;
294                _nbits -= _BITSTR_BITS;
295        }
296        if (_nbits > 0) {
297                mask = _bit_make_mask(0, _bit_offset(_nbits - 1));
298                _value += __bitcountl(*_curbitstr & mask);
299        }
300
301out:
302        *_result = _value;
303}
304
305#endif  /* _SYS_BITSTRING_H_ */
Note: See TracBrowser for help on using the repository browser.