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 "metaprogramming/isIntegral.hpp"
30 #include "metaprogramming/isSigned.hpp"
31 #include "utilities/count_leading_zeros.hpp"
32 #include "utilities/debug.hpp"
33 #include "utilities/globalDefinitions.hpp"
34
35 // Power of two convenience library.
36
37 template <typename T>
is_power_of_2(T x)38 bool is_power_of_2(T x) {
39 return (x > T(0)) && ((x & (x - 1)) == T(0));
40 }
41
42 // Log2 of a power of 2
exact_log2(intptr_t x)43 inline int exact_log2(intptr_t x) {
44 assert(is_power_of_2((uintptr_t)x), "x must be a power of 2: " INTPTR_FORMAT, x);
45
46 const int bits = sizeof x * BitsPerByte;
47 return bits - count_leading_zeros(x) - 1;
48 }
49
50 // Log2 of a power of 2
exact_log2_long(jlong x)51 inline int exact_log2_long(jlong x) {
52 assert(is_power_of_2((julong)x), "x must be a power of 2: " JLONG_FORMAT, x);
53
54 const int bits = sizeof x * BitsPerByte;
55 return bits - count_leading_zeros(x) - 1;
56 }
57
58 // Round down to the closest power of two greater to or equal to the given
59 // value.
60
61 // Signed version: 0 is an invalid input, negative values are invalid
62 template <typename T>
round_down_power_of_2(T value)63 inline typename EnableIf<IsSigned<T>::value, T>::type round_down_power_of_2(T value) {
64 STATIC_ASSERT(IsIntegral<T>::value);
65 assert(value > 0, "Invalid value");
66 uint32_t lz = count_leading_zeros(value);
67 assert(lz < sizeof(T) * BitsPerByte, "Sanity");
68 return T(1) << (sizeof(T) * BitsPerByte - 1 - lz);
69 }
70
71 // Unsigned version: 0 is an invalid input
72 template <typename T>
round_down_power_of_2(T value)73 inline typename EnableIf<!IsSigned<T>::value, T>::type round_down_power_of_2(T value) {
74 STATIC_ASSERT(IsIntegral<T>::value);
75 assert(value != 0, "Invalid value");
76 uint32_t lz = count_leading_zeros(value);
77 assert(lz < sizeof(T) * BitsPerByte, "Sanity");
78 return T(1) << (sizeof(T) * BitsPerByte - 1 - lz);
79 }
80
81 // Round up to the closest power of two greater to or equal to
82 // the given value.
83
84 // Signed version: 0 is an invalid input, negative values are invalid,
85 // overflows with assert if value is larger than 2^30 or 2^62 for 32- and
86 // 64-bit integers, respectively
87 template <typename T>
round_up_power_of_2(T value)88 inline typename EnableIf<IsSigned<T>::value, T>::type round_up_power_of_2(T value) {
89 STATIC_ASSERT(IsIntegral<T>::value);
90 STATIC_ASSERT(IsSigned<T>::value);
91 assert(value > 0, "Invalid value");
92 if (is_power_of_2(value)) {
93 return value;
94 }
95 uint32_t lz = count_leading_zeros(value);
96 assert(lz < sizeof(T) * BitsPerByte, "Sanity");
97 assert(lz > 1, "Will overflow");
98 return T(1) << (sizeof(T) * BitsPerByte - lz);
99 }
100
101 // Unsigned version: 0 is an invalid input, overflows with assert if value
102 // is larger than 2^31 or 2^63 for 32- and 64-bit integers, respectively
103 template <typename T>
round_up_power_of_2(T value)104 inline typename EnableIf<!IsSigned<T>::value, T>::type round_up_power_of_2(T value) {
105 STATIC_ASSERT(IsIntegral<T>::value);
106 STATIC_ASSERT(!IsSigned<T>::value);
107 assert(value != 0, "Invalid value");
108 if (is_power_of_2(value)) {
109 return value;
110 }
111 uint32_t lz = count_leading_zeros(value);
112 assert(lz < sizeof(T) * BitsPerByte, "Sanity");
113 assert(lz > 0, "Will overflow");
114 return T(1) << (sizeof(T) * BitsPerByte - lz);
115 }
116
117 // Helper function to get the maximum positive value. Implemented here
118 // since using std::numeric_limits<T>::max() seems problematic on some
119 // platforms.
120
max_value()121 template <typename T> T max_value() {
122 if (IsSigned<T>::value) {
123 // Highest positive power of two expressible in the type
124 uint64_t val = static_cast<T>(1) << (sizeof(T) * BitsPerByte - 2);
125 // Fill lower bits with ones
126 val |= val >> 1;
127 val |= val >> 2;
128 val |= val >> 4;
129 if (sizeof(T) >= 2) val |= val >> 8;
130 if (sizeof(T) >= 4) val |= val >> 16;
131 if (sizeof(T) == 8) val |= val >> 32;
132 return (T)val;
133 } else {
134 return ~(static_cast<T>(0));
135 }
136 }
137
138 // Calculate the next power of two greater than the given value.
139
140 // Accepts 0 (returns 1), overflows with assert if value is larger than
141 // or equal to 2^31 (signed: 2^30) or 2^63 (signed: 2^62), for 32-
142 // and 64-bit integers, respectively
143 template <typename T>
next_power_of_2(T value)144 inline T next_power_of_2(T value) {
145 assert(value != max_value<T>(), "Overflow");
146 return round_up_power_of_2(value + 1);
147 }
148
149 #endif // SHARE_UTILITIES_POWEROFTWO_HPP
150