[Mesa-dev] [PATCH v2 1/2] util/u_math: Implement a logbase2 function for unsigned long

[Eric Engestrom]

On Thursday, 2018-05-24 11:47:52 +0200, Karol Herbst wrote:
> From: Pierre Moreau <pierre.morrow at free.fr>
> 
> v2 (Karol Herbst <kherbst at redhat.com>):
> * removed unneeded ll
> * ll -> ull

Reviewed-by: Eric Engestrom <eric.engestrom at intel.com>

> 
> Signed-off-by: Karol Herbst <kherbst at redhat.com>
> ---
>  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.17.0
>