3 * @brief Arbitrary sized integer definitions
5 * @see add_digits_asm.s
6 * @see sub_digits_asm.s
7 * @see mul_digits_asm.s
25 Arbint::Arbint(int64_t i) : m_digits(1), m_sign(i < 0)
27 m_digits[0] = llabs(i);
30 Arbint::Arbint(unsigned n, digit_t d0, ...) : m_digits(n), m_sign(false)
36 for (unsigned i = 1; i < n; ++i)
38 m_digits[i] = va_arg(ap, digit_t);
43 Arbint::Arbint(const Arbint & cpy) : m_digits(cpy.m_digits), m_sign(cpy.m_sign)
48 Arbint::Arbint(const vector<digit_t> & digits) : m_digits(digits), m_sign(false)
53 Arbint & Arbint::operator=(const Arbint & cpy)
55 memmove(m_digits.data(), cpy.m_digits.data(),
56 sizeof(digit_t)*min(m_digits.size(), cpy.m_digits.size()));
57 if (cpy.m_digits.size() > m_digits.size())
59 unsigned old_size = m_digits.size();
60 m_digits.resize(cpy.m_digits.size());
61 memset(m_digits.data()+old_size, 0, sizeof(digit_t)*m_digits.size()-old_size);
68 memset(m_digits.data(), 0, sizeof(digit_t)*m_digits.size());
71 unsigned Arbint::Shrink()
73 if (m_digits.size() <= 1)
76 for (i = m_digits.size()-1; (i > 0 && m_digits[i] != 0L); --i);
77 unsigned result = m_digits.size() - i;
82 Arbint & Arbint::operator*=(const Arbint & mul)
84 vector<digit_t> new_digits(m_digits.size(), 0L);
85 new_digits.reserve(new_digits.size()+mul.m_digits.size());
86 for (unsigned i = 0; i < mul.m_digits.size(); ++i)
88 vector<digit_t> step(m_digits.size()+i, 0L);
89 memcpy(step.data()+i, m_digits.data(), sizeof(digit_t)*m_digits.size());
91 digit_t overflow = mul_digits((digit_t*)step.data()+i, mul.m_digits[i], m_digits.size());
94 step.push_back(overflow);
96 new_digits.resize(max(new_digits.size(), step.size()), 0L);
97 digit_t carry = add_digits((digit_t*)new_digits.data(), step.data(), step.size());
100 new_digits.push_back(carry);
104 m_digits.swap(new_digits);
105 m_sign = !(m_sign == mul.m_sign);
109 void Arbint::Division(const Arbint & div, Arbint & result, Arbint & remainder) const
113 for (int i = 8*sizeof(digit_t)*m_digits.size(); i >= 0; --i)
119 remainder.BitClear(0);
120 if (remainder >= div)
128 Arbint & Arbint::operator+=(const Arbint & add)
130 if (m_sign == add.m_sign)
132 // -a + -b == -(a + b)
133 return AddBasic(add);
138 // -a + b == -(a - b)
151 Arbint & Arbint::operator-=(const Arbint & sub)
153 if (m_sign == sub.m_sign)
154 return SubBasic(sub);
155 return AddBasic(sub);
158 Arbint & Arbint::AddBasic(const Arbint & add)
160 if (add.m_digits.size() >= m_digits.size())
162 m_digits.resize(add.m_digits.size()+1,0L);
165 digit_t carry = add_digits((digit_t*)m_digits.data(),
166 (digit_t*)add.m_digits.data(), add.m_digits.size());
168 m_digits[m_digits.size()-1] = carry;
169 else if (m_digits.back() == 0L)
170 m_digits.resize(m_digits.size()-1);
174 Arbint & Arbint::SubBasic(const Arbint & sub)
176 if (sub.m_digits.size() >= m_digits.size())
178 m_digits.resize(sub.m_digits.size(),0L);
180 digit_t borrow = sub_digits((digit_t*)m_digits.data(),
181 (digit_t*)sub.m_digits.data(), sub.m_digits.size());
184 //TODO: Write ASM to do this bit?
188 for (unsigned i = 0; i < m_digits.size(); ++i)
189 m_digits[i] = -m_digits[i];
195 string Arbint::Str(const string & base) const
200 reverse(s.begin(), s.end());
204 bool Arbint::IsZero() const
206 for (unsigned i = m_digits.size()-1; i > 0; --i)
208 if (m_digits[i] != 0L) return false;
210 return (m_digits[0] == 0L);
213 bool Arbint::operator==(const Arbint & equ) const
215 if (m_sign != equ.m_sign)
217 unsigned min_size = m_digits.size();
218 const Arbint * larger = &equ;
219 if (m_digits.size() > equ.m_digits.size())
221 min_size = equ.m_digits.size();
225 if (memcmp(m_digits.data(), equ.m_digits.data(), sizeof(digit_t)*min_size) != 0)
228 for (unsigned i = min_size; i < larger->m_digits.size(); ++i)
230 if (larger->m_digits[i] != 0L)
236 bool Arbint::operator<(const Arbint & less) const
240 return (cpy.m_sign && !cpy.IsZero());
243 string Arbint::DigitStr() const
246 //ss << std::hex << std::setfill('0');
247 for (unsigned i = 0; i < m_digits.size(); ++i)
249 if (i != 0) ss << ',';
250 //ss << std::setw(2*sizeof(digit_t)) << static_cast<digit_t>(m_digits[i]);
251 ss << static_cast<digit_t>(m_digits[i]);
256 Arbint & Arbint::operator>>=(unsigned amount)
258 // Shift by whole number of digits
259 unsigned whole = amount/(8*sizeof(digit_t));
260 unsigned old_size = m_digits.size();
262 if (whole >= old_size)
268 memmove(m_digits.data(), m_digits.data()+whole, sizeof(digit_t)*(old_size-whole));
269 m_digits.resize(old_size-whole, 0L);
271 // Shift by partial amount
272 amount = amount %(8*sizeof(digit_t));
276 digit_t underflow = 0L;
277 for (int i = (int)(m_digits.size()-1); i >= 0; --i)
279 unsigned shl = (8*sizeof(digit_t)-amount);
280 digit_t next_underflow = (m_digits[i] << shl);
281 //digit_t mask_upper = ~(0L >> amount);
282 m_digits[i] = (m_digits[i] >> amount);// & mask_upper;
283 m_digits[i] |= underflow;
284 underflow = next_underflow;
289 Arbint & Arbint::operator<<=(unsigned amount)
291 // Shift by whole number of digits
292 unsigned whole = amount/(8*sizeof(digit_t));
293 unsigned old_size = m_digits.size();
294 m_digits.resize(m_digits.size() + whole);
295 memmove(m_digits.data()+whole, m_digits.data(), sizeof(digit_t)*old_size);
296 memset(m_digits.data(), 0L, whole*sizeof(digit_t));
301 amount = amount % (8*sizeof(digit_t));
305 //Debug("Shift by %u from %u", amount, whole);
306 digit_t overflow = 0L;
307 for (unsigned i = whole; i < m_digits.size(); ++i)
309 //Debug("Digit is %.16lx", m_digits[i]);
310 unsigned shr = (8*sizeof(digit_t)-amount);
311 //Debug("shr is %u", shr);
312 digit_t next_overflow = (m_digits[i] >> shr);
313 //Debug("Next overflow %.16lx", next_overflow);
314 m_digits[i] <<= amount;
315 //Debug("Before overflow %.16lx", m_digits[i]);
316 m_digits[i] |= overflow;
317 overflow = next_overflow;
320 m_digits.push_back(overflow);
325 bool Arbint::GetBit(unsigned i) const
327 unsigned digit = i/(8*sizeof(digit_t));
328 if (digit > m_digits.size())
331 i = i % (8*sizeof(digit_t));
333 return (m_digits[digit] & (1L << i));
337 void Arbint::BitClear(unsigned i)
339 unsigned digit = i/(8*sizeof(digit_t));
340 if (digit > m_digits.size())
342 i = i % (8*sizeof(digit_t));
343 m_digits[digit] &= ~(1L << i);
346 void Arbint::BitSet(unsigned i)
348 unsigned digit = i/(8*sizeof(digit_t));
349 if (digit > m_digits.size())
351 m_digits.resize(digit+1, 0L);
353 i = i % (8*sizeof(digit_t));
354 m_digits[digit] |= (1L << i);