Mesa (master): util/u_math: Implement a logbase2 function for unsigned long
Karol Herbst
karolherbst at kemper.freedesktop.org
Tue May 29 11:38:05 UTC 2018
Module: Mesa
Branch: master
Commit: 03f592a164fa95abbc839dc9820d2ef9fdd21edd
URL: http://cgit.freedesktop.org/mesa/mesa/commit/?id=03f592a164fa95abbc839dc9820d2ef9fdd21edd
Author: Pierre Moreau <pierre.morrow at free.fr>
Date: Sat May 6 17:52:59 2017 +0200
util/u_math: Implement a logbase2 function for unsigned long
v2 (Karol Herbst <kherbst at redhat.com>):
* removed unneeded ll
* ll -> ull
Signed-off-by: Karol Herbst <kherbst at redhat.com>
Reviewed-by: Eric Engestrom <eric.engestrom at intel.com>
Reviewed-by: Ilia Mirkin <imirkin at alum.mit.edu>
---
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 46d02978fd..79869a119a 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 5cc75f0beb..dc89ac93f2 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
More information about the mesa-commit
mailing list