rapidjson/internal/biginteger.h

0001 // Tencent is pleased to support the open source community by making RapidJSON available.
0002 //
0003 // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip.
0004 //
0005 // Licensed under the MIT License (the "License"); you may not use this file except
0006 // in compliance with the License. You may obtain a copy of the License at
0007 //
0008 // http://opensource.org/licenses/MIT
0009 //
0010 // Unless required by applicable law or agreed to in writing, software distributed
0011 // under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
0012 // CONDITIONS OF ANY KIND, either express or implied. See the License for the
0013 // specific language governing permissions and limitations under the License.
0014
0015 #ifndef RAPIDJSON_BIGINTEGER_H_
0016 #define RAPIDJSON_BIGINTEGER_H_
0017
0018 #include "../rapidjson.h"
0019
0020 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) && defined(_M_AMD64)
0021 #include <intrin.h> // for _umul128
0022 #if !defined(_ARM64EC_)
0023 #pragma intrinsic(_umul128)
0024 #else
0025 #pragma comment(lib,"softintrin")
0026 #endif
0027 #endif
0028
0029 RAPIDJSON_NAMESPACE_BEGIN
0030 namespace internal {
0031
0032 class BigInteger {
0033 public:
0034     typedef uint64_t Type;
0035
0036     BigInteger(const BigInteger& rhs) : count_(rhs.count_) {
0037         std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
0038     }
0039
0040     explicit BigInteger(uint64_t u) : count_(1) {
0041         digits_[0] = u;
0042     }
0043
0044     template<typename Ch>
0045     BigInteger(const Ch* decimals, size_t length) : count_(1) {
0046         RAPIDJSON_ASSERT(length > 0);
0047         digits_[0] = 0;
0048         size_t i = 0;
0049         const size_t kMaxDigitPerIteration = 19;  // 2^64 = 18446744073709551616 > 10^19
0050         while (length >= kMaxDigitPerIteration) {
0051             AppendDecimal64(decimals + i, decimals + i + kMaxDigitPerIteration);
0052             length -= kMaxDigitPerIteration;
0053             i += kMaxDigitPerIteration;
0054         }
0055
0056         if (length > 0)
0057             AppendDecimal64(decimals + i, decimals + i + length);
0058     }
0059
0060     BigInteger& operator=(const BigInteger &rhs)
0061     {
0062         if (this != &rhs) {
0063             count_ = rhs.count_;
0064             std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
0065         }
0066         return *this;
0067     }
0068
0069     BigInteger& operator=(uint64_t u) {
0070         digits_[0] = u;
0071         count_ = 1;
0072         return *this;
0073     }
0074
0075     BigInteger& operator+=(uint64_t u) {
0076         Type backup = digits_[0];
0077         digits_[0] += u;
0078         for (size_t i = 0; i < count_ - 1; i++) {
0079             if (digits_[i] >= backup)
0080                 return *this; // no carry
0081             backup = digits_[i + 1];
0082             digits_[i + 1] += 1;
0083         }
0084
0085         // Last carry
0086         if (digits_[count_ - 1] < backup)
0087             PushBack(1);
0088
0089         return *this;
0090     }
0091
0092     BigInteger& operator*=(uint64_t u) {
0093         if (u == 0) return *this = 0;
0094         if (u == 1) return *this;
0095         if (*this == 1) return *this = u;
0096
0097         uint64_t k = 0;
0098         for (size_t i = 0; i < count_; i++) {
0099             uint64_t hi;
0100             digits_[i] = MulAdd64(digits_[i], u, k, &hi);
0101             k = hi;
0102         }
0103
0104         if (k > 0)
0105             PushBack(k);
0106
0107         return *this;
0108     }
0109
0110     BigInteger& operator*=(uint32_t u) {
0111         if (u == 0) return *this = 0;
0112         if (u == 1) return *this;
0113         if (*this == 1) return *this = u;
0114
0115         uint64_t k = 0;
0116         for (size_t i = 0; i < count_; i++) {
0117             const uint64_t c = digits_[i] >> 32;
0118             const uint64_t d = digits_[i] & 0xFFFFFFFF;
0119             const uint64_t uc = u * c;
0120             const uint64_t ud = u * d;
0121             const uint64_t p0 = ud + k;
0122             const uint64_t p1 = uc + (p0 >> 32);
0123             digits_[i] = (p0 & 0xFFFFFFFF) | (p1 << 32);
0124             k = p1 >> 32;
0125         }
0126
0127         if (k > 0)
0128             PushBack(k);
0129
0130         return *this;
0131     }
0132
0133     BigInteger& operator<<=(size_t shift) {
0134         if (IsZero() || shift == 0) return *this;
0135
0136         size_t offset = shift / kTypeBit;
0137         size_t interShift = shift % kTypeBit;
0138         RAPIDJSON_ASSERT(count_ + offset <= kCapacity);
0139
0140         if (interShift == 0) {
0141             std::memmove(digits_ + offset, digits_, count_ * sizeof(Type));
0142             count_ += offset;
0143         }
0144         else {
0145             digits_[count_] = 0;
0146             for (size_t i = count_; i > 0; i--)
0147                 digits_[i + offset] = (digits_[i] << interShift) | (digits_[i - 1] >> (kTypeBit - interShift));
0148             digits_[offset] = digits_[0] << interShift;
0149             count_ += offset;
0150             if (digits_[count_])
0151                 count_++;
0152         }
0153
0154         std::memset(digits_, 0, offset * sizeof(Type));
0155
0156         return *this;
0157     }
0158
0159     bool operator==(const BigInteger& rhs) const {
0160         return count_ == rhs.count_ && std::memcmp(digits_, rhs.digits_, count_ * sizeof(Type)) == 0;
0161     }
0162
0163     bool operator==(const Type rhs) const {
0164         return count_ == 1 && digits_[0] == rhs;
0165     }
0166
0167     BigInteger& MultiplyPow5(unsigned exp) {
0168         static const uint32_t kPow5[12] = {
0169             5,
0170             5 * 5,
0171             5 * 5 * 5,
0172             5 * 5 * 5 * 5,
0173             5 * 5 * 5 * 5 * 5,
0174             5 * 5 * 5 * 5 * 5 * 5,
0175             5 * 5 * 5 * 5 * 5 * 5 * 5,
0176             5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
0177             5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
0178             5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
0179             5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
0180             5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5
0181         };
0182         if (exp == 0) return *this;
0183         for (; exp >= 27; exp -= 27) *this *= RAPIDJSON_UINT64_C2(0X6765C793, 0XFA10079D); // 5^27
0184         for (; exp >= 13; exp -= 13) *this *= static_cast<uint32_t>(1220703125u); // 5^13
0185         if (exp > 0)                 *this *= kPow5[exp - 1];
0186         return *this;
0187     }
0188
0189     // Compute absolute difference of this and rhs.
0190     // Assume this != rhs
0191     bool Difference(const BigInteger& rhs, BigInteger* out) const {
0192         int cmp = Compare(rhs);
0193         RAPIDJSON_ASSERT(cmp != 0);
0194         const BigInteger *a, *b;  // Makes a > b
0195         bool ret;
0196         if (cmp < 0) { a = &rhs; b = this; ret = true; }
0197         else         { a = this; b = &rhs; ret = false; }
0198
0199         Type borrow = 0;
0200         for (size_t i = 0; i < a->count_; i++) {
0201             Type d = a->digits_[i] - borrow;
0202             if (i < b->count_)
0203                 d -= b->digits_[i];
0204             borrow = (d > a->digits_[i]) ? 1 : 0;
0205             out->digits_[i] = d;
0206             if (d != 0)
0207                 out->count_ = i + 1;
0208         }
0209
0210         return ret;
0211     }
0212
0213     int Compare(const BigInteger& rhs) const {
0214         if (count_ != rhs.count_)
0215             return count_ < rhs.count_ ? -1 : 1;
0216
0217         for (size_t i = count_; i-- > 0;)
0218             if (digits_[i] != rhs.digits_[i])
0219                 return digits_[i] < rhs.digits_[i] ? -1 : 1;
0220
0221         return 0;
0222     }
0223
0224     size_t GetCount() const { return count_; }
0225     Type GetDigit(size_t index) const { RAPIDJSON_ASSERT(index < count_); return digits_[index]; }
0226     bool IsZero() const { return count_ == 1 && digits_[0] == 0; }
0227
0228 private:
0229     template<typename Ch>
0230     void AppendDecimal64(const Ch* begin, const Ch* end) {
0231         uint64_t u = ParseUint64(begin, end);
0232         if (IsZero())
0233             *this = u;
0234         else {
0235             unsigned exp = static_cast<unsigned>(end - begin);
0236             (MultiplyPow5(exp) <<= exp) += u;   // *this = *this * 10^exp + u
0237         }
0238     }
0239
0240     void PushBack(Type digit) {
0241         RAPIDJSON_ASSERT(count_ < kCapacity);
0242         digits_[count_++] = digit;
0243     }
0244
0245     template<typename Ch>
0246     static uint64_t ParseUint64(const Ch* begin, const Ch* end) {
0247         uint64_t r = 0;
0248         for (const Ch* p = begin; p != end; ++p) {
0249             RAPIDJSON_ASSERT(*p >= Ch('0') && *p <= Ch('9'));
0250             r = r * 10u + static_cast<unsigned>(*p - Ch('0'));
0251         }
0252         return r;
0253     }
0254
0255     // Assume a * b + k < 2^128
0256     static uint64_t MulAdd64(uint64_t a, uint64_t b, uint64_t k, uint64_t* outHigh) {
0257 #if defined(_MSC_VER) && defined(_M_AMD64)
0258         uint64_t low = _umul128(a, b, outHigh) + k;
0259         if (low < k)
0260             (*outHigh)++;
0261         return low;
0262 #elif defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__x86_64__)
0263         __extension__ typedef unsigned __int128 uint128;
0264         uint128 p = static_cast<uint128>(a) * static_cast<uint128>(b);
0265         p += k;
0266         *outHigh = static_cast<uint64_t>(p >> 64);
0267         return static_cast<uint64_t>(p);
0268 #else
0269         const uint64_t a0 = a & 0xFFFFFFFF, a1 = a >> 32, b0 = b & 0xFFFFFFFF, b1 = b >> 32;
0270         uint64_t x0 = a0 * b0, x1 = a0 * b1, x2 = a1 * b0, x3 = a1 * b1;
0271         x1 += (x0 >> 32); // can't give carry
0272         x1 += x2;
0273         if (x1 < x2)
0274             x3 += (static_cast<uint64_t>(1) << 32);
0275         uint64_t lo = (x1 << 32) + (x0 & 0xFFFFFFFF);
0276         uint64_t hi = x3 + (x1 >> 32);
0277
0278         lo += k;
0279         if (lo < k)
0280             hi++;
0281         *outHigh = hi;
0282         return lo;
0283 #endif
0284     }
0285
0286     static const size_t kBitCount = 3328;  // 64bit * 54 > 10^1000
0287     static const size_t kCapacity = kBitCount / sizeof(Type);
0288     static const size_t kTypeBit = sizeof(Type) * 8;
0289
0290     Type digits_[kCapacity];
0291     size_t count_;
0292 };
0293
0294 } // namespace internal
0295 RAPIDJSON_NAMESPACE_END
0296
0297 #endif // RAPIDJSON_BIGINTEGER_H_