1 | /* Copyright 2019 Google LLC. All Rights Reserved. |
2 | |
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 RUY_RUY_SIZE_UTIL_H_ |
17 | #define RUY_RUY_SIZE_UTIL_H_ |
18 | |
19 | #include <type_traits> |
20 | |
21 | #include "ruy/check_macros.h" |
22 | |
23 | #ifdef _WIN32 |
24 | #include <intrin.h> |
25 | #endif |
26 | |
27 | namespace ruy { |
28 | |
29 | template <typename Integer> |
30 | inline Integer floor_log2(Integer n) { |
31 | static_assert(std::is_integral<Integer>::value, "" ); |
32 | static_assert(std::is_signed<Integer>::value, "" ); |
33 | static_assert(sizeof(Integer) == 4 || sizeof(Integer) == 8, "" ); |
34 | |
35 | RUY_DCHECK_GE(n, 1); |
36 | #ifdef _MSC_VER |
37 | unsigned long result; // NOLINT[runtime/int] |
38 | if (sizeof(Integer) == 4) { |
39 | _BitScanReverse(&result, n); |
40 | } else { |
41 | #if defined(_M_X64) || defined(_M_ARM64) |
42 | // _BitScanReverse64 is supported only on 64-bit MSVC platforms |
43 | _BitScanReverse64(&result, static_cast<unsigned __int64>(n)); |
44 | #else |
45 | // Emulate using 32-bit _BitScanReverse |
46 | const uint32_t n_hi = uint64_t(n) >> 32; |
47 | if (n_hi == 0) { |
48 | _BitScanReverse(&result, static_cast<unsigned long>(n)); |
49 | } else { |
50 | _BitScanReverse(&result, static_cast<unsigned long>(n_hi)); |
51 | result += 32; |
52 | } |
53 | #endif // defined(_M_X64) || defined(_M_ARM64) |
54 | } |
55 | return result; |
56 | #else |
57 | if (sizeof(Integer) == 4) { |
58 | return 31 - __builtin_clz(n); |
59 | } else { |
60 | return 63 - __builtin_clzll(n); |
61 | } |
62 | #endif |
63 | } |
64 | |
65 | template <typename Integer> |
66 | Integer ceil_log2(Integer n) { |
67 | RUY_DCHECK_GE(n, 1); |
68 | return n == 1 ? 0 : floor_log2(n - 1) + 1; |
69 | } |
70 | |
71 | template <typename Integer> |
72 | constexpr bool is_pot(Integer value) { |
73 | return (value > 0) && ((value & (value - 1)) == 0); |
74 | } |
75 | |
76 | template <typename Integer> |
77 | Integer pot_log2(Integer n) { |
78 | RUY_DCHECK(is_pot(n)); |
79 | return floor_log2(n); |
80 | } |
81 | |
82 | template <typename Integer> |
83 | Integer round_down_pot(Integer value) { |
84 | return static_cast<Integer>(1) << floor_log2(value); |
85 | } |
86 | |
87 | template <typename Integer> |
88 | Integer round_up_pot(Integer value) { |
89 | return static_cast<Integer>(1) << ceil_log2(value); |
90 | } |
91 | |
92 | template <typename Integer, typename Modulo> |
93 | Integer round_down_pot(Integer value, Modulo modulo) { |
94 | RUY_DCHECK_EQ(modulo & (modulo - 1), 0); |
95 | return value & ~(modulo - 1); |
96 | } |
97 | |
98 | template <typename Integer, typename Modulo> |
99 | Integer round_up_pot(Integer value, Modulo modulo) { |
100 | return round_down_pot(value + modulo - 1, modulo); |
101 | } |
102 | |
103 | } // namespace ruy |
104 | |
105 | #endif // RUY_RUY_SIZE_UTIL_H_ |
106 | |