1 files changed, 33 insertions, 0 deletions
diff --git a/lib/util.c b/lib/util.c
index e6d57dadf..5e90ecb50 100644
--- a/lib/util.c
+++ b/lib/util.c
@@ -663,3 +663,36 @@ log_2_floor(uint32_t n)
     }
 #endif
 }
+
+/* Returns the number of trailing 0-bits in 'n', or 32 if 'n' is 0. */
+int
+ctz(uint32_t n)
+{
+    if (!n) {
+        return 32;
+    } else {
+#if !defined(UINT_MAX) || !defined(UINT32_MAX)
+#error "Someone screwed up the #includes."
+#elif __GNUC__ >= 4 && UINT_MAX == UINT32_MAX
+        return __builtin_ctz(n);
+#else
+        unsigned int k;
+        int count = 31;
+
+#define CTZ_STEP(X)                             \
+        k = n << (X);                           \
+        if (k) {                                \
+            count -= X;                         \
+            n = k;                              \
+        }
+        CTZ_STEP(16);
+        CTZ_STEP(8);
+        CTZ_STEP(4);
+        CTZ_STEP(2);
+        CTZ_STEP(1);
+#undef CTZ_STEP
+
+        return count;
+#endif
+    }
+}