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