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

   1 #if !defined(_ilog_H)
   2 # define _ilog_H (1)
   3 # include "config.h"
   4 # include <stdint.h>
   5 # include <ccan/compiler/compiler.h>
   6 # include <limits.h>
   7 /*Note the casts to (int) below: this prevents CLZ{32|64}_OFFS from "upgrading"
   8    the type of an entire expression to an (unsigned) size_t.*/
   9 # if HAVE_BUILTIN_CLZ && INT_MAX>=2147483647
  10 #  define CLZ32_OFFS ((int)sizeof(unsigned)*CHAR_BIT)
  11 #  define CLZ32(_x) (__builtin_clz(_x))
  12 # elif HAVE_BUILTIN_CLZL && LONG_MAX>=2147483647L
  13 #  define CLZ32_OFFS ((int)sizeof(unsigned long)*CHAR_BIT)
  14 #  define CLZ32(_x) (__builtin_clzl(_x))
  15 # endif
  16
  17 # if HAVE_BUILTIN_CLZ && INT_MAX>=9223372036854775807LL
  18 #  define CLZ64_OFFS ((int)sizeof(unsigned)*CHAR_BIT)
  19 #  define CLZ64(_x) (__builtin_clz(_x))
  20 # elif HAVE_BUILTIN_CLZL && LONG_MAX>=9223372036854775807LL
  21 #  define CLZ64_OFFS ((int)sizeof(unsigned long)*CHAR_BIT)
  22 #  define CLZ64(_x) (__builtin_clzl(_x))
  23 # elif HAVE_BUILTIN_CLZLL /* long long must be >= 64 bits according to ISO C */
  24 #  define CLZ64_OFFS ((int)sizeof(unsigned long long)*CHAR_BIT)
  25 #  define CLZ64(_x) (__builtin_clzll(_x))
  26 # endif
  27
  28
  29
  30 /**
  31  * ilog32 - Integer binary logarithm of a 32-bit value.
  32  * @_v: A 32-bit value.
  33  * Returns floor(log2(_v))+1, or 0 if _v==0.
  34  * This is the number of bits that would be required to represent _v in two's
  35  *  complement notation with all of the leading zeros stripped.
  36  * The ILOG_32() or ILOGNZ_32() macros may be able to use a builtin function
  37  *  instead, which should be faster.
  38  */
  39 int ilog32(uint32_t _v) IDEMPOTENT_ATTRIBUTE;
  40 /**
  41  * ilog64 - Integer binary logarithm of a 64-bit value.
  42  * @_v: A 64-bit value.
  43  * Returns floor(log2(_v))+1, or 0 if _v==0.
  44  * This is the number of bits that would be required to represent _v in two's
  45  *  complement notation with all of the leading zeros stripped.
  46  * The ILOG_64() or ILOGNZ_64() macros may be able to use a builtin function
  47  *  instead, which should be faster.
  48  */
  49 int ilog64(uint64_t _v) IDEMPOTENT_ATTRIBUTE;
  50
  51
  52 # if defined(CLZ32)
  53 /**
  54  * ILOGNZ_32 - Integer binary logarithm of a non-zero 32-bit value.
  55  * @_v: A non-zero 32-bit value.
  56  * Returns floor(log2(_v))+1.
  57  * This is the number of bits that would be required to represent _v in two's
  58  *  complement notation with all of the leading zeros stripped.
  59  * If _v is zero, the return value is undefined; use ILOG_32() instead.
  60  */
  61 #  define ILOGNZ_32(_v) (CLZ32_OFFS-CLZ32(_v))
  62 /**
  63  * ILOG_32 - Integer binary logarithm of a 32-bit value.
  64  * @_v: A 32-bit value.
  65  * Returns floor(log2(_v))+1, or 0 if _v==0.
  66  * This is the number of bits that would be required to represent _v in two's
  67  *  complement notation with all of the leading zeros stripped.
  68  */
  69 #  define ILOG_32(_v)   (ILOGNZ_32(_v)&-!!(_v))
  70 # else
  71 #  define ILOGNZ_32(_v) (ilog32(_v))
  72 #  define ILOG_32(_v)   (ilog32(_v))
  73 # endif
  74
  75 # if defined(CLZ64)
  76 /**
  77  * ILOGNZ_64 - Integer binary logarithm of a non-zero 64-bit value.
  78  * @_v: A non-zero 64-bit value.
  79  * Returns floor(log2(_v))+1.
  80  * This is the number of bits that would be required to represent _v in two's
  81  *  complement notation with all of the leading zeros stripped.
  82  * If _v is zero, the return value is undefined; use ILOG_64() instead.
  83  */
  84 #  define ILOGNZ_64(_v) (CLZ64_OFFS-CLZ64(_v))
  85 /**
  86  * ILOG_64 - Integer binary logarithm of a 64-bit value.
  87  * @_v: A 64-bit value.
  88  * Returns floor(log2(_v))+1, or 0 if _v==0.
  89  * This is the number of bits that would be required to represent _v in two's
  90  *  complement notation with all of the leading zeros stripped.
  91  */
  92 #  define ILOG_64(_v)   (ILOGNZ_64(_v)&-!!(_v))
  93 # else
  94 #  define ILOGNZ_64(_v) (ilog64(_v))
  95 #  define ILOG_64(_v)   (ilog64(_v))
  96 # endif
  97
  98 # define STATIC_ILOG0(_v) (!!(_v))
  99 # define STATIC_ILOG1(_v) (((_v)&0x2)?2:STATIC_ILOG0(_v))
 100 # define STATIC_ILOG2(_v) (((_v)&0xC)?2+STATIC_ILOG1((_v)>>2):STATIC_ILOG1(_v))
 101 # define STATIC_ILOG3(_v) \
 102  (((_v)&0xF0)?4+STATIC_ILOG2((_v)>>4):STATIC_ILOG2(_v))
 103 # define STATIC_ILOG4(_v) \
 104  (((_v)&0xFF00)?8+STATIC_ILOG3((_v)>>8):STATIC_ILOG3(_v))
 105 # define STATIC_ILOG5(_v) \
 106  (((_v)&0xFFFF0000)?16+STATIC_ILOG4((_v)>>16):STATIC_ILOG4(_v))
 107 # define STATIC_ILOG6(_v) \
 108  (((_v)&0xFFFFFFFF00000000ULL)?32+STATIC_ILOG5((_v)>>32):STATIC_ILOG5(_v))
 109 /**
 110  * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant.
 111  * @_v: A non-negative 32-bit constant.
 112  * Returns floor(log2(_v))+1, or 0 if _v==0.
 113  * This is the number of bits that would be required to represent _v in two's
 114  *  complement notation with all of the leading zeros stripped.
 115  * This macro is suitable for evaluation at compile time, but it should not be
 116  *  used on values that can change at runtime, as it operates via exhaustive
 117  *  search.
 118  */
 119 # define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v)))
 120 /**
 121  * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant.
 122  * @_v: A non-negative 64-bit constant.
 123  * Returns floor(log2(_v))+1, or 0 if _v==0.
 124  * This is the number of bits that would be required to represent _v in two's
 125  *  complement notation with all of the leading zeros stripped.
 126  * This macro is suitable for evaluation at compile time, but it should not be
 127  *  used on values that can change at runtime, as it operates via exhaustive
 128  *  search.
 129  */
 130 # define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v)))
 131
 132 #endif