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 13158 : TEST(Bits, CountPopulation32) {
22 2 : EXPECT_EQ(0u, CountPopulation(uint32_t{0}));
23 2 : EXPECT_EQ(1u, CountPopulation(uint32_t{1}));
24 2 : EXPECT_EQ(8u, CountPopulation(uint32_t{0x11111111}));
25 2 : EXPECT_EQ(16u, CountPopulation(uint32_t{0xf0f0f0f0}));
26 2 : EXPECT_EQ(24u, CountPopulation(uint32_t{0xfff0f0ff}));
27 2 : EXPECT_EQ(32u, CountPopulation(uint32_t{0xffffffff}));
28 1 : }
29 :
30 :
31 13158 : TEST(Bits, CountPopulation64) {
32 2 : EXPECT_EQ(0u, CountPopulation(uint64_t{0}));
33 2 : EXPECT_EQ(1u, CountPopulation(uint64_t{1}));
34 2 : EXPECT_EQ(2u, CountPopulation(uint64_t{0x8000000000000001}));
35 2 : EXPECT_EQ(8u, CountPopulation(uint64_t{0x11111111}));
36 2 : EXPECT_EQ(16u, CountPopulation(uint64_t{0xf0f0f0f0}));
37 2 : EXPECT_EQ(24u, CountPopulation(uint64_t{0xfff0f0ff}));
38 2 : EXPECT_EQ(32u, CountPopulation(uint64_t{0xffffffff}));
39 2 : EXPECT_EQ(16u, CountPopulation(uint64_t{0x1111111111111111}));
40 2 : EXPECT_EQ(32u, CountPopulation(uint64_t{0xf0f0f0f0f0f0f0f0}));
41 2 : EXPECT_EQ(48u, CountPopulation(uint64_t{0xfff0f0fffff0f0ff}));
42 2 : EXPECT_EQ(64u, CountPopulation(uint64_t{0xffffffffffffffff}));
43 1 : }
44 :
45 :
46 13158 : TEST(Bits, CountLeadingZeros32) {
47 2 : EXPECT_EQ(32u, CountLeadingZeros32(0));
48 2 : EXPECT_EQ(31u, CountLeadingZeros32(1));
49 257 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
50 96 : EXPECT_EQ(31u - shift, CountLeadingZeros32(1u << shift));
51 32 : }
52 2 : EXPECT_EQ(4u, CountLeadingZeros32(0x0f0f0f0f));
53 1 : }
54 :
55 :
56 13158 : TEST(Bits, CountLeadingZeros64) {
57 2 : EXPECT_EQ(64u, CountLeadingZeros64(0));
58 2 : EXPECT_EQ(63u, CountLeadingZeros64(1));
59 513 : TRACED_FORRANGE(uint32_t, shift, 0, 63) {
60 192 : EXPECT_EQ(63u - shift, CountLeadingZeros64(V8_UINT64_C(1) << shift));
61 64 : }
62 2 : EXPECT_EQ(36u, CountLeadingZeros64(0x0f0f0f0f));
63 2 : EXPECT_EQ(4u, CountLeadingZeros64(0x0f0f0f0f00000000));
64 1 : }
65 :
66 :
67 13158 : TEST(Bits, CountTrailingZeros32) {
68 2 : EXPECT_EQ(32u, CountTrailingZeros32(0));
69 2 : EXPECT_EQ(31u, CountTrailingZeros32(0x80000000));
70 289 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
71 96 : EXPECT_EQ(shift, CountTrailingZeros32(1u << shift));
72 32 : }
73 2 : EXPECT_EQ(4u, CountTrailingZeros32(0xf0f0f0f0));
74 1 : }
75 :
76 :
77 13158 : TEST(Bits, CountTrailingZeros64) {
78 2 : EXPECT_EQ(64u, CountTrailingZeros64(0));
79 2 : EXPECT_EQ(63u, CountTrailingZeros64(0x8000000000000000));
80 577 : TRACED_FORRANGE(uint32_t, shift, 0, 63) {
81 192 : EXPECT_EQ(shift, CountTrailingZeros64(V8_UINT64_C(1) << shift));
82 64 : }
83 2 : EXPECT_EQ(4u, CountTrailingZeros64(0xf0f0f0f0));
84 2 : EXPECT_EQ(36u, CountTrailingZeros64(0xf0f0f0f000000000));
85 1 : }
86 :
87 :
88 13158 : TEST(Bits, IsPowerOfTwo32) {
89 : EXPECT_FALSE(IsPowerOfTwo(0U));
90 257 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
91 64 : EXPECT_TRUE(IsPowerOfTwo(1U << shift));
92 96 : EXPECT_FALSE(IsPowerOfTwo((1U << shift) + 5U));
93 96 : EXPECT_FALSE(IsPowerOfTwo(~(1U << shift)));
94 32 : }
95 270 : TRACED_FORRANGE(uint32_t, shift, 2, 31) {
96 90 : EXPECT_FALSE(IsPowerOfTwo((1U << shift) - 1U));
97 30 : }
98 : EXPECT_FALSE(IsPowerOfTwo(0xffffffff));
99 1 : }
100 :
101 :
102 13158 : TEST(Bits, IsPowerOfTwo64) {
103 : EXPECT_FALSE(IsPowerOfTwo(V8_UINT64_C(0)));
104 513 : TRACED_FORRANGE(uint32_t, shift, 0, 63) {
105 128 : EXPECT_TRUE(IsPowerOfTwo(V8_UINT64_C(1) << shift));
106 192 : EXPECT_FALSE(IsPowerOfTwo((V8_UINT64_C(1) << shift) + 5U));
107 192 : EXPECT_FALSE(IsPowerOfTwo(~(V8_UINT64_C(1) << shift)));
108 64 : }
109 558 : TRACED_FORRANGE(uint32_t, shift, 2, 63) {
110 186 : EXPECT_FALSE(IsPowerOfTwo((V8_UINT64_C(1) << shift) - 1U));
111 62 : }
112 : EXPECT_FALSE(IsPowerOfTwo(V8_UINT64_C(0xffffffffffffffff)));
113 1 : }
114 :
115 :
116 13158 : TEST(Bits, RoundUpToPowerOfTwo32) {
117 257 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
118 64 : EXPECT_EQ(1u << shift, RoundUpToPowerOfTwo32(1u << shift));
119 32 : }
120 2 : EXPECT_EQ(1u, RoundUpToPowerOfTwo32(0));
121 2 : EXPECT_EQ(1u, RoundUpToPowerOfTwo32(1));
122 2 : EXPECT_EQ(4u, RoundUpToPowerOfTwo32(3));
123 2 : EXPECT_EQ(0x80000000u, RoundUpToPowerOfTwo32(0x7fffffffu));
124 1 : }
125 :
126 :
127 13155 : TEST(BitsDeathTest, DISABLE_IN_RELEASE(RoundUpToPowerOfTwo32)) {
128 0 : ASSERT_DEATH_IF_SUPPORTED({ RoundUpToPowerOfTwo32(0x80000001u); },
129 : ".*heck failed:.* << 31");
130 : }
131 :
132 13158 : TEST(Bits, RoundUpToPowerOfTwo64) {
133 513 : TRACED_FORRANGE(uint64_t, shift, 0, 63) {
134 64 : uint64_t value = uint64_t{1} << shift;
135 128 : EXPECT_EQ(value, RoundUpToPowerOfTwo64(value));
136 64 : }
137 2 : EXPECT_EQ(uint64_t{1}, RoundUpToPowerOfTwo64(0));
138 2 : EXPECT_EQ(uint64_t{1}, RoundUpToPowerOfTwo64(1));
139 2 : EXPECT_EQ(uint64_t{4}, RoundUpToPowerOfTwo64(3));
140 2 : EXPECT_EQ(uint64_t{1} << 63, RoundUpToPowerOfTwo64((uint64_t{1} << 63) - 1));
141 2 : EXPECT_EQ(uint64_t{1} << 63, RoundUpToPowerOfTwo64(uint64_t{1} << 63));
142 1 : }
143 :
144 13155 : TEST(BitsDeathTest, DISABLE_IN_RELEASE(RoundUpToPowerOfTwo64)) {
145 0 : ASSERT_DEATH_IF_SUPPORTED({ RoundUpToPowerOfTwo64((uint64_t{1} << 63) + 1); },
146 : ".*heck failed:.* << 63");
147 : }
148 :
149 :
150 13158 : TEST(Bits, RoundDownToPowerOfTwo32) {
151 257 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
152 96 : EXPECT_EQ(1u << shift, RoundDownToPowerOfTwo32(1u << shift));
153 32 : }
154 2 : EXPECT_EQ(0u, RoundDownToPowerOfTwo32(0));
155 2 : EXPECT_EQ(4u, RoundDownToPowerOfTwo32(5));
156 2 : EXPECT_EQ(0x80000000u, RoundDownToPowerOfTwo32(0x80000001u));
157 1 : }
158 :
159 :
160 13158 : TEST(Bits, RotateRight32) {
161 257 : TRACED_FORRANGE(uint32_t, shift, 0, 31) {
162 64 : EXPECT_EQ(0u, RotateRight32(0u, shift));
163 32 : }
164 2 : EXPECT_EQ(1u, RotateRight32(1, 0));
165 2 : EXPECT_EQ(1u, RotateRight32(2, 1));
166 2 : EXPECT_EQ(0x80000000u, RotateRight32(1, 1));
167 1 : }
168 :
169 :
170 13158 : TEST(Bits, RotateRight64) {
171 513 : TRACED_FORRANGE(uint64_t, shift, 0, 63) {
172 128 : EXPECT_EQ(0u, RotateRight64(0u, shift));
173 64 : }
174 2 : EXPECT_EQ(1u, RotateRight64(1, 0));
175 2 : EXPECT_EQ(1u, RotateRight64(2, 1));
176 2 : EXPECT_EQ(V8_UINT64_C(0x8000000000000000), RotateRight64(1, 1));
177 1 : }
178 :
179 :
180 13158 : TEST(Bits, SignedAddOverflow32) {
181 1 : int32_t val = 0;
182 : EXPECT_FALSE(SignedAddOverflow32(0, 0, &val));
183 2 : EXPECT_EQ(0, val);
184 : EXPECT_TRUE(
185 : SignedAddOverflow32(std::numeric_limits<int32_t>::max(), 1, &val));
186 2 : EXPECT_EQ(std::numeric_limits<int32_t>::min(), val);
187 : EXPECT_TRUE(
188 : SignedAddOverflow32(std::numeric_limits<int32_t>::min(), -1, &val));
189 2 : EXPECT_EQ(std::numeric_limits<int32_t>::max(), val);
190 : EXPECT_TRUE(SignedAddOverflow32(std::numeric_limits<int32_t>::max(),
191 : std::numeric_limits<int32_t>::max(), &val));
192 2 : EXPECT_EQ(-2, val);
193 401 : TRACED_FORRANGE(int32_t, i, 1, 50) {
194 11475 : TRACED_FORRANGE(int32_t, j, 1, i) {
195 2550 : EXPECT_FALSE(SignedAddOverflow32(i, j, &val));
196 2550 : EXPECT_EQ(i + j, val);
197 1275 : }
198 50 : }
199 1 : }
200 :
201 :
202 13158 : TEST(Bits, SignedSubOverflow32) {
203 1 : int32_t val = 0;
204 : EXPECT_FALSE(SignedSubOverflow32(0, 0, &val));
205 2 : EXPECT_EQ(0, val);
206 : EXPECT_TRUE(
207 : SignedSubOverflow32(std::numeric_limits<int32_t>::min(), 1, &val));
208 2 : EXPECT_EQ(std::numeric_limits<int32_t>::max(), val);
209 : EXPECT_TRUE(
210 : SignedSubOverflow32(std::numeric_limits<int32_t>::max(), -1, &val));
211 2 : EXPECT_EQ(std::numeric_limits<int32_t>::min(), val);
212 401 : TRACED_FORRANGE(int32_t, i, 1, 50) {
213 11475 : TRACED_FORRANGE(int32_t, j, 1, i) {
214 2550 : EXPECT_FALSE(SignedSubOverflow32(i, j, &val));
215 2550 : EXPECT_EQ(i - j, val);
216 1275 : }
217 50 : }
218 1 : }
219 :
220 :
221 13158 : TEST(Bits, SignedMulHigh32) {
222 2 : EXPECT_EQ(0, SignedMulHigh32(0, 0));
223 401 : TRACED_FORRANGE(int32_t, i, 1, 50) {
224 10200 : TRACED_FORRANGE(int32_t, j, 1, i) { EXPECT_EQ(0, SignedMulHigh32(i, j)); }
225 50 : }
226 2 : EXPECT_EQ(-1073741824, SignedMulHigh32(std::numeric_limits<int32_t>::max(),
227 0 : std::numeric_limits<int32_t>::min()));
228 2 : EXPECT_EQ(-1073741824, SignedMulHigh32(std::numeric_limits<int32_t>::min(),
229 0 : std::numeric_limits<int32_t>::max()));
230 2 : EXPECT_EQ(1, SignedMulHigh32(1024 * 1024 * 1024, 4));
231 2 : EXPECT_EQ(2, SignedMulHigh32(8 * 1024, 1024 * 1024));
232 1 : }
233 :
234 :
235 13158 : TEST(Bits, SignedMulHighAndAdd32) {
236 451 : TRACED_FORRANGE(int32_t, i, 1, 50) {
237 100 : EXPECT_EQ(i, SignedMulHighAndAdd32(0, 0, i));
238 10250 : TRACED_FORRANGE(int32_t, j, 1, i) {
239 2550 : EXPECT_EQ(i, SignedMulHighAndAdd32(j, j, i));
240 1275 : }
241 100 : EXPECT_EQ(i + 1, SignedMulHighAndAdd32(1024 * 1024 * 1024, 4, i));
242 50 : }
243 1 : }
244 :
245 :
246 13158 : TEST(Bits, SignedDiv32) {
247 2 : EXPECT_EQ(std::numeric_limits<int32_t>::min(),
248 0 : SignedDiv32(std::numeric_limits<int32_t>::min(), -1));
249 2 : EXPECT_EQ(std::numeric_limits<int32_t>::max(),
250 0 : SignedDiv32(std::numeric_limits<int32_t>::max(), 1));
251 409 : TRACED_FORRANGE(int32_t, i, 0, 50) {
252 102 : EXPECT_EQ(0, SignedDiv32(i, 0));
253 10251 : TRACED_FORRANGE(int32_t, j, 1, i) {
254 2550 : EXPECT_EQ(1, SignedDiv32(j, j));
255 2550 : EXPECT_EQ(i / j, SignedDiv32(i, j));
256 2550 : EXPECT_EQ(-i / j, SignedDiv32(i, -j));
257 1275 : }
258 51 : }
259 1 : }
260 :
261 :
262 13158 : TEST(Bits, SignedMod32) {
263 2 : EXPECT_EQ(0, SignedMod32(std::numeric_limits<int32_t>::min(), -1));
264 2 : EXPECT_EQ(0, SignedMod32(std::numeric_limits<int32_t>::max(), 1));
265 409 : TRACED_FORRANGE(int32_t, i, 0, 50) {
266 102 : EXPECT_EQ(0, SignedMod32(i, 0));
267 10251 : TRACED_FORRANGE(int32_t, j, 1, i) {
268 2550 : EXPECT_EQ(0, SignedMod32(j, j));
269 2550 : EXPECT_EQ(i % j, SignedMod32(i, j));
270 2550 : EXPECT_EQ(i % j, SignedMod32(i, -j));
271 1275 : }
272 51 : }
273 1 : }
274 :
275 :
276 13158 : TEST(Bits, UnsignedAddOverflow32) {
277 1 : uint32_t val = 0;
278 : EXPECT_FALSE(UnsignedAddOverflow32(0, 0, &val));
279 2 : EXPECT_EQ(0u, val);
280 : EXPECT_TRUE(
281 : UnsignedAddOverflow32(std::numeric_limits<uint32_t>::max(), 1u, &val));
282 2 : EXPECT_EQ(std::numeric_limits<uint32_t>::min(), val);
283 : EXPECT_TRUE(UnsignedAddOverflow32(std::numeric_limits<uint32_t>::max(),
284 : std::numeric_limits<uint32_t>::max(),
285 : &val));
286 401 : TRACED_FORRANGE(uint32_t, i, 1, 50) {
287 11475 : TRACED_FORRANGE(uint32_t, j, 1, i) {
288 2550 : EXPECT_FALSE(UnsignedAddOverflow32(i, j, &val));
289 2550 : EXPECT_EQ(i + j, val);
290 1275 : }
291 50 : }
292 1 : }
293 :
294 :
295 13158 : TEST(Bits, UnsignedDiv32) {
296 409 : TRACED_FORRANGE(uint32_t, i, 0, 50) {
297 102 : EXPECT_EQ(0u, UnsignedDiv32(i, 0));
298 30651 : TRACED_FORRANGE(uint32_t, j, i + 1, 100) {
299 7650 : EXPECT_EQ(1u, UnsignedDiv32(j, j));
300 7650 : EXPECT_EQ(i / j, UnsignedDiv32(i, j));
301 3825 : }
302 51 : }
303 1 : }
304 :
305 :
306 13158 : TEST(Bits, UnsignedMod32) {
307 409 : TRACED_FORRANGE(uint32_t, i, 0, 50) {
308 102 : EXPECT_EQ(0u, UnsignedMod32(i, 0));
309 30651 : TRACED_FORRANGE(uint32_t, j, i + 1, 100) {
310 7650 : EXPECT_EQ(0u, UnsignedMod32(j, j));
311 7650 : EXPECT_EQ(i % j, UnsignedMod32(i, j));
312 3825 : }
313 51 : }
314 1 : }
315 :
316 : } // namespace bits
317 : } // namespace base
318 7893 : } // namespace v8
|
