timeout-bitops.c 4.7 KB

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