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 #include "rational.h"
  21
  22 using namespace std;
  23
  24 namespace IPDF
  25 {
  26
  27 /** Absolute value hackery **/
  28 template <> Arbint Tabs(const Arbint & a)
  29 {
  30         //Debug("Called");
  31         return a.Abs();
  32 }
  33
  34
  35 Arbint::Arbint(int64_t i) : m_digits(1), m_sign(i < 0)
  36 {
  37         m_digits[0] = llabs(i);
  38 }
  39
  40 Arbint::Arbint(unsigned n, digit_t d0, ...) : m_digits(n), m_sign(false)
  41 {
  42         va_list ap;
  43         va_start(ap, d0);
  44         if (n >= 1)
  45                 m_digits[0] = d0;
  46         for (unsigned i = 1; i < n; ++i)
  47         {
  48                 m_digits[i] = va_arg(ap, digit_t);
  49         }
  50         va_end(ap);
  51 }
  52
  53 Arbint::Arbint(const Arbint & cpy) : m_digits(cpy.m_digits), m_sign(cpy.m_sign)
  54 {
  55
  56 }
  57
  58 Arbint::Arbint(const vector<digit_t> & digits) : m_digits(digits), m_sign(false)
  59 {
  60
  61 }
  62
  63 Arbint & Arbint::operator=(const Arbint & cpy)
  64 {
  65         m_digits = cpy.m_digits;
  66         m_sign = cpy.m_sign;
  67         return *this;
  68 }
  69
  70 void Arbint::Zero()
  71 {
  72         m_digits.resize(1, 0L);
  73 }
  74
  75 unsigned Arbint::Shrink()
  76 {
  77
  78         if (m_digits.size() <= 1)
  79                 return 0;
  80
  81         unsigned shrunk = 0;
  82         while (m_digits.size() > 1 && m_digits[m_digits.size()-1] == 0L)
  83         {
  84                 Debug("Shrink 1");
  85                 m_digits.pop_back();
  86                 shrunk++;
  87         }
  88         return shrunk;
  89 }
  90
  91 void Arbint::GrowDigit(digit_t new_msd)
  92 {
  93         static unsigned total_grows = 0;
  94         m_digits.push_back(new_msd);
  95         Warn("Arbint grows digit (%.16lx), this->m_digits.size() = %u, total grown = %u", new_msd, m_digits.size(), ++total_grows);
  96         if (total_grows++ > 10000)
  97         {
  98                 Fatal("Too many GrowDigit calls!");
  99         }
 100 }
 101
 102 Arbint & Arbint::operator*=(const Arbint & mul)
 103 {
 104         vector<digit_t> new_digits(m_digits.size(), 0L);
 105         new_digits.reserve(new_digits.size()+mul.m_digits.size());
 106         for (unsigned i = 0; i < mul.m_digits.size(); ++i)
 107         {
 108                 vector<digit_t> step(m_digits.size()+i, 0L);
 109                 memcpy(step.data()+i, m_digits.data(), sizeof(digit_t)*m_digits.size());
 110
 111                 digit_t overflow = mul_digits((digit_t*)step.data()+i, mul.m_digits[i], m_digits.size());
 112                 if (overflow != 0L)
 113                 {
 114                         step.push_back(overflow);
 115                 }
 116                 new_digits.resize(max(new_digits.size(), step.size()), 0L);
 117                 digit_t carry = add_digits((digit_t*)new_digits.data(), step.data(), step.size());
 118                 if (carry != 0L)
 119                 {
 120                         Debug("Add carry");
 121                         GrowDigit(carry);
 122                 }
 123         }
 124
 125         m_digits.swap(new_digits);
 126         m_sign = !(m_sign == mul.m_sign);
 127         Shrink();
 128         return *this;
 129 }
 130
 131 void Arbint::Division(const Arbint & div, Arbint & result, Arbint & remainder) const
 132 {
 133         remainder = 0;
 134         result = 0;
 135         if (div.IsZero())
 136         {
 137                 result = *this;
 138                 return;
 139         }
 140         /* may break things (even more that is)
 141         else if (div.m_digits.size() == 1)
 142         {
 143                 result.m_digits.resize(m_digits.size(), 0L);
 144                 remainder = Arbint(div_digits((digit_t*)&m_digits[0], div.m_digits[0], m_digits.size(), result.m_digits.data()));
 145                 result.m_sign = !(m_sign == div.m_sign);
 146                 return;
 147         } */
 148
 149         for (int i = 8*sizeof(digit_t)*m_digits.size(); i >= 0; --i)
 150         {
 151                 remainder <<= 1;
 152                 if (GetBit(i))
 153                         remainder.BitSet(0);
 154                 else
 155                         remainder.BitClear(0);
 156                 if (remainder >= div)
 157                 {
 158                         remainder -= div;
 159                         result.BitSet(i);
 160                 }
 161         }
 162         result.m_sign = !(m_sign == div.m_sign);
 163         result.Shrink();
 164 }
 165
 166 Arbint & Arbint::operator+=(const Arbint & add)
 167 {
 168         if (m_sign == add.m_sign)
 169         {
 170                 // -a + -b == -(a + b)
 171                 return AddBasic(add);
 172         }
 173
 174         if (m_sign)
 175         {
 176                 // -a + b == -(a - b)
 177                 m_sign = false;
 178                 SubBasic(add);
 179                 m_sign = !m_sign;
 180         }
 181         else
 182         {
 183                 // a + -b == a - b
 184                 SubBasic(add);
 185         }
 186         Shrink();
 187         return *this;
 188 }
 189
 190 Arbint & Arbint::operator-=(const Arbint & sub)
 191 {
 192         if (m_sign == sub.m_sign)
 193                 return SubBasic(sub);
 194         return AddBasic(sub);
 195 }
 196
 197 Arbint & Arbint::AddBasic(const Arbint & add)
 198 {
 199         while (m_digits.size() < add.m_digits.size())
 200         {
 201
 202                 Debug("Size is %u, add's size is %u", m_digits.size(), add.m_digits.size());
 203                 GrowDigit(0L);
 204         }
 205         //m_digits.resize(add.m_digits.size()+1,0L);
 206
 207         digit_t carry = add_digits((digit_t*)m_digits.data(),
 208                         (digit_t*)add.m_digits.data(), add.m_digits.size());
 209         if (carry != 0L)
 210         {
 211                 Debug("Grow carry %lu", carry);
 212                 GrowDigit(carry);
 213         }
 214         Shrink();
 215         return *this;
 216 }
 217
 218 Arbint & Arbint::SubBasic(const Arbint & sub)
 219 {
 220         bool fith = false;
 221         while (sub.m_digits.size() > m_digits.size())
 222         {
 223                 fith = true;
 224                 GrowDigit(0L);
 225         }
 226         if (fith)
 227         {
 228                 Debug("START sub was %c%s, I am %c%s", SignChar(), sub.DigitStr().c_str(), SignChar(), DigitStr().c_str());
 229         }
 230
 231         digit_t borrow = sub_digits((digit_t*)m_digits.data(),
 232                         (digit_t*)sub.m_digits.data(), sub.m_digits.size());
 233
 234         if (fith)
 235         {
 236                 Debug("SUB_DIGITS -> sub was %c%s, I am %c%s", SignChar(), sub.DigitStr().c_str(), SignChar(), DigitStr().c_str());
 237         }
 238
 239         //TODO: Write ASM to do this bit?
 240         if (borrow != 0L)
 241         {
 242                 m_sign = !m_sign;
 243                 for (unsigned i = 0; i < m_digits.size(); ++i)
 244                         m_digits[i] = (~m_digits[i]);
 245                 vector<digit_t> one_digits(m_digits.size(), 0L);
 246                 one_digits[0] = 1L;
 247                 add_digits((digit_t*)m_digits.data(), (digit_t*)one_digits.data(), m_digits.size());
 248         }
 249         if (fith)
 250         {
 251                 Debug("END -> sub was %c%s, I am %c%s", sub.SignChar(), sub.DigitStr().c_str(), SignChar(), DigitStr().c_str());
 252         }
 253         Shrink();
 254         if (fith)
 255         {
 256                 Debug("SHRUNK -> sub was %c%s, I am %c%s", sub.SignChar(), sub.DigitStr().c_str(), SignChar(), DigitStr().c_str());
 257         }
 258         return *this;
 259 }
 260
 261
 262 string Arbint::Str(const string & base) const
 263 {
 264         string s("");
 265         Arbint cpy(*this);
 266
 267         reverse(s.begin(), s.end());
 268         return s;
 269 }
 270
 271 bool Arbint::IsZero() const
 272 {
 273         for (unsigned i = m_digits.size()-1; i > 0; --i)
 274         {
 275                 if (m_digits[i] != 0L) return false;
 276         }
 277         return (m_digits[0] == 0L);
 278 }
 279
 280 bool Arbint::operator==(const Arbint & equ) const
 281 {
 282         if (m_sign != equ.m_sign)
 283                 return false;
 284         unsigned min_size = m_digits.size();
 285         const Arbint * larger = &equ;
 286         if (m_digits.size() > equ.m_digits.size())
 287         {
 288                 min_size = equ.m_digits.size();
 289                 larger = this;
 290         }
 291
 292         if (memcmp(m_digits.data(), equ.m_digits.data(), sizeof(digit_t)*min_size) != 0)
 293                 return false;
 294
 295         for (unsigned i = min_size; i < larger->m_digits.size(); ++i)
 296         {
 297                 if (larger->m_digits[i] != 0L)
 298                         return false;
 299         }
 300         return true;
 301 }
 302
 303 bool Arbint::operator<(const Arbint & less) const
 304 {
 305         Arbint cpy(*this);
 306         cpy -= less;
 307         return (cpy.m_sign && !cpy.IsZero());
 308 }
 309
 310 string Arbint::DigitStr() const
 311 {
 312         stringstream ss("");
 313         //ss << std::hex << std::setfill('0');
 314         for (unsigned i = 0; i < m_digits.size(); ++i)
 315         {
 316                 if (i != 0) ss << ',';
 317                 //ss << std::setw(2*sizeof(digit_t)) << static_cast<digit_t>(m_digits[i]);
 318                 ss << static_cast<digit_t>(m_digits[i]);
 319         }
 320         return ss.str();
 321 }
 322
 323 Arbint & Arbint::operator>>=(unsigned amount)
 324 {
 325         // Shift by whole number of digits
 326         unsigned whole = amount/(8*sizeof(digit_t));
 327         unsigned old_size = m_digits.size();
 328
 329         if (whole >= old_size)
 330         {
 331                 m_digits.resize(1,0L);
 332                 m_digits[0] = 0L;
 333                 return *this;
 334         }
 335         memmove(m_digits.data(), m_digits.data()+whole, sizeof(digit_t)*(old_size-whole));
 336         m_digits.resize(old_size-whole, 0L);
 337
 338         // Shift by partial amount
 339         amount = amount %(8*sizeof(digit_t));
 340         if (amount == 0)
 341                 return *this;
 342
 343         digit_t underflow = 0L;
 344         for (int i = (int)(m_digits.size()-1); i >= 0; --i)
 345         {
 346                 unsigned shl = (8*sizeof(digit_t)-amount);
 347                 digit_t next_underflow = (m_digits[i] << shl);
 348                 //digit_t mask_upper = ~(0L >> amount);
 349                 m_digits[i] = (m_digits[i] >> amount);// & mask_upper;
 350                 m_digits[i] |= underflow;
 351                 underflow = next_underflow;
 352         }
 353         Shrink();
 354         return *this;
 355 }
 356
 357 Arbint & Arbint::operator<<=(unsigned amount)
 358 {
 359         // Shift by whole number of digits
 360         unsigned whole = amount/(8*sizeof(digit_t));
 361         unsigned old_size = m_digits.size();
 362         for (unsigned i = 0; i < whole; ++i)
 363         {
 364
 365                 GrowDigit(0L);//m_digits.resize(m_digits.size() + whole);
 366         }
 367         memmove(m_digits.data()+whole, m_digits.data(), sizeof(digit_t)*old_size);
 368         memset(m_digits.data(), 0L, whole*sizeof(digit_t));
 369
 370
 371
 372         // Partial shifting
 373         amount = amount % (8*sizeof(digit_t));
 374         if (amount == 0)
 375                 return *this;
 376
 377         //Debug("Shift by %u from %u", amount, whole);
 378         digit_t overflow = 0L;
 379         for (unsigned i = whole; i < m_digits.size(); ++i)
 380         {
 381                 //Debug("Digit is %.16lx", m_digits[i]);
 382                 unsigned shr = (8*sizeof(digit_t)-amount);
 383                 //Debug("shr is %u", shr);
 384                 digit_t next_overflow = (m_digits[i] >> shr);
 385                 //Debug("Next overflow %.16lx", next_overflow);
 386                 m_digits[i] <<= amount;
 387                 //Debug("Before overflow %.16lx", m_digits[i]);
 388                 m_digits[i] |= overflow;
 389                 overflow = next_overflow;
 390         }
 391         if (overflow != 0L)
 392                 m_digits.push_back(overflow);
 393         Shrink();
 394         return *this;
 395 }
 396
 397 bool Arbint::GetBit(unsigned i) const
 398 {
 399         unsigned digit = i/(8*sizeof(digit_t));
 400         if (digit >= m_digits.size())
 401                 return false;
 402
 403         i = i % (8*sizeof(digit_t));
 404
 405         return (m_digits[digit] & (1L << i));
 406
 407 }
 408
 409 void Arbint::BitClear(unsigned i)
 410 {
 411         unsigned digit = i/(8*sizeof(digit_t));
 412         if (digit >= m_digits.size())
 413                 return;
 414         i = i % (8*sizeof(digit_t));
 415         m_digits[digit] &= ~(1L << i);
 416 }
 417
 418 void Arbint::BitSet(unsigned i)
 419 {
 420         unsigned digit = i/(8*sizeof(digit_t));
 421         while (m_digits.size() < digit+1)
 422         {
 423                 Debug("Grow BitSet Size %u, digit %u", m_digits.size(), digit);
 424                 GrowDigit(0L);
 425         }
 426
 427         i = i % (8*sizeof(digit_t));
 428         m_digits[digit] |= (1L << i);
 429 }
 430
 431 }