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