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                 :            : #include <cassert>
      12                 :            : 
      13                 :            : template <unsigned int BITS>
      14                 :          0 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
      15                 :            : {
      16                 :          0 :     base_uint<BITS> a(*this);
      17         [ #  # ]:          0 :     for (int i = 0; i < WIDTH; i++)
      18                 :          0 :         pn[i] = 0;
      19                 :          0 :     int k = shift / 32;
      20                 :          0 :     shift = shift % 32;
      21         [ #  # ]:          0 :     for (int i = 0; i < WIDTH; i++) {
      22 [ #  # ][ #  # ]:          0 :         if (i + k + 1 < WIDTH && shift != 0)
      23                 :          0 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
      24         [ #  # ]:          0 :         if (i + k < WIDTH)
      25                 :          0 :             pn[i + k] |= (a.pn[i] << shift);
      26                 :          0 :     }
      27                 :          0 :     return *this;
      28                 :            : }
      29                 :            : 
      30                 :            : template <unsigned int BITS>
      31                 :          0 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
      32                 :            : {
      33                 :          0 :     base_uint<BITS> a(*this);
      34         [ #  # ]:          0 :     for (int i = 0; i < WIDTH; i++)
      35                 :          0 :         pn[i] = 0;
      36                 :          0 :     int k = shift / 32;
      37                 :          0 :     shift = shift % 32;
      38         [ #  # ]:          0 :     for (int i = 0; i < WIDTH; i++) {
      39 [ #  # ][ #  # ]:          0 :         if (i - k - 1 >= 0 && shift != 0)
      40                 :          0 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
      41         [ #  # ]:          0 :         if (i - k >= 0)
      42                 :          0 :             pn[i - k] |= (a.pn[i] >> shift);
      43                 :          0 :     }
      44                 :          0 :     return *this;
      45                 :            : }
      46                 :            : 
      47                 :            : template <unsigned int BITS>
      48                 :          0 : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
      49                 :            : {
      50                 :          0 :     uint64_t carry = 0;
      51         [ #  # ]:          0 :     for (int i = 0; i < WIDTH; i++) {
      52                 :          0 :         uint64_t n = carry + (uint64_t)b32 * pn[i];
      53                 :          0 :         pn[i] = n & 0xffffffff;
      54                 :          0 :         carry = n >> 32;
      55                 :          0 :     }
      56                 :          0 :     return *this;
      57                 :            : }
      58                 :            : 
      59                 :            : template <unsigned int BITS>
      60                 :          0 : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
      61                 :            : {
      62                 :          0 :     base_uint<BITS> a;
      63         [ #  # ]:          0 :     for (int j = 0; j < WIDTH; j++) {
      64                 :          0 :         uint64_t carry = 0;
      65         [ #  # ]:          0 :         for (int i = 0; i + j < WIDTH; i++) {
      66                 :          0 :             uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
      67                 :          0 :             a.pn[i + j] = n & 0xffffffff;
      68                 :          0 :             carry = n >> 32;
      69                 :          0 :         }
      70                 :          0 :     }
      71                 :          0 :     *this = a;
      72                 :          0 :     return *this;
      73                 :            : }
      74                 :            : 
      75                 :            : template <unsigned int BITS>
      76                 :          0 : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
      77                 :            : {
      78                 :          0 :     base_uint<BITS> div = b;     // make a copy, so we can shift.
      79                 :          0 :     base_uint<BITS> num = *this; // make a copy, so we can subtract.
      80                 :          0 :     *this = 0;                   // the quotient.
      81                 :          0 :     int num_bits = num.bits();
      82                 :          0 :     int div_bits = div.bits();
      83         [ #  # ]:          0 :     if (div_bits == 0)
      84 [ #  # ][ #  # ]:          0 :         throw uint_error("Division by zero");
         [ #  # ][ #  # ]
      85         [ #  # ]:          0 :     if (div_bits > num_bits) // the result is certainly 0.
      86                 :          0 :         return *this;
      87                 :          0 :     int shift = num_bits - div_bits;
      88                 :          0 :     div <<= shift; // shift so that div and num align.
      89         [ #  # ]:          0 :     while (shift >= 0) {
      90         [ #  # ]:          0 :         if (num >= div) {
      91                 :          0 :             num -= div;
      92                 :          0 :             pn[shift / 32] |= (1U << (shift & 31)); // set a bit of the result.
      93                 :          0 :         }
      94                 :          0 :         div >>= 1; // shift back.
      95                 :          0 :         shift--;
      96                 :            :     }
      97                 :            :     // num now contains the remainder of the division.
      98                 :          0 :     return *this;
      99                 :          0 : }
     100                 :            : 
     101                 :            : template <unsigned int BITS>
     102                 :          0 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
     103                 :            : {
     104         [ #  # ]:          0 :     for (int i = WIDTH - 1; i >= 0; i--) {
     105         [ #  # ]:          0 :         if (pn[i] < b.pn[i])
     106                 :          0 :             return -1;
     107         [ #  # ]:          0 :         if (pn[i] > b.pn[i])
     108                 :          0 :             return 1;
     109                 :          0 :     }
     110                 :          0 :     return 0;
     111                 :          0 : }
     112                 :            : 
     113                 :            : template <unsigned int BITS>
     114                 :          0 : bool base_uint<BITS>::EqualTo(uint64_t b) const
     115                 :            : {
     116         [ #  # ]:          0 :     for (int i = WIDTH - 1; i >= 2; i--) {
     117         [ #  # ]:          0 :         if (pn[i])
     118                 :          0 :             return false;
     119                 :          0 :     }
     120         [ #  # ]:          0 :     if (pn[1] != (b >> 32))
     121                 :          0 :         return false;
     122         [ #  # ]:          0 :     if (pn[0] != (b & 0xfffffffful))
     123                 :          0 :         return false;
     124                 :          0 :     return true;
     125                 :          0 : }
     126                 :            : 
     127                 :            : template <unsigned int BITS>
     128                 :          0 : double base_uint<BITS>::getdouble() const
     129                 :            : {
     130                 :          0 :     double ret = 0.0;
     131                 :          0 :     double fact = 1.0;
     132         [ #  # ]:          0 :     for (int i = 0; i < WIDTH; i++) {
     133                 :          0 :         ret += fact * pn[i];
     134                 :          0 :         fact *= 4294967296.0;
     135                 :          0 :     }
     136                 :          0 :     return ret;
     137                 :            : }
     138                 :            : 
     139                 :            : template <unsigned int BITS>
     140                 :          0 : std::string base_uint<BITS>::GetHex() const
     141                 :            : {
     142                 :          0 :     base_blob<BITS> b;
     143         [ #  # ]:          0 :     for (int x = 0; x < this->WIDTH; ++x) {
     144                 :          0 :         WriteLE32(b.begin() + x*4, this->pn[x]);
     145                 :          0 :     }
     146                 :          0 :     return b.GetHex();
     147                 :            : }
     148                 :            : 
     149                 :            : template <unsigned int BITS>
     150                 :          0 : std::string base_uint<BITS>::ToString() const
     151                 :            : {
     152                 :          0 :     return GetHex();
     153                 :            : }
     154                 :            : 
     155                 :            : template <unsigned int BITS>
     156                 :          0 : unsigned int base_uint<BITS>::bits() const
     157                 :            : {
     158         [ #  # ]:          0 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
     159         [ #  # ]:          0 :         if (pn[pos]) {
     160         [ #  # ]:          0 :             for (int nbits = 31; nbits > 0; nbits--) {
     161         [ #  # ]:          0 :                 if (pn[pos] & 1U << nbits)
     162                 :          0 :                     return 32 * pos + nbits + 1;
     163                 :          0 :             }
     164                 :          0 :             return 32 * pos + 1;
     165                 :            :         }
     166                 :          0 :     }
     167                 :          0 :     return 0;
     168                 :          0 : }
     169                 :            : 
     170                 :            : // Explicit instantiations for base_uint<256>
     171                 :            : template class base_uint<256>;
     172                 :            : 
     173                 :            : // This implementation directly uses shifts instead of going
     174                 :            : // through an intermediate MPI representation.
     175                 :          0 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
     176                 :            : {
     177                 :          0 :     int nSize = nCompact >> 24;
     178                 :          0 :     uint32_t nWord = nCompact & 0x007fffff;
     179         [ #  # ]:          0 :     if (nSize <= 3) {
     180                 :          0 :         nWord >>= 8 * (3 - nSize);
     181                 :          0 :         *this = nWord;
     182                 :          0 :     } else {
     183                 :          0 :         *this = nWord;
     184                 :          0 :         *this <<= 8 * (nSize - 3);
     185                 :            :     }
     186         [ #  # ]:          0 :     if (pfNegative)
     187         [ #  # ]:          0 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
     188         [ #  # ]:          0 :     if (pfOverflow)
     189 [ #  # ][ #  # ]:          0 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
     190 [ #  # ][ #  # ]:          0 :                                      (nWord > 0xff && nSize > 33) ||
     191         [ #  # ]:          0 :                                      (nWord > 0xffff && nSize > 32));
     192                 :          0 :     return *this;
     193                 :            : }
     194                 :            : 
     195                 :          0 : uint32_t arith_uint256::GetCompact(bool fNegative) const
     196                 :            : {
     197                 :          0 :     int nSize = (bits() + 7) / 8;
     198                 :          0 :     uint32_t nCompact = 0;
     199         [ #  # ]:          0 :     if (nSize <= 3) {
     200                 :          0 :         nCompact = GetLow64() << 8 * (3 - nSize);
     201                 :          0 :     } else {
     202                 :          0 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
     203                 :          0 :         nCompact = bn.GetLow64();
     204                 :            :     }
     205                 :            :     // The 0x00800000 bit denotes the sign.
     206                 :            :     // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
     207         [ #  # ]:          0 :     if (nCompact & 0x00800000) {
     208                 :          0 :         nCompact >>= 8;
     209                 :          0 :         nSize++;
     210                 :          0 :     }
     211         [ #  # ]:          0 :     assert((nCompact & ~0x007fffffU) == 0);
     212         [ #  # ]:          0 :     assert(nSize < 256);
     213                 :          0 :     nCompact |= nSize << 24;
     214         [ #  # ]:          0 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
     215                 :          0 :     return nCompact;
     216                 :            : }
     217                 :            : 
     218                 :          0 : uint256 ArithToUint256(const arith_uint256 &a)
     219                 :            : {
     220                 :          0 :     uint256 b;
     221         [ #  # ]:          0 :     for(int x=0; x<a.WIDTH; ++x)
     222                 :          0 :         WriteLE32(b.begin() + x*4, a.pn[x]);
     223                 :          0 :     return b;
     224                 :            : }
     225                 :          0 : arith_uint256 UintToArith256(const uint256 &a)
     226                 :            : {
     227                 :          0 :     arith_uint256 b;
     228         [ #  # ]:          0 :     for(int x=0; x<b.WIDTH; ++x)
     229                 :          0 :         b.pn[x] = ReadLE32(a.begin() + x*4);
     230                 :          0 :     return b;
     231                 :            : }