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 <limits>
       9             : #include <uint256.h>
      10             : #include <crypto/common.h>
      11             : 
      12             : #include <cassert>
      13             : 
      14             : template <unsigned int BITS>
      15      855560 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
      16             : {
      17      855560 :     base_uint<BITS> a(*this);
      18     7700040 :     for (int i = 0; i < WIDTH; i++)
      19     6844480 :         pn[i] = 0;
      20      855560 :     int k = shift / 32;
      21      855560 :     shift = shift % 32;
      22     7700040 :     for (int i = 0; i < WIDTH; i++) {
      23     6844480 :         if (i + k + 1 < WIDTH && shift != 0)
      24      860076 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
      25     6844480 :         if (i + k < WIDTH)
      26     1866401 :             pn[i + k] |= (a.pn[i] << shift);
      27     6844480 :     }
      28      855560 :     return *this;
      29             : }
      30             : 
      31             : template <unsigned int BITS>
      32      207842 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
      33             : {
      34      207842 :     base_uint<BITS> a(*this);
      35     1870578 :     for (int i = 0; i < WIDTH; i++)
      36     1662736 :         pn[i] = 0;
      37      207842 :     int k = shift / 32;
      38      207842 :     shift = shift % 32;
      39     1870578 :     for (int i = 0; i < WIDTH; i++) {
      40     1662736 :         if (i - k - 1 >= 0 && shift != 0)
      41      741021 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
      42     1662736 :         if (i - k >= 0)
      43      949628 :             pn[i - k] |= (a.pn[i] >> shift);
      44     1662736 :     }
      45      207842 :     return *this;
      46             : }
      47             : 
      48             : template <unsigned int BITS>
      49          95 : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
      50             : {
      51          95 :     uint64_t carry = 0;
      52         855 :     for (int i = 0; i < WIDTH; i++) {
      53         760 :         uint64_t n = carry + (uint64_t)b32 * pn[i];
      54         760 :         pn[i] = n & 0xffffffff;
      55         760 :         carry = n >> 32;
      56         760 :     }
      57          95 :     return *this;
      58             : }
      59             : 
      60             : template <unsigned int BITS>
      61        1013 : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
      62             : {
      63        1013 :     base_uint<BITS> a;
      64        9117 :     for (int j = 0; j < WIDTH; j++) {
      65        8104 :         uint64_t carry = 0;
      66       44572 :         for (int i = 0; i + j < WIDTH; i++) {
      67       36468 :             uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
      68       36468 :             a.pn[i + j] = n & 0xffffffff;
      69       36468 :             carry = n >> 32;
      70       36468 :         }
      71        8104 :     }
      72        1013 :     *this = a;
      73        1013 :     return *this;
      74             : }
      75             : 
      76             : template <unsigned int BITS>
      77          73 : base_uint<BITS>& base_uint<BITS>::operator/=(uint64_t b32)
      78             : {
      79          73 :     if (b32 == 0)
      80           1 :         throw uint_error("Division by zero");
      81          72 :     if (b32 > std::numeric_limits<uint32_t>::max()) {
      82           6 :         return *this /= base_uint(b32);
      83             :     }
      84          66 :     uint64_t rem = 0;
      85         594 :     for (int i = WIDTH - 1; i >= 0; --i) {
      86         528 :         uint64_t cur = (rem << 32) | pn[i];
      87         528 :         pn[i] = static_cast<uint32_t>(cur / b32);
      88         528 :         rem = cur % b32;
      89         528 :     }
      90          66 :     return *this;
      91          73 : }
      92             : 
      93             : template <unsigned int BITS>
      94       36994 : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
      95             : {
      96       36994 :     base_uint<BITS> div = b;     // make a copy, so we can shift.
      97       36994 :     base_uint<BITS> num = *this; // make a copy, so we can subtract.
      98       36994 :     *this = 0;                   // the quotient.
      99       36994 :     int num_bits = num.bits();
     100       36994 :     int div_bits = div.bits();
     101       36994 :     if (div_bits == 0)
     102           2 :         throw uint_error("Division by zero");
     103       36992 :     if (div_bits > num_bits) // the result is certainly 0.
     104           1 :         return *this;
     105       36991 :     int shift = num_bits - div_bits;
     106       36991 :     div <<= shift; // shift so that div and num align.
     107      139130 :     while (shift >= 0) {
     108      102139 :         if (num >= div) {
     109       50151 :             num -= div;
     110       50151 :             pn[shift / 32] |= (1U << (shift & 31)); // set a bit of the result.
     111       50151 :         }
     112      102139 :         div >>= 1; // shift back.
     113      102139 :         shift--;
     114             :     }
     115             :     // num now contains the remainder of the division.
     116       36991 :     return *this;
     117       36994 : }
     118             : 
     119             : template <unsigned int BITS>
     120   167192389 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
     121             : {
     122  1328029362 :     for (int i = WIDTH - 1; i >= 0; i--) {
     123  1327368270 :         if (pn[i] < b.pn[i])
     124   132652839 :             return -1;
     125  1194715431 :         if (pn[i] > b.pn[i])
     126    33878458 :             return 1;
     127  1160836973 :     }
     128      661092 :     return 0;
     129   167192389 : }
     130             : 
     131             : template <unsigned int BITS>
     132      762730 : bool base_uint<BITS>::EqualTo(uint64_t b) const
     133             : {
     134      763648 :     for (int i = WIDTH - 1; i >= 2; i--) {
     135      763575 :         if (pn[i])
     136      762657 :             return false;
     137         918 :     }
     138          73 :     if (pn[1] != (b >> 32))
     139          32 :         return false;
     140          41 :     if (pn[0] != (b & 0xfffffffful))
     141          32 :         return false;
     142           9 :     return true;
     143      762730 : }
     144             : 
     145             : template <unsigned int BITS>
     146       25605 : double base_uint<BITS>::getdouble() const
     147             : {
     148       25605 :     double ret = 0.0;
     149       25605 :     double fact = 1.0;
     150      230445 :     for (int i = 0; i < WIDTH; i++) {
     151      204840 :         ret += fact * pn[i];
     152      204840 :         fact *= 4294967296.0;
     153      204840 :     }
     154       25605 :     return ret;
     155             : }
     156             : 
     157             : template <unsigned int BITS>
     158         678 : std::string base_uint<BITS>::GetHex() const
     159             : {
     160         678 :     base_blob<BITS> b;
     161        6102 :     for (int x = 0; x < this->WIDTH; ++x) {
     162        5424 :         WriteLE32(b.begin() + x*4, this->pn[x]);
     163        5424 :     }
     164         678 :     return b.GetHex();
     165             : }
     166             : 
     167             : template <unsigned int BITS>
     168          26 : std::string base_uint<BITS>::ToString() const
     169             : {
     170          26 :     return GetHex();
     171             : }
     172             : 
     173             : template <unsigned int BITS>
     174      173173 : unsigned int base_uint<BITS>::bits() const
     175             : {
     176      194572 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
     177      194558 :         if (pn[pos]) {
     178      370250 :             for (int nbits = 31; nbits > 0; nbits--) {
     179      370239 :                 if (pn[pos] & 1U << nbits)
     180      173148 :                     return 32 * pos + nbits + 1;
     181      197091 :             }
     182          11 :             return 32 * pos + 1;
     183             :         }
     184       21399 :     }
     185          14 :     return 0;
     186      173173 : }
     187             : 
     188             : // Explicit instantiations for base_uint<256>
     189             : template class base_uint<256>;
     190             : 
     191             : // This implementation directly uses shifts instead of going
     192             : // through an intermediate MPI representation.
     193      763168 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
     194             : {
     195      763168 :     int nSize = nCompact >> 24;
     196      763168 :     uint32_t nWord = nCompact & 0x007fffff;
     197      763168 :     if (nSize <= 3) {
     198          14 :         nWord >>= 8 * (3 - nSize);
     199          14 :         *this = nWord;
     200          14 :     } else {
     201      763154 :         *this = nWord;
     202      763154 :         *this <<= 8 * (nSize - 3);
     203             :     }
     204      763168 :     if (pfNegative)
     205      762488 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
     206      763168 :     if (pfOverflow)
     207     1524964 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
     208     1524948 :                                      (nWord > 0xff && nSize > 33) ||
     209      762474 :                                      (nWord > 0xffff && nSize > 32));
     210      763168 :     return *this;
     211             : }
     212             : 
     213       98185 : uint32_t arith_uint256::GetCompact(bool fNegative) const
     214             : {
     215       98185 :     int nSize = (bits() + 7) / 8;
     216       98185 :     uint32_t nCompact = 0;
     217       98185 :     if (nSize <= 3) {
     218          17 :         nCompact = GetLow64() << 8 * (3 - nSize);
     219          17 :     } else {
     220       98168 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
     221       98168 :         nCompact = bn.GetLow64();
     222             :     }
     223             :     // The 0x00800000 bit denotes the sign.
     224             :     // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
     225       98185 :     if (nCompact & 0x00800000) {
     226           4 :         nCompact >>= 8;
     227           4 :         nSize++;
     228           4 :     }
     229       98185 :     assert((nCompact & ~0x007fffffU) == 0);
     230       98185 :     assert(nSize < 256);
     231       98185 :     nCompact |= nSize << 24;
     232       98185 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
     233       98185 :     return nCompact;
     234             : }
     235             : 
     236      250072 : uint256 ArithToUint256(const arith_uint256 &a)
     237             : {
     238      250072 :     uint256 b;
     239     2250648 :     for(int x=0; x<a.WIDTH; ++x)
     240     2000576 :         WriteLE32(b.begin() + x*4, a.pn[x]);
     241      250072 :     return b;
     242             : }
     243     1808156 : arith_uint256 UintToArith256(const uint256 &a)
     244             : {
     245     1808156 :     arith_uint256 b;
     246    16273404 :     for(int x=0; x<b.WIDTH; ++x)
     247    14465248 :         b.pn[x] = ReadLE32(a.begin() + x*4);
     248     1808156 :     return b;
     249             : }