APInt.cpp revision a05eaa658eeb5cd57219ea87e0c2e775dc5105ca
1//===-- APInt.cpp - Implement APInt class ---------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by Sheng Zhou and is distributed under the 6// University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements a class to represent arbitrary precision integral 11// constant values. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/ADT/APInt.h" 16 17#if 0 18#include "llvm/DerivedTypes.h" 19#include "llvm/Support/MathExtras.h" 20#include <cstring> 21#include <cstdlib> 22using namespace llvm; 23 24/// mul_1 - This function performs the multiplication operation on a 25/// large integer (represented as an integer array) and a uint64_t integer. 26/// @returns the carry of the multiplication. 27static uint64_t mul_1(uint64_t dest[], uint64_t x[], 28 unsigned len, uint64_t y) { 29 // Split y into high 32-bit part and low 32-bit part. 30 uint64_t ly = y & 0xffffffffULL, hy = y >> 32; 31 uint64_t carry = 0, lx, hx; 32 for (unsigned i = 0; i < len; ++i) { 33 lx = x[i] & 0xffffffffULL; 34 hx = x[i] >> 32; 35 // hasCarry - A flag to indicate if has carry. 36 // hasCarry == 0, no carry 37 // hasCarry == 1, has carry 38 // hasCarry == 2, no carry and the calculation result == 0. 39 uint8_t hasCarry = 0; 40 dest[i] = carry + lx * ly; 41 // Determine if the add above introduces carry. 42 hasCarry = (dest[i] < carry) ? 1 : 0; 43 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0); 44 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) + 45 // (2^32 - 1) + 2^32 = 2^64. 46 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 47 48 carry += (lx * hy) & 0xffffffffULL; 49 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL); 50 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) + 51 (carry >> 32) + ((lx * hy) >> 32) + hx * hy; 52 } 53 54 return carry; 55} 56 57/// mul - This function multiplies integer array x[] by integer array y[] and 58/// stores the result into integer array dest[]. 59/// Note the array dest[]'s size should no less than xlen + ylen. 60static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, 61 uint64_t y[], unsigned ylen) { 62 dest[xlen] = mul_1(dest, x, xlen, y[0]); 63 64 for (unsigned i = 1; i < ylen; ++i) { 65 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32; 66 uint64_t carry = 0, lx, hx; 67 for (unsigned j = 0; j < xlen; ++j) { 68 lx = x[j] & 0xffffffffULL; 69 hx = x[j] >> 32; 70 // hasCarry - A flag to indicate if has carry. 71 // hasCarry == 0, no carry 72 // hasCarry == 1, has carry 73 // hasCarry == 2, no carry and the calculation result == 0. 74 uint8_t hasCarry = 0; 75 uint64_t resul = carry + lx * ly; 76 hasCarry = (resul < carry) ? 1 : 0; 77 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32); 78 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0); 79 80 carry += (lx * hy) & 0xffffffffULL; 81 resul = (carry << 32) | (resul & 0xffffffffULL); 82 dest[i+j] += resul; 83 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+ 84 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) + 85 ((lx * hy) >> 32) + hx * hy; 86 } 87 dest[i+xlen] = carry; 88 } 89} 90 91/// add_1 - This function adds the integer array x[] by integer y and 92/// returns the carry. 93/// @returns the carry of the addition. 94static uint64_t add_1(uint64_t dest[], uint64_t x[], 95 unsigned len, uint64_t y) { 96 uint64_t carry = y; 97 98 for (unsigned i = 0; i < len; ++i) { 99 dest[i] = carry + x[i]; 100 carry = (dest[i] < carry) ? 1 : 0; 101 } 102 return carry; 103} 104 105/// add - This function adds the integer array x[] by integer array 106/// y[] and returns the carry. 107static uint64_t add(uint64_t dest[], uint64_t x[], 108 uint64_t y[], unsigned len) { 109 unsigned carry = 0; 110 111 for (unsigned i = 0; i< len; ++i) { 112 carry += x[i]; 113 dest[i] = carry + y[i]; 114 carry = carry < x[i] ? 1 : (dest[i] < carry ? 1 : 0); 115 } 116 return carry; 117} 118 119/// sub_1 - This function subtracts the integer array x[] by 120/// integer y and returns the borrow-out carry. 121static uint64_t sub_1(uint64_t x[], unsigned len, uint64_t y) { 122 uint64_t cy = y; 123 124 for (unsigned i = 0; i < len; ++i) { 125 uint64_t X = x[i]; 126 x[i] -= cy; 127 if (cy > X) 128 cy = 1; 129 else { 130 cy = 0; 131 break; 132 } 133 } 134 135 return cy; 136} 137 138/// sub - This function subtracts the integer array x[] by 139/// integer array y[], and returns the borrow-out carry. 140static uint64_t sub(uint64_t dest[], uint64_t x[], 141 uint64_t y[], unsigned len) { 142 // Carry indicator. 143 uint64_t cy = 0; 144 145 for (unsigned i = 0; i < len; ++i) { 146 uint64_t Y = y[i], X = x[i]; 147 Y += cy; 148 149 cy = Y < cy ? 1 : 0; 150 Y = X - Y; 151 cy += Y > X ? 1 : 0; 152 dest[i] = Y; 153 } 154 return cy; 155} 156 157/// UnitDiv - This function divides N by D, 158/// and returns (remainder << 32) | quotient. 159/// Assumes (N >> 32) < D. 160static uint64_t unitDiv(uint64_t N, unsigned D) { 161 uint64_t q, r; // q: quotient, r: remainder. 162 uint64_t a1 = N >> 32; // a1: high 32-bit part of N. 163 uint64_t a0 = N & 0xffffffffL; // a0: low 32-bit part of N 164 if (a1 < ((D - a1 - (a0 >> 31)) & 0xffffffffL)) { 165 q = N / D; 166 r = N % D; 167 } 168 else { 169 // Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d 170 uint64_t c = N - ((uint64_t) D << 31); 171 // Divide (c1*2^32 + c0) by d 172 q = c / D; 173 r = c % D; 174 // Add 2^31 to quotient 175 q += 1 << 31; 176 } 177 178 return (r << 32) | (q & 0xFFFFFFFFl); 179} 180 181/// subMul - This function substracts x[len-1:0] * y from 182/// dest[offset+len-1:offset], and returns the most significant 183/// word of the product, minus the borrow-out from the subtraction. 184static unsigned subMul(unsigned dest[], unsigned offset, 185 unsigned x[], unsigned len, unsigned y) { 186 uint64_t yl = (uint64_t) y & 0xffffffffL; 187 unsigned carry = 0; 188 unsigned j = 0; 189 do { 190 uint64_t prod = ((uint64_t) x[j] & 0xffffffffL) * yl; 191 unsigned prod_low = (unsigned) prod; 192 unsigned prod_high = (unsigned) (prod >> 32); 193 prod_low += carry; 194 carry = (prod_low < carry ? 1 : 0) + prod_high; 195 unsigned x_j = dest[offset+j]; 196 prod_low = x_j - prod_low; 197 if (prod_low > x_j) ++carry; 198 dest[offset+j] = prod_low; 199 } while (++j < len); 200 return carry; 201} 202 203/// div - This is basically Knuth's formulation of the classical algorithm. 204/// Correspondance with Knuth's notation: 205/// Knuth's u[0:m+n] == zds[nx:0]. 206/// Knuth's v[1:n] == y[ny-1:0] 207/// Knuth's n == ny. 208/// Knuth's m == nx-ny. 209/// Our nx == Knuth's m+n. 210/// Could be re-implemented using gmp's mpn_divrem: 211/// zds[nx] = mpn_divrem (&zds[ny], 0, zds, nx, y, ny). 212static void div(unsigned zds[], unsigned nx, unsigned y[], unsigned ny) { 213 unsigned j = nx; 214 do { // loop over digits of quotient 215 // Knuth's j == our nx-j. 216 // Knuth's u[j:j+n] == our zds[j:j-ny]. 217 unsigned qhat; // treated as unsigned 218 if (zds[j] == y[ny-1]) qhat = -1U; // 0xffffffff 219 else { 220 uint64_t w = (((uint64_t)(zds[j])) << 32) + 221 ((uint64_t)zds[j-1] & 0xffffffffL); 222 qhat = (unsigned) unitDiv(w, y[ny-1]); 223 } 224 if (qhat) { 225 unsigned borrow = subMul(zds, j - ny, y, ny, qhat); 226 unsigned save = zds[j]; 227 uint64_t num = ((uint64_t)save&0xffffffffL) - 228 ((uint64_t)borrow&0xffffffffL); 229 while (num) { 230 qhat--; 231 uint64_t carry = 0; 232 for (unsigned i = 0; i < ny; i++) { 233 carry += ((uint64_t) zds[j-ny+i] & 0xffffffffL) 234 + ((uint64_t) y[i] & 0xffffffffL); 235 zds[j-ny+i] = (unsigned) carry; 236 carry >>= 32; 237 } 238 zds[j] += carry; 239 num = carry - 1; 240 } 241 } 242 zds[j] = qhat; 243 } while (--j >= ny); 244} 245 246/// lshift - This function shift x[0:len-1] left by shiftAmt bits, and 247/// store the len least significant words of the result in 248/// dest[d_offset:d_offset+len-1]. It returns the bits shifted out from 249/// the most significant digit. 250static uint64_t lshift(uint64_t dest[], unsigned d_offset, 251 uint64_t x[], unsigned len, unsigned shiftAmt) { 252 unsigned count = 64 - shiftAmt; 253 int i = len - 1; 254 uint64_t high_word = x[i], retVal = high_word >> count; 255 ++d_offset; 256 while (--i >= 0) { 257 uint64_t low_word = x[i]; 258 dest[d_offset+i] = (high_word << shiftAmt) | (low_word >> count); 259 high_word = low_word; 260 } 261 dest[d_offset+i] = high_word << shiftAmt; 262 return retVal; 263} 264 265APInt::APInt(uint64_t val, unsigned numBits) 266 : BitsNum(numBits) { 267 assert(BitsNum >= IntegerType::MIN_INT_BITS && "bitwidth too small"); 268 assert(BitsNum <= IntegerType::MAX_INT_BITS && "bitwidth too large"); 269 if (isSingleWord()) 270 VAL = val & (~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - BitsNum)); 271 else { 272 // Memory allocation and check if successful. 273 assert((pVal = new uint64_t[getNumWords()]) && 274 "APInt memory allocation fails!"); 275 memset(pVal, 0, getNumWords() * 8); 276 pVal[0] = val; 277 } 278} 279 280APInt::APInt(unsigned numBits, uint64_t bigVal[]) 281 : BitsNum(numBits) { 282 assert(BitsNum >= IntegerType::MIN_INT_BITS && "bitwidth too small"); 283 assert(BitsNum <= IntegerType::MAX_INT_BITS && "bitwidth too large"); 284 assert(bigVal && "Null pointer detected!"); 285 if (isSingleWord()) 286 VAL = bigVal[0] & (~uint64_t(0ULL) >> (APINT_BITS_PER_WORD - BitsNum)); 287 else { 288 // Memory allocation and check if successful. 289 assert((pVal = new uint64_t[getNumWords()]) && 290 "APInt memory allocation fails!"); 291 // Calculate the actual length of bigVal[]. 292 unsigned n = sizeof(*bigVal) / sizeof(bigVal[0]); 293 unsigned maxN = std::max<unsigned>(n, getNumWords()); 294 unsigned minN = std::min<unsigned>(n, getNumWords()); 295 memcpy(pVal, bigVal, (minN - 1) * 8); 296 pVal[minN-1] = bigVal[minN-1] & (~uint64_t(0ULL) >> (64 - BitsNum % 64)); 297 if (maxN == getNumWords()) 298 memset(pVal+n, 0, (getNumWords() - n) * 8); 299 } 300} 301 302/// @brief Create a new APInt by translating the char array represented 303/// integer value. 304APInt::APInt(const char StrStart[], unsigned slen, uint8_t radix) { 305 StrToAPInt(StrStart, slen, radix); 306} 307 308/// @brief Create a new APInt by translating the string represented 309/// integer value. 310APInt::APInt(const std::string& Val, uint8_t radix) { 311 assert(!Val.empty() && "String empty?"); 312 StrToAPInt(Val.c_str(), Val.size(), radix); 313} 314 315/// @brief Converts a char array into an integer. 316void APInt::StrToAPInt(const char *StrStart, unsigned slen, uint8_t radix) { 317 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && 318 "Radix should be 2, 8, 10, or 16!"); 319 assert(StrStart && "String empty?"); 320 unsigned size = 0; 321 // If the radix is a power of 2, read the input 322 // from most significant to least significant. 323 if ((radix & (radix - 1)) == 0) { 324 unsigned nextBitPos = 0, bits_per_digit = radix / 8 + 2; 325 uint64_t resDigit = 0; 326 BitsNum = slen * bits_per_digit; 327 if (getNumWords() > 1) 328 assert((pVal = new uint64_t[getNumWords()]) && 329 "APInt memory allocation fails!"); 330 for (int i = slen - 1; i >= 0; --i) { 331 uint64_t digit = StrStart[i] - 48; // '0' == 48. 332 resDigit |= digit << nextBitPos; 333 nextBitPos += bits_per_digit; 334 if (nextBitPos >= 64) { 335 if (isSingleWord()) { 336 VAL = resDigit; 337 break; 338 } 339 pVal[size++] = resDigit; 340 nextBitPos -= 64; 341 resDigit = digit >> (bits_per_digit - nextBitPos); 342 } 343 } 344 if (!isSingleWord() && size <= getNumWords()) 345 pVal[size] = resDigit; 346 } else { // General case. The radix is not a power of 2. 347 // For 10-radix, the max value of 64-bit integer is 18446744073709551615, 348 // and its digits number is 14. 349 const unsigned chars_per_word = 20; 350 if (slen < chars_per_word || 351 (slen == chars_per_word && // In case the value <= 2^64 - 1 352 strcmp(StrStart, "18446744073709551615") <= 0)) { 353 BitsNum = 64; 354 VAL = strtoull(StrStart, 0, 10); 355 } else { // In case the value > 2^64 - 1 356 BitsNum = (slen / chars_per_word + 1) * 64; 357 assert((pVal = new uint64_t[getNumWords()]) && 358 "APInt memory allocation fails!"); 359 memset(pVal, 0, getNumWords() * 8); 360 unsigned str_pos = 0; 361 while (str_pos < slen) { 362 unsigned chunk = slen - str_pos; 363 if (chunk > chars_per_word - 1) 364 chunk = chars_per_word - 1; 365 uint64_t resDigit = StrStart[str_pos++] - 48; // 48 == '0'. 366 uint64_t big_base = radix; 367 while (--chunk > 0) { 368 resDigit = resDigit * radix + StrStart[str_pos++] - 48; 369 big_base *= radix; 370 } 371 372 uint64_t carry; 373 if (!size) 374 carry = resDigit; 375 else { 376 carry = mul_1(pVal, pVal, size, big_base); 377 carry += add_1(pVal, pVal, size, resDigit); 378 } 379 380 if (carry) pVal[size++] = carry; 381 } 382 } 383 } 384} 385 386APInt::APInt(const APInt& APIVal) 387 : BitsNum(APIVal.BitsNum) { 388 if (isSingleWord()) VAL = APIVal.VAL; 389 else { 390 // Memory allocation and check if successful. 391 assert((pVal = new uint64_t[getNumWords()]) && 392 "APInt memory allocation fails!"); 393 memcpy(pVal, APIVal.pVal, getNumWords() * 8); 394 } 395} 396 397APInt::~APInt() { 398 if (!isSingleWord() && pVal) delete[] pVal; 399} 400 401/// @brief Copy assignment operator. Create a new object from the given 402/// APInt one by initialization. 403APInt& APInt::operator=(const APInt& RHS) { 404 if (isSingleWord()) VAL = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 405 else { 406 unsigned minN = std::min(getNumWords(), RHS.getNumWords()); 407 memcpy(pVal, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, minN * 8); 408 if (getNumWords() != minN) 409 memset(pVal + minN, 0, (getNumWords() - minN) * 8); 410 } 411 return *this; 412} 413 414/// @brief Assignment operator. Assigns a common case integer value to 415/// the APInt. 416APInt& APInt::operator=(uint64_t RHS) { 417 if (isSingleWord()) VAL = RHS; 418 else { 419 pVal[0] = RHS; 420 memset(pVal, 0, (getNumWords() - 1) * 8); 421 } 422 TruncToBits(); 423 return *this; 424} 425 426/// @brief Prefix increment operator. Increments the APInt by one. 427APInt& APInt::operator++() { 428 if (isSingleWord()) ++VAL; 429 else 430 add_1(pVal, pVal, getNumWords(), 1); 431 TruncToBits(); 432 return *this; 433} 434 435/// @brief Prefix decrement operator. Decrements the APInt by one. 436APInt& APInt::operator--() { 437 if (isSingleWord()) --VAL; 438 else 439 sub_1(pVal, getNumWords(), 1); 440 TruncToBits(); 441 return *this; 442} 443 444/// @brief Addition assignment operator. Adds this APInt by the given APInt& 445/// RHS and assigns the result to this APInt. 446APInt& APInt::operator+=(const APInt& RHS) { 447 if (isSingleWord()) VAL += RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 448 else { 449 if (RHS.isSingleWord()) add_1(pVal, pVal, getNumWords(), RHS.VAL); 450 else { 451 if (getNumWords() <= RHS.getNumWords()) 452 add(pVal, pVal, RHS.pVal, getNumWords()); 453 else { 454 uint64_t carry = add(pVal, pVal, RHS.pVal, RHS.getNumWords()); 455 add_1(pVal + RHS.getNumWords(), pVal + RHS.getNumWords(), 456 getNumWords() - RHS.getNumWords(), carry); 457 } 458 } 459 } 460 TruncToBits(); 461 return *this; 462} 463 464/// @brief Subtraction assignment operator. Subtracts this APInt by the given 465/// APInt &RHS and assigns the result to this APInt. 466APInt& APInt::operator-=(const APInt& RHS) { 467 if (isSingleWord()) 468 VAL -= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 469 else { 470 if (RHS.isSingleWord()) 471 sub_1(pVal, getNumWords(), RHS.VAL); 472 else { 473 if (RHS.getNumWords() < getNumWords()) { 474 uint64_t carry = sub(pVal, pVal, RHS.pVal, RHS.getNumWords()); 475 sub_1(pVal + RHS.getNumWords(), getNumWords() - RHS.getNumWords(), carry); 476 } 477 else 478 sub(pVal, pVal, RHS.pVal, getNumWords()); 479 } 480 } 481 TruncToBits(); 482 return *this; 483} 484 485/// @brief Multiplication assignment operator. Multiplies this APInt by the 486/// given APInt& RHS and assigns the result to this APInt. 487APInt& APInt::operator*=(const APInt& RHS) { 488 if (isSingleWord()) VAL *= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 489 else { 490 // one-based first non-zero bit position. 491 unsigned first = getNumWords() * APINT_BITS_PER_WORD - CountLeadingZeros(); 492 unsigned xlen = !first ? 0 : whichWord(first - 1) + 1; 493 if (!xlen) 494 return *this; 495 else if (RHS.isSingleWord()) 496 mul_1(pVal, pVal, xlen, RHS.VAL); 497 else { 498 first = RHS.getNumWords() * APINT_BITS_PER_WORD - RHS.CountLeadingZeros(); 499 unsigned ylen = !first ? 0 : whichWord(first - 1) + 1; 500 if (!ylen) { 501 memset(pVal, 0, getNumWords() * 8); 502 return *this; 503 } 504 uint64_t *dest = new uint64_t[xlen+ylen]; 505 assert(dest && "Memory Allocation Failed!"); 506 mul(dest, pVal, xlen, RHS.pVal, ylen); 507 memcpy(pVal, dest, ((xlen + ylen >= getNumWords()) ? 508 getNumWords() : xlen + ylen) * 8); 509 delete[] dest; 510 } 511 } 512 TruncToBits(); 513 return *this; 514} 515 516/// @brief Bitwise AND assignment operator. Performs bitwise AND operation on 517/// this APInt and the given APInt& RHS, assigns the result to this APInt. 518APInt& APInt::operator&=(const APInt& RHS) { 519 if (isSingleWord()) { 520 if (RHS.isSingleWord()) VAL &= RHS.VAL; 521 else VAL &= RHS.pVal[0]; 522 } else { 523 if (RHS.isSingleWord()) { 524 memset(pVal, 0, (getNumWords() - 1) * 8); 525 pVal[0] &= RHS.VAL; 526 } else { 527 unsigned minwords = getNumWords() < RHS.getNumWords() ? 528 getNumWords() : RHS.getNumWords(); 529 for (unsigned i = 0; i < minwords; ++i) 530 pVal[i] &= RHS.pVal[i]; 531 if (getNumWords() > minwords) 532 memset(pVal+minwords, 0, (getNumWords() - minwords) * 8); 533 } 534 } 535 return *this; 536} 537 538/// @brief Bitwise OR assignment operator. Performs bitwise OR operation on 539/// this APInt and the given APInt& RHS, assigns the result to this APInt. 540APInt& APInt::operator|=(const APInt& RHS) { 541 if (isSingleWord()) { 542 if (RHS.isSingleWord()) VAL |= RHS.VAL; 543 else VAL |= RHS.pVal[0]; 544 } else { 545 if (RHS.isSingleWord()) { 546 pVal[0] |= RHS.VAL; 547 } else { 548 unsigned minwords = getNumWords() < RHS.getNumWords() ? 549 getNumWords() : RHS.getNumWords(); 550 for (unsigned i = 0; i < minwords; ++i) 551 pVal[i] |= RHS.pVal[i]; 552 } 553 } 554 TruncToBits(); 555 return *this; 556} 557 558/// @brief Bitwise XOR assignment operator. Performs bitwise XOR operation on 559/// this APInt and the given APInt& RHS, assigns the result to this APInt. 560APInt& APInt::operator^=(const APInt& RHS) { 561 if (isSingleWord()) { 562 if (RHS.isSingleWord()) VAL ^= RHS.VAL; 563 else VAL ^= RHS.pVal[0]; 564 } else { 565 if (RHS.isSingleWord()) { 566 for (unsigned i = 0; i < getNumWords(); ++i) 567 pVal[i] ^= RHS.VAL; 568 } else { 569 unsigned minwords = getNumWords() < RHS.getNumWords() ? 570 getNumWords() : RHS.getNumWords(); 571 for (unsigned i = 0; i < minwords; ++i) 572 pVal[i] ^= RHS.pVal[i]; 573 if (getNumWords() > minwords) 574 for (unsigned i = minwords; i < getNumWords(); ++i) 575 pVal[i] ^= 0; 576 } 577 } 578 TruncToBits(); 579 return *this; 580} 581 582/// @brief Bitwise AND operator. Performs bitwise AND operation on this APInt 583/// and the given APInt& RHS. 584APInt APInt::operator&(const APInt& RHS) const { 585 APInt API(RHS); 586 return API &= *this; 587} 588 589/// @brief Bitwise OR operator. Performs bitwise OR operation on this APInt 590/// and the given APInt& RHS. 591APInt APInt::operator|(const APInt& RHS) const { 592 APInt API(RHS); 593 API |= *this; 594 API.TruncToBits(); 595 return API; 596} 597 598/// @brief Bitwise XOR operator. Performs bitwise XOR operation on this APInt 599/// and the given APInt& RHS. 600APInt APInt::operator^(const APInt& RHS) const { 601 APInt API(RHS); 602 API ^= *this; 603 API.TruncToBits(); 604 return API; 605} 606 607/// @brief Logical AND operator. Performs logical AND operation on this APInt 608/// and the given APInt& RHS. 609bool APInt::operator&&(const APInt& RHS) const { 610 if (isSingleWord()) 611 return RHS.isSingleWord() ? VAL && RHS.VAL : VAL && RHS.pVal[0]; 612 else if (RHS.isSingleWord()) 613 return RHS.VAL && pVal[0]; 614 else { 615 unsigned minN = std::min(getNumWords(), RHS.getNumWords()); 616 for (unsigned i = 0; i < minN; ++i) 617 if (pVal[i] && RHS.pVal[i]) 618 return true; 619 } 620 return false; 621} 622 623/// @brief Logical OR operator. Performs logical OR operation on this APInt 624/// and the given APInt& RHS. 625bool APInt::operator||(const APInt& RHS) const { 626 if (isSingleWord()) 627 return RHS.isSingleWord() ? VAL || RHS.VAL : VAL || RHS.pVal[0]; 628 else if (RHS.isSingleWord()) 629 return RHS.VAL || pVal[0]; 630 else { 631 unsigned minN = std::min(getNumWords(), RHS.getNumWords()); 632 for (unsigned i = 0; i < minN; ++i) 633 if (pVal[i] || RHS.pVal[i]) 634 return true; 635 } 636 return false; 637} 638 639/// @brief Logical negation operator. Performs logical negation operation on 640/// this APInt. 641bool APInt::operator !() const { 642 if (isSingleWord()) 643 return !VAL; 644 else 645 for (unsigned i = 0; i < getNumWords(); ++i) 646 if (pVal[i]) 647 return false; 648 return true; 649} 650 651/// @brief Multiplication operator. Multiplies this APInt by the given APInt& 652/// RHS. 653APInt APInt::operator*(const APInt& RHS) const { 654 APInt API(RHS); 655 API *= *this; 656 API.TruncToBits(); 657 return API; 658} 659 660/// @brief Addition operator. Adds this APInt by the given APInt& RHS. 661APInt APInt::operator+(const APInt& RHS) const { 662 APInt API(*this); 663 API += RHS; 664 API.TruncToBits(); 665 return API; 666} 667 668/// @brief Subtraction operator. Subtracts this APInt by the given APInt& RHS 669APInt APInt::operator-(const APInt& RHS) const { 670 APInt API(*this); 671 API -= RHS; 672 return API; 673} 674 675/// @brief Array-indexing support. 676bool APInt::operator[](unsigned bitPosition) const { 677 return maskBit(bitPosition) & (isSingleWord() ? 678 VAL : pVal[whichWord(bitPosition)]) != 0; 679} 680 681/// @brief Equality operator. Compare this APInt with the given APInt& RHS 682/// for the validity of the equality relationship. 683bool APInt::operator==(const APInt& RHS) const { 684 unsigned n1 = getNumWords() * APINT_BITS_PER_WORD - CountLeadingZeros(), 685 n2 = RHS.getNumWords() * APINT_BITS_PER_WORD - RHS.CountLeadingZeros(); 686 if (n1 != n2) return false; 687 else if (isSingleWord()) 688 return VAL == (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]); 689 else { 690 if (n1 <= 64) 691 return pVal[0] == (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]); 692 for (int i = whichWord(n1 - 1); i >= 0; --i) 693 if (pVal[i] != RHS.pVal[i]) return false; 694 } 695 return true; 696} 697 698/// @brief Equality operator. Compare this APInt with the given uint64_t value 699/// for the validity of the equality relationship. 700bool APInt::operator==(uint64_t Val) const { 701 if (isSingleWord()) 702 return VAL == Val; 703 else { 704 unsigned n = getNumWords() * APINT_BITS_PER_WORD - CountLeadingZeros(); 705 if (n <= 64) 706 return pVal[0] == Val; 707 else 708 return false; 709 } 710} 711 712/// @brief Less-than operator. Compare this APInt with the given APInt& RHS 713/// for the validity of the less-than relationship. 714bool APInt::operator <(const APInt& RHS) const { 715 unsigned n1 = getNumWords() * 64 - CountLeadingZeros(), 716 n2 = RHS.getNumWords() * 64 - RHS.CountLeadingZeros(); 717 if (n1 < n2) return true; 718 else if (n1 > n2) return false; 719 else if (isSingleWord()) 720 return VAL < (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]); 721 else { 722 if (n1 <= 64) 723 return pVal[0] < (RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]); 724 for (int i = whichWord(n1 - 1); i >= 0; --i) { 725 if (pVal[i] > RHS.pVal[i]) return false; 726 else if (pVal[i] < RHS.pVal[i]) return true; 727 } 728 } 729 return false; 730} 731 732/// @brief Less-than-or-equal operator. Compare this APInt with the given 733/// APInt& RHS for the validity of the less-than-or-equal relationship. 734bool APInt::operator<=(const APInt& RHS) const { 735 return (*this) == RHS || (*this) < RHS; 736} 737 738/// @brief Greater-than operator. Compare this APInt with the given APInt& RHS 739/// for the validity of the greater-than relationship. 740bool APInt::operator >(const APInt& RHS) const { 741 return !((*this) <= RHS); 742} 743 744/// @brief Greater-than-or-equal operator. Compare this APInt with the given 745/// APInt& RHS for the validity of the greater-than-or-equal relationship. 746bool APInt::operator>=(const APInt& RHS) const { 747 return !((*this) < RHS); 748} 749 750/// Set the given bit to 1 whose poition is given as "bitPosition". 751/// @brief Set a given bit to 1. 752APInt& APInt::set(unsigned bitPosition) { 753 if (isSingleWord()) VAL |= maskBit(bitPosition); 754 else pVal[whichWord(bitPosition)] |= maskBit(bitPosition); 755 return *this; 756} 757 758/// @brief Set every bit to 1. 759APInt& APInt::set() { 760 if (isSingleWord()) VAL = -1ULL; 761 else 762 for (unsigned i = 0; i < getNumWords(); ++i) 763 pVal[i] = -1ULL; 764 return *this; 765} 766 767/// Set the given bit to 0 whose position is given as "bitPosition". 768/// @brief Set a given bit to 0. 769APInt& APInt::clear(unsigned bitPosition) { 770 if (isSingleWord()) VAL &= ~maskBit(bitPosition); 771 else pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition); 772 return *this; 773} 774 775/// @brief Set every bit to 0. 776APInt& APInt::clear() { 777 if (isSingleWord()) VAL = 0; 778 else 779 memset(pVal, 0, getNumWords() * 8); 780 return *this; 781} 782 783/// @brief Bitwise NOT operator. Performs a bitwise logical NOT operation on 784/// this APInt. 785APInt APInt::operator~() const { 786 APInt API(*this); 787 API.flip(); 788 return API; 789} 790 791/// @brief Toggle every bit to its opposite value. 792APInt& APInt::flip() { 793 if (isSingleWord()) VAL = (~(VAL << (64 - BitsNum))) >> (64 - BitsNum); 794 else { 795 unsigned i = 0; 796 for (; i < getNumWords() - 1; ++i) 797 pVal[i] = ~pVal[i]; 798 unsigned offset = 64 - (BitsNum - 64 * (i - 1)); 799 pVal[i] = (~(pVal[i] << offset)) >> offset; 800 } 801 return *this; 802} 803 804/// Toggle a given bit to its opposite value whose position is given 805/// as "bitPosition". 806/// @brief Toggles a given bit to its opposite value. 807APInt& APInt::flip(unsigned bitPosition) { 808 assert(bitPosition < BitsNum && "Out of the bit-width range!"); 809 if ((*this)[bitPosition]) clear(bitPosition); 810 else set(bitPosition); 811 return *this; 812} 813 814/// to_string - This function translates the APInt into a string. 815std::string APInt::to_string(uint8_t radix) const { 816 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2) && 817 "Radix should be 2, 8, 10, or 16!"); 818 char *buf = 0; 819 unsigned n = getNumWords() * 64 - CountLeadingZeros(); 820 std::string format = radix == 8 ? 821 "%0*llo" : (radix == 10 ? "%0*llu" : "%0*llx"); 822 // If the radix is a power of 2, set the format of ostringstream, 823 // and output the value into buf. 824 if ((radix & (radix - 1)) == 0) { 825 assert((buf = new char[n / Log2_32(radix) + 2]) && 826 "Memory allocation failed"); 827 if (isSingleWord()) 828 sprintf(buf, format.c_str(), 0, VAL); 829 else { 830 unsigned offset = sprintf(buf, format.c_str(), 0, pVal[whichWord(n-1)]); 831 for (int i = whichWord(n-1) - 1; i >= 0; --i) 832 offset += sprintf(buf + offset, format.c_str(), 833 64 / Log2_32(radix) + (64 % Log2_32(radix) ? 1 : 0), pVal[i]); 834 } 835 } 836 else { // If the radix = 10, need to translate the value into a 837 // string. 838 assert((buf = new char[(n / 64 + 1) * 20]) && "Memory allocation failed"); 839 if (isSingleWord()) 840 sprintf(buf, format.c_str(), 0, VAL); 841 else { 842 // FIXME: To be supported. 843 } 844 } 845 std::string retStr(buf); 846 delete[] buf; 847 return retStr; 848} 849 850/// getMaxValue - This function returns the largest value 851/// for an APInt of the specified bit-width and if isSign == true, 852/// it should be largest signed value, otherwise unsigned value. 853APInt APInt::getMaxValue(unsigned numBits, bool isSign) { 854 APInt APIVal(numBits, 1); 855 APIVal.set(); 856 return isSign ? APIVal.clear(numBits) : APIVal; 857} 858 859/// getMinValue - This function returns the smallest value for 860/// an APInt of the given bit-width and if isSign == true, 861/// it should be smallest signed value, otherwise zero. 862APInt APInt::getMinValue(unsigned numBits, bool isSign) { 863 APInt APIVal(0, numBits); 864 return isSign ? APIVal : APIVal.set(numBits); 865} 866 867/// getAllOnesValue - This function returns an all-ones value for 868/// an APInt of the specified bit-width. 869APInt APInt::getAllOnesValue(unsigned numBits) { 870 return getMaxValue(numBits, false); 871} 872 873/// getNullValue - This function creates an '0' value for an 874/// APInt of the specified bit-width. 875APInt APInt::getNullValue(unsigned numBits) { 876 return getMinValue(numBits, true); 877} 878 879/// HiBits - This function returns the high "numBits" bits of this APInt. 880APInt APInt::HiBits(unsigned numBits) const { 881 return APIntOps::lshr(*this, BitsNum - numBits); 882} 883 884/// LoBits - This function returns the low "numBits" bits of this APInt. 885APInt APInt::LoBits(unsigned numBits) const { 886 return APIntOps::lshr(APIntOps::shl(*this, BitsNum - numBits), 887 BitsNum - numBits); 888} 889 890/// CountLeadingZeros - This function is a APInt version corresponding to 891/// llvm/include/llvm/Support/MathExtras.h's function 892/// CountLeadingZeros_{32, 64}. It performs platform optimal form of counting 893/// the number of zeros from the most significant bit to the first one bit. 894/// @returns numWord() * 64 if the value is zero. 895unsigned APInt::CountLeadingZeros() const { 896 if (isSingleWord()) 897 return CountLeadingZeros_64(VAL); 898 unsigned Count = 0; 899 for (int i = getNumWords() - 1; i >= 0; --i) { 900 unsigned tmp = CountLeadingZeros_64(pVal[i]); 901 Count += tmp; 902 if (tmp != 64) 903 break; 904 } 905 return Count; 906} 907 908/// CountTrailingZero - This function is a APInt version corresponding to 909/// llvm/include/llvm/Support/MathExtras.h's function 910/// CountTrailingZeros_{32, 64}. It performs platform optimal form of counting 911/// the number of zeros from the least significant bit to the first one bit. 912/// @returns numWord() * 64 if the value is zero. 913unsigned APInt::CountTrailingZeros() const { 914 if (isSingleWord()) 915 return CountTrailingZeros_64(~VAL & (VAL - 1)); 916 APInt Tmp = ~(*this) & ((*this) - 1); 917 return getNumWords() * 64 - Tmp.CountLeadingZeros(); 918} 919 920/// CountPopulation - This function is a APInt version corresponding to 921/// llvm/include/llvm/Support/MathExtras.h's function 922/// CountPopulation_{32, 64}. It counts the number of set bits in a value. 923/// @returns 0 if the value is zero. 924unsigned APInt::CountPopulation() const { 925 if (isSingleWord()) 926 return CountPopulation_64(VAL); 927 unsigned Count = 0; 928 for (unsigned i = 0; i < getNumWords(); ++i) 929 Count += CountPopulation_64(pVal[i]); 930 return Count; 931} 932 933 934/// ByteSwap - This function returns a byte-swapped representation of the 935/// APInt argument, APIVal. 936APInt llvm::APIntOps::ByteSwap(const APInt& APIVal) { 937 if (APIVal.BitsNum <= 32) 938 return APInt(APIVal.BitsNum, ByteSwap_32(unsigned(APIVal.VAL))); 939 else if (APIVal.BitsNum <= 64) 940 return APInt(APIVal.BitsNum, ByteSwap_64(APIVal.VAL)); 941 else 942 return APIVal; 943} 944 945/// GreatestCommonDivisor - This function returns the greatest common 946/// divisor of the two APInt values using Enclid's algorithm. 947APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1, 948 const APInt& API2) { 949 APInt A = API1, B = API2; 950 while (!!B) { 951 APInt T = B; 952 B = APIntOps::urem(A, B); 953 A = T; 954 } 955 return A; 956} 957 958/// Arithmetic right-shift the APInt by shiftAmt. 959/// @brief Arithmetic right-shift function. 960APInt llvm::APIntOps::ashr(const APInt& LHS, unsigned shiftAmt) { 961 APInt API(LHS); 962 if (API.isSingleWord()) 963 API.VAL = (((int64_t(API.VAL) << (64 - API.BitsNum)) >> (64 - API.BitsNum)) 964 >> shiftAmt) & (~uint64_t(0UL) >> (64 - API.BitsNum)); 965 else { 966 if (shiftAmt >= API.BitsNum) { 967 memset(API.pVal, API[API.BitsNum-1] ? 1 : 0, (API.getNumWords()-1) * 8); 968 API.pVal[API.getNumWords() - 1] = ~uint64_t(0UL) >> 969 (64 - API.BitsNum % 64); 970 } else { 971 unsigned i = 0; 972 for (; i < API.BitsNum - shiftAmt; ++i) 973 if (API[i+shiftAmt]) 974 API.set(i); 975 else 976 API.clear(i); 977 for (; i < API.BitsNum; ++i) 978 API[API.BitsNum-1] ? API.set(i) : API.clear(i); 979 } 980 } 981 return API; 982} 983 984/// Logical right-shift the APInt by shiftAmt. 985/// @brief Logical right-shift function. 986APInt llvm::APIntOps::lshr(const APInt& RHS, unsigned shiftAmt) { 987 APInt API(RHS); 988 if (API.isSingleWord()) 989 API.VAL >>= shiftAmt; 990 else { 991 if (shiftAmt >= API.BitsNum) 992 memset(API.pVal, 0, API.getNumWords() * 8); 993 unsigned i = 0; 994 for (i = 0; i < API.BitsNum - shiftAmt; ++i) 995 if (API[i+shiftAmt]) API.set(i); 996 else API.clear(i); 997 for (; i < API.BitsNum; ++i) 998 API.clear(i); 999 } 1000 return API; 1001} 1002 1003/// Left-shift the APInt by shiftAmt. 1004/// @brief Left-shift function. 1005APInt llvm::APIntOps::shl(const APInt& RHS, unsigned shiftAmt) { 1006 APInt API(RHS); 1007 if (shiftAmt >= API.BitsNum) { 1008 if (API.isSingleWord()) 1009 API.VAL = 0; 1010 else 1011 memset(API.pVal, 0, API.getNumWords() * 8); 1012 } else { 1013 for (unsigned i = 0; i < shiftAmt; ++i) API.clear(i); 1014 for (unsigned i = shiftAmt; i < API.BitsNum; ++i) { 1015 if (API[i-shiftAmt]) API.set(i); 1016 else API.clear(i); 1017 } 1018 } 1019 return API; 1020} 1021 1022/// Unsigned divide APInt LHS by APInt RHS. 1023/// @brief Unsigned division function for APInt. 1024APInt llvm::APIntOps::udiv(const APInt& LHS, const APInt& RHS) { 1025 APInt API(LHS); 1026 unsigned first = RHS.getNumWords() * APInt::APINT_BITS_PER_WORD - 1027 RHS.CountLeadingZeros(); 1028 unsigned ylen = !first ? 0 : APInt::whichWord(first - 1) + 1; 1029 assert(ylen && "Divided by zero???"); 1030 if (API.isSingleWord()) { 1031 API.VAL = RHS.isSingleWord() ? (API.VAL / RHS.VAL) : 1032 (ylen > 1 ? 0 : API.VAL / RHS.pVal[0]); 1033 } else { 1034 unsigned first2 = API.getNumWords() * APInt::APINT_BITS_PER_WORD - 1035 API.CountLeadingZeros(); 1036 unsigned xlen = !first2 ? 0 : APInt::whichWord(first2 - 1) + 1; 1037 if (!xlen) 1038 return API; 1039 else if (API < RHS) 1040 memset(API.pVal, 0, API.getNumWords() * 8); 1041 else if (API == RHS) { 1042 memset(API.pVal, 0, API.getNumWords() * 8); 1043 API.pVal[0] = 1; 1044 } else if (xlen == 1) 1045 API.pVal[0] /= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 1046 else { 1047 uint64_t *xwords = new uint64_t[xlen+1], *ywords = new uint64_t[ylen]; 1048 assert(xwords && ywords && "Memory Allocation Failed!"); 1049 memcpy(xwords, API.pVal, xlen * 8); 1050 xwords[xlen] = 0; 1051 memcpy(ywords, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, ylen * 8); 1052 if (unsigned nshift = 63 - (first - 1) % 64) { 1053 lshift(ywords, 0, ywords, ylen, nshift); 1054 unsigned xlentmp = xlen; 1055 xwords[xlen++] = lshift(xwords, 0, xwords, xlentmp, nshift); 1056 } 1057 div((unsigned*)xwords, xlen*2-1, (unsigned*)ywords, ylen*2); 1058 memset(API.pVal, 0, API.getNumWords() * 8); 1059 memcpy(API.pVal, xwords + ylen, (xlen - ylen) * 8); 1060 delete[] xwords; 1061 delete[] ywords; 1062 } 1063 } 1064 return API; 1065} 1066 1067/// Unsigned remainder operation on APInt. 1068/// @brief Function for unsigned remainder operation. 1069APInt llvm::APIntOps::urem(const APInt& LHS, const APInt& RHS) { 1070 APInt API(LHS); 1071 unsigned first = RHS.getNumWords() * APInt::APINT_BITS_PER_WORD - 1072 RHS.CountLeadingZeros(); 1073 unsigned ylen = !first ? 0 : APInt::whichWord(first - 1) + 1; 1074 assert(ylen && "Performing remainder operation by zero ???"); 1075 if (API.isSingleWord()) { 1076 API.VAL = RHS.isSingleWord() ? (API.VAL % RHS.VAL) : 1077 (ylen > 1 ? API.VAL : API.VAL % RHS.pVal[0]); 1078 } else { 1079 unsigned first2 = API.getNumWords() * APInt::APINT_BITS_PER_WORD - 1080 API.CountLeadingZeros(); 1081 unsigned xlen = !first2 ? 0 : API.whichWord(first2 - 1) + 1; 1082 if (!xlen || API < RHS) 1083 return API; 1084 else if (API == RHS) 1085 memset(API.pVal, 0, API.getNumWords() * 8); 1086 else if (xlen == 1) 1087 API.pVal[0] %= RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0]; 1088 else { 1089 uint64_t *xwords = new uint64_t[xlen+1], *ywords = new uint64_t[ylen]; 1090 assert(xwords && ywords && "Memory Allocation Failed!"); 1091 memcpy(xwords, API.pVal, xlen * 8); 1092 xwords[xlen] = 0; 1093 memcpy(ywords, RHS.isSingleWord() ? &RHS.VAL : RHS.pVal, ylen * 8); 1094 unsigned nshift = 63 - (first - 1) % 64; 1095 if (nshift) { 1096 lshift(ywords, 0, ywords, ylen, nshift); 1097 unsigned xlentmp = xlen; 1098 xwords[xlen++] = lshift(xwords, 0, xwords, xlentmp, nshift); 1099 } 1100 div((unsigned*)xwords, xlen*2-1, (unsigned*)ywords, ylen*2); 1101 memset(API.pVal, 0, API.getNumWords() * 8); 1102 for (unsigned i = 0; i < ylen-1; ++i) 1103 API.pVal[i] = (xwords[i] >> nshift) | (xwords[i+1] << (64 - nshift)); 1104 API.pVal[ylen-1] = xwords[ylen-1] >> nshift; 1105 delete[] xwords; 1106 delete[] ywords; 1107 } 1108 } 1109 return API; 1110} 1111 1112#endif 1113 1114