9#if defined(__GNUC__) && !defined(TIMEOUT_DISABLE_GNUC_BITOPS)
12#define LONG_BIT (SIZEOF_LONG*CHAR_BIT)
18#define ctz64(n) __builtin_ctzll(n)
19#define clz64(n) __builtin_clzll(n)
21#define ctz32(n) __builtin_ctzl(n)
22#define clz32(n) __builtin_clzl(n)
24#define ctz32(n) __builtin_ctz(n)
25#define clz32(n) __builtin_clz(n)
28#elif defined(_MSC_VER) && !defined(TIMEOUT_DISABLE_MSVC_BITOPS)
33static __inline
int ctz32(
unsigned long val)
36 _BitScanForward(&zeros, val);
39static __inline
int clz32(
unsigned long val)
42 _BitScanReverse(&zeros, val);
47static __inline
int ctz64(uint64_t val)
50 _BitScanForward64(&zeros, val);
53static __inline
int clz64(uint64_t val)
56 _BitScanReverse64(&zeros, val);
60static __inline
int ctz64(uint64_t val)
62 uint32_t lo = (uint32_t) val;
63 uint32_t hi = (uint32_t) (val >> 32);
64 return lo ? ctz32(lo) : 32 + ctz32(hi);
66static __inline
int clz64(uint64_t val)
68 uint32_t lo = (uint32_t) val;
69 uint32_t hi = (uint32_t) (val >> 32);
81#define process_(one, cz_bits, bits) \
82 if (x < ( one << (cz_bits - bits))) { rv += bits; x <<= bits; }
84#define process64(bits) process_((UINT64_C(1)), 64, (bits))
85static inline int clz64(uint64_t x)
97#define process32(bits) process_((UINT32_C(1)), 32, (bits))
98static inline int clz32(uint32_t x)
113#define process_(one, bits) \
114 if ((x & ((one << (bits))-1)) == 0) { rv += bits; x >>= bits; }
116#define process64(bits) process_((UINT64_C(1)), bits)
117static inline int ctz64(uint64_t x)
130#define process32(bits) process_((UINT32_C(1)), bits)
131static inline int ctz32(uint32_t x)
155static uint64_t testcases[] = {
160 (((uint64_t)1)<<63) + (((uint64_t)1)<<31) + 10101
164naive_clz(
int bits, uint64_t v)
167 uint64_t bit = ((uint64_t)1) << (bits-1);
168 while (bit && 0 == (v & bit)) {
177naive_ctz(
int bits, uint64_t v)
181 while (bit && 0 == (v & bit)) {
194 uint32_t v32 = (uint32_t) vv;
199 if (ctz64(vv) != naive_ctz(64, vv)) {
200 printf(
"mismatch with ctz64: %d\n", ctz64(vv));
204 if (clz64(vv) != naive_clz(64, vv)) {
205 printf(
"mismatch with clz64: %d\n", clz64(vv));
213 if (ctz32(v32) != naive_ctz(32, v32)) {
214 printf(
"mismatch with ctz32: %d\n", ctz32(v32));
218 if (
clz32(v32) != naive_clz(32, v32)) {
219 printf(
"mismatch with clz32: %d\n",
clz32(v32));
230 const unsigned int n =
sizeof(testcases)/
sizeof(testcases[0]);
233 for (i = 0; i <= 63; ++i) {
243 for (i = 0; i < n; ++i) {
244 if (! check(testcases[i]))
static unsigned clz32(uint32_t x)
int main(int argc, char *argv[])