Port timeout.c to platforms without __builtin_c[tl]z

This patch includes an intrinsic implementation for these functions
when the compiler is GCC, Clang, or MSVC--or if the compiler claims
to be one of those.  Otherwise, a naive implementation is used.

Tests are included for all of these functions, which turned up a
possible problem: according to the gcc documentation, __builtin_ctz
and __builtin_clz give an undefined result when their inputs is
zero.  I was not able to persuade myself that we always called them
with a nonzero argument.

2 files changed, 254 insertions, 12 deletions

diff --git a/bitops.c b/bitops.c
new file mode 100644
index 0000000..f203fad
--- /dev/null
+++ b/bitops.c
@@ -0,0 +1,243 @@
+#include <stdint.h>
+#ifdef _MSC_VER
+#include <intrin.h>     /* _BitScanForward, _BitScanReverse */
+#endif
+
+/* First define ctz and clz functions; these are compiler-dependent if
+ * you want them to be fast. */
+#if defined(__GNUC__) && !defined(TIMEOUT_DISABLE_GNUC_BITOPS)
+
+/* On GCC and clang and some others, we can use __builtin functions. They
+ * are not defined for n==0, however.*/
+
+static inline int ctz64(uint64_t n)
+{
+	return n ? __builtin_ctzll(n) : 64;
+}
+static inline int clz64(uint64_t n)
+{
+	return n ? __builtin_clzll(n) : 64;
+}
+#if LONG_BITS == 32
+#define ctz32_(n) __builtin_ctzl(n)
+#define clz32_(n) __builtin_clzl(n)
+#else
+#define ctz32_(n) __builtin_ctz(n)
+#define clz32_(n) __builtin_clz(n)
+#endif
+static inline int ctz32(uint64_t n)
+{
+	return n ? ctz32_(n) : 32;
+}
+static inline int clz32(uint64_t n)
+{
+	return n ? clz32_(n) : 32;
+}
+
+#elif defined(_MSC_VER) && !defined(TIMEOUT_DISABLE_MSVC_BITOPS)
+
+/* On MSVC, we have these handy functions */
+
+static __inline int ctz64(uint64_t val)
+{
+	DWORD zeros = 0;
+	return _BitScanForward64(&zeros, val) ? zeros : 64;
+}
+static __inline int clz64(uint64_t val)
+{
+	DWORD zeros = 0;
+	return _BitScanReverse64(&zeros, val) ? zeros : 64;
+}
+static __inline int ctz32(unsigned long val)
+{
+	DWORD zeros = 0;
+	return _BitScanForward(&zeros, val) ? zeros : 32;
+}
+static __inline int clz32(unsigned long val)
+{
+	DWORD zeros = 0;
+	return _BitScanReverse(&zeros, val) ? zeros : 32;
+}
+
+/* End of MSVC case. */
+
+#else
+
+/* TODO: There are more clever ways to do this in the generic case. */
+
+
+#define process_(one, cz_bits, bits)					\
+	if (x < ( one << (cz_bits - bits))) { rv += bits; x <<= bits; }
+
+#define process64(bits) process_((UINT64_C(1)), 64, (bits))
+static inline int clz64(uint64_t x)
+{
+	int rv = 0;
+	if (!x)
+		return 64;
+
+	process64(32);
+	process64(16);
+	process64(8);
+	process64(4);
+	process64(2);
+	process64(1);
+	return rv;
+}
+#define process32(bits) process_((UINT32_C(1)), 32, (bits))
+static inline int clz32(uint32_t x)
+{
+	int rv = 0;
+	if (!x)
+		return 32;
+
+	process32(16);
+	process32(8);
+	process32(4);
+	process32(2);
+	process32(1);
+	return rv;
+}
+
+#undef process_
+#undef process32
+#undef process64
+#define process_(one, bits)						\
+	if ((x & ((one << (bits))-1)) == 0) { rv += bits; x >>= bits; }
+
+#define process64(bits) process_((UINT64_C(1)), bits)
+static inline int ctz64(uint64_t x)
+{
+	int rv = 0;
+	if (!x)
+		return 64;
+
+	process64(32);
+	process64(16);
+	process64(8);
+	process64(4);
+	process64(2);
+	process64(1);
+	return rv;
+}
+
+#define process32(bits) process_((UINT32_C(1)), bits)
+static inline int ctz32(uint32_t x)
+{
+	int rv = 0;
+	if (!x)
+		return 32;
+
+	process32(16);
+	process32(8);
+	process32(4);
+	process32(2);
+	process32(1);
+	return rv;
+}
+
+#undef process32
+#undef process64
+#undef process_
+
+/* End of generic case */
+
+#endif /* End of defining ctz */
+
+#ifdef TEST_BITOPS
+#include <stdio.h>
+#include <stdlib.h>
+
+static uint64_t testcases[] = {
+	13371337 * 10,
+	100,
+	385789752,
+	82574,
+	(((uint64_t)1)<<63) + (((uint64_t)1)<<31) + 10101
+};
+
+static int
+naive_clz(int bits, uint64_t v)
+{
+	int r = 0;
+	uint64_t bit = ((uint64_t)1) << (bits-1);
+	while (bit && 0 == (v & bit)) {
+		r++;
+		bit >>= 1;
+	}
+	/* printf("clz(%d,%lx) -> %d\n", bits, v, r); */
+	return r;
+}
+
+static int
+naive_ctz(int bits, uint64_t v)
+{
+	int r = 0;
+	uint64_t bit = 1;
+	while (bit && 0 == (v & bit)) {
+		r++;
+		bit <<= 1;
+		if (r == bits)
+			break;
+	}
+	/* printf("ctz(%d,%lx) -> %d\n", bits, v, r); */
+	return r;
+}
+
+static int
+check(uint64_t vv)
+{
+	uint32_t v32 = (uint32_t) vv;
+
+	if (ctz64(vv) != naive_ctz(64, vv)) {
+		printf("mismatch with ctz64: %d\n", ctz64(vv));
+				exit(1);
+		return 0;
+	}
+	if (clz64(vv) != naive_clz(64, vv)) {
+		printf("mismatch with clz64: %d\n", clz64(vv));
+				exit(1);
+		return 0;
+	}
+	if (ctz32(v32) != naive_ctz(32, v32)) {
+		printf("mismatch with ctz32: %d\n", ctz32(v32));
+		exit(1);
+		return 0;
+	}
+	if (clz32(v32) != naive_clz(32, v32)) {
+		printf("mismatch with clz32: %d\n", clz32(v32));
+				exit(1);
+		return 0;
+	}
+	return 1;
+}
+
+int
+main(int c, char **v)
+{
+	unsigned int i;
+	const unsigned int n = sizeof(testcases)/sizeof(testcases[0]);
+	int result = 0;
+
+	for (i = 0; i <= 63; ++i) {
+		uint64_t x = 1 << i;
+		if (!check(x))
+			result = 1;
+		--x;
+		if (!check(x))
+			result = 1;
+	}
+
+	for (i = 0; i < n; ++i) {
+		if (! check(testcases[i]))
+			result = 1;
+	}
+	if (result) {
+		puts("FAIL");
+	} else {
+		puts("OK");
+	}
+	return result;
+}
+#endif
+
diff --git a/timeout.c b/timeout.c
index fa23fc4..55a1789 100644
--- a/timeout.c
+++ b/timeout.c
@@ -122,17 +122,25 @@
 #define WHEEL_MASK (WHEEL_LEN - 1)
 #define TIMEOUT_MAX ((TIMEOUT_C(1) << (WHEEL_BIT * WHEEL_NUM)) - 1)
 
+#include "bitops.c"
+
 #if WHEEL_BIT == 6
+#define ctz(n) ctz64(n)
+#define clz(n) clz64(n)
+#define fls(n) ((int)(64 - clz64(n)))
+#else
+#define ctz(n) ctz32(n)
+#define clz(n) clz32(n)
+#define fls(n) ((int)(32 - clz32(n)))
+#endif
 
+#if WHEEL_BIT == 6
 #define WHEEL_C(n) UINT64_C(n)
 #define WHEEL_PRIu PRIu64
 #define WHEEL_PRIx PRIx64
 
 typedef uint64_t wheel_t;
 
-#define ctz(n) __builtin_ctzll(n)
-#define fls(n) ((int)(sizeof (long long) * CHAR_BIT) - __builtin_clzll(n))
-
 #elif WHEEL_BIT == 5
 
 #define WHEEL_C(n) UINT32_C(n)
@@ -141,9 +149,6 @@ typedef uint64_t wheel_t;
 
 typedef uint32_t wheel_t;
 
-#define ctz(n) __builtin_ctzl(n)
-#define fls(n) ((int)(sizeof (long) * CHAR_BIT) - __builtin_clzl(n))
-
 #elif WHEEL_BIT == 4
 
 #define WHEEL_C(n) UINT16_C(n)
@@ -152,9 +157,6 @@ typedef uint32_t wheel_t;
 
 typedef uint16_t wheel_t;
 
-#define ctz(n) __builtin_ctz(n)
-#define fls(n) ((int)(sizeof (int) * CHAR_BIT) - __builtin_clz(n))
-
 #elif WHEEL_BIT == 3
 
 #define WHEEL_C(n) UINT8_C(n)
@@ -163,9 +165,6 @@ typedef uint16_t wheel_t;
 
 typedef uint8_t wheel_t;
 
-#define ctz(n) __builtin_ctz(n)
-#define fls(n) ((int)(sizeof (int) * CHAR_BIT) - __builtin_clz(n))
-
 #else
 #error invalid WHEEL_BIT value
 #endif