src/bignum.h

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2012 The Bitcoin developers
   3 // Distributed under the MIT/X11 software license, see the accompanying
   4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5 #ifndef BITCOIN_BIGNUM_H
   6 #define BITCOIN_BIGNUM_H
   7
   8 #include <stdexcept>
   9 #include <vector>
  10 #include <openssl/bn.h>
  11
  12 #include "util.h" // for uint64
  13
  14 /** Errors thrown by the bignum class */
  15 class bignum_error : public std::runtime_error
  16 {
  17 public:
  18     explicit bignum_error(const std::string& str) : std::runtime_error(str) {}
  19 };
  20
  21
  22 /** RAII encapsulated BN_CTX (OpenSSL bignum context) */
  23 class CAutoBN_CTX
  24 {
  25 protected:
  26     BN_CTX* pctx;
  27     BN_CTX* operator=(BN_CTX* pnew) { return pctx = pnew; }
  28
  29 public:
  30     CAutoBN_CTX()
  31     {
  32         pctx = BN_CTX_new();
  33         if (pctx == NULL)
  34             throw bignum_error("CAutoBN_CTX : BN_CTX_new() returned NULL");
  35     }
  36
  37     ~CAutoBN_CTX()
  38     {
  39         if (pctx != NULL)
  40             BN_CTX_free(pctx);
  41     }
  42
  43     operator BN_CTX*() { return pctx; }
  44     BN_CTX& operator*() { return *pctx; }
  45     BN_CTX** operator&() { return &pctx; }
  46     bool operator!() { return (pctx == NULL); }
  47 };
  48
  49
  50 /** C++ wrapper for BIGNUM (OpenSSL bignum) */
  51 class CBigNum : public BIGNUM
  52 {
  53 public:
  54     CBigNum()
  55     {
  56         BN_init(this);
  57     }
  58
  59     CBigNum(const CBigNum& b)
  60     {
  61         BN_init(this);
  62         if (!BN_copy(this, &b))
  63         {
  64             BN_clear_free(this);
  65             throw bignum_error("CBigNum::CBigNum(const CBigNum&) : BN_copy failed");
  66         }
  67     }
  68
  69     CBigNum& operator=(const CBigNum& b)
  70     {
  71         if (!BN_copy(this, &b))
  72             throw bignum_error("CBigNum::operator= : BN_copy failed");
  73         return (*this);
  74     }
  75
  76     ~CBigNum()
  77     {
  78         BN_clear_free(this);
  79     }
  80
  81     //CBigNum(char n) is not portable.  Use 'signed char' or 'unsigned char'.
  82     CBigNum(signed char n)      { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
  83     CBigNum(short n)            { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
  84     CBigNum(int n)              { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
  85     CBigNum(long n)             { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
  86     CBigNum(int64 n)            { BN_init(this); setint64(n); }
  87     CBigNum(unsigned char n)    { BN_init(this); setulong(n); }
  88     CBigNum(unsigned short n)   { BN_init(this); setulong(n); }
  89     CBigNum(unsigned int n)     { BN_init(this); setulong(n); }
  90     CBigNum(unsigned long n)    { BN_init(this); setulong(n); }
  91     CBigNum(uint64 n)           { BN_init(this); setuint64(n); }
  92     explicit CBigNum(uint256 n) { BN_init(this); setuint256(n); }
  93
  94     explicit CBigNum(const std::vector<unsigned char>& vch)
  95     {
  96         BN_init(this);
  97         setvch(vch);
  98     }
  99
 100     void setulong(unsigned long n)
 101     {
 102         if (!BN_set_word(this, n))
 103             throw bignum_error("CBigNum conversion from unsigned long : BN_set_word failed");
 104     }
 105
 106     unsigned long getulong() const
 107     {
 108         return BN_get_word(this);
 109     }
 110
 111     unsigned int getuint() const
 112     {
 113         return BN_get_word(this);
 114     }
 115
 116     int getint() const
 117     {
 118         unsigned long n = BN_get_word(this);
 119         if (!BN_is_negative(this))
 120             return (n > (unsigned long)std::numeric_limits<int>::max() ? std::numeric_limits<int>::max() : n);
 121         else
 122             return (n > (unsigned long)std::numeric_limits<int>::max() ? std::numeric_limits<int>::min() : -(int)n);
 123     }
 124
 125     void setint64(int64 sn)
 126     {
 127         unsigned char pch[sizeof(sn) + 6];
 128         unsigned char* p = pch + 4;
 129         bool fNegative;
 130         uint64 n;
 131
 132         if (sn < (int64)0)
 133         {
 134             // Since the minimum signed integer cannot be represented as positive so long as its type is signed, and it's not well-defined what happens if you make it unsigned before negating it, we instead increment the negative integer by 1, convert it, then increment the (now positive) unsigned integer by 1 to compensate
 135             n = -(sn + 1);
 136             ++n;
 137             fNegative = true;
 138         } else {
 139             n = sn;
 140             fNegative = false;
 141         }
 142
 143         bool fLeadingZeroes = true;
 144         for (int i = 0; i < 8; i++)
 145         {
 146             unsigned char c = (n >> 56) & 0xff;
 147             n <<= 8;
 148             if (fLeadingZeroes)
 149             {
 150                 if (c == 0)
 151                     continue;
 152                 if (c & 0x80)
 153                     *p++ = (fNegative ? 0x80 : 0);
 154                 else if (fNegative)
 155                     c |= 0x80;
 156                 fLeadingZeroes = false;
 157             }
 158             *p++ = c;
 159         }
 160         unsigned int nSize = p - (pch + 4);
 161         pch[0] = (nSize >> 24) & 0xff;
 162         pch[1] = (nSize >> 16) & 0xff;
 163         pch[2] = (nSize >> 8) & 0xff;
 164         pch[3] = (nSize) & 0xff;
 165         BN_mpi2bn(pch, p - pch, this);
 166     }
 167
 168     void setuint64(uint64 n)
 169     {
 170         unsigned char pch[sizeof(n) + 6];
 171         unsigned char* p = pch + 4;
 172         bool fLeadingZeroes = true;
 173         for (int i = 0; i < 8; i++)
 174         {
 175             unsigned char c = (n >> 56) & 0xff;
 176             n <<= 8;
 177             if (fLeadingZeroes)
 178             {
 179                 if (c == 0)
 180                     continue;
 181                 if (c & 0x80)
 182                     *p++ = 0;
 183                 fLeadingZeroes = false;
 184             }
 185             *p++ = c;
 186         }
 187         unsigned int nSize = p - (pch + 4);
 188         pch[0] = (nSize >> 24) & 0xff;
 189         pch[1] = (nSize >> 16) & 0xff;
 190         pch[2] = (nSize >> 8) & 0xff;
 191         pch[3] = (nSize) & 0xff;
 192         BN_mpi2bn(pch, p - pch, this);
 193     }
 194
 195     void setuint256(uint256 n)
 196     {
 197         unsigned char pch[sizeof(n) + 6];
 198         unsigned char* p = pch + 4;
 199         bool fLeadingZeroes = true;
 200         unsigned char* pbegin = (unsigned char*)&n;
 201         unsigned char* psrc = pbegin + sizeof(n);
 202         while (psrc != pbegin)
 203         {
 204             unsigned char c = *(--psrc);
 205             if (fLeadingZeroes)
 206             {
 207                 if (c == 0)
 208                     continue;
 209                 if (c & 0x80)
 210                     *p++ = 0;
 211                 fLeadingZeroes = false;
 212             }
 213             *p++ = c;
 214         }
 215         unsigned int nSize = p - (pch + 4);
 216         pch[0] = (nSize >> 24) & 0xff;
 217         pch[1] = (nSize >> 16) & 0xff;
 218         pch[2] = (nSize >> 8) & 0xff;
 219         pch[3] = (nSize >> 0) & 0xff;
 220         BN_mpi2bn(pch, p - pch, this);
 221     }
 222
 223     uint256 getuint256()
 224     {
 225         unsigned int nSize = BN_bn2mpi(this, NULL);
 226         if (nSize < 4)
 227             return 0;
 228         std::vector<unsigned char> vch(nSize);
 229         BN_bn2mpi(this, &vch[0]);
 230         if (vch.size() > 4)
 231             vch[4] &= 0x7f;
 232         uint256 n = 0;
 233         for (unsigned int i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
 234             ((unsigned char*)&n)[i] = vch[j];
 235         return n;
 236     }
 237
 238     void setvch(const std::vector<unsigned char>& vch)
 239     {
 240         std::vector<unsigned char> vch2(vch.size() + 4);
 241         unsigned int nSize = vch.size();
 242         // BIGNUM's byte stream format expects 4 bytes of
 243         // big endian size data info at the front
 244         vch2[0] = (nSize >> 24) & 0xff;
 245         vch2[1] = (nSize >> 16) & 0xff;
 246         vch2[2] = (nSize >> 8) & 0xff;
 247         vch2[3] = (nSize >> 0) & 0xff;
 248         // swap data to big endian
 249         reverse_copy(vch.begin(), vch.end(), vch2.begin() + 4);
 250         BN_mpi2bn(&vch2[0], vch2.size(), this);
 251     }
 252
 253     std::vector<unsigned char> getvch() const
 254     {
 255         unsigned int nSize = BN_bn2mpi(this, NULL);
 256         if (nSize <= 4)
 257             return std::vector<unsigned char>();
 258         std::vector<unsigned char> vch(nSize);
 259         BN_bn2mpi(this, &vch[0]);
 260         vch.erase(vch.begin(), vch.begin() + 4);
 261         reverse(vch.begin(), vch.end());
 262         return vch;
 263     }
 264
 265     CBigNum& SetCompact(unsigned int nCompact)
 266     {
 267         unsigned int nSize = nCompact >> 24;
 268         std::vector<unsigned char> vch(4 + nSize);
 269         vch[3] = nSize;
 270         if (nSize >= 1) vch[4] = (nCompact >> 16) & 0xff;
 271         if (nSize >= 2) vch[5] = (nCompact >> 8) & 0xff;
 272         if (nSize >= 3) vch[6] = (nCompact >> 0) & 0xff;
 273         BN_mpi2bn(&vch[0], vch.size(), this);
 274         return *this;
 275     }
 276
 277     unsigned int GetCompact() const
 278     {
 279         unsigned int nSize = BN_bn2mpi(this, NULL);
 280         std::vector<unsigned char> vch(nSize);
 281         nSize -= 4;
 282         BN_bn2mpi(this, &vch[0]);
 283         unsigned int nCompact = nSize << 24;
 284         if (nSize >= 1) nCompact |= (vch[4] << 16);
 285         if (nSize >= 2) nCompact |= (vch[5] << 8);
 286         if (nSize >= 3) nCompact |= (vch[6] << 0);
 287         return nCompact;
 288     }
 289
 290     void SetHex(const std::string& str)
 291     {
 292         // skip 0x
 293         const char* psz = str.c_str();
 294         while (isspace(*psz))
 295             psz++;
 296         bool fNegative = false;
 297         if (*psz == '-')
 298         {
 299             fNegative = true;
 300             psz++;
 301         }
 302         if (psz[0] == '0' && tolower(psz[1]) == 'x')
 303             psz += 2;
 304         while (isspace(*psz))
 305             psz++;
 306
 307         // hex string to bignum
 308         static signed char phexdigit[256] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0 };
 309         *this = 0;
 310         while (isxdigit(*psz))
 311         {
 312             *this <<= 4;
 313             int n = phexdigit[(unsigned char)*psz++];
 314             *this += n;
 315         }
 316         if (fNegative)
 317             *this = 0 - *this;
 318     }
 319
 320     std::string ToString(int nBase=10) const
 321     {
 322         CAutoBN_CTX pctx;
 323         CBigNum bnBase = nBase;
 324         CBigNum bn0 = 0;
 325         std::string str;
 326         CBigNum bn = *this;
 327         BN_set_negative(&bn, false);
 328         CBigNum dv;
 329         CBigNum rem;
 330         if (BN_cmp(&bn, &bn0) == 0)
 331             return "0";
 332         while (BN_cmp(&bn, &bn0) > 0)
 333         {
 334             if (!BN_div(&dv, &rem, &bn, &bnBase, pctx))
 335                 throw bignum_error("CBigNum::ToString() : BN_div failed");
 336             bn = dv;
 337             unsigned int c = rem.getulong();
 338             str += "0123456789abcdef"[c];
 339         }
 340         if (BN_is_negative(this))
 341             str += "-";
 342         reverse(str.begin(), str.end());
 343         return str;
 344     }
 345
 346     std::string GetHex() const
 347     {
 348         return ToString(16);
 349     }
 350
 351     unsigned int GetSerializeSize(int nType=0, int nVersion=PROTOCOL_VERSION) const
 352     {
 353         return ::GetSerializeSize(getvch(), nType, nVersion);
 354     }
 355
 356     template<typename Stream>
 357     void Serialize(Stream& s, int nType=0, int nVersion=PROTOCOL_VERSION) const
 358     {
 359         ::Serialize(s, getvch(), nType, nVersion);
 360     }
 361
 362     template<typename Stream>
 363     void Unserialize(Stream& s, int nType=0, int nVersion=PROTOCOL_VERSION)
 364     {
 365         std::vector<unsigned char> vch;
 366         ::Unserialize(s, vch, nType, nVersion);
 367         setvch(vch);
 368     }
 369
 370
 371     bool operator!() const
 372     {
 373         return BN_is_zero(this);
 374     }
 375
 376     CBigNum& operator+=(const CBigNum& b)
 377     {
 378         if (!BN_add(this, this, &b))
 379             throw bignum_error("CBigNum::operator+= : BN_add failed");
 380         return *this;
 381     }
 382
 383     CBigNum& operator-=(const CBigNum& b)
 384     {
 385         *this = *this - b;
 386         return *this;
 387     }
 388
 389     CBigNum& operator*=(const CBigNum& b)
 390     {
 391         CAutoBN_CTX pctx;
 392         if (!BN_mul(this, this, &b, pctx))
 393             throw bignum_error("CBigNum::operator*= : BN_mul failed");
 394         return *this;
 395     }
 396
 397     CBigNum& operator/=(const CBigNum& b)
 398     {
 399         *this = *this / b;
 400         return *this;
 401     }
 402
 403     CBigNum& operator%=(const CBigNum& b)
 404     {
 405         *this = *this % b;
 406         return *this;
 407     }
 408
 409     CBigNum& operator<<=(unsigned int shift)
 410     {
 411         if (!BN_lshift(this, this, shift))
 412             throw bignum_error("CBigNum:operator<<= : BN_lshift failed");
 413         return *this;
 414     }
 415
 416     CBigNum& operator>>=(unsigned int shift)
 417     {
 418         // Note: BN_rshift segfaults on 64-bit if 2^shift is greater than the number
 419         //   if built on ubuntu 9.04 or 9.10, probably depends on version of OpenSSL
 420         CBigNum a = 1;
 421         a <<= shift;
 422         if (BN_cmp(&a, this) > 0)
 423         {
 424             *this = 0;
 425             return *this;
 426         }
 427
 428         if (!BN_rshift(this, this, shift))
 429             throw bignum_error("CBigNum:operator>>= : BN_rshift failed");
 430         return *this;
 431     }
 432
 433
 434     CBigNum& operator++()
 435     {
 436         // prefix operator
 437         if (!BN_add(this, this, BN_value_one()))
 438             throw bignum_error("CBigNum::operator++ : BN_add failed");
 439         return *this;
 440     }
 441
 442     const CBigNum operator++(int)
 443     {
 444         // postfix operator
 445         const CBigNum ret = *this;
 446         ++(*this);
 447         return ret;
 448     }
 449
 450     CBigNum& operator--()
 451     {
 452         // prefix operator
 453         CBigNum r;
 454         if (!BN_sub(&r, this, BN_value_one()))
 455             throw bignum_error("CBigNum::operator-- : BN_sub failed");
 456         *this = r;
 457         return *this;
 458     }
 459
 460     const CBigNum operator--(int)
 461     {
 462         // postfix operator
 463         const CBigNum ret = *this;
 464         --(*this);
 465         return ret;
 466     }
 467
 468
 469     friend inline const CBigNum operator-(const CBigNum& a, const CBigNum& b);
 470     friend inline const CBigNum operator/(const CBigNum& a, const CBigNum& b);
 471     friend inline const CBigNum operator%(const CBigNum& a, const CBigNum& b);
 472 };
 473
 474
 475
 476 inline const CBigNum operator+(const CBigNum& a, const CBigNum& b)
 477 {
 478     CBigNum r;
 479     if (!BN_add(&r, &a, &b))
 480         throw bignum_error("CBigNum::operator+ : BN_add failed");
 481     return r;
 482 }
 483
 484 inline const CBigNum operator-(const CBigNum& a, const CBigNum& b)
 485 {
 486     CBigNum r;
 487     if (!BN_sub(&r, &a, &b))
 488         throw bignum_error("CBigNum::operator- : BN_sub failed");
 489     return r;
 490 }
 491
 492 inline const CBigNum operator-(const CBigNum& a)
 493 {
 494     CBigNum r(a);
 495     BN_set_negative(&r, !BN_is_negative(&r));
 496     return r;
 497 }
 498
 499 inline const CBigNum operator*(const CBigNum& a, const CBigNum& b)
 500 {
 501     CAutoBN_CTX pctx;
 502     CBigNum r;
 503     if (!BN_mul(&r, &a, &b, pctx))
 504         throw bignum_error("CBigNum::operator* : BN_mul failed");
 505     return r;
 506 }
 507
 508 inline const CBigNum operator/(const CBigNum& a, const CBigNum& b)
 509 {
 510     CAutoBN_CTX pctx;
 511     CBigNum r;
 512     if (!BN_div(&r, NULL, &a, &b, pctx))
 513         throw bignum_error("CBigNum::operator/ : BN_div failed");
 514     return r;
 515 }
 516
 517 inline const CBigNum operator%(const CBigNum& a, const CBigNum& b)
 518 {
 519     CAutoBN_CTX pctx;
 520     CBigNum r;
 521     if (!BN_mod(&r, &a, &b, pctx))
 522         throw bignum_error("CBigNum::operator% : BN_div failed");
 523     return r;
 524 }
 525
 526 inline const CBigNum operator<<(const CBigNum& a, unsigned int shift)
 527 {
 528     CBigNum r;
 529     if (!BN_lshift(&r, &a, shift))
 530         throw bignum_error("CBigNum:operator<< : BN_lshift failed");
 531     return r;
 532 }
 533
 534 inline const CBigNum operator>>(const CBigNum& a, unsigned int shift)
 535 {
 536     CBigNum r = a;
 537     r >>= shift;
 538     return r;
 539 }
 540
 541 inline bool operator==(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) == 0); }
 542 inline bool operator!=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) != 0); }
 543 inline bool operator<=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) <= 0); }
 544 inline bool operator>=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) >= 0); }
 545 inline bool operator<(const CBigNum& a, const CBigNum& b)  { return (BN_cmp(&a, &b) < 0); }
 546 inline bool operator>(const CBigNum& a, const CBigNum& b)  { return (BN_cmp(&a, &b) > 0); }
 547
 548 #endif