src/bignum.h

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