1//===----------------------------------------------------------------------===//
2// DuckDB
3//
4// duckdb/common/bit_utils.hpp
5//
6//
7//===----------------------------------------------------------------------===//
8
9#pragma once
10
11#include "duckdb/common/hugeint.hpp"
12
13#ifdef _MSC_VER
14#define __restrict__
15#define __BYTE_ORDER__ __ORDER_LITTLE_ENDIAN__
16#define __ORDER_LITTLE_ENDIAN__ 2
17#include <intrin.h>
18static inline int __builtin_ctzll(unsigned long long x) {
19#ifdef _WIN64
20 unsigned long ret;
21 _BitScanForward64(&ret, x);
22 return (int)ret;
23#else
24 unsigned long low, high;
25 bool low_set = _BitScanForward(&low, (unsigned __int32)(x)) != 0;
26 _BitScanForward(&high, (unsigned __int32)(x >> 32));
27 high += 32;
28 return low_set ? low : high;
29#endif
30}
31static inline int __builtin_clzll(unsigned long long mask) {
32 unsigned long where;
33// BitScanReverse scans from MSB to LSB for first set bit.
34// Returns 0 if no set bit is found.
35#if defined(_WIN64)
36 if (_BitScanReverse64(&where, mask))
37 return static_cast<int>(63 - where);
38#elif defined(_WIN32)
39 // Scan the high 32 bits.
40 if (_BitScanReverse(&where, static_cast<unsigned long>(mask >> 32)))
41 return static_cast<int>(63 - (where + 32)); // Create a bit offset from the MSB.
42 // Scan the low 32 bits.
43 if (_BitScanReverse(&where, static_cast<unsigned long>(mask)))
44 return static_cast<int>(63 - where);
45#else
46#error "Implementation of __builtin_clzll required"
47#endif
48 return 64; // Undefined Behavior.
49}
50
51static inline int __builtin_ctz(unsigned int value) {
52 unsigned long trailing_zero = 0;
53
54 if (_BitScanForward(&trailing_zero, value)) {
55 return trailing_zero;
56 } else {
57 // This is undefined, I better choose 32 than 0
58 return 32;
59 }
60}
61
62static inline int __builtin_clz(unsigned int value) {
63 unsigned long leading_zero = 0;
64
65 if (_BitScanReverse(&leading_zero, value)) {
66 return 31 - leading_zero;
67 } else {
68 // Same remarks as above
69 return 32;
70 }
71}
72
73#endif
74
75namespace duckdb {
76
77template <class T>
78struct CountZeros {};
79
80template <>
81struct CountZeros<uint32_t> {
82 inline static int Leading(uint32_t value) {
83 if (!value) {
84 return 32;
85 }
86 return __builtin_clz(value);
87 }
88 inline static int Trailing(uint32_t value) {
89 if (!value) {
90 return 32;
91 }
92 return __builtin_ctz(value);
93 }
94};
95
96template <>
97struct CountZeros<uint64_t> {
98 inline static int Leading(uint64_t value) {
99 if (!value) {
100 return 64;
101 }
102 return __builtin_clzll(value);
103 }
104 inline static int Trailing(uint64_t value) {
105 if (!value) {
106 return 64;
107 }
108 return __builtin_ctzll(value);
109 }
110};
111
112template <>
113struct CountZeros<hugeint_t> {
114 inline static int Leading(hugeint_t value) {
115 const uint64_t upper = (uint64_t)value.upper;
116 const uint64_t lower = value.lower;
117
118 if (upper) {
119 return __builtin_clzll(upper);
120 } else if (lower) {
121 return 64 + __builtin_clzll(lower);
122 } else {
123 return 128;
124 }
125 }
126
127 inline static int Trailing(hugeint_t value) {
128 const uint64_t upper = (uint64_t)value.upper;
129 const uint64_t lower = value.lower;
130
131 if (lower) {
132 return __builtin_ctzll(lower);
133 } else if (upper) {
134 return 64 + __builtin_ctzll(upper);
135 } else {
136 return 128;
137 }
138 }
139};
140
141} // namespace duckdb
142