| Wireshark 4.7.3 The Wireshark network protocol analyzer

Loading...
Searching...
No Matches
bits_ctz.h
Go to the documentation of this file.
1
9
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
23ws_ctz(uint64_t x)
24{
25 return __builtin_ctzll(x);
26}
27
28 static inline int
29ws_ilog2(uint64_t x)
30{
31 return 63 - __builtin_clzll(x);
32}
33
34#else
35
44 static inline int
45__ws_ctz32(uint32_t x)
46{
47 /* From http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup */
48 static const uint8_t table[32] = {
49 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
50 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
51 };
52
53 return table[((uint32_t)((x & -(int32_t)x) * 0x077CB531U)) >> 27];
54}
55
67 static inline int
68ws_ctz(uint64_t x)
69{
70 uint32_t hi = x >> 32;
71 uint32_t lo = (uint32_t) x;
72
73 if (lo == 0)
74 return 32 + __ws_ctz32(hi);
75 else
76 return __ws_ctz32(lo);
77}
78
88 static inline int
89__ws_ilog2_32(uint32_t x)
90{
91 /* From http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn */
92 static const uint8_t table[32] = {
93 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
94 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
95 };
96
97 x |= x >> 1;
98 x |= x >> 2;
99 x |= x >> 4;
100 x |= x >> 8;
101 x |= x >> 16;
102
103 return table[((uint32_t)(x * 0x07C4ACDDU)) >> 27];
104}
105
116 static inline int
117ws_ilog2(uint64_t x)
118{
119 uint32_t hi = x >> 32;
120 uint32_t lo = (uint32_t) x;
121
122 if (hi == 0)
123 return __ws_ilog2_32(lo);
124 else
125 return 32 + __ws_ilog2_32(hi);
126}
127
128#endif
129
130#endif /* __WSUTIL_BITS_CTZ_H__ */