git.ozlabs.org Git - ccan/blob - ccan/bitops/bitops.h

   1 /* CC0 license (public domain) - see LICENSE file for details */
   2 #ifndef CCAN_BITOPS_H
   3 #define CCAN_BITOPS_H
   4 #include "config.h"
   5 #include <stdint.h>
   6
   7 #if defined(CCAN_DEBUG) || defined(CCAN_BITOPS_DEBUG)
   8 #include <assert.h>
   9 #define BITOPS_ASSERT_NONZERO(u) assert((u) != 0)
  10 #else
  11 #define BITOPS_ASSERT_NONZERO(u)
  12 #endif
  13
  14 #if HAVE_BUILTIN_FFS && HAVE_BUILTIN_FFSL && HAVE_BUILTIN_FFSLL
  15 /**
  16  * bitops_ffs32: find first set bit in a uint32_t
  17  *
  18  * Returns 1 for least signficant bit, 32 for most significant bit, 0
  19  * for no bits set.
  20  */
  21 static inline int bitops_ffs32(uint32_t u)
  22 {
  23         return __builtin_ffs(u);
  24 }
  25
  26 /**
  27  * bitops_ffs64: find lowest set bit in a uint64_t
  28  *
  29  * Returns 1 for least signficant bit, 32 for most significant bit, 0
  30  * for no bits set.
  31  */
  32 static inline int bitops_ffs64(uint64_t u)
  33 {
  34         if (sizeof(u) == sizeof(long))
  35                 return __builtin_ffsl(u);
  36         else
  37                 return __builtin_ffsll(u);
  38 }
  39 #else
  40 int bitops_ffs32(uint32_t u);
  41 int bitops_ffs64(uint64_t u);
  42 #define BITOPS_NEED_FFS 1
  43 #endif
  44
  45 #if HAVE_BUILTIN_CLZ && HAVE_BUILTIN_CLZL && HAVE_BUILTIN_CLZLL
  46 /**
  47  * bitops_clz32: count leading zeros in a uint32_t (must not be 0)
  48  *
  49  * Returns 0 if most signficant bit is set, 31 if only least
  50  * signficant bit is set.
  51  */
  52 static inline int bitops_clz32(uint32_t u)
  53 {
  54         BITOPS_ASSERT_NONZERO(u);
  55         return __builtin_clz(u);
  56 }
  57
  58 /**
  59  * bitops_clz64: count leading zeros in a uint64_t (must not be 0)
  60  *
  61  * Returns 0 if most signficant bit is set, 63 if only least
  62  * signficant bit is set.
  63  */
  64 static inline int bitops_clz64(uint64_t u)
  65 {
  66         BITOPS_ASSERT_NONZERO(u);
  67         if (sizeof(u) == sizeof(long))
  68                 return __builtin_clzl(u);
  69         else
  70                 return __builtin_clzll(u);
  71 }
  72 #else
  73 int bitops_clz32(uint32_t u);
  74 int bitops_clz64(uint64_t u);
  75 #define BITOPS_NEED_CLZ 1
  76 #endif
  77
  78 #if HAVE_BUILTIN_CTZ && HAVE_BUILTIN_CTZL && HAVE_BUILTIN_CTZLL
  79 /**
  80  * bitops_ctz32: count trailing zeros in a uint32_t (must not be 0)
  81  *
  82  * Returns 0 if least signficant bit is set, 31 if only most
  83  * signficant bit is set.
  84  */
  85 static inline int bitops_ctz32(uint32_t u)
  86 {
  87         BITOPS_ASSERT_NONZERO(u);
  88         return __builtin_ctz(u);
  89 }
  90
  91 /**
  92  * bitops_ctz64: count trailing zeros in a uint64_t (must not be 0)
  93  *
  94  * Returns 0 if least signficant bit is set, 63 if only most
  95  * signficant bit is set.
  96  */
  97 static inline int bitops_ctz64(uint64_t u)
  98 {
  99         BITOPS_ASSERT_NONZERO(u);
 100         if (sizeof(u) == sizeof(long))
 101                 return __builtin_ctzl(u);
 102         else
 103                 return __builtin_ctzll(u);
 104 }
 105 #else
 106 int bitops_ctz32(uint32_t u);
 107 int bitops_ctz64(uint64_t u);
 108 #define BITOPS_NEED_CTZ 1
 109 #endif
 110
 111 /**
 112  * bitops_ls32: find lowest set bit in a uint32_t (must not be zero)
 113  *
 114  * Returns 0 for least signficant bit, 31 for most significant bit.
 115  */
 116 static inline int bitops_ls32(uint32_t u)
 117 {
 118         BITOPS_ASSERT_NONZERO(u);
 119         return bitops_ffs32(u) - 1;
 120 }
 121
 122 /**
 123  * bitops_ls64: find lowest set bit in a uint64_t (must not be zero)
 124  *
 125  * Returns 0 for least signficant bit, 63 for most significant bit.
 126  */
 127 static inline int bitops_ls64(uint64_t u)
 128 {
 129         BITOPS_ASSERT_NONZERO(u);
 130         return bitops_ffs64(u) - 1;
 131 }
 132
 133 /**
 134  * bitops_hs32: find highest set bit in a uint32_t (must not be zero)
 135  *
 136  * Returns 0 for least signficant bit, 31 for most significant bit.
 137  */
 138 static inline int bitops_hs32(uint32_t u)
 139 {
 140         BITOPS_ASSERT_NONZERO(u);
 141         return 31 - bitops_clz32(u);
 142 }
 143
 144 /**
 145  * bitops_hs64: find highest set bit in a uint64_t (must not be zero)
 146  *
 147  * Returns 0 for least signficant bit, 63 for most significant bit.
 148  */
 149 static inline int bitops_hs64(uint64_t u)
 150 {
 151         BITOPS_ASSERT_NONZERO(u);
 152         return 63 - bitops_clz64(u);
 153 }
 154
 155 /**
 156  * bitops_lc32: find lowest clear bit in a uint32_t (must not be 0xFFFFFFFF)
 157  *
 158  * Returns 0 for least signficant bit, 31 for most significant bit.
 159  */
 160 static inline int bitops_lc32(uint32_t u)
 161 {
 162         return bitops_ctz32(~u);
 163 }
 164
 165 /**
 166  * bitops_lc64: find lowest clear bit in a uint64_t (must not be 0xFFFFFFFFFFFFFFFF)
 167  *
 168  * Returns 0 for least signficant bit, 63 for most significant bit.
 169  */
 170 static inline int bitops_lc64(uint64_t u)
 171 {
 172         return bitops_ctz64(~u);
 173 }
 174
 175 /**
 176  * bitops_hc32: find highest clear bit in a uint32_t (must not be 0xFFFFFFFF)
 177  *
 178  * Returns 0 for least signficant bit, 31 for most significant bit.
 179  */
 180 static inline int bitops_hc32(uint32_t u)
 181 {
 182         return 31 - bitops_clz32(~u);
 183 }
 184
 185 /**
 186  * bitops_hc64: find highest clear bit in a uint64_t (must not be 0xFFFFFFFFFFFFFFFF)
 187  *
 188  * Returns 0 for least signficant bit, 63 for most significant bit.
 189  */
 190 static inline int bitops_hc64(uint64_t u)
 191 {
 192         return 63 - bitops_clz64(~u);
 193 }
 194
 195 #if HAVE_BUILTIN_POPCOUNT && HAVE_BUILTIN_POPCOUNTL && HAVE_BUILTIN_POPCOUNTLL
 196 /**
 197  * bitops_weight32: count number of bits set in a uint32_t
 198  *
 199  * Returns 0 to 32.
 200  */
 201 static inline int bitops_weight32(uint32_t u)
 202 {
 203         return __builtin_popcount(u);
 204 }
 205
 206 /**
 207  * bitops_weight64: count number of bits set in a uint64_t
 208  *
 209  * Returns 0 to 64.
 210  */
 211 static inline int bitops_weight64(uint64_t u)
 212 {
 213         if (sizeof(u) == sizeof(long))
 214                 return __builtin_popcountl(u);
 215         else
 216                 return __builtin_popcountll(u);
 217 }
 218 #else
 219 int bitops_weight32(uint32_t u);
 220 int bitops_weight64(uint64_t u);
 221 #define BITOPS_NEED_WEIGHT 1
 222 #endif
 223 #endif /* CCAN_BITOPS_H */