1 //===- llvm/unittest/Support/ScaledNumberTest.cpp - ScaledPair tests -----==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Support/ScaledNumber.h"
12 #include "llvm/Support/DataTypes.h"
13 #include "gtest/gtest.h"
16 using namespace llvm::ScaledNumbers;
20 template <class UIntT> struct ScaledPair {
23 ScaledPair(const std::pair<UIntT, int16_t> &F) : D(F.first), S(F.second) {}
24 ScaledPair(UIntT D, int S) : D(D), S(S) {}
26 bool operator==(const ScaledPair<UIntT> &X) const {
27 return D == X.D && S == X.S;
30 template <class UIntT>
31 bool operator==(const std::pair<UIntT, int16_t> &L,
32 const ScaledPair<UIntT> &R) {
33 return ScaledPair<UIntT>(L) == R;
35 template <class UIntT>
36 void PrintTo(const ScaledPair<UIntT> &F, ::std::ostream *os) {
37 *os << F.D << "*2^" << F.S;
40 typedef ScaledPair<uint32_t> SP32;
41 typedef ScaledPair<uint64_t> SP64;
43 TEST(ScaledNumberHelpersTest, getRounded) {
44 EXPECT_EQ(getRounded32(0, 0, false), SP32(0, 0));
45 EXPECT_EQ(getRounded32(0, 0, true), SP32(1, 0));
46 EXPECT_EQ(getRounded32(20, 21, true), SP32(21, 21));
47 EXPECT_EQ(getRounded32(UINT32_MAX, 0, false), SP32(UINT32_MAX, 0));
48 EXPECT_EQ(getRounded32(UINT32_MAX, 0, true), SP32(1 << 31, 1));
50 EXPECT_EQ(getRounded64(0, 0, false), SP64(0, 0));
51 EXPECT_EQ(getRounded64(0, 0, true), SP64(1, 0));
52 EXPECT_EQ(getRounded64(20, 21, true), SP64(21, 21));
53 EXPECT_EQ(getRounded64(UINT32_MAX, 0, false), SP64(UINT32_MAX, 0));
54 EXPECT_EQ(getRounded64(UINT32_MAX, 0, true), SP64(UINT64_C(1) << 32, 0));
55 EXPECT_EQ(getRounded64(UINT64_MAX, 0, false), SP64(UINT64_MAX, 0));
56 EXPECT_EQ(getRounded64(UINT64_MAX, 0, true), SP64(UINT64_C(1) << 63, 1));
59 TEST(FloatsTest, getAdjusted) {
60 const uint64_t Max32In64 = UINT32_MAX;
61 EXPECT_EQ(getAdjusted32(0), SP32(0, 0));
62 EXPECT_EQ(getAdjusted32(0, 5), SP32(0, 5));
63 EXPECT_EQ(getAdjusted32(UINT32_MAX), SP32(UINT32_MAX, 0));
64 EXPECT_EQ(getAdjusted32(Max32In64 << 1), SP32(UINT32_MAX, 1));
65 EXPECT_EQ(getAdjusted32(Max32In64 << 1, 1), SP32(UINT32_MAX, 2));
66 EXPECT_EQ(getAdjusted32(Max32In64 << 31), SP32(UINT32_MAX, 31));
67 EXPECT_EQ(getAdjusted32(Max32In64 << 32), SP32(UINT32_MAX, 32));
68 EXPECT_EQ(getAdjusted32(Max32In64 + 1), SP32(1u << 31, 1));
69 EXPECT_EQ(getAdjusted32(UINT64_MAX), SP32(1u << 31, 33));
71 EXPECT_EQ(getAdjusted64(0), SP64(0, 0));
72 EXPECT_EQ(getAdjusted64(0, 5), SP64(0, 5));
73 EXPECT_EQ(getAdjusted64(UINT32_MAX), SP64(UINT32_MAX, 0));
74 EXPECT_EQ(getAdjusted64(Max32In64 << 1), SP64(Max32In64 << 1, 0));
75 EXPECT_EQ(getAdjusted64(Max32In64 << 1, 1), SP64(Max32In64 << 1, 1));
76 EXPECT_EQ(getAdjusted64(Max32In64 << 31), SP64(Max32In64 << 31, 0));
77 EXPECT_EQ(getAdjusted64(Max32In64 << 32), SP64(Max32In64 << 32, 0));
78 EXPECT_EQ(getAdjusted64(Max32In64 + 1), SP64(Max32In64 + 1, 0));
79 EXPECT_EQ(getAdjusted64(UINT64_MAX), SP64(UINT64_MAX, 0));
82 TEST(PositiveFloatTest, getProduct) {
84 EXPECT_EQ(SP32(0, 0), getProduct32(0, 0));
85 EXPECT_EQ(SP32(0, 0), getProduct32(0, 1));
86 EXPECT_EQ(SP32(0, 0), getProduct32(0, 33));
89 EXPECT_EQ(SP32(6, 0), getProduct32(2, 3));
90 EXPECT_EQ(SP32(UINT16_MAX / 3 * UINT16_MAX / 5 * 2, 0),
91 getProduct32(UINT16_MAX / 3, UINT16_MAX / 5 * 2));
93 // Overflow, no loss of precision.
94 // ==> 0xf00010 * 0x1001
95 // ==> 0xf00f00000 + 0x10010
97 // ==> 0xf00f1001 * 2^4
98 EXPECT_EQ(SP32(0xf00f1001, 4), getProduct32(0xf00010, 0x1001));
100 // Overflow, loss of precision, rounds down.
101 // ==> 0xf000070 * 0x1001
102 // ==> 0xf00f000000 + 0x70070
104 // ==> 0xf00f0700 * 2^8
105 EXPECT_EQ(SP32(0xf00f0700, 8), getProduct32(0xf000070, 0x1001));
107 // Overflow, loss of precision, rounds up.
108 // ==> 0xf000080 * 0x1001
109 // ==> 0xf00f000000 + 0x80080
111 // ==> 0xf00f0801 * 2^8
112 EXPECT_EQ(SP32(0xf00f0801, 8), getProduct32(0xf000080, 0x1001));
114 // Reverse operand order.
115 EXPECT_EQ(SP32(0, 0), getProduct32(1, 0));
116 EXPECT_EQ(SP32(0, 0), getProduct32(33, 0));
117 EXPECT_EQ(SP32(6, 0), getProduct32(3, 2));
118 EXPECT_EQ(SP32(UINT16_MAX / 3 * UINT16_MAX / 5 * 2, 0),
119 getProduct32(UINT16_MAX / 5 * 2, UINT16_MAX / 3));
120 EXPECT_EQ(SP32(0xf00f1001, 4), getProduct32(0x1001, 0xf00010));
121 EXPECT_EQ(SP32(0xf00f0700, 8), getProduct32(0x1001, 0xf000070));
122 EXPECT_EQ(SP32(0xf00f0801, 8), getProduct32(0x1001, 0xf000080));
124 // Round to overflow.
125 EXPECT_EQ(SP64(UINT64_C(1) << 63, 64),
126 getProduct64(UINT64_C(10376293541461622786),
127 UINT64_C(16397105843297379211)));
129 // Big number with rounding.
130 EXPECT_EQ(SP64(UINT64_C(9223372036854775810), 64),
131 getProduct64(UINT64_C(18446744073709551556),
132 UINT64_C(9223372036854775840)));
135 TEST(PositiveFloatTest, Divide) {
137 EXPECT_EQ(SP32(0, 0), getQuotient32(0, 0));
138 EXPECT_EQ(SP32(0, 0), getQuotient32(0, 1));
139 EXPECT_EQ(SP32(0, 0), getQuotient32(0, 73));
140 EXPECT_EQ(SP32(UINT32_MAX, INT16_MAX), getQuotient32(1, 0));
141 EXPECT_EQ(SP32(UINT32_MAX, INT16_MAX), getQuotient32(6, 0));
144 EXPECT_EQ(SP32(1u << 31, -31), getQuotient32(1, 1));
145 EXPECT_EQ(SP32(1u << 31, -30), getQuotient32(2, 1));
146 EXPECT_EQ(SP32(1u << 31, -33), getQuotient32(4, 16));
147 EXPECT_EQ(SP32(7u << 29, -29), getQuotient32(7, 1));
148 EXPECT_EQ(SP32(7u << 29, -30), getQuotient32(7, 2));
149 EXPECT_EQ(SP32(7u << 29, -33), getQuotient32(7, 16));
152 EXPECT_EQ(SP32(3u << 30, -30), getQuotient32(9, 3));
153 EXPECT_EQ(SP32(9u << 28, -28), getQuotient32(63, 7));
156 EXPECT_EQ(SP32(0xaaaaaaab, -33), getQuotient32(1, 3));
157 EXPECT_EQ(SP32(0xd5555555, -31), getQuotient32(5, 3));
159 // 64-bit division is hard to test, since divide64 doesn't canonicalized its
160 // output. However, this is the algorithm the implementation uses:
162 // - Shift divisor right.
163 // - If we have 1 (power of 2), return early -- not canonicalized.
164 // - Shift dividend left.
165 // - 64-bit integer divide.
166 // - If there's a remainder, continue with long division.
168 // TODO: require less knowledge about the implementation in the test.
171 EXPECT_EQ(SP64(0, 0), getQuotient64(0, 0));
172 EXPECT_EQ(SP64(0, 0), getQuotient64(0, 1));
173 EXPECT_EQ(SP64(0, 0), getQuotient64(0, 73));
174 EXPECT_EQ(SP64(UINT64_MAX, INT16_MAX), getQuotient64(1, 0));
175 EXPECT_EQ(SP64(UINT64_MAX, INT16_MAX), getQuotient64(6, 0));
178 EXPECT_EQ(SP64(1, 0), getQuotient64(1, 1));
179 EXPECT_EQ(SP64(2, 0), getQuotient64(2, 1));
180 EXPECT_EQ(SP64(4, -4), getQuotient64(4, 16));
181 EXPECT_EQ(SP64(7, 0), getQuotient64(7, 1));
182 EXPECT_EQ(SP64(7, -1), getQuotient64(7, 2));
183 EXPECT_EQ(SP64(7, -4), getQuotient64(7, 16));
186 EXPECT_EQ(SP64(UINT64_C(3) << 60, -60), getQuotient64(9, 3));
187 EXPECT_EQ(SP64(UINT64_C(9) << 58, -58), getQuotient64(63, 7));
190 EXPECT_EQ(SP64(0xaaaaaaaaaaaaaaab, -65), getQuotient64(1, 3));
191 EXPECT_EQ(SP64(0xd555555555555555, -63), getQuotient64(5, 3));
194 TEST(ScaledNumbersHelpersTest, getLg) {
195 EXPECT_EQ(0, getLg(UINT32_C(1), 0));
196 EXPECT_EQ(1, getLg(UINT32_C(1), 1));
197 EXPECT_EQ(1, getLg(UINT32_C(2), 0));
198 EXPECT_EQ(3, getLg(UINT32_C(1), 3));
199 EXPECT_EQ(3, getLg(UINT32_C(7), 0));
200 EXPECT_EQ(3, getLg(UINT32_C(8), 0));
201 EXPECT_EQ(3, getLg(UINT32_C(9), 0));
202 EXPECT_EQ(3, getLg(UINT32_C(64), -3));
203 EXPECT_EQ(31, getLg((UINT32_MAX >> 1) + 2, 0));
204 EXPECT_EQ(32, getLg(UINT32_MAX, 0));
205 EXPECT_EQ(-1, getLg(UINT32_C(1), -1));
206 EXPECT_EQ(-1, getLg(UINT32_C(2), -2));
207 EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), -1));
208 EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), 0));
209 EXPECT_EQ(INT32_MIN, getLg(UINT32_C(0), 1));
211 EXPECT_EQ(0, getLg(UINT64_C(1), 0));
212 EXPECT_EQ(1, getLg(UINT64_C(1), 1));
213 EXPECT_EQ(1, getLg(UINT64_C(2), 0));
214 EXPECT_EQ(3, getLg(UINT64_C(1), 3));
215 EXPECT_EQ(3, getLg(UINT64_C(7), 0));
216 EXPECT_EQ(3, getLg(UINT64_C(8), 0));
217 EXPECT_EQ(3, getLg(UINT64_C(9), 0));
218 EXPECT_EQ(3, getLg(UINT64_C(64), -3));
219 EXPECT_EQ(63, getLg((UINT64_MAX >> 1) + 2, 0));
220 EXPECT_EQ(64, getLg(UINT64_MAX, 0));
221 EXPECT_EQ(-1, getLg(UINT64_C(1), -1));
222 EXPECT_EQ(-1, getLg(UINT64_C(2), -2));
223 EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), -1));
224 EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), 0));
225 EXPECT_EQ(INT32_MIN, getLg(UINT64_C(0), 1));
228 TEST(ScaledNumbersHelpersTest, getLgFloor) {
229 EXPECT_EQ(0, getLgFloor(UINT32_C(1), 0));
230 EXPECT_EQ(1, getLgFloor(UINT32_C(1), 1));
231 EXPECT_EQ(1, getLgFloor(UINT32_C(2), 0));
232 EXPECT_EQ(2, getLgFloor(UINT32_C(7), 0));
233 EXPECT_EQ(3, getLgFloor(UINT32_C(1), 3));
234 EXPECT_EQ(3, getLgFloor(UINT32_C(8), 0));
235 EXPECT_EQ(3, getLgFloor(UINT32_C(9), 0));
236 EXPECT_EQ(3, getLgFloor(UINT32_C(64), -3));
237 EXPECT_EQ(31, getLgFloor((UINT32_MAX >> 1) + 2, 0));
238 EXPECT_EQ(31, getLgFloor(UINT32_MAX, 0));
239 EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), -1));
240 EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), 0));
241 EXPECT_EQ(INT32_MIN, getLgFloor(UINT32_C(0), 1));
243 EXPECT_EQ(0, getLgFloor(UINT64_C(1), 0));
244 EXPECT_EQ(1, getLgFloor(UINT64_C(1), 1));
245 EXPECT_EQ(1, getLgFloor(UINT64_C(2), 0));
246 EXPECT_EQ(2, getLgFloor(UINT64_C(7), 0));
247 EXPECT_EQ(3, getLgFloor(UINT64_C(1), 3));
248 EXPECT_EQ(3, getLgFloor(UINT64_C(8), 0));
249 EXPECT_EQ(3, getLgFloor(UINT64_C(9), 0));
250 EXPECT_EQ(3, getLgFloor(UINT64_C(64), -3));
251 EXPECT_EQ(63, getLgFloor((UINT64_MAX >> 1) + 2, 0));
252 EXPECT_EQ(63, getLgFloor(UINT64_MAX, 0));
253 EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), -1));
254 EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), 0));
255 EXPECT_EQ(INT32_MIN, getLgFloor(UINT64_C(0), 1));
258 TEST(ScaledNumbersHelpersTest, getLgCeiling) {
259 EXPECT_EQ(0, getLgCeiling(UINT32_C(1), 0));
260 EXPECT_EQ(1, getLgCeiling(UINT32_C(1), 1));
261 EXPECT_EQ(1, getLgCeiling(UINT32_C(2), 0));
262 EXPECT_EQ(3, getLgCeiling(UINT32_C(1), 3));
263 EXPECT_EQ(3, getLgCeiling(UINT32_C(7), 0));
264 EXPECT_EQ(3, getLgCeiling(UINT32_C(8), 0));
265 EXPECT_EQ(3, getLgCeiling(UINT32_C(64), -3));
266 EXPECT_EQ(4, getLgCeiling(UINT32_C(9), 0));
267 EXPECT_EQ(32, getLgCeiling(UINT32_MAX, 0));
268 EXPECT_EQ(32, getLgCeiling((UINT32_MAX >> 1) + 2, 0));
269 EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), -1));
270 EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), 0));
271 EXPECT_EQ(INT32_MIN, getLgCeiling(UINT32_C(0), 1));
273 EXPECT_EQ(0, getLgCeiling(UINT64_C(1), 0));
274 EXPECT_EQ(1, getLgCeiling(UINT64_C(1), 1));
275 EXPECT_EQ(1, getLgCeiling(UINT64_C(2), 0));
276 EXPECT_EQ(3, getLgCeiling(UINT64_C(1), 3));
277 EXPECT_EQ(3, getLgCeiling(UINT64_C(7), 0));
278 EXPECT_EQ(3, getLgCeiling(UINT64_C(8), 0));
279 EXPECT_EQ(3, getLgCeiling(UINT64_C(64), -3));
280 EXPECT_EQ(4, getLgCeiling(UINT64_C(9), 0));
281 EXPECT_EQ(64, getLgCeiling((UINT64_MAX >> 1) + 2, 0));
282 EXPECT_EQ(64, getLgCeiling(UINT64_MAX, 0));
283 EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), -1));
284 EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), 0));
285 EXPECT_EQ(INT32_MIN, getLgCeiling(UINT64_C(0), 1));