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