biginteger.h
Go to the documentation of this file.
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) && !__INTEL_COMPILER && defined(_M_AMD64)
21 #include <intrin.h> // for _umul128
22 #pragma intrinsic(_umul128)
23 #endif
24 
26 namespace internal {
27 
28 class BigInteger {
29 public:
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 
56  {
57  if (this != &rhs) {
58  count_ = rhs.count_;
59  std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
60  }
61  return *this;
62  }
63 
65  digits_[0] = u;
66  count_ = 1;
67  return *this;
68  }
69 
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 
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 
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_ + offset, digits_, 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 
223 private:
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) {
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
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 
284  size_t count_;
285 };
286 
287 } // namespace internal
289 
290 #endif // RAPIDJSON_BIGINTEGER_H_
static const size_t kCapacity
Definition: biginteger.h:280
end
while True: pbar.update(maxval-len(onlies[E][S])) #print iS, "/", len(onlies[E][S]) found = False for...
BigInteger & operator<<=(size_t shift)
Definition: biginteger.h:128
BigInteger & operator+=(uint64_t u)
Definition: biginteger.h:70
bool IsZero() const
Definition: biginteger.h:221
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:406
Type GetDigit(size_t index) const
Definition: biginteger.h:220
#define RAPIDJSON_UINT64_C2(high32, low32)
Construct a 64-bit literal by a pair of 32-bit integer.
Definition: rapidjson.h:289
#define a0
#define RAPIDJSON_NAMESPACE_END
provide custom rapidjson namespace (closing expression)
Definition: rapidjson.h:124
void AppendDecimal64(const char *begin, const char *end)
Definition: biginteger.h:224
BigInteger & operator=(uint64_t u)
Definition: biginteger.h:64
BigInteger & operator*=(uint32_t u)
Definition: biginteger.h:105
size_t GetCount() const
Definition: biginteger.h:219
int Compare(const BigInteger &rhs) const
Definition: biginteger.h:208
void PushBack(Type digit)
Definition: biginteger.h:234
#define RAPIDJSON_NAMESPACE_BEGIN
provide custom rapidjson namespace (opening expression)
Definition: rapidjson.h:121
BigInteger(const BigInteger &rhs)
Definition: biginteger.h:32
static uint64_t MulAdd64(uint64_t a, uint64_t b, uint64_t k, uint64_t *outHigh)
Definition: biginteger.h:249
BigInteger(const char *decimals, size_t length)
Definition: biginteger.h:40
unsigned int uint32_t
Definition: stdint.h:126
static uint64_t ParseUint64(const char *begin, const char *end)
Definition: biginteger.h:239
BigInteger(uint64_t u)
Definition: biginteger.h:36
unsigned __int64 uint64_t
Definition: stdint.h:136
BigInteger & operator=(const BigInteger &rhs)
Definition: biginteger.h:55
BigInteger & operator*=(uint64_t u)
Definition: biginteger.h:87
Type digits_[kCapacity]
Definition: biginteger.h:283
bool operator==(const Type rhs) const
Definition: biginteger.h:158
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
p
Definition: test.py:223
static const size_t kTypeBit
Definition: biginteger.h:281
bool operator==(const BigInteger &rhs) const
Definition: biginteger.h:154
static bool * b
Definition: config.cpp:1043
decltype(auto) constexpr begin(T &&obj)
ADL-aware version of std::begin.
Definition: StdUtils.h:72
static const size_t kBitCount
Definition: biginteger.h:279
BigInteger & MultiplyPow5(unsigned exp)
Definition: biginteger.h:162
#define a1
bool Difference(const BigInteger &rhs, BigInteger *out) const
Definition: biginteger.h:186