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                 :    1245203 : {
#      23                 :    1245203 :     base_uint<BITS> a(*this);
#      24         [ +  + ]:   11206827 :     for (int i = 0; i < WIDTH; i++)
#      25                 :    9961624 :         pn[i] = 0;
#      26                 :    1245203 :     int k = shift / 32;
#      27                 :    1245203 :     shift = shift % 32;
#      28         [ +  + ]:   11206827 :     for (int i = 0; i < WIDTH; i++) {
#      29 [ +  + ][ +  + ]:    9961624 :         if (i + k + 1 < WIDTH && shift != 0)
#      30                 :    1646896 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
#      31         [ +  + ]:    9961624 :         if (i + k < WIDTH)
#      32                 :    3201831 :             pn[i + k] |= (a.pn[i] << shift);
#      33                 :    9961624 :     }
#      34                 :    1245203 :     return *this;
#      35                 :    1245203 : }
#      36                 :            : 
#      37                 :            : template <unsigned int BITS>
#      38                 :            : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
#      39                 :     613333 : {
#      40                 :     613333 :     base_uint<BITS> a(*this);
#      41         [ +  + ]:    5519997 :     for (int i = 0; i < WIDTH; i++)
#      42                 :    4906664 :         pn[i] = 0;
#      43                 :     613333 :     int k = shift / 32;
#      44                 :     613333 :     shift = shift % 32;
#      45         [ +  + ]:    5519997 :     for (int i = 0; i < WIDTH; i++) {
#      46 [ +  + ][ +  + ]:    4906664 :         if (i - k - 1 >= 0 && shift != 0)
#      47                 :    3107488 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
#      48         [ +  + ]:    4906664 :         if (i - k >= 0)
#      49                 :    3722343 :             pn[i - k] |= (a.pn[i] >> shift);
#      50                 :    4906664 :     }
#      51                 :     613333 :     return *this;
#      52                 :     613333 : }
#      53                 :            : 
#      54                 :            : template <unsigned int BITS>
#      55                 :            : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
#      56                 :      13343 : {
#      57                 :      13343 :     uint64_t carry = 0;
#      58         [ +  + ]:     120087 :     for (int i = 0; i < WIDTH; i++) {
#      59                 :     106744 :         uint64_t n = carry + (uint64_t)b32 * pn[i];
#      60                 :     106744 :         pn[i] = n & 0xffffffff;
#      61                 :     106744 :         carry = n >> 32;
#      62                 :     106744 :     }
#      63                 :      13343 :     return *this;
#      64                 :      13343 : }
#      65                 :            : 
#      66                 :            : template <unsigned int BITS>
#      67                 :            : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
#      68                 :       2236 : {
#      69                 :       2236 :     base_uint<BITS> a;
#      70         [ +  + ]:      20124 :     for (int j = 0; j < WIDTH; j++) {
#      71                 :      17888 :         uint64_t carry = 0;
#      72         [ +  + ]:      98384 :         for (int i = 0; i + j < WIDTH; i++) {
#      73                 :      80496 :             uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
#      74                 :      80496 :             a.pn[i + j] = n & 0xffffffff;
#      75                 :      80496 :             carry = n >> 32;
#      76                 :      80496 :         }
#      77                 :      17888 :     }
#      78                 :       2236 :     *this = a;
#      79                 :       2236 :     return *this;
#      80                 :       2236 : }
#      81                 :            : 
#      82                 :            : template <unsigned int BITS>
#      83                 :            : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
#      84                 :     172450 : {
#      85                 :     172450 :     base_uint<BITS> div = b;     // make a copy, so we can shift.
#      86                 :     172450 :     base_uint<BITS> num = *this; // make a copy, so we can subtract.
#      87                 :     172450 :     *this = 0;                   // the quotient.
#      88                 :     172450 :     int num_bits = num.bits();
#      89                 :     172450 :     int div_bits = div.bits();
#      90         [ +  + ]:     172450 :     if (div_bits == 0)
#      91                 :          4 :         throw uint_error("Division by zero");
#      92         [ +  + ]:     172446 :     if (div_bits > num_bits) // the result is certainly 0.
#      93                 :          2 :         return *this;
#      94                 :     172444 :     int shift = num_bits - div_bits;
#      95                 :     172444 :     div <<= shift; // shift so that div and num align.
#      96         [ +  + ]:     608849 :     while (shift >= 0) {
#      97         [ +  + ]:     436405 :         if (num >= div) {
#      98                 :     194596 :             num -= div;
#      99                 :     194596 :             pn[shift / 32] |= (1 << (shift & 31)); // set a bit of the result.
#     100                 :     194596 :         }
#     101                 :     436405 :         div >>= 1; // shift back.
#     102                 :     436405 :         shift--;
#     103                 :     436405 :     }
#     104                 :            :     // num now contains the remainder of the division.
#     105                 :     172444 :     return *this;
#     106                 :     172444 : }
#     107                 :            : 
#     108                 :            : template <unsigned int BITS>
#     109                 :            : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
#     110                 :  762304560 : {
#     111         [ +  + ]: 6091299843 :     for (int i = WIDTH - 1; i >= 0; i--) {
#     112         [ +  + ]: 6087301054 :         if (pn[i] < b.pn[i])
#     113                 :  564996474 :             return -1;
#     114         [ +  + ]: 5522304580 :         if (pn[i] > b.pn[i])
#     115                 :  193309297 :             return 1;
#     116                 : 5522304580 :     }
#     117                 :  762304560 :     return 0;
#     118                 :  762304560 : }
#     119                 :            : 
#     120                 :            : template <unsigned int BITS>
#     121                 :            : bool base_uint<BITS>::EqualTo(uint64_t b) const
#     122                 :     962708 : {
#     123         [ +  + ]:     967715 :     for (int i = WIDTH - 1; i >= 2; i--) {
#     124         [ +  + ]:     967569 :         if (pn[i])
#     125                 :     962562 :             return false;
#     126                 :     967569 :     }
#     127         [ +  + ]:     962708 :     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                 :         18 : }
#     133                 :            : 
#     134                 :            : template <unsigned int BITS>
#     135                 :            : double base_uint<BITS>::getdouble() const
#     136                 :      85117 : {
#     137                 :      85117 :     double ret = 0.0;
#     138                 :      85117 :     double fact = 1.0;
#     139         [ +  + ]:     766053 :     for (int i = 0; i < WIDTH; i++) {
#     140                 :     680936 :         ret += fact * pn[i];
#     141                 :     680936 :         fact *= 4294967296.0;
#     142                 :     680936 :     }
#     143                 :      85117 :     return ret;
#     144                 :      85117 : }
#     145                 :            : 
#     146                 :            : template <unsigned int BITS>
#     147                 :            : std::string base_uint<BITS>::GetHex() const
#     148                 :       7690 : {
#     149                 :       7690 :     return ArithToUint256(*this).GetHex();
#     150                 :       7690 : }
#     151                 :            : 
#     152                 :            : template <unsigned int BITS>
#     153                 :            : void base_uint<BITS>::SetHex(const char* psz)
#     154                 :         46 : {
#     155                 :         46 :     *this = UintToArith256(uint256S(psz));
#     156                 :         46 : }
#     157                 :            : 
#     158                 :            : template <unsigned int BITS>
#     159                 :            : void base_uint<BITS>::SetHex(const std::string& str)
#     160                 :         46 : {
#     161                 :         46 :     SetHex(str.c_str());
#     162                 :         46 : }
#     163                 :            : 
#     164                 :            : template <unsigned int BITS>
#     165                 :            : std::string base_uint<BITS>::ToString() const
#     166                 :         60 : {
#     167                 :         60 :     return (GetHex());
#     168                 :         60 : }
#     169                 :            : 
#     170                 :            : template <unsigned int BITS>
#     171                 :            : unsigned int base_uint<BITS>::bits() const
#     172                 :     509002 : {
#     173         [ +  + ]:     558226 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
#     174         [ +  + ]:     558198 :         if (pn[pos]) {
#     175         [ +  + ]:     954656 :             for (int nbits = 31; nbits > 0; nbits--) {
#     176         [ +  + ]:     954650 :                 if (pn[pos] & 1U << nbits)
#     177                 :     508968 :                     return 32 * pos + nbits + 1;
#     178                 :     954650 :             }
#     179                 :     508974 :             return 32 * pos + 1;
#     180                 :     508974 :         }
#     181                 :     558198 :     }
#     182                 :     509002 :     return 0;
#     183                 :     509002 : }
#     184                 :            : 
#     185                 :            : // Explicit instantiations for base_uint<256>
#     186                 :            : template base_uint<256>::base_uint(const std::string&);
#     187                 :            : template base_uint<256>& base_uint<256>::operator<<=(unsigned int);
#     188                 :            : template base_uint<256>& base_uint<256>::operator>>=(unsigned int);
#     189                 :            : template base_uint<256>& base_uint<256>::operator*=(uint32_t b32);
#     190                 :            : template base_uint<256>& base_uint<256>::operator*=(const base_uint<256>& b);
#     191                 :            : template base_uint<256>& base_uint<256>::operator/=(const base_uint<256>& b);
#     192                 :            : template int base_uint<256>::CompareTo(const base_uint<256>&) const;
#     193                 :            : template bool base_uint<256>::EqualTo(uint64_t) const;
#     194                 :            : template double base_uint<256>::getdouble() const;
#     195                 :            : template std::string base_uint<256>::GetHex() const;
#     196                 :            : template std::string base_uint<256>::ToString() const;
#     197                 :            : template void base_uint<256>::SetHex(const char*);
#     198                 :            : template void base_uint<256>::SetHex(const std::string&);
#     199                 :            : template unsigned int base_uint<256>::bits() const;
#     200                 :            : 
#     201                 :            : // This implementation directly uses shifts instead of going
#     202                 :            : // through an intermediate MPI representation.
#     203                 :            : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
#     204                 :     962283 : {
#     205                 :     962283 :     int nSize = nCompact >> 24;
#     206                 :     962283 :     uint32_t nWord = nCompact & 0x007fffff;
#     207         [ +  + ]:     962283 :     if (nSize <= 3) {
#     208                 :         28 :         nWord >>= 8 * (3 - nSize);
#     209                 :         28 :         *this = nWord;
#     210                 :     962255 :     } else {
#     211                 :     962255 :         *this = nWord;
#     212                 :     962255 :         *this <<= 8 * (nSize - 3);
#     213                 :     962255 :     }
#     214         [ +  + ]:     962283 :     if (pfNegative)
#     215 [ +  + ][ +  + ]:     962224 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
#     216         [ +  + ]:     962283 :     if (pfOverflow)
#     217 [ +  + ][ +  + ]:     962224 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
#     218 [ +  + ][ -  + ]:     962200 :                                      (nWord > 0xff && nSize > 33) ||
#     219 [ +  + ][ -  + ]:     962200 :                                      (nWord > 0xffff && nSize > 32));
#     220                 :     962283 :     return *this;
#     221                 :     962283 : }
#     222                 :            : 
#     223                 :            : uint32_t arith_uint256::GetCompact(bool fNegative) const
#     224                 :     161892 : {
#     225                 :     161892 :     int nSize = (bits() + 7) / 8;
#     226                 :     161892 :     uint32_t nCompact = 0;
#     227         [ +  + ]:     161892 :     if (nSize <= 3) {
#     228                 :         34 :         nCompact = GetLow64() << 8 * (3 - nSize);
#     229                 :     161858 :     } else {
#     230                 :     161858 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
#     231                 :     161858 :         nCompact = bn.GetLow64();
#     232                 :     161858 :     }
#     233                 :            :     // The 0x00800000 bit denotes the sign.
#     234                 :            :     // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
#     235         [ +  + ]:     161892 :     if (nCompact & 0x00800000) {
#     236                 :        861 :         nCompact >>= 8;
#     237                 :        861 :         nSize++;
#     238                 :        861 :     }
#     239                 :     161892 :     assert((nCompact & ~0x007fffff) == 0);
#     240                 :     161892 :     assert(nSize < 256);
#     241                 :     161892 :     nCompact |= nSize << 24;
#     242 [ +  + ][ +  - ]:     161892 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
#     243                 :     161892 :     return nCompact;
#     244                 :     161892 : }
#     245                 :            : 
#     246                 :            : uint256 ArithToUint256(const arith_uint256 &a)
#     247                 :     507732 : {
#     248                 :     507732 :     uint256 b;
#     249         [ +  + ]:    4569588 :     for(int x=0; x<a.WIDTH; ++x)
#     250                 :    4061856 :         WriteLE32(b.begin() + x*4, a.pn[x]);
#     251                 :     507732 :     return b;
#     252                 :     507732 : }
#     253                 :            : arith_uint256 UintToArith256(const uint256 &a)
#     254                 :    2059320 : {
#     255                 :    2059320 :     arith_uint256 b;
#     256         [ +  + ]:   18533880 :     for(int x=0; x<b.WIDTH; ++x)
#     257                 :   16474560 :         b.pn[x] = ReadLE32(a.begin() + x*4);
#     258                 :    2059320 :     return b;
#     259                 :    2059320 : }