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 #include "llvm/ADT/APInt.h"
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/ADT/Hashing.h"
19 #include "llvm/ADT/SmallString.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/ErrorHandling.h"
23 #include "llvm/Support/MathExtras.h"
24 #include "llvm/Support/raw_ostream.h"
31 #define DEBUG_TYPE "apint"
33 /// A utility function for allocating memory, checking for allocation failures,
34 /// and ensuring the contents are zeroed.
35 inline static uint64_t* getClearedMemory(unsigned numWords) {
36 uint64_t * result = new uint64_t[numWords];
37 assert(result && "APInt memory allocation fails!");
38 memset(result, 0, numWords * sizeof(uint64_t));
42 /// A utility function for allocating memory and checking for allocation
43 /// failure. The content is not zeroed.
44 inline static uint64_t* getMemory(unsigned numWords) {
45 uint64_t * result = new uint64_t[numWords];
46 assert(result && "APInt memory allocation fails!");
50 /// A utility function that converts a character to a digit.
51 inline static unsigned getDigit(char cdigit, uint8_t radix) {
54 if (radix == 16 || radix == 36) {
78 void APInt::initSlowCase(uint64_t val, bool isSigned) {
79 U.pVal = getClearedMemory(getNumWords());
81 if (isSigned && int64_t(val) < 0)
82 for (unsigned i = 1; i < getNumWords(); ++i)
87 void APInt::initSlowCase(const APInt& that) {
88 U.pVal = getMemory(getNumWords());
89 memcpy(U.pVal, that.U.pVal, getNumWords() * APINT_WORD_SIZE);
92 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
93 assert(BitWidth && "Bitwidth too small");
94 assert(bigVal.data() && "Null pointer detected!");
98 // Get memory, cleared to 0
99 U.pVal = getClearedMemory(getNumWords());
100 // Calculate the number of words to copy
101 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
102 // Copy the words from bigVal to pVal
103 memcpy(U.pVal, bigVal.data(), words * APINT_WORD_SIZE);
105 // Make sure unused high bits are cleared
109 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
110 : BitWidth(numBits) {
111 initFromArray(bigVal);
114 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
115 : BitWidth(numBits) {
116 initFromArray(makeArrayRef(bigVal, numWords));
119 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
120 : BitWidth(numbits) {
121 assert(BitWidth && "Bitwidth too small");
122 fromString(numbits, Str, radix);
125 void APInt::reallocate(unsigned NewBitWidth) {
126 // If the number of words is the same we can just change the width and stop.
127 if (getNumWords() == getNumWords(NewBitWidth)) {
128 BitWidth = NewBitWidth;
132 // If we have an allocation, delete it.
137 BitWidth = NewBitWidth;
139 // If we are supposed to have an allocation, create it.
141 U.pVal = getMemory(getNumWords());
144 void APInt::AssignSlowCase(const APInt& RHS) {
145 // Don't do anything for X = X
149 // Adjust the bit width and handle allocations as necessary.
150 reallocate(RHS.getBitWidth());
156 memcpy(U.pVal, RHS.U.pVal, getNumWords() * APINT_WORD_SIZE);
159 /// This method 'profiles' an APInt for use with FoldingSet.
160 void APInt::Profile(FoldingSetNodeID& ID) const {
161 ID.AddInteger(BitWidth);
163 if (isSingleWord()) {
164 ID.AddInteger(U.VAL);
168 unsigned NumWords = getNumWords();
169 for (unsigned i = 0; i < NumWords; ++i)
170 ID.AddInteger(U.pVal[i]);
173 /// @brief Prefix increment operator. Increments the APInt by one.
174 APInt& APInt::operator++() {
178 tcIncrement(U.pVal, getNumWords());
179 return clearUnusedBits();
182 /// @brief Prefix decrement operator. Decrements the APInt by one.
183 APInt& APInt::operator--() {
187 tcDecrement(U.pVal, getNumWords());
188 return clearUnusedBits();
191 /// Adds the RHS APint to this APInt.
192 /// @returns this, after addition of RHS.
193 /// @brief Addition assignment operator.
194 APInt& APInt::operator+=(const APInt& RHS) {
195 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
199 tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());
200 return clearUnusedBits();
203 APInt& APInt::operator+=(uint64_t RHS) {
207 tcAddPart(U.pVal, RHS, getNumWords());
208 return clearUnusedBits();
211 /// Subtracts the RHS APInt from this APInt
212 /// @returns this, after subtraction
213 /// @brief Subtraction assignment operator.
214 APInt& APInt::operator-=(const APInt& RHS) {
215 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
219 tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());
220 return clearUnusedBits();
223 APInt& APInt::operator-=(uint64_t RHS) {
227 tcSubtractPart(U.pVal, RHS, getNumWords());
228 return clearUnusedBits();
231 APInt APInt::operator*(const APInt& RHS) const {
232 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
234 return APInt(BitWidth, U.VAL * RHS.U.VAL);
236 APInt Result(getMemory(getNumWords()), getBitWidth());
238 tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());
240 Result.clearUnusedBits();
244 void APInt::AndAssignSlowCase(const APInt& RHS) {
245 tcAnd(U.pVal, RHS.U.pVal, getNumWords());
248 void APInt::OrAssignSlowCase(const APInt& RHS) {
249 tcOr(U.pVal, RHS.U.pVal, getNumWords());
252 void APInt::XorAssignSlowCase(const APInt& RHS) {
253 tcXor(U.pVal, RHS.U.pVal, getNumWords());
256 APInt& APInt::operator*=(const APInt& RHS) {
257 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
262 APInt& APInt::operator*=(uint64_t RHS) {
263 if (isSingleWord()) {
266 unsigned NumWords = getNumWords();
267 tcMultiplyPart(U.pVal, U.pVal, RHS, 0, NumWords, NumWords, false);
269 return clearUnusedBits();
272 bool APInt::EqualSlowCase(const APInt& RHS) const {
273 return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal);
276 int APInt::compare(const APInt& RHS) const {
277 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
279 return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;
281 return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
284 int APInt::compareSigned(const APInt& RHS) const {
285 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
286 if (isSingleWord()) {
287 int64_t lhsSext = SignExtend64(U.VAL, BitWidth);
288 int64_t rhsSext = SignExtend64(RHS.U.VAL, BitWidth);
289 return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
292 bool lhsNeg = isNegative();
293 bool rhsNeg = RHS.isNegative();
295 // If the sign bits don't match, then (LHS < RHS) if LHS is negative
296 if (lhsNeg != rhsNeg)
297 return lhsNeg ? -1 : 1;
299 // Otherwise we can just use an unsigned comparison, because even negative
300 // numbers compare correctly this way if both have the same signed-ness.
301 return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
304 void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
305 unsigned loWord = whichWord(loBit);
306 unsigned hiWord = whichWord(hiBit);
308 // Create an initial mask for the low word with zeros below loBit.
309 uint64_t loMask = WORD_MAX << whichBit(loBit);
311 // If hiBit is not aligned, we need a high mask.
312 unsigned hiShiftAmt = whichBit(hiBit);
313 if (hiShiftAmt != 0) {
314 // Create a high mask with zeros above hiBit.
315 uint64_t hiMask = WORD_MAX >> (APINT_BITS_PER_WORD - hiShiftAmt);
316 // If loWord and hiWord are equal, then we combine the masks. Otherwise,
317 // set the bits in hiWord.
318 if (hiWord == loWord)
321 U.pVal[hiWord] |= hiMask;
323 // Apply the mask to the low word.
324 U.pVal[loWord] |= loMask;
326 // Fill any words between loWord and hiWord with all ones.
327 for (unsigned word = loWord + 1; word < hiWord; ++word)
328 U.pVal[word] = WORD_MAX;
331 /// @brief Toggle every bit to its opposite value.
332 void APInt::flipAllBitsSlowCase() {
333 tcComplement(U.pVal, getNumWords());
337 /// Toggle a given bit to its opposite value whose position is given
338 /// as "bitPosition".
339 /// @brief Toggles a given bit to its opposite value.
340 void APInt::flipBit(unsigned bitPosition) {
341 assert(bitPosition < BitWidth && "Out of the bit-width range!");
342 if ((*this)[bitPosition]) clearBit(bitPosition);
343 else setBit(bitPosition);
346 void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
347 unsigned subBitWidth = subBits.getBitWidth();
348 assert(0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth &&
349 "Illegal bit insertion");
351 // Insertion is a direct copy.
352 if (subBitWidth == BitWidth) {
357 // Single word result can be done as a direct bitmask.
358 if (isSingleWord()) {
359 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
360 U.VAL &= ~(mask << bitPosition);
361 U.VAL |= (subBits.U.VAL << bitPosition);
365 unsigned loBit = whichBit(bitPosition);
366 unsigned loWord = whichWord(bitPosition);
367 unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
369 // Insertion within a single word can be done as a direct bitmask.
370 if (loWord == hi1Word) {
371 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
372 U.pVal[loWord] &= ~(mask << loBit);
373 U.pVal[loWord] |= (subBits.U.VAL << loBit);
377 // Insert on word boundaries.
379 // Direct copy whole words.
380 unsigned numWholeSubWords = subBitWidth / APINT_BITS_PER_WORD;
381 memcpy(U.pVal + loWord, subBits.getRawData(),
382 numWholeSubWords * APINT_WORD_SIZE);
384 // Mask+insert remaining bits.
385 unsigned remainingBits = subBitWidth % APINT_BITS_PER_WORD;
386 if (remainingBits != 0) {
387 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - remainingBits);
388 U.pVal[hi1Word] &= ~mask;
389 U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
394 // General case - set/clear individual bits in dst based on src.
395 // TODO - there is scope for optimization here, but at the moment this code
396 // path is barely used so prefer readability over performance.
397 for (unsigned i = 0; i != subBitWidth; ++i) {
399 setBit(bitPosition + i);
401 clearBit(bitPosition + i);
405 APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {
406 assert(numBits > 0 && "Can't extract zero bits");
407 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
408 "Illegal bit extraction");
411 return APInt(numBits, U.VAL >> bitPosition);
413 unsigned loBit = whichBit(bitPosition);
414 unsigned loWord = whichWord(bitPosition);
415 unsigned hiWord = whichWord(bitPosition + numBits - 1);
417 // Single word result extracting bits from a single word source.
418 if (loWord == hiWord)
419 return APInt(numBits, U.pVal[loWord] >> loBit);
421 // Extracting bits that start on a source word boundary can be done
422 // as a fast memory copy.
424 return APInt(numBits, makeArrayRef(U.pVal + loWord, 1 + hiWord - loWord));
426 // General case - shift + copy source words directly into place.
427 APInt Result(numBits, 0);
428 unsigned NumSrcWords = getNumWords();
429 unsigned NumDstWords = Result.getNumWords();
431 for (unsigned word = 0; word < NumDstWords; ++word) {
432 uint64_t w0 = U.pVal[loWord + word];
434 (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
435 Result.U.pVal[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));
438 return Result.clearUnusedBits();
441 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
442 assert(!str.empty() && "Invalid string length");
443 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
445 "Radix should be 2, 8, 10, 16, or 36!");
447 size_t slen = str.size();
449 // Each computation below needs to know if it's negative.
450 StringRef::iterator p = str.begin();
451 unsigned isNegative = *p == '-';
452 if (*p == '-' || *p == '+') {
455 assert(slen && "String is only a sign, needs a value.");
458 // For radixes of power-of-two values, the bits required is accurately and
461 return slen + isNegative;
463 return slen * 3 + isNegative;
465 return slen * 4 + isNegative;
469 // This is grossly inefficient but accurate. We could probably do something
470 // with a computation of roughly slen*64/20 and then adjust by the value of
471 // the first few digits. But, I'm not sure how accurate that could be.
473 // Compute a sufficient number of bits that is always large enough but might
474 // be too large. This avoids the assertion in the constructor. This
475 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
476 // bits in that case.
478 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
479 : (slen == 1 ? 7 : slen * 16/3);
481 // Convert to the actual binary value.
482 APInt tmp(sufficient, StringRef(p, slen), radix);
484 // Compute how many bits are required. If the log is infinite, assume we need
486 unsigned log = tmp.logBase2();
487 if (log == (unsigned)-1) {
488 return isNegative + 1;
490 return isNegative + log + 1;
494 hash_code llvm::hash_value(const APInt &Arg) {
495 if (Arg.isSingleWord())
496 return hash_combine(Arg.U.VAL);
498 return hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords());
501 bool APInt::isSplat(unsigned SplatSizeInBits) const {
502 assert(getBitWidth() % SplatSizeInBits == 0 &&
503 "SplatSizeInBits must divide width!");
504 // We can check that all parts of an integer are equal by making use of a
505 // little trick: rotate and check if it's still the same value.
506 return *this == rotl(SplatSizeInBits);
509 /// This function returns the high "numBits" bits of this APInt.
510 APInt APInt::getHiBits(unsigned numBits) const {
511 return this->lshr(BitWidth - numBits);
514 /// This function returns the low "numBits" bits of this APInt.
515 APInt APInt::getLoBits(unsigned numBits) const {
516 APInt Result(getLowBitsSet(BitWidth, numBits));
521 /// Return a value containing V broadcasted over NewLen bits.
522 APInt APInt::getSplat(unsigned NewLen, const APInt &V) {
523 assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!");
525 APInt Val = V.zextOrSelf(NewLen);
526 for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1)
532 unsigned APInt::countLeadingZerosSlowCase() const {
534 for (int i = getNumWords()-1; i >= 0; --i) {
535 uint64_t V = U.pVal[i];
537 Count += APINT_BITS_PER_WORD;
539 Count += llvm::countLeadingZeros(V);
543 // Adjust for unused bits in the most significant word (they are zero).
544 unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
545 Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
549 unsigned APInt::countLeadingOnesSlowCase() const {
550 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
553 highWordBits = APINT_BITS_PER_WORD;
556 shift = APINT_BITS_PER_WORD - highWordBits;
558 int i = getNumWords() - 1;
559 unsigned Count = llvm::countLeadingOnes(U.pVal[i] << shift);
560 if (Count == highWordBits) {
561 for (i--; i >= 0; --i) {
562 if (U.pVal[i] == WORD_MAX)
563 Count += APINT_BITS_PER_WORD;
565 Count += llvm::countLeadingOnes(U.pVal[i]);
573 unsigned APInt::countTrailingZerosSlowCase() const {
576 for (; i < getNumWords() && U.pVal[i] == 0; ++i)
577 Count += APINT_BITS_PER_WORD;
578 if (i < getNumWords())
579 Count += llvm::countTrailingZeros(U.pVal[i]);
580 return std::min(Count, BitWidth);
583 unsigned APInt::countTrailingOnesSlowCase() const {
586 for (; i < getNumWords() && U.pVal[i] == WORD_MAX; ++i)
587 Count += APINT_BITS_PER_WORD;
588 if (i < getNumWords())
589 Count += llvm::countTrailingOnes(U.pVal[i]);
590 assert(Count <= BitWidth);
594 unsigned APInt::countPopulationSlowCase() const {
596 for (unsigned i = 0; i < getNumWords(); ++i)
597 Count += llvm::countPopulation(U.pVal[i]);
601 bool APInt::intersectsSlowCase(const APInt &RHS) const {
602 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
603 if ((U.pVal[i] & RHS.U.pVal[i]) != 0)
609 bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
610 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
611 if ((U.pVal[i] & ~RHS.U.pVal[i]) != 0)
617 APInt APInt::byteSwap() const {
618 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
620 return APInt(BitWidth, ByteSwap_16(uint16_t(U.VAL)));
622 return APInt(BitWidth, ByteSwap_32(unsigned(U.VAL)));
623 if (BitWidth == 48) {
624 unsigned Tmp1 = unsigned(U.VAL >> 16);
625 Tmp1 = ByteSwap_32(Tmp1);
626 uint16_t Tmp2 = uint16_t(U.VAL);
627 Tmp2 = ByteSwap_16(Tmp2);
628 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
631 return APInt(BitWidth, ByteSwap_64(U.VAL));
633 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
634 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
635 Result.U.pVal[I] = ByteSwap_64(U.pVal[N - I - 1]);
636 if (Result.BitWidth != BitWidth) {
637 Result.lshrInPlace(Result.BitWidth - BitWidth);
638 Result.BitWidth = BitWidth;
643 APInt APInt::reverseBits() const {
646 return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
648 return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
650 return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
652 return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
658 APInt Reversed(BitWidth, 0);
659 unsigned S = BitWidth;
661 for (; Val != 0; Val.lshrInPlace(1)) {
671 APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {
672 // Fast-path a common case.
673 if (A == B) return A;
675 // Corner cases: if either operand is zero, the other is the gcd.
679 // Count common powers of 2 and remove all other powers of 2.
682 unsigned Pow2_A = A.countTrailingZeros();
683 unsigned Pow2_B = B.countTrailingZeros();
684 if (Pow2_A > Pow2_B) {
685 A.lshrInPlace(Pow2_A - Pow2_B);
687 } else if (Pow2_B > Pow2_A) {
688 B.lshrInPlace(Pow2_B - Pow2_A);
695 // Both operands are odd multiples of 2^Pow_2:
697 // gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))
699 // This is a modified version of Stein's algorithm, taking advantage of
700 // efficient countTrailingZeros().
704 A.lshrInPlace(A.countTrailingZeros() - Pow2);
707 B.lshrInPlace(B.countTrailingZeros() - Pow2);
714 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
721 // Get the sign bit from the highest order bit
722 bool isNeg = T.I >> 63;
724 // Get the 11-bit exponent and adjust for the 1023 bit bias
725 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
727 // If the exponent is negative, the value is < 0 so just return 0.
729 return APInt(width, 0u);
731 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
732 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
734 // If the exponent doesn't shift all bits out of the mantissa
736 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
737 APInt(width, mantissa >> (52 - exp));
739 // If the client didn't provide enough bits for us to shift the mantissa into
740 // then the result is undefined, just return 0
741 if (width <= exp - 52)
742 return APInt(width, 0);
744 // Otherwise, we have to shift the mantissa bits up to the right location
745 APInt Tmp(width, mantissa);
746 Tmp <<= (unsigned)exp - 52;
747 return isNeg ? -Tmp : Tmp;
750 /// This function converts this APInt to a double.
751 /// The layout for double is as following (IEEE Standard 754):
752 /// --------------------------------------
753 /// | Sign Exponent Fraction Bias |
754 /// |-------------------------------------- |
755 /// | 1[63] 11[62-52] 52[51-00] 1023 |
756 /// --------------------------------------
757 double APInt::roundToDouble(bool isSigned) const {
759 // Handle the simple case where the value is contained in one uint64_t.
760 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
761 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
763 int64_t sext = SignExtend64(getWord(0), BitWidth);
766 return double(getWord(0));
769 // Determine if the value is negative.
770 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
772 // Construct the absolute value if we're negative.
773 APInt Tmp(isNeg ? -(*this) : (*this));
775 // Figure out how many bits we're using.
776 unsigned n = Tmp.getActiveBits();
778 // The exponent (without bias normalization) is just the number of bits
779 // we are using. Note that the sign bit is gone since we constructed the
783 // Return infinity for exponent overflow
785 if (!isSigned || !isNeg)
786 return std::numeric_limits<double>::infinity();
788 return -std::numeric_limits<double>::infinity();
790 exp += 1023; // Increment for 1023 bias
792 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
793 // extract the high 52 bits from the correct words in pVal.
795 unsigned hiWord = whichWord(n-1);
797 mantissa = Tmp.U.pVal[0];
799 mantissa >>= n - 52; // shift down, we want the top 52 bits.
801 assert(hiWord > 0 && "huh?");
802 uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
803 uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
804 mantissa = hibits | lobits;
807 // The leading bit of mantissa is implicit, so get rid of it.
808 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
813 T.I = sign | (exp << 52) | mantissa;
817 // Truncate to new width.
818 APInt APInt::trunc(unsigned width) const {
819 assert(width < BitWidth && "Invalid APInt Truncate request");
820 assert(width && "Can't truncate to 0 bits");
822 if (width <= APINT_BITS_PER_WORD)
823 return APInt(width, getRawData()[0]);
825 APInt Result(getMemory(getNumWords(width)), width);
829 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
830 Result.U.pVal[i] = U.pVal[i];
832 // Truncate and copy any partial word.
833 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
835 Result.U.pVal[i] = U.pVal[i] << bits >> bits;
840 // Sign extend to a new width.
841 APInt APInt::sext(unsigned Width) const {
842 assert(Width > BitWidth && "Invalid APInt SignExtend request");
844 if (Width <= APINT_BITS_PER_WORD)
845 return APInt(Width, SignExtend64(U.VAL, BitWidth));
847 APInt Result(getMemory(getNumWords(Width)), Width);
850 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
852 // Sign extend the last word since there may be unused bits in the input.
853 Result.U.pVal[getNumWords() - 1] =
854 SignExtend64(Result.U.pVal[getNumWords() - 1],
855 ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
857 // Fill with sign bits.
858 std::memset(Result.U.pVal + getNumWords(), isNegative() ? -1 : 0,
859 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
860 Result.clearUnusedBits();
864 // Zero extend to a new width.
865 APInt APInt::zext(unsigned width) const {
866 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
868 if (width <= APINT_BITS_PER_WORD)
869 return APInt(width, U.VAL);
871 APInt Result(getMemory(getNumWords(width)), width);
874 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
876 // Zero remaining words.
877 std::memset(Result.U.pVal + getNumWords(), 0,
878 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
883 APInt APInt::zextOrTrunc(unsigned width) const {
884 if (BitWidth < width)
886 if (BitWidth > width)
891 APInt APInt::sextOrTrunc(unsigned width) const {
892 if (BitWidth < width)
894 if (BitWidth > width)
899 APInt APInt::zextOrSelf(unsigned width) const {
900 if (BitWidth < width)
905 APInt APInt::sextOrSelf(unsigned width) const {
906 if (BitWidth < width)
911 /// Arithmetic right-shift this APInt by shiftAmt.
912 /// @brief Arithmetic right-shift function.
913 void APInt::ashrInPlace(const APInt &shiftAmt) {
914 ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
917 /// Arithmetic right-shift this APInt by shiftAmt.
918 /// @brief Arithmetic right-shift function.
919 void APInt::ashrSlowCase(unsigned ShiftAmt) {
920 // Don't bother performing a no-op shift.
924 // Save the original sign bit for later.
925 bool Negative = isNegative();
927 // WordShift is the inter-part shift; BitShift is is intra-part shift.
928 unsigned WordShift = ShiftAmt / APINT_BITS_PER_WORD;
929 unsigned BitShift = ShiftAmt % APINT_BITS_PER_WORD;
931 unsigned WordsToMove = getNumWords() - WordShift;
932 if (WordsToMove != 0) {
933 // Sign extend the last word to fill in the unused bits.
934 U.pVal[getNumWords() - 1] = SignExtend64(
935 U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
937 // Fastpath for moving by whole words.
939 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
941 // Move the words containing significant bits.
942 for (unsigned i = 0; i != WordsToMove - 1; ++i)
943 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
944 (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));
946 // Handle the last word which has no high bits to copy.
947 U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
948 // Sign extend one more time.
949 U.pVal[WordsToMove - 1] =
950 SignExtend64(U.pVal[WordsToMove - 1], APINT_BITS_PER_WORD - BitShift);
954 // Fill in the remainder based on the original sign.
955 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
956 WordShift * APINT_WORD_SIZE);
960 /// Logical right-shift this APInt by shiftAmt.
961 /// @brief Logical right-shift function.
962 void APInt::lshrInPlace(const APInt &shiftAmt) {
963 lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
966 /// Logical right-shift this APInt by shiftAmt.
967 /// @brief Logical right-shift function.
968 void APInt::lshrSlowCase(unsigned ShiftAmt) {
969 tcShiftRight(U.pVal, getNumWords(), ShiftAmt);
972 /// Left-shift this APInt by shiftAmt.
973 /// @brief Left-shift function.
974 APInt &APInt::operator<<=(const APInt &shiftAmt) {
975 // It's undefined behavior in C to shift by BitWidth or greater.
976 *this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);
980 void APInt::shlSlowCase(unsigned ShiftAmt) {
981 tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);
985 // Calculate the rotate amount modulo the bit width.
986 static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
987 unsigned rotBitWidth = rotateAmt.getBitWidth();
988 APInt rot = rotateAmt;
989 if (rotBitWidth < BitWidth) {
990 // Extend the rotate APInt, so that the urem doesn't divide by 0.
991 // e.g. APInt(1, 32) would give APInt(1, 0).
992 rot = rotateAmt.zext(BitWidth);
994 rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
995 return rot.getLimitedValue(BitWidth);
998 APInt APInt::rotl(const APInt &rotateAmt) const {
999 return rotl(rotateModulo(BitWidth, rotateAmt));
1002 APInt APInt::rotl(unsigned rotateAmt) const {
1003 rotateAmt %= BitWidth;
1006 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1009 APInt APInt::rotr(const APInt &rotateAmt) const {
1010 return rotr(rotateModulo(BitWidth, rotateAmt));
1013 APInt APInt::rotr(unsigned rotateAmt) const {
1014 rotateAmt %= BitWidth;
1017 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1020 // Square Root - this method computes and returns the square root of "this".
1021 // Three mechanisms are used for computation. For small values (<= 5 bits),
1022 // a table lookup is done. This gets some performance for common cases. For
1023 // values using less than 52 bits, the value is converted to double and then
1024 // the libc sqrt function is called. The result is rounded and then converted
1025 // back to a uint64_t which is then used to construct the result. Finally,
1026 // the Babylonian method for computing square roots is used.
1027 APInt APInt::sqrt() const {
1029 // Determine the magnitude of the value.
1030 unsigned magnitude = getActiveBits();
1032 // Use a fast table for some small values. This also gets rid of some
1033 // rounding errors in libc sqrt for small values.
1034 if (magnitude <= 5) {
1035 static const uint8_t results[32] = {
1038 /* 3- 6 */ 2, 2, 2, 2,
1039 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1040 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1041 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1044 return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
1047 // If the magnitude of the value fits in less than 52 bits (the precision of
1048 // an IEEE double precision floating point value), then we can use the
1049 // libc sqrt function which will probably use a hardware sqrt computation.
1050 // This should be faster than the algorithm below.
1051 if (magnitude < 52) {
1052 return APInt(BitWidth,
1053 uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL
1057 // Okay, all the short cuts are exhausted. We must compute it. The following
1058 // is a classical Babylonian method for computing the square root. This code
1059 // was adapted to APInt from a wikipedia article on such computations.
1060 // See http://www.wikipedia.org/ and go to the page named
1061 // Calculate_an_integer_square_root.
1062 unsigned nbits = BitWidth, i = 4;
1063 APInt testy(BitWidth, 16);
1064 APInt x_old(BitWidth, 1);
1065 APInt x_new(BitWidth, 0);
1066 APInt two(BitWidth, 2);
1068 // Select a good starting value using binary logarithms.
1069 for (;; i += 2, testy = testy.shl(2))
1070 if (i >= nbits || this->ule(testy)) {
1071 x_old = x_old.shl(i / 2);
1075 // Use the Babylonian method to arrive at the integer square root:
1077 x_new = (this->udiv(x_old) + x_old).udiv(two);
1078 if (x_old.ule(x_new))
1083 // Make sure we return the closest approximation
1084 // NOTE: The rounding calculation below is correct. It will produce an
1085 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1086 // determined to be a rounding issue with pari/gp as it begins to use a
1087 // floating point representation after 192 bits. There are no discrepancies
1088 // between this algorithm and pari/gp for bit widths < 192 bits.
1089 APInt square(x_old * x_old);
1090 APInt nextSquare((x_old + 1) * (x_old +1));
1091 if (this->ult(square))
1093 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1094 APInt midpoint((nextSquare - square).udiv(two));
1095 APInt offset(*this - square);
1096 if (offset.ult(midpoint))
1101 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1102 /// iterative extended Euclidean algorithm is used to solve for this value,
1103 /// however we simplify it to speed up calculating only the inverse, and take
1104 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1105 /// (potentially large) APInts around.
1106 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1107 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1109 // Using the properties listed at the following web page (accessed 06/21/08):
1110 // http://www.numbertheory.org/php/euclid.html
1111 // (especially the properties numbered 3, 4 and 9) it can be proved that
1112 // BitWidth bits suffice for all the computations in the algorithm implemented
1113 // below. More precisely, this number of bits suffice if the multiplicative
1114 // inverse exists, but may not suffice for the general extended Euclidean
1117 APInt r[2] = { modulo, *this };
1118 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1119 APInt q(BitWidth, 0);
1122 for (i = 0; r[i^1] != 0; i ^= 1) {
1123 // An overview of the math without the confusing bit-flipping:
1124 // q = r[i-2] / r[i-1]
1125 // r[i] = r[i-2] % r[i-1]
1126 // t[i] = t[i-2] - t[i-1] * q
1127 udivrem(r[i], r[i^1], q, r[i]);
1131 // If this APInt and the modulo are not coprime, there is no multiplicative
1132 // inverse, so return 0. We check this by looking at the next-to-last
1133 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1136 return APInt(BitWidth, 0);
1138 // The next-to-last t is the multiplicative inverse. However, we are
1139 // interested in a positive inverse. Calculate a positive one from a negative
1140 // one if necessary. A simple addition of the modulo suffices because
1141 // abs(t[i]) is known to be less than *this/2 (see the link above).
1142 if (t[i].isNegative())
1145 return std::move(t[i]);
1148 /// Calculate the magic numbers required to implement a signed integer division
1149 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1150 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1151 /// Warren, Jr., chapter 10.
1152 APInt::ms APInt::magic() const {
1153 const APInt& d = *this;
1155 APInt ad, anc, delta, q1, r1, q2, r2, t;
1156 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1160 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1161 anc = t - 1 - t.urem(ad); // absolute value of nc
1162 p = d.getBitWidth() - 1; // initialize p
1163 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1164 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1165 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1166 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1169 q1 = q1<<1; // update q1 = 2p/abs(nc)
1170 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1171 if (r1.uge(anc)) { // must be unsigned comparison
1175 q2 = q2<<1; // update q2 = 2p/abs(d)
1176 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1177 if (r2.uge(ad)) { // must be unsigned comparison
1182 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1185 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1186 mag.s = p - d.getBitWidth(); // resulting shift
1190 /// Calculate the magic numbers required to implement an unsigned integer
1191 /// division by a constant as a sequence of multiplies, adds and shifts.
1192 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1193 /// S. Warren, Jr., chapter 10.
1194 /// LeadingZeros can be used to simplify the calculation if the upper bits
1195 /// of the divided value are known zero.
1196 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1197 const APInt& d = *this;
1199 APInt nc, delta, q1, r1, q2, r2;
1201 magu.a = 0; // initialize "add" indicator
1202 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1203 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1204 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1206 nc = allOnes - (allOnes - d).urem(d);
1207 p = d.getBitWidth() - 1; // initialize p
1208 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1209 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1210 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1211 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1214 if (r1.uge(nc - r1)) {
1215 q1 = q1 + q1 + 1; // update q1
1216 r1 = r1 + r1 - nc; // update r1
1219 q1 = q1+q1; // update q1
1220 r1 = r1+r1; // update r1
1222 if ((r2 + 1).uge(d - r2)) {
1223 if (q2.uge(signedMax)) magu.a = 1;
1224 q2 = q2+q2 + 1; // update q2
1225 r2 = r2+r2 + 1 - d; // update r2
1228 if (q2.uge(signedMin)) magu.a = 1;
1229 q2 = q2+q2; // update q2
1230 r2 = r2+r2 + 1; // update r2
1233 } while (p < d.getBitWidth()*2 &&
1234 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1235 magu.m = q2 + 1; // resulting magic number
1236 magu.s = p - d.getBitWidth(); // resulting shift
1240 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1241 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1242 /// variables here have the same names as in the algorithm. Comments explain
1243 /// the algorithm and any deviation from it.
1244 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1245 unsigned m, unsigned n) {
1246 assert(u && "Must provide dividend");
1247 assert(v && "Must provide divisor");
1248 assert(q && "Must provide quotient");
1249 assert(u != v && u != q && v != q && "Must use different memory");
1250 assert(n>1 && "n must be > 1");
1252 // b denotes the base of the number system. In our case b is 2^32.
1253 const uint64_t b = uint64_t(1) << 32;
1255 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1256 DEBUG(dbgs() << "KnuthDiv: original:");
1257 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1258 DEBUG(dbgs() << " by");
1259 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1260 DEBUG(dbgs() << '\n');
1261 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1262 // u and v by d. Note that we have taken Knuth's advice here to use a power
1263 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1264 // 2 allows us to shift instead of multiply and it is easy to determine the
1265 // shift amount from the leading zeros. We are basically normalizing the u
1266 // and v so that its high bits are shifted to the top of v's range without
1267 // overflow. Note that this can require an extra word in u so that u must
1268 // be of length m+n+1.
1269 unsigned shift = countLeadingZeros(v[n-1]);
1270 uint32_t v_carry = 0;
1271 uint32_t u_carry = 0;
1273 for (unsigned i = 0; i < m+n; ++i) {
1274 uint32_t u_tmp = u[i] >> (32 - shift);
1275 u[i] = (u[i] << shift) | u_carry;
1278 for (unsigned i = 0; i < n; ++i) {
1279 uint32_t v_tmp = v[i] >> (32 - shift);
1280 v[i] = (v[i] << shift) | v_carry;
1286 DEBUG(dbgs() << "KnuthDiv: normal:");
1287 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1288 DEBUG(dbgs() << " by");
1289 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1290 DEBUG(dbgs() << '\n');
1292 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1295 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1296 // D3. [Calculate q'.].
1297 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1298 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1299 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1300 // qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test
1301 // on v[n-2] determines at high speed most of the cases in which the trial
1302 // value qp is one too large, and it eliminates all cases where qp is two
1304 uint64_t dividend = Make_64(u[j+n], u[j+n-1]);
1305 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1306 uint64_t qp = dividend / v[n-1];
1307 uint64_t rp = dividend % v[n-1];
1308 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1311 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1314 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1316 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1317 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1318 // consists of a simple multiplication by a one-place number, combined with
1320 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1321 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1322 // true value plus b**(n+1), namely as the b's complement of
1323 // the true value, and a "borrow" to the left should be remembered.
1325 for (unsigned i = 0; i < n; ++i) {
1326 uint64_t p = uint64_t(qp) * uint64_t(v[i]);
1327 int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
1328 u[j+i] = Lo_32(subres);
1329 borrow = Hi_32(p) - Hi_32(subres);
1330 DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]
1331 << ", borrow = " << borrow << '\n');
1333 bool isNeg = u[j+n] < borrow;
1334 u[j+n] -= Lo_32(borrow);
1336 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1337 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1338 DEBUG(dbgs() << '\n');
1340 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1341 // negative, go to step D6; otherwise go on to step D7.
1344 // D6. [Add back]. The probability that this step is necessary is very
1345 // small, on the order of only 2/b. Make sure that test data accounts for
1346 // this possibility. Decrease q[j] by 1
1348 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1349 // A carry will occur to the left of u[j+n], and it should be ignored
1350 // since it cancels with the borrow that occurred in D4.
1352 for (unsigned i = 0; i < n; i++) {
1353 uint32_t limit = std::min(u[j+i],v[i]);
1354 u[j+i] += v[i] + carry;
1355 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1359 DEBUG(dbgs() << "KnuthDiv: after correction:");
1360 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1361 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1363 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1366 DEBUG(dbgs() << "KnuthDiv: quotient:");
1367 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1368 DEBUG(dbgs() << '\n');
1370 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1371 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1372 // compute the remainder (urem uses this).
1374 // The value d is expressed by the "shift" value above since we avoided
1375 // multiplication by d by using a shift left. So, all we have to do is
1376 // shift right here.
1379 DEBUG(dbgs() << "KnuthDiv: remainder:");
1380 for (int i = n-1; i >= 0; i--) {
1381 r[i] = (u[i] >> shift) | carry;
1382 carry = u[i] << (32 - shift);
1383 DEBUG(dbgs() << " " << r[i]);
1386 for (int i = n-1; i >= 0; i--) {
1388 DEBUG(dbgs() << " " << r[i]);
1391 DEBUG(dbgs() << '\n');
1393 DEBUG(dbgs() << '\n');
1396 void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
1397 unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
1398 assert(lhsWords >= rhsWords && "Fractional result");
1400 // First, compose the values into an array of 32-bit words instead of
1401 // 64-bit words. This is a necessity of both the "short division" algorithm
1402 // and the Knuth "classical algorithm" which requires there to be native
1403 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1404 // can't use 64-bit operands here because we don't have native results of
1405 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1406 // work on large-endian machines.
1407 unsigned n = rhsWords * 2;
1408 unsigned m = (lhsWords * 2) - n;
1410 // Allocate space for the temporary values we need either on the stack, if
1411 // it will fit, or on the heap if it won't.
1412 uint32_t SPACE[128];
1413 uint32_t *U = nullptr;
1414 uint32_t *V = nullptr;
1415 uint32_t *Q = nullptr;
1416 uint32_t *R = nullptr;
1417 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1420 Q = &SPACE[(m+n+1) + n];
1422 R = &SPACE[(m+n+1) + n + (m+n)];
1424 U = new uint32_t[m + n + 1];
1425 V = new uint32_t[n];
1426 Q = new uint32_t[m+n];
1428 R = new uint32_t[n];
1431 // Initialize the dividend
1432 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1433 for (unsigned i = 0; i < lhsWords; ++i) {
1434 uint64_t tmp = LHS[i];
1435 U[i * 2] = Lo_32(tmp);
1436 U[i * 2 + 1] = Hi_32(tmp);
1438 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1440 // Initialize the divisor
1441 memset(V, 0, (n)*sizeof(uint32_t));
1442 for (unsigned i = 0; i < rhsWords; ++i) {
1443 uint64_t tmp = RHS[i];
1444 V[i * 2] = Lo_32(tmp);
1445 V[i * 2 + 1] = Hi_32(tmp);
1448 // initialize the quotient and remainder
1449 memset(Q, 0, (m+n) * sizeof(uint32_t));
1451 memset(R, 0, n * sizeof(uint32_t));
1453 // Now, adjust m and n for the Knuth division. n is the number of words in
1454 // the divisor. m is the number of words by which the dividend exceeds the
1455 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1456 // contain any zero words or the Knuth algorithm fails.
1457 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1461 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1464 // If we're left with only a single word for the divisor, Knuth doesn't work
1465 // so we implement the short division algorithm here. This is much simpler
1466 // and faster because we are certain that we can divide a 64-bit quantity
1467 // by a 32-bit quantity at hardware speed and short division is simply a
1468 // series of such operations. This is just like doing short division but we
1469 // are using base 2^32 instead of base 10.
1470 assert(n != 0 && "Divide by zero?");
1472 uint32_t divisor = V[0];
1473 uint32_t remainder = 0;
1474 for (int i = m; i >= 0; i--) {
1475 uint64_t partial_dividend = Make_64(remainder, U[i]);
1476 if (partial_dividend == 0) {
1479 } else if (partial_dividend < divisor) {
1481 remainder = Lo_32(partial_dividend);
1482 } else if (partial_dividend == divisor) {
1486 Q[i] = Lo_32(partial_dividend / divisor);
1487 remainder = Lo_32(partial_dividend - (Q[i] * divisor));
1493 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1495 KnuthDiv(U, V, Q, R, m, n);
1498 // If the caller wants the quotient
1500 for (unsigned i = 0; i < lhsWords; ++i)
1501 Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
1504 // If the caller wants the remainder
1506 for (unsigned i = 0; i < rhsWords; ++i)
1507 Remainder[i] = Make_64(R[i*2+1], R[i*2]);
1510 // Clean up the memory we allocated.
1511 if (U != &SPACE[0]) {
1519 APInt APInt::udiv(const APInt &RHS) const {
1520 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1522 // First, deal with the easy case
1523 if (isSingleWord()) {
1524 assert(RHS.U.VAL != 0 && "Divide by zero?");
1525 return APInt(BitWidth, U.VAL / RHS.U.VAL);
1528 // Get some facts about the LHS and RHS number of bits and words
1529 unsigned lhsWords = getNumWords(getActiveBits());
1530 unsigned rhsBits = RHS.getActiveBits();
1531 unsigned rhsWords = getNumWords(rhsBits);
1532 assert(rhsWords && "Divided by zero???");
1534 // Deal with some degenerate cases
1537 return APInt(BitWidth, 0);
1541 if (lhsWords < rhsWords || this->ult(RHS))
1542 // X / Y ===> 0, iff X < Y
1543 return APInt(BitWidth, 0);
1546 return APInt(BitWidth, 1);
1547 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
1548 // All high words are zero, just use native divide
1549 return APInt(BitWidth, this->U.pVal[0] / RHS.U.pVal[0]);
1551 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1552 APInt Quotient(BitWidth, 0); // to hold result.
1553 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal, nullptr);
1557 APInt APInt::udiv(uint64_t RHS) const {
1558 assert(RHS != 0 && "Divide by zero?");
1560 // First, deal with the easy case
1562 return APInt(BitWidth, U.VAL / RHS);
1564 // Get some facts about the LHS words.
1565 unsigned lhsWords = getNumWords(getActiveBits());
1567 // Deal with some degenerate cases
1570 return APInt(BitWidth, 0);
1575 // X / Y ===> 0, iff X < Y
1576 return APInt(BitWidth, 0);
1579 return APInt(BitWidth, 1);
1580 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
1581 // All high words are zero, just use native divide
1582 return APInt(BitWidth, this->U.pVal[0] / RHS);
1584 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1585 APInt Quotient(BitWidth, 0); // to hold result.
1586 divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, nullptr);
1590 APInt APInt::sdiv(const APInt &RHS) const {
1592 if (RHS.isNegative())
1593 return (-(*this)).udiv(-RHS);
1594 return -((-(*this)).udiv(RHS));
1596 if (RHS.isNegative())
1597 return -(this->udiv(-RHS));
1598 return this->udiv(RHS);
1601 APInt APInt::sdiv(int64_t RHS) const {
1604 return (-(*this)).udiv(-RHS);
1605 return -((-(*this)).udiv(RHS));
1608 return -(this->udiv(-RHS));
1609 return this->udiv(RHS);
1612 APInt APInt::urem(const APInt &RHS) const {
1613 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1614 if (isSingleWord()) {
1615 assert(RHS.U.VAL != 0 && "Remainder by zero?");
1616 return APInt(BitWidth, U.VAL % RHS.U.VAL);
1619 // Get some facts about the LHS
1620 unsigned lhsWords = getNumWords(getActiveBits());
1622 // Get some facts about the RHS
1623 unsigned rhsBits = RHS.getActiveBits();
1624 unsigned rhsWords = getNumWords(rhsBits);
1625 assert(rhsWords && "Performing remainder operation by zero ???");
1627 // Check the degenerate cases
1630 return APInt(BitWidth, 0);
1633 return APInt(BitWidth, 0);
1634 if (lhsWords < rhsWords || this->ult(RHS))
1635 // X % Y ===> X, iff X < Y
1639 return APInt(BitWidth, 0);
1641 // All high words are zero, just use native remainder
1642 return APInt(BitWidth, U.pVal[0] % RHS.U.pVal[0]);
1644 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1645 APInt Remainder(BitWidth, 0);
1646 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, nullptr, Remainder.U.pVal);
1650 uint64_t APInt::urem(uint64_t RHS) const {
1651 assert(RHS != 0 && "Remainder by zero?");
1656 // Get some facts about the LHS
1657 unsigned lhsWords = getNumWords(getActiveBits());
1659 // Check the degenerate cases
1667 // X % Y ===> X, iff X < Y
1668 return getZExtValue();
1673 // All high words are zero, just use native remainder
1674 return U.pVal[0] % RHS;
1676 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1678 divide(U.pVal, lhsWords, &RHS, 1, nullptr, &Remainder);
1682 APInt APInt::srem(const APInt &RHS) const {
1684 if (RHS.isNegative())
1685 return -((-(*this)).urem(-RHS));
1686 return -((-(*this)).urem(RHS));
1688 if (RHS.isNegative())
1689 return this->urem(-RHS);
1690 return this->urem(RHS);
1693 int64_t APInt::srem(int64_t RHS) const {
1696 return -((-(*this)).urem(-RHS));
1697 return -((-(*this)).urem(RHS));
1700 return this->urem(-RHS);
1701 return this->urem(RHS);
1704 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1705 APInt &Quotient, APInt &Remainder) {
1706 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
1707 unsigned BitWidth = LHS.BitWidth;
1709 // First, deal with the easy case
1710 if (LHS.isSingleWord()) {
1711 assert(RHS.U.VAL != 0 && "Divide by zero?");
1712 uint64_t QuotVal = LHS.U.VAL / RHS.U.VAL;
1713 uint64_t RemVal = LHS.U.VAL % RHS.U.VAL;
1714 Quotient = APInt(BitWidth, QuotVal);
1715 Remainder = APInt(BitWidth, RemVal);
1719 // Get some size facts about the dividend and divisor
1720 unsigned lhsWords = getNumWords(LHS.getActiveBits());
1721 unsigned rhsBits = RHS.getActiveBits();
1722 unsigned rhsWords = getNumWords(rhsBits);
1723 assert(rhsWords && "Performing divrem operation by zero ???");
1725 // Check the degenerate cases
1726 if (lhsWords == 0) {
1727 Quotient = 0; // 0 / Y ===> 0
1728 Remainder = 0; // 0 % Y ===> 0
1733 Quotient = LHS; // X / 1 ===> X
1734 Remainder = 0; // X % 1 ===> 0
1737 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1738 Remainder = LHS; // X % Y ===> X, iff X < Y
1739 Quotient = 0; // X / Y ===> 0, iff X < Y
1744 Quotient = 1; // X / X ===> 1
1745 Remainder = 0; // X % X ===> 0;
1749 // Make sure there is enough space to hold the results.
1750 // NOTE: This assumes that reallocate won't affect any bits if it doesn't
1751 // change the size. This is necessary if Quotient or Remainder is aliased
1753 Quotient.reallocate(BitWidth);
1754 Remainder.reallocate(BitWidth);
1756 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
1757 // There is only one word to consider so use the native versions.
1758 uint64_t lhsValue = LHS.U.pVal[0];
1759 uint64_t rhsValue = RHS.U.pVal[0];
1760 Quotient = lhsValue / rhsValue;
1761 Remainder = lhsValue % rhsValue;
1765 // Okay, lets do it the long way
1766 divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,
1768 // Clear the rest of the Quotient and Remainder.
1769 std::memset(Quotient.U.pVal + lhsWords, 0,
1770 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
1771 std::memset(Remainder.U.pVal + rhsWords, 0,
1772 (getNumWords(BitWidth) - rhsWords) * APINT_WORD_SIZE);
1775 void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
1776 uint64_t &Remainder) {
1777 assert(RHS != 0 && "Divide by zero?");
1778 unsigned BitWidth = LHS.BitWidth;
1780 // First, deal with the easy case
1781 if (LHS.isSingleWord()) {
1782 uint64_t QuotVal = LHS.U.VAL / RHS;
1783 Remainder = LHS.U.VAL % RHS;
1784 Quotient = APInt(BitWidth, QuotVal);
1788 // Get some size facts about the dividend and divisor
1789 unsigned lhsWords = getNumWords(LHS.getActiveBits());
1791 // Check the degenerate cases
1792 if (lhsWords == 0) {
1793 Quotient = 0; // 0 / Y ===> 0
1794 Remainder = 0; // 0 % Y ===> 0
1799 Quotient = LHS; // X / 1 ===> X
1800 Remainder = 0; // X % 1 ===> 0
1804 Remainder = LHS.getZExtValue(); // X % Y ===> X, iff X < Y
1805 Quotient = 0; // X / Y ===> 0, iff X < Y
1810 Quotient = 1; // X / X ===> 1
1811 Remainder = 0; // X % X ===> 0;
1815 // Make sure there is enough space to hold the results.
1816 // NOTE: This assumes that reallocate won't affect any bits if it doesn't
1817 // change the size. This is necessary if Quotient is aliased with LHS.
1818 Quotient.reallocate(BitWidth);
1820 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
1821 // There is only one word to consider so use the native versions.
1822 uint64_t lhsValue = LHS.U.pVal[0];
1823 Quotient = lhsValue / RHS;
1824 Remainder = lhsValue % RHS;
1828 // Okay, lets do it the long way
1829 divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
1830 // Clear the rest of the Quotient.
1831 std::memset(Quotient.U.pVal + lhsWords, 0,
1832 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
1835 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
1836 APInt &Quotient, APInt &Remainder) {
1837 if (LHS.isNegative()) {
1838 if (RHS.isNegative())
1839 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
1841 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
1845 } else if (RHS.isNegative()) {
1846 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
1849 APInt::udivrem(LHS, RHS, Quotient, Remainder);
1853 void APInt::sdivrem(const APInt &LHS, int64_t RHS,
1854 APInt &Quotient, int64_t &Remainder) {
1855 uint64_t R = Remainder;
1856 if (LHS.isNegative()) {
1858 APInt::udivrem(-LHS, -RHS, Quotient, R);
1860 APInt::udivrem(-LHS, RHS, Quotient, R);
1864 } else if (RHS < 0) {
1865 APInt::udivrem(LHS, -RHS, Quotient, R);
1868 APInt::udivrem(LHS, RHS, Quotient, R);
1873 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
1874 APInt Res = *this+RHS;
1875 Overflow = isNonNegative() == RHS.isNonNegative() &&
1876 Res.isNonNegative() != isNonNegative();
1880 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
1881 APInt Res = *this+RHS;
1882 Overflow = Res.ult(RHS);
1886 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
1887 APInt Res = *this - RHS;
1888 Overflow = isNonNegative() != RHS.isNonNegative() &&
1889 Res.isNonNegative() != isNonNegative();
1893 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
1894 APInt Res = *this-RHS;
1895 Overflow = Res.ugt(*this);
1899 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
1900 // MININT/-1 --> overflow.
1901 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
1905 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
1906 APInt Res = *this * RHS;
1908 if (*this != 0 && RHS != 0)
1909 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
1915 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
1916 APInt Res = *this * RHS;
1918 if (*this != 0 && RHS != 0)
1919 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
1925 APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
1926 Overflow = ShAmt.uge(getBitWidth());
1928 return APInt(BitWidth, 0);
1930 if (isNonNegative()) // Don't allow sign change.
1931 Overflow = ShAmt.uge(countLeadingZeros());
1933 Overflow = ShAmt.uge(countLeadingOnes());
1935 return *this << ShAmt;
1938 APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
1939 Overflow = ShAmt.uge(getBitWidth());
1941 return APInt(BitWidth, 0);
1943 Overflow = ShAmt.ugt(countLeadingZeros());
1945 return *this << ShAmt;
1951 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
1952 // Check our assumptions here
1953 assert(!str.empty() && "Invalid string length");
1954 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
1956 "Radix should be 2, 8, 10, 16, or 36!");
1958 StringRef::iterator p = str.begin();
1959 size_t slen = str.size();
1960 bool isNeg = *p == '-';
1961 if (*p == '-' || *p == '+') {
1964 assert(slen && "String is only a sign, needs a value.");
1966 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
1967 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
1968 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
1969 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
1970 "Insufficient bit width");
1972 // Allocate memory if needed
1976 U.pVal = getClearedMemory(getNumWords());
1978 // Figure out if we can shift instead of multiply
1979 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1981 // Enter digit traversal loop
1982 for (StringRef::iterator e = str.end(); p != e; ++p) {
1983 unsigned digit = getDigit(*p, radix);
1984 assert(digit < radix && "Invalid character in digit string");
1986 // Shift or multiply the value by the radix
1994 // Add in the digit we just interpreted
1997 // If its negative, put it in two's complement form
2002 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2003 bool Signed, bool formatAsCLiteral) const {
2004 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2006 "Radix should be 2, 8, 10, 16, or 36!");
2008 const char *Prefix = "";
2009 if (formatAsCLiteral) {
2012 // Binary literals are a non-standard extension added in gcc 4.3:
2013 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2025 llvm_unreachable("Invalid radix!");
2029 // First, check for a zero value and just short circuit the logic below.
2032 Str.push_back(*Prefix);
2039 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2041 if (isSingleWord()) {
2043 char *BufPtr = std::end(Buffer);
2049 int64_t I = getSExtValue();
2059 Str.push_back(*Prefix);
2064 *--BufPtr = Digits[N % Radix];
2067 Str.append(BufPtr, std::end(Buffer));
2073 if (Signed && isNegative()) {
2074 // They want to print the signed version and it is a negative value
2075 // Flip the bits and add one to turn it into the equivalent positive
2076 // value and put a '-' in the result.
2082 Str.push_back(*Prefix);
2086 // We insert the digits backward, then reverse them to get the right order.
2087 unsigned StartDig = Str.size();
2089 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2090 // because the number of bits per digit (1, 3 and 4 respectively) divides
2091 // equally. We just shift until the value is zero.
2092 if (Radix == 2 || Radix == 8 || Radix == 16) {
2093 // Just shift tmp right for each digit width until it becomes zero
2094 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2095 unsigned MaskAmt = Radix - 1;
2097 while (Tmp.getBoolValue()) {
2098 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2099 Str.push_back(Digits[Digit]);
2100 Tmp.lshrInPlace(ShiftAmt);
2103 while (Tmp.getBoolValue()) {
2105 udivrem(Tmp, Radix, Tmp, Digit);
2106 assert(Digit < Radix && "divide failed");
2107 Str.push_back(Digits[Digit]);
2111 // Reverse the digits before returning.
2112 std::reverse(Str.begin()+StartDig, Str.end());
2115 /// Returns the APInt as a std::string. Note that this is an inefficient method.
2116 /// It is better to pass in a SmallVector/SmallString to the methods above.
2117 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2119 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2123 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2124 LLVM_DUMP_METHOD void APInt::dump() const {
2125 SmallString<40> S, U;
2126 this->toStringUnsigned(U);
2127 this->toStringSigned(S);
2128 dbgs() << "APInt(" << BitWidth << "b, "
2129 << U << "u " << S << "s)\n";
2133 void APInt::print(raw_ostream &OS, bool isSigned) const {
2135 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2139 // This implements a variety of operations on a representation of
2140 // arbitrary precision, two's-complement, bignum integer values.
2142 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2143 // and unrestricting assumption.
2144 static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,
2145 "Part width must be divisible by 2!");
2147 /* Some handy functions local to this file. */
2149 /* Returns the integer part with the least significant BITS set.
2150 BITS cannot be zero. */
2151 static inline APInt::WordType lowBitMask(unsigned bits) {
2152 assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD);
2154 return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
2157 /* Returns the value of the lower half of PART. */
2158 static inline APInt::WordType lowHalf(APInt::WordType part) {
2159 return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
2162 /* Returns the value of the upper half of PART. */
2163 static inline APInt::WordType highHalf(APInt::WordType part) {
2164 return part >> (APInt::APINT_BITS_PER_WORD / 2);
2167 /* Returns the bit number of the most significant set bit of a part.
2168 If the input number has no bits set -1U is returned. */
2169 static unsigned partMSB(APInt::WordType value) {
2170 return findLastSet(value, ZB_Max);
2173 /* Returns the bit number of the least significant set bit of a
2174 part. If the input number has no bits set -1U is returned. */
2175 static unsigned partLSB(APInt::WordType value) {
2176 return findFirstSet(value, ZB_Max);
2179 /* Sets the least significant part of a bignum to the input value, and
2180 zeroes out higher parts. */
2181 void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
2185 for (unsigned i = 1; i < parts; i++)
2189 /* Assign one bignum to another. */
2190 void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
2191 for (unsigned i = 0; i < parts; i++)
2195 /* Returns true if a bignum is zero, false otherwise. */
2196 bool APInt::tcIsZero(const WordType *src, unsigned parts) {
2197 for (unsigned i = 0; i < parts; i++)
2204 /* Extract the given bit of a bignum; returns 0 or 1. */
2205 int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
2206 return (parts[whichWord(bit)] & maskBit(bit)) != 0;
2209 /* Set the given bit of a bignum. */
2210 void APInt::tcSetBit(WordType *parts, unsigned bit) {
2211 parts[whichWord(bit)] |= maskBit(bit);
2214 /* Clears the given bit of a bignum. */
2215 void APInt::tcClearBit(WordType *parts, unsigned bit) {
2216 parts[whichWord(bit)] &= ~maskBit(bit);
2219 /* Returns the bit number of the least significant set bit of a
2220 number. If the input number has no bits set -1U is returned. */
2221 unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
2222 for (unsigned i = 0; i < n; i++) {
2223 if (parts[i] != 0) {
2224 unsigned lsb = partLSB(parts[i]);
2226 return lsb + i * APINT_BITS_PER_WORD;
2233 /* Returns the bit number of the most significant set bit of a number.
2234 If the input number has no bits set -1U is returned. */
2235 unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
2239 if (parts[n] != 0) {
2240 unsigned msb = partMSB(parts[n]);
2242 return msb + n * APINT_BITS_PER_WORD;
2249 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2250 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2251 the least significant bit of DST. All high bits above srcBITS in
2252 DST are zero-filled. */
2254 APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
2255 unsigned srcBits, unsigned srcLSB) {
2256 unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
2257 assert(dstParts <= dstCount);
2259 unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
2260 tcAssign (dst, src + firstSrcPart, dstParts);
2262 unsigned shift = srcLSB % APINT_BITS_PER_WORD;
2263 tcShiftRight (dst, dstParts, shift);
2265 /* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
2266 in DST. If this is less that srcBits, append the rest, else
2267 clear the high bits. */
2268 unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
2270 WordType mask = lowBitMask (srcBits - n);
2271 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2272 << n % APINT_BITS_PER_WORD);
2273 } else if (n > srcBits) {
2274 if (srcBits % APINT_BITS_PER_WORD)
2275 dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
2278 /* Clear high parts. */
2279 while (dstParts < dstCount)
2280 dst[dstParts++] = 0;
2283 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2284 APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
2285 WordType c, unsigned parts) {
2288 for (unsigned i = 0; i < parts; i++) {
2289 WordType l = dst[i];
2291 dst[i] += rhs[i] + 1;
2302 /// This function adds a single "word" integer, src, to the multiple
2303 /// "word" integer array, dst[]. dst[] is modified to reflect the addition and
2304 /// 1 is returned if there is a carry out, otherwise 0 is returned.
2305 /// @returns the carry of the addition.
2306 APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
2308 for (unsigned i = 0; i < parts; ++i) {
2311 return 0; // No need to carry so exit early.
2312 src = 1; // Carry one to next digit.
2318 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2319 APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
2320 WordType c, unsigned parts) {
2323 for (unsigned i = 0; i < parts; i++) {
2324 WordType l = dst[i];
2326 dst[i] -= rhs[i] + 1;
2337 /// This function subtracts a single "word" (64-bit word), src, from
2338 /// the multi-word integer array, dst[], propagating the borrowed 1 value until
2339 /// no further borrowing is needed or it runs out of "words" in dst. The result
2340 /// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
2341 /// exhausted. In other words, if src > dst then this function returns 1,
2343 /// @returns the borrow out of the subtraction
2344 APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
2346 for (unsigned i = 0; i < parts; ++i) {
2347 WordType Dst = dst[i];
2350 return 0; // No need to borrow so exit early.
2351 src = 1; // We have to "borrow 1" from next "word"
2357 /* Negate a bignum in-place. */
2358 void APInt::tcNegate(WordType *dst, unsigned parts) {
2359 tcComplement(dst, parts);
2360 tcIncrement(dst, parts);
2363 /* DST += SRC * MULTIPLIER + CARRY if add is true
2364 DST = SRC * MULTIPLIER + CARRY if add is false
2366 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2367 they must start at the same point, i.e. DST == SRC.
2369 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2370 returned. Otherwise DST is filled with the least significant
2371 DSTPARTS parts of the result, and if all of the omitted higher
2372 parts were zero return zero, otherwise overflow occurred and
2374 int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
2375 WordType multiplier, WordType carry,
2376 unsigned srcParts, unsigned dstParts,
2378 /* Otherwise our writes of DST kill our later reads of SRC. */
2379 assert(dst <= src || dst >= src + srcParts);
2380 assert(dstParts <= srcParts + 1);
2382 /* N loops; minimum of dstParts and srcParts. */
2383 unsigned n = std::min(dstParts, srcParts);
2385 for (unsigned i = 0; i < n; i++) {
2386 WordType low, mid, high, srcPart;
2388 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2390 This cannot overflow, because
2392 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2394 which is less than n^2. */
2398 if (multiplier == 0 || srcPart == 0) {
2402 low = lowHalf(srcPart) * lowHalf(multiplier);
2403 high = highHalf(srcPart) * highHalf(multiplier);
2405 mid = lowHalf(srcPart) * highHalf(multiplier);
2406 high += highHalf(mid);
2407 mid <<= APINT_BITS_PER_WORD / 2;
2408 if (low + mid < low)
2412 mid = highHalf(srcPart) * lowHalf(multiplier);
2413 high += highHalf(mid);
2414 mid <<= APINT_BITS_PER_WORD / 2;
2415 if (low + mid < low)
2419 /* Now add carry. */
2420 if (low + carry < low)
2426 /* And now DST[i], and store the new low part there. */
2427 if (low + dst[i] < low)
2436 if (srcParts < dstParts) {
2437 /* Full multiplication, there is no overflow. */
2438 assert(srcParts + 1 == dstParts);
2439 dst[srcParts] = carry;
2443 /* We overflowed if there is carry. */
2447 /* We would overflow if any significant unwritten parts would be
2448 non-zero. This is true if any remaining src parts are non-zero
2449 and the multiplier is non-zero. */
2451 for (unsigned i = dstParts; i < srcParts; i++)
2455 /* We fitted in the narrow destination. */
2459 /* DST = LHS * RHS, where DST has the same width as the operands and
2460 is filled with the least significant parts of the result. Returns
2461 one if overflow occurred, otherwise zero. DST must be disjoint
2462 from both operands. */
2463 int APInt::tcMultiply(WordType *dst, const WordType *lhs,
2464 const WordType *rhs, unsigned parts) {
2465 assert(dst != lhs && dst != rhs);
2468 tcSet(dst, 0, parts);
2470 for (unsigned i = 0; i < parts; i++)
2471 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2477 /// DST = LHS * RHS, where DST has width the sum of the widths of the
2478 /// operands. No overflow occurs. DST must be disjoint from both operands.
2479 void APInt::tcFullMultiply(WordType *dst, const WordType *lhs,
2480 const WordType *rhs, unsigned lhsParts,
2481 unsigned rhsParts) {
2482 /* Put the narrower number on the LHS for less loops below. */
2483 if (lhsParts > rhsParts)
2484 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2486 assert(dst != lhs && dst != rhs);
2488 tcSet(dst, 0, rhsParts);
2490 for (unsigned i = 0; i < lhsParts; i++)
2491 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true);
2494 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2495 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2496 set REMAINDER to the remainder, return zero. i.e.
2498 OLD_LHS = RHS * LHS + REMAINDER
2500 SCRATCH is a bignum of the same size as the operands and result for
2501 use by the routine; its contents need not be initialized and are
2502 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2504 int APInt::tcDivide(WordType *lhs, const WordType *rhs,
2505 WordType *remainder, WordType *srhs,
2507 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2509 unsigned shiftCount = tcMSB(rhs, parts) + 1;
2510 if (shiftCount == 0)
2513 shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;
2514 unsigned n = shiftCount / APINT_BITS_PER_WORD;
2515 WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);
2517 tcAssign(srhs, rhs, parts);
2518 tcShiftLeft(srhs, parts, shiftCount);
2519 tcAssign(remainder, lhs, parts);
2520 tcSet(lhs, 0, parts);
2522 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2525 int compare = tcCompare(remainder, srhs, parts);
2527 tcSubtract(remainder, srhs, 0, parts);
2531 if (shiftCount == 0)
2534 tcShiftRight(srhs, parts, 1);
2535 if ((mask >>= 1) == 0) {
2536 mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);
2544 /// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
2545 /// no restrictions on Count.
2546 void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {
2547 // Don't bother performing a no-op shift.
2551 // WordShift is the inter-part shift; BitShift is the intra-part shift.
2552 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
2553 unsigned BitShift = Count % APINT_BITS_PER_WORD;
2555 // Fastpath for moving by whole words.
2556 if (BitShift == 0) {
2557 std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
2559 while (Words-- > WordShift) {
2560 Dst[Words] = Dst[Words - WordShift] << BitShift;
2561 if (Words > WordShift)
2563 Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);
2567 // Fill in the remainder with 0s.
2568 std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);
2571 /// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
2572 /// are no restrictions on Count.
2573 void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {
2574 // Don't bother performing a no-op shift.
2578 // WordShift is the inter-part shift; BitShift is the intra-part shift.
2579 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
2580 unsigned BitShift = Count % APINT_BITS_PER_WORD;
2582 unsigned WordsToMove = Words - WordShift;
2583 // Fastpath for moving by whole words.
2584 if (BitShift == 0) {
2585 std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
2587 for (unsigned i = 0; i != WordsToMove; ++i) {
2588 Dst[i] = Dst[i + WordShift] >> BitShift;
2589 if (i + 1 != WordsToMove)
2590 Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);
2594 // Fill in the remainder with 0s.
2595 std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
2598 /* Bitwise and of two bignums. */
2599 void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
2600 for (unsigned i = 0; i < parts; i++)
2604 /* Bitwise inclusive or of two bignums. */
2605 void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
2606 for (unsigned i = 0; i < parts; i++)
2610 /* Bitwise exclusive or of two bignums. */
2611 void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
2612 for (unsigned i = 0; i < parts; i++)
2616 /* Complement a bignum in-place. */
2617 void APInt::tcComplement(WordType *dst, unsigned parts) {
2618 for (unsigned i = 0; i < parts; i++)
2622 /* Comparison (unsigned) of two bignums. */
2623 int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
2627 if (lhs[parts] != rhs[parts])
2628 return (lhs[parts] > rhs[parts]) ? 1 : -1;
2634 /* Set the least significant BITS bits of a bignum, clear the
2636 void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
2639 while (bits > APINT_BITS_PER_WORD) {
2640 dst[i++] = ~(WordType) 0;
2641 bits -= APINT_BITS_PER_WORD;
2645 dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);