]>
Commit | Line | Data |
---|---|---|
31f18b77 FG |
1 | // Tencent is pleased to support the open source community by making RapidJSON available. |
2 | // | |
3 | // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved. | |
4 | // | |
5 | // Licensed under the MIT License (the "License"); you may not use this file except | |
6 | // in compliance with the License. You may obtain a copy of the License at | |
7 | // | |
8 | // http://opensource.org/licenses/MIT | |
9 | // | |
10 | // Unless required by applicable law or agreed to in writing, software distributed | |
11 | // under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR | |
12 | // CONDITIONS OF ANY KIND, either express or implied. See the License for the | |
13 | // specific language governing permissions and limitations under the License. | |
14 | ||
15 | #ifndef RAPIDJSON_BIGINTEGER_H_ | |
16 | #define RAPIDJSON_BIGINTEGER_H_ | |
17 | ||
18 | #include "../rapidjson.h" | |
19 | ||
20 | #if defined(_MSC_VER) && defined(_M_AMD64) | |
21 | #include <intrin.h> // for _umul128 | |
22 | #pragma intrinsic(_umul128) | |
23 | #endif | |
24 | ||
25 | RAPIDJSON_NAMESPACE_BEGIN | |
26 | namespace internal { | |
27 | ||
28 | class BigInteger { | |
29 | public: | |
30 | typedef uint64_t Type; | |
31 | ||
32 | BigInteger(const BigInteger& rhs) : count_(rhs.count_) { | |
33 | std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type)); | |
34 | } | |
35 | ||
36 | explicit BigInteger(uint64_t u) : count_(1) { | |
37 | digits_[0] = u; | |
38 | } | |
39 | ||
40 | BigInteger(const char* decimals, size_t length) : count_(1) { | |
41 | RAPIDJSON_ASSERT(length > 0); | |
42 | digits_[0] = 0; | |
43 | size_t i = 0; | |
44 | const size_t kMaxDigitPerIteration = 19; // 2^64 = 18446744073709551616 > 10^19 | |
45 | while (length >= kMaxDigitPerIteration) { | |
46 | AppendDecimal64(decimals + i, decimals + i + kMaxDigitPerIteration); | |
47 | length -= kMaxDigitPerIteration; | |
48 | i += kMaxDigitPerIteration; | |
49 | } | |
50 | ||
51 | if (length > 0) | |
52 | AppendDecimal64(decimals + i, decimals + i + length); | |
53 | } | |
54 | ||
55 | BigInteger& operator=(const BigInteger &rhs) | |
56 | { | |
57 | if (this != &rhs) { | |
58 | count_ = rhs.count_; | |
59 | std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type)); | |
60 | } | |
61 | return *this; | |
62 | } | |
63 | ||
64 | BigInteger& operator=(uint64_t u) { | |
65 | digits_[0] = u; | |
66 | count_ = 1; | |
67 | return *this; | |
68 | } | |
69 | ||
70 | BigInteger& operator+=(uint64_t u) { | |
71 | Type backup = digits_[0]; | |
72 | digits_[0] += u; | |
73 | for (size_t i = 0; i < count_ - 1; i++) { | |
74 | if (digits_[i] >= backup) | |
75 | return *this; // no carry | |
76 | backup = digits_[i + 1]; | |
77 | digits_[i + 1] += 1; | |
78 | } | |
79 | ||
80 | // Last carry | |
81 | if (digits_[count_ - 1] < backup) | |
82 | PushBack(1); | |
83 | ||
84 | return *this; | |
85 | } | |
86 | ||
87 | BigInteger& operator*=(uint64_t u) { | |
88 | if (u == 0) return *this = 0; | |
89 | if (u == 1) return *this; | |
90 | if (*this == 1) return *this = u; | |
91 | ||
92 | uint64_t k = 0; | |
93 | for (size_t i = 0; i < count_; i++) { | |
94 | uint64_t hi; | |
95 | digits_[i] = MulAdd64(digits_[i], u, k, &hi); | |
96 | k = hi; | |
97 | } | |
98 | ||
99 | if (k > 0) | |
100 | PushBack(k); | |
101 | ||
102 | return *this; | |
103 | } | |
104 | ||
105 | BigInteger& operator*=(uint32_t u) { | |
106 | if (u == 0) return *this = 0; | |
107 | if (u == 1) return *this; | |
108 | if (*this == 1) return *this = u; | |
109 | ||
110 | uint64_t k = 0; | |
111 | for (size_t i = 0; i < count_; i++) { | |
112 | const uint64_t c = digits_[i] >> 32; | |
113 | const uint64_t d = digits_[i] & 0xFFFFFFFF; | |
114 | const uint64_t uc = u * c; | |
115 | const uint64_t ud = u * d; | |
116 | const uint64_t p0 = ud + k; | |
117 | const uint64_t p1 = uc + (p0 >> 32); | |
118 | digits_[i] = (p0 & 0xFFFFFFFF) | (p1 << 32); | |
119 | k = p1 >> 32; | |
120 | } | |
121 | ||
122 | if (k > 0) | |
123 | PushBack(k); | |
124 | ||
125 | return *this; | |
126 | } | |
127 | ||
128 | BigInteger& operator<<=(size_t shift) { | |
129 | if (IsZero() || shift == 0) return *this; | |
130 | ||
131 | size_t offset = shift / kTypeBit; | |
132 | size_t interShift = shift % kTypeBit; | |
133 | RAPIDJSON_ASSERT(count_ + offset <= kCapacity); | |
134 | ||
135 | if (interShift == 0) { | |
136 | std::memmove(&digits_[count_ - 1 + offset], &digits_[count_ - 1], count_ * sizeof(Type)); | |
137 | count_ += offset; | |
138 | } | |
139 | else { | |
140 | digits_[count_] = 0; | |
141 | for (size_t i = count_; i > 0; i--) | |
142 | digits_[i + offset] = (digits_[i] << interShift) | (digits_[i - 1] >> (kTypeBit - interShift)); | |
143 | digits_[offset] = digits_[0] << interShift; | |
144 | count_ += offset; | |
145 | if (digits_[count_]) | |
146 | count_++; | |
147 | } | |
148 | ||
149 | std::memset(digits_, 0, offset * sizeof(Type)); | |
150 | ||
151 | return *this; | |
152 | } | |
153 | ||
154 | bool operator==(const BigInteger& rhs) const { | |
155 | return count_ == rhs.count_ && std::memcmp(digits_, rhs.digits_, count_ * sizeof(Type)) == 0; | |
156 | } | |
157 | ||
158 | bool operator==(const Type rhs) const { | |
159 | return count_ == 1 && digits_[0] == rhs; | |
160 | } | |
161 | ||
162 | BigInteger& MultiplyPow5(unsigned exp) { | |
163 | static const uint32_t kPow5[12] = { | |
164 | 5, | |
165 | 5 * 5, | |
166 | 5 * 5 * 5, | |
167 | 5 * 5 * 5 * 5, | |
168 | 5 * 5 * 5 * 5 * 5, | |
169 | 5 * 5 * 5 * 5 * 5 * 5, | |
170 | 5 * 5 * 5 * 5 * 5 * 5 * 5, | |
171 | 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, | |
172 | 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, | |
173 | 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, | |
174 | 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, | |
175 | 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 | |
176 | }; | |
177 | if (exp == 0) return *this; | |
178 | for (; exp >= 27; exp -= 27) *this *= RAPIDJSON_UINT64_C2(0X6765C793, 0XFA10079D); // 5^27 | |
179 | for (; exp >= 13; exp -= 13) *this *= static_cast<uint32_t>(1220703125u); // 5^13 | |
180 | if (exp > 0) *this *= kPow5[exp - 1]; | |
181 | return *this; | |
182 | } | |
183 | ||
184 | // Compute absolute difference of this and rhs. | |
185 | // Assume this != rhs | |
186 | bool Difference(const BigInteger& rhs, BigInteger* out) const { | |
187 | int cmp = Compare(rhs); | |
188 | RAPIDJSON_ASSERT(cmp != 0); | |
189 | const BigInteger *a, *b; // Makes a > b | |
190 | bool ret; | |
191 | if (cmp < 0) { a = &rhs; b = this; ret = true; } | |
192 | else { a = this; b = &rhs; ret = false; } | |
193 | ||
194 | Type borrow = 0; | |
195 | for (size_t i = 0; i < a->count_; i++) { | |
196 | Type d = a->digits_[i] - borrow; | |
197 | if (i < b->count_) | |
198 | d -= b->digits_[i]; | |
199 | borrow = (d > a->digits_[i]) ? 1 : 0; | |
200 | out->digits_[i] = d; | |
201 | if (d != 0) | |
202 | out->count_ = i + 1; | |
203 | } | |
204 | ||
205 | return ret; | |
206 | } | |
207 | ||
208 | int Compare(const BigInteger& rhs) const { | |
209 | if (count_ != rhs.count_) | |
210 | return count_ < rhs.count_ ? -1 : 1; | |
211 | ||
212 | for (size_t i = count_; i-- > 0;) | |
213 | if (digits_[i] != rhs.digits_[i]) | |
214 | return digits_[i] < rhs.digits_[i] ? -1 : 1; | |
215 | ||
216 | return 0; | |
217 | } | |
218 | ||
219 | size_t GetCount() const { return count_; } | |
220 | Type GetDigit(size_t index) const { RAPIDJSON_ASSERT(index < count_); return digits_[index]; } | |
221 | bool IsZero() const { return count_ == 1 && digits_[0] == 0; } | |
222 | ||
223 | private: | |
224 | void AppendDecimal64(const char* begin, const char* end) { | |
225 | uint64_t u = ParseUint64(begin, end); | |
226 | if (IsZero()) | |
227 | *this = u; | |
228 | else { | |
229 | unsigned exp = static_cast<unsigned>(end - begin); | |
230 | (MultiplyPow5(exp) <<= exp) += u; // *this = *this * 10^exp + u | |
231 | } | |
232 | } | |
233 | ||
234 | void PushBack(Type digit) { | |
235 | RAPIDJSON_ASSERT(count_ < kCapacity); | |
236 | digits_[count_++] = digit; | |
237 | } | |
238 | ||
239 | static uint64_t ParseUint64(const char* begin, const char* end) { | |
240 | uint64_t r = 0; | |
241 | for (const char* p = begin; p != end; ++p) { | |
242 | RAPIDJSON_ASSERT(*p >= '0' && *p <= '9'); | |
243 | r = r * 10u + static_cast<unsigned>(*p - '0'); | |
244 | } | |
245 | return r; | |
246 | } | |
247 | ||
248 | // Assume a * b + k < 2^128 | |
249 | static uint64_t MulAdd64(uint64_t a, uint64_t b, uint64_t k, uint64_t* outHigh) { | |
250 | #if defined(_MSC_VER) && defined(_M_AMD64) | |
251 | uint64_t low = _umul128(a, b, outHigh) + k; | |
252 | if (low < k) | |
253 | (*outHigh)++; | |
254 | return low; | |
255 | #elif (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__x86_64__) | |
256 | __extension__ typedef unsigned __int128 uint128; | |
257 | uint128 p = static_cast<uint128>(a) * static_cast<uint128>(b); | |
258 | p += k; | |
259 | *outHigh = static_cast<uint64_t>(p >> 64); | |
260 | return static_cast<uint64_t>(p); | |
261 | #else | |
262 | const uint64_t a0 = a & 0xFFFFFFFF, a1 = a >> 32, b0 = b & 0xFFFFFFFF, b1 = b >> 32; | |
263 | uint64_t x0 = a0 * b0, x1 = a0 * b1, x2 = a1 * b0, x3 = a1 * b1; | |
264 | x1 += (x0 >> 32); // can't give carry | |
265 | x1 += x2; | |
266 | if (x1 < x2) | |
267 | x3 += (static_cast<uint64_t>(1) << 32); | |
268 | uint64_t lo = (x1 << 32) + (x0 & 0xFFFFFFFF); | |
269 | uint64_t hi = x3 + (x1 >> 32); | |
270 | ||
271 | lo += k; | |
272 | if (lo < k) | |
273 | hi++; | |
274 | *outHigh = hi; | |
275 | return lo; | |
276 | #endif | |
277 | } | |
278 | ||
279 | static const size_t kBitCount = 3328; // 64bit * 54 > 10^1000 | |
280 | static const size_t kCapacity = kBitCount / sizeof(Type); | |
281 | static const size_t kTypeBit = sizeof(Type) * 8; | |
282 | ||
283 | Type digits_[kCapacity]; | |
284 | size_t count_; | |
285 | }; | |
286 | ||
287 | } // namespace internal | |
288 | RAPIDJSON_NAMESPACE_END | |
289 | ||
290 | #endif // RAPIDJSON_BIGINTEGER_H_ |