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         static unsigned biggest_arbint = 1;
  95         m_digits.push_back(new_msd);
  96         total_grows++;
  97         if (m_digits.size() > biggest_arbint)
  98         {
  99                 biggest_arbint = m_digits.size();
 100                 Warn("New biggest Arbint of size %u", m_digits.size());
 101         }
 102         //Warn("Arbint grows digit (%.16lx), this->m_digits.size() = %u, total grown = %u", new_msd, m_digits.size(), ++total_grows);
 103         //if (total_grows++ > 10000)
 104         //{
 105         //      Fatal("Too many GrowDigit calls!");
 106         //}
 107 }
 108
 109 Arbint & Arbint::operator*=(const Arbint & mul)
 110 {
 111         vector<digit_t> new_digits(m_digits.size(), 0L);
 112         new_digits.reserve(new_digits.size()+mul.m_digits.size());
 113         for (unsigned i = 0; i < mul.m_digits.size(); ++i)
 114         {
 115                 vector<digit_t> step(m_digits.size()+i, 0L);
 116                 memcpy(step.data()+i, m_digits.data(), sizeof(digit_t)*m_digits.size());
 117
 118                 digit_t overflow = mul_digits((digit_t*)step.data()+i, mul.m_digits[i], m_digits.size());
 119                 if (overflow != 0L)
 120                 {
 121                         step.push_back(overflow);
 122                 }
 123                 new_digits.resize(max(new_digits.size(), step.size()), 0L);
 124                 digit_t carry = add_digits((digit_t*)new_digits.data(), step.data(), step.size());
 125                 if (carry != 0L)
 126                 {
 127                         Debug("Add carry");
 128                         GrowDigit(carry);
 129                 }
 130         }
 131
 132         m_digits.swap(new_digits);
 133         m_sign = !(m_sign == mul.m_sign);
 134         Shrink();
 135         return *this;
 136 }
 137
 138 void Arbint::Division(const Arbint & div, Arbint & result, Arbint & remainder) const
 139 {
 140         remainder = 0;
 141         result = 0;
 142         if (div.IsZero())
 143         {
 144                 result = *this;
 145                 return;
 146         }
 147         /* may break things (even more that is)
 148         else if (div.m_digits.size() == 1)
 149         {
 150                 result.m_digits.resize(m_digits.size(), 0L);
 151                 remainder = Arbint(div_digits((digit_t*)&m_digits[0], div.m_digits[0], m_digits.size(), result.m_digits.data()));
 152                 result.m_sign = !(m_sign == div.m_sign);
 153                 return;
 154         } */
 155
 156         for (int i = 8*sizeof(digit_t)*m_digits.size(); i >= 0; --i)
 157         {
 158                 remainder <<= 1;
 159                 if (GetBit(i))
 160                         remainder.BitSet(0);
 161                 else
 162                         remainder.BitClear(0);
 163                 if (remainder >= div)
 164                 {
 165                         remainder -= div;
 166                         result.BitSet(i);
 167                 }
 168         }
 169         result.m_sign = !(m_sign == div.m_sign);
 170         result.Shrink();
 171 }
 172
 173 Arbint & Arbint::operator+=(const Arbint & add)
 174 {
 175         if (m_sign == add.m_sign)
 176         {
 177                 // -a + -b == -(a + b)
 178                 return AddBasic(add);
 179         }
 180
 181         if (m_sign)
 182         {
 183                 // -a + b == -(a - b)
 184                 m_sign = false;
 185                 SubBasic(add);
 186                 m_sign = !m_sign;
 187         }
 188         else
 189         {
 190                 // a + -b == a - b
 191                 SubBasic(add);
 192         }
 193         Shrink();
 194         return *this;
 195 }
 196
 197 Arbint & Arbint::operator-=(const Arbint & sub)
 198 {
 199         if (m_sign == sub.m_sign)
 200                 return SubBasic(sub);
 201         return AddBasic(sub);
 202 }
 203
 204 Arbint & Arbint::AddBasic(const Arbint & add)
 205 {
 206         // Add any leading zeros to this number
 207         while (m_digits.size() < add.m_digits.size())
 208         {
 209                 GrowDigit(0L);
 210         }
 211         //m_digits.resize(add.m_digits.size()+1,0L);
 212
 213         digit_t carry = add_digits((digit_t*)m_digits.data(),
 214                         (digit_t*)add.m_digits.data(), add.m_digits.size());
 215
 216         // This number had more digits but there is a carry left over
 217         if (carry != 0L && m_digits.size() > add.m_digits.size())
 218         {
 219                 vector<digit_t> carry_digits(m_digits.size() - add.m_digits.size(), 0L);
 220                 carry_digits[0] = carry;
 221                 carry = add_digits((digit_t*)m_digits.data()+add.m_digits.size(),
 222                         (digit_t*)carry_digits.data(), m_digits.size()-add.m_digits.size());
 223         }
 224
 225         // There is still a carry left over
 226         if (carry != 0L)
 227         {
 228                 GrowDigit(carry);
 229         }
 230         Shrink();
 231         return *this;
 232 }
 233
 234 Arbint & Arbint::SubBasic(const Arbint & sub)
 235 {
 236         // Add leading zeros
 237         while (sub.m_digits.size() > m_digits.size())
 238         {
 239                 GrowDigit(0L);
 240         }
 241
 242         // Do subtraction on digits
 243         digit_t borrow = sub_digits((digit_t*)m_digits.data(),
 244                         (digit_t*)sub.m_digits.data(), sub.m_digits.size());
 245
 246         // This number had more digits but there is a borrow left over
 247         if (borrow != 0L && m_digits.size() > sub.m_digits.size())
 248         {
 249                 vector<digit_t> borrow_digits(m_digits.size()-sub.m_digits.size(), 0L);
 250                 borrow_digits[0] = borrow;
 251                 borrow = sub_digits((digit_t*)m_digits.data()+sub.m_digits.size(),
 252                         (digit_t*)borrow_digits.data(), m_digits.size()-sub.m_digits.size());
 253         }
 254
 255         // borrow is still set => number is negative
 256         if (borrow != 0L)
 257         {
 258                 m_sign = !m_sign;
 259                 for (unsigned i = 0; i < m_digits.size(); ++i)
 260                         m_digits[i] = (~m_digits[i]);
 261                 vector<digit_t> one_digits(m_digits.size(), 0L);
 262                 one_digits[0] = 1L;
 263                 add_digits((digit_t*)m_digits.data(), (digit_t*)one_digits.data(), m_digits.size());
 264         }
 265         Shrink();
 266         return *this;
 267 }
 268
 269
 270 string Arbint::Str(const string & base) const
 271 {
 272         string s("");
 273         Arbint cpy(*this);
 274         unsigned b = base.size();
 275         while (cpy > Arbint(0L))
 276         {
 277                 //Debug("cpy is %s", cpy.DigitStr().c_str());
 278                 unsigned c = (unsigned)(cpy % Arbint(b)).AsDigit();
 279                 s += base[c];
 280                 cpy /= Arbint(b);
 281         }
 282         if (m_sign)
 283                 s += '-';
 284         reverse(s.begin(), s.end());
 285         return s;
 286 }
 287
 288 bool Arbint::IsZero() const
 289 {
 290         for (unsigned i = m_digits.size()-1; i > 0; --i)
 291         {
 292                 if (m_digits[i] != 0L) return false;
 293         }
 294         return (m_digits[0] == 0L);
 295 }
 296
 297 bool Arbint::operator==(const Arbint & equ) const
 298 {
 299         if (m_sign != equ.m_sign)
 300                 return false;
 301         unsigned min_size = m_digits.size();
 302         const Arbint * larger = &equ;
 303         if (m_digits.size() > equ.m_digits.size())
 304         {
 305                 min_size = equ.m_digits.size();
 306                 larger = this;
 307         }
 308
 309         if (memcmp(m_digits.data(), equ.m_digits.data(), sizeof(digit_t)*min_size) != 0)
 310                 return false;
 311
 312         for (unsigned i = min_size; i < larger->m_digits.size(); ++i)
 313         {
 314                 if (larger->m_digits[i] != 0L)
 315                         return false;
 316         }
 317         return true;
 318 }
 319
 320 bool Arbint::operator<(const Arbint & less) const
 321 {
 322         Arbint cpy(*this);
 323         cpy -= less;
 324         return (cpy.m_sign && !cpy.IsZero());
 325 }
 326
 327 string Arbint::DigitStr() const
 328 {
 329         stringstream ss("");
 330         //ss << std::hex << std::setfill('0');
 331         for (unsigned i = 0; i < m_digits.size(); ++i)
 332         {
 333                 if (i != 0) ss << ',';
 334                 //ss << std::setw(2*sizeof(digit_t)) << static_cast<digit_t>(m_digits[i]);
 335                 ss << static_cast<digit_t>(m_digits[i]);
 336         }
 337         return ss.str();
 338 }
 339
 340 Arbint & Arbint::operator>>=(unsigned amount)
 341 {
 342         // Shift by whole number of digits
 343         unsigned whole = amount/(8*sizeof(digit_t));
 344         unsigned old_size = m_digits.size();
 345
 346         if (whole >= old_size)
 347         {
 348                 m_digits.resize(1,0L);
 349                 m_digits[0] = 0L;
 350                 return *this;
 351         }
 352         memmove(m_digits.data(), m_digits.data()+whole, sizeof(digit_t)*(old_size-whole));
 353         m_digits.resize(old_size-whole, 0L);
 354
 355         // Shift by partial amount
 356         amount = amount %(8*sizeof(digit_t));
 357         if (amount == 0)
 358                 return *this;
 359
 360         digit_t underflow = 0L;
 361         for (int i = (int)(m_digits.size()-1); i >= 0; --i)
 362         {
 363                 unsigned shl = (8*sizeof(digit_t)-amount);
 364                 digit_t next_underflow = (m_digits[i] << shl);
 365                 //digit_t mask_upper = ~(0L >> amount);
 366                 m_digits[i] = (m_digits[i] >> amount);// & mask_upper;
 367                 m_digits[i] |= underflow;
 368                 underflow = next_underflow;
 369         }
 370         Shrink();
 371         return *this;
 372 }
 373
 374 Arbint & Arbint::operator<<=(unsigned amount)
 375 {
 376         // Shift by whole number of digits
 377         unsigned whole = amount/(8*sizeof(digit_t));
 378         unsigned old_size = m_digits.size();
 379         for (unsigned i = 0; i < whole; ++i)
 380         {
 381                 //Debug("i = %u, whole = %u", i, whole);
 382                 GrowDigit(0L);//m_digits.resize(m_digits.size() + whole);
 383         }
 384         memmove(m_digits.data()+whole, m_digits.data(), sizeof(digit_t)*old_size);
 385         memset(m_digits.data(), 0L, whole*sizeof(digit_t));
 386
 387
 388
 389         // Partial shifting
 390         amount = amount % (8*sizeof(digit_t));
 391         if (amount == 0)
 392                 return *this;
 393
 394         //Debug("Shift by %u from %u", amount, whole);
 395         digit_t overflow = 0L;
 396         for (unsigned i = whole; i < m_digits.size(); ++i)
 397         {
 398                 //Debug("Digit is %.16lx", m_digits[i]);
 399                 unsigned shr = (8*sizeof(digit_t)-amount);
 400                 //Debug("shr is %u", shr);
 401                 digit_t next_overflow = (m_digits[i] >> shr);
 402                 //Debug("Next overflow %.16lx", next_overflow);
 403                 m_digits[i] <<= amount;
 404                 //Debug("Before overflow %.16lx", m_digits[i]);
 405                 m_digits[i] |= overflow;
 406                 overflow = next_overflow;
 407         }
 408         if (overflow != 0L)
 409                 m_digits.push_back(overflow);
 410         Shrink();
 411         return *this;
 412 }
 413
 414 bool Arbint::GetBit(unsigned i) const
 415 {
 416         unsigned digit = i/(8*sizeof(digit_t));
 417         if (digit >= m_digits.size())
 418                 return false;
 419
 420         i = i % (8*sizeof(digit_t));
 421
 422         return (m_digits[digit] & (1L << i));
 423
 424 }
 425
 426 void Arbint::BitClear(unsigned i)
 427 {
 428         unsigned digit = i/(8*sizeof(digit_t));
 429         if (digit >= m_digits.size())
 430                 return;
 431         i = i % (8*sizeof(digit_t));
 432         m_digits[digit] &= ~(1L << i);
 433 }
 434
 435 void Arbint::BitSet(unsigned i)
 436 {
 437         unsigned digit = i/(8*sizeof(digit_t));
 438         while (m_digits.size() < digit+1)
 439         {
 440                 //Debug("Grow BitSet Size %u, digit %u", m_digits.size(), digit);
 441                 GrowDigit(0L);
 442         }
 443
 444         i = i % (8*sizeof(digit_t));
 445         m_digits[digit] |= (1L << i);
 446 }
 447
 448 }