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 
13 using namespace llvm;
14 
15 namespace {
16 
TEST(MathExtras,countTrailingZeros)17 TEST(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 
TEST(MathExtras,countLeadingZeros)37 TEST(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 
TEST(MathExtras,findFirstSet)69 TEST(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 
TEST(MathExtras,findLastSet)89 TEST(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 
TEST(MathExtras,isIntN)109 TEST(MathExtras, isIntN) {
110   EXPECT_TRUE(isIntN(16, 32767));
111   EXPECT_FALSE(isIntN(16, 32768));
112 }
113 
TEST(MathExtras,isUIntN)114 TEST(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 
TEST(MathExtras,maxIntN)121 TEST(MathExtras, maxIntN) {
122   EXPECT_EQ(32767, maxIntN(16));
123   EXPECT_EQ(2147483647, maxIntN(32));
124 }
125 
TEST(MathExtras,minIntN)126 TEST(MathExtras, minIntN) {
127   EXPECT_EQ(-32768LL, minIntN(16));
128   EXPECT_EQ(-64LL, minIntN(7));
129 }
130 
TEST(MathExtras,maxUIntN)131 TEST(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 
TEST(MathExtras,reverseBits)138 TEST(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 
TEST(MathExtras,isPowerOf2_32)149 TEST(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 
TEST(MathExtras,isPowerOf2_64)156 TEST(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 
TEST(MathExtras,ByteSwap_32)163 TEST(MathExtras, ByteSwap_32) {
164   EXPECT_EQ(0x44332211u, ByteSwap_32(0x11223344));
165   EXPECT_EQ(0xDDCCBBAAu, ByteSwap_32(0xAABBCCDD));
166 }
167 
TEST(MathExtras,ByteSwap_64)168 TEST(MathExtras, ByteSwap_64) {
169   EXPECT_EQ(0x8877665544332211ULL, ByteSwap_64(0x1122334455667788LL));
170   EXPECT_EQ(0x1100FFEEDDCCBBAAULL, ByteSwap_64(0xAABBCCDDEEFF0011LL));
171 }
172 
TEST(MathExtras,countLeadingOnes)173 TEST(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 
TEST(MathExtras,FloatBits)188 TEST(MathExtras, FloatBits) {
189   static const float kValue = 5632.34f;
190   EXPECT_FLOAT_EQ(kValue, BitsToFloat(FloatToBits(kValue)));
191 }
192 
TEST(MathExtras,DoubleBits)193 TEST(MathExtras, DoubleBits) {
194   static const double kValue = 87987234.983498;
195   EXPECT_DOUBLE_EQ(kValue, BitsToDouble(DoubleToBits(kValue)));
196 }
197 
TEST(MathExtras,MinAlign)198 TEST(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 
TEST(MathExtras,NextPowerOf2)205 TEST(MathExtras, NextPowerOf2) {
206   EXPECT_EQ(4u, NextPowerOf2(3));
207   EXPECT_EQ(16u, NextPowerOf2(15));
208   EXPECT_EQ(256u, NextPowerOf2(128));
209 }
210 
TEST(MathExtras,alignTo)211 TEST(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 
222 template<typename T>
SaturatingAddTestHelper()223 void 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 
TEST(MathExtras,SaturatingAdd)249 TEST(MathExtras, SaturatingAdd) {
250   SaturatingAddTestHelper<uint8_t>();
251   SaturatingAddTestHelper<uint16_t>();
252   SaturatingAddTestHelper<uint32_t>();
253   SaturatingAddTestHelper<uint64_t>();
254 }
255 
256 template<typename T>
SaturatingMultiplyTestHelper()257 void 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 
TEST(MathExtras,SaturatingMultiply)329 TEST(MathExtras, SaturatingMultiply) {
330   SaturatingMultiplyTestHelper<uint8_t>();
331   SaturatingMultiplyTestHelper<uint16_t>();
332   SaturatingMultiplyTestHelper<uint32_t>();
333   SaturatingMultiplyTestHelper<uint64_t>();
334 }
335 
336 template<typename T>
SaturatingMultiplyAddTestHelper()337 void 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 
TEST(MathExtras,SaturatingMultiplyAdd)383 TEST(MathExtras, SaturatingMultiplyAdd) {
384   SaturatingMultiplyAddTestHelper<uint8_t>();
385   SaturatingMultiplyAddTestHelper<uint16_t>();
386   SaturatingMultiplyAddTestHelper<uint32_t>();
387   SaturatingMultiplyAddTestHelper<uint64_t>();
388 }
389 
390 }
391