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