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