py/misc: Add a popcount(uint32_t) implementation.

This makes the existing popcount(uint32_t) implementation found in the
RV32 emitter available to the rest of the codebase.  This version of
popcount will use intrinsic or builtin implementations if they are
available, falling back to a generic implementation if that is not the
case.

Signed-off-by: Alessandro Gatti <a.gatti@frob.it>

1 files changed, 17 insertions, 0 deletions

diff --git a/py/misc.h b/py/misc.h
index 2629d0c46c..e05fbe61a9 100644
--- a/py/misc.h
+++ b/py/misc.h
@@ -370,12 +370,29 @@ static inline uint32_t mp_ctz(uint32_t x) {
 static inline bool mp_check(bool value) {
     return value;
 }
+
+static inline uint32_t mp_popcount(uint32_t x) {
+    return __popcnt(x);
+}
 #else
 #define mp_clz(x) __builtin_clz(x)
 #define mp_clzl(x) __builtin_clzl(x)
 #define mp_clzll(x) __builtin_clzll(x)
 #define mp_ctz(x) __builtin_ctz(x)
 #define mp_check(x) (x)
+#if defined __has_builtin
+#if __has_builtin(__builtin_popcount)
+#define mp_popcount(x) __builtin_popcount(x)
+#endif
+#endif
+#if !defined(mp_popcount)
+static inline uint32_t mp_popcount(uint32_t x) {
+    x = x - ((x >> 1) & 0x55555555);
+    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
+    x = (x + (x >> 4)) & 0x0F0F0F0F;
+    return x * 0x01010101;
+}
+#endif
 #endif
 
 // mp_int_t can be larger than long, i.e. Windows 64-bit, nan-box variants