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