APInt.cpp revision 208599
1//===-- APInt.cpp - Implement APInt class ---------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements a class to represent arbitrary precision integer 11// constant values and provide a variety of arithmetic operations on them. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "apint" 16#include "llvm/ADT/APInt.h" 17#include "llvm/ADT/StringRef.h" 18#include "llvm/ADT/FoldingSet.h" 19#include "llvm/ADT/SmallString.h" 20#include "llvm/Support/Debug.h" 21#include "llvm/Support/ErrorHandling.h" 22#include "llvm/Support/MathExtras.h" 23#include "llvm/Support/raw_ostream.h" 24#include <cmath> 25#include <limits> 26#include <cstring> 27#include <cstdlib> 28using namespace llvm; 29 30/// A utility function for allocating memory, checking for allocation failures, 31/// and ensuring the contents are zeroed. 32inline static uint64_t* getClearedMemory(unsigned numWords) { 33 uint64_t * result = new uint64_t[numWords]; 34 assert(result && "APInt memory allocation fails!"); 35 memset(result, 0, numWords * sizeof(uint64_t)); 36 return result; 37} 38 39/// A utility function for allocating memory and checking for allocation 40/// failure. The content is not zeroed. 41inline static uint64_t* getMemory(unsigned numWords) { 42 uint64_t * result = new uint64_t[numWords]; 43 assert(result && "APInt memory allocation fails!"); 44 return result; 45} 46 47/// A utility function that converts a character to a digit. 48inline static unsigned getDigit(char cdigit, uint8_t radix) { 49 unsigned r; 50 51 if (radix == 16) { 52 r = cdigit - '0'; 53 if (r <= 9) 54 return r; 55 56 r = cdigit - 'A'; 57 if (r <= 5) 58 return r + 10; 59 60 r = cdigit - 'a'; 61 if (r <= 5) 62 return r + 10; 63 } 64 65 r = cdigit - '0'; 66 if (r < radix) 67 return r; 68 69 return -1U; 70} 71 72 73void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) { 74 pVal = getClearedMemory(getNumWords()); 75 pVal[0] = val; 76 if (isSigned && int64_t(val) < 0) 77 for (unsigned i = 1; i < getNumWords(); ++i) 78 pVal[i] = -1ULL; 79} 80 81void APInt::initSlowCase(const APInt& that) { 82 pVal = getMemory(getNumWords()); 83 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE); 84} 85 86 87APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]) 88 : BitWidth(numBits), VAL(0) { 89 assert(BitWidth && "Bitwidth too small"); 90 assert(bigVal && "Null pointer detected!"); 91 if (isSingleWord()) 92 VAL = bigVal[0]; 93 else { 94 // Get memory, cleared to 0 95 pVal = getClearedMemory(getNumWords()); 96 // Calculate the number of words to copy 97 unsigned words = std::min<unsigned>(numWords, getNumWords()); 98 // Copy the words from bigVal to pVal 99 memcpy(pVal, bigVal, words * APINT_WORD_SIZE); 100 } 101 // Make sure unused high bits are cleared 102 clearUnusedBits(); 103} 104 105APInt::APInt(unsigned numbits, const StringRef& Str, uint8_t radix) 106 : BitWidth(numbits), VAL(0) { 107 assert(BitWidth && "Bitwidth too small"); 108 fromString(numbits, Str, radix); 109} 110 111APInt& APInt::AssignSlowCase(const APInt& RHS) { 112 // Don't do anything for X = X 113 if (this == &RHS) 114 return *this; 115 116 if (BitWidth == RHS.getBitWidth()) { 117 // assume same bit-width single-word case is already handled 118 assert(!isSingleWord()); 119 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE); 120 return *this; 121 } 122 123 if (isSingleWord()) { 124 // assume case where both are single words is already handled 125 assert(!RHS.isSingleWord()); 126 VAL = 0; 127 pVal = getMemory(RHS.getNumWords()); 128 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 129 } else if (getNumWords() == RHS.getNumWords()) 130 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 131 else if (RHS.isSingleWord()) { 132 delete [] pVal; 133 VAL = RHS.VAL; 134 } else { 135 delete [] pVal; 136 pVal = getMemory(RHS.getNumWords()); 137 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 138 } 139 BitWidth = RHS.BitWidth; 140 return clearUnusedBits(); 141} 142 143APInt& APInt::operator=(uint64_t RHS) { 144 if (isSingleWord()) 145 VAL = RHS; 146 else { 147 pVal[0] = RHS; 148 memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); 149 } 150 return clearUnusedBits(); 151} 152 153/// Profile - This method 'profiles' an APInt for use with FoldingSet. 154void APInt::Profile(FoldingSetNodeID& ID) const { 155 ID.AddInteger(BitWidth); 156 157 if (isSingleWord()) { 158 ID.AddInteger(VAL); 159 return; 160 } 161 162 unsigned NumWords = getNumWords(); 163 for (unsigned i = 0; i < NumWords; ++i) 164 ID.AddInteger(pVal[i]); 165} 166 167/// add_1 - This function adds a single "digit" integer, y, to the multiple 168/// "digit" integer array, x[]. x[] is modified to reflect the addition and 169/// 1 is returned if there is a carry out, otherwise 0 is returned. 170/// @returns the carry of the addition. 171static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) { 172 for (unsigned i = 0; i < len; ++i) { 173 dest[i] = y + x[i]; 174 if (dest[i] < y) 175 y = 1; // Carry one to next digit. 176 else { 177 y = 0; // No need to carry so exit early 178 break; 179 } 180 } 181 return y; 182} 183 184/// @brief Prefix increment operator. Increments the APInt by one. 185APInt& APInt::operator++() { 186 if (isSingleWord()) 187 ++VAL; 188 else 189 add_1(pVal, pVal, getNumWords(), 1); 190 return clearUnusedBits(); 191} 192 193/// sub_1 - This function subtracts a single "digit" (64-bit word), y, from 194/// the multi-digit integer array, x[], propagating the borrowed 1 value until 195/// no further borrowing is neeeded or it runs out of "digits" in x. The result 196/// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted. 197/// In other words, if y > x then this function returns 1, otherwise 0. 198/// @returns the borrow out of the subtraction 199static bool sub_1(uint64_t x[], unsigned len, uint64_t y) { 200 for (unsigned i = 0; i < len; ++i) { 201 uint64_t X = x[i]; 202 x[i] -= y; 203 if (y > X) 204 y = 1; // We have to "borrow 1" from next "digit" 205 else { 206 y = 0; // No need to borrow 207 break; // Remaining digits are unchanged so exit early 208 } 209 } 210 return bool(y); 211} 212 213/// @brief Prefix decrement operator. Decrements the APInt by one. 214APInt& APInt::operator--() { 215 if (isSingleWord()) 216 --VAL; 217 else 218 sub_1(pVal, getNumWords(), 1); 219 return clearUnusedBits(); 220} 221 222/// add - This function adds the integer array x to the integer array Y and 223/// places the result in dest. 224/// @returns the carry out from the addition 225/// @brief General addition of 64-bit integer arrays 226static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y, 227 unsigned len) { 228 bool carry = false; 229 for (unsigned i = 0; i< len; ++i) { 230 uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x 231 dest[i] = x[i] + y[i] + carry; 232 carry = dest[i] < limit || (carry && dest[i] == limit); 233 } 234 return carry; 235} 236 237/// Adds the RHS APint to this APInt. 238/// @returns this, after addition of RHS. 239/// @brief Addition assignment operator. 240APInt& APInt::operator+=(const APInt& RHS) { 241 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 242 if (isSingleWord()) 243 VAL += RHS.VAL; 244 else { 245 add(pVal, pVal, RHS.pVal, getNumWords()); 246 } 247 return clearUnusedBits(); 248} 249 250/// Subtracts the integer array y from the integer array x 251/// @returns returns the borrow out. 252/// @brief Generalized subtraction of 64-bit integer arrays. 253static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y, 254 unsigned len) { 255 bool borrow = false; 256 for (unsigned i = 0; i < len; ++i) { 257 uint64_t x_tmp = borrow ? x[i] - 1 : x[i]; 258 borrow = y[i] > x_tmp || (borrow && x[i] == 0); 259 dest[i] = x_tmp - y[i]; 260 } 261 return borrow; 262} 263 264/// Subtracts the RHS APInt from this APInt 265/// @returns this, after subtraction 266/// @brief Subtraction assignment operator. 267APInt& APInt::operator-=(const APInt& RHS) { 268 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 269 if (isSingleWord()) 270 VAL -= RHS.VAL; 271 else 272 sub(pVal, pVal, RHS.pVal, getNumWords()); 273 return clearUnusedBits(); 274} 275 276/// Multiplies an integer array, x, by a uint64_t integer and places the result 277/// into dest. 278/// @returns the carry out of the multiplication. 279/// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer. 280static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) { 281 // Split y into high 32-bit part (hy) and low 32-bit part (ly) 282 uint64_t ly = y & 0xffffffffULL, hy = y >> 32; 283 uint64_t carry = 0; 284 285 // For each digit of x. 286 for (unsigned i = 0; i < len; ++i) { 287 // Split x into high and low words 288 uint64_t lx = x[i] & 0xffffffffULL; 289 uint64_t hx = x[i] >> 32; 290 // hasCarry - A flag to indicate if there is a carry to the next digit. 291 // hasCarry == 0, no carry 292 // hasCarry == 1, has carry 293 // hasCarry == 2, no carry and the calculation result == 0. 294 uint8_t hasCarry = 0; 295 dest[i] = carry + lx * ly; 296 // Determine if the add above introduces carry. 297 hasCarry = (dest[i] < carry) ? 1 : 0; 298 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0); 299 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) + 300 // (2^32 - 1) + 2^32 = 2^64. 301 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 302 303 carry += (lx * hy) & 0xffffffffULL; 304 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL); 305 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) + 306 (carry >> 32) + ((lx * hy) >> 32) + hx * hy; 307 } 308 return carry; 309} 310 311/// Multiplies integer array x by integer array y and stores the result into 312/// the integer array dest. Note that dest's size must be >= xlen + ylen. 313/// @brief Generalized multiplicate of integer arrays. 314static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[], 315 unsigned ylen) { 316 dest[xlen] = mul_1(dest, x, xlen, y[0]); 317 for (unsigned i = 1; i < ylen; ++i) { 318 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32; 319 uint64_t carry = 0, lx = 0, hx = 0; 320 for (unsigned j = 0; j < xlen; ++j) { 321 lx = x[j] & 0xffffffffULL; 322 hx = x[j] >> 32; 323 // hasCarry - A flag to indicate if has carry. 324 // hasCarry == 0, no carry 325 // hasCarry == 1, has carry 326 // hasCarry == 2, no carry and the calculation result == 0. 327 uint8_t hasCarry = 0; 328 uint64_t resul = carry + lx * ly; 329 hasCarry = (resul < carry) ? 1 : 0; 330 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32); 331 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 332 333 carry += (lx * hy) & 0xffffffffULL; 334 resul = (carry << 32) | (resul & 0xffffffffULL); 335 dest[i+j] += resul; 336 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+ 337 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) + 338 ((lx * hy) >> 32) + hx * hy; 339 } 340 dest[i+xlen] = carry; 341 } 342} 343 344APInt& APInt::operator*=(const APInt& RHS) { 345 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 346 if (isSingleWord()) { 347 VAL *= RHS.VAL; 348 clearUnusedBits(); 349 return *this; 350 } 351 352 // Get some bit facts about LHS and check for zero 353 unsigned lhsBits = getActiveBits(); 354 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1; 355 if (!lhsWords) 356 // 0 * X ===> 0 357 return *this; 358 359 // Get some bit facts about RHS and check for zero 360 unsigned rhsBits = RHS.getActiveBits(); 361 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1; 362 if (!rhsWords) { 363 // X * 0 ===> 0 364 clear(); 365 return *this; 366 } 367 368 // Allocate space for the result 369 unsigned destWords = rhsWords + lhsWords; 370 uint64_t *dest = getMemory(destWords); 371 372 // Perform the long multiply 373 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords); 374 375 // Copy result back into *this 376 clear(); 377 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords; 378 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE); 379 380 // delete dest array and return 381 delete[] dest; 382 return *this; 383} 384 385APInt& APInt::operator&=(const APInt& RHS) { 386 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 387 if (isSingleWord()) { 388 VAL &= RHS.VAL; 389 return *this; 390 } 391 unsigned numWords = getNumWords(); 392 for (unsigned i = 0; i < numWords; ++i) 393 pVal[i] &= RHS.pVal[i]; 394 return *this; 395} 396 397APInt& APInt::operator|=(const APInt& RHS) { 398 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 399 if (isSingleWord()) { 400 VAL |= RHS.VAL; 401 return *this; 402 } 403 unsigned numWords = getNumWords(); 404 for (unsigned i = 0; i < numWords; ++i) 405 pVal[i] |= RHS.pVal[i]; 406 return *this; 407} 408 409APInt& APInt::operator^=(const APInt& RHS) { 410 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 411 if (isSingleWord()) { 412 VAL ^= RHS.VAL; 413 this->clearUnusedBits(); 414 return *this; 415 } 416 unsigned numWords = getNumWords(); 417 for (unsigned i = 0; i < numWords; ++i) 418 pVal[i] ^= RHS.pVal[i]; 419 return clearUnusedBits(); 420} 421 422APInt APInt::AndSlowCase(const APInt& RHS) const { 423 unsigned numWords = getNumWords(); 424 uint64_t* val = getMemory(numWords); 425 for (unsigned i = 0; i < numWords; ++i) 426 val[i] = pVal[i] & RHS.pVal[i]; 427 return APInt(val, getBitWidth()); 428} 429 430APInt APInt::OrSlowCase(const APInt& RHS) const { 431 unsigned numWords = getNumWords(); 432 uint64_t *val = getMemory(numWords); 433 for (unsigned i = 0; i < numWords; ++i) 434 val[i] = pVal[i] | RHS.pVal[i]; 435 return APInt(val, getBitWidth()); 436} 437 438APInt APInt::XorSlowCase(const APInt& RHS) const { 439 unsigned numWords = getNumWords(); 440 uint64_t *val = getMemory(numWords); 441 for (unsigned i = 0; i < numWords; ++i) 442 val[i] = pVal[i] ^ RHS.pVal[i]; 443 444 // 0^0==1 so clear the high bits in case they got set. 445 return APInt(val, getBitWidth()).clearUnusedBits(); 446} 447 448bool APInt::operator !() const { 449 if (isSingleWord()) 450 return !VAL; 451 452 for (unsigned i = 0; i < getNumWords(); ++i) 453 if (pVal[i]) 454 return false; 455 return true; 456} 457 458APInt APInt::operator*(const APInt& RHS) const { 459 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 460 if (isSingleWord()) 461 return APInt(BitWidth, VAL * RHS.VAL); 462 APInt Result(*this); 463 Result *= RHS; 464 return Result.clearUnusedBits(); 465} 466 467APInt APInt::operator+(const APInt& RHS) const { 468 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 469 if (isSingleWord()) 470 return APInt(BitWidth, VAL + RHS.VAL); 471 APInt Result(BitWidth, 0); 472 add(Result.pVal, this->pVal, RHS.pVal, getNumWords()); 473 return Result.clearUnusedBits(); 474} 475 476APInt APInt::operator-(const APInt& RHS) const { 477 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 478 if (isSingleWord()) 479 return APInt(BitWidth, VAL - RHS.VAL); 480 APInt Result(BitWidth, 0); 481 sub(Result.pVal, this->pVal, RHS.pVal, getNumWords()); 482 return Result.clearUnusedBits(); 483} 484 485bool APInt::operator[](unsigned bitPosition) const { 486 return (maskBit(bitPosition) & 487 (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0; 488} 489 490bool APInt::EqualSlowCase(const APInt& RHS) const { 491 // Get some facts about the number of bits used in the two operands. 492 unsigned n1 = getActiveBits(); 493 unsigned n2 = RHS.getActiveBits(); 494 495 // If the number of bits isn't the same, they aren't equal 496 if (n1 != n2) 497 return false; 498 499 // If the number of bits fits in a word, we only need to compare the low word. 500 if (n1 <= APINT_BITS_PER_WORD) 501 return pVal[0] == RHS.pVal[0]; 502 503 // Otherwise, compare everything 504 for (int i = whichWord(n1 - 1); i >= 0; --i) 505 if (pVal[i] != RHS.pVal[i]) 506 return false; 507 return true; 508} 509 510bool APInt::EqualSlowCase(uint64_t Val) const { 511 unsigned n = getActiveBits(); 512 if (n <= APINT_BITS_PER_WORD) 513 return pVal[0] == Val; 514 else 515 return false; 516} 517 518bool APInt::ult(const APInt& RHS) const { 519 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"); 520 if (isSingleWord()) 521 return VAL < RHS.VAL; 522 523 // Get active bit length of both operands 524 unsigned n1 = getActiveBits(); 525 unsigned n2 = RHS.getActiveBits(); 526 527 // If magnitude of LHS is less than RHS, return true. 528 if (n1 < n2) 529 return true; 530 531 // If magnitude of RHS is greather than LHS, return false. 532 if (n2 < n1) 533 return false; 534 535 // If they bot fit in a word, just compare the low order word 536 if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD) 537 return pVal[0] < RHS.pVal[0]; 538 539 // Otherwise, compare all words 540 unsigned topWord = whichWord(std::max(n1,n2)-1); 541 for (int i = topWord; i >= 0; --i) { 542 if (pVal[i] > RHS.pVal[i]) 543 return false; 544 if (pVal[i] < RHS.pVal[i]) 545 return true; 546 } 547 return false; 548} 549 550bool APInt::slt(const APInt& RHS) const { 551 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"); 552 if (isSingleWord()) { 553 int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth); 554 int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth); 555 return lhsSext < rhsSext; 556 } 557 558 APInt lhs(*this); 559 APInt rhs(RHS); 560 bool lhsNeg = isNegative(); 561 bool rhsNeg = rhs.isNegative(); 562 if (lhsNeg) { 563 // Sign bit is set so perform two's complement to make it positive 564 lhs.flip(); 565 lhs++; 566 } 567 if (rhsNeg) { 568 // Sign bit is set so perform two's complement to make it positive 569 rhs.flip(); 570 rhs++; 571 } 572 573 // Now we have unsigned values to compare so do the comparison if necessary 574 // based on the negativeness of the values. 575 if (lhsNeg) 576 if (rhsNeg) 577 return lhs.ugt(rhs); 578 else 579 return true; 580 else if (rhsNeg) 581 return false; 582 else 583 return lhs.ult(rhs); 584} 585 586APInt& APInt::set(unsigned bitPosition) { 587 if (isSingleWord()) 588 VAL |= maskBit(bitPosition); 589 else 590 pVal[whichWord(bitPosition)] |= maskBit(bitPosition); 591 return *this; 592} 593 594/// Set the given bit to 0 whose position is given as "bitPosition". 595/// @brief Set a given bit to 0. 596APInt& APInt::clear(unsigned bitPosition) { 597 if (isSingleWord()) 598 VAL &= ~maskBit(bitPosition); 599 else 600 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition); 601 return *this; 602} 603 604/// @brief Toggle every bit to its opposite value. 605 606/// Toggle a given bit to its opposite value whose position is given 607/// as "bitPosition". 608/// @brief Toggles a given bit to its opposite value. 609APInt& APInt::flip(unsigned bitPosition) { 610 assert(bitPosition < BitWidth && "Out of the bit-width range!"); 611 if ((*this)[bitPosition]) clear(bitPosition); 612 else set(bitPosition); 613 return *this; 614} 615 616unsigned APInt::getBitsNeeded(const StringRef& str, uint8_t radix) { 617 assert(!str.empty() && "Invalid string length"); 618 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && 619 "Radix should be 2, 8, 10, or 16!"); 620 621 size_t slen = str.size(); 622 623 // Each computation below needs to know if it's negative. 624 StringRef::iterator p = str.begin(); 625 unsigned isNegative = *p == '-'; 626 if (*p == '-' || *p == '+') { 627 p++; 628 slen--; 629 assert(slen && "String is only a sign, needs a value."); 630 } 631 632 // For radixes of power-of-two values, the bits required is accurately and 633 // easily computed 634 if (radix == 2) 635 return slen + isNegative; 636 if (radix == 8) 637 return slen * 3 + isNegative; 638 if (radix == 16) 639 return slen * 4 + isNegative; 640 641 // This is grossly inefficient but accurate. We could probably do something 642 // with a computation of roughly slen*64/20 and then adjust by the value of 643 // the first few digits. But, I'm not sure how accurate that could be. 644 645 // Compute a sufficient number of bits that is always large enough but might 646 // be too large. This avoids the assertion in the constructor. This 647 // calculation doesn't work appropriately for the numbers 0-9, so just use 4 648 // bits in that case. 649 unsigned sufficient = slen == 1 ? 4 : slen * 64/18; 650 651 // Convert to the actual binary value. 652 APInt tmp(sufficient, StringRef(p, slen), radix); 653 654 // Compute how many bits are required. If the log is infinite, assume we need 655 // just bit. 656 unsigned log = tmp.logBase2(); 657 if (log == (unsigned)-1) { 658 return isNegative + 1; 659 } else { 660 return isNegative + log + 1; 661 } 662} 663 664// From http://www.burtleburtle.net, byBob Jenkins. 665// When targeting x86, both GCC and LLVM seem to recognize this as a 666// rotate instruction. 667#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 668 669// From http://www.burtleburtle.net, by Bob Jenkins. 670#define mix(a,b,c) \ 671 { \ 672 a -= c; a ^= rot(c, 4); c += b; \ 673 b -= a; b ^= rot(a, 6); a += c; \ 674 c -= b; c ^= rot(b, 8); b += a; \ 675 a -= c; a ^= rot(c,16); c += b; \ 676 b -= a; b ^= rot(a,19); a += c; \ 677 c -= b; c ^= rot(b, 4); b += a; \ 678 } 679 680// From http://www.burtleburtle.net, by Bob Jenkins. 681#define final(a,b,c) \ 682 { \ 683 c ^= b; c -= rot(b,14); \ 684 a ^= c; a -= rot(c,11); \ 685 b ^= a; b -= rot(a,25); \ 686 c ^= b; c -= rot(b,16); \ 687 a ^= c; a -= rot(c,4); \ 688 b ^= a; b -= rot(a,14); \ 689 c ^= b; c -= rot(b,24); \ 690 } 691 692// hashword() was adapted from http://www.burtleburtle.net, by Bob 693// Jenkins. k is a pointer to an array of uint32_t values; length is 694// the length of the key, in 32-bit chunks. This version only handles 695// keys that are a multiple of 32 bits in size. 696static inline uint32_t hashword(const uint64_t *k64, size_t length) 697{ 698 const uint32_t *k = reinterpret_cast<const uint32_t *>(k64); 699 uint32_t a,b,c; 700 701 /* Set up the internal state */ 702 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2); 703 704 /*------------------------------------------------- handle most of the key */ 705 while (length > 3) { 706 a += k[0]; 707 b += k[1]; 708 c += k[2]; 709 mix(a,b,c); 710 length -= 3; 711 k += 3; 712 } 713 714 /*------------------------------------------- handle the last 3 uint32_t's */ 715 switch (length) { /* all the case statements fall through */ 716 case 3 : c+=k[2]; 717 case 2 : b+=k[1]; 718 case 1 : a+=k[0]; 719 final(a,b,c); 720 case 0: /* case 0: nothing left to add */ 721 break; 722 } 723 /*------------------------------------------------------ report the result */ 724 return c; 725} 726 727// hashword8() was adapted from http://www.burtleburtle.net, by Bob 728// Jenkins. This computes a 32-bit hash from one 64-bit word. When 729// targeting x86 (32 or 64 bit), both LLVM and GCC compile this 730// function into about 35 instructions when inlined. 731static inline uint32_t hashword8(const uint64_t k64) 732{ 733 uint32_t a,b,c; 734 a = b = c = 0xdeadbeef + 4; 735 b += k64 >> 32; 736 a += k64 & 0xffffffff; 737 final(a,b,c); 738 return c; 739} 740#undef final 741#undef mix 742#undef rot 743 744uint64_t APInt::getHashValue() const { 745 uint64_t hash; 746 if (isSingleWord()) 747 hash = hashword8(VAL); 748 else 749 hash = hashword(pVal, getNumWords()*2); 750 return hash; 751} 752 753/// HiBits - This function returns the high "numBits" bits of this APInt. 754APInt APInt::getHiBits(unsigned numBits) const { 755 return APIntOps::lshr(*this, BitWidth - numBits); 756} 757 758/// LoBits - This function returns the low "numBits" bits of this APInt. 759APInt APInt::getLoBits(unsigned numBits) const { 760 return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits), 761 BitWidth - numBits); 762} 763 764bool APInt::isPowerOf2() const { 765 return (!!*this) && !(*this & (*this - APInt(BitWidth,1))); 766} 767 768unsigned APInt::countLeadingZerosSlowCase() const { 769 // Treat the most significand word differently because it might have 770 // meaningless bits set beyond the precision. 771 unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD; 772 integerPart MSWMask; 773 if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1; 774 else { 775 MSWMask = ~integerPart(0); 776 BitsInMSW = APINT_BITS_PER_WORD; 777 } 778 779 unsigned i = getNumWords(); 780 integerPart MSW = pVal[i-1] & MSWMask; 781 if (MSW) 782 return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW); 783 784 unsigned Count = BitsInMSW; 785 for (--i; i > 0u; --i) { 786 if (pVal[i-1] == 0) 787 Count += APINT_BITS_PER_WORD; 788 else { 789 Count += CountLeadingZeros_64(pVal[i-1]); 790 break; 791 } 792 } 793 return Count; 794} 795 796static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) { 797 unsigned Count = 0; 798 if (skip) 799 V <<= skip; 800 while (V && (V & (1ULL << 63))) { 801 Count++; 802 V <<= 1; 803 } 804 return Count; 805} 806 807unsigned APInt::countLeadingOnes() const { 808 if (isSingleWord()) 809 return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth); 810 811 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD; 812 unsigned shift; 813 if (!highWordBits) { 814 highWordBits = APINT_BITS_PER_WORD; 815 shift = 0; 816 } else { 817 shift = APINT_BITS_PER_WORD - highWordBits; 818 } 819 int i = getNumWords() - 1; 820 unsigned Count = countLeadingOnes_64(pVal[i], shift); 821 if (Count == highWordBits) { 822 for (i--; i >= 0; --i) { 823 if (pVal[i] == -1ULL) 824 Count += APINT_BITS_PER_WORD; 825 else { 826 Count += countLeadingOnes_64(pVal[i], 0); 827 break; 828 } 829 } 830 } 831 return Count; 832} 833 834unsigned APInt::countTrailingZeros() const { 835 if (isSingleWord()) 836 return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth); 837 unsigned Count = 0; 838 unsigned i = 0; 839 for (; i < getNumWords() && pVal[i] == 0; ++i) 840 Count += APINT_BITS_PER_WORD; 841 if (i < getNumWords()) 842 Count += CountTrailingZeros_64(pVal[i]); 843 return std::min(Count, BitWidth); 844} 845 846unsigned APInt::countTrailingOnesSlowCase() const { 847 unsigned Count = 0; 848 unsigned i = 0; 849 for (; i < getNumWords() && pVal[i] == -1ULL; ++i) 850 Count += APINT_BITS_PER_WORD; 851 if (i < getNumWords()) 852 Count += CountTrailingOnes_64(pVal[i]); 853 return std::min(Count, BitWidth); 854} 855 856unsigned APInt::countPopulationSlowCase() const { 857 unsigned Count = 0; 858 for (unsigned i = 0; i < getNumWords(); ++i) 859 Count += CountPopulation_64(pVal[i]); 860 return Count; 861} 862 863APInt APInt::byteSwap() const { 864 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!"); 865 if (BitWidth == 16) 866 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL))); 867 else if (BitWidth == 32) 868 return APInt(BitWidth, ByteSwap_32(unsigned(VAL))); 869 else if (BitWidth == 48) { 870 unsigned Tmp1 = unsigned(VAL >> 16); 871 Tmp1 = ByteSwap_32(Tmp1); 872 uint16_t Tmp2 = uint16_t(VAL); 873 Tmp2 = ByteSwap_16(Tmp2); 874 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1); 875 } else if (BitWidth == 64) 876 return APInt(BitWidth, ByteSwap_64(VAL)); 877 else { 878 APInt Result(BitWidth, 0); 879 char *pByte = (char*)Result.pVal; 880 for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) { 881 char Tmp = pByte[i]; 882 pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i]; 883 pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp; 884 } 885 return Result; 886 } 887} 888 889APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1, 890 const APInt& API2) { 891 APInt A = API1, B = API2; 892 while (!!B) { 893 APInt T = B; 894 B = APIntOps::urem(A, B); 895 A = T; 896 } 897 return A; 898} 899 900APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) { 901 union { 902 double D; 903 uint64_t I; 904 } T; 905 T.D = Double; 906 907 // Get the sign bit from the highest order bit 908 bool isNeg = T.I >> 63; 909 910 // Get the 11-bit exponent and adjust for the 1023 bit bias 911 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023; 912 913 // If the exponent is negative, the value is < 0 so just return 0. 914 if (exp < 0) 915 return APInt(width, 0u); 916 917 // Extract the mantissa by clearing the top 12 bits (sign + exponent). 918 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52; 919 920 // If the exponent doesn't shift all bits out of the mantissa 921 if (exp < 52) 922 return isNeg ? -APInt(width, mantissa >> (52 - exp)) : 923 APInt(width, mantissa >> (52 - exp)); 924 925 // If the client didn't provide enough bits for us to shift the mantissa into 926 // then the result is undefined, just return 0 927 if (width <= exp - 52) 928 return APInt(width, 0); 929 930 // Otherwise, we have to shift the mantissa bits up to the right location 931 APInt Tmp(width, mantissa); 932 Tmp = Tmp.shl((unsigned)exp - 52); 933 return isNeg ? -Tmp : Tmp; 934} 935 936/// RoundToDouble - This function converts this APInt to a double. 937/// The layout for double is as following (IEEE Standard 754): 938/// -------------------------------------- 939/// | Sign Exponent Fraction Bias | 940/// |-------------------------------------- | 941/// | 1[63] 11[62-52] 52[51-00] 1023 | 942/// -------------------------------------- 943double APInt::roundToDouble(bool isSigned) const { 944 945 // Handle the simple case where the value is contained in one uint64_t. 946 // It is wrong to optimize getWord(0) to VAL; there might be more than one word. 947 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) { 948 if (isSigned) { 949 int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth); 950 return double(sext); 951 } else 952 return double(getWord(0)); 953 } 954 955 // Determine if the value is negative. 956 bool isNeg = isSigned ? (*this)[BitWidth-1] : false; 957 958 // Construct the absolute value if we're negative. 959 APInt Tmp(isNeg ? -(*this) : (*this)); 960 961 // Figure out how many bits we're using. 962 unsigned n = Tmp.getActiveBits(); 963 964 // The exponent (without bias normalization) is just the number of bits 965 // we are using. Note that the sign bit is gone since we constructed the 966 // absolute value. 967 uint64_t exp = n; 968 969 // Return infinity for exponent overflow 970 if (exp > 1023) { 971 if (!isSigned || !isNeg) 972 return std::numeric_limits<double>::infinity(); 973 else 974 return -std::numeric_limits<double>::infinity(); 975 } 976 exp += 1023; // Increment for 1023 bias 977 978 // Number of bits in mantissa is 52. To obtain the mantissa value, we must 979 // extract the high 52 bits from the correct words in pVal. 980 uint64_t mantissa; 981 unsigned hiWord = whichWord(n-1); 982 if (hiWord == 0) { 983 mantissa = Tmp.pVal[0]; 984 if (n > 52) 985 mantissa >>= n - 52; // shift down, we want the top 52 bits. 986 } else { 987 assert(hiWord > 0 && "huh?"); 988 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD); 989 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD); 990 mantissa = hibits | lobits; 991 } 992 993 // The leading bit of mantissa is implicit, so get rid of it. 994 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0; 995 union { 996 double D; 997 uint64_t I; 998 } T; 999 T.I = sign | (exp << 52) | mantissa; 1000 return T.D; 1001} 1002 1003// Truncate to new width. 1004APInt &APInt::trunc(unsigned width) { 1005 assert(width < BitWidth && "Invalid APInt Truncate request"); 1006 assert(width && "Can't truncate to 0 bits"); 1007 unsigned wordsBefore = getNumWords(); 1008 BitWidth = width; 1009 unsigned wordsAfter = getNumWords(); 1010 if (wordsBefore != wordsAfter) { 1011 if (wordsAfter == 1) { 1012 uint64_t *tmp = pVal; 1013 VAL = pVal[0]; 1014 delete [] tmp; 1015 } else { 1016 uint64_t *newVal = getClearedMemory(wordsAfter); 1017 for (unsigned i = 0; i < wordsAfter; ++i) 1018 newVal[i] = pVal[i]; 1019 delete [] pVal; 1020 pVal = newVal; 1021 } 1022 } 1023 return clearUnusedBits(); 1024} 1025 1026// Sign extend to a new width. 1027APInt &APInt::sext(unsigned width) { 1028 assert(width > BitWidth && "Invalid APInt SignExtend request"); 1029 // If the sign bit isn't set, this is the same as zext. 1030 if (!isNegative()) { 1031 zext(width); 1032 return *this; 1033 } 1034 1035 // The sign bit is set. First, get some facts 1036 unsigned wordsBefore = getNumWords(); 1037 unsigned wordBits = BitWidth % APINT_BITS_PER_WORD; 1038 BitWidth = width; 1039 unsigned wordsAfter = getNumWords(); 1040 1041 // Mask the high order word appropriately 1042 if (wordsBefore == wordsAfter) { 1043 unsigned newWordBits = width % APINT_BITS_PER_WORD; 1044 // The extension is contained to the wordsBefore-1th word. 1045 uint64_t mask = ~0ULL; 1046 if (newWordBits) 1047 mask >>= APINT_BITS_PER_WORD - newWordBits; 1048 mask <<= wordBits; 1049 if (wordsBefore == 1) 1050 VAL |= mask; 1051 else 1052 pVal[wordsBefore-1] |= mask; 1053 return clearUnusedBits(); 1054 } 1055 1056 uint64_t mask = wordBits == 0 ? 0 : ~0ULL << wordBits; 1057 uint64_t *newVal = getMemory(wordsAfter); 1058 if (wordsBefore == 1) 1059 newVal[0] = VAL | mask; 1060 else { 1061 for (unsigned i = 0; i < wordsBefore; ++i) 1062 newVal[i] = pVal[i]; 1063 newVal[wordsBefore-1] |= mask; 1064 } 1065 for (unsigned i = wordsBefore; i < wordsAfter; i++) 1066 newVal[i] = -1ULL; 1067 if (wordsBefore != 1) 1068 delete [] pVal; 1069 pVal = newVal; 1070 return clearUnusedBits(); 1071} 1072 1073// Zero extend to a new width. 1074APInt &APInt::zext(unsigned width) { 1075 assert(width > BitWidth && "Invalid APInt ZeroExtend request"); 1076 unsigned wordsBefore = getNumWords(); 1077 BitWidth = width; 1078 unsigned wordsAfter = getNumWords(); 1079 if (wordsBefore != wordsAfter) { 1080 uint64_t *newVal = getClearedMemory(wordsAfter); 1081 if (wordsBefore == 1) 1082 newVal[0] = VAL; 1083 else 1084 for (unsigned i = 0; i < wordsBefore; ++i) 1085 newVal[i] = pVal[i]; 1086 if (wordsBefore != 1) 1087 delete [] pVal; 1088 pVal = newVal; 1089 } 1090 return *this; 1091} 1092 1093APInt &APInt::zextOrTrunc(unsigned width) { 1094 if (BitWidth < width) 1095 return zext(width); 1096 if (BitWidth > width) 1097 return trunc(width); 1098 return *this; 1099} 1100 1101APInt &APInt::sextOrTrunc(unsigned width) { 1102 if (BitWidth < width) 1103 return sext(width); 1104 if (BitWidth > width) 1105 return trunc(width); 1106 return *this; 1107} 1108 1109/// Arithmetic right-shift this APInt by shiftAmt. 1110/// @brief Arithmetic right-shift function. 1111APInt APInt::ashr(const APInt &shiftAmt) const { 1112 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth)); 1113} 1114 1115/// Arithmetic right-shift this APInt by shiftAmt. 1116/// @brief Arithmetic right-shift function. 1117APInt APInt::ashr(unsigned shiftAmt) const { 1118 assert(shiftAmt <= BitWidth && "Invalid shift amount"); 1119 // Handle a degenerate case 1120 if (shiftAmt == 0) 1121 return *this; 1122 1123 // Handle single word shifts with built-in ashr 1124 if (isSingleWord()) { 1125 if (shiftAmt == BitWidth) 1126 return APInt(BitWidth, 0); // undefined 1127 else { 1128 unsigned SignBit = APINT_BITS_PER_WORD - BitWidth; 1129 return APInt(BitWidth, 1130 (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt)); 1131 } 1132 } 1133 1134 // If all the bits were shifted out, the result is, technically, undefined. 1135 // We return -1 if it was negative, 0 otherwise. We check this early to avoid 1136 // issues in the algorithm below. 1137 if (shiftAmt == BitWidth) { 1138 if (isNegative()) 1139 return APInt(BitWidth, -1ULL, true); 1140 else 1141 return APInt(BitWidth, 0); 1142 } 1143 1144 // Create some space for the result. 1145 uint64_t * val = new uint64_t[getNumWords()]; 1146 1147 // Compute some values needed by the following shift algorithms 1148 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word 1149 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift 1150 unsigned breakWord = getNumWords() - 1 - offset; // last word affected 1151 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word? 1152 if (bitsInWord == 0) 1153 bitsInWord = APINT_BITS_PER_WORD; 1154 1155 // If we are shifting whole words, just move whole words 1156 if (wordShift == 0) { 1157 // Move the words containing significant bits 1158 for (unsigned i = 0; i <= breakWord; ++i) 1159 val[i] = pVal[i+offset]; // move whole word 1160 1161 // Adjust the top significant word for sign bit fill, if negative 1162 if (isNegative()) 1163 if (bitsInWord < APINT_BITS_PER_WORD) 1164 val[breakWord] |= ~0ULL << bitsInWord; // set high bits 1165 } else { 1166 // Shift the low order words 1167 for (unsigned i = 0; i < breakWord; ++i) { 1168 // This combines the shifted corresponding word with the low bits from 1169 // the next word (shifted into this word's high bits). 1170 val[i] = (pVal[i+offset] >> wordShift) | 1171 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); 1172 } 1173 1174 // Shift the break word. In this case there are no bits from the next word 1175 // to include in this word. 1176 val[breakWord] = pVal[breakWord+offset] >> wordShift; 1177 1178 // Deal with sign extenstion in the break word, and possibly the word before 1179 // it. 1180 if (isNegative()) { 1181 if (wordShift > bitsInWord) { 1182 if (breakWord > 0) 1183 val[breakWord-1] |= 1184 ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord)); 1185 val[breakWord] |= ~0ULL; 1186 } else 1187 val[breakWord] |= (~0ULL << (bitsInWord - wordShift)); 1188 } 1189 } 1190 1191 // Remaining words are 0 or -1, just assign them. 1192 uint64_t fillValue = (isNegative() ? -1ULL : 0); 1193 for (unsigned i = breakWord+1; i < getNumWords(); ++i) 1194 val[i] = fillValue; 1195 return APInt(val, BitWidth).clearUnusedBits(); 1196} 1197 1198/// Logical right-shift this APInt by shiftAmt. 1199/// @brief Logical right-shift function. 1200APInt APInt::lshr(const APInt &shiftAmt) const { 1201 return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth)); 1202} 1203 1204/// Logical right-shift this APInt by shiftAmt. 1205/// @brief Logical right-shift function. 1206APInt APInt::lshr(unsigned shiftAmt) const { 1207 if (isSingleWord()) { 1208 if (shiftAmt == BitWidth) 1209 return APInt(BitWidth, 0); 1210 else 1211 return APInt(BitWidth, this->VAL >> shiftAmt); 1212 } 1213 1214 // If all the bits were shifted out, the result is 0. This avoids issues 1215 // with shifting by the size of the integer type, which produces undefined 1216 // results. We define these "undefined results" to always be 0. 1217 if (shiftAmt == BitWidth) 1218 return APInt(BitWidth, 0); 1219 1220 // If none of the bits are shifted out, the result is *this. This avoids 1221 // issues with shifting by the size of the integer type, which produces 1222 // undefined results in the code below. This is also an optimization. 1223 if (shiftAmt == 0) 1224 return *this; 1225 1226 // Create some space for the result. 1227 uint64_t * val = new uint64_t[getNumWords()]; 1228 1229 // If we are shifting less than a word, compute the shift with a simple carry 1230 if (shiftAmt < APINT_BITS_PER_WORD) { 1231 uint64_t carry = 0; 1232 for (int i = getNumWords()-1; i >= 0; --i) { 1233 val[i] = (pVal[i] >> shiftAmt) | carry; 1234 carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt); 1235 } 1236 return APInt(val, BitWidth).clearUnusedBits(); 1237 } 1238 1239 // Compute some values needed by the remaining shift algorithms 1240 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; 1241 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; 1242 1243 // If we are shifting whole words, just move whole words 1244 if (wordShift == 0) { 1245 for (unsigned i = 0; i < getNumWords() - offset; ++i) 1246 val[i] = pVal[i+offset]; 1247 for (unsigned i = getNumWords()-offset; i < getNumWords(); i++) 1248 val[i] = 0; 1249 return APInt(val,BitWidth).clearUnusedBits(); 1250 } 1251 1252 // Shift the low order words 1253 unsigned breakWord = getNumWords() - offset -1; 1254 for (unsigned i = 0; i < breakWord; ++i) 1255 val[i] = (pVal[i+offset] >> wordShift) | 1256 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); 1257 // Shift the break word. 1258 val[breakWord] = pVal[breakWord+offset] >> wordShift; 1259 1260 // Remaining words are 0 1261 for (unsigned i = breakWord+1; i < getNumWords(); ++i) 1262 val[i] = 0; 1263 return APInt(val, BitWidth).clearUnusedBits(); 1264} 1265 1266/// Left-shift this APInt by shiftAmt. 1267/// @brief Left-shift function. 1268APInt APInt::shl(const APInt &shiftAmt) const { 1269 // It's undefined behavior in C to shift by BitWidth or greater. 1270 return shl((unsigned)shiftAmt.getLimitedValue(BitWidth)); 1271} 1272 1273APInt APInt::shlSlowCase(unsigned shiftAmt) const { 1274 // If all the bits were shifted out, the result is 0. This avoids issues 1275 // with shifting by the size of the integer type, which produces undefined 1276 // results. We define these "undefined results" to always be 0. 1277 if (shiftAmt == BitWidth) 1278 return APInt(BitWidth, 0); 1279 1280 // If none of the bits are shifted out, the result is *this. This avoids a 1281 // lshr by the words size in the loop below which can produce incorrect 1282 // results. It also avoids the expensive computation below for a common case. 1283 if (shiftAmt == 0) 1284 return *this; 1285 1286 // Create some space for the result. 1287 uint64_t * val = new uint64_t[getNumWords()]; 1288 1289 // If we are shifting less than a word, do it the easy way 1290 if (shiftAmt < APINT_BITS_PER_WORD) { 1291 uint64_t carry = 0; 1292 for (unsigned i = 0; i < getNumWords(); i++) { 1293 val[i] = pVal[i] << shiftAmt | carry; 1294 carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt); 1295 } 1296 return APInt(val, BitWidth).clearUnusedBits(); 1297 } 1298 1299 // Compute some values needed by the remaining shift algorithms 1300 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; 1301 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; 1302 1303 // If we are shifting whole words, just move whole words 1304 if (wordShift == 0) { 1305 for (unsigned i = 0; i < offset; i++) 1306 val[i] = 0; 1307 for (unsigned i = offset; i < getNumWords(); i++) 1308 val[i] = pVal[i-offset]; 1309 return APInt(val,BitWidth).clearUnusedBits(); 1310 } 1311 1312 // Copy whole words from this to Result. 1313 unsigned i = getNumWords() - 1; 1314 for (; i > offset; --i) 1315 val[i] = pVal[i-offset] << wordShift | 1316 pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift); 1317 val[offset] = pVal[0] << wordShift; 1318 for (i = 0; i < offset; ++i) 1319 val[i] = 0; 1320 return APInt(val, BitWidth).clearUnusedBits(); 1321} 1322 1323APInt APInt::rotl(const APInt &rotateAmt) const { 1324 return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth)); 1325} 1326 1327APInt APInt::rotl(unsigned rotateAmt) const { 1328 if (rotateAmt == 0) 1329 return *this; 1330 // Don't get too fancy, just use existing shift/or facilities 1331 APInt hi(*this); 1332 APInt lo(*this); 1333 hi.shl(rotateAmt); 1334 lo.lshr(BitWidth - rotateAmt); 1335 return hi | lo; 1336} 1337 1338APInt APInt::rotr(const APInt &rotateAmt) const { 1339 return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth)); 1340} 1341 1342APInt APInt::rotr(unsigned rotateAmt) const { 1343 if (rotateAmt == 0) 1344 return *this; 1345 // Don't get too fancy, just use existing shift/or facilities 1346 APInt hi(*this); 1347 APInt lo(*this); 1348 lo.lshr(rotateAmt); 1349 hi.shl(BitWidth - rotateAmt); 1350 return hi | lo; 1351} 1352 1353// Square Root - this method computes and returns the square root of "this". 1354// Three mechanisms are used for computation. For small values (<= 5 bits), 1355// a table lookup is done. This gets some performance for common cases. For 1356// values using less than 52 bits, the value is converted to double and then 1357// the libc sqrt function is called. The result is rounded and then converted 1358// back to a uint64_t which is then used to construct the result. Finally, 1359// the Babylonian method for computing square roots is used. 1360APInt APInt::sqrt() const { 1361 1362 // Determine the magnitude of the value. 1363 unsigned magnitude = getActiveBits(); 1364 1365 // Use a fast table for some small values. This also gets rid of some 1366 // rounding errors in libc sqrt for small values. 1367 if (magnitude <= 5) { 1368 static const uint8_t results[32] = { 1369 /* 0 */ 0, 1370 /* 1- 2 */ 1, 1, 1371 /* 3- 6 */ 2, 2, 2, 2, 1372 /* 7-12 */ 3, 3, 3, 3, 3, 3, 1373 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4, 1374 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1375 /* 31 */ 6 1376 }; 1377 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]); 1378 } 1379 1380 // If the magnitude of the value fits in less than 52 bits (the precision of 1381 // an IEEE double precision floating point value), then we can use the 1382 // libc sqrt function which will probably use a hardware sqrt computation. 1383 // This should be faster than the algorithm below. 1384 if (magnitude < 52) { 1385#if HAVE_ROUND 1386 return APInt(BitWidth, 1387 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0]))))); 1388#else 1389 return APInt(BitWidth, 1390 uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0]))) + 0.5); 1391#endif 1392 } 1393 1394 // Okay, all the short cuts are exhausted. We must compute it. The following 1395 // is a classical Babylonian method for computing the square root. This code 1396 // was adapted to APINt from a wikipedia article on such computations. 1397 // See http://www.wikipedia.org/ and go to the page named 1398 // Calculate_an_integer_square_root. 1399 unsigned nbits = BitWidth, i = 4; 1400 APInt testy(BitWidth, 16); 1401 APInt x_old(BitWidth, 1); 1402 APInt x_new(BitWidth, 0); 1403 APInt two(BitWidth, 2); 1404 1405 // Select a good starting value using binary logarithms. 1406 for (;; i += 2, testy = testy.shl(2)) 1407 if (i >= nbits || this->ule(testy)) { 1408 x_old = x_old.shl(i / 2); 1409 break; 1410 } 1411 1412 // Use the Babylonian method to arrive at the integer square root: 1413 for (;;) { 1414 x_new = (this->udiv(x_old) + x_old).udiv(two); 1415 if (x_old.ule(x_new)) 1416 break; 1417 x_old = x_new; 1418 } 1419 1420 // Make sure we return the closest approximation 1421 // NOTE: The rounding calculation below is correct. It will produce an 1422 // off-by-one discrepancy with results from pari/gp. That discrepancy has been 1423 // determined to be a rounding issue with pari/gp as it begins to use a 1424 // floating point representation after 192 bits. There are no discrepancies 1425 // between this algorithm and pari/gp for bit widths < 192 bits. 1426 APInt square(x_old * x_old); 1427 APInt nextSquare((x_old + 1) * (x_old +1)); 1428 if (this->ult(square)) 1429 return x_old; 1430 else if (this->ule(nextSquare)) { 1431 APInt midpoint((nextSquare - square).udiv(two)); 1432 APInt offset(*this - square); 1433 if (offset.ult(midpoint)) 1434 return x_old; 1435 else 1436 return x_old + 1; 1437 } else 1438 llvm_unreachable("Error in APInt::sqrt computation"); 1439 return x_old + 1; 1440} 1441 1442/// Computes the multiplicative inverse of this APInt for a given modulo. The 1443/// iterative extended Euclidean algorithm is used to solve for this value, 1444/// however we simplify it to speed up calculating only the inverse, and take 1445/// advantage of div+rem calculations. We also use some tricks to avoid copying 1446/// (potentially large) APInts around. 1447APInt APInt::multiplicativeInverse(const APInt& modulo) const { 1448 assert(ult(modulo) && "This APInt must be smaller than the modulo"); 1449 1450 // Using the properties listed at the following web page (accessed 06/21/08): 1451 // http://www.numbertheory.org/php/euclid.html 1452 // (especially the properties numbered 3, 4 and 9) it can be proved that 1453 // BitWidth bits suffice for all the computations in the algorithm implemented 1454 // below. More precisely, this number of bits suffice if the multiplicative 1455 // inverse exists, but may not suffice for the general extended Euclidean 1456 // algorithm. 1457 1458 APInt r[2] = { modulo, *this }; 1459 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) }; 1460 APInt q(BitWidth, 0); 1461 1462 unsigned i; 1463 for (i = 0; r[i^1] != 0; i ^= 1) { 1464 // An overview of the math without the confusing bit-flipping: 1465 // q = r[i-2] / r[i-1] 1466 // r[i] = r[i-2] % r[i-1] 1467 // t[i] = t[i-2] - t[i-1] * q 1468 udivrem(r[i], r[i^1], q, r[i]); 1469 t[i] -= t[i^1] * q; 1470 } 1471 1472 // If this APInt and the modulo are not coprime, there is no multiplicative 1473 // inverse, so return 0. We check this by looking at the next-to-last 1474 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean 1475 // algorithm. 1476 if (r[i] != 1) 1477 return APInt(BitWidth, 0); 1478 1479 // The next-to-last t is the multiplicative inverse. However, we are 1480 // interested in a positive inverse. Calcuate a positive one from a negative 1481 // one if necessary. A simple addition of the modulo suffices because 1482 // abs(t[i]) is known to be less than *this/2 (see the link above). 1483 return t[i].isNegative() ? t[i] + modulo : t[i]; 1484} 1485 1486/// Calculate the magic numbers required to implement a signed integer division 1487/// by a constant as a sequence of multiplies, adds and shifts. Requires that 1488/// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S. 1489/// Warren, Jr., chapter 10. 1490APInt::ms APInt::magic() const { 1491 const APInt& d = *this; 1492 unsigned p; 1493 APInt ad, anc, delta, q1, r1, q2, r2, t; 1494 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); 1495 struct ms mag; 1496 1497 ad = d.abs(); 1498 t = signedMin + (d.lshr(d.getBitWidth() - 1)); 1499 anc = t - 1 - t.urem(ad); // absolute value of nc 1500 p = d.getBitWidth() - 1; // initialize p 1501 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc) 1502 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc)) 1503 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d) 1504 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d)) 1505 do { 1506 p = p + 1; 1507 q1 = q1<<1; // update q1 = 2p/abs(nc) 1508 r1 = r1<<1; // update r1 = rem(2p/abs(nc)) 1509 if (r1.uge(anc)) { // must be unsigned comparison 1510 q1 = q1 + 1; 1511 r1 = r1 - anc; 1512 } 1513 q2 = q2<<1; // update q2 = 2p/abs(d) 1514 r2 = r2<<1; // update r2 = rem(2p/abs(d)) 1515 if (r2.uge(ad)) { // must be unsigned comparison 1516 q2 = q2 + 1; 1517 r2 = r2 - ad; 1518 } 1519 delta = ad - r2; 1520 } while (q1.ule(delta) || (q1 == delta && r1 == 0)); 1521 1522 mag.m = q2 + 1; 1523 if (d.isNegative()) mag.m = -mag.m; // resulting magic number 1524 mag.s = p - d.getBitWidth(); // resulting shift 1525 return mag; 1526} 1527 1528/// Calculate the magic numbers required to implement an unsigned integer 1529/// division by a constant as a sequence of multiplies, adds and shifts. 1530/// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry 1531/// S. Warren, Jr., chapter 10. 1532APInt::mu APInt::magicu() const { 1533 const APInt& d = *this; 1534 unsigned p; 1535 APInt nc, delta, q1, r1, q2, r2; 1536 struct mu magu; 1537 magu.a = 0; // initialize "add" indicator 1538 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()); 1539 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); 1540 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth()); 1541 1542 nc = allOnes - (-d).urem(d); 1543 p = d.getBitWidth() - 1; // initialize p 1544 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc 1545 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc) 1546 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d 1547 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d) 1548 do { 1549 p = p + 1; 1550 if (r1.uge(nc - r1)) { 1551 q1 = q1 + q1 + 1; // update q1 1552 r1 = r1 + r1 - nc; // update r1 1553 } 1554 else { 1555 q1 = q1+q1; // update q1 1556 r1 = r1+r1; // update r1 1557 } 1558 if ((r2 + 1).uge(d - r2)) { 1559 if (q2.uge(signedMax)) magu.a = 1; 1560 q2 = q2+q2 + 1; // update q2 1561 r2 = r2+r2 + 1 - d; // update r2 1562 } 1563 else { 1564 if (q2.uge(signedMin)) magu.a = 1; 1565 q2 = q2+q2; // update q2 1566 r2 = r2+r2 + 1; // update r2 1567 } 1568 delta = d - 1 - r2; 1569 } while (p < d.getBitWidth()*2 && 1570 (q1.ult(delta) || (q1 == delta && r1 == 0))); 1571 magu.m = q2 + 1; // resulting magic number 1572 magu.s = p - d.getBitWidth(); // resulting shift 1573 return magu; 1574} 1575 1576/// Implementation of Knuth's Algorithm D (Division of nonnegative integers) 1577/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The 1578/// variables here have the same names as in the algorithm. Comments explain 1579/// the algorithm and any deviation from it. 1580static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, 1581 unsigned m, unsigned n) { 1582 assert(u && "Must provide dividend"); 1583 assert(v && "Must provide divisor"); 1584 assert(q && "Must provide quotient"); 1585 assert(u != v && u != q && v != q && "Must us different memory"); 1586 assert(n>1 && "n must be > 1"); 1587 1588 // Knuth uses the value b as the base of the number system. In our case b 1589 // is 2^31 so we just set it to -1u. 1590 uint64_t b = uint64_t(1) << 32; 1591 1592#if 0 1593 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n'); 1594 DEBUG(dbgs() << "KnuthDiv: original:"); 1595 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1596 DEBUG(dbgs() << " by"); 1597 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]); 1598 DEBUG(dbgs() << '\n'); 1599#endif 1600 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of 1601 // u and v by d. Note that we have taken Knuth's advice here to use a power 1602 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of 1603 // 2 allows us to shift instead of multiply and it is easy to determine the 1604 // shift amount from the leading zeros. We are basically normalizing the u 1605 // and v so that its high bits are shifted to the top of v's range without 1606 // overflow. Note that this can require an extra word in u so that u must 1607 // be of length m+n+1. 1608 unsigned shift = CountLeadingZeros_32(v[n-1]); 1609 unsigned v_carry = 0; 1610 unsigned u_carry = 0; 1611 if (shift) { 1612 for (unsigned i = 0; i < m+n; ++i) { 1613 unsigned u_tmp = u[i] >> (32 - shift); 1614 u[i] = (u[i] << shift) | u_carry; 1615 u_carry = u_tmp; 1616 } 1617 for (unsigned i = 0; i < n; ++i) { 1618 unsigned v_tmp = v[i] >> (32 - shift); 1619 v[i] = (v[i] << shift) | v_carry; 1620 v_carry = v_tmp; 1621 } 1622 } 1623 u[m+n] = u_carry; 1624#if 0 1625 DEBUG(dbgs() << "KnuthDiv: normal:"); 1626 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1627 DEBUG(dbgs() << " by"); 1628 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]); 1629 DEBUG(dbgs() << '\n'); 1630#endif 1631 1632 // D2. [Initialize j.] Set j to m. This is the loop counter over the places. 1633 int j = m; 1634 do { 1635 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n'); 1636 // D3. [Calculate q'.]. 1637 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q') 1638 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r') 1639 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease 1640 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test 1641 // on v[n-2] determines at high speed most of the cases in which the trial 1642 // value qp is one too large, and it eliminates all cases where qp is two 1643 // too large. 1644 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]); 1645 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n'); 1646 uint64_t qp = dividend / v[n-1]; 1647 uint64_t rp = dividend % v[n-1]; 1648 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) { 1649 qp--; 1650 rp += v[n-1]; 1651 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2])) 1652 qp--; 1653 } 1654 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n'); 1655 1656 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with 1657 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation 1658 // consists of a simple multiplication by a one-place number, combined with 1659 // a subtraction. 1660 bool isNeg = false; 1661 for (unsigned i = 0; i < n; ++i) { 1662 uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32); 1663 uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]); 1664 bool borrow = subtrahend > u_tmp; 1665 DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp 1666 << ", subtrahend == " << subtrahend 1667 << ", borrow = " << borrow << '\n'); 1668 1669 uint64_t result = u_tmp - subtrahend; 1670 unsigned k = j + i; 1671 u[k++] = (unsigned)(result & (b-1)); // subtract low word 1672 u[k++] = (unsigned)(result >> 32); // subtract high word 1673 while (borrow && k <= m+n) { // deal with borrow to the left 1674 borrow = u[k] == 0; 1675 u[k]--; 1676 k++; 1677 } 1678 isNeg |= borrow; 1679 DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " << 1680 u[j+i+1] << '\n'); 1681 } 1682 DEBUG(dbgs() << "KnuthDiv: after subtraction:"); 1683 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1684 DEBUG(dbgs() << '\n'); 1685 // The digits (u[j+n]...u[j]) should be kept positive; if the result of 1686 // this step is actually negative, (u[j+n]...u[j]) should be left as the 1687 // true value plus b**(n+1), namely as the b's complement of 1688 // the true value, and a "borrow" to the left should be remembered. 1689 // 1690 if (isNeg) { 1691 bool carry = true; // true because b's complement is "complement + 1" 1692 for (unsigned i = 0; i <= m+n; ++i) { 1693 u[i] = ~u[i] + carry; // b's complement 1694 carry = carry && u[i] == 0; 1695 } 1696 } 1697 DEBUG(dbgs() << "KnuthDiv: after complement:"); 1698 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1699 DEBUG(dbgs() << '\n'); 1700 1701 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was 1702 // negative, go to step D6; otherwise go on to step D7. 1703 q[j] = (unsigned)qp; 1704 if (isNeg) { 1705 // D6. [Add back]. The probability that this step is necessary is very 1706 // small, on the order of only 2/b. Make sure that test data accounts for 1707 // this possibility. Decrease q[j] by 1 1708 q[j]--; 1709 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]). 1710 // A carry will occur to the left of u[j+n], and it should be ignored 1711 // since it cancels with the borrow that occurred in D4. 1712 bool carry = false; 1713 for (unsigned i = 0; i < n; i++) { 1714 unsigned limit = std::min(u[j+i],v[i]); 1715 u[j+i] += v[i] + carry; 1716 carry = u[j+i] < limit || (carry && u[j+i] == limit); 1717 } 1718 u[j+n] += carry; 1719 } 1720 DEBUG(dbgs() << "KnuthDiv: after correction:"); 1721 DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]); 1722 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n'); 1723 1724 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3. 1725 } while (--j >= 0); 1726 1727 DEBUG(dbgs() << "KnuthDiv: quotient:"); 1728 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]); 1729 DEBUG(dbgs() << '\n'); 1730 1731 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired 1732 // remainder may be obtained by dividing u[...] by d. If r is non-null we 1733 // compute the remainder (urem uses this). 1734 if (r) { 1735 // The value d is expressed by the "shift" value above since we avoided 1736 // multiplication by d by using a shift left. So, all we have to do is 1737 // shift right here. In order to mak 1738 if (shift) { 1739 unsigned carry = 0; 1740 DEBUG(dbgs() << "KnuthDiv: remainder:"); 1741 for (int i = n-1; i >= 0; i--) { 1742 r[i] = (u[i] >> shift) | carry; 1743 carry = u[i] << (32 - shift); 1744 DEBUG(dbgs() << " " << r[i]); 1745 } 1746 } else { 1747 for (int i = n-1; i >= 0; i--) { 1748 r[i] = u[i]; 1749 DEBUG(dbgs() << " " << r[i]); 1750 } 1751 } 1752 DEBUG(dbgs() << '\n'); 1753 } 1754#if 0 1755 DEBUG(dbgs() << '\n'); 1756#endif 1757} 1758 1759void APInt::divide(const APInt LHS, unsigned lhsWords, 1760 const APInt &RHS, unsigned rhsWords, 1761 APInt *Quotient, APInt *Remainder) 1762{ 1763 assert(lhsWords >= rhsWords && "Fractional result"); 1764 1765 // First, compose the values into an array of 32-bit words instead of 1766 // 64-bit words. This is a necessity of both the "short division" algorithm 1767 // and the Knuth "classical algorithm" which requires there to be native 1768 // operations for +, -, and * on an m bit value with an m*2 bit result. We 1769 // can't use 64-bit operands here because we don't have native results of 1770 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't 1771 // work on large-endian machines. 1772 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT); 1773 unsigned n = rhsWords * 2; 1774 unsigned m = (lhsWords * 2) - n; 1775 1776 // Allocate space for the temporary values we need either on the stack, if 1777 // it will fit, or on the heap if it won't. 1778 unsigned SPACE[128]; 1779 unsigned *U = 0; 1780 unsigned *V = 0; 1781 unsigned *Q = 0; 1782 unsigned *R = 0; 1783 if ((Remainder?4:3)*n+2*m+1 <= 128) { 1784 U = &SPACE[0]; 1785 V = &SPACE[m+n+1]; 1786 Q = &SPACE[(m+n+1) + n]; 1787 if (Remainder) 1788 R = &SPACE[(m+n+1) + n + (m+n)]; 1789 } else { 1790 U = new unsigned[m + n + 1]; 1791 V = new unsigned[n]; 1792 Q = new unsigned[m+n]; 1793 if (Remainder) 1794 R = new unsigned[n]; 1795 } 1796 1797 // Initialize the dividend 1798 memset(U, 0, (m+n+1)*sizeof(unsigned)); 1799 for (unsigned i = 0; i < lhsWords; ++i) { 1800 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]); 1801 U[i * 2] = (unsigned)(tmp & mask); 1802 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT)); 1803 } 1804 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm. 1805 1806 // Initialize the divisor 1807 memset(V, 0, (n)*sizeof(unsigned)); 1808 for (unsigned i = 0; i < rhsWords; ++i) { 1809 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]); 1810 V[i * 2] = (unsigned)(tmp & mask); 1811 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT)); 1812 } 1813 1814 // initialize the quotient and remainder 1815 memset(Q, 0, (m+n) * sizeof(unsigned)); 1816 if (Remainder) 1817 memset(R, 0, n * sizeof(unsigned)); 1818 1819 // Now, adjust m and n for the Knuth division. n is the number of words in 1820 // the divisor. m is the number of words by which the dividend exceeds the 1821 // divisor (i.e. m+n is the length of the dividend). These sizes must not 1822 // contain any zero words or the Knuth algorithm fails. 1823 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) { 1824 n--; 1825 m++; 1826 } 1827 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--) 1828 m--; 1829 1830 // If we're left with only a single word for the divisor, Knuth doesn't work 1831 // so we implement the short division algorithm here. This is much simpler 1832 // and faster because we are certain that we can divide a 64-bit quantity 1833 // by a 32-bit quantity at hardware speed and short division is simply a 1834 // series of such operations. This is just like doing short division but we 1835 // are using base 2^32 instead of base 10. 1836 assert(n != 0 && "Divide by zero?"); 1837 if (n == 1) { 1838 unsigned divisor = V[0]; 1839 unsigned remainder = 0; 1840 for (int i = m+n-1; i >= 0; i--) { 1841 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i]; 1842 if (partial_dividend == 0) { 1843 Q[i] = 0; 1844 remainder = 0; 1845 } else if (partial_dividend < divisor) { 1846 Q[i] = 0; 1847 remainder = (unsigned)partial_dividend; 1848 } else if (partial_dividend == divisor) { 1849 Q[i] = 1; 1850 remainder = 0; 1851 } else { 1852 Q[i] = (unsigned)(partial_dividend / divisor); 1853 remainder = (unsigned)(partial_dividend - (Q[i] * divisor)); 1854 } 1855 } 1856 if (R) 1857 R[0] = remainder; 1858 } else { 1859 // Now we're ready to invoke the Knuth classical divide algorithm. In this 1860 // case n > 1. 1861 KnuthDiv(U, V, Q, R, m, n); 1862 } 1863 1864 // If the caller wants the quotient 1865 if (Quotient) { 1866 // Set up the Quotient value's memory. 1867 if (Quotient->BitWidth != LHS.BitWidth) { 1868 if (Quotient->isSingleWord()) 1869 Quotient->VAL = 0; 1870 else 1871 delete [] Quotient->pVal; 1872 Quotient->BitWidth = LHS.BitWidth; 1873 if (!Quotient->isSingleWord()) 1874 Quotient->pVal = getClearedMemory(Quotient->getNumWords()); 1875 } else 1876 Quotient->clear(); 1877 1878 // The quotient is in Q. Reconstitute the quotient into Quotient's low 1879 // order words. 1880 if (lhsWords == 1) { 1881 uint64_t tmp = 1882 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2)); 1883 if (Quotient->isSingleWord()) 1884 Quotient->VAL = tmp; 1885 else 1886 Quotient->pVal[0] = tmp; 1887 } else { 1888 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough"); 1889 for (unsigned i = 0; i < lhsWords; ++i) 1890 Quotient->pVal[i] = 1891 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2)); 1892 } 1893 } 1894 1895 // If the caller wants the remainder 1896 if (Remainder) { 1897 // Set up the Remainder value's memory. 1898 if (Remainder->BitWidth != RHS.BitWidth) { 1899 if (Remainder->isSingleWord()) 1900 Remainder->VAL = 0; 1901 else 1902 delete [] Remainder->pVal; 1903 Remainder->BitWidth = RHS.BitWidth; 1904 if (!Remainder->isSingleWord()) 1905 Remainder->pVal = getClearedMemory(Remainder->getNumWords()); 1906 } else 1907 Remainder->clear(); 1908 1909 // The remainder is in R. Reconstitute the remainder into Remainder's low 1910 // order words. 1911 if (rhsWords == 1) { 1912 uint64_t tmp = 1913 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2)); 1914 if (Remainder->isSingleWord()) 1915 Remainder->VAL = tmp; 1916 else 1917 Remainder->pVal[0] = tmp; 1918 } else { 1919 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough"); 1920 for (unsigned i = 0; i < rhsWords; ++i) 1921 Remainder->pVal[i] = 1922 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2)); 1923 } 1924 } 1925 1926 // Clean up the memory we allocated. 1927 if (U != &SPACE[0]) { 1928 delete [] U; 1929 delete [] V; 1930 delete [] Q; 1931 delete [] R; 1932 } 1933} 1934 1935APInt APInt::udiv(const APInt& RHS) const { 1936 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 1937 1938 // First, deal with the easy case 1939 if (isSingleWord()) { 1940 assert(RHS.VAL != 0 && "Divide by zero?"); 1941 return APInt(BitWidth, VAL / RHS.VAL); 1942 } 1943 1944 // Get some facts about the LHS and RHS number of bits and words 1945 unsigned rhsBits = RHS.getActiveBits(); 1946 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 1947 assert(rhsWords && "Divided by zero???"); 1948 unsigned lhsBits = this->getActiveBits(); 1949 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); 1950 1951 // Deal with some degenerate cases 1952 if (!lhsWords) 1953 // 0 / X ===> 0 1954 return APInt(BitWidth, 0); 1955 else if (lhsWords < rhsWords || this->ult(RHS)) { 1956 // X / Y ===> 0, iff X < Y 1957 return APInt(BitWidth, 0); 1958 } else if (*this == RHS) { 1959 // X / X ===> 1 1960 return APInt(BitWidth, 1); 1961 } else if (lhsWords == 1 && rhsWords == 1) { 1962 // All high words are zero, just use native divide 1963 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]); 1964 } 1965 1966 // We have to compute it the hard way. Invoke the Knuth divide algorithm. 1967 APInt Quotient(1,0); // to hold result. 1968 divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0); 1969 return Quotient; 1970} 1971 1972APInt APInt::urem(const APInt& RHS) const { 1973 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 1974 if (isSingleWord()) { 1975 assert(RHS.VAL != 0 && "Remainder by zero?"); 1976 return APInt(BitWidth, VAL % RHS.VAL); 1977 } 1978 1979 // Get some facts about the LHS 1980 unsigned lhsBits = getActiveBits(); 1981 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1); 1982 1983 // Get some facts about the RHS 1984 unsigned rhsBits = RHS.getActiveBits(); 1985 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 1986 assert(rhsWords && "Performing remainder operation by zero ???"); 1987 1988 // Check the degenerate cases 1989 if (lhsWords == 0) { 1990 // 0 % Y ===> 0 1991 return APInt(BitWidth, 0); 1992 } else if (lhsWords < rhsWords || this->ult(RHS)) { 1993 // X % Y ===> X, iff X < Y 1994 return *this; 1995 } else if (*this == RHS) { 1996 // X % X == 0; 1997 return APInt(BitWidth, 0); 1998 } else if (lhsWords == 1) { 1999 // All high words are zero, just use native remainder 2000 return APInt(BitWidth, pVal[0] % RHS.pVal[0]); 2001 } 2002 2003 // We have to compute it the hard way. Invoke the Knuth divide algorithm. 2004 APInt Remainder(1,0); 2005 divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder); 2006 return Remainder; 2007} 2008 2009void APInt::udivrem(const APInt &LHS, const APInt &RHS, 2010 APInt &Quotient, APInt &Remainder) { 2011 // Get some size facts about the dividend and divisor 2012 unsigned lhsBits = LHS.getActiveBits(); 2013 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); 2014 unsigned rhsBits = RHS.getActiveBits(); 2015 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 2016 2017 // Check the degenerate cases 2018 if (lhsWords == 0) { 2019 Quotient = 0; // 0 / Y ===> 0 2020 Remainder = 0; // 0 % Y ===> 0 2021 return; 2022 } 2023 2024 if (lhsWords < rhsWords || LHS.ult(RHS)) { 2025 Remainder = LHS; // X % Y ===> X, iff X < Y 2026 Quotient = 0; // X / Y ===> 0, iff X < Y 2027 return; 2028 } 2029 2030 if (LHS == RHS) { 2031 Quotient = 1; // X / X ===> 1 2032 Remainder = 0; // X % X ===> 0; 2033 return; 2034 } 2035 2036 if (lhsWords == 1 && rhsWords == 1) { 2037 // There is only one word to consider so use the native versions. 2038 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0]; 2039 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 2040 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue); 2041 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue); 2042 return; 2043 } 2044 2045 // Okay, lets do it the long way 2046 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder); 2047} 2048 2049void APInt::fromString(unsigned numbits, const StringRef& str, uint8_t radix) { 2050 // Check our assumptions here 2051 assert(!str.empty() && "Invalid string length"); 2052 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && 2053 "Radix should be 2, 8, 10, or 16!"); 2054 2055 StringRef::iterator p = str.begin(); 2056 size_t slen = str.size(); 2057 bool isNeg = *p == '-'; 2058 if (*p == '-' || *p == '+') { 2059 p++; 2060 slen--; 2061 assert(slen && "String is only a sign, needs a value."); 2062 } 2063 assert((slen <= numbits || radix != 2) && "Insufficient bit width"); 2064 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width"); 2065 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width"); 2066 assert((((slen-1)*64)/22 <= numbits || radix != 10) && 2067 "Insufficient bit width"); 2068 2069 // Allocate memory 2070 if (!isSingleWord()) 2071 pVal = getClearedMemory(getNumWords()); 2072 2073 // Figure out if we can shift instead of multiply 2074 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0); 2075 2076 // Set up an APInt for the digit to add outside the loop so we don't 2077 // constantly construct/destruct it. 2078 APInt apdigit(getBitWidth(), 0); 2079 APInt apradix(getBitWidth(), radix); 2080 2081 // Enter digit traversal loop 2082 for (StringRef::iterator e = str.end(); p != e; ++p) { 2083 unsigned digit = getDigit(*p, radix); 2084 assert(digit < radix && "Invalid character in digit string"); 2085 2086 // Shift or multiply the value by the radix 2087 if (slen > 1) { 2088 if (shift) 2089 *this <<= shift; 2090 else 2091 *this *= apradix; 2092 } 2093 2094 // Add in the digit we just interpreted 2095 if (apdigit.isSingleWord()) 2096 apdigit.VAL = digit; 2097 else 2098 apdigit.pVal[0] = digit; 2099 *this += apdigit; 2100 } 2101 // If its negative, put it in two's complement form 2102 if (isNeg) { 2103 (*this)--; 2104 this->flip(); 2105 } 2106} 2107 2108void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix, 2109 bool Signed) const { 2110 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2) && 2111 "Radix should be 2, 8, 10, or 16!"); 2112 2113 // First, check for a zero value and just short circuit the logic below. 2114 if (*this == 0) { 2115 Str.push_back('0'); 2116 return; 2117 } 2118 2119 static const char Digits[] = "0123456789ABCDEF"; 2120 2121 if (isSingleWord()) { 2122 char Buffer[65]; 2123 char *BufPtr = Buffer+65; 2124 2125 uint64_t N; 2126 if (Signed) { 2127 int64_t I = getSExtValue(); 2128 if (I < 0) { 2129 Str.push_back('-'); 2130 I = -I; 2131 } 2132 N = I; 2133 } else { 2134 N = getZExtValue(); 2135 } 2136 2137 while (N) { 2138 *--BufPtr = Digits[N % Radix]; 2139 N /= Radix; 2140 } 2141 Str.append(BufPtr, Buffer+65); 2142 return; 2143 } 2144 2145 APInt Tmp(*this); 2146 2147 if (Signed && isNegative()) { 2148 // They want to print the signed version and it is a negative value 2149 // Flip the bits and add one to turn it into the equivalent positive 2150 // value and put a '-' in the result. 2151 Tmp.flip(); 2152 Tmp++; 2153 Str.push_back('-'); 2154 } 2155 2156 // We insert the digits backward, then reverse them to get the right order. 2157 unsigned StartDig = Str.size(); 2158 2159 // For the 2, 8 and 16 bit cases, we can just shift instead of divide 2160 // because the number of bits per digit (1, 3 and 4 respectively) divides 2161 // equaly. We just shift until the value is zero. 2162 if (Radix != 10) { 2163 // Just shift tmp right for each digit width until it becomes zero 2164 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1)); 2165 unsigned MaskAmt = Radix - 1; 2166 2167 while (Tmp != 0) { 2168 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt; 2169 Str.push_back(Digits[Digit]); 2170 Tmp = Tmp.lshr(ShiftAmt); 2171 } 2172 } else { 2173 APInt divisor(4, 10); 2174 while (Tmp != 0) { 2175 APInt APdigit(1, 0); 2176 APInt tmp2(Tmp.getBitWidth(), 0); 2177 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2, 2178 &APdigit); 2179 unsigned Digit = (unsigned)APdigit.getZExtValue(); 2180 assert(Digit < Radix && "divide failed"); 2181 Str.push_back(Digits[Digit]); 2182 Tmp = tmp2; 2183 } 2184 } 2185 2186 // Reverse the digits before returning. 2187 std::reverse(Str.begin()+StartDig, Str.end()); 2188} 2189 2190/// toString - This returns the APInt as a std::string. Note that this is an 2191/// inefficient method. It is better to pass in a SmallVector/SmallString 2192/// to the methods above. 2193std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const { 2194 SmallString<40> S; 2195 toString(S, Radix, Signed); 2196 return S.str(); 2197} 2198 2199 2200void APInt::dump() const { 2201 SmallString<40> S, U; 2202 this->toStringUnsigned(U); 2203 this->toStringSigned(S); 2204 dbgs() << "APInt(" << BitWidth << "b, " 2205 << U.str() << "u " << S.str() << "s)"; 2206} 2207 2208void APInt::print(raw_ostream &OS, bool isSigned) const { 2209 SmallString<40> S; 2210 this->toString(S, 10, isSigned); 2211 OS << S.str(); 2212} 2213 2214// This implements a variety of operations on a representation of 2215// arbitrary precision, two's-complement, bignum integer values. 2216 2217// Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe 2218// and unrestricting assumption. 2219#define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1] 2220COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0); 2221 2222/* Some handy functions local to this file. */ 2223namespace { 2224 2225 /* Returns the integer part with the least significant BITS set. 2226 BITS cannot be zero. */ 2227 static inline integerPart 2228 lowBitMask(unsigned int bits) 2229 { 2230 assert(bits != 0 && bits <= integerPartWidth); 2231 2232 return ~(integerPart) 0 >> (integerPartWidth - bits); 2233 } 2234 2235 /* Returns the value of the lower half of PART. */ 2236 static inline integerPart 2237 lowHalf(integerPart part) 2238 { 2239 return part & lowBitMask(integerPartWidth / 2); 2240 } 2241 2242 /* Returns the value of the upper half of PART. */ 2243 static inline integerPart 2244 highHalf(integerPart part) 2245 { 2246 return part >> (integerPartWidth / 2); 2247 } 2248 2249 /* Returns the bit number of the most significant set bit of a part. 2250 If the input number has no bits set -1U is returned. */ 2251 static unsigned int 2252 partMSB(integerPart value) 2253 { 2254 unsigned int n, msb; 2255 2256 if (value == 0) 2257 return -1U; 2258 2259 n = integerPartWidth / 2; 2260 2261 msb = 0; 2262 do { 2263 if (value >> n) { 2264 value >>= n; 2265 msb += n; 2266 } 2267 2268 n >>= 1; 2269 } while (n); 2270 2271 return msb; 2272 } 2273 2274 /* Returns the bit number of the least significant set bit of a 2275 part. If the input number has no bits set -1U is returned. */ 2276 static unsigned int 2277 partLSB(integerPart value) 2278 { 2279 unsigned int n, lsb; 2280 2281 if (value == 0) 2282 return -1U; 2283 2284 lsb = integerPartWidth - 1; 2285 n = integerPartWidth / 2; 2286 2287 do { 2288 if (value << n) { 2289 value <<= n; 2290 lsb -= n; 2291 } 2292 2293 n >>= 1; 2294 } while (n); 2295 2296 return lsb; 2297 } 2298} 2299 2300/* Sets the least significant part of a bignum to the input value, and 2301 zeroes out higher parts. */ 2302void 2303APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts) 2304{ 2305 unsigned int i; 2306 2307 assert(parts > 0); 2308 2309 dst[0] = part; 2310 for (i = 1; i < parts; i++) 2311 dst[i] = 0; 2312} 2313 2314/* Assign one bignum to another. */ 2315void 2316APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts) 2317{ 2318 unsigned int i; 2319 2320 for (i = 0; i < parts; i++) 2321 dst[i] = src[i]; 2322} 2323 2324/* Returns true if a bignum is zero, false otherwise. */ 2325bool 2326APInt::tcIsZero(const integerPart *src, unsigned int parts) 2327{ 2328 unsigned int i; 2329 2330 for (i = 0; i < parts; i++) 2331 if (src[i]) 2332 return false; 2333 2334 return true; 2335} 2336 2337/* Extract the given bit of a bignum; returns 0 or 1. */ 2338int 2339APInt::tcExtractBit(const integerPart *parts, unsigned int bit) 2340{ 2341 return (parts[bit / integerPartWidth] & 2342 ((integerPart) 1 << bit % integerPartWidth)) != 0; 2343} 2344 2345/* Set the given bit of a bignum. */ 2346void 2347APInt::tcSetBit(integerPart *parts, unsigned int bit) 2348{ 2349 parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth); 2350} 2351 2352/* Clears the given bit of a bignum. */ 2353void 2354APInt::tcClearBit(integerPart *parts, unsigned int bit) 2355{ 2356 parts[bit / integerPartWidth] &= 2357 ~((integerPart) 1 << (bit % integerPartWidth)); 2358} 2359 2360/* Returns the bit number of the least significant set bit of a 2361 number. If the input number has no bits set -1U is returned. */ 2362unsigned int 2363APInt::tcLSB(const integerPart *parts, unsigned int n) 2364{ 2365 unsigned int i, lsb; 2366 2367 for (i = 0; i < n; i++) { 2368 if (parts[i] != 0) { 2369 lsb = partLSB(parts[i]); 2370 2371 return lsb + i * integerPartWidth; 2372 } 2373 } 2374 2375 return -1U; 2376} 2377 2378/* Returns the bit number of the most significant set bit of a number. 2379 If the input number has no bits set -1U is returned. */ 2380unsigned int 2381APInt::tcMSB(const integerPart *parts, unsigned int n) 2382{ 2383 unsigned int msb; 2384 2385 do { 2386 --n; 2387 2388 if (parts[n] != 0) { 2389 msb = partMSB(parts[n]); 2390 2391 return msb + n * integerPartWidth; 2392 } 2393 } while (n); 2394 2395 return -1U; 2396} 2397 2398/* Copy the bit vector of width srcBITS from SRC, starting at bit 2399 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes 2400 the least significant bit of DST. All high bits above srcBITS in 2401 DST are zero-filled. */ 2402void 2403APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src, 2404 unsigned int srcBits, unsigned int srcLSB) 2405{ 2406 unsigned int firstSrcPart, dstParts, shift, n; 2407 2408 dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth; 2409 assert(dstParts <= dstCount); 2410 2411 firstSrcPart = srcLSB / integerPartWidth; 2412 tcAssign (dst, src + firstSrcPart, dstParts); 2413 2414 shift = srcLSB % integerPartWidth; 2415 tcShiftRight (dst, dstParts, shift); 2416 2417 /* We now have (dstParts * integerPartWidth - shift) bits from SRC 2418 in DST. If this is less that srcBits, append the rest, else 2419 clear the high bits. */ 2420 n = dstParts * integerPartWidth - shift; 2421 if (n < srcBits) { 2422 integerPart mask = lowBitMask (srcBits - n); 2423 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask) 2424 << n % integerPartWidth); 2425 } else if (n > srcBits) { 2426 if (srcBits % integerPartWidth) 2427 dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth); 2428 } 2429 2430 /* Clear high parts. */ 2431 while (dstParts < dstCount) 2432 dst[dstParts++] = 0; 2433} 2434 2435/* DST += RHS + C where C is zero or one. Returns the carry flag. */ 2436integerPart 2437APInt::tcAdd(integerPart *dst, const integerPart *rhs, 2438 integerPart c, unsigned int parts) 2439{ 2440 unsigned int i; 2441 2442 assert(c <= 1); 2443 2444 for (i = 0; i < parts; i++) { 2445 integerPart l; 2446 2447 l = dst[i]; 2448 if (c) { 2449 dst[i] += rhs[i] + 1; 2450 c = (dst[i] <= l); 2451 } else { 2452 dst[i] += rhs[i]; 2453 c = (dst[i] < l); 2454 } 2455 } 2456 2457 return c; 2458} 2459 2460/* DST -= RHS + C where C is zero or one. Returns the carry flag. */ 2461integerPart 2462APInt::tcSubtract(integerPart *dst, const integerPart *rhs, 2463 integerPart c, unsigned int parts) 2464{ 2465 unsigned int i; 2466 2467 assert(c <= 1); 2468 2469 for (i = 0; i < parts; i++) { 2470 integerPart l; 2471 2472 l = dst[i]; 2473 if (c) { 2474 dst[i] -= rhs[i] + 1; 2475 c = (dst[i] >= l); 2476 } else { 2477 dst[i] -= rhs[i]; 2478 c = (dst[i] > l); 2479 } 2480 } 2481 2482 return c; 2483} 2484 2485/* Negate a bignum in-place. */ 2486void 2487APInt::tcNegate(integerPart *dst, unsigned int parts) 2488{ 2489 tcComplement(dst, parts); 2490 tcIncrement(dst, parts); 2491} 2492 2493/* DST += SRC * MULTIPLIER + CARRY if add is true 2494 DST = SRC * MULTIPLIER + CARRY if add is false 2495 2496 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC 2497 they must start at the same point, i.e. DST == SRC. 2498 2499 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is 2500 returned. Otherwise DST is filled with the least significant 2501 DSTPARTS parts of the result, and if all of the omitted higher 2502 parts were zero return zero, otherwise overflow occurred and 2503 return one. */ 2504int 2505APInt::tcMultiplyPart(integerPart *dst, const integerPart *src, 2506 integerPart multiplier, integerPart carry, 2507 unsigned int srcParts, unsigned int dstParts, 2508 bool add) 2509{ 2510 unsigned int i, n; 2511 2512 /* Otherwise our writes of DST kill our later reads of SRC. */ 2513 assert(dst <= src || dst >= src + srcParts); 2514 assert(dstParts <= srcParts + 1); 2515 2516 /* N loops; minimum of dstParts and srcParts. */ 2517 n = dstParts < srcParts ? dstParts: srcParts; 2518 2519 for (i = 0; i < n; i++) { 2520 integerPart low, mid, high, srcPart; 2521 2522 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY. 2523 2524 This cannot overflow, because 2525 2526 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1) 2527 2528 which is less than n^2. */ 2529 2530 srcPart = src[i]; 2531 2532 if (multiplier == 0 || srcPart == 0) { 2533 low = carry; 2534 high = 0; 2535 } else { 2536 low = lowHalf(srcPart) * lowHalf(multiplier); 2537 high = highHalf(srcPart) * highHalf(multiplier); 2538 2539 mid = lowHalf(srcPart) * highHalf(multiplier); 2540 high += highHalf(mid); 2541 mid <<= integerPartWidth / 2; 2542 if (low + mid < low) 2543 high++; 2544 low += mid; 2545 2546 mid = highHalf(srcPart) * lowHalf(multiplier); 2547 high += highHalf(mid); 2548 mid <<= integerPartWidth / 2; 2549 if (low + mid < low) 2550 high++; 2551 low += mid; 2552 2553 /* Now add carry. */ 2554 if (low + carry < low) 2555 high++; 2556 low += carry; 2557 } 2558 2559 if (add) { 2560 /* And now DST[i], and store the new low part there. */ 2561 if (low + dst[i] < low) 2562 high++; 2563 dst[i] += low; 2564 } else 2565 dst[i] = low; 2566 2567 carry = high; 2568 } 2569 2570 if (i < dstParts) { 2571 /* Full multiplication, there is no overflow. */ 2572 assert(i + 1 == dstParts); 2573 dst[i] = carry; 2574 return 0; 2575 } else { 2576 /* We overflowed if there is carry. */ 2577 if (carry) 2578 return 1; 2579 2580 /* We would overflow if any significant unwritten parts would be 2581 non-zero. This is true if any remaining src parts are non-zero 2582 and the multiplier is non-zero. */ 2583 if (multiplier) 2584 for (; i < srcParts; i++) 2585 if (src[i]) 2586 return 1; 2587 2588 /* We fitted in the narrow destination. */ 2589 return 0; 2590 } 2591} 2592 2593/* DST = LHS * RHS, where DST has the same width as the operands and 2594 is filled with the least significant parts of the result. Returns 2595 one if overflow occurred, otherwise zero. DST must be disjoint 2596 from both operands. */ 2597int 2598APInt::tcMultiply(integerPart *dst, const integerPart *lhs, 2599 const integerPart *rhs, unsigned int parts) 2600{ 2601 unsigned int i; 2602 int overflow; 2603 2604 assert(dst != lhs && dst != rhs); 2605 2606 overflow = 0; 2607 tcSet(dst, 0, parts); 2608 2609 for (i = 0; i < parts; i++) 2610 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, 2611 parts - i, true); 2612 2613 return overflow; 2614} 2615 2616/* DST = LHS * RHS, where DST has width the sum of the widths of the 2617 operands. No overflow occurs. DST must be disjoint from both 2618 operands. Returns the number of parts required to hold the 2619 result. */ 2620unsigned int 2621APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs, 2622 const integerPart *rhs, unsigned int lhsParts, 2623 unsigned int rhsParts) 2624{ 2625 /* Put the narrower number on the LHS for less loops below. */ 2626 if (lhsParts > rhsParts) { 2627 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts); 2628 } else { 2629 unsigned int n; 2630 2631 assert(dst != lhs && dst != rhs); 2632 2633 tcSet(dst, 0, rhsParts); 2634 2635 for (n = 0; n < lhsParts; n++) 2636 tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true); 2637 2638 n = lhsParts + rhsParts; 2639 2640 return n - (dst[n - 1] == 0); 2641 } 2642} 2643 2644/* If RHS is zero LHS and REMAINDER are left unchanged, return one. 2645 Otherwise set LHS to LHS / RHS with the fractional part discarded, 2646 set REMAINDER to the remainder, return zero. i.e. 2647 2648 OLD_LHS = RHS * LHS + REMAINDER 2649 2650 SCRATCH is a bignum of the same size as the operands and result for 2651 use by the routine; its contents need not be initialized and are 2652 destroyed. LHS, REMAINDER and SCRATCH must be distinct. 2653*/ 2654int 2655APInt::tcDivide(integerPart *lhs, const integerPart *rhs, 2656 integerPart *remainder, integerPart *srhs, 2657 unsigned int parts) 2658{ 2659 unsigned int n, shiftCount; 2660 integerPart mask; 2661 2662 assert(lhs != remainder && lhs != srhs && remainder != srhs); 2663 2664 shiftCount = tcMSB(rhs, parts) + 1; 2665 if (shiftCount == 0) 2666 return true; 2667 2668 shiftCount = parts * integerPartWidth - shiftCount; 2669 n = shiftCount / integerPartWidth; 2670 mask = (integerPart) 1 << (shiftCount % integerPartWidth); 2671 2672 tcAssign(srhs, rhs, parts); 2673 tcShiftLeft(srhs, parts, shiftCount); 2674 tcAssign(remainder, lhs, parts); 2675 tcSet(lhs, 0, parts); 2676 2677 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to 2678 the total. */ 2679 for (;;) { 2680 int compare; 2681 2682 compare = tcCompare(remainder, srhs, parts); 2683 if (compare >= 0) { 2684 tcSubtract(remainder, srhs, 0, parts); 2685 lhs[n] |= mask; 2686 } 2687 2688 if (shiftCount == 0) 2689 break; 2690 shiftCount--; 2691 tcShiftRight(srhs, parts, 1); 2692 if ((mask >>= 1) == 0) 2693 mask = (integerPart) 1 << (integerPartWidth - 1), n--; 2694 } 2695 2696 return false; 2697} 2698 2699/* Shift a bignum left COUNT bits in-place. Shifted in bits are zero. 2700 There are no restrictions on COUNT. */ 2701void 2702APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count) 2703{ 2704 if (count) { 2705 unsigned int jump, shift; 2706 2707 /* Jump is the inter-part jump; shift is is intra-part shift. */ 2708 jump = count / integerPartWidth; 2709 shift = count % integerPartWidth; 2710 2711 while (parts > jump) { 2712 integerPart part; 2713 2714 parts--; 2715 2716 /* dst[i] comes from the two parts src[i - jump] and, if we have 2717 an intra-part shift, src[i - jump - 1]. */ 2718 part = dst[parts - jump]; 2719 if (shift) { 2720 part <<= shift; 2721 if (parts >= jump + 1) 2722 part |= dst[parts - jump - 1] >> (integerPartWidth - shift); 2723 } 2724 2725 dst[parts] = part; 2726 } 2727 2728 while (parts > 0) 2729 dst[--parts] = 0; 2730 } 2731} 2732 2733/* Shift a bignum right COUNT bits in-place. Shifted in bits are 2734 zero. There are no restrictions on COUNT. */ 2735void 2736APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count) 2737{ 2738 if (count) { 2739 unsigned int i, jump, shift; 2740 2741 /* Jump is the inter-part jump; shift is is intra-part shift. */ 2742 jump = count / integerPartWidth; 2743 shift = count % integerPartWidth; 2744 2745 /* Perform the shift. This leaves the most significant COUNT bits 2746 of the result at zero. */ 2747 for (i = 0; i < parts; i++) { 2748 integerPart part; 2749 2750 if (i + jump >= parts) { 2751 part = 0; 2752 } else { 2753 part = dst[i + jump]; 2754 if (shift) { 2755 part >>= shift; 2756 if (i + jump + 1 < parts) 2757 part |= dst[i + jump + 1] << (integerPartWidth - shift); 2758 } 2759 } 2760 2761 dst[i] = part; 2762 } 2763 } 2764} 2765 2766/* Bitwise and of two bignums. */ 2767void 2768APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts) 2769{ 2770 unsigned int i; 2771 2772 for (i = 0; i < parts; i++) 2773 dst[i] &= rhs[i]; 2774} 2775 2776/* Bitwise inclusive or of two bignums. */ 2777void 2778APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts) 2779{ 2780 unsigned int i; 2781 2782 for (i = 0; i < parts; i++) 2783 dst[i] |= rhs[i]; 2784} 2785 2786/* Bitwise exclusive or of two bignums. */ 2787void 2788APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts) 2789{ 2790 unsigned int i; 2791 2792 for (i = 0; i < parts; i++) 2793 dst[i] ^= rhs[i]; 2794} 2795 2796/* Complement a bignum in-place. */ 2797void 2798APInt::tcComplement(integerPart *dst, unsigned int parts) 2799{ 2800 unsigned int i; 2801 2802 for (i = 0; i < parts; i++) 2803 dst[i] = ~dst[i]; 2804} 2805 2806/* Comparison (unsigned) of two bignums. */ 2807int 2808APInt::tcCompare(const integerPart *lhs, const integerPart *rhs, 2809 unsigned int parts) 2810{ 2811 while (parts) { 2812 parts--; 2813 if (lhs[parts] == rhs[parts]) 2814 continue; 2815 2816 if (lhs[parts] > rhs[parts]) 2817 return 1; 2818 else 2819 return -1; 2820 } 2821 2822 return 0; 2823} 2824 2825/* Increment a bignum in-place, return the carry flag. */ 2826integerPart 2827APInt::tcIncrement(integerPart *dst, unsigned int parts) 2828{ 2829 unsigned int i; 2830 2831 for (i = 0; i < parts; i++) 2832 if (++dst[i] != 0) 2833 break; 2834 2835 return i == parts; 2836} 2837 2838/* Set the least significant BITS bits of a bignum, clear the 2839 rest. */ 2840void 2841APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts, 2842 unsigned int bits) 2843{ 2844 unsigned int i; 2845 2846 i = 0; 2847 while (bits > integerPartWidth) { 2848 dst[i++] = ~(integerPart) 0; 2849 bits -= integerPartWidth; 2850 } 2851 2852 if (bits) 2853 dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits); 2854 2855 while (i < parts) 2856 dst[i++] = 0; 2857} 2858