1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Sheng Zhou and is distributed under the
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a class to represent arbitrary precision integer
11 // constant values and provide a variety of arithmetic operations on them.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "apint"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/Support/Debug.h"
18 #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 /// add_1 - This function adds a single "digit" integer, y, to the multiple
169 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
170 /// 1 is returned if there is a carry out, otherwise 0 is returned.
171 /// @returns the carry of the addition.
172 static bool add_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
173 for (uint32_t i = 0; i < len; ++i) {
176 y = 1; // Carry one to next digit.
178 y = 0; // No need to carry so exit early
185 /// @brief Prefix increment operator. Increments the APInt by one.
186 APInt& APInt::operator++() {
190 add_1(pVal, pVal, getNumWords(), 1);
191 return clearUnusedBits();
194 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
195 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
196 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
197 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
198 /// In other words, if y > x then this function returns 1, otherwise 0.
199 /// @returns the borrow out of the subtraction
200 static bool sub_1(uint64_t x[], uint32_t len, uint64_t y) {
201 for (uint32_t i = 0; i < len; ++i) {
205 y = 1; // We have to "borrow 1" from next "digit"
207 y = 0; // No need to borrow
208 break; // Remaining digits are unchanged so exit early
214 /// @brief Prefix decrement operator. Decrements the APInt by one.
215 APInt& APInt::operator--() {
219 sub_1(pVal, getNumWords(), 1);
220 return clearUnusedBits();
223 /// add - This function adds the integer array x to the integer array Y and
224 /// places the result in dest.
225 /// @returns the carry out from the addition
226 /// @brief General addition of 64-bit integer arrays
227 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
230 for (uint32_t i = 0; i< len; ++i) {
231 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
232 dest[i] = x[i] + y[i] + carry;
233 carry = dest[i] < limit || (carry && dest[i] == limit);
238 /// Adds the RHS APint to this APInt.
239 /// @returns this, after addition of RHS.
240 /// @brief Addition assignment operator.
241 APInt& APInt::operator+=(const APInt& RHS) {
242 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
246 add(pVal, pVal, RHS.pVal, getNumWords());
248 return clearUnusedBits();
251 /// Subtracts the integer array y from the integer array x
252 /// @returns returns the borrow out.
253 /// @brief Generalized subtraction of 64-bit integer arrays.
254 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
257 for (uint32_t i = 0; i < len; ++i) {
258 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
259 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
260 dest[i] = x_tmp - y[i];
265 /// Subtracts the RHS APInt from this APInt
266 /// @returns this, after subtraction
267 /// @brief Subtraction assignment operator.
268 APInt& APInt::operator-=(const APInt& RHS) {
269 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
273 sub(pVal, pVal, RHS.pVal, getNumWords());
274 return clearUnusedBits();
277 /// Multiplies an integer array, x by a a uint64_t integer and places the result
279 /// @returns the carry out of the multiplication.
280 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
281 static uint64_t mul_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
282 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
283 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
286 // For each digit of x.
287 for (uint32_t i = 0; i < len; ++i) {
288 // Split x into high and low words
289 uint64_t lx = x[i] & 0xffffffffULL;
290 uint64_t hx = x[i] >> 32;
291 // hasCarry - A flag to indicate if there is a carry to the next digit.
292 // hasCarry == 0, no carry
293 // hasCarry == 1, has carry
294 // hasCarry == 2, no carry and the calculation result == 0.
295 uint8_t hasCarry = 0;
296 dest[i] = carry + lx * ly;
297 // Determine if the add above introduces carry.
298 hasCarry = (dest[i] < carry) ? 1 : 0;
299 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
300 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
301 // (2^32 - 1) + 2^32 = 2^64.
302 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
304 carry += (lx * hy) & 0xffffffffULL;
305 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
306 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
307 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
312 /// Multiplies integer array x by integer array y and stores the result into
313 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
314 /// @brief Generalized multiplicate of integer arrays.
315 static void mul(uint64_t dest[], uint64_t x[], uint32_t xlen, uint64_t y[],
317 dest[xlen] = mul_1(dest, x, xlen, y[0]);
318 for (uint32_t i = 1; i < ylen; ++i) {
319 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
320 uint64_t carry = 0, lx = 0, hx = 0;
321 for (uint32_t j = 0; j < xlen; ++j) {
322 lx = x[j] & 0xffffffffULL;
324 // hasCarry - A flag to indicate if has carry.
325 // hasCarry == 0, no carry
326 // hasCarry == 1, has carry
327 // hasCarry == 2, no carry and the calculation result == 0.
328 uint8_t hasCarry = 0;
329 uint64_t resul = carry + lx * ly;
330 hasCarry = (resul < carry) ? 1 : 0;
331 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
332 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
334 carry += (lx * hy) & 0xffffffffULL;
335 resul = (carry << 32) | (resul & 0xffffffffULL);
337 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
338 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
339 ((lx * hy) >> 32) + hx * hy;
341 dest[i+xlen] = carry;
345 APInt& APInt::operator*=(const APInt& RHS) {
346 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
347 if (isSingleWord()) {
353 // Get some bit facts about LHS and check for zero
354 uint32_t lhsBits = getActiveBits();
355 uint32_t lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
360 // Get some bit facts about RHS and check for zero
361 uint32_t rhsBits = RHS.getActiveBits();
362 uint32_t rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
369 // Allocate space for the result
370 uint32_t destWords = rhsWords + lhsWords;
371 uint64_t *dest = getMemory(destWords);
373 // Perform the long multiply
374 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
376 // Copy result back into *this
378 uint32_t wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
379 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
381 // delete dest array and return
386 APInt& APInt::operator&=(const APInt& RHS) {
387 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
388 if (isSingleWord()) {
392 uint32_t numWords = getNumWords();
393 for (uint32_t i = 0; i < numWords; ++i)
394 pVal[i] &= RHS.pVal[i];
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()) {
414 this->clearUnusedBits();
417 uint32_t numWords = getNumWords();
418 for (uint32_t i = 0; i < numWords; ++i)
419 pVal[i] ^= RHS.pVal[i];
420 return clearUnusedBits();
423 APInt APInt::operator&(const APInt& RHS) const {
424 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
426 return APInt(getBitWidth(), VAL & RHS.VAL);
428 uint32_t numWords = getNumWords();
429 uint64_t* val = getMemory(numWords);
430 for (uint32_t i = 0; i < numWords; ++i)
431 val[i] = pVal[i] & RHS.pVal[i];
432 return APInt(val, getBitWidth());
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(BitWidth, 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];
457 // 0^0==1 so clear the high bits in case they got set.
458 return APInt(val, getBitWidth()).clearUnusedBits();
461 bool APInt::operator !() const {
465 for (uint32_t i = 0; i < getNumWords(); ++i)
471 APInt APInt::operator*(const APInt& RHS) const {
472 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
474 return APInt(BitWidth, VAL * RHS.VAL);
477 return Result.clearUnusedBits();
480 APInt APInt::operator+(const APInt& RHS) const {
481 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
483 return APInt(BitWidth, VAL + RHS.VAL);
484 APInt Result(BitWidth, 0);
485 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
486 return Result.clearUnusedBits();
489 APInt APInt::operator-(const APInt& RHS) const {
490 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
492 return APInt(BitWidth, VAL - RHS.VAL);
493 APInt Result(BitWidth, 0);
494 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
495 return Result.clearUnusedBits();
498 bool APInt::operator[](uint32_t bitPosition) const {
499 return (maskBit(bitPosition) &
500 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
503 bool APInt::operator==(const APInt& RHS) const {
504 assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
506 return VAL == RHS.VAL;
508 // Get some facts about the number of bits used in the two operands.
509 uint32_t n1 = getActiveBits();
510 uint32_t n2 = RHS.getActiveBits();
512 // If the number of bits isn't the same, they aren't equal
516 // If the number of bits fits in a word, we only need to compare the low word.
517 if (n1 <= APINT_BITS_PER_WORD)
518 return pVal[0] == RHS.pVal[0];
520 // Otherwise, compare everything
521 for (int i = whichWord(n1 - 1); i >= 0; --i)
522 if (pVal[i] != RHS.pVal[i])
527 bool APInt::operator==(uint64_t Val) const {
531 uint32_t n = getActiveBits();
532 if (n <= APINT_BITS_PER_WORD)
533 return pVal[0] == Val;
538 bool APInt::ult(const APInt& RHS) const {
539 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
541 return VAL < RHS.VAL;
543 // Get active bit length of both operands
544 uint32_t n1 = getActiveBits();
545 uint32_t n2 = RHS.getActiveBits();
547 // If magnitude of LHS is less than RHS, return true.
551 // If magnitude of RHS is greather than LHS, return false.
555 // If they bot fit in a word, just compare the low order word
556 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
557 return pVal[0] < RHS.pVal[0];
559 // Otherwise, compare all words
560 uint32_t topWord = whichWord(std::max(n1,n2)-1);
561 for (int i = topWord; i >= 0; --i) {
562 if (pVal[i] > RHS.pVal[i])
564 if (pVal[i] < RHS.pVal[i])
570 bool APInt::slt(const APInt& RHS) const {
571 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
572 if (isSingleWord()) {
573 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
574 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
575 return lhsSext < rhsSext;
580 bool lhsNeg = isNegative();
581 bool rhsNeg = rhs.isNegative();
583 // Sign bit is set so perform two's complement to make it positive
588 // Sign bit is set so perform two's complement to make it positive
593 // Now we have unsigned values to compare so do the comparison if necessary
594 // based on the negativeness of the values.
606 APInt& APInt::set(uint32_t bitPosition) {
608 VAL |= maskBit(bitPosition);
610 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
614 APInt& APInt::set() {
615 if (isSingleWord()) {
617 return clearUnusedBits();
620 // Set all the bits in all the words.
621 for (uint32_t i = 0; i < getNumWords(); ++i)
623 // Clear the unused ones
624 return clearUnusedBits();
627 /// Set the given bit to 0 whose position is given as "bitPosition".
628 /// @brief Set a given bit to 0.
629 APInt& APInt::clear(uint32_t bitPosition) {
631 VAL &= ~maskBit(bitPosition);
633 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
637 /// @brief Set every bit to 0.
638 APInt& APInt::clear() {
642 memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
646 /// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on
648 APInt APInt::operator~() const {
654 /// @brief Toggle every bit to its opposite value.
655 APInt& APInt::flip() {
656 if (isSingleWord()) {
658 return clearUnusedBits();
660 for (uint32_t i = 0; i < getNumWords(); ++i)
662 return clearUnusedBits();
665 /// Toggle a given bit to its opposite value whose position is given
666 /// as "bitPosition".
667 /// @brief Toggles a given bit to its opposite value.
668 APInt& APInt::flip(uint32_t bitPosition) {
669 assert(bitPosition < BitWidth && "Out of the bit-width range!");
670 if ((*this)[bitPosition]) clear(bitPosition);
671 else set(bitPosition);
675 uint32_t APInt::getBitsNeeded(const char* str, uint32_t slen, uint8_t radix) {
676 assert(str != 0 && "Invalid value string");
677 assert(slen > 0 && "Invalid string length");
679 // Each computation below needs to know if its negative
680 uint32_t isNegative = str[0] == '-';
685 // For radixes of power-of-two values, the bits required is accurately and
688 return slen + isNegative;
690 return slen * 3 + isNegative;
692 return slen * 4 + isNegative;
694 // Otherwise it must be radix == 10, the hard case
695 assert(radix == 10 && "Invalid radix");
697 // This is grossly inefficient but accurate. We could probably do something
698 // with a computation of roughly slen*64/20 and then adjust by the value of
699 // the first few digits. But, I'm not sure how accurate that could be.
701 // Compute a sufficient number of bits that is always large enough but might
702 // be too large. This avoids the assertion in the constructor.
703 uint32_t sufficient = slen*64/18;
705 // Convert to the actual binary value.
706 APInt tmp(sufficient, str, slen, radix);
708 // Compute how many bits are required.
709 return isNegative + tmp.logBase2() + 1;
712 uint64_t APInt::getHashValue() const {
713 // Put the bit width into the low order bits.
714 uint64_t hash = BitWidth;
716 // Add the sum of the words to the hash.
718 hash += VAL << 6; // clear separation of up to 64 bits
720 for (uint32_t i = 0; i < getNumWords(); ++i)
721 hash += pVal[i] << 6; // clear sepration of up to 64 bits
725 /// HiBits - This function returns the high "numBits" bits of this APInt.
726 APInt APInt::getHiBits(uint32_t numBits) const {
727 return APIntOps::lshr(*this, BitWidth - numBits);
730 /// LoBits - This function returns the low "numBits" bits of this APInt.
731 APInt APInt::getLoBits(uint32_t numBits) const {
732 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
736 bool APInt::isPowerOf2() const {
737 return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
740 uint32_t APInt::countLeadingZeros() const {
743 Count = CountLeadingZeros_64(VAL);
745 for (uint32_t i = getNumWords(); i > 0u; --i) {
747 Count += APINT_BITS_PER_WORD;
749 Count += CountLeadingZeros_64(pVal[i-1]);
754 uint32_t remainder = BitWidth % APINT_BITS_PER_WORD;
756 Count -= APINT_BITS_PER_WORD - remainder;
757 return std::min(Count, BitWidth);
760 static uint32_t countLeadingOnes_64(uint64_t V, uint32_t skip) {
764 while (V && (V & (1ULL << 63))) {
771 uint32_t APInt::countLeadingOnes() const {
773 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
775 uint32_t highWordBits = BitWidth % APINT_BITS_PER_WORD;
776 uint32_t shift = (highWordBits == 0 ? 0 : APINT_BITS_PER_WORD - highWordBits);
777 int i = getNumWords() - 1;
778 uint32_t Count = countLeadingOnes_64(pVal[i], shift);
779 if (Count == highWordBits) {
780 for (i--; i >= 0; --i) {
781 if (pVal[i] == -1ULL)
782 Count += APINT_BITS_PER_WORD;
784 Count += countLeadingOnes_64(pVal[i], 0);
792 uint32_t APInt::countTrailingZeros() const {
794 return std::min(CountTrailingZeros_64(VAL), BitWidth);
797 for (; i < getNumWords() && pVal[i] == 0; ++i)
798 Count += APINT_BITS_PER_WORD;
799 if (i < getNumWords())
800 Count += CountTrailingZeros_64(pVal[i]);
801 return std::min(Count, BitWidth);
804 uint32_t APInt::countPopulation() const {
806 return CountPopulation_64(VAL);
808 for (uint32_t i = 0; i < getNumWords(); ++i)
809 Count += CountPopulation_64(pVal[i]);
813 APInt APInt::byteSwap() const {
814 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
816 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
817 else if (BitWidth == 32)
818 return APInt(BitWidth, ByteSwap_32(uint32_t(VAL)));
819 else if (BitWidth == 48) {
820 uint32_t Tmp1 = uint32_t(VAL >> 16);
821 Tmp1 = ByteSwap_32(Tmp1);
822 uint16_t Tmp2 = uint16_t(VAL);
823 Tmp2 = ByteSwap_16(Tmp2);
824 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
825 } else if (BitWidth == 64)
826 return APInt(BitWidth, ByteSwap_64(VAL));
828 APInt Result(BitWidth, 0);
829 char *pByte = (char*)Result.pVal;
830 for (uint32_t i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
832 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
833 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
839 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
841 APInt A = API1, B = API2;
844 B = APIntOps::urem(A, B);
850 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) {
857 // Get the sign bit from the highest order bit
858 bool isNeg = T.I >> 63;
860 // Get the 11-bit exponent and adjust for the 1023 bit bias
861 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
863 // If the exponent is negative, the value is < 0 so just return 0.
865 return APInt(width, 0u);
867 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
868 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
870 // If the exponent doesn't shift all bits out of the mantissa
872 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
873 APInt(width, mantissa >> (52 - exp));
875 // If the client didn't provide enough bits for us to shift the mantissa into
876 // then the result is undefined, just return 0
877 if (width <= exp - 52)
878 return APInt(width, 0);
880 // Otherwise, we have to shift the mantissa bits up to the right location
881 APInt Tmp(width, mantissa);
882 Tmp = Tmp.shl(exp - 52);
883 return isNeg ? -Tmp : Tmp;
886 /// RoundToDouble - This function convert this APInt to a double.
887 /// The layout for double is as following (IEEE Standard 754):
888 /// --------------------------------------
889 /// | Sign Exponent Fraction Bias |
890 /// |-------------------------------------- |
891 /// | 1[63] 11[62-52] 52[51-00] 1023 |
892 /// --------------------------------------
893 double APInt::roundToDouble(bool isSigned) const {
895 // Handle the simple case where the value is contained in one uint64_t.
896 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
898 int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
904 // Determine if the value is negative.
905 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
907 // Construct the absolute value if we're negative.
908 APInt Tmp(isNeg ? -(*this) : (*this));
910 // Figure out how many bits we're using.
911 uint32_t n = Tmp.getActiveBits();
913 // The exponent (without bias normalization) is just the number of bits
914 // we are using. Note that the sign bit is gone since we constructed the
918 // Return infinity for exponent overflow
920 if (!isSigned || !isNeg)
921 return std::numeric_limits<double>::infinity();
923 return -std::numeric_limits<double>::infinity();
925 exp += 1023; // Increment for 1023 bias
927 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
928 // extract the high 52 bits from the correct words in pVal.
930 unsigned hiWord = whichWord(n-1);
932 mantissa = Tmp.pVal[0];
934 mantissa >>= n - 52; // shift down, we want the top 52 bits.
936 assert(hiWord > 0 && "huh?");
937 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
938 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
939 mantissa = hibits | lobits;
942 // The leading bit of mantissa is implicit, so get rid of it.
943 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
948 T.I = sign | (exp << 52) | mantissa;
952 // Truncate to new width.
953 APInt &APInt::trunc(uint32_t width) {
954 assert(width < BitWidth && "Invalid APInt Truncate request");
955 assert(width >= MIN_INT_BITS && "Can't truncate to 0 bits");
956 uint32_t wordsBefore = getNumWords();
958 uint32_t wordsAfter = getNumWords();
959 if (wordsBefore != wordsAfter) {
960 if (wordsAfter == 1) {
961 uint64_t *tmp = pVal;
965 uint64_t *newVal = getClearedMemory(wordsAfter);
966 for (uint32_t i = 0; i < wordsAfter; ++i)
972 return clearUnusedBits();
975 // Sign extend to a new width.
976 APInt &APInt::sext(uint32_t width) {
977 assert(width > BitWidth && "Invalid APInt SignExtend request");
978 assert(width <= MAX_INT_BITS && "Too many bits");
979 // If the sign bit isn't set, this is the same as zext.
985 // The sign bit is set. First, get some facts
986 uint32_t wordsBefore = getNumWords();
987 uint32_t wordBits = BitWidth % APINT_BITS_PER_WORD;
989 uint32_t wordsAfter = getNumWords();
991 // Mask the high order word appropriately
992 if (wordsBefore == wordsAfter) {
993 uint32_t newWordBits = width % APINT_BITS_PER_WORD;
994 // The extension is contained to the wordsBefore-1th word.
995 uint64_t mask = ~0ULL;
997 mask >>= APINT_BITS_PER_WORD - newWordBits;
999 if (wordsBefore == 1)
1002 pVal[wordsBefore-1] |= mask;
1003 return clearUnusedBits();
1006 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
1007 uint64_t *newVal = getMemory(wordsAfter);
1008 if (wordsBefore == 1)
1009 newVal[0] = VAL | mask;
1011 for (uint32_t i = 0; i < wordsBefore; ++i)
1012 newVal[i] = pVal[i];
1013 newVal[wordsBefore-1] |= mask;
1015 for (uint32_t i = wordsBefore; i < wordsAfter; i++)
1017 if (wordsBefore != 1)
1020 return clearUnusedBits();
1023 // Zero extend to a new width.
1024 APInt &APInt::zext(uint32_t width) {
1025 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1026 assert(width <= MAX_INT_BITS && "Too many bits");
1027 uint32_t wordsBefore = getNumWords();
1029 uint32_t wordsAfter = getNumWords();
1030 if (wordsBefore != wordsAfter) {
1031 uint64_t *newVal = getClearedMemory(wordsAfter);
1032 if (wordsBefore == 1)
1035 for (uint32_t i = 0; i < wordsBefore; ++i)
1036 newVal[i] = pVal[i];
1037 if (wordsBefore != 1)
1044 APInt &APInt::zextOrTrunc(uint32_t width) {
1045 if (BitWidth < width)
1047 if (BitWidth > width)
1048 return trunc(width);
1052 APInt &APInt::sextOrTrunc(uint32_t width) {
1053 if (BitWidth < width)
1055 if (BitWidth > width)
1056 return trunc(width);
1060 /// Arithmetic right-shift this APInt by shiftAmt.
1061 /// @brief Arithmetic right-shift function.
1062 APInt APInt::ashr(uint32_t shiftAmt) const {
1063 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1064 // Handle a degenerate case
1068 // Handle single word shifts with built-in ashr
1069 if (isSingleWord()) {
1070 if (shiftAmt == BitWidth)
1071 return APInt(BitWidth, 0); // undefined
1073 uint32_t SignBit = APINT_BITS_PER_WORD - BitWidth;
1074 return APInt(BitWidth,
1075 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1079 // If all the bits were shifted out, the result is, technically, undefined.
1080 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1081 // issues in the algorithm below.
1082 if (shiftAmt == BitWidth) {
1084 return APInt(BitWidth, -1ULL);
1086 return APInt(BitWidth, 0);
1089 // Create some space for the result.
1090 uint64_t * val = new uint64_t[getNumWords()];
1092 // Compute some values needed by the following shift algorithms
1093 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1094 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1095 uint32_t breakWord = getNumWords() - 1 - offset; // last word affected
1096 uint32_t bitsInWord = whichBit(BitWidth); // how many bits in last word?
1097 if (bitsInWord == 0)
1098 bitsInWord = APINT_BITS_PER_WORD;
1100 // If we are shifting whole words, just move whole words
1101 if (wordShift == 0) {
1102 // Move the words containing significant bits
1103 for (uint32_t i = 0; i <= breakWord; ++i)
1104 val[i] = pVal[i+offset]; // move whole word
1106 // Adjust the top significant word for sign bit fill, if negative
1108 if (bitsInWord < APINT_BITS_PER_WORD)
1109 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1111 // Shift the low order words
1112 for (uint32_t i = 0; i < breakWord; ++i) {
1113 // This combines the shifted corresponding word with the low bits from
1114 // the next word (shifted into this word's high bits).
1115 val[i] = (pVal[i+offset] >> wordShift) |
1116 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1119 // Shift the break word. In this case there are no bits from the next word
1120 // to include in this word.
1121 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1123 // Deal with sign extenstion in the break word, and possibly the word before
1126 if (wordShift > bitsInWord) {
1129 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1130 val[breakWord] |= ~0ULL;
1132 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1136 // Remaining words are 0 or -1, just assign them.
1137 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1138 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1140 return APInt(val, BitWidth).clearUnusedBits();
1143 /// Logical right-shift this APInt by shiftAmt.
1144 /// @brief Logical right-shift function.
1145 APInt APInt::lshr(uint32_t shiftAmt) const {
1146 if (isSingleWord()) {
1147 if (shiftAmt == BitWidth)
1148 return APInt(BitWidth, 0);
1150 return APInt(BitWidth, this->VAL >> shiftAmt);
1153 // If all the bits were shifted out, the result is 0. This avoids issues
1154 // with shifting by the size of the integer type, which produces undefined
1155 // results. We define these "undefined results" to always be 0.
1156 if (shiftAmt == BitWidth)
1157 return APInt(BitWidth, 0);
1159 // If none of the bits are shifted out, the result is *this. This avoids
1160 // issues with shifting byt he size of the integer type, which produces
1161 // undefined results in the code below. This is also an optimization.
1165 // Create some space for the result.
1166 uint64_t * val = new uint64_t[getNumWords()];
1168 // If we are shifting less than a word, compute the shift with a simple carry
1169 if (shiftAmt < APINT_BITS_PER_WORD) {
1171 for (int i = getNumWords()-1; i >= 0; --i) {
1172 val[i] = (pVal[i] >> shiftAmt) | carry;
1173 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1175 return APInt(val, BitWidth).clearUnusedBits();
1178 // Compute some values needed by the remaining shift algorithms
1179 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1180 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1182 // If we are shifting whole words, just move whole words
1183 if (wordShift == 0) {
1184 for (uint32_t i = 0; i < getNumWords() - offset; ++i)
1185 val[i] = pVal[i+offset];
1186 for (uint32_t i = getNumWords()-offset; i < getNumWords(); i++)
1188 return APInt(val,BitWidth).clearUnusedBits();
1191 // Shift the low order words
1192 uint32_t breakWord = getNumWords() - offset -1;
1193 for (uint32_t i = 0; i < breakWord; ++i)
1194 val[i] = (pVal[i+offset] >> wordShift) |
1195 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1196 // Shift the break word.
1197 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1199 // Remaining words are 0
1200 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1202 return APInt(val, BitWidth).clearUnusedBits();
1205 /// Left-shift this APInt by shiftAmt.
1206 /// @brief Left-shift function.
1207 APInt APInt::shl(uint32_t shiftAmt) const {
1208 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1209 if (isSingleWord()) {
1210 if (shiftAmt == BitWidth)
1211 return APInt(BitWidth, 0); // avoid undefined shift results
1212 return APInt(BitWidth, VAL << shiftAmt);
1215 // If all the bits were shifted out, the result is 0. This avoids issues
1216 // with shifting by the size of the integer type, which produces undefined
1217 // results. We define these "undefined results" to always be 0.
1218 if (shiftAmt == BitWidth)
1219 return APInt(BitWidth, 0);
1221 // If none of the bits are shifted out, the result is *this. This avoids a
1222 // lshr by the words size in the loop below which can produce incorrect
1223 // results. It also avoids the expensive computation below for a common case.
1227 // Create some space for the result.
1228 uint64_t * val = new uint64_t[getNumWords()];
1230 // If we are shifting less than a word, do it the easy way
1231 if (shiftAmt < APINT_BITS_PER_WORD) {
1233 for (uint32_t i = 0; i < getNumWords(); i++) {
1234 val[i] = pVal[i] << shiftAmt | carry;
1235 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1237 return APInt(val, BitWidth).clearUnusedBits();
1240 // Compute some values needed by the remaining shift algorithms
1241 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1242 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1244 // If we are shifting whole words, just move whole words
1245 if (wordShift == 0) {
1246 for (uint32_t i = 0; i < offset; i++)
1248 for (uint32_t i = offset; i < getNumWords(); i++)
1249 val[i] = pVal[i-offset];
1250 return APInt(val,BitWidth).clearUnusedBits();
1253 // Copy whole words from this to Result.
1254 uint32_t i = getNumWords() - 1;
1255 for (; i > offset; --i)
1256 val[i] = pVal[i-offset] << wordShift |
1257 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1258 val[offset] = pVal[0] << wordShift;
1259 for (i = 0; i < offset; ++i)
1261 return APInt(val, BitWidth).clearUnusedBits();
1264 APInt APInt::rotl(uint32_t rotateAmt) const {
1267 // Don't get too fancy, just use existing shift/or facilities
1271 lo.lshr(BitWidth - rotateAmt);
1275 APInt APInt::rotr(uint32_t rotateAmt) const {
1278 // Don't get too fancy, just use existing shift/or facilities
1282 hi.shl(BitWidth - rotateAmt);
1286 // Square Root - this method computes and returns the square root of "this".
1287 // Three mechanisms are used for computation. For small values (<= 5 bits),
1288 // a table lookup is done. This gets some performance for common cases. For
1289 // values using less than 52 bits, the value is converted to double and then
1290 // the libc sqrt function is called. The result is rounded and then converted
1291 // back to a uint64_t which is then used to construct the result. Finally,
1292 // the Babylonian method for computing square roots is used.
1293 APInt APInt::sqrt() const {
1295 // Determine the magnitude of the value.
1296 uint32_t magnitude = getActiveBits();
1298 // Use a fast table for some small values. This also gets rid of some
1299 // rounding errors in libc sqrt for small values.
1300 if (magnitude <= 5) {
1301 static const uint8_t results[32] = {
1304 /* 3- 6 */ 2, 2, 2, 2,
1305 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1306 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1307 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1310 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1313 // If the magnitude of the value fits in less than 52 bits (the precision of
1314 // an IEEE double precision floating point value), then we can use the
1315 // libc sqrt function which will probably use a hardware sqrt computation.
1316 // This should be faster than the algorithm below.
1317 if (magnitude < 52) {
1319 // Amazingly, VC++ doesn't have round().
1320 return APInt(BitWidth,
1321 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1323 return APInt(BitWidth,
1324 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1328 // Okay, all the short cuts are exhausted. We must compute it. The following
1329 // is a classical Babylonian method for computing the square root. This code
1330 // was adapted to APINt from a wikipedia article on such computations.
1331 // See http://www.wikipedia.org/ and go to the page named
1332 // Calculate_an_integer_square_root.
1333 uint32_t nbits = BitWidth, i = 4;
1334 APInt testy(BitWidth, 16);
1335 APInt x_old(BitWidth, 1);
1336 APInt x_new(BitWidth, 0);
1337 APInt two(BitWidth, 2);
1339 // Select a good starting value using binary logarithms.
1340 for (;; i += 2, testy = testy.shl(2))
1341 if (i >= nbits || this->ule(testy)) {
1342 x_old = x_old.shl(i / 2);
1346 // Use the Babylonian method to arrive at the integer square root:
1348 x_new = (this->udiv(x_old) + x_old).udiv(two);
1349 if (x_old.ule(x_new))
1354 // Make sure we return the closest approximation
1355 // NOTE: The rounding calculation below is correct. It will produce an
1356 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1357 // determined to be a rounding issue with pari/gp as it begins to use a
1358 // floating point representation after 192 bits. There are no discrepancies
1359 // between this algorithm and pari/gp for bit widths < 192 bits.
1360 APInt square(x_old * x_old);
1361 APInt nextSquare((x_old + 1) * (x_old +1));
1362 if (this->ult(square))
1364 else if (this->ule(nextSquare)) {
1365 APInt midpoint((nextSquare - square).udiv(two));
1366 APInt offset(*this - square);
1367 if (offset.ult(midpoint))
1372 assert(0 && "Error in APInt::sqrt computation");
1376 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1377 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1378 /// variables here have the same names as in the algorithm. Comments explain
1379 /// the algorithm and any deviation from it.
1380 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1381 uint32_t m, uint32_t n) {
1382 assert(u && "Must provide dividend");
1383 assert(v && "Must provide divisor");
1384 assert(q && "Must provide quotient");
1385 assert(u != v && u != q && v != q && "Must us different memory");
1386 assert(n>1 && "n must be > 1");
1388 // Knuth uses the value b as the base of the number system. In our case b
1389 // is 2^31 so we just set it to -1u.
1390 uint64_t b = uint64_t(1) << 32;
1392 DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n');
1393 DEBUG(cerr << "KnuthDiv: original:");
1394 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1395 DEBUG(cerr << " by");
1396 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1397 DEBUG(cerr << '\n');
1398 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1399 // u and v by d. Note that we have taken Knuth's advice here to use a power
1400 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1401 // 2 allows us to shift instead of multiply and it is easy to determine the
1402 // shift amount from the leading zeros. We are basically normalizing the u
1403 // and v so that its high bits are shifted to the top of v's range without
1404 // overflow. Note that this can require an extra word in u so that u must
1405 // be of length m+n+1.
1406 uint32_t shift = CountLeadingZeros_32(v[n-1]);
1407 uint32_t v_carry = 0;
1408 uint32_t u_carry = 0;
1410 for (uint32_t i = 0; i < m+n; ++i) {
1411 uint32_t u_tmp = u[i] >> (32 - shift);
1412 u[i] = (u[i] << shift) | u_carry;
1415 for (uint32_t i = 0; i < n; ++i) {
1416 uint32_t v_tmp = v[i] >> (32 - shift);
1417 v[i] = (v[i] << shift) | v_carry;
1422 DEBUG(cerr << "KnuthDiv: normal:");
1423 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1424 DEBUG(cerr << " by");
1425 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1426 DEBUG(cerr << '\n');
1428 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1431 DEBUG(cerr << "KnuthDiv: quotient digit #" << j << '\n');
1432 // D3. [Calculate q'.].
1433 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1434 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1435 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1436 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1437 // on v[n-2] determines at high speed most of the cases in which the trial
1438 // value qp is one too large, and it eliminates all cases where qp is two
1440 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1441 DEBUG(cerr << "KnuthDiv: dividend == " << dividend << '\n');
1442 uint64_t qp = dividend / v[n-1];
1443 uint64_t rp = dividend % v[n-1];
1444 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1447 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1450 DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1452 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1453 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1454 // consists of a simple multiplication by a one-place number, combined with
1457 for (uint32_t i = 0; i < n; ++i) {
1458 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1459 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1460 bool borrow = subtrahend > u_tmp;
1461 DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp
1462 << ", subtrahend == " << subtrahend
1463 << ", borrow = " << borrow << '\n');
1465 uint64_t result = u_tmp - subtrahend;
1467 u[k++] = result & (b-1); // subtract low word
1468 u[k++] = result >> 32; // subtract high word
1469 while (borrow && k <= m+n) { // deal with borrow to the left
1475 DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1478 DEBUG(cerr << "KnuthDiv: after subtraction:");
1479 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1480 DEBUG(cerr << '\n');
1481 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1482 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1483 // true value plus b**(n+1), namely as the b's complement of
1484 // the true value, and a "borrow" to the left should be remembered.
1487 bool carry = true; // true because b's complement is "complement + 1"
1488 for (uint32_t i = 0; i <= m+n; ++i) {
1489 u[i] = ~u[i] + carry; // b's complement
1490 carry = carry && u[i] == 0;
1493 DEBUG(cerr << "KnuthDiv: after complement:");
1494 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1495 DEBUG(cerr << '\n');
1497 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1498 // negative, go to step D6; otherwise go on to step D7.
1501 // D6. [Add back]. The probability that this step is necessary is very
1502 // small, on the order of only 2/b. Make sure that test data accounts for
1503 // this possibility. Decrease q[j] by 1
1505 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1506 // A carry will occur to the left of u[j+n], and it should be ignored
1507 // since it cancels with the borrow that occurred in D4.
1509 for (uint32_t i = 0; i < n; i++) {
1510 uint32_t limit = std::min(u[j+i],v[i]);
1511 u[j+i] += v[i] + carry;
1512 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1516 DEBUG(cerr << "KnuthDiv: after correction:");
1517 DEBUG(for (int i = m+n; i >=0; i--) cerr <<" " << u[i]);
1518 DEBUG(cerr << "\nKnuthDiv: digit result = " << q[j] << '\n');
1520 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1523 DEBUG(cerr << "KnuthDiv: quotient:");
1524 DEBUG(for (int i = m; i >=0; i--) cerr <<" " << q[i]);
1525 DEBUG(cerr << '\n');
1527 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1528 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1529 // compute the remainder (urem uses this).
1531 // The value d is expressed by the "shift" value above since we avoided
1532 // multiplication by d by using a shift left. So, all we have to do is
1533 // shift right here. In order to mak
1536 DEBUG(cerr << "KnuthDiv: remainder:");
1537 for (int i = n-1; i >= 0; i--) {
1538 r[i] = (u[i] >> shift) | carry;
1539 carry = u[i] << (32 - shift);
1540 DEBUG(cerr << " " << r[i]);
1543 for (int i = n-1; i >= 0; i--) {
1545 DEBUG(cerr << " " << r[i]);
1548 DEBUG(cerr << '\n');
1550 DEBUG(cerr << std::setbase(10) << '\n');
1553 void APInt::divide(const APInt LHS, uint32_t lhsWords,
1554 const APInt &RHS, uint32_t rhsWords,
1555 APInt *Quotient, APInt *Remainder)
1557 assert(lhsWords >= rhsWords && "Fractional result");
1559 // First, compose the values into an array of 32-bit words instead of
1560 // 64-bit words. This is a necessity of both the "short division" algorithm
1561 // and the the Knuth "classical algorithm" which requires there to be native
1562 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1563 // can't use 64-bit operands here because we don't have native results of
1564 // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't
1565 // work on large-endian machines.
1566 uint64_t mask = ~0ull >> (sizeof(uint32_t)*8);
1567 uint32_t n = rhsWords * 2;
1568 uint32_t m = (lhsWords * 2) - n;
1570 // Allocate space for the temporary values we need either on the stack, if
1571 // it will fit, or on the heap if it won't.
1572 uint32_t SPACE[128];
1577 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1580 Q = &SPACE[(m+n+1) + n];
1582 R = &SPACE[(m+n+1) + n + (m+n)];
1584 U = new uint32_t[m + n + 1];
1585 V = new uint32_t[n];
1586 Q = new uint32_t[m+n];
1588 R = new uint32_t[n];
1591 // Initialize the dividend
1592 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1593 for (unsigned i = 0; i < lhsWords; ++i) {
1594 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1595 U[i * 2] = tmp & mask;
1596 U[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1598 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1600 // Initialize the divisor
1601 memset(V, 0, (n)*sizeof(uint32_t));
1602 for (unsigned i = 0; i < rhsWords; ++i) {
1603 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1604 V[i * 2] = tmp & mask;
1605 V[i * 2 + 1] = tmp >> (sizeof(uint32_t)*8);
1608 // initialize the quotient and remainder
1609 memset(Q, 0, (m+n) * sizeof(uint32_t));
1611 memset(R, 0, n * sizeof(uint32_t));
1613 // Now, adjust m and n for the Knuth division. n is the number of words in
1614 // the divisor. m is the number of words by which the dividend exceeds the
1615 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1616 // contain any zero words or the Knuth algorithm fails.
1617 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1621 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1624 // If we're left with only a single word for the divisor, Knuth doesn't work
1625 // so we implement the short division algorithm here. This is much simpler
1626 // and faster because we are certain that we can divide a 64-bit quantity
1627 // by a 32-bit quantity at hardware speed and short division is simply a
1628 // series of such operations. This is just like doing short division but we
1629 // are using base 2^32 instead of base 10.
1630 assert(n != 0 && "Divide by zero?");
1632 uint32_t divisor = V[0];
1633 uint32_t remainder = 0;
1634 for (int i = m+n-1; i >= 0; i--) {
1635 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1636 if (partial_dividend == 0) {
1639 } else if (partial_dividend < divisor) {
1641 remainder = partial_dividend;
1642 } else if (partial_dividend == divisor) {
1646 Q[i] = partial_dividend / divisor;
1647 remainder = partial_dividend - (Q[i] * divisor);
1653 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1655 KnuthDiv(U, V, Q, R, m, n);
1658 // If the caller wants the quotient
1660 // Set up the Quotient value's memory.
1661 if (Quotient->BitWidth != LHS.BitWidth) {
1662 if (Quotient->isSingleWord())
1665 delete [] Quotient->pVal;
1666 Quotient->BitWidth = LHS.BitWidth;
1667 if (!Quotient->isSingleWord())
1668 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1672 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1674 if (lhsWords == 1) {
1676 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1677 if (Quotient->isSingleWord())
1678 Quotient->VAL = tmp;
1680 Quotient->pVal[0] = tmp;
1682 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1683 for (unsigned i = 0; i < lhsWords; ++i)
1685 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1689 // If the caller wants the remainder
1691 // Set up the Remainder value's memory.
1692 if (Remainder->BitWidth != RHS.BitWidth) {
1693 if (Remainder->isSingleWord())
1696 delete [] Remainder->pVal;
1697 Remainder->BitWidth = RHS.BitWidth;
1698 if (!Remainder->isSingleWord())
1699 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1703 // The remainder is in R. Reconstitute the remainder into Remainder's low
1705 if (rhsWords == 1) {
1707 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1708 if (Remainder->isSingleWord())
1709 Remainder->VAL = tmp;
1711 Remainder->pVal[0] = tmp;
1713 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1714 for (unsigned i = 0; i < rhsWords; ++i)
1715 Remainder->pVal[i] =
1716 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1720 // Clean up the memory we allocated.
1721 if (U != &SPACE[0]) {
1729 APInt APInt::udiv(const APInt& RHS) const {
1730 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1732 // First, deal with the easy case
1733 if (isSingleWord()) {
1734 assert(RHS.VAL != 0 && "Divide by zero?");
1735 return APInt(BitWidth, VAL / RHS.VAL);
1738 // Get some facts about the LHS and RHS number of bits and words
1739 uint32_t rhsBits = RHS.getActiveBits();
1740 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1741 assert(rhsWords && "Divided by zero???");
1742 uint32_t lhsBits = this->getActiveBits();
1743 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1745 // Deal with some degenerate cases
1748 return APInt(BitWidth, 0);
1749 else if (lhsWords < rhsWords || this->ult(RHS)) {
1750 // X / Y ===> 0, iff X < Y
1751 return APInt(BitWidth, 0);
1752 } else if (*this == RHS) {
1754 return APInt(BitWidth, 1);
1755 } else if (lhsWords == 1 && rhsWords == 1) {
1756 // All high words are zero, just use native divide
1757 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1760 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1761 APInt Quotient(1,0); // to hold result.
1762 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1766 APInt APInt::urem(const APInt& RHS) const {
1767 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1768 if (isSingleWord()) {
1769 assert(RHS.VAL != 0 && "Remainder by zero?");
1770 return APInt(BitWidth, VAL % RHS.VAL);
1773 // Get some facts about the LHS
1774 uint32_t lhsBits = getActiveBits();
1775 uint32_t lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1777 // Get some facts about the RHS
1778 uint32_t rhsBits = RHS.getActiveBits();
1779 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1780 assert(rhsWords && "Performing remainder operation by zero ???");
1782 // Check the degenerate cases
1783 if (lhsWords == 0) {
1785 return APInt(BitWidth, 0);
1786 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1787 // X % Y ===> X, iff X < Y
1789 } else if (*this == RHS) {
1791 return APInt(BitWidth, 0);
1792 } else if (lhsWords == 1) {
1793 // All high words are zero, just use native remainder
1794 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1797 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1798 APInt Remainder(1,0);
1799 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1803 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1804 APInt &Quotient, APInt &Remainder) {
1805 // Get some size facts about the dividend and divisor
1806 uint32_t lhsBits = LHS.getActiveBits();
1807 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1808 uint32_t rhsBits = RHS.getActiveBits();
1809 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1811 // Check the degenerate cases
1812 if (lhsWords == 0) {
1813 Quotient = 0; // 0 / Y ===> 0
1814 Remainder = 0; // 0 % Y ===> 0
1818 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1819 Quotient = 0; // X / Y ===> 0, iff X < Y
1820 Remainder = LHS; // X % Y ===> X, iff X < Y
1825 Quotient = 1; // X / X ===> 1
1826 Remainder = 0; // X % X ===> 0;
1830 if (lhsWords == 1 && rhsWords == 1) {
1831 // There is only one word to consider so use the native versions.
1832 if (LHS.isSingleWord()) {
1833 Quotient = APInt(LHS.getBitWidth(), LHS.VAL / RHS.VAL);
1834 Remainder = APInt(LHS.getBitWidth(), LHS.VAL % RHS.VAL);
1836 Quotient = APInt(LHS.getBitWidth(), LHS.pVal[0] / RHS.pVal[0]);
1837 Remainder = APInt(LHS.getBitWidth(), LHS.pVal[0] % RHS.pVal[0]);
1842 // Okay, lets do it the long way
1843 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1846 void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen,
1848 // Check our assumptions here
1849 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1850 "Radix should be 2, 8, 10, or 16!");
1851 assert(str && "String is null?");
1852 bool isNeg = str[0] == '-';
1855 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
1856 assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width");
1857 assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width");
1858 assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width");
1861 if (!isSingleWord())
1862 pVal = getClearedMemory(getNumWords());
1864 // Figure out if we can shift instead of multiply
1865 uint32_t shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1867 // Set up an APInt for the digit to add outside the loop so we don't
1868 // constantly construct/destruct it.
1869 APInt apdigit(getBitWidth(), 0);
1870 APInt apradix(getBitWidth(), radix);
1872 // Enter digit traversal loop
1873 for (unsigned i = 0; i < slen; i++) {
1876 char cdigit = str[i];
1878 if (!isxdigit(cdigit))
1879 assert(0 && "Invalid hex digit in string");
1880 if (isdigit(cdigit))
1881 digit = cdigit - '0';
1882 else if (cdigit >= 'a')
1883 digit = cdigit - 'a' + 10;
1884 else if (cdigit >= 'A')
1885 digit = cdigit - 'A' + 10;
1887 assert(0 && "huh? we shouldn't get here");
1888 } else if (isdigit(cdigit)) {
1889 digit = cdigit - '0';
1891 assert(0 && "Invalid character in digit string");
1894 // Shift or multiply the value by the radix
1900 // Add in the digit we just interpreted
1901 if (apdigit.isSingleWord())
1902 apdigit.VAL = digit;
1904 apdigit.pVal[0] = digit;
1907 // If its negative, put it in two's complement form
1914 std::string APInt::toString(uint8_t radix, bool wantSigned) const {
1915 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1916 "Radix should be 2, 8, 10, or 16!");
1917 static const char *digits[] = {
1918 "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"
1921 uint32_t bits_used = getActiveBits();
1922 if (isSingleWord()) {
1924 const char *format = (radix == 10 ? (wantSigned ? "%lld" : "%llu") :
1925 (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0)));
1928 int64_t sextVal = (int64_t(VAL) << (APINT_BITS_PER_WORD-BitWidth)) >>
1929 (APINT_BITS_PER_WORD-BitWidth);
1930 sprintf(buf, format, sextVal);
1932 sprintf(buf, format, VAL);
1937 uint32_t bit = v & 1;
1939 buf[bits_used] = digits[bit][0];
1948 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
1949 // because the number of bits per digit (1,3 and 4 respectively) divides
1950 // equaly. We just shift until there value is zero.
1952 // First, check for a zero value and just short circuit the logic below.
1957 size_t insert_at = 0;
1958 if (wantSigned && this->isNegative()) {
1959 // They want to print the signed version and it is a negative value
1960 // Flip the bits and add one to turn it into the equivalent positive
1961 // value and put a '-' in the result.
1967 // Just shift tmp right for each digit width until it becomes zero
1968 uint32_t shift = (radix == 16 ? 4 : (radix == 8 ? 3 : 1));
1969 uint64_t mask = radix - 1;
1970 APInt zero(tmp.getBitWidth(), 0);
1971 while (tmp.ne(zero)) {
1972 unsigned digit = (tmp.isSingleWord() ? tmp.VAL : tmp.pVal[0]) & mask;
1973 result.insert(insert_at, digits[digit]);
1974 tmp = tmp.lshr(shift);
1981 APInt divisor(4, radix);
1982 APInt zero(tmp.getBitWidth(), 0);
1983 size_t insert_at = 0;
1984 if (wantSigned && tmp[BitWidth-1]) {
1985 // They want to print the signed version and it is a negative value
1986 // Flip the bits and add one to turn it into the equivalent positive
1987 // value and put a '-' in the result.
1993 if (tmp == APInt(tmp.getBitWidth(), 0))
1995 else while (tmp.ne(zero)) {
1997 APInt tmp2(tmp.getBitWidth(), 0);
1998 divide(tmp, tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2000 uint32_t digit = APdigit.getZExtValue();
2001 assert(digit < radix && "divide failed");
2002 result.insert(insert_at,digits[digit]);
2009 void APInt::dump() const
2011 cerr << "APInt(" << BitWidth << ")=" << std::setbase(16);
2014 else for (unsigned i = getNumWords(); i > 0; i--) {
2015 cerr << pVal[i-1] << " ";
2017 cerr << " U(" << this->toStringUnsigned(10) << ") S("
2018 << this->toStringSigned(10) << ")" << std::setbase(10);
2021 // This implements a variety of operations on a representation of
2022 // arbitrary precision, two's-complement, bignum integer values.
2024 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2025 and unrestricting assumption. */
2026 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2028 /* Some handy functions local to this file. */
2031 /* Returns the integer part with the least significant BITS set.
2032 BITS cannot be zero. */
2034 lowBitMask(unsigned int bits)
2036 assert (bits != 0 && bits <= integerPartWidth);
2038 return ~(integerPart) 0 >> (integerPartWidth - bits);
2041 /* Returns the value of the lower half of PART. */
2043 lowHalf(integerPart part)
2045 return part & lowBitMask(integerPartWidth / 2);
2048 /* Returns the value of the upper half of PART. */
2050 highHalf(integerPart part)
2052 return part >> (integerPartWidth / 2);
2055 /* Returns the bit number of the most significant set bit of a part.
2056 If the input number has no bits set -1U is returned. */
2058 partMSB(integerPart value)
2060 unsigned int n, msb;
2065 n = integerPartWidth / 2;
2080 /* Returns the bit number of the least significant set bit of a
2081 part. If the input number has no bits set -1U is returned. */
2083 partLSB(integerPart value)
2085 unsigned int n, lsb;
2090 lsb = integerPartWidth - 1;
2091 n = integerPartWidth / 2;
2106 /* Sets the least significant part of a bignum to the input value, and
2107 zeroes out higher parts. */
2109 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2116 for(i = 1; i < parts; i++)
2120 /* Assign one bignum to another. */
2122 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2126 for(i = 0; i < parts; i++)
2130 /* Returns true if a bignum is zero, false otherwise. */
2132 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2136 for(i = 0; i < parts; i++)
2143 /* Extract the given bit of a bignum; returns 0 or 1. */
2145 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2147 return(parts[bit / integerPartWidth]
2148 & ((integerPart) 1 << bit % integerPartWidth)) != 0;
2151 /* Set the given bit of a bignum. */
2153 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2155 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2158 /* Returns the bit number of the least significant set bit of a
2159 number. If the input number has no bits set -1U is returned. */
2161 APInt::tcLSB(const integerPart *parts, unsigned int n)
2163 unsigned int i, lsb;
2165 for(i = 0; i < n; i++) {
2166 if (parts[i] != 0) {
2167 lsb = partLSB(parts[i]);
2169 return lsb + i * integerPartWidth;
2176 /* Returns the bit number of the most significant set bit of a number.
2177 If the input number has no bits set -1U is returned. */
2179 APInt::tcMSB(const integerPart *parts, unsigned int n)
2186 if (parts[n] != 0) {
2187 msb = partMSB(parts[n]);
2189 return msb + n * integerPartWidth;
2196 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2197 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2198 the least significant bit of DST. All high bits above srcBITS in
2199 DST are zero-filled. */
2201 APInt::tcExtract(integerPart *dst, unsigned int dstCount, const integerPart *src,
2202 unsigned int srcBits, unsigned int srcLSB)
2204 unsigned int firstSrcPart, dstParts, shift, n;
2206 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2207 assert (dstParts <= dstCount);
2209 firstSrcPart = srcLSB / integerPartWidth;
2210 tcAssign (dst, src + firstSrcPart, dstParts);
2212 shift = srcLSB % integerPartWidth;
2213 tcShiftRight (dst, dstParts, shift);
2215 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2216 in DST. If this is less that srcBits, append the rest, else
2217 clear the high bits. */
2218 n = dstParts * integerPartWidth - shift;
2220 integerPart mask = lowBitMask (srcBits - n);
2221 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2222 << n % integerPartWidth);
2223 } else if (n > srcBits) {
2224 if (srcBits % integerPartWidth)
2225 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2228 /* Clear high parts. */
2229 while (dstParts < dstCount)
2230 dst[dstParts++] = 0;
2233 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2235 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2236 integerPart c, unsigned int parts)
2242 for(i = 0; i < parts; i++) {
2247 dst[i] += rhs[i] + 1;
2258 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2260 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2261 integerPart c, unsigned int parts)
2267 for(i = 0; i < parts; i++) {
2272 dst[i] -= rhs[i] + 1;
2283 /* Negate a bignum in-place. */
2285 APInt::tcNegate(integerPart *dst, unsigned int parts)
2287 tcComplement(dst, parts);
2288 tcIncrement(dst, parts);
2291 /* DST += SRC * MULTIPLIER + CARRY if add is true
2292 DST = SRC * MULTIPLIER + CARRY if add is false
2294 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2295 they must start at the same point, i.e. DST == SRC.
2297 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2298 returned. Otherwise DST is filled with the least significant
2299 DSTPARTS parts of the result, and if all of the omitted higher
2300 parts were zero return zero, otherwise overflow occurred and
2303 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2304 integerPart multiplier, integerPart carry,
2305 unsigned int srcParts, unsigned int dstParts,
2310 /* Otherwise our writes of DST kill our later reads of SRC. */
2311 assert(dst <= src || dst >= src + srcParts);
2312 assert(dstParts <= srcParts + 1);
2314 /* N loops; minimum of dstParts and srcParts. */
2315 n = dstParts < srcParts ? dstParts: srcParts;
2317 for(i = 0; i < n; i++) {
2318 integerPart low, mid, high, srcPart;
2320 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2322 This cannot overflow, because
2324 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2326 which is less than n^2. */
2330 if (multiplier == 0 || srcPart == 0) {
2334 low = lowHalf(srcPart) * lowHalf(multiplier);
2335 high = highHalf(srcPart) * highHalf(multiplier);
2337 mid = lowHalf(srcPart) * highHalf(multiplier);
2338 high += highHalf(mid);
2339 mid <<= integerPartWidth / 2;
2340 if (low + mid < low)
2344 mid = highHalf(srcPart) * lowHalf(multiplier);
2345 high += highHalf(mid);
2346 mid <<= integerPartWidth / 2;
2347 if (low + mid < low)
2351 /* Now add carry. */
2352 if (low + carry < low)
2358 /* And now DST[i], and store the new low part there. */
2359 if (low + dst[i] < low)
2369 /* Full multiplication, there is no overflow. */
2370 assert(i + 1 == dstParts);
2374 /* We overflowed if there is carry. */
2378 /* We would overflow if any significant unwritten parts would be
2379 non-zero. This is true if any remaining src parts are non-zero
2380 and the multiplier is non-zero. */
2382 for(; i < srcParts; i++)
2386 /* We fitted in the narrow destination. */
2391 /* DST = LHS * RHS, where DST has the same width as the operands and
2392 is filled with the least significant parts of the result. Returns
2393 one if overflow occurred, otherwise zero. DST must be disjoint
2394 from both operands. */
2396 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2397 const integerPart *rhs, unsigned int parts)
2402 assert(dst != lhs && dst != rhs);
2405 tcSet(dst, 0, parts);
2407 for(i = 0; i < parts; i++)
2408 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2414 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2415 operands. No overflow occurs. DST must be disjoint from both
2416 operands. Returns the number of parts required to hold the
2419 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2420 const integerPart *rhs, unsigned int lhsParts,
2421 unsigned int rhsParts)
2423 /* Put the narrower number on the LHS for less loops below. */
2424 if (lhsParts > rhsParts) {
2425 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2429 assert(dst != lhs && dst != rhs);
2431 tcSet(dst, 0, rhsParts);
2433 for(n = 0; n < lhsParts; n++)
2434 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2436 n = lhsParts + rhsParts;
2438 return n - (dst[n - 1] == 0);
2442 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2443 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2444 set REMAINDER to the remainder, return zero. i.e.
2446 OLD_LHS = RHS * LHS + REMAINDER
2448 SCRATCH is a bignum of the same size as the operands and result for
2449 use by the routine; its contents need not be initialized and are
2450 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2453 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2454 integerPart *remainder, integerPart *srhs,
2457 unsigned int n, shiftCount;
2460 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2462 shiftCount = tcMSB(rhs, parts) + 1;
2463 if (shiftCount == 0)
2466 shiftCount = parts * integerPartWidth - shiftCount;
2467 n = shiftCount / integerPartWidth;
2468 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2470 tcAssign(srhs, rhs, parts);
2471 tcShiftLeft(srhs, parts, shiftCount);
2472 tcAssign(remainder, lhs, parts);
2473 tcSet(lhs, 0, parts);
2475 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2480 compare = tcCompare(remainder, srhs, parts);
2482 tcSubtract(remainder, srhs, 0, parts);
2486 if (shiftCount == 0)
2489 tcShiftRight(srhs, parts, 1);
2490 if ((mask >>= 1) == 0)
2491 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2497 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2498 There are no restrictions on COUNT. */
2500 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2503 unsigned int jump, shift;
2505 /* Jump is the inter-part jump; shift is is intra-part shift. */
2506 jump = count / integerPartWidth;
2507 shift = count % integerPartWidth;
2509 while (parts > jump) {
2514 /* dst[i] comes from the two parts src[i - jump] and, if we have
2515 an intra-part shift, src[i - jump - 1]. */
2516 part = dst[parts - jump];
2519 if (parts >= jump + 1)
2520 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2531 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2532 zero. There are no restrictions on COUNT. */
2534 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2537 unsigned int i, jump, shift;
2539 /* Jump is the inter-part jump; shift is is intra-part shift. */
2540 jump = count / integerPartWidth;
2541 shift = count % integerPartWidth;
2543 /* Perform the shift. This leaves the most significant COUNT bits
2544 of the result at zero. */
2545 for(i = 0; i < parts; i++) {
2548 if (i + jump >= parts) {
2551 part = dst[i + jump];
2554 if (i + jump + 1 < parts)
2555 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2564 /* Bitwise and of two bignums. */
2566 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2570 for(i = 0; i < parts; i++)
2574 /* Bitwise inclusive or of two bignums. */
2576 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2580 for(i = 0; i < parts; i++)
2584 /* Bitwise exclusive or of two bignums. */
2586 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2590 for(i = 0; i < parts; i++)
2594 /* Complement a bignum in-place. */
2596 APInt::tcComplement(integerPart *dst, unsigned int parts)
2600 for(i = 0; i < parts; i++)
2604 /* Comparison (unsigned) of two bignums. */
2606 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2611 if (lhs[parts] == rhs[parts])
2614 if (lhs[parts] > rhs[parts])
2623 /* Increment a bignum in-place, return the carry flag. */
2625 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2629 for(i = 0; i < parts; i++)
2636 /* Set the least significant BITS bits of a bignum, clear the
2639 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2645 while (bits > integerPartWidth) {
2646 dst[i++] = ~(integerPart) 0;
2647 bits -= integerPartWidth;
2651 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);