bignum.h

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