X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=blobdiff_plain;f=src%2Farbint.cpp;h=8af84f951f39694ad309e9ab96cb28a693ddd39b;hp=ac3994260836d567fa94f636aaab305151f2bb32;hb=e88c1ef58e2446cf57d5f7b0d5d4e5bfff0b8c37;hpb=924cb525f587c58440c43bcae6ccfd9b2e41c99c diff --git a/src/arbint.cpp b/src/arbint.cpp index ac39942..8af84f9 100644 --- a/src/arbint.cpp +++ b/src/arbint.cpp @@ -74,13 +74,36 @@ void Arbint::Zero() unsigned Arbint::Shrink() { + if (m_digits.size() <= 1) return 0; - unsigned i; - for (i = m_digits.size()-1; (i > 0 && m_digits[i] != 0L); --i); - unsigned result = m_digits.size() - i; - m_digits.resize(i); - return result; + + unsigned shrunk = 0; + while (m_digits.size() > 1 && m_digits[m_digits.size()-1] == 0L) + { + //Debug("Shrink 1"); + m_digits.pop_back(); + shrunk++; + } + return shrunk; +} + +void Arbint::GrowDigit(digit_t new_msd) +{ + static unsigned total_grows = 0; + static unsigned biggest_arbint = 1; + m_digits.push_back(new_msd); + total_grows++; + if (m_digits.size() > biggest_arbint) + { + biggest_arbint = m_digits.size(); + Warn("New biggest Arbint of size %u", m_digits.size()); + } + //Warn("Arbint grows digit (%.16lx), this->m_digits.size() = %u, total grown = %u", new_msd, m_digits.size(), ++total_grows); + //if (total_grows++ > 10000) + //{ + // Fatal("Too many GrowDigit calls!"); + //} } Arbint & Arbint::operator*=(const Arbint & mul) @@ -101,12 +124,14 @@ Arbint & Arbint::operator*=(const Arbint & mul) digit_t carry = add_digits((digit_t*)new_digits.data(), step.data(), step.size()); if (carry != 0L) { - new_digits.push_back(carry); + Debug("Add carry"); + GrowDigit(carry); } } m_digits.swap(new_digits); m_sign = !(m_sign == mul.m_sign); + Shrink(); return *this; } @@ -119,6 +144,15 @@ void Arbint::Division(const Arbint & div, Arbint & result, Arbint & remainder) c result = *this; return; } + /* may break things (even more that is) + else if (div.m_digits.size() == 1) + { + result.m_digits.resize(m_digits.size(), 0L); + remainder = Arbint(div_digits((digit_t*)&m_digits[0], div.m_digits[0], m_digits.size(), result.m_digits.data())); + result.m_sign = !(m_sign == div.m_sign); + return; + } */ + for (int i = 8*sizeof(digit_t)*m_digits.size(); i >= 0; --i) { remainder <<= 1; @@ -133,6 +167,7 @@ void Arbint::Division(const Arbint & div, Arbint & result, Arbint & remainder) c } } result.m_sign = !(m_sign == div.m_sign); + result.Shrink(); } Arbint & Arbint::operator+=(const Arbint & add) @@ -155,6 +190,7 @@ Arbint & Arbint::operator+=(const Arbint & add) // a + -b == a - b SubBasic(add); } + Shrink(); return *this; } @@ -167,37 +203,66 @@ Arbint & Arbint::operator-=(const Arbint & sub) Arbint & Arbint::AddBasic(const Arbint & add) { - if (add.m_digits.size() >= m_digits.size()) + // Add any leading zeros to this number + while (m_digits.size() < add.m_digits.size()) { - m_digits.resize(add.m_digits.size()+1,0L); + GrowDigit(0L); } + //m_digits.resize(add.m_digits.size()+1,0L); digit_t carry = add_digits((digit_t*)m_digits.data(), (digit_t*)add.m_digits.data(), add.m_digits.size()); + + // This number had more digits but there is a carry left over + if (carry != 0L && m_digits.size() > add.m_digits.size()) + { + vector carry_digits(m_digits.size() - add.m_digits.size(), 0L); + carry_digits[0] = carry; + carry = add_digits((digit_t*)m_digits.data()+add.m_digits.size(), + (digit_t*)carry_digits.data(), m_digits.size()-add.m_digits.size()); + } + + // There is still a carry left over if (carry != 0L) - m_digits[m_digits.size()-1] = carry; - else if (m_digits.back() == 0L) - m_digits.resize(m_digits.size()-1); + { + GrowDigit(carry); + } + Shrink(); return *this; } Arbint & Arbint::SubBasic(const Arbint & sub) { - if (sub.m_digits.size() >= m_digits.size()) + // Add leading zeros + while (sub.m_digits.size() > m_digits.size()) { - m_digits.resize(sub.m_digits.size(),0L); + GrowDigit(0L); } + + // Do subtraction on digits digit_t borrow = sub_digits((digit_t*)m_digits.data(), (digit_t*)sub.m_digits.data(), sub.m_digits.size()); - - - //TODO: Write ASM to do this bit? + + // This number had more digits but there is a borrow left over + if (borrow != 0L && m_digits.size() > sub.m_digits.size()) + { + vector borrow_digits(m_digits.size()-sub.m_digits.size(), 0L); + borrow_digits[0] = borrow; + borrow = sub_digits((digit_t*)m_digits.data()+sub.m_digits.size(), + (digit_t*)borrow_digits.data(), m_digits.size()-sub.m_digits.size()); + } + + // borrow is still set => number is negative if (borrow != 0L) { m_sign = !m_sign; for (unsigned i = 0; i < m_digits.size(); ++i) - m_digits[i] = -m_digits[i]; + m_digits[i] = (~m_digits[i]); + vector one_digits(m_digits.size(), 0L); + one_digits[0] = 1L; + add_digits((digit_t*)m_digits.data(), (digit_t*)one_digits.data(), m_digits.size()); } + Shrink(); return *this; } @@ -206,7 +271,16 @@ string Arbint::Str(const string & base) const { string s(""); Arbint cpy(*this); - + unsigned b = base.size(); + while (cpy > Arbint(0L)) + { + //Debug("cpy is %s", cpy.DigitStr().c_str()); + unsigned c = (unsigned)(cpy % Arbint(b)).AsDigit(); + s += base[c]; + cpy /= Arbint(b); + } + if (m_sign) + s += '-'; reverse(s.begin(), s.end()); return s; } @@ -293,6 +367,7 @@ Arbint & Arbint::operator>>=(unsigned amount) m_digits[i] |= underflow; underflow = next_underflow; } + Shrink(); return *this; } @@ -301,7 +376,11 @@ Arbint & Arbint::operator<<=(unsigned amount) // Shift by whole number of digits unsigned whole = amount/(8*sizeof(digit_t)); unsigned old_size = m_digits.size(); - m_digits.resize(m_digits.size() + whole); + for (unsigned i = 0; i < whole; ++i) + { + //Debug("i = %u, whole = %u", i, whole); + GrowDigit(0L);//m_digits.resize(m_digits.size() + whole); + } memmove(m_digits.data()+whole, m_digits.data(), sizeof(digit_t)*old_size); memset(m_digits.data(), 0L, whole*sizeof(digit_t)); @@ -328,7 +407,7 @@ Arbint & Arbint::operator<<=(unsigned amount) } if (overflow != 0L) m_digits.push_back(overflow); - + Shrink(); return *this; } @@ -356,10 +435,12 @@ void Arbint::BitClear(unsigned i) void Arbint::BitSet(unsigned i) { unsigned digit = i/(8*sizeof(digit_t)); - if (digit >= m_digits.size()) + while (m_digits.size() < digit+1) { - m_digits.resize(digit+1, 0L); + //Debug("Grow BitSet Size %u, digit %u", m_digits.size(), digit); + GrowDigit(0L); } + i = i % (8*sizeof(digit_t)); m_digits[digit] |= (1L << i); }