1 /*        $NetBSD: bitops.h,v 1.16 2024/05/12 10:34:56 rillig Exp $   */
2 
3 /*-
4  * Copyright (c) 2007, 2010 The NetBSD Foundation, Inc.
5  * All rights reserved.
6  *
7  * This code is derived from software contributed to The NetBSD Foundation
8  * by Christos Zoulas and Joerg Sonnenberger.
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  *
19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29  * POSSIBILITY OF SUCH DAMAGE.
30  */
31 #ifndef _SYS_BITOPS_H_
32 #define _SYS_BITOPS_H_
33 
34 #include <sys/stdint.h>
35 
36 /*
37  * Find First Set functions
38  */
39 #ifndef ffs32
40 static __inline int __unused
ffs32(uint32_t _n)41 ffs32(uint32_t _n)
42 {
43           int _v;
44 
45           if (!_n)
46                     return 0;
47 
48           _v = 1;
49           if ((_n & 0x0000FFFFU) == 0) {
50                     _n >>= 16;
51                     _v += 16;
52           }
53           if ((_n & 0x000000FFU) == 0) {
54                     _n >>= 8;
55                     _v += 8;
56           }
57           if ((_n & 0x0000000FU) == 0) {
58                     _n >>= 4;
59                     _v += 4;
60           }
61           if ((_n & 0x00000003U) == 0) {
62                     _n >>= 2;
63                     _v += 2;
64           }
65           if ((_n & 0x00000001U) == 0) {
66                     _n >>= 1;
67                     _v += 1;
68           }
69           return _v;
70 }
71 #endif
72 
73 #ifndef ffs64
74 static __inline int __unused
ffs64(uint64_t _n)75 ffs64(uint64_t _n)
76 {
77           int _v;
78 
79           if (!_n)
80                     return 0;
81 
82           _v = 1;
83           if ((_n & 0x00000000FFFFFFFFULL) == 0) {
84                     _n >>= 32;
85                     _v += 32;
86           }
87           if ((_n & 0x000000000000FFFFULL) == 0) {
88                     _n >>= 16;
89                     _v += 16;
90           }
91           if ((_n & 0x00000000000000FFULL) == 0) {
92                     _n >>= 8;
93                     _v += 8;
94           }
95           if ((_n & 0x000000000000000FULL) == 0) {
96                     _n >>= 4;
97                     _v += 4;
98           }
99           if ((_n & 0x0000000000000003ULL) == 0) {
100                     _n >>= 2;
101                     _v += 2;
102           }
103           if ((_n & 0x0000000000000001ULL) == 0) {
104                     _n >>= 1;
105                     _v += 1;
106           }
107           return _v;
108 }
109 #endif
110 
111 /*
112  * Find Last Set functions
113  */
114 #ifndef fls32
115 static __inline int __unused
fls32(uint32_t _n)116 fls32(uint32_t _n)
117 {
118           int _v;
119 
120           if (!_n)
121                     return 0;
122 
123           _v = 32;
124           if ((_n & 0xFFFF0000U) == 0) {
125                     _n <<= 16;
126                     _v -= 16;
127           }
128           if ((_n & 0xFF000000U) == 0) {
129                     _n <<= 8;
130                     _v -= 8;
131           }
132           if ((_n & 0xF0000000U) == 0) {
133                     _n <<= 4;
134                     _v -= 4;
135           }
136           if ((_n & 0xC0000000U) == 0) {
137                     _n <<= 2;
138                     _v -= 2;
139           }
140           if ((_n & 0x80000000U) == 0) {
141                     _n <<= 1;
142                     _v -= 1;
143           }
144           return _v;
145 }
146 #endif
147 
148 #ifndef fls64
149 static __inline int __unused
fls64(uint64_t _n)150 fls64(uint64_t _n)
151 {
152           int _v;
153 
154           if (!_n)
155                     return 0;
156 
157           _v = 64;
158           if ((_n & 0xFFFFFFFF00000000ULL) == 0) {
159                     _n <<= 32;
160                     _v -= 32;
161           }
162           if ((_n & 0xFFFF000000000000ULL) == 0) {
163                     _n <<= 16;
164                     _v -= 16;
165           }
166           if ((_n & 0xFF00000000000000ULL) == 0) {
167                     _n <<= 8;
168                     _v -= 8;
169           }
170           if ((_n & 0xF000000000000000ULL) == 0) {
171                     _n <<= 4;
172                     _v -= 4;
173           }
174           if ((_n & 0xC000000000000000ULL) == 0) {
175                     _n <<= 2;
176                     _v -= 2;
177           }
178           if ((_n & 0x8000000000000000ULL) == 0) {
179                     _n <<= 1;
180                     _v -= 1;
181           }
182           return _v;
183 }
184 #endif
185 
186 /*
187  * Integer logarithm, returns -1 on error. Inspired by the linux
188  * version written by David Howells.
189  */
190 #define _ilog2_helper(_n, _x) ((_n) & (1ULL << (_x))) ? _x :
191 #define _ilog2_const(_n) ( \
192           _ilog2_helper(_n, 63) \
193           _ilog2_helper(_n, 62) \
194           _ilog2_helper(_n, 61) \
195           _ilog2_helper(_n, 60) \
196           _ilog2_helper(_n, 59) \
197           _ilog2_helper(_n, 58) \
198           _ilog2_helper(_n, 57) \
199           _ilog2_helper(_n, 56) \
200           _ilog2_helper(_n, 55) \
201           _ilog2_helper(_n, 54) \
202           _ilog2_helper(_n, 53) \
203           _ilog2_helper(_n, 52) \
204           _ilog2_helper(_n, 51) \
205           _ilog2_helper(_n, 50) \
206           _ilog2_helper(_n, 49) \
207           _ilog2_helper(_n, 48) \
208           _ilog2_helper(_n, 47) \
209           _ilog2_helper(_n, 46) \
210           _ilog2_helper(_n, 45) \
211           _ilog2_helper(_n, 44) \
212           _ilog2_helper(_n, 43) \
213           _ilog2_helper(_n, 42) \
214           _ilog2_helper(_n, 41) \
215           _ilog2_helper(_n, 40) \
216           _ilog2_helper(_n, 39) \
217           _ilog2_helper(_n, 38) \
218           _ilog2_helper(_n, 37) \
219           _ilog2_helper(_n, 36) \
220           _ilog2_helper(_n, 35) \
221           _ilog2_helper(_n, 34) \
222           _ilog2_helper(_n, 33) \
223           _ilog2_helper(_n, 32) \
224           _ilog2_helper(_n, 31) \
225           _ilog2_helper(_n, 30) \
226           _ilog2_helper(_n, 29) \
227           _ilog2_helper(_n, 28) \
228           _ilog2_helper(_n, 27) \
229           _ilog2_helper(_n, 26) \
230           _ilog2_helper(_n, 25) \
231           _ilog2_helper(_n, 24) \
232           _ilog2_helper(_n, 23) \
233           _ilog2_helper(_n, 22) \
234           _ilog2_helper(_n, 21) \
235           _ilog2_helper(_n, 20) \
236           _ilog2_helper(_n, 19) \
237           _ilog2_helper(_n, 18) \
238           _ilog2_helper(_n, 17) \
239           _ilog2_helper(_n, 16) \
240           _ilog2_helper(_n, 15) \
241           _ilog2_helper(_n, 14) \
242           _ilog2_helper(_n, 13) \
243           _ilog2_helper(_n, 12) \
244           _ilog2_helper(_n, 11) \
245           _ilog2_helper(_n, 10) \
246           _ilog2_helper(_n,  9) \
247           _ilog2_helper(_n,  8) \
248           _ilog2_helper(_n,  7) \
249           _ilog2_helper(_n,  6) \
250           _ilog2_helper(_n,  5) \
251           _ilog2_helper(_n,  4) \
252           _ilog2_helper(_n,  3) \
253           _ilog2_helper(_n,  2) \
254           _ilog2_helper(_n,  1) \
255           _ilog2_helper(_n,  0) \
256           -1)
257 
258 #define ilog2(_n) \
259 ( \
260           __builtin_constant_p(_n) ?  _ilog2_const(_n) : \
261           ((sizeof(_n) > 4 ? fls64(_n) : fls32(_n)) - 1) \
262 )
263 
264 static __inline void
fast_divide32_prepare(uint32_t _div,uint32_t * __restrict _m,uint8_t * __restrict _s1,uint8_t * __restrict _s2)265 fast_divide32_prepare(uint32_t _div, uint32_t * __restrict _m,
266     uint8_t *__restrict _s1, uint8_t *__restrict _s2)
267 {
268           uint64_t _mt;
269           int _l;
270 
271           _l = fls32(_div - 1);
272           _mt = (uint64_t)(0x100000000ULL * ((1ULL << _l) - _div));
273           *_m = (uint32_t)(_mt / _div + 1);
274           *_s1 = (_l > 1) ? 1U : (uint8_t)_l;
275           *_s2 = (_l == 0) ? 0 : (uint8_t)(_l - 1);
276 }
277 
278 /* ARGSUSED */
279 static __inline uint32_t
fast_divide32(uint32_t _v,uint32_t _div __unused,uint32_t _m,uint8_t _s1,uint8_t _s2)280 fast_divide32(uint32_t _v, uint32_t _div __unused, uint32_t _m, uint8_t _s1,
281     uint8_t _s2)
282 {
283           uint32_t _t;
284 
285           _t = (uint32_t)(((uint64_t)_v * _m) >> 32);
286           return (_t + ((_v - _t) >> _s1)) >> _s2;
287 }
288 
289 static __inline uint32_t
fast_remainder32(uint32_t _v,uint32_t _div,uint32_t _m,uint8_t _s1,uint8_t _s2)290 fast_remainder32(uint32_t _v, uint32_t _div, uint32_t _m, uint8_t _s1,
291     uint8_t _s2)
292 {
293 
294           return _v - _div * fast_divide32(_v, _div, _m, _s1, _s2);
295 }
296 
297 #define __BITMAP_TYPE(__s, __t, __n) struct __s { \
298     __t _b[__BITMAP_SIZE(__t, __n)]; \
299 }
300 
301 #define __BITMAP_BITS(__t)              (sizeof(__t) * NBBY)
302 #define __BITMAP_SHIFT(__t)             (ilog2(__BITMAP_BITS(__t)))
303 #define __BITMAP_MASK(__t)              (__BITMAP_BITS(__t) - 1)
304 #define __BITMAP_SIZE(__t, __n) \
305     (((__n) + (__BITMAP_BITS(__t) - 1)) / __BITMAP_BITS(__t))
306 #define __BITMAP_BIT(__n, __v) \
307     ((__typeof__((__v)->_b[0]))1 << ((__n) & __BITMAP_MASK(*(__v)->_b)))
308 #define __BITMAP_WORD(__n, __v) \
309     ((__n) >> __BITMAP_SHIFT(*(__v)->_b))
310 
311 #define __BITMAP_SET(__n, __v) \
312     ((__v)->_b[__BITMAP_WORD(__n, __v)] |= __BITMAP_BIT(__n, __v))
313 #define __BITMAP_CLR(__n, __v) \
314     ((__v)->_b[__BITMAP_WORD(__n, __v)] &= ~__BITMAP_BIT(__n, __v))
315 #define __BITMAP_ISSET(__n, __v) \
316     ((__v)->_b[__BITMAP_WORD(__n, __v)] & __BITMAP_BIT(__n, __v))
317 
318 #if __GNUC_PREREQ__(2, 95)
319 #define   __BITMAP_ZERO(__v) \
320     (void)__builtin_memset((__v), 0, sizeof(*__v))
321 #else
322 #define __BITMAP_ZERO(__v) do {                                                           \
323           size_t __i;                                                                     \
324           for (__i = 0; __i < __arraycount((__v)->_b); __i++)                   \
325                     (__v)->_b[__i] = 0;                                         \
326           } while (0)
327 #endif /* GCC 2.95 */
328 
329 #endif /* _SYS_BITOPS_H_ */
330