5 files changed, 69 insertions, 11 deletions

diff --git a/src/arch/neon.h b/src/arch/neon.h
index 6261c9a..1fb1c82 100644
--- a/src/arch/neon.h
+++ b/src/arch/neon.h
@@ -30,16 +30,17 @@ STATIC_INLINE uint8x8_t compose_corners_slim(uint8x8_t, uint8x8_t);
 #define SOLVED_CUBE STATIC_CUBE( \
         0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
 
-/* TODO: optimize this (use intrinsics?) */
 STATIC_INLINE int
 popcount_u32(uint32_t x)
 {
-        int ret;
+        /* Same as the portable version */
+        x -= (x >> UINT32_C(1)) & UINT32_C(0x55555555);
+        x = (x & UINT32_C(0x33333333)) +
+            ((x >> UINT32_C(2)) & UINT32_C(0x33333333));
+        x = (x + (x >> UINT32_C(4))) & UINT32_C(0x0F0F0F0F);
+        x = (x * UINT32_C(0x01010101)) >> UINT32_C(24);
 
-        for (ret = 0; x != 0; x >>= 1)
-                ret += x & 1;
-
-        return ret;
+        return (int)x;
 }
 
 STATIC void
diff --git a/src/arch/portable.h b/src/arch/portable.h
index 56d3074..bd67c18 100644
--- a/src/arch/portable.h
+++ b/src/arch/portable.h
@@ -9,16 +9,29 @@
 #define SOLVED_CUBE STATIC_CUBE( \
     0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
 
-/* TODO: optimize this (use bit tricks?) */
 STATIC_INLINE int
 popcount_u32(uint32_t x)
 {
-        int ret;
+        /*
+        Bit trick: accumulate in pairs of bits, quads of bits and so on,
+        until the final result is the sum of all bits.
 
-        for (ret = 0; x != 0; x >>= 1)
-                ret += x & 1;
+        x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
+        x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
+        x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
+        x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
+        x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
 
-        return ret;
+        The actual method we use is a small optimization of the one above.
+        */
+
+        x -= (x >> UINT32_C(1)) & UINT32_C(0x55555555);
+        x = (x & UINT32_C(0x33333333)) +
+            ((x >> UINT32_C(2)) & UINT32_C(0x33333333));
+        x = (x + (x >> UINT32_C(4))) & UINT32_C(0x0F0F0F0F);
+        x = (x * UINT32_C(0x01010101)) >> UINT32_C(24);
+
+        return (int)x;
 }
 
 STATIC void
diff --git a/test/016_popcount_u32/00_all.in b/test/016_popcount_u32/00_all.in
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/016_popcount_u32/00_all.in
diff --git a/test/016_popcount_u32/00_all.out b/test/016_popcount_u32/00_all.out
new file mode 100644
index 0000000..7326d96
--- /dev/null
+++ b/test/016_popcount_u32/00_all.out
@@ -0,0 +1 @@
+Ok
diff --git a/test/016_popcount_u32/popcount_u32_tests.c b/test/016_popcount_u32/popcount_u32_tests.c
new file mode 100644
index 0000000..ff60c68
--- /dev/null
+++ b/test/016_popcount_u32/popcount_u32_tests.c
@@ -0,0 +1,43 @@
+#include "../test.h"
+
+int popcount_u32(uint32_t x);
+
+int
+popcount_u32_simple(uint32_t x)
+{
+        int ret;
+
+        for (ret = 0; x != 0; x >>= 1)
+                ret += x & 1;
+
+        return ret;
+}
+
+bool
+correct(uint32_t x)
+{
+        int expected = popcount_u32_simple(x);
+        int actual = popcount_u32(x);
+        if (actual != expected) {
+                printf("Error at %" PRIu32 ": expected %d bits, found %d\n",
+                    x, expected, actual);
+                return false;
+        }
+        return true;
+}
+
+void run(void) {
+        uint32_t i;
+
+        /* Test all numbers up to 2^16, and other ranges of 2^16 numbers */
+        for (i = 0; i < 0xFFFF; i++) {
+                if (!correct(i) ||
+                    !correct(i + UINT32_C(0xFFFF0000)) ||
+                    !correct(i + UINT32_C(1000000)) ||
+                    !correct(i + UINT32_C(1)) ||
+                    !correct(i + UINT32_C(1234567)))
+                    return;
+        }
+
+        printf("Ok\n");
+}