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

[Karol Herbst]

From: Pierre Moreau <pierre.morrow at free.fr>

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..504d67664b2 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) * 8ll - 1ll) - __builtin_clzll(n | 1ll));
+#else
+   uint64_t pos = 0ll;
+   if (n >= 1ll<<32ll) { n >>= 32ll; pos += 32ll; }
+   if (n >= 1ll<<16ll) { n >>= 16ll; pos += 16ll; }
+   if (n >= 1ll<< 8ll) { n >>=  8ll; pos +=  8ll; }
+   if (n >= 1ll<< 4ll) { n >>=  4ll; pos +=  4ll; }
+   if (n >= 1ll<< 2ll) { n >>=  2ll; pos +=  2ll; }
+   if (n >= 1ll<< 1ll) {             pos +=  1ll; }
+   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 <= 1ll)
+      return 0ll;
+
+   return 1ll + util_logbase2_64(n - 1ll);
+}
+
 /**
  * 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 <= 1ll)
+       return 1ll;
+
+   return (1ll << ((sizeof(uint64_t) * 8ll) - __builtin_clzll(x - 1ll)));
+#else
+   uint64_t val = x;
+
+   if (x <= 1ll)
+      return 1ll;
+
+   if (util_is_power_of_two_or_zero64(x))
+      return x;
+
+   val--;
+   val = (val >> 1ll)  | val;
+   val = (val >> 2ll)  | val;
+   val = (val >> 4ll)  | val;
+   val = (val >> 8ll)  | val;
+   val = (val >> 16ll) | val;
+   val = (val >> 32ll) | 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..310b4ed2e37 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 - 1ll)) == 0ll;
+}
+
 /* Determine if an unsigned value is a power of two.
  *
  * \note
-- 
2.17.0