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::countTrailingOnes() const {
818 return std::min(uint32_t(CountTrailingOnes_64(VAL)), BitWidth);
821 for (; i < getNumWords() && pVal[i] == -1; ++i)
822 Count += APINT_BITS_PER_WORD;
823 if (i < getNumWords())
824 Count += CountTrailingOnes_64(pVal[i]);
825 return std::min(Count, BitWidth);
828 uint32_t APInt::countPopulation() const {
830 return CountPopulation_64(VAL);
832 for (uint32_t i = 0; i < getNumWords(); ++i)
833 Count += CountPopulation_64(pVal[i]);
837 APInt APInt::byteSwap() const {
838 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
840 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
841 else if (BitWidth == 32)
842 return APInt(BitWidth, ByteSwap_32(uint32_t(VAL)));
843 else if (BitWidth == 48) {
844 uint32_t Tmp1 = uint32_t(VAL >> 16);
845 Tmp1 = ByteSwap_32(Tmp1);
846 uint16_t Tmp2 = uint16_t(VAL);
847 Tmp2 = ByteSwap_16(Tmp2);
848 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
849 } else if (BitWidth == 64)
850 return APInt(BitWidth, ByteSwap_64(VAL));
852 APInt Result(BitWidth, 0);
853 char *pByte = (char*)Result.pVal;
854 for (uint32_t i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
856 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
857 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
863 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
865 APInt A = API1, B = API2;
868 B = APIntOps::urem(A, B);
874 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) {
881 // Get the sign bit from the highest order bit
882 bool isNeg = T.I >> 63;
884 // Get the 11-bit exponent and adjust for the 1023 bit bias
885 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
887 // If the exponent is negative, the value is < 0 so just return 0.
889 return APInt(width, 0u);
891 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
892 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
894 // If the exponent doesn't shift all bits out of the mantissa
896 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
897 APInt(width, mantissa >> (52 - exp));
899 // If the client didn't provide enough bits for us to shift the mantissa into
900 // then the result is undefined, just return 0
901 if (width <= exp - 52)
902 return APInt(width, 0);
904 // Otherwise, we have to shift the mantissa bits up to the right location
905 APInt Tmp(width, mantissa);
906 Tmp = Tmp.shl(exp - 52);
907 return isNeg ? -Tmp : Tmp;
910 /// RoundToDouble - This function convert this APInt to a double.
911 /// The layout for double is as following (IEEE Standard 754):
912 /// --------------------------------------
913 /// | Sign Exponent Fraction Bias |
914 /// |-------------------------------------- |
915 /// | 1[63] 11[62-52] 52[51-00] 1023 |
916 /// --------------------------------------
917 double APInt::roundToDouble(bool isSigned) const {
919 // Handle the simple case where the value is contained in one uint64_t.
920 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
922 int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
928 // Determine if the value is negative.
929 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
931 // Construct the absolute value if we're negative.
932 APInt Tmp(isNeg ? -(*this) : (*this));
934 // Figure out how many bits we're using.
935 uint32_t n = Tmp.getActiveBits();
937 // The exponent (without bias normalization) is just the number of bits
938 // we are using. Note that the sign bit is gone since we constructed the
942 // Return infinity for exponent overflow
944 if (!isSigned || !isNeg)
945 return std::numeric_limits<double>::infinity();
947 return -std::numeric_limits<double>::infinity();
949 exp += 1023; // Increment for 1023 bias
951 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
952 // extract the high 52 bits from the correct words in pVal.
954 unsigned hiWord = whichWord(n-1);
956 mantissa = Tmp.pVal[0];
958 mantissa >>= n - 52; // shift down, we want the top 52 bits.
960 assert(hiWord > 0 && "huh?");
961 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
962 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
963 mantissa = hibits | lobits;
966 // The leading bit of mantissa is implicit, so get rid of it.
967 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
972 T.I = sign | (exp << 52) | mantissa;
976 // Truncate to new width.
977 APInt &APInt::trunc(uint32_t width) {
978 assert(width < BitWidth && "Invalid APInt Truncate request");
979 assert(width >= MIN_INT_BITS && "Can't truncate to 0 bits");
980 uint32_t wordsBefore = getNumWords();
982 uint32_t wordsAfter = getNumWords();
983 if (wordsBefore != wordsAfter) {
984 if (wordsAfter == 1) {
985 uint64_t *tmp = pVal;
989 uint64_t *newVal = getClearedMemory(wordsAfter);
990 for (uint32_t i = 0; i < wordsAfter; ++i)
996 return clearUnusedBits();
999 // Sign extend to a new width.
1000 APInt &APInt::sext(uint32_t width) {
1001 assert(width > BitWidth && "Invalid APInt SignExtend request");
1002 assert(width <= MAX_INT_BITS && "Too many bits");
1003 // If the sign bit isn't set, this is the same as zext.
1004 if (!isNegative()) {
1009 // The sign bit is set. First, get some facts
1010 uint32_t wordsBefore = getNumWords();
1011 uint32_t wordBits = BitWidth % APINT_BITS_PER_WORD;
1013 uint32_t wordsAfter = getNumWords();
1015 // Mask the high order word appropriately
1016 if (wordsBefore == wordsAfter) {
1017 uint32_t newWordBits = width % APINT_BITS_PER_WORD;
1018 // The extension is contained to the wordsBefore-1th word.
1019 uint64_t mask = ~0ULL;
1021 mask >>= APINT_BITS_PER_WORD - newWordBits;
1023 if (wordsBefore == 1)
1026 pVal[wordsBefore-1] |= mask;
1027 return clearUnusedBits();
1030 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
1031 uint64_t *newVal = getMemory(wordsAfter);
1032 if (wordsBefore == 1)
1033 newVal[0] = VAL | mask;
1035 for (uint32_t i = 0; i < wordsBefore; ++i)
1036 newVal[i] = pVal[i];
1037 newVal[wordsBefore-1] |= mask;
1039 for (uint32_t i = wordsBefore; i < wordsAfter; i++)
1041 if (wordsBefore != 1)
1044 return clearUnusedBits();
1047 // Zero extend to a new width.
1048 APInt &APInt::zext(uint32_t width) {
1049 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1050 assert(width <= MAX_INT_BITS && "Too many bits");
1051 uint32_t wordsBefore = getNumWords();
1053 uint32_t wordsAfter = getNumWords();
1054 if (wordsBefore != wordsAfter) {
1055 uint64_t *newVal = getClearedMemory(wordsAfter);
1056 if (wordsBefore == 1)
1059 for (uint32_t i = 0; i < wordsBefore; ++i)
1060 newVal[i] = pVal[i];
1061 if (wordsBefore != 1)
1068 APInt &APInt::zextOrTrunc(uint32_t width) {
1069 if (BitWidth < width)
1071 if (BitWidth > width)
1072 return trunc(width);
1076 APInt &APInt::sextOrTrunc(uint32_t width) {
1077 if (BitWidth < width)
1079 if (BitWidth > width)
1080 return trunc(width);
1084 /// Arithmetic right-shift this APInt by shiftAmt.
1085 /// @brief Arithmetic right-shift function.
1086 APInt APInt::ashr(uint32_t shiftAmt) const {
1087 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1088 // Handle a degenerate case
1092 // Handle single word shifts with built-in ashr
1093 if (isSingleWord()) {
1094 if (shiftAmt == BitWidth)
1095 return APInt(BitWidth, 0); // undefined
1097 uint32_t SignBit = APINT_BITS_PER_WORD - BitWidth;
1098 return APInt(BitWidth,
1099 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1103 // If all the bits were shifted out, the result is, technically, undefined.
1104 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1105 // issues in the algorithm below.
1106 if (shiftAmt == BitWidth) {
1108 return APInt(BitWidth, -1ULL);
1110 return APInt(BitWidth, 0);
1113 // Create some space for the result.
1114 uint64_t * val = new uint64_t[getNumWords()];
1116 // Compute some values needed by the following shift algorithms
1117 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1118 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1119 uint32_t breakWord = getNumWords() - 1 - offset; // last word affected
1120 uint32_t bitsInWord = whichBit(BitWidth); // how many bits in last word?
1121 if (bitsInWord == 0)
1122 bitsInWord = APINT_BITS_PER_WORD;
1124 // If we are shifting whole words, just move whole words
1125 if (wordShift == 0) {
1126 // Move the words containing significant bits
1127 for (uint32_t i = 0; i <= breakWord; ++i)
1128 val[i] = pVal[i+offset]; // move whole word
1130 // Adjust the top significant word for sign bit fill, if negative
1132 if (bitsInWord < APINT_BITS_PER_WORD)
1133 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1135 // Shift the low order words
1136 for (uint32_t i = 0; i < breakWord; ++i) {
1137 // This combines the shifted corresponding word with the low bits from
1138 // the next word (shifted into this word's high bits).
1139 val[i] = (pVal[i+offset] >> wordShift) |
1140 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1143 // Shift the break word. In this case there are no bits from the next word
1144 // to include in this word.
1145 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1147 // Deal with sign extenstion in the break word, and possibly the word before
1150 if (wordShift > bitsInWord) {
1153 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1154 val[breakWord] |= ~0ULL;
1156 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1160 // Remaining words are 0 or -1, just assign them.
1161 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1162 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1164 return APInt(val, BitWidth).clearUnusedBits();
1167 /// Logical right-shift this APInt by shiftAmt.
1168 /// @brief Logical right-shift function.
1169 APInt APInt::lshr(uint32_t shiftAmt) const {
1170 if (isSingleWord()) {
1171 if (shiftAmt == BitWidth)
1172 return APInt(BitWidth, 0);
1174 return APInt(BitWidth, this->VAL >> shiftAmt);
1177 // If all the bits were shifted out, the result is 0. This avoids issues
1178 // with shifting by the size of the integer type, which produces undefined
1179 // results. We define these "undefined results" to always be 0.
1180 if (shiftAmt == BitWidth)
1181 return APInt(BitWidth, 0);
1183 // If none of the bits are shifted out, the result is *this. This avoids
1184 // issues with shifting byt he size of the integer type, which produces
1185 // undefined results in the code below. This is also an optimization.
1189 // Create some space for the result.
1190 uint64_t * val = new uint64_t[getNumWords()];
1192 // If we are shifting less than a word, compute the shift with a simple carry
1193 if (shiftAmt < APINT_BITS_PER_WORD) {
1195 for (int i = getNumWords()-1; i >= 0; --i) {
1196 val[i] = (pVal[i] >> shiftAmt) | carry;
1197 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1199 return APInt(val, BitWidth).clearUnusedBits();
1202 // Compute some values needed by the remaining shift algorithms
1203 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1204 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1206 // If we are shifting whole words, just move whole words
1207 if (wordShift == 0) {
1208 for (uint32_t i = 0; i < getNumWords() - offset; ++i)
1209 val[i] = pVal[i+offset];
1210 for (uint32_t i = getNumWords()-offset; i < getNumWords(); i++)
1212 return APInt(val,BitWidth).clearUnusedBits();
1215 // Shift the low order words
1216 uint32_t breakWord = getNumWords() - offset -1;
1217 for (uint32_t i = 0; i < breakWord; ++i)
1218 val[i] = (pVal[i+offset] >> wordShift) |
1219 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1220 // Shift the break word.
1221 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1223 // Remaining words are 0
1224 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1226 return APInt(val, BitWidth).clearUnusedBits();
1229 /// Left-shift this APInt by shiftAmt.
1230 /// @brief Left-shift function.
1231 APInt APInt::shl(uint32_t shiftAmt) const {
1232 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1233 if (isSingleWord()) {
1234 if (shiftAmt == BitWidth)
1235 return APInt(BitWidth, 0); // avoid undefined shift results
1236 return APInt(BitWidth, VAL << shiftAmt);
1239 // If all the bits were shifted out, the result is 0. This avoids issues
1240 // with shifting by the size of the integer type, which produces undefined
1241 // results. We define these "undefined results" to always be 0.
1242 if (shiftAmt == BitWidth)
1243 return APInt(BitWidth, 0);
1245 // If none of the bits are shifted out, the result is *this. This avoids a
1246 // lshr by the words size in the loop below which can produce incorrect
1247 // results. It also avoids the expensive computation below for a common case.
1251 // Create some space for the result.
1252 uint64_t * val = new uint64_t[getNumWords()];
1254 // If we are shifting less than a word, do it the easy way
1255 if (shiftAmt < APINT_BITS_PER_WORD) {
1257 for (uint32_t i = 0; i < getNumWords(); i++) {
1258 val[i] = pVal[i] << shiftAmt | carry;
1259 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1261 return APInt(val, BitWidth).clearUnusedBits();
1264 // Compute some values needed by the remaining shift algorithms
1265 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1266 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1268 // If we are shifting whole words, just move whole words
1269 if (wordShift == 0) {
1270 for (uint32_t i = 0; i < offset; i++)
1272 for (uint32_t i = offset; i < getNumWords(); i++)
1273 val[i] = pVal[i-offset];
1274 return APInt(val,BitWidth).clearUnusedBits();
1277 // Copy whole words from this to Result.
1278 uint32_t i = getNumWords() - 1;
1279 for (; i > offset; --i)
1280 val[i] = pVal[i-offset] << wordShift |
1281 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1282 val[offset] = pVal[0] << wordShift;
1283 for (i = 0; i < offset; ++i)
1285 return APInt(val, BitWidth).clearUnusedBits();
1288 APInt APInt::rotl(uint32_t rotateAmt) const {
1291 // Don't get too fancy, just use existing shift/or facilities
1295 lo.lshr(BitWidth - rotateAmt);
1299 APInt APInt::rotr(uint32_t rotateAmt) const {
1302 // Don't get too fancy, just use existing shift/or facilities
1306 hi.shl(BitWidth - rotateAmt);
1310 // Square Root - this method computes and returns the square root of "this".
1311 // Three mechanisms are used for computation. For small values (<= 5 bits),
1312 // a table lookup is done. This gets some performance for common cases. For
1313 // values using less than 52 bits, the value is converted to double and then
1314 // the libc sqrt function is called. The result is rounded and then converted
1315 // back to a uint64_t which is then used to construct the result. Finally,
1316 // the Babylonian method for computing square roots is used.
1317 APInt APInt::sqrt() const {
1319 // Determine the magnitude of the value.
1320 uint32_t magnitude = getActiveBits();
1322 // Use a fast table for some small values. This also gets rid of some
1323 // rounding errors in libc sqrt for small values.
1324 if (magnitude <= 5) {
1325 static const uint8_t results[32] = {
1328 /* 3- 6 */ 2, 2, 2, 2,
1329 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1330 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1331 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1334 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1337 // If the magnitude of the value fits in less than 52 bits (the precision of
1338 // an IEEE double precision floating point value), then we can use the
1339 // libc sqrt function which will probably use a hardware sqrt computation.
1340 // This should be faster than the algorithm below.
1341 if (magnitude < 52) {
1343 // Amazingly, VC++ doesn't have round().
1344 return APInt(BitWidth,
1345 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1347 return APInt(BitWidth,
1348 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1352 // Okay, all the short cuts are exhausted. We must compute it. The following
1353 // is a classical Babylonian method for computing the square root. This code
1354 // was adapted to APINt from a wikipedia article on such computations.
1355 // See http://www.wikipedia.org/ and go to the page named
1356 // Calculate_an_integer_square_root.
1357 uint32_t nbits = BitWidth, i = 4;
1358 APInt testy(BitWidth, 16);
1359 APInt x_old(BitWidth, 1);
1360 APInt x_new(BitWidth, 0);
1361 APInt two(BitWidth, 2);
1363 // Select a good starting value using binary logarithms.
1364 for (;; i += 2, testy = testy.shl(2))
1365 if (i >= nbits || this->ule(testy)) {
1366 x_old = x_old.shl(i / 2);
1370 // Use the Babylonian method to arrive at the integer square root:
1372 x_new = (this->udiv(x_old) + x_old).udiv(two);
1373 if (x_old.ule(x_new))
1378 // Make sure we return the closest approximation
1379 // NOTE: The rounding calculation below is correct. It will produce an
1380 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1381 // determined to be a rounding issue with pari/gp as it begins to use a
1382 // floating point representation after 192 bits. There are no discrepancies
1383 // between this algorithm and pari/gp for bit widths < 192 bits.
1384 APInt square(x_old * x_old);
1385 APInt nextSquare((x_old + 1) * (x_old +1));
1386 if (this->ult(square))
1388 else if (this->ule(nextSquare)) {
1389 APInt midpoint((nextSquare - square).udiv(two));
1390 APInt offset(*this - square);
1391 if (offset.ult(midpoint))
1396 assert(0 && "Error in APInt::sqrt computation");
1400 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1401 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1402 /// variables here have the same names as in the algorithm. Comments explain
1403 /// the algorithm and any deviation from it.
1404 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1405 uint32_t m, uint32_t n) {
1406 assert(u && "Must provide dividend");
1407 assert(v && "Must provide divisor");
1408 assert(q && "Must provide quotient");
1409 assert(u != v && u != q && v != q && "Must us different memory");
1410 assert(n>1 && "n must be > 1");
1412 // Knuth uses the value b as the base of the number system. In our case b
1413 // is 2^31 so we just set it to -1u.
1414 uint64_t b = uint64_t(1) << 32;
1416 DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n');
1417 DEBUG(cerr << "KnuthDiv: original:");
1418 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1419 DEBUG(cerr << " by");
1420 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1421 DEBUG(cerr << '\n');
1422 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1423 // u and v by d. Note that we have taken Knuth's advice here to use a power
1424 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1425 // 2 allows us to shift instead of multiply and it is easy to determine the
1426 // shift amount from the leading zeros. We are basically normalizing the u
1427 // and v so that its high bits are shifted to the top of v's range without
1428 // overflow. Note that this can require an extra word in u so that u must
1429 // be of length m+n+1.
1430 uint32_t shift = CountLeadingZeros_32(v[n-1]);
1431 uint32_t v_carry = 0;
1432 uint32_t u_carry = 0;
1434 for (uint32_t i = 0; i < m+n; ++i) {
1435 uint32_t u_tmp = u[i] >> (32 - shift);
1436 u[i] = (u[i] << shift) | u_carry;
1439 for (uint32_t i = 0; i < n; ++i) {
1440 uint32_t v_tmp = v[i] >> (32 - shift);
1441 v[i] = (v[i] << shift) | v_carry;
1446 DEBUG(cerr << "KnuthDiv: normal:");
1447 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1448 DEBUG(cerr << " by");
1449 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1450 DEBUG(cerr << '\n');
1452 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1455 DEBUG(cerr << "KnuthDiv: quotient digit #" << j << '\n');
1456 // D3. [Calculate q'.].
1457 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1458 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1459 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1460 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1461 // on v[n-2] determines at high speed most of the cases in which the trial
1462 // value qp is one too large, and it eliminates all cases where qp is two
1464 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1465 DEBUG(cerr << "KnuthDiv: dividend == " << dividend << '\n');
1466 uint64_t qp = dividend / v[n-1];
1467 uint64_t rp = dividend % v[n-1];
1468 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1471 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1474 DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1476 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1477 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1478 // consists of a simple multiplication by a one-place number, combined with
1481 for (uint32_t i = 0; i < n; ++i) {
1482 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1483 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1484 bool borrow = subtrahend > u_tmp;
1485 DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp
1486 << ", subtrahend == " << subtrahend
1487 << ", borrow = " << borrow << '\n');
1489 uint64_t result = u_tmp - subtrahend;
1491 u[k++] = result & (b-1); // subtract low word
1492 u[k++] = result >> 32; // subtract high word
1493 while (borrow && k <= m+n) { // deal with borrow to the left
1499 DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1502 DEBUG(cerr << "KnuthDiv: after subtraction:");
1503 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1504 DEBUG(cerr << '\n');
1505 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1506 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1507 // true value plus b**(n+1), namely as the b's complement of
1508 // the true value, and a "borrow" to the left should be remembered.
1511 bool carry = true; // true because b's complement is "complement + 1"
1512 for (uint32_t i = 0; i <= m+n; ++i) {
1513 u[i] = ~u[i] + carry; // b's complement
1514 carry = carry && u[i] == 0;
1517 DEBUG(cerr << "KnuthDiv: after complement:");
1518 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1519 DEBUG(cerr << '\n');
1521 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1522 // negative, go to step D6; otherwise go on to step D7.
1525 // D6. [Add back]. The probability that this step is necessary is very
1526 // small, on the order of only 2/b. Make sure that test data accounts for
1527 // this possibility. Decrease q[j] by 1
1529 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1530 // A carry will occur to the left of u[j+n], and it should be ignored
1531 // since it cancels with the borrow that occurred in D4.
1533 for (uint32_t i = 0; i < n; i++) {
1534 uint32_t limit = std::min(u[j+i],v[i]);
1535 u[j+i] += v[i] + carry;
1536 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1540 DEBUG(cerr << "KnuthDiv: after correction:");
1541 DEBUG(for (int i = m+n; i >=0; i--) cerr <<" " << u[i]);
1542 DEBUG(cerr << "\nKnuthDiv: digit result = " << q[j] << '\n');
1544 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1547 DEBUG(cerr << "KnuthDiv: quotient:");
1548 DEBUG(for (int i = m; i >=0; i--) cerr <<" " << q[i]);
1549 DEBUG(cerr << '\n');
1551 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1552 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1553 // compute the remainder (urem uses this).
1555 // The value d is expressed by the "shift" value above since we avoided
1556 // multiplication by d by using a shift left. So, all we have to do is
1557 // shift right here. In order to mak
1560 DEBUG(cerr << "KnuthDiv: remainder:");
1561 for (int i = n-1; i >= 0; i--) {
1562 r[i] = (u[i] >> shift) | carry;
1563 carry = u[i] << (32 - shift);
1564 DEBUG(cerr << " " << r[i]);
1567 for (int i = n-1; i >= 0; i--) {
1569 DEBUG(cerr << " " << r[i]);
1572 DEBUG(cerr << '\n');
1574 DEBUG(cerr << std::setbase(10) << '\n');
1577 void APInt::divide(const APInt LHS, uint32_t lhsWords,
1578 const APInt &RHS, uint32_t rhsWords,
1579 APInt *Quotient, APInt *Remainder)
1581 assert(lhsWords >= rhsWords && "Fractional result");
1583 // First, compose the values into an array of 32-bit words instead of
1584 // 64-bit words. This is a necessity of both the "short division" algorithm
1585 // and the the Knuth "classical algorithm" which requires there to be native
1586 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1587 // can't use 64-bit operands here because we don't have native results of
1588 // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't
1589 // work on large-endian machines.
1590 uint64_t mask = ~0ull >> (sizeof(uint32_t)*8);
1591 uint32_t n = rhsWords * 2;
1592 uint32_t m = (lhsWords * 2) - n;
1594 // Allocate space for the temporary values we need either on the stack, if
1595 // it will fit, or on the heap if it won't.
1596 uint32_t SPACE[128];
1601 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1604 Q = &SPACE[(m+n+1) + n];
1606 R = &SPACE[(m+n+1) + n + (m+n)];
1608 U = new uint32_t[m + n + 1];
1609 V = new uint32_t[n];
1610 Q = new uint32_t[m+n];
1612 R = new uint32_t[n];
1615 // Initialize the dividend
1616 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1617 for (unsigned i = 0; i < lhsWords; ++i) {
1618 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1619 U[i * 2] = tmp & mask;
1620 U[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1622 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1624 // Initialize the divisor
1625 memset(V, 0, (n)*sizeof(uint32_t));
1626 for (unsigned i = 0; i < rhsWords; ++i) {
1627 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1628 V[i * 2] = tmp & mask;
1629 V[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1632 // initialize the quotient and remainder
1633 memset(Q, 0, (m+n) * sizeof(uint32_t));
1635 memset(R, 0, n * sizeof(uint32_t));
1637 // Now, adjust m and n for the Knuth division. n is the number of words in
1638 // the divisor. m is the number of words by which the dividend exceeds the
1639 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1640 // contain any zero words or the Knuth algorithm fails.
1641 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1645 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1648 // If we're left with only a single word for the divisor, Knuth doesn't work
1649 // so we implement the short division algorithm here. This is much simpler
1650 // and faster because we are certain that we can divide a 64-bit quantity
1651 // by a 32-bit quantity at hardware speed and short division is simply a
1652 // series of such operations. This is just like doing short division but we
1653 // are using base 2^32 instead of base 10.
1654 assert(n != 0 && "Divide by zero?");
1656 uint32_t divisor = V[0];
1657 uint32_t remainder = 0;
1658 for (int i = m+n-1; i >= 0; i--) {
1659 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1660 if (partial_dividend == 0) {
1663 } else if (partial_dividend < divisor) {
1665 remainder = partial_dividend;
1666 } else if (partial_dividend == divisor) {
1670 Q[i] = partial_dividend / divisor;
1671 remainder = partial_dividend - (Q[i] * divisor);
1677 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1679 KnuthDiv(U, V, Q, R, m, n);
1682 // If the caller wants the quotient
1684 // Set up the Quotient value's memory.
1685 if (Quotient->BitWidth != LHS.BitWidth) {
1686 if (Quotient->isSingleWord())
1689 delete [] Quotient->pVal;
1690 Quotient->BitWidth = LHS.BitWidth;
1691 if (!Quotient->isSingleWord())
1692 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1696 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1698 if (lhsWords == 1) {
1700 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1701 if (Quotient->isSingleWord())
1702 Quotient->VAL = tmp;
1704 Quotient->pVal[0] = tmp;
1706 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1707 for (unsigned i = 0; i < lhsWords; ++i)
1709 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1713 // If the caller wants the remainder
1715 // Set up the Remainder value's memory.
1716 if (Remainder->BitWidth != RHS.BitWidth) {
1717 if (Remainder->isSingleWord())
1720 delete [] Remainder->pVal;
1721 Remainder->BitWidth = RHS.BitWidth;
1722 if (!Remainder->isSingleWord())
1723 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1727 // The remainder is in R. Reconstitute the remainder into Remainder's low
1729 if (rhsWords == 1) {
1731 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1732 if (Remainder->isSingleWord())
1733 Remainder->VAL = tmp;
1735 Remainder->pVal[0] = tmp;
1737 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1738 for (unsigned i = 0; i < rhsWords; ++i)
1739 Remainder->pVal[i] =
1740 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1744 // Clean up the memory we allocated.
1745 if (U != &SPACE[0]) {
1753 APInt APInt::udiv(const APInt& RHS) const {
1754 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1756 // First, deal with the easy case
1757 if (isSingleWord()) {
1758 assert(RHS.VAL != 0 && "Divide by zero?");
1759 return APInt(BitWidth, VAL / RHS.VAL);
1762 // Get some facts about the LHS and RHS number of bits and words
1763 uint32_t rhsBits = RHS.getActiveBits();
1764 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1765 assert(rhsWords && "Divided by zero???");
1766 uint32_t lhsBits = this->getActiveBits();
1767 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1769 // Deal with some degenerate cases
1772 return APInt(BitWidth, 0);
1773 else if (lhsWords < rhsWords || this->ult(RHS)) {
1774 // X / Y ===> 0, iff X < Y
1775 return APInt(BitWidth, 0);
1776 } else if (*this == RHS) {
1778 return APInt(BitWidth, 1);
1779 } else if (lhsWords == 1 && rhsWords == 1) {
1780 // All high words are zero, just use native divide
1781 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1784 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1785 APInt Quotient(1,0); // to hold result.
1786 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1790 APInt APInt::urem(const APInt& RHS) const {
1791 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1792 if (isSingleWord()) {
1793 assert(RHS.VAL != 0 && "Remainder by zero?");
1794 return APInt(BitWidth, VAL % RHS.VAL);
1797 // Get some facts about the LHS
1798 uint32_t lhsBits = getActiveBits();
1799 uint32_t lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1801 // Get some facts about the RHS
1802 uint32_t rhsBits = RHS.getActiveBits();
1803 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1804 assert(rhsWords && "Performing remainder operation by zero ???");
1806 // Check the degenerate cases
1807 if (lhsWords == 0) {
1809 return APInt(BitWidth, 0);
1810 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1811 // X % Y ===> X, iff X < Y
1813 } else if (*this == RHS) {
1815 return APInt(BitWidth, 0);
1816 } else if (lhsWords == 1) {
1817 // All high words are zero, just use native remainder
1818 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1821 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1822 APInt Remainder(1,0);
1823 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1827 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1828 APInt &Quotient, APInt &Remainder) {
1829 // Get some size facts about the dividend and divisor
1830 uint32_t lhsBits = LHS.getActiveBits();
1831 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1832 uint32_t rhsBits = RHS.getActiveBits();
1833 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1835 // Check the degenerate cases
1836 if (lhsWords == 0) {
1837 Quotient = 0; // 0 / Y ===> 0
1838 Remainder = 0; // 0 % Y ===> 0
1842 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1843 Quotient = 0; // X / Y ===> 0, iff X < Y
1844 Remainder = LHS; // X % Y ===> X, iff X < Y
1849 Quotient = 1; // X / X ===> 1
1850 Remainder = 0; // X % X ===> 0;
1854 if (lhsWords == 1 && rhsWords == 1) {
1855 // There is only one word to consider so use the native versions.
1856 if (LHS.isSingleWord()) {
1857 Quotient = APInt(LHS.getBitWidth(), LHS.VAL / RHS.VAL);
1858 Remainder = APInt(LHS.getBitWidth(), LHS.VAL % RHS.VAL);
1860 Quotient = APInt(LHS.getBitWidth(), LHS.pVal[0] / RHS.pVal[0]);
1861 Remainder = APInt(LHS.getBitWidth(), LHS.pVal[0] % RHS.pVal[0]);
1866 // Okay, lets do it the long way
1867 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1870 void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen,
1872 // Check our assumptions here
1873 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1874 "Radix should be 2, 8, 10, or 16!");
1875 assert(str && "String is null?");
1876 bool isNeg = str[0] == '-';
1879 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
1880 assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width");
1881 assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width");
1882 assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width");
1885 if (!isSingleWord())
1886 pVal = getClearedMemory(getNumWords());
1888 // Figure out if we can shift instead of multiply
1889 uint32_t shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1891 // Set up an APInt for the digit to add outside the loop so we don't
1892 // constantly construct/destruct it.
1893 APInt apdigit(getBitWidth(), 0);
1894 APInt apradix(getBitWidth(), radix);
1896 // Enter digit traversal loop
1897 for (unsigned i = 0; i < slen; i++) {
1900 char cdigit = str[i];
1902 if (!isxdigit(cdigit))
1903 assert(0 && "Invalid hex digit in string");
1904 if (isdigit(cdigit))
1905 digit = cdigit - '0';
1906 else if (cdigit >= 'a')
1907 digit = cdigit - 'a' + 10;
1908 else if (cdigit >= 'A')
1909 digit = cdigit - 'A' + 10;
1911 assert(0 && "huh? we shouldn't get here");
1912 } else if (isdigit(cdigit)) {
1913 digit = cdigit - '0';
1915 assert(0 && "Invalid character in digit string");
1918 // Shift or multiply the value by the radix
1924 // Add in the digit we just interpreted
1925 if (apdigit.isSingleWord())
1926 apdigit.VAL = digit;
1928 apdigit.pVal[0] = digit;
1931 // If its negative, put it in two's complement form
1938 std::string APInt::toString(uint8_t radix, bool wantSigned) const {
1939 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1940 "Radix should be 2, 8, 10, or 16!");
1941 static const char *digits[] = {
1942 "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"
1945 uint32_t bits_used = getActiveBits();
1946 if (isSingleWord()) {
1948 const char *format = (radix == 10 ? (wantSigned ? "%lld" : "%llu") :
1949 (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0)));
1952 int64_t sextVal = (int64_t(VAL) << (APINT_BITS_PER_WORD-BitWidth)) >>
1953 (APINT_BITS_PER_WORD-BitWidth);
1954 sprintf(buf, format, sextVal);
1956 sprintf(buf, format, VAL);
1961 uint32_t bit = v & 1;
1963 buf[bits_used] = digits[bit][0];
1972 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
1973 // because the number of bits per digit (1,3 and 4 respectively) divides
1974 // equaly. We just shift until there value is zero.
1976 // First, check for a zero value and just short circuit the logic below.
1981 size_t insert_at = 0;
1982 if (wantSigned && this->isNegative()) {
1983 // They want to print the signed version and it is a negative value
1984 // Flip the bits and add one to turn it into the equivalent positive
1985 // value and put a '-' in the result.
1991 // Just shift tmp right for each digit width until it becomes zero
1992 uint32_t shift = (radix == 16 ? 4 : (radix == 8 ? 3 : 1));
1993 uint64_t mask = radix - 1;
1994 APInt zero(tmp.getBitWidth(), 0);
1995 while (tmp.ne(zero)) {
1996 unsigned digit = (tmp.isSingleWord() ? tmp.VAL : tmp.pVal[0]) & mask;
1997 result.insert(insert_at, digits[digit]);
1998 tmp = tmp.lshr(shift);
2005 APInt divisor(4, radix);
2006 APInt zero(tmp.getBitWidth(), 0);
2007 size_t insert_at = 0;
2008 if (wantSigned && tmp[BitWidth-1]) {
2009 // They want to print the signed version and it is a negative value
2010 // Flip the bits and add one to turn it into the equivalent positive
2011 // value and put a '-' in the result.
2017 if (tmp == APInt(tmp.getBitWidth(), 0))
2019 else while (tmp.ne(zero)) {
2021 APInt tmp2(tmp.getBitWidth(), 0);
2022 divide(tmp, tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2024 uint32_t digit = APdigit.getZExtValue();
2025 assert(digit < radix && "divide failed");
2026 result.insert(insert_at,digits[digit]);
2033 void APInt::dump() const
2035 cerr << "APInt(" << BitWidth << ")=" << std::setbase(16);
2038 else for (unsigned i = getNumWords(); i > 0; i--) {
2039 cerr << pVal[i-1] << " ";
2041 cerr << " U(" << this->toStringUnsigned(10) << ") S("
2042 << this->toStringSigned(10) << ")" << std::setbase(10);
2045 // This implements a variety of operations on a representation of
2046 // arbitrary precision, two's-complement, bignum integer values.
2048 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2049 and unrestricting assumption. */
2050 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2052 /* Some handy functions local to this file. */
2055 /* Returns the integer part with the least significant BITS set.
2056 BITS cannot be zero. */
2058 lowBitMask(unsigned int bits)
2060 assert (bits != 0 && bits <= integerPartWidth);
2062 return ~(integerPart) 0 >> (integerPartWidth - bits);
2065 /* Returns the value of the lower half of PART. */
2067 lowHalf(integerPart part)
2069 return part & lowBitMask(integerPartWidth / 2);
2072 /* Returns the value of the upper half of PART. */
2074 highHalf(integerPart part)
2076 return part >> (integerPartWidth / 2);
2079 /* Returns the bit number of the most significant set bit of a part.
2080 If the input number has no bits set -1U is returned. */
2082 partMSB(integerPart value)
2084 unsigned int n, msb;
2089 n = integerPartWidth / 2;
2104 /* Returns the bit number of the least significant set bit of a
2105 part. If the input number has no bits set -1U is returned. */
2107 partLSB(integerPart value)
2109 unsigned int n, lsb;
2114 lsb = integerPartWidth - 1;
2115 n = integerPartWidth / 2;
2130 /* Sets the least significant part of a bignum to the input value, and
2131 zeroes out higher parts. */
2133 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2140 for(i = 1; i < parts; i++)
2144 /* Assign one bignum to another. */
2146 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2150 for(i = 0; i < parts; i++)
2154 /* Returns true if a bignum is zero, false otherwise. */
2156 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2160 for(i = 0; i < parts; i++)
2167 /* Extract the given bit of a bignum; returns 0 or 1. */
2169 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2171 return(parts[bit / integerPartWidth]
2172 & ((integerPart) 1 << bit % integerPartWidth)) != 0;
2175 /* Set the given bit of a bignum. */
2177 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2179 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2182 /* Returns the bit number of the least significant set bit of a
2183 number. If the input number has no bits set -1U is returned. */
2185 APInt::tcLSB(const integerPart *parts, unsigned int n)
2187 unsigned int i, lsb;
2189 for(i = 0; i < n; i++) {
2190 if (parts[i] != 0) {
2191 lsb = partLSB(parts[i]);
2193 return lsb + i * integerPartWidth;
2200 /* Returns the bit number of the most significant set bit of a number.
2201 If the input number has no bits set -1U is returned. */
2203 APInt::tcMSB(const integerPart *parts, unsigned int n)
2210 if (parts[n] != 0) {
2211 msb = partMSB(parts[n]);
2213 return msb + n * integerPartWidth;
2220 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2221 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2222 the least significant bit of DST. All high bits above srcBITS in
2223 DST are zero-filled. */
2225 APInt::tcExtract(integerPart *dst, unsigned int dstCount, const integerPart *src,
2226 unsigned int srcBits, unsigned int srcLSB)
2228 unsigned int firstSrcPart, dstParts, shift, n;
2230 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2231 assert (dstParts <= dstCount);
2233 firstSrcPart = srcLSB / integerPartWidth;
2234 tcAssign (dst, src + firstSrcPart, dstParts);
2236 shift = srcLSB % integerPartWidth;
2237 tcShiftRight (dst, dstParts, shift);
2239 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2240 in DST. If this is less that srcBits, append the rest, else
2241 clear the high bits. */
2242 n = dstParts * integerPartWidth - shift;
2244 integerPart mask = lowBitMask (srcBits - n);
2245 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2246 << n % integerPartWidth);
2247 } else if (n > srcBits) {
2248 if (srcBits % integerPartWidth)
2249 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2252 /* Clear high parts. */
2253 while (dstParts < dstCount)
2254 dst[dstParts++] = 0;
2257 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2259 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2260 integerPart c, unsigned int parts)
2266 for(i = 0; i < parts; i++) {
2271 dst[i] += rhs[i] + 1;
2282 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2284 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2285 integerPart c, unsigned int parts)
2291 for(i = 0; i < parts; i++) {
2296 dst[i] -= rhs[i] + 1;
2307 /* Negate a bignum in-place. */
2309 APInt::tcNegate(integerPart *dst, unsigned int parts)
2311 tcComplement(dst, parts);
2312 tcIncrement(dst, parts);
2315 /* DST += SRC * MULTIPLIER + CARRY if add is true
2316 DST = SRC * MULTIPLIER + CARRY if add is false
2318 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2319 they must start at the same point, i.e. DST == SRC.
2321 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2322 returned. Otherwise DST is filled with the least significant
2323 DSTPARTS parts of the result, and if all of the omitted higher
2324 parts were zero return zero, otherwise overflow occurred and
2327 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2328 integerPart multiplier, integerPart carry,
2329 unsigned int srcParts, unsigned int dstParts,
2334 /* Otherwise our writes of DST kill our later reads of SRC. */
2335 assert(dst <= src || dst >= src + srcParts);
2336 assert(dstParts <= srcParts + 1);
2338 /* N loops; minimum of dstParts and srcParts. */
2339 n = dstParts < srcParts ? dstParts: srcParts;
2341 for(i = 0; i < n; i++) {
2342 integerPart low, mid, high, srcPart;
2344 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2346 This cannot overflow, because
2348 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2350 which is less than n^2. */
2354 if (multiplier == 0 || srcPart == 0) {
2358 low = lowHalf(srcPart) * lowHalf(multiplier);
2359 high = highHalf(srcPart) * highHalf(multiplier);
2361 mid = lowHalf(srcPart) * highHalf(multiplier);
2362 high += highHalf(mid);
2363 mid <<= integerPartWidth / 2;
2364 if (low + mid < low)
2368 mid = highHalf(srcPart) * lowHalf(multiplier);
2369 high += highHalf(mid);
2370 mid <<= integerPartWidth / 2;
2371 if (low + mid < low)
2375 /* Now add carry. */
2376 if (low + carry < low)
2382 /* And now DST[i], and store the new low part there. */
2383 if (low + dst[i] < low)
2393 /* Full multiplication, there is no overflow. */
2394 assert(i + 1 == dstParts);
2398 /* We overflowed if there is carry. */
2402 /* We would overflow if any significant unwritten parts would be
2403 non-zero. This is true if any remaining src parts are non-zero
2404 and the multiplier is non-zero. */
2406 for(; i < srcParts; i++)
2410 /* We fitted in the narrow destination. */
2415 /* DST = LHS * RHS, where DST has the same width as the operands and
2416 is filled with the least significant parts of the result. Returns
2417 one if overflow occurred, otherwise zero. DST must be disjoint
2418 from both operands. */
2420 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2421 const integerPart *rhs, unsigned int parts)
2426 assert(dst != lhs && dst != rhs);
2429 tcSet(dst, 0, parts);
2431 for(i = 0; i < parts; i++)
2432 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2438 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2439 operands. No overflow occurs. DST must be disjoint from both
2440 operands. Returns the number of parts required to hold the
2443 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2444 const integerPart *rhs, unsigned int lhsParts,
2445 unsigned int rhsParts)
2447 /* Put the narrower number on the LHS for less loops below. */
2448 if (lhsParts > rhsParts) {
2449 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2453 assert(dst != lhs && dst != rhs);
2455 tcSet(dst, 0, rhsParts);
2457 for(n = 0; n < lhsParts; n++)
2458 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2460 n = lhsParts + rhsParts;
2462 return n - (dst[n - 1] == 0);
2466 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2467 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2468 set REMAINDER to the remainder, return zero. i.e.
2470 OLD_LHS = RHS * LHS + REMAINDER
2472 SCRATCH is a bignum of the same size as the operands and result for
2473 use by the routine; its contents need not be initialized and are
2474 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2477 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2478 integerPart *remainder, integerPart *srhs,
2481 unsigned int n, shiftCount;
2484 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2486 shiftCount = tcMSB(rhs, parts) + 1;
2487 if (shiftCount == 0)
2490 shiftCount = parts * integerPartWidth - shiftCount;
2491 n = shiftCount / integerPartWidth;
2492 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2494 tcAssign(srhs, rhs, parts);
2495 tcShiftLeft(srhs, parts, shiftCount);
2496 tcAssign(remainder, lhs, parts);
2497 tcSet(lhs, 0, parts);
2499 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2504 compare = tcCompare(remainder, srhs, parts);
2506 tcSubtract(remainder, srhs, 0, parts);
2510 if (shiftCount == 0)
2513 tcShiftRight(srhs, parts, 1);
2514 if ((mask >>= 1) == 0)
2515 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2521 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2522 There are no restrictions on COUNT. */
2524 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2527 unsigned int jump, shift;
2529 /* Jump is the inter-part jump; shift is is intra-part shift. */
2530 jump = count / integerPartWidth;
2531 shift = count % integerPartWidth;
2533 while (parts > jump) {
2538 /* dst[i] comes from the two parts src[i - jump] and, if we have
2539 an intra-part shift, src[i - jump - 1]. */
2540 part = dst[parts - jump];
2543 if (parts >= jump + 1)
2544 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2555 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2556 zero. There are no restrictions on COUNT. */
2558 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2561 unsigned int i, jump, shift;
2563 /* Jump is the inter-part jump; shift is is intra-part shift. */
2564 jump = count / integerPartWidth;
2565 shift = count % integerPartWidth;
2567 /* Perform the shift. This leaves the most significant COUNT bits
2568 of the result at zero. */
2569 for(i = 0; i < parts; i++) {
2572 if (i + jump >= parts) {
2575 part = dst[i + jump];
2578 if (i + jump + 1 < parts)
2579 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2588 /* Bitwise and of two bignums. */
2590 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2594 for(i = 0; i < parts; i++)
2598 /* Bitwise inclusive or of two bignums. */
2600 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2604 for(i = 0; i < parts; i++)
2608 /* Bitwise exclusive or of two bignums. */
2610 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2614 for(i = 0; i < parts; i++)
2618 /* Complement a bignum in-place. */
2620 APInt::tcComplement(integerPart *dst, unsigned int parts)
2624 for(i = 0; i < parts; i++)
2628 /* Comparison (unsigned) of two bignums. */
2630 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2635 if (lhs[parts] == rhs[parts])
2638 if (lhs[parts] > rhs[parts])
2647 /* Increment a bignum in-place, return the carry flag. */
2649 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2653 for(i = 0; i < parts; i++)
2660 /* Set the least significant BITS bits of a bignum, clear the
2663 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2669 while (bits > integerPartWidth) {
2670 dst[i++] = ~(integerPart) 0;
2671 bits -= integerPartWidth;
2675 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);