15 #ifndef RAPIDJSON_BIGINTEGER_H_ 16 #define RAPIDJSON_BIGINTEGER_H_ 18 #include "../rapidjson.h" 20 #if defined(_MSC_VER) && defined(_M_AMD64) 24 RAPIDJSON_NAMESPACE_BEGIN
29 typedef uint64_t
Type;
31 BigInteger(
const BigInteger& rhs) : count_(rhs.count_) {
32 std::memcpy(digits_, rhs.digits_, count_ *
sizeof(Type));
35 explicit BigInteger(uint64_t u) : count_(1) {
39 BigInteger(
const char* decimals,
size_t length) : count_(1) {
43 const size_t kMaxDigitPerIteration = 19;
44 while (length >= kMaxDigitPerIteration) {
45 AppendDecimal64(decimals + i, decimals + i + kMaxDigitPerIteration);
46 length -= kMaxDigitPerIteration;
47 i += kMaxDigitPerIteration;
51 AppendDecimal64(decimals + i, decimals + i + length);
54 BigInteger& operator=(uint64_t u) {
60 BigInteger& operator+=(uint64_t u) {
61 Type backup = digits_[0];
63 for (
size_t i = 0; i < count_ - 1; i++) {
64 if (digits_[i] >= backup)
66 backup = digits_[i + 1];
71 if (digits_[count_ - 1] < backup)
77 BigInteger& operator*=(uint64_t u) {
78 if (u == 0)
return *
this = 0;
79 if (u == 1)
return *
this;
80 if (*
this == 1)
return *
this = u;
83 for (
size_t i = 0; i < count_; i++) {
85 digits_[i] = MulAdd64(digits_[i], u, k, &hi);
95 BigInteger& operator*=(uint32_t u) {
96 if (u == 0)
return *
this = 0;
97 if (u == 1)
return *
this;
98 if (*
this == 1)
return *
this = u;
101 for (
size_t i = 0; i < count_; i++) {
102 const uint64_t c = digits_[i] >> 32;
103 const uint64_t d = digits_[i] & 0xFFFFFFFF;
104 const uint64_t uc = u * c;
105 const uint64_t ud = u * d;
106 const uint64_t p0 = ud + k;
107 const uint64_t p1 = uc + (p0 >> 32);
108 digits_[i] = (p0 & 0xFFFFFFFF) | (p1 << 32);
118 BigInteger& operator<<=(
size_t shift) {
119 if (IsZero() || shift == 0)
return *
this;
121 size_t offset = shift / kTypeBit;
122 size_t interShift = shift % kTypeBit;
125 if (interShift == 0) {
126 std::memmove(&digits_[count_ - 1 + offset], &digits_[count_ - 1], count_ *
sizeof(Type));
131 for (
size_t i = count_; i > 0; i--)
132 digits_[i + offset] = (digits_[i] << interShift) | (digits_[i - 1] >> (kTypeBit - interShift));
133 digits_[offset] = digits_[0] << interShift;
139 std::memset(digits_, 0, offset *
sizeof(Type));
144 bool operator==(
const BigInteger& rhs)
const {
145 return count_ == rhs.count_ && std::memcmp(digits_, rhs.digits_, count_ *
sizeof(Type)) == 0;
148 bool operator==(
const Type rhs)
const {
149 return count_ == 1 && digits_[0] == rhs;
152 BigInteger& MultiplyPow5(
unsigned exp) {
153 static const uint32_t kPow5[12] = {
159 5 * 5 * 5 * 5 * 5 * 5,
160 5 * 5 * 5 * 5 * 5 * 5 * 5,
161 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
162 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
163 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
164 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
165 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5
167 if (exp == 0)
return *
this;
169 for (; exp >= 13; exp -= 13) *
this *= static_cast<uint32_t>(1220703125u);
170 if (exp > 0) *
this *= kPow5[exp - 1];
176 bool Difference(
const BigInteger& rhs, BigInteger* out)
const {
177 int cmp = Compare(rhs);
179 const BigInteger *a, *b;
181 if (cmp < 0) { a = &rhs; b =
this; ret =
true; }
182 else { a =
this; b = &rhs; ret =
false; }
185 for (
size_t i = 0; i < a->count_; i++) {
186 Type d = a->digits_[i] - borrow;
189 borrow = (d > a->digits_[i]) ? 1 : 0;
198 int Compare(
const BigInteger& rhs)
const {
199 if (count_ != rhs.count_)
200 return count_ < rhs.count_ ? -1 : 1;
202 for (
size_t i = count_; i-- > 0;)
203 if (digits_[i] != rhs.digits_[i])
204 return digits_[i] < rhs.digits_[i] ? -1 : 1;
209 size_t GetCount()
const {
return count_; }
210 Type GetDigit(
size_t index)
const {
RAPIDJSON_ASSERT(index < count_);
return digits_[index]; }
211 bool IsZero()
const {
return count_ == 1 && digits_[0] == 0; }
214 void AppendDecimal64(
const char* begin,
const char* end) {
215 uint64_t u = ParseUint64(begin, end);
219 unsigned exp =
static_cast<unsigned>(end - begin);
220 (MultiplyPow5(exp) <<= exp) += u;
224 void PushBack(Type digit) {
226 digits_[count_++] = digit;
229 static uint64_t ParseUint64(
const char* begin,
const char* end) {
231 for (
const char* p = begin; p != end; ++p) {
233 r = r * 10 + (*p -
'0');
239 static uint64_t MulAdd64(uint64_t a, uint64_t b, uint64_t k, uint64_t* outHigh) {
240 #if defined(_MSC_VER) && defined(_M_AMD64) 241 uint64_t low = _umul128(a, b, outHigh) + k;
245 #elif (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__x86_64__) 246 __extension__
typedef unsigned __int128 uint128;
247 uint128 p =
static_cast<uint128
>(a) * static_cast<uint128>(b);
249 *outHigh =
static_cast<uint64_t
>(p >> 64);
250 return static_cast<uint64_t
>(p);
252 const uint64_t a0 = a & 0xFFFFFFFF, a1 = a >> 32, b0 = b & 0xFFFFFFFF, b1 = b >> 32;
253 uint64_t x0 = a0 * b0, x1 = a0 * b1, x2 = a1 * b0, x3 = a1 * b1;
257 x3 += (
static_cast<uint64_t
>(1) << 32);
258 uint64_t lo = (x1 << 32) + (x0 & 0xFFFFFFFF);
259 uint64_t hi = x3 + (x1 >> 32);
269 static const size_t kBitCount = 3328;
270 static const size_t kCapacity = kBitCount /
sizeof(
Type);
271 static const size_t kTypeBit =
sizeof(
Type) * 8;
273 Type digits_[kCapacity];
278 RAPIDJSON_NAMESPACE_END
280 #endif // RAPIDJSON_BIGINTEGER_H_ #define RAPIDJSON_UINT64_C2(high32, low32)
Construct a 64-bit literal by a pair of 32-bit integer.
Definition: rapidjson.h:261
Type
Type of JSON value.
Definition: rapidjson.h:642
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:344