APFloat.cpp

Go to the documentation of this file.

//===-- APFloat.cpp - Implement APFloat class -----------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements a class to represent arbitrary precision floating
// point values and provide a variety of arithmetic operations on them.
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/Support/MathExtras.h"
#include <cstring>

using namespace llvm;

#define convolve(lhs, rhs) ((lhs) * 4 + (rhs))

/* Assumed in hexadecimal significand parsing, and conversion to
   hexadecimal strings.  */
#define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
COMPILE_TIME_ASSERT(integerPartWidth % 4 == 0);

namespace llvm {

  /* Represents floating point arithmetic semantics.  */
  struct fltSemantics {
    /* The largest E such that 2^E is representable; this matches the
       definition of IEEE 754.  */
    exponent_t maxExponent;

    /* The smallest E such that 2^E is a normalized number; this
       matches the definition of IEEE 754.  */
    exponent_t minExponent;

    /* Number of bits in the significand.  This includes the integer
       bit.  */
    unsigned int precision;

    /* True if arithmetic is supported.  */
    unsigned int arithmeticOK;
  };

  const fltSemantics APFloat::IEEEsingle = { 127, -126, 24, true };
  const fltSemantics APFloat::IEEEdouble = { 1023, -1022, 53, true };
  const fltSemantics APFloat::IEEEquad = { 16383, -16382, 113, true };
  const fltSemantics APFloat::x87DoubleExtended = { 16383, -16382, 64, true };
  const fltSemantics APFloat::Bogus = { 0, 0, 0, true };

  // The PowerPC format consists of two doubles.  It does not map cleanly
  // onto the usual format above.  For now only storage of constants of
  // this type is supported, no arithmetic.
  const fltSemantics APFloat::PPCDoubleDouble = { 1023, -1022, 106, false };

  /* A tight upper bound on number of parts required to hold the value
     pow(5, power) is

       power * 815 / (351 * integerPartWidth) + 1
       
     However, whilst the result may require only this many parts,
     because we are multiplying two values to get it, the
     multiplication may require an extra part with the excess part
     being zero (consider the trivial case of 1 * 1, tcFullMultiply
     requires two parts to hold the single-part result).  So we add an
     extra one to guarantee enough space whilst multiplying.  */
  const unsigned int maxExponent = 16383;
  const unsigned int maxPrecision = 113;
  const unsigned int maxPowerOfFiveExponent = maxExponent + maxPrecision - 1;
  const unsigned int maxPowerOfFiveParts = 2 + ((maxPowerOfFiveExponent * 815)
                                                / (351 * integerPartWidth));
}

/* Put a bunch of private, handy routines in an anonymous namespace.  */
namespace {

  static inline unsigned int
  partCountForBits(unsigned int bits)
  {
    return ((bits) + integerPartWidth - 1) / integerPartWidth;
  }

  /* Returns 0U-9U.  Return values >= 10U are not digits.  */
  static inline unsigned int
  decDigitValue(unsigned int c)
  {
    return c - '0';
  }

  static unsigned int
  hexDigitValue(unsigned int c)
  {
    unsigned int r;

    r = c - '0';
    if(r <= 9)
      return r;

    r = c - 'A';
    if(r <= 5)
      return r + 10;

    r = c - 'a';
    if(r <= 5)
      return r + 10;

    return -1U;
  }

  static inline void
  assertArithmeticOK(const llvm::fltSemantics &semantics) {
    assert(semantics.arithmeticOK
           && "Compile-time arithmetic does not support these semantics");
  }

  /* Return the value of a decimal exponent of the form
     [+-]ddddddd.

     If the exponent overflows, returns a large exponent with the
     appropriate sign.  */
  static int
  readExponent(const char *p)
  {
    bool isNegative;
    unsigned int absExponent;
    const unsigned int overlargeExponent = 24000;  /* FIXME.  */

    isNegative = (*p == '-');
    if (*p == '-' || *p == '+')
      p++;

    absExponent = decDigitValue(*p++);
    assert (absExponent < 10U);

    for (;;) {
      unsigned int value;

      value = decDigitValue(*p);
      if (value >= 10U)
        break;

      p++;
      value += absExponent * 10;
      if (absExponent >= overlargeExponent) {
        absExponent = overlargeExponent;
        break;
      }
      absExponent = value;
    }

    if (isNegative)
      return -(int) absExponent;
    else
      return (int) absExponent;
  }

  /* This is ugly and needs cleaning up, but I don't immediately see
     how whilst remaining safe.  */
  static int
  totalExponent(const char *p, int exponentAdjustment)
  {
    int unsignedExponent;
    bool negative, overflow;
    int exponent;

    /* Move past the exponent letter and sign to the digits.  */
    p++;
    negative = *p == '-';
    if(*p == '-' || *p == '+')
      p++;

    unsignedExponent = 0;
    overflow = false;
    for(;;) {
      unsigned int value;

      value = decDigitValue(*p);
      if(value >= 10U)
        break;

      p++;
      unsignedExponent = unsignedExponent * 10 + value;
      if(unsignedExponent > 65535)
        overflow = true;
    }

    if(exponentAdjustment > 65535 || exponentAdjustment < -65536)
      overflow = true;

    if(!overflow) {
      exponent = unsignedExponent;
      if(negative)
        exponent = -exponent;
      exponent += exponentAdjustment;
      if(exponent > 65535 || exponent < -65536)
        overflow = true;
    }

    if(overflow)
      exponent = negative ? -65536: 65535;

    return exponent;
  }

  static const char *
  skipLeadingZeroesAndAnyDot(const char *p, const char **dot)
  {
    *dot = 0;
    while(*p == '0')
      p++;

    if(*p == '.') {
      *dot = p++;
      while(*p == '0')
        p++;
    }

    return p;
  }

  /* Given a normal decimal floating point number of the form

       dddd.dddd[eE][+-]ddd

     where the decimal point and exponent are optional, fill out the
     structure D.  Exponent is appropriate if the significand is
     treated as an integer, and normalizedExponent if the significand
     is taken to have the decimal point after a single leading
     non-zero digit.

     If the value is zero, V->firstSigDigit points to a non-digit, and
     the return exponent is zero.
  */
  struct decimalInfo {
    const char *firstSigDigit;
    const char *lastSigDigit;
    int exponent;
    int normalizedExponent;
  };

  static void
  interpretDecimal(const char *p, decimalInfo *D)
  {
    const char *dot;

    p = skipLeadingZeroesAndAnyDot (p, &dot);

    D->firstSigDigit = p;
    D->exponent = 0;
    D->normalizedExponent = 0;

    for (;;) {
      if (*p == '.') {
        assert(dot == 0);
        dot = p++;
      }
      if (decDigitValue(*p) >= 10U)
        break;
      p++;
    }

    /* If number is all zerooes accept any exponent.  */
    if (p != D->firstSigDigit) {
      if (*p == 'e' || *p == 'E')
        D->exponent = readExponent(p + 1);

      /* Implied decimal point?  */
      if (!dot)
        dot = p;

      /* Drop insignificant trailing zeroes.  */
      do
        do
          p--;
        while (*p == '0');
      while (*p == '.');

      /* Adjust the exponents for any decimal point.  */
      D->exponent += static_cast<exponent_t>((dot - p) - (dot > p));
      D->normalizedExponent = (D->exponent +
                static_cast<exponent_t>((p - D->firstSigDigit)
                                        - (dot > D->firstSigDigit && dot < p)));
    }

    D->lastSigDigit = p;
  }

  /* Return the trailing fraction of a hexadecimal number.
     DIGITVALUE is the first hex digit of the fraction, P points to
     the next digit.  */
  static lostFraction
  trailingHexadecimalFraction(const char *p, unsigned int digitValue)
  {
    unsigned int hexDigit;

    /* If the first trailing digit isn't 0 or 8 we can work out the
       fraction immediately.  */
    if(digitValue > 8)
      return lfMoreThanHalf;
    else if(digitValue < 8 && digitValue > 0)
      return lfLessThanHalf;

    /* Otherwise we need to find the first non-zero digit.  */
    while(*p == '0')
      p++;

    hexDigit = hexDigitValue(*p);

    /* If we ran off the end it is exactly zero or one-half, otherwise
       a little more.  */
    if(hexDigit == -1U)
      return digitValue == 0 ? lfExactlyZero: lfExactlyHalf;
    else
      return digitValue == 0 ? lfLessThanHalf: lfMoreThanHalf;
  }

  /* Return the fraction lost were a bignum truncated losing the least
     significant BITS bits.  */
  static lostFraction
  lostFractionThroughTruncation(const integerPart *parts,
                                unsigned int partCount,
                                unsigned int bits)
  {
    unsigned int lsb;

    lsb = APInt::tcLSB(parts, partCount);

    /* Note this is guaranteed true if bits == 0, or LSB == -1U.  */
    if(bits <= lsb)
      return lfExactlyZero;
    if(bits == lsb + 1)
      return lfExactlyHalf;
    if(bits <= partCount * integerPartWidth
       && APInt::tcExtractBit(parts, bits - 1))
      return lfMoreThanHalf;

    return lfLessThanHalf;
  }

  /* Shift DST right BITS bits noting lost fraction.  */
  static lostFraction
  shiftRight(integerPart *dst, unsigned int parts, unsigned int bits)
  {
    lostFraction lost_fraction;

    lost_fraction = lostFractionThroughTruncation(dst, parts, bits);

    APInt::tcShiftRight(dst, parts, bits);

    return lost_fraction;
  }

  /* Combine the effect of two lost fractions.  */
  static lostFraction
  combineLostFractions(lostFraction moreSignificant,
                       lostFraction lessSignificant)
  {
    if(lessSignificant != lfExactlyZero) {
      if(moreSignificant == lfExactlyZero)
        moreSignificant = lfLessThanHalf;
      else if(moreSignificant == lfExactlyHalf)
        moreSignificant = lfMoreThanHalf;
    }

    return moreSignificant;
  }

  /* The error from the true value, in half-ulps, on multiplying two
     floating point numbers, which differ from the value they
     approximate by at most HUE1 and HUE2 half-ulps, is strictly less
     than the returned value.

     See "How to Read Floating Point Numbers Accurately" by William D
     Clinger.  */
  static unsigned int
  HUerrBound(bool inexactMultiply, unsigned int HUerr1, unsigned int HUerr2)
  {
    assert(HUerr1 < 2 || HUerr2 < 2 || (HUerr1 + HUerr2 < 8));

    if (HUerr1 + HUerr2 == 0)
      return inexactMultiply * 2;  /* <= inexactMultiply half-ulps.  */
    else
      return inexactMultiply + 2 * (HUerr1 + HUerr2);
  }

  /* The number of ulps from the boundary (zero, or half if ISNEAREST)
     when the least significant BITS are truncated.  BITS cannot be
     zero.  */
  static integerPart
  ulpsFromBoundary(const integerPart *parts, unsigned int bits, bool isNearest)
  {
    unsigned int count, partBits;
    integerPart part, boundary;

    assert (bits != 0);

    bits--;
    count = bits / integerPartWidth;
    partBits = bits % integerPartWidth + 1;

    part = parts[count] & (~(integerPart) 0 >> (integerPartWidth - partBits));

    if (isNearest)
      boundary = (integerPart) 1 << (partBits - 1);
    else
      boundary = 0;

    if (count == 0) {
      if (part - boundary <= boundary - part)
        return part - boundary;
      else
        return boundary - part;
    }

    if (part == boundary) {
      while (--count)
        if (parts[count])
          return ~(integerPart) 0; /* A lot.  */

      return parts[0];
    } else if (part == boundary - 1) {
      while (--count)
        if (~parts[count])
          return ~(integerPart) 0; /* A lot.  */

      return -parts[0];
    }

    return ~(integerPart) 0; /* A lot.  */
  }

  /* Place pow(5, power) in DST, and return the number of parts used.
     DST must be at least one part larger than size of the answer.  */
  static unsigned int
  powerOf5(integerPart *dst, unsigned int power)
  {
    static const integerPart firstEightPowers[] = { 1, 5, 25, 125, 625, 3125,
                                                    15625, 78125 };
    static integerPart pow5s[maxPowerOfFiveParts * 2 + 5] = { 78125 * 5 };
    static unsigned int partsCount[16] = { 1 };

    integerPart scratch[maxPowerOfFiveParts], *p1, *p2, *pow5;
    unsigned int result;

    assert(power <= maxExponent);

    p1 = dst;
    p2 = scratch;

    *p1 = firstEightPowers[power & 7];
    power >>= 3;

    result = 1;
    pow5 = pow5s;

    for (unsigned int n = 0; power; power >>= 1, n++) {
      unsigned int pc;

      pc = partsCount[n];

      /* Calculate pow(5,pow(2,n+3)) if we haven't yet.  */
      if (pc == 0) {
        pc = partsCount[n - 1];
        APInt::tcFullMultiply(pow5, pow5 - pc, pow5 - pc, pc, pc);
        pc *= 2;
        if (pow5[pc - 1] == 0)
          pc--;
        partsCount[n] = pc;
      }

      if (power & 1) {
        integerPart *tmp;

        APInt::tcFullMultiply(p2, p1, pow5, result, pc);
        result += pc;
        if (p2[result - 1] == 0)
          result--;

        /* Now result is in p1 with partsCount parts and p2 is scratch
           space.  */
        tmp = p1, p1 = p2, p2 = tmp;
      }

      pow5 += pc;
    }

    if (p1 != dst)
      APInt::tcAssign(dst, p1, result);

    return result;
  }

  /* Zero at the end to avoid modular arithmetic when adding one; used
     when rounding up during hexadecimal output.  */
  static const char hexDigitsLower[] = "0123456789abcdef0";
  static const char hexDigitsUpper[] = "0123456789ABCDEF0";
  static const char infinityL[] = "infinity";
  static const char infinityU[] = "INFINITY";
  static const char NaNL[] = "nan";
  static const char NaNU[] = "NAN";

  /* Write out an integerPart in hexadecimal, starting with the most
     significant nibble.  Write out exactly COUNT hexdigits, return
     COUNT.  */
  static unsigned int
  partAsHex (char *dst, integerPart part, unsigned int count,
             const char *hexDigitChars)
  {
    unsigned int result = count;

    assert (count != 0 && count <= integerPartWidth / 4);

    part >>= (integerPartWidth - 4 * count);
    while (count--) {
      dst[count] = hexDigitChars[part & 0xf];
      part >>= 4;
    }

    return result;
  }

  /* Write out an unsigned decimal integer.  */
  static char *
  writeUnsignedDecimal (char *dst, unsigned int n)
  {
    char buff[40], *p;

    p = buff;
    do
      *p++ = '0' + n % 10;
    while (n /= 10);

    do
      *dst++ = *--p;
    while (p != buff);

    return dst;
  }

  /* Write out a signed decimal integer.  */
  static char *
  writeSignedDecimal (char *dst, int value)
  {
    if (value < 0) {
      *dst++ = '-';
      dst = writeUnsignedDecimal(dst, -(unsigned) value);
    } else
      dst = writeUnsignedDecimal(dst, value);

    return dst;
  }
}

/* Constructors.  */
void
APFloat::initialize(const fltSemantics *ourSemantics)
{
  unsigned int count;

  semantics = ourSemantics;
  count = partCount();
  if(count > 1)
    significand.parts = new integerPart[count];
}

void
APFloat::freeSignificand()
{
  if(partCount() > 1)
    delete [] significand.parts;
}

void
APFloat::assign(const APFloat &rhs)
{
  assert(semantics == rhs.semantics);

  sign = rhs.sign;
  category = rhs.category;
  exponent = rhs.exponent;
  sign2 = rhs.sign2;
  exponent2 = rhs.exponent2;
  if(category == fcNormal || category == fcNaN)
    copySignificand(rhs);
}

void
APFloat::copySignificand(const APFloat &rhs)
{
  assert(category == fcNormal || category == fcNaN);
  assert(rhs.partCount() >= partCount());

  APInt::tcAssign(significandParts(), rhs.significandParts(),
                  partCount());
}

/* Make this number a NaN, with an arbitrary but deterministic value
   for the significand.  */
void
APFloat::makeNaN(void)
{
  category = fcNaN;
  APInt::tcSet(significandParts(), ~0U, partCount());
}

APFloat &
APFloat::operator=(const APFloat &rhs)
{
  if(this != &rhs) {
    if(semantics != rhs.semantics) {
      freeSignificand();
      initialize(rhs.semantics);
    }
    assign(rhs);
  }

  return *this;
}

bool
APFloat::bitwiseIsEqual(const APFloat &rhs) const {
  if (this == &rhs)
    return true;
  if (semantics != rhs.semantics ||
      category != rhs.category ||
      sign != rhs.sign)
    return false;
  if (semantics==(const llvm::fltSemantics*)&PPCDoubleDouble &&
      sign2 != rhs.sign2)
    return false;
  if (category==fcZero || category==fcInfinity)
    return true;
  else if (category==fcNormal && exponent!=rhs.exponent)
    return false;
  else if (semantics==(const llvm::fltSemantics*)&PPCDoubleDouble &&
           exponent2!=rhs.exponent2)
    return false;
  else {
    int i= partCount();
    const integerPart* p=significandParts();
    const integerPart* q=rhs.significandParts();
    for (; i>0; i--, p++, q++) {
      if (*p != *q)
        return false;
    }
    return true;
  }
}

APFloat::APFloat(const fltSemantics &ourSemantics, integerPart value)
{
  assertArithmeticOK(ourSemantics);
  initialize(&ourSemantics);
  sign = 0;
  zeroSignificand();
  exponent = ourSemantics.precision - 1;
  significandParts()[0] = value;
  normalize(rmNearestTiesToEven, lfExactlyZero);
}

APFloat::APFloat(const fltSemantics &ourSemantics,
                 fltCategory ourCategory, bool negative)
{
  assertArithmeticOK(ourSemantics);
  initialize(&ourSemantics);
  category = ourCategory;
  sign = negative;
  if(category == fcNormal)
    category = fcZero;
  else if (ourCategory == fcNaN)
    makeNaN();
}

APFloat::APFloat(const fltSemantics &ourSemantics, const char *text)
{
  assertArithmeticOK(ourSemantics);
  initialize(&ourSemantics);
  convertFromString(text, rmNearestTiesToEven);
}

APFloat::APFloat(const APFloat &rhs)
{
  initialize(rhs.semantics);
  assign(rhs);
}

APFloat::~APFloat()
{
  freeSignificand();
}

// Profile - This method 'profiles' an APFloat for use with FoldingSet.
void APFloat::Profile(FoldingSetNodeID& ID) const {
  ID.Add(bitcastToAPInt());
}

unsigned int
APFloat::partCount() const
{
  return partCountForBits(semantics->precision + 1);
}

unsigned int
APFloat::semanticsPrecision(const fltSemantics &semantics)
{
  return semantics.precision;
}

const integerPart *
APFloat::significandParts() const
{
  return const_cast<APFloat *>(this)->significandParts();
}

integerPart *
APFloat::significandParts()
{
  assert(category == fcNormal || category == fcNaN);

  if(partCount() > 1)
    return significand.parts;
  else
    return &significand.part;
}

void
APFloat::zeroSignificand()
{
  category = fcNormal;
  APInt::tcSet(significandParts(), 0, partCount());
}

/* Increment an fcNormal floating point number's significand.  */
void
APFloat::incrementSignificand()
{
  integerPart carry;

  carry = APInt::tcIncrement(significandParts(), partCount());

  /* Our callers should never cause us to overflow.  */
  assert(carry == 0);
}

/* Add the significand of the RHS.  Returns the carry flag.  */
integerPart
APFloat::addSignificand(const APFloat &rhs)
{
  integerPart *parts;

  parts = significandParts();

  assert(semantics == rhs.semantics);
  assert(exponent == rhs.exponent);

  return APInt::tcAdd(parts, rhs.significandParts(), 0, partCount());
}

/* Subtract the significand of the RHS with a borrow flag.  Returns
   the borrow flag.  */
integerPart
APFloat::subtractSignificand(const APFloat &rhs, integerPart borrow)
{
  integerPart *parts;

  parts = significandParts();

  assert(semantics == rhs.semantics);
  assert(exponent == rhs.exponent);

  return APInt::tcSubtract(parts, rhs.significandParts(), borrow,
                           partCount());
}

/* Multiply the significand of the RHS.  If ADDEND is non-NULL, add it
   on to the full-precision result of the multiplication.  Returns the
   lost fraction.  */
lostFraction
APFloat::multiplySignificand(const APFloat &rhs, const APFloat *addend)
{
  unsigned int omsb;        // One, not zero, based MSB.
  unsigned int partsCount, newPartsCount, precision;
  integerPart *lhsSignificand;
  integerPart scratch[4];
  integerPart *fullSignificand;
  lostFraction lost_fraction;
  bool ignored;

  assert(semantics == rhs.semantics);

  precision = semantics->precision;
  newPartsCount = partCountForBits(precision * 2);

  if(newPartsCount > 4)
    fullSignificand = new integerPart[newPartsCount];
  else
    fullSignificand = scratch;

  lhsSignificand = significandParts();
  partsCount = partCount();

  APInt::tcFullMultiply(fullSignificand, lhsSignificand,
                        rhs.significandParts(), partsCount, partsCount);

  lost_fraction = lfExactlyZero;
  omsb = APInt::tcMSB(fullSignificand, newPartsCount) + 1;
  exponent += rhs.exponent;

  if(addend) {
    Significand savedSignificand = significand;
    const fltSemantics *savedSemantics = semantics;
    fltSemantics extendedSemantics;
    opStatus status;
    unsigned int extendedPrecision;

    /* Normalize our MSB.  */
    extendedPrecision = precision + precision - 1;
    if(omsb != extendedPrecision)
      {
        APInt::tcShiftLeft(fullSignificand, newPartsCount,
                           extendedPrecision - omsb);
        exponent -= extendedPrecision - omsb;
      }

    /* Create new semantics.  */
    extendedSemantics = *semantics;
    extendedSemantics.precision = extendedPrecision;

    if(newPartsCount == 1)
      significand.part = fullSignificand[0];
    else
      significand.parts = fullSignificand;
    semantics = &extendedSemantics;

    APFloat extendedAddend(*addend);
    status = extendedAddend.convert(extendedSemantics, rmTowardZero, &ignored);
    assert(status == opOK);
    lost_fraction = addOrSubtractSignificand(extendedAddend, false);

    /* Restore our state.  */
    if(newPartsCount == 1)
      fullSignificand[0] = significand.part;
    significand = savedSignificand;
    semantics = savedSemantics;

    omsb = APInt::tcMSB(fullSignificand, newPartsCount) + 1;
  }

  exponent -= (precision - 1);

  if(omsb > precision) {
    unsigned int bits, significantParts;
    lostFraction lf;

    bits = omsb - precision;
    significantParts = partCountForBits(omsb);
    lf = shiftRight(fullSignificand, significantParts, bits);
    lost_fraction = combineLostFractions(lf, lost_fraction);
    exponent += bits;
  }

  APInt::tcAssign(lhsSignificand, fullSignificand, partsCount);

  if(newPartsCount > 4)
    delete [] fullSignificand;

  return lost_fraction;
}

/* Multiply the significands of LHS and RHS to DST.  */
lostFraction
APFloat::divideSignificand(const APFloat &rhs)
{
  unsigned int bit, i, partsCount;
  const integerPart *rhsSignificand;
  integerPart *lhsSignificand, *dividend, *divisor;
  integerPart scratch[4];
  lostFraction lost_fraction;

  assert(semantics == rhs.semantics);

  lhsSignificand = significandParts();
  rhsSignificand = rhs.significandParts();
  partsCount = partCount();

  if(partsCount > 2)
    dividend = new integerPart[partsCount * 2];
  else
    dividend = scratch;

  divisor = dividend + partsCount;

  /* Copy the dividend and divisor as they will be modified in-place.  */
  for(i = 0; i < partsCount; i++) {
    dividend[i] = lhsSignificand[i];
    divisor[i] = rhsSignificand[i];
    lhsSignificand[i] = 0;
  }

  exponent -= rhs.exponent;

  unsigned int precision = semantics->precision;

  /* Normalize the divisor.  */
  bit = precision - APInt::tcMSB(divisor, partsCount) - 1;
  if(bit) {
    exponent += bit;
    APInt::tcShiftLeft(divisor, partsCount, bit);
  }

  /* Normalize the dividend.  */
  bit = precision - APInt::tcMSB(dividend, partsCount) - 1;
  if(bit) {
    exponent -= bit;
    APInt::tcShiftLeft(dividend, partsCount, bit);
  }

  /* Ensure the dividend >= divisor initially for the loop below.
     Incidentally, this means that the division loop below is
     guaranteed to set the integer bit to one.  */
  if(APInt::tcCompare(dividend, divisor, partsCount) < 0) {
    exponent--;
    APInt::tcShiftLeft(dividend, partsCount, 1);
    assert(APInt::tcCompare(dividend, divisor, partsCount) >= 0);
  }

  /* Long division.  */
  for(bit = precision; bit; bit -= 1) {
    if(APInt::tcCompare(dividend, divisor, partsCount) >= 0) {
      APInt::tcSubtract(dividend, divisor, 0, partsCount);
      APInt::tcSetBit(lhsSignificand, bit - 1);
    }

    APInt::tcShiftLeft(dividend, partsCount, 1);
  }

  /* Figure out the lost fraction.  */
  int cmp = APInt::tcCompare(dividend, divisor, partsCount);

  if(cmp > 0)
    lost_fraction = lfMoreThanHalf;
  else if(cmp == 0)
    lost_fraction = lfExactlyHalf;
  else if(APInt::tcIsZero(dividend, partsCount))
    lost_fraction = lfExactlyZero;
  else
    lost_fraction = lfLessThanHalf;

  if(partsCount > 2)
    delete [] dividend;

  return lost_fraction;
}

unsigned int
APFloat::significandMSB() const
{
  return APInt::tcMSB(significandParts(), partCount());
}

unsigned int
APFloat::significandLSB() const
{
  return APInt::tcLSB(significandParts(), partCount());
}

/* Note that a zero result is NOT normalized to fcZero.  */
lostFraction
APFloat::shiftSignificandRight(unsigned int bits)
{
  /* Our exponent should not overflow.  */
  assert((exponent_t) (exponent + bits) >= exponent);

  exponent += bits;

  return shiftRight(significandParts(), partCount(), bits);
}

/* Shift the significand left BITS bits, subtract BITS from its exponent.  */
void
APFloat::shiftSignificandLeft(unsigned int bits)
{
  assert(bits < semantics->precision);

  if(bits) {
    unsigned int partsCount = partCount();

    APInt::tcShiftLeft(significandParts(), partsCount, bits);
    exponent -= bits;

    assert(!APInt::tcIsZero(significandParts(), partsCount));
  }
}

APFloat::cmpResult
APFloat::compareAbsoluteValue(const APFloat &rhs) const
{
  int compare;

  assert(semantics == rhs.semantics);
  assert(category == fcNormal);
  assert(rhs.category == fcNormal);

  compare = exponent - rhs.exponent;

  /* If exponents are equal, do an unsigned bignum comparison of the
     significands.  */
  if(compare == 0)
    compare = APInt::tcCompare(significandParts(), rhs.significandParts(),
                               partCount());

  if(compare > 0)
    return cmpGreaterThan;
  else if(compare < 0)
    return cmpLessThan;
  else
    return cmpEqual;
}

/* Handle overflow.  Sign is preserved.  We either become infinity or
   the largest finite number.  */
APFloat::opStatus
APFloat::handleOverflow(roundingMode rounding_mode)
{
  /* Infinity?  */
  if(rounding_mode == rmNearestTiesToEven
     || rounding_mode == rmNearestTiesToAway
     || (rounding_mode == rmTowardPositive && !sign)
     || (rounding_mode == rmTowardNegative && sign))
    {
      category = fcInfinity;
      return (opStatus) (opOverflow | opInexact);
    }

  /* Otherwise we become the largest finite number.  */
  category = fcNormal;
  exponent = semantics->maxExponent;
  APInt::tcSetLeastSignificantBits(significandParts(), partCount(),
                                   semantics->precision);

  return opInexact;
}

/* Returns TRUE if, when truncating the current number, with BIT the
   new LSB, with the given lost fraction and rounding mode, the result
   would need to be rounded away from zero (i.e., by increasing the
   signficand).  This routine must work for fcZero of both signs, and
   fcNormal numbers.  */
bool
APFloat::roundAwayFromZero(roundingMode rounding_mode,
                           lostFraction lost_fraction,
                           unsigned int bit) const
{
  /* NaNs and infinities should not have lost fractions.  */
  assert(category == fcNormal || category == fcZero);

  /* Current callers never pass this so we don't handle it.  */
  assert(lost_fraction != lfExactlyZero);

  switch(rounding_mode) {
  default:
    assert(0);

  case rmNearestTiesToAway:
    return lost_fraction == lfExactlyHalf || lost_fraction == lfMoreThanHalf;

  case rmNearestTiesToEven:
    if(lost_fraction == lfMoreThanHalf)
      return true;

    /* Our zeroes don't have a significand to test.  */
    if(lost_fraction == lfExactlyHalf && category != fcZero)
      return APInt::tcExtractBit(significandParts(), bit);

    return false;

  case rmTowardZero:
    return false;

  case rmTowardPositive:
    return sign == false;

  case rmTowardNegative:
    return sign == true;
  }
}

APFloat::opStatus
APFloat::normalize(roundingMode rounding_mode,
                   lostFraction lost_fraction)
{
  unsigned int omsb;                /* One, not zero, based MSB.  */
  int exponentChange;

  if(category != fcNormal)
    return opOK;

  /* Before rounding normalize the exponent of fcNormal numbers.  */
  omsb = significandMSB() + 1;

  if(omsb) {
    /* OMSB is numbered from 1.  We want to place it in the integer
       bit numbered PRECISON if possible, with a compensating change in
       the exponent.  */
    exponentChange = omsb - semantics->precision;

    /* If the resulting exponent is too high, overflow according to
       the rounding mode.  */
    if(exponent + exponentChange > semantics->maxExponent)
      return handleOverflow(rounding_mode);

    /* Subnormal numbers have exponent minExponent, and their MSB
       is forced based on that.  */
    if(exponent + exponentChange < semantics->minExponent)
      exponentChange = semantics->minExponent - exponent;

    /* Shifting left is easy as we don't lose precision.  */
    if(exponentChange < 0) {
      assert(lost_fraction == lfExactlyZero);

      shiftSignificandLeft(-exponentChange);

      return opOK;
    }

    if(exponentChange > 0) {
      lostFraction lf;

      /* Shift right and capture any new lost fraction.  */
      lf = shiftSignificandRight(exponentChange);

      lost_fraction = combineLostFractions(lf, lost_fraction);

      /* Keep OMSB up-to-date.  */
      if(omsb > (unsigned) exponentChange)
        omsb -= exponentChange;
      else
        omsb = 0;
    }
  }

  /* Now round the number according to rounding_mode given the lost
     fraction.  */

  /* As specified in IEEE 754, since we do not trap we do not report
     underflow for exact results.  */
  if(lost_fraction == lfExactlyZero) {
    /* Canonicalize zeroes.  */
    if(omsb == 0)
      category = fcZero;

    return opOK;
  }

  /* Increment the significand if we're rounding away from zero.  */
  if(roundAwayFromZero(rounding_mode, lost_fraction, 0)) {
    if(omsb == 0)
      exponent = semantics->minExponent;

    incrementSignificand();
    omsb = significandMSB() + 1;

    /* Did the significand increment overflow?  */
    if(omsb == (unsigned) semantics->precision + 1) {
      /* Renormalize by incrementing the exponent and shifting our
         significand right one.  However if we already have the
         maximum exponent we overflow to infinity.  */
      if(exponent == semantics->maxExponent) {
        category = fcInfinity;

        return (opStatus) (opOverflow | opInexact);
      }

      shiftSignificandRight(1);

      return opInexact;
    }
  }

  /* The normal case - we were and are not denormal, and any
     significand increment above didn't overflow.  */
  if(omsb == semantics->precision)
    return opInexact;

  /* We have a non-zero denormal.  */
  assert(omsb < semantics->precision);

  /* Canonicalize zeroes.  */
  if(omsb == 0)
    category = fcZero;

  /* The fcZero case is a denormal that underflowed to zero.  */
  return (opStatus) (opUnderflow | opInexact);
}

APFloat::opStatus
APFloat::addOrSubtractSpecials(const APFloat &rhs, bool subtract)
{
  switch(convolve(category, rhs.category)) {
  default:
    assert(0);

  case convolve(fcNaN, fcZero):
  case convolve(fcNaN, fcNormal):
  case convolve(fcNaN, fcInfinity):
  case convolve(fcNaN, fcNaN):
  case convolve(fcNormal, fcZero):
  case convolve(fcInfinity, fcNormal):
  case convolve(fcInfinity, fcZero):
    return opOK;

  case convolve(fcZero, fcNaN):
  case convolve(fcNormal, fcNaN):
  case convolve(fcInfinity,