Branch data     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 <uint256.h>
#       9                 :            : #include <crypto/common.h>
#      10                 :            : 
#      11                 :            : 
#      12                 :            : template <unsigned int BITS>
#      13                 :            : base_uint<BITS>::base_uint(const std::string& str)
#      14                 :         38 : {
#      15                 :         38 :     static_assert(BITS/32 > 0 && BITS%32 == 0, "Template parameter BITS must be a positive multiple of 32.");
#      16                 :            : 
#      17                 :         38 :     SetHex(str);
#      18                 :         38 : }
#      19                 :            : 
#      20                 :            : template <unsigned int BITS>
#      21                 :            : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
#      22                 :    1324168 : {
#      23                 :    1324168 :     base_uint<BITS> a(*this);
#      24         [ +  + ]:   11917512 :     for (int i = 0; i < WIDTH; i++)
#      25                 :   10593344 :         pn[i] = 0;
#      26                 :    1324168 :     int k = shift / 32;
#      27                 :    1324168 :     shift = shift % 32;
#      28         [ +  + ]:   11917512 :     for (int i = 0; i < WIDTH; i++) {
#      29 [ +  + ][ +  + ]:   10593344 :         if (i + k + 1 < WIDTH && shift != 0)
#      30                 :    1781369 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
#      31         [ +  + ]:   10593344 :         if (i + k < WIDTH)
#      32                 :    3415281 :             pn[i + k] |= (a.pn[i] << shift);
#      33                 :   10593344 :     }
#      34                 :    1324168 :     return *this;
#      35                 :    1324168 : }
#      36                 :            : 
#      37                 :            : template <unsigned int BITS>
#      38                 :            : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
#      39                 :     634981 : {
#      40                 :     634981 :     base_uint<BITS> a(*this);
#      41         [ +  + ]:    5714829 :     for (int i = 0; i < WIDTH; i++)
#      42                 :    5079848 :         pn[i] = 0;
#      43                 :     634981 :     int k = shift / 32;
#      44                 :     634981 :     shift = shift % 32;
#      45         [ +  + ]:    5714829 :     for (int i = 0; i < WIDTH; i++) {
#      46 [ +  + ][ +  + ]:    5079848 :         if (i - k - 1 >= 0 && shift != 0)
#      47                 :    3329170 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
#      48         [ +  + ]:    5079848 :         if (i - k >= 0)
#      49                 :    3965673 :             pn[i - k] |= (a.pn[i] >> shift);
#      50                 :    5079848 :     }
#      51                 :     634981 :     return *this;
#      52                 :     634981 : }
#      53                 :            : 
#      54                 :            : template <unsigned int BITS>
#      55                 :            : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
#      56                 :      17292 : {
#      57                 :      17292 :     uint64_t carry = 0;
#      58         [ +  + ]:     155628 :     for (int i = 0; i < WIDTH; i++) {
#      59                 :     138336 :         uint64_t n = carry + (uint64_t)b32 * pn[i];
#      60                 :     138336 :         pn[i] = n & 0xffffffff;
#      61                 :     138336 :         carry = n >> 32;
#      62                 :     138336 :     }
#      63                 :      17292 :     return *this;
#      64                 :      17292 : }
#      65                 :            : 
#      66                 :            : template <unsigned int BITS>
#      67                 :            : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
#      68                 :       2237 : {
#      69                 :       2237 :     base_uint<BITS> a;
#      70         [ +  + ]:      20133 :     for (int j = 0; j < WIDTH; j++) {
#      71                 :      17896 :         uint64_t carry = 0;
#      72         [ +  + ]:      98428 :         for (int i = 0; i + j < WIDTH; i++) {
#      73                 :      80532 :             uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
#      74                 :      80532 :             a.pn[i + j] = n & 0xffffffff;
#      75                 :      80532 :             carry = n >> 32;
#      76                 :      80532 :         }
#      77                 :      17896 :     }
#      78                 :       2237 :     *this = a;
#      79                 :       2237 :     return *this;
#      80                 :       2237 : }
#      81                 :            : 
#      82                 :            : template <unsigned int BITS>
#      83                 :            : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
#      84                 :     188138 : {
#      85                 :     188138 :     base_uint<BITS> div = b;     // make a copy, so we can shift.
#      86                 :     188138 :     base_uint<BITS> num = *this; // make a copy, so we can subtract.
#      87                 :     188138 :     *this = 0;                   // the quotient.
#      88                 :     188138 :     int num_bits = num.bits();
#      89                 :     188138 :     int div_bits = div.bits();
#      90         [ +  + ]:     188138 :     if (div_bits == 0)
#      91                 :          4 :         throw uint_error("Division by zero");
#      92         [ +  + ]:     188134 :     if (div_bits > num_bits) // the result is certainly 0.
#      93                 :          2 :         return *this;
#      94                 :     188132 :     int shift = num_bits - div_bits;
#      95                 :     188132 :     div <<= shift; // shift so that div and num align.
#      96         [ +  + ]:     656205 :     while (shift >= 0) {
#      97         [ +  + ]:     468073 :         if (num >= div) {
#      98                 :     210535 :             num -= div;
#      99                 :     210535 :             pn[shift / 32] |= (1U << (shift & 31)); // set a bit of the result.
#     100                 :     210535 :         }
#     101                 :     468073 :         div >>= 1; // shift back.
#     102                 :     468073 :         shift--;
#     103                 :     468073 :     }
#     104                 :            :     // num now contains the remainder of the division.
#     105                 :     188132 :     return *this;
#     106                 :     188134 : }
#     107                 :            : 
#     108                 :            : template <unsigned int BITS>
#     109                 :            : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
#     110                 :  648320434 : {
#     111         [ +  + ]: 5099770102 :     for (int i = WIDTH - 1; i >= 0; i--) {
#     112         [ +  + ]: 5096045164 :         if (pn[i] < b.pn[i])
#     113                 :  465671262 :             return -1;
#     114         [ +  + ]: 4630373902 :         if (pn[i] > b.pn[i])
#     115                 :  178924234 :             return 1;
#     116                 : 4630373902 :     }
#     117                 :    3724938 :     return 0;
#     118                 :  648320434 : }
#     119                 :            : 
#     120                 :            : template <unsigned int BITS>
#     121                 :            : bool base_uint<BITS>::EqualTo(uint64_t b) const
#     122                 :    1025981 : {
#     123         [ +  + ]:    1030999 :     for (int i = WIDTH - 1; i >= 2; i--) {
#     124         [ +  + ]:    1030853 :         if (pn[i])
#     125                 :    1025835 :             return false;
#     126                 :    1030853 :     }
#     127         [ +  + ]:        146 :     if (pn[1] != (b >> 32))
#     128                 :         64 :         return false;
#     129         [ +  + ]:         82 :     if (pn[0] != (b & 0xfffffffful))
#     130                 :         64 :         return false;
#     131                 :         18 :     return true;
#     132                 :         82 : }
#     133                 :            : 
#     134                 :            : template <unsigned int BITS>
#     135                 :            : double base_uint<BITS>::getdouble() const
#     136                 :      82965 : {
#     137                 :      82965 :     double ret = 0.0;
#     138                 :      82965 :     double fact = 1.0;
#     139         [ +  + ]:     746685 :     for (int i = 0; i < WIDTH; i++) {
#     140                 :     663720 :         ret += fact * pn[i];
#     141                 :     663720 :         fact *= 4294967296.0;
#     142                 :     663720 :     }
#     143                 :      82965 :     return ret;
#     144                 :      82965 : }
#     145                 :            : 
#     146                 :            : template <unsigned int BITS>
#     147                 :            : std::string base_uint<BITS>::GetHex() const
#     148                 :       6877 : {
#     149                 :       6877 :     base_blob<BITS> b;
#     150         [ +  + ]:      61893 :     for (int x = 0; x < this->WIDTH; ++x) {
#     151                 :      55016 :         WriteLE32(b.begin() + x*4, this->pn[x]);
#     152                 :      55016 :     }
#     153                 :       6877 :     return b.GetHex();
#     154                 :       6877 : }
#     155                 :            : 
#     156                 :            : template <unsigned int BITS>
#     157                 :            : void base_uint<BITS>::SetHex(const char* psz)
#     158                 :         46 : {
#     159                 :         46 :     base_blob<BITS> b;
#     160                 :         46 :     b.SetHex(psz);
#     161         [ +  + ]:        414 :     for (int x = 0; x < this->WIDTH; ++x) {
#     162                 :        368 :         this->pn[x] = ReadLE32(b.begin() + x*4);
#     163                 :        368 :     }
#     164                 :         46 : }
#     165                 :            : 
#     166                 :            : template <unsigned int BITS>
#     167                 :            : void base_uint<BITS>::SetHex(const std::string& str)
#     168                 :         46 : {
#     169                 :         46 :     SetHex(str.c_str());
#     170                 :         46 : }
#     171                 :            : 
#     172                 :            : template <unsigned int BITS>
#     173                 :            : std::string base_uint<BITS>::ToString() const
#     174                 :         60 : {
#     175                 :         60 :     return GetHex();
#     176                 :         60 : }
#     177                 :            : 
#     178                 :            : template <unsigned int BITS>
#     179                 :            : unsigned int base_uint<BITS>::bits() const
#     180                 :     530359 : {
#     181         [ +  + ]:     579606 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
#     182         [ +  + ]:     579578 :         if (pn[pos]) {
#     183         [ +  + ]:     981685 :             for (int nbits = 31; nbits > 0; nbits--) {
#     184         [ +  + ]:     981679 :                 if (pn[pos] & 1U << nbits)
#     185                 :     530325 :                     return 32 * pos + nbits + 1;
#     186                 :     981679 :             }
#     187                 :          6 :             return 32 * pos + 1;
#     188                 :     530331 :         }
#     189                 :     579578 :     }
#     190                 :         28 :     return 0;
#     191                 :     530359 : }
#     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                 :            : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
#     199                 :    1025561 : {
#     200                 :    1025561 :     int nSize = nCompact >> 24;
#     201                 :    1025561 :     uint32_t nWord = nCompact & 0x007fffff;
#     202         [ +  + ]:    1025561 :     if (nSize <= 3) {
#     203                 :         28 :         nWord >>= 8 * (3 - nSize);
#     204                 :         28 :         *this = nWord;
#     205                 :    1025533 :     } else {
#     206                 :    1025533 :         *this = nWord;
#     207                 :    1025533 :         *this <<= 8 * (nSize - 3);
#     208                 :    1025533 :     }
#     209         [ +  + ]:    1025561 :     if (pfNegative)
#     210 [ +  + ][ +  + ]:    1025497 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
#     211         [ +  + ]:    1025561 :     if (pfOverflow)
#     212 [ +  + ][ +  + ]:    1025497 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
#     213 [ +  + ][ -  + ]:    1025473 :                                      (nWord > 0xff && nSize > 33) ||
#     214 [ +  + ][ -  + ]:    1025473 :                                      (nWord > 0xffff && nSize > 32));
#     215                 :    1025561 :     return *this;
#     216                 :    1025561 : }
#     217                 :            : 
#     218                 :            : uint32_t arith_uint256::GetCompact(bool fNegative) const
#     219                 :     151872 : {
#     220                 :     151872 :     int nSize = (bits() + 7) / 8;
#     221                 :     151872 :     uint32_t nCompact = 0;
#     222         [ +  + ]:     151872 :     if (nSize <= 3) {
#     223                 :         34 :         nCompact = GetLow64() << 8 * (3 - nSize);
#     224                 :     151838 :     } else {
#     225                 :     151838 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
#     226                 :     151838 :         nCompact = bn.GetLow64();
#     227                 :     151838 :     }
#     228                 :            :     // The 0x00800000 bit denotes the sign.
#     229                 :            :     // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
#     230         [ +  + ]:     151872 :     if (nCompact & 0x00800000) {
#     231                 :        861 :         nCompact >>= 8;
#     232                 :        861 :         nSize++;
#     233                 :        861 :     }
#     234                 :     151872 :     assert((nCompact & ~0x007fffffU) == 0);
#     235                 :          0 :     assert(nSize < 256);
#     236                 :          0 :     nCompact |= nSize << 24;
#     237 [ +  + ][ +  - ]:     151872 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
#     238                 :     151872 :     return nCompact;
#     239                 :     151872 : }
#     240                 :            : 
#     241                 :            : uint256 ArithToUint256(const arith_uint256 &a)
#     242                 :     500042 : {
#     243                 :     500042 :     uint256 b;
#     244         [ +  + ]:    4500378 :     for(int x=0; x<a.WIDTH; ++x)
#     245                 :    4000336 :         WriteLE32(b.begin() + x*4, a.pn[x]);
#     246                 :     500042 :     return b;
#     247                 :     500042 : }
#     248                 :            : arith_uint256 UintToArith256(const uint256 &a)
#     249                 :   13290371 : {
#     250                 :   13290371 :     arith_uint256 b;
#     251         [ +  + ]:  119875587 :     for(int x=0; x<b.WIDTH; ++x)
#     252                 :  106585216 :         b.pn[x] = ReadLE32(a.begin() + x*4);
#     253                 :   13290371 :     return b;
#     254                 :   13290371 : }