[cogl] cogl-bitmask: Use ffsl to speedup bitmask iteration

[Neil Roberts <nroberts src gnome org>]

commit 2ba4fe417acb0352e6eca0e1f61627975c9716e3
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.
    
    Reviewed-by: Robert Bragg <robert linux intel com>

 cogl/cogl-bitmask.c          |   21 ++++++++++++---------
 cogl/cogl-util.c             |   23 +++++++++++++++++++++++
 cogl/cogl-util.h             |   15 +++++++++++++++
 tests/conform/test-bitmask.c |    1 +
 4 files changed, 51 insertions(+), 9 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 357e9c0..d38167c 100644
--- a/cogl/cogl-util.h
+++ b/cogl/cogl-util.h
@@ -108,6 +108,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 5f67657..b02a9ba 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
 {