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