Mesa (master): util: better logbase2/next_power_of_two implementations

[Roland Scheidegger]

Module: Mesa
Branch: master
Commit: 894db40f122175ed85e0d32d42296f2d56cf748e
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=894db40f122175ed85e0d32d42296f2d56cf748e

Author: Benjamin Bellec <b.bellec at gmail.com>
Date:   Wed Jun  8 23:00:54 2011 +0200

util: better logbase2/next_power_of_two implementations

Use __builtin_clz when available for logbase/next_power_of_two,
and replace next_power_of_two with faster implementation otherwise.

---

 src/gallium/auxiliary/util/u_math.h |   32 ++++++++++++++++++++++++--------
 1 files changed, 24 insertions(+), 8 deletions(-)

diff --git a/src/gallium/auxiliary/util/u_math.h b/src/gallium/auxiliary/util/u_math.h
index 65a99fc..417f79f 100644
--- a/src/gallium/auxiliary/util/u_math.h
+++ b/src/gallium/auxiliary/util/u_math.h
@@ -477,6 +477,9 @@ float_to_byte_tex(float f)
 static INLINE unsigned
 util_logbase2(unsigned n)
 {
+#if defined(PIPE_CC_GCC)
+   return ((sizeof(unsigned) * 8 - 1) - __builtin_clz(n | 1));
+#else
    unsigned pos = 0;
    if (n >= 1<<16) { n >>= 16; pos += 16; }
    if (n >= 1<< 8) { n >>=  8; pos +=  8; }
@@ -484,6 +487,7 @@ util_logbase2(unsigned n)
    if (n >= 1<< 2) { n >>=  2; pos +=  2; }
    if (n >= 1<< 1) {           pos +=  1; }
    return pos;
+#endif
 }
 
 
@@ -493,17 +497,29 @@ util_logbase2(unsigned n)
 static INLINE unsigned
 util_next_power_of_two(unsigned x)
 {
-   unsigned i;
-
-   if (x == 0)
-      return 1;
+#if defined(PIPE_CC_GCC)
+   if (x <= 1)
+       return 1;
 
-   --x;
+   return (1 << ((sizeof(unsigned) * 8) - __builtin_clz(x - 1)));
+#else
+   unsigned val = x;
 
-   for (i = 1; i < sizeof(unsigned) * 8; i <<= 1)
-      x |= x >> i;
+   if (x <= 1)
+      return 1;
 
-   return x + 1;
+   if (util_is_power_of_two(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++;
+   return val;
+#endif
 }