Back to home page

Bitcoin sources

 
 

    


0001 // Copyright (c) 2009-2010 Satoshi Nakamoto
0002 // Copyright (c) 2011 The Bitcoin developers
0003 // Distributed under the MIT/X11 software license, see the accompanying
0004 // file license.txt or http://www.opensource.org/licenses/mit-license.php.
0005 #ifndef BITCOIN_BIGNUM_H
0006 #define BITCOIN_BIGNUM_H
0007 
0008 #include <stdexcept>
0009 #include <vector>
0010 #include <openssl/bn.h>
0011 
0012 #include "util.h"
0013 
0014 class bignum_error : public std::runtime_error
0015 {
0016 public:
0017     explicit bignum_error(const std::string& str) : std::runtime_error(str) {}
0018 };
0019 
0020 
0021 
0022 class CAutoBN_CTX
0023 {
0024 protected:
0025     BN_CTX* pctx;
0026     BN_CTX* operator=(BN_CTX* pnew) { return pctx = pnew; }
0027 
0028 public:
0029     CAutoBN_CTX()
0030     {
0031         pctx = BN_CTX_new();
0032         if (pctx == NULL)
0033             throw bignum_error("CAutoBN_CTX : BN_CTX_new() returned NULL");
0034     }
0035 
0036     ~CAutoBN_CTX()
0037     {
0038         if (pctx != NULL)
0039             BN_CTX_free(pctx);
0040     }
0041 
0042     operator BN_CTX*() { return pctx; }
0043     BN_CTX& operator*() { return *pctx; }
0044     BN_CTX** operator&() { return &pctx; }
0045     bool operator!() { return (pctx == NULL); }
0046 };
0047 
0048 
0049 
0050 class CBigNum : public BIGNUM
0051 {
0052 public:
0053     CBigNum()
0054     {
0055         BN_init(this);
0056     }
0057 
0058     CBigNum(const CBigNum& b)
0059     {
0060         BN_init(this);
0061         if (!BN_copy(this, &b))
0062         {
0063             BN_clear_free(this);
0064             throw bignum_error("CBigNum::CBigNum(const CBigNum&) : BN_copy failed");
0065         }
0066     }
0067 
0068     CBigNum& operator=(const CBigNum& b)
0069     {
0070         if (!BN_copy(this, &b))
0071             throw bignum_error("CBigNum::operator= : BN_copy failed");
0072         return (*this);
0073     }
0074 
0075     ~CBigNum()
0076     {
0077         BN_clear_free(this);
0078     }
0079 
0080     CBigNum(char n)             { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
0081     CBigNum(short n)            { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
0082     CBigNum(int n)              { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
0083     CBigNum(long n)             { BN_init(this); if (n >= 0) setulong(n); else setint64(n); }
0084     CBigNum(int64 n)            { BN_init(this); setint64(n); }
0085     CBigNum(unsigned char n)    { BN_init(this); setulong(n); }
0086     CBigNum(unsigned short n)   { BN_init(this); setulong(n); }
0087     CBigNum(unsigned int n)     { BN_init(this); setulong(n); }
0088     CBigNum(unsigned long n)    { BN_init(this); setulong(n); }
0089     CBigNum(uint64 n)           { BN_init(this); setuint64(n); }
0090     explicit CBigNum(uint256 n) { BN_init(this); setuint256(n); }
0091 
0092     explicit CBigNum(const std::vector<unsigned char>& vch)
0093     {
0094         BN_init(this);
0095         setvch(vch);
0096     }
0097 
0098     void setulong(unsigned long n)
0099     {
0100         if (!BN_set_word(this, n))
0101             throw bignum_error("CBigNum conversion from unsigned long : BN_set_word failed");
0102     }
0103 
0104     unsigned long getulong() const
0105     {
0106         return BN_get_word(this);
0107     }
0108 
0109     unsigned int getuint() const
0110     {
0111         return BN_get_word(this);
0112     }
0113 
0114     int getint() const
0115     {
0116         unsigned long n = BN_get_word(this);
0117         if (!BN_is_negative(this))
0118             return (n > INT_MAX ? INT_MAX : n);
0119         else
0120             return (n > INT_MAX ? INT_MIN : -(int)n);
0121     }
0122 
0123     void setint64(int64 n)
0124     {
0125         unsigned char pch[sizeof(n) + 6];
0126         unsigned char* p = pch + 4;
0127         bool fNegative = false;
0128         if (n < (int64)0)
0129         {
0130             n = -n;
0131             fNegative = true;
0132         }
0133         bool fLeadingZeroes = true;
0134         for (int i = 0; i < 8; i++)
0135         {
0136             unsigned char c = (n >> 56) & 0xff;
0137             n <<= 8;
0138             if (fLeadingZeroes)
0139             {
0140                 if (c == 0)
0141                     continue;
0142                 if (c & 0x80)
0143                     *p++ = (fNegative ? 0x80 : 0);
0144                 else if (fNegative)
0145                     c |= 0x80;
0146                 fLeadingZeroes = false;
0147             }
0148             *p++ = c;
0149         }
0150         unsigned int nSize = p - (pch + 4);
0151         pch[0] = (nSize >> 24) & 0xff;
0152         pch[1] = (nSize >> 16) & 0xff;
0153         pch[2] = (nSize >> 8) & 0xff;
0154         pch[3] = (nSize) & 0xff;
0155         BN_mpi2bn(pch, p - pch, this);
0156     }
0157 
0158     void setuint64(uint64 n)
0159     {
0160         unsigned char pch[sizeof(n) + 6];
0161         unsigned char* p = pch + 4;
0162         bool fLeadingZeroes = true;
0163         for (int i = 0; i < 8; i++)
0164         {
0165             unsigned char c = (n >> 56) & 0xff;
0166             n <<= 8;
0167             if (fLeadingZeroes)
0168             {
0169                 if (c == 0)
0170                     continue;
0171                 if (c & 0x80)
0172                     *p++ = 0;
0173                 fLeadingZeroes = false;
0174             }
0175             *p++ = c;
0176         }
0177         unsigned int nSize = p - (pch + 4);
0178         pch[0] = (nSize >> 24) & 0xff;
0179         pch[1] = (nSize >> 16) & 0xff;
0180         pch[2] = (nSize >> 8) & 0xff;
0181         pch[3] = (nSize) & 0xff;
0182         BN_mpi2bn(pch, p - pch, this);
0183     }
0184 
0185     void setuint256(uint256 n)
0186     {
0187         unsigned char pch[sizeof(n) + 6];
0188         unsigned char* p = pch + 4;
0189         bool fLeadingZeroes = true;
0190         unsigned char* pbegin = (unsigned char*)&n;
0191         unsigned char* psrc = pbegin + sizeof(n);
0192         while (psrc != pbegin)
0193         {
0194             unsigned char c = *(--psrc);
0195             if (fLeadingZeroes)
0196             {
0197                 if (c == 0)
0198                     continue;
0199                 if (c & 0x80)
0200                     *p++ = 0;
0201                 fLeadingZeroes = false;
0202             }
0203             *p++ = c;
0204         }
0205         unsigned int nSize = p - (pch + 4);
0206         pch[0] = (nSize >> 24) & 0xff;
0207         pch[1] = (nSize >> 16) & 0xff;
0208         pch[2] = (nSize >> 8) & 0xff;
0209         pch[3] = (nSize >> 0) & 0xff;
0210         BN_mpi2bn(pch, p - pch, this);
0211     }
0212 
0213     uint256 getuint256()
0214     {
0215         unsigned int nSize = BN_bn2mpi(this, NULL);
0216         if (nSize < 4)
0217             return 0;
0218         std::vector<unsigned char> vch(nSize);
0219         BN_bn2mpi(this, &vch[0]);
0220         if (vch.size() > 4)
0221             vch[4] &= 0x7f;
0222         uint256 n = 0;
0223         for (int i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
0224             ((unsigned char*)&n)[i] = vch[j];
0225         return n;
0226     }
0227 
0228     void setvch(const std::vector<unsigned char>& vch)
0229     {
0230         std::vector<unsigned char> vch2(vch.size() + 4);
0231         unsigned int nSize = vch.size();
0232         // BIGNUM's byte stream format expects 4 bytes of
0233         // big endian size data info at the front
0234         vch2[0] = (nSize >> 24) & 0xff;
0235         vch2[1] = (nSize >> 16) & 0xff;
0236         vch2[2] = (nSize >> 8) & 0xff;
0237         vch2[3] = (nSize >> 0) & 0xff;
0238         // swap data to big endian
0239         reverse_copy(vch.begin(), vch.end(), vch2.begin() + 4);
0240         BN_mpi2bn(&vch2[0], vch2.size(), this);
0241     }
0242 
0243     std::vector<unsigned char> getvch() const
0244     {
0245         unsigned int nSize = BN_bn2mpi(this, NULL);
0246         if (nSize < 4)
0247             return std::vector<unsigned char>();
0248         std::vector<unsigned char> vch(nSize);
0249         BN_bn2mpi(this, &vch[0]);
0250         vch.erase(vch.begin(), vch.begin() + 4);
0251         reverse(vch.begin(), vch.end());
0252         return vch;
0253     }
0254 
0255     CBigNum& SetCompact(unsigned int nCompact)
0256     {
0257         unsigned int nSize = nCompact >> 24;
0258         std::vector<unsigned char> vch(4 + nSize);
0259         vch[3] = nSize;
0260         if (nSize >= 1) vch[4] = (nCompact >> 16) & 0xff;
0261         if (nSize >= 2) vch[5] = (nCompact >> 8) & 0xff;
0262         if (nSize >= 3) vch[6] = (nCompact >> 0) & 0xff;
0263         BN_mpi2bn(&vch[0], vch.size(), this);
0264         return *this;
0265     }
0266 
0267     unsigned int GetCompact() const
0268     {
0269         unsigned int nSize = BN_bn2mpi(this, NULL);
0270         std::vector<unsigned char> vch(nSize);
0271         nSize -= 4;
0272         BN_bn2mpi(this, &vch[0]);
0273         unsigned int nCompact = nSize << 24;
0274         if (nSize >= 1) nCompact |= (vch[4] << 16);
0275         if (nSize >= 2) nCompact |= (vch[5] << 8);
0276         if (nSize >= 3) nCompact |= (vch[6] << 0);
0277         return nCompact;
0278     }
0279 
0280     void SetHex(const std::string& str)
0281     {
0282         // skip 0x
0283         const char* psz = str.c_str();
0284         while (isspace(*psz))
0285             psz++;
0286         bool fNegative = false;
0287         if (*psz == '-')
0288         {
0289             fNegative = true;
0290             psz++;
0291         }
0292         if (psz[0] == '0' && tolower(psz[1]) == 'x')
0293             psz += 2;
0294         while (isspace(*psz))
0295             psz++;
0296 
0297         // hex string to bignum
0298         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 };
0299         *this = 0;
0300         while (isxdigit(*psz))
0301         {
0302             *this <<= 4;
0303             int n = phexdigit[*psz++];
0304             *this += n;
0305         }
0306         if (fNegative)
0307             *this = 0 - *this;
0308     }
0309 
0310     std::string ToString(int nBase=10) const
0311     {
0312         CAutoBN_CTX pctx;
0313         CBigNum bnBase = nBase;
0314         CBigNum bn0 = 0;
0315         std::string str;
0316         CBigNum bn = *this;
0317         BN_set_negative(&bn, false);
0318         CBigNum dv;
0319         CBigNum rem;
0320         if (BN_cmp(&bn, &bn0) == 0)
0321             return "0";
0322         while (BN_cmp(&bn, &bn0) > 0)
0323         {
0324             if (!BN_div(&dv, &rem, &bn, &bnBase, pctx))
0325                 throw bignum_error("CBigNum::ToString() : BN_div failed");
0326             bn = dv;
0327             unsigned int c = rem.getulong();
0328             str += "0123456789abcdef"[c];
0329         }
0330         if (BN_is_negative(this))
0331             str += "-";
0332         reverse(str.begin(), str.end());
0333         return str;
0334     }
0335 
0336     std::string GetHex() const
0337     {
0338         return ToString(16);
0339     }
0340 
0341     unsigned int GetSerializeSize(int nType=0, int nVersion=VERSION) const
0342     {
0343         return ::GetSerializeSize(getvch(), nType, nVersion);
0344     }
0345 
0346     template<typename Stream>
0347     void Serialize(Stream& s, int nType=0, int nVersion=VERSION) const
0348     {
0349         ::Serialize(s, getvch(), nType, nVersion);
0350     }
0351 
0352     template<typename Stream>
0353     void Unserialize(Stream& s, int nType=0, int nVersion=VERSION)
0354     {
0355         std::vector<unsigned char> vch;
0356         ::Unserialize(s, vch, nType, nVersion);
0357         setvch(vch);
0358     }
0359 
0360 
0361     bool operator!() const
0362     {
0363         return BN_is_zero(this);
0364     }
0365 
0366     CBigNum& operator+=(const CBigNum& b)
0367     {
0368         if (!BN_add(this, this, &b))
0369             throw bignum_error("CBigNum::operator+= : BN_add failed");
0370         return *this;
0371     }
0372 
0373     CBigNum& operator-=(const CBigNum& b)
0374     {
0375         *this = *this - b;
0376         return *this;
0377     }
0378 
0379     CBigNum& operator*=(const CBigNum& b)
0380     {
0381         CAutoBN_CTX pctx;
0382         if (!BN_mul(this, this, &b, pctx))
0383             throw bignum_error("CBigNum::operator*= : BN_mul failed");
0384         return *this;
0385     }
0386 
0387     CBigNum& operator/=(const CBigNum& b)
0388     {
0389         *this = *this / b;
0390         return *this;
0391     }
0392 
0393     CBigNum& operator%=(const CBigNum& b)
0394     {
0395         *this = *this % b;
0396         return *this;
0397     }
0398 
0399     CBigNum& operator<<=(unsigned int shift)
0400     {
0401         if (!BN_lshift(this, this, shift))
0402             throw bignum_error("CBigNum:operator<<= : BN_lshift failed");
0403         return *this;
0404     }
0405 
0406     CBigNum& operator>>=(unsigned int shift)
0407     {
0408         // Note: BN_rshift segfaults on 64-bit if 2^shift is greater than the number
0409         //   if built on ubuntu 9.04 or 9.10, probably depends on version of openssl
0410         CBigNum a = 1;
0411         a <<= shift;
0412         if (BN_cmp(&a, this) > 0)
0413         {
0414             *this = 0;
0415             return *this;
0416         }
0417 
0418         if (!BN_rshift(this, this, shift))
0419             throw bignum_error("CBigNum:operator>>= : BN_rshift failed");
0420         return *this;
0421     }
0422 
0423 
0424     CBigNum& operator++()
0425     {
0426         // prefix operator
0427         if (!BN_add(this, this, BN_value_one()))
0428             throw bignum_error("CBigNum::operator++ : BN_add failed");
0429         return *this;
0430     }
0431 
0432     const CBigNum operator++(int)
0433     {
0434         // postfix operator
0435         const CBigNum ret = *this;
0436         ++(*this);
0437         return ret;
0438     }
0439 
0440     CBigNum& operator--()
0441     {
0442         // prefix operator
0443         CBigNum r;
0444         if (!BN_sub(&r, this, BN_value_one()))
0445             throw bignum_error("CBigNum::operator-- : BN_sub failed");
0446         *this = r;
0447         return *this;
0448     }
0449 
0450     const CBigNum operator--(int)
0451     {
0452         // postfix operator
0453         const CBigNum ret = *this;
0454         --(*this);
0455         return ret;
0456     }
0457 
0458 
0459     friend inline const CBigNum operator-(const CBigNum& a, const CBigNum& b);
0460     friend inline const CBigNum operator/(const CBigNum& a, const CBigNum& b);
0461     friend inline const CBigNum operator%(const CBigNum& a, const CBigNum& b);
0462 };
0463 
0464 
0465 
0466 inline const CBigNum operator+(const CBigNum& a, const CBigNum& b)
0467 {
0468     CBigNum r;
0469     if (!BN_add(&r, &a, &b))
0470         throw bignum_error("CBigNum::operator+ : BN_add failed");
0471     return r;
0472 }
0473 
0474 inline const CBigNum operator-(const CBigNum& a, const CBigNum& b)
0475 {
0476     CBigNum r;
0477     if (!BN_sub(&r, &a, &b))
0478         throw bignum_error("CBigNum::operator- : BN_sub failed");
0479     return r;
0480 }
0481 
0482 inline const CBigNum operator-(const CBigNum& a)
0483 {
0484     CBigNum r(a);
0485     BN_set_negative(&r, !BN_is_negative(&r));
0486     return r;
0487 }
0488 
0489 inline const CBigNum operator*(const CBigNum& a, const CBigNum& b)
0490 {
0491     CAutoBN_CTX pctx;
0492     CBigNum r;
0493     if (!BN_mul(&r, &a, &b, pctx))
0494         throw bignum_error("CBigNum::operator* : BN_mul failed");
0495     return r;
0496 }
0497 
0498 inline const CBigNum operator/(const CBigNum& a, const CBigNum& b)
0499 {
0500     CAutoBN_CTX pctx;
0501     CBigNum r;
0502     if (!BN_div(&r, NULL, &a, &b, pctx))
0503         throw bignum_error("CBigNum::operator/ : BN_div failed");
0504     return r;
0505 }
0506 
0507 inline const CBigNum operator%(const CBigNum& a, const CBigNum& b)
0508 {
0509     CAutoBN_CTX pctx;
0510     CBigNum r;
0511     if (!BN_mod(&r, &a, &b, pctx))
0512         throw bignum_error("CBigNum::operator% : BN_div failed");
0513     return r;
0514 }
0515 
0516 inline const CBigNum operator<<(const CBigNum& a, unsigned int shift)
0517 {
0518     CBigNum r;
0519     if (!BN_lshift(&r, &a, shift))
0520         throw bignum_error("CBigNum:operator<< : BN_lshift failed");
0521     return r;
0522 }
0523 
0524 inline const CBigNum operator>>(const CBigNum& a, unsigned int shift)
0525 {
0526     CBigNum r = a;
0527     r >>= shift;
0528     return r;
0529 }
0530 
0531 inline bool operator==(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) == 0); }
0532 inline bool operator!=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) != 0); }
0533 inline bool operator<=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) <= 0); }
0534 inline bool operator>=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) >= 0); }
0535 inline bool operator<(const CBigNum& a, const CBigNum& b)  { return (BN_cmp(&a, &b) < 0); }
0536 inline bool operator>(const CBigNum& a, const CBigNum& b)  { return (BN_cmp(&a, &b) > 0); }
0537 
0538 #endif