src/bignum.cpp

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