biginteger.h

00001 // Tencent is pleased to support the open source community by making RapidJSON available.
00002 // 
00003 // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
00004 //
00005 // Licensed under the MIT License (the "License"); you may not use this file except
00006 // in compliance with the License. You may obtain a copy of the License at
00007 //
00008 // http://opensource.org/licenses/MIT
00009 //
00010 // Unless required by applicable law or agreed to in writing, software distributed 
00011 // under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR 
00012 // CONDITIONS OF ANY KIND, either express or implied. See the License for the 
00013 // specific language governing permissions and limitations under the License.
00014 
00015 #ifndef RAPIDJSON_BIGINTEGER_H_
00016 #define RAPIDJSON_BIGINTEGER_H_
00017 
00018 #include "../rapidjson.h"
00019 
00020 #if defined(_MSC_VER) && defined(_M_AMD64)
00021 #include <intrin.h> // for _umul128
00022 #pragma intrinsic(_umul128)
00023 #endif
00024 
00025 RAPIDJSON_NAMESPACE_BEGIN
00026 namespace internal {
00027 
00028 class BigInteger {
00029 public:
00030     typedef uint64_t Type;
00031 
00032     BigInteger(const BigInteger& rhs) : count_(rhs.count_) {
00033         std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
00034     }
00035 
00036     explicit BigInteger(uint64_t u) : count_(1) {
00037         digits_[0] = u;
00038     }
00039 
00040     BigInteger(const char* decimals, size_t length) : count_(1) {
00041         RAPIDJSON_ASSERT(length > 0);
00042         digits_[0] = 0;
00043         size_t i = 0;
00044         const size_t kMaxDigitPerIteration = 19;  // 2^64 = 18446744073709551616 > 10^19
00045         while (length >= kMaxDigitPerIteration) {
00046             AppendDecimal64(decimals + i, decimals + i + kMaxDigitPerIteration);
00047             length -= kMaxDigitPerIteration;
00048             i += kMaxDigitPerIteration;
00049         }
00050 
00051         if (length > 0)
00052             AppendDecimal64(decimals + i, decimals + i + length);
00053     }
00054     
00055     BigInteger& operator=(const BigInteger &rhs)
00056     {
00057         if (this != &rhs) {
00058             count_ = rhs.count_;
00059             std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
00060         }
00061         return *this;
00062     }
00063     
00064     BigInteger& operator=(uint64_t u) {
00065         digits_[0] = u;            
00066         count_ = 1;
00067         return *this;
00068     }
00069 
00070     BigInteger& operator+=(uint64_t u) {
00071         Type backup = digits_[0];
00072         digits_[0] += u;
00073         for (size_t i = 0; i < count_ - 1; i++) {
00074             if (digits_[i] >= backup)
00075                 return *this; // no carry
00076             backup = digits_[i + 1];
00077             digits_[i + 1] += 1;
00078         }
00079 
00080         // Last carry
00081         if (digits_[count_ - 1] < backup)
00082             PushBack(1);
00083 
00084         return *this;
00085     }
00086 
00087     BigInteger& operator*=(uint64_t u) {
00088         if (u == 0) return *this = 0;
00089         if (u == 1) return *this;
00090         if (*this == 1) return *this = u;
00091 
00092         uint64_t k = 0;
00093         for (size_t i = 0; i < count_; i++) {
00094             uint64_t hi;
00095             digits_[i] = MulAdd64(digits_[i], u, k, &hi);
00096             k = hi;
00097         }
00098         
00099         if (k > 0)
00100             PushBack(k);
00101 
00102         return *this;
00103     }
00104 
00105     BigInteger& operator*=(uint32_t u) {
00106         if (u == 0) return *this = 0;
00107         if (u == 1) return *this;
00108         if (*this == 1) return *this = u;
00109 
00110         uint64_t k = 0;
00111         for (size_t i = 0; i < count_; i++) {
00112             const uint64_t c = digits_[i] >> 32;
00113             const uint64_t d = digits_[i] & 0xFFFFFFFF;
00114             const uint64_t uc = u * c;
00115             const uint64_t ud = u * d;
00116             const uint64_t p0 = ud + k;
00117             const uint64_t p1 = uc + (p0 >> 32);
00118             digits_[i] = (p0 & 0xFFFFFFFF) | (p1 << 32);
00119             k = p1 >> 32;
00120         }
00121         
00122         if (k > 0)
00123             PushBack(k);
00124 
00125         return *this;
00126     }
00127 
00128     BigInteger& operator<<=(size_t shift) {
00129         if (IsZero() || shift == 0) return *this;
00130 
00131         size_t offset = shift / kTypeBit;
00132         size_t interShift = shift % kTypeBit;
00133         RAPIDJSON_ASSERT(count_ + offset <= kCapacity);
00134 
00135         if (interShift == 0) {
00136             std::memmove(&digits_[count_ - 1 + offset], &digits_[count_ - 1], count_ * sizeof(Type));
00137             count_ += offset;
00138         }
00139         else {
00140             digits_[count_] = 0;
00141             for (size_t i = count_; i > 0; i--)
00142                 digits_[i + offset] = (digits_[i] << interShift) | (digits_[i - 1] >> (kTypeBit - interShift));
00143             digits_[offset] = digits_[0] << interShift;
00144             count_ += offset;
00145             if (digits_[count_])
00146                 count_++;
00147         }
00148 
00149         std::memset(digits_, 0, offset * sizeof(Type));
00150 
00151         return *this;
00152     }
00153 
00154     bool operator==(const BigInteger& rhs) const {
00155         return count_ == rhs.count_ && std::memcmp(digits_, rhs.digits_, count_ * sizeof(Type)) == 0;
00156     }
00157 
00158     bool operator==(const Type rhs) const {
00159         return count_ == 1 && digits_[0] == rhs;
00160     }
00161 
00162     BigInteger& MultiplyPow5(unsigned exp) {
00163         static const uint32_t kPow5[12] = {
00164             5,
00165             5 * 5,
00166             5 * 5 * 5,
00167             5 * 5 * 5 * 5,
00168             5 * 5 * 5 * 5 * 5,
00169             5 * 5 * 5 * 5 * 5 * 5,
00170             5 * 5 * 5 * 5 * 5 * 5 * 5,
00171             5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
00172             5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
00173             5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
00174             5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5,
00175             5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5
00176         };
00177         if (exp == 0) return *this;
00178         for (; exp >= 27; exp -= 27) *this *= RAPIDJSON_UINT64_C2(0X6765C793, 0XFA10079D); // 5^27
00179         for (; exp >= 13; exp -= 13) *this *= static_cast<uint32_t>(1220703125u); // 5^13
00180         if (exp > 0)                 *this *= kPow5[exp - 1];
00181         return *this;
00182     }
00183 
00184     // Compute absolute difference of this and rhs.
00185     // Assume this != rhs
00186     bool Difference(const BigInteger& rhs, BigInteger* out) const {
00187         int cmp = Compare(rhs);
00188         RAPIDJSON_ASSERT(cmp != 0);
00189         const BigInteger *a, *b;  // Makes a > b
00190         bool ret;
00191         if (cmp < 0) { a = &rhs; b = this; ret = true; }
00192         else         { a = this; b = &rhs; ret = false; }
00193 
00194         Type borrow = 0;
00195         for (size_t i = 0; i < a->count_; i++) {
00196             Type d = a->digits_[i] - borrow;
00197             if (i < b->count_)
00198                 d -= b->digits_[i];
00199             borrow = (d > a->digits_[i]) ? 1 : 0;
00200             out->digits_[i] = d;
00201             if (d != 0)
00202                 out->count_ = i + 1;
00203         }
00204 
00205         return ret;
00206     }
00207 
00208     int Compare(const BigInteger& rhs) const {
00209         if (count_ != rhs.count_)
00210             return count_ < rhs.count_ ? -1 : 1;
00211 
00212         for (size_t i = count_; i-- > 0;)
00213             if (digits_[i] != rhs.digits_[i])
00214                 return digits_[i] < rhs.digits_[i] ? -1 : 1;
00215 
00216         return 0;
00217     }
00218 
00219     size_t GetCount() const { return count_; }
00220     Type GetDigit(size_t index) const { RAPIDJSON_ASSERT(index < count_); return digits_[index]; }
00221     bool IsZero() const { return count_ == 1 && digits_[0] == 0; }
00222 
00223 private:
00224     void AppendDecimal64(const char* begin, const char* end) {
00225         uint64_t u = ParseUint64(begin, end);
00226         if (IsZero())
00227             *this = u;
00228         else {
00229             unsigned exp = static_cast<unsigned>(end - begin);
00230             (MultiplyPow5(exp) <<= exp) += u;   // *this = *this * 10^exp + u
00231         }
00232     }
00233 
00234     void PushBack(Type digit) {
00235         RAPIDJSON_ASSERT(count_ < kCapacity);
00236         digits_[count_++] = digit;
00237     }
00238 
00239     static uint64_t ParseUint64(const char* begin, const char* end) {
00240         uint64_t r = 0;
00241         for (const char* p = begin; p != end; ++p) {
00242             RAPIDJSON_ASSERT(*p >= '0' && *p <= '9');
00243             r = r * 10u + static_cast<unsigned>(*p - '0');
00244         }
00245         return r;
00246     }
00247 
00248     // Assume a * b + k < 2^128
00249     static uint64_t MulAdd64(uint64_t a, uint64_t b, uint64_t k, uint64_t* outHigh) {
00250 #if defined(_MSC_VER) && defined(_M_AMD64)
00251         uint64_t low = _umul128(a, b, outHigh) + k;
00252         if (low < k)
00253             (*outHigh)++;
00254         return low;
00255 #elif (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__x86_64__)
00256         __extension__ typedef unsigned __int128 uint128;
00257         uint128 p = static_cast<uint128>(a) * static_cast<uint128>(b);
00258         p += k;
00259         *outHigh = static_cast<uint64_t>(p >> 64);
00260         return static_cast<uint64_t>(p);
00261 #else
00262         const uint64_t a0 = a & 0xFFFFFFFF, a1 = a >> 32, b0 = b & 0xFFFFFFFF, b1 = b >> 32;
00263         uint64_t x0 = a0 * b0, x1 = a0 * b1, x2 = a1 * b0, x3 = a1 * b1;
00264         x1 += (x0 >> 32); // can't give carry
00265         x1 += x2;
00266         if (x1 < x2)
00267             x3 += (static_cast<uint64_t>(1) << 32);
00268         uint64_t lo = (x1 << 32) + (x0 & 0xFFFFFFFF);
00269         uint64_t hi = x3 + (x1 >> 32);
00270 
00271         lo += k;
00272         if (lo < k)
00273             hi++;
00274         *outHigh = hi;
00275         return lo;
00276 #endif
00277     }
00278 
00279     static const size_t kBitCount = 3328;  // 64bit * 54 > 10^1000
00280     static const size_t kCapacity = kBitCount / sizeof(Type);
00281     static const size_t kTypeBit = sizeof(Type) * 8;
00282 
00283     Type digits_[kCapacity];
00284     size_t count_;
00285 };
00286 
00287 } // namespace internal
00288 RAPIDJSON_NAMESPACE_END
00289 
00290 #endif // RAPIDJSON_BIGINTEGER_H_