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
27namespace 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 */
34constexpr 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 */
45constexpr 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 */
54template <typename T>
55constexpr 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 */
64constexpr 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 */
80constexpr 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 */
94constexpr 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
109template <typename T>
110T 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
122template <typename T>
123T 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 */
138inline 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
146template <typename T>
147inline 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