include/sys/bitops.h

   1 /*      $NetBSD: bitops.h,v 1.7 2010/03/21 14:28:15 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(_n) \
 192 ( \
 193         __builtin_constant_p(_n) ? ( \
 194         _ilog2_helper(_n, 63) \
 195         _ilog2_helper(_n, 62) \
 196         _ilog2_helper(_n, 61) \
 197         _ilog2_helper(_n, 60) \
 198         _ilog2_helper(_n, 59) \
 199         _ilog2_helper(_n, 58) \
 200         _ilog2_helper(_n, 57) \
 201         _ilog2_helper(_n, 56) \
 202         _ilog2_helper(_n, 55) \
 203         _ilog2_helper(_n, 54) \
 204         _ilog2_helper(_n, 53) \
 205         _ilog2_helper(_n, 52) \
 206         _ilog2_helper(_n, 51) \
 207         _ilog2_helper(_n, 50) \
 208         _ilog2_helper(_n, 49) \
 209         _ilog2_helper(_n, 48) \
 210         _ilog2_helper(_n, 47) \
 211         _ilog2_helper(_n, 46) \
 212         _ilog2_helper(_n, 45) \
 213         _ilog2_helper(_n, 44) \
 214         _ilog2_helper(_n, 43) \
 215         _ilog2_helper(_n, 42) \
 216         _ilog2_helper(_n, 41) \
 217         _ilog2_helper(_n, 40) \
 218         _ilog2_helper(_n, 39) \
 219         _ilog2_helper(_n, 38) \
 220         _ilog2_helper(_n, 37) \
 221         _ilog2_helper(_n, 36) \
 222         _ilog2_helper(_n, 35) \
 223         _ilog2_helper(_n, 34) \
 224         _ilog2_helper(_n, 33) \
 225         _ilog2_helper(_n, 32) \
 226         _ilog2_helper(_n, 31) \
 227         _ilog2_helper(_n, 30) \
 228         _ilog2_helper(_n, 29) \
 229         _ilog2_helper(_n, 28) \
 230         _ilog2_helper(_n, 27) \
 231         _ilog2_helper(_n, 26) \
 232         _ilog2_helper(_n, 25) \
 233         _ilog2_helper(_n, 24) \
 234         _ilog2_helper(_n, 23) \
 235         _ilog2_helper(_n, 22) \
 236         _ilog2_helper(_n, 21) \
 237         _ilog2_helper(_n, 20) \
 238         _ilog2_helper(_n, 19) \
 239         _ilog2_helper(_n, 18) \
 240         _ilog2_helper(_n, 17) \
 241         _ilog2_helper(_n, 16) \
 242         _ilog2_helper(_n, 15) \
 243         _ilog2_helper(_n, 14) \
 244         _ilog2_helper(_n, 13) \
 245         _ilog2_helper(_n, 12) \
 246         _ilog2_helper(_n, 11) \
 247         _ilog2_helper(_n, 10) \
 248         _ilog2_helper(_n,  9) \
 249         _ilog2_helper(_n,  8) \
 250         _ilog2_helper(_n,  7) \
 251         _ilog2_helper(_n,  6) \
 252         _ilog2_helper(_n,  5) \
 253         _ilog2_helper(_n,  4) \
 254         _ilog2_helper(_n,  3) \
 255         _ilog2_helper(_n,  2) \
 256         _ilog2_helper(_n,  1) \
 257         _ilog2_helper(_n,  0) \
 258         -1) : ((sizeof(_n) >= 4 ? fls64(_n) : fls32(_n)) - 1) \
 259 )
 260
 261 static __inline void
 262 fast_divide32_prepare(uint32_t _div, uint32_t * __restrict _m,
 263     uint8_t *__restrict _s1, uint8_t *__restrict _s2)
 264 {
 265         uint64_t _mt;
 266         int _l;
 267
 268         _l = fls32(_div - 1);
 269         _mt = 0x100000000ULL * ((1ULL << _l) - _div);
 270         *_m = (uint32_t)(_mt / _div + 1);
 271         *_s1 = (_l > 1) ? 1 : _l;
 272         *_s2 = (_l == 0) ? 0 : _l - 1;
 273 }
 274
 275 /* ARGSUSED */
 276 static __inline uint32_t
 277 fast_divide32(uint32_t _v, uint32_t _div, uint32_t _m, uint8_t _s1,
 278     uint8_t _s2)
 279 {
 280         uint32_t _t;
 281
 282         _t = (uint32_t)(((uint64_t)_v * _m) >> 32);
 283         return (_t + ((_v - _t) >> _s1)) >> _s2;
 284 }
 285
 286 static __inline uint32_t
 287 fast_remainder32(uint32_t _v, uint32_t _div, uint32_t _m, uint8_t _s1,
 288     uint8_t _s2)
 289 {
 290
 291         return _v - _div * fast_divide32(_v, _div, _m, _s1, _s2);
 292 }
 293
 294 #endif /* _SYS_BITOPS_H_ */