From 7c3701364542355c29b2e4ebc6d719ddd123c0f2 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 24 Jul 2025 09:00:49 +0200 Subject: Use bit trick for portable and arm popcount --- src/arch/neon.h | 15 ++++++++------- src/arch/portable.h | 27 ++++++++++++++++++++------- 2 files changed, 28 insertions(+), 14 deletions(-) (limited to 'src') 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; - - for (ret = 0; x != 0; x >>= 1) - ret += x & 1; - - return 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); + + 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; - - for (ret = 0; x != 0; x >>= 1) - ret += x & 1; - - return ret; + /* + Bit trick: accumulate in pairs of bits, quads of bits and so on, + until the final result is the sum of all bits. + + 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); + + 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 -- cgit v1.3