wimlib.net Git - wimlib/blob - include/wimlib/bitops.h

   1 /*
   2  * bitops.h - inline functions for bit manipulation
   3  *
   4  * The following copying information applies to this specific source code file:
   5  *
   6  * Written in 2014-2016 by Eric Biggers <ebiggers3@gmail.com>
   7  *
   8  * To the extent possible under law, the author(s) have dedicated all copyright
   9  * and related and neighboring rights to this software to the public domain
  10  * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
  11  * Dedication (the "CC0").
  12  *
  13  * This software is distributed in the hope that it will be useful, but WITHOUT
  14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  15  * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
  16  *
  17  * You should have received a copy of the CC0 along with this software; if not
  18  * see <http://creativecommons.org/publicdomain/zero/1.0/>.
  19  */
  20
  21 #ifndef _WIMLIB_BITOPS_H
  22 #define _WIMLIB_BITOPS_H
  23
  24 #include "wimlib/compiler.h"
  25 #include "wimlib/types.h"
  26
  27 /*
  28  * Bit Scan Reverse (BSR) - find the 0-based index (relative to the least
  29  * significant bit) of the *most* significant 1 bit in the input value.  The
  30  * input value must be nonzero!
  31  */
  32
  33 static forceinline unsigned
  34 bsr32(u32 v)
  35 {
  36 #ifdef compiler_bsr32
  37         return compiler_bsr32(v);
  38 #else
  39         unsigned bit = 0;
  40         while ((v >>= 1) != 0)
  41                 bit++;
  42         return bit;
  43 #endif
  44 }
  45
  46 static forceinline unsigned
  47 bsr64(u64 v)
  48 {
  49 #ifdef compiler_bsr64
  50         return compiler_bsr64(v);
  51 #else
  52         unsigned bit = 0;
  53         while ((v >>= 1) != 0)
  54                 bit++;
  55         return bit;
  56 #endif
  57 }
  58
  59 static forceinline unsigned
  60 bsrw(machine_word_t v)
  61 {
  62         STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
  63         if (WORDBITS == 32)
  64                 return bsr32(v);
  65         else
  66                 return bsr64(v);
  67 }
  68
  69 /*
  70  * Bit Scan Forward (BSF) - find the 0-based index (relative to the least
  71  * significant bit) of the *least* significant 1 bit in the input value.  The
  72  * input value must be nonzero!
  73  */
  74
  75 static forceinline unsigned
  76 bsf32(u32 v)
  77 {
  78 #ifdef compiler_bsf32
  79         return compiler_bsf32(v);
  80 #else
  81         unsigned bit;
  82         for (bit = 0; !(v & 1); bit++, v >>= 1)
  83                 ;
  84         return bit;
  85 #endif
  86 }
  87
  88 static forceinline unsigned
  89 bsf64(u64 v)
  90 {
  91 #ifdef compiler_bsf64
  92         return compiler_bsf64(v);
  93 #else
  94         unsigned bit;
  95         for (bit = 0; !(v & 1); bit++, v >>= 1)
  96                 ;
  97         return bit;
  98 #endif
  99 }
 100
 101 static forceinline unsigned
 102 bsfw(machine_word_t v)
 103 {
 104         STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
 105         if (WORDBITS == 32)
 106                 return bsf32(v);
 107         else
 108                 return bsf64(v);
 109 }
 110
 111 /* Return the log base 2 of 'n', rounded up to the nearest integer. */
 112 static forceinline unsigned
 113 ilog2_ceil(size_t n)
 114 {
 115         if (n <= 1)
 116                 return 0;
 117         return 1 + bsrw(n - 1);
 118 }
 119
 120 /* Round 'n' up to the nearest power of 2 */
 121 static forceinline size_t
 122 roundup_pow_of_2(size_t n)
 123 {
 124         return (size_t)1 << ilog2_ceil(n);
 125 }
 126
 127 #endif /* _WIMLIB_BITOPS_H */