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"
30 /// A utility function for allocating memory, checking for allocation failures,
31 /// and ensuring the contents are zeroed.
32 inline static uint64_t* getClearedMemory(uint32_t numWords) {
33 uint64_t * result = new uint64_t[numWords];
34 assert(result && "APInt memory allocation fails!");
35 memset(result, 0, numWords * sizeof(uint64_t));
39 /// A utility function for allocating memory and checking for allocation
40 /// failure. The content is not zeroed.
41 inline static uint64_t* getMemory(uint32_t numWords) {
42 uint64_t * result = new uint64_t[numWords];
43 assert(result && "APInt memory allocation fails!");
47 APInt::APInt(uint32_t numBits, uint64_t val, bool isSigned)
48 : BitWidth(numBits), VAL(0) {
49 assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
50 assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
54 pVal = getClearedMemory(getNumWords());
56 if (isSigned && int64_t(val) < 0)
57 for (unsigned i = 1; i < getNumWords(); ++i)
63 APInt::APInt(uint32_t numBits, uint32_t numWords, uint64_t bigVal[])
64 : BitWidth(numBits), VAL(0) {
65 assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
66 assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
67 assert(bigVal && "Null pointer detected!");
71 // Get memory, cleared to 0
72 pVal = getClearedMemory(getNumWords());
73 // Calculate the number of words to copy
74 uint32_t words = std::min<uint32_t>(numWords, getNumWords());
75 // Copy the words from bigVal to pVal
76 memcpy(pVal, bigVal, words * APINT_WORD_SIZE);
78 // Make sure unused high bits are cleared
82 APInt::APInt(uint32_t numbits, const char StrStart[], uint32_t slen,
84 : BitWidth(numbits), VAL(0) {
85 assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
86 assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
87 fromString(numbits, StrStart, slen, radix);
90 APInt::APInt(uint32_t numbits, const std::string& Val, uint8_t radix)
91 : BitWidth(numbits), VAL(0) {
92 assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
93 assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
94 assert(!Val.empty() && "String empty?");
95 fromString(numbits, Val.c_str(), Val.size(), radix);
98 APInt::APInt(const APInt& that)
99 : BitWidth(that.BitWidth), VAL(0) {
100 assert(BitWidth >= IntegerType::MIN_INT_BITS && "bitwidth too small");
101 assert(BitWidth <= IntegerType::MAX_INT_BITS && "bitwidth too large");
105 pVal = getMemory(getNumWords());
106 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
111 if (!isSingleWord() && pVal)
115 APInt& APInt::operator=(const APInt& RHS) {
116 // Don't do anything for X = X
120 // If the bitwidths are the same, we can avoid mucking with memory
121 if (BitWidth == RHS.getBitWidth()) {
125 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
130 if (RHS.isSingleWord())
134 pVal = getMemory(RHS.getNumWords());
135 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
137 else if (getNumWords() == RHS.getNumWords())
138 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
139 else if (RHS.isSingleWord()) {
144 pVal = getMemory(RHS.getNumWords());
145 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
147 BitWidth = RHS.BitWidth;
148 return clearUnusedBits();
151 APInt& APInt::operator=(uint64_t RHS) {
156 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
158 return clearUnusedBits();
161 /// add_1 - This function adds a single "digit" integer, y, to the multiple
162 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
163 /// 1 is returned if there is a carry out, otherwise 0 is returned.
164 /// @returns the carry of the addition.
165 static bool add_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
166 for (uint32_t i = 0; i < len; ++i) {
169 y = 1; // Carry one to next digit.
171 y = 0; // No need to carry so exit early
178 /// @brief Prefix increment operator. Increments the APInt by one.
179 APInt& APInt::operator++() {
183 add_1(pVal, pVal, getNumWords(), 1);
184 return clearUnusedBits();
187 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
188 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
189 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
190 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
191 /// In other words, if y > x then this function returns 1, otherwise 0.
192 /// @returns the borrow out of the subtraction
193 static bool sub_1(uint64_t x[], uint32_t len, uint64_t y) {
194 for (uint32_t i = 0; i < len; ++i) {
198 y = 1; // We have to "borrow 1" from next "digit"
200 y = 0; // No need to borrow
201 break; // Remaining digits are unchanged so exit early
207 /// @brief Prefix decrement operator. Decrements the APInt by one.
208 APInt& APInt::operator--() {
212 sub_1(pVal, getNumWords(), 1);
213 return clearUnusedBits();
216 /// add - This function adds the integer array x to the integer array Y and
217 /// places the result in dest.
218 /// @returns the carry out from the addition
219 /// @brief General addition of 64-bit integer arrays
220 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
223 for (uint32_t i = 0; i< len; ++i) {
224 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
225 dest[i] = x[i] + y[i] + carry;
226 carry = dest[i] < limit || (carry && dest[i] == limit);
231 /// Adds the RHS APint to this APInt.
232 /// @returns this, after addition of RHS.
233 /// @brief Addition assignment operator.
234 APInt& APInt::operator+=(const APInt& RHS) {
235 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
239 add(pVal, pVal, RHS.pVal, getNumWords());
241 return clearUnusedBits();
244 /// Subtracts the integer array y from the integer array x
245 /// @returns returns the borrow out.
246 /// @brief Generalized subtraction of 64-bit integer arrays.
247 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
250 for (uint32_t i = 0; i < len; ++i) {
251 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
252 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
253 dest[i] = x_tmp - y[i];
258 /// Subtracts the RHS APInt from this APInt
259 /// @returns this, after subtraction
260 /// @brief Subtraction assignment operator.
261 APInt& APInt::operator-=(const APInt& RHS) {
262 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
266 sub(pVal, pVal, RHS.pVal, getNumWords());
267 return clearUnusedBits();
270 /// Multiplies an integer array, x by a a uint64_t integer and places the result
272 /// @returns the carry out of the multiplication.
273 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
274 static uint64_t mul_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
275 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
276 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
279 // For each digit of x.
280 for (uint32_t i = 0; i < len; ++i) {
281 // Split x into high and low words
282 uint64_t lx = x[i] & 0xffffffffULL;
283 uint64_t hx = x[i] >> 32;
284 // hasCarry - A flag to indicate if there is a carry to the next digit.
285 // hasCarry == 0, no carry
286 // hasCarry == 1, has carry
287 // hasCarry == 2, no carry and the calculation result == 0.
288 uint8_t hasCarry = 0;
289 dest[i] = carry + lx * ly;
290 // Determine if the add above introduces carry.
291 hasCarry = (dest[i] < carry) ? 1 : 0;
292 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
293 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
294 // (2^32 - 1) + 2^32 = 2^64.
295 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
297 carry += (lx * hy) & 0xffffffffULL;
298 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
299 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
300 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
305 /// Multiplies integer array x by integer array y and stores the result into
306 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
307 /// @brief Generalized multiplicate of integer arrays.
308 static void mul(uint64_t dest[], uint64_t x[], uint32_t xlen, uint64_t y[],
310 dest[xlen] = mul_1(dest, x, xlen, y[0]);
311 for (uint32_t i = 1; i < ylen; ++i) {
312 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
313 uint64_t carry = 0, lx = 0, hx = 0;
314 for (uint32_t j = 0; j < xlen; ++j) {
315 lx = x[j] & 0xffffffffULL;
317 // hasCarry - A flag to indicate if has carry.
318 // hasCarry == 0, no carry
319 // hasCarry == 1, has carry
320 // hasCarry == 2, no carry and the calculation result == 0.
321 uint8_t hasCarry = 0;
322 uint64_t resul = carry + lx * ly;
323 hasCarry = (resul < carry) ? 1 : 0;
324 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
325 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
327 carry += (lx * hy) & 0xffffffffULL;
328 resul = (carry << 32) | (resul & 0xffffffffULL);
330 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
331 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
332 ((lx * hy) >> 32) + hx * hy;
334 dest[i+xlen] = carry;
338 APInt& APInt::operator*=(const APInt& RHS) {
339 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
340 if (isSingleWord()) {
346 // Get some bit facts about LHS and check for zero
347 uint32_t lhsBits = getActiveBits();
348 uint32_t lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
353 // Get some bit facts about RHS and check for zero
354 uint32_t rhsBits = RHS.getActiveBits();
355 uint32_t rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
362 // Allocate space for the result
363 uint32_t destWords = rhsWords + lhsWords;
364 uint64_t *dest = getMemory(destWords);
366 // Perform the long multiply
367 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
369 // Copy result back into *this
371 uint32_t wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
372 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
374 // delete dest array and return
379 APInt& APInt::operator&=(const APInt& RHS) {
380 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
381 if (isSingleWord()) {
385 uint32_t numWords = getNumWords();
386 for (uint32_t i = 0; i < numWords; ++i)
387 pVal[i] &= RHS.pVal[i];
391 APInt& APInt::operator|=(const APInt& RHS) {
392 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
393 if (isSingleWord()) {
397 uint32_t numWords = getNumWords();
398 for (uint32_t i = 0; i < numWords; ++i)
399 pVal[i] |= RHS.pVal[i];
403 APInt& APInt::operator^=(const APInt& RHS) {
404 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
405 if (isSingleWord()) {
407 this->clearUnusedBits();
410 uint32_t numWords = getNumWords();
411 for (uint32_t i = 0; i < numWords; ++i)
412 pVal[i] ^= RHS.pVal[i];
413 return clearUnusedBits();
416 APInt APInt::operator&(const APInt& RHS) const {
417 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
419 return APInt(getBitWidth(), VAL & RHS.VAL);
421 uint32_t numWords = getNumWords();
422 uint64_t* val = getMemory(numWords);
423 for (uint32_t i = 0; i < numWords; ++i)
424 val[i] = pVal[i] & RHS.pVal[i];
425 return APInt(val, getBitWidth());
428 APInt APInt::operator|(const APInt& RHS) const {
429 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
431 return APInt(getBitWidth(), VAL | RHS.VAL);
433 uint32_t numWords = getNumWords();
434 uint64_t *val = getMemory(numWords);
435 for (uint32_t i = 0; i < numWords; ++i)
436 val[i] = pVal[i] | RHS.pVal[i];
437 return APInt(val, getBitWidth());
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);
445 uint32_t numWords = getNumWords();
446 uint64_t *val = getMemory(numWords);
447 for (uint32_t i = 0; i < numWords; ++i)
448 val[i] = pVal[i] ^ RHS.pVal[i];
450 // 0^0==1 so clear the high bits in case they got set.
451 return APInt(val, getBitWidth()).clearUnusedBits();
454 bool APInt::operator !() const {
458 for (uint32_t i = 0; i < getNumWords(); ++i)
464 APInt APInt::operator*(const APInt& RHS) const {
465 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
467 return APInt(BitWidth, VAL * RHS.VAL);
470 return Result.clearUnusedBits();
473 APInt APInt::operator+(const APInt& RHS) const {
474 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
476 return APInt(BitWidth, VAL + RHS.VAL);
477 APInt Result(BitWidth, 0);
478 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
479 return Result.clearUnusedBits();
482 APInt APInt::operator-(const APInt& RHS) const {
483 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
485 return APInt(BitWidth, VAL - RHS.VAL);
486 APInt Result(BitWidth, 0);
487 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
488 return Result.clearUnusedBits();
491 bool APInt::operator[](uint32_t bitPosition) const {
492 return (maskBit(bitPosition) &
493 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
496 bool APInt::operator==(const APInt& RHS) const {
497 assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
499 return VAL == RHS.VAL;
501 // Get some facts about the number of bits used in the two operands.
502 uint32_t n1 = getActiveBits();
503 uint32_t n2 = RHS.getActiveBits();
505 // If the number of bits isn't the same, they aren't equal
509 // If the number of bits fits in a word, we only need to compare the low word.
510 if (n1 <= APINT_BITS_PER_WORD)
511 return pVal[0] == RHS.pVal[0];
513 // Otherwise, compare everything
514 for (int i = whichWord(n1 - 1); i >= 0; --i)
515 if (pVal[i] != RHS.pVal[i])
520 bool APInt::operator==(uint64_t Val) const {
524 uint32_t n = getActiveBits();
525 if (n <= APINT_BITS_PER_WORD)
526 return pVal[0] == Val;
531 bool APInt::ult(const APInt& RHS) const {
532 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
534 return VAL < RHS.VAL;
536 // Get active bit length of both operands
537 uint32_t n1 = getActiveBits();
538 uint32_t n2 = RHS.getActiveBits();
540 // If magnitude of LHS is less than RHS, return true.
544 // If magnitude of RHS is greather than LHS, return false.
548 // If they bot fit in a word, just compare the low order word
549 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
550 return pVal[0] < RHS.pVal[0];
552 // Otherwise, compare all words
553 uint32_t topWord = whichWord(std::max(n1,n2)-1);
554 for (int i = topWord; i >= 0; --i) {
555 if (pVal[i] > RHS.pVal[i])
557 if (pVal[i] < RHS.pVal[i])
563 bool APInt::slt(const APInt& RHS) const {
564 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
565 if (isSingleWord()) {
566 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
567 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
568 return lhsSext < rhsSext;
573 bool lhsNeg = isNegative();
574 bool rhsNeg = rhs.isNegative();
576 // Sign bit is set so perform two's complement to make it positive
581 // Sign bit is set so perform two's complement to make it positive
586 // Now we have unsigned values to compare so do the comparison if necessary
587 // based on the negativeness of the values.
599 APInt& APInt::set(uint32_t bitPosition) {
601 VAL |= maskBit(bitPosition);
603 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
607 APInt& APInt::set() {
608 if (isSingleWord()) {
610 return clearUnusedBits();
613 // Set all the bits in all the words.
614 for (uint32_t i = 0; i < getNumWords(); ++i)
616 // Clear the unused ones
617 return clearUnusedBits();
620 /// Set the given bit to 0 whose position is given as "bitPosition".
621 /// @brief Set a given bit to 0.
622 APInt& APInt::clear(uint32_t bitPosition) {
624 VAL &= ~maskBit(bitPosition);
626 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
630 /// @brief Set every bit to 0.
631 APInt& APInt::clear() {
635 memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
639 /// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on
641 APInt APInt::operator~() const {
647 /// @brief Toggle every bit to its opposite value.
648 APInt& APInt::flip() {
649 if (isSingleWord()) {
651 return clearUnusedBits();
653 for (uint32_t i = 0; i < getNumWords(); ++i)
655 return clearUnusedBits();
658 /// Toggle a given bit to its opposite value whose position is given
659 /// as "bitPosition".
660 /// @brief Toggles a given bit to its opposite value.
661 APInt& APInt::flip(uint32_t bitPosition) {
662 assert(bitPosition < BitWidth && "Out of the bit-width range!");
663 if ((*this)[bitPosition]) clear(bitPosition);
664 else set(bitPosition);
668 uint32_t APInt::getBitsNeeded(const char* str, uint32_t slen, uint8_t radix) {
669 assert(str != 0 && "Invalid value string");
670 assert(slen > 0 && "Invalid string length");
672 // Each computation below needs to know if its negative
673 uint32_t isNegative = str[0] == '-';
678 // For radixes of power-of-two values, the bits required is accurately and
681 return slen + isNegative;
683 return slen * 3 + isNegative;
685 return slen * 4 + isNegative;
687 // Otherwise it must be radix == 10, the hard case
688 assert(radix == 10 && "Invalid radix");
690 // This is grossly inefficient but accurate. We could probably do something
691 // with a computation of roughly slen*64/20 and then adjust by the value of
692 // the first few digits. But, I'm not sure how accurate that could be.
694 // Compute a sufficient number of bits that is always large enough but might
695 // be too large. This avoids the assertion in the constructor.
696 uint32_t sufficient = slen*64/18;
698 // Convert to the actual binary value.
699 APInt tmp(sufficient, str, slen, radix);
701 // Compute how many bits are required.
702 return isNegative + tmp.logBase2() + 1;
705 uint64_t APInt::getHashValue() const {
706 // Put the bit width into the low order bits.
707 uint64_t hash = BitWidth;
709 // Add the sum of the words to the hash.
711 hash += VAL << 6; // clear separation of up to 64 bits
713 for (uint32_t i = 0; i < getNumWords(); ++i)
714 hash += pVal[i] << 6; // clear sepration of up to 64 bits
718 /// HiBits - This function returns the high "numBits" bits of this APInt.
719 APInt APInt::getHiBits(uint32_t numBits) const {
720 return APIntOps::lshr(*this, BitWidth - numBits);
723 /// LoBits - This function returns the low "numBits" bits of this APInt.
724 APInt APInt::getLoBits(uint32_t numBits) const {
725 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
729 bool APInt::isPowerOf2() const {
730 return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
733 uint32_t APInt::countLeadingZeros() const {
736 Count = CountLeadingZeros_64(VAL);
738 for (uint32_t i = getNumWords(); i > 0u; --i) {
740 Count += APINT_BITS_PER_WORD;
742 Count += CountLeadingZeros_64(pVal[i-1]);
747 uint32_t remainder = BitWidth % APINT_BITS_PER_WORD;
749 Count -= APINT_BITS_PER_WORD - remainder;
753 static uint32_t countLeadingOnes_64(uint64_t V, uint32_t skip) {
757 while (V && (V & (1ULL << 63))) {
764 uint32_t APInt::countLeadingOnes() const {
766 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
768 uint32_t highWordBits = BitWidth % APINT_BITS_PER_WORD;
769 uint32_t shift = (highWordBits == 0 ? 0 : APINT_BITS_PER_WORD - highWordBits);
770 int i = getNumWords() - 1;
771 uint32_t Count = countLeadingOnes_64(pVal[i], shift);
772 if (Count == highWordBits) {
773 for (i--; i >= 0; --i) {
774 if (pVal[i] == -1ULL)
775 Count += APINT_BITS_PER_WORD;
777 Count += countLeadingOnes_64(pVal[i], 0);
785 uint32_t APInt::countTrailingZeros() const {
787 return CountTrailingZeros_64(VAL);
790 for (; i < getNumWords() && pVal[i] == 0; ++i)
791 Count += APINT_BITS_PER_WORD;
792 if (i < getNumWords())
793 Count += CountTrailingZeros_64(pVal[i]);
797 uint32_t APInt::countPopulation() const {
799 return CountPopulation_64(VAL);
801 for (uint32_t i = 0; i < getNumWords(); ++i)
802 Count += CountPopulation_64(pVal[i]);
806 APInt APInt::byteSwap() const {
807 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
809 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
810 else if (BitWidth == 32)
811 return APInt(BitWidth, ByteSwap_32(uint32_t(VAL)));
812 else if (BitWidth == 48) {
813 uint32_t Tmp1 = uint32_t(VAL >> 16);
814 Tmp1 = ByteSwap_32(Tmp1);
815 uint16_t Tmp2 = uint16_t(VAL);
816 Tmp2 = ByteSwap_16(Tmp2);
817 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
818 } else if (BitWidth == 64)
819 return APInt(BitWidth, ByteSwap_64(VAL));
821 APInt Result(BitWidth, 0);
822 char *pByte = (char*)Result.pVal;
823 for (uint32_t i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
825 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
826 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
832 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
834 APInt A = API1, B = API2;
837 B = APIntOps::urem(A, B);
843 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) {
850 // Get the sign bit from the highest order bit
851 bool isNeg = T.I >> 63;
853 // Get the 11-bit exponent and adjust for the 1023 bit bias
854 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
856 // If the exponent is negative, the value is < 0 so just return 0.
858 return APInt(width, 0u);
860 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
861 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
863 // If the exponent doesn't shift all bits out of the mantissa
865 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
866 APInt(width, mantissa >> (52 - exp));
868 // If the client didn't provide enough bits for us to shift the mantissa into
869 // then the result is undefined, just return 0
870 if (width <= exp - 52)
871 return APInt(width, 0);
873 // Otherwise, we have to shift the mantissa bits up to the right location
874 APInt Tmp(width, mantissa);
875 Tmp = Tmp.shl(exp - 52);
876 return isNeg ? -Tmp : Tmp;
879 /// RoundToDouble - This function convert this APInt to a double.
880 /// The layout for double is as following (IEEE Standard 754):
881 /// --------------------------------------
882 /// | Sign Exponent Fraction Bias |
883 /// |-------------------------------------- |
884 /// | 1[63] 11[62-52] 52[51-00] 1023 |
885 /// --------------------------------------
886 double APInt::roundToDouble(bool isSigned) const {
888 // Handle the simple case where the value is contained in one uint64_t.
889 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
891 int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
897 // Determine if the value is negative.
898 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
900 // Construct the absolute value if we're negative.
901 APInt Tmp(isNeg ? -(*this) : (*this));
903 // Figure out how many bits we're using.
904 uint32_t n = Tmp.getActiveBits();
906 // The exponent (without bias normalization) is just the number of bits
907 // we are using. Note that the sign bit is gone since we constructed the
911 // Return infinity for exponent overflow
913 if (!isSigned || !isNeg)
914 return std::numeric_limits<double>::infinity();
916 return -std::numeric_limits<double>::infinity();
918 exp += 1023; // Increment for 1023 bias
920 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
921 // extract the high 52 bits from the correct words in pVal.
923 unsigned hiWord = whichWord(n-1);
925 mantissa = Tmp.pVal[0];
927 mantissa >>= n - 52; // shift down, we want the top 52 bits.
929 assert(hiWord > 0 && "huh?");
930 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
931 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
932 mantissa = hibits | lobits;
935 // The leading bit of mantissa is implicit, so get rid of it.
936 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
941 T.I = sign | (exp << 52) | mantissa;
945 // Truncate to new width.
946 APInt &APInt::trunc(uint32_t width) {
947 assert(width < BitWidth && "Invalid APInt Truncate request");
948 assert(width >= IntegerType::MIN_INT_BITS && "Can't truncate to 0 bits");
949 uint32_t wordsBefore = getNumWords();
951 uint32_t wordsAfter = getNumWords();
952 if (wordsBefore != wordsAfter) {
953 if (wordsAfter == 1) {
954 uint64_t *tmp = pVal;
958 uint64_t *newVal = getClearedMemory(wordsAfter);
959 for (uint32_t i = 0; i < wordsAfter; ++i)
965 return clearUnusedBits();
968 // Sign extend to a new width.
969 APInt &APInt::sext(uint32_t width) {
970 assert(width > BitWidth && "Invalid APInt SignExtend request");
971 assert(width <= IntegerType::MAX_INT_BITS && "Too many bits");
972 // If the sign bit isn't set, this is the same as zext.
978 // The sign bit is set. First, get some facts
979 uint32_t wordsBefore = getNumWords();
980 uint32_t wordBits = BitWidth % APINT_BITS_PER_WORD;
982 uint32_t wordsAfter = getNumWords();
984 // Mask the high order word appropriately
985 if (wordsBefore == wordsAfter) {
986 uint32_t newWordBits = width % APINT_BITS_PER_WORD;
987 // The extension is contained to the wordsBefore-1th word.
988 uint64_t mask = ~0ULL;
990 mask >>= APINT_BITS_PER_WORD - newWordBits;
992 if (wordsBefore == 1)
995 pVal[wordsBefore-1] |= mask;
996 return clearUnusedBits();
999 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
1000 uint64_t *newVal = getMemory(wordsAfter);
1001 if (wordsBefore == 1)
1002 newVal[0] = VAL | mask;
1004 for (uint32_t i = 0; i < wordsBefore; ++i)
1005 newVal[i] = pVal[i];
1006 newVal[wordsBefore-1] |= mask;
1008 for (uint32_t i = wordsBefore; i < wordsAfter; i++)
1010 if (wordsBefore != 1)
1013 return clearUnusedBits();
1016 // Zero extend to a new width.
1017 APInt &APInt::zext(uint32_t width) {
1018 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1019 assert(width <= IntegerType::MAX_INT_BITS && "Too many bits");
1020 uint32_t wordsBefore = getNumWords();
1022 uint32_t wordsAfter = getNumWords();
1023 if (wordsBefore != wordsAfter) {
1024 uint64_t *newVal = getClearedMemory(wordsAfter);
1025 if (wordsBefore == 1)
1028 for (uint32_t i = 0; i < wordsBefore; ++i)
1029 newVal[i] = pVal[i];
1030 if (wordsBefore != 1)
1037 APInt &APInt::zextOrTrunc(uint32_t width) {
1038 if (BitWidth < width)
1040 if (BitWidth > width)
1041 return trunc(width);
1045 APInt &APInt::sextOrTrunc(uint32_t width) {
1046 if (BitWidth < width)
1048 if (BitWidth > width)
1049 return trunc(width);
1053 /// Arithmetic right-shift this APInt by shiftAmt.
1054 /// @brief Arithmetic right-shift function.
1055 APInt APInt::ashr(uint32_t shiftAmt) const {
1056 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1057 // Handle a degenerate case
1061 // Handle single word shifts with built-in ashr
1062 if (isSingleWord()) {
1063 if (shiftAmt == BitWidth)
1064 return APInt(BitWidth, 0); // undefined
1066 uint32_t SignBit = APINT_BITS_PER_WORD - BitWidth;
1067 return APInt(BitWidth,
1068 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1072 // If all the bits were shifted out, the result is, technically, undefined.
1073 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1074 // issues in the algorithm below.
1075 if (shiftAmt == BitWidth) {
1077 return APInt(BitWidth, -1ULL);
1079 return APInt(BitWidth, 0);
1082 // Create some space for the result.
1083 uint64_t * val = new uint64_t[getNumWords()];
1085 // Compute some values needed by the following shift algorithms
1086 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1087 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1088 uint32_t breakWord = getNumWords() - 1 - offset; // last word affected
1089 uint32_t bitsInWord = whichBit(BitWidth); // how many bits in last word?
1090 if (bitsInWord == 0)
1091 bitsInWord = APINT_BITS_PER_WORD;
1093 // If we are shifting whole words, just move whole words
1094 if (wordShift == 0) {
1095 // Move the words containing significant bits
1096 for (uint32_t i = 0; i <= breakWord; ++i)
1097 val[i] = pVal[i+offset]; // move whole word
1099 // Adjust the top significant word for sign bit fill, if negative
1101 if (bitsInWord < APINT_BITS_PER_WORD)
1102 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1104 // Shift the low order words
1105 for (uint32_t i = 0; i < breakWord; ++i) {
1106 // This combines the shifted corresponding word with the low bits from
1107 // the next word (shifted into this word's high bits).
1108 val[i] = (pVal[i+offset] >> wordShift) |
1109 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1112 // Shift the break word. In this case there are no bits from the next word
1113 // to include in this word.
1114 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1116 // Deal with sign extenstion in the break word, and possibly the word before
1119 if (wordShift > bitsInWord) {
1122 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1123 val[breakWord] |= ~0ULL;
1125 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1129 // Remaining words are 0 or -1, just assign them.
1130 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1131 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1133 return APInt(val, BitWidth).clearUnusedBits();
1136 /// Logical right-shift this APInt by shiftAmt.
1137 /// @brief Logical right-shift function.
1138 APInt APInt::lshr(uint32_t shiftAmt) const {
1139 if (isSingleWord()) {
1140 if (shiftAmt == BitWidth)
1141 return APInt(BitWidth, 0);
1143 return APInt(BitWidth, this->VAL >> shiftAmt);
1146 // If all the bits were shifted out, the result is 0. This avoids issues
1147 // with shifting by the size of the integer type, which produces undefined
1148 // results. We define these "undefined results" to always be 0.
1149 if (shiftAmt == BitWidth)
1150 return APInt(BitWidth, 0);
1152 // If none of the bits are shifted out, the result is *this. This avoids
1153 // issues with shifting byt he size of the integer type, which produces
1154 // undefined results in the code below. This is also an optimization.
1158 // Create some space for the result.
1159 uint64_t * val = new uint64_t[getNumWords()];
1161 // If we are shifting less than a word, compute the shift with a simple carry
1162 if (shiftAmt < APINT_BITS_PER_WORD) {
1164 for (int i = getNumWords()-1; i >= 0; --i) {
1165 val[i] = (pVal[i] >> shiftAmt) | carry;
1166 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1168 return APInt(val, BitWidth).clearUnusedBits();
1171 // Compute some values needed by the remaining shift algorithms
1172 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1173 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1175 // If we are shifting whole words, just move whole words
1176 if (wordShift == 0) {
1177 for (uint32_t i = 0; i < getNumWords() - offset; ++i)
1178 val[i] = pVal[i+offset];
1179 for (uint32_t i = getNumWords()-offset; i < getNumWords(); i++)
1181 return APInt(val,BitWidth).clearUnusedBits();
1184 // Shift the low order words
1185 uint32_t breakWord = getNumWords() - offset -1;
1186 for (uint32_t i = 0; i < breakWord; ++i)
1187 val[i] = (pVal[i+offset] >> wordShift) |
1188 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1189 // Shift the break word.
1190 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1192 // Remaining words are 0
1193 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1195 return APInt(val, BitWidth).clearUnusedBits();
1198 /// Left-shift this APInt by shiftAmt.
1199 /// @brief Left-shift function.
1200 APInt APInt::shl(uint32_t shiftAmt) const {
1201 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1202 if (isSingleWord()) {
1203 if (shiftAmt == BitWidth)
1204 return APInt(BitWidth, 0); // avoid undefined shift results
1205 return APInt(BitWidth, VAL << shiftAmt);
1208 // If all the bits were shifted out, the result is 0. This avoids issues
1209 // with shifting by the size of the integer type, which produces undefined
1210 // results. We define these "undefined results" to always be 0.
1211 if (shiftAmt == BitWidth)
1212 return APInt(BitWidth, 0);
1214 // If none of the bits are shifted out, the result is *this. This avoids a
1215 // lshr by the words size in the loop below which can produce incorrect
1216 // results. It also avoids the expensive computation below for a common case.
1220 // Create some space for the result.
1221 uint64_t * val = new uint64_t[getNumWords()];
1223 // If we are shifting less than a word, do it the easy way
1224 if (shiftAmt < APINT_BITS_PER_WORD) {
1226 for (uint32_t i = 0; i < getNumWords(); i++) {
1227 val[i] = pVal[i] << shiftAmt | carry;
1228 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1230 return APInt(val, BitWidth).clearUnusedBits();
1233 // Compute some values needed by the remaining shift algorithms
1234 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1235 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1237 // If we are shifting whole words, just move whole words
1238 if (wordShift == 0) {
1239 for (uint32_t i = 0; i < offset; i++)
1241 for (uint32_t i = offset; i < getNumWords(); i++)
1242 val[i] = pVal[i-offset];
1243 return APInt(val,BitWidth).clearUnusedBits();
1246 // Copy whole words from this to Result.
1247 uint32_t i = getNumWords() - 1;
1248 for (; i > offset; --i)
1249 val[i] = pVal[i-offset] << wordShift |
1250 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1251 val[offset] = pVal[0] << wordShift;
1252 for (i = 0; i < offset; ++i)
1254 return APInt(val, BitWidth).clearUnusedBits();
1257 APInt APInt::rotl(uint32_t rotateAmt) const {
1260 // Don't get too fancy, just use existing shift/or facilities
1264 lo.lshr(BitWidth - rotateAmt);
1268 APInt APInt::rotr(uint32_t rotateAmt) const {
1271 // Don't get too fancy, just use existing shift/or facilities
1275 hi.shl(BitWidth - rotateAmt);
1279 // Square Root - this method computes and returns the square root of "this".
1280 // Three mechanisms are used for computation. For small values (<= 5 bits),
1281 // a table lookup is done. This gets some performance for common cases. For
1282 // values using less than 52 bits, the value is converted to double and then
1283 // the libc sqrt function is called. The result is rounded and then converted
1284 // back to a uint64_t which is then used to construct the result. Finally,
1285 // the Babylonian method for computing square roots is used.
1286 APInt APInt::sqrt() const {
1288 // Determine the magnitude of the value.
1289 uint32_t magnitude = getActiveBits();
1291 // Use a fast table for some small values. This also gets rid of some
1292 // rounding errors in libc sqrt for small values.
1293 if (magnitude <= 5) {
1294 static const uint8_t results[32] = {
1297 /* 3- 6 */ 2, 2, 2, 2,
1298 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1299 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1300 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1303 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1306 // If the magnitude of the value fits in less than 52 bits (the precision of
1307 // an IEEE double precision floating point value), then we can use the
1308 // libc sqrt function which will probably use a hardware sqrt computation.
1309 // This should be faster than the algorithm below.
1310 if (magnitude < 52) {
1312 // Amazingly, VC++ doesn't have round().
1313 return APInt(BitWidth,
1314 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1316 return APInt(BitWidth,
1317 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1321 // Okay, all the short cuts are exhausted. We must compute it. The following
1322 // is a classical Babylonian method for computing the square root. This code
1323 // was adapted to APINt from a wikipedia article on such computations.
1324 // See http://www.wikipedia.org/ and go to the page named
1325 // Calculate_an_integer_square_root.
1326 uint32_t nbits = BitWidth, i = 4;
1327 APInt testy(BitWidth, 16);
1328 APInt x_old(BitWidth, 1);
1329 APInt x_new(BitWidth, 0);
1330 APInt two(BitWidth, 2);
1332 // Select a good starting value using binary logarithms.
1333 for (;; i += 2, testy = testy.shl(2))
1334 if (i >= nbits || this->ule(testy)) {
1335 x_old = x_old.shl(i / 2);
1339 // Use the Babylonian method to arrive at the integer square root:
1341 x_new = (this->udiv(x_old) + x_old).udiv(two);
1342 if (x_old.ule(x_new))
1347 // Make sure we return the closest approximation
1348 // NOTE: The rounding calculation below is correct. It will produce an
1349 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1350 // determined to be a rounding issue with pari/gp as it begins to use a
1351 // floating point representation after 192 bits. There are no discrepancies
1352 // between this algorithm and pari/gp for bit widths < 192 bits.
1353 APInt square(x_old * x_old);
1354 APInt nextSquare((x_old + 1) * (x_old +1));
1355 if (this->ult(square))
1357 else if (this->ule(nextSquare)) {
1358 APInt midpoint((nextSquare - square).udiv(two));
1359 APInt offset(*this - square);
1360 if (offset.ult(midpoint))
1365 assert(0 && "Error in APInt::sqrt computation");
1369 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1370 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1371 /// variables here have the same names as in the algorithm. Comments explain
1372 /// the algorithm and any deviation from it.
1373 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1374 uint32_t m, uint32_t n) {
1375 assert(u && "Must provide dividend");
1376 assert(v && "Must provide divisor");
1377 assert(q && "Must provide quotient");
1378 assert(u != v && u != q && v != q && "Must us different memory");
1379 assert(n>1 && "n must be > 1");
1381 // Knuth uses the value b as the base of the number system. In our case b
1382 // is 2^31 so we just set it to -1u.
1383 uint64_t b = uint64_t(1) << 32;
1385 DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n');
1386 DEBUG(cerr << "KnuthDiv: original:");
1387 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1388 DEBUG(cerr << " by");
1389 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1390 DEBUG(cerr << '\n');
1391 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1392 // u and v by d. Note that we have taken Knuth's advice here to use a power
1393 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1394 // 2 allows us to shift instead of multiply and it is easy to determine the
1395 // shift amount from the leading zeros. We are basically normalizing the u
1396 // and v so that its high bits are shifted to the top of v's range without
1397 // overflow. Note that this can require an extra word in u so that u must
1398 // be of length m+n+1.
1399 uint32_t shift = CountLeadingZeros_32(v[n-1]);
1400 uint32_t v_carry = 0;
1401 uint32_t u_carry = 0;
1403 for (uint32_t i = 0; i < m+n; ++i) {
1404 uint32_t u_tmp = u[i] >> (32 - shift);
1405 u[i] = (u[i] << shift) | u_carry;
1408 for (uint32_t i = 0; i < n; ++i) {
1409 uint32_t v_tmp = v[i] >> (32 - shift);
1410 v[i] = (v[i] << shift) | v_carry;
1415 DEBUG(cerr << "KnuthDiv: normal:");
1416 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1417 DEBUG(cerr << " by");
1418 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1419 DEBUG(cerr << '\n');
1421 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1424 DEBUG(cerr << "KnuthDiv: quotient digit #" << j << '\n');
1425 // D3. [Calculate q'.].
1426 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1427 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1428 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1429 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1430 // on v[n-2] determines at high speed most of the cases in which the trial
1431 // value qp is one too large, and it eliminates all cases where qp is two
1433 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1434 DEBUG(cerr << "KnuthDiv: dividend == " << dividend << '\n');
1435 uint64_t qp = dividend / v[n-1];
1436 uint64_t rp = dividend % v[n-1];
1437 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1440 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1443 DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1445 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1446 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1447 // consists of a simple multiplication by a one-place number, combined with
1450 for (uint32_t i = 0; i < n; ++i) {
1451 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1452 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1453 bool borrow = subtrahend > u_tmp;
1454 DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp
1455 << ", subtrahend == " << subtrahend
1456 << ", borrow = " << borrow << '\n');
1458 uint64_t result = u_tmp - subtrahend;
1460 u[k++] = result & (b-1); // subtract low word
1461 u[k++] = result >> 32; // subtract high word
1462 while (borrow && k <= m+n) { // deal with borrow to the left
1468 DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1471 DEBUG(cerr << "KnuthDiv: after subtraction:");
1472 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1473 DEBUG(cerr << '\n');
1474 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1475 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1476 // true value plus b**(n+1), namely as the b's complement of
1477 // the true value, and a "borrow" to the left should be remembered.
1480 bool carry = true; // true because b's complement is "complement + 1"
1481 for (uint32_t i = 0; i <= m+n; ++i) {
1482 u[i] = ~u[i] + carry; // b's complement
1483 carry = carry && u[i] == 0;
1486 DEBUG(cerr << "KnuthDiv: after complement:");
1487 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1488 DEBUG(cerr << '\n');
1490 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1491 // negative, go to step D6; otherwise go on to step D7.
1494 // D6. [Add back]. The probability that this step is necessary is very
1495 // small, on the order of only 2/b. Make sure that test data accounts for
1496 // this possibility. Decrease q[j] by 1
1498 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1499 // A carry will occur to the left of u[j+n], and it should be ignored
1500 // since it cancels with the borrow that occurred in D4.
1502 for (uint32_t i = 0; i < n; i++) {
1503 uint32_t limit = std::min(u[j+i],v[i]);
1504 u[j+i] += v[i] + carry;
1505 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1509 DEBUG(cerr << "KnuthDiv: after correction:");
1510 DEBUG(for (int i = m+n; i >=0; i--) cerr <<" " << u[i]);
1511 DEBUG(cerr << "\nKnuthDiv: digit result = " << q[j] << '\n');
1513 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1516 DEBUG(cerr << "KnuthDiv: quotient:");
1517 DEBUG(for (int i = m; i >=0; i--) cerr <<" " << q[i]);
1518 DEBUG(cerr << '\n');
1520 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1521 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1522 // compute the remainder (urem uses this).
1524 // The value d is expressed by the "shift" value above since we avoided
1525 // multiplication by d by using a shift left. So, all we have to do is
1526 // shift right here. In order to mak
1529 DEBUG(cerr << "KnuthDiv: remainder:");
1530 for (int i = n-1; i >= 0; i--) {
1531 r[i] = (u[i] >> shift) | carry;
1532 carry = u[i] << (32 - shift);
1533 DEBUG(cerr << " " << r[i]);
1536 for (int i = n-1; i >= 0; i--) {
1538 DEBUG(cerr << " " << r[i]);
1541 DEBUG(cerr << '\n');
1543 DEBUG(cerr << std::setbase(10) << '\n');
1546 void APInt::divide(const APInt LHS, uint32_t lhsWords,
1547 const APInt &RHS, uint32_t rhsWords,
1548 APInt *Quotient, APInt *Remainder)
1550 assert(lhsWords >= rhsWords && "Fractional result");
1552 // First, compose the values into an array of 32-bit words instead of
1553 // 64-bit words. This is a necessity of both the "short division" algorithm
1554 // and the the Knuth "classical algorithm" which requires there to be native
1555 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1556 // can't use 64-bit operands here because we don't have native results of
1557 // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't
1558 // work on large-endian machines.
1559 uint64_t mask = ~0ull >> (sizeof(uint32_t)*8);
1560 uint32_t n = rhsWords * 2;
1561 uint32_t m = (lhsWords * 2) - n;
1563 // Allocate space for the temporary values we need either on the stack, if
1564 // it will fit, or on the heap if it won't.
1565 uint32_t SPACE[128];
1570 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1573 Q = &SPACE[(m+n+1) + n];
1575 R = &SPACE[(m+n+1) + n + (m+n)];
1577 U = new uint32_t[m + n + 1];
1578 V = new uint32_t[n];
1579 Q = new uint32_t[m+n];
1581 R = new uint32_t[n];
1584 // Initialize the dividend
1585 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1586 for (unsigned i = 0; i < lhsWords; ++i) {
1587 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1588 U[i * 2] = tmp & mask;
1589 U[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1591 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1593 // Initialize the divisor
1594 memset(V, 0, (n)*sizeof(uint32_t));
1595 for (unsigned i = 0; i < rhsWords; ++i) {
1596 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1597 V[i * 2] = tmp & mask;
1598 V[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1601 // initialize the quotient and remainder
1602 memset(Q, 0, (m+n) * sizeof(uint32_t));
1604 memset(R, 0, n * sizeof(uint32_t));
1606 // Now, adjust m and n for the Knuth division. n is the number of words in
1607 // the divisor. m is the number of words by which the dividend exceeds the
1608 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1609 // contain any zero words or the Knuth algorithm fails.
1610 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1614 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1617 // If we're left with only a single word for the divisor, Knuth doesn't work
1618 // so we implement the short division algorithm here. This is much simpler
1619 // and faster because we are certain that we can divide a 64-bit quantity
1620 // by a 32-bit quantity at hardware speed and short division is simply a
1621 // series of such operations. This is just like doing short division but we
1622 // are using base 2^32 instead of base 10.
1623 assert(n != 0 && "Divide by zero?");
1625 uint32_t divisor = V[0];
1626 uint32_t remainder = 0;
1627 for (int i = m+n-1; i >= 0; i--) {
1628 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1629 if (partial_dividend == 0) {
1632 } else if (partial_dividend < divisor) {
1634 remainder = partial_dividend;
1635 } else if (partial_dividend == divisor) {
1639 Q[i] = partial_dividend / divisor;
1640 remainder = partial_dividend - (Q[i] * divisor);
1646 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1648 KnuthDiv(U, V, Q, R, m, n);
1651 // If the caller wants the quotient
1653 // Set up the Quotient value's memory.
1654 if (Quotient->BitWidth != LHS.BitWidth) {
1655 if (Quotient->isSingleWord())
1658 delete [] Quotient->pVal;
1659 Quotient->BitWidth = LHS.BitWidth;
1660 if (!Quotient->isSingleWord())
1661 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1665 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1667 if (lhsWords == 1) {
1669 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1670 if (Quotient->isSingleWord())
1671 Quotient->VAL = tmp;
1673 Quotient->pVal[0] = tmp;
1675 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1676 for (unsigned i = 0; i < lhsWords; ++i)
1678 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1682 // If the caller wants the remainder
1684 // Set up the Remainder value's memory.
1685 if (Remainder->BitWidth != RHS.BitWidth) {
1686 if (Remainder->isSingleWord())
1689 delete [] Remainder->pVal;
1690 Remainder->BitWidth = RHS.BitWidth;
1691 if (!Remainder->isSingleWord())
1692 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1696 // The remainder is in R. Reconstitute the remainder into Remainder's low
1698 if (rhsWords == 1) {
1700 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1701 if (Remainder->isSingleWord())
1702 Remainder->VAL = tmp;
1704 Remainder->pVal[0] = tmp;
1706 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1707 for (unsigned i = 0; i < rhsWords; ++i)
1708 Remainder->pVal[i] =
1709 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1713 // Clean up the memory we allocated.
1714 if (U != &SPACE[0]) {
1722 APInt APInt::udiv(const APInt& RHS) const {
1723 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1725 // First, deal with the easy case
1726 if (isSingleWord()) {
1727 assert(RHS.VAL != 0 && "Divide by zero?");
1728 return APInt(BitWidth, VAL / RHS.VAL);
1731 // Get some facts about the LHS and RHS number of bits and words
1732 uint32_t rhsBits = RHS.getActiveBits();
1733 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1734 assert(rhsWords && "Divided by zero???");
1735 uint32_t lhsBits = this->getActiveBits();
1736 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1738 // Deal with some degenerate cases
1741 return APInt(BitWidth, 0);
1742 else if (lhsWords < rhsWords || this->ult(RHS)) {
1743 // X / Y ===> 0, iff X < Y
1744 return APInt(BitWidth, 0);
1745 } else if (*this == RHS) {
1747 return APInt(BitWidth, 1);
1748 } else if (lhsWords == 1 && rhsWords == 1) {
1749 // All high words are zero, just use native divide
1750 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1753 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1754 APInt Quotient(1,0); // to hold result.
1755 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1759 APInt APInt::urem(const APInt& RHS) const {
1760 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1761 if (isSingleWord()) {
1762 assert(RHS.VAL != 0 && "Remainder by zero?");
1763 return APInt(BitWidth, VAL % RHS.VAL);
1766 // Get some facts about the LHS
1767 uint32_t lhsBits = getActiveBits();
1768 uint32_t lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1770 // Get some facts about the RHS
1771 uint32_t rhsBits = RHS.getActiveBits();
1772 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1773 assert(rhsWords && "Performing remainder operation by zero ???");
1775 // Check the degenerate cases
1776 if (lhsWords == 0) {
1778 return APInt(BitWidth, 0);
1779 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1780 // X % Y ===> X, iff X < Y
1782 } else if (*this == RHS) {
1784 return APInt(BitWidth, 0);
1785 } else if (lhsWords == 1) {
1786 // All high words are zero, just use native remainder
1787 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1790 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1791 APInt Remainder(1,0);
1792 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1796 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1797 APInt &Quotient, APInt &Remainder) {
1798 // Get some size facts about the dividend and divisor
1799 uint32_t lhsBits = LHS.getActiveBits();
1800 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1801 uint32_t rhsBits = RHS.getActiveBits();
1802 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1804 // Check the degenerate cases
1805 if (lhsWords == 0) {
1806 Quotient = 0; // 0 / Y ===> 0
1807 Remainder = 0; // 0 % Y ===> 0
1811 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1812 Quotient = 0; // X / Y ===> 0, iff X < Y
1813 Remainder = LHS; // X % Y ===> X, iff X < Y
1818 Quotient = 1; // X / X ===> 1
1819 Remainder = 0; // X % X ===> 0;
1823 if (lhsWords == 1 && rhsWords == 1) {
1824 // There is only one word to consider so use the native versions.
1825 if (LHS.isSingleWord()) {
1826 Quotient = APInt(LHS.getBitWidth(), LHS.VAL / RHS.VAL);
1827 Remainder = APInt(LHS.getBitWidth(), LHS.VAL % RHS.VAL);
1829 Quotient = APInt(LHS.getBitWidth(), LHS.pVal[0] / RHS.pVal[0]);
1830 Remainder = APInt(LHS.getBitWidth(), LHS.pVal[0] % RHS.pVal[0]);
1835 // Okay, lets do it the long way
1836 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1839 void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen,
1841 // Check our assumptions here
1842 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1843 "Radix should be 2, 8, 10, or 16!");
1844 assert(str && "String is null?");
1845 bool isNeg = str[0] == '-';
1848 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
1849 assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width");
1850 assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width");
1851 assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width");
1854 if (!isSingleWord())
1855 pVal = getClearedMemory(getNumWords());
1857 // Figure out if we can shift instead of multiply
1858 uint32_t shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1860 // Set up an APInt for the digit to add outside the loop so we don't
1861 // constantly construct/destruct it.
1862 APInt apdigit(getBitWidth(), 0);
1863 APInt apradix(getBitWidth(), radix);
1865 // Enter digit traversal loop
1866 for (unsigned i = 0; i < slen; i++) {
1869 char cdigit = str[i];
1871 if (!isxdigit(cdigit))
1872 assert(0 && "Invalid hex digit in string");
1873 if (isdigit(cdigit))
1874 digit = cdigit - '0';
1875 else if (cdigit >= 'a')
1876 digit = cdigit - 'a' + 10;
1877 else if (cdigit >= 'A')
1878 digit = cdigit - 'A' + 10;
1880 assert(0 && "huh? we shouldn't get here");
1881 } else if (isdigit(cdigit)) {
1882 digit = cdigit - '0';
1884 assert(0 && "Invalid character in digit string");
1887 // Shift or multiply the value by the radix
1893 // Add in the digit we just interpreted
1894 if (apdigit.isSingleWord())
1895 apdigit.VAL = digit;
1897 apdigit.pVal[0] = digit;
1900 // If its negative, put it in two's complement form
1907 std::string APInt::toString(uint8_t radix, bool wantSigned) const {
1908 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1909 "Radix should be 2, 8, 10, or 16!");
1910 static const char *digits[] = {
1911 "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"
1914 uint32_t bits_used = getActiveBits();
1915 if (isSingleWord()) {
1917 const char *format = (radix == 10 ? (wantSigned ? "%lld" : "%llu") :
1918 (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0)));
1921 int64_t sextVal = (int64_t(VAL) << (APINT_BITS_PER_WORD-BitWidth)) >>
1922 (APINT_BITS_PER_WORD-BitWidth);
1923 sprintf(buf, format, sextVal);
1925 sprintf(buf, format, VAL);
1930 uint32_t bit = v & 1;
1932 buf[bits_used] = digits[bit][0];
1941 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
1942 // because the number of bits per digit (1,3 and 4 respectively) divides
1943 // equaly. We just shift until there value is zero.
1945 // First, check for a zero value and just short circuit the logic below.
1950 size_t insert_at = 0;
1951 if (wantSigned && this->isNegative()) {
1952 // They want to print the signed version and it is a negative value
1953 // Flip the bits and add one to turn it into the equivalent positive
1954 // value and put a '-' in the result.
1960 // Just shift tmp right for each digit width until it becomes zero
1961 uint32_t shift = (radix == 16 ? 4 : (radix == 8 ? 3 : 1));
1962 uint64_t mask = radix - 1;
1963 APInt zero(tmp.getBitWidth(), 0);
1964 while (tmp.ne(zero)) {
1965 unsigned digit = (tmp.isSingleWord() ? tmp.VAL : tmp.pVal[0]) & mask;
1966 result.insert(insert_at, digits[digit]);
1967 tmp = tmp.lshr(shift);
1974 APInt divisor(4, radix);
1975 APInt zero(tmp.getBitWidth(), 0);
1976 size_t insert_at = 0;
1977 if (wantSigned && tmp[BitWidth-1]) {
1978 // They want to print the signed version and it is a negative value
1979 // Flip the bits and add one to turn it into the equivalent positive
1980 // value and put a '-' in the result.
1986 if (tmp == APInt(tmp.getBitWidth(), 0))
1988 else while (tmp.ne(zero)) {
1990 APInt tmp2(tmp.getBitWidth(), 0);
1991 divide(tmp, tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
1993 uint32_t digit = APdigit.getZExtValue();
1994 assert(digit < radix && "divide failed");
1995 result.insert(insert_at,digits[digit]);
2003 void APInt::dump() const
2005 cerr << "APInt(" << BitWidth << ")=" << std::setbase(16);
2008 else for (unsigned i = getNumWords(); i > 0; i--) {
2009 cerr << pVal[i-1] << " ";
2011 cerr << " U(" << this->toStringUnsigned(10) << ") S("
2012 << this->toStringSigned(10) << ")\n" << std::setbase(10);
2016 // This implements a variety of operations on a representation of
2017 // arbitrary precision, two's-complement, bignum integer values.
2019 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2020 and unrestricting assumption. */
2021 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2023 /* Some handy functions local to this file. */
2026 /* Returns the integer part with the least significant BITS set.
2027 BITS cannot be zero. */
2029 lowBitMask(unsigned int bits)
2031 assert (bits != 0 && bits <= integerPartWidth);
2033 return ~(integerPart) 0 >> (integerPartWidth - bits);
2036 /* Returns the value of the lower nibble of PART. */
2038 lowHalf(integerPart part)
2040 return part & lowBitMask(integerPartWidth / 2);
2043 /* Returns the value of the upper nibble of PART. */
2045 highHalf(integerPart part)
2047 return part >> (integerPartWidth / 2);
2050 /* Returns the bit number of the most significant bit of a part. If
2051 the input number has no bits set -1U is returned. */
2053 partMSB(integerPart value)
2055 unsigned int n, msb;
2060 n = integerPartWidth / 2;
2075 /* Returns the bit number of the least significant bit of a part.
2076 If the input number has no bits set -1U is returned. */
2078 partLSB(integerPart value)
2080 unsigned int n, lsb;
2085 lsb = integerPartWidth - 1;
2086 n = integerPartWidth / 2;
2101 /* Sets the least significant part of a bignum to the input value, and
2102 zeroes out higher parts. */
2104 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2109 for(i = 1; i < parts; i++)
2113 /* Assign one bignum to another. */
2115 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2119 for(i = 0; i < parts; i++)
2123 /* Returns true if a bignum is zero, false otherwise. */
2125 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2129 for(i = 0; i < parts; i++)
2136 /* Extract the given bit of a bignum; returns 0 or 1. */
2138 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2140 return(parts[bit / integerPartWidth]
2141 & ((integerPart) 1 << bit % integerPartWidth)) != 0;
2144 /* Set the given bit of a bignum. */
2146 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2148 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2151 /* Returns the bit number of the least significant bit of a number.
2152 If the input number has no bits set -1U is returned. */
2154 APInt::tcLSB(const integerPart *parts, unsigned int n)
2156 unsigned int i, lsb;
2158 for(i = 0; i < n; i++) {
2159 if (parts[i] != 0) {
2160 lsb = partLSB(parts[i]);
2162 return lsb + i * integerPartWidth;
2169 /* Returns the bit number of the most significant bit of a number. If
2170 the input number has no bits set -1U is returned. */
2172 APInt::tcMSB(const integerPart *parts, unsigned int n)
2179 if (parts[n] != 0) {
2180 msb = partMSB(parts[n]);
2182 return msb + n * integerPartWidth;
2189 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2191 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2192 integerPart c, unsigned int parts)
2198 for(i = 0; i < parts; i++) {
2203 dst[i] += rhs[i] + 1;
2214 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2216 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2217 integerPart c, unsigned int parts)
2223 for(i = 0; i < parts; i++) {
2228 dst[i] -= rhs[i] + 1;
2239 /* Negate a bignum in-place. */
2241 APInt::tcNegate(integerPart *dst, unsigned int parts)
2243 tcComplement(dst, parts);
2244 tcIncrement(dst, parts);
2247 /* DST += SRC * MULTIPLIER + PART if add is true
2248 DST = SRC * MULTIPLIER + PART if add is false
2250 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2251 they must start at the same point, i.e. DST == SRC.
2253 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2254 returned. Otherwise DST is filled with the least significant
2255 DSTPARTS parts of the result, and if all of the omitted higher
2256 parts were zero return zero, otherwise overflow occurred and
2259 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2260 integerPart multiplier, integerPart carry,
2261 unsigned int srcParts, unsigned int dstParts,
2266 /* Otherwise our writes of DST kill our later reads of SRC. */
2267 assert(dst <= src || dst >= src + srcParts);
2268 assert(dstParts <= srcParts + 1);
2270 /* N loops; minimum of dstParts and srcParts. */
2271 n = dstParts < srcParts ? dstParts: srcParts;
2273 for(i = 0; i < n; i++) {
2274 integerPart low, mid, high, srcPart;
2276 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2278 This cannot overflow, because
2280 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2282 which is less than n^2. */
2286 if (multiplier == 0 || srcPart == 0) {
2290 low = lowHalf(srcPart) * lowHalf(multiplier);
2291 high = highHalf(srcPart) * highHalf(multiplier);
2293 mid = lowHalf(srcPart) * highHalf(multiplier);
2294 high += highHalf(mid);
2295 mid <<= integerPartWidth / 2;
2296 if (low + mid < low)
2300 mid = highHalf(srcPart) * lowHalf(multiplier);
2301 high += highHalf(mid);
2302 mid <<= integerPartWidth / 2;
2303 if (low + mid < low)
2307 /* Now add carry. */
2308 if (low + carry < low)
2314 /* And now DST[i], and store the new low part there. */
2315 if (low + dst[i] < low)
2325 /* Full multiplication, there is no overflow. */
2326 assert(i + 1 == dstParts);
2330 /* We overflowed if there is carry. */
2334 /* We would overflow if any significant unwritten parts would be
2335 non-zero. This is true if any remaining src parts are non-zero
2336 and the multiplier is non-zero. */
2338 for(; i < srcParts; i++)
2342 /* We fitted in the narrow destination. */
2347 /* DST = LHS * RHS, where DST has the same width as the operands and
2348 is filled with the least significant parts of the result. Returns
2349 one if overflow occurred, otherwise zero. DST must be disjoint
2350 from both operands. */
2352 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2353 const integerPart *rhs, unsigned int parts)
2358 assert(dst != lhs && dst != rhs);
2361 tcSet(dst, 0, parts);
2363 for(i = 0; i < parts; i++)
2364 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2370 /* DST = LHS * RHS, where DST has twice the width as the operands. No
2371 overflow occurs. DST must be disjoint from both operands. */
2373 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2374 const integerPart *rhs, unsigned int parts)
2379 assert(dst != lhs && dst != rhs);
2382 tcSet(dst, 0, parts);
2384 for(i = 0; i < parts; i++)
2385 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2391 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2392 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2393 set REMAINDER to the remainder, return zero. i.e.
2395 OLD_LHS = RHS * LHS + REMAINDER
2397 SCRATCH is a bignum of the same size as the operands and result for
2398 use by the routine; its contents need not be initialized and are
2399 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2402 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2403 integerPart *remainder, integerPart *srhs,
2406 unsigned int n, shiftCount;
2409 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2411 shiftCount = tcMSB(rhs, parts) + 1;
2412 if (shiftCount == 0)
2415 shiftCount = parts * integerPartWidth - shiftCount;
2416 n = shiftCount / integerPartWidth;
2417 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2419 tcAssign(srhs, rhs, parts);
2420 tcShiftLeft(srhs, parts, shiftCount);
2421 tcAssign(remainder, lhs, parts);
2422 tcSet(lhs, 0, parts);
2424 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2429 compare = tcCompare(remainder, srhs, parts);
2431 tcSubtract(remainder, srhs, 0, parts);
2435 if (shiftCount == 0)
2438 tcShiftRight(srhs, parts, 1);
2439 if ((mask >>= 1) == 0)
2440 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2446 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2447 There are no restrictions on COUNT. */
2449 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2451 unsigned int jump, shift;
2453 /* Jump is the inter-part jump; shift is is intra-part shift. */
2454 jump = count / integerPartWidth;
2455 shift = count % integerPartWidth;
2457 while (parts > jump) {
2462 /* dst[i] comes from the two parts src[i - jump] and, if we have
2463 an intra-part shift, src[i - jump - 1]. */
2464 part = dst[parts - jump];
2467 if (parts >= jump + 1)
2468 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2478 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2479 zero. There are no restrictions on COUNT. */
2481 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2483 unsigned int i, jump, shift;
2485 /* Jump is the inter-part jump; shift is is intra-part shift. */
2486 jump = count / integerPartWidth;
2487 shift = count % integerPartWidth;
2489 /* Perform the shift. This leaves the most significant COUNT bits
2490 of the result at zero. */
2491 for(i = 0; i < parts; i++) {
2494 if (i + jump >= parts) {
2497 part = dst[i + jump];
2500 if (i + jump + 1 < parts)
2501 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2509 /* Bitwise and of two bignums. */
2511 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2515 for(i = 0; i < parts; i++)
2519 /* Bitwise inclusive or of two bignums. */
2521 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2525 for(i = 0; i < parts; i++)
2529 /* Bitwise exclusive or of two bignums. */
2531 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2535 for(i = 0; i < parts; i++)
2539 /* Complement a bignum in-place. */
2541 APInt::tcComplement(integerPart *dst, unsigned int parts)
2545 for(i = 0; i < parts; i++)
2549 /* Comparison (unsigned) of two bignums. */
2551 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2556 if (lhs[parts] == rhs[parts])
2559 if (lhs[parts] > rhs[parts])
2568 /* Increment a bignum in-place, return the carry flag. */
2570 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2574 for(i = 0; i < parts; i++)
2581 /* Set the least significant BITS bits of a bignum, clear the
2584 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2590 while (bits > integerPartWidth) {
2591 dst[i++] = ~(integerPart) 0;
2592 bits -= integerPartWidth;
2596 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);