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 /* Find Last Set bit   */
  28
  29 static inline unsigned
  30 fls32(u32 v)
  31 {
  32 #ifdef compiler_fls32
  33         return compiler_fls32(v);
  34 #else
  35         unsigned bit = 0;
  36         while ((v >>= 1) != 0)
  37                 bit++;
  38         return bit;
  39 #endif
  40 }
  41
  42 static inline unsigned
  43 fls64(u64 v)
  44 {
  45 #ifdef compiler_fls64
  46         return compiler_fls64(v);
  47 #else
  48         unsigned bit = 0;
  49         while ((v >>= 1) != 0)
  50                 bit++;
  51         return bit;
  52 #endif
  53 }
  54
  55 static inline unsigned
  56 flsw(machine_word_t v)
  57 {
  58         STATIC_ASSERT(WORDSIZE == 4 || WORDSIZE == 8);
  59         if (WORDSIZE == 4)
  60                 return fls32(v);
  61         else
  62                 return fls64(v);
  63 }
  64
  65 /* Find First Set bit   */
  66
  67 static inline unsigned
  68 ffs32(u32 v)
  69 {
  70 #ifdef compiler_ffs32
  71         return compiler_ffs32(v);
  72 #else
  73         unsigned bit;
  74         for (bit = 0; !(v & 1); bit++, v >>= 1)
  75                 ;
  76         return bit;
  77 #endif
  78 }
  79
  80 static inline unsigned
  81 ffs64(u64 v)
  82 {
  83 #ifdef compiler_ffs64
  84         return compiler_ffs64(v);
  85 #else
  86         unsigned bit;
  87         for (bit = 0; !(v & 1); bit++, v >>= 1)
  88                 ;
  89         return bit;
  90 #endif
  91 }
  92
  93 static inline unsigned
  94 ffsw(machine_word_t v)
  95 {
  96         STATIC_ASSERT(WORDSIZE == 4 || WORDSIZE == 8);
  97         if (WORDSIZE == 4)
  98                 return ffs32(v);
  99         else
 100                 return ffs64(v);
 101 }
 102
 103 /* Round up to nearest power of 2  */
 104
 105 static inline size_t
 106 roundup_pow_of_2(size_t n)
 107 {
 108         if (n <= 1)
 109                 return 1;
 110         return (size_t)1 << (1 + flsw(n - 1));
 111 }
 112
 113 #endif /* _WIMLIB_BITOPS_H */