lib/Support/APFloat.cpp

   1 //===-- APFloat.cpp - Implement APFloat class -----------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a class to represent arbitrary precision floating
  11 // point values and provide a variety of arithmetic operations on them.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/ADT/APFloat.h"
  16 #include "llvm/ADT/APSInt.h"
  17 #include "llvm/ADT/FoldingSet.h"
  18 #include "llvm/ADT/Hashing.h"
  19 #include "llvm/ADT/StringExtras.h"
  20 #include "llvm/ADT/StringRef.h"
  21 #include "llvm/Support/ErrorHandling.h"
  22 #include "llvm/Support/MathExtras.h"
  23 #include <cstring>
  24 #include <limits.h>
  25
  26 using namespace llvm;
  27
  28 /// A macro used to combine two fcCategory enums into one key which can be used
  29 /// in a switch statement to classify how the interaction of two APFloat's
  30 /// categories affects an operation.
  31 ///
  32 /// TODO: If clang source code is ever allowed to use constexpr in its own
  33 /// codebase, change this into a static inline function.
  34 #define PackCategoriesIntoKey(_lhs, _rhs) ((_lhs) * 4 + (_rhs))
  35
  36 /* Assumed in hexadecimal significand parsing, and conversion to
  37    hexadecimal strings.  */
  38 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
  39 COMPILE_TIME_ASSERT(integerPartWidth % 4 == 0);
  40
  41 namespace llvm {
  42
  43   /* Represents floating point arithmetic semantics.  */
  44   struct fltSemantics {
  45     /* The largest E such that 2^E is representable; this matches the
  46        definition of IEEE 754.  */
  47     APFloat::ExponentType maxExponent;
  48
  49     /* The smallest E such that 2^E is a normalized number; this
  50        matches the definition of IEEE 754.  */
  51     APFloat::ExponentType minExponent;
  52
  53     /* Number of bits in the significand.  This includes the integer
  54        bit.  */
  55     unsigned int precision;
  56   };
  57
  58   const fltSemantics APFloat::IEEEhalf = { 15, -14, 11 };
  59   const fltSemantics APFloat::IEEEsingle = { 127, -126, 24 };
  60   const fltSemantics APFloat::IEEEdouble = { 1023, -1022, 53 };
  61   const fltSemantics APFloat::IEEEquad = { 16383, -16382, 113 };
  62   const fltSemantics APFloat::x87DoubleExtended = { 16383, -16382, 64 };
  63   const fltSemantics APFloat::Bogus = { 0, 0, 0 };
  64
  65   /* The PowerPC format consists of two doubles.  It does not map cleanly
  66      onto the usual format above.  It is approximated using twice the
  67      mantissa bits.  Note that for exponents near the double minimum,
  68      we no longer can represent the full 106 mantissa bits, so those
  69      will be treated as denormal numbers.
  70
  71      FIXME: While this approximation is equivalent to what GCC uses for
  72      compile-time arithmetic on PPC double-double numbers, it is not able
  73      to represent all possible values held by a PPC double-double number,
  74      for example: (long double) 1.0 + (long double) 0x1p-106
  75      Should this be replaced by a full emulation of PPC double-double?  */
  76   const fltSemantics APFloat::PPCDoubleDouble = { 1023, -1022 + 53, 53 + 53 };
  77
  78   /* A tight upper bound on number of parts required to hold the value
  79      pow(5, power) is
  80
  81        power * 815 / (351 * integerPartWidth) + 1
  82
  83      However, whilst the result may require only this many parts,
  84      because we are multiplying two values to get it, the
  85      multiplication may require an extra part with the excess part
  86      being zero (consider the trivial case of 1 * 1, tcFullMultiply
  87      requires two parts to hold the single-part result).  So we add an
  88      extra one to guarantee enough space whilst multiplying.  */
  89   const unsigned int maxExponent = 16383;
  90   const unsigned int maxPrecision = 113;
  91   const unsigned int maxPowerOfFiveExponent = maxExponent + maxPrecision - 1;
  92   const unsigned int maxPowerOfFiveParts = 2 + ((maxPowerOfFiveExponent * 815)
  93                                                 / (351 * integerPartWidth));
  94 }
  95
  96 /* A bunch of private, handy routines.  */
  97
  98 static inline unsigned int
  99 partCountForBits(unsigned int bits)
 100 {
 101   return ((bits) + integerPartWidth - 1) / integerPartWidth;
 102 }
 103
 104 /* Returns 0U-9U.  Return values >= 10U are not digits.  */
 105 static inline unsigned int
 106 decDigitValue(unsigned int c)
 107 {
 108   return c - '0';
 109 }
 110
 111 /* Return the value of a decimal exponent of the form
 112    [+-]ddddddd.
 113
 114    If the exponent overflows, returns a large exponent with the
 115    appropriate sign.  */
 116 static int
 117 readExponent(StringRef::iterator begin, StringRef::iterator end)
 118 {
 119   bool isNegative;
 120   unsigned int absExponent;
 121   const unsigned int overlargeExponent = 24000;  /* FIXME.  */
 122   StringRef::iterator p = begin;
 123
 124   assert(p != end && "Exponent has no digits");
 125
 126   isNegative = (*p == '-');
 127   if (*p == '-' || *p == '+') {
 128     p++;
 129     assert(p != end && "Exponent has no digits");
 130   }
 131
 132   absExponent = decDigitValue(*p++);
 133   assert(absExponent < 10U && "Invalid character in exponent");
 134
 135   for (; p != end; ++p) {
 136     unsigned int value;
 137
 138     value = decDigitValue(*p);
 139     assert(value < 10U && "Invalid character in exponent");
 140
 141     value += absExponent * 10;
 142     if (absExponent >= overlargeExponent) {
 143       absExponent = overlargeExponent;
 144       p = end;  /* outwit assert below */
 145       break;
 146     }
 147     absExponent = value;
 148   }
 149
 150   assert(p == end && "Invalid exponent in exponent");
 151
 152   if (isNegative)
 153     return -(int) absExponent;
 154   else
 155     return (int) absExponent;
 156 }
 157
 158 /* This is ugly and needs cleaning up, but I don't immediately see
 159    how whilst remaining safe.  */
 160 static int
 161 totalExponent(StringRef::iterator p, StringRef::iterator end,
 162               int exponentAdjustment)
 163 {
 164   int unsignedExponent;
 165   bool negative, overflow;
 166   int exponent = 0;
 167
 168   assert(p != end && "Exponent has no digits");
 169
 170   negative = *p == '-';
 171   if (*p == '-' || *p == '+') {
 172     p++;
 173     assert(p != end && "Exponent has no digits");
 174   }
 175
 176   unsignedExponent = 0;
 177   overflow = false;
 178   for (; p != end; ++p) {
 179     unsigned int value;
 180
 181     value = decDigitValue(*p);
 182     assert(value < 10U && "Invalid character in exponent");
 183
 184     unsignedExponent = unsignedExponent * 10 + value;
 185     if (unsignedExponent > 32767) {
 186       overflow = true;
 187       break;
 188     }
 189   }
 190
 191   if (exponentAdjustment > 32767 || exponentAdjustment < -32768)
 192     overflow = true;
 193
 194   if (!overflow) {
 195     exponent = unsignedExponent;
 196     if (negative)
 197       exponent = -exponent;
 198     exponent += exponentAdjustment;
 199     if (exponent > 32767 || exponent < -32768)
 200       overflow = true;
 201   }
 202
 203   if (overflow)
 204     exponent = negative ? -32768: 32767;
 205
 206   return exponent;
 207 }
 208
 209 static StringRef::iterator
 210 skipLeadingZeroesAndAnyDot(StringRef::iterator begin, StringRef::iterator end,
 211                            StringRef::iterator *dot)
 212 {
 213   StringRef::iterator p = begin;
 214   *dot = end;
 215   while (p != end && *p == '0')
 216     p++;
 217
 218   if (p != end && *p == '.') {
 219     *dot = p++;
 220
 221     assert(end - begin != 1 && "Significand has no digits");
 222
 223     while (p != end && *p == '0')
 224       p++;
 225   }
 226
 227   return p;
 228 }
 229
 230 /* Given a normal decimal floating point number of the form
 231
 232      dddd.dddd[eE][+-]ddd
 233
 234    where the decimal point and exponent are optional, fill out the
 235    structure D.  Exponent is appropriate if the significand is
 236    treated as an integer, and normalizedExponent if the significand
 237    is taken to have the decimal point after a single leading
 238    non-zero digit.
 239
 240    If the value is zero, V->firstSigDigit points to a non-digit, and
 241    the return exponent is zero.
 242 */
 243 struct decimalInfo {
 244   const char *firstSigDigit;
 245   const char *lastSigDigit;
 246   int exponent;
 247   int normalizedExponent;
 248 };
 249
 250 static void
 251 interpretDecimal(StringRef::iterator begin, StringRef::iterator end,
 252                  decimalInfo *D)
 253 {
 254   StringRef::iterator dot = end;
 255   StringRef::iterator p = skipLeadingZeroesAndAnyDot (begin, end, &dot);
 256
 257   D->firstSigDigit = p;
 258   D->exponent = 0;
 259   D->normalizedExponent = 0;
 260
 261   for (; p != end; ++p) {
 262     if (*p == '.') {
 263       assert(dot == end && "String contains multiple dots");
 264       dot = p++;
 265       if (p == end)
 266         break;
 267     }
 268     if (decDigitValue(*p) >= 10U)
 269       break;
 270   }
 271
 272   if (p != end) {
 273     assert((*p == 'e' || *p == 'E') && "Invalid character in significand");
 274     assert(p != begin && "Significand has no digits");
 275     assert((dot == end || p - begin != 1) && "Significand has no digits");
 276
 277     /* p points to the first non-digit in the string */
 278     D->exponent = readExponent(p + 1, end);
 279
 280     /* Implied decimal point?  */
 281     if (dot == end)
 282       dot = p;
 283   }
 284
 285   /* If number is all zeroes accept any exponent.  */
 286   if (p != D->firstSigDigit) {
 287     /* Drop insignificant trailing zeroes.  */
 288     if (p != begin) {
 289       do
 290         do
 291           p--;
 292         while (p != begin && *p == '0');
 293       while (p != begin && *p == '.');
 294     }
 295
 296     /* Adjust the exponents for any decimal point.  */
 297     D->exponent += static_cast<APFloat::ExponentType>((dot - p) - (dot > p));
 298     D->normalizedExponent = (D->exponent +
 299               static_cast<APFloat::ExponentType>((p - D->firstSigDigit)
 300                                       - (dot > D->firstSigDigit && dot < p)));
 301   }
 302
 303   D->lastSigDigit = p;
 304 }
 305
 306 /* Return the trailing fraction of a hexadecimal number.
 307    DIGITVALUE is the first hex digit of the fraction, P points to
 308    the next digit.  */
 309 static lostFraction
 310 trailingHexadecimalFraction(StringRef::iterator p, StringRef::iterator end,
 311                             unsigned int digitValue)
 312 {
 313   unsigned int hexDigit;
 314
 315   /* If the first trailing digit isn't 0 or 8 we can work out the
 316      fraction immediately.  */
 317   if (digitValue > 8)
 318     return lfMoreThanHalf;
 319   else if (digitValue < 8 && digitValue > 0)
 320     return lfLessThanHalf;
 321
 322   // Otherwise we need to find the first non-zero digit.
 323   while (p != end && (*p == '0' || *p == '.'))
 324     p++;
 325
 326   assert(p != end && "Invalid trailing hexadecimal fraction!");
 327
 328   hexDigit = hexDigitValue(*p);
 329
 330   /* If we ran off the end it is exactly zero or one-half, otherwise
 331      a little more.  */
 332   if (hexDigit == -1U)
 333     return digitValue == 0 ? lfExactlyZero: lfExactlyHalf;
 334   else
 335     return digitValue == 0 ? lfLessThanHalf: lfMoreThanHalf;
 336 }
 337
 338 /* Return the fraction lost were a bignum truncated losing the least
 339    significant BITS bits.  */
 340 static lostFraction
 341 lostFractionThroughTruncation(const integerPart *parts,
 342                               unsigned int partCount,
 343                               unsigned int bits)
 344 {
 345   unsigned int lsb;
 346
 347   lsb = APInt::tcLSB(parts, partCount);
 348
 349   /* Note this is guaranteed true if bits == 0, or LSB == -1U.  */
 350   if (bits <= lsb)
 351     return lfExactlyZero;
 352   if (bits == lsb + 1)
 353     return lfExactlyHalf;
 354   if (bits <= partCount * integerPartWidth &&
 355       APInt::tcExtractBit(parts, bits - 1))
 356     return lfMoreThanHalf;
 357
 358   return lfLessThanHalf;
 359 }
 360
 361 /* Shift DST right BITS bits noting lost fraction.  */
 362 static lostFraction
 363 shiftRight(integerPart *dst, unsigned int parts, unsigned int bits)
 364 {
 365   lostFraction lost_fraction;
 366
 367   lost_fraction = lostFractionThroughTruncation(dst, parts, bits);
 368
 369   APInt::tcShiftRight(dst, parts, bits);
 370
 371   return lost_fraction;
 372 }
 373
 374 /* Combine the effect of two lost fractions.  */
 375 static lostFraction
 376 combineLostFractions(lostFraction moreSignificant,
 377                      lostFraction lessSignificant)
 378 {
 379   if (lessSignificant != lfExactlyZero) {
 380     if (moreSignificant == lfExactlyZero)
 381       moreSignificant = lfLessThanHalf;
 382     else if (moreSignificant == lfExactlyHalf)
 383       moreSignificant = lfMoreThanHalf;
 384   }
 385
 386   return moreSignificant;
 387 }
 388
 389 /* The error from the true value, in half-ulps, on multiplying two
 390    floating point numbers, which differ from the value they
 391    approximate by at most HUE1 and HUE2 half-ulps, is strictly less
 392    than the returned value.
 393
 394    See "How to Read Floating Point Numbers Accurately" by William D
 395    Clinger.  */
 396 static unsigned int
 397 HUerrBound(bool inexactMultiply, unsigned int HUerr1, unsigned int HUerr2)
 398 {
 399   assert(HUerr1 < 2 || HUerr2 < 2 || (HUerr1 + HUerr2 < 8));
 400
 401   if (HUerr1 + HUerr2 == 0)
 402     return inexactMultiply * 2;  /* <= inexactMultiply half-ulps.  */
 403   else
 404     return inexactMultiply + 2 * (HUerr1 + HUerr2);
 405 }
 406
 407 /* The number of ulps from the boundary (zero, or half if ISNEAREST)
 408    when the least significant BITS are truncated.  BITS cannot be
 409    zero.  */
 410 static integerPart
 411 ulpsFromBoundary(const integerPart *parts, unsigned int bits, bool isNearest)
 412 {
 413   unsigned int count, partBits;
 414   integerPart part, boundary;
 415
 416   assert(bits != 0);
 417
 418   bits--;
 419   count = bits / integerPartWidth;
 420   partBits = bits % integerPartWidth + 1;
 421
 422   part = parts[count] & (~(integerPart) 0 >> (integerPartWidth - partBits));
 423
 424   if (isNearest)
 425     boundary = (integerPart) 1 << (partBits - 1);
 426   else
 427     boundary = 0;
 428
 429   if (count == 0) {
 430     if (part - boundary <= boundary - part)
 431       return part - boundary;
 432     else
 433       return boundary - part;
 434   }
 435
 436   if (part == boundary) {
 437     while (--count)
 438       if (parts[count])
 439         return ~(integerPart) 0; /* A lot.  */
 440
 441     return parts[0];
 442   } else if (part == boundary - 1) {
 443     while (--count)
 444       if (~parts[count])
 445         return ~(integerPart) 0; /* A lot.  */
 446
 447     return -parts[0];
 448   }
 449
 450   return ~(integerPart) 0; /* A lot.  */
 451 }
 452
 453 /* Place pow(5, power) in DST, and return the number of parts used.
 454    DST must be at least one part larger than size of the answer.  */
 455 static unsigned int
 456 powerOf5(integerPart *dst, unsigned int power)
 457 {
 458   static const integerPart firstEightPowers[] = { 1, 5, 25, 125, 625, 3125,
 459                                                   15625, 78125 };
 460   integerPart pow5s[maxPowerOfFiveParts * 2 + 5];
 461   pow5s[0] = 78125 * 5;
 462
 463   unsigned int partsCount[16] = { 1 };
 464   integerPart scratch[maxPowerOfFiveParts], *p1, *p2, *pow5;
 465   unsigned int result;
 466   assert(power <= maxExponent);
 467
 468   p1 = dst;
 469   p2 = scratch;
 470
 471   *p1 = firstEightPowers[power & 7];
 472   power >>= 3;
 473
 474   result = 1;
 475   pow5 = pow5s;
 476
 477   for (unsigned int n = 0; power; power >>= 1, n++) {
 478     unsigned int pc;
 479
 480     pc = partsCount[n];
 481
 482     /* Calculate pow(5,pow(2,n+3)) if we haven't yet.  */
 483     if (pc == 0) {
 484       pc = partsCount[n - 1];
 485       APInt::tcFullMultiply(pow5, pow5 - pc, pow5 - pc, pc, pc);
 486       pc *= 2;
 487       if (pow5[pc - 1] == 0)
 488         pc--;
 489       partsCount[n] = pc;
 490     }
 491
 492     if (power & 1) {
 493       integerPart *tmp;
 494
 495       APInt::tcFullMultiply(p2, p1, pow5, result, pc);
 496       result += pc;
 497       if (p2[result - 1] == 0)
 498         result--;
 499
 500       /* Now result is in p1 with partsCount parts and p2 is scratch
 501          space.  */
 502       tmp = p1, p1 = p2, p2 = tmp;
 503     }
 504
 505     pow5 += pc;
 506   }
 507
 508   if (p1 != dst)
 509     APInt::tcAssign(dst, p1, result);
 510
 511   return result;
 512 }
 513
 514 /* Zero at the end to avoid modular arithmetic when adding one; used
 515    when rounding up during hexadecimal output.  */
 516 static const char hexDigitsLower[] = "0123456789abcdef0";
 517 static const char hexDigitsUpper[] = "0123456789ABCDEF0";
 518 static const char infinityL[] = "infinity";
 519 static const char infinityU[] = "INFINITY";
 520 static const char NaNL[] = "nan";
 521 static const char NaNU[] = "NAN";
 522
 523 /* Write out an integerPart in hexadecimal, starting with the most
 524    significant nibble.  Write out exactly COUNT hexdigits, return
 525    COUNT.  */
 526 static unsigned int
 527 partAsHex (char *dst, integerPart part, unsigned int count,
 528            const char *hexDigitChars)
 529 {
 530   unsigned int result = count;
 531
 532   assert(count != 0 && count <= integerPartWidth / 4);
 533
 534   part >>= (integerPartWidth - 4 * count);
 535   while (count--) {
 536     dst[count] = hexDigitChars[part & 0xf];
 537     part >>= 4;
 538   }
 539
 540   return result;
 541 }
 542
 543 /* Write out an unsigned decimal integer.  */
 544 static char *
 545 writeUnsignedDecimal (char *dst, unsigned int n)
 546 {
 547   char buff[40], *p;
 548
 549   p = buff;
 550   do
 551     *p++ = '0' + n % 10;
 552   while (n /= 10);
 553
 554   do
 555     *dst++ = *--p;
 556   while (p != buff);
 557
 558   return dst;
 559 }
 560
 561 /* Write out a signed decimal integer.  */
 562 static char *
 563 writeSignedDecimal (char *dst, int value)
 564 {
 565   if (value < 0) {
 566     *dst++ = '-';
 567     dst = writeUnsignedDecimal(dst, -(unsigned) value);
 568   } else
 569     dst = writeUnsignedDecimal(dst, value);
 570
 571   return dst;
 572 }
 573
 574 /* Constructors.  */
 575 void
 576 APFloat::initialize(const fltSemantics *ourSemantics)
 577 {
 578   unsigned int count;
 579
 580   semantics = ourSemantics;
 581   count = partCount();
 582   if (count > 1)
 583     significand.parts = new integerPart[count];
 584 }
 585
 586 void
 587 APFloat::freeSignificand()
 588 {
 589   if (needsCleanup())
 590     delete [] significand.parts;
 591 }
 592
 593 void
 594 APFloat::assign(const APFloat &rhs)
 595 {
 596   assert(semantics == rhs.semantics);
 597
 598   sign = rhs.sign;
 599   category = rhs.category;
 600   exponent = rhs.exponent;
 601   if (isFiniteNonZero() || category == fcNaN)
 602     copySignificand(rhs);
 603 }
 604
 605 void
 606 APFloat::copySignificand(const APFloat &rhs)
 607 {
 608   assert(isFiniteNonZero() || category == fcNaN);
 609   assert(rhs.partCount() >= partCount());
 610
 611   APInt::tcAssign(significandParts(), rhs.significandParts(),
 612                   partCount());
 613 }
 614
 615 /* Make this number a NaN, with an arbitrary but deterministic value
 616    for the significand.  If double or longer, this is a signalling NaN,
 617    which may not be ideal.  If float, this is QNaN(0).  */
 618 void APFloat::makeNaN(bool SNaN, bool Negative, const APInt *fill)
 619 {
 620   category = fcNaN;
 621   sign = Negative;
 622
 623   integerPart *significand = significandParts();
 624   unsigned numParts = partCount();
 625
 626   // Set the significand bits to the fill.
 627   if (!fill || fill->getNumWords() < numParts)
 628     APInt::tcSet(significand, 0, numParts);
 629   if (fill) {
 630     APInt::tcAssign(significand, fill->getRawData(),
 631                     std::min(fill->getNumWords(), numParts));
 632
 633     // Zero out the excess bits of the significand.
 634     unsigned bitsToPreserve = semantics->precision - 1;
 635     unsigned part = bitsToPreserve / 64;
 636     bitsToPreserve %= 64;
 637     significand[part] &= ((1ULL << bitsToPreserve) - 1);
 638     for (part++; part != numParts; ++part)
 639       significand[part] = 0;
 640   }
 641
 642   unsigned QNaNBit = semantics->precision - 2;
 643
 644   if (SNaN) {
 645     // We always have to clear the QNaN bit to make it an SNaN.
 646     APInt::tcClearBit(significand, QNaNBit);
 647
 648     // If there are no bits set in the payload, we have to set
 649     // *something* to make it a NaN instead of an infinity;
 650     // conventionally, this is the next bit down from the QNaN bit.
 651     if (APInt::tcIsZero(significand, numParts))
 652       APInt::tcSetBit(significand, QNaNBit - 1);
 653   } else {
 654     // We always have to set the QNaN bit to make it a QNaN.
 655     APInt::tcSetBit(significand, QNaNBit);
 656   }
 657
 658   // For x87 extended precision, we want to make a NaN, not a
 659   // pseudo-NaN.  Maybe we should expose the ability to make
 660   // pseudo-NaNs?
 661   if (semantics == &APFloat::x87DoubleExtended)
 662     APInt::tcSetBit(significand, QNaNBit + 1);
 663 }
 664
 665 APFloat APFloat::makeNaN(const fltSemantics &Sem, bool SNaN, bool Negative,
 666                          const APInt *fill) {
 667   APFloat value(Sem, uninitialized);
 668   value.makeNaN(SNaN, Negative, fill);
 669   return value;
 670 }
 671
 672 APFloat &
 673 APFloat::operator=(const APFloat &rhs)
 674 {
 675   if (this != &rhs) {
 676     if (semantics != rhs.semantics) {
 677       freeSignificand();
 678       initialize(rhs.semantics);
 679     }
 680     assign(rhs);
 681   }
 682
 683   return *this;
 684 }
 685
 686 APFloat &
 687 APFloat::operator=(APFloat &&rhs) {
 688   freeSignificand();
 689
 690   semantics = rhs.semantics;
 691   significand = rhs.significand;
 692   exponent = rhs.exponent;
 693   category = rhs.category;
 694   sign = rhs.sign;
 695
 696   rhs.semantics = &Bogus;
 697   return *this;
 698 }
 699
 700 bool
 701 APFloat::isDenormal() const {
 702   return isFiniteNonZero() && (exponent == semantics->minExponent) &&
 703          (APInt::tcExtractBit(significandParts(),
 704                               semantics->precision - 1) == 0);
 705 }
 706
 707 bool
 708 APFloat::isSmallest() const {
 709   // The smallest number by magnitude in our format will be the smallest
 710   // denormal, i.e. the floating point number with exponent being minimum
 711   // exponent and significand bitwise equal to 1 (i.e. with MSB equal to 0).
 712   return isFiniteNonZero() && exponent == semantics->minExponent &&
 713     significandMSB() == 0;
 714 }
 715
 716 bool APFloat::isSignificandAllOnes() const {
 717   // Test if the significand excluding the integral bit is all ones. This allows
 718   // us to test for binade boundaries.
 719   const integerPart *Parts = significandParts();
 720   const unsigned PartCount = partCount();
 721   for (unsigned i = 0; i < PartCount - 1; i++)
 722     if (~Parts[i])
 723       return false;
 724
 725   // Set the unused high bits to all ones when we compare.
 726   const unsigned NumHighBits =
 727     PartCount*integerPartWidth - semantics->precision + 1;
 728   assert(NumHighBits <= integerPartWidth && "Can not have more high bits to "
 729          "fill than integerPartWidth");
 730   const integerPart HighBitFill =
 731     ~integerPart(0) << (integerPartWidth - NumHighBits);
 732   if (~(Parts[PartCount - 1] | HighBitFill))
 733     return false;
 734
 735   return true;
 736 }
 737
 738 bool APFloat::isSignificandAllZeros() const {
 739   // Test if the significand excluding the integral bit is all zeros. This
 740   // allows us to test for binade boundaries.
 741   const integerPart *Parts = significandParts();
 742   const unsigned PartCount = partCount();
 743
 744   for (unsigned i = 0; i < PartCount - 1; i++)
 745     if (Parts[i])
 746       return false;
 747
 748   const unsigned NumHighBits =
 749     PartCount*integerPartWidth - semantics->precision + 1;
 750   assert(NumHighBits <= integerPartWidth && "Can not have more high bits to "
 751          "clear than integerPartWidth");
 752   const integerPart HighBitMask = ~integerPart(0) >> NumHighBits;
 753
 754   if (Parts[PartCount - 1] & HighBitMask)
 755     return false;
 756
 757   return true;
 758 }
 759
 760 bool
 761 APFloat::isLargest() const {
 762   // The largest number by magnitude in our format will be the floating point
 763   // number with maximum exponent and with significand that is all ones.
 764   return isFiniteNonZero() && exponent == semantics->maxExponent
 765     && isSignificandAllOnes();
 766 }
 767
 768 bool
 769 APFloat::bitwiseIsEqual(const APFloat &rhs) const {
 770   if (this == &rhs)
 771     return true;
 772   if (semantics != rhs.semantics ||
 773       category != rhs.category ||
 774       sign != rhs.sign)
 775     return false;
 776   if (category==fcZero || category==fcInfinity)
 777     return true;
 778   else if (isFiniteNonZero() && exponent!=rhs.exponent)
 779     return false;
 780   else {
 781     int i= partCount();
 782     const integerPart* p=significandParts();
 783     const integerPart* q=rhs.significandParts();
 784     for (; i>0; i--, p++, q++) {
 785       if (*p != *q)
 786         return false;
 787     }
 788     return true;
 789   }
 790 }
 791
 792 APFloat::APFloat(const fltSemantics &ourSemantics, integerPart value) {
 793   initialize(&ourSemantics);
 794   sign = 0;
 795   category = fcNormal;
 796   zeroSignificand();
 797   exponent = ourSemantics.precision - 1;
 798   significandParts()[0] = value;
 799   normalize(rmNearestTiesToEven, lfExactlyZero);
 800 }
 801
 802 APFloat::APFloat(const fltSemantics &ourSemantics) {
 803   initialize(&ourSemantics);
 804   category = fcZero;
 805   sign = false;
 806 }
 807
 808 APFloat::APFloat(const fltSemantics &ourSemantics, uninitializedTag tag) {
 809   // Allocates storage if necessary but does not initialize it.
 810   initialize(&ourSemantics);
 811 }
 812
 813 APFloat::APFloat(const fltSemantics &ourSemantics, StringRef text) {
 814   initialize(&ourSemantics);
 815   convertFromString(text, rmNearestTiesToEven);
 816 }
 817
 818 APFloat::APFloat(const APFloat &rhs) {
 819   initialize(rhs.semantics);
 820   assign(rhs);
 821 }
 822
 823 APFloat::APFloat(APFloat &&rhs) : semantics(&Bogus) {
 824   *this = std::move(rhs);
 825 }
 826
 827 APFloat::~APFloat()
 828 {
 829   freeSignificand();
 830 }
 831
 832 // Profile - This method 'profiles' an APFloat for use with FoldingSet.
 833 void APFloat::Profile(FoldingSetNodeID& ID) const {
 834   ID.Add(bitcastToAPInt());
 835 }
 836
 837 unsigned int
 838 APFloat::partCount() const
 839 {
 840   return partCountForBits(semantics->precision + 1);
 841 }
 842
 843 unsigned int
 844 APFloat::semanticsPrecision(const fltSemantics &semantics)
 845 {
 846   return semantics.precision;
 847 }
 848
 849 const integerPart *
 850 APFloat::significandParts() const
 851 {
 852   return const_cast<APFloat *>(this)->significandParts();
 853 }
 854
 855 integerPart *
 856 APFloat::significandParts()
 857 {
 858   if (partCount() > 1)
 859     return significand.parts;
 860   else
 861     return &significand.part;
 862 }
 863
 864 void
 865 APFloat::zeroSignificand()
 866 {
 867   APInt::tcSet(significandParts(), 0, partCount());
 868 }
 869
 870 /* Increment an fcNormal floating point number's significand.  */
 871 void
 872 APFloat::incrementSignificand()
 873 {
 874   integerPart carry;
 875
 876   carry = APInt::tcIncrement(significandParts(), partCount());
 877
 878   /* Our callers should never cause us to overflow.  */
 879   assert(carry == 0);
 880   (void)carry;
 881 }
 882
 883 /* Add the significand of the RHS.  Returns the carry flag.  */
 884 integerPart
 885 APFloat::addSignificand(const APFloat &rhs)
 886 {
 887   integerPart *parts;
 888
 889   parts = significandParts();
 890
 891   assert(semantics == rhs.semantics);
 892   assert(exponent == rhs.exponent);
 893
 894   return APInt::tcAdd(parts, rhs.significandParts(), 0, partCount());
 895 }
 896
 897 /* Subtract the significand of the RHS with a borrow flag.  Returns
 898    the borrow flag.  */
 899 integerPart
 900 APFloat::subtractSignificand(const APFloat &rhs, integerPart borrow)
 901 {
 902   integerPart *parts;
 903
 904   parts = significandParts();
 905
 906   assert(semantics == rhs.semantics);
 907   assert(exponent == rhs.exponent);
 908
 909   return APInt::tcSubtract(parts, rhs.significandParts(), borrow,
 910                            partCount());
 911 }
 912
 913 /* Multiply the significand of the RHS.  If ADDEND is non-NULL, add it
 914    on to the full-precision result of the multiplication.  Returns the
 915    lost fraction.  */
 916 lostFraction
 917 APFloat::multiplySignificand(const APFloat &rhs, const APFloat *addend)
 918 {
 919   unsigned int omsb;        // One, not zero, based MSB.
 920   unsigned int partsCount, newPartsCount, precision;
 921   integerPart *lhsSignificand;
 922   integerPart scratch[4];
 923   integerPart *fullSignificand;
 924   lostFraction lost_fraction;
 925   bool ignored;
 926
 927   assert(semantics == rhs.semantics);
 928
 929   precision = semantics->precision;
 930   newPartsCount = partCountForBits(precision * 2);
 931
 932   if (newPartsCount > 4)
 933     fullSignificand = new integerPart[newPartsCount];
 934   else
 935     fullSignificand = scratch;
 936
 937   lhsSignificand = significandParts();
 938   partsCount = partCount();
 939
 940   APInt::tcFullMultiply(fullSignificand, lhsSignificand,
 941                         rhs.significandParts(), partsCount, partsCount);
 942
 943   lost_fraction = lfExactlyZero;
 944   omsb = APInt::tcMSB(fullSignificand, newPartsCount) + 1;
 945   exponent += rhs.exponent;
 946
 947   // Assume the operands involved in the multiplication are single-precision
 948   // FP, and the two multiplicants are:
 949   //   *this = a23 . a22 ... a0 * 2^e1
 950   //     rhs = b23 . b22 ... b0 * 2^e2
 951   // the result of multiplication is:
 952   //   *this = c47 c46 . c45 ... c0 * 2^(e1+e2)
 953   // Note that there are two significant bits at the left-hand side of the
 954   // radix point. Move the radix point toward left by one bit, and adjust
 955   // exponent accordingly.
 956   exponent += 1;
 957
 958   if (addend) {
 959     // The intermediate result of the multiplication has "2 * precision"
 960     // signicant bit; adjust the addend to be consistent with mul result.
 961     //
 962     Significand savedSignificand = significand;
 963     const fltSemantics *savedSemantics = semantics;
 964     fltSemantics extendedSemantics;
 965     opStatus status;
 966     unsigned int extendedPrecision;
 967
 968     /* Normalize our MSB.  */
 969     extendedPrecision = 2 * precision;
 970     if (omsb != extendedPrecision) {
 971       assert(extendedPrecision > omsb);
 972       APInt::tcShiftLeft(fullSignificand, newPartsCount,
 973                          extendedPrecision - omsb);
 974       exponent -= extendedPrecision - omsb;
 975     }
 976
 977     /* Create new semantics.  */
 978     extendedSemantics = *semantics;
 979     extendedSemantics.precision = extendedPrecision;
 980
 981     if (newPartsCount == 1)
 982       significand.part = fullSignificand[0];
 983     else
 984       significand.parts = fullSignificand;
 985     semantics = &extendedSemantics;
 986
 987     APFloat extendedAddend(*addend);
 988     status = extendedAddend.convert(extendedSemantics, rmTowardZero, &ignored);
 989     assert(status == opOK);
 990     (void)status;
 991     lost_fraction = addOrSubtractSignificand(extendedAddend, false);
 992
 993     /* Restore our state.  */
 994     if (newPartsCount == 1)
 995       fullSignificand[0] = significand.part;
 996     significand = savedSignificand;
 997     semantics = savedSemantics;
 998
 999     omsb = APInt::tcMSB(fullSignificand, newPartsCount) + 1;
1000   }
1001
1002   // Convert the result having "2 * precision" significant-bits back to the one
1003   // having "precision" significant-bits. First, move the radix point from
1004   // poision "2*precision - 1" to "precision - 1". The exponent need to be
1005   // adjusted by "2*precision - 1" - "precision - 1" = "precision".
1006   exponent -= precision;
1007
1008   // In case MSB resides at the left-hand side of radix point, shift the
1009   // mantissa right by some amount to make sure the MSB reside right before
1010   // the radix point (i.e. "MSB . rest-significant-bits").
1011   //
1012   // Note that the result is not normalized when "omsb < precision". So, the
1013   // caller needs to call APFloat::normalize() if normalized value is expected.
1014   if (omsb > precision) {
1015     unsigned int bits, significantParts;
1016     lostFraction lf;
1017
1018     bits = omsb - precision;
1019     significantParts = partCountForBits(omsb);
1020     lf = shiftRight(fullSignificand, significantParts, bits);
1021     lost_fraction = combineLostFractions(lf, lost_fraction);
1022     exponent += bits;
1023   }
1024
1025   APInt::tcAssign(lhsSignificand, fullSignificand, partsCount);
1026
1027   if (newPartsCount > 4)
1028     delete [] fullSignificand;
1029
1030   return lost_fraction;
1031 }
1032
1033 /* Multiply the significands of LHS and RHS to DST.  */
1034 lostFraction
1035 APFloat::divideSignificand(const APFloat &rhs)
1036 {
1037   unsigned int bit, i, partsCount;
1038   const integerPart *rhsSignificand;
1039   integerPart *lhsSignificand, *dividend, *divisor;
1040   integerPart scratch[4];
1041   lostFraction lost_fraction;
1042
1043   assert(semantics == rhs.semantics);
1044
1045   lhsSignificand = significandParts();
1046   rhsSignificand = rhs.significandParts();
1047   partsCount = partCount();
1048
1049   if (partsCount > 2)
1050     dividend = new integerPart[partsCount * 2];
1051   else
1052     dividend = scratch;
1053
1054   divisor = dividend + partsCount;
1055
1056   /* Copy the dividend and divisor as they will be modified in-place.  */
1057   for (i = 0; i < partsCount; i++) {
1058     dividend[i] = lhsSignificand[i];
1059     divisor[i] = rhsSignificand[i];
1060     lhsSignificand[i] = 0;
1061   }
1062
1063   exponent -= rhs.exponent;
1064
1065   unsigned int precision = semantics->precision;
1066
1067   /* Normalize the divisor.  */
1068   bit = precision - APInt::tcMSB(divisor, partsCount) - 1;
1069   if (bit) {
1070     exponent += bit;
1071     APInt::tcShiftLeft(divisor, partsCount, bit);
1072   }
1073
1074   /* Normalize the dividend.  */
1075   bit = precision - APInt::tcMSB(dividend, partsCount) - 1;
1076   if (bit) {
1077     exponent -= bit;
1078     APInt::tcShiftLeft(dividend, partsCount, bit);
1079   }
1080
1081   /* Ensure the dividend >= divisor initially for the loop below.
1082      Incidentally, this means that the division loop below is
1083      guaranteed to set the integer bit to one.  */
1084   if (APInt::tcCompare(dividend, divisor, partsCount) < 0) {
1085     exponent--;
1086     APInt::tcShiftLeft(dividend, partsCount, 1);
1087     assert(APInt::tcCompare(dividend, divisor, partsCount) >= 0);
1088   }
1089
1090   /* Long division.  */
1091   for (bit = precision; bit; bit -= 1) {
1092     if (APInt::tcCompare(dividend, divisor, partsCount) >= 0) {
1093       APInt::tcSubtract(dividend, divisor, 0, partsCount);
1094       APInt::tcSetBit(lhsSignificand, bit - 1);
1095     }
1096
1097     APInt::tcShiftLeft(dividend, partsCount, 1);
1098   }
1099
1100   /* Figure out the lost fraction.  */
1101   int cmp = APInt::tcCompare(dividend, divisor, partsCount);
1102
1103   if (cmp > 0)
1104     lost_fraction = lfMoreThanHalf;
1105   else if (cmp == 0)
1106     lost_fraction = lfExactlyHalf;
1107   else if (APInt::tcIsZero(dividend, partsCount))
1108     lost_fraction = lfExactlyZero;
1109   else
1110     lost_fraction = lfLessThanHalf;
1111
1112   if (partsCount > 2)
1113     delete [] dividend;
1114
1115   return lost_fraction;
1116 }
1117
1118 unsigned int
1119 APFloat::significandMSB() const
1120 {
1121   return APInt::tcMSB(significandParts(), partCount());
1122 }
1123
1124 unsigned int
1125 APFloat::significandLSB() const
1126 {
1127   return APInt::tcLSB(significandParts(), partCount());
1128 }
1129
1130 /* Note that a zero result is NOT normalized to fcZero.  */
1131 lostFraction
1132 APFloat::shiftSignificandRight(unsigned int bits)
1133 {
1134   /* Our exponent should not overflow.  */
1135   assert((ExponentType) (exponent + bits) >= exponent);
1136
1137   exponent += bits;
1138
1139   return shiftRight(significandParts(), partCount(), bits);
1140 }
1141
1142 /* Shift the significand left BITS bits, subtract BITS from its exponent.  */
1143 void
1144 APFloat::shiftSignificandLeft(unsigned int bits)
1145 {
1146   assert(bits < semantics->precision);
1147
1148   if (bits) {
1149     unsigned int partsCount = partCount();
1150
1151     APInt::tcShiftLeft(significandParts(), partsCount, bits);
1152     exponent -= bits;
1153
1154     assert(!APInt::tcIsZero(significandParts(), partsCount));
1155   }
1156 }
1157
1158 APFloat::cmpResult
1159 APFloat::compareAbsoluteValue(const APFloat &rhs) const
1160 {
1161   int compare;
1162
1163   assert(semantics == rhs.semantics);
1164   assert(isFiniteNonZero());
1165   assert(rhs.isFiniteNonZero());
1166
1167   compare = exponent - rhs.exponent;
1168
1169   /* If exponents are equal, do an unsigned bignum comparison of the
1170      significands.  */
1171   if (compare == 0)
1172     compare = APInt::tcCompare(significandParts(), rhs.significandParts(),
1173                                partCount());
1174
1175   if (compare > 0)
1176     return cmpGreaterThan;
1177   else if (compare < 0)
1178     return cmpLessThan;
1179   else
1180     return cmpEqual;
1181 }
1182
1183 /* Handle overflow.  Sign is preserved.  We either become infinity or
1184    the largest finite number.  */
1185 APFloat::opStatus
1186 APFloat::handleOverflow(roundingMode rounding_mode)
1187 {
1188   /* Infinity?  */
1189   if (rounding_mode == rmNearestTiesToEven ||
1190       rounding_mode == rmNearestTiesToAway ||
1191       (rounding_mode == rmTowardPositive && !sign) ||
1192       (rounding_mode == rmTowardNegative && sign)) {
1193     category = fcInfinity;
1194     return (opStatus) (opOverflow | opInexact);
1195   }
1196
1197   /* Otherwise we become the largest finite number.  */
1198   category = fcNormal;
1199   exponent = semantics->maxExponent;
1200   APInt::tcSetLeastSignificantBits(significandParts(), partCount(),
1201                                    semantics->precision);
1202
1203   return opInexact;
1204 }
1205
1206 /* Returns TRUE if, when truncating the current number, with BIT the
1207    new LSB, with the given lost fraction and rounding mode, the result
1208    would need to be rounded away from zero (i.e., by increasing the
1209    signficand).  This routine must work for fcZero of both signs, and
1210    fcNormal numbers.  */
1211 bool
1212 APFloat::roundAwayFromZero(roundingMode rounding_mode,
1213                            lostFraction lost_fraction,
1214                            unsigned int bit) const
1215 {
1216   /* NaNs and infinities should not have lost fractions.  */
1217   assert(isFiniteNonZero() || category == fcZero);
1218
1219   /* Current callers never pass this so we don't handle it.  */
1220   assert(lost_fraction != lfExactlyZero);
1221
1222   switch (rounding_mode) {
1223   case rmNearestTiesToAway:
1224     return lost_fraction == lfExactlyHalf || lost_fraction == lfMoreThanHalf;
1225
1226   case rmNearestTiesToEven:
1227     if (lost_fraction == lfMoreThanHalf)
1228       return true;
1229
1230     /* Our zeroes don't have a significand to test.  */
1231     if (lost_fraction == lfExactlyHalf && category != fcZero)
1232       return APInt::tcExtractBit(significandParts(), bit);
1233
1234     return false;
1235
1236   case rmTowardZero:
1237     return false;
1238
1239   case rmTowardPositive:
1240     return sign == false;
1241
1242   case rmTowardNegative:
1243     return sign == true;
1244   }
1245   llvm_unreachable("Invalid rounding mode found");
1246 }
1247
1248 APFloat::opStatus
1249 APFloat::normalize(roundingMode rounding_mode,
1250                    lostFraction lost_fraction)
1251 {
1252   unsigned int omsb;                /* One, not zero, based MSB.  */
1253   int exponentChange;
1254
1255   if (!isFiniteNonZero())
1256     return opOK;
1257
1258   /* Before rounding normalize the exponent of fcNormal numbers.  */
1259   omsb = significandMSB() + 1;
1260
1261   if (omsb) {
1262     /* OMSB is numbered from 1.  We want to place it in the integer
1263        bit numbered PRECISION if possible, with a compensating change in
1264        the exponent.  */
1265     exponentChange = omsb - semantics->precision;
1266
1267     /* If the resulting exponent is too high, overflow according to
1268        the rounding mode.  */
1269     if (exponent + exponentChange > semantics->maxExponent)
1270       return handleOverflow(rounding_mode);
1271
1272     /* Subnormal numbers have exponent minExponent, and their MSB
1273        is forced based on that.  */
1274     if (exponent + exponentChange < semantics->minExponent)
1275       exponentChange = semantics->minExponent - exponent;
1276
1277     /* Shifting left is easy as we don't lose precision.  */
1278     if (exponentChange < 0) {
1279       assert(lost_fraction == lfExactlyZero);
1280
1281       shiftSignificandLeft(-exponentChange);
1282
1283       return opOK;
1284     }
1285
1286     if (exponentChange > 0) {
1287       lostFraction lf;
1288
1289       /* Shift right and capture any new lost fraction.  */
1290       lf = shiftSignificandRight(exponentChange);
1291
1292       lost_fraction = combineLostFractions(lf, lost_fraction);
1293
1294       /* Keep OMSB up-to-date.  */
1295       if (omsb > (unsigned) exponentChange)
1296         omsb -= exponentChange;
1297       else
1298         omsb = 0;
1299     }
1300   }
1301
1302   /* Now round the number according to rounding_mode given the lost
1303      fraction.  */
1304
1305   /* As specified in IEEE 754, since we do not trap we do not report
1306      underflow for exact results.  */
1307   if (lost_fraction == lfExactlyZero) {
1308     /* Canonicalize zeroes.  */
1309     if (omsb == 0)
1310       category = fcZero;
1311
1312     return opOK;
1313   }
1314
1315   /* Increment the significand if we're rounding away from zero.  */
1316   if (roundAwayFromZero(rounding_mode, lost_fraction, 0)) {
1317     if (omsb == 0)
1318       exponent = semantics->minExponent;
1319
1320     incrementSignificand();
1321     omsb = significandMSB() + 1;
1322
1323     /* Did the significand increment overflow?  */
1324     if (omsb == (unsigned) semantics->precision + 1) {
1325       /* Renormalize by incrementing the exponent and shifting our
1326          significand right one.  However if we already have the
1327          maximum exponent we overflow to infinity.  */
1328       if (exponent == semantics->maxExponent) {
1329         category = fcInfinity;
1330
1331         return (opStatus) (opOverflow | opInexact);
1332       }
1333
1334       shiftSignificandRight(1);
1335
1336       return opInexact;
1337     }
1338   }
1339
1340   /* The normal case - we were and are not denormal, and any
1341      significand increment above didn't overflow.  */
1342   if (omsb == semantics->precision)
1343     return opInexact;
1344
1345   /* We have a non-zero denormal.  */
1346   assert(omsb < semantics->precision);
1347
1348   /* Canonicalize zeroes.  */
1349   if (omsb == 0)
1350     category = fcZero;
1351
1352   /* The fcZero case is a denormal that underflowed to zero.  */
1353   return (opStatus) (opUnderflow | opInexact);
1354 }
1355
1356 APFloat::opStatus
1357 APFloat::addOrSubtractSpecials(const APFloat &rhs, bool subtract)
1358 {
1359   switch (PackCategoriesIntoKey(category, rhs.category)) {
1360   default:
1361     llvm_unreachable(nullptr);
1362
1363   case PackCategoriesIntoKey(fcNaN, fcZero):
1364   case PackCategoriesIntoKey(fcNaN, fcNormal):
1365   case PackCategoriesIntoKey(fcNaN, fcInfinity):
1366   case PackCategoriesIntoKey(fcNaN, fcNaN):
1367   case PackCategoriesIntoKey(fcNormal, fcZero):
1368   case PackCategoriesIntoKey(fcInfinity, fcNormal):
1369   case PackCategoriesIntoKey(fcInfinity, fcZero):
1370     return opOK;
1371
1372   case PackCategoriesIntoKey(fcZero, fcNaN):
1373   case PackCategoriesIntoKey(fcNormal, fcNaN):
1374   case PackCategoriesIntoKey(fcInfinity, fcNaN):
1375     // We need to be sure to flip the sign here for subtraction because we
1376     // don't have a separate negate operation so -NaN becomes 0 - NaN here.
1377     sign = rhs.sign ^ subtract;
1378     category = fcNaN;
1379     copySignificand(rhs);
1380     return opOK;
1381
1382   case PackCategoriesIntoKey(fcNormal, fcInfinity):
1383   case PackCategoriesIntoKey(fcZero, fcInfinity):
1384     category = fcInfinity;
1385     sign = rhs.sign ^ subtract;
1386     return opOK;
1387
1388   case PackCategoriesIntoKey(fcZero, fcNormal):
1389     assign(rhs);
1390     sign = rhs.sign ^ subtract;
1391     return opOK;
1392
1393   case PackCategoriesIntoKey(fcZero, fcZero):
1394     /* Sign depends on rounding mode; handled by caller.  */
1395     return opOK;
1396
1397   case PackCategoriesIntoKey(fcInfinity, fcInfinity):
1398     /* Differently signed infinities can only be validly
1399        subtracted.  */
1400     if (((sign ^ rhs.sign)!=0) != subtract) {
1401       makeNaN();
1402       return opInvalidOp;
1403     }
1404
1405     return opOK;
1406
1407   case PackCategoriesIntoKey(fcNormal, fcNormal):
1408     return opDivByZero;
1409   }
1410 }
1411
1412 /* Add or subtract two normal numbers.  */
1413 lostFraction
1414 APFloat::addOrSubtractSignificand(const APFloat &rhs, bool subtract)
1415 {
1416   integerPart carry;
1417   lostFraction lost_fraction;
1418   int bits;
1419
1420   /* Determine if the operation on the absolute values is effectively
1421      an addition or subtraction.  */
1422   subtract ^= (sign ^ rhs.sign) ? true : false;
1423
1424   /* Are we bigger exponent-wise than the RHS?  */
1425   bits = exponent - rhs.exponent;
1426
1427   /* Subtraction is more subtle than one might naively expect.  */
1428   if (subtract) {
1429     APFloat temp_rhs(rhs);
1430     bool reverse;
1431
1432     if (bits == 0) {
1433       reverse = compareAbsoluteValue(temp_rhs) == cmpLessThan;
1434       lost_fraction = lfExactlyZero;
1435     } else if (bits > 0) {
1436       lost_fraction = temp_rhs.shiftSignificandRight(bits - 1);
1437       shiftSignificandLeft(1);
1438       reverse = false;
1439     } else {
1440       lost_fraction = shiftSignificandRight(-bits - 1);
1441       temp_rhs.shiftSignificandLeft(1);
1442       reverse = true;
1443     }
1444
1445     if (reverse) {
1446       carry = temp_rhs.subtractSignificand
1447         (*this, lost_fraction != lfExactlyZero);
1448       copySignificand(temp_rhs);
1449       sign = !sign;
1450     } else {
1451       carry = subtractSignificand
1452         (temp_rhs, lost_fraction != lfExactlyZero);
1453     }
1454
1455     /* Invert the lost fraction - it was on the RHS and
1456        subtracted.  */
1457     if (lost_fraction == lfLessThanHalf)
1458       lost_fraction = lfMoreThanHalf;
1459     else if (lost_fraction == lfMoreThanHalf)
1460       lost_fraction = lfLessThanHalf;
1461
1462     /* The code above is intended to ensure that no borrow is
1463        necessary.  */
1464     assert(!carry);
1465     (void)carry;
1466   } else {
1467     if (bits > 0) {
1468       APFloat temp_rhs(rhs);
1469
1470       lost_fraction = temp_rhs.shiftSignificandRight(bits);
1471       carry = addSignificand(temp_rhs);
1472     } else {
1473       lost_fraction = shiftSignificandRight(-bits);
1474       carry = addSignificand(rhs);
1475     }
1476
1477     /* We have a guard bit; generating a carry cannot happen.  */
1478     assert(!carry);
1479     (void)carry;
1480   }
1481
1482   return lost_fraction;
1483 }
1484
1485 APFloat::opStatus
1486 APFloat::multiplySpecials(const APFloat &rhs)
1487 {
1488   switch (PackCategoriesIntoKey(category, rhs.category)) {
1489   default:
1490     llvm_unreachable(nullptr);
1491
1492   case PackCategoriesIntoKey(fcNaN, fcZero):
1493   case PackCategoriesIntoKey(fcNaN, fcNormal):
1494   case PackCategoriesIntoKey(fcNaN, fcInfinity):
1495   case PackCategoriesIntoKey(fcNaN, fcNaN):
1496     sign = false;
1497     return opOK;
1498
1499   case PackCategoriesIntoKey(fcZero, fcNaN):
1500   case PackCategoriesIntoKey(fcNormal, fcNaN):
1501   case PackCategoriesIntoKey(fcInfinity, fcNaN):
1502     sign = false;
1503     category = fcNaN;
1504     copySignificand(rhs);
1505     return opOK;
1506
1507   case PackCategoriesIntoKey(fcNormal, fcInfinity):
1508   case PackCategoriesIntoKey(fcInfinity, fcNormal):
1509   case PackCategoriesIntoKey(fcInfinity, fcInfinity):
1510     category = fcInfinity;
1511     return opOK;
1512
1513   case PackCategoriesIntoKey(fcZero, fcNormal):
1514   case PackCategoriesIntoKey(fcNormal, fcZero):
1515   case PackCategoriesIntoKey(fcZero, fcZero):
1516     category = fcZero;
1517     return opOK;
1518
1519   case PackCategoriesIntoKey(fcZero, fcInfinity):
1520   case PackCategoriesIntoKey(fcInfinity, fcZero):
1521     makeNaN();
1522     return opInvalidOp;
1523
1524   case PackCategoriesIntoKey(fcNormal, fcNormal):
1525     return opOK;
1526   }
1527 }
1528
1529 APFloat::opStatus
1530 APFloat::divideSpecials(const APFloat &rhs)
1531 {
1532   switch (PackCategoriesIntoKey(category, rhs.category)) {
1533   default:
1534     llvm_unreachable(nullptr);
1535
1536   case PackCategoriesIntoKey(fcZero, fcNaN):
1537   case PackCategoriesIntoKey(fcNormal, fcNaN):
1538   case PackCategoriesIntoKey(fcInfinity, fcNaN):
1539     category = fcNaN;
1540     copySignificand(rhs);
1541   case PackCategoriesIntoKey(fcNaN, fcZero):
1542   case PackCategoriesIntoKey(fcNaN, fcNormal):
1543   case PackCategoriesIntoKey(fcNaN, fcInfinity):
1544   case PackCategoriesIntoKey(fcNaN, fcNaN):
1545     sign = false;
1546   case PackCategoriesIntoKey(fcInfinity, fcZero):
1547   case PackCategoriesIntoKey(fcInfinity, fcNormal):
1548   case PackCategoriesIntoKey(fcZero, fcInfinity):
1549   case PackCategoriesIntoKey(fcZero, fcNormal):
1550     return opOK;
1551
1552   case PackCategoriesIntoKey(fcNormal, fcInfinity):
1553     category = fcZero;
1554     return opOK;
1555
1556   case PackCategoriesIntoKey(fcNormal, fcZero):
1557     category = fcInfinity;
1558     return opDivByZero;
1559
1560   case PackCategoriesIntoKey(fcInfinity, fcInfinity):
1561   case PackCategoriesIntoKey(fcZero, fcZero):
1562     makeNaN();
1563     return opInvalidOp;
1564
1565   case PackCategoriesIntoKey(fcNormal, fcNormal):
1566     return opOK;
1567   }
1568 }
1569
1570 APFloat::opStatus
1571 APFloat::modSpecials(const APFloat &rhs)
1572 {
1573   switch (PackCategoriesIntoKey(category, rhs.category)) {
1574   default:
1575     llvm_unreachable(nullptr);
1576
1577   case PackCategoriesIntoKey(fcNaN, fcZero):
1578   case PackCategoriesIntoKey(fcNaN, fcNormal):
1579   case PackCategoriesIntoKey(fcNaN, fcInfinity):
1580   case PackCategoriesIntoKey(fcNaN, fcNaN):
1581   case PackCategoriesIntoKey(fcZero, fcInfinity):
1582   case PackCategoriesIntoKey(fcZero, fcNormal):
1583   case PackCategoriesIntoKey(fcNormal, fcInfinity):
1584     return opOK;
1585
1586   case PackCategoriesIntoKey(fcZero, fcNaN):
1587   case PackCategoriesIntoKey(fcNormal, fcNaN):
1588   case PackCategoriesIntoKey(fcInfinity, fcNaN):
1589     sign = false;
1590     category = fcNaN;
1591     copySignificand(rhs);
1592     return opOK;
1593
1594   case PackCategoriesIntoKey(fcNormal, fcZero):
1595   case PackCategoriesIntoKey(fcInfinity, fcZero):
1596   case PackCategoriesIntoKey(fcInfinity, fcNormal):
1597   case PackCategoriesIntoKey(fcInfinity, fcInfinity):
1598   case PackCategoriesIntoKey(fcZero, fcZero):
1599     makeNaN();
1600     return opInvalidOp;
1601
1602   case PackCategoriesIntoKey(fcNormal, fcNormal):
1603     return opOK;
1604   }
1605 }
1606
1607 /* Change sign.  */
1608 void
1609 APFloat::changeSign()
1610 {
1611   /* Look mummy, this one's easy.  */
1612   sign = !sign;
1613 }
1614
1615 void
1616 APFloat::clearSign()
1617 {
1618   /* So is this one. */
1619   sign = 0;
1620 }
1621
1622 void
1623 APFloat::copySign(const APFloat &rhs)
1624 {
1625   /* And this one. */
1626   sign = rhs.sign;
1627 }
1628
1629 /* Normalized addition or subtraction.  */
1630 APFloat::opStatus
1631 APFloat::addOrSubtract(const APFloat &rhs, roundingMode rounding_mode,
1632                        bool subtract)
1633 {
1634   opStatus fs;
1635
1636   fs = addOrSubtractSpecials(rhs, subtract);
1637
1638   /* This return code means it was not a simple case.  */
1639   if (fs == opDivByZero) {
1640     lostFraction lost_fraction;
1641
1642     lost_fraction = addOrSubtractSignificand(rhs, subtract);
1643     fs = normalize(rounding_mode, lost_fraction);
1644
1645     /* Can only be zero if we lost no fraction.  */
1646     assert(category != fcZero || lost_fraction == lfExactlyZero);
1647   }
1648
1649   /* If two numbers add (exactly) to zero, IEEE 754 decrees it is a
1650      positive zero unless rounding to minus infinity, except that
1651      adding two like-signed zeroes gives that zero.  */
1652   if (category == fcZero) {
1653     if (rhs.category != fcZero || (sign == rhs.sign) == subtract)
1654       sign = (rounding_mode == rmTowardNegative);
1655   }
1656
1657   return fs;
1658 }
1659
1660 /* Normalized addition.  */
1661 APFloat::opStatus
1662 APFloat::add(const APFloat &rhs, roundingMode rounding_mode)
1663 {
1664   return addOrSubtract(rhs, rounding_mode, false);
1665 }
1666
1667 /* Normalized subtraction.  */
1668 APFloat::opStatus
1669 APFloat::subtract(const APFloat &rhs, roundingMode rounding_mode)
1670 {
1671   return addOrSubtract(rhs, rounding_mode, true);
1672 }
1673
1674 /* Normalized multiply.  */
1675 APFloat::opStatus
1676 APFloat::multiply(const APFloat &rhs, roundingMode rounding_mode)
1677 {
1678   opStatus fs;
1679
1680   sign ^= rhs.sign;
1681   fs = multiplySpecials(rhs);
1682
1683   if (isFiniteNonZero()) {
1684     lostFraction lost_fraction = multiplySignificand(rhs, nullptr);
1685     fs = normalize(rounding_mode, lost_fraction);
1686     if (lost_fraction != lfExactlyZero)
1687       fs = (opStatus) (fs | opInexact);
1688   }
1689
1690   return fs;
1691 }
1692
1693 /* Normalized divide.  */
1694 APFloat::opStatus
1695 APFloat::divide(const APFloat &rhs, roundingMode rounding_mode)
1696 {
1697   opStatus fs;
1698
1699   sign ^= rhs.sign;
1700   fs = divideSpecials(rhs);
1701
1702   if (isFiniteNonZero()) {
1703     lostFraction lost_fraction = divideSignificand(rhs);
1704     fs = normalize(rounding_mode, lost_fraction);
1705     if (lost_fraction != lfExactlyZero)
1706       fs = (opStatus) (fs | opInexact);
1707   }
1708
1709   return fs;
1710 }
1711
1712 /* Normalized remainder.  This is not currently correct in all cases.  */
1713 APFloat::opStatus
1714 APFloat::remainder(const APFloat &rhs)
1715 {
1716   opStatus fs;
1717   APFloat V = *this;
1718   unsigned int origSign = sign;
1719
1720   fs = V.divide(rhs, rmNearestTiesToEven);
1721   if (fs == opDivByZero)
1722     return fs;
1723
1724   int parts = partCount();
1725   integerPart *x = new integerPart[parts];
1726   bool ignored;
1727   fs = V.convertToInteger(x, parts * integerPartWidth, true,
1728                           rmNearestTiesToEven, &ignored);
1729   if (fs==opInvalidOp)
1730     return fs;
1731
1732   fs = V.convertFromZeroExtendedInteger(x, parts * integerPartWidth, true,
1733                                         rmNearestTiesToEven);
1734   assert(fs==opOK);   // should always work
1735
1736   fs = V.multiply(rhs, rmNearestTiesToEven);
1737   assert(fs==opOK || fs==opInexact);   // should not overflow or underflow
1738
1739   fs = subtract(V, rmNearestTiesToEven);
1740   assert(fs==opOK || fs==opInexact);   // likewise
1741
1742   if (isZero())
1743     sign = origSign;    // IEEE754 requires this
1744   delete[] x;
1745   return fs;
1746 }
1747
1748 /* Normalized llvm frem (C fmod).
1749    This is not currently correct in all cases.  */
1750 APFloat::opStatus
1751 APFloat::mod(const APFloat &rhs, roundingMode rounding_mode)
1752 {
1753   opStatus fs;
1754   fs = modSpecials(rhs);
1755
1756   if (isFiniteNonZero() && rhs.isFiniteNonZero()) {
1757     APFloat V = *this;
1758     unsigned int origSign = sign;
1759
1760     fs = V.divide(rhs, rmNearestTiesToEven);
1761     if (fs == opDivByZero)
1762       return fs;
1763
1764     int parts = partCount();
1765     integerPart *x = new integerPart[parts];
1766     bool ignored;
1767     fs = V.convertToInteger(x, parts * integerPartWidth, true,
1768                             rmTowardZero, &ignored);
1769     if (fs==opInvalidOp)
1770       return fs;
1771
1772     fs = V.convertFromZeroExtendedInteger(x, parts * integerPartWidth, true,
1773                                           rmNearestTiesToEven);
1774     assert(fs==opOK);   // should always work
1775
1776     fs = V.multiply(rhs, rounding_mode);
1777     assert(fs==opOK || fs==opInexact);   // should not overflow or underflow
1778
1779     fs = subtract(V, rounding_mode);
1780     assert(fs==opOK || fs==opInexact);   // likewise
1781
1782     if (isZero())
1783       sign = origSign;    // IEEE754 requires this
1784     delete[] x;
1785   }
1786   return fs;
1787 }
1788
1789 /* Normalized fused-multiply-add.  */
1790 APFloat::opStatus
1791 APFloat::fusedMultiplyAdd(const APFloat &multiplicand,
1792                           const APFloat &addend,
1793                           roundingMode rounding_mode)
1794 {
1795   opStatus fs;
1796
1797   /* Post-multiplication sign, before addition.  */
1798   sign ^= multiplicand.sign;
1799
1800   /* If and only if all arguments are normal do we need to do an
1801      extended-precision calculation.  */
1802   if (isFiniteNonZero() &&
1803       multiplicand.isFiniteNonZero() &&
1804       addend.isFiniteNonZero()) {
1805     lostFraction lost_fraction;
1806
1807     lost_fraction = multiplySignificand(multiplicand, &addend);
1808     fs = normalize(rounding_mode, lost_fraction);
1809     if (lost_fraction != lfExactlyZero)
1810       fs = (opStatus) (fs | opInexact);
1811
1812     /* If two numbers add (exactly) to zero, IEEE 754 decrees it is a
1813        positive zero unless rounding to minus infinity, except that
1814        adding two like-signed zeroes gives that zero.  */
1815     if (category == fcZero && sign != addend.sign)
1816       sign = (rounding_mode == rmTowardNegative);
1817   } else {
1818     fs = multiplySpecials(multiplicand);
1819
1820     /* FS can only be opOK or opInvalidOp.  There is no more work
1821        to do in the latter case.  The IEEE-754R standard says it is
1822        implementation-defined in this case whether, if ADDEND is a
1823        quiet NaN, we raise invalid op; this implementation does so.
1824
1825        If we need to do the addition we can do so with normal
1826        precision.  */
1827     if (fs == opOK)
1828       fs = addOrSubtract(addend, rounding_mode, false);
1829   }
1830
1831   return fs;
1832 }
1833
1834 /* Rounding-mode corrrect round to integral value.  */
1835 APFloat::opStatus APFloat::roundToIntegral(roundingMode rounding_mode) {
1836   opStatus fs;
1837
1838   // If the exponent is large enough, we know that this value is already
1839   // integral, and the arithmetic below would potentially cause it to saturate
1840   // to +/-Inf.  Bail out early instead.
1841   if (isFiniteNonZero() && exponent+1 >= (int)semanticsPrecision(*semantics))
1842     return opOK;
1843
1844   // The algorithm here is quite simple: we add 2^(p-1), where p is the
1845   // precision of our format, and then subtract it back off again.  The choice
1846   // of rounding modes for the addition/subtraction determines the rounding mode
1847   // for our integral rounding as well.
1848   // NOTE: When the input value is negative, we do subtraction followed by
1849   // addition instead.
1850   APInt IntegerConstant(NextPowerOf2(semanticsPrecision(*semantics)), 1);
1851   IntegerConstant <<= semanticsPrecision(*semantics)-1;
1852   APFloat MagicConstant(*semantics);
1853   fs = MagicConstant.convertFromAPInt(IntegerConstant, false,
1854                                       rmNearestTiesToEven);
1855   MagicConstant.copySign(*this);
1856
1857   if (fs != opOK)
1858     return fs;
1859
1860   // Preserve the input sign so that we can handle 0.0/-0.0 cases correctly.
1861   bool inputSign = isNegative();
1862
1863   fs = add(MagicConstant, rounding_mode);
1864   if (fs != opOK && fs != opInexact)
1865     return fs;
1866
1867   fs = subtract(MagicConstant, rounding_mode);
1868
1869   // Restore the input sign.
1870   if (inputSign != isNegative())
1871     changeSign();
1872
1873   return fs;
1874 }
1875
1876
1877 /* Comparison requires normalized numbers.  */
1878 APFloat::cmpResult
1879 APFloat::compare(const APFloat &rhs) const
1880 {
1881   cmpResult result;
1882
1883   assert(semantics == rhs.semantics);
1884
1885   switch (PackCategoriesIntoKey(category, rhs.category)) {
1886   default:
1887     llvm_unreachable(nullptr);
1888
1889   case PackCategoriesIntoKey(fcNaN, fcZero):
1890   case PackCategoriesIntoKey(fcNaN, fcNormal):
1891   case PackCategoriesIntoKey(fcNaN, fcInfinity):
1892   case PackCategoriesIntoKey(fcNaN, fcNaN):
1893   case PackCategoriesIntoKey(fcZero, fcNaN):
1894   case PackCategoriesIntoKey(fcNormal, fcNaN):
1895   case PackCategoriesIntoKey(fcInfinity, fcNaN):
1896     return cmpUnordered;
1897
1898   case PackCategoriesIntoKey(fcInfinity, fcNormal):
1899   case PackCategoriesIntoKey(fcInfinity, fcZero):
1900   case PackCategoriesIntoKey(fcNormal, fcZero):
1901     if (sign)
1902       return cmpLessThan;
1903     else
1904       return cmpGreaterThan;
1905
1906   case PackCategoriesIntoKey(fcNormal, fcInfinity):
1907   case PackCategoriesIntoKey(fcZero, fcInfinity):
1908   case PackCategoriesIntoKey(fcZero, fcNormal):
1909     if (rhs.sign)
1910       return cmpGreaterThan;
1911     else
1912       return cmpLessThan;
1913
1914   case PackCategoriesIntoKey(fcInfinity, fcInfinity):
1915     if (sign == rhs.sign)
1916       return cmpEqual;
1917     else if (sign)
1918       return cmpLessThan;
1919     else
1920       return cmpGreaterThan;
1921
1922   case PackCategoriesIntoKey(fcZero, fcZero):
1923     return cmpEqual;
1924
1925   case PackCategoriesIntoKey(fcNormal, fcNormal):
1926     break;
1927   }
1928
1929   /* Two normal numbers.  Do they have the same sign?  */
1930   if (sign != rhs.sign) {
1931     if (sign)
1932       result = cmpLessThan;
1933     else
1934       result = cmpGreaterThan;
1935   } else {
1936     /* Compare absolute values; invert result if negative.  */
1937     result = compareAbsoluteValue(rhs);
1938
1939     if (sign) {
1940       if (result == cmpLessThan)
1941         result = cmpGreaterThan;
1942       else if (result == cmpGreaterThan)
1943         result = cmpLessThan;
1944     }
1945   }
1946
1947   return result;
1948 }
1949
1950 /// APFloat::convert - convert a value of one floating point type to another.
1951 /// The return value corresponds to the IEEE754 exceptions.  *losesInfo
1952 /// records whether the transformation lost information, i.e. whether
1953 /// converting the result back to the original type will produce the
1954 /// original value (this is almost the same as return value==fsOK, but there
1955 /// are edge cases where this is not so).
1956
1957 APFloat::opStatus
1958 APFloat::convert(const fltSemantics &toSemantics,
1959                  roundingMode rounding_mode, bool *losesInfo)
1960 {
1961   lostFraction lostFraction;
1962   unsigned int newPartCount, oldPartCount;
1963   opStatus fs;
1964   int shift;
1965   const fltSemantics &fromSemantics = *semantics;
1966
1967   lostFraction = lfExactlyZero;
1968   newPartCount = partCountForBits(toSemantics.precision + 1);
1969   oldPartCount = partCount();
1970   shift = toSemantics.precision - fromSemantics.precision;
1971
1972   bool X86SpecialNan = false;
1973   if (&fromSemantics == &APFloat::x87DoubleExtended &&
1974       &toSemantics != &APFloat::x87DoubleExtended && category == fcNaN &&
1975       (!(*significandParts() & 0x8000000000000000ULL) ||
1976        !(*significandParts() & 0x4000000000000000ULL))) {
1977     // x86 has some unusual NaNs which cannot be represented in any other
1978     // format; note them here.
1979     X86SpecialNan = true;
1980   }
1981
1982   // If this is a truncation of a denormal number, and the target semantics
1983   // has larger exponent range than the source semantics (this can happen
1984   // when truncating from PowerPC double-double to double format), the
1985   // right shift could lose result mantissa bits.  Adjust exponent instead
1986   // of performing excessive shift.
1987   if (shift < 0 && isFiniteNonZero()) {
1988     int exponentChange = significandMSB() + 1 - fromSemantics.precision;
1989     if (exponent + exponentChange < toSemantics.minExponent)
1990       exponentChange = toSemantics.minExponent - exponent;
1991     if (exponentChange < shift)
1992       exponentChange = shift;
1993     if (exponentChange < 0) {
1994       shift -= exponentChange;
1995       exponent += exponentChange;
1996     }
1997   }
1998
1999   // If this is a truncation, perform the shift before we narrow the storage.
2000   if (shift < 0 && (isFiniteNonZero() || category==fcNaN))
2001     lostFraction = shiftRight(significandParts(), oldPartCount, -shift);
2002
2003   // Fix the storage so it can hold to new value.
2004   if (newPartCount > oldPartCount) {
2005     // The new type requires more storage; make it available.
2006     integerPart *newParts;
2007     newParts = new integerPart[newPartCount];
2008     APInt::tcSet(newParts, 0, newPartCount);
2009     if (isFiniteNonZero() || category==fcNaN)
2010       APInt::tcAssign(newParts, significandParts(), oldPartCount);
2011     freeSignificand();
2012     significand.parts = newParts;
2013   } else if (newPartCount == 1 && oldPartCount != 1) {
2014     // Switch to built-in storage for a single part.
2015     integerPart newPart = 0;
2016     if (isFiniteNonZero() || category==fcNaN)
2017       newPart = significandParts()[0];
2018     freeSignificand();
2019     significand.part = newPart;
2020   }
2021
2022   // Now that we have the right storage, switch the semantics.
2023   semantics = &toSemantics;
2024
2025   // If this is an extension, perform the shift now that the storage is
2026   // available.
2027   if (shift > 0 && (isFiniteNonZero() || category==fcNaN))
2028     APInt::tcShiftLeft(significandParts(), newPartCount, shift);
2029
2030   if (isFiniteNonZero()) {
2031     fs = normalize(rounding_mode, lostFraction);
2032     *losesInfo = (fs != opOK);
2033   } else if (category == fcNaN) {
2034     *losesInfo = lostFraction != lfExactlyZero || X86SpecialNan;
2035
2036     // For x87 extended precision, we want to make a NaN, not a special NaN if
2037     // the input wasn't special either.
2038     if (!X86SpecialNan && semantics == &APFloat::x87DoubleExtended)
2039       APInt::tcSetBit(significandParts(), semantics->precision - 1);
2040
2041     // gcc forces the Quiet bit on, which means (float)(double)(float_sNan)
2042     // does not give you back the same bits.  This is dubious, and we
2043     // don't currently do it.  You're really supposed to get
2044     // an invalid operation signal at runtime, but nobody does that.
2045     fs = opOK;
2046   } else {
2047     *losesInfo = false;
2048     fs = opOK;
2049   }
2050
2051   return fs;
2052 }
2053
2054 /* Convert a floating point number to an integer according to the
2055    rounding mode.  If the rounded integer value is out of range this
2056    returns an invalid operation exception and the contents of the
2057    destination parts are unspecified.  If the rounded value is in
2058    range but the floating point number is not the exact integer, the C
2059    standard doesn't require an inexact exception to be raised.  IEEE
2060    854 does require it so we do that.
2061
2062    Note that for conversions to integer type the C standard requires
2063    round-to-zero to always be used.  */
2064 APFloat::opStatus
2065 APFloat::convertToSignExtendedInteger(integerPart *parts, unsigned int width,
2066                                       bool isSigned,
2067                                       roundingMode rounding_mode,
2068                                       bool *isExact) const
2069 {
2070   lostFraction lost_fraction;
2071   const integerPart *src;
2072   unsigned int dstPartsCount, truncatedBits;
2073
2074   *isExact = false;
2075
2076   /* Handle the three special cases first.  */
2077   if (category == fcInfinity || category == fcNaN)
2078     return opInvalidOp;
2079
2080   dstPartsCount = partCountForBits(width);
2081
2082   if (category == fcZero) {
2083     APInt::tcSet(parts, 0, dstPartsCount);
2084     // Negative zero can't be represented as an int.
2085     *isExact = !sign;
2086     return opOK;
2087   }
2088
2089   src = significandParts();
2090
2091   /* Step 1: place our absolute value, with any fraction truncated, in
2092      the destination.  */
2093   if (exponent < 0) {
2094     /* Our absolute value is less than one; truncate everything.  */
2095     APInt::tcSet(parts, 0, dstPartsCount);
2096     /* For exponent -1 the integer bit represents .5, look at that.
2097        For smaller exponents leftmost truncated bit is 0. */
2098     truncatedBits = semantics->precision -1U - exponent;
2099   } else {
2100     /* We want the most significant (exponent + 1) bits; the rest are
2101        truncated.  */
2102     unsigned int bits = exponent + 1U;
2103
2104     /* Hopelessly large in magnitude?  */
2105     if (bits > width)
2106       return opInvalidOp;
2107
2108     if (bits < semantics->precision) {
2109       /* We truncate (semantics->precision - bits) bits.  */
2110       truncatedBits = semantics->precision - bits;
2111       APInt::tcExtract(parts, dstPartsCount, src, bits, truncatedBits);
2112     } else {
2113       /* We want at least as many bits as are available.  */
2114       APInt::tcExtract(parts, dstPartsCount, src, semantics->precision, 0);
2115       APInt::tcShiftLeft(parts, dstPartsCount, bits - semantics->precision);
2116       truncatedBits = 0;
2117     }
2118   }
2119
2120   /* Step 2: work out any lost fraction, and increment the absolute
2121      value if we would round away from zero.  */
2122   if (truncatedBits) {
2123     lost_fraction = lostFractionThroughTruncation(src, partCount(),
2124                                                   truncatedBits);
2125     if (lost_fraction != lfExactlyZero &&
2126         roundAwayFromZero(rounding_mode, lost_fraction, truncatedBits)) {
2127       if (APInt::tcIncrement(parts, dstPartsCount))
2128         return opInvalidOp;     /* Overflow.  */
2129     }
2130   } else {
2131     lost_fraction = lfExactlyZero;
2132   }
2133
2134   /* Step 3: check if we fit in the destination.  */
2135   unsigned int omsb = APInt::tcMSB(parts, dstPartsCount) + 1;
2136
2137   if (sign) {
2138     if (!isSigned) {
2139       /* Negative numbers cannot be represented as unsigned.  */
2140       if (omsb != 0)
2141         return opInvalidOp;
2142     } else {
2143       /* It takes omsb bits to represent the unsigned integer value.
2144          We lose a bit for the sign, but care is needed as the
2145          maximally negative integer is a special case.  */
2146       if (omsb == width && APInt::tcLSB(parts, dstPartsCount) + 1 != omsb)
2147         return opInvalidOp;
2148
2149       /* This case can happen because of rounding.  */
2150       if (omsb > width)
2151         return opInvalidOp;
2152     }
2153
2154     APInt::tcNegate (parts, dstPartsCount);
2155   } else {
2156     if (omsb >= width + !isSigned)
2157       return opInvalidOp;
2158   }
2159
2160   if (lost_fraction == lfExactlyZero) {
2161     *isExact = true;
2162     return opOK;
2163   } else
2164     return opInexact;
2165 }
2166
2167 /* Same as convertToSignExtendedInteger, except we provide
2168    deterministic values in case of an invalid operation exception,
2169    namely zero for NaNs and the minimal or maximal value respectively
2170    for underflow or overflow.
2171    The *isExact output tells whether the result is exact, in the sense
2172    that converting it back to the original floating point type produces
2173    the original value.  This is almost equivalent to result==opOK,
2174    except for negative zeroes.
2175 */
2176 APFloat::opStatus
2177 APFloat::convertToInteger(integerPart *parts, unsigned int width,
2178                           bool isSigned,
2179                           roundingMode rounding_mode, bool *isExact) const
2180 {
2181   opStatus fs;
2182
2183   fs = convertToSignExtendedInteger(parts, width, isSigned, rounding_mode,
2184                                     isExact);
2185
2186   if (fs == opInvalidOp) {
2187     unsigned int bits, dstPartsCount;
2188
2189     dstPartsCount = partCountForBits(width);
2190
2191     if (category == fcNaN)
2192       bits = 0;
2193     else if (sign)
2194       bits = isSigned;
2195     else
2196       bits = width - isSigned;
2197
2198     APInt::tcSetLeastSignificantBits(parts, dstPartsCount, bits);
2199     if (sign && isSigned)
2200       APInt::tcShiftLeft(parts, dstPartsCount, width - 1);
2201   }
2202
2203   return fs;
2204 }
2205
2206 /* Same as convertToInteger(integerPart*, ...), except the result is returned in
2207    an APSInt, whose initial bit-width and signed-ness are used to determine the
2208    precision of the conversion.
2209  */
2210 APFloat::opStatus
2211 APFloat::convertToInteger(APSInt &result,
2212                           roundingMode rounding_mode, bool *isExact) const
2213 {
2214   unsigned bitWidth = result.getBitWidth();
2215   SmallVector<uint64_t, 4> parts(result.getNumWords());
2216   opStatus status = convertToInteger(
2217     parts.data(), bitWidth, result.isSigned(), rounding_mode, isExact);
2218   // Keeps the original signed-ness.
2219   result = APInt(bitWidth, parts);
2220   return status;
2221 }
2222
2223 /* Convert an unsigned integer SRC to a floating point number,
2224    rounding according to ROUNDING_MODE.  The sign of the floating
2225    point number is not modified.  */
2226 APFloat::opStatus
2227 APFloat::convertFromUnsignedParts(const integerPart *src,
2228                                   unsigned int srcCount,
2229                                   roundingMode rounding_mode)
2230 {
2231   unsigned int omsb, precision, dstCount;
2232   integerPart *dst;
2233   lostFraction lost_fraction;
2234
2235   category = fcNormal;
2236   omsb = APInt::tcMSB(src, srcCount) + 1;
2237   dst = significandParts();
2238   dstCount = partCount();
2239   precision = semantics->precision;
2240
2241   /* We want the most significant PRECISION bits of SRC.  There may not
2242      be that many; extract what we can.  */
2243   if (precision <= omsb) {
2244     exponent = omsb - 1;
2245     lost_fraction = lostFractionThroughTruncation(src, srcCount,
2246                                                   omsb - precision);
2247     APInt::tcExtract(dst, dstCount, src, precision, omsb - precision);
2248   } else {
2249     exponent = precision - 1;
2250     lost_fraction = lfExactlyZero;
2251     APInt::tcExtract(dst, dstCount, src, omsb, 0);
2252   }
2253
2254   return normalize(rounding_mode, lost_fraction);
2255 }
2256
2257 APFloat::opStatus
2258 APFloat::convertFromAPInt(const APInt &Val,
2259                           bool isSigned,
2260                           roundingMode rounding_mode)
2261 {
2262   unsigned int partCount = Val.getNumWords();
2263   APInt api = Val;
2264
2265   sign = false;
2266   if (isSigned && api.isNegative()) {
2267     sign = true;
2268     api = -api;
2269   }
2270
2271   return convertFromUnsignedParts(api.getRawData(), partCount, rounding_mode);
2272 }
2273
2274 /* Convert a two's complement integer SRC to a floating point number,
2275    rounding according to ROUNDING_MODE.  ISSIGNED is true if the
2276    integer is signed, in which case it must be sign-extended.  */
2277 APFloat::opStatus
2278 APFloat::convertFromSignExtendedInteger(const integerPart *src,
2279                                         unsigned int srcCount,
2280                                         bool isSigned,
2281                                         roundingMode rounding_mode)
2282 {
2283   opStatus status;
2284
2285   if (isSigned &&
2286       APInt::tcExtractBit(src, srcCount * integerPartWidth - 1)) {
2287     integerPart *copy;
2288
2289     /* If we're signed and negative negate a copy.  */
2290     sign = true;
2291     copy = new integerPart[srcCount];
2292     APInt::tcAssign(copy, src, srcCount);
2293     APInt::tcNegate(copy, srcCount);
2294     status = convertFromUnsignedParts(copy, srcCount, rounding_mode);
2295     delete [] copy;
2296   } else {
2297     sign = false;
2298     status = convertFromUnsignedParts(src, srcCount, rounding_mode);
2299   }
2300
2301   return status;
2302 }
2303
2304 /* FIXME: should this just take a const APInt reference?  */
2305 APFloat::opStatus
2306 APFloat::convertFromZeroExtendedInteger(const integerPart *parts,
2307                                         unsigned int width, bool isSigned,
2308                                         roundingMode rounding_mode)
2309 {
2310   unsigned int partCount = partCountForBits(width);
2311   APInt api = APInt(width, makeArrayRef(parts, partCount));
2312
2313   sign = false;
2314   if (isSigned && APInt::tcExtractBit(parts, width - 1)) {
2315     sign = true;
2316     api = -api;
2317   }
2318
2319   return convertFromUnsignedParts(api.getRawData(), partCount, rounding_mode);
2320 }
2321
2322 APFloat::opStatus
2323 APFloat::convertFromHexadecimalString(StringRef s, roundingMode rounding_mode)
2324 {
2325   lostFraction lost_fraction = lfExactlyZero;
2326
2327   category = fcNormal;
2328   zeroSignificand();
2329   exponent = 0;
2330
2331   integerPart *significand = significandParts();
2332   unsigned partsCount = partCount();
2333   unsigned bitPos = partsCount * integerPartWidth;
2334   bool computedTrailingFraction = false;
2335
2336   // Skip leading zeroes and any (hexa)decimal point.
2337   StringRef::iterator begin = s.begin();
2338   StringRef::iterator end = s.end();
2339   StringRef::iterator dot;
2340   StringRef::iterator p = skipLeadingZeroesAndAnyDot(begin, end, &dot);
2341   StringRef::iterator firstSignificantDigit = p;
2342
2343   while (p != end) {
2344     integerPart hex_value;
2345
2346     if (*p == '.') {
2347       assert(dot == end && "String contains multiple dots");
2348       dot = p++;
2349       continue;
2350     }
2351
2352     hex_value = hexDigitValue(*p);
2353     if (hex_value == -1U)
2354       break;
2355
2356     p++;
2357
2358     // Store the number while we have space.
2359     if (bitPos) {
2360       bitPos -= 4;
2361       hex_value <<= bitPos % integerPartWidth;
2362       significand[bitPos / integerPartWidth] |= hex_value;
2363     } else if (!computedTrailingFraction) {
2364       lost_fraction = trailingHexadecimalFraction(p, end, hex_value);
2365       computedTrailingFraction = true;
2366     }
2367   }
2368
2369   /* Hex floats require an exponent but not a hexadecimal point.  */
2370   assert(p != end && "Hex strings require an exponent");
2371   assert((*p == 'p' || *p == 'P') && "Invalid character in significand");
2372   assert(p != begin && "Significand has no digits");
2373   assert((dot == end || p - begin != 1) && "Significand has no digits");
2374
2375   /* Ignore the exponent if we are zero.  */
2376   if (p != firstSignificantDigit) {
2377     int expAdjustment;
2378
2379     /* Implicit hexadecimal point?  */
2380     if (dot == end)
2381       dot = p;
2382
2383     /* Calculate the exponent adjustment implicit in the number of
2384        significant digits.  */
2385     expAdjustment = static_cast<int>(dot - firstSignificantDigit);
2386     if (expAdjustment < 0)
2387       expAdjustment++;
2388     expAdjustment = expAdjustment * 4 - 1;
2389
2390     /* Adjust for writing the significand starting at the most
2391        significant nibble.  */
2392     expAdjustment += semantics->precision;
2393     expAdjustment -= partsCount * integerPartWidth;
2394
2395     /* Adjust for the given exponent.  */
2396     exponent = totalExponent(p + 1, end, expAdjustment);
2397   }
2398
2399   return normalize(rounding_mode, lost_fraction);
2400 }
2401
2402 APFloat::opStatus
2403 APFloat::roundSignificandWithExponent(const integerPart *decSigParts,
2404                                       unsigned sigPartCount, int exp,
2405                                       roundingMode rounding_mode)
2406 {
2407   unsigned int parts, pow5PartCount;
2408   fltSemantics calcSemantics = { 32767, -32767, 0 };
2409   integerPart pow5Parts[maxPowerOfFiveParts];
2410   bool isNearest;
2411
2412   isNearest = (rounding_mode == rmNearestTiesToEven ||
2413                rounding_mode == rmNearestTiesToAway);
2414
2415   parts = partCountForBits(semantics->precision + 11);
2416
2417   /* Calculate pow(5, abs(exp)).  */
2418   pow5PartCount = powerOf5(pow5Parts, exp >= 0 ? exp: -exp);
2419
2420   for (;; parts *= 2) {
2421     opStatus sigStatus, powStatus;
2422     unsigned int excessPrecision, truncatedBits;
2423
2424     calcSemantics.precision = parts * integerPartWidth - 1;
2425     excessPrecision = calcSemantics.precision - semantics->precision;
2426     truncatedBits = excessPrecision;
2427
2428     APFloat decSig = APFloat::getZero(calcSemantics, sign);
2429     APFloat pow5(calcSemantics);
2430
2431     sigStatus = decSig.convertFromUnsignedParts(decSigParts, sigPartCount,
2432                                                 rmNearestTiesToEven);
2433     powStatus = pow5.convertFromUnsignedParts(pow5Parts, pow5PartCount,
2434                                               rmNearestTiesToEven);
2435     /* Add exp, as 10^n = 5^n * 2^n.  */
2436     decSig.exponent += exp;
2437
2438     lostFraction calcLostFraction;
2439     integerPart HUerr, HUdistance;
2440     unsigned int powHUerr;
2441
2442     if (exp >= 0) {
2443       /* multiplySignificand leaves the precision-th bit set to 1.  */
2444       calcLostFraction = decSig.multiplySignificand(pow5, nullptr);
2445       powHUerr = powStatus != opOK;
2446     } else {
2447       calcLostFraction = decSig.divideSignificand(pow5);
2448       /* Denormal numbers have less precision.  */
2449       if (decSig.exponent < semantics->minExponent) {
2450         excessPrecision += (semantics->minExponent - decSig.exponent);
2451         truncatedBits = excessPrecision;
2452         if (excessPrecision > calcSemantics.precision)
2453           excessPrecision = calcSemantics.precision;
2454       }
2455       /* Extra half-ulp lost in reciprocal of exponent.  */
2456       powHUerr = (powStatus == opOK && calcLostFraction == lfExactlyZero) ? 0:2;
2457     }
2458
2459     /* Both multiplySignificand and divideSignificand return the
2460        result with the integer bit set.  */
2461     assert(APInt::tcExtractBit
2462            (decSig.significandParts(), calcSemantics.precision - 1) == 1);
2463
2464     HUerr = HUerrBound(calcLostFraction != lfExactlyZero, sigStatus != opOK,
2465                        powHUerr);
2466     HUdistance = 2 * ulpsFromBoundary(decSig.significandParts(),
2467                                       excessPrecision, isNearest);
2468
2469     /* Are we guaranteed to round correctly if we truncate?  */
2470     if (HUdistance >= HUerr) {
2471       APInt::tcExtract(significandParts(), partCount(), decSig.significandParts(),
2472                        calcSemantics.precision - excessPrecision,
2473                        excessPrecision);
2474       /* Take the exponent of decSig.  If we tcExtract-ed less bits
2475          above we must adjust our exponent to compensate for the
2476          implicit right shift.  */
2477       exponent = (decSig.exponent + semantics->precision
2478                   - (calcSemantics.precision - excessPrecision));
2479       calcLostFraction = lostFractionThroughTruncation(decSig.significandParts(),
2480                                                        decSig.partCount(),
2481                                                        truncatedBits);
2482       return normalize(rounding_mode, calcLostFraction);
2483     }
2484   }
2485 }
2486
2487 APFloat::opStatus
2488 APFloat::convertFromDecimalString(StringRef str, roundingMode rounding_mode)
2489 {
2490   decimalInfo D;
2491   opStatus fs;
2492
2493   /* Scan the text.  */
2494   StringRef::iterator p = str.begin();
2495   interpretDecimal(p, str.end(), &D);
2496
2497   /* Handle the quick cases.  First the case of no significant digits,
2498      i.e. zero, and then exponents that are obviously too large or too
2499      small.  Writing L for log 10 / log 2, a number d.ddddd*10^exp
2500      definitely overflows if
2501
2502            (exp - 1) * L >= maxExponent
2503
2504      and definitely underflows to zero where
2505
2506            (exp + 1) * L <= minExponent - precision
2507
2508      With integer arithmetic the tightest bounds for L are
2509
2510            93/28 < L < 196/59            [ numerator <= 256 ]
2511            42039/12655 < L < 28738/8651  [ numerator <= 65536 ]
2512   */
2513
2514   // Test if we have a zero number allowing for strings with no null terminators
2515   // and zero decimals with non-zero exponents.
2516   //
2517   // We computed firstSigDigit by ignoring all zeros and dots. Thus if
2518   // D->firstSigDigit equals str.end(), every digit must be a zero and there can
2519   // be at most one dot. On the other hand, if we have a zero with a non-zero
2520   // exponent, then we know that D.firstSigDigit will be non-numeric.
2521   if (D.firstSigDigit == str.end() || decDigitValue(*D.firstSigDigit) >= 10U) {
2522     category = fcZero;
2523     fs = opOK;
2524
2525   /* Check whether the normalized exponent is high enough to overflow
2526      max during the log-rebasing in the max-exponent check below. */
2527   } else if (D.normalizedExponent - 1 > INT_MAX / 42039) {
2528     fs = handleOverflow(rounding_mode);
2529
2530   /* If it wasn't, then it also wasn't high enough to overflow max
2531      during the log-rebasing in the min-exponent check.  Check that it
2532      won't overflow min in either check, then perform the min-exponent
2533      check. */
2534   } else if (D.normalizedExponent - 1 < INT_MIN / 42039 ||
2535              (D.normalizedExponent + 1) * 28738 <=
2536                8651 * (semantics->minExponent - (int) semantics->precision)) {
2537     /* Underflow to zero and round.  */
2538     category = fcNormal;
2539     zeroSignificand();
2540     fs = normalize(rounding_mode, lfLessThanHalf);
2541
2542   /* We can finally safely perform the max-exponent check. */
2543   } else if ((D.normalizedExponent - 1) * 42039
2544              >= 12655 * semantics->maxExponent) {
2545     /* Overflow and round.  */
2546     fs = handleOverflow(rounding_mode);
2547   } else {
2548     integerPart *decSignificand;
2549     unsigned int partCount;
2550
2551     /* A tight upper bound on number of bits required to hold an
2552        N-digit decimal integer is N * 196 / 59.  Allocate enough space
2553        to hold the full significand, and an extra part required by
2554        tcMultiplyPart.  */
2555     partCount = static_cast<unsigned int>(D.lastSigDigit - D.firstSigDigit) + 1;
2556     partCount = partCountForBits(1 + 196 * partCount / 59);
2557     decSignificand = new integerPart[partCount + 1];
2558     partCount = 0;
2559
2560     /* Convert to binary efficiently - we do almost all multiplication
2561        in an integerPart.  When this would overflow do we do a single
2562        bignum multiplication, and then revert again to multiplication
2563        in an integerPart.  */
2564     do {
2565       integerPart decValue, val, multiplier;
2566
2567       val = 0;
2568       multiplier = 1;
2569
2570       do {
2571         if (*p == '.') {
2572           p++;
2573           if (p == str.end()) {
2574             break;
2575           }
2576         }
2577         decValue = decDigitValue(*p++);
2578         assert(decValue < 10U && "Invalid character in significand");
2579         multiplier *= 10;
2580         val = val * 10 + decValue;
2581         /* The maximum number that can be multiplied by ten with any
2582            digit added without overflowing an integerPart.  */
2583       } while (p <= D.lastSigDigit && multiplier <= (~ (integerPart) 0 - 9) / 10);
2584
2585       /* Multiply out the current part.  */
2586       APInt::tcMultiplyPart(decSignificand, decSignificand, multiplier, val,
2587                             partCount, partCount + 1, false);
2588
2589       /* If we used another part (likely but not guaranteed), increase
2590          the count.  */
2591       if (decSignificand[partCount])
2592         partCount++;
2593     } while (p <= D.lastSigDigit);
2594
2595     category = fcNormal;
2596     fs = roundSignificandWithExponent(decSignificand, partCount,
2597                                       D.exponent, rounding_mode);
2598
2599     delete [] decSignificand;
2600   }
2601
2602   return fs;
2603 }
2604
2605 bool
2606 APFloat::convertFromStringSpecials(StringRef str) {
2607   if (str.equals("inf") || str.equals("INFINITY")) {
2608     makeInf(false);
2609     return true;
2610   }
2611
2612   if (str.equals("-inf") || str.equals("-INFINITY")) {
2613     makeInf(true);
2614     return true;
2615   }
2616
2617   if (str.equals("nan") || str.equals("NaN")) {
2618     makeNaN(false, false);
2619     return true;
2620   }
2621
2622   if (str.equals("-nan") || str.equals("-NaN")) {
2623     makeNaN(false, true);
2624     return true;
2625   }
2626
2627   return false;
2628 }
2629
2630 APFloat::opStatus
2631 APFloat::convertFromString(StringRef str, roundingMode rounding_mode)
2632 {
2633   assert(!str.empty() && "Invalid string length");
2634
2635   // Handle special cases.
2636   if (convertFromStringSpecials(str))
2637     return opOK;
2638
2639   /* Handle a leading minus sign.  */
2640   StringRef::iterator p = str.begin();
2641   size_t slen = str.size();
2642   sign = *p == '-' ? 1 : 0;
2643   if (*p == '-' || *p == '+') {
2644     p++;
2645     slen--;
2646     assert(slen && "String has no digits");
2647   }
2648
2649   if (slen >= 2 && p[0] == '0' && (p[1] == 'x' || p[1] == 'X')) {
2650     assert(slen - 2 && "Invalid string");
2651     return convertFromHexadecimalString(StringRef(p + 2, slen - 2),
2652                                         rounding_mode);
2653   }
2654
2655   return convertFromDecimalString(StringRef(p, slen), rounding_mode);
2656 }
2657
2658 /* Write out a hexadecimal representation of the floating point value
2659    to DST, which must be of sufficient size, in the C99 form
2660    [-]0xh.hhhhp[+-]d.  Return the number of characters written,
2661    excluding the terminating NUL.
2662
2663    If UPPERCASE, the output is in upper case, otherwise in lower case.
2664
2665    HEXDIGITS digits appear altogether, rounding the value if
2666    necessary.  If HEXDIGITS is 0, the minimal precision to display the
2667    number precisely is used instead.  If nothing would appear after
2668    the decimal point it is suppressed.
2669
2670    The decimal exponent is always printed and has at least one digit.
2671    Zero values display an exponent of zero.  Infinities and NaNs
2672    appear as "infinity" or "nan" respectively.
2673
2674    The above rules are as specified by C99.  There is ambiguity about
2675    what the leading hexadecimal digit should be.  This implementation
2676    uses whatever is necessary so that the exponent is displayed as
2677    stored.  This implies the exponent will fall within the IEEE format
2678    range, and the leading hexadecimal digit will be 0 (for denormals),
2679    1 (normal numbers) or 2 (normal numbers rounded-away-from-zero with
2680    any other digits zero).
2681 */
2682 unsigned int
2683 APFloat::convertToHexString(char *dst, unsigned int hexDigits,
2684                             bool upperCase, roundingMode rounding_mode) const
2685 {
2686   char *p;
2687
2688   p = dst;
2689   if (sign)
2690     *dst++ = '-';
2691
2692   switch (category) {
2693   case fcInfinity:
2694     memcpy (dst, upperCase ? infinityU: infinityL, sizeof infinityU - 1);
2695     dst += sizeof infinityL - 1;
2696     break;
2697
2698   case fcNaN:
2699     memcpy (dst, upperCase ? NaNU: NaNL, sizeof NaNU - 1);
2700     dst += sizeof NaNU - 1;
2701     break;
2702
2703   case fcZero:
2704     *dst++ = '0';
2705     *dst++ = upperCase ? 'X': 'x';
2706     *dst++ = '0';
2707     if (hexDigits > 1) {
2708       *dst++ = '.';
2709       memset (dst, '0', hexDigits - 1);
2710       dst += hexDigits - 1;
2711     }
2712     *dst++ = upperCase ? 'P': 'p';
2713     *dst++ = '0';
2714     break;
2715
2716   case fcNormal:
2717     dst = convertNormalToHexString (dst, hexDigits, upperCase, rounding_mode);
2718     break;
2719   }
2720
2721   *dst = 0;
2722
2723   return static_cast<unsigned int>(dst - p);
2724 }
2725
2726 /* Does the hard work of outputting the correctly rounded hexadecimal
2727    form of a normal floating point number with the specified number of
2728    hexadecimal digits.  If HEXDIGITS is zero the minimum number of
2729    digits necessary to print the value precisely is output.  */
2730 char *
2731 APFloat::convertNormalToHexString(char *dst, unsigned int hexDigits,
2732                                   bool upperCase,
2733                                   roundingMode rounding_mode) const
2734 {
2735   unsigned int count, valueBits, shift, partsCount, outputDigits;
2736   const char *hexDigitChars;
2737   const integerPart *significand;
2738   char *p;
2739   bool roundUp;
2740
2741   *dst++ = '0';
2742   *dst++ = upperCase ? 'X': 'x';
2743
2744   roundUp = false;
2745   hexDigitChars = upperCase ? hexDigitsUpper: hexDigitsLower;
2746
2747   significand = significandParts();
2748   partsCount = partCount();
2749
2750   /* +3 because the first digit only uses the single integer bit, so
2751      we have 3 virtual zero most-significant-bits.  */
2752   valueBits = semantics->precision + 3;
2753   shift = integerPartWidth - valueBits % integerPartWidth;
2754
2755   /* The natural number of digits required ignoring trailing
2756      insignificant zeroes.  */
2757   outputDigits = (valueBits - significandLSB () + 3) / 4;
2758
2759   /* hexDigits of zero means use the required number for the
2760      precision.  Otherwise, see if we are truncating.  If we are,
2761      find out if we need to round away from zero.  */
2762   if (hexDigits) {
2763     if (hexDigits < outputDigits) {
2764       /* We are dropping non-zero bits, so need to check how to round.
2765          "bits" is the number of dropped bits.  */
2766       unsigned int bits;
2767       lostFraction fraction;
2768
2769       bits = valueBits - hexDigits * 4;
2770       fraction = lostFractionThroughTruncation (significand, partsCount, bits);
2771       roundUp = roundAwayFromZero(rounding_mode, fraction, bits);
2772     }
2773     outputDigits = hexDigits;
2774   }
2775
2776   /* Write the digits consecutively, and start writing in the location
2777      of the hexadecimal point.  We move the most significant digit
2778      left and add the hexadecimal point later.  */
2779   p = ++dst;
2780
2781   count = (valueBits + integerPartWidth - 1) / integerPartWidth;
2782
2783   while (outputDigits && count) {
2784     integerPart part;
2785
2786     /* Put the most significant integerPartWidth bits in "part".  */
2787     if (--count == partsCount)
2788       part = 0;  /* An imaginary higher zero part.  */
2789     else
2790       part = significand[count] << shift;
2791
2792     if (count && shift)
2793       part |= significand[count - 1] >> (integerPartWidth - shift);
2794
2795     /* Convert as much of "part" to hexdigits as we can.  */
2796     unsigned int curDigits = integerPartWidth / 4;
2797
2798     if (curDigits > outputDigits)
2799       curDigits = outputDigits;
2800     dst += partAsHex (dst, part, curDigits, hexDigitChars);
2801     outputDigits -= curDigits;
2802   }
2803
2804   if (roundUp) {
2805     char *q = dst;
2806
2807     /* Note that hexDigitChars has a trailing '0'.  */
2808     do {
2809       q--;
2810       *q = hexDigitChars[hexDigitValue (*q) + 1];
2811     } while (*q == '0');
2812     assert(q >= p);
2813   } else {
2814     /* Add trailing zeroes.  */
2815     memset (dst, '0', outputDigits);
2816     dst += outputDigits;
2817   }
2818
2819   /* Move the most significant digit to before the point, and if there
2820      is something after the decimal point add it.  This must come
2821      after rounding above.  */
2822   p[-1] = p[0];
2823   if (dst -1 == p)
2824     dst--;
2825   else
2826     p[0] = '.';
2827
2828   /* Finally output the exponent.  */
2829   *dst++ = upperCase ? 'P': 'p';
2830
2831   return writeSignedDecimal (dst, exponent);
2832 }
2833
2834 hash_code llvm::hash_value(const APFloat &Arg) {
2835   if (!Arg.isFiniteNonZero())
2836     return hash_combine((uint8_t)Arg.category,
2837                         // NaN has no sign, fix it at zero.
2838                         Arg.isNaN() ? (uint8_t)0 : (uint8_t)Arg.sign,
2839                         Arg.semantics->precision);
2840
2841   // Normal floats need their exponent and significand hashed.
2842   return hash_combine((uint8_t)Arg.category, (uint8_t)Arg.sign,
2843                       Arg.semantics->precision, Arg.exponent,
2844                       hash_combine_range(
2845                         Arg.significandParts(),
2846                         Arg.significandParts() + Arg.partCount()));
2847 }
2848
2849 // Conversion from APFloat to/from host float/double.  It may eventually be
2850 // possible to eliminate these and have everybody deal with APFloats, but that
2851 // will take a while.  This approach will not easily extend to long double.
2852 // Current implementation requires integerPartWidth==64, which is correct at
2853 // the moment but could be made more general.
2854
2855 // Denormals have exponent minExponent in APFloat, but minExponent-1 in
2856 // the actual IEEE respresentations.  We compensate for that here.
2857
2858 APInt
2859 APFloat::convertF80LongDoubleAPFloatToAPInt() const
2860 {
2861   assert(semantics == (const llvm::fltSemantics*)&x87DoubleExtended);
2862   assert(partCount()==2);
2863
2864   uint64_t myexponent, mysignificand;
2865
2866   if (isFiniteNonZero()) {
2867     myexponent = exponent+16383; //bias
2868     mysignificand = significandParts()[0];
2869     if (myexponent==1 && !(mysignificand & 0x8000000000000000ULL))
2870       myexponent = 0;   // denormal
2871   } else if (category==fcZero) {
2872     myexponent = 0;
2873     mysignificand = 0;
2874   } else if (category==fcInfinity) {
2875     myexponent = 0x7fff;
2876     mysignificand = 0x8000000000000000ULL;
2877   } else {
2878     assert(category == fcNaN && "Unknown category");
2879     myexponent = 0x7fff;
2880     mysignificand = significandParts()[0];
2881   }
2882
2883   uint64_t words[2];
2884   words[0] = mysignificand;
2885   words[1] =  ((uint64_t)(sign & 1) << 15) |
2886               (myexponent & 0x7fffLL);
2887   return APInt(80, words);
2888 }
2889
2890 APInt
2891 APFloat::convertPPCDoubleDoubleAPFloatToAPInt() const
2892 {
2893   assert(semantics == (const llvm::fltSemantics*)&PPCDoubleDouble);
2894   assert(partCount()==2);
2895
2896   uint64_t words[2];
2897   opStatus fs;
2898   bool losesInfo;
2899
2900   // Convert number to double.  To avoid spurious underflows, we re-
2901   // normalize against the "double" minExponent first, and only *then*
2902   // truncate the mantissa.  The result of that second conversion
2903   // may be inexact, but should never underflow.
2904   // Declare fltSemantics before APFloat that uses it (and
2905   // saves pointer to it) to ensure correct destruction order.
2906   fltSemantics extendedSemantics = *semantics;
2907   extendedSemantics.minExponent = IEEEdouble.minExponent;
2908   APFloat extended(*this);
2909   fs = extended.convert(extendedSemantics, rmNearestTiesToEven, &losesInfo);
2910   assert(fs == opOK && !losesInfo);
2911   (void)fs;
2912
2913   APFloat u(extended);
2914   fs = u.convert(IEEEdouble, rmNearestTiesToEven, &losesInfo);
2915   assert(fs == opOK || fs == opInexact);
2916   (void)fs;
2917   words[0] = *u.convertDoubleAPFloatToAPInt().getRawData();
2918
2919   // If conversion was exact or resulted in a special case, we're done;
2920   // just set the second double to zero.  Otherwise, re-convert back to
2921   // the extended format and compute the difference.  This now should
2922   // convert exactly to double.
2923   if (u.isFiniteNonZero() && losesInfo) {
2924     fs = u.convert(extendedSemantics, rmNearestTiesToEven, &losesInfo);
2925     assert(fs == opOK && !losesInfo);
2926     (void)fs;
2927
2928     APFloat v(extended);
2929     v.subtract(u, rmNearestTiesToEven);
2930     fs = v.convert(IEEEdouble, rmNearestTiesToEven, &losesInfo);
2931     assert(fs == opOK && !losesInfo);
2932     (void)fs;
2933     words[1] = *v.convertDoubleAPFloatToAPInt().getRawData();
2934   } else {
2935     words[1] = 0;
2936   }
2937
2938   return APInt(128, words);
2939 }
2940
2941 APInt
2942 APFloat::convertQuadrupleAPFloatToAPInt() const
2943 {
2944   assert(semantics == (const llvm::fltSemantics*)&IEEEquad);
2945   assert(partCount()==2);
2946
2947   uint64_t myexponent, mysignificand, mysignificand2;
2948
2949   if (isFiniteNonZero()) {
2950     myexponent = exponent+16383; //bias
2951     mysignificand = significandParts()[0];
2952     mysignificand2 = significandParts()[1];
2953     if (myexponent==1 && !(mysignificand2 & 0x1000000000000LL))
2954       myexponent = 0;   // denormal
2955   } else if (category==fcZero) {
2956     myexponent = 0;
2957     mysignificand = mysignificand2 = 0;
2958   } else if (category==fcInfinity) {
2959     myexponent = 0x7fff;
2960     mysignificand = mysignificand2 = 0;
2961   } else {
2962     assert(category == fcNaN && "Unknown category!");
2963     myexponent = 0x7fff;
2964     mysignificand = significandParts()[0];
2965     mysignificand2 = significandParts()[1];
2966   }
2967
2968   uint64_t words[2];
2969   words[0] = mysignificand;
2970   words[1] = ((uint64_t)(sign & 1) << 63) |
2971              ((myexponent & 0x7fff) << 48) |
2972              (mysignificand2 & 0xffffffffffffLL);
2973
2974   return APInt(128, words);
2975 }
2976
2977 APInt
2978 APFloat::convertDoubleAPFloatToAPInt() const
2979 {
2980   assert(semantics == (const llvm::fltSemantics*)&IEEEdouble);
2981   assert(partCount()==1);
2982
2983   uint64_t myexponent, mysignificand;
2984
2985   if (isFiniteNonZero()) {
2986     myexponent = exponent+1023; //bias
2987     mysignificand = *significandParts();
2988     if (myexponent==1 && !(mysignificand & 0x10000000000000LL))
2989       myexponent = 0;   // denormal
2990   } else if (category==fcZero) {
2991     myexponent = 0;
2992     mysignificand = 0;
2993   } else if (category==fcInfinity) {
2994     myexponent = 0x7ff;
2995     mysignificand = 0;
2996   } else {
2997     assert(category == fcNaN && "Unknown category!");
2998     myexponent = 0x7ff;
2999     mysignificand = *significandParts();
3000   }
3001
3002   return APInt(64, ((((uint64_t)(sign & 1) << 63) |
3003                      ((myexponent & 0x7ff) <<  52) |
3004                      (mysignificand & 0xfffffffffffffLL))));
3005 }
3006
3007 APInt
3008 APFloat::convertFloatAPFloatToAPInt() const
3009 {
3010   assert(semantics == (const llvm::fltSemantics*)&IEEEsingle);
3011   assert(partCount()==1);
3012
3013   uint32_t myexponent, mysignificand;
3014
3015   if (isFiniteNonZero()) {
3016     myexponent = exponent+127; //bias
3017     mysignificand = (uint32_t)*significandParts();
3018     if (myexponent == 1 && !(mysignificand & 0x800000))
3019       myexponent = 0;   // denormal
3020   } else if (category==fcZero) {
3021     myexponent = 0;
3022     mysignificand = 0;
3023   } else if (category==fcInfinity) {
3024     myexponent = 0xff;
3025     mysignificand = 0;
3026   } else {
3027     assert(category == fcNaN && "Unknown category!");
3028     myexponent = 0xff;
3029     mysignificand = (uint32_t)*significandParts();
3030   }
3031
3032   return APInt(32, (((sign&1) << 31) | ((myexponent&0xff) << 23) |
3033                     (mysignificand & 0x7fffff)));
3034 }
3035
3036 APInt
3037 APFloat::convertHalfAPFloatToAPInt() const
3038 {
3039   assert(semantics == (const llvm::fltSemantics*)&IEEEhalf);
3040   assert(partCount()==1);
3041
3042   uint32_t myexponent, mysignificand;
3043
3044   if (isFiniteNonZero()) {
3045     myexponent = exponent+15; //bias
3046     mysignificand = (uint32_t)*significandParts();
3047     if (myexponent == 1 && !(mysignificand & 0x400))
3048       myexponent = 0;   // denormal
3049   } else if (category==fcZero) {
3050     myexponent = 0;
3051     mysignificand = 0;
3052   } else if (category==fcInfinity) {
3053     myexponent = 0x1f;
3054     mysignificand = 0;
3055   } else {
3056     assert(category == fcNaN && "Unknown category!");
3057     myexponent = 0x1f;
3058     mysignificand = (uint32_t)*significandParts();
3059   }
3060
3061   return APInt(16, (((sign&1) << 15) | ((myexponent&0x1f) << 10) |
3062                     (mysignificand & 0x3ff)));
3063 }
3064
3065 // This function creates an APInt that is just a bit map of the floating
3066 // point constant as it would appear in memory.  It is not a conversion,
3067 // and treating the result as a normal integer is unlikely to be useful.
3068
3069 APInt
3070 APFloat::bitcastToAPInt() const
3071 {
3072   if (semantics == (const llvm::fltSemantics*)&IEEEhalf)
3073     return convertHalfAPFloatToAPInt();
3074
3075   if (semantics == (const llvm::fltSemantics*)&IEEEsingle)
3076     return convertFloatAPFloatToAPInt();
3077
3078   if (semantics == (const llvm::fltSemantics*)&IEEEdouble)
3079     return convertDoubleAPFloatToAPInt();
3080
3081   if (semantics == (const llvm::fltSemantics*)&IEEEquad)
3082     return convertQuadrupleAPFloatToAPInt();
3083
3084   if (semantics == (const llvm::fltSemantics*)&PPCDoubleDouble)
3085     return convertPPCDoubleDoubleAPFloatToAPInt();
3086
3087   assert(semantics == (const llvm::fltSemantics*)&x87DoubleExtended &&
3088          "unknown format!");
3089   return convertF80LongDoubleAPFloatToAPInt();
3090 }
3091
3092 float
3093 APFloat::convertToFloat() const
3094 {
3095   assert(semantics == (const llvm::fltSemantics*)&IEEEsingle &&
3096          "Float semantics are not IEEEsingle");
3097   APInt api = bitcastToAPInt();
3098   return api.bitsToFloat();
3099 }
3100
3101 double
3102 APFloat::convertToDouble() const
3103 {
3104   assert(semantics == (const llvm::fltSemantics*)&IEEEdouble &&
3105          "Float semantics are not IEEEdouble");
3106   APInt api = bitcastToAPInt();
3107   return api.bitsToDouble();
3108 }
3109
3110 /// Integer bit is explicit in this format.  Intel hardware (387 and later)
3111 /// does not support these bit patterns:
3112 ///  exponent = all 1's, integer bit 0, significand 0 ("pseudoinfinity")
3113 ///  exponent = all 1's, integer bit 0, significand nonzero ("pseudoNaN")
3114 ///  exponent = 0, integer bit 1 ("pseudodenormal")
3115 ///  exponent!=0 nor all 1's, integer bit 0 ("unnormal")
3116 /// At the moment, the first two are treated as NaNs, the second two as Normal.
3117 void
3118 APFloat::initFromF80LongDoubleAPInt(const APInt &api)
3119 {
3120   assert(api.getBitWidth()==80);
3121   uint64_t i1 = api.getRawData()[0];
3122   uint64_t i2 = api.getRawData()[1];
3123   uint64_t myexponent = (i2 & 0x7fff);
3124   uint64_t mysignificand = i1;
3125
3126   initialize(&APFloat::x87DoubleExtended);
3127   assert(partCount()==2);
3128
3129   sign = static_cast<unsigned int>(i2>>15);
3130   if (myexponent==0 && mysignificand==0) {
3131     // exponent, significand meaningless
3132     category = fcZero;
3133   } else if (myexponent==0x7fff && mysignificand==0x8000000000000000ULL) {
3134     // exponent, significand meaningless
3135     category = fcInfinity;
3136   } else if (myexponent==0x7fff && mysignificand!=0x8000000000000000ULL) {
3137     // exponent meaningless
3138     category = fcNaN;
3139     significandParts()[0] = mysignificand;
3140     significandParts()[1] = 0;
3141   } else {
3142     category = fcNormal;
3143     exponent = myexponent - 16383;
3144     significandParts()[0] = mysignificand;
3145     significandParts()[1] = 0;
3146     if (myexponent==0)          // denormal
3147       exponent = -16382;
3148   }
3149 }
3150
3151 void
3152 APFloat::initFromPPCDoubleDoubleAPInt(const APInt &api)
3153 {
3154   assert(api.getBitWidth()==128);
3155   uint64_t i1 = api.getRawData()[0];
3156   uint64_t i2 = api.getRawData()[1];
3157   opStatus fs;
3158   bool losesInfo;
3159
3160   // Get the first double and convert to our format.
3161   initFromDoubleAPInt(APInt(64, i1));
3162   fs = convert(PPCDoubleDouble, rmNearestTiesToEven, &losesInfo);
3163   assert(fs == opOK && !losesInfo);
3164   (void)fs;
3165
3166   // Unless we have a special case, add in second double.
3167   if (isFiniteNonZero()) {
3168     APFloat v(IEEEdouble, APInt(64, i2));
3169     fs = v.convert(PPCDoubleDouble, rmNearestTiesToEven, &losesInfo);
3170     assert(fs == opOK && !losesInfo);
3171     (void)fs;
3172
3173     add(v, rmNearestTiesToEven);
3174   }
3175 }
3176
3177 void
3178 APFloat::initFromQuadrupleAPInt(const APInt &api)
3179 {
3180   assert(api.getBitWidth()==128);
3181   uint64_t i1 = api.getRawData()[0];
3182   uint64_t i2 = api.getRawData()[1];
3183   uint64_t myexponent = (i2 >> 48) & 0x7fff;
3184   uint64_t mysignificand  = i1;
3185   uint64_t mysignificand2 = i2 & 0xffffffffffffLL;
3186
3187   initialize(&APFloat::IEEEquad);
3188   assert(partCount()==2);
3189
3190   sign = static_cast<unsigned int>(i2>>63);
3191   if (myexponent==0 &&
3192       (mysignificand==0 && mysignificand2==0)) {
3193     // exponent, significand meaningless
3194     category = fcZero;
3195   } else if (myexponent==0x7fff &&
3196              (mysignificand==0 && mysignificand2==0)) {
3197     // exponent, significand meaningless
3198     category = fcInfinity;
3199   } else if (myexponent==0x7fff &&
3200              (mysignificand!=0 || mysignificand2 !=0)) {
3201     // exponent meaningless
3202     category = fcNaN;
3203     significandParts()[0] = mysignificand;
3204     significandParts()[1] = mysignificand2;
3205   } else {
3206     category = fcNormal;
3207     exponent = myexponent - 16383;
3208     significandParts()[0] = mysignificand;
3209     significandParts()[1] = mysignificand2;
3210     if (myexponent==0)          // denormal
3211       exponent = -16382;
3212     else
3213       significandParts()[1] |= 0x1000000000000LL;  // integer bit
3214   }
3215 }
3216
3217 void
3218 APFloat::initFromDoubleAPInt(const APInt &api)
3219 {
3220   assert(api.getBitWidth()==64);
3221   uint64_t i = *api.getRawData();
3222   uint64_t myexponent = (i >> 52) & 0x7ff;
3223   uint64_t mysignificand = i & 0xfffffffffffffLL;
3224
3225   initialize(&APFloat::IEEEdouble);
3226   assert(partCount()==1);
3227
3228   sign = static_cast<unsigned int>(i>>63);
3229   if (myexponent==0 && mysignificand==0) {
3230     // exponent, significand meaningless
3231     category = fcZero;
3232   } else if (myexponent==0x7ff && mysignificand==0) {
3233     // exponent, significand meaningless
3234     category = fcInfinity;
3235   } else if (myexponent==0x7ff && mysignificand!=0) {
3236     // exponent meaningless
3237     category = fcNaN;
3238     *significandParts() = mysignificand;
3239   } else {
3240     category = fcNormal;
3241     exponent = myexponent - 1023;
3242     *significandParts() = mysignificand;
3243     if (myexponent==0)          // denormal
3244       exponent = -1022;
3245     else
3246       *significandParts() |= 0x10000000000000LL;  // integer bit
3247   }
3248 }
3249
3250 void
3251 APFloat::initFromFloatAPInt(const APInt & api)
3252 {
3253   assert(api.getBitWidth()==32);
3254   uint32_t i = (uint32_t)*api.getRawData();
3255   uint32_t myexponent = (i >> 23) & 0xff;
3256   uint32_t mysignificand = i & 0x7fffff;
3257
3258   initialize(&APFloat::IEEEsingle);
3259   assert(partCount()==1);
3260
3261   sign = i >> 31;
3262   if (myexponent==0 && mysignificand==0) {
3263     // exponent, significand meaningless
3264     category = fcZero;
3265   } else if (myexponent==0xff && mysignificand==0) {
3266     // exponent, significand meaningless
3267     category = fcInfinity;
3268   } else if (myexponent==0xff && mysignificand!=0) {
3269     // sign, exponent, significand meaningless
3270     category = fcNaN;
3271     *significandParts() = mysignificand;
3272   } else {
3273     category = fcNormal;
3274     exponent = myexponent - 127;  //bias
3275     *significandParts() = mysignificand;
3276     if (myexponent==0)    // denormal
3277       exponent = -126;
3278     else
3279       *significandParts() |= 0x800000; // integer bit
3280   }
3281 }
3282
3283 void
3284 APFloat::initFromHalfAPInt(const APInt & api)
3285 {
3286   assert(api.getBitWidth()==16);
3287   uint32_t i = (uint32_t)*api.getRawData();
3288   uint32_t myexponent = (i >> 10) & 0x1f;
3289   uint32_t mysignificand = i & 0x3ff;
3290
3291   initialize(&APFloat::IEEEhalf);
3292   assert(partCount()==1);
3293
3294   sign = i >> 15;
3295   if (myexponent==0 && mysignificand==0) {
3296     // exponent, significand meaningless
3297     category = fcZero;
3298   } else if (myexponent==0x1f && mysignificand==0) {
3299     // exponent, significand meaningless
3300     category = fcInfinity;
3301   } else if (myexponent==0x1f && mysignificand!=0) {
3302     // sign, exponent, significand meaningless
3303     category = fcNaN;
3304     *significandParts() = mysignificand;
3305   } else {
3306     category = fcNormal;
3307     exponent = myexponent - 15;  //bias
3308     *significandParts() = mysignificand;
3309     if (myexponent==0)    // denormal
3310       exponent = -14;
3311     else
3312       *significandParts() |= 0x400; // integer bit
3313   }
3314 }
3315
3316 /// Treat api as containing the bits of a floating point number.  Currently
3317 /// we infer the floating point type from the size of the APInt.  The
3318 /// isIEEE argument distinguishes between PPC128 and IEEE128 (not meaningful
3319 /// when the size is anything else).
3320 void
3321 APFloat::initFromAPInt(const fltSemantics* Sem, const APInt& api)
3322 {
3323   if (Sem == &IEEEhalf)
3324     return initFromHalfAPInt(api);
3325   if (Sem == &IEEEsingle)
3326     return initFromFloatAPInt(api);
3327   if (Sem == &IEEEdouble)
3328     return initFromDoubleAPInt(api);
3329   if (Sem == &x87DoubleExtended)
3330     return initFromF80LongDoubleAPInt(api);
3331   if (Sem == &IEEEquad)
3332     return initFromQuadrupleAPInt(api);
3333   if (Sem == &PPCDoubleDouble)
3334     return initFromPPCDoubleDoubleAPInt(api);
3335
3336   llvm_unreachable(nullptr);
3337 }
3338
3339 APFloat
3340 APFloat::getAllOnesValue(unsigned BitWidth, bool isIEEE)
3341 {
3342   switch (BitWidth) {
3343   case 16:
3344     return APFloat(IEEEhalf, APInt::getAllOnesValue(BitWidth));
3345   case 32:
3346     return APFloat(IEEEsingle, APInt::getAllOnesValue(BitWidth));
3347   case 64:
3348     return APFloat(IEEEdouble, APInt::getAllOnesValue(BitWidth));
3349   case 80:
3350     return APFloat(x87DoubleExtended, APInt::getAllOnesValue(BitWidth));
3351   case 128:
3352     if (isIEEE)
3353       return APFloat(IEEEquad, APInt::getAllOnesValue(BitWidth));
3354     return APFloat(PPCDoubleDouble, APInt::getAllOnesValue(BitWidth));
3355   default:
3356     llvm_unreachable("Unknown floating bit width");
3357   }
3358 }
3359
3360 /// Make this number the largest magnitude normal number in the given
3361 /// semantics.
3362 void APFloat::makeLargest(bool Negative) {
3363   // We want (in interchange format):
3364   //   sign = {Negative}
3365   //   exponent = 1..10
3366   //   significand = 1..1
3367   category = fcNormal;
3368   sign = Negative;
3369   exponent = semantics->maxExponent;
3370
3371   // Use memset to set all but the highest integerPart to all ones.
3372   integerPart *significand = significandParts();
3373   unsigned PartCount = partCount();
3374   memset(significand, 0xFF, sizeof(integerPart)*(PartCount - 1));
3375
3376   // Set the high integerPart especially setting all unused top bits for
3377   // internal consistency.
3378   const unsigned NumUnusedHighBits =
3379     PartCount*integerPartWidth - semantics->precision;
3380   significand[PartCount - 1] = (NumUnusedHighBits < integerPartWidth)
3381                                    ? (~integerPart(0) >> NumUnusedHighBits)
3382                                    : 0;
3383 }
3384
3385 /// Make this number the smallest magnitude denormal number in the given
3386 /// semantics.
3387 void APFloat::makeSmallest(bool Negative) {
3388   // We want (in interchange format):
3389   //   sign = {Negative}
3390   //   exponent = 0..0
3391   //   significand = 0..01
3392   category = fcNormal;
3393   sign = Negative;
3394   exponent = semantics->minExponent;
3395   APInt::tcSet(significandParts(), 1, partCount());
3396 }
3397
3398
3399 APFloat APFloat::getLargest(const fltSemantics &Sem, bool Negative) {
3400   // We want (in interchange format):
3401   //   sign = {Negative}
3402   //   exponent = 1..10
3403   //   significand = 1..1
3404   APFloat Val(Sem, uninitialized);
3405   Val.makeLargest(Negative);
3406   return Val;
3407 }
3408
3409 APFloat APFloat::getSmallest(const fltSemantics &Sem, bool Negative) {
3410   // We want (in interchange format):
3411   //   sign = {Negative}
3412   //   exponent = 0..0
3413   //   significand = 0..01
3414   APFloat Val(Sem, uninitialized);
3415   Val.makeSmallest(Negative);
3416   return Val;
3417 }
3418
3419 APFloat APFloat::getSmallestNormalized(const fltSemantics &Sem, bool Negative) {
3420   APFloat Val(Sem, uninitialized);
3421
3422   // We want (in interchange format):
3423   //   sign = {Negative}
3424   //   exponent = 0..0
3425   //   significand = 10..0
3426
3427   Val.category = fcNormal;
3428   Val.zeroSignificand();
3429   Val.sign = Negative;
3430   Val.exponent = Sem.minExponent;
3431   Val.significandParts()[partCountForBits(Sem.precision)-1] |=
3432     (((integerPart) 1) << ((Sem.precision - 1) % integerPartWidth));
3433
3434   return Val;
3435 }
3436
3437 APFloat::APFloat(const fltSemantics &Sem, const APInt &API) {
3438   initFromAPInt(&Sem, API);
3439 }
3440
3441 APFloat::APFloat(float f) {
3442   initFromAPInt(&IEEEsingle, APInt::floatToBits(f));
3443 }
3444
3445 APFloat::APFloat(double d) {
3446   initFromAPInt(&IEEEdouble, APInt::doubleToBits(d));
3447 }
3448
3449 namespace {
3450   void append(SmallVectorImpl<char> &Buffer, StringRef Str) {
3451     Buffer.append(Str.begin(), Str.end());
3452   }
3453
3454   /// Removes data from the given significand until it is no more
3455   /// precise than is required for the desired precision.
3456   void AdjustToPrecision(APInt &significand,
3457                          int &exp, unsigned FormatPrecision) {
3458     unsigned bits = significand.getActiveBits();
3459
3460     // 196/59 is a very slight overestimate of lg_2(10).
3461     unsigned bitsRequired = (FormatPrecision * 196 + 58) / 59;
3462
3463     if (bits <= bitsRequired) return;
3464
3465     unsigned tensRemovable = (bits - bitsRequired) * 59 / 196;
3466     if (!tensRemovable) return;
3467
3468     exp += tensRemovable;
3469
3470     APInt divisor(significand.getBitWidth(), 1);
3471     APInt powten(significand.getBitWidth(), 10);
3472     while (true) {
3473       if (tensRemovable & 1)
3474         divisor *= powten;
3475       tensRemovable >>= 1;
3476       if (!tensRemovable) break;
3477       powten *= powten;
3478     }
3479
3480     significand = significand.udiv(divisor);
3481
3482     // Truncate the significand down to its active bit count.
3483     significand = significand.trunc(significand.getActiveBits());
3484   }
3485
3486
3487   void AdjustToPrecision(SmallVectorImpl<char> &buffer,
3488                          int &exp, unsigned FormatPrecision) {
3489     unsigned N = buffer.size();
3490     if (N <= FormatPrecision) return;
3491
3492     // The most significant figures are the last ones in the buffer.
3493     unsigned FirstSignificant = N - FormatPrecision;
3494
3495     // Round.
3496     // FIXME: this probably shouldn't use 'round half up'.
3497
3498     // Rounding down is just a truncation, except we also want to drop
3499     // trailing zeros from the new result.
3500     if (buffer[FirstSignificant - 1] < '5') {
3501       while (FirstSignificant < N && buffer[FirstSignificant] == '0')
3502         FirstSignificant++;
3503
3504       exp += FirstSignificant;
3505       buffer.erase(&buffer[0], &buffer[FirstSignificant]);
3506       return;
3507     }
3508
3509     // Rounding up requires a decimal add-with-carry.  If we continue
3510     // the carry, the newly-introduced zeros will just be truncated.
3511     for (unsigned I = FirstSignificant; I != N; ++I) {
3512       if (buffer[I] == '9') {
3513         FirstSignificant++;
3514       } else {
3515         buffer[I]++;
3516         break;
3517       }
3518     }
3519
3520     // If we carried through, we have exactly one digit of precision.
3521     if (FirstSignificant == N) {
3522       exp += FirstSignificant;
3523       buffer.clear();
3524       buffer.push_back('1');
3525       return;
3526     }
3527
3528     exp += FirstSignificant;
3529     buffer.erase(&buffer[0], &buffer[FirstSignificant]);
3530   }
3531 }
3532
3533 void APFloat::toString(SmallVectorImpl<char> &Str,
3534                        unsigned FormatPrecision,
3535                        unsigned FormatMaxPadding) const {
3536   switch (category) {
3537   case fcInfinity:
3538     if (isNegative())
3539       return append(Str, "-Inf");
3540     else
3541       return append(Str, "+Inf");
3542
3543   case fcNaN: return append(Str, "NaN");
3544
3545   case fcZero:
3546     if (isNegative())
3547       Str.push_back('-');
3548
3549     if (!FormatMaxPadding)
3550       append(Str, "0.0E+0");
3551     else
3552       Str.push_back('0');
3553     return;
3554
3555   case fcNormal:
3556     break;
3557   }
3558
3559   if (isNegative())
3560     Str.push_back('-');
3561
3562   // Decompose the number into an APInt and an exponent.
3563   int exp = exponent - ((int) semantics->precision - 1);
3564   APInt significand(semantics->precision,
3565                     makeArrayRef(significandParts(),
3566                                  partCountForBits(semantics->precision)));
3567
3568   // Set FormatPrecision if zero.  We want to do this before we
3569   // truncate trailing zeros, as those are part of the precision.
3570   if (!FormatPrecision) {
3571     // We use enough digits so the number can be round-tripped back to an
3572     // APFloat. The formula comes from "How to Print Floating-Point Numbers
3573     // Accurately" by Steele and White.
3574     // FIXME: Using a formula based purely on the precision is conservative;
3575     // we can print fewer digits depending on the actual value being printed.
3576
3577     // FormatPrecision = 2 + floor(significandBits / lg_2(10))
3578     FormatPrecision = 2 + semantics->precision * 59 / 196;
3579   }
3580
3581   // Ignore trailing binary zeros.
3582   int trailingZeros = significand.countTrailingZeros();
3583   exp += trailingZeros;
3584   significand = significand.lshr(trailingZeros);
3585
3586   // Change the exponent from 2^e to 10^e.
3587   if (exp == 0) {
3588     // Nothing to do.
3589   } else if (exp > 0) {
3590     // Just shift left.
3591     significand = significand.zext(semantics->precision + exp);
3592     significand <<= exp;
3593     exp = 0;
3594   } else { /* exp < 0 */
3595     int texp = -exp;
3596
3597     // We transform this using the identity:
3598     //   (N)(2^-e) == (N)(5^e)(10^-e)
3599     // This means we have to multiply N (the significand) by 5^e.
3600     // To avoid overflow, we have to operate on numbers large
3601     // enough to store N * 5^e:
3602     //   log2(N * 5^e) == log2(N) + e * log2(5)
3603     //                 <= semantics->precision + e * 137 / 59
3604     //   (log_2(5) ~ 2.321928 < 2.322034 ~ 137/59)
3605
3606     unsigned precision = semantics->precision + (137 * texp + 136) / 59;
3607
3608     // Multiply significand by 5^e.
3609     //   N * 5^0101 == N * 5^(1*1) * 5^(0*2) * 5^(1*4) * 5^(0*8)
3610     significand = significand.zext(precision);
3611     APInt five_to_the_i(precision, 5);
3612     while (true) {
3613       if (texp & 1) significand *= five_to_the_i;
3614
3615       texp >>= 1;
3616       if (!texp) break;
3617       five_to_the_i *= five_to_the_i;
3618     }
3619   }
3620
3621   AdjustToPrecision(significand, exp, FormatPrecision);
3622
3623   SmallVector<char, 256> buffer;
3624
3625   // Fill the buffer.
3626   unsigned precision = significand.getBitWidth();
3627   APInt ten(precision, 10);
3628   APInt digit(precision, 0);
3629
3630   bool inTrail = true;
3631   while (significand != 0) {
3632     // digit <- significand % 10
3633     // significand <- significand / 10
3634     APInt::udivrem(significand, ten, significand, digit);
3635
3636     unsigned d = digit.getZExtValue();
3637
3638     // Drop trailing zeros.
3639     if (inTrail && !d) exp++;
3640     else {
3641       buffer.push_back((char) ('0' + d));
3642       inTrail = false;
3643     }
3644   }
3645
3646   assert(!buffer.empty() && "no characters in buffer!");
3647
3648   // Drop down to FormatPrecision.
3649   // TODO: don't do more precise calculations above than are required.
3650   AdjustToPrecision(buffer, exp, FormatPrecision);
3651
3652   unsigned NDigits = buffer.size();
3653
3654   // Check whether we should use scientific notation.
3655   bool FormatScientific;
3656   if (!FormatMaxPadding)
3657     FormatScientific = true;
3658   else {
3659     if (exp >= 0) {
3660       // 765e3 --> 765000
3661       //              ^^^
3662       // But we shouldn't make the number look more precise than it is.
3663       FormatScientific = ((unsigned) exp > FormatMaxPadding ||
3664                           NDigits + (unsigned) exp > FormatPrecision);
3665     } else {
3666       // Power of the most significant digit.
3667       int MSD = exp + (int) (NDigits - 1);
3668       if (MSD >= 0) {
3669         // 765e-2 == 7.65
3670         FormatScientific = false;
3671       } else {
3672         // 765e-5 == 0.00765
3673         //           ^ ^^
3674         FormatScientific = ((unsigned) -MSD) > FormatMaxPadding;
3675       }
3676     }
3677   }
3678
3679   // Scientific formatting is pretty straightforward.
3680   if (FormatScientific) {
3681     exp += (NDigits - 1);
3682
3683     Str.push_back(buffer[NDigits-1]);
3684     Str.push_back('.');
3685     if (NDigits == 1)
3686       Str.push_back('0');
3687     else
3688       for (unsigned I = 1; I != NDigits; ++I)
3689         Str.push_back(buffer[NDigits-1-I]);
3690     Str.push_back('E');
3691
3692     Str.push_back(exp >= 0 ? '+' : '-');
3693     if (exp < 0) exp = -exp;
3694     SmallVector<char, 6> expbuf;
3695     do {
3696       expbuf.push_back((char) ('0' + (exp % 10)));
3697       exp /= 10;
3698     } while (exp);
3699     for (unsigned I = 0, E = expbuf.size(); I != E; ++I)
3700       Str.push_back(expbuf[E-1-I]);
3701     return;
3702   }
3703
3704   // Non-scientific, positive exponents.
3705   if (exp >= 0) {
3706     for (unsigned I = 0; I != NDigits; ++I)
3707       Str.push_back(buffer[NDigits-1-I]);
3708     for (unsigned I = 0; I != (unsigned) exp; ++I)
3709       Str.push_back('0');
3710     return;
3711   }
3712
3713   // Non-scientific, negative exponents.
3714
3715   // The number of digits to the left of the decimal point.
3716   int NWholeDigits = exp + (int) NDigits;
3717
3718   unsigned I = 0;
3719   if (NWholeDigits > 0) {
3720     for (; I != (unsigned) NWholeDigits; ++I)
3721       Str.push_back(buffer[NDigits-I-1]);
3722     Str.push_back('.');
3723   } else {
3724     unsigned NZeros = 1 + (unsigned) -NWholeDigits;
3725
3726     Str.push_back('0');
3727     Str.push_back('.');
3728     for (unsigned Z = 1; Z != NZeros; ++Z)
3729       Str.push_back('0');
3730   }
3731
3732   for (; I != NDigits; ++I)
3733     Str.push_back(buffer[NDigits-I-1]);
3734 }
3735
3736 bool APFloat::getExactInverse(APFloat *inv) const {
3737   // Special floats and denormals have no exact inverse.
3738   if (!isFiniteNonZero())
3739     return false;
3740
3741   // Check that the number is a power of two by making sure that only the
3742   // integer bit is set in the significand.
3743   if (significandLSB() != semantics->precision - 1)
3744     return false;
3745
3746   // Get the inverse.
3747   APFloat reciprocal(*semantics, 1ULL);
3748   if (reciprocal.divide(*this, rmNearestTiesToEven) != opOK)
3749     return false;
3750
3751   // Avoid multiplication with a denormal, it is not safe on all platforms and
3752   // may be slower than a normal division.
3753   if (reciprocal.isDenormal())
3754     return false;
3755
3756   assert(reciprocal.isFiniteNonZero() &&
3757          reciprocal.significandLSB() == reciprocal.semantics->precision - 1);
3758
3759   if (inv)
3760     *inv = reciprocal;
3761
3762   return true;
3763 }
3764
3765 bool APFloat::isSignaling() const {
3766   if (!isNaN())
3767     return false;
3768
3769   // IEEE-754R 2008 6.2.1: A signaling NaN bit string should be encoded with the
3770   // first bit of the trailing significand being 0.
3771   return !APInt::tcExtractBit(significandParts(), semantics->precision - 2);
3772 }
3773
3774 /// IEEE-754R 2008 5.3.1: nextUp/nextDown.
3775 ///
3776 /// *NOTE* since nextDown(x) = -nextUp(-x), we only implement nextUp with
3777 /// appropriate sign switching before/after the computation.
3778 APFloat::opStatus APFloat::next(bool nextDown) {
3779   // If we are performing nextDown, swap sign so we have -x.
3780   if (nextDown)
3781     changeSign();
3782
3783   // Compute nextUp(x)
3784   opStatus result = opOK;
3785
3786   // Handle each float category separately.
3787   switch (category) {
3788   case fcInfinity:
3789     // nextUp(+inf) = +inf
3790     if (!isNegative())
3791       break;
3792     // nextUp(-inf) = -getLargest()
3793     makeLargest(true);
3794     break;
3795   case fcNaN:
3796     // IEEE-754R 2008 6.2 Par 2: nextUp(sNaN) = qNaN. Set Invalid flag.
3797     // IEEE-754R 2008 6.2: nextUp(qNaN) = qNaN. Must be identity so we do not
3798     //                     change the payload.
3799     if (isSignaling()) {
3800       result = opInvalidOp;
3801       // For consistency, propagate the sign of the sNaN to the qNaN.
3802       makeNaN(false, isNegative(), nullptr);
3803     }
3804     break;
3805   case fcZero:
3806     // nextUp(pm 0) = +getSmallest()
3807     makeSmallest(false);
3808     break;
3809   case fcNormal:
3810     // nextUp(-getSmallest()) = -0
3811     if (isSmallest() && isNegative()) {
3812       APInt::tcSet(significandParts(), 0, partCount());
3813       category = fcZero;
3814       exponent = 0;
3815       break;
3816     }
3817
3818     // nextUp(getLargest()) == INFINITY
3819     if (isLargest() && !isNegative()) {
3820       APInt::tcSet(significandParts(), 0, partCount());
3821       category = fcInfinity;
3822       exponent = semantics->maxExponent + 1;
3823       break;
3824     }
3825
3826     // nextUp(normal) == normal + inc.
3827     if (isNegative()) {
3828       // If we are negative, we need to decrement the significand.
3829
3830       // We only cross a binade boundary that requires adjusting the exponent
3831       // if:
3832       //   1. exponent != semantics->minExponent. This implies we are not in the
3833       //   smallest binade or are dealing with denormals.
3834       //   2. Our significand excluding the integral bit is all zeros.
3835       bool WillCrossBinadeBoundary =
3836         exponent != semantics->minExponent && isSignificandAllZeros();
3837
3838       // Decrement the significand.
3839       //
3840       // We always do this since:
3841       //   1. If we are dealing with a non-binade decrement, by definition we
3842       //   just decrement the significand.
3843       //   2. If we are dealing with a normal -> normal binade decrement, since
3844       //   we have an explicit integral bit the fact that all bits but the
3845       //   integral bit are zero implies that subtracting one will yield a
3846       //   significand with 0 integral bit and 1 in all other spots. Thus we
3847       //   must just adjust the exponent and set the integral bit to 1.
3848       //   3. If we are dealing with a normal -> denormal binade decrement,
3849       //   since we set the integral bit to 0 when we represent denormals, we
3850       //   just decrement the significand.
3851       integerPart *Parts = significandParts();
3852       APInt::tcDecrement(Parts, partCount());
3853
3854       if (WillCrossBinadeBoundary) {
3855         // Our result is a normal number. Do the following:
3856         // 1. Set the integral bit to 1.
3857         // 2. Decrement the exponent.
3858         APInt::tcSetBit(Parts, semantics->precision - 1);
3859         exponent--;
3860       }
3861     } else {
3862       // If we are positive, we need to increment the significand.
3863
3864       // We only cross a binade boundary that requires adjusting the exponent if
3865       // the input is not a denormal and all of said input's significand bits
3866       // are set. If all of said conditions are true: clear the significand, set
3867       // the integral bit to 1, and increment the exponent. If we have a
3868       // denormal always increment since moving denormals and the numbers in the
3869       // smallest normal binade have the same exponent in our representation.
3870       bool WillCrossBinadeBoundary = !isDenormal() && isSignificandAllOnes();
3871
3872       if (WillCrossBinadeBoundary) {
3873         integerPart *Parts = significandParts();
3874         APInt::tcSet(Parts, 0, partCount());
3875         APInt::tcSetBit(Parts, semantics->precision - 1);
3876         assert(exponent != semantics->maxExponent &&
3877                "We can not increment an exponent beyond the maxExponent allowed"
3878                " by the given floating point semantics.");
3879         exponent++;
3880       } else {
3881         incrementSignificand();
3882       }
3883     }
3884     break;
3885   }
3886
3887   // If we are performing nextDown, swap sign so we have -nextUp(-x)
3888   if (nextDown)
3889     changeSign();
3890
3891   return result;
3892 }
3893
3894 void
3895 APFloat::makeInf(bool Negative) {
3896   category = fcInfinity;
3897   sign = Negative;
3898   exponent = semantics->maxExponent + 1;
3899   APInt::tcSet(significandParts(), 0, partCount());
3900 }
3901
3902 void
3903 APFloat::makeZero(bool Negative) {
3904   category = fcZero;
3905   sign = Negative;
3906   exponent = semantics->minExponent-1;
3907   APInt::tcSet(significandParts(), 0, partCount());
3908 }