APInt: Simplify code. No functionality change.
[oota-llvm.git] / lib / Support / APInt.cpp
1 //===-- APInt.cpp - Implement APInt 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 integer
11 // constant values and provide a variety of arithmetic operations on them.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #define DEBUG_TYPE "apint"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/ADT/Hashing.h"
19 #include "llvm/ADT/SmallString.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/ErrorHandling.h"
23 #include "llvm/Support/MathExtras.h"
24 #include "llvm/Support/raw_ostream.h"
25 #include <cmath>
26 #include <cstdlib>
27 #include <cstring>
28 #include <limits>
29 using namespace llvm;
30
31 /// A utility function for allocating memory, checking for allocation failures,
32 /// and ensuring the contents are zeroed.
33 inline static uint64_t* getClearedMemory(unsigned numWords) {
34   uint64_t * result = new uint64_t[numWords];
35   assert(result && "APInt memory allocation fails!");
36   memset(result, 0, numWords * sizeof(uint64_t));
37   return result;
38 }
39
40 /// A utility function for allocating memory and checking for allocation
41 /// failure.  The content is not zeroed.
42 inline static uint64_t* getMemory(unsigned numWords) {
43   uint64_t * result = new uint64_t[numWords];
44   assert(result && "APInt memory allocation fails!");
45   return result;
46 }
47
48 /// A utility function that converts a character to a digit.
49 inline static unsigned getDigit(char cdigit, uint8_t radix) {
50   unsigned r;
51
52   if (radix == 16 || radix == 36) {
53     r = cdigit - '0';
54     if (r <= 9)
55       return r;
56
57     r = cdigit - 'A';
58     if (r <= radix - 11U)
59       return r + 10;
60
61     r = cdigit - 'a';
62     if (r <= radix - 11U)
63       return r + 10;
64     
65     radix = 10;
66   }
67
68   r = cdigit - '0';
69   if (r < radix)
70     return r;
71
72   return -1U;
73 }
74
75
76 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
77   pVal = getClearedMemory(getNumWords());
78   pVal[0] = val;
79   if (isSigned && int64_t(val) < 0)
80     for (unsigned i = 1; i < getNumWords(); ++i)
81       pVal[i] = -1ULL;
82 }
83
84 void APInt::initSlowCase(const APInt& that) {
85   pVal = getMemory(getNumWords());
86   memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
87 }
88
89 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
90   assert(BitWidth && "Bitwidth too small");
91   assert(bigVal.data() && "Null pointer detected!");
92   if (isSingleWord())
93     VAL = bigVal[0];
94   else {
95     // Get memory, cleared to 0
96     pVal = getClearedMemory(getNumWords());
97     // Calculate the number of words to copy
98     unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
99     // Copy the words from bigVal to pVal
100     memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
101   }
102   // Make sure unused high bits are cleared
103   clearUnusedBits();
104 }
105
106 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
107   : BitWidth(numBits), VAL(0) {
108   initFromArray(bigVal);
109 }
110
111 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
112   : BitWidth(numBits), VAL(0) {
113   initFromArray(makeArrayRef(bigVal, numWords));
114 }
115
116 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
117   : BitWidth(numbits), VAL(0) {
118   assert(BitWidth && "Bitwidth too small");
119   fromString(numbits, Str, radix);
120 }
121
122 APInt& APInt::AssignSlowCase(const APInt& RHS) {
123   // Don't do anything for X = X
124   if (this == &RHS)
125     return *this;
126
127   if (BitWidth == RHS.getBitWidth()) {
128     // assume same bit-width single-word case is already handled
129     assert(!isSingleWord());
130     memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
131     return *this;
132   }
133
134   if (isSingleWord()) {
135     // assume case where both are single words is already handled
136     assert(!RHS.isSingleWord());
137     VAL = 0;
138     pVal = getMemory(RHS.getNumWords());
139     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
140   } else if (getNumWords() == RHS.getNumWords())
141     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
142   else if (RHS.isSingleWord()) {
143     delete [] pVal;
144     VAL = RHS.VAL;
145   } else {
146     delete [] pVal;
147     pVal = getMemory(RHS.getNumWords());
148     memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
149   }
150   BitWidth = RHS.BitWidth;
151   return clearUnusedBits();
152 }
153
154 APInt& APInt::operator=(uint64_t RHS) {
155   if (isSingleWord())
156     VAL = RHS;
157   else {
158     pVal[0] = RHS;
159     memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
160   }
161   return clearUnusedBits();
162 }
163
164 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
165 void APInt::Profile(FoldingSetNodeID& ID) const {
166   ID.AddInteger(BitWidth);
167
168   if (isSingleWord()) {
169     ID.AddInteger(VAL);
170     return;
171   }
172
173   unsigned NumWords = getNumWords();
174   for (unsigned i = 0; i < NumWords; ++i)
175     ID.AddInteger(pVal[i]);
176 }
177
178 /// add_1 - This function adds a single "digit" integer, y, to the multiple
179 /// "digit" integer array,  x[]. x[] is modified to reflect the addition and
180 /// 1 is returned if there is a carry out, otherwise 0 is returned.
181 /// @returns the carry of the addition.
182 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
183   for (unsigned i = 0; i < len; ++i) {
184     dest[i] = y + x[i];
185     if (dest[i] < y)
186       y = 1; // Carry one to next digit.
187     else {
188       y = 0; // No need to carry so exit early
189       break;
190     }
191   }
192   return y;
193 }
194
195 /// @brief Prefix increment operator. Increments the APInt by one.
196 APInt& APInt::operator++() {
197   if (isSingleWord())
198     ++VAL;
199   else
200     add_1(pVal, pVal, getNumWords(), 1);
201   return clearUnusedBits();
202 }
203
204 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
205 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
206 /// no further borrowing is neeeded or it runs out of "digits" in x.  The result
207 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
208 /// In other words, if y > x then this function returns 1, otherwise 0.
209 /// @returns the borrow out of the subtraction
210 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
211   for (unsigned i = 0; i < len; ++i) {
212     uint64_t X = x[i];
213     x[i] -= y;
214     if (y > X)
215       y = 1;  // We have to "borrow 1" from next "digit"
216     else {
217       y = 0;  // No need to borrow
218       break;  // Remaining digits are unchanged so exit early
219     }
220   }
221   return bool(y);
222 }
223
224 /// @brief Prefix decrement operator. Decrements the APInt by one.
225 APInt& APInt::operator--() {
226   if (isSingleWord())
227     --VAL;
228   else
229     sub_1(pVal, getNumWords(), 1);
230   return clearUnusedBits();
231 }
232
233 /// add - This function adds the integer array x to the integer array Y and
234 /// places the result in dest.
235 /// @returns the carry out from the addition
236 /// @brief General addition of 64-bit integer arrays
237 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
238                 unsigned len) {
239   bool carry = false;
240   for (unsigned i = 0; i< len; ++i) {
241     uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
242     dest[i] = x[i] + y[i] + carry;
243     carry = dest[i] < limit || (carry && dest[i] == limit);
244   }
245   return carry;
246 }
247
248 /// Adds the RHS APint to this APInt.
249 /// @returns this, after addition of RHS.
250 /// @brief Addition assignment operator.
251 APInt& APInt::operator+=(const APInt& RHS) {
252   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
253   if (isSingleWord())
254     VAL += RHS.VAL;
255   else {
256     add(pVal, pVal, RHS.pVal, getNumWords());
257   }
258   return clearUnusedBits();
259 }
260
261 /// Subtracts the integer array y from the integer array x
262 /// @returns returns the borrow out.
263 /// @brief Generalized subtraction of 64-bit integer arrays.
264 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
265                 unsigned len) {
266   bool borrow = false;
267   for (unsigned i = 0; i < len; ++i) {
268     uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
269     borrow = y[i] > x_tmp || (borrow && x[i] == 0);
270     dest[i] = x_tmp - y[i];
271   }
272   return borrow;
273 }
274
275 /// Subtracts the RHS APInt from this APInt
276 /// @returns this, after subtraction
277 /// @brief Subtraction assignment operator.
278 APInt& APInt::operator-=(const APInt& RHS) {
279   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
280   if (isSingleWord())
281     VAL -= RHS.VAL;
282   else
283     sub(pVal, pVal, RHS.pVal, getNumWords());
284   return clearUnusedBits();
285 }
286
287 /// Multiplies an integer array, x, by a uint64_t integer and places the result
288 /// into dest.
289 /// @returns the carry out of the multiplication.
290 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
291 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
292   // Split y into high 32-bit part (hy)  and low 32-bit part (ly)
293   uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
294   uint64_t carry = 0;
295
296   // For each digit of x.
297   for (unsigned i = 0; i < len; ++i) {
298     // Split x into high and low words
299     uint64_t lx = x[i] & 0xffffffffULL;
300     uint64_t hx = x[i] >> 32;
301     // hasCarry - A flag to indicate if there is a carry to the next digit.
302     // hasCarry == 0, no carry
303     // hasCarry == 1, has carry
304     // hasCarry == 2, no carry and the calculation result == 0.
305     uint8_t hasCarry = 0;
306     dest[i] = carry + lx * ly;
307     // Determine if the add above introduces carry.
308     hasCarry = (dest[i] < carry) ? 1 : 0;
309     carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
310     // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
311     // (2^32 - 1) + 2^32 = 2^64.
312     hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
313
314     carry += (lx * hy) & 0xffffffffULL;
315     dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
316     carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
317             (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
318   }
319   return carry;
320 }
321
322 /// Multiplies integer array x by integer array y and stores the result into
323 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
324 /// @brief Generalized multiplicate of integer arrays.
325 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
326                 unsigned ylen) {
327   dest[xlen] = mul_1(dest, x, xlen, y[0]);
328   for (unsigned i = 1; i < ylen; ++i) {
329     uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
330     uint64_t carry = 0, lx = 0, hx = 0;
331     for (unsigned j = 0; j < xlen; ++j) {
332       lx = x[j] & 0xffffffffULL;
333       hx = x[j] >> 32;
334       // hasCarry - A flag to indicate if has carry.
335       // hasCarry == 0, no carry
336       // hasCarry == 1, has carry
337       // hasCarry == 2, no carry and the calculation result == 0.
338       uint8_t hasCarry = 0;
339       uint64_t resul = carry + lx * ly;
340       hasCarry = (resul < carry) ? 1 : 0;
341       carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
342       hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
343
344       carry += (lx * hy) & 0xffffffffULL;
345       resul = (carry << 32) | (resul & 0xffffffffULL);
346       dest[i+j] += resul;
347       carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
348               (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
349               ((lx * hy) >> 32) + hx * hy;
350     }
351     dest[i+xlen] = carry;
352   }
353 }
354
355 APInt& APInt::operator*=(const APInt& RHS) {
356   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
357   if (isSingleWord()) {
358     VAL *= RHS.VAL;
359     clearUnusedBits();
360     return *this;
361   }
362
363   // Get some bit facts about LHS and check for zero
364   unsigned lhsBits = getActiveBits();
365   unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
366   if (!lhsWords)
367     // 0 * X ===> 0
368     return *this;
369
370   // Get some bit facts about RHS and check for zero
371   unsigned rhsBits = RHS.getActiveBits();
372   unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
373   if (!rhsWords) {
374     // X * 0 ===> 0
375     clearAllBits();
376     return *this;
377   }
378
379   // Allocate space for the result
380   unsigned destWords = rhsWords + lhsWords;
381   uint64_t *dest = getMemory(destWords);
382
383   // Perform the long multiply
384   mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
385
386   // Copy result back into *this
387   clearAllBits();
388   unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
389   memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
390   clearUnusedBits();
391
392   // delete dest array and return
393   delete[] dest;
394   return *this;
395 }
396
397 APInt& APInt::operator&=(const APInt& RHS) {
398   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
399   if (isSingleWord()) {
400     VAL &= RHS.VAL;
401     return *this;
402   }
403   unsigned numWords = getNumWords();
404   for (unsigned i = 0; i < numWords; ++i)
405     pVal[i] &= RHS.pVal[i];
406   return *this;
407 }
408
409 APInt& APInt::operator|=(const APInt& RHS) {
410   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
411   if (isSingleWord()) {
412     VAL |= RHS.VAL;
413     return *this;
414   }
415   unsigned numWords = getNumWords();
416   for (unsigned i = 0; i < numWords; ++i)
417     pVal[i] |= RHS.pVal[i];
418   return *this;
419 }
420
421 APInt& APInt::operator^=(const APInt& RHS) {
422   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
423   if (isSingleWord()) {
424     VAL ^= RHS.VAL;
425     this->clearUnusedBits();
426     return *this;
427   }
428   unsigned numWords = getNumWords();
429   for (unsigned i = 0; i < numWords; ++i)
430     pVal[i] ^= RHS.pVal[i];
431   return clearUnusedBits();
432 }
433
434 APInt APInt::AndSlowCase(const APInt& RHS) const {
435   unsigned numWords = getNumWords();
436   uint64_t* val = getMemory(numWords);
437   for (unsigned i = 0; i < numWords; ++i)
438     val[i] = pVal[i] & RHS.pVal[i];
439   return APInt(val, getBitWidth());
440 }
441
442 APInt APInt::OrSlowCase(const APInt& RHS) const {
443   unsigned numWords = getNumWords();
444   uint64_t *val = getMemory(numWords);
445   for (unsigned i = 0; i < numWords; ++i)
446     val[i] = pVal[i] | RHS.pVal[i];
447   return APInt(val, getBitWidth());
448 }
449
450 APInt APInt::XorSlowCase(const APInt& RHS) const {
451   unsigned numWords = getNumWords();
452   uint64_t *val = getMemory(numWords);
453   for (unsigned i = 0; i < numWords; ++i)
454     val[i] = pVal[i] ^ RHS.pVal[i];
455
456   // 0^0==1 so clear the high bits in case they got set.
457   return APInt(val, getBitWidth()).clearUnusedBits();
458 }
459
460 APInt APInt::operator*(const APInt& RHS) const {
461   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
462   if (isSingleWord())
463     return APInt(BitWidth, VAL * RHS.VAL);
464   APInt Result(*this);
465   Result *= RHS;
466   return Result;
467 }
468
469 APInt APInt::operator+(const APInt& RHS) const {
470   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
471   if (isSingleWord())
472     return APInt(BitWidth, VAL + RHS.VAL);
473   APInt Result(BitWidth, 0);
474   add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
475   return Result.clearUnusedBits();
476 }
477
478 APInt APInt::operator-(const APInt& RHS) const {
479   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
480   if (isSingleWord())
481     return APInt(BitWidth, VAL - RHS.VAL);
482   APInt Result(BitWidth, 0);
483   sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
484   return Result.clearUnusedBits();
485 }
486
487 bool APInt::EqualSlowCase(const APInt& RHS) const {
488   // Get some facts about the number of bits used in the two operands.
489   unsigned n1 = getActiveBits();
490   unsigned n2 = RHS.getActiveBits();
491
492   // If the number of bits isn't the same, they aren't equal
493   if (n1 != n2)
494     return false;
495
496   // If the number of bits fits in a word, we only need to compare the low word.
497   if (n1 <= APINT_BITS_PER_WORD)
498     return pVal[0] == RHS.pVal[0];
499
500   // Otherwise, compare everything
501   for (int i = whichWord(n1 - 1); i >= 0; --i)
502     if (pVal[i] != RHS.pVal[i])
503       return false;
504   return true;
505 }
506
507 bool APInt::EqualSlowCase(uint64_t Val) const {
508   unsigned n = getActiveBits();
509   if (n <= APINT_BITS_PER_WORD)
510     return pVal[0] == Val;
511   else
512     return false;
513 }
514
515 bool APInt::ult(const APInt& RHS) const {
516   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
517   if (isSingleWord())
518     return VAL < RHS.VAL;
519
520   // Get active bit length of both operands
521   unsigned n1 = getActiveBits();
522   unsigned n2 = RHS.getActiveBits();
523
524   // If magnitude of LHS is less than RHS, return true.
525   if (n1 < n2)
526     return true;
527
528   // If magnitude of RHS is greather than LHS, return false.
529   if (n2 < n1)
530     return false;
531
532   // If they bot fit in a word, just compare the low order word
533   if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
534     return pVal[0] < RHS.pVal[0];
535
536   // Otherwise, compare all words
537   unsigned topWord = whichWord(std::max(n1,n2)-1);
538   for (int i = topWord; i >= 0; --i) {
539     if (pVal[i] > RHS.pVal[i])
540       return false;
541     if (pVal[i] < RHS.pVal[i])
542       return true;
543   }
544   return false;
545 }
546
547 bool APInt::slt(const APInt& RHS) const {
548   assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
549   if (isSingleWord()) {
550     int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
551     int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
552     return lhsSext < rhsSext;
553   }
554
555   APInt lhs(*this);
556   APInt rhs(RHS);
557   bool lhsNeg = isNegative();
558   bool rhsNeg = rhs.isNegative();
559   if (lhsNeg) {
560     // Sign bit is set so perform two's complement to make it positive
561     lhs.flipAllBits();
562     ++lhs;
563   }
564   if (rhsNeg) {
565     // Sign bit is set so perform two's complement to make it positive
566     rhs.flipAllBits();
567     ++rhs;
568   }
569
570   // Now we have unsigned values to compare so do the comparison if necessary
571   // based on the negativeness of the values.
572   if (lhsNeg)
573     if (rhsNeg)
574       return lhs.ugt(rhs);
575     else
576       return true;
577   else if (rhsNeg)
578     return false;
579   else
580     return lhs.ult(rhs);
581 }
582
583 void APInt::setBit(unsigned bitPosition) {
584   if (isSingleWord())
585     VAL |= maskBit(bitPosition);
586   else
587     pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
588 }
589
590 /// Set the given bit to 0 whose position is given as "bitPosition".
591 /// @brief Set a given bit to 0.
592 void APInt::clearBit(unsigned bitPosition) {
593   if (isSingleWord())
594     VAL &= ~maskBit(bitPosition);
595   else
596     pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
597 }
598
599 /// @brief Toggle every bit to its opposite value.
600
601 /// Toggle a given bit to its opposite value whose position is given
602 /// as "bitPosition".
603 /// @brief Toggles a given bit to its opposite value.
604 void APInt::flipBit(unsigned bitPosition) {
605   assert(bitPosition < BitWidth && "Out of the bit-width range!");
606   if ((*this)[bitPosition]) clearBit(bitPosition);
607   else setBit(bitPosition);
608 }
609
610 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
611   assert(!str.empty() && "Invalid string length");
612   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 || 
613           radix == 36) &&
614          "Radix should be 2, 8, 10, 16, or 36!");
615
616   size_t slen = str.size();
617
618   // Each computation below needs to know if it's negative.
619   StringRef::iterator p = str.begin();
620   unsigned isNegative = *p == '-';
621   if (*p == '-' || *p == '+') {
622     p++;
623     slen--;
624     assert(slen && "String is only a sign, needs a value.");
625   }
626
627   // For radixes of power-of-two values, the bits required is accurately and
628   // easily computed
629   if (radix == 2)
630     return slen + isNegative;
631   if (radix == 8)
632     return slen * 3 + isNegative;
633   if (radix == 16)
634     return slen * 4 + isNegative;
635
636   // FIXME: base 36
637   
638   // This is grossly inefficient but accurate. We could probably do something
639   // with a computation of roughly slen*64/20 and then adjust by the value of
640   // the first few digits. But, I'm not sure how accurate that could be.
641
642   // Compute a sufficient number of bits that is always large enough but might
643   // be too large. This avoids the assertion in the constructor. This
644   // calculation doesn't work appropriately for the numbers 0-9, so just use 4
645   // bits in that case.
646   unsigned sufficient 
647     = radix == 10? (slen == 1 ? 4 : slen * 64/18)
648                  : (slen == 1 ? 7 : slen * 16/3);
649
650   // Convert to the actual binary value.
651   APInt tmp(sufficient, StringRef(p, slen), radix);
652
653   // Compute how many bits are required. If the log is infinite, assume we need
654   // just bit.
655   unsigned log = tmp.logBase2();
656   if (log == (unsigned)-1) {
657     return isNegative + 1;
658   } else {
659     return isNegative + log + 1;
660   }
661 }
662
663 hash_code llvm::hash_value(const APInt &Arg) {
664   if (Arg.isSingleWord())
665     return hash_combine(Arg.VAL);
666
667   return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
668 }
669
670 /// HiBits - This function returns the high "numBits" bits of this APInt.
671 APInt APInt::getHiBits(unsigned numBits) const {
672   return APIntOps::lshr(*this, BitWidth - numBits);
673 }
674
675 /// LoBits - This function returns the low "numBits" bits of this APInt.
676 APInt APInt::getLoBits(unsigned numBits) const {
677   return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
678                         BitWidth - numBits);
679 }
680
681 unsigned APInt::countLeadingZerosSlowCase() const {
682   // Treat the most significand word differently because it might have
683   // meaningless bits set beyond the precision.
684   unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;
685   integerPart MSWMask;
686   if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;
687   else {
688     MSWMask = ~integerPart(0);
689     BitsInMSW = APINT_BITS_PER_WORD;
690   }
691
692   unsigned i = getNumWords();
693   integerPart MSW = pVal[i-1] & MSWMask;
694   if (MSW)
695     return llvm::countLeadingZeros(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);
696
697   unsigned Count = BitsInMSW;
698   for (--i; i > 0u; --i) {
699     if (pVal[i-1] == 0)
700       Count += APINT_BITS_PER_WORD;
701     else {
702       Count += llvm::countLeadingZeros(pVal[i-1]);
703       break;
704     }
705   }
706   return Count;
707 }
708
709 unsigned APInt::countLeadingOnes() const {
710   if (isSingleWord())
711     return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth));
712
713   unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
714   unsigned shift;
715   if (!highWordBits) {
716     highWordBits = APINT_BITS_PER_WORD;
717     shift = 0;
718   } else {
719     shift = APINT_BITS_PER_WORD - highWordBits;
720   }
721   int i = getNumWords() - 1;
722   unsigned Count = CountLeadingOnes_64(pVal[i] << shift);
723   if (Count == highWordBits) {
724     for (i--; i >= 0; --i) {
725       if (pVal[i] == -1ULL)
726         Count += APINT_BITS_PER_WORD;
727       else {
728         Count += CountLeadingOnes_64(pVal[i]);
729         break;
730       }
731     }
732   }
733   return Count;
734 }
735
736 unsigned APInt::countTrailingZeros() const {
737   if (isSingleWord())
738     return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);
739   unsigned Count = 0;
740   unsigned i = 0;
741   for (; i < getNumWords() && pVal[i] == 0; ++i)
742     Count += APINT_BITS_PER_WORD;
743   if (i < getNumWords())
744     Count += llvm::countTrailingZeros(pVal[i]);
745   return std::min(Count, BitWidth);
746 }
747
748 unsigned APInt::countTrailingOnesSlowCase() const {
749   unsigned Count = 0;
750   unsigned i = 0;
751   for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
752     Count += APINT_BITS_PER_WORD;
753   if (i < getNumWords())
754     Count += CountTrailingOnes_64(pVal[i]);
755   return std::min(Count, BitWidth);
756 }
757
758 unsigned APInt::countPopulationSlowCase() const {
759   unsigned Count = 0;
760   for (unsigned i = 0; i < getNumWords(); ++i)
761     Count += CountPopulation_64(pVal[i]);
762   return Count;
763 }
764
765 /// Perform a logical right-shift from Src to Dst, which must be equal or
766 /// non-overlapping, of Words words, by Shift, which must be less than 64.
767 static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,
768                      unsigned Shift) {
769   uint64_t Carry = 0;
770   for (int I = Words - 1; I >= 0; --I) {
771     uint64_t Tmp = Src[I];
772     Dst[I] = (Tmp >> Shift) | Carry;
773     Carry = Tmp << (64 - Shift);
774   }
775 }
776
777 APInt APInt::byteSwap() const {
778   assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
779   if (BitWidth == 16)
780     return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
781   if (BitWidth == 32)
782     return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
783   if (BitWidth == 48) {
784     unsigned Tmp1 = unsigned(VAL >> 16);
785     Tmp1 = ByteSwap_32(Tmp1);
786     uint16_t Tmp2 = uint16_t(VAL);
787     Tmp2 = ByteSwap_16(Tmp2);
788     return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
789   }
790   if (BitWidth == 64)
791     return APInt(BitWidth, ByteSwap_64(VAL));
792
793   APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
794   for (unsigned I = 0, N = getNumWords(); I != N; ++I)
795     Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
796   if (Result.BitWidth != BitWidth) {
797     lshrNear(Result.pVal, Result.pVal, getNumWords(),
798              Result.BitWidth - BitWidth);
799     Result.BitWidth = BitWidth;
800   }
801   return Result;
802 }
803
804 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
805                                             const APInt& API2) {
806   APInt A = API1, B = API2;
807   while (!!B) {
808     APInt T = B;
809     B = APIntOps::urem(A, B);
810     A = T;
811   }
812   return A;
813 }
814
815 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
816   union {
817     double D;
818     uint64_t I;
819   } T;
820   T.D = Double;
821
822   // Get the sign bit from the highest order bit
823   bool isNeg = T.I >> 63;
824
825   // Get the 11-bit exponent and adjust for the 1023 bit bias
826   int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
827
828   // If the exponent is negative, the value is < 0 so just return 0.
829   if (exp < 0)
830     return APInt(width, 0u);
831
832   // Extract the mantissa by clearing the top 12 bits (sign + exponent).
833   uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
834
835   // If the exponent doesn't shift all bits out of the mantissa
836   if (exp < 52)
837     return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
838                     APInt(width, mantissa >> (52 - exp));
839
840   // If the client didn't provide enough bits for us to shift the mantissa into
841   // then the result is undefined, just return 0
842   if (width <= exp - 52)
843     return APInt(width, 0);
844
845   // Otherwise, we have to shift the mantissa bits up to the right location
846   APInt Tmp(width, mantissa);
847   Tmp = Tmp.shl((unsigned)exp - 52);
848   return isNeg ? -Tmp : Tmp;
849 }
850
851 /// RoundToDouble - This function converts this APInt to a double.
852 /// The layout for double is as following (IEEE Standard 754):
853 ///  --------------------------------------
854 /// |  Sign    Exponent    Fraction    Bias |
855 /// |-------------------------------------- |
856 /// |  1[63]   11[62-52]   52[51-00]   1023 |
857 ///  --------------------------------------
858 double APInt::roundToDouble(bool isSigned) const {
859
860   // Handle the simple case where the value is contained in one uint64_t.
861   // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
862   if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
863     if (isSigned) {
864       int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);
865       return double(sext);
866     } else
867       return double(getWord(0));
868   }
869
870   // Determine if the value is negative.
871   bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
872
873   // Construct the absolute value if we're negative.
874   APInt Tmp(isNeg ? -(*this) : (*this));
875
876   // Figure out how many bits we're using.
877   unsigned n = Tmp.getActiveBits();
878
879   // The exponent (without bias normalization) is just the number of bits
880   // we are using. Note that the sign bit is gone since we constructed the
881   // absolute value.
882   uint64_t exp = n;
883
884   // Return infinity for exponent overflow
885   if (exp > 1023) {
886     if (!isSigned || !isNeg)
887       return std::numeric_limits<double>::infinity();
888     else
889       return -std::numeric_limits<double>::infinity();
890   }
891   exp += 1023; // Increment for 1023 bias
892
893   // Number of bits in mantissa is 52. To obtain the mantissa value, we must
894   // extract the high 52 bits from the correct words in pVal.
895   uint64_t mantissa;
896   unsigned hiWord = whichWord(n-1);
897   if (hiWord == 0) {
898     mantissa = Tmp.pVal[0];
899     if (n > 52)
900       mantissa >>= n - 52; // shift down, we want the top 52 bits.
901   } else {
902     assert(hiWord > 0 && "huh?");
903     uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
904     uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
905     mantissa = hibits | lobits;
906   }
907
908   // The leading bit of mantissa is implicit, so get rid of it.
909   uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
910   union {
911     double D;
912     uint64_t I;
913   } T;
914   T.I = sign | (exp << 52) | mantissa;
915   return T.D;
916 }
917
918 // Truncate to new width.
919 APInt APInt::trunc(unsigned width) const {
920   assert(width < BitWidth && "Invalid APInt Truncate request");
921   assert(width && "Can't truncate to 0 bits");
922
923   if (width <= APINT_BITS_PER_WORD)
924     return APInt(width, getRawData()[0]);
925
926   APInt Result(getMemory(getNumWords(width)), width);
927
928   // Copy full words.
929   unsigned i;
930   for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
931     Result.pVal[i] = pVal[i];
932
933   // Truncate and copy any partial word.
934   unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
935   if (bits != 0)
936     Result.pVal[i] = pVal[i] << bits >> bits;
937
938   return Result;
939 }
940
941 // Sign extend to a new width.
942 APInt APInt::sext(unsigned width) const {
943   assert(width > BitWidth && "Invalid APInt SignExtend request");
944
945   if (width <= APINT_BITS_PER_WORD) {
946     uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
947     val = (int64_t)val >> (width - BitWidth);
948     return APInt(width, val >> (APINT_BITS_PER_WORD - width));
949   }
950
951   APInt Result(getMemory(getNumWords(width)), width);
952
953   // Copy full words.
954   unsigned i;
955   uint64_t word = 0;
956   for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
957     word = getRawData()[i];
958     Result.pVal[i] = word;
959   }
960
961   // Read and sign-extend any partial word.
962   unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
963   if (bits != 0)
964     word = (int64_t)getRawData()[i] << bits >> bits;
965   else
966     word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
967
968   // Write remaining full words.
969   for (; i != width / APINT_BITS_PER_WORD; i++) {
970     Result.pVal[i] = word;
971     word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
972   }
973
974   // Write any partial word.
975   bits = (0 - width) % APINT_BITS_PER_WORD;
976   if (bits != 0)
977     Result.pVal[i] = word << bits >> bits;
978
979   return Result;
980 }
981
982 //  Zero extend to a new width.
983 APInt APInt::zext(unsigned width) const {
984   assert(width > BitWidth && "Invalid APInt ZeroExtend request");
985
986   if (width <= APINT_BITS_PER_WORD)
987     return APInt(width, VAL);
988
989   APInt Result(getMemory(getNumWords(width)), width);
990
991   // Copy words.
992   unsigned i;
993   for (i = 0; i != getNumWords(); i++)
994     Result.pVal[i] = getRawData()[i];
995
996   // Zero remaining words.
997   memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
998
999   return Result;
1000 }
1001
1002 APInt APInt::zextOrTrunc(unsigned width) const {
1003   if (BitWidth < width)
1004     return zext(width);
1005   if (BitWidth > width)
1006     return trunc(width);
1007   return *this;
1008 }
1009
1010 APInt APInt::sextOrTrunc(unsigned width) const {
1011   if (BitWidth < width)
1012     return sext(width);
1013   if (BitWidth > width)
1014     return trunc(width);
1015   return *this;
1016 }
1017
1018 APInt APInt::zextOrSelf(unsigned width) const {
1019   if (BitWidth < width)
1020     return zext(width);
1021   return *this;
1022 }
1023
1024 APInt APInt::sextOrSelf(unsigned width) const {
1025   if (BitWidth < width)
1026     return sext(width);
1027   return *this;
1028 }
1029
1030 /// Arithmetic right-shift this APInt by shiftAmt.
1031 /// @brief Arithmetic right-shift function.
1032 APInt APInt::ashr(const APInt &shiftAmt) const {
1033   return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1034 }
1035
1036 /// Arithmetic right-shift this APInt by shiftAmt.
1037 /// @brief Arithmetic right-shift function.
1038 APInt APInt::ashr(unsigned shiftAmt) const {
1039   assert(shiftAmt <= BitWidth && "Invalid shift amount");
1040   // Handle a degenerate case
1041   if (shiftAmt == 0)
1042     return *this;
1043
1044   // Handle single word shifts with built-in ashr
1045   if (isSingleWord()) {
1046     if (shiftAmt == BitWidth)
1047       return APInt(BitWidth, 0); // undefined
1048     else {
1049       unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1050       return APInt(BitWidth,
1051         (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1052     }
1053   }
1054
1055   // If all the bits were shifted out, the result is, technically, undefined.
1056   // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1057   // issues in the algorithm below.
1058   if (shiftAmt == BitWidth) {
1059     if (isNegative())
1060       return APInt(BitWidth, -1ULL, true);
1061     else
1062       return APInt(BitWidth, 0);
1063   }
1064
1065   // Create some space for the result.
1066   uint64_t * val = new uint64_t[getNumWords()];
1067
1068   // Compute some values needed by the following shift algorithms
1069   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1070   unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1071   unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1072   unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1073   if (bitsInWord == 0)
1074     bitsInWord = APINT_BITS_PER_WORD;
1075
1076   // If we are shifting whole words, just move whole words
1077   if (wordShift == 0) {
1078     // Move the words containing significant bits
1079     for (unsigned i = 0; i <= breakWord; ++i)
1080       val[i] = pVal[i+offset]; // move whole word
1081
1082     // Adjust the top significant word for sign bit fill, if negative
1083     if (isNegative())
1084       if (bitsInWord < APINT_BITS_PER_WORD)
1085         val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1086   } else {
1087     // Shift the low order words
1088     for (unsigned i = 0; i < breakWord; ++i) {
1089       // This combines the shifted corresponding word with the low bits from
1090       // the next word (shifted into this word's high bits).
1091       val[i] = (pVal[i+offset] >> wordShift) |
1092                (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1093     }
1094
1095     // Shift the break word. In this case there are no bits from the next word
1096     // to include in this word.
1097     val[breakWord] = pVal[breakWord+offset] >> wordShift;
1098
1099     // Deal with sign extenstion in the break word, and possibly the word before
1100     // it.
1101     if (isNegative()) {
1102       if (wordShift > bitsInWord) {
1103         if (breakWord > 0)
1104           val[breakWord-1] |=
1105             ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1106         val[breakWord] |= ~0ULL;
1107       } else
1108         val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1109     }
1110   }
1111
1112   // Remaining words are 0 or -1, just assign them.
1113   uint64_t fillValue = (isNegative() ? -1ULL : 0);
1114   for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1115     val[i] = fillValue;
1116   return APInt(val, BitWidth).clearUnusedBits();
1117 }
1118
1119 /// Logical right-shift this APInt by shiftAmt.
1120 /// @brief Logical right-shift function.
1121 APInt APInt::lshr(const APInt &shiftAmt) const {
1122   return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1123 }
1124
1125 /// Logical right-shift this APInt by shiftAmt.
1126 /// @brief Logical right-shift function.
1127 APInt APInt::lshr(unsigned shiftAmt) const {
1128   if (isSingleWord()) {
1129     if (shiftAmt >= BitWidth)
1130       return APInt(BitWidth, 0);
1131     else
1132       return APInt(BitWidth, this->VAL >> shiftAmt);
1133   }
1134
1135   // If all the bits were shifted out, the result is 0. This avoids issues
1136   // with shifting by the size of the integer type, which produces undefined
1137   // results. We define these "undefined results" to always be 0.
1138   if (shiftAmt >= BitWidth)
1139     return APInt(BitWidth, 0);
1140
1141   // If none of the bits are shifted out, the result is *this. This avoids
1142   // issues with shifting by the size of the integer type, which produces
1143   // undefined results in the code below. This is also an optimization.
1144   if (shiftAmt == 0)
1145     return *this;
1146
1147   // Create some space for the result.
1148   uint64_t * val = new uint64_t[getNumWords()];
1149
1150   // If we are shifting less than a word, compute the shift with a simple carry
1151   if (shiftAmt < APINT_BITS_PER_WORD) {
1152     lshrNear(val, pVal, getNumWords(), shiftAmt);
1153     return APInt(val, BitWidth).clearUnusedBits();
1154   }
1155
1156   // Compute some values needed by the remaining shift algorithms
1157   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1158   unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1159
1160   // If we are shifting whole words, just move whole words
1161   if (wordShift == 0) {
1162     for (unsigned i = 0; i < getNumWords() - offset; ++i)
1163       val[i] = pVal[i+offset];
1164     for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1165       val[i] = 0;
1166     return APInt(val,BitWidth).clearUnusedBits();
1167   }
1168
1169   // Shift the low order words
1170   unsigned breakWord = getNumWords() - offset -1;
1171   for (unsigned i = 0; i < breakWord; ++i)
1172     val[i] = (pVal[i+offset] >> wordShift) |
1173              (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1174   // Shift the break word.
1175   val[breakWord] = pVal[breakWord+offset] >> wordShift;
1176
1177   // Remaining words are 0
1178   for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1179     val[i] = 0;
1180   return APInt(val, BitWidth).clearUnusedBits();
1181 }
1182
1183 /// Left-shift this APInt by shiftAmt.
1184 /// @brief Left-shift function.
1185 APInt APInt::shl(const APInt &shiftAmt) const {
1186   // It's undefined behavior in C to shift by BitWidth or greater.
1187   return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1188 }
1189
1190 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1191   // If all the bits were shifted out, the result is 0. This avoids issues
1192   // with shifting by the size of the integer type, which produces undefined
1193   // results. We define these "undefined results" to always be 0.
1194   if (shiftAmt == BitWidth)
1195     return APInt(BitWidth, 0);
1196
1197   // If none of the bits are shifted out, the result is *this. This avoids a
1198   // lshr by the words size in the loop below which can produce incorrect
1199   // results. It also avoids the expensive computation below for a common case.
1200   if (shiftAmt == 0)
1201     return *this;
1202
1203   // Create some space for the result.
1204   uint64_t * val = new uint64_t[getNumWords()];
1205
1206   // If we are shifting less than a word, do it the easy way
1207   if (shiftAmt < APINT_BITS_PER_WORD) {
1208     uint64_t carry = 0;
1209     for (unsigned i = 0; i < getNumWords(); i++) {
1210       val[i] = pVal[i] << shiftAmt | carry;
1211       carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1212     }
1213     return APInt(val, BitWidth).clearUnusedBits();
1214   }
1215
1216   // Compute some values needed by the remaining shift algorithms
1217   unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1218   unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1219
1220   // If we are shifting whole words, just move whole words
1221   if (wordShift == 0) {
1222     for (unsigned i = 0; i < offset; i++)
1223       val[i] = 0;
1224     for (unsigned i = offset; i < getNumWords(); i++)
1225       val[i] = pVal[i-offset];
1226     return APInt(val,BitWidth).clearUnusedBits();
1227   }
1228
1229   // Copy whole words from this to Result.
1230   unsigned i = getNumWords() - 1;
1231   for (; i > offset; --i)
1232     val[i] = pVal[i-offset] << wordShift |
1233              pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1234   val[offset] = pVal[0] << wordShift;
1235   for (i = 0; i < offset; ++i)
1236     val[i] = 0;
1237   return APInt(val, BitWidth).clearUnusedBits();
1238 }
1239
1240 APInt APInt::rotl(const APInt &rotateAmt) const {
1241   return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1242 }
1243
1244 APInt APInt::rotl(unsigned rotateAmt) const {
1245   rotateAmt %= BitWidth;
1246   if (rotateAmt == 0)
1247     return *this;
1248   return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1249 }
1250
1251 APInt APInt::rotr(const APInt &rotateAmt) const {
1252   return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1253 }
1254
1255 APInt APInt::rotr(unsigned rotateAmt) const {
1256   rotateAmt %= BitWidth;
1257   if (rotateAmt == 0)
1258     return *this;
1259   return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1260 }
1261
1262 // Square Root - this method computes and returns the square root of "this".
1263 // Three mechanisms are used for computation. For small values (<= 5 bits),
1264 // a table lookup is done. This gets some performance for common cases. For
1265 // values using less than 52 bits, the value is converted to double and then
1266 // the libc sqrt function is called. The result is rounded and then converted
1267 // back to a uint64_t which is then used to construct the result. Finally,
1268 // the Babylonian method for computing square roots is used.
1269 APInt APInt::sqrt() const {
1270
1271   // Determine the magnitude of the value.
1272   unsigned magnitude = getActiveBits();
1273
1274   // Use a fast table for some small values. This also gets rid of some
1275   // rounding errors in libc sqrt for small values.
1276   if (magnitude <= 5) {
1277     static const uint8_t results[32] = {
1278       /*     0 */ 0,
1279       /*  1- 2 */ 1, 1,
1280       /*  3- 6 */ 2, 2, 2, 2,
1281       /*  7-12 */ 3, 3, 3, 3, 3, 3,
1282       /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1283       /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1284       /*    31 */ 6
1285     };
1286     return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1287   }
1288
1289   // If the magnitude of the value fits in less than 52 bits (the precision of
1290   // an IEEE double precision floating point value), then we can use the
1291   // libc sqrt function which will probably use a hardware sqrt computation.
1292   // This should be faster than the algorithm below.
1293   if (magnitude < 52) {
1294 #if HAVE_ROUND
1295     return APInt(BitWidth,
1296                  uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1297 #else
1298     return APInt(BitWidth,
1299                  uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5));
1300 #endif
1301   }
1302
1303   // Okay, all the short cuts are exhausted. We must compute it. The following
1304   // is a classical Babylonian method for computing the square root. This code
1305   // was adapted to APINt from a wikipedia article on such computations.
1306   // See http://www.wikipedia.org/ and go to the page named
1307   // Calculate_an_integer_square_root.
1308   unsigned nbits = BitWidth, i = 4;
1309   APInt testy(BitWidth, 16);
1310   APInt x_old(BitWidth, 1);
1311   APInt x_new(BitWidth, 0);
1312   APInt two(BitWidth, 2);
1313
1314   // Select a good starting value using binary logarithms.
1315   for (;; i += 2, testy = testy.shl(2))
1316     if (i >= nbits || this->ule(testy)) {
1317       x_old = x_old.shl(i / 2);
1318       break;
1319     }
1320
1321   // Use the Babylonian method to arrive at the integer square root:
1322   for (;;) {
1323     x_new = (this->udiv(x_old) + x_old).udiv(two);
1324     if (x_old.ule(x_new))
1325       break;
1326     x_old = x_new;
1327   }
1328
1329   // Make sure we return the closest approximation
1330   // NOTE: The rounding calculation below is correct. It will produce an
1331   // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1332   // determined to be a rounding issue with pari/gp as it begins to use a
1333   // floating point representation after 192 bits. There are no discrepancies
1334   // between this algorithm and pari/gp for bit widths < 192 bits.
1335   APInt square(x_old * x_old);
1336   APInt nextSquare((x_old + 1) * (x_old +1));
1337   if (this->ult(square))
1338     return x_old;
1339   assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1340   APInt midpoint((nextSquare - square).udiv(two));
1341   APInt offset(*this - square);
1342   if (offset.ult(midpoint))
1343     return x_old;
1344   return x_old + 1;
1345 }
1346
1347 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1348 /// iterative extended Euclidean algorithm is used to solve for this value,
1349 /// however we simplify it to speed up calculating only the inverse, and take
1350 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1351 /// (potentially large) APInts around.
1352 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1353   assert(ult(modulo) && "This APInt must be smaller than the modulo");
1354
1355   // Using the properties listed at the following web page (accessed 06/21/08):
1356   //   http://www.numbertheory.org/php/euclid.html
1357   // (especially the properties numbered 3, 4 and 9) it can be proved that
1358   // BitWidth bits suffice for all the computations in the algorithm implemented
1359   // below. More precisely, this number of bits suffice if the multiplicative
1360   // inverse exists, but may not suffice for the general extended Euclidean
1361   // algorithm.
1362
1363   APInt r[2] = { modulo, *this };
1364   APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1365   APInt q(BitWidth, 0);
1366
1367   unsigned i;
1368   for (i = 0; r[i^1] != 0; i ^= 1) {
1369     // An overview of the math without the confusing bit-flipping:
1370     // q = r[i-2] / r[i-1]
1371     // r[i] = r[i-2] % r[i-1]
1372     // t[i] = t[i-2] - t[i-1] * q
1373     udivrem(r[i], r[i^1], q, r[i]);
1374     t[i] -= t[i^1] * q;
1375   }
1376
1377   // If this APInt and the modulo are not coprime, there is no multiplicative
1378   // inverse, so return 0. We check this by looking at the next-to-last
1379   // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1380   // algorithm.
1381   if (r[i] != 1)
1382     return APInt(BitWidth, 0);
1383
1384   // The next-to-last t is the multiplicative inverse.  However, we are
1385   // interested in a positive inverse. Calcuate a positive one from a negative
1386   // one if necessary. A simple addition of the modulo suffices because
1387   // abs(t[i]) is known to be less than *this/2 (see the link above).
1388   return t[i].isNegative() ? t[i] + modulo : t[i];
1389 }
1390
1391 /// Calculate the magic numbers required to implement a signed integer division
1392 /// by a constant as a sequence of multiplies, adds and shifts.  Requires that
1393 /// the divisor not be 0, 1, or -1.  Taken from "Hacker's Delight", Henry S.
1394 /// Warren, Jr., chapter 10.
1395 APInt::ms APInt::magic() const {
1396   const APInt& d = *this;
1397   unsigned p;
1398   APInt ad, anc, delta, q1, r1, q2, r2, t;
1399   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1400   struct ms mag;
1401
1402   ad = d.abs();
1403   t = signedMin + (d.lshr(d.getBitWidth() - 1));
1404   anc = t - 1 - t.urem(ad);   // absolute value of nc
1405   p = d.getBitWidth() - 1;    // initialize p
1406   q1 = signedMin.udiv(anc);   // initialize q1 = 2p/abs(nc)
1407   r1 = signedMin - q1*anc;    // initialize r1 = rem(2p,abs(nc))
1408   q2 = signedMin.udiv(ad);    // initialize q2 = 2p/abs(d)
1409   r2 = signedMin - q2*ad;     // initialize r2 = rem(2p,abs(d))
1410   do {
1411     p = p + 1;
1412     q1 = q1<<1;          // update q1 = 2p/abs(nc)
1413     r1 = r1<<1;          // update r1 = rem(2p/abs(nc))
1414     if (r1.uge(anc)) {  // must be unsigned comparison
1415       q1 = q1 + 1;
1416       r1 = r1 - anc;
1417     }
1418     q2 = q2<<1;          // update q2 = 2p/abs(d)
1419     r2 = r2<<1;          // update r2 = rem(2p/abs(d))
1420     if (r2.uge(ad)) {   // must be unsigned comparison
1421       q2 = q2 + 1;
1422       r2 = r2 - ad;
1423     }
1424     delta = ad - r2;
1425   } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1426
1427   mag.m = q2 + 1;
1428   if (d.isNegative()) mag.m = -mag.m;   // resulting magic number
1429   mag.s = p - d.getBitWidth();          // resulting shift
1430   return mag;
1431 }
1432
1433 /// Calculate the magic numbers required to implement an unsigned integer
1434 /// division by a constant as a sequence of multiplies, adds and shifts.
1435 /// Requires that the divisor not be 0.  Taken from "Hacker's Delight", Henry
1436 /// S. Warren, Jr., chapter 10.
1437 /// LeadingZeros can be used to simplify the calculation if the upper bits
1438 /// of the divided value are known zero.
1439 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1440   const APInt& d = *this;
1441   unsigned p;
1442   APInt nc, delta, q1, r1, q2, r2;
1443   struct mu magu;
1444   magu.a = 0;               // initialize "add" indicator
1445   APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1446   APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1447   APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1448
1449   nc = allOnes - (allOnes - d).urem(d);
1450   p = d.getBitWidth() - 1;  // initialize p
1451   q1 = signedMin.udiv(nc);  // initialize q1 = 2p/nc
1452   r1 = signedMin - q1*nc;   // initialize r1 = rem(2p,nc)
1453   q2 = signedMax.udiv(d);   // initialize q2 = (2p-1)/d
1454   r2 = signedMax - q2*d;    // initialize r2 = rem((2p-1),d)
1455   do {
1456     p = p + 1;
1457     if (r1.uge(nc - r1)) {
1458       q1 = q1 + q1 + 1;  // update q1
1459       r1 = r1 + r1 - nc; // update r1
1460     }
1461     else {
1462       q1 = q1+q1; // update q1
1463       r1 = r1+r1; // update r1
1464     }
1465     if ((r2 + 1).uge(d - r2)) {
1466       if (q2.uge(signedMax)) magu.a = 1;
1467       q2 = q2+q2 + 1;     // update q2
1468       r2 = r2+r2 + 1 - d; // update r2
1469     }
1470     else {
1471       if (q2.uge(signedMin)) magu.a = 1;
1472       q2 = q2+q2;     // update q2
1473       r2 = r2+r2 + 1; // update r2
1474     }
1475     delta = d - 1 - r2;
1476   } while (p < d.getBitWidth()*2 &&
1477            (q1.ult(delta) || (q1 == delta && r1 == 0)));
1478   magu.m = q2 + 1; // resulting magic number
1479   magu.s = p - d.getBitWidth();  // resulting shift
1480   return magu;
1481 }
1482
1483 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1484 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1485 /// variables here have the same names as in the algorithm. Comments explain
1486 /// the algorithm and any deviation from it.
1487 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1488                      unsigned m, unsigned n) {
1489   assert(u && "Must provide dividend");
1490   assert(v && "Must provide divisor");
1491   assert(q && "Must provide quotient");
1492   assert(u != v && u != q && v != q && "Must us different memory");
1493   assert(n>1 && "n must be > 1");
1494
1495   // Knuth uses the value b as the base of the number system. In our case b
1496   // is 2^31 so we just set it to -1u.
1497   uint64_t b = uint64_t(1) << 32;
1498
1499 #if 0
1500   DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1501   DEBUG(dbgs() << "KnuthDiv: original:");
1502   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1503   DEBUG(dbgs() << " by");
1504   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1505   DEBUG(dbgs() << '\n');
1506 #endif
1507   // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1508   // u and v by d. Note that we have taken Knuth's advice here to use a power
1509   // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1510   // 2 allows us to shift instead of multiply and it is easy to determine the
1511   // shift amount from the leading zeros.  We are basically normalizing the u
1512   // and v so that its high bits are shifted to the top of v's range without
1513   // overflow. Note that this can require an extra word in u so that u must
1514   // be of length m+n+1.
1515   unsigned shift = countLeadingZeros(v[n-1]);
1516   unsigned v_carry = 0;
1517   unsigned u_carry = 0;
1518   if (shift) {
1519     for (unsigned i = 0; i < m+n; ++i) {
1520       unsigned u_tmp = u[i] >> (32 - shift);
1521       u[i] = (u[i] << shift) | u_carry;
1522       u_carry = u_tmp;
1523     }
1524     for (unsigned i = 0; i < n; ++i) {
1525       unsigned v_tmp = v[i] >> (32 - shift);
1526       v[i] = (v[i] << shift) | v_carry;
1527       v_carry = v_tmp;
1528     }
1529   }
1530   u[m+n] = u_carry;
1531 #if 0
1532   DEBUG(dbgs() << "KnuthDiv:   normal:");
1533   DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1534   DEBUG(dbgs() << " by");
1535   DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1536   DEBUG(dbgs() << '\n');
1537 #endif
1538
1539   // D2. [Initialize j.]  Set j to m. This is the loop counter over the places.
1540   int j = m;
1541   do {
1542     DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1543     // D3. [Calculate q'.].
1544     //     Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1545     //     Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1546     // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1547     // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1548     // on v[n-2] determines at high speed most of the cases in which the trial
1549     // value qp is one too large, and it eliminates all cases where qp is two
1550     // too large.
1551     uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1552     DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1553     uint64_t qp = dividend / v[n-1];
1554     uint64_t rp = dividend % v[n-1];
1555     if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1556       qp--;
1557       rp += v[n-1];
1558       if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1559         qp--;
1560     }
1561     DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1562
1563     // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1564     // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1565     // consists of a simple multiplication by a one-place number, combined with
1566     // a subtraction.
1567     bool isNeg = false;
1568     for (unsigned i = 0; i < n; ++i) {
1569       uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1570       uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1571       bool borrow = subtrahend > u_tmp;
1572       DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp
1573                    << ", subtrahend == " << subtrahend
1574                    << ", borrow = " << borrow << '\n');
1575
1576       uint64_t result = u_tmp - subtrahend;
1577       unsigned k = j + i;
1578       u[k++] = (unsigned)(result & (b-1)); // subtract low word
1579       u[k++] = (unsigned)(result >> 32);   // subtract high word
1580       while (borrow && k <= m+n) { // deal with borrow to the left
1581         borrow = u[k] == 0;
1582         u[k]--;
1583         k++;
1584       }
1585       isNeg |= borrow;
1586       DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ",  u[j+i+1] == " <<
1587                     u[j+i+1] << '\n');
1588     }
1589     DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1590     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1591     DEBUG(dbgs() << '\n');
1592     // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1593     // this step is actually negative, (u[j+n]...u[j]) should be left as the
1594     // true value plus b**(n+1), namely as the b's complement of
1595     // the true value, and a "borrow" to the left should be remembered.
1596     //
1597     if (isNeg) {
1598       bool carry = true;  // true because b's complement is "complement + 1"
1599       for (unsigned i = 0; i <= m+n; ++i) {
1600         u[i] = ~u[i] + carry; // b's complement
1601         carry = carry && u[i] == 0;
1602       }
1603     }
1604     DEBUG(dbgs() << "KnuthDiv: after complement:");
1605     DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1606     DEBUG(dbgs() << '\n');
1607
1608     // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1609     // negative, go to step D6; otherwise go on to step D7.
1610     q[j] = (unsigned)qp;
1611     if (isNeg) {
1612       // D6. [Add back]. The probability that this step is necessary is very
1613       // small, on the order of only 2/b. Make sure that test data accounts for
1614       // this possibility. Decrease q[j] by 1
1615       q[j]--;
1616       // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1617       // A carry will occur to the left of u[j+n], and it should be ignored
1618       // since it cancels with the borrow that occurred in D4.
1619       bool carry = false;
1620       for (unsigned i = 0; i < n; i++) {
1621         unsigned limit = std::min(u[j+i],v[i]);
1622         u[j+i] += v[i] + carry;
1623         carry = u[j+i] < limit || (carry && u[j+i] == limit);
1624       }
1625       u[j+n] += carry;
1626     }
1627     DEBUG(dbgs() << "KnuthDiv: after correction:");
1628     DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]);
1629     DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1630
1631   // D7. [Loop on j.]  Decrease j by one. Now if j >= 0, go back to D3.
1632   } while (--j >= 0);
1633
1634   DEBUG(dbgs() << "KnuthDiv: quotient:");
1635   DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1636   DEBUG(dbgs() << '\n');
1637
1638   // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1639   // remainder may be obtained by dividing u[...] by d. If r is non-null we
1640   // compute the remainder (urem uses this).
1641   if (r) {
1642     // The value d is expressed by the "shift" value above since we avoided
1643     // multiplication by d by using a shift left. So, all we have to do is
1644     // shift right here. In order to mak
1645     if (shift) {
1646       unsigned carry = 0;
1647       DEBUG(dbgs() << "KnuthDiv: remainder:");
1648       for (int i = n-1; i >= 0; i--) {
1649         r[i] = (u[i] >> shift) | carry;
1650         carry = u[i] << (32 - shift);
1651         DEBUG(dbgs() << " " << r[i]);
1652       }
1653     } else {
1654       for (int i = n-1; i >= 0; i--) {
1655         r[i] = u[i];
1656         DEBUG(dbgs() << " " << r[i]);
1657       }
1658     }
1659     DEBUG(dbgs() << '\n');
1660   }
1661 #if 0
1662   DEBUG(dbgs() << '\n');
1663 #endif
1664 }
1665
1666 void APInt::divide(const APInt LHS, unsigned lhsWords,
1667                    const APInt &RHS, unsigned rhsWords,
1668                    APInt *Quotient, APInt *Remainder)
1669 {
1670   assert(lhsWords >= rhsWords && "Fractional result");
1671
1672   // First, compose the values into an array of 32-bit words instead of
1673   // 64-bit words. This is a necessity of both the "short division" algorithm
1674   // and the Knuth "classical algorithm" which requires there to be native
1675   // operations for +, -, and * on an m bit value with an m*2 bit result. We
1676   // can't use 64-bit operands here because we don't have native results of
1677   // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1678   // work on large-endian machines.
1679   uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
1680   unsigned n = rhsWords * 2;
1681   unsigned m = (lhsWords * 2) - n;
1682
1683   // Allocate space for the temporary values we need either on the stack, if
1684   // it will fit, or on the heap if it won't.
1685   unsigned SPACE[128];
1686   unsigned *U = 0;
1687   unsigned *V = 0;
1688   unsigned *Q = 0;
1689   unsigned *R = 0;
1690   if ((Remainder?4:3)*n+2*m+1 <= 128) {
1691     U = &SPACE[0];
1692     V = &SPACE[m+n+1];
1693     Q = &SPACE[(m+n+1) + n];
1694     if (Remainder)
1695       R = &SPACE[(m+n+1) + n + (m+n)];
1696   } else {
1697     U = new unsigned[m + n + 1];
1698     V = new unsigned[n];
1699     Q = new unsigned[m+n];
1700     if (Remainder)
1701       R = new unsigned[n];
1702   }
1703
1704   // Initialize the dividend
1705   memset(U, 0, (m+n+1)*sizeof(unsigned));
1706   for (unsigned i = 0; i < lhsWords; ++i) {
1707     uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1708     U[i * 2] = (unsigned)(tmp & mask);
1709     U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1710   }
1711   U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1712
1713   // Initialize the divisor
1714   memset(V, 0, (n)*sizeof(unsigned));
1715   for (unsigned i = 0; i < rhsWords; ++i) {
1716     uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1717     V[i * 2] = (unsigned)(tmp & mask);
1718     V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
1719   }
1720
1721   // initialize the quotient and remainder
1722   memset(Q, 0, (m+n) * sizeof(unsigned));
1723   if (Remainder)
1724     memset(R, 0, n * sizeof(unsigned));
1725
1726   // Now, adjust m and n for the Knuth division. n is the number of words in
1727   // the divisor. m is the number of words by which the dividend exceeds the
1728   // divisor (i.e. m+n is the length of the dividend). These sizes must not
1729   // contain any zero words or the Knuth algorithm fails.
1730   for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1731     n--;
1732     m++;
1733   }
1734   for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1735     m--;
1736
1737   // If we're left with only a single word for the divisor, Knuth doesn't work
1738   // so we implement the short division algorithm here. This is much simpler
1739   // and faster because we are certain that we can divide a 64-bit quantity
1740   // by a 32-bit quantity at hardware speed and short division is simply a
1741   // series of such operations. This is just like doing short division but we
1742   // are using base 2^32 instead of base 10.
1743   assert(n != 0 && "Divide by zero?");
1744   if (n == 1) {
1745     unsigned divisor = V[0];
1746     unsigned remainder = 0;
1747     for (int i = m+n-1; i >= 0; i--) {
1748       uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1749       if (partial_dividend == 0) {
1750         Q[i] = 0;
1751         remainder = 0;
1752       } else if (partial_dividend < divisor) {
1753         Q[i] = 0;
1754         remainder = (unsigned)partial_dividend;
1755       } else if (partial_dividend == divisor) {
1756         Q[i] = 1;
1757         remainder = 0;
1758       } else {
1759         Q[i] = (unsigned)(partial_dividend / divisor);
1760         remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1761       }
1762     }
1763     if (R)
1764       R[0] = remainder;
1765   } else {
1766     // Now we're ready to invoke the Knuth classical divide algorithm. In this
1767     // case n > 1.
1768     KnuthDiv(U, V, Q, R, m, n);
1769   }
1770
1771   // If the caller wants the quotient
1772   if (Quotient) {
1773     // Set up the Quotient value's memory.
1774     if (Quotient->BitWidth != LHS.BitWidth) {
1775       if (Quotient->isSingleWord())
1776         Quotient->VAL = 0;
1777       else
1778         delete [] Quotient->pVal;
1779       Quotient->BitWidth = LHS.BitWidth;
1780       if (!Quotient->isSingleWord())
1781         Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1782     } else
1783       Quotient->clearAllBits();
1784
1785     // The quotient is in Q. Reconstitute the quotient into Quotient's low
1786     // order words.
1787     if (lhsWords == 1) {
1788       uint64_t tmp =
1789         uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1790       if (Quotient->isSingleWord())
1791         Quotient->VAL = tmp;
1792       else
1793         Quotient->pVal[0] = tmp;
1794     } else {
1795       assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1796       for (unsigned i = 0; i < lhsWords; ++i)
1797         Quotient->pVal[i] =
1798           uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1799     }
1800   }
1801
1802   // If the caller wants the remainder
1803   if (Remainder) {
1804     // Set up the Remainder value's memory.
1805     if (Remainder->BitWidth != RHS.BitWidth) {
1806       if (Remainder->isSingleWord())
1807         Remainder->VAL = 0;
1808       else
1809         delete [] Remainder->pVal;
1810       Remainder->BitWidth = RHS.BitWidth;
1811       if (!Remainder->isSingleWord())
1812         Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1813     } else
1814       Remainder->clearAllBits();
1815
1816     // The remainder is in R. Reconstitute the remainder into Remainder's low
1817     // order words.
1818     if (rhsWords == 1) {
1819       uint64_t tmp =
1820         uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1821       if (Remainder->isSingleWord())
1822         Remainder->VAL = tmp;
1823       else
1824         Remainder->pVal[0] = tmp;
1825     } else {
1826       assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1827       for (unsigned i = 0; i < rhsWords; ++i)
1828         Remainder->pVal[i] =
1829           uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1830     }
1831   }
1832
1833   // Clean up the memory we allocated.
1834   if (U != &SPACE[0]) {
1835     delete [] U;
1836     delete [] V;
1837     delete [] Q;
1838     delete [] R;
1839   }
1840 }
1841
1842 APInt APInt::udiv(const APInt& RHS) const {
1843   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1844
1845   // First, deal with the easy case
1846   if (isSingleWord()) {
1847     assert(RHS.VAL != 0 && "Divide by zero?");
1848     return APInt(BitWidth, VAL / RHS.VAL);
1849   }
1850
1851   // Get some facts about the LHS and RHS number of bits and words
1852   unsigned rhsBits = RHS.getActiveBits();
1853   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1854   assert(rhsWords && "Divided by zero???");
1855   unsigned lhsBits = this->getActiveBits();
1856   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1857
1858   // Deal with some degenerate cases
1859   if (!lhsWords)
1860     // 0 / X ===> 0
1861     return APInt(BitWidth, 0);
1862   else if (lhsWords < rhsWords || this->ult(RHS)) {
1863     // X / Y ===> 0, iff X < Y
1864     return APInt(BitWidth, 0);
1865   } else if (*this == RHS) {
1866     // X / X ===> 1
1867     return APInt(BitWidth, 1);
1868   } else if (lhsWords == 1 && rhsWords == 1) {
1869     // All high words are zero, just use native divide
1870     return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1871   }
1872
1873   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1874   APInt Quotient(1,0); // to hold result.
1875   divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1876   return Quotient;
1877 }
1878
1879 APInt APInt::sdiv(const APInt &RHS) const {
1880   if (isNegative()) {
1881     if (RHS.isNegative())
1882       return (-(*this)).udiv(-RHS);
1883     return -((-(*this)).udiv(RHS));
1884   }
1885   if (RHS.isNegative())
1886     return -(this->udiv(-RHS));
1887   return this->udiv(RHS);
1888 }
1889
1890 APInt APInt::urem(const APInt& RHS) const {
1891   assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1892   if (isSingleWord()) {
1893     assert(RHS.VAL != 0 && "Remainder by zero?");
1894     return APInt(BitWidth, VAL % RHS.VAL);
1895   }
1896
1897   // Get some facts about the LHS
1898   unsigned lhsBits = getActiveBits();
1899   unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1900
1901   // Get some facts about the RHS
1902   unsigned rhsBits = RHS.getActiveBits();
1903   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1904   assert(rhsWords && "Performing remainder operation by zero ???");
1905
1906   // Check the degenerate cases
1907   if (lhsWords == 0) {
1908     // 0 % Y ===> 0
1909     return APInt(BitWidth, 0);
1910   } else if (lhsWords < rhsWords || this->ult(RHS)) {
1911     // X % Y ===> X, iff X < Y
1912     return *this;
1913   } else if (*this == RHS) {
1914     // X % X == 0;
1915     return APInt(BitWidth, 0);
1916   } else if (lhsWords == 1) {
1917     // All high words are zero, just use native remainder
1918     return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1919   }
1920
1921   // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1922   APInt Remainder(1,0);
1923   divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1924   return Remainder;
1925 }
1926
1927 APInt APInt::srem(const APInt &RHS) const {
1928   if (isNegative()) {
1929     if (RHS.isNegative())
1930       return -((-(*this)).urem(-RHS));
1931     return -((-(*this)).urem(RHS));
1932   }
1933   if (RHS.isNegative())
1934     return this->urem(-RHS);
1935   return this->urem(RHS);
1936 }
1937
1938 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1939                     APInt &Quotient, APInt &Remainder) {
1940   // Get some size facts about the dividend and divisor
1941   unsigned lhsBits  = LHS.getActiveBits();
1942   unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1943   unsigned rhsBits  = RHS.getActiveBits();
1944   unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1945
1946   // Check the degenerate cases
1947   if (lhsWords == 0) {
1948     Quotient = 0;                // 0 / Y ===> 0
1949     Remainder = 0;               // 0 % Y ===> 0
1950     return;
1951   }
1952
1953   if (lhsWords < rhsWords || LHS.ult(RHS)) {
1954     Remainder = LHS;            // X % Y ===> X, iff X < Y
1955     Quotient = 0;               // X / Y ===> 0, iff X < Y
1956     return;
1957   }
1958
1959   if (LHS == RHS) {
1960     Quotient  = 1;              // X / X ===> 1
1961     Remainder = 0;              // X % X ===> 0;
1962     return;
1963   }
1964
1965   if (lhsWords == 1 && rhsWords == 1) {
1966     // There is only one word to consider so use the native versions.
1967     uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1968     uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1969     Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1970     Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
1971     return;
1972   }
1973
1974   // Okay, lets do it the long way
1975   divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1976 }
1977
1978 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
1979                     APInt &Quotient, APInt &Remainder) {
1980   if (LHS.isNegative()) {
1981     if (RHS.isNegative())
1982       APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
1983     else {
1984       APInt::udivrem(-LHS, RHS, Quotient, Remainder);
1985       Quotient = -Quotient;
1986     }
1987     Remainder = -Remainder;
1988   } else if (RHS.isNegative()) {
1989     APInt::udivrem(LHS, -RHS, Quotient, Remainder);
1990     Quotient = -Quotient;
1991   } else {
1992     APInt::udivrem(LHS, RHS, Quotient, Remainder);
1993   }
1994 }
1995
1996 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
1997   APInt Res = *this+RHS;
1998   Overflow = isNonNegative() == RHS.isNonNegative() &&
1999              Res.isNonNegative() != isNonNegative();
2000   return Res;
2001 }
2002
2003 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
2004   APInt Res = *this+RHS;
2005   Overflow = Res.ult(RHS);
2006   return Res;
2007 }
2008
2009 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
2010   APInt Res = *this - RHS;
2011   Overflow = isNonNegative() != RHS.isNonNegative() &&
2012              Res.isNonNegative() != isNonNegative();
2013   return Res;
2014 }
2015
2016 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
2017   APInt Res = *this-RHS;
2018   Overflow = Res.ugt(*this);
2019   return Res;
2020 }
2021
2022 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
2023   // MININT/-1  -->  overflow.
2024   Overflow = isMinSignedValue() && RHS.isAllOnesValue();
2025   return sdiv(RHS);
2026 }
2027
2028 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
2029   APInt Res = *this * RHS;
2030   
2031   if (*this != 0 && RHS != 0)
2032     Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
2033   else
2034     Overflow = false;
2035   return Res;
2036 }
2037
2038 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
2039   APInt Res = *this * RHS;
2040
2041   if (*this != 0 && RHS != 0)
2042     Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
2043   else
2044     Overflow = false;
2045   return Res;
2046 }
2047
2048 APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const {
2049   Overflow = ShAmt >= getBitWidth();
2050   if (Overflow)
2051     ShAmt = getBitWidth()-1;
2052
2053   if (isNonNegative()) // Don't allow sign change.
2054     Overflow = ShAmt >= countLeadingZeros();
2055   else
2056     Overflow = ShAmt >= countLeadingOnes();
2057   
2058   return *this << ShAmt;
2059 }
2060
2061
2062
2063
2064 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
2065   // Check our assumptions here
2066   assert(!str.empty() && "Invalid string length");
2067   assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 || 
2068           radix == 36) &&
2069          "Radix should be 2, 8, 10, 16, or 36!");
2070
2071   StringRef::iterator p = str.begin();
2072   size_t slen = str.size();
2073   bool isNeg = *p == '-';
2074   if (*p == '-' || *p == '+') {
2075     p++;
2076     slen--;
2077     assert(slen && "String is only a sign, needs a value.");
2078   }
2079   assert((slen <= numbits || radix != 2) && "Insufficient bit width");
2080   assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
2081   assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
2082   assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2083          "Insufficient bit width");
2084
2085   // Allocate memory
2086   if (!isSingleWord())
2087     pVal = getClearedMemory(getNumWords());
2088
2089   // Figure out if we can shift instead of multiply
2090   unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2091
2092   // Set up an APInt for the digit to add outside the loop so we don't
2093   // constantly construct/destruct it.
2094   APInt apdigit(getBitWidth(), 0);
2095   APInt apradix(getBitWidth(), radix);
2096
2097   // Enter digit traversal loop
2098   for (StringRef::iterator e = str.end(); p != e; ++p) {
2099     unsigned digit = getDigit(*p, radix);
2100     assert(digit < radix && "Invalid character in digit string");
2101
2102     // Shift or multiply the value by the radix
2103     if (slen > 1) {
2104       if (shift)
2105         *this <<= shift;
2106       else
2107         *this *= apradix;
2108     }
2109
2110     // Add in the digit we just interpreted
2111     if (apdigit.isSingleWord())
2112       apdigit.VAL = digit;
2113     else
2114       apdigit.pVal[0] = digit;
2115     *this += apdigit;
2116   }
2117   // If its negative, put it in two's complement form
2118   if (isNeg) {
2119     --(*this);
2120     this->flipAllBits();
2121   }
2122 }
2123
2124 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2125                      bool Signed, bool formatAsCLiteral) const {
2126   assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || 
2127           Radix == 36) &&
2128          "Radix should be 2, 8, 10, 16, or 36!");
2129
2130   const char *Prefix = "";
2131   if (formatAsCLiteral) {
2132     switch (Radix) {
2133       case 2:
2134         // Binary literals are a non-standard extension added in gcc 4.3:
2135         // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2136         Prefix = "0b";
2137         break;
2138       case 8:
2139         Prefix = "0";
2140         break;
2141       case 10:
2142         break; // No prefix
2143       case 16:
2144         Prefix = "0x";
2145         break;
2146       default:
2147         llvm_unreachable("Invalid radix!");
2148     }
2149   }
2150
2151   // First, check for a zero value and just short circuit the logic below.
2152   if (*this == 0) {
2153     while (*Prefix) {
2154       Str.push_back(*Prefix);
2155       ++Prefix;
2156     };
2157     Str.push_back('0');
2158     return;
2159   }
2160
2161   static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2162
2163   if (isSingleWord()) {
2164     char Buffer[65];
2165     char *BufPtr = Buffer+65;
2166
2167     uint64_t N;
2168     if (!Signed) {
2169       N = getZExtValue();
2170     } else {
2171       int64_t I = getSExtValue();
2172       if (I >= 0) {
2173         N = I;
2174       } else {
2175         Str.push_back('-');
2176         N = -(uint64_t)I;
2177       }
2178     }
2179
2180     while (*Prefix) {
2181       Str.push_back(*Prefix);
2182       ++Prefix;
2183     };
2184
2185     while (N) {
2186       *--BufPtr = Digits[N % Radix];
2187       N /= Radix;
2188     }
2189     Str.append(BufPtr, Buffer+65);
2190     return;
2191   }
2192
2193   APInt Tmp(*this);
2194
2195   if (Signed && isNegative()) {
2196     // They want to print the signed version and it is a negative value
2197     // Flip the bits and add one to turn it into the equivalent positive
2198     // value and put a '-' in the result.
2199     Tmp.flipAllBits();
2200     ++Tmp;
2201     Str.push_back('-');
2202   }
2203
2204   while (*Prefix) {
2205     Str.push_back(*Prefix);
2206     ++Prefix;
2207   };
2208
2209   // We insert the digits backward, then reverse them to get the right order.
2210   unsigned StartDig = Str.size();
2211
2212   // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2213   // because the number of bits per digit (1, 3 and 4 respectively) divides
2214   // equaly.  We just shift until the value is zero.
2215   if (Radix == 2 || Radix == 8 || Radix == 16) {
2216     // Just shift tmp right for each digit width until it becomes zero
2217     unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2218     unsigned MaskAmt = Radix - 1;
2219
2220     while (Tmp != 0) {
2221       unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2222       Str.push_back(Digits[Digit]);
2223       Tmp = Tmp.lshr(ShiftAmt);
2224     }
2225   } else {
2226     APInt divisor(Radix == 10? 4 : 8, Radix);
2227     while (Tmp != 0) {
2228       APInt APdigit(1, 0);
2229       APInt tmp2(Tmp.getBitWidth(), 0);
2230       divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2231              &APdigit);
2232       unsigned Digit = (unsigned)APdigit.getZExtValue();
2233       assert(Digit < Radix && "divide failed");
2234       Str.push_back(Digits[Digit]);
2235       Tmp = tmp2;
2236     }
2237   }
2238
2239   // Reverse the digits before returning.
2240   std::reverse(Str.begin()+StartDig, Str.end());
2241 }
2242
2243 /// toString - This returns the APInt as a std::string.  Note that this is an
2244 /// inefficient method.  It is better to pass in a SmallVector/SmallString
2245 /// to the methods above.
2246 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2247   SmallString<40> S;
2248   toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2249   return S.str();
2250 }
2251
2252
2253 void APInt::dump() const {
2254   SmallString<40> S, U;
2255   this->toStringUnsigned(U);
2256   this->toStringSigned(S);
2257   dbgs() << "APInt(" << BitWidth << "b, "
2258          << U.str() << "u " << S.str() << "s)";
2259 }
2260
2261 void APInt::print(raw_ostream &OS, bool isSigned) const {
2262   SmallString<40> S;
2263   this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2264   OS << S.str();
2265 }
2266
2267 // This implements a variety of operations on a representation of
2268 // arbitrary precision, two's-complement, bignum integer values.
2269
2270 // Assumed by lowHalf, highHalf, partMSB and partLSB.  A fairly safe
2271 // and unrestricting assumption.
2272 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2273 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2274
2275 /* Some handy functions local to this file.  */
2276 namespace {
2277
2278   /* Returns the integer part with the least significant BITS set.
2279      BITS cannot be zero.  */
2280   static inline integerPart
2281   lowBitMask(unsigned int bits)
2282   {
2283     assert(bits != 0 && bits <= integerPartWidth);
2284
2285     return ~(integerPart) 0 >> (integerPartWidth - bits);
2286   }
2287
2288   /* Returns the value of the lower half of PART.  */
2289   static inline integerPart
2290   lowHalf(integerPart part)
2291   {
2292     return part & lowBitMask(integerPartWidth / 2);
2293   }
2294
2295   /* Returns the value of the upper half of PART.  */
2296   static inline integerPart
2297   highHalf(integerPart part)
2298   {
2299     return part >> (integerPartWidth / 2);
2300   }
2301
2302   /* Returns the bit number of the most significant set bit of a part.
2303      If the input number has no bits set -1U is returned.  */
2304   static unsigned int
2305   partMSB(integerPart value)
2306   {
2307     return findLastSet(value, ZB_Max);
2308   }
2309
2310   /* Returns the bit number of the least significant set bit of a
2311      part.  If the input number has no bits set -1U is returned.  */
2312   static unsigned int
2313   partLSB(integerPart value)
2314   {
2315     return findFirstSet(value, ZB_Max);
2316   }
2317 }
2318
2319 /* Sets the least significant part of a bignum to the input value, and
2320    zeroes out higher parts.  */
2321 void
2322 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2323 {
2324   unsigned int i;
2325
2326   assert(parts > 0);
2327
2328   dst[0] = part;
2329   for (i = 1; i < parts; i++)
2330     dst[i] = 0;
2331 }
2332
2333 /* Assign one bignum to another.  */
2334 void
2335 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2336 {
2337   unsigned int i;
2338
2339   for (i = 0; i < parts; i++)
2340     dst[i] = src[i];
2341 }
2342
2343 /* Returns true if a bignum is zero, false otherwise.  */
2344 bool
2345 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2346 {
2347   unsigned int i;
2348
2349   for (i = 0; i < parts; i++)
2350     if (src[i])
2351       return false;
2352
2353   return true;
2354 }
2355
2356 /* Extract the given bit of a bignum; returns 0 or 1.  */
2357 int
2358 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2359 {
2360   return (parts[bit / integerPartWidth] &
2361           ((integerPart) 1 << bit % integerPartWidth)) != 0;
2362 }
2363
2364 /* Set the given bit of a bignum. */
2365 void
2366 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2367 {
2368   parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2369 }
2370
2371 /* Clears the given bit of a bignum. */
2372 void
2373 APInt::tcClearBit(integerPart *parts, unsigned int bit)
2374 {
2375   parts[bit / integerPartWidth] &=
2376     ~((integerPart) 1 << (bit % integerPartWidth));
2377 }
2378
2379 /* Returns the bit number of the least significant set bit of a
2380    number.  If the input number has no bits set -1U is returned.  */
2381 unsigned int
2382 APInt::tcLSB(const integerPart *parts, unsigned int n)
2383 {
2384   unsigned int i, lsb;
2385
2386   for (i = 0; i < n; i++) {
2387       if (parts[i] != 0) {
2388           lsb = partLSB(parts[i]);
2389
2390           return lsb + i * integerPartWidth;
2391       }
2392   }
2393
2394   return -1U;
2395 }
2396
2397 /* Returns the bit number of the most significant set bit of a number.
2398    If the input number has no bits set -1U is returned.  */
2399 unsigned int
2400 APInt::tcMSB(const integerPart *parts, unsigned int n)
2401 {
2402   unsigned int msb;
2403
2404   do {
2405     --n;
2406
2407     if (parts[n] != 0) {
2408       msb = partMSB(parts[n]);
2409
2410       return msb + n * integerPartWidth;
2411     }
2412   } while (n);
2413
2414   return -1U;
2415 }
2416
2417 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2418    srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2419    the least significant bit of DST.  All high bits above srcBITS in
2420    DST are zero-filled.  */
2421 void
2422 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,
2423                  unsigned int srcBits, unsigned int srcLSB)
2424 {
2425   unsigned int firstSrcPart, dstParts, shift, n;
2426
2427   dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2428   assert(dstParts <= dstCount);
2429
2430   firstSrcPart = srcLSB / integerPartWidth;
2431   tcAssign (dst, src + firstSrcPart, dstParts);
2432
2433   shift = srcLSB % integerPartWidth;
2434   tcShiftRight (dst, dstParts, shift);
2435
2436   /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2437      in DST.  If this is less that srcBits, append the rest, else
2438      clear the high bits.  */
2439   n = dstParts * integerPartWidth - shift;
2440   if (n < srcBits) {
2441     integerPart mask = lowBitMask (srcBits - n);
2442     dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2443                           << n % integerPartWidth);
2444   } else if (n > srcBits) {
2445     if (srcBits % integerPartWidth)
2446       dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2447   }
2448
2449   /* Clear high parts.  */
2450   while (dstParts < dstCount)
2451     dst[dstParts++] = 0;
2452 }
2453
2454 /* DST += RHS + C where C is zero or one.  Returns the carry flag.  */
2455 integerPart
2456 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2457              integerPart c, unsigned int parts)
2458 {
2459   unsigned int i;
2460
2461   assert(c <= 1);
2462
2463   for (i = 0; i < parts; i++) {
2464     integerPart l;
2465
2466     l = dst[i];
2467     if (c) {
2468       dst[i] += rhs[i] + 1;
2469       c = (dst[i] <= l);
2470     } else {
2471       dst[i] += rhs[i];
2472       c = (dst[i] < l);
2473     }
2474   }
2475
2476   return c;
2477 }
2478
2479 /* DST -= RHS + C where C is zero or one.  Returns the carry flag.  */
2480 integerPart
2481 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2482                   integerPart c, unsigned int parts)
2483 {
2484   unsigned int i;
2485
2486   assert(c <= 1);
2487
2488   for (i = 0; i < parts; i++) {
2489     integerPart l;
2490
2491     l = dst[i];
2492     if (c) {
2493       dst[i] -= rhs[i] + 1;
2494       c = (dst[i] >= l);
2495     } else {
2496       dst[i] -= rhs[i];
2497       c = (dst[i] > l);
2498     }
2499   }
2500
2501   return c;
2502 }
2503
2504 /* Negate a bignum in-place.  */
2505 void
2506 APInt::tcNegate(integerPart *dst, unsigned int parts)
2507 {
2508   tcComplement(dst, parts);
2509   tcIncrement(dst, parts);
2510 }
2511
2512 /*  DST += SRC * MULTIPLIER + CARRY   if add is true
2513     DST  = SRC * MULTIPLIER + CARRY   if add is false
2514
2515     Requires 0 <= DSTPARTS <= SRCPARTS + 1.  If DST overlaps SRC
2516     they must start at the same point, i.e. DST == SRC.
2517
2518     If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2519     returned.  Otherwise DST is filled with the least significant
2520     DSTPARTS parts of the result, and if all of the omitted higher
2521     parts were zero return zero, otherwise overflow occurred and
2522     return one.  */
2523 int
2524 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2525                       integerPart multiplier, integerPart carry,
2526                       unsigned int srcParts, unsigned int dstParts,
2527                       bool add)
2528 {
2529   unsigned int i, n;
2530
2531   /* Otherwise our writes of DST kill our later reads of SRC.  */
2532   assert(dst <= src || dst >= src + srcParts);
2533   assert(dstParts <= srcParts + 1);
2534
2535   /* N loops; minimum of dstParts and srcParts.  */
2536   n = dstParts < srcParts ? dstParts: srcParts;
2537
2538   for (i = 0; i < n; i++) {
2539     integerPart low, mid, high, srcPart;
2540
2541       /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2542
2543          This cannot overflow, because
2544
2545          (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2546
2547          which is less than n^2.  */
2548
2549     srcPart = src[i];
2550
2551     if (multiplier == 0 || srcPart == 0)        {
2552       low = carry;
2553       high = 0;
2554     } else {
2555       low = lowHalf(srcPart) * lowHalf(multiplier);
2556       high = highHalf(srcPart) * highHalf(multiplier);
2557
2558       mid = lowHalf(srcPart) * highHalf(multiplier);
2559       high += highHalf(mid);
2560       mid <<= integerPartWidth / 2;
2561       if (low + mid < low)
2562         high++;
2563       low += mid;
2564
2565       mid = highHalf(srcPart) * lowHalf(multiplier);
2566       high += highHalf(mid);
2567       mid <<= integerPartWidth / 2;
2568       if (low + mid < low)
2569         high++;
2570       low += mid;
2571
2572       /* Now add carry.  */
2573       if (low + carry < low)
2574         high++;
2575       low += carry;
2576     }
2577
2578     if (add) {
2579       /* And now DST[i], and store the new low part there.  */
2580       if (low + dst[i] < low)
2581         high++;
2582       dst[i] += low;
2583     } else
2584       dst[i] = low;
2585
2586     carry = high;
2587   }
2588
2589   if (i < dstParts) {
2590     /* Full multiplication, there is no overflow.  */
2591     assert(i + 1 == dstParts);
2592     dst[i] = carry;
2593     return 0;
2594   } else {
2595     /* We overflowed if there is carry.  */
2596     if (carry)
2597       return 1;
2598
2599     /* We would overflow if any significant unwritten parts would be
2600        non-zero.  This is true if any remaining src parts are non-zero
2601        and the multiplier is non-zero.  */
2602     if (multiplier)
2603       for (; i < srcParts; i++)
2604         if (src[i])
2605           return 1;
2606
2607     /* We fitted in the narrow destination.  */
2608     return 0;
2609   }
2610 }
2611
2612 /* DST = LHS * RHS, where DST has the same width as the operands and
2613    is filled with the least significant parts of the result.  Returns
2614    one if overflow occurred, otherwise zero.  DST must be disjoint
2615    from both operands.  */
2616 int
2617 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2618                   const integerPart *rhs, unsigned int parts)
2619 {
2620   unsigned int i;
2621   int overflow;
2622
2623   assert(dst != lhs && dst != rhs);
2624
2625   overflow = 0;
2626   tcSet(dst, 0, parts);
2627
2628   for (i = 0; i < parts; i++)
2629     overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2630                                parts - i, true);
2631
2632   return overflow;
2633 }
2634
2635 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2636    operands.  No overflow occurs.  DST must be disjoint from both
2637    operands.  Returns the number of parts required to hold the
2638    result.  */
2639 unsigned int
2640 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2641                       const integerPart *rhs, unsigned int lhsParts,
2642                       unsigned int rhsParts)
2643 {
2644   /* Put the narrower number on the LHS for less loops below.  */
2645   if (lhsParts > rhsParts) {
2646     return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2647   } else {
2648     unsigned int n;
2649
2650     assert(dst != lhs && dst != rhs);
2651
2652     tcSet(dst, 0, rhsParts);
2653
2654     for (n = 0; n < lhsParts; n++)
2655       tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2656
2657     n = lhsParts + rhsParts;
2658
2659     return n - (dst[n - 1] == 0);
2660   }
2661 }
2662
2663 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2664    Otherwise set LHS to LHS / RHS with the fractional part discarded,
2665    set REMAINDER to the remainder, return zero.  i.e.
2666
2667    OLD_LHS = RHS * LHS + REMAINDER
2668
2669    SCRATCH is a bignum of the same size as the operands and result for
2670    use by the routine; its contents need not be initialized and are
2671    destroyed.  LHS, REMAINDER and SCRATCH must be distinct.
2672 */
2673 int
2674 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2675                 integerPart *remainder, integerPart *srhs,
2676                 unsigned int parts)
2677 {
2678   unsigned int n, shiftCount;
2679   integerPart mask;
2680
2681   assert(lhs != remainder && lhs != srhs && remainder != srhs);
2682
2683   shiftCount = tcMSB(rhs, parts) + 1;
2684   if (shiftCount == 0)
2685     return true;
2686
2687   shiftCount = parts * integerPartWidth - shiftCount;
2688   n = shiftCount / integerPartWidth;
2689   mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2690
2691   tcAssign(srhs, rhs, parts);
2692   tcShiftLeft(srhs, parts, shiftCount);
2693   tcAssign(remainder, lhs, parts);
2694   tcSet(lhs, 0, parts);
2695
2696   /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2697      the total.  */
2698   for (;;) {
2699       int compare;
2700
2701       compare = tcCompare(remainder, srhs, parts);
2702       if (compare >= 0) {
2703         tcSubtract(remainder, srhs, 0, parts);
2704         lhs[n] |= mask;
2705       }
2706
2707       if (shiftCount == 0)
2708         break;
2709       shiftCount--;
2710       tcShiftRight(srhs, parts, 1);
2711       if ((mask >>= 1) == 0)
2712         mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2713   }
2714
2715   return false;
2716 }
2717
2718 /* Shift a bignum left COUNT bits in-place.  Shifted in bits are zero.
2719    There are no restrictions on COUNT.  */
2720 void
2721 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2722 {
2723   if (count) {
2724     unsigned int jump, shift;
2725
2726     /* Jump is the inter-part jump; shift is is intra-part shift.  */
2727     jump = count / integerPartWidth;
2728     shift = count % integerPartWidth;
2729
2730     while (parts > jump) {
2731       integerPart part;
2732
2733       parts--;
2734
2735       /* dst[i] comes from the two parts src[i - jump] and, if we have
2736          an intra-part shift, src[i - jump - 1].  */
2737       part = dst[parts - jump];
2738       if (shift) {
2739         part <<= shift;
2740         if (parts >= jump + 1)
2741           part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2742       }
2743
2744       dst[parts] = part;
2745     }
2746
2747     while (parts > 0)
2748       dst[--parts] = 0;
2749   }
2750 }
2751
2752 /* Shift a bignum right COUNT bits in-place.  Shifted in bits are
2753    zero.  There are no restrictions on COUNT.  */
2754 void
2755 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2756 {
2757   if (count) {
2758     unsigned int i, jump, shift;
2759
2760     /* Jump is the inter-part jump; shift is is intra-part shift.  */
2761     jump = count / integerPartWidth;
2762     shift = count % integerPartWidth;
2763
2764     /* Perform the shift.  This leaves the most significant COUNT bits
2765        of the result at zero.  */
2766     for (i = 0; i < parts; i++) {
2767       integerPart part;
2768
2769       if (i + jump >= parts) {
2770         part = 0;
2771       } else {
2772         part = dst[i + jump];
2773         if (shift) {
2774           part >>= shift;
2775           if (i + jump + 1 < parts)
2776             part |= dst[i + jump + 1] << (integerPartWidth - shift);
2777         }
2778       }
2779
2780       dst[i] = part;
2781     }
2782   }
2783 }
2784
2785 /* Bitwise and of two bignums.  */
2786 void
2787 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2788 {
2789   unsigned int i;
2790
2791   for (i = 0; i < parts; i++)
2792     dst[i] &= rhs[i];
2793 }
2794
2795 /* Bitwise inclusive or of two bignums.  */
2796 void
2797 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2798 {
2799   unsigned int i;
2800
2801   for (i = 0; i < parts; i++)
2802     dst[i] |= rhs[i];
2803 }
2804
2805 /* Bitwise exclusive or of two bignums.  */
2806 void
2807 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2808 {
2809   unsigned int i;
2810
2811   for (i = 0; i < parts; i++)
2812     dst[i] ^= rhs[i];
2813 }
2814
2815 /* Complement a bignum in-place.  */
2816 void
2817 APInt::tcComplement(integerPart *dst, unsigned int parts)
2818 {
2819   unsigned int i;
2820
2821   for (i = 0; i < parts; i++)
2822     dst[i] = ~dst[i];
2823 }
2824
2825 /* Comparison (unsigned) of two bignums.  */
2826 int
2827 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2828                  unsigned int parts)
2829 {
2830   while (parts) {
2831       parts--;
2832       if (lhs[parts] == rhs[parts])
2833         continue;
2834
2835       if (lhs[parts] > rhs[parts])
2836         return 1;
2837       else
2838         return -1;
2839     }
2840
2841   return 0;
2842 }
2843
2844 /* Increment a bignum in-place, return the carry flag.  */
2845 integerPart
2846 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2847 {
2848   unsigned int i;
2849
2850   for (i = 0; i < parts; i++)
2851     if (++dst[i] != 0)
2852       break;
2853
2854   return i == parts;
2855 }
2856
2857 /* Decrement a bignum in-place, return the borrow flag.  */
2858 integerPart
2859 APInt::tcDecrement(integerPart *dst, unsigned int parts) {
2860   for (unsigned int i = 0; i < parts; i++) {
2861     // If the current word is non-zero, then the decrement has no effect on the
2862     // higher-order words of the integer and no borrow can occur. Exit early.
2863     if (dst[i]--)
2864       return 0;
2865   }
2866   // If every word was zero, then there is a borrow.
2867   return 1;
2868 }
2869
2870
2871 /* Set the least significant BITS bits of a bignum, clear the
2872    rest.  */
2873 void
2874 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2875                                  unsigned int bits)
2876 {
2877   unsigned int i;
2878
2879   i = 0;
2880   while (bits > integerPartWidth) {
2881     dst[i++] = ~(integerPart) 0;
2882     bits -= integerPartWidth;
2883   }
2884
2885   if (bits)
2886     dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);
2887
2888   while (i < parts)
2889     dst[i++] = 0;
2890 }