Line data Source code
1 : //===- llvm/Support/ScaledNumber.h - Support for scaled numbers -*- C++ -*-===//
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 : // This file contains functions (and a class) useful for working with scaled
11 : // numbers -- in particular, pairs of integers where one represents digits and
12 : // another represents a scale. The functions are helpers and live in the
13 : // namespace ScaledNumbers. The class ScaledNumber is useful for modelling
14 : // certain cost metrics that need simple, integer-like semantics that are easy
15 : // to reason about.
16 : //
17 : // These might remind you of soft-floats. If you want one of those, you're in
18 : // the wrong place. Look at include/llvm/ADT/APFloat.h instead.
19 : //
20 : //===----------------------------------------------------------------------===//
21 :
22 : #ifndef LLVM_SUPPORT_SCALEDNUMBER_H
23 : #define LLVM_SUPPORT_SCALEDNUMBER_H
24 :
25 : #include "llvm/Support/MathExtras.h"
26 : #include <algorithm>
27 : #include <cstdint>
28 : #include <limits>
29 : #include <string>
30 : #include <tuple>
31 : #include <utility>
32 :
33 : namespace llvm {
34 : namespace ScaledNumbers {
35 :
36 : /// Maximum scale; same as APFloat for easy debug printing.
37 : const int32_t MaxScale = 16383;
38 :
39 : /// Maximum scale; same as APFloat for easy debug printing.
40 : const int32_t MinScale = -16382;
41 :
42 : /// Get the width of a number.
43 : template <class DigitsT> inline int getWidth() { return sizeof(DigitsT) * 8; }
44 :
45 : /// Conditionally round up a scaled number.
46 : ///
47 : /// Given \c Digits and \c Scale, round up iff \c ShouldRound is \c true.
48 : /// Always returns \c Scale unless there's an overflow, in which case it
49 : /// returns \c 1+Scale.
50 : ///
51 : /// \pre adding 1 to \c Scale will not overflow INT16_MAX.
52 : template <class DigitsT>
53 : inline std::pair<DigitsT, int16_t> getRounded(DigitsT Digits, int16_t Scale,
54 : bool ShouldRound) {
55 : static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
56 :
57 204368 : if (ShouldRound)
58 1228211 : if (!++Digits)
59 : // Overflow.
60 : return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1);
61 : return std::make_pair(Digits, Scale);
62 : }
63 :
64 : /// Convenience helper for 32-bit rounding.
65 : inline std::pair<uint32_t, int16_t> getRounded32(uint32_t Digits, int16_t Scale,
66 : bool ShouldRound) {
67 : return getRounded(Digits, Scale, ShouldRound);
68 : }
69 :
70 : /// Convenience helper for 64-bit rounding.
71 : inline std::pair<uint64_t, int16_t> getRounded64(uint64_t Digits, int16_t Scale,
72 : bool ShouldRound) {
73 : return getRounded(Digits, Scale, ShouldRound);
74 : }
75 :
76 : /// Adjust a 64-bit scaled number down to the appropriate width.
77 : ///
78 : /// \pre Adding 64 to \c Scale will not overflow INT16_MAX.
79 : template <class DigitsT>
80 37 : inline std::pair<DigitsT, int16_t> getAdjusted(uint64_t Digits,
81 : int16_t Scale = 0) {
82 : static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
83 :
84 : const int Width = getWidth<DigitsT>();
85 37 : if (Width == 64 || Digits <= std::numeric_limits<DigitsT>::max())
86 14 : return std::make_pair(Digits, Scale);
87 :
88 : // Shift right and round.
89 23 : int Shift = 64 - Width - countLeadingZeros(Digits);
90 23 : return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
91 23 : Digits & (UINT64_C(1) << (Shift - 1)));
92 : }
93 :
94 : /// Convenience helper for adjusting to 32 bits.
95 : inline std::pair<uint32_t, int16_t> getAdjusted32(uint64_t Digits,
96 : int16_t Scale = 0) {
97 9 : return getAdjusted<uint32_t>(Digits, Scale);
98 : }
99 :
100 : /// Convenience helper for adjusting to 64 bits.
101 : inline std::pair<uint64_t, int16_t> getAdjusted64(uint64_t Digits,
102 : int16_t Scale = 0) {
103 : return getAdjusted<uint64_t>(Digits, Scale);
104 : }
105 :
106 : /// Multiply two 64-bit integers to create a 64-bit scaled number.
107 : ///
108 : /// Implemented with four 64-bit integer multiplies.
109 : std::pair<uint64_t, int16_t> multiply64(uint64_t LHS, uint64_t RHS);
110 :
111 : /// Multiply two 32-bit integers to create a 32-bit scaled number.
112 : ///
113 : /// Implemented with one 64-bit integer multiply.
114 : template <class DigitsT>
115 4102737 : inline std::pair<DigitsT, int16_t> getProduct(DigitsT LHS, DigitsT RHS) {
116 : static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
117 :
118 4102737 : if (getWidth<DigitsT>() <= 32 || (LHS <= UINT32_MAX && RHS <= UINT32_MAX))
119 1337183 : return getAdjusted<DigitsT>(uint64_t(LHS) * RHS);
120 :
121 2765568 : return multiply64(LHS, RHS);
122 : }
123 :
124 : /// Convenience helper for 32-bit product.
125 : inline std::pair<uint32_t, int16_t> getProduct32(uint32_t LHS, uint32_t RHS) {
126 : return getProduct(LHS, RHS);
127 : }
128 :
129 : /// Convenience helper for 64-bit product.
130 : inline std::pair<uint64_t, int16_t> getProduct64(uint64_t LHS, uint64_t RHS) {
131 2 : return getProduct(LHS, RHS);
132 : }
133 :
134 : /// Divide two 64-bit integers to create a 64-bit scaled number.
135 : ///
136 : /// Implemented with long division.
137 : ///
138 : /// \pre \c Dividend and \c Divisor are non-zero.
139 : std::pair<uint64_t, int16_t> divide64(uint64_t Dividend, uint64_t Divisor);
140 :
141 : /// Divide two 32-bit integers to create a 32-bit scaled number.
142 : ///
143 : /// Implemented with one 64-bit integer divide/remainder pair.
144 : ///
145 : /// \pre \c Dividend and \c Divisor are non-zero.
146 : std::pair<uint32_t, int16_t> divide32(uint32_t Dividend, uint32_t Divisor);
147 :
148 : /// Divide two 32-bit numbers to create a 32-bit scaled number.
149 : ///
150 : /// Implemented with one 64-bit integer divide/remainder pair.
151 : ///
152 : /// Returns \c (DigitsT_MAX, MaxScale) for divide-by-zero (0 for 0/0).
153 : template <class DigitsT>
154 2698461 : std::pair<DigitsT, int16_t> getQuotient(DigitsT Dividend, DigitsT Divisor) {
155 : static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
156 : static_assert(sizeof(DigitsT) == 4 || sizeof(DigitsT) == 8,
157 : "expected 32-bit or 64-bit digits");
158 :
159 : // Check for zero.
160 2698461 : if (!Dividend)
161 6 : return std::make_pair(0, 0);
162 2698455 : if (!Divisor)
163 4 : return std::make_pair(std::numeric_limits<DigitsT>::max(), MaxScale);
164 :
165 : if (getWidth<DigitsT>() == 64)
166 2698440 : return divide64(Dividend, Divisor);
167 11 : return divide32(Dividend, Divisor);
168 : }
169 16 :
170 : /// Convenience helper for 32-bit quotient.
171 : inline std::pair<uint32_t, int16_t> getQuotient32(uint32_t Dividend,
172 : uint32_t Divisor) {
173 : return getQuotient(Dividend, Divisor);
174 : }
175 16 :
176 3 : /// Convenience helper for 64-bit quotient.
177 13 : inline std::pair<uint64_t, int16_t> getQuotient64(uint64_t Dividend,
178 2 : uint64_t Divisor) {
179 : return getQuotient(Dividend, Divisor);
180 : }
181 11 :
182 : /// Implementation of getLg() and friends.
183 : ///
184 16 : /// Returns the rounded lg of \c Digits*2^Scale and an int specifying whether
185 : /// this was rounded up (1), down (-1), or exact (0).
186 : ///
187 : /// Returns \c INT32_MIN when \c Digits is zero.
188 : template <class DigitsT>
189 27908410 : inline std::pair<int32_t, int> getLgImpl(DigitsT Digits, int16_t Scale) {
190 16 : static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
191 3 :
192 27908423 : if (!Digits)
193 2 : return std::make_pair(INT32_MIN, 0);
194 :
195 : // Get the floor of the lg of Digits.
196 27908410 : int32_t LocalFloor = sizeof(Digits) * 8 - countLeadingZeros(Digits) - 1;
197 11 :
198 : // Get the actual floor.
199 27908410 : int32_t Floor = Scale + LocalFloor;
200 27908410 : if (Digits == UINT64_C(1) << LocalFloor)
201 : return std::make_pair(Floor, 0);
202 :
203 15 : // Round based on the next digit.
204 : assert(LocalFloor >= 1);
205 16587013 : bool Round = Digits & UINT64_C(1) << (LocalFloor - 1);
206 22239926 : return std::make_pair(Floor + Round, Round ? 1 : -1);
207 : }
208 :
209 14 : /// Get the lg (rounded) of a scaled number.
210 : ///
211 : /// Get the lg of \c Digits*2^Scale.
212 : ///
213 : /// Returns \c INT32_MIN when \c Digits is zero.
214 : template <class DigitsT> int32_t getLg(DigitsT Digits, int16_t Scale) {
215 1314189 : return getLgImpl(Digits, Scale).first;
216 : }
217 :
218 : /// Get the lg floor of a scaled number.
219 180 : ///
220 : /// Get the floor of the lg of \c Digits*2^Scale.
221 : ///
222 180 : /// Returns \c INT32_MIN when \c Digits is zero.
223 18 : template <class DigitsT> int32_t getLgFloor(DigitsT Digits, int16_t Scale) {
224 26594220 : auto Lg = getLgImpl(Digits, Scale);
225 26594220 : return Lg.first - (Lg.second > 0);
226 162 : }
227 :
228 : /// Get the lg ceiling of a scaled number.
229 162 : ///
230 162 : /// Get the ceiling of the lg of \c Digits*2^Scale.
231 : ///
232 : /// Returns \c INT32_MIN when \c Digits is zero.
233 : template <class DigitsT> int32_t getLgCeiling(DigitsT Digits, int16_t Scale) {
234 : auto Lg = getLgImpl(Digits, Scale);
235 46 : return Lg.first + (Lg.second < 0);
236 70 : }
237 :
238 93 : /// Implementation for comparing scaled numbers.
239 : ///
240 : /// Compare two 64-bit numbers with different scales. Given that the scale of
241 93 : /// \c L is higher than that of \c R by \c ScaleDiff, compare them. Return -1,
242 9 : /// 1, and 0 for less than, greater than, and equal, respectively.
243 : ///
244 : /// \pre 0 <= ScaleDiff < 64.
245 84 : int compareImpl(uint64_t L, uint64_t R, int ScaleDiff);
246 :
247 : /// Compare two scaled numbers.
248 84 : ///
249 84 : /// Compare two scaled numbers. Returns 0 for equal, -1 for less than, and 1
250 : /// for greater than.
251 : template <class DigitsT>
252 14611300 : int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale) {
253 : static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
254 24 :
255 36 : // Check for zero.
256 14611300 : if (!LDigits)
257 1314277 : return RDigits ? -1 : 0;
258 13297110 : if (!RDigits)
259 : return 1;
260 87 :
261 9 : // Check for the scale. Use getLgFloor to be sure that the scale difference
262 : // is always lower than 64.
263 13297110 : int32_t lgL = getLgFloor(LDigits, LScale), lgR = getLgFloor(RDigits, RScale);
264 13297188 : if (lgL != lgR)
265 20634555 : return lgL < lgR ? -1 : 1;
266 :
267 78 : // Compare digits.
268 354860 : if (LScale < RScale)
269 14188 : return compareImpl(LDigits, RDigits, RScale - LScale);
270 :
271 340594 : return -compareImpl(RDigits, LDigits, LScale - RScale);
272 : }
273 22 :
274 34 : /// Match scales of two numbers.
275 : ///
276 : /// Given two scaled numbers, match up their scales. Change the digits and
277 : /// scales in place. Shift the digits as necessary to form equivalent numbers,
278 : /// losing precision only when necessary.
279 : ///
280 : /// If the output value of \c LDigits (\c RDigits) is \c 0, the output value of
281 : /// \c LScale (\c RScale) is unspecified.
282 : ///
283 30 : /// As a convenience, returns the matching scale. If the output value of one
284 : /// number is zero, returns the scale of the other. If both are zero, which
285 : /// scale is returned is unspecified.
286 : template <class DigitsT>
287 : int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits,
288 : int16_t &RScale) {
289 : static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
290 :
291 : if (LScale < RScale)
292 26 : // Swap arguments.
293 26 : return matchScales(RDigits, RScale, LDigits, LScale);
294 : if (!LDigits)
295 : return RScale;
296 : if (!RDigits || LScale == RScale)
297 : return LScale;
298 :
299 : // Now LScale > RScale. Get the difference.
300 : int32_t ScaleDiff = int32_t(LScale) - RScale;
301 : if (ScaleDiff >= 2 * getWidth<DigitsT>()) {
302 26 : // Don't bother shifting. RDigits will get zero-ed out anyway.
303 26 : RDigits = 0;
304 : return LScale;
305 : }
306 :
307 : // Shift LDigits left as much as possible, then shift RDigits right.
308 : int32_t ShiftL = std::min<int32_t>(countLeadingZeros(LDigits), ScaleDiff);
309 : assert(ShiftL < getWidth<DigitsT>() && "can't shift more than width");
310 :
311 : int32_t ShiftR = ScaleDiff - ShiftL;
312 : if (ShiftR >= getWidth<DigitsT>()) {
313 : // Don't bother shifting. RDigits will get zero-ed out anyway.
314 : RDigits = 0;
315 : return LScale;
316 : }
317 :
318 : LDigits <<= ShiftL;
319 : RDigits >>= ShiftR;
320 45 :
321 : LScale -= ShiftL;
322 : RScale += ShiftR;
323 : assert(LScale == RScale && "scales should match");
324 45 : return LScale;
325 0 : }
326 45 :
327 : /// Get the sum of two scaled numbers.
328 : ///
329 : /// Get the sum of two scaled numbers with as much precision as possible.
330 : ///
331 45 : /// \pre Adding 1 to \c LScale (or \c RScale) will not overflow INT16_MAX.
332 45 : template <class DigitsT>
333 6 : std::pair<DigitsT, int16_t> getSum(DigitsT LDigits, int16_t LScale,
334 : DigitsT RDigits, int16_t RScale) {
335 : static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
336 39 :
337 22 : // Check inputs up front. This is only relevant if addition overflows, but
338 : // testing here should catch more bugs.
339 17 : assert(LScale < INT16_MAX && "scale too large");
340 : assert(RScale < INT16_MAX && "scale too large");
341 24 :
342 : // Normalize digits to match scales.
343 : int16_t Scale = matchScales(LDigits, LScale, RDigits, RScale);
344 :
345 24 : // Compute sum.
346 0 : DigitsT Sum = LDigits + RDigits;
347 24 : if (Sum >= RDigits)
348 : return std::make_pair(Sum, Scale);
349 :
350 : // Adjust sum after arithmetic overflow.
351 : DigitsT HighBit = DigitsT(1) << (getWidth<DigitsT>() - 1);
352 24 : return std::make_pair(HighBit | Sum >> 1, Scale + 1);
353 24 : }
354 4 :
355 : /// Convenience helper for 32-bit sum.
356 : inline std::pair<uint32_t, int16_t> getSum32(uint32_t LDigits, int16_t LScale,
357 20 : uint32_t RDigits, int16_t RScale) {
358 11 : return getSum(LDigits, LScale, RDigits, RScale);
359 : }
360 9 :
361 : /// Convenience helper for 64-bit sum.
362 21 : inline std::pair<uint64_t, int16_t> getSum64(uint64_t LDigits, int16_t LScale,
363 : uint64_t RDigits, int16_t RScale) {
364 : return getSum(LDigits, LScale, RDigits, RScale);
365 : }
366 21 :
367 0 : /// Get the difference of two scaled numbers.
368 21 : ///
369 : /// Get LHS minus RHS with as much precision as possible.
370 : ///
371 : /// Returns \c (0, 0) if the RHS is larger than the LHS.
372 : template <class DigitsT>
373 21 : std::pair<DigitsT, int16_t> getDifference(DigitsT LDigits, int16_t LScale,
374 21 : DigitsT RDigits, int16_t RScale) {
375 2 : static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
376 :
377 : // Normalize digits to match scales.
378 19 : const DigitsT SavedRDigits = RDigits;
379 11 : const int16_t SavedRScale = RScale;
380 : matchScales(LDigits, LScale, RDigits, RScale);
381 8 :
382 : // Compute difference.
383 : if (LDigits <= RDigits)
384 : return std::make_pair(0, 0);
385 : if (RDigits || !SavedRDigits)
386 : return std::make_pair(LDigits - RDigits, LScale);
387 :
388 : // Check if RDigits just barely lost its last bit. E.g., for 32-bit:
389 : //
390 : // 1*2^32 - 1*2^0 == 0xffffffff != 1*2^32
391 : const auto RLgFloor = getLgFloor(SavedRDigits, SavedRScale);
392 : if (!compare(LDigits, LScale, DigitsT(1), RLgFloor + getWidth<DigitsT>()))
393 : return std::make_pair(std::numeric_limits<DigitsT>::max(), RLgFloor);
394 :
395 : return std::make_pair(LDigits, LScale);
396 : }
397 129 :
398 : /// Convenience helper for 32-bit difference.
399 : inline std::pair<uint32_t, int16_t> getDifference32(uint32_t LDigits,
400 : int16_t LScale,
401 171 : uint32_t RDigits,
402 : int16_t RScale) {
403 : return getDifference(LDigits, LScale, RDigits, RScale);
404 129 : }
405 :
406 107 : /// Convenience helper for 64-bit difference.
407 : inline std::pair<uint64_t, int16_t> getDifference64(uint64_t LDigits,
408 : int16_t LScale,
409 : uint64_t RDigits,
410 77 : int16_t RScale) {
411 77 : return getDifference(LDigits, LScale, RDigits, RScale);
412 : }
413 0 :
414 0 : } // end namespace ScaledNumbers
415 : } // end namespace llvm
416 :
417 : namespace llvm {
418 77 :
419 : class raw_ostream;
420 : class ScaledNumberBase {
421 77 : public:
422 77 : static const int DefaultPrecision = 10;
423 :
424 0 : static void dump(uint64_t D, int16_t E, int Width);
425 0 : static raw_ostream &print(raw_ostream &OS, uint64_t D, int16_t E, int Width,
426 : unsigned Precision);
427 : static std::string toString(uint64_t D, int16_t E, int Width,
428 77 : unsigned Precision);
429 77 : static int countLeadingZeros32(uint32_t N) { return countLeadingZeros(N); }
430 0 : static int countLeadingZeros64(uint64_t N) { return countLeadingZeros(N); }
431 77 : static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
432 77 :
433 : static std::pair<uint64_t, bool> splitSigned(int64_t N) {
434 77 : if (N >= 0)
435 : return std::make_pair(N, false);
436 64 : uint64_t Unsigned = N == INT64_MIN ? UINT64_C(1) << 63 : uint64_t(-N);
437 : return std::make_pair(Unsigned, true);
438 : }
439 : static int64_t joinSigned(uint64_t U, bool IsNeg) {
440 85 : if (U > uint64_t(INT64_MAX))
441 : return IsNeg ? INT64_MIN : INT64_MAX;
442 : return IsNeg ? -int64_t(U) : int64_t(U);
443 64 : }
444 : };
445 53 :
446 : /// Simple representation of a scaled number.
447 : ///
448 : /// ScaledNumber is a number represented by digits and a scale. It uses simple
449 38 : /// saturation arithmetic and every operation is well-defined for every value.
450 38 : /// It's somewhat similar in behaviour to a soft-float, but is *not* a
451 : /// replacement for one. If you're doing numerics, look at \a APFloat instead.
452 0 : /// Nevertheless, we've found these semantics useful for modelling certain cost
453 0 : /// metrics.
454 : ///
455 : /// The number is split into a signed scale and unsigned digits. The number
456 : /// represented is \c getDigits()*2^getScale(). In this way, the digits are
457 38 : /// much like the mantissa in the x87 long double, but there is no canonical
458 : /// form so the same number can be represented by many bit representations.
459 : ///
460 38 : /// ScaledNumber is templated on the underlying integer type for digits, which
461 38 : /// is expected to be unsigned.
462 : ///
463 0 : /// Unlike APFloat, ScaledNumber does not model architecture floating point
464 0 : /// behaviour -- while this might make it a little faster and easier to reason
465 : /// about, it certainly makes it more dangerous for general numerics.
466 : ///
467 38 : /// ScaledNumber is totally ordered. However, there is no canonical form, so
468 38 : /// there are multiple representations of most scalars. E.g.:
469 : ///
470 38 : /// ScaledNumber(8u, 0) == ScaledNumber(4u, 1)
471 38 : /// ScaledNumber(4u, 1) == ScaledNumber(2u, 2)
472 : /// ScaledNumber(2u, 2) == ScaledNumber(1u, 3)
473 38 : ///
474 : /// ScaledNumber implements most arithmetic operations. Precision is kept
475 65 : /// where possible. Uses simple saturation arithmetic, so that operations
476 : /// saturate to 0.0 or getLargest() rather than under or overflowing. It has
477 : /// some extra arithmetic for unit inversion. 0.0/0.0 is defined to be 0.0.
478 : /// Any other division by 0.0 is defined to be getLargest().
479 86 : ///
480 : /// As a convenience for modifying the exponent, left and right shifting are
481 : /// both implemented, and both interpret negative shifts as positive shifts in
482 65 : /// the opposite direction.
483 : ///
484 54 : /// Scales are limited to the range accepted by x87 long double. This makes
485 : /// it trivial to add functionality to convert to APFloat (this is already
486 : /// relied on for the implementation of printing).
487 : ///
488 39 : /// Possible (and conflicting) future directions:
489 39 : ///
490 : /// 1. Turn this into a wrapper around \a APFloat.
491 0 : /// 2. Share the algorithm implementations with \a APFloat.
492 0 : /// 3. Allow \a ScaledNumber to represent a signed number.
493 : template <class DigitsT> class ScaledNumber : ScaledNumberBase {
494 : public:
495 : static_assert(!std::numeric_limits<DigitsT>::is_signed,
496 39 : "only unsigned floats supported");
497 :
498 : typedef DigitsT DigitsType;
499 39 :
500 39 : private:
501 : typedef std::numeric_limits<DigitsType> DigitsLimits;
502 0 :
503 0 : static const int Width = sizeof(DigitsType) * 8;
504 : static_assert(Width <= 64, "invalid integer width for digits");
505 :
506 39 : private:
507 39 : DigitsType Digits = 0;
508 : int16_t Scale = 0;
509 39 :
510 39 : public:
511 72153 : ScaledNumber() = default;
512 39 :
513 283 : constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
514 283 : : Digits(Digits), Scale(Scale) {}
515 :
516 : private:
517 : ScaledNumber(const std::pair<DigitsT, int16_t> &X)
518 6801165 : : Digits(X.first), Scale(X.second) {}
519 :
520 : public:
521 52 : static ScaledNumber getZero() { return ScaledNumber(0, 0); }
522 : static ScaledNumber getOne() { return ScaledNumber(1, 0); }
523 : static ScaledNumber getLargest() {
524 : return ScaledNumber(DigitsLimits::max(), ScaledNumbers::MaxScale);
525 : }
526 : static ScaledNumber get(uint64_t N) { return adjustToWidth(N, 0); }
527 : static ScaledNumber getInverse(uint64_t N) {
528 : return get(N).invert();
529 : }
530 : static ScaledNumber getFraction(DigitsType N, DigitsType D) {
531 52 : return getQuotient(N, D);
532 : }
533 :
534 52 : int16_t getScale() const { return Scale; }
535 52 : DigitsType getDigits() const { return Digits; }
536 :
537 : /// Convert to the given integer type.
538 : ///
539 : /// Convert to \c IntT using simple saturating arithmetic, truncating if
540 8 : /// necessary.
541 : template <class IntT> IntT toInt() const;
542 26 :
543 0 : bool isZero() const { return !Digits; }
544 : bool isLargest() const { return *this == getLargest(); }
545 : bool isOne() const {
546 : if (Scale > 0 || Scale <= -Width)
547 : return false;
548 : return Digits == DigitsType(1) << -Scale;
549 : }
550 :
551 : /// The log base 2, rounded.
552 26 : ///
553 : /// Get the lg of the scalar. lg 0 is defined to be INT32_MIN.
554 0 : int32_t lg() const { return ScaledNumbers::getLg(Digits, Scale); }
555 26 :
556 26 : /// The log base 2, rounded towards INT32_MIN.
557 : ///
558 : /// Get the lg floor. lg 0 is defined to be INT32_MIN.
559 : int32_t lgFloor() const { return ScaledNumbers::getLgFloor(Digits, Scale); }
560 :
561 4 : /// The log base 2, rounded towards INT32_MAX.
562 : ///
563 26 : /// Get the lg ceiling. lg 0 is defined to be INT32_MIN.
564 : int32_t lgCeiling() const {
565 : return ScaledNumbers::getLgCeiling(Digits, Scale);
566 : }
567 :
568 : bool operator==(const ScaledNumber &X) const { return compare(X) == 0; }
569 7306075 : bool operator<(const ScaledNumber &X) const { return compare(X) < 0; }
570 : bool operator!=(const ScaledNumber &X) const { return compare(X) != 0; }
571 : bool operator>(const ScaledNumber &X) const { return compare(X) > 0; }
572 : bool operator<=(const ScaledNumber &X) const { return compare(X) <= 0; }
573 26 : bool operator>=(const ScaledNumber &X) const { return compare(X) >= 0; }
574 :
575 : bool operator!() const { return isZero(); }
576 26 :
577 26 : /// Convert to a decimal representation in a string.
578 : ///
579 : /// Convert to a string. Uses scientific notation for very large/small
580 : /// numbers. Scientific notation is used roughly for numbers outside of the
581 : /// range 2^-64 through 2^64.
582 4 : ///
583 : /// \c Precision indicates the number of decimal digits of precision to use;
584 : /// 0 requests the maximum available.
585 : ///
586 : /// As a special case to make debugging easier, if the number is small enough
587 : /// to convert without scientific notation and has more than \c Precision
588 25 : /// digits before the decimal place, it's printed accurately to the first
589 : /// digit past zero. E.g., assuming 10 digits of precision:
590 : ///
591 : /// 98765432198.7654... => 98765432198.8
592 : /// 8765432198.7654... => 8765432198.8
593 : /// 765432198.7654... => 765432198.8
594 25 : /// 65432198.7654... => 65432198.77
595 : /// 5432198.7654... => 5432198.765
596 : std::string toString(unsigned Precision = DefaultPrecision) {
597 : return ScaledNumberBase::toString(Digits, Scale, Width, Precision);
598 : }
599 :
600 : /// Print a decimal representation.
601 : ///
602 : /// Print a string. See toString for documentation.
603 39 : raw_ostream &print(raw_ostream &OS,
604 : unsigned Precision = DefaultPrecision) const {
605 532 : return ScaledNumberBase::print(OS, Digits, Scale, Width, Precision);
606 : }
607 : void dump() const { return ScaledNumberBase::dump(Digits, Scale, Width); }
608 39 :
609 39 : ScaledNumber &operator+=(const ScaledNumber &X) {
610 39 : std::tie(Digits, Scale) =
611 : ScaledNumbers::getSum(Digits, Scale, X.Digits, X.Scale);
612 : // Check for exponent past MaxScale.
613 39 : if (Scale > ScaledNumbers::MaxScale)
614 18 : *this = getLargest();
615 21 : return *this;
616 13 : }
617 : ScaledNumber &operator-=(const ScaledNumber &X) {
618 : std::tie(Digits, Scale) =
619 : ScaledNumbers::getDifference(Digits, Scale, X.Digits, X.Scale);
620 : return *this;
621 8 : }
622 8 : ScaledNumber &operator*=(const ScaledNumber &X);
623 4 : ScaledNumber &operator/=(const ScaledNumber &X);
624 : ScaledNumber &operator<<=(int16_t Shift) {
625 4010752 : shiftLeft(Shift);
626 : return *this;
627 19 : }
628 : ScaledNumber &operator>>=(int16_t Shift) {
629 : shiftRight(Shift);
630 : return *this;
631 : }
632 19 :
633 19 : private:
634 19 : void shiftLeft(int32_t Shift);
635 : void shiftRight(int32_t Shift);
636 :
637 19 : /// Adjust two floats to have matching exponents.
638 9 : ///
639 10 : /// Adjust \c this and \c X to have matching exponents. Returns the new \c X
640 6 : /// by value. Does nothing if \a isZero() for either.
641 : ///
642 : /// The value that compares smaller will lose precision, and possibly become
643 : /// \a isZero().
644 : ScaledNumber matchScales(ScaledNumber X) {
645 4 : ScaledNumbers::matchScales(Digits, Scale, X.Digits, X.Scale);
646 4 : return X;
647 2 : }
648 :
649 2 : public:
650 : /// Scale a large number accurately.
651 20 : ///
652 : /// Scale N (multiply it by this). Uses full precision multiplication, even
653 : /// if Width is smaller than 64, so information is not lost.
654 : uint64_t scale(uint64_t N) const;
655 : uint64_t scaleByInverse(uint64_t N) const {
656 20 : // TODO: implement directly, rather than relying on inverse. Inverse is
657 20 : // expensive.
658 20 : return inverse().scale(N);
659 : }
660 : int64_t scale(int64_t N) const {
661 20 : std::pair<uint64_t, bool> Unsigned = splitSigned(N);
662 9 : return joinSigned(scale(Unsigned.first), Unsigned.second);
663 11 : }
664 7 : int64_t scaleByInverse(int64_t N) const {
665 : std::pair<uint64_t, bool> Unsigned = splitSigned(N);
666 : return joinSigned(scaleByInverse(Unsigned.first), Unsigned.second);
667 : }
668 :
669 4 : int compare(const ScaledNumber &X) const {
670 7306079 : return ScaledNumbers::compare(Digits, Scale, X.Digits, X.Scale);
671 2 : }
672 0 : int compareTo(uint64_t N) const {
673 2 : return ScaledNumbers::compare<uint64_t>(Digits, Scale, N, 0);
674 : }
675 3653321 : int compareTo(int64_t N) const { return N < 0 ? 1 : compareTo(uint64_t(N)); }
676 :
677 2764169 : ScaledNumber &invert() { return *this = ScaledNumber::get(1) / *this; }
678 1382084 : ScaledNumber inverse() const { return ScaledNumber(*this).invert(); }
679 :
680 : private:
681 19 : static ScaledNumber getProduct(DigitsType LHS, DigitsType RHS) {
682 8205468 : return ScaledNumbers::getProduct(LHS, RHS);
683 : }
684 : static ScaledNumber getQuotient(DigitsType Dividend, DigitsType Divisor) {
685 5396861 : return ScaledNumbers::getQuotient(Dividend, Divisor);
686 : }
687 :
688 : static int countLeadingZerosWidth(DigitsType Digits) {
689 18 : if (Width == 64)
690 : return countLeadingZeros64(Digits);
691 : if (Width == 32)
692 : return countLeadingZeros32(Digits);
693 : return countLeadingZeros32(Digits) + Width - 32;
694 : }
695 :
696 : /// Adjust a number to width, rounding up if necessary.
697 : ///
698 : /// Should only be called for \c Shift close to zero.
699 : ///
700 : /// \pre Shift >= MinScale && Shift + 64 <= MaxScale.
701 : static ScaledNumber adjustToWidth(uint64_t N, int32_t Shift) {
702 : assert(Shift >= ScaledNumbers::MinScale && "Shift should be close to 0");
703 : assert(Shift <= ScaledNumbers::MaxScale - 64 &&
704 : "Shift should be close to 0");
705 : auto Adjusted = ScaledNumbers::getAdjusted<DigitsT>(N, Shift);
706 : return Adjusted;
707 0 : }
708 0 :
709 : static ScaledNumber getRounded(ScaledNumber P, bool Round) {
710 : // Saturate.
711 : if (P.isLargest())
712 : return P;
713 :
714 : return ScaledNumbers::getRounded(P.Digits, P.Scale, Round);
715 : }
716 : };
717 :
718 : #define SCALED_NUMBER_BOP(op, base) \
719 : template <class DigitsT> \
720 : ScaledNumber<DigitsT> operator op(const ScaledNumber<DigitsT> &L, \
721 : const ScaledNumber<DigitsT> &R) { \
722 : return ScaledNumber<DigitsT>(L) base R; \
723 : }
724 : SCALED_NUMBER_BOP(+, += )
725 : SCALED_NUMBER_BOP(-, -= )
726 4030574 : SCALED_NUMBER_BOP(*, *= )
727 2698147 : SCALED_NUMBER_BOP(/, /= )
728 : #undef SCALED_NUMBER_BOP
729 :
730 : template <class DigitsT>
731 : ScaledNumber<DigitsT> operator<<(const ScaledNumber<DigitsT> &L,
732 : int16_t Shift) {
733 : return ScaledNumber<DigitsT>(L) <<= Shift;
734 : }
735 :
736 : template <class DigitsT>
737 : ScaledNumber<DigitsT> operator>>(const ScaledNumber<DigitsT> &L,
738 : int16_t Shift) {
739 : return ScaledNumber<DigitsT>(L) >>= Shift;
740 : }
741 :
742 : template <class DigitsT>
743 : raw_ostream &operator<<(raw_ostream &OS, const ScaledNumber<DigitsT> &X) {
744 0 : return X.print(OS, 10);
745 : }
746 :
747 : #define SCALED_NUMBER_COMPARE_TO_TYPE(op, T1, T2) \
748 : template <class DigitsT> \
749 : bool operator op(const ScaledNumber<DigitsT> &L, T1 R) { \
750 : return L.compareTo(T2(R)) op 0; \
751 : } \
752 : template <class DigitsT> \
753 : bool operator op(T1 L, const ScaledNumber<DigitsT> &R) { \
754 : return 0 op R.compareTo(T2(L)); \
755 : }
756 : #define SCALED_NUMBER_COMPARE_TO(op) \
757 : SCALED_NUMBER_COMPARE_TO_TYPE(op, uint64_t, uint64_t) \
758 : SCALED_NUMBER_COMPARE_TO_TYPE(op, uint32_t, uint64_t) \
759 : SCALED_NUMBER_COMPARE_TO_TYPE(op, int64_t, int64_t) \
760 : SCALED_NUMBER_COMPARE_TO_TYPE(op, int32_t, int64_t)
761 : SCALED_NUMBER_COMPARE_TO(< )
762 : SCALED_NUMBER_COMPARE_TO(> )
763 : SCALED_NUMBER_COMPARE_TO(== )
764 : SCALED_NUMBER_COMPARE_TO(!= )
765 : SCALED_NUMBER_COMPARE_TO(<= )
766 3651903 : SCALED_NUMBER_COMPARE_TO(>= )
767 : #undef SCALED_NUMBER_COMPARE_TO
768 : #undef SCALED_NUMBER_COMPARE_TO_TYPE
769 :
770 : template <class DigitsT>
771 : uint64_t ScaledNumber<DigitsT>::scale(uint64_t N) const {
772 : if (Width == 64 || N <= DigitsLimits::max())
773 : return (get(N) * *this).template toInt<uint64_t>();
774 :
775 : // Defer to the 64-bit version.
776 : return ScaledNumber<uint64_t>(Digits, Scale).scale(N);
777 : }
778 :
779 : template <class DigitsT>
780 : template <class IntT>
781 3653321 : IntT ScaledNumber<DigitsT>::toInt() const {
782 : typedef std::numeric_limits<IntT> Limits;
783 3653321 : if (*this < 1)
784 : return 0;
785 3651903 : if (*this >= Limits::max())
786 : return Limits::max();
787 :
788 3649385 : IntT N = Digits;
789 3649385 : if (Scale > 0) {
790 : assert(size_t(Scale) < sizeof(IntT) * 8);
791 1309149 : return N << Scale;
792 12 : }
793 2340256 : if (Scale < 0) {
794 : assert(size_t(-Scale) < sizeof(IntT) * 8);
795 2308026 : return N >> -Scale;
796 3 : }
797 : return N;
798 : }
799 :
800 : template <class DigitsT>
801 4102734 : ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
802 : operator*=(const ScaledNumber &X) {
803 4102734 : if (isZero())
804 : return *this;
805 4102734 : if (X.isZero())
806 0 : return *this = X;
807 :
808 : // Save the exponents.
809 4102734 : int32_t Scales = int32_t(Scale) + int32_t(X.Scale);
810 :
811 : // Get the raw product.
812 4102734 : *this = getProduct(Digits, X.Digits);
813 :
814 : // Combine with exponents.
815 4102734 : return *this <<= Scales;
816 : }
817 : template <class DigitsT>
818 2698430 : ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
819 : operator/=(const ScaledNumber &X) {
820 2698430 : if (isZero())
821 0 : return *this;
822 2698430 : if (X.isZero())
823 0 : return *this = getLargest();
824 :
825 : // Save the exponents.
826 2698430 : int32_t Scales = int32_t(Scale) - int32_t(X.Scale);
827 :
828 : // Get the raw quotient.
829 2698431 : *this = getQuotient(Digits, X.Digits);
830 :
831 : // Combine with exponents.
832 2698431 : return *this <<= Scales;
833 : }
834 8113481 : template <class DigitsT> void ScaledNumber<DigitsT>::shiftLeft(int32_t Shift) {
835 8113481 : if (!Shift || isZero())
836 : return;
837 : assert(Shift != INT32_MIN);
838 5707158 : if (Shift < 0) {
839 2777437 : shiftRight(-Shift);
840 2777437 : return;
841 : }
842 :
843 : // Shift as much as we can in the exponent.
844 2929721 : int32_t ScaleShift = std::min(Shift, ScaledNumbers::MaxScale - Scale);
845 2929721 : Scale += ScaleShift;
846 2929733 : if (ScaleShift == Shift)
847 : return;
848 :
849 : // Check this late, since it's rare.
850 0 : if (isLargest())
851 : return;
852 :
853 : // Shift the digits themselves.
854 0 : Shift -= ScaleShift;
855 0 : if (Shift > countLeadingZerosWidth(Digits)) {
856 : // Saturate.
857 0 : *this = getLargest();
858 0 : return;
859 : }
860 :
861 0 : Digits <<= Shift;
862 : }
863 :
864 2777437 : template <class DigitsT> void ScaledNumber<DigitsT>::shiftRight(int32_t Shift) {
865 2777437 : if (!Shift || isZero())
866 : return;
867 : assert(Shift != INT32_MIN);
868 2777437 : if (Shift < 0) {
869 0 : shiftLeft(-Shift);
870 0 : return;
871 : }
872 :
873 : // Shift as much as we can in the exponent.
874 2777437 : int32_t ScaleShift = std::min(Shift, Scale - ScaledNumbers::MinScale);
875 2777437 : Scale -= ScaleShift;
876 2777437 : if (ScaleShift == Shift)
877 : return;
878 :
879 : // Shift the digits themselves.
880 0 : Shift -= ScaleShift;
881 0 : if (Shift >= Width) {
882 : // Saturate.
883 0 : *this = getZero();
884 0 : return;
885 : }
886 :
887 0 : Digits >>= Shift;
888 0 : }
889 0 :
890 : template <typename T> struct isPodLike;
891 0 : template <typename T> struct isPodLike<ScaledNumber<T>> {
892 0 : static const bool value = true;
893 0 : };
894 :
895 0 : } // end namespace llvm
896 0 :
897 0 : #endif // LLVM_SUPPORT_SCALEDNUMBER_H
|
