1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a class to represent arbitrary precision integer
11 // constant values and provide a variety of arithmetic operations on them.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "apint"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/Support/Debug.h"
19 #include "llvm/Support/MathExtras.h"
28 /// This enumeration just provides for internal constants used in this
31 MIN_INT_BITS = 1, ///< Minimum number of bits that can be specified
32 ///< Note that this must remain synchronized with IntegerType::MIN_INT_BITS
33 MAX_INT_BITS = (1<<23)-1 ///< Maximum number of bits that can be specified
34 ///< Note that this must remain synchronized with IntegerType::MAX_INT_BITS
37 /// A utility function for allocating memory, checking for allocation failures,
38 /// and ensuring the contents are zeroed.
39 inline static uint64_t* getClearedMemory(uint32_t numWords) {
40 uint64_t * result = new uint64_t[numWords];
41 assert(result && "APInt memory allocation fails!");
42 memset(result, 0, numWords * sizeof(uint64_t));
46 /// A utility function for allocating memory and checking for allocation
47 /// failure. The content is not zeroed.
48 inline static uint64_t* getMemory(uint32_t numWords) {
49 uint64_t * result = new uint64_t[numWords];
50 assert(result && "APInt memory allocation fails!");
54 APInt::APInt(uint32_t numBits, uint64_t val, bool isSigned)
55 : BitWidth(numBits), VAL(0) {
56 assert(BitWidth >= MIN_INT_BITS && "bitwidth too small");
57 assert(BitWidth <= MAX_INT_BITS && "bitwidth too large");
61 pVal = getClearedMemory(getNumWords());
63 if (isSigned && int64_t(val) < 0)
64 for (unsigned i = 1; i < getNumWords(); ++i)
70 APInt::APInt(uint32_t numBits, uint32_t numWords, const uint64_t bigVal[])
71 : BitWidth(numBits), VAL(0) {
72 assert(BitWidth >= MIN_INT_BITS && "bitwidth too small");
73 assert(BitWidth <= MAX_INT_BITS && "bitwidth too large");
74 assert(bigVal && "Null pointer detected!");
78 // Get memory, cleared to 0
79 pVal = getClearedMemory(getNumWords());
80 // Calculate the number of words to copy
81 uint32_t words = std::min<uint32_t>(numWords, getNumWords());
82 // Copy the words from bigVal to pVal
83 memcpy(pVal, bigVal, words * APINT_WORD_SIZE);
85 // Make sure unused high bits are cleared
89 APInt::APInt(uint32_t numbits, const char StrStart[], uint32_t slen,
91 : BitWidth(numbits), VAL(0) {
92 assert(BitWidth >= MIN_INT_BITS && "bitwidth too small");
93 assert(BitWidth <= MAX_INT_BITS && "bitwidth too large");
94 fromString(numbits, StrStart, slen, radix);
97 APInt::APInt(uint32_t numbits, const std::string& Val, uint8_t radix)
98 : BitWidth(numbits), VAL(0) {
99 assert(BitWidth >= MIN_INT_BITS && "bitwidth too small");
100 assert(BitWidth <= MAX_INT_BITS && "bitwidth too large");
101 assert(!Val.empty() && "String empty?");
102 fromString(numbits, Val.c_str(), Val.size(), radix);
105 APInt::APInt(const APInt& that)
106 : BitWidth(that.BitWidth), VAL(0) {
107 assert(BitWidth >= MIN_INT_BITS && "bitwidth too small");
108 assert(BitWidth <= MAX_INT_BITS && "bitwidth too large");
112 pVal = getMemory(getNumWords());
113 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
118 if (!isSingleWord() && pVal)
122 APInt& APInt::operator=(const APInt& RHS) {
123 // Don't do anything for X = X
127 // If the bitwidths are the same, we can avoid mucking with memory
128 if (BitWidth == RHS.getBitWidth()) {
132 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
137 if (RHS.isSingleWord())
141 pVal = getMemory(RHS.getNumWords());
142 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
144 else if (getNumWords() == RHS.getNumWords())
145 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
146 else if (RHS.isSingleWord()) {
151 pVal = getMemory(RHS.getNumWords());
152 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
154 BitWidth = RHS.BitWidth;
155 return clearUnusedBits();
158 APInt& APInt::operator=(uint64_t RHS) {
163 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);
165 return clearUnusedBits();
168 /// Profile - This method 'profiles' an APInt for use with FoldingSet.
169 void APInt::Profile(FoldingSetNodeID& ID) const {
170 if (isSingleWord()) {
175 uint32_t NumWords = getNumWords();
176 for (unsigned i = 0; i < NumWords; ++i)
177 ID.AddInteger(pVal[i]);
180 /// add_1 - This function adds a single "digit" integer, y, to the multiple
181 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
182 /// 1 is returned if there is a carry out, otherwise 0 is returned.
183 /// @returns the carry of the addition.
184 static bool add_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
185 for (uint32_t i = 0; i < len; ++i) {
188 y = 1; // Carry one to next digit.
190 y = 0; // No need to carry so exit early
197 /// @brief Prefix increment operator. Increments the APInt by one.
198 APInt& APInt::operator++() {
202 add_1(pVal, pVal, getNumWords(), 1);
203 return clearUnusedBits();
206 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
207 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
208 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
209 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
210 /// In other words, if y > x then this function returns 1, otherwise 0.
211 /// @returns the borrow out of the subtraction
212 static bool sub_1(uint64_t x[], uint32_t len, uint64_t y) {
213 for (uint32_t i = 0; i < len; ++i) {
217 y = 1; // We have to "borrow 1" from next "digit"
219 y = 0; // No need to borrow
220 break; // Remaining digits are unchanged so exit early
226 /// @brief Prefix decrement operator. Decrements the APInt by one.
227 APInt& APInt::operator--() {
231 sub_1(pVal, getNumWords(), 1);
232 return clearUnusedBits();
235 /// add - This function adds the integer array x to the integer array Y and
236 /// places the result in dest.
237 /// @returns the carry out from the addition
238 /// @brief General addition of 64-bit integer arrays
239 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
242 for (uint32_t i = 0; i< len; ++i) {
243 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
244 dest[i] = x[i] + y[i] + carry;
245 carry = dest[i] < limit || (carry && dest[i] == limit);
250 /// Adds the RHS APint to this APInt.
251 /// @returns this, after addition of RHS.
252 /// @brief Addition assignment operator.
253 APInt& APInt::operator+=(const APInt& RHS) {
254 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
258 add(pVal, pVal, RHS.pVal, getNumWords());
260 return clearUnusedBits();
263 /// Subtracts the integer array y from the integer array x
264 /// @returns returns the borrow out.
265 /// @brief Generalized subtraction of 64-bit integer arrays.
266 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
269 for (uint32_t i = 0; i < len; ++i) {
270 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
271 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
272 dest[i] = x_tmp - y[i];
277 /// Subtracts the RHS APInt from this APInt
278 /// @returns this, after subtraction
279 /// @brief Subtraction assignment operator.
280 APInt& APInt::operator-=(const APInt& RHS) {
281 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
285 sub(pVal, pVal, RHS.pVal, getNumWords());
286 return clearUnusedBits();
289 /// Multiplies an integer array, x by a a uint64_t integer and places the result
291 /// @returns the carry out of the multiplication.
292 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
293 static uint64_t mul_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
294 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
295 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
298 // For each digit of x.
299 for (uint32_t i = 0; i < len; ++i) {
300 // Split x into high and low words
301 uint64_t lx = x[i] & 0xffffffffULL;
302 uint64_t hx = x[i] >> 32;
303 // hasCarry - A flag to indicate if there is a carry to the next digit.
304 // hasCarry == 0, no carry
305 // hasCarry == 1, has carry
306 // hasCarry == 2, no carry and the calculation result == 0.
307 uint8_t hasCarry = 0;
308 dest[i] = carry + lx * ly;
309 // Determine if the add above introduces carry.
310 hasCarry = (dest[i] < carry) ? 1 : 0;
311 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
312 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
313 // (2^32 - 1) + 2^32 = 2^64.
314 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
316 carry += (lx * hy) & 0xffffffffULL;
317 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
318 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
319 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
324 /// Multiplies integer array x by integer array y and stores the result into
325 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
326 /// @brief Generalized multiplicate of integer arrays.
327 static void mul(uint64_t dest[], uint64_t x[], uint32_t xlen, uint64_t y[],
329 dest[xlen] = mul_1(dest, x, xlen, y[0]);
330 for (uint32_t i = 1; i < ylen; ++i) {
331 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
332 uint64_t carry = 0, lx = 0, hx = 0;
333 for (uint32_t j = 0; j < xlen; ++j) {
334 lx = x[j] & 0xffffffffULL;
336 // hasCarry - A flag to indicate if has carry.
337 // hasCarry == 0, no carry
338 // hasCarry == 1, has carry
339 // hasCarry == 2, no carry and the calculation result == 0.
340 uint8_t hasCarry = 0;
341 uint64_t resul = carry + lx * ly;
342 hasCarry = (resul < carry) ? 1 : 0;
343 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
344 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
346 carry += (lx * hy) & 0xffffffffULL;
347 resul = (carry << 32) | (resul & 0xffffffffULL);
349 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
350 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
351 ((lx * hy) >> 32) + hx * hy;
353 dest[i+xlen] = carry;
357 APInt& APInt::operator*=(const APInt& RHS) {
358 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
359 if (isSingleWord()) {
365 // Get some bit facts about LHS and check for zero
366 uint32_t lhsBits = getActiveBits();
367 uint32_t lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
372 // Get some bit facts about RHS and check for zero
373 uint32_t rhsBits = RHS.getActiveBits();
374 uint32_t rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
381 // Allocate space for the result
382 uint32_t destWords = rhsWords + lhsWords;
383 uint64_t *dest = getMemory(destWords);
385 // Perform the long multiply
386 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
388 // Copy result back into *this
390 uint32_t wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
391 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
393 // delete dest array and return
398 APInt& APInt::operator&=(const APInt& RHS) {
399 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
400 if (isSingleWord()) {
404 uint32_t numWords = getNumWords();
405 for (uint32_t i = 0; i < numWords; ++i)
406 pVal[i] &= RHS.pVal[i];
410 APInt& APInt::operator|=(const APInt& RHS) {
411 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
412 if (isSingleWord()) {
416 uint32_t numWords = getNumWords();
417 for (uint32_t i = 0; i < numWords; ++i)
418 pVal[i] |= RHS.pVal[i];
422 APInt& APInt::operator^=(const APInt& RHS) {
423 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
424 if (isSingleWord()) {
426 this->clearUnusedBits();
429 uint32_t numWords = getNumWords();
430 for (uint32_t i = 0; i < numWords; ++i)
431 pVal[i] ^= RHS.pVal[i];
432 return clearUnusedBits();
435 APInt APInt::operator&(const APInt& RHS) const {
436 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
438 return APInt(getBitWidth(), VAL & RHS.VAL);
440 uint32_t numWords = getNumWords();
441 uint64_t* val = getMemory(numWords);
442 for (uint32_t i = 0; i < numWords; ++i)
443 val[i] = pVal[i] & RHS.pVal[i];
444 return APInt(val, getBitWidth());
447 APInt APInt::operator|(const APInt& RHS) const {
448 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
450 return APInt(getBitWidth(), VAL | RHS.VAL);
452 uint32_t numWords = getNumWords();
453 uint64_t *val = getMemory(numWords);
454 for (uint32_t i = 0; i < numWords; ++i)
455 val[i] = pVal[i] | RHS.pVal[i];
456 return APInt(val, getBitWidth());
459 APInt APInt::operator^(const APInt& RHS) const {
460 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
462 return APInt(BitWidth, VAL ^ RHS.VAL);
464 uint32_t numWords = getNumWords();
465 uint64_t *val = getMemory(numWords);
466 for (uint32_t i = 0; i < numWords; ++i)
467 val[i] = pVal[i] ^ RHS.pVal[i];
469 // 0^0==1 so clear the high bits in case they got set.
470 return APInt(val, getBitWidth()).clearUnusedBits();
473 bool APInt::operator !() const {
477 for (uint32_t i = 0; i < getNumWords(); ++i)
483 APInt APInt::operator*(const APInt& RHS) const {
484 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
486 return APInt(BitWidth, VAL * RHS.VAL);
489 return Result.clearUnusedBits();
492 APInt APInt::operator+(const APInt& RHS) const {
493 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
495 return APInt(BitWidth, VAL + RHS.VAL);
496 APInt Result(BitWidth, 0);
497 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
498 return Result.clearUnusedBits();
501 APInt APInt::operator-(const APInt& RHS) const {
502 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
504 return APInt(BitWidth, VAL - RHS.VAL);
505 APInt Result(BitWidth, 0);
506 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
507 return Result.clearUnusedBits();
510 bool APInt::operator[](uint32_t bitPosition) const {
511 return (maskBit(bitPosition) &
512 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
515 bool APInt::operator==(const APInt& RHS) const {
516 assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
518 return VAL == RHS.VAL;
520 // Get some facts about the number of bits used in the two operands.
521 uint32_t n1 = getActiveBits();
522 uint32_t n2 = RHS.getActiveBits();
524 // If the number of bits isn't the same, they aren't equal
528 // If the number of bits fits in a word, we only need to compare the low word.
529 if (n1 <= APINT_BITS_PER_WORD)
530 return pVal[0] == RHS.pVal[0];
532 // Otherwise, compare everything
533 for (int i = whichWord(n1 - 1); i >= 0; --i)
534 if (pVal[i] != RHS.pVal[i])
539 bool APInt::operator==(uint64_t Val) const {
543 uint32_t n = getActiveBits();
544 if (n <= APINT_BITS_PER_WORD)
545 return pVal[0] == Val;
550 bool APInt::ult(const APInt& RHS) const {
551 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
553 return VAL < RHS.VAL;
555 // Get active bit length of both operands
556 uint32_t n1 = getActiveBits();
557 uint32_t n2 = RHS.getActiveBits();
559 // If magnitude of LHS is less than RHS, return true.
563 // If magnitude of RHS is greather than LHS, return false.
567 // If they bot fit in a word, just compare the low order word
568 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
569 return pVal[0] < RHS.pVal[0];
571 // Otherwise, compare all words
572 uint32_t topWord = whichWord(std::max(n1,n2)-1);
573 for (int i = topWord; i >= 0; --i) {
574 if (pVal[i] > RHS.pVal[i])
576 if (pVal[i] < RHS.pVal[i])
582 bool APInt::slt(const APInt& RHS) const {
583 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
584 if (isSingleWord()) {
585 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
586 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
587 return lhsSext < rhsSext;
592 bool lhsNeg = isNegative();
593 bool rhsNeg = rhs.isNegative();
595 // Sign bit is set so perform two's complement to make it positive
600 // Sign bit is set so perform two's complement to make it positive
605 // Now we have unsigned values to compare so do the comparison if necessary
606 // based on the negativeness of the values.
618 APInt& APInt::set(uint32_t bitPosition) {
620 VAL |= maskBit(bitPosition);
622 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
626 APInt& APInt::set() {
627 if (isSingleWord()) {
629 return clearUnusedBits();
632 // Set all the bits in all the words.
633 for (uint32_t i = 0; i < getNumWords(); ++i)
635 // Clear the unused ones
636 return clearUnusedBits();
639 /// Set the given bit to 0 whose position is given as "bitPosition".
640 /// @brief Set a given bit to 0.
641 APInt& APInt::clear(uint32_t bitPosition) {
643 VAL &= ~maskBit(bitPosition);
645 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
649 /// @brief Set every bit to 0.
650 APInt& APInt::clear() {
654 memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
658 /// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on
660 APInt APInt::operator~() const {
666 /// @brief Toggle every bit to its opposite value.
667 APInt& APInt::flip() {
668 if (isSingleWord()) {
670 return clearUnusedBits();
672 for (uint32_t i = 0; i < getNumWords(); ++i)
674 return clearUnusedBits();
677 /// Toggle a given bit to its opposite value whose position is given
678 /// as "bitPosition".
679 /// @brief Toggles a given bit to its opposite value.
680 APInt& APInt::flip(uint32_t bitPosition) {
681 assert(bitPosition < BitWidth && "Out of the bit-width range!");
682 if ((*this)[bitPosition]) clear(bitPosition);
683 else set(bitPosition);
687 uint32_t APInt::getBitsNeeded(const char* str, uint32_t slen, uint8_t radix) {
688 assert(str != 0 && "Invalid value string");
689 assert(slen > 0 && "Invalid string length");
691 // Each computation below needs to know if its negative
692 uint32_t isNegative = str[0] == '-';
697 // For radixes of power-of-two values, the bits required is accurately and
700 return slen + isNegative;
702 return slen * 3 + isNegative;
704 return slen * 4 + isNegative;
706 // Otherwise it must be radix == 10, the hard case
707 assert(radix == 10 && "Invalid radix");
709 // This is grossly inefficient but accurate. We could probably do something
710 // with a computation of roughly slen*64/20 and then adjust by the value of
711 // the first few digits. But, I'm not sure how accurate that could be.
713 // Compute a sufficient number of bits that is always large enough but might
714 // be too large. This avoids the assertion in the constructor.
715 uint32_t sufficient = slen*64/18;
717 // Convert to the actual binary value.
718 APInt tmp(sufficient, str, slen, radix);
720 // Compute how many bits are required.
721 return isNegative + tmp.logBase2() + 1;
724 uint64_t APInt::getHashValue() const {
725 // Put the bit width into the low order bits.
726 uint64_t hash = BitWidth;
728 // Add the sum of the words to the hash.
730 hash += VAL << 6; // clear separation of up to 64 bits
732 for (uint32_t i = 0; i < getNumWords(); ++i)
733 hash += pVal[i] << 6; // clear sepration of up to 64 bits
737 /// HiBits - This function returns the high "numBits" bits of this APInt.
738 APInt APInt::getHiBits(uint32_t numBits) const {
739 return APIntOps::lshr(*this, BitWidth - numBits);
742 /// LoBits - This function returns the low "numBits" bits of this APInt.
743 APInt APInt::getLoBits(uint32_t numBits) const {
744 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
748 bool APInt::isPowerOf2() const {
749 return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
752 uint32_t APInt::countLeadingZeros() const {
755 Count = CountLeadingZeros_64(VAL);
757 for (uint32_t i = getNumWords(); i > 0u; --i) {
759 Count += APINT_BITS_PER_WORD;
761 Count += CountLeadingZeros_64(pVal[i-1]);
766 uint32_t remainder = BitWidth % APINT_BITS_PER_WORD;
768 Count -= APINT_BITS_PER_WORD - remainder;
769 return std::min(Count, BitWidth);
772 static uint32_t countLeadingOnes_64(uint64_t V, uint32_t skip) {
776 while (V && (V & (1ULL << 63))) {
783 uint32_t APInt::countLeadingOnes() const {
785 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
787 uint32_t highWordBits = BitWidth % APINT_BITS_PER_WORD;
788 uint32_t shift = (highWordBits == 0 ? 0 : APINT_BITS_PER_WORD - highWordBits);
789 int i = getNumWords() - 1;
790 uint32_t Count = countLeadingOnes_64(pVal[i], shift);
791 if (Count == highWordBits) {
792 for (i--; i >= 0; --i) {
793 if (pVal[i] == -1ULL)
794 Count += APINT_BITS_PER_WORD;
796 Count += countLeadingOnes_64(pVal[i], 0);
804 uint32_t APInt::countTrailingZeros() const {
806 return std::min(uint32_t(CountTrailingZeros_64(VAL)), BitWidth);
809 for (; i < getNumWords() && pVal[i] == 0; ++i)
810 Count += APINT_BITS_PER_WORD;
811 if (i < getNumWords())
812 Count += CountTrailingZeros_64(pVal[i]);
813 return std::min(Count, BitWidth);
816 uint32_t APInt::countPopulation() const {
818 return CountPopulation_64(VAL);
820 for (uint32_t i = 0; i < getNumWords(); ++i)
821 Count += CountPopulation_64(pVal[i]);
825 APInt APInt::byteSwap() const {
826 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
828 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
829 else if (BitWidth == 32)
830 return APInt(BitWidth, ByteSwap_32(uint32_t(VAL)));
831 else if (BitWidth == 48) {
832 uint32_t Tmp1 = uint32_t(VAL >> 16);
833 Tmp1 = ByteSwap_32(Tmp1);
834 uint16_t Tmp2 = uint16_t(VAL);
835 Tmp2 = ByteSwap_16(Tmp2);
836 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
837 } else if (BitWidth == 64)
838 return APInt(BitWidth, ByteSwap_64(VAL));
840 APInt Result(BitWidth, 0);
841 char *pByte = (char*)Result.pVal;
842 for (uint32_t i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
844 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
845 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
851 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
853 APInt A = API1, B = API2;
856 B = APIntOps::urem(A, B);
862 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) {
869 // Get the sign bit from the highest order bit
870 bool isNeg = T.I >> 63;
872 // Get the 11-bit exponent and adjust for the 1023 bit bias
873 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
875 // If the exponent is negative, the value is < 0 so just return 0.
877 return APInt(width, 0u);
879 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
880 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
882 // If the exponent doesn't shift all bits out of the mantissa
884 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
885 APInt(width, mantissa >> (52 - exp));
887 // If the client didn't provide enough bits for us to shift the mantissa into
888 // then the result is undefined, just return 0
889 if (width <= exp - 52)
890 return APInt(width, 0);
892 // Otherwise, we have to shift the mantissa bits up to the right location
893 APInt Tmp(width, mantissa);
894 Tmp = Tmp.shl(exp - 52);
895 return isNeg ? -Tmp : Tmp;
898 /// RoundToDouble - This function convert this APInt to a double.
899 /// The layout for double is as following (IEEE Standard 754):
900 /// --------------------------------------
901 /// | Sign Exponent Fraction Bias |
902 /// |-------------------------------------- |
903 /// | 1[63] 11[62-52] 52[51-00] 1023 |
904 /// --------------------------------------
905 double APInt::roundToDouble(bool isSigned) const {
907 // Handle the simple case where the value is contained in one uint64_t.
908 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
910 int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
916 // Determine if the value is negative.
917 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
919 // Construct the absolute value if we're negative.
920 APInt Tmp(isNeg ? -(*this) : (*this));
922 // Figure out how many bits we're using.
923 uint32_t n = Tmp.getActiveBits();
925 // The exponent (without bias normalization) is just the number of bits
926 // we are using. Note that the sign bit is gone since we constructed the
930 // Return infinity for exponent overflow
932 if (!isSigned || !isNeg)
933 return std::numeric_limits<double>::infinity();
935 return -std::numeric_limits<double>::infinity();
937 exp += 1023; // Increment for 1023 bias
939 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
940 // extract the high 52 bits from the correct words in pVal.
942 unsigned hiWord = whichWord(n-1);
944 mantissa = Tmp.pVal[0];
946 mantissa >>= n - 52; // shift down, we want the top 52 bits.
948 assert(hiWord > 0 && "huh?");
949 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
950 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
951 mantissa = hibits | lobits;
954 // The leading bit of mantissa is implicit, so get rid of it.
955 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
960 T.I = sign | (exp << 52) | mantissa;
964 // Truncate to new width.
965 APInt &APInt::trunc(uint32_t width) {
966 assert(width < BitWidth && "Invalid APInt Truncate request");
967 assert(width >= MIN_INT_BITS && "Can't truncate to 0 bits");
968 uint32_t wordsBefore = getNumWords();
970 uint32_t wordsAfter = getNumWords();
971 if (wordsBefore != wordsAfter) {
972 if (wordsAfter == 1) {
973 uint64_t *tmp = pVal;
977 uint64_t *newVal = getClearedMemory(wordsAfter);
978 for (uint32_t i = 0; i < wordsAfter; ++i)
984 return clearUnusedBits();
987 // Sign extend to a new width.
988 APInt &APInt::sext(uint32_t width) {
989 assert(width > BitWidth && "Invalid APInt SignExtend request");
990 assert(width <= MAX_INT_BITS && "Too many bits");
991 // If the sign bit isn't set, this is the same as zext.
997 // The sign bit is set. First, get some facts
998 uint32_t wordsBefore = getNumWords();
999 uint32_t wordBits = BitWidth % APINT_BITS_PER_WORD;
1001 uint32_t wordsAfter = getNumWords();
1003 // Mask the high order word appropriately
1004 if (wordsBefore == wordsAfter) {
1005 uint32_t newWordBits = width % APINT_BITS_PER_WORD;
1006 // The extension is contained to the wordsBefore-1th word.
1007 uint64_t mask = ~0ULL;
1009 mask >>= APINT_BITS_PER_WORD - newWordBits;
1011 if (wordsBefore == 1)
1014 pVal[wordsBefore-1] |= mask;
1015 return clearUnusedBits();
1018 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
1019 uint64_t *newVal = getMemory(wordsAfter);
1020 if (wordsBefore == 1)
1021 newVal[0] = VAL | mask;
1023 for (uint32_t i = 0; i < wordsBefore; ++i)
1024 newVal[i] = pVal[i];
1025 newVal[wordsBefore-1] |= mask;
1027 for (uint32_t i = wordsBefore; i < wordsAfter; i++)
1029 if (wordsBefore != 1)
1032 return clearUnusedBits();
1035 // Zero extend to a new width.
1036 APInt &APInt::zext(uint32_t width) {
1037 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1038 assert(width <= MAX_INT_BITS && "Too many bits");
1039 uint32_t wordsBefore = getNumWords();
1041 uint32_t wordsAfter = getNumWords();
1042 if (wordsBefore != wordsAfter) {
1043 uint64_t *newVal = getClearedMemory(wordsAfter);
1044 if (wordsBefore == 1)
1047 for (uint32_t i = 0; i < wordsBefore; ++i)
1048 newVal[i] = pVal[i];
1049 if (wordsBefore != 1)
1056 APInt &APInt::zextOrTrunc(uint32_t width) {
1057 if (BitWidth < width)
1059 if (BitWidth > width)
1060 return trunc(width);
1064 APInt &APInt::sextOrTrunc(uint32_t width) {
1065 if (BitWidth < width)
1067 if (BitWidth > width)
1068 return trunc(width);
1072 /// Arithmetic right-shift this APInt by shiftAmt.
1073 /// @brief Arithmetic right-shift function.
1074 APInt APInt::ashr(uint32_t shiftAmt) const {
1075 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1076 // Handle a degenerate case
1080 // Handle single word shifts with built-in ashr
1081 if (isSingleWord()) {
1082 if (shiftAmt == BitWidth)
1083 return APInt(BitWidth, 0); // undefined
1085 uint32_t SignBit = APINT_BITS_PER_WORD - BitWidth;
1086 return APInt(BitWidth,
1087 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1091 // If all the bits were shifted out, the result is, technically, undefined.
1092 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1093 // issues in the algorithm below.
1094 if (shiftAmt == BitWidth) {
1096 return APInt(BitWidth, -1ULL);
1098 return APInt(BitWidth, 0);
1101 // Create some space for the result.
1102 uint64_t * val = new uint64_t[getNumWords()];
1104 // Compute some values needed by the following shift algorithms
1105 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1106 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1107 uint32_t breakWord = getNumWords() - 1 - offset; // last word affected
1108 uint32_t bitsInWord = whichBit(BitWidth); // how many bits in last word?
1109 if (bitsInWord == 0)
1110 bitsInWord = APINT_BITS_PER_WORD;
1112 // If we are shifting whole words, just move whole words
1113 if (wordShift == 0) {
1114 // Move the words containing significant bits
1115 for (uint32_t i = 0; i <= breakWord; ++i)
1116 val[i] = pVal[i+offset]; // move whole word
1118 // Adjust the top significant word for sign bit fill, if negative
1120 if (bitsInWord < APINT_BITS_PER_WORD)
1121 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1123 // Shift the low order words
1124 for (uint32_t i = 0; i < breakWord; ++i) {
1125 // This combines the shifted corresponding word with the low bits from
1126 // the next word (shifted into this word's high bits).
1127 val[i] = (pVal[i+offset] >> wordShift) |
1128 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1131 // Shift the break word. In this case there are no bits from the next word
1132 // to include in this word.
1133 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1135 // Deal with sign extenstion in the break word, and possibly the word before
1138 if (wordShift > bitsInWord) {
1141 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1142 val[breakWord] |= ~0ULL;
1144 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1148 // Remaining words are 0 or -1, just assign them.
1149 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1150 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1152 return APInt(val, BitWidth).clearUnusedBits();
1155 /// Logical right-shift this APInt by shiftAmt.
1156 /// @brief Logical right-shift function.
1157 APInt APInt::lshr(uint32_t shiftAmt) const {
1158 if (isSingleWord()) {
1159 if (shiftAmt == BitWidth)
1160 return APInt(BitWidth, 0);
1162 return APInt(BitWidth, this->VAL >> shiftAmt);
1165 // If all the bits were shifted out, the result is 0. This avoids issues
1166 // with shifting by the size of the integer type, which produces undefined
1167 // results. We define these "undefined results" to always be 0.
1168 if (shiftAmt == BitWidth)
1169 return APInt(BitWidth, 0);
1171 // If none of the bits are shifted out, the result is *this. This avoids
1172 // issues with shifting byt he size of the integer type, which produces
1173 // undefined results in the code below. This is also an optimization.
1177 // Create some space for the result.
1178 uint64_t * val = new uint64_t[getNumWords()];
1180 // If we are shifting less than a word, compute the shift with a simple carry
1181 if (shiftAmt < APINT_BITS_PER_WORD) {
1183 for (int i = getNumWords()-1; i >= 0; --i) {
1184 val[i] = (pVal[i] >> shiftAmt) | carry;
1185 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1187 return APInt(val, BitWidth).clearUnusedBits();
1190 // Compute some values needed by the remaining shift algorithms
1191 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1192 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1194 // If we are shifting whole words, just move whole words
1195 if (wordShift == 0) {
1196 for (uint32_t i = 0; i < getNumWords() - offset; ++i)
1197 val[i] = pVal[i+offset];
1198 for (uint32_t i = getNumWords()-offset; i < getNumWords(); i++)
1200 return APInt(val,BitWidth).clearUnusedBits();
1203 // Shift the low order words
1204 uint32_t breakWord = getNumWords() - offset -1;
1205 for (uint32_t i = 0; i < breakWord; ++i)
1206 val[i] = (pVal[i+offset] >> wordShift) |
1207 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1208 // Shift the break word.
1209 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1211 // Remaining words are 0
1212 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1214 return APInt(val, BitWidth).clearUnusedBits();
1217 /// Left-shift this APInt by shiftAmt.
1218 /// @brief Left-shift function.
1219 APInt APInt::shl(uint32_t shiftAmt) const {
1220 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1221 if (isSingleWord()) {
1222 if (shiftAmt == BitWidth)
1223 return APInt(BitWidth, 0); // avoid undefined shift results
1224 return APInt(BitWidth, VAL << shiftAmt);
1227 // If all the bits were shifted out, the result is 0. This avoids issues
1228 // with shifting by the size of the integer type, which produces undefined
1229 // results. We define these "undefined results" to always be 0.
1230 if (shiftAmt == BitWidth)
1231 return APInt(BitWidth, 0);
1233 // If none of the bits are shifted out, the result is *this. This avoids a
1234 // lshr by the words size in the loop below which can produce incorrect
1235 // results. It also avoids the expensive computation below for a common case.
1239 // Create some space for the result.
1240 uint64_t * val = new uint64_t[getNumWords()];
1242 // If we are shifting less than a word, do it the easy way
1243 if (shiftAmt < APINT_BITS_PER_WORD) {
1245 for (uint32_t i = 0; i < getNumWords(); i++) {
1246 val[i] = pVal[i] << shiftAmt | carry;
1247 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1249 return APInt(val, BitWidth).clearUnusedBits();
1252 // Compute some values needed by the remaining shift algorithms
1253 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1254 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1256 // If we are shifting whole words, just move whole words
1257 if (wordShift == 0) {
1258 for (uint32_t i = 0; i < offset; i++)
1260 for (uint32_t i = offset; i < getNumWords(); i++)
1261 val[i] = pVal[i-offset];
1262 return APInt(val,BitWidth).clearUnusedBits();
1265 // Copy whole words from this to Result.
1266 uint32_t i = getNumWords() - 1;
1267 for (; i > offset; --i)
1268 val[i] = pVal[i-offset] << wordShift |
1269 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1270 val[offset] = pVal[0] << wordShift;
1271 for (i = 0; i < offset; ++i)
1273 return APInt(val, BitWidth).clearUnusedBits();
1276 APInt APInt::rotl(uint32_t rotateAmt) const {
1279 // Don't get too fancy, just use existing shift/or facilities
1283 lo.lshr(BitWidth - rotateAmt);
1287 APInt APInt::rotr(uint32_t rotateAmt) const {
1290 // Don't get too fancy, just use existing shift/or facilities
1294 hi.shl(BitWidth - rotateAmt);
1298 // Square Root - this method computes and returns the square root of "this".
1299 // Three mechanisms are used for computation. For small values (<= 5 bits),
1300 // a table lookup is done. This gets some performance for common cases. For
1301 // values using less than 52 bits, the value is converted to double and then
1302 // the libc sqrt function is called. The result is rounded and then converted
1303 // back to a uint64_t which is then used to construct the result. Finally,
1304 // the Babylonian method for computing square roots is used.
1305 APInt APInt::sqrt() const {
1307 // Determine the magnitude of the value.
1308 uint32_t magnitude = getActiveBits();
1310 // Use a fast table for some small values. This also gets rid of some
1311 // rounding errors in libc sqrt for small values.
1312 if (magnitude <= 5) {
1313 static const uint8_t results[32] = {
1316 /* 3- 6 */ 2, 2, 2, 2,
1317 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1318 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1319 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1322 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1325 // If the magnitude of the value fits in less than 52 bits (the precision of
1326 // an IEEE double precision floating point value), then we can use the
1327 // libc sqrt function which will probably use a hardware sqrt computation.
1328 // This should be faster than the algorithm below.
1329 if (magnitude < 52) {
1331 // Amazingly, VC++ doesn't have round().
1332 return APInt(BitWidth,
1333 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1335 return APInt(BitWidth,
1336 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1340 // Okay, all the short cuts are exhausted. We must compute it. The following
1341 // is a classical Babylonian method for computing the square root. This code
1342 // was adapted to APINt from a wikipedia article on such computations.
1343 // See http://www.wikipedia.org/ and go to the page named
1344 // Calculate_an_integer_square_root.
1345 uint32_t nbits = BitWidth, i = 4;
1346 APInt testy(BitWidth, 16);
1347 APInt x_old(BitWidth, 1);
1348 APInt x_new(BitWidth, 0);
1349 APInt two(BitWidth, 2);
1351 // Select a good starting value using binary logarithms.
1352 for (;; i += 2, testy = testy.shl(2))
1353 if (i >= nbits || this->ule(testy)) {
1354 x_old = x_old.shl(i / 2);
1358 // Use the Babylonian method to arrive at the integer square root:
1360 x_new = (this->udiv(x_old) + x_old).udiv(two);
1361 if (x_old.ule(x_new))
1366 // Make sure we return the closest approximation
1367 // NOTE: The rounding calculation below is correct. It will produce an
1368 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1369 // determined to be a rounding issue with pari/gp as it begins to use a
1370 // floating point representation after 192 bits. There are no discrepancies
1371 // between this algorithm and pari/gp for bit widths < 192 bits.
1372 APInt square(x_old * x_old);
1373 APInt nextSquare((x_old + 1) * (x_old +1));
1374 if (this->ult(square))
1376 else if (this->ule(nextSquare)) {
1377 APInt midpoint((nextSquare - square).udiv(two));
1378 APInt offset(*this - square);
1379 if (offset.ult(midpoint))
1384 assert(0 && "Error in APInt::sqrt computation");
1388 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1389 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1390 /// variables here have the same names as in the algorithm. Comments explain
1391 /// the algorithm and any deviation from it.
1392 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1393 uint32_t m, uint32_t n) {
1394 assert(u && "Must provide dividend");
1395 assert(v && "Must provide divisor");
1396 assert(q && "Must provide quotient");
1397 assert(u != v && u != q && v != q && "Must us different memory");
1398 assert(n>1 && "n must be > 1");
1400 // Knuth uses the value b as the base of the number system. In our case b
1401 // is 2^31 so we just set it to -1u.
1402 uint64_t b = uint64_t(1) << 32;
1404 DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n');
1405 DEBUG(cerr << "KnuthDiv: original:");
1406 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1407 DEBUG(cerr << " by");
1408 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1409 DEBUG(cerr << '\n');
1410 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1411 // u and v by d. Note that we have taken Knuth's advice here to use a power
1412 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1413 // 2 allows us to shift instead of multiply and it is easy to determine the
1414 // shift amount from the leading zeros. We are basically normalizing the u
1415 // and v so that its high bits are shifted to the top of v's range without
1416 // overflow. Note that this can require an extra word in u so that u must
1417 // be of length m+n+1.
1418 uint32_t shift = CountLeadingZeros_32(v[n-1]);
1419 uint32_t v_carry = 0;
1420 uint32_t u_carry = 0;
1422 for (uint32_t i = 0; i < m+n; ++i) {
1423 uint32_t u_tmp = u[i] >> (32 - shift);
1424 u[i] = (u[i] << shift) | u_carry;
1427 for (uint32_t i = 0; i < n; ++i) {
1428 uint32_t v_tmp = v[i] >> (32 - shift);
1429 v[i] = (v[i] << shift) | v_carry;
1434 DEBUG(cerr << "KnuthDiv: normal:");
1435 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1436 DEBUG(cerr << " by");
1437 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1438 DEBUG(cerr << '\n');
1440 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1443 DEBUG(cerr << "KnuthDiv: quotient digit #" << j << '\n');
1444 // D3. [Calculate q'.].
1445 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1446 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1447 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1448 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1449 // on v[n-2] determines at high speed most of the cases in which the trial
1450 // value qp is one too large, and it eliminates all cases where qp is two
1452 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1453 DEBUG(cerr << "KnuthDiv: dividend == " << dividend << '\n');
1454 uint64_t qp = dividend / v[n-1];
1455 uint64_t rp = dividend % v[n-1];
1456 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1459 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1462 DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1464 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1465 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1466 // consists of a simple multiplication by a one-place number, combined with
1469 for (uint32_t i = 0; i < n; ++i) {
1470 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1471 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1472 bool borrow = subtrahend > u_tmp;
1473 DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp
1474 << ", subtrahend == " << subtrahend
1475 << ", borrow = " << borrow << '\n');
1477 uint64_t result = u_tmp - subtrahend;
1479 u[k++] = result & (b-1); // subtract low word
1480 u[k++] = result >> 32; // subtract high word
1481 while (borrow && k <= m+n) { // deal with borrow to the left
1487 DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1490 DEBUG(cerr << "KnuthDiv: after subtraction:");
1491 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1492 DEBUG(cerr << '\n');
1493 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1494 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1495 // true value plus b**(n+1), namely as the b's complement of
1496 // the true value, and a "borrow" to the left should be remembered.
1499 bool carry = true; // true because b's complement is "complement + 1"
1500 for (uint32_t i = 0; i <= m+n; ++i) {
1501 u[i] = ~u[i] + carry; // b's complement
1502 carry = carry && u[i] == 0;
1505 DEBUG(cerr << "KnuthDiv: after complement:");
1506 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1507 DEBUG(cerr << '\n');
1509 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1510 // negative, go to step D6; otherwise go on to step D7.
1513 // D6. [Add back]. The probability that this step is necessary is very
1514 // small, on the order of only 2/b. Make sure that test data accounts for
1515 // this possibility. Decrease q[j] by 1
1517 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1518 // A carry will occur to the left of u[j+n], and it should be ignored
1519 // since it cancels with the borrow that occurred in D4.
1521 for (uint32_t i = 0; i < n; i++) {
1522 uint32_t limit = std::min(u[j+i],v[i]);
1523 u[j+i] += v[i] + carry;
1524 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1528 DEBUG(cerr << "KnuthDiv: after correction:");
1529 DEBUG(for (int i = m+n; i >=0; i--) cerr <<" " << u[i]);
1530 DEBUG(cerr << "\nKnuthDiv: digit result = " << q[j] << '\n');
1532 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1535 DEBUG(cerr << "KnuthDiv: quotient:");
1536 DEBUG(for (int i = m; i >=0; i--) cerr <<" " << q[i]);
1537 DEBUG(cerr << '\n');
1539 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1540 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1541 // compute the remainder (urem uses this).
1543 // The value d is expressed by the "shift" value above since we avoided
1544 // multiplication by d by using a shift left. So, all we have to do is
1545 // shift right here. In order to mak
1548 DEBUG(cerr << "KnuthDiv: remainder:");
1549 for (int i = n-1; i >= 0; i--) {
1550 r[i] = (u[i] >> shift) | carry;
1551 carry = u[i] << (32 - shift);
1552 DEBUG(cerr << " " << r[i]);
1555 for (int i = n-1; i >= 0; i--) {
1557 DEBUG(cerr << " " << r[i]);
1560 DEBUG(cerr << '\n');
1562 DEBUG(cerr << std::setbase(10) << '\n');
1565 void APInt::divide(const APInt LHS, uint32_t lhsWords,
1566 const APInt &RHS, uint32_t rhsWords,
1567 APInt *Quotient, APInt *Remainder)
1569 assert(lhsWords >= rhsWords && "Fractional result");
1571 // First, compose the values into an array of 32-bit words instead of
1572 // 64-bit words. This is a necessity of both the "short division" algorithm
1573 // and the the Knuth "classical algorithm" which requires there to be native
1574 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1575 // can't use 64-bit operands here because we don't have native results of
1576 // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't
1577 // work on large-endian machines.
1578 uint64_t mask = ~0ull >> (sizeof(uint32_t)*8);
1579 uint32_t n = rhsWords * 2;
1580 uint32_t m = (lhsWords * 2) - n;
1582 // Allocate space for the temporary values we need either on the stack, if
1583 // it will fit, or on the heap if it won't.
1584 uint32_t SPACE[128];
1589 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1592 Q = &SPACE[(m+n+1) + n];
1594 R = &SPACE[(m+n+1) + n + (m+n)];
1596 U = new uint32_t[m + n + 1];
1597 V = new uint32_t[n];
1598 Q = new uint32_t[m+n];
1600 R = new uint32_t[n];
1603 // Initialize the dividend
1604 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1605 for (unsigned i = 0; i < lhsWords; ++i) {
1606 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1607 U[i * 2] = tmp & mask;
1608 U[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1610 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1612 // Initialize the divisor
1613 memset(V, 0, (n)*sizeof(uint32_t));
1614 for (unsigned i = 0; i < rhsWords; ++i) {
1615 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1616 V[i * 2] = tmp & mask;
1617 V[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1620 // initialize the quotient and remainder
1621 memset(Q, 0, (m+n) * sizeof(uint32_t));
1623 memset(R, 0, n * sizeof(uint32_t));
1625 // Now, adjust m and n for the Knuth division. n is the number of words in
1626 // the divisor. m is the number of words by which the dividend exceeds the
1627 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1628 // contain any zero words or the Knuth algorithm fails.
1629 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1633 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1636 // If we're left with only a single word for the divisor, Knuth doesn't work
1637 // so we implement the short division algorithm here. This is much simpler
1638 // and faster because we are certain that we can divide a 64-bit quantity
1639 // by a 32-bit quantity at hardware speed and short division is simply a
1640 // series of such operations. This is just like doing short division but we
1641 // are using base 2^32 instead of base 10.
1642 assert(n != 0 && "Divide by zero?");
1644 uint32_t divisor = V[0];
1645 uint32_t remainder = 0;
1646 for (int i = m+n-1; i >= 0; i--) {
1647 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1648 if (partial_dividend == 0) {
1651 } else if (partial_dividend < divisor) {
1653 remainder = partial_dividend;
1654 } else if (partial_dividend == divisor) {
1658 Q[i] = partial_dividend / divisor;
1659 remainder = partial_dividend - (Q[i] * divisor);
1665 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1667 KnuthDiv(U, V, Q, R, m, n);
1670 // If the caller wants the quotient
1672 // Set up the Quotient value's memory.
1673 if (Quotient->BitWidth != LHS.BitWidth) {
1674 if (Quotient->isSingleWord())
1677 delete [] Quotient->pVal;
1678 Quotient->BitWidth = LHS.BitWidth;
1679 if (!Quotient->isSingleWord())
1680 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1684 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1686 if (lhsWords == 1) {
1688 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1689 if (Quotient->isSingleWord())
1690 Quotient->VAL = tmp;
1692 Quotient->pVal[0] = tmp;
1694 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1695 for (unsigned i = 0; i < lhsWords; ++i)
1697 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1701 // If the caller wants the remainder
1703 // Set up the Remainder value's memory.
1704 if (Remainder->BitWidth != RHS.BitWidth) {
1705 if (Remainder->isSingleWord())
1708 delete [] Remainder->pVal;
1709 Remainder->BitWidth = RHS.BitWidth;
1710 if (!Remainder->isSingleWord())
1711 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1715 // The remainder is in R. Reconstitute the remainder into Remainder's low
1717 if (rhsWords == 1) {
1719 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1720 if (Remainder->isSingleWord())
1721 Remainder->VAL = tmp;
1723 Remainder->pVal[0] = tmp;
1725 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1726 for (unsigned i = 0; i < rhsWords; ++i)
1727 Remainder->pVal[i] =
1728 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1732 // Clean up the memory we allocated.
1733 if (U != &SPACE[0]) {
1741 APInt APInt::udiv(const APInt& RHS) const {
1742 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1744 // First, deal with the easy case
1745 if (isSingleWord()) {
1746 assert(RHS.VAL != 0 && "Divide by zero?");
1747 return APInt(BitWidth, VAL / RHS.VAL);
1750 // Get some facts about the LHS and RHS number of bits and words
1751 uint32_t rhsBits = RHS.getActiveBits();
1752 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1753 assert(rhsWords && "Divided by zero???");
1754 uint32_t lhsBits = this->getActiveBits();
1755 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1757 // Deal with some degenerate cases
1760 return APInt(BitWidth, 0);
1761 else if (lhsWords < rhsWords || this->ult(RHS)) {
1762 // X / Y ===> 0, iff X < Y
1763 return APInt(BitWidth, 0);
1764 } else if (*this == RHS) {
1766 return APInt(BitWidth, 1);
1767 } else if (lhsWords == 1 && rhsWords == 1) {
1768 // All high words are zero, just use native divide
1769 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1772 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1773 APInt Quotient(1,0); // to hold result.
1774 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1778 APInt APInt::urem(const APInt& RHS) const {
1779 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1780 if (isSingleWord()) {
1781 assert(RHS.VAL != 0 && "Remainder by zero?");
1782 return APInt(BitWidth, VAL % RHS.VAL);
1785 // Get some facts about the LHS
1786 uint32_t lhsBits = getActiveBits();
1787 uint32_t lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1789 // Get some facts about the RHS
1790 uint32_t rhsBits = RHS.getActiveBits();
1791 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1792 assert(rhsWords && "Performing remainder operation by zero ???");
1794 // Check the degenerate cases
1795 if (lhsWords == 0) {
1797 return APInt(BitWidth, 0);
1798 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1799 // X % Y ===> X, iff X < Y
1801 } else if (*this == RHS) {
1803 return APInt(BitWidth, 0);
1804 } else if (lhsWords == 1) {
1805 // All high words are zero, just use native remainder
1806 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1809 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1810 APInt Remainder(1,0);
1811 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1815 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1816 APInt &Quotient, APInt &Remainder) {
1817 // Get some size facts about the dividend and divisor
1818 uint32_t lhsBits = LHS.getActiveBits();
1819 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1820 uint32_t rhsBits = RHS.getActiveBits();
1821 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1823 // Check the degenerate cases
1824 if (lhsWords == 0) {
1825 Quotient = 0; // 0 / Y ===> 0
1826 Remainder = 0; // 0 % Y ===> 0
1830 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1831 Quotient = 0; // X / Y ===> 0, iff X < Y
1832 Remainder = LHS; // X % Y ===> X, iff X < Y
1837 Quotient = 1; // X / X ===> 1
1838 Remainder = 0; // X % X ===> 0;
1842 if (lhsWords == 1 && rhsWords == 1) {
1843 // There is only one word to consider so use the native versions.
1844 if (LHS.isSingleWord()) {
1845 Quotient = APInt(LHS.getBitWidth(), LHS.VAL / RHS.VAL);
1846 Remainder = APInt(LHS.getBitWidth(), LHS.VAL % RHS.VAL);
1848 Quotient = APInt(LHS.getBitWidth(), LHS.pVal[0] / RHS.pVal[0]);
1849 Remainder = APInt(LHS.getBitWidth(), LHS.pVal[0] % RHS.pVal[0]);
1854 // Okay, lets do it the long way
1855 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1858 void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen,
1860 // Check our assumptions here
1861 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1862 "Radix should be 2, 8, 10, or 16!");
1863 assert(str && "String is null?");
1864 bool isNeg = str[0] == '-';
1867 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
1868 assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width");
1869 assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width");
1870 assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width");
1873 if (!isSingleWord())
1874 pVal = getClearedMemory(getNumWords());
1876 // Figure out if we can shift instead of multiply
1877 uint32_t shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1879 // Set up an APInt for the digit to add outside the loop so we don't
1880 // constantly construct/destruct it.
1881 APInt apdigit(getBitWidth(), 0);
1882 APInt apradix(getBitWidth(), radix);
1884 // Enter digit traversal loop
1885 for (unsigned i = 0; i < slen; i++) {
1888 char cdigit = str[i];
1890 if (!isxdigit(cdigit))
1891 assert(0 && "Invalid hex digit in string");
1892 if (isdigit(cdigit))
1893 digit = cdigit - '0';
1894 else if (cdigit >= 'a')
1895 digit = cdigit - 'a' + 10;
1896 else if (cdigit >= 'A')
1897 digit = cdigit - 'A' + 10;
1899 assert(0 && "huh? we shouldn't get here");
1900 } else if (isdigit(cdigit)) {
1901 digit = cdigit - '0';
1903 assert(0 && "Invalid character in digit string");
1906 // Shift or multiply the value by the radix
1912 // Add in the digit we just interpreted
1913 if (apdigit.isSingleWord())
1914 apdigit.VAL = digit;
1916 apdigit.pVal[0] = digit;
1919 // If its negative, put it in two's complement form
1926 std::string APInt::toString(uint8_t radix, bool wantSigned) const {
1927 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1928 "Radix should be 2, 8, 10, or 16!");
1929 static const char *digits[] = {
1930 "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"
1933 uint32_t bits_used = getActiveBits();
1934 if (isSingleWord()) {
1936 const char *format = (radix == 10 ? (wantSigned ? "%lld" : "%llu") :
1937 (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0)));
1940 int64_t sextVal = (int64_t(VAL) << (APINT_BITS_PER_WORD-BitWidth)) >>
1941 (APINT_BITS_PER_WORD-BitWidth);
1942 sprintf(buf, format, sextVal);
1944 sprintf(buf, format, VAL);
1949 uint32_t bit = v & 1;
1951 buf[bits_used] = digits[bit][0];
1960 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
1961 // because the number of bits per digit (1,3 and 4 respectively) divides
1962 // equaly. We just shift until there value is zero.
1964 // First, check for a zero value and just short circuit the logic below.
1969 size_t insert_at = 0;
1970 if (wantSigned && this->isNegative()) {
1971 // They want to print the signed version and it is a negative value
1972 // Flip the bits and add one to turn it into the equivalent positive
1973 // value and put a '-' in the result.
1979 // Just shift tmp right for each digit width until it becomes zero
1980 uint32_t shift = (radix == 16 ? 4 : (radix == 8 ? 3 : 1));
1981 uint64_t mask = radix - 1;
1982 APInt zero(tmp.getBitWidth(), 0);
1983 while (tmp.ne(zero)) {
1984 unsigned digit = (tmp.isSingleWord() ? tmp.VAL : tmp.pVal[0]) & mask;
1985 result.insert(insert_at, digits[digit]);
1986 tmp = tmp.lshr(shift);
1993 APInt divisor(4, radix);
1994 APInt zero(tmp.getBitWidth(), 0);
1995 size_t insert_at = 0;
1996 if (wantSigned && tmp[BitWidth-1]) {
1997 // They want to print the signed version and it is a negative value
1998 // Flip the bits and add one to turn it into the equivalent positive
1999 // value and put a '-' in the result.
2005 if (tmp == APInt(tmp.getBitWidth(), 0))
2007 else while (tmp.ne(zero)) {
2009 APInt tmp2(tmp.getBitWidth(), 0);
2010 divide(tmp, tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2012 uint32_t digit = APdigit.getZExtValue();
2013 assert(digit < radix && "divide failed");
2014 result.insert(insert_at,digits[digit]);
2021 void APInt::dump() const
2023 cerr << "APInt(" << BitWidth << ")=" << std::setbase(16);
2026 else for (unsigned i = getNumWords(); i > 0; i--) {
2027 cerr << pVal[i-1] << " ";
2029 cerr << " U(" << this->toStringUnsigned(10) << ") S("
2030 << this->toStringSigned(10) << ")" << std::setbase(10);
2033 // This implements a variety of operations on a representation of
2034 // arbitrary precision, two's-complement, bignum integer values.
2036 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2037 and unrestricting assumption. */
2038 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2040 /* Some handy functions local to this file. */
2043 /* Returns the integer part with the least significant BITS set.
2044 BITS cannot be zero. */
2046 lowBitMask(unsigned int bits)
2048 assert (bits != 0 && bits <= integerPartWidth);
2050 return ~(integerPart) 0 >> (integerPartWidth - bits);
2053 /* Returns the value of the lower half of PART. */
2055 lowHalf(integerPart part)
2057 return part & lowBitMask(integerPartWidth / 2);
2060 /* Returns the value of the upper half of PART. */
2062 highHalf(integerPart part)
2064 return part >> (integerPartWidth / 2);
2067 /* Returns the bit number of the most significant set bit of a part.
2068 If the input number has no bits set -1U is returned. */
2070 partMSB(integerPart value)
2072 unsigned int n, msb;
2077 n = integerPartWidth / 2;
2092 /* Returns the bit number of the least significant set bit of a
2093 part. If the input number has no bits set -1U is returned. */
2095 partLSB(integerPart value)
2097 unsigned int n, lsb;
2102 lsb = integerPartWidth - 1;
2103 n = integerPartWidth / 2;
2118 /* Sets the least significant part of a bignum to the input value, and
2119 zeroes out higher parts. */
2121 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2128 for(i = 1; i < parts; i++)
2132 /* Assign one bignum to another. */
2134 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2138 for(i = 0; i < parts; i++)
2142 /* Returns true if a bignum is zero, false otherwise. */
2144 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2148 for(i = 0; i < parts; i++)
2155 /* Extract the given bit of a bignum; returns 0 or 1. */
2157 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2159 return(parts[bit / integerPartWidth]
2160 & ((integerPart) 1 << bit % integerPartWidth)) != 0;
2163 /* Set the given bit of a bignum. */
2165 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2167 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2170 /* Returns the bit number of the least significant set bit of a
2171 number. If the input number has no bits set -1U is returned. */
2173 APInt::tcLSB(const integerPart *parts, unsigned int n)
2175 unsigned int i, lsb;
2177 for(i = 0; i < n; i++) {
2178 if (parts[i] != 0) {
2179 lsb = partLSB(parts[i]);
2181 return lsb + i * integerPartWidth;
2188 /* Returns the bit number of the most significant set bit of a number.
2189 If the input number has no bits set -1U is returned. */
2191 APInt::tcMSB(const integerPart *parts, unsigned int n)
2198 if (parts[n] != 0) {
2199 msb = partMSB(parts[n]);
2201 return msb + n * integerPartWidth;
2208 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2209 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2210 the least significant bit of DST. All high bits above srcBITS in
2211 DST are zero-filled. */
2213 APInt::tcExtract(integerPart *dst, unsigned int dstCount, const integerPart *src,
2214 unsigned int srcBits, unsigned int srcLSB)
2216 unsigned int firstSrcPart, dstParts, shift, n;
2218 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2219 assert (dstParts <= dstCount);
2221 firstSrcPart = srcLSB / integerPartWidth;
2222 tcAssign (dst, src + firstSrcPart, dstParts);
2224 shift = srcLSB % integerPartWidth;
2225 tcShiftRight (dst, dstParts, shift);
2227 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2228 in DST. If this is less that srcBits, append the rest, else
2229 clear the high bits. */
2230 n = dstParts * integerPartWidth - shift;
2232 integerPart mask = lowBitMask (srcBits - n);
2233 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2234 << n % integerPartWidth);
2235 } else if (n > srcBits) {
2236 if (srcBits % integerPartWidth)
2237 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2240 /* Clear high parts. */
2241 while (dstParts < dstCount)
2242 dst[dstParts++] = 0;
2245 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2247 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2248 integerPart c, unsigned int parts)
2254 for(i = 0; i < parts; i++) {
2259 dst[i] += rhs[i] + 1;
2270 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2272 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2273 integerPart c, unsigned int parts)
2279 for(i = 0; i < parts; i++) {
2284 dst[i] -= rhs[i] + 1;
2295 /* Negate a bignum in-place. */
2297 APInt::tcNegate(integerPart *dst, unsigned int parts)
2299 tcComplement(dst, parts);
2300 tcIncrement(dst, parts);
2303 /* DST += SRC * MULTIPLIER + CARRY if add is true
2304 DST = SRC * MULTIPLIER + CARRY if add is false
2306 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2307 they must start at the same point, i.e. DST == SRC.
2309 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2310 returned. Otherwise DST is filled with the least significant
2311 DSTPARTS parts of the result, and if all of the omitted higher
2312 parts were zero return zero, otherwise overflow occurred and
2315 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2316 integerPart multiplier, integerPart carry,
2317 unsigned int srcParts, unsigned int dstParts,
2322 /* Otherwise our writes of DST kill our later reads of SRC. */
2323 assert(dst <= src || dst >= src + srcParts);
2324 assert(dstParts <= srcParts + 1);
2326 /* N loops; minimum of dstParts and srcParts. */
2327 n = dstParts < srcParts ? dstParts: srcParts;
2329 for(i = 0; i < n; i++) {
2330 integerPart low, mid, high, srcPart;
2332 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2334 This cannot overflow, because
2336 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2338 which is less than n^2. */
2342 if (multiplier == 0 || srcPart == 0) {
2346 low = lowHalf(srcPart) * lowHalf(multiplier);
2347 high = highHalf(srcPart) * highHalf(multiplier);
2349 mid = lowHalf(srcPart) * highHalf(multiplier);
2350 high += highHalf(mid);
2351 mid <<= integerPartWidth / 2;
2352 if (low + mid < low)
2356 mid = highHalf(srcPart) * lowHalf(multiplier);
2357 high += highHalf(mid);
2358 mid <<= integerPartWidth / 2;
2359 if (low + mid < low)
2363 /* Now add carry. */
2364 if (low + carry < low)
2370 /* And now DST[i], and store the new low part there. */
2371 if (low + dst[i] < low)
2381 /* Full multiplication, there is no overflow. */
2382 assert(i + 1 == dstParts);
2386 /* We overflowed if there is carry. */
2390 /* We would overflow if any significant unwritten parts would be
2391 non-zero. This is true if any remaining src parts are non-zero
2392 and the multiplier is non-zero. */
2394 for(; i < srcParts; i++)
2398 /* We fitted in the narrow destination. */
2403 /* DST = LHS * RHS, where DST has the same width as the operands and
2404 is filled with the least significant parts of the result. Returns
2405 one if overflow occurred, otherwise zero. DST must be disjoint
2406 from both operands. */
2408 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2409 const integerPart *rhs, unsigned int parts)
2414 assert(dst != lhs && dst != rhs);
2417 tcSet(dst, 0, parts);
2419 for(i = 0; i < parts; i++)
2420 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2426 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2427 operands. No overflow occurs. DST must be disjoint from both
2428 operands. Returns the number of parts required to hold the
2431 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2432 const integerPart *rhs, unsigned int lhsParts,
2433 unsigned int rhsParts)
2435 /* Put the narrower number on the LHS for less loops below. */
2436 if (lhsParts > rhsParts) {
2437 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2441 assert(dst != lhs && dst != rhs);
2443 tcSet(dst, 0, rhsParts);
2445 for(n = 0; n < lhsParts; n++)
2446 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2448 n = lhsParts + rhsParts;
2450 return n - (dst[n - 1] == 0);
2454 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2455 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2456 set REMAINDER to the remainder, return zero. i.e.
2458 OLD_LHS = RHS * LHS + REMAINDER
2460 SCRATCH is a bignum of the same size as the operands and result for
2461 use by the routine; its contents need not be initialized and are
2462 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2465 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2466 integerPart *remainder, integerPart *srhs,
2469 unsigned int n, shiftCount;
2472 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2474 shiftCount = tcMSB(rhs, parts) + 1;
2475 if (shiftCount == 0)
2478 shiftCount = parts * integerPartWidth - shiftCount;
2479 n = shiftCount / integerPartWidth;
2480 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2482 tcAssign(srhs, rhs, parts);
2483 tcShiftLeft(srhs, parts, shiftCount);
2484 tcAssign(remainder, lhs, parts);
2485 tcSet(lhs, 0, parts);
2487 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2492 compare = tcCompare(remainder, srhs, parts);
2494 tcSubtract(remainder, srhs, 0, parts);
2498 if (shiftCount == 0)
2501 tcShiftRight(srhs, parts, 1);
2502 if ((mask >>= 1) == 0)
2503 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2509 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2510 There are no restrictions on COUNT. */
2512 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2515 unsigned int jump, shift;
2517 /* Jump is the inter-part jump; shift is is intra-part shift. */
2518 jump = count / integerPartWidth;
2519 shift = count % integerPartWidth;
2521 while (parts > jump) {
2526 /* dst[i] comes from the two parts src[i - jump] and, if we have
2527 an intra-part shift, src[i - jump - 1]. */
2528 part = dst[parts - jump];
2531 if (parts >= jump + 1)
2532 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2543 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2544 zero. There are no restrictions on COUNT. */
2546 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2549 unsigned int i, jump, shift;
2551 /* Jump is the inter-part jump; shift is is intra-part shift. */
2552 jump = count / integerPartWidth;
2553 shift = count % integerPartWidth;
2555 /* Perform the shift. This leaves the most significant COUNT bits
2556 of the result at zero. */
2557 for(i = 0; i < parts; i++) {
2560 if (i + jump >= parts) {
2563 part = dst[i + jump];
2566 if (i + jump + 1 < parts)
2567 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2576 /* Bitwise and of two bignums. */
2578 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2582 for(i = 0; i < parts; i++)
2586 /* Bitwise inclusive or of two bignums. */
2588 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2592 for(i = 0; i < parts; i++)
2596 /* Bitwise exclusive or of two bignums. */
2598 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2602 for(i = 0; i < parts; i++)
2606 /* Complement a bignum in-place. */
2608 APInt::tcComplement(integerPart *dst, unsigned int parts)
2612 for(i = 0; i < parts; i++)
2616 /* Comparison (unsigned) of two bignums. */
2618 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2623 if (lhs[parts] == rhs[parts])
2626 if (lhs[parts] > rhs[parts])
2635 /* Increment a bignum in-place, return the carry flag. */
2637 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2641 for(i = 0; i < parts; i++)
2648 /* Set the least significant BITS bits of a bignum, clear the
2651 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2657 while (bits > integerPartWidth) {
2658 dst[i++] = ~(integerPart) 0;
2659 bits -= integerPartWidth;
2663 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);