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. All rights reserved.
  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(_M_AMD64)
 21#include <intrin.h> // for _umul128
 22#pragma intrinsic(_umul128)
 23#endif
 24
 25RAPIDJSON_NAMESPACE_BEGIN
 26namespace internal {
 27
 28class BigInteger {
 29public:
 30    typedef uint64_t Type;
 31
 32    BigInteger(const BigInteger& rhs) : count_(rhs.count_) {
 33        std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
 34    }
 35
 36    explicit BigInteger(uint64_t u) : count_(1) {
 37        digits_[0] = u;
 38    }
 39
 40    BigInteger(const char* decimals, size_t length) : count_(1) {
 41        RAPIDJSON_ASSERT(length > 0);
 42        digits_[0] = 0;
 43        size_t i = 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;
 49        }
 50
 51        if (length > 0)
 52            AppendDecimal64(decimals + i, decimals + i + length);
 53    }
 54    
 55    BigInteger& operator=(const BigInteger &rhs)
 56    {
 57        if (this != &rhs) {
 58            count_ = rhs.count_;
 59            std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
 60        }
 61        return *this;
 62    }
 63    
 64    BigInteger& operator=(uint64_t u) {
 65        digits_[0] = u;            
 66        count_ = 1;
 67        return *this;
 68    }
 69
 70    BigInteger& operator+=(uint64_t u) {
 71        Type backup = digits_[0];
 72        digits_[0] += u;
 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];
 77            digits_[i + 1] += 1;
 78        }
 79
 80        // Last carry
 81        if (digits_[count_ - 1] < backup)
 82            PushBack(1);
 83
 84        return *this;
 85    }
 86
 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;
 91
 92        uint64_t k = 0;
 93        for (size_t i = 0; i < count_; i++) {
 94            uint64_t hi;
 95            digits_[i] = MulAdd64(digits_[i], u, k, &hi);
 96            k = hi;
 97        }
 98        
 99        if (k > 0)
100            PushBack(k);
101
102        return *this;
103    }
104
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;
109
110        uint64_t k = 0;
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);
119            k = p1 >> 32;
120        }
121        
122        if (k > 0)
123            PushBack(k);
124
125        return *this;
126    }
127
128    BigInteger& operator<<=(size_t shift) {
129        if (IsZero() || shift == 0) return *this;
130
131        size_t offset = shift / kTypeBit;
132        size_t interShift = shift % kTypeBit;
133        RAPIDJSON_ASSERT(count_ + offset <= kCapacity);
134
135        if (interShift == 0) {
136            std::memmove(&digits_[count_ - 1 + offset], &digits_[count_ - 1], count_ * sizeof(Type));
137            count_ += offset;
138        }
139        else {
140            digits_[count_] = 0;
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;
144            count_ += offset;
145            if (digits_[count_])
146                count_++;
147        }
148
149        std::memset(digits_, 0, offset * sizeof(Type));
150
151        return *this;
152    }
153
154    bool operator==(const BigInteger& rhs) const {
155        return count_ == rhs.count_ && std::memcmp(digits_, rhs.digits_, count_ * sizeof(Type)) == 0;
156    }
157
158    bool operator==(const Type rhs) const {
159        return count_ == 1 && digits_[0] == rhs;
160    }
161
162    BigInteger& MultiplyPow5(unsigned exp) {
163        static const uint32_t kPow5[12] = {
164            5,
165            5 * 5,
166            5 * 5 * 5,
167            5 * 5 * 5 * 5,
168            5 * 5 * 5 * 5 * 5,
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
176        };
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];
181        return *this;
182    }
183
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
190        bool ret;
191        if (cmp < 0) { a = &rhs; b = this; ret = true; }
192        else         { a = this; b = &rhs; ret = false; }
193
194        Type borrow = 0;
195        for (size_t i = 0; i < a->count_; i++) {
196            Type d = a->digits_[i] - borrow;
197            if (i < b->count_)
198                d -= b->digits_[i];
199            borrow = (d > a->digits_[i]) ? 1 : 0;
200            out->digits_[i] = d;
201            if (d != 0)
202                out->count_ = i + 1;
203        }
204
205        return ret;
206    }
207
208    int Compare(const BigInteger& rhs) const {
209        if (count_ != rhs.count_)
210            return count_ < rhs.count_ ? -1 : 1;
211
212        for (size_t i = count_; i-- > 0;)
213            if (digits_[i] != rhs.digits_[i])
214                return digits_[i] < rhs.digits_[i] ? -1 : 1;
215
216        return 0;
217    }
218
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; }
222
223private:
224    void AppendDecimal64(const char* begin, const char* end) {
225        uint64_t u = ParseUint64(begin, end);
226        if (IsZero())
227            *this = u;
228        else {
229            unsigned exp = static_cast<unsigned>(end - begin);
230            (MultiplyPow5(exp) <<= exp) += u;   // *this = *this * 10^exp + u
231        }
232    }
233
234    void PushBack(Type digit) {
235        RAPIDJSON_ASSERT(count_ < kCapacity);
236        digits_[count_++] = digit;
237    }
238
239    static uint64_t ParseUint64(const char* begin, const char* end) {
240        uint64_t r = 0;
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');
244        }
245        return r;
246    }
247
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;
252        if (low < k)
253            (*outHigh)++;
254        return low;
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);
258        p += k;
259        *outHigh = static_cast<uint64_t>(p >> 64);
260        return static_cast<uint64_t>(p);
261#else
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
265        x1 += x2;
266        if (x1 < x2)
267            x3 += (static_cast<uint64_t>(1) << 32);
268        uint64_t lo = (x1 << 32) + (x0 & 0xFFFFFFFF);
269        uint64_t hi = x3 + (x1 >> 32);
270
271        lo += k;
272        if (lo < k)
273            hi++;
274        *outHigh = hi;
275        return lo;
276#endif
277    }
278
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;
282
283    Type digits_[kCapacity];
284    size_t count_;
285};
286
287} // namespace internal
288RAPIDJSON_NAMESPACE_END
289
290#endif // RAPIDJSON_BIGINTEGER_H_