1 /*
2 * Copyright (c) 2019, 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 #include "precompiled.hpp"
25
26 #include "utilities/globalDefinitions.hpp"
27 #include "utilities/powerOfTwo.hpp"
28 #include "unittest.hpp"
29
30 template <typename T> T max_pow2() {
31 T max_val = max_value<T>();
32 return max_val - (max_val >> 1);
33 }
34
35 template <typename T> static void test_is_power_of_2() {
36 EXPECT_FALSE(is_power_of_2(T(0)));
37 EXPECT_FALSE(is_power_of_2(~T(0)));
38
39 // Test true
40 for (T i = max_pow2<T>(); i > 0; i = (i >> 1)) {
41 EXPECT_TRUE(is_power_of_2(i)) << "value = " << T(i);
42 }
43
44 // Test one less
45 for (T i = max_pow2<T>(); i > 2; i = (i >> 1)) {
46 EXPECT_FALSE(is_power_of_2(i - 1)) << "value = " << T(i - 1);
47 }
48
49 // Test one more
50 for (T i = max_pow2<T>(); i > 1; i = (i >> 1)) {
51 EXPECT_FALSE(is_power_of_2(i + 1)) << "value = " << T(i + 1);
52 }
53 }
54
55 TEST(power_of_2, is_power_of_2) {
56 test_is_power_of_2<int8_t>();
57 test_is_power_of_2<int16_t>();
58 test_is_power_of_2<int32_t>();
59 test_is_power_of_2<int64_t>();
60 test_is_power_of_2<int8_t>();
61 test_is_power_of_2<int16_t>();
62 test_is_power_of_2<int32_t>();
63 test_is_power_of_2<int64_t>();
64
65 test_is_power_of_2<jint>();
66 test_is_power_of_2<jlong>();
67 }
68
69 template <typename T> void round_up_power_of_2() {
70 EXPECT_EQ(round_up_power_of_2(T(1)), T(1)) << "value = " << T(1);
71 EXPECT_EQ(round_up_power_of_2(T(2)), T(2)) << "value = " << T(2);
72 EXPECT_EQ(round_up_power_of_2(T(3)), T(4)) << "value = " << T(3);
73 EXPECT_EQ(round_up_power_of_2(T(4)), T(4)) << "value = " << T(4);
74 EXPECT_EQ(round_up_power_of_2(T(5)), T(8)) << "value = " << T(5);
75 EXPECT_EQ(round_up_power_of_2(T(6)), T(8)) << "value = " << T(6);
76 EXPECT_EQ(round_up_power_of_2(T(7)), T(8)) << "value = " << T(7);
77 EXPECT_EQ(round_up_power_of_2(T(8)), T(8)) << "value = " << T(8);
78 EXPECT_EQ(round_up_power_of_2(T(9)), T(16)) << "value = " << T(9);
79 EXPECT_EQ(round_up_power_of_2(T(10)), T(16)) << "value = " << T(10);
80
81 T t_max_pow2 = max_pow2<T>();
82
83 // round_up(any power of two) should return input
84 for (T pow2 = T(1); pow2 < t_max_pow2; pow2 *= 2) {
85 EXPECT_EQ(pow2, round_up_power_of_2(pow2))
86 << "value = " << pow2;
87 }
88 EXPECT_EQ(round_up_power_of_2(t_max_pow2), t_max_pow2)
89 << "value = " << (t_max_pow2);
90
91 // For each pow2 gt 2, round_up(pow2 - 1) should return pow2
92 for (T pow2 = T(4); pow2 < t_max_pow2; pow2 *= 2) {
93 EXPECT_EQ(pow2, round_up_power_of_2(pow2 - 1))
94 << "value = " << pow2;
95 }
96 EXPECT_EQ(round_up_power_of_2(t_max_pow2 - 1), t_max_pow2)
97 << "value = " << (t_max_pow2 - 1);
98
99 }
100
101 TEST(power_of_2, round_up_power_of_2) {
102 round_up_power_of_2<int8_t>();
103 round_up_power_of_2<int16_t>();
104 round_up_power_of_2<int32_t>();
105 round_up_power_of_2<int64_t>();
106 round_up_power_of_2<uint8_t>();
107 round_up_power_of_2<uint16_t>();
108 round_up_power_of_2<uint32_t>();
109 round_up_power_of_2<uint64_t>();
110 }
111
112 template <typename T> void round_down_power_of_2() {
113 EXPECT_EQ(round_down_power_of_2(T(1)), T(1)) << "value = " << T(1);
114 EXPECT_EQ(round_down_power_of_2(T(2)), T(2)) << "value = " << T(2);
115 EXPECT_EQ(round_down_power_of_2(T(3)), T(2)) << "value = " << T(3);
116 EXPECT_EQ(round_down_power_of_2(T(4)), T(4)) << "value = " << T(4);
117 EXPECT_EQ(round_down_power_of_2(T(5)), T(4)) << "value = " << T(5);
118 EXPECT_EQ(round_down_power_of_2(T(6)), T(4)) << "value = " << T(6);
119 EXPECT_EQ(round_down_power_of_2(T(7)), T(4)) << "value = " << T(7);
120 EXPECT_EQ(round_down_power_of_2(T(8)), T(8)) << "value = " << T(8);
121 EXPECT_EQ(round_down_power_of_2(T(9)), T(8)) << "value = " << T(9);
122 EXPECT_EQ(round_down_power_of_2(T(10)), T(8)) << "value = " << T(10);
123
124 T t_max_pow2 = max_pow2<T>();
125
126 // For each pow2 >= 2:
127 // - round_down(pow2) should return pow2
128 // - round_down(pow2 + 1) should return pow2
129 // - round_down(pow2 - 1) should return pow2 / 2
130 for (T pow2 = T(2); pow2 < t_max_pow2; pow2 = pow2 * 2) {
131 EXPECT_EQ(pow2, round_down_power_of_2(pow2))
132 << "value = " << pow2;
133 EXPECT_EQ(pow2, round_down_power_of_2(pow2 + 1))
134 << "value = " << pow2;
135 EXPECT_EQ(pow2 / 2, round_down_power_of_2(pow2 - 1))
136 << "value = " << (pow2 / 2);
137 }
138 EXPECT_EQ(round_down_power_of_2(t_max_pow2), t_max_pow2)
139 << "value = " << (t_max_pow2);
140 EXPECT_EQ(round_down_power_of_2(t_max_pow2 + 1), t_max_pow2)
141 << "value = " << (t_max_pow2 + 1);
142 EXPECT_EQ(round_down_power_of_2(t_max_pow2 - 1), t_max_pow2 / 2)
143 << "value = " << (t_max_pow2 - 1);
144 }
145
146 TEST(power_of_2, round_down_power_of_2) {
147 round_down_power_of_2<int8_t>();
148 round_down_power_of_2<int16_t>();
149 round_down_power_of_2<int32_t>();
150 round_down_power_of_2<int64_t>();
151 round_down_power_of_2<uint8_t>();
152 round_down_power_of_2<uint16_t>();
153 round_down_power_of_2<uint32_t>();
154 round_down_power_of_2<uint64_t>();
155 }
156
157 template <typename T> void next_power_of_2() {
158 EXPECT_EQ(next_power_of_2(T(0)), T(1)) << "value = " << T(0);
159 EXPECT_EQ(next_power_of_2(T(1)), T(2)) << "value = " << T(1);
160 EXPECT_EQ(next_power_of_2(T(2)), T(4)) << "value = " << T(2);
161 EXPECT_EQ(next_power_of_2(T(3)), T(4)) << "value = " << T(3);
162 EXPECT_EQ(next_power_of_2(T(4)), T(8)) << "value = " << T(4);
163 EXPECT_EQ(next_power_of_2(T(5)), T(8)) << "value = " << T(5);
164 EXPECT_EQ(next_power_of_2(T(6)), T(8)) << "value = " << T(6);
165 EXPECT_EQ(next_power_of_2(T(7)), T(8)) << "value = " << T(7);
166 EXPECT_EQ(next_power_of_2(T(8)), T(16)) << "value = " << T(8);
167 EXPECT_EQ(next_power_of_2(T(9)), T(16)) << "value = " << T(9);
168 EXPECT_EQ(next_power_of_2(T(10)), T(16)) << "value = " << T(10);
169
170 T t_max_pow2 = max_pow2<T>();
171
172 // next(pow2 - 1) should return pow2
173 for (T pow2 = T(1); pow2 < t_max_pow2; pow2 = pow2 * 2) {
174 EXPECT_EQ(pow2, next_power_of_2(pow2 - 1))
175 << "value = " << pow2 - 1;
176 }
177 EXPECT_EQ(next_power_of_2(t_max_pow2 - 1), t_max_pow2)
178 << "value = " << (t_max_pow2 - 1);
179
180 // next(pow2) should return pow2 * 2
181 for (T pow2 = T(1); pow2 < t_max_pow2 / 2; pow2 = pow2 * 2) {
182 EXPECT_EQ(pow2 * 2, next_power_of_2(pow2))
183 << "value = " << pow2;
184 }
185 }
186
187 TEST(power_of_2, next_power_of_2) {
188 next_power_of_2<int8_t>();
189 next_power_of_2<int16_t>();
190 next_power_of_2<int32_t>();
191 next_power_of_2<int64_t>();
192 next_power_of_2<uint8_t>();
193 next_power_of_2<uint16_t>();
194 next_power_of_2<uint32_t>();
195 next_power_of_2<uint64_t>();
196 }