From 03f592a164fa95abbc839dc9820d2ef9fdd21edd Mon Sep 17 00:00:00 2001 From: Pierre Moreau Date: Sat, 6 May 2017 17:52:59 +0200 Subject: [PATCH] util/u_math: Implement a logbase2 function for unsigned long v2 (Karol Herbst ): * removed unneeded ll * ll -> ull Signed-off-by: Karol Herbst Reviewed-by: Eric Engestrom Reviewed-by: Ilia Mirkin --- src/gallium/auxiliary/util/u_math.h | 55 +++++++++++++++++++++++++++++ src/util/bitscan.h | 11 ++++++ 2 files changed, 66 insertions(+) diff --git a/src/gallium/auxiliary/util/u_math.h b/src/gallium/auxiliary/util/u_math.h index 46d02978fd6..79869a119af 100644 --- a/src/gallium/auxiliary/util/u_math.h +++ b/src/gallium/auxiliary/util/u_math.h @@ -421,6 +421,23 @@ util_logbase2(unsigned n) #endif } +static inline uint64_t +util_logbase2_64(uint64_t n) +{ +#if defined(HAVE___BUILTIN_CLZLL) + return ((sizeof(uint64_t) * 8 - 1) - __builtin_clzll(n | 1)); +#else + uint64_t pos = 0ull; + if (n >= 1ull<<32) { n >>= 32; pos += 32; } + if (n >= 1ull<<16) { n >>= 16; pos += 16; } + if (n >= 1ull<< 8) { n >>= 8; pos += 8; } + if (n >= 1ull<< 4) { n >>= 4; pos += 4; } + if (n >= 1ull<< 2) { n >>= 2; pos += 2; } + if (n >= 1ull<< 1) { pos += 1; } + return pos; +#endif +} + /** * Returns the ceiling of log n base 2, and 0 when n == 0. Equivalently, * returns the smallest x such that n <= 2**x. @@ -434,6 +451,15 @@ util_logbase2_ceil(unsigned n) return 1 + util_logbase2(n - 1); } +static inline uint64_t +util_logbase2_ceil64(uint64_t n) +{ + if (n <= 1) + return 0; + + return 1ull + util_logbase2_64(n - 1); +} + /** * Returns the smallest power of two >= x */ @@ -465,6 +491,35 @@ util_next_power_of_two(unsigned x) #endif } +static inline uint64_t +util_next_power_of_two64(uint64_t x) +{ +#if defined(HAVE___BUILTIN_CLZLL) + if (x <= 1) + return 1; + + return (1ull << ((sizeof(uint64_t) * 8) - __builtin_clzll(x - 1))); +#else + uint64_t val = x; + + if (x <= 1) + return 1; + + if (util_is_power_of_two_or_zero64(x)) + return x; + + val--; + val = (val >> 1) | val; + val = (val >> 2) | val; + val = (val >> 4) | val; + val = (val >> 8) | val; + val = (val >> 16) | val; + val = (val >> 32) | val; + val++; + return val; +#endif +} + /** * Return number of bits set in n. diff --git a/src/util/bitscan.h b/src/util/bitscan.h index 5cc75f0beba..dc89ac93f28 100644 --- a/src/util/bitscan.h +++ b/src/util/bitscan.h @@ -123,6 +123,17 @@ util_is_power_of_two_or_zero(unsigned v) return (v & (v - 1)) == 0; } +/* Determine if an uint64_t value is a power of two. + * + * \note + * Zero is treated as a power of two. + */ +static inline bool +util_is_power_of_two_or_zero64(uint64_t v) +{ + return (v & (v - 1)) == 0; +} + /* Determine if an unsigned value is a power of two. * * \note -- 2.30.2