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 m_digits = cpy.m_digits;
62 m_digits.resize(1, 0L);
65 unsigned Arbint::Shrink()
67 if (m_digits.size() <= 1)
70 for (i = m_digits.size()-1; (i > 0 && m_digits[i] != 0L); --i);
71 unsigned result = m_digits.size() - i;
76 Arbint & Arbint::operator*=(const Arbint & mul)
78 vector<digit_t> new_digits(m_digits.size(), 0L);
79 new_digits.reserve(new_digits.size()+mul.m_digits.size());
80 for (unsigned i = 0; i < mul.m_digits.size(); ++i)
82 vector<digit_t> step(m_digits.size()+i, 0L);
83 memcpy(step.data()+i, m_digits.data(), sizeof(digit_t)*m_digits.size());
85 digit_t overflow = mul_digits((digit_t*)step.data()+i, mul.m_digits[i], m_digits.size());
88 step.push_back(overflow);
90 new_digits.resize(max(new_digits.size(), step.size()), 0L);
91 digit_t carry = add_digits((digit_t*)new_digits.data(), step.data(), step.size());
94 new_digits.push_back(carry);
98 m_digits.swap(new_digits);
99 m_sign = !(m_sign == mul.m_sign);
103 void Arbint::Division(const Arbint & div, Arbint & result, Arbint & remainder) const
107 for (int i = 8*sizeof(digit_t)*m_digits.size(); i >= 0; --i)
113 remainder.BitClear(0);
114 if (remainder >= div)
122 Arbint & Arbint::operator+=(const Arbint & add)
124 if (m_sign == add.m_sign)
126 // -a + -b == -(a + b)
127 return AddBasic(add);
132 // -a + b == -(a - b)
145 Arbint & Arbint::operator-=(const Arbint & sub)
147 if (m_sign == sub.m_sign)
148 return SubBasic(sub);
149 return AddBasic(sub);
152 Arbint & Arbint::AddBasic(const Arbint & add)
154 if (add.m_digits.size() >= m_digits.size())
156 m_digits.resize(add.m_digits.size()+1,0L);
159 digit_t carry = add_digits((digit_t*)m_digits.data(),
160 (digit_t*)add.m_digits.data(), add.m_digits.size());
162 m_digits[m_digits.size()-1] = carry;
163 else if (m_digits.back() == 0L)
164 m_digits.resize(m_digits.size()-1);
168 Arbint & Arbint::SubBasic(const Arbint & sub)
170 if (sub.m_digits.size() >= m_digits.size())
172 m_digits.resize(sub.m_digits.size(),0L);
174 digit_t borrow = sub_digits((digit_t*)m_digits.data(),
175 (digit_t*)sub.m_digits.data(), sub.m_digits.size());
178 //TODO: Write ASM to do this bit?
182 for (unsigned i = 0; i < m_digits.size(); ++i)
183 m_digits[i] = -m_digits[i];
189 string Arbint::Str(const string & base) const
194 reverse(s.begin(), s.end());
198 bool Arbint::IsZero() const
200 for (unsigned i = m_digits.size()-1; i > 0; --i)
202 if (m_digits[i] != 0L) return false;
204 return (m_digits[0] == 0L);
207 bool Arbint::operator==(const Arbint & equ) const
209 if (m_sign != equ.m_sign)
211 unsigned min_size = m_digits.size();
212 const Arbint * larger = &equ;
213 if (m_digits.size() > equ.m_digits.size())
215 min_size = equ.m_digits.size();
219 if (memcmp(m_digits.data(), equ.m_digits.data(), sizeof(digit_t)*min_size) != 0)
222 for (unsigned i = min_size; i < larger->m_digits.size(); ++i)
224 if (larger->m_digits[i] != 0L)
230 bool Arbint::operator<(const Arbint & less) const
234 return (cpy.m_sign && !cpy.IsZero());
237 string Arbint::DigitStr() const
240 //ss << std::hex << std::setfill('0');
241 for (unsigned i = 0; i < m_digits.size(); ++i)
243 if (i != 0) ss << ',';
244 //ss << std::setw(2*sizeof(digit_t)) << static_cast<digit_t>(m_digits[i]);
245 ss << static_cast<digit_t>(m_digits[i]);
250 Arbint & Arbint::operator>>=(unsigned amount)
252 // Shift by whole number of digits
253 unsigned whole = amount/(8*sizeof(digit_t));
254 unsigned old_size = m_digits.size();
256 if (whole >= old_size)
262 memmove(m_digits.data(), m_digits.data()+whole, sizeof(digit_t)*(old_size-whole));
263 m_digits.resize(old_size-whole, 0L);
265 // Shift by partial amount
266 amount = amount %(8*sizeof(digit_t));
270 digit_t underflow = 0L;
271 for (int i = (int)(m_digits.size()-1); i >= 0; --i)
273 unsigned shl = (8*sizeof(digit_t)-amount);
274 digit_t next_underflow = (m_digits[i] << shl);
275 //digit_t mask_upper = ~(0L >> amount);
276 m_digits[i] = (m_digits[i] >> amount);// & mask_upper;
277 m_digits[i] |= underflow;
278 underflow = next_underflow;
283 Arbint & Arbint::operator<<=(unsigned amount)
285 // Shift by whole number of digits
286 unsigned whole = amount/(8*sizeof(digit_t));
287 unsigned old_size = m_digits.size();
288 m_digits.resize(m_digits.size() + whole);
289 memmove(m_digits.data()+whole, m_digits.data(), sizeof(digit_t)*old_size);
290 memset(m_digits.data(), 0L, whole*sizeof(digit_t));
295 amount = amount % (8*sizeof(digit_t));
299 //Debug("Shift by %u from %u", amount, whole);
300 digit_t overflow = 0L;
301 for (unsigned i = whole; i < m_digits.size(); ++i)
303 //Debug("Digit is %.16lx", m_digits[i]);
304 unsigned shr = (8*sizeof(digit_t)-amount);
305 //Debug("shr is %u", shr);
306 digit_t next_overflow = (m_digits[i] >> shr);
307 //Debug("Next overflow %.16lx", next_overflow);
308 m_digits[i] <<= amount;
309 //Debug("Before overflow %.16lx", m_digits[i]);
310 m_digits[i] |= overflow;
311 overflow = next_overflow;
314 m_digits.push_back(overflow);
319 bool Arbint::GetBit(unsigned i) const
321 unsigned digit = i/(8*sizeof(digit_t));
322 if (digit >= m_digits.size())
325 i = i % (8*sizeof(digit_t));
327 return (m_digits[digit] & (1L << i));
331 void Arbint::BitClear(unsigned i)
333 unsigned digit = i/(8*sizeof(digit_t));
334 if (digit >= m_digits.size())
336 i = i % (8*sizeof(digit_t));
337 m_digits[digit] &= ~(1L << i);
340 void Arbint::BitSet(unsigned i)
342 unsigned digit = i/(8*sizeof(digit_t));
343 if (digit >= m_digits.size())
345 m_digits.resize(digit+1, 0L);
347 i = i % (8*sizeof(digit_t));
348 m_digits[digit] |= (1L << i);