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