3 * @brief Arbitrary sized integer definitions
5 * @see add_digits_asm.s
6 * @see sub_digits_asm.s
7 * @see mul_digits_asm.s
27 /** Absolute value hackery **/
28 template <> Arbint Tabs(const Arbint & a)
35 Arbint::Arbint(int64_t i) : m_digits(1), m_sign(i < 0)
37 m_digits[0] = llabs(i);
40 Arbint::Arbint(unsigned n, digit_t d0, ...) : m_digits(n), m_sign(false)
46 for (unsigned i = 1; i < n; ++i)
48 m_digits[i] = va_arg(ap, digit_t);
53 Arbint::Arbint(const Arbint & cpy) : m_digits(cpy.m_digits), m_sign(cpy.m_sign)
58 Arbint::Arbint(const vector<digit_t> & digits) : m_digits(digits), m_sign(false)
63 Arbint & Arbint::operator=(const Arbint & cpy)
65 m_digits = cpy.m_digits;
72 m_digits.resize(1, 0L);
75 unsigned Arbint::Shrink()
78 if (m_digits.size() <= 1)
82 while (m_digits.size() > 1 && m_digits[m_digits.size()-1] == 0L)
91 void Arbint::GrowDigit(digit_t new_msd)
93 static unsigned total_grows = 0;
94 static unsigned biggest_arbint = 1;
95 m_digits.push_back(new_msd);
97 if (m_digits.size() > biggest_arbint)
99 biggest_arbint = m_digits.size();
100 Warn("New biggest Arbint of size %u", m_digits.size());
102 //Warn("Arbint grows digit (%.16lx), this->m_digits.size() = %u, total grown = %u", new_msd, m_digits.size(), ++total_grows);
103 //if (total_grows++ > 10000)
105 // Fatal("Too many GrowDigit calls!");
109 Arbint & Arbint::operator*=(const Arbint & mul)
111 vector<digit_t> new_digits(m_digits.size(), 0L);
112 new_digits.reserve(new_digits.size()+mul.m_digits.size());
113 for (unsigned i = 0; i < mul.m_digits.size(); ++i)
115 vector<digit_t> step(m_digits.size()+i, 0L);
116 memcpy(step.data()+i, m_digits.data(), sizeof(digit_t)*m_digits.size());
118 digit_t overflow = mul_digits((digit_t*)step.data()+i, mul.m_digits[i], m_digits.size());
121 step.push_back(overflow);
123 new_digits.resize(max(new_digits.size(), step.size()), 0L);
124 digit_t carry = add_digits((digit_t*)new_digits.data(), step.data(), step.size());
132 m_digits.swap(new_digits);
133 m_sign = !(m_sign == mul.m_sign);
138 void Arbint::Division(const Arbint & div, Arbint & result, Arbint & remainder) const
147 /* may break things (even more that is)
148 else if (div.m_digits.size() == 1)
150 result.m_digits.resize(m_digits.size(), 0L);
151 remainder = Arbint(div_digits((digit_t*)&m_digits[0], div.m_digits[0], m_digits.size(), result.m_digits.data()));
152 result.m_sign = !(m_sign == div.m_sign);
156 for (int i = 8*sizeof(digit_t)*m_digits.size(); i >= 0; --i)
162 remainder.BitClear(0);
163 if (remainder >= div)
169 result.m_sign = !(m_sign == div.m_sign);
173 Arbint & Arbint::operator+=(const Arbint & add)
175 if (m_sign == add.m_sign)
177 // -a + -b == -(a + b)
178 return AddBasic(add);
183 // -a + b == -(a - b)
197 Arbint & Arbint::operator-=(const Arbint & sub)
199 if (m_sign == sub.m_sign)
200 return SubBasic(sub);
201 return AddBasic(sub);
204 Arbint & Arbint::AddBasic(const Arbint & add)
206 // Add any leading zeros to this number
207 while (m_digits.size() < add.m_digits.size())
211 //m_digits.resize(add.m_digits.size()+1,0L);
213 digit_t carry = add_digits((digit_t*)m_digits.data(),
214 (digit_t*)add.m_digits.data(), add.m_digits.size());
216 // This number had more digits but there is a carry left over
217 if (carry != 0L && m_digits.size() > add.m_digits.size())
219 vector<digit_t> carry_digits(m_digits.size() - add.m_digits.size(), 0L);
220 carry_digits[0] = carry;
221 carry = add_digits((digit_t*)m_digits.data()+add.m_digits.size(),
222 (digit_t*)carry_digits.data(), m_digits.size()-add.m_digits.size());
225 // There is still a carry left over
234 Arbint & Arbint::SubBasic(const Arbint & sub)
237 while (sub.m_digits.size() > m_digits.size())
242 // Do subtraction on digits
243 digit_t borrow = sub_digits((digit_t*)m_digits.data(),
244 (digit_t*)sub.m_digits.data(), sub.m_digits.size());
246 // This number had more digits but there is a borrow left over
247 if (borrow != 0L && m_digits.size() > sub.m_digits.size())
249 vector<digit_t> borrow_digits(m_digits.size()-sub.m_digits.size(), 0L);
250 borrow_digits[0] = borrow;
251 borrow = sub_digits((digit_t*)m_digits.data()+sub.m_digits.size(),
252 (digit_t*)borrow_digits.data(), m_digits.size()-sub.m_digits.size());
255 // borrow is still set => number is negative
259 for (unsigned i = 0; i < m_digits.size(); ++i)
260 m_digits[i] = (~m_digits[i]);
261 vector<digit_t> one_digits(m_digits.size(), 0L);
263 add_digits((digit_t*)m_digits.data(), (digit_t*)one_digits.data(), m_digits.size());
270 string Arbint::Str(const string & base) const
274 unsigned b = base.size();
275 while (cpy > Arbint(0L))
277 //Debug("cpy is %s", cpy.DigitStr().c_str());
278 unsigned c = (unsigned)(cpy % Arbint(b)).AsDigit();
284 reverse(s.begin(), s.end());
288 bool Arbint::IsZero() const
290 for (unsigned i = m_digits.size()-1; i > 0; --i)
292 if (m_digits[i] != 0L) return false;
294 return (m_digits[0] == 0L);
297 bool Arbint::operator==(const Arbint & equ) const
299 if (m_sign != equ.m_sign)
301 unsigned min_size = m_digits.size();
302 const Arbint * larger = &equ;
303 if (m_digits.size() > equ.m_digits.size())
305 min_size = equ.m_digits.size();
309 if (memcmp(m_digits.data(), equ.m_digits.data(), sizeof(digit_t)*min_size) != 0)
312 for (unsigned i = min_size; i < larger->m_digits.size(); ++i)
314 if (larger->m_digits[i] != 0L)
320 bool Arbint::operator<(const Arbint & less) const
324 return (cpy.m_sign && !cpy.IsZero());
327 string Arbint::DigitStr() const
330 //ss << std::hex << std::setfill('0');
331 for (unsigned i = 0; i < m_digits.size(); ++i)
333 if (i != 0) ss << ',';
334 //ss << std::setw(2*sizeof(digit_t)) << static_cast<digit_t>(m_digits[i]);
335 ss << static_cast<digit_t>(m_digits[i]);
340 Arbint & Arbint::operator>>=(unsigned amount)
342 // Shift by whole number of digits
343 unsigned whole = amount/(8*sizeof(digit_t));
344 unsigned old_size = m_digits.size();
346 if (whole >= old_size)
348 m_digits.resize(1,0L);
352 memmove(m_digits.data(), m_digits.data()+whole, sizeof(digit_t)*(old_size-whole));
353 m_digits.resize(old_size-whole, 0L);
355 // Shift by partial amount
356 amount = amount %(8*sizeof(digit_t));
360 digit_t underflow = 0L;
361 for (int i = (int)(m_digits.size()-1); i >= 0; --i)
363 unsigned shl = (8*sizeof(digit_t)-amount);
364 digit_t next_underflow = (m_digits[i] << shl);
365 //digit_t mask_upper = ~(0L >> amount);
366 m_digits[i] = (m_digits[i] >> amount);// & mask_upper;
367 m_digits[i] |= underflow;
368 underflow = next_underflow;
374 Arbint & Arbint::operator<<=(unsigned amount)
376 // Shift by whole number of digits
377 unsigned whole = amount/(8*sizeof(digit_t));
378 unsigned old_size = m_digits.size();
379 for (unsigned i = 0; i < whole; ++i)
381 //Debug("i = %u, whole = %u", i, whole);
382 GrowDigit(0L);//m_digits.resize(m_digits.size() + whole);
384 memmove(m_digits.data()+whole, m_digits.data(), sizeof(digit_t)*old_size);
385 memset(m_digits.data(), 0L, whole*sizeof(digit_t));
390 amount = amount % (8*sizeof(digit_t));
394 //Debug("Shift by %u from %u", amount, whole);
395 digit_t overflow = 0L;
396 for (unsigned i = whole; i < m_digits.size(); ++i)
398 //Debug("Digit is %.16lx", m_digits[i]);
399 unsigned shr = (8*sizeof(digit_t)-amount);
400 //Debug("shr is %u", shr);
401 digit_t next_overflow = (m_digits[i] >> shr);
402 //Debug("Next overflow %.16lx", next_overflow);
403 m_digits[i] <<= amount;
404 //Debug("Before overflow %.16lx", m_digits[i]);
405 m_digits[i] |= overflow;
406 overflow = next_overflow;
409 m_digits.push_back(overflow);
414 bool Arbint::GetBit(unsigned i) const
416 unsigned digit = i/(8*sizeof(digit_t));
417 if (digit >= m_digits.size())
420 i = i % (8*sizeof(digit_t));
422 return (m_digits[digit] & (1L << i));
426 void Arbint::BitClear(unsigned i)
428 unsigned digit = i/(8*sizeof(digit_t));
429 if (digit >= m_digits.size())
431 i = i % (8*sizeof(digit_t));
432 m_digits[digit] &= ~(1L << i);
435 void Arbint::BitSet(unsigned i)
437 unsigned digit = i/(8*sizeof(digit_t));
438 while (m_digits.size() < digit+1)
440 //Debug("Grow BitSet Size %u, digit %u", m_digits.size(), digit);
444 i = i % (8*sizeof(digit_t));
445 m_digits[digit] |= (1L << i);