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 40static __inline int __unused 41ffs32(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 74static __inline int __unused 75ffs64(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 115static __inline int __unused 116fls32(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 149static __inline int __unused 150fls64(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 264static __inline void 265fast_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 */ 279static __inline uint32_t 280fast_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 289static __inline uint32_t 290fast_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