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