1 /*
2 * Copyright (c) 2019, 2020, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_UTILITIES_POWEROFTWO_HPP
26 #define SHARE_UTILITIES_POWEROFTWO_HPP
27
28 #include "metaprogramming/enableIf.hpp"
29 #include "utilities/count_leading_zeros.hpp"
30 #include "utilities/debug.hpp"
31 #include "utilities/globalDefinitions.hpp"
32 #include <limits>
33 #include <type_traits>
34
35 // Power of two convenience library.
36
37 template <typename T, ENABLE_IF(std::is_integral<T>::value)>
max_power_of_2()38 constexpr T max_power_of_2() {
39 T max_val = std::numeric_limits<T>::max();
40 return max_val - (max_val >> 1);
41 }
42
43 // Returns true iff there exists integer i such that (T(1) << i) == x.
44 template <typename T, ENABLE_IF(std::is_integral<T>::value)>
is_power_of_2(T x)45 constexpr bool is_power_of_2(T x) {
46 return (x > T(0)) && ((x & (x - 1)) == T(0));
47 }
48
49 // Log2 of a power of 2
exact_log2(intptr_t x)50 inline int exact_log2(intptr_t x) {
51 assert(is_power_of_2((uintptr_t)x), "x must be a power of 2: " INTPTR_FORMAT, x);
52
53 const int bits = sizeof x * BitsPerByte;
54 return bits - count_leading_zeros(x) - 1;
55 }
56
57 // Log2 of a power of 2
exact_log2_long(jlong x)58 inline int exact_log2_long(jlong x) {
59 assert(is_power_of_2((julong)x), "x must be a power of 2: " JLONG_FORMAT, x);
60
61 const int bits = sizeof x * BitsPerByte;
62 return bits - count_leading_zeros(x) - 1;
63 }
64
65 // Round down to the closest power of two less than or equal to the given value.
66 // precondition: value > 0.
67 template<typename T, ENABLE_IF(std::is_integral<T>::value)>
round_down_power_of_2(T value)68 inline T round_down_power_of_2(T value) {
69 assert(value > 0, "Invalid value");
70 uint32_t lz = count_leading_zeros(value);
71 return T(1) << (sizeof(T) * BitsPerByte - 1 - lz);
72 }
73
74 // Round up to the closest power of two greater to or equal to the given value.
75 // precondition: value > 0.
76 // precondition: value <= maximum power of two representable by T.
77 template<typename T, ENABLE_IF(std::is_integral<T>::value)>
round_up_power_of_2(T value)78 inline T round_up_power_of_2(T value) {
79 assert(value > 0, "Invalid value");
80 assert(value <= max_power_of_2<T>(), "Overflow");
81 if (is_power_of_2(value)) {
82 return value;
83 }
84 uint32_t lz = count_leading_zeros(value);
85 return T(1) << (sizeof(T) * BitsPerByte - lz);
86 }
87
88 // Calculate the next power of two greater than the given value.
89 // precondition: if signed, value >= 0.
90 // precondition: value < maximum power of two representable by T.
91 template <typename T, ENABLE_IF(std::is_integral<T>::value)>
next_power_of_2(T value)92 inline T next_power_of_2(T value) {
93 assert(value < std::numeric_limits<T>::max(), "Overflow");
94 return round_up_power_of_2(value + 1);
95 }
96
97 #endif // SHARE_UTILITIES_POWEROFTWO_HPP
98