Line data    Source code

       1             : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2             : // Copyright (c) 2009-2019 The Bitcoin Core developers
       3             : // Distributed under the MIT software license, see the accompanying
       4             : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
       5             : 
       6             : #include <arith_uint256.h>
       7             : 
       8             : #include <limits>
       9             : #include <uint256.h>
      10             : #include <crypto/common.h>
      11             : 
      12             : #include <cassert>
      13             : 
      14             : template <unsigned int BITS>
      15     3680183 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
      16             : {
      17     3680183 :     base_uint<BITS> a(*this);
      18    33121636 :     for (int i = 0; i < WIDTH; i++)
      19    29441453 :         pn[i] = 0;
      20     3680183 :     int k = shift / 32;
      21     3680183 :     shift = shift % 32;
      22    33121626 :     for (int i = 0; i < WIDTH; i++) {
      23    29441443 :         if (i + k + 1 < WIDTH && shift != 0)
      24     5018613 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
      25    29441443 :         if (i + k < WIDTH)
      26     8849561 :             pn[i + k] |= (a.pn[i] << shift);
      27    29441443 :     }
      28     3680183 :     return *this;
      29             : }
      30             : 
      31             : template <unsigned int BITS>
      32     1858003 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
      33             : {
      34     1858003 :     base_uint<BITS> a(*this);
      35    16722027 :     for (int i = 0; i < WIDTH; i++)
      36    14864024 :         pn[i] = 0;
      37     1858003 :     int k = shift / 32;
      38     1858003 :     shift = shift % 32;
      39    16722027 :     for (int i = 0; i < WIDTH; i++) {
      40    14864024 :         if (i - k - 1 >= 0 && shift != 0)
      41     9239023 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
      42    14864024 :         if (i - k >= 0)
      43    11097791 :             pn[i - k] |= (a.pn[i] >> shift);
      44    14864024 :     }
      45     1858003 :     return *this;
      46             : }
      47             : 
      48             : template <unsigned int BITS>
      49       23941 : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
      50             : {
      51       23941 :     uint64_t carry = 0;
      52      215469 :     for (int i = 0; i < WIDTH; i++) {
      53      191528 :         uint64_t n = carry + (uint64_t)b32 * pn[i];
      54      191528 :         pn[i] = n & 0xffffffff;
      55      191528 :         carry = n >> 32;
      56      191528 :     }
      57       23941 :     return *this;
      58             : }
      59             : 
      60             : template <unsigned int BITS>
      61        1434 : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
      62             : {
      63        1434 :     base_uint<BITS> a;
      64       12906 :     for (int j = 0; j < WIDTH; j++) {
      65       11472 :         uint64_t carry = 0;
      66       63096 :         for (int i = 0; i + j < WIDTH; i++) {
      67       51624 :             uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
      68       51624 :             a.pn[i + j] = n & 0xffffffff;
      69       51624 :             carry = n >> 32;
      70       51624 :         }
      71       11472 :     }
      72        1434 :     *this = a;
      73        1434 :     return *this;
      74             : }
      75             : 
      76             : template <unsigned int BITS>
      77          73 : base_uint<BITS>& base_uint<BITS>::operator/=(uint64_t b32)
      78             : {
      79          73 :     if (b32 == 0)
      80           1 :         throw uint_error("Division by zero");
      81          72 :     if (b32 > std::numeric_limits<uint32_t>::max()) {
      82           6 :         return *this /= base_uint(b32);
      83             :     }
      84          66 :     uint64_t rem = 0;
      85         594 :     for (int i = WIDTH - 1; i >= 0; --i) {
      86         528 :         uint64_t cur = (rem << 32) | pn[i];
      87         528 :         pn[i] = static_cast<uint32_t>(cur / b32);
      88         528 :         rem = cur % b32;
      89         528 :     }
      90          66 :     return *this;
      91          73 : }
      92             : 
      93             : template <unsigned int BITS>
      94      630773 : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
      95             : {
      96      630773 :     base_uint<BITS> div = b;     // make a copy, so we can shift.
      97      630773 :     base_uint<BITS> num = *this; // make a copy, so we can subtract.
      98      630773 :     *this = 0;                   // the quotient.
      99      630773 :     int num_bits = num.bits();
     100      630773 :     int div_bits = div.bits();
     101      630773 :     if (div_bits == 0)
     102           2 :         throw uint_error("Division by zero");
     103      630771 :     if (div_bits > num_bits) // the result is certainly 0.
     104           1 :         return *this;
     105      630770 :     int shift = num_bits - div_bits;
     106      630770 :     div <<= shift; // shift so that div and num align.
     107     1946835 :     while (shift >= 0) {
     108     1316065 :         if (num >= div) {
     109      651227 :             num -= div;
     110      651227 :             pn[shift / 32] |= (1U << (shift & 31)); // set a bit of the result.
     111      651227 :         }
     112     1316065 :         div >>= 1; // shift back.
     113     1316065 :         shift--;
     114             :     }
     115             :     // num now contains the remainder of the division.
     116      630770 :     return *this;
     117      630773 : }
     118             : 
     119             : template <unsigned int BITS>
     120  1739515735 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
     121             : {
     122 13889110074 :     for (int i = WIDTH - 1; i >= 0; i--) {
     123 13872411430 :         if (pn[i] < b.pn[i])
     124  1248437599 :             return -1;
     125 12623973831 :         if (pn[i] > b.pn[i])
     126   474379492 :             return 1;
     127 12149594339 :     }
     128    16698644 :     return 0;
     129  1739515735 : }
     130             : 
     131             : template <unsigned int BITS>
     132     2989906 : bool base_uint<BITS>::EqualTo(uint64_t b) const
     133             : {
     134     2991112 :     for (int i = WIDTH - 1; i >= 2; i--) {
     135     2990991 :         if (pn[i])
     136     2989785 :             return false;
     137        1206 :     }
     138         121 :     if (pn[1] != (b >> 32))
     139          32 :         return false;
     140          89 :     if (pn[0] != (b & 0xfffffffful))
     141          32 :         return false;
     142          57 :     return true;
     143     2989906 : }
     144             : 
     145             : template <unsigned int BITS>
     146      271573 : double base_uint<BITS>::getdouble() const
     147             : {
     148      271573 :     double ret = 0.0;
     149      271573 :     double fact = 1.0;
     150     2444157 :     for (int i = 0; i < WIDTH; i++) {
     151     2172584 :         ret += fact * pn[i];
     152     2172584 :         fact *= 4294967296.0;
     153     2172584 :     }
     154      271573 :     return ret;
     155             : }
     156             : 
     157             : template <unsigned int BITS>
     158       30749 : std::string base_uint<BITS>::GetHex() const
     159             : {
     160       30749 :     base_blob<BITS> b;
     161      276741 :     for (int x = 0; x < this->WIDTH; ++x) {
     162      245992 :         WriteLE32(b.begin() + x*4, this->pn[x]);
     163      245992 :     }
     164       30749 :     return b.GetHex();
     165             : }
     166             : 
     167             : template <unsigned int BITS>
     168          26 : std::string base_uint<BITS>::ToString() const
     169             : {
     170          26 :     return GetHex();
     171             : }
     172             : 
     173             : template <unsigned int BITS>
     174     1797387 : unsigned int base_uint<BITS>::bits() const
     175             : {
     176     1827627 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
     177     1827613 :         if (pn[pos]) {
     178     3077836 :             for (int nbits = 31; nbits > 0; nbits--) {
     179     3077825 :                 if (pn[pos] & 1U << nbits)
     180     1797362 :                     return 32 * pos + nbits + 1;
     181     1280463 :             }
     182          11 :             return 32 * pos + 1;
     183             :         }
     184       30240 :     }
     185          14 :     return 0;
     186     1797387 : }
     187             : 
     188             : // Explicit instantiations for base_uint<256>
     189             : template class base_uint<256>;
     190             : 
     191             : // This implementation directly uses shifts instead of going
     192             : // through an intermediate MPI representation.
     193     2994066 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
     194             : {
     195     2994066 :     int nSize = nCompact >> 24;
     196     2994066 :     uint32_t nWord = nCompact & 0x007fffff;
     197     2994066 :     if (nSize <= 3) {
     198          62 :         nWord >>= 8 * (3 - nSize);
     199          62 :         *this = nWord;
     200          62 :     } else {
     201     2994004 :         *this = nWord;
     202     2994004 :         *this <<= 8 * (nSize - 3);
     203             :     }
     204     2994066 :     if (pfNegative)
     205     2989669 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
     206     2994066 :     if (pfOverflow)
     207     5979273 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
     208     5979213 :                                      (nWord > 0xff && nSize > 33) ||
     209     2989609 :                                      (nWord > 0xffff && nSize > 32));
     210     2994066 :     return *this;
     211             : }
     212             : 
     213      534420 : uint32_t arith_uint256::GetCompact(bool fNegative) const
     214             : {
     215      534420 :     int nSize = (bits() + 7) / 8;
     216      534420 :     uint32_t nCompact = 0;
     217      534420 :     if (nSize <= 3) {
     218          17 :         nCompact = GetLow64() << 8 * (3 - nSize);
     219          17 :     } else {
     220      534403 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
     221      534403 :         nCompact = bn.GetLow64();
     222             :     }
     223             :     // The 0x00800000 bit denotes the sign.
     224             :     // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
     225      534420 :     if (nCompact & 0x00800000) {
     226           4 :         nCompact >>= 8;
     227           4 :         nSize++;
     228           4 :     }
     229      534420 :     assert((nCompact & ~0x007fffffU) == 0);
     230      534420 :     assert(nSize < 256);
     231      534420 :     nCompact |= nSize << 24;
     232      534420 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
     233      534420 :     return nCompact;
     234             : }
     235             : 
     236      250072 : uint256 ArithToUint256(const arith_uint256 &a)
     237             : {
     238      250072 :     uint256 b;
     239     2250648 :     for(int x=0; x<a.WIDTH; ++x)
     240     2000576 :         WriteLE32(b.begin() + x*4, a.pn[x]);
     241      250072 :     return b;
     242             : }
     243     6098500 : arith_uint256 UintToArith256(const uint256 &a)
     244             : {
     245     6098500 :     arith_uint256 b;
     246    54886258 :     for(int x=0; x<b.WIDTH; ++x)
     247    48787758 :         b.pn[x] = ReadLE32(a.begin() + x*4);
     248     6098500 :     return b;
     249             : }