0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 //===-- APInt.cpp - Implement APInt class ---------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 // The LLVM Compiler Infrastructure
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 // This file is distributed under the University of Illinois Open Source
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 // License. See LICENSE.TXT for details.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 // This file implements a class to represent arbitrary precision integer
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 // constant values and provide a variety of arithmetic operations on them.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 #include "llvm/ADT/APInt.h"
|
120
|
16 #include "llvm/ADT/ArrayRef.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17 #include "llvm/ADT/FoldingSet.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18 #include "llvm/ADT/Hashing.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
19 #include "llvm/ADT/SmallString.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 #include "llvm/ADT/StringRef.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
21 #include "llvm/Support/Debug.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 #include "llvm/Support/ErrorHandling.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23 #include "llvm/Support/MathExtras.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 #include "llvm/Support/raw_ostream.h"
|
120
|
25 #include <climits>
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26 #include <cmath>
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 #include <cstdlib>
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 #include <cstring>
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 using namespace llvm;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30
|
77
|
31 #define DEBUG_TYPE "apint"
|
|
32
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33 /// A utility function for allocating memory, checking for allocation failures,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 /// and ensuring the contents are zeroed.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 inline static uint64_t* getClearedMemory(unsigned numWords) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 uint64_t * result = new uint64_t[numWords];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 assert(result && "APInt memory allocation fails!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38 memset(result, 0, numWords * sizeof(uint64_t));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 return result;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 /// A utility function for allocating memory and checking for allocation
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 /// failure. The content is not zeroed.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44 inline static uint64_t* getMemory(unsigned numWords) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 uint64_t * result = new uint64_t[numWords];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 assert(result && "APInt memory allocation fails!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 return result;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 /// A utility function that converts a character to a digit.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 inline static unsigned getDigit(char cdigit, uint8_t radix) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 unsigned r;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 if (radix == 16 || radix == 36) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 r = cdigit - '0';
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
56 if (r <= 9)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57 return r;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59 r = cdigit - 'A';
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 if (r <= radix - 11U)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 return r + 10;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63 r = cdigit - 'a';
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64 if (r <= radix - 11U)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 return r + 10;
|
121
|
66
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 radix = 10;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
69
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70 r = cdigit - '0';
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
71 if (r < radix)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
72 return r;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74 return -1U;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77
|
120
|
78 void APInt::initSlowCase(uint64_t val, bool isSigned) {
|
121
|
79 U.pVal = getClearedMemory(getNumWords());
|
|
80 U.pVal[0] = val;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 if (isSigned && int64_t(val) < 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82 for (unsigned i = 1; i < getNumWords(); ++i)
|
121
|
83 U.pVal[i] = WORD_MAX;
|
|
84 clearUnusedBits();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 void APInt::initSlowCase(const APInt& that) {
|
121
|
88 U.pVal = getMemory(getNumWords());
|
|
89 memcpy(U.pVal, that.U.pVal, getNumWords() * APINT_WORD_SIZE);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
90 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92 void APInt::initFromArray(ArrayRef<uint64_t> bigVal) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93 assert(BitWidth && "Bitwidth too small");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 assert(bigVal.data() && "Null pointer detected!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
95 if (isSingleWord())
|
121
|
96 U.VAL = bigVal[0];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97 else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
98 // Get memory, cleared to 0
|
121
|
99 U.pVal = getClearedMemory(getNumWords());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
100 // Calculate the number of words to copy
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
101 unsigned words = std::min<unsigned>(bigVal.size(), getNumWords());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102 // Copy the words from bigVal to pVal
|
121
|
103 memcpy(U.pVal, bigVal.data(), words * APINT_WORD_SIZE);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
104 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
105 // Make sure unused high bits are cleared
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106 clearUnusedBits();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
109 APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal)
|
121
|
110 : BitWidth(numBits) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
111 initFromArray(bigVal);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
112 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
113
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
114 APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[])
|
121
|
115 : BitWidth(numBits) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116 initFromArray(makeArrayRef(bigVal, numWords));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
117 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
118
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
119 APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix)
|
121
|
120 : BitWidth(numbits) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
121 assert(BitWidth && "Bitwidth too small");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
122 fromString(numbits, Str, radix);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
123 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124
|
121
|
125 void APInt::reallocate(unsigned NewBitWidth) {
|
|
126 // If the number of words is the same we can just change the width and stop.
|
|
127 if (getNumWords() == getNumWords(NewBitWidth)) {
|
|
128 BitWidth = NewBitWidth;
|
|
129 return;
|
|
130 }
|
|
131
|
|
132 // If we have an allocation, delete it.
|
|
133 if (!isSingleWord())
|
|
134 delete [] U.pVal;
|
|
135
|
|
136 // Update BitWidth.
|
|
137 BitWidth = NewBitWidth;
|
|
138
|
|
139 // If we are supposed to have an allocation, create it.
|
|
140 if (!isSingleWord())
|
|
141 U.pVal = getMemory(getNumWords());
|
|
142 }
|
|
143
|
|
144 void APInt::AssignSlowCase(const APInt& RHS) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
145 // Don't do anything for X = X
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
146 if (this == &RHS)
|
121
|
147 return;
|
|
148
|
|
149 // Adjust the bit width and handle allocations as necessary.
|
|
150 reallocate(RHS.getBitWidth());
|
|
151
|
|
152 // Copy the data.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
153 if (isSingleWord())
|
121
|
154 U.VAL = RHS.U.VAL;
|
|
155 else
|
|
156 memcpy(U.pVal, RHS.U.pVal, getNumWords() * APINT_WORD_SIZE);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
157 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
158
|
95
|
159 /// This method 'profiles' an APInt for use with FoldingSet.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
160 void APInt::Profile(FoldingSetNodeID& ID) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
161 ID.AddInteger(BitWidth);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
162
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
163 if (isSingleWord()) {
|
121
|
164 ID.AddInteger(U.VAL);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
165 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
166 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
167
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
168 unsigned NumWords = getNumWords();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
169 for (unsigned i = 0; i < NumWords; ++i)
|
121
|
170 ID.AddInteger(U.pVal[i]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
171 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
172
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
173 /// @brief Prefix increment operator. Increments the APInt by one.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
174 APInt& APInt::operator++() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
175 if (isSingleWord())
|
121
|
176 ++U.VAL;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
177 else
|
121
|
178 tcIncrement(U.pVal, getNumWords());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
179 return clearUnusedBits();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
180 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
181
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
182 /// @brief Prefix decrement operator. Decrements the APInt by one.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
183 APInt& APInt::operator--() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
184 if (isSingleWord())
|
121
|
185 --U.VAL;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
186 else
|
121
|
187 tcDecrement(U.pVal, getNumWords());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
188 return clearUnusedBits();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
189 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
190
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
191 /// Adds the RHS APint to this APInt.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
192 /// @returns this, after addition of RHS.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
193 /// @brief Addition assignment operator.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
194 APInt& APInt::operator+=(const APInt& RHS) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
195 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
196 if (isSingleWord())
|
121
|
197 U.VAL += RHS.U.VAL;
|
|
198 else
|
|
199 tcAdd(U.pVal, RHS.U.pVal, 0, getNumWords());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
200 return clearUnusedBits();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
201 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
202
|
120
|
203 APInt& APInt::operator+=(uint64_t RHS) {
|
|
204 if (isSingleWord())
|
121
|
205 U.VAL += RHS;
|
120
|
206 else
|
121
|
207 tcAddPart(U.pVal, RHS, getNumWords());
|
120
|
208 return clearUnusedBits();
|
|
209 }
|
|
210
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
211 /// Subtracts the RHS APInt from this APInt
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
212 /// @returns this, after subtraction
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
213 /// @brief Subtraction assignment operator.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
214 APInt& APInt::operator-=(const APInt& RHS) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
215 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
216 if (isSingleWord())
|
121
|
217 U.VAL -= RHS.U.VAL;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
218 else
|
121
|
219 tcSubtract(U.pVal, RHS.U.pVal, 0, getNumWords());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
220 return clearUnusedBits();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
221 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
222
|
120
|
223 APInt& APInt::operator-=(uint64_t RHS) {
|
|
224 if (isSingleWord())
|
121
|
225 U.VAL -= RHS;
|
120
|
226 else
|
121
|
227 tcSubtractPart(U.pVal, RHS, getNumWords());
|
120
|
228 return clearUnusedBits();
|
|
229 }
|
|
230
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
231 APInt APInt::operator*(const APInt& RHS) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
232 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
233 if (isSingleWord())
|
121
|
234 return APInt(BitWidth, U.VAL * RHS.U.VAL);
|
|
235
|
|
236 APInt Result(getMemory(getNumWords()), getBitWidth());
|
|
237
|
|
238 tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords());
|
|
239
|
|
240 Result.clearUnusedBits();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
241 return Result;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
242 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
243
|
121
|
244 void APInt::AndAssignSlowCase(const APInt& RHS) {
|
|
245 tcAnd(U.pVal, RHS.U.pVal, getNumWords());
|
|
246 }
|
|
247
|
|
248 void APInt::OrAssignSlowCase(const APInt& RHS) {
|
|
249 tcOr(U.pVal, RHS.U.pVal, getNumWords());
|
|
250 }
|
|
251
|
|
252 void APInt::XorAssignSlowCase(const APInt& RHS) {
|
|
253 tcXor(U.pVal, RHS.U.pVal, getNumWords());
|
|
254 }
|
|
255
|
|
256 APInt& APInt::operator*=(const APInt& RHS) {
|
|
257 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
|
|
258 *this = *this * RHS;
|
|
259 return *this;
|
|
260 }
|
|
261
|
|
262 APInt& APInt::operator*=(uint64_t RHS) {
|
|
263 if (isSingleWord()) {
|
|
264 U.VAL *= RHS;
|
|
265 } else {
|
|
266 unsigned NumWords = getNumWords();
|
|
267 tcMultiplyPart(U.pVal, U.pVal, RHS, 0, NumWords, NumWords, false);
|
|
268 }
|
|
269 return clearUnusedBits();
|
|
270 }
|
|
271
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
272 bool APInt::EqualSlowCase(const APInt& RHS) const {
|
121
|
273 return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
274 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
275
|
121
|
276 int APInt::compare(const APInt& RHS) const {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
277 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
278 if (isSingleWord())
|
121
|
279 return U.VAL < RHS.U.VAL ? -1 : U.VAL > RHS.U.VAL;
|
|
280
|
|
281 return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
282 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
283
|
121
|
284 int APInt::compareSigned(const APInt& RHS) const {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
285 assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
286 if (isSingleWord()) {
|
121
|
287 int64_t lhsSext = SignExtend64(U.VAL, BitWidth);
|
|
288 int64_t rhsSext = SignExtend64(RHS.U.VAL, BitWidth);
|
|
289 return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
290 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
291
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
292 bool lhsNeg = isNegative();
|
120
|
293 bool rhsNeg = RHS.isNegative();
|
|
294
|
|
295 // If the sign bits don't match, then (LHS < RHS) if LHS is negative
|
|
296 if (lhsNeg != rhsNeg)
|
121
|
297 return lhsNeg ? -1 : 1;
|
|
298
|
|
299 // Otherwise we can just use an unsigned comparison, because even negative
|
120
|
300 // numbers compare correctly this way if both have the same signed-ness.
|
121
|
301 return tcCompare(U.pVal, RHS.U.pVal, getNumWords());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
302 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
303
|
121
|
304 void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) {
|
|
305 unsigned loWord = whichWord(loBit);
|
|
306 unsigned hiWord = whichWord(hiBit);
|
|
307
|
|
308 // Create an initial mask for the low word with zeros below loBit.
|
|
309 uint64_t loMask = WORD_MAX << whichBit(loBit);
|
|
310
|
|
311 // If hiBit is not aligned, we need a high mask.
|
|
312 unsigned hiShiftAmt = whichBit(hiBit);
|
|
313 if (hiShiftAmt != 0) {
|
|
314 // Create a high mask with zeros above hiBit.
|
|
315 uint64_t hiMask = WORD_MAX >> (APINT_BITS_PER_WORD - hiShiftAmt);
|
|
316 // If loWord and hiWord are equal, then we combine the masks. Otherwise,
|
|
317 // set the bits in hiWord.
|
|
318 if (hiWord == loWord)
|
|
319 loMask &= hiMask;
|
|
320 else
|
|
321 U.pVal[hiWord] |= hiMask;
|
|
322 }
|
|
323 // Apply the mask to the low word.
|
|
324 U.pVal[loWord] |= loMask;
|
|
325
|
|
326 // Fill any words between loWord and hiWord with all ones.
|
|
327 for (unsigned word = loWord + 1; word < hiWord; ++word)
|
|
328 U.pVal[word] = WORD_MAX;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
329 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
330
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
331 /// @brief Toggle every bit to its opposite value.
|
121
|
332 void APInt::flipAllBitsSlowCase() {
|
|
333 tcComplement(U.pVal, getNumWords());
|
|
334 clearUnusedBits();
|
|
335 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
336
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
337 /// Toggle a given bit to its opposite value whose position is given
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
338 /// as "bitPosition".
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
339 /// @brief Toggles a given bit to its opposite value.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
340 void APInt::flipBit(unsigned bitPosition) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
341 assert(bitPosition < BitWidth && "Out of the bit-width range!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
342 if ((*this)[bitPosition]) clearBit(bitPosition);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
343 else setBit(bitPosition);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
344 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
345
|
121
|
346 void APInt::insertBits(const APInt &subBits, unsigned bitPosition) {
|
|
347 unsigned subBitWidth = subBits.getBitWidth();
|
|
348 assert(0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth &&
|
|
349 "Illegal bit insertion");
|
|
350
|
|
351 // Insertion is a direct copy.
|
|
352 if (subBitWidth == BitWidth) {
|
|
353 *this = subBits;
|
|
354 return;
|
|
355 }
|
|
356
|
|
357 // Single word result can be done as a direct bitmask.
|
|
358 if (isSingleWord()) {
|
|
359 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
|
|
360 U.VAL &= ~(mask << bitPosition);
|
|
361 U.VAL |= (subBits.U.VAL << bitPosition);
|
|
362 return;
|
|
363 }
|
|
364
|
|
365 unsigned loBit = whichBit(bitPosition);
|
|
366 unsigned loWord = whichWord(bitPosition);
|
|
367 unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
|
|
368
|
|
369 // Insertion within a single word can be done as a direct bitmask.
|
|
370 if (loWord == hi1Word) {
|
|
371 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - subBitWidth);
|
|
372 U.pVal[loWord] &= ~(mask << loBit);
|
|
373 U.pVal[loWord] |= (subBits.U.VAL << loBit);
|
|
374 return;
|
|
375 }
|
|
376
|
|
377 // Insert on word boundaries.
|
|
378 if (loBit == 0) {
|
|
379 // Direct copy whole words.
|
|
380 unsigned numWholeSubWords = subBitWidth / APINT_BITS_PER_WORD;
|
|
381 memcpy(U.pVal + loWord, subBits.getRawData(),
|
|
382 numWholeSubWords * APINT_WORD_SIZE);
|
|
383
|
|
384 // Mask+insert remaining bits.
|
|
385 unsigned remainingBits = subBitWidth % APINT_BITS_PER_WORD;
|
|
386 if (remainingBits != 0) {
|
|
387 uint64_t mask = WORD_MAX >> (APINT_BITS_PER_WORD - remainingBits);
|
|
388 U.pVal[hi1Word] &= ~mask;
|
|
389 U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
|
|
390 }
|
|
391 return;
|
|
392 }
|
|
393
|
|
394 // General case - set/clear individual bits in dst based on src.
|
|
395 // TODO - there is scope for optimization here, but at the moment this code
|
|
396 // path is barely used so prefer readability over performance.
|
|
397 for (unsigned i = 0; i != subBitWidth; ++i) {
|
|
398 if (subBits[i])
|
|
399 setBit(bitPosition + i);
|
|
400 else
|
|
401 clearBit(bitPosition + i);
|
|
402 }
|
|
403 }
|
|
404
|
|
405 APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const {
|
|
406 assert(numBits > 0 && "Can't extract zero bits");
|
|
407 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
|
|
408 "Illegal bit extraction");
|
|
409
|
|
410 if (isSingleWord())
|
|
411 return APInt(numBits, U.VAL >> bitPosition);
|
|
412
|
|
413 unsigned loBit = whichBit(bitPosition);
|
|
414 unsigned loWord = whichWord(bitPosition);
|
|
415 unsigned hiWord = whichWord(bitPosition + numBits - 1);
|
|
416
|
|
417 // Single word result extracting bits from a single word source.
|
|
418 if (loWord == hiWord)
|
|
419 return APInt(numBits, U.pVal[loWord] >> loBit);
|
|
420
|
|
421 // Extracting bits that start on a source word boundary can be done
|
|
422 // as a fast memory copy.
|
|
423 if (loBit == 0)
|
|
424 return APInt(numBits, makeArrayRef(U.pVal + loWord, 1 + hiWord - loWord));
|
|
425
|
|
426 // General case - shift + copy source words directly into place.
|
|
427 APInt Result(numBits, 0);
|
|
428 unsigned NumSrcWords = getNumWords();
|
|
429 unsigned NumDstWords = Result.getNumWords();
|
|
430
|
|
431 for (unsigned word = 0; word < NumDstWords; ++word) {
|
|
432 uint64_t w0 = U.pVal[loWord + word];
|
|
433 uint64_t w1 =
|
|
434 (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
|
|
435 Result.U.pVal[word] = (w0 >> loBit) | (w1 << (APINT_BITS_PER_WORD - loBit));
|
|
436 }
|
|
437
|
|
438 return Result.clearUnusedBits();
|
|
439 }
|
|
440
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
441 unsigned APInt::getBitsNeeded(StringRef str, uint8_t radix) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
442 assert(!str.empty() && "Invalid string length");
|
121
|
443 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
444 radix == 36) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
445 "Radix should be 2, 8, 10, 16, or 36!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
446
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
447 size_t slen = str.size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
448
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
449 // Each computation below needs to know if it's negative.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
450 StringRef::iterator p = str.begin();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
451 unsigned isNegative = *p == '-';
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
452 if (*p == '-' || *p == '+') {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
453 p++;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
454 slen--;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
455 assert(slen && "String is only a sign, needs a value.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
456 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
457
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
458 // For radixes of power-of-two values, the bits required is accurately and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
459 // easily computed
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
460 if (radix == 2)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
461 return slen + isNegative;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
462 if (radix == 8)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
463 return slen * 3 + isNegative;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
464 if (radix == 16)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
465 return slen * 4 + isNegative;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
466
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
467 // FIXME: base 36
|
121
|
468
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
469 // This is grossly inefficient but accurate. We could probably do something
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
470 // with a computation of roughly slen*64/20 and then adjust by the value of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
471 // the first few digits. But, I'm not sure how accurate that could be.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
472
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
473 // Compute a sufficient number of bits that is always large enough but might
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
474 // be too large. This avoids the assertion in the constructor. This
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
475 // calculation doesn't work appropriately for the numbers 0-9, so just use 4
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
476 // bits in that case.
|
121
|
477 unsigned sufficient
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
478 = radix == 10? (slen == 1 ? 4 : slen * 64/18)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
479 : (slen == 1 ? 7 : slen * 16/3);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
480
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
481 // Convert to the actual binary value.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
482 APInt tmp(sufficient, StringRef(p, slen), radix);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
483
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
484 // Compute how many bits are required. If the log is infinite, assume we need
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
485 // just bit.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
486 unsigned log = tmp.logBase2();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
487 if (log == (unsigned)-1) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
488 return isNegative + 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
489 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
490 return isNegative + log + 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
491 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
492 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
493
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
494 hash_code llvm::hash_value(const APInt &Arg) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
495 if (Arg.isSingleWord())
|
121
|
496 return hash_combine(Arg.U.VAL);
|
|
497
|
|
498 return hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
499 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
500
|
95
|
501 bool APInt::isSplat(unsigned SplatSizeInBits) const {
|
|
502 assert(getBitWidth() % SplatSizeInBits == 0 &&
|
|
503 "SplatSizeInBits must divide width!");
|
|
504 // We can check that all parts of an integer are equal by making use of a
|
|
505 // little trick: rotate and check if it's still the same value.
|
|
506 return *this == rotl(SplatSizeInBits);
|
|
507 }
|
|
508
|
|
509 /// This function returns the high "numBits" bits of this APInt.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
510 APInt APInt::getHiBits(unsigned numBits) const {
|
121
|
511 return this->lshr(BitWidth - numBits);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
512 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
513
|
95
|
514 /// This function returns the low "numBits" bits of this APInt.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
515 APInt APInt::getLoBits(unsigned numBits) const {
|
121
|
516 APInt Result(getLowBitsSet(BitWidth, numBits));
|
|
517 Result &= *this;
|
|
518 return Result;
|
|
519 }
|
|
520
|
|
521 /// Return a value containing V broadcasted over NewLen bits.
|
|
522 APInt APInt::getSplat(unsigned NewLen, const APInt &V) {
|
|
523 assert(NewLen >= V.getBitWidth() && "Can't splat to smaller bit width!");
|
|
524
|
|
525 APInt Val = V.zextOrSelf(NewLen);
|
|
526 for (unsigned I = V.getBitWidth(); I < NewLen; I <<= 1)
|
|
527 Val |= Val << I;
|
|
528
|
|
529 return Val;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
530 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
531
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
532 unsigned APInt::countLeadingZerosSlowCase() const {
|
120
|
533 unsigned Count = 0;
|
|
534 for (int i = getNumWords()-1; i >= 0; --i) {
|
121
|
535 uint64_t V = U.pVal[i];
|
120
|
536 if (V == 0)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
537 Count += APINT_BITS_PER_WORD;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
538 else {
|
120
|
539 Count += llvm::countLeadingZeros(V);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
540 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
541 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
542 }
|
120
|
543 // Adjust for unused bits in the most significant word (they are zero).
|
|
544 unsigned Mod = BitWidth % APINT_BITS_PER_WORD;
|
|
545 Count -= Mod > 0 ? APINT_BITS_PER_WORD - Mod : 0;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
546 return Count;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
547 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
548
|
121
|
549 unsigned APInt::countLeadingOnesSlowCase() const {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
550 unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
551 unsigned shift;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
552 if (!highWordBits) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
553 highWordBits = APINT_BITS_PER_WORD;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
554 shift = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
555 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
556 shift = APINT_BITS_PER_WORD - highWordBits;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
557 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
558 int i = getNumWords() - 1;
|
121
|
559 unsigned Count = llvm::countLeadingOnes(U.pVal[i] << shift);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
560 if (Count == highWordBits) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
561 for (i--; i >= 0; --i) {
|
121
|
562 if (U.pVal[i] == WORD_MAX)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
563 Count += APINT_BITS_PER_WORD;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
564 else {
|
121
|
565 Count += llvm::countLeadingOnes(U.pVal[i]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
566 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
567 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
568 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
569 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
570 return Count;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
571 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
572
|
121
|
573 unsigned APInt::countTrailingZerosSlowCase() const {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
574 unsigned Count = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
575 unsigned i = 0;
|
121
|
576 for (; i < getNumWords() && U.pVal[i] == 0; ++i)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
577 Count += APINT_BITS_PER_WORD;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
578 if (i < getNumWords())
|
121
|
579 Count += llvm::countTrailingZeros(U.pVal[i]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
580 return std::min(Count, BitWidth);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
581 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
582
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
583 unsigned APInt::countTrailingOnesSlowCase() const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
584 unsigned Count = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
585 unsigned i = 0;
|
121
|
586 for (; i < getNumWords() && U.pVal[i] == WORD_MAX; ++i)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
587 Count += APINT_BITS_PER_WORD;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
588 if (i < getNumWords())
|
121
|
589 Count += llvm::countTrailingOnes(U.pVal[i]);
|
|
590 assert(Count <= BitWidth);
|
|
591 return Count;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
592 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
593
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
594 unsigned APInt::countPopulationSlowCase() const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
595 unsigned Count = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
596 for (unsigned i = 0; i < getNumWords(); ++i)
|
121
|
597 Count += llvm::countPopulation(U.pVal[i]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
598 return Count;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
599 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
600
|
121
|
601 bool APInt::intersectsSlowCase(const APInt &RHS) const {
|
|
602 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
|
|
603 if ((U.pVal[i] & RHS.U.pVal[i]) != 0)
|
|
604 return true;
|
|
605
|
|
606 return false;
|
|
607 }
|
|
608
|
|
609 bool APInt::isSubsetOfSlowCase(const APInt &RHS) const {
|
|
610 for (unsigned i = 0, e = getNumWords(); i != e; ++i)
|
|
611 if ((U.pVal[i] & ~RHS.U.pVal[i]) != 0)
|
|
612 return false;
|
|
613
|
|
614 return true;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
615 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
616
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
617 APInt APInt::byteSwap() const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
618 assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
619 if (BitWidth == 16)
|
121
|
620 return APInt(BitWidth, ByteSwap_16(uint16_t(U.VAL)));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
621 if (BitWidth == 32)
|
121
|
622 return APInt(BitWidth, ByteSwap_32(unsigned(U.VAL)));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
623 if (BitWidth == 48) {
|
121
|
624 unsigned Tmp1 = unsigned(U.VAL >> 16);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
625 Tmp1 = ByteSwap_32(Tmp1);
|
121
|
626 uint16_t Tmp2 = uint16_t(U.VAL);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
627 Tmp2 = ByteSwap_16(Tmp2);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
628 return APInt(BitWidth, (uint64_t(Tmp2) << 32) | Tmp1);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
629 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
630 if (BitWidth == 64)
|
121
|
631 return APInt(BitWidth, ByteSwap_64(U.VAL));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
632
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
633 APInt Result(getNumWords() * APINT_BITS_PER_WORD, 0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
634 for (unsigned I = 0, N = getNumWords(); I != N; ++I)
|
121
|
635 Result.U.pVal[I] = ByteSwap_64(U.pVal[N - I - 1]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
636 if (Result.BitWidth != BitWidth) {
|
121
|
637 Result.lshrInPlace(Result.BitWidth - BitWidth);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
638 Result.BitWidth = BitWidth;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
639 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
640 return Result;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
641 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
642
|
120
|
643 APInt APInt::reverseBits() const {
|
|
644 switch (BitWidth) {
|
|
645 case 64:
|
121
|
646 return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
|
120
|
647 case 32:
|
121
|
648 return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
|
120
|
649 case 16:
|
121
|
650 return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
|
120
|
651 case 8:
|
121
|
652 return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
|
120
|
653 default:
|
|
654 break;
|
|
655 }
|
|
656
|
|
657 APInt Val(*this);
|
121
|
658 APInt Reversed(BitWidth, 0);
|
|
659 unsigned S = BitWidth;
|
|
660
|
|
661 for (; Val != 0; Val.lshrInPlace(1)) {
|
120
|
662 Reversed <<= 1;
|
121
|
663 Reversed |= Val[0];
|
120
|
664 --S;
|
|
665 }
|
|
666
|
|
667 Reversed <<= S;
|
|
668 return Reversed;
|
|
669 }
|
|
670
|
121
|
671 APInt llvm::APIntOps::GreatestCommonDivisor(APInt A, APInt B) {
|
|
672 // Fast-path a common case.
|
|
673 if (A == B) return A;
|
|
674
|
|
675 // Corner cases: if either operand is zero, the other is the gcd.
|
|
676 if (!A) return B;
|
|
677 if (!B) return A;
|
|
678
|
|
679 // Count common powers of 2 and remove all other powers of 2.
|
|
680 unsigned Pow2;
|
|
681 {
|
|
682 unsigned Pow2_A = A.countTrailingZeros();
|
|
683 unsigned Pow2_B = B.countTrailingZeros();
|
|
684 if (Pow2_A > Pow2_B) {
|
|
685 A.lshrInPlace(Pow2_A - Pow2_B);
|
|
686 Pow2 = Pow2_B;
|
|
687 } else if (Pow2_B > Pow2_A) {
|
|
688 B.lshrInPlace(Pow2_B - Pow2_A);
|
|
689 Pow2 = Pow2_A;
|
|
690 } else {
|
|
691 Pow2 = Pow2_A;
|
|
692 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
693 }
|
121
|
694
|
|
695 // Both operands are odd multiples of 2^Pow_2:
|
|
696 //
|
|
697 // gcd(a, b) = gcd(|a - b| / 2^i, min(a, b))
|
|
698 //
|
|
699 // This is a modified version of Stein's algorithm, taking advantage of
|
|
700 // efficient countTrailingZeros().
|
|
701 while (A != B) {
|
|
702 if (A.ugt(B)) {
|
|
703 A -= B;
|
|
704 A.lshrInPlace(A.countTrailingZeros() - Pow2);
|
|
705 } else {
|
|
706 B -= A;
|
|
707 B.lshrInPlace(B.countTrailingZeros() - Pow2);
|
|
708 }
|
|
709 }
|
|
710
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
711 return A;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
712 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
713
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
714 APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
715 union {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
716 double D;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
717 uint64_t I;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
718 } T;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
719 T.D = Double;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
720
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
721 // Get the sign bit from the highest order bit
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
722 bool isNeg = T.I >> 63;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
723
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
724 // Get the 11-bit exponent and adjust for the 1023 bit bias
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
725 int64_t exp = ((T.I >> 52) & 0x7ff) - 1023;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
726
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
727 // If the exponent is negative, the value is < 0 so just return 0.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
728 if (exp < 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
729 return APInt(width, 0u);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
730
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
731 // Extract the mantissa by clearing the top 12 bits (sign + exponent).
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
732 uint64_t mantissa = (T.I & (~0ULL >> 12)) | 1ULL << 52;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
733
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
734 // If the exponent doesn't shift all bits out of the mantissa
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
735 if (exp < 52)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
736 return isNeg ? -APInt(width, mantissa >> (52 - exp)) :
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
737 APInt(width, mantissa >> (52 - exp));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
738
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
739 // If the client didn't provide enough bits for us to shift the mantissa into
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
740 // then the result is undefined, just return 0
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
741 if (width <= exp - 52)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
742 return APInt(width, 0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
743
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
744 // Otherwise, we have to shift the mantissa bits up to the right location
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
745 APInt Tmp(width, mantissa);
|
121
|
746 Tmp <<= (unsigned)exp - 52;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
747 return isNeg ? -Tmp : Tmp;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
748 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
749
|
95
|
750 /// This function converts this APInt to a double.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
751 /// The layout for double is as following (IEEE Standard 754):
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
752 /// --------------------------------------
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
753 /// | Sign Exponent Fraction Bias |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
754 /// |-------------------------------------- |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
755 /// | 1[63] 11[62-52] 52[51-00] 1023 |
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
756 /// --------------------------------------
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
757 double APInt::roundToDouble(bool isSigned) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
758
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
759 // Handle the simple case where the value is contained in one uint64_t.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
760 // It is wrong to optimize getWord(0) to VAL; there might be more than one word.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
761 if (isSingleWord() || getActiveBits() <= APINT_BITS_PER_WORD) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
762 if (isSigned) {
|
120
|
763 int64_t sext = SignExtend64(getWord(0), BitWidth);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
764 return double(sext);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
765 } else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
766 return double(getWord(0));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
767 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
768
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
769 // Determine if the value is negative.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
770 bool isNeg = isSigned ? (*this)[BitWidth-1] : false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
771
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
772 // Construct the absolute value if we're negative.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
773 APInt Tmp(isNeg ? -(*this) : (*this));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
774
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
775 // Figure out how many bits we're using.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
776 unsigned n = Tmp.getActiveBits();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
777
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
778 // The exponent (without bias normalization) is just the number of bits
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
779 // we are using. Note that the sign bit is gone since we constructed the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
780 // absolute value.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
781 uint64_t exp = n;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
782
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
783 // Return infinity for exponent overflow
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
784 if (exp > 1023) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
785 if (!isSigned || !isNeg)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
786 return std::numeric_limits<double>::infinity();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
787 else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
788 return -std::numeric_limits<double>::infinity();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
789 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
790 exp += 1023; // Increment for 1023 bias
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
791
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
792 // Number of bits in mantissa is 52. To obtain the mantissa value, we must
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
793 // extract the high 52 bits from the correct words in pVal.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
794 uint64_t mantissa;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
795 unsigned hiWord = whichWord(n-1);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
796 if (hiWord == 0) {
|
121
|
797 mantissa = Tmp.U.pVal[0];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
798 if (n > 52)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
799 mantissa >>= n - 52; // shift down, we want the top 52 bits.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
800 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
801 assert(hiWord > 0 && "huh?");
|
121
|
802 uint64_t hibits = Tmp.U.pVal[hiWord] << (52 - n % APINT_BITS_PER_WORD);
|
|
803 uint64_t lobits = Tmp.U.pVal[hiWord-1] >> (11 + n % APINT_BITS_PER_WORD);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
804 mantissa = hibits | lobits;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
805 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
806
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
807 // The leading bit of mantissa is implicit, so get rid of it.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
808 uint64_t sign = isNeg ? (1ULL << (APINT_BITS_PER_WORD - 1)) : 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
809 union {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
810 double D;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
811 uint64_t I;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
812 } T;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
813 T.I = sign | (exp << 52) | mantissa;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
814 return T.D;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
815 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
816
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
817 // Truncate to new width.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
818 APInt APInt::trunc(unsigned width) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
819 assert(width < BitWidth && "Invalid APInt Truncate request");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
820 assert(width && "Can't truncate to 0 bits");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
821
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
822 if (width <= APINT_BITS_PER_WORD)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
823 return APInt(width, getRawData()[0]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
824
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
825 APInt Result(getMemory(getNumWords(width)), width);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
826
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
827 // Copy full words.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
828 unsigned i;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
829 for (i = 0; i != width / APINT_BITS_PER_WORD; i++)
|
121
|
830 Result.U.pVal[i] = U.pVal[i];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
831
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
832 // Truncate and copy any partial word.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
833 unsigned bits = (0 - width) % APINT_BITS_PER_WORD;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
834 if (bits != 0)
|
121
|
835 Result.U.pVal[i] = U.pVal[i] << bits >> bits;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
836
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
837 return Result;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
838 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
839
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
840 // Sign extend to a new width.
|
121
|
841 APInt APInt::sext(unsigned Width) const {
|
|
842 assert(Width > BitWidth && "Invalid APInt SignExtend request");
|
|
843
|
|
844 if (Width <= APINT_BITS_PER_WORD)
|
|
845 return APInt(Width, SignExtend64(U.VAL, BitWidth));
|
|
846
|
|
847 APInt Result(getMemory(getNumWords(Width)), Width);
|
|
848
|
|
849 // Copy words.
|
|
850 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
|
|
851
|
|
852 // Sign extend the last word since there may be unused bits in the input.
|
|
853 Result.U.pVal[getNumWords() - 1] =
|
|
854 SignExtend64(Result.U.pVal[getNumWords() - 1],
|
|
855 ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
|
|
856
|
|
857 // Fill with sign bits.
|
|
858 std::memset(Result.U.pVal + getNumWords(), isNegative() ? -1 : 0,
|
|
859 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
|
|
860 Result.clearUnusedBits();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
861 return Result;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
862 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
863
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
864 // Zero extend to a new width.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
865 APInt APInt::zext(unsigned width) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
866 assert(width > BitWidth && "Invalid APInt ZeroExtend request");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
867
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
868 if (width <= APINT_BITS_PER_WORD)
|
121
|
869 return APInt(width, U.VAL);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
870
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
871 APInt Result(getMemory(getNumWords(width)), width);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
872
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
873 // Copy words.
|
121
|
874 std::memcpy(Result.U.pVal, getRawData(), getNumWords() * APINT_WORD_SIZE);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
875
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
876 // Zero remaining words.
|
121
|
877 std::memset(Result.U.pVal + getNumWords(), 0,
|
|
878 (Result.getNumWords() - getNumWords()) * APINT_WORD_SIZE);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
879
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
880 return Result;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
881 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
882
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
883 APInt APInt::zextOrTrunc(unsigned width) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
884 if (BitWidth < width)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
885 return zext(width);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
886 if (BitWidth > width)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
887 return trunc(width);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
888 return *this;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
889 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
890
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
891 APInt APInt::sextOrTrunc(unsigned width) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
892 if (BitWidth < width)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
893 return sext(width);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
894 if (BitWidth > width)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
895 return trunc(width);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
896 return *this;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
897 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
898
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
899 APInt APInt::zextOrSelf(unsigned width) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
900 if (BitWidth < width)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
901 return zext(width);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
902 return *this;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
903 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
904
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
905 APInt APInt::sextOrSelf(unsigned width) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
906 if (BitWidth < width)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
907 return sext(width);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
908 return *this;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
909 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
910
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
911 /// Arithmetic right-shift this APInt by shiftAmt.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
912 /// @brief Arithmetic right-shift function.
|
121
|
913 void APInt::ashrInPlace(const APInt &shiftAmt) {
|
|
914 ashrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
915 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
916
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
917 /// Arithmetic right-shift this APInt by shiftAmt.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
918 /// @brief Arithmetic right-shift function.
|
121
|
919 void APInt::ashrSlowCase(unsigned ShiftAmt) {
|
|
920 // Don't bother performing a no-op shift.
|
|
921 if (!ShiftAmt)
|
|
922 return;
|
|
923
|
|
924 // Save the original sign bit for later.
|
|
925 bool Negative = isNegative();
|
|
926
|
|
927 // WordShift is the inter-part shift; BitShift is is intra-part shift.
|
|
928 unsigned WordShift = ShiftAmt / APINT_BITS_PER_WORD;
|
|
929 unsigned BitShift = ShiftAmt % APINT_BITS_PER_WORD;
|
|
930
|
|
931 unsigned WordsToMove = getNumWords() - WordShift;
|
|
932 if (WordsToMove != 0) {
|
|
933 // Sign extend the last word to fill in the unused bits.
|
|
934 U.pVal[getNumWords() - 1] = SignExtend64(
|
|
935 U.pVal[getNumWords() - 1], ((BitWidth - 1) % APINT_BITS_PER_WORD) + 1);
|
|
936
|
|
937 // Fastpath for moving by whole words.
|
|
938 if (BitShift == 0) {
|
|
939 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove * APINT_WORD_SIZE);
|
|
940 } else {
|
|
941 // Move the words containing significant bits.
|
|
942 for (unsigned i = 0; i != WordsToMove - 1; ++i)
|
|
943 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
|
|
944 (U.pVal[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift));
|
|
945
|
|
946 // Handle the last word which has no high bits to copy.
|
|
947 U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
|
|
948 // Sign extend one more time.
|
|
949 U.pVal[WordsToMove - 1] =
|
|
950 SignExtend64(U.pVal[WordsToMove - 1], APINT_BITS_PER_WORD - BitShift);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
951 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
952 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
953
|
121
|
954 // Fill in the remainder based on the original sign.
|
|
955 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
|
|
956 WordShift * APINT_WORD_SIZE);
|
|
957 clearUnusedBits();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
958 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
959
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
960 /// Logical right-shift this APInt by shiftAmt.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
961 /// @brief Logical right-shift function.
|
121
|
962 void APInt::lshrInPlace(const APInt &shiftAmt) {
|
|
963 lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth));
|
|
964 }
|
|
965
|
|
966 /// Logical right-shift this APInt by shiftAmt.
|
|
967 /// @brief Logical right-shift function.
|
|
968 void APInt::lshrSlowCase(unsigned ShiftAmt) {
|
|
969 tcShiftRight(U.pVal, getNumWords(), ShiftAmt);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
970 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
971
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
972 /// Left-shift this APInt by shiftAmt.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
973 /// @brief Left-shift function.
|
121
|
974 APInt &APInt::operator<<=(const APInt &shiftAmt) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
975 // It's undefined behavior in C to shift by BitWidth or greater.
|
121
|
976 *this <<= (unsigned)shiftAmt.getLimitedValue(BitWidth);
|
|
977 return *this;
|
|
978 }
|
|
979
|
|
980 void APInt::shlSlowCase(unsigned ShiftAmt) {
|
|
981 tcShiftLeft(U.pVal, getNumWords(), ShiftAmt);
|
|
982 clearUnusedBits();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
983 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
984
|
121
|
985 // Calculate the rotate amount modulo the bit width.
|
|
986 static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) {
|
|
987 unsigned rotBitWidth = rotateAmt.getBitWidth();
|
|
988 APInt rot = rotateAmt;
|
|
989 if (rotBitWidth < BitWidth) {
|
|
990 // Extend the rotate APInt, so that the urem doesn't divide by 0.
|
|
991 // e.g. APInt(1, 32) would give APInt(1, 0).
|
|
992 rot = rotateAmt.zext(BitWidth);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
993 }
|
121
|
994 rot = rot.urem(APInt(rot.getBitWidth(), BitWidth));
|
|
995 return rot.getLimitedValue(BitWidth);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
996 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
997
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
998 APInt APInt::rotl(const APInt &rotateAmt) const {
|
121
|
999 return rotl(rotateModulo(BitWidth, rotateAmt));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1000 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1001
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1002 APInt APInt::rotl(unsigned rotateAmt) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1003 rotateAmt %= BitWidth;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1004 if (rotateAmt == 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1005 return *this;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1006 return shl(rotateAmt) | lshr(BitWidth - rotateAmt);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1007 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1008
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1009 APInt APInt::rotr(const APInt &rotateAmt) const {
|
121
|
1010 return rotr(rotateModulo(BitWidth, rotateAmt));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1011 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1012
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1013 APInt APInt::rotr(unsigned rotateAmt) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1014 rotateAmt %= BitWidth;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1015 if (rotateAmt == 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1016 return *this;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1017 return lshr(rotateAmt) | shl(BitWidth - rotateAmt);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1018 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1019
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1020 // Square Root - this method computes and returns the square root of "this".
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1021 // Three mechanisms are used for computation. For small values (<= 5 bits),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1022 // a table lookup is done. This gets some performance for common cases. For
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1023 // values using less than 52 bits, the value is converted to double and then
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1024 // the libc sqrt function is called. The result is rounded and then converted
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1025 // back to a uint64_t which is then used to construct the result. Finally,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1026 // the Babylonian method for computing square roots is used.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1027 APInt APInt::sqrt() const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1028
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1029 // Determine the magnitude of the value.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1030 unsigned magnitude = getActiveBits();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1031
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1032 // Use a fast table for some small values. This also gets rid of some
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1033 // rounding errors in libc sqrt for small values.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1034 if (magnitude <= 5) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1035 static const uint8_t results[32] = {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1036 /* 0 */ 0,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1037 /* 1- 2 */ 1, 1,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1038 /* 3- 6 */ 2, 2, 2, 2,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1039 /* 7-12 */ 3, 3, 3, 3, 3, 3,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1040 /* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1041 /* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1042 /* 31 */ 6
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1043 };
|
121
|
1044 return APInt(BitWidth, results[ (isSingleWord() ? U.VAL : U.pVal[0]) ]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1045 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1046
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1047 // If the magnitude of the value fits in less than 52 bits (the precision of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1048 // an IEEE double precision floating point value), then we can use the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1049 // libc sqrt function which will probably use a hardware sqrt computation.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1050 // This should be faster than the algorithm below.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1051 if (magnitude < 52) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1052 return APInt(BitWidth,
|
121
|
1053 uint64_t(::round(::sqrt(double(isSingleWord() ? U.VAL
|
|
1054 : U.pVal[0])))));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1055 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1056
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1057 // Okay, all the short cuts are exhausted. We must compute it. The following
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1058 // is a classical Babylonian method for computing the square root. This code
|
83
|
1059 // was adapted to APInt from a wikipedia article on such computations.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1060 // See http://www.wikipedia.org/ and go to the page named
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1061 // Calculate_an_integer_square_root.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1062 unsigned nbits = BitWidth, i = 4;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1063 APInt testy(BitWidth, 16);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1064 APInt x_old(BitWidth, 1);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1065 APInt x_new(BitWidth, 0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1066 APInt two(BitWidth, 2);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1067
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1068 // Select a good starting value using binary logarithms.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1069 for (;; i += 2, testy = testy.shl(2))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1070 if (i >= nbits || this->ule(testy)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1071 x_old = x_old.shl(i / 2);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1072 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1073 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1074
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1075 // Use the Babylonian method to arrive at the integer square root:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1076 for (;;) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1077 x_new = (this->udiv(x_old) + x_old).udiv(two);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1078 if (x_old.ule(x_new))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1079 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1080 x_old = x_new;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1081 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1082
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1083 // Make sure we return the closest approximation
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1084 // NOTE: The rounding calculation below is correct. It will produce an
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1085 // off-by-one discrepancy with results from pari/gp. That discrepancy has been
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1086 // determined to be a rounding issue with pari/gp as it begins to use a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1087 // floating point representation after 192 bits. There are no discrepancies
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1088 // between this algorithm and pari/gp for bit widths < 192 bits.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1089 APInt square(x_old * x_old);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1090 APInt nextSquare((x_old + 1) * (x_old +1));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1091 if (this->ult(square))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1092 return x_old;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1093 assert(this->ule(nextSquare) && "Error in APInt::sqrt computation");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1094 APInt midpoint((nextSquare - square).udiv(two));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1095 APInt offset(*this - square);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1096 if (offset.ult(midpoint))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1097 return x_old;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1098 return x_old + 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1099 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1100
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1101 /// Computes the multiplicative inverse of this APInt for a given modulo. The
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1102 /// iterative extended Euclidean algorithm is used to solve for this value,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1103 /// however we simplify it to speed up calculating only the inverse, and take
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1104 /// advantage of div+rem calculations. We also use some tricks to avoid copying
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1105 /// (potentially large) APInts around.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1106 APInt APInt::multiplicativeInverse(const APInt& modulo) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1107 assert(ult(modulo) && "This APInt must be smaller than the modulo");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1108
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1109 // Using the properties listed at the following web page (accessed 06/21/08):
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1110 // http://www.numbertheory.org/php/euclid.html
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1111 // (especially the properties numbered 3, 4 and 9) it can be proved that
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1112 // BitWidth bits suffice for all the computations in the algorithm implemented
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1113 // below. More precisely, this number of bits suffice if the multiplicative
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1114 // inverse exists, but may not suffice for the general extended Euclidean
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1115 // algorithm.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1116
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1117 APInt r[2] = { modulo, *this };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1118 APInt t[2] = { APInt(BitWidth, 0), APInt(BitWidth, 1) };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1119 APInt q(BitWidth, 0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1120
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1121 unsigned i;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1122 for (i = 0; r[i^1] != 0; i ^= 1) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1123 // An overview of the math without the confusing bit-flipping:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1124 // q = r[i-2] / r[i-1]
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1125 // r[i] = r[i-2] % r[i-1]
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1126 // t[i] = t[i-2] - t[i-1] * q
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1127 udivrem(r[i], r[i^1], q, r[i]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1128 t[i] -= t[i^1] * q;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1129 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1130
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1131 // If this APInt and the modulo are not coprime, there is no multiplicative
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1132 // inverse, so return 0. We check this by looking at the next-to-last
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1133 // remainder, which is the gcd(*this,modulo) as calculated by the Euclidean
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1134 // algorithm.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1135 if (r[i] != 1)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1136 return APInt(BitWidth, 0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1137
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1138 // The next-to-last t is the multiplicative inverse. However, we are
|
121
|
1139 // interested in a positive inverse. Calculate a positive one from a negative
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1140 // one if necessary. A simple addition of the modulo suffices because
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1141 // abs(t[i]) is known to be less than *this/2 (see the link above).
|
121
|
1142 if (t[i].isNegative())
|
|
1143 t[i] += modulo;
|
|
1144
|
|
1145 return std::move(t[i]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1146 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1147
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1148 /// Calculate the magic numbers required to implement a signed integer division
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1149 /// by a constant as a sequence of multiplies, adds and shifts. Requires that
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1150 /// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1151 /// Warren, Jr., chapter 10.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1152 APInt::ms APInt::magic() const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1153 const APInt& d = *this;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1154 unsigned p;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1155 APInt ad, anc, delta, q1, r1, q2, r2, t;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1156 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1157 struct ms mag;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1158
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1159 ad = d.abs();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1160 t = signedMin + (d.lshr(d.getBitWidth() - 1));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1161 anc = t - 1 - t.urem(ad); // absolute value of nc
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1162 p = d.getBitWidth() - 1; // initialize p
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1163 q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1164 r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1165 q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1166 r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1167 do {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1168 p = p + 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1169 q1 = q1<<1; // update q1 = 2p/abs(nc)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1170 r1 = r1<<1; // update r1 = rem(2p/abs(nc))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1171 if (r1.uge(anc)) { // must be unsigned comparison
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1172 q1 = q1 + 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1173 r1 = r1 - anc;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1174 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1175 q2 = q2<<1; // update q2 = 2p/abs(d)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1176 r2 = r2<<1; // update r2 = rem(2p/abs(d))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1177 if (r2.uge(ad)) { // must be unsigned comparison
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1178 q2 = q2 + 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1179 r2 = r2 - ad;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1180 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1181 delta = ad - r2;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1182 } while (q1.ult(delta) || (q1 == delta && r1 == 0));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1183
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1184 mag.m = q2 + 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1185 if (d.isNegative()) mag.m = -mag.m; // resulting magic number
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1186 mag.s = p - d.getBitWidth(); // resulting shift
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1187 return mag;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1188 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1189
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1190 /// Calculate the magic numbers required to implement an unsigned integer
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1191 /// division by a constant as a sequence of multiplies, adds and shifts.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1192 /// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1193 /// S. Warren, Jr., chapter 10.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1194 /// LeadingZeros can be used to simplify the calculation if the upper bits
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1195 /// of the divided value are known zero.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1196 APInt::mu APInt::magicu(unsigned LeadingZeros) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1197 const APInt& d = *this;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1198 unsigned p;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1199 APInt nc, delta, q1, r1, q2, r2;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1200 struct mu magu;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1201 magu.a = 0; // initialize "add" indicator
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1202 APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1203 APInt signedMin = APInt::getSignedMinValue(d.getBitWidth());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1204 APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1205
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1206 nc = allOnes - (allOnes - d).urem(d);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1207 p = d.getBitWidth() - 1; // initialize p
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1208 q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1209 r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1210 q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1211 r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1212 do {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1213 p = p + 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1214 if (r1.uge(nc - r1)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1215 q1 = q1 + q1 + 1; // update q1
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1216 r1 = r1 + r1 - nc; // update r1
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1217 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1218 else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1219 q1 = q1+q1; // update q1
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1220 r1 = r1+r1; // update r1
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1221 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1222 if ((r2 + 1).uge(d - r2)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1223 if (q2.uge(signedMax)) magu.a = 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1224 q2 = q2+q2 + 1; // update q2
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1225 r2 = r2+r2 + 1 - d; // update r2
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1226 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1227 else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1228 if (q2.uge(signedMin)) magu.a = 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1229 q2 = q2+q2; // update q2
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1230 r2 = r2+r2 + 1; // update r2
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1231 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1232 delta = d - 1 - r2;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1233 } while (p < d.getBitWidth()*2 &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1234 (q1.ult(delta) || (q1 == delta && r1 == 0)));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1235 magu.m = q2 + 1; // resulting magic number
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1236 magu.s = p - d.getBitWidth(); // resulting shift
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1237 return magu;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1238 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1239
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1240 /// Implementation of Knuth's Algorithm D (Division of nonnegative integers)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1241 /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1242 /// variables here have the same names as in the algorithm. Comments explain
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1243 /// the algorithm and any deviation from it.
|
121
|
1244 static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t* r,
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1245 unsigned m, unsigned n) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1246 assert(u && "Must provide dividend");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1247 assert(v && "Must provide divisor");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1248 assert(q && "Must provide quotient");
|
95
|
1249 assert(u != v && u != q && v != q && "Must use different memory");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1250 assert(n>1 && "n must be > 1");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1251
|
95
|
1252 // b denotes the base of the number system. In our case b is 2^32.
|
120
|
1253 const uint64_t b = uint64_t(1) << 32;
|
95
|
1254
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1255 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1256 DEBUG(dbgs() << "KnuthDiv: original:");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1257 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1258 DEBUG(dbgs() << " by");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1259 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1260 DEBUG(dbgs() << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1261 // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1262 // u and v by d. Note that we have taken Knuth's advice here to use a power
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1263 // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1264 // 2 allows us to shift instead of multiply and it is easy to determine the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1265 // shift amount from the leading zeros. We are basically normalizing the u
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1266 // and v so that its high bits are shifted to the top of v's range without
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1267 // overflow. Note that this can require an extra word in u so that u must
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1268 // be of length m+n+1.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1269 unsigned shift = countLeadingZeros(v[n-1]);
|
121
|
1270 uint32_t v_carry = 0;
|
|
1271 uint32_t u_carry = 0;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1272 if (shift) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1273 for (unsigned i = 0; i < m+n; ++i) {
|
121
|
1274 uint32_t u_tmp = u[i] >> (32 - shift);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1275 u[i] = (u[i] << shift) | u_carry;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1276 u_carry = u_tmp;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1277 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1278 for (unsigned i = 0; i < n; ++i) {
|
121
|
1279 uint32_t v_tmp = v[i] >> (32 - shift);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1280 v[i] = (v[i] << shift) | v_carry;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1281 v_carry = v_tmp;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1282 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1283 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1284 u[m+n] = u_carry;
|
95
|
1285
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1286 DEBUG(dbgs() << "KnuthDiv: normal:");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1287 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1288 DEBUG(dbgs() << " by");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1289 DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1290 DEBUG(dbgs() << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1291
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1292 // D2. [Initialize j.] Set j to m. This is the loop counter over the places.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1293 int j = m;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1294 do {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1295 DEBUG(dbgs() << "KnuthDiv: quotient digit #" << j << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1296 // D3. [Calculate q'.].
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1297 // Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q')
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1298 // Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r')
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1299 // Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease
|
121
|
1300 // qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1301 // on v[n-2] determines at high speed most of the cases in which the trial
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1302 // value qp is one too large, and it eliminates all cases where qp is two
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1303 // too large.
|
121
|
1304 uint64_t dividend = Make_64(u[j+n], u[j+n-1]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1305 DEBUG(dbgs() << "KnuthDiv: dividend == " << dividend << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1306 uint64_t qp = dividend / v[n-1];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1307 uint64_t rp = dividend % v[n-1];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1308 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1309 qp--;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1310 rp += v[n-1];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1311 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1312 qp--;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1313 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1314 DEBUG(dbgs() << "KnuthDiv: qp == " << qp << ", rp == " << rp << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1315
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1316 // D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1317 // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1318 // consists of a simple multiplication by a one-place number, combined with
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1319 // a subtraction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1320 // The digits (u[j+n]...u[j]) should be kept positive; if the result of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1321 // this step is actually negative, (u[j+n]...u[j]) should be left as the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1322 // true value plus b**(n+1), namely as the b's complement of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1323 // the true value, and a "borrow" to the left should be remembered.
|
95
|
1324 int64_t borrow = 0;
|
|
1325 for (unsigned i = 0; i < n; ++i) {
|
|
1326 uint64_t p = uint64_t(qp) * uint64_t(v[i]);
|
121
|
1327 int64_t subres = int64_t(u[j+i]) - borrow - Lo_32(p);
|
|
1328 u[j+i] = Lo_32(subres);
|
|
1329 borrow = Hi_32(p) - Hi_32(subres);
|
95
|
1330 DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i]
|
|
1331 << ", borrow = " << borrow << '\n');
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1332 }
|
95
|
1333 bool isNeg = u[j+n] < borrow;
|
121
|
1334 u[j+n] -= Lo_32(borrow);
|
95
|
1335
|
|
1336 DEBUG(dbgs() << "KnuthDiv: after subtraction:");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1337 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1338 DEBUG(dbgs() << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1339
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1340 // D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1341 // negative, go to step D6; otherwise go on to step D7.
|
121
|
1342 q[j] = Lo_32(qp);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1343 if (isNeg) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1344 // D6. [Add back]. The probability that this step is necessary is very
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1345 // small, on the order of only 2/b. Make sure that test data accounts for
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1346 // this possibility. Decrease q[j] by 1
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1347 q[j]--;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1348 // and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]).
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1349 // A carry will occur to the left of u[j+n], and it should be ignored
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1350 // since it cancels with the borrow that occurred in D4.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1351 bool carry = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1352 for (unsigned i = 0; i < n; i++) {
|
121
|
1353 uint32_t limit = std::min(u[j+i],v[i]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1354 u[j+i] += v[i] + carry;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1355 carry = u[j+i] < limit || (carry && u[j+i] == limit);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1356 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1357 u[j+n] += carry;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1358 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1359 DEBUG(dbgs() << "KnuthDiv: after correction:");
|
95
|
1360 DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1361 DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1362
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1363 // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1364 } while (--j >= 0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1365
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1366 DEBUG(dbgs() << "KnuthDiv: quotient:");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1367 DEBUG(for (int i = m; i >=0; i--) dbgs() <<" " << q[i]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1368 DEBUG(dbgs() << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1369
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1370 // D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1371 // remainder may be obtained by dividing u[...] by d. If r is non-null we
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1372 // compute the remainder (urem uses this).
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1373 if (r) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1374 // The value d is expressed by the "shift" value above since we avoided
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1375 // multiplication by d by using a shift left. So, all we have to do is
|
121
|
1376 // shift right here.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1377 if (shift) {
|
121
|
1378 uint32_t carry = 0;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1379 DEBUG(dbgs() << "KnuthDiv: remainder:");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1380 for (int i = n-1; i >= 0; i--) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1381 r[i] = (u[i] >> shift) | carry;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1382 carry = u[i] << (32 - shift);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1383 DEBUG(dbgs() << " " << r[i]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1384 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1385 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1386 for (int i = n-1; i >= 0; i--) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1387 r[i] = u[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1388 DEBUG(dbgs() << " " << r[i]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1389 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1390 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1391 DEBUG(dbgs() << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1392 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1393 DEBUG(dbgs() << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1394 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1395
|
121
|
1396 void APInt::divide(const WordType *LHS, unsigned lhsWords, const WordType *RHS,
|
|
1397 unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1398 assert(lhsWords >= rhsWords && "Fractional result");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1399
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1400 // First, compose the values into an array of 32-bit words instead of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1401 // 64-bit words. This is a necessity of both the "short division" algorithm
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1402 // and the Knuth "classical algorithm" which requires there to be native
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1403 // operations for +, -, and * on an m bit value with an m*2 bit result. We
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1404 // can't use 64-bit operands here because we don't have native results of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1405 // 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1406 // work on large-endian machines.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1407 unsigned n = rhsWords * 2;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1408 unsigned m = (lhsWords * 2) - n;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1409
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1410 // Allocate space for the temporary values we need either on the stack, if
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1411 // it will fit, or on the heap if it won't.
|
121
|
1412 uint32_t SPACE[128];
|
|
1413 uint32_t *U = nullptr;
|
|
1414 uint32_t *V = nullptr;
|
|
1415 uint32_t *Q = nullptr;
|
|
1416 uint32_t *R = nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1417 if ((Remainder?4:3)*n+2*m+1 <= 128) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1418 U = &SPACE[0];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1419 V = &SPACE[m+n+1];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1420 Q = &SPACE[(m+n+1) + n];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1421 if (Remainder)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1422 R = &SPACE[(m+n+1) + n + (m+n)];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1423 } else {
|
121
|
1424 U = new uint32_t[m + n + 1];
|
|
1425 V = new uint32_t[n];
|
|
1426 Q = new uint32_t[m+n];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1427 if (Remainder)
|
121
|
1428 R = new uint32_t[n];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1429 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1430
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1431 // Initialize the dividend
|
121
|
1432 memset(U, 0, (m+n+1)*sizeof(uint32_t));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1433 for (unsigned i = 0; i < lhsWords; ++i) {
|
121
|
1434 uint64_t tmp = LHS[i];
|
|
1435 U[i * 2] = Lo_32(tmp);
|
|
1436 U[i * 2 + 1] = Hi_32(tmp);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1437 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1438 U[m+n] = 0; // this extra word is for "spill" in the Knuth algorithm.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1439
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1440 // Initialize the divisor
|
121
|
1441 memset(V, 0, (n)*sizeof(uint32_t));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1442 for (unsigned i = 0; i < rhsWords; ++i) {
|
121
|
1443 uint64_t tmp = RHS[i];
|
|
1444 V[i * 2] = Lo_32(tmp);
|
|
1445 V[i * 2 + 1] = Hi_32(tmp);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1446 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1447
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1448 // initialize the quotient and remainder
|
121
|
1449 memset(Q, 0, (m+n) * sizeof(uint32_t));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1450 if (Remainder)
|
121
|
1451 memset(R, 0, n * sizeof(uint32_t));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1452
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1453 // Now, adjust m and n for the Knuth division. n is the number of words in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1454 // the divisor. m is the number of words by which the dividend exceeds the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1455 // divisor (i.e. m+n is the length of the dividend). These sizes must not
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1456 // contain any zero words or the Knuth algorithm fails.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1457 for (unsigned i = n; i > 0 && V[i-1] == 0; i--) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1458 n--;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1459 m++;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1460 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1461 for (unsigned i = m+n; i > 0 && U[i-1] == 0; i--)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1462 m--;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1463
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1464 // If we're left with only a single word for the divisor, Knuth doesn't work
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1465 // so we implement the short division algorithm here. This is much simpler
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1466 // and faster because we are certain that we can divide a 64-bit quantity
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1467 // by a 32-bit quantity at hardware speed and short division is simply a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1468 // series of such operations. This is just like doing short division but we
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1469 // are using base 2^32 instead of base 10.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1470 assert(n != 0 && "Divide by zero?");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1471 if (n == 1) {
|
121
|
1472 uint32_t divisor = V[0];
|
|
1473 uint32_t remainder = 0;
|
|
1474 for (int i = m; i >= 0; i--) {
|
|
1475 uint64_t partial_dividend = Make_64(remainder, U[i]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1476 if (partial_dividend == 0) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1477 Q[i] = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1478 remainder = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1479 } else if (partial_dividend < divisor) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1480 Q[i] = 0;
|
121
|
1481 remainder = Lo_32(partial_dividend);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1482 } else if (partial_dividend == divisor) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1483 Q[i] = 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1484 remainder = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1485 } else {
|
121
|
1486 Q[i] = Lo_32(partial_dividend / divisor);
|
|
1487 remainder = Lo_32(partial_dividend - (Q[i] * divisor));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1488 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1489 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1490 if (R)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1491 R[0] = remainder;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1492 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1493 // Now we're ready to invoke the Knuth classical divide algorithm. In this
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1494 // case n > 1.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1495 KnuthDiv(U, V, Q, R, m, n);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1496 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1497
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1498 // If the caller wants the quotient
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1499 if (Quotient) {
|
121
|
1500 for (unsigned i = 0; i < lhsWords; ++i)
|
|
1501 Quotient[i] = Make_64(Q[i*2+1], Q[i*2]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1502 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1503
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1504 // If the caller wants the remainder
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1505 if (Remainder) {
|
121
|
1506 for (unsigned i = 0; i < rhsWords; ++i)
|
|
1507 Remainder[i] = Make_64(R[i*2+1], R[i*2]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1508 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1509
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1510 // Clean up the memory we allocated.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1511 if (U != &SPACE[0]) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1512 delete [] U;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1513 delete [] V;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1514 delete [] Q;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1515 delete [] R;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1516 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1517 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1518
|
121
|
1519 APInt APInt::udiv(const APInt &RHS) const {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1520 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1521
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1522 // First, deal with the easy case
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1523 if (isSingleWord()) {
|
121
|
1524 assert(RHS.U.VAL != 0 && "Divide by zero?");
|
|
1525 return APInt(BitWidth, U.VAL / RHS.U.VAL);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1526 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1527
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1528 // Get some facts about the LHS and RHS number of bits and words
|
121
|
1529 unsigned lhsWords = getNumWords(getActiveBits());
|
|
1530 unsigned rhsBits = RHS.getActiveBits();
|
|
1531 unsigned rhsWords = getNumWords(rhsBits);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1532 assert(rhsWords && "Divided by zero???");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1533
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1534 // Deal with some degenerate cases
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1535 if (!lhsWords)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1536 // 0 / X ===> 0
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1537 return APInt(BitWidth, 0);
|
121
|
1538 if (rhsBits == 1)
|
|
1539 // X / 1 ===> X
|
|
1540 return *this;
|
|
1541 if (lhsWords < rhsWords || this->ult(RHS))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1542 // X / Y ===> 0, iff X < Y
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1543 return APInt(BitWidth, 0);
|
121
|
1544 if (*this == RHS)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1545 // X / X ===> 1
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1546 return APInt(BitWidth, 1);
|
121
|
1547 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1548 // All high words are zero, just use native divide
|
121
|
1549 return APInt(BitWidth, this->U.pVal[0] / RHS.U.pVal[0]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1550
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1551 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
|
121
|
1552 APInt Quotient(BitWidth, 0); // to hold result.
|
|
1553 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal, nullptr);
|
|
1554 return Quotient;
|
|
1555 }
|
|
1556
|
|
1557 APInt APInt::udiv(uint64_t RHS) const {
|
|
1558 assert(RHS != 0 && "Divide by zero?");
|
|
1559
|
|
1560 // First, deal with the easy case
|
|
1561 if (isSingleWord())
|
|
1562 return APInt(BitWidth, U.VAL / RHS);
|
|
1563
|
|
1564 // Get some facts about the LHS words.
|
|
1565 unsigned lhsWords = getNumWords(getActiveBits());
|
|
1566
|
|
1567 // Deal with some degenerate cases
|
|
1568 if (!lhsWords)
|
|
1569 // 0 / X ===> 0
|
|
1570 return APInt(BitWidth, 0);
|
|
1571 if (RHS == 1)
|
|
1572 // X / 1 ===> X
|
|
1573 return *this;
|
|
1574 if (this->ult(RHS))
|
|
1575 // X / Y ===> 0, iff X < Y
|
|
1576 return APInt(BitWidth, 0);
|
|
1577 if (*this == RHS)
|
|
1578 // X / X ===> 1
|
|
1579 return APInt(BitWidth, 1);
|
|
1580 if (lhsWords == 1) // rhsWords is 1 if lhsWords is 1.
|
|
1581 // All high words are zero, just use native divide
|
|
1582 return APInt(BitWidth, this->U.pVal[0] / RHS);
|
|
1583
|
|
1584 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
|
|
1585 APInt Quotient(BitWidth, 0); // to hold result.
|
|
1586 divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, nullptr);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1587 return Quotient;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1588 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1589
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1590 APInt APInt::sdiv(const APInt &RHS) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1591 if (isNegative()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1592 if (RHS.isNegative())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1593 return (-(*this)).udiv(-RHS);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1594 return -((-(*this)).udiv(RHS));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1595 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1596 if (RHS.isNegative())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1597 return -(this->udiv(-RHS));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1598 return this->udiv(RHS);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1599 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1600
|
121
|
1601 APInt APInt::sdiv(int64_t RHS) const {
|
|
1602 if (isNegative()) {
|
|
1603 if (RHS < 0)
|
|
1604 return (-(*this)).udiv(-RHS);
|
|
1605 return -((-(*this)).udiv(RHS));
|
|
1606 }
|
|
1607 if (RHS < 0)
|
|
1608 return -(this->udiv(-RHS));
|
|
1609 return this->udiv(RHS);
|
|
1610 }
|
|
1611
|
|
1612 APInt APInt::urem(const APInt &RHS) const {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1613 assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1614 if (isSingleWord()) {
|
121
|
1615 assert(RHS.U.VAL != 0 && "Remainder by zero?");
|
|
1616 return APInt(BitWidth, U.VAL % RHS.U.VAL);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1617 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1618
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1619 // Get some facts about the LHS
|
121
|
1620 unsigned lhsWords = getNumWords(getActiveBits());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1621
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1622 // Get some facts about the RHS
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1623 unsigned rhsBits = RHS.getActiveBits();
|
121
|
1624 unsigned rhsWords = getNumWords(rhsBits);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1625 assert(rhsWords && "Performing remainder operation by zero ???");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1626
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1627 // Check the degenerate cases
|
121
|
1628 if (lhsWords == 0)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1629 // 0 % Y ===> 0
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1630 return APInt(BitWidth, 0);
|
121
|
1631 if (rhsBits == 1)
|
|
1632 // X % 1 ===> 0
|
|
1633 return APInt(BitWidth, 0);
|
|
1634 if (lhsWords < rhsWords || this->ult(RHS))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1635 // X % Y ===> X, iff X < Y
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1636 return *this;
|
121
|
1637 if (*this == RHS)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1638 // X % X == 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1639 return APInt(BitWidth, 0);
|
121
|
1640 if (lhsWords == 1)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1641 // All high words are zero, just use native remainder
|
121
|
1642 return APInt(BitWidth, U.pVal[0] % RHS.U.pVal[0]);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1643
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1644 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
|
121
|
1645 APInt Remainder(BitWidth, 0);
|
|
1646 divide(U.pVal, lhsWords, RHS.U.pVal, rhsWords, nullptr, Remainder.U.pVal);
|
|
1647 return Remainder;
|
|
1648 }
|
|
1649
|
|
1650 uint64_t APInt::urem(uint64_t RHS) const {
|
|
1651 assert(RHS != 0 && "Remainder by zero?");
|
|
1652
|
|
1653 if (isSingleWord())
|
|
1654 return U.VAL % RHS;
|
|
1655
|
|
1656 // Get some facts about the LHS
|
|
1657 unsigned lhsWords = getNumWords(getActiveBits());
|
|
1658
|
|
1659 // Check the degenerate cases
|
|
1660 if (lhsWords == 0)
|
|
1661 // 0 % Y ===> 0
|
|
1662 return 0;
|
|
1663 if (RHS == 1)
|
|
1664 // X % 1 ===> 0
|
|
1665 return 0;
|
|
1666 if (this->ult(RHS))
|
|
1667 // X % Y ===> X, iff X < Y
|
|
1668 return getZExtValue();
|
|
1669 if (*this == RHS)
|
|
1670 // X % X == 0;
|
|
1671 return 0;
|
|
1672 if (lhsWords == 1)
|
|
1673 // All high words are zero, just use native remainder
|
|
1674 return U.pVal[0] % RHS;
|
|
1675
|
|
1676 // We have to compute it the hard way. Invoke the Knuth divide algorithm.
|
|
1677 uint64_t Remainder;
|
|
1678 divide(U.pVal, lhsWords, &RHS, 1, nullptr, &Remainder);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1679 return Remainder;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1680 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1681
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1682 APInt APInt::srem(const APInt &RHS) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1683 if (isNegative()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1684 if (RHS.isNegative())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1685 return -((-(*this)).urem(-RHS));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1686 return -((-(*this)).urem(RHS));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1687 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1688 if (RHS.isNegative())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1689 return this->urem(-RHS);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1690 return this->urem(RHS);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1691 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1692
|
121
|
1693 int64_t APInt::srem(int64_t RHS) const {
|
|
1694 if (isNegative()) {
|
|
1695 if (RHS < 0)
|
|
1696 return -((-(*this)).urem(-RHS));
|
|
1697 return -((-(*this)).urem(RHS));
|
|
1698 }
|
|
1699 if (RHS < 0)
|
|
1700 return this->urem(-RHS);
|
|
1701 return this->urem(RHS);
|
|
1702 }
|
|
1703
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1704 void APInt::udivrem(const APInt &LHS, const APInt &RHS,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1705 APInt &Quotient, APInt &Remainder) {
|
83
|
1706 assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same");
|
121
|
1707 unsigned BitWidth = LHS.BitWidth;
|
83
|
1708
|
|
1709 // First, deal with the easy case
|
|
1710 if (LHS.isSingleWord()) {
|
121
|
1711 assert(RHS.U.VAL != 0 && "Divide by zero?");
|
|
1712 uint64_t QuotVal = LHS.U.VAL / RHS.U.VAL;
|
|
1713 uint64_t RemVal = LHS.U.VAL % RHS.U.VAL;
|
|
1714 Quotient = APInt(BitWidth, QuotVal);
|
|
1715 Remainder = APInt(BitWidth, RemVal);
|
83
|
1716 return;
|
|
1717 }
|
|
1718
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1719 // Get some size facts about the dividend and divisor
|
121
|
1720 unsigned lhsWords = getNumWords(LHS.getActiveBits());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1721 unsigned rhsBits = RHS.getActiveBits();
|
121
|
1722 unsigned rhsWords = getNumWords(rhsBits);
|
|
1723 assert(rhsWords && "Performing divrem operation by zero ???");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1724
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1725 // Check the degenerate cases
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1726 if (lhsWords == 0) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1727 Quotient = 0; // 0 / Y ===> 0
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1728 Remainder = 0; // 0 % Y ===> 0
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1729 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1730 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1731
|
121
|
1732 if (rhsBits == 1) {
|
|
1733 Quotient = LHS; // X / 1 ===> X
|
|
1734 Remainder = 0; // X % 1 ===> 0
|
|
1735 }
|
|
1736
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1737 if (lhsWords < rhsWords || LHS.ult(RHS)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1738 Remainder = LHS; // X % Y ===> X, iff X < Y
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1739 Quotient = 0; // X / Y ===> 0, iff X < Y
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1740 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1741 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1742
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1743 if (LHS == RHS) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1744 Quotient = 1; // X / X ===> 1
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1745 Remainder = 0; // X % X ===> 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1746 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1747 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1748
|
121
|
1749 // Make sure there is enough space to hold the results.
|
|
1750 // NOTE: This assumes that reallocate won't affect any bits if it doesn't
|
|
1751 // change the size. This is necessary if Quotient or Remainder is aliased
|
|
1752 // with LHS or RHS.
|
|
1753 Quotient.reallocate(BitWidth);
|
|
1754 Remainder.reallocate(BitWidth);
|
|
1755
|
|
1756 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1757 // There is only one word to consider so use the native versions.
|
121
|
1758 uint64_t lhsValue = LHS.U.pVal[0];
|
|
1759 uint64_t rhsValue = RHS.U.pVal[0];
|
|
1760 Quotient = lhsValue / rhsValue;
|
|
1761 Remainder = lhsValue % rhsValue;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1762 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1763 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1764
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1765 // Okay, lets do it the long way
|
121
|
1766 divide(LHS.U.pVal, lhsWords, RHS.U.pVal, rhsWords, Quotient.U.pVal,
|
|
1767 Remainder.U.pVal);
|
|
1768 // Clear the rest of the Quotient and Remainder.
|
|
1769 std::memset(Quotient.U.pVal + lhsWords, 0,
|
|
1770 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
|
|
1771 std::memset(Remainder.U.pVal + rhsWords, 0,
|
|
1772 (getNumWords(BitWidth) - rhsWords) * APINT_WORD_SIZE);
|
|
1773 }
|
|
1774
|
|
1775 void APInt::udivrem(const APInt &LHS, uint64_t RHS, APInt &Quotient,
|
|
1776 uint64_t &Remainder) {
|
|
1777 assert(RHS != 0 && "Divide by zero?");
|
|
1778 unsigned BitWidth = LHS.BitWidth;
|
|
1779
|
|
1780 // First, deal with the easy case
|
|
1781 if (LHS.isSingleWord()) {
|
|
1782 uint64_t QuotVal = LHS.U.VAL / RHS;
|
|
1783 Remainder = LHS.U.VAL % RHS;
|
|
1784 Quotient = APInt(BitWidth, QuotVal);
|
|
1785 return;
|
|
1786 }
|
|
1787
|
|
1788 // Get some size facts about the dividend and divisor
|
|
1789 unsigned lhsWords = getNumWords(LHS.getActiveBits());
|
|
1790
|
|
1791 // Check the degenerate cases
|
|
1792 if (lhsWords == 0) {
|
|
1793 Quotient = 0; // 0 / Y ===> 0
|
|
1794 Remainder = 0; // 0 % Y ===> 0
|
|
1795 return;
|
|
1796 }
|
|
1797
|
|
1798 if (RHS == 1) {
|
|
1799 Quotient = LHS; // X / 1 ===> X
|
|
1800 Remainder = 0; // X % 1 ===> 0
|
|
1801 }
|
|
1802
|
|
1803 if (LHS.ult(RHS)) {
|
|
1804 Remainder = LHS.getZExtValue(); // X % Y ===> X, iff X < Y
|
|
1805 Quotient = 0; // X / Y ===> 0, iff X < Y
|
|
1806 return;
|
|
1807 }
|
|
1808
|
|
1809 if (LHS == RHS) {
|
|
1810 Quotient = 1; // X / X ===> 1
|
|
1811 Remainder = 0; // X % X ===> 0;
|
|
1812 return;
|
|
1813 }
|
|
1814
|
|
1815 // Make sure there is enough space to hold the results.
|
|
1816 // NOTE: This assumes that reallocate won't affect any bits if it doesn't
|
|
1817 // change the size. This is necessary if Quotient is aliased with LHS.
|
|
1818 Quotient.reallocate(BitWidth);
|
|
1819
|
|
1820 if (lhsWords == 1) { // rhsWords is 1 if lhsWords is 1.
|
|
1821 // There is only one word to consider so use the native versions.
|
|
1822 uint64_t lhsValue = LHS.U.pVal[0];
|
|
1823 Quotient = lhsValue / RHS;
|
|
1824 Remainder = lhsValue % RHS;
|
|
1825 return;
|
|
1826 }
|
|
1827
|
|
1828 // Okay, lets do it the long way
|
|
1829 divide(LHS.U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal, &Remainder);
|
|
1830 // Clear the rest of the Quotient.
|
|
1831 std::memset(Quotient.U.pVal + lhsWords, 0,
|
|
1832 (getNumWords(BitWidth) - lhsWords) * APINT_WORD_SIZE);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1833 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1834
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1835 void APInt::sdivrem(const APInt &LHS, const APInt &RHS,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1836 APInt &Quotient, APInt &Remainder) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1837 if (LHS.isNegative()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1838 if (RHS.isNegative())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1839 APInt::udivrem(-LHS, -RHS, Quotient, Remainder);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1840 else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1841 APInt::udivrem(-LHS, RHS, Quotient, Remainder);
|
121
|
1842 Quotient.negate();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1843 }
|
121
|
1844 Remainder.negate();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1845 } else if (RHS.isNegative()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1846 APInt::udivrem(LHS, -RHS, Quotient, Remainder);
|
121
|
1847 Quotient.negate();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1848 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1849 APInt::udivrem(LHS, RHS, Quotient, Remainder);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1850 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1851 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1852
|
121
|
1853 void APInt::sdivrem(const APInt &LHS, int64_t RHS,
|
|
1854 APInt &Quotient, int64_t &Remainder) {
|
|
1855 uint64_t R = Remainder;
|
|
1856 if (LHS.isNegative()) {
|
|
1857 if (RHS < 0)
|
|
1858 APInt::udivrem(-LHS, -RHS, Quotient, R);
|
|
1859 else {
|
|
1860 APInt::udivrem(-LHS, RHS, Quotient, R);
|
|
1861 Quotient.negate();
|
|
1862 }
|
|
1863 R = -R;
|
|
1864 } else if (RHS < 0) {
|
|
1865 APInt::udivrem(LHS, -RHS, Quotient, R);
|
|
1866 Quotient.negate();
|
|
1867 } else {
|
|
1868 APInt::udivrem(LHS, RHS, Quotient, R);
|
|
1869 }
|
|
1870 Remainder = R;
|
|
1871 }
|
|
1872
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1873 APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1874 APInt Res = *this+RHS;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1875 Overflow = isNonNegative() == RHS.isNonNegative() &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1876 Res.isNonNegative() != isNonNegative();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1877 return Res;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1878 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1879
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1880 APInt APInt::uadd_ov(const APInt &RHS, bool &Overflow) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1881 APInt Res = *this+RHS;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1882 Overflow = Res.ult(RHS);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1883 return Res;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1884 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1885
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1886 APInt APInt::ssub_ov(const APInt &RHS, bool &Overflow) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1887 APInt Res = *this - RHS;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1888 Overflow = isNonNegative() != RHS.isNonNegative() &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1889 Res.isNonNegative() != isNonNegative();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1890 return Res;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1891 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1892
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1893 APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1894 APInt Res = *this-RHS;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1895 Overflow = Res.ugt(*this);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1896 return Res;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1897 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1898
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1899 APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1900 // MININT/-1 --> overflow.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1901 Overflow = isMinSignedValue() && RHS.isAllOnesValue();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1902 return sdiv(RHS);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1903 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1904
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1905 APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1906 APInt Res = *this * RHS;
|
121
|
1907
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1908 if (*this != 0 && RHS != 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1909 Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1910 else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1911 Overflow = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1912 return Res;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1913 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1914
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1915 APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1916 APInt Res = *this * RHS;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1917
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1918 if (*this != 0 && RHS != 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1919 Overflow = Res.udiv(RHS) != *this || Res.udiv(*this) != RHS;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1920 else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1921 Overflow = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1922 return Res;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1923 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1924
|
83
|
1925 APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const {
|
|
1926 Overflow = ShAmt.uge(getBitWidth());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1927 if (Overflow)
|
83
|
1928 return APInt(BitWidth, 0);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1929
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1930 if (isNonNegative()) // Don't allow sign change.
|
83
|
1931 Overflow = ShAmt.uge(countLeadingZeros());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1932 else
|
83
|
1933 Overflow = ShAmt.uge(countLeadingOnes());
|
121
|
1934
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1935 return *this << ShAmt;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1936 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1937
|
83
|
1938 APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const {
|
|
1939 Overflow = ShAmt.uge(getBitWidth());
|
|
1940 if (Overflow)
|
|
1941 return APInt(BitWidth, 0);
|
|
1942
|
|
1943 Overflow = ShAmt.ugt(countLeadingZeros());
|
|
1944
|
|
1945 return *this << ShAmt;
|
|
1946 }
|
|
1947
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1948
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1949
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1950
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1951 void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1952 // Check our assumptions here
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1953 assert(!str.empty() && "Invalid string length");
|
121
|
1954 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1955 radix == 36) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1956 "Radix should be 2, 8, 10, 16, or 36!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1957
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1958 StringRef::iterator p = str.begin();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1959 size_t slen = str.size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1960 bool isNeg = *p == '-';
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1961 if (*p == '-' || *p == '+') {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1962 p++;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1963 slen--;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1964 assert(slen && "String is only a sign, needs a value.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1965 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1966 assert((slen <= numbits || radix != 2) && "Insufficient bit width");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1967 assert(((slen-1)*3 <= numbits || radix != 8) && "Insufficient bit width");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1968 assert(((slen-1)*4 <= numbits || radix != 16) && "Insufficient bit width");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1969 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1970 "Insufficient bit width");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1971
|
121
|
1972 // Allocate memory if needed
|
|
1973 if (isSingleWord())
|
|
1974 U.VAL = 0;
|
|
1975 else
|
|
1976 U.pVal = getClearedMemory(getNumWords());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1977
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1978 // Figure out if we can shift instead of multiply
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1979 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1980
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1981 // Enter digit traversal loop
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1982 for (StringRef::iterator e = str.end(); p != e; ++p) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1983 unsigned digit = getDigit(*p, radix);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1984 assert(digit < radix && "Invalid character in digit string");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1985
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1986 // Shift or multiply the value by the radix
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1987 if (slen > 1) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1988 if (shift)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1989 *this <<= shift;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1990 else
|
121
|
1991 *this *= radix;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1992 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1993
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1994 // Add in the digit we just interpreted
|
121
|
1995 *this += digit;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1996 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1997 // If its negative, put it in two's complement form
|
121
|
1998 if (isNeg)
|
|
1999 this->negate();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2000 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2001
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2002 void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2003 bool Signed, bool formatAsCLiteral) const {
|
121
|
2004 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2005 Radix == 36) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2006 "Radix should be 2, 8, 10, 16, or 36!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2007
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2008 const char *Prefix = "";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2009 if (formatAsCLiteral) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2010 switch (Radix) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2011 case 2:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2012 // Binary literals are a non-standard extension added in gcc 4.3:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2013 // http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2014 Prefix = "0b";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2015 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2016 case 8:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2017 Prefix = "0";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2018 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2019 case 10:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2020 break; // No prefix
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2021 case 16:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2022 Prefix = "0x";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2023 break;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2024 default:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2025 llvm_unreachable("Invalid radix!");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2026 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2027 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2028
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2029 // First, check for a zero value and just short circuit the logic below.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2030 if (*this == 0) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2031 while (*Prefix) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2032 Str.push_back(*Prefix);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2033 ++Prefix;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2034 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2035 Str.push_back('0');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2036 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2037 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2038
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2039 static const char Digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2040
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2041 if (isSingleWord()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2042 char Buffer[65];
|
121
|
2043 char *BufPtr = std::end(Buffer);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2044
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2045 uint64_t N;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2046 if (!Signed) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2047 N = getZExtValue();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2048 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2049 int64_t I = getSExtValue();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2050 if (I >= 0) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2051 N = I;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2052 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2053 Str.push_back('-');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2054 N = -(uint64_t)I;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2055 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2056 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2057
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2058 while (*Prefix) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2059 Str.push_back(*Prefix);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2060 ++Prefix;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2061 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2062
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2063 while (N) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2064 *--BufPtr = Digits[N % Radix];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2065 N /= Radix;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2066 }
|
121
|
2067 Str.append(BufPtr, std::end(Buffer));
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2068 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2069 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2070
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2071 APInt Tmp(*this);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2072
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2073 if (Signed && isNegative()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2074 // They want to print the signed version and it is a negative value
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2075 // Flip the bits and add one to turn it into the equivalent positive
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2076 // value and put a '-' in the result.
|
121
|
2077 Tmp.negate();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2078 Str.push_back('-');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2079 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2080
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2081 while (*Prefix) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2082 Str.push_back(*Prefix);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2083 ++Prefix;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2084 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2085
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2086 // We insert the digits backward, then reverse them to get the right order.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2087 unsigned StartDig = Str.size();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2088
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2089 // For the 2, 8 and 16 bit cases, we can just shift instead of divide
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2090 // because the number of bits per digit (1, 3 and 4 respectively) divides
|
121
|
2091 // equally. We just shift until the value is zero.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2092 if (Radix == 2 || Radix == 8 || Radix == 16) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2093 // Just shift tmp right for each digit width until it becomes zero
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2094 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2095 unsigned MaskAmt = Radix - 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2096
|
121
|
2097 while (Tmp.getBoolValue()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2098 unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2099 Str.push_back(Digits[Digit]);
|
121
|
2100 Tmp.lshrInPlace(ShiftAmt);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2101 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2102 } else {
|
121
|
2103 while (Tmp.getBoolValue()) {
|
|
2104 uint64_t Digit;
|
|
2105 udivrem(Tmp, Radix, Tmp, Digit);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2106 assert(Digit < Radix && "divide failed");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2107 Str.push_back(Digits[Digit]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2108 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2109 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2110
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2111 // Reverse the digits before returning.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2112 std::reverse(Str.begin()+StartDig, Str.end());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2113 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2114
|
95
|
2115 /// Returns the APInt as a std::string. Note that this is an inefficient method.
|
|
2116 /// It is better to pass in a SmallVector/SmallString to the methods above.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2117 std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2118 SmallString<40> S;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2119 toString(S, Radix, Signed, /* formatAsCLiteral = */false);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2120 return S.str();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2121 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2122
|
121
|
2123 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
|
120
|
2124 LLVM_DUMP_METHOD void APInt::dump() const {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2125 SmallString<40> S, U;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2126 this->toStringUnsigned(U);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2127 this->toStringSigned(S);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2128 dbgs() << "APInt(" << BitWidth << "b, "
|
121
|
2129 << U << "u " << S << "s)\n";
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2130 }
|
121
|
2131 #endif
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2132
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2133 void APInt::print(raw_ostream &OS, bool isSigned) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2134 SmallString<40> S;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2135 this->toString(S, 10, isSigned, /* formatAsCLiteral = */false);
|
95
|
2136 OS << S;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2137 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2138
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2139 // This implements a variety of operations on a representation of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2140 // arbitrary precision, two's-complement, bignum integer values.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2141
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2142 // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2143 // and unrestricting assumption.
|
121
|
2144 static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0,
|
|
2145 "Part width must be divisible by 2!");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2146
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2147 /* Some handy functions local to this file. */
|
121
|
2148
|
|
2149 /* Returns the integer part with the least significant BITS set.
|
|
2150 BITS cannot be zero. */
|
|
2151 static inline APInt::WordType lowBitMask(unsigned bits) {
|
|
2152 assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD);
|
|
2153
|
|
2154 return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits);
|
|
2155 }
|
|
2156
|
|
2157 /* Returns the value of the lower half of PART. */
|
|
2158 static inline APInt::WordType lowHalf(APInt::WordType part) {
|
|
2159 return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2);
|
|
2160 }
|
|
2161
|
|
2162 /* Returns the value of the upper half of PART. */
|
|
2163 static inline APInt::WordType highHalf(APInt::WordType part) {
|
|
2164 return part >> (APInt::APINT_BITS_PER_WORD / 2);
|
|
2165 }
|
|
2166
|
|
2167 /* Returns the bit number of the most significant set bit of a part.
|
|
2168 If the input number has no bits set -1U is returned. */
|
|
2169 static unsigned partMSB(APInt::WordType value) {
|
|
2170 return findLastSet(value, ZB_Max);
|
|
2171 }
|
|
2172
|
|
2173 /* Returns the bit number of the least significant set bit of a
|
|
2174 part. If the input number has no bits set -1U is returned. */
|
|
2175 static unsigned partLSB(APInt::WordType value) {
|
|
2176 return findFirstSet(value, ZB_Max);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2177 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2178
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2179 /* Sets the least significant part of a bignum to the input value, and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2180 zeroes out higher parts. */
|
121
|
2181 void APInt::tcSet(WordType *dst, WordType part, unsigned parts) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2182 assert(parts > 0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2183
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2184 dst[0] = part;
|
121
|
2185 for (unsigned i = 1; i < parts; i++)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2186 dst[i] = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2187 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2188
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2189 /* Assign one bignum to another. */
|
121
|
2190 void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) {
|
|
2191 for (unsigned i = 0; i < parts; i++)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2192 dst[i] = src[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2193 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2194
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2195 /* Returns true if a bignum is zero, false otherwise. */
|
121
|
2196 bool APInt::tcIsZero(const WordType *src, unsigned parts) {
|
|
2197 for (unsigned i = 0; i < parts; i++)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2198 if (src[i])
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2199 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2200
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2201 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2202 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2203
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2204 /* Extract the given bit of a bignum; returns 0 or 1. */
|
121
|
2205 int APInt::tcExtractBit(const WordType *parts, unsigned bit) {
|
|
2206 return (parts[whichWord(bit)] & maskBit(bit)) != 0;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2207 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2208
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2209 /* Set the given bit of a bignum. */
|
121
|
2210 void APInt::tcSetBit(WordType *parts, unsigned bit) {
|
|
2211 parts[whichWord(bit)] |= maskBit(bit);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2212 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2213
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2214 /* Clears the given bit of a bignum. */
|
121
|
2215 void APInt::tcClearBit(WordType *parts, unsigned bit) {
|
|
2216 parts[whichWord(bit)] &= ~maskBit(bit);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2217 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2218
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2219 /* Returns the bit number of the least significant set bit of a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2220 number. If the input number has no bits set -1U is returned. */
|
121
|
2221 unsigned APInt::tcLSB(const WordType *parts, unsigned n) {
|
|
2222 for (unsigned i = 0; i < n; i++) {
|
|
2223 if (parts[i] != 0) {
|
|
2224 unsigned lsb = partLSB(parts[i]);
|
|
2225
|
|
2226 return lsb + i * APINT_BITS_PER_WORD;
|
|
2227 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2228 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2229
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2230 return -1U;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2231 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2232
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2233 /* Returns the bit number of the most significant set bit of a number.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2234 If the input number has no bits set -1U is returned. */
|
121
|
2235 unsigned APInt::tcMSB(const WordType *parts, unsigned n) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2236 do {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2237 --n;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2238
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2239 if (parts[n] != 0) {
|
121
|
2240 unsigned msb = partMSB(parts[n]);
|
|
2241
|
|
2242 return msb + n * APINT_BITS_PER_WORD;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2243 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2244 } while (n);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2245
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2246 return -1U;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2247 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2248
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2249 /* Copy the bit vector of width srcBITS from SRC, starting at bit
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2250 srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2251 the least significant bit of DST. All high bits above srcBITS in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2252 DST are zero-filled. */
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2253 void
|
121
|
2254 APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src,
|
|
2255 unsigned srcBits, unsigned srcLSB) {
|
|
2256 unsigned dstParts = (srcBits + APINT_BITS_PER_WORD - 1) / APINT_BITS_PER_WORD;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2257 assert(dstParts <= dstCount);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2258
|
121
|
2259 unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2260 tcAssign (dst, src + firstSrcPart, dstParts);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2261
|
121
|
2262 unsigned shift = srcLSB % APINT_BITS_PER_WORD;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2263 tcShiftRight (dst, dstParts, shift);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2264
|
121
|
2265 /* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2266 in DST. If this is less that srcBits, append the rest, else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2267 clear the high bits. */
|
121
|
2268 unsigned n = dstParts * APINT_BITS_PER_WORD - shift;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2269 if (n < srcBits) {
|
121
|
2270 WordType mask = lowBitMask (srcBits - n);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2271 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
|
121
|
2272 << n % APINT_BITS_PER_WORD);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2273 } else if (n > srcBits) {
|
121
|
2274 if (srcBits % APINT_BITS_PER_WORD)
|
|
2275 dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2276 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2277
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2278 /* Clear high parts. */
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2279 while (dstParts < dstCount)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2280 dst[dstParts++] = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2281 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2282
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2283 /* DST += RHS + C where C is zero or one. Returns the carry flag. */
|
121
|
2284 APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs,
|
|
2285 WordType c, unsigned parts) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2286 assert(c <= 1);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2287
|
121
|
2288 for (unsigned i = 0; i < parts; i++) {
|
|
2289 WordType l = dst[i];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2290 if (c) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2291 dst[i] += rhs[i] + 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2292 c = (dst[i] <= l);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2293 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2294 dst[i] += rhs[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2295 c = (dst[i] < l);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2296 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2297 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2298
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2299 return c;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2300 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2301
|
121
|
2302 /// This function adds a single "word" integer, src, to the multiple
|
|
2303 /// "word" integer array, dst[]. dst[] is modified to reflect the addition and
|
|
2304 /// 1 is returned if there is a carry out, otherwise 0 is returned.
|
|
2305 /// @returns the carry of the addition.
|
|
2306 APInt::WordType APInt::tcAddPart(WordType *dst, WordType src,
|
|
2307 unsigned parts) {
|
|
2308 for (unsigned i = 0; i < parts; ++i) {
|
|
2309 dst[i] += src;
|
|
2310 if (dst[i] >= src)
|
|
2311 return 0; // No need to carry so exit early.
|
|
2312 src = 1; // Carry one to next digit.
|
|
2313 }
|
|
2314
|
|
2315 return 1;
|
|
2316 }
|
|
2317
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2318 /* DST -= RHS + C where C is zero or one. Returns the carry flag. */
|
121
|
2319 APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs,
|
|
2320 WordType c, unsigned parts) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2321 assert(c <= 1);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2322
|
121
|
2323 for (unsigned i = 0; i < parts; i++) {
|
|
2324 WordType l = dst[i];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2325 if (c) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2326 dst[i] -= rhs[i] + 1;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2327 c = (dst[i] >= l);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2328 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2329 dst[i] -= rhs[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2330 c = (dst[i] > l);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2331 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2332 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2333
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2334 return c;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2335 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2336
|
121
|
2337 /// This function subtracts a single "word" (64-bit word), src, from
|
|
2338 /// the multi-word integer array, dst[], propagating the borrowed 1 value until
|
|
2339 /// no further borrowing is needed or it runs out of "words" in dst. The result
|
|
2340 /// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not
|
|
2341 /// exhausted. In other words, if src > dst then this function returns 1,
|
|
2342 /// otherwise 0.
|
|
2343 /// @returns the borrow out of the subtraction
|
|
2344 APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src,
|
|
2345 unsigned parts) {
|
|
2346 for (unsigned i = 0; i < parts; ++i) {
|
|
2347 WordType Dst = dst[i];
|
|
2348 dst[i] -= src;
|
|
2349 if (src <= Dst)
|
|
2350 return 0; // No need to borrow so exit early.
|
|
2351 src = 1; // We have to "borrow 1" from next "word"
|
|
2352 }
|
|
2353
|
|
2354 return 1;
|
|
2355 }
|
|
2356
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2357 /* Negate a bignum in-place. */
|
121
|
2358 void APInt::tcNegate(WordType *dst, unsigned parts) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2359 tcComplement(dst, parts);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2360 tcIncrement(dst, parts);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2361 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2362
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2363 /* DST += SRC * MULTIPLIER + CARRY if add is true
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2364 DST = SRC * MULTIPLIER + CARRY if add is false
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2365
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2366 Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2367 they must start at the same point, i.e. DST == SRC.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2368
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2369 If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2370 returned. Otherwise DST is filled with the least significant
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2371 DSTPARTS parts of the result, and if all of the omitted higher
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2372 parts were zero return zero, otherwise overflow occurred and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2373 return one. */
|
121
|
2374 int APInt::tcMultiplyPart(WordType *dst, const WordType *src,
|
|
2375 WordType multiplier, WordType carry,
|
|
2376 unsigned srcParts, unsigned dstParts,
|
|
2377 bool add) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2378 /* Otherwise our writes of DST kill our later reads of SRC. */
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2379 assert(dst <= src || dst >= src + srcParts);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2380 assert(dstParts <= srcParts + 1);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2381
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2382 /* N loops; minimum of dstParts and srcParts. */
|
121
|
2383 unsigned n = std::min(dstParts, srcParts);
|
|
2384
|
|
2385 for (unsigned i = 0; i < n; i++) {
|
|
2386 WordType low, mid, high, srcPart;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2387
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2388 /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2389
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2390 This cannot overflow, because
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2391
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2392 (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2393
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2394 which is less than n^2. */
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2395
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2396 srcPart = src[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2397
|
121
|
2398 if (multiplier == 0 || srcPart == 0) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2399 low = carry;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2400 high = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2401 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2402 low = lowHalf(srcPart) * lowHalf(multiplier);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2403 high = highHalf(srcPart) * highHalf(multiplier);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2404
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2405 mid = lowHalf(srcPart) * highHalf(multiplier);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2406 high += highHalf(mid);
|
121
|
2407 mid <<= APINT_BITS_PER_WORD / 2;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2408 if (low + mid < low)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2409 high++;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2410 low += mid;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2411
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2412 mid = highHalf(srcPart) * lowHalf(multiplier);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2413 high += highHalf(mid);
|
121
|
2414 mid <<= APINT_BITS_PER_WORD / 2;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2415 if (low + mid < low)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2416 high++;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2417 low += mid;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2418
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2419 /* Now add carry. */
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2420 if (low + carry < low)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2421 high++;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2422 low += carry;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2423 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2424
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2425 if (add) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2426 /* And now DST[i], and store the new low part there. */
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2427 if (low + dst[i] < low)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2428 high++;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2429 dst[i] += low;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2430 } else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2431 dst[i] = low;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2432
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2433 carry = high;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2434 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2435
|
121
|
2436 if (srcParts < dstParts) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2437 /* Full multiplication, there is no overflow. */
|
121
|
2438 assert(srcParts + 1 == dstParts);
|
|
2439 dst[srcParts] = carry;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2440 return 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2441 }
|
121
|
2442
|
|
2443 /* We overflowed if there is carry. */
|
|
2444 if (carry)
|
|
2445 return 1;
|
|
2446
|
|
2447 /* We would overflow if any significant unwritten parts would be
|
|
2448 non-zero. This is true if any remaining src parts are non-zero
|
|
2449 and the multiplier is non-zero. */
|
|
2450 if (multiplier)
|
|
2451 for (unsigned i = dstParts; i < srcParts; i++)
|
|
2452 if (src[i])
|
|
2453 return 1;
|
|
2454
|
|
2455 /* We fitted in the narrow destination. */
|
|
2456 return 0;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2457 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2458
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2459 /* DST = LHS * RHS, where DST has the same width as the operands and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2460 is filled with the least significant parts of the result. Returns
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2461 one if overflow occurred, otherwise zero. DST must be disjoint
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2462 from both operands. */
|
121
|
2463 int APInt::tcMultiply(WordType *dst, const WordType *lhs,
|
|
2464 const WordType *rhs, unsigned parts) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2465 assert(dst != lhs && dst != rhs);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2466
|
121
|
2467 int overflow = 0;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2468 tcSet(dst, 0, parts);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2469
|
121
|
2470 for (unsigned i = 0; i < parts; i++)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2471 overflow |= tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2472 parts - i, true);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2473
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2474 return overflow;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2475 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2476
|
121
|
2477 /// DST = LHS * RHS, where DST has width the sum of the widths of the
|
|
2478 /// operands. No overflow occurs. DST must be disjoint from both operands.
|
|
2479 void APInt::tcFullMultiply(WordType *dst, const WordType *lhs,
|
|
2480 const WordType *rhs, unsigned lhsParts,
|
|
2481 unsigned rhsParts) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2482 /* Put the narrower number on the LHS for less loops below. */
|
121
|
2483 if (lhsParts > rhsParts)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2484 return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts);
|
121
|
2485
|
|
2486 assert(dst != lhs && dst != rhs);
|
|
2487
|
|
2488 tcSet(dst, 0, rhsParts);
|
|
2489
|
|
2490 for (unsigned i = 0; i < lhsParts; i++)
|
|
2491 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2492 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2493
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2494 /* If RHS is zero LHS and REMAINDER are left unchanged, return one.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2495 Otherwise set LHS to LHS / RHS with the fractional part discarded,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2496 set REMAINDER to the remainder, return zero. i.e.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2497
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2498 OLD_LHS = RHS * LHS + REMAINDER
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2499
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2500 SCRATCH is a bignum of the same size as the operands and result for
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2501 use by the routine; its contents need not be initialized and are
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2502 destroyed. LHS, REMAINDER and SCRATCH must be distinct.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2503 */
|
121
|
2504 int APInt::tcDivide(WordType *lhs, const WordType *rhs,
|
|
2505 WordType *remainder, WordType *srhs,
|
|
2506 unsigned parts) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2507 assert(lhs != remainder && lhs != srhs && remainder != srhs);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2508
|
121
|
2509 unsigned shiftCount = tcMSB(rhs, parts) + 1;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2510 if (shiftCount == 0)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2511 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2512
|
121
|
2513 shiftCount = parts * APINT_BITS_PER_WORD - shiftCount;
|
|
2514 unsigned n = shiftCount / APINT_BITS_PER_WORD;
|
|
2515 WordType mask = (WordType) 1 << (shiftCount % APINT_BITS_PER_WORD);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2516
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2517 tcAssign(srhs, rhs, parts);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2518 tcShiftLeft(srhs, parts, shiftCount);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2519 tcAssign(remainder, lhs, parts);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2520 tcSet(lhs, 0, parts);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2521
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2522 /* Loop, subtracting SRHS if REMAINDER is greater and adding that to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2523 the total. */
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2524 for (;;) {
|
121
|
2525 int compare = tcCompare(remainder, srhs, parts);
|
|
2526 if (compare >= 0) {
|
|
2527 tcSubtract(remainder, srhs, 0, parts);
|
|
2528 lhs[n] |= mask;
|
|
2529 }
|
|
2530
|
|
2531 if (shiftCount == 0)
|
|
2532 break;
|
|
2533 shiftCount--;
|
|
2534 tcShiftRight(srhs, parts, 1);
|
|
2535 if ((mask >>= 1) == 0) {
|
|
2536 mask = (WordType) 1 << (APINT_BITS_PER_WORD - 1);
|
|
2537 n--;
|
|
2538 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2539 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2540
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2541 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2542 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2543
|
121
|
2544 /// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are
|
|
2545 /// no restrictions on Count.
|
|
2546 void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) {
|
|
2547 // Don't bother performing a no-op shift.
|
|
2548 if (!Count)
|
|
2549 return;
|
|
2550
|
|
2551 // WordShift is the inter-part shift; BitShift is the intra-part shift.
|
|
2552 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
|
|
2553 unsigned BitShift = Count % APINT_BITS_PER_WORD;
|
|
2554
|
|
2555 // Fastpath for moving by whole words.
|
|
2556 if (BitShift == 0) {
|
|
2557 std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE);
|
|
2558 } else {
|
|
2559 while (Words-- > WordShift) {
|
|
2560 Dst[Words] = Dst[Words - WordShift] << BitShift;
|
|
2561 if (Words > WordShift)
|
|
2562 Dst[Words] |=
|
|
2563 Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2564 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2565 }
|
121
|
2566
|
|
2567 // Fill in the remainder with 0s.
|
|
2568 std::memset(Dst, 0, WordShift * APINT_WORD_SIZE);
|
|
2569 }
|
|
2570
|
|
2571 /// Shift a bignum right Count bits in-place. Shifted in bits are zero. There
|
|
2572 /// are no restrictions on Count.
|
|
2573 void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {
|
|
2574 // Don't bother performing a no-op shift.
|
|
2575 if (!Count)
|
|
2576 return;
|
|
2577
|
|
2578 // WordShift is the inter-part shift; BitShift is the intra-part shift.
|
|
2579 unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words);
|
|
2580 unsigned BitShift = Count % APINT_BITS_PER_WORD;
|
|
2581
|
|
2582 unsigned WordsToMove = Words - WordShift;
|
|
2583 // Fastpath for moving by whole words.
|
|
2584 if (BitShift == 0) {
|
|
2585 std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE);
|
|
2586 } else {
|
|
2587 for (unsigned i = 0; i != WordsToMove; ++i) {
|
|
2588 Dst[i] = Dst[i + WordShift] >> BitShift;
|
|
2589 if (i + 1 != WordsToMove)
|
|
2590 Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift);
|
|
2591 }
|
|
2592 }
|
|
2593
|
|
2594 // Fill in the remainder with 0s.
|
|
2595 std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2596 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2597
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2598 /* Bitwise and of two bignums. */
|
121
|
2599 void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) {
|
|
2600 for (unsigned i = 0; i < parts; i++)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2601 dst[i] &= rhs[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2602 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2603
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2604 /* Bitwise inclusive or of two bignums. */
|
121
|
2605 void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) {
|
|
2606 for (unsigned i = 0; i < parts; i++)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2607 dst[i] |= rhs[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2608 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2609
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2610 /* Bitwise exclusive or of two bignums. */
|
121
|
2611 void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) {
|
|
2612 for (unsigned i = 0; i < parts; i++)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2613 dst[i] ^= rhs[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2614 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2615
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2616 /* Complement a bignum in-place. */
|
121
|
2617 void APInt::tcComplement(WordType *dst, unsigned parts) {
|
|
2618 for (unsigned i = 0; i < parts; i++)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2619 dst[i] = ~dst[i];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2620 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2621
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2622 /* Comparison (unsigned) of two bignums. */
|
121
|
2623 int APInt::tcCompare(const WordType *lhs, const WordType *rhs,
|
|
2624 unsigned parts) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2625 while (parts) {
|
121
|
2626 parts--;
|
|
2627 if (lhs[parts] != rhs[parts])
|
|
2628 return (lhs[parts] > rhs[parts]) ? 1 : -1;
|
|
2629 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2630
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2631 return 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2632 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2633
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2634 /* Set the least significant BITS bits of a bignum, clear the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2635 rest. */
|
121
|
2636 void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts,
|
|
2637 unsigned bits) {
|
|
2638 unsigned i = 0;
|
|
2639 while (bits > APINT_BITS_PER_WORD) {
|
|
2640 dst[i++] = ~(WordType) 0;
|
|
2641 bits -= APINT_BITS_PER_WORD;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2642 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2643
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2644 if (bits)
|
121
|
2645 dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2646
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2647 while (i < parts)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2648 dst[i++] = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2649 }
|