1 //===- llvm/unittests/ADT/BitTest.cpp - <bit> tests ---===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/ADT/bit.h"
10 #include "gtest/gtest.h"
11 #include <cstdint>
12 #include <cstdlib>
13
14 using namespace llvm;
15
16 namespace {
17
TEST(BitTest,BitCast)18 TEST(BitTest, BitCast) {
19 static const uint8_t kValueU8 = 0x80;
20 EXPECT_TRUE(llvm::bit_cast<int8_t>(kValueU8) < 0);
21
22 static const uint16_t kValueU16 = 0x8000;
23 EXPECT_TRUE(llvm::bit_cast<int16_t>(kValueU16) < 0);
24
25 static const float kValueF32 = 5632.34f;
26 EXPECT_FLOAT_EQ(kValueF32,
27 llvm::bit_cast<float>(llvm::bit_cast<uint32_t>(kValueF32)));
28
29 static const double kValueF64 = 87987234.983498;
30 EXPECT_DOUBLE_EQ(kValueF64,
31 llvm::bit_cast<double>(llvm::bit_cast<uint64_t>(kValueF64)));
32 }
33
34 // In these first two tests all of the original_uintx values are truncated
35 // except for 64. We could avoid this, but there's really no point.
36
TEST(BitTest,ByteSwapUnsignedRoundTrip)37 TEST(BitTest, ByteSwapUnsignedRoundTrip) {
38 // The point of the bit twiddling of magic is to test with and without bits
39 // in every byte.
40 uint64_t value = 1;
41 for (std::size_t i = 0; i <= sizeof(value); ++i) {
42 uint8_t original_uint8 = static_cast<uint8_t>(value);
43 EXPECT_EQ(original_uint8, llvm::byteswap(llvm::byteswap(original_uint8)));
44
45 uint16_t original_uint16 = static_cast<uint16_t>(value);
46 EXPECT_EQ(original_uint16, llvm::byteswap(llvm::byteswap(original_uint16)));
47
48 uint32_t original_uint32 = static_cast<uint32_t>(value);
49 EXPECT_EQ(original_uint32, llvm::byteswap(llvm::byteswap(original_uint32)));
50
51 uint64_t original_uint64 = static_cast<uint64_t>(value);
52 EXPECT_EQ(original_uint64, llvm::byteswap(llvm::byteswap(original_uint64)));
53
54 value = (value << 8) | 0x55; // binary 0101 0101.
55 }
56 }
57
TEST(BitTest,ByteSwapSignedRoundTrip)58 TEST(BitTest, ByteSwapSignedRoundTrip) {
59 // The point of the bit twiddling of magic is to test with and without bits
60 // in every byte.
61 uint64_t value = 1;
62 for (std::size_t i = 0; i <= sizeof(value); ++i) {
63 int8_t original_int8 = static_cast<int8_t>(value);
64 EXPECT_EQ(original_int8, llvm::byteswap(llvm::byteswap(original_int8)));
65
66 int16_t original_int16 = static_cast<int16_t>(value);
67 EXPECT_EQ(original_int16, llvm::byteswap(llvm::byteswap(original_int16)));
68
69 int32_t original_int32 = static_cast<int32_t>(value);
70 EXPECT_EQ(original_int32, llvm::byteswap(llvm::byteswap(original_int32)));
71
72 int64_t original_int64 = static_cast<int64_t>(value);
73 EXPECT_EQ(original_int64, llvm::byteswap(llvm::byteswap(original_int64)));
74
75 // Test other sign.
76 value *= -1;
77
78 original_int8 = static_cast<int8_t>(value);
79 EXPECT_EQ(original_int8, llvm::byteswap(llvm::byteswap(original_int8)));
80
81 original_int16 = static_cast<int16_t>(value);
82 EXPECT_EQ(original_int16, llvm::byteswap(llvm::byteswap(original_int16)));
83
84 original_int32 = static_cast<int32_t>(value);
85 EXPECT_EQ(original_int32, llvm::byteswap(llvm::byteswap(original_int32)));
86
87 original_int64 = static_cast<int64_t>(value);
88 EXPECT_EQ(original_int64, llvm::byteswap(llvm::byteswap(original_int64)));
89
90 // Return to normal sign and twiddle.
91 value *= -1;
92 value = (value << 8) | 0x55; // binary 0101 0101.
93 }
94 }
95
TEST(BitTest,ByteSwap)96 TEST(BitTest, ByteSwap) {
97 // Unsigned types.
98 EXPECT_EQ(uint8_t(0x11), llvm::byteswap(uint8_t(0x11)));
99 EXPECT_EQ(uint16_t(0x1122), llvm::byteswap(uint16_t(0x2211)));
100 EXPECT_EQ(uint32_t(0x11223344), llvm::byteswap(uint32_t(0x44332211)));
101 EXPECT_EQ(uint64_t(0x1122334455667788ULL),
102 llvm::byteswap(uint64_t(0x8877665544332211ULL)));
103
104 // Signed types.
105 EXPECT_EQ(int8_t(0x11), llvm::byteswap(int8_t(0x11)));
106 EXPECT_EQ(int16_t(0x1122), llvm::byteswap(int16_t(0x2211)));
107 EXPECT_EQ(int32_t(0x11223344), llvm::byteswap(int32_t(0x44332211)));
108 EXPECT_EQ(int64_t(0x1122334455667788LL),
109 llvm::byteswap(int64_t(0x8877665544332211LL)));
110 }
111
TEST(BitTest,HasSingleBit)112 TEST(BitTest, HasSingleBit) {
113 EXPECT_FALSE(llvm::has_single_bit(0U));
114 EXPECT_FALSE(llvm::has_single_bit(0ULL));
115
116 EXPECT_FALSE(llvm::has_single_bit(~0U));
117 EXPECT_FALSE(llvm::has_single_bit(~0ULL));
118
119 EXPECT_TRUE(llvm::has_single_bit(1U));
120 EXPECT_TRUE(llvm::has_single_bit(1ULL));
121
122 static const int8_t kValueS8 = -128;
123 EXPECT_TRUE(llvm::has_single_bit(static_cast<uint8_t>(kValueS8)));
124
125 static const int16_t kValueS16 = -32768;
126 EXPECT_TRUE(llvm::has_single_bit(static_cast<uint16_t>(kValueS16)));
127 }
128
TEST(BitTest,BitFloor)129 TEST(BitTest, BitFloor) {
130 EXPECT_EQ(0u, llvm::bit_floor(uint8_t(0)));
131 EXPECT_EQ(0u, llvm::bit_floor(uint16_t(0)));
132 EXPECT_EQ(0u, llvm::bit_floor(uint32_t(0)));
133 EXPECT_EQ(0u, llvm::bit_floor(uint64_t(0)));
134
135 EXPECT_EQ(1u, llvm::bit_floor(uint8_t(1)));
136 EXPECT_EQ(1u, llvm::bit_floor(uint16_t(1)));
137 EXPECT_EQ(1u, llvm::bit_floor(uint32_t(1)));
138 EXPECT_EQ(1u, llvm::bit_floor(uint64_t(1)));
139
140 EXPECT_EQ(2u, llvm::bit_floor(uint8_t(2)));
141 EXPECT_EQ(2u, llvm::bit_floor(uint16_t(2)));
142 EXPECT_EQ(2u, llvm::bit_floor(uint32_t(2)));
143 EXPECT_EQ(2u, llvm::bit_floor(uint64_t(2)));
144
145 EXPECT_EQ(2u, llvm::bit_floor(uint8_t(3)));
146 EXPECT_EQ(2u, llvm::bit_floor(uint16_t(3)));
147 EXPECT_EQ(2u, llvm::bit_floor(uint32_t(3)));
148 EXPECT_EQ(2u, llvm::bit_floor(uint64_t(3)));
149
150 EXPECT_EQ(4u, llvm::bit_floor(uint8_t(4)));
151 EXPECT_EQ(4u, llvm::bit_floor(uint16_t(4)));
152 EXPECT_EQ(4u, llvm::bit_floor(uint32_t(4)));
153 EXPECT_EQ(4u, llvm::bit_floor(uint64_t(4)));
154
155 EXPECT_EQ(0x40u, llvm::bit_floor(uint8_t(0x7f)));
156 EXPECT_EQ(0x4000u, llvm::bit_floor(uint16_t(0x7fff)));
157 EXPECT_EQ(0x40000000u, llvm::bit_floor(uint32_t(0x7fffffffu)));
158 EXPECT_EQ(0x4000000000000000ull,
159 llvm::bit_floor(uint64_t(0x7fffffffffffffffull)));
160
161 EXPECT_EQ(0x80u, llvm::bit_floor(uint8_t(0x80)));
162 EXPECT_EQ(0x8000u, llvm::bit_floor(uint16_t(0x8000)));
163 EXPECT_EQ(0x80000000u, llvm::bit_floor(uint32_t(0x80000000u)));
164 EXPECT_EQ(0x8000000000000000ull,
165 llvm::bit_floor(uint64_t(0x8000000000000000ull)));
166
167 EXPECT_EQ(0x80u, llvm::bit_floor(uint8_t(0xff)));
168 EXPECT_EQ(0x8000u, llvm::bit_floor(uint16_t(0xffff)));
169 EXPECT_EQ(0x80000000u, llvm::bit_floor(uint32_t(0xffffffffu)));
170 EXPECT_EQ(0x8000000000000000ull,
171 llvm::bit_floor(uint64_t(0xffffffffffffffffull)));
172 }
173
TEST(BitTest,BitCeil)174 TEST(BitTest, BitCeil) {
175 EXPECT_EQ(1u, llvm::bit_ceil(uint8_t(0)));
176 EXPECT_EQ(1u, llvm::bit_ceil(uint16_t(0)));
177 EXPECT_EQ(1u, llvm::bit_ceil(uint32_t(0)));
178 EXPECT_EQ(1u, llvm::bit_ceil(uint64_t(0)));
179
180 EXPECT_EQ(1u, llvm::bit_ceil(uint8_t(1)));
181 EXPECT_EQ(1u, llvm::bit_ceil(uint16_t(1)));
182 EXPECT_EQ(1u, llvm::bit_ceil(uint32_t(1)));
183 EXPECT_EQ(1u, llvm::bit_ceil(uint64_t(1)));
184
185 EXPECT_EQ(2u, llvm::bit_ceil(uint8_t(2)));
186 EXPECT_EQ(2u, llvm::bit_ceil(uint16_t(2)));
187 EXPECT_EQ(2u, llvm::bit_ceil(uint32_t(2)));
188 EXPECT_EQ(2u, llvm::bit_ceil(uint64_t(2)));
189
190 EXPECT_EQ(4u, llvm::bit_ceil(uint8_t(3)));
191 EXPECT_EQ(4u, llvm::bit_ceil(uint16_t(3)));
192 EXPECT_EQ(4u, llvm::bit_ceil(uint32_t(3)));
193 EXPECT_EQ(4u, llvm::bit_ceil(uint64_t(3)));
194
195 EXPECT_EQ(4u, llvm::bit_ceil(uint8_t(4)));
196 EXPECT_EQ(4u, llvm::bit_ceil(uint16_t(4)));
197 EXPECT_EQ(4u, llvm::bit_ceil(uint32_t(4)));
198 EXPECT_EQ(4u, llvm::bit_ceil(uint64_t(4)));
199
200 // The result is the largest representable value for each type.
201 EXPECT_EQ(0x80u, llvm::bit_ceil(uint8_t(0x7f)));
202 EXPECT_EQ(0x8000u, llvm::bit_ceil(uint16_t(0x7fff)));
203 EXPECT_EQ(0x80000000u, llvm::bit_ceil(uint32_t(0x7fffffffu)));
204 EXPECT_EQ(0x8000000000000000ull,
205 llvm::bit_ceil(uint64_t(0x7fffffffffffffffull)));
206 }
207
TEST(BitTest,BitWidth)208 TEST(BitTest, BitWidth) {
209 EXPECT_EQ(0, llvm::bit_width(uint8_t(0)));
210 EXPECT_EQ(0, llvm::bit_width(uint16_t(0)));
211 EXPECT_EQ(0, llvm::bit_width(uint32_t(0)));
212 EXPECT_EQ(0, llvm::bit_width(uint64_t(0)));
213
214 EXPECT_EQ(1, llvm::bit_width(uint8_t(1)));
215 EXPECT_EQ(1, llvm::bit_width(uint16_t(1)));
216 EXPECT_EQ(1, llvm::bit_width(uint32_t(1)));
217 EXPECT_EQ(1, llvm::bit_width(uint64_t(1)));
218
219 EXPECT_EQ(2, llvm::bit_width(uint8_t(2)));
220 EXPECT_EQ(2, llvm::bit_width(uint16_t(2)));
221 EXPECT_EQ(2, llvm::bit_width(uint32_t(2)));
222 EXPECT_EQ(2, llvm::bit_width(uint64_t(2)));
223
224 EXPECT_EQ(2, llvm::bit_width(uint8_t(3)));
225 EXPECT_EQ(2, llvm::bit_width(uint16_t(3)));
226 EXPECT_EQ(2, llvm::bit_width(uint32_t(3)));
227 EXPECT_EQ(2, llvm::bit_width(uint64_t(3)));
228
229 EXPECT_EQ(3, llvm::bit_width(uint8_t(4)));
230 EXPECT_EQ(3, llvm::bit_width(uint16_t(4)));
231 EXPECT_EQ(3, llvm::bit_width(uint32_t(4)));
232 EXPECT_EQ(3, llvm::bit_width(uint64_t(4)));
233
234 EXPECT_EQ(7, llvm::bit_width(uint8_t(0x7f)));
235 EXPECT_EQ(15, llvm::bit_width(uint16_t(0x7fff)));
236 EXPECT_EQ(31, llvm::bit_width(uint32_t(0x7fffffffu)));
237 EXPECT_EQ(63, llvm::bit_width(uint64_t(0x7fffffffffffffffull)));
238
239 EXPECT_EQ(8, llvm::bit_width(uint8_t(0x80)));
240 EXPECT_EQ(16, llvm::bit_width(uint16_t(0x8000)));
241 EXPECT_EQ(32, llvm::bit_width(uint32_t(0x80000000u)));
242 EXPECT_EQ(64, llvm::bit_width(uint64_t(0x8000000000000000ull)));
243
244 EXPECT_EQ(8, llvm::bit_width(uint8_t(0xff)));
245 EXPECT_EQ(16, llvm::bit_width(uint16_t(0xffff)));
246 EXPECT_EQ(32, llvm::bit_width(uint32_t(0xffffffffu)));
247 EXPECT_EQ(64, llvm::bit_width(uint64_t(0xffffffffffffffffull)));
248 }
249
TEST(BitTest,CountlZero)250 TEST(BitTest, CountlZero) {
251 uint8_t Z8 = 0;
252 uint16_t Z16 = 0;
253 uint32_t Z32 = 0;
254 uint64_t Z64 = 0;
255 EXPECT_EQ(8, llvm::countl_zero(Z8));
256 EXPECT_EQ(16, llvm::countl_zero(Z16));
257 EXPECT_EQ(32, llvm::countl_zero(Z32));
258 EXPECT_EQ(64, llvm::countl_zero(Z64));
259
260 uint8_t NZ8 = 42;
261 uint16_t NZ16 = 42;
262 uint32_t NZ32 = 42;
263 uint64_t NZ64 = 42;
264 EXPECT_EQ(2, llvm::countl_zero(NZ8));
265 EXPECT_EQ(10, llvm::countl_zero(NZ16));
266 EXPECT_EQ(26, llvm::countl_zero(NZ32));
267 EXPECT_EQ(58, llvm::countl_zero(NZ64));
268
269 EXPECT_EQ(8, llvm::countl_zero(0x00F000FFu));
270 EXPECT_EQ(8, llvm::countl_zero(0x00F12345u));
271 for (unsigned i = 0; i <= 30; ++i) {
272 EXPECT_EQ(int(31 - i), llvm::countl_zero(1u << i));
273 }
274
275 EXPECT_EQ(8, llvm::countl_zero(0x00F1234500F12345ULL));
276 EXPECT_EQ(1, llvm::countl_zero(1ULL << 62));
277 for (unsigned i = 0; i <= 62; ++i) {
278 EXPECT_EQ(int(63 - i), llvm::countl_zero(1ULL << i));
279 }
280 }
281
TEST(BitTest,CountrZero)282 TEST(BitTest, CountrZero) {
283 uint8_t Z8 = 0;
284 uint16_t Z16 = 0;
285 uint32_t Z32 = 0;
286 uint64_t Z64 = 0;
287 EXPECT_EQ(8, llvm::countr_zero(Z8));
288 EXPECT_EQ(16, llvm::countr_zero(Z16));
289 EXPECT_EQ(32, llvm::countr_zero(Z32));
290 EXPECT_EQ(64, llvm::countr_zero(Z64));
291
292 uint8_t NZ8 = 42;
293 uint16_t NZ16 = 42;
294 uint32_t NZ32 = 42;
295 uint64_t NZ64 = 42;
296 EXPECT_EQ(1, llvm::countr_zero(NZ8));
297 EXPECT_EQ(1, llvm::countr_zero(NZ16));
298 EXPECT_EQ(1, llvm::countr_zero(NZ32));
299 EXPECT_EQ(1, llvm::countr_zero(NZ64));
300 }
301
TEST(BitTest,CountlOne)302 TEST(BitTest, CountlOne) {
303 for (int i = 30; i >= 0; --i) {
304 // Start with all ones and unset some bit.
305 EXPECT_EQ(31 - i, llvm::countl_one(0xFFFFFFFF ^ (1 << i)));
306 }
307 for (int i = 62; i >= 0; --i) {
308 // Start with all ones and unset some bit.
309 EXPECT_EQ(63 - i, llvm::countl_one(0xFFFFFFFFFFFFFFFFULL ^ (1LL << i)));
310 }
311 for (int i = 30; i >= 0; --i) {
312 // Start with all ones and unset some bit.
313 EXPECT_EQ(31 - i, llvm::countl_one(0xFFFFFFFF ^ (1 << i)));
314 }
315 }
316
TEST(BitTest,CountrOne)317 TEST(BitTest, CountrOne) {
318 uint8_t AllOnes8 = ~(uint8_t)0;
319 uint16_t AllOnes16 = ~(uint16_t)0;
320 uint32_t AllOnes32 = ~(uint32_t)0;
321 uint64_t AllOnes64 = ~(uint64_t)0;
322 EXPECT_EQ(8, llvm::countr_one(AllOnes8));
323 EXPECT_EQ(16, llvm::countr_one(AllOnes16));
324 EXPECT_EQ(32, llvm::countr_one(AllOnes32));
325 EXPECT_EQ(64, llvm::countr_one(AllOnes64));
326
327 uint8_t X8 = 6;
328 uint16_t X16 = 6;
329 uint32_t X32 = 6;
330 uint64_t X64 = 6;
331 EXPECT_EQ(0, llvm::countr_one(X8));
332 EXPECT_EQ(0, llvm::countr_one(X16));
333 EXPECT_EQ(0, llvm::countr_one(X32));
334 EXPECT_EQ(0, llvm::countr_one(X64));
335
336 uint8_t Y8 = 23;
337 uint16_t Y16 = 23;
338 uint32_t Y32 = 23;
339 uint64_t Y64 = 23;
340 EXPECT_EQ(3, llvm::countr_one(Y8));
341 EXPECT_EQ(3, llvm::countr_one(Y16));
342 EXPECT_EQ(3, llvm::countr_one(Y32));
343 EXPECT_EQ(3, llvm::countr_one(Y64));
344 }
345
TEST(BitTest,PopCount)346 TEST(BitTest, PopCount) {
347 EXPECT_EQ(0, llvm::popcount(0U));
348 EXPECT_EQ(0, llvm::popcount(0ULL));
349
350 EXPECT_EQ(32, llvm::popcount(~0U));
351 EXPECT_EQ(64, llvm::popcount(~0ULL));
352
353 for (int I = 0; I != 32; ++I)
354 EXPECT_EQ(1, llvm::popcount(1U << I));
355 }
356
TEST(BitTest,Rotl)357 TEST(BitTest, Rotl) {
358 EXPECT_EQ(0x53U, llvm::rotl<uint8_t>(0x53, 0));
359 EXPECT_EQ(0x4dU, llvm::rotl<uint8_t>(0x53, 2));
360 EXPECT_EQ(0xa6U, llvm::rotl<uint8_t>(0x53, 9));
361 EXPECT_EQ(0x9aU, llvm::rotl<uint8_t>(0x53, -5));
362
363 EXPECT_EQ(0xabcdU, llvm::rotl<uint16_t>(0xabcd, 0));
364 EXPECT_EQ(0xf36aU, llvm::rotl<uint16_t>(0xabcd, 6));
365 EXPECT_EQ(0xaf36U, llvm::rotl<uint16_t>(0xabcd, 18));
366 EXPECT_EQ(0xf36aU, llvm::rotl<uint16_t>(0xabcd, -10));
367
368 EXPECT_EQ(0xdeadbeefU, llvm::rotl<uint32_t>(0xdeadbeef, 0));
369 EXPECT_EQ(0x7ddfbd5bU, llvm::rotl<uint32_t>(0xdeadbeef, 17));
370 EXPECT_EQ(0x5b7ddfbdU, llvm::rotl<uint32_t>(0xdeadbeef, 41));
371 EXPECT_EQ(0xb6fbbf7aU, llvm::rotl<uint32_t>(0xdeadbeef, -22));
372
373 EXPECT_EQ(0x12345678deadbeefULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 0));
374 EXPECT_EQ(0xf56df77891a2b3c6ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 35));
375 EXPECT_EQ(0x8d159e37ab6fbbc4ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, 70));
376 EXPECT_EQ(0xb7dde2468acf1bd5ULL, llvm::rotl<uint64_t>(0x12345678deadbeefULL, -19));
377 }
378
TEST(BitTest,Rotr)379 TEST(BitTest, Rotr) {
380 EXPECT_EQ(0x53U, llvm::rotr<uint8_t>(0x53, 0));
381 EXPECT_EQ(0xd4U, llvm::rotr<uint8_t>(0x53, 2));
382 EXPECT_EQ(0xa9U, llvm::rotr<uint8_t>(0x53, 9));
383 EXPECT_EQ(0x6aU, llvm::rotr<uint8_t>(0x53, -5));
384
385 EXPECT_EQ(0xabcdU, llvm::rotr<uint16_t>(0xabcd, 0));
386 EXPECT_EQ(0x36afU, llvm::rotr<uint16_t>(0xabcd, 6));
387 EXPECT_EQ(0x6af3U, llvm::rotr<uint16_t>(0xabcd, 18));
388 EXPECT_EQ(0x36afU, llvm::rotr<uint16_t>(0xabcd, -10));
389
390 EXPECT_EQ(0xdeadbeefU, llvm::rotr<uint32_t>(0xdeadbeef, 0));
391 EXPECT_EQ(0xdf77ef56U, llvm::rotr<uint32_t>(0xdeadbeef, 17));
392 EXPECT_EQ(0x77ef56dfU, llvm::rotr<uint32_t>(0xdeadbeef, 41));
393 EXPECT_EQ(0xbbf7ab6fU, llvm::rotr<uint32_t>(0xdeadbeef, -22));
394
395 EXPECT_EQ(0x12345678deadbeefULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 0));
396 EXPECT_EQ(0x1bd5b7dde2468acfULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 35));
397 EXPECT_EQ(0xbc48d159e37ab6fbULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, 70));
398 EXPECT_EQ(0xb3c6f56df77891a2ULL, llvm::rotr<uint64_t>(0x12345678deadbeefULL, -19));
399 }
400
401 } // anonymous namespace
402