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        1274 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
      22             : {
      23        1274 :     base_uint<BITS> a(*this);
      24       11466 :     for (int i = 0; i < WIDTH; i++)
      25       10192 :         pn[i] = 0;
      26        1274 :     int k = shift / 32;
      27        1274 :     shift = shift % 32;
      28       11466 :     for (int i = 0; i < WIDTH; i++) {
      29       10192 :         if (i + k + 1 < WIDTH && shift != 0)
      30        1407 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
      31       10192 :         if (i + k < WIDTH)
      32        2681 :             pn[i + k] |= (a.pn[i] << shift);
      33       10192 :     }
      34        1274 :     return *this;
      35             : }
      36             : 
      37             : template <unsigned int BITS>
      38       15779 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
      39             : {
      40       15779 :     base_uint<BITS> a(*this);
      41      142011 :     for (int i = 0; i < WIDTH; i++)
      42      126232 :         pn[i] = 0;
      43       15779 :     int k = shift / 32;
      44       15779 :     shift = shift % 32;
      45      142011 :     for (int i = 0; i < WIDTH; i++) {
      46      126232 :         if (i - k - 1 >= 0 && shift != 0)
      47        2814 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
      48      126232 :         if (i - k >= 0)
      49       18593 :             pn[i - k] |= (a.pn[i] >> shift);
      50      126232 :     }
      51       15779 :     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      371360 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
     110             : {
     111     2960667 :     for (int i = WIDTH - 1; i >= 0; i--) {
     112     2955858 :         if (pn[i] < b.pn[i])
     113      243075 :             return -1;
     114     2712783 :         if (pn[i] > b.pn[i])
     115      123476 :             return 1;
     116     2589307 :     }
     117        4809 :     return 0;
     118      371360 : }
     119             : 
     120             : template <unsigned int BITS>
     121        1073 : bool base_uint<BITS>::EqualTo(uint64_t b) const
     122             : {
     123        1073 :     for (int i = WIDTH - 1; i >= 2; i--) {
     124        1073 :         if (pn[i])
     125        1073 :             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        1073 : }
     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       15779 : unsigned int base_uint<BITS>::bits() const
     180             : {
     181       15779 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
     182       15779 :         if (pn[pos]) {
     183       31357 :             for (int nbits = 31; nbits > 0; nbits--) {
     184       31357 :                 if (pn[pos] & 1U << nbits)
     185       15779 :                     return 32 * pos + nbits + 1;
     186       15578 :             }
     187           0 :             return 32 * pos + 1;
     188             :         }
     189           0 :     }
     190           0 :     return 0;
     191       15779 : }
     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        1073 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
     199             : {
     200        1073 :     int nSize = nCompact >> 24;
     201        1073 :     uint32_t nWord = nCompact & 0x007fffff;
     202        1073 :     if (nSize <= 3) {
     203           0 :         nWord >>= 8 * (3 - nSize);
     204           0 :         *this = nWord;
     205           0 :     } else {
     206        1073 :         *this = nWord;
     207        1073 :         *this <<= 8 * (nSize - 3);
     208             :     }
     209        1073 :     if (pfNegative)
     210        1073 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
     211        1073 :     if (pfOverflow)
     212        2146 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
     213        2146 :                                      (nWord > 0xff && nSize > 33) ||
     214        1073 :                                      (nWord > 0xffff && nSize > 32));
     215        1073 :     return *this;
     216             : }
     217             : 
     218       15377 : uint32_t arith_uint256::GetCompact(bool fNegative) const
     219             : {
     220       15377 :     int nSize = (bits() + 7) / 8;
     221       15377 :     uint32_t nCompact = 0;
     222       15377 :     if (nSize <= 3) {
     223           0 :         nCompact = GetLow64() << 8 * (3 - nSize);
     224           0 :     } else {
     225       15377 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
     226       15377 :         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       15377 :     if (nCompact & 0x00800000) {
     231           0 :         nCompact >>= 8;
     232           0 :         nSize++;
     233           0 :     }
     234       15377 :     assert((nCompact & ~0x007fffffU) == 0);
     235       15377 :     assert(nSize < 256);
     236       15377 :     nCompact |= nSize << 24;
     237       15377 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
     238       15377 :     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       17123 : arith_uint256 UintToArith256(const uint256 &a)
     249             : {
     250       17123 :     arith_uint256 b;
     251      154107 :     for(int x=0; x<b.WIDTH; ++x)
     252      136984 :         b.pn[x] = ReadLE32(a.begin() + x*4);
     253       17123 :     return b;
     254             : }