src/arbint.cpp

   1 /**
   2  * @file arbint.cpp
   3  * @brief Arbitrary sized integer definitions
   4  * @see arbint.h
   5  * @see add_digits_asm.s
   6  * @see sub_digits_asm.s
   7  * @see mul_digits_asm.s
   8  */
   9
  10 #include "arbint.h"
  11 #include <algorithm>
  12 #include <cstring>
  13
  14
  15 #include <string>
  16 #include <iomanip>
  17 #include <sstream>
  18 #include <cstdarg>
  19
  20 using namespace std;
  21
  22 namespace IPDF
  23 {
  24
  25 Arbint::Arbint(digit_t i) : m_digits(1), m_sign(i < 0)
  26 {
  27         m_digits[0] = llabs(i);
  28 }
  29
  30 Arbint::Arbint(unsigned n, digit_t d0, ...) : m_digits(n), m_sign(false)
  31 {
  32         va_list ap;
  33         va_start(ap, d0);
  34         if (n > 1)
  35                 m_digits[0] = d0;
  36         for (unsigned i = 1; i < n; ++i)
  37         {
  38                 m_digits[i] = va_arg(ap, digit_t);
  39         }
  40         va_end(ap);
  41 }
  42
  43 Arbint::Arbint(const Arbint & cpy) : m_digits(cpy.m_digits), m_sign(cpy.m_sign)
  44 {
  45
  46 }
  47
  48 Arbint::Arbint(const vector<digit_t> & digits) : m_digits(digits), m_sign(false)
  49 {
  50
  51 }
  52
  53 Arbint & Arbint::operator=(const Arbint & cpy)
  54 {
  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())
  58         {
  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);
  62         }
  63         return *this;
  64 }
  65
  66 void Arbint::Zero()
  67 {
  68         memset(m_digits.data(), 0, sizeof(digit_t)*m_digits.size());
  69 }
  70
  71 unsigned Arbint::Shrink()
  72 {
  73         if (m_digits.size() <= 1)
  74                 return 0;
  75         unsigned i;
  76         for (i = m_digits.size()-1; (i > 0 && m_digits[i] != 0L); --i);
  77         unsigned result = m_digits.size() - i;
  78         m_digits.resize(i);
  79         return result;
  80 }
  81
  82 Arbint & Arbint::operator*=(const Arbint & mul)
  83 {
  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)
  87         {
  88                 vector<digit_t> step(m_digits.size()+i, 0L);
  89                 memcpy(step.data()+i, m_digits.data(), sizeof(digit_t)*m_digits.size());
  90
  91                 digit_t overflow = mul_digits((digit_t*)step.data()+i, mul.m_digits[i], m_digits.size());
  92                 if (overflow != 0L)
  93                 {
  94                         step.push_back(overflow);
  95                 }
  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());
  98                 if (carry != 0L)
  99                 {
 100                         new_digits.push_back(carry);
 101                 }
 102         }
 103
 104         m_digits.swap(new_digits);
 105         m_sign = !(m_sign == mul.m_sign);
 106         return *this;
 107 }
 108
 109 void Arbint::Division(const Arbint & div, Arbint & result, Arbint & remainder) const
 110 {
 111         //TODO: Optimise?
 112         remainder = *this;
 113         result = 0L;
 114         while ((remainder -= div) > 0L)
 115         {
 116                 //Debug("Remainder %c%s", remainder.SignChar(), remainder.DigitStr().c_str());
 117                 //Debug("Result %c%s + 1", result.SignChar(), result.DigitStr().c_str());
 118                 result += 1;
 119         }
 120         remainder += div;
 121 }
 122
 123 Arbint & Arbint::operator+=(const Arbint & add)
 124 {
 125         if (m_sign == add.m_sign)
 126         {
 127                 // -a + -b == -(a + b)
 128                 return AddBasic(add);
 129         }
 130
 131         if (m_sign)
 132         {
 133                 // -a + b == -(a - b)
 134                 m_sign = false;
 135                 SubBasic(add);
 136                 m_sign = !m_sign;
 137         }
 138         else
 139         {
 140                 // a + -b == a - b
 141                 SubBasic(add);
 142         }
 143         return *this;
 144 }
 145
 146 Arbint & Arbint::operator-=(const Arbint & sub)
 147 {
 148         if (m_sign == sub.m_sign)
 149                 return SubBasic(sub);
 150         return AddBasic(sub);
 151 }
 152
 153 Arbint & Arbint::AddBasic(const Arbint & add)
 154 {
 155         if (add.m_digits.size() >= m_digits.size())
 156         {
 157                 m_digits.resize(add.m_digits.size()+1,0L);
 158         }
 159
 160         digit_t carry = add_digits((digit_t*)m_digits.data(),
 161                         (digit_t*)add.m_digits.data(), add.m_digits.size());
 162         if (carry != 0L)
 163                 m_digits[m_digits.size()-1] = carry;
 164         else if (m_digits.back() == 0L)
 165                 m_digits.resize(m_digits.size()-1);
 166         return *this;
 167 }
 168
 169 Arbint & Arbint::SubBasic(const Arbint & sub)
 170 {
 171         if (sub.m_digits.size() >= m_digits.size())
 172         {
 173                 m_digits.resize(sub.m_digits.size(),0L);
 174         }
 175         digit_t borrow = sub_digits((digit_t*)m_digits.data(),
 176                         (digit_t*)sub.m_digits.data(), sub.m_digits.size());
 177
 178
 179         //TODO: Write ASM to do this bit?
 180         if (borrow != 0L)
 181         {
 182                 m_sign = !m_sign;
 183                 for (unsigned i = 0; i < m_digits.size(); ++i)
 184                         m_digits[i] = -m_digits[i];
 185         }
 186         return *this;
 187 }
 188
 189
 190 string Arbint::Str(const string & base) const
 191 {
 192         string s("");
 193         for (unsigned i = 0; i < m_digits.size(); ++i)
 194         {
 195                 digit_t w = m_digits[i];
 196                 do
 197                 {
 198                         digit_t q = w % 10;
 199                         w /= 10;
 200                         s += ('0' + q);
 201                 }
 202                 while (w > 0);
 203                 if (i+1 < m_digits.size()) s += ",";
 204         }
 205         reverse(s.begin(), s.end());
 206         return s;
 207 }
 208
 209 bool Arbint::IsZero() const
 210 {
 211         for (unsigned i = m_digits.size()-1; i > 0; --i)
 212         {
 213                 if (m_digits[i] != 0L) return false;
 214         }
 215         return (m_digits[0] == 0L);
 216 }
 217
 218 bool Arbint::operator==(const Arbint & equ) const
 219 {
 220         if (m_sign != equ.m_sign) return false;
 221         unsigned min_size = m_digits.size();
 222         const Arbint * larger = &equ;
 223         if (m_digits.size() > equ.m_digits.size())
 224         {
 225                 min_size = equ.m_digits.size();
 226                 larger = this;
 227         }
 228
 229         if (memcmp(m_digits.data(), equ.m_digits.data(), sizeof(digit_t)*min_size) != 0)
 230                 return false;
 231
 232         for (unsigned i = min_size; i < larger->m_digits.size(); ++i)
 233         {
 234                 if (larger->m_digits[i] != 0L)
 235                         return false;
 236         }
 237         return true;
 238 }
 239
 240 bool Arbint::operator<(const Arbint & less) const
 241 {
 242         Arbint cpy(*this);
 243         cpy -= less;
 244         return (cpy.m_sign && !cpy.IsZero());
 245 }
 246
 247 string Arbint::DigitStr() const
 248 {
 249         stringstream ss("");
 250         ss << std::hex << std::setfill('0');
 251         for (unsigned i = 0; i < m_digits.size(); ++i)
 252         {
 253                 if (i != 0) ss << ',';
 254                 ss << std::setw(2*sizeof(digit_t)) << static_cast<digit_t>(m_digits[i]);
 255         }
 256         return ss.str();
 257 }
 258
 259 }