src/bignum.h

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