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"
27 /// A utility function for allocating memory, checking for allocation failures,
28 /// and ensuring the contents are zeroed.
29 inline static uint64_t* getClearedMemory(uint32_t numWords) {
30 uint64_t * result = new uint64_t[numWords];
31 assert(result && "APInt memory allocation fails!");
32 memset(result, 0, numWords * sizeof(uint64_t));
36 /// A utility function for allocating memory and checking for allocation
37 /// failure. The content is not zeroed.
38 inline static uint64_t* getMemory(uint32_t numWords) {
39 uint64_t * result = new uint64_t[numWords];
40 assert(result && "APInt memory allocation fails!");
44 void APInt::initSlowCase(uint32_t 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 APInt::APInt(uint32_t numBits, uint32_t numWords, const uint64_t bigVal[])
54 : BitWidth(numBits), VAL(0) {
55 assert(BitWidth && "bitwidth too small");
56 assert(bigVal && "Null pointer detected!");
60 // Get memory, cleared to 0
61 pVal = getClearedMemory(getNumWords());
62 // Calculate the number of words to copy
63 uint32_t words = std::min<uint32_t>(numWords, getNumWords());
64 // Copy the words from bigVal to pVal
65 memcpy(pVal, bigVal, words * APINT_WORD_SIZE);
67 // Make sure unused high bits are cleared
71 APInt::APInt(uint32_t numbits, const char StrStart[], uint32_t slen,
73 : BitWidth(numbits), VAL(0) {
74 assert(BitWidth && "bitwidth too small");
75 fromString(numbits, StrStart, slen, radix);
78 void APInt::initSlowCase(const APInt& that)
80 pVal = getMemory(getNumWords());
81 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
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 uint32_t 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[], uint32_t len, uint64_t y) {
145 for (uint32_t 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[], uint32_t len, uint64_t y) {
173 for (uint32_t 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 (uint32_t 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 (uint32_t 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[], uint32_t 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 (uint32_t 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[], uint32_t xlen, uint64_t y[],
289 dest[xlen] = mul_1(dest, x, xlen, y[0]);
290 for (uint32_t 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 (uint32_t 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 uint32_t lhsBits = getActiveBits();
327 uint32_t lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
332 // Get some bit facts about RHS and check for zero
333 uint32_t rhsBits = RHS.getActiveBits();
334 uint32_t rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
341 // Allocate space for the result
342 uint32_t 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 uint32_t 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 uint32_t numWords = getNumWords();
365 for (uint32_t 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 uint32_t numWords = getNumWords();
377 for (uint32_t 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 uint32_t numWords = getNumWords();
390 for (uint32_t i = 0; i < numWords; ++i)
391 pVal[i] ^= RHS.pVal[i];
392 return clearUnusedBits();
395 APInt APInt::AndSlowCase(const APInt& RHS) const {
396 uint32_t numWords = getNumWords();
397 uint64_t* val = getMemory(numWords);
398 for (uint32_t 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 uint32_t numWords = getNumWords();
405 uint64_t *val = getMemory(numWords);
406 for (uint32_t 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 uint32_t numWords = getNumWords();
413 uint64_t *val = getMemory(numWords);
414 for (uint32_t 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 (uint32_t 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[](uint32_t 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 uint32_t n1 = getActiveBits();
466 uint32_t 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 uint32_t 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 uint32_t n1 = getActiveBits();
498 uint32_t 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 uint32_t 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(uint32_t 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(uint32_t 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(uint32_t bitPosition) {
583 assert(bitPosition < BitWidth && "Out of the bit-width range!");
584 if ((*this)[bitPosition]) clear(bitPosition);
585 else set(bitPosition);
589 uint32_t APInt::getBitsNeeded(const char* str, uint32_t 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 uint32_t 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 uint32_t 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 (uint32_t 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(uint32_t 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(uint32_t 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 uint32_t APInt::countLeadingZerosSlowCase() const {
656 for (uint32_t i = getNumWords(); i > 0u; --i) {
658 Count += APINT_BITS_PER_WORD;
660 Count += CountLeadingZeros_64(pVal[i-1]);
664 uint32_t remainder = BitWidth % APINT_BITS_PER_WORD;
666 Count -= APINT_BITS_PER_WORD - remainder;
667 return std::min(Count, BitWidth);
670 static uint32_t countLeadingOnes_64(uint64_t V, uint32_t skip) {
674 while (V && (V & (1ULL << 63))) {
681 uint32_t APInt::countLeadingOnes() const {
683 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
685 uint32_t highWordBits = BitWidth % APINT_BITS_PER_WORD;
686 uint32_t shift = (highWordBits == 0 ? 0 : APINT_BITS_PER_WORD - highWordBits);
687 int i = getNumWords() - 1;
688 uint32_t Count = countLeadingOnes_64(pVal[i], shift);
689 if (Count == highWordBits) {
690 for (i--; i >= 0; --i) {
691 if (pVal[i] == -1ULL)
692 Count += APINT_BITS_PER_WORD;
694 Count += countLeadingOnes_64(pVal[i], 0);
702 uint32_t APInt::countTrailingZeros() const {
704 return std::min(uint32_t(CountTrailingZeros_64(VAL)), BitWidth);
707 for (; i < getNumWords() && pVal[i] == 0; ++i)
708 Count += APINT_BITS_PER_WORD;
709 if (i < getNumWords())
710 Count += CountTrailingZeros_64(pVal[i]);
711 return std::min(Count, BitWidth);
714 uint32_t APInt::countTrailingOnesSlowCase() const {
717 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
718 Count += APINT_BITS_PER_WORD;
719 if (i < getNumWords())
720 Count += CountTrailingOnes_64(pVal[i]);
721 return std::min(Count, BitWidth);
724 uint32_t APInt::countPopulationSlowCase() const {
726 for (uint32_t i = 0; i < getNumWords(); ++i)
727 Count += CountPopulation_64(pVal[i]);
731 APInt APInt::byteSwap() const {
732 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
734 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
735 else if (BitWidth == 32)
736 return APInt(BitWidth, ByteSwap_32(uint32_t(VAL)));
737 else if (BitWidth == 48) {
738 uint32_t Tmp1 = uint32_t(VAL >> 16);
739 Tmp1 = ByteSwap_32(Tmp1);
740 uint16_t Tmp2 = uint16_t(VAL);
741 Tmp2 = ByteSwap_16(Tmp2);
742 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
743 } else if (BitWidth == 64)
744 return APInt(BitWidth, ByteSwap_64(VAL));
746 APInt Result(BitWidth, 0);
747 char *pByte = (char*)Result.pVal;
748 for (uint32_t i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
750 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
751 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
757 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
759 APInt A = API1, B = API2;
762 B = APIntOps::urem(A, B);
768 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) {
775 // Get the sign bit from the highest order bit
776 bool isNeg = T.I >> 63;
778 // Get the 11-bit exponent and adjust for the 1023 bit bias
779 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
781 // If the exponent is negative, the value is < 0 so just return 0.
783 return APInt(width, 0u);
785 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
786 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
788 // If the exponent doesn't shift all bits out of the mantissa
790 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
791 APInt(width, mantissa >> (52 - exp));
793 // If the client didn't provide enough bits for us to shift the mantissa into
794 // then the result is undefined, just return 0
795 if (width <= exp - 52)
796 return APInt(width, 0);
798 // Otherwise, we have to shift the mantissa bits up to the right location
799 APInt Tmp(width, mantissa);
800 Tmp = Tmp.shl((uint32_t)exp - 52);
801 return isNeg ? -Tmp : Tmp;
804 /// RoundToDouble - This function convert this APInt to a double.
805 /// The layout for double is as following (IEEE Standard 754):
806 /// --------------------------------------
807 /// | Sign Exponent Fraction Bias |
808 /// |-------------------------------------- |
809 /// | 1[63] 11[62-52] 52[51-00] 1023 |
810 /// --------------------------------------
811 double APInt::roundToDouble(bool isSigned) const {
813 // Handle the simple case where the value is contained in one uint64_t.
814 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
816 int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
822 // Determine if the value is negative.
823 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
825 // Construct the absolute value if we're negative.
826 APInt Tmp(isNeg ? -(*this) : (*this));
828 // Figure out how many bits we're using.
829 uint32_t n = Tmp.getActiveBits();
831 // The exponent (without bias normalization) is just the number of bits
832 // we are using. Note that the sign bit is gone since we constructed the
836 // Return infinity for exponent overflow
838 if (!isSigned || !isNeg)
839 return std::numeric_limits<double>::infinity();
841 return -std::numeric_limits<double>::infinity();
843 exp += 1023; // Increment for 1023 bias
845 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
846 // extract the high 52 bits from the correct words in pVal.
848 unsigned hiWord = whichWord(n-1);
850 mantissa = Tmp.pVal[0];
852 mantissa >>= n - 52; // shift down, we want the top 52 bits.
854 assert(hiWord > 0 && "huh?");
855 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
856 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
857 mantissa = hibits | lobits;
860 // The leading bit of mantissa is implicit, so get rid of it.
861 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
866 T.I = sign | (exp << 52) | mantissa;
870 // Truncate to new width.
871 APInt &APInt::trunc(uint32_t width) {
872 assert(width < BitWidth && "Invalid APInt Truncate request");
873 assert(width && "Can't truncate to 0 bits");
874 uint32_t wordsBefore = getNumWords();
876 uint32_t wordsAfter = getNumWords();
877 if (wordsBefore != wordsAfter) {
878 if (wordsAfter == 1) {
879 uint64_t *tmp = pVal;
883 uint64_t *newVal = getClearedMemory(wordsAfter);
884 for (uint32_t i = 0; i < wordsAfter; ++i)
890 return clearUnusedBits();
893 // Sign extend to a new width.
894 APInt &APInt::sext(uint32_t width) {
895 assert(width > BitWidth && "Invalid APInt SignExtend request");
896 // If the sign bit isn't set, this is the same as zext.
902 // The sign bit is set. First, get some facts
903 uint32_t wordsBefore = getNumWords();
904 uint32_t wordBits = BitWidth % APINT_BITS_PER_WORD;
906 uint32_t wordsAfter = getNumWords();
908 // Mask the high order word appropriately
909 if (wordsBefore == wordsAfter) {
910 uint32_t newWordBits = width % APINT_BITS_PER_WORD;
911 // The extension is contained to the wordsBefore-1th word.
912 uint64_t mask = ~0ULL;
914 mask >>= APINT_BITS_PER_WORD - newWordBits;
916 if (wordsBefore == 1)
919 pVal[wordsBefore-1] |= mask;
920 return clearUnusedBits();
923 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
924 uint64_t *newVal = getMemory(wordsAfter);
925 if (wordsBefore == 1)
926 newVal[0] = VAL | mask;
928 for (uint32_t i = 0; i < wordsBefore; ++i)
930 newVal[wordsBefore-1] |= mask;
932 for (uint32_t i = wordsBefore; i < wordsAfter; i++)
934 if (wordsBefore != 1)
937 return clearUnusedBits();
940 // Zero extend to a new width.
941 APInt &APInt::zext(uint32_t width) {
942 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
943 uint32_t wordsBefore = getNumWords();
945 uint32_t wordsAfter = getNumWords();
946 if (wordsBefore != wordsAfter) {
947 uint64_t *newVal = getClearedMemory(wordsAfter);
948 if (wordsBefore == 1)
951 for (uint32_t i = 0; i < wordsBefore; ++i)
953 if (wordsBefore != 1)
960 APInt &APInt::zextOrTrunc(uint32_t width) {
961 if (BitWidth < width)
963 if (BitWidth > width)
968 APInt &APInt::sextOrTrunc(uint32_t width) {
969 if (BitWidth < width)
971 if (BitWidth > width)
976 /// Arithmetic right-shift this APInt by shiftAmt.
977 /// @brief Arithmetic right-shift function.
978 APInt APInt::ashr(const APInt &shiftAmt) const {
979 return ashr((uint32_t)shiftAmt.getLimitedValue(BitWidth));
982 /// Arithmetic right-shift this APInt by shiftAmt.
983 /// @brief Arithmetic right-shift function.
984 APInt APInt::ashr(uint32_t shiftAmt) const {
985 assert(shiftAmt <= BitWidth && "Invalid shift amount");
986 // Handle a degenerate case
990 // Handle single word shifts with built-in ashr
991 if (isSingleWord()) {
992 if (shiftAmt == BitWidth)
993 return APInt(BitWidth, 0); // undefined
995 uint32_t SignBit = APINT_BITS_PER_WORD - BitWidth;
996 return APInt(BitWidth,
997 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1001 // If all the bits were shifted out, the result is, technically, undefined.
1002 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1003 // issues in the algorithm below.
1004 if (shiftAmt == BitWidth) {
1006 return APInt(BitWidth, -1ULL, true);
1008 return APInt(BitWidth, 0);
1011 // Create some space for the result.
1012 uint64_t * val = new uint64_t[getNumWords()];
1014 // Compute some values needed by the following shift algorithms
1015 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1016 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1017 uint32_t breakWord = getNumWords() - 1 - offset; // last word affected
1018 uint32_t bitsInWord = whichBit(BitWidth); // how many bits in last word?
1019 if (bitsInWord == 0)
1020 bitsInWord = APINT_BITS_PER_WORD;
1022 // If we are shifting whole words, just move whole words
1023 if (wordShift == 0) {
1024 // Move the words containing significant bits
1025 for (uint32_t i = 0; i <= breakWord; ++i)
1026 val[i] = pVal[i+offset]; // move whole word
1028 // Adjust the top significant word for sign bit fill, if negative
1030 if (bitsInWord < APINT_BITS_PER_WORD)
1031 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1033 // Shift the low order words
1034 for (uint32_t i = 0; i < breakWord; ++i) {
1035 // This combines the shifted corresponding word with the low bits from
1036 // the next word (shifted into this word's high bits).
1037 val[i] = (pVal[i+offset] >> wordShift) |
1038 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1041 // Shift the break word. In this case there are no bits from the next word
1042 // to include in this word.
1043 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1045 // Deal with sign extenstion in the break word, and possibly the word before
1048 if (wordShift > bitsInWord) {
1051 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1052 val[breakWord] |= ~0ULL;
1054 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1058 // Remaining words are 0 or -1, just assign them.
1059 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1060 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1062 return APInt(val, BitWidth).clearUnusedBits();
1065 /// Logical right-shift this APInt by shiftAmt.
1066 /// @brief Logical right-shift function.
1067 APInt APInt::lshr(const APInt &shiftAmt) const {
1068 return lshr((uint32_t)shiftAmt.getLimitedValue(BitWidth));
1071 /// Logical right-shift this APInt by shiftAmt.
1072 /// @brief Logical right-shift function.
1073 APInt APInt::lshr(uint32_t shiftAmt) const {
1074 if (isSingleWord()) {
1075 if (shiftAmt == BitWidth)
1076 return APInt(BitWidth, 0);
1078 return APInt(BitWidth, this->VAL >> shiftAmt);
1081 // If all the bits were shifted out, the result is 0. This avoids issues
1082 // with shifting by the size of the integer type, which produces undefined
1083 // results. We define these "undefined results" to always be 0.
1084 if (shiftAmt == BitWidth)
1085 return APInt(BitWidth, 0);
1087 // If none of the bits are shifted out, the result is *this. This avoids
1088 // issues with shifting byt he size of the integer type, which produces
1089 // undefined results in the code below. This is also an optimization.
1093 // Create some space for the result.
1094 uint64_t * val = new uint64_t[getNumWords()];
1096 // If we are shifting less than a word, compute the shift with a simple carry
1097 if (shiftAmt < APINT_BITS_PER_WORD) {
1099 for (int i = getNumWords()-1; i >= 0; --i) {
1100 val[i] = (pVal[i] >> shiftAmt) | carry;
1101 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1103 return APInt(val, BitWidth).clearUnusedBits();
1106 // Compute some values needed by the remaining shift algorithms
1107 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1108 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1110 // If we are shifting whole words, just move whole words
1111 if (wordShift == 0) {
1112 for (uint32_t i = 0; i < getNumWords() - offset; ++i)
1113 val[i] = pVal[i+offset];
1114 for (uint32_t i = getNumWords()-offset; i < getNumWords(); i++)
1116 return APInt(val,BitWidth).clearUnusedBits();
1119 // Shift the low order words
1120 uint32_t breakWord = getNumWords() - offset -1;
1121 for (uint32_t i = 0; i < breakWord; ++i)
1122 val[i] = (pVal[i+offset] >> wordShift) |
1123 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1124 // Shift the break word.
1125 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1127 // Remaining words are 0
1128 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1130 return APInt(val, BitWidth).clearUnusedBits();
1133 /// Left-shift this APInt by shiftAmt.
1134 /// @brief Left-shift function.
1135 APInt APInt::shl(const APInt &shiftAmt) const {
1136 // It's undefined behavior in C to shift by BitWidth or greater, but
1137 return shl((uint32_t)shiftAmt.getLimitedValue(BitWidth));
1140 APInt APInt::shlSlowCase(uint32_t shiftAmt) const {
1141 // If all the bits were shifted out, the result is 0. This avoids issues
1142 // with shifting by the size of the integer type, which produces undefined
1143 // results. We define these "undefined results" to always be 0.
1144 if (shiftAmt == BitWidth)
1145 return APInt(BitWidth, 0);
1147 // If none of the bits are shifted out, the result is *this. This avoids a
1148 // lshr by the words size in the loop below which can produce incorrect
1149 // results. It also avoids the expensive computation below for a common case.
1153 // Create some space for the result.
1154 uint64_t * val = new uint64_t[getNumWords()];
1156 // If we are shifting less than a word, do it the easy way
1157 if (shiftAmt < APINT_BITS_PER_WORD) {
1159 for (uint32_t i = 0; i < getNumWords(); i++) {
1160 val[i] = pVal[i] << shiftAmt | carry;
1161 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1163 return APInt(val, BitWidth).clearUnusedBits();
1166 // Compute some values needed by the remaining shift algorithms
1167 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1168 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1170 // If we are shifting whole words, just move whole words
1171 if (wordShift == 0) {
1172 for (uint32_t i = 0; i < offset; i++)
1174 for (uint32_t i = offset; i < getNumWords(); i++)
1175 val[i] = pVal[i-offset];
1176 return APInt(val,BitWidth).clearUnusedBits();
1179 // Copy whole words from this to Result.
1180 uint32_t i = getNumWords() - 1;
1181 for (; i > offset; --i)
1182 val[i] = pVal[i-offset] << wordShift |
1183 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1184 val[offset] = pVal[0] << wordShift;
1185 for (i = 0; i < offset; ++i)
1187 return APInt(val, BitWidth).clearUnusedBits();
1190 APInt APInt::rotl(const APInt &rotateAmt) const {
1191 return rotl((uint32_t)rotateAmt.getLimitedValue(BitWidth));
1194 APInt APInt::rotl(uint32_t rotateAmt) const {
1197 // Don't get too fancy, just use existing shift/or facilities
1201 lo.lshr(BitWidth - rotateAmt);
1205 APInt APInt::rotr(const APInt &rotateAmt) const {
1206 return rotr((uint32_t)rotateAmt.getLimitedValue(BitWidth));
1209 APInt APInt::rotr(uint32_t rotateAmt) const {
1212 // Don't get too fancy, just use existing shift/or facilities
1216 hi.shl(BitWidth - rotateAmt);
1220 // Square Root - this method computes and returns the square root of "this".
1221 // Three mechanisms are used for computation. For small values (<= 5 bits),
1222 // a table lookup is done. This gets some performance for common cases. For
1223 // values using less than 52 bits, the value is converted to double and then
1224 // the libc sqrt function is called. The result is rounded and then converted
1225 // back to a uint64_t which is then used to construct the result. Finally,
1226 // the Babylonian method for computing square roots is used.
1227 APInt APInt::sqrt() const {
1229 // Determine the magnitude of the value.
1230 uint32_t magnitude = getActiveBits();
1232 // Use a fast table for some small values. This also gets rid of some
1233 // rounding errors in libc sqrt for small values.
1234 if (magnitude <= 5) {
1235 static const uint8_t results[32] = {
1238 /* 3- 6 */ 2, 2, 2, 2,
1239 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1240 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1241 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1244 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1247 // If the magnitude of the value fits in less than 52 bits (the precision of
1248 // an IEEE double precision floating point value), then we can use the
1249 // libc sqrt function which will probably use a hardware sqrt computation.
1250 // This should be faster than the algorithm below.
1251 if (magnitude < 52) {
1253 // Amazingly, VC++ doesn't have round().
1254 return APInt(BitWidth,
1255 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1257 return APInt(BitWidth,
1258 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1262 // Okay, all the short cuts are exhausted. We must compute it. The following
1263 // is a classical Babylonian method for computing the square root. This code
1264 // was adapted to APINt from a wikipedia article on such computations.
1265 // See http://www.wikipedia.org/ and go to the page named
1266 // Calculate_an_integer_square_root.
1267 uint32_t nbits = BitWidth, i = 4;
1268 APInt testy(BitWidth, 16);
1269 APInt x_old(BitWidth, 1);
1270 APInt x_new(BitWidth, 0);
1271 APInt two(BitWidth, 2);
1273 // Select a good starting value using binary logarithms.
1274 for (;; i += 2, testy = testy.shl(2))
1275 if (i >= nbits || this->ule(testy)) {
1276 x_old = x_old.shl(i / 2);
1280 // Use the Babylonian method to arrive at the integer square root:
1282 x_new = (this->udiv(x_old) + x_old).udiv(two);
1283 if (x_old.ule(x_new))
1288 // Make sure we return the closest approximation
1289 // NOTE: The rounding calculation below is correct. It will produce an
1290 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1291 // determined to be a rounding issue with pari/gp as it begins to use a
1292 // floating point representation after 192 bits. There are no discrepancies
1293 // between this algorithm and pari/gp for bit widths < 192 bits.
1294 APInt square(x_old * x_old);
1295 APInt nextSquare((x_old + 1) * (x_old +1));
1296 if (this->ult(square))
1298 else if (this->ule(nextSquare)) {
1299 APInt midpoint((nextSquare - square).udiv(two));
1300 APInt offset(*this - square);
1301 if (offset.ult(midpoint))
1306 assert(0 && "Error in APInt::sqrt computation");
1310 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1311 /// iterative extended Euclidean algorithm is used to solve for this value,
1312 /// however we simplify it to speed up calculating only the inverse, and take
1313 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1314 /// (potentially large) APInts around.
1315 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1316 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1318 // Using the properties listed at the following web page (accessed 06/21/08):
1319 // http://www.numbertheory.org/php/euclid.html
1320 // (especially the properties numbered 3, 4 and 9) it can be proved that
1321 // BitWidth bits suffice for all the computations in the algorithm implemented
1322 // below. More precisely, this number of bits suffice if the multiplicative
1323 // inverse exists, but may not suffice for the general extended Euclidean
1326 APInt r[2] = { modulo, *this };
1327 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1328 APInt q(BitWidth, 0);
1331 for (i = 0; r[i^1] != 0; i ^= 1) {
1332 // An overview of the math without the confusing bit-flipping:
1333 // q = r[i-2] / r[i-1]
1334 // r[i] = r[i-2] % r[i-1]
1335 // t[i] = t[i-2] - t[i-1] * q
1336 udivrem(r[i], r[i^1], q, r[i]);
1340 // If this APInt and the modulo are not coprime, there is no multiplicative
1341 // inverse, so return 0. We check this by looking at the next-to-last
1342 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1345 return APInt(BitWidth, 0);
1347 // The next-to-last t is the multiplicative inverse. However, we are
1348 // interested in a positive inverse. Calcuate a positive one from a negative
1349 // one if necessary. A simple addition of the modulo suffices because
1350 // abs(t[i]) is known to be less than *this/2 (see the link above).
1351 return t[i].isNegative() ? t[i] + modulo : t[i];
1354 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1355 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1356 /// variables here have the same names as in the algorithm. Comments explain
1357 /// the algorithm and any deviation from it.
1358 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1359 uint32_t m, uint32_t n) {
1360 assert(u && "Must provide dividend");
1361 assert(v && "Must provide divisor");
1362 assert(q && "Must provide quotient");
1363 assert(u != v && u != q && v != q && "Must us different memory");
1364 assert(n>1 && "n must be > 1");
1366 // Knuth uses the value b as the base of the number system. In our case b
1367 // is 2^31 so we just set it to -1u.
1368 uint64_t b = uint64_t(1) << 32;
1371 DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n');
1372 DEBUG(cerr << "KnuthDiv: original:");
1373 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1374 DEBUG(cerr << " by");
1375 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1376 DEBUG(cerr << '\n');
1378 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1379 // u and v by d. Note that we have taken Knuth's advice here to use a power
1380 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1381 // 2 allows us to shift instead of multiply and it is easy to determine the
1382 // shift amount from the leading zeros. We are basically normalizing the u
1383 // and v so that its high bits are shifted to the top of v's range without
1384 // overflow. Note that this can require an extra word in u so that u must
1385 // be of length m+n+1.
1386 uint32_t shift = CountLeadingZeros_32(v[n-1]);
1387 uint32_t v_carry = 0;
1388 uint32_t u_carry = 0;
1390 for (uint32_t i = 0; i < m+n; ++i) {
1391 uint32_t u_tmp = u[i] >> (32 - shift);
1392 u[i] = (u[i] << shift) | u_carry;
1395 for (uint32_t i = 0; i < n; ++i) {
1396 uint32_t v_tmp = v[i] >> (32 - shift);
1397 v[i] = (v[i] << shift) | v_carry;
1403 DEBUG(cerr << "KnuthDiv: normal:");
1404 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1405 DEBUG(cerr << " by");
1406 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1407 DEBUG(cerr << '\n');
1410 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1413 DEBUG(cerr << "KnuthDiv: quotient digit #" << j << '\n');
1414 // D3. [Calculate q'.].
1415 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1416 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1417 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1418 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1419 // on v[n-2] determines at high speed most of the cases in which the trial
1420 // value qp is one too large, and it eliminates all cases where qp is two
1422 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1423 DEBUG(cerr << "KnuthDiv: dividend == " << dividend << '\n');
1424 uint64_t qp = dividend / v[n-1];
1425 uint64_t rp = dividend % v[n-1];
1426 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1429 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1432 DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1434 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1435 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1436 // consists of a simple multiplication by a one-place number, combined with
1439 for (uint32_t i = 0; i < n; ++i) {
1440 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1441 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1442 bool borrow = subtrahend > u_tmp;
1443 DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp
1444 << ", subtrahend == " << subtrahend
1445 << ", borrow = " << borrow << '\n');
1447 uint64_t result = u_tmp - subtrahend;
1449 u[k++] = (uint32_t)(result & (b-1)); // subtract low word
1450 u[k++] = (uint32_t)(result >> 32); // subtract high word
1451 while (borrow && k <= m+n) { // deal with borrow to the left
1457 DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1460 DEBUG(cerr << "KnuthDiv: after subtraction:");
1461 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1462 DEBUG(cerr << '\n');
1463 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1464 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1465 // true value plus b**(n+1), namely as the b's complement of
1466 // the true value, and a "borrow" to the left should be remembered.
1469 bool carry = true; // true because b's complement is "complement + 1"
1470 for (uint32_t i = 0; i <= m+n; ++i) {
1471 u[i] = ~u[i] + carry; // b's complement
1472 carry = carry && u[i] == 0;
1475 DEBUG(cerr << "KnuthDiv: after complement:");
1476 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1477 DEBUG(cerr << '\n');
1479 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1480 // negative, go to step D6; otherwise go on to step D7.
1481 q[j] = (uint32_t)qp;
1483 // D6. [Add back]. The probability that this step is necessary is very
1484 // small, on the order of only 2/b. Make sure that test data accounts for
1485 // this possibility. Decrease q[j] by 1
1487 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1488 // A carry will occur to the left of u[j+n], and it should be ignored
1489 // since it cancels with the borrow that occurred in D4.
1491 for (uint32_t i = 0; i < n; i++) {
1492 uint32_t limit = std::min(u[j+i],v[i]);
1493 u[j+i] += v[i] + carry;
1494 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1498 DEBUG(cerr << "KnuthDiv: after correction:");
1499 DEBUG(for (int i = m+n; i >=0; i--) cerr <<" " << u[i]);
1500 DEBUG(cerr << "\nKnuthDiv: digit result = " << q[j] << '\n');
1502 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1505 DEBUG(cerr << "KnuthDiv: quotient:");
1506 DEBUG(for (int i = m; i >=0; i--) cerr <<" " << q[i]);
1507 DEBUG(cerr << '\n');
1509 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1510 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1511 // compute the remainder (urem uses this).
1513 // The value d is expressed by the "shift" value above since we avoided
1514 // multiplication by d by using a shift left. So, all we have to do is
1515 // shift right here. In order to mak
1518 DEBUG(cerr << "KnuthDiv: remainder:");
1519 for (int i = n-1; i >= 0; i--) {
1520 r[i] = (u[i] >> shift) | carry;
1521 carry = u[i] << (32 - shift);
1522 DEBUG(cerr << " " << r[i]);
1525 for (int i = n-1; i >= 0; i--) {
1527 DEBUG(cerr << " " << r[i]);
1530 DEBUG(cerr << '\n');
1533 DEBUG(cerr << std::setbase(10) << '\n');
1537 void APInt::divide(const APInt LHS, uint32_t lhsWords,
1538 const APInt &RHS, uint32_t rhsWords,
1539 APInt *Quotient, APInt *Remainder)
1541 assert(lhsWords >= rhsWords && "Fractional result");
1543 // First, compose the values into an array of 32-bit words instead of
1544 // 64-bit words. This is a necessity of both the "short division" algorithm
1545 // and the the Knuth "classical algorithm" which requires there to be native
1546 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1547 // can't use 64-bit operands here because we don't have native results of
1548 // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't
1549 // work on large-endian machines.
1550 uint64_t mask = ~0ull >> (sizeof(uint32_t)*8);
1551 uint32_t n = rhsWords * 2;
1552 uint32_t m = (lhsWords * 2) - n;
1554 // Allocate space for the temporary values we need either on the stack, if
1555 // it will fit, or on the heap if it won't.
1556 uint32_t SPACE[128];
1561 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1564 Q = &SPACE[(m+n+1) + n];
1566 R = &SPACE[(m+n+1) + n + (m+n)];
1568 U = new uint32_t[m + n + 1];
1569 V = new uint32_t[n];
1570 Q = new uint32_t[m+n];
1572 R = new uint32_t[n];
1575 // Initialize the dividend
1576 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1577 for (unsigned i = 0; i < lhsWords; ++i) {
1578 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1579 U[i * 2] = (uint32_t)(tmp & mask);
1580 U[i * 2 + 1] = (uint32_t)(tmp >> (sizeof(uint32_t)*8));
1582 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1584 // Initialize the divisor
1585 memset(V, 0, (n)*sizeof(uint32_t));
1586 for (unsigned i = 0; i < rhsWords; ++i) {
1587 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1588 V[i * 2] = (uint32_t)(tmp & mask);
1589 V[i * 2 + 1] = (uint32_t)(tmp >> (sizeof(uint32_t)*8));
1592 // initialize the quotient and remainder
1593 memset(Q, 0, (m+n) * sizeof(uint32_t));
1595 memset(R, 0, n * sizeof(uint32_t));
1597 // Now, adjust m and n for the Knuth division. n is the number of words in
1598 // the divisor. m is the number of words by which the dividend exceeds the
1599 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1600 // contain any zero words or the Knuth algorithm fails.
1601 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1605 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1608 // If we're left with only a single word for the divisor, Knuth doesn't work
1609 // so we implement the short division algorithm here. This is much simpler
1610 // and faster because we are certain that we can divide a 64-bit quantity
1611 // by a 32-bit quantity at hardware speed and short division is simply a
1612 // series of such operations. This is just like doing short division but we
1613 // are using base 2^32 instead of base 10.
1614 assert(n != 0 && "Divide by zero?");
1616 uint32_t divisor = V[0];
1617 uint32_t remainder = 0;
1618 for (int i = m+n-1; i >= 0; i--) {
1619 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1620 if (partial_dividend == 0) {
1623 } else if (partial_dividend < divisor) {
1625 remainder = (uint32_t)partial_dividend;
1626 } else if (partial_dividend == divisor) {
1630 Q[i] = (uint32_t)(partial_dividend / divisor);
1631 remainder = (uint32_t)(partial_dividend - (Q[i] * divisor));
1637 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1639 KnuthDiv(U, V, Q, R, m, n);
1642 // If the caller wants the quotient
1644 // Set up the Quotient value's memory.
1645 if (Quotient->BitWidth != LHS.BitWidth) {
1646 if (Quotient->isSingleWord())
1649 delete [] Quotient->pVal;
1650 Quotient->BitWidth = LHS.BitWidth;
1651 if (!Quotient->isSingleWord())
1652 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1656 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1658 if (lhsWords == 1) {
1660 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1661 if (Quotient->isSingleWord())
1662 Quotient->VAL = tmp;
1664 Quotient->pVal[0] = tmp;
1666 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1667 for (unsigned i = 0; i < lhsWords; ++i)
1669 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1673 // If the caller wants the remainder
1675 // Set up the Remainder value's memory.
1676 if (Remainder->BitWidth != RHS.BitWidth) {
1677 if (Remainder->isSingleWord())
1680 delete [] Remainder->pVal;
1681 Remainder->BitWidth = RHS.BitWidth;
1682 if (!Remainder->isSingleWord())
1683 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1687 // The remainder is in R. Reconstitute the remainder into Remainder's low
1689 if (rhsWords == 1) {
1691 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1692 if (Remainder->isSingleWord())
1693 Remainder->VAL = tmp;
1695 Remainder->pVal[0] = tmp;
1697 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1698 for (unsigned i = 0; i < rhsWords; ++i)
1699 Remainder->pVal[i] =
1700 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1704 // Clean up the memory we allocated.
1705 if (U != &SPACE[0]) {
1713 APInt APInt::udiv(const APInt& RHS) const {
1714 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1716 // First, deal with the easy case
1717 if (isSingleWord()) {
1718 assert(RHS.VAL != 0 && "Divide by zero?");
1719 return APInt(BitWidth, VAL / RHS.VAL);
1722 // Get some facts about the LHS and RHS number of bits and words
1723 uint32_t rhsBits = RHS.getActiveBits();
1724 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1725 assert(rhsWords && "Divided by zero???");
1726 uint32_t lhsBits = this->getActiveBits();
1727 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1729 // Deal with some degenerate cases
1732 return APInt(BitWidth, 0);
1733 else if (lhsWords < rhsWords || this->ult(RHS)) {
1734 // X / Y ===> 0, iff X < Y
1735 return APInt(BitWidth, 0);
1736 } else if (*this == RHS) {
1738 return APInt(BitWidth, 1);
1739 } else if (lhsWords == 1 && rhsWords == 1) {
1740 // All high words are zero, just use native divide
1741 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1744 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1745 APInt Quotient(1,0); // to hold result.
1746 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1750 APInt APInt::urem(const APInt& RHS) const {
1751 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1752 if (isSingleWord()) {
1753 assert(RHS.VAL != 0 && "Remainder by zero?");
1754 return APInt(BitWidth, VAL % RHS.VAL);
1757 // Get some facts about the LHS
1758 uint32_t lhsBits = getActiveBits();
1759 uint32_t lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1761 // Get some facts about the RHS
1762 uint32_t rhsBits = RHS.getActiveBits();
1763 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1764 assert(rhsWords && "Performing remainder operation by zero ???");
1766 // Check the degenerate cases
1767 if (lhsWords == 0) {
1769 return APInt(BitWidth, 0);
1770 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1771 // X % Y ===> X, iff X < Y
1773 } else if (*this == RHS) {
1775 return APInt(BitWidth, 0);
1776 } else if (lhsWords == 1) {
1777 // All high words are zero, just use native remainder
1778 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1781 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1782 APInt Remainder(1,0);
1783 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1787 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1788 APInt &Quotient, APInt &Remainder) {
1789 // Get some size facts about the dividend and divisor
1790 uint32_t lhsBits = LHS.getActiveBits();
1791 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1792 uint32_t rhsBits = RHS.getActiveBits();
1793 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1795 // Check the degenerate cases
1796 if (lhsWords == 0) {
1797 Quotient = 0; // 0 / Y ===> 0
1798 Remainder = 0; // 0 % Y ===> 0
1802 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1803 Quotient = 0; // X / Y ===> 0, iff X < Y
1804 Remainder = LHS; // X % Y ===> X, iff X < Y
1809 Quotient = 1; // X / X ===> 1
1810 Remainder = 0; // X % X ===> 0;
1814 if (lhsWords == 1 && rhsWords == 1) {
1815 // There is only one word to consider so use the native versions.
1816 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1817 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1818 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1819 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
1823 // Okay, lets do it the long way
1824 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1827 void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen,
1829 // Check our assumptions here
1830 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1831 "Radix should be 2, 8, 10, or 16!");
1832 assert(str && "String is null?");
1833 bool isNeg = str[0] == '-';
1836 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
1837 assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width");
1838 assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width");
1839 assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width");
1842 if (!isSingleWord())
1843 pVal = getClearedMemory(getNumWords());
1845 // Figure out if we can shift instead of multiply
1846 uint32_t shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1848 // Set up an APInt for the digit to add outside the loop so we don't
1849 // constantly construct/destruct it.
1850 APInt apdigit(getBitWidth(), 0);
1851 APInt apradix(getBitWidth(), radix);
1853 // Enter digit traversal loop
1854 for (unsigned i = 0; i < slen; i++) {
1857 char cdigit = str[i];
1859 if (!isxdigit(cdigit))
1860 assert(0 && "Invalid hex digit in string");
1861 if (isdigit(cdigit))
1862 digit = cdigit - '0';
1863 else if (cdigit >= 'a')
1864 digit = cdigit - 'a' + 10;
1865 else if (cdigit >= 'A')
1866 digit = cdigit - 'A' + 10;
1868 assert(0 && "huh? we shouldn't get here");
1869 } else if (isdigit(cdigit)) {
1870 digit = cdigit - '0';
1871 assert((radix == 10 ||
1872 (radix == 8 && digit != 8 && digit != 9) ||
1873 (radix == 2 && (digit == 0 || digit == 1))) &&
1874 "Invalid digit in string for given radix");
1876 assert(0 && "Invalid character in digit string");
1879 // Shift or multiply the value by the radix
1885 // Add in the digit we just interpreted
1886 if (apdigit.isSingleWord())
1887 apdigit.VAL = digit;
1889 apdigit.pVal[0] = digit;
1892 // If its negative, put it in two's complement form
1899 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
1900 bool Signed) const {
1901 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) &&
1902 "Radix should be 2, 8, 10, or 16!");
1904 // First, check for a zero value and just short circuit the logic below.
1910 static const char Digits[] = "0123456789ABCDEF";
1912 if (isSingleWord()) {
1914 char *BufPtr = Buffer+65;
1918 int64_t I = getSExtValue();
1929 *--BufPtr = Digits[N % Radix];
1932 Str.append(BufPtr, Buffer+65);
1938 if (Signed && isNegative()) {
1939 // They want to print the signed version and it is a negative value
1940 // Flip the bits and add one to turn it into the equivalent positive
1941 // value and put a '-' in the result.
1947 // We insert the digits backward, then reverse them to get the right order.
1948 unsigned StartDig = Str.size();
1950 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
1951 // because the number of bits per digit (1, 3 and 4 respectively) divides
1952 // equaly. We just shift until the value is zero.
1954 // Just shift tmp right for each digit width until it becomes zero
1955 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
1956 unsigned MaskAmt = Radix - 1;
1959 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
1960 Str.push_back(Digits[Digit]);
1961 Tmp = Tmp.lshr(ShiftAmt);
1964 APInt divisor(4, 10);
1966 APInt APdigit(1, 0);
1967 APInt tmp2(Tmp.getBitWidth(), 0);
1968 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
1970 uint32_t Digit = (uint32_t)APdigit.getZExtValue();
1971 assert(Digit < Radix && "divide failed");
1972 Str.push_back(Digits[Digit]);
1977 // Reverse the digits before returning.
1978 std::reverse(Str.begin()+StartDig, Str.end());
1981 /// toString - This returns the APInt as a std::string. Note that this is an
1982 /// inefficient method. It is better to pass in a SmallVector/SmallString
1983 /// to the methods above.
1984 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
1986 toString(S, Radix, Signed);
1991 void APInt::dump() const {
1992 SmallString<40> S, U;
1993 this->toStringUnsigned(U);
1994 this->toStringSigned(S);
1995 fprintf(stderr, "APInt(%db, %su %ss)", BitWidth, U.c_str(), S.c_str());
1998 void APInt::print(std::ostream &OS, bool isSigned) const {
2000 this->toString(S, 10, isSigned);
2005 // This implements a variety of operations on a representation of
2006 // arbitrary precision, two's-complement, bignum integer values.
2008 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2009 and unrestricting assumption. */
2010 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
2011 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2013 /* Some handy functions local to this file. */
2016 /* Returns the integer part with the least significant BITS set.
2017 BITS cannot be zero. */
2018 static inline integerPart
2019 lowBitMask(unsigned int bits)
2021 assert (bits != 0 && bits <= integerPartWidth);
2023 return ~(integerPart) 0 >> (integerPartWidth - bits);
2026 /* Returns the value of the lower half of PART. */
2027 static inline integerPart
2028 lowHalf(integerPart part)
2030 return part & lowBitMask(integerPartWidth / 2);
2033 /* Returns the value of the upper half of PART. */
2034 static inline integerPart
2035 highHalf(integerPart part)
2037 return part >> (integerPartWidth / 2);
2040 /* Returns the bit number of the most significant set bit of a part.
2041 If the input number has no bits set -1U is returned. */
2043 partMSB(integerPart value)
2045 unsigned int n, msb;
2050 n = integerPartWidth / 2;
2065 /* Returns the bit number of the least significant set bit of a
2066 part. If the input number has no bits set -1U is returned. */
2068 partLSB(integerPart value)
2070 unsigned int n, lsb;
2075 lsb = integerPartWidth - 1;
2076 n = integerPartWidth / 2;
2091 /* Sets the least significant part of a bignum to the input value, and
2092 zeroes out higher parts. */
2094 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2101 for(i = 1; i < parts; i++)
2105 /* Assign one bignum to another. */
2107 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2111 for(i = 0; i < parts; i++)
2115 /* Returns true if a bignum is zero, false otherwise. */
2117 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2121 for(i = 0; i < parts; i++)
2128 /* Extract the given bit of a bignum; returns 0 or 1. */
2130 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2132 return(parts[bit / integerPartWidth]
2133 & ((integerPart) 1 << bit % integerPartWidth)) != 0;
2136 /* Set the given bit of a bignum. */
2138 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2140 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2143 /* Returns the bit number of the least significant set bit of a
2144 number. If the input number has no bits set -1U is returned. */
2146 APInt::tcLSB(const integerPart *parts, unsigned int n)
2148 unsigned int i, lsb;
2150 for(i = 0; i < n; i++) {
2151 if (parts[i] != 0) {
2152 lsb = partLSB(parts[i]);
2154 return lsb + i * integerPartWidth;
2161 /* Returns the bit number of the most significant set bit of a number.
2162 If the input number has no bits set -1U is returned. */
2164 APInt::tcMSB(const integerPart *parts, unsigned int n)
2171 if (parts[n] != 0) {
2172 msb = partMSB(parts[n]);
2174 return msb + n * integerPartWidth;
2181 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2182 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2183 the least significant bit of DST. All high bits above srcBITS in
2184 DST are zero-filled. */
2186 APInt::tcExtract(integerPart *dst, unsigned int dstCount, const integerPart *src,
2187 unsigned int srcBits, unsigned int srcLSB)
2189 unsigned int firstSrcPart, dstParts, shift, n;
2191 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2192 assert (dstParts <= dstCount);
2194 firstSrcPart = srcLSB / integerPartWidth;
2195 tcAssign (dst, src + firstSrcPart, dstParts);
2197 shift = srcLSB % integerPartWidth;
2198 tcShiftRight (dst, dstParts, shift);
2200 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2201 in DST. If this is less that srcBits, append the rest, else
2202 clear the high bits. */
2203 n = dstParts * integerPartWidth - shift;
2205 integerPart mask = lowBitMask (srcBits - n);
2206 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2207 << n % integerPartWidth);
2208 } else if (n > srcBits) {
2209 if (srcBits % integerPartWidth)
2210 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2213 /* Clear high parts. */
2214 while (dstParts < dstCount)
2215 dst[dstParts++] = 0;
2218 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2220 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2221 integerPart c, unsigned int parts)
2227 for(i = 0; i < parts; i++) {
2232 dst[i] += rhs[i] + 1;
2243 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2245 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2246 integerPart c, unsigned int parts)
2252 for(i = 0; i < parts; i++) {
2257 dst[i] -= rhs[i] + 1;
2268 /* Negate a bignum in-place. */
2270 APInt::tcNegate(integerPart *dst, unsigned int parts)
2272 tcComplement(dst, parts);
2273 tcIncrement(dst, parts);
2276 /* DST += SRC * MULTIPLIER + CARRY if add is true
2277 DST = SRC * MULTIPLIER + CARRY if add is false
2279 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2280 they must start at the same point, i.e. DST == SRC.
2282 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2283 returned. Otherwise DST is filled with the least significant
2284 DSTPARTS parts of the result, and if all of the omitted higher
2285 parts were zero return zero, otherwise overflow occurred and
2288 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2289 integerPart multiplier, integerPart carry,
2290 unsigned int srcParts, unsigned int dstParts,
2295 /* Otherwise our writes of DST kill our later reads of SRC. */
2296 assert(dst <= src || dst >= src + srcParts);
2297 assert(dstParts <= srcParts + 1);
2299 /* N loops; minimum of dstParts and srcParts. */
2300 n = dstParts < srcParts ? dstParts: srcParts;
2302 for(i = 0; i < n; i++) {
2303 integerPart low, mid, high, srcPart;
2305 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2307 This cannot overflow, because
2309 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2311 which is less than n^2. */
2315 if (multiplier == 0 || srcPart == 0) {
2319 low = lowHalf(srcPart) * lowHalf(multiplier);
2320 high = highHalf(srcPart) * highHalf(multiplier);
2322 mid = lowHalf(srcPart) * highHalf(multiplier);
2323 high += highHalf(mid);
2324 mid <<= integerPartWidth / 2;
2325 if (low + mid < low)
2329 mid = highHalf(srcPart) * lowHalf(multiplier);
2330 high += highHalf(mid);
2331 mid <<= integerPartWidth / 2;
2332 if (low + mid < low)
2336 /* Now add carry. */
2337 if (low + carry < low)
2343 /* And now DST[i], and store the new low part there. */
2344 if (low + dst[i] < low)
2354 /* Full multiplication, there is no overflow. */
2355 assert(i + 1 == dstParts);
2359 /* We overflowed if there is carry. */
2363 /* We would overflow if any significant unwritten parts would be
2364 non-zero. This is true if any remaining src parts are non-zero
2365 and the multiplier is non-zero. */
2367 for(; i < srcParts; i++)
2371 /* We fitted in the narrow destination. */
2376 /* DST = LHS * RHS, where DST has the same width as the operands and
2377 is filled with the least significant parts of the result. Returns
2378 one if overflow occurred, otherwise zero. DST must be disjoint
2379 from both operands. */
2381 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2382 const integerPart *rhs, unsigned int parts)
2387 assert(dst != lhs && dst != rhs);
2390 tcSet(dst, 0, parts);
2392 for(i = 0; i < parts; i++)
2393 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2399 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2400 operands. No overflow occurs. DST must be disjoint from both
2401 operands. Returns the number of parts required to hold the
2404 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2405 const integerPart *rhs, unsigned int lhsParts,
2406 unsigned int rhsParts)
2408 /* Put the narrower number on the LHS for less loops below. */
2409 if (lhsParts > rhsParts) {
2410 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2414 assert(dst != lhs && dst != rhs);
2416 tcSet(dst, 0, rhsParts);
2418 for(n = 0; n < lhsParts; n++)
2419 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2421 n = lhsParts + rhsParts;
2423 return n - (dst[n - 1] == 0);
2427 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2428 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2429 set REMAINDER to the remainder, return zero. i.e.
2431 OLD_LHS = RHS * LHS + REMAINDER
2433 SCRATCH is a bignum of the same size as the operands and result for
2434 use by the routine; its contents need not be initialized and are
2435 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2438 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2439 integerPart *remainder, integerPart *srhs,
2442 unsigned int n, shiftCount;
2445 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2447 shiftCount = tcMSB(rhs, parts) + 1;
2448 if (shiftCount == 0)
2451 shiftCount = parts * integerPartWidth - shiftCount;
2452 n = shiftCount / integerPartWidth;
2453 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2455 tcAssign(srhs, rhs, parts);
2456 tcShiftLeft(srhs, parts, shiftCount);
2457 tcAssign(remainder, lhs, parts);
2458 tcSet(lhs, 0, parts);
2460 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2465 compare = tcCompare(remainder, srhs, parts);
2467 tcSubtract(remainder, srhs, 0, parts);
2471 if (shiftCount == 0)
2474 tcShiftRight(srhs, parts, 1);
2475 if ((mask >>= 1) == 0)
2476 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2482 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2483 There are no restrictions on COUNT. */
2485 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2488 unsigned int jump, shift;
2490 /* Jump is the inter-part jump; shift is is intra-part shift. */
2491 jump = count / integerPartWidth;
2492 shift = count % integerPartWidth;
2494 while (parts > jump) {
2499 /* dst[i] comes from the two parts src[i - jump] and, if we have
2500 an intra-part shift, src[i - jump - 1]. */
2501 part = dst[parts - jump];
2504 if (parts >= jump + 1)
2505 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2516 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2517 zero. There are no restrictions on COUNT. */
2519 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2522 unsigned int i, jump, shift;
2524 /* Jump is the inter-part jump; shift is is intra-part shift. */
2525 jump = count / integerPartWidth;
2526 shift = count % integerPartWidth;
2528 /* Perform the shift. This leaves the most significant COUNT bits
2529 of the result at zero. */
2530 for(i = 0; i < parts; i++) {
2533 if (i + jump >= parts) {
2536 part = dst[i + jump];
2539 if (i + jump + 1 < parts)
2540 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2549 /* Bitwise and of two bignums. */
2551 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2555 for(i = 0; i < parts; i++)
2559 /* Bitwise inclusive or of two bignums. */
2561 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2565 for(i = 0; i < parts; i++)
2569 /* Bitwise exclusive or of two bignums. */
2571 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2575 for(i = 0; i < parts; i++)
2579 /* Complement a bignum in-place. */
2581 APInt::tcComplement(integerPart *dst, unsigned int parts)
2585 for(i = 0; i < parts; i++)
2589 /* Comparison (unsigned) of two bignums. */
2591 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2596 if (lhs[parts] == rhs[parts])
2599 if (lhs[parts] > rhs[parts])
2608 /* Increment a bignum in-place, return the carry flag. */
2610 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2614 for(i = 0; i < parts; i++)
2621 /* Set the least significant BITS bits of a bignum, clear the
2624 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2630 while (bits > integerPartWidth) {
2631 dst[i++] = ~(integerPart) 0;
2632 bits -= integerPartWidth;
2636 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);