| Wireshark 4.7.0 The Wireshark network protocol analyzer

Loading...
Searching...
No Matches
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
22static inline int
23ws_ctz(uint64_t x)
24{
25 return __builtin_ctzll(x);
26}
27
28static inline int
29ws_ilog2(uint64_t x)
30{
31 return 63 - __builtin_clzll(x);
32}
33
34#else
35
36static 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
48static inline int
49ws_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
60static 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
78static inline int
79ws_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__ */