bitops.h

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*      $NetBSD: bitops.h,v 1.15 2021/09/12 15:22:05 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
   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) ? 1U : (uint8_t)_l;
  275         *_s2 = (_l == 0) ? 0 : (uint8_t)(_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     ((__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 (/* CONSTCOND */ 0)
  327 #endif /* GCC 2.95 */
  328 
  329 #endif /* _SYS_BITOPS_H_ */
Cache object: 0456feafeac2c3ff9f2b30084b5b3206
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/sys/bitops.h

FreeBSD/Linux Kernel Cross Reference
sys/sys/bitops.h
