1//===- unittests/Support/MathExtrasTest.cpp - math utils tests ------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "gtest/gtest.h"
11#include "llvm/Support/MathExtras.h"
12
13using namespace llvm;
14
15namespace {
16
17TEST(MathExtras, countTrailingZeros) {
18  uint8_t Z8 = 0;
19  uint16_t Z16 = 0;
20  uint32_t Z32 = 0;
21  uint64_t Z64 = 0;
22  EXPECT_EQ(8u, countTrailingZeros(Z8));
23  EXPECT_EQ(16u, countTrailingZeros(Z16));
24  EXPECT_EQ(32u, countTrailingZeros(Z32));
25  EXPECT_EQ(64u, countTrailingZeros(Z64));
26
27  uint8_t NZ8 = 42;
28  uint16_t NZ16 = 42;
29  uint32_t NZ32 = 42;
30  uint64_t NZ64 = 42;
31  EXPECT_EQ(1u, countTrailingZeros(NZ8));
32  EXPECT_EQ(1u, countTrailingZeros(NZ16));
33  EXPECT_EQ(1u, countTrailingZeros(NZ32));
34  EXPECT_EQ(1u, countTrailingZeros(NZ64));
35}
36
37TEST(MathExtras, countLeadingZeros) {
38  uint8_t Z8 = 0;
39  uint16_t Z16 = 0;
40  uint32_t Z32 = 0;
41  uint64_t Z64 = 0;
42  EXPECT_EQ(8u, countLeadingZeros(Z8));
43  EXPECT_EQ(16u, countLeadingZeros(Z16));
44  EXPECT_EQ(32u, countLeadingZeros(Z32));
45  EXPECT_EQ(64u, countLeadingZeros(Z64));
46
47  uint8_t NZ8 = 42;
48  uint16_t NZ16 = 42;
49  uint32_t NZ32 = 42;
50  uint64_t NZ64 = 42;
51  EXPECT_EQ(2u, countLeadingZeros(NZ8));
52  EXPECT_EQ(10u, countLeadingZeros(NZ16));
53  EXPECT_EQ(26u, countLeadingZeros(NZ32));
54  EXPECT_EQ(58u, countLeadingZeros(NZ64));
55
56  EXPECT_EQ(8u, countLeadingZeros(0x00F000FFu));
57  EXPECT_EQ(8u, countLeadingZeros(0x00F12345u));
58  for (unsigned i = 0; i <= 30; ++i) {
59    EXPECT_EQ(31 - i, countLeadingZeros(1u << i));
60  }
61
62  EXPECT_EQ(8u, countLeadingZeros(0x00F1234500F12345ULL));
63  EXPECT_EQ(1u, countLeadingZeros(1ULL << 62));
64  for (unsigned i = 0; i <= 62; ++i) {
65    EXPECT_EQ(63 - i, countLeadingZeros(1ULL << i));
66  }
67}
68
69TEST(MathExtras, findFirstSet) {
70  uint8_t Z8 = 0;
71  uint16_t Z16 = 0;
72  uint32_t Z32 = 0;
73  uint64_t Z64 = 0;
74  EXPECT_EQ(0xFFULL, findFirstSet(Z8));
75  EXPECT_EQ(0xFFFFULL, findFirstSet(Z16));
76  EXPECT_EQ(0xFFFFFFFFULL, findFirstSet(Z32));
77  EXPECT_EQ(0xFFFFFFFFFFFFFFFFULL, findFirstSet(Z64));
78
79  uint8_t NZ8 = 42;
80  uint16_t NZ16 = 42;
81  uint32_t NZ32 = 42;
82  uint64_t NZ64 = 42;
83  EXPECT_EQ(1u, findFirstSet(NZ8));
84  EXPECT_EQ(1u, findFirstSet(NZ16));
85  EXPECT_EQ(1u, findFirstSet(NZ32));
86  EXPECT_EQ(1u, findFirstSet(NZ64));
87}
88
89TEST(MathExtras, findLastSet) {
90  uint8_t Z8 = 0;
91  uint16_t Z16 = 0;
92  uint32_t Z32 = 0;
93  uint64_t Z64 = 0;
94  EXPECT_EQ(0xFFULL, findLastSet(Z8));
95  EXPECT_EQ(0xFFFFULL, findLastSet(Z16));
96  EXPECT_EQ(0xFFFFFFFFULL, findLastSet(Z32));
97  EXPECT_EQ(0xFFFFFFFFFFFFFFFFULL, findLastSet(Z64));
98
99  uint8_t NZ8 = 42;
100  uint16_t NZ16 = 42;
101  uint32_t NZ32 = 42;
102  uint64_t NZ64 = 42;
103  EXPECT_EQ(5u, findLastSet(NZ8));
104  EXPECT_EQ(5u, findLastSet(NZ16));
105  EXPECT_EQ(5u, findLastSet(NZ32));
106  EXPECT_EQ(5u, findLastSet(NZ64));
107}
108
109TEST(MathExtras, isIntN) {
110  EXPECT_TRUE(isIntN(16, 32767));
111  EXPECT_FALSE(isIntN(16, 32768));
112}
113
114TEST(MathExtras, isUIntN) {
115  EXPECT_TRUE(isUIntN(16, 65535));
116  EXPECT_FALSE(isUIntN(16, 65536));
117  EXPECT_TRUE(isUIntN(1, 0));
118  EXPECT_TRUE(isUIntN(6, 63));
119}
120
121TEST(MathExtras, maxIntN) {
122  EXPECT_EQ(32767, maxIntN(16));
123  EXPECT_EQ(2147483647, maxIntN(32));
124}
125
126TEST(MathExtras, minIntN) {
127  EXPECT_EQ(-32768LL, minIntN(16));
128  EXPECT_EQ(-64LL, minIntN(7));
129}
130
131TEST(MathExtras, maxUIntN) {
132  EXPECT_EQ(0xffffULL, maxUIntN(16));
133  EXPECT_EQ(0xffffffffULL, maxUIntN(32));
134  EXPECT_EQ(1ULL, maxUIntN(1));
135  EXPECT_EQ(0x0fULL, maxUIntN(4));
136}
137
138TEST(MathExtras, reverseBits) {
139  uint8_t NZ8 = 42;
140  uint16_t NZ16 = 42;
141  uint32_t NZ32 = 42;
142  uint64_t NZ64 = 42;
143  EXPECT_EQ(0x54ULL, reverseBits(NZ8));
144  EXPECT_EQ(0x5400ULL, reverseBits(NZ16));
145  EXPECT_EQ(0x54000000ULL, reverseBits(NZ32));
146  EXPECT_EQ(0x5400000000000000ULL, reverseBits(NZ64));
147}
148
149TEST(MathExtras, isPowerOf2_32) {
150  EXPECT_TRUE(isPowerOf2_32(1 << 6));
151  EXPECT_TRUE(isPowerOf2_32(1 << 12));
152  EXPECT_FALSE(isPowerOf2_32((1 << 19) + 3));
153  EXPECT_FALSE(isPowerOf2_32(0xABCDEF0));
154}
155
156TEST(MathExtras, isPowerOf2_64) {
157  EXPECT_TRUE(isPowerOf2_64(1LL << 46));
158  EXPECT_TRUE(isPowerOf2_64(1LL << 12));
159  EXPECT_FALSE(isPowerOf2_64((1LL << 53) + 3));
160  EXPECT_FALSE(isPowerOf2_64(0xABCDEF0ABCDEF0LL));
161}
162
163TEST(MathExtras, ByteSwap_32) {
164  EXPECT_EQ(0x44332211u, ByteSwap_32(0x11223344));
165  EXPECT_EQ(0xDDCCBBAAu, ByteSwap_32(0xAABBCCDD));
166}
167
168TEST(MathExtras, ByteSwap_64) {
169  EXPECT_EQ(0x8877665544332211ULL, ByteSwap_64(0x1122334455667788LL));
170  EXPECT_EQ(0x1100FFEEDDCCBBAAULL, ByteSwap_64(0xAABBCCDDEEFF0011LL));
171}
172
173TEST(MathExtras, countLeadingOnes) {
174  for (int i = 30; i >= 0; --i) {
175    // Start with all ones and unset some bit.
176    EXPECT_EQ(31u - i, countLeadingOnes(0xFFFFFFFF ^ (1 << i)));
177  }
178  for (int i = 62; i >= 0; --i) {
179    // Start with all ones and unset some bit.
180    EXPECT_EQ(63u - i, countLeadingOnes(0xFFFFFFFFFFFFFFFFULL ^ (1LL << i)));
181  }
182  for (int i = 30; i >= 0; --i) {
183    // Start with all ones and unset some bit.
184    EXPECT_EQ(31u - i, countLeadingOnes(0xFFFFFFFF ^ (1 << i)));
185  }
186}
187
188TEST(MathExtras, FloatBits) {
189  static const float kValue = 5632.34f;
190  EXPECT_FLOAT_EQ(kValue, BitsToFloat(FloatToBits(kValue)));
191}
192
193TEST(MathExtras, DoubleBits) {
194  static const double kValue = 87987234.983498;
195  EXPECT_DOUBLE_EQ(kValue, BitsToDouble(DoubleToBits(kValue)));
196}
197
198TEST(MathExtras, MinAlign) {
199  EXPECT_EQ(1u, MinAlign(2, 3));
200  EXPECT_EQ(2u, MinAlign(2, 4));
201  EXPECT_EQ(1u, MinAlign(17, 64));
202  EXPECT_EQ(256u, MinAlign(256, 512));
203}
204
205TEST(MathExtras, NextPowerOf2) {
206  EXPECT_EQ(4u, NextPowerOf2(3));
207  EXPECT_EQ(16u, NextPowerOf2(15));
208  EXPECT_EQ(256u, NextPowerOf2(128));
209}
210
211TEST(MathExtras, alignTo) {
212  EXPECT_EQ(8u, alignTo(5, 8));
213  EXPECT_EQ(24u, alignTo(17, 8));
214  EXPECT_EQ(0u, alignTo(~0LL, 8));
215
216  EXPECT_EQ(7u, alignTo(5, 8, 7));
217  EXPECT_EQ(17u, alignTo(17, 8, 1));
218  EXPECT_EQ(3u, alignTo(~0LL, 8, 3));
219  EXPECT_EQ(552u, alignTo(321, 255, 42));
220}
221
222template<typename T>
223void SaturatingAddTestHelper()
224{
225  const T Max = std::numeric_limits<T>::max();
226  bool ResultOverflowed;
227
228  EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2)));
229  EXPECT_EQ(T(3), SaturatingAdd(T(1), T(2), &ResultOverflowed));
230  EXPECT_FALSE(ResultOverflowed);
231
232  EXPECT_EQ(Max, SaturatingAdd(Max, T(1)));
233  EXPECT_EQ(Max, SaturatingAdd(Max, T(1), &ResultOverflowed));
234  EXPECT_TRUE(ResultOverflowed);
235
236  EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1)));
237  EXPECT_EQ(Max, SaturatingAdd(T(1), T(Max - 1), &ResultOverflowed));
238  EXPECT_FALSE(ResultOverflowed);
239
240  EXPECT_EQ(Max, SaturatingAdd(T(1), Max));
241  EXPECT_EQ(Max, SaturatingAdd(T(1), Max, &ResultOverflowed));
242  EXPECT_TRUE(ResultOverflowed);
243
244  EXPECT_EQ(Max, SaturatingAdd(Max, Max));
245  EXPECT_EQ(Max, SaturatingAdd(Max, Max, &ResultOverflowed));
246  EXPECT_TRUE(ResultOverflowed);
247}
248
249TEST(MathExtras, SaturatingAdd) {
250  SaturatingAddTestHelper<uint8_t>();
251  SaturatingAddTestHelper<uint16_t>();
252  SaturatingAddTestHelper<uint32_t>();
253  SaturatingAddTestHelper<uint64_t>();
254}
255
256template<typename T>
257void SaturatingMultiplyTestHelper()
258{
259  const T Max = std::numeric_limits<T>::max();
260  bool ResultOverflowed;
261
262  // Test basic multiplication.
263  EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3)));
264  EXPECT_EQ(T(6), SaturatingMultiply(T(2), T(3), &ResultOverflowed));
265  EXPECT_FALSE(ResultOverflowed);
266
267  EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2)));
268  EXPECT_EQ(T(6), SaturatingMultiply(T(3), T(2), &ResultOverflowed));
269  EXPECT_FALSE(ResultOverflowed);
270
271  // Test multiplication by zero.
272  EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0)));
273  EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(0), &ResultOverflowed));
274  EXPECT_FALSE(ResultOverflowed);
275
276  EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0)));
277  EXPECT_EQ(T(0), SaturatingMultiply(T(1), T(0), &ResultOverflowed));
278  EXPECT_FALSE(ResultOverflowed);
279
280  EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1)));
281  EXPECT_EQ(T(0), SaturatingMultiply(T(0), T(1), &ResultOverflowed));
282  EXPECT_FALSE(ResultOverflowed);
283
284  EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0)));
285  EXPECT_EQ(T(0), SaturatingMultiply(Max, T(0), &ResultOverflowed));
286  EXPECT_FALSE(ResultOverflowed);
287
288  EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max));
289  EXPECT_EQ(T(0), SaturatingMultiply(T(0), Max, &ResultOverflowed));
290  EXPECT_FALSE(ResultOverflowed);
291
292  // Test multiplication by maximum value.
293  EXPECT_EQ(Max, SaturatingMultiply(Max, T(2)));
294  EXPECT_EQ(Max, SaturatingMultiply(Max, T(2), &ResultOverflowed));
295  EXPECT_TRUE(ResultOverflowed);
296
297  EXPECT_EQ(Max, SaturatingMultiply(T(2), Max));
298  EXPECT_EQ(Max, SaturatingMultiply(T(2), Max, &ResultOverflowed));
299  EXPECT_TRUE(ResultOverflowed);
300
301  EXPECT_EQ(Max, SaturatingMultiply(Max, Max));
302  EXPECT_EQ(Max, SaturatingMultiply(Max, Max, &ResultOverflowed));
303  EXPECT_TRUE(ResultOverflowed);
304
305  // Test interesting boundary conditions for algorithm -
306  // ((1 << A) - 1) * ((1 << B) + K) for K in [-1, 0, 1]
307  // and A + B == std::numeric_limits<T>::digits.
308  // We expect overflow iff A > B and K = 1.
309  const int Digits = std::numeric_limits<T>::digits;
310  for (int A = 1, B = Digits - 1; B >= 1; ++A, --B) {
311    for (int K = -1; K <= 1; ++K) {
312      T X = (T(1) << A) - T(1);
313      T Y = (T(1) << B) + K;
314      bool OverflowExpected = A > B && K == 1;
315
316      if(OverflowExpected) {
317        EXPECT_EQ(Max, SaturatingMultiply(X, Y));
318        EXPECT_EQ(Max, SaturatingMultiply(X, Y, &ResultOverflowed));
319        EXPECT_TRUE(ResultOverflowed);
320      } else {
321        EXPECT_EQ(X * Y, SaturatingMultiply(X, Y));
322        EXPECT_EQ(X * Y, SaturatingMultiply(X, Y, &ResultOverflowed));
323        EXPECT_FALSE(ResultOverflowed);
324      }
325    }
326  }
327}
328
329TEST(MathExtras, SaturatingMultiply) {
330  SaturatingMultiplyTestHelper<uint8_t>();
331  SaturatingMultiplyTestHelper<uint16_t>();
332  SaturatingMultiplyTestHelper<uint32_t>();
333  SaturatingMultiplyTestHelper<uint64_t>();
334}
335
336template<typename T>
337void SaturatingMultiplyAddTestHelper()
338{
339  const T Max = std::numeric_limits<T>::max();
340  bool ResultOverflowed;
341
342  // Test basic multiply-add.
343  EXPECT_EQ(T(16), SaturatingMultiplyAdd(T(2), T(3), T(10)));
344  EXPECT_EQ(T(16), SaturatingMultiplyAdd(T(2), T(3), T(10), &ResultOverflowed));
345  EXPECT_FALSE(ResultOverflowed);
346
347  // Test multiply overflows, add doesn't overflow
348  EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, T(0), &ResultOverflowed));
349  EXPECT_TRUE(ResultOverflowed);
350
351  // Test multiply doesn't overflow, add overflows
352  EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), T(1), Max, &ResultOverflowed));
353  EXPECT_TRUE(ResultOverflowed);
354
355  // Test multiply-add with Max as operand
356  EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), T(1), Max, &ResultOverflowed));
357  EXPECT_TRUE(ResultOverflowed);
358
359  EXPECT_EQ(Max, SaturatingMultiplyAdd(T(1), Max, T(1), &ResultOverflowed));
360  EXPECT_TRUE(ResultOverflowed);
361
362  EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, T(1), &ResultOverflowed));
363  EXPECT_TRUE(ResultOverflowed);
364
365  EXPECT_EQ(Max, SaturatingMultiplyAdd(Max, Max, Max, &ResultOverflowed));
366  EXPECT_TRUE(ResultOverflowed);
367
368  // Test multiply-add with 0 as operand
369  EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(1), T(1), T(0), &ResultOverflowed));
370  EXPECT_FALSE(ResultOverflowed);
371
372  EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(1), T(0), T(1), &ResultOverflowed));
373  EXPECT_FALSE(ResultOverflowed);
374
375  EXPECT_EQ(T(1), SaturatingMultiplyAdd(T(0), T(0), T(1), &ResultOverflowed));
376  EXPECT_FALSE(ResultOverflowed);
377
378  EXPECT_EQ(T(0), SaturatingMultiplyAdd(T(0), T(0), T(0), &ResultOverflowed));
379  EXPECT_FALSE(ResultOverflowed);
380
381}
382
383TEST(MathExtras, SaturatingMultiplyAdd) {
384  SaturatingMultiplyAddTestHelper<uint8_t>();
385  SaturatingMultiplyAddTestHelper<uint16_t>();
386  SaturatingMultiplyAddTestHelper<uint32_t>();
387  SaturatingMultiplyAddTestHelper<uint64_t>();
388}
389
390}
391