Tor  0.4.6.0-alpha-dev
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 
clz32
static unsigned clz32(uint32_t x)
Definition: prob_distr.c:97
main
int main(int argc, char *argv[])
Definition: tor_main.c:25