Electroneum
internal::BigInteger Class Reference

#include <biginteger.h>

Public Types

typedef uint64_t Type
 

Public Member Functions

 BigInteger (const BigInteger &rhs)
 
 BigInteger (uint64_t u)
 
 BigInteger (const char *decimals, size_t length)
 
BigIntegeroperator= (const BigInteger &rhs)
 
BigIntegeroperator= (uint64_t u)
 
BigIntegeroperator+= (uint64_t u)
 
BigIntegeroperator*= (uint64_t u)
 
BigIntegeroperator*= (uint32_t u)
 
BigIntegeroperator<<= (size_t shift)
 
bool operator== (const BigInteger &rhs) const
 
bool operator== (const Type rhs) const
 
BigIntegerMultiplyPow5 (unsigned exp)
 
bool Difference (const BigInteger &rhs, BigInteger *out) const
 
int Compare (const BigInteger &rhs) const
 
size_t GetCount () const
 
Type GetDigit (size_t index) const
 
bool IsZero () const
 

Detailed Description

Definition at line 28 of file biginteger.h.

Member Typedef Documentation

◆ Type

Definition at line 30 of file biginteger.h.

Constructor & Destructor Documentation

◆ BigInteger() [1/3]

internal::BigInteger::BigInteger ( const BigInteger rhs)
inline

Definition at line 32 of file biginteger.h.

32  : count_(rhs.count_) {
33  std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
34  }
void * memcpy(void *a, const void *b, size_t c)
Type
Type of JSON value.
Definition: rapidjson.h:620
Here is the call graph for this function:

◆ BigInteger() [2/3]

internal::BigInteger::BigInteger ( uint64_t  u)
inlineexplicit

Definition at line 36 of file biginteger.h.

36  : count_(1) {
37  digits_[0] = u;
38  }

◆ BigInteger() [3/3]

internal::BigInteger::BigInteger ( const char *  decimals,
size_t  length 
)
inline

Definition at line 40 of file biginteger.h.

40  : 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  }
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:411

Member Function Documentation

◆ Compare()

int internal::BigInteger::Compare ( const BigInteger rhs) const
inline

Definition at line 208 of file biginteger.h.

208  {
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  }
Here is the caller graph for this function:

◆ Difference()

bool internal::BigInteger::Difference ( const BigInteger rhs,
BigInteger out 
) const
inline

Definition at line 186 of file biginteger.h.

186  {
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  }
int Compare(const BigInteger &rhs) const
Definition: biginteger.h:208
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
BigInteger(const BigInteger &rhs)
Definition: biginteger.h:32
Type
Type of JSON value.
Definition: rapidjson.h:620
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:411
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GetCount()

size_t internal::BigInteger::GetCount ( ) const
inline

Definition at line 219 of file biginteger.h.

219 { return count_; }

◆ GetDigit()

Type internal::BigInteger::GetDigit ( size_t  index) const
inline

Definition at line 220 of file biginteger.h.

220 { RAPIDJSON_ASSERT(index < count_); return digits_[index]; }
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:411

◆ IsZero()

bool internal::BigInteger::IsZero ( ) const
inline

Definition at line 221 of file biginteger.h.

221 { return count_ == 1 && digits_[0] == 0; }
Here is the caller graph for this function:

◆ MultiplyPow5()

BigInteger& internal::BigInteger::MultiplyPow5 ( unsigned  exp)
inline

Definition at line 162 of file biginteger.h.

162  {
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  }
#define RAPIDJSON_UINT64_C2(high32, low32)
Construct a 64-bit literal by a pair of 32-bit integer.
Definition: rapidjson.h:294
unsigned int uint32_t
Definition: stdint.h:126
Here is the caller graph for this function:

◆ operator*=() [1/2]

BigInteger& internal::BigInteger::operator*= ( uint64_t  u)
inline

Definition at line 87 of file biginteger.h.

87  {
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  }
unsigned __int64 uint64_t
Definition: stdint.h:136

◆ operator*=() [2/2]

BigInteger& internal::BigInteger::operator*= ( uint32_t  u)
inline

Definition at line 105 of file biginteger.h.

105  {
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  }
unsigned __int64 uint64_t
Definition: stdint.h:136

◆ operator+=()

BigInteger& internal::BigInteger::operator+= ( uint64_t  u)
inline

Definition at line 70 of file biginteger.h.

70  {
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  }
Type
Type of JSON value.
Definition: rapidjson.h:620

◆ operator<<=()

BigInteger& internal::BigInteger::operator<<= ( size_t  shift)
inline

Definition at line 128 of file biginteger.h.

128  {
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  }
bool IsZero() const
Definition: biginteger.h:221
Type
Type of JSON value.
Definition: rapidjson.h:620
void * memmove(void *a, const void *b, size_t c)
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:411
Here is the call graph for this function:

◆ operator=() [1/2]

BigInteger& internal::BigInteger::operator= ( const BigInteger rhs)
inline

Definition at line 55 of file biginteger.h.

56  {
57  if (this != &rhs) {
58  count_ = rhs.count_;
59  std::memcpy(digits_, rhs.digits_, count_ * sizeof(Type));
60  }
61  return *this;
62  }
void * memcpy(void *a, const void *b, size_t c)
Type
Type of JSON value.
Definition: rapidjson.h:620
Here is the call graph for this function:

◆ operator=() [2/2]

BigInteger& internal::BigInteger::operator= ( uint64_t  u)
inline

Definition at line 64 of file biginteger.h.

64  {
65  digits_[0] = u;
66  count_ = 1;
67  return *this;
68  }

◆ operator==() [1/2]

bool internal::BigInteger::operator== ( const BigInteger rhs) const
inline

Definition at line 154 of file biginteger.h.

154  {
155  return count_ == rhs.count_ && std::memcmp(digits_, rhs.digits_, count_ * sizeof(Type)) == 0;
156  }
Type
Type of JSON value.
Definition: rapidjson.h:620

◆ operator==() [2/2]

bool internal::BigInteger::operator== ( const Type  rhs) const
inline

Definition at line 158 of file biginteger.h.

158  {
159  return count_ == 1 && digits_[0] == rhs;
160  }

The documentation for this class was generated from the following file: