[cogl] cogl-bitmask: Add _cogl_bitmask_popcount

[Neil Roberts <nroberts src gnome org>]

commit f23b12a886b117d39b76490c5bceb30eed3cb239
Author: Neil Roberts <neil linux intel com>
Date:   Fri Nov 4 17:11:50 2011 +0000

    cogl-bitmask: Add _cogl_bitmask_popcount
    
    This returns a population count of all the bits that are set in the
    bitmask.
    
    There is now also a _cogl_bitmask_popcount_upto which counts the
    number of bits set up to but not including the given bit index. This
    will be useful to determine the number of uniform overrides to skip if
    we tightly pack the values in an array.
    
    The test-bitmask test has been modified to check these two functions.
    
    Reviewed-by: Robert Bragg <robert linux intel com>

 cogl/cogl-bitmask.c          |   38 +++++++++++++++++++++++++++++++++
 cogl/cogl-bitmask.h          |   48 ++++++++++++++++++++++++++++++++++++++++++
 tests/conform/test-bitmask.c |   13 +++++++++++
 3 files changed, 99 insertions(+), 0 deletions(-)
---
diff --git a/cogl/cogl-bitmask.c b/cogl/cogl-bitmask.c
index 5e2ff92..1d2f2f8 100644
--- a/cogl/cogl-bitmask.c
+++ b/cogl/cogl-bitmask.c
@@ -271,3 +271,41 @@ _cogl_bitmask_set_flags_array (const CoglBitmask *bitmask,
   for (i = 0; i < array->len; i++)
     flags[i] |= g_array_index (array, unsigned long, i);
 }
+
+int
+_cogl_bitmask_popcount_in_array (const CoglBitmask *bitmask)
+{
+  const GArray *array = (const GArray *) *bitmask;
+  int pop = 0;
+  int i;
+
+  for (i = 0; i < array->len; i++)
+    pop += _cogl_util_popcountl (g_array_index (array, unsigned long, i));
+
+  return pop;
+}
+
+int
+_cogl_bitmask_popcount_upto_in_array (const CoglBitmask *bitmask,
+                                      int upto)
+{
+  const GArray *array = (const GArray *) *bitmask;
+
+  if (upto >= array->len * sizeof (unsigned long) * 8)
+    return _cogl_bitmask_popcount_in_array (bitmask);
+  else
+    {
+      unsigned long top_mask;
+      int array_index = ARRAY_INDEX (upto);
+      int bit_index = BIT_INDEX (upto);
+      int pop = 0;
+      int i;
+
+      for (i = 0; i < array_index; i++)
+        pop += _cogl_util_popcountl (g_array_index (array, unsigned long, i));
+
+      top_mask = g_array_index (array, unsigned long, array_index);
+
+      return pop + _cogl_util_popcountl (top_mask & ((1UL << bit_index) - 1));
+    }
+}
diff --git a/cogl/cogl-bitmask.h b/cogl/cogl-bitmask.h
index 479ac4a..e37fc0f 100644
--- a/cogl/cogl-bitmask.h
+++ b/cogl/cogl-bitmask.h
@@ -28,6 +28,7 @@
 #define __COGL_BITMASK_H
 
 #include <glib.h>
+#include "cogl-util.h"
 
 G_BEGIN_DECLS
 
@@ -104,6 +105,14 @@ _cogl_bitmask_clear_all_in_array (CoglBitmask *bitmask);
 void
 _cogl_bitmask_set_flags_array (const CoglBitmask *bitmask,
                                unsigned long *flags);
+
+int
+_cogl_bitmask_popcount_in_array (const CoglBitmask *bitmask);
+
+int
+_cogl_bitmask_popcount_upto_in_array (const CoglBitmask *bitmask,
+                                      int upto);
+
 /*
  * cogl_bitmask_set_bits:
  * @dst: The bitmask to modify
@@ -254,6 +263,45 @@ _cogl_bitmask_set_flags (const CoglBitmask *bitmask,
     flags[0] |= _cogl_bitmask_to_bits (bitmask);
 }
 
+/*
+ * _cogl_bitmask_popcount:
+ * @bitmask: A pointer to a bitmask
+ *
+ * Counts the number of bits that are set in the bitmask.
+ *
+ * Return value: the number of bits set in @bitmask.
+ */
+static inline int
+_cogl_bitmask_popcount (const CoglBitmask *bitmask)
+{
+  return (_cogl_bitmask_has_array (bitmask) ?
+          _cogl_bitmask_popcount_in_array (bitmask) :
+          _cogl_util_popcountl (_cogl_bitmask_to_bits (bitmask)));
+}
+
+/*
+ * _cogl_bitmask_popcount:
+ * @Bitmask: A pointer to a bitmask
+ * @upto: The maximum bit index to consider
+ *
+ * Counts the number of bits that are set and have an index which is
+ * less than @upto.
+ *
+ * Return value: the number of bits set in @bitmask that are less than @upto.
+ */
+static inline int
+_cogl_bitmask_popcount_upto (const CoglBitmask *bitmask,
+                             int upto)
+{
+  if (_cogl_bitmask_has_array (bitmask))
+    return _cogl_bitmask_popcount_upto_in_array (bitmask, upto);
+  else if (upto >= COGL_BITMASK_MAX_DIRECT_BITS)
+    return _cogl_util_popcountl (_cogl_bitmask_to_bits (bitmask));
+  else
+    return _cogl_util_popcountl (_cogl_bitmask_to_bits (bitmask) &
+                                 ((1UL << upto) - 1));
+}
+
 G_END_DECLS
 
 #endif /* __COGL_BITMASK_H */
diff --git a/tests/conform/test-bitmask.c b/tests/conform/test-bitmask.c
index 613e5ee..3636901 100644
--- a/tests/conform/test-bitmask.c
+++ b/tests/conform/test-bitmask.c
@@ -62,13 +62,26 @@ verify_bits (const CoglBitmask *bitmask,
   for (i = 0; i < data.n_bits; i++)
     g_assert_cmpint (data.bits[i], ==, -1);
 
+  g_assert_cmpint (_cogl_bitmask_popcount (bitmask), ==, data.n_bits);
+
   for (i = 0; i < 1024; i++)
     {
+      int upto_popcount = 0;
       int j;
 
       G_VA_COPY (ap, ap_copy);
 
       for (j = 0; j < data.n_bits; j++)
+        if (va_arg (ap, int) < i)
+          upto_popcount++;
+
+      g_assert_cmpint (_cogl_bitmask_popcount_upto (bitmask, i),
+                       ==,
+                       upto_popcount);
+
+      G_VA_COPY (ap, ap_copy);
+
+      for (j = 0; j < data.n_bits; j++)
         if (va_arg (ap, int) == i)
           break;