Line data Source code
1 : // Copyright 2014 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include <limits>
6 :
7 : #include "src/base/bits.h"
8 : #include "src/base/macros.h"
9 : #include "testing/gtest-support.h"
10 :
11 : #ifdef DEBUG
12 : #define DISABLE_IN_RELEASE(Name) Name
13 : #else
14 : #define DISABLE_IN_RELEASE(Name) DISABLED_##Name
15 : #endif
16 :
17 : namespace v8 {
18 : namespace base {
19 : namespace bits {
20 :
21 15128 : TEST(Bits, CountPopulation16) {
22 2 : EXPECT_EQ(0u, CountPopulation(uint16_t{0}));
23 2 : EXPECT_EQ(1u, CountPopulation(uint16_t{1}));
24 2 : EXPECT_EQ(4u, CountPopulation(uint16_t{0x1111}));
25 2 : EXPECT_EQ(8u, CountPopulation(uint16_t{0xF0F0}));
26 2 : EXPECT_EQ(12u, CountPopulation(uint16_t{0xF0FF}));
27 2 : EXPECT_EQ(16u, CountPopulation(uint16_t{0xFFFF}));
28 1 : }
29 :
30 15128 : TEST(Bits, CountPopulation32) {
31 2 : EXPECT_EQ(0u, CountPopulation(uint32_t{0}));
32 2 : EXPECT_EQ(1u, CountPopulation(uint32_t{1}));
33 2 : EXPECT_EQ(8u, CountPopulation(uint32_t{0x11111111}));
34 2 : EXPECT_EQ(16u, CountPopulation(uint32_t{0xF0F0F0F0}));
35 2 : EXPECT_EQ(24u, CountPopulation(uint32_t{0xFFF0F0FF}));
36 2 : EXPECT_EQ(32u, CountPopulation(uint32_t{0xFFFFFFFF}));
37 1 : }
38 :
39 15128 : TEST(Bits, CountPopulation64) {
40 2 : EXPECT_EQ(0u, CountPopulation(uint64_t{0}));
41 2 : EXPECT_EQ(1u, CountPopulation(uint64_t{1}));
42 2 : EXPECT_EQ(2u, CountPopulation(uint64_t{0x8000000000000001}));
43 2 : EXPECT_EQ(8u, CountPopulation(uint64_t{0x11111111}));
44 2 : EXPECT_EQ(16u, CountPopulation(uint64_t{0xF0F0F0F0}));
45 2 : EXPECT_EQ(24u, CountPopulation(uint64_t{0xFFF0F0FF}));
46 2 : EXPECT_EQ(32u, CountPopulation(uint64_t{0xFFFFFFFF}));
47 2 : EXPECT_EQ(16u, CountPopulation(uint64_t{0x1111111111111111}));
48 2 : EXPECT_EQ(32u, CountPopulation(uint64_t{0xF0F0F0F0F0F0F0F0}));
49 2 : EXPECT_EQ(48u, CountPopulation(uint64_t{0xFFF0F0FFFFF0F0FF}));
50 2 : EXPECT_EQ(64u, CountPopulation(uint64_t{0xFFFFFFFFFFFFFFFF}));
51 1 : }
52 :
53 15128 : TEST(Bits, CountLeadingZeros16) {
54 2 : EXPECT_EQ(16u, CountLeadingZeros(uint16_t{0}));
55 2 : EXPECT_EQ(15u, CountLeadingZeros(uint16_t{1}));
56 97 : TRACED_FORRANGE(uint16_t, shift, 0, 15) {
57 48 : EXPECT_EQ(15u - shift,
58 0 : CountLeadingZeros(static_cast<uint16_t>(1 << shift)));
59 16 : }
60 2 : EXPECT_EQ(4u, CountLeadingZeros(uint16_t{0x0F0F}));
61 1 : }
62 :
63 15128 : TEST(Bits, CountLeadingZeros32) {
64 2 : EXPECT_EQ(32u, CountLeadingZeros(uint32_t{0}));
65 2 : EXPECT_EQ(31u, CountLeadingZeros(uint32_t{1}));
66 193 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
67 96 : EXPECT_EQ(31u - shift, CountLeadingZeros(uint32_t{1} << shift));
68 32 : }
69 2 : EXPECT_EQ(4u, CountLeadingZeros(uint32_t{0x0F0F0F0F}));
70 1 : }
71 :
72 15128 : TEST(Bits, CountLeadingZeros64) {
73 2 : EXPECT_EQ(64u, CountLeadingZeros(uint64_t{0}));
74 2 : EXPECT_EQ(63u, CountLeadingZeros(uint64_t{1}));
75 385 : TRACED_FORRANGE(uint32_t, shift, 0, 63) {
76 192 : EXPECT_EQ(63u - shift, CountLeadingZeros(uint64_t{1} << shift));
77 64 : }
78 2 : EXPECT_EQ(36u, CountLeadingZeros(uint64_t{0x0F0F0F0F}));
79 2 : EXPECT_EQ(4u, CountLeadingZeros(uint64_t{0x0F0F0F0F00000000}));
80 1 : }
81 :
82 15128 : TEST(Bits, CountTrailingZeros16) {
83 2 : EXPECT_EQ(16u, CountTrailingZeros(uint16_t{0}));
84 2 : EXPECT_EQ(15u, CountTrailingZeros(uint16_t{0x8000}));
85 113 : TRACED_FORRANGE(uint16_t, shift, 0, 15) {
86 48 : EXPECT_EQ(shift, CountTrailingZeros(static_cast<uint16_t>(1 << shift)));
87 16 : }
88 2 : EXPECT_EQ(4u, CountTrailingZeros(uint16_t{0xF0F0u}));
89 1 : }
90 :
91 15128 : TEST(Bits, CountTrailingZerosu32) {
92 2 : EXPECT_EQ(32u, CountTrailingZeros(uint32_t{0}));
93 2 : EXPECT_EQ(31u, CountTrailingZeros(uint32_t{0x80000000}));
94 225 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
95 96 : EXPECT_EQ(shift, CountTrailingZeros(uint32_t{1} << shift));
96 32 : }
97 2 : EXPECT_EQ(4u, CountTrailingZeros(uint32_t{0xF0F0F0F0u}));
98 1 : }
99 :
100 15128 : TEST(Bits, CountTrailingZerosi32) {
101 2 : EXPECT_EQ(32u, CountTrailingZeros(int32_t{0}));
102 225 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
103 96 : EXPECT_EQ(shift, CountTrailingZeros(int32_t{1} << shift));
104 32 : }
105 2 : EXPECT_EQ(4u, CountTrailingZeros(int32_t{0x70F0F0F0u}));
106 2 : EXPECT_EQ(2u, CountTrailingZeros(int32_t{-4}));
107 2 : EXPECT_EQ(0u, CountTrailingZeros(int32_t{-1}));
108 1 : }
109 :
110 15128 : TEST(Bits, CountTrailingZeros64) {
111 2 : EXPECT_EQ(64u, CountTrailingZeros(uint64_t{0}));
112 2 : EXPECT_EQ(63u, CountTrailingZeros(uint64_t{0x8000000000000000}));
113 449 : TRACED_FORRANGE(uint32_t, shift, 0, 63) {
114 192 : EXPECT_EQ(shift, CountTrailingZeros(uint64_t{1} << shift));
115 64 : }
116 2 : EXPECT_EQ(4u, CountTrailingZeros(uint64_t{0xF0F0F0F0}));
117 2 : EXPECT_EQ(36u, CountTrailingZeros(uint64_t{0xF0F0F0F000000000}));
118 1 : }
119 :
120 :
121 15128 : TEST(Bits, IsPowerOfTwo32) {
122 : EXPECT_FALSE(IsPowerOfTwo(0U));
123 193 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
124 64 : EXPECT_TRUE(IsPowerOfTwo(1U << shift));
125 96 : EXPECT_FALSE(IsPowerOfTwo((1U << shift) + 5U));
126 96 : EXPECT_FALSE(IsPowerOfTwo(~(1U << shift)));
127 32 : }
128 210 : TRACED_FORRANGE(uint32_t, shift, 2, 31) {
129 90 : EXPECT_FALSE(IsPowerOfTwo((1U << shift) - 1U));
130 30 : }
131 : EXPECT_FALSE(IsPowerOfTwo(0xFFFFFFFF));
132 1 : }
133 :
134 :
135 15128 : TEST(Bits, IsPowerOfTwo64) {
136 : EXPECT_FALSE(IsPowerOfTwo(uint64_t{0}));
137 385 : TRACED_FORRANGE(uint32_t, shift, 0, 63) {
138 128 : EXPECT_TRUE(IsPowerOfTwo(uint64_t{1} << shift));
139 192 : EXPECT_FALSE(IsPowerOfTwo((uint64_t{1} << shift) + 5U));
140 192 : EXPECT_FALSE(IsPowerOfTwo(~(uint64_t{1} << shift)));
141 64 : }
142 434 : TRACED_FORRANGE(uint32_t, shift, 2, 63) {
143 186 : EXPECT_FALSE(IsPowerOfTwo((uint64_t{1} << shift) - 1U));
144 62 : }
145 : EXPECT_FALSE(IsPowerOfTwo(uint64_t{0xFFFFFFFFFFFFFFFF}));
146 1 : }
147 :
148 :
149 15128 : TEST(Bits, RoundUpToPowerOfTwo32) {
150 193 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
151 64 : EXPECT_EQ(1u << shift, RoundUpToPowerOfTwo32(1u << shift));
152 32 : }
153 2 : EXPECT_EQ(1u, RoundUpToPowerOfTwo32(0));
154 2 : EXPECT_EQ(1u, RoundUpToPowerOfTwo32(1));
155 2 : EXPECT_EQ(4u, RoundUpToPowerOfTwo32(3));
156 2 : EXPECT_EQ(0x80000000u, RoundUpToPowerOfTwo32(0x7FFFFFFFu));
157 1 : }
158 :
159 :
160 15125 : TEST(BitsDeathTest, DISABLE_IN_RELEASE(RoundUpToPowerOfTwo32)) {
161 0 : ASSERT_DEATH_IF_SUPPORTED({ RoundUpToPowerOfTwo32(0x80000001u); },
162 : ".*heck failed:.* << 31");
163 : }
164 :
165 15128 : TEST(Bits, RoundUpToPowerOfTwo64) {
166 385 : TRACED_FORRANGE(uint64_t, shift, 0, 63) {
167 64 : uint64_t value = uint64_t{1} << shift;
168 128 : EXPECT_EQ(value, RoundUpToPowerOfTwo64(value));
169 64 : }
170 2 : EXPECT_EQ(uint64_t{1}, RoundUpToPowerOfTwo64(0));
171 2 : EXPECT_EQ(uint64_t{1}, RoundUpToPowerOfTwo64(1));
172 2 : EXPECT_EQ(uint64_t{4}, RoundUpToPowerOfTwo64(3));
173 2 : EXPECT_EQ(uint64_t{1} << 63, RoundUpToPowerOfTwo64((uint64_t{1} << 63) - 1));
174 2 : EXPECT_EQ(uint64_t{1} << 63, RoundUpToPowerOfTwo64(uint64_t{1} << 63));
175 1 : }
176 :
177 15125 : TEST(BitsDeathTest, DISABLE_IN_RELEASE(RoundUpToPowerOfTwo64)) {
178 0 : ASSERT_DEATH_IF_SUPPORTED({ RoundUpToPowerOfTwo64((uint64_t{1} << 63) + 1); },
179 : ".*heck failed:.* << 63");
180 : }
181 :
182 :
183 15128 : TEST(Bits, RoundDownToPowerOfTwo32) {
184 193 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
185 96 : EXPECT_EQ(1u << shift, RoundDownToPowerOfTwo32(1u << shift));
186 32 : }
187 2 : EXPECT_EQ(0u, RoundDownToPowerOfTwo32(0));
188 2 : EXPECT_EQ(4u, RoundDownToPowerOfTwo32(5));
189 2 : EXPECT_EQ(0x80000000u, RoundDownToPowerOfTwo32(0x80000001u));
190 1 : }
191 :
192 :
193 15128 : TEST(Bits, RotateRight32) {
194 193 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
195 64 : EXPECT_EQ(0u, RotateRight32(0u, shift));
196 32 : }
197 2 : EXPECT_EQ(1u, RotateRight32(1, 0));
198 2 : EXPECT_EQ(1u, RotateRight32(2, 1));
199 2 : EXPECT_EQ(0x80000000u, RotateRight32(1, 1));
200 1 : }
201 :
202 :
203 15128 : TEST(Bits, RotateRight64) {
204 385 : TRACED_FORRANGE(uint64_t, shift, 0, 63) {
205 128 : EXPECT_EQ(0u, RotateRight64(0u, shift));
206 64 : }
207 2 : EXPECT_EQ(1u, RotateRight64(1, 0));
208 2 : EXPECT_EQ(1u, RotateRight64(2, 1));
209 2 : EXPECT_EQ(uint64_t{0x8000000000000000}, RotateRight64(1, 1));
210 1 : }
211 :
212 :
213 15128 : TEST(Bits, SignedAddOverflow32) {
214 1 : int32_t val = 0;
215 : EXPECT_FALSE(SignedAddOverflow32(0, 0, &val));
216 2 : EXPECT_EQ(0, val);
217 : EXPECT_TRUE(
218 : SignedAddOverflow32(std::numeric_limits<int32_t>::max(), 1, &val));
219 2 : EXPECT_EQ(std::numeric_limits<int32_t>::min(), val);
220 : EXPECT_TRUE(
221 : SignedAddOverflow32(std::numeric_limits<int32_t>::min(), -1, &val));
222 2 : EXPECT_EQ(std::numeric_limits<int32_t>::max(), val);
223 : EXPECT_TRUE(SignedAddOverflow32(std::numeric_limits<int32_t>::max(),
224 : std::numeric_limits<int32_t>::max(), &val));
225 2 : EXPECT_EQ(-2, val);
226 301 : TRACED_FORRANGE(int32_t, i, 1, 50) {
227 8925 : TRACED_FORRANGE(int32_t, j, 1, i) {
228 2550 : EXPECT_FALSE(SignedAddOverflow32(i, j, &val));
229 2550 : EXPECT_EQ(i + j, val);
230 1275 : }
231 50 : }
232 1 : }
233 :
234 :
235 15128 : TEST(Bits, SignedSubOverflow32) {
236 1 : int32_t val = 0;
237 : EXPECT_FALSE(SignedSubOverflow32(0, 0, &val));
238 2 : EXPECT_EQ(0, val);
239 : EXPECT_TRUE(
240 : SignedSubOverflow32(std::numeric_limits<int32_t>::min(), 1, &val));
241 2 : EXPECT_EQ(std::numeric_limits<int32_t>::max(), val);
242 : EXPECT_TRUE(
243 : SignedSubOverflow32(std::numeric_limits<int32_t>::max(), -1, &val));
244 2 : EXPECT_EQ(std::numeric_limits<int32_t>::min(), val);
245 301 : TRACED_FORRANGE(int32_t, i, 1, 50) {
246 8925 : TRACED_FORRANGE(int32_t, j, 1, i) {
247 2550 : EXPECT_FALSE(SignedSubOverflow32(i, j, &val));
248 2550 : EXPECT_EQ(i - j, val);
249 1275 : }
250 50 : }
251 1 : }
252 :
253 :
254 15128 : TEST(Bits, SignedMulHigh32) {
255 2 : EXPECT_EQ(0, SignedMulHigh32(0, 0));
256 301 : TRACED_FORRANGE(int32_t, i, 1, 50) {
257 7650 : TRACED_FORRANGE(int32_t, j, 1, i) { EXPECT_EQ(0, SignedMulHigh32(i, j)); }
258 50 : }
259 2 : EXPECT_EQ(-1073741824, SignedMulHigh32(std::numeric_limits<int32_t>::max(),
260 0 : std::numeric_limits<int32_t>::min()));
261 2 : EXPECT_EQ(-1073741824, SignedMulHigh32(std::numeric_limits<int32_t>::min(),
262 0 : std::numeric_limits<int32_t>::max()));
263 2 : EXPECT_EQ(1, SignedMulHigh32(1024 * 1024 * 1024, 4));
264 2 : EXPECT_EQ(2, SignedMulHigh32(8 * 1024, 1024 * 1024));
265 1 : }
266 :
267 :
268 15128 : TEST(Bits, SignedMulHighAndAdd32) {
269 351 : TRACED_FORRANGE(int32_t, i, 1, 50) {
270 100 : EXPECT_EQ(i, SignedMulHighAndAdd32(0, 0, i));
271 7700 : TRACED_FORRANGE(int32_t, j, 1, i) {
272 2550 : EXPECT_EQ(i, SignedMulHighAndAdd32(j, j, i));
273 1275 : }
274 100 : EXPECT_EQ(i + 1, SignedMulHighAndAdd32(1024 * 1024 * 1024, 4, i));
275 50 : }
276 1 : }
277 :
278 :
279 15128 : TEST(Bits, SignedDiv32) {
280 2 : EXPECT_EQ(std::numeric_limits<int32_t>::min(),
281 0 : SignedDiv32(std::numeric_limits<int32_t>::min(), -1));
282 2 : EXPECT_EQ(std::numeric_limits<int32_t>::max(),
283 0 : SignedDiv32(std::numeric_limits<int32_t>::max(), 1));
284 307 : TRACED_FORRANGE(int32_t, i, 0, 50) {
285 102 : EXPECT_EQ(0, SignedDiv32(i, 0));
286 7701 : TRACED_FORRANGE(int32_t, j, 1, i) {
287 2550 : EXPECT_EQ(1, SignedDiv32(j, j));
288 2550 : EXPECT_EQ(i / j, SignedDiv32(i, j));
289 2550 : EXPECT_EQ(-i / j, SignedDiv32(i, -j));
290 1275 : }
291 51 : }
292 1 : }
293 :
294 :
295 15128 : TEST(Bits, SignedMod32) {
296 2 : EXPECT_EQ(0, SignedMod32(std::numeric_limits<int32_t>::min(), -1));
297 2 : EXPECT_EQ(0, SignedMod32(std::numeric_limits<int32_t>::max(), 1));
298 307 : TRACED_FORRANGE(int32_t, i, 0, 50) {
299 102 : EXPECT_EQ(0, SignedMod32(i, 0));
300 7701 : TRACED_FORRANGE(int32_t, j, 1, i) {
301 2550 : EXPECT_EQ(0, SignedMod32(j, j));
302 2550 : EXPECT_EQ(i % j, SignedMod32(i, j));
303 2550 : EXPECT_EQ(i % j, SignedMod32(i, -j));
304 1275 : }
305 51 : }
306 1 : }
307 :
308 :
309 15128 : TEST(Bits, UnsignedAddOverflow32) {
310 1 : uint32_t val = 0;
311 : EXPECT_FALSE(UnsignedAddOverflow32(0, 0, &val));
312 2 : EXPECT_EQ(0u, val);
313 : EXPECT_TRUE(
314 : UnsignedAddOverflow32(std::numeric_limits<uint32_t>::max(), 1u, &val));
315 2 : EXPECT_EQ(std::numeric_limits<uint32_t>::min(), val);
316 : EXPECT_TRUE(UnsignedAddOverflow32(std::numeric_limits<uint32_t>::max(),
317 : std::numeric_limits<uint32_t>::max(),
318 : &val));
319 301 : TRACED_FORRANGE(uint32_t, i, 1, 50) {
320 8925 : TRACED_FORRANGE(uint32_t, j, 1, i) {
321 2550 : EXPECT_FALSE(UnsignedAddOverflow32(i, j, &val));
322 2550 : EXPECT_EQ(i + j, val);
323 1275 : }
324 50 : }
325 1 : }
326 :
327 :
328 15128 : TEST(Bits, UnsignedDiv32) {
329 307 : TRACED_FORRANGE(uint32_t, i, 0, 50) {
330 102 : EXPECT_EQ(0u, UnsignedDiv32(i, 0));
331 23001 : TRACED_FORRANGE(uint32_t, j, i + 1, 100) {
332 7650 : EXPECT_EQ(1u, UnsignedDiv32(j, j));
333 7650 : EXPECT_EQ(i / j, UnsignedDiv32(i, j));
334 3825 : }
335 51 : }
336 1 : }
337 :
338 :
339 15128 : TEST(Bits, UnsignedMod32) {
340 307 : TRACED_FORRANGE(uint32_t, i, 0, 50) {
341 102 : EXPECT_EQ(0u, UnsignedMod32(i, 0));
342 23001 : TRACED_FORRANGE(uint32_t, j, i + 1, 100) {
343 7650 : EXPECT_EQ(0u, UnsignedMod32(j, j));
344 7650 : EXPECT_EQ(i % j, UnsignedMod32(i, j));
345 3825 : }
346 51 : }
347 1 : }
348 :
349 : } // namespace bits
350 : } // namespace base
351 9075 : } // namespace v8
|
