~pali/+junk/llvm-toolchain-3.7 : revision 1

lib/Support/APInt.cpp

//===-- APInt.cpp - Implement APInt class ---------------------------------===//

// The LLVM Compiler Infrastructure

// This file is distributed under the University of Illinois Open Source

// License. See LICENSE.TXT for details.

//===----------------------------------------------------------------------===//

// This file implements a class to represent arbitrary precision integer

// constant values and provide a variety of arithmetic operations on them.

//===----------------------------------------------------------------------===//

#include "llvm/ADT/APInt.h"

#include "llvm/ADT/FoldingSet.h"

#include "llvm/ADT/Hashing.h"

#include "llvm/ADT/SmallString.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/ErrorHandling.h"

#include "llvm/Support/MathExtras.h"

#include "llvm/Support/raw_ostream.h"

#include <cmath>

#include <cstdlib>

#include <cstring>

#include <limits>

using namespace llvm;

#define DEBUG_TYPE "apint"

/// A utility function for allocating memory, checking for allocation failures,

/// and ensuring the contents are zeroed.

inline static uint64_t* getClearedMemory(unsigned numWords) {

uint64_t * result = new uint64_t[numWords];

assert(result && "APInt memory allocation fails!");

memset(result, 0, numWords * sizeof(uint64_t));

return result;

}

/// A utility function for allocating memory and checking for allocation

/// failure. The content is not zeroed.

inline static uint64_t* getMemory(unsigned numWords) {

uint64_t * result = new uint64_t[numWords];

assert(result && "APInt memory allocation fails!");

return result;

}

/// A utility function that converts a character to a digit.

inline static unsigned getDigit(char cdigit, uint8_t radix) {

unsigned r;

if (radix == 16 || radix == 36) {

r = cdigit - '0';

if (r <= 9)

return r;

r = cdigit - 'A';

if (r <= radix - 11U)

return r + 10;

r = cdigit - 'a';

if (r <= radix - 11U)

return r + 10;

radix = 10;

}

r = cdigit - '0';

if (r < radix)

return r;

return -1U;

}

void APInt::initSlowCase(unsigned numBits, uint64_t val, bool isSigned) {

pVal = getClearedMemory(getNumWords());

pVal[0] = val;

if (isSigned && int64_t(val) < 0)

for (unsigned i = 1; i < getNumWords(); ++i)

pVal[i] = -1ULL;

}

void APInt::initSlowCase(const APInt& that) {

pVal = getMemory(getNumWords());

memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);

}

void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {

assert(BitWidth && "Bitwidth too small");

assert(bigVal.data() && "Null pointer detected!");

if (isSingleWord())

VAL = bigVal[0];

else {

// Get memory, cleared to 0

pVal = getClearedMemory(getNumWords());

// Calculate the number of words to copy

unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());

100

// Copy the words from bigVal to pVal

101

memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);

102

}

103

// Make sure unused high bits are cleared

104

clearUnusedBits();

105

}

106

107

APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)

108

: BitWidth(numBits), VAL(0) {

109

initFromArray(bigVal);

110

}

111

112

APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])

113

: BitWidth(numBits), VAL(0) {

114

initFromArray(makeArrayRef(bigVal, numWords));

115

}

116

117

APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)

118

: BitWidth(numbits), VAL(0) {

119

assert(BitWidth && "Bitwidth too small");

120

fromString(numbits, Str, radix);

121

}

122

123

APInt& APInt::AssignSlowCase(const APInt& RHS) {

124

// Don't do anything for X = X

125

if (this == &RHS)

126

return *this;

127

128

if (BitWidth == RHS.getBitWidth()) {

129

// assume same bit-width single-word case is already handled

130

assert(!isSingleWord());

131

memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);

132

return *this;

133

}

134

135

if (isSingleWord()) {

136

// assume case where both are single words is already handled

137

assert(!RHS.isSingleWord());

138

VAL = 0;

139

pVal = getMemory(RHS.getNumWords());

140

memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);

141

} else if (getNumWords() == RHS.getNumWords())

142

memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);

143

else if (RHS.isSingleWord()) {

144

delete [] pVal;

145

VAL = RHS.VAL;

146

} else {

147

delete [] pVal;

148

pVal = getMemory(RHS.getNumWords());

149

memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);

150

}

151

BitWidth = RHS.BitWidth;

152

return clearUnusedBits();

153

}

154

155

APInt& APInt::operator=(uint64_t RHS) {

156

if (isSingleWord())

157

VAL = RHS;

158

else {

159

pVal[0] = RHS;

160

memset(pVal+1, 0, (getNumWords() - 1) * APINT_WORD_SIZE);

161

}

162

return clearUnusedBits();

163

}

164

165

/// This method 'profiles' an APInt for use with FoldingSet.

166

void APInt::Profile(FoldingSetNodeID& ID) const {

167

ID.AddInteger(BitWidth);

168

169

if (isSingleWord()) {

170

ID.AddInteger(VAL);

171

return;

172

}

173

174

unsigned NumWords = getNumWords();

175

for (unsigned i = 0; i < NumWords; ++i)

176

ID.AddInteger(pVal[i]);

177

}

178

179

/// This function adds a single "digit" integer, y, to the multiple

180

/// "digit" integer array, x[]. x[] is modified to reflect the addition and

181

/// 1 is returned if there is a carry out, otherwise 0 is returned.

182

/// @returns the carry of the addition.

183

static bool add_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {

184

for (unsigned i = 0; i < len; ++i) {

185

dest[i] = y + x[i];

186

if (dest[i] < y)

187

y = 1; // Carry one to next digit.

188

else {

189

y = 0; // No need to carry so exit early

190

break;

191

}

192

}

193

return y;

194

}

195

196

/// @brief Prefix increment operator. Increments the APInt by one.

197

APInt& APInt::operator++() {

198

if (isSingleWord())

199

++VAL;

200

else

201

add_1(pVal, pVal, getNumWords(), 1);

202

return clearUnusedBits();

203

}

204

205

/// This function subtracts a single "digit" (64-bit word), y, from

206

/// the multi-digit integer array, x[], propagating the borrowed 1 value until

207

/// no further borrowing is neeeded or it runs out of "digits" in x. The result

208

/// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted.

209

/// In other words, if y > x then this function returns 1, otherwise 0.

210

/// @returns the borrow out of the subtraction

211

static bool sub_1(uint64_t x[], unsigned len, uint64_t y) {

212

for (unsigned i = 0; i < len; ++i) {

213

uint64_t X = x[i];

214

x[i] -= y;

215

if (y > X)

216

y = 1; // We have to "borrow 1" from next "digit"

217

else {

218

y = 0; // No need to borrow

219

break; // Remaining digits are unchanged so exit early

220

}

221

}

222

return bool(y);

223

}

224

225

/// @brief Prefix decrement operator. Decrements the APInt by one.

226

APInt& APInt::operator--() {

227

if (isSingleWord())

228

--VAL;

229

else

230

sub_1(pVal, getNumWords(), 1);

231

return clearUnusedBits();

232

}

233

234

/// This function adds the integer array x to the integer array Y and

235

/// places the result in dest.

236

/// @returns the carry out from the addition

237

/// @brief General addition of 64-bit integer arrays

238

static bool add(uint64_t *dest, const uint64_t *x, const uint64_t *y,

239

unsigned len) {

240

bool carry = false;

241

for (unsigned i = 0; i< len; ++i) {

242

uint64_t limit = std::min(x[i],y[i]); // must come first in case dest == x

243

dest[i] = x[i] + y[i] + carry;

244

carry = dest[i] < limit || (carry && dest[i] == limit);

245

}

246

return carry;

247

}

248

249

/// Adds the RHS APint to this APInt.

250

/// @returns this, after addition of RHS.

251

/// @brief Addition assignment operator.

252

APInt& APInt::operator+=(const APInt& RHS) {

253

assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

254

if (isSingleWord())

255

VAL += RHS.VAL;

256

else {

257

add(pVal, pVal, RHS.pVal, getNumWords());

258

}

259

return clearUnusedBits();

260

}

261

262

/// Subtracts the integer array y from the integer array x

263

/// @returns returns the borrow out.

264

/// @brief Generalized subtraction of 64-bit integer arrays.

265

static bool sub(uint64_t *dest, const uint64_t *x, const uint64_t *y,

266

unsigned len) {

267

bool borrow = false;

268

for (unsigned i = 0; i < len; ++i) {

269

uint64_t x_tmp = borrow ? x[i] - 1 : x[i];

270

borrow = y[i] > x_tmp || (borrow && x[i] == 0);

271

dest[i] = x_tmp - y[i];

272

}

273

return borrow;

274

}

275

276

/// Subtracts the RHS APInt from this APInt

277

/// @returns this, after subtraction

278

/// @brief Subtraction assignment operator.

279

APInt& APInt::operator-=(const APInt& RHS) {

280

assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

281

if (isSingleWord())

282

VAL -= RHS.VAL;

283

else

284

sub(pVal, pVal, RHS.pVal, getNumWords());

285

return clearUnusedBits();

286

}

287

288

/// Multiplies an integer array, x, by a uint64_t integer and places the result

289

/// into dest.

290

/// @returns the carry out of the multiplication.

291

/// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.

292

static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {

293

// Split y into high 32-bit part (hy) and low 32-bit part (ly)

294

uint64_t ly = y & 0xffffffffULL, hy = y >> 32;

295

uint64_t carry = 0;

296

297

// For each digit of x.

298

for (unsigned i = 0; i < len; ++i) {

299

// Split x into high and low words

300

uint64_t lx = x[i] & 0xffffffffULL;

301

uint64_t hx = x[i] >> 32;

302

// hasCarry - A flag to indicate if there is a carry to the next digit.

303

// hasCarry == 0, no carry

304

// hasCarry == 1, has carry

305

// hasCarry == 2, no carry and the calculation result == 0.

306

uint8_t hasCarry = 0;

307

dest[i] = carry + lx * ly;

308

// Determine if the add above introduces carry.

309

hasCarry = (dest[i] < carry) ? 1 : 0;

310

carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);

311

// The upper limit of carry can be (2^32 - 1)(2^32 - 1) +

312

// (2^32 - 1) + 2^32 = 2^64.

313

hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);

314

315

carry += (lx * hy) & 0xffffffffULL;

316

dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);

317

carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +

318

(carry >> 32) + ((lx * hy) >> 32) + hx * hy;

319

}

320

return carry;

321

}

322

323

/// Multiplies integer array x by integer array y and stores the result into

324

/// the integer array dest. Note that dest's size must be >= xlen + ylen.

325

/// @brief Generalized multiplicate of integer arrays.

326

static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],

327

unsigned ylen) {

328

dest[xlen] = mul_1(dest, x, xlen, y[0]);

329

for (unsigned i = 1; i < ylen; ++i) {

330

uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;

331

uint64_t carry = 0, lx = 0, hx = 0;

332

for (unsigned j = 0; j < xlen; ++j) {

333

lx = x[j] & 0xffffffffULL;

334

hx = x[j] >> 32;

335

// hasCarry - A flag to indicate if has carry.

336

// hasCarry == 0, no carry

337

// hasCarry == 1, has carry

338

// hasCarry == 2, no carry and the calculation result == 0.

339

uint8_t hasCarry = 0;

340

uint64_t resul = carry + lx * ly;

341

hasCarry = (resul < carry) ? 1 : 0;

342

carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);

343

hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);

344

345

carry += (lx * hy) & 0xffffffffULL;

346

resul = (carry << 32) | (resul & 0xffffffffULL);

347

dest[i+j] += resul;

348

carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+

349

(carry >> 32) + (dest[i+j] < resul ? 1 : 0) +

350

((lx * hy) >> 32) + hx * hy;

351

}

352

dest[i+xlen] = carry;

353

}

354

}

355

356

APInt& APInt::operator*=(const APInt& RHS) {

357

assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

358

if (isSingleWord()) {

359

VAL *= RHS.VAL;

360

clearUnusedBits();

361

return *this;

362

}

363

364

// Get some bit facts about LHS and check for zero

365

unsigned lhsBits = getActiveBits();

366

unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;

367

if (!lhsWords)

368

// 0 * X ===> 0

369

return *this;

370

371

// Get some bit facts about RHS and check for zero

372

unsigned rhsBits = RHS.getActiveBits();

373

unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;

374

if (!rhsWords) {

375

// X * 0 ===> 0

376

clearAllBits();

377

return *this;

378

}

379

380

// Allocate space for the result

381

unsigned destWords = rhsWords + lhsWords;

382

uint64_t *dest = getMemory(destWords);

383

384

// Perform the long multiply

385

mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);

386

387

// Copy result back into *this

388

clearAllBits();

389

unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;

390

memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);

391

clearUnusedBits();

392

393

// delete dest array and return

394

delete[] dest;

395

return *this;

396

}

397

398

APInt& APInt::operator&=(const APInt& RHS) {

399

assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

400

if (isSingleWord()) {

401

VAL &= RHS.VAL;

402

return *this;

403

}

404

unsigned numWords = getNumWords();

405

for (unsigned i = 0; i < numWords; ++i)

406

pVal[i] &= RHS.pVal[i];

407

return *this;

408

}

409

410

APInt& APInt::operator|=(const APInt& RHS) {

411

assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

412

if (isSingleWord()) {

413

VAL |= RHS.VAL;

414

return *this;

415

}

416

unsigned numWords = getNumWords();

417

for (unsigned i = 0; i < numWords; ++i)

418

pVal[i] |= RHS.pVal[i];

419

return *this;

420

}

421

422

APInt& APInt::operator^=(const APInt& RHS) {

423

assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

424

if (isSingleWord()) {

425

VAL ^= RHS.VAL;

426

this->clearUnusedBits();

427

return *this;

428

}

429

unsigned numWords = getNumWords();

430

for (unsigned i = 0; i < numWords; ++i)

431

pVal[i] ^= RHS.pVal[i];

432

return clearUnusedBits();

433

}

434

435

APInt APInt::AndSlowCase(const APInt& RHS) const {

436

unsigned numWords = getNumWords();

437

uint64_t* val = getMemory(numWords);

438

for (unsigned i = 0; i < numWords; ++i)

439

val[i] = pVal[i] & RHS.pVal[i];

440

return APInt(val, getBitWidth());

441

}

442

443

APInt APInt::OrSlowCase(const APInt& RHS) const {

444

unsigned numWords = getNumWords();

445

uint64_t *val = getMemory(numWords);

446

for (unsigned i = 0; i < numWords; ++i)

447

val[i] = pVal[i] | RHS.pVal[i];

448

return APInt(val, getBitWidth());

449

}

450

451

APInt APInt::XorSlowCase(const APInt& RHS) const {

452

unsigned numWords = getNumWords();

453

uint64_t *val = getMemory(numWords);

454

for (unsigned i = 0; i < numWords; ++i)

455

val[i] = pVal[i] ^ RHS.pVal[i];

456

457

APInt Result(val, getBitWidth());

458

// 0^0==1 so clear the high bits in case they got set.

459

Result.clearUnusedBits();

460

return Result;

461

}

462

463

APInt APInt::operator*(const APInt& RHS) const {

464

assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

465

if (isSingleWord())

466

return APInt(BitWidth, VAL * RHS.VAL);

467

APInt Result(*this);

468

Result *= RHS;

469

return Result;

470

}

471

472

APInt APInt::operator+(const APInt& RHS) const {

473

assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

474

if (isSingleWord())

475

return APInt(BitWidth, VAL + RHS.VAL);

476

APInt Result(BitWidth, 0);

477

add(Result.pVal, this->pVal, RHS.pVal, getNumWords());

478

Result.clearUnusedBits();

479

return Result;

480

}

481

482

APInt APInt::operator-(const APInt& RHS) const {

483

assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

484

if (isSingleWord())

485

return APInt(BitWidth, VAL - RHS.VAL);

486

APInt Result(BitWidth, 0);

487

sub(Result.pVal, this->pVal, RHS.pVal, getNumWords());

488

Result.clearUnusedBits();

489

return Result;

490

}

491

492

bool APInt::EqualSlowCase(const APInt& RHS) const {

493

// Get some facts about the number of bits used in the two operands.

494

unsigned n1 = getActiveBits();

495

unsigned n2 = RHS.getActiveBits();

496

497

// If the number of bits isn't the same, they aren't equal

498

if (n1 != n2)

499

return false;

500

501

// If the number of bits fits in a word, we only need to compare the low word.

502

if (n1 <= APINT_BITS_PER_WORD)

503

return pVal[0] == RHS.pVal[0];

504

505

// Otherwise, compare everything

506

for (int i = whichWord(n1 - 1); i >= 0; --i)

507

if (pVal[i] != RHS.pVal[i])

508

return false;

509

return true;

510

}

511

512

bool APInt::EqualSlowCase(uint64_t Val) const {

513

unsigned n = getActiveBits();

514

if (n <= APINT_BITS_PER_WORD)

515

return pVal[0] == Val;

516

else

517

return false;

518

}

519

520

bool APInt::ult(const APInt& RHS) const {

521

assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");

522

if (isSingleWord())

523

return VAL < RHS.VAL;

524

525

// Get active bit length of both operands

526

unsigned n1 = getActiveBits();

527

unsigned n2 = RHS.getActiveBits();

528

529

// If magnitude of LHS is less than RHS, return true.

530

if (n1 < n2)

531

return true;

532

533

// If magnitude of RHS is greather than LHS, return false.

534

if (n2 < n1)

535

return false;

536

537

// If they bot fit in a word, just compare the low order word

538

if (n1 <= APINT_BITS_PER_WORD && n2 <= APINT_BITS_PER_WORD)

539

return pVal[0] < RHS.pVal[0];

540

541

// Otherwise, compare all words

542

unsigned topWord = whichWord(std::max(n1,n2)-1);

543

for (int i = topWord; i >= 0; --i) {

544

if (pVal[i] > RHS.pVal[i])

545

return false;

546

if (pVal[i] < RHS.pVal[i])

547

return true;

548

}

549

return false;

550

}

551

552

bool APInt::slt(const APInt& RHS) const {

553

assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");

554

if (isSingleWord()) {

555

int64_t lhsSext = (int64_t(VAL) << (64-BitWidth)) >> (64-BitWidth);

556

int64_t rhsSext = (int64_t(RHS.VAL) << (64-BitWidth)) >> (64-BitWidth);

557

return lhsSext < rhsSext;

558

}

559

560

APInt lhs(*this);

561

APInt rhs(RHS);

562

bool lhsNeg = isNegative();

563

bool rhsNeg = rhs.isNegative();

564

if (lhsNeg) {

565

// Sign bit is set so perform two's complement to make it positive

566

lhs.flipAllBits();

567

++lhs;

568

}

569

if (rhsNeg) {

570

// Sign bit is set so perform two's complement to make it positive

571

rhs.flipAllBits();

572

++rhs;

573

}

574

575

// Now we have unsigned values to compare so do the comparison if necessary

576

// based on the negativeness of the values.

577

if (lhsNeg)

578

if (rhsNeg)

579

return lhs.ugt(rhs);

580

else

581

return true;

582

else if (rhsNeg)

583

return false;

584

else

585

return lhs.ult(rhs);

586

}

587

588

void APInt::setBit(unsigned bitPosition) {

589

if (isSingleWord())

590

VAL |= maskBit(bitPosition);

591

else

592

pVal[whichWord(bitPosition)] |= maskBit(bitPosition);

593

}

594

595

/// Set the given bit to 0 whose position is given as "bitPosition".

596

/// @brief Set a given bit to 0.

597

void APInt::clearBit(unsigned bitPosition) {

598

if (isSingleWord())

599

VAL &= ~maskBit(bitPosition);

600

else

601

pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);

602

}

603

604

/// @brief Toggle every bit to its opposite value.

605

606

/// Toggle a given bit to its opposite value whose position is given

607

/// as "bitPosition".

608

/// @brief Toggles a given bit to its opposite value.

609

void APInt::flipBit(unsigned bitPosition) {

610

assert(bitPosition < BitWidth && "Out of the bit-width range!");

611

if ((*this)[bitPosition]) clearBit(bitPosition);

612

else setBit(bitPosition);

613

}

614

615

unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {

616

assert(!str.empty() && "Invalid string length");

617

assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||

618

radix == 36) &&

619

"Radix should be 2, 8, 10, 16, or 36!");

620

621

size_t slen = str.size();

622

623

// Each computation below needs to know if it's negative.

624

StringRef::iterator p = str.begin();

625

unsigned isNegative = *p == '-';

626

if (*p == '-' || *p == '+') {

627

p++;

628

slen--;

629

assert(slen && "String is only a sign, needs a value.");

630

}

631

632

// For radixes of power-of-two values, the bits required is accurately and

633

// easily computed

634

if (radix == 2)

635

return slen + isNegative;

636

if (radix == 8)

637

return slen * 3 + isNegative;

638

if (radix == 16)

639

return slen * 4 + isNegative;

640

641

// FIXME: base 36

642

643

// This is grossly inefficient but accurate. We could probably do something

644

// with a computation of roughly slen*64/20 and then adjust by the value of

645

// the first few digits. But, I'm not sure how accurate that could be.

646

647

// Compute a sufficient number of bits that is always large enough but might

648

// be too large. This avoids the assertion in the constructor. This

649

// calculation doesn't work appropriately for the numbers 0-9, so just use 4

650

// bits in that case.

651

unsigned sufficient

652

= radix == 10? (slen == 1 ? 4 : slen * 64/18)

653

: (slen == 1 ? 7 : slen * 16/3);

654

655

// Convert to the actual binary value.

656

APInt tmp(sufficient, StringRef(p, slen), radix);

657

658

// Compute how many bits are required. If the log is infinite, assume we need

659

// just bit.

660

unsigned log = tmp.logBase2();

661

if (log == (unsigned)-1) {

662

return isNegative + 1;

663

} else {

664

return isNegative + log + 1;

665

}

666

}

667

668

hash_code llvm::hash_value(const APInt &Arg) {

669

if (Arg.isSingleWord())

670

return hash_combine(Arg.VAL);

671

672

return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());

673

}

674

675

bool APInt::isSplat(unsigned SplatSizeInBits) const {

676

assert(getBitWidth() % SplatSizeInBits == 0 &&

677

"SplatSizeInBits must divide width!");

678

// We can check that all parts of an integer are equal by making use of a

679

// little trick: rotate and check if it's still the same value.

680

return *this == rotl(SplatSizeInBits);

681

}

682

683

/// This function returns the high "numBits" bits of this APInt.

684

APInt APInt::getHiBits(unsigned numBits) const {

685

return APIntOps::lshr(*this, BitWidth - numBits);

686

}

687

688

/// This function returns the low "numBits" bits of this APInt.

689

APInt APInt::getLoBits(unsigned numBits) const {

690

return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits),

691

BitWidth - numBits);

692

}

693

694

unsigned APInt::countLeadingZerosSlowCase() const {

695

// Treat the most significand word differently because it might have

696

// meaningless bits set beyond the precision.

697

unsigned BitsInMSW = BitWidth % APINT_BITS_PER_WORD;

698

integerPart MSWMask;

699

if (BitsInMSW) MSWMask = (integerPart(1) << BitsInMSW) - 1;

700

else {

701

MSWMask = ~integerPart(0);

702

BitsInMSW = APINT_BITS_PER_WORD;

703

}

704

705

unsigned i = getNumWords();

706

integerPart MSW = pVal[i-1] & MSWMask;

707

if (MSW)

708

return llvm::countLeadingZeros(MSW) - (APINT_BITS_PER_WORD - BitsInMSW);

709

710

unsigned Count = BitsInMSW;

711

for (--i; i > 0u; --i) {

712

if (pVal[i-1] == 0)

713

Count += APINT_BITS_PER_WORD;

714

else {

715

Count += llvm::countLeadingZeros(pVal[i-1]);

716

break;

717

}

718

}

719

return Count;

720

}

721

722

unsigned APInt::countLeadingOnes() const {

723

if (isSingleWord())

724

return llvm::countLeadingOnes(VAL << (APINT_BITS_PER_WORD - BitWidth));

725

726

unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;

727

unsigned shift;

728

if (!highWordBits) {

729

highWordBits = APINT_BITS_PER_WORD;

730

shift = 0;

731

} else {

732

shift = APINT_BITS_PER_WORD - highWordBits;

733

}

734

int i = getNumWords() - 1;

735

unsigned Count = llvm::countLeadingOnes(pVal[i] << shift);

736

if (Count == highWordBits) {

737

for (i--; i >= 0; --i) {

738

if (pVal[i] == -1ULL)

739

Count += APINT_BITS_PER_WORD;

740

else {

741

Count += llvm::countLeadingOnes(pVal[i]);

742

break;

743

}

744

}

745

}

746

return Count;

747

}

748

749

unsigned APInt::countTrailingZeros() const {

750

if (isSingleWord())

751

return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);

752

unsigned Count = 0;

753

unsigned i = 0;

754

for (; i < getNumWords() && pVal[i] == 0; ++i)

755

Count += APINT_BITS_PER_WORD;

756

if (i < getNumWords())

757

Count += llvm::countTrailingZeros(pVal[i]);

758

return std::min(Count, BitWidth);

759

}

760

761

unsigned APInt::countTrailingOnesSlowCase() const {

762

unsigned Count = 0;

763

unsigned i = 0;

764

for (; i < getNumWords() && pVal[i] == -1ULL; ++i)

765

Count += APINT_BITS_PER_WORD;

766

if (i < getNumWords())

767

Count += llvm::countTrailingOnes(pVal[i]);

768

return std::min(Count, BitWidth);

769

}

770

771

unsigned APInt::countPopulationSlowCase() const {

772

unsigned Count = 0;

773

for (unsigned i = 0; i < getNumWords(); ++i)

774

Count += llvm::countPopulation(pVal[i]);

775

return Count;

776

}

777

778

/// Perform a logical right-shift from Src to Dst, which must be equal or

779

/// non-overlapping, of Words words, by Shift, which must be less than 64.

780

static void lshrNear(uint64_t *Dst, uint64_t *Src, unsigned Words,

781

unsigned Shift) {

782

uint64_t Carry = 0;

783

for (int I = Words - 1; I >= 0; --I) {

784

uint64_t Tmp = Src[I];

785

Dst[I] = (Tmp >> Shift) | Carry;

786

Carry = Tmp << (64 - Shift);

787

}

788

}

789

790

APInt APInt::byteSwap() const {

791

assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");

792

if (BitWidth == 16)

793

return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));

794

if (BitWidth == 32)

795

return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));

796

if (BitWidth == 48) {

797

unsigned Tmp1 = unsigned(VAL >> 16);

798

Tmp1 = ByteSwap_32(Tmp1);

799

uint16_t Tmp2 = uint16_t(VAL);

800

Tmp2 = ByteSwap_16(Tmp2);

801

return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);

802

}

803

if (BitWidth == 64)

804

return APInt(BitWidth, ByteSwap_64(VAL));

805

806

APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);

807

for (unsigned I = 0, N = getNumWords(); I != N; ++I)

808

Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);

809

if (Result.BitWidth != BitWidth) {

810

lshrNear(Result.pVal, Result.pVal, getNumWords(),

811

Result.BitWidth - BitWidth);

812

Result.BitWidth = BitWidth;

813

}

814

return Result;

815

}

816

817

APInt llvm::APIntOps::GreatestCommonDivisor(const APInt& API1,

818

const APInt& API2) {

819

APInt A = API1, B = API2;

820

while (!!B) {

821

APInt T = B;

822

B = APIntOps::urem(A, B);

823

A = T;

824

}

825

return A;

826

}

827

828

APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {

829

union {

830

double D;

831

uint64_t I;

832

} T;

833

T.D = Double;

834

835

// Get the sign bit from the highest order bit

836

bool isNeg = T.I >> 63;

837

838

// Get the 11-bit exponent and adjust for the 1023 bit bias

839

int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;

840

841

// If the exponent is negative, the value is < 0 so just return 0.

842

if (exp < 0)

843

return APInt(width, 0u);

844

845

// Extract the mantissa by clearing the top 12 bits (sign + exponent).

846

uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;

847

848

// If the exponent doesn't shift all bits out of the mantissa

849

if (exp < 52)

850

return isNeg ? -APInt(width, mantissa >> (52 - exp)) :

851

APInt(width, mantissa >> (52 - exp));

852

853

// If the client didn't provide enough bits for us to shift the mantissa into

854

// then the result is undefined, just return 0

855

if (width <= exp - 52)

856

return APInt(width, 0);

857

858

// Otherwise, we have to shift the mantissa bits up to the right location

859

APInt Tmp(width, mantissa);

860

Tmp = Tmp.shl((unsigned)exp - 52);

861

return isNeg ? -Tmp : Tmp;

862

}

863

864

/// This function converts this APInt to a double.

865

/// The layout for double is as following (IEEE Standard 754):

866

/// --------------------------------------

867

/// | Sign Exponent Fraction Bias |

868

/// |-------------------------------------- |

869

/// | 1[63] 11[62-52] 52[51-00] 1023 |

870

/// --------------------------------------

871

double APInt::roundToDouble(bool isSigned) const {

872

873

// Handle the simple case where the value is contained in one uint64_t.

874

// It is wrong to optimize getWord(0) to VAL; there might be more than one word.

875

if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {

876

if (isSigned) {

877

int64_t sext = (int64_t(getWord(0)) << (64-BitWidth)) >> (64-BitWidth);

878

return double(sext);

879

} else

880

return double(getWord(0));

881

}

882

883

// Determine if the value is negative.

884

bool isNeg = isSigned ? (*this)[BitWidth-1] : false;

885

886

// Construct the absolute value if we're negative.

887

APInt Tmp(isNeg ? -(*this) : (*this));

888

889

// Figure out how many bits we're using.

890

unsigned n = Tmp.getActiveBits();

891

892

// The exponent (without bias normalization) is just the number of bits

893

// we are using. Note that the sign bit is gone since we constructed the

894

// absolute value.

895

uint64_t exp = n;

896

897

// Return infinity for exponent overflow

898

if (exp > 1023) {

899

if (!isSigned || !isNeg)

900

return std::numeric_limits<double>::infinity();

901

else

902

return -std::numeric_limits<double>::infinity();

903

}

904

exp += 1023; // Increment for 1023 bias

905

906

// Number of bits in mantissa is 52. To obtain the mantissa value, we must

907

// extract the high 52 bits from the correct words in pVal.

908

uint64_t mantissa;

909

unsigned hiWord = whichWord(n-1);

910

if (hiWord == 0) {

911

mantissa = Tmp.pVal[0];

912

if (n > 52)

913

mantissa >>= n - 52; // shift down, we want the top 52 bits.

914

} else {

915

assert(hiWord > 0 && "huh?");

916

uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);

917

uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);

918

mantissa = hibits | lobits;

919

}

920

921

// The leading bit of mantissa is implicit, so get rid of it.

922

uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;

923

union {

924

double D;

925

uint64_t I;

926

} T;

927

T.I = sign | (exp << 52) | mantissa;

928

return T.D;

929

}

930

931

// Truncate to new width.

932

APInt APInt::trunc(unsigned width) const {

933

assert(width < BitWidth && "Invalid APInt Truncate request");

934

assert(width && "Can't truncate to 0 bits");

935

936

if (width <= APINT_BITS_PER_WORD)

937

return APInt(width, getRawData()[0]);

938

939

APInt Result(getMemory(getNumWords(width)), width);

940

941

// Copy full words.

942

unsigned i;

943

for (i = 0; i != width / APINT_BITS_PER_WORD; i++)

944

Result.pVal[i] = pVal[i];

945

946

// Truncate and copy any partial word.

947

unsigned bits = (0 - width) % APINT_BITS_PER_WORD;

948

if (bits != 0)

949

Result.pVal[i] = pVal[i] << bits >> bits;

950

951

return Result;

952

}

953

954

// Sign extend to a new width.

955

APInt APInt::sext(unsigned width) const {

956

assert(width > BitWidth && "Invalid APInt SignExtend request");

957

958

if (width <= APINT_BITS_PER_WORD) {

959

uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);

960

val = (int64_t)val >> (width - BitWidth);

961

return APInt(width, val >> (APINT_BITS_PER_WORD - width));

962

}

963

964

APInt Result(getMemory(getNumWords(width)), width);

965

966

// Copy full words.

967

unsigned i;

968

uint64_t word = 0;

969

for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {

970

word = getRawData()[i];

971

Result.pVal[i] = word;

972

}

973

974

// Read and sign-extend any partial word.

975

unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;

976

if (bits != 0)

977

word = (int64_t)getRawData()[i] << bits >> bits;

978

else

979

word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);

980

981

// Write remaining full words.

982

for (; i != width / APINT_BITS_PER_WORD; i++) {

983

Result.pVal[i] = word;

984

word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);

985

}

986

987

// Write any partial word.

988

bits = (0 - width) % APINT_BITS_PER_WORD;

989

if (bits != 0)

990

Result.pVal[i] = word << bits >> bits;

991

992

return Result;

993

}

994

995

// Zero extend to a new width.

996

APInt APInt::zext(unsigned width) const {

997

assert(width > BitWidth && "Invalid APInt ZeroExtend request");

998

999

if (width <= APINT_BITS_PER_WORD)

1000

return APInt(width, VAL);

1001

1002

APInt Result(getMemory(getNumWords(width)), width);

1003

1004

// Copy words.

1005

unsigned i;

1006

for (i = 0; i != getNumWords(); i++)

1007

Result.pVal[i] = getRawData()[i];

1008

1009

// Zero remaining words.

1010

memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);

1011

1012

return Result;

1013

}

1014

1015

APInt APInt::zextOrTrunc(unsigned width) const {

1016

if (BitWidth < width)

1017

return zext(width);

1018

if (BitWidth > width)

1019

return trunc(width);

1020

return *this;

1021

}

1022

1023

APInt APInt::sextOrTrunc(unsigned width) const {

1024

if (BitWidth < width)

1025

return sext(width);

1026

if (BitWidth > width)

1027

return trunc(width);

1028

return *this;

1029

}

1030

1031

APInt APInt::zextOrSelf(unsigned width) const {

1032

if (BitWidth < width)

1033

return zext(width);

1034

return *this;

1035

}

1036

1037

APInt APInt::sextOrSelf(unsigned width) const {

1038

if (BitWidth < width)

1039

return sext(width);

1040

return *this;

1041

}

1042

1043

/// Arithmetic right-shift this APInt by shiftAmt.

1044

/// @brief Arithmetic right-shift function.

1045

APInt APInt::ashr(const APInt &shiftAmt) const {

1046

return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));

1047

}

1048

1049

/// Arithmetic right-shift this APInt by shiftAmt.

1050

/// @brief Arithmetic right-shift function.

1051

APInt APInt::ashr(unsigned shiftAmt) const {

1052

assert(shiftAmt <= BitWidth && "Invalid shift amount");

1053

// Handle a degenerate case

1054

if (shiftAmt == 0)

1055

return *this;

1056

1057

// Handle single word shifts with built-in ashr

1058

if (isSingleWord()) {

1059

if (shiftAmt == BitWidth)

1060

return APInt(BitWidth, 0); // undefined

1061

else {

1062

unsigned SignBit = APINT_BITS_PER_WORD - BitWidth;

1063

return APInt(BitWidth,

1064

(((int64_t(VAL) << SignBit) >> SignBit) >> shiftAmt));

1065

}

1066

}

1067

1068

// If all the bits were shifted out, the result is, technically, undefined.

1069

// We return -1 if it was negative, 0 otherwise. We check this early to avoid

1070

// issues in the algorithm below.

1071

if (shiftAmt == BitWidth) {

1072

if (isNegative())

1073

return APInt(BitWidth, -1ULL, true);

1074

else

1075

return APInt(BitWidth, 0);

1076

}

1077

1078

// Create some space for the result.

1079

uint64_t * val = new uint64_t[getNumWords()];

1080

1081

// Compute some values needed by the following shift algorithms

1082

unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word

1083

unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift

1084

unsigned breakWord = getNumWords() - 1 - offset; // last word affected

1085

unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?

1086

if (bitsInWord == 0)

1087

bitsInWord = APINT_BITS_PER_WORD;

1088

1089

// If we are shifting whole words, just move whole words

1090

if (wordShift == 0) {

1091

// Move the words containing significant bits

1092

for (unsigned i = 0; i <= breakWord; ++i)

1093

val[i] = pVal[i+offset]; // move whole word

1094

1095

// Adjust the top significant word for sign bit fill, if negative

1096

if (isNegative())

1097

if (bitsInWord < APINT_BITS_PER_WORD)

1098

val[breakWord] |= ~0ULL << bitsInWord; // set high bits

1099

} else {

1100

// Shift the low order words

1101

for (unsigned i = 0; i < breakWord; ++i) {

1102

// This combines the shifted corresponding word with the low bits from

1103

// the next word (shifted into this word's high bits).

1104

val[i] = (pVal[i+offset] >> wordShift) |

1105

(pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));

1106

}

1107

1108

// Shift the break word. In this case there are no bits from the next word

1109

// to include in this word.

1110

val[breakWord] = pVal[breakWord+offset] >> wordShift;

1111

1112

// Deal with sign extension in the break word, and possibly the word before

1113

// it.

1114

if (isNegative()) {

1115

if (wordShift > bitsInWord) {

1116

if (breakWord > 0)

1117

val[breakWord-1] |=

1118

~0ULL << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));

1119

val[breakWord] |= ~0ULL;

1120

} else

1121

val[breakWord] |= (~0ULL << (bitsInWord - wordShift));

1122

}

1123

}

1124

1125

// Remaining words are 0 or -1, just assign them.

1126

uint64_t fillValue = (isNegative() ? -1ULL : 0);

1127

for (unsigned i = breakWord+1; i < getNumWords(); ++i)

1128

val[i] = fillValue;

1129

APInt Result(val, BitWidth);

1130

Result.clearUnusedBits();

1131

return Result;

1132

}

1133

1134

/// Logical right-shift this APInt by shiftAmt.

1135

/// @brief Logical right-shift function.

1136

APInt APInt::lshr(const APInt &shiftAmt) const {

1137

return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));

1138

}

1139

1140

/// Logical right-shift this APInt by shiftAmt.

1141

/// @brief Logical right-shift function.

1142

APInt APInt::lshr(unsigned shiftAmt) const {

1143

if (isSingleWord()) {

1144

if (shiftAmt >= BitWidth)

1145

return APInt(BitWidth, 0);

1146

else

1147

return APInt(BitWidth, this->VAL >> shiftAmt);

1148

}

1149

1150

// If all the bits were shifted out, the result is 0. This avoids issues

1151

// with shifting by the size of the integer type, which produces undefined

1152

// results. We define these "undefined results" to always be 0.

1153

if (shiftAmt >= BitWidth)

1154

return APInt(BitWidth, 0);

1155

1156

// If none of the bits are shifted out, the result is *this. This avoids

1157

// issues with shifting by the size of the integer type, which produces

1158

// undefined results in the code below. This is also an optimization.

1159

if (shiftAmt == 0)

1160

return *this;

1161

1162

// Create some space for the result.

1163

uint64_t * val = new uint64_t[getNumWords()];

1164

1165

// If we are shifting less than a word, compute the shift with a simple carry

1166

if (shiftAmt < APINT_BITS_PER_WORD) {

1167

lshrNear(val, pVal, getNumWords(), shiftAmt);

1168

APInt Result(val, BitWidth);

1169

Result.clearUnusedBits();

1170

return Result;

1171

}

1172

1173

// Compute some values needed by the remaining shift algorithms

1174

unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;

1175

unsigned offset = shiftAmt / APINT_BITS_PER_WORD;

1176

1177

// If we are shifting whole words, just move whole words

1178

if (wordShift == 0) {

1179

for (unsigned i = 0; i < getNumWords() - offset; ++i)

1180

val[i] = pVal[i+offset];

1181

for (unsigned i = getNumWords()-offset; i < getNumWords(); i++)

1182

val[i] = 0;

1183

APInt Result(val, BitWidth);

1184

Result.clearUnusedBits();

1185

return Result;

1186

}

1187

1188

// Shift the low order words

1189

unsigned breakWord = getNumWords() - offset -1;

1190

for (unsigned i = 0; i < breakWord; ++i)

1191

val[i] = (pVal[i+offset] >> wordShift) |

1192

(pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));

1193

// Shift the break word.

1194

val[breakWord] = pVal[breakWord+offset] >> wordShift;

1195

1196

// Remaining words are 0

1197

for (unsigned i = breakWord+1; i < getNumWords(); ++i)

1198

val[i] = 0;

1199

APInt Result(val, BitWidth);

1200

Result.clearUnusedBits();

1201

return Result;

1202

}

1203

1204

/// Left-shift this APInt by shiftAmt.

1205

/// @brief Left-shift function.

1206

APInt APInt::shl(const APInt &shiftAmt) const {

1207

// It's undefined behavior in C to shift by BitWidth or greater.

1208

return shl((unsigned)shiftAmt.getLimitedValue(BitWidth));

1209

}

1210

1211

APInt APInt::shlSlowCase(unsigned shiftAmt) const {

1212

// If all the bits were shifted out, the result is 0. This avoids issues

1213

// with shifting by the size of the integer type, which produces undefined

1214

// results. We define these "undefined results" to always be 0.

1215

if (shiftAmt == BitWidth)

1216

return APInt(BitWidth, 0);

1217

1218

// If none of the bits are shifted out, the result is *this. This avoids a

1219

// lshr by the words size in the loop below which can produce incorrect

1220

// results. It also avoids the expensive computation below for a common case.

1221

if (shiftAmt == 0)

1222

return *this;

1223

1224

// Create some space for the result.

1225

uint64_t * val = new uint64_t[getNumWords()];

1226

1227

// If we are shifting less than a word, do it the easy way

1228

if (shiftAmt < APINT_BITS_PER_WORD) {

1229

uint64_t carry = 0;

1230

for (unsigned i = 0; i < getNumWords(); i++) {

1231

val[i] = pVal[i] << shiftAmt | carry;

1232

carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt);

1233

}

1234

APInt Result(val, BitWidth);

1235

Result.clearUnusedBits();

1236

return Result;

1237

}

1238

1239

// Compute some values needed by the remaining shift algorithms

1240

unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD;

1241

unsigned offset = shiftAmt / APINT_BITS_PER_WORD;

1242

1243

// If we are shifting whole words, just move whole words

1244

if (wordShift == 0) {

1245

for (unsigned i = 0; i < offset; i++)

1246

val[i] = 0;

1247

for (unsigned i = offset; i < getNumWords(); i++)

1248

val[i] = pVal[i-offset];

1249

APInt Result(val, BitWidth);

1250

Result.clearUnusedBits();

1251

return Result;

1252

}

1253

1254

// Copy whole words from this to Result.

1255

unsigned i = getNumWords() - 1;

1256

for (; i > offset; --i)

1257

val[i] = pVal[i-offset] << wordShift |

1258

pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift);

1259

val[offset] = pVal[0] << wordShift;

1260

for (i = 0; i < offset; ++i)

1261

val[i] = 0;

1262

APInt Result(val, BitWidth);

1263

Result.clearUnusedBits();

1264

return Result;

1265

}

1266

1267

APInt APInt::rotl(const APInt &rotateAmt) const {

1268

return rotl((unsigned)rotateAmt.getLimitedValue(BitWidth));

1269

}

1270

1271

APInt APInt::rotl(unsigned rotateAmt) const {

1272

rotateAmt %= BitWidth;

1273

if (rotateAmt == 0)

1274

return *this;

1275

return shl(rotateAmt) | lshr(BitWidth - rotateAmt);

1276

}

1277

1278

APInt APInt::rotr(const APInt &rotateAmt) const {

1279

return rotr((unsigned)rotateAmt.getLimitedValue(BitWidth));

1280

}

1281

1282

APInt APInt::rotr(unsigned rotateAmt) const {

1283

rotateAmt %= BitWidth;

1284

if (rotateAmt == 0)

1285

return *this;

1286

return lshr(rotateAmt) | shl(BitWidth - rotateAmt);

1287

}

1288

1289

// Square Root - this method computes and returns the square root of "this".

1290

// Three mechanisms are used for computation. For small values (<= 5 bits),

1291

// a table lookup is done. This gets some performance for common cases. For

1292

// values using less than 52 bits, the value is converted to double and then

1293

// the libc sqrt function is called. The result is rounded and then converted

1294

// back to a uint64_t which is then used to construct the result. Finally,

1295

// the Babylonian method for computing square roots is used.

1296

APInt APInt::sqrt() const {

1297

1298

// Determine the magnitude of the value.

1299

unsigned magnitude = getActiveBits();

1300

1301

// Use a fast table for some small values. This also gets rid of some

1302

// rounding errors in libc sqrt for small values.

1303

if (magnitude <= 5) {

1304

static const uint8_t results[32] = {

1305

/* 0 */ 0,

1306

/* 1- 2 */ 1, 1,

1307

/* 3- 6 */ 2, 2, 2, 2,

1308

/* 7-12 */ 3, 3, 3, 3, 3, 3,

1309

/* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,

1310

/* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,

1311

/* 31 */ 6

1312

};

1313

return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);

1314

}

1315

1316

// If the magnitude of the value fits in less than 52 bits (the precision of

1317

// an IEEE double precision floating point value), then we can use the

1318

// libc sqrt function which will probably use a hardware sqrt computation.

1319

// This should be faster than the algorithm below.

1320

if (magnitude < 52) {

1321

return APInt(BitWidth,

1322

uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));

1323

}

1324

1325

// Okay, all the short cuts are exhausted. We must compute it. The following

1326

// is a classical Babylonian method for computing the square root. This code

1327

// was adapted to APInt from a wikipedia article on such computations.

1328

// See http://www.wikipedia.org/ and go to the page named

1329

// Calculate_an_integer_square_root.

1330

unsigned nbits = BitWidth, i = 4;

1331

APInt testy(BitWidth, 16);

1332

APInt x_old(BitWidth, 1);

1333

APInt x_new(BitWidth, 0);

1334

APInt two(BitWidth, 2);

1335

1336

// Select a good starting value using binary logarithms.

1337

for (;; i += 2, testy = testy.shl(2))

1338

if (i >= nbits || this->ule(testy)) {

1339

x_old = x_old.shl(i / 2);

1340

break;

1341

}

1342

1343

// Use the Babylonian method to arrive at the integer square root:

1344

for (;;) {

1345

x_new = (this->udiv(x_old) + x_old).udiv(two);

1346

if (x_old.ule(x_new))

1347

break;

1348

x_old = x_new;

1349

}

1350

1351

// Make sure we return the closest approximation

1352

// NOTE: The rounding calculation below is correct. It will produce an

1353

// off-by-one discrepancy with results from pari/gp. That discrepancy has been

1354

// determined to be a rounding issue with pari/gp as it begins to use a

1355

// floating point representation after 192 bits. There are no discrepancies

1356

// between this algorithm and pari/gp for bit widths < 192 bits.

1357

APInt square(x_old * x_old);

1358

APInt nextSquare((x_old + 1) * (x_old +1));

1359

if (this->ult(square))

1360

return x_old;

1361

assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");

1362

APInt midpoint((nextSquare - square).udiv(two));

1363

APInt offset(*this - square);

1364

if (offset.ult(midpoint))

1365

return x_old;

1366

return x_old + 1;

1367

}

1368

1369

/// Computes the multiplicative inverse of this APInt for a given modulo. The

1370

/// iterative extended Euclidean algorithm is used to solve for this value,

1371

/// however we simplify it to speed up calculating only the inverse, and take

1372

/// advantage of div+rem calculations. We also use some tricks to avoid copying

1373

/// (potentially large) APInts around.

1374

APInt APInt::multiplicativeInverse(const APInt& modulo) const {

1375

assert(ult(modulo) && "This APInt must be smaller than the modulo");

1376

1377

// Using the properties listed at the following web page (accessed 06/21/08):

1378

// http://www.numbertheory.org/php/euclid.html

1379

// (especially the properties numbered 3, 4 and 9) it can be proved that

1380

// BitWidth bits suffice for all the computations in the algorithm implemented

1381

// below. More precisely, this number of bits suffice if the multiplicative

1382

// inverse exists, but may not suffice for the general extended Euclidean

1383

// algorithm.

1384

1385

APInt r[2] = { modulo, *this };

1386

APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };

1387

APInt q(BitWidth, 0);

1388

1389

unsigned i;

1390

for (i = 0; r[i^1] != 0; i ^= 1) {

1391

// An overview of the math without the confusing bit-flipping:

1392

// q = r[i-2] / r[i-1]

1393

// r[i] = r[i-2] % r[i-1]

1394

// t[i] = t[i-2] - t[i-1] * q

1395

udivrem(r[i], r[i^1], q, r[i]);

1396

t[i] -= t[i^1] * q;

1397

}

1398

1399

// If this APInt and the modulo are not coprime, there is no multiplicative

1400

// inverse, so return 0. We check this by looking at the next-to-last

1401

// remainder, which is the gcd(*this,modulo) as calculated by the Euclidean

1402

// algorithm.

1403

if (r[i] != 1)

1404

return APInt(BitWidth, 0);

1405

1406

// The next-to-last t is the multiplicative inverse. However, we are

1407

// interested in a positive inverse. Calcuate a positive one from a negative

1408

// one if necessary. A simple addition of the modulo suffices because

1409

// abs(t[i]) is known to be less than *this/2 (see the link above).

1410

return t[i].isNegative() ? t[i] + modulo : t[i];

1411

}

1412

1413

/// Calculate the magic numbers required to implement a signed integer division

1414

/// by a constant as a sequence of multiplies, adds and shifts. Requires that

1415

/// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.

1416

/// Warren, Jr., chapter 10.

1417

APInt::ms APInt::magic() const {

1418

const APInt& d = *this;

1419

unsigned p;

1420

APInt ad, anc, delta, q1, r1, q2, r2, t;

1421

APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());

1422

struct ms mag;

1423

1424

ad = d.abs();

1425

t = signedMin + (d.lshr(d.getBitWidth() - 1));

1426

anc = t - 1 - t.urem(ad); // absolute value of nc

1427

p = d.getBitWidth() - 1; // initialize p

1428

q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)

1429

r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))

1430

q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)

1431

r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))

1432

do {

1433

p = p + 1;

1434

q1 = q1<<1; // update q1 = 2p/abs(nc)

1435

r1 = r1<<1; // update r1 = rem(2p/abs(nc))

1436

if (r1.uge(anc)) { // must be unsigned comparison

1437

q1 = q1 + 1;

1438

r1 = r1 - anc;

1439

}

1440

q2 = q2<<1; // update q2 = 2p/abs(d)

1441

r2 = r2<<1; // update r2 = rem(2p/abs(d))

1442

if (r2.uge(ad)) { // must be unsigned comparison

1443

q2 = q2 + 1;

1444

r2 = r2 - ad;

1445

}

1446

delta = ad - r2;

1447

} while (q1.ult(delta) || (q1 == delta && r1 == 0));

1448

1449

mag.m = q2 + 1;

1450

if (d.isNegative()) mag.m = -mag.m; // resulting magic number

1451

mag.s = p - d.getBitWidth(); // resulting shift

1452

return mag;

1453

}

1454

1455

/// Calculate the magic numbers required to implement an unsigned integer

1456

/// division by a constant as a sequence of multiplies, adds and shifts.

1457

/// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry

1458

/// S. Warren, Jr., chapter 10.

1459

/// LeadingZeros can be used to simplify the calculation if the upper bits

1460

/// of the divided value are known zero.

1461

APInt::mu APInt::magicu(unsigned LeadingZeros) const {

1462

const APInt& d = *this;

1463

unsigned p;

1464

APInt nc, delta, q1, r1, q2, r2;

1465

struct mu magu;

1466

magu.a = 0; // initialize "add" indicator

1467

APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);

1468

APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());

1469

APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());

1470

1471

nc = allOnes - (allOnes - d).urem(d);

1472

p = d.getBitWidth() - 1; // initialize p

1473

q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc

1474

r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)

1475

q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d

1476

r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)

1477

do {

1478

p = p + 1;

1479

if (r1.uge(nc - r1)) {

1480

q1 = q1 + q1 + 1; // update q1

1481

r1 = r1 + r1 - nc; // update r1

1482

}

1483

else {

1484

q1 = q1+q1; // update q1

1485

r1 = r1+r1; // update r1

1486

}

1487

if ((r2 + 1).uge(d - r2)) {

1488

if (q2.uge(signedMax)) magu.a = 1;

1489

q2 = q2+q2 + 1; // update q2

1490

r2 = r2+r2 + 1 - d; // update r2

1491

}

1492

else {

1493

if (q2.uge(signedMin)) magu.a = 1;

1494

q2 = q2+q2; // update q2

1495

r2 = r2+r2 + 1; // update r2

1496

}

1497

delta = d - 1 - r2;

1498

} while (p < d.getBitWidth()*2 &&

1499

(q1.ult(delta) || (q1 == delta && r1 == 0)));

1500

magu.m = q2 + 1; // resulting magic number

1501

magu.s = p - d.getBitWidth(); // resulting shift

1502

return magu;

1503

}

1504

1505

/// Implementation of Knuth's Algorithm D (Division of nonnegative integers)

1506

/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The

1507

/// variables here have the same names as in the algorithm. Comments explain

1508

/// the algorithm and any deviation from it.

1509

static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,

1510

unsigned m, unsigned n) {

1511

assert(u && "Must provide dividend");

1512

assert(v && "Must provide divisor");

1513

assert(q && "Must provide quotient");

1514

assert(u != v && u != q && v != q && "Must use different memory");

1515

assert(n>1 && "n must be > 1");

1516

1517

// b denotes the base of the number system. In our case b is 2^32.

1518

LLVM_CONSTEXPR uint64_t b = uint64_t(1) << 32;

1519

1520

DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');

1521

DEBUG(dbgs() << "KnuthDiv: original:");

1522

DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);

1523

DEBUG(dbgs() << " by");

1524

DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);

1525

DEBUG(dbgs() << '\n');

1526

// D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of

1527

// u and v by d. Note that we have taken Knuth's advice here to use a power

1528

// of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of

1529

// 2 allows us to shift instead of multiply and it is easy to determine the

1530

// shift amount from the leading zeros. We are basically normalizing the u

1531

// and v so that its high bits are shifted to the top of v's range without

1532

// overflow. Note that this can require an extra word in u so that u must

1533

// be of length m+n+1.

1534

unsigned shift = countLeadingZeros(v[n-1]);

1535

unsigned v_carry = 0;

1536

unsigned u_carry = 0;

1537

if (shift) {

1538

for (unsigned i = 0; i < m+n; ++i) {

1539

unsigned u_tmp = u[i] >> (32 - shift);

1540

u[i] = (u[i] << shift) | u_carry;

1541

u_carry = u_tmp;

1542

}

1543

for (unsigned i = 0; i < n; ++i) {

1544

unsigned v_tmp = v[i] >> (32 - shift);

1545

v[i] = (v[i] << shift) | v_carry;

1546

v_carry = v_tmp;

1547

}

1548

}

1549

u[m+n] = u_carry;

1550

1551

DEBUG(dbgs() << "KnuthDiv: normal:");

1552

DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);

1553

DEBUG(dbgs() << " by");

1554

DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);

1555

DEBUG(dbgs() << '\n');

1556

1557

// D2. [Initialize j.] Set j to m. This is the loop counter over the places.

1558

int j = m;

1559

do {

1560

DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');

1561

// D3. [Calculate q'.].

1562

// Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')

1563

// Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')

1564

// Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease

1565

// qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test

1566

// on v[n-2] determines at high speed most of the cases in which the trial

1567

// value qp is one too large, and it eliminates all cases where qp is two

1568

// too large.

1569

uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);

1570

DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');

1571

uint64_t qp = dividend / v[n-1];

1572

uint64_t rp = dividend % v[n-1];

1573

if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {

1574

qp--;

1575

rp += v[n-1];

1576

if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))

1577

qp--;

1578

}

1579

DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');

1580

1581

// D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with

1582

// (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation

1583

// consists of a simple multiplication by a one-place number, combined with

1584

// a subtraction.

1585

// The digits (u[j+n]...u[j]) should be kept positive; if the result of

1586

// this step is actually negative, (u[j+n]...u[j]) should be left as the

1587

// true value plus b**(n+1), namely as the b's complement of

1588

// the true value, and a "borrow" to the left should be remembered.

1589

int64_t borrow = 0;

1590

for (unsigned i = 0; i < n; ++i) {

1591

uint64_t p = uint64_t(qp) * uint64_t(v[i]);

1592

int64_t subres = int64_t(u[j+i]) - borrow - (unsigned)p;

1593

u[j+i] = (unsigned)subres;

1594

borrow = (p >> 32) - (subres >> 32);

1595

DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]

1596

<< ", borrow = " << borrow << '\n');

1597

}

1598

bool isNeg = u[j+n] < borrow;

1599

u[j+n] -= (unsigned)borrow;

1600

1601

DEBUG(dbgs() << "KnuthDiv: after subtraction:");

1602

DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);

1603

DEBUG(dbgs() << '\n');

1604

1605

// D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was

1606

// negative, go to step D6; otherwise go on to step D7.

1607

q[j] = (unsigned)qp;

1608

if (isNeg) {

1609

// D6. [Add back]. The probability that this step is necessary is very

1610

// small, on the order of only 2/b. Make sure that test data accounts for

1611

// this possibility. Decrease q[j] by 1

1612

q[j]--;

1613

// and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).

1614

// A carry will occur to the left of u[j+n], and it should be ignored

1615

// since it cancels with the borrow that occurred in D4.

1616

bool carry = false;

1617

for (unsigned i = 0; i < n; i++) {

1618

unsigned limit = std::min(u[j+i],v[i]);

1619

u[j+i] += v[i] + carry;

1620

carry = u[j+i] < limit || (carry && u[j+i] == limit);

1621

}

1622

u[j+n] += carry;

1623

}

1624

DEBUG(dbgs() << "KnuthDiv: after correction:");

1625

DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);

1626

DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');

1627

1628

// D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.

1629

} while (--j >= 0);

1630

1631

DEBUG(dbgs() << "KnuthDiv: quotient:");

1632

DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);

1633

DEBUG(dbgs() << '\n');

1634

1635

// D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired

1636

// remainder may be obtained by dividing u[...] by d. If r is non-null we

1637

// compute the remainder (urem uses this).

1638

if (r) {

1639

// The value d is expressed by the "shift" value above since we avoided

1640

// multiplication by d by using a shift left. So, all we have to do is

1641

// shift right here. In order to mak

1642

if (shift) {

1643

unsigned carry = 0;

1644

DEBUG(dbgs() << "KnuthDiv: remainder:");

1645

for (int i = n-1; i >= 0; i--) {

1646

r[i] = (u[i] >> shift) | carry;

1647

carry = u[i] << (32 - shift);

1648

DEBUG(dbgs() << " " << r[i]);

1649

}

1650

} else {

1651

for (int i = n-1; i >= 0; i--) {

1652

r[i] = u[i];

1653

DEBUG(dbgs() << " " << r[i]);

1654

}

1655

}

1656

DEBUG(dbgs() << '\n');

1657

}

1658

DEBUG(dbgs() << '\n');

1659

}

1660

1661

void APInt::divide(const APInt LHS, unsigned lhsWords,

1662

const APInt &RHS, unsigned rhsWords,

1663

APInt *Quotient, APInt *Remainder)

1664

{

1665

assert(lhsWords >= rhsWords && "Fractional result");

1666

1667

// First, compose the values into an array of 32-bit words instead of

1668

// 64-bit words. This is a necessity of both the "short division" algorithm

1669

// and the Knuth "classical algorithm" which requires there to be native

1670

// operations for +, -, and * on an m bit value with an m*2 bit result. We

1671

// can't use 64-bit operands here because we don't have native results of

1672

// 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't

1673

// work on large-endian machines.

1674

uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);

1675

unsigned n = rhsWords * 2;

1676

unsigned m = (lhsWords * 2) - n;

1677

1678

// Allocate space for the temporary values we need either on the stack, if

1679

// it will fit, or on the heap if it won't.

1680

unsigned SPACE[128];

1681

unsigned *U = nullptr;

1682

unsigned *V = nullptr;

1683

unsigned *Q = nullptr;

1684

unsigned *R = nullptr;

1685

if ((Remainder?4:3)*n+2*m+1 <= 128) {

1686

U = &SPACE[0];

1687

V = &SPACE[m+n+1];

1688

Q = &SPACE[(m+n+1) + n];

1689

if (Remainder)

1690

R = &SPACE[(m+n+1) + n + (m+n)];

1691

} else {

1692

U = new unsigned[m + n + 1];

1693

V = new unsigned[n];

1694

Q = new unsigned[m+n];

1695

if (Remainder)

1696

R = new unsigned[n];

1697

}

1698

1699

// Initialize the dividend

1700

memset(U, 0, (m+n+1)*sizeof(unsigned));

1701

for (unsigned i = 0; i < lhsWords; ++i) {

1702

uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);

1703

U[i * 2] = (unsigned)(tmp & mask);

1704

U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));

1705

}

1706

U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.

1707

1708

// Initialize the divisor

1709

memset(V, 0, (n)*sizeof(unsigned));

1710

for (unsigned i = 0; i < rhsWords; ++i) {

1711

uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);

1712

V[i * 2] = (unsigned)(tmp & mask);

1713

V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));

1714

}

1715

1716

// initialize the quotient and remainder

1717

memset(Q, 0, (m+n) * sizeof(unsigned));

1718

if (Remainder)

1719

memset(R, 0, n * sizeof(unsigned));

1720

1721

// Now, adjust m and n for the Knuth division. n is the number of words in

1722

// the divisor. m is the number of words by which the dividend exceeds the

1723

// divisor (i.e. m+n is the length of the dividend). These sizes must not

1724

// contain any zero words or the Knuth algorithm fails.

1725

for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {

1726

n--;

1727

m++;

1728

}

1729

for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)

1730

m--;

1731

1732

// If we're left with only a single word for the divisor, Knuth doesn't work

1733

// so we implement the short division algorithm here. This is much simpler

1734

// and faster because we are certain that we can divide a 64-bit quantity

1735

// by a 32-bit quantity at hardware speed and short division is simply a

1736

// series of such operations. This is just like doing short division but we

1737

// are using base 2^32 instead of base 10.

1738

assert(n != 0 && "Divide by zero?");

1739

if (n == 1) {

1740

unsigned divisor = V[0];

1741

unsigned remainder = 0;

1742

for (int i = m+n-1; i >= 0; i--) {

1743

uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];

1744

if (partial_dividend == 0) {

1745

Q[i] = 0;

1746

remainder = 0;

1747

} else if (partial_dividend < divisor) {

1748

Q[i] = 0;

1749

remainder = (unsigned)partial_dividend;

1750

} else if (partial_dividend == divisor) {

1751

Q[i] = 1;

1752

remainder = 0;

1753

} else {

1754

Q[i] = (unsigned)(partial_dividend / divisor);

1755

remainder = (unsigned)(partial_dividend - (Q[i] * divisor));

1756

}

1757

}

1758

if (R)

1759

R[0] = remainder;

1760

} else {

1761

// Now we're ready to invoke the Knuth classical divide algorithm. In this

1762

// case n > 1.

1763

KnuthDiv(U, V, Q, R, m, n);

1764

}

1765

1766

// If the caller wants the quotient

1767

if (Quotient) {

1768

// Set up the Quotient value's memory.

1769

if (Quotient->BitWidth != LHS.BitWidth) {

1770

if (Quotient->isSingleWord())

1771

Quotient->VAL = 0;

1772

else

1773

delete [] Quotient->pVal;

1774

Quotient->BitWidth = LHS.BitWidth;

1775

if (!Quotient->isSingleWord())

1776

Quotient->pVal = getClearedMemory(Quotient->getNumWords());

1777

} else

1778

Quotient->clearAllBits();

1779

1780

// The quotient is in Q. Reconstitute the quotient into Quotient's low

1781

// order words.

1782

// This case is currently dead as all users of divide() handle trivial cases

1783

// earlier.

1784

if (lhsWords == 1) {

1785

uint64_t tmp =

1786

uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));

1787

if (Quotient->isSingleWord())

1788

Quotient->VAL = tmp;

1789

else

1790

Quotient->pVal[0] = tmp;

1791

} else {

1792

assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");

1793

for (unsigned i = 0; i < lhsWords; ++i)

1794

Quotient->pVal[i] =

1795

uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));

1796

}

1797

}

1798

1799

// If the caller wants the remainder

1800

if (Remainder) {

1801

// Set up the Remainder value's memory.

1802

if (Remainder->BitWidth != RHS.BitWidth) {

1803

if (Remainder->isSingleWord())

1804

Remainder->VAL = 0;

1805

else

1806

delete [] Remainder->pVal;

1807

Remainder->BitWidth = RHS.BitWidth;

1808

if (!Remainder->isSingleWord())

1809

Remainder->pVal = getClearedMemory(Remainder->getNumWords());

1810

} else

1811

Remainder->clearAllBits();

1812

1813

// The remainder is in R. Reconstitute the remainder into Remainder's low

1814

// order words.

1815

if (rhsWords == 1) {

1816

uint64_t tmp =

1817

uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));

1818

if (Remainder->isSingleWord())

1819

Remainder->VAL = tmp;

1820

else

1821

Remainder->pVal[0] = tmp;

1822

} else {

1823

assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");

1824

for (unsigned i = 0; i < rhsWords; ++i)

1825

Remainder->pVal[i] =

1826

uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));

1827

}

1828

}

1829

1830

// Clean up the memory we allocated.

1831

if (U != &SPACE[0]) {

1832

delete [] U;

1833

delete [] V;

1834

delete [] Q;

1835

delete [] R;

1836

}

1837

}

1838

1839

APInt APInt::udiv(const APInt& RHS) const {

1840

assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

1841

1842

// First, deal with the easy case

1843

if (isSingleWord()) {

1844

assert(RHS.VAL != 0 && "Divide by zero?");

1845

return APInt(BitWidth, VAL / RHS.VAL);

1846

}

1847

1848

// Get some facts about the LHS and RHS number of bits and words

1849

unsigned rhsBits = RHS.getActiveBits();

1850

unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);

1851

assert(rhsWords && "Divided by zero???");

1852

unsigned lhsBits = this->getActiveBits();

1853

unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);

1854

1855

// Deal with some degenerate cases

1856

if (!lhsWords)

1857

// 0 / X ===> 0

1858

return APInt(BitWidth, 0);

1859

else if (lhsWords < rhsWords || this->ult(RHS)) {

1860

// X / Y ===> 0, iff X < Y

1861

return APInt(BitWidth, 0);

1862

} else if (*this == RHS) {

1863

// X / X ===> 1

1864

return APInt(BitWidth, 1);

1865

} else if (lhsWords == 1 && rhsWords == 1) {

1866

// All high words are zero, just use native divide

1867

return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);

1868

}

1869

1870

// We have to compute it the hard way. Invoke the Knuth divide algorithm.

1871

APInt Quotient(1,0); // to hold result.

1872

divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr);

1873

return Quotient;

1874

}

1875

1876

APInt APInt::sdiv(const APInt &RHS) const {

1877

if (isNegative()) {

1878

if (RHS.isNegative())

1879

return (-(*this)).udiv(-RHS);

1880

return -((-(*this)).udiv(RHS));

1881

}

1882

if (RHS.isNegative())

1883

return -(this->udiv(-RHS));

1884

return this->udiv(RHS);

1885

}

1886

1887

APInt APInt::urem(const APInt& RHS) const {

1888

assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");

1889

if (isSingleWord()) {

1890

assert(RHS.VAL != 0 && "Remainder by zero?");

1891

return APInt(BitWidth, VAL % RHS.VAL);

1892

}

1893

1894

// Get some facts about the LHS

1895

unsigned lhsBits = getActiveBits();

1896

unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);

1897

1898

// Get some facts about the RHS

1899

unsigned rhsBits = RHS.getActiveBits();

1900

unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);

1901

assert(rhsWords && "Performing remainder operation by zero ???");

1902

1903

// Check the degenerate cases

1904

if (lhsWords == 0) {

1905

// 0 % Y ===> 0

1906

return APInt(BitWidth, 0);

1907

} else if (lhsWords < rhsWords || this->ult(RHS)) {

1908

// X % Y ===> X, iff X < Y

1909

return *this;

1910

} else if (*this == RHS) {

1911

// X % X == 0;

1912

return APInt(BitWidth, 0);

1913

} else if (lhsWords == 1) {

1914

// All high words are zero, just use native remainder

1915

return APInt(BitWidth, pVal[0] % RHS.pVal[0]);

1916

}

1917

1918

// We have to compute it the hard way. Invoke the Knuth divide algorithm.

1919

APInt Remainder(1,0);

1920

divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder);

1921

return Remainder;

1922

}

1923

1924

APInt APInt::srem(const APInt &RHS) const {

1925

if (isNegative()) {

1926

if (RHS.isNegative())

1927

return -((-(*this)).urem(-RHS));

1928

return -((-(*this)).urem(RHS));

1929

}

1930

if (RHS.isNegative())

1931

return this->urem(-RHS);

1932

return this->urem(RHS);

1933

}

1934

1935

void APInt::udivrem(const APInt &LHS, const APInt &RHS,

1936

APInt &Quotient, APInt &Remainder) {

1937

assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");

1938

1939

// First, deal with the easy case

1940

if (LHS.isSingleWord()) {

1941

assert(RHS.VAL != 0 && "Divide by zero?");

1942

uint64_t QuotVal = LHS.VAL / RHS.VAL;

1943

uint64_t RemVal = LHS.VAL % RHS.VAL;

1944

Quotient = APInt(LHS.BitWidth, QuotVal);

1945

Remainder = APInt(LHS.BitWidth, RemVal);

1946

return;

1947

}

1948

1949

// Get some size facts about the dividend and divisor

1950

unsigned lhsBits = LHS.getActiveBits();

1951

unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);

1952

unsigned rhsBits = RHS.getActiveBits();

1953

unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);

1954

1955

// Check the degenerate cases

1956

if (lhsWords == 0) {

1957

Quotient = 0; // 0 / Y ===> 0

1958

Remainder = 0; // 0 % Y ===> 0

1959

return;

1960

}

1961

1962

if (lhsWords < rhsWords || LHS.ult(RHS)) {

1963

Remainder = LHS; // X % Y ===> X, iff X < Y

1964

Quotient = 0; // X / Y ===> 0, iff X < Y

1965

return;

1966

}

1967

1968

if (LHS == RHS) {

1969

Quotient = 1; // X / X ===> 1

1970

Remainder = 0; // X % X ===> 0;

1971

return;

1972

}

1973

1974

if (lhsWords == 1 && rhsWords == 1) {

1975

// There is only one word to consider so use the native versions.

1976

uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];

1977

uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];

1978

Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);

1979

Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);

1980

return;

1981

}

1982

1983

// Okay, lets do it the long way

1984

divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);

1985

}

1986

1987

void APInt::sdivrem(const APInt &LHS, const APInt &RHS,

1988

APInt &Quotient, APInt &Remainder) {

1989

if (LHS.isNegative()) {

1990

if (RHS.isNegative())

1991

APInt::udivrem(-LHS, -RHS, Quotient, Remainder);

1992

else {

1993

APInt::udivrem(-LHS, RHS, Quotient, Remainder);

1994

Quotient = -Quotient;

1995

}

1996

Remainder = -Remainder;

1997

} else if (RHS.isNegative()) {

1998

APInt::udivrem(LHS, -RHS, Quotient, Remainder);

1999

Quotient = -Quotient;

2000

} else {

2001

APInt::udivrem(LHS, RHS, Quotient, Remainder);

2002

}

2003

}

2004

2005

APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {

2006

APInt Res = *this+RHS;

2007

Overflow = isNonNegative() == RHS.isNonNegative() &&

2008

Res.isNonNegative() != isNonNegative();

2009

return Res;

2010

}

2011

2012

APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {

2013

APInt Res = *this+RHS;

2014

Overflow = Res.ult(RHS);

2015

return Res;

2016

}

2017

2018

APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {

2019

APInt Res = *this - RHS;

2020

Overflow = isNonNegative() != RHS.isNonNegative() &&

2021

Res.isNonNegative() != isNonNegative();

2022

return Res;

2023

}

2024

2025

APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {

2026

APInt Res = *this-RHS;

2027

Overflow = Res.ugt(*this);

2028

return Res;

2029

}

2030

2031

APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {

2032

// MININT/-1 --> overflow.

2033

Overflow = isMinSignedValue() && RHS.isAllOnesValue();

2034

return sdiv(RHS);

2035

}

2036

2037

APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {

2038

APInt Res = *this * RHS;

2039

2040

if (*this != 0 && RHS != 0)

2041

Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;

2042

else

2043

Overflow = false;

2044

return Res;

2045

}

2046

2047

APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {

2048

APInt Res = *this * RHS;

2049

2050

if (*this != 0 && RHS != 0)

2051

Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;

2052

else

2053

Overflow = false;

2054

return Res;

2055

}

2056

2057

APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {

2058

Overflow = ShAmt.uge(getBitWidth());

2059

if (Overflow)

2060

return APInt(BitWidth, 0);

2061

2062

if (isNonNegative()) // Don't allow sign change.

2063

Overflow = ShAmt.uge(countLeadingZeros());

2064

else

2065

Overflow = ShAmt.uge(countLeadingOnes());

2066

2067

return *this << ShAmt;

2068

}

2069

2070

APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {

2071

Overflow = ShAmt.uge(getBitWidth());

2072

if (Overflow)

2073

return APInt(BitWidth, 0);

2074

2075

Overflow = ShAmt.ugt(countLeadingZeros());

2076

2077

return *this << ShAmt;

2078

}

2079

2080

2081

2082

2083

void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {

2084

// Check our assumptions here

2085

assert(!str.empty() && "Invalid string length");

2086

assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||

2087

radix == 36) &&

2088

"Radix should be 2, 8, 10, 16, or 36!");

2089

2090

StringRef::iterator p = str.begin();

2091

size_t slen = str.size();

2092

bool isNeg = *p == '-';

2093

if (*p == '-' || *p == '+') {

2094

p++;

2095

slen--;

2096

assert(slen && "String is only a sign, needs a value.");

2097

}

2098

assert((slen <= numbits || radix != 2) && "Insufficient bit width");

2099

assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");

2100

assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");

2101

assert((((slen-1)*64)/22 <= numbits || radix != 10) &&

2102

"Insufficient bit width");

2103

2104

// Allocate memory

2105

if (!isSingleWord())

2106

pVal = getClearedMemory(getNumWords());

2107

2108

// Figure out if we can shift instead of multiply

2109

unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);

2110

2111

// Set up an APInt for the digit to add outside the loop so we don't

2112

// constantly construct/destruct it.

2113

APInt apdigit(getBitWidth(), 0);

2114

APInt apradix(getBitWidth(), radix);

2115

2116

// Enter digit traversal loop

2117

for (StringRef::iterator e = str.end(); p != e; ++p) {

2118

unsigned digit = getDigit(*p, radix);

2119

assert(digit < radix && "Invalid character in digit string");

2120

2121

// Shift or multiply the value by the radix

2122

if (slen > 1) {

2123

if (shift)

2124

*this <<= shift;

2125

else

2126

*this *= apradix;

2127

}

2128

2129

// Add in the digit we just interpreted

2130

if (apdigit.isSingleWord())

2131

apdigit.VAL = digit;

2132

else

2133

apdigit.pVal[0] = digit;

2134

*this += apdigit;

2135

}

2136

// If its negative, put it in two's complement form

2137

if (isNeg) {

2138

--(*this);

2139

this->flipAllBits();

2140

}

2141

}

2142

2143

void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,

2144

bool Signed, bool formatAsCLiteral) const {

2145

assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||

2146

Radix == 36) &&

2147

"Radix should be 2, 8, 10, 16, or 36!");

2148

2149

const char *Prefix = "";

2150

if (formatAsCLiteral) {

2151

switch (Radix) {

2152

case 2:

2153

// Binary literals are a non-standard extension added in gcc 4.3:

2154

// http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html

2155

Prefix = "0b";

2156

break;

2157

case 8:

2158

Prefix = "0";

2159

break;

2160

case 10:

2161

break; // No prefix

2162

case 16:

2163

Prefix = "0x";

2164

break;

2165

default:

2166

llvm_unreachable("Invalid radix!");

2167

}

2168

}

2169

2170

// First, check for a zero value and just short circuit the logic below.

2171

if (*this == 0) {

2172

while (*Prefix) {

2173

Str.push_back(*Prefix);

2174

++Prefix;

2175

};

2176

Str.push_back('0');

2177

return;

2178

}

2179

2180

static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

2181

2182

if (isSingleWord()) {

2183

char Buffer[65];

2184

char *BufPtr = Buffer+65;

2185

2186

uint64_t N;

2187

if (!Signed) {

2188

N = getZExtValue();

2189

} else {

2190

int64_t I = getSExtValue();

2191

if (I >= 0) {

2192

N = I;

2193

} else {

2194

Str.push_back('-');

2195

N = -(uint64_t)I;

2196

}

2197

}

2198

2199

while (*Prefix) {

2200

Str.push_back(*Prefix);

2201

++Prefix;

2202

};

2203

2204

while (N) {

2205

*--BufPtr = Digits[N % Radix];

2206

N /= Radix;

2207

}

2208

Str.append(BufPtr, Buffer+65);

2209

return;

2210

}

2211

2212

APInt Tmp(*this);

2213

2214

if (Signed && isNegative()) {

2215

// They want to print the signed version and it is a negative value

2216

// Flip the bits and add one to turn it into the equivalent positive

2217

// value and put a '-' in the result.

2218

Tmp.flipAllBits();

2219

++Tmp;

2220

Str.push_back('-');

2221

}

2222

2223

while (*Prefix) {

2224

Str.push_back(*Prefix);

2225

++Prefix;

2226

};

2227

2228

// We insert the digits backward, then reverse them to get the right order.

2229

unsigned StartDig = Str.size();

2230

2231

// For the 2, 8 and 16 bit cases, we can just shift instead of divide

2232

// because the number of bits per digit (1, 3 and 4 respectively) divides

2233

// equaly. We just shift until the value is zero.

2234

if (Radix == 2 || Radix == 8 || Radix == 16) {

2235

// Just shift tmp right for each digit width until it becomes zero

2236

unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));

2237

unsigned MaskAmt = Radix - 1;

2238

2239

while (Tmp != 0) {

2240

unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;

2241

Str.push_back(Digits[Digit]);

2242

Tmp = Tmp.lshr(ShiftAmt);

2243

}

2244

} else {

2245

APInt divisor(Radix == 10? 4 : 8, Radix);

2246

while (Tmp != 0) {

2247

APInt APdigit(1, 0);

2248

APInt tmp2(Tmp.getBitWidth(), 0);

2249

divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,

2250

&APdigit);

2251

unsigned Digit = (unsigned)APdigit.getZExtValue();

2252

assert(Digit < Radix && "divide failed");

2253

Str.push_back(Digits[Digit]);

2254

Tmp = tmp2;

2255

}

2256

}

2257

2258

// Reverse the digits before returning.

2259

std::reverse(Str.begin()+StartDig, Str.end());

2260

}

2261

2262

/// Returns the APInt as a std::string. Note that this is an inefficient method.

2263

/// It is better to pass in a SmallVector/SmallString to the methods above.

2264

std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {

2265

SmallString<40> S;

2266

toString(S, Radix, Signed, /* formatAsCLiteral = */false);

2267

return S.str();

2268

}

2269

2270

2271

void APInt::dump() const {

2272

SmallString<40> S, U;

2273

this->toStringUnsigned(U);

2274

this->toStringSigned(S);

2275

dbgs() << "APInt(" << BitWidth << "b, "

2276

<< U << "u " << S << "s)";

2277

}

2278

2279

void APInt::print(raw_ostream &OS, bool isSigned) const {

2280

SmallString<40> S;

2281

this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);

2282

OS << S;

2283

}

2284

2285

// This implements a variety of operations on a representation of

2286

// arbitrary precision, two's-complement, bignum integer values.

2287

2288

// Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe

2289

// and unrestricting assumption.

2290

static_assert(integerPartWidth % 2 == 0, "Part width must be divisible by 2!");

2291

2292

/* Some handy functions local to this file. */

2293

namespace {

2294

2295

/* Returns the integer part with the least significant BITS set.

2296

BITS cannot be zero. */

2297

static inline integerPart

2298

lowBitMask(unsigned int bits)

2299

{

2300

assert(bits != 0 && bits <= integerPartWidth);

2301

2302

return ~(integerPart) 0 >> (integerPartWidth - bits);

2303

}

2304

2305

/* Returns the value of the lower half of PART. */

2306

static inline integerPart

2307

lowHalf(integerPart part)

2308

{

2309

return part & lowBitMask(integerPartWidth / 2);

2310

}

2311

2312

/* Returns the value of the upper half of PART. */

2313

static inline integerPart

2314

highHalf(integerPart part)

2315

{

2316

return part >> (integerPartWidth / 2);

2317

}

2318

2319

/* Returns the bit number of the most significant set bit of a part.

2320

If the input number has no bits set -1U is returned. */

2321

static unsigned int

2322

partMSB(integerPart value)

2323

{

2324

return findLastSet(value, ZB_Max);

2325

}

2326

2327

/* Returns the bit number of the least significant set bit of a

2328

part. If the input number has no bits set -1U is returned. */

2329

static unsigned int

2330

partLSB(integerPart value)

2331

{

2332

return findFirstSet(value, ZB_Max);

2333

}

2334

}

2335

2336

/* Sets the least significant part of a bignum to the input value, and

2337

zeroes out higher parts. */

2338

void

2339

APInt::tcSet(integerPart *dst, integerPart part, unsigned int parts)

2340

{

2341

unsigned int i;

2342

2343

assert(parts > 0);

2344

2345

dst[0] = part;

2346

for (i = 1; i < parts; i++)

2347

dst[i] = 0;

2348

}

2349

2350

/* Assign one bignum to another. */

2351

void

2352

APInt::tcAssign(integerPart *dst, const integerPart *src, unsigned int parts)

2353

{

2354

unsigned int i;

2355

2356

for (i = 0; i < parts; i++)

2357

dst[i] = src[i];

2358

}

2359

2360

/* Returns true if a bignum is zero, false otherwise. */

2361

bool

2362

APInt::tcIsZero(const integerPart *src, unsigned int parts)

2363

{

2364

unsigned int i;

2365

2366

for (i = 0; i < parts; i++)

2367

if (src[i])

2368

return false;

2369

2370

return true;

2371

}

2372

2373

/* Extract the given bit of a bignum; returns 0 or 1. */

2374

int

2375

APInt::tcExtractBit(const integerPart *parts, unsigned int bit)

2376

{

2377

return (parts[bit / integerPartWidth] &

2378

((integerPart) 1 << bit % integerPartWidth)) != 0;

2379

}

2380

2381

/* Set the given bit of a bignum. */

2382

void

2383

APInt::tcSetBit(integerPart *parts, unsigned int bit)

2384

{

2385

parts[bit / integerPartWidth] |= (integerPart) 1 << (bit % integerPartWidth);

2386

}

2387

2388

/* Clears the given bit of a bignum. */

2389

void

2390

APInt::tcClearBit(integerPart *parts, unsigned int bit)

2391

{

2392

parts[bit / integerPartWidth] &=

2393

~((integerPart) 1 << (bit % integerPartWidth));

2394

}

2395

2396

/* Returns the bit number of the least significant set bit of a

2397

number. If the input number has no bits set -1U is returned. */

2398

unsigned int

2399

APInt::tcLSB(const integerPart *parts, unsigned int n)

2400

{

2401

unsigned int i, lsb;

2402

2403

for (i = 0; i < n; i++) {

2404

if (parts[i] != 0) {

2405

lsb = partLSB(parts[i]);

2406

2407

return lsb + i * integerPartWidth;

2408

}

2409

}

2410

2411

return -1U;

2412

}

2413

2414

/* Returns the bit number of the most significant set bit of a number.

2415

If the input number has no bits set -1U is returned. */

2416

unsigned int

2417

APInt::tcMSB(const integerPart *parts, unsigned int n)

2418

{

2419

unsigned int msb;

2420

2421

do {

2422

--n;

2423

2424

if (parts[n] != 0) {

2425

msb = partMSB(parts[n]);

2426

2427

return msb + n * integerPartWidth;

2428

}

2429

} while (n);

2430

2431

return -1U;

2432

}

2433

2434

/* Copy the bit vector of width srcBITS from SRC, starting at bit

2435

srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes

2436

the least significant bit of DST. All high bits above srcBITS in

2437

DST are zero-filled. */

2438

void

2439

APInt::tcExtract(integerPart *dst, unsigned int dstCount,const integerPart *src,

2440

unsigned int srcBits, unsigned int srcLSB)

2441

{

2442

unsigned int firstSrcPart, dstParts, shift, n;

2443

2444

dstParts = (srcBits + integerPartWidth - 1) / integerPartWidth;

2445

assert(dstParts <= dstCount);

2446

2447

firstSrcPart = srcLSB / integerPartWidth;

2448

tcAssign (dst, src + firstSrcPart, dstParts);

2449

2450

shift = srcLSB % integerPartWidth;

2451

tcShiftRight (dst, dstParts, shift);

2452

2453

/* We now have (dstParts * integerPartWidth - shift) bits from SRC

2454

in DST. If this is less that srcBits, append the rest, else

2455

clear the high bits. */

2456

n = dstParts * integerPartWidth - shift;

2457

if (n < srcBits) {

2458

integerPart mask = lowBitMask (srcBits - n);

2459

dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)

2460

<< n % integerPartWidth);

2461

} else if (n > srcBits) {

2462

if (srcBits % integerPartWidth)

2463

dst[dstParts - 1] &= lowBitMask (srcBits % integerPartWidth);

2464

}

2465

2466

/* Clear high parts. */

2467

while (dstParts < dstCount)

2468

dst[dstParts++] = 0;

2469

}

2470

2471

/* DST += RHS + C where C is zero or one. Returns the carry flag. */

2472

integerPart

2473

APInt::tcAdd(integerPart *dst, const integerPart *rhs,

2474

integerPart c, unsigned int parts)

2475

{

2476

unsigned int i;

2477

2478

assert(c <= 1);

2479

2480

for (i = 0; i < parts; i++) {

2481

integerPart l;

2482

2483

l = dst[i];

2484

if (c) {

2485

dst[i] += rhs[i] + 1;

2486

c = (dst[i] <= l);

2487

} else {

2488

dst[i] += rhs[i];

2489

c = (dst[i] < l);

2490

}

2491

}

2492

2493

return c;

2494

}

2495

2496

/* DST -= RHS + C where C is zero or one. Returns the carry flag. */

2497

integerPart

2498

APInt::tcSubtract(integerPart *dst, const integerPart *rhs,

2499

integerPart c, unsigned int parts)

2500

{

2501

unsigned int i;

2502

2503

assert(c <= 1);

2504

2505

for (i = 0; i < parts; i++) {

2506

integerPart l;

2507

2508

l = dst[i];

2509

if (c) {

2510

dst[i] -= rhs[i] + 1;

2511

c = (dst[i] >= l);

2512

} else {

2513

dst[i] -= rhs[i];

2514

c = (dst[i] > l);

2515

}

2516

}

2517

2518

return c;

2519

}

2520

2521

/* Negate a bignum in-place. */

2522

void

2523

APInt::tcNegate(integerPart *dst, unsigned int parts)

2524

{

2525

tcComplement(dst, parts);

2526

tcIncrement(dst, parts);

2527

}

2528

2529

/* DST += SRC * MULTIPLIER + CARRY if add is true

2530

DST = SRC * MULTIPLIER + CARRY if add is false

2531

2532

Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC

2533

they must start at the same point, i.e. DST == SRC.

2534

2535

If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is

2536

returned. Otherwise DST is filled with the least significant

2537

DSTPARTS parts of the result, and if all of the omitted higher

2538

parts were zero return zero, otherwise overflow occurred and

2539

return one. */

2540

int

2541

APInt::tcMultiplyPart(integerPart *dst, const integerPart *src,

2542

integerPart multiplier, integerPart carry,

2543

unsigned int srcParts, unsigned int dstParts,

2544

bool add)

2545

{

2546

unsigned int i, n;

2547

2548

/* Otherwise our writes of DST kill our later reads of SRC. */

2549

assert(dst <= src || dst >= src + srcParts);

2550

assert(dstParts <= srcParts + 1);

2551

2552

/* N loops; minimum of dstParts and srcParts. */

2553

n = dstParts < srcParts ? dstParts: srcParts;

2554

2555

for (i = 0; i < n; i++) {

2556

integerPart low, mid, high, srcPart;

2557

2558

/* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.

2559

2560

This cannot overflow, because

2561

2562

(n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)

2563

2564

which is less than n^2. */

2565

2566

srcPart = src[i];

2567

2568

if (multiplier == 0 || srcPart == 0) {

2569

low = carry;

2570

high = 0;

2571

} else {

2572

low = lowHalf(srcPart) * lowHalf(multiplier);

2573

high = highHalf(srcPart) * highHalf(multiplier);

2574

2575

mid = lowHalf(srcPart) * highHalf(multiplier);

2576

high += highHalf(mid);

2577

mid <<= integerPartWidth / 2;

2578

if (low + mid < low)

2579

high++;

2580

low += mid;

2581

2582

mid = highHalf(srcPart) * lowHalf(multiplier);

2583

high += highHalf(mid);

2584

mid <<= integerPartWidth / 2;

2585

if (low + mid < low)

2586

high++;

2587

low += mid;

2588

2589

/* Now add carry. */

2590

if (low + carry < low)

2591

high++;

2592

low += carry;

2593

}

2594

2595

if (add) {

2596

/* And now DST[i], and store the new low part there. */

2597

if (low + dst[i] < low)

2598

high++;

2599

dst[i] += low;

2600

} else

2601

dst[i] = low;

2602

2603

carry = high;

2604

}

2605

2606

if (i < dstParts) {

2607

/* Full multiplication, there is no overflow. */

2608

assert(i + 1 == dstParts);

2609

dst[i] = carry;

2610

return 0;

2611

} else {

2612

/* We overflowed if there is carry. */

2613

if (carry)

2614

return 1;

2615

2616

/* We would overflow if any significant unwritten parts would be

2617

non-zero. This is true if any remaining src parts are non-zero

2618

and the multiplier is non-zero. */

2619

if (multiplier)

2620

for (; i < srcParts; i++)

2621

if (src[i])

2622

return 1;

2623

2624

/* We fitted in the narrow destination. */

2625

return 0;

2626

}

2627

}

2628

2629

/* DST = LHS * RHS, where DST has the same width as the operands and

2630

is filled with the least significant parts of the result. Returns

2631

one if overflow occurred, otherwise zero. DST must be disjoint

2632

from both operands. */

2633

int

2634

APInt::tcMultiply(integerPart *dst, const integerPart *lhs,

2635

const integerPart *rhs, unsigned int parts)

2636

{

2637

unsigned int i;

2638

int overflow;

2639

2640

assert(dst != lhs && dst != rhs);

2641

2642

overflow = 0;

2643

tcSet(dst, 0, parts);

2644

2645

for (i = 0; i < parts; i++)

2646

overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,

2647

parts - i, true);

2648

2649

return overflow;

2650

}

2651

2652

/* DST = LHS * RHS, where DST has width the sum of the widths of the

2653

operands. No overflow occurs. DST must be disjoint from both

2654

operands. Returns the number of parts required to hold the

2655

result. */

2656

unsigned int

2657

APInt::tcFullMultiply(integerPart *dst, const integerPart *lhs,

2658

const integerPart *rhs, unsigned int lhsParts,

2659

unsigned int rhsParts)

2660

{

2661

/* Put the narrower number on the LHS for less loops below. */

2662

if (lhsParts > rhsParts) {

2663

return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);

2664

} else {

2665

unsigned int n;

2666

2667

assert(dst != lhs && dst != rhs);

2668

2669

tcSet(dst, 0, rhsParts);

2670

2671

for (n = 0; n < lhsParts; n++)

2672

tcMultiplyPart(&dst[n], rhs, lhs[n], 0, rhsParts, rhsParts + 1, true);

2673

2674

n = lhsParts + rhsParts;

2675

2676

return n - (dst[n - 1] == 0);

2677

}

2678

}

2679

2680

/* If RHS is zero LHS and REMAINDER are left unchanged, return one.

2681

Otherwise set LHS to LHS / RHS with the fractional part discarded,

2682

set REMAINDER to the remainder, return zero. i.e.

2683

2684

OLD_LHS = RHS * LHS + REMAINDER

2685

2686

SCRATCH is a bignum of the same size as the operands and result for

2687

use by the routine; its contents need not be initialized and are

2688

destroyed. LHS, REMAINDER and SCRATCH must be distinct.

2689

2690

int

2691

APInt::tcDivide(integerPart *lhs, const integerPart *rhs,

2692

integerPart *remainder, integerPart *srhs,

2693

unsigned int parts)

2694

{

2695

unsigned int n, shiftCount;

2696

integerPart mask;

2697

2698

assert(lhs != remainder && lhs != srhs && remainder != srhs);

2699

2700

shiftCount = tcMSB(rhs, parts) + 1;

2701

if (shiftCount == 0)

2702

return true;

2703

2704

shiftCount = parts * integerPartWidth - shiftCount;

2705

n = shiftCount / integerPartWidth;

2706

mask = (integerPart) 1 << (shiftCount % integerPartWidth);

2707

2708

tcAssign(srhs, rhs, parts);

2709

tcShiftLeft(srhs, parts, shiftCount);

2710

tcAssign(remainder, lhs, parts);

2711

tcSet(lhs, 0, parts);

2712

2713

/* Loop, subtracting SRHS if REMAINDER is greater and adding that to

2714

the total. */

2715

for (;;) {

2716

int compare;

2717

2718

compare = tcCompare(remainder, srhs, parts);

2719

if (compare >= 0) {

2720

tcSubtract(remainder, srhs, 0, parts);

2721

lhs[n] |= mask;

2722

}

2723

2724

if (shiftCount == 0)

2725

break;

2726

shiftCount--;

2727

tcShiftRight(srhs, parts, 1);

2728

if ((mask >>= 1) == 0)

2729

mask = (integerPart) 1 << (integerPartWidth - 1), n--;

2730

}

2731

2732

return false;

2733

}

2734

2735

/* Shift a bignum left COUNT bits in-place. Shifted in bits are zero.

2736

There are no restrictions on COUNT. */

2737

void

2738

APInt::tcShiftLeft(integerPart *dst, unsigned int parts, unsigned int count)

2739

{

2740

if (count) {

2741

unsigned int jump, shift;

2742

2743

/* Jump is the inter-part jump; shift is is intra-part shift. */

2744

jump = count / integerPartWidth;

2745

shift = count % integerPartWidth;

2746

2747

while (parts > jump) {

2748

integerPart part;

2749

2750

parts--;

2751

2752

/* dst[i] comes from the two parts src[i - jump] and, if we have

2753

an intra-part shift, src[i - jump - 1]. */

2754

part = dst[parts - jump];

2755

if (shift) {

2756

part <<= shift;

2757

if (parts >= jump + 1)

2758

part |= dst[parts - jump - 1] >> (integerPartWidth - shift);

2759

}

2760

2761

dst[parts] = part;

2762

}

2763

2764

while (parts > 0)

2765

dst[--parts] = 0;

2766

}

2767

}

2768

2769

/* Shift a bignum right COUNT bits in-place. Shifted in bits are

2770

zero. There are no restrictions on COUNT. */

2771

void

2772

APInt::tcShiftRight(integerPart *dst, unsigned int parts, unsigned int count)

2773

{

2774

if (count) {

2775

unsigned int i, jump, shift;

2776

2777

/* Jump is the inter-part jump; shift is is intra-part shift. */

2778

jump = count / integerPartWidth;

2779

shift = count % integerPartWidth;

2780

2781

/* Perform the shift. This leaves the most significant COUNT bits

2782

of the result at zero. */

2783

for (i = 0; i < parts; i++) {

2784

integerPart part;

2785

2786

if (i + jump >= parts) {

2787

part = 0;

2788

} else {

2789

part = dst[i + jump];

2790

if (shift) {

2791

part >>= shift;

2792

if (i + jump + 1 < parts)

2793

part |= dst[i + jump + 1] << (integerPartWidth - shift);

2794

}

2795

}

2796

2797

dst[i] = part;

2798

}

2799

}

2800

}

2801

2802

/* Bitwise and of two bignums. */

2803

void

2804

APInt::tcAnd(integerPart *dst, const integerPart *rhs, unsigned int parts)

2805

{

2806

unsigned int i;

2807

2808

for (i = 0; i < parts; i++)

2809

dst[i] &= rhs[i];

2810

}

2811

2812

/* Bitwise inclusive or of two bignums. */

2813

void

2814

APInt::tcOr(integerPart *dst, const integerPart *rhs, unsigned int parts)

2815

{

2816

unsigned int i;

2817

2818

for (i = 0; i < parts; i++)

2819

dst[i] |= rhs[i];

2820

}

2821

2822

/* Bitwise exclusive or of two bignums. */

2823

void

2824

APInt::tcXor(integerPart *dst, const integerPart *rhs, unsigned int parts)

2825

{

2826

unsigned int i;

2827

2828

for (i = 0; i < parts; i++)

2829

dst[i] ^= rhs[i];

2830

}

2831

2832

/* Complement a bignum in-place. */

2833

void

2834

APInt::tcComplement(integerPart *dst, unsigned int parts)

2835

{

2836

unsigned int i;

2837

2838

for (i = 0; i < parts; i++)

2839

dst[i] = ~dst[i];

2840

}

2841

2842

/* Comparison (unsigned) of two bignums. */

2843

int

2844

APInt::tcCompare(const integerPart *lhs, const integerPart *rhs,

2845

unsigned int parts)

2846

{

2847

while (parts) {

2848

parts--;

2849

if (lhs[parts] == rhs[parts])

2850

continue;

2851

2852

if (lhs[parts] > rhs[parts])

2853

return 1;

2854

else

2855

return -1;

2856

}

2857

2858

return 0;

2859

}

2860

2861

/* Increment a bignum in-place, return the carry flag. */

2862

integerPart

2863

APInt::tcIncrement(integerPart *dst, unsigned int parts)

2864

{

2865

unsigned int i;

2866

2867

for (i = 0; i < parts; i++)

2868

if (++dst[i] != 0)

2869

break;

2870

2871

return i == parts;

2872

}

2873

2874

/* Decrement a bignum in-place, return the borrow flag. */

2875

integerPart

2876

APInt::tcDecrement(integerPart *dst, unsigned int parts) {

2877

for (unsigned int i = 0; i < parts; i++) {

2878

// If the current word is non-zero, then the decrement has no effect on the

2879

// higher-order words of the integer and no borrow can occur. Exit early.

2880

if (dst[i]--)

2881

return 0;

2882

}

2883

// If every word was zero, then there is a borrow.

2884

return 1;

2885

}

2886

2887

2888

/* Set the least significant BITS bits of a bignum, clear the

2889

rest. */

2890

void

2891

APInt::tcSetLeastSignificantBits(integerPart *dst, unsigned int parts,

2892

unsigned int bits)

2893

{

2894

unsigned int i;

2895

2896

i = 0;

2897

while (bits > integerPartWidth) {

2898

dst[i++] = ~(integerPart) 0;

2899

bits -= integerPartWidth;

2900

}

2901

2902

if (bits)

2903

dst[i++] = ~(integerPart) 0 >> (integerPartWidth - bits);

2904

2905

while (i < parts)

2906

dst[i++] = 0;

2907

}

Older »