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