1//===-- Unittests for Bit -------------------------------------------------===//
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 "src/__support/CPP/bit.h"
10#include "src/__support/big_int.h"
11#include "src/__support/macros/config.h"
12#include "src/__support/macros/properties/types.h" // LIBC_TYPES_HAS_INT128
13#include "test/UnitTest/Test.h"
14
15#include <stdint.h>
16
17namespace LIBC_NAMESPACE_DECL {
18namespace cpp {
19
20using UnsignedTypes = testing::TypeList<
21#if defined(LIBC_TYPES_HAS_INT128)
22 __uint128_t,
23#endif // LIBC_TYPES_HAS_INT128
24 unsigned char, unsigned short, unsigned int, unsigned long,
25 unsigned long long, UInt<128>>;
26
27#ifdef FAKE_MACRO_DISABLE
28TYPED_TEST(LlvmLibcBitTest, HasSingleBit, UnsignedTypes) {
29 constexpr auto ZERO = T(0);
30 constexpr auto ALL_ONES = T(~ZERO);
31 EXPECT_FALSE(has_single_bit<T>(ZERO));
32 EXPECT_FALSE(has_single_bit<T>(ALL_ONES));
33
34 for (T value = 1; value; value <<= 1)
35 EXPECT_TRUE(has_single_bit<T>(value));
36
37 // We test that if two bits are set has_single_bit returns false.
38 // We do this by setting the highest or lowest bit depending or where the
39 // current bit is. This is a bit convoluted but it helps catch a bug on BigInt
40 // where we have to work on an element-by-element basis.
41 constexpr auto MIDPOINT = T(ALL_ONES / 2);
42 constexpr auto LSB = T(1);
43 constexpr auto MSB = T(~(ALL_ONES >> 1));
44 for (T value = 1; value; value <<= 1) {
45 T two_bits_value =
46 static_cast<T>(value | ((value <= MIDPOINT) ? MSB : LSB));
47 EXPECT_FALSE(has_single_bit<T>(two_bits_value));
48 }
49}
50#endif
51
52TYPED_TEST(LlvmLibcBitTest, CountLZero, UnsignedTypes) {
53 EXPECT_EQ(countl_zero<T>(T(0)), cpp::numeric_limits<T>::digits);
54 int expected = 0;
55 for (T value = T(~0); value; value >>= 1, ++expected)
56 EXPECT_EQ(countl_zero<T>(value), expected);
57}
58
59TYPED_TEST(LlvmLibcBitTest, CountRZero, UnsignedTypes) {
60 EXPECT_EQ(countr_zero<T>(T(0)), cpp::numeric_limits<T>::digits);
61 int expected = 0;
62 for (T value = T(~0); value; value <<= 1, ++expected)
63 EXPECT_EQ(countr_zero<T>(value), expected);
64}
65
66TYPED_TEST(LlvmLibcBitTest, CountLOne, UnsignedTypes) {
67 EXPECT_EQ(countl_one<T>(T(0)), 0);
68 int expected = cpp::numeric_limits<T>::digits;
69 for (T value = T(~0); value; value <<= 1, --expected)
70 EXPECT_EQ(countl_one<T>(value), expected);
71}
72
73TYPED_TEST(LlvmLibcBitTest, CountROne, UnsignedTypes) {
74 EXPECT_EQ(countr_one<T>(T(0)), 0);
75 int expected = cpp::numeric_limits<T>::digits;
76 for (T value = T(~0); value; value >>= 1, --expected)
77 EXPECT_EQ(countr_one<T>(value), expected);
78}
79
80TYPED_TEST(LlvmLibcBitTest, BitWidth, UnsignedTypes) {
81 EXPECT_EQ(bit_width<T>(T(0)), 0);
82 int one_index = 0;
83 for (T value = 1; value; value <<= 1, ++one_index)
84 EXPECT_EQ(bit_width<T>(value), one_index + 1);
85}
86
87TEST(LlvmLibcBitTest, BitCeil) {
88 EXPECT_EQ(uint8_t(1), bit_ceil(uint8_t(0)));
89 EXPECT_EQ(uint16_t(1), bit_ceil(uint16_t(0)));
90 EXPECT_EQ(uint32_t(1), bit_ceil(uint32_t(0)));
91 EXPECT_EQ(uint64_t(1), bit_ceil(uint64_t(0)));
92
93 EXPECT_EQ(uint8_t(1), bit_ceil(uint8_t(1)));
94 EXPECT_EQ(uint16_t(1), bit_ceil(uint16_t(1)));
95 EXPECT_EQ(uint32_t(1), bit_ceil(uint32_t(1)));
96 EXPECT_EQ(uint64_t(1), bit_ceil(uint64_t(1)));
97
98 EXPECT_EQ(uint8_t(2), bit_ceil(uint8_t(2)));
99 EXPECT_EQ(uint16_t(2), bit_ceil(uint16_t(2)));
100 EXPECT_EQ(uint32_t(2), bit_ceil(uint32_t(2)));
101 EXPECT_EQ(uint64_t(2), bit_ceil(uint64_t(2)));
102
103 EXPECT_EQ(uint8_t(4), bit_ceil(uint8_t(3)));
104 EXPECT_EQ(uint16_t(4), bit_ceil(uint16_t(3)));
105 EXPECT_EQ(uint32_t(4), bit_ceil(uint32_t(3)));
106 EXPECT_EQ(uint64_t(4), bit_ceil(uint64_t(3)));
107
108 EXPECT_EQ(uint8_t(4), bit_ceil(uint8_t(4)));
109 EXPECT_EQ(uint16_t(4), bit_ceil(uint16_t(4)));
110 EXPECT_EQ(uint32_t(4), bit_ceil(uint32_t(4)));
111 EXPECT_EQ(uint64_t(4), bit_ceil(uint64_t(4)));
112
113 // The result is the representable power of 2 for each type.
114 EXPECT_EQ(uint8_t(0x80), bit_ceil(uint8_t(0x7f)));
115 EXPECT_EQ(uint16_t(0x8000), bit_ceil(uint16_t(0x7fff)));
116 EXPECT_EQ(uint32_t(0x80000000), bit_ceil(uint32_t(0x7fffffff)));
117 EXPECT_EQ(uint64_t(0x8000000000000000),
118 bit_ceil(uint64_t(0x7fffffffffffffff)));
119}
120
121TEST(LlvmLibcBitTest, BitFloor) {
122 EXPECT_EQ(uint8_t(0), bit_floor(uint8_t(0)));
123 EXPECT_EQ(uint16_t(0), bit_floor(uint16_t(0)));
124 EXPECT_EQ(uint32_t(0), bit_floor(uint32_t(0)));
125 EXPECT_EQ(uint64_t(0), bit_floor(uint64_t(0)));
126
127 EXPECT_EQ(uint8_t(1), bit_floor(uint8_t(1)));
128 EXPECT_EQ(uint16_t(1), bit_floor(uint16_t(1)));
129 EXPECT_EQ(uint32_t(1), bit_floor(uint32_t(1)));
130 EXPECT_EQ(uint64_t(1), bit_floor(uint64_t(1)));
131
132 EXPECT_EQ(uint8_t(2), bit_floor(uint8_t(2)));
133 EXPECT_EQ(uint16_t(2), bit_floor(uint16_t(2)));
134 EXPECT_EQ(uint32_t(2), bit_floor(uint32_t(2)));
135 EXPECT_EQ(uint64_t(2), bit_floor(uint64_t(2)));
136
137 EXPECT_EQ(uint8_t(2), bit_floor(uint8_t(3)));
138 EXPECT_EQ(uint16_t(2), bit_floor(uint16_t(3)));
139 EXPECT_EQ(uint32_t(2), bit_floor(uint32_t(3)));
140 EXPECT_EQ(uint64_t(2), bit_floor(uint64_t(3)));
141
142 EXPECT_EQ(uint8_t(4), bit_floor(uint8_t(4)));
143 EXPECT_EQ(uint16_t(4), bit_floor(uint16_t(4)));
144 EXPECT_EQ(uint32_t(4), bit_floor(uint32_t(4)));
145 EXPECT_EQ(uint64_t(4), bit_floor(uint64_t(4)));
146
147 EXPECT_EQ(uint8_t(0x40), bit_floor(uint8_t(0x7f)));
148 EXPECT_EQ(uint16_t(0x4000), bit_floor(uint16_t(0x7fff)));
149 EXPECT_EQ(uint32_t(0x40000000), bit_floor(uint32_t(0x7fffffff)));
150 EXPECT_EQ(uint64_t(0x4000000000000000),
151 bit_floor(uint64_t(0x7fffffffffffffffull)));
152
153 EXPECT_EQ(uint8_t(0x80), bit_floor(uint8_t(0x80)));
154 EXPECT_EQ(uint16_t(0x8000), bit_floor(uint16_t(0x8000)));
155 EXPECT_EQ(uint32_t(0x80000000), bit_floor(uint32_t(0x80000000)));
156 EXPECT_EQ(uint64_t(0x8000000000000000),
157 bit_floor(uint64_t(0x8000000000000000)));
158
159 EXPECT_EQ(uint8_t(0x80), bit_floor(uint8_t(0xff)));
160 EXPECT_EQ(uint16_t(0x8000), bit_floor(uint16_t(0xffff)));
161 EXPECT_EQ(uint32_t(0x80000000), bit_floor(uint32_t(0xffffffff)));
162 EXPECT_EQ(uint64_t(0x8000000000000000),
163 bit_floor(uint64_t(0xffffffffffffffff)));
164}
165
166TYPED_TEST(LlvmLibcBitTest, RotateIsInvariantForZeroAndOne, UnsignedTypes) {
167 constexpr T all_zeros = T(0);
168 constexpr T all_ones = T(~0);
169 for (int i = 0; i < cpp::numeric_limits<T>::digits; ++i) {
170 EXPECT_EQ(rotl<T>(all_zeros, i), all_zeros);
171 EXPECT_EQ(rotl<T>(all_ones, i), all_ones);
172 EXPECT_EQ(rotr<T>(all_zeros, i), all_zeros);
173 EXPECT_EQ(rotr<T>(all_ones, i), all_ones);
174 }
175}
176
177TEST(LlvmLibcBitTest, Rotl) {
178 EXPECT_EQ(uint8_t(0x53U), rotl<uint8_t>(0x53, 0));
179 EXPECT_EQ(uint8_t(0x4dU), rotl<uint8_t>(0x53, 2));
180 EXPECT_EQ(uint8_t(0xa6U), rotl<uint8_t>(0x53, 9));
181 EXPECT_EQ(uint8_t(0x9aU), rotl<uint8_t>(0x53, -5));
182
183 EXPECT_EQ(uint16_t(0xabcdU), rotl<uint16_t>(0xabcd, 0));
184 EXPECT_EQ(uint16_t(0xf36aU), rotl<uint16_t>(0xabcd, 6));
185 EXPECT_EQ(uint16_t(0xaf36U), rotl<uint16_t>(0xabcd, 18));
186 EXPECT_EQ(uint16_t(0xf36aU), rotl<uint16_t>(0xabcd, -10));
187
188 EXPECT_EQ(uint32_t(0xdeadbeefU), rotl<uint32_t>(0xdeadbeef, 0));
189 EXPECT_EQ(uint32_t(0x7ddfbd5bU), rotl<uint32_t>(0xdeadbeef, 17));
190 EXPECT_EQ(uint32_t(0x5b7ddfbdU), rotl<uint32_t>(0xdeadbeef, 41));
191 EXPECT_EQ(uint32_t(0xb6fbbf7aU), rotl<uint32_t>(0xdeadbeef, -22));
192
193 EXPECT_EQ(uint64_t(0x12345678deadbeefULL),
194 rotl<uint64_t>(0x12345678deadbeefULL, 0));
195 EXPECT_EQ(uint64_t(0xf56df77891a2b3c6ULL),
196 rotl<uint64_t>(0x12345678deadbeefULL, 35));
197 EXPECT_EQ(uint64_t(0x8d159e37ab6fbbc4ULL),
198 rotl<uint64_t>(0x12345678deadbeefULL, 70));
199 EXPECT_EQ(uint64_t(0xb7dde2468acf1bd5ULL),
200 rotl<uint64_t>(0x12345678deadbeefULL, -19));
201}
202
203TEST(LlvmLibcBitTest, Rotr) {
204 EXPECT_EQ(uint8_t(0x53U), rotr<uint8_t>(0x53, 0));
205 EXPECT_EQ(uint8_t(0xd4U), rotr<uint8_t>(0x53, 2));
206 EXPECT_EQ(uint8_t(0xa9U), rotr<uint8_t>(0x53, 9));
207 EXPECT_EQ(uint8_t(0x6aU), rotr<uint8_t>(0x53, -5));
208
209 EXPECT_EQ(uint16_t(0xabcdU), rotr<uint16_t>(0xabcd, 0));
210 EXPECT_EQ(uint16_t(0x36afU), rotr<uint16_t>(0xabcd, 6));
211 EXPECT_EQ(uint16_t(0x6af3U), rotr<uint16_t>(0xabcd, 18));
212 EXPECT_EQ(uint16_t(0x36afU), rotr<uint16_t>(0xabcd, -10));
213
214 EXPECT_EQ(uint32_t(0xdeadbeefU), rotr<uint32_t>(0xdeadbeef, 0));
215 EXPECT_EQ(uint32_t(0xdf77ef56U), rotr<uint32_t>(0xdeadbeef, 17));
216 EXPECT_EQ(uint32_t(0x77ef56dfU), rotr<uint32_t>(0xdeadbeef, 41));
217 EXPECT_EQ(uint32_t(0xbbf7ab6fU), rotr<uint32_t>(0xdeadbeef, -22));
218
219 EXPECT_EQ(uint64_t(0x12345678deadbeefULL),
220 rotr<uint64_t>(0x12345678deadbeefULL, 0));
221 EXPECT_EQ(uint64_t(0x1bd5b7dde2468acfULL),
222 rotr<uint64_t>(0x12345678deadbeefULL, 35));
223 EXPECT_EQ(uint64_t(0xbc48d159e37ab6fbULL),
224 rotr<uint64_t>(0x12345678deadbeefULL, 70));
225 EXPECT_EQ(uint64_t(0xb3c6f56df77891a2ULL),
226 rotr<uint64_t>(0x12345678deadbeefULL, -19));
227}
228
229TYPED_TEST(LlvmLibcBitTest, CountOnes, UnsignedTypes) {
230 EXPECT_EQ(popcount(T(0)), 0);
231 for (int i = 0; i != cpp::numeric_limits<T>::digits; ++i)
232 EXPECT_EQ(
233 popcount<T>(cpp::numeric_limits<T>::max() >> static_cast<size_t>(i)),
234 cpp::numeric_limits<T>::digits - i);
235}
236
237} // namespace cpp
238} // namespace LIBC_NAMESPACE_DECL
239

source code of libc/test/src/__support/CPP/bit_test.cpp