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