/src/rapidjson/include/rapidjson/internal/biginteger.h

Source
// Tencent is pleased to support the open source community by making RapidJSON available.
// 
// Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip.
//
// Licensed under the MIT License (the "License"); you may not use this file except
// in compliance with the License. You may obtain a copy of the License at
//
// http://opensource.org/licenses/MIT
//
// Unless required by applicable law or agreed to in writing, software distributed 
// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR 
// CONDITIONS OF ANY KIND, either express or implied. See the License for the 
// specific language governing permissions and limitations under the License.

#ifndef RAPIDJSON_BIGINTEGER_H_
#define RAPIDJSON_BIGINTEGER_H_

#include "../rapidjson.h"

#if defined(_MSC_VER) && !defined(__INTEL_COMPILER) && defined(_M_AMD64)
#include <intrin.h> // for _umul128
#if !defined(_ARM64EC_)
#pragma intrinsic(_umul128)
#else
#pragma comment(lib,"softintrin")
#endif
#endif

RAPIDJSON_NAMESPACE_BEGIN
namespace internal {

class BigInteger {
public:
    typedef uint64_t Type;

    BigInteger(const BigInteger& rhs) : count_(rhs.count_) {
        std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
    }

    explicit BigInteger(uint64_t u) : count_(1) {
        digits_[0] = u;
    }

    template<typename Ch>
    BigInteger(const Ch* decimals, size_t length) : count_(1) {
        RAPIDJSON_ASSERT(length > 0);
        digits_[0] = 0;
        size_t i = 0;
        const size_t kMaxDigitPerIteration = 19;  // 2^64 = 18446744073709551616 > 10^19
        while (length >= kMaxDigitPerIteration) {
            AppendDecimal64(decimals + i, decimals + i + kMaxDigitPerIteration);
            length -= kMaxDigitPerIteration;
            i += kMaxDigitPerIteration;
        }

        if (length > 0)
            AppendDecimal64(decimals + i, decimals + i + length);
    }
    
    BigInteger& operator=(const BigInteger &rhs)
    {
        if (this != &rhs) {
            count_ = rhs.count_;
            std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
        }
        return *this;
    }
    
    BigInteger& operator=(uint64_t u) {
        digits_[0] = u;            
        count_ = 1;
        return *this;
    }

    BigInteger& operator+=(uint64_t u) {
        Type backup = digits_[0];
        digits_[0] += u;
        for (size_t i = 0; i < count_ - 1; i++) {
            if (digits_[i] >= backup)
                return *this; // no carry
            backup = digits_[i + 1];
            digits_[i + 1] += 1;
        }

        // Last carry
        if (digits_[count_ - 1] < backup)
            PushBack(1);

        return *this;
    }

    BigInteger& operator*=(uint64_t u) {
        if (u == 0) return *this = 0;
        if (u == 1) return *this;
        if (*this == 1) return *this = u;

        uint64_t k = 0;
        for (size_t i = 0; i < count_; i++) {
            uint64_t hi;
            digits_[i] = MulAdd64(digits_[i], u, k, &hi);
            k = hi;
        }
        
        if (k > 0)
            PushBack(k);

        return *this;
    }

    BigInteger& operator*=(uint32_t u) {
        if (u == 0) return *this = 0;
        if (u == 1) return *this;
        if (*this == 1) return *this = u;

        uint64_t k = 0;
        for (size_t i = 0; i < count_; i++) {
            const uint64_t c = digits_[i] >> 32;
            const uint64_t d = digits_[i] & 0xFFFFFFFF;
            const uint64_t uc = u * c;
            const uint64_t ud = u * d;
            const uint64_t p0 = ud + k;
            const uint64_t p1 = uc + (p0 >> 32);
            digits_[i] = (p0 & 0xFFFFFFFF) | (p1 << 32);
            k = p1 >> 32;
        }
        
        if (k > 0)
            PushBack(k);

        return *this;
    }

    BigInteger& operator<<=(size_t shift) {
        if (IsZero() || shift == 0) return *this;

        size_t offset = shift / kTypeBit;
        size_t interShift = shift % kTypeBit;
        RAPIDJSON_ASSERT(count_ + offset <= kCapacity);

        if (interShift == 0) {
            std::memmove(digits_ + offset, digits_, count_ * sizeof(Type));
            count_ += offset;
        }
        else {
            digits_[count_] = 0;
            for (size_t i = count_; i > 0; i--)
                digits_[i + offset] = (digits_[i] << interShift) | (digits_[i - 1] >> (kTypeBit - interShift));
            digits_[offset] = digits_[0] << interShift;
            count_ += offset;
            if (digits_[count_])
                count_++;
        }

        std::memset(digits_, 0, offset * sizeof(Type));

        return *this;
    }

    bool operator==(const BigInteger& rhs) const {
        return count_ == rhs.count_ && std::memcmp(digits_, rhs.digits_, count_ * sizeof(Type)) == 0;
    }

    bool operator==(const Type rhs) const {
        return count_ == 1 && digits_[0] == rhs;
    }

    BigInteger& MultiplyPow5(unsigned exp) {
        static const uint32_t kPow5[12] = {
            5,
            5 * 5,
            5 * 5 * 5,
            5 * 5 * 5 * 5,
            5 * 5 * 5 * 5 * 5,
            5 * 5 * 5 * 5 * 5 * 5,
            5 * 5 * 5 * 5 * 5 * 5 * 5,
            5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
            5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
            5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
            5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
            5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5
        };
        if (exp == 0) return *this;
        for (; exp >= 27; exp -= 27) *this *= RAPIDJSON_UINT64_C2(0X6765C793, 0XFA10079D); // 5^27
        for (; exp >= 13; exp -= 13) *this *= static_cast<uint32_t>(1220703125u); // 5^13
        if (exp > 0)                 *this *= kPow5[exp - 1];
        return *this;
    }

    // Compute absolute difference of this and rhs.
    // Assume this != rhs
    bool Difference(const BigInteger& rhs, BigInteger* out) const {
        int cmp = Compare(rhs);
        RAPIDJSON_ASSERT(cmp != 0);
        const BigInteger *a, *b;  // Makes a > b
        bool ret;
        if (cmp < 0) { a = &rhs; b = this; ret = true; }
        else         { a = this; b = &rhs; ret = false; }

        Type borrow = 0;
        for (size_t i = 0; i < a->count_; i++) {
            Type d = a->digits_[i] - borrow;
            if (i < b->count_)
                d -= b->digits_[i];
            borrow = (d > a->digits_[i]) ? 1 : 0;
            out->digits_[i] = d;
            if (d != 0)
                out->count_ = i + 1;
        }

        return ret;
    }

    int Compare(const BigInteger& rhs) const {
        if (count_ != rhs.count_)
            return count_ < rhs.count_ ? -1 : 1;

        for (size_t i = count_; i-- > 0;)
            if (digits_[i] != rhs.digits_[i])
                return digits_[i] < rhs.digits_[i] ? -1 : 1;

        return 0;
    }

    size_t GetCount() const { return count_; }
    Type GetDigit(size_t index) const { RAPIDJSON_ASSERT(index < count_); return digits_[index]; }
    bool IsZero() const { return count_ == 1 && digits_[0] == 0; }

private:
    template<typename Ch>
    void AppendDecimal64(const Ch* begin, const Ch* end) {
        uint64_t u = ParseUint64(begin, end);
        if (IsZero())
            *this = u;
        else {
            unsigned exp = static_cast<unsigned>(end - begin);
            (MultiplyPow5(exp) <<= exp) += u;   // *this = *this * 10^exp + u
        }
    }

    void PushBack(Type digit) {
        RAPIDJSON_ASSERT(count_ < kCapacity);
        digits_[count_++] = digit;
    }

    template<typename Ch>
    static uint64_t ParseUint64(const Ch* begin, const Ch* end) {
        uint64_t r = 0;
        for (const Ch* p = begin; p != end; ++p) {
            RAPIDJSON_ASSERT(*p >= Ch('0') && *p <= Ch('9'));
            r = r * 10u + static_cast<unsigned>(*p - Ch('0'));
        }
        return r;
    }

    // Assume a * b + k < 2^128
    static uint64_t MulAdd64(uint64_t a, uint64_t b, uint64_t k, uint64_t* outHigh) {
#if defined(_MSC_VER) && defined(_M_AMD64)
        uint64_t low = _umul128(a, b, outHigh) + k;
        if (low < k)
            (*outHigh)++;
        return low;
#elif defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__x86_64__)
        __extension__ typedef unsigned __int128 uint128;
        uint128 p = static_cast<uint128>(a) * static_cast<uint128>(b);
        p += k;
        *outHigh = static_cast<uint64_t>(p >> 64);
        return static_cast<uint64_t>(p);
#else
        const uint64_t a0 = a & 0xFFFFFFFF, a1 = a >> 32, b0 = b & 0xFFFFFFFF, b1 = b >> 32;
        uint64_t x0 = a0 * b0, x1 = a0 * b1, x2 = a1 * b0, x3 = a1 * b1;
        x1 += (x0 >> 32); // can't give carry
        x1 += x2;
        if (x1 < x2)
            x3 += (static_cast<uint64_t>(1) << 32);
        uint64_t lo = (x1 << 32) + (x0 & 0xFFFFFFFF);
        uint64_t hi = x3 + (x1 >> 32);

        lo += k;
        if (lo < k)
            hi++;
        *outHigh = hi;
        return lo;
#endif
    }

    static const size_t kBitCount = 3328;  // 64bit * 54 > 10^1000
    static const size_t kCapacity = kBitCount / sizeof(Type);
    static const size_t kTypeBit = sizeof(Type) * 8;

    Type digits_[kCapacity];
    size_t count_;
};

} // namespace internal
RAPIDJSON_NAMESPACE_END

#endif // RAPIDJSON_BIGINTEGER_H_

Coverage Report

Created: 2025-10-04 06:24

Line	Count	Source
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.
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(__INTEL_COMPILER) && defined(_M_AMD64)
21		#include <intrin.h> // for _umul128
22		#if !defined(_ARM64EC_)
23		#pragma intrinsic(_umul128)
24		#else
25		#pragma comment(lib,"softintrin")
26		#endif
27		#endif
28
29		RAPIDJSON_NAMESPACE_BEGIN
30		namespace internal {
31
32		class BigInteger {
33		public:
34		typedef uint64_t Type;
35
36	0	BigInteger(const BigInteger& rhs) : count_(rhs.count_) {
37	0	std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
38	0	}
39
40	0	explicit BigInteger(uint64_t u) : count_(1) {
41	0	digits_[0] = u;
42	0	}
43
44		template<typename Ch>
45	0	BigInteger(const Ch* decimals, size_t length) : count_(1) {
46	0	RAPIDJSON_ASSERT(length > 0);
47	0	digits_[0] = 0;
48	0	size_t i = 0;
49	0	const size_t kMaxDigitPerIteration = 19; // 2^64 = 18446744073709551616 > 10^19
50	0	while (length >= kMaxDigitPerIteration) {
51	0	AppendDecimal64(decimals + i, decimals + i + kMaxDigitPerIteration);
52	0	length -= kMaxDigitPerIteration;
53	0	i += kMaxDigitPerIteration;
54	0	}
55
56	0	if (length > 0)
57	0	AppendDecimal64(decimals + i, decimals + i + length);
58	0	}
59
60		BigInteger& operator=(const BigInteger &rhs)
61	0	{
62	0	if (this != &rhs) {
63	0	count_ = rhs.count_;
64	0	std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
65	0	}
66	0	return *this;
67	0	}
68
69	0	BigInteger& operator=(uint64_t u) {
70	0	digits_[0] = u;
71	0	count_ = 1;
72	0	return *this;
73	0	}
74
75	0	BigInteger& operator+=(uint64_t u) {
76	0	Type backup = digits_[0];
77	0	digits_[0] += u;
78	0	for (size_t i = 0; i < count_ - 1; i++) {
79	0	if (digits_[i] >= backup)
80	0	return *this; // no carry
81	0	backup = digits_[i + 1];
82	0	digits_[i + 1] += 1;
83	0	}
84
85		// Last carry
86	0	if (digits_[count_ - 1] < backup)
87	0	PushBack(1);
88
89	0	return *this;
90	0	}
91
92	0	BigInteger& operator*=(uint64_t u) {
93	0	if (u == 0) return *this = 0;
94	0	if (u == 1) return *this;
95	0	if (this == 1) return this = u;
96
97	0	uint64_t k = 0;
98	0	for (size_t i = 0; i < count_; i++) {
99	0	uint64_t hi;
100	0	digits_[i] = MulAdd64(digits_[i], u, k, &hi);
101	0	k = hi;
102	0	}
103
104	0	if (k > 0)
105	0	PushBack(k);
106
107	0	return *this;
108	0	}
109
110	0	BigInteger& operator*=(uint32_t u) {
111	0	if (u == 0) return *this = 0;
112	0	if (u == 1) return *this;
113	0	if (this == 1) return this = u;
114
115	0	uint64_t k = 0;
116	0	for (size_t i = 0; i < count_; i++) {
117	0	const uint64_t c = digits_[i] >> 32;
118	0	const uint64_t d = digits_[i] & 0xFFFFFFFF;
119	0	const uint64_t uc = u * c;
120	0	const uint64_t ud = u * d;
121	0	const uint64_t p0 = ud + k;
122	0	const uint64_t p1 = uc + (p0 >> 32);
123	0	digits_[i] = (p0 & 0xFFFFFFFF) \| (p1 << 32);
124	0	k = p1 >> 32;
125	0	}
126
127	0	if (k > 0)
128	0	PushBack(k);
129
130	0	return *this;
131	0	}
132
133	0	BigInteger& operator<<=(size_t shift) {
134	0	if (IsZero() \|\| shift == 0) return *this;
135
136	0	size_t offset = shift / kTypeBit;
137	0	size_t interShift = shift % kTypeBit;
138	0	RAPIDJSON_ASSERT(count_ + offset <= kCapacity);
139
140	0	if (interShift == 0) {
141	0	std::memmove(digits_ + offset, digits_, count_ * sizeof(Type));
142	0	count_ += offset;
143	0	}
144	0	else {
145	0	digits_[count_] = 0;
146	0	for (size_t i = count_; i > 0; i--)
147	0	digits_[i + offset] = (digits_[i] << interShift) \| (digits_[i - 1] >> (kTypeBit - interShift));
148	0	digits_[offset] = digits_[0] << interShift;
149	0	count_ += offset;
150	0	if (digits_[count_])
151	0	count_++;
152	0	}
153
154	0	std::memset(digits_, 0, offset * sizeof(Type));
155
156	0	return *this;
157	0	}
158
159	0	bool operator==(const BigInteger& rhs) const {
160	0	return count_ == rhs.count_ && std::memcmp(digits_, rhs.digits_, count_ * sizeof(Type)) == 0;
161	0	}
162
163	0	bool operator==(const Type rhs) const {
164	0	return count_ == 1 && digits_[0] == rhs;
165	0	}
166
167	0	BigInteger& MultiplyPow5(unsigned exp) {
168	0	static const uint32_t kPow5[12] = {
169	0	5,
170	0	5 * 5,
171	0	5 * 5 * 5,
172	0	5 * 5 * 5 * 5,
173	0	5 * 5 * 5 * 5 * 5,
174	0	5 * 5 * 5 * 5 * 5 * 5,
175	0	5 * 5 * 5 * 5 * 5 * 5 * 5,
176	0	5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
177	0	5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
178	0	5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
179	0	5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
180	0	5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5
181	0	};
182	0	if (exp == 0) return *this;
183	0	for (; exp >= 27; exp -= 27) this = RAPIDJSON_UINT64_C2(0X6765C793, 0XFA10079D); // 5^27
184	0	for (; exp >= 13; exp -= 13) this = static_cast<uint32_t>(1220703125u); // 5^13
185	0	if (exp > 0) this = kPow5[exp - 1];
186	0	return *this;
187	0	}
188
189		// Compute absolute difference of this and rhs.
190		// Assume this != rhs
191	0	bool Difference(const BigInteger& rhs, BigInteger* out) const {
192	0	int cmp = Compare(rhs);
193	0	RAPIDJSON_ASSERT(cmp != 0);
194	0	const BigInteger a, b; // Makes a > b
195	0	bool ret;
196	0	if (cmp < 0) { a = &rhs; b = this; ret = true; }
197	0	else { a = this; b = &rhs; ret = false; }
198
199	0	Type borrow = 0;
200	0	for (size_t i = 0; i < a->count_; i++) {
201	0	Type d = a->digits_[i] - borrow;
202	0	if (i < b->count_)
203	0	d -= b->digits_[i];
204	0	borrow = (d > a->digits_[i]) ? 1 : 0;
205	0	out->digits_[i] = d;
206	0	if (d != 0)
207	0	out->count_ = i + 1;
208	0	}
209
210	0	return ret;
211	0	}
212
213	0	int Compare(const BigInteger& rhs) const {
214	0	if (count_ != rhs.count_)
215	0	return count_ < rhs.count_ ? -1 : 1;
216
217	0	for (size_t i = count_; i-- > 0;)
218	0	if (digits_[i] != rhs.digits_[i])
219	0	return digits_[i] < rhs.digits_[i] ? -1 : 1;
220
221	0	return 0;
222	0	}
223
224	0	size_t GetCount() const { return count_; }
225	0	Type GetDigit(size_t index) const { RAPIDJSON_ASSERT(index < count_); return digits_[index]; }
226	0	bool IsZero() const { return count_ == 1 && digits_[0] == 0; }
227
228		private:
229		template<typename Ch>
230	0	void AppendDecimal64(const Ch* begin, const Ch* end) {
231	0	uint64_t u = ParseUint64(begin, end);
232	0	if (IsZero())
233	0	*this = u;
234	0	else {
235	0	unsigned exp = static_cast<unsigned>(end - begin);
236	0	(MultiplyPow5(exp) <<= exp) += u; // this = this * 10^exp + u
237	0	}
238	0	}
239
240	0	void PushBack(Type digit) {
241	0	RAPIDJSON_ASSERT(count_ < kCapacity);
242	0	digits_[count_++] = digit;
243	0	}
244
245		template<typename Ch>
246	0	static uint64_t ParseUint64(const Ch* begin, const Ch* end) {
247	0	uint64_t r = 0;
248	0	for (const Ch* p = begin; p != end; ++p) {
249	0	RAPIDJSON_ASSERT(p >= Ch('0') && p <= Ch('9'));
250	0	r = r * 10u + static_cast<unsigned>(*p - Ch('0'));
251	0	}
252	0	return r;
253	0	}
254
255		// Assume a * b + k < 2^128
256	0	static uint64_t MulAdd64(uint64_t a, uint64_t b, uint64_t k, uint64_t* outHigh) {
257		#if defined(_MSC_VER) && defined(_M_AMD64)
258		uint64_t low = _umul128(a, b, outHigh) + k;
259		if (low < k)
260		(*outHigh)++;
261		return low;
262		#elif defined(__GNUC__) && (__GNUC__ > 4 \|\| (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__x86_64__)
263		__extension__ typedef unsigned __int128 uint128;
264		uint128 p = static_cast<uint128>(a) * static_cast<uint128>(b);
265		p += k;
266		*outHigh = static_cast<uint64_t>(p >> 64);
267		return static_cast<uint64_t>(p);
268		#else
269	0	const uint64_t a0 = a & 0xFFFFFFFF, a1 = a >> 32, b0 = b & 0xFFFFFFFF, b1 = b >> 32;
270	0	uint64_t x0 = a0 * b0, x1 = a0 * b1, x2 = a1 * b0, x3 = a1 * b1;
271	0	x1 += (x0 >> 32); // can't give carry
272	0	x1 += x2;
273	0	if (x1 < x2)
274	0	x3 += (static_cast<uint64_t>(1) << 32);
275	0	uint64_t lo = (x1 << 32) + (x0 & 0xFFFFFFFF);
276	0	uint64_t hi = x3 + (x1 >> 32);
277
278	0	lo += k;
279	0	if (lo < k)
280	0	hi++;
281	0	*outHigh = hi;
282	0	return lo;
283	0	#endif
284	0	}
285
286		static const size_t kBitCount = 3328; // 64bit * 54 > 10^1000
287		static const size_t kCapacity = kBitCount / sizeof(Type);
288		static const size_t kTypeBit = sizeof(Type) * 8;
289
290		Type digits_[kCapacity];
291		size_t count_;
292		};
293
294		} // namespace internal
295		RAPIDJSON_NAMESPACE_END
296
297		#endif // RAPIDJSON_BIGINTEGER_H_