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                 :       1194 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
      22                 :            : {
      23                 :       1194 :     base_uint<BITS> a(*this);
      24         [ +  + ]:      10746 :     for (int i = 0; i < WIDTH; i++)
      25                 :       9552 :         pn[i] = 0;
      26                 :       1194 :     int k = shift / 32;
      27                 :       1194 :     shift = shift % 32;
      28         [ +  + ]:      10746 :     for (int i = 0; i < WIDTH; i++) {
      29 [ +  + ][ -  + ]:       9552 :         if (i + k + 1 < WIDTH && shift != 0)
      30                 :       1407 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
      31         [ +  + ]:       9552 :         if (i + k < WIDTH)
      32                 :       2601 :             pn[i + k] |= (a.pn[i] << shift);
      33                 :       9552 :     }
      34                 :       1194 :     return *this;
      35                 :            : }
      36                 :            : 
      37                 :            : template <unsigned int BITS>
      38                 :       1202 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
      39                 :            : {
      40                 :       1202 :     base_uint<BITS> a(*this);
      41         [ +  + ]:      10818 :     for (int i = 0; i < WIDTH; i++)
      42                 :       9616 :         pn[i] = 0;
      43                 :       1202 :     int k = shift / 32;
      44                 :       1202 :     shift = shift % 32;
      45         [ +  + ]:      10818 :     for (int i = 0; i < WIDTH; i++) {
      46 [ +  + ][ -  + ]:       9616 :         if (i - k - 1 >= 0 && shift != 0)
      47                 :       2814 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
      48         [ +  + ]:       9616 :         if (i - k >= 0)
      49                 :       4016 :             pn[i - k] |= (a.pn[i] >> shift);
      50                 :       9616 :     }
      51                 :       1202 :     return *this;
      52                 :            : }
      53                 :            : 
      54                 :            : template <unsigned int BITS>
      55                 :          0 : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
      56                 :            : {
      57                 :          0 :     uint64_t carry = 0;
      58         [ #  # ]:          0 :     for (int i = 0; i < WIDTH; i++) {
      59                 :          0 :         uint64_t n = carry + (uint64_t)b32 * pn[i];
      60                 :          0 :         pn[i] = n & 0xffffffff;
      61                 :          0 :         carry = n >> 32;
      62                 :          0 :     }
      63                 :          0 :     return *this;
      64                 :            : }
      65                 :            : 
      66                 :            : template <unsigned int BITS>
      67                 :          0 : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
      68                 :            : {
      69                 :          0 :     base_uint<BITS> a;
      70         [ #  # ]:          0 :     for (int j = 0; j < WIDTH; j++) {
      71                 :          0 :         uint64_t carry = 0;
      72         [ #  # ]:          0 :         for (int i = 0; i + j < WIDTH; i++) {
      73                 :          0 :             uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
      74                 :          0 :             a.pn[i + j] = n & 0xffffffff;
      75                 :          0 :             carry = n >> 32;
      76                 :          0 :         }
      77                 :          0 :     }
      78                 :          0 :     *this = a;
      79                 :          0 :     return *this;
      80                 :            : }
      81                 :            : 
      82                 :            : template <unsigned int BITS>
      83                 :        201 : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
      84                 :            : {
      85                 :        201 :     base_uint<BITS> div = b;     // make a copy, so we can shift.
      86                 :        201 :     base_uint<BITS> num = *this; // make a copy, so we can subtract.
      87                 :        201 :     *this = 0;                   // the quotient.
      88                 :        201 :     int num_bits = num.bits();
      89                 :        201 :     int div_bits = div.bits();
      90         [ +  - ]:        201 :     if (div_bits == 0)
      91 [ #  # ][ #  # ]:          0 :         throw uint_error("Division by zero");
         [ #  # ][ #  # ]
      92         [ -  + ]:        201 :     if (div_bits > num_bits) // the result is certainly 0.
      93                 :          0 :         return *this;
      94                 :        201 :     int shift = num_bits - div_bits;
      95                 :        201 :     div <<= shift; // shift so that div and num align.
      96         [ +  + ]:        603 :     while (shift >= 0) {
      97         [ +  + ]:        402 :         if (num >= div) {
      98                 :        201 :             num -= div;
      99                 :        201 :             pn[shift / 32] |= (1U << (shift & 31)); // set a bit of the result.
     100                 :        201 :         }
     101                 :        402 :         div >>= 1; // shift back.
     102                 :        402 :         shift--;
     103                 :            :     }
     104                 :            :     // num now contains the remainder of the division.
     105                 :        201 :     return *this;
     106                 :        201 : }
     107                 :            : 
     108                 :            : template <unsigned int BITS>
     109                 :     371400 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
     110                 :            : {
     111         [ +  + ]:    2962107 :     for (int i = WIDTH - 1; i >= 0; i--) {
     112         [ +  + ]:    2957298 :         if (pn[i] < b.pn[i])
     113                 :     242995 :             return -1;
     114         [ +  + ]:    2714303 :         if (pn[i] > b.pn[i])
     115                 :     123596 :             return 1;
     116                 :    2590707 :     }
     117                 :       4809 :     return 0;
     118                 :     371400 : }
     119                 :            : 
     120                 :            : template <unsigned int BITS>
     121                 :        993 : bool base_uint<BITS>::EqualTo(uint64_t b) const
     122                 :            : {
     123         [ +  - ]:        993 :     for (int i = WIDTH - 1; i >= 2; i--) {
     124         [ -  + ]:        993 :         if (pn[i])
     125                 :        993 :             return false;
     126                 :          0 :     }
     127         [ #  # ]:          0 :     if (pn[1] != (b >> 32))
     128                 :          0 :         return false;
     129         [ #  # ]:          0 :     if (pn[0] != (b & 0xfffffffful))
     130                 :          0 :         return false;
     131                 :          0 :     return true;
     132                 :        993 : }
     133                 :            : 
     134                 :            : template <unsigned int BITS>
     135                 :        201 : double base_uint<BITS>::getdouble() const
     136                 :            : {
     137                 :        201 :     double ret = 0.0;
     138                 :        201 :     double fact = 1.0;
     139         [ +  + ]:       1809 :     for (int i = 0; i < WIDTH; i++) {
     140                 :       1608 :         ret += fact * pn[i];
     141                 :       1608 :         fact *= 4294967296.0;
     142                 :       1608 :     }
     143                 :        201 :     return ret;
     144                 :            : }
     145                 :            : 
     146                 :            : template <unsigned int BITS>
     147                 :          1 : std::string base_uint<BITS>::GetHex() const
     148                 :            : {
     149                 :          1 :     base_blob<BITS> b;
     150         [ +  + ]:          9 :     for (int x = 0; x < this->WIDTH; ++x) {
     151                 :          8 :         WriteLE32(b.begin() + x*4, this->pn[x]);
     152                 :          8 :     }
     153                 :          1 :     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                 :          0 : std::string base_uint<BITS>::ToString() const
     174                 :            : {
     175                 :          0 :     return GetHex();
     176                 :            : }
     177                 :            : 
     178                 :            : template <unsigned int BITS>
     179                 :       1202 : unsigned int base_uint<BITS>::bits() const
     180                 :            : {
     181         [ +  - ]:       1202 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
     182         [ -  + ]:       1202 :         if (pn[pos]) {
     183         [ +  - ]:       2203 :             for (int nbits = 31; nbits > 0; nbits--) {
     184         [ +  + ]:       2203 :                 if (pn[pos] & 1U << nbits)
     185                 :       1202 :                     return 32 * pos + nbits + 1;
     186                 :       1001 :             }
     187                 :          0 :             return 32 * pos + 1;
     188                 :            :         }
     189                 :          0 :     }
     190                 :          0 :     return 0;
     191                 :       1202 : }
     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                 :        993 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
     199                 :            : {
     200                 :        993 :     int nSize = nCompact >> 24;
     201                 :        993 :     uint32_t nWord = nCompact & 0x007fffff;
     202         [ -  + ]:        993 :     if (nSize <= 3) {
     203                 :          0 :         nWord >>= 8 * (3 - nSize);
     204                 :          0 :         *this = nWord;
     205                 :          0 :     } else {
     206                 :        993 :         *this = nWord;
     207                 :        993 :         *this <<= 8 * (nSize - 3);
     208                 :            :     }
     209         [ -  + ]:        993 :     if (pfNegative)
     210         [ -  + ]:        993 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
     211         [ -  + ]:        993 :     if (pfOverflow)
     212 [ -  + ][ +  - ]:       1986 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
     213 [ +  - ][ -  + ]:       1986 :                                      (nWord > 0xff && nSize > 33) ||
     214         [ -  + ]:        993 :                                      (nWord > 0xffff && nSize > 32));
     215                 :        993 :     return *this;
     216                 :            : }
     217                 :            : 
     218                 :        800 : uint32_t arith_uint256::GetCompact(bool fNegative) const
     219                 :            : {
     220                 :        800 :     int nSize = (bits() + 7) / 8;
     221                 :        800 :     uint32_t nCompact = 0;
     222         [ -  + ]:        800 :     if (nSize <= 3) {
     223                 :          0 :         nCompact = GetLow64() << 8 * (3 - nSize);
     224                 :          0 :     } else {
     225                 :        800 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
     226                 :        800 :         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         [ +  - ]:        800 :     if (nCompact & 0x00800000) {
     231                 :          0 :         nCompact >>= 8;
     232                 :          0 :         nSize++;
     233                 :          0 :     }
     234         [ +  - ]:        800 :     assert((nCompact & ~0x007fffffU) == 0);
     235         [ -  + ]:        800 :     assert(nSize < 256);
     236                 :        800 :     nCompact |= nSize << 24;
     237         [ +  - ]:        800 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
     238                 :        800 :     return nCompact;
     239                 :            : }
     240                 :            : 
     241                 :          0 : uint256 ArithToUint256(const arith_uint256 &a)
     242                 :            : {
     243                 :          0 :     uint256 b;
     244         [ #  # ]:          0 :     for(int x=0; x<a.WIDTH; ++x)
     245                 :          0 :         WriteLE32(b.begin() + x*4, a.pn[x]);
     246                 :          0 :     return b;
     247                 :            : }
     248                 :       2386 : arith_uint256 UintToArith256(const uint256 &a)
     249                 :            : {
     250                 :       2386 :     arith_uint256 b;
     251         [ +  + ]:      21474 :     for(int x=0; x<b.WIDTH; ++x)
     252                 :      19088 :         b.pn[x] = ReadLE32(a.begin() + x*4);
     253                 :       2386 :     return b;
     254                 :            : }