1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Sheng Zhou and is distributed under the
6 // University of Illinois Open Source 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/DerivedTypes.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/MathExtras.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(uint32_t 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(uint32_t numWords) {
40 uint64_t * result = new uint64_t[numWords];
41 assert(result && "APInt memory allocation fails!");
45 APInt::APInt(uint32_t numBits, uint64_t val, bool isSigned)
46 : BitWidth(numBits), VAL(0) {
47 assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
48 assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
52 pVal = getClearedMemory(getNumWords());
54 if (isSigned && int64_t(val) < 0)
55 for (unsigned i = 1; i < getNumWords(); ++i)
61 APInt::APInt(uint32_t numBits, uint32_t numWords, const uint64_t bigVal[])
62 : BitWidth(numBits), VAL(0) {
63 assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
64 assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
65 assert(bigVal && "Null pointer detected!");
69 // Get memory, cleared to 0
70 pVal = getClearedMemory(getNumWords());
71 // Calculate the number of words to copy
72 uint32_t words = std::min<uint32_t>(numWords, getNumWords());
73 // Copy the words from bigVal to pVal
74 memcpy(pVal, bigVal, words * APINT_WORD_SIZE);
76 // Make sure unused high bits are cleared
80 APInt::APInt(uint32_t numbits, const char StrStart[], uint32_t slen,
82 : BitWidth(numbits), VAL(0) {
83 assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
84 assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
85 fromString(numbits, StrStart, slen, radix);
88 APInt::APInt(uint32_t numbits, const std::string& Val, uint8_t radix)
89 : BitWidth(numbits), VAL(0) {
90 assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
91 assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
92 assert(!Val.empty() && "String empty?");
93 fromString(numbits, Val.c_str(), Val.size(), radix);
96 APInt::APInt(const APInt& that)
97 : BitWidth(that.BitWidth), VAL(0) {
98 assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
99 assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
103 pVal = getMemory(getNumWords());
104 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
109 if (!isSingleWord() && pVal)
113 APInt& APInt::operator=(const APInt& RHS) {
114 // Don't do anything for X = X
118 // If the bitwidths are the same, we can avoid mucking with memory
119 if (BitWidth == RHS.getBitWidth()) {
123 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
128 if (RHS.isSingleWord())
132 pVal = getMemory(RHS.getNumWords());
133 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
135 else if (getNumWords() == RHS.getNumWords())
136 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
137 else if (RHS.isSingleWord()) {
142 pVal = getMemory(RHS.getNumWords());
143 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
145 BitWidth = RHS.BitWidth;
146 return clearUnusedBits();
149 APInt& APInt::operator=(uint64_t RHS) {
154 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
156 return clearUnusedBits();
159 /// add_1 - This function adds a single "digit" integer, y, to the multiple
160 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
161 /// 1 is returned if there is a carry out, otherwise 0 is returned.
162 /// @returns the carry of the addition.
163 static bool add_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
164 for (uint32_t i = 0; i < len; ++i) {
167 y = 1; // Carry one to next digit.
169 y = 0; // No need to carry so exit early
176 /// @brief Prefix increment operator. Increments the APInt by one.
177 APInt& APInt::operator++() {
181 add_1(pVal, pVal, getNumWords(), 1);
182 return clearUnusedBits();
185 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
186 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
187 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
188 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
189 /// In other words, if y > x then this function returns 1, otherwise 0.
190 /// @returns the borrow out of the subtraction
191 static bool sub_1(uint64_t x[], uint32_t len, uint64_t y) {
192 for (uint32_t i = 0; i < len; ++i) {
196 y = 1; // We have to "borrow 1" from next "digit"
198 y = 0; // No need to borrow
199 break; // Remaining digits are unchanged so exit early
205 /// @brief Prefix decrement operator. Decrements the APInt by one.
206 APInt& APInt::operator--() {
210 sub_1(pVal, getNumWords(), 1);
211 return clearUnusedBits();
214 /// add - This function adds the integer array x to the integer array Y and
215 /// places the result in dest.
216 /// @returns the carry out from the addition
217 /// @brief General addition of 64-bit integer arrays
218 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
221 for (uint32_t i = 0; i< len; ++i) {
222 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
223 dest[i] = x[i] + y[i] + carry;
224 carry = dest[i] < limit || (carry && dest[i] == limit);
229 /// Adds the RHS APint to this APInt.
230 /// @returns this, after addition of RHS.
231 /// @brief Addition assignment operator.
232 APInt& APInt::operator+=(const APInt& RHS) {
233 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
237 add(pVal, pVal, RHS.pVal, getNumWords());
239 return clearUnusedBits();
242 /// Subtracts the integer array y from the integer array x
243 /// @returns returns the borrow out.
244 /// @brief Generalized subtraction of 64-bit integer arrays.
245 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
248 for (uint32_t i = 0; i < len; ++i) {
249 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
250 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
251 dest[i] = x_tmp - y[i];
256 /// Subtracts the RHS APInt from this APInt
257 /// @returns this, after subtraction
258 /// @brief Subtraction assignment operator.
259 APInt& APInt::operator-=(const APInt& RHS) {
260 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
264 sub(pVal, pVal, RHS.pVal, getNumWords());
265 return clearUnusedBits();
268 /// Multiplies an integer array, x by a a uint64_t integer and places the result
270 /// @returns the carry out of the multiplication.
271 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
272 static uint64_t mul_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
273 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
274 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
277 // For each digit of x.
278 for (uint32_t i = 0; i < len; ++i) {
279 // Split x into high and low words
280 uint64_t lx = x[i] & 0xffffffffULL;
281 uint64_t hx = x[i] >> 32;
282 // hasCarry - A flag to indicate if there is a carry to the next digit.
283 // hasCarry == 0, no carry
284 // hasCarry == 1, has carry
285 // hasCarry == 2, no carry and the calculation result == 0.
286 uint8_t hasCarry = 0;
287 dest[i] = carry + lx * ly;
288 // Determine if the add above introduces carry.
289 hasCarry = (dest[i] < carry) ? 1 : 0;
290 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
291 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
292 // (2^32 - 1) + 2^32 = 2^64.
293 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
295 carry += (lx * hy) & 0xffffffffULL;
296 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
297 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
298 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
303 /// Multiplies integer array x by integer array y and stores the result into
304 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
305 /// @brief Generalized multiplicate of integer arrays.
306 static void mul(uint64_t dest[], uint64_t x[], uint32_t xlen, uint64_t y[],
308 dest[xlen] = mul_1(dest, x, xlen, y[0]);
309 for (uint32_t i = 1; i < ylen; ++i) {
310 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
311 uint64_t carry = 0, lx = 0, hx = 0;
312 for (uint32_t j = 0; j < xlen; ++j) {
313 lx = x[j] & 0xffffffffULL;
315 // hasCarry - A flag to indicate if has carry.
316 // hasCarry == 0, no carry
317 // hasCarry == 1, has carry
318 // hasCarry == 2, no carry and the calculation result == 0.
319 uint8_t hasCarry = 0;
320 uint64_t resul = carry + lx * ly;
321 hasCarry = (resul < carry) ? 1 : 0;
322 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
323 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
325 carry += (lx * hy) & 0xffffffffULL;
326 resul = (carry << 32) | (resul & 0xffffffffULL);
328 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
329 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
330 ((lx * hy) >> 32) + hx * hy;
332 dest[i+xlen] = carry;
336 APInt& APInt::operator*=(const APInt& RHS) {
337 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
338 if (isSingleWord()) {
344 // Get some bit facts about LHS and check for zero
345 uint32_t lhsBits = getActiveBits();
346 uint32_t lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
351 // Get some bit facts about RHS and check for zero
352 uint32_t rhsBits = RHS.getActiveBits();
353 uint32_t rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
360 // Allocate space for the result
361 uint32_t destWords = rhsWords + lhsWords;
362 uint64_t *dest = getMemory(destWords);
364 // Perform the long multiply
365 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
367 // Copy result back into *this
369 uint32_t wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
370 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
372 // delete dest array and return
377 APInt& APInt::operator&=(const APInt& RHS) {
378 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
379 if (isSingleWord()) {
383 uint32_t numWords = getNumWords();
384 for (uint32_t i = 0; i < numWords; ++i)
385 pVal[i] &= RHS.pVal[i];
389 APInt& APInt::operator|=(const APInt& RHS) {
390 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
391 if (isSingleWord()) {
395 uint32_t numWords = getNumWords();
396 for (uint32_t i = 0; i < numWords; ++i)
397 pVal[i] |= RHS.pVal[i];
401 APInt& APInt::operator^=(const APInt& RHS) {
402 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
403 if (isSingleWord()) {
405 this->clearUnusedBits();
408 uint32_t numWords = getNumWords();
409 for (uint32_t i = 0; i < numWords; ++i)
410 pVal[i] ^= RHS.pVal[i];
411 return clearUnusedBits();
414 APInt APInt::operator&(const APInt& RHS) const {
415 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
417 return APInt(getBitWidth(), VAL & RHS.VAL);
419 uint32_t numWords = getNumWords();
420 uint64_t* val = getMemory(numWords);
421 for (uint32_t i = 0; i < numWords; ++i)
422 val[i] = pVal[i] & RHS.pVal[i];
423 return APInt(val, getBitWidth());
426 APInt APInt::operator|(const APInt& RHS) const {
427 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
429 return APInt(getBitWidth(), VAL | RHS.VAL);
431 uint32_t numWords = getNumWords();
432 uint64_t *val = getMemory(numWords);
433 for (uint32_t i = 0; i < numWords; ++i)
434 val[i] = pVal[i] | RHS.pVal[i];
435 return APInt(val, getBitWidth());
438 APInt APInt::operator^(const APInt& RHS) const {
439 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
441 return APInt(BitWidth, VAL ^ RHS.VAL);
443 uint32_t numWords = getNumWords();
444 uint64_t *val = getMemory(numWords);
445 for (uint32_t i = 0; i < numWords; ++i)
446 val[i] = pVal[i] ^ RHS.pVal[i];
448 // 0^0==1 so clear the high bits in case they got set.
449 return APInt(val, getBitWidth()).clearUnusedBits();
452 bool APInt::operator !() const {
456 for (uint32_t i = 0; i < getNumWords(); ++i)
462 APInt APInt::operator*(const APInt& RHS) const {
463 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
465 return APInt(BitWidth, VAL * RHS.VAL);
468 return Result.clearUnusedBits();
471 APInt APInt::operator+(const APInt& RHS) const {
472 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
474 return APInt(BitWidth, VAL + RHS.VAL);
475 APInt Result(BitWidth, 0);
476 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
477 return Result.clearUnusedBits();
480 APInt APInt::operator-(const APInt& RHS) const {
481 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
483 return APInt(BitWidth, VAL - RHS.VAL);
484 APInt Result(BitWidth, 0);
485 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
486 return Result.clearUnusedBits();
489 bool APInt::operator[](uint32_t bitPosition) const {
490 return (maskBit(bitPosition) &
491 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
494 bool APInt::operator==(const APInt& RHS) const {
495 assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
497 return VAL == RHS.VAL;
499 // Get some facts about the number of bits used in the two operands.
500 uint32_t n1 = getActiveBits();
501 uint32_t n2 = RHS.getActiveBits();
503 // If the number of bits isn't the same, they aren't equal
507 // If the number of bits fits in a word, we only need to compare the low word.
508 if (n1 <= APINT_BITS_PER_WORD)
509 return pVal[0] == RHS.pVal[0];
511 // Otherwise, compare everything
512 for (int i = whichWord(n1 - 1); i >= 0; --i)
513 if (pVal[i] != RHS.pVal[i])
518 bool APInt::operator==(uint64_t Val) const {
522 uint32_t n = getActiveBits();
523 if (n <= APINT_BITS_PER_WORD)
524 return pVal[0] == Val;
529 bool APInt::ult(const APInt& RHS) const {
530 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
532 return VAL < RHS.VAL;
534 // Get active bit length of both operands
535 uint32_t n1 = getActiveBits();
536 uint32_t n2 = RHS.getActiveBits();
538 // If magnitude of LHS is less than RHS, return true.
542 // If magnitude of RHS is greather than LHS, return false.
546 // If they bot fit in a word, just compare the low order word
547 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
548 return pVal[0] < RHS.pVal[0];
550 // Otherwise, compare all words
551 uint32_t topWord = whichWord(std::max(n1,n2)-1);
552 for (int i = topWord; i >= 0; --i) {
553 if (pVal[i] > RHS.pVal[i])
555 if (pVal[i] < RHS.pVal[i])
561 bool APInt::slt(const APInt& RHS) const {
562 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
563 if (isSingleWord()) {
564 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
565 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
566 return lhsSext < rhsSext;
571 bool lhsNeg = isNegative();
572 bool rhsNeg = rhs.isNegative();
574 // Sign bit is set so perform two's complement to make it positive
579 // Sign bit is set so perform two's complement to make it positive
584 // Now we have unsigned values to compare so do the comparison if necessary
585 // based on the negativeness of the values.
597 APInt& APInt::set(uint32_t bitPosition) {
599 VAL |= maskBit(bitPosition);
601 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
605 APInt& APInt::set() {
606 if (isSingleWord()) {
608 return clearUnusedBits();
611 // Set all the bits in all the words.
612 for (uint32_t i = 0; i < getNumWords(); ++i)
614 // Clear the unused ones
615 return clearUnusedBits();
618 /// Set the given bit to 0 whose position is given as "bitPosition".
619 /// @brief Set a given bit to 0.
620 APInt& APInt::clear(uint32_t bitPosition) {
622 VAL &= ~maskBit(bitPosition);
624 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
628 /// @brief Set every bit to 0.
629 APInt& APInt::clear() {
633 memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
637 /// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on
639 APInt APInt::operator~() const {
645 /// @brief Toggle every bit to its opposite value.
646 APInt& APInt::flip() {
647 if (isSingleWord()) {
649 return clearUnusedBits();
651 for (uint32_t i = 0; i < getNumWords(); ++i)
653 return clearUnusedBits();
656 /// Toggle a given bit to its opposite value whose position is given
657 /// as "bitPosition".
658 /// @brief Toggles a given bit to its opposite value.
659 APInt& APInt::flip(uint32_t bitPosition) {
660 assert(bitPosition < BitWidth && "Out of the bit-width range!");
661 if ((*this)[bitPosition]) clear(bitPosition);
662 else set(bitPosition);
666 uint32_t APInt::getBitsNeeded(const char* str, uint32_t slen, uint8_t radix) {
667 assert(str != 0 && "Invalid value string");
668 assert(slen > 0 && "Invalid string length");
670 // Each computation below needs to know if its negative
671 uint32_t isNegative = str[0] == '-';
676 // For radixes of power-of-two values, the bits required is accurately and
679 return slen + isNegative;
681 return slen * 3 + isNegative;
683 return slen * 4 + isNegative;
685 // Otherwise it must be radix == 10, the hard case
686 assert(radix == 10 && "Invalid radix");
688 // This is grossly inefficient but accurate. We could probably do something
689 // with a computation of roughly slen*64/20 and then adjust by the value of
690 // the first few digits. But, I'm not sure how accurate that could be.
692 // Compute a sufficient number of bits that is always large enough but might
693 // be too large. This avoids the assertion in the constructor.
694 uint32_t sufficient = slen*64/18;
696 // Convert to the actual binary value.
697 APInt tmp(sufficient, str, slen, radix);
699 // Compute how many bits are required.
700 return isNegative + tmp.logBase2() + 1;
703 uint64_t APInt::getHashValue() const {
704 // Put the bit width into the low order bits.
705 uint64_t hash = BitWidth;
707 // Add the sum of the words to the hash.
709 hash += VAL << 6; // clear separation of up to 64 bits
711 for (uint32_t i = 0; i < getNumWords(); ++i)
712 hash += pVal[i] << 6; // clear sepration of up to 64 bits
716 /// HiBits - This function returns the high "numBits" bits of this APInt.
717 APInt APInt::getHiBits(uint32_t numBits) const {
718 return APIntOps::lshr(*this, BitWidth - numBits);
721 /// LoBits - This function returns the low "numBits" bits of this APInt.
722 APInt APInt::getLoBits(uint32_t numBits) const {
723 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
727 bool APInt::isPowerOf2() const {
728 return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
731 uint32_t APInt::countLeadingZeros() const {
734 Count = CountLeadingZeros_64(VAL);
736 for (uint32_t i = getNumWords(); i > 0u; --i) {
738 Count += APINT_BITS_PER_WORD;
740 Count += CountLeadingZeros_64(pVal[i-1]);
745 uint32_t remainder = BitWidth % APINT_BITS_PER_WORD;
747 Count -= APINT_BITS_PER_WORD - remainder;
751 static uint32_t countLeadingOnes_64(uint64_t V, uint32_t skip) {
755 while (V && (V & (1ULL << 63))) {
762 uint32_t APInt::countLeadingOnes() const {
764 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
766 uint32_t highWordBits = BitWidth % APINT_BITS_PER_WORD;
767 uint32_t shift = (highWordBits == 0 ? 0 : APINT_BITS_PER_WORD - highWordBits);
768 int i = getNumWords() - 1;
769 uint32_t Count = countLeadingOnes_64(pVal[i], shift);
770 if (Count == highWordBits) {
771 for (i--; i >= 0; --i) {
772 if (pVal[i] == -1ULL)
773 Count += APINT_BITS_PER_WORD;
775 Count += countLeadingOnes_64(pVal[i], 0);
783 uint32_t APInt::countTrailingZeros() const {
785 return CountTrailingZeros_64(VAL);
788 for (; i < getNumWords() && pVal[i] == 0; ++i)
789 Count += APINT_BITS_PER_WORD;
790 if (i < getNumWords())
791 Count += CountTrailingZeros_64(pVal[i]);
795 uint32_t APInt::countPopulation() const {
797 return CountPopulation_64(VAL);
799 for (uint32_t i = 0; i < getNumWords(); ++i)
800 Count += CountPopulation_64(pVal[i]);
804 APInt APInt::byteSwap() const {
805 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
807 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
808 else if (BitWidth == 32)
809 return APInt(BitWidth, ByteSwap_32(uint32_t(VAL)));
810 else if (BitWidth == 48) {
811 uint32_t Tmp1 = uint32_t(VAL >> 16);
812 Tmp1 = ByteSwap_32(Tmp1);
813 uint16_t Tmp2 = uint16_t(VAL);
814 Tmp2 = ByteSwap_16(Tmp2);
815 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
816 } else if (BitWidth == 64)
817 return APInt(BitWidth, ByteSwap_64(VAL));
819 APInt Result(BitWidth, 0);
820 char *pByte = (char*)Result.pVal;
821 for (uint32_t i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
823 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
824 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
830 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
832 APInt A = API1, B = API2;
835 B = APIntOps::urem(A, B);
841 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) {
848 // Get the sign bit from the highest order bit
849 bool isNeg = T.I >> 63;
851 // Get the 11-bit exponent and adjust for the 1023 bit bias
852 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
854 // If the exponent is negative, the value is < 0 so just return 0.
856 return APInt(width, 0u);
858 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
859 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
861 // If the exponent doesn't shift all bits out of the mantissa
863 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
864 APInt(width, mantissa >> (52 - exp));
866 // If the client didn't provide enough bits for us to shift the mantissa into
867 // then the result is undefined, just return 0
868 if (width <= exp - 52)
869 return APInt(width, 0);
871 // Otherwise, we have to shift the mantissa bits up to the right location
872 APInt Tmp(width, mantissa);
873 Tmp = Tmp.shl(exp - 52);
874 return isNeg ? -Tmp : Tmp;
877 /// RoundToDouble - This function convert this APInt to a double.
878 /// The layout for double is as following (IEEE Standard 754):
879 /// --------------------------------------
880 /// | Sign Exponent Fraction Bias |
881 /// |-------------------------------------- |
882 /// | 1[63] 11[62-52] 52[51-00] 1023 |
883 /// --------------------------------------
884 double APInt::roundToDouble(bool isSigned) const {
886 // Handle the simple case where the value is contained in one uint64_t.
887 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
889 int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
895 // Determine if the value is negative.
896 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
898 // Construct the absolute value if we're negative.
899 APInt Tmp(isNeg ? -(*this) : (*this));
901 // Figure out how many bits we're using.
902 uint32_t n = Tmp.getActiveBits();
904 // The exponent (without bias normalization) is just the number of bits
905 // we are using. Note that the sign bit is gone since we constructed the
909 // Return infinity for exponent overflow
911 if (!isSigned || !isNeg)
912 return std::numeric_limits<double>::infinity();
914 return -std::numeric_limits<double>::infinity();
916 exp += 1023; // Increment for 1023 bias
918 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
919 // extract the high 52 bits from the correct words in pVal.
921 unsigned hiWord = whichWord(n-1);
923 mantissa = Tmp.pVal[0];
925 mantissa >>= n - 52; // shift down, we want the top 52 bits.
927 assert(hiWord > 0 && "huh?");
928 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
929 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
930 mantissa = hibits | lobits;
933 // The leading bit of mantissa is implicit, so get rid of it.
934 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
939 T.I = sign | (exp << 52) | mantissa;
943 // Truncate to new width.
944 APInt &APInt::trunc(uint32_t width) {
945 assert(width < BitWidth && "Invalid APInt Truncate request");
946 assert(width >= IntegerType::MIN_INT_BITS && "Can't truncate to 0 bits");
947 uint32_t wordsBefore = getNumWords();
949 uint32_t wordsAfter = getNumWords();
950 if (wordsBefore != wordsAfter) {
951 if (wordsAfter == 1) {
952 uint64_t *tmp = pVal;
956 uint64_t *newVal = getClearedMemory(wordsAfter);
957 for (uint32_t i = 0; i < wordsAfter; ++i)
963 return clearUnusedBits();
966 // Sign extend to a new width.
967 APInt &APInt::sext(uint32_t width) {
968 assert(width > BitWidth && "Invalid APInt SignExtend request");
969 assert(width <= IntegerType::MAX_INT_BITS && "Too many bits");
970 // If the sign bit isn't set, this is the same as zext.
976 // The sign bit is set. First, get some facts
977 uint32_t wordsBefore = getNumWords();
978 uint32_t wordBits = BitWidth % APINT_BITS_PER_WORD;
980 uint32_t wordsAfter = getNumWords();
982 // Mask the high order word appropriately
983 if (wordsBefore == wordsAfter) {
984 uint32_t newWordBits = width % APINT_BITS_PER_WORD;
985 // The extension is contained to the wordsBefore-1th word.
986 uint64_t mask = ~0ULL;
988 mask >>= APINT_BITS_PER_WORD - newWordBits;
990 if (wordsBefore == 1)
993 pVal[wordsBefore-1] |= mask;
994 return clearUnusedBits();
997 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
998 uint64_t *newVal = getMemory(wordsAfter);
999 if (wordsBefore == 1)
1000 newVal[0] = VAL | mask;
1002 for (uint32_t i = 0; i < wordsBefore; ++i)
1003 newVal[i] = pVal[i];
1004 newVal[wordsBefore-1] |= mask;
1006 for (uint32_t i = wordsBefore; i < wordsAfter; i++)
1008 if (wordsBefore != 1)
1011 return clearUnusedBits();
1014 // Zero extend to a new width.
1015 APInt &APInt::zext(uint32_t width) {
1016 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1017 assert(width <= IntegerType::MAX_INT_BITS && "Too many bits");
1018 uint32_t wordsBefore = getNumWords();
1020 uint32_t wordsAfter = getNumWords();
1021 if (wordsBefore != wordsAfter) {
1022 uint64_t *newVal = getClearedMemory(wordsAfter);
1023 if (wordsBefore == 1)
1026 for (uint32_t i = 0; i < wordsBefore; ++i)
1027 newVal[i] = pVal[i];
1028 if (wordsBefore != 1)
1035 APInt &APInt::zextOrTrunc(uint32_t width) {
1036 if (BitWidth < width)
1038 if (BitWidth > width)
1039 return trunc(width);
1043 APInt &APInt::sextOrTrunc(uint32_t width) {
1044 if (BitWidth < width)
1046 if (BitWidth > width)
1047 return trunc(width);
1051 /// Arithmetic right-shift this APInt by shiftAmt.
1052 /// @brief Arithmetic right-shift function.
1053 APInt APInt::ashr(uint32_t shiftAmt) const {
1054 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1055 // Handle a degenerate case
1059 // Handle single word shifts with built-in ashr
1060 if (isSingleWord()) {
1061 if (shiftAmt == BitWidth)
1062 return APInt(BitWidth, 0); // undefined
1064 uint32_t SignBit = APINT_BITS_PER_WORD - BitWidth;
1065 return APInt(BitWidth,
1066 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1070 // If all the bits were shifted out, the result is, technically, undefined.
1071 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1072 // issues in the algorithm below.
1073 if (shiftAmt == BitWidth) {
1075 return APInt(BitWidth, -1ULL);
1077 return APInt(BitWidth, 0);
1080 // Create some space for the result.
1081 uint64_t * val = new uint64_t[getNumWords()];
1083 // Compute some values needed by the following shift algorithms
1084 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1085 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1086 uint32_t breakWord = getNumWords() - 1 - offset; // last word affected
1087 uint32_t bitsInWord = whichBit(BitWidth); // how many bits in last word?
1088 if (bitsInWord == 0)
1089 bitsInWord = APINT_BITS_PER_WORD;
1091 // If we are shifting whole words, just move whole words
1092 if (wordShift == 0) {
1093 // Move the words containing significant bits
1094 for (uint32_t i = 0; i <= breakWord; ++i)
1095 val[i] = pVal[i+offset]; // move whole word
1097 // Adjust the top significant word for sign bit fill, if negative
1099 if (bitsInWord < APINT_BITS_PER_WORD)
1100 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1102 // Shift the low order words
1103 for (uint32_t i = 0; i < breakWord; ++i) {
1104 // This combines the shifted corresponding word with the low bits from
1105 // the next word (shifted into this word's high bits).
1106 val[i] = (pVal[i+offset] >> wordShift) |
1107 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1110 // Shift the break word. In this case there are no bits from the next word
1111 // to include in this word.
1112 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1114 // Deal with sign extenstion in the break word, and possibly the word before
1117 if (wordShift > bitsInWord) {
1120 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1121 val[breakWord] |= ~0ULL;
1123 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1127 // Remaining words are 0 or -1, just assign them.
1128 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1129 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1131 return APInt(val, BitWidth).clearUnusedBits();
1134 /// Logical right-shift this APInt by shiftAmt.
1135 /// @brief Logical right-shift function.
1136 APInt APInt::lshr(uint32_t shiftAmt) const {
1137 if (isSingleWord()) {
1138 if (shiftAmt == BitWidth)
1139 return APInt(BitWidth, 0);
1141 return APInt(BitWidth, this->VAL >> shiftAmt);
1144 // If all the bits were shifted out, the result is 0. This avoids issues
1145 // with shifting by the size of the integer type, which produces undefined
1146 // results. We define these "undefined results" to always be 0.
1147 if (shiftAmt == BitWidth)
1148 return APInt(BitWidth, 0);
1150 // If none of the bits are shifted out, the result is *this. This avoids
1151 // issues with shifting byt he size of the integer type, which produces
1152 // undefined results in the code below. This is also an optimization.
1156 // Create some space for the result.
1157 uint64_t * val = new uint64_t[getNumWords()];
1159 // If we are shifting less than a word, compute the shift with a simple carry
1160 if (shiftAmt < APINT_BITS_PER_WORD) {
1162 for (int i = getNumWords()-1; i >= 0; --i) {
1163 val[i] = (pVal[i] >> shiftAmt) | carry;
1164 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1166 return APInt(val, BitWidth).clearUnusedBits();
1169 // Compute some values needed by the remaining shift algorithms
1170 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1171 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1173 // If we are shifting whole words, just move whole words
1174 if (wordShift == 0) {
1175 for (uint32_t i = 0; i < getNumWords() - offset; ++i)
1176 val[i] = pVal[i+offset];
1177 for (uint32_t i = getNumWords()-offset; i < getNumWords(); i++)
1179 return APInt(val,BitWidth).clearUnusedBits();
1182 // Shift the low order words
1183 uint32_t breakWord = getNumWords() - offset -1;
1184 for (uint32_t i = 0; i < breakWord; ++i)
1185 val[i] = (pVal[i+offset] >> wordShift) |
1186 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1187 // Shift the break word.
1188 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1190 // Remaining words are 0
1191 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1193 return APInt(val, BitWidth).clearUnusedBits();
1196 /// Left-shift this APInt by shiftAmt.
1197 /// @brief Left-shift function.
1198 APInt APInt::shl(uint32_t shiftAmt) const {
1199 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1200 if (isSingleWord()) {
1201 if (shiftAmt == BitWidth)
1202 return APInt(BitWidth, 0); // avoid undefined shift results
1203 return APInt(BitWidth, VAL << shiftAmt);
1206 // If all the bits were shifted out, the result is 0. This avoids issues
1207 // with shifting by the size of the integer type, which produces undefined
1208 // results. We define these "undefined results" to always be 0.
1209 if (shiftAmt == BitWidth)
1210 return APInt(BitWidth, 0);
1212 // If none of the bits are shifted out, the result is *this. This avoids a
1213 // lshr by the words size in the loop below which can produce incorrect
1214 // results. It also avoids the expensive computation below for a common case.
1218 // Create some space for the result.
1219 uint64_t * val = new uint64_t[getNumWords()];
1221 // If we are shifting less than a word, do it the easy way
1222 if (shiftAmt < APINT_BITS_PER_WORD) {
1224 for (uint32_t i = 0; i < getNumWords(); i++) {
1225 val[i] = pVal[i] << shiftAmt | carry;
1226 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1228 return APInt(val, BitWidth).clearUnusedBits();
1231 // Compute some values needed by the remaining shift algorithms
1232 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1233 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1235 // If we are shifting whole words, just move whole words
1236 if (wordShift == 0) {
1237 for (uint32_t i = 0; i < offset; i++)
1239 for (uint32_t i = offset; i < getNumWords(); i++)
1240 val[i] = pVal[i-offset];
1241 return APInt(val,BitWidth).clearUnusedBits();
1244 // Copy whole words from this to Result.
1245 uint32_t i = getNumWords() - 1;
1246 for (; i > offset; --i)
1247 val[i] = pVal[i-offset] << wordShift |
1248 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1249 val[offset] = pVal[0] << wordShift;
1250 for (i = 0; i < offset; ++i)
1252 return APInt(val, BitWidth).clearUnusedBits();
1255 APInt APInt::rotl(uint32_t rotateAmt) const {
1258 // Don't get too fancy, just use existing shift/or facilities
1262 lo.lshr(BitWidth - rotateAmt);
1266 APInt APInt::rotr(uint32_t rotateAmt) const {
1269 // Don't get too fancy, just use existing shift/or facilities
1273 hi.shl(BitWidth - rotateAmt);
1277 // Square Root - this method computes and returns the square root of "this".
1278 // Three mechanisms are used for computation. For small values (<= 5 bits),
1279 // a table lookup is done. This gets some performance for common cases. For
1280 // values using less than 52 bits, the value is converted to double and then
1281 // the libc sqrt function is called. The result is rounded and then converted
1282 // back to a uint64_t which is then used to construct the result. Finally,
1283 // the Babylonian method for computing square roots is used.
1284 APInt APInt::sqrt() const {
1286 // Determine the magnitude of the value.
1287 uint32_t magnitude = getActiveBits();
1289 // Use a fast table for some small values. This also gets rid of some
1290 // rounding errors in libc sqrt for small values.
1291 if (magnitude <= 5) {
1292 static const uint8_t results[32] = {
1295 /* 3- 6 */ 2, 2, 2, 2,
1296 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1297 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1298 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1301 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1304 // If the magnitude of the value fits in less than 52 bits (the precision of
1305 // an IEEE double precision floating point value), then we can use the
1306 // libc sqrt function which will probably use a hardware sqrt computation.
1307 // This should be faster than the algorithm below.
1308 if (magnitude < 52) {
1310 // Amazingly, VC++ doesn't have round().
1311 return APInt(BitWidth,
1312 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1314 return APInt(BitWidth,
1315 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1319 // Okay, all the short cuts are exhausted. We must compute it. The following
1320 // is a classical Babylonian method for computing the square root. This code
1321 // was adapted to APINt from a wikipedia article on such computations.
1322 // See http://www.wikipedia.org/ and go to the page named
1323 // Calculate_an_integer_square_root.
1324 uint32_t nbits = BitWidth, i = 4;
1325 APInt testy(BitWidth, 16);
1326 APInt x_old(BitWidth, 1);
1327 APInt x_new(BitWidth, 0);
1328 APInt two(BitWidth, 2);
1330 // Select a good starting value using binary logarithms.
1331 for (;; i += 2, testy = testy.shl(2))
1332 if (i >= nbits || this->ule(testy)) {
1333 x_old = x_old.shl(i / 2);
1337 // Use the Babylonian method to arrive at the integer square root:
1339 x_new = (this->udiv(x_old) + x_old).udiv(two);
1340 if (x_old.ule(x_new))
1345 // Make sure we return the closest approximation
1346 // NOTE: The rounding calculation below is correct. It will produce an
1347 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1348 // determined to be a rounding issue with pari/gp as it begins to use a
1349 // floating point representation after 192 bits. There are no discrepancies
1350 // between this algorithm and pari/gp for bit widths < 192 bits.
1351 APInt square(x_old * x_old);
1352 APInt nextSquare((x_old + 1) * (x_old +1));
1353 if (this->ult(square))
1355 else if (this->ule(nextSquare)) {
1356 APInt midpoint((nextSquare - square).udiv(two));
1357 APInt offset(*this - square);
1358 if (offset.ult(midpoint))
1363 assert(0 && "Error in APInt::sqrt computation");
1367 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1368 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1369 /// variables here have the same names as in the algorithm. Comments explain
1370 /// the algorithm and any deviation from it.
1371 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1372 uint32_t m, uint32_t n) {
1373 assert(u && "Must provide dividend");
1374 assert(v && "Must provide divisor");
1375 assert(q && "Must provide quotient");
1376 assert(u != v && u != q && v != q && "Must us different memory");
1377 assert(n>1 && "n must be > 1");
1379 // Knuth uses the value b as the base of the number system. In our case b
1380 // is 2^31 so we just set it to -1u.
1381 uint64_t b = uint64_t(1) << 32;
1383 DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n');
1384 DEBUG(cerr << "KnuthDiv: original:");
1385 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1386 DEBUG(cerr << " by");
1387 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1388 DEBUG(cerr << '\n');
1389 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1390 // u and v by d. Note that we have taken Knuth's advice here to use a power
1391 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1392 // 2 allows us to shift instead of multiply and it is easy to determine the
1393 // shift amount from the leading zeros. We are basically normalizing the u
1394 // and v so that its high bits are shifted to the top of v's range without
1395 // overflow. Note that this can require an extra word in u so that u must
1396 // be of length m+n+1.
1397 uint32_t shift = CountLeadingZeros_32(v[n-1]);
1398 uint32_t v_carry = 0;
1399 uint32_t u_carry = 0;
1401 for (uint32_t i = 0; i < m+n; ++i) {
1402 uint32_t u_tmp = u[i] >> (32 - shift);
1403 u[i] = (u[i] << shift) | u_carry;
1406 for (uint32_t i = 0; i < n; ++i) {
1407 uint32_t v_tmp = v[i] >> (32 - shift);
1408 v[i] = (v[i] << shift) | v_carry;
1413 DEBUG(cerr << "KnuthDiv: normal:");
1414 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1415 DEBUG(cerr << " by");
1416 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1417 DEBUG(cerr << '\n');
1419 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1422 DEBUG(cerr << "KnuthDiv: quotient digit #" << j << '\n');
1423 // D3. [Calculate q'.].
1424 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1425 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1426 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1427 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1428 // on v[n-2] determines at high speed most of the cases in which the trial
1429 // value qp is one too large, and it eliminates all cases where qp is two
1431 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1432 DEBUG(cerr << "KnuthDiv: dividend == " << dividend << '\n');
1433 uint64_t qp = dividend / v[n-1];
1434 uint64_t rp = dividend % v[n-1];
1435 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1438 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1441 DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1443 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1444 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1445 // consists of a simple multiplication by a one-place number, combined with
1448 for (uint32_t i = 0; i < n; ++i) {
1449 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1450 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1451 bool borrow = subtrahend > u_tmp;
1452 DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp
1453 << ", subtrahend == " << subtrahend
1454 << ", borrow = " << borrow << '\n');
1456 uint64_t result = u_tmp - subtrahend;
1458 u[k++] = result & (b-1); // subtract low word
1459 u[k++] = result >> 32; // subtract high word
1460 while (borrow && k <= m+n) { // deal with borrow to the left
1466 DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1469 DEBUG(cerr << "KnuthDiv: after subtraction:");
1470 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1471 DEBUG(cerr << '\n');
1472 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1473 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1474 // true value plus b**(n+1), namely as the b's complement of
1475 // the true value, and a "borrow" to the left should be remembered.
1478 bool carry = true; // true because b's complement is "complement + 1"
1479 for (uint32_t i = 0; i <= m+n; ++i) {
1480 u[i] = ~u[i] + carry; // b's complement
1481 carry = carry && u[i] == 0;
1484 DEBUG(cerr << "KnuthDiv: after complement:");
1485 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1486 DEBUG(cerr << '\n');
1488 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1489 // negative, go to step D6; otherwise go on to step D7.
1492 // D6. [Add back]. The probability that this step is necessary is very
1493 // small, on the order of only 2/b. Make sure that test data accounts for
1494 // this possibility. Decrease q[j] by 1
1496 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1497 // A carry will occur to the left of u[j+n], and it should be ignored
1498 // since it cancels with the borrow that occurred in D4.
1500 for (uint32_t i = 0; i < n; i++) {
1501 uint32_t limit = std::min(u[j+i],v[i]);
1502 u[j+i] += v[i] + carry;
1503 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1507 DEBUG(cerr << "KnuthDiv: after correction:");
1508 DEBUG(for (int i = m+n; i >=0; i--) cerr <<" " << u[i]);
1509 DEBUG(cerr << "\nKnuthDiv: digit result = " << q[j] << '\n');
1511 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1514 DEBUG(cerr << "KnuthDiv: quotient:");
1515 DEBUG(for (int i = m; i >=0; i--) cerr <<" " << q[i]);
1516 DEBUG(cerr << '\n');
1518 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1519 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1520 // compute the remainder (urem uses this).
1522 // The value d is expressed by the "shift" value above since we avoided
1523 // multiplication by d by using a shift left. So, all we have to do is
1524 // shift right here. In order to mak
1527 DEBUG(cerr << "KnuthDiv: remainder:");
1528 for (int i = n-1; i >= 0; i--) {
1529 r[i] = (u[i] >> shift) | carry;
1530 carry = u[i] << (32 - shift);
1531 DEBUG(cerr << " " << r[i]);
1534 for (int i = n-1; i >= 0; i--) {
1536 DEBUG(cerr << " " << r[i]);
1539 DEBUG(cerr << '\n');
1541 DEBUG(cerr << std::setbase(10) << '\n');
1544 void APInt::divide(const APInt LHS, uint32_t lhsWords,
1545 const APInt &RHS, uint32_t rhsWords,
1546 APInt *Quotient, APInt *Remainder)
1548 assert(lhsWords >= rhsWords && "Fractional result");
1550 // First, compose the values into an array of 32-bit words instead of
1551 // 64-bit words. This is a necessity of both the "short division" algorithm
1552 // and the the Knuth "classical algorithm" which requires there to be native
1553 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1554 // can't use 64-bit operands here because we don't have native results of
1555 // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't
1556 // work on large-endian machines.
1557 uint64_t mask = ~0ull >> (sizeof(uint32_t)*8);
1558 uint32_t n = rhsWords * 2;
1559 uint32_t m = (lhsWords * 2) - n;
1561 // Allocate space for the temporary values we need either on the stack, if
1562 // it will fit, or on the heap if it won't.
1563 uint32_t SPACE[128];
1568 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1571 Q = &SPACE[(m+n+1) + n];
1573 R = &SPACE[(m+n+1) + n + (m+n)];
1575 U = new uint32_t[m + n + 1];
1576 V = new uint32_t[n];
1577 Q = new uint32_t[m+n];
1579 R = new uint32_t[n];
1582 // Initialize the dividend
1583 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1584 for (unsigned i = 0; i < lhsWords; ++i) {
1585 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1586 U[i * 2] = tmp & mask;
1587 U[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1589 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1591 // Initialize the divisor
1592 memset(V, 0, (n)*sizeof(uint32_t));
1593 for (unsigned i = 0; i < rhsWords; ++i) {
1594 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1595 V[i * 2] = tmp & mask;
1596 V[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1599 // initialize the quotient and remainder
1600 memset(Q, 0, (m+n) * sizeof(uint32_t));
1602 memset(R, 0, n * sizeof(uint32_t));
1604 // Now, adjust m and n for the Knuth division. n is the number of words in
1605 // the divisor. m is the number of words by which the dividend exceeds the
1606 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1607 // contain any zero words or the Knuth algorithm fails.
1608 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1612 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1615 // If we're left with only a single word for the divisor, Knuth doesn't work
1616 // so we implement the short division algorithm here. This is much simpler
1617 // and faster because we are certain that we can divide a 64-bit quantity
1618 // by a 32-bit quantity at hardware speed and short division is simply a
1619 // series of such operations. This is just like doing short division but we
1620 // are using base 2^32 instead of base 10.
1621 assert(n != 0 && "Divide by zero?");
1623 uint32_t divisor = V[0];
1624 uint32_t remainder = 0;
1625 for (int i = m+n-1; i >= 0; i--) {
1626 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1627 if (partial_dividend == 0) {
1630 } else if (partial_dividend < divisor) {
1632 remainder = partial_dividend;
1633 } else if (partial_dividend == divisor) {
1637 Q[i] = partial_dividend / divisor;
1638 remainder = partial_dividend - (Q[i] * divisor);
1644 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1646 KnuthDiv(U, V, Q, R, m, n);
1649 // If the caller wants the quotient
1651 // Set up the Quotient value's memory.
1652 if (Quotient->BitWidth != LHS.BitWidth) {
1653 if (Quotient->isSingleWord())
1656 delete [] Quotient->pVal;
1657 Quotient->BitWidth = LHS.BitWidth;
1658 if (!Quotient->isSingleWord())
1659 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1663 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1665 if (lhsWords == 1) {
1667 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1668 if (Quotient->isSingleWord())
1669 Quotient->VAL = tmp;
1671 Quotient->pVal[0] = tmp;
1673 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1674 for (unsigned i = 0; i < lhsWords; ++i)
1676 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1680 // If the caller wants the remainder
1682 // Set up the Remainder value's memory.
1683 if (Remainder->BitWidth != RHS.BitWidth) {
1684 if (Remainder->isSingleWord())
1687 delete [] Remainder->pVal;
1688 Remainder->BitWidth = RHS.BitWidth;
1689 if (!Remainder->isSingleWord())
1690 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1694 // The remainder is in R. Reconstitute the remainder into Remainder's low
1696 if (rhsWords == 1) {
1698 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1699 if (Remainder->isSingleWord())
1700 Remainder->VAL = tmp;
1702 Remainder->pVal[0] = tmp;
1704 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1705 for (unsigned i = 0; i < rhsWords; ++i)
1706 Remainder->pVal[i] =
1707 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1711 // Clean up the memory we allocated.
1712 if (U != &SPACE[0]) {
1720 APInt APInt::udiv(const APInt& RHS) const {
1721 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1723 // First, deal with the easy case
1724 if (isSingleWord()) {
1725 assert(RHS.VAL != 0 && "Divide by zero?");
1726 return APInt(BitWidth, VAL / RHS.VAL);
1729 // Get some facts about the LHS and RHS number of bits and words
1730 uint32_t rhsBits = RHS.getActiveBits();
1731 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1732 assert(rhsWords && "Divided by zero???");
1733 uint32_t lhsBits = this->getActiveBits();
1734 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1736 // Deal with some degenerate cases
1739 return APInt(BitWidth, 0);
1740 else if (lhsWords < rhsWords || this->ult(RHS)) {
1741 // X / Y ===> 0, iff X < Y
1742 return APInt(BitWidth, 0);
1743 } else if (*this == RHS) {
1745 return APInt(BitWidth, 1);
1746 } else if (lhsWords == 1 && rhsWords == 1) {
1747 // All high words are zero, just use native divide
1748 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1751 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1752 APInt Quotient(1,0); // to hold result.
1753 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1757 APInt APInt::urem(const APInt& RHS) const {
1758 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1759 if (isSingleWord()) {
1760 assert(RHS.VAL != 0 && "Remainder by zero?");
1761 return APInt(BitWidth, VAL % RHS.VAL);
1764 // Get some facts about the LHS
1765 uint32_t lhsBits = getActiveBits();
1766 uint32_t lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1768 // Get some facts about the RHS
1769 uint32_t rhsBits = RHS.getActiveBits();
1770 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1771 assert(rhsWords && "Performing remainder operation by zero ???");
1773 // Check the degenerate cases
1774 if (lhsWords == 0) {
1776 return APInt(BitWidth, 0);
1777 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1778 // X % Y ===> X, iff X < Y
1780 } else if (*this == RHS) {
1782 return APInt(BitWidth, 0);
1783 } else if (lhsWords == 1) {
1784 // All high words are zero, just use native remainder
1785 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1788 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1789 APInt Remainder(1,0);
1790 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1794 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1795 APInt &Quotient, APInt &Remainder) {
1796 // Get some size facts about the dividend and divisor
1797 uint32_t lhsBits = LHS.getActiveBits();
1798 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1799 uint32_t rhsBits = RHS.getActiveBits();
1800 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1802 // Check the degenerate cases
1803 if (lhsWords == 0) {
1804 Quotient = 0; // 0 / Y ===> 0
1805 Remainder = 0; // 0 % Y ===> 0
1809 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1810 Quotient = 0; // X / Y ===> 0, iff X < Y
1811 Remainder = LHS; // X % Y ===> X, iff X < Y
1816 Quotient = 1; // X / X ===> 1
1817 Remainder = 0; // X % X ===> 0;
1821 if (lhsWords == 1 && rhsWords == 1) {
1822 // There is only one word to consider so use the native versions.
1823 if (LHS.isSingleWord()) {
1824 Quotient = APInt(LHS.getBitWidth(), LHS.VAL / RHS.VAL);
1825 Remainder = APInt(LHS.getBitWidth(), LHS.VAL % RHS.VAL);
1827 Quotient = APInt(LHS.getBitWidth(), LHS.pVal[0] / RHS.pVal[0]);
1828 Remainder = APInt(LHS.getBitWidth(), LHS.pVal[0] % RHS.pVal[0]);
1833 // Okay, lets do it the long way
1834 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1837 void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen,
1839 // Check our assumptions here
1840 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1841 "Radix should be 2, 8, 10, or 16!");
1842 assert(str && "String is null?");
1843 bool isNeg = str[0] == '-';
1846 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
1847 assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width");
1848 assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width");
1849 assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width");
1852 if (!isSingleWord())
1853 pVal = getClearedMemory(getNumWords());
1855 // Figure out if we can shift instead of multiply
1856 uint32_t shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1858 // Set up an APInt for the digit to add outside the loop so we don't
1859 // constantly construct/destruct it.
1860 APInt apdigit(getBitWidth(), 0);
1861 APInt apradix(getBitWidth(), radix);
1863 // Enter digit traversal loop
1864 for (unsigned i = 0; i < slen; i++) {
1867 char cdigit = str[i];
1869 if (!isxdigit(cdigit))
1870 assert(0 && "Invalid hex digit in string");
1871 if (isdigit(cdigit))
1872 digit = cdigit - '0';
1873 else if (cdigit >= 'a')
1874 digit = cdigit - 'a' + 10;
1875 else if (cdigit >= 'A')
1876 digit = cdigit - 'A' + 10;
1878 assert(0 && "huh? we shouldn't get here");
1879 } else if (isdigit(cdigit)) {
1880 digit = cdigit - '0';
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 std::string APInt::toString(uint8_t radix, bool wantSigned) const {
1906 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1907 "Radix should be 2, 8, 10, or 16!");
1908 static const char *digits[] = {
1909 "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"
1912 uint32_t bits_used = getActiveBits();
1913 if (isSingleWord()) {
1915 const char *format = (radix == 10 ? (wantSigned ? "%lld" : "%llu") :
1916 (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0)));
1919 int64_t sextVal = (int64_t(VAL) << (APINT_BITS_PER_WORD-BitWidth)) >>
1920 (APINT_BITS_PER_WORD-BitWidth);
1921 sprintf(buf, format, sextVal);
1923 sprintf(buf, format, VAL);
1928 uint32_t bit = v & 1;
1930 buf[bits_used] = digits[bit][0];
1939 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
1940 // because the number of bits per digit (1,3 and 4 respectively) divides
1941 // equaly. We just shift until there value is zero.
1943 // First, check for a zero value and just short circuit the logic below.
1948 size_t insert_at = 0;
1949 if (wantSigned && this->isNegative()) {
1950 // They want to print the signed version and it is a negative value
1951 // Flip the bits and add one to turn it into the equivalent positive
1952 // value and put a '-' in the result.
1958 // Just shift tmp right for each digit width until it becomes zero
1959 uint32_t shift = (radix == 16 ? 4 : (radix == 8 ? 3 : 1));
1960 uint64_t mask = radix - 1;
1961 APInt zero(tmp.getBitWidth(), 0);
1962 while (tmp.ne(zero)) {
1963 unsigned digit = (tmp.isSingleWord() ? tmp.VAL : tmp.pVal[0]) & mask;
1964 result.insert(insert_at, digits[digit]);
1965 tmp = tmp.lshr(shift);
1972 APInt divisor(4, radix);
1973 APInt zero(tmp.getBitWidth(), 0);
1974 size_t insert_at = 0;
1975 if (wantSigned && tmp[BitWidth-1]) {
1976 // They want to print the signed version and it is a negative value
1977 // Flip the bits and add one to turn it into the equivalent positive
1978 // value and put a '-' in the result.
1984 if (tmp == APInt(tmp.getBitWidth(), 0))
1986 else while (tmp.ne(zero)) {
1988 APInt tmp2(tmp.getBitWidth(), 0);
1989 divide(tmp, tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
1991 uint32_t digit = APdigit.getZExtValue();
1992 assert(digit < radix && "divide failed");
1993 result.insert(insert_at,digits[digit]);
2000 void APInt::dump() const
2002 cerr << "APInt(" << BitWidth << ")=" << std::setbase(16);
2005 else for (unsigned i = getNumWords(); i > 0; i--) {
2006 cerr << pVal[i-1] << " ";
2008 cerr << " U(" << this->toStringUnsigned(10) << ") S("
2009 << this->toStringSigned(10) << ")" << std::setbase(10);
2012 // This implements a variety of operations on a representation of
2013 // arbitrary precision, two's-complement, bignum integer values.
2015 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2016 and unrestricting assumption. */
2017 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2019 /* Some handy functions local to this file. */
2022 /* Returns the integer part with the least significant BITS set.
2023 BITS cannot be zero. */
2025 lowBitMask(unsigned int bits)
2027 assert (bits != 0 && bits <= integerPartWidth);
2029 return ~(integerPart) 0 >> (integerPartWidth - bits);
2032 /* Returns the value of the lower half of PART. */
2034 lowHalf(integerPart part)
2036 return part & lowBitMask(integerPartWidth / 2);
2039 /* Returns the value of the upper half of PART. */
2041 highHalf(integerPart part)
2043 return part >> (integerPartWidth / 2);
2046 /* Returns the bit number of the most significant set bit of a part.
2047 If the input number has no bits set -1U is returned. */
2049 partMSB(integerPart value)
2051 unsigned int n, msb;
2056 n = integerPartWidth / 2;
2071 /* Returns the bit number of the least significant set bit of a
2072 part. If the input number has no bits set -1U is returned. */
2074 partLSB(integerPart value)
2076 unsigned int n, lsb;
2081 lsb = integerPartWidth - 1;
2082 n = integerPartWidth / 2;
2097 /* Sets the least significant part of a bignum to the input value, and
2098 zeroes out higher parts. */
2100 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2107 for(i = 1; i < parts; i++)
2111 /* Assign one bignum to another. */
2113 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2117 for(i = 0; i < parts; i++)
2121 /* Returns true if a bignum is zero, false otherwise. */
2123 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2127 for(i = 0; i < parts; i++)
2134 /* Extract the given bit of a bignum; returns 0 or 1. */
2136 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2138 return(parts[bit / integerPartWidth]
2139 & ((integerPart) 1 << bit % integerPartWidth)) != 0;
2142 /* Set the given bit of a bignum. */
2144 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2146 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2149 /* Returns the bit number of the least significant set bit of a
2150 number. If the input number has no bits set -1U is returned. */
2152 APInt::tcLSB(const integerPart *parts, unsigned int n)
2154 unsigned int i, lsb;
2156 for(i = 0; i < n; i++) {
2157 if (parts[i] != 0) {
2158 lsb = partLSB(parts[i]);
2160 return lsb + i * integerPartWidth;
2167 /* Returns the bit number of the most significant set bit of a number.
2168 If the input number has no bits set -1U is returned. */
2170 APInt::tcMSB(const integerPart *parts, unsigned int n)
2177 if (parts[n] != 0) {
2178 msb = partMSB(parts[n]);
2180 return msb + n * integerPartWidth;
2187 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2188 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2189 the least significant bit of DST. All high bits above srcBITS in
2190 DST are zero-filled. */
2192 APInt::tcExtract(integerPart *dst, unsigned int dstCount, const integerPart *src,
2193 unsigned int srcBits, unsigned int srcLSB)
2195 unsigned int firstSrcPart, dstParts, shift, n;
2197 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2198 assert (dstParts <= dstCount);
2200 firstSrcPart = srcLSB / integerPartWidth;
2201 tcAssign (dst, src + firstSrcPart, dstParts);
2203 shift = srcLSB % integerPartWidth;
2204 tcShiftRight (dst, dstParts, shift);
2206 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2207 in DST. If this is less that srcBits, append the rest, else
2208 clear the high bits. */
2209 n = dstParts * integerPartWidth - shift;
2211 integerPart mask = lowBitMask (srcBits - n);
2212 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2213 << n % integerPartWidth);
2214 } else if (n > srcBits) {
2215 if (srcBits % integerPartWidth)
2216 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2219 /* Clear high parts. */
2220 while (dstParts < dstCount)
2221 dst[dstParts++] = 0;
2224 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2226 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2227 integerPart c, unsigned int parts)
2233 for(i = 0; i < parts; i++) {
2238 dst[i] += rhs[i] + 1;
2249 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2251 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2252 integerPart c, unsigned int parts)
2258 for(i = 0; i < parts; i++) {
2263 dst[i] -= rhs[i] + 1;
2274 /* Negate a bignum in-place. */
2276 APInt::tcNegate(integerPart *dst, unsigned int parts)
2278 tcComplement(dst, parts);
2279 tcIncrement(dst, parts);
2282 /* DST += SRC * MULTIPLIER + CARRY if add is true
2283 DST = SRC * MULTIPLIER + CARRY if add is false
2285 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2286 they must start at the same point, i.e. DST == SRC.
2288 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2289 returned. Otherwise DST is filled with the least significant
2290 DSTPARTS parts of the result, and if all of the omitted higher
2291 parts were zero return zero, otherwise overflow occurred and
2294 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2295 integerPart multiplier, integerPart carry,
2296 unsigned int srcParts, unsigned int dstParts,
2301 /* Otherwise our writes of DST kill our later reads of SRC. */
2302 assert(dst <= src || dst >= src + srcParts);
2303 assert(dstParts <= srcParts + 1);
2305 /* N loops; minimum of dstParts and srcParts. */
2306 n = dstParts < srcParts ? dstParts: srcParts;
2308 for(i = 0; i < n; i++) {
2309 integerPart low, mid, high, srcPart;
2311 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2313 This cannot overflow, because
2315 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2317 which is less than n^2. */
2321 if (multiplier == 0 || srcPart == 0) {
2325 low = lowHalf(srcPart) * lowHalf(multiplier);
2326 high = highHalf(srcPart) * highHalf(multiplier);
2328 mid = lowHalf(srcPart) * highHalf(multiplier);
2329 high += highHalf(mid);
2330 mid <<= integerPartWidth / 2;
2331 if (low + mid < low)
2335 mid = highHalf(srcPart) * lowHalf(multiplier);
2336 high += highHalf(mid);
2337 mid <<= integerPartWidth / 2;
2338 if (low + mid < low)
2342 /* Now add carry. */
2343 if (low + carry < low)
2349 /* And now DST[i], and store the new low part there. */
2350 if (low + dst[i] < low)
2360 /* Full multiplication, there is no overflow. */
2361 assert(i + 1 == dstParts);
2365 /* We overflowed if there is carry. */
2369 /* We would overflow if any significant unwritten parts would be
2370 non-zero. This is true if any remaining src parts are non-zero
2371 and the multiplier is non-zero. */
2373 for(; i < srcParts; i++)
2377 /* We fitted in the narrow destination. */
2382 /* DST = LHS * RHS, where DST has the same width as the operands and
2383 is filled with the least significant parts of the result. Returns
2384 one if overflow occurred, otherwise zero. DST must be disjoint
2385 from both operands. */
2387 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2388 const integerPart *rhs, unsigned int parts)
2393 assert(dst != lhs && dst != rhs);
2396 tcSet(dst, 0, parts);
2398 for(i = 0; i < parts; i++)
2399 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2405 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2406 operands. No overflow occurs. DST must be disjoint from both
2407 operands. Returns the number of parts required to hold the
2410 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2411 const integerPart *rhs, unsigned int lhsParts,
2412 unsigned int rhsParts)
2414 /* Put the narrower number on the LHS for less loops below. */
2415 if (lhsParts > rhsParts) {
2416 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2420 assert(dst != lhs && dst != rhs);
2422 tcSet(dst, 0, rhsParts);
2424 for(n = 0; n < lhsParts; n++)
2425 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2427 n = lhsParts + rhsParts;
2429 return n - (dst[n - 1] == 0);
2433 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2434 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2435 set REMAINDER to the remainder, return zero. i.e.
2437 OLD_LHS = RHS * LHS + REMAINDER
2439 SCRATCH is a bignum of the same size as the operands and result for
2440 use by the routine; its contents need not be initialized and are
2441 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2444 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2445 integerPart *remainder, integerPart *srhs,
2448 unsigned int n, shiftCount;
2451 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2453 shiftCount = tcMSB(rhs, parts) + 1;
2454 if (shiftCount == 0)
2457 shiftCount = parts * integerPartWidth - shiftCount;
2458 n = shiftCount / integerPartWidth;
2459 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2461 tcAssign(srhs, rhs, parts);
2462 tcShiftLeft(srhs, parts, shiftCount);
2463 tcAssign(remainder, lhs, parts);
2464 tcSet(lhs, 0, parts);
2466 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2471 compare = tcCompare(remainder, srhs, parts);
2473 tcSubtract(remainder, srhs, 0, parts);
2477 if (shiftCount == 0)
2480 tcShiftRight(srhs, parts, 1);
2481 if ((mask >>= 1) == 0)
2482 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2488 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2489 There are no restrictions on COUNT. */
2491 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2494 unsigned int jump, shift;
2496 /* Jump is the inter-part jump; shift is is intra-part shift. */
2497 jump = count / integerPartWidth;
2498 shift = count % integerPartWidth;
2500 while (parts > jump) {
2505 /* dst[i] comes from the two parts src[i - jump] and, if we have
2506 an intra-part shift, src[i - jump - 1]. */
2507 part = dst[parts - jump];
2510 if (parts >= jump + 1)
2511 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2522 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2523 zero. There are no restrictions on COUNT. */
2525 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2528 unsigned int i, jump, shift;
2530 /* Jump is the inter-part jump; shift is is intra-part shift. */
2531 jump = count / integerPartWidth;
2532 shift = count % integerPartWidth;
2534 /* Perform the shift. This leaves the most significant COUNT bits
2535 of the result at zero. */
2536 for(i = 0; i < parts; i++) {
2539 if (i + jump >= parts) {
2542 part = dst[i + jump];
2545 if (i + jump + 1 < parts)
2546 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2555 /* Bitwise and of two bignums. */
2557 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2561 for(i = 0; i < parts; i++)
2565 /* Bitwise inclusive or of two bignums. */
2567 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2571 for(i = 0; i < parts; i++)
2575 /* Bitwise exclusive or of two bignums. */
2577 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2581 for(i = 0; i < parts; i++)
2585 /* Complement a bignum in-place. */
2587 APInt::tcComplement(integerPart *dst, unsigned int parts)
2591 for(i = 0; i < parts; i++)
2595 /* Comparison (unsigned) of two bignums. */
2597 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2602 if (lhs[parts] == rhs[parts])
2605 if (lhs[parts] > rhs[parts])
2614 /* Increment a bignum in-place, return the carry flag. */
2616 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2620 for(i = 0; i < parts; i++)
2627 /* Set the least significant BITS bits of a bignum, clear the
2630 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2636 while (bits > integerPartWidth) {
2637 dst[i++] = ~(integerPart) 0;
2638 bits -= integerPartWidth;
2642 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);