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