1 // Tencent is pleased to support the open source community by making RapidJSON available.
3 // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
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
8 // http://opensource.org/licenses/MIT
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.
15 #ifndef RAPIDJSON_BIGINTEGER_H_
16 #define RAPIDJSON_BIGINTEGER_H_
18 #include "../rapidjson.h"
20 #if defined(_MSC_VER) && defined(_M_AMD64)
21 #include <intrin.h> // for _umul128
22 #pragma intrinsic(_umul128)
25 RAPIDJSON_NAMESPACE_BEGIN
30 typedef uint64_t Type
;
32 BigInteger(const BigInteger
& rhs
) : count_(rhs
.count_
) {
33 std::memcpy(digits_
, rhs
.digits_
, count_
* sizeof(Type
));
36 explicit BigInteger(uint64_t u
) : count_(1) {
40 BigInteger(const char* decimals
, size_t length
) : count_(1) {
41 RAPIDJSON_ASSERT(length
> 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
;
52 AppendDecimal64(decimals
+ i
, decimals
+ i
+ length
);
55 BigInteger
& operator=(const BigInteger
&rhs
)
59 std::memcpy(digits_
, rhs
.digits_
, count_
* sizeof(Type
));
64 BigInteger
& operator=(uint64_t u
) {
70 BigInteger
& operator+=(uint64_t u
) {
71 Type backup
= digits_
[0];
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];
81 if (digits_
[count_
- 1] < backup
)
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
;
93 for (size_t i
= 0; i
< count_
; i
++) {
95 digits_
[i
] = MulAdd64(digits_
[i
], u
, k
, &hi
);
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
;
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);
128 BigInteger
& operator<<=(size_t shift
) {
129 if (IsZero() || shift
== 0) return *this;
131 size_t offset
= shift
/ kTypeBit
;
132 size_t interShift
= shift
% kTypeBit
;
133 RAPIDJSON_ASSERT(count_
+ offset
<= kCapacity
);
135 if (interShift
== 0) {
136 std::memmove(&digits_
[count_
- 1 + offset
], &digits_
[count_
- 1], count_
* sizeof(Type
));
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
;
149 std::memset(digits_
, 0, offset
* sizeof(Type
));
154 bool operator==(const BigInteger
& rhs
) const {
155 return count_
== rhs
.count_
&& std::memcmp(digits_
, rhs
.digits_
, count_
* sizeof(Type
)) == 0;
158 bool operator==(const Type rhs
) const {
159 return count_
== 1 && digits_
[0] == rhs
;
162 BigInteger
& MultiplyPow5(unsigned exp
) {
163 static const uint32_t kPow5
[12] = {
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
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];
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
191 if (cmp
< 0) { a
= &rhs
; b
= this; ret
= true; }
192 else { a
= this; b
= &rhs
; ret
= false; }
195 for (size_t i
= 0; i
< a
->count_
; i
++) {
196 Type d
= a
->digits_
[i
] - borrow
;
199 borrow
= (d
> a
->digits_
[i
]) ? 1 : 0;
208 int Compare(const BigInteger
& rhs
) const {
209 if (count_
!= rhs
.count_
)
210 return count_
< rhs
.count_
? -1 : 1;
212 for (size_t i
= count_
; i
-- > 0;)
213 if (digits_
[i
] != rhs
.digits_
[i
])
214 return digits_
[i
] < rhs
.digits_
[i
] ? -1 : 1;
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; }
224 void AppendDecimal64(const char* begin
, const char* end
) {
225 uint64_t u
= ParseUint64(begin
, end
);
229 unsigned exp
= static_cast<unsigned>(end
- begin
);
230 (MultiplyPow5(exp
) <<= exp
) += u
; // *this = *this * 10^exp + u
234 void PushBack(Type digit
) {
235 RAPIDJSON_ASSERT(count_
< kCapacity
);
236 digits_
[count_
++] = digit
;
239 static uint64_t ParseUint64(const char* begin
, const char* end
) {
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');
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
;
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
);
259 *outHigh
= static_cast<uint64_t>(p
>> 64);
260 return static_cast<uint64_t>(p
);
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
267 x3
+= (static_cast<uint64_t>(1) << 32);
268 uint64_t lo
= (x1
<< 32) + (x0
& 0xFFFFFFFF);
269 uint64_t hi
= x3
+ (x1
>> 32);
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;
283 Type digits_
[kCapacity
];
287 } // namespace internal
288 RAPIDJSON_NAMESPACE_END
290 #endif // RAPIDJSON_BIGINTEGER_H_