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(), (uint32_t)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 ID.AddInteger(BitWidth);
172 if (isSingleWord()) {
177 uint32_t NumWords = getNumWords();
178 for (unsigned i = 0; i < NumWords; ++i)
179 ID.AddInteger(pVal[i]);
182 /// add_1 - This function adds a single "digit" integer, y, to the multiple
183 /// "digit" integer array, x[]. x[] is modified to reflect the addition and
184 /// 1 is returned if there is a carry out, otherwise 0 is returned.
185 /// @returns the carry of the addition.
186 static bool add_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
187 for (uint32_t i = 0; i < len; ++i) {
190 y = 1; // Carry one to next digit.
192 y = 0; // No need to carry so exit early
199 /// @brief Prefix increment operator. Increments the APInt by one.
200 APInt& APInt::operator++() {
204 add_1(pVal, pVal, getNumWords(), 1);
205 return clearUnusedBits();
208 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from
209 /// the multi-digit integer array, x[], propagating the borrowed 1 value until
210 /// no further borrowing is neeeded or it runs out of "digits" in x. The result
211 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.
212 /// In other words, if y > x then this function returns 1, otherwise 0.
213 /// @returns the borrow out of the subtraction
214 static bool sub_1(uint64_t x[], uint32_t len, uint64_t y) {
215 for (uint32_t i = 0; i < len; ++i) {
219 y = 1; // We have to "borrow 1" from next "digit"
221 y = 0; // No need to borrow
222 break; // Remaining digits are unchanged so exit early
228 /// @brief Prefix decrement operator. Decrements the APInt by one.
229 APInt& APInt::operator--() {
233 sub_1(pVal, getNumWords(), 1);
234 return clearUnusedBits();
237 /// add - This function adds the integer array x to the integer array Y and
238 /// places the result in dest.
239 /// @returns the carry out from the addition
240 /// @brief General addition of 64-bit integer arrays
241 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,
244 for (uint32_t i = 0; i< len; ++i) {
245 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x
246 dest[i] = x[i] + y[i] + carry;
247 carry = dest[i] < limit || (carry && dest[i] == limit);
252 /// Adds the RHS APint to this APInt.
253 /// @returns this, after addition of RHS.
254 /// @brief Addition assignment operator.
255 APInt& APInt::operator+=(const APInt& RHS) {
256 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
260 add(pVal, pVal, RHS.pVal, getNumWords());
262 return clearUnusedBits();
265 /// Subtracts the integer array y from the integer array x
266 /// @returns returns the borrow out.
267 /// @brief Generalized subtraction of 64-bit integer arrays.
268 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,
271 for (uint32_t i = 0; i < len; ++i) {
272 uint64_t x_tmp = borrow ? x[i] - 1 : x[i];
273 borrow = y[i] > x_tmp || (borrow && x[i] == 0);
274 dest[i] = x_tmp - y[i];
279 /// Subtracts the RHS APInt from this APInt
280 /// @returns this, after subtraction
281 /// @brief Subtraction assignment operator.
282 APInt& APInt::operator-=(const APInt& RHS) {
283 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
287 sub(pVal, pVal, RHS.pVal, getNumWords());
288 return clearUnusedBits();
291 /// Multiplies an integer array, x by a a uint64_t integer and places the result
293 /// @returns the carry out of the multiplication.
294 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
295 static uint64_t mul_1(uint64_t dest[], uint64_t x[], uint32_t len, uint64_t y) {
296 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
297 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
300 // For each digit of x.
301 for (uint32_t i = 0; i < len; ++i) {
302 // Split x into high and low words
303 uint64_t lx = x[i] & 0xffffffffULL;
304 uint64_t hx = x[i] >> 32;
305 // hasCarry - A flag to indicate if there is a carry to the next digit.
306 // hasCarry == 0, no carry
307 // hasCarry == 1, has carry
308 // hasCarry == 2, no carry and the calculation result == 0.
309 uint8_t hasCarry = 0;
310 dest[i] = carry + lx * ly;
311 // Determine if the add above introduces carry.
312 hasCarry = (dest[i] < carry) ? 1 : 0;
313 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
314 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
315 // (2^32 - 1) + 2^32 = 2^64.
316 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
318 carry += (lx * hy) & 0xffffffffULL;
319 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
320 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
321 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
326 /// Multiplies integer array x by integer array y and stores the result into
327 /// the integer array dest. Note that dest's size must be >= xlen + ylen.
328 /// @brief Generalized multiplicate of integer arrays.
329 static void mul(uint64_t dest[], uint64_t x[], uint32_t xlen, uint64_t y[],
331 dest[xlen] = mul_1(dest, x, xlen, y[0]);
332 for (uint32_t i = 1; i < ylen; ++i) {
333 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
334 uint64_t carry = 0, lx = 0, hx = 0;
335 for (uint32_t j = 0; j < xlen; ++j) {
336 lx = x[j] & 0xffffffffULL;
338 // hasCarry - A flag to indicate if has carry.
339 // hasCarry == 0, no carry
340 // hasCarry == 1, has carry
341 // hasCarry == 2, no carry and the calculation result == 0.
342 uint8_t hasCarry = 0;
343 uint64_t resul = carry + lx * ly;
344 hasCarry = (resul < carry) ? 1 : 0;
345 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
346 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
348 carry += (lx * hy) & 0xffffffffULL;
349 resul = (carry << 32) | (resul & 0xffffffffULL);
351 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
352 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
353 ((lx * hy) >> 32) + hx * hy;
355 dest[i+xlen] = carry;
359 APInt& APInt::operator*=(const APInt& RHS) {
360 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
361 if (isSingleWord()) {
367 // Get some bit facts about LHS and check for zero
368 uint32_t lhsBits = getActiveBits();
369 uint32_t lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
374 // Get some bit facts about RHS and check for zero
375 uint32_t rhsBits = RHS.getActiveBits();
376 uint32_t rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
383 // Allocate space for the result
384 uint32_t destWords = rhsWords + lhsWords;
385 uint64_t *dest = getMemory(destWords);
387 // Perform the long multiply
388 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
390 // Copy result back into *this
392 uint32_t wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
393 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
395 // delete dest array and return
400 APInt& APInt::operator&=(const APInt& RHS) {
401 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
402 if (isSingleWord()) {
406 uint32_t numWords = getNumWords();
407 for (uint32_t i = 0; i < numWords; ++i)
408 pVal[i] &= RHS.pVal[i];
412 APInt& APInt::operator|=(const APInt& RHS) {
413 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
414 if (isSingleWord()) {
418 uint32_t numWords = getNumWords();
419 for (uint32_t i = 0; i < numWords; ++i)
420 pVal[i] |= RHS.pVal[i];
424 APInt& APInt::operator^=(const APInt& RHS) {
425 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
426 if (isSingleWord()) {
428 this->clearUnusedBits();
431 uint32_t numWords = getNumWords();
432 for (uint32_t i = 0; i < numWords; ++i)
433 pVal[i] ^= RHS.pVal[i];
434 return clearUnusedBits();
437 APInt APInt::operator&(const APInt& RHS) const {
438 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
440 return APInt(getBitWidth(), VAL & RHS.VAL);
442 uint32_t numWords = getNumWords();
443 uint64_t* val = getMemory(numWords);
444 for (uint32_t i = 0; i < numWords; ++i)
445 val[i] = pVal[i] & RHS.pVal[i];
446 return APInt(val, getBitWidth());
449 APInt APInt::operator|(const APInt& RHS) const {
450 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
452 return APInt(getBitWidth(), VAL | RHS.VAL);
454 uint32_t numWords = getNumWords();
455 uint64_t *val = getMemory(numWords);
456 for (uint32_t i = 0; i < numWords; ++i)
457 val[i] = pVal[i] | RHS.pVal[i];
458 return APInt(val, getBitWidth());
461 APInt APInt::operator^(const APInt& RHS) const {
462 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
464 return APInt(BitWidth, VAL ^ RHS.VAL);
466 uint32_t numWords = getNumWords();
467 uint64_t *val = getMemory(numWords);
468 for (uint32_t i = 0; i < numWords; ++i)
469 val[i] = pVal[i] ^ RHS.pVal[i];
471 // 0^0==1 so clear the high bits in case they got set.
472 return APInt(val, getBitWidth()).clearUnusedBits();
475 bool APInt::operator !() const {
479 for (uint32_t i = 0; i < getNumWords(); ++i)
485 APInt APInt::operator*(const APInt& RHS) const {
486 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
488 return APInt(BitWidth, VAL * RHS.VAL);
491 return Result.clearUnusedBits();
494 APInt APInt::operator+(const APInt& RHS) const {
495 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
497 return APInt(BitWidth, VAL + RHS.VAL);
498 APInt Result(BitWidth, 0);
499 add(Result.pVal, this->pVal, RHS.pVal, getNumWords());
500 return Result.clearUnusedBits();
503 APInt APInt::operator-(const APInt& RHS) const {
504 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
506 return APInt(BitWidth, VAL - RHS.VAL);
507 APInt Result(BitWidth, 0);
508 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());
509 return Result.clearUnusedBits();
512 bool APInt::operator[](uint32_t bitPosition) const {
513 return (maskBit(bitPosition) &
514 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0;
517 bool APInt::operator==(const APInt& RHS) const {
518 assert(BitWidth == RHS.BitWidth && "Comparison requires equal bit widths");
520 return VAL == RHS.VAL;
522 // Get some facts about the number of bits used in the two operands.
523 uint32_t n1 = getActiveBits();
524 uint32_t n2 = RHS.getActiveBits();
526 // If the number of bits isn't the same, they aren't equal
530 // If the number of bits fits in a word, we only need to compare the low word.
531 if (n1 <= APINT_BITS_PER_WORD)
532 return pVal[0] == RHS.pVal[0];
534 // Otherwise, compare everything
535 for (int i = whichWord(n1 - 1); i >= 0; --i)
536 if (pVal[i] != RHS.pVal[i])
541 bool APInt::operator==(uint64_t Val) const {
545 uint32_t n = getActiveBits();
546 if (n <= APINT_BITS_PER_WORD)
547 return pVal[0] == Val;
552 bool APInt::ult(const APInt& RHS) const {
553 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
555 return VAL < RHS.VAL;
557 // Get active bit length of both operands
558 uint32_t n1 = getActiveBits();
559 uint32_t n2 = RHS.getActiveBits();
561 // If magnitude of LHS is less than RHS, return true.
565 // If magnitude of RHS is greather than LHS, return false.
569 // If they bot fit in a word, just compare the low order word
570 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)
571 return pVal[0] < RHS.pVal[0];
573 // Otherwise, compare all words
574 uint32_t topWord = whichWord(std::max(n1,n2)-1);
575 for (int i = topWord; i >= 0; --i) {
576 if (pVal[i] > RHS.pVal[i])
578 if (pVal[i] < RHS.pVal[i])
584 bool APInt::slt(const APInt& RHS) const {
585 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
586 if (isSingleWord()) {
587 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
588 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);
589 return lhsSext < rhsSext;
594 bool lhsNeg = isNegative();
595 bool rhsNeg = rhs.isNegative();
597 // Sign bit is set so perform two's complement to make it positive
602 // Sign bit is set so perform two's complement to make it positive
607 // Now we have unsigned values to compare so do the comparison if necessary
608 // based on the negativeness of the values.
620 APInt& APInt::set(uint32_t bitPosition) {
622 VAL |= maskBit(bitPosition);
624 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
628 APInt& APInt::set() {
629 if (isSingleWord()) {
631 return clearUnusedBits();
634 // Set all the bits in all the words.
635 for (uint32_t i = 0; i < getNumWords(); ++i)
637 // Clear the unused ones
638 return clearUnusedBits();
641 /// Set the given bit to 0 whose position is given as "bitPosition".
642 /// @brief Set a given bit to 0.
643 APInt& APInt::clear(uint32_t bitPosition) {
645 VAL &= ~maskBit(bitPosition);
647 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
651 /// @brief Set every bit to 0.
652 APInt& APInt::clear() {
656 memset(pVal, 0, getNumWords() * APINT_WORD_SIZE);
660 /// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on
662 APInt APInt::operator~() const {
668 /// @brief Toggle every bit to its opposite value.
669 APInt& APInt::flip() {
670 if (isSingleWord()) {
672 return clearUnusedBits();
674 for (uint32_t i = 0; i < getNumWords(); ++i)
676 return clearUnusedBits();
679 /// Toggle a given bit to its opposite value whose position is given
680 /// as "bitPosition".
681 /// @brief Toggles a given bit to its opposite value.
682 APInt& APInt::flip(uint32_t bitPosition) {
683 assert(bitPosition < BitWidth && "Out of the bit-width range!");
684 if ((*this)[bitPosition]) clear(bitPosition);
685 else set(bitPosition);
689 uint32_t APInt::getBitsNeeded(const char* str, uint32_t slen, uint8_t radix) {
690 assert(str != 0 && "Invalid value string");
691 assert(slen > 0 && "Invalid string length");
693 // Each computation below needs to know if its negative
694 uint32_t isNegative = str[0] == '-';
699 // For radixes of power-of-two values, the bits required is accurately and
702 return slen + isNegative;
704 return slen * 3 + isNegative;
706 return slen * 4 + isNegative;
708 // Otherwise it must be radix == 10, the hard case
709 assert(radix == 10 && "Invalid radix");
711 // This is grossly inefficient but accurate. We could probably do something
712 // with a computation of roughly slen*64/20 and then adjust by the value of
713 // the first few digits. But, I'm not sure how accurate that could be.
715 // Compute a sufficient number of bits that is always large enough but might
716 // be too large. This avoids the assertion in the constructor.
717 uint32_t sufficient = slen*64/18;
719 // Convert to the actual binary value.
720 APInt tmp(sufficient, str, slen, radix);
722 // Compute how many bits are required.
723 return isNegative + tmp.logBase2() + 1;
726 uint64_t APInt::getHashValue() const {
727 // Put the bit width into the low order bits.
728 uint64_t hash = BitWidth;
730 // Add the sum of the words to the hash.
732 hash += VAL << 6; // clear separation of up to 64 bits
734 for (uint32_t i = 0; i < getNumWords(); ++i)
735 hash += pVal[i] << 6; // clear sepration of up to 64 bits
739 /// HiBits - This function returns the high "numBits" bits of this APInt.
740 APInt APInt::getHiBits(uint32_t numBits) const {
741 return APIntOps::lshr(*this, BitWidth - numBits);
744 /// LoBits - This function returns the low "numBits" bits of this APInt.
745 APInt APInt::getLoBits(uint32_t numBits) const {
746 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),
750 bool APInt::isPowerOf2() const {
751 return (!!*this) && !(*this & (*this - APInt(BitWidth,1)));
754 uint32_t APInt::countLeadingZeros() const {
757 Count = CountLeadingZeros_64(VAL);
759 for (uint32_t i = getNumWords(); i > 0u; --i) {
761 Count += APINT_BITS_PER_WORD;
763 Count += CountLeadingZeros_64(pVal[i-1]);
768 uint32_t remainder = BitWidth % APINT_BITS_PER_WORD;
770 Count -= APINT_BITS_PER_WORD - remainder;
771 return std::min(Count, BitWidth);
774 static uint32_t countLeadingOnes_64(uint64_t V, uint32_t skip) {
778 while (V && (V & (1ULL << 63))) {
785 uint32_t APInt::countLeadingOnes() const {
787 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
789 uint32_t highWordBits = BitWidth % APINT_BITS_PER_WORD;
790 uint32_t shift = (highWordBits == 0 ? 0 : APINT_BITS_PER_WORD - highWordBits);
791 int i = getNumWords() - 1;
792 uint32_t Count = countLeadingOnes_64(pVal[i], shift);
793 if (Count == highWordBits) {
794 for (i--; i >= 0; --i) {
795 if (pVal[i] == -1ULL)
796 Count += APINT_BITS_PER_WORD;
798 Count += countLeadingOnes_64(pVal[i], 0);
806 uint32_t APInt::countTrailingZeros() const {
808 return std::min(uint32_t(CountTrailingZeros_64(VAL)), BitWidth);
811 for (; i < getNumWords() && pVal[i] == 0; ++i)
812 Count += APINT_BITS_PER_WORD;
813 if (i < getNumWords())
814 Count += CountTrailingZeros_64(pVal[i]);
815 return std::min(Count, BitWidth);
818 uint32_t APInt::countTrailingOnes() const {
820 return std::min(uint32_t(CountTrailingOnes_64(VAL)), BitWidth);
823 for (; i < getNumWords() && pVal[i] == -1ULL; ++i)
824 Count += APINT_BITS_PER_WORD;
825 if (i < getNumWords())
826 Count += CountTrailingOnes_64(pVal[i]);
827 return std::min(Count, BitWidth);
830 uint32_t APInt::countPopulation() const {
832 return CountPopulation_64(VAL);
834 for (uint32_t i = 0; i < getNumWords(); ++i)
835 Count += CountPopulation_64(pVal[i]);
839 APInt APInt::byteSwap() const {
840 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
842 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
843 else if (BitWidth == 32)
844 return APInt(BitWidth, ByteSwap_32(uint32_t(VAL)));
845 else if (BitWidth == 48) {
846 uint32_t Tmp1 = uint32_t(VAL >> 16);
847 Tmp1 = ByteSwap_32(Tmp1);
848 uint16_t Tmp2 = uint16_t(VAL);
849 Tmp2 = ByteSwap_16(Tmp2);
850 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
851 } else if (BitWidth == 64)
852 return APInt(BitWidth, ByteSwap_64(VAL));
854 APInt Result(BitWidth, 0);
855 char *pByte = (char*)Result.pVal;
856 for (uint32_t i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) {
858 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i];
859 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp;
865 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,
867 APInt A = API1, B = API2;
870 B = APIntOps::urem(A, B);
876 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, uint32_t width) {
883 // Get the sign bit from the highest order bit
884 bool isNeg = T.I >> 63;
886 // Get the 11-bit exponent and adjust for the 1023 bit bias
887 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
889 // If the exponent is negative, the value is < 0 so just return 0.
891 return APInt(width, 0u);
893 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
894 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
896 // If the exponent doesn't shift all bits out of the mantissa
898 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
899 APInt(width, mantissa >> (52 - exp));
901 // If the client didn't provide enough bits for us to shift the mantissa into
902 // then the result is undefined, just return 0
903 if (width <= exp - 52)
904 return APInt(width, 0);
906 // Otherwise, we have to shift the mantissa bits up to the right location
907 APInt Tmp(width, mantissa);
908 Tmp = Tmp.shl((uint32_t)exp - 52);
909 return isNeg ? -Tmp : Tmp;
912 /// RoundToDouble - This function convert this APInt to a double.
913 /// The layout for double is as following (IEEE Standard 754):
914 /// --------------------------------------
915 /// | Sign Exponent Fraction Bias |
916 /// |-------------------------------------- |
917 /// | 1[63] 11[62-52] 52[51-00] 1023 |
918 /// --------------------------------------
919 double APInt::roundToDouble(bool isSigned) const {
921 // Handle the simple case where the value is contained in one uint64_t.
922 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
924 int64_t sext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);
930 // Determine if the value is negative.
931 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
933 // Construct the absolute value if we're negative.
934 APInt Tmp(isNeg ? -(*this) : (*this));
936 // Figure out how many bits we're using.
937 uint32_t n = Tmp.getActiveBits();
939 // The exponent (without bias normalization) is just the number of bits
940 // we are using. Note that the sign bit is gone since we constructed the
944 // Return infinity for exponent overflow
946 if (!isSigned || !isNeg)
947 return std::numeric_limits<double>::infinity();
949 return -std::numeric_limits<double>::infinity();
951 exp += 1023; // Increment for 1023 bias
953 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
954 // extract the high 52 bits from the correct words in pVal.
956 unsigned hiWord = whichWord(n-1);
958 mantissa = Tmp.pVal[0];
960 mantissa >>= n - 52; // shift down, we want the top 52 bits.
962 assert(hiWord > 0 && "huh?");
963 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
964 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
965 mantissa = hibits | lobits;
968 // The leading bit of mantissa is implicit, so get rid of it.
969 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
974 T.I = sign | (exp << 52) | mantissa;
978 // Truncate to new width.
979 APInt &APInt::trunc(uint32_t width) {
980 assert(width < BitWidth && "Invalid APInt Truncate request");
981 assert(width >= MIN_INT_BITS && "Can't truncate to 0 bits");
982 uint32_t wordsBefore = getNumWords();
984 uint32_t wordsAfter = getNumWords();
985 if (wordsBefore != wordsAfter) {
986 if (wordsAfter == 1) {
987 uint64_t *tmp = pVal;
991 uint64_t *newVal = getClearedMemory(wordsAfter);
992 for (uint32_t i = 0; i < wordsAfter; ++i)
998 return clearUnusedBits();
1001 // Sign extend to a new width.
1002 APInt &APInt::sext(uint32_t width) {
1003 assert(width > BitWidth && "Invalid APInt SignExtend request");
1004 assert(width <= MAX_INT_BITS && "Too many bits");
1005 // If the sign bit isn't set, this is the same as zext.
1006 if (!isNegative()) {
1011 // The sign bit is set. First, get some facts
1012 uint32_t wordsBefore = getNumWords();
1013 uint32_t wordBits = BitWidth % APINT_BITS_PER_WORD;
1015 uint32_t wordsAfter = getNumWords();
1017 // Mask the high order word appropriately
1018 if (wordsBefore == wordsAfter) {
1019 uint32_t newWordBits = width % APINT_BITS_PER_WORD;
1020 // The extension is contained to the wordsBefore-1th word.
1021 uint64_t mask = ~0ULL;
1023 mask >>= APINT_BITS_PER_WORD - newWordBits;
1025 if (wordsBefore == 1)
1028 pVal[wordsBefore-1] |= mask;
1029 return clearUnusedBits();
1032 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits;
1033 uint64_t *newVal = getMemory(wordsAfter);
1034 if (wordsBefore == 1)
1035 newVal[0] = VAL | mask;
1037 for (uint32_t i = 0; i < wordsBefore; ++i)
1038 newVal[i] = pVal[i];
1039 newVal[wordsBefore-1] |= mask;
1041 for (uint32_t i = wordsBefore; i < wordsAfter; i++)
1043 if (wordsBefore != 1)
1046 return clearUnusedBits();
1049 // Zero extend to a new width.
1050 APInt &APInt::zext(uint32_t width) {
1051 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
1052 assert(width <= MAX_INT_BITS && "Too many bits");
1053 uint32_t wordsBefore = getNumWords();
1055 uint32_t wordsAfter = getNumWords();
1056 if (wordsBefore != wordsAfter) {
1057 uint64_t *newVal = getClearedMemory(wordsAfter);
1058 if (wordsBefore == 1)
1061 for (uint32_t i = 0; i < wordsBefore; ++i)
1062 newVal[i] = pVal[i];
1063 if (wordsBefore != 1)
1070 APInt &APInt::zextOrTrunc(uint32_t width) {
1071 if (BitWidth < width)
1073 if (BitWidth > width)
1074 return trunc(width);
1078 APInt &APInt::sextOrTrunc(uint32_t width) {
1079 if (BitWidth < width)
1081 if (BitWidth > width)
1082 return trunc(width);
1086 /// Arithmetic right-shift this APInt by shiftAmt.
1087 /// @brief Arithmetic right-shift function.
1088 APInt APInt::ashr(const APInt &shiftAmt) const {
1089 return ashr((uint32_t)shiftAmt.getLimitedValue(BitWidth));
1092 /// Arithmetic right-shift this APInt by shiftAmt.
1093 /// @brief Arithmetic right-shift function.
1094 APInt APInt::ashr(uint32_t shiftAmt) const {
1095 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1096 // Handle a degenerate case
1100 // Handle single word shifts with built-in ashr
1101 if (isSingleWord()) {
1102 if (shiftAmt == BitWidth)
1103 return APInt(BitWidth, 0); // undefined
1105 uint32_t SignBit = APINT_BITS_PER_WORD - BitWidth;
1106 return APInt(BitWidth,
1107 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));
1111 // If all the bits were shifted out, the result is, technically, undefined.
1112 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1113 // issues in the algorithm below.
1114 if (shiftAmt == BitWidth) {
1116 return APInt(BitWidth, -1ULL, true);
1118 return APInt(BitWidth, 0);
1121 // Create some space for the result.
1122 uint64_t * val = new uint64_t[getNumWords()];
1124 // Compute some values needed by the following shift algorithms
1125 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1126 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1127 uint32_t breakWord = getNumWords() - 1 - offset; // last word affected
1128 uint32_t bitsInWord = whichBit(BitWidth); // how many bits in last word?
1129 if (bitsInWord == 0)
1130 bitsInWord = APINT_BITS_PER_WORD;
1132 // If we are shifting whole words, just move whole words
1133 if (wordShift == 0) {
1134 // Move the words containing significant bits
1135 for (uint32_t i = 0; i <= breakWord; ++i)
1136 val[i] = pVal[i+offset]; // move whole word
1138 // Adjust the top significant word for sign bit fill, if negative
1140 if (bitsInWord < APINT_BITS_PER_WORD)
1141 val[breakWord] |= ~0ULL << bitsInWord; // set high bits
1143 // Shift the low order words
1144 for (uint32_t i = 0; i < breakWord; ++i) {
1145 // This combines the shifted corresponding word with the low bits from
1146 // the next word (shifted into this word's high bits).
1147 val[i] = (pVal[i+offset] >> wordShift) |
1148 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1151 // Shift the break word. In this case there are no bits from the next word
1152 // to include in this word.
1153 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1155 // Deal with sign extenstion in the break word, and possibly the word before
1158 if (wordShift > bitsInWord) {
1161 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1162 val[breakWord] |= ~0ULL;
1164 val[breakWord] |= (~0ULL << (bitsInWord - wordShift));
1168 // Remaining words are 0 or -1, just assign them.
1169 uint64_t fillValue = (isNegative() ? -1ULL : 0);
1170 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1172 return APInt(val, BitWidth).clearUnusedBits();
1175 /// Logical right-shift this APInt by shiftAmt.
1176 /// @brief Logical right-shift function.
1177 APInt APInt::lshr(const APInt &shiftAmt) const {
1178 return lshr((uint32_t)shiftAmt.getLimitedValue(BitWidth));
1181 /// Logical right-shift this APInt by shiftAmt.
1182 /// @brief Logical right-shift function.
1183 APInt APInt::lshr(uint32_t shiftAmt) const {
1184 if (isSingleWord()) {
1185 if (shiftAmt == BitWidth)
1186 return APInt(BitWidth, 0);
1188 return APInt(BitWidth, this->VAL >> shiftAmt);
1191 // If all the bits were shifted out, the result is 0. This avoids issues
1192 // with shifting by the size of the integer type, which produces undefined
1193 // results. We define these "undefined results" to always be 0.
1194 if (shiftAmt == BitWidth)
1195 return APInt(BitWidth, 0);
1197 // If none of the bits are shifted out, the result is *this. This avoids
1198 // issues with shifting byt he size of the integer type, which produces
1199 // undefined results in the code below. This is also an optimization.
1203 // Create some space for the result.
1204 uint64_t * val = new uint64_t[getNumWords()];
1206 // If we are shifting less than a word, compute the shift with a simple carry
1207 if (shiftAmt < APINT_BITS_PER_WORD) {
1209 for (int i = getNumWords()-1; i >= 0; --i) {
1210 val[i] = (pVal[i] >> shiftAmt) | carry;
1211 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt);
1213 return APInt(val, BitWidth).clearUnusedBits();
1216 // Compute some values needed by the remaining shift algorithms
1217 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1218 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1220 // If we are shifting whole words, just move whole words
1221 if (wordShift == 0) {
1222 for (uint32_t i = 0; i < getNumWords() - offset; ++i)
1223 val[i] = pVal[i+offset];
1224 for (uint32_t i = getNumWords()-offset; i < getNumWords(); i++)
1226 return APInt(val,BitWidth).clearUnusedBits();
1229 // Shift the low order words
1230 uint32_t breakWord = getNumWords() - offset -1;
1231 for (uint32_t i = 0; i < breakWord; ++i)
1232 val[i] = (pVal[i+offset] >> wordShift) |
1233 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1234 // Shift the break word.
1235 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1237 // Remaining words are 0
1238 for (uint32_t i = breakWord+1; i < getNumWords(); ++i)
1240 return APInt(val, BitWidth).clearUnusedBits();
1243 /// Left-shift this APInt by shiftAmt.
1244 /// @brief Left-shift function.
1245 APInt APInt::shl(const APInt &shiftAmt) const {
1246 // It's undefined behavior in C to shift by BitWidth or greater, but
1247 return shl((uint32_t)shiftAmt.getLimitedValue(BitWidth));
1250 /// Left-shift this APInt by shiftAmt.
1251 /// @brief Left-shift function.
1252 APInt APInt::shl(uint32_t shiftAmt) const {
1253 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1254 if (isSingleWord()) {
1255 if (shiftAmt == BitWidth)
1256 return APInt(BitWidth, 0); // avoid undefined shift results
1257 return APInt(BitWidth, VAL << shiftAmt);
1260 // If all the bits were shifted out, the result is 0. This avoids issues
1261 // with shifting by the size of the integer type, which produces undefined
1262 // results. We define these "undefined results" to always be 0.
1263 if (shiftAmt == BitWidth)
1264 return APInt(BitWidth, 0);
1266 // If none of the bits are shifted out, the result is *this. This avoids a
1267 // lshr by the words size in the loop below which can produce incorrect
1268 // results. It also avoids the expensive computation below for a common case.
1272 // Create some space for the result.
1273 uint64_t * val = new uint64_t[getNumWords()];
1275 // If we are shifting less than a word, do it the easy way
1276 if (shiftAmt < APINT_BITS_PER_WORD) {
1278 for (uint32_t i = 0; i < getNumWords(); i++) {
1279 val[i] = pVal[i] << shiftAmt | carry;
1280 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);
1282 return APInt(val, BitWidth).clearUnusedBits();
1285 // Compute some values needed by the remaining shift algorithms
1286 uint32_t wordShift = shiftAmt % APINT_BITS_PER_WORD;
1287 uint32_t offset = shiftAmt / APINT_BITS_PER_WORD;
1289 // If we are shifting whole words, just move whole words
1290 if (wordShift == 0) {
1291 for (uint32_t i = 0; i < offset; i++)
1293 for (uint32_t i = offset; i < getNumWords(); i++)
1294 val[i] = pVal[i-offset];
1295 return APInt(val,BitWidth).clearUnusedBits();
1298 // Copy whole words from this to Result.
1299 uint32_t i = getNumWords() - 1;
1300 for (; i > offset; --i)
1301 val[i] = pVal[i-offset] << wordShift |
1302 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);
1303 val[offset] = pVal[0] << wordShift;
1304 for (i = 0; i < offset; ++i)
1306 return APInt(val, BitWidth).clearUnusedBits();
1309 APInt APInt::rotl(const APInt &rotateAmt) const {
1310 return rotl((uint32_t)rotateAmt.getLimitedValue(BitWidth));
1313 APInt APInt::rotl(uint32_t rotateAmt) const {
1316 // Don't get too fancy, just use existing shift/or facilities
1320 lo.lshr(BitWidth - rotateAmt);
1324 APInt APInt::rotr(const APInt &rotateAmt) const {
1325 return rotr((uint32_t)rotateAmt.getLimitedValue(BitWidth));
1328 APInt APInt::rotr(uint32_t rotateAmt) const {
1331 // Don't get too fancy, just use existing shift/or facilities
1335 hi.shl(BitWidth - rotateAmt);
1339 // Square Root - this method computes and returns the square root of "this".
1340 // Three mechanisms are used for computation. For small values (<= 5 bits),
1341 // a table lookup is done. This gets some performance for common cases. For
1342 // values using less than 52 bits, the value is converted to double and then
1343 // the libc sqrt function is called. The result is rounded and then converted
1344 // back to a uint64_t which is then used to construct the result. Finally,
1345 // the Babylonian method for computing square roots is used.
1346 APInt APInt::sqrt() const {
1348 // Determine the magnitude of the value.
1349 uint32_t magnitude = getActiveBits();
1351 // Use a fast table for some small values. This also gets rid of some
1352 // rounding errors in libc sqrt for small values.
1353 if (magnitude <= 5) {
1354 static const uint8_t results[32] = {
1357 /* 3- 6 */ 2, 2, 2, 2,
1358 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1359 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1360 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1363 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
1366 // If the magnitude of the value fits in less than 52 bits (the precision of
1367 // an IEEE double precision floating point value), then we can use the
1368 // libc sqrt function which will probably use a hardware sqrt computation.
1369 // This should be faster than the algorithm below.
1370 if (magnitude < 52) {
1372 // Amazingly, VC++ doesn't have round().
1373 return APInt(BitWidth,
1374 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5);
1376 return APInt(BitWidth,
1377 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
1381 // Okay, all the short cuts are exhausted. We must compute it. The following
1382 // is a classical Babylonian method for computing the square root. This code
1383 // was adapted to APINt from a wikipedia article on such computations.
1384 // See http://www.wikipedia.org/ and go to the page named
1385 // Calculate_an_integer_square_root.
1386 uint32_t nbits = BitWidth, i = 4;
1387 APInt testy(BitWidth, 16);
1388 APInt x_old(BitWidth, 1);
1389 APInt x_new(BitWidth, 0);
1390 APInt two(BitWidth, 2);
1392 // Select a good starting value using binary logarithms.
1393 for (;; i += 2, testy = testy.shl(2))
1394 if (i >= nbits || this->ule(testy)) {
1395 x_old = x_old.shl(i / 2);
1399 // Use the Babylonian method to arrive at the integer square root:
1401 x_new = (this->udiv(x_old) + x_old).udiv(two);
1402 if (x_old.ule(x_new))
1407 // Make sure we return the closest approximation
1408 // NOTE: The rounding calculation below is correct. It will produce an
1409 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1410 // determined to be a rounding issue with pari/gp as it begins to use a
1411 // floating point representation after 192 bits. There are no discrepancies
1412 // between this algorithm and pari/gp for bit widths < 192 bits.
1413 APInt square(x_old * x_old);
1414 APInt nextSquare((x_old + 1) * (x_old +1));
1415 if (this->ult(square))
1417 else if (this->ule(nextSquare)) {
1418 APInt midpoint((nextSquare - square).udiv(two));
1419 APInt offset(*this - square);
1420 if (offset.ult(midpoint))
1425 assert(0 && "Error in APInt::sqrt computation");
1429 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1430 /// iterative extended Euclidean algorithm is used to solve for this value,
1431 /// however we simplify it to speed up calculating only the inverse, and take
1432 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1433 /// (potentially large) APInts around.
1434 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1435 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1437 // Using the properties listed at the following web page (accessed 06/21/08):
1438 // http://www.numbertheory.org/php/euclid.html
1439 // (especially the properties numbered 3, 4 and 9) it can be proved that
1440 // BitWidth bits suffice for all the computations in the algorithm implemented
1441 // below. More precisely, this number of bits suffice if the multiplicative
1442 // inverse exists, but may not suffice for the general extended Euclidean
1445 APInt r[2] = { modulo, *this };
1446 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1447 APInt q(BitWidth, 0);
1450 for (i = 0; r[i^1] != 0; i ^= 1) {
1451 // An overview of the math without the confusing bit-flipping:
1452 // q = r[i-2] / r[i-1]
1453 // r[i] = r[i-2] % r[i-1]
1454 // t[i] = t[i-2] - t[i-1] * q
1455 udivrem(r[i], r[i^1], q, r[i]);
1459 // If this APInt and the modulo are not coprime, there is no multiplicative
1460 // inverse, so return 0. We check this by looking at the next-to-last
1461 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1464 return APInt(BitWidth, 0);
1466 // The next-to-last t is the multiplicative inverse. However, we are
1467 // interested in a positive inverse. Calcuate a positive one from a negative
1468 // one if necessary. A simple addition of the modulo suffices because
1469 // abs(t[i]) is known to less than *this/2 (see the link above).
1470 return t[i].isNegative() ? t[i] + modulo : t[i];
1473 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1474 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1475 /// variables here have the same names as in the algorithm. Comments explain
1476 /// the algorithm and any deviation from it.
1477 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1478 uint32_t m, uint32_t n) {
1479 assert(u && "Must provide dividend");
1480 assert(v && "Must provide divisor");
1481 assert(q && "Must provide quotient");
1482 assert(u != v && u != q && v != q && "Must us different memory");
1483 assert(n>1 && "n must be > 1");
1485 // Knuth uses the value b as the base of the number system. In our case b
1486 // is 2^31 so we just set it to -1u.
1487 uint64_t b = uint64_t(1) << 32;
1489 DEBUG(cerr << "KnuthDiv: m=" << m << " n=" << n << '\n');
1490 DEBUG(cerr << "KnuthDiv: original:");
1491 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1492 DEBUG(cerr << " by");
1493 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1494 DEBUG(cerr << '\n');
1495 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1496 // u and v by d. Note that we have taken Knuth's advice here to use a power
1497 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1498 // 2 allows us to shift instead of multiply and it is easy to determine the
1499 // shift amount from the leading zeros. We are basically normalizing the u
1500 // and v so that its high bits are shifted to the top of v's range without
1501 // overflow. Note that this can require an extra word in u so that u must
1502 // be of length m+n+1.
1503 uint32_t shift = CountLeadingZeros_32(v[n-1]);
1504 uint32_t v_carry = 0;
1505 uint32_t u_carry = 0;
1507 for (uint32_t i = 0; i < m+n; ++i) {
1508 uint32_t u_tmp = u[i] >> (32 - shift);
1509 u[i] = (u[i] << shift) | u_carry;
1512 for (uint32_t i = 0; i < n; ++i) {
1513 uint32_t v_tmp = v[i] >> (32 - shift);
1514 v[i] = (v[i] << shift) | v_carry;
1519 DEBUG(cerr << "KnuthDiv: normal:");
1520 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << std::setbase(16) << u[i]);
1521 DEBUG(cerr << " by");
1522 DEBUG(for (int i = n; i >0; i--) cerr << " " << std::setbase(16) << v[i-1]);
1523 DEBUG(cerr << '\n');
1525 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1528 DEBUG(cerr << "KnuthDiv: quotient digit #" << j << '\n');
1529 // D3. [Calculate q'.].
1530 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1531 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1532 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1533 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1534 // on v[n-2] determines at high speed most of the cases in which the trial
1535 // value qp is one too large, and it eliminates all cases where qp is two
1537 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
1538 DEBUG(cerr << "KnuthDiv: dividend == " << dividend << '\n');
1539 uint64_t qp = dividend / v[n-1];
1540 uint64_t rp = dividend % v[n-1];
1541 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1544 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1547 DEBUG(cerr << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1549 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1550 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1551 // consists of a simple multiplication by a one-place number, combined with
1554 for (uint32_t i = 0; i < n; ++i) {
1555 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32);
1556 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]);
1557 bool borrow = subtrahend > u_tmp;
1558 DEBUG(cerr << "KnuthDiv: u_tmp == " << u_tmp
1559 << ", subtrahend == " << subtrahend
1560 << ", borrow = " << borrow << '\n');
1562 uint64_t result = u_tmp - subtrahend;
1564 u[k++] = (uint32_t)(result & (b-1)); // subtract low word
1565 u[k++] = (uint32_t)(result >> 32); // subtract high word
1566 while (borrow && k <= m+n) { // deal with borrow to the left
1572 DEBUG(cerr << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " <<
1575 DEBUG(cerr << "KnuthDiv: after subtraction:");
1576 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1577 DEBUG(cerr << '\n');
1578 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1579 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1580 // true value plus b**(n+1), namely as the b's complement of
1581 // the true value, and a "borrow" to the left should be remembered.
1584 bool carry = true; // true because b's complement is "complement + 1"
1585 for (uint32_t i = 0; i <= m+n; ++i) {
1586 u[i] = ~u[i] + carry; // b's complement
1587 carry = carry && u[i] == 0;
1590 DEBUG(cerr << "KnuthDiv: after complement:");
1591 DEBUG(for (int i = m+n; i >=0; i--) cerr << " " << u[i]);
1592 DEBUG(cerr << '\n');
1594 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1595 // negative, go to step D6; otherwise go on to step D7.
1596 q[j] = (uint32_t)qp;
1598 // D6. [Add back]. The probability that this step is necessary is very
1599 // small, on the order of only 2/b. Make sure that test data accounts for
1600 // this possibility. Decrease q[j] by 1
1602 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1603 // A carry will occur to the left of u[j+n], and it should be ignored
1604 // since it cancels with the borrow that occurred in D4.
1606 for (uint32_t i = 0; i < n; i++) {
1607 uint32_t limit = std::min(u[j+i],v[i]);
1608 u[j+i] += v[i] + carry;
1609 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1613 DEBUG(cerr << "KnuthDiv: after correction:");
1614 DEBUG(for (int i = m+n; i >=0; i--) cerr <<" " << u[i]);
1615 DEBUG(cerr << "\nKnuthDiv: digit result = " << q[j] << '\n');
1617 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1620 DEBUG(cerr << "KnuthDiv: quotient:");
1621 DEBUG(for (int i = m; i >=0; i--) cerr <<" " << q[i]);
1622 DEBUG(cerr << '\n');
1624 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1625 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1626 // compute the remainder (urem uses this).
1628 // The value d is expressed by the "shift" value above since we avoided
1629 // multiplication by d by using a shift left. So, all we have to do is
1630 // shift right here. In order to mak
1633 DEBUG(cerr << "KnuthDiv: remainder:");
1634 for (int i = n-1; i >= 0; i--) {
1635 r[i] = (u[i] >> shift) | carry;
1636 carry = u[i] << (32 - shift);
1637 DEBUG(cerr << " " << r[i]);
1640 for (int i = n-1; i >= 0; i--) {
1642 DEBUG(cerr << " " << r[i]);
1645 DEBUG(cerr << '\n');
1647 DEBUG(cerr << std::setbase(10) << '\n');
1650 void APInt::divide(const APInt LHS, uint32_t lhsWords,
1651 const APInt &RHS, uint32_t rhsWords,
1652 APInt *Quotient, APInt *Remainder)
1654 assert(lhsWords >= rhsWords && "Fractional result");
1656 // First, compose the values into an array of 32-bit words instead of
1657 // 64-bit words. This is a necessity of both the "short division" algorithm
1658 // and the the Knuth "classical algorithm" which requires there to be native
1659 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1660 // can't use 64-bit operands here because we don't have native results of
1661 // 128-bits. Furthremore, casting the 64-bit values to 32-bit values won't
1662 // work on large-endian machines.
1663 uint64_t mask = ~0ull >> (sizeof(uint32_t)*8);
1664 uint32_t n = rhsWords * 2;
1665 uint32_t m = (lhsWords * 2) - n;
1667 // Allocate space for the temporary values we need either on the stack, if
1668 // it will fit, or on the heap if it won't.
1669 uint32_t SPACE[128];
1674 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1677 Q = &SPACE[(m+n+1) + n];
1679 R = &SPACE[(m+n+1) + n + (m+n)];
1681 U = new uint32_t[m + n + 1];
1682 V = new uint32_t[n];
1683 Q = new uint32_t[m+n];
1685 R = new uint32_t[n];
1688 // Initialize the dividend
1689 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1690 for (unsigned i = 0; i < lhsWords; ++i) {
1691 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
1692 U[i * 2] = (uint32_t)(tmp & mask);
1693 U[i * 2 + 1] = (uint32_t)(tmp >> (sizeof(uint32_t)*8));
1695 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1697 // Initialize the divisor
1698 memset(V, 0, (n)*sizeof(uint32_t));
1699 for (unsigned i = 0; i < rhsWords; ++i) {
1700 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
1701 V[i * 2] = (uint32_t)(tmp & mask);
1702 V[i * 2 + 1] = (uint32_t)(tmp >> (sizeof(uint32_t)*8));
1705 // initialize the quotient and remainder
1706 memset(Q, 0, (m+n) * sizeof(uint32_t));
1708 memset(R, 0, n * sizeof(uint32_t));
1710 // Now, adjust m and n for the Knuth division. n is the number of words in
1711 // the divisor. m is the number of words by which the dividend exceeds the
1712 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1713 // contain any zero words or the Knuth algorithm fails.
1714 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1718 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1721 // If we're left with only a single word for the divisor, Knuth doesn't work
1722 // so we implement the short division algorithm here. This is much simpler
1723 // and faster because we are certain that we can divide a 64-bit quantity
1724 // by a 32-bit quantity at hardware speed and short division is simply a
1725 // series of such operations. This is just like doing short division but we
1726 // are using base 2^32 instead of base 10.
1727 assert(n != 0 && "Divide by zero?");
1729 uint32_t divisor = V[0];
1730 uint32_t remainder = 0;
1731 for (int i = m+n-1; i >= 0; i--) {
1732 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1733 if (partial_dividend == 0) {
1736 } else if (partial_dividend < divisor) {
1738 remainder = (uint32_t)partial_dividend;
1739 } else if (partial_dividend == divisor) {
1743 Q[i] = (uint32_t)(partial_dividend / divisor);
1744 remainder = (uint32_t)(partial_dividend - (Q[i] * divisor));
1750 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1752 KnuthDiv(U, V, Q, R, m, n);
1755 // If the caller wants the quotient
1757 // Set up the Quotient value's memory.
1758 if (Quotient->BitWidth != LHS.BitWidth) {
1759 if (Quotient->isSingleWord())
1762 delete [] Quotient->pVal;
1763 Quotient->BitWidth = LHS.BitWidth;
1764 if (!Quotient->isSingleWord())
1765 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
1769 // The quotient is in Q. Reconstitute the quotient into Quotient's low
1771 if (lhsWords == 1) {
1773 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1774 if (Quotient->isSingleWord())
1775 Quotient->VAL = tmp;
1777 Quotient->pVal[0] = tmp;
1779 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1780 for (unsigned i = 0; i < lhsWords; ++i)
1782 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1786 // If the caller wants the remainder
1788 // Set up the Remainder value's memory.
1789 if (Remainder->BitWidth != RHS.BitWidth) {
1790 if (Remainder->isSingleWord())
1793 delete [] Remainder->pVal;
1794 Remainder->BitWidth = RHS.BitWidth;
1795 if (!Remainder->isSingleWord())
1796 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
1800 // The remainder is in R. Reconstitute the remainder into Remainder's low
1802 if (rhsWords == 1) {
1804 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1805 if (Remainder->isSingleWord())
1806 Remainder->VAL = tmp;
1808 Remainder->pVal[0] = tmp;
1810 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1811 for (unsigned i = 0; i < rhsWords; ++i)
1812 Remainder->pVal[i] =
1813 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1817 // Clean up the memory we allocated.
1818 if (U != &SPACE[0]) {
1826 APInt APInt::udiv(const APInt& RHS) const {
1827 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1829 // First, deal with the easy case
1830 if (isSingleWord()) {
1831 assert(RHS.VAL != 0 && "Divide by zero?");
1832 return APInt(BitWidth, VAL / RHS.VAL);
1835 // Get some facts about the LHS and RHS number of bits and words
1836 uint32_t rhsBits = RHS.getActiveBits();
1837 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1838 assert(rhsWords && "Divided by zero???");
1839 uint32_t lhsBits = this->getActiveBits();
1840 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1842 // Deal with some degenerate cases
1845 return APInt(BitWidth, 0);
1846 else if (lhsWords < rhsWords || this->ult(RHS)) {
1847 // X / Y ===> 0, iff X < Y
1848 return APInt(BitWidth, 0);
1849 } else if (*this == RHS) {
1851 return APInt(BitWidth, 1);
1852 } else if (lhsWords == 1 && rhsWords == 1) {
1853 // All high words are zero, just use native divide
1854 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
1857 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1858 APInt Quotient(1,0); // to hold result.
1859 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0);
1863 APInt APInt::urem(const APInt& RHS) const {
1864 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1865 if (isSingleWord()) {
1866 assert(RHS.VAL != 0 && "Remainder by zero?");
1867 return APInt(BitWidth, VAL % RHS.VAL);
1870 // Get some facts about the LHS
1871 uint32_t lhsBits = getActiveBits();
1872 uint32_t lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
1874 // Get some facts about the RHS
1875 uint32_t rhsBits = RHS.getActiveBits();
1876 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1877 assert(rhsWords && "Performing remainder operation by zero ???");
1879 // Check the degenerate cases
1880 if (lhsWords == 0) {
1882 return APInt(BitWidth, 0);
1883 } else if (lhsWords < rhsWords || this->ult(RHS)) {
1884 // X % Y ===> X, iff X < Y
1886 } else if (*this == RHS) {
1888 return APInt(BitWidth, 0);
1889 } else if (lhsWords == 1) {
1890 // All high words are zero, just use native remainder
1891 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
1894 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1895 APInt Remainder(1,0);
1896 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder);
1900 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1901 APInt &Quotient, APInt &Remainder) {
1902 // Get some size facts about the dividend and divisor
1903 uint32_t lhsBits = LHS.getActiveBits();
1904 uint32_t lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1905 uint32_t rhsBits = RHS.getActiveBits();
1906 uint32_t rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
1908 // Check the degenerate cases
1909 if (lhsWords == 0) {
1910 Quotient = 0; // 0 / Y ===> 0
1911 Remainder = 0; // 0 % Y ===> 0
1915 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1916 Quotient = 0; // X / Y ===> 0, iff X < Y
1917 Remainder = LHS; // X % Y ===> X, iff X < Y
1922 Quotient = 1; // X / X ===> 1
1923 Remainder = 0; // X % X ===> 0;
1927 if (lhsWords == 1 && rhsWords == 1) {
1928 // There is only one word to consider so use the native versions.
1929 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1930 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1931 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1932 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
1936 // Okay, lets do it the long way
1937 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1940 void APInt::fromString(uint32_t numbits, const char *str, uint32_t slen,
1942 // Check our assumptions here
1943 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
1944 "Radix should be 2, 8, 10, or 16!");
1945 assert(str && "String is null?");
1946 bool isNeg = str[0] == '-';
1949 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
1950 assert((slen*3 <= numbits || radix != 8) && "Insufficient bit width");
1951 assert((slen*4 <= numbits || radix != 16) && "Insufficient bit width");
1952 assert(((slen*64)/22 <= numbits || radix != 10) && "Insufficient bit width");
1955 if (!isSingleWord())
1956 pVal = getClearedMemory(getNumWords());
1958 // Figure out if we can shift instead of multiply
1959 uint32_t shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1961 // Set up an APInt for the digit to add outside the loop so we don't
1962 // constantly construct/destruct it.
1963 APInt apdigit(getBitWidth(), 0);
1964 APInt apradix(getBitWidth(), radix);
1966 // Enter digit traversal loop
1967 for (unsigned i = 0; i < slen; i++) {
1970 char cdigit = str[i];
1972 if (!isxdigit(cdigit))
1973 assert(0 && "Invalid hex digit in string");
1974 if (isdigit(cdigit))
1975 digit = cdigit - '0';
1976 else if (cdigit >= 'a')
1977 digit = cdigit - 'a' + 10;
1978 else if (cdigit >= 'A')
1979 digit = cdigit - 'A' + 10;
1981 assert(0 && "huh? we shouldn't get here");
1982 } else if (isdigit(cdigit)) {
1983 digit = cdigit - '0';
1984 assert((radix == 10 ||
1985 (radix == 8 && digit != 8 && digit != 9) ||
1986 (radix == 2 && (digit == 0 || digit == 1))) &&
1987 "Invalid digit in string for given radix");
1989 assert(0 && "Invalid character in digit string");
1992 // Shift or multiply the value by the radix
1998 // Add in the digit we just interpreted
1999 if (apdigit.isSingleWord())
2000 apdigit.VAL = digit;
2002 apdigit.pVal[0] = digit;
2005 // If its negative, put it in two's complement form
2012 std::string APInt::toString(uint8_t radix, bool wantSigned) const {
2013 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) &&
2014 "Radix should be 2, 8, 10, or 16!");
2015 static const char *const digits[] = {
2016 "0","1","2","3","4","5","6","7","8","9","A","B","C","D","E","F"
2019 uint32_t bits_used = getActiveBits();
2020 if (isSingleWord()) {
2022 const char *format = (radix == 10 ? (wantSigned ? "%lld" : "%llu") :
2023 (radix == 16 ? "%llX" : (radix == 8 ? "%llo" : 0)));
2026 int64_t sextVal = (int64_t(VAL) << (APINT_BITS_PER_WORD-BitWidth)) >>
2027 (APINT_BITS_PER_WORD-BitWidth);
2028 sprintf(buf, format, sextVal);
2030 sprintf(buf, format, VAL);
2035 uint32_t bit = (uint32_t)v & 1;
2037 buf[bits_used] = digits[bit][0];
2046 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2047 // because the number of bits per digit (1,3 and 4 respectively) divides
2048 // equaly. We just shift until there value is zero.
2050 // First, check for a zero value and just short circuit the logic below.
2055 size_t insert_at = 0;
2056 if (wantSigned && this->isNegative()) {
2057 // They want to print the signed version and it is a negative value
2058 // Flip the bits and add one to turn it into the equivalent positive
2059 // value and put a '-' in the result.
2065 // Just shift tmp right for each digit width until it becomes zero
2066 uint32_t shift = (radix == 16 ? 4 : (radix == 8 ? 3 : 1));
2067 uint64_t mask = radix - 1;
2068 APInt zero(tmp.getBitWidth(), 0);
2069 while (tmp.ne(zero)) {
2071 (unsigned)((tmp.isSingleWord() ? tmp.VAL : tmp.pVal[0]) & mask);
2072 result.insert(insert_at, digits[digit]);
2073 tmp = tmp.lshr(shift);
2080 APInt divisor(4, radix);
2081 APInt zero(tmp.getBitWidth(), 0);
2082 size_t insert_at = 0;
2083 if (wantSigned && tmp[BitWidth-1]) {
2084 // They want to print the signed version and it is a negative value
2085 // Flip the bits and add one to turn it into the equivalent positive
2086 // value and put a '-' in the result.
2094 else while (tmp.ne(zero)) {
2096 APInt tmp2(tmp.getBitWidth(), 0);
2097 divide(tmp, tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
2099 uint32_t digit = (uint32_t)APdigit.getZExtValue();
2100 assert(digit < radix && "divide failed");
2101 result.insert(insert_at,digits[digit]);
2108 void APInt::dump() const
2110 cerr << "APInt(" << BitWidth << ")=" << std::setbase(16);
2113 else for (unsigned i = getNumWords(); i > 0; i--) {
2114 cerr << pVal[i-1] << " ";
2116 cerr << " U(" << this->toStringUnsigned(10) << ") S("
2117 << this->toStringSigned(10) << ")" << std::setbase(10);
2120 // This implements a variety of operations on a representation of
2121 // arbitrary precision, two's-complement, bignum integer values.
2123 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2124 and unrestricting assumption. */
2125 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0);
2127 /* Some handy functions local to this file. */
2130 /* Returns the integer part with the least significant BITS set.
2131 BITS cannot be zero. */
2132 static inline integerPart
2133 lowBitMask(unsigned int bits)
2135 assert (bits != 0 && bits <= integerPartWidth);
2137 return ~(integerPart) 0 >> (integerPartWidth - bits);
2140 /* Returns the value of the lower half of PART. */
2141 static inline integerPart
2142 lowHalf(integerPart part)
2144 return part & lowBitMask(integerPartWidth / 2);
2147 /* Returns the value of the upper half of PART. */
2148 static inline integerPart
2149 highHalf(integerPart part)
2151 return part >> (integerPartWidth / 2);
2154 /* Returns the bit number of the most significant set bit of a part.
2155 If the input number has no bits set -1U is returned. */
2157 partMSB(integerPart value)
2159 unsigned int n, msb;
2164 n = integerPartWidth / 2;
2179 /* Returns the bit number of the least significant set bit of a
2180 part. If the input number has no bits set -1U is returned. */
2182 partLSB(integerPart value)
2184 unsigned int n, lsb;
2189 lsb = integerPartWidth - 1;
2190 n = integerPartWidth / 2;
2205 /* Sets the least significant part of a bignum to the input value, and
2206 zeroes out higher parts. */
2208 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)
2215 for(i = 1; i < parts; i++)
2219 /* Assign one bignum to another. */
2221 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)
2225 for(i = 0; i < parts; i++)
2229 /* Returns true if a bignum is zero, false otherwise. */
2231 APInt::tcIsZero(const integerPart *src, unsigned int parts)
2235 for(i = 0; i < parts; i++)
2242 /* Extract the given bit of a bignum; returns 0 or 1. */
2244 APInt::tcExtractBit(const integerPart *parts, unsigned int bit)
2246 return(parts[bit / integerPartWidth]
2247 & ((integerPart) 1 << bit % integerPartWidth)) != 0;
2250 /* Set the given bit of a bignum. */
2252 APInt::tcSetBit(integerPart *parts, unsigned int bit)
2254 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);
2257 /* Returns the bit number of the least significant set bit of a
2258 number. If the input number has no bits set -1U is returned. */
2260 APInt::tcLSB(const integerPart *parts, unsigned int n)
2262 unsigned int i, lsb;
2264 for(i = 0; i < n; i++) {
2265 if (parts[i] != 0) {
2266 lsb = partLSB(parts[i]);
2268 return lsb + i * integerPartWidth;
2275 /* Returns the bit number of the most significant set bit of a number.
2276 If the input number has no bits set -1U is returned. */
2278 APInt::tcMSB(const integerPart *parts, unsigned int n)
2285 if (parts[n] != 0) {
2286 msb = partMSB(parts[n]);
2288 return msb + n * integerPartWidth;
2295 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2296 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2297 the least significant bit of DST. All high bits above srcBITS in
2298 DST are zero-filled. */
2300 APInt::tcExtract(integerPart *dst, unsigned int dstCount, const integerPart *src,
2301 unsigned int srcBits, unsigned int srcLSB)
2303 unsigned int firstSrcPart, dstParts, shift, n;
2305 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;
2306 assert (dstParts <= dstCount);
2308 firstSrcPart = srcLSB / integerPartWidth;
2309 tcAssign (dst, src + firstSrcPart, dstParts);
2311 shift = srcLSB % integerPartWidth;
2312 tcShiftRight (dst, dstParts, shift);
2314 /* We now have (dstParts * integerPartWidth - shift) bits from SRC
2315 in DST. If this is less that srcBits, append the rest, else
2316 clear the high bits. */
2317 n = dstParts * integerPartWidth - shift;
2319 integerPart mask = lowBitMask (srcBits - n);
2320 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2321 << n % integerPartWidth);
2322 } else if (n > srcBits) {
2323 if (srcBits % integerPartWidth)
2324 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);
2327 /* Clear high parts. */
2328 while (dstParts < dstCount)
2329 dst[dstParts++] = 0;
2332 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2334 APInt::tcAdd(integerPart *dst, const integerPart *rhs,
2335 integerPart c, unsigned int parts)
2341 for(i = 0; i < parts; i++) {
2346 dst[i] += rhs[i] + 1;
2357 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2359 APInt::tcSubtract(integerPart *dst, const integerPart *rhs,
2360 integerPart c, unsigned int parts)
2366 for(i = 0; i < parts; i++) {
2371 dst[i] -= rhs[i] + 1;
2382 /* Negate a bignum in-place. */
2384 APInt::tcNegate(integerPart *dst, unsigned int parts)
2386 tcComplement(dst, parts);
2387 tcIncrement(dst, parts);
2390 /* DST += SRC * MULTIPLIER + CARRY if add is true
2391 DST = SRC * MULTIPLIER + CARRY if add is false
2393 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2394 they must start at the same point, i.e. DST == SRC.
2396 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2397 returned. Otherwise DST is filled with the least significant
2398 DSTPARTS parts of the result, and if all of the omitted higher
2399 parts were zero return zero, otherwise overflow occurred and
2402 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,
2403 integerPart multiplier, integerPart carry,
2404 unsigned int srcParts, unsigned int dstParts,
2409 /* Otherwise our writes of DST kill our later reads of SRC. */
2410 assert(dst <= src || dst >= src + srcParts);
2411 assert(dstParts <= srcParts + 1);
2413 /* N loops; minimum of dstParts and srcParts. */
2414 n = dstParts < srcParts ? dstParts: srcParts;
2416 for(i = 0; i < n; i++) {
2417 integerPart low, mid, high, srcPart;
2419 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2421 This cannot overflow, because
2423 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2425 which is less than n^2. */
2429 if (multiplier == 0 || srcPart == 0) {
2433 low = lowHalf(srcPart) * lowHalf(multiplier);
2434 high = highHalf(srcPart) * highHalf(multiplier);
2436 mid = lowHalf(srcPart) * highHalf(multiplier);
2437 high += highHalf(mid);
2438 mid <<= integerPartWidth / 2;
2439 if (low + mid < low)
2443 mid = highHalf(srcPart) * lowHalf(multiplier);
2444 high += highHalf(mid);
2445 mid <<= integerPartWidth / 2;
2446 if (low + mid < low)
2450 /* Now add carry. */
2451 if (low + carry < low)
2457 /* And now DST[i], and store the new low part there. */
2458 if (low + dst[i] < low)
2468 /* Full multiplication, there is no overflow. */
2469 assert(i + 1 == dstParts);
2473 /* We overflowed if there is carry. */
2477 /* We would overflow if any significant unwritten parts would be
2478 non-zero. This is true if any remaining src parts are non-zero
2479 and the multiplier is non-zero. */
2481 for(; i < srcParts; i++)
2485 /* We fitted in the narrow destination. */
2490 /* DST = LHS * RHS, where DST has the same width as the operands and
2491 is filled with the least significant parts of the result. Returns
2492 one if overflow occurred, otherwise zero. DST must be disjoint
2493 from both operands. */
2495 APInt::tcMultiply(integerPart *dst, const integerPart *lhs,
2496 const integerPart *rhs, unsigned int parts)
2501 assert(dst != lhs && dst != rhs);
2504 tcSet(dst, 0, parts);
2506 for(i = 0; i < parts; i++)
2507 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2513 /* DST = LHS * RHS, where DST has width the sum of the widths of the
2514 operands. No overflow occurs. DST must be disjoint from both
2515 operands. Returns the number of parts required to hold the
2518 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,
2519 const integerPart *rhs, unsigned int lhsParts,
2520 unsigned int rhsParts)
2522 /* Put the narrower number on the LHS for less loops below. */
2523 if (lhsParts > rhsParts) {
2524 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2528 assert(dst != lhs && dst != rhs);
2530 tcSet(dst, 0, rhsParts);
2532 for(n = 0; n < lhsParts; n++)
2533 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);
2535 n = lhsParts + rhsParts;
2537 return n - (dst[n - 1] == 0);
2541 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2542 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2543 set REMAINDER to the remainder, return zero. i.e.
2545 OLD_LHS = RHS * LHS + REMAINDER
2547 SCRATCH is a bignum of the same size as the operands and result for
2548 use by the routine; its contents need not be initialized and are
2549 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2552 APInt::tcDivide(integerPart *lhs, const integerPart *rhs,
2553 integerPart *remainder, integerPart *srhs,
2556 unsigned int n, shiftCount;
2559 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2561 shiftCount = tcMSB(rhs, parts) + 1;
2562 if (shiftCount == 0)
2565 shiftCount = parts * integerPartWidth - shiftCount;
2566 n = shiftCount / integerPartWidth;
2567 mask = (integerPart) 1 << (shiftCount % integerPartWidth);
2569 tcAssign(srhs, rhs, parts);
2570 tcShiftLeft(srhs, parts, shiftCount);
2571 tcAssign(remainder, lhs, parts);
2572 tcSet(lhs, 0, parts);
2574 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2579 compare = tcCompare(remainder, srhs, parts);
2581 tcSubtract(remainder, srhs, 0, parts);
2585 if (shiftCount == 0)
2588 tcShiftRight(srhs, parts, 1);
2589 if ((mask >>= 1) == 0)
2590 mask = (integerPart) 1 << (integerPartWidth - 1), n--;
2596 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.
2597 There are no restrictions on COUNT. */
2599 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)
2602 unsigned int jump, shift;
2604 /* Jump is the inter-part jump; shift is is intra-part shift. */
2605 jump = count / integerPartWidth;
2606 shift = count % integerPartWidth;
2608 while (parts > jump) {
2613 /* dst[i] comes from the two parts src[i - jump] and, if we have
2614 an intra-part shift, src[i - jump - 1]. */
2615 part = dst[parts - jump];
2618 if (parts >= jump + 1)
2619 part |= dst[parts - jump - 1] >> (integerPartWidth - shift);
2630 /* Shift a bignum right COUNT bits in-place. Shifted in bits are
2631 zero. There are no restrictions on COUNT. */
2633 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)
2636 unsigned int i, jump, shift;
2638 /* Jump is the inter-part jump; shift is is intra-part shift. */
2639 jump = count / integerPartWidth;
2640 shift = count % integerPartWidth;
2642 /* Perform the shift. This leaves the most significant COUNT bits
2643 of the result at zero. */
2644 for(i = 0; i < parts; i++) {
2647 if (i + jump >= parts) {
2650 part = dst[i + jump];
2653 if (i + jump + 1 < parts)
2654 part |= dst[i + jump + 1] << (integerPartWidth - shift);
2663 /* Bitwise and of two bignums. */
2665 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)
2669 for(i = 0; i < parts; i++)
2673 /* Bitwise inclusive or of two bignums. */
2675 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)
2679 for(i = 0; i < parts; i++)
2683 /* Bitwise exclusive or of two bignums. */
2685 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)
2689 for(i = 0; i < parts; i++)
2693 /* Complement a bignum in-place. */
2695 APInt::tcComplement(integerPart *dst, unsigned int parts)
2699 for(i = 0; i < parts; i++)
2703 /* Comparison (unsigned) of two bignums. */
2705 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,
2710 if (lhs[parts] == rhs[parts])
2713 if (lhs[parts] > rhs[parts])
2722 /* Increment a bignum in-place, return the carry flag. */
2724 APInt::tcIncrement(integerPart *dst, unsigned int parts)
2728 for(i = 0; i < parts; i++)
2735 /* Set the least significant BITS bits of a bignum, clear the
2738 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,
2744 while (bits > integerPartWidth) {
2745 dst[i++] = ~(integerPart) 0;
2746 bits -= integerPartWidth;
2750 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);