1193323Sed//===-- APInt.cpp - Implement APInt class ---------------------------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements a class to represent arbitrary precision integer 11193323Sed// constant values and provide a variety of arithmetic operations on them. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15193323Sed#define DEBUG_TYPE "apint" 16193323Sed#include "llvm/ADT/APInt.h" 17193323Sed#include "llvm/ADT/FoldingSet.h" 18234353Sdim#include "llvm/ADT/Hashing.h" 19193323Sed#include "llvm/ADT/SmallString.h" 20234353Sdim#include "llvm/ADT/StringRef.h" 21193323Sed#include "llvm/Support/Debug.h" 22198090Srdivacky#include "llvm/Support/ErrorHandling.h" 23193323Sed#include "llvm/Support/MathExtras.h" 24193323Sed#include "llvm/Support/raw_ostream.h" 25193323Sed#include <cmath> 26249423Sdim#include <cstdlib> 27249423Sdim#include <cstring> 28193323Sed#include <limits> 29193323Sedusing namespace llvm; 30193323Sed 31193323Sed/// A utility function for allocating memory, checking for allocation failures, 32193323Sed/// and ensuring the contents are zeroed. 33193323Sedinline static uint64_t* getClearedMemory(unsigned numWords) { 34193323Sed uint64_t * result = new uint64_t[numWords]; 35193323Sed assert(result && "APInt memory allocation fails!"); 36193323Sed memset(result, 0, numWords * sizeof(uint64_t)); 37193323Sed return result; 38193323Sed} 39193323Sed 40198090Srdivacky/// A utility function for allocating memory and checking for allocation 41193323Sed/// failure. The content is not zeroed. 42193323Sedinline static uint64_t* getMemory(unsigned numWords) { 43193323Sed uint64_t * result = new uint64_t[numWords]; 44193323Sed assert(result && "APInt memory allocation fails!"); 45193323Sed return result; 46193323Sed} 47193323Sed 48198090Srdivacky/// A utility function that converts a character to a digit. 49198090Srdivackyinline static unsigned getDigit(char cdigit, uint8_t radix) { 50198090Srdivacky unsigned r; 51198090Srdivacky 52226633Sdim if (radix == 16 || radix == 36) { 53198090Srdivacky r = cdigit - '0'; 54198090Srdivacky if (r <= 9) 55198090Srdivacky return r; 56198090Srdivacky 57198090Srdivacky r = cdigit - 'A'; 58226633Sdim if (r <= radix - 11U) 59198090Srdivacky return r + 10; 60198090Srdivacky 61198090Srdivacky r = cdigit - 'a'; 62226633Sdim if (r <= radix - 11U) 63198090Srdivacky return r + 10; 64226633Sdim 65226633Sdim radix = 10; 66198090Srdivacky } 67198090Srdivacky 68198090Srdivacky r = cdigit - '0'; 69198090Srdivacky if (r < radix) 70198090Srdivacky return r; 71198090Srdivacky 72198090Srdivacky return -1U; 73198090Srdivacky} 74198090Srdivacky 75198090Srdivacky 76193323Sedvoid APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) { 77193323Sed pVal = getClearedMemory(getNumWords()); 78193323Sed pVal[0] = val; 79198090Srdivacky if (isSigned && int64_t(val) < 0) 80193323Sed for (unsigned i = 1; i < getNumWords(); ++i) 81193323Sed pVal[i] = -1ULL; 82193323Sed} 83193323Sed 84193323Sedvoid APInt::initSlowCase(const APInt& that) { 85193323Sed pVal = getMemory(getNumWords()); 86193323Sed memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE); 87193323Sed} 88193323Sed 89226633Sdimvoid APInt::initFromArray(ArrayRef<uint64_t> bigVal) { 90198090Srdivacky assert(BitWidth && "Bitwidth too small"); 91226633Sdim assert(bigVal.data() && "Null pointer detected!"); 92193323Sed if (isSingleWord()) 93193323Sed VAL = bigVal[0]; 94193323Sed else { 95193323Sed // Get memory, cleared to 0 96193323Sed pVal = getClearedMemory(getNumWords()); 97193323Sed // Calculate the number of words to copy 98226633Sdim unsigned words = std::min<unsigned>(bigVal.size(), getNumWords()); 99193323Sed // Copy the words from bigVal to pVal 100226633Sdim memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE); 101193323Sed } 102193323Sed // Make sure unused high bits are cleared 103193323Sed clearUnusedBits(); 104193323Sed} 105193323Sed 106226633SdimAPInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal) 107226633Sdim : BitWidth(numBits), VAL(0) { 108226633Sdim initFromArray(bigVal); 109226633Sdim} 110226633Sdim 111226633SdimAPInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]) 112226633Sdim : BitWidth(numBits), VAL(0) { 113226633Sdim initFromArray(makeArrayRef(bigVal, numWords)); 114226633Sdim} 115226633Sdim 116210299SedAPInt::APInt(unsigned numbits, StringRef Str, uint8_t radix) 117193323Sed : BitWidth(numbits), VAL(0) { 118198090Srdivacky assert(BitWidth && "Bitwidth too small"); 119198090Srdivacky fromString(numbits, Str, radix); 120193323Sed} 121193323Sed 122193323SedAPInt& APInt::AssignSlowCase(const APInt& RHS) { 123193323Sed // Don't do anything for X = X 124193323Sed if (this == &RHS) 125193323Sed return *this; 126193323Sed 127193323Sed if (BitWidth == RHS.getBitWidth()) { 128193323Sed // assume same bit-width single-word case is already handled 129193323Sed assert(!isSingleWord()); 130193323Sed memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE); 131193323Sed return *this; 132193323Sed } 133193323Sed 134193323Sed if (isSingleWord()) { 135193323Sed // assume case where both are single words is already handled 136193323Sed assert(!RHS.isSingleWord()); 137193323Sed VAL = 0; 138193323Sed pVal = getMemory(RHS.getNumWords()); 139193323Sed memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 140198090Srdivacky } else if (getNumWords() == RHS.getNumWords()) 141193323Sed memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 142193323Sed else if (RHS.isSingleWord()) { 143193323Sed delete [] pVal; 144193323Sed VAL = RHS.VAL; 145193323Sed } else { 146193323Sed delete [] pVal; 147193323Sed pVal = getMemory(RHS.getNumWords()); 148193323Sed memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 149193323Sed } 150193323Sed BitWidth = RHS.BitWidth; 151193323Sed return clearUnusedBits(); 152193323Sed} 153193323Sed 154193323SedAPInt& APInt::operator=(uint64_t RHS) { 155198090Srdivacky if (isSingleWord()) 156193323Sed VAL = RHS; 157193323Sed else { 158193323Sed pVal[0] = RHS; 159193323Sed memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); 160193323Sed } 161193323Sed return clearUnusedBits(); 162193323Sed} 163193323Sed 164193323Sed/// Profile - This method 'profiles' an APInt for use with FoldingSet. 165193323Sedvoid APInt::Profile(FoldingSetNodeID& ID) const { 166193323Sed ID.AddInteger(BitWidth); 167198090Srdivacky 168193323Sed if (isSingleWord()) { 169193323Sed ID.AddInteger(VAL); 170193323Sed return; 171193323Sed } 172193323Sed 173193323Sed unsigned NumWords = getNumWords(); 174193323Sed for (unsigned i = 0; i < NumWords; ++i) 175193323Sed ID.AddInteger(pVal[i]); 176193323Sed} 177193323Sed 178198090Srdivacky/// add_1 - This function adds a single "digit" integer, y, to the multiple 179193323Sed/// "digit" integer array, x[]. x[] is modified to reflect the addition and 180193323Sed/// 1 is returned if there is a carry out, otherwise 0 is returned. 181193323Sed/// @returns the carry of the addition. 182193323Sedstatic bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) { 183193323Sed for (unsigned i = 0; i < len; ++i) { 184193323Sed dest[i] = y + x[i]; 185193323Sed if (dest[i] < y) 186193323Sed y = 1; // Carry one to next digit. 187193323Sed else { 188193323Sed y = 0; // No need to carry so exit early 189193323Sed break; 190193323Sed } 191193323Sed } 192193323Sed return y; 193193323Sed} 194193323Sed 195193323Sed/// @brief Prefix increment operator. Increments the APInt by one. 196193323SedAPInt& APInt::operator++() { 197198090Srdivacky if (isSingleWord()) 198193323Sed ++VAL; 199193323Sed else 200193323Sed add_1(pVal, pVal, getNumWords(), 1); 201193323Sed return clearUnusedBits(); 202193323Sed} 203193323Sed 204198090Srdivacky/// sub_1 - This function subtracts a single "digit" (64-bit word), y, from 205198090Srdivacky/// the multi-digit integer array, x[], propagating the borrowed 1 value until 206193323Sed/// no further borrowing is neeeded or it runs out of "digits" in x. The result 207193323Sed/// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted. 208193323Sed/// In other words, if y > x then this function returns 1, otherwise 0. 209193323Sed/// @returns the borrow out of the subtraction 210193323Sedstatic bool sub_1(uint64_t x[], unsigned len, uint64_t y) { 211193323Sed for (unsigned i = 0; i < len; ++i) { 212193323Sed uint64_t X = x[i]; 213193323Sed x[i] -= y; 214198090Srdivacky if (y > X) 215193323Sed y = 1; // We have to "borrow 1" from next "digit" 216193323Sed else { 217193323Sed y = 0; // No need to borrow 218193323Sed break; // Remaining digits are unchanged so exit early 219193323Sed } 220193323Sed } 221193323Sed return bool(y); 222193323Sed} 223193323Sed 224193323Sed/// @brief Prefix decrement operator. Decrements the APInt by one. 225193323SedAPInt& APInt::operator--() { 226198090Srdivacky if (isSingleWord()) 227193323Sed --VAL; 228193323Sed else 229193323Sed sub_1(pVal, getNumWords(), 1); 230193323Sed return clearUnusedBits(); 231193323Sed} 232193323Sed 233193323Sed/// add - This function adds the integer array x to the integer array Y and 234198090Srdivacky/// places the result in dest. 235193323Sed/// @returns the carry out from the addition 236193323Sed/// @brief General addition of 64-bit integer arrays 237198090Srdivackystatic bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y, 238193323Sed unsigned len) { 239193323Sed bool carry = false; 240193323Sed for (unsigned i = 0; i< len; ++i) { 241193323Sed uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x 242193323Sed dest[i] = x[i] + y[i] + carry; 243193323Sed carry = dest[i] < limit || (carry && dest[i] == limit); 244193323Sed } 245193323Sed return carry; 246193323Sed} 247193323Sed 248193323Sed/// Adds the RHS APint to this APInt. 249193323Sed/// @returns this, after addition of RHS. 250198090Srdivacky/// @brief Addition assignment operator. 251193323SedAPInt& APInt::operator+=(const APInt& RHS) { 252193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 253198090Srdivacky if (isSingleWord()) 254193323Sed VAL += RHS.VAL; 255193323Sed else { 256193323Sed add(pVal, pVal, RHS.pVal, getNumWords()); 257193323Sed } 258193323Sed return clearUnusedBits(); 259193323Sed} 260193323Sed 261198090Srdivacky/// Subtracts the integer array y from the integer array x 262193323Sed/// @returns returns the borrow out. 263193323Sed/// @brief Generalized subtraction of 64-bit integer arrays. 264198090Srdivackystatic bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y, 265193323Sed unsigned len) { 266193323Sed bool borrow = false; 267193323Sed for (unsigned i = 0; i < len; ++i) { 268193323Sed uint64_t x_tmp = borrow ? x[i] - 1 : x[i]; 269193323Sed borrow = y[i] > x_tmp || (borrow && x[i] == 0); 270193323Sed dest[i] = x_tmp - y[i]; 271193323Sed } 272193323Sed return borrow; 273193323Sed} 274193323Sed 275193323Sed/// Subtracts the RHS APInt from this APInt 276193323Sed/// @returns this, after subtraction 277198090Srdivacky/// @brief Subtraction assignment operator. 278193323SedAPInt& APInt::operator-=(const APInt& RHS) { 279193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 280198090Srdivacky if (isSingleWord()) 281193323Sed VAL -= RHS.VAL; 282193323Sed else 283193323Sed sub(pVal, pVal, RHS.pVal, getNumWords()); 284193323Sed return clearUnusedBits(); 285193323Sed} 286193323Sed 287203954Srdivacky/// Multiplies an integer array, x, by a uint64_t integer and places the result 288198090Srdivacky/// into dest. 289193323Sed/// @returns the carry out of the multiplication. 290193323Sed/// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer. 291193323Sedstatic uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) { 292193323Sed // Split y into high 32-bit part (hy) and low 32-bit part (ly) 293193323Sed uint64_t ly = y & 0xffffffffULL, hy = y >> 32; 294193323Sed uint64_t carry = 0; 295193323Sed 296193323Sed // For each digit of x. 297193323Sed for (unsigned i = 0; i < len; ++i) { 298193323Sed // Split x into high and low words 299193323Sed uint64_t lx = x[i] & 0xffffffffULL; 300193323Sed uint64_t hx = x[i] >> 32; 301193323Sed // hasCarry - A flag to indicate if there is a carry to the next digit. 302193323Sed // hasCarry == 0, no carry 303193323Sed // hasCarry == 1, has carry 304193323Sed // hasCarry == 2, no carry and the calculation result == 0. 305193323Sed uint8_t hasCarry = 0; 306193323Sed dest[i] = carry + lx * ly; 307193323Sed // Determine if the add above introduces carry. 308193323Sed hasCarry = (dest[i] < carry) ? 1 : 0; 309193323Sed carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0); 310198090Srdivacky // The upper limit of carry can be (2^32 - 1)(2^32 - 1) + 311193323Sed // (2^32 - 1) + 2^32 = 2^64. 312193323Sed hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 313193323Sed 314193323Sed carry += (lx * hy) & 0xffffffffULL; 315193323Sed dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL); 316198090Srdivacky carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) + 317193323Sed (carry >> 32) + ((lx * hy) >> 32) + hx * hy; 318193323Sed } 319193323Sed return carry; 320193323Sed} 321193323Sed 322198090Srdivacky/// Multiplies integer array x by integer array y and stores the result into 323193323Sed/// the integer array dest. Note that dest's size must be >= xlen + ylen. 324193323Sed/// @brief Generalized multiplicate of integer arrays. 325193323Sedstatic void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[], 326193323Sed unsigned ylen) { 327193323Sed dest[xlen] = mul_1(dest, x, xlen, y[0]); 328193323Sed for (unsigned i = 1; i < ylen; ++i) { 329193323Sed uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32; 330193323Sed uint64_t carry = 0, lx = 0, hx = 0; 331193323Sed for (unsigned j = 0; j < xlen; ++j) { 332193323Sed lx = x[j] & 0xffffffffULL; 333193323Sed hx = x[j] >> 32; 334193323Sed // hasCarry - A flag to indicate if has carry. 335193323Sed // hasCarry == 0, no carry 336193323Sed // hasCarry == 1, has carry 337193323Sed // hasCarry == 2, no carry and the calculation result == 0. 338193323Sed uint8_t hasCarry = 0; 339193323Sed uint64_t resul = carry + lx * ly; 340193323Sed hasCarry = (resul < carry) ? 1 : 0; 341193323Sed carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32); 342193323Sed hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 343193323Sed 344193323Sed carry += (lx * hy) & 0xffffffffULL; 345193323Sed resul = (carry << 32) | (resul & 0xffffffffULL); 346193323Sed dest[i+j] += resul; 347193323Sed carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+ 348198090Srdivacky (carry >> 32) + (dest[i+j] < resul ? 1 : 0) + 349193323Sed ((lx * hy) >> 32) + hx * hy; 350193323Sed } 351193323Sed dest[i+xlen] = carry; 352193323Sed } 353193323Sed} 354193323Sed 355193323SedAPInt& APInt::operator*=(const APInt& RHS) { 356193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 357193323Sed if (isSingleWord()) { 358193323Sed VAL *= RHS.VAL; 359193323Sed clearUnusedBits(); 360193323Sed return *this; 361193323Sed } 362193323Sed 363193323Sed // Get some bit facts about LHS and check for zero 364193323Sed unsigned lhsBits = getActiveBits(); 365193323Sed unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1; 366198090Srdivacky if (!lhsWords) 367193323Sed // 0 * X ===> 0 368193323Sed return *this; 369193323Sed 370193323Sed // Get some bit facts about RHS and check for zero 371193323Sed unsigned rhsBits = RHS.getActiveBits(); 372193323Sed unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1; 373193323Sed if (!rhsWords) { 374193323Sed // X * 0 ===> 0 375218893Sdim clearAllBits(); 376193323Sed return *this; 377193323Sed } 378193323Sed 379193323Sed // Allocate space for the result 380193323Sed unsigned destWords = rhsWords + lhsWords; 381193323Sed uint64_t *dest = getMemory(destWords); 382193323Sed 383193323Sed // Perform the long multiply 384193323Sed mul(dest, pVal, lhsWords, RHS.pVal, rhsWords); 385193323Sed 386193323Sed // Copy result back into *this 387218893Sdim clearAllBits(); 388193323Sed unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords; 389193323Sed memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE); 390226633Sdim clearUnusedBits(); 391193323Sed 392193323Sed // delete dest array and return 393193323Sed delete[] dest; 394193323Sed return *this; 395193323Sed} 396193323Sed 397193323SedAPInt& APInt::operator&=(const APInt& RHS) { 398193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 399193323Sed if (isSingleWord()) { 400193323Sed VAL &= RHS.VAL; 401193323Sed return *this; 402193323Sed } 403193323Sed unsigned numWords = getNumWords(); 404193323Sed for (unsigned i = 0; i < numWords; ++i) 405193323Sed pVal[i] &= RHS.pVal[i]; 406193323Sed return *this; 407193323Sed} 408193323Sed 409193323SedAPInt& APInt::operator|=(const APInt& RHS) { 410193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 411193323Sed if (isSingleWord()) { 412193323Sed VAL |= RHS.VAL; 413193323Sed return *this; 414193323Sed } 415193323Sed unsigned numWords = getNumWords(); 416193323Sed for (unsigned i = 0; i < numWords; ++i) 417193323Sed pVal[i] |= RHS.pVal[i]; 418193323Sed return *this; 419193323Sed} 420193323Sed 421193323SedAPInt& APInt::operator^=(const APInt& RHS) { 422193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 423193323Sed if (isSingleWord()) { 424193323Sed VAL ^= RHS.VAL; 425193323Sed this->clearUnusedBits(); 426193323Sed return *this; 427198090Srdivacky } 428193323Sed unsigned numWords = getNumWords(); 429193323Sed for (unsigned i = 0; i < numWords; ++i) 430193323Sed pVal[i] ^= RHS.pVal[i]; 431193323Sed return clearUnusedBits(); 432193323Sed} 433193323Sed 434193323SedAPInt APInt::AndSlowCase(const APInt& RHS) const { 435193323Sed unsigned numWords = getNumWords(); 436193323Sed uint64_t* val = getMemory(numWords); 437193323Sed for (unsigned i = 0; i < numWords; ++i) 438193323Sed val[i] = pVal[i] & RHS.pVal[i]; 439193323Sed return APInt(val, getBitWidth()); 440193323Sed} 441193323Sed 442193323SedAPInt APInt::OrSlowCase(const APInt& RHS) const { 443193323Sed unsigned numWords = getNumWords(); 444193323Sed uint64_t *val = getMemory(numWords); 445193323Sed for (unsigned i = 0; i < numWords; ++i) 446193323Sed val[i] = pVal[i] | RHS.pVal[i]; 447193323Sed return APInt(val, getBitWidth()); 448193323Sed} 449193323Sed 450193323SedAPInt APInt::XorSlowCase(const APInt& RHS) const { 451193323Sed unsigned numWords = getNumWords(); 452193323Sed uint64_t *val = getMemory(numWords); 453193323Sed for (unsigned i = 0; i < numWords; ++i) 454193323Sed val[i] = pVal[i] ^ RHS.pVal[i]; 455193323Sed 456193323Sed // 0^0==1 so clear the high bits in case they got set. 457193323Sed return APInt(val, getBitWidth()).clearUnusedBits(); 458193323Sed} 459193323Sed 460193323SedAPInt APInt::operator*(const APInt& RHS) const { 461193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 462193323Sed if (isSingleWord()) 463193323Sed return APInt(BitWidth, VAL * RHS.VAL); 464193323Sed APInt Result(*this); 465193323Sed Result *= RHS; 466226633Sdim return Result; 467193323Sed} 468193323Sed 469193323SedAPInt APInt::operator+(const APInt& RHS) const { 470193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 471193323Sed if (isSingleWord()) 472193323Sed return APInt(BitWidth, VAL + RHS.VAL); 473193323Sed APInt Result(BitWidth, 0); 474193323Sed add(Result.pVal, this->pVal, RHS.pVal, getNumWords()); 475193323Sed return Result.clearUnusedBits(); 476193323Sed} 477193323Sed 478193323SedAPInt APInt::operator-(const APInt& RHS) const { 479193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 480193323Sed if (isSingleWord()) 481193323Sed return APInt(BitWidth, VAL - RHS.VAL); 482193323Sed APInt Result(BitWidth, 0); 483193323Sed sub(Result.pVal, this->pVal, RHS.pVal, getNumWords()); 484193323Sed return Result.clearUnusedBits(); 485193323Sed} 486193323Sed 487193323Sedbool APInt::EqualSlowCase(const APInt& RHS) const { 488193323Sed // Get some facts about the number of bits used in the two operands. 489193323Sed unsigned n1 = getActiveBits(); 490193323Sed unsigned n2 = RHS.getActiveBits(); 491193323Sed 492193323Sed // If the number of bits isn't the same, they aren't equal 493198090Srdivacky if (n1 != n2) 494193323Sed return false; 495193323Sed 496193323Sed // If the number of bits fits in a word, we only need to compare the low word. 497193323Sed if (n1 <= APINT_BITS_PER_WORD) 498193323Sed return pVal[0] == RHS.pVal[0]; 499193323Sed 500193323Sed // Otherwise, compare everything 501193323Sed for (int i = whichWord(n1 - 1); i >= 0; --i) 502198090Srdivacky if (pVal[i] != RHS.pVal[i]) 503193323Sed return false; 504193323Sed return true; 505193323Sed} 506193323Sed 507193323Sedbool APInt::EqualSlowCase(uint64_t Val) const { 508193323Sed unsigned n = getActiveBits(); 509193323Sed if (n <= APINT_BITS_PER_WORD) 510193323Sed return pVal[0] == Val; 511193323Sed else 512193323Sed return false; 513193323Sed} 514193323Sed 515193323Sedbool APInt::ult(const APInt& RHS) const { 516193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"); 517193323Sed if (isSingleWord()) 518193323Sed return VAL < RHS.VAL; 519193323Sed 520193323Sed // Get active bit length of both operands 521193323Sed unsigned n1 = getActiveBits(); 522193323Sed unsigned n2 = RHS.getActiveBits(); 523193323Sed 524193323Sed // If magnitude of LHS is less than RHS, return true. 525193323Sed if (n1 < n2) 526193323Sed return true; 527193323Sed 528193323Sed // If magnitude of RHS is greather than LHS, return false. 529193323Sed if (n2 < n1) 530193323Sed return false; 531193323Sed 532193323Sed // If they bot fit in a word, just compare the low order word 533193323Sed if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD) 534193323Sed return pVal[0] < RHS.pVal[0]; 535193323Sed 536193323Sed // Otherwise, compare all words 537193323Sed unsigned topWord = whichWord(std::max(n1,n2)-1); 538193323Sed for (int i = topWord; i >= 0; --i) { 539198090Srdivacky if (pVal[i] > RHS.pVal[i]) 540193323Sed return false; 541198090Srdivacky if (pVal[i] < RHS.pVal[i]) 542193323Sed return true; 543193323Sed } 544193323Sed return false; 545193323Sed} 546193323Sed 547193323Sedbool APInt::slt(const APInt& RHS) const { 548193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"); 549193323Sed if (isSingleWord()) { 550193323Sed int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth); 551193323Sed int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth); 552193323Sed return lhsSext < rhsSext; 553193323Sed } 554193323Sed 555193323Sed APInt lhs(*this); 556193323Sed APInt rhs(RHS); 557193323Sed bool lhsNeg = isNegative(); 558193323Sed bool rhsNeg = rhs.isNegative(); 559193323Sed if (lhsNeg) { 560193323Sed // Sign bit is set so perform two's complement to make it positive 561218893Sdim lhs.flipAllBits(); 562249423Sdim ++lhs; 563193323Sed } 564193323Sed if (rhsNeg) { 565193323Sed // Sign bit is set so perform two's complement to make it positive 566218893Sdim rhs.flipAllBits(); 567249423Sdim ++rhs; 568193323Sed } 569193323Sed 570193323Sed // Now we have unsigned values to compare so do the comparison if necessary 571193323Sed // based on the negativeness of the values. 572193323Sed if (lhsNeg) 573193323Sed if (rhsNeg) 574193323Sed return lhs.ugt(rhs); 575193323Sed else 576193323Sed return true; 577193323Sed else if (rhsNeg) 578193323Sed return false; 579198090Srdivacky else 580193323Sed return lhs.ult(rhs); 581193323Sed} 582193323Sed 583218893Sdimvoid APInt::setBit(unsigned bitPosition) { 584198090Srdivacky if (isSingleWord()) 585193323Sed VAL |= maskBit(bitPosition); 586198090Srdivacky else 587193323Sed pVal[whichWord(bitPosition)] |= maskBit(bitPosition); 588193323Sed} 589193323Sed 590193323Sed/// Set the given bit to 0 whose position is given as "bitPosition". 591193323Sed/// @brief Set a given bit to 0. 592218893Sdimvoid APInt::clearBit(unsigned bitPosition) { 593198090Srdivacky if (isSingleWord()) 594193323Sed VAL &= ~maskBit(bitPosition); 595198090Srdivacky else 596193323Sed pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition); 597193323Sed} 598193323Sed 599193323Sed/// @brief Toggle every bit to its opposite value. 600193323Sed 601198090Srdivacky/// Toggle a given bit to its opposite value whose position is given 602193323Sed/// as "bitPosition". 603193323Sed/// @brief Toggles a given bit to its opposite value. 604218893Sdimvoid APInt::flipBit(unsigned bitPosition) { 605193323Sed assert(bitPosition < BitWidth && "Out of the bit-width range!"); 606218893Sdim if ((*this)[bitPosition]) clearBit(bitPosition); 607218893Sdim else setBit(bitPosition); 608193323Sed} 609193323Sed 610210299Sedunsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) { 611198090Srdivacky assert(!str.empty() && "Invalid string length"); 612226633Sdim assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 || 613226633Sdim radix == 36) && 614226633Sdim "Radix should be 2, 8, 10, 16, or 36!"); 615193323Sed 616198090Srdivacky size_t slen = str.size(); 617198090Srdivacky 618198090Srdivacky // Each computation below needs to know if it's negative. 619198090Srdivacky StringRef::iterator p = str.begin(); 620198090Srdivacky unsigned isNegative = *p == '-'; 621198090Srdivacky if (*p == '-' || *p == '+') { 622198090Srdivacky p++; 623193323Sed slen--; 624198090Srdivacky assert(slen && "String is only a sign, needs a value."); 625193323Sed } 626198090Srdivacky 627193323Sed // For radixes of power-of-two values, the bits required is accurately and 628193323Sed // easily computed 629193323Sed if (radix == 2) 630193323Sed return slen + isNegative; 631193323Sed if (radix == 8) 632193323Sed return slen * 3 + isNegative; 633193323Sed if (radix == 16) 634193323Sed return slen * 4 + isNegative; 635193323Sed 636226633Sdim // FIXME: base 36 637226633Sdim 638193323Sed // This is grossly inefficient but accurate. We could probably do something 639193323Sed // with a computation of roughly slen*64/20 and then adjust by the value of 640193323Sed // the first few digits. But, I'm not sure how accurate that could be. 641193323Sed 642193323Sed // Compute a sufficient number of bits that is always large enough but might 643198090Srdivacky // be too large. This avoids the assertion in the constructor. This 644198090Srdivacky // calculation doesn't work appropriately for the numbers 0-9, so just use 4 645198090Srdivacky // bits in that case. 646226633Sdim unsigned sufficient 647226633Sdim = radix == 10? (slen == 1 ? 4 : slen * 64/18) 648226633Sdim : (slen == 1 ? 7 : slen * 16/3); 649193323Sed 650193323Sed // Convert to the actual binary value. 651198090Srdivacky APInt tmp(sufficient, StringRef(p, slen), radix); 652193323Sed 653198090Srdivacky // Compute how many bits are required. If the log is infinite, assume we need 654198090Srdivacky // just bit. 655198090Srdivacky unsigned log = tmp.logBase2(); 656198090Srdivacky if (log == (unsigned)-1) { 657198090Srdivacky return isNegative + 1; 658198090Srdivacky } else { 659198090Srdivacky return isNegative + log + 1; 660198090Srdivacky } 661193323Sed} 662193323Sed 663234353Sdimhash_code llvm::hash_value(const APInt &Arg) { 664234353Sdim if (Arg.isSingleWord()) 665234353Sdim return hash_combine(Arg.VAL); 666193323Sed 667234353Sdim return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords()); 668193323Sed} 669193323Sed 670193323Sed/// HiBits - This function returns the high "numBits" bits of this APInt. 671193323SedAPInt APInt::getHiBits(unsigned numBits) const { 672193323Sed return APIntOps::lshr(*this, BitWidth - numBits); 673193323Sed} 674193323Sed 675193323Sed/// LoBits - This function returns the low "numBits" bits of this APInt. 676193323SedAPInt APInt::getLoBits(unsigned numBits) const { 677198090Srdivacky return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits), 678193323Sed BitWidth - numBits); 679193323Sed} 680193323Sed 681193323Sedunsigned APInt::countLeadingZerosSlowCase() const { 682203954Srdivacky // Treat the most significand word differently because it might have 683203954Srdivacky // meaningless bits set beyond the precision. 684203954Srdivacky unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD; 685203954Srdivacky integerPart MSWMask; 686203954Srdivacky if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1; 687203954Srdivacky else { 688203954Srdivacky MSWMask = ~integerPart(0); 689203954Srdivacky BitsInMSW = APINT_BITS_PER_WORD; 690203954Srdivacky } 691203954Srdivacky 692203954Srdivacky unsigned i = getNumWords(); 693203954Srdivacky integerPart MSW = pVal[i-1] & MSWMask; 694203954Srdivacky if (MSW) 695263508Sdim return llvm::countLeadingZeros(MSW) - (APINT_BITS_PER_WORD - BitsInMSW); 696203954Srdivacky 697203954Srdivacky unsigned Count = BitsInMSW; 698203954Srdivacky for (--i; i > 0u; --i) { 699193323Sed if (pVal[i-1] == 0) 700193323Sed Count += APINT_BITS_PER_WORD; 701193323Sed else { 702263508Sdim Count += llvm::countLeadingZeros(pVal[i-1]); 703193323Sed break; 704193323Sed } 705193323Sed } 706203954Srdivacky return Count; 707193323Sed} 708193323Sed 709193323Sedunsigned APInt::countLeadingOnes() const { 710193323Sed if (isSingleWord()) 711234353Sdim return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth)); 712193323Sed 713193323Sed unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD; 714193323Sed unsigned shift; 715193323Sed if (!highWordBits) { 716193323Sed highWordBits = APINT_BITS_PER_WORD; 717193323Sed shift = 0; 718193323Sed } else { 719193323Sed shift = APINT_BITS_PER_WORD - highWordBits; 720193323Sed } 721193323Sed int i = getNumWords() - 1; 722234353Sdim unsigned Count = CountLeadingOnes_64(pVal[i] << shift); 723193323Sed if (Count == highWordBits) { 724193323Sed for (i--; i >= 0; --i) { 725193323Sed if (pVal[i] == -1ULL) 726193323Sed Count += APINT_BITS_PER_WORD; 727193323Sed else { 728234353Sdim Count += CountLeadingOnes_64(pVal[i]); 729193323Sed break; 730193323Sed } 731193323Sed } 732193323Sed } 733193323Sed return Count; 734193323Sed} 735193323Sed 736193323Sedunsigned APInt::countTrailingZeros() const { 737193323Sed if (isSingleWord()) 738263508Sdim return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth); 739193323Sed unsigned Count = 0; 740193323Sed unsigned i = 0; 741193323Sed for (; i < getNumWords() && pVal[i] == 0; ++i) 742193323Sed Count += APINT_BITS_PER_WORD; 743193323Sed if (i < getNumWords()) 744263508Sdim Count += llvm::countTrailingZeros(pVal[i]); 745193323Sed return std::min(Count, BitWidth); 746193323Sed} 747193323Sed 748193323Sedunsigned APInt::countTrailingOnesSlowCase() const { 749193323Sed unsigned Count = 0; 750193323Sed unsigned i = 0; 751193323Sed for (; i < getNumWords() && pVal[i] == -1ULL; ++i) 752193323Sed Count += APINT_BITS_PER_WORD; 753193323Sed if (i < getNumWords()) 754193323Sed Count += CountTrailingOnes_64(pVal[i]); 755193323Sed return std::min(Count, BitWidth); 756193323Sed} 757193323Sed 758193323Sedunsigned APInt::countPopulationSlowCase() const { 759193323Sed unsigned Count = 0; 760193323Sed for (unsigned i = 0; i < getNumWords(); ++i) 761193323Sed Count += CountPopulation_64(pVal[i]); 762193323Sed return Count; 763193323Sed} 764193323Sed 765234353Sdim/// Perform a logical right-shift from Src to Dst, which must be equal or 766234353Sdim/// non-overlapping, of Words words, by Shift, which must be less than 64. 767234353Sdimstatic void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words, 768234353Sdim unsigned Shift) { 769234353Sdim uint64_t Carry = 0; 770234353Sdim for (int I = Words - 1; I >= 0; --I) { 771234353Sdim uint64_t Tmp = Src[I]; 772234353Sdim Dst[I] = (Tmp >> Shift) | Carry; 773234353Sdim Carry = Tmp << (64 - Shift); 774234353Sdim } 775234353Sdim} 776234353Sdim 777193323SedAPInt APInt::byteSwap() const { 778193323Sed assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!"); 779193323Sed if (BitWidth == 16) 780193323Sed return APInt(BitWidth, ByteSwap_16(uint16_t(VAL))); 781234353Sdim if (BitWidth == 32) 782193323Sed return APInt(BitWidth, ByteSwap_32(unsigned(VAL))); 783234353Sdim if (BitWidth == 48) { 784193323Sed unsigned Tmp1 = unsigned(VAL >> 16); 785193323Sed Tmp1 = ByteSwap_32(Tmp1); 786193323Sed uint16_t Tmp2 = uint16_t(VAL); 787193323Sed Tmp2 = ByteSwap_16(Tmp2); 788193323Sed return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1); 789234353Sdim } 790234353Sdim if (BitWidth == 64) 791193323Sed return APInt(BitWidth, ByteSwap_64(VAL)); 792234353Sdim 793234353Sdim APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0); 794234353Sdim for (unsigned I = 0, N = getNumWords(); I != N; ++I) 795234353Sdim Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]); 796234353Sdim if (Result.BitWidth != BitWidth) { 797234353Sdim lshrNear(Result.pVal, Result.pVal, getNumWords(), 798234353Sdim Result.BitWidth - BitWidth); 799234353Sdim Result.BitWidth = BitWidth; 800193323Sed } 801234353Sdim return Result; 802193323Sed} 803193323Sed 804198090SrdivackyAPInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1, 805193323Sed const APInt& API2) { 806193323Sed APInt A = API1, B = API2; 807193323Sed while (!!B) { 808193323Sed APInt T = B; 809193323Sed B = APIntOps::urem(A, B); 810193323Sed A = T; 811193323Sed } 812193323Sed return A; 813193323Sed} 814193323Sed 815193323SedAPInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) { 816193323Sed union { 817193323Sed double D; 818193323Sed uint64_t I; 819193323Sed } T; 820193323Sed T.D = Double; 821193323Sed 822193323Sed // Get the sign bit from the highest order bit 823193323Sed bool isNeg = T.I >> 63; 824193323Sed 825193323Sed // Get the 11-bit exponent and adjust for the 1023 bit bias 826193323Sed int64_t exp = ((T.I >> 52) & 0x7ff) - 1023; 827193323Sed 828193323Sed // If the exponent is negative, the value is < 0 so just return 0. 829193323Sed if (exp < 0) 830193323Sed return APInt(width, 0u); 831193323Sed 832193323Sed // Extract the mantissa by clearing the top 12 bits (sign + exponent). 833193323Sed uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52; 834193323Sed 835193323Sed // If the exponent doesn't shift all bits out of the mantissa 836193323Sed if (exp < 52) 837198090Srdivacky return isNeg ? -APInt(width, mantissa >> (52 - exp)) : 838193323Sed APInt(width, mantissa >> (52 - exp)); 839193323Sed 840193323Sed // If the client didn't provide enough bits for us to shift the mantissa into 841193323Sed // then the result is undefined, just return 0 842193323Sed if (width <= exp - 52) 843193323Sed return APInt(width, 0); 844193323Sed 845193323Sed // Otherwise, we have to shift the mantissa bits up to the right location 846193323Sed APInt Tmp(width, mantissa); 847193323Sed Tmp = Tmp.shl((unsigned)exp - 52); 848193323Sed return isNeg ? -Tmp : Tmp; 849193323Sed} 850193323Sed 851198090Srdivacky/// RoundToDouble - This function converts this APInt to a double. 852193323Sed/// The layout for double is as following (IEEE Standard 754): 853193323Sed/// -------------------------------------- 854193323Sed/// | Sign Exponent Fraction Bias | 855193323Sed/// |-------------------------------------- | 856193323Sed/// | 1[63] 11[62-52] 52[51-00] 1023 | 857198090Srdivacky/// -------------------------------------- 858193323Seddouble APInt::roundToDouble(bool isSigned) const { 859193323Sed 860193323Sed // Handle the simple case where the value is contained in one uint64_t. 861198090Srdivacky // It is wrong to optimize getWord(0) to VAL; there might be more than one word. 862193323Sed if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) { 863193323Sed if (isSigned) { 864198090Srdivacky int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth); 865193323Sed return double(sext); 866193323Sed } else 867198090Srdivacky return double(getWord(0)); 868193323Sed } 869193323Sed 870193323Sed // Determine if the value is negative. 871193323Sed bool isNeg = isSigned ? (*this)[BitWidth-1] : false; 872193323Sed 873193323Sed // Construct the absolute value if we're negative. 874193323Sed APInt Tmp(isNeg ? -(*this) : (*this)); 875193323Sed 876193323Sed // Figure out how many bits we're using. 877193323Sed unsigned n = Tmp.getActiveBits(); 878193323Sed 879193323Sed // The exponent (without bias normalization) is just the number of bits 880193323Sed // we are using. Note that the sign bit is gone since we constructed the 881193323Sed // absolute value. 882193323Sed uint64_t exp = n; 883193323Sed 884193323Sed // Return infinity for exponent overflow 885193323Sed if (exp > 1023) { 886193323Sed if (!isSigned || !isNeg) 887193323Sed return std::numeric_limits<double>::infinity(); 888198090Srdivacky else 889193323Sed return -std::numeric_limits<double>::infinity(); 890193323Sed } 891193323Sed exp += 1023; // Increment for 1023 bias 892193323Sed 893193323Sed // Number of bits in mantissa is 52. To obtain the mantissa value, we must 894193323Sed // extract the high 52 bits from the correct words in pVal. 895193323Sed uint64_t mantissa; 896193323Sed unsigned hiWord = whichWord(n-1); 897193323Sed if (hiWord == 0) { 898193323Sed mantissa = Tmp.pVal[0]; 899193323Sed if (n > 52) 900193323Sed mantissa >>= n - 52; // shift down, we want the top 52 bits. 901193323Sed } else { 902193323Sed assert(hiWord > 0 && "huh?"); 903193323Sed uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD); 904193323Sed uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD); 905193323Sed mantissa = hibits | lobits; 906193323Sed } 907193323Sed 908193323Sed // The leading bit of mantissa is implicit, so get rid of it. 909193323Sed uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0; 910193323Sed union { 911193323Sed double D; 912193323Sed uint64_t I; 913193323Sed } T; 914193323Sed T.I = sign | (exp << 52) | mantissa; 915193323Sed return T.D; 916193323Sed} 917193323Sed 918193323Sed// Truncate to new width. 919218893SdimAPInt APInt::trunc(unsigned width) const { 920193323Sed assert(width < BitWidth && "Invalid APInt Truncate request"); 921193323Sed assert(width && "Can't truncate to 0 bits"); 922218893Sdim 923218893Sdim if (width <= APINT_BITS_PER_WORD) 924218893Sdim return APInt(width, getRawData()[0]); 925218893Sdim 926218893Sdim APInt Result(getMemory(getNumWords(width)), width); 927218893Sdim 928218893Sdim // Copy full words. 929218893Sdim unsigned i; 930218893Sdim for (i = 0; i != width / APINT_BITS_PER_WORD; i++) 931218893Sdim Result.pVal[i] = pVal[i]; 932218893Sdim 933218893Sdim // Truncate and copy any partial word. 934218893Sdim unsigned bits = (0 - width) % APINT_BITS_PER_WORD; 935218893Sdim if (bits != 0) 936218893Sdim Result.pVal[i] = pVal[i] << bits >> bits; 937218893Sdim 938218893Sdim return Result; 939193323Sed} 940193323Sed 941193323Sed// Sign extend to a new width. 942218893SdimAPInt APInt::sext(unsigned width) const { 943193323Sed assert(width > BitWidth && "Invalid APInt SignExtend request"); 944218893Sdim 945218893Sdim if (width <= APINT_BITS_PER_WORD) { 946218893Sdim uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth); 947218893Sdim val = (int64_t)val >> (width - BitWidth); 948218893Sdim return APInt(width, val >> (APINT_BITS_PER_WORD - width)); 949193323Sed } 950193323Sed 951218893Sdim APInt Result(getMemory(getNumWords(width)), width); 952193323Sed 953218893Sdim // Copy full words. 954218893Sdim unsigned i; 955218893Sdim uint64_t word = 0; 956218893Sdim for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) { 957218893Sdim word = getRawData()[i]; 958218893Sdim Result.pVal[i] = word; 959193323Sed } 960193323Sed 961218893Sdim // Read and sign-extend any partial word. 962218893Sdim unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD; 963218893Sdim if (bits != 0) 964218893Sdim word = (int64_t)getRawData()[i] << bits >> bits; 965218893Sdim else 966218893Sdim word = (int64_t)word >> (APINT_BITS_PER_WORD - 1); 967218893Sdim 968218893Sdim // Write remaining full words. 969218893Sdim for (; i != width / APINT_BITS_PER_WORD; i++) { 970218893Sdim Result.pVal[i] = word; 971218893Sdim word = (int64_t)word >> (APINT_BITS_PER_WORD - 1); 972193323Sed } 973218893Sdim 974218893Sdim // Write any partial word. 975218893Sdim bits = (0 - width) % APINT_BITS_PER_WORD; 976218893Sdim if (bits != 0) 977218893Sdim Result.pVal[i] = word << bits >> bits; 978218893Sdim 979218893Sdim return Result; 980193323Sed} 981193323Sed 982193323Sed// Zero extend to a new width. 983218893SdimAPInt APInt::zext(unsigned width) const { 984193323Sed assert(width > BitWidth && "Invalid APInt ZeroExtend request"); 985218893Sdim 986218893Sdim if (width <= APINT_BITS_PER_WORD) 987218893Sdim return APInt(width, VAL); 988218893Sdim 989218893Sdim APInt Result(getMemory(getNumWords(width)), width); 990218893Sdim 991218893Sdim // Copy words. 992218893Sdim unsigned i; 993218893Sdim for (i = 0; i != getNumWords(); i++) 994218893Sdim Result.pVal[i] = getRawData()[i]; 995218893Sdim 996218893Sdim // Zero remaining words. 997218893Sdim memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE); 998218893Sdim 999218893Sdim return Result; 1000193323Sed} 1001193323Sed 1002218893SdimAPInt APInt::zextOrTrunc(unsigned width) const { 1003193323Sed if (BitWidth < width) 1004193323Sed return zext(width); 1005193323Sed if (BitWidth > width) 1006193323Sed return trunc(width); 1007193323Sed return *this; 1008193323Sed} 1009193323Sed 1010218893SdimAPInt APInt::sextOrTrunc(unsigned width) const { 1011193323Sed if (BitWidth < width) 1012193323Sed return sext(width); 1013193323Sed if (BitWidth > width) 1014193323Sed return trunc(width); 1015193323Sed return *this; 1016193323Sed} 1017193323Sed 1018234353SdimAPInt APInt::zextOrSelf(unsigned width) const { 1019234353Sdim if (BitWidth < width) 1020234353Sdim return zext(width); 1021234353Sdim return *this; 1022234353Sdim} 1023234353Sdim 1024234353SdimAPInt APInt::sextOrSelf(unsigned width) const { 1025234353Sdim if (BitWidth < width) 1026234353Sdim return sext(width); 1027234353Sdim return *this; 1028234353Sdim} 1029234353Sdim 1030193323Sed/// Arithmetic right-shift this APInt by shiftAmt. 1031193323Sed/// @brief Arithmetic right-shift function. 1032193323SedAPInt APInt::ashr(const APInt &shiftAmt) const { 1033193323Sed return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth)); 1034193323Sed} 1035193323Sed 1036193323Sed/// Arithmetic right-shift this APInt by shiftAmt. 1037193323Sed/// @brief Arithmetic right-shift function. 1038193323SedAPInt APInt::ashr(unsigned shiftAmt) const { 1039193323Sed assert(shiftAmt <= BitWidth && "Invalid shift amount"); 1040193323Sed // Handle a degenerate case 1041193323Sed if (shiftAmt == 0) 1042193323Sed return *this; 1043193323Sed 1044193323Sed // Handle single word shifts with built-in ashr 1045193323Sed if (isSingleWord()) { 1046193323Sed if (shiftAmt == BitWidth) 1047193323Sed return APInt(BitWidth, 0); // undefined 1048193323Sed else { 1049193323Sed unsigned SignBit = APINT_BITS_PER_WORD - BitWidth; 1050198090Srdivacky return APInt(BitWidth, 1051193323Sed (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt)); 1052193323Sed } 1053193323Sed } 1054193323Sed 1055193323Sed // If all the bits were shifted out, the result is, technically, undefined. 1056193323Sed // We return -1 if it was negative, 0 otherwise. We check this early to avoid 1057193323Sed // issues in the algorithm below. 1058193323Sed if (shiftAmt == BitWidth) { 1059193323Sed if (isNegative()) 1060193323Sed return APInt(BitWidth, -1ULL, true); 1061193323Sed else 1062193323Sed return APInt(BitWidth, 0); 1063193323Sed } 1064193323Sed 1065193323Sed // Create some space for the result. 1066193323Sed uint64_t * val = new uint64_t[getNumWords()]; 1067193323Sed 1068193323Sed // Compute some values needed by the following shift algorithms 1069193323Sed unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word 1070193323Sed unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift 1071193323Sed unsigned breakWord = getNumWords() - 1 - offset; // last word affected 1072193323Sed unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word? 1073193323Sed if (bitsInWord == 0) 1074193323Sed bitsInWord = APINT_BITS_PER_WORD; 1075193323Sed 1076193323Sed // If we are shifting whole words, just move whole words 1077193323Sed if (wordShift == 0) { 1078193323Sed // Move the words containing significant bits 1079193323Sed for (unsigned i = 0; i <= breakWord; ++i) 1080193323Sed val[i] = pVal[i+offset]; // move whole word 1081193323Sed 1082193323Sed // Adjust the top significant word for sign bit fill, if negative 1083193323Sed if (isNegative()) 1084193323Sed if (bitsInWord < APINT_BITS_PER_WORD) 1085193323Sed val[breakWord] |= ~0ULL << bitsInWord; // set high bits 1086193323Sed } else { 1087198090Srdivacky // Shift the low order words 1088193323Sed for (unsigned i = 0; i < breakWord; ++i) { 1089193323Sed // This combines the shifted corresponding word with the low bits from 1090193323Sed // the next word (shifted into this word's high bits). 1091198090Srdivacky val[i] = (pVal[i+offset] >> wordShift) | 1092193323Sed (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); 1093193323Sed } 1094193323Sed 1095193323Sed // Shift the break word. In this case there are no bits from the next word 1096193323Sed // to include in this word. 1097193323Sed val[breakWord] = pVal[breakWord+offset] >> wordShift; 1098193323Sed 1099193323Sed // Deal with sign extenstion in the break word, and possibly the word before 1100193323Sed // it. 1101193323Sed if (isNegative()) { 1102193323Sed if (wordShift > bitsInWord) { 1103193323Sed if (breakWord > 0) 1104198090Srdivacky val[breakWord-1] |= 1105193323Sed ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord)); 1106193323Sed val[breakWord] |= ~0ULL; 1107198090Srdivacky } else 1108193323Sed val[breakWord] |= (~0ULL << (bitsInWord - wordShift)); 1109193323Sed } 1110193323Sed } 1111193323Sed 1112193323Sed // Remaining words are 0 or -1, just assign them. 1113193323Sed uint64_t fillValue = (isNegative() ? -1ULL : 0); 1114193323Sed for (unsigned i = breakWord+1; i < getNumWords(); ++i) 1115193323Sed val[i] = fillValue; 1116193323Sed return APInt(val, BitWidth).clearUnusedBits(); 1117193323Sed} 1118193323Sed 1119193323Sed/// Logical right-shift this APInt by shiftAmt. 1120193323Sed/// @brief Logical right-shift function. 1121193323SedAPInt APInt::lshr(const APInt &shiftAmt) const { 1122193323Sed return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth)); 1123193323Sed} 1124193323Sed 1125193323Sed/// Logical right-shift this APInt by shiftAmt. 1126193323Sed/// @brief Logical right-shift function. 1127193323SedAPInt APInt::lshr(unsigned shiftAmt) const { 1128193323Sed if (isSingleWord()) { 1129234353Sdim if (shiftAmt >= BitWidth) 1130193323Sed return APInt(BitWidth, 0); 1131198090Srdivacky else 1132193323Sed return APInt(BitWidth, this->VAL >> shiftAmt); 1133193323Sed } 1134193323Sed 1135193323Sed // If all the bits were shifted out, the result is 0. This avoids issues 1136193323Sed // with shifting by the size of the integer type, which produces undefined 1137193323Sed // results. We define these "undefined results" to always be 0. 1138239462Sdim if (shiftAmt >= BitWidth) 1139193323Sed return APInt(BitWidth, 0); 1140193323Sed 1141193323Sed // If none of the bits are shifted out, the result is *this. This avoids 1142198090Srdivacky // issues with shifting by the size of the integer type, which produces 1143193323Sed // undefined results in the code below. This is also an optimization. 1144193323Sed if (shiftAmt == 0) 1145193323Sed return *this; 1146193323Sed 1147193323Sed // Create some space for the result. 1148193323Sed uint64_t * val = new uint64_t[getNumWords()]; 1149193323Sed 1150193323Sed // If we are shifting less than a word, compute the shift with a simple carry 1151193323Sed if (shiftAmt < APINT_BITS_PER_WORD) { 1152234353Sdim lshrNear(val, pVal, getNumWords(), shiftAmt); 1153193323Sed return APInt(val, BitWidth).clearUnusedBits(); 1154193323Sed } 1155193323Sed 1156193323Sed // Compute some values needed by the remaining shift algorithms 1157193323Sed unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; 1158193323Sed unsigned offset = shiftAmt / APINT_BITS_PER_WORD; 1159193323Sed 1160193323Sed // If we are shifting whole words, just move whole words 1161193323Sed if (wordShift == 0) { 1162193323Sed for (unsigned i = 0; i < getNumWords() - offset; ++i) 1163193323Sed val[i] = pVal[i+offset]; 1164193323Sed for (unsigned i = getNumWords()-offset; i < getNumWords(); i++) 1165193323Sed val[i] = 0; 1166193323Sed return APInt(val,BitWidth).clearUnusedBits(); 1167193323Sed } 1168193323Sed 1169198090Srdivacky // Shift the low order words 1170193323Sed unsigned breakWord = getNumWords() - offset -1; 1171193323Sed for (unsigned i = 0; i < breakWord; ++i) 1172193323Sed val[i] = (pVal[i+offset] >> wordShift) | 1173193323Sed (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); 1174193323Sed // Shift the break word. 1175193323Sed val[breakWord] = pVal[breakWord+offset] >> wordShift; 1176193323Sed 1177193323Sed // Remaining words are 0 1178193323Sed for (unsigned i = breakWord+1; i < getNumWords(); ++i) 1179193323Sed val[i] = 0; 1180193323Sed return APInt(val, BitWidth).clearUnusedBits(); 1181193323Sed} 1182193323Sed 1183193323Sed/// Left-shift this APInt by shiftAmt. 1184193323Sed/// @brief Left-shift function. 1185193323SedAPInt APInt::shl(const APInt &shiftAmt) const { 1186193323Sed // It's undefined behavior in C to shift by BitWidth or greater. 1187193323Sed return shl((unsigned)shiftAmt.getLimitedValue(BitWidth)); 1188193323Sed} 1189193323Sed 1190193323SedAPInt APInt::shlSlowCase(unsigned shiftAmt) const { 1191193323Sed // If all the bits were shifted out, the result is 0. This avoids issues 1192193323Sed // with shifting by the size of the integer type, which produces undefined 1193193323Sed // results. We define these "undefined results" to always be 0. 1194193323Sed if (shiftAmt == BitWidth) 1195193323Sed return APInt(BitWidth, 0); 1196193323Sed 1197193323Sed // If none of the bits are shifted out, the result is *this. This avoids a 1198193323Sed // lshr by the words size in the loop below which can produce incorrect 1199193323Sed // results. It also avoids the expensive computation below for a common case. 1200193323Sed if (shiftAmt == 0) 1201193323Sed return *this; 1202193323Sed 1203193323Sed // Create some space for the result. 1204193323Sed uint64_t * val = new uint64_t[getNumWords()]; 1205193323Sed 1206193323Sed // If we are shifting less than a word, do it the easy way 1207193323Sed if (shiftAmt < APINT_BITS_PER_WORD) { 1208193323Sed uint64_t carry = 0; 1209193323Sed for (unsigned i = 0; i < getNumWords(); i++) { 1210193323Sed val[i] = pVal[i] << shiftAmt | carry; 1211193323Sed carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt); 1212193323Sed } 1213193323Sed return APInt(val, BitWidth).clearUnusedBits(); 1214193323Sed } 1215193323Sed 1216193323Sed // Compute some values needed by the remaining shift algorithms 1217193323Sed unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; 1218193323Sed unsigned offset = shiftAmt / APINT_BITS_PER_WORD; 1219193323Sed 1220193323Sed // If we are shifting whole words, just move whole words 1221193323Sed if (wordShift == 0) { 1222193323Sed for (unsigned i = 0; i < offset; i++) 1223193323Sed val[i] = 0; 1224193323Sed for (unsigned i = offset; i < getNumWords(); i++) 1225193323Sed val[i] = pVal[i-offset]; 1226193323Sed return APInt(val,BitWidth).clearUnusedBits(); 1227193323Sed } 1228193323Sed 1229193323Sed // Copy whole words from this to Result. 1230193323Sed unsigned i = getNumWords() - 1; 1231193323Sed for (; i > offset; --i) 1232193323Sed val[i] = pVal[i-offset] << wordShift | 1233193323Sed pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift); 1234193323Sed val[offset] = pVal[0] << wordShift; 1235193323Sed for (i = 0; i < offset; ++i) 1236193323Sed val[i] = 0; 1237193323Sed return APInt(val, BitWidth).clearUnusedBits(); 1238193323Sed} 1239193323Sed 1240193323SedAPInt APInt::rotl(const APInt &rotateAmt) const { 1241193323Sed return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth)); 1242193323Sed} 1243193323Sed 1244193323SedAPInt APInt::rotl(unsigned rotateAmt) const { 1245234353Sdim rotateAmt %= BitWidth; 1246193323Sed if (rotateAmt == 0) 1247193323Sed return *this; 1248234353Sdim return shl(rotateAmt) | lshr(BitWidth - rotateAmt); 1249193323Sed} 1250193323Sed 1251193323SedAPInt APInt::rotr(const APInt &rotateAmt) const { 1252193323Sed return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth)); 1253193323Sed} 1254193323Sed 1255193323SedAPInt APInt::rotr(unsigned rotateAmt) const { 1256234353Sdim rotateAmt %= BitWidth; 1257193323Sed if (rotateAmt == 0) 1258193323Sed return *this; 1259234353Sdim return lshr(rotateAmt) | shl(BitWidth - rotateAmt); 1260193323Sed} 1261193323Sed 1262193323Sed// Square Root - this method computes and returns the square root of "this". 1263193323Sed// Three mechanisms are used for computation. For small values (<= 5 bits), 1264193323Sed// a table lookup is done. This gets some performance for common cases. For 1265193323Sed// values using less than 52 bits, the value is converted to double and then 1266193323Sed// the libc sqrt function is called. The result is rounded and then converted 1267193323Sed// back to a uint64_t which is then used to construct the result. Finally, 1268198090Srdivacky// the Babylonian method for computing square roots is used. 1269193323SedAPInt APInt::sqrt() const { 1270193323Sed 1271193323Sed // Determine the magnitude of the value. 1272193323Sed unsigned magnitude = getActiveBits(); 1273193323Sed 1274193323Sed // Use a fast table for some small values. This also gets rid of some 1275193323Sed // rounding errors in libc sqrt for small values. 1276193323Sed if (magnitude <= 5) { 1277193323Sed static const uint8_t results[32] = { 1278193323Sed /* 0 */ 0, 1279193323Sed /* 1- 2 */ 1, 1, 1280198090Srdivacky /* 3- 6 */ 2, 2, 2, 2, 1281193323Sed /* 7-12 */ 3, 3, 3, 3, 3, 3, 1282193323Sed /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4, 1283193323Sed /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1284193323Sed /* 31 */ 6 1285193323Sed }; 1286193323Sed return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]); 1287193323Sed } 1288193323Sed 1289193323Sed // If the magnitude of the value fits in less than 52 bits (the precision of 1290193323Sed // an IEEE double precision floating point value), then we can use the 1291193323Sed // libc sqrt function which will probably use a hardware sqrt computation. 1292193323Sed // This should be faster than the algorithm below. 1293193323Sed if (magnitude < 52) { 1294208599Srdivacky#if HAVE_ROUND 1295198090Srdivacky return APInt(BitWidth, 1296208599Srdivacky uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0]))))); 1297193323Sed#else 1298198090Srdivacky return APInt(BitWidth, 1299223017Sdim uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5)); 1300193323Sed#endif 1301193323Sed } 1302193323Sed 1303193323Sed // Okay, all the short cuts are exhausted. We must compute it. The following 1304193323Sed // is a classical Babylonian method for computing the square root. This code 1305193323Sed // was adapted to APINt from a wikipedia article on such computations. 1306193323Sed // See http://www.wikipedia.org/ and go to the page named 1307198090Srdivacky // Calculate_an_integer_square_root. 1308193323Sed unsigned nbits = BitWidth, i = 4; 1309193323Sed APInt testy(BitWidth, 16); 1310193323Sed APInt x_old(BitWidth, 1); 1311193323Sed APInt x_new(BitWidth, 0); 1312193323Sed APInt two(BitWidth, 2); 1313193323Sed 1314193323Sed // Select a good starting value using binary logarithms. 1315198090Srdivacky for (;; i += 2, testy = testy.shl(2)) 1316193323Sed if (i >= nbits || this->ule(testy)) { 1317193323Sed x_old = x_old.shl(i / 2); 1318193323Sed break; 1319193323Sed } 1320193323Sed 1321198090Srdivacky // Use the Babylonian method to arrive at the integer square root: 1322193323Sed for (;;) { 1323193323Sed x_new = (this->udiv(x_old) + x_old).udiv(two); 1324193323Sed if (x_old.ule(x_new)) 1325193323Sed break; 1326193323Sed x_old = x_new; 1327193323Sed } 1328193323Sed 1329193323Sed // Make sure we return the closest approximation 1330198090Srdivacky // NOTE: The rounding calculation below is correct. It will produce an 1331193323Sed // off-by-one discrepancy with results from pari/gp. That discrepancy has been 1332198090Srdivacky // determined to be a rounding issue with pari/gp as it begins to use a 1333193323Sed // floating point representation after 192 bits. There are no discrepancies 1334193323Sed // between this algorithm and pari/gp for bit widths < 192 bits. 1335193323Sed APInt square(x_old * x_old); 1336193323Sed APInt nextSquare((x_old + 1) * (x_old +1)); 1337193323Sed if (this->ult(square)) 1338193323Sed return x_old; 1339234353Sdim assert(this->ule(nextSquare) && "Error in APInt::sqrt computation"); 1340234353Sdim APInt midpoint((nextSquare - square).udiv(two)); 1341234353Sdim APInt offset(*this - square); 1342234353Sdim if (offset.ult(midpoint)) 1343234353Sdim return x_old; 1344193323Sed return x_old + 1; 1345193323Sed} 1346193323Sed 1347193323Sed/// Computes the multiplicative inverse of this APInt for a given modulo. The 1348193323Sed/// iterative extended Euclidean algorithm is used to solve for this value, 1349193323Sed/// however we simplify it to speed up calculating only the inverse, and take 1350193323Sed/// advantage of div+rem calculations. We also use some tricks to avoid copying 1351193323Sed/// (potentially large) APInts around. 1352193323SedAPInt APInt::multiplicativeInverse(const APInt& modulo) const { 1353193323Sed assert(ult(modulo) && "This APInt must be smaller than the modulo"); 1354193323Sed 1355193323Sed // Using the properties listed at the following web page (accessed 06/21/08): 1356193323Sed // http://www.numbertheory.org/php/euclid.html 1357193323Sed // (especially the properties numbered 3, 4 and 9) it can be proved that 1358193323Sed // BitWidth bits suffice for all the computations in the algorithm implemented 1359193323Sed // below. More precisely, this number of bits suffice if the multiplicative 1360193323Sed // inverse exists, but may not suffice for the general extended Euclidean 1361193323Sed // algorithm. 1362193323Sed 1363193323Sed APInt r[2] = { modulo, *this }; 1364193323Sed APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) }; 1365193323Sed APInt q(BitWidth, 0); 1366198090Srdivacky 1367193323Sed unsigned i; 1368193323Sed for (i = 0; r[i^1] != 0; i ^= 1) { 1369193323Sed // An overview of the math without the confusing bit-flipping: 1370193323Sed // q = r[i-2] / r[i-1] 1371193323Sed // r[i] = r[i-2] % r[i-1] 1372193323Sed // t[i] = t[i-2] - t[i-1] * q 1373193323Sed udivrem(r[i], r[i^1], q, r[i]); 1374193323Sed t[i] -= t[i^1] * q; 1375193323Sed } 1376193323Sed 1377193323Sed // If this APInt and the modulo are not coprime, there is no multiplicative 1378193323Sed // inverse, so return 0. We check this by looking at the next-to-last 1379193323Sed // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean 1380193323Sed // algorithm. 1381193323Sed if (r[i] != 1) 1382193323Sed return APInt(BitWidth, 0); 1383193323Sed 1384193323Sed // The next-to-last t is the multiplicative inverse. However, we are 1385193323Sed // interested in a positive inverse. Calcuate a positive one from a negative 1386193323Sed // one if necessary. A simple addition of the modulo suffices because 1387193323Sed // abs(t[i]) is known to be less than *this/2 (see the link above). 1388193323Sed return t[i].isNegative() ? t[i] + modulo : t[i]; 1389193323Sed} 1390193323Sed 1391193323Sed/// Calculate the magic numbers required to implement a signed integer division 1392193323Sed/// by a constant as a sequence of multiplies, adds and shifts. Requires that 1393193323Sed/// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S. 1394193323Sed/// Warren, Jr., chapter 10. 1395193323SedAPInt::ms APInt::magic() const { 1396193323Sed const APInt& d = *this; 1397193323Sed unsigned p; 1398193323Sed APInt ad, anc, delta, q1, r1, q2, r2, t; 1399193323Sed APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); 1400193323Sed struct ms mag; 1401198090Srdivacky 1402193323Sed ad = d.abs(); 1403193323Sed t = signedMin + (d.lshr(d.getBitWidth() - 1)); 1404193323Sed anc = t - 1 - t.urem(ad); // absolute value of nc 1405193323Sed p = d.getBitWidth() - 1; // initialize p 1406193323Sed q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc) 1407193323Sed r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc)) 1408193323Sed q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d) 1409193323Sed r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d)) 1410193323Sed do { 1411193323Sed p = p + 1; 1412193323Sed q1 = q1<<1; // update q1 = 2p/abs(nc) 1413193323Sed r1 = r1<<1; // update r1 = rem(2p/abs(nc)) 1414193323Sed if (r1.uge(anc)) { // must be unsigned comparison 1415193323Sed q1 = q1 + 1; 1416193323Sed r1 = r1 - anc; 1417193323Sed } 1418193323Sed q2 = q2<<1; // update q2 = 2p/abs(d) 1419193323Sed r2 = r2<<1; // update r2 = rem(2p/abs(d)) 1420193323Sed if (r2.uge(ad)) { // must be unsigned comparison 1421193323Sed q2 = q2 + 1; 1422193323Sed r2 = r2 - ad; 1423193323Sed } 1424193323Sed delta = ad - r2; 1425219077Sdim } while (q1.ult(delta) || (q1 == delta && r1 == 0)); 1426198090Srdivacky 1427193323Sed mag.m = q2 + 1; 1428193323Sed if (d.isNegative()) mag.m = -mag.m; // resulting magic number 1429193323Sed mag.s = p - d.getBitWidth(); // resulting shift 1430193323Sed return mag; 1431193323Sed} 1432193323Sed 1433193323Sed/// Calculate the magic numbers required to implement an unsigned integer 1434193323Sed/// division by a constant as a sequence of multiplies, adds and shifts. 1435193323Sed/// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry 1436193323Sed/// S. Warren, Jr., chapter 10. 1437221345Sdim/// LeadingZeros can be used to simplify the calculation if the upper bits 1438221345Sdim/// of the divided value are known zero. 1439221345SdimAPInt::mu APInt::magicu(unsigned LeadingZeros) const { 1440193323Sed const APInt& d = *this; 1441193323Sed unsigned p; 1442193323Sed APInt nc, delta, q1, r1, q2, r2; 1443193323Sed struct mu magu; 1444193323Sed magu.a = 0; // initialize "add" indicator 1445221345Sdim APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros); 1446193323Sed APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); 1447193323Sed APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth()); 1448193323Sed 1449239462Sdim nc = allOnes - (allOnes - d).urem(d); 1450193323Sed p = d.getBitWidth() - 1; // initialize p 1451193323Sed q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc 1452193323Sed r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc) 1453193323Sed q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d 1454193323Sed r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d) 1455193323Sed do { 1456193323Sed p = p + 1; 1457193323Sed if (r1.uge(nc - r1)) { 1458193323Sed q1 = q1 + q1 + 1; // update q1 1459193323Sed r1 = r1 + r1 - nc; // update r1 1460193323Sed } 1461193323Sed else { 1462193323Sed q1 = q1+q1; // update q1 1463193323Sed r1 = r1+r1; // update r1 1464193323Sed } 1465193323Sed if ((r2 + 1).uge(d - r2)) { 1466193323Sed if (q2.uge(signedMax)) magu.a = 1; 1467193323Sed q2 = q2+q2 + 1; // update q2 1468193323Sed r2 = r2+r2 + 1 - d; // update r2 1469193323Sed } 1470193323Sed else { 1471193323Sed if (q2.uge(signedMin)) magu.a = 1; 1472193323Sed q2 = q2+q2; // update q2 1473193323Sed r2 = r2+r2 + 1; // update r2 1474193323Sed } 1475193323Sed delta = d - 1 - r2; 1476193323Sed } while (p < d.getBitWidth()*2 && 1477193323Sed (q1.ult(delta) || (q1 == delta && r1 == 0))); 1478193323Sed magu.m = q2 + 1; // resulting magic number 1479193323Sed magu.s = p - d.getBitWidth(); // resulting shift 1480193323Sed return magu; 1481193323Sed} 1482193323Sed 1483193323Sed/// Implementation of Knuth's Algorithm D (Division of nonnegative integers) 1484193323Sed/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The 1485193323Sed/// variables here have the same names as in the algorithm. Comments explain 1486193323Sed/// the algorithm and any deviation from it. 1487193323Sedstatic void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, 1488193323Sed unsigned m, unsigned n) { 1489193323Sed assert(u && "Must provide dividend"); 1490193323Sed assert(v && "Must provide divisor"); 1491193323Sed assert(q && "Must provide quotient"); 1492193323Sed assert(u != v && u != q && v != q && "Must us different memory"); 1493193323Sed assert(n>1 && "n must be > 1"); 1494193323Sed 1495193323Sed // Knuth uses the value b as the base of the number system. In our case b 1496193323Sed // is 2^31 so we just set it to -1u. 1497193323Sed uint64_t b = uint64_t(1) << 32; 1498193323Sed 1499193323Sed#if 0 1500202375Srdivacky DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n'); 1501202375Srdivacky DEBUG(dbgs() << "KnuthDiv: original:"); 1502202375Srdivacky DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1503202375Srdivacky DEBUG(dbgs() << " by"); 1504202375Srdivacky DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]); 1505202375Srdivacky DEBUG(dbgs() << '\n'); 1506193323Sed#endif 1507198090Srdivacky // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of 1508198090Srdivacky // u and v by d. Note that we have taken Knuth's advice here to use a power 1509198090Srdivacky // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of 1510198090Srdivacky // 2 allows us to shift instead of multiply and it is easy to determine the 1511193323Sed // shift amount from the leading zeros. We are basically normalizing the u 1512193323Sed // and v so that its high bits are shifted to the top of v's range without 1513193323Sed // overflow. Note that this can require an extra word in u so that u must 1514193323Sed // be of length m+n+1. 1515263508Sdim unsigned shift = countLeadingZeros(v[n-1]); 1516193323Sed unsigned v_carry = 0; 1517193323Sed unsigned u_carry = 0; 1518193323Sed if (shift) { 1519193323Sed for (unsigned i = 0; i < m+n; ++i) { 1520193323Sed unsigned u_tmp = u[i] >> (32 - shift); 1521193323Sed u[i] = (u[i] << shift) | u_carry; 1522193323Sed u_carry = u_tmp; 1523193323Sed } 1524193323Sed for (unsigned i = 0; i < n; ++i) { 1525193323Sed unsigned v_tmp = v[i] >> (32 - shift); 1526193323Sed v[i] = (v[i] << shift) | v_carry; 1527193323Sed v_carry = v_tmp; 1528193323Sed } 1529193323Sed } 1530193323Sed u[m+n] = u_carry; 1531193323Sed#if 0 1532202375Srdivacky DEBUG(dbgs() << "KnuthDiv: normal:"); 1533202375Srdivacky DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1534202375Srdivacky DEBUG(dbgs() << " by"); 1535202375Srdivacky DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]); 1536202375Srdivacky DEBUG(dbgs() << '\n'); 1537193323Sed#endif 1538193323Sed 1539193323Sed // D2. [Initialize j.] Set j to m. This is the loop counter over the places. 1540193323Sed int j = m; 1541193323Sed do { 1542202375Srdivacky DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n'); 1543198090Srdivacky // D3. [Calculate q'.]. 1544193323Sed // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q') 1545193323Sed // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r') 1546193323Sed // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease 1547193323Sed // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test 1548193323Sed // on v[n-2] determines at high speed most of the cases in which the trial 1549198090Srdivacky // value qp is one too large, and it eliminates all cases where qp is two 1550198090Srdivacky // too large. 1551193323Sed uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]); 1552202375Srdivacky DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n'); 1553193323Sed uint64_t qp = dividend / v[n-1]; 1554193323Sed uint64_t rp = dividend % v[n-1]; 1555193323Sed if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) { 1556193323Sed qp--; 1557193323Sed rp += v[n-1]; 1558193323Sed if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2])) 1559193323Sed qp--; 1560193323Sed } 1561202375Srdivacky DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n'); 1562193323Sed 1563193323Sed // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with 1564193323Sed // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation 1565193323Sed // consists of a simple multiplication by a one-place number, combined with 1566198090Srdivacky // a subtraction. 1567193323Sed bool isNeg = false; 1568193323Sed for (unsigned i = 0; i < n; ++i) { 1569193323Sed uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32); 1570193323Sed uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]); 1571193323Sed bool borrow = subtrahend > u_tmp; 1572202375Srdivacky DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp 1573198090Srdivacky << ", subtrahend == " << subtrahend 1574198090Srdivacky << ", borrow = " << borrow << '\n'); 1575193323Sed 1576193323Sed uint64_t result = u_tmp - subtrahend; 1577193323Sed unsigned k = j + i; 1578193323Sed u[k++] = (unsigned)(result & (b-1)); // subtract low word 1579193323Sed u[k++] = (unsigned)(result >> 32); // subtract high word 1580193323Sed while (borrow && k <= m+n) { // deal with borrow to the left 1581193323Sed borrow = u[k] == 0; 1582193323Sed u[k]--; 1583193323Sed k++; 1584193323Sed } 1585193323Sed isNeg |= borrow; 1586202375Srdivacky DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " << 1587198090Srdivacky u[j+i+1] << '\n'); 1588193323Sed } 1589202375Srdivacky DEBUG(dbgs() << "KnuthDiv: after subtraction:"); 1590202375Srdivacky DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1591202375Srdivacky DEBUG(dbgs() << '\n'); 1592198090Srdivacky // The digits (u[j+n]...u[j]) should be kept positive; if the result of 1593198090Srdivacky // this step is actually negative, (u[j+n]...u[j]) should be left as the 1594193323Sed // true value plus b**(n+1), namely as the b's complement of 1595193323Sed // the true value, and a "borrow" to the left should be remembered. 1596193323Sed // 1597193323Sed if (isNeg) { 1598193323Sed bool carry = true; // true because b's complement is "complement + 1" 1599193323Sed for (unsigned i = 0; i <= m+n; ++i) { 1600193323Sed u[i] = ~u[i] + carry; // b's complement 1601193323Sed carry = carry && u[i] == 0; 1602193323Sed } 1603193323Sed } 1604202375Srdivacky DEBUG(dbgs() << "KnuthDiv: after complement:"); 1605202375Srdivacky DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1606202375Srdivacky DEBUG(dbgs() << '\n'); 1607193323Sed 1608198090Srdivacky // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was 1609193323Sed // negative, go to step D6; otherwise go on to step D7. 1610193323Sed q[j] = (unsigned)qp; 1611193323Sed if (isNeg) { 1612198090Srdivacky // D6. [Add back]. The probability that this step is necessary is very 1613193323Sed // small, on the order of only 2/b. Make sure that test data accounts for 1614198090Srdivacky // this possibility. Decrease q[j] by 1 1615193323Sed q[j]--; 1616198090Srdivacky // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]). 1617198090Srdivacky // A carry will occur to the left of u[j+n], and it should be ignored 1618193323Sed // since it cancels with the borrow that occurred in D4. 1619193323Sed bool carry = false; 1620193323Sed for (unsigned i = 0; i < n; i++) { 1621193323Sed unsigned limit = std::min(u[j+i],v[i]); 1622193323Sed u[j+i] += v[i] + carry; 1623193323Sed carry = u[j+i] < limit || (carry && u[j+i] == limit); 1624193323Sed } 1625193323Sed u[j+n] += carry; 1626193323Sed } 1627202375Srdivacky DEBUG(dbgs() << "KnuthDiv: after correction:"); 1628202375Srdivacky DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]); 1629202375Srdivacky DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n'); 1630193323Sed 1631193323Sed // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3. 1632193323Sed } while (--j >= 0); 1633193323Sed 1634202375Srdivacky DEBUG(dbgs() << "KnuthDiv: quotient:"); 1635202375Srdivacky DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]); 1636202375Srdivacky DEBUG(dbgs() << '\n'); 1637193323Sed 1638193323Sed // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired 1639193323Sed // remainder may be obtained by dividing u[...] by d. If r is non-null we 1640193323Sed // compute the remainder (urem uses this). 1641193323Sed if (r) { 1642193323Sed // The value d is expressed by the "shift" value above since we avoided 1643193323Sed // multiplication by d by using a shift left. So, all we have to do is 1644193323Sed // shift right here. In order to mak 1645193323Sed if (shift) { 1646193323Sed unsigned carry = 0; 1647202375Srdivacky DEBUG(dbgs() << "KnuthDiv: remainder:"); 1648193323Sed for (int i = n-1; i >= 0; i--) { 1649193323Sed r[i] = (u[i] >> shift) | carry; 1650193323Sed carry = u[i] << (32 - shift); 1651202375Srdivacky DEBUG(dbgs() << " " << r[i]); 1652193323Sed } 1653193323Sed } else { 1654193323Sed for (int i = n-1; i >= 0; i--) { 1655193323Sed r[i] = u[i]; 1656202375Srdivacky DEBUG(dbgs() << " " << r[i]); 1657193323Sed } 1658193323Sed } 1659202375Srdivacky DEBUG(dbgs() << '\n'); 1660193323Sed } 1661193323Sed#if 0 1662202375Srdivacky DEBUG(dbgs() << '\n'); 1663193323Sed#endif 1664193323Sed} 1665193323Sed 1666193323Sedvoid APInt::divide(const APInt LHS, unsigned lhsWords, 1667193323Sed const APInt &RHS, unsigned rhsWords, 1668193323Sed APInt *Quotient, APInt *Remainder) 1669193323Sed{ 1670193323Sed assert(lhsWords >= rhsWords && "Fractional result"); 1671193323Sed 1672198090Srdivacky // First, compose the values into an array of 32-bit words instead of 1673193323Sed // 64-bit words. This is a necessity of both the "short division" algorithm 1674203954Srdivacky // and the Knuth "classical algorithm" which requires there to be native 1675198090Srdivacky // operations for +, -, and * on an m bit value with an m*2 bit result. We 1676198090Srdivacky // can't use 64-bit operands here because we don't have native results of 1677198090Srdivacky // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't 1678193323Sed // work on large-endian machines. 1679193323Sed uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT); 1680193323Sed unsigned n = rhsWords * 2; 1681193323Sed unsigned m = (lhsWords * 2) - n; 1682193323Sed 1683193323Sed // Allocate space for the temporary values we need either on the stack, if 1684193323Sed // it will fit, or on the heap if it won't. 1685193323Sed unsigned SPACE[128]; 1686193323Sed unsigned *U = 0; 1687193323Sed unsigned *V = 0; 1688193323Sed unsigned *Q = 0; 1689193323Sed unsigned *R = 0; 1690193323Sed if ((Remainder?4:3)*n+2*m+1 <= 128) { 1691193323Sed U = &SPACE[0]; 1692193323Sed V = &SPACE[m+n+1]; 1693193323Sed Q = &SPACE[(m+n+1) + n]; 1694193323Sed if (Remainder) 1695193323Sed R = &SPACE[(m+n+1) + n + (m+n)]; 1696193323Sed } else { 1697193323Sed U = new unsigned[m + n + 1]; 1698193323Sed V = new unsigned[n]; 1699193323Sed Q = new unsigned[m+n]; 1700193323Sed if (Remainder) 1701193323Sed R = new unsigned[n]; 1702193323Sed } 1703193323Sed 1704193323Sed // Initialize the dividend 1705193323Sed memset(U, 0, (m+n+1)*sizeof(unsigned)); 1706193323Sed for (unsigned i = 0; i < lhsWords; ++i) { 1707193323Sed uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]); 1708193323Sed U[i * 2] = (unsigned)(tmp & mask); 1709193323Sed U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT)); 1710193323Sed } 1711193323Sed U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm. 1712193323Sed 1713193323Sed // Initialize the divisor 1714193323Sed memset(V, 0, (n)*sizeof(unsigned)); 1715193323Sed for (unsigned i = 0; i < rhsWords; ++i) { 1716193323Sed uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]); 1717193323Sed V[i * 2] = (unsigned)(tmp & mask); 1718193323Sed V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT)); 1719193323Sed } 1720193323Sed 1721193323Sed // initialize the quotient and remainder 1722193323Sed memset(Q, 0, (m+n) * sizeof(unsigned)); 1723193323Sed if (Remainder) 1724193323Sed memset(R, 0, n * sizeof(unsigned)); 1725193323Sed 1726198090Srdivacky // Now, adjust m and n for the Knuth division. n is the number of words in 1727193323Sed // the divisor. m is the number of words by which the dividend exceeds the 1728198090Srdivacky // divisor (i.e. m+n is the length of the dividend). These sizes must not 1729193323Sed // contain any zero words or the Knuth algorithm fails. 1730193323Sed for (unsigned i = n; i > 0 && V[i-1] == 0; i--) { 1731193323Sed n--; 1732193323Sed m++; 1733193323Sed } 1734193323Sed for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--) 1735193323Sed m--; 1736193323Sed 1737193323Sed // If we're left with only a single word for the divisor, Knuth doesn't work 1738193323Sed // so we implement the short division algorithm here. This is much simpler 1739193323Sed // and faster because we are certain that we can divide a 64-bit quantity 1740193323Sed // by a 32-bit quantity at hardware speed and short division is simply a 1741193323Sed // series of such operations. This is just like doing short division but we 1742193323Sed // are using base 2^32 instead of base 10. 1743193323Sed assert(n != 0 && "Divide by zero?"); 1744193323Sed if (n == 1) { 1745193323Sed unsigned divisor = V[0]; 1746193323Sed unsigned remainder = 0; 1747193323Sed for (int i = m+n-1; i >= 0; i--) { 1748193323Sed uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i]; 1749193323Sed if (partial_dividend == 0) { 1750193323Sed Q[i] = 0; 1751193323Sed remainder = 0; 1752193323Sed } else if (partial_dividend < divisor) { 1753193323Sed Q[i] = 0; 1754193323Sed remainder = (unsigned)partial_dividend; 1755193323Sed } else if (partial_dividend == divisor) { 1756193323Sed Q[i] = 1; 1757193323Sed remainder = 0; 1758193323Sed } else { 1759193323Sed Q[i] = (unsigned)(partial_dividend / divisor); 1760193323Sed remainder = (unsigned)(partial_dividend - (Q[i] * divisor)); 1761193323Sed } 1762193323Sed } 1763193323Sed if (R) 1764193323Sed R[0] = remainder; 1765193323Sed } else { 1766193323Sed // Now we're ready to invoke the Knuth classical divide algorithm. In this 1767193323Sed // case n > 1. 1768193323Sed KnuthDiv(U, V, Q, R, m, n); 1769193323Sed } 1770193323Sed 1771193323Sed // If the caller wants the quotient 1772193323Sed if (Quotient) { 1773193323Sed // Set up the Quotient value's memory. 1774193323Sed if (Quotient->BitWidth != LHS.BitWidth) { 1775193323Sed if (Quotient->isSingleWord()) 1776193323Sed Quotient->VAL = 0; 1777193323Sed else 1778193323Sed delete [] Quotient->pVal; 1779193323Sed Quotient->BitWidth = LHS.BitWidth; 1780193323Sed if (!Quotient->isSingleWord()) 1781193323Sed Quotient->pVal = getClearedMemory(Quotient->getNumWords()); 1782193323Sed } else 1783218893Sdim Quotient->clearAllBits(); 1784193323Sed 1785198090Srdivacky // The quotient is in Q. Reconstitute the quotient into Quotient's low 1786193323Sed // order words. 1787193323Sed if (lhsWords == 1) { 1788198090Srdivacky uint64_t tmp = 1789193323Sed uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2)); 1790193323Sed if (Quotient->isSingleWord()) 1791193323Sed Quotient->VAL = tmp; 1792193323Sed else 1793193323Sed Quotient->pVal[0] = tmp; 1794193323Sed } else { 1795193323Sed assert(!Quotient->isSingleWord() && "Quotient APInt not large enough"); 1796193323Sed for (unsigned i = 0; i < lhsWords; ++i) 1797198090Srdivacky Quotient->pVal[i] = 1798193323Sed uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2)); 1799193323Sed } 1800193323Sed } 1801193323Sed 1802193323Sed // If the caller wants the remainder 1803193323Sed if (Remainder) { 1804193323Sed // Set up the Remainder value's memory. 1805193323Sed if (Remainder->BitWidth != RHS.BitWidth) { 1806193323Sed if (Remainder->isSingleWord()) 1807193323Sed Remainder->VAL = 0; 1808193323Sed else 1809193323Sed delete [] Remainder->pVal; 1810193323Sed Remainder->BitWidth = RHS.BitWidth; 1811193323Sed if (!Remainder->isSingleWord()) 1812193323Sed Remainder->pVal = getClearedMemory(Remainder->getNumWords()); 1813193323Sed } else 1814218893Sdim Remainder->clearAllBits(); 1815193323Sed 1816193323Sed // The remainder is in R. Reconstitute the remainder into Remainder's low 1817193323Sed // order words. 1818193323Sed if (rhsWords == 1) { 1819198090Srdivacky uint64_t tmp = 1820193323Sed uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2)); 1821193323Sed if (Remainder->isSingleWord()) 1822193323Sed Remainder->VAL = tmp; 1823193323Sed else 1824193323Sed Remainder->pVal[0] = tmp; 1825193323Sed } else { 1826193323Sed assert(!Remainder->isSingleWord() && "Remainder APInt not large enough"); 1827193323Sed for (unsigned i = 0; i < rhsWords; ++i) 1828198090Srdivacky Remainder->pVal[i] = 1829193323Sed uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2)); 1830193323Sed } 1831193323Sed } 1832193323Sed 1833193323Sed // Clean up the memory we allocated. 1834193323Sed if (U != &SPACE[0]) { 1835193323Sed delete [] U; 1836193323Sed delete [] V; 1837193323Sed delete [] Q; 1838193323Sed delete [] R; 1839193323Sed } 1840193323Sed} 1841193323Sed 1842193323SedAPInt APInt::udiv(const APInt& RHS) const { 1843193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 1844193323Sed 1845193323Sed // First, deal with the easy case 1846193323Sed if (isSingleWord()) { 1847193323Sed assert(RHS.VAL != 0 && "Divide by zero?"); 1848193323Sed return APInt(BitWidth, VAL / RHS.VAL); 1849193323Sed } 1850193323Sed 1851193323Sed // Get some facts about the LHS and RHS number of bits and words 1852193323Sed unsigned rhsBits = RHS.getActiveBits(); 1853193323Sed unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 1854193323Sed assert(rhsWords && "Divided by zero???"); 1855193323Sed unsigned lhsBits = this->getActiveBits(); 1856193323Sed unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); 1857193323Sed 1858193323Sed // Deal with some degenerate cases 1859198090Srdivacky if (!lhsWords) 1860193323Sed // 0 / X ===> 0 1861198090Srdivacky return APInt(BitWidth, 0); 1862193323Sed else if (lhsWords < rhsWords || this->ult(RHS)) { 1863193323Sed // X / Y ===> 0, iff X < Y 1864193323Sed return APInt(BitWidth, 0); 1865193323Sed } else if (*this == RHS) { 1866193323Sed // X / X ===> 1 1867193323Sed return APInt(BitWidth, 1); 1868193323Sed } else if (lhsWords == 1 && rhsWords == 1) { 1869193323Sed // All high words are zero, just use native divide 1870193323Sed return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]); 1871193323Sed } 1872193323Sed 1873193323Sed // We have to compute it the hard way. Invoke the Knuth divide algorithm. 1874193323Sed APInt Quotient(1,0); // to hold result. 1875193323Sed divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0); 1876193323Sed return Quotient; 1877193323Sed} 1878193323Sed 1879249423SdimAPInt APInt::sdiv(const APInt &RHS) const { 1880249423Sdim if (isNegative()) { 1881249423Sdim if (RHS.isNegative()) 1882249423Sdim return (-(*this)).udiv(-RHS); 1883249423Sdim return -((-(*this)).udiv(RHS)); 1884249423Sdim } 1885249423Sdim if (RHS.isNegative()) 1886249423Sdim return -(this->udiv(-RHS)); 1887249423Sdim return this->udiv(RHS); 1888249423Sdim} 1889249423Sdim 1890193323SedAPInt APInt::urem(const APInt& RHS) const { 1891193323Sed assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 1892193323Sed if (isSingleWord()) { 1893193323Sed assert(RHS.VAL != 0 && "Remainder by zero?"); 1894193323Sed return APInt(BitWidth, VAL % RHS.VAL); 1895193323Sed } 1896193323Sed 1897193323Sed // Get some facts about the LHS 1898193323Sed unsigned lhsBits = getActiveBits(); 1899193323Sed unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1); 1900193323Sed 1901193323Sed // Get some facts about the RHS 1902193323Sed unsigned rhsBits = RHS.getActiveBits(); 1903193323Sed unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 1904193323Sed assert(rhsWords && "Performing remainder operation by zero ???"); 1905193323Sed 1906193323Sed // Check the degenerate cases 1907193323Sed if (lhsWords == 0) { 1908193323Sed // 0 % Y ===> 0 1909193323Sed return APInt(BitWidth, 0); 1910193323Sed } else if (lhsWords < rhsWords || this->ult(RHS)) { 1911193323Sed // X % Y ===> X, iff X < Y 1912193323Sed return *this; 1913193323Sed } else if (*this == RHS) { 1914193323Sed // X % X == 0; 1915193323Sed return APInt(BitWidth, 0); 1916193323Sed } else if (lhsWords == 1) { 1917193323Sed // All high words are zero, just use native remainder 1918193323Sed return APInt(BitWidth, pVal[0] % RHS.pVal[0]); 1919193323Sed } 1920193323Sed 1921193323Sed // We have to compute it the hard way. Invoke the Knuth divide algorithm. 1922193323Sed APInt Remainder(1,0); 1923193323Sed divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder); 1924193323Sed return Remainder; 1925193323Sed} 1926193323Sed 1927249423SdimAPInt APInt::srem(const APInt &RHS) const { 1928249423Sdim if (isNegative()) { 1929249423Sdim if (RHS.isNegative()) 1930249423Sdim return -((-(*this)).urem(-RHS)); 1931249423Sdim return -((-(*this)).urem(RHS)); 1932249423Sdim } 1933249423Sdim if (RHS.isNegative()) 1934249423Sdim return this->urem(-RHS); 1935249423Sdim return this->urem(RHS); 1936249423Sdim} 1937249423Sdim 1938198090Srdivackyvoid APInt::udivrem(const APInt &LHS, const APInt &RHS, 1939193323Sed APInt &Quotient, APInt &Remainder) { 1940193323Sed // Get some size facts about the dividend and divisor 1941193323Sed unsigned lhsBits = LHS.getActiveBits(); 1942193323Sed unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); 1943193323Sed unsigned rhsBits = RHS.getActiveBits(); 1944193323Sed unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 1945193323Sed 1946193323Sed // Check the degenerate cases 1947198090Srdivacky if (lhsWords == 0) { 1948193323Sed Quotient = 0; // 0 / Y ===> 0 1949193323Sed Remainder = 0; // 0 % Y ===> 0 1950193323Sed return; 1951198090Srdivacky } 1952198090Srdivacky 1953198090Srdivacky if (lhsWords < rhsWords || LHS.ult(RHS)) { 1954201360Srdivacky Remainder = LHS; // X % Y ===> X, iff X < Y 1955193323Sed Quotient = 0; // X / Y ===> 0, iff X < Y 1956193323Sed return; 1957198090Srdivacky } 1958198090Srdivacky 1959193323Sed if (LHS == RHS) { 1960193323Sed Quotient = 1; // X / X ===> 1 1961193323Sed Remainder = 0; // X % X ===> 0; 1962193323Sed return; 1963198090Srdivacky } 1964198090Srdivacky 1965193323Sed if (lhsWords == 1 && rhsWords == 1) { 1966193323Sed // There is only one word to consider so use the native versions. 1967193323Sed uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0]; 1968193323Sed uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 1969193323Sed Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue); 1970193323Sed Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue); 1971193323Sed return; 1972193323Sed } 1973193323Sed 1974193323Sed // Okay, lets do it the long way 1975193323Sed divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder); 1976193323Sed} 1977193323Sed 1978249423Sdimvoid APInt::sdivrem(const APInt &LHS, const APInt &RHS, 1979249423Sdim APInt &Quotient, APInt &Remainder) { 1980249423Sdim if (LHS.isNegative()) { 1981249423Sdim if (RHS.isNegative()) 1982249423Sdim APInt::udivrem(-LHS, -RHS, Quotient, Remainder); 1983249423Sdim else { 1984249423Sdim APInt::udivrem(-LHS, RHS, Quotient, Remainder); 1985249423Sdim Quotient = -Quotient; 1986249423Sdim } 1987249423Sdim Remainder = -Remainder; 1988249423Sdim } else if (RHS.isNegative()) { 1989249423Sdim APInt::udivrem(LHS, -RHS, Quotient, Remainder); 1990249423Sdim Quotient = -Quotient; 1991249423Sdim } else { 1992249423Sdim APInt::udivrem(LHS, RHS, Quotient, Remainder); 1993249423Sdim } 1994249423Sdim} 1995249423Sdim 1996218893SdimAPInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const { 1997218893Sdim APInt Res = *this+RHS; 1998218893Sdim Overflow = isNonNegative() == RHS.isNonNegative() && 1999218893Sdim Res.isNonNegative() != isNonNegative(); 2000218893Sdim return Res; 2001218893Sdim} 2002218893Sdim 2003218893SdimAPInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const { 2004218893Sdim APInt Res = *this+RHS; 2005218893Sdim Overflow = Res.ult(RHS); 2006218893Sdim return Res; 2007218893Sdim} 2008218893Sdim 2009218893SdimAPInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const { 2010218893Sdim APInt Res = *this - RHS; 2011218893Sdim Overflow = isNonNegative() != RHS.isNonNegative() && 2012218893Sdim Res.isNonNegative() != isNonNegative(); 2013218893Sdim return Res; 2014218893Sdim} 2015218893Sdim 2016218893SdimAPInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const { 2017218893Sdim APInt Res = *this-RHS; 2018218893Sdim Overflow = Res.ugt(*this); 2019218893Sdim return Res; 2020218893Sdim} 2021218893Sdim 2022218893SdimAPInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const { 2023218893Sdim // MININT/-1 --> overflow. 2024218893Sdim Overflow = isMinSignedValue() && RHS.isAllOnesValue(); 2025218893Sdim return sdiv(RHS); 2026218893Sdim} 2027218893Sdim 2028218893SdimAPInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const { 2029218893Sdim APInt Res = *this * RHS; 2030218893Sdim 2031218893Sdim if (*this != 0 && RHS != 0) 2032218893Sdim Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS; 2033218893Sdim else 2034218893Sdim Overflow = false; 2035218893Sdim return Res; 2036218893Sdim} 2037218893Sdim 2038221345SdimAPInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const { 2039221345Sdim APInt Res = *this * RHS; 2040221345Sdim 2041221345Sdim if (*this != 0 && RHS != 0) 2042221345Sdim Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS; 2043221345Sdim else 2044221345Sdim Overflow = false; 2045221345Sdim return Res; 2046221345Sdim} 2047221345Sdim 2048218893SdimAPInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const { 2049218893Sdim Overflow = ShAmt >= getBitWidth(); 2050218893Sdim if (Overflow) 2051218893Sdim ShAmt = getBitWidth()-1; 2052218893Sdim 2053218893Sdim if (isNonNegative()) // Don't allow sign change. 2054218893Sdim Overflow = ShAmt >= countLeadingZeros(); 2055218893Sdim else 2056218893Sdim Overflow = ShAmt >= countLeadingOnes(); 2057218893Sdim 2058218893Sdim return *this << ShAmt; 2059218893Sdim} 2060218893Sdim 2061218893Sdim 2062218893Sdim 2063218893Sdim 2064210299Sedvoid APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) { 2065193323Sed // Check our assumptions here 2066198090Srdivacky assert(!str.empty() && "Invalid string length"); 2067226633Sdim assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 || 2068226633Sdim radix == 36) && 2069226633Sdim "Radix should be 2, 8, 10, 16, or 36!"); 2070198090Srdivacky 2071198090Srdivacky StringRef::iterator p = str.begin(); 2072198090Srdivacky size_t slen = str.size(); 2073198090Srdivacky bool isNeg = *p == '-'; 2074198090Srdivacky if (*p == '-' || *p == '+') { 2075198090Srdivacky p++; 2076198090Srdivacky slen--; 2077198090Srdivacky assert(slen && "String is only a sign, needs a value."); 2078198090Srdivacky } 2079193323Sed assert((slen <= numbits || radix != 2) && "Insufficient bit width"); 2080193323Sed assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width"); 2081193323Sed assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width"); 2082206083Srdivacky assert((((slen-1)*64)/22 <= numbits || radix != 10) && 2083206083Srdivacky "Insufficient bit width"); 2084193323Sed 2085193323Sed // Allocate memory 2086193323Sed if (!isSingleWord()) 2087193323Sed pVal = getClearedMemory(getNumWords()); 2088193323Sed 2089193323Sed // Figure out if we can shift instead of multiply 2090193323Sed unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0); 2091193323Sed 2092193323Sed // Set up an APInt for the digit to add outside the loop so we don't 2093193323Sed // constantly construct/destruct it. 2094193323Sed APInt apdigit(getBitWidth(), 0); 2095193323Sed APInt apradix(getBitWidth(), radix); 2096193323Sed 2097193323Sed // Enter digit traversal loop 2098198090Srdivacky for (StringRef::iterator e = str.end(); p != e; ++p) { 2099198090Srdivacky unsigned digit = getDigit(*p, radix); 2100198090Srdivacky assert(digit < radix && "Invalid character in digit string"); 2101193323Sed 2102193323Sed // Shift or multiply the value by the radix 2103193323Sed if (slen > 1) { 2104193323Sed if (shift) 2105193323Sed *this <<= shift; 2106193323Sed else 2107193323Sed *this *= apradix; 2108193323Sed } 2109193323Sed 2110193323Sed // Add in the digit we just interpreted 2111193323Sed if (apdigit.isSingleWord()) 2112193323Sed apdigit.VAL = digit; 2113193323Sed else 2114193323Sed apdigit.pVal[0] = digit; 2115193323Sed *this += apdigit; 2116193323Sed } 2117193323Sed // If its negative, put it in two's complement form 2118193323Sed if (isNeg) { 2119249423Sdim --(*this); 2120218893Sdim this->flipAllBits(); 2121193323Sed } 2122193323Sed} 2123193323Sed 2124193323Sedvoid APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix, 2125224145Sdim bool Signed, bool formatAsCLiteral) const { 2126226633Sdim assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || 2127226633Sdim Radix == 36) && 2128234353Sdim "Radix should be 2, 8, 10, 16, or 36!"); 2129198090Srdivacky 2130224145Sdim const char *Prefix = ""; 2131224145Sdim if (formatAsCLiteral) { 2132224145Sdim switch (Radix) { 2133224145Sdim case 2: 2134224145Sdim // Binary literals are a non-standard extension added in gcc 4.3: 2135224145Sdim // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html 2136224145Sdim Prefix = "0b"; 2137224145Sdim break; 2138224145Sdim case 8: 2139224145Sdim Prefix = "0"; 2140224145Sdim break; 2141234353Sdim case 10: 2142234353Sdim break; // No prefix 2143224145Sdim case 16: 2144224145Sdim Prefix = "0x"; 2145224145Sdim break; 2146234353Sdim default: 2147234353Sdim llvm_unreachable("Invalid radix!"); 2148224145Sdim } 2149224145Sdim } 2150224145Sdim 2151193323Sed // First, check for a zero value and just short circuit the logic below. 2152193323Sed if (*this == 0) { 2153224145Sdim while (*Prefix) { 2154224145Sdim Str.push_back(*Prefix); 2155224145Sdim ++Prefix; 2156224145Sdim }; 2157193323Sed Str.push_back('0'); 2158193323Sed return; 2159193323Sed } 2160198090Srdivacky 2161226633Sdim static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 2162198090Srdivacky 2163193323Sed if (isSingleWord()) { 2164193323Sed char Buffer[65]; 2165193323Sed char *BufPtr = Buffer+65; 2166198090Srdivacky 2167193323Sed uint64_t N; 2168212904Sdim if (!Signed) { 2169212904Sdim N = getZExtValue(); 2170212904Sdim } else { 2171193323Sed int64_t I = getSExtValue(); 2172212904Sdim if (I >= 0) { 2173212904Sdim N = I; 2174212904Sdim } else { 2175193323Sed Str.push_back('-'); 2176212904Sdim N = -(uint64_t)I; 2177193323Sed } 2178193323Sed } 2179198090Srdivacky 2180224145Sdim while (*Prefix) { 2181224145Sdim Str.push_back(*Prefix); 2182224145Sdim ++Prefix; 2183224145Sdim }; 2184224145Sdim 2185193323Sed while (N) { 2186193323Sed *--BufPtr = Digits[N % Radix]; 2187193323Sed N /= Radix; 2188193323Sed } 2189193323Sed Str.append(BufPtr, Buffer+65); 2190193323Sed return; 2191193323Sed } 2192193323Sed 2193193323Sed APInt Tmp(*this); 2194198090Srdivacky 2195193323Sed if (Signed && isNegative()) { 2196193323Sed // They want to print the signed version and it is a negative value 2197193323Sed // Flip the bits and add one to turn it into the equivalent positive 2198193323Sed // value and put a '-' in the result. 2199218893Sdim Tmp.flipAllBits(); 2200249423Sdim ++Tmp; 2201193323Sed Str.push_back('-'); 2202193323Sed } 2203198090Srdivacky 2204224145Sdim while (*Prefix) { 2205224145Sdim Str.push_back(*Prefix); 2206224145Sdim ++Prefix; 2207224145Sdim }; 2208224145Sdim 2209193323Sed // We insert the digits backward, then reverse them to get the right order. 2210193323Sed unsigned StartDig = Str.size(); 2211198090Srdivacky 2212198090Srdivacky // For the 2, 8 and 16 bit cases, we can just shift instead of divide 2213198090Srdivacky // because the number of bits per digit (1, 3 and 4 respectively) divides 2214193323Sed // equaly. We just shift until the value is zero. 2215226633Sdim if (Radix == 2 || Radix == 8 || Radix == 16) { 2216193323Sed // Just shift tmp right for each digit width until it becomes zero 2217193323Sed unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1)); 2218193323Sed unsigned MaskAmt = Radix - 1; 2219198090Srdivacky 2220193323Sed while (Tmp != 0) { 2221193323Sed unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt; 2222193323Sed Str.push_back(Digits[Digit]); 2223193323Sed Tmp = Tmp.lshr(ShiftAmt); 2224193323Sed } 2225193323Sed } else { 2226226633Sdim APInt divisor(Radix == 10? 4 : 8, Radix); 2227193323Sed while (Tmp != 0) { 2228193323Sed APInt APdigit(1, 0); 2229193323Sed APInt tmp2(Tmp.getBitWidth(), 0); 2230198090Srdivacky divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2, 2231193323Sed &APdigit); 2232193323Sed unsigned Digit = (unsigned)APdigit.getZExtValue(); 2233193323Sed assert(Digit < Radix && "divide failed"); 2234193323Sed Str.push_back(Digits[Digit]); 2235193323Sed Tmp = tmp2; 2236193323Sed } 2237193323Sed } 2238198090Srdivacky 2239193323Sed // Reverse the digits before returning. 2240193323Sed std::reverse(Str.begin()+StartDig, Str.end()); 2241193323Sed} 2242193323Sed 2243193323Sed/// toString - This returns the APInt as a std::string. Note that this is an 2244193323Sed/// inefficient method. It is better to pass in a SmallVector/SmallString 2245193323Sed/// to the methods above. 2246193323Sedstd::string APInt::toString(unsigned Radix = 10, bool Signed = true) const { 2247193323Sed SmallString<40> S; 2248224145Sdim toString(S, Radix, Signed, /* formatAsCLiteral = */false); 2249198090Srdivacky return S.str(); 2250193323Sed} 2251193323Sed 2252193323Sed 2253193323Sedvoid APInt::dump() const { 2254193323Sed SmallString<40> S, U; 2255193323Sed this->toStringUnsigned(U); 2256193323Sed this->toStringSigned(S); 2257202375Srdivacky dbgs() << "APInt(" << BitWidth << "b, " 2258198090Srdivacky << U.str() << "u " << S.str() << "s)"; 2259193323Sed} 2260193323Sed 2261193323Sedvoid APInt::print(raw_ostream &OS, bool isSigned) const { 2262193323Sed SmallString<40> S; 2263224145Sdim this->toString(S, 10, isSigned, /* formatAsCLiteral = */false); 2264198090Srdivacky OS << S.str(); 2265193323Sed} 2266193323Sed 2267193323Sed// This implements a variety of operations on a representation of 2268193323Sed// arbitrary precision, two's-complement, bignum integer values. 2269193323Sed 2270198090Srdivacky// Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe 2271198090Srdivacky// and unrestricting assumption. 2272193323Sed#define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1] 2273193323SedCOMPILE_TIME_ASSERT(integerPartWidth % 2 == 0); 2274193323Sed 2275193323Sed/* Some handy functions local to this file. */ 2276193323Sednamespace { 2277193323Sed 2278193323Sed /* Returns the integer part with the least significant BITS set. 2279193323Sed BITS cannot be zero. */ 2280193323Sed static inline integerPart 2281193323Sed lowBitMask(unsigned int bits) 2282193323Sed { 2283206083Srdivacky assert(bits != 0 && bits <= integerPartWidth); 2284193323Sed 2285193323Sed return ~(integerPart) 0 >> (integerPartWidth - bits); 2286193323Sed } 2287193323Sed 2288193323Sed /* Returns the value of the lower half of PART. */ 2289193323Sed static inline integerPart 2290193323Sed lowHalf(integerPart part) 2291193323Sed { 2292193323Sed return part & lowBitMask(integerPartWidth / 2); 2293193323Sed } 2294193323Sed 2295193323Sed /* Returns the value of the upper half of PART. */ 2296193323Sed static inline integerPart 2297193323Sed highHalf(integerPart part) 2298193323Sed { 2299193323Sed return part >> (integerPartWidth / 2); 2300193323Sed } 2301193323Sed 2302193323Sed /* Returns the bit number of the most significant set bit of a part. 2303193323Sed If the input number has no bits set -1U is returned. */ 2304193323Sed static unsigned int 2305193323Sed partMSB(integerPart value) 2306193323Sed { 2307263508Sdim return findLastSet(value, ZB_Max); 2308193323Sed } 2309193323Sed 2310193323Sed /* Returns the bit number of the least significant set bit of a 2311193323Sed part. If the input number has no bits set -1U is returned. */ 2312193323Sed static unsigned int 2313193323Sed partLSB(integerPart value) 2314193323Sed { 2315263508Sdim return findFirstSet(value, ZB_Max); 2316193323Sed } 2317193323Sed} 2318193323Sed 2319193323Sed/* Sets the least significant part of a bignum to the input value, and 2320193323Sed zeroes out higher parts. */ 2321193323Sedvoid 2322193323SedAPInt::tcSet(integerPart *dst, integerPart part, unsigned int parts) 2323193323Sed{ 2324193323Sed unsigned int i; 2325193323Sed 2326206083Srdivacky assert(parts > 0); 2327193323Sed 2328193323Sed dst[0] = part; 2329206083Srdivacky for (i = 1; i < parts; i++) 2330193323Sed dst[i] = 0; 2331193323Sed} 2332193323Sed 2333193323Sed/* Assign one bignum to another. */ 2334193323Sedvoid 2335193323SedAPInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts) 2336193323Sed{ 2337193323Sed unsigned int i; 2338193323Sed 2339206083Srdivacky for (i = 0; i < parts; i++) 2340193323Sed dst[i] = src[i]; 2341193323Sed} 2342193323Sed 2343193323Sed/* Returns true if a bignum is zero, false otherwise. */ 2344193323Sedbool 2345193323SedAPInt::tcIsZero(const integerPart *src, unsigned int parts) 2346193323Sed{ 2347193323Sed unsigned int i; 2348193323Sed 2349206083Srdivacky for (i = 0; i < parts; i++) 2350193323Sed if (src[i]) 2351193323Sed return false; 2352193323Sed 2353193323Sed return true; 2354193323Sed} 2355193323Sed 2356193323Sed/* Extract the given bit of a bignum; returns 0 or 1. */ 2357193323Sedint 2358193323SedAPInt::tcExtractBit(const integerPart *parts, unsigned int bit) 2359193323Sed{ 2360206083Srdivacky return (parts[bit / integerPartWidth] & 2361206083Srdivacky ((integerPart) 1 << bit % integerPartWidth)) != 0; 2362193323Sed} 2363193323Sed 2364204642Srdivacky/* Set the given bit of a bignum. */ 2365193323Sedvoid 2366193323SedAPInt::tcSetBit(integerPart *parts, unsigned int bit) 2367193323Sed{ 2368193323Sed parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth); 2369193323Sed} 2370193323Sed 2371204642Srdivacky/* Clears the given bit of a bignum. */ 2372204642Srdivackyvoid 2373204642SrdivackyAPInt::tcClearBit(integerPart *parts, unsigned int bit) 2374204642Srdivacky{ 2375204642Srdivacky parts[bit / integerPartWidth] &= 2376204642Srdivacky ~((integerPart) 1 << (bit % integerPartWidth)); 2377204642Srdivacky} 2378204642Srdivacky 2379193323Sed/* Returns the bit number of the least significant set bit of a 2380193323Sed number. If the input number has no bits set -1U is returned. */ 2381193323Sedunsigned int 2382193323SedAPInt::tcLSB(const integerPart *parts, unsigned int n) 2383193323Sed{ 2384193323Sed unsigned int i, lsb; 2385193323Sed 2386206083Srdivacky for (i = 0; i < n; i++) { 2387193323Sed if (parts[i] != 0) { 2388193323Sed lsb = partLSB(parts[i]); 2389193323Sed 2390193323Sed return lsb + i * integerPartWidth; 2391193323Sed } 2392193323Sed } 2393193323Sed 2394193323Sed return -1U; 2395193323Sed} 2396193323Sed 2397193323Sed/* Returns the bit number of the most significant set bit of a number. 2398193323Sed If the input number has no bits set -1U is returned. */ 2399193323Sedunsigned int 2400193323SedAPInt::tcMSB(const integerPart *parts, unsigned int n) 2401193323Sed{ 2402193323Sed unsigned int msb; 2403193323Sed 2404193323Sed do { 2405206083Srdivacky --n; 2406193323Sed 2407206083Srdivacky if (parts[n] != 0) { 2408206083Srdivacky msb = partMSB(parts[n]); 2409193323Sed 2410206083Srdivacky return msb + n * integerPartWidth; 2411206083Srdivacky } 2412193323Sed } while (n); 2413193323Sed 2414193323Sed return -1U; 2415193323Sed} 2416193323Sed 2417193323Sed/* Copy the bit vector of width srcBITS from SRC, starting at bit 2418193323Sed srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes 2419193323Sed the least significant bit of DST. All high bits above srcBITS in 2420193323Sed DST are zero-filled. */ 2421193323Sedvoid 2422193323SedAPInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src, 2423193323Sed unsigned int srcBits, unsigned int srcLSB) 2424193323Sed{ 2425193323Sed unsigned int firstSrcPart, dstParts, shift, n; 2426193323Sed 2427193323Sed dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth; 2428206083Srdivacky assert(dstParts <= dstCount); 2429193323Sed 2430193323Sed firstSrcPart = srcLSB / integerPartWidth; 2431193323Sed tcAssign (dst, src + firstSrcPart, dstParts); 2432193323Sed 2433193323Sed shift = srcLSB % integerPartWidth; 2434193323Sed tcShiftRight (dst, dstParts, shift); 2435193323Sed 2436193323Sed /* We now have (dstParts * integerPartWidth - shift) bits from SRC 2437193323Sed in DST. If this is less that srcBits, append the rest, else 2438193323Sed clear the high bits. */ 2439193323Sed n = dstParts * integerPartWidth - shift; 2440193323Sed if (n < srcBits) { 2441193323Sed integerPart mask = lowBitMask (srcBits - n); 2442193323Sed dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask) 2443193323Sed << n % integerPartWidth); 2444193323Sed } else if (n > srcBits) { 2445193323Sed if (srcBits % integerPartWidth) 2446193323Sed dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth); 2447193323Sed } 2448193323Sed 2449193323Sed /* Clear high parts. */ 2450193323Sed while (dstParts < dstCount) 2451193323Sed dst[dstParts++] = 0; 2452193323Sed} 2453193323Sed 2454193323Sed/* DST += RHS + C where C is zero or one. Returns the carry flag. */ 2455193323SedintegerPart 2456193323SedAPInt::tcAdd(integerPart *dst, const integerPart *rhs, 2457193323Sed integerPart c, unsigned int parts) 2458193323Sed{ 2459193323Sed unsigned int i; 2460193323Sed 2461193323Sed assert(c <= 1); 2462193323Sed 2463206083Srdivacky for (i = 0; i < parts; i++) { 2464193323Sed integerPart l; 2465193323Sed 2466193323Sed l = dst[i]; 2467193323Sed if (c) { 2468193323Sed dst[i] += rhs[i] + 1; 2469193323Sed c = (dst[i] <= l); 2470193323Sed } else { 2471193323Sed dst[i] += rhs[i]; 2472193323Sed c = (dst[i] < l); 2473193323Sed } 2474193323Sed } 2475193323Sed 2476193323Sed return c; 2477193323Sed} 2478193323Sed 2479193323Sed/* DST -= RHS + C where C is zero or one. Returns the carry flag. */ 2480193323SedintegerPart 2481193323SedAPInt::tcSubtract(integerPart *dst, const integerPart *rhs, 2482193323Sed integerPart c, unsigned int parts) 2483193323Sed{ 2484193323Sed unsigned int i; 2485193323Sed 2486193323Sed assert(c <= 1); 2487193323Sed 2488206083Srdivacky for (i = 0; i < parts; i++) { 2489193323Sed integerPart l; 2490193323Sed 2491193323Sed l = dst[i]; 2492193323Sed if (c) { 2493193323Sed dst[i] -= rhs[i] + 1; 2494193323Sed c = (dst[i] >= l); 2495193323Sed } else { 2496193323Sed dst[i] -= rhs[i]; 2497193323Sed c = (dst[i] > l); 2498193323Sed } 2499193323Sed } 2500193323Sed 2501193323Sed return c; 2502193323Sed} 2503193323Sed 2504193323Sed/* Negate a bignum in-place. */ 2505193323Sedvoid 2506193323SedAPInt::tcNegate(integerPart *dst, unsigned int parts) 2507193323Sed{ 2508193323Sed tcComplement(dst, parts); 2509193323Sed tcIncrement(dst, parts); 2510193323Sed} 2511193323Sed 2512193323Sed/* DST += SRC * MULTIPLIER + CARRY if add is true 2513193323Sed DST = SRC * MULTIPLIER + CARRY if add is false 2514193323Sed 2515193323Sed Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC 2516193323Sed they must start at the same point, i.e. DST == SRC. 2517193323Sed 2518193323Sed If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is 2519193323Sed returned. Otherwise DST is filled with the least significant 2520193323Sed DSTPARTS parts of the result, and if all of the omitted higher 2521193323Sed parts were zero return zero, otherwise overflow occurred and 2522193323Sed return one. */ 2523193323Sedint 2524193323SedAPInt::tcMultiplyPart(integerPart *dst, const integerPart *src, 2525193323Sed integerPart multiplier, integerPart carry, 2526193323Sed unsigned int srcParts, unsigned int dstParts, 2527193323Sed bool add) 2528193323Sed{ 2529193323Sed unsigned int i, n; 2530193323Sed 2531193323Sed /* Otherwise our writes of DST kill our later reads of SRC. */ 2532193323Sed assert(dst <= src || dst >= src + srcParts); 2533193323Sed assert(dstParts <= srcParts + 1); 2534193323Sed 2535193323Sed /* N loops; minimum of dstParts and srcParts. */ 2536193323Sed n = dstParts < srcParts ? dstParts: srcParts; 2537193323Sed 2538206083Srdivacky for (i = 0; i < n; i++) { 2539193323Sed integerPart low, mid, high, srcPart; 2540193323Sed 2541193323Sed /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY. 2542193323Sed 2543193323Sed This cannot overflow, because 2544193323Sed 2545193323Sed (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1) 2546193323Sed 2547193323Sed which is less than n^2. */ 2548193323Sed 2549193323Sed srcPart = src[i]; 2550193323Sed 2551193323Sed if (multiplier == 0 || srcPart == 0) { 2552193323Sed low = carry; 2553193323Sed high = 0; 2554193323Sed } else { 2555193323Sed low = lowHalf(srcPart) * lowHalf(multiplier); 2556193323Sed high = highHalf(srcPart) * highHalf(multiplier); 2557193323Sed 2558193323Sed mid = lowHalf(srcPart) * highHalf(multiplier); 2559193323Sed high += highHalf(mid); 2560193323Sed mid <<= integerPartWidth / 2; 2561193323Sed if (low + mid < low) 2562193323Sed high++; 2563193323Sed low += mid; 2564193323Sed 2565193323Sed mid = highHalf(srcPart) * lowHalf(multiplier); 2566193323Sed high += highHalf(mid); 2567193323Sed mid <<= integerPartWidth / 2; 2568193323Sed if (low + mid < low) 2569193323Sed high++; 2570193323Sed low += mid; 2571193323Sed 2572193323Sed /* Now add carry. */ 2573193323Sed if (low + carry < low) 2574193323Sed high++; 2575193323Sed low += carry; 2576193323Sed } 2577193323Sed 2578193323Sed if (add) { 2579193323Sed /* And now DST[i], and store the new low part there. */ 2580193323Sed if (low + dst[i] < low) 2581193323Sed high++; 2582193323Sed dst[i] += low; 2583193323Sed } else 2584193323Sed dst[i] = low; 2585193323Sed 2586193323Sed carry = high; 2587193323Sed } 2588193323Sed 2589193323Sed if (i < dstParts) { 2590193323Sed /* Full multiplication, there is no overflow. */ 2591193323Sed assert(i + 1 == dstParts); 2592193323Sed dst[i] = carry; 2593193323Sed return 0; 2594193323Sed } else { 2595193323Sed /* We overflowed if there is carry. */ 2596193323Sed if (carry) 2597193323Sed return 1; 2598193323Sed 2599193323Sed /* We would overflow if any significant unwritten parts would be 2600193323Sed non-zero. This is true if any remaining src parts are non-zero 2601193323Sed and the multiplier is non-zero. */ 2602193323Sed if (multiplier) 2603206083Srdivacky for (; i < srcParts; i++) 2604193323Sed if (src[i]) 2605193323Sed return 1; 2606193323Sed 2607193323Sed /* We fitted in the narrow destination. */ 2608193323Sed return 0; 2609193323Sed } 2610193323Sed} 2611193323Sed 2612193323Sed/* DST = LHS * RHS, where DST has the same width as the operands and 2613193323Sed is filled with the least significant parts of the result. Returns 2614193323Sed one if overflow occurred, otherwise zero. DST must be disjoint 2615193323Sed from both operands. */ 2616193323Sedint 2617193323SedAPInt::tcMultiply(integerPart *dst, const integerPart *lhs, 2618193323Sed const integerPart *rhs, unsigned int parts) 2619193323Sed{ 2620193323Sed unsigned int i; 2621193323Sed int overflow; 2622193323Sed 2623193323Sed assert(dst != lhs && dst != rhs); 2624193323Sed 2625193323Sed overflow = 0; 2626193323Sed tcSet(dst, 0, parts); 2627193323Sed 2628206083Srdivacky for (i = 0; i < parts; i++) 2629193323Sed overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, 2630193323Sed parts - i, true); 2631193323Sed 2632193323Sed return overflow; 2633193323Sed} 2634193323Sed 2635193323Sed/* DST = LHS * RHS, where DST has width the sum of the widths of the 2636193323Sed operands. No overflow occurs. DST must be disjoint from both 2637193323Sed operands. Returns the number of parts required to hold the 2638193323Sed result. */ 2639193323Sedunsigned int 2640193323SedAPInt::tcFullMultiply(integerPart *dst, const integerPart *lhs, 2641193323Sed const integerPart *rhs, unsigned int lhsParts, 2642193323Sed unsigned int rhsParts) 2643193323Sed{ 2644193323Sed /* Put the narrower number on the LHS for less loops below. */ 2645193323Sed if (lhsParts > rhsParts) { 2646193323Sed return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts); 2647193323Sed } else { 2648193323Sed unsigned int n; 2649193323Sed 2650193323Sed assert(dst != lhs && dst != rhs); 2651193323Sed 2652193323Sed tcSet(dst, 0, rhsParts); 2653193323Sed 2654206083Srdivacky for (n = 0; n < lhsParts; n++) 2655193323Sed tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true); 2656193323Sed 2657193323Sed n = lhsParts + rhsParts; 2658193323Sed 2659193323Sed return n - (dst[n - 1] == 0); 2660193323Sed } 2661193323Sed} 2662193323Sed 2663193323Sed/* If RHS is zero LHS and REMAINDER are left unchanged, return one. 2664193323Sed Otherwise set LHS to LHS / RHS with the fractional part discarded, 2665193323Sed set REMAINDER to the remainder, return zero. i.e. 2666193323Sed 2667193323Sed OLD_LHS = RHS * LHS + REMAINDER 2668193323Sed 2669193323Sed SCRATCH is a bignum of the same size as the operands and result for 2670193323Sed use by the routine; its contents need not be initialized and are 2671193323Sed destroyed. LHS, REMAINDER and SCRATCH must be distinct. 2672193323Sed*/ 2673193323Sedint 2674193323SedAPInt::tcDivide(integerPart *lhs, const integerPart *rhs, 2675193323Sed integerPart *remainder, integerPart *srhs, 2676193323Sed unsigned int parts) 2677193323Sed{ 2678193323Sed unsigned int n, shiftCount; 2679193323Sed integerPart mask; 2680193323Sed 2681193323Sed assert(lhs != remainder && lhs != srhs && remainder != srhs); 2682193323Sed 2683193323Sed shiftCount = tcMSB(rhs, parts) + 1; 2684193323Sed if (shiftCount == 0) 2685193323Sed return true; 2686193323Sed 2687193323Sed shiftCount = parts * integerPartWidth - shiftCount; 2688193323Sed n = shiftCount / integerPartWidth; 2689193323Sed mask = (integerPart) 1 << (shiftCount % integerPartWidth); 2690193323Sed 2691193323Sed tcAssign(srhs, rhs, parts); 2692193323Sed tcShiftLeft(srhs, parts, shiftCount); 2693193323Sed tcAssign(remainder, lhs, parts); 2694193323Sed tcSet(lhs, 0, parts); 2695193323Sed 2696193323Sed /* Loop, subtracting SRHS if REMAINDER is greater and adding that to 2697193323Sed the total. */ 2698206083Srdivacky for (;;) { 2699193323Sed int compare; 2700193323Sed 2701193323Sed compare = tcCompare(remainder, srhs, parts); 2702193323Sed if (compare >= 0) { 2703193323Sed tcSubtract(remainder, srhs, 0, parts); 2704193323Sed lhs[n] |= mask; 2705193323Sed } 2706193323Sed 2707193323Sed if (shiftCount == 0) 2708193323Sed break; 2709193323Sed shiftCount--; 2710193323Sed tcShiftRight(srhs, parts, 1); 2711193323Sed if ((mask >>= 1) == 0) 2712193323Sed mask = (integerPart) 1 << (integerPartWidth - 1), n--; 2713193323Sed } 2714193323Sed 2715193323Sed return false; 2716193323Sed} 2717193323Sed 2718193323Sed/* Shift a bignum left COUNT bits in-place. Shifted in bits are zero. 2719193323Sed There are no restrictions on COUNT. */ 2720193323Sedvoid 2721193323SedAPInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count) 2722193323Sed{ 2723193323Sed if (count) { 2724193323Sed unsigned int jump, shift; 2725193323Sed 2726193323Sed /* Jump is the inter-part jump; shift is is intra-part shift. */ 2727193323Sed jump = count / integerPartWidth; 2728193323Sed shift = count % integerPartWidth; 2729193323Sed 2730193323Sed while (parts > jump) { 2731193323Sed integerPart part; 2732193323Sed 2733193323Sed parts--; 2734193323Sed 2735193323Sed /* dst[i] comes from the two parts src[i - jump] and, if we have 2736193323Sed an intra-part shift, src[i - jump - 1]. */ 2737193323Sed part = dst[parts - jump]; 2738193323Sed if (shift) { 2739193323Sed part <<= shift; 2740193323Sed if (parts >= jump + 1) 2741193323Sed part |= dst[parts - jump - 1] >> (integerPartWidth - shift); 2742193323Sed } 2743193323Sed 2744193323Sed dst[parts] = part; 2745193323Sed } 2746193323Sed 2747193323Sed while (parts > 0) 2748193323Sed dst[--parts] = 0; 2749193323Sed } 2750193323Sed} 2751193323Sed 2752193323Sed/* Shift a bignum right COUNT bits in-place. Shifted in bits are 2753193323Sed zero. There are no restrictions on COUNT. */ 2754193323Sedvoid 2755193323SedAPInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count) 2756193323Sed{ 2757193323Sed if (count) { 2758193323Sed unsigned int i, jump, shift; 2759193323Sed 2760193323Sed /* Jump is the inter-part jump; shift is is intra-part shift. */ 2761193323Sed jump = count / integerPartWidth; 2762193323Sed shift = count % integerPartWidth; 2763193323Sed 2764193323Sed /* Perform the shift. This leaves the most significant COUNT bits 2765193323Sed of the result at zero. */ 2766206083Srdivacky for (i = 0; i < parts; i++) { 2767193323Sed integerPart part; 2768193323Sed 2769193323Sed if (i + jump >= parts) { 2770193323Sed part = 0; 2771193323Sed } else { 2772193323Sed part = dst[i + jump]; 2773193323Sed if (shift) { 2774193323Sed part >>= shift; 2775193323Sed if (i + jump + 1 < parts) 2776193323Sed part |= dst[i + jump + 1] << (integerPartWidth - shift); 2777193323Sed } 2778193323Sed } 2779193323Sed 2780193323Sed dst[i] = part; 2781193323Sed } 2782193323Sed } 2783193323Sed} 2784193323Sed 2785193323Sed/* Bitwise and of two bignums. */ 2786193323Sedvoid 2787193323SedAPInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts) 2788193323Sed{ 2789193323Sed unsigned int i; 2790193323Sed 2791206083Srdivacky for (i = 0; i < parts; i++) 2792193323Sed dst[i] &= rhs[i]; 2793193323Sed} 2794193323Sed 2795193323Sed/* Bitwise inclusive or of two bignums. */ 2796193323Sedvoid 2797193323SedAPInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts) 2798193323Sed{ 2799193323Sed unsigned int i; 2800193323Sed 2801206083Srdivacky for (i = 0; i < parts; i++) 2802193323Sed dst[i] |= rhs[i]; 2803193323Sed} 2804193323Sed 2805193323Sed/* Bitwise exclusive or of two bignums. */ 2806193323Sedvoid 2807193323SedAPInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts) 2808193323Sed{ 2809193323Sed unsigned int i; 2810193323Sed 2811206083Srdivacky for (i = 0; i < parts; i++) 2812193323Sed dst[i] ^= rhs[i]; 2813193323Sed} 2814193323Sed 2815193323Sed/* Complement a bignum in-place. */ 2816193323Sedvoid 2817193323SedAPInt::tcComplement(integerPart *dst, unsigned int parts) 2818193323Sed{ 2819193323Sed unsigned int i; 2820193323Sed 2821206083Srdivacky for (i = 0; i < parts; i++) 2822193323Sed dst[i] = ~dst[i]; 2823193323Sed} 2824193323Sed 2825193323Sed/* Comparison (unsigned) of two bignums. */ 2826193323Sedint 2827193323SedAPInt::tcCompare(const integerPart *lhs, const integerPart *rhs, 2828193323Sed unsigned int parts) 2829193323Sed{ 2830193323Sed while (parts) { 2831193323Sed parts--; 2832193323Sed if (lhs[parts] == rhs[parts]) 2833193323Sed continue; 2834193323Sed 2835193323Sed if (lhs[parts] > rhs[parts]) 2836193323Sed return 1; 2837193323Sed else 2838193323Sed return -1; 2839193323Sed } 2840193323Sed 2841193323Sed return 0; 2842193323Sed} 2843193323Sed 2844193323Sed/* Increment a bignum in-place, return the carry flag. */ 2845193323SedintegerPart 2846193323SedAPInt::tcIncrement(integerPart *dst, unsigned int parts) 2847193323Sed{ 2848193323Sed unsigned int i; 2849193323Sed 2850206083Srdivacky for (i = 0; i < parts; i++) 2851193323Sed if (++dst[i] != 0) 2852193323Sed break; 2853193323Sed 2854193323Sed return i == parts; 2855193323Sed} 2856193323Sed 2857263508Sdim/* Decrement a bignum in-place, return the borrow flag. */ 2858263508SdimintegerPart 2859263508SdimAPInt::tcDecrement(integerPart *dst, unsigned int parts) { 2860263508Sdim for (unsigned int i = 0; i < parts; i++) { 2861263508Sdim // If the current word is non-zero, then the decrement has no effect on the 2862263508Sdim // higher-order words of the integer and no borrow can occur. Exit early. 2863263508Sdim if (dst[i]--) 2864263508Sdim return 0; 2865263508Sdim } 2866263508Sdim // If every word was zero, then there is a borrow. 2867263508Sdim return 1; 2868263508Sdim} 2869263508Sdim 2870263508Sdim 2871193323Sed/* Set the least significant BITS bits of a bignum, clear the 2872193323Sed rest. */ 2873193323Sedvoid 2874193323SedAPInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts, 2875193323Sed unsigned int bits) 2876193323Sed{ 2877193323Sed unsigned int i; 2878193323Sed 2879193323Sed i = 0; 2880193323Sed while (bits > integerPartWidth) { 2881193323Sed dst[i++] = ~(integerPart) 0; 2882193323Sed bits -= integerPartWidth; 2883193323Sed } 2884193323Sed 2885193323Sed if (bits) 2886193323Sed dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits); 2887193323Sed 2888193323Sed while (i < parts) 2889193323Sed dst[i++] = 0; 2890193323Sed} 2891