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