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::countLeadingOnes() const {
551 return llvm::countLeadingOnes(U.VAL << (APINT_BITS_PER_WORD - BitWidth));
553 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
556 highWordBits = APINT_BITS_PER_WORD;
559 shift = APINT_BITS_PER_WORD - highWordBits;
561 int i = getNumWords() - 1;
562 unsigned Count = llvm::countLeadingOnes(U.pVal[i] << shift);
563 if (Count == highWordBits) {
564 for (i--; i >= 0; --i) {
565 if (U.pVal[i] == WORD_MAX)
566 Count += APINT_BITS_PER_WORD;
568 Count += llvm::countLeadingOnes(U.pVal[i]);
576 unsigned APInt::countTrailingZeros() const {
578 return std::min(unsigned(llvm::countTrailingZeros(U.VAL)), BitWidth);
581 for (; i < getNumWords() && U.pVal[i] == 0; ++i)
582 Count += APINT_BITS_PER_WORD;
583 if (i < getNumWords())
584 Count += llvm::countTrailingZeros(U.pVal[i]);
585 return std::min(Count, BitWidth);
588 unsigned APInt::countTrailingOnesSlowCase() const {
591 for (; i < getNumWords() && U.pVal[i] == WORD_MAX; ++i)
592 Count += APINT_BITS_PER_WORD;
593 if (i < getNumWords())
594 Count += llvm::countTrailingOnes(U.pVal[i]);
595 assert(Count <= BitWidth);
599 unsigned APInt::countPopulationSlowCase() const {
601 for (unsigned i = 0; i < getNumWords(); ++i)
602 Count += llvm::countPopulation(U.pVal[i]);
606 bool APInt::intersectsSlowCase(const APInt &RHS) const {
607 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
608 if ((U.pVal[i] & RHS.U.pVal[i]) != 0)
614 bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
615 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
616 if ((U.pVal[i] & ~RHS.U.pVal[i]) != 0)
622 APInt APInt::byteSwap() const {
623 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
625 return APInt(BitWidth, ByteSwap_16(uint16_t(U.VAL)));
627 return APInt(BitWidth, ByteSwap_32(unsigned(U.VAL)));
628 if (BitWidth == 48) {
629 unsigned Tmp1 = unsigned(U.VAL >> 16);
630 Tmp1 = ByteSwap_32(Tmp1);
631 uint16_t Tmp2 = uint16_t(U.VAL);
632 Tmp2 = ByteSwap_16(Tmp2);
633 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
636 return APInt(BitWidth, ByteSwap_64(U.VAL));
638 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
639 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
640 Result.U.pVal[I] = ByteSwap_64(U.pVal[N - I - 1]);
641 if (Result.BitWidth != BitWidth) {
642 Result.lshrInPlace(Result.BitWidth - BitWidth);
643 Result.BitWidth = BitWidth;
648 APInt APInt::reverseBits() const {
651 return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
653 return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
655 return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
657 return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
663 APInt Reversed(BitWidth, 0);
664 unsigned S = BitWidth;
666 for (; Val != 0; Val.lshrInPlace(1)) {
676 APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {
677 // Fast-path a common case.
678 if (A == B) return A;
680 // Corner cases: if either operand is zero, the other is the gcd.
684 // Count common powers of 2 and remove all other powers of 2.
687 unsigned Pow2_A = A.countTrailingZeros();
688 unsigned Pow2_B = B.countTrailingZeros();
689 if (Pow2_A > Pow2_B) {
690 A.lshrInPlace(Pow2_A - Pow2_B);
692 } else if (Pow2_B > Pow2_A) {
693 B.lshrInPlace(Pow2_B - Pow2_A);
700 // Both operands are odd multiples of 2^Pow_2:
702 // gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))
704 // This is a modified version of Stein's algorithm, taking advantage of
705 // efficient countTrailingZeros().
709 A.lshrInPlace(A.countTrailingZeros() - Pow2);
712 B.lshrInPlace(B.countTrailingZeros() - Pow2);
719 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
726 // Get the sign bit from the highest order bit
727 bool isNeg = T.I >> 63;
729 // Get the 11-bit exponent and adjust for the 1023 bit bias
730 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
732 // If the exponent is negative, the value is < 0 so just return 0.
734 return APInt(width, 0u);
736 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
737 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
739 // If the exponent doesn't shift all bits out of the mantissa
741 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
742 APInt(width, mantissa >> (52 - exp));
744 // If the client didn't provide enough bits for us to shift the mantissa into
745 // then the result is undefined, just return 0
746 if (width <= exp - 52)
747 return APInt(width, 0);
749 // Otherwise, we have to shift the mantissa bits up to the right location
750 APInt Tmp(width, mantissa);
751 Tmp <<= (unsigned)exp - 52;
752 return isNeg ? -Tmp : Tmp;
755 /// This function converts this APInt to a double.
756 /// The layout for double is as following (IEEE Standard 754):
757 /// --------------------------------------
758 /// | Sign Exponent Fraction Bias |
759 /// |-------------------------------------- |
760 /// | 1[63] 11[62-52] 52[51-00] 1023 |
761 /// --------------------------------------
762 double APInt::roundToDouble(bool isSigned) const {
764 // Handle the simple case where the value is contained in one uint64_t.
765 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
766 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
768 int64_t sext = SignExtend64(getWord(0), BitWidth);
771 return double(getWord(0));
774 // Determine if the value is negative.
775 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
777 // Construct the absolute value if we're negative.
778 APInt Tmp(isNeg ? -(*this) : (*this));
780 // Figure out how many bits we're using.
781 unsigned n = Tmp.getActiveBits();
783 // The exponent (without bias normalization) is just the number of bits
784 // we are using. Note that the sign bit is gone since we constructed the
788 // Return infinity for exponent overflow
790 if (!isSigned || !isNeg)
791 return std::numeric_limits<double>::infinity();
793 return -std::numeric_limits<double>::infinity();
795 exp += 1023; // Increment for 1023 bias
797 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
798 // extract the high 52 bits from the correct words in pVal.
800 unsigned hiWord = whichWord(n-1);
802 mantissa = Tmp.U.pVal[0];
804 mantissa >>= n - 52; // shift down, we want the top 52 bits.
806 assert(hiWord > 0 && "huh?");
807 uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
808 uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
809 mantissa = hibits | lobits;
812 // The leading bit of mantissa is implicit, so get rid of it.
813 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
818 T.I = sign | (exp << 52) | mantissa;
822 // Truncate to new width.
823 APInt APInt::trunc(unsigned width) const {
824 assert(width < BitWidth && "Invalid APInt Truncate request");
825 assert(width && "Can't truncate to 0 bits");
827 if (width <= APINT_BITS_PER_WORD)
828 return APInt(width, getRawData()[0]);
830 APInt Result(getMemory(getNumWords(width)), width);
834 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
835 Result.U.pVal[i] = U.pVal[i];
837 // Truncate and copy any partial word.
838 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
840 Result.U.pVal[i] = U.pVal[i] << bits >> bits;
845 // Sign extend to a new width.
846 APInt APInt::sext(unsigned Width) const {
847 assert(Width > BitWidth && "Invalid APInt SignExtend request");
849 if (Width <= APINT_BITS_PER_WORD)
850 return APInt(Width, SignExtend64(U.VAL, BitWidth));
852 APInt Result(getMemory(getNumWords(Width)), Width);
855 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
857 // Sign extend the last word since there may be unused bits in the input.
858 Result.U.pVal[getNumWords() - 1] =
859 SignExtend64(Result.U.pVal[getNumWords() - 1],
860 ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
862 // Fill with sign bits.
863 std::memset(Result.U.pVal + getNumWords(), isNegative() ? -1 : 0,
864 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
865 Result.clearUnusedBits();
869 // Zero extend to a new width.
870 APInt APInt::zext(unsigned width) const {
871 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
873 if (width <= APINT_BITS_PER_WORD)
874 return APInt(width, U.VAL);
876 APInt Result(getMemory(getNumWords(width)), width);
879 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
881 // Zero remaining words.
882 std::memset(Result.U.pVal + getNumWords(), 0,
883 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
888 APInt APInt::zextOrTrunc(unsigned width) const {
889 if (BitWidth < width)
891 if (BitWidth > width)
896 APInt APInt::sextOrTrunc(unsigned width) const {
897 if (BitWidth < width)
899 if (BitWidth > width)
904 APInt APInt::zextOrSelf(unsigned width) const {
905 if (BitWidth < width)
910 APInt APInt::sextOrSelf(unsigned width) const {
911 if (BitWidth < width)
916 /// Arithmetic right-shift this APInt by shiftAmt.
917 /// @brief Arithmetic right-shift function.
918 void APInt::ashrInPlace(const APInt &shiftAmt) {
919 ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
922 /// Arithmetic right-shift this APInt by shiftAmt.
923 /// @brief Arithmetic right-shift function.
924 void APInt::ashrSlowCase(unsigned ShiftAmt) {
925 // Don't bother performing a no-op shift.
929 // Save the original sign bit for later.
930 bool Negative = isNegative();
932 // WordShift is the inter-part shift; BitShift is is intra-part shift.
933 unsigned WordShift = ShiftAmt / APINT_BITS_PER_WORD;
934 unsigned BitShift = ShiftAmt % APINT_BITS_PER_WORD;
936 unsigned WordsToMove = getNumWords() - WordShift;
937 if (WordsToMove != 0) {
938 // Sign extend the last word to fill in the unused bits.
939 U.pVal[getNumWords() - 1] = SignExtend64(
940 U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
942 // Fastpath for moving by whole words.
944 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
946 // Move the words containing significant bits.
947 for (unsigned i = 0; i != WordsToMove - 1; ++i)
948 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
949 (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));
951 // Handle the last word which has no high bits to copy.
952 U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
953 // Sign extend one more time.
954 U.pVal[WordsToMove - 1] =
955 SignExtend64(U.pVal[WordsToMove - 1], APINT_BITS_PER_WORD - BitShift);
959 // Fill in the remainder based on the original sign.
960 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
961 WordShift * APINT_WORD_SIZE);
965 /// Logical right-shift this APInt by shiftAmt.
966 /// @brief Logical right-shift function.
967 void APInt::lshrInPlace(const APInt &shiftAmt) {
968 lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
971 /// Logical right-shift this APInt by shiftAmt.
972 /// @brief Logical right-shift function.
973 void APInt::lshrSlowCase(unsigned ShiftAmt) {
974 tcShiftRight(U.pVal, getNumWords(), ShiftAmt);
977 /// Left-shift this APInt by shiftAmt.
978 /// @brief Left-shift function.
979 APInt &APInt::operator<<=(const APInt &shiftAmt) {
980 // It's undefined behavior in C to shift by BitWidth or greater.
981 *this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);
985 void APInt::shlSlowCase(unsigned ShiftAmt) {
986 tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);
990 // Calculate the rotate amount modulo the bit width.
991 static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
992 unsigned rotBitWidth = rotateAmt.getBitWidth();
993 APInt rot = rotateAmt;
994 if (rotBitWidth < BitWidth) {
995 // Extend the rotate APInt, so that the urem doesn't divide by 0.
996 // e.g. APInt(1, 32) would give APInt(1, 0).
997 rot = rotateAmt.zext(BitWidth);
999 rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
1000 return rot.getLimitedValue(BitWidth);
1003 APInt APInt::rotl(const APInt &rotateAmt) const {
1004 return rotl(rotateModulo(BitWidth, rotateAmt));
1007 APInt APInt::rotl(unsigned rotateAmt) const {
1008 rotateAmt %= BitWidth;
1011 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
1014 APInt APInt::rotr(const APInt &rotateAmt) const {
1015 return rotr(rotateModulo(BitWidth, rotateAmt));
1018 APInt APInt::rotr(unsigned rotateAmt) const {
1019 rotateAmt %= BitWidth;
1022 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
1025 // Square Root - this method computes and returns the square root of "this".
1026 // Three mechanisms are used for computation. For small values (<= 5 bits),
1027 // a table lookup is done. This gets some performance for common cases. For
1028 // values using less than 52 bits, the value is converted to double and then
1029 // the libc sqrt function is called. The result is rounded and then converted
1030 // back to a uint64_t which is then used to construct the result. Finally,
1031 // the Babylonian method for computing square roots is used.
1032 APInt APInt::sqrt() const {
1034 // Determine the magnitude of the value.
1035 unsigned magnitude = getActiveBits();
1037 // Use a fast table for some small values. This also gets rid of some
1038 // rounding errors in libc sqrt for small values.
1039 if (magnitude <= 5) {
1040 static const uint8_t results[32] = {
1043 /* 3- 6 */ 2, 2, 2, 2,
1044 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1045 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1046 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1049 return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
1052 // If the magnitude of the value fits in less than 52 bits (the precision of
1053 // an IEEE double precision floating point value), then we can use the
1054 // libc sqrt function which will probably use a hardware sqrt computation.
1055 // This should be faster than the algorithm below.
1056 if (magnitude < 52) {
1057 return APInt(BitWidth,
1058 uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL
1062 // Okay, all the short cuts are exhausted. We must compute it. The following
1063 // is a classical Babylonian method for computing the square root. This code
1064 // was adapted to APInt from a wikipedia article on such computations.
1065 // See http://www.wikipedia.org/ and go to the page named
1066 // Calculate_an_integer_square_root.
1067 unsigned nbits = BitWidth, i = 4;
1068 APInt testy(BitWidth, 16);
1069 APInt x_old(BitWidth, 1);
1070 APInt x_new(BitWidth, 0);
1071 APInt two(BitWidth, 2);
1073 // Select a good starting value using binary logarithms.
1074 for (;; i += 2, testy = testy.shl(2))
1075 if (i >= nbits || this->ule(testy)) {
1076 x_old = x_old.shl(i / 2);
1080 // Use the Babylonian method to arrive at the integer square root:
1082 x_new = (this->udiv(x_old) + x_old).udiv(two);
1083 if (x_old.ule(x_new))
1088 // Make sure we return the closest approximation
1089 // NOTE: The rounding calculation below is correct. It will produce an
1090 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
1091 // determined to be a rounding issue with pari/gp as it begins to use a
1092 // floating point representation after 192 bits. There are no discrepancies
1093 // between this algorithm and pari/gp for bit widths < 192 bits.
1094 APInt square(x_old * x_old);
1095 APInt nextSquare((x_old + 1) * (x_old +1));
1096 if (this->ult(square))
1098 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1099 APInt midpoint((nextSquare - square).udiv(two));
1100 APInt offset(*this - square);
1101 if (offset.ult(midpoint))
1106 /// Computes the multiplicative inverse of this APInt for a given modulo. The
1107 /// iterative extended Euclidean algorithm is used to solve for this value,
1108 /// however we simplify it to speed up calculating only the inverse, and take
1109 /// advantage of div+rem calculations. We also use some tricks to avoid copying
1110 /// (potentially large) APInts around.
1111 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1112 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1114 // Using the properties listed at the following web page (accessed 06/21/08):
1115 // http://www.numbertheory.org/php/euclid.html
1116 // (especially the properties numbered 3, 4 and 9) it can be proved that
1117 // BitWidth bits suffice for all the computations in the algorithm implemented
1118 // below. More precisely, this number of bits suffice if the multiplicative
1119 // inverse exists, but may not suffice for the general extended Euclidean
1122 APInt r[2] = { modulo, *this };
1123 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1124 APInt q(BitWidth, 0);
1127 for (i = 0; r[i^1] != 0; i ^= 1) {
1128 // An overview of the math without the confusing bit-flipping:
1129 // q = r[i-2] / r[i-1]
1130 // r[i] = r[i-2] % r[i-1]
1131 // t[i] = t[i-2] - t[i-1] * q
1132 udivrem(r[i], r[i^1], q, r[i]);
1136 // If this APInt and the modulo are not coprime, there is no multiplicative
1137 // inverse, so return 0. We check this by looking at the next-to-last
1138 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1141 return APInt(BitWidth, 0);
1143 // The next-to-last t is the multiplicative inverse. However, we are
1144 // interested in a positive inverse. Calculate a positive one from a negative
1145 // one if necessary. A simple addition of the modulo suffices because
1146 // abs(t[i]) is known to be less than *this/2 (see the link above).
1147 if (t[i].isNegative())
1150 return std::move(t[i]);
1153 /// Calculate the magic numbers required to implement a signed integer division
1154 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
1155 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1156 /// Warren, Jr., chapter 10.
1157 APInt::ms APInt::magic() const {
1158 const APInt& d = *this;
1160 APInt ad, anc, delta, q1, r1, q2, r2, t;
1161 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1165 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1166 anc = t - 1 - t.urem(ad); // absolute value of nc
1167 p = d.getBitWidth() - 1; // initialize p
1168 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1169 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1170 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1171 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1174 q1 = q1<<1; // update q1 = 2p/abs(nc)
1175 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1176 if (r1.uge(anc)) { // must be unsigned comparison
1180 q2 = q2<<1; // update q2 = 2p/abs(d)
1181 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1182 if (r2.uge(ad)) { // must be unsigned comparison
1187 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
1190 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1191 mag.s = p - d.getBitWidth(); // resulting shift
1195 /// Calculate the magic numbers required to implement an unsigned integer
1196 /// division by a constant as a sequence of multiplies, adds and shifts.
1197 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1198 /// S. Warren, Jr., chapter 10.
1199 /// LeadingZeros can be used to simplify the calculation if the upper bits
1200 /// of the divided value are known zero.
1201 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
1202 const APInt& d = *this;
1204 APInt nc, delta, q1, r1, q2, r2;
1206 magu.a = 0; // initialize "add" indicator
1207 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
1208 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1209 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1211 nc = allOnes - (allOnes - d).urem(d);
1212 p = d.getBitWidth() - 1; // initialize p
1213 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1214 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1215 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1216 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1219 if (r1.uge(nc - r1)) {
1220 q1 = q1 + q1 + 1; // update q1
1221 r1 = r1 + r1 - nc; // update r1
1224 q1 = q1+q1; // update q1
1225 r1 = r1+r1; // update r1
1227 if ((r2 + 1).uge(d - r2)) {
1228 if (q2.uge(signedMax)) magu.a = 1;
1229 q2 = q2+q2 + 1; // update q2
1230 r2 = r2+r2 + 1 - d; // update r2
1233 if (q2.uge(signedMin)) magu.a = 1;
1234 q2 = q2+q2; // update q2
1235 r2 = r2+r2 + 1; // update r2
1238 } while (p < d.getBitWidth()*2 &&
1239 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1240 magu.m = q2 + 1; // resulting magic number
1241 magu.s = p - d.getBitWidth(); // resulting shift
1245 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1246 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1247 /// variables here have the same names as in the algorithm. Comments explain
1248 /// the algorithm and any deviation from it.
1249 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
1250 unsigned m, unsigned n) {
1251 assert(u && "Must provide dividend");
1252 assert(v && "Must provide divisor");
1253 assert(q && "Must provide quotient");
1254 assert(u != v && u != q && v != q && "Must use different memory");
1255 assert(n>1 && "n must be > 1");
1257 // b denotes the base of the number system. In our case b is 2^32.
1258 const uint64_t b = uint64_t(1) << 32;
1260 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1261 DEBUG(dbgs() << "KnuthDiv: original:");
1262 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1263 DEBUG(dbgs() << " by");
1264 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1265 DEBUG(dbgs() << '\n');
1266 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1267 // u and v by d. Note that we have taken Knuth's advice here to use a power
1268 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1269 // 2 allows us to shift instead of multiply and it is easy to determine the
1270 // shift amount from the leading zeros. We are basically normalizing the u
1271 // and v so that its high bits are shifted to the top of v's range without
1272 // overflow. Note that this can require an extra word in u so that u must
1273 // be of length m+n+1.
1274 unsigned shift = countLeadingZeros(v[n-1]);
1275 uint32_t v_carry = 0;
1276 uint32_t u_carry = 0;
1278 for (unsigned i = 0; i < m+n; ++i) {
1279 uint32_t u_tmp = u[i] >> (32 - shift);
1280 u[i] = (u[i] << shift) | u_carry;
1283 for (unsigned i = 0; i < n; ++i) {
1284 uint32_t v_tmp = v[i] >> (32 - shift);
1285 v[i] = (v[i] << shift) | v_carry;
1291 DEBUG(dbgs() << "KnuthDiv: normal:");
1292 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1293 DEBUG(dbgs() << " by");
1294 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1295 DEBUG(dbgs() << '\n');
1297 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1300 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
1301 // D3. [Calculate q'.].
1302 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1303 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1304 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1305 // qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test
1306 // on v[n-2] determines at high speed most of the cases in which the trial
1307 // value qp is one too large, and it eliminates all cases where qp is two
1309 uint64_t dividend = Make_64(u[j+n], u[j+n-1]);
1310 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
1311 uint64_t qp = dividend / v[n-1];
1312 uint64_t rp = dividend % v[n-1];
1313 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1316 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1319 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
1321 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1322 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1323 // consists of a simple multiplication by a one-place number, combined with
1325 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1326 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1327 // true value plus b**(n+1), namely as the b's complement of
1328 // the true value, and a "borrow" to the left should be remembered.
1330 for (unsigned i = 0; i < n; ++i) {
1331 uint64_t p = uint64_t(qp) * uint64_t(v[i]);
1332 int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
1333 u[j+i] = Lo_32(subres);
1334 borrow = Hi_32(p) - Hi_32(subres);
1335 DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]
1336 << ", borrow = " << borrow << '\n');
1338 bool isNeg = u[j+n] < borrow;
1339 u[j+n] -= Lo_32(borrow);
1341 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1342 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1343 DEBUG(dbgs() << '\n');
1345 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
1346 // negative, go to step D6; otherwise go on to step D7.
1349 // D6. [Add back]. The probability that this step is necessary is very
1350 // small, on the order of only 2/b. Make sure that test data accounts for
1351 // this possibility. Decrease q[j] by 1
1353 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1354 // A carry will occur to the left of u[j+n], and it should be ignored
1355 // since it cancels with the borrow that occurred in D4.
1357 for (unsigned i = 0; i < n; i++) {
1358 uint32_t limit = std::min(u[j+i],v[i]);
1359 u[j+i] += v[i] + carry;
1360 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1364 DEBUG(dbgs() << "KnuthDiv: after correction:");
1365 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1366 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
1368 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1371 DEBUG(dbgs() << "KnuthDiv: quotient:");
1372 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1373 DEBUG(dbgs() << '\n');
1375 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1376 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1377 // compute the remainder (urem uses this).
1379 // The value d is expressed by the "shift" value above since we avoided
1380 // multiplication by d by using a shift left. So, all we have to do is
1381 // shift right here.
1384 DEBUG(dbgs() << "KnuthDiv: remainder:");
1385 for (int i = n-1; i >= 0; i--) {
1386 r[i] = (u[i] >> shift) | carry;
1387 carry = u[i] << (32 - shift);
1388 DEBUG(dbgs() << " " << r[i]);
1391 for (int i = n-1; i >= 0; i--) {
1393 DEBUG(dbgs() << " " << r[i]);
1396 DEBUG(dbgs() << '\n');
1398 DEBUG(dbgs() << '\n');
1401 void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
1402 unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
1403 assert(lhsWords >= rhsWords && "Fractional result");
1405 // First, compose the values into an array of 32-bit words instead of
1406 // 64-bit words. This is a necessity of both the "short division" algorithm
1407 // and the Knuth "classical algorithm" which requires there to be native
1408 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1409 // can't use 64-bit operands here because we don't have native results of
1410 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
1411 // work on large-endian machines.
1412 unsigned n = rhsWords * 2;
1413 unsigned m = (lhsWords * 2) - n;
1415 // Allocate space for the temporary values we need either on the stack, if
1416 // it will fit, or on the heap if it won't.
1417 uint32_t SPACE[128];
1418 uint32_t *U = nullptr;
1419 uint32_t *V = nullptr;
1420 uint32_t *Q = nullptr;
1421 uint32_t *R = nullptr;
1422 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1425 Q = &SPACE[(m+n+1) + n];
1427 R = &SPACE[(m+n+1) + n + (m+n)];
1429 U = new uint32_t[m + n + 1];
1430 V = new uint32_t[n];
1431 Q = new uint32_t[m+n];
1433 R = new uint32_t[n];
1436 // Initialize the dividend
1437 memset(U, 0, (m+n+1)*sizeof(uint32_t));
1438 for (unsigned i = 0; i < lhsWords; ++i) {
1439 uint64_t tmp = LHS[i];
1440 U[i * 2] = Lo_32(tmp);
1441 U[i * 2 + 1] = Hi_32(tmp);
1443 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1445 // Initialize the divisor
1446 memset(V, 0, (n)*sizeof(uint32_t));
1447 for (unsigned i = 0; i < rhsWords; ++i) {
1448 uint64_t tmp = RHS[i];
1449 V[i * 2] = Lo_32(tmp);
1450 V[i * 2 + 1] = Hi_32(tmp);
1453 // initialize the quotient and remainder
1454 memset(Q, 0, (m+n) * sizeof(uint32_t));
1456 memset(R, 0, n * sizeof(uint32_t));
1458 // Now, adjust m and n for the Knuth division. n is the number of words in
1459 // the divisor. m is the number of words by which the dividend exceeds the
1460 // divisor (i.e. m+n is the length of the dividend). These sizes must not
1461 // contain any zero words or the Knuth algorithm fails.
1462 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1466 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1469 // If we're left with only a single word for the divisor, Knuth doesn't work
1470 // so we implement the short division algorithm here. This is much simpler
1471 // and faster because we are certain that we can divide a 64-bit quantity
1472 // by a 32-bit quantity at hardware speed and short division is simply a
1473 // series of such operations. This is just like doing short division but we
1474 // are using base 2^32 instead of base 10.
1475 assert(n != 0 && "Divide by zero?");
1477 uint32_t divisor = V[0];
1478 uint32_t remainder = 0;
1479 for (int i = m; i >= 0; i--) {
1480 uint64_t partial_dividend = Make_64(remainder, U[i]);
1481 if (partial_dividend == 0) {
1484 } else if (partial_dividend < divisor) {
1486 remainder = Lo_32(partial_dividend);
1487 } else if (partial_dividend == divisor) {
1491 Q[i] = Lo_32(partial_dividend / divisor);
1492 remainder = Lo_32(partial_dividend - (Q[i] * divisor));
1498 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1500 KnuthDiv(U, V, Q, R, m, n);
1503 // If the caller wants the quotient
1505 for (unsigned i = 0; i < lhsWords; ++i)
1506 Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
1509 // If the caller wants the remainder
1511 for (unsigned i = 0; i < rhsWords; ++i)
1512 Remainder[i] = Make_64(R[i*2+1], R[i*2]);
1515 // Clean up the memory we allocated.
1516 if (U != &SPACE[0]) {
1524 APInt APInt::udiv(const APInt &RHS) const {
1525 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1527 // First, deal with the easy case
1528 if (isSingleWord()) {
1529 assert(RHS.U.VAL != 0 && "Divide by zero?");
1530 return APInt(BitWidth, U.VAL / RHS.U.VAL);
1533 // Get some facts about the LHS and RHS number of bits and words
1534 unsigned lhsWords = getNumWords(getActiveBits());
1535 unsigned rhsBits = RHS.getActiveBits();
1536 unsigned rhsWords = getNumWords(rhsBits);
1537 assert(rhsWords && "Divided by zero???");
1539 // Deal with some degenerate cases
1542 return APInt(BitWidth, 0);
1546 if (lhsWords < rhsWords || this->ult(RHS))
1547 // X / Y ===> 0, iff X < Y
1548 return APInt(BitWidth, 0);
1551 return APInt(BitWidth, 1);
1552 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
1553 // All high words are zero, just use native divide
1554 return APInt(BitWidth, this->U.pVal[0] / RHS.U.pVal[0]);
1556 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1557 APInt Quotient(BitWidth, 0); // to hold result.
1558 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal, nullptr);
1562 APInt APInt::udiv(uint64_t RHS) const {
1563 assert(RHS != 0 && "Divide by zero?");
1565 // First, deal with the easy case
1567 return APInt(BitWidth, U.VAL / RHS);
1569 // Get some facts about the LHS words.
1570 unsigned lhsWords = getNumWords(getActiveBits());
1572 // Deal with some degenerate cases
1575 return APInt(BitWidth, 0);
1580 // X / Y ===> 0, iff X < Y
1581 return APInt(BitWidth, 0);
1584 return APInt(BitWidth, 1);
1585 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
1586 // All high words are zero, just use native divide
1587 return APInt(BitWidth, this->U.pVal[0] / RHS);
1589 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1590 APInt Quotient(BitWidth, 0); // to hold result.
1591 divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, nullptr);
1595 APInt APInt::sdiv(const APInt &RHS) const {
1597 if (RHS.isNegative())
1598 return (-(*this)).udiv(-RHS);
1599 return -((-(*this)).udiv(RHS));
1601 if (RHS.isNegative())
1602 return -(this->udiv(-RHS));
1603 return this->udiv(RHS);
1606 APInt APInt::sdiv(int64_t RHS) const {
1609 return (-(*this)).udiv(-RHS);
1610 return -((-(*this)).udiv(RHS));
1613 return -(this->udiv(-RHS));
1614 return this->udiv(RHS);
1617 APInt APInt::urem(const APInt &RHS) const {
1618 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
1619 if (isSingleWord()) {
1620 assert(RHS.U.VAL != 0 && "Remainder by zero?");
1621 return APInt(BitWidth, U.VAL % RHS.U.VAL);
1624 // Get some facts about the LHS
1625 unsigned lhsWords = getNumWords(getActiveBits());
1627 // Get some facts about the RHS
1628 unsigned rhsBits = RHS.getActiveBits();
1629 unsigned rhsWords = getNumWords(rhsBits);
1630 assert(rhsWords && "Performing remainder operation by zero ???");
1632 // Check the degenerate cases
1635 return APInt(BitWidth, 0);
1638 return APInt(BitWidth, 0);
1639 if (lhsWords < rhsWords || this->ult(RHS))
1640 // X % Y ===> X, iff X < Y
1644 return APInt(BitWidth, 0);
1646 // All high words are zero, just use native remainder
1647 return APInt(BitWidth, U.pVal[0] % RHS.U.pVal[0]);
1649 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1650 APInt Remainder(BitWidth, 0);
1651 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, nullptr, Remainder.U.pVal);
1655 uint64_t APInt::urem(uint64_t RHS) const {
1656 assert(RHS != 0 && "Remainder by zero?");
1661 // Get some facts about the LHS
1662 unsigned lhsWords = getNumWords(getActiveBits());
1664 // Check the degenerate cases
1672 // X % Y ===> X, iff X < Y
1673 return getZExtValue();
1678 // All high words are zero, just use native remainder
1679 return U.pVal[0] % RHS;
1681 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1683 divide(U.pVal, lhsWords, &RHS, 1, nullptr, &Remainder);
1687 APInt APInt::srem(const APInt &RHS) const {
1689 if (RHS.isNegative())
1690 return -((-(*this)).urem(-RHS));
1691 return -((-(*this)).urem(RHS));
1693 if (RHS.isNegative())
1694 return this->urem(-RHS);
1695 return this->urem(RHS);
1698 int64_t APInt::srem(int64_t RHS) const {
1701 return -((-(*this)).urem(-RHS));
1702 return -((-(*this)).urem(RHS));
1705 return this->urem(-RHS);
1706 return this->urem(RHS);
1709 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
1710 APInt &Quotient, APInt &Remainder) {
1711 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
1712 unsigned BitWidth = LHS.BitWidth;
1714 // First, deal with the easy case
1715 if (LHS.isSingleWord()) {
1716 assert(RHS.U.VAL != 0 && "Divide by zero?");
1717 uint64_t QuotVal = LHS.U.VAL / RHS.U.VAL;
1718 uint64_t RemVal = LHS.U.VAL % RHS.U.VAL;
1719 Quotient = APInt(BitWidth, QuotVal);
1720 Remainder = APInt(BitWidth, RemVal);
1724 // Get some size facts about the dividend and divisor
1725 unsigned lhsWords = getNumWords(LHS.getActiveBits());
1726 unsigned rhsBits = RHS.getActiveBits();
1727 unsigned rhsWords = getNumWords(rhsBits);
1728 assert(rhsWords && "Performing divrem operation by zero ???");
1730 // Check the degenerate cases
1731 if (lhsWords == 0) {
1732 Quotient = 0; // 0 / Y ===> 0
1733 Remainder = 0; // 0 % Y ===> 0
1738 Quotient = LHS; // X / 1 ===> X
1739 Remainder = 0; // X % 1 ===> 0
1742 if (lhsWords < rhsWords || LHS.ult(RHS)) {
1743 Remainder = LHS; // X % Y ===> X, iff X < Y
1744 Quotient = 0; // X / Y ===> 0, iff X < Y
1749 Quotient = 1; // X / X ===> 1
1750 Remainder = 0; // X % X ===> 0;
1754 // Make sure there is enough space to hold the results.
1755 // NOTE: This assumes that reallocate won't affect any bits if it doesn't
1756 // change the size. This is necessary if Quotient or Remainder is aliased
1758 Quotient.reallocate(BitWidth);
1759 Remainder.reallocate(BitWidth);
1761 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
1762 // There is only one word to consider so use the native versions.
1763 uint64_t lhsValue = LHS.U.pVal[0];
1764 uint64_t rhsValue = RHS.U.pVal[0];
1765 Quotient = lhsValue / rhsValue;
1766 Remainder = lhsValue % rhsValue;
1770 // Okay, lets do it the long way
1771 divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,
1773 // Clear the rest of the Quotient and Remainder.
1774 std::memset(Quotient.U.pVal + lhsWords, 0,
1775 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
1776 std::memset(Remainder.U.pVal + rhsWords, 0,
1777 (getNumWords(BitWidth) - rhsWords) * APINT_WORD_SIZE);
1780 void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
1781 uint64_t &Remainder) {
1782 assert(RHS != 0 && "Divide by zero?");
1783 unsigned BitWidth = LHS.BitWidth;
1785 // First, deal with the easy case
1786 if (LHS.isSingleWord()) {
1787 uint64_t QuotVal = LHS.U.VAL / RHS;
1788 Remainder = LHS.U.VAL % RHS;
1789 Quotient = APInt(BitWidth, QuotVal);
1793 // Get some size facts about the dividend and divisor
1794 unsigned lhsWords = getNumWords(LHS.getActiveBits());
1796 // Check the degenerate cases
1797 if (lhsWords == 0) {
1798 Quotient = 0; // 0 / Y ===> 0
1799 Remainder = 0; // 0 % Y ===> 0
1804 Quotient = LHS; // X / 1 ===> X
1805 Remainder = 0; // X % 1 ===> 0
1809 Remainder = LHS.getZExtValue(); // X % Y ===> X, iff X < Y
1810 Quotient = 0; // X / Y ===> 0, iff X < Y
1815 Quotient = 1; // X / X ===> 1
1816 Remainder = 0; // X % X ===> 0;
1820 // Make sure there is enough space to hold the results.
1821 // NOTE: This assumes that reallocate won't affect any bits if it doesn't
1822 // change the size. This is necessary if Quotient is aliased with LHS.
1823 Quotient.reallocate(BitWidth);
1825 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
1826 // There is only one word to consider so use the native versions.
1827 uint64_t lhsValue = LHS.U.pVal[0];
1828 Quotient = lhsValue / RHS;
1829 Remainder = lhsValue % RHS;
1833 // Okay, lets do it the long way
1834 divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
1835 // Clear the rest of the Quotient.
1836 std::memset(Quotient.U.pVal + lhsWords, 0,
1837 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
1840 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
1841 APInt &Quotient, APInt &Remainder) {
1842 if (LHS.isNegative()) {
1843 if (RHS.isNegative())
1844 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
1846 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
1850 } else if (RHS.isNegative()) {
1851 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
1854 APInt::udivrem(LHS, RHS, Quotient, Remainder);
1858 void APInt::sdivrem(const APInt &LHS, int64_t RHS,
1859 APInt &Quotient, int64_t &Remainder) {
1860 uint64_t R = Remainder;
1861 if (LHS.isNegative()) {
1863 APInt::udivrem(-LHS, -RHS, Quotient, R);
1865 APInt::udivrem(-LHS, RHS, Quotient, R);
1869 } else if (RHS < 0) {
1870 APInt::udivrem(LHS, -RHS, Quotient, R);
1873 APInt::udivrem(LHS, RHS, Quotient, R);
1878 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
1879 APInt Res = *this+RHS;
1880 Overflow = isNonNegative() == RHS.isNonNegative() &&
1881 Res.isNonNegative() != isNonNegative();
1885 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
1886 APInt Res = *this+RHS;
1887 Overflow = Res.ult(RHS);
1891 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
1892 APInt Res = *this - RHS;
1893 Overflow = isNonNegative() != RHS.isNonNegative() &&
1894 Res.isNonNegative() != isNonNegative();
1898 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
1899 APInt Res = *this-RHS;
1900 Overflow = Res.ugt(*this);
1904 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
1905 // MININT/-1 --> overflow.
1906 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
1910 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
1911 APInt Res = *this * RHS;
1913 if (*this != 0 && RHS != 0)
1914 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
1920 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
1921 APInt Res = *this * RHS;
1923 if (*this != 0 && RHS != 0)
1924 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
1930 APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
1931 Overflow = ShAmt.uge(getBitWidth());
1933 return APInt(BitWidth, 0);
1935 if (isNonNegative()) // Don't allow sign change.
1936 Overflow = ShAmt.uge(countLeadingZeros());
1938 Overflow = ShAmt.uge(countLeadingOnes());
1940 return *this << ShAmt;
1943 APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
1944 Overflow = ShAmt.uge(getBitWidth());
1946 return APInt(BitWidth, 0);
1948 Overflow = ShAmt.ugt(countLeadingZeros());
1950 return *this << ShAmt;
1956 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
1957 // Check our assumptions here
1958 assert(!str.empty() && "Invalid string length");
1959 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
1961 "Radix should be 2, 8, 10, 16, or 36!");
1963 StringRef::iterator p = str.begin();
1964 size_t slen = str.size();
1965 bool isNeg = *p == '-';
1966 if (*p == '-' || *p == '+') {
1969 assert(slen && "String is only a sign, needs a value.");
1971 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
1972 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
1973 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
1974 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
1975 "Insufficient bit width");
1977 // Allocate memory if needed
1981 U.pVal = getClearedMemory(getNumWords());
1983 // Figure out if we can shift instead of multiply
1984 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
1986 // Enter digit traversal loop
1987 for (StringRef::iterator e = str.end(); p != e; ++p) {
1988 unsigned digit = getDigit(*p, radix);
1989 assert(digit < radix && "Invalid character in digit string");
1991 // Shift or multiply the value by the radix
1999 // Add in the digit we just interpreted
2002 // If its negative, put it in two's complement form
2007 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
2008 bool Signed, bool formatAsCLiteral) const {
2009 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2011 "Radix should be 2, 8, 10, 16, or 36!");
2013 const char *Prefix = "";
2014 if (formatAsCLiteral) {
2017 // Binary literals are a non-standard extension added in gcc 4.3:
2018 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2030 llvm_unreachable("Invalid radix!");
2034 // First, check for a zero value and just short circuit the logic below.
2037 Str.push_back(*Prefix);
2044 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2046 if (isSingleWord()) {
2048 char *BufPtr = std::end(Buffer);
2054 int64_t I = getSExtValue();
2064 Str.push_back(*Prefix);
2069 *--BufPtr = Digits[N % Radix];
2072 Str.append(BufPtr, std::end(Buffer));
2078 if (Signed && isNegative()) {
2079 // They want to print the signed version and it is a negative value
2080 // Flip the bits and add one to turn it into the equivalent positive
2081 // value and put a '-' in the result.
2087 Str.push_back(*Prefix);
2091 // We insert the digits backward, then reverse them to get the right order.
2092 unsigned StartDig = Str.size();
2094 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2095 // because the number of bits per digit (1, 3 and 4 respectively) divides
2096 // equally. We just shift until the value is zero.
2097 if (Radix == 2 || Radix == 8 || Radix == 16) {
2098 // Just shift tmp right for each digit width until it becomes zero
2099 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2100 unsigned MaskAmt = Radix - 1;
2102 while (Tmp.getBoolValue()) {
2103 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2104 Str.push_back(Digits[Digit]);
2105 Tmp.lshrInPlace(ShiftAmt);
2108 while (Tmp.getBoolValue()) {
2110 udivrem(Tmp, Radix, Tmp, Digit);
2111 assert(Digit < Radix && "divide failed");
2112 Str.push_back(Digits[Digit]);
2116 // Reverse the digits before returning.
2117 std::reverse(Str.begin()+StartDig, Str.end());
2120 /// Returns the APInt as a std::string. Note that this is an inefficient method.
2121 /// It is better to pass in a SmallVector/SmallString to the methods above.
2122 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2124 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
2128 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2129 LLVM_DUMP_METHOD void APInt::dump() const {
2130 SmallString<40> S, U;
2131 this->toStringUnsigned(U);
2132 this->toStringSigned(S);
2133 dbgs() << "APInt(" << BitWidth << "b, "
2134 << U << "u " << S << "s)\n";
2138 void APInt::print(raw_ostream &OS, bool isSigned) const {
2140 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
2144 // This implements a variety of operations on a representation of
2145 // arbitrary precision, two's-complement, bignum integer values.
2147 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2148 // and unrestricting assumption.
2149 static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,
2150 "Part width must be divisible by 2!");
2152 /* Some handy functions local to this file. */
2154 /* Returns the integer part with the least significant BITS set.
2155 BITS cannot be zero. */
2156 static inline APInt::WordType lowBitMask(unsigned bits) {
2157 assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD);
2159 return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
2162 /* Returns the value of the lower half of PART. */
2163 static inline APInt::WordType lowHalf(APInt::WordType part) {
2164 return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
2167 /* Returns the value of the upper half of PART. */
2168 static inline APInt::WordType highHalf(APInt::WordType part) {
2169 return part >> (APInt::APINT_BITS_PER_WORD / 2);
2172 /* Returns the bit number of the most significant set bit of a part.
2173 If the input number has no bits set -1U is returned. */
2174 static unsigned partMSB(APInt::WordType value) {
2175 return findLastSet(value, ZB_Max);
2178 /* Returns the bit number of the least significant set bit of a
2179 part. If the input number has no bits set -1U is returned. */
2180 static unsigned partLSB(APInt::WordType value) {
2181 return findFirstSet(value, ZB_Max);
2184 /* Sets the least significant part of a bignum to the input value, and
2185 zeroes out higher parts. */
2186 void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
2190 for (unsigned i = 1; i < parts; i++)
2194 /* Assign one bignum to another. */
2195 void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
2196 for (unsigned i = 0; i < parts; i++)
2200 /* Returns true if a bignum is zero, false otherwise. */
2201 bool APInt::tcIsZero(const WordType *src, unsigned parts) {
2202 for (unsigned i = 0; i < parts; i++)
2209 /* Extract the given bit of a bignum; returns 0 or 1. */
2210 int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
2211 return (parts[whichWord(bit)] & maskBit(bit)) != 0;
2214 /* Set the given bit of a bignum. */
2215 void APInt::tcSetBit(WordType *parts, unsigned bit) {
2216 parts[whichWord(bit)] |= maskBit(bit);
2219 /* Clears the given bit of a bignum. */
2220 void APInt::tcClearBit(WordType *parts, unsigned bit) {
2221 parts[whichWord(bit)] &= ~maskBit(bit);
2224 /* Returns the bit number of the least significant set bit of a
2225 number. If the input number has no bits set -1U is returned. */
2226 unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
2227 for (unsigned i = 0; i < n; i++) {
2228 if (parts[i] != 0) {
2229 unsigned lsb = partLSB(parts[i]);
2231 return lsb + i * APINT_BITS_PER_WORD;
2238 /* Returns the bit number of the most significant set bit of a number.
2239 If the input number has no bits set -1U is returned. */
2240 unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
2244 if (parts[n] != 0) {
2245 unsigned msb = partMSB(parts[n]);
2247 return msb + n * APINT_BITS_PER_WORD;
2254 /* Copy the bit vector of width srcBITS from SRC, starting at bit
2255 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2256 the least significant bit of DST. All high bits above srcBITS in
2257 DST are zero-filled. */
2259 APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
2260 unsigned srcBits, unsigned srcLSB) {
2261 unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
2262 assert(dstParts <= dstCount);
2264 unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
2265 tcAssign (dst, src + firstSrcPart, dstParts);
2267 unsigned shift = srcLSB % APINT_BITS_PER_WORD;
2268 tcShiftRight (dst, dstParts, shift);
2270 /* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
2271 in DST. If this is less that srcBits, append the rest, else
2272 clear the high bits. */
2273 unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
2275 WordType mask = lowBitMask (srcBits - n);
2276 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2277 << n % APINT_BITS_PER_WORD);
2278 } else if (n > srcBits) {
2279 if (srcBits % APINT_BITS_PER_WORD)
2280 dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
2283 /* Clear high parts. */
2284 while (dstParts < dstCount)
2285 dst[dstParts++] = 0;
2288 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
2289 APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
2290 WordType c, unsigned parts) {
2293 for (unsigned i = 0; i < parts; i++) {
2294 WordType l = dst[i];
2296 dst[i] += rhs[i] + 1;
2307 /// This function adds a single "word" integer, src, to the multiple
2308 /// "word" integer array, dst[]. dst[] is modified to reflect the addition and
2309 /// 1 is returned if there is a carry out, otherwise 0 is returned.
2310 /// @returns the carry of the addition.
2311 APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
2313 for (unsigned i = 0; i < parts; ++i) {
2316 return 0; // No need to carry so exit early.
2317 src = 1; // Carry one to next digit.
2323 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
2324 APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
2325 WordType c, unsigned parts) {
2328 for (unsigned i = 0; i < parts; i++) {
2329 WordType l = dst[i];
2331 dst[i] -= rhs[i] + 1;
2342 /// This function subtracts a single "word" (64-bit word), src, from
2343 /// the multi-word integer array, dst[], propagating the borrowed 1 value until
2344 /// no further borrowing is needed or it runs out of "words" in dst. The result
2345 /// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
2346 /// exhausted. In other words, if src > dst then this function returns 1,
2348 /// @returns the borrow out of the subtraction
2349 APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
2351 for (unsigned i = 0; i < parts; ++i) {
2352 WordType Dst = dst[i];
2355 return 0; // No need to borrow so exit early.
2356 src = 1; // We have to "borrow 1" from next "word"
2362 /* Negate a bignum in-place. */
2363 void APInt::tcNegate(WordType *dst, unsigned parts) {
2364 tcComplement(dst, parts);
2365 tcIncrement(dst, parts);
2368 /* DST += SRC * MULTIPLIER + CARRY if add is true
2369 DST = SRC * MULTIPLIER + CARRY if add is false
2371 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2372 they must start at the same point, i.e. DST == SRC.
2374 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2375 returned. Otherwise DST is filled with the least significant
2376 DSTPARTS parts of the result, and if all of the omitted higher
2377 parts were zero return zero, otherwise overflow occurred and
2379 int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
2380 WordType multiplier, WordType carry,
2381 unsigned srcParts, unsigned dstParts,
2383 /* Otherwise our writes of DST kill our later reads of SRC. */
2384 assert(dst <= src || dst >= src + srcParts);
2385 assert(dstParts <= srcParts + 1);
2387 /* N loops; minimum of dstParts and srcParts. */
2388 unsigned n = std::min(dstParts, srcParts);
2390 for (unsigned i = 0; i < n; i++) {
2391 WordType low, mid, high, srcPart;
2393 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2395 This cannot overflow, because
2397 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2399 which is less than n^2. */
2403 if (multiplier == 0 || srcPart == 0) {
2407 low = lowHalf(srcPart) * lowHalf(multiplier);
2408 high = highHalf(srcPart) * highHalf(multiplier);
2410 mid = lowHalf(srcPart) * highHalf(multiplier);
2411 high += highHalf(mid);
2412 mid <<= APINT_BITS_PER_WORD / 2;
2413 if (low + mid < low)
2417 mid = highHalf(srcPart) * lowHalf(multiplier);
2418 high += highHalf(mid);
2419 mid <<= APINT_BITS_PER_WORD / 2;
2420 if (low + mid < low)
2424 /* Now add carry. */
2425 if (low + carry < low)
2431 /* And now DST[i], and store the new low part there. */
2432 if (low + dst[i] < low)
2441 if (srcParts < dstParts) {
2442 /* Full multiplication, there is no overflow. */
2443 assert(srcParts + 1 == dstParts);
2444 dst[srcParts] = carry;
2448 /* We overflowed if there is carry. */
2452 /* We would overflow if any significant unwritten parts would be
2453 non-zero. This is true if any remaining src parts are non-zero
2454 and the multiplier is non-zero. */
2456 for (unsigned i = dstParts; i < srcParts; i++)
2460 /* We fitted in the narrow destination. */
2464 /* DST = LHS * RHS, where DST has the same width as the operands and
2465 is filled with the least significant parts of the result. Returns
2466 one if overflow occurred, otherwise zero. DST must be disjoint
2467 from both operands. */
2468 int APInt::tcMultiply(WordType *dst, const WordType *lhs,
2469 const WordType *rhs, unsigned parts) {
2470 assert(dst != lhs && dst != rhs);
2473 tcSet(dst, 0, parts);
2475 for (unsigned i = 0; i < parts; i++)
2476 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2482 /// DST = LHS * RHS, where DST has width the sum of the widths of the
2483 /// operands. No overflow occurs. DST must be disjoint from both operands.
2484 void APInt::tcFullMultiply(WordType *dst, const WordType *lhs,
2485 const WordType *rhs, unsigned lhsParts,
2486 unsigned rhsParts) {
2487 /* Put the narrower number on the LHS for less loops below. */
2488 if (lhsParts > rhsParts)
2489 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2491 assert(dst != lhs && dst != rhs);
2493 tcSet(dst, 0, rhsParts);
2495 for (unsigned i = 0; i < lhsParts; i++)
2496 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true);
2499 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2500 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2501 set REMAINDER to the remainder, return zero. i.e.
2503 OLD_LHS = RHS * LHS + REMAINDER
2505 SCRATCH is a bignum of the same size as the operands and result for
2506 use by the routine; its contents need not be initialized and are
2507 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2509 int APInt::tcDivide(WordType *lhs, const WordType *rhs,
2510 WordType *remainder, WordType *srhs,
2512 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2514 unsigned shiftCount = tcMSB(rhs, parts) + 1;
2515 if (shiftCount == 0)
2518 shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;
2519 unsigned n = shiftCount / APINT_BITS_PER_WORD;
2520 WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);
2522 tcAssign(srhs, rhs, parts);
2523 tcShiftLeft(srhs, parts, shiftCount);
2524 tcAssign(remainder, lhs, parts);
2525 tcSet(lhs, 0, parts);
2527 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2530 int compare = tcCompare(remainder, srhs, parts);
2532 tcSubtract(remainder, srhs, 0, parts);
2536 if (shiftCount == 0)
2539 tcShiftRight(srhs, parts, 1);
2540 if ((mask >>= 1) == 0) {
2541 mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);
2549 /// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
2550 /// no restrictions on Count.
2551 void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {
2552 // Don't bother performing a no-op shift.
2556 // WordShift is the inter-part shift; BitShift is the intra-part shift.
2557 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
2558 unsigned BitShift = Count % APINT_BITS_PER_WORD;
2560 // Fastpath for moving by whole words.
2561 if (BitShift == 0) {
2562 std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
2564 while (Words-- > WordShift) {
2565 Dst[Words] = Dst[Words - WordShift] << BitShift;
2566 if (Words > WordShift)
2568 Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);
2572 // Fill in the remainder with 0s.
2573 std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);
2576 /// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
2577 /// are no restrictions on Count.
2578 void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {
2579 // Don't bother performing a no-op shift.
2583 // WordShift is the inter-part shift; BitShift is the intra-part shift.
2584 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
2585 unsigned BitShift = Count % APINT_BITS_PER_WORD;
2587 unsigned WordsToMove = Words - WordShift;
2588 // Fastpath for moving by whole words.
2589 if (BitShift == 0) {
2590 std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
2592 for (unsigned i = 0; i != WordsToMove; ++i) {
2593 Dst[i] = Dst[i + WordShift] >> BitShift;
2594 if (i + 1 != WordsToMove)
2595 Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);
2599 // Fill in the remainder with 0s.
2600 std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
2603 /* Bitwise and of two bignums. */
2604 void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
2605 for (unsigned i = 0; i < parts; i++)
2609 /* Bitwise inclusive or of two bignums. */
2610 void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
2611 for (unsigned i = 0; i < parts; i++)
2615 /* Bitwise exclusive or of two bignums. */
2616 void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
2617 for (unsigned i = 0; i < parts; i++)
2621 /* Complement a bignum in-place. */
2622 void APInt::tcComplement(WordType *dst, unsigned parts) {
2623 for (unsigned i = 0; i < parts; i++)
2627 /* Comparison (unsigned) of two bignums. */
2628 int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
2632 if (lhs[parts] != rhs[parts])
2633 return (lhs[parts] > rhs[parts]) ? 1 : -1;
2639 /* Set the least significant BITS bits of a bignum, clear the
2641 void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
2644 while (bits > APINT_BITS_PER_WORD) {
2645 dst[i++] = ~(WordType) 0;
2646 bits -= APINT_BITS_PER_WORD;
2650 dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);