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>

4 files changed, 51 insertions, 9 deletions

diff --git a/cogl/cogl-bitmask.c b/cogl/cogl-bitmask.c
index 0e47d4ff..bdd7b057 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 649e1e19..1cb38143 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 357e9c04..d38167c6 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 5f676570..b02a9ba3 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
 {