X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Filog%2Filog.h;h=55dd009885a73c488cb41280f64a319e84ed6233;hp=29689f5f5ff69825bf3bca6c1d215ac8ac983315;hb=788c3a4f3469afa00c7414451a5f93e584ce0187;hpb=2037a903729fea95d76ad7baa7c1e2cd3ce38f04 diff --git a/ccan/ilog/ilog.h b/ccan/ilog/ilog.h index 29689f5f..55dd0098 100644 --- a/ccan/ilog/ilog.h +++ b/ccan/ilog/ilog.h @@ -1,44 +1,9 @@ #if !defined(_ilog_H) # define _ilog_H (1) +# include "config.h" # include - -# ifdef __GNUC_PREREQ -/*Tag our functions as idempotent to aid optimization, if possible.*/ -# if __GNUC_PREREQ(2,5) -# define IDEMPOTENT __attribute__((const)) -# endif -# if __GNUC_PREREQ(3,4) -# include -/*Note the casts to (int) below: this prevents CLZ{32|64}_OFFS from "upgrading" - the type of an entire expression to an (unsigned) size_t.*/ -# if INT_MAX>=2147483647 -# define CLZ32_OFFS ((int)sizeof(unsigned)*CHAR_BIT) -# define CLZ32(_x) (__builtin_clz(_x)) -# elif LONG_MAX>=2147483647L -# define CLZ32_OFFS ((int)sizeof(unsigned long)*CHAR_BIT) -# define CLZ32(_x) (__builtin_clzl(_x)) -# endif -# if INT_MAX>=9223372036854775807LL -# define CLZ64_OFFS ((int)sizeof(unsigned)*CHAR_BIT) -# define CLZ64(_x) (__builtin_clz(_x)) -# elif LONG_MAX>=9223372036854775807LL -# define CLZ64_OFFS ((int)sizeof(unsigned long)*CHAR_BIT) -# define CLZ64(_x) (__builtin_clzl(_x)) -# else /* long long must be >= 64 bits according to ISO C */ -# define CLZ64_OFFS ((int)sizeof(unsigned long long)*CHAR_BIT) -# define CLZ64(_x) (__builtin_clzll(_x)) -# endif -# endif -# endif - -/*If you have some other compiler which defines its own clz-style builtin, - implement a check for it here.*/ - -# if !defined(IDEMPOTENT) -# define IDEMPOTENT -# endif - - +# include +# include /** * ilog32 - Integer binary logarithm of a 32-bit value. @@ -46,70 +11,130 @@ * Returns floor(log2(_v))+1, or 0 if _v==0. * This is the number of bits that would be required to represent _v in two's * complement notation with all of the leading zeros stripped. - * The ILOG_32() or ILOGNZ_32() macros may be able to use a builtin function - * instead, which should be faster. + * Note that many uses will resolve to the fast macro version instead. + * + * See Also: + * ilog32_nz(), ilog64() + * + * Example: + * // Rounds up to next power of 2 (if not a power of 2). + * static uint32_t round_up32(uint32_t i) + * { + * assert(i != 0); + * return 1U << ilog32(i-1); + * } */ -int ilog32(uint32_t _v)IDEMPOTENT; +int ilog32(uint32_t _v) IDEMPOTENT; + /** - * ilog64 - Integer binary logarithm of a 64-bit value. - * @_v: A 64-bit value. - * Returns floor(log2(_v))+1, or 0 if _v==0. + * ilog32_nz - Integer binary logarithm of a non-zero 32-bit value. + * @_v: A 32-bit value. + * Returns floor(log2(_v))+1, or undefined if _v==0. * This is the number of bits that would be required to represent _v in two's * complement notation with all of the leading zeros stripped. - * The ILOG_64() or ILOGNZ_64() macros may be able to use a builtin function - * instead, which should be faster. + * Note that many uses will resolve to the fast macro version instead. + * See Also: + * ilog32(), ilog64_nz() + * Example: + * // Find Last Set (ie. highest bit set, 0 to 31). + * static uint32_t fls32(uint32_t i) + * { + * assert(i != 0); + * return ilog32_nz(i) - 1; + * } */ -int ilog64(uint64_t _v)IDEMPOTENT; - -# undef IDEMPOTENT - +int ilog32_nz(uint32_t _v) IDEMPOTENT; -# if defined(CLZ32) /** - * ILOGNZ_32 - Integer binary logarithm of a non-zero 32-bit value. - * @_v: A non-zero 32-bit value. - * Returns floor(log2(_v))+1. + * ilog64 - Integer binary logarithm of a 64-bit value. + * @_v: A 64-bit value. + * Returns floor(log2(_v))+1, or 0 if _v==0. * This is the number of bits that would be required to represent _v in two's * complement notation with all of the leading zeros stripped. - * If _v is zero, the return value is undefined; use ILOG_32() instead. + * Note that many uses will resolve to the fast macro version instead. + * See Also: + * ilog64_nz(), ilog32() */ -# define ILOGNZ_32(_v) (CLZ32_OFFS-CLZ32(_v)) +int ilog64(uint64_t _v) IDEMPOTENT; + /** - * ILOG_32 - Integer binary logarithm of a 32-bit value. - * @_v: A 32-bit value. - * Returns floor(log2(_v))+1, or 0 if _v==0. + * ilog64_nz - Integer binary logarithm of a non-zero 64-bit value. + * @_v: A 64-bit value. + * Returns floor(log2(_v))+1, or undefined if _v==0. * This is the number of bits that would be required to represent _v in two's * complement notation with all of the leading zeros stripped. + * Note that many uses will resolve to the fast macro version instead. + * See Also: + * ilog64(), ilog32_nz() */ -# define ILOG_32(_v) (ILOGNZ_32(_v)&-!!(_v)) -# else -# define ILOGNZ_32(_v) (ilog32(_v)) -# define ILOG_32(_v) (ilog32(_v)) -# endif +int ilog64_nz(uint64_t _v) IDEMPOTENT; -# if defined(CLZ64) /** - * ILOGNZ_64 - Integer binary logarithm of a non-zero 64-bit value. - * @_v: A non-zero 64-bit value. - * Returns floor(log2(_v))+1. + * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant. + * @_v: A non-negative 32-bit constant. + * Returns floor(log2(_v))+1, or 0 if _v==0. * This is the number of bits that would be required to represent _v in two's * complement notation with all of the leading zeros stripped. - * If _v is zero, the return value is undefined; use ILOG_64() instead. + * This macro should only be used when you need a compile-time constant, + * otherwise ilog32 or ilog32_nz are just as fast and more flexible. + * + * Example: + * #define MY_PAGE_SIZE 4096 + * #define MY_PAGE_BITS (STATIC_ILOG_32(PAGE_SIZE) - 1) */ -# define ILOGNZ_64(_v) (CLZ64_OFFS-CLZ64(_v)) +#define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v))) + /** - * ILOG_64 - Integer binary logarithm of a 64-bit value. - * @_v: A 64-bit value. + * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant. + * @_v: A non-negative 64-bit constant. * Returns floor(log2(_v))+1, or 0 if _v==0. * This is the number of bits that would be required to represent _v in two's * complement notation with all of the leading zeros stripped. + * This macro should only be used when you need a compile-time constant, + * otherwise ilog64 or ilog64_nz are just as fast and more flexible. */ -# define ILOG_64(_v) (ILOGNZ_64(_v)&-!!(_v)) -# else -# define ILOGNZ_64(_v) (ilog64(_v)) -# define ILOG_64(_v) (ilog64(_v)) -# endif +#define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v))) +/* Private implementation details */ + +/*Note the casts to (int) below: this prevents "upgrading" + the type of an entire expression to an (unsigned) size_t.*/ +#if INT_MAX>=2147483647 && HAVE_BUILTIN_CLZ +#define builtin_ilog32_nz(v) \ + (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v)) +#elif LONG_MAX>=2147483647L && HAVE_BUILTIN_CLZL +#define builtin_ilog32_nz(v) \ + (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clzl(v)) +#endif + +#if INT_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZ +#define builtin_ilog64_nz(v) \ + (((int)sizeof(unsigned)*CHAR_BIT) - __builtin_clz(v)) +#elif LONG_MAX>=9223372036854775807LL && HAVE_BUILTIN_CLZL +#define builtin_ilog64_nz(v) \ + (((int)sizeof(unsigned long)*CHAR_BIT) - __builtin_clzl(v)) +#elif HAVE_BUILTIN_CLZLL +#define builtin_ilog64_nz(v) \ + (((int)sizeof(unsigned long long)*CHAR_BIT) - __builtin_clzll(v)) +#endif + +#ifdef builtin_ilog32_nz +#define ilog32(_v) (builtin_ilog32_nz(_v)&-!!(_v)) +#define ilog32_nz(_v) builtin_ilog32_nz(_v) +#else +#define ilog32_nz(_v) ilog32(_v) +#define ilog32(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_32(_v) : ilog32(_v)) +#endif /* builtin_ilog32_nz */ + +#ifdef builtin_ilog64_nz +#define ilog64(_v) (builtin_ilog64_nz(_v)&-!!(_v)) +#define ilog64_nz(_v) builtin_ilog64_nz(_v) +#else +#define ilog64_nz(_v) ilog64(_v) +#define ilog64(_v) (IS_COMPILE_CONSTANT(_v) ? STATIC_ILOG_64(_v) : ilog64(_v)) +#endif /* builtin_ilog64_nz */ + +/* Macros for evaluating compile-time constant ilog. */ # define STATIC_ILOG0(_v) (!!(_v)) # define STATIC_ILOG1(_v) (((_v)&0x2)?2:STATIC_ILOG0(_v)) # define STATIC_ILOG2(_v) (((_v)&0xC)?2+STATIC_ILOG1((_v)>>2):STATIC_ILOG1(_v)) @@ -121,27 +146,5 @@ int ilog64(uint64_t _v)IDEMPOTENT; (((_v)&0xFFFF0000)?16+STATIC_ILOG4((_v)>>16):STATIC_ILOG4(_v)) # define STATIC_ILOG6(_v) \ (((_v)&0xFFFFFFFF00000000ULL)?32+STATIC_ILOG5((_v)>>32):STATIC_ILOG5(_v)) -/** - * STATIC_ILOG_32 - The integer logarithm of an (unsigned, 32-bit) constant. - * @_v: A non-negative 32-bit constant. - * Returns floor(log2(_v))+1, or 0 if _v==0. - * This is the number of bits that would be required to represent _v in two's - * complement notation with all of the leading zeros stripped. - * This macro is suitable for evaluation at compile time, but it should not be - * used on values that can change at runtime, as it operates via exhaustive - * search. - */ -# define STATIC_ILOG_32(_v) (STATIC_ILOG5((uint32_t)(_v))) -/** - * STATIC_ILOG_64 - The integer logarithm of an (unsigned, 64-bit) constant. - * @_v: A non-negative 64-bit constant. - * Returns floor(log2(_v))+1, or 0 if _v==0. - * This is the number of bits that would be required to represent _v in two's - * complement notation with all of the leading zeros stripped. - * This macro is suitable for evaluation at compile time, but it should not be - * used on values that can change at runtime, as it operates via exhaustive - * search. - */ -# define STATIC_ILOG_64(_v) (STATIC_ILOG6((uint64_t)(_v))) -#endif +#endif /* _ilog_H */