Wireshark  4.3.0
The Wireshark network protocol analyzer
bits_ctz.h
Go to the documentation of this file.
1 
10 #ifndef __WSUTIL_BITS_CTZ_H__
11 #define __WSUTIL_BITS_CTZ_H__
12 
13 #include <inttypes.h>
14 
15 /* ws_ctz == trailing zeros == position of lowest set bit [0..63] */
16 /* ws_ilog2 == position of highest set bit == 63 - leading zeros [0..63] */
17 
18 /* The return value of both ws_ctz and ws_ilog2 is undefined for x == 0 */
19 
20 #if defined(__GNUC__) && ((__GNUC__ > 3) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4))
21 
22 static inline int
23 ws_ctz(uint64_t x)
24 {
25  return __builtin_ctzll(x);
26 }
27 
28 static inline int
29 ws_ilog2(uint64_t x)
30 {
31  return 63 - __builtin_clzll(x);
32 }
33 
34 #else
35 
36 static inline int
37 __ws_ctz32(uint32_t x)
38 {
39  /* From http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup */
40  static const uint8_t table[32] = {
41  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
42  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
43  };
44 
45  return table[((uint32_t)((x & -(int32_t)x) * 0x077CB531U)) >> 27];
46 }
47 
48 static inline int
49 ws_ctz(uint64_t x)
50 {
51  uint32_t hi = x >> 32;
52  uint32_t lo = (uint32_t) x;
53 
54  if (lo == 0)
55  return 32 + __ws_ctz32(hi);
56  else
57  return __ws_ctz32(lo);
58 }
59 
60 static inline int
61 __ws_ilog2_32(uint32_t x)
62 {
63  /* From http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn */
64  static const uint8_t table[32] = {
65  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
66  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
67  };
68 
69  x |= x >> 1;
70  x |= x >> 2;
71  x |= x >> 4;
72  x |= x >> 8;
73  x |= x >> 16;
74 
75  return table[((uint32_t)(x * 0x07C4ACDDU)) >> 27];
76 }
77 
78 static inline int
79 ws_ilog2(uint64_t x)
80 {
81  uint32_t hi = x >> 32;
82  uint32_t lo = (uint32_t) x;
83 
84  if (hi == 0)
85  return __ws_ilog2_32(lo);
86  else
87  return 32 + __ws_ilog2_32(hi);
88 }
89 
90 #endif
91 
92 #endif /* __WSUTIL_BITS_CTZ_H__ */