biginteger.h
Engine/source/persistence/rapidjson/internal/biginteger.h
Classes:
class
Namespaces:
namespace
Detailed Description
1 2// Tencent is pleased to support the open source community by making RapidJSON available. 3// 4// Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved. 5// 6// Licensed under the MIT License (the "License"); you may not use this file except 7// in compliance with the License. You may obtain a copy of the License at 8// 9// http://opensource.org/licenses/MIT 10// 11// Unless required by applicable law or agreed to in writing, software distributed 12// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR 13// CONDITIONS OF ANY KIND, either express or implied. See the License for the 14// specific language governing permissions and limitations under the License. 15 16#ifndef RAPIDJSON_BIGINTEGER_H_ 17#define RAPIDJSON_BIGINTEGER_H_ 18 19#include "../rapidjson.h" 20 21#if defined(_MSC_VER) && !__INTEL_COMPILER && defined(_M_AMD64) 22#include <intrin.h> // for _umul128 23#pragma intrinsic(_umul128) 24#endif 25 26RAPIDJSON_NAMESPACE_BEGIN 27namespace internal { 28 29class BigInteger { 30public: 31 typedef uint64_t Type; 32 33 BigInteger(const BigInteger& rhs) : count_(rhs.count_) { 34 std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type)); 35 } 36 37 explicit BigInteger(uint64_t u) : count_(1) { 38 digits_[0] = u; 39 } 40 41 BigInteger(const char* decimals, size_t length) : count_(1) { 42 RAPIDJSON_ASSERT(length > 0); 43 digits_[0] = 0; 44 size_t i = 0; 45 const size_t kMaxDigitPerIteration = 19; // 2^64 = 18446744073709551616 > 10^19 46 while (length >= kMaxDigitPerIteration) { 47 AppendDecimal64(decimals + i, decimals + i + kMaxDigitPerIteration); 48 length -= kMaxDigitPerIteration; 49 i += kMaxDigitPerIteration; 50 } 51 52 if (length > 0) 53 AppendDecimal64(decimals + i, decimals + i + length); 54 } 55 56 BigInteger& operator=(const BigInteger &rhs) 57 { 58 if (this != &rhs) { 59 count_ = rhs.count_; 60 std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type)); 61 } 62 return *this; 63 } 64 65 BigInteger& operator=(uint64_t u) { 66 digits_[0] = u; 67 count_ = 1; 68 return *this; 69 } 70 71 BigInteger& operator+=(uint64_t u) { 72 Type backup = digits_[0]; 73 digits_[0] += u; 74 for (size_t i = 0; i < count_ - 1; i++) { 75 if (digits_[i] >= backup) 76 return *this; // no carry 77 backup = digits_[i + 1]; 78 digits_[i + 1] += 1; 79 } 80 81 // Last carry 82 if (digits_[count_ - 1] < backup) 83 PushBack(1); 84 85 return *this; 86 } 87 88 BigInteger& operator*=(uint64_t u) { 89 if (u == 0) return *this = 0; 90 if (u == 1) return *this; 91 if (*this == 1) return *this = u; 92 93 uint64_t k = 0; 94 for (size_t i = 0; i < count_; i++) { 95 uint64_t hi; 96 digits_[i] = MulAdd64(digits_[i], u, k, &hi); 97 k = hi; 98 } 99 100 if (k > 0) 101 PushBack(k); 102 103 return *this; 104 } 105 106 BigInteger& operator*=(uint32_t u) { 107 if (u == 0) return *this = 0; 108 if (u == 1) return *this; 109 if (*this == 1) return *this = u; 110 111 uint64_t k = 0; 112 for (size_t i = 0; i < count_; i++) { 113 const uint64_t c = digits_[i] >> 32; 114 const uint64_t d = digits_[i] & 0xFFFFFFFF; 115 const uint64_t uc = u * c; 116 const uint64_t ud = u * d; 117 const uint64_t p0 = ud + k; 118 const uint64_t p1 = uc + (p0 >> 32); 119 digits_[i] = (p0 & 0xFFFFFFFF) | (p1 << 32); 120 k = p1 >> 32; 121 } 122 123 if (k > 0) 124 PushBack(k); 125 126 return *this; 127 } 128 129 BigInteger& operator<<=(size_t shift) { 130 if (IsZero() || shift == 0) return *this; 131 132 size_t offset = shift / kTypeBit; 133 size_t interShift = shift % kTypeBit; 134 RAPIDJSON_ASSERT(count_ + offset <= kCapacity); 135 136 if (interShift == 0) { 137 std::memmove(digits_ + offset, digits_, count_ * sizeof(Type)); 138 count_ += offset; 139 } 140 else { 141 digits_[count_] = 0; 142 for (size_t i = count_; i > 0; i--) 143 digits_[i + offset] = (digits_[i] << interShift) | (digits_[i - 1] >> (kTypeBit - interShift)); 144 digits_[offset] = digits_[0] << interShift; 145 count_ += offset; 146 if (digits_[count_]) 147 count_++; 148 } 149 150 std::memset(digits_, 0, offset * sizeof(Type)); 151 152 return *this; 153 } 154 155 bool operator==(const BigInteger& rhs) const { 156 return count_ == rhs.count_ && std::memcmp(digits_, rhs.digits_, count_ * sizeof(Type)) == 0; 157 } 158 159 bool operator==(const Type rhs) const { 160 return count_ == 1 && digits_[0] == rhs; 161 } 162 163 BigInteger& MultiplyPow5(unsigned exp) { 164 static const uint32_t kPow5[12] = { 165 5, 166 5 * 5, 167 5 * 5 * 5, 168 5 * 5 * 5 * 5, 169 5 * 5 * 5 * 5 * 5, 170 5 * 5 * 5 * 5 * 5 * 5, 171 5 * 5 * 5 * 5 * 5 * 5 * 5, 172 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, 173 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, 174 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, 175 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5, 176 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 177 }; 178 if (exp == 0) return *this; 179 for (; exp >= 27; exp -= 27) *this *= RAPIDJSON_UINT64_C2(0X6765C793, 0XFA10079D); // 5^27 180 for (; exp >= 13; exp -= 13) *this *= static_cast<uint32_t>(1220703125u); // 5^13 181 if (exp > 0) *this *= kPow5[exp - 1]; 182 return *this; 183 } 184 185 // Compute absolute difference of this and rhs. 186 // Assume this != rhs 187 bool Difference(const BigInteger& rhs, BigInteger* out) const { 188 int cmp = Compare(rhs); 189 RAPIDJSON_ASSERT(cmp != 0); 190 const BigInteger *a, *b; // Makes a > b 191 bool ret; 192 if (cmp < 0) { a = &rhs; b = this; ret = true; } 193 else { a = this; b = &rhs; ret = false; } 194 195 Type borrow = 0; 196 for (size_t i = 0; i < a->count_; i++) { 197 Type d = a->digits_[i] - borrow; 198 if (i < b->count_) 199 d -= b->digits_[i]; 200 borrow = (d > a->digits_[i]) ? 1 : 0; 201 out->digits_[i] = d; 202 if (d != 0) 203 out->count_ = i + 1; 204 } 205 206 return ret; 207 } 208 209 int Compare(const BigInteger& rhs) const { 210 if (count_ != rhs.count_) 211 return count_ < rhs.count_ ? -1 : 1; 212 213 for (size_t i = count_; i-- > 0;) 214 if (digits_[i] != rhs.digits_[i]) 215 return digits_[i] < rhs.digits_[i] ? -1 : 1; 216 217 return 0; 218 } 219 220 size_t GetCount() const { return count_; } 221 Type GetDigit(size_t index) const { RAPIDJSON_ASSERT(index < count_); return digits_[index]; } 222 bool IsZero() const { return count_ == 1 && digits_[0] == 0; } 223 224private: 225 void AppendDecimal64(const char* begin, const char* end) { 226 uint64_t u = ParseUint64(begin, end); 227 if (IsZero()) 228 *this = u; 229 else { 230 unsigned exp = static_cast<unsigned>(end - begin); 231 (MultiplyPow5(exp) <<= exp) += u; // *this = *this * 10^exp + u 232 } 233 } 234 235 void PushBack(Type digit) { 236 RAPIDJSON_ASSERT(count_ < kCapacity); 237 digits_[count_++] = digit; 238 } 239 240 static uint64_t ParseUint64(const char* begin, const char* end) { 241 uint64_t r = 0; 242 for (const char* p = begin; p != end; ++p) { 243 RAPIDJSON_ASSERT(*p >= '0' && *p <= '9'); 244 r = r * 10u + static_cast<unsigned>(*p - '0'); 245 } 246 return r; 247 } 248 249 // Assume a * b + k < 2^128 250 static uint64_t MulAdd64(uint64_t a, uint64_t b, uint64_t k, uint64_t* outHigh) { 251#if defined(_MSC_VER) && defined(_M_AMD64) 252 uint64_t low = _umul128(a, b, outHigh) + k; 253 if (low < k) 254 (*outHigh)++; 255 return low; 256#elif (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) && defined(__x86_64__) 257 __extension__ typedef unsigned __int128 uint128; 258 uint128 p = static_cast<uint128>(a) * static_cast<uint128>(b); 259 p += k; 260 *outHigh = static_cast<uint64_t>(p >> 64); 261 return static_cast<uint64_t>(p); 262#else 263 const uint64_t a0 = a & 0xFFFFFFFF, a1 = a >> 32, b0 = b & 0xFFFFFFFF, b1 = b >> 32; 264 uint64_t x0 = a0 * b0, x1 = a0 * b1, x2 = a1 * b0, x3 = a1 * b1; 265 x1 += (x0 >> 32); // can't give carry 266 x1 += x2; 267 if (x1 < x2) 268 x3 += (static_cast<uint64_t>(1) << 32); 269 uint64_t lo = (x1 << 32) + (x0 & 0xFFFFFFFF); 270 uint64_t hi = x3 + (x1 >> 32); 271 272 lo += k; 273 if (lo < k) 274 hi++; 275 *outHigh = hi; 276 return lo; 277#endif 278 } 279 280 static const size_t kBitCount = 3328; // 64bit * 54 > 10^1000 281 static const size_t kCapacity = kBitCount / sizeof(Type); 282 static const size_t kTypeBit = sizeof(Type) * 8; 283 284 Type digits_[kCapacity]; 285 size_t count_; 286}; 287 288} // namespace internal 289RAPIDJSON_NAMESPACE_END 290 291#endif // RAPIDJSON_BIGINTEGER_H_ 292