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