blob: 1c697d301a73fd197cbc668c199215b18b5c51e9 [file] [log] [blame]
Zhou Shengdac63782007-02-06 03:00:16 +00001//===-- APInt.cpp - Implement APInt class ---------------------------------===//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Zhou Shengdac63782007-02-06 03:00:16 +00007//
8//===----------------------------------------------------------------------===//
9//
Reid Spencera41e93b2007-02-25 19:32:03 +000010// This file implements a class to represent arbitrary precision integer
11// constant values and provide a variety of arithmetic operations on them.
Zhou Shengdac63782007-02-06 03:00:16 +000012//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/ADT/APInt.h"
Mehdi Amini47b292d2016-04-16 07:51:28 +000016#include "llvm/ADT/ArrayRef.h"
Ted Kremenek5c75d542008-01-19 04:23:33 +000017#include "llvm/ADT/FoldingSet.h"
Chandler Carruth71bd7d12012-03-04 12:02:57 +000018#include "llvm/ADT/Hashing.h"
Chris Lattner17f71652008-08-17 07:19:36 +000019#include "llvm/ADT/SmallString.h"
Chandler Carruth71bd7d12012-03-04 12:02:57 +000020#include "llvm/ADT/StringRef.h"
Reid Spencera5e0d202007-02-24 03:58:46 +000021#include "llvm/Support/Debug.h"
Torok Edwin56d06592009-07-11 20:10:48 +000022#include "llvm/Support/ErrorHandling.h"
Zhou Shengdac63782007-02-06 03:00:16 +000023#include "llvm/Support/MathExtras.h"
Chris Lattner0c19df42008-08-23 22:23:09 +000024#include "llvm/Support/raw_ostream.h"
Vassil Vassilev2ec8b152016-09-14 08:55:18 +000025#include <climits>
Chris Lattner17f71652008-08-17 07:19:36 +000026#include <cmath>
Zhou Shengdac63782007-02-06 03:00:16 +000027#include <cstdlib>
Chandler Carruthed0881b2012-12-03 16:50:05 +000028#include <cstring>
Zhou Shengdac63782007-02-06 03:00:16 +000029using namespace llvm;
30
Chandler Carruth64648262014-04-22 03:07:47 +000031#define DEBUG_TYPE "apint"
32
Reid Spencera41e93b2007-02-25 19:32:03 +000033/// A utility function for allocating memory, checking for allocation failures,
34/// and ensuring the contents are zeroed.
Chris Lattner77527f52009-01-21 18:09:24 +000035inline static uint64_t* getClearedMemory(unsigned numWords) {
Reid Spencera856b6e2007-02-18 18:38:44 +000036 uint64_t * result = new uint64_t[numWords];
37 assert(result && "APInt memory allocation fails!");
38 memset(result, 0, numWords * sizeof(uint64_t));
39 return result;
Zhou Sheng94b623a2007-02-06 06:04:53 +000040}
41
Eric Christopher820256b2009-08-21 04:06:45 +000042/// A utility function for allocating memory and checking for allocation
Reid Spencera41e93b2007-02-25 19:32:03 +000043/// failure. The content is not zeroed.
Chris Lattner77527f52009-01-21 18:09:24 +000044inline static uint64_t* getMemory(unsigned numWords) {
Reid Spencera856b6e2007-02-18 18:38:44 +000045 uint64_t * result = new uint64_t[numWords];
46 assert(result && "APInt memory allocation fails!");
47 return result;
48}
49
Erick Tryzelaardadb15712009-08-21 03:15:28 +000050/// A utility function that converts a character to a digit.
51inline static unsigned getDigit(char cdigit, uint8_t radix) {
Erick Tryzelaar60964092009-08-21 06:48:37 +000052 unsigned r;
53
Douglas Gregor663c0682011-09-14 15:54:46 +000054 if (radix == 16 || radix == 36) {
Erick Tryzelaar60964092009-08-21 06:48:37 +000055 r = cdigit - '0';
56 if (r <= 9)
57 return r;
58
59 r = cdigit - 'A';
Douglas Gregorc98ac852011-09-20 18:33:29 +000060 if (r <= radix - 11U)
Erick Tryzelaar60964092009-08-21 06:48:37 +000061 return r + 10;
62
63 r = cdigit - 'a';
Douglas Gregorc98ac852011-09-20 18:33:29 +000064 if (r <= radix - 11U)
Erick Tryzelaar60964092009-08-21 06:48:37 +000065 return r + 10;
Simon Pilgrim4c0ea9d2017-02-23 16:07:04 +000066
Douglas Gregore4e20f42011-09-20 18:11:52 +000067 radix = 10;
Erick Tryzelaardadb15712009-08-21 03:15:28 +000068 }
69
Erick Tryzelaar60964092009-08-21 06:48:37 +000070 r = cdigit - '0';
71 if (r < radix)
72 return r;
73
74 return -1U;
Erick Tryzelaardadb15712009-08-21 03:15:28 +000075}
76
77
Pawel Bylica68304012016-06-27 08:31:48 +000078void APInt::initSlowCase(uint64_t val, bool isSigned) {
Craig Topper0085ffb2017-03-20 01:29:52 +000079 VAL = 0;
Chris Lattner1ac3e252008-08-20 17:02:31 +000080 pVal = getClearedMemory(getNumWords());
81 pVal[0] = val;
Eric Christopher820256b2009-08-21 04:06:45 +000082 if (isSigned && int64_t(val) < 0)
Chris Lattner1ac3e252008-08-20 17:02:31 +000083 for (unsigned i = 1; i < getNumWords(); ++i)
Craig Topper5e113742017-04-22 06:31:36 +000084 pVal[i] = WORD_MAX;
Craig Topperf78a6f02017-03-01 21:06:18 +000085 clearUnusedBits();
Zhou Shengdac63782007-02-06 03:00:16 +000086}
87
Chris Lattnerd57b7602008-10-11 22:07:19 +000088void APInt::initSlowCase(const APInt& that) {
Craig Topper0085ffb2017-03-20 01:29:52 +000089 VAL = 0;
Chris Lattnerd57b7602008-10-11 22:07:19 +000090 pVal = getMemory(getNumWords());
91 memcpy(pVal, that.pVal, getNumWords() * APINT_WORD_SIZE);
92}
93
Jeffrey Yasskin7a162882011-07-18 21:45:40 +000094void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
Erick Tryzelaar1264bcb2009-08-21 03:15:14 +000095 assert(BitWidth && "Bitwidth too small");
Jeffrey Yasskin7a162882011-07-18 21:45:40 +000096 assert(bigVal.data() && "Null pointer detected!");
Zhou Shengdac63782007-02-06 03:00:16 +000097 if (isSingleWord())
Reid Spencerdf6cf5a2007-02-24 10:01:42 +000098 VAL = bigVal[0];
Zhou Shengdac63782007-02-06 03:00:16 +000099 else {
Reid Spencerdf6cf5a2007-02-24 10:01:42 +0000100 // Get memory, cleared to 0
Craig Topper0085ffb2017-03-20 01:29:52 +0000101 VAL = 0;
Reid Spencerdf6cf5a2007-02-24 10:01:42 +0000102 pVal = getClearedMemory(getNumWords());
103 // Calculate the number of words to copy
Jeffrey Yasskin7a162882011-07-18 21:45:40 +0000104 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
Reid Spencerdf6cf5a2007-02-24 10:01:42 +0000105 // Copy the words from bigVal to pVal
Jeffrey Yasskin7a162882011-07-18 21:45:40 +0000106 memcpy(pVal, bigVal.data(), words * APINT_WORD_SIZE);
Zhou Shengdac63782007-02-06 03:00:16 +0000107 }
Reid Spencerdf6cf5a2007-02-24 10:01:42 +0000108 // Make sure unused high bits are cleared
109 clearUnusedBits();
Zhou Shengdac63782007-02-06 03:00:16 +0000110}
111
Jeffrey Yasskin7a162882011-07-18 21:45:40 +0000112APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
Craig Topper0085ffb2017-03-20 01:29:52 +0000113 : BitWidth(numBits) {
Jeffrey Yasskin7a162882011-07-18 21:45:40 +0000114 initFromArray(bigVal);
115}
116
117APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
Craig Topper0085ffb2017-03-20 01:29:52 +0000118 : BitWidth(numBits) {
Jeffrey Yasskin7a162882011-07-18 21:45:40 +0000119 initFromArray(makeArrayRef(bigVal, numWords));
120}
121
Benjamin Kramer92d89982010-07-14 22:38:02 +0000122APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
Craig Topper90377de2017-04-13 04:59:11 +0000123 : VAL(0), BitWidth(numbits) {
Erick Tryzelaar1264bcb2009-08-21 03:15:14 +0000124 assert(BitWidth && "Bitwidth too small");
Daniel Dunbar3a1efd112009-08-13 02:33:34 +0000125 fromString(numbits, Str, radix);
Zhou Sheng3e8022d2007-02-07 06:14:53 +0000126}
127
Craig Topperc67fe572017-04-19 17:01:58 +0000128void APInt::AssignSlowCase(const APInt& RHS) {
Reid Spencer7c16cd22007-02-26 23:38:21 +0000129 // Don't do anything for X = X
130 if (this == &RHS)
Craig Topperc67fe572017-04-19 17:01:58 +0000131 return;
Reid Spencer7c16cd22007-02-26 23:38:21 +0000132
Reid Spencer7c16cd22007-02-26 23:38:21 +0000133 if (BitWidth == RHS.getBitWidth()) {
Chris Lattner1ac3e252008-08-20 17:02:31 +0000134 // assume same bit-width single-word case is already handled
135 assert(!isSingleWord());
136 memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE);
Craig Topperc67fe572017-04-19 17:01:58 +0000137 return;
Reid Spencer7c16cd22007-02-26 23:38:21 +0000138 }
139
Chris Lattner1ac3e252008-08-20 17:02:31 +0000140 if (isSingleWord()) {
141 // assume case where both are single words is already handled
142 assert(!RHS.isSingleWord());
143 VAL = 0;
144 pVal = getMemory(RHS.getNumWords());
145 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
Eric Christopher820256b2009-08-21 04:06:45 +0000146 } else if (getNumWords() == RHS.getNumWords())
Reid Spencer7c16cd22007-02-26 23:38:21 +0000147 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
148 else if (RHS.isSingleWord()) {
149 delete [] pVal;
Reid Spencera856b6e2007-02-18 18:38:44 +0000150 VAL = RHS.VAL;
Reid Spencer7c16cd22007-02-26 23:38:21 +0000151 } else {
152 delete [] pVal;
153 pVal = getMemory(RHS.getNumWords());
154 memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE);
155 }
156 BitWidth = RHS.BitWidth;
Craig Topperc67fe572017-04-19 17:01:58 +0000157 clearUnusedBits();
Zhou Shengdac63782007-02-06 03:00:16 +0000158}
159
Pawel Bylica6eeeac72015-04-06 13:31:39 +0000160/// This method 'profiles' an APInt for use with FoldingSet.
Ted Kremenek5c75d542008-01-19 04:23:33 +0000161void APInt::Profile(FoldingSetNodeID& ID) const {
Ted Kremenek901540f2008-02-19 20:50:41 +0000162 ID.AddInteger(BitWidth);
Eric Christopher820256b2009-08-21 04:06:45 +0000163
Ted Kremenek5c75d542008-01-19 04:23:33 +0000164 if (isSingleWord()) {
165 ID.AddInteger(VAL);
166 return;
167 }
168
Chris Lattner77527f52009-01-21 18:09:24 +0000169 unsigned NumWords = getNumWords();
Ted Kremenek5c75d542008-01-19 04:23:33 +0000170 for (unsigned i = 0; i < NumWords; ++i)
171 ID.AddInteger(pVal[i]);
172}
173
Zhou Shengdac63782007-02-06 03:00:16 +0000174/// @brief Prefix increment operator. Increments the APInt by one.
175APInt& APInt::operator++() {
Eric Christopher820256b2009-08-21 04:06:45 +0000176 if (isSingleWord())
Reid Spencer1d072122007-02-16 22:36:51 +0000177 ++VAL;
Zhou Shengdac63782007-02-06 03:00:16 +0000178 else
Craig Topper92fc4772017-04-13 04:36:06 +0000179 tcIncrement(pVal, getNumWords());
Reid Spencera41e93b2007-02-25 19:32:03 +0000180 return clearUnusedBits();
Zhou Shengdac63782007-02-06 03:00:16 +0000181}
182
Zhou Shengdac63782007-02-06 03:00:16 +0000183/// @brief Prefix decrement operator. Decrements the APInt by one.
184APInt& APInt::operator--() {
Eric Christopher820256b2009-08-21 04:06:45 +0000185 if (isSingleWord())
Reid Spencera856b6e2007-02-18 18:38:44 +0000186 --VAL;
Zhou Shengdac63782007-02-06 03:00:16 +0000187 else
Craig Topper92fc4772017-04-13 04:36:06 +0000188 tcDecrement(pVal, getNumWords());
Reid Spencera41e93b2007-02-25 19:32:03 +0000189 return clearUnusedBits();
Zhou Shengdac63782007-02-06 03:00:16 +0000190}
191
Reid Spencera41e93b2007-02-25 19:32:03 +0000192/// Adds the RHS APint to this APInt.
193/// @returns this, after addition of RHS.
Eric Christopher820256b2009-08-21 04:06:45 +0000194/// @brief Addition assignment operator.
Zhou Shengdac63782007-02-06 03:00:16 +0000195APInt& APInt::operator+=(const APInt& RHS) {
Reid Spencera32372d12007-02-17 00:18:01 +0000196 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
Eric Christopher820256b2009-08-21 04:06:45 +0000197 if (isSingleWord())
Reid Spencer7a6a8d52007-02-20 23:40:25 +0000198 VAL += RHS.VAL;
Craig Topper15e484a2017-04-02 06:59:43 +0000199 else
200 tcAdd(pVal, RHS.pVal, 0, getNumWords());
Reid Spencera41e93b2007-02-25 19:32:03 +0000201 return clearUnusedBits();
Zhou Shengdac63782007-02-06 03:00:16 +0000202}
203
Pete Cooperfea21392016-07-22 20:55:46 +0000204APInt& APInt::operator+=(uint64_t RHS) {
205 if (isSingleWord())
206 VAL += RHS;
207 else
Craig Topper92fc4772017-04-13 04:36:06 +0000208 tcAddPart(pVal, RHS, getNumWords());
Pete Cooperfea21392016-07-22 20:55:46 +0000209 return clearUnusedBits();
210}
211
Reid Spencera41e93b2007-02-25 19:32:03 +0000212/// Subtracts the RHS APInt from this APInt
213/// @returns this, after subtraction
Eric Christopher820256b2009-08-21 04:06:45 +0000214/// @brief Subtraction assignment operator.
Zhou Shengdac63782007-02-06 03:00:16 +0000215APInt& APInt::operator-=(const APInt& RHS) {
Reid Spencera32372d12007-02-17 00:18:01 +0000216 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
Eric Christopher820256b2009-08-21 04:06:45 +0000217 if (isSingleWord())
Reid Spencer7a6a8d52007-02-20 23:40:25 +0000218 VAL -= RHS.VAL;
219 else
Craig Topper15e484a2017-04-02 06:59:43 +0000220 tcSubtract(pVal, RHS.pVal, 0, getNumWords());
Reid Spencera41e93b2007-02-25 19:32:03 +0000221 return clearUnusedBits();
Zhou Shengdac63782007-02-06 03:00:16 +0000222}
223
Pete Cooperfea21392016-07-22 20:55:46 +0000224APInt& APInt::operator-=(uint64_t RHS) {
225 if (isSingleWord())
226 VAL -= RHS;
227 else
Craig Topper92fc4772017-04-13 04:36:06 +0000228 tcSubtractPart(pVal, RHS, getNumWords());
Pete Cooperfea21392016-07-22 20:55:46 +0000229 return clearUnusedBits();
230}
231
Dan Gohman4a618822010-02-10 16:03:48 +0000232/// Multiplies an integer array, x, by a uint64_t integer and places the result
Eric Christopher820256b2009-08-21 04:06:45 +0000233/// into dest.
Reid Spencera41e93b2007-02-25 19:32:03 +0000234/// @returns the carry out of the multiplication.
235/// @brief Multiply a multi-digit APInt by a single digit (64-bit) integer.
Chris Lattner77527f52009-01-21 18:09:24 +0000236static uint64_t mul_1(uint64_t dest[], uint64_t x[], unsigned len, uint64_t y) {
Reid Spencerdf6cf5a2007-02-24 10:01:42 +0000237 // Split y into high 32-bit part (hy) and low 32-bit part (ly)
Reid Spencer100502d2007-02-17 03:16:00 +0000238 uint64_t ly = y & 0xffffffffULL, hy = y >> 32;
Reid Spencera41e93b2007-02-25 19:32:03 +0000239 uint64_t carry = 0;
240
241 // For each digit of x.
Chris Lattner77527f52009-01-21 18:09:24 +0000242 for (unsigned i = 0; i < len; ++i) {
Reid Spencera41e93b2007-02-25 19:32:03 +0000243 // Split x into high and low words
244 uint64_t lx = x[i] & 0xffffffffULL;
245 uint64_t hx = x[i] >> 32;
246 // hasCarry - A flag to indicate if there is a carry to the next digit.
Reid Spencer100502d2007-02-17 03:16:00 +0000247 // hasCarry == 0, no carry
248 // hasCarry == 1, has carry
249 // hasCarry == 2, no carry and the calculation result == 0.
250 uint8_t hasCarry = 0;
251 dest[i] = carry + lx * ly;
252 // Determine if the add above introduces carry.
253 hasCarry = (dest[i] < carry) ? 1 : 0;
254 carry = hx * ly + (dest[i] >> 32) + (hasCarry ? (1ULL << 32) : 0);
Eric Christopher820256b2009-08-21 04:06:45 +0000255 // The upper limit of carry can be (2^32 - 1)(2^32 - 1) +
Reid Spencer100502d2007-02-17 03:16:00 +0000256 // (2^32 - 1) + 2^32 = 2^64.
257 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
258
259 carry += (lx * hy) & 0xffffffffULL;
260 dest[i] = (carry << 32) | (dest[i] & 0xffffffffULL);
Eric Christopher820256b2009-08-21 04:06:45 +0000261 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0) +
Reid Spencer100502d2007-02-17 03:16:00 +0000262 (carry >> 32) + ((lx * hy) >> 32) + hx * hy;
263 }
Reid Spencer100502d2007-02-17 03:16:00 +0000264 return carry;
265}
266
Eric Christopher820256b2009-08-21 04:06:45 +0000267/// Multiplies integer array x by integer array y and stores the result into
Reid Spencera41e93b2007-02-25 19:32:03 +0000268/// the integer array dest. Note that dest's size must be >= xlen + ylen.
Simon Pilgrim0099beb2017-03-09 13:57:04 +0000269/// @brief Generalized multiplication of integer arrays.
Chris Lattner77527f52009-01-21 18:09:24 +0000270static void mul(uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[],
271 unsigned ylen) {
Reid Spencer100502d2007-02-17 03:16:00 +0000272 dest[xlen] = mul_1(dest, x, xlen, y[0]);
Chris Lattner77527f52009-01-21 18:09:24 +0000273 for (unsigned i = 1; i < ylen; ++i) {
Reid Spencer100502d2007-02-17 03:16:00 +0000274 uint64_t ly = y[i] & 0xffffffffULL, hy = y[i] >> 32;
Reid Spencer58a6a432007-02-21 08:21:52 +0000275 uint64_t carry = 0, lx = 0, hx = 0;
Chris Lattner77527f52009-01-21 18:09:24 +0000276 for (unsigned j = 0; j < xlen; ++j) {
Reid Spencer100502d2007-02-17 03:16:00 +0000277 lx = x[j] & 0xffffffffULL;
278 hx = x[j] >> 32;
279 // hasCarry - A flag to indicate if has carry.
280 // hasCarry == 0, no carry
281 // hasCarry == 1, has carry
282 // hasCarry == 2, no carry and the calculation result == 0.
283 uint8_t hasCarry = 0;
284 uint64_t resul = carry + lx * ly;
285 hasCarry = (resul < carry) ? 1 : 0;
286 carry = (hasCarry ? (1ULL << 32) : 0) + hx * ly + (resul >> 32);
287 hasCarry = (!carry && hasCarry) ? 1 : (!carry ? 2 : 0);
288
289 carry += (lx * hy) & 0xffffffffULL;
290 resul = (carry << 32) | (resul & 0xffffffffULL);
291 dest[i+j] += resul;
292 carry = (((!carry && hasCarry != 2) || hasCarry == 1) ? (1ULL << 32) : 0)+
Eric Christopher820256b2009-08-21 04:06:45 +0000293 (carry >> 32) + (dest[i+j] < resul ? 1 : 0) +
Reid Spencer100502d2007-02-17 03:16:00 +0000294 ((lx * hy) >> 32) + hx * hy;
295 }
296 dest[i+xlen] = carry;
297 }
298}
299
Zhou Shengdac63782007-02-06 03:00:16 +0000300APInt& APInt::operator*=(const APInt& RHS) {
Reid Spencera32372d12007-02-17 00:18:01 +0000301 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
Reid Spencer58a6a432007-02-21 08:21:52 +0000302 if (isSingleWord()) {
Reid Spencer4bb430c2007-02-20 20:42:10 +0000303 VAL *= RHS.VAL;
Reid Spencer58a6a432007-02-21 08:21:52 +0000304 clearUnusedBits();
305 return *this;
Zhou Shengdac63782007-02-06 03:00:16 +0000306 }
Reid Spencer58a6a432007-02-21 08:21:52 +0000307
308 // Get some bit facts about LHS and check for zero
Chris Lattner77527f52009-01-21 18:09:24 +0000309 unsigned lhsBits = getActiveBits();
310 unsigned lhsWords = !lhsBits ? 0 : whichWord(lhsBits - 1) + 1;
Eric Christopher820256b2009-08-21 04:06:45 +0000311 if (!lhsWords)
Reid Spencer58a6a432007-02-21 08:21:52 +0000312 // 0 * X ===> 0
313 return *this;
314
315 // Get some bit facts about RHS and check for zero
Chris Lattner77527f52009-01-21 18:09:24 +0000316 unsigned rhsBits = RHS.getActiveBits();
317 unsigned rhsWords = !rhsBits ? 0 : whichWord(rhsBits - 1) + 1;
Reid Spencer58a6a432007-02-21 08:21:52 +0000318 if (!rhsWords) {
319 // X * 0 ===> 0
Jay Foad25a5e4c2010-12-01 08:53:58 +0000320 clearAllBits();
Reid Spencer58a6a432007-02-21 08:21:52 +0000321 return *this;
322 }
323
324 // Allocate space for the result
Chris Lattner77527f52009-01-21 18:09:24 +0000325 unsigned destWords = rhsWords + lhsWords;
Reid Spencer58a6a432007-02-21 08:21:52 +0000326 uint64_t *dest = getMemory(destWords);
327
328 // Perform the long multiply
329 mul(dest, pVal, lhsWords, RHS.pVal, rhsWords);
330
331 // Copy result back into *this
Jay Foad25a5e4c2010-12-01 08:53:58 +0000332 clearAllBits();
Chris Lattner77527f52009-01-21 18:09:24 +0000333 unsigned wordsToCopy = destWords >= getNumWords() ? getNumWords() : destWords;
Reid Spencer58a6a432007-02-21 08:21:52 +0000334 memcpy(pVal, dest, wordsToCopy * APINT_WORD_SIZE);
Eli Friedman19546412011-10-07 23:40:49 +0000335 clearUnusedBits();
Reid Spencer58a6a432007-02-21 08:21:52 +0000336
337 // delete dest array and return
338 delete[] dest;
Zhou Shengdac63782007-02-06 03:00:16 +0000339 return *this;
340}
341
Craig Topperc67fe572017-04-19 17:01:58 +0000342void APInt::AndAssignSlowCase(const APInt& RHS) {
Craig Topperb2aaa5d2017-04-01 21:50:03 +0000343 tcAnd(pVal, RHS.pVal, getNumWords());
Zhou Shengdac63782007-02-06 03:00:16 +0000344}
345
Craig Topperc67fe572017-04-19 17:01:58 +0000346void APInt::OrAssignSlowCase(const APInt& RHS) {
Craig Topperb2aaa5d2017-04-01 21:50:03 +0000347 tcOr(pVal, RHS.pVal, getNumWords());
Zhou Shengdac63782007-02-06 03:00:16 +0000348}
349
Craig Topperc67fe572017-04-19 17:01:58 +0000350void APInt::XorAssignSlowCase(const APInt& RHS) {
Craig Topperb2aaa5d2017-04-01 21:50:03 +0000351 tcXor(pVal, RHS.pVal, getNumWords());
Zhou Shengdac63782007-02-06 03:00:16 +0000352}
353
Zhou Shengdac63782007-02-06 03:00:16 +0000354APInt APInt::operator*(const APInt& RHS) const {
Reid Spencera32372d12007-02-17 00:18:01 +0000355 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
Reid Spencera41e93b2007-02-25 19:32:03 +0000356 if (isSingleWord())
Reid Spenceraa8dcfe2007-02-26 07:44:38 +0000357 return APInt(BitWidth, VAL * RHS.VAL);
Reid Spencer4bb430c2007-02-20 20:42:10 +0000358 APInt Result(*this);
359 Result *= RHS;
Eli Friedman19546412011-10-07 23:40:49 +0000360 return Result;
Zhou Shengdac63782007-02-06 03:00:16 +0000361}
362
Chris Lattner1ac3e252008-08-20 17:02:31 +0000363bool APInt::EqualSlowCase(const APInt& RHS) const {
Matthias Braun5117fcd2016-02-15 20:06:19 +0000364 return std::equal(pVal, pVal + getNumWords(), RHS.pVal);
Zhou Shengdac63782007-02-06 03:00:16 +0000365}
366
Craig Topper1dc8fc82017-04-21 16:13:15 +0000367int APInt::compare(const APInt& RHS) const {
Reid Spencer1d072122007-02-16 22:36:51 +0000368 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
369 if (isSingleWord())
Craig Topper1dc8fc82017-04-21 16:13:15 +0000370 return VAL < RHS.VAL ? -1 : VAL > RHS.VAL;
Reid Spencera41e93b2007-02-25 19:32:03 +0000371
Craig Topper1dc8fc82017-04-21 16:13:15 +0000372 return tcCompare(pVal, RHS.pVal, getNumWords());
Zhou Shengdac63782007-02-06 03:00:16 +0000373}
374
Craig Topper1dc8fc82017-04-21 16:13:15 +0000375int APInt::compareSigned(const APInt& RHS) const {
Reid Spencer1d072122007-02-16 22:36:51 +0000376 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
Reid Spencerbe4ddf62007-02-18 20:09:41 +0000377 if (isSingleWord()) {
David Majnemer5f1c0172016-06-24 20:51:47 +0000378 int64_t lhsSext = SignExtend64(VAL, BitWidth);
379 int64_t rhsSext = SignExtend64(RHS.VAL, BitWidth);
Craig Topper1dc8fc82017-04-21 16:13:15 +0000380 return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
Reid Spencer1d072122007-02-16 22:36:51 +0000381 }
Reid Spencerbe4ddf62007-02-18 20:09:41 +0000382
Reid Spencer54abdcf2007-02-27 18:23:40 +0000383 bool lhsNeg = isNegative();
Pete Cooperd6e6bf12016-05-26 17:40:07 +0000384 bool rhsNeg = RHS.isNegative();
Reid Spencera41e93b2007-02-25 19:32:03 +0000385
Pete Cooperd6e6bf12016-05-26 17:40:07 +0000386 // If the sign bits don't match, then (LHS < RHS) if LHS is negative
387 if (lhsNeg != rhsNeg)
Craig Topper1dc8fc82017-04-21 16:13:15 +0000388 return lhsNeg ? -1 : 1;
Pete Cooperd6e6bf12016-05-26 17:40:07 +0000389
Simon Pilgrim0099beb2017-03-09 13:57:04 +0000390 // Otherwise we can just use an unsigned comparison, because even negative
Pete Cooperd6e6bf12016-05-26 17:40:07 +0000391 // numbers compare correctly this way if both have the same signed-ness.
Craig Topper1dc8fc82017-04-21 16:13:15 +0000392 return tcCompare(pVal, RHS.pVal, getNumWords());
Zhou Shengdac63782007-02-06 03:00:16 +0000393}
394
Jay Foad25a5e4c2010-12-01 08:53:58 +0000395void APInt::setBit(unsigned bitPosition) {
Eric Christopher820256b2009-08-21 04:06:45 +0000396 if (isSingleWord())
Reid Spencera41e93b2007-02-25 19:32:03 +0000397 VAL |= maskBit(bitPosition);
Eric Christopher820256b2009-08-21 04:06:45 +0000398 else
Reid Spencera41e93b2007-02-25 19:32:03 +0000399 pVal[whichWord(bitPosition)] |= maskBit(bitPosition);
Zhou Shengdac63782007-02-06 03:00:16 +0000400}
401
Craig Topperbafdd032017-03-07 01:56:01 +0000402void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
403 unsigned loWord = whichWord(loBit);
404 unsigned hiWord = whichWord(hiBit);
Simon Pilgrimaed35222017-02-24 10:15:29 +0000405
Simon Pilgrim0099beb2017-03-09 13:57:04 +0000406 // Create an initial mask for the low word with zeros below loBit.
Craig Topper5e113742017-04-22 06:31:36 +0000407 uint64_t loMask = WORD_MAX << whichBit(loBit);
Simon Pilgrimaed35222017-02-24 10:15:29 +0000408
Craig Topperbafdd032017-03-07 01:56:01 +0000409 // If hiBit is not aligned, we need a high mask.
410 unsigned hiShiftAmt = whichBit(hiBit);
411 if (hiShiftAmt != 0) {
412 // Create a high mask with zeros above hiBit.
Craig Topper5e113742017-04-22 06:31:36 +0000413 uint64_t hiMask = WORD_MAX >> (APINT_BITS_PER_WORD - hiShiftAmt);
Craig Topperbafdd032017-03-07 01:56:01 +0000414 // If loWord and hiWord are equal, then we combine the masks. Otherwise,
415 // set the bits in hiWord.
416 if (hiWord == loWord)
417 loMask &= hiMask;
418 else
Simon Pilgrimaed35222017-02-24 10:15:29 +0000419 pVal[hiWord] |= hiMask;
Simon Pilgrimaed35222017-02-24 10:15:29 +0000420 }
Craig Topperbafdd032017-03-07 01:56:01 +0000421 // Apply the mask to the low word.
422 pVal[loWord] |= loMask;
423
424 // Fill any words between loWord and hiWord with all ones.
425 for (unsigned word = loWord + 1; word < hiWord; ++word)
Craig Topper5e113742017-04-22 06:31:36 +0000426 pVal[word] = WORD_MAX;
Simon Pilgrimaed35222017-02-24 10:15:29 +0000427}
428
Zhou Shengdac63782007-02-06 03:00:16 +0000429/// Set the given bit to 0 whose position is given as "bitPosition".
430/// @brief Set a given bit to 0.
Jay Foad25a5e4c2010-12-01 08:53:58 +0000431void APInt::clearBit(unsigned bitPosition) {
Eric Christopher820256b2009-08-21 04:06:45 +0000432 if (isSingleWord())
Reid Spencera856b6e2007-02-18 18:38:44 +0000433 VAL &= ~maskBit(bitPosition);
Eric Christopher820256b2009-08-21 04:06:45 +0000434 else
Reid Spencera856b6e2007-02-18 18:38:44 +0000435 pVal[whichWord(bitPosition)] &= ~maskBit(bitPosition);
Zhou Shengdac63782007-02-06 03:00:16 +0000436}
437
Zhou Shengdac63782007-02-06 03:00:16 +0000438/// @brief Toggle every bit to its opposite value.
Craig Topperafc9e352017-03-27 17:10:21 +0000439void APInt::flipAllBitsSlowCase() {
Craig Toppera742cb52017-04-01 21:50:08 +0000440 tcComplement(pVal, getNumWords());
Craig Topperafc9e352017-03-27 17:10:21 +0000441 clearUnusedBits();
442}
Zhou Shengdac63782007-02-06 03:00:16 +0000443
Eric Christopher820256b2009-08-21 04:06:45 +0000444/// Toggle a given bit to its opposite value whose position is given
Zhou Shengdac63782007-02-06 03:00:16 +0000445/// as "bitPosition".
446/// @brief Toggles a given bit to its opposite value.
Jay Foad25a5e4c2010-12-01 08:53:58 +0000447void APInt::flipBit(unsigned bitPosition) {
Reid Spencer1d072122007-02-16 22:36:51 +0000448 assert(bitPosition < BitWidth && "Out of the bit-width range!");
Jay Foad25a5e4c2010-12-01 08:53:58 +0000449 if ((*this)[bitPosition]) clearBit(bitPosition);
450 else setBit(bitPosition);
Zhou Shengdac63782007-02-06 03:00:16 +0000451}
452
Simon Pilgrimb02667c2017-03-10 13:44:32 +0000453void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
454 unsigned subBitWidth = subBits.getBitWidth();
455 assert(0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth &&
456 "Illegal bit insertion");
457
458 // Insertion is a direct copy.
459 if (subBitWidth == BitWidth) {
460 *this = subBits;
461 return;
462 }
463
464 // Single word result can be done as a direct bitmask.
465 if (isSingleWord()) {
Craig Topper5e113742017-04-22 06:31:36 +0000466 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
Simon Pilgrimb02667c2017-03-10 13:44:32 +0000467 VAL &= ~(mask << bitPosition);
468 VAL |= (subBits.VAL << bitPosition);
469 return;
470 }
471
472 unsigned loBit = whichBit(bitPosition);
473 unsigned loWord = whichWord(bitPosition);
474 unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
475
476 // Insertion within a single word can be done as a direct bitmask.
477 if (loWord == hi1Word) {
Craig Topper5e113742017-04-22 06:31:36 +0000478 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
Simon Pilgrimb02667c2017-03-10 13:44:32 +0000479 pVal[loWord] &= ~(mask << loBit);
480 pVal[loWord] |= (subBits.VAL << loBit);
481 return;
482 }
483
484 // Insert on word boundaries.
485 if (loBit == 0) {
486 // Direct copy whole words.
487 unsigned numWholeSubWords = subBitWidth / APINT_BITS_PER_WORD;
488 memcpy(pVal + loWord, subBits.getRawData(),
489 numWholeSubWords * APINT_WORD_SIZE);
490
491 // Mask+insert remaining bits.
492 unsigned remainingBits = subBitWidth % APINT_BITS_PER_WORD;
493 if (remainingBits != 0) {
Craig Topper5e113742017-04-22 06:31:36 +0000494 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - remainingBits);
Simon Pilgrimb02667c2017-03-10 13:44:32 +0000495 pVal[hi1Word] &= ~mask;
496 pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
497 }
498 return;
499 }
500
501 // General case - set/clear individual bits in dst based on src.
502 // TODO - there is scope for optimization here, but at the moment this code
503 // path is barely used so prefer readability over performance.
504 for (unsigned i = 0; i != subBitWidth; ++i) {
505 if (subBits[i])
506 setBit(bitPosition + i);
507 else
508 clearBit(bitPosition + i);
509 }
510}
511
Simon Pilgrim0f5fb5f2017-02-25 20:01:58 +0000512APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {
513 assert(numBits > 0 && "Can't extract zero bits");
514 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
515 "Illegal bit extraction");
516
517 if (isSingleWord())
518 return APInt(numBits, VAL >> bitPosition);
519
520 unsigned loBit = whichBit(bitPosition);
521 unsigned loWord = whichWord(bitPosition);
522 unsigned hiWord = whichWord(bitPosition + numBits - 1);
523
524 // Single word result extracting bits from a single word source.
525 if (loWord == hiWord)
526 return APInt(numBits, pVal[loWord] >> loBit);
527
528 // Extracting bits that start on a source word boundary can be done
529 // as a fast memory copy.
530 if (loBit == 0)
531 return APInt(numBits, makeArrayRef(pVal + loWord, 1 + hiWord - loWord));
532
533 // General case - shift + copy source words directly into place.
534 APInt Result(numBits, 0);
535 unsigned NumSrcWords = getNumWords();
536 unsigned NumDstWords = Result.getNumWords();
537
538 for (unsigned word = 0; word < NumDstWords; ++word) {
539 uint64_t w0 = pVal[loWord + word];
540 uint64_t w1 =
541 (loWord + word + 1) < NumSrcWords ? pVal[loWord + word + 1] : 0;
542 Result.pVal[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));
543 }
544
545 return Result.clearUnusedBits();
546}
547
Benjamin Kramer92d89982010-07-14 22:38:02 +0000548unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
Daniel Dunbar3a1efd112009-08-13 02:33:34 +0000549 assert(!str.empty() && "Invalid string length");
Simon Pilgrim4c0ea9d2017-02-23 16:07:04 +0000550 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
Douglas Gregor663c0682011-09-14 15:54:46 +0000551 radix == 36) &&
552 "Radix should be 2, 8, 10, 16, or 36!");
Daniel Dunbar3a1efd112009-08-13 02:33:34 +0000553
554 size_t slen = str.size();
Reid Spencer9329e7b2007-04-13 19:19:07 +0000555
Eric Christopher43a1dec2009-08-21 04:10:31 +0000556 // Each computation below needs to know if it's negative.
Erick Tryzelaar1264bcb2009-08-21 03:15:14 +0000557 StringRef::iterator p = str.begin();
Eric Christopher43a1dec2009-08-21 04:10:31 +0000558 unsigned isNegative = *p == '-';
Erick Tryzelaar1264bcb2009-08-21 03:15:14 +0000559 if (*p == '-' || *p == '+') {
560 p++;
Reid Spencer9329e7b2007-04-13 19:19:07 +0000561 slen--;
Eric Christopher43a1dec2009-08-21 04:10:31 +0000562 assert(slen && "String is only a sign, needs a value.");
Reid Spencer9329e7b2007-04-13 19:19:07 +0000563 }
Eric Christopher43a1dec2009-08-21 04:10:31 +0000564
Reid Spencer9329e7b2007-04-13 19:19:07 +0000565 // For radixes of power-of-two values, the bits required is accurately and
566 // easily computed
567 if (radix == 2)
568 return slen + isNegative;
569 if (radix == 8)
570 return slen * 3 + isNegative;
571 if (radix == 16)
572 return slen * 4 + isNegative;
573
Douglas Gregor663c0682011-09-14 15:54:46 +0000574 // FIXME: base 36
Simon Pilgrim4c0ea9d2017-02-23 16:07:04 +0000575
Reid Spencer9329e7b2007-04-13 19:19:07 +0000576 // This is grossly inefficient but accurate. We could probably do something
577 // with a computation of roughly slen*64/20 and then adjust by the value of
578 // the first few digits. But, I'm not sure how accurate that could be.
579
580 // Compute a sufficient number of bits that is always large enough but might
Erick Tryzelaardadb15712009-08-21 03:15:28 +0000581 // be too large. This avoids the assertion in the constructor. This
582 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
583 // bits in that case.
Simon Pilgrim4c0ea9d2017-02-23 16:07:04 +0000584 unsigned sufficient
Douglas Gregor663c0682011-09-14 15:54:46 +0000585 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
586 : (slen == 1 ? 7 : slen * 16/3);
Reid Spencer9329e7b2007-04-13 19:19:07 +0000587
588 // Convert to the actual binary value.
Erick Tryzelaar1264bcb2009-08-21 03:15:14 +0000589 APInt tmp(sufficient, StringRef(p, slen), radix);
Reid Spencer9329e7b2007-04-13 19:19:07 +0000590
Erick Tryzelaardadb15712009-08-21 03:15:28 +0000591 // Compute how many bits are required. If the log is infinite, assume we need
592 // just bit.
593 unsigned log = tmp.logBase2();
594 if (log == (unsigned)-1) {
595 return isNegative + 1;
596 } else {
597 return isNegative + log + 1;
598 }
Reid Spencer9329e7b2007-04-13 19:19:07 +0000599}
600
Chandler Carruth71bd7d12012-03-04 12:02:57 +0000601hash_code llvm::hash_value(const APInt &Arg) {
602 if (Arg.isSingleWord())
603 return hash_combine(Arg.VAL);
Reid Spencerb2bc9852007-02-26 21:02:27 +0000604
Chandler Carruth71bd7d12012-03-04 12:02:57 +0000605 return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
Reid Spencerb2bc9852007-02-26 21:02:27 +0000606}
607
Benjamin Kramerb4b51502015-03-25 16:49:59 +0000608bool APInt::isSplat(unsigned SplatSizeInBits) const {
609 assert(getBitWidth() % SplatSizeInBits == 0 &&
610 "SplatSizeInBits must divide width!");
611 // We can check that all parts of an integer are equal by making use of a
612 // little trick: rotate and check if it's still the same value.
613 return *this == rotl(SplatSizeInBits);
614}
615
Pawel Bylica6eeeac72015-04-06 13:31:39 +0000616/// This function returns the high "numBits" bits of this APInt.
Chris Lattner77527f52009-01-21 18:09:24 +0000617APInt APInt::getHiBits(unsigned numBits) const {
Craig Toppere7e35602017-03-31 18:48:14 +0000618 return this->lshr(BitWidth - numBits);
Zhou Shengdac63782007-02-06 03:00:16 +0000619}
620
Pawel Bylica6eeeac72015-04-06 13:31:39 +0000621/// This function returns the low "numBits" bits of this APInt.
Chris Lattner77527f52009-01-21 18:09:24 +0000622APInt APInt::getLoBits(unsigned numBits) const {
Craig Toppere7e35602017-03-31 18:48:14 +0000623 APInt Result(getLowBitsSet(BitWidth, numBits));
624 Result &= *this;
625 return Result;
Zhou Shengdac63782007-02-06 03:00:16 +0000626}
627
Chris Lattner77527f52009-01-21 18:09:24 +0000628unsigned APInt::countLeadingZerosSlowCase() const {
Matthias Brauna6be4e82016-02-15 20:06:22 +0000629 unsigned Count = 0;
630 for (int i = getNumWords()-1; i >= 0; --i) {
Craig Topper55229b72017-04-02 19:17:22 +0000631 uint64_t V = pVal[i];
Matthias Brauna6be4e82016-02-15 20:06:22 +0000632 if (V == 0)
Chris Lattner1ac3e252008-08-20 17:02:31 +0000633 Count += APINT_BITS_PER_WORD;
634 else {
Matthias Brauna6be4e82016-02-15 20:06:22 +0000635 Count += llvm::countLeadingZeros(V);
Chris Lattner1ac3e252008-08-20 17:02:31 +0000636 break;
Reid Spencer74cf82e2007-02-21 00:29:48 +0000637 }
Zhou Shengdac63782007-02-06 03:00:16 +0000638 }
Matthias Brauna6be4e82016-02-15 20:06:22 +0000639 // Adjust for unused bits in the most significant word (they are zero).
640 unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
641 Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
John McCalldf951bd2010-02-03 03:42:44 +0000642 return Count;
Zhou Shengdac63782007-02-06 03:00:16 +0000643}
644
Chris Lattner77527f52009-01-21 18:09:24 +0000645unsigned APInt::countLeadingOnes() const {
Reid Spencer31acef52007-02-27 21:59:26 +0000646 if (isSingleWord())
Benjamin Kramer5f6a9072015-02-12 15:35:40 +0000647 return llvm::countLeadingOnes(VAL << (APINT_BITS_PER_WORD - BitWidth));
Reid Spencer31acef52007-02-27 21:59:26 +0000648
Chris Lattner77527f52009-01-21 18:09:24 +0000649 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
Torok Edwinec39eb82009-01-27 18:06:03 +0000650 unsigned shift;
651 if (!highWordBits) {
652 highWordBits = APINT_BITS_PER_WORD;
653 shift = 0;
654 } else {
655 shift = APINT_BITS_PER_WORD - highWordBits;
656 }
Reid Spencer31acef52007-02-27 21:59:26 +0000657 int i = getNumWords() - 1;
Benjamin Kramer5f6a9072015-02-12 15:35:40 +0000658 unsigned Count = llvm::countLeadingOnes(pVal[i] << shift);
Reid Spencer31acef52007-02-27 21:59:26 +0000659 if (Count == highWordBits) {
660 for (i--; i >= 0; --i) {
Craig Topper5e113742017-04-22 06:31:36 +0000661 if (pVal[i] == WORD_MAX)
Reid Spencer31acef52007-02-27 21:59:26 +0000662 Count += APINT_BITS_PER_WORD;
663 else {
Benjamin Kramer5f6a9072015-02-12 15:35:40 +0000664 Count += llvm::countLeadingOnes(pVal[i]);
Reid Spencer31acef52007-02-27 21:59:26 +0000665 break;
666 }
667 }
668 }
669 return Count;
670}
671
Chris Lattner77527f52009-01-21 18:09:24 +0000672unsigned APInt::countTrailingZeros() const {
Zhou Shengdac63782007-02-06 03:00:16 +0000673 if (isSingleWord())
Michael J. Spencerdf1ecbd72013-05-24 22:23:49 +0000674 return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth);
Chris Lattner77527f52009-01-21 18:09:24 +0000675 unsigned Count = 0;
676 unsigned i = 0;
Reid Spenceraa8dcfe2007-02-26 07:44:38 +0000677 for (; i < getNumWords() && pVal[i] == 0; ++i)
678 Count += APINT_BITS_PER_WORD;
679 if (i < getNumWords())
Michael J. Spencerdf1ecbd72013-05-24 22:23:49 +0000680 Count += llvm::countTrailingZeros(pVal[i]);
Chris Lattnerc2c4c742007-11-23 22:36:25 +0000681 return std::min(Count, BitWidth);
Zhou Shengdac63782007-02-06 03:00:16 +0000682}
683
Chris Lattner77527f52009-01-21 18:09:24 +0000684unsigned APInt::countTrailingOnesSlowCase() const {
685 unsigned Count = 0;
686 unsigned i = 0;
Craig Topper5e113742017-04-22 06:31:36 +0000687 for (; i < getNumWords() && pVal[i] == WORD_MAX; ++i)
Dan Gohman8b4fa9d2008-02-13 21:11:05 +0000688 Count += APINT_BITS_PER_WORD;
689 if (i < getNumWords())
Benjamin Kramer5f6a9072015-02-12 15:35:40 +0000690 Count += llvm::countTrailingOnes(pVal[i]);
Craig Topper3a29e3b82017-04-22 19:59:11 +0000691 assert(Count <= BitWidth);
692 return Count;
Dan Gohman8b4fa9d2008-02-13 21:11:05 +0000693}
694
Chris Lattner77527f52009-01-21 18:09:24 +0000695unsigned APInt::countPopulationSlowCase() const {
696 unsigned Count = 0;
697 for (unsigned i = 0; i < getNumWords(); ++i)
Benjamin Kramer5f6a9072015-02-12 15:35:40 +0000698 Count += llvm::countPopulation(pVal[i]);
Zhou Shengdac63782007-02-06 03:00:16 +0000699 return Count;
700}
701
Craig Topperbaa392e2017-04-20 02:11:27 +0000702bool APInt::intersectsSlowCase(const APInt &RHS) const {
703 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
704 if ((pVal[i] & RHS.pVal[i]) != 0)
705 return true;
706
707 return false;
708}
709
Craig Toppera8129a12017-04-20 16:17:13 +0000710bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
711 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
712 if ((pVal[i] & ~RHS.pVal[i]) != 0)
713 return false;
714
715 return true;
716}
717
Reid Spencer1d072122007-02-16 22:36:51 +0000718APInt APInt::byteSwap() const {
719 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
720 if (BitWidth == 16)
Jeff Cohene06855e2007-03-20 20:42:36 +0000721 return APInt(BitWidth, ByteSwap_16(uint16_t(VAL)));
Richard Smith4f9a8082011-11-23 21:33:37 +0000722 if (BitWidth == 32)
Chris Lattner77527f52009-01-21 18:09:24 +0000723 return APInt(BitWidth, ByteSwap_32(unsigned(VAL)));
Richard Smith4f9a8082011-11-23 21:33:37 +0000724 if (BitWidth == 48) {
Chris Lattner77527f52009-01-21 18:09:24 +0000725 unsigned Tmp1 = unsigned(VAL >> 16);
Zhou Shengcfa2ac02007-02-15 06:36:31 +0000726 Tmp1 = ByteSwap_32(Tmp1);
Jeff Cohene06855e2007-03-20 20:42:36 +0000727 uint16_t Tmp2 = uint16_t(VAL);
Zhou Shengcfa2ac02007-02-15 06:36:31 +0000728 Tmp2 = ByteSwap_16(Tmp2);
Jeff Cohene06855e2007-03-20 20:42:36 +0000729 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
Zhou Shengcfa2ac02007-02-15 06:36:31 +0000730 }
Richard Smith4f9a8082011-11-23 21:33:37 +0000731 if (BitWidth == 64)
732 return APInt(BitWidth, ByteSwap_64(VAL));
733
734 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
735 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
736 Result.pVal[I] = ByteSwap_64(pVal[N - I - 1]);
737 if (Result.BitWidth != BitWidth) {
Richard Smith55bd3752017-04-13 20:29:59 +0000738 Result.lshrInPlace(Result.BitWidth - BitWidth);
Richard Smith4f9a8082011-11-23 21:33:37 +0000739 Result.BitWidth = BitWidth;
740 }
741 return Result;
Zhou Shengdac63782007-02-06 03:00:16 +0000742}
743
Matt Arsenault155dda92016-03-21 15:00:35 +0000744APInt APInt::reverseBits() const {
745 switch (BitWidth) {
746 case 64:
747 return APInt(BitWidth, llvm::reverseBits<uint64_t>(VAL));
748 case 32:
749 return APInt(BitWidth, llvm::reverseBits<uint32_t>(VAL));
750 case 16:
751 return APInt(BitWidth, llvm::reverseBits<uint16_t>(VAL));
752 case 8:
753 return APInt(BitWidth, llvm::reverseBits<uint8_t>(VAL));
754 default:
755 break;
756 }
757
758 APInt Val(*this);
Craig Topper9eaef072017-04-18 05:02:21 +0000759 APInt Reversed(BitWidth, 0);
760 unsigned S = BitWidth;
Matt Arsenault155dda92016-03-21 15:00:35 +0000761
Craig Topper9eaef072017-04-18 05:02:21 +0000762 for (; Val != 0; Val.lshrInPlace(1)) {
Matt Arsenault155dda92016-03-21 15:00:35 +0000763 Reversed <<= 1;
Craig Topper9eaef072017-04-18 05:02:21 +0000764 Reversed |= Val[0];
Matt Arsenault155dda92016-03-21 15:00:35 +0000765 --S;
766 }
767
768 Reversed <<= S;
769 return Reversed;
770}
771
Craig Topper278ebd22017-04-01 20:30:57 +0000772APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {
Richard Smith55bd3752017-04-13 20:29:59 +0000773 // Fast-path a common case.
774 if (A == B) return A;
775
776 // Corner cases: if either operand is zero, the other is the gcd.
777 if (!A) return B;
778 if (!B) return A;
779
780 // Count common powers of 2 and remove all other powers of 2.
781 unsigned Pow2;
782 {
783 unsigned Pow2_A = A.countTrailingZeros();
784 unsigned Pow2_B = B.countTrailingZeros();
785 if (Pow2_A > Pow2_B) {
786 A.lshrInPlace(Pow2_A - Pow2_B);
787 Pow2 = Pow2_B;
788 } else if (Pow2_B > Pow2_A) {
789 B.lshrInPlace(Pow2_B - Pow2_A);
790 Pow2 = Pow2_A;
791 } else {
792 Pow2 = Pow2_A;
793 }
Zhou Shengdac63782007-02-06 03:00:16 +0000794 }
Richard Smith55bd3752017-04-13 20:29:59 +0000795
796 // Both operands are odd multiples of 2^Pow_2:
797 //
798 // gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))
799 //
800 // This is a modified version of Stein's algorithm, taking advantage of
801 // efficient countTrailingZeros().
802 while (A != B) {
803 if (A.ugt(B)) {
804 A -= B;
805 A.lshrInPlace(A.countTrailingZeros() - Pow2);
806 } else {
807 B -= A;
808 B.lshrInPlace(B.countTrailingZeros() - Pow2);
809 }
810 }
811
Zhou Shengdac63782007-02-06 03:00:16 +0000812 return A;
813}
Chris Lattner28cbd1d2007-02-06 05:38:37 +0000814
Chris Lattner77527f52009-01-21 18:09:24 +0000815APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
Zhou Shengd707d632007-02-12 20:02:55 +0000816 union {
817 double D;
818 uint64_t I;
819 } T;
820 T.D = Double;
Reid Spencer974551a2007-02-27 01:28:10 +0000821
822 // Get the sign bit from the highest order bit
Zhou Shengd707d632007-02-12 20:02:55 +0000823 bool isNeg = T.I >> 63;
Reid Spencer974551a2007-02-27 01:28:10 +0000824
825 // Get the 11-bit exponent and adjust for the 1023 bit bias
Zhou Shengd707d632007-02-12 20:02:55 +0000826 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
Reid Spencer974551a2007-02-27 01:28:10 +0000827
828 // If the exponent is negative, the value is < 0 so just return 0.
Zhou Shengd707d632007-02-12 20:02:55 +0000829 if (exp < 0)
Reid Spencer66d0d572007-02-28 01:30:08 +0000830 return APInt(width, 0u);
Reid Spencer974551a2007-02-27 01:28:10 +0000831
832 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
833 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
834
835 // If the exponent doesn't shift all bits out of the mantissa
Zhou Shengd707d632007-02-12 20:02:55 +0000836 if (exp < 52)
Eric Christopher820256b2009-08-21 04:06:45 +0000837 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
Reid Spencer54abdcf2007-02-27 18:23:40 +0000838 APInt(width, mantissa >> (52 - exp));
839
840 // If the client didn't provide enough bits for us to shift the mantissa into
841 // then the result is undefined, just return 0
842 if (width <= exp - 52)
843 return APInt(width, 0);
Reid Spencer974551a2007-02-27 01:28:10 +0000844
845 // Otherwise, we have to shift the mantissa bits up to the right location
Reid Spencer54abdcf2007-02-27 18:23:40 +0000846 APInt Tmp(width, mantissa);
Craig Topper5f68af02017-04-23 05:18:31 +0000847 Tmp <<= (unsigned)exp - 52;
Zhou Shengd707d632007-02-12 20:02:55 +0000848 return isNeg ? -Tmp : Tmp;
849}
850
Pawel Bylica6eeeac72015-04-06 13:31:39 +0000851/// This function converts this APInt to a double.
Zhou Shengd707d632007-02-12 20:02:55 +0000852/// The layout for double is as following (IEEE Standard 754):
853/// --------------------------------------
854/// | Sign Exponent Fraction Bias |
855/// |-------------------------------------- |
856/// | 1[63] 11[62-52] 52[51-00] 1023 |
Eric Christopher820256b2009-08-21 04:06:45 +0000857/// --------------------------------------
Reid Spencer1d072122007-02-16 22:36:51 +0000858double APInt::roundToDouble(bool isSigned) const {
Reid Spencerfb77b2b2007-02-20 08:51:03 +0000859
860 // Handle the simple case where the value is contained in one uint64_t.
Dale Johannesen54be7852009-08-12 18:04:11 +0000861 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
Reid Spencerbe4ddf62007-02-18 20:09:41 +0000862 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
863 if (isSigned) {
David Majnemer03992262016-06-24 21:15:36 +0000864 int64_t sext = SignExtend64(getWord(0), BitWidth);
Reid Spencerbe4ddf62007-02-18 20:09:41 +0000865 return double(sext);
866 } else
Dale Johannesen34c08bb2009-08-12 17:42:34 +0000867 return double(getWord(0));
Reid Spencerbe4ddf62007-02-18 20:09:41 +0000868 }
869
Reid Spencerfb77b2b2007-02-20 08:51:03 +0000870 // Determine if the value is negative.
Reid Spencer1d072122007-02-16 22:36:51 +0000871 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
Reid Spencerfb77b2b2007-02-20 08:51:03 +0000872
873 // Construct the absolute value if we're negative.
Zhou Shengd707d632007-02-12 20:02:55 +0000874 APInt Tmp(isNeg ? -(*this) : (*this));
Reid Spencerfb77b2b2007-02-20 08:51:03 +0000875
876 // Figure out how many bits we're using.
Chris Lattner77527f52009-01-21 18:09:24 +0000877 unsigned n = Tmp.getActiveBits();
Zhou Shengd707d632007-02-12 20:02:55 +0000878
Reid Spencerfb77b2b2007-02-20 08:51:03 +0000879 // The exponent (without bias normalization) is just the number of bits
880 // we are using. Note that the sign bit is gone since we constructed the
881 // absolute value.
882 uint64_t exp = n;
Zhou Shengd707d632007-02-12 20:02:55 +0000883
Reid Spencerfb77b2b2007-02-20 08:51:03 +0000884 // Return infinity for exponent overflow
885 if (exp > 1023) {
886 if (!isSigned || !isNeg)
Jeff Cohene06855e2007-03-20 20:42:36 +0000887 return std::numeric_limits<double>::infinity();
Eric Christopher820256b2009-08-21 04:06:45 +0000888 else
Jeff Cohene06855e2007-03-20 20:42:36 +0000889 return -std::numeric_limits<double>::infinity();
Reid Spencerfb77b2b2007-02-20 08:51:03 +0000890 }
891 exp += 1023; // Increment for 1023 bias
892
893 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
894 // extract the high 52 bits from the correct words in pVal.
Zhou Shengd707d632007-02-12 20:02:55 +0000895 uint64_t mantissa;
Reid Spencerfb77b2b2007-02-20 08:51:03 +0000896 unsigned hiWord = whichWord(n-1);
897 if (hiWord == 0) {
898 mantissa = Tmp.pVal[0];
899 if (n > 52)
900 mantissa >>= n - 52; // shift down, we want the top 52 bits.
901 } else {
902 assert(hiWord > 0 && "huh?");
903 uint64_t hibits = Tmp.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
904 uint64_t lobits = Tmp.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
905 mantissa = hibits | lobits;
906 }
907
Zhou Shengd707d632007-02-12 20:02:55 +0000908 // The leading bit of mantissa is implicit, so get rid of it.
Reid Spencerfbd48a52007-02-18 00:44:22 +0000909 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
Zhou Shengd707d632007-02-12 20:02:55 +0000910 union {
911 double D;
912 uint64_t I;
913 } T;
914 T.I = sign | (exp << 52) | mantissa;
915 return T.D;
916}
917
Reid Spencer1d072122007-02-16 22:36:51 +0000918// Truncate to new width.
Jay Foad583abbc2010-12-07 08:25:19 +0000919APInt APInt::trunc(unsigned width) const {
Reid Spencer1d072122007-02-16 22:36:51 +0000920 assert(width < BitWidth && "Invalid APInt Truncate request");
Chris Lattner1ac3e252008-08-20 17:02:31 +0000921 assert(width && "Can't truncate to 0 bits");
Jay Foad583abbc2010-12-07 08:25:19 +0000922
923 if (width <= APINT_BITS_PER_WORD)
924 return APInt(width, getRawData()[0]);
925
926 APInt Result(getMemory(getNumWords(width)), width);
927
928 // Copy full words.
929 unsigned i;
930 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
931 Result.pVal[i] = pVal[i];
932
933 // Truncate and copy any partial word.
934 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
935 if (bits != 0)
936 Result.pVal[i] = pVal[i] << bits >> bits;
937
938 return Result;
Reid Spencer1d072122007-02-16 22:36:51 +0000939}
940
941// Sign extend to a new width.
Jay Foad583abbc2010-12-07 08:25:19 +0000942APInt APInt::sext(unsigned width) const {
Reid Spencer1d072122007-02-16 22:36:51 +0000943 assert(width > BitWidth && "Invalid APInt SignExtend request");
Jay Foad583abbc2010-12-07 08:25:19 +0000944
945 if (width <= APINT_BITS_PER_WORD) {
946 uint64_t val = VAL << (APINT_BITS_PER_WORD - BitWidth);
947 val = (int64_t)val >> (width - BitWidth);
948 return APInt(width, val >> (APINT_BITS_PER_WORD - width));
Reid Spencerb6b5cc32007-02-25 23:44:53 +0000949 }
950
Jay Foad583abbc2010-12-07 08:25:19 +0000951 APInt Result(getMemory(getNumWords(width)), width);
Reid Spencerb6b5cc32007-02-25 23:44:53 +0000952
Jay Foad583abbc2010-12-07 08:25:19 +0000953 // Copy full words.
954 unsigned i;
955 uint64_t word = 0;
956 for (i = 0; i != BitWidth / APINT_BITS_PER_WORD; i++) {
957 word = getRawData()[i];
958 Result.pVal[i] = word;
Reid Spencerb6b5cc32007-02-25 23:44:53 +0000959 }
960
Jay Foad583abbc2010-12-07 08:25:19 +0000961 // Read and sign-extend any partial word.
962 unsigned bits = (0 - BitWidth) % APINT_BITS_PER_WORD;
963 if (bits != 0)
964 word = (int64_t)getRawData()[i] << bits >> bits;
965 else
966 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
967
968 // Write remaining full words.
969 for (; i != width / APINT_BITS_PER_WORD; i++) {
970 Result.pVal[i] = word;
971 word = (int64_t)word >> (APINT_BITS_PER_WORD - 1);
Reid Spencerb6b5cc32007-02-25 23:44:53 +0000972 }
Jay Foad583abbc2010-12-07 08:25:19 +0000973
974 // Write any partial word.
975 bits = (0 - width) % APINT_BITS_PER_WORD;
976 if (bits != 0)
977 Result.pVal[i] = word << bits >> bits;
978
979 return Result;
Reid Spencer1d072122007-02-16 22:36:51 +0000980}
981
982// Zero extend to a new width.
Jay Foad583abbc2010-12-07 08:25:19 +0000983APInt APInt::zext(unsigned width) const {
Reid Spencer1d072122007-02-16 22:36:51 +0000984 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
Jay Foad583abbc2010-12-07 08:25:19 +0000985
986 if (width <= APINT_BITS_PER_WORD)
987 return APInt(width, VAL);
988
989 APInt Result(getMemory(getNumWords(width)), width);
990
991 // Copy words.
992 unsigned i;
993 for (i = 0; i != getNumWords(); i++)
994 Result.pVal[i] = getRawData()[i];
995
996 // Zero remaining words.
997 memset(&Result.pVal[i], 0, (Result.getNumWords() - i) * APINT_WORD_SIZE);
998
999 return Result;
Reid Spencer1d072122007-02-16 22:36:51 +00001000}
1001
Jay Foad583abbc2010-12-07 08:25:19 +00001002APInt APInt::zextOrTrunc(unsigned width) const {
Reid Spencer742d1702007-03-01 17:15:32 +00001003 if (BitWidth < width)
1004 return zext(width);
1005 if (BitWidth > width)
1006 return trunc(width);
1007 return *this;
1008}
1009
Jay Foad583abbc2010-12-07 08:25:19 +00001010APInt APInt::sextOrTrunc(unsigned width) const {
Reid Spencer742d1702007-03-01 17:15:32 +00001011 if (BitWidth < width)
1012 return sext(width);
1013 if (BitWidth > width)
1014 return trunc(width);
1015 return *this;
1016}
1017
Rafael Espindolabb893fe2012-01-27 23:33:07 +00001018APInt APInt::zextOrSelf(unsigned width) const {
1019 if (BitWidth < width)
1020 return zext(width);
1021 return *this;
1022}
1023
1024APInt APInt::sextOrSelf(unsigned width) const {
1025 if (BitWidth < width)
1026 return sext(width);
1027 return *this;
1028}
1029
Zhou Shenge93db8f2007-02-09 07:48:24 +00001030/// Arithmetic right-shift this APInt by shiftAmt.
Zhou Shengfbf61ea2007-02-08 14:35:19 +00001031/// @brief Arithmetic right-shift function.
Renato Golincc4a9122017-04-23 12:02:07 +00001032APInt APInt::ashr(const APInt &shiftAmt) const {
1033 return ashr((unsigned)shiftAmt.getLimitedValue(BitWidth));
Dan Gohman105c1d42008-02-29 01:40:47 +00001034}
1035
1036/// Arithmetic right-shift this APInt by shiftAmt.
1037/// @brief Arithmetic right-shift function.
Renato Golincc4a9122017-04-23 12:02:07 +00001038APInt APInt::ashr(unsigned shiftAmt) const {
1039 assert(shiftAmt <= BitWidth && "Invalid shift amount");
1040 // Handle a degenerate case
1041 if (shiftAmt == 0)
1042 return *this;
Reid Spencer1825dd02007-03-02 22:39:11 +00001043
Renato Golincc4a9122017-04-23 12:02:07 +00001044 // Handle single word shifts with built-in ashr
1045 if (isSingleWord()) {
1046 if (shiftAmt == BitWidth)
1047 return APInt(BitWidth, 0); // undefined
1048 return APInt(BitWidth, SignExtend64(VAL, BitWidth) >> shiftAmt);
1049 }
Reid Spencer522ca7c2007-02-25 01:56:07 +00001050
Renato Golincc4a9122017-04-23 12:02:07 +00001051 // If all the bits were shifted out, the result is, technically, undefined.
1052 // We return -1 if it was negative, 0 otherwise. We check this early to avoid
1053 // issues in the algorithm below.
1054 if (shiftAmt == BitWidth) {
1055 if (isNegative())
1056 return APInt(BitWidth, WORD_MAX, true);
1057 else
1058 return APInt(BitWidth, 0);
1059 }
Reid Spenceraa8dcfe2007-02-26 07:44:38 +00001060
Renato Golincc4a9122017-04-23 12:02:07 +00001061 // Create some space for the result.
1062 uint64_t * val = new uint64_t[getNumWords()];
1063
1064 // Compute some values needed by the following shift algorithms
1065 unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; // bits to shift per word
1066 unsigned offset = shiftAmt / APINT_BITS_PER_WORD; // word offset for shift
1067 unsigned breakWord = getNumWords() - 1 - offset; // last word affected
1068 unsigned bitsInWord = whichBit(BitWidth); // how many bits in last word?
1069 if (bitsInWord == 0)
1070 bitsInWord = APINT_BITS_PER_WORD;
1071
1072 // If we are shifting whole words, just move whole words
1073 if (wordShift == 0) {
1074 // Move the words containing significant bits
1075 for (unsigned i = 0; i <= breakWord; ++i)
1076 val[i] = pVal[i+offset]; // move whole word
1077
1078 // Adjust the top significant word for sign bit fill, if negative
1079 if (isNegative())
1080 if (bitsInWord < APINT_BITS_PER_WORD)
1081 val[breakWord] |= WORD_MAX << bitsInWord; // set high bits
Reid Spencer1825dd02007-03-02 22:39:11 +00001082 } else {
Renato Golincc4a9122017-04-23 12:02:07 +00001083 // Shift the low order words
1084 for (unsigned i = 0; i < breakWord; ++i) {
1085 // This combines the shifted corresponding word with the low bits from
1086 // the next word (shifted into this word's high bits).
1087 val[i] = (pVal[i+offset] >> wordShift) |
1088 (pVal[i+offset+1] << (APINT_BITS_PER_WORD - wordShift));
1089 }
1090
1091 // Shift the break word. In this case there are no bits from the next word
1092 // to include in this word.
1093 val[breakWord] = pVal[breakWord+offset] >> wordShift;
1094
1095 // Deal with sign extension in the break word, and possibly the word before
1096 // it.
1097 if (isNegative()) {
1098 if (wordShift > bitsInWord) {
1099 if (breakWord > 0)
1100 val[breakWord-1] |=
1101 WORD_MAX << (APINT_BITS_PER_WORD - (wordShift - bitsInWord));
1102 val[breakWord] |= WORD_MAX;
1103 } else
1104 val[breakWord] |= WORD_MAX << (bitsInWord - wordShift);
Chris Lattnerdad2d092007-05-03 18:15:36 +00001105 }
Reid Spenceraa8dcfe2007-02-26 07:44:38 +00001106 }
1107
Renato Golincc4a9122017-04-23 12:02:07 +00001108 // Remaining words are 0 or -1, just assign them.
1109 uint64_t fillValue = (isNegative() ? WORD_MAX : 0);
1110 for (unsigned i = breakWord+1; i < getNumWords(); ++i)
1111 val[i] = fillValue;
1112 APInt Result(val, BitWidth);
1113 Result.clearUnusedBits();
1114 return Result;
Zhou Shengfbf61ea2007-02-08 14:35:19 +00001115}
1116
Zhou Shenge93db8f2007-02-09 07:48:24 +00001117/// Logical right-shift this APInt by shiftAmt.
Zhou Shengfbf61ea2007-02-08 14:35:19 +00001118/// @brief Logical right-shift function.
Craig Topperfc947bc2017-04-18 17:14:21 +00001119void APInt::lshrInPlace(const APInt &shiftAmt) {
1120 lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
Dan Gohman105c1d42008-02-29 01:40:47 +00001121}
1122
1123/// Logical right-shift this APInt by shiftAmt.
1124/// @brief Logical right-shift function.
Craig Topperae8bd672017-04-18 19:13:27 +00001125void APInt::lshrSlowCase(unsigned ShiftAmt) {
Craig Topperfc947bc2017-04-18 17:14:21 +00001126 tcShiftRight(pVal, getNumWords(), ShiftAmt);
Zhou Shengfbf61ea2007-02-08 14:35:19 +00001127}
1128
Zhou Shenge93db8f2007-02-09 07:48:24 +00001129/// Left-shift this APInt by shiftAmt.
Zhou Shengfbf61ea2007-02-08 14:35:19 +00001130/// @brief Left-shift function.
Craig Topper5f68af02017-04-23 05:18:31 +00001131APInt &APInt::operator<<=(const APInt &shiftAmt) {
Nick Lewycky030c4502009-01-19 17:42:33 +00001132 // It's undefined behavior in C to shift by BitWidth or greater.
Craig Topper5f68af02017-04-23 05:18:31 +00001133 *this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);
1134 return *this;
Dan Gohman105c1d42008-02-29 01:40:47 +00001135}
1136
Craig Toppera8a4f0d2017-04-18 04:39:48 +00001137void APInt::shlSlowCase(unsigned ShiftAmt) {
1138 tcShiftLeft(pVal, getNumWords(), ShiftAmt);
1139 clearUnusedBits();
Zhou Shengfbf61ea2007-02-08 14:35:19 +00001140}
1141
Joey Gouly51c0ae52017-02-07 11:58:22 +00001142// Calculate the rotate amount modulo the bit width.
1143static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
1144 unsigned rotBitWidth = rotateAmt.getBitWidth();
1145 APInt rot = rotateAmt;
1146 if (rotBitWidth < BitWidth) {
1147 // Extend the rotate APInt, so that the urem doesn't divide by 0.
1148 // e.g. APInt(1, 32) would give APInt(1, 0).
1149 rot = rotateAmt.zext(BitWidth);
1150 }
1151 rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
1152 return rot.getLimitedValue(BitWidth);
1153}
1154
Dan Gohman105c1d42008-02-29 01:40:47 +00001155APInt APInt::rotl(const APInt &rotateAmt) const {
Joey Gouly51c0ae52017-02-07 11:58:22 +00001156 return rotl(rotateModulo(BitWidth, rotateAmt));
Dan Gohman105c1d42008-02-29 01:40:47 +00001157}
1158
Chris Lattner77527f52009-01-21 18:09:24 +00001159APInt APInt::rotl(unsigned rotateAmt) const {
Eli Friedman2aae94f2011-12-22 03:15:35 +00001160 rotateAmt %= BitWidth;
Reid Spencer98ed7db2007-05-14 00:15:28 +00001161 if (rotateAmt == 0)
1162 return *this;
Eli Friedman2aae94f2011-12-22 03:15:35 +00001163 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
Reid Spencer4c50b522007-05-13 23:44:59 +00001164}
1165
Dan Gohman105c1d42008-02-29 01:40:47 +00001166APInt APInt::rotr(const APInt &rotateAmt) const {
Joey Gouly51c0ae52017-02-07 11:58:22 +00001167 return rotr(rotateModulo(BitWidth, rotateAmt));
Dan Gohman105c1d42008-02-29 01:40:47 +00001168}
1169
Chris Lattner77527f52009-01-21 18:09:24 +00001170APInt APInt::rotr(unsigned rotateAmt) const {
Eli Friedman2aae94f2011-12-22 03:15:35 +00001171 rotateAmt %= BitWidth;
Reid Spencer98ed7db2007-05-14 00:15:28 +00001172 if (rotateAmt == 0)
1173 return *this;
Eli Friedman2aae94f2011-12-22 03:15:35 +00001174 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
Reid Spencer4c50b522007-05-13 23:44:59 +00001175}
Reid Spencerd99feaf2007-03-01 05:39:56 +00001176
1177// Square Root - this method computes and returns the square root of "this".
1178// Three mechanisms are used for computation. For small values (<= 5 bits),
1179// a table lookup is done. This gets some performance for common cases. For
1180// values using less than 52 bits, the value is converted to double and then
1181// the libc sqrt function is called. The result is rounded and then converted
1182// back to a uint64_t which is then used to construct the result. Finally,
Eric Christopher820256b2009-08-21 04:06:45 +00001183// the Babylonian method for computing square roots is used.
Reid Spencerd99feaf2007-03-01 05:39:56 +00001184APInt APInt::sqrt() const {
1185
1186 // Determine the magnitude of the value.
Chris Lattner77527f52009-01-21 18:09:24 +00001187 unsigned magnitude = getActiveBits();
Reid Spencerd99feaf2007-03-01 05:39:56 +00001188
1189 // Use a fast table for some small values. This also gets rid of some
1190 // rounding errors in libc sqrt for small values.
1191 if (magnitude <= 5) {
Reid Spencer2f6ad4d2007-03-01 17:47:31 +00001192 static const uint8_t results[32] = {
Reid Spencerc8841d22007-03-01 06:23:32 +00001193 /* 0 */ 0,
1194 /* 1- 2 */ 1, 1,
Eric Christopher820256b2009-08-21 04:06:45 +00001195 /* 3- 6 */ 2, 2, 2, 2,
Reid Spencerc8841d22007-03-01 06:23:32 +00001196 /* 7-12 */ 3, 3, 3, 3, 3, 3,
1197 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1198 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1199 /* 31 */ 6
1200 };
1201 return APInt(BitWidth, results[ (isSingleWord() ? VAL : pVal[0]) ]);
Reid Spencerd99feaf2007-03-01 05:39:56 +00001202 }
1203
1204 // If the magnitude of the value fits in less than 52 bits (the precision of
1205 // an IEEE double precision floating point value), then we can use the
1206 // libc sqrt function which will probably use a hardware sqrt computation.
1207 // This should be faster than the algorithm below.
Jeff Cohenb622c112007-03-05 00:00:42 +00001208 if (magnitude < 52) {
Eric Christopher820256b2009-08-21 04:06:45 +00001209 return APInt(BitWidth,
Reid Spencerd99feaf2007-03-01 05:39:56 +00001210 uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0])))));
Jeff Cohenb622c112007-03-05 00:00:42 +00001211 }
Reid Spencerd99feaf2007-03-01 05:39:56 +00001212
1213 // Okay, all the short cuts are exhausted. We must compute it. The following
1214 // is a classical Babylonian method for computing the square root. This code
Sanjay Patel4cb54e02014-09-11 15:41:01 +00001215 // was adapted to APInt from a wikipedia article on such computations.
Reid Spencerd99feaf2007-03-01 05:39:56 +00001216 // See http://www.wikipedia.org/ and go to the page named
Eric Christopher820256b2009-08-21 04:06:45 +00001217 // Calculate_an_integer_square_root.
Chris Lattner77527f52009-01-21 18:09:24 +00001218 unsigned nbits = BitWidth, i = 4;
Reid Spencerd99feaf2007-03-01 05:39:56 +00001219 APInt testy(BitWidth, 16);
1220 APInt x_old(BitWidth, 1);
1221 APInt x_new(BitWidth, 0);
1222 APInt two(BitWidth, 2);
1223
1224 // Select a good starting value using binary logarithms.
Eric Christopher820256b2009-08-21 04:06:45 +00001225 for (;; i += 2, testy = testy.shl(2))
Reid Spencerd99feaf2007-03-01 05:39:56 +00001226 if (i >= nbits || this->ule(testy)) {
1227 x_old = x_old.shl(i / 2);
1228 break;
1229 }
1230
Eric Christopher820256b2009-08-21 04:06:45 +00001231 // Use the Babylonian method to arrive at the integer square root:
Reid Spencerd99feaf2007-03-01 05:39:56 +00001232 for (;;) {
1233 x_new = (this->udiv(x_old) + x_old).udiv(two);
1234 if (x_old.ule(x_new))
1235 break;
1236 x_old = x_new;
1237 }
1238
1239 // Make sure we return the closest approximation
Eric Christopher820256b2009-08-21 04:06:45 +00001240 // NOTE: The rounding calculation below is correct. It will produce an
Reid Spencercf817562007-03-02 04:21:55 +00001241 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
Eric Christopher820256b2009-08-21 04:06:45 +00001242 // determined to be a rounding issue with pari/gp as it begins to use a
Reid Spencercf817562007-03-02 04:21:55 +00001243 // floating point representation after 192 bits. There are no discrepancies
1244 // between this algorithm and pari/gp for bit widths < 192 bits.
Reid Spencerd99feaf2007-03-01 05:39:56 +00001245 APInt square(x_old * x_old);
1246 APInt nextSquare((x_old + 1) * (x_old +1));
1247 if (this->ult(square))
1248 return x_old;
David Blaikie54c94622011-12-01 20:58:30 +00001249 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
1250 APInt midpoint((nextSquare - square).udiv(two));
1251 APInt offset(*this - square);
1252 if (offset.ult(midpoint))
1253 return x_old;
Reid Spencerd99feaf2007-03-01 05:39:56 +00001254 return x_old + 1;
1255}
1256
Wojciech Matyjewicz41b744d2008-06-23 19:39:50 +00001257/// Computes the multiplicative inverse of this APInt for a given modulo. The
1258/// iterative extended Euclidean algorithm is used to solve for this value,
1259/// however we simplify it to speed up calculating only the inverse, and take
1260/// advantage of div+rem calculations. We also use some tricks to avoid copying
1261/// (potentially large) APInts around.
1262APInt APInt::multiplicativeInverse(const APInt& modulo) const {
1263 assert(ult(modulo) && "This APInt must be smaller than the modulo");
1264
1265 // Using the properties listed at the following web page (accessed 06/21/08):
1266 // http://www.numbertheory.org/php/euclid.html
1267 // (especially the properties numbered 3, 4 and 9) it can be proved that
1268 // BitWidth bits suffice for all the computations in the algorithm implemented
1269 // below. More precisely, this number of bits suffice if the multiplicative
1270 // inverse exists, but may not suffice for the general extended Euclidean
1271 // algorithm.
1272
1273 APInt r[2] = { modulo, *this };
1274 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
1275 APInt q(BitWidth, 0);
Eric Christopher820256b2009-08-21 04:06:45 +00001276
Wojciech Matyjewicz41b744d2008-06-23 19:39:50 +00001277 unsigned i;
1278 for (i = 0; r[i^1] != 0; i ^= 1) {
1279 // An overview of the math without the confusing bit-flipping:
1280 // q = r[i-2] / r[i-1]
1281 // r[i] = r[i-2] % r[i-1]
1282 // t[i] = t[i-2] - t[i-1] * q
1283 udivrem(r[i], r[i^1], q, r[i]);
1284 t[i] -= t[i^1] * q;
1285 }
1286
1287 // If this APInt and the modulo are not coprime, there is no multiplicative
1288 // inverse, so return 0. We check this by looking at the next-to-last
1289 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
1290 // algorithm.
1291 if (r[i] != 1)
1292 return APInt(BitWidth, 0);
1293
1294 // The next-to-last t is the multiplicative inverse. However, we are
1295 // interested in a positive inverse. Calcuate a positive one from a negative
1296 // one if necessary. A simple addition of the modulo suffices because
Wojciech Matyjewiczf0d21cd2008-07-20 15:55:14 +00001297 // abs(t[i]) is known to be less than *this/2 (see the link above).
Wojciech Matyjewicz41b744d2008-06-23 19:39:50 +00001298 return t[i].isNegative() ? t[i] + modulo : t[i];
1299}
1300
Jay Foadfe0c6482009-04-30 10:15:35 +00001301/// Calculate the magic numbers required to implement a signed integer division
1302/// by a constant as a sequence of multiplies, adds and shifts. Requires that
1303/// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
1304/// Warren, Jr., chapter 10.
1305APInt::ms APInt::magic() const {
1306 const APInt& d = *this;
1307 unsigned p;
1308 APInt ad, anc, delta, q1, r1, q2, r2, t;
Jay Foadfe0c6482009-04-30 10:15:35 +00001309 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
Jay Foadfe0c6482009-04-30 10:15:35 +00001310 struct ms mag;
Eric Christopher820256b2009-08-21 04:06:45 +00001311
Jay Foadfe0c6482009-04-30 10:15:35 +00001312 ad = d.abs();
1313 t = signedMin + (d.lshr(d.getBitWidth() - 1));
1314 anc = t - 1 - t.urem(ad); // absolute value of nc
1315 p = d.getBitWidth() - 1; // initialize p
1316 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
1317 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
1318 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
1319 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
1320 do {
1321 p = p + 1;
1322 q1 = q1<<1; // update q1 = 2p/abs(nc)
1323 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
1324 if (r1.uge(anc)) { // must be unsigned comparison
1325 q1 = q1 + 1;
1326 r1 = r1 - anc;
1327 }
1328 q2 = q2<<1; // update q2 = 2p/abs(d)
1329 r2 = r2<<1; // update r2 = rem(2p/abs(d))
1330 if (r2.uge(ad)) { // must be unsigned comparison
1331 q2 = q2 + 1;
1332 r2 = r2 - ad;
1333 }
1334 delta = ad - r2;
Cameron Zwarich8731d0c2011-02-21 00:22:02 +00001335 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
Eric Christopher820256b2009-08-21 04:06:45 +00001336
Jay Foadfe0c6482009-04-30 10:15:35 +00001337 mag.m = q2 + 1;
1338 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
1339 mag.s = p - d.getBitWidth(); // resulting shift
1340 return mag;
1341}
1342
1343/// Calculate the magic numbers required to implement an unsigned integer
1344/// division by a constant as a sequence of multiplies, adds and shifts.
1345/// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
1346/// S. Warren, Jr., chapter 10.
Benjamin Kramer09a51ba2011-03-17 20:39:06 +00001347/// LeadingZeros can be used to simplify the calculation if the upper bits
Chris Lattner0ab5e2c2011-04-15 05:18:47 +00001348/// of the divided value are known zero.
Benjamin Kramer09a51ba2011-03-17 20:39:06 +00001349APInt::mu APInt::magicu(unsigned LeadingZeros) const {
Jay Foadfe0c6482009-04-30 10:15:35 +00001350 const APInt& d = *this;
1351 unsigned p;
1352 APInt nc, delta, q1, r1, q2, r2;
1353 struct mu magu;
1354 magu.a = 0; // initialize "add" indicator
Benjamin Kramer09a51ba2011-03-17 20:39:06 +00001355 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
Jay Foadfe0c6482009-04-30 10:15:35 +00001356 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
1357 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
1358
Benjamin Kramer3aab6a82012-07-11 18:31:59 +00001359 nc = allOnes - (allOnes - d).urem(d);
Jay Foadfe0c6482009-04-30 10:15:35 +00001360 p = d.getBitWidth() - 1; // initialize p
1361 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
1362 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
1363 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
1364 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
1365 do {
1366 p = p + 1;
1367 if (r1.uge(nc - r1)) {
1368 q1 = q1 + q1 + 1; // update q1
1369 r1 = r1 + r1 - nc; // update r1
1370 }
1371 else {
1372 q1 = q1+q1; // update q1
1373 r1 = r1+r1; // update r1
1374 }
1375 if ((r2 + 1).uge(d - r2)) {
1376 if (q2.uge(signedMax)) magu.a = 1;
1377 q2 = q2+q2 + 1; // update q2
1378 r2 = r2+r2 + 1 - d; // update r2
1379 }
1380 else {
1381 if (q2.uge(signedMin)) magu.a = 1;
1382 q2 = q2+q2; // update q2
1383 r2 = r2+r2 + 1; // update r2
1384 }
1385 delta = d - 1 - r2;
1386 } while (p < d.getBitWidth()*2 &&
1387 (q1.ult(delta) || (q1 == delta && r1 == 0)));
1388 magu.m = q2 + 1; // resulting magic number
1389 magu.s = p - d.getBitWidth(); // resulting shift
1390 return magu;
1391}
1392
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001393/// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
1394/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
1395/// variables here have the same names as in the algorithm. Comments explain
1396/// the algorithm and any deviation from it.
Chris Lattner77527f52009-01-21 18:09:24 +00001397static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r,
1398 unsigned m, unsigned n) {
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001399 assert(u && "Must provide dividend");
1400 assert(v && "Must provide divisor");
1401 assert(q && "Must provide quotient");
Yaron Keren39fc5a62015-03-26 19:45:19 +00001402 assert(u != v && u != q && v != q && "Must use different memory");
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001403 assert(n>1 && "n must be > 1");
1404
Yaron Keren39fc5a62015-03-26 19:45:19 +00001405 // b denotes the base of the number system. In our case b is 2^32.
George Burgess IV381fc0e2016-08-25 01:05:08 +00001406 const uint64_t b = uint64_t(1) << 32;
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001407
David Greenef32fcb42010-01-05 01:28:52 +00001408 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
1409 DEBUG(dbgs() << "KnuthDiv: original:");
1410 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1411 DEBUG(dbgs() << " by");
1412 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1413 DEBUG(dbgs() << '\n');
Eric Christopher820256b2009-08-21 04:06:45 +00001414 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
1415 // u and v by d. Note that we have taken Knuth's advice here to use a power
1416 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
1417 // 2 allows us to shift instead of multiply and it is easy to determine the
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001418 // shift amount from the leading zeros. We are basically normalizing the u
1419 // and v so that its high bits are shifted to the top of v's range without
1420 // overflow. Note that this can require an extra word in u so that u must
1421 // be of length m+n+1.
Michael J. Spencerdf1ecbd72013-05-24 22:23:49 +00001422 unsigned shift = countLeadingZeros(v[n-1]);
Chris Lattner77527f52009-01-21 18:09:24 +00001423 unsigned v_carry = 0;
1424 unsigned u_carry = 0;
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001425 if (shift) {
Chris Lattner77527f52009-01-21 18:09:24 +00001426 for (unsigned i = 0; i < m+n; ++i) {
1427 unsigned u_tmp = u[i] >> (32 - shift);
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001428 u[i] = (u[i] << shift) | u_carry;
1429 u_carry = u_tmp;
Reid Spencer100502d2007-02-17 03:16:00 +00001430 }
Chris Lattner77527f52009-01-21 18:09:24 +00001431 for (unsigned i = 0; i < n; ++i) {
1432 unsigned v_tmp = v[i] >> (32 - shift);
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001433 v[i] = (v[i] << shift) | v_carry;
1434 v_carry = v_tmp;
1435 }
1436 }
1437 u[m+n] = u_carry;
Yaron Keren39fc5a62015-03-26 19:45:19 +00001438
David Greenef32fcb42010-01-05 01:28:52 +00001439 DEBUG(dbgs() << "KnuthDiv: normal:");
1440 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1441 DEBUG(dbgs() << " by");
1442 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
1443 DEBUG(dbgs() << '\n');
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001444
1445 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
1446 int j = m;
1447 do {
David Greenef32fcb42010-01-05 01:28:52 +00001448 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
Eric Christopher820256b2009-08-21 04:06:45 +00001449 // D3. [Calculate q'.].
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001450 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
1451 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
1452 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
1453 // qp by 1, inrease rp by v[n-1], and repeat this test if rp < b. The test
1454 // on v[n-2] determines at high speed most of the cases in which the trial
Eric Christopher820256b2009-08-21 04:06:45 +00001455 // value qp is one too large, and it eliminates all cases where qp is two
1456 // too large.
Reid Spencercb292e42007-02-23 01:57:13 +00001457 uint64_t dividend = ((uint64_t(u[j+n]) << 32) + u[j+n-1]);
David Greenef32fcb42010-01-05 01:28:52 +00001458 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
Reid Spencercb292e42007-02-23 01:57:13 +00001459 uint64_t qp = dividend / v[n-1];
1460 uint64_t rp = dividend % v[n-1];
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001461 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1462 qp--;
1463 rp += v[n-1];
Reid Spencerdf6cf5a2007-02-24 10:01:42 +00001464 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
Reid Spencera5e0d202007-02-24 03:58:46 +00001465 qp--;
Reid Spencercb292e42007-02-23 01:57:13 +00001466 }
David Greenef32fcb42010-01-05 01:28:52 +00001467 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001468
Reid Spencercb292e42007-02-23 01:57:13 +00001469 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
1470 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
1471 // consists of a simple multiplication by a one-place number, combined with
Eric Christopher820256b2009-08-21 04:06:45 +00001472 // a subtraction.
Yaron Keren39fc5a62015-03-26 19:45:19 +00001473 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
1474 // this step is actually negative, (u[j+n]...u[j]) should be left as the
1475 // true value plus b**(n+1), namely as the b's complement of
1476 // the true value, and a "borrow" to the left should be remembered.
Pawel Bylica86ac4472015-04-24 07:38:39 +00001477 int64_t borrow = 0;
Chris Lattner77527f52009-01-21 18:09:24 +00001478 for (unsigned i = 0; i < n; ++i) {
Pawel Bylica86ac4472015-04-24 07:38:39 +00001479 uint64_t p = uint64_t(qp) * uint64_t(v[i]);
1480 int64_t subres = int64_t(u[j+i]) - borrow - (unsigned)p;
1481 u[j+i] = (unsigned)subres;
1482 borrow = (p >> 32) - (subres >> 32);
1483 DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]
Daniel Dunbar763ace92009-07-13 05:27:30 +00001484 << ", borrow = " << borrow << '\n');
Reid Spencera5e0d202007-02-24 03:58:46 +00001485 }
Pawel Bylica86ac4472015-04-24 07:38:39 +00001486 bool isNeg = u[j+n] < borrow;
1487 u[j+n] -= (unsigned)borrow;
1488
David Greenef32fcb42010-01-05 01:28:52 +00001489 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
1490 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
1491 DEBUG(dbgs() << '\n');
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001492
Eric Christopher820256b2009-08-21 04:06:45 +00001493 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001494 // negative, go to step D6; otherwise go on to step D7.
Chris Lattner77527f52009-01-21 18:09:24 +00001495 q[j] = (unsigned)qp;
Reid Spenceraa8dcfe2007-02-26 07:44:38 +00001496 if (isNeg) {
Eric Christopher820256b2009-08-21 04:06:45 +00001497 // D6. [Add back]. The probability that this step is necessary is very
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001498 // small, on the order of only 2/b. Make sure that test data accounts for
Eric Christopher820256b2009-08-21 04:06:45 +00001499 // this possibility. Decrease q[j] by 1
Reid Spencercb292e42007-02-23 01:57:13 +00001500 q[j]--;
Eric Christopher820256b2009-08-21 04:06:45 +00001501 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
1502 // A carry will occur to the left of u[j+n], and it should be ignored
Reid Spencercb292e42007-02-23 01:57:13 +00001503 // since it cancels with the borrow that occurred in D4.
1504 bool carry = false;
Chris Lattner77527f52009-01-21 18:09:24 +00001505 for (unsigned i = 0; i < n; i++) {
1506 unsigned limit = std::min(u[j+i],v[i]);
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001507 u[j+i] += v[i] + carry;
Reid Spencera5e0d202007-02-24 03:58:46 +00001508 carry = u[j+i] < limit || (carry && u[j+i] == limit);
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001509 }
Reid Spencera5e0d202007-02-24 03:58:46 +00001510 u[j+n] += carry;
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001511 }
David Greenef32fcb42010-01-05 01:28:52 +00001512 DEBUG(dbgs() << "KnuthDiv: after correction:");
Yaron Keren39fc5a62015-03-26 19:45:19 +00001513 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
David Greenef32fcb42010-01-05 01:28:52 +00001514 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001515
Reid Spencercb292e42007-02-23 01:57:13 +00001516 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
1517 } while (--j >= 0);
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001518
David Greenef32fcb42010-01-05 01:28:52 +00001519 DEBUG(dbgs() << "KnuthDiv: quotient:");
1520 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
1521 DEBUG(dbgs() << '\n');
Reid Spencera5e0d202007-02-24 03:58:46 +00001522
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001523 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
1524 // remainder may be obtained by dividing u[...] by d. If r is non-null we
1525 // compute the remainder (urem uses this).
1526 if (r) {
1527 // The value d is expressed by the "shift" value above since we avoided
1528 // multiplication by d by using a shift left. So, all we have to do is
Simon Pilgrim0099beb2017-03-09 13:57:04 +00001529 // shift right here.
Reid Spencer468ad9112007-02-24 20:38:01 +00001530 if (shift) {
Chris Lattner77527f52009-01-21 18:09:24 +00001531 unsigned carry = 0;
David Greenef32fcb42010-01-05 01:28:52 +00001532 DEBUG(dbgs() << "KnuthDiv: remainder:");
Reid Spencer468ad9112007-02-24 20:38:01 +00001533 for (int i = n-1; i >= 0; i--) {
1534 r[i] = (u[i] >> shift) | carry;
1535 carry = u[i] << (32 - shift);
David Greenef32fcb42010-01-05 01:28:52 +00001536 DEBUG(dbgs() << " " << r[i]);
Reid Spencer468ad9112007-02-24 20:38:01 +00001537 }
1538 } else {
1539 for (int i = n-1; i >= 0; i--) {
1540 r[i] = u[i];
David Greenef32fcb42010-01-05 01:28:52 +00001541 DEBUG(dbgs() << " " << r[i]);
Reid Spencer468ad9112007-02-24 20:38:01 +00001542 }
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001543 }
David Greenef32fcb42010-01-05 01:28:52 +00001544 DEBUG(dbgs() << '\n');
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001545 }
David Greenef32fcb42010-01-05 01:28:52 +00001546 DEBUG(dbgs() << '\n');
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001547}
1548
Benjamin Kramerc321e532016-06-08 19:09:22 +00001549void APInt::divide(const APInt &LHS, unsigned lhsWords, const APInt &RHS,
1550 unsigned rhsWords, APInt *Quotient, APInt *Remainder) {
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001551 assert(lhsWords >= rhsWords && "Fractional result");
1552
Eric Christopher820256b2009-08-21 04:06:45 +00001553 // First, compose the values into an array of 32-bit words instead of
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001554 // 64-bit words. This is a necessity of both the "short division" algorithm
Dan Gohman4a618822010-02-10 16:03:48 +00001555 // and the Knuth "classical algorithm" which requires there to be native
Eric Christopher820256b2009-08-21 04:06:45 +00001556 // operations for +, -, and * on an m bit value with an m*2 bit result. We
1557 // can't use 64-bit operands here because we don't have native results of
1558 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001559 // work on large-endian machines.
Dan Gohmancff69532009-04-01 18:45:54 +00001560 uint64_t mask = ~0ull >> (sizeof(unsigned)*CHAR_BIT);
Chris Lattner77527f52009-01-21 18:09:24 +00001561 unsigned n = rhsWords * 2;
1562 unsigned m = (lhsWords * 2) - n;
Reid Spencer522ca7c2007-02-25 01:56:07 +00001563
1564 // Allocate space for the temporary values we need either on the stack, if
1565 // it will fit, or on the heap if it won't.
Chris Lattner77527f52009-01-21 18:09:24 +00001566 unsigned SPACE[128];
Craig Topperc10719f2014-04-07 04:17:22 +00001567 unsigned *U = nullptr;
1568 unsigned *V = nullptr;
1569 unsigned *Q = nullptr;
1570 unsigned *R = nullptr;
Reid Spencer522ca7c2007-02-25 01:56:07 +00001571 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1572 U = &SPACE[0];
1573 V = &SPACE[m+n+1];
1574 Q = &SPACE[(m+n+1) + n];
1575 if (Remainder)
1576 R = &SPACE[(m+n+1) + n + (m+n)];
1577 } else {
Chris Lattner77527f52009-01-21 18:09:24 +00001578 U = new unsigned[m + n + 1];
1579 V = new unsigned[n];
1580 Q = new unsigned[m+n];
Reid Spencer522ca7c2007-02-25 01:56:07 +00001581 if (Remainder)
Chris Lattner77527f52009-01-21 18:09:24 +00001582 R = new unsigned[n];
Reid Spencer522ca7c2007-02-25 01:56:07 +00001583 }
1584
1585 // Initialize the dividend
Chris Lattner77527f52009-01-21 18:09:24 +00001586 memset(U, 0, (m+n+1)*sizeof(unsigned));
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001587 for (unsigned i = 0; i < lhsWords; ++i) {
Reid Spencer867b4062007-02-22 00:58:45 +00001588 uint64_t tmp = (LHS.getNumWords() == 1 ? LHS.VAL : LHS.pVal[i]);
Chris Lattner77527f52009-01-21 18:09:24 +00001589 U[i * 2] = (unsigned)(tmp & mask);
Dan Gohmancff69532009-04-01 18:45:54 +00001590 U[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001591 }
1592 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
1593
Reid Spencer522ca7c2007-02-25 01:56:07 +00001594 // Initialize the divisor
Chris Lattner77527f52009-01-21 18:09:24 +00001595 memset(V, 0, (n)*sizeof(unsigned));
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001596 for (unsigned i = 0; i < rhsWords; ++i) {
Reid Spencer867b4062007-02-22 00:58:45 +00001597 uint64_t tmp = (RHS.getNumWords() == 1 ? RHS.VAL : RHS.pVal[i]);
Chris Lattner77527f52009-01-21 18:09:24 +00001598 V[i * 2] = (unsigned)(tmp & mask);
Dan Gohmancff69532009-04-01 18:45:54 +00001599 V[i * 2 + 1] = (unsigned)(tmp >> (sizeof(unsigned)*CHAR_BIT));
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001600 }
1601
Reid Spencer522ca7c2007-02-25 01:56:07 +00001602 // initialize the quotient and remainder
Chris Lattner77527f52009-01-21 18:09:24 +00001603 memset(Q, 0, (m+n) * sizeof(unsigned));
Reid Spencer522ca7c2007-02-25 01:56:07 +00001604 if (Remainder)
Chris Lattner77527f52009-01-21 18:09:24 +00001605 memset(R, 0, n * sizeof(unsigned));
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001606
Eric Christopher820256b2009-08-21 04:06:45 +00001607 // Now, adjust m and n for the Knuth division. n is the number of words in
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001608 // the divisor. m is the number of words by which the dividend exceeds the
Eric Christopher820256b2009-08-21 04:06:45 +00001609 // divisor (i.e. m+n is the length of the dividend). These sizes must not
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001610 // contain any zero words or the Knuth algorithm fails.
1611 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
1612 n--;
1613 m++;
1614 }
1615 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
1616 m--;
1617
1618 // If we're left with only a single word for the divisor, Knuth doesn't work
1619 // so we implement the short division algorithm here. This is much simpler
1620 // and faster because we are certain that we can divide a 64-bit quantity
1621 // by a 32-bit quantity at hardware speed and short division is simply a
1622 // series of such operations. This is just like doing short division but we
1623 // are using base 2^32 instead of base 10.
1624 assert(n != 0 && "Divide by zero?");
1625 if (n == 1) {
Chris Lattner77527f52009-01-21 18:09:24 +00001626 unsigned divisor = V[0];
1627 unsigned remainder = 0;
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001628 for (int i = m+n-1; i >= 0; i--) {
1629 uint64_t partial_dividend = uint64_t(remainder) << 32 | U[i];
1630 if (partial_dividend == 0) {
1631 Q[i] = 0;
1632 remainder = 0;
1633 } else if (partial_dividend < divisor) {
1634 Q[i] = 0;
Chris Lattner77527f52009-01-21 18:09:24 +00001635 remainder = (unsigned)partial_dividend;
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001636 } else if (partial_dividend == divisor) {
1637 Q[i] = 1;
1638 remainder = 0;
1639 } else {
Chris Lattner77527f52009-01-21 18:09:24 +00001640 Q[i] = (unsigned)(partial_dividend / divisor);
1641 remainder = (unsigned)(partial_dividend - (Q[i] * divisor));
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001642 }
1643 }
1644 if (R)
1645 R[0] = remainder;
1646 } else {
1647 // Now we're ready to invoke the Knuth classical divide algorithm. In this
1648 // case n > 1.
1649 KnuthDiv(U, V, Q, R, m, n);
1650 }
1651
1652 // If the caller wants the quotient
1653 if (Quotient) {
1654 // Set up the Quotient value's memory.
1655 if (Quotient->BitWidth != LHS.BitWidth) {
1656 if (Quotient->isSingleWord())
1657 Quotient->VAL = 0;
1658 else
Reid Spencer7c16cd22007-02-26 23:38:21 +00001659 delete [] Quotient->pVal;
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001660 Quotient->BitWidth = LHS.BitWidth;
1661 if (!Quotient->isSingleWord())
Reid Spencer58a6a432007-02-21 08:21:52 +00001662 Quotient->pVal = getClearedMemory(Quotient->getNumWords());
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001663 } else
Jay Foad25a5e4c2010-12-01 08:53:58 +00001664 Quotient->clearAllBits();
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001665
Eric Christopher820256b2009-08-21 04:06:45 +00001666 // The quotient is in Q. Reconstitute the quotient into Quotient's low
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001667 // order words.
Yaron Keren39fc5a62015-03-26 19:45:19 +00001668 // This case is currently dead as all users of divide() handle trivial cases
1669 // earlier.
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001670 if (lhsWords == 1) {
Eric Christopher820256b2009-08-21 04:06:45 +00001671 uint64_t tmp =
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001672 uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2));
1673 if (Quotient->isSingleWord())
1674 Quotient->VAL = tmp;
1675 else
1676 Quotient->pVal[0] = tmp;
1677 } else {
1678 assert(!Quotient->isSingleWord() && "Quotient APInt not large enough");
1679 for (unsigned i = 0; i < lhsWords; ++i)
Eric Christopher820256b2009-08-21 04:06:45 +00001680 Quotient->pVal[i] =
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001681 uint64_t(Q[i*2]) | (uint64_t(Q[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1682 }
1683 }
1684
1685 // If the caller wants the remainder
1686 if (Remainder) {
1687 // Set up the Remainder value's memory.
1688 if (Remainder->BitWidth != RHS.BitWidth) {
1689 if (Remainder->isSingleWord())
1690 Remainder->VAL = 0;
1691 else
Reid Spencer7c16cd22007-02-26 23:38:21 +00001692 delete [] Remainder->pVal;
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001693 Remainder->BitWidth = RHS.BitWidth;
1694 if (!Remainder->isSingleWord())
Reid Spencer58a6a432007-02-21 08:21:52 +00001695 Remainder->pVal = getClearedMemory(Remainder->getNumWords());
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001696 } else
Jay Foad25a5e4c2010-12-01 08:53:58 +00001697 Remainder->clearAllBits();
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001698
1699 // The remainder is in R. Reconstitute the remainder into Remainder's low
1700 // order words.
1701 if (rhsWords == 1) {
Eric Christopher820256b2009-08-21 04:06:45 +00001702 uint64_t tmp =
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001703 uint64_t(R[0]) | (uint64_t(R[1]) << (APINT_BITS_PER_WORD / 2));
1704 if (Remainder->isSingleWord())
1705 Remainder->VAL = tmp;
1706 else
1707 Remainder->pVal[0] = tmp;
1708 } else {
1709 assert(!Remainder->isSingleWord() && "Remainder APInt not large enough");
1710 for (unsigned i = 0; i < rhsWords; ++i)
Eric Christopher820256b2009-08-21 04:06:45 +00001711 Remainder->pVal[i] =
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001712 uint64_t(R[i*2]) | (uint64_t(R[i*2+1]) << (APINT_BITS_PER_WORD / 2));
1713 }
1714 }
1715
1716 // Clean up the memory we allocated.
Reid Spencer522ca7c2007-02-25 01:56:07 +00001717 if (U != &SPACE[0]) {
1718 delete [] U;
1719 delete [] V;
1720 delete [] Q;
1721 delete [] R;
1722 }
Reid Spencer100502d2007-02-17 03:16:00 +00001723}
1724
Reid Spencer1d072122007-02-16 22:36:51 +00001725APInt APInt::udiv(const APInt& RHS) const {
Reid Spencera32372d12007-02-17 00:18:01 +00001726 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
Reid Spencer39867762007-02-17 02:07:07 +00001727
1728 // First, deal with the easy case
1729 if (isSingleWord()) {
1730 assert(RHS.VAL != 0 && "Divide by zero?");
1731 return APInt(BitWidth, VAL / RHS.VAL);
Zhou Shengfbf61ea2007-02-08 14:35:19 +00001732 }
Reid Spencer39867762007-02-17 02:07:07 +00001733
Reid Spencer39867762007-02-17 02:07:07 +00001734 // Get some facts about the LHS and RHS number of bits and words
Chris Lattner77527f52009-01-21 18:09:24 +00001735 unsigned rhsBits = RHS.getActiveBits();
1736 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
Reid Spencer39867762007-02-17 02:07:07 +00001737 assert(rhsWords && "Divided by zero???");
Chris Lattner77527f52009-01-21 18:09:24 +00001738 unsigned lhsBits = this->getActiveBits();
1739 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
Reid Spencer39867762007-02-17 02:07:07 +00001740
1741 // Deal with some degenerate cases
Eric Christopher820256b2009-08-21 04:06:45 +00001742 if (!lhsWords)
Reid Spencer58a6a432007-02-21 08:21:52 +00001743 // 0 / X ===> 0
Eric Christopher820256b2009-08-21 04:06:45 +00001744 return APInt(BitWidth, 0);
Reid Spencer58a6a432007-02-21 08:21:52 +00001745 else if (lhsWords < rhsWords || this->ult(RHS)) {
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001746 // X / Y ===> 0, iff X < Y
Reid Spencer58a6a432007-02-21 08:21:52 +00001747 return APInt(BitWidth, 0);
1748 } else if (*this == RHS) {
1749 // X / X ===> 1
1750 return APInt(BitWidth, 1);
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001751 } else if (lhsWords == 1 && rhsWords == 1) {
Reid Spencer39867762007-02-17 02:07:07 +00001752 // All high words are zero, just use native divide
Reid Spencer58a6a432007-02-21 08:21:52 +00001753 return APInt(BitWidth, this->pVal[0] / RHS.pVal[0]);
Reid Spencer39867762007-02-17 02:07:07 +00001754 }
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001755
1756 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
1757 APInt Quotient(1,0); // to hold result.
Craig Topperc10719f2014-04-07 04:17:22 +00001758 divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr);
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001759 return Quotient;
Zhou Shengfbf61ea2007-02-08 14:35:19 +00001760}
1761
Jakub Staszak6605c602013-02-20 00:17:42 +00001762APInt APInt::sdiv(const APInt &RHS) const {
1763 if (isNegative()) {
1764 if (RHS.isNegative())
1765 return (-(*this)).udiv(-RHS);
1766 return -((-(*this)).udiv(RHS));
1767 }
1768 if (RHS.isNegative())
1769 return -(this->udiv(-RHS));
1770 return this->udiv(RHS);
1771}
1772
Reid Spencer1d072122007-02-16 22:36:51 +00001773APInt APInt::urem(const APInt& RHS) const {
Reid Spencera32372d12007-02-17 00:18:01 +00001774 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
Reid Spencer39867762007-02-17 02:07:07 +00001775 if (isSingleWord()) {
1776 assert(RHS.VAL != 0 && "Remainder by zero?");
1777 return APInt(BitWidth, VAL % RHS.VAL);
Zhou Shengfbf61ea2007-02-08 14:35:19 +00001778 }
Reid Spencer39867762007-02-17 02:07:07 +00001779
Reid Spencer58a6a432007-02-21 08:21:52 +00001780 // Get some facts about the LHS
Chris Lattner77527f52009-01-21 18:09:24 +00001781 unsigned lhsBits = getActiveBits();
1782 unsigned lhsWords = !lhsBits ? 0 : (whichWord(lhsBits - 1) + 1);
Reid Spencer39867762007-02-17 02:07:07 +00001783
1784 // Get some facts about the RHS
Chris Lattner77527f52009-01-21 18:09:24 +00001785 unsigned rhsBits = RHS.getActiveBits();
1786 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
Reid Spencer39867762007-02-17 02:07:07 +00001787 assert(rhsWords && "Performing remainder operation by zero ???");
1788
Reid Spencer39867762007-02-17 02:07:07 +00001789 // Check the degenerate cases
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001790 if (lhsWords == 0) {
Reid Spencer58a6a432007-02-21 08:21:52 +00001791 // 0 % Y ===> 0
1792 return APInt(BitWidth, 0);
1793 } else if (lhsWords < rhsWords || this->ult(RHS)) {
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001794 // X % Y ===> X, iff X < Y
Reid Spencer58a6a432007-02-21 08:21:52 +00001795 return *this;
1796 } else if (*this == RHS) {
Reid Spencer39867762007-02-17 02:07:07 +00001797 // X % X == 0;
Reid Spencer58a6a432007-02-21 08:21:52 +00001798 return APInt(BitWidth, 0);
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001799 } else if (lhsWords == 1) {
Reid Spencer39867762007-02-17 02:07:07 +00001800 // All high words are zero, just use native remainder
Reid Spencer58a6a432007-02-21 08:21:52 +00001801 return APInt(BitWidth, pVal[0] % RHS.pVal[0]);
Reid Spencer39867762007-02-17 02:07:07 +00001802 }
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001803
Reid Spencer4c50b522007-05-13 23:44:59 +00001804 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001805 APInt Remainder(1,0);
Craig Topperc10719f2014-04-07 04:17:22 +00001806 divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder);
Reid Spencerfb77b2b2007-02-20 08:51:03 +00001807 return Remainder;
Zhou Shengfbf61ea2007-02-08 14:35:19 +00001808}
Reid Spencer100502d2007-02-17 03:16:00 +00001809
Jakub Staszak6605c602013-02-20 00:17:42 +00001810APInt APInt::srem(const APInt &RHS) const {
1811 if (isNegative()) {
1812 if (RHS.isNegative())
1813 return -((-(*this)).urem(-RHS));
1814 return -((-(*this)).urem(RHS));
1815 }
1816 if (RHS.isNegative())
1817 return this->urem(-RHS);
1818 return this->urem(RHS);
1819}
1820
Eric Christopher820256b2009-08-21 04:06:45 +00001821void APInt::udivrem(const APInt &LHS, const APInt &RHS,
Reid Spencer4c50b522007-05-13 23:44:59 +00001822 APInt &Quotient, APInt &Remainder) {
David Majnemer7f039202014-12-14 09:41:56 +00001823 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
1824
1825 // First, deal with the easy case
1826 if (LHS.isSingleWord()) {
1827 assert(RHS.VAL != 0 && "Divide by zero?");
1828 uint64_t QuotVal = LHS.VAL / RHS.VAL;
1829 uint64_t RemVal = LHS.VAL % RHS.VAL;
1830 Quotient = APInt(LHS.BitWidth, QuotVal);
1831 Remainder = APInt(LHS.BitWidth, RemVal);
1832 return;
1833 }
1834
Reid Spencer4c50b522007-05-13 23:44:59 +00001835 // Get some size facts about the dividend and divisor
Chris Lattner77527f52009-01-21 18:09:24 +00001836 unsigned lhsBits = LHS.getActiveBits();
1837 unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1);
1838 unsigned rhsBits = RHS.getActiveBits();
1839 unsigned rhsWords = !rhsBits ? 0 : (APInt::whichWord(rhsBits - 1) + 1);
Reid Spencer4c50b522007-05-13 23:44:59 +00001840
1841 // Check the degenerate cases
Eric Christopher820256b2009-08-21 04:06:45 +00001842 if (lhsWords == 0) {
Reid Spencer4c50b522007-05-13 23:44:59 +00001843 Quotient = 0; // 0 / Y ===> 0
1844 Remainder = 0; // 0 % Y ===> 0
1845 return;
Eric Christopher820256b2009-08-21 04:06:45 +00001846 }
1847
1848 if (lhsWords < rhsWords || LHS.ult(RHS)) {
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001849 Remainder = LHS; // X % Y ===> X, iff X < Y
1850 Quotient = 0; // X / Y ===> 0, iff X < Y
Reid Spencer4c50b522007-05-13 23:44:59 +00001851 return;
Eric Christopher820256b2009-08-21 04:06:45 +00001852 }
1853
Reid Spencer4c50b522007-05-13 23:44:59 +00001854 if (LHS == RHS) {
1855 Quotient = 1; // X / X ===> 1
1856 Remainder = 0; // X % X ===> 0;
1857 return;
Eric Christopher820256b2009-08-21 04:06:45 +00001858 }
1859
Reid Spencer4c50b522007-05-13 23:44:59 +00001860 if (lhsWords == 1 && rhsWords == 1) {
1861 // There is only one word to consider so use the native versions.
Wojciech Matyjewicz41b744d2008-06-23 19:39:50 +00001862 uint64_t lhsValue = LHS.isSingleWord() ? LHS.VAL : LHS.pVal[0];
1863 uint64_t rhsValue = RHS.isSingleWord() ? RHS.VAL : RHS.pVal[0];
1864 Quotient = APInt(LHS.getBitWidth(), lhsValue / rhsValue);
1865 Remainder = APInt(LHS.getBitWidth(), lhsValue % rhsValue);
Reid Spencer4c50b522007-05-13 23:44:59 +00001866 return;
1867 }
1868
1869 // Okay, lets do it the long way
1870 divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder);
1871}
1872
Jakub Staszak6605c602013-02-20 00:17:42 +00001873void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
1874 APInt &Quotient, APInt &Remainder) {
1875 if (LHS.isNegative()) {
1876 if (RHS.isNegative())
1877 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
1878 else {
1879 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
1880 Quotient = -Quotient;
1881 }
1882 Remainder = -Remainder;
1883 } else if (RHS.isNegative()) {
1884 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
1885 Quotient = -Quotient;
1886 } else {
1887 APInt::udivrem(LHS, RHS, Quotient, Remainder);
1888 }
1889}
1890
Chris Lattner2c819b02010-10-13 23:54:10 +00001891APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
Chris Lattner79bdd882010-10-13 23:46:33 +00001892 APInt Res = *this+RHS;
1893 Overflow = isNonNegative() == RHS.isNonNegative() &&
1894 Res.isNonNegative() != isNonNegative();
1895 return Res;
1896}
1897
Chris Lattner698661c2010-10-14 00:05:07 +00001898APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
1899 APInt Res = *this+RHS;
1900 Overflow = Res.ult(RHS);
1901 return Res;
1902}
1903
Chris Lattner2c819b02010-10-13 23:54:10 +00001904APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
Chris Lattner79bdd882010-10-13 23:46:33 +00001905 APInt Res = *this - RHS;
1906 Overflow = isNonNegative() != RHS.isNonNegative() &&
1907 Res.isNonNegative() != isNonNegative();
1908 return Res;
1909}
1910
Chris Lattner698661c2010-10-14 00:05:07 +00001911APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
Chris Lattnerb9681ad2010-10-14 00:30:00 +00001912 APInt Res = *this-RHS;
1913 Overflow = Res.ugt(*this);
Chris Lattner698661c2010-10-14 00:05:07 +00001914 return Res;
1915}
1916
Chris Lattner2c819b02010-10-13 23:54:10 +00001917APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
Chris Lattner79bdd882010-10-13 23:46:33 +00001918 // MININT/-1 --> overflow.
1919 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
1920 return sdiv(RHS);
1921}
1922
Chris Lattner2c819b02010-10-13 23:54:10 +00001923APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
Chris Lattner79bdd882010-10-13 23:46:33 +00001924 APInt Res = *this * RHS;
Simon Pilgrim4c0ea9d2017-02-23 16:07:04 +00001925
Chris Lattner79bdd882010-10-13 23:46:33 +00001926 if (*this != 0 && RHS != 0)
1927 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
1928 else
1929 Overflow = false;
1930 return Res;
1931}
1932
Frits van Bommel0bb2ad22011-03-27 14:26:13 +00001933APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
1934 APInt Res = *this * RHS;
1935
1936 if (*this != 0 && RHS != 0)
1937 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
1938 else
1939 Overflow = false;
1940 return Res;
1941}
1942
David Majnemera2521382014-10-13 21:48:30 +00001943APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
1944 Overflow = ShAmt.uge(getBitWidth());
Chris Lattner79bdd882010-10-13 23:46:33 +00001945 if (Overflow)
David Majnemera2521382014-10-13 21:48:30 +00001946 return APInt(BitWidth, 0);
Chris Lattner79bdd882010-10-13 23:46:33 +00001947
1948 if (isNonNegative()) // Don't allow sign change.
David Majnemera2521382014-10-13 21:48:30 +00001949 Overflow = ShAmt.uge(countLeadingZeros());
Chris Lattner79bdd882010-10-13 23:46:33 +00001950 else
David Majnemera2521382014-10-13 21:48:30 +00001951 Overflow = ShAmt.uge(countLeadingOnes());
Simon Pilgrim4c0ea9d2017-02-23 16:07:04 +00001952
Chris Lattner79bdd882010-10-13 23:46:33 +00001953 return *this << ShAmt;
1954}
1955
David Majnemera2521382014-10-13 21:48:30 +00001956APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
1957 Overflow = ShAmt.uge(getBitWidth());
1958 if (Overflow)
1959 return APInt(BitWidth, 0);
1960
1961 Overflow = ShAmt.ugt(countLeadingZeros());
1962
1963 return *this << ShAmt;
1964}
1965
Chris Lattner79bdd882010-10-13 23:46:33 +00001966
1967
1968
Benjamin Kramer92d89982010-07-14 22:38:02 +00001969void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
Reid Spencer1ba83352007-02-21 03:55:44 +00001970 // Check our assumptions here
Erick Tryzelaar1264bcb2009-08-21 03:15:14 +00001971 assert(!str.empty() && "Invalid string length");
Simon Pilgrim4c0ea9d2017-02-23 16:07:04 +00001972 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
Douglas Gregor663c0682011-09-14 15:54:46 +00001973 radix == 36) &&
1974 "Radix should be 2, 8, 10, 16, or 36!");
Erick Tryzelaar1264bcb2009-08-21 03:15:14 +00001975
Daniel Dunbar3a1efd112009-08-13 02:33:34 +00001976 StringRef::iterator p = str.begin();
1977 size_t slen = str.size();
1978 bool isNeg = *p == '-';
Erick Tryzelaar1264bcb2009-08-21 03:15:14 +00001979 if (*p == '-' || *p == '+') {
Daniel Dunbar3a1efd112009-08-13 02:33:34 +00001980 p++;
1981 slen--;
Eric Christopher43a1dec2009-08-21 04:10:31 +00001982 assert(slen && "String is only a sign, needs a value.");
Daniel Dunbar3a1efd112009-08-13 02:33:34 +00001983 }
Chris Lattnerdad2d092007-05-03 18:15:36 +00001984 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
Chris Lattnerb869a0a2009-04-25 18:34:04 +00001985 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
1986 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
Dan Gohmanb452d4e2010-03-24 19:38:02 +00001987 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
1988 "Insufficient bit width");
Reid Spencer1ba83352007-02-21 03:55:44 +00001989
1990 // Allocate memory
1991 if (!isSingleWord())
1992 pVal = getClearedMemory(getNumWords());
1993
1994 // Figure out if we can shift instead of multiply
Chris Lattner77527f52009-01-21 18:09:24 +00001995 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
Reid Spencer1ba83352007-02-21 03:55:44 +00001996
Craig Topperb7d8faa2017-04-02 06:59:38 +00001997 // Set up an APInt for the radix multiplier outside the loop so we don't
Reid Spencer1ba83352007-02-21 03:55:44 +00001998 // constantly construct/destruct it.
Reid Spencer1ba83352007-02-21 03:55:44 +00001999 APInt apradix(getBitWidth(), radix);
2000
2001 // Enter digit traversal loop
Daniel Dunbar3a1efd112009-08-13 02:33:34 +00002002 for (StringRef::iterator e = str.end(); p != e; ++p) {
Erick Tryzelaardadb15712009-08-21 03:15:28 +00002003 unsigned digit = getDigit(*p, radix);
Erick Tryzelaar60964092009-08-21 06:48:37 +00002004 assert(digit < radix && "Invalid character in digit string");
Reid Spencer1ba83352007-02-21 03:55:44 +00002005
Reid Spencera93c9812007-05-16 19:18:22 +00002006 // Shift or multiply the value by the radix
Chris Lattnerb869a0a2009-04-25 18:34:04 +00002007 if (slen > 1) {
2008 if (shift)
2009 *this <<= shift;
2010 else
2011 *this *= apradix;
2012 }
Reid Spencer1ba83352007-02-21 03:55:44 +00002013
2014 // Add in the digit we just interpreted
Craig Topperb7d8faa2017-04-02 06:59:38 +00002015 *this += digit;
Reid Spencer100502d2007-02-17 03:16:00 +00002016 }
Reid Spencerb6b5cc32007-02-25 23:44:53 +00002017 // If its negative, put it in two's complement form
Reid Spenceraa8dcfe2007-02-26 07:44:38 +00002018 if (isNeg) {
Jakub Staszak773be0c2013-03-20 23:56:19 +00002019 --(*this);
Jay Foad25a5e4c2010-12-01 08:53:58 +00002020 this->flipAllBits();
Reid Spencerb6b5cc32007-02-25 23:44:53 +00002021 }
Reid Spencer100502d2007-02-17 03:16:00 +00002022}
Reid Spencerfb77b2b2007-02-20 08:51:03 +00002023
Chris Lattner17f71652008-08-17 07:19:36 +00002024void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
Ted Kremenekb05f02e2011-06-15 00:51:55 +00002025 bool Signed, bool formatAsCLiteral) const {
Simon Pilgrim4c0ea9d2017-02-23 16:07:04 +00002026 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
Douglas Gregor663c0682011-09-14 15:54:46 +00002027 Radix == 36) &&
Dylan Noblesmith1c419ff2011-12-16 20:36:31 +00002028 "Radix should be 2, 8, 10, 16, or 36!");
Eric Christopher820256b2009-08-21 04:06:45 +00002029
Ted Kremenekb05f02e2011-06-15 00:51:55 +00002030 const char *Prefix = "";
2031 if (formatAsCLiteral) {
2032 switch (Radix) {
2033 case 2:
2034 // Binary literals are a non-standard extension added in gcc 4.3:
2035 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
2036 Prefix = "0b";
2037 break;
2038 case 8:
2039 Prefix = "0";
2040 break;
Dylan Noblesmith1c419ff2011-12-16 20:36:31 +00002041 case 10:
2042 break; // No prefix
Ted Kremenekb05f02e2011-06-15 00:51:55 +00002043 case 16:
2044 Prefix = "0x";
2045 break;
Dylan Noblesmith1c419ff2011-12-16 20:36:31 +00002046 default:
2047 llvm_unreachable("Invalid radix!");
Ted Kremenekb05f02e2011-06-15 00:51:55 +00002048 }
2049 }
2050
Chris Lattner17f71652008-08-17 07:19:36 +00002051 // First, check for a zero value and just short circuit the logic below.
2052 if (*this == 0) {
Ted Kremenekb05f02e2011-06-15 00:51:55 +00002053 while (*Prefix) {
2054 Str.push_back(*Prefix);
2055 ++Prefix;
2056 };
Chris Lattner17f71652008-08-17 07:19:36 +00002057 Str.push_back('0');
2058 return;
2059 }
Eric Christopher820256b2009-08-21 04:06:45 +00002060
Douglas Gregor663c0682011-09-14 15:54:46 +00002061 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
Eric Christopher820256b2009-08-21 04:06:45 +00002062
Reid Spencerfb77b2b2007-02-20 08:51:03 +00002063 if (isSingleWord()) {
Chris Lattner17f71652008-08-17 07:19:36 +00002064 char Buffer[65];
2065 char *BufPtr = Buffer+65;
Eric Christopher820256b2009-08-21 04:06:45 +00002066
Chris Lattner17f71652008-08-17 07:19:36 +00002067 uint64_t N;
Chris Lattnerb91c9032010-08-18 00:33:47 +00002068 if (!Signed) {
Chris Lattner17f71652008-08-17 07:19:36 +00002069 N = getZExtValue();
Chris Lattnerb91c9032010-08-18 00:33:47 +00002070 } else {
2071 int64_t I = getSExtValue();
2072 if (I >= 0) {
2073 N = I;
2074 } else {
2075 Str.push_back('-');
2076 N = -(uint64_t)I;
2077 }
Reid Spencerfb77b2b2007-02-20 08:51:03 +00002078 }
Eric Christopher820256b2009-08-21 04:06:45 +00002079
Ted Kremenekb05f02e2011-06-15 00:51:55 +00002080 while (*Prefix) {
2081 Str.push_back(*Prefix);
2082 ++Prefix;
2083 };
2084
Chris Lattner17f71652008-08-17 07:19:36 +00002085 while (N) {
2086 *--BufPtr = Digits[N % Radix];
2087 N /= Radix;
2088 }
2089 Str.append(BufPtr, Buffer+65);
2090 return;
Reid Spencerfb77b2b2007-02-20 08:51:03 +00002091 }
2092
Chris Lattner17f71652008-08-17 07:19:36 +00002093 APInt Tmp(*this);
Eric Christopher820256b2009-08-21 04:06:45 +00002094
Chris Lattner17f71652008-08-17 07:19:36 +00002095 if (Signed && isNegative()) {
Reid Spencerfb77b2b2007-02-20 08:51:03 +00002096 // They want to print the signed version and it is a negative value
2097 // Flip the bits and add one to turn it into the equivalent positive
2098 // value and put a '-' in the result.
Jay Foad25a5e4c2010-12-01 08:53:58 +00002099 Tmp.flipAllBits();
Jakub Staszak773be0c2013-03-20 23:56:19 +00002100 ++Tmp;
Chris Lattner17f71652008-08-17 07:19:36 +00002101 Str.push_back('-');
Reid Spencerfb77b2b2007-02-20 08:51:03 +00002102 }
Eric Christopher820256b2009-08-21 04:06:45 +00002103
Ted Kremenekb05f02e2011-06-15 00:51:55 +00002104 while (*Prefix) {
2105 Str.push_back(*Prefix);
2106 ++Prefix;
2107 };
2108
Chris Lattner17f71652008-08-17 07:19:36 +00002109 // We insert the digits backward, then reverse them to get the right order.
2110 unsigned StartDig = Str.size();
Eric Christopher820256b2009-08-21 04:06:45 +00002111
2112 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
2113 // because the number of bits per digit (1, 3 and 4 respectively) divides
Craig Topperd7ed50d2017-04-02 06:59:36 +00002114 // equally. We just shift until the value is zero.
Douglas Gregor663c0682011-09-14 15:54:46 +00002115 if (Radix == 2 || Radix == 8 || Radix == 16) {
Chris Lattner17f71652008-08-17 07:19:36 +00002116 // Just shift tmp right for each digit width until it becomes zero
2117 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2118 unsigned MaskAmt = Radix - 1;
Eric Christopher820256b2009-08-21 04:06:45 +00002119
Chris Lattner17f71652008-08-17 07:19:36 +00002120 while (Tmp != 0) {
2121 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
2122 Str.push_back(Digits[Digit]);
Craig Topperfc947bc2017-04-18 17:14:21 +00002123 Tmp.lshrInPlace(ShiftAmt);
Chris Lattner17f71652008-08-17 07:19:36 +00002124 }
2125 } else {
Douglas Gregor663c0682011-09-14 15:54:46 +00002126 APInt divisor(Radix == 10? 4 : 8, Radix);
Chris Lattner17f71652008-08-17 07:19:36 +00002127 while (Tmp != 0) {
2128 APInt APdigit(1, 0);
2129 APInt tmp2(Tmp.getBitWidth(), 0);
Eric Christopher820256b2009-08-21 04:06:45 +00002130 divide(Tmp, Tmp.getNumWords(), divisor, divisor.getNumWords(), &tmp2,
Chris Lattner17f71652008-08-17 07:19:36 +00002131 &APdigit);
Chris Lattner77527f52009-01-21 18:09:24 +00002132 unsigned Digit = (unsigned)APdigit.getZExtValue();
Chris Lattner17f71652008-08-17 07:19:36 +00002133 assert(Digit < Radix && "divide failed");
2134 Str.push_back(Digits[Digit]);
2135 Tmp = tmp2;
2136 }
Reid Spencerfb77b2b2007-02-20 08:51:03 +00002137 }
Eric Christopher820256b2009-08-21 04:06:45 +00002138
Chris Lattner17f71652008-08-17 07:19:36 +00002139 // Reverse the digits before returning.
2140 std::reverse(Str.begin()+StartDig, Str.end());
Reid Spencerfb77b2b2007-02-20 08:51:03 +00002141}
2142
Pawel Bylica6eeeac72015-04-06 13:31:39 +00002143/// Returns the APInt as a std::string. Note that this is an inefficient method.
2144/// It is better to pass in a SmallVector/SmallString to the methods above.
Chris Lattner17f71652008-08-17 07:19:36 +00002145std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
2146 SmallString<40> S;
Ted Kremenekb05f02e2011-06-15 00:51:55 +00002147 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
Daniel Dunbar8b0b1152009-08-19 20:07:03 +00002148 return S.str();
Reid Spencer1ba83352007-02-21 03:55:44 +00002149}
Chris Lattner6b695682007-08-16 15:56:55 +00002150
Matthias Braun8c209aa2017-01-28 02:02:38 +00002151#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Yaron Kereneb2a2542016-01-29 20:50:44 +00002152LLVM_DUMP_METHOD void APInt::dump() const {
Chris Lattner17f71652008-08-17 07:19:36 +00002153 SmallString<40> S, U;
2154 this->toStringUnsigned(U);
2155 this->toStringSigned(S);
David Greenef32fcb42010-01-05 01:28:52 +00002156 dbgs() << "APInt(" << BitWidth << "b, "
Davide Italiano5a473d22017-01-31 21:26:18 +00002157 << U << "u " << S << "s)\n";
Chris Lattner17f71652008-08-17 07:19:36 +00002158}
Matthias Braun8c209aa2017-01-28 02:02:38 +00002159#endif
Chris Lattner17f71652008-08-17 07:19:36 +00002160
Chris Lattner0c19df42008-08-23 22:23:09 +00002161void APInt::print(raw_ostream &OS, bool isSigned) const {
Chris Lattner17f71652008-08-17 07:19:36 +00002162 SmallString<40> S;
Ted Kremenekb05f02e2011-06-15 00:51:55 +00002163 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
Yaron Keren92e1b622015-03-18 10:17:07 +00002164 OS << S;
Chris Lattner17f71652008-08-17 07:19:36 +00002165}
2166
Chris Lattner6b695682007-08-16 15:56:55 +00002167// This implements a variety of operations on a representation of
2168// arbitrary precision, two's-complement, bignum integer values.
2169
Chris Lattner96cffa62009-08-23 23:11:28 +00002170// Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
2171// and unrestricting assumption.
Craig Topper55229b72017-04-02 19:17:22 +00002172static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,
2173 "Part width must be divisible by 2!");
Chris Lattner6b695682007-08-16 15:56:55 +00002174
2175/* Some handy functions local to this file. */
Chris Lattner6b695682007-08-16 15:56:55 +00002176
Craig Topper76f42462017-03-28 05:32:53 +00002177/* Returns the integer part with the least significant BITS set.
2178 BITS cannot be zero. */
Craig Topper55229b72017-04-02 19:17:22 +00002179static inline APInt::WordType lowBitMask(unsigned bits) {
2180 assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD);
Chris Lattnerfe02c1f2007-08-20 22:49:32 +00002181
Craig Topper55229b72017-04-02 19:17:22 +00002182 return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
Craig Topper76f42462017-03-28 05:32:53 +00002183}
Chris Lattnerfe02c1f2007-08-20 22:49:32 +00002184
Craig Topper76f42462017-03-28 05:32:53 +00002185/* Returns the value of the lower half of PART. */
Craig Topper55229b72017-04-02 19:17:22 +00002186static inline APInt::WordType lowHalf(APInt::WordType part) {
2187 return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
Craig Topper76f42462017-03-28 05:32:53 +00002188}
Chris Lattnerfe02c1f2007-08-20 22:49:32 +00002189
Craig Topper76f42462017-03-28 05:32:53 +00002190/* Returns the value of the upper half of PART. */
Craig Topper55229b72017-04-02 19:17:22 +00002191static inline APInt::WordType highHalf(APInt::WordType part) {
2192 return part >> (APInt::APINT_BITS_PER_WORD / 2);
Craig Topper76f42462017-03-28 05:32:53 +00002193}
Chris Lattnerfe02c1f2007-08-20 22:49:32 +00002194
Craig Topper76f42462017-03-28 05:32:53 +00002195/* Returns the bit number of the most significant set bit of a part.
2196 If the input number has no bits set -1U is returned. */
Craig Topper55229b72017-04-02 19:17:22 +00002197static unsigned partMSB(APInt::WordType value) {
Craig Topper76f42462017-03-28 05:32:53 +00002198 return findLastSet(value, ZB_Max);
2199}
Chris Lattner6b695682007-08-16 15:56:55 +00002200
Craig Topper76f42462017-03-28 05:32:53 +00002201/* Returns the bit number of the least significant set bit of a
2202 part. If the input number has no bits set -1U is returned. */
Craig Topper55229b72017-04-02 19:17:22 +00002203static unsigned partLSB(APInt::WordType value) {
Craig Topper76f42462017-03-28 05:32:53 +00002204 return findFirstSet(value, ZB_Max);
Alexander Kornienkof00654e2015-06-23 09:49:53 +00002205}
Chris Lattner6b695682007-08-16 15:56:55 +00002206
2207/* Sets the least significant part of a bignum to the input value, and
2208 zeroes out higher parts. */
Craig Topper55229b72017-04-02 19:17:22 +00002209void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
Dan Gohmanb452d4e2010-03-24 19:38:02 +00002210 assert(parts > 0);
Neil Boothb6182162007-10-08 13:47:12 +00002211
Chris Lattner6b695682007-08-16 15:56:55 +00002212 dst[0] = part;
Craig Topperb0038162017-03-28 05:32:52 +00002213 for (unsigned i = 1; i < parts; i++)
Chris Lattner6b695682007-08-16 15:56:55 +00002214 dst[i] = 0;
2215}
2216
2217/* Assign one bignum to another. */
Craig Topper55229b72017-04-02 19:17:22 +00002218void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
Craig Topperb0038162017-03-28 05:32:52 +00002219 for (unsigned i = 0; i < parts; i++)
Chris Lattner6b695682007-08-16 15:56:55 +00002220 dst[i] = src[i];
2221}
2222
2223/* Returns true if a bignum is zero, false otherwise. */
Craig Topper55229b72017-04-02 19:17:22 +00002224bool APInt::tcIsZero(const WordType *src, unsigned parts) {
Craig Topperb0038162017-03-28 05:32:52 +00002225 for (unsigned i = 0; i < parts; i++)
Chris Lattner6b695682007-08-16 15:56:55 +00002226 if (src[i])
2227 return false;
2228
2229 return true;
2230}
2231
2232/* Extract the given bit of a bignum; returns 0 or 1. */
Craig Topper55229b72017-04-02 19:17:22 +00002233int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
Craig Topper00b47ee2017-04-02 19:35:18 +00002234 return (parts[whichWord(bit)] & maskBit(bit)) != 0;
Chris Lattner6b695682007-08-16 15:56:55 +00002235}
2236
John McCalldcb9a7a2010-02-28 02:51:25 +00002237/* Set the given bit of a bignum. */
Craig Topper55229b72017-04-02 19:17:22 +00002238void APInt::tcSetBit(WordType *parts, unsigned bit) {
Craig Topper00b47ee2017-04-02 19:35:18 +00002239 parts[whichWord(bit)] |= maskBit(bit);
Chris Lattner6b695682007-08-16 15:56:55 +00002240}
2241
John McCalldcb9a7a2010-02-28 02:51:25 +00002242/* Clears the given bit of a bignum. */
Craig Topper55229b72017-04-02 19:17:22 +00002243void APInt::tcClearBit(WordType *parts, unsigned bit) {
Craig Topper00b47ee2017-04-02 19:35:18 +00002244 parts[whichWord(bit)] &= ~maskBit(bit);
John McCalldcb9a7a2010-02-28 02:51:25 +00002245}
2246
Neil Boothc8b650a2007-10-06 00:43:45 +00002247/* Returns the bit number of the least significant set bit of a
2248 number. If the input number has no bits set -1U is returned. */
Craig Topper55229b72017-04-02 19:17:22 +00002249unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
Craig Topperb0038162017-03-28 05:32:52 +00002250 for (unsigned i = 0; i < n; i++) {
2251 if (parts[i] != 0) {
2252 unsigned lsb = partLSB(parts[i]);
Chris Lattner6b695682007-08-16 15:56:55 +00002253
Craig Topper55229b72017-04-02 19:17:22 +00002254 return lsb + i * APINT_BITS_PER_WORD;
Craig Topperb0038162017-03-28 05:32:52 +00002255 }
Chris Lattner6b695682007-08-16 15:56:55 +00002256 }
2257
2258 return -1U;
2259}
2260
Neil Boothc8b650a2007-10-06 00:43:45 +00002261/* Returns the bit number of the most significant set bit of a number.
2262 If the input number has no bits set -1U is returned. */
Craig Topper55229b72017-04-02 19:17:22 +00002263unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
Chris Lattner6b695682007-08-16 15:56:55 +00002264 do {
Dan Gohmanb452d4e2010-03-24 19:38:02 +00002265 --n;
Chris Lattner6b695682007-08-16 15:56:55 +00002266
Dan Gohmanb452d4e2010-03-24 19:38:02 +00002267 if (parts[n] != 0) {
Craig Topperb0038162017-03-28 05:32:52 +00002268 unsigned msb = partMSB(parts[n]);
Chris Lattner6b695682007-08-16 15:56:55 +00002269
Craig Topper55229b72017-04-02 19:17:22 +00002270 return msb + n * APINT_BITS_PER_WORD;
Dan Gohmanb452d4e2010-03-24 19:38:02 +00002271 }
Chris Lattner6b695682007-08-16 15:56:55 +00002272 } while (n);
2273
2274 return -1U;
2275}
2276
Neil Boothb6182162007-10-08 13:47:12 +00002277/* Copy the bit vector of width srcBITS from SRC, starting at bit
2278 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
2279 the least significant bit of DST. All high bits above srcBITS in
2280 DST are zero-filled. */
2281void
Craig Topper55229b72017-04-02 19:17:22 +00002282APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
Craig Topper6a8518082017-03-28 05:32:55 +00002283 unsigned srcBits, unsigned srcLSB) {
Craig Topper55229b72017-04-02 19:17:22 +00002284 unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
Dan Gohmanb452d4e2010-03-24 19:38:02 +00002285 assert(dstParts <= dstCount);
Neil Boothb6182162007-10-08 13:47:12 +00002286
Craig Topper55229b72017-04-02 19:17:22 +00002287 unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
Neil Boothb6182162007-10-08 13:47:12 +00002288 tcAssign (dst, src + firstSrcPart, dstParts);
2289
Craig Topper55229b72017-04-02 19:17:22 +00002290 unsigned shift = srcLSB % APINT_BITS_PER_WORD;
Neil Boothb6182162007-10-08 13:47:12 +00002291 tcShiftRight (dst, dstParts, shift);
2292
Craig Topper55229b72017-04-02 19:17:22 +00002293 /* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
Neil Boothb6182162007-10-08 13:47:12 +00002294 in DST. If this is less that srcBits, append the rest, else
2295 clear the high bits. */
Craig Topper55229b72017-04-02 19:17:22 +00002296 unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
Neil Boothb6182162007-10-08 13:47:12 +00002297 if (n < srcBits) {
Craig Topper55229b72017-04-02 19:17:22 +00002298 WordType mask = lowBitMask (srcBits - n);
Neil Boothb6182162007-10-08 13:47:12 +00002299 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
Craig Topper55229b72017-04-02 19:17:22 +00002300 << n % APINT_BITS_PER_WORD);
Neil Boothb6182162007-10-08 13:47:12 +00002301 } else if (n > srcBits) {
Craig Topper55229b72017-04-02 19:17:22 +00002302 if (srcBits % APINT_BITS_PER_WORD)
2303 dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
Neil Boothb6182162007-10-08 13:47:12 +00002304 }
2305
2306 /* Clear high parts. */
2307 while (dstParts < dstCount)
2308 dst[dstParts++] = 0;
2309}
2310
Chris Lattner6b695682007-08-16 15:56:55 +00002311/* DST += RHS + C where C is zero or one. Returns the carry flag. */
Craig Topper55229b72017-04-02 19:17:22 +00002312APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
2313 WordType c, unsigned parts) {
Chris Lattner6b695682007-08-16 15:56:55 +00002314 assert(c <= 1);
2315
Craig Topperb0038162017-03-28 05:32:52 +00002316 for (unsigned i = 0; i < parts; i++) {
Craig Topper55229b72017-04-02 19:17:22 +00002317 WordType l = dst[i];
Chris Lattner6b695682007-08-16 15:56:55 +00002318 if (c) {
2319 dst[i] += rhs[i] + 1;
2320 c = (dst[i] <= l);
2321 } else {
2322 dst[i] += rhs[i];
2323 c = (dst[i] < l);
2324 }
2325 }
2326
2327 return c;
2328}
2329
Craig Topper92fc4772017-04-13 04:36:06 +00002330/// This function adds a single "word" integer, src, to the multiple
2331/// "word" integer array, dst[]. dst[] is modified to reflect the addition and
2332/// 1 is returned if there is a carry out, otherwise 0 is returned.
2333/// @returns the carry of the addition.
2334APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
2335 unsigned parts) {
2336 for (unsigned i = 0; i < parts; ++i) {
2337 dst[i] += src;
2338 if (dst[i] >= src)
2339 return 0; // No need to carry so exit early.
2340 src = 1; // Carry one to next digit.
2341 }
2342
2343 return 1;
2344}
2345
Chris Lattner6b695682007-08-16 15:56:55 +00002346/* DST -= RHS + C where C is zero or one. Returns the carry flag. */
Craig Topper55229b72017-04-02 19:17:22 +00002347APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
2348 WordType c, unsigned parts) {
Chris Lattner6b695682007-08-16 15:56:55 +00002349 assert(c <= 1);
2350
Craig Topperb0038162017-03-28 05:32:52 +00002351 for (unsigned i = 0; i < parts; i++) {
Craig Topper55229b72017-04-02 19:17:22 +00002352 WordType l = dst[i];
Chris Lattner6b695682007-08-16 15:56:55 +00002353 if (c) {
2354 dst[i] -= rhs[i] + 1;
2355 c = (dst[i] >= l);
2356 } else {
2357 dst[i] -= rhs[i];
2358 c = (dst[i] > l);
2359 }
2360 }
2361
2362 return c;
2363}
2364
Craig Topper92fc4772017-04-13 04:36:06 +00002365/// This function subtracts a single "word" (64-bit word), src, from
2366/// the multi-word integer array, dst[], propagating the borrowed 1 value until
2367/// no further borrowing is needed or it runs out of "words" in dst. The result
2368/// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
2369/// exhausted. In other words, if src > dst then this function returns 1,
2370/// otherwise 0.
2371/// @returns the borrow out of the subtraction
2372APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
2373 unsigned parts) {
2374 for (unsigned i = 0; i < parts; ++i) {
2375 WordType Dst = dst[i];
2376 dst[i] -= src;
2377 if (src <= Dst)
2378 return 0; // No need to borrow so exit early.
2379 src = 1; // We have to "borrow 1" from next "word"
2380 }
2381
2382 return 1;
2383}
2384
Chris Lattner6b695682007-08-16 15:56:55 +00002385/* Negate a bignum in-place. */
Craig Topper55229b72017-04-02 19:17:22 +00002386void APInt::tcNegate(WordType *dst, unsigned parts) {
Chris Lattner6b695682007-08-16 15:56:55 +00002387 tcComplement(dst, parts);
2388 tcIncrement(dst, parts);
2389}
2390
Neil Boothc8b650a2007-10-06 00:43:45 +00002391/* DST += SRC * MULTIPLIER + CARRY if add is true
2392 DST = SRC * MULTIPLIER + CARRY if add is false
Chris Lattner6b695682007-08-16 15:56:55 +00002393
2394 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
2395 they must start at the same point, i.e. DST == SRC.
2396
2397 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
2398 returned. Otherwise DST is filled with the least significant
2399 DSTPARTS parts of the result, and if all of the omitted higher
2400 parts were zero return zero, otherwise overflow occurred and
2401 return one. */
Craig Topper55229b72017-04-02 19:17:22 +00002402int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
2403 WordType multiplier, WordType carry,
Craig Topper6a8518082017-03-28 05:32:55 +00002404 unsigned srcParts, unsigned dstParts,
2405 bool add) {
Chris Lattner6b695682007-08-16 15:56:55 +00002406 /* Otherwise our writes of DST kill our later reads of SRC. */
2407 assert(dst <= src || dst >= src + srcParts);
2408 assert(dstParts <= srcParts + 1);
2409
2410 /* N loops; minimum of dstParts and srcParts. */
Craig Topperb0038162017-03-28 05:32:52 +00002411 unsigned n = dstParts < srcParts ? dstParts: srcParts;
Chris Lattner6b695682007-08-16 15:56:55 +00002412
Craig Topperb0038162017-03-28 05:32:52 +00002413 unsigned i;
Dan Gohmanb452d4e2010-03-24 19:38:02 +00002414 for (i = 0; i < n; i++) {
Craig Topper55229b72017-04-02 19:17:22 +00002415 WordType low, mid, high, srcPart;
Chris Lattner6b695682007-08-16 15:56:55 +00002416
2417 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
2418
2419 This cannot overflow, because
2420
2421 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
2422
2423 which is less than n^2. */
2424
2425 srcPart = src[i];
2426
Craig Topper6a8518082017-03-28 05:32:55 +00002427 if (multiplier == 0 || srcPart == 0) {
Chris Lattner6b695682007-08-16 15:56:55 +00002428 low = carry;
2429 high = 0;
2430 } else {
2431 low = lowHalf(srcPart) * lowHalf(multiplier);
2432 high = highHalf(srcPart) * highHalf(multiplier);
2433
2434 mid = lowHalf(srcPart) * highHalf(multiplier);
2435 high += highHalf(mid);
Craig Topper55229b72017-04-02 19:17:22 +00002436 mid <<= APINT_BITS_PER_WORD / 2;
Chris Lattner6b695682007-08-16 15:56:55 +00002437 if (low + mid < low)
2438 high++;
2439 low += mid;
2440
2441 mid = highHalf(srcPart) * lowHalf(multiplier);
2442 high += highHalf(mid);
Craig Topper55229b72017-04-02 19:17:22 +00002443 mid <<= APINT_BITS_PER_WORD / 2;
Chris Lattner6b695682007-08-16 15:56:55 +00002444 if (low + mid < low)
2445 high++;
2446 low += mid;
2447
2448 /* Now add carry. */
2449 if (low + carry < low)
2450 high++;
2451 low += carry;
2452 }
2453
2454 if (add) {
2455 /* And now DST[i], and store the new low part there. */
2456 if (low + dst[i] < low)
2457 high++;
2458 dst[i] += low;
2459 } else
2460 dst[i] = low;
2461
2462 carry = high;
2463 }
2464
2465 if (i < dstParts) {
2466 /* Full multiplication, there is no overflow. */
2467 assert(i + 1 == dstParts);
2468 dst[i] = carry;
2469 return 0;
2470 } else {
2471 /* We overflowed if there is carry. */
2472 if (carry)
2473 return 1;
2474
2475 /* We would overflow if any significant unwritten parts would be
2476 non-zero. This is true if any remaining src parts are non-zero
2477 and the multiplier is non-zero. */
2478 if (multiplier)
Dan Gohmanb452d4e2010-03-24 19:38:02 +00002479 for (; i < srcParts; i++)
Chris Lattner6b695682007-08-16 15:56:55 +00002480 if (src[i])
2481 return 1;
2482
2483 /* We fitted in the narrow destination. */
2484 return 0;
2485 }
2486}
2487
2488/* DST = LHS * RHS, where DST has the same width as the operands and
2489 is filled with the least significant parts of the result. Returns
2490 one if overflow occurred, otherwise zero. DST must be disjoint
2491 from both operands. */
Craig Topper55229b72017-04-02 19:17:22 +00002492int APInt::tcMultiply(WordType *dst, const WordType *lhs,
2493 const WordType *rhs, unsigned parts) {
Chris Lattner6b695682007-08-16 15:56:55 +00002494 assert(dst != lhs && dst != rhs);
2495
Craig Topperb0038162017-03-28 05:32:52 +00002496 int overflow = 0;
Chris Lattner6b695682007-08-16 15:56:55 +00002497 tcSet(dst, 0, parts);
2498
Craig Topperb0038162017-03-28 05:32:52 +00002499 for (unsigned i = 0; i < parts; i++)
Chris Lattner6b695682007-08-16 15:56:55 +00002500 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
2501 parts - i, true);
2502
2503 return overflow;
2504}
2505
Neil Booth0ea72a92007-10-06 00:24:48 +00002506/* DST = LHS * RHS, where DST has width the sum of the widths of the
2507 operands. No overflow occurs. DST must be disjoint from both
2508 operands. Returns the number of parts required to hold the
2509 result. */
Craig Topper55229b72017-04-02 19:17:22 +00002510unsigned APInt::tcFullMultiply(WordType *dst, const WordType *lhs,
2511 const WordType *rhs, unsigned lhsParts,
Craig Topper6a8518082017-03-28 05:32:55 +00002512 unsigned rhsParts) {
Neil Booth0ea72a92007-10-06 00:24:48 +00002513 /* Put the narrower number on the LHS for less loops below. */
2514 if (lhsParts > rhsParts) {
2515 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
2516 } else {
Neil Booth0ea72a92007-10-06 00:24:48 +00002517 assert(dst != lhs && dst != rhs);
Chris Lattner6b695682007-08-16 15:56:55 +00002518
Neil Booth0ea72a92007-10-06 00:24:48 +00002519 tcSet(dst, 0, rhsParts);
Chris Lattner6b695682007-08-16 15:56:55 +00002520
Craig Topperb0038162017-03-28 05:32:52 +00002521 for (unsigned i = 0; i < lhsParts; i++)
2522 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true);
Chris Lattner6b695682007-08-16 15:56:55 +00002523
Craig Topperb0038162017-03-28 05:32:52 +00002524 unsigned n = lhsParts + rhsParts;
Neil Booth0ea72a92007-10-06 00:24:48 +00002525
2526 return n - (dst[n - 1] == 0);
2527 }
Chris Lattner6b695682007-08-16 15:56:55 +00002528}
2529
2530/* If RHS is zero LHS and REMAINDER are left unchanged, return one.
2531 Otherwise set LHS to LHS / RHS with the fractional part discarded,
2532 set REMAINDER to the remainder, return zero. i.e.
2533
2534 OLD_LHS = RHS * LHS + REMAINDER
2535
2536 SCRATCH is a bignum of the same size as the operands and result for
2537 use by the routine; its contents need not be initialized and are
2538 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
2539*/
Craig Topper55229b72017-04-02 19:17:22 +00002540int APInt::tcDivide(WordType *lhs, const WordType *rhs,
2541 WordType *remainder, WordType *srhs,
Craig Topper6a8518082017-03-28 05:32:55 +00002542 unsigned parts) {
Chris Lattner6b695682007-08-16 15:56:55 +00002543 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2544
Craig Topperb0038162017-03-28 05:32:52 +00002545 unsigned shiftCount = tcMSB(rhs, parts) + 1;
Chris Lattnerfe02c1f2007-08-20 22:49:32 +00002546 if (shiftCount == 0)
Chris Lattner6b695682007-08-16 15:56:55 +00002547 return true;
2548
Craig Topper55229b72017-04-02 19:17:22 +00002549 shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;
2550 unsigned n = shiftCount / APINT_BITS_PER_WORD;
2551 WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);
Chris Lattner6b695682007-08-16 15:56:55 +00002552
2553 tcAssign(srhs, rhs, parts);
2554 tcShiftLeft(srhs, parts, shiftCount);
2555 tcAssign(remainder, lhs, parts);
2556 tcSet(lhs, 0, parts);
2557
2558 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
2559 the total. */
Dan Gohmanb452d4e2010-03-24 19:38:02 +00002560 for (;;) {
Chris Lattner6b695682007-08-16 15:56:55 +00002561 int compare;
2562
2563 compare = tcCompare(remainder, srhs, parts);
2564 if (compare >= 0) {
2565 tcSubtract(remainder, srhs, 0, parts);
2566 lhs[n] |= mask;
2567 }
2568
2569 if (shiftCount == 0)
2570 break;
2571 shiftCount--;
2572 tcShiftRight(srhs, parts, 1);
Richard Trieu7a083812016-02-18 22:09:30 +00002573 if ((mask >>= 1) == 0) {
Craig Topper55229b72017-04-02 19:17:22 +00002574 mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);
Richard Trieu7a083812016-02-18 22:09:30 +00002575 n--;
2576 }
Chris Lattner6b695682007-08-16 15:56:55 +00002577 }
2578
2579 return false;
2580}
2581
Craig Toppera8a4f0d2017-04-18 04:39:48 +00002582/// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
2583/// no restrictions on Count.
2584void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {
2585 // Don't bother performing a no-op shift.
2586 if (!Count)
2587 return;
Chris Lattner6b695682007-08-16 15:56:55 +00002588
Craig Toppera8a4f0d2017-04-18 04:39:48 +00002589 /* WordShift is the inter-part shift; BitShift is is intra-part shift. */
2590 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
2591 unsigned BitShift = Count % APINT_BITS_PER_WORD;
Chris Lattner6b695682007-08-16 15:56:55 +00002592
Craig Toppera8a4f0d2017-04-18 04:39:48 +00002593 // Fastpath for moving by whole words.
2594 if (BitShift == 0) {
2595 std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
2596 } else {
2597 while (Words-- > WordShift) {
2598 Dst[Words] = Dst[Words - WordShift] << BitShift;
2599 if (Words > WordShift)
2600 Dst[Words] |=
2601 Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);
Neil Boothb6182162007-10-08 13:47:12 +00002602 }
Neil Boothb6182162007-10-08 13:47:12 +00002603 }
Craig Toppera8a4f0d2017-04-18 04:39:48 +00002604
2605 // Fill in the remainder with 0s.
2606 std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);
Chris Lattner6b695682007-08-16 15:56:55 +00002607}
2608
Craig Topper9575d8f2017-04-17 21:43:43 +00002609/// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
2610/// are no restrictions on Count.
2611void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {
2612 // Don't bother performing a no-op shift.
2613 if (!Count)
2614 return;
Chris Lattner6b695682007-08-16 15:56:55 +00002615
Craig Topper9575d8f2017-04-17 21:43:43 +00002616 // WordShift is the inter-part shift; BitShift is is intra-part shift.
2617 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
2618 unsigned BitShift = Count % APINT_BITS_PER_WORD;
Chris Lattner6b695682007-08-16 15:56:55 +00002619
Craig Topper9575d8f2017-04-17 21:43:43 +00002620 unsigned WordsToMove = Words - WordShift;
2621 // Fastpath for moving by whole words.
2622 if (BitShift == 0) {
2623 std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
2624 } else {
2625 for (unsigned i = 0; i != WordsToMove; ++i) {
2626 Dst[i] = Dst[i + WordShift] >> BitShift;
2627 if (i + 1 != WordsToMove)
2628 Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);
Neil Boothb6182162007-10-08 13:47:12 +00002629 }
Chris Lattner6b695682007-08-16 15:56:55 +00002630 }
Craig Topper9575d8f2017-04-17 21:43:43 +00002631
2632 // Fill in the remainder with 0s.
2633 std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
Chris Lattner6b695682007-08-16 15:56:55 +00002634}
2635
2636/* Bitwise and of two bignums. */
Craig Topper55229b72017-04-02 19:17:22 +00002637void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
Craig Topperb0038162017-03-28 05:32:52 +00002638 for (unsigned i = 0; i < parts; i++)
Chris Lattner6b695682007-08-16 15:56:55 +00002639 dst[i] &= rhs[i];
2640}
2641
2642/* Bitwise inclusive or of two bignums. */
Craig Topper55229b72017-04-02 19:17:22 +00002643void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
Craig Topperb0038162017-03-28 05:32:52 +00002644 for (unsigned i = 0; i < parts; i++)
Chris Lattner6b695682007-08-16 15:56:55 +00002645 dst[i] |= rhs[i];
2646}
2647
2648/* Bitwise exclusive or of two bignums. */
Craig Topper55229b72017-04-02 19:17:22 +00002649void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
Craig Topperb0038162017-03-28 05:32:52 +00002650 for (unsigned i = 0; i < parts; i++)
Chris Lattner6b695682007-08-16 15:56:55 +00002651 dst[i] ^= rhs[i];
2652}
2653
2654/* Complement a bignum in-place. */
Craig Topper55229b72017-04-02 19:17:22 +00002655void APInt::tcComplement(WordType *dst, unsigned parts) {
Craig Topperb0038162017-03-28 05:32:52 +00002656 for (unsigned i = 0; i < parts; i++)
Chris Lattner6b695682007-08-16 15:56:55 +00002657 dst[i] = ~dst[i];
2658}
2659
2660/* Comparison (unsigned) of two bignums. */
Craig Topper55229b72017-04-02 19:17:22 +00002661int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
Craig Topper6a8518082017-03-28 05:32:55 +00002662 unsigned parts) {
Chris Lattner6b695682007-08-16 15:56:55 +00002663 while (parts) {
Craig Topper99cfe4f2017-04-01 21:50:06 +00002664 parts--;
Craig Topper1dc8fc82017-04-21 16:13:15 +00002665 if (lhs[parts] != rhs[parts])
2666 return (lhs[parts] > rhs[parts]) ? 1 : -1;
Craig Topper99cfe4f2017-04-01 21:50:06 +00002667 }
Chris Lattner6b695682007-08-16 15:56:55 +00002668
2669 return 0;
2670}
2671
Chris Lattner6b695682007-08-16 15:56:55 +00002672/* Set the least significant BITS bits of a bignum, clear the
2673 rest. */
Craig Topper55229b72017-04-02 19:17:22 +00002674void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
Craig Topper6a8518082017-03-28 05:32:55 +00002675 unsigned bits) {
Craig Topperb0038162017-03-28 05:32:52 +00002676 unsigned i = 0;
Craig Topper55229b72017-04-02 19:17:22 +00002677 while (bits > APINT_BITS_PER_WORD) {
2678 dst[i++] = ~(WordType) 0;
2679 bits -= APINT_BITS_PER_WORD;
Chris Lattner6b695682007-08-16 15:56:55 +00002680 }
2681
2682 if (bits)
Craig Topper55229b72017-04-02 19:17:22 +00002683 dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);
Chris Lattner6b695682007-08-16 15:56:55 +00002684
2685 while (i < parts)
2686 dst[i++] = 0;
2687}