tdb2: test: fix run-57-die-during-transaction.c to be more efficient.
[ccan] / ccan / alloc / bitops.c
index ad4465f93b746555d543c5d83b4e32684d242b62..78c2b24f4f14f13287ef77445fdc448e535b7bda 100644 (file)
@@ -1,44 +1,22 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
 #include "bitops.h"
 #include "config.h"
+#include <ccan/build_assert/build_assert.h>
 #include <ccan/short_types/short_types.h>
+#include <ccan/ilog/ilog.h>
 #include <limits.h>
 
-unsigned int fls(unsigned long val)
+unsigned int afls(unsigned long val)
 {
-#if HAVE_BUILTIN_CLZL
-       /* This is significantly faster! */
-       return val ? sizeof(long) * CHAR_BIT - __builtin_clzl(val) : 0;
-#else
-       unsigned int r = 32;
-
-       if (!val)
-               return 0;
-       if (!(val & 0xffff0000u)) {
-               val <<= 16;
-               r -= 16;
-       }
-       if (!(val & 0xff000000u)) {
-               val <<= 8;
-               r -= 8;
-       }
-       if (!(val & 0xf0000000u)) {
-               val <<= 4;
-               r -= 4;
-       }
-       if (!(val & 0xc0000000u)) {
-               val <<= 2;
-               r -= 2;
-       }
-       if (!(val & 0x80000000u)) {
-               val <<= 1;
-               r -= 1;
-       }
-       return r;
-#endif
+       BUILD_ASSERT(sizeof(val) == sizeof(u32) || sizeof(val) == sizeof(u64));
+       if (sizeof(val) == sizeof(u32))
+               return ilog32(val);
+       else
+               return ilog64(val);
 }
 
 /* FIXME: Move to bitops. */
-unsigned int ffsl(unsigned long val)
+unsigned int affsl(unsigned long val)
 {
 #if HAVE_BUILTIN_FFSL
        /* This is significantly faster! */
@@ -92,22 +70,22 @@ unsigned int popcount(unsigned long val)
                v = (v & 0x5555555555555555ULL)
                        + ((v >> 1) & 0x5555555555555555ULL);
                v = (v & 0x3333333333333333ULL)
-                       + ((v >> 1) & 0x3333333333333333ULL);
+                       + ((v >> 2) & 0x3333333333333333ULL);
                v = (v & 0x0F0F0F0F0F0F0F0FULL)
-                       + ((v >> 1) & 0x0F0F0F0F0F0F0F0FULL);
+                       + ((v >> 4) & 0x0F0F0F0F0F0F0F0FULL);
                v = (v & 0x00FF00FF00FF00FFULL)
-                       + ((v >> 1) & 0x00FF00FF00FF00FFULL);
+                       + ((v >> 8) & 0x00FF00FF00FF00FFULL);
                v = (v & 0x0000FFFF0000FFFFULL)
-                       + ((v >> 1) & 0x0000FFFF0000FFFFULL);
+                       + ((v >> 16) & 0x0000FFFF0000FFFFULL);
                v = (v & 0x00000000FFFFFFFFULL)
-                       + ((v >> 1) & 0x00000000FFFFFFFFULL);
+                       + ((v >> 32) & 0x00000000FFFFFFFFULL);
                return v;
        }
        val = (val & 0x55555555ULL) + ((val >> 1) & 0x55555555ULL);
-       val = (val & 0x33333333ULL) + ((val >> 1) & 0x33333333ULL);
-       val = (val & 0x0F0F0F0FULL) + ((val >> 1) & 0x0F0F0F0FULL);
-       val = (val & 0x00FF00FFULL) + ((val >> 1) & 0x00FF00FFULL);
-       val = (val & 0x0000FFFFULL) + ((val >> 1) & 0x0000FFFFULL);
+       val = (val & 0x33333333ULL) + ((val >> 2) & 0x33333333ULL);
+       val = (val & 0x0F0F0F0FULL) + ((val >> 4) & 0x0F0F0F0FULL);
+       val = (val & 0x00FF00FFULL) + ((val >> 8) & 0x00FF00FFULL);
+       val = (val & 0x0000FFFFULL) + ((val >> 16) & 0x0000FFFFULL);
        return val;
 #endif
 }