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          16 : base_uint<BITS>::base_uint(const std::string& str)
      14           0 : {
      15             :     static_assert(BITS/32 > 0 && BITS%32 == 0, "Template parameter BITS must be a positive multiple of 32.");
      16             : 
      17          16 :     SetHex(str);
      18          16 : }
      19             : 
      20             : template <unsigned int BITS>
      21      573904 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
      22             : {
      23      573904 :     base_uint<BITS> a(*this);
      24     5165150 :     for (int i = 0; i < WIDTH; i++)
      25     4591247 :         pn[i] = 0;
      26      573906 :     int k = shift / 32;
      27      573906 :     shift = shift % 32;
      28     5165152 :     for (int i = 0; i < WIDTH; i++) {
      29     4591245 :         if (i + k + 1 < WIDTH && shift != 0)
      30      806913 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
      31     4591246 :         if (i + k < WIDTH)
      32     1539036 :             pn[i + k] |= (a.pn[i] << shift);
      33             :     }
      34      573906 :     return *this;
      35      573906 : }
      36             : 
      37             : template <unsigned int BITS>
      38      409519 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
      39             : {
      40      409519 :     base_uint<BITS> a(*this);
      41     3685671 :     for (int i = 0; i < WIDTH; i++)
      42     3276152 :         pn[i] = 0;
      43      409519 :     int k = shift / 32;
      44      409519 :     shift = shift % 32;
      45     3685671 :     for (int i = 0; i < WIDTH; i++) {
      46     3276152 :         if (i - k - 1 >= 0 && shift != 0)
      47     2064211 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
      48     3276152 :         if (i - k >= 0)
      49     2474491 :             pn[i - k] |= (a.pn[i] >> shift);
      50             :     }
      51      409519 :     return *this;
      52      409519 : }
      53             : 
      54             : template <unsigned int BITS>
      55        2695 : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
      56             : {
      57             :     uint64_t carry = 0;
      58       24255 :     for (int i = 0; i < WIDTH; i++) {
      59       21560 :         uint64_t n = carry + (uint64_t)b32 * pn[i];
      60       21560 :         pn[i] = n & 0xffffffff;
      61       21560 :         carry = n >> 32;
      62             :     }
      63        2695 :     return *this;
      64             : }
      65             : 
      66             : template <unsigned int BITS>
      67        1222 : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
      68             : {
      69        1222 :     base_uint<BITS> a;
      70       10998 :     for (int j = 0; j < WIDTH; j++) {
      71             :         uint64_t carry = 0;
      72       53768 :         for (int i = 0; i + j < WIDTH; i++) {
      73       43992 :             uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
      74       43992 :             a.pn[i + j] = n & 0xffffffff;
      75       43992 :             carry = n >> 32;
      76             :         }
      77             :     }
      78        1222 :     *this = a;
      79        1222 :     return *this;
      80        1222 : }
      81             : 
      82             : template <unsigned int BITS>
      83      113580 : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
      84             : {
      85      113580 :     base_uint<BITS> div = b;     // make a copy, so we can shift.
      86      113580 :     base_uint<BITS> num = *this; // make a copy, so we can subtract.
      87      113580 :     *this = 0;                   // the quotient.
      88      113580 :     int num_bits = num.bits();
      89      113580 :     int div_bits = div.bits();
      90      113580 :     if (div_bits == 0)
      91           2 :         throw uint_error("Division by zero");
      92      113578 :     if (div_bits > num_bits) // the result is certainly 0.
      93           1 :         return *this;
      94      113577 :     int shift = num_bits - div_bits;
      95      113577 :     div <<= shift; // shift so that div and num align.
      96      404665 :     while (shift >= 0) {
      97      291088 :         if (num >= div) {
      98      125529 :             num -= div;
      99      125529 :             pn[shift / 32] |= (1 << (shift & 31)); // set a bit of the result.
     100      125529 :         }
     101      291088 :         div >>= 1; // shift back.
     102      291088 :         shift--;
     103             :     }
     104             :     // num now contains the remainder of the division.
     105             :     return *this;
     106      113580 : }
     107             : 
     108             : template <unsigned int BITS>
     109   979703696 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
     110             : {
     111  7835187978 :     for (int i = WIDTH - 1; i >= 0; i--) {
     112  7831574976 :         if (pn[i] < b.pn[i])
     113   569924763 :             return -1;
     114  7261650213 :         if (pn[i] > b.pn[i])
     115   406165931 :             return 1;
     116             :     }
     117     3613002 :     return 0;
     118   979703696 : }
     119             : 
     120             : template <unsigned int BITS>
     121      405224 : bool base_uint<BITS>::EqualTo(uint64_t b) const
     122             : {
     123      408885 :     for (int i = WIDTH - 1; i >= 2; i--) {
     124      408812 :         if (pn[i])
     125      405151 :             return false;
     126             :     }
     127          73 :     if (pn[1] != (b >> 32))
     128          32 :         return false;
     129          41 :     if (pn[0] != (b & 0xfffffffful))
     130          32 :         return false;
     131           9 :     return true;
     132      405224 : }
     133             : 
     134             : template <unsigned int BITS>
     135       51171 : double base_uint<BITS>::getdouble() const
     136             : {
     137             :     double ret = 0.0;
     138             :     double fact = 1.0;
     139      460539 :     for (int i = 0; i < WIDTH; i++) {
     140      409368 :         ret += fact * pn[i];
     141      409368 :         fact *= 4294967296.0;
     142             :     }
     143       51171 :     return ret;
     144             : }
     145             : 
     146             : template <unsigned int BITS>
     147        7726 : std::string base_uint<BITS>::GetHex() const
     148             : {
     149        7726 :     return ArithToUint256(*this).GetHex();
     150             : }
     151             : 
     152             : template <unsigned int BITS>
     153          20 : void base_uint<BITS>::SetHex(const char* psz)
     154             : {
     155          20 :     *this = UintToArith256(uint256S(psz));
     156          20 : }
     157             : 
     158             : template <unsigned int BITS>
     159          20 : void base_uint<BITS>::SetHex(const std::string& str)
     160             : {
     161          20 :     SetHex(str.c_str());
     162          20 : }
     163             : 
     164             : template <unsigned int BITS>
     165          30 : std::string base_uint<BITS>::ToString() const
     166             : {
     167          30 :     return (GetHex());
     168             : }
     169             : 
     170             : template <unsigned int BITS>
     171      339282 : unsigned int base_uint<BITS>::bits() const
     172             : {
     173      366891 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
     174      366877 :         if (pn[pos]) {
     175      623832 :             for (int nbits = 31; nbits > 0; nbits--) {
     176      623829 :                 if (pn[pos] & 1U << nbits)
     177      339265 :                     return 32 * pos + nbits + 1;
     178             :             }
     179           3 :             return 32 * pos + 1;
     180             :         }
     181             :     }
     182          14 :     return 0;
     183      339282 : }
     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      405002 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
     204             : {
     205      405002 :     int nSize = nCompact >> 24;
     206      405002 :     uint32_t nWord = nCompact & 0x007fffff;
     207      405002 :     if (nSize <= 3) {
     208          14 :         nWord >>= 8 * (3 - nSize);
     209          14 :         *this = nWord;
     210          14 :     } else {
     211      404989 :         *this = nWord;
     212      404989 :         *this <<= 8 * (nSize - 3);
     213             :     }
     214      405003 :     if (pfNegative)
     215      404983 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
     216      405003 :     if (pfOverflow)
     217      809952 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
     218      404969 :                                      (nWord > 0xff && nSize > 33) ||
     219      404969 :                                      (nWord > 0xffff && nSize > 32));
     220      405003 :     return *this;
     221             : }
     222             : 
     223      110913 : uint32_t arith_uint256::GetCompact(bool fNegative) const
     224             : {
     225      110913 :     int nSize = (bits() + 7) / 8;
     226             :     uint32_t nCompact = 0;
     227      110913 :     if (nSize <= 3) {
     228          17 :         nCompact = GetLow64() << 8 * (3 - nSize);
     229          17 :     } else {
     230      110896 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
     231      110896 :         nCompact = bn.GetLow64();
     232      110896 :     }
     233             :     // The 0x00800000 bit denotes the sign.
     234             :     // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
     235      110913 :     if (nCompact & 0x00800000) {
     236         706 :         nCompact >>= 8;
     237         706 :         nSize++;
     238         706 :     }
     239      110913 :     assert((nCompact & ~0x007fffff) == 0);
     240      110913 :     assert(nSize < 256);
     241      110913 :     nCompact |= nSize << 24;
     242      110913 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
     243      110913 :     return nCompact;
     244             : }
     245             : 
     246      257747 : uint256 ArithToUint256(const arith_uint256 &a)
     247             : {
     248      257747 :     uint256 b;
     249     2319723 :     for(int x=0; x<a.WIDTH; ++x)
     250     2061976 :         WriteLE32(b.begin() + x*4, a.pn[x]);
     251      257747 :     return b;
     252             : }
     253      853759 : arith_uint256 UintToArith256(const uint256 &a)
     254             : {
     255      853759 :     arith_uint256 b;
     256     7683832 :     for(int x=0; x<b.WIDTH; ++x)
     257     6830075 :         b.pn[x] = ReadLE32(a.begin() + x*4);
     258      853761 :     return b;
     259             : }