1 | /* $NetBSD: bitops.h,v 1.11 2012/12/07 02:27:58 christos 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 |
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 |
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 |
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 |
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 |
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) ? 1 : _l; |
275 | *_s2 = (_l == 0) ? 0 : _l - 1; |
276 | } |
277 | |
278 | /* ARGSUSED */ |
279 | static __inline uint32_t |
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 |
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 | (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 (/* CONSTCOND */ 0) |
327 | #endif /* GCC 2.95 */ |
328 | |
329 | #endif /* _SYS_BITOPS_H_ */ |
330 | |