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
21#include "gtest/gtest.h"
22
23namespace art {
24
25// NOTE: CLZ(0u) is undefined.
26static_assert(31 == CLZ<uint32_t>(1u), "TestCLZ32#1");
27static_assert(30 == CLZ<uint32_t>(2u), "TestCLZ32#2");
28static_assert(16 == CLZ<uint32_t>(0x00008765u), "TestCLZ32#3");
29static_assert(15 == CLZ<uint32_t>(0x00012345u), "TestCLZ32#4");
30static_assert(1 == CLZ<uint32_t>(0x43214321u), "TestCLZ32#5");
31static_assert(0 == CLZ<uint32_t>(0x87654321u), "TestCLZ32#6");
32
33// NOTE: CLZ(0ull) is undefined.
34static_assert(63 == CLZ<uint64_t>(UINT64_C(1)), "TestCLZ64#1");
35static_assert(62 == CLZ<uint64_t>(UINT64_C(3)), "TestCLZ64#2");
36static_assert(48 == CLZ<uint64_t>(UINT64_C(0x00008765)), "TestCLZ64#3");
37static_assert(32 == CLZ<uint64_t>(UINT64_C(0x87654321)), "TestCLZ64#4");
38static_assert(31 == CLZ<uint64_t>(UINT64_C(0x123456789)), "TestCLZ64#5");
39static_assert(16 == CLZ<uint64_t>(UINT64_C(0x876543211234)), "TestCLZ64#6");
40static_assert(1 == CLZ<uint64_t>(UINT64_C(0x4321432187654321)), "TestCLZ64#7");
41static_assert(0 == CLZ<uint64_t>(UINT64_C(0x8765432187654321)), "TestCLZ64#8");
42
43// NOTE: CTZ(0u) is undefined.
44static_assert(0 == CTZ<uint32_t>(1u), "TestCTZ32#1");
45static_assert(1 == CTZ<uint32_t>(2u), "TestCTZ32#2");
46static_assert(15 == CTZ<uint32_t>(0x45678000u), "TestCTZ32#3");
47static_assert(16 == CTZ<uint32_t>(0x43210000u), "TestCTZ32#4");
48static_assert(30 == CTZ<uint32_t>(0xc0000000u), "TestCTZ32#5");
49static_assert(31 == CTZ<uint32_t>(0x80000000u), "TestCTZ32#6");
50
51// NOTE: CTZ(0ull) is undefined.
52static_assert(0 == CTZ<uint64_t>(UINT64_C(1)), "TestCTZ64#1");
53static_assert(1 == CTZ<uint64_t>(UINT64_C(2)), "TestCTZ64#2");
54static_assert(16 == CTZ<uint64_t>(UINT64_C(0x43210000)), "TestCTZ64#3");
55static_assert(31 == CTZ<uint64_t>(UINT64_C(0x80000000)), "TestCTZ64#4");
56static_assert(32 == CTZ<uint64_t>(UINT64_C(0x8765432100000000)), "TestCTZ64#5");
57static_assert(48 == CTZ<uint64_t>(UINT64_C(0x4321000000000000)), "TestCTZ64#6");
58static_assert(62 == CTZ<uint64_t>(UINT64_C(0x4000000000000000)), "TestCTZ64#7");
59static_assert(63 == CTZ<uint64_t>(UINT64_C(0x8000000000000000)), "TestCTZ64#8");
60
61static_assert(0 == POPCOUNT<uint32_t>(0u), "TestPOPCOUNT32#1");
62static_assert(1 == POPCOUNT<uint32_t>(8u), "TestPOPCOUNT32#2");
63static_assert(15 == POPCOUNT<uint32_t>(0x55555554u), "TestPOPCOUNT32#3");
64static_assert(16 == POPCOUNT<uint32_t>(0xaaaaaaaau), "TestPOPCOUNT32#4");
65static_assert(31 == POPCOUNT<uint32_t>(0xfffffffeu), "TestPOPCOUNT32#5");
66static_assert(32 == POPCOUNT<uint32_t>(0xffffffffu), "TestPOPCOUNT32#6");
67
68static_assert(0 == POPCOUNT<uint64_t>(UINT64_C(0)), "TestPOPCOUNT64#1");
69static_assert(1 == POPCOUNT<uint64_t>(UINT64_C(0x40000)), "TestPOPCOUNT64#2");
70static_assert(16 == POPCOUNT<uint64_t>(UINT64_C(0x1414141482828282)), "TestPOPCOUNT64#3");
71static_assert(31 == POPCOUNT<uint64_t>(UINT64_C(0x0000ffff00007fff)), "TestPOPCOUNT64#4");
72static_assert(32 == POPCOUNT<uint64_t>(UINT64_C(0x5555555555555555)), "TestPOPCOUNT64#5");
73static_assert(48 == POPCOUNT<uint64_t>(UINT64_C(0x7777bbbbddddeeee)), "TestPOPCOUNT64#6");
74static_assert(63 == POPCOUNT<uint64_t>(UINT64_C(0x7fffffffffffffff)), "TestPOPCOUNT64#7");
75static_assert(64 == POPCOUNT<uint64_t>(UINT64_C(0xffffffffffffffff)), "TestPOPCOUNT64#8");
76
77static_assert(-1 == MostSignificantBit<uint32_t>(0u), "TestMSB32#1");
78static_assert(0 == MostSignificantBit<uint32_t>(1u), "TestMSB32#2");
79static_assert(31 == MostSignificantBit<uint32_t>(~static_cast<uint32_t>(0u)), "TestMSB32#3");
80static_assert(2 == MostSignificantBit<uint32_t>(0b110), "TestMSB32#4");
81static_assert(2 == MostSignificantBit<uint32_t>(0b100), "TestMSB32#5");
82
83static_assert(-1 == MostSignificantBit<uint64_t>(UINT64_C(0)), "TestMSB64#1");
84static_assert(0 == MostSignificantBit<uint64_t>(UINT64_C(1)), "TestMSB64#2");
85static_assert(63 == MostSignificantBit<uint64_t>(~UINT64_C(0)), "TestMSB64#3");
86static_assert(34 == MostSignificantBit<uint64_t>(UINT64_C(0x700000000)), "TestMSB64#4");
87static_assert(34 == MostSignificantBit<uint64_t>(UINT64_C(0x777777777)), "TestMSB64#5");
88
89static_assert(-1 == LeastSignificantBit<uint32_t>(0u), "TestLSB32#1");
90static_assert(0 == LeastSignificantBit<uint32_t>(1u), "TestLSB32#1");
91static_assert(0 == LeastSignificantBit<uint32_t>(~static_cast<uint32_t>(0u)), "TestLSB32#1");
92static_assert(1 == LeastSignificantBit<uint32_t>(0b110), "TestLSB32#1");
93static_assert(2 == LeastSignificantBit<uint32_t>(0b100), "TestLSB32#1");
94
95static_assert(-1 == LeastSignificantBit<uint64_t>(UINT64_C(0)), "TestLSB64#1");
96static_assert(0 == LeastSignificantBit<uint64_t>(UINT64_C(1)), "TestLSB64#2");
97static_assert(0 == LeastSignificantBit<uint64_t>(~UINT64_C(0)), "TestLSB64#3");
98static_assert(12 == LeastSignificantBit<uint64_t>(UINT64_C(0x5000)), "TestLSB64#4");
99static_assert(48 == LeastSignificantBit<uint64_t>(UINT64_C(0x5555000000000000)), "TestLSB64#5");
100
101static_assert(0u == MinimumBitsToStore<uint32_t>(0u), "TestMinBits2Store32#1");
102static_assert(1u == MinimumBitsToStore<uint32_t>(1u), "TestMinBits2Store32#2");
103static_assert(2u == MinimumBitsToStore<uint32_t>(0b10u), "TestMinBits2Store32#3");
104static_assert(2u == MinimumBitsToStore<uint32_t>(0b11u), "TestMinBits2Store32#4");
105static_assert(3u == MinimumBitsToStore<uint32_t>(0b100u), "TestMinBits2Store32#5");
106static_assert(3u == MinimumBitsToStore<uint32_t>(0b110u), "TestMinBits2Store32#6");
107static_assert(3u == MinimumBitsToStore<uint32_t>(0b101u), "TestMinBits2Store32#7");
108static_assert(8u == MinimumBitsToStore<uint32_t>(0xFFu), "TestMinBits2Store32#8");
109static_assert(32u == MinimumBitsToStore<uint32_t>(~static_cast<uint32_t>(0u)),
110              "TestMinBits2Store32#9");
111
112static_assert(0u == MinimumBitsToStore<uint64_t>(UINT64_C(0)), "TestMinBits2Store64#1");
113static_assert(1u == MinimumBitsToStore<uint64_t>(UINT64_C(1)), "TestMinBits2Store64#2");
114static_assert(2u == MinimumBitsToStore<uint64_t>(UINT64_C(0b10)), "TestMinBits2Store64#3");
115static_assert(2u == MinimumBitsToStore<uint64_t>(UINT64_C(0b11)), "TestMinBits2Store64#4");
116static_assert(3u == MinimumBitsToStore<uint64_t>(UINT64_C(0b100)), "TestMinBits2Store64#5");
117static_assert(3u == MinimumBitsToStore<uint64_t>(UINT64_C(0b110)), "TestMinBits2Store64#6");
118static_assert(3u == MinimumBitsToStore<uint64_t>(UINT64_C(0b101)), "TestMinBits2Store64#7");
119static_assert(8u == MinimumBitsToStore<uint64_t>(UINT64_C(0xFF)), "TestMinBits2Store64#8");
120static_assert(32u == MinimumBitsToStore<uint64_t>(UINT64_C(0xFFFFFFFF)), "TestMinBits2Store64#9");
121static_assert(33u == MinimumBitsToStore<uint64_t>(UINT64_C(0x1FFFFFFFF)), "TestMinBits2Store64#10");
122static_assert(64u == MinimumBitsToStore<uint64_t>(~UINT64_C(0)), "TestMinBits2Store64#11");
123
124static_assert(0 == RoundUpToPowerOfTwo<uint32_t>(0u), "TestRoundUpPowerOfTwo32#1");
125static_assert(1 == RoundUpToPowerOfTwo<uint32_t>(1u), "TestRoundUpPowerOfTwo32#2");
126static_assert(2 == RoundUpToPowerOfTwo<uint32_t>(2u), "TestRoundUpPowerOfTwo32#3");
127static_assert(4 == RoundUpToPowerOfTwo<uint32_t>(3u), "TestRoundUpPowerOfTwo32#4");
128static_assert(8 == RoundUpToPowerOfTwo<uint32_t>(7u), "TestRoundUpPowerOfTwo32#5");
129static_assert(0x40000u == RoundUpToPowerOfTwo<uint32_t>(0x2aaaau),
130              "TestRoundUpPowerOfTwo32#6");
131static_assert(0x80000000u == RoundUpToPowerOfTwo<uint32_t>(0x40000001u),
132              "TestRoundUpPowerOfTwo32#7");
133static_assert(0x80000000u == RoundUpToPowerOfTwo<uint32_t>(0x80000000u),
134              "TestRoundUpPowerOfTwo32#8");
135
136static_assert(0 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0)), "TestRoundUpPowerOfTwo64#1");
137static_assert(1 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(1)), "TestRoundUpPowerOfTwo64#2");
138static_assert(2 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(2)), "TestRoundUpPowerOfTwo64#3");
139static_assert(4 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(3)), "TestRoundUpPowerOfTwo64#4");
140static_assert(8 == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(7)), "TestRoundUpPowerOfTwo64#5");
141static_assert(UINT64_C(0x40000) == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0x2aaaa)),
142              "TestRoundUpPowerOfTwo64#6");
143static_assert(
144    UINT64_C(0x8000000000000000) == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0x4000000000000001)),
145    "TestRoundUpPowerOfTwo64#7");
146static_assert(
147    UINT64_C(0x8000000000000000) == RoundUpToPowerOfTwo<uint64_t>(UINT64_C(0x8000000000000000)),
148    "TestRoundUpPowerOfTwo64#8");
149
150static constexpr int64_t kInt32MinMinus1 =
151    static_cast<int64_t>(std::numeric_limits<int32_t>::min()) - 1;
152static constexpr int64_t kInt32MaxPlus1 =
153    static_cast<int64_t>(std::numeric_limits<int32_t>::max()) + 1;
154static constexpr int64_t kUint32MaxPlus1 =
155    static_cast<int64_t>(std::numeric_limits<uint32_t>::max()) + 1;
156
157TEST(BitUtilsTest, TestIsInt32) {
158  EXPECT_FALSE(IsInt<int32_t>(1, -2));
159  EXPECT_TRUE(IsInt<int32_t>(1, -1));
160  EXPECT_TRUE(IsInt<int32_t>(1, 0));
161  EXPECT_FALSE(IsInt<int32_t>(1, 1));
162  EXPECT_FALSE(IsInt<int32_t>(4, -9));
163  EXPECT_TRUE(IsInt<int32_t>(4, -8));
164  EXPECT_TRUE(IsInt<int32_t>(4, 7));
165  EXPECT_FALSE(IsInt<int32_t>(4, 8));
166  EXPECT_FALSE(IsInt<int32_t>(31, std::numeric_limits<int32_t>::min()));
167  EXPECT_FALSE(IsInt<int32_t>(31, std::numeric_limits<int32_t>::max()));
168  EXPECT_TRUE(IsInt<int32_t>(32, std::numeric_limits<int32_t>::min()));
169  EXPECT_TRUE(IsInt<int32_t>(32, std::numeric_limits<int32_t>::max()));
170}
171
172TEST(BitUtilsTest, TestIsInt64) {
173  EXPECT_FALSE(IsInt<int64_t>(1, -2));
174  EXPECT_TRUE(IsInt<int64_t>(1, -1));
175  EXPECT_TRUE(IsInt<int64_t>(1, 0));
176  EXPECT_FALSE(IsInt<int64_t>(1, 1));
177  EXPECT_FALSE(IsInt<int64_t>(4, -9));
178  EXPECT_TRUE(IsInt<int64_t>(4, -8));
179  EXPECT_TRUE(IsInt<int64_t>(4, 7));
180  EXPECT_FALSE(IsInt<int64_t>(4, 8));
181  EXPECT_FALSE(IsInt<int64_t>(31, std::numeric_limits<int32_t>::min()));
182  EXPECT_FALSE(IsInt<int64_t>(31, std::numeric_limits<int32_t>::max()));
183  EXPECT_TRUE(IsInt<int64_t>(32, std::numeric_limits<int32_t>::min()));
184  EXPECT_TRUE(IsInt<int64_t>(32, std::numeric_limits<int32_t>::max()));
185  EXPECT_FALSE(IsInt<int64_t>(32, kInt32MinMinus1));
186  EXPECT_FALSE(IsInt<int64_t>(32, kInt32MaxPlus1));
187  EXPECT_FALSE(IsInt<int64_t>(63, std::numeric_limits<int64_t>::min()));
188  EXPECT_FALSE(IsInt<int64_t>(63, std::numeric_limits<int64_t>::max()));
189  EXPECT_TRUE(IsInt<int64_t>(64, std::numeric_limits<int64_t>::min()));
190  EXPECT_TRUE(IsInt<int64_t>(64, std::numeric_limits<int64_t>::max()));
191}
192
193static_assert(!IsInt<1, int32_t>(-2), "TestIsInt32#1");
194static_assert(IsInt<1, int32_t>(-1), "TestIsInt32#2");
195static_assert(IsInt<1, int32_t>(0), "TestIsInt32#3");
196static_assert(!IsInt<1, int32_t>(1), "TestIsInt32#4");
197static_assert(!IsInt<4, int32_t>(-9), "TestIsInt32#5");
198static_assert(IsInt<4, int32_t>(-8), "TestIsInt32#6");
199static_assert(IsInt<4, int32_t>(7), "TestIsInt32#7");
200static_assert(!IsInt<4, int32_t>(8), "TestIsInt32#8");
201static_assert(!IsInt<31, int32_t>(std::numeric_limits<int32_t>::min()), "TestIsInt32#9");
202static_assert(!IsInt<31, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsInt32#10");
203static_assert(IsInt<32, int32_t>(std::numeric_limits<int32_t>::min()), "TestIsInt32#11");
204static_assert(IsInt<32, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsInt32#12");
205
206static_assert(!IsInt<1, int64_t>(-2), "TestIsInt64#1");
207static_assert(IsInt<1, int64_t>(-1), "TestIsInt64#2");
208static_assert(IsInt<1, int64_t>(0), "TestIsInt64#3");
209static_assert(!IsInt<1, int64_t>(1), "TestIsInt64#4");
210static_assert(!IsInt<4, int64_t>(-9), "TestIsInt64#5");
211static_assert(IsInt<4, int64_t>(-8), "TestIsInt64#6");
212static_assert(IsInt<4, int64_t>(7), "TestIsInt64#7");
213static_assert(!IsInt<4, int64_t>(8), "TestIsInt64#8");
214static_assert(!IsInt<31, int64_t>(std::numeric_limits<int32_t>::min()), "TestIsInt64#9");
215static_assert(!IsInt<31, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsInt64#10");
216static_assert(IsInt<32, int64_t>(std::numeric_limits<int32_t>::min()), "TestIsInt64#11");
217static_assert(IsInt<32, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsInt64#12");
218static_assert(!IsInt<32, int64_t>(kInt32MinMinus1), "TestIsInt64#13");
219static_assert(!IsInt<32, int64_t>(kInt32MaxPlus1), "TestIsInt64#14");
220static_assert(!IsInt<63, int64_t>(std::numeric_limits<int64_t>::min()), "TestIsInt64#15");
221static_assert(!IsInt<63, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsInt64#16");
222static_assert(IsInt<64, int64_t>(std::numeric_limits<int64_t>::min()), "TestIsInt64#17");
223static_assert(IsInt<64, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsInt64#18");
224
225static_assert(!IsUint<1, int32_t>(-1), "TestIsUint32#1");
226static_assert(IsUint<1, int32_t>(0), "TestIsUint32#2");
227static_assert(IsUint<1, int32_t>(1), "TestIsUint32#3");
228static_assert(!IsUint<1, int32_t>(2), "TestIsUint32#4");
229static_assert(!IsUint<4, int32_t>(-1), "TestIsUint32#5");
230static_assert(IsUint<4, int32_t>(0), "TestIsUint32#6");
231static_assert(IsUint<4, int32_t>(15), "TestIsUint32#7");
232static_assert(!IsUint<4, int32_t>(16), "TestIsUint32#8");
233static_assert(!IsUint<30, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsUint32#9");
234static_assert(IsUint<31, int32_t>(std::numeric_limits<int32_t>::max()), "TestIsUint32#10");
235static_assert(!IsUint<32, int32_t>(-1), "TestIsUint32#11");
236static_assert(IsUint<32, int32_t>(0), "TestIsUint32#11");
237static_assert(IsUint<32, uint32_t>(static_cast<uint32_t>(-1)), "TestIsUint32#12");
238
239static_assert(!IsUint<1, int64_t>(-1), "TestIsUint64#1");
240static_assert(IsUint<1, int64_t>(0), "TestIsUint64#2");
241static_assert(IsUint<1, int64_t>(1), "TestIsUint64#3");
242static_assert(!IsUint<1, int64_t>(2), "TestIsUint64#4");
243static_assert(!IsUint<4, int64_t>(-1), "TestIsUint64#5");
244static_assert(IsUint<4, int64_t>(0), "TestIsUint64#6");
245static_assert(IsUint<4, int64_t>(15), "TestIsUint64#7");
246static_assert(!IsUint<4, int64_t>(16), "TestIsUint64#8");
247static_assert(!IsUint<30, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsUint64#9");
248static_assert(IsUint<31, int64_t>(std::numeric_limits<int32_t>::max()), "TestIsUint64#10");
249static_assert(!IsUint<62, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsUint64#11");
250static_assert(IsUint<63, int64_t>(std::numeric_limits<int64_t>::max()), "TestIsUint64#12");
251static_assert(!IsUint<64, int64_t>(-1), "TestIsUint64#13");
252static_assert(IsUint<64, int64_t>(0), "TestIsUint64#14");
253static_assert(IsUint<64, uint64_t>(static_cast<uint32_t>(-1)), "TestIsUint64#15");
254
255static_assert(!IsAbsoluteUint<1, int32_t>(-2), "TestIsAbsoluteUint32#1");
256static_assert(IsAbsoluteUint<1, int32_t>(-1), "TestIsAbsoluteUint32#2");
257static_assert(IsAbsoluteUint<1, int32_t>(0), "TestIsAbsoluteUint32#3");
258static_assert(IsAbsoluteUint<1, int32_t>(1), "TestIsAbsoluteUint32#4");
259static_assert(!IsAbsoluteUint<1, int32_t>(2), "TestIsAbsoluteUint32#5");
260static_assert(!IsAbsoluteUint<4, int32_t>(-16), "TestIsAbsoluteUint32#6");
261static_assert(IsAbsoluteUint<4, int32_t>(-15), "TestIsAbsoluteUint32#7");
262static_assert(IsAbsoluteUint<4, int32_t>(0), "TestIsAbsoluteUint32#8");
263static_assert(IsAbsoluteUint<4, int32_t>(15), "TestIsAbsoluteUint32#9");
264static_assert(!IsAbsoluteUint<4, int32_t>(16), "TestIsAbsoluteUint32#10");
265static_assert(!IsAbsoluteUint<30, int32_t>(std::numeric_limits<int32_t>::max()),
266              "TestIsAbsoluteUint32#11");
267static_assert(IsAbsoluteUint<31, int32_t>(std::numeric_limits<int32_t>::max()),
268              "TestIsAbsoluteUint32#12");
269static_assert(!IsAbsoluteUint<31, int32_t>(std::numeric_limits<int32_t>::min()),
270              "TestIsAbsoluteUint32#13");
271static_assert(IsAbsoluteUint<31, int32_t>(std::numeric_limits<int32_t>::min() + 1),
272              "TestIsAbsoluteUint32#14");
273static_assert(IsAbsoluteUint<32, int32_t>(std::numeric_limits<int32_t>::max()),
274              "TestIsAbsoluteUint32#15");
275static_assert(IsAbsoluteUint<32, int32_t>(std::numeric_limits<int32_t>::min()),
276              "TestIsAbsoluteUint32#16");
277static_assert(IsAbsoluteUint<32, int32_t>(0), "TestIsAbsoluteUint32#17");
278
279static_assert(!IsAbsoluteUint<1, int64_t>(-2), "TestIsAbsoluteUint64#1");
280static_assert(IsAbsoluteUint<1, int64_t>(-1), "TestIsAbsoluteUint64#2");
281static_assert(IsAbsoluteUint<1, int64_t>(0), "TestIsAbsoluteUint64#3");
282static_assert(IsAbsoluteUint<1, int64_t>(1), "TestIsAbsoluteUint64#4");
283static_assert(!IsAbsoluteUint<1, int64_t>(2), "TestIsAbsoluteUint64#5");
284static_assert(!IsAbsoluteUint<4, int64_t>(-16), "TestIsAbsoluteUint64#6");
285static_assert(IsAbsoluteUint<4, int64_t>(-15), "TestIsAbsoluteUint64#7");
286static_assert(IsAbsoluteUint<4, int64_t>(0), "TestIsAbsoluteUint64#8");
287static_assert(IsAbsoluteUint<4, int64_t>(15), "TestIsAbsoluteUint64#9");
288static_assert(!IsAbsoluteUint<4, int64_t>(16), "TestIsAbsoluteUint64#10");
289static_assert(!IsAbsoluteUint<30, int64_t>(std::numeric_limits<int32_t>::max()),
290              "TestIsAbsoluteUint64#11");
291static_assert(IsAbsoluteUint<31, int64_t>(std::numeric_limits<int32_t>::max()),
292              "TestIsAbsoluteUint64#12");
293static_assert(!IsAbsoluteUint<31, int64_t>(std::numeric_limits<int32_t>::min()),
294              "TestIsAbsoluteUint64#13");
295static_assert(IsAbsoluteUint<31, int64_t>(std::numeric_limits<int32_t>::min() + 1),
296              "TestIsAbsoluteUint64#14");
297static_assert(IsAbsoluteUint<32, int64_t>(std::numeric_limits<int32_t>::max()),
298              "TestIsAbsoluteUint64#15");
299static_assert(IsAbsoluteUint<32, int64_t>(std::numeric_limits<int32_t>::min()),
300              "TestIsAbsoluteUint64#16");
301static_assert(!IsAbsoluteUint<62, int64_t>(std::numeric_limits<int64_t>::max()),
302              "TestIsAbsoluteUint64#17");
303static_assert(IsAbsoluteUint<63, int64_t>(std::numeric_limits<int64_t>::max()),
304              "TestIsAbsoluteUint64#18");
305static_assert(!IsAbsoluteUint<63, int64_t>(std::numeric_limits<int64_t>::min()),
306              "TestIsAbsoluteUint64#19");
307static_assert(IsAbsoluteUint<63, int64_t>(std::numeric_limits<int64_t>::min() + 1),
308              "TestIsAbsoluteUint64#20");
309static_assert(IsAbsoluteUint<64, int64_t>(std::numeric_limits<int64_t>::max()),
310              "TestIsAbsoluteUint64#21");
311static_assert(IsAbsoluteUint<64, int64_t>(std::numeric_limits<int64_t>::min()),
312              "TestIsAbsoluteUint64#22");
313static_assert(!IsAbsoluteUint<32, int64_t>(-kUint32MaxPlus1), "TestIsAbsoluteUint64#23");
314static_assert(IsAbsoluteUint<32, int64_t>(-kUint32MaxPlus1 + 1), "TestIsAbsoluteUint64#24");
315static_assert(IsAbsoluteUint<32, int64_t>(0), "TestIsAbsoluteUint64#25");
316static_assert(IsAbsoluteUint<64, int64_t>(0), "TestIsAbsoluteUint64#26");
317static_assert(IsAbsoluteUint<32, int64_t>(std::numeric_limits<uint32_t>::max()),
318              "TestIsAbsoluteUint64#27");
319static_assert(!IsAbsoluteUint<32, int64_t>(kUint32MaxPlus1), "TestIsAbsoluteUint64#28");
320
321template <typename Container>
322void CheckElements(const std::initializer_list<uint32_t>& expected, const Container& elements) {
323  auto expected_it = expected.begin();
324  auto element_it = elements.begin();
325  size_t idx = 0u;
326  while (expected_it != expected.end() && element_it != elements.end()) {
327    EXPECT_EQ(*expected_it, *element_it) << idx;
328    ++idx;
329    ++expected_it;
330    ++element_it;
331  }
332  ASSERT_TRUE(expected_it == expected.end() && element_it == elements.end())
333      << std::boolalpha << (expected_it == expected.end()) << " " << (element_it == elements.end());
334}
335
336TEST(BitUtilsTest, TestLowToHighBits32) {
337  CheckElements({}, LowToHighBits<uint32_t>(0u));
338  CheckElements({0}, LowToHighBits<uint32_t>(1u));
339  CheckElements({15}, LowToHighBits<uint32_t>(0x8000u));
340  CheckElements({31}, LowToHighBits<uint32_t>(0x80000000u));
341  CheckElements({0, 31}, LowToHighBits<uint32_t>(0x80000001u));
342  CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 31}, LowToHighBits<uint32_t>(0x800000ffu));
343  CheckElements({0, 8, 16, 24, 31}, LowToHighBits<uint32_t>(0x81010101u));
344  CheckElements({16, 17, 30, 31}, LowToHighBits<uint32_t>(0xc0030000u));
345  CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
346                 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31},
347                LowToHighBits<uint32_t>(0xffffffffu));
348}
349
350TEST(BitUtilsTest, TestLowToHighBits64) {
351  CheckElements({}, LowToHighBits<uint64_t>(UINT64_C(0)));
352  CheckElements({0}, LowToHighBits<uint64_t>(UINT64_C(1)));
353  CheckElements({32}, LowToHighBits<uint64_t>(UINT64_C(0x100000000)));
354  CheckElements({63}, LowToHighBits<uint64_t>(UINT64_C(0x8000000000000000)));
355  CheckElements({0, 63}, LowToHighBits<uint64_t>(UINT64_C(0x8000000000000001)));
356  CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 63},
357                LowToHighBits<uint64_t>(UINT64_C(0x80000000000000ff)));
358  CheckElements({0, 8, 16, 24, 32, 40, 48, 56, 63},
359                LowToHighBits<uint64_t>(UINT64_C(0x8101010101010101)));
360  CheckElements({16, 17, 62, 63}, LowToHighBits<uint64_t>(UINT64_C(0xc000000000030000)));
361  CheckElements({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
362                 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
363                 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
364                 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63},
365                LowToHighBits<uint64_t>(UINT64_C(0xffffffffffffffff)));
366}
367
368TEST(BitUtilsTest, TestHighToLowBits32) {
369  CheckElements({}, HighToLowBits<uint32_t>(0u));
370  CheckElements({0}, HighToLowBits<uint32_t>(1u));
371  CheckElements({15}, HighToLowBits<uint32_t>(0x8000u));
372  CheckElements({31}, HighToLowBits<uint32_t>(0x80000000u));
373  CheckElements({31, 0}, HighToLowBits<uint32_t>(0x80000001u));
374  CheckElements({31, 7, 6, 5, 4, 3, 2, 1, 0}, HighToLowBits<uint32_t>(0x800000ffu));
375  CheckElements({31, 24, 16, 8, 0}, HighToLowBits<uint32_t>(0x81010101u));
376  CheckElements({31, 30, 17, 16}, HighToLowBits<uint32_t>(0xc0030000u));
377  CheckElements({31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16,
378                 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
379                HighToLowBits<uint32_t>(0xffffffffu));
380}
381
382TEST(BitUtilsTest, TestHighToLowBits64) {
383  CheckElements({}, HighToLowBits<uint64_t>(UINT64_C(0)));
384  CheckElements({0}, HighToLowBits<uint64_t>(UINT64_C(1)));
385  CheckElements({32}, HighToLowBits<uint64_t>(UINT64_C(0x100000000)));
386  CheckElements({63}, HighToLowBits<uint64_t>(UINT64_C(0x8000000000000000)));
387  CheckElements({63, 0}, HighToLowBits<uint64_t>(UINT64_C(0x8000000000000001)));
388  CheckElements({63, 7, 6, 5, 4, 3, 2, 1, 0},
389                HighToLowBits<uint64_t>(UINT64_C(0x80000000000000ff)));
390  CheckElements({63, 56, 48, 40, 32, 24, 16, 8, 0},
391                HighToLowBits<uint64_t>(UINT64_C(0x8101010101010101)));
392  CheckElements({63, 62, 17, 16}, HighToLowBits<uint64_t>(UINT64_C(0xc000000000030000)));
393  CheckElements({63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48,
394                 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32,
395                 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16,
396                 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0},
397                HighToLowBits<uint64_t>(UINT64_C(0xffffffffffffffff)));
398}
399
400}  // namespace art
401