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

[Neil Roberts <nroberts src gnome org>]

commit d6f64b9ab7e128769c51c49ab80cca48ab1663d4
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          |   22 +++++++++++++---------
 cogl/cogl-util.c             |   23 +++++++++++++++++++++++
 cogl/cogl-util.h             |   14 ++++++++++++++
 tests/conform/test-bitmask.c |    2 ++
 4 files changed, 52 insertions(+), 9 deletions(-)
---
diff --git a/cogl/cogl-bitmask.c b/cogl/cogl-bitmask.c
index 6effc1c..1fe2198 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,13 +246,14 @@ _cogl_bitmask_foreach (const CoglBitmask *bitmask,
 
           while (mask)
             {
-              if ((mask & 1UL) &&
-                  !func (array_index * sizeof (unsigned long) * 8 + bit,
+              int next_bit = _cogl_util_ffsl (mask);
+
+              bit += next_bit;
+              mask >>= next_bit;
+
+              if (!func (array_index * sizeof (unsigned long) * 8 + bit - 1,
                          user_data))
                 return;
-
-              bit++;
-              mask >>= 1;
             }
         }
     }
@@ -262,11 +264,13 @@ _cogl_bitmask_foreach (const CoglBitmask *bitmask,
 
       while (mask)
         {
-          if ((mask & 1) && !func (bit, user_data))
-            return;
+          int next_bit = _cogl_util_ffsl (mask);
+
+          bit += next_bit;
+          mask >>= next_bit;
 
-          bit++;
-          mask >>= 1;
+          if (!func (bit - 1, user_data))
+            return;
         }
     }
 }
diff --git a/cogl/cogl-util.c b/cogl/cogl-util.c
index ddee76a..1dc8877 100644
--- a/cogl/cogl-util.c
+++ b/cogl/cogl-util.c
@@ -238,3 +238,26 @@ _cogl_util_ffs (int num)
 }
 
 #endif /* HAVE_FFS */
+
+/* The 'ffsl' is non-standard but when building with GCC we'll use its
+   builtin instead */
+#if !defined (__GNUC__)
+
+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 /* HAVE_FFS */
diff --git a/cogl/cogl-util.h b/cogl/cogl-util.h
index e32fcd6..124ca5c 100644
--- a/cogl/cogl-util.h
+++ b/cogl/cogl-util.h
@@ -103,4 +103,18 @@ int
 _cogl_util_ffs (int num);
 #endif
 
+/* The 'ffsl' function is non-standard but GCC has a builtin for it
+   which we can use */
+#if defined (__GNUC__)
+#define _cogl_util_ffsl __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
+
 #endif /* __COGL_UTIL_H */
diff --git a/tests/conform/test-bitmask.c b/tests/conform/test-bitmask.c
index d7afab7..66daa16 100644
--- a/tests/conform/test-bitmask.c
+++ b/tests/conform/test-bitmask.c
@@ -9,8 +9,10 @@
    within Cogl. Cogl doesn't export the symbols for this data type so
    we just directly include the source instead */
 
+#define CLUTTER_COMPILATION
 #include <cogl/cogl-bitmask.h>
 #include <cogl/cogl-bitmask.c>
+#include <cogl/cogl-util.c>
 
 typedef struct
 {