1 /*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include <vector>
18
19 #include "bit_utils.h"
20 #include "bit_utils_iterator.h"
21
22 #include "gtest/gtest.h"
23
24 namespace art {
25
26 // NOTE: CLZ(0u) is undefined.
27 static_assert(31 == CLZ<uint32_t>(1u), "TestCLZ32#1");
28 static_assert(30 == CLZ<uint32_t>(2u), "TestCLZ32#2");
29 static_assert(16 == CLZ<uint32_t>(0x00008765u), "TestCLZ32#3");
30 static_assert(15 == CLZ<uint32_t>(0x00012345u), "TestCLZ32#4");
31 static_assert(1 == CLZ<uint32_t>(0x43214321u), "TestCLZ32#5");
32 static_assert(0 == CLZ<uint32_t>(0x87654321u), "TestCLZ32#6");
33
34 // NOTE: CLZ(0ull) is undefined.
35 static_assert(63 == CLZ<uint64_t>(UINT64_C(1)), "TestCLZ64#1");
36 static_assert(62 == CLZ<uint64_t>(UINT64_C(3)), "TestCLZ64#2");
37 static_assert(48 == CLZ<uint64_t>(UINT64_C(0x00008765)), "TestCLZ64#3");
38 static_assert(32 == CLZ<uint64_t>(UINT64_C(0x87654321)), "TestCLZ64#4");
39 static_assert(31 == CLZ<uint64_t>(UINT64_C(0x123456789)), "TestCLZ64#5");
40 static_assert(16 == CLZ<uint64_t>(UINT64_C(0x876543211234)), "TestCLZ64#6");
41 static_assert(1 == CLZ<uint64_t>(UINT64_C(0x4321432187654321)), "TestCLZ64#7");
42 static_assert(0 == CLZ<uint64_t>(UINT64_C(0x8765432187654321)), "TestCLZ64#8");
43
44 // NOTE: CTZ(0u) is undefined.
45 static_assert(0 == CTZ<uint32_t>(1u), "TestCTZ32#1");
46 static_assert(1 == CTZ<uint32_t>(2u), "TestCTZ32#2");
47 static_assert(15 == CTZ<uint32_t>(0x45678000u), "TestCTZ32#3");
48 static_assert(16 == CTZ<uint32_t>(0x43210000u), "TestCTZ32#4");
49 static_assert(30 == CTZ<uint32_t>(0xc0000000u), "TestCTZ32#5");
50 static_assert(31 == CTZ<uint32_t>(0x80000000u), "TestCTZ32#6");
51
52 // NOTE: CTZ(0ull) is undefined.
53 static_assert(0 == CTZ<uint64_t>(UINT64_C(1)), "TestCTZ64#1");
54 static_assert(1 == CTZ<uint64_t>(UINT64_C(2)), "TestCTZ64#2");
55 static_assert(16 == CTZ<uint64_t>(UINT64_C(0x43210000)), "TestCTZ64#3");
56 static_assert(31 == CTZ<uint64_t>(UINT64_C(0x80000000)), "TestCTZ64#4");
57 static_assert(32 == CTZ<uint64_t>(UINT64_C(0x8765432100000000)), "TestCTZ64#5");
58 static_assert(48 == CTZ<uint64_t>(UINT64_C(0x4321000000000000)), "TestCTZ64#6");
59 static_assert(62 == CTZ<uint64_t>(UINT64_C(0x4000000000000000)), "TestCTZ64#7");
60 static_assert(63 == CTZ<uint64_t>(UINT64_C(0x8000000000000000)), "TestCTZ64#8");
61
62 static_assert(0 == POPCOUNT<uint32_t>(0u), "TestPOPCOUNT32#1");
63 static_assert(1 == POPCOUNT<uint32_t>(8u), "TestPOPCOUNT32#2");
64 static_assert(15 == POPCOUNT<uint32_t>(0x55555554u), "TestPOPCOUNT32#3");
65 static_assert(16 == POPCOUNT<uint32_t>(0xaaaaaaaau), "TestPOPCOUNT32#4");
66 static_assert(31 == POPCOUNT<uint32_t>(0xfffffffeu), "TestPOPCOUNT32#5");
67 static_assert(32 == POPCOUNT<uint32_t>(0xffffffffu), "TestPOPCOUNT32#6");
68
69 static_assert(0 == POPCOUNT<uint64_t>(UINT64_C(0)), "TestPOPCOUNT64#1");
70 static_assert(1 == POPCOUNT<uint64_t>(UINT64_C(0x40000)), "TestPOPCOUNT64#2");
71 static_assert(16 == POPCOUNT<uint64_t>(UINT64_C(0x1414141482828282)), "TestPOPCOUNT64#3");
72 static_assert(31 == POPCOUNT<uint64_t>(UINT64_C(0x0000ffff00007fff)), "TestPOPCOUNT64#4");
73 static_assert(32 == POPCOUNT<uint64_t>(UINT64_C(0x5555555555555555)), "TestPOPCOUNT64#5");
74 static_assert(48 == POPCOUNT<uint64_t>(UINT64_C(0x7777bbbbddddeeee)), "TestPOPCOUNT64#6");
75 static_assert(63 == POPCOUNT<uint64_t>(UINT64_C(0x7fffffffffffffff)), "TestPOPCOUNT64#7");
76 static_assert(64 == POPCOUNT<uint64_t>(UINT64_C(0xffffffffffffffff)), "TestPOPCOUNT64#8");
77
78 static_assert(-1 == MostSignificantBit<uint32_t>(0u), "TestMSB32#1");
79 static_assert(0 == MostSignificantBit<uint32_t>(1u), "TestMSB32#2");
80 static_assert(31 == MostSignificantBit<uint32_t>(~static_cast<uint32_t>(0u)), "TestMSB32#3");
81 static_assert(2 == MostSignificantBit<uint32_t>(0b110), "TestMSB32#4");
82 static_assert(2 == MostSignificantBit<uint32_t>(0b100), "TestMSB32#5");
83
84 static_assert(-1 == MostSignificantBit<uint64_t>(UINT64_C(0)), "TestMSB64#1");
85 static_assert(0 == MostSignificantBit<uint64_t>(UINT64_C(1)), "TestMSB64#2");
86 static_assert(63 == MostSignificantBit<uint64_t>(~UINT64_C(0)), "TestMSB64#3");
87 static_assert(34 == MostSignificantBit<uint64_t>(UINT64_C(0x700000000)), "TestMSB64#4");
88 static_assert(34 == MostSignificantBit<uint64_t>(UINT64_C(0x777777777)), "TestMSB64#5");
89
90 static_assert(-1 == LeastSignificantBit<uint32_t>(0u), "TestLSB32#1");
91 static_assert(0 == LeastSignificantBit<uint32_t>(1u), "TestLSB32#1");
92 static_assert(0 == LeastSignificantBit<uint32_t>(~static_cast<uint32_t>(0u)), "TestLSB32#1");
93 static_assert(1 == LeastSignificantBit<uint32_t>(0b110), "TestLSB32#1");
94 static_assert(2 == LeastSignificantBit<uint32_t>(0b100), "TestLSB32#1");
95
96 static_assert(-1 == LeastSignificantBit<uint64_t>(UINT64_C(0)), "TestLSB64#1");
97 static_assert(0 == LeastSignificantBit<uint64_t>(UINT64_C(1)), "TestLSB64#2");
98 static_assert(0 == LeastSignificantBit<uint64_t>(~UINT64_C(0)), "TestLSB64#3");
99 static_assert(12 == LeastSignificantBit<uint64_t>(UINT64_C(0x5000)), "TestLSB64#4");
100 static_assert(48 == LeastSignificantBit<uint64_t>(UINT64_C(0x5555000000000000)), "TestLSB64#5");
101
102 static_assert(0u == MinimumBitsToStore<uint32_t>(0u), "TestMinBits2Store32#1");
103 static_assert(1u == MinimumBitsToStore<uint32_t>(1u), "TestMinBits2Store32#2");
104 static_assert(2u == MinimumBitsToStore<uint32_t>(0b10u), "TestMinBits2Store32#3");
105 static_assert(2u == MinimumBitsToStore<uint32_t>(0b11u), "TestMinBits2Store32#4");
106 static_assert(3u == MinimumBitsToStore<uint32_t>(0b100u), "TestMinBits2Store32#5");
107 static_assert(3u == MinimumBitsToStore<uint32_t>(0b110u), "TestMinBits2Store32#6");
108 static_assert(3u == MinimumBitsToStore<uint32_t>(0b101u), "TestMinBits2Store32#7");
109 static_assert(8u == MinimumBitsToStore<uint32_t>(0xFFu), "TestMinBits2Store32#8");
110 static_assert(32u == MinimumBitsToStore<uint32_t>(~static_cast<uint32_t>(0u)),
111 "TestMinBits2Store32#9");
112
113 static_assert(0u == MinimumBitsToStore<uint64_t>(UINT64_C(0)), "TestMinBits2Store64#1");
114 static_assert(1u == MinimumBitsToStore<uint64_t>(UINT64_C(1)), "TestMinBits2Store64#2");
115 static_assert(2u == MinimumBitsToStore<uint64_t>(UINT64_C(0b10)), "TestMinBits2Store64#3");
116 static_assert(2u == MinimumBitsToStore<uint64_t>(UINT64_C(0b11)), "TestMinBits2Store64#4");
117 static_assert(3u == MinimumBitsToStore<uint64_t>(UINT64_C(0b100)), "TestMinBits2Store64#5");
118 static_assert(3u == MinimumBitsToStore<uint64_t>(UINT64_C(0b110)), "TestMinBits2Store64#6");
119 static_assert(3u == MinimumBitsToStore<uint64_t>(UINT64_C(0b101)), "TestMinBits2Store64#7");
120 static_assert(8u == MinimumBitsToStore<uint64_t>(UINT64_C(0xFF)), "TestMinBits2Store64#8");
121 static_assert(32u == MinimumBitsToStore<uint64_t>(UINT64_C(0xFFFFFFFF)), "TestMinBits2Store64#9");
122 static_assert(33u == MinimumBitsToStore<uint64_t>(UINT64_C(0x1FFFFFFFF)), "TestMinBits2Store64#10");
123 static_assert(64u == MinimumBitsToStore<uint64_t>(~UINT64_C(0)), "TestMinBits2Store64#11");
124
125 static_assert(0 == TruncToPowerOfTwo<uint32_t>(0u), "TestTruncToPowerOfTwo32#1");
126 static_assert(1 == TruncToPowerOfTwo<uint32_t>(1u), "TestTruncToPowerOfTwo32#2");
127 static_assert(2 == TruncToPowerOfTwo<uint32_t>(2u), "TestTruncToPowerOfTwo32#3");
128 static_assert(2 == TruncToPowerOfTwo<uint32_t>(3u), "TestTruncToPowerOfTwo32#4");
129 static_assert(4 == TruncToPowerOfTwo<uint32_t>(7u), "TestTruncToPowerOfTwo32#5");
130 static_assert(0x20000u == TruncToPowerOfTwo<uint32_t>(0x3aaaau),
131 "TestTruncToPowerOfTwo32#6");
132 static_assert(0x40000000u == TruncToPowerOfTwo<uint32_t>(0x40000001u),
133 "TestTruncToPowerOfTwo32#7");
134 static_assert(0x80000000u == TruncToPowerOfTwo<uint32_t>(0x80000000u),
135 "TestTruncToPowerOfTwo32#8");
136
137 static_assert(0 == TruncToPowerOfTwo<uint64_t>(UINT64_C(0)), "TestTruncToPowerOfTwo64#1");
138 static_assert(1 == TruncToPowerOfTwo<uint64_t>(UINT64_C(1)), "TestTruncToPowerOfTwo64#2");
139 static_assert(2 == TruncToPowerOfTwo<uint64_t>(UINT64_C(2)), "TestTruncToPowerOfTwo64#3");
140 static_assert(2 == TruncToPowerOfTwo<uint64_t>(UINT64_C(3)), "TestTruncToPowerOfTwo64#4");
141 static_assert(4 == TruncToPowerOfTwo<uint64_t>(UINT64_C(7)), "TestTruncToPowerOfTwo64#5");
142 static_assert(UINT64_C(0x20000) == TruncToPowerOfTwo<uint64_t>(UINT64_C(0x3aaaa)),
143 "TestTruncToPowerOfTwo64#6");
144 static_assert(
145 UINT64_C(0x4000000000000000) == TruncToPowerOfTwo<uint64_t>(UINT64_C(0x4000000000000001)),
146 "TestTruncToPowerOfTwo64#7");
147 static_assert(
148 UINT64_C(0x8000000000000000) == TruncToPowerOfTwo<uint64_t>(UINT64_C(0x8000000000000000)),
149 "TestTruncToPowerOfTwo64#8");
150
151 static_assert(0 == RoundUpToPowerOfTwo<uint32_t>(0u), "TestRoundUpPowerOfTwo32#1");
152 static_assert(1 == RoundUpToPowerOfTwo<uint32_t>(1u), "TestRoundUpPowerOfTwo32#2");
153 static_assert(2 == RoundUpToPowerOfTwo<uint32_t>(2u), "TestRoundUpPowerOfTwo32#3");
154 static_assert(4 == RoundUpToPowerOfTwo<uint32_t>(3u), "TestRoundUpPowerOfTwo32#4");
155 static_assert(8 == RoundUpToPowerOfTwo<uint32_t>(7u), "TestRoundUpPowerOfTwo32#5");
156 static_assert(0x40000u == RoundUpToPowerOfTwo<uint32_t>(0x2aaaau),
157 "TestRoundUpPowerOfTwo32#6");
158 static_assert(0x80000000u == RoundUpToPowerOfTwo<uint32_t>(0x40000001u),
159 "TestRoundUpPowerOfTwo32#7");
160 static_assert(0x80000000u == RoundUpToPowerOfTwo<uint32_t>(0x80000000u),
161 "TestRoundUpPowerOfTwo32#8");
162
163 static_assert(0 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0)), "TestRoundUpPowerOfTwo64#1");
164 static_assert(1 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(1)), "TestRoundUpPowerOfTwo64#2");
165 static_assert(2 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(2)), "TestRoundUpPowerOfTwo64#3");
166 static_assert(4 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(3)), "TestRoundUpPowerOfTwo64#4");
167 static_assert(8 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(7)), "TestRoundUpPowerOfTwo64#5");
168 static_assert(UINT64_C(0x40000) == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0x2aaaa)),
169 "TestRoundUpPowerOfTwo64#6");
170 static_assert(
171 UINT64_C(0x8000000000000000) == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0x4000000000000001)),
172 "TestRoundUpPowerOfTwo64#7");
173 static_assert(
174 UINT64_C(0x8000000000000000) == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0x8000000000000000)),
175 "TestRoundUpPowerOfTwo64#8");
176
177 static constexpr int64_t kInt32MinMinus1 =
178 static_cast<int64_t>(std::numeric_limits<int32_t>::min()) - 1;
179 static constexpr int64_t kInt32MaxPlus1 =
180 static_cast<int64_t>(std::numeric_limits<int32_t>::max()) + 1;
181 static constexpr int64_t kUint32MaxPlus1 =
182 static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 1;
183
TEST(BitUtilsTest,TestIsInt32)184 TEST(BitUtilsTest, TestIsInt32) {
185 EXPECT_FALSE(IsInt<int32_t>(1, -2));
186 EXPECT_TRUE(IsInt<int32_t>(1, -1));
187 EXPECT_TRUE(IsInt<int32_t>(1, 0));
188 EXPECT_FALSE(IsInt<int32_t>(1, 1));
189 EXPECT_FALSE(IsInt<int32_t>(4, -9));
190 EXPECT_TRUE(IsInt<int32_t>(4, -8));
191 EXPECT_TRUE(IsInt<int32_t>(4, 7));
192 EXPECT_FALSE(IsInt<int32_t>(4, 8));
193 EXPECT_FALSE(IsInt<int32_t>(31, std::numeric_limits<int32_t>::min()));
194 EXPECT_FALSE(IsInt<int32_t>(31, std::numeric_limits<int32_t>::max()));
195 EXPECT_TRUE(IsInt<int32_t>(32, std::numeric_limits<int32_t>::min()));
196 EXPECT_TRUE(IsInt<int32_t>(32, std::numeric_limits<int32_t>::max()));
197 }
198
TEST(BitUtilsTest,TestIsInt64)199 TEST(BitUtilsTest, TestIsInt64) {
200 EXPECT_FALSE(IsInt<int64_t>(1, -2));
201 EXPECT_TRUE(IsInt<int64_t>(1, -1));
202 EXPECT_TRUE(IsInt<int64_t>(1, 0));
203 EXPECT_FALSE(IsInt<int64_t>(1, 1));
204 EXPECT_FALSE(IsInt<int64_t>(4, -9));
205 EXPECT_TRUE(IsInt<int64_t>(4, -8));
206 EXPECT_TRUE(IsInt<int64_t>(4, 7));
207 EXPECT_FALSE(IsInt<int64_t>(4, 8));
208 EXPECT_FALSE(IsInt<int64_t>(31, std::numeric_limits<int32_t>::min()));
209 EXPECT_FALSE(IsInt<int64_t>(31, std::numeric_limits<int32_t>::max()));
210 EXPECT_TRUE(IsInt<int64_t>(32, std::numeric_limits<int32_t>::min()));
211 EXPECT_TRUE(IsInt<int64_t>(32, std::numeric_limits<int32_t>::max()));
212 EXPECT_FALSE(IsInt<int64_t>(32, kInt32MinMinus1));
213 EXPECT_FALSE(IsInt<int64_t>(32, kInt32MaxPlus1));
214 EXPECT_FALSE(IsInt<int64_t>(63, std::numeric_limits<int64_t>::min()));
215 EXPECT_FALSE(IsInt<int64_t>(63, std::numeric_limits<int64_t>::max()));
216 EXPECT_TRUE(IsInt<int64_t>(64, std::numeric_limits<int64_t>::min()));
217 EXPECT_TRUE(IsInt<int64_t>(64, std::numeric_limits<int64_t>::max()));
218 }
219
220 static_assert(!IsInt<1, int32_t>(-2), "TestIsInt32#1");
221 static_assert(IsInt<1, int32_t>(-1), "TestIsInt32#2");
222 static_assert(IsInt<1, int32_t>(0), "TestIsInt32#3");
223 static_assert(!IsInt<1, int32_t>(1), "TestIsInt32#4");
224 static_assert(!IsInt<4, int32_t>(-9), "TestIsInt32#5");
225 static_assert(IsInt<4, int32_t>(-8), "TestIsInt32#6");
226 static_assert(IsInt<4, int32_t>(7), "TestIsInt32#7");
227 static_assert(!IsInt<4, int32_t>(8), "TestIsInt32#8");
228 static_assert(!IsInt<31, int32_t>(std::numeric_limits<int32_t>::min()), "TestIsInt32#9");
229 static_assert(!IsInt<31, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsInt32#10");
230 static_assert(IsInt<32, int32_t>(std::numeric_limits<int32_t>::min()), "TestIsInt32#11");
231 static_assert(IsInt<32, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsInt32#12");
232
233 static_assert(!IsInt<1, int64_t>(-2), "TestIsInt64#1");
234 static_assert(IsInt<1, int64_t>(-1), "TestIsInt64#2");
235 static_assert(IsInt<1, int64_t>(0), "TestIsInt64#3");
236 static_assert(!IsInt<1, int64_t>(1), "TestIsInt64#4");
237 static_assert(!IsInt<4, int64_t>(-9), "TestIsInt64#5");
238 static_assert(IsInt<4, int64_t>(-8), "TestIsInt64#6");
239 static_assert(IsInt<4, int64_t>(7), "TestIsInt64#7");
240 static_assert(!IsInt<4, int64_t>(8), "TestIsInt64#8");
241 static_assert(!IsInt<31, int64_t>(std::numeric_limits<int32_t>::min()), "TestIsInt64#9");
242 static_assert(!IsInt<31, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsInt64#10");
243 static_assert(IsInt<32, int64_t>(std::numeric_limits<int32_t>::min()), "TestIsInt64#11");
244 static_assert(IsInt<32, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsInt64#12");
245 static_assert(!IsInt<32, int64_t>(kInt32MinMinus1), "TestIsInt64#13");
246 static_assert(!IsInt<32, int64_t>(kInt32MaxPlus1), "TestIsInt64#14");
247 static_assert(!IsInt<63, int64_t>(std::numeric_limits<int64_t>::min()), "TestIsInt64#15");
248 static_assert(!IsInt<63, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsInt64#16");
249 static_assert(IsInt<64, int64_t>(std::numeric_limits<int64_t>::min()), "TestIsInt64#17");
250 static_assert(IsInt<64, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsInt64#18");
251
252 static_assert(!IsUint<1, int32_t>(-1), "TestIsUint32#1");
253 static_assert(IsUint<1, int32_t>(0), "TestIsUint32#2");
254 static_assert(IsUint<1, int32_t>(1), "TestIsUint32#3");
255 static_assert(!IsUint<1, int32_t>(2), "TestIsUint32#4");
256 static_assert(!IsUint<4, int32_t>(-1), "TestIsUint32#5");
257 static_assert(IsUint<4, int32_t>(0), "TestIsUint32#6");
258 static_assert(IsUint<4, int32_t>(15), "TestIsUint32#7");
259 static_assert(!IsUint<4, int32_t>(16), "TestIsUint32#8");
260 static_assert(!IsUint<30, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsUint32#9");
261 static_assert(IsUint<31, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsUint32#10");
262 static_assert(!IsUint<32, int32_t>(-1), "TestIsUint32#11");
263 static_assert(IsUint<32, int32_t>(0), "TestIsUint32#11");
264 static_assert(IsUint<32, uint32_t>(static_cast<uint32_t>(-1)), "TestIsUint32#12");
265
266 static_assert(!IsUint<1, int64_t>(-1), "TestIsUint64#1");
267 static_assert(IsUint<1, int64_t>(0), "TestIsUint64#2");
268 static_assert(IsUint<1, int64_t>(1), "TestIsUint64#3");
269 static_assert(!IsUint<1, int64_t>(2), "TestIsUint64#4");
270 static_assert(!IsUint<4, int64_t>(-1), "TestIsUint64#5");
271 static_assert(IsUint<4, int64_t>(0), "TestIsUint64#6");
272 static_assert(IsUint<4, int64_t>(15), "TestIsUint64#7");
273 static_assert(!IsUint<4, int64_t>(16), "TestIsUint64#8");
274 static_assert(!IsUint<30, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsUint64#9");
275 static_assert(IsUint<31, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsUint64#10");
276 static_assert(!IsUint<62, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsUint64#11");
277 static_assert(IsUint<63, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsUint64#12");
278 static_assert(!IsUint<64, int64_t>(-1), "TestIsUint64#13");
279 static_assert(IsUint<64, int64_t>(0), "TestIsUint64#14");
280 static_assert(IsUint<64, uint64_t>(static_cast<uint32_t>(-1)), "TestIsUint64#15");
281
282 static_assert(!IsAbsoluteUint<1, int32_t>(-2), "TestIsAbsoluteUint32#1");
283 static_assert(IsAbsoluteUint<1, int32_t>(-1), "TestIsAbsoluteUint32#2");
284 static_assert(IsAbsoluteUint<1, int32_t>(0), "TestIsAbsoluteUint32#3");
285 static_assert(IsAbsoluteUint<1, int32_t>(1), "TestIsAbsoluteUint32#4");
286 static_assert(!IsAbsoluteUint<1, int32_t>(2), "TestIsAbsoluteUint32#5");
287 static_assert(!IsAbsoluteUint<4, int32_t>(-16), "TestIsAbsoluteUint32#6");
288 static_assert(IsAbsoluteUint<4, int32_t>(-15), "TestIsAbsoluteUint32#7");
289 static_assert(IsAbsoluteUint<4, int32_t>(0), "TestIsAbsoluteUint32#8");
290 static_assert(IsAbsoluteUint<4, int32_t>(15), "TestIsAbsoluteUint32#9");
291 static_assert(!IsAbsoluteUint<4, int32_t>(16), "TestIsAbsoluteUint32#10");
292 static_assert(!IsAbsoluteUint<30, int32_t>(std::numeric_limits<int32_t>::max()),
293 "TestIsAbsoluteUint32#11");
294 static_assert(IsAbsoluteUint<31, int32_t>(std::numeric_limits<int32_t>::max()),
295 "TestIsAbsoluteUint32#12");
296 static_assert(!IsAbsoluteUint<31, int32_t>(std::numeric_limits<int32_t>::min()),
297 "TestIsAbsoluteUint32#13");
298 static_assert(IsAbsoluteUint<31, int32_t>(std::numeric_limits<int32_t>::min() + 1),
299 "TestIsAbsoluteUint32#14");
300 static_assert(IsAbsoluteUint<32, int32_t>(std::numeric_limits<int32_t>::max()),
301 "TestIsAbsoluteUint32#15");
302 static_assert(IsAbsoluteUint<32, int32_t>(std::numeric_limits<int32_t>::min()),
303 "TestIsAbsoluteUint32#16");
304 static_assert(IsAbsoluteUint<32, int32_t>(0), "TestIsAbsoluteUint32#17");
305
306 static_assert(!IsAbsoluteUint<1, int64_t>(-2), "TestIsAbsoluteUint64#1");
307 static_assert(IsAbsoluteUint<1, int64_t>(-1), "TestIsAbsoluteUint64#2");
308 static_assert(IsAbsoluteUint<1, int64_t>(0), "TestIsAbsoluteUint64#3");
309 static_assert(IsAbsoluteUint<1, int64_t>(1), "TestIsAbsoluteUint64#4");
310 static_assert(!IsAbsoluteUint<1, int64_t>(2), "TestIsAbsoluteUint64#5");
311 static_assert(!IsAbsoluteUint<4, int64_t>(-16), "TestIsAbsoluteUint64#6");
312 static_assert(IsAbsoluteUint<4, int64_t>(-15), "TestIsAbsoluteUint64#7");
313 static_assert(IsAbsoluteUint<4, int64_t>(0), "TestIsAbsoluteUint64#8");
314 static_assert(IsAbsoluteUint<4, int64_t>(15), "TestIsAbsoluteUint64#9");
315 static_assert(!IsAbsoluteUint<4, int64_t>(16), "TestIsAbsoluteUint64#10");
316 static_assert(!IsAbsoluteUint<30, int64_t>(std::numeric_limits<int32_t>::max()),
317 "TestIsAbsoluteUint64#11");
318 static_assert(IsAbsoluteUint<31, int64_t>(std::numeric_limits<int32_t>::max()),
319 "TestIsAbsoluteUint64#12");
320 static_assert(!IsAbsoluteUint<31, int64_t>(std::numeric_limits<int32_t>::min()),
321 "TestIsAbsoluteUint64#13");
322 static_assert(IsAbsoluteUint<31, int64_t>(std::numeric_limits<int32_t>::min() + 1),
323 "TestIsAbsoluteUint64#14");
324 static_assert(IsAbsoluteUint<32, int64_t>(std::numeric_limits<int32_t>::max()),
325 "TestIsAbsoluteUint64#15");
326 static_assert(IsAbsoluteUint<32, int64_t>(std::numeric_limits<int32_t>::min()),
327 "TestIsAbsoluteUint64#16");
328 static_assert(!IsAbsoluteUint<62, int64_t>(std::numeric_limits<int64_t>::max()),
329 "TestIsAbsoluteUint64#17");
330 static_assert(IsAbsoluteUint<63, int64_t>(std::numeric_limits<int64_t>::max()),
331 "TestIsAbsoluteUint64#18");
332 static_assert(!IsAbsoluteUint<63, int64_t>(std::numeric_limits<int64_t>::min()),
333 "TestIsAbsoluteUint64#19");
334 static_assert(IsAbsoluteUint<63, int64_t>(std::numeric_limits<int64_t>::min() + 1),
335 "TestIsAbsoluteUint64#20");
336 static_assert(IsAbsoluteUint<64, int64_t>(std::numeric_limits<int64_t>::max()),
337 "TestIsAbsoluteUint64#21");
338 static_assert(IsAbsoluteUint<64, int64_t>(std::numeric_limits<int64_t>::min()),
339 "TestIsAbsoluteUint64#22");
340 static_assert(!IsAbsoluteUint<32, int64_t>(-kUint32MaxPlus1), "TestIsAbsoluteUint64#23");
341 static_assert(IsAbsoluteUint<32, int64_t>(-kUint32MaxPlus1 + 1), "TestIsAbsoluteUint64#24");
342 static_assert(IsAbsoluteUint<32, int64_t>(0), "TestIsAbsoluteUint64#25");
343 static_assert(IsAbsoluteUint<64, int64_t>(0), "TestIsAbsoluteUint64#26");
344 static_assert(IsAbsoluteUint<32, int64_t>(std::numeric_limits<uint32_t>::max()),
345 "TestIsAbsoluteUint64#27");
346 static_assert(!IsAbsoluteUint<32, int64_t>(kUint32MaxPlus1), "TestIsAbsoluteUint64#28");
347
348 static_assert(MaskLeastSignificant(0) == 0b0, "TestMaskLeastSignificant#1");
349 static_assert(MaskLeastSignificant(1) == 0b1, "TestMaskLeastSignificant#2");
350 static_assert(MaskLeastSignificant(2) == 0b11, "TestMaskLeastSignificant#3");
351 static_assert(MaskLeastSignificant<uint8_t>(8) == 0xFF, "TestMaskLeastSignificant#4");
352 static_assert(MaskLeastSignificant<int8_t>(8) == 0xFF, "TestMaskLeastSignificant#5");
353 static_assert(MaskLeastSignificant<uint64_t>(63) == (std::numeric_limits<uint64_t>::max() >> 1u),
354 "TestMaskLeastSignificant#6");
355
356 static_assert(BitFieldClear(0xFF, /*lsb=*/0, /*width=*/0) == 0xFF, "TestBitFieldClear#1");
357 static_assert(BitFieldClear(std::numeric_limits<uint32_t>::max(), /*lsb=*/0, /*width=*/32) == 0x0,
358 "TestBitFieldClear#2");
359 static_assert(BitFieldClear(std::numeric_limits<int32_t>::max(), /*lsb=*/0, /*width=*/32) == 0x0,
360 "TestBitFieldClear#3");
361 static_assert(BitFieldClear(0xFF, /*lsb=*/0, /*width=*/2) == 0b11111100, "TestBitFieldClear#4");
362 static_assert(BitFieldClear(0xFF, /*lsb=*/0, /*width=*/3) == 0b11111000, "TestBitFieldClear#5");
363 static_assert(BitFieldClear(0xFF, /*lsb=*/1, /*width=*/3) == 0b11110001, "TestBitFieldClear#6");
364 static_assert(BitFieldClear(0xFF, /*lsb=*/2, /*width=*/3) == 0b11100011, "TestBitFieldClear#7");
365
366 static_assert(BitFieldExtract(0xFF, /*lsb=*/0, /*width=*/0) == 0x0, "TestBitFieldExtract#1");
367 static_assert(BitFieldExtract(std::numeric_limits<uint32_t>::max(), /*lsb=*/0, /*width=*/32)
368 == std::numeric_limits<uint32_t>::max(),
369 "TestBitFieldExtract#2");
370 static_assert(BitFieldExtract(std::numeric_limits<int32_t>::max(), /*lsb=*/0, /*width=*/32)
371 == std::numeric_limits<int32_t>::max(),
372 "TestBitFieldExtract#3");
373 static_assert(BitFieldExtract(static_cast<uint32_t>(0xFF), /*lsb=*/0, /*width=*/2) == 0b00000011,
374 "TestBitFieldExtract#4");
375 static_assert(BitFieldExtract(static_cast<uint32_t>(0xFF), /*lsb=*/0, /*width=*/3) == 0b00000111,
376 "TestBitFieldExtract#5");
377 static_assert(BitFieldExtract(static_cast<uint32_t>(0xFF), /*lsb=*/1, /*width=*/3) == 0b00000111,
378 "TestBitFieldExtract#6");
379 static_assert(BitFieldExtract(static_cast<uint32_t>(0xFF), /*lsb=*/2, /*width=*/3) == 0b00000111,
380 "TestBitFieldExtract#7");
381 static_assert(BitFieldExtract(static_cast<uint32_t>(0xFF), /*lsb=*/3, /*width=*/3) == 0b00000111,
382 "TestBitFieldExtract#8");
383 static_assert(BitFieldExtract(static_cast<uint32_t>(0xFF), /*lsb=*/8, /*width=*/3) == 0b00000000,
384 "TestBitFieldExtract#9");
385 static_assert(BitFieldExtract(static_cast<uint32_t>(0xFF), /*lsb=*/7, /*width=*/3) == 0b00000001,
386 "TestBitFieldExtract#10");
387 static_assert(BitFieldExtract(static_cast<uint32_t>(0xFF), /*lsb=*/6, /*width=*/3) == 0b00000011,
388 "TestBitFieldExtract#11");
389 static_assert(BitFieldExtract(0xFF, /*lsb=*/0, /*width=*/2) == -1, "TestBitFieldExtract#12");
390 static_assert(BitFieldExtract(0xFF, /*lsb=*/0, /*width=*/3) == -1, "TestBitFieldExtract#13");
391 static_assert(BitFieldExtract(0xFF, /*lsb=*/1, /*width=*/3) == -1, "TestBitFieldExtract#14");
392 static_assert(BitFieldExtract(0xFF, /*lsb=*/2, /*width=*/3) == -1, "TestBitFieldExtract#15");
393 static_assert(BitFieldExtract(0xFF, /*lsb=*/3, /*width=*/3) == -1, "TestBitFieldExtract#16");
394 static_assert(BitFieldExtract(0xFF, /*lsb=*/8, /*width=*/3) == 0b00000000,
395 "TestBitFieldExtract#17");
396 static_assert(BitFieldExtract(0xFF, /*lsb=*/7, /*width=*/3) == 0b00000001,
397 "TestBitFieldExtract#18");
398 static_assert(BitFieldExtract(0xFF, /*lsb=*/6, /*width=*/3) == 0b00000011,
399 "TestBitFieldExtract#19");
400 static_assert(BitFieldExtract(static_cast<uint8_t>(0b01101010), /*lsb=*/2, /*width=*/4)
401 == 0b00001010,
402 "TestBitFieldExtract#20");
403 static_assert(BitFieldExtract(static_cast<int8_t>(0b01101010), /*lsb=*/2, /*width=*/4)
404 == static_cast<int8_t>(0b11111010),
405 "TestBitFieldExtract#21");
406
407 static_assert(BitFieldInsert(0xFF, /*data=*/0x0, /*lsb=*/0, /*width=*/0) == 0xFF,
408 "TestBitFieldInsert#1");
409 static_assert(BitFieldInsert(std::numeric_limits<uint32_t>::max(),
410 /*data=*/std::numeric_limits<uint32_t>::max(),
411 /*lsb=*/0,
412 /*width=*/32)
413 == std::numeric_limits<uint32_t>::max(),
414 "TestBitFieldInsert#2");
415 static_assert(BitFieldInsert(std::numeric_limits<int32_t>::max(),
416 /*data=*/std::numeric_limits<uint32_t>::max(),
417 /*lsb=*/0,
418 /*width=*/32)
419 == std::numeric_limits<uint32_t>::max(),
420 "TestBitFieldInsert#3");
421 static_assert(BitFieldInsert(0u,
422 /*data=*/std::numeric_limits<uint32_t>::max(),
423 /*lsb=*/0,
424 /*width=*/32)
425 == std::numeric_limits<uint32_t>::max(),
426 "TestBitFieldInsert#4");
427 static_assert(BitFieldInsert(-(-0),
428 /*data=*/std::numeric_limits<uint32_t>::max(),
429 /*lsb=*/0,
430 /*width=*/32)
431 == std::numeric_limits<uint32_t>::max(),
432 "TestBitFieldInsert#5");
433 static_assert(BitFieldInsert(0x00, /*data=*/0b11u, /*lsb=*/0, /*width=*/2) == 0b00000011,
434 "TestBitFieldInsert#6");
435 static_assert(BitFieldInsert(0x00, /*data=*/0b111u, /*lsb=*/0, /*width=*/3) == 0b00000111,
436 "TestBitFieldInsert#7");
437 static_assert(BitFieldInsert(0x00, /*data=*/0b111u, /*lsb=*/1, /*width=*/3) == 0b00001110,
438 "TestBitFieldInsert#8");
439 static_assert(BitFieldInsert(0x00, /*data=*/0b111u, /*lsb=*/2, /*width=*/3) == 0b00011100,
440 "TestBitFieldInsert#9");
441 static_assert(BitFieldInsert(0b01011100, /*data=*/0b1101u, /*lsb=*/4, /*width=*/4) == 0b11011100,
442 "TestBitFieldInsert#10");
443
444 template <typename Container>
CheckElements(const std::initializer_list<uint32_t> & expected,const Container & elements)445 void CheckElements(const std::initializer_list<uint32_t>& expected, const Container& elements) {
446 auto expected_it = expected.begin();
447 auto element_it = elements.begin();
448 size_t idx = 0u;
449 while (expected_it != expected.end() && element_it != elements.end()) {
450 EXPECT_EQ(*expected_it, *element_it) << idx;
451 ++idx;
452 ++expected_it;
453 ++element_it;
454 }
455 ASSERT_TRUE(expected_it == expected.end() && element_it == elements.end())
456 << std::boolalpha << (expected_it == expected.end()) << " " << (element_it == elements.end());
457 }
458
TEST(BitUtilsTest,TestLowToHighBits32)459 TEST(BitUtilsTest, TestLowToHighBits32) {
460 CheckElements({}, LowToHighBits<uint32_t>(0u));
461 CheckElements({0}, LowToHighBits<uint32_t>(1u));
462 CheckElements({15}, LowToHighBits<uint32_t>(0x8000u));
463 CheckElements({31}, LowToHighBits<uint32_t>(0x80000000u));
464 CheckElements({0, 31}, LowToHighBits<uint32_t>(0x80000001u));
465 CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 31}, LowToHighBits<uint32_t>(0x800000ffu));
466 CheckElements({0, 8, 16, 24, 31}, LowToHighBits<uint32_t>(0x81010101u));
467 CheckElements({16, 17, 30, 31}, LowToHighBits<uint32_t>(0xc0030000u));
468 CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
469 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31},
470 LowToHighBits<uint32_t>(0xffffffffu));
471 }
472
TEST(BitUtilsTest,TestLowToHighBits64)473 TEST(BitUtilsTest, TestLowToHighBits64) {
474 CheckElements({}, LowToHighBits<uint64_t>(UINT64_C(0)));
475 CheckElements({0}, LowToHighBits<uint64_t>(UINT64_C(1)));
476 CheckElements({32}, LowToHighBits<uint64_t>(UINT64_C(0x100000000)));
477 CheckElements({63}, LowToHighBits<uint64_t>(UINT64_C(0x8000000000000000)));
478 CheckElements({0, 63}, LowToHighBits<uint64_t>(UINT64_C(0x8000000000000001)));
479 CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 63},
480 LowToHighBits<uint64_t>(UINT64_C(0x80000000000000ff)));
481 CheckElements({0, 8, 16, 24, 32, 40, 48, 56, 63},
482 LowToHighBits<uint64_t>(UINT64_C(0x8101010101010101)));
483 CheckElements({16, 17, 62, 63}, LowToHighBits<uint64_t>(UINT64_C(0xc000000000030000)));
484 CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
485 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
486 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
487 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63},
488 LowToHighBits<uint64_t>(UINT64_C(0xffffffffffffffff)));
489 }
490
TEST(BitUtilsTest,TestHighToLowBits32)491 TEST(BitUtilsTest, TestHighToLowBits32) {
492 CheckElements({}, HighToLowBits<uint32_t>(0u));
493 CheckElements({0}, HighToLowBits<uint32_t>(1u));
494 CheckElements({15}, HighToLowBits<uint32_t>(0x8000u));
495 CheckElements({31}, HighToLowBits<uint32_t>(0x80000000u));
496 CheckElements({31, 0}, HighToLowBits<uint32_t>(0x80000001u));
497 CheckElements({31, 7, 6, 5, 4, 3, 2, 1, 0}, HighToLowBits<uint32_t>(0x800000ffu));
498 CheckElements({31, 24, 16, 8, 0}, HighToLowBits<uint32_t>(0x81010101u));
499 CheckElements({31, 30, 17, 16}, HighToLowBits<uint32_t>(0xc0030000u));
500 CheckElements({31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16,
501 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
502 HighToLowBits<uint32_t>(0xffffffffu));
503 }
504
TEST(BitUtilsTest,TestHighToLowBits64)505 TEST(BitUtilsTest, TestHighToLowBits64) {
506 CheckElements({}, HighToLowBits<uint64_t>(UINT64_C(0)));
507 CheckElements({0}, HighToLowBits<uint64_t>(UINT64_C(1)));
508 CheckElements({32}, HighToLowBits<uint64_t>(UINT64_C(0x100000000)));
509 CheckElements({63}, HighToLowBits<uint64_t>(UINT64_C(0x8000000000000000)));
510 CheckElements({63, 0}, HighToLowBits<uint64_t>(UINT64_C(0x8000000000000001)));
511 CheckElements({63, 7, 6, 5, 4, 3, 2, 1, 0},
512 HighToLowBits<uint64_t>(UINT64_C(0x80000000000000ff)));
513 CheckElements({63, 56, 48, 40, 32, 24, 16, 8, 0},
514 HighToLowBits<uint64_t>(UINT64_C(0x8101010101010101)));
515 CheckElements({63, 62, 17, 16}, HighToLowBits<uint64_t>(UINT64_C(0xc000000000030000)));
516 CheckElements({63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48,
517 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32,
518 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16,
519 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
520 HighToLowBits<uint64_t>(UINT64_C(0xffffffffffffffff)));
521 }
522
523 } // namespace art
524