1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a class to represent arbitrary precision integer
11 // constant values and provide a variety of arithmetic operations on them.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "apint"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/ADT/SmallString.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Support/MathExtras.h"
21 #include "llvm/Support/raw_ostream.h"
28 /// A utility function for allocating memory, checking for allocation failures,
29 /// and ensuring the contents are zeroed.
30 inline static uint64_t* getClearedMemory(unsigned numWords) {
31 uint64_t * result = new uint64_t[numWords];
32 assert(result && "APInt memory allocation fails!");
33 memset(result, 0, numWords * sizeof(uint64_t));
37 /// A utility function for allocating memory and checking for allocation
38 /// failure. The content is not zeroed.
39 inline static uint64_t* getMemory(unsigned numWords) {
40 uint64_t * result = new uint64_t[numWords];
41 assert(result && "APInt memory allocation fails!");
45 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {
46 pVal = getClearedMemory(getNumWords());
48 if (isSigned && int64_t(val) < 0)
49 for (unsigned i = 1; i < getNumWords(); ++i)
53 void APInt::initSlowCase(const APInt& that) {
54 pVal = getMemory(getNumWords());
55 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
59 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
60 : BitWidth(numBits), VAL(0) {
61 assert(BitWidth && "bitwidth too small");
62 assert(bigVal && "Null pointer detected!");
66 // Get memory, cleared to 0
67 pVal = getClearedMemory(getNumWords());
68 // Calculate the number of words to copy
69 unsigned words = std::min<unsigned>(numWords, getNumWords());
70 // Copy the words from bigVal to pVal
71 memcpy(pVal, bigVal, words * APINT_WORD_SIZE);
73 // Make sure unused high bits are cleared
77 APInt::APInt(unsigned numbits, const char StrStart[], unsigned slen,
79 : BitWidth(numbits), VAL(0) {
80 assert(BitWidth && "bitwidth too small");
81 fromString(numbits, StrStart, slen, radix);
84 APInt& APInt::AssignSlowCase(const APInt& RHS) {
85 // Don't do anything for X = X
89 if (BitWidth == RHS.getBitWidth()) {
90 // assume same bit-width single-word case is already handled
91 assert(!isSingleWord());
92 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
97 // assume case where both are single words is already handled
98 assert(!RHS.isSingleWord());
100 pVal = getMemory(RHS.getNumWords());
101 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
102 } else if (getNumWords() == RHS.getNumWords())
103 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
104 else if (RHS.isSingleWord()) {
109 pVal = getMemory(RHS.getNumWords());
110 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
112 BitWidth = RHS.BitWidth;
113 return clearUnusedBits();
116 APInt& APInt::operator=(uint64_t RHS) {
121 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
123 return clearUnusedBits();
126 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
127 void APInt::Profile(FoldingSetNodeID& ID) const {
128 ID.AddInteger(BitWidth);
130 if (isSingleWord()) {
135 unsigned NumWords = getNumWords();
136 for (unsigned i = 0; i < NumWords; ++i)
137 ID.AddInteger(pVal[i]);
140 /// add_1 - This function adds a single "digit" integer, y, to the multiple
141 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
142 /// 1 is returned if there is a carry out, otherwise 0 is returned.
143 /// @returns the carry of the addition.
144 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
145 for (unsigned i = 0; i < len; ++i) {
148 y = 1; // Carry one to next digit.
150 y = 0; // No need to carry so exit early
157 /// @brief Prefix increment operator. Increments the APInt by one.
158 APInt& APInt::operator++() {
162 add_1(pVal, pVal, getNumWords(), 1);
163 return clearUnusedBits();
166 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
167 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
168 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
169 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
170 /// In other words, if y > x then this function returns 1, otherwise 0.
171 /// @returns the borrow out of the subtraction
172 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {
173 for (unsigned i = 0; i < len; ++i) {
177 y = 1; // We have to "borrow 1" from next "digit"
179 y = 0; // No need to borrow
180 break; // Remaining digits are unchanged so exit early
186 /// @brief Prefix decrement operator. Decrements the APInt by one.
187 APInt& APInt::operator--() {
191 sub_1(pVal, getNumWords(), 1);
192 return clearUnusedBits();
195 /// add - This function adds the integer array x to the integer array Y and
196 /// places the result in dest.
197 /// @returns the carry out from the addition
198 /// @brief General addition of 64-bit integer arrays
199 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
202 for (unsigned i = 0; i< len; ++i) {
203 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
204 dest[i] = x[i] + y[i] + carry;
205 carry = dest[i] < limit || (carry && dest[i] == limit);
210 /// Adds the RHS APint to this APInt.
211 /// @returns this, after addition of RHS.
212 /// @brief Addition assignment operator.
213 APInt& APInt::operator+=(const APInt& RHS) {
214 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
218 add(pVal, pVal, RHS.pVal, getNumWords());
220 return clearUnusedBits();
223 /// Subtracts the integer array y from the integer array x
224 /// @returns returns the borrow out.
225 /// @brief Generalized subtraction of 64-bit integer arrays.
226 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
229 for (unsigned i = 0; i < len; ++i) {
230 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
231 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
232 dest[i] = x_tmp - y[i];
237 /// Subtracts the RHS APInt from this APInt
238 /// @returns this, after subtraction
239 /// @brief Subtraction assignment operator.
240 APInt& APInt::operator-=(const APInt& RHS) {
241 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
245 sub(pVal, pVal, RHS.pVal, getNumWords());
246 return clearUnusedBits();
249 /// Multiplies an integer array, x by a a uint64_t integer and places the result
251 /// @returns the carry out of the multiplication.
252 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
253 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
254 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
255 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
258 // For each digit of x.
259 for (unsigned i = 0; i < len; ++i) {
260 // Split x into high and low words
261 uint64_t lx = x[i] & 0xffffffffULL;
262 uint64_t hx = x[i] >> 32;
263 // hasCarry - A flag to indicate if there is a carry to the next digit.
264 // hasCarry == 0, no carry
265 // hasCarry == 1, has carry
266 // hasCarry == 2, no carry and the calculation result == 0.
267 uint8_t hasCarry = 0;
268 dest[i] = carry + lx * ly;
269 // Determine if the add above introduces carry.
270 hasCarry = (dest[i] < carry) ? 1 : 0;
271 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
272 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
273 // (2^32 - 1) + 2^32 = 2^64.
274 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
276 carry += (lx * hy) & 0xffffffffULL;
277 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
278 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
279 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
284 /// Multiplies integer array x by integer array y and stores the result into
285 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
286 /// @brief Generalized multiplicate of integer arrays.
287 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
289 dest[xlen] = mul_1(dest, x, xlen, y[0]);
290 for (unsigned i = 1; i < ylen; ++i) {
291 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
292 uint64_t carry = 0, lx = 0, hx = 0;
293 for (unsigned j = 0; j < xlen; ++j) {
294 lx = x[j] & 0xffffffffULL;
296 // hasCarry - A flag to indicate if has carry.
297 // hasCarry == 0, no carry
298 // hasCarry == 1, has carry
299 // hasCarry == 2, no carry and the calculation result == 0.
300 uint8_t hasCarry = 0;
301 uint64_t resul = carry + lx * ly;
302 hasCarry = (resul < carry) ? 1 : 0;
303 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
304 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
306 carry += (lx * hy) & 0xffffffffULL;
307 resul = (carry << 32) | (resul & 0xffffffffULL);
309 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
310 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
311 ((lx * hy) >> 32) + hx * hy;
313 dest[i+xlen] = carry;
317 APInt& APInt::operator*=(const APInt& RHS) {
318 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
319 if (isSingleWord()) {
325 // Get some bit facts about LHS and check for zero
326 unsigned lhsBits = getActiveBits();
327 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
332 // Get some bit facts about RHS and check for zero
333 unsigned rhsBits = RHS.getActiveBits();
334 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
341 // Allocate space for the result
342 unsigned destWords = rhsWords + lhsWords;
343 uint64_t *dest = getMemory(destWords);
345 // Perform the long multiply
346 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
348 // Copy result back into *this
350 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
351 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
353 // delete dest array and return
358 APInt& APInt::operator&=(const APInt& RHS) {
359 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
360 if (isSingleWord()) {
364 unsigned numWords = getNumWords();
365 for (unsigned i = 0; i < numWords; ++i)
366 pVal[i] &= RHS.pVal[i];
370 APInt& APInt::operator|=(const APInt& RHS) {
371 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
372 if (isSingleWord()) {
376 unsigned numWords = getNumWords();
377 for (unsigned i = 0; i < numWords; ++i)
378 pVal[i] |= RHS.pVal[i];
382 APInt& APInt::operator^=(const APInt& RHS) {
383 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
384 if (isSingleWord()) {
386 this->clearUnusedBits();
389 unsigned numWords = getNumWords();
390 for (unsigned i = 0; i < numWords; ++i)
391 pVal[i] ^= RHS.pVal[i];
392 return clearUnusedBits();
395 APInt APInt::AndSlowCase(const APInt& RHS) const {
396 unsigned numWords = getNumWords();
397 uint64_t* val = getMemory(numWords);
398 for (unsigned i = 0; i < numWords; ++i)
399 val[i] = pVal[i] & RHS.pVal[i];
400 return APInt(val, getBitWidth());
403 APInt APInt::OrSlowCase(const APInt& RHS) const {
404 unsigned numWords = getNumWords();
405 uint64_t *val = getMemory(numWords);
406 for (unsigned i = 0; i < numWords; ++i)
407 val[i] = pVal[i] | RHS.pVal[i];
408 return APInt(val, getBitWidth());
411 APInt APInt::XorSlowCase(const APInt& RHS) const {
412 unsigned numWords = getNumWords();
413 uint64_t *val = getMemory(numWords);
414 for (unsigned i = 0; i < numWords; ++i)
415 val[i] = pVal[i] ^ RHS.pVal[i];
417 // 0^0==1 so clear the high bits in case they got set.
418 return APInt(val, getBitWidth()).clearUnusedBits();
421 bool APInt::operator !() const {
425 for (unsigned i = 0; i < getNumWords(); ++i)
431 APInt APInt::operator*(const APInt& RHS) const {
432 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
434 return APInt(BitWidth, VAL * RHS.VAL);
437 return Result.clearUnusedBits();
440 APInt APInt::operator+(const APInt& RHS) const {
441 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
443 return APInt(BitWidth, VAL + RHS.VAL);
444 APInt Result(BitWidth, 0);
445 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
446 return Result.clearUnusedBits();
449 APInt APInt::operator-(const APInt& RHS) const {
450 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
452 return APInt(BitWidth, VAL - RHS.VAL);
453 APInt Result(BitWidth, 0);
454 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
455 return Result.clearUnusedBits();
458 bool APInt::operator[](unsigned bitPosition) const {
459 return (maskBit(bitPosition) &
460 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
463 bool APInt::EqualSlowCase(const APInt& RHS) const {
464 // Get some facts about the number of bits used in the two operands.
465 unsigned n1 = getActiveBits();
466 unsigned n2 = RHS.getActiveBits();
468 // If the number of bits isn't the same, they aren't equal
472 // If the number of bits fits in a word, we only need to compare the low word.
473 if (n1 <= APINT_BITS_PER_WORD)
474 return pVal[0] == RHS.pVal[0];
476 // Otherwise, compare everything
477 for (int i = whichWord(n1 - 1); i >= 0; --i)
478 if (pVal[i] != RHS.pVal[i])
483 bool APInt::EqualSlowCase(uint64_t Val) const {
484 unsigned n = getActiveBits();
485 if (n <= APINT_BITS_PER_WORD)
486 return pVal[0] == Val;
491 bool APInt::ult(const APInt& RHS) const {
492 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
494 return VAL < RHS.VAL;
496 // Get active bit length of both operands
497 unsigned n1 = getActiveBits();
498 unsigned n2 = RHS.getActiveBits();
500 // If magnitude of LHS is less than RHS, return true.
504 // If magnitude of RHS is greather than LHS, return false.
508 // If they bot fit in a word, just compare the low order word
509 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
510 return pVal[0] < RHS.pVal[0];
512 // Otherwise, compare all words
513 unsigned topWord = whichWord(std::max(n1,n2)-1);
514 for (int i = topWord; i >= 0; --i) {
515 if (pVal[i] > RHS.pVal[i])
517 if (pVal[i] < RHS.pVal[i])
523 bool APInt::slt(const APInt& RHS) const {
524 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
525 if (isSingleWord()) {
526 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
527 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
528 return lhsSext < rhsSext;
533 bool lhsNeg = isNegative();
534 bool rhsNeg = rhs.isNegative();
536 // Sign bit is set so perform two's complement to make it positive
541 // Sign bit is set so perform two's complement to make it positive
546 // Now we have unsigned values to compare so do the comparison if necessary
547 // based on the negativeness of the values.
559 APInt& APInt::set(unsigned bitPosition) {
561 VAL |= maskBit(bitPosition);
563 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
567 /// Set the given bit to 0 whose position is given as "bitPosition".
568 /// @brief Set a given bit to 0.
569 APInt& APInt::clear(unsigned bitPosition) {
571 VAL &= ~maskBit(bitPosition);
573 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
577 /// @brief Toggle every bit to its opposite value.
579 /// Toggle a given bit to its opposite value whose position is given
580 /// as "bitPosition".
581 /// @brief Toggles a given bit to its opposite value.
582 APInt& APInt::flip(unsigned bitPosition) {
583 assert(bitPosition < BitWidth && "Out of the bit-width range!");
584 if ((*this)[bitPosition]) clear(bitPosition);
585 else set(bitPosition);
589 unsigned APInt::getBitsNeeded(const char* str, unsigned slen, uint8_t radix) {
590 assert(str != 0 && "Invalid value string");
591 assert(slen > 0 && "Invalid string length");
593 // Each computation below needs to know if its negative
594 unsigned isNegative = str[0] == '-';
599 // For radixes of power-of-two values, the bits required is accurately and
602 return slen + isNegative;
604 return slen * 3 + isNegative;
606 return slen * 4 + isNegative;
608 // Otherwise it must be radix == 10, the hard case
609 assert(radix == 10 && "Invalid radix");
611 // This is grossly inefficient but accurate. We could probably do something
612 // with a computation of roughly slen*64/20 and then adjust by the value of
613 // the first few digits. But, I'm not sure how accurate that could be.
615 // Compute a sufficient number of bits that is always large enough but might
616 // be too large. This avoids the assertion in the constructor.
617 unsigned sufficient = slen*64/18;
619 // Convert to the actual binary value.
620 APInt tmp(sufficient, str, slen, radix);
622 // Compute how many bits are required.
623 return isNegative + tmp.logBase2() + 1;
626 uint64_t APInt::getHashValue() const {
627 // Put the bit width into the low order bits.
628 uint64_t hash = BitWidth;
630 // Add the sum of the words to the hash.
632 hash += VAL << 6; // clear separation of up to 64 bits
634 for (unsigned i = 0; i < getNumWords(); ++i)
635 hash += pVal[i] << 6; // clear sepration of up to 64 bits
639 /// HiBits - This function returns the high "numBits" bits of this APInt.
640 APInt APInt::getHiBits(unsigned numBits) const {
641 return APIntOps::lshr(*this, BitWidth - numBits);
644 /// LoBits - This function returns the low "numBits" bits of this APInt.
645 APInt APInt::getLoBits(unsigned numBits) const {
646 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
650 bool APInt::isPowerOf2() const {
651 return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
654 unsigned APInt::countLeadingZerosSlowCase() const {
656 for (unsigned i = getNumWords(); i > 0u; --i) {
658 Count += APINT_BITS_PER_WORD;
660 Count += CountLeadingZeros_64(pVal[i-1]);
664 unsigned remainder = BitWidth % APINT_BITS_PER_WORD;
666 Count -= APINT_BITS_PER_WORD - remainder;
667 return std::min(Count, BitWidth);
670 static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
674 while (V && (V & (1ULL << 63))) {
681 unsigned APInt::countLeadingOnes() const {
683 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
685 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
688 highWordBits = APINT_BITS_PER_WORD;
691 shift = APINT_BITS_PER_WORD - highWordBits;
693 int i = getNumWords() - 1;
694 unsigned Count = countLeadingOnes_64(pVal[i], shift);
695 if (Count == highWordBits) {
696 for (i--; i >= 0; --i) {
697 if (pVal[i] == -1ULL)
698 Count += APINT_BITS_PER_WORD;
700 Count += countLeadingOnes_64(pVal[i], 0);
708 unsigned APInt::countTrailingZeros() const {
710 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth);
713 for (; i < getNumWords() && pVal[i] == 0; ++i)
714 Count += APINT_BITS_PER_WORD;
715 if (i < getNumWords())
716 Count += CountTrailingZeros_64(pVal[i]);
717 return std::min(Count, BitWidth);
720 unsigned APInt::countTrailingOnesSlowCase() const {
723 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
724 Count += APINT_BITS_PER_WORD;
725 if (i < getNumWords())
726 Count += CountTrailingOnes_64(pVal[i]);
727 return std::min(Count, BitWidth);
730 unsigned APInt::countPopulationSlowCase() const {
732 for (unsigned i = 0; i < getNumWords(); ++i)
733 Count += CountPopulation_64(pVal[i]);
737 APInt APInt::byteSwap() const {
738 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
740 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
741 else if (BitWidth == 32)
742 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
743 else if (BitWidth == 48) {
744 unsigned Tmp1 = unsigned(VAL >> 16);
745 Tmp1 = ByteSwap_32(Tmp1);
746 uint16_t Tmp2 = uint16_t(VAL);
747 Tmp2 = ByteSwap_16(Tmp2);
748 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
749 } else if (BitWidth == 64)
750 return APInt(BitWidth, ByteSwap_64(VAL));
752 APInt Result(BitWidth, 0);
753 char *pByte = (char*)Result.pVal;
754 for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
756 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
757 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
763 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
765 APInt A = API1, B = API2;
768 B = APIntOps::urem(A, B);
774 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
781 // Get the sign bit from the highest order bit
782 bool isNeg = T.I >> 63;
784 // Get the 11-bit exponent and adjust for the 1023 bit bias
785 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
787 // If the exponent is negative, the value is < 0 so just return 0.
789 return APInt(width, 0u);
791 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
792 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
794 // If the exponent doesn't shift all bits out of the mantissa
796 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
797 APInt(width, mantissa >> (52 - exp));
799 // If the client didn't provide enough bits for us to shift the mantissa into
800 // then the result is undefined, just return 0
801 if (width <= exp - 52)
802 return APInt(width, 0);
804 // Otherwise, we have to shift the mantissa bits up to the right location
805 APInt Tmp(width, mantissa);
806 Tmp = Tmp.shl((unsigned)exp - 52);
807 return isNeg ? -Tmp : Tmp;
810 /// RoundToDouble - This function convert this APInt to a double.
811 /// The layout for double is as following (IEEE Standard 754):
812 /// --------------------------------------
813 /// | Sign Exponent Fraction Bias |
814 /// |-------------------------------------- |
815 /// | 1[63] 11[62-52] 52[51-00] 1023 |
816 /// --------------------------------------
817 double APInt::roundToDouble(bool isSigned) const {
819 // Handle the simple case where the value is contained in one uint64_t.
820 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
822 int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
828 // Determine if the value is negative.
829 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
831 // Construct the absolute value if we're negative.
832 APInt Tmp(isNeg ? -(*this) : (*this));
834 // Figure out how many bits we're using.
835 unsigned n = Tmp.getActiveBits();
837 // The exponent (without bias normalization) is just the number of bits
838 // we are using. Note that the sign bit is gone since we constructed the
842 // Return infinity for exponent overflow
844 if (!isSigned || !isNeg)
845 return std::numeric_limits<double>::infinity();
847 return -std::numeric_limits<double>::infinity();
849 exp += 1023; // Increment for 1023 bias
851 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
852 // extract the high 52 bits from the correct words in pVal.
854 unsigned hiWord = whichWord(n-1);
856 mantissa = Tmp.pVal[0];
858 mantissa >>= n - 52; // shift down, we want the top 52 bits.
860 assert(hiWord > 0 && "huh?");
861 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
862 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
863 mantissa = hibits | lobits;
866 // The leading bit of mantissa is implicit, so get rid of it.
867 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
872 T.I = sign | (exp << 52) | mantissa;
876 // Truncate to new width.
877 APInt &APInt::trunc(unsigned width) {
878 assert(width < BitWidth && "Invalid APInt Truncate request");
879 assert(width && "Can't truncate to 0 bits");
880 unsigned wordsBefore = getNumWords();
882 unsigned wordsAfter = getNumWords();
883 if (wordsBefore != wordsAfter) {
884 if (wordsAfter == 1) {
885 uint64_t *tmp = pVal;
889 uint64_t *newVal = getClearedMemory(wordsAfter);
890 for (unsigned i = 0; i < wordsAfter; ++i)
896 return clearUnusedBits();
899 // Sign extend to a new width.
900 APInt &APInt::sext(unsigned width) {
901 assert(width > BitWidth && "Invalid APInt SignExtend request");
902 // If the sign bit isn't set, this is the same as zext.
908 // The sign bit is set. First, get some facts
909 unsigned wordsBefore = getNumWords();
910 unsigned wordBits = BitWidth % APINT_BITS_PER_WORD;
912 unsigned wordsAfter = getNumWords();
914 // Mask the high order word appropriately
915 if (wordsBefore == wordsAfter) {
916 unsigned newWordBits = width % APINT_BITS_PER_WORD;
917 // The extension is contained to the wordsBefore-1th word.
918 uint64_t mask = ~0ULL;
920 mask >>= APINT_BITS_PER_WORD - newWordBits;
922 if (wordsBefore == 1)
925 pVal[wordsBefore-1] |= mask;
926 return clearUnusedBits();
929 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
930 uint64_t *newVal = getMemory(wordsAfter);
931 if (wordsBefore == 1)
932 newVal[0] = VAL | mask;
934 for (unsigned i = 0; i < wordsBefore; ++i)
936 newVal[wordsBefore-1] |= mask;
938 for (unsigned i = wordsBefore; i < wordsAfter; i++)
940 if (wordsBefore != 1)
943 return clearUnusedBits();
946 // Zero extend to a new width.
947 APInt &APInt::zext(unsigned width) {
948 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
949 unsigned wordsBefore = getNumWords();
951 unsigned wordsAfter = getNumWords();
952 if (wordsBefore != wordsAfter) {
953 uint64_t *newVal = getClearedMemory(wordsAfter);
954 if (wordsBefore == 1)
957 for (unsigned i = 0; i < wordsBefore; ++i)
959 if (wordsBefore != 1)
966 APInt &APInt::zextOrTrunc(unsigned width) {
967 if (BitWidth < width)
969 if (BitWidth > width)
974 APInt &APInt::sextOrTrunc(unsigned width) {
975 if (BitWidth < width)
977 if (BitWidth > width)
982 /// Arithmetic right-shift this APInt by shiftAmt.
983 /// @brief Arithmetic right-shift function.
984 APInt APInt::ashr(const APInt &shiftAmt) const {
985 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
988 /// Arithmetic right-shift this APInt by shiftAmt.
989 /// @brief Arithmetic right-shift function.
990 APInt APInt::ashr(unsigned shiftAmt) const {
991 assert(shiftAmt <= BitWidth && "Invalid shift amount");
992 // Handle a degenerate case
996 // Handle single word shifts with built-in ashr
997 if (isSingleWord()) {
998 if (shiftAmt == BitWidth)
999 return APInt(BitWidth, 0); // undefined
1001 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;
1002 return APInt(BitWidth,
1003 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1007 // If all the bits were shifted out, the result is, technically, undefined.
1008 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1009 // issues in the algorithm below.
1010 if (shiftAmt == BitWidth) {
1012 return APInt(BitWidth, -1ULL, true);
1014 return APInt(BitWidth, 0);
1017 // Create some space for the result.
1018 uint64_t * val = new uint64_t[getNumWords()];
1020 // Compute some values needed by the following shift algorithms
1021 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1022 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1023 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1024 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1025 if (bitsInWord == 0)
1026 bitsInWord = APINT_BITS_PER_WORD;
1028 // If we are shifting whole words, just move whole words
1029 if (wordShift == 0) {
1030 // Move the words containing significant bits
1031 for (unsigned i = 0; i <= breakWord; ++i)
1032 val[i] = pVal[i+offset]; // move whole word
1034 // Adjust the top significant word for sign bit fill, if negative
1036 if (bitsInWord < APINT_BITS_PER_WORD)
1037 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1039 // Shift the low order words
1040 for (unsigned i = 0; i < breakWord; ++i) {
1041 // This combines the shifted corresponding word with the low bits from
1042 // the next word (shifted into this word's high bits).
1043 val[i] = (pVal[i+offset] >> wordShift) |
1044 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1047 // Shift the break word. In this case there are no bits from the next word
1048 // to include in this word.
1049 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1051 // Deal with sign extenstion in the break word, and possibly the word before
1054 if (wordShift > bitsInWord) {
1057 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1058 val[breakWord] |= ~0ULL;
1060 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1064 // Remaining words are 0 or -1, just assign them.
1065 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1066 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1068 return APInt(val, BitWidth).clearUnusedBits();
1071 /// Logical right-shift this APInt by shiftAmt.
1072 /// @brief Logical right-shift function.
1073 APInt APInt::lshr(const APInt &shiftAmt) const {
1074 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
1077 /// Logical right-shift this APInt by shiftAmt.
1078 /// @brief Logical right-shift function.
1079 APInt APInt::lshr(unsigned shiftAmt) const {
1080 if (isSingleWord()) {
1081 if (shiftAmt == BitWidth)
1082 return APInt(BitWidth, 0);
1084 return APInt(BitWidth, this->VAL >> shiftAmt);
1087 // If all the bits were shifted out, the result is 0. This avoids issues
1088 // with shifting by the size of the integer type, which produces undefined
1089 // results. We define these "undefined results" to always be 0.
1090 if (shiftAmt == BitWidth)
1091 return APInt(BitWidth, 0);
1093 // If none of the bits are shifted out, the result is *this. This avoids
1094 // issues with shifting by the size of the integer type, which produces
1095 // undefined results in the code below. This is also an optimization.
1099 // Create some space for the result.
1100 uint64_t * val = new uint64_t[getNumWords()];
1102 // If we are shifting less than a word, compute the shift with a simple carry
1103 if (shiftAmt < APINT_BITS_PER_WORD) {
1105 for (int i = getNumWords()-1; i >= 0; --i) {
1106 val[i] = (pVal[i] >> shiftAmt) | carry;
1107 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1109 return APInt(val, BitWidth).clearUnusedBits();
1112 // Compute some values needed by the remaining shift algorithms
1113 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1114 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1116 // If we are shifting whole words, just move whole words
1117 if (wordShift == 0) {
1118 for (unsigned i = 0; i < getNumWords() - offset; ++i)
1119 val[i] = pVal[i+offset];
1120 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)
1122 return APInt(val,BitWidth).clearUnusedBits();
1125 // Shift the low order words
1126 unsigned breakWord = getNumWords() - offset -1;
1127 for (unsigned i = 0; i < breakWord; ++i)
1128 val[i] = (pVal[i+offset] >> wordShift) |
1129 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1130 // Shift the break word.
1131 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1133 // Remaining words are 0
1134 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1136 return APInt(val, BitWidth).clearUnusedBits();
1139 /// Left-shift this APInt by shiftAmt.
1140 /// @brief Left-shift function.
1141 APInt APInt::shl(const APInt &shiftAmt) const {
1142 // It's undefined behavior in C to shift by BitWidth or greater.
1143 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));
1146 APInt APInt::shlSlowCase(unsigned shiftAmt) const {
1147 // If all the bits were shifted out, the result is 0. This avoids issues
1148 // with shifting by the size of the integer type, which produces undefined
1149 // results. We define these "undefined results" to always be 0.
1150 if (shiftAmt == BitWidth)
1151 return APInt(BitWidth, 0);
1153 // If none of the bits are shifted out, the result is *this. This avoids a
1154 // lshr by the words size in the loop below which can produce incorrect
1155 // results. It also avoids the expensive computation below for a common case.
1159 // Create some space for the result.
1160 uint64_t * val = new uint64_t[getNumWords()];
1162 // If we are shifting less than a word, do it the easy way
1163 if (shiftAmt < APINT_BITS_PER_WORD) {
1165 for (unsigned i = 0; i < getNumWords(); i++) {
1166 val[i] = pVal[i] << shiftAmt | carry;
1167 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1169 return APInt(val, BitWidth).clearUnusedBits();
1172 // Compute some values needed by the remaining shift algorithms
1173 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;
1174 unsigned offset = shiftAmt / APINT_BITS_PER_WORD;
1176 // If we are shifting whole words, just move whole words
1177 if (wordShift == 0) {
1178 for (unsigned i = 0; i < offset; i++)
1180 for (unsigned i = offset; i < getNumWords(); i++)
1181 val[i] = pVal[i-offset];
1182 return APInt(val,BitWidth).clearUnusedBits();
1185 // Copy whole words from this to Result.
1186 unsigned i = getNumWords() - 1;
1187 for (; i > offset; --i)
1188 val[i] = pVal[i-offset] << wordShift |
1189 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1190 val[offset] = pVal[0] << wordShift;
1191 for (i = 0; i < offset; ++i)
1193 return APInt(val, BitWidth).clearUnusedBits();
1196 APInt APInt::rotl(const APInt &rotateAmt) const {
1197 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));
1200 APInt APInt::rotl(unsigned rotateAmt) const {
1203 // Don't get too fancy, just use existing shift/or facilities
1207 lo.lshr(BitWidth - rotateAmt);
1211 APInt APInt::rotr(const APInt &rotateAmt) const {
1212 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));
1215 APInt APInt::rotr(unsigned rotateAmt) const {
1218 // Don't get too fancy, just use existing shift/or facilities
1222 hi.shl(BitWidth - rotateAmt);
1226 // Square Root - this method computes and returns the square root of "this".
1227 // Three mechanisms are used for computation. For small values (<= 5 bits),
1228 // a table lookup is done. This gets some performance for common cases. For
1229 // values using less than 52 bits, the value is converted to double and then
1230 // the libc sqrt function is called. The result is rounded and then converted
1231 // back to a uint64_t which is then used to construct the result. Finally,
1232 // the Babylonian method for computing square roots is used.
1233 APInt APInt::sqrt() const {
1235 // Determine the magnitude of the value.
1236 unsigned magnitude = getActiveBits();
1238 // Use a fast table for some small values. This also gets rid of some
1239 // rounding errors in libc sqrt for small values.
1240 if (magnitude <= 5) {
1241 static const uint8_t results[32] = {
1244 /* 3- 6 */ 2, 2, 2, 2,
1245 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1246 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1247 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1250 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1253 // If the magnitude of the value fits in less than 52 bits (the precision of
1254 // an IEEE double precision floating point value), then we can use the
1255 // libc sqrt function which will probably use a hardware sqrt computation.
1256 // This should be faster than the algorithm below.
1257 if (magnitude < 52) {
1259 // Amazingly, VC++ doesn't have round().
1260 return APInt(BitWidth,
1261 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1263 return APInt(BitWidth,
1264 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1268 // Okay, all the short cuts are exhausted. We must compute it. The following
1269 // is a classical Babylonian method for computing the square root. This code
1270 // was adapted to APINt from a wikipedia article on such computations.
1271 // See http://www.wikipedia.org/ and go to the page named
1272 // Calculate_an_integer_square_root.
1273 unsigned nbits = BitWidth, i = 4;
1274 APInt testy(BitWidth, 16);
1275 APInt x_old(BitWidth, 1);
1276 APInt x_new(BitWidth, 0);
1277 APInt two(BitWidth, 2);
1279 // Select a good starting value using binary logarithms.
1280 for (;; i += 2, testy = testy.shl(2))
1281 if (i >= nbits || this->ule(testy)) {
1282 x_old = x_old.shl(i / 2);
1286 // Use the Babylonian method to arrive at the integer square root:
1288 x_new = (this->udiv(x_old) + x_old).udiv(two);
1289 if (x_old.ule(x_new))
1294 // Make sure we return the closest approximation
1295 // NOTE: The rounding calculation below is correct. It will produce an
1296 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1297 // determined to be a rounding issue with pari/gp as it begins to use a
1298 // floating point representation after 192 bits. There are no discrepancies
1299 // between this algorithm and pari/gp for bit widths < 192 bits.
1300 APInt square(x_old * x_old);
1301 APInt nextSquare((x_old + 1) * (x_old +1));
1302 if (this->ult(square))
1304 else if (this->ule(nextSquare)) {
1305 APInt midpoint((nextSquare - square).udiv(two));
1306 APInt offset(*this - square);
1307 if (offset.ult(midpoint))
1312 assert(0 && "Error in APInt::sqrt computation");
1316 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1317 /// iterative extended Euclidean algorithm is used to solve for this value,
1318 /// however we simplify it to speed up calculating only the inverse, and take
1319 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1320 /// (potentially large) APInts around.
1321 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1322 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1324 // Using the properties listed at the following web page (accessed 06/21/08):
1325 // http://www.numbertheory.org/php/euclid.html
1326 // (especially the properties numbered 3, 4 and 9) it can be proved that
1327 // BitWidth bits suffice for all the computations in the algorithm implemented
1328 // below. More precisely, this number of bits suffice if the multiplicative
1329 // inverse exists, but may not suffice for the general extended Euclidean
1332 APInt r[2] = { modulo, *this };
1333 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1334 APInt q(BitWidth, 0);
1337 for (i = 0; r[i^1] != 0; i ^= 1) {
1338 // An overview of the math without the confusing bit-flipping:
1339 // q = r[i-2] / r[i-1]
1340 // r[i] = r[i-2] % r[i-1]
1341 // t[i] = t[i-2] - t[i-1] * q
1342 udivrem(r[i], r[i^1], q, r[i]);
1346 // If this APInt and the modulo are not coprime, there is no multiplicative
1347 // inverse, so return 0. We check this by looking at the next-to-last
1348 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1351 return APInt(BitWidth, 0);
1353 // The next-to-last t is the multiplicative inverse. However, we are
1354 // interested in a positive inverse. Calcuate a positive one from a negative
1355 // one if necessary. A simple addition of the modulo suffices because
1356 // abs(t[i]) is known to be less than *this/2 (see the link above).
1357 return t[i].isNegative() ? t[i] + modulo : t[i];
1360 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1361 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1362 /// variables here have the same names as in the algorithm. Comments explain
1363 /// the algorithm and any deviation from it.
1364 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1365 unsigned m, unsigned n) {
1366 assert(u && "Must provide dividend");
1367 assert(v && "Must provide divisor");
1368 assert(q && "Must provide quotient");
1369 assert(u != v && u != q && v != q && "Must us different memory");
1370 assert(n>1 && "n must be > 1");
1372 // Knuth uses the value b as the base of the number system. In our case b
1373 // is 2^31 so we just set it to -1u.
1374 uint64_t b = uint64_t(1) << 32;
1377 DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n');
1378 DEBUG(cerr << "KnuthDiv: original:");
1379 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1380 DEBUG(cerr << " by");
1381 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1382 DEBUG(cerr << '\n');
1384 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1385 // u and v by d. Note that we have taken Knuth's advice here to use a power
1386 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1387 // 2 allows us to shift instead of multiply and it is easy to determine the
1388 // shift amount from the leading zeros. We are basically normalizing the u
1389 // and v so that its high bits are shifted to the top of v's range without
1390 // overflow. Note that this can require an extra word in u so that u must
1391 // be of length m+n+1.
1392 unsigned shift = CountLeadingZeros_32(v[n-1]);
1393 unsigned v_carry = 0;
1394 unsigned u_carry = 0;
1396 for (unsigned i = 0; i < m+n; ++i) {
1397 unsigned u_tmp = u[i] >> (32 - shift);
1398 u[i] = (u[i] << shift) | u_carry;
1401 for (unsigned i = 0; i < n; ++i) {
1402 unsigned v_tmp = v[i] >> (32 - shift);
1403 v[i] = (v[i] << shift) | v_carry;
1409 DEBUG(cerr << "KnuthDiv: normal:");
1410 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1411 DEBUG(cerr << " by");
1412 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1413 DEBUG(cerr << '\n');
1416 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1419 DEBUG(cerr << "KnuthDiv: quotient digit #" << j << '\n');
1420 // D3. [Calculate q'.].
1421 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1422 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1423 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1424 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1425 // on v[n-2] determines at high speed most of the cases in which the trial
1426 // value qp is one too large, and it eliminates all cases where qp is two
1428 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1429 DEBUG(cerr << "KnuthDiv: dividend == " << dividend << '\n');
1430 uint64_t qp = dividend / v[n-1];
1431 uint64_t rp = dividend % v[n-1];
1432 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1435 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1438 DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1440 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1441 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1442 // consists of a simple multiplication by a one-place number, combined with
1445 for (unsigned i = 0; i < n; ++i) {
1446 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1447 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1448 bool borrow = subtrahend > u_tmp;
1449 DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp
1450 << ", subtrahend == " << subtrahend
1451 << ", borrow = " << borrow << '\n');
1453 uint64_t result = u_tmp - subtrahend;
1455 u[k++] = (unsigned)(result & (b-1)); // subtract low word
1456 u[k++] = (unsigned)(result >> 32); // subtract high word
1457 while (borrow && k <= m+n) { // deal with borrow to the left
1463 DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1466 DEBUG(cerr << "KnuthDiv: after subtraction:");
1467 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1468 DEBUG(cerr << '\n');
1469 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1470 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1471 // true value plus b**(n+1), namely as the b's complement of
1472 // the true value, and a "borrow" to the left should be remembered.
1475 bool carry = true; // true because b's complement is "complement + 1"
1476 for (unsigned i = 0; i <= m+n; ++i) {
1477 u[i] = ~u[i] + carry; // b's complement
1478 carry = carry && u[i] == 0;
1481 DEBUG(cerr << "KnuthDiv: after complement:");
1482 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1483 DEBUG(cerr << '\n');
1485 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1486 // negative, go to step D6; otherwise go on to step D7.
1487 q[j] = (unsigned)qp;
1489 // D6. [Add back]. The probability that this step is necessary is very
1490 // small, on the order of only 2/b. Make sure that test data accounts for
1491 // this possibility. Decrease q[j] by 1
1493 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1494 // A carry will occur to the left of u[j+n], and it should be ignored
1495 // since it cancels with the borrow that occurred in D4.
1497 for (unsigned i = 0; i < n; i++) {
1498 unsigned limit = std::min(u[j+i],v[i]);
1499 u[j+i] += v[i] + carry;
1500 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1504 DEBUG(cerr << "KnuthDiv: after correction:");
1505 DEBUG(for (int i = m+n; i >=0; i--) cerr <<" " << u[i]);
1506 DEBUG(cerr << "\nKnuthDiv: digit result = " << q[j] << '\n');
1508 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1511 DEBUG(cerr << "KnuthDiv: quotient:");
1512 DEBUG(for (int i = m; i >=0; i--) cerr <<" " << q[i]);
1513 DEBUG(cerr << '\n');
1515 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1516 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1517 // compute the remainder (urem uses this).
1519 // The value d is expressed by the "shift" value above since we avoided
1520 // multiplication by d by using a shift left. So, all we have to do is
1521 // shift right here. In order to mak
1524 DEBUG(cerr << "KnuthDiv: remainder:");
1525 for (int i = n-1; i >= 0; i--) {
1526 r[i] = (u[i] >> shift) | carry;
1527 carry = u[i] << (32 - shift);
1528 DEBUG(cerr << " " << r[i]);
1531 for (int i = n-1; i >= 0; i--) {
1533 DEBUG(cerr << " " << r[i]);
1536 DEBUG(cerr << '\n');
1539 DEBUG(cerr << std::setbase(10) << '\n');
1543 void APInt::divide(const APInt LHS, unsigned lhsWords,
1544 const APInt &RHS, unsigned rhsWords,
1545 APInt *Quotient, APInt *Remainder)
1547 assert(lhsWords >= rhsWords && "Fractional result");
1549 // First, compose the values into an array of 32-bit words instead of
1550 // 64-bit words. This is a necessity of both the "short division" algorithm
1551 // and the the Knuth "classical algorithm" which requires there to be native
1552 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1553 // can't use 64-bit operands here because we don't have native results of
1554 // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't
1555 // work on large-endian machines.
1556 uint64_t mask = ~0ull >> (sizeof(unsigned)*8);
1557 unsigned n = rhsWords * 2;
1558 unsigned m = (lhsWords * 2) - n;
1560 // Allocate space for the temporary values we need either on the stack, if
1561 // it will fit, or on the heap if it won't.
1562 unsigned SPACE[128];
1567 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1570 Q = &SPACE[(m+n+1) + n];
1572 R = &SPACE[(m+n+1) + n + (m+n)];
1574 U = new unsigned[m + n + 1];
1575 V = new unsigned[n];
1576 Q = new unsigned[m+n];
1578 R = new unsigned[n];
1581 // Initialize the dividend
1582 memset(U, 0, (m+n+1)*sizeof(unsigned));
1583 for (unsigned i = 0; i < lhsWords; ++i) {
1584 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1585 U[i * 2] = (unsigned)(tmp & mask);
1586 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*8));
1588 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1590 // Initialize the divisor
1591 memset(V, 0, (n)*sizeof(unsigned));
1592 for (unsigned i = 0; i < rhsWords; ++i) {
1593 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1594 V[i * 2] = (unsigned)(tmp & mask);
1595 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*8));
1598 // initialize the quotient and remainder
1599 memset(Q, 0, (m+n) * sizeof(unsigned));
1601 memset(R, 0, n * sizeof(unsigned));
1603 // Now, adjust m and n for the Knuth division. n is the number of words in
1604 // the divisor. m is the number of words by which the dividend exceeds the
1605 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1606 // contain any zero words or the Knuth algorithm fails.
1607 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1611 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1614 // If we're left with only a single word for the divisor, Knuth doesn't work
1615 // so we implement the short division algorithm here. This is much simpler
1616 // and faster because we are certain that we can divide a 64-bit quantity
1617 // by a 32-bit quantity at hardware speed and short division is simply a
1618 // series of such operations. This is just like doing short division but we
1619 // are using base 2^32 instead of base 10.
1620 assert(n != 0 && "Divide by zero?");
1622 unsigned divisor = V[0];
1623 unsigned remainder = 0;
1624 for (int i = m+n-1; i >= 0; i--) {
1625 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1626 if (partial_dividend == 0) {
1629 } else if (partial_dividend < divisor) {
1631 remainder = (unsigned)partial_dividend;
1632 } else if (partial_dividend == divisor) {
1636 Q[i] = (unsigned)(partial_dividend / divisor);
1637 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
1643 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1645 KnuthDiv(U, V, Q, R, m, n);
1648 // If the caller wants the quotient
1650 // Set up the Quotient value's memory.
1651 if (Quotient->BitWidth != LHS.BitWidth) {
1652 if (Quotient->isSingleWord())
1655 delete [] Quotient->pVal;
1656 Quotient->BitWidth = LHS.BitWidth;
1657 if (!Quotient->isSingleWord())
1658 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1662 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1664 if (lhsWords == 1) {
1666 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1667 if (Quotient->isSingleWord())
1668 Quotient->VAL = tmp;
1670 Quotient->pVal[0] = tmp;
1672 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1673 for (unsigned i = 0; i < lhsWords; ++i)
1675 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1679 // If the caller wants the remainder
1681 // Set up the Remainder value's memory.
1682 if (Remainder->BitWidth != RHS.BitWidth) {
1683 if (Remainder->isSingleWord())
1686 delete [] Remainder->pVal;
1687 Remainder->BitWidth = RHS.BitWidth;
1688 if (!Remainder->isSingleWord())
1689 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1693 // The remainder is in R. Reconstitute the remainder into Remainder's low
1695 if (rhsWords == 1) {
1697 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1698 if (Remainder->isSingleWord())
1699 Remainder->VAL = tmp;
1701 Remainder->pVal[0] = tmp;
1703 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1704 for (unsigned i = 0; i < rhsWords; ++i)
1705 Remainder->pVal[i] =
1706 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1710 // Clean up the memory we allocated.
1711 if (U != &SPACE[0]) {
1719 APInt APInt::udiv(const APInt& RHS) const {
1720 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1722 // First, deal with the easy case
1723 if (isSingleWord()) {
1724 assert(RHS.VAL != 0 && "Divide by zero?");
1725 return APInt(BitWidth, VAL / RHS.VAL);
1728 // Get some facts about the LHS and RHS number of bits and words
1729 unsigned rhsBits = RHS.getActiveBits();
1730 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1731 assert(rhsWords && "Divided by zero???");
1732 unsigned lhsBits = this->getActiveBits();
1733 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1735 // Deal with some degenerate cases
1738 return APInt(BitWidth, 0);
1739 else if (lhsWords < rhsWords || this->ult(RHS)) {
1740 // X / Y ===> 0, iff X < Y
1741 return APInt(BitWidth, 0);
1742 } else if (*this == RHS) {
1744 return APInt(BitWidth, 1);
1745 } else if (lhsWords == 1 && rhsWords == 1) {
1746 // All high words are zero, just use native divide
1747 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1750 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1751 APInt Quotient(1,0); // to hold result.
1752 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1756 APInt APInt::urem(const APInt& RHS) const {
1757 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1758 if (isSingleWord()) {
1759 assert(RHS.VAL != 0 && "Remainder by zero?");
1760 return APInt(BitWidth, VAL % RHS.VAL);
1763 // Get some facts about the LHS
1764 unsigned lhsBits = getActiveBits();
1765 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1767 // Get some facts about the RHS
1768 unsigned rhsBits = RHS.getActiveBits();
1769 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1770 assert(rhsWords && "Performing remainder operation by zero ???");
1772 // Check the degenerate cases
1773 if (lhsWords == 0) {
1775 return APInt(BitWidth, 0);
1776 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1777 // X % Y ===> X, iff X < Y
1779 } else if (*this == RHS) {
1781 return APInt(BitWidth, 0);
1782 } else if (lhsWords == 1) {
1783 // All high words are zero, just use native remainder
1784 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1787 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1788 APInt Remainder(1,0);
1789 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1793 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1794 APInt &Quotient, APInt &Remainder) {
1795 // Get some size facts about the dividend and divisor
1796 unsigned lhsBits = LHS.getActiveBits();
1797 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1798 unsigned rhsBits = RHS.getActiveBits();
1799 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1801 // Check the degenerate cases
1802 if (lhsWords == 0) {
1803 Quotient = 0; // 0 / Y ===> 0
1804 Remainder = 0; // 0 % Y ===> 0
1808 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1809 Quotient = 0; // X / Y ===> 0, iff X < Y
1810 Remainder = LHS; // X % Y ===> X, iff X < Y
1815 Quotient = 1; // X / X ===> 1
1816 Remainder = 0; // X % X ===> 0;
1820 if (lhsWords == 1 && rhsWords == 1) {
1821 // There is only one word to consider so use the native versions.
1822 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1823 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1824 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1825 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
1829 // Okay, lets do it the long way
1830 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1833 void APInt::fromString(unsigned numbits, const char *str, unsigned slen,
1835 // Check our assumptions here
1836 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1837 "Radix should be 2, 8, 10, or 16!");
1838 assert(str && "String is null?");
1839 bool isNeg = str[0] == '-';
1842 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
1843 assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width");
1844 assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width");
1845 assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width");
1848 if (!isSingleWord())
1849 pVal = getClearedMemory(getNumWords());
1851 // Figure out if we can shift instead of multiply
1852 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1854 // Set up an APInt for the digit to add outside the loop so we don't
1855 // constantly construct/destruct it.
1856 APInt apdigit(getBitWidth(), 0);
1857 APInt apradix(getBitWidth(), radix);
1859 // Enter digit traversal loop
1860 for (unsigned i = 0; i < slen; i++) {
1863 char cdigit = str[i];
1865 if (!isxdigit(cdigit))
1866 assert(0 && "Invalid hex digit in string");
1867 if (isdigit(cdigit))
1868 digit = cdigit - '0';
1869 else if (cdigit >= 'a')
1870 digit = cdigit - 'a' + 10;
1871 else if (cdigit >= 'A')
1872 digit = cdigit - 'A' + 10;
1874 assert(0 && "huh? we shouldn't get here");
1875 } else if (isdigit(cdigit)) {
1876 digit = cdigit - '0';
1877 assert((radix == 10 ||
1878 (radix == 8 && digit != 8 && digit != 9) ||
1879 (radix == 2 && (digit == 0 || digit == 1))) &&
1880 "Invalid digit in string for given radix");
1882 assert(0 && "Invalid character in digit string");
1885 // Shift or multiply the value by the radix
1891 // Add in the digit we just interpreted
1892 if (apdigit.isSingleWord())
1893 apdigit.VAL = digit;
1895 apdigit.pVal[0] = digit;
1898 // If its negative, put it in two's complement form
1905 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
1906 bool Signed) const {
1907 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) &&
1908 "Radix should be 2, 8, 10, or 16!");
1910 // First, check for a zero value and just short circuit the logic below.
1916 static const char Digits[] = "0123456789ABCDEF";
1918 if (isSingleWord()) {
1920 char *BufPtr = Buffer+65;
1924 int64_t I = getSExtValue();
1935 *--BufPtr = Digits[N % Radix];
1938 Str.append(BufPtr, Buffer+65);
1944 if (Signed && isNegative()) {
1945 // They want to print the signed version and it is a negative value
1946 // Flip the bits and add one to turn it into the equivalent positive
1947 // value and put a '-' in the result.
1953 // We insert the digits backward, then reverse them to get the right order.
1954 unsigned StartDig = Str.size();
1956 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
1957 // because the number of bits per digit (1, 3 and 4 respectively) divides
1958 // equaly. We just shift until the value is zero.
1960 // Just shift tmp right for each digit width until it becomes zero
1961 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
1962 unsigned MaskAmt = Radix - 1;
1965 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
1966 Str.push_back(Digits[Digit]);
1967 Tmp = Tmp.lshr(ShiftAmt);
1970 APInt divisor(4, 10);
1972 APInt APdigit(1, 0);
1973 APInt tmp2(Tmp.getBitWidth(), 0);
1974 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
1976 unsigned Digit = (unsigned)APdigit.getZExtValue();
1977 assert(Digit < Radix && "divide failed");
1978 Str.push_back(Digits[Digit]);
1983 // Reverse the digits before returning.
1984 std::reverse(Str.begin()+StartDig, Str.end());
1987 /// toString - This returns the APInt as a std::string. Note that this is an
1988 /// inefficient method. It is better to pass in a SmallVector/SmallString
1989 /// to the methods above.
1990 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
1992 toString(S, Radix, Signed);
1997 void APInt::dump() const {
1998 SmallString<40> S, U;
1999 this->toStringUnsigned(U);
2000 this->toStringSigned(S);
2001 fprintf(stderr, "APInt(%db, %su %ss)", BitWidth, U.c_str(), S.c_str());
2004 void APInt::print(raw_ostream &OS, bool isSigned) const {
2006 this->toString(S, 10, isSigned);
2010 // This implements a variety of operations on a representation of
2011 // arbitrary precision, two's-complement, bignum integer values.
2013 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2014 and unrestricting assumption. */
2015 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2016 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2018 /* Some handy functions local to this file. */
2021 /* Returns the integer part with the least significant BITS set.
2022 BITS cannot be zero. */
2023 static inline integerPart
2024 lowBitMask(unsigned int bits)
2026 assert (bits != 0 && bits <= integerPartWidth);
2028 return ~(integerPart) 0 >> (integerPartWidth - bits);
2031 /* Returns the value of the lower half of PART. */
2032 static inline integerPart
2033 lowHalf(integerPart part)
2035 return part & lowBitMask(integerPartWidth / 2);
2038 /* Returns the value of the upper half of PART. */
2039 static inline integerPart
2040 highHalf(integerPart part)
2042 return part >> (integerPartWidth / 2);
2045 /* Returns the bit number of the most significant set bit of a part.
2046 If the input number has no bits set -1U is returned. */
2048 partMSB(integerPart value)
2050 unsigned int n, msb;
2055 n = integerPartWidth / 2;
2070 /* Returns the bit number of the least significant set bit of a
2071 part. If the input number has no bits set -1U is returned. */
2073 partLSB(integerPart value)
2075 unsigned int n, lsb;
2080 lsb = integerPartWidth - 1;
2081 n = integerPartWidth / 2;
2096 /* Sets the least significant part of a bignum to the input value, and
2097 zeroes out higher parts. */
2099 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2106 for(i = 1; i < parts; i++)
2110 /* Assign one bignum to another. */
2112 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2116 for(i = 0; i < parts; i++)
2120 /* Returns true if a bignum is zero, false otherwise. */
2122 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2126 for(i = 0; i < parts; i++)
2133 /* Extract the given bit of a bignum; returns 0 or 1. */
2135 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2137 return(parts[bit / integerPartWidth]
2138 & ((integerPart) 1 << bit % integerPartWidth)) != 0;
2141 /* Set the given bit of a bignum. */
2143 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2145 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2148 /* Returns the bit number of the least significant set bit of a
2149 number. If the input number has no bits set -1U is returned. */
2151 APInt::tcLSB(const integerPart *parts, unsigned int n)
2153 unsigned int i, lsb;
2155 for(i = 0; i < n; i++) {
2156 if (parts[i] != 0) {
2157 lsb = partLSB(parts[i]);
2159 return lsb + i * integerPartWidth;
2166 /* Returns the bit number of the most significant set bit of a number.
2167 If the input number has no bits set -1U is returned. */
2169 APInt::tcMSB(const integerPart *parts, unsigned int n)
2176 if (parts[n] != 0) {
2177 msb = partMSB(parts[n]);
2179 return msb + n * integerPartWidth;
2186 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2187 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2188 the least significant bit of DST. All high bits above srcBITS in
2189 DST are zero-filled. */
2191 APInt::tcExtract(integerPart *dst, unsigned int dstCount, const integerPart *src,
2192 unsigned int srcBits, unsigned int srcLSB)
2194 unsigned int firstSrcPart, dstParts, shift, n;
2196 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2197 assert (dstParts <= dstCount);
2199 firstSrcPart = srcLSB / integerPartWidth;
2200 tcAssign (dst, src + firstSrcPart, dstParts);
2202 shift = srcLSB % integerPartWidth;
2203 tcShiftRight (dst, dstParts, shift);
2205 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2206 in DST. If this is less that srcBits, append the rest, else
2207 clear the high bits. */
2208 n = dstParts * integerPartWidth - shift;
2210 integerPart mask = lowBitMask (srcBits - n);
2211 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2212 << n % integerPartWidth);
2213 } else if (n > srcBits) {
2214 if (srcBits % integerPartWidth)
2215 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2218 /* Clear high parts. */
2219 while (dstParts < dstCount)
2220 dst[dstParts++] = 0;
2223 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2225 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2226 integerPart c, unsigned int parts)
2232 for(i = 0; i < parts; i++) {
2237 dst[i] += rhs[i] + 1;
2248 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2250 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2251 integerPart c, unsigned int parts)
2257 for(i = 0; i < parts; i++) {
2262 dst[i] -= rhs[i] + 1;
2273 /* Negate a bignum in-place. */
2275 APInt::tcNegate(integerPart *dst, unsigned int parts)
2277 tcComplement(dst, parts);
2278 tcIncrement(dst, parts);
2281 /* DST += SRC * MULTIPLIER + CARRY if add is true
2282 DST = SRC * MULTIPLIER + CARRY if add is false
2284 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2285 they must start at the same point, i.e. DST == SRC.
2287 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2288 returned. Otherwise DST is filled with the least significant
2289 DSTPARTS parts of the result, and if all of the omitted higher
2290 parts were zero return zero, otherwise overflow occurred and
2293 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2294 integerPart multiplier, integerPart carry,
2295 unsigned int srcParts, unsigned int dstParts,
2300 /* Otherwise our writes of DST kill our later reads of SRC. */
2301 assert(dst <= src || dst >= src + srcParts);
2302 assert(dstParts <= srcParts + 1);
2304 /* N loops; minimum of dstParts and srcParts. */
2305 n = dstParts < srcParts ? dstParts: srcParts;
2307 for(i = 0; i < n; i++) {
2308 integerPart low, mid, high, srcPart;
2310 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2312 This cannot overflow, because
2314 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2316 which is less than n^2. */
2320 if (multiplier == 0 || srcPart == 0) {
2324 low = lowHalf(srcPart) * lowHalf(multiplier);
2325 high = highHalf(srcPart) * highHalf(multiplier);
2327 mid = lowHalf(srcPart) * highHalf(multiplier);
2328 high += highHalf(mid);
2329 mid <<= integerPartWidth / 2;
2330 if (low + mid < low)
2334 mid = highHalf(srcPart) * lowHalf(multiplier);
2335 high += highHalf(mid);
2336 mid <<= integerPartWidth / 2;
2337 if (low + mid < low)
2341 /* Now add carry. */
2342 if (low + carry < low)
2348 /* And now DST[i], and store the new low part there. */
2349 if (low + dst[i] < low)
2359 /* Full multiplication, there is no overflow. */
2360 assert(i + 1 == dstParts);
2364 /* We overflowed if there is carry. */
2368 /* We would overflow if any significant unwritten parts would be
2369 non-zero. This is true if any remaining src parts are non-zero
2370 and the multiplier is non-zero. */
2372 for(; i < srcParts; i++)
2376 /* We fitted in the narrow destination. */
2381 /* DST = LHS * RHS, where DST has the same width as the operands and
2382 is filled with the least significant parts of the result. Returns
2383 one if overflow occurred, otherwise zero. DST must be disjoint
2384 from both operands. */
2386 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2387 const integerPart *rhs, unsigned int parts)
2392 assert(dst != lhs && dst != rhs);
2395 tcSet(dst, 0, parts);
2397 for(i = 0; i < parts; i++)
2398 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2404 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2405 operands. No overflow occurs. DST must be disjoint from both
2406 operands. Returns the number of parts required to hold the
2409 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2410 const integerPart *rhs, unsigned int lhsParts,
2411 unsigned int rhsParts)
2413 /* Put the narrower number on the LHS for less loops below. */
2414 if (lhsParts > rhsParts) {
2415 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2419 assert(dst != lhs && dst != rhs);
2421 tcSet(dst, 0, rhsParts);
2423 for(n = 0; n < lhsParts; n++)
2424 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2426 n = lhsParts + rhsParts;
2428 return n - (dst[n - 1] == 0);
2432 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2433 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2434 set REMAINDER to the remainder, return zero. i.e.
2436 OLD_LHS = RHS * LHS + REMAINDER
2438 SCRATCH is a bignum of the same size as the operands and result for
2439 use by the routine; its contents need not be initialized and are
2440 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2443 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2444 integerPart *remainder, integerPart *srhs,
2447 unsigned int n, shiftCount;
2450 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2452 shiftCount = tcMSB(rhs, parts) + 1;
2453 if (shiftCount == 0)
2456 shiftCount = parts * integerPartWidth - shiftCount;
2457 n = shiftCount / integerPartWidth;
2458 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2460 tcAssign(srhs, rhs, parts);
2461 tcShiftLeft(srhs, parts, shiftCount);
2462 tcAssign(remainder, lhs, parts);
2463 tcSet(lhs, 0, parts);
2465 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2470 compare = tcCompare(remainder, srhs, parts);
2472 tcSubtract(remainder, srhs, 0, parts);
2476 if (shiftCount == 0)
2479 tcShiftRight(srhs, parts, 1);
2480 if ((mask >>= 1) == 0)
2481 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2487 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2488 There are no restrictions on COUNT. */
2490 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2493 unsigned int jump, shift;
2495 /* Jump is the inter-part jump; shift is is intra-part shift. */
2496 jump = count / integerPartWidth;
2497 shift = count % integerPartWidth;
2499 while (parts > jump) {
2504 /* dst[i] comes from the two parts src[i - jump] and, if we have
2505 an intra-part shift, src[i - jump - 1]. */
2506 part = dst[parts - jump];
2509 if (parts >= jump + 1)
2510 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2521 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2522 zero. There are no restrictions on COUNT. */
2524 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2527 unsigned int i, jump, shift;
2529 /* Jump is the inter-part jump; shift is is intra-part shift. */
2530 jump = count / integerPartWidth;
2531 shift = count % integerPartWidth;
2533 /* Perform the shift. This leaves the most significant COUNT bits
2534 of the result at zero. */
2535 for(i = 0; i < parts; i++) {
2538 if (i + jump >= parts) {
2541 part = dst[i + jump];
2544 if (i + jump + 1 < parts)
2545 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2554 /* Bitwise and of two bignums. */
2556 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2560 for(i = 0; i < parts; i++)
2564 /* Bitwise inclusive or of two bignums. */
2566 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2570 for(i = 0; i < parts; i++)
2574 /* Bitwise exclusive or of two bignums. */
2576 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2580 for(i = 0; i < parts; i++)
2584 /* Complement a bignum in-place. */
2586 APInt::tcComplement(integerPart *dst, unsigned int parts)
2590 for(i = 0; i < parts; i++)
2594 /* Comparison (unsigned) of two bignums. */
2596 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2601 if (lhs[parts] == rhs[parts])
2604 if (lhs[parts] > rhs[parts])
2613 /* Increment a bignum in-place, return the carry flag. */
2615 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2619 for(i = 0; i < parts; i++)
2626 /* Set the least significant BITS bits of a bignum, clear the
2629 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2635 while (bits > integerPartWidth) {
2636 dst[i++] = ~(integerPart) 0;
2637 bits -= integerPartWidth;
2641 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);