1 /**
2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15 #ifndef PANDA_LIBBASE_UTILS_MATH_HELPERS_H_
16 #define PANDA_LIBBASE_UTILS_MATH_HELPERS_H_
17
18 #include "bit_utils.h"
19 #include "macros.h"
20
21 #include <array>
22 #include <climits>
23 #include <cstdint>
24 #include <cmath>
25
26 namespace ark::helpers::math {
27
28 /**
29 * @brief returns log2 for argument
30 * @param X - should be power of 2
31 * @return log2(X) or undefined if X 0
32 */
GetIntLog2(const uint32_t x)33 constexpr uint32_t GetIntLog2(const uint32_t x)
34 {
35 ASSERT((x > 0) && !(x & (x - 1U)));
36 return static_cast<uint32_t>(PANDA_BIT_UTILS_CTZ(x));
37 }
38
39 /**
40 * @brief returns log2 for argument
41 * @param X - of type uint64_t, should be power of 2
42 * @return log2(X) or undefined if X 0
43 */
GetIntLog2(const uint64_t x)44 constexpr uint64_t GetIntLog2(const uint64_t x)
45 {
46 ASSERT((x > 0) && !(x & (x - 1U)));
47 return static_cast<uint64_t>(PANDA_BIT_UTILS_CTZLL(x));
48 }
49
50 template <typename T>
AbsOrMin(T v)51 inline constexpr T AbsOrMin(T v)
52 {
53 static_assert(std::is_integral_v<T> && std::is_signed_v<T>);
54 if (UNLIKELY(v == std::numeric_limits<T>::min())) {
55 return v;
56 }
57 return std::abs(v);
58 }
59
60 /// return value is power of two
61 template <typename T>
IsPowerOfTwo(T value)62 inline constexpr bool IsPowerOfTwo(T value)
63 {
64 static_assert(std::is_integral_v<T>);
65 if constexpr (std::is_unsigned_v<T>) {
66 return (value != 0U) && (value & (value - 1U)) == 0U;
67 } else {
68 using UT = std::make_unsigned_t<T>;
69 auto absValue = bit_cast<UT>(AbsOrMin(value));
70 return (absValue != 0U) && (absValue & (absValue - 1U)) == 0U;
71 }
72 }
73
74 /// returns an integer power of two but not greater than value.
GetPowerOfTwoValue32(uint32_t value)75 constexpr uint32_t GetPowerOfTwoValue32(uint32_t value)
76 {
77 ASSERT(value < (1UL << 31UL));
78 if (value > 0) {
79 --value;
80 }
81 if (value == 0) {
82 return 1;
83 }
84 constexpr uint32_t BIT = 32UL;
85 return 1UL << (BIT - Clz(static_cast<uint32_t>(value)));
86 }
87
88 /// Count trailing zeroes
Ctz(uint32_t value)89 constexpr unsigned int Ctz(uint32_t value)
90 {
91 constexpr std::array<uint32_t, 32> MULTIPLY_DE_BRUIJN_BIT_POSITION = {0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20,
92 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
93 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
94 constexpr size_t SHIFT = 27;
95 constexpr size_t C = 0x077CB531;
96 return MULTIPLY_DE_BRUIJN_BIT_POSITION[(static_cast<uint32_t>((value & static_cast<uint32_t>(-value)) * C)) >>
97 SHIFT];
98 }
99
100 /// Count leading zeroes
Clz(uint32_t value)101 constexpr uint32_t Clz(uint32_t value)
102 {
103 constexpr std::array<uint32_t, 32> MULTIPLY_DE_BRUIJN_BIT_POSITION = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16,
104 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17,
105 24, 7, 19, 27, 23, 6, 26, 5, 4, 31};
106 constexpr size_t BIT32 = 32;
107 constexpr size_t SHIFT = 27;
108 value |= value >> 1U;
109 value |= value >> 2U;
110 value |= value >> 4U;
111 value |= value >> 8U; // NOLINT(readability-magic-numbers)
112 value |= value >> 16U; // NOLINT(readability-magic-numbers)
113 return BIT32 - 1 - MULTIPLY_DE_BRUIJN_BIT_POSITION[static_cast<uint32_t>(value * 0x07C4ACDDU) >> SHIFT]; // NOLINT
114 }
115
116 template <typename T>
Min(T a,T b)117 T Min(T a, T b)
118 {
119 static_assert(std::is_floating_point_v<T>);
120 if (std::isnan(a)) {
121 return a;
122 }
123 if (a == 0.0 && b == 0.0 && std::signbit(b)) {
124 return b;
125 }
126 return a <= b ? a : b;
127 }
128
129 template <typename T>
Max(T a,T b)130 T Max(T a, T b)
131 {
132 static_assert(std::is_floating_point_v<T>);
133 if (std::isnan(a)) {
134 return a;
135 }
136 if (a == 0.0 && b == 0.0 && std::signbit(a)) {
137 return b;
138 }
139 return a >= b ? a : b;
140 }
141
142 /// Combine lhash and rhash
MergeHashes(size_t lhash,size_t rhash)143 inline size_t MergeHashes(size_t lhash, size_t rhash)
144 {
145 constexpr const size_t MAGIC_CONSTANT = 0x9e3779b9;
146 size_t shl = lhash << 6U;
147 size_t shr = lhash >> 2U;
148 return lhash ^ (rhash + MAGIC_CONSTANT + shl + shr);
149 }
150
151 template <typename T>
152 inline T PowerOfTwoTableSlot(T key, T tableSize, uint32_t skippedLowestBits = 0)
153 {
154 ASSERT(IsPowerOfTwo(tableSize));
155 return (key >> skippedLowestBits) & (tableSize - 1);
156 }
157
158 } // namespace ark::helpers::math
159
160 #endif // PANDA_LIBBASE_UTILS_MATH_HELPERS_H_
161