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