Debian Codegraph @

llvm-project/llvm/unittests/Support/MathExtrasTest.cpp

raw
1 //===- unittests/Support/MathExtrasTest.cpp - math utils tests ------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/Support/MathExtras.h"
10 #include "gtest/gtest.h"
11
12 using namespace llvm;
13
14 namespace {
15
16 TEST(MathExtras, countTrailingZeros) {
17 uint8_t Z8 = 0;
18 uint16_t Z16 = 0;
19 uint32_t Z32 = 0;
20 uint64_t Z64 = 0;
21 EXPECT_EQ(8u, countTrailingZeros(Z8));
22 EXPECT_EQ(16u, countTrailingZeros(Z16));
23 EXPECT_EQ(32u, countTrailingZeros(Z32));
24 EXPECT_EQ(64u, countTrailingZeros(Z64));
25
26 uint8_t NZ8 = 42;
27 uint16_t NZ16 = 42;
28 uint32_t NZ32 = 42;
29 uint64_t NZ64 = 42;
30 EXPECT_EQ(1u, countTrailingZeros(NZ8));
31 EXPECT_EQ(1u, countTrailingZeros(NZ16));
32 EXPECT_EQ(1u, countTrailingZeros(NZ32));
33 EXPECT_EQ(1u, countTrailingZeros(NZ64));
34 }
35
36 TEST(MathExtras, countLeadingZeros) {
37 uint8_t Z8 = 0;
38 uint16_t Z16 = 0;
39 uint32_t Z32 = 0;
40 uint64_t Z64 = 0;
41 EXPECT_EQ(8u, countLeadingZeros(Z8));
42 EXPECT_EQ(16u, countLeadingZeros(Z16));
43 EXPECT_EQ(32u, countLeadingZeros(Z32));
44 EXPECT_EQ(64u, countLeadingZeros(Z64));
45
46 uint8_t NZ8 = 42;
47 uint16_t NZ16 = 42;
48 uint32_t NZ32 = 42;
49 uint64_t NZ64 = 42;
50 EXPECT_EQ(2u, countLeadingZeros(NZ8));
51 EXPECT_EQ(10u, countLeadingZeros(NZ16));
52 EXPECT_EQ(26u, countLeadingZeros(NZ32));
53 EXPECT_EQ(58u, countLeadingZeros(NZ64));
54
55 EXPECT_EQ(8u, countLeadingZeros(0x00F000FFu));
56 EXPECT_EQ(8u, countLeadingZeros(0x00F12345u));
57 for (unsigned i = 0; i <= 30; ++i) {
58 EXPECT_EQ(31 - i, countLeadingZeros(1u << i));
59 }
60
61 EXPECT_EQ(8u, countLeadingZeros(0x00F1234500F12345ULL));
62 EXPECT_EQ(1u, countLeadingZeros(1ULL << 62));
63 for (unsigned i = 0; i <= 62; ++i) {
64 EXPECT_EQ(63 - i, countLeadingZeros(1ULL << i));
65 }
66 }
67
68 TEST(MathExtras, onesMask) {
69 EXPECT_EQ(0U, maskLeadingOnes<uint8_t>(0));
70 EXPECT_EQ(0U, maskTrailingOnes<uint8_t>(0));
71 EXPECT_EQ(0U, maskLeadingOnes<uint16_t>(0));
72 EXPECT_EQ(0U, maskTrailingOnes<uint16_t>(0));
73 EXPECT_EQ(0U, maskLeadingOnes<uint32_t>(0));
74 EXPECT_EQ(0U, maskTrailingOnes<uint32_t>(0));
75 EXPECT_EQ(0U, maskLeadingOnes<uint64_t>(0));
76 EXPECT_EQ(0U, maskTrailingOnes<uint64_t>(0));
77
78 EXPECT_EQ(0x00000003U, maskTrailingOnes<uint32_t>(2U));
79 EXPECT_EQ(0xC0000000U, maskLeadingOnes<uint32_t>(2U));
80
81 EXPECT_EQ(0x000007FFU, maskTrailingOnes<uint32_t>(11U));
82 EXPECT_EQ(0xFFE00000U, maskLeadingOnes<uint32_t>(11U));
83
84 EXPECT_EQ(0xFFFFFFFFU, maskTrailingOnes<uint32_t>(32U));
85 EXPECT_EQ(0xFFFFFFFFU, maskLeadingOnes<uint32_t>(32U));
86 EXPECT_EQ(0xFFFFFFFFFFFFFFFFULL, maskTrailingOnes<uint64_t>(64U));
87 EXPECT_EQ(0xFFFFFFFFFFFFFFFFULL, maskLeadingOnes<uint64_t>(64U));
88
89 EXPECT_EQ(0x0000FFFFFFFFFFFFULL, maskTrailingOnes<uint64_t>(48U));
90 EXPECT_EQ(0xFFFFFFFFFFFF0000ULL, maskLeadingOnes<uint64_t>(48U));
91 }
92
93 TEST(MathExtras, findFirstSet) {
94 uint8_t Z8 = 0;
95 uint16_t Z16 = 0;
96 uint32_t Z32 = 0;
97 uint64_t Z64 = 0;
98 EXPECT_EQ(0xFFULL, findFirstSet(Z8));
99 EXPECT_EQ(0xFFFFULL, findFirstSet(Z16));
100 EXPECT_EQ(0xFFFFFFFFULL, findFirstSet(Z32));
101 EXPECT_EQ(0xFFFFFFFFFFFFFFFFULL, findFirstSet(Z64));
102
103 uint8_t NZ8 = 42;
104 uint16_t NZ16 = 42;
105 uint32_t NZ32 = 42;
106 uint64_t NZ64 = 42;
107 EXPECT_EQ(1u, findFirstSet(NZ8));
108 EXPECT_EQ(1u, findFirstSet(NZ16));
109 EXPECT_EQ(1u, findFirstSet(NZ32));
110 EXPECT_EQ(1u, findFirstSet(NZ64));
111 }
112
113 TEST(MathExtras, findLastSet) {
114 uint8_t Z8 = 0;
115 uint16_t Z16 = 0;
116 uint32_t Z32 = 0;
117 uint64_t Z64 = 0;
118 EXPECT_EQ(0xFFULL, findLastSet(Z8));
119 EXPECT_EQ(0xFFFFULL, findLastSet(Z16));
120 EXPECT_EQ(0xFFFFFFFFULL, findLastSet(Z32));
121 EXPECT_EQ(0xFFFFFFFFFFFFFFFFULL, findLastSet(Z64));
122
123 uint8_t NZ8 = 42;
124 uint16_t NZ16 = 42;
125 uint32_t NZ32 = 42;
126 uint64_t NZ64 = 42;
127 EXPECT_EQ(5u, findLastSet(NZ8));
128 EXPECT_EQ(5u, findLastSet(NZ16));
129 EXPECT_EQ(5u, findLastSet(NZ32));
130 EXPECT_EQ(5u, findLastSet(NZ64));
131 }
132
133 TEST(MathExtras, isIntN) {
134 EXPECT_TRUE(isIntN(16, 32767));
135 EXPECT_FALSE(isIntN(16, 32768));
136 }
137
138 TEST(MathExtras, isUIntN) {
139 EXPECT_TRUE(isUIntN(16, 65535));
140 EXPECT_FALSE(isUIntN(16, 65536));
141 EXPECT_TRUE(isUIntN(1, 0));
142 EXPECT_TRUE(isUIntN(6, 63));
143 }
144
145 TEST(MathExtras, maxIntN) {
146 EXPECT_EQ(32767, maxIntN(16));
147 EXPECT_EQ(2147483647, maxIntN(32));
148 EXPECT_EQ(std::numeric_limits<int32_t>::max(), maxIntN(32));
149 EXPECT_EQ(std::numeric_limits<int64_t>::max(), maxIntN(64));
150 }
151
152 TEST(MathExtras, minIntN) {
153 EXPECT_EQ(-32768LL, minIntN(16));
154 EXPECT_EQ(-64LL, minIntN(7));
155 EXPECT_EQ(std::numeric_limits<int32_t>::min(), minIntN(32));
156 EXPECT_EQ(std::numeric_limits<int64_t>::min(), minIntN(64));
157 }
158
159 TEST(MathExtras, maxUIntN) {
160 EXPECT_EQ(0xffffULL, maxUIntN(16));
161 EXPECT_EQ(0xffffffffULL, maxUIntN(32));
162 EXPECT_EQ(0xffffffffffffffffULL, maxUIntN(64));
163 EXPECT_EQ(1ULL, maxUIntN(1));
164 EXPECT_EQ(0x0fULL, maxUIntN(4));
165 }
166
167 TEST(MathExtras, reverseBits) {
168 uint8_t NZ8 = 42;
169 uint16_t NZ16 = 42;
170 uint32_t NZ32 = 42;
171 uint64_t NZ64 = 42;
172 EXPECT_EQ(0x54ULL, reverseBits(NZ8));
173 EXPECT_EQ(0x5400ULL, reverseBits(NZ16));
174 EXPECT_EQ(0x54000000ULL, reverseBits(NZ32));
175 EXPECT_EQ(0x5400000000000000ULL, reverseBits(NZ64));
176 }
177
178 TEST(MathExtras, isShiftedMask_32) {
179 EXPECT_FALSE(isShiftedMask_32(0x01010101));
180 EXPECT_TRUE(isShiftedMask_32(0xf0000000));
181 EXPECT_TRUE(isShiftedMask_32(0xffff0000));
182 EXPECT_TRUE(isShiftedMask_32(0xff << 1));
183
184 unsigned MaskIdx, MaskLen;
185 EXPECT_FALSE(isShiftedMask_32(0x01010101, MaskIdx, MaskLen));
186 EXPECT_TRUE(isShiftedMask_32(0xf0000000, MaskIdx, MaskLen));
187 EXPECT_EQ(28, (int)MaskIdx);
188 EXPECT_EQ(4, (int)MaskLen);
189 EXPECT_TRUE(isShiftedMask_32(0xffff0000, MaskIdx, MaskLen));
190 EXPECT_EQ(16, (int)MaskIdx);
191 EXPECT_EQ(16, (int)MaskLen);
192 EXPECT_TRUE(isShiftedMask_32(0xff << 1, MaskIdx, MaskLen));
193 EXPECT_EQ(1, (int)MaskIdx);
194 EXPECT_EQ(8, (int)MaskLen);
195 }
196
197 TEST(MathExtras, isShiftedMask_64) {
198 EXPECT_FALSE(isShiftedMask_64(0x0101010101010101ull));
199 EXPECT_TRUE(isShiftedMask_64(0xf000000000000000ull));
200 EXPECT_TRUE(isShiftedMask_64(0xffff000000000000ull));
201 EXPECT_TRUE(isShiftedMask_64(0xffull << 55));
202
203 unsigned MaskIdx, MaskLen;
204 EXPECT_FALSE(isShiftedMask_64(0x0101010101010101ull, MaskIdx, MaskLen));
205 EXPECT_TRUE(isShiftedMask_64(0xf000000000000000ull, MaskIdx, MaskLen));
206 EXPECT_EQ(60, (int)MaskIdx);
207 EXPECT_EQ(4, (int)MaskLen);
208 EXPECT_TRUE(isShiftedMask_64(0xffff000000000000ull, MaskIdx, MaskLen));
209 EXPECT_EQ(48, (int)MaskIdx);
210 EXPECT_EQ(16, (int)MaskLen);
211 EXPECT_TRUE(isShiftedMask_64(0xffull << 55, MaskIdx, MaskLen));
212 EXPECT_EQ(55, (int)MaskIdx);
213 EXPECT_EQ(8, (int)MaskLen);
214 }
215
216 TEST(MathExtras, isPowerOf2_32) {
217 EXPECT_FALSE(isPowerOf2_32(0));
218 EXPECT_TRUE(isPowerOf2_32(1 << 6));
219 EXPECT_TRUE(isPowerOf2_32(1 << 12));
220 EXPECT_FALSE(isPowerOf2_32((1 << 19) + 3));
221 EXPECT_FALSE(isPowerOf2_32(0xABCDEF0));
222 }
223
224 TEST(MathExtras, isPowerOf2_64) {
225 EXPECT_FALSE(isPowerOf2_64(0));
226 EXPECT_TRUE(isPowerOf2_64(1LL << 46));
227 EXPECT_TRUE(isPowerOf2_64(1LL << 12));
228 EXPECT_FALSE(isPowerOf2_64((1LL << 53) + 3));
229 EXPECT_FALSE(isPowerOf2_64(0xABCDEF0ABCDEF0LL));
230 }
231
232 TEST(MathExtras, PowerOf2Ceil) {
233 EXPECT_EQ(0U, PowerOf2Ceil(0U));
234 EXPECT_EQ(8U, PowerOf2Ceil(8U));
235 EXPECT_EQ(8U, PowerOf2Ceil(7U));
236 }
237
238 TEST(MathExtras, PowerOf2Floor) {
239 EXPECT_EQ(0U, PowerOf2Floor(0U));
240 EXPECT_EQ(8U, PowerOf2Floor(8U));
241 EXPECT_EQ(4U, PowerOf2Floor(7U));
242 }
243
244 TEST(MathExtras, CTLog2) {
245 EXPECT_EQ(CTLog2<1ULL << 0>(), 0U);
246 EXPECT_EQ(CTLog2<1ULL << 1>(), 1U);
247 EXPECT_EQ(CTLog2<1ULL << 2>(), 2U);
248 EXPECT_EQ(CTLog2<1ULL << 3>(), 3U);
249 EXPECT_EQ(CTLog2<1ULL << 4>(), 4U);
250 EXPECT_EQ(CTLog2<1ULL << 5>(), 5U);
251 EXPECT_EQ(CTLog2<1ULL << 6>(), 6U);
252 EXPECT_EQ(CTLog2<1ULL << 7>(), 7U);
253 EXPECT_EQ(CTLog2<1ULL << 8>(), 8U);
254 EXPECT_EQ(CTLog2<1ULL << 9>(), 9U);
255 EXPECT_EQ(CTLog2<1ULL << 10>(), 10U);
256 EXPECT_EQ(CTLog2<1ULL << 11>(), 11U);
257 EXPECT_EQ(CTLog2<1ULL << 12>(), 12U);
258 EXPECT_EQ(CTLog2<1ULL << 13>(), 13U);
259 EXPECT_EQ(CTLog2<1ULL << 14>(), 14U);
260 EXPECT_EQ(CTLog2<1ULL << 15>(), 15U);
261 }
262
263 TEST(MathExtras, countLeadingOnes) {
264 for (int i = 30; i >= 0; --i) {
265 // Start with all ones and unset some bit.
266 EXPECT_EQ(31u - i, countLeadingOnes(0xFFFFFFFF ^ (1 << i)));
267 }
268 for (int i = 62; i >= 0; --i) {
269 // Start with all ones and unset some bit.
270 EXPECT_EQ(63u - i, countLeadingOnes(0xFFFFFFFFFFFFFFFFULL ^ (1LL << i)));
271 }
272 for (int i = 30; i >= 0; --i) {
273 // Start with all ones and unset some bit.
274 EXPECT_EQ(31u - i, countLeadingOnes(0xFFFFFFFF ^ (1 << i)));
275 }
276 }
277
278 TEST(MathExtras, FloatBits) {
279 static const float kValue = 5632.34f;
280 EXPECT_FLOAT_EQ(kValue, BitsToFloat(FloatToBits(kValue)));
281 }
282
283 TEST(MathExtras, DoubleBits) {
284 static const double kValue = 87987234.983498;
285 EXPECT_DOUBLE_EQ(kValue, BitsToDouble(DoubleToBits(kValue)));
286 }
287
288 TEST(MathExtras, MinAlign) {
289 EXPECT_EQ(1u, MinAlign(2, 3));
290 EXPECT_EQ(2u, MinAlign(2, 4));
291 EXPECT_EQ(1u, MinAlign(17, 64));
292 EXPECT_EQ(256u, MinAlign(256, 512));
293 }
294
295 TEST(MathExtras, NextPowerOf2) {
296 EXPECT_EQ(4u, NextPowerOf2(3));
297 EXPECT_EQ(16u, NextPowerOf2(15));
298 EXPECT_EQ(256u, NextPowerOf2(128));
299 }
300
301 TEST(MathExtras, alignTo) {
302 EXPECT_EQ(8u, alignTo(5, 8));
303 EXPECT_EQ(24u, alignTo(17, 8));
304 EXPECT_EQ(0u, alignTo(~0LL, 8));
305
306 EXPECT_EQ(7u, alignTo(5, 8, 7));
307 EXPECT_EQ(17u, alignTo(17, 8, 1));
308 EXPECT_EQ(3u, alignTo(~0LL, 8, 3));
309 EXPECT_EQ(552u, alignTo(321, 255, 42));
310 }
311
312 template <typename T> void SaturatingAddTestHelper() {
313 const T Max = std::numeric_limits<T>::max();
314 bool ResultOverflowed;
315
316 EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2)));
317 EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2), &ResultOverflowed));
318 EXPECT_FALSE(ResultOverflowed);
319
320 EXPECT_EQ(Max, SaturatingAdd(Max, T(1)));
321 EXPECT_EQ(Max, SaturatingAdd(Max, T(1), &ResultOverflowed));
322 EXPECT_TRUE(ResultOverflowed);
323
324 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1)));
325 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1), &ResultOverflowed));
326 EXPECT_FALSE(ResultOverflowed);
327
328 EXPECT_EQ(Max, SaturatingAdd(T(1), Max));
329 EXPECT_EQ(Max, SaturatingAdd(T(1), Max, &ResultOverflowed));
330 EXPECT_TRUE(ResultOverflowed);
331
332 EXPECT_EQ(Max, SaturatingAdd(Max, Max));
333 EXPECT_EQ(Max, SaturatingAdd(Max, Max, &ResultOverflowed));
334 EXPECT_TRUE(ResultOverflowed);
335
336 EXPECT_EQ(T(6), SaturatingAdd(T(1), T(2), T(3)));
337 EXPECT_EQ(T(6), SaturatingAdd(T(1), T(2), T(3), &ResultOverflowed));
338 EXPECT_FALSE(ResultOverflowed);
339
340 EXPECT_EQ(T(10), SaturatingAdd(T(1), T(2), T(3), T(4)));
341 EXPECT_EQ(T(10), SaturatingAdd(T(1), T(2), T(3), T(4), &ResultOverflowed));
342 EXPECT_FALSE(ResultOverflowed);
343
344 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(0)));
345 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(0), &ResultOverflowed));
346 EXPECT_FALSE(ResultOverflowed);
347
348 EXPECT_EQ(Max, SaturatingAdd(T(0), T(0), Max));
349 EXPECT_EQ(Max, SaturatingAdd(T(0), T(0), Max, &ResultOverflowed));
350 EXPECT_FALSE(ResultOverflowed);
351
352 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(1)));
353 EXPECT_EQ(Max, SaturatingAdd(Max, T(0), T(1), &ResultOverflowed));
354 EXPECT_TRUE(ResultOverflowed);
355
356 EXPECT_EQ(Max, SaturatingAdd(T(0), T(1), Max));
357 EXPECT_EQ(Max, SaturatingAdd(T(0), T(1), Max, &ResultOverflowed));
358 EXPECT_TRUE(ResultOverflowed);
359
360 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 2), T(1)));
361 EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 2), T(1), &ResultOverflowed));
362 EXPECT_FALSE(ResultOverflowed);
363
364 EXPECT_EQ(Max, SaturatingAdd(T(1), T(1), T(Max - 2)));
365 EXPECT_EQ(Max, SaturatingAdd(T(1), T(1), T(Max - 2), &ResultOverflowed));
366 EXPECT_FALSE(ResultOverflowed);
367
368 EXPECT_EQ(Max, SaturatingAdd(Max, Max, Max));
369 EXPECT_EQ(Max, SaturatingAdd(Max, Max, Max, &ResultOverflowed));
370 EXPECT_TRUE(ResultOverflowed);
371 }
372
373 TEST(MathExtras, SaturatingAdd) {
374 SaturatingAddTestHelper<uint8_t>();
375 SaturatingAddTestHelper<uint16_t>();
376 SaturatingAddTestHelper<uint32_t>();
377 SaturatingAddTestHelper<uint64_t>();
378 }
379
380 template<typename T>
381 void SaturatingMultiplyTestHelper()
382 {
383 const T Max = std::numeric_limits<T>::max();
384 bool ResultOverflowed;
385
386 // Test basic multiplication.
387 EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3)));
388 EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3), &ResultOverflowed));
389 EXPECT_FALSE(ResultOverflowed);
390
391 EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2)));
392 EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2), &ResultOverflowed));
393 EXPECT_FALSE(ResultOverflowed);
394
395 // Test multiplication by zero.
396 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0)));
397 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0), &ResultOverflowed));
398 EXPECT_FALSE(ResultOverflowed);
399
400 EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0)));
401 EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0), &ResultOverflowed));
402 EXPECT_FALSE(ResultOverflowed);
403
404 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1)));
405 EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1), &ResultOverflowed));
406 EXPECT_FALSE(ResultOverflowed);
407
408 EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0)));
409 EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0), &ResultOverflowed));
410 EXPECT_FALSE(ResultOverflowed);
411
412 EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max));
413 EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max, &ResultOverflowed));
414 EXPECT_FALSE(ResultOverflowed);
415
416 // Test multiplication by maximum value.
417 EXPECT_EQ(Max, SaturatingMultiply(Max, T(2)));
418 EXPECT_EQ(Max, SaturatingMultiply(Max, T(2), &ResultOverflowed));
419 EXPECT_TRUE(ResultOverflowed);
420
421 EXPECT_EQ(Max, SaturatingMultiply(T(2), Max));
422 EXPECT_EQ(Max, SaturatingMultiply(T(2), Max, &ResultOverflowed));
423 EXPECT_TRUE(ResultOverflowed);
424
425 EXPECT_EQ(Max, SaturatingMultiply(Max, Max));
426 EXPECT_EQ(Max, SaturatingMultiply(Max, Max, &ResultOverflowed));
427 EXPECT_TRUE(ResultOverflowed);
428
429 // Test interesting boundary conditions for algorithm -
430 // ((1 << A) - 1) * ((1 << B) + K) for K in [-1, 0, 1]
431 // and A + B == std::numeric_limits<T>::digits.
432 // We expect overflow iff A > B and K = 1.
433 const int Digits = std::numeric_limits<T>::digits;
434 for (int A = 1, B = Digits - 1; B >= 1; ++A, --B) {
435 for (int K = -1; K <= 1; ++K) {
436 T X = (T(1) << A) - T(1);
437 T Y = (T(1) << B) + K;
438 bool OverflowExpected = A > B && K == 1;
439
440 if(OverflowExpected) {
441 EXPECT_EQ(Max, SaturatingMultiply(X, Y));
442 EXPECT_EQ(Max, SaturatingMultiply(X, Y, &ResultOverflowed));
443 EXPECT_TRUE(ResultOverflowed);
444 } else {
445 EXPECT_EQ(X * Y, SaturatingMultiply(X, Y));
446 EXPECT_EQ(X * Y, SaturatingMultiply(X, Y, &ResultOverflowed));
447 EXPECT_FALSE(ResultOverflowed);
448 }
449 }
450 }
451 }
452
453 TEST(MathExtras, SaturatingMultiply) {
454 SaturatingMultiplyTestHelper<uint8_t>();
455 SaturatingMultiplyTestHelper<uint16_t>();
456 SaturatingMultiplyTestHelper<uint32_t>();
457 SaturatingMultiplyTestHelper<uint64_t>();
458 }
459
460 template<typename T>
461 void SaturatingMultiplyAddTestHelper()
462 {
463 const T Max = std::numeric_limits<T>::max();
464 bool ResultOverflowed;
465
466 // Test basic multiply-add.
467 EXPECT_EQ(T(16), SaturatingMultiplyAdd(T(2), T(3), T(10)));
468 EXPECT_EQ(T(16), SaturatingMultiplyAdd(T(2), T(3), T(10), &ResultOverflowed));
469 EXPECT_FALSE(ResultOverflowed);
470
471 // Test multiply overflows, add doesn't overflow
472 EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, T(0), &ResultOverflowed));
473 EXPECT_TRUE(ResultOverflowed);
474
475 // Test multiply doesn't overflow, add overflows
476 EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), T(1), Max, &ResultOverflowed));
477 EXPECT_TRUE(ResultOverflowed);
478
479 // Test multiply-add with Max as operand
480 EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), T(1), Max, &ResultOverflowed));
481 EXPECT_TRUE(ResultOverflowed);
482
483 EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), Max, T(1), &ResultOverflowed));
484 EXPECT_TRUE(ResultOverflowed);
485
486 EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, T(1), &ResultOverflowed));
487 EXPECT_TRUE(ResultOverflowed);
488
489 EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, Max, &ResultOverflowed));
490 EXPECT_TRUE(ResultOverflowed);
491
492 // Test multiply-add with 0 as operand
493 EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(1), T(1), T(0), &ResultOverflowed));
494 EXPECT_FALSE(ResultOverflowed);
495
496 EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(1), T(0), T(1), &ResultOverflowed));
497 EXPECT_FALSE(ResultOverflowed);
498
499 EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(0), T(0), T(1), &ResultOverflowed));
500 EXPECT_FALSE(ResultOverflowed);
501
502 EXPECT_EQ(T(0), SaturatingMultiplyAdd(T(0), T(0), T(0), &ResultOverflowed));
503 EXPECT_FALSE(ResultOverflowed);
504
505 }
506
507 TEST(MathExtras, SaturatingMultiplyAdd) {
508 SaturatingMultiplyAddTestHelper<uint8_t>();
509 SaturatingMultiplyAddTestHelper<uint16_t>();
510 SaturatingMultiplyAddTestHelper<uint32_t>();
511 SaturatingMultiplyAddTestHelper<uint64_t>();
512 }
513
514 TEST(MathExtras, IsShiftedUInt) {
515 EXPECT_TRUE((isShiftedUInt<1, 0>(0)));
516 EXPECT_TRUE((isShiftedUInt<1, 0>(1)));
517 EXPECT_FALSE((isShiftedUInt<1, 0>(2)));
518 EXPECT_FALSE((isShiftedUInt<1, 0>(3)));
519 EXPECT_FALSE((isShiftedUInt<1, 0>(0x8000000000000000)));
520 EXPECT_TRUE((isShiftedUInt<1, 63>(0x8000000000000000)));
521 EXPECT_TRUE((isShiftedUInt<2, 62>(0xC000000000000000)));
522 EXPECT_FALSE((isShiftedUInt<2, 62>(0xE000000000000000)));
523
524 // 0x201 is ten bits long and has a 1 in the MSB and LSB.
525 EXPECT_TRUE((isShiftedUInt<10, 5>(uint64_t(0x201) << 5)));
526 EXPECT_FALSE((isShiftedUInt<10, 5>(uint64_t(0x201) << 4)));
527 EXPECT_FALSE((isShiftedUInt<10, 5>(uint64_t(0x201) << 6)));
528 }
529
530 TEST(MathExtras, IsShiftedInt) {
531 EXPECT_TRUE((isShiftedInt<1, 0>(0)));
532 EXPECT_TRUE((isShiftedInt<1, 0>(-1)));
533 EXPECT_FALSE((isShiftedInt<1, 0>(2)));
534 EXPECT_FALSE((isShiftedInt<1, 0>(3)));
535 EXPECT_FALSE((isShiftedInt<1, 0>(0x8000000000000000)));
536 EXPECT_TRUE((isShiftedInt<1, 63>(0x8000000000000000)));
537 EXPECT_TRUE((isShiftedInt<2, 62>(0xC000000000000000)));
538 EXPECT_FALSE((isShiftedInt<2, 62>(0xE000000000000000)));
539
540 // 0x201 is ten bits long and has a 1 in the MSB and LSB.
541 EXPECT_TRUE((isShiftedInt<11, 5>(int64_t(0x201) << 5)));
542 EXPECT_FALSE((isShiftedInt<11, 5>(int64_t(0x201) << 3)));
543 EXPECT_FALSE((isShiftedInt<11, 5>(int64_t(0x201) << 6)));
544 EXPECT_TRUE((isShiftedInt<11, 5>(-(int64_t(0x201) << 5))));
545 EXPECT_FALSE((isShiftedInt<11, 5>(-(int64_t(0x201) << 3))));
546 EXPECT_FALSE((isShiftedInt<11, 5>(-(int64_t(0x201) << 6))));
547
548 EXPECT_TRUE((isShiftedInt<6, 10>(-(int64_t(1) << 15))));
549 EXPECT_FALSE((isShiftedInt<6, 10>(int64_t(1) << 15)));
550 }
551
552 template <typename T>
553 class OverflowTest : public ::testing::Test { };
554
555 using OverflowTestTypes = ::testing::Types<signed char, short, int, long,
556 long long>;
557
558 TYPED_TEST_SUITE(OverflowTest, OverflowTestTypes, );
559
560 TYPED_TEST(OverflowTest, AddNoOverflow) {
561 TypeParam Result;
562 EXPECT_FALSE(AddOverflow<TypeParam>(1, 2, Result));
563 EXPECT_EQ(Result, TypeParam(3));
564 }
565
566 TYPED_TEST(OverflowTest, AddOverflowToNegative) {
567 TypeParam Result;
568 auto MaxValue = std::numeric_limits<TypeParam>::max();
569 EXPECT_TRUE(AddOverflow<TypeParam>(MaxValue, MaxValue, Result));
570 EXPECT_EQ(Result, TypeParam(-2));
571 }
572
573 TYPED_TEST(OverflowTest, AddOverflowToMin) {
574 TypeParam Result;
575 auto MaxValue = std::numeric_limits<TypeParam>::max();
576 EXPECT_TRUE(AddOverflow<TypeParam>(MaxValue, TypeParam(1), Result));
577 EXPECT_EQ(Result, std::numeric_limits<TypeParam>::min());
578 }
579
580 TYPED_TEST(OverflowTest, AddOverflowToZero) {
581 TypeParam Result;
582 auto MinValue = std::numeric_limits<TypeParam>::min();
583 EXPECT_TRUE(AddOverflow<TypeParam>(MinValue, MinValue, Result));
584 EXPECT_EQ(Result, TypeParam(0));
585 }
586
587 TYPED_TEST(OverflowTest, AddOverflowToMax) {
588 TypeParam Result;
589 auto MinValue = std::numeric_limits<TypeParam>::min();
590 EXPECT_TRUE(AddOverflow<TypeParam>(MinValue, TypeParam(-1), Result));
591 EXPECT_EQ(Result, std::numeric_limits<TypeParam>::max());
592 }
593
594 TYPED_TEST(OverflowTest, SubNoOverflow) {
595 TypeParam Result;
596 EXPECT_FALSE(SubOverflow<TypeParam>(1, 2, Result));
597 EXPECT_EQ(Result, TypeParam(-1));
598 }
599
600 TYPED_TEST(OverflowTest, SubOverflowToMax) {
601 TypeParam Result;
602 auto MinValue = std::numeric_limits<TypeParam>::min();
603 EXPECT_TRUE(SubOverflow<TypeParam>(0, MinValue, Result));
604 EXPECT_EQ(Result, MinValue);
605 }
606
607 TYPED_TEST(OverflowTest, SubOverflowToMin) {
608 TypeParam Result;
609 auto MinValue = std::numeric_limits<TypeParam>::min();
610 EXPECT_TRUE(SubOverflow<TypeParam>(0, MinValue, Result));
611 EXPECT_EQ(Result, MinValue);
612 }
613
614 TYPED_TEST(OverflowTest, SubOverflowToNegative) {
615 TypeParam Result;
616 auto MaxValue = std::numeric_limits<TypeParam>::max();
617 auto MinValue = std::numeric_limits<TypeParam>::min();
618 EXPECT_TRUE(SubOverflow<TypeParam>(MaxValue, MinValue, Result));
619 EXPECT_EQ(Result, TypeParam(-1));
620 }
621
622 TYPED_TEST(OverflowTest, SubOverflowToPositive) {
623 TypeParam Result;
624 auto MaxValue = std::numeric_limits<TypeParam>::max();
625 auto MinValue = std::numeric_limits<TypeParam>::min();
626 EXPECT_TRUE(SubOverflow<TypeParam>(MinValue, MaxValue, Result));
627 EXPECT_EQ(Result, TypeParam(1));
628 }
629
630 TYPED_TEST(OverflowTest, MulNoOverflow) {
631 TypeParam Result;
632 EXPECT_FALSE(MulOverflow<TypeParam>(1, 2, Result));
633 EXPECT_EQ(Result, 2);
634 EXPECT_FALSE(MulOverflow<TypeParam>(-1, 3, Result));
635 EXPECT_EQ(Result, -3);
636 EXPECT_FALSE(MulOverflow<TypeParam>(4, -2, Result));
637 EXPECT_EQ(Result, -8);
638 EXPECT_FALSE(MulOverflow<TypeParam>(-6, -5, Result));
639 EXPECT_EQ(Result, 30);
640 }
641
642 TYPED_TEST(OverflowTest, MulNoOverflowToMax) {
643 TypeParam Result;
644 auto MaxValue = std::numeric_limits<TypeParam>::max();
645 auto MinValue = std::numeric_limits<TypeParam>::min();
646 EXPECT_FALSE(MulOverflow<TypeParam>(MinValue + 1, -1, Result));
647 EXPECT_EQ(Result, MaxValue);
648 }
649
650 TYPED_TEST(OverflowTest, MulOverflowToMin) {
651 TypeParam Result;
652 auto MinValue = std::numeric_limits<TypeParam>::min();
653 EXPECT_TRUE(MulOverflow<TypeParam>(MinValue, -1, Result));
654 EXPECT_EQ(Result, MinValue);
655 }
656
657 TYPED_TEST(OverflowTest, MulOverflowMax) {
658 TypeParam Result;
659 auto MinValue = std::numeric_limits<TypeParam>::min();
660 auto MaxValue = std::numeric_limits<TypeParam>::max();
661 EXPECT_TRUE(MulOverflow<TypeParam>(MinValue, MinValue, Result));
662 EXPECT_EQ(Result, 0);
663 EXPECT_TRUE(MulOverflow<TypeParam>(MaxValue, MaxValue, Result));
664 EXPECT_EQ(Result, 1);
665 }
666
667 TYPED_TEST(OverflowTest, MulResultZero) {
668 TypeParam Result;
669 EXPECT_FALSE(MulOverflow<TypeParam>(4, 0, Result));
670 EXPECT_EQ(Result, TypeParam(0));
671 EXPECT_FALSE(MulOverflow<TypeParam>(-5, 0, Result));
672 EXPECT_EQ(Result, TypeParam(0));
673 EXPECT_FALSE(MulOverflow<TypeParam>(0, 5, Result));
674 EXPECT_EQ(Result, TypeParam(0));
675 EXPECT_FALSE(MulOverflow<TypeParam>(0, -5, Result));
676 EXPECT_EQ(Result, TypeParam(0));
677 }
678
679 } // namespace