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         if (div == Arbint(1L))
 112         {
 113                 result = *this;
 114                 remainder = 0L;
 115                 return;
 116         }
 117         if (div == *this)
 118         {
 119                 result = 1L;
 120                 remainder = 0L;
 121                 return;
 122         }
 123
 124
 125         result = 0L;
 126         remainder = *this;
 127         Arbint next_rem(remainder);
 128         while ((next_rem -= div) >= Arbint(0L))
 129         {
 130                 //Debug("%li - %li = %li", digit_t(remainder), digit_t(div), digit_t(next_rem));
 131                 //Debug("Sign is %d", next_rem.m_sign);
 132                 remainder = next_rem;
 133                 result += 1L;
 134         }
 135
 136
 137 }
 138
 139 Arbint & Arbint::operator+=(const Arbint & add)
 140 {
 141         if (m_sign == add.m_sign)
 142         {
 143                 // -a + -b == -(a + b)
 144                 return AddBasic(add);
 145         }
 146
 147         if (m_sign)
 148         {
 149                 // -a + b == -(a - b)
 150                 m_sign = false;
 151                 SubBasic(add);
 152                 m_sign = !m_sign;
 153         }
 154         else
 155         {
 156                 // a + -b == a - b
 157                 SubBasic(add);
 158         }
 159         return *this;
 160 }
 161
 162 Arbint & Arbint::operator-=(const Arbint & sub)
 163 {
 164         if (m_sign == sub.m_sign)
 165                 return SubBasic(sub);
 166         return AddBasic(sub);
 167 }
 168
 169 Arbint & Arbint::AddBasic(const Arbint & add)
 170 {
 171         if (add.m_digits.size() >= m_digits.size())
 172         {
 173                 m_digits.resize(add.m_digits.size()+1,0L);
 174         }
 175
 176         digit_t carry = add_digits((digit_t*)m_digits.data(),
 177                         (digit_t*)add.m_digits.data(), add.m_digits.size());
 178         if (carry != 0L)
 179                 m_digits[m_digits.size()-1] = carry;
 180         else if (m_digits.back() == 0L)
 181                 m_digits.resize(m_digits.size()-1);
 182         return *this;
 183 }
 184
 185 Arbint & Arbint::SubBasic(const Arbint & sub)
 186 {
 187         if (sub.m_digits.size() >= m_digits.size())
 188         {
 189                 m_digits.resize(sub.m_digits.size(),0L);
 190         }
 191         digit_t borrow = sub_digits((digit_t*)m_digits.data(),
 192                         (digit_t*)sub.m_digits.data(), sub.m_digits.size());
 193
 194
 195         //TODO: Write ASM to do this bit?
 196         if (borrow != 0L)
 197         {
 198                 m_sign = !m_sign;
 199                 for (unsigned i = 0; i < m_digits.size(); ++i)
 200                         m_digits[i] = -m_digits[i];
 201         }
 202         return *this;
 203 }
 204
 205
 206 string Arbint::Str(const string & base) const
 207 {
 208         string s("");
 209         for (unsigned i = 0; i < m_digits.size(); ++i)
 210         {
 211                 digit_t w = m_digits[i];
 212                 do
 213                 {
 214                         digit_t q = w % 10;
 215                         w /= 10;
 216                         s += ('0' + q);
 217                 }
 218                 while (w > 0);
 219                 if (i+1 < m_digits.size()) s += ",";
 220         }
 221         reverse(s.begin(), s.end());
 222         return s;
 223 }
 224
 225 bool Arbint::IsZero() const
 226 {
 227         for (unsigned i = m_digits.size()-1; i > 0; --i)
 228         {
 229                 if (m_digits[i] != 0L) return false;
 230         }
 231         return (m_digits[0] == 0L);
 232 }
 233
 234 bool Arbint::operator==(const Arbint & equ) const
 235 {
 236         if (m_sign != equ.m_sign)
 237                 return false;
 238         unsigned min_size = m_digits.size();
 239         const Arbint * larger = &equ;
 240         if (m_digits.size() > equ.m_digits.size())
 241         {
 242                 min_size = equ.m_digits.size();
 243                 larger = this;
 244         }
 245
 246         if (memcmp(m_digits.data(), equ.m_digits.data(), sizeof(digit_t)*min_size) != 0)
 247                 return false;
 248
 249         for (unsigned i = min_size; i < larger->m_digits.size(); ++i)
 250         {
 251                 if (larger->m_digits[i] != 0L)
 252                         return false;
 253         }
 254         return true;
 255 }
 256
 257 bool Arbint::operator<(const Arbint & less) const
 258 {
 259         Arbint cpy(*this);
 260         cpy -= less;
 261         return (cpy.m_sign && !cpy.IsZero());
 262 }
 263
 264 string Arbint::DigitStr() const
 265 {
 266         stringstream ss("");
 267         ss << std::hex << std::setfill('0');
 268         for (unsigned i = 0; i < m_digits.size(); ++i)
 269         {
 270                 if (i != 0) ss << ',';
 271                 ss << std::setw(2*sizeof(digit_t)) << static_cast<digit_t>(m_digits[i]);
 272         }
 273         return ss.str();
 274 }
 275
 276 }