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

   1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
   2 #if !defined(_ilog_H)
   3 # define _ilog_H (1)
   4 # include "config.h"
   5 # include <stdint.h>
   6 # include <limits.h>
   7 # include <ccan/compiler/compiler.h>
   8
   9 /**
  10  * ilog32 - Integer binary logarithm of a 32-bit value.
  11  * @_v: A 32-bit value.
  12  * Returns floor(log2(_v))+1, or 0 if _v==0.
  13  * This is the number of bits that would be required to represent _v in two's
  14  *  complement notation with all of the leading zeros stripped.
  15  * Note that many uses will resolve to the fast macro version instead.
  16  *
  17  * See Also:
  18  *      ilog32_nz(), ilog64()
  19  *
  20  * Example:
  21  *      // Rounds up to next power of 2 (if not a power of 2).
  22  *      static uint32_t round_up32(uint32_t i)
  23  *      {
  24  *              assert(i != 0);
  25  *              return 1U << ilog32(i-1);
  26  *      }
  27  */
  28 int ilog32(uint32_t _v) CONST_FUNCTION;
  29
  30 /**
  31  * ilog32_nz - Integer binary logarithm of a non-zero 32-bit value.
  32  * @_v: A 32-bit value.
  33  * Returns floor(log2(_v))+1, or undefined 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  * Note that many uses will resolve to the fast macro version instead.
  37  * See Also:
  38  *      ilog32(), ilog64_nz()
  39  * Example:
  40  *      // Find Last Set (ie. highest bit set, 0 to 31).
  41  *      static uint32_t fls32(uint32_t i)
  42  *      {
  43  *              assert(i != 0);
  44  *              return ilog32_nz(i) - 1;
  45  *      }
  46  */
  47 int ilog32_nz(uint32_t _v) CONST_FUNCTION;
  48
  49 /**
  50  * ilog64 - Integer binary logarithm of a 64-bit value.
  51  * @_v: A 64-bit value.
  52  * Returns floor(log2(_v))+1, or 0 if _v==0.
  53  * This is the number of bits that would be required to represent _v in two's
  54  *  complement notation with all of the leading zeros stripped.
  55  * Note that many uses will resolve to the fast macro version instead.
  56  * See Also:
  57  *      ilog64_nz(), ilog32()
  58  */
  59 int ilog64(uint64_t _v) CONST_FUNCTION;
  60
  61 /**
  62  * ilog64_nz - Integer binary logarithm of a non-zero 64-bit value.
  63  * @_v: A 64-bit value.
  64  * Returns floor(log2(_v))+1, or undefined if _v==0.
  65  * This is the number of bits that would be required to represent _v in two's
  66  *  complement notation with all of the leading zeros stripped.
  67  * Note that many uses will resolve to the fast macro version instead.
  68  * See Also:
  69  *      ilog64(), ilog32_nz()
  70  */
  71 int ilog64_nz(uint64_t _v) CONST_FUNCTION;
  72
  73 /**
  74  * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant.
  75  * @_v: A non-negative 32-bit constant.
  76  * Returns floor(log2(_v))+1, or 0 if _v==0.
  77  * This is the number of bits that would be required to represent _v in two's
  78  *  complement notation with all of the leading zeros stripped.
  79  * This macro should only be used when you need a compile-time constant,
  80  * otherwise ilog32 or ilog32_nz are just as fast and more flexible.
  81  *
  82  * Example:
  83  *      #define MY_PAGE_SIZE    4096
  84  *      #define MY_PAGE_BITS    (STATIC_ILOG_32(PAGE_SIZE) - 1)
  85  */
  86 #define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v)))
  87
  88 /**
  89  * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant.
  90  * @_v: A non-negative 64-bit constant.
  91  * Returns floor(log2(_v))+1, or 0 if _v==0.
  92  * This is the number of bits that would be required to represent _v in two's
  93  *  complement notation with all of the leading zeros stripped.
  94  * This macro should only be used when you need a compile-time constant,
  95  * otherwise ilog64 or ilog64_nz are just as fast and more flexible.
  96  */
  97 #define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v)))
  98
  99 /* Private implementation details */
 100
 101 /*Note the casts to (int) below: this prevents "upgrading"
 102    the type of an entire expression to an (unsigned) size_t.*/
 103 #if INT_MAX>=2147483647 && HAVE_BUILTIN_CLZ
 104 #define builtin_ilog32_nz(v) \
 105         (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v))
 106 #elif LONG_MAX>=2147483647L && HAVE_BUILTIN_CLZL
 107 #define builtin_ilog32_nz(v) \
 108         (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clzl(v))
 109 #endif
 110
 111 #if INT_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZ
 112 #define builtin_ilog64_nz(v) \
 113         (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v))
 114 #elif LONG_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZL
 115 #define builtin_ilog64_nz(v) \
 116         (((int)sizeof(unsigned long)*CHAR_BIT) - __builtin_clzl(v))
 117 #elif HAVE_BUILTIN_CLZLL
 118 #define builtin_ilog64_nz(v) \
 119         (((int)sizeof(unsigned long long)*CHAR_BIT) - __builtin_clzll(v))
 120 #endif
 121
 122 #ifdef builtin_ilog32_nz
 123 #define ilog32(_v) (builtin_ilog32_nz(_v)&-!!(_v))
 124 #define ilog32_nz(_v) builtin_ilog32_nz(_v)
 125 #else
 126 #define ilog32_nz(_v) ilog32(_v)
 127 #define ilog32(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_32(_v) : ilog32(_v))
 128 #endif /* builtin_ilog32_nz */
 129
 130 #ifdef builtin_ilog64_nz
 131 #define ilog64(_v) (builtin_ilog64_nz(_v)&-!!(_v))
 132 #define ilog64_nz(_v) builtin_ilog64_nz(_v)
 133 #else
 134 #define ilog64_nz(_v) ilog64(_v)
 135 #define ilog64(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_64(_v) : ilog64(_v))
 136 #endif /* builtin_ilog64_nz */
 137
 138 /* Macros for evaluating compile-time constant ilog. */
 139 # define STATIC_ILOG0(_v) (!!(_v))
 140 # define STATIC_ILOG1(_v) (((_v)&0x2)?2:STATIC_ILOG0(_v))
 141 # define STATIC_ILOG2(_v) (((_v)&0xC)?2+STATIC_ILOG1((_v)>>2):STATIC_ILOG1(_v))
 142 # define STATIC_ILOG3(_v) \
 143  (((_v)&0xF0)?4+STATIC_ILOG2((_v)>>4):STATIC_ILOG2(_v))
 144 # define STATIC_ILOG4(_v) \
 145  (((_v)&0xFF00)?8+STATIC_ILOG3((_v)>>8):STATIC_ILOG3(_v))
 146 # define STATIC_ILOG5(_v) \
 147  (((_v)&0xFFFF0000)?16+STATIC_ILOG4((_v)>>16):STATIC_ILOG4(_v))
 148 # define STATIC_ILOG6(_v) \
 149  (((_v)&0xFFFFFFFF00000000ULL)?32+STATIC_ILOG5((_v)>>32):STATIC_ILOG5(_v))
 150
 151 #endif /* _ilog_H */