LLVM API Documentation
00001 //===-- APInt.cpp - Implement APInt class ---------------------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements a class to represent arbitrary precision integer 00011 // constant values and provide a variety of arithmetic operations on them. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #define DEBUG_TYPE "apint" 00016 #include "llvm/ADT/APInt.h" 00017 #include "llvm/ADT/StringRef.h" 00018 #include "llvm/ADT/FoldingSet.h" 00019 #include "llvm/ADT/SmallString.h" 00020 #include "llvm/Support/Debug.h" 00021 #include "llvm/Support/ErrorHandling.h" 00022 #include "llvm/Support/MathExtras.h" 00023 #include "llvm/Support/raw_ostream.h" 00024 #include <cmath> 00025 #include <limits> 00026 #include <cstring> 00027 #include <cstdlib> 00028 using namespace llvm; 00029 00030 /// A utility function for allocating memory, checking for allocation failures, 00031 /// and ensuring the contents are zeroed. 00032 inline static uint64_t* getClearedMemory(unsigned numWords) { 00033 uint64_t * result = new uint64_t[numWords]; 00034 assert(result && "APInt memory allocation fails!"); 00035 memset(result, 0, numWords * sizeof(uint64_t)); 00036 return result; 00037 } 00038 00039 /// A utility function for allocating memory and checking for allocation 00040 /// failure. The content is not zeroed. 00041 inline static uint64_t* getMemory(unsigned numWords) { 00042 uint64_t * result = new uint64_t[numWords]; 00043 assert(result && "APInt memory allocation fails!"); 00044 return result; 00045 } 00046 00047 /// A utility function that converts a character to a digit. 00048 inline static unsigned getDigit(char cdigit, uint8_t radix) { 00049 unsigned r; 00050 00051 if (radix == 16) { 00052 r = cdigit - '0'; 00053 if (r <= 9) 00054 return r; 00055 00056 r = cdigit - 'A'; 00057 if (r <= 5) 00058 return r + 10; 00059 00060 r = cdigit - 'a'; 00061 if (r <= 5) 00062 return r + 10; 00063 } 00064 00065 r = cdigit - '0'; 00066 if (r < radix) 00067 return r; 00068 00069 return -1U; 00070 } 00071 00072 00073 void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) { 00074 pVal = getClearedMemory(getNumWords()); 00075 pVal[0] = val; 00076 if (isSigned && int64_t(val) < 0) 00077 for (unsigned i = 1; i < getNumWords(); ++i) 00078 pVal[i] = -1ULL; 00079 } 00080 00081 void APInt::initSlowCase(const APInt& that) { 00082 pVal = getMemory(getNumWords()); 00083 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE); 00084 } 00085 00086 00087 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]) 00088 : BitWidth(numBits), VAL(0) { 00089 assert(BitWidth && "Bitwidth too small"); 00090 assert(bigVal && "Null pointer detected!"); 00091 if (isSingleWord()) 00092 VAL = bigVal[0]; 00093 else { 00094 // Get memory, cleared to 0 00095 pVal = getClearedMemory(getNumWords()); 00096 // Calculate the number of words to copy 00097 unsigned words = std::min<unsigned>(numWords, getNumWords()); 00098 // Copy the words from bigVal to pVal 00099 memcpy(pVal, bigVal, words * APINT_WORD_SIZE); 00100 } 00101 // Make sure unused high bits are cleared 00102 clearUnusedBits(); 00103 } 00104 00105 APInt::APInt(unsigned numbits, const StringRef& Str, uint8_t radix) 00106 : BitWidth(numbits), VAL(0) { 00107 assert(BitWidth && "Bitwidth too small"); 00108 fromString(numbits, Str, radix); 00109 } 00110 00111 APInt& APInt::AssignSlowCase(const APInt& RHS) { 00112 // Don't do anything for X = X 00113 if (this == &RHS) 00114 return *this; 00115 00116 if (BitWidth == RHS.getBitWidth()) { 00117 // assume same bit-width single-word case is already handled 00118 assert(!isSingleWord()); 00119 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE); 00120 return *this; 00121 } 00122 00123 if (isSingleWord()) { 00124 // assume case where both are single words is already handled 00125 assert(!RHS.isSingleWord()); 00126 VAL = 0; 00127 pVal = getMemory(RHS.getNumWords()); 00128 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 00129 } else if (getNumWords() == RHS.getNumWords()) 00130 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 00131 else if (RHS.isSingleWord()) { 00132 delete [] pVal; 00133 VAL = RHS.VAL; 00134 } else { 00135 delete [] pVal; 00136 pVal = getMemory(RHS.getNumWords()); 00137 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 00138 } 00139 BitWidth = RHS.BitWidth; 00140 return clearUnusedBits(); 00141 } 00142 00143 APInt& APInt::operator=(uint64_t RHS) { 00144 if (isSingleWord()) 00145 VAL = RHS; 00146 else { 00147 pVal[0] = RHS; 00148 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); 00149 } 00150 return clearUnusedBits(); 00151 } 00152 00153 /// Profile - This method 'profiles' an APInt for use with FoldingSet. 00154 void APInt::Profile(FoldingSetNodeID& ID) const { 00155 ID.AddInteger(BitWidth); 00156 00157 if (isSingleWord()) { 00158 ID.AddInteger(VAL); 00159 return; 00160 } 00161 00162 unsigned NumWords = getNumWords(); 00163 for (unsigned i = 0; i < NumWords; ++i) 00164 ID.AddInteger(pVal[i]); 00165 } 00166 00167 /// add_1 - This function adds a single "digit" integer, y, to the multiple 00168 /// "digit" integer array, x[]. x[] is modified to reflect the addition and 00169 /// 1 is returned if there is a carry out, otherwise 0 is returned. 00170 /// @returns the carry of the addition. 00171 static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) { 00172 for (unsigned i = 0; i < len; ++i) { 00173 dest[i] = y + x[i]; 00174 if (dest[i] < y) 00175 y = 1; // Carry one to next digit. 00176 else { 00177 y = 0; // No need to carry so exit early 00178 break; 00179 } 00180 } 00181 return y; 00182 } 00183 00184 /// @brief Prefix increment operator. Increments the APInt by one. 00185 APInt& APInt::operator++() { 00186 if (isSingleWord()) 00187 ++VAL; 00188 else 00189 add_1(pVal, pVal, getNumWords(), 1); 00190 return clearUnusedBits(); 00191 } 00192 00193 /// sub_1 - This function subtracts a single "digit" (64-bit word), y, from 00194 /// the multi-digit integer array, x[], propagating the borrowed 1 value until 00195 /// no further borrowing is neeeded or it runs out of "digits" in x. The result 00196 /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted. 00197 /// In other words, if y > x then this function returns 1, otherwise 0. 00198 /// @returns the borrow out of the subtraction 00199 static bool sub_1(uint64_t x[], unsigned len, uint64_t y) { 00200 for (unsigned i = 0; i < len; ++i) { 00201 uint64_t X = x[i]; 00202 x[i] -= y; 00203 if (y > X) 00204 y = 1; // We have to "borrow 1" from next "digit" 00205 else { 00206 y = 0; // No need to borrow 00207 break; // Remaining digits are unchanged so exit early 00208 } 00209 } 00210 return bool(y); 00211 } 00212 00213 /// @brief Prefix decrement operator. Decrements the APInt by one. 00214 APInt& APInt::operator--() { 00215 if (isSingleWord()) 00216 --VAL; 00217 else 00218 sub_1(pVal, getNumWords(), 1); 00219 return clearUnusedBits(); 00220 } 00221 00222 /// add - This function adds the integer array x to the integer array Y and 00223 /// places the result in dest. 00224 /// @returns the carry out from the addition 00225 /// @brief General addition of 64-bit integer arrays 00226 static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y, 00227 unsigned len) { 00228 bool carry = false; 00229 for (unsigned i = 0; i< len; ++i) { 00230 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x 00231 dest[i] = x[i] + y[i] + carry; 00232 carry = dest[i] < limit || (carry && dest[i] == limit); 00233 } 00234 return carry; 00235 } 00236 00237 /// Adds the RHS APint to this APInt. 00238 /// @returns this, after addition of RHS. 00239 /// @brief Addition assignment operator. 00240 APInt& APInt::operator+=(const APInt& RHS) { 00241 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 00242 if (isSingleWord()) 00243 VAL += RHS.VAL; 00244 else { 00245 add(pVal, pVal, RHS.pVal, getNumWords()); 00246 } 00247 return clearUnusedBits(); 00248 } 00249 00250 /// Subtracts the integer array y from the integer array x 00251 /// @returns returns the borrow out. 00252 /// @brief Generalized subtraction of 64-bit integer arrays. 00253 static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y, 00254 unsigned len) { 00255 bool borrow = false; 00256 for (unsigned i = 0; i < len; ++i) { 00257 uint64_t x_tmp = borrow ? x[i] - 1 : x[i]; 00258 borrow = y[i] > x_tmp || (borrow && x[i] == 0); 00259 dest[i] = x_tmp - y[i]; 00260 } 00261 return borrow; 00262 } 00263 00264 /// Subtracts the RHS APInt from this APInt 00265 /// @returns this, after subtraction 00266 /// @brief Subtraction assignment operator. 00267 APInt& APInt::operator-=(const APInt& RHS) { 00268 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 00269 if (isSingleWord()) 00270 VAL -= RHS.VAL; 00271 else 00272 sub(pVal, pVal, RHS.pVal, getNumWords()); 00273 return clearUnusedBits(); 00274 } 00275 00276 /// Multiplies an integer array, x by a a uint64_t integer and places the result 00277 /// into dest. 00278 /// @returns the carry out of the multiplication. 00279 /// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer. 00280 static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) { 00281 // Split y into high 32-bit part (hy) and low 32-bit part (ly) 00282 uint64_t ly = y & 0xffffffffULL, hy = y >> 32; 00283 uint64_t carry = 0; 00284 00285 // For each digit of x. 00286 for (unsigned i = 0; i < len; ++i) { 00287 // Split x into high and low words 00288 uint64_t lx = x[i] & 0xffffffffULL; 00289 uint64_t hx = x[i] >> 32; 00290 // hasCarry - A flag to indicate if there is a carry to the next digit. 00291 // hasCarry == 0, no carry 00292 // hasCarry == 1, has carry 00293 // hasCarry == 2, no carry and the calculation result == 0. 00294 uint8_t hasCarry = 0; 00295 dest[i] = carry + lx * ly; 00296 // Determine if the add above introduces carry. 00297 hasCarry = (dest[i] < carry) ? 1 : 0; 00298 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0); 00299 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) + 00300 // (2^32 - 1) + 2^32 = 2^64. 00301 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 00302 00303 carry += (lx * hy) & 0xffffffffULL; 00304 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL); 00305 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) + 00306 (carry >> 32) + ((lx * hy) >> 32) + hx * hy; 00307 } 00308 return carry; 00309 } 00310 00311 /// Multiplies integer array x by integer array y and stores the result into 00312 /// the integer array dest. Note that dest's size must be >= xlen + ylen. 00313 /// @brief Generalized multiplicate of integer arrays. 00314 static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[], 00315 unsigned ylen) { 00316 dest[xlen] = mul_1(dest, x, xlen, y[0]); 00317 for (unsigned i = 1; i < ylen; ++i) { 00318 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32; 00319 uint64_t carry = 0, lx = 0, hx = 0; 00320 for (unsigned j = 0; j < xlen; ++j) { 00321 lx = x[j] & 0xffffffffULL; 00322 hx = x[j] >> 32; 00323 // hasCarry - A flag to indicate if has carry. 00324 // hasCarry == 0, no carry 00325 // hasCarry == 1, has carry 00326 // hasCarry == 2, no carry and the calculation result == 0. 00327 uint8_t hasCarry = 0; 00328 uint64_t resul = carry + lx * ly; 00329 hasCarry = (resul < carry) ? 1 : 0; 00330 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32); 00331 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 00332 00333 carry += (lx * hy) & 0xffffffffULL; 00334 resul = (carry << 32) | (resul & 0xffffffffULL); 00335 dest[i+j] += resul; 00336 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+ 00337 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) + 00338 ((lx * hy) >> 32) + hx * hy; 00339 } 00340 dest[i+xlen] = carry; 00341 } 00342 } 00343 00344 APInt& APInt::operator*=(const APInt& RHS) { 00345 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 00346 if (isSingleWord()) { 00347 VAL *= RHS.VAL; 00348 clearUnusedBits(); 00349 return *this; 00350 } 00351 00352 // Get some bit facts about LHS and check for zero 00353 unsigned lhsBits = getActiveBits(); 00354 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1; 00355 if (!lhsWords) 00356 // 0 * X ===> 0 00357 return *this; 00358 00359 // Get some bit facts about RHS and check for zero 00360 unsigned rhsBits = RHS.getActiveBits(); 00361 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1; 00362 if (!rhsWords) { 00363 // X * 0 ===> 0 00364 clear(); 00365 return *this; 00366 } 00367 00368 // Allocate space for the result 00369 unsigned destWords = rhsWords + lhsWords; 00370 uint64_t *dest = getMemory(destWords); 00371 00372 // Perform the long multiply 00373 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords); 00374 00375 // Copy result back into *this 00376 clear(); 00377 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords; 00378 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE); 00379 00380 // delete dest array and return 00381 delete[] dest; 00382 return *this; 00383 } 00384 00385 APInt& APInt::operator&=(const APInt& RHS) { 00386 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 00387 if (isSingleWord()) { 00388 VAL &= RHS.VAL; 00389 return *this; 00390 } 00391 unsigned numWords = getNumWords(); 00392 for (unsigned i = 0; i < numWords; ++i) 00393 pVal[i] &= RHS.pVal[i]; 00394 return *this; 00395 } 00396 00397 APInt& APInt::operator|=(const APInt& RHS) { 00398 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 00399 if (isSingleWord()) { 00400 VAL |= RHS.VAL; 00401 return *this; 00402 } 00403 unsigned numWords = getNumWords(); 00404 for (unsigned i = 0; i < numWords; ++i) 00405 pVal[i] |= RHS.pVal[i]; 00406 return *this; 00407 } 00408 00409 APInt& APInt::operator^=(const APInt& RHS) { 00410 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 00411 if (isSingleWord()) { 00412 VAL ^= RHS.VAL; 00413 this->clearUnusedBits(); 00414 return *this; 00415 } 00416 unsigned numWords = getNumWords(); 00417 for (unsigned i = 0; i < numWords; ++i) 00418 pVal[i] ^= RHS.pVal[i]; 00419 return clearUnusedBits(); 00420 } 00421 00422 APInt APInt::AndSlowCase(const APInt& RHS) const { 00423 unsigned numWords = getNumWords(); 00424 uint64_t* val = getMemory(numWords); 00425 for (unsigned i = 0; i < numWords; ++i) 00426 val[i] = pVal[i] & RHS.pVal[i]; 00427 return APInt(val, getBitWidth()); 00428 } 00429 00430 APInt APInt::OrSlowCase(const APInt& RHS) const { 00431 unsigned numWords = getNumWords(); 00432 uint64_t *val = getMemory(numWords); 00433 for (unsigned i = 0; i < numWords; ++i) 00434 val[i] = pVal[i] | RHS.pVal[i]; 00435 return APInt(val, getBitWidth()); 00436 } 00437 00438 APInt APInt::XorSlowCase(const APInt& RHS) const { 00439 unsigned numWords = getNumWords(); 00440 uint64_t *val = getMemory(numWords); 00441 for (unsigned i = 0; i < numWords; ++i) 00442 val[i] = pVal[i] ^ RHS.pVal[i]; 00443 00444 // 0^0==1 so clear the high bits in case they got set. 00445 return APInt(val, getBitWidth()).clearUnusedBits(); 00446 } 00447 00448 bool APInt::operator !() const { 00449 if (isSingleWord()) 00450 return !VAL; 00451 00452 for (unsigned i = 0; i < getNumWords(); ++i) 00453 if (pVal[i]) 00454 return false; 00455 return true; 00456 } 00457 00458 APInt APInt::operator*(const APInt& RHS) const { 00459 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 00460 if (isSingleWord()) 00461 return APInt(BitWidth, VAL * RHS.VAL); 00462 APInt Result(*this); 00463 Result *= RHS; 00464 return Result.clearUnusedBits(); 00465 } 00466 00467 APInt APInt::operator+(const APInt& RHS) const { 00468 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 00469 if (isSingleWord()) 00470 return APInt(BitWidth, VAL + RHS.VAL); 00471 APInt Result(BitWidth, 0); 00472 add(Result.pVal, this->pVal, RHS.pVal, getNumWords()); 00473 return Result.clearUnusedBits(); 00474 } 00475 00476 APInt APInt::operator-(const APInt& RHS) const { 00477 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 00478 if (isSingleWord()) 00479 return APInt(BitWidth, VAL - RHS.VAL); 00480 APInt Result(BitWidth, 0); 00481 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords()); 00482 return Result.clearUnusedBits(); 00483 } 00484 00485 bool APInt::operator[](unsigned bitPosition) const { 00486 return (maskBit(bitPosition) & 00487 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0; 00488 } 00489 00490 bool APInt::EqualSlowCase(const APInt& RHS) const { 00491 // Get some facts about the number of bits used in the two operands. 00492 unsigned n1 = getActiveBits(); 00493 unsigned n2 = RHS.getActiveBits(); 00494 00495 // If the number of bits isn't the same, they aren't equal 00496 if (n1 != n2) 00497 return false; 00498 00499 // If the number of bits fits in a word, we only need to compare the low word. 00500 if (n1 <= APINT_BITS_PER_WORD) 00501 return pVal[0] == RHS.pVal[0]; 00502 00503 // Otherwise, compare everything 00504 for (int i = whichWord(n1 - 1); i >= 0; --i) 00505 if (pVal[i] != RHS.pVal[i]) 00506 return false; 00507 return true; 00508 } 00509 00510 bool APInt::EqualSlowCase(uint64_t Val) const { 00511 unsigned n = getActiveBits(); 00512 if (n <= APINT_BITS_PER_WORD) 00513 return pVal[0] == Val; 00514 else 00515 return false; 00516 } 00517 00518 bool APInt::ult(const APInt& RHS) const { 00519 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"); 00520 if (isSingleWord()) 00521 return VAL < RHS.VAL; 00522 00523 // Get active bit length of both operands 00524 unsigned n1 = getActiveBits(); 00525 unsigned n2 = RHS.getActiveBits(); 00526 00527 // If magnitude of LHS is less than RHS, return true. 00528 if (n1 < n2) 00529 return true; 00530 00531 // If magnitude of RHS is greather than LHS, return false. 00532 if (n2 < n1) 00533 return false; 00534 00535 // If they bot fit in a word, just compare the low order word 00536 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD) 00537 return pVal[0] < RHS.pVal[0]; 00538 00539 // Otherwise, compare all words 00540 unsigned topWord = whichWord(std::max(n1,n2)-1); 00541 for (int i = topWord; i >= 0; --i) { 00542 if (pVal[i] > RHS.pVal[i]) 00543 return false; 00544 if (pVal[i] < RHS.pVal[i]) 00545 return true; 00546 } 00547 return false; 00548 } 00549 00550 bool APInt::slt(const APInt& RHS) const { 00551 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"); 00552 if (isSingleWord()) { 00553 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth); 00554 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth); 00555 return lhsSext < rhsSext; 00556 } 00557 00558 APInt lhs(*this); 00559 APInt rhs(RHS); 00560 bool lhsNeg = isNegative(); 00561 bool rhsNeg = rhs.isNegative(); 00562 if (lhsNeg) { 00563 // Sign bit is set so perform two's complement to make it positive 00564 lhs.flip(); 00565 lhs++; 00566 } 00567 if (rhsNeg) { 00568 // Sign bit is set so perform two's complement to make it positive 00569 rhs.flip(); 00570 rhs++; 00571 } 00572 00573 // Now we have unsigned values to compare so do the comparison if necessary 00574 // based on the negativeness of the values. 00575 if (lhsNeg) 00576 if (rhsNeg) 00577 return lhs.ugt(rhs); 00578 else 00579 return true; 00580 else if (rhsNeg) 00581 return false; 00582 else 00583 return lhs.ult(rhs); 00584 } 00585 00586 APInt& APInt::set(unsigned bitPosition) { 00587 if (isSingleWord()) 00588 VAL |= maskBit(bitPosition); 00589 else 00590 pVal[whichWord(bitPosition)] |= maskBit(bitPosition); 00591 return *this; 00592 } 00593 00594 /// Set the given bit to 0 whose position is given as "bitPosition". 00595 /// @brief Set a given bit to 0. 00596 APInt& APInt::clear(unsigned bitPosition) { 00597 if (isSingleWord()) 00598 VAL &= ~maskBit(bitPosition); 00599 else 00600 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition); 00601 return *this; 00602 } 00603 00604 /// @brief Toggle every bit to its opposite value. 00605 00606 /// Toggle a given bit to its opposite value whose position is given 00607 /// as "bitPosition". 00608 /// @brief Toggles a given bit to its opposite value. 00609 APInt& APInt::flip(unsigned bitPosition) { 00610 assert(bitPosition < BitWidth && "Out of the bit-width range!"); 00611 if ((*this)[bitPosition]) clear(bitPosition); 00612 else set(bitPosition); 00613 return *this; 00614 } 00615 00616 unsigned APInt::getBitsNeeded(const StringRef& str, uint8_t radix) { 00617 assert(!str.empty() && "Invalid string length"); 00618 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && 00619 "Radix should be 2, 8, 10, or 16!"); 00620 00621 size_t slen = str.size(); 00622 00623 // Each computation below needs to know if it's negative. 00624 StringRef::iterator p = str.begin(); 00625 unsigned isNegative = *p == '-'; 00626 if (*p == '-' || *p == '+') { 00627 p++; 00628 slen--; 00629 assert(slen && "String is only a sign, needs a value."); 00630 } 00631 00632 // For radixes of power-of-two values, the bits required is accurately and 00633 // easily computed 00634 if (radix == 2) 00635 return slen + isNegative; 00636 if (radix == 8) 00637 return slen * 3 + isNegative; 00638 if (radix == 16) 00639 return slen * 4 + isNegative; 00640 00641 // This is grossly inefficient but accurate. We could probably do something 00642 // with a computation of roughly slen*64/20 and then adjust by the value of 00643 // the first few digits. But, I'm not sure how accurate that could be. 00644 00645 // Compute a sufficient number of bits that is always large enough but might 00646 // be too large. This avoids the assertion in the constructor. This 00647 // calculation doesn't work appropriately for the numbers 0-9, so just use 4 00648 // bits in that case. 00649 unsigned sufficient = slen == 1 ? 4 : slen * 64/18; 00650 00651 // Convert to the actual binary value. 00652 APInt tmp(sufficient, StringRef(p, slen), radix); 00653 00654 // Compute how many bits are required. If the log is infinite, assume we need 00655 // just bit. 00656 unsigned log = tmp.logBase2(); 00657 if (log == (unsigned)-1) { 00658 return isNegative + 1; 00659 } else { 00660 return isNegative + log + 1; 00661 } 00662 } 00663 00664 // From http://www.burtleburtle.net, byBob Jenkins. 00665 // When targeting x86, both GCC and LLVM seem to recognize this as a 00666 // rotate instruction. 00667 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 00668 00669 // From http://www.burtleburtle.net, by Bob Jenkins. 00670 #define mix(a,b,c) \ 00671 { \ 00672 a -= c; a ^= rot(c, 4); c += b; \ 00673 b -= a; b ^= rot(a, 6); a += c; \ 00674 c -= b; c ^= rot(b, 8); b += a; \ 00675 a -= c; a ^= rot(c,16); c += b; \ 00676 b -= a; b ^= rot(a,19); a += c; \ 00677 c -= b; c ^= rot(b, 4); b += a; \ 00678 } 00679 00680 // From http://www.burtleburtle.net, by Bob Jenkins. 00681 #define final(a,b,c) \ 00682 { \ 00683 c ^= b; c -= rot(b,14); \ 00684 a ^= c; a -= rot(c,11); \ 00685 b ^= a; b -= rot(a,25); \ 00686 c ^= b; c -= rot(b,16); \ 00687 a ^= c; a -= rot(c,4); \ 00688 b ^= a; b -= rot(a,14); \ 00689 c ^= b; c -= rot(b,24); \ 00690 } 00691 00692 // hashword() was adapted from http://www.burtleburtle.net, by Bob 00693 // Jenkins. k is a pointer to an array of uint32_t values; length is 00694 // the length of the key, in 32-bit chunks. This version only handles 00695 // keys that are a multiple of 32 bits in size. 00696 static inline uint32_t hashword(const uint64_t *k64, size_t length) 00697 { 00698 const uint32_t *k = reinterpret_cast<const uint32_t *>(k64); 00699 uint32_t a,b,c; 00700 00701 /* Set up the internal state */ 00702 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2); 00703 00704 /*------------------------------------------------- handle most of the key */ 00705 while (length > 3) 00706 { 00707 a += k[0]; 00708 b += k[1]; 00709 c += k[2]; 00710 mix(a,b,c); 00711 length -= 3; 00712 k += 3; 00713 } 00714 00715 /*------------------------------------------- handle the last 3 uint32_t's */ 00716 switch (length) { /* all the case statements fall through */ 00717 case 3 : c+=k[2]; 00718 case 2 : b+=k[1]; 00719 case 1 : a+=k[0]; 00720 final(a,b,c); 00721 case 0: /* case 0: nothing left to add */ 00722 break; 00723 } 00724 /*------------------------------------------------------ report the result */ 00725 return c; 00726 } 00727 00728 // hashword8() was adapted from http://www.burtleburtle.net, by Bob 00729 // Jenkins. This computes a 32-bit hash from one 64-bit word. When 00730 // targeting x86 (32 or 64 bit), both LLVM and GCC compile this 00731 // function into about 35 instructions when inlined. 00732 static inline uint32_t hashword8(const uint64_t k64) 00733 { 00734 uint32_t a,b,c; 00735 a = b = c = 0xdeadbeef + 4; 00736 b += k64 >> 32; 00737 a += k64 & 0xffffffff; 00738 final(a,b,c); 00739 return c; 00740 } 00741 #undef final 00742 #undef mix 00743 #undef rot 00744 00745 uint64_t APInt::getHashValue() const { 00746 uint64_t hash; 00747 if (isSingleWord()) 00748 hash = hashword8(VAL); 00749 else 00750 hash = hashword(pVal, getNumWords()*2); 00751 return hash; 00752 } 00753 00754 /// HiBits - This function returns the high "numBits" bits of this APInt. 00755 APInt APInt::getHiBits(unsigned numBits) const { 00756 return APIntOps::lshr(*this, BitWidth - numBits); 00757 } 00758 00759 /// LoBits - This function returns the low "numBits" bits of this APInt. 00760 APInt APInt::getLoBits(unsigned numBits) const { 00761 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits), 00762 BitWidth - numBits); 00763 } 00764 00765 bool APInt::isPowerOf2() const { 00766 return (!!*this) && !(*this & (*this - APInt(BitWidth,1))); 00767 } 00768 00769 unsigned APInt::countLeadingZerosSlowCase() const { 00770 unsigned Count = 0; 00771 for (unsigned i = getNumWords(); i > 0u; --i) { 00772 if (pVal[i-1] == 0) 00773 Count += APINT_BITS_PER_WORD; 00774 else { 00775 Count += CountLeadingZeros_64(pVal[i-1]); 00776 break; 00777 } 00778 } 00779 unsigned remainder = BitWidth % APINT_BITS_PER_WORD; 00780 if (remainder) 00781 Count -= APINT_BITS_PER_WORD - remainder; 00782 return std::min(Count, BitWidth); 00783 } 00784 00785 static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) { 00786 unsigned Count = 0; 00787 if (skip) 00788 V <<= skip; 00789 while (V && (V & (1ULL << 63))) { 00790 Count++; 00791 V <<= 1; 00792 } 00793 return Count; 00794 } 00795 00796 unsigned APInt::countLeadingOnes() const { 00797 if (isSingleWord()) 00798 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth); 00799 00800 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD; 00801 unsigned shift; 00802 if (!highWordBits) { 00803 highWordBits = APINT_BITS_PER_WORD; 00804 shift = 0; 00805 } else { 00806 shift = APINT_BITS_PER_WORD - highWordBits; 00807 } 00808 int i = getNumWords() - 1; 00809 unsigned Count = countLeadingOnes_64(pVal[i], shift); 00810 if (Count == highWordBits) { 00811 for (i--; i >= 0; --i) { 00812 if (pVal[i] == -1ULL) 00813 Count += APINT_BITS_PER_WORD; 00814 else { 00815 Count += countLeadingOnes_64(pVal[i], 0); 00816 break; 00817 } 00818 } 00819 } 00820 return Count; 00821 } 00822 00823 unsigned APInt::countTrailingZeros() const { 00824 if (isSingleWord()) 00825 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth); 00826 unsigned Count = 0; 00827 unsigned i = 0; 00828 for (; i < getNumWords() && pVal[i] == 0; ++i) 00829 Count += APINT_BITS_PER_WORD; 00830 if (i < getNumWords()) 00831 Count += CountTrailingZeros_64(pVal[i]); 00832 return std::min(Count, BitWidth); 00833 } 00834 00835 unsigned APInt::countTrailingOnesSlowCase() const { 00836 unsigned Count = 0; 00837 unsigned i = 0; 00838 for (; i < getNumWords() && pVal[i] == -1ULL; ++i) 00839 Count += APINT_BITS_PER_WORD; 00840 if (i < getNumWords()) 00841 Count += CountTrailingOnes_64(pVal[i]); 00842 return std::min(Count, BitWidth); 00843 } 00844 00845 unsigned APInt::countPopulationSlowCase() const { 00846 unsigned Count = 0; 00847 for (unsigned i = 0; i < getNumWords(); ++i) 00848 Count += CountPopulation_64(pVal[i]); 00849 return Count; 00850 } 00851 00852 APInt APInt::byteSwap() const { 00853 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!"); 00854 if (BitWidth == 16) 00855 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL))); 00856 else if (BitWidth == 32) 00857 return APInt(BitWidth, ByteSwap_32(unsigned(VAL))); 00858 else if (BitWidth == 48) { 00859 unsigned Tmp1 = unsigned(VAL >> 16); 00860 Tmp1 = ByteSwap_32(Tmp1); 00861 uint16_t Tmp2 = uint16_t(VAL); 00862 Tmp2 = ByteSwap_16(Tmp2); 00863 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1); 00864 } else if (BitWidth == 64) 00865 return APInt(BitWidth, ByteSwap_64(VAL)); 00866 else { 00867 APInt Result(BitWidth, 0); 00868 char *pByte = (char*)Result.pVal; 00869 for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) { 00870 char Tmp = pByte[i]; 00871 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i]; 00872 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp; 00873 } 00874 return Result; 00875 } 00876 } 00877 00878 APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1, 00879 const APInt& API2) { 00880 APInt A = API1, B = API2; 00881 while (!!B) { 00882 APInt T = B; 00883 B = APIntOps::urem(A, B); 00884 A = T; 00885 } 00886 return A; 00887 } 00888 00889 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) { 00890 union { 00891 double D; 00892 uint64_t I; 00893 } T; 00894 T.D = Double; 00895 00896 // Get the sign bit from the highest order bit 00897 bool isNeg = T.I >> 63; 00898 00899 // Get the 11-bit exponent and adjust for the 1023 bit bias 00900 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023; 00901 00902 // If the exponent is negative, the value is < 0 so just return 0. 00903 if (exp < 0) 00904 return APInt(width, 0u); 00905 00906 // Extract the mantissa by clearing the top 12 bits (sign + exponent). 00907 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52; 00908 00909 // If the exponent doesn't shift all bits out of the mantissa 00910 if (exp < 52) 00911 return isNeg ? -APInt(width, mantissa >> (52 - exp)) : 00912 APInt(width, mantissa >> (52 - exp)); 00913 00914 // If the client didn't provide enough bits for us to shift the mantissa into 00915 // then the result is undefined, just return 0 00916 if (width <= exp - 52) 00917 return APInt(width, 0); 00918 00919 // Otherwise, we have to shift the mantissa bits up to the right location 00920 APInt Tmp(width, mantissa); 00921 Tmp = Tmp.shl((unsigned)exp - 52); 00922 return isNeg ? -Tmp : Tmp; 00923 } 00924 00925 /// RoundToDouble - This function converts this APInt to a double. 00926 /// The layout for double is as following (IEEE Standard 754): 00927 /// -------------------------------------- 00928 /// | Sign Exponent Fraction Bias | 00929 /// |-------------------------------------- | 00930 /// | 1[63] 11[62-52] 52[51-00] 1023 | 00931 /// -------------------------------------- 00932 double APInt::roundToDouble(bool isSigned) const { 00933 00934 // Handle the simple case where the value is contained in one uint64_t. 00935 // It is wrong to optimize getWord(0) to VAL; there might be more than one word. 00936 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) { 00937 if (isSigned) { 00938 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth); 00939 return double(sext); 00940 } else 00941 return double(getWord(0)); 00942 } 00943 00944 // Determine if the value is negative. 00945 bool isNeg = isSigned ? (*this)[BitWidth-1] : false; 00946 00947 // Construct the absolute value if we're negative. 00948 APInt Tmp(isNeg ? -(*this) : (*this)); 00949 00950 // Figure out how many bits we're using. 00951 unsigned n = Tmp.getActiveBits(); 00952 00953 // The exponent (without bias normalization) is just the number of bits 00954 // we are using. Note that the sign bit is gone since we constructed the 00955 // absolute value. 00956 uint64_t exp = n; 00957 00958 // Return infinity for exponent overflow 00959 if (exp > 1023) { 00960 if (!isSigned || !isNeg) 00961 return std::numeric_limits<double>::infinity(); 00962 else 00963 return -std::numeric_limits<double>::infinity(); 00964 } 00965 exp += 1023; // Increment for 1023 bias 00966 00967 // Number of bits in mantissa is 52. To obtain the mantissa value, we must 00968 // extract the high 52 bits from the correct words in pVal. 00969 uint64_t mantissa; 00970 unsigned hiWord = whichWord(n-1); 00971 if (hiWord == 0) { 00972 mantissa = Tmp.pVal[0]; 00973 if (n > 52) 00974 mantissa >>= n - 52; // shift down, we want the top 52 bits. 00975 } else { 00976 assert(hiWord > 0 && "huh?"); 00977 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD); 00978 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD); 00979 mantissa = hibits | lobits; 00980 } 00981 00982 // The leading bit of mantissa is implicit, so get rid of it. 00983 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0; 00984 union { 00985 double D; 00986 uint64_t I; 00987 } T; 00988 T.I = sign | (exp << 52) | mantissa; 00989 return T.D; 00990 } 00991 00992 // Truncate to new width. 00993 APInt &APInt::trunc(unsigned width) { 00994 assert(width < BitWidth && "Invalid APInt Truncate request"); 00995 assert(width && "Can't truncate to 0 bits"); 00996 unsigned wordsBefore = getNumWords(); 00997 BitWidth = width; 00998 unsigned wordsAfter = getNumWords(); 00999 if (wordsBefore != wordsAfter) { 01000 if (wordsAfter == 1) { 01001 uint64_t *tmp = pVal; 01002 VAL = pVal[0]; 01003 delete [] tmp; 01004 } else { 01005 uint64_t *newVal = getClearedMemory(wordsAfter); 01006 for (unsigned i = 0; i < wordsAfter; ++i) 01007 newVal[i] = pVal[i]; 01008 delete [] pVal; 01009 pVal = newVal; 01010 } 01011 } 01012 return clearUnusedBits(); 01013 } 01014 01015 // Sign extend to a new width. 01016 APInt &APInt::sext(unsigned width) { 01017 assert(width > BitWidth && "Invalid APInt SignExtend request"); 01018 // If the sign bit isn't set, this is the same as zext. 01019 if (!isNegative()) { 01020 zext(width); 01021 return *this; 01022 } 01023 01024 // The sign bit is set. First, get some facts 01025 unsigned wordsBefore = getNumWords(); 01026 unsigned wordBits = BitWidth % APINT_BITS_PER_WORD; 01027 BitWidth = width; 01028 unsigned wordsAfter = getNumWords(); 01029 01030 // Mask the high order word appropriately 01031 if (wordsBefore == wordsAfter) { 01032 unsigned newWordBits = width % APINT_BITS_PER_WORD; 01033 // The extension is contained to the wordsBefore-1th word. 01034 uint64_t mask = ~0ULL; 01035 if (newWordBits) 01036 mask >>= APINT_BITS_PER_WORD - newWordBits; 01037 mask <<= wordBits; 01038 if (wordsBefore == 1) 01039 VAL |= mask; 01040 else 01041 pVal[wordsBefore-1] |= mask; 01042 return clearUnusedBits(); 01043 } 01044 01045 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits; 01046 uint64_t *newVal = getMemory(wordsAfter); 01047 if (wordsBefore == 1) 01048 newVal[0] = VAL | mask; 01049 else { 01050 for (unsigned i = 0; i < wordsBefore; ++i) 01051 newVal[i] = pVal[i]; 01052 newVal[wordsBefore-1] |= mask; 01053 } 01054 for (unsigned i = wordsBefore; i < wordsAfter; i++) 01055 newVal[i] = -1ULL; 01056 if (wordsBefore != 1) 01057 delete [] pVal; 01058 pVal = newVal; 01059 return clearUnusedBits(); 01060 } 01061 01062 // Zero extend to a new width. 01063 APInt &APInt::zext(unsigned width) { 01064 assert(width > BitWidth && "Invalid APInt ZeroExtend request"); 01065 unsigned wordsBefore = getNumWords(); 01066 BitWidth = width; 01067 unsigned wordsAfter = getNumWords(); 01068 if (wordsBefore != wordsAfter) { 01069 uint64_t *newVal = getClearedMemory(wordsAfter); 01070 if (wordsBefore == 1) 01071 newVal[0] = VAL; 01072 else 01073 for (unsigned i = 0; i < wordsBefore; ++i) 01074 newVal[i] = pVal[i]; 01075 if (wordsBefore != 1) 01076 delete [] pVal; 01077 pVal = newVal; 01078 } 01079 return *this; 01080 } 01081 01082 APInt &APInt::zextOrTrunc(unsigned width) { 01083 if (BitWidth < width) 01084 return zext(width); 01085 if (BitWidth > width) 01086 return trunc(width); 01087 return *this; 01088 } 01089 01090 APInt &APInt::sextOrTrunc(unsigned width) { 01091 if (BitWidth < width) 01092 return sext(width); 01093 if (BitWidth > width) 01094 return trunc(width); 01095 return *this; 01096 } 01097 01098 /// Arithmetic right-shift this APInt by shiftAmt. 01099 /// @brief Arithmetic right-shift function. 01100 APInt APInt::ashr(const APInt &shiftAmt) const { 01101 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth)); 01102 } 01103 01104 /// Arithmetic right-shift this APInt by shiftAmt. 01105 /// @brief Arithmetic right-shift function. 01106 APInt APInt::ashr(unsigned shiftAmt) const { 01107 assert(shiftAmt <= BitWidth && "Invalid shift amount"); 01108 // Handle a degenerate case 01109 if (shiftAmt == 0) 01110 return *this; 01111 01112 // Handle single word shifts with built-in ashr 01113 if (isSingleWord()) { 01114 if (shiftAmt == BitWidth) 01115 return APInt(BitWidth, 0); // undefined 01116 else { 01117 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth; 01118 return APInt(BitWidth, 01119 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt)); 01120 } 01121 } 01122 01123 // If all the bits were shifted out, the result is, technically, undefined. 01124 // We return -1 if it was negative, 0 otherwise. We check this early to avoid 01125 // issues in the algorithm below. 01126 if (shiftAmt == BitWidth) { 01127 if (isNegative()) 01128 return APInt(BitWidth, -1ULL, true); 01129 else 01130 return APInt(BitWidth, 0); 01131 } 01132 01133 // Create some space for the result. 01134 uint64_t * val = new uint64_t[getNumWords()]; 01135 01136 // Compute some values needed by the following shift algorithms 01137 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word 01138 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift 01139 unsigned breakWord = getNumWords() - 1 - offset; // last word affected 01140 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word? 01141 if (bitsInWord == 0) 01142 bitsInWord = APINT_BITS_PER_WORD; 01143 01144 // If we are shifting whole words, just move whole words 01145 if (wordShift == 0) { 01146 // Move the words containing significant bits 01147 for (unsigned i = 0; i <= breakWord; ++i) 01148 val[i] = pVal[i+offset]; // move whole word 01149 01150 // Adjust the top significant word for sign bit fill, if negative 01151 if (isNegative()) 01152 if (bitsInWord < APINT_BITS_PER_WORD) 01153 val[breakWord] |= ~0ULL << bitsInWord; // set high bits 01154 } else { 01155 // Shift the low order words 01156 for (unsigned i = 0; i < breakWord; ++i) { 01157 // This combines the shifted corresponding word with the low bits from 01158 // the next word (shifted into this word's high bits). 01159 val[i] = (pVal[i+offset] >> wordShift) | 01160 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); 01161 } 01162 01163 // Shift the break word. In this case there are no bits from the next word 01164 // to include in this word. 01165 val[breakWord] = pVal[breakWord+offset] >> wordShift; 01166 01167 // Deal with sign extenstion in the break word, and possibly the word before 01168 // it. 01169 if (isNegative()) { 01170 if (wordShift > bitsInWord) { 01171 if (breakWord > 0) 01172 val[breakWord-1] |= 01173 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord)); 01174 val[breakWord] |= ~0ULL; 01175 } else 01176 val[breakWord] |= (~0ULL << (bitsInWord - wordShift)); 01177 } 01178 } 01179 01180 // Remaining words are 0 or -1, just assign them. 01181 uint64_t fillValue = (isNegative() ? -1ULL : 0); 01182 for (unsigned i = breakWord+1; i < getNumWords(); ++i) 01183 val[i] = fillValue; 01184 return APInt(val, BitWidth).clearUnusedBits(); 01185 } 01186 01187 /// Logical right-shift this APInt by shiftAmt. 01188 /// @brief Logical right-shift function. 01189 APInt APInt::lshr(const APInt &shiftAmt) const { 01190 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth)); 01191 } 01192 01193 /// Logical right-shift this APInt by shiftAmt. 01194 /// @brief Logical right-shift function. 01195 APInt APInt::lshr(unsigned shiftAmt) const { 01196 if (isSingleWord()) { 01197 if (shiftAmt == BitWidth) 01198 return APInt(BitWidth, 0); 01199 else 01200 return APInt(BitWidth, this->VAL >> shiftAmt); 01201 } 01202 01203 // If all the bits were shifted out, the result is 0. This avoids issues 01204 // with shifting by the size of the integer type, which produces undefined 01205 // results. We define these "undefined results" to always be 0. 01206 if (shiftAmt == BitWidth) 01207 return APInt(BitWidth, 0); 01208 01209 // If none of the bits are shifted out, the result is *this. This avoids 01210 // issues with shifting by the size of the integer type, which produces 01211 // undefined results in the code below. This is also an optimization. 01212 if (shiftAmt == 0) 01213 return *this; 01214 01215 // Create some space for the result. 01216 uint64_t * val = new uint64_t[getNumWords()]; 01217 01218 // If we are shifting less than a word, compute the shift with a simple carry 01219 if (shiftAmt < APINT_BITS_PER_WORD) { 01220 uint64_t carry = 0; 01221 for (int i = getNumWords()-1; i >= 0; --i) { 01222 val[i] = (pVal[i] >> shiftAmt) | carry; 01223 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt); 01224 } 01225 return APInt(val, BitWidth).clearUnusedBits(); 01226 } 01227 01228 // Compute some values needed by the remaining shift algorithms 01229 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; 01230 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; 01231 01232 // If we are shifting whole words, just move whole words 01233 if (wordShift == 0) { 01234 for (unsigned i = 0; i < getNumWords() - offset; ++i) 01235 val[i] = pVal[i+offset]; 01236 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++) 01237 val[i] = 0; 01238 return APInt(val,BitWidth).clearUnusedBits(); 01239 } 01240 01241 // Shift the low order words 01242 unsigned breakWord = getNumWords() - offset -1; 01243 for (unsigned i = 0; i < breakWord; ++i) 01244 val[i] = (pVal[i+offset] >> wordShift) | 01245 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); 01246 // Shift the break word. 01247 val[breakWord] = pVal[breakWord+offset] >> wordShift; 01248 01249 // Remaining words are 0 01250 for (unsigned i = breakWord+1; i < getNumWords(); ++i) 01251 val[i] = 0; 01252 return APInt(val, BitWidth).clearUnusedBits(); 01253 } 01254 01255 /// Left-shift this APInt by shiftAmt. 01256 /// @brief Left-shift function. 01257 APInt APInt::shl(const APInt &shiftAmt) const { 01258 // It's undefined behavior in C to shift by BitWidth or greater. 01259 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth)); 01260 } 01261 01262 APInt APInt::shlSlowCase(unsigned shiftAmt) const { 01263 // If all the bits were shifted out, the result is 0. This avoids issues 01264 // with shifting by the size of the integer type, which produces undefined 01265 // results. We define these "undefined results" to always be 0. 01266 if (shiftAmt == BitWidth) 01267 return APInt(BitWidth, 0); 01268 01269 // If none of the bits are shifted out, the result is *this. This avoids a 01270 // lshr by the words size in the loop below which can produce incorrect 01271 // results. It also avoids the expensive computation below for a common case. 01272 if (shiftAmt == 0) 01273 return *this; 01274 01275 // Create some space for the result. 01276 uint64_t * val = new uint64_t[getNumWords()]; 01277 01278 // If we are shifting less than a word, do it the easy way 01279 if (shiftAmt < APINT_BITS_PER_WORD) { 01280 uint64_t carry = 0; 01281 for (unsigned i = 0; i < getNumWords(); i++) { 01282 val[i] = pVal[i] << shiftAmt | carry; 01283 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt); 01284 } 01285 return APInt(val, BitWidth).clearUnusedBits(); 01286 } 01287 01288 // Compute some values needed by the remaining shift algorithms 01289 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; 01290 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; 01291 01292 // If we are shifting whole words, just move whole words 01293 if (wordShift == 0) { 01294 for (unsigned i = 0; i < offset; i++) 01295 val[i] = 0; 01296 for (unsigned i = offset; i < getNumWords(); i++) 01297 val[i] = pVal[i-offset]; 01298 return APInt(val,BitWidth).clearUnusedBits(); 01299 } 01300 01301 // Copy whole words from this to Result. 01302 unsigned i = getNumWords() - 1; 01303 for (; i > offset; --i) 01304 val[i] = pVal[i-offset] << wordShift | 01305 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift); 01306 val[offset] = pVal[0] << wordShift; 01307 for (i = 0; i < offset; ++i) 01308 val[i] = 0; 01309 return APInt(val, BitWidth).clearUnusedBits(); 01310 } 01311 01312 APInt APInt::rotl(const APInt &rotateAmt) const { 01313 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth)); 01314 } 01315 01316 APInt APInt::rotl(unsigned rotateAmt) const { 01317 if (rotateAmt == 0) 01318 return *this; 01319 // Don't get too fancy, just use existing shift/or facilities 01320 APInt hi(*this); 01321 APInt lo(*this); 01322 hi.shl(rotateAmt); 01323 lo.lshr(BitWidth - rotateAmt); 01324 return hi | lo; 01325 } 01326 01327 APInt APInt::rotr(const APInt &rotateAmt) const { 01328 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth)); 01329 } 01330 01331 APInt APInt::rotr(unsigned rotateAmt) const { 01332 if (rotateAmt == 0) 01333 return *this; 01334 // Don't get too fancy, just use existing shift/or facilities 01335 APInt hi(*this); 01336 APInt lo(*this); 01337 lo.lshr(rotateAmt); 01338 hi.shl(BitWidth - rotateAmt); 01339 return hi | lo; 01340 } 01341 01342 // Square Root - this method computes and returns the square root of "this". 01343 // Three mechanisms are used for computation. For small values (<= 5 bits), 01344 // a table lookup is done. This gets some performance for common cases. For 01345 // values using less than 52 bits, the value is converted to double and then 01346 // the libc sqrt function is called. The result is rounded and then converted 01347 // back to a uint64_t which is then used to construct the result. Finally, 01348 // the Babylonian method for computing square roots is used. 01349 APInt APInt::sqrt() const { 01350 01351 // Determine the magnitude of the value. 01352 unsigned magnitude = getActiveBits(); 01353 01354 // Use a fast table for some small values. This also gets rid of some 01355 // rounding errors in libc sqrt for small values. 01356 if (magnitude <= 5) { 01357 static const uint8_t results[32] = { 01358 /* 0 */ 0, 01359 /* 1- 2 */ 1, 1, 01360 /* 3- 6 */ 2, 2, 2, 2, 01361 /* 7-12 */ 3, 3, 3, 3, 3, 3, 01362 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4, 01363 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 01364 /* 31 */ 6 01365 }; 01366 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]); 01367 } 01368 01369 // If the magnitude of the value fits in less than 52 bits (the precision of 01370 // an IEEE double precision floating point value), then we can use the 01371 // libc sqrt function which will probably use a hardware sqrt computation. 01372 // This should be faster than the algorithm below. 01373 if (magnitude < 52) { 01374 #ifdef _MSC_VER 01375 // Amazingly, VC++ doesn't have round(). 01376 return APInt(BitWidth, 01377 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5); 01378 #else 01379 return APInt(BitWidth, 01380 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0]))))); 01381 #endif 01382 } 01383 01384 // Okay, all the short cuts are exhausted. We must compute it. The following 01385 // is a classical Babylonian method for computing the square root. This code 01386 // was adapted to APINt from a wikipedia article on such computations. 01387 // See http://www.wikipedia.org/ and go to the page named 01388 // Calculate_an_integer_square_root. 01389 unsigned nbits = BitWidth, i = 4; 01390 APInt testy(BitWidth, 16); 01391 APInt x_old(BitWidth, 1); 01392 APInt x_new(BitWidth, 0); 01393 APInt two(BitWidth, 2); 01394 01395 // Select a good starting value using binary logarithms. 01396 for (;; i += 2, testy = testy.shl(2)) 01397 if (i >= nbits || this->ule(testy)) { 01398 x_old = x_old.shl(i / 2); 01399 break; 01400 } 01401 01402 // Use the Babylonian method to arrive at the integer square root: 01403 for (;;) { 01404 x_new = (this->udiv(x_old) + x_old).udiv(two); 01405 if (x_old.ule(x_new)) 01406 break; 01407 x_old = x_new; 01408 } 01409 01410 // Make sure we return the closest approximation 01411 // NOTE: The rounding calculation below is correct. It will produce an 01412 // off-by-one discrepancy with results from pari/gp. That discrepancy has been 01413 // determined to be a rounding issue with pari/gp as it begins to use a 01414 // floating point representation after 192 bits. There are no discrepancies 01415 // between this algorithm and pari/gp for bit widths < 192 bits. 01416 APInt square(x_old * x_old); 01417 APInt nextSquare((x_old + 1) * (x_old +1)); 01418 if (this->ult(square)) 01419 return x_old; 01420 else if (this->ule(nextSquare)) { 01421 APInt midpoint((nextSquare - square).udiv(two)); 01422 APInt offset(*this - square); 01423 if (offset.ult(midpoint)) 01424 return x_old; 01425 else 01426 return x_old + 1; 01427 } else 01428 llvm_unreachable("Error in APInt::sqrt computation"); 01429 return x_old + 1; 01430 } 01431 01432 /// Computes the multiplicative inverse of this APInt for a given modulo. The 01433 /// iterative extended Euclidean algorithm is used to solve for this value, 01434 /// however we simplify it to speed up calculating only the inverse, and take 01435 /// advantage of div+rem calculations. We also use some tricks to avoid copying 01436 /// (potentially large) APInts around. 01437 APInt APInt::multiplicativeInverse(const APInt& modulo) const { 01438 assert(ult(modulo) && "This APInt must be smaller than the modulo"); 01439 01440 // Using the properties listed at the following web page (accessed 06/21/08): 01441 // http://www.numbertheory.org/php/euclid.html 01442 // (especially the properties numbered 3, 4 and 9) it can be proved that 01443 // BitWidth bits suffice for all the computations in the algorithm implemented 01444 // below. More precisely, this number of bits suffice if the multiplicative 01445 // inverse exists, but may not suffice for the general extended Euclidean 01446 // algorithm. 01447 01448 APInt r[2] = { modulo, *this }; 01449 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) }; 01450 APInt q(BitWidth, 0); 01451 01452 unsigned i; 01453 for (i = 0; r[i^1] != 0; i ^= 1) { 01454 // An overview of the math without the confusing bit-flipping: 01455 // q = r[i-2] / r[i-1] 01456 // r[i] = r[i-2] % r[i-1] 01457 // t[i] = t[i-2] - t[i-1] * q 01458 udivrem(r[i], r[i^1], q, r[i]); 01459 t[i] -= t[i^1] * q; 01460 } 01461 01462 // If this APInt and the modulo are not coprime, there is no multiplicative 01463 // inverse, so return 0. We check this by looking at the next-to-last 01464 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean 01465 // algorithm. 01466 if (r[i] != 1) 01467 return APInt(BitWidth, 0); 01468 01469 // The next-to-last t is the multiplicative inverse. However, we are 01470 // interested in a positive inverse. Calcuate a positive one from a negative 01471 // one if necessary. A simple addition of the modulo suffices because 01472 // abs(t[i]) is known to be less than *this/2 (see the link above). 01473 return t[i].isNegative() ? t[i] + modulo : t[i]; 01474 } 01475 01476 /// Calculate the magic numbers required to implement a signed integer division 01477 /// by a constant as a sequence of multiplies, adds and shifts. Requires that 01478 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S. 01479 /// Warren, Jr., chapter 10. 01480 APInt::ms APInt::magic() const { 01481 const APInt& d = *this; 01482 unsigned p; 01483 APInt ad, anc, delta, q1, r1, q2, r2, t; 01484 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()); 01485 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); 01486 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth()); 01487 struct ms mag; 01488 01489 ad = d.abs(); 01490 t = signedMin + (d.lshr(d.getBitWidth() - 1)); 01491 anc = t - 1 - t.urem(ad); // absolute value of nc 01492 p = d.getBitWidth() - 1; // initialize p 01493 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc) 01494 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc)) 01495 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d) 01496 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d)) 01497 do { 01498 p = p + 1; 01499 q1 = q1<<1; // update q1 = 2p/abs(nc) 01500 r1 = r1<<1; // update r1 = rem(2p/abs(nc)) 01501 if (r1.uge(anc)) { // must be unsigned comparison 01502 q1 = q1 + 1; 01503 r1 = r1 - anc; 01504 } 01505 q2 = q2<<1; // update q2 = 2p/abs(d) 01506 r2 = r2<<1; // update r2 = rem(2p/abs(d)) 01507 if (r2.uge(ad)) { // must be unsigned comparison 01508 q2 = q2 + 1; 01509 r2 = r2 - ad; 01510 } 01511 delta = ad - r2; 01512 } while (q1.ule(delta) || (q1 == delta && r1 == 0)); 01513 01514 mag.m = q2 + 1; 01515 if (d.isNegative()) mag.m = -mag.m; // resulting magic number 01516 mag.s = p - d.getBitWidth(); // resulting shift 01517 return mag; 01518 } 01519 01520 /// Calculate the magic numbers required to implement an unsigned integer 01521 /// division by a constant as a sequence of multiplies, adds and shifts. 01522 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry 01523 /// S. Warren, Jr., chapter 10. 01524 APInt::mu APInt::magicu() const { 01525 const APInt& d = *this; 01526 unsigned p; 01527 APInt nc, delta, q1, r1, q2, r2; 01528 struct mu magu; 01529 magu.a = 0; // initialize "add" indicator 01530 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()); 01531 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); 01532 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth()); 01533 01534 nc = allOnes - (-d).urem(d); 01535 p = d.getBitWidth() - 1; // initialize p 01536 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc 01537 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc) 01538 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d 01539 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d) 01540 do { 01541 p = p + 1; 01542 if (r1.uge(nc - r1)) { 01543 q1 = q1 + q1 + 1; // update q1 01544 r1 = r1 + r1 - nc; // update r1 01545 } 01546 else { 01547 q1 = q1+q1; // update q1 01548 r1 = r1+r1; // update r1 01549 } 01550 if ((r2 + 1).uge(d - r2)) { 01551 if (q2.uge(signedMax)) magu.a = 1; 01552 q2 = q2+q2 + 1; // update q2 01553 r2 = r2+r2 + 1 - d; // update r2 01554 } 01555 else { 01556 if (q2.uge(signedMin)) magu.a = 1; 01557 q2 = q2+q2; // update q2 01558 r2 = r2+r2 + 1; // update r2 01559 } 01560 delta = d - 1 - r2; 01561 } while (p < d.getBitWidth()*2 && 01562 (q1.ult(delta) || (q1 == delta && r1 == 0))); 01563 magu.m = q2 + 1; // resulting magic number 01564 magu.s = p - d.getBitWidth(); // resulting shift 01565 return magu; 01566 } 01567 01568 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers) 01569 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The 01570 /// variables here have the same names as in the algorithm. Comments explain 01571 /// the algorithm and any deviation from it. 01572 static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, 01573 unsigned m, unsigned n) { 01574 assert(u && "Must provide dividend"); 01575 assert(v && "Must provide divisor"); 01576 assert(q && "Must provide quotient"); 01577 assert(u != v && u != q && v != q && "Must us different memory"); 01578 assert(n>1 && "n must be > 1"); 01579 01580 // Knuth uses the value b as the base of the number system. In our case b 01581 // is 2^31 so we just set it to -1u. 01582 uint64_t b = uint64_t(1) << 32; 01583 01584 #if 0 01585 DEBUG(errs() << "KnuthDiv: m=" << m << " n=" << n << '\n'); 01586 DEBUG(errs() << "KnuthDiv: original:"); 01587 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]); 01588 DEBUG(errs() << " by"); 01589 DEBUG(for (int i = n; i >0; i--) errs() << " " << v[i-1]); 01590 DEBUG(errs() << '\n'); 01591 #endif 01592 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of 01593 // u and v by d. Note that we have taken Knuth's advice here to use a power 01594 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of 01595 // 2 allows us to shift instead of multiply and it is easy to determine the 01596 // shift amount from the leading zeros. We are basically normalizing the u 01597 // and v so that its high bits are shifted to the top of v's range without 01598 // overflow. Note that this can require an extra word in u so that u must 01599 // be of length m+n+1. 01600 unsigned shift = CountLeadingZeros_32(v[n-1]); 01601 unsigned v_carry = 0; 01602 unsigned u_carry = 0; 01603 if (shift) { 01604 for (unsigned i = 0; i < m+n; ++i) { 01605 unsigned u_tmp = u[i] >> (32 - shift); 01606 u[i] = (u[i] << shift) | u_carry; 01607 u_carry = u_tmp; 01608 } 01609 for (unsigned i = 0; i < n; ++i) { 01610 unsigned v_tmp = v[i] >> (32 - shift); 01611 v[i] = (v[i] << shift) | v_carry; 01612 v_carry = v_tmp; 01613 } 01614 } 01615 u[m+n] = u_carry; 01616 #if 0 01617 DEBUG(errs() << "KnuthDiv: normal:"); 01618 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]); 01619 DEBUG(errs() << " by"); 01620 DEBUG(for (int i = n; i >0; i--) errs() << " " << v[i-1]); 01621 DEBUG(errs() << '\n'); 01622 #endif 01623 01624 // D2. [Initialize j.] Set j to m. This is the loop counter over the places. 01625 int j = m; 01626 do { 01627 DEBUG(errs() << "KnuthDiv: quotient digit #" << j << '\n'); 01628 // D3. [Calculate q'.]. 01629 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q') 01630 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r') 01631 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease 01632 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test 01633 // on v[n-2] determines at high speed most of the cases in which the trial 01634 // value qp is one too large, and it eliminates all cases where qp is two 01635 // too large. 01636 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]); 01637 DEBUG(errs() << "KnuthDiv: dividend == " << dividend << '\n'); 01638 uint64_t qp = dividend / v[n-1]; 01639 uint64_t rp = dividend % v[n-1]; 01640 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) { 01641 qp--; 01642 rp += v[n-1]; 01643 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2])) 01644 qp--; 01645 } 01646 DEBUG(errs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n'); 01647 01648 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with 01649 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation 01650 // consists of a simple multiplication by a one-place number, combined with 01651 // a subtraction. 01652 bool isNeg = false; 01653 for (unsigned i = 0; i < n; ++i) { 01654 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32); 01655 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]); 01656 bool borrow = subtrahend > u_tmp; 01657 DEBUG(errs() << "KnuthDiv: u_tmp == " << u_tmp 01658 << ", subtrahend == " << subtrahend 01659 << ", borrow = " << borrow << '\n'); 01660 01661 uint64_t result = u_tmp - subtrahend; 01662 unsigned k = j + i; 01663 u[k++] = (unsigned)(result & (b-1)); // subtract low word 01664 u[k++] = (unsigned)(result >> 32); // subtract high word 01665 while (borrow && k <= m+n) { // deal with borrow to the left 01666 borrow = u[k] == 0; 01667 u[k]--; 01668 k++; 01669 } 01670 isNeg |= borrow; 01671 DEBUG(errs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " << 01672 u[j+i+1] << '\n'); 01673 } 01674 DEBUG(errs() << "KnuthDiv: after subtraction:"); 01675 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]); 01676 DEBUG(errs() << '\n'); 01677 // The digits (u[j+n]...u[j]) should be kept positive; if the result of 01678 // this step is actually negative, (u[j+n]...u[j]) should be left as the 01679 // true value plus b**(n+1), namely as the b's complement of 01680 // the true value, and a "borrow" to the left should be remembered. 01681 // 01682 if (isNeg) { 01683 bool carry = true; // true because b's complement is "complement + 1" 01684 for (unsigned i = 0; i <= m+n; ++i) { 01685 u[i] = ~u[i] + carry; // b's complement 01686 carry = carry && u[i] == 0; 01687 } 01688 } 01689 DEBUG(errs() << "KnuthDiv: after complement:"); 01690 DEBUG(for (int i = m+n; i >=0; i--) errs() << " " << u[i]); 01691 DEBUG(errs() << '\n'); 01692 01693 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was 01694 // negative, go to step D6; otherwise go on to step D7. 01695 q[j] = (unsigned)qp; 01696 if (isNeg) { 01697 // D6. [Add back]. The probability that this step is necessary is very 01698 // small, on the order of only 2/b. Make sure that test data accounts for 01699 // this possibility. Decrease q[j] by 1 01700 q[j]--; 01701 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]). 01702 // A carry will occur to the left of u[j+n], and it should be ignored 01703 // since it cancels with the borrow that occurred in D4. 01704 bool carry = false; 01705 for (unsigned i = 0; i < n; i++) { 01706 unsigned limit = std::min(u[j+i],v[i]); 01707 u[j+i] += v[i] + carry; 01708 carry = u[j+i] < limit || (carry && u[j+i] == limit); 01709 } 01710 u[j+n] += carry; 01711 } 01712 DEBUG(errs() << "KnuthDiv: after correction:"); 01713 DEBUG(for (int i = m+n; i >=0; i--) errs() <<" " << u[i]); 01714 DEBUG(errs() << "\nKnuthDiv: digit result = " << q[j] << '\n'); 01715 01716 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3. 01717 } while (--j >= 0); 01718 01719 DEBUG(errs() << "KnuthDiv: quotient:"); 01720 DEBUG(for (int i = m; i >=0; i--) errs() <<" " << q[i]); 01721 DEBUG(errs() << '\n'); 01722 01723 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired 01724 // remainder may be obtained by dividing u[...] by d. If r is non-null we 01725 // compute the remainder (urem uses this). 01726 if (r) { 01727 // The value d is expressed by the "shift" value above since we avoided 01728 // multiplication by d by using a shift left. So, all we have to do is 01729 // shift right here. In order to mak 01730 if (shift) { 01731 unsigned carry = 0; 01732 DEBUG(errs() << "KnuthDiv: remainder:"); 01733 for (int i = n-1; i >= 0; i--) { 01734 r[i] = (u[i] >> shift) | carry; 01735 carry = u[i] << (32 - shift); 01736 DEBUG(errs() << " " << r[i]); 01737 } 01738 } else { 01739 for (int i = n-1; i >= 0; i--) { 01740 r[i] = u[i]; 01741 DEBUG(errs() << " " << r[i]); 01742 } 01743 } 01744 DEBUG(errs() << '\n'); 01745 } 01746 #if 0 01747 DEBUG(errs() << '\n'); 01748 #endif 01749 } 01750 01751 void APInt::divide(const APInt LHS, unsigned lhsWords, 01752 const APInt &RHS, unsigned rhsWords, 01753 APInt *Quotient, APInt *Remainder) 01754 { 01755 assert(lhsWords >= rhsWords && "Fractional result"); 01756 01757 // First, compose the values into an array of 32-bit words instead of 01758 // 64-bit words. This is a necessity of both the "short division" algorithm 01759 // and the the Knuth "classical algorithm" which requires there to be native 01760 // operations for +, -, and * on an m bit value with an m*2 bit result. We 01761 // can't use 64-bit operands here because we don't have native results of 01762 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't 01763 // work on large-endian machines. 01764 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT); 01765 unsigned n = rhsWords * 2; 01766 unsigned m = (lhsWords * 2) - n; 01767 01768 // Allocate space for the temporary values we need either on the stack, if 01769 // it will fit, or on the heap if it won't. 01770 unsigned SPACE[128]; 01771 unsigned *U = 0; 01772 unsigned *V = 0; 01773 unsigned *Q = 0; 01774 unsigned *R = 0; 01775 if ((Remainder?4:3)*n+2*m+1 <= 128) { 01776 U = &SPACE[0]; 01777 V = &SPACE[m+n+1]; 01778 Q = &SPACE[(m+n+1) + n]; 01779 if (Remainder) 01780 R = &SPACE[(m+n+1) + n + (m+n)]; 01781 } else { 01782 U = new unsigned[m + n + 1]; 01783 V = new unsigned[n]; 01784 Q = new unsigned[m+n]; 01785 if (Remainder) 01786 R = new unsigned[n]; 01787 } 01788 01789 // Initialize the dividend 01790 memset(U, 0, (m+n+1)*sizeof(unsigned)); 01791 for (unsigned i = 0; i < lhsWords; ++i) { 01792 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]); 01793 U[i * 2] = (unsigned)(tmp & mask); 01794 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT)); 01795 } 01796 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm. 01797 01798 // Initialize the divisor 01799 memset(V, 0, (n)*sizeof(unsigned)); 01800 for (unsigned i = 0; i < rhsWords; ++i) { 01801 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]); 01802 V[i * 2] = (unsigned)(tmp & mask); 01803 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT)); 01804 } 01805 01806 // initialize the quotient and remainder 01807 memset(Q, 0, (m+n) * sizeof(unsigned)); 01808 if (Remainder) 01809 memset(R, 0, n * sizeof(unsigned)); 01810 01811 // Now, adjust m and n for the Knuth division. n is the number of words in 01812 // the divisor. m is the number of words by which the dividend exceeds the 01813 // divisor (i.e. m+n is the length of the dividend). These sizes must not 01814 // contain any zero words or the Knuth algorithm fails. 01815 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) { 01816 n--; 01817 m++; 01818 } 01819 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--) 01820 m--; 01821 01822 // If we're left with only a single word for the divisor, Knuth doesn't work 01823 // so we implement the short division algorithm here. This is much simpler 01824 // and faster because we are certain that we can divide a 64-bit quantity 01825 // by a 32-bit quantity at hardware speed and short division is simply a 01826 // series of such operations. This is just like doing short division but we 01827 // are using base 2^32 instead of base 10. 01828 assert(n != 0 && "Divide by zero?"); 01829 if (n == 1) { 01830 unsigned divisor = V[0]; 01831 unsigned remainder = 0; 01832 for (int i = m+n-1; i >= 0; i--) { 01833 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i]; 01834 if (partial_dividend == 0) { 01835 Q[i] = 0; 01836 remainder = 0; 01837 } else if (partial_dividend < divisor) { 01838 Q[i] = 0; 01839 remainder = (unsigned)partial_dividend; 01840 } else if (partial_dividend == divisor) { 01841 Q[i] = 1; 01842 remainder = 0; 01843 } else { 01844 Q[i] = (unsigned)(partial_dividend / divisor); 01845 remainder = (unsigned)(partial_dividend - (Q[i] * divisor)); 01846 } 01847 } 01848 if (R) 01849 R[0] = remainder; 01850 } else { 01851 // Now we're ready to invoke the Knuth classical divide algorithm. In this 01852 // case n > 1. 01853 KnuthDiv(U, V, Q, R, m, n); 01854 } 01855 01856 // If the caller wants the quotient 01857 if (Quotient) { 01858 // Set up the Quotient value's memory. 01859 if (Quotient->BitWidth != LHS.BitWidth) { 01860 if (Quotient->isSingleWord()) 01861 Quotient->VAL = 0; 01862 else 01863 delete [] Quotient->pVal; 01864 Quotient->BitWidth = LHS.BitWidth; 01865 if (!Quotient->isSingleWord()) 01866 Quotient->pVal = getClearedMemory(Quotient->getNumWords()); 01867 } else 01868 Quotient->clear(); 01869 01870 // The quotient is in Q. Reconstitute the quotient into Quotient's low 01871 // order words. 01872 if (lhsWords == 1) { 01873 uint64_t tmp = 01874 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2)); 01875 if (Quotient->isSingleWord()) 01876 Quotient->VAL = tmp; 01877 else 01878 Quotient->pVal[0] = tmp; 01879 } else { 01880 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough"); 01881 for (unsigned i = 0; i < lhsWords; ++i) 01882 Quotient->pVal[i] = 01883 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2)); 01884 } 01885 } 01886 01887 // If the caller wants the remainder 01888 if (Remainder) { 01889 // Set up the Remainder value's memory. 01890 if (Remainder->BitWidth != RHS.BitWidth) { 01891 if (Remainder->isSingleWord()) 01892 Remainder->VAL = 0; 01893 else 01894 delete [] Remainder->pVal; 01895 Remainder->BitWidth = RHS.BitWidth; 01896 if (!Remainder->isSingleWord()) 01897 Remainder->pVal = getClearedMemory(Remainder->getNumWords()); 01898 } else 01899 Remainder->clear(); 01900 01901 // The remainder is in R. Reconstitute the remainder into Remainder's low 01902 // order words. 01903 if (rhsWords == 1) { 01904 uint64_t tmp = 01905 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2)); 01906 if (Remainder->isSingleWord()) 01907 Remainder->VAL = tmp; 01908 else 01909 Remainder->pVal[0] = tmp; 01910 } else { 01911 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough"); 01912 for (unsigned i = 0; i < rhsWords; ++i) 01913 Remainder->pVal[i] = 01914 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2)); 01915 } 01916 } 01917 01918 // Clean up the memory we allocated. 01919 if (U != &SPACE[0]) { 01920 delete [] U; 01921 delete [] V; 01922 delete [] Q; 01923 delete [] R; 01924 } 01925 } 01926 01927 APInt APInt::udiv(const APInt& RHS) const { 01928 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 01929 01930 // First, deal with the easy case 01931 if (isSingleWord()) { 01932 assert(RHS.VAL != 0 && "Divide by zero?"); 01933 return APInt(BitWidth, VAL / RHS.VAL); 01934 } 01935 01936 // Get some facts about the LHS and RHS number of bits and words 01937 unsigned rhsBits = RHS.getActiveBits(); 01938 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 01939 assert(rhsWords && "Divided by zero???"); 01940 unsigned lhsBits = this->getActiveBits(); 01941 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); 01942 01943 // Deal with some degenerate cases 01944 if (!lhsWords) 01945 // 0 / X ===> 0 01946 return APInt(BitWidth, 0); 01947 else if (lhsWords < rhsWords || this->ult(RHS)) { 01948 // X / Y ===> 0, iff X < Y 01949 return APInt(BitWidth, 0); 01950 } else if (*this == RHS) { 01951 // X / X ===> 1 01952 return APInt(BitWidth, 1); 01953 } else if (lhsWords == 1 && rhsWords == 1) { 01954 // All high words are zero, just use native divide 01955 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]); 01956 } 01957 01958 // We have to compute it the hard way. Invoke the Knuth divide algorithm. 01959 APInt Quotient(1,0); // to hold result. 01960 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0); 01961 return Quotient; 01962 } 01963 01964 APInt APInt::urem(const APInt& RHS) const { 01965 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 01966 if (isSingleWord()) { 01967 assert(RHS.VAL != 0 && "Remainder by zero?"); 01968 return APInt(BitWidth, VAL % RHS.VAL); 01969 } 01970 01971 // Get some facts about the LHS 01972 unsigned lhsBits = getActiveBits(); 01973 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1); 01974 01975 // Get some facts about the RHS 01976 unsigned rhsBits = RHS.getActiveBits(); 01977 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 01978 assert(rhsWords && "Performing remainder operation by zero ???"); 01979 01980 // Check the degenerate cases 01981 if (lhsWords == 0) { 01982 // 0 % Y ===> 0 01983 return APInt(BitWidth, 0); 01984 } else if (lhsWords < rhsWords || this->ult(RHS)) { 01985 // X % Y ===> X, iff X < Y 01986 return *this; 01987 } else if (*this == RHS) { 01988 // X % X == 0; 01989 return APInt(BitWidth, 0); 01990 } else if (lhsWords == 1) { 01991 // All high words are zero, just use native remainder 01992 return APInt(BitWidth, pVal[0] % RHS.pVal[0]); 01993 } 01994 01995 // We have to compute it the hard way. Invoke the Knuth divide algorithm. 01996 APInt Remainder(1,0); 01997 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder); 01998 return Remainder; 01999 } 02000 02001 void APInt::udivrem(const APInt &LHS, const APInt &RHS, 02002 APInt &Quotient, APInt &Remainder) { 02003 // Get some size facts about the dividend and divisor 02004 unsigned lhsBits = LHS.getActiveBits(); 02005 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); 02006 unsigned rhsBits = RHS.getActiveBits(); 02007 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 02008 02009 // Check the degenerate cases 02010 if (lhsWords == 0) { 02011 Quotient = 0; // 0 / Y ===> 0 02012 Remainder = 0; // 0 % Y ===> 0 02013 return; 02014 } 02015 02016 if (lhsWords < rhsWords || LHS.ult(RHS)) { 02017 Quotient = 0; // X / Y ===> 0, iff X < Y 02018 Remainder = LHS; // X % Y ===> X, iff X < Y 02019 return; 02020 } 02021 02022 if (LHS == RHS) { 02023 Quotient = 1; // X / X ===> 1 02024 Remainder = 0; // X % X ===> 0; 02025 return; 02026 } 02027 02028 if (lhsWords == 1 && rhsWords == 1) { 02029 // There is only one word to consider so use the native versions. 02030 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0]; 02031 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 02032 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue); 02033 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue); 02034 return; 02035 } 02036 02037 // Okay, lets do it the long way 02038 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder); 02039 } 02040 02041 void APInt::fromString(unsigned numbits, const StringRef& str, uint8_t radix) { 02042 // Check our assumptions here 02043 assert(!str.empty() && "Invalid string length"); 02044 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && 02045 "Radix should be 2, 8, 10, or 16!"); 02046 02047 StringRef::iterator p = str.begin(); 02048 size_t slen = str.size(); 02049 bool isNeg = *p == '-'; 02050 if (*p == '-' || *p == '+') { 02051 p++; 02052 slen--; 02053 assert(slen && "String is only a sign, needs a value."); 02054 } 02055 assert((slen <= numbits || radix != 2) && "Insufficient bit width"); 02056 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width"); 02057 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width"); 02058 assert((((slen-1)*64)/22 <= numbits || radix != 10) 02059 && "Insufficient bit width"); 02060 02061 // Allocate memory 02062 if (!isSingleWord()) 02063 pVal = getClearedMemory(getNumWords()); 02064 02065 // Figure out if we can shift instead of multiply 02066 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0); 02067 02068 // Set up an APInt for the digit to add outside the loop so we don't 02069 // constantly construct/destruct it. 02070 APInt apdigit(getBitWidth(), 0); 02071 APInt apradix(getBitWidth(), radix); 02072 02073 // Enter digit traversal loop 02074 for (StringRef::iterator e = str.end(); p != e; ++p) { 02075 unsigned digit = getDigit(*p, radix); 02076 assert(digit < radix && "Invalid character in digit string"); 02077 02078 // Shift or multiply the value by the radix 02079 if (slen > 1) { 02080 if (shift) 02081 *this <<= shift; 02082 else 02083 *this *= apradix; 02084 } 02085 02086 // Add in the digit we just interpreted 02087 if (apdigit.isSingleWord()) 02088 apdigit.VAL = digit; 02089 else 02090 apdigit.pVal[0] = digit; 02091 *this += apdigit; 02092 } 02093 // If its negative, put it in two's complement form 02094 if (isNeg) { 02095 (*this)--; 02096 this->flip(); 02097 } 02098 } 02099 02100 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix, 02101 bool Signed) const { 02102 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) && 02103 "Radix should be 2, 8, 10, or 16!"); 02104 02105 // First, check for a zero value and just short circuit the logic below. 02106 if (*this == 0) { 02107 Str.push_back('0'); 02108 return; 02109 } 02110 02111 static const char Digits[] = "0123456789ABCDEF"; 02112 02113 if (isSingleWord()) { 02114 char Buffer[65]; 02115 char *BufPtr = Buffer+65; 02116 02117 uint64_t N; 02118 if (Signed) { 02119 int64_t I = getSExtValue(); 02120 if (I < 0) { 02121 Str.push_back('-'); 02122 I = -I; 02123 } 02124 N = I; 02125 } else { 02126 N = getZExtValue(); 02127 } 02128 02129 while (N) { 02130 *--BufPtr = Digits[N % Radix]; 02131 N /= Radix; 02132 } 02133 Str.append(BufPtr, Buffer+65); 02134 return; 02135 } 02136 02137 APInt Tmp(*this); 02138 02139 if (Signed && isNegative()) { 02140 // They want to print the signed version and it is a negative value 02141 // Flip the bits and add one to turn it into the equivalent positive 02142 // value and put a '-' in the result. 02143 Tmp.flip(); 02144 Tmp++; 02145 Str.push_back('-'); 02146 } 02147 02148 // We insert the digits backward, then reverse them to get the right order. 02149 unsigned StartDig = Str.size(); 02150 02151 // For the 2, 8 and 16 bit cases, we can just shift instead of divide 02152 // because the number of bits per digit (1, 3 and 4 respectively) divides 02153 // equaly. We just shift until the value is zero. 02154 if (Radix != 10) { 02155 // Just shift tmp right for each digit width until it becomes zero 02156 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1)); 02157 unsigned MaskAmt = Radix - 1; 02158 02159 while (Tmp != 0) { 02160 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt; 02161 Str.push_back(Digits[Digit]); 02162 Tmp = Tmp.lshr(ShiftAmt); 02163 } 02164 } else { 02165 APInt divisor(4, 10); 02166 while (Tmp != 0) { 02167 APInt APdigit(1, 0); 02168 APInt tmp2(Tmp.getBitWidth(), 0); 02169 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2, 02170 &APdigit); 02171 unsigned Digit = (unsigned)APdigit.getZExtValue(); 02172 assert(Digit < Radix && "divide failed"); 02173 Str.push_back(Digits[Digit]); 02174 Tmp = tmp2; 02175 } 02176 } 02177 02178 // Reverse the digits before returning. 02179 std::reverse(Str.begin()+StartDig, Str.end()); 02180 } 02181 02182 /// toString - This returns the APInt as a std::string. Note that this is an 02183 /// inefficient method. It is better to pass in a SmallVector/SmallString 02184 /// to the methods above. 02185 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const { 02186 SmallString<40> S; 02187 toString(S, Radix, Signed); 02188 return S.str(); 02189 } 02190 02191 02192 void APInt::dump() const { 02193 SmallString<40> S, U; 02194 this->toStringUnsigned(U); 02195 this->toStringSigned(S); 02196 errs() << "APInt(" << BitWidth << "b, " 02197 << U.str() << "u " << S.str() << "s)"; 02198 } 02199 02200 void APInt::print(raw_ostream &OS, bool isSigned) const { 02201 SmallString<40> S; 02202 this->toString(S, 10, isSigned); 02203 OS << S.str(); 02204 } 02205 02206 std::ostream &llvm::operator<<(std::ostream &o, const APInt &I) { 02207 raw_os_ostream OS(o); 02208 OS << I; 02209 return o; 02210 } 02211 02212 // This implements a variety of operations on a representation of 02213 // arbitrary precision, two's-complement, bignum integer values. 02214 02215 /* Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe 02216 and unrestricting assumption. */ 02217 #define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1] 02218 COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0); 02219 02220 /* Some handy functions local to this file. */ 02221 namespace { 02222 02223 /* Returns the integer part with the least significant BITS set. 02224 BITS cannot be zero. */ 02225 static inline integerPart 02226 lowBitMask(unsigned int bits) 02227 { 02228 assert (bits != 0 && bits <= integerPartWidth); 02229 02230 return ~(integerPart) 0 >> (integerPartWidth - bits); 02231 } 02232 02233 /* Returns the value of the lower half of PART. */ 02234 static inline integerPart 02235 lowHalf(integerPart part) 02236 { 02237 return part & lowBitMask(integerPartWidth / 2); 02238 } 02239 02240 /* Returns the value of the upper half of PART. */ 02241 static inline integerPart 02242 highHalf(integerPart part) 02243 { 02244 return part >> (integerPartWidth / 2); 02245 } 02246 02247 /* Returns the bit number of the most significant set bit of a part. 02248 If the input number has no bits set -1U is returned. */ 02249 static unsigned int 02250 partMSB(integerPart value) 02251 { 02252 unsigned int n, msb; 02253 02254 if (value == 0) 02255 return -1U; 02256 02257 n = integerPartWidth / 2; 02258 02259 msb = 0; 02260 do { 02261 if (value >> n) { 02262 value >>= n; 02263 msb += n; 02264 } 02265 02266 n >>= 1; 02267 } while (n); 02268 02269 return msb; 02270 } 02271 02272 /* Returns the bit number of the least significant set bit of a 02273 part. If the input number has no bits set -1U is returned. */ 02274 static unsigned int 02275 partLSB(integerPart value) 02276 { 02277 unsigned int n, lsb; 02278 02279 if (value == 0) 02280 return -1U; 02281 02282 lsb = integerPartWidth - 1; 02283 n = integerPartWidth / 2; 02284 02285 do { 02286 if (value << n) { 02287 value <<= n; 02288 lsb -= n; 02289 } 02290 02291 n >>= 1; 02292 } while (n); 02293 02294 return lsb; 02295 } 02296 } 02297 02298 /* Sets the least significant part of a bignum to the input value, and 02299 zeroes out higher parts. */ 02300 void 02301 APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts) 02302 { 02303 unsigned int i; 02304 02305 assert (parts > 0); 02306 02307 dst[0] = part; 02308 for(i = 1; i < parts; i++) 02309 dst[i] = 0; 02310 } 02311 02312 /* Assign one bignum to another. */ 02313 void 02314 APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts) 02315 { 02316 unsigned int i; 02317 02318 for(i = 0; i < parts; i++) 02319 dst[i] = src[i]; 02320 } 02321 02322 /* Returns true if a bignum is zero, false otherwise. */ 02323 bool 02324 APInt::tcIsZero(const integerPart *src, unsigned int parts) 02325 { 02326 unsigned int i; 02327 02328 for(i = 0; i < parts; i++) 02329 if (src[i]) 02330 return false; 02331 02332 return true; 02333 } 02334 02335 /* Extract the given bit of a bignum; returns 0 or 1. */ 02336 int 02337 APInt::tcExtractBit(const integerPart *parts, unsigned int bit) 02338 { 02339 return(parts[bit / integerPartWidth] 02340 & ((integerPart) 1 << bit % integerPartWidth)) != 0; 02341 } 02342 02343 /* Set the given bit of a bignum. */ 02344 void 02345 APInt::tcSetBit(integerPart *parts, unsigned int bit) 02346 { 02347 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth); 02348 } 02349 02350 /* Returns the bit number of the least significant set bit of a 02351 number. If the input number has no bits set -1U is returned. */ 02352 unsigned int 02353 APInt::tcLSB(const integerPart *parts, unsigned int n) 02354 { 02355 unsigned int i, lsb; 02356 02357 for(i = 0; i < n; i++) { 02358 if (parts[i] != 0) { 02359 lsb = partLSB(parts[i]); 02360 02361 return lsb + i * integerPartWidth; 02362 } 02363 } 02364 02365 return -1U; 02366 } 02367 02368 /* Returns the bit number of the most significant set bit of a number. 02369 If the input number has no bits set -1U is returned. */ 02370 unsigned int 02371 APInt::tcMSB(const integerPart *parts, unsigned int n) 02372 { 02373 unsigned int msb; 02374 02375 do { 02376 --n; 02377 02378 if (parts[n] != 0) { 02379 msb = partMSB(parts[n]); 02380 02381 return msb + n * integerPartWidth; 02382 } 02383 } while (n); 02384 02385 return -1U; 02386 } 02387 02388 /* Copy the bit vector of width srcBITS from SRC, starting at bit 02389 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes 02390 the least significant bit of DST. All high bits above srcBITS in 02391 DST are zero-filled. */ 02392 void 02393 APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src, 02394 unsigned int srcBits, unsigned int srcLSB) 02395 { 02396 unsigned int firstSrcPart, dstParts, shift, n; 02397 02398 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth; 02399 assert (dstParts <= dstCount); 02400 02401 firstSrcPart = srcLSB / integerPartWidth; 02402 tcAssign (dst, src + firstSrcPart, dstParts); 02403 02404 shift = srcLSB % integerPartWidth; 02405 tcShiftRight (dst, dstParts, shift); 02406 02407 /* We now have (dstParts * integerPartWidth - shift) bits from SRC 02408 in DST. If this is less that srcBits, append the rest, else 02409 clear the high bits. */ 02410 n = dstParts * integerPartWidth - shift; 02411 if (n < srcBits) { 02412 integerPart mask = lowBitMask (srcBits - n); 02413 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask) 02414 << n % integerPartWidth); 02415 } else if (n > srcBits) { 02416 if (srcBits % integerPartWidth) 02417 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth); 02418 } 02419 02420 /* Clear high parts. */ 02421 while (dstParts < dstCount) 02422 dst[dstParts++] = 0; 02423 } 02424 02425 /* DST += RHS + C where C is zero or one. Returns the carry flag. */ 02426 integerPart 02427 APInt::tcAdd(integerPart *dst, const integerPart *rhs, 02428 integerPart c, unsigned int parts) 02429 { 02430 unsigned int i; 02431 02432 assert(c <= 1); 02433 02434 for(i = 0; i < parts; i++) { 02435 integerPart l; 02436 02437 l = dst[i]; 02438 if (c) { 02439 dst[i] += rhs[i] + 1; 02440 c = (dst[i] <= l); 02441 } else { 02442 dst[i] += rhs[i]; 02443 c = (dst[i] < l); 02444 } 02445 } 02446 02447 return c; 02448 } 02449 02450 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */ 02451 integerPart 02452 APInt::tcSubtract(integerPart *dst, const integerPart *rhs, 02453 integerPart c, unsigned int parts) 02454 { 02455 unsigned int i; 02456 02457 assert(c <= 1); 02458 02459 for(i = 0; i < parts; i++) { 02460 integerPart l; 02461 02462 l = dst[i]; 02463 if (c) { 02464 dst[i] -= rhs[i] + 1; 02465 c = (dst[i] >= l); 02466 } else { 02467 dst[i] -= rhs[i]; 02468 c = (dst[i] > l); 02469 } 02470 } 02471 02472 return c; 02473 } 02474 02475 /* Negate a bignum in-place. */ 02476 void 02477 APInt::tcNegate(integerPart *dst, unsigned int parts) 02478 { 02479 tcComplement(dst, parts); 02480 tcIncrement(dst, parts); 02481 } 02482 02483 /* DST += SRC * MULTIPLIER + CARRY if add is true 02484 DST = SRC * MULTIPLIER + CARRY if add is false 02485 02486 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC 02487 they must start at the same point, i.e. DST == SRC. 02488 02489 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is 02490 returned. Otherwise DST is filled with the least significant 02491 DSTPARTS parts of the result, and if all of the omitted higher 02492 parts were zero return zero, otherwise overflow occurred and 02493 return one. */ 02494 int 02495 APInt::tcMultiplyPart(integerPart *dst, const integerPart *src, 02496 integerPart multiplier, integerPart carry, 02497 unsigned int srcParts, unsigned int dstParts, 02498 bool add) 02499 { 02500 unsigned int i, n; 02501 02502 /* Otherwise our writes of DST kill our later reads of SRC. */ 02503 assert(dst <= src || dst >= src + srcParts); 02504 assert(dstParts <= srcParts + 1); 02505 02506 /* N loops; minimum of dstParts and srcParts. */ 02507 n = dstParts < srcParts ? dstParts: srcParts; 02508 02509 for(i = 0; i < n; i++) { 02510 integerPart low, mid, high, srcPart; 02511 02512 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY. 02513 02514 This cannot overflow, because 02515 02516 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1) 02517 02518 which is less than n^2. */ 02519 02520 srcPart = src[i]; 02521 02522 if (multiplier == 0 || srcPart == 0) { 02523 low = carry; 02524 high = 0; 02525 } else { 02526 low = lowHalf(srcPart) * lowHalf(multiplier); 02527 high = highHalf(srcPart) * highHalf(multiplier); 02528 02529 mid = lowHalf(srcPart) * highHalf(multiplier); 02530 high += highHalf(mid); 02531 mid <<= integerPartWidth / 2; 02532 if (low + mid < low) 02533 high++; 02534 low += mid; 02535 02536 mid = highHalf(srcPart) * lowHalf(multiplier); 02537 high += highHalf(mid); 02538 mid <<= integerPartWidth / 2; 02539 if (low + mid < low) 02540 high++; 02541 low += mid; 02542 02543 /* Now add carry. */ 02544 if (low + carry < low) 02545 high++; 02546 low += carry; 02547 } 02548 02549 if (add) { 02550 /* And now DST[i], and store the new low part there. */ 02551 if (low + dst[i] < low) 02552 high++; 02553 dst[i] += low; 02554 } else 02555 dst[i] = low; 02556 02557 carry = high; 02558 } 02559 02560 if (i < dstParts) { 02561 /* Full multiplication, there is no overflow. */ 02562 assert(i + 1 == dstParts); 02563 dst[i] = carry; 02564 return 0; 02565 } else { 02566 /* We overflowed if there is carry. */ 02567 if (carry) 02568 return 1; 02569 02570 /* We would overflow if any significant unwritten parts would be 02571 non-zero. This is true if any remaining src parts are non-zero 02572 and the multiplier is non-zero. */ 02573 if (multiplier) 02574 for(; i < srcParts; i++) 02575 if (src[i]) 02576 return 1; 02577 02578 /* We fitted in the narrow destination. */ 02579 return 0; 02580 } 02581 } 02582 02583 /* DST = LHS * RHS, where DST has the same width as the operands and 02584 is filled with the least significant parts of the result. Returns 02585 one if overflow occurred, otherwise zero. DST must be disjoint 02586 from both operands. */ 02587 int 02588 APInt::tcMultiply(integerPart *dst, const integerPart *lhs, 02589 const integerPart *rhs, unsigned int parts) 02590 { 02591 unsigned int i; 02592 int overflow; 02593 02594 assert(dst != lhs && dst != rhs); 02595 02596 overflow = 0; 02597 tcSet(dst, 0, parts); 02598 02599 for(i = 0; i < parts; i++) 02600 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, 02601 parts - i, true); 02602 02603 return overflow; 02604 } 02605 02606 /* DST = LHS * RHS, where DST has width the sum of the widths of the 02607 operands. No overflow occurs. DST must be disjoint from both 02608 operands. Returns the number of parts required to hold the 02609 result. */ 02610 unsigned int 02611 APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs, 02612 const integerPart *rhs, unsigned int lhsParts, 02613 unsigned int rhsParts) 02614 { 02615 /* Put the narrower number on the LHS for less loops below. */ 02616 if (lhsParts > rhsParts) { 02617 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts); 02618 } else { 02619 unsigned int n; 02620 02621 assert(dst != lhs && dst != rhs); 02622 02623 tcSet(dst, 0, rhsParts); 02624 02625 for(n = 0; n < lhsParts; n++) 02626 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true); 02627 02628 n = lhsParts + rhsParts; 02629 02630 return n - (dst[n - 1] == 0); 02631 } 02632 } 02633 02634 /* If RHS is zero LHS and REMAINDER are left unchanged, return one. 02635 Otherwise set LHS to LHS / RHS with the fractional part discarded, 02636 set REMAINDER to the remainder, return zero. i.e. 02637 02638 OLD_LHS = RHS * LHS + REMAINDER 02639 02640 SCRATCH is a bignum of the same size as the operands and result for 02641 use by the routine; its contents need not be initialized and are 02642 destroyed. LHS, REMAINDER and SCRATCH must be distinct. 02643 */ 02644 int 02645 APInt::tcDivide(integerPart *lhs, const integerPart *rhs, 02646 integerPart *remainder, integerPart *srhs, 02647 unsigned int parts) 02648 { 02649 unsigned int n, shiftCount; 02650 integerPart mask; 02651 02652 assert(lhs != remainder && lhs != srhs && remainder != srhs); 02653 02654 shiftCount = tcMSB(rhs, parts) + 1; 02655 if (shiftCount == 0) 02656 return true; 02657 02658 shiftCount = parts * integerPartWidth - shiftCount; 02659 n = shiftCount / integerPartWidth; 02660 mask = (integerPart) 1 << (shiftCount % integerPartWidth); 02661 02662 tcAssign(srhs, rhs, parts); 02663 tcShiftLeft(srhs, parts, shiftCount); 02664 tcAssign(remainder, lhs, parts); 02665 tcSet(lhs, 0, parts); 02666 02667 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to 02668 the total. */ 02669 for(;;) { 02670 int compare; 02671 02672 compare = tcCompare(remainder, srhs, parts); 02673 if (compare >= 0) { 02674 tcSubtract(remainder, srhs, 0, parts); 02675 lhs[n] |= mask; 02676 } 02677 02678 if (shiftCount == 0) 02679 break; 02680 shiftCount--; 02681 tcShiftRight(srhs, parts, 1); 02682 if ((mask >>= 1) == 0) 02683 mask = (integerPart) 1 << (integerPartWidth - 1), n--; 02684 } 02685 02686 return false; 02687 } 02688 02689 /* Shift a bignum left COUNT bits in-place. Shifted in bits are zero. 02690 There are no restrictions on COUNT. */ 02691 void 02692 APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count) 02693 { 02694 if (count) { 02695 unsigned int jump, shift; 02696 02697 /* Jump is the inter-part jump; shift is is intra-part shift. */ 02698 jump = count / integerPartWidth; 02699 shift = count % integerPartWidth; 02700 02701 while (parts > jump) { 02702 integerPart part; 02703 02704 parts--; 02705 02706 /* dst[i] comes from the two parts src[i - jump] and, if we have 02707 an intra-part shift, src[i - jump - 1]. */ 02708 part = dst[parts - jump]; 02709 if (shift) { 02710 part <<= shift; 02711 if (parts >= jump + 1) 02712 part |= dst[parts - jump - 1] >> (integerPartWidth - shift); 02713 } 02714 02715 dst[parts] = part; 02716 } 02717 02718 while (parts > 0) 02719 dst[--parts] = 0; 02720 } 02721 } 02722 02723 /* Shift a bignum right COUNT bits in-place. Shifted in bits are 02724 zero. There are no restrictions on COUNT. */ 02725 void 02726 APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count) 02727 { 02728 if (count) { 02729 unsigned int i, jump, shift; 02730 02731 /* Jump is the inter-part jump; shift is is intra-part shift. */ 02732 jump = count / integerPartWidth; 02733 shift = count % integerPartWidth; 02734 02735 /* Perform the shift. This leaves the most significant COUNT bits 02736 of the result at zero. */ 02737 for(i = 0; i < parts; i++) { 02738 integerPart part; 02739 02740 if (i + jump >= parts) { 02741 part = 0; 02742 } else { 02743 part = dst[i + jump]; 02744 if (shift) { 02745 part >>= shift; 02746 if (i + jump + 1 < parts) 02747 part |= dst[i + jump + 1] << (integerPartWidth - shift); 02748 } 02749 } 02750 02751 dst[i] = part; 02752 } 02753 } 02754 } 02755 02756 /* Bitwise and of two bignums. */ 02757 void 02758 APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts) 02759 { 02760 unsigned int i; 02761 02762 for(i = 0; i < parts; i++) 02763 dst[i] &= rhs[i]; 02764 } 02765 02766 /* Bitwise inclusive or of two bignums. */ 02767 void 02768 APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts) 02769 { 02770 unsigned int i; 02771 02772 for(i = 0; i < parts; i++) 02773 dst[i] |= rhs[i]; 02774 } 02775 02776 /* Bitwise exclusive or of two bignums. */ 02777 void 02778 APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts) 02779 { 02780 unsigned int i; 02781 02782 for(i = 0; i < parts; i++) 02783 dst[i] ^= rhs[i]; 02784 } 02785 02786 /* Complement a bignum in-place. */ 02787 void 02788 APInt::tcComplement(integerPart *dst, unsigned int parts) 02789 { 02790 unsigned int i; 02791 02792 for(i = 0; i < parts; i++) 02793 dst[i] = ~dst[i]; 02794 } 02795 02796 /* Comparison (unsigned) of two bignums. */ 02797 int 02798 APInt::tcCompare(const integerPart *lhs, const integerPart *rhs, 02799 unsigned int parts) 02800 { 02801 while (parts) { 02802 parts--; 02803 if (lhs[parts] == rhs[parts]) 02804 continue; 02805 02806 if (lhs[parts] > rhs[parts]) 02807 return 1; 02808 else 02809 return -1; 02810 } 02811 02812 return 0; 02813 } 02814 02815 /* Increment a bignum in-place, return the carry flag. */ 02816 integerPart 02817 APInt::tcIncrement(integerPart *dst, unsigned int parts) 02818 { 02819 unsigned int i; 02820 02821 for(i = 0; i < parts; i++) 02822 if (++dst[i] != 0) 02823 break; 02824 02825 return i == parts; 02826 } 02827 02828 /* Set the least significant BITS bits of a bignum, clear the 02829 rest. */ 02830 void 02831 APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts, 02832 unsigned int bits) 02833 { 02834 unsigned int i; 02835 02836 i = 0; 02837 while (bits > integerPartWidth) { 02838 dst[i++] = ~(integerPart) 0; 02839 bits -= integerPartWidth; 02840 } 02841 02842 if (bits) 02843 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits); 02844 02845 while (i < parts) 02846 dst[i++] = 0; 02847 }