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