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