1 //===- llvm/Support/ScaledNumber.h - Support for scaled numbers -*- C++ -*-===//
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 // 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
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.
20 //===----------------------------------------------------------------------===//
22 #ifndef LLVM_SUPPORT_SCALEDNUMBER_H
23 #define LLVM_SUPPORT_SCALEDNUMBER_H
25 #include "llvm/Support/MathExtras.h"
33 namespace ScaledNumbers {
35 /// \brief Maximum scale; same as APFloat for easy debug printing.
36 const int32_t MaxScale = 16383;
38 /// \brief Maximum scale; same as APFloat for easy debug printing.
39 const int32_t MinScale = -16382;
41 /// \brief Get the width of a number.
42 template <class DigitsT> inline int getWidth() { return sizeof(DigitsT) * 8; }
44 /// \brief Conditionally round up a scaled number.
46 /// Given \c Digits and \c Scale, round up iff \c ShouldRound is \c true.
47 /// Always returns \c Scale unless there's an overflow, in which case it
48 /// returns \c 1+Scale.
50 /// \pre adding 1 to \c Scale will not overflow INT16_MAX.
51 template <class DigitsT>
52 inline std::pair<DigitsT, int16_t> getRounded(DigitsT Digits, int16_t Scale,
54 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
59 return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1);
60 return std::make_pair(Digits, Scale);
63 /// \brief Convenience helper for 32-bit rounding.
64 inline std::pair<uint32_t, int16_t> getRounded32(uint32_t Digits, int16_t Scale,
66 return getRounded(Digits, Scale, ShouldRound);
69 /// \brief Convenience helper for 64-bit rounding.
70 inline std::pair<uint64_t, int16_t> getRounded64(uint64_t Digits, int16_t Scale,
72 return getRounded(Digits, Scale, ShouldRound);
75 /// \brief Adjust a 64-bit scaled number down to the appropriate width.
77 /// \pre Adding 64 to \c Scale will not overflow INT16_MAX.
78 template <class DigitsT>
79 inline std::pair<DigitsT, int16_t> getAdjusted(uint64_t Digits,
81 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
83 const int Width = getWidth<DigitsT>();
84 if (Width == 64 || Digits <= std::numeric_limits<DigitsT>::max())
85 return std::make_pair(Digits, Scale);
87 // Shift right and round.
88 int Shift = 64 - Width - countLeadingZeros(Digits);
89 return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
90 Digits & (UINT64_C(1) << (Shift - 1)));
93 /// \brief Convenience helper for adjusting to 32 bits.
94 inline std::pair<uint32_t, int16_t> getAdjusted32(uint64_t Digits,
96 return getAdjusted<uint32_t>(Digits, Scale);
99 /// \brief Convenience helper for adjusting to 64 bits.
100 inline std::pair<uint64_t, int16_t> getAdjusted64(uint64_t Digits,
102 return getAdjusted<uint64_t>(Digits, Scale);
105 /// \brief Multiply two 64-bit integers to create a 64-bit scaled number.
107 /// Implemented with four 64-bit integer multiplies.
108 std::pair<uint64_t, int16_t> multiply64(uint64_t LHS, uint64_t RHS);
110 /// \brief Multiply two 32-bit integers to create a 32-bit scaled number.
112 /// Implemented with one 64-bit integer multiply.
113 template <class DigitsT>
114 inline std::pair<DigitsT, int16_t> getProduct(DigitsT LHS, DigitsT RHS) {
115 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
117 if (getWidth<DigitsT>() <= 32 || (LHS <= UINT32_MAX && RHS <= UINT32_MAX))
118 return getAdjusted<DigitsT>(uint64_t(LHS) * RHS);
120 return multiply64(LHS, RHS);
123 /// \brief Convenience helper for 32-bit product.
124 inline std::pair<uint32_t, int16_t> getProduct32(uint32_t LHS, uint32_t RHS) {
125 return getProduct(LHS, RHS);
128 /// \brief Convenience helper for 64-bit product.
129 inline std::pair<uint64_t, int16_t> getProduct64(uint64_t LHS, uint64_t RHS) {
130 return getProduct(LHS, RHS);
133 /// \brief Divide two 64-bit integers to create a 64-bit scaled number.
135 /// Implemented with long division.
137 /// \pre \c Dividend and \c Divisor are non-zero.
138 std::pair<uint64_t, int16_t> divide64(uint64_t Dividend, uint64_t Divisor);
140 /// \brief Divide two 32-bit integers to create a 32-bit scaled number.
142 /// Implemented with one 64-bit integer divide/remainder pair.
144 /// \pre \c Dividend and \c Divisor are non-zero.
145 std::pair<uint32_t, int16_t> divide32(uint32_t Dividend, uint32_t Divisor);
147 /// \brief Divide two 32-bit numbers to create a 32-bit scaled number.
149 /// Implemented with one 64-bit integer divide/remainder pair.
151 /// Returns \c (DigitsT_MAX, INT16_MAX) for divide-by-zero (0 for 0/0).
152 template <class DigitsT>
153 std::pair<DigitsT, int16_t> getQuotient(DigitsT Dividend, DigitsT Divisor) {
154 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
155 static_assert(sizeof(DigitsT) == 4 || sizeof(DigitsT) == 8,
156 "expected 32-bit or 64-bit digits");
160 return std::make_pair(0, 0);
162 return std::make_pair(std::numeric_limits<DigitsT>::max(), INT16_MAX);
164 if (getWidth<DigitsT>() == 64)
165 return divide64(Dividend, Divisor);
166 return divide32(Dividend, Divisor);
169 /// \brief Convenience helper for 32-bit quotient.
170 inline std::pair<uint32_t, int16_t> getQuotient32(uint32_t Dividend,
172 return getQuotient(Dividend, Divisor);
175 /// \brief Convenience helper for 64-bit quotient.
176 inline std::pair<uint64_t, int16_t> getQuotient64(uint64_t Dividend,
178 return getQuotient(Dividend, Divisor);
181 /// \brief Implementation of getLg() and friends.
183 /// Returns the rounded lg of \c Digits*2^Scale and an int specifying whether
184 /// this was rounded up (1), down (-1), or exact (0).
186 /// Returns \c INT32_MIN when \c Digits is zero.
187 template <class DigitsT>
188 inline std::pair<int32_t, int> getLgImpl(DigitsT Digits, int16_t Scale) {
189 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
192 return std::make_pair(INT32_MIN, 0);
194 // Get the floor of the lg of Digits.
195 int32_t LocalFloor = sizeof(Digits) * 8 - countLeadingZeros(Digits) - 1;
197 // Get the actual floor.
198 int32_t Floor = Scale + LocalFloor;
199 if (Digits == UINT64_C(1) << LocalFloor)
200 return std::make_pair(Floor, 0);
202 // Round based on the next digit.
203 assert(LocalFloor >= 1);
204 bool Round = Digits & UINT64_C(1) << (LocalFloor - 1);
205 return std::make_pair(Floor + Round, Round ? 1 : -1);
208 /// \brief Get the lg (rounded) of a scaled number.
210 /// Get the lg of \c Digits*2^Scale.
212 /// Returns \c INT32_MIN when \c Digits is zero.
213 template <class DigitsT> int32_t getLg(DigitsT Digits, int16_t Scale) {
214 return getLgImpl(Digits, Scale).first;
217 /// \brief Get the lg floor of a scaled number.
219 /// Get the floor of the lg of \c Digits*2^Scale.
221 /// Returns \c INT32_MIN when \c Digits is zero.
222 template <class DigitsT> int32_t getLgFloor(DigitsT Digits, int16_t Scale) {
223 auto Lg = getLgImpl(Digits, Scale);
224 return Lg.first - (Lg.second > 0);
227 /// \brief Get the lg ceiling of a scaled number.
229 /// Get the ceiling of the lg of \c Digits*2^Scale.
231 /// Returns \c INT32_MIN when \c Digits is zero.
232 template <class DigitsT> int32_t getLgCeiling(DigitsT Digits, int16_t Scale) {
233 auto Lg = getLgImpl(Digits, Scale);
234 return Lg.first + (Lg.second < 0);
237 /// \brief Implementation for comparing scaled numbers.
239 /// Compare two 64-bit numbers with different scales. Given that the scale of
240 /// \c L is higher than that of \c R by \c ScaleDiff, compare them. Return -1,
241 /// 1, and 0 for less than, greater than, and equal, respectively.
243 /// \pre 0 <= ScaleDiff < 64.
244 int compareImpl(uint64_t L, uint64_t R, int ScaleDiff);
246 /// \brief Compare two scaled numbers.
248 /// Compare two scaled numbers. Returns 0 for equal, -1 for less than, and 1
249 /// for greater than.
250 template <class DigitsT>
251 int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale) {
252 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
256 return RDigits ? -1 : 0;
260 // Check for the scale. Use getLgFloor to be sure that the scale difference
261 // is always lower than 64.
262 int32_t lgL = getLgFloor(LDigits, LScale), lgR = getLgFloor(RDigits, RScale);
264 return lgL < lgR ? -1 : 1;
268 return compareImpl(LDigits, RDigits, RScale - LScale);
270 return -compareImpl(RDigits, LDigits, LScale - RScale);
273 /// \brief Match scales of two numbers.
275 /// Given two scaled numbers, match up their scales. Change the digits and
276 /// scales in place. Shift the digits as necessary to form equivalent numbers,
277 /// losing precision only when necessary.
279 /// If the output value of \c LDigits (\c RDigits) is \c 0, the output value of
280 /// \c LScale (\c RScale) is unspecified.
282 /// As a convenience, returns the matching scale. If the output value of one
283 /// number is zero, returns the scale of the other. If both are zero, which
284 /// scale is returned is unspecifed.
285 template <class DigitsT>
286 int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits,
288 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
292 return matchScales(RDigits, RScale, LDigits, LScale);
295 if (!RDigits || LScale == RScale)
298 // Now LScale > RScale. Get the difference.
299 int32_t ScaleDiff = int32_t(LScale) - RScale;
300 if (ScaleDiff >= 2 * getWidth<DigitsT>()) {
301 // Don't bother shifting. RDigits will get zero-ed out anyway.
306 // Shift LDigits left as much as possible, then shift RDigits right.
307 int32_t ShiftL = std::min<int32_t>(countLeadingZeros(LDigits), ScaleDiff);
308 assert(ShiftL < getWidth<DigitsT>() && "can't shift more than width");
310 int32_t ShiftR = ScaleDiff - ShiftL;
311 if (ShiftR >= getWidth<DigitsT>()) {
312 // Don't bother shifting. RDigits will get zero-ed out anyway.
322 assert(LScale == RScale && "scales should match");
326 /// \brief Get the sum of two scaled numbers.
328 /// Get the sum of two scaled numbers with as much precision as possible.
330 /// \pre Adding 1 to \c LScale (or \c RScale) will not overflow INT16_MAX.
331 template <class DigitsT>
332 std::pair<DigitsT, int16_t> getSum(DigitsT LDigits, int16_t LScale,
333 DigitsT RDigits, int16_t RScale) {
334 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
336 // Check inputs up front. This is only relevent if addition overflows, but
337 // testing here should catch more bugs.
338 assert(LScale < INT16_MAX && "scale too large");
339 assert(RScale < INT16_MAX && "scale too large");
341 // Normalize digits to match scales.
342 int16_t Scale = matchScales(LDigits, LScale, RDigits, RScale);
345 DigitsT Sum = LDigits + RDigits;
347 return std::make_pair(Sum, Scale);
349 // Adjust sum after arithmetic overflow.
350 DigitsT HighBit = DigitsT(1) << (getWidth<DigitsT>() - 1);
351 return std::make_pair(HighBit | Sum >> 1, Scale + 1);
354 /// \brief Convenience helper for 32-bit sum.
355 inline std::pair<uint32_t, int16_t> getSum32(uint32_t LDigits, int16_t LScale,
356 uint32_t RDigits, int16_t RScale) {
357 return getSum(LDigits, LScale, RDigits, RScale);
360 /// \brief Convenience helper for 64-bit sum.
361 inline std::pair<uint64_t, int16_t> getSum64(uint64_t LDigits, int16_t LScale,
362 uint64_t RDigits, int16_t RScale) {
363 return getSum(LDigits, LScale, RDigits, RScale);
366 /// \brief Get the difference of two scaled numbers.
368 /// Get LHS minus RHS with as much precision as possible.
370 /// Returns \c (0, 0) if the RHS is larger than the LHS.
371 template <class DigitsT>
372 std::pair<DigitsT, int16_t> getDifference(DigitsT LDigits, int16_t LScale,
373 DigitsT RDigits, int16_t RScale) {
374 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
376 // Normalize digits to match scales.
377 const DigitsT SavedRDigits = RDigits;
378 const int16_t SavedRScale = RScale;
379 matchScales(LDigits, LScale, RDigits, RScale);
381 // Compute difference.
382 if (LDigits <= RDigits)
383 return std::make_pair(0, 0);
384 if (RDigits || !SavedRDigits)
385 return std::make_pair(LDigits - RDigits, LScale);
387 // Check if RDigits just barely lost its last bit. E.g., for 32-bit:
389 // 1*2^32 - 1*2^0 == 0xffffffff != 1*2^32
390 const auto RLgFloor = getLgFloor(SavedRDigits, SavedRScale);
391 if (!compare(LDigits, LScale, DigitsT(1), RLgFloor + getWidth<DigitsT>()))
392 return std::make_pair(std::numeric_limits<DigitsT>::max(), RLgFloor);
394 return std::make_pair(LDigits, LScale);
397 /// \brief Convenience helper for 32-bit difference.
398 inline std::pair<uint32_t, int16_t> getDifference32(uint32_t LDigits,
402 return getDifference(LDigits, LScale, RDigits, RScale);
405 /// \brief Convenience helper for 64-bit difference.
406 inline std::pair<uint64_t, int16_t> getDifference64(uint64_t LDigits,
410 return getDifference(LDigits, LScale, RDigits, RScale);
413 } // end namespace ScaledNumbers
414 } // end namespace llvm