35 typedef uint64_t Type;
37 BigInteger(
const BigInteger& rhs) : count_(rhs.count_) {
38 std::memcpy(digits_, rhs.digits_, count_ *
sizeof(Type));
41 explicit BigInteger(uint64_t u) : count_(1) {
46 BigInteger(
const Ch* decimals,
size_t length) : count_(1) {
50 const size_t kMaxDigitPerIteration = 19;
51 while (length >= kMaxDigitPerIteration) {
52 AppendDecimal64(decimals + i, decimals + i + kMaxDigitPerIteration);
53 length -= kMaxDigitPerIteration;
54 i += kMaxDigitPerIteration;
58 AppendDecimal64(decimals + i, decimals + i + length);
61 BigInteger& operator=(
const BigInteger &rhs)
65 std::memcpy(digits_, rhs.digits_, count_ *
sizeof(Type));
70 BigInteger& operator=(uint64_t u) {
76 BigInteger& operator+=(uint64_t u) {
77 Type backup = digits_[0];
79 for (
size_t i = 0; i < count_ - 1; i++) {
80 if (digits_[i] >= backup)
82 backup = digits_[i + 1];
87 if (digits_[count_ - 1] < backup)
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;
99 for (
size_t i = 0; i < count_; i++) {
101 digits_[i] = MulAdd64(digits_[i], u, k, &hi);
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;
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);
134 BigInteger& operator<<=(
size_t shift) {
135 if (IsZero() || shift == 0)
return *
this;
137 size_t offset = shift / kTypeBit;
138 size_t interShift = shift % kTypeBit;
141 if (interShift == 0) {
142 std::memmove(digits_ + offset, digits_, count_ *
sizeof(Type));
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;
155 std::memset(digits_, 0, offset *
sizeof(Type));
160 bool operator==(
const BigInteger& rhs)
const {
161 return count_ == rhs.count_ && std::memcmp(digits_, rhs.digits_, count_ *
sizeof(Type)) == 0;
164 bool operator==(
const Type rhs)
const {
165 return count_ == 1 && digits_[0] == rhs;
168 BigInteger& MultiplyPow5(
unsigned exp) {
169 static const uint32_t kPow5[12] = {
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
183 if (exp == 0)
return *
this;
185 for (; exp >= 13; exp -= 13) *
this *=
static_cast<uint32_t
>(1220703125u);
186 if (exp > 0) *
this *= kPow5[exp - 1];
192 bool Difference(
const BigInteger& rhs, BigInteger* out)
const {
193 int cmp = Compare(rhs);
195 const BigInteger *a, *b;
197 if (cmp < 0) { a = &rhs; b =
this; ret =
true; }
198 else { a =
this; b = &rhs; ret =
false; }
201 for (
size_t i = 0; i < a->count_; i++) {
202 Type d = a->digits_[i] - borrow;
205 borrow = (d > a->digits_[i]) ? 1 : 0;
214 int Compare(
const BigInteger& rhs)
const {
215 if (count_ != rhs.count_)
216 return count_ < rhs.count_ ? -1 : 1;
218 for (
size_t i = count_; i-- > 0;)
219 if (digits_[i] != rhs.digits_[i])
220 return digits_[i] < rhs.digits_[i] ? -1 : 1;
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; }
230 template<
typename Ch>
231 void AppendDecimal64(
const Ch* begin,
const Ch* end) {
232 uint64_t u = ParseUint64(begin, end);
236 unsigned exp =
static_cast<unsigned>(end - begin);
237 (MultiplyPow5(exp) <<= exp) += u;
241 void PushBack(Type digit) {
243 digits_[count_++] = digit;
246 template<
typename Ch>
247 static uint64_t ParseUint64(
const Ch* begin,
const Ch* end) {
249 for (
const Ch* p = begin; p != end; ++p) {
251 r = r * 10u +
static_cast<unsigned>(*p - Ch(
'0'));
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;
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);
267 *outHigh =
static_cast<uint64_t
>(p >> 64);
268 return static_cast<uint64_t
>(p);
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;
275 x3 += (
static_cast<uint64_t
>(1) << 32);
276 uint64_t lo = (x1 << 32) + (x0 & 0xFFFFFFFF);
277 uint64_t hi = x3 + (x1 >> 32);
287 static const size_t kBitCount = 3328;
288 static const size_t kCapacity = kBitCount /
sizeof(Type);
289 static const size_t kTypeBit =
sizeof(Type) * 8;
291 Type digits_[kCapacity];