timeout-bitops.c (4823B)
1 #include <stdint.h> 2 #include <limits.h> 3 #ifdef _MSC_VER 4 #include <intrin.h> /* _BitScanForward, _BitScanReverse */ 5 #endif 6 7 /* First define ctz and clz functions; these are compiler-dependent if 8 * you want them to be fast. */ 9 #if defined(__GNUC__) && !defined(TIMEOUT_DISABLE_GNUC_BITOPS) 10 11 #ifndef LONG_BIT 12 #define LONG_BIT (SIZEOF_LONG*CHAR_BIT) 13 #endif 14 15 /* On GCC and clang and some others, we can use __builtin functions. They 16 * are not defined for n==0, but timeout.s never calls them with n==0. */ 17 18 #define ctz64(n) __builtin_ctzll(n) 19 #define clz64(n) __builtin_clzll(n) 20 #if LONG_BIT == 32 21 #define ctz32(n) __builtin_ctzl(n) 22 #define clz32(n) __builtin_clzl(n) 23 #else 24 #define ctz32(n) __builtin_ctz(n) 25 #define clz32(n) __builtin_clz(n) 26 #endif 27 28 #elif defined(_MSC_VER) && !defined(TIMEOUT_DISABLE_MSVC_BITOPS) 29 30 /* On MSVC, we have these handy functions. We can ignore their return 31 * values, since we will never supply val == 0. */ 32 33 static __inline int ctz32(unsigned long val) 34 { 35 DWORD zeros = 0; 36 _BitScanForward(&zeros, val); 37 return zeros; 38 } 39 static __inline int clz32(unsigned long val) 40 { 41 DWORD zeros = 0; 42 _BitScanReverse(&zeros, val); 43 return 31 - zeros; 44 } 45 #ifdef _WIN64 46 /* According to the documentation, these only exist on Win64. */ 47 static __inline int ctz64(uint64_t val) 48 { 49 DWORD zeros = 0; 50 _BitScanForward64(&zeros, val); 51 return zeros; 52 } 53 static __inline int clz64(uint64_t val) 54 { 55 DWORD zeros = 0; 56 _BitScanReverse64(&zeros, val); 57 return 63 - zeros; 58 } 59 #else 60 static __inline int ctz64(uint64_t val) 61 { 62 uint32_t lo = (uint32_t) val; 63 uint32_t hi = (uint32_t) (val >> 32); 64 return lo ? ctz32(lo) : 32 + ctz32(hi); 65 } 66 static __inline int clz64(uint64_t val) 67 { 68 uint32_t lo = (uint32_t) val; 69 uint32_t hi = (uint32_t) (val >> 32); 70 return hi ? clz32(hi) : 32 + clz32(lo); 71 } 72 #endif 73 74 /* End of MSVC case. */ 75 76 #else 77 78 /* TODO: There are more clever ways to do this in the generic case. */ 79 80 81 #define process_(one, cz_bits, bits) \ 82 if (x < ( one << (cz_bits - bits))) { rv += bits; x <<= bits; } 83 84 #define process64(bits) process_((UINT64_C(1)), 64, (bits)) 85 static inline int clz64(uint64_t x) 86 { 87 int rv = 0; 88 89 process64(32); 90 process64(16); 91 process64(8); 92 process64(4); 93 process64(2); 94 process64(1); 95 return rv; 96 } 97 #define process32(bits) process_((UINT32_C(1)), 32, (bits)) 98 static inline int clz32(uint32_t x) 99 { 100 int rv = 0; 101 102 process32(16); 103 process32(8); 104 process32(4); 105 process32(2); 106 process32(1); 107 return rv; 108 } 109 110 #undef process_ 111 #undef process32 112 #undef process64 113 #define process_(one, bits) \ 114 if ((x & ((one << (bits))-1)) == 0) { rv += bits; x >>= bits; } 115 116 #define process64(bits) process_((UINT64_C(1)), bits) 117 static inline int ctz64(uint64_t x) 118 { 119 int rv = 0; 120 121 process64(32); 122 process64(16); 123 process64(8); 124 process64(4); 125 process64(2); 126 process64(1); 127 return rv; 128 } 129 130 #define process32(bits) process_((UINT32_C(1)), bits) 131 static inline int ctz32(uint32_t x) 132 { 133 int rv = 0; 134 135 process32(16); 136 process32(8); 137 process32(4); 138 process32(2); 139 process32(1); 140 return rv; 141 } 142 143 #undef process32 144 #undef process64 145 #undef process_ 146 147 /* End of generic case */ 148 149 #endif /* End of defining ctz */ 150 151 #ifdef TEST_BITOPS 152 #include <stdio.h> 153 #include <stdlib.h> 154 155 static uint64_t testcases[] = { 156 13371337 * 10, 157 100, 158 385789752, 159 82574, 160 (((uint64_t)1)<<63) + (((uint64_t)1)<<31) + 10101 161 }; 162 163 static int 164 naive_clz(int bits, uint64_t v) 165 { 166 int r = 0; 167 uint64_t bit = ((uint64_t)1) << (bits-1); 168 while (bit && 0 == (v & bit)) { 169 r++; 170 bit >>= 1; 171 } 172 /* printf("clz(%d,%lx) -> %d\n", bits, v, r); */ 173 return r; 174 } 175 176 static int 177 naive_ctz(int bits, uint64_t v) 178 { 179 int r = 0; 180 uint64_t bit = 1; 181 while (bit && 0 == (v & bit)) { 182 r++; 183 bit <<= 1; 184 if (r == bits) 185 break; 186 } 187 /* printf("ctz(%d,%lx) -> %d\n", bits, v, r); */ 188 return r; 189 } 190 191 static int 192 check(uint64_t vv) 193 { 194 uint32_t v32 = (uint32_t) vv; 195 196 if (vv == 0) 197 return 1; /* c[tl]z64(0) is undefined. */ 198 199 if (ctz64(vv) != naive_ctz(64, vv)) { 200 printf("mismatch with ctz64: %d\n", ctz64(vv)); 201 exit(1); 202 return 0; 203 } 204 if (clz64(vv) != naive_clz(64, vv)) { 205 printf("mismatch with clz64: %d\n", clz64(vv)); 206 exit(1); 207 return 0; 208 } 209 210 if (v32 == 0) 211 return 1; /* c[lt]z(0) is undefined. */ 212 213 if (ctz32(v32) != naive_ctz(32, v32)) { 214 printf("mismatch with ctz32: %d\n", ctz32(v32)); 215 exit(1); 216 return 0; 217 } 218 if (clz32(v32) != naive_clz(32, v32)) { 219 printf("mismatch with clz32: %d\n", clz32(v32)); 220 exit(1); 221 return 0; 222 } 223 return 1; 224 } 225 226 int 227 main(int c, char **v) 228 { 229 unsigned int i; 230 const unsigned int n = sizeof(testcases)/sizeof(testcases[0]); 231 int result = 0; 232 233 for (i = 0; i <= 63; ++i) { 234 uint64_t x = 1; 235 x <<= i; 236 if (!check(x)) 237 result = 1; 238 --x; 239 if (!check(x)) 240 result = 1; 241 } 242 243 for (i = 0; i < n; ++i) { 244 if (! check(testcases[i])) 245 result = 1; 246 } 247 if (result) { 248 puts("FAIL"); 249 } else { 250 puts("OK"); 251 } 252 return result; 253 } 254 #endif