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(int64_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         remainder = 0;
 112         result = 0;
 113         for (int i = 8*sizeof(digit_t)*m_digits.size(); i >= 0; --i)
 114         {
 115                 remainder <<= 1;
 116                 if (GetBit(i))
 117                         remainder.BitSet(0);
 118                 else
 119                         remainder.BitClear(0);
 120                 if (remainder >= div)
 121                 {
 122                         remainder -= div;
 123                         result.BitSet(i);
 124                 }
 125         }
 126 }
 127
 128 Arbint & Arbint::operator+=(const Arbint & add)
 129 {
 130         if (m_sign == add.m_sign)
 131         {
 132                 // -a + -b == -(a + b)
 133                 return AddBasic(add);
 134         }
 135
 136         if (m_sign)
 137         {
 138                 // -a + b == -(a - b)
 139                 m_sign = false;
 140                 SubBasic(add);
 141                 m_sign = !m_sign;
 142         }
 143         else
 144         {
 145                 // a + -b == a - b
 146                 SubBasic(add);
 147         }
 148         return *this;
 149 }
 150
 151 Arbint & Arbint::operator-=(const Arbint & sub)
 152 {
 153         if (m_sign == sub.m_sign)
 154                 return SubBasic(sub);
 155         return AddBasic(sub);
 156 }
 157
 158 Arbint & Arbint::AddBasic(const Arbint & add)
 159 {
 160         if (add.m_digits.size() >= m_digits.size())
 161         {
 162                 m_digits.resize(add.m_digits.size()+1,0L);
 163         }
 164
 165         digit_t carry = add_digits((digit_t*)m_digits.data(),
 166                         (digit_t*)add.m_digits.data(), add.m_digits.size());
 167         if (carry != 0L)
 168                 m_digits[m_digits.size()-1] = carry;
 169         else if (m_digits.back() == 0L)
 170                 m_digits.resize(m_digits.size()-1);
 171         return *this;
 172 }
 173
 174 Arbint & Arbint::SubBasic(const Arbint & sub)
 175 {
 176         if (sub.m_digits.size() >= m_digits.size())
 177         {
 178                 m_digits.resize(sub.m_digits.size(),0L);
 179         }
 180         digit_t borrow = sub_digits((digit_t*)m_digits.data(),
 181                         (digit_t*)sub.m_digits.data(), sub.m_digits.size());
 182
 183
 184         //TODO: Write ASM to do this bit?
 185         if (borrow != 0L)
 186         {
 187                 m_sign = !m_sign;
 188                 for (unsigned i = 0; i < m_digits.size(); ++i)
 189                         m_digits[i] = -m_digits[i];
 190         }
 191         return *this;
 192 }
 193
 194
 195 string Arbint::Str(const string & base) const
 196 {
 197         string s("");
 198         Arbint cpy(*this);
 199
 200         reverse(s.begin(), s.end());
 201         return s;
 202 }
 203
 204 bool Arbint::IsZero() const
 205 {
 206         for (unsigned i = m_digits.size()-1; i > 0; --i)
 207         {
 208                 if (m_digits[i] != 0L) return false;
 209         }
 210         return (m_digits[0] == 0L);
 211 }
 212
 213 bool Arbint::operator==(const Arbint & equ) const
 214 {
 215         if (m_sign != equ.m_sign)
 216                 return false;
 217         unsigned min_size = m_digits.size();
 218         const Arbint * larger = &equ;
 219         if (m_digits.size() > equ.m_digits.size())
 220         {
 221                 min_size = equ.m_digits.size();
 222                 larger = this;
 223         }
 224
 225         if (memcmp(m_digits.data(), equ.m_digits.data(), sizeof(digit_t)*min_size) != 0)
 226                 return false;
 227
 228         for (unsigned i = min_size; i < larger->m_digits.size(); ++i)
 229         {
 230                 if (larger->m_digits[i] != 0L)
 231                         return false;
 232         }
 233         return true;
 234 }
 235
 236 bool Arbint::operator<(const Arbint & less) const
 237 {
 238         Arbint cpy(*this);
 239         cpy -= less;
 240         return (cpy.m_sign && !cpy.IsZero());
 241 }
 242
 243 string Arbint::DigitStr() const
 244 {
 245         stringstream ss("");
 246         //ss << std::hex << std::setfill('0');
 247         for (unsigned i = 0; i < m_digits.size(); ++i)
 248         {
 249                 if (i != 0) ss << ',';
 250                 //ss << std::setw(2*sizeof(digit_t)) << static_cast<digit_t>(m_digits[i]);
 251                 ss << static_cast<digit_t>(m_digits[i]);
 252         }
 253         return ss.str();
 254 }
 255
 256 Arbint & Arbint::operator>>=(unsigned amount)
 257 {
 258         // Shift by whole number of digits
 259         unsigned whole = amount/(8*sizeof(digit_t));
 260         unsigned old_size = m_digits.size();
 261
 262         if (whole >= old_size)
 263         {
 264                 m_digits.resize(1);
 265                 m_digits[0] = 0L;
 266                 return *this;
 267         }
 268         memmove(m_digits.data(), m_digits.data()+whole, sizeof(digit_t)*(old_size-whole));
 269         m_digits.resize(old_size-whole, 0L);
 270
 271         // Shift by partial amount
 272         amount = amount %(8*sizeof(digit_t));
 273         if (amount == 0)
 274                 return *this;
 275
 276         digit_t underflow = 0L;
 277         for (int i = (int)(m_digits.size()-1); i >= 0; --i)
 278         {
 279                 unsigned shl = (8*sizeof(digit_t)-amount);
 280                 digit_t next_underflow = (m_digits[i] << shl);
 281                 //digit_t mask_upper = ~(0L >> amount);
 282                 m_digits[i] = (m_digits[i] >> amount);// & mask_upper;
 283                 m_digits[i] |= underflow;
 284                 underflow = next_underflow;
 285         }
 286         return *this;
 287 }
 288
 289 Arbint & Arbint::operator<<=(unsigned amount)
 290 {
 291         // Shift by whole number of digits
 292         unsigned whole = amount/(8*sizeof(digit_t));
 293         unsigned old_size = m_digits.size();
 294         m_digits.resize(m_digits.size() + whole);
 295         memmove(m_digits.data()+whole, m_digits.data(), sizeof(digit_t)*old_size);
 296         memset(m_digits.data(), 0L, whole*sizeof(digit_t));
 297
 298
 299
 300         // Partial shifting
 301         amount = amount % (8*sizeof(digit_t));
 302         if (amount == 0)
 303                 return *this;
 304
 305         //Debug("Shift by %u from %u", amount, whole);
 306         digit_t overflow = 0L;
 307         for (unsigned i = whole; i < m_digits.size(); ++i)
 308         {
 309                 //Debug("Digit is %.16lx", m_digits[i]);
 310                 unsigned shr = (8*sizeof(digit_t)-amount);
 311                 //Debug("shr is %u", shr);
 312                 digit_t next_overflow = (m_digits[i] >> shr);
 313                 //Debug("Next overflow %.16lx", next_overflow);
 314                 m_digits[i] <<= amount;
 315                 //Debug("Before overflow %.16lx", m_digits[i]);
 316                 m_digits[i] |= overflow;
 317                 overflow = next_overflow;
 318         }
 319         if (overflow != 0L)
 320                 m_digits.push_back(overflow);
 321
 322         return *this;
 323 }
 324
 325 bool Arbint::GetBit(unsigned i) const
 326 {
 327         unsigned digit = i/(8*sizeof(digit_t));
 328         if (digit > m_digits.size())
 329                 return false;
 330
 331         i = i % (8*sizeof(digit_t));
 332
 333         return (m_digits[digit] & (1L << i));
 334
 335 }
 336
 337 void Arbint::BitClear(unsigned i)
 338 {
 339         unsigned digit = i/(8*sizeof(digit_t));
 340         if (digit > m_digits.size())
 341                 return;
 342         i = i % (8*sizeof(digit_t));
 343         m_digits[digit] &= ~(1L << i);
 344 }
 345
 346 void Arbint::BitSet(unsigned i)
 347 {
 348         unsigned digit = i/(8*sizeof(digit_t));
 349         if (digit > m_digits.size())
 350         {
 351                 m_digits.resize(digit+1, 0L);
 352         }
 353         i = i % (8*sizeof(digit_t));
 354         m_digits[digit] |= (1L << i);
 355 }
 356
 357 }