Branch data     Line data    Source code

       1                 :            : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2                 :            : // Copyright (c) 2009-2022 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 <uint256.h>
       9                 :            : #include <crypto/common.h>
      10                 :            : 
      11                 :            : 
      12                 :            : template <unsigned int BITS>
      13                 :          0 : base_uint<BITS>::base_uint(const std::string& str)
      14                 :            : {
      15                 :            :     static_assert(BITS/32 > 0 && BITS%32 == 0, "Template parameter BITS must be a positive multiple of 32.");
      16                 :            : 
      17                 :          0 :     SetHex(str);
      18                 :          0 : }
      19                 :            : 
      20                 :            : template <unsigned int BITS>
      21                 :    1147968 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
      22                 :            : {
      23                 :    1147968 :     base_uint<BITS> a(*this);
      24         [ +  + ]:   10331712 :     for (int i = 0; i < WIDTH; i++)
      25                 :    9183744 :         pn[i] = 0;
      26                 :    1147968 :     int k = shift / 32;
      27                 :    1147968 :     shift = shift % 32;
      28         [ +  + ]:   10331712 :     for (int i = 0; i < WIDTH; i++) {
      29   [ +  +  +  + ]:    9183744 :         if (i + k + 1 < WIDTH && shift != 0)
      30                 :    1502402 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
      31         [ +  + ]:    9183744 :         if (i + k < WIDTH)
      32                 :    2875910 :             pn[i + k] |= (a.pn[i] << shift);
      33                 :    9183744 :     }
      34                 :    1147968 :     return *this;
      35                 :            : }
      36                 :            : 
      37                 :            : template <unsigned int BITS>
      38                 :   14788929 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
      39                 :            : {
      40                 :   14788929 :     base_uint<BITS> a(*this);
      41         [ +  + ]:  133100361 :     for (int i = 0; i < WIDTH; i++)
      42                 :  118311432 :         pn[i] = 0;
      43                 :   14788929 :     int k = shift / 32;
      44                 :   14788929 :     shift = shift % 32;
      45         [ +  + ]:  133100361 :     for (int i = 0; i < WIDTH; i++) {
      46   [ +  +  +  + ]:  118311432 :         if (i - k - 1 >= 0 && shift != 0)
      47                 :  101555297 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
      48         [ +  + ]:  118311432 :         if (i - k >= 0)
      49                 :  116360814 :             pn[i - k] |= (a.pn[i] >> shift);
      50                 :  118311432 :     }
      51                 :   14788929 :     return *this;
      52                 :            : }
      53                 :            : 
      54                 :            : template <unsigned int BITS>
      55                 :      88798 : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
      56                 :            : {
      57                 :      88798 :     uint64_t carry = 0;
      58         [ +  + ]:     799182 :     for (int i = 0; i < WIDTH; i++) {
      59                 :     710384 :         uint64_t n = carry + (uint64_t)b32 * pn[i];
      60                 :     710384 :         pn[i] = n & 0xffffffff;
      61                 :     710384 :         carry = n >> 32;
      62                 :     710384 :     }
      63                 :      88798 :     return *this;
      64                 :            : }
      65                 :            : 
      66                 :            : template <unsigned int BITS>
      67                 :     109948 : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
      68                 :            : {
      69                 :     109948 :     base_uint<BITS> a;
      70         [ +  + ]:     989532 :     for (int j = 0; j < WIDTH; j++) {
      71                 :     879584 :         uint64_t carry = 0;
      72         [ +  + ]:    4837712 :         for (int i = 0; i + j < WIDTH; i++) {
      73                 :    3958128 :             uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
      74                 :    3958128 :             a.pn[i + j] = n & 0xffffffff;
      75                 :    3958128 :             carry = n >> 32;
      76                 :    3958128 :         }
      77                 :     879584 :     }
      78                 :     109948 :     *this = a;
      79                 :     109948 :     return *this;
      80                 :            : }
      81                 :            : 
      82                 :            : template <unsigned int BITS>
      83                 :     423090 : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
      84                 :            : {
      85                 :     423090 :     base_uint<BITS> div = b;     // make a copy, so we can shift.
      86                 :     423090 :     base_uint<BITS> num = *this; // make a copy, so we can subtract.
      87                 :     423090 :     *this = 0;                   // the quotient.
      88                 :     423090 :     int num_bits = num.bits();
      89                 :     423090 :     int div_bits = div.bits();
      90         [ +  + ]:     423090 :     if (div_bits == 0)
      91   [ +  -  +  -  :      60745 :         throw uint_error("Division by zero");
             -  +  +  - ]
      92         [ +  + ]:     362345 :     if (div_bits > num_bits) // the result is certainly 0.
      93                 :      77777 :         return *this;
      94                 :     284568 :     int shift = num_bits - div_bits;
      95                 :     284568 :     div <<= shift; // shift so that div and num align.
      96         [ +  + ]:   14784899 :     while (shift >= 0) {
      97         [ +  + ]:   14500331 :         if (num >= div) {
      98                 :    5679628 :             num -= div;
      99                 :    5679628 :             pn[shift / 32] |= (1U << (shift & 31)); // set a bit of the result.
     100                 :    5679628 :         }
     101                 :   14500331 :         div >>= 1; // shift back.
     102                 :   14500331 :         shift--;
     103                 :            :     }
     104                 :            :     // num now contains the remainder of the division.
     105                 :     284568 :     return *this;
     106                 :     423090 : }
     107                 :            : 
     108                 :            : template <unsigned int BITS>
     109                 :  152032043 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
     110                 :            : {
     111         [ +  + ]: 1142954159 :     for (int i = WIDTH - 1; i >= 0; i--) {
     112         [ +  + ]: 1141080519 :         if (pn[i] < b.pn[i])
     113                 :   92728943 :             return -1;
     114         [ +  + ]: 1048351576 :         if (pn[i] > b.pn[i])
     115                 :   57429460 :             return 1;
     116                 :  990922116 :     }
     117                 :    1873640 :     return 0;
     118                 :  152032043 : }
     119                 :            : 
     120                 :            : template <unsigned int BITS>
     121                 :     653276 : bool base_uint<BITS>::EqualTo(uint64_t b) const
     122                 :            : {
     123         [ +  + ]:    1323533 :     for (int i = WIDTH - 1; i >= 2; i--) {
     124         [ +  + ]:    1245972 :         if (pn[i])
     125                 :     575715 :             return false;
     126                 :     670257 :     }
     127         [ +  + ]:      77561 :     if (pn[1] != (b >> 32))
     128                 :       7514 :         return false;
     129         [ +  + ]:      70047 :     if (pn[0] != (b & 0xfffffffful))
     130                 :       9834 :         return false;
     131                 :      60213 :     return true;
     132                 :     653276 : }
     133                 :            : 
     134                 :            : template <unsigned int BITS>
     135                 :      56888 : double base_uint<BITS>::getdouble() const
     136                 :            : {
     137                 :      56888 :     double ret = 0.0;
     138                 :      56888 :     double fact = 1.0;
     139         [ +  + ]:     511992 :     for (int i = 0; i < WIDTH; i++) {
     140                 :     455104 :         ret += fact * pn[i];
     141                 :     455104 :         fact *= 4294967296.0;
     142                 :     455104 :     }
     143                 :      56888 :     return ret;
     144                 :            : }
     145                 :            : 
     146                 :            : template <unsigned int BITS>
     147                 :       1032 : std::string base_uint<BITS>::GetHex() const
     148                 :            : {
     149                 :       1032 :     base_blob<BITS> b;
     150         [ +  + ]:       9288 :     for (int x = 0; x < this->WIDTH; ++x) {
     151                 :       8256 :         WriteLE32(b.begin() + x*4, this->pn[x]);
     152                 :       8256 :     }
     153                 :       1032 :     return b.GetHex();
     154                 :            : }
     155                 :            : 
     156                 :            : template <unsigned int BITS>
     157                 :          0 : void base_uint<BITS>::SetHex(const char* psz)
     158                 :            : {
     159                 :          0 :     base_blob<BITS> b;
     160                 :          0 :     b.SetHex(psz);
     161         [ #  # ]:          0 :     for (int x = 0; x < this->WIDTH; ++x) {
     162                 :          0 :         this->pn[x] = ReadLE32(b.begin() + x*4);
     163                 :          0 :     }
     164                 :          0 : }
     165                 :            : 
     166                 :            : template <unsigned int BITS>
     167                 :          0 : void base_uint<BITS>::SetHex(const std::string& str)
     168                 :            : {
     169                 :          0 :     SetHex(str.c_str());
     170                 :          0 : }
     171                 :            : 
     172                 :            : template <unsigned int BITS>
     173                 :         65 : std::string base_uint<BITS>::ToString() const
     174                 :            : {
     175                 :         65 :     return GetHex();
     176                 :            : }
     177                 :            : 
     178                 :            : template <unsigned int BITS>
     179                 :    1227357 : unsigned int base_uint<BITS>::bits() const
     180                 :            : {
     181         [ +  + ]:    4381850 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
     182         [ +  + ]:    4134645 :         if (pn[pos]) {
     183         [ +  + ]:    4681555 :             for (int nbits = 31; nbits > 0; nbits--) {
     184         [ +  + ]:    4670246 :                 if (pn[pos] & 1U << nbits)
     185                 :     968843 :                     return 32 * pos + nbits + 1;
     186                 :    3701403 :             }
     187                 :      11309 :             return 32 * pos + 1;
     188                 :            :         }
     189                 :    3154493 :     }
     190                 :     247205 :     return 0;
     191                 :    1227357 : }
     192                 :            : 
     193                 :            : // Explicit instantiations for base_uint<256>
     194                 :            : template class base_uint<256>;
     195                 :            : 
     196                 :            : // This implementation directly uses shifts instead of going
     197                 :            : // through an intermediate MPI representation.
     198                 :     927217 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
     199                 :            : {
     200                 :     927217 :     int nSize = nCompact >> 24;
     201                 :     927217 :     uint32_t nWord = nCompact & 0x007fffff;
     202         [ +  + ]:     927217 :     if (nSize <= 3) {
     203                 :      63817 :         nWord >>= 8 * (3 - nSize);
     204                 :      63817 :         *this = nWord;
     205                 :      63817 :     } else {
     206                 :     863400 :         *this = nWord;
     207                 :     863400 :         *this <<= 8 * (nSize - 3);
     208                 :            :     }
     209         [ +  + ]:     927217 :     if (pfNegative)
     210         [ +  + ]:     837822 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
     211         [ +  + ]:     927217 :     if (pfOverflow)
     212   [ +  +  +  + ]:    1629967 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
     213   [ +  +  +  + ]:    1197664 :                                      (nWord > 0xff && nSize > 33) ||
     214         [ +  + ]:     598224 :                                      (nWord > 0xffff && nSize > 32));
     215                 :     927217 :     return *this;
     216                 :            : }
     217                 :            : 
     218                 :     353500 : uint32_t arith_uint256::GetCompact(bool fNegative) const
     219                 :            : {
     220                 :     353500 :     int nSize = (bits() + 7) / 8;
     221                 :     353500 :     uint32_t nCompact = 0;
     222         [ +  + ]:     353500 :     if (nSize <= 3) {
     223                 :      64902 :         nCompact = GetLow64() << 8 * (3 - nSize);
     224                 :      64902 :     } else {
     225                 :     288598 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
     226                 :     288598 :         nCompact = bn.GetLow64();
     227                 :            :     }
     228                 :            :     // The 0x00800000 bit denotes the sign.
     229                 :            :     // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
     230         [ +  + ]:     353500 :     if (nCompact & 0x00800000) {
     231                 :       5222 :         nCompact >>= 8;
     232                 :       5222 :         nSize++;
     233                 :       5222 :     }
     234         [ +  - ]:     353500 :     assert((nCompact & ~0x007fffffU) == 0);
     235         [ -  + ]:     353500 :     assert(nSize < 256);
     236                 :     353500 :     nCompact |= nSize << 24;
     237         [ +  + ]:     353500 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
     238                 :     353500 :     return nCompact;
     239                 :            : }
     240                 :            : 
     241                 :         65 : uint256 ArithToUint256(const arith_uint256 &a)
     242                 :            : {
     243                 :         65 :     uint256 b;
     244         [ +  + ]:        585 :     for(int x=0; x<a.WIDTH; ++x)
     245                 :        520 :         WriteLE32(b.begin() + x*4, a.pn[x]);
     246                 :         65 :     return b;
     247                 :            : }
     248                 :    1083703 : arith_uint256 UintToArith256(const uint256 &a)
     249                 :            : {
     250                 :    1083703 :     arith_uint256 b;
     251         [ +  + ]:    9753327 :     for(int x=0; x<b.WIDTH; ++x)
     252                 :    8669624 :         b.pn[x] = ReadLE32(a.begin() + x*4);
     253                 :    1083703 :     return b;
     254                 :            : }