APInt.cpp revision 226633
1130803Smarcel//===-- APInt.cpp - Implement APInt class ---------------------------------===// 2130803Smarcel// 3130803Smarcel// The LLVM Compiler Infrastructure 4130803Smarcel// 5130803Smarcel// This file is distributed under the University of Illinois Open Source 6130803Smarcel// License. See LICENSE.TXT for details. 7130803Smarcel// 8130803Smarcel//===----------------------------------------------------------------------===// 9130803Smarcel// 10130803Smarcel// This file implements a class to represent arbitrary precision integer 11130803Smarcel// constant values and provide a variety of arithmetic operations on them. 12130803Smarcel// 13130803Smarcel//===----------------------------------------------------------------------===// 14130803Smarcel 15130803Smarcel#define DEBUG_TYPE "apint" 16130803Smarcel#include "llvm/ADT/APInt.h" 17130803Smarcel#include "llvm/ADT/StringRef.h" 18130803Smarcel#include "llvm/ADT/FoldingSet.h" 19130803Smarcel#include "llvm/ADT/SmallString.h" 20130803Smarcel#include "llvm/Support/Debug.h" 21130803Smarcel#include "llvm/Support/ErrorHandling.h" 22130803Smarcel#include "llvm/Support/MathExtras.h" 23130803Smarcel#include "llvm/Support/raw_ostream.h" 24130803Smarcel#include <cmath> 25130803Smarcel#include <limits> 26130803Smarcel#include <cstring> 27130803Smarcel#include <cstdlib> 28130803Smarcelusing namespace llvm; 29130803Smarcel 30130803Smarcel/// A utility function for allocating memory, checking for allocation failures, 31130803Smarcel/// and ensuring the contents are zeroed. 32130803Smarcelinline static uint64_t* getClearedMemory(unsigned numWords) { 33130803Smarcel uint64_t * result = new uint64_t[numWords]; 34130803Smarcel assert(result && "APInt memory allocation fails!"); 35130803Smarcel memset(result, 0, numWords * sizeof(uint64_t)); 36130803Smarcel return result; 37130803Smarcel} 38130803Smarcel 39130803Smarcel/// A utility function for allocating memory and checking for allocation 40130803Smarcel/// failure. The content is not zeroed. 41130803Smarcelinline static uint64_t* getMemory(unsigned numWords) { 42130803Smarcel uint64_t * result = new uint64_t[numWords]; 43130803Smarcel assert(result && "APInt memory allocation fails!"); 44130803Smarcel return result; 45130803Smarcel} 46130803Smarcel 47130803Smarcel/// A utility function that converts a character to a digit. 48130803Smarcelinline static unsigned getDigit(char cdigit, uint8_t radix) { 49130803Smarcel unsigned r; 50130803Smarcel 51130803Smarcel if (radix == 16 || radix == 36) { 52130803Smarcel r = cdigit - '0'; 53130803Smarcel if (r <= 9) 54130803Smarcel return r; 55130803Smarcel 56130803Smarcel r = cdigit - 'A'; 57130803Smarcel if (r <= radix - 11U) 58130803Smarcel return r + 10; 59130803Smarcel 60130803Smarcel r = cdigit - 'a'; 61130803Smarcel if (r <= radix - 11U) 62130803Smarcel return r + 10; 63130803Smarcel 64130803Smarcel radix = 10; 65130803Smarcel } 66130803Smarcel 67130803Smarcel r = cdigit - '0'; 68130803Smarcel if (r < radix) 69130803Smarcel return r; 70130803Smarcel 71130803Smarcel return -1U; 72130803Smarcel} 73130803Smarcel 74130803Smarcel 75130803Smarcelvoid APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) { 76130803Smarcel pVal = getClearedMemory(getNumWords()); 77130803Smarcel pVal[0] = val; 78130803Smarcel if (isSigned && int64_t(val) < 0) 79130803Smarcel for (unsigned i = 1; i < getNumWords(); ++i) 80130803Smarcel pVal[i] = -1ULL; 81130803Smarcel} 82130803Smarcel 83130803Smarcelvoid APInt::initSlowCase(const APInt& that) { 84130803Smarcel pVal = getMemory(getNumWords()); 85130803Smarcel memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE); 86130803Smarcel} 87130803Smarcel 88130803Smarcelvoid APInt::initFromArray(ArrayRef<uint64_t> bigVal) { 89130803Smarcel assert(BitWidth && "Bitwidth too small"); 90130803Smarcel assert(bigVal.data() && "Null pointer detected!"); 91130803Smarcel if (isSingleWord()) 92130803Smarcel VAL = bigVal[0]; 93130803Smarcel else { 94130803Smarcel // Get memory, cleared to 0 95130803Smarcel pVal = getClearedMemory(getNumWords()); 96130803Smarcel // Calculate the number of words to copy 97130803Smarcel unsigned words = std::min<unsigned>(bigVal.size(), getNumWords()); 98130803Smarcel // Copy the words from bigVal to pVal 99130803Smarcel memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE); 100130803Smarcel } 101130803Smarcel // Make sure unused high bits are cleared 102130803Smarcel clearUnusedBits(); 103130803Smarcel} 104130803Smarcel 105130803SmarcelAPInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal) 106130803Smarcel : BitWidth(numBits), VAL(0) { 107130803Smarcel initFromArray(bigVal); 108130803Smarcel} 109130803Smarcel 110130803SmarcelAPInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]) 111130803Smarcel : BitWidth(numBits), VAL(0) { 112130803Smarcel initFromArray(makeArrayRef(bigVal, numWords)); 113130803Smarcel} 114130803Smarcel 115130803SmarcelAPInt::APInt(unsigned numbits, StringRef Str, uint8_t radix) 116130803Smarcel : BitWidth(numbits), VAL(0) { 117130803Smarcel assert(BitWidth && "Bitwidth too small"); 118130803Smarcel fromString(numbits, Str, radix); 119130803Smarcel} 120130803Smarcel 121130803SmarcelAPInt& APInt::AssignSlowCase(const APInt& RHS) { 122130803Smarcel // Don't do anything for X = X 123130803Smarcel if (this == &RHS) 124130803Smarcel return *this; 125130803Smarcel 126130803Smarcel if (BitWidth == RHS.getBitWidth()) { 127130803Smarcel // assume same bit-width single-word case is already handled 128130803Smarcel assert(!isSingleWord()); 129130803Smarcel memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE); 130130803Smarcel return *this; 131130803Smarcel } 132130803Smarcel 133130803Smarcel if (isSingleWord()) { 134130803Smarcel // assume case where both are single words is already handled 135130803Smarcel assert(!RHS.isSingleWord()); 136130803Smarcel VAL = 0; 137130803Smarcel pVal = getMemory(RHS.getNumWords()); 138130803Smarcel memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 139130803Smarcel } else if (getNumWords() == RHS.getNumWords()) 140130803Smarcel memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 141130803Smarcel else if (RHS.isSingleWord()) { 142130803Smarcel delete [] pVal; 143130803Smarcel VAL = RHS.VAL; 144130803Smarcel } else { 145130803Smarcel delete [] pVal; 146130803Smarcel pVal = getMemory(RHS.getNumWords()); 147130803Smarcel memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); 148130803Smarcel } 149130803Smarcel BitWidth = RHS.BitWidth; 150130803Smarcel return clearUnusedBits(); 151130803Smarcel} 152130803Smarcel 153130803SmarcelAPInt& APInt::operator=(uint64_t RHS) { 154130803Smarcel if (isSingleWord()) 155130803Smarcel VAL = RHS; 156130803Smarcel else { 157130803Smarcel pVal[0] = RHS; 158130803Smarcel memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE); 159130803Smarcel } 160130803Smarcel return clearUnusedBits(); 161130803Smarcel} 162130803Smarcel 163130803Smarcel/// Profile - This method 'profiles' an APInt for use with FoldingSet. 164130803Smarcelvoid APInt::Profile(FoldingSetNodeID& ID) const { 165130803Smarcel ID.AddInteger(BitWidth); 166130803Smarcel 167130803Smarcel if (isSingleWord()) { 168130803Smarcel ID.AddInteger(VAL); 169130803Smarcel return; 170130803Smarcel } 171130803Smarcel 172130803Smarcel unsigned NumWords = getNumWords(); 173130803Smarcel for (unsigned i = 0; i < NumWords; ++i) 174130803Smarcel ID.AddInteger(pVal[i]); 175130803Smarcel} 176130803Smarcel 177130803Smarcel/// add_1 - This function adds a single "digit" integer, y, to the multiple 178130803Smarcel/// "digit" integer array, x[]. x[] is modified to reflect the addition and 179130803Smarcel/// 1 is returned if there is a carry out, otherwise 0 is returned. 180130803Smarcel/// @returns the carry of the addition. 181130803Smarcelstatic bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) { 182130803Smarcel for (unsigned i = 0; i < len; ++i) { 183130803Smarcel dest[i] = y + x[i]; 184130803Smarcel if (dest[i] < y) 185130803Smarcel y = 1; // Carry one to next digit. 186130803Smarcel else { 187130803Smarcel y = 0; // No need to carry so exit early 188130803Smarcel break; 189130803Smarcel } 190130803Smarcel } 191130803Smarcel return y; 192130803Smarcel} 193130803Smarcel 194130803Smarcel/// @brief Prefix increment operator. Increments the APInt by one. 195130803SmarcelAPInt& APInt::operator++() { 196130803Smarcel if (isSingleWord()) 197130803Smarcel ++VAL; 198130803Smarcel else 199130803Smarcel add_1(pVal, pVal, getNumWords(), 1); 200130803Smarcel return clearUnusedBits(); 201130803Smarcel} 202130803Smarcel 203130803Smarcel/// sub_1 - This function subtracts a single "digit" (64-bit word), y, from 204130803Smarcel/// the multi-digit integer array, x[], propagating the borrowed 1 value until 205130803Smarcel/// no further borrowing is neeeded or it runs out of "digits" in x. The result 206130803Smarcel/// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted. 207130803Smarcel/// In other words, if y > x then this function returns 1, otherwise 0. 208130803Smarcel/// @returns the borrow out of the subtraction 209130803Smarcelstatic bool sub_1(uint64_t x[], unsigned len, uint64_t y) { 210130803Smarcel for (unsigned i = 0; i < len; ++i) { 211130803Smarcel uint64_t X = x[i]; 212130803Smarcel x[i] -= y; 213130803Smarcel if (y > X) 214130803Smarcel y = 1; // We have to "borrow 1" from next "digit" 215130803Smarcel else { 216130803Smarcel y = 0; // No need to borrow 217130803Smarcel break; // Remaining digits are unchanged so exit early 218130803Smarcel } 219130803Smarcel } 220130803Smarcel return bool(y); 221130803Smarcel} 222130803Smarcel 223130803Smarcel/// @brief Prefix decrement operator. Decrements the APInt by one. 224130803SmarcelAPInt& APInt::operator--() { 225130803Smarcel if (isSingleWord()) 226130803Smarcel --VAL; 227130803Smarcel else 228130803Smarcel sub_1(pVal, getNumWords(), 1); 229130803Smarcel return clearUnusedBits(); 230130803Smarcel} 231130803Smarcel 232130803Smarcel/// add - This function adds the integer array x to the integer array Y and 233130803Smarcel/// places the result in dest. 234130803Smarcel/// @returns the carry out from the addition 235130803Smarcel/// @brief General addition of 64-bit integer arrays 236130803Smarcelstatic bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y, 237130803Smarcel unsigned len) { 238130803Smarcel bool carry = false; 239130803Smarcel for (unsigned i = 0; i< len; ++i) { 240130803Smarcel uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x 241130803Smarcel dest[i] = x[i] + y[i] + carry; 242130803Smarcel carry = dest[i] < limit || (carry && dest[i] == limit); 243130803Smarcel } 244130803Smarcel return carry; 245130803Smarcel} 246130803Smarcel 247130803Smarcel/// Adds the RHS APint to this APInt. 248130803Smarcel/// @returns this, after addition of RHS. 249130803Smarcel/// @brief Addition assignment operator. 250130803SmarcelAPInt& APInt::operator+=(const APInt& RHS) { 251130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 252130803Smarcel if (isSingleWord()) 253130803Smarcel VAL += RHS.VAL; 254130803Smarcel else { 255130803Smarcel add(pVal, pVal, RHS.pVal, getNumWords()); 256130803Smarcel } 257130803Smarcel return clearUnusedBits(); 258130803Smarcel} 259130803Smarcel 260130803Smarcel/// Subtracts the integer array y from the integer array x 261130803Smarcel/// @returns returns the borrow out. 262130803Smarcel/// @brief Generalized subtraction of 64-bit integer arrays. 263130803Smarcelstatic bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y, 264130803Smarcel unsigned len) { 265130803Smarcel bool borrow = false; 266130803Smarcel for (unsigned i = 0; i < len; ++i) { 267130803Smarcel uint64_t x_tmp = borrow ? x[i] - 1 : x[i]; 268130803Smarcel borrow = y[i] > x_tmp || (borrow && x[i] == 0); 269130803Smarcel dest[i] = x_tmp - y[i]; 270130803Smarcel } 271130803Smarcel return borrow; 272130803Smarcel} 273130803Smarcel 274130803Smarcel/// Subtracts the RHS APInt from this APInt 275130803Smarcel/// @returns this, after subtraction 276130803Smarcel/// @brief Subtraction assignment operator. 277130803SmarcelAPInt& APInt::operator-=(const APInt& RHS) { 278130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 279130803Smarcel if (isSingleWord()) 280130803Smarcel VAL -= RHS.VAL; 281130803Smarcel else 282130803Smarcel sub(pVal, pVal, RHS.pVal, getNumWords()); 283130803Smarcel return clearUnusedBits(); 284130803Smarcel} 285130803Smarcel 286130803Smarcel/// Multiplies an integer array, x, by a uint64_t integer and places the result 287130803Smarcel/// into dest. 288130803Smarcel/// @returns the carry out of the multiplication. 289130803Smarcel/// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer. 290130803Smarcelstatic uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) { 291130803Smarcel // Split y into high 32-bit part (hy) and low 32-bit part (ly) 292130803Smarcel uint64_t ly = y & 0xffffffffULL, hy = y >> 32; 293130803Smarcel uint64_t carry = 0; 294130803Smarcel 295130803Smarcel // For each digit of x. 296130803Smarcel for (unsigned i = 0; i < len; ++i) { 297130803Smarcel // Split x into high and low words 298130803Smarcel uint64_t lx = x[i] & 0xffffffffULL; 299130803Smarcel uint64_t hx = x[i] >> 32; 300130803Smarcel // hasCarry - A flag to indicate if there is a carry to the next digit. 301130803Smarcel // hasCarry == 0, no carry 302130803Smarcel // hasCarry == 1, has carry 303130803Smarcel // hasCarry == 2, no carry and the calculation result == 0. 304130803Smarcel uint8_t hasCarry = 0; 305130803Smarcel dest[i] = carry + lx * ly; 306130803Smarcel // Determine if the add above introduces carry. 307130803Smarcel hasCarry = (dest[i] < carry) ? 1 : 0; 308130803Smarcel carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0); 309130803Smarcel // The upper limit of carry can be (2^32 - 1)(2^32 - 1) + 310130803Smarcel // (2^32 - 1) + 2^32 = 2^64. 311130803Smarcel hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 312130803Smarcel 313130803Smarcel carry += (lx * hy) & 0xffffffffULL; 314130803Smarcel dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL); 315130803Smarcel carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) + 316130803Smarcel (carry >> 32) + ((lx * hy) >> 32) + hx * hy; 317130803Smarcel } 318130803Smarcel return carry; 319130803Smarcel} 320130803Smarcel 321130803Smarcel/// Multiplies integer array x by integer array y and stores the result into 322130803Smarcel/// the integer array dest. Note that dest's size must be >= xlen + ylen. 323130803Smarcel/// @brief Generalized multiplicate of integer arrays. 324130803Smarcelstatic void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[], 325130803Smarcel unsigned ylen) { 326130803Smarcel dest[xlen] = mul_1(dest, x, xlen, y[0]); 327130803Smarcel for (unsigned i = 1; i < ylen; ++i) { 328130803Smarcel uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32; 329130803Smarcel uint64_t carry = 0, lx = 0, hx = 0; 330130803Smarcel for (unsigned j = 0; j < xlen; ++j) { 331130803Smarcel lx = x[j] & 0xffffffffULL; 332130803Smarcel hx = x[j] >> 32; 333130803Smarcel // hasCarry - A flag to indicate if has carry. 334130803Smarcel // hasCarry == 0, no carry 335130803Smarcel // hasCarry == 1, has carry 336130803Smarcel // hasCarry == 2, no carry and the calculation result == 0. 337130803Smarcel uint8_t hasCarry = 0; 338130803Smarcel uint64_t resul = carry + lx * ly; 339130803Smarcel hasCarry = (resul < carry) ? 1 : 0; 340130803Smarcel carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32); 341130803Smarcel hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 342130803Smarcel 343130803Smarcel carry += (lx * hy) & 0xffffffffULL; 344130803Smarcel resul = (carry << 32) | (resul & 0xffffffffULL); 345130803Smarcel dest[i+j] += resul; 346130803Smarcel carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+ 347130803Smarcel (carry >> 32) + (dest[i+j] < resul ? 1 : 0) + 348130803Smarcel ((lx * hy) >> 32) + hx * hy; 349130803Smarcel } 350130803Smarcel dest[i+xlen] = carry; 351130803Smarcel } 352130803Smarcel} 353130803Smarcel 354130803SmarcelAPInt& APInt::operator*=(const APInt& RHS) { 355130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 356130803Smarcel if (isSingleWord()) { 357130803Smarcel VAL *= RHS.VAL; 358130803Smarcel clearUnusedBits(); 359130803Smarcel return *this; 360130803Smarcel } 361130803Smarcel 362130803Smarcel // Get some bit facts about LHS and check for zero 363130803Smarcel unsigned lhsBits = getActiveBits(); 364130803Smarcel unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1; 365130803Smarcel if (!lhsWords) 366130803Smarcel // 0 * X ===> 0 367130803Smarcel return *this; 368130803Smarcel 369130803Smarcel // Get some bit facts about RHS and check for zero 370130803Smarcel unsigned rhsBits = RHS.getActiveBits(); 371130803Smarcel unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1; 372130803Smarcel if (!rhsWords) { 373130803Smarcel // X * 0 ===> 0 374130803Smarcel clearAllBits(); 375130803Smarcel return *this; 376130803Smarcel } 377130803Smarcel 378130803Smarcel // Allocate space for the result 379130803Smarcel unsigned destWords = rhsWords + lhsWords; 380130803Smarcel uint64_t *dest = getMemory(destWords); 381130803Smarcel 382130803Smarcel // Perform the long multiply 383130803Smarcel mul(dest, pVal, lhsWords, RHS.pVal, rhsWords); 384130803Smarcel 385130803Smarcel // Copy result back into *this 386130803Smarcel clearAllBits(); 387130803Smarcel unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords; 388130803Smarcel memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE); 389130803Smarcel clearUnusedBits(); 390130803Smarcel 391130803Smarcel // delete dest array and return 392130803Smarcel delete[] dest; 393130803Smarcel return *this; 394130803Smarcel} 395130803Smarcel 396130803SmarcelAPInt& APInt::operator&=(const APInt& RHS) { 397130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 398130803Smarcel if (isSingleWord()) { 399130803Smarcel VAL &= RHS.VAL; 400130803Smarcel return *this; 401130803Smarcel } 402130803Smarcel unsigned numWords = getNumWords(); 403130803Smarcel for (unsigned i = 0; i < numWords; ++i) 404130803Smarcel pVal[i] &= RHS.pVal[i]; 405130803Smarcel return *this; 406130803Smarcel} 407130803Smarcel 408130803SmarcelAPInt& APInt::operator|=(const APInt& RHS) { 409130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 410130803Smarcel if (isSingleWord()) { 411130803Smarcel VAL |= RHS.VAL; 412130803Smarcel return *this; 413130803Smarcel } 414130803Smarcel unsigned numWords = getNumWords(); 415130803Smarcel for (unsigned i = 0; i < numWords; ++i) 416130803Smarcel pVal[i] |= RHS.pVal[i]; 417130803Smarcel return *this; 418130803Smarcel} 419130803Smarcel 420130803SmarcelAPInt& APInt::operator^=(const APInt& RHS) { 421130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 422130803Smarcel if (isSingleWord()) { 423130803Smarcel VAL ^= RHS.VAL; 424130803Smarcel this->clearUnusedBits(); 425130803Smarcel return *this; 426130803Smarcel } 427130803Smarcel unsigned numWords = getNumWords(); 428130803Smarcel for (unsigned i = 0; i < numWords; ++i) 429130803Smarcel pVal[i] ^= RHS.pVal[i]; 430130803Smarcel return clearUnusedBits(); 431130803Smarcel} 432130803Smarcel 433130803SmarcelAPInt APInt::AndSlowCase(const APInt& RHS) const { 434130803Smarcel unsigned numWords = getNumWords(); 435130803Smarcel uint64_t* val = getMemory(numWords); 436130803Smarcel for (unsigned i = 0; i < numWords; ++i) 437130803Smarcel val[i] = pVal[i] & RHS.pVal[i]; 438130803Smarcel return APInt(val, getBitWidth()); 439130803Smarcel} 440130803Smarcel 441130803SmarcelAPInt APInt::OrSlowCase(const APInt& RHS) const { 442130803Smarcel unsigned numWords = getNumWords(); 443130803Smarcel uint64_t *val = getMemory(numWords); 444130803Smarcel for (unsigned i = 0; i < numWords; ++i) 445130803Smarcel val[i] = pVal[i] | RHS.pVal[i]; 446130803Smarcel return APInt(val, getBitWidth()); 447130803Smarcel} 448130803Smarcel 449130803SmarcelAPInt APInt::XorSlowCase(const APInt& RHS) const { 450130803Smarcel unsigned numWords = getNumWords(); 451130803Smarcel uint64_t *val = getMemory(numWords); 452130803Smarcel for (unsigned i = 0; i < numWords; ++i) 453130803Smarcel val[i] = pVal[i] ^ RHS.pVal[i]; 454130803Smarcel 455130803Smarcel // 0^0==1 so clear the high bits in case they got set. 456130803Smarcel return APInt(val, getBitWidth()).clearUnusedBits(); 457130803Smarcel} 458130803Smarcel 459130803Smarcelbool APInt::operator !() const { 460130803Smarcel if (isSingleWord()) 461130803Smarcel return !VAL; 462130803Smarcel 463130803Smarcel for (unsigned i = 0; i < getNumWords(); ++i) 464130803Smarcel if (pVal[i]) 465130803Smarcel return false; 466130803Smarcel return true; 467130803Smarcel} 468130803Smarcel 469130803SmarcelAPInt APInt::operator*(const APInt& RHS) const { 470130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 471130803Smarcel if (isSingleWord()) 472130803Smarcel return APInt(BitWidth, VAL * RHS.VAL); 473130803Smarcel APInt Result(*this); 474130803Smarcel Result *= RHS; 475130803Smarcel return Result; 476130803Smarcel} 477130803Smarcel 478130803SmarcelAPInt APInt::operator+(const APInt& RHS) const { 479130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 480130803Smarcel if (isSingleWord()) 481130803Smarcel return APInt(BitWidth, VAL + RHS.VAL); 482130803Smarcel APInt Result(BitWidth, 0); 483130803Smarcel add(Result.pVal, this->pVal, RHS.pVal, getNumWords()); 484130803Smarcel return Result.clearUnusedBits(); 485130803Smarcel} 486130803Smarcel 487130803SmarcelAPInt APInt::operator-(const APInt& RHS) const { 488130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 489130803Smarcel if (isSingleWord()) 490130803Smarcel return APInt(BitWidth, VAL - RHS.VAL); 491130803Smarcel APInt Result(BitWidth, 0); 492130803Smarcel sub(Result.pVal, this->pVal, RHS.pVal, getNumWords()); 493130803Smarcel return Result.clearUnusedBits(); 494130803Smarcel} 495130803Smarcel 496130803Smarcelbool APInt::operator[](unsigned bitPosition) const { 497130803Smarcel assert(bitPosition < getBitWidth() && "Bit position out of bounds!"); 498130803Smarcel return (maskBit(bitPosition) & 499130803Smarcel (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0; 500130803Smarcel} 501130803Smarcel 502130803Smarcelbool APInt::EqualSlowCase(const APInt& RHS) const { 503130803Smarcel // Get some facts about the number of bits used in the two operands. 504130803Smarcel unsigned n1 = getActiveBits(); 505130803Smarcel unsigned n2 = RHS.getActiveBits(); 506130803Smarcel 507130803Smarcel // If the number of bits isn't the same, they aren't equal 508130803Smarcel if (n1 != n2) 509130803Smarcel return false; 510130803Smarcel 511130803Smarcel // If the number of bits fits in a word, we only need to compare the low word. 512130803Smarcel if (n1 <= APINT_BITS_PER_WORD) 513130803Smarcel return pVal[0] == RHS.pVal[0]; 514130803Smarcel 515130803Smarcel // Otherwise, compare everything 516130803Smarcel for (int i = whichWord(n1 - 1); i >= 0; --i) 517130803Smarcel if (pVal[i] != RHS.pVal[i]) 518130803Smarcel return false; 519130803Smarcel return true; 520130803Smarcel} 521130803Smarcel 522130803Smarcelbool APInt::EqualSlowCase(uint64_t Val) const { 523130803Smarcel unsigned n = getActiveBits(); 524130803Smarcel if (n <= APINT_BITS_PER_WORD) 525130803Smarcel return pVal[0] == Val; 526130803Smarcel else 527130803Smarcel return false; 528130803Smarcel} 529130803Smarcel 530130803Smarcelbool APInt::ult(const APInt& RHS) const { 531130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"); 532130803Smarcel if (isSingleWord()) 533130803Smarcel return VAL < RHS.VAL; 534130803Smarcel 535130803Smarcel // Get active bit length of both operands 536130803Smarcel unsigned n1 = getActiveBits(); 537130803Smarcel unsigned n2 = RHS.getActiveBits(); 538130803Smarcel 539130803Smarcel // If magnitude of LHS is less than RHS, return true. 540130803Smarcel if (n1 < n2) 541130803Smarcel return true; 542130803Smarcel 543130803Smarcel // If magnitude of RHS is greather than LHS, return false. 544130803Smarcel if (n2 < n1) 545130803Smarcel return false; 546130803Smarcel 547130803Smarcel // If they bot fit in a word, just compare the low order word 548130803Smarcel if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD) 549130803Smarcel return pVal[0] < RHS.pVal[0]; 550130803Smarcel 551130803Smarcel // Otherwise, compare all words 552130803Smarcel unsigned topWord = whichWord(std::max(n1,n2)-1); 553130803Smarcel for (int i = topWord; i >= 0; --i) { 554130803Smarcel if (pVal[i] > RHS.pVal[i]) 555130803Smarcel return false; 556130803Smarcel if (pVal[i] < RHS.pVal[i]) 557130803Smarcel return true; 558130803Smarcel } 559130803Smarcel return false; 560130803Smarcel} 561130803Smarcel 562130803Smarcelbool APInt::slt(const APInt& RHS) const { 563130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"); 564130803Smarcel if (isSingleWord()) { 565130803Smarcel int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth); 566130803Smarcel int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth); 567130803Smarcel return lhsSext < rhsSext; 568130803Smarcel } 569130803Smarcel 570130803Smarcel APInt lhs(*this); 571130803Smarcel APInt rhs(RHS); 572130803Smarcel bool lhsNeg = isNegative(); 573130803Smarcel bool rhsNeg = rhs.isNegative(); 574130803Smarcel if (lhsNeg) { 575130803Smarcel // Sign bit is set so perform two's complement to make it positive 576130803Smarcel lhs.flipAllBits(); 577130803Smarcel lhs++; 578130803Smarcel } 579130803Smarcel if (rhsNeg) { 580130803Smarcel // Sign bit is set so perform two's complement to make it positive 581130803Smarcel rhs.flipAllBits(); 582130803Smarcel rhs++; 583130803Smarcel } 584130803Smarcel 585130803Smarcel // Now we have unsigned values to compare so do the comparison if necessary 586130803Smarcel // based on the negativeness of the values. 587130803Smarcel if (lhsNeg) 588130803Smarcel if (rhsNeg) 589130803Smarcel return lhs.ugt(rhs); 590130803Smarcel else 591130803Smarcel return true; 592130803Smarcel else if (rhsNeg) 593130803Smarcel return false; 594130803Smarcel else 595130803Smarcel return lhs.ult(rhs); 596130803Smarcel} 597130803Smarcel 598130803Smarcelvoid APInt::setBit(unsigned bitPosition) { 599130803Smarcel if (isSingleWord()) 600130803Smarcel VAL |= maskBit(bitPosition); 601130803Smarcel else 602130803Smarcel pVal[whichWord(bitPosition)] |= maskBit(bitPosition); 603130803Smarcel} 604130803Smarcel 605130803Smarcel/// Set the given bit to 0 whose position is given as "bitPosition". 606130803Smarcel/// @brief Set a given bit to 0. 607130803Smarcelvoid APInt::clearBit(unsigned bitPosition) { 608130803Smarcel if (isSingleWord()) 609130803Smarcel VAL &= ~maskBit(bitPosition); 610130803Smarcel else 611130803Smarcel pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition); 612130803Smarcel} 613130803Smarcel 614130803Smarcel/// @brief Toggle every bit to its opposite value. 615130803Smarcel 616130803Smarcel/// Toggle a given bit to its opposite value whose position is given 617130803Smarcel/// as "bitPosition". 618130803Smarcel/// @brief Toggles a given bit to its opposite value. 619130803Smarcelvoid APInt::flipBit(unsigned bitPosition) { 620130803Smarcel assert(bitPosition < BitWidth && "Out of the bit-width range!"); 621130803Smarcel if ((*this)[bitPosition]) clearBit(bitPosition); 622130803Smarcel else setBit(bitPosition); 623130803Smarcel} 624130803Smarcel 625130803Smarcelunsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) { 626130803Smarcel assert(!str.empty() && "Invalid string length"); 627130803Smarcel assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 || 628130803Smarcel radix == 36) && 629130803Smarcel "Radix should be 2, 8, 10, 16, or 36!"); 630130803Smarcel 631130803Smarcel size_t slen = str.size(); 632130803Smarcel 633130803Smarcel // Each computation below needs to know if it's negative. 634130803Smarcel StringRef::iterator p = str.begin(); 635130803Smarcel unsigned isNegative = *p == '-'; 636130803Smarcel if (*p == '-' || *p == '+') { 637130803Smarcel p++; 638130803Smarcel slen--; 639130803Smarcel assert(slen && "String is only a sign, needs a value."); 640130803Smarcel } 641130803Smarcel 642130803Smarcel // For radixes of power-of-two values, the bits required is accurately and 643130803Smarcel // easily computed 644130803Smarcel if (radix == 2) 645130803Smarcel return slen + isNegative; 646130803Smarcel if (radix == 8) 647130803Smarcel return slen * 3 + isNegative; 648130803Smarcel if (radix == 16) 649130803Smarcel return slen * 4 + isNegative; 650130803Smarcel 651130803Smarcel // FIXME: base 36 652130803Smarcel 653130803Smarcel // This is grossly inefficient but accurate. We could probably do something 654130803Smarcel // with a computation of roughly slen*64/20 and then adjust by the value of 655130803Smarcel // the first few digits. But, I'm not sure how accurate that could be. 656130803Smarcel 657130803Smarcel // Compute a sufficient number of bits that is always large enough but might 658130803Smarcel // be too large. This avoids the assertion in the constructor. This 659130803Smarcel // calculation doesn't work appropriately for the numbers 0-9, so just use 4 660130803Smarcel // bits in that case. 661130803Smarcel unsigned sufficient 662130803Smarcel = radix == 10? (slen == 1 ? 4 : slen * 64/18) 663130803Smarcel : (slen == 1 ? 7 : slen * 16/3); 664130803Smarcel 665130803Smarcel // Convert to the actual binary value. 666130803Smarcel APInt tmp(sufficient, StringRef(p, slen), radix); 667130803Smarcel 668130803Smarcel // Compute how many bits are required. If the log is infinite, assume we need 669130803Smarcel // just bit. 670130803Smarcel unsigned log = tmp.logBase2(); 671130803Smarcel if (log == (unsigned)-1) { 672130803Smarcel return isNegative + 1; 673130803Smarcel } else { 674130803Smarcel return isNegative + log + 1; 675130803Smarcel } 676130803Smarcel} 677130803Smarcel 678130803Smarcel// From http://www.burtleburtle.net, byBob Jenkins. 679130803Smarcel// When targeting x86, both GCC and LLVM seem to recognize this as a 680130803Smarcel// rotate instruction. 681130803Smarcel#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 682130803Smarcel 683130803Smarcel// From http://www.burtleburtle.net, by Bob Jenkins. 684130803Smarcel#define mix(a,b,c) \ 685130803Smarcel { \ 686130803Smarcel a -= c; a ^= rot(c, 4); c += b; \ 687130803Smarcel b -= a; b ^= rot(a, 6); a += c; \ 688130803Smarcel c -= b; c ^= rot(b, 8); b += a; \ 689130803Smarcel a -= c; a ^= rot(c,16); c += b; \ 690130803Smarcel b -= a; b ^= rot(a,19); a += c; \ 691130803Smarcel c -= b; c ^= rot(b, 4); b += a; \ 692130803Smarcel } 693130803Smarcel 694130803Smarcel// From http://www.burtleburtle.net, by Bob Jenkins. 695130803Smarcel#define final(a,b,c) \ 696130803Smarcel { \ 697130803Smarcel c ^= b; c -= rot(b,14); \ 698130803Smarcel a ^= c; a -= rot(c,11); \ 699130803Smarcel b ^= a; b -= rot(a,25); \ 700130803Smarcel c ^= b; c -= rot(b,16); \ 701130803Smarcel a ^= c; a -= rot(c,4); \ 702130803Smarcel b ^= a; b -= rot(a,14); \ 703130803Smarcel c ^= b; c -= rot(b,24); \ 704130803Smarcel } 705130803Smarcel 706130803Smarcel// hashword() was adapted from http://www.burtleburtle.net, by Bob 707130803Smarcel// Jenkins. k is a pointer to an array of uint32_t values; length is 708130803Smarcel// the length of the key, in 32-bit chunks. This version only handles 709130803Smarcel// keys that are a multiple of 32 bits in size. 710130803Smarcelstatic inline uint32_t hashword(const uint64_t *k64, size_t length) 711130803Smarcel{ 712130803Smarcel const uint32_t *k = reinterpret_cast<const uint32_t *>(k64); 713130803Smarcel uint32_t a,b,c; 714130803Smarcel 715130803Smarcel /* Set up the internal state */ 716130803Smarcel a = b = c = 0xdeadbeef + (((uint32_t)length)<<2); 717130803Smarcel 718130803Smarcel /*------------------------------------------------- handle most of the key */ 719130803Smarcel while (length > 3) { 720130803Smarcel a += k[0]; 721130803Smarcel b += k[1]; 722130803Smarcel c += k[2]; 723130803Smarcel mix(a,b,c); 724130803Smarcel length -= 3; 725130803Smarcel k += 3; 726130803Smarcel } 727130803Smarcel 728130803Smarcel /*------------------------------------------- handle the last 3 uint32_t's */ 729130803Smarcel switch (length) { /* all the case statements fall through */ 730130803Smarcel case 3 : c+=k[2]; 731130803Smarcel case 2 : b+=k[1]; 732130803Smarcel case 1 : a+=k[0]; 733130803Smarcel final(a,b,c); 734130803Smarcel case 0: /* case 0: nothing left to add */ 735130803Smarcel break; 736130803Smarcel } 737130803Smarcel /*------------------------------------------------------ report the result */ 738130803Smarcel return c; 739130803Smarcel} 740130803Smarcel 741130803Smarcel// hashword8() was adapted from http://www.burtleburtle.net, by Bob 742130803Smarcel// Jenkins. This computes a 32-bit hash from one 64-bit word. When 743130803Smarcel// targeting x86 (32 or 64 bit), both LLVM and GCC compile this 744130803Smarcel// function into about 35 instructions when inlined. 745130803Smarcelstatic inline uint32_t hashword8(const uint64_t k64) 746130803Smarcel{ 747130803Smarcel uint32_t a,b,c; 748130803Smarcel a = b = c = 0xdeadbeef + 4; 749130803Smarcel b += k64 >> 32; 750130803Smarcel a += k64 & 0xffffffff; 751130803Smarcel final(a,b,c); 752130803Smarcel return c; 753130803Smarcel} 754130803Smarcel#undef final 755130803Smarcel#undef mix 756130803Smarcel#undef rot 757130803Smarcel 758130803Smarceluint64_t APInt::getHashValue() const { 759130803Smarcel uint64_t hash; 760130803Smarcel if (isSingleWord()) 761130803Smarcel hash = hashword8(VAL); 762130803Smarcel else 763130803Smarcel hash = hashword(pVal, getNumWords()*2); 764130803Smarcel return hash; 765130803Smarcel} 766130803Smarcel 767130803Smarcel/// HiBits - This function returns the high "numBits" bits of this APInt. 768130803SmarcelAPInt APInt::getHiBits(unsigned numBits) const { 769130803Smarcel return APIntOps::lshr(*this, BitWidth - numBits); 770130803Smarcel} 771130803Smarcel 772130803Smarcel/// LoBits - This function returns the low "numBits" bits of this APInt. 773130803SmarcelAPInt APInt::getLoBits(unsigned numBits) const { 774130803Smarcel return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits), 775130803Smarcel BitWidth - numBits); 776130803Smarcel} 777130803Smarcel 778130803Smarcelunsigned APInt::countLeadingZerosSlowCase() const { 779130803Smarcel // Treat the most significand word differently because it might have 780130803Smarcel // meaningless bits set beyond the precision. 781130803Smarcel unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD; 782130803Smarcel integerPart MSWMask; 783130803Smarcel if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1; 784130803Smarcel else { 785130803Smarcel MSWMask = ~integerPart(0); 786130803Smarcel BitsInMSW = APINT_BITS_PER_WORD; 787130803Smarcel } 788130803Smarcel 789130803Smarcel unsigned i = getNumWords(); 790130803Smarcel integerPart MSW = pVal[i-1] & MSWMask; 791130803Smarcel if (MSW) 792130803Smarcel return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW); 793130803Smarcel 794130803Smarcel unsigned Count = BitsInMSW; 795130803Smarcel for (--i; i > 0u; --i) { 796130803Smarcel if (pVal[i-1] == 0) 797130803Smarcel Count += APINT_BITS_PER_WORD; 798130803Smarcel else { 799130803Smarcel Count += CountLeadingZeros_64(pVal[i-1]); 800130803Smarcel break; 801130803Smarcel } 802130803Smarcel } 803130803Smarcel return Count; 804130803Smarcel} 805130803Smarcel 806130803Smarcelstatic unsigned countLeadingOnes_64(uint64_t V, unsigned skip) { 807130803Smarcel unsigned Count = 0; 808130803Smarcel if (skip) 809130803Smarcel V <<= skip; 810130803Smarcel while (V && (V & (1ULL << 63))) { 811130803Smarcel Count++; 812130803Smarcel V <<= 1; 813130803Smarcel } 814130803Smarcel return Count; 815130803Smarcel} 816130803Smarcel 817130803Smarcelunsigned APInt::countLeadingOnes() const { 818130803Smarcel if (isSingleWord()) 819130803Smarcel return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth); 820130803Smarcel 821130803Smarcel unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD; 822130803Smarcel unsigned shift; 823130803Smarcel if (!highWordBits) { 824130803Smarcel highWordBits = APINT_BITS_PER_WORD; 825130803Smarcel shift = 0; 826130803Smarcel } else { 827130803Smarcel shift = APINT_BITS_PER_WORD - highWordBits; 828130803Smarcel } 829130803Smarcel int i = getNumWords() - 1; 830130803Smarcel unsigned Count = countLeadingOnes_64(pVal[i], shift); 831130803Smarcel if (Count == highWordBits) { 832130803Smarcel for (i--; i >= 0; --i) { 833130803Smarcel if (pVal[i] == -1ULL) 834130803Smarcel Count += APINT_BITS_PER_WORD; 835130803Smarcel else { 836130803Smarcel Count += countLeadingOnes_64(pVal[i], 0); 837130803Smarcel break; 838130803Smarcel } 839130803Smarcel } 840130803Smarcel } 841130803Smarcel return Count; 842130803Smarcel} 843130803Smarcel 844130803Smarcelunsigned APInt::countTrailingZeros() const { 845130803Smarcel if (isSingleWord()) 846130803Smarcel return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth); 847130803Smarcel unsigned Count = 0; 848130803Smarcel unsigned i = 0; 849130803Smarcel for (; i < getNumWords() && pVal[i] == 0; ++i) 850130803Smarcel Count += APINT_BITS_PER_WORD; 851130803Smarcel if (i < getNumWords()) 852130803Smarcel Count += CountTrailingZeros_64(pVal[i]); 853130803Smarcel return std::min(Count, BitWidth); 854130803Smarcel} 855130803Smarcel 856130803Smarcelunsigned APInt::countTrailingOnesSlowCase() const { 857130803Smarcel unsigned Count = 0; 858130803Smarcel unsigned i = 0; 859130803Smarcel for (; i < getNumWords() && pVal[i] == -1ULL; ++i) 860130803Smarcel Count += APINT_BITS_PER_WORD; 861130803Smarcel if (i < getNumWords()) 862130803Smarcel Count += CountTrailingOnes_64(pVal[i]); 863130803Smarcel return std::min(Count, BitWidth); 864130803Smarcel} 865130803Smarcel 866130803Smarcelunsigned APInt::countPopulationSlowCase() const { 867130803Smarcel unsigned Count = 0; 868130803Smarcel for (unsigned i = 0; i < getNumWords(); ++i) 869130803Smarcel Count += CountPopulation_64(pVal[i]); 870130803Smarcel return Count; 871130803Smarcel} 872130803Smarcel 873130803SmarcelAPInt APInt::byteSwap() const { 874130803Smarcel assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!"); 875130803Smarcel if (BitWidth == 16) 876130803Smarcel return APInt(BitWidth, ByteSwap_16(uint16_t(VAL))); 877130803Smarcel else if (BitWidth == 32) 878130803Smarcel return APInt(BitWidth, ByteSwap_32(unsigned(VAL))); 879130803Smarcel else if (BitWidth == 48) { 880130803Smarcel unsigned Tmp1 = unsigned(VAL >> 16); 881130803Smarcel Tmp1 = ByteSwap_32(Tmp1); 882130803Smarcel uint16_t Tmp2 = uint16_t(VAL); 883130803Smarcel Tmp2 = ByteSwap_16(Tmp2); 884130803Smarcel return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1); 885130803Smarcel } else if (BitWidth == 64) 886130803Smarcel return APInt(BitWidth, ByteSwap_64(VAL)); 887130803Smarcel else { 888130803Smarcel APInt Result(BitWidth, 0); 889130803Smarcel char *pByte = (char*)Result.pVal; 890130803Smarcel for (unsigned i = 0; i < BitWidth / APINT_WORD_SIZE / 2; ++i) { 891130803Smarcel char Tmp = pByte[i]; 892130803Smarcel pByte[i] = pByte[BitWidth / APINT_WORD_SIZE - 1 - i]; 893130803Smarcel pByte[BitWidth / APINT_WORD_SIZE - i - 1] = Tmp; 894130803Smarcel } 895130803Smarcel return Result; 896130803Smarcel } 897130803Smarcel} 898130803Smarcel 899130803SmarcelAPInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1, 900130803Smarcel const APInt& API2) { 901130803Smarcel APInt A = API1, B = API2; 902130803Smarcel while (!!B) { 903130803Smarcel APInt T = B; 904130803Smarcel B = APIntOps::urem(A, B); 905130803Smarcel A = T; 906130803Smarcel } 907130803Smarcel return A; 908130803Smarcel} 909130803Smarcel 910130803SmarcelAPInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) { 911130803Smarcel union { 912130803Smarcel double D; 913130803Smarcel uint64_t I; 914130803Smarcel } T; 915130803Smarcel T.D = Double; 916130803Smarcel 917130803Smarcel // Get the sign bit from the highest order bit 918130803Smarcel bool isNeg = T.I >> 63; 919130803Smarcel 920130803Smarcel // Get the 11-bit exponent and adjust for the 1023 bit bias 921130803Smarcel int64_t exp = ((T.I >> 52) & 0x7ff) - 1023; 922130803Smarcel 923130803Smarcel // If the exponent is negative, the value is < 0 so just return 0. 924130803Smarcel if (exp < 0) 925130803Smarcel return APInt(width, 0u); 926130803Smarcel 927130803Smarcel // Extract the mantissa by clearing the top 12 bits (sign + exponent). 928130803Smarcel uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52; 929130803Smarcel 930130803Smarcel // If the exponent doesn't shift all bits out of the mantissa 931130803Smarcel if (exp < 52) 932130803Smarcel return isNeg ? -APInt(width, mantissa >> (52 - exp)) : 933130803Smarcel APInt(width, mantissa >> (52 - exp)); 934130803Smarcel 935130803Smarcel // If the client didn't provide enough bits for us to shift the mantissa into 936130803Smarcel // then the result is undefined, just return 0 937130803Smarcel if (width <= exp - 52) 938130803Smarcel return APInt(width, 0); 939130803Smarcel 940130803Smarcel // Otherwise, we have to shift the mantissa bits up to the right location 941130803Smarcel APInt Tmp(width, mantissa); 942130803Smarcel Tmp = Tmp.shl((unsigned)exp - 52); 943130803Smarcel return isNeg ? -Tmp : Tmp; 944130803Smarcel} 945130803Smarcel 946130803Smarcel/// RoundToDouble - This function converts this APInt to a double. 947130803Smarcel/// The layout for double is as following (IEEE Standard 754): 948130803Smarcel/// -------------------------------------- 949130803Smarcel/// | Sign Exponent Fraction Bias | 950130803Smarcel/// |-------------------------------------- | 951130803Smarcel/// | 1[63] 11[62-52] 52[51-00] 1023 | 952130803Smarcel/// -------------------------------------- 953130803Smarceldouble APInt::roundToDouble(bool isSigned) const { 954130803Smarcel 955130803Smarcel // Handle the simple case where the value is contained in one uint64_t. 956130803Smarcel // It is wrong to optimize getWord(0) to VAL; there might be more than one word. 957130803Smarcel if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) { 958130803Smarcel if (isSigned) { 959130803Smarcel int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth); 960130803Smarcel return double(sext); 961130803Smarcel } else 962130803Smarcel return double(getWord(0)); 963130803Smarcel } 964130803Smarcel 965130803Smarcel // Determine if the value is negative. 966130803Smarcel bool isNeg = isSigned ? (*this)[BitWidth-1] : false; 967130803Smarcel 968130803Smarcel // Construct the absolute value if we're negative. 969130803Smarcel APInt Tmp(isNeg ? -(*this) : (*this)); 970130803Smarcel 971130803Smarcel // Figure out how many bits we're using. 972130803Smarcel unsigned n = Tmp.getActiveBits(); 973130803Smarcel 974130803Smarcel // The exponent (without bias normalization) is just the number of bits 975130803Smarcel // we are using. Note that the sign bit is gone since we constructed the 976130803Smarcel // absolute value. 977130803Smarcel uint64_t exp = n; 978130803Smarcel 979130803Smarcel // Return infinity for exponent overflow 980130803Smarcel if (exp > 1023) { 981130803Smarcel if (!isSigned || !isNeg) 982130803Smarcel return std::numeric_limits<double>::infinity(); 983130803Smarcel else 984130803Smarcel return -std::numeric_limits<double>::infinity(); 985130803Smarcel } 986130803Smarcel exp += 1023; // Increment for 1023 bias 987130803Smarcel 988130803Smarcel // Number of bits in mantissa is 52. To obtain the mantissa value, we must 989130803Smarcel // extract the high 52 bits from the correct words in pVal. 990130803Smarcel uint64_t mantissa; 991130803Smarcel unsigned hiWord = whichWord(n-1); 992130803Smarcel if (hiWord == 0) { 993130803Smarcel mantissa = Tmp.pVal[0]; 994130803Smarcel if (n > 52) 995130803Smarcel mantissa >>= n - 52; // shift down, we want the top 52 bits. 996130803Smarcel } else { 997130803Smarcel assert(hiWord > 0 && "huh?"); 998130803Smarcel uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD); 999130803Smarcel uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD); 1000130803Smarcel mantissa = hibits | lobits; 1001130803Smarcel } 1002130803Smarcel 1003130803Smarcel // The leading bit of mantissa is implicit, so get rid of it. 1004130803Smarcel uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0; 1005130803Smarcel union { 1006130803Smarcel double D; 1007130803Smarcel uint64_t I; 1008130803Smarcel } T; 1009130803Smarcel T.I = sign | (exp << 52) | mantissa; 1010130803Smarcel return T.D; 1011130803Smarcel} 1012130803Smarcel 1013130803Smarcel// Truncate to new width. 1014130803SmarcelAPInt APInt::trunc(unsigned width) const { 1015130803Smarcel assert(width < BitWidth && "Invalid APInt Truncate request"); 1016130803Smarcel assert(width && "Can't truncate to 0 bits"); 1017130803Smarcel 1018130803Smarcel if (width <= APINT_BITS_PER_WORD) 1019130803Smarcel return APInt(width, getRawData()[0]); 1020130803Smarcel 1021130803Smarcel APInt Result(getMemory(getNumWords(width)), width); 1022130803Smarcel 1023130803Smarcel // Copy full words. 1024130803Smarcel unsigned i; 1025130803Smarcel for (i = 0; i != width / APINT_BITS_PER_WORD; i++) 1026130803Smarcel Result.pVal[i] = pVal[i]; 1027130803Smarcel 1028130803Smarcel // Truncate and copy any partial word. 1029130803Smarcel unsigned bits = (0 - width) % APINT_BITS_PER_WORD; 1030130803Smarcel if (bits != 0) 1031130803Smarcel Result.pVal[i] = pVal[i] << bits >> bits; 1032130803Smarcel 1033130803Smarcel return Result; 1034130803Smarcel} 1035130803Smarcel 1036130803Smarcel// Sign extend to a new width. 1037130803SmarcelAPInt APInt::sext(unsigned width) const { 1038130803Smarcel assert(width > BitWidth && "Invalid APInt SignExtend request"); 1039130803Smarcel 1040130803Smarcel if (width <= APINT_BITS_PER_WORD) { 1041130803Smarcel uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth); 1042130803Smarcel val = (int64_t)val >> (width - BitWidth); 1043130803Smarcel return APInt(width, val >> (APINT_BITS_PER_WORD - width)); 1044130803Smarcel } 1045130803Smarcel 1046130803Smarcel APInt Result(getMemory(getNumWords(width)), width); 1047130803Smarcel 1048130803Smarcel // Copy full words. 1049130803Smarcel unsigned i; 1050130803Smarcel uint64_t word = 0; 1051130803Smarcel for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) { 1052130803Smarcel word = getRawData()[i]; 1053130803Smarcel Result.pVal[i] = word; 1054130803Smarcel } 1055130803Smarcel 1056130803Smarcel // Read and sign-extend any partial word. 1057130803Smarcel unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD; 1058130803Smarcel if (bits != 0) 1059130803Smarcel word = (int64_t)getRawData()[i] << bits >> bits; 1060130803Smarcel else 1061130803Smarcel word = (int64_t)word >> (APINT_BITS_PER_WORD - 1); 1062130803Smarcel 1063130803Smarcel // Write remaining full words. 1064130803Smarcel for (; i != width / APINT_BITS_PER_WORD; i++) { 1065130803Smarcel Result.pVal[i] = word; 1066130803Smarcel word = (int64_t)word >> (APINT_BITS_PER_WORD - 1); 1067130803Smarcel } 1068130803Smarcel 1069130803Smarcel // Write any partial word. 1070130803Smarcel bits = (0 - width) % APINT_BITS_PER_WORD; 1071130803Smarcel if (bits != 0) 1072130803Smarcel Result.pVal[i] = word << bits >> bits; 1073130803Smarcel 1074130803Smarcel return Result; 1075130803Smarcel} 1076130803Smarcel 1077130803Smarcel// Zero extend to a new width. 1078130803SmarcelAPInt APInt::zext(unsigned width) const { 1079130803Smarcel assert(width > BitWidth && "Invalid APInt ZeroExtend request"); 1080130803Smarcel 1081130803Smarcel if (width <= APINT_BITS_PER_WORD) 1082130803Smarcel return APInt(width, VAL); 1083130803Smarcel 1084130803Smarcel APInt Result(getMemory(getNumWords(width)), width); 1085130803Smarcel 1086130803Smarcel // Copy words. 1087130803Smarcel unsigned i; 1088130803Smarcel for (i = 0; i != getNumWords(); i++) 1089130803Smarcel Result.pVal[i] = getRawData()[i]; 1090130803Smarcel 1091130803Smarcel // Zero remaining words. 1092130803Smarcel memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE); 1093130803Smarcel 1094130803Smarcel return Result; 1095130803Smarcel} 1096130803Smarcel 1097130803SmarcelAPInt APInt::zextOrTrunc(unsigned width) const { 1098130803Smarcel if (BitWidth < width) 1099130803Smarcel return zext(width); 1100130803Smarcel if (BitWidth > width) 1101130803Smarcel return trunc(width); 1102130803Smarcel return *this; 1103130803Smarcel} 1104130803Smarcel 1105130803SmarcelAPInt APInt::sextOrTrunc(unsigned width) const { 1106130803Smarcel if (BitWidth < width) 1107130803Smarcel return sext(width); 1108130803Smarcel if (BitWidth > width) 1109130803Smarcel return trunc(width); 1110130803Smarcel return *this; 1111130803Smarcel} 1112130803Smarcel 1113130803Smarcel/// Arithmetic right-shift this APInt by shiftAmt. 1114130803Smarcel/// @brief Arithmetic right-shift function. 1115130803SmarcelAPInt APInt::ashr(const APInt &shiftAmt) const { 1116130803Smarcel return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth)); 1117130803Smarcel} 1118130803Smarcel 1119130803Smarcel/// Arithmetic right-shift this APInt by shiftAmt. 1120130803Smarcel/// @brief Arithmetic right-shift function. 1121130803SmarcelAPInt APInt::ashr(unsigned shiftAmt) const { 1122130803Smarcel assert(shiftAmt <= BitWidth && "Invalid shift amount"); 1123130803Smarcel // Handle a degenerate case 1124130803Smarcel if (shiftAmt == 0) 1125130803Smarcel return *this; 1126130803Smarcel 1127130803Smarcel // Handle single word shifts with built-in ashr 1128130803Smarcel if (isSingleWord()) { 1129130803Smarcel if (shiftAmt == BitWidth) 1130130803Smarcel return APInt(BitWidth, 0); // undefined 1131130803Smarcel else { 1132130803Smarcel unsigned SignBit = APINT_BITS_PER_WORD - BitWidth; 1133130803Smarcel return APInt(BitWidth, 1134130803Smarcel (((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt)); 1135130803Smarcel } 1136130803Smarcel } 1137130803Smarcel 1138130803Smarcel // If all the bits were shifted out, the result is, technically, undefined. 1139130803Smarcel // We return -1 if it was negative, 0 otherwise. We check this early to avoid 1140130803Smarcel // issues in the algorithm below. 1141130803Smarcel if (shiftAmt == BitWidth) { 1142130803Smarcel if (isNegative()) 1143130803Smarcel return APInt(BitWidth, -1ULL, true); 1144130803Smarcel else 1145130803Smarcel return APInt(BitWidth, 0); 1146130803Smarcel } 1147130803Smarcel 1148130803Smarcel // Create some space for the result. 1149130803Smarcel uint64_t * val = new uint64_t[getNumWords()]; 1150130803Smarcel 1151130803Smarcel // Compute some values needed by the following shift algorithms 1152130803Smarcel unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word 1153130803Smarcel unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift 1154130803Smarcel unsigned breakWord = getNumWords() - 1 - offset; // last word affected 1155130803Smarcel unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word? 1156130803Smarcel if (bitsInWord == 0) 1157130803Smarcel bitsInWord = APINT_BITS_PER_WORD; 1158130803Smarcel 1159130803Smarcel // If we are shifting whole words, just move whole words 1160130803Smarcel if (wordShift == 0) { 1161130803Smarcel // Move the words containing significant bits 1162130803Smarcel for (unsigned i = 0; i <= breakWord; ++i) 1163130803Smarcel val[i] = pVal[i+offset]; // move whole word 1164130803Smarcel 1165130803Smarcel // Adjust the top significant word for sign bit fill, if negative 1166130803Smarcel if (isNegative()) 1167130803Smarcel if (bitsInWord < APINT_BITS_PER_WORD) 1168130803Smarcel val[breakWord] |= ~0ULL << bitsInWord; // set high bits 1169130803Smarcel } else { 1170130803Smarcel // Shift the low order words 1171130803Smarcel for (unsigned i = 0; i < breakWord; ++i) { 1172130803Smarcel // This combines the shifted corresponding word with the low bits from 1173130803Smarcel // the next word (shifted into this word's high bits). 1174130803Smarcel val[i] = (pVal[i+offset] >> wordShift) | 1175130803Smarcel (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); 1176130803Smarcel } 1177130803Smarcel 1178130803Smarcel // Shift the break word. In this case there are no bits from the next word 1179130803Smarcel // to include in this word. 1180130803Smarcel val[breakWord] = pVal[breakWord+offset] >> wordShift; 1181130803Smarcel 1182130803Smarcel // Deal with sign extenstion in the break word, and possibly the word before 1183130803Smarcel // it. 1184130803Smarcel if (isNegative()) { 1185130803Smarcel if (wordShift > bitsInWord) { 1186130803Smarcel if (breakWord > 0) 1187130803Smarcel val[breakWord-1] |= 1188130803Smarcel ~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord)); 1189130803Smarcel val[breakWord] |= ~0ULL; 1190130803Smarcel } else 1191130803Smarcel val[breakWord] |= (~0ULL << (bitsInWord - wordShift)); 1192130803Smarcel } 1193130803Smarcel } 1194130803Smarcel 1195130803Smarcel // Remaining words are 0 or -1, just assign them. 1196130803Smarcel uint64_t fillValue = (isNegative() ? -1ULL : 0); 1197130803Smarcel for (unsigned i = breakWord+1; i < getNumWords(); ++i) 1198130803Smarcel val[i] = fillValue; 1199130803Smarcel return APInt(val, BitWidth).clearUnusedBits(); 1200130803Smarcel} 1201130803Smarcel 1202130803Smarcel/// Logical right-shift this APInt by shiftAmt. 1203130803Smarcel/// @brief Logical right-shift function. 1204130803SmarcelAPInt APInt::lshr(const APInt &shiftAmt) const { 1205130803Smarcel return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth)); 1206130803Smarcel} 1207130803Smarcel 1208130803Smarcel/// Logical right-shift this APInt by shiftAmt. 1209130803Smarcel/// @brief Logical right-shift function. 1210130803SmarcelAPInt APInt::lshr(unsigned shiftAmt) const { 1211130803Smarcel if (isSingleWord()) { 1212130803Smarcel if (shiftAmt == BitWidth) 1213130803Smarcel return APInt(BitWidth, 0); 1214130803Smarcel else 1215130803Smarcel return APInt(BitWidth, this->VAL >> shiftAmt); 1216130803Smarcel } 1217130803Smarcel 1218130803Smarcel // If all the bits were shifted out, the result is 0. This avoids issues 1219130803Smarcel // with shifting by the size of the integer type, which produces undefined 1220130803Smarcel // results. We define these "undefined results" to always be 0. 1221130803Smarcel if (shiftAmt == BitWidth) 1222130803Smarcel return APInt(BitWidth, 0); 1223130803Smarcel 1224130803Smarcel // If none of the bits are shifted out, the result is *this. This avoids 1225130803Smarcel // issues with shifting by the size of the integer type, which produces 1226130803Smarcel // undefined results in the code below. This is also an optimization. 1227130803Smarcel if (shiftAmt == 0) 1228130803Smarcel return *this; 1229130803Smarcel 1230130803Smarcel // Create some space for the result. 1231130803Smarcel uint64_t * val = new uint64_t[getNumWords()]; 1232130803Smarcel 1233130803Smarcel // If we are shifting less than a word, compute the shift with a simple carry 1234130803Smarcel if (shiftAmt < APINT_BITS_PER_WORD) { 1235130803Smarcel uint64_t carry = 0; 1236130803Smarcel for (int i = getNumWords()-1; i >= 0; --i) { 1237130803Smarcel val[i] = (pVal[i] >> shiftAmt) | carry; 1238130803Smarcel carry = pVal[i] << (APINT_BITS_PER_WORD - shiftAmt); 1239130803Smarcel } 1240130803Smarcel return APInt(val, BitWidth).clearUnusedBits(); 1241130803Smarcel } 1242130803Smarcel 1243130803Smarcel // Compute some values needed by the remaining shift algorithms 1244130803Smarcel unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; 1245130803Smarcel unsigned offset = shiftAmt / APINT_BITS_PER_WORD; 1246130803Smarcel 1247130803Smarcel // If we are shifting whole words, just move whole words 1248130803Smarcel if (wordShift == 0) { 1249130803Smarcel for (unsigned i = 0; i < getNumWords() - offset; ++i) 1250130803Smarcel val[i] = pVal[i+offset]; 1251130803Smarcel for (unsigned i = getNumWords()-offset; i < getNumWords(); i++) 1252130803Smarcel val[i] = 0; 1253130803Smarcel return APInt(val,BitWidth).clearUnusedBits(); 1254130803Smarcel } 1255130803Smarcel 1256130803Smarcel // Shift the low order words 1257130803Smarcel unsigned breakWord = getNumWords() - offset -1; 1258130803Smarcel for (unsigned i = 0; i < breakWord; ++i) 1259130803Smarcel val[i] = (pVal[i+offset] >> wordShift) | 1260130803Smarcel (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift)); 1261130803Smarcel // Shift the break word. 1262130803Smarcel val[breakWord] = pVal[breakWord+offset] >> wordShift; 1263130803Smarcel 1264130803Smarcel // Remaining words are 0 1265130803Smarcel for (unsigned i = breakWord+1; i < getNumWords(); ++i) 1266130803Smarcel val[i] = 0; 1267130803Smarcel return APInt(val, BitWidth).clearUnusedBits(); 1268130803Smarcel} 1269130803Smarcel 1270130803Smarcel/// Left-shift this APInt by shiftAmt. 1271130803Smarcel/// @brief Left-shift function. 1272130803SmarcelAPInt APInt::shl(const APInt &shiftAmt) const { 1273130803Smarcel // It's undefined behavior in C to shift by BitWidth or greater. 1274130803Smarcel return shl((unsigned)shiftAmt.getLimitedValue(BitWidth)); 1275130803Smarcel} 1276130803Smarcel 1277130803SmarcelAPInt APInt::shlSlowCase(unsigned shiftAmt) const { 1278130803Smarcel // If all the bits were shifted out, the result is 0. This avoids issues 1279130803Smarcel // with shifting by the size of the integer type, which produces undefined 1280130803Smarcel // results. We define these "undefined results" to always be 0. 1281130803Smarcel if (shiftAmt == BitWidth) 1282130803Smarcel return APInt(BitWidth, 0); 1283130803Smarcel 1284130803Smarcel // If none of the bits are shifted out, the result is *this. This avoids a 1285130803Smarcel // lshr by the words size in the loop below which can produce incorrect 1286130803Smarcel // results. It also avoids the expensive computation below for a common case. 1287130803Smarcel if (shiftAmt == 0) 1288130803Smarcel return *this; 1289130803Smarcel 1290130803Smarcel // Create some space for the result. 1291130803Smarcel uint64_t * val = new uint64_t[getNumWords()]; 1292130803Smarcel 1293130803Smarcel // If we are shifting less than a word, do it the easy way 1294130803Smarcel if (shiftAmt < APINT_BITS_PER_WORD) { 1295130803Smarcel uint64_t carry = 0; 1296130803Smarcel for (unsigned i = 0; i < getNumWords(); i++) { 1297130803Smarcel val[i] = pVal[i] << shiftAmt | carry; 1298130803Smarcel carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt); 1299130803Smarcel } 1300130803Smarcel return APInt(val, BitWidth).clearUnusedBits(); 1301130803Smarcel } 1302130803Smarcel 1303130803Smarcel // Compute some values needed by the remaining shift algorithms 1304130803Smarcel unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; 1305130803Smarcel unsigned offset = shiftAmt / APINT_BITS_PER_WORD; 1306130803Smarcel 1307130803Smarcel // If we are shifting whole words, just move whole words 1308130803Smarcel if (wordShift == 0) { 1309130803Smarcel for (unsigned i = 0; i < offset; i++) 1310130803Smarcel val[i] = 0; 1311130803Smarcel for (unsigned i = offset; i < getNumWords(); i++) 1312130803Smarcel val[i] = pVal[i-offset]; 1313130803Smarcel return APInt(val,BitWidth).clearUnusedBits(); 1314130803Smarcel } 1315130803Smarcel 1316130803Smarcel // Copy whole words from this to Result. 1317130803Smarcel unsigned i = getNumWords() - 1; 1318130803Smarcel for (; i > offset; --i) 1319130803Smarcel val[i] = pVal[i-offset] << wordShift | 1320130803Smarcel pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift); 1321130803Smarcel val[offset] = pVal[0] << wordShift; 1322130803Smarcel for (i = 0; i < offset; ++i) 1323130803Smarcel val[i] = 0; 1324130803Smarcel return APInt(val, BitWidth).clearUnusedBits(); 1325130803Smarcel} 1326130803Smarcel 1327130803SmarcelAPInt APInt::rotl(const APInt &rotateAmt) const { 1328130803Smarcel return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth)); 1329130803Smarcel} 1330130803Smarcel 1331130803SmarcelAPInt APInt::rotl(unsigned rotateAmt) const { 1332130803Smarcel if (rotateAmt == 0) 1333130803Smarcel return *this; 1334130803Smarcel // Don't get too fancy, just use existing shift/or facilities 1335130803Smarcel APInt hi(*this); 1336130803Smarcel APInt lo(*this); 1337130803Smarcel hi.shl(rotateAmt); 1338130803Smarcel lo.lshr(BitWidth - rotateAmt); 1339130803Smarcel return hi | lo; 1340130803Smarcel} 1341130803Smarcel 1342130803SmarcelAPInt APInt::rotr(const APInt &rotateAmt) const { 1343130803Smarcel return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth)); 1344130803Smarcel} 1345130803Smarcel 1346130803SmarcelAPInt APInt::rotr(unsigned rotateAmt) const { 1347130803Smarcel if (rotateAmt == 0) 1348130803Smarcel return *this; 1349130803Smarcel // Don't get too fancy, just use existing shift/or facilities 1350130803Smarcel APInt hi(*this); 1351130803Smarcel APInt lo(*this); 1352130803Smarcel lo.lshr(rotateAmt); 1353130803Smarcel hi.shl(BitWidth - rotateAmt); 1354130803Smarcel return hi | lo; 1355130803Smarcel} 1356130803Smarcel 1357130803Smarcel// Square Root - this method computes and returns the square root of "this". 1358130803Smarcel// Three mechanisms are used for computation. For small values (<= 5 bits), 1359130803Smarcel// a table lookup is done. This gets some performance for common cases. For 1360130803Smarcel// values using less than 52 bits, the value is converted to double and then 1361130803Smarcel// the libc sqrt function is called. The result is rounded and then converted 1362130803Smarcel// back to a uint64_t which is then used to construct the result. Finally, 1363130803Smarcel// the Babylonian method for computing square roots is used. 1364130803SmarcelAPInt APInt::sqrt() const { 1365130803Smarcel 1366130803Smarcel // Determine the magnitude of the value. 1367130803Smarcel unsigned magnitude = getActiveBits(); 1368130803Smarcel 1369130803Smarcel // Use a fast table for some small values. This also gets rid of some 1370130803Smarcel // rounding errors in libc sqrt for small values. 1371130803Smarcel if (magnitude <= 5) { 1372130803Smarcel static const uint8_t results[32] = { 1373130803Smarcel /* 0 */ 0, 1374130803Smarcel /* 1- 2 */ 1, 1, 1375130803Smarcel /* 3- 6 */ 2, 2, 2, 2, 1376130803Smarcel /* 7-12 */ 3, 3, 3, 3, 3, 3, 1377130803Smarcel /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4, 1378130803Smarcel /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1379130803Smarcel /* 31 */ 6 1380130803Smarcel }; 1381130803Smarcel return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]); 1382130803Smarcel } 1383130803Smarcel 1384130803Smarcel // If the magnitude of the value fits in less than 52 bits (the precision of 1385130803Smarcel // an IEEE double precision floating point value), then we can use the 1386130803Smarcel // libc sqrt function which will probably use a hardware sqrt computation. 1387130803Smarcel // This should be faster than the algorithm below. 1388130803Smarcel if (magnitude < 52) { 1389130803Smarcel#if HAVE_ROUND 1390130803Smarcel return APInt(BitWidth, 1391130803Smarcel uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0]))))); 1392130803Smarcel#else 1393130803Smarcel return APInt(BitWidth, 1394130803Smarcel uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5)); 1395130803Smarcel#endif 1396130803Smarcel } 1397130803Smarcel 1398130803Smarcel // Okay, all the short cuts are exhausted. We must compute it. The following 1399130803Smarcel // is a classical Babylonian method for computing the square root. This code 1400130803Smarcel // was adapted to APINt from a wikipedia article on such computations. 1401130803Smarcel // See http://www.wikipedia.org/ and go to the page named 1402130803Smarcel // Calculate_an_integer_square_root. 1403130803Smarcel unsigned nbits = BitWidth, i = 4; 1404130803Smarcel APInt testy(BitWidth, 16); 1405130803Smarcel APInt x_old(BitWidth, 1); 1406130803Smarcel APInt x_new(BitWidth, 0); 1407130803Smarcel APInt two(BitWidth, 2); 1408130803Smarcel 1409130803Smarcel // Select a good starting value using binary logarithms. 1410130803Smarcel for (;; i += 2, testy = testy.shl(2)) 1411130803Smarcel if (i >= nbits || this->ule(testy)) { 1412130803Smarcel x_old = x_old.shl(i / 2); 1413130803Smarcel break; 1414130803Smarcel } 1415130803Smarcel 1416130803Smarcel // Use the Babylonian method to arrive at the integer square root: 1417130803Smarcel for (;;) { 1418130803Smarcel x_new = (this->udiv(x_old) + x_old).udiv(two); 1419130803Smarcel if (x_old.ule(x_new)) 1420130803Smarcel break; 1421130803Smarcel x_old = x_new; 1422130803Smarcel } 1423130803Smarcel 1424130803Smarcel // Make sure we return the closest approximation 1425130803Smarcel // NOTE: The rounding calculation below is correct. It will produce an 1426130803Smarcel // off-by-one discrepancy with results from pari/gp. That discrepancy has been 1427130803Smarcel // determined to be a rounding issue with pari/gp as it begins to use a 1428130803Smarcel // floating point representation after 192 bits. There are no discrepancies 1429130803Smarcel // between this algorithm and pari/gp for bit widths < 192 bits. 1430130803Smarcel APInt square(x_old * x_old); 1431130803Smarcel APInt nextSquare((x_old + 1) * (x_old +1)); 1432130803Smarcel if (this->ult(square)) 1433130803Smarcel return x_old; 1434130803Smarcel else if (this->ule(nextSquare)) { 1435130803Smarcel APInt midpoint((nextSquare - square).udiv(two)); 1436130803Smarcel APInt offset(*this - square); 1437130803Smarcel if (offset.ult(midpoint)) 1438130803Smarcel return x_old; 1439130803Smarcel else 1440130803Smarcel return x_old + 1; 1441130803Smarcel } else 1442130803Smarcel llvm_unreachable("Error in APInt::sqrt computation"); 1443130803Smarcel return x_old + 1; 1444130803Smarcel} 1445130803Smarcel 1446130803Smarcel/// Computes the multiplicative inverse of this APInt for a given modulo. The 1447130803Smarcel/// iterative extended Euclidean algorithm is used to solve for this value, 1448130803Smarcel/// however we simplify it to speed up calculating only the inverse, and take 1449130803Smarcel/// advantage of div+rem calculations. We also use some tricks to avoid copying 1450130803Smarcel/// (potentially large) APInts around. 1451130803SmarcelAPInt APInt::multiplicativeInverse(const APInt& modulo) const { 1452130803Smarcel assert(ult(modulo) && "This APInt must be smaller than the modulo"); 1453130803Smarcel 1454130803Smarcel // Using the properties listed at the following web page (accessed 06/21/08): 1455130803Smarcel // http://www.numbertheory.org/php/euclid.html 1456130803Smarcel // (especially the properties numbered 3, 4 and 9) it can be proved that 1457130803Smarcel // BitWidth bits suffice for all the computations in the algorithm implemented 1458130803Smarcel // below. More precisely, this number of bits suffice if the multiplicative 1459130803Smarcel // inverse exists, but may not suffice for the general extended Euclidean 1460130803Smarcel // algorithm. 1461130803Smarcel 1462130803Smarcel APInt r[2] = { modulo, *this }; 1463130803Smarcel APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) }; 1464130803Smarcel APInt q(BitWidth, 0); 1465130803Smarcel 1466130803Smarcel unsigned i; 1467130803Smarcel for (i = 0; r[i^1] != 0; i ^= 1) { 1468130803Smarcel // An overview of the math without the confusing bit-flipping: 1469130803Smarcel // q = r[i-2] / r[i-1] 1470130803Smarcel // r[i] = r[i-2] % r[i-1] 1471130803Smarcel // t[i] = t[i-2] - t[i-1] * q 1472130803Smarcel udivrem(r[i], r[i^1], q, r[i]); 1473130803Smarcel t[i] -= t[i^1] * q; 1474130803Smarcel } 1475130803Smarcel 1476130803Smarcel // If this APInt and the modulo are not coprime, there is no multiplicative 1477130803Smarcel // inverse, so return 0. We check this by looking at the next-to-last 1478130803Smarcel // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean 1479130803Smarcel // algorithm. 1480130803Smarcel if (r[i] != 1) 1481130803Smarcel return APInt(BitWidth, 0); 1482130803Smarcel 1483130803Smarcel // The next-to-last t is the multiplicative inverse. However, we are 1484130803Smarcel // interested in a positive inverse. Calcuate a positive one from a negative 1485130803Smarcel // one if necessary. A simple addition of the modulo suffices because 1486130803Smarcel // abs(t[i]) is known to be less than *this/2 (see the link above). 1487130803Smarcel return t[i].isNegative() ? t[i] + modulo : t[i]; 1488130803Smarcel} 1489130803Smarcel 1490130803Smarcel/// Calculate the magic numbers required to implement a signed integer division 1491130803Smarcel/// by a constant as a sequence of multiplies, adds and shifts. Requires that 1492130803Smarcel/// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S. 1493130803Smarcel/// Warren, Jr., chapter 10. 1494130803SmarcelAPInt::ms APInt::magic() const { 1495130803Smarcel const APInt& d = *this; 1496130803Smarcel unsigned p; 1497130803Smarcel APInt ad, anc, delta, q1, r1, q2, r2, t; 1498130803Smarcel APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); 1499130803Smarcel struct ms mag; 1500130803Smarcel 1501130803Smarcel ad = d.abs(); 1502130803Smarcel t = signedMin + (d.lshr(d.getBitWidth() - 1)); 1503130803Smarcel anc = t - 1 - t.urem(ad); // absolute value of nc 1504130803Smarcel p = d.getBitWidth() - 1; // initialize p 1505130803Smarcel q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc) 1506130803Smarcel r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc)) 1507130803Smarcel q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d) 1508130803Smarcel r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d)) 1509130803Smarcel do { 1510130803Smarcel p = p + 1; 1511130803Smarcel q1 = q1<<1; // update q1 = 2p/abs(nc) 1512130803Smarcel r1 = r1<<1; // update r1 = rem(2p/abs(nc)) 1513130803Smarcel if (r1.uge(anc)) { // must be unsigned comparison 1514130803Smarcel q1 = q1 + 1; 1515130803Smarcel r1 = r1 - anc; 1516130803Smarcel } 1517130803Smarcel q2 = q2<<1; // update q2 = 2p/abs(d) 1518130803Smarcel r2 = r2<<1; // update r2 = rem(2p/abs(d)) 1519130803Smarcel if (r2.uge(ad)) { // must be unsigned comparison 1520130803Smarcel q2 = q2 + 1; 1521130803Smarcel r2 = r2 - ad; 1522130803Smarcel } 1523130803Smarcel delta = ad - r2; 1524130803Smarcel } while (q1.ult(delta) || (q1 == delta && r1 == 0)); 1525130803Smarcel 1526130803Smarcel mag.m = q2 + 1; 1527130803Smarcel if (d.isNegative()) mag.m = -mag.m; // resulting magic number 1528130803Smarcel mag.s = p - d.getBitWidth(); // resulting shift 1529130803Smarcel return mag; 1530130803Smarcel} 1531130803Smarcel 1532130803Smarcel/// Calculate the magic numbers required to implement an unsigned integer 1533130803Smarcel/// division by a constant as a sequence of multiplies, adds and shifts. 1534130803Smarcel/// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry 1535130803Smarcel/// S. Warren, Jr., chapter 10. 1536130803Smarcel/// LeadingZeros can be used to simplify the calculation if the upper bits 1537130803Smarcel/// of the divided value are known zero. 1538130803SmarcelAPInt::mu APInt::magicu(unsigned LeadingZeros) const { 1539130803Smarcel const APInt& d = *this; 1540130803Smarcel unsigned p; 1541130803Smarcel APInt nc, delta, q1, r1, q2, r2; 1542130803Smarcel struct mu magu; 1543130803Smarcel magu.a = 0; // initialize "add" indicator 1544130803Smarcel APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros); 1545130803Smarcel APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); 1546130803Smarcel APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth()); 1547130803Smarcel 1548130803Smarcel nc = allOnes - (-d).urem(d); 1549130803Smarcel p = d.getBitWidth() - 1; // initialize p 1550130803Smarcel q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc 1551130803Smarcel r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc) 1552130803Smarcel q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d 1553130803Smarcel r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d) 1554130803Smarcel do { 1555130803Smarcel p = p + 1; 1556130803Smarcel if (r1.uge(nc - r1)) { 1557130803Smarcel q1 = q1 + q1 + 1; // update q1 1558130803Smarcel r1 = r1 + r1 - nc; // update r1 1559130803Smarcel } 1560130803Smarcel else { 1561130803Smarcel q1 = q1+q1; // update q1 1562130803Smarcel r1 = r1+r1; // update r1 1563130803Smarcel } 1564130803Smarcel if ((r2 + 1).uge(d - r2)) { 1565130803Smarcel if (q2.uge(signedMax)) magu.a = 1; 1566130803Smarcel q2 = q2+q2 + 1; // update q2 1567130803Smarcel r2 = r2+r2 + 1 - d; // update r2 1568130803Smarcel } 1569130803Smarcel else { 1570130803Smarcel if (q2.uge(signedMin)) magu.a = 1; 1571130803Smarcel q2 = q2+q2; // update q2 1572130803Smarcel r2 = r2+r2 + 1; // update r2 1573130803Smarcel } 1574130803Smarcel delta = d - 1 - r2; 1575130803Smarcel } while (p < d.getBitWidth()*2 && 1576130803Smarcel (q1.ult(delta) || (q1 == delta && r1 == 0))); 1577130803Smarcel magu.m = q2 + 1; // resulting magic number 1578130803Smarcel magu.s = p - d.getBitWidth(); // resulting shift 1579130803Smarcel return magu; 1580130803Smarcel} 1581130803Smarcel 1582130803Smarcel/// Implementation of Knuth's Algorithm D (Division of nonnegative integers) 1583130803Smarcel/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The 1584130803Smarcel/// variables here have the same names as in the algorithm. Comments explain 1585130803Smarcel/// the algorithm and any deviation from it. 1586130803Smarcelstatic void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, 1587130803Smarcel unsigned m, unsigned n) { 1588130803Smarcel assert(u && "Must provide dividend"); 1589130803Smarcel assert(v && "Must provide divisor"); 1590130803Smarcel assert(q && "Must provide quotient"); 1591130803Smarcel assert(u != v && u != q && v != q && "Must us different memory"); 1592130803Smarcel assert(n>1 && "n must be > 1"); 1593130803Smarcel 1594130803Smarcel // Knuth uses the value b as the base of the number system. In our case b 1595130803Smarcel // is 2^31 so we just set it to -1u. 1596130803Smarcel uint64_t b = uint64_t(1) << 32; 1597130803Smarcel 1598130803Smarcel#if 0 1599130803Smarcel DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n'); 1600130803Smarcel DEBUG(dbgs() << "KnuthDiv: original:"); 1601130803Smarcel DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1602130803Smarcel DEBUG(dbgs() << " by"); 1603130803Smarcel DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]); 1604130803Smarcel DEBUG(dbgs() << '\n'); 1605130803Smarcel#endif 1606130803Smarcel // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of 1607130803Smarcel // u and v by d. Note that we have taken Knuth's advice here to use a power 1608130803Smarcel // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of 1609130803Smarcel // 2 allows us to shift instead of multiply and it is easy to determine the 1610130803Smarcel // shift amount from the leading zeros. We are basically normalizing the u 1611130803Smarcel // and v so that its high bits are shifted to the top of v's range without 1612130803Smarcel // overflow. Note that this can require an extra word in u so that u must 1613130803Smarcel // be of length m+n+1. 1614130803Smarcel unsigned shift = CountLeadingZeros_32(v[n-1]); 1615130803Smarcel unsigned v_carry = 0; 1616130803Smarcel unsigned u_carry = 0; 1617130803Smarcel if (shift) { 1618130803Smarcel for (unsigned i = 0; i < m+n; ++i) { 1619130803Smarcel unsigned u_tmp = u[i] >> (32 - shift); 1620130803Smarcel u[i] = (u[i] << shift) | u_carry; 1621130803Smarcel u_carry = u_tmp; 1622130803Smarcel } 1623130803Smarcel for (unsigned i = 0; i < n; ++i) { 1624130803Smarcel unsigned v_tmp = v[i] >> (32 - shift); 1625130803Smarcel v[i] = (v[i] << shift) | v_carry; 1626130803Smarcel v_carry = v_tmp; 1627130803Smarcel } 1628130803Smarcel } 1629130803Smarcel u[m+n] = u_carry; 1630130803Smarcel#if 0 1631130803Smarcel DEBUG(dbgs() << "KnuthDiv: normal:"); 1632130803Smarcel DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1633130803Smarcel DEBUG(dbgs() << " by"); 1634130803Smarcel DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]); 1635130803Smarcel DEBUG(dbgs() << '\n'); 1636130803Smarcel#endif 1637130803Smarcel 1638130803Smarcel // D2. [Initialize j.] Set j to m. This is the loop counter over the places. 1639130803Smarcel int j = m; 1640130803Smarcel do { 1641130803Smarcel DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n'); 1642130803Smarcel // D3. [Calculate q'.]. 1643130803Smarcel // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q') 1644130803Smarcel // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r') 1645130803Smarcel // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease 1646130803Smarcel // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test 1647130803Smarcel // on v[n-2] determines at high speed most of the cases in which the trial 1648130803Smarcel // value qp is one too large, and it eliminates all cases where qp is two 1649130803Smarcel // too large. 1650130803Smarcel uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]); 1651130803Smarcel DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n'); 1652130803Smarcel uint64_t qp = dividend / v[n-1]; 1653130803Smarcel uint64_t rp = dividend % v[n-1]; 1654130803Smarcel if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) { 1655130803Smarcel qp--; 1656130803Smarcel rp += v[n-1]; 1657130803Smarcel if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2])) 1658130803Smarcel qp--; 1659130803Smarcel } 1660130803Smarcel DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n'); 1661130803Smarcel 1662130803Smarcel // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with 1663130803Smarcel // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation 1664130803Smarcel // consists of a simple multiplication by a one-place number, combined with 1665130803Smarcel // a subtraction. 1666130803Smarcel bool isNeg = false; 1667130803Smarcel for (unsigned i = 0; i < n; ++i) { 1668130803Smarcel uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32); 1669130803Smarcel uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]); 1670130803Smarcel bool borrow = subtrahend > u_tmp; 1671130803Smarcel DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp 1672130803Smarcel << ", subtrahend == " << subtrahend 1673130803Smarcel << ", borrow = " << borrow << '\n'); 1674130803Smarcel 1675130803Smarcel uint64_t result = u_tmp - subtrahend; 1676130803Smarcel unsigned k = j + i; 1677130803Smarcel u[k++] = (unsigned)(result & (b-1)); // subtract low word 1678130803Smarcel u[k++] = (unsigned)(result >> 32); // subtract high word 1679130803Smarcel while (borrow && k <= m+n) { // deal with borrow to the left 1680130803Smarcel borrow = u[k] == 0; 1681130803Smarcel u[k]--; 1682130803Smarcel k++; 1683130803Smarcel } 1684130803Smarcel isNeg |= borrow; 1685130803Smarcel DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " << 1686130803Smarcel u[j+i+1] << '\n'); 1687130803Smarcel } 1688130803Smarcel DEBUG(dbgs() << "KnuthDiv: after subtraction:"); 1689130803Smarcel DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1690130803Smarcel DEBUG(dbgs() << '\n'); 1691130803Smarcel // The digits (u[j+n]...u[j]) should be kept positive; if the result of 1692130803Smarcel // this step is actually negative, (u[j+n]...u[j]) should be left as the 1693130803Smarcel // true value plus b**(n+1), namely as the b's complement of 1694130803Smarcel // the true value, and a "borrow" to the left should be remembered. 1695130803Smarcel // 1696130803Smarcel if (isNeg) { 1697130803Smarcel bool carry = true; // true because b's complement is "complement + 1" 1698130803Smarcel for (unsigned i = 0; i <= m+n; ++i) { 1699130803Smarcel u[i] = ~u[i] + carry; // b's complement 1700130803Smarcel carry = carry && u[i] == 0; 1701130803Smarcel } 1702130803Smarcel } 1703130803Smarcel DEBUG(dbgs() << "KnuthDiv: after complement:"); 1704130803Smarcel DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); 1705130803Smarcel DEBUG(dbgs() << '\n'); 1706130803Smarcel 1707130803Smarcel // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was 1708130803Smarcel // negative, go to step D6; otherwise go on to step D7. 1709130803Smarcel q[j] = (unsigned)qp; 1710130803Smarcel if (isNeg) { 1711130803Smarcel // D6. [Add back]. The probability that this step is necessary is very 1712130803Smarcel // small, on the order of only 2/b. Make sure that test data accounts for 1713130803Smarcel // this possibility. Decrease q[j] by 1 1714130803Smarcel q[j]--; 1715130803Smarcel // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]). 1716130803Smarcel // A carry will occur to the left of u[j+n], and it should be ignored 1717130803Smarcel // since it cancels with the borrow that occurred in D4. 1718130803Smarcel bool carry = false; 1719130803Smarcel for (unsigned i = 0; i < n; i++) { 1720130803Smarcel unsigned limit = std::min(u[j+i],v[i]); 1721130803Smarcel u[j+i] += v[i] + carry; 1722130803Smarcel carry = u[j+i] < limit || (carry && u[j+i] == limit); 1723130803Smarcel } 1724130803Smarcel u[j+n] += carry; 1725130803Smarcel } 1726130803Smarcel DEBUG(dbgs() << "KnuthDiv: after correction:"); 1727130803Smarcel DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]); 1728130803Smarcel DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n'); 1729130803Smarcel 1730130803Smarcel // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3. 1731130803Smarcel } while (--j >= 0); 1732130803Smarcel 1733130803Smarcel DEBUG(dbgs() << "KnuthDiv: quotient:"); 1734130803Smarcel DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]); 1735130803Smarcel DEBUG(dbgs() << '\n'); 1736130803Smarcel 1737130803Smarcel // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired 1738130803Smarcel // remainder may be obtained by dividing u[...] by d. If r is non-null we 1739130803Smarcel // compute the remainder (urem uses this). 1740130803Smarcel if (r) { 1741130803Smarcel // The value d is expressed by the "shift" value above since we avoided 1742130803Smarcel // multiplication by d by using a shift left. So, all we have to do is 1743130803Smarcel // shift right here. In order to mak 1744130803Smarcel if (shift) { 1745130803Smarcel unsigned carry = 0; 1746130803Smarcel DEBUG(dbgs() << "KnuthDiv: remainder:"); 1747130803Smarcel for (int i = n-1; i >= 0; i--) { 1748130803Smarcel r[i] = (u[i] >> shift) | carry; 1749130803Smarcel carry = u[i] << (32 - shift); 1750130803Smarcel DEBUG(dbgs() << " " << r[i]); 1751130803Smarcel } 1752130803Smarcel } else { 1753130803Smarcel for (int i = n-1; i >= 0; i--) { 1754130803Smarcel r[i] = u[i]; 1755130803Smarcel DEBUG(dbgs() << " " << r[i]); 1756130803Smarcel } 1757130803Smarcel } 1758130803Smarcel DEBUG(dbgs() << '\n'); 1759130803Smarcel } 1760130803Smarcel#if 0 1761130803Smarcel DEBUG(dbgs() << '\n'); 1762130803Smarcel#endif 1763130803Smarcel} 1764130803Smarcel 1765130803Smarcelvoid APInt::divide(const APInt LHS, unsigned lhsWords, 1766130803Smarcel const APInt &RHS, unsigned rhsWords, 1767130803Smarcel APInt *Quotient, APInt *Remainder) 1768130803Smarcel{ 1769130803Smarcel assert(lhsWords >= rhsWords && "Fractional result"); 1770130803Smarcel 1771130803Smarcel // First, compose the values into an array of 32-bit words instead of 1772130803Smarcel // 64-bit words. This is a necessity of both the "short division" algorithm 1773130803Smarcel // and the Knuth "classical algorithm" which requires there to be native 1774130803Smarcel // operations for +, -, and * on an m bit value with an m*2 bit result. We 1775130803Smarcel // can't use 64-bit operands here because we don't have native results of 1776130803Smarcel // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't 1777130803Smarcel // work on large-endian machines. 1778130803Smarcel uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT); 1779130803Smarcel unsigned n = rhsWords * 2; 1780130803Smarcel unsigned m = (lhsWords * 2) - n; 1781130803Smarcel 1782130803Smarcel // Allocate space for the temporary values we need either on the stack, if 1783130803Smarcel // it will fit, or on the heap if it won't. 1784130803Smarcel unsigned SPACE[128]; 1785130803Smarcel unsigned *U = 0; 1786130803Smarcel unsigned *V = 0; 1787130803Smarcel unsigned *Q = 0; 1788130803Smarcel unsigned *R = 0; 1789130803Smarcel if ((Remainder?4:3)*n+2*m+1 <= 128) { 1790130803Smarcel U = &SPACE[0]; 1791130803Smarcel V = &SPACE[m+n+1]; 1792130803Smarcel Q = &SPACE[(m+n+1) + n]; 1793130803Smarcel if (Remainder) 1794130803Smarcel R = &SPACE[(m+n+1) + n + (m+n)]; 1795130803Smarcel } else { 1796130803Smarcel U = new unsigned[m + n + 1]; 1797130803Smarcel V = new unsigned[n]; 1798130803Smarcel Q = new unsigned[m+n]; 1799130803Smarcel if (Remainder) 1800130803Smarcel R = new unsigned[n]; 1801130803Smarcel } 1802130803Smarcel 1803130803Smarcel // Initialize the dividend 1804130803Smarcel memset(U, 0, (m+n+1)*sizeof(unsigned)); 1805130803Smarcel for (unsigned i = 0; i < lhsWords; ++i) { 1806130803Smarcel uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]); 1807130803Smarcel U[i * 2] = (unsigned)(tmp & mask); 1808130803Smarcel U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT)); 1809130803Smarcel } 1810130803Smarcel U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm. 1811130803Smarcel 1812130803Smarcel // Initialize the divisor 1813130803Smarcel memset(V, 0, (n)*sizeof(unsigned)); 1814130803Smarcel for (unsigned i = 0; i < rhsWords; ++i) { 1815130803Smarcel uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]); 1816130803Smarcel V[i * 2] = (unsigned)(tmp & mask); 1817130803Smarcel V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT)); 1818130803Smarcel } 1819130803Smarcel 1820130803Smarcel // initialize the quotient and remainder 1821130803Smarcel memset(Q, 0, (m+n) * sizeof(unsigned)); 1822130803Smarcel if (Remainder) 1823130803Smarcel memset(R, 0, n * sizeof(unsigned)); 1824130803Smarcel 1825130803Smarcel // Now, adjust m and n for the Knuth division. n is the number of words in 1826130803Smarcel // the divisor. m is the number of words by which the dividend exceeds the 1827130803Smarcel // divisor (i.e. m+n is the length of the dividend). These sizes must not 1828130803Smarcel // contain any zero words or the Knuth algorithm fails. 1829130803Smarcel for (unsigned i = n; i > 0 && V[i-1] == 0; i--) { 1830130803Smarcel n--; 1831130803Smarcel m++; 1832130803Smarcel } 1833130803Smarcel for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--) 1834130803Smarcel m--; 1835130803Smarcel 1836130803Smarcel // If we're left with only a single word for the divisor, Knuth doesn't work 1837130803Smarcel // so we implement the short division algorithm here. This is much simpler 1838130803Smarcel // and faster because we are certain that we can divide a 64-bit quantity 1839130803Smarcel // by a 32-bit quantity at hardware speed and short division is simply a 1840130803Smarcel // series of such operations. This is just like doing short division but we 1841130803Smarcel // are using base 2^32 instead of base 10. 1842130803Smarcel assert(n != 0 && "Divide by zero?"); 1843130803Smarcel if (n == 1) { 1844130803Smarcel unsigned divisor = V[0]; 1845130803Smarcel unsigned remainder = 0; 1846130803Smarcel for (int i = m+n-1; i >= 0; i--) { 1847130803Smarcel uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i]; 1848130803Smarcel if (partial_dividend == 0) { 1849130803Smarcel Q[i] = 0; 1850130803Smarcel remainder = 0; 1851130803Smarcel } else if (partial_dividend < divisor) { 1852130803Smarcel Q[i] = 0; 1853130803Smarcel remainder = (unsigned)partial_dividend; 1854130803Smarcel } else if (partial_dividend == divisor) { 1855130803Smarcel Q[i] = 1; 1856130803Smarcel remainder = 0; 1857130803Smarcel } else { 1858130803Smarcel Q[i] = (unsigned)(partial_dividend / divisor); 1859130803Smarcel remainder = (unsigned)(partial_dividend - (Q[i] * divisor)); 1860130803Smarcel } 1861130803Smarcel } 1862130803Smarcel if (R) 1863130803Smarcel R[0] = remainder; 1864130803Smarcel } else { 1865130803Smarcel // Now we're ready to invoke the Knuth classical divide algorithm. In this 1866130803Smarcel // case n > 1. 1867130803Smarcel KnuthDiv(U, V, Q, R, m, n); 1868130803Smarcel } 1869130803Smarcel 1870130803Smarcel // If the caller wants the quotient 1871130803Smarcel if (Quotient) { 1872130803Smarcel // Set up the Quotient value's memory. 1873130803Smarcel if (Quotient->BitWidth != LHS.BitWidth) { 1874130803Smarcel if (Quotient->isSingleWord()) 1875130803Smarcel Quotient->VAL = 0; 1876130803Smarcel else 1877130803Smarcel delete [] Quotient->pVal; 1878130803Smarcel Quotient->BitWidth = LHS.BitWidth; 1879130803Smarcel if (!Quotient->isSingleWord()) 1880130803Smarcel Quotient->pVal = getClearedMemory(Quotient->getNumWords()); 1881130803Smarcel } else 1882130803Smarcel Quotient->clearAllBits(); 1883130803Smarcel 1884130803Smarcel // The quotient is in Q. Reconstitute the quotient into Quotient's low 1885130803Smarcel // order words. 1886130803Smarcel if (lhsWords == 1) { 1887130803Smarcel uint64_t tmp = 1888130803Smarcel uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2)); 1889130803Smarcel if (Quotient->isSingleWord()) 1890130803Smarcel Quotient->VAL = tmp; 1891130803Smarcel else 1892130803Smarcel Quotient->pVal[0] = tmp; 1893130803Smarcel } else { 1894130803Smarcel assert(!Quotient->isSingleWord() && "Quotient APInt not large enough"); 1895130803Smarcel for (unsigned i = 0; i < lhsWords; ++i) 1896130803Smarcel Quotient->pVal[i] = 1897130803Smarcel uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2)); 1898130803Smarcel } 1899130803Smarcel } 1900130803Smarcel 1901130803Smarcel // If the caller wants the remainder 1902130803Smarcel if (Remainder) { 1903130803Smarcel // Set up the Remainder value's memory. 1904130803Smarcel if (Remainder->BitWidth != RHS.BitWidth) { 1905130803Smarcel if (Remainder->isSingleWord()) 1906130803Smarcel Remainder->VAL = 0; 1907130803Smarcel else 1908130803Smarcel delete [] Remainder->pVal; 1909130803Smarcel Remainder->BitWidth = RHS.BitWidth; 1910130803Smarcel if (!Remainder->isSingleWord()) 1911130803Smarcel Remainder->pVal = getClearedMemory(Remainder->getNumWords()); 1912130803Smarcel } else 1913130803Smarcel Remainder->clearAllBits(); 1914130803Smarcel 1915130803Smarcel // The remainder is in R. Reconstitute the remainder into Remainder's low 1916130803Smarcel // order words. 1917130803Smarcel if (rhsWords == 1) { 1918130803Smarcel uint64_t tmp = 1919130803Smarcel uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2)); 1920130803Smarcel if (Remainder->isSingleWord()) 1921130803Smarcel Remainder->VAL = tmp; 1922130803Smarcel else 1923130803Smarcel Remainder->pVal[0] = tmp; 1924130803Smarcel } else { 1925130803Smarcel assert(!Remainder->isSingleWord() && "Remainder APInt not large enough"); 1926130803Smarcel for (unsigned i = 0; i < rhsWords; ++i) 1927130803Smarcel Remainder->pVal[i] = 1928130803Smarcel uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2)); 1929130803Smarcel } 1930130803Smarcel } 1931130803Smarcel 1932130803Smarcel // Clean up the memory we allocated. 1933130803Smarcel if (U != &SPACE[0]) { 1934130803Smarcel delete [] U; 1935130803Smarcel delete [] V; 1936130803Smarcel delete [] Q; 1937130803Smarcel delete [] R; 1938130803Smarcel } 1939130803Smarcel} 1940130803Smarcel 1941130803SmarcelAPInt APInt::udiv(const APInt& RHS) const { 1942130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 1943130803Smarcel 1944130803Smarcel // First, deal with the easy case 1945130803Smarcel if (isSingleWord()) { 1946130803Smarcel assert(RHS.VAL != 0 && "Divide by zero?"); 1947130803Smarcel return APInt(BitWidth, VAL / RHS.VAL); 1948130803Smarcel } 1949130803Smarcel 1950130803Smarcel // Get some facts about the LHS and RHS number of bits and words 1951130803Smarcel unsigned rhsBits = RHS.getActiveBits(); 1952130803Smarcel unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 1953130803Smarcel assert(rhsWords && "Divided by zero???"); 1954130803Smarcel unsigned lhsBits = this->getActiveBits(); 1955130803Smarcel unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); 1956130803Smarcel 1957130803Smarcel // Deal with some degenerate cases 1958130803Smarcel if (!lhsWords) 1959130803Smarcel // 0 / X ===> 0 1960130803Smarcel return APInt(BitWidth, 0); 1961130803Smarcel else if (lhsWords < rhsWords || this->ult(RHS)) { 1962130803Smarcel // X / Y ===> 0, iff X < Y 1963130803Smarcel return APInt(BitWidth, 0); 1964130803Smarcel } else if (*this == RHS) { 1965130803Smarcel // X / X ===> 1 1966130803Smarcel return APInt(BitWidth, 1); 1967130803Smarcel } else if (lhsWords == 1 && rhsWords == 1) { 1968130803Smarcel // All high words are zero, just use native divide 1969130803Smarcel return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]); 1970130803Smarcel } 1971130803Smarcel 1972130803Smarcel // We have to compute it the hard way. Invoke the Knuth divide algorithm. 1973130803Smarcel APInt Quotient(1,0); // to hold result. 1974130803Smarcel divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0); 1975130803Smarcel return Quotient; 1976130803Smarcel} 1977130803Smarcel 1978130803SmarcelAPInt APInt::urem(const APInt& RHS) const { 1979130803Smarcel assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); 1980130803Smarcel if (isSingleWord()) { 1981130803Smarcel assert(RHS.VAL != 0 && "Remainder by zero?"); 1982130803Smarcel return APInt(BitWidth, VAL % RHS.VAL); 1983130803Smarcel } 1984130803Smarcel 1985130803Smarcel // Get some facts about the LHS 1986130803Smarcel unsigned lhsBits = getActiveBits(); 1987130803Smarcel unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1); 1988130803Smarcel 1989130803Smarcel // Get some facts about the RHS 1990130803Smarcel unsigned rhsBits = RHS.getActiveBits(); 1991130803Smarcel unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 1992130803Smarcel assert(rhsWords && "Performing remainder operation by zero ???"); 1993130803Smarcel 1994130803Smarcel // Check the degenerate cases 1995130803Smarcel if (lhsWords == 0) { 1996130803Smarcel // 0 % Y ===> 0 1997130803Smarcel return APInt(BitWidth, 0); 1998130803Smarcel } else if (lhsWords < rhsWords || this->ult(RHS)) { 1999130803Smarcel // X % Y ===> X, iff X < Y 2000130803Smarcel return *this; 2001130803Smarcel } else if (*this == RHS) { 2002130803Smarcel // X % X == 0; 2003130803Smarcel return APInt(BitWidth, 0); 2004130803Smarcel } else if (lhsWords == 1) { 2005130803Smarcel // All high words are zero, just use native remainder 2006130803Smarcel return APInt(BitWidth, pVal[0] % RHS.pVal[0]); 2007130803Smarcel } 2008130803Smarcel 2009130803Smarcel // We have to compute it the hard way. Invoke the Knuth divide algorithm. 2010130803Smarcel APInt Remainder(1,0); 2011130803Smarcel divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder); 2012130803Smarcel return Remainder; 2013130803Smarcel} 2014130803Smarcel 2015130803Smarcelvoid APInt::udivrem(const APInt &LHS, const APInt &RHS, 2016130803Smarcel APInt &Quotient, APInt &Remainder) { 2017130803Smarcel // Get some size facts about the dividend and divisor 2018130803Smarcel unsigned lhsBits = LHS.getActiveBits(); 2019130803Smarcel unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); 2020130803Smarcel unsigned rhsBits = RHS.getActiveBits(); 2021130803Smarcel unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1); 2022130803Smarcel 2023130803Smarcel // Check the degenerate cases 2024130803Smarcel if (lhsWords == 0) { 2025130803Smarcel Quotient = 0; // 0 / Y ===> 0 2026130803Smarcel Remainder = 0; // 0 % Y ===> 0 2027130803Smarcel return; 2028130803Smarcel } 2029130803Smarcel 2030130803Smarcel if (lhsWords < rhsWords || LHS.ult(RHS)) { 2031130803Smarcel Remainder = LHS; // X % Y ===> X, iff X < Y 2032130803Smarcel Quotient = 0; // X / Y ===> 0, iff X < Y 2033130803Smarcel return; 2034130803Smarcel } 2035130803Smarcel 2036130803Smarcel if (LHS == RHS) { 2037130803Smarcel Quotient = 1; // X / X ===> 1 2038130803Smarcel Remainder = 0; // X % X ===> 0; 2039130803Smarcel return; 2040130803Smarcel } 2041130803Smarcel 2042130803Smarcel if (lhsWords == 1 && rhsWords == 1) { 2043130803Smarcel // There is only one word to consider so use the native versions. 2044130803Smarcel uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0]; 2045130803Smarcel uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 2046130803Smarcel Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue); 2047130803Smarcel Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue); 2048130803Smarcel return; 2049130803Smarcel } 2050130803Smarcel 2051130803Smarcel // Okay, lets do it the long way 2052130803Smarcel divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder); 2053130803Smarcel} 2054130803Smarcel 2055130803SmarcelAPInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const { 2056130803Smarcel APInt Res = *this+RHS; 2057130803Smarcel Overflow = isNonNegative() == RHS.isNonNegative() && 2058130803Smarcel Res.isNonNegative() != isNonNegative(); 2059130803Smarcel return Res; 2060130803Smarcel} 2061130803Smarcel 2062130803SmarcelAPInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const { 2063130803Smarcel APInt Res = *this+RHS; 2064130803Smarcel Overflow = Res.ult(RHS); 2065130803Smarcel return Res; 2066130803Smarcel} 2067130803Smarcel 2068130803SmarcelAPInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const { 2069130803Smarcel APInt Res = *this - RHS; 2070130803Smarcel Overflow = isNonNegative() != RHS.isNonNegative() && 2071130803Smarcel Res.isNonNegative() != isNonNegative(); 2072130803Smarcel return Res; 2073130803Smarcel} 2074130803Smarcel 2075130803SmarcelAPInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const { 2076130803Smarcel APInt Res = *this-RHS; 2077130803Smarcel Overflow = Res.ugt(*this); 2078130803Smarcel return Res; 2079130803Smarcel} 2080130803Smarcel 2081130803SmarcelAPInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const { 2082130803Smarcel // MININT/-1 --> overflow. 2083130803Smarcel Overflow = isMinSignedValue() && RHS.isAllOnesValue(); 2084130803Smarcel return sdiv(RHS); 2085130803Smarcel} 2086130803Smarcel 2087130803SmarcelAPInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const { 2088130803Smarcel APInt Res = *this * RHS; 2089130803Smarcel 2090130803Smarcel if (*this != 0 && RHS != 0) 2091130803Smarcel Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS; 2092130803Smarcel else 2093130803Smarcel Overflow = false; 2094130803Smarcel return Res; 2095130803Smarcel} 2096130803Smarcel 2097130803SmarcelAPInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const { 2098130803Smarcel APInt Res = *this * RHS; 2099130803Smarcel 2100130803Smarcel if (*this != 0 && RHS != 0) 2101130803Smarcel Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS; 2102130803Smarcel else 2103130803Smarcel Overflow = false; 2104130803Smarcel return Res; 2105130803Smarcel} 2106130803Smarcel 2107130803SmarcelAPInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const { 2108130803Smarcel Overflow = ShAmt >= getBitWidth(); 2109130803Smarcel if (Overflow) 2110130803Smarcel ShAmt = getBitWidth()-1; 2111130803Smarcel 2112130803Smarcel if (isNonNegative()) // Don't allow sign change. 2113130803Smarcel Overflow = ShAmt >= countLeadingZeros(); 2114130803Smarcel else 2115130803Smarcel Overflow = ShAmt >= countLeadingOnes(); 2116130803Smarcel 2117130803Smarcel return *this << ShAmt; 2118130803Smarcel} 2119130803Smarcel 2120130803Smarcel 2121130803Smarcel 2122130803Smarcel 2123130803Smarcelvoid APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) { 2124130803Smarcel // Check our assumptions here 2125130803Smarcel assert(!str.empty() && "Invalid string length"); 2126130803Smarcel assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 || 2127130803Smarcel radix == 36) && 2128130803Smarcel "Radix should be 2, 8, 10, 16, or 36!"); 2129130803Smarcel 2130130803Smarcel StringRef::iterator p = str.begin(); 2131130803Smarcel size_t slen = str.size(); 2132130803Smarcel bool isNeg = *p == '-'; 2133130803Smarcel if (*p == '-' || *p == '+') { 2134130803Smarcel p++; 2135130803Smarcel slen--; 2136130803Smarcel assert(slen && "String is only a sign, needs a value."); 2137130803Smarcel } 2138130803Smarcel assert((slen <= numbits || radix != 2) && "Insufficient bit width"); 2139130803Smarcel assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width"); 2140130803Smarcel assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width"); 2141130803Smarcel assert((((slen-1)*64)/22 <= numbits || radix != 10) && 2142130803Smarcel "Insufficient bit width"); 2143130803Smarcel 2144130803Smarcel // Allocate memory 2145130803Smarcel if (!isSingleWord()) 2146130803Smarcel pVal = getClearedMemory(getNumWords()); 2147130803Smarcel 2148130803Smarcel // Figure out if we can shift instead of multiply 2149130803Smarcel unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0); 2150130803Smarcel 2151130803Smarcel // Set up an APInt for the digit to add outside the loop so we don't 2152130803Smarcel // constantly construct/destruct it. 2153130803Smarcel APInt apdigit(getBitWidth(), 0); 2154130803Smarcel APInt apradix(getBitWidth(), radix); 2155130803Smarcel 2156130803Smarcel // Enter digit traversal loop 2157130803Smarcel for (StringRef::iterator e = str.end(); p != e; ++p) { 2158130803Smarcel unsigned digit = getDigit(*p, radix); 2159130803Smarcel assert(digit < radix && "Invalid character in digit string"); 2160130803Smarcel 2161130803Smarcel // Shift or multiply the value by the radix 2162130803Smarcel if (slen > 1) { 2163130803Smarcel if (shift) 2164130803Smarcel *this <<= shift; 2165130803Smarcel else 2166130803Smarcel *this *= apradix; 2167130803Smarcel } 2168130803Smarcel 2169130803Smarcel // Add in the digit we just interpreted 2170130803Smarcel if (apdigit.isSingleWord()) 2171130803Smarcel apdigit.VAL = digit; 2172130803Smarcel else 2173130803Smarcel apdigit.pVal[0] = digit; 2174130803Smarcel *this += apdigit; 2175130803Smarcel } 2176130803Smarcel // If its negative, put it in two's complement form 2177130803Smarcel if (isNeg) { 2178130803Smarcel (*this)--; 2179130803Smarcel this->flipAllBits(); 2180130803Smarcel } 2181130803Smarcel} 2182130803Smarcel 2183130803Smarcelvoid APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix, 2184130803Smarcel bool Signed, bool formatAsCLiteral) const { 2185130803Smarcel assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 || 2186130803Smarcel Radix == 36) && 2187130803Smarcel "Radix should be 2, 8, 10, or 16!"); 2188130803Smarcel 2189130803Smarcel const char *Prefix = ""; 2190130803Smarcel if (formatAsCLiteral) { 2191130803Smarcel switch (Radix) { 2192130803Smarcel case 2: 2193130803Smarcel // Binary literals are a non-standard extension added in gcc 4.3: 2194130803Smarcel // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html 2195130803Smarcel Prefix = "0b"; 2196130803Smarcel break; 2197130803Smarcel case 8: 2198130803Smarcel Prefix = "0"; 2199130803Smarcel break; 2200130803Smarcel case 16: 2201130803Smarcel Prefix = "0x"; 2202130803Smarcel break; 2203130803Smarcel } 2204130803Smarcel } 2205130803Smarcel 2206130803Smarcel // First, check for a zero value and just short circuit the logic below. 2207130803Smarcel if (*this == 0) { 2208130803Smarcel while (*Prefix) { 2209130803Smarcel Str.push_back(*Prefix); 2210130803Smarcel ++Prefix; 2211130803Smarcel }; 2212130803Smarcel Str.push_back('0'); 2213130803Smarcel return; 2214130803Smarcel } 2215130803Smarcel 2216130803Smarcel static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 2217130803Smarcel 2218130803Smarcel if (isSingleWord()) { 2219130803Smarcel char Buffer[65]; 2220130803Smarcel char *BufPtr = Buffer+65; 2221130803Smarcel 2222130803Smarcel uint64_t N; 2223130803Smarcel if (!Signed) { 2224130803Smarcel N = getZExtValue(); 2225130803Smarcel } else { 2226130803Smarcel int64_t I = getSExtValue(); 2227130803Smarcel if (I >= 0) { 2228130803Smarcel N = I; 2229130803Smarcel } else { 2230130803Smarcel Str.push_back('-'); 2231130803Smarcel N = -(uint64_t)I; 2232130803Smarcel } 2233130803Smarcel } 2234130803Smarcel 2235130803Smarcel while (*Prefix) { 2236130803Smarcel Str.push_back(*Prefix); 2237130803Smarcel ++Prefix; 2238130803Smarcel }; 2239130803Smarcel 2240130803Smarcel while (N) { 2241130803Smarcel *--BufPtr = Digits[N % Radix]; 2242130803Smarcel N /= Radix; 2243130803Smarcel } 2244130803Smarcel Str.append(BufPtr, Buffer+65); 2245130803Smarcel return; 2246130803Smarcel } 2247130803Smarcel 2248130803Smarcel APInt Tmp(*this); 2249130803Smarcel 2250130803Smarcel if (Signed && isNegative()) { 2251130803Smarcel // They want to print the signed version and it is a negative value 2252130803Smarcel // Flip the bits and add one to turn it into the equivalent positive 2253130803Smarcel // value and put a '-' in the result. 2254130803Smarcel Tmp.flipAllBits(); 2255130803Smarcel Tmp++; 2256130803Smarcel Str.push_back('-'); 2257130803Smarcel } 2258130803Smarcel 2259130803Smarcel while (*Prefix) { 2260130803Smarcel Str.push_back(*Prefix); 2261130803Smarcel ++Prefix; 2262130803Smarcel }; 2263130803Smarcel 2264130803Smarcel // We insert the digits backward, then reverse them to get the right order. 2265130803Smarcel unsigned StartDig = Str.size(); 2266130803Smarcel 2267130803Smarcel // For the 2, 8 and 16 bit cases, we can just shift instead of divide 2268130803Smarcel // because the number of bits per digit (1, 3 and 4 respectively) divides 2269130803Smarcel // equaly. We just shift until the value is zero. 2270130803Smarcel if (Radix == 2 || Radix == 8 || Radix == 16) { 2271130803Smarcel // Just shift tmp right for each digit width until it becomes zero 2272130803Smarcel unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1)); 2273130803Smarcel unsigned MaskAmt = Radix - 1; 2274130803Smarcel 2275130803Smarcel while (Tmp != 0) { 2276130803Smarcel unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt; 2277130803Smarcel Str.push_back(Digits[Digit]); 2278130803Smarcel Tmp = Tmp.lshr(ShiftAmt); 2279130803Smarcel } 2280130803Smarcel } else { 2281130803Smarcel APInt divisor(Radix == 10? 4 : 8, Radix); 2282130803Smarcel while (Tmp != 0) { 2283130803Smarcel APInt APdigit(1, 0); 2284130803Smarcel APInt tmp2(Tmp.getBitWidth(), 0); 2285130803Smarcel divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2, 2286130803Smarcel &APdigit); 2287130803Smarcel unsigned Digit = (unsigned)APdigit.getZExtValue(); 2288130803Smarcel assert(Digit < Radix && "divide failed"); 2289130803Smarcel Str.push_back(Digits[Digit]); 2290130803Smarcel Tmp = tmp2; 2291130803Smarcel } 2292130803Smarcel } 2293130803Smarcel 2294130803Smarcel // Reverse the digits before returning. 2295130803Smarcel std::reverse(Str.begin()+StartDig, Str.end()); 2296130803Smarcel} 2297130803Smarcel 2298130803Smarcel/// toString - This returns the APInt as a std::string. Note that this is an 2299130803Smarcel/// inefficient method. It is better to pass in a SmallVector/SmallString 2300130803Smarcel/// to the methods above. 2301130803Smarcelstd::string APInt::toString(unsigned Radix = 10, bool Signed = true) const { 2302130803Smarcel SmallString<40> S; 2303130803Smarcel toString(S, Radix, Signed, /* formatAsCLiteral = */false); 2304130803Smarcel return S.str(); 2305130803Smarcel} 2306130803Smarcel 2307130803Smarcel 2308130803Smarcelvoid APInt::dump() const { 2309130803Smarcel SmallString<40> S, U; 2310130803Smarcel this->toStringUnsigned(U); 2311130803Smarcel this->toStringSigned(S); 2312130803Smarcel dbgs() << "APInt(" << BitWidth << "b, " 2313130803Smarcel << U.str() << "u " << S.str() << "s)"; 2314130803Smarcel} 2315130803Smarcel 2316130803Smarcelvoid APInt::print(raw_ostream &OS, bool isSigned) const { 2317130803Smarcel SmallString<40> S; 2318130803Smarcel this->toString(S, 10, isSigned, /* formatAsCLiteral = */false); 2319130803Smarcel OS << S.str(); 2320130803Smarcel} 2321130803Smarcel 2322130803Smarcel// This implements a variety of operations on a representation of 2323130803Smarcel// arbitrary precision, two's-complement, bignum integer values. 2324130803Smarcel 2325130803Smarcel// Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe 2326130803Smarcel// and unrestricting assumption. 2327130803Smarcel#define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1] 2328130803SmarcelCOMPILE_TIME_ASSERT(integerPartWidth % 2 == 0); 2329130803Smarcel 2330130803Smarcel/* Some handy functions local to this file. */ 2331130803Smarcelnamespace { 2332130803Smarcel 2333130803Smarcel /* Returns the integer part with the least significant BITS set. 2334130803Smarcel BITS cannot be zero. */ 2335130803Smarcel static inline integerPart 2336130803Smarcel lowBitMask(unsigned int bits) 2337130803Smarcel { 2338130803Smarcel assert(bits != 0 && bits <= integerPartWidth); 2339130803Smarcel 2340130803Smarcel return ~(integerPart) 0 >> (integerPartWidth - bits); 2341130803Smarcel } 2342130803Smarcel 2343130803Smarcel /* Returns the value of the lower half of PART. */ 2344130803Smarcel static inline integerPart 2345130803Smarcel lowHalf(integerPart part) 2346130803Smarcel { 2347130803Smarcel return part & lowBitMask(integerPartWidth / 2); 2348130803Smarcel } 2349130803Smarcel 2350130803Smarcel /* Returns the value of the upper half of PART. */ 2351130803Smarcel static inline integerPart 2352130803Smarcel highHalf(integerPart part) 2353130803Smarcel { 2354130803Smarcel return part >> (integerPartWidth / 2); 2355130803Smarcel } 2356130803Smarcel 2357130803Smarcel /* Returns the bit number of the most significant set bit of a part. 2358130803Smarcel If the input number has no bits set -1U is returned. */ 2359130803Smarcel static unsigned int 2360130803Smarcel partMSB(integerPart value) 2361130803Smarcel { 2362130803Smarcel unsigned int n, msb; 2363130803Smarcel 2364130803Smarcel if (value == 0) 2365130803Smarcel return -1U; 2366130803Smarcel 2367130803Smarcel n = integerPartWidth / 2; 2368130803Smarcel 2369130803Smarcel msb = 0; 2370130803Smarcel do { 2371130803Smarcel if (value >> n) { 2372130803Smarcel value >>= n; 2373130803Smarcel msb += n; 2374130803Smarcel } 2375130803Smarcel 2376130803Smarcel n >>= 1; 2377130803Smarcel } while (n); 2378130803Smarcel 2379130803Smarcel return msb; 2380130803Smarcel } 2381130803Smarcel 2382130803Smarcel /* Returns the bit number of the least significant set bit of a 2383130803Smarcel part. If the input number has no bits set -1U is returned. */ 2384130803Smarcel static unsigned int 2385130803Smarcel partLSB(integerPart value) 2386130803Smarcel { 2387130803Smarcel unsigned int n, lsb; 2388130803Smarcel 2389130803Smarcel if (value == 0) 2390130803Smarcel return -1U; 2391130803Smarcel 2392130803Smarcel lsb = integerPartWidth - 1; 2393130803Smarcel n = integerPartWidth / 2; 2394130803Smarcel 2395130803Smarcel do { 2396130803Smarcel if (value << n) { 2397130803Smarcel value <<= n; 2398130803Smarcel lsb -= n; 2399130803Smarcel } 2400130803Smarcel 2401130803Smarcel n >>= 1; 2402130803Smarcel } while (n); 2403130803Smarcel 2404130803Smarcel return lsb; 2405130803Smarcel } 2406130803Smarcel} 2407130803Smarcel 2408130803Smarcel/* Sets the least significant part of a bignum to the input value, and 2409130803Smarcel zeroes out higher parts. */ 2410130803Smarcelvoid 2411130803SmarcelAPInt::tcSet(integerPart *dst, integerPart part, unsigned int parts) 2412130803Smarcel{ 2413130803Smarcel unsigned int i; 2414130803Smarcel 2415130803Smarcel assert(parts > 0); 2416130803Smarcel 2417130803Smarcel dst[0] = part; 2418130803Smarcel for (i = 1; i < parts; i++) 2419130803Smarcel dst[i] = 0; 2420130803Smarcel} 2421130803Smarcel 2422130803Smarcel/* Assign one bignum to another. */ 2423130803Smarcelvoid 2424130803SmarcelAPInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts) 2425130803Smarcel{ 2426130803Smarcel unsigned int i; 2427130803Smarcel 2428130803Smarcel for (i = 0; i < parts; i++) 2429130803Smarcel dst[i] = src[i]; 2430130803Smarcel} 2431130803Smarcel 2432130803Smarcel/* Returns true if a bignum is zero, false otherwise. */ 2433130803Smarcelbool 2434130803SmarcelAPInt::tcIsZero(const integerPart *src, unsigned int parts) 2435130803Smarcel{ 2436130803Smarcel unsigned int i; 2437130803Smarcel 2438130803Smarcel for (i = 0; i < parts; i++) 2439130803Smarcel if (src[i]) 2440130803Smarcel return false; 2441130803Smarcel 2442130803Smarcel return true; 2443130803Smarcel} 2444130803Smarcel 2445130803Smarcel/* Extract the given bit of a bignum; returns 0 or 1. */ 2446130803Smarcelint 2447130803SmarcelAPInt::tcExtractBit(const integerPart *parts, unsigned int bit) 2448130803Smarcel{ 2449130803Smarcel return (parts[bit / integerPartWidth] & 2450130803Smarcel ((integerPart) 1 << bit % integerPartWidth)) != 0; 2451130803Smarcel} 2452130803Smarcel 2453130803Smarcel/* Set the given bit of a bignum. */ 2454130803Smarcelvoid 2455130803SmarcelAPInt::tcSetBit(integerPart *parts, unsigned int bit) 2456130803Smarcel{ 2457130803Smarcel parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth); 2458130803Smarcel} 2459130803Smarcel 2460130803Smarcel/* Clears the given bit of a bignum. */ 2461130803Smarcelvoid 2462130803SmarcelAPInt::tcClearBit(integerPart *parts, unsigned int bit) 2463130803Smarcel{ 2464130803Smarcel parts[bit / integerPartWidth] &= 2465130803Smarcel ~((integerPart) 1 << (bit % integerPartWidth)); 2466130803Smarcel} 2467130803Smarcel 2468130803Smarcel/* Returns the bit number of the least significant set bit of a 2469130803Smarcel number. If the input number has no bits set -1U is returned. */ 2470130803Smarcelunsigned int 2471130803SmarcelAPInt::tcLSB(const integerPart *parts, unsigned int n) 2472130803Smarcel{ 2473130803Smarcel unsigned int i, lsb; 2474130803Smarcel 2475130803Smarcel for (i = 0; i < n; i++) { 2476130803Smarcel if (parts[i] != 0) { 2477130803Smarcel lsb = partLSB(parts[i]); 2478130803Smarcel 2479130803Smarcel return lsb + i * integerPartWidth; 2480130803Smarcel } 2481130803Smarcel } 2482130803Smarcel 2483130803Smarcel return -1U; 2484130803Smarcel} 2485130803Smarcel 2486130803Smarcel/* Returns the bit number of the most significant set bit of a number. 2487130803Smarcel If the input number has no bits set -1U is returned. */ 2488130803Smarcelunsigned int 2489130803SmarcelAPInt::tcMSB(const integerPart *parts, unsigned int n) 2490130803Smarcel{ 2491130803Smarcel unsigned int msb; 2492130803Smarcel 2493130803Smarcel do { 2494130803Smarcel --n; 2495130803Smarcel 2496130803Smarcel if (parts[n] != 0) { 2497130803Smarcel msb = partMSB(parts[n]); 2498130803Smarcel 2499130803Smarcel return msb + n * integerPartWidth; 2500130803Smarcel } 2501130803Smarcel } while (n); 2502130803Smarcel 2503130803Smarcel return -1U; 2504130803Smarcel} 2505130803Smarcel 2506130803Smarcel/* Copy the bit vector of width srcBITS from SRC, starting at bit 2507130803Smarcel srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes 2508130803Smarcel the least significant bit of DST. All high bits above srcBITS in 2509130803Smarcel DST are zero-filled. */ 2510130803Smarcelvoid 2511130803SmarcelAPInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src, 2512130803Smarcel unsigned int srcBits, unsigned int srcLSB) 2513130803Smarcel{ 2514130803Smarcel unsigned int firstSrcPart, dstParts, shift, n; 2515130803Smarcel 2516130803Smarcel dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth; 2517130803Smarcel assert(dstParts <= dstCount); 2518130803Smarcel 2519130803Smarcel firstSrcPart = srcLSB / integerPartWidth; 2520130803Smarcel tcAssign (dst, src + firstSrcPart, dstParts); 2521130803Smarcel 2522130803Smarcel shift = srcLSB % integerPartWidth; 2523130803Smarcel tcShiftRight (dst, dstParts, shift); 2524130803Smarcel 2525130803Smarcel /* We now have (dstParts * integerPartWidth - shift) bits from SRC 2526130803Smarcel in DST. If this is less that srcBits, append the rest, else 2527130803Smarcel clear the high bits. */ 2528130803Smarcel n = dstParts * integerPartWidth - shift; 2529130803Smarcel if (n < srcBits) { 2530130803Smarcel integerPart mask = lowBitMask (srcBits - n); 2531130803Smarcel dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask) 2532130803Smarcel << n % integerPartWidth); 2533130803Smarcel } else if (n > srcBits) { 2534130803Smarcel if (srcBits % integerPartWidth) 2535130803Smarcel dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth); 2536130803Smarcel } 2537130803Smarcel 2538130803Smarcel /* Clear high parts. */ 2539130803Smarcel while (dstParts < dstCount) 2540130803Smarcel dst[dstParts++] = 0; 2541130803Smarcel} 2542130803Smarcel 2543130803Smarcel/* DST += RHS + C where C is zero or one. Returns the carry flag. */ 2544130803SmarcelintegerPart 2545130803SmarcelAPInt::tcAdd(integerPart *dst, const integerPart *rhs, 2546130803Smarcel integerPart c, unsigned int parts) 2547130803Smarcel{ 2548130803Smarcel unsigned int i; 2549130803Smarcel 2550130803Smarcel assert(c <= 1); 2551130803Smarcel 2552130803Smarcel for (i = 0; i < parts; i++) { 2553130803Smarcel integerPart l; 2554130803Smarcel 2555130803Smarcel l = dst[i]; 2556130803Smarcel if (c) { 2557130803Smarcel dst[i] += rhs[i] + 1; 2558130803Smarcel c = (dst[i] <= l); 2559130803Smarcel } else { 2560130803Smarcel dst[i] += rhs[i]; 2561130803Smarcel c = (dst[i] < l); 2562130803Smarcel } 2563130803Smarcel } 2564130803Smarcel 2565130803Smarcel return c; 2566130803Smarcel} 2567130803Smarcel 2568130803Smarcel/* DST -= RHS + C where C is zero or one. Returns the carry flag. */ 2569130803SmarcelintegerPart 2570130803SmarcelAPInt::tcSubtract(integerPart *dst, const integerPart *rhs, 2571130803Smarcel integerPart c, unsigned int parts) 2572130803Smarcel{ 2573130803Smarcel unsigned int i; 2574130803Smarcel 2575130803Smarcel assert(c <= 1); 2576130803Smarcel 2577130803Smarcel for (i = 0; i < parts; i++) { 2578130803Smarcel integerPart l; 2579130803Smarcel 2580130803Smarcel l = dst[i]; 2581130803Smarcel if (c) { 2582130803Smarcel dst[i] -= rhs[i] + 1; 2583130803Smarcel c = (dst[i] >= l); 2584130803Smarcel } else { 2585130803Smarcel dst[i] -= rhs[i]; 2586130803Smarcel c = (dst[i] > l); 2587130803Smarcel } 2588130803Smarcel } 2589130803Smarcel 2590130803Smarcel return c; 2591130803Smarcel} 2592130803Smarcel 2593130803Smarcel/* Negate a bignum in-place. */ 2594130803Smarcelvoid 2595130803SmarcelAPInt::tcNegate(integerPart *dst, unsigned int parts) 2596130803Smarcel{ 2597130803Smarcel tcComplement(dst, parts); 2598130803Smarcel tcIncrement(dst, parts); 2599130803Smarcel} 2600130803Smarcel 2601130803Smarcel/* DST += SRC * MULTIPLIER + CARRY if add is true 2602130803Smarcel DST = SRC * MULTIPLIER + CARRY if add is false 2603130803Smarcel 2604130803Smarcel Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC 2605130803Smarcel they must start at the same point, i.e. DST == SRC. 2606130803Smarcel 2607130803Smarcel If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is 2608130803Smarcel returned. Otherwise DST is filled with the least significant 2609130803Smarcel DSTPARTS parts of the result, and if all of the omitted higher 2610130803Smarcel parts were zero return zero, otherwise overflow occurred and 2611130803Smarcel return one. */ 2612130803Smarcelint 2613130803SmarcelAPInt::tcMultiplyPart(integerPart *dst, const integerPart *src, 2614130803Smarcel integerPart multiplier, integerPart carry, 2615130803Smarcel unsigned int srcParts, unsigned int dstParts, 2616130803Smarcel bool add) 2617130803Smarcel{ 2618130803Smarcel unsigned int i, n; 2619130803Smarcel 2620130803Smarcel /* Otherwise our writes of DST kill our later reads of SRC. */ 2621130803Smarcel assert(dst <= src || dst >= src + srcParts); 2622130803Smarcel assert(dstParts <= srcParts + 1); 2623130803Smarcel 2624130803Smarcel /* N loops; minimum of dstParts and srcParts. */ 2625130803Smarcel n = dstParts < srcParts ? dstParts: srcParts; 2626130803Smarcel 2627130803Smarcel for (i = 0; i < n; i++) { 2628130803Smarcel integerPart low, mid, high, srcPart; 2629130803Smarcel 2630130803Smarcel /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY. 2631130803Smarcel 2632130803Smarcel This cannot overflow, because 2633130803Smarcel 2634130803Smarcel (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1) 2635130803Smarcel 2636130803Smarcel which is less than n^2. */ 2637130803Smarcel 2638130803Smarcel srcPart = src[i]; 2639130803Smarcel 2640130803Smarcel if (multiplier == 0 || srcPart == 0) { 2641130803Smarcel low = carry; 2642130803Smarcel high = 0; 2643130803Smarcel } else { 2644130803Smarcel low = lowHalf(srcPart) * lowHalf(multiplier); 2645130803Smarcel high = highHalf(srcPart) * highHalf(multiplier); 2646130803Smarcel 2647130803Smarcel mid = lowHalf(srcPart) * highHalf(multiplier); 2648130803Smarcel high += highHalf(mid); 2649130803Smarcel mid <<= integerPartWidth / 2; 2650130803Smarcel if (low + mid < low) 2651130803Smarcel high++; 2652130803Smarcel low += mid; 2653130803Smarcel 2654130803Smarcel mid = highHalf(srcPart) * lowHalf(multiplier); 2655130803Smarcel high += highHalf(mid); 2656130803Smarcel mid <<= integerPartWidth / 2; 2657130803Smarcel if (low + mid < low) 2658130803Smarcel high++; 2659130803Smarcel low += mid; 2660130803Smarcel 2661130803Smarcel /* Now add carry. */ 2662130803Smarcel if (low + carry < low) 2663130803Smarcel high++; 2664130803Smarcel low += carry; 2665130803Smarcel } 2666130803Smarcel 2667130803Smarcel if (add) { 2668130803Smarcel /* And now DST[i], and store the new low part there. */ 2669130803Smarcel if (low + dst[i] < low) 2670130803Smarcel high++; 2671130803Smarcel dst[i] += low; 2672130803Smarcel } else 2673130803Smarcel dst[i] = low; 2674130803Smarcel 2675130803Smarcel carry = high; 2676130803Smarcel } 2677130803Smarcel 2678130803Smarcel if (i < dstParts) { 2679130803Smarcel /* Full multiplication, there is no overflow. */ 2680130803Smarcel assert(i + 1 == dstParts); 2681130803Smarcel dst[i] = carry; 2682130803Smarcel return 0; 2683130803Smarcel } else { 2684130803Smarcel /* We overflowed if there is carry. */ 2685130803Smarcel if (carry) 2686130803Smarcel return 1; 2687130803Smarcel 2688130803Smarcel /* We would overflow if any significant unwritten parts would be 2689130803Smarcel non-zero. This is true if any remaining src parts are non-zero 2690130803Smarcel and the multiplier is non-zero. */ 2691130803Smarcel if (multiplier) 2692130803Smarcel for (; i < srcParts; i++) 2693130803Smarcel if (src[i]) 2694130803Smarcel return 1; 2695130803Smarcel 2696130803Smarcel /* We fitted in the narrow destination. */ 2697130803Smarcel return 0; 2698130803Smarcel } 2699130803Smarcel} 2700130803Smarcel 2701130803Smarcel/* DST = LHS * RHS, where DST has the same width as the operands and 2702130803Smarcel is filled with the least significant parts of the result. Returns 2703130803Smarcel one if overflow occurred, otherwise zero. DST must be disjoint 2704130803Smarcel from both operands. */ 2705130803Smarcelint 2706130803SmarcelAPInt::tcMultiply(integerPart *dst, const integerPart *lhs, 2707130803Smarcel const integerPart *rhs, unsigned int parts) 2708130803Smarcel{ 2709130803Smarcel unsigned int i; 2710130803Smarcel int overflow; 2711130803Smarcel 2712130803Smarcel assert(dst != lhs && dst != rhs); 2713130803Smarcel 2714130803Smarcel overflow = 0; 2715130803Smarcel tcSet(dst, 0, parts); 2716130803Smarcel 2717130803Smarcel for (i = 0; i < parts; i++) 2718130803Smarcel overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, 2719130803Smarcel parts - i, true); 2720130803Smarcel 2721130803Smarcel return overflow; 2722130803Smarcel} 2723130803Smarcel 2724130803Smarcel/* DST = LHS * RHS, where DST has width the sum of the widths of the 2725130803Smarcel operands. No overflow occurs. DST must be disjoint from both 2726130803Smarcel operands. Returns the number of parts required to hold the 2727130803Smarcel result. */ 2728130803Smarcelunsigned int 2729130803SmarcelAPInt::tcFullMultiply(integerPart *dst, const integerPart *lhs, 2730130803Smarcel const integerPart *rhs, unsigned int lhsParts, 2731130803Smarcel unsigned int rhsParts) 2732130803Smarcel{ 2733130803Smarcel /* Put the narrower number on the LHS for less loops below. */ 2734130803Smarcel if (lhsParts > rhsParts) { 2735130803Smarcel return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts); 2736130803Smarcel } else { 2737130803Smarcel unsigned int n; 2738130803Smarcel 2739130803Smarcel assert(dst != lhs && dst != rhs); 2740130803Smarcel 2741130803Smarcel tcSet(dst, 0, rhsParts); 2742130803Smarcel 2743130803Smarcel for (n = 0; n < lhsParts; n++) 2744130803Smarcel tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true); 2745130803Smarcel 2746130803Smarcel n = lhsParts + rhsParts; 2747130803Smarcel 2748130803Smarcel return n - (dst[n - 1] == 0); 2749130803Smarcel } 2750130803Smarcel} 2751130803Smarcel 2752130803Smarcel/* If RHS is zero LHS and REMAINDER are left unchanged, return one. 2753130803Smarcel Otherwise set LHS to LHS / RHS with the fractional part discarded, 2754130803Smarcel set REMAINDER to the remainder, return zero. i.e. 2755130803Smarcel 2756130803Smarcel OLD_LHS = RHS * LHS + REMAINDER 2757130803Smarcel 2758130803Smarcel SCRATCH is a bignum of the same size as the operands and result for 2759130803Smarcel use by the routine; its contents need not be initialized and are 2760130803Smarcel destroyed. LHS, REMAINDER and SCRATCH must be distinct. 2761130803Smarcel*/ 2762130803Smarcelint 2763130803SmarcelAPInt::tcDivide(integerPart *lhs, const integerPart *rhs, 2764130803Smarcel integerPart *remainder, integerPart *srhs, 2765130803Smarcel unsigned int parts) 2766130803Smarcel{ 2767130803Smarcel unsigned int n, shiftCount; 2768130803Smarcel integerPart mask; 2769130803Smarcel 2770130803Smarcel assert(lhs != remainder && lhs != srhs && remainder != srhs); 2771130803Smarcel 2772130803Smarcel shiftCount = tcMSB(rhs, parts) + 1; 2773130803Smarcel if (shiftCount == 0) 2774130803Smarcel return true; 2775130803Smarcel 2776130803Smarcel shiftCount = parts * integerPartWidth - shiftCount; 2777130803Smarcel n = shiftCount / integerPartWidth; 2778130803Smarcel mask = (integerPart) 1 << (shiftCount % integerPartWidth); 2779130803Smarcel 2780130803Smarcel tcAssign(srhs, rhs, parts); 2781130803Smarcel tcShiftLeft(srhs, parts, shiftCount); 2782130803Smarcel tcAssign(remainder, lhs, parts); 2783130803Smarcel tcSet(lhs, 0, parts); 2784130803Smarcel 2785130803Smarcel /* Loop, subtracting SRHS if REMAINDER is greater and adding that to 2786130803Smarcel the total. */ 2787130803Smarcel for (;;) { 2788130803Smarcel int compare; 2789130803Smarcel 2790130803Smarcel compare = tcCompare(remainder, srhs, parts); 2791130803Smarcel if (compare >= 0) { 2792130803Smarcel tcSubtract(remainder, srhs, 0, parts); 2793130803Smarcel lhs[n] |= mask; 2794130803Smarcel } 2795130803Smarcel 2796130803Smarcel if (shiftCount == 0) 2797130803Smarcel break; 2798130803Smarcel shiftCount--; 2799130803Smarcel tcShiftRight(srhs, parts, 1); 2800130803Smarcel if ((mask >>= 1) == 0) 2801130803Smarcel mask = (integerPart) 1 << (integerPartWidth - 1), n--; 2802130803Smarcel } 2803130803Smarcel 2804130803Smarcel return false; 2805130803Smarcel} 2806130803Smarcel 2807130803Smarcel/* Shift a bignum left COUNT bits in-place. Shifted in bits are zero. 2808130803Smarcel There are no restrictions on COUNT. */ 2809130803Smarcelvoid 2810130803SmarcelAPInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count) 2811130803Smarcel{ 2812130803Smarcel if (count) { 2813130803Smarcel unsigned int jump, shift; 2814130803Smarcel 2815130803Smarcel /* Jump is the inter-part jump; shift is is intra-part shift. */ 2816130803Smarcel jump = count / integerPartWidth; 2817130803Smarcel shift = count % integerPartWidth; 2818130803Smarcel 2819130803Smarcel while (parts > jump) { 2820130803Smarcel integerPart part; 2821130803Smarcel 2822130803Smarcel parts--; 2823130803Smarcel 2824130803Smarcel /* dst[i] comes from the two parts src[i - jump] and, if we have 2825130803Smarcel an intra-part shift, src[i - jump - 1]. */ 2826130803Smarcel part = dst[parts - jump]; 2827130803Smarcel if (shift) { 2828130803Smarcel part <<= shift; 2829130803Smarcel if (parts >= jump + 1) 2830130803Smarcel part |= dst[parts - jump - 1] >> (integerPartWidth - shift); 2831130803Smarcel } 2832130803Smarcel 2833130803Smarcel dst[parts] = part; 2834130803Smarcel } 2835130803Smarcel 2836130803Smarcel while (parts > 0) 2837130803Smarcel dst[--parts] = 0; 2838130803Smarcel } 2839130803Smarcel} 2840130803Smarcel 2841130803Smarcel/* Shift a bignum right COUNT bits in-place. Shifted in bits are 2842130803Smarcel zero. There are no restrictions on COUNT. */ 2843130803Smarcelvoid 2844130803SmarcelAPInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count) 2845130803Smarcel{ 2846130803Smarcel if (count) { 2847130803Smarcel unsigned int i, jump, shift; 2848130803Smarcel 2849130803Smarcel /* Jump is the inter-part jump; shift is is intra-part shift. */ 2850130803Smarcel jump = count / integerPartWidth; 2851130803Smarcel shift = count % integerPartWidth; 2852130803Smarcel 2853130803Smarcel /* Perform the shift. This leaves the most significant COUNT bits 2854130803Smarcel of the result at zero. */ 2855130803Smarcel for (i = 0; i < parts; i++) { 2856130803Smarcel integerPart part; 2857130803Smarcel 2858130803Smarcel if (i + jump >= parts) { 2859130803Smarcel part = 0; 2860130803Smarcel } else { 2861130803Smarcel part = dst[i + jump]; 2862130803Smarcel if (shift) { 2863130803Smarcel part >>= shift; 2864130803Smarcel if (i + jump + 1 < parts) 2865130803Smarcel part |= dst[i + jump + 1] << (integerPartWidth - shift); 2866130803Smarcel } 2867130803Smarcel } 2868130803Smarcel 2869130803Smarcel dst[i] = part; 2870130803Smarcel } 2871130803Smarcel } 2872130803Smarcel} 2873130803Smarcel 2874130803Smarcel/* Bitwise and of two bignums. */ 2875130803Smarcelvoid 2876130803SmarcelAPInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts) 2877130803Smarcel{ 2878130803Smarcel unsigned int i; 2879130803Smarcel 2880130803Smarcel for (i = 0; i < parts; i++) 2881130803Smarcel dst[i] &= rhs[i]; 2882130803Smarcel} 2883130803Smarcel 2884130803Smarcel/* Bitwise inclusive or of two bignums. */ 2885130803Smarcelvoid 2886130803SmarcelAPInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts) 2887130803Smarcel{ 2888130803Smarcel unsigned int i; 2889130803Smarcel 2890130803Smarcel for (i = 0; i < parts; i++) 2891130803Smarcel dst[i] |= rhs[i]; 2892130803Smarcel} 2893130803Smarcel 2894130803Smarcel/* Bitwise exclusive or of two bignums. */ 2895130803Smarcelvoid 2896130803SmarcelAPInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts) 2897130803Smarcel{ 2898130803Smarcel unsigned int i; 2899130803Smarcel 2900130803Smarcel for (i = 0; i < parts; i++) 2901130803Smarcel dst[i] ^= rhs[i]; 2902130803Smarcel} 2903130803Smarcel 2904130803Smarcel/* Complement a bignum in-place. */ 2905130803Smarcelvoid 2906130803SmarcelAPInt::tcComplement(integerPart *dst, unsigned int parts) 2907130803Smarcel{ 2908130803Smarcel unsigned int i; 2909130803Smarcel 2910130803Smarcel for (i = 0; i < parts; i++) 2911130803Smarcel dst[i] = ~dst[i]; 2912130803Smarcel} 2913130803Smarcel 2914130803Smarcel/* Comparison (unsigned) of two bignums. */ 2915130803Smarcelint 2916130803SmarcelAPInt::tcCompare(const integerPart *lhs, const integerPart *rhs, 2917130803Smarcel unsigned int parts) 2918130803Smarcel{ 2919130803Smarcel while (parts) { 2920130803Smarcel parts--; 2921130803Smarcel if (lhs[parts] == rhs[parts]) 2922130803Smarcel continue; 2923130803Smarcel 2924130803Smarcel if (lhs[parts] > rhs[parts]) 2925130803Smarcel return 1; 2926130803Smarcel else 2927130803Smarcel return -1; 2928130803Smarcel } 2929130803Smarcel 2930130803Smarcel return 0; 2931130803Smarcel} 2932130803Smarcel 2933130803Smarcel/* Increment a bignum in-place, return the carry flag. */ 2934130803SmarcelintegerPart 2935130803SmarcelAPInt::tcIncrement(integerPart *dst, unsigned int parts) 2936130803Smarcel{ 2937130803Smarcel unsigned int i; 2938130803Smarcel 2939130803Smarcel for (i = 0; i < parts; i++) 2940130803Smarcel if (++dst[i] != 0) 2941130803Smarcel break; 2942130803Smarcel 2943130803Smarcel return i == parts; 2944130803Smarcel} 2945130803Smarcel 2946130803Smarcel/* Set the least significant BITS bits of a bignum, clear the 2947130803Smarcel rest. */ 2948130803Smarcelvoid 2949130803SmarcelAPInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts, 2950130803Smarcel unsigned int bits) 2951130803Smarcel{ 2952130803Smarcel unsigned int i; 2953130803Smarcel 2954130803Smarcel i = 0; 2955130803Smarcel while (bits > integerPartWidth) { 2956130803Smarcel dst[i++] = ~(integerPart) 0; 2957130803Smarcel bits -= integerPartWidth; 2958130803Smarcel } 2959130803Smarcel 2960130803Smarcel if (bits) 2961130803Smarcel dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits); 2962130803Smarcel 2963130803Smarcel while (i < parts) 2964130803Smarcel dst[i++] = 0; 2965130803Smarcel} 2966130803Smarcel