Optimize hot loops with direct access, LUTs, and closed-form formulas

1 files changed, 8 insertions, 10 deletions

diff --git a/src/compat.h b/src/compat.h
index a972a0f..c0ae6fa 100644
--- a/src/compat.h
+++ b/src/compat.h
@@ -80,12 +80,11 @@ static inline int term_ctz32(uint32_t x)
 {
     if (!x)
         return 32;
-    int n = 0;
-    while (!(x & 1u)) {
-        x >>= 1;
-        n++;
-    }
-    return n;
+    static const uint8_t de_bruijn[32] = {
+        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
+        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
+    };
+    return (int)de_bruijn[((uint32_t)((x & -x) * 0x077CB531U)) >> 27];
 }
 static inline int term_clz32(uint32_t x)
 {
@@ -101,10 +100,9 @@ static inline int term_clz32(uint32_t x)
 }
 static inline int term_popcount32(uint32_t x)
 {
-    int n = 0;
-    for (; x; x &= x - 1)
-        n++;
-    return n;
+    x = x - ((x >> 1) & 0x55555555u);
+    x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u);
+    return (int)((((x + (x >> 4)) & 0x0F0F0F0Fu) * 0x01010101u) >> 24);
 }
 #endif