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 license.txt 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 n)
 126     {
 127         unsigned char pch[sizeof(n) + 6];
 128         unsigned char* p = pch + 4;
 129         bool fNegative = false;
 130         if (n < (int64)0)
 131         {
 132             n = -n;
 133             fNegative = true;
 134         }
 135         bool fLeadingZeroes = true;
 136         for (int i = 0; i < 8; i++)
 137         {
 138             unsigned char c = (n >> 56) & 0xff;
 139             n <<= 8;
 140             if (fLeadingZeroes)
 141             {
 142                 if (c == 0)
 143                     continue;
 144                 if (c & 0x80)
 145                     *p++ = (fNegative ? 0x80 : 0);
 146                 else if (fNegative)
 147                     c |= 0x80;
 148                 fLeadingZeroes = false;
 149             }
 150             *p++ = c;
 151         }
 152         unsigned int nSize = p - (pch + 4);
 153         pch[0] = (nSize >> 24) & 0xff;
 154         pch[1] = (nSize >> 16) & 0xff;
 155         pch[2] = (nSize >> 8) & 0xff;
 156         pch[3] = (nSize) & 0xff;
 157         BN_mpi2bn(pch, p - pch, this);
 158     }
 159
 160     void setuint64(uint64 n)
 161     {
 162         unsigned char pch[sizeof(n) + 6];
 163         unsigned char* p = pch + 4;
 164         bool fLeadingZeroes = true;
 165         for (int i = 0; i < 8; i++)
 166         {
 167             unsigned char c = (n >> 56) & 0xff;
 168             n <<= 8;
 169             if (fLeadingZeroes)
 170             {
 171                 if (c == 0)
 172                     continue;
 173                 if (c & 0x80)
 174                     *p++ = 0;
 175                 fLeadingZeroes = false;
 176             }
 177             *p++ = c;
 178         }
 179         unsigned int nSize = p - (pch + 4);
 180         pch[0] = (nSize >> 24) & 0xff;
 181         pch[1] = (nSize >> 16) & 0xff;
 182         pch[2] = (nSize >> 8) & 0xff;
 183         pch[3] = (nSize) & 0xff;
 184         BN_mpi2bn(pch, p - pch, this);
 185     }
 186
 187     void setuint256(uint256 n)
 188     {
 189         unsigned char pch[sizeof(n) + 6];
 190         unsigned char* p = pch + 4;
 191         bool fLeadingZeroes = true;
 192         unsigned char* pbegin = (unsigned char*)&n;
 193         unsigned char* psrc = pbegin + sizeof(n);
 194         while (psrc != pbegin)
 195         {
 196             unsigned char c = *(--psrc);
 197             if (fLeadingZeroes)
 198             {
 199                 if (c == 0)
 200                     continue;
 201                 if (c & 0x80)
 202                     *p++ = 0;
 203                 fLeadingZeroes = false;
 204             }
 205             *p++ = c;
 206         }
 207         unsigned int nSize = p - (pch + 4);
 208         pch[0] = (nSize >> 24) & 0xff;
 209         pch[1] = (nSize >> 16) & 0xff;
 210         pch[2] = (nSize >> 8) & 0xff;
 211         pch[3] = (nSize >> 0) & 0xff;
 212         BN_mpi2bn(pch, p - pch, this);
 213     }
 214
 215     uint256 getuint256()
 216     {
 217         unsigned int nSize = BN_bn2mpi(this, NULL);
 218         if (nSize < 4)
 219             return 0;
 220         std::vector<unsigned char> vch(nSize);
 221         BN_bn2mpi(this, &vch[0]);
 222         if (vch.size() > 4)
 223             vch[4] &= 0x7f;
 224         uint256 n = 0;
 225         for (unsigned int i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
 226             ((unsigned char*)&n)[i] = vch[j];
 227         return n;
 228     }
 229
 230     void setvch(const std::vector<unsigned char>& vch)
 231     {
 232         std::vector<unsigned char> vch2(vch.size() + 4);
 233         unsigned int nSize = vch.size();
 234         // BIGNUM's byte stream format expects 4 bytes of
 235         // big endian size data info at the front
 236         vch2[0] = (nSize >> 24) & 0xff;
 237         vch2[1] = (nSize >> 16) & 0xff;
 238         vch2[2] = (nSize >> 8) & 0xff;
 239         vch2[3] = (nSize >> 0) & 0xff;
 240         // swap data to big endian
 241         reverse_copy(vch.begin(), vch.end(), vch2.begin() + 4);
 242         BN_mpi2bn(&vch2[0], vch2.size(), this);
 243     }
 244
 245     std::vector<unsigned char> getvch() const
 246     {
 247         unsigned int nSize = BN_bn2mpi(this, NULL);
 248         if (nSize <= 4)
 249             return std::vector<unsigned char>();
 250         std::vector<unsigned char> vch(nSize);
 251         BN_bn2mpi(this, &vch[0]);
 252         vch.erase(vch.begin(), vch.begin() + 4);
 253         reverse(vch.begin(), vch.end());
 254         return vch;
 255     }
 256
 257     CBigNum& SetCompact(unsigned int nCompact)
 258     {
 259         unsigned int nSize = nCompact >> 24;
 260         std::vector<unsigned char> vch(4 + nSize);
 261         vch[3] = nSize;
 262         if (nSize >= 1) vch[4] = (nCompact >> 16) & 0xff;
 263         if (nSize >= 2) vch[5] = (nCompact >> 8) & 0xff;
 264         if (nSize >= 3) vch[6] = (nCompact >> 0) & 0xff;
 265         BN_mpi2bn(&vch[0], vch.size(), this);
 266         return *this;
 267     }
 268
 269     unsigned int GetCompact() const
 270     {
 271         unsigned int nSize = BN_bn2mpi(this, NULL);
 272         std::vector<unsigned char> vch(nSize);
 273         nSize -= 4;
 274         BN_bn2mpi(this, &vch[0]);
 275         unsigned int nCompact = nSize << 24;
 276         if (nSize >= 1) nCompact |= (vch[4] << 16);
 277         if (nSize >= 2) nCompact |= (vch[5] << 8);
 278         if (nSize >= 3) nCompact |= (vch[6] << 0);
 279         return nCompact;
 280     }
 281
 282     void SetHex(const std::string& str)
 283     {
 284         // skip 0x
 285         const char* psz = str.c_str();
 286         while (isspace(*psz))
 287             psz++;
 288         bool fNegative = false;
 289         if (*psz == '-')
 290         {
 291             fNegative = true;
 292             psz++;
 293         }
 294         if (psz[0] == '0' && tolower(psz[1]) == 'x')
 295             psz += 2;
 296         while (isspace(*psz))
 297             psz++;
 298
 299         // hex string to bignum
 300         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 };
 301         *this = 0;
 302         while (isxdigit(*psz))
 303         {
 304             *this <<= 4;
 305             int n = phexdigit[(unsigned char)*psz++];
 306             *this += n;
 307         }
 308         if (fNegative)
 309             *this = 0 - *this;
 310     }
 311
 312     std::string ToString(int nBase=10) const
 313     {
 314         CAutoBN_CTX pctx;
 315         CBigNum bnBase = nBase;
 316         CBigNum bn0 = 0;
 317         std::string str;
 318         CBigNum bn = *this;
 319         BN_set_negative(&bn, false);
 320         CBigNum dv;
 321         CBigNum rem;
 322         if (BN_cmp(&bn, &bn0) == 0)
 323             return "0";
 324         while (BN_cmp(&bn, &bn0) > 0)
 325         {
 326             if (!BN_div(&dv, &rem, &bn, &bnBase, pctx))
 327                 throw bignum_error("CBigNum::ToString() : BN_div failed");
 328             bn = dv;
 329             unsigned int c = rem.getulong();
 330             str += "0123456789abcdef"[c];
 331         }
 332         if (BN_is_negative(this))
 333             str += "-";
 334         reverse(str.begin(), str.end());
 335         return str;
 336     }
 337
 338     std::string GetHex() const
 339     {
 340         return ToString(16);
 341     }
 342
 343     unsigned int GetSerializeSize(int nType=0, int nVersion=PROTOCOL_VERSION) const
 344     {
 345         return ::GetSerializeSize(getvch(), nType, nVersion);
 346     }
 347
 348     template<typename Stream>
 349     void Serialize(Stream& s, int nType=0, int nVersion=PROTOCOL_VERSION) const
 350     {
 351         ::Serialize(s, getvch(), nType, nVersion);
 352     }
 353
 354     template<typename Stream>
 355     void Unserialize(Stream& s, int nType=0, int nVersion=PROTOCOL_VERSION)
 356     {
 357         std::vector<unsigned char> vch;
 358         ::Unserialize(s, vch, nType, nVersion);
 359         setvch(vch);
 360     }
 361
 362
 363     bool operator!() const
 364     {
 365         return BN_is_zero(this);
 366     }
 367
 368     CBigNum& operator+=(const CBigNum& b)
 369     {
 370         if (!BN_add(this, this, &b))
 371             throw bignum_error("CBigNum::operator+= : BN_add failed");
 372         return *this;
 373     }
 374
 375     CBigNum& operator-=(const CBigNum& b)
 376     {
 377         *this = *this - b;
 378         return *this;
 379     }
 380
 381     CBigNum& operator*=(const CBigNum& b)
 382     {
 383         CAutoBN_CTX pctx;
 384         if (!BN_mul(this, this, &b, pctx))
 385             throw bignum_error("CBigNum::operator*= : BN_mul failed");
 386         return *this;
 387     }
 388
 389     CBigNum& operator/=(const CBigNum& b)
 390     {
 391         *this = *this / b;
 392         return *this;
 393     }
 394
 395     CBigNum& operator%=(const CBigNum& b)
 396     {
 397         *this = *this % b;
 398         return *this;
 399     }
 400
 401     CBigNum& operator<<=(unsigned int shift)
 402     {
 403         if (!BN_lshift(this, this, shift))
 404             throw bignum_error("CBigNum:operator<<= : BN_lshift failed");
 405         return *this;
 406     }
 407
 408     CBigNum& operator>>=(unsigned int shift)
 409     {
 410         // Note: BN_rshift segfaults on 64-bit if 2^shift is greater than the number
 411         //   if built on ubuntu 9.04 or 9.10, probably depends on version of openssl
 412         CBigNum a = 1;
 413         a <<= shift;
 414         if (BN_cmp(&a, this) > 0)
 415         {
 416             *this = 0;
 417             return *this;
 418         }
 419
 420         if (!BN_rshift(this, this, shift))
 421             throw bignum_error("CBigNum:operator>>= : BN_rshift failed");
 422         return *this;
 423     }
 424
 425
 426     CBigNum& operator++()
 427     {
 428         // prefix operator
 429         if (!BN_add(this, this, BN_value_one()))
 430             throw bignum_error("CBigNum::operator++ : BN_add failed");
 431         return *this;
 432     }
 433
 434     const CBigNum operator++(int)
 435     {
 436         // postfix operator
 437         const CBigNum ret = *this;
 438         ++(*this);
 439         return ret;
 440     }
 441
 442     CBigNum& operator--()
 443     {
 444         // prefix operator
 445         CBigNum r;
 446         if (!BN_sub(&r, this, BN_value_one()))
 447             throw bignum_error("CBigNum::operator-- : BN_sub failed");
 448         *this = r;
 449         return *this;
 450     }
 451
 452     const CBigNum operator--(int)
 453     {
 454         // postfix operator
 455         const CBigNum ret = *this;
 456         --(*this);
 457         return ret;
 458     }
 459
 460
 461     friend inline const CBigNum operator-(const CBigNum& a, const CBigNum& b);
 462     friend inline const CBigNum operator/(const CBigNum& a, const CBigNum& b);
 463     friend inline const CBigNum operator%(const CBigNum& a, const CBigNum& b);
 464 };
 465
 466
 467
 468 inline const CBigNum operator+(const CBigNum& a, const CBigNum& b)
 469 {
 470     CBigNum r;
 471     if (!BN_add(&r, &a, &b))
 472         throw bignum_error("CBigNum::operator+ : BN_add failed");
 473     return r;
 474 }
 475
 476 inline const CBigNum operator-(const CBigNum& a, const CBigNum& b)
 477 {
 478     CBigNum r;
 479     if (!BN_sub(&r, &a, &b))
 480         throw bignum_error("CBigNum::operator- : BN_sub failed");
 481     return r;
 482 }
 483
 484 inline const CBigNum operator-(const CBigNum& a)
 485 {
 486     CBigNum r(a);
 487     BN_set_negative(&r, !BN_is_negative(&r));
 488     return r;
 489 }
 490
 491 inline const CBigNum operator*(const CBigNum& a, const CBigNum& b)
 492 {
 493     CAutoBN_CTX pctx;
 494     CBigNum r;
 495     if (!BN_mul(&r, &a, &b, pctx))
 496         throw bignum_error("CBigNum::operator* : BN_mul failed");
 497     return r;
 498 }
 499
 500 inline const CBigNum operator/(const CBigNum& a, const CBigNum& b)
 501 {
 502     CAutoBN_CTX pctx;
 503     CBigNum r;
 504     if (!BN_div(&r, NULL, &a, &b, pctx))
 505         throw bignum_error("CBigNum::operator/ : BN_div failed");
 506     return r;
 507 }
 508
 509 inline const CBigNum operator%(const CBigNum& a, const CBigNum& b)
 510 {
 511     CAutoBN_CTX pctx;
 512     CBigNum r;
 513     if (!BN_mod(&r, &a, &b, pctx))
 514         throw bignum_error("CBigNum::operator% : BN_div failed");
 515     return r;
 516 }
 517
 518 inline const CBigNum operator<<(const CBigNum& a, unsigned int shift)
 519 {
 520     CBigNum r;
 521     if (!BN_lshift(&r, &a, shift))
 522         throw bignum_error("CBigNum:operator<< : BN_lshift failed");
 523     return r;
 524 }
 525
 526 inline const CBigNum operator>>(const CBigNum& a, unsigned int shift)
 527 {
 528     CBigNum r = a;
 529     r >>= shift;
 530     return r;
 531 }
 532
 533 inline bool operator==(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) == 0); }
 534 inline bool operator!=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) != 0); }
 535 inline bool operator<=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) <= 0); }
 536 inline bool operator>=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) >= 0); }
 537 inline bool operator<(const CBigNum& a, const CBigNum& b)  { return (BN_cmp(&a, &b) < 0); }
 538 inline bool operator>(const CBigNum& a, const CBigNum& b)  { return (BN_cmp(&a, &b) > 0); }
 539
 540 #endif