src/bignum.cpp

   1 #include "bignum.h"
   2 #include "uint256.h"
   3
   4
   5 CAutoBN_CTX::CAutoBN_CTX() {
   6     pctx = BN_CTX_new();
   7     if (pctx == nullptr)
   8         throw bignum_error("CAutoBN_CTX : BN_CTX_new() returned NULL");
   9 }
  10
  11 CAutoBN_CTX::~CAutoBN_CTX() {
  12     if (pctx != nullptr)
  13         BN_CTX_free(pctx);
  14 }
  15
  16 CBigNum::CBigNum() {
  17     bn = BN_new();
  18 }
  19
  20 CBigNum::CBigNum(const CBigNum &b) {
  21     BIGNUM *dup = BN_dup(b.bn);
  22     if (!dup) {
  23         throw bignum_error("CBigNum::CBigNum(const CBigNum&) : BN_dup failed");
  24     }
  25     bn = dup;
  26 }
  27
  28 CBigNum &CBigNum::operator=(const CBigNum &b) {
  29     BIGNUM *dup = BN_dup(b.bn);
  30     if (!dup) {
  31         throw bignum_error("CBigNum::operator= : BN_dup failed");
  32     }
  33     bn = dup;
  34     return (*this);
  35 }
  36
  37 CBigNum::CBigNum(const BIGNUM *bnp) {
  38     BIGNUM *dup = BN_dup(bnp);
  39     if (!dup) {
  40         throw bignum_error("CBigNum::CBigNum(const BIGNUM*) : BN_dup failed");
  41     }
  42     bn = dup;
  43 }
  44
  45 CBigNum::~CBigNum() {
  46     BN_clear_free(bn);
  47 }
  48
  49 CBigNum::CBigNum(uint256 n) { bn = BN_new(); setuint256(n); }
  50
  51 void CBigNum::setuint32(uint32_t n) {
  52     if (!BN_set_word(bn, n))
  53         throw bignum_error("CBigNum conversion from uint32_t : BN_set_word failed");
  54 }
  55
  56 uint32_t CBigNum::getuint32() const {
  57     return BN_get_word(bn);
  58 }
  59
  60 int32_t CBigNum::getint32() const {
  61     uint64_t n = BN_get_word(bn);
  62     if (!BN_is_negative(bn))
  63         return (n > (uint64_t)std::numeric_limits<int32_t>::max() ? std::numeric_limits<int32_t>::max() : (int32_t)n);
  64     else
  65         return (n > (uint64_t)std::numeric_limits<int32_t>::max() ? std::numeric_limits<int32_t>::min() : -(int32_t)n);
  66 }
  67
  68 void CBigNum::setint64(int64_t sn) {
  69     uint8_t pch[sizeof(sn) + 6];
  70     uint8_t* p = pch + 4;
  71     bool fNegative;
  72     uint64_t n;
  73
  74     if (sn < (int64_t)0)
  75     {
  76         // Since the minimum signed integer cannot be represented as positive so long as its type is signed, and it's not well-defined what happens if you make it unsigned before negating it, we instead increment the negative integer by 1, convert it, then increment the (now positive) unsigned integer by 1 to compensate
  77         n = -(sn + 1);
  78         ++n;
  79         fNegative = true;
  80     } else {
  81         n = sn;
  82         fNegative = false;
  83     }
  84
  85     bool fLeadingZeroes = true;
  86     for (int i = 0; i < 8; i++)
  87     {
  88         uint8_t c = (n >> 56) & 0xff;
  89         n <<= 8;
  90         if (fLeadingZeroes)
  91         {
  92             if (c == 0)
  93                 continue;
  94             if (c & 0x80)
  95                 *p++ = (fNegative ? 0x80 : 0);
  96             else if (fNegative)
  97                 c |= 0x80;
  98             fLeadingZeroes = false;
  99         }
 100         *p++ = c;
 101     }
 102     uint32_t nSize = (uint32_t) (p - (pch + 4));
 103     pch[0] = (nSize >> 24) & 0xff;
 104     pch[1] = (nSize >> 16) & 0xff;
 105     pch[2] = (nSize >> 8) & 0xff;
 106     pch[3] = (nSize) & 0xff;
 107     BN_mpi2bn(pch, (int)(p - pch), bn);
 108 }
 109
 110 uint64_t CBigNum::getuint64() {
 111     size_t nSize = BN_bn2mpi(bn, nullptr);
 112     if (nSize < 4)
 113         return 0;
 114     std::vector<uint8_t> vch(nSize);
 115     BN_bn2mpi(bn, &vch[0]);
 116     if (vch.size() > 4)
 117         vch[4] &= 0x7f;
 118     uint64_t n = 0;
 119     for (size_t i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
 120         ((uint8_t*)&n)[i] = vch[j];
 121     return n;
 122 }
 123
 124 void CBigNum::setuint64(uint64_t n) {
 125     // Use BN_set_word if word size is sufficient for uint64_t
 126     if (check(sizeof(n) <= sizeof(BN_ULONG)))
 127     {
 128         if (!BN_set_word(bn, (BN_ULONG)n))
 129             throw bignum_error("CBigNum conversion from uint64_t : BN_set_word failed");
 130         return;
 131     }
 132
 133     uint8_t pch[sizeof(n) + 6];
 134     uint8_t* p = pch + 4;
 135     bool fLeadingZeroes = true;
 136     for (int i = 0; i < 8; i++)
 137     {
 138         uint8_t c = (n >> 56) & 0xff;
 139         n <<= 8;
 140         if (fLeadingZeroes)
 141         {
 142             if (c == 0)
 143                 continue;
 144             if (c & 0x80)
 145                 *p++ = 0;
 146             fLeadingZeroes = false;
 147         }
 148         *p++ = c;
 149     }
 150     uint32_t nSize = (uint32_t) (p - (pch + 4));
 151     pch[0] = (nSize >> 24) & 0xff;
 152     pch[1] = (nSize >> 16) & 0xff;
 153     pch[2] = (nSize >> 8) & 0xff;
 154     pch[3] = (nSize) & 0xff;
 155     BN_mpi2bn(pch, (int)(p - pch), bn);
 156 }
 157
 158 void CBigNum::setuint160(uint160 n) {
 159     uint8_t pch[sizeof(n) + 6];
 160     uint8_t* p = pch + 4;
 161     bool fLeadingZeroes = true;
 162     uint8_t* pbegin = (uint8_t*)&n;
 163     uint8_t* psrc = pbegin + sizeof(n);
 164     while (psrc != pbegin)
 165     {
 166         uint8_t c = *(--psrc);
 167         if (fLeadingZeroes)
 168         {
 169             if (c == 0)
 170                 continue;
 171             if (c & 0x80)
 172                 *p++ = 0;
 173             fLeadingZeroes = false;
 174         }
 175         *p++ = c;
 176     }
 177     uint32_t nSize = (uint32_t) (p - (pch + 4));
 178     pch[0] = (nSize >> 24) & 0xff;
 179     pch[1] = (nSize >> 16) & 0xff;
 180     pch[2] = (nSize >> 8) & 0xff;
 181     pch[3] = (nSize >> 0) & 0xff;
 182     BN_mpi2bn(pch, (int) (p - pch), bn);
 183 }
 184
 185 uint160 CBigNum::getuint160() const {
 186     unsigned int nSize = BN_bn2mpi(bn, nullptr);
 187     if (nSize < 4)
 188         return 0;
 189     std::vector<uint8_t> vch(nSize);
 190     BN_bn2mpi(bn, &vch[0]);
 191     if (vch.size() > 4)
 192         vch[4] &= 0x7f;
 193     uint160 n = 0;
 194     for (size_t i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
 195         ((uint8_t*)&n)[i] = vch[j];
 196     return n;
 197 }
 198
 199 void CBigNum::setuint256(uint256 n) {
 200     uint8_t pch[sizeof(n) + 6];
 201     uint8_t* p = pch + 4;
 202     bool fLeadingZeroes = true;
 203     uint8_t* pbegin = (uint8_t*)&n;
 204     uint8_t* psrc = pbegin + sizeof(n);
 205     while (psrc != pbegin)
 206     {
 207         uint8_t c = *(--psrc);
 208         if (fLeadingZeroes)
 209         {
 210             if (c == 0)
 211                 continue;
 212             if (c & 0x80)
 213                 *p++ = 0;
 214             fLeadingZeroes = false;
 215         }
 216         *p++ = c;
 217     }
 218     uint32_t nSize = (uint32_t) (p - (pch + 4));
 219     pch[0] = (nSize >> 24) & 0xff;
 220     pch[1] = (nSize >> 16) & 0xff;
 221     pch[2] = (nSize >> 8) & 0xff;
 222     pch[3] = (nSize >> 0) & 0xff;
 223     BN_mpi2bn(pch, (int) (p - pch), bn);
 224 }
 225
 226 uint256 CBigNum::getuint256() const {
 227     unsigned int nSize = BN_bn2mpi(bn, nullptr);
 228     if (nSize < 4)
 229         return 0;
 230     std::vector<uint8_t> vch(nSize);
 231     BN_bn2mpi(bn, &vch[0]);
 232     if (vch.size() > 4)
 233         vch[4] &= 0x7f;
 234     uint256 n = 0;
 235     for (size_t i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--)
 236         ((uint8_t*)&n)[i] = vch[j];
 237     return n;
 238 }
 239
 240 void CBigNum::setBytes(const std::vector<uint8_t> &vchBytes) {
 241     BN_bin2bn(&vchBytes[0], (int) vchBytes.size(), bn);
 242 }
 243
 244 std::vector<uint8_t> CBigNum::getBytes() const {
 245     int nBytes = BN_num_bytes(bn);
 246
 247     std::vector<uint8_t> vchBytes(nBytes);
 248
 249     int n = BN_bn2bin(bn, &vchBytes[0]);
 250     if (n != nBytes) {
 251         throw bignum_error("CBigNum::getBytes : BN_bn2bin failed");
 252     }
 253
 254     return vchBytes;
 255 }
 256
 257 void CBigNum::setvch(const std::vector<uint8_t> &vch) {
 258     std::vector<uint8_t> vch2(vch.size() + 4);
 259     uint32_t nSize = (uint32_t) vch.size();
 260     // BIGNUM's byte stream format expects 4 bytes of
 261     // big endian size data info at the front
 262     vch2[0] = (nSize >> 24) & 0xff;
 263     vch2[1] = (nSize >> 16) & 0xff;
 264     vch2[2] = (nSize >> 8) & 0xff;
 265     vch2[3] = (nSize >> 0) & 0xff;
 266     // swap data to big endian
 267     std::reverse_copy(vch.begin(), vch.end(), vch2.begin() + 4);
 268     BN_mpi2bn(&vch2[0], (int) vch2.size(), bn);
 269 }
 270
 271 std::vector<uint8_t> CBigNum::getvch() const {
 272     unsigned int nSize = BN_bn2mpi(bn, nullptr);
 273     if (nSize <= 4)
 274         return {};
 275     std::vector<uint8_t> vch(nSize);
 276     BN_bn2mpi(bn, &vch[0]);
 277     vch.erase(vch.begin(), vch.begin() + 4);
 278     std::reverse(vch.begin(), vch.end());
 279     return vch;
 280 }
 281
 282 CBigNum &CBigNum::SetCompact(uint32_t nCompact) {
 283     uint32_t nSize = nCompact >> 24;
 284     std::vector<uint8_t> vch(4 + nSize);
 285     vch[3] = nSize;
 286     if (nSize >= 1) vch[4] = (nCompact >> 16) & 0xff;
 287     if (nSize >= 2) vch[5] = (nCompact >> 8) & 0xff;
 288     if (nSize >= 3) vch[6] = (nCompact >> 0) & 0xff;
 289     BN_mpi2bn(&vch[0], (int) vch.size(), bn);
 290     return *this;
 291 }
 292
 293 uint32_t CBigNum::GetCompact() const {
 294     uint32_t nSize = BN_bn2mpi(bn, nullptr);
 295     std::vector<uint8_t> vch(nSize);
 296     nSize -= 4;
 297     BN_bn2mpi(bn, &vch[0]);
 298     uint32_t nCompact = nSize << 24;
 299     if (nSize >= 1) nCompact |= (vch[4] << 16);
 300     if (nSize >= 2) nCompact |= (vch[5] << 8);
 301     if (nSize >= 3) nCompact |= (vch[6] << 0);
 302     return nCompact;
 303 }
 304
 305 void CBigNum::SetHex(const std::string &str) {
 306     // skip 0x
 307     const char* psz = str.c_str();
 308     while (isspace(*psz))
 309         psz++;
 310     bool fNegative = false;
 311     if (*psz == '-')
 312     {
 313         fNegative = true;
 314         psz++;
 315     }
 316     if (psz[0] == '0' && tolower(psz[1]) == 'x')
 317         psz += 2;
 318     while (isspace(*psz))
 319         psz++;
 320
 321     // hex string to bignum
 322     static const 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 };
 323     *this = 0;
 324     while (isxdigit(*psz))
 325     {
 326         *this <<= 4;
 327         int n = phexdigit[(uint8_t)*psz++];
 328         *this += n;
 329     }
 330     if (fNegative)
 331         *this = 0 - *this;
 332 }
 333
 334 std::string CBigNum::ToString(int nBase) const {
 335     CAutoBN_CTX pctx;
 336     CBigNum bnBase = nBase;
 337     CBigNum bn0 = 0;
 338     std::string str;
 339     CBigNum bn = *this;
 340     BN_set_negative(bn.bn, false);
 341     CBigNum dv;
 342     CBigNum rem;
 343     if (BN_cmp(bn.bn, bn0.bn) == 0)
 344         return "0";
 345     while (BN_cmp(bn.bn, bn0.bn) > 0)
 346     {
 347         if (!BN_div(dv.bn, rem.bn, bn.bn, bnBase.bn, pctx))
 348             throw bignum_error("CBigNum::ToString() : BN_div failed");
 349         bn = dv;
 350         uint32_t c = rem.getuint32();
 351         str += "0123456789abcdef"[c];
 352     }
 353     if (BN_is_negative(bn.bn))
 354         str += "-";
 355     std::reverse(str.begin(), str.end());
 356     return str;
 357 }
 358
 359 bool CBigNum::operator!() const {
 360     return BN_is_zero(bn);
 361 }
 362
 363 CBigNum &CBigNum::operator+=(const CBigNum &b) {
 364     if (!BN_add(bn, bn, b.bn))
 365         throw bignum_error("CBigNum::operator+= : BN_add failed");
 366     return *this;
 367 }
 368
 369 CBigNum &CBigNum::operator-=(const CBigNum &b) {
 370     *this = *this - b;
 371     return *this;
 372 }
 373
 374 CBigNum &CBigNum::operator*=(const CBigNum &b) {
 375     CAutoBN_CTX pctx;
 376     if (!BN_mul(bn, bn, b.bn, pctx))
 377         throw bignum_error("CBigNum::operator*= : BN_mul failed");
 378     return *this;
 379 }
 380
 381 CBigNum &CBigNum::operator/=(const CBigNum &b) {
 382     *this = *this / b;
 383     return *this;
 384 }
 385
 386 CBigNum &CBigNum::operator%=(const CBigNum &b) {
 387     *this = *this % b;
 388     return *this;
 389 }
 390
 391 CBigNum &CBigNum::operator<<=(unsigned int shift) {
 392     if (!BN_lshift(bn, bn, shift))
 393         throw bignum_error("CBigNum:operator<<= : BN_lshift failed");
 394     return *this;
 395 }
 396
 397 CBigNum &CBigNum::operator>>=(unsigned int shift) {
 398     // Note: BN_rshift segfaults on 64-bit if 2^shift is greater than the number
 399     //   if built on ubuntu 9.04 or 9.10, probably depends on version of OpenSSL
 400     CBigNum a = 1;
 401     a <<= shift;
 402     if (BN_cmp(a.bn, bn) > 0)
 403     {
 404         *this = 0;
 405         return *this;
 406     }
 407
 408     if (!BN_rshift(bn, bn, shift))
 409         throw bignum_error("CBigNum:operator>>= : BN_rshift failed");
 410     return *this;
 411 }
 412
 413 CBigNum &CBigNum::operator++() {
 414     // prefix operator
 415     if (!BN_add(bn, bn, BN_value_one()))
 416         throw bignum_error("CBigNum::operator++ : BN_add failed");
 417     return *this;
 418 }
 419
 420 CBigNum &CBigNum::operator--() {
 421     // prefix operator
 422     CBigNum r;
 423     if (!BN_sub(r.bn, bn, BN_value_one()))
 424         throw bignum_error("CBigNum::operator-- : BN_sub failed");
 425     *this = r;
 426     return *this;
 427 }
 428
 429 const CBigNum CBigNum::operator--(int) {
 430     // postfix operator
 431     const CBigNum ret = *this;
 432     --(*this);
 433     return ret;
 434 }
 435
 436 const CBigNum CBigNum::operator++(int) {
 437     // postfix operator
 438     const CBigNum ret = *this;
 439     ++(*this);
 440     return ret;
 441 }