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

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