1 /**
2 * Copyright (c) 2021-2022 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
16 #ifndef LIBPANDABASE_UTILS_MATH_HELPERS_H
17 #define LIBPANDABASE_UTILS_MATH_HELPERS_H
18
19 #include "bit_utils.h"
20 #include "macros.h"
21
22 #include <array>
23 #include <climits>
24 #include <cstdint>
25 #include <cmath>
26
27 namespace panda::helpers::math {
28
29 /**
30 * \brief returns log2 for argument
31 * @param X - should be power of 2
32 * @return log2(X) or undefined if X 0
33 */
GetIntLog2(const uint32_t X)34 constexpr uint32_t GetIntLog2(const uint32_t X)
35 {
36 ASSERT((X > 0) && !(X & (X - 1U)));
37 return static_cast<uint32_t>(panda_bit_utils_ctz(X));
38 }
39
40 /**
41 * \brief returns log2 for argument
42 * @param X - of type uint64_t, should be power of 2
43 * @return log2(X) or undefined if X 0
44 */
GetIntLog2(const uint64_t X)45 constexpr uint64_t GetIntLog2(const uint64_t X)
46 {
47 ASSERT((X > 0) && !(X & (X - 1U)));
48 return static_cast<uint64_t>(panda_bit_utils_ctzll(X));
49 }
50
51 /**
52 * return value is power of two
53 */
54 template <typename T>
IsPowerOfTwo(T value)55 constexpr bool IsPowerOfTwo(T value)
56 {
57 ASSERT(value > 0);
58 return (value & (value - 1)) == 0;
59 }
60
61 /**
62 * returns an integer power of two but not greater than value.
63 */
GetPowerOfTwoValue32(uint32_t value)64 constexpr uint32_t GetPowerOfTwoValue32(uint32_t value)
65 {
66 ASSERT(value < (1UL << 31UL));
67 if (value > 0) {
68 --value;
69 }
70 if (value == 0) {
71 return 1;
72 }
73 constexpr uint32_t BIT = 32UL;
74 return 1UL << (BIT - Clz(static_cast<uint32_t>(value)));
75 }
76
77 /**
78 * Count trailing zeroes
79 */
Ctz(uint32_t value)80 constexpr unsigned int Ctz(uint32_t value)
81 {
82 constexpr std::array<uint32_t, 32> MULTIPLY_DE_BRUIJN_BIT_POSITION = {0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20,
83 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
84 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
85 constexpr size_t SHIFT = 27;
86 constexpr size_t C = 0x077CB531;
87 return MULTIPLY_DE_BRUIJN_BIT_POSITION[(static_cast<uint32_t>((value & static_cast<uint32_t>(-value)) * C)) >>
88 SHIFT];
89 }
90
91 /**
92 * Count leading zeroes
93 */
Clz(uint32_t value)94 constexpr uint32_t Clz(uint32_t value)
95 {
96 constexpr std::array<uint32_t, 32> MULTIPLY_DE_BRUIJN_BIT_POSITION = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16,
97 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17,
98 24, 7, 19, 27, 23, 6, 26, 5, 4, 31};
99 constexpr size_t BIT32 = 32;
100 constexpr size_t SHIFT = 27;
101 value |= value >> 1U;
102 value |= value >> 2U;
103 value |= value >> 4U;
104 value |= value >> 8U; // NOLINT(readability-magic-numbers)
105 value |= value >> 16U; // NOLINT(readability-magic-numbers)
106 return BIT32 - 1 - MULTIPLY_DE_BRUIJN_BIT_POSITION[static_cast<uint32_t>(value * 0x07C4ACDDU) >> SHIFT]; // NOLINT
107 }
108
109 template <typename T>
min(T a,T b)110 T min(T a, T b)
111 {
112 static_assert(std::is_floating_point_v<T>);
113 if (std::isnan(a)) {
114 return a;
115 }
116 if (a == 0.0 && b == 0.0 && std::signbit(b)) {
117 return b;
118 }
119 return a <= b ? a : b;
120 }
121
122 template <typename T>
max(T a,T b)123 T max(T a, T b)
124 {
125 static_assert(std::is_floating_point_v<T>);
126 if (std::isnan(a)) {
127 return a;
128 }
129 if (a == 0.0 && b == 0.0 && std::signbit(a)) {
130 return b;
131 }
132 return a >= b ? a : b;
133 }
134
135 /**
136 * Combine lhash and rhash
137 */
merge_hashes(size_t lhash,size_t rhash)138 inline size_t merge_hashes(size_t lhash, size_t rhash)
139 {
140 constexpr const size_t magic_constant = 0x9e3779b9;
141 size_t shl = lhash << 6U;
142 size_t shr = lhash >> 2U;
143 return lhash ^ (rhash + magic_constant + shl + shr);
144 }
145
146 template <typename T>
147 inline T PowerOfTwoTableSlot(T key, T table_size, uint32_t skipped_lowest_bits = 0)
148 {
149 ASSERT(IsPowerOfTwo(table_size));
150 return (key >> skipped_lowest_bits) & (table_size - 1);
151 }
152
153 } // namespace panda::helpers::math
154
155 #endif // LIBPANDABASE_UTILS_MATH_HELPERS_H
156