jdk

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
#include "precompiled.hpp"
25

26
#include "utilities/globalDefinitions.hpp"
27
#include "utilities/powerOfTwo.hpp"
28
#include "unittest.hpp"
29

30
#include <limits>
31
#include <type_traits>
32

33
struct StaticTestIsPowerOf2Result {
34
  uint64_t _value;
35
  int _status;            // 0: success, > 0 indicates which failure case
36
  constexpr StaticTestIsPowerOf2Result(uint64_t value, int status) :
37
    _value(value), _status(status) {}
38
};
39

40
// Structure copied from test_is_power_of_2 runtime test (below).
41
template<typename T>
42
static constexpr StaticTestIsPowerOf2Result static_test_is_power_of_2_aux(T v) {
43
  using Result = StaticTestIsPowerOf2Result;
44
  for ( ; v > 0; v >>= 1) {
45
    if (!is_power_of_2(v)) {
46
      return Result(v, 1);
47
    } else if ((v > 2) && is_power_of_2(T(v - 1))) {
48
      return Result(v, 2);
49
    } else if ((v > 1) && is_power_of_2(T(v + 1))) {
50
      return Result(v, 3);
51
    }
52
  }
53
  return Result(v, 0);
54
}
55

56
template<typename T>
57
static void static_test_is_power_of_2() {
58
  constexpr StaticTestIsPowerOf2Result result
59
    = static_test_is_power_of_2_aux(max_power_of_2<T>());
60

61
  EXPECT_EQ(0, result._status)
62
    << "value = " << result._value << ", status = " << result._status;
63
}
64

65
template <typename T> static void test_is_power_of_2() {
66
  EXPECT_FALSE(is_power_of_2(T(0)));
67
  EXPECT_FALSE(is_power_of_2(~T(0)));
68

69
  static_assert(!is_power_of_2(T(0)), "");
70
  static_assert(!is_power_of_2(~T(0)), "");
71

72
  // Should be false regardless of whether T is signed or unsigned.
73
  EXPECT_FALSE(is_power_of_2(std::numeric_limits<T>::min()));
74
  static_assert(!is_power_of_2(std::numeric_limits<T>::min()), "");
75

76
  // Test true
77
  for (T i = max_power_of_2<T>(); i > 0; i = (i >> 1)) {
78
    EXPECT_TRUE(is_power_of_2(i)) << "value = " << T(i);
79
  }
80

81
  // Test one less
82
  for (T i = max_power_of_2<T>(); i > 2; i = (i >> 1)) {
83
    EXPECT_FALSE(is_power_of_2(i - 1)) << "value = " << T(i - 1);
84
  }
85

86
  // Test one more
87
  for (T i = max_power_of_2<T>(); i > 1; i = (i >> 1)) {
88
    EXPECT_FALSE(is_power_of_2(i + 1)) << "value = " << T(i + 1);
89
  }
90

91
  static_test_is_power_of_2<T>();
92
}
93

94
TEST(power_of_2, is_power_of_2) {
95
  test_is_power_of_2<int8_t>();
96
  test_is_power_of_2<int16_t>();
97
  test_is_power_of_2<int32_t>();
98
  test_is_power_of_2<int64_t>();
99
  test_is_power_of_2<int8_t>();
100
  test_is_power_of_2<int16_t>();
101
  test_is_power_of_2<int32_t>();
102
  test_is_power_of_2<int64_t>();
103

104
  test_is_power_of_2<jint>();
105
  test_is_power_of_2<jlong>();
106
}
107

108
TEST(power_of_2, exact_log2) {
109
  {
110
    uintptr_t j = 1;
111
#ifdef _LP64
112
    for (int i = 0; i < 64; i++, j <<= 1) {
113
#else
114
    for (int i = 0; i < 32; i++, j <<= 1) {
115
#endif
116
      EXPECT_EQ(i, exact_log2(j));
117
    }
118
  }
119
  {
120
    julong j = 1;
121
    for (int i = 0; i < 64; i++, j <<= 1) {
122
      EXPECT_EQ(i, exact_log2_long(j));
123
    }
124
  }
125
}
126

127
template <typename T> void round_up_power_of_2() {
128
  EXPECT_EQ(round_up_power_of_2(T(1)), T(1)) << "value = " << T(1);
129
  EXPECT_EQ(round_up_power_of_2(T(2)), T(2)) << "value = " << T(2);
130
  EXPECT_EQ(round_up_power_of_2(T(3)), T(4)) << "value = " << T(3);
131
  EXPECT_EQ(round_up_power_of_2(T(4)), T(4)) << "value = " << T(4);
132
  EXPECT_EQ(round_up_power_of_2(T(5)), T(8)) << "value = " << T(5);
133
  EXPECT_EQ(round_up_power_of_2(T(6)), T(8)) << "value = " << T(6);
134
  EXPECT_EQ(round_up_power_of_2(T(7)), T(8)) << "value = " << T(7);
135
  EXPECT_EQ(round_up_power_of_2(T(8)), T(8)) << "value = " << T(8);
136
  EXPECT_EQ(round_up_power_of_2(T(9)), T(16)) << "value = " << T(9);
137
  EXPECT_EQ(round_up_power_of_2(T(10)), T(16)) << "value = " << T(10);
138

139
  T t_max_pow2 = max_power_of_2<T>();
140

141
  // round_up(any power of two) should return input
142
  for (T pow2 = T(1); pow2 < t_max_pow2; pow2 *= 2) {
143
    EXPECT_EQ(pow2, round_up_power_of_2(pow2))
144
      << "value = " << pow2;
145
  }
146
  EXPECT_EQ(round_up_power_of_2(t_max_pow2), t_max_pow2)
147
    << "value = " << (t_max_pow2);
148

149
  // For each pow2 gt 2, round_up(pow2 - 1) should return pow2
150
  for (T pow2 = T(4); pow2 < t_max_pow2; pow2 *= 2) {
151
    EXPECT_EQ(pow2, round_up_power_of_2(pow2 - 1))
152
      << "value = " << pow2;
153
  }
154
  EXPECT_EQ(round_up_power_of_2(t_max_pow2 - 1), t_max_pow2)
155
    << "value = " << (t_max_pow2 - 1);
156

157
}
158

159
TEST(power_of_2, round_up_power_of_2) {
160
  round_up_power_of_2<int8_t>();
161
  round_up_power_of_2<int16_t>();
162
  round_up_power_of_2<int32_t>();
163
  round_up_power_of_2<int64_t>();
164
  round_up_power_of_2<uint8_t>();
165
  round_up_power_of_2<uint16_t>();
166
  round_up_power_of_2<uint32_t>();
167
  round_up_power_of_2<uint64_t>();
168
}
169

170
template <typename T> void round_down_power_of_2() {
171
  EXPECT_EQ(round_down_power_of_2(T(1)), T(1)) << "value = " << T(1);
172
  EXPECT_EQ(round_down_power_of_2(T(2)), T(2)) << "value = " << T(2);
173
  EXPECT_EQ(round_down_power_of_2(T(3)), T(2)) << "value = " << T(3);
174
  EXPECT_EQ(round_down_power_of_2(T(4)), T(4)) << "value = " << T(4);
175
  EXPECT_EQ(round_down_power_of_2(T(5)), T(4)) << "value = " << T(5);
176
  EXPECT_EQ(round_down_power_of_2(T(6)), T(4)) << "value = " << T(6);
177
  EXPECT_EQ(round_down_power_of_2(T(7)), T(4)) << "value = " << T(7);
178
  EXPECT_EQ(round_down_power_of_2(T(8)), T(8)) << "value = " << T(8);
179
  EXPECT_EQ(round_down_power_of_2(T(9)), T(8)) << "value = " << T(9);
180
  EXPECT_EQ(round_down_power_of_2(T(10)), T(8)) << "value = " << T(10);
181

182
  T t_max_pow2 = max_power_of_2<T>();
183

184
  // For each pow2 >= 2:
185
  // - round_down(pow2) should return pow2
186
  // - round_down(pow2 + 1) should return pow2
187
  // - round_down(pow2 - 1) should return pow2 / 2
188
  for (T pow2 = T(2); pow2 < t_max_pow2; pow2 = pow2 * 2) {
189
    EXPECT_EQ(pow2, round_down_power_of_2(pow2))
190
      << "value = " << pow2;
191
    EXPECT_EQ(pow2, round_down_power_of_2(pow2 + 1))
192
      << "value = " << pow2;
193
    EXPECT_EQ(pow2 / 2, round_down_power_of_2(pow2 - 1))
194
      << "value = " << (pow2 / 2);
195
  }
196
  EXPECT_EQ(round_down_power_of_2(t_max_pow2), t_max_pow2)
197
    << "value = " << (t_max_pow2);
198
  EXPECT_EQ(round_down_power_of_2(t_max_pow2 + 1), t_max_pow2)
199
    << "value = " << (t_max_pow2 + 1);
200
  EXPECT_EQ(round_down_power_of_2(t_max_pow2 - 1), t_max_pow2 / 2)
201
    << "value = " << (t_max_pow2 - 1);
202
}
203

204
TEST(power_of_2, round_down_power_of_2) {
205
  round_down_power_of_2<int8_t>();
206
  round_down_power_of_2<int16_t>();
207
  round_down_power_of_2<int32_t>();
208
  round_down_power_of_2<int64_t>();
209
  round_down_power_of_2<uint8_t>();
210
  round_down_power_of_2<uint16_t>();
211
  round_down_power_of_2<uint32_t>();
212
  round_down_power_of_2<uint64_t>();
213
}
214

215
template <typename T> void next_power_of_2() {
216
  EXPECT_EQ(next_power_of_2(T(0)), T(1)) << "value = " << T(0);
217
  EXPECT_EQ(next_power_of_2(T(1)), T(2)) << "value = " << T(1);
218
  EXPECT_EQ(next_power_of_2(T(2)), T(4)) << "value = " << T(2);
219
  EXPECT_EQ(next_power_of_2(T(3)), T(4)) << "value = " << T(3);
220
  EXPECT_EQ(next_power_of_2(T(4)), T(8)) << "value = " << T(4);
221
  EXPECT_EQ(next_power_of_2(T(5)), T(8)) << "value = " << T(5);
222
  EXPECT_EQ(next_power_of_2(T(6)), T(8)) << "value = " << T(6);
223
  EXPECT_EQ(next_power_of_2(T(7)), T(8)) << "value = " << T(7);
224
  EXPECT_EQ(next_power_of_2(T(8)), T(16)) << "value = " << T(8);
225
  EXPECT_EQ(next_power_of_2(T(9)), T(16)) << "value = " << T(9);
226
  EXPECT_EQ(next_power_of_2(T(10)), T(16)) << "value = " << T(10);
227

228
  T t_max_pow2 = max_power_of_2<T>();
229

230
  // next(pow2 - 1) should return pow2
231
  for (T pow2 = T(1); pow2 < t_max_pow2; pow2 = pow2 * 2) {
232
    EXPECT_EQ(pow2, next_power_of_2(pow2 - 1))
233
      << "value = " << pow2 - 1;
234
  }
235
  EXPECT_EQ(next_power_of_2(t_max_pow2 - 1), t_max_pow2)
236
    << "value = " << (t_max_pow2 - 1);
237

238
  // next(pow2) should return pow2 * 2
239
  for (T pow2 = T(1); pow2 < t_max_pow2 / 2; pow2 = pow2 * 2) {
240
    EXPECT_EQ(pow2 * 2, next_power_of_2(pow2))
241
      << "value = " << pow2;
242
  }
243
}
244

245
TEST(power_of_2, next_power_of_2) {
246
  next_power_of_2<int8_t>();
247
  next_power_of_2<int16_t>();
248
  next_power_of_2<int32_t>();
249
  next_power_of_2<int64_t>();
250
  next_power_of_2<uint8_t>();
251
  next_power_of_2<uint16_t>();
252
  next_power_of_2<uint32_t>();
253
  next_power_of_2<uint64_t>();
254
}
255

256
TEST(power_of_2, max) {
257
  EXPECT_EQ(max_power_of_2<int8_t>(),  0x40);
258
  EXPECT_EQ(max_power_of_2<int16_t>(), 0x4000);
259
  EXPECT_EQ(max_power_of_2<int32_t>(), 0x40000000);
260
  EXPECT_EQ(max_power_of_2<int64_t>(), CONST64(0x4000000000000000));
261
  EXPECT_EQ(max_power_of_2<uint8_t>(),  0x80u);
262
  EXPECT_EQ(max_power_of_2<uint16_t>(), 0x8000u);
263
  EXPECT_EQ(max_power_of_2<uint32_t>(), 0x80000000u);
264
  EXPECT_EQ(max_power_of_2<uint64_t>(), UCONST64(0x8000000000000000));
265
}
266

267
template <typename T, ENABLE_IF(std::is_integral<T>::value)>
268
void check_log2i_variants_for(T dummy) {
269
  int limit = sizeof(T) * BitsPerByte;
270
  if (std::is_signed<T>::value) {
271
    T min = std::numeric_limits<T>::min();
272
    EXPECT_EQ(limit - 1, log2i_graceful(min));
273
    EXPECT_EQ(limit - 1, log2i_graceful((T)-1));
274
    limit--;
275
  }
276
  {
277
    // Test log2i_graceful handles 0 input
278
    EXPECT_EQ(-1, log2i_graceful(T(0)));
279
  }
280
  {
281
    // Test the all-1s bit patterns
282
    T var = 1;
283
    for (int i = 0; i < limit; i++, var = (var << 1) | 1) {
284
      EXPECT_EQ(i, log2i(var));
285
    }
286
  }
287
  {
288
    // Test the powers of 2 and powers + 1
289
    T var = 1;
290
    for (int i = 0; i < limit; i++, var <<= 1) {
291
      EXPECT_EQ(i, log2i(var));
292
      EXPECT_EQ(i, log2i_graceful(var));
293
      EXPECT_EQ(i, log2i_exact(var));
294
      EXPECT_EQ(i, log2i(var | 1));
295
    }
296
  }
297
}
298

299
TEST(power_of_2, log2i) {
300
  check_log2i_variants_for((uintptr_t)0);
301
  check_log2i_variants_for((intptr_t)0);
302
  check_log2i_variants_for((julong)0);
303
  check_log2i_variants_for((int)0);
304
  check_log2i_variants_for((jint)0);
305
  check_log2i_variants_for((uint)0);
306
  check_log2i_variants_for((jlong)0);
307
}
308