[cogl/wip/neil/pipeline-uniforms: 4/17] cogl-bitmask: Use ffsl to speedup bitmask iteration

[Neil Roberts <nroberts src gnome org>]

commit 610c57ae60e792284707ebc0b42f23efd1bae6f8
Author: Neil Roberts <neil linux intel com>
Date:   Fri Oct 28 20:09:53 2011 +0100

    cogl-bitmask: Use ffsl to speedup bitmask iteration
    
    Instead of testing each bit when iterating a bitmask, we can use ffsl
    to skip over unset bits in single instruction. That way it will scale
    by the number of bits set, not the total number of bits.
    
    ffsl is a non-standard function which glibc only provides by defining
    GNUC_SOURCE. However if we are compiling with GCC we can avoid that
    mess and just use the equivalent builtin. When not compiling for GCC
    it will fall back to _cogl_util_ffs if the size of ints and longs are
    the same (which is the case on i686). Otherwise it fallbacks to a slow
    function implementation.

 cogl/cogl-bitmask.c          |   21 ++++++++++++---------
 cogl/cogl-util.c             |   23 +++++++++++++++++++++++
 cogl/cogl-util.h             |   15 +++++++++++++++
 tests/conform/test-bitmask.c |    7 ++++---
 4 files changed, 54 insertions(+), 12 deletions(-)
---
diff --git a/cogl/cogl-bitmask.c b/cogl/cogl-bitmask.c
index 0e47d4f..bdd7b05 100644
--- a/cogl/cogl-bitmask.c
+++ b/cogl/cogl-bitmask.c
@@ -32,6 +32,7 @@
 #include <string.h>
 
 #include "cogl-bitmask.h"
+#include "cogl-util.h"
 
 /* This code assumes that we can cast an unsigned long to a pointer
    and back without losing any data */
@@ -245,12 +246,13 @@ _cogl_bitmask_foreach (const CoglBitmask *bitmask,
 
           while (mask)
             {
-              if (mask & 1UL)
-                func (array_index * sizeof (unsigned long) * 8 + bit,
-                      user_data);
+              int next_bit = _cogl_util_ffsl (mask);
 
-              bit++;
-              mask >>= 1;
+              bit += next_bit;
+              mask >>= next_bit;
+
+              func (array_index * sizeof (unsigned long) * 8 + bit - 1,
+                    user_data);
             }
         }
     }
@@ -261,11 +263,12 @@ _cogl_bitmask_foreach (const CoglBitmask *bitmask,
 
       while (mask)
         {
-          if (mask & 1UL)
-            func (bit, user_data);
+          int next_bit = _cogl_util_ffsl (mask);
+
+          bit += next_bit;
+          mask >>= next_bit;
 
-          bit++;
-          mask >>= 1;
+          func (bit - 1, user_data);
         }
     }
 }
diff --git a/cogl/cogl-util.c b/cogl/cogl-util.c
index 649e1e1..1cb3814 100644
--- a/cogl/cogl-util.c
+++ b/cogl/cogl-util.c
@@ -77,3 +77,26 @@ _cogl_util_ffs (int num)
   return i;
 }
 #endif /* HAVE_FFS */
+
+/* The 'ffsl' is non-standard but when building with GCC we'll use its
+   builtin instead */
+#ifndef COGL_UTIL_HAVE_BUILTIN_FFSL
+
+int
+_cogl_util_ffsl_wrapper (long int num)
+{
+  int i = 1;
+
+  if (num == 0)
+    return 0;
+
+  while ((num & 1) == 0)
+    {
+      num >>= 1;
+      i++;
+    }
+
+  return i;
+}
+
+#endif /* COGL_UTIL_HAVE_BUILTIN_FFSL */
diff --git a/cogl/cogl-util.h b/cogl/cogl-util.h
index 44bb501..b3267f9 100644
--- a/cogl/cogl-util.h
+++ b/cogl/cogl-util.h
@@ -107,6 +107,21 @@ int
 _cogl_util_ffs (int num);
 #endif
 
+/* The 'ffsl' function is non-standard but GCC has a builtin for it
+   since 3.4 which we can use */
+#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
+#define _cogl_util_ffsl __builtin_ffsl
+#define COGL_UTIL_HAVE_BUILTIN_FFSL
+#else
+/* If ints and longs are the same size we can just use ffs. Hopefully
+   the compiler will optimise away this conditional */
+#define _cogl_util_ffsl(x)                                              \
+  (sizeof (long int) == sizeof (int) ? _cogl_util_ffs ((int) x) :       \
+   _cogl_util_ffsl_wrapper (x))
+int
+_cogl_util_ffsl_wrapper (long int num);
+#endif
+
 #ifdef COGL_HAS_GLIB_SUPPORT
 #define _COGL_RETURN_IF_FAIL(EXPR) g_return_if_fail(EXPR)
 #define _COGL_RETURN_VAL_IF_FAIL(EXPR, VAL) g_return_val_if_fail(EXPR, VAL)
diff --git a/tests/conform/test-bitmask.c b/tests/conform/test-bitmask.c
index d7afab7..30c2dbf 100644
--- a/tests/conform/test-bitmask.c
+++ b/tests/conform/test-bitmask.c
@@ -11,6 +11,7 @@
 
 #include <cogl/cogl-bitmask.h>
 #include <cogl/cogl-bitmask.c>
+#include <cogl/cogl-util.c>
 
 typedef struct
 {
@@ -18,7 +19,7 @@ typedef struct
   int *bits;
 } CheckData;
 
-static gboolean
+static void
 check_bit (int bit_num, void *user_data)
 {
   CheckData *data = user_data;
@@ -28,12 +29,12 @@ check_bit (int bit_num, void *user_data)
     if (data->bits[i] == bit_num)
       {
         data->bits[i] = -1;
-        return TRUE;
+        return;
       }
 
   g_assert_not_reached ();
 
-  return TRUE;
+  return;
 }
 
 static void