src/ext/timeouts/timeout-bitops.c

   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
 255