Line data    Source code

       1             : // Copyright (c) 2009-2010 Satoshi Nakamoto
       2             : // Copyright (c) 2009-2014 The Bitcoin 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 "crypto/common.h"
       9             : #include "uint256.h"
      10             : #include "utilstrencodings.h"
      11             : 
      12             : #include <stdio.h>
      13             : #include <string.h>
      14             : 
      15             : template <unsigned int BITS>
      16          36 : base_uint<BITS>::base_uint(const std::string& str)
      17             : {
      18          36 :     SetHex(str);
      19          36 : }
      20             : 
      21             : template <unsigned int BITS>
      22        3008 : base_uint<BITS>::base_uint(const std::vector<unsigned char>& vch)
      23             : {
      24        3008 :     if (vch.size() != sizeof(pn))
      25          12 :         throw uint_error("Converting vector of wrong size to base_uint");
      26        3004 :     memcpy(pn, vch.data(), sizeof(pn));
      27        3004 : }
      28             : 
      29             : template <unsigned int BITS>
      30      316294 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
      31             : {
      32     2836046 :     base_uint<BITS> a(*this);
      33     2836046 :     for (int i = 0; i < WIDTH; i++)
      34     2519754 :         pn[i] = 0;
      35      316294 :     int k = shift / 32;
      36      316294 :     shift = shift % 32;
      37     2836046 :     for (int i = 0; i < WIDTH; i++) {
      38     2519754 :         if (i + k + 1 < WIDTH && shift != 0)
      39      496965 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
      40     2519754 :         if (i + k < WIDTH)
      41      964158 :             pn[i + k] |= (a.pn[i] << shift);
      42             :     }
      43      316294 :     return *this;
      44             : }
      45             : 
      46             : template <unsigned int BITS>
      47      526324 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
      48             : {
      49     4720609 :     base_uint<BITS> a(*this);
      50     4720609 :     for (int i = 0; i < WIDTH; i++)
      51     4194279 :         pn[i] = 0;
      52      526324 :     int k = shift / 32;
      53      526324 :     shift = shift % 32;
      54     4720609 :     for (int i = 0; i < WIDTH; i++) {
      55     4194279 :         if (i - k - 1 >= 0 && shift != 0)
      56     3353163 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
      57     4194279 :         if (i - k >= 0)
      58     3881810 :             pn[i - k] |= (a.pn[i] >> shift);
      59             :     }
      60      526324 :     return *this;
      61             : }
      62             : 
      63             : template <unsigned int BITS>
      64         504 : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
      65             : {
      66         504 :     uint64_t carry = 0;
      67        4524 :     for (int i = 0; i < WIDTH; i++) {
      68        4020 :         uint64_t n = carry + (uint64_t)b32 * pn[i];
      69        4020 :         pn[i] = n & 0xffffffff;
      70        4020 :         carry = n >> 32;
      71             :     }
      72         504 :     return *this;
      73             : }
      74             : 
      75             : template <unsigned int BITS>
      76       12367 : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
      77             : {
      78      111267 :     base_uint<BITS> a;
      79      111267 :     for (int j = 0; j < WIDTH; j++) {
      80             :         uint64_t carry = 0;
      81      543860 :         for (int i = 0; i + j < WIDTH; i++) {
      82      444960 :             uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
      83      444960 :             a.pn[i + j] = n & 0xffffffff;
      84      444960 :             carry = n >> 32;
      85             :         }
      86             :     }
      87       12367 :     *this = a;
      88       12367 :     return *this;
      89             : }
      90             : 
      91             : template <unsigned int BITS>
      92       67166 : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
      93             : {
      94       67166 :     base_uint<BITS> div = b;     // make a copy, so we can shift.
      95       67166 :     base_uint<BITS> num = *this; // make a copy, so we can subtract.
      96       67166 :     *this = 0;                   // the quotient.
      97       67166 :     int num_bits = num.bits();
      98       67166 :     int div_bits = div.bits();
      99       67166 :     if (div_bits == 0)
     100          12 :         throw uint_error("Division by zero");
     101       67162 :     if (div_bits > num_bits) // the result is certainly 0.
     102             :         return *this;
     103       67161 :     int shift = num_bits - div_bits;
     104       67161 :     div <<= shift; // shift so that div and num align.
     105      541479 :     while (shift >= 0) {
     106      474318 :         if (num >= div) {
     107      216666 :             num -= div;
     108      216666 :             pn[shift / 32] |= (1 << (shift & 31)); // set a bit of the result.
     109             :         }
     110      474318 :         div >>= 1; // shift back.
     111      474318 :         shift--;
     112             :     }
     113             :     // num now contains the remainder of the division.
     114             :     return *this;
     115             : }
     116             : 
     117             : template <unsigned int BITS>
     118   134883834 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
     119             : {
     120  1076386154 :     for (int i = WIDTH - 1; i >= 0; i--) {
     121  1075637700 :         if (pn[i] < b.pn[i])
     122             :             return -1;
     123   986505939 :         if (pn[i] > b.pn[i])
     124             :             return 1;
     125             :     }
     126             :     return 0;
     127             : }
     128             : 
     129             : template <unsigned int BITS>
     130         428 : bool base_uint<BITS>::EqualTo(uint64_t b) const
     131             : {
     132        1637 :     for (int i = WIDTH - 1; i >= 2; i--) {
     133        1497 :         if (pn[i])
     134             :             return false;
     135             :     }
     136         140 :     if (pn[1] != (b >> 32))
     137             :         return false;
     138          76 :     if (pn[0] != (b & 0xfffffffful))
     139          64 :         return false;
     140             :     return true;
     141             : }
     142             : 
     143             : template <unsigned int BITS>
     144       26183 : double base_uint<BITS>::getdouble() const
     145             : {
     146       26183 :     double ret = 0.0;
     147       26183 :     double fact = 1.0;
     148      234684 :     for (int i = 0; i < WIDTH; i++) {
     149      208501 :         ret += fact * pn[i];
     150      208501 :         fact *= 4294967296.0;
     151             :     }
     152       26183 :     return ret;
     153             : }
     154             : 
     155             : template <unsigned int BITS>
     156        8386 : std::string base_uint<BITS>::GetHex() const
     157             : {
     158             :     char psz[sizeof(pn) * 2 + 1];
     159      276330 :     for (unsigned int i = 0; i < sizeof(pn); i++)
     160      267944 :         sprintf(psz + i * 2, "%02x", ((unsigned char*)pn)[sizeof(pn) - i - 1]);
     161        8386 :     return std::string(psz, psz + sizeof(pn) * 2);
     162             : }
     163             : 
     164             : template <unsigned int BITS>
     165          44 : void base_uint<BITS>::SetHex(const char* psz)
     166             : {
     167          44 :     memset(pn, 0, sizeof(pn));
     168             : 
     169             :     // skip leading spaces
     170          50 :     while (isspace(*psz))
     171           6 :         psz++;
     172             : 
     173             :     // skip 0x
     174          44 :     if (psz[0] == '0' && tolower(psz[1]) == 'x')
     175          16 :         psz += 2;
     176             : 
     177             :     // hex string to uint
     178          44 :     const char* pbegin = psz;
     179        1846 :     while (::HexDigit(*psz) != -1)
     180        1802 :         psz++;
     181          44 :     psz--;
     182          44 :     unsigned char* p1 = (unsigned char*)pn;
     183          44 :     unsigned char* pend = p1 + WIDTH * 4;
     184         923 :     while (psz >= pbegin && p1 < pend) {
     185         879 :         *p1 = ::HexDigit(*psz--);
     186         879 :         if (psz >= pbegin) {
     187         875 :             *p1 |= ((unsigned char)::HexDigit(*psz--) << 4);
     188         875 :             p1++;
     189             :         }
     190             :     }
     191          44 : }
     192             : 
     193             : template <unsigned int BITS>
     194          44 : void base_uint<BITS>::SetHex(const std::string& str)
     195             : {
     196          44 :     SetHex(str.c_str());
     197          44 : }
     198             : 
     199             : template <unsigned int BITS>
     200          60 : std::string base_uint<BITS>::ToString() const
     201             : {
     202          60 :     return (GetHex());
     203             : }
     204             : 
     205             : template <unsigned int BITS>
     206           0 : std::string base_uint<BITS>::ToStringReverseEndian() const
     207             : {
     208             :     char psz[sizeof(pn) * 2 + 1];
     209           0 :     for (unsigned int i = 0; i < sizeof(pn); i++)
     210           0 :         sprintf(psz + i * 2, "%02x", ((unsigned char*)pn)[i]);
     211           0 :     return std::string(psz, psz + sizeof(pn) * 2);
     212             : }
     213             : 
     214             : template <unsigned int BITS>
     215      173897 : unsigned int base_uint<BITS>::bits() const
     216             : {
     217      334664 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
     218      334649 :         if (pn[pos]) {
     219      957842 :             for (int bits = 31; bits > 0; bits--) {
     220      957838 :                 if (pn[pos] & 1 << bits)
     221      173878 :                     return 32 * pos + bits + 1;
     222             :             }
     223           4 :             return 32 * pos + 1;
     224             :         }
     225             :     }
     226             :     return 0;
     227             : }
     228             : 
     229             : // Explicit instantiations for base_uint<160>
     230             : template base_uint<160>::base_uint(const std::string&);
     231             : template base_uint<160>::base_uint(const std::vector<unsigned char>&);
     232             : template base_uint<160>& base_uint<160>::operator<<=(unsigned int);
     233             : template base_uint<160>& base_uint<160>::operator>>=(unsigned int);
     234             : template base_uint<160>& base_uint<160>::operator*=(uint32_t b32);
     235             : template base_uint<160>& base_uint<160>::operator*=(const base_uint<160>& b);
     236             : template base_uint<160>& base_uint<160>::operator/=(const base_uint<160>& b);
     237             : template int base_uint<160>::CompareTo(const base_uint<160>&) const;
     238             : template bool base_uint<160>::EqualTo(uint64_t) const;
     239             : template double base_uint<160>::getdouble() const;
     240             : template std::string base_uint<160>::GetHex() const;
     241             : template std::string base_uint<160>::ToString() const;
     242             : template void base_uint<160>::SetHex(const char*);
     243             : template void base_uint<160>::SetHex(const std::string&);
     244             : template unsigned int base_uint<160>::bits() const;
     245             : 
     246             : // Explicit instantiations for base_uint<256>
     247             : template base_uint<256>::base_uint(const std::string&);
     248             : template base_uint<256>::base_uint(const std::vector<unsigned char>&);
     249             : template base_uint<256>& base_uint<256>::operator<<=(unsigned int);
     250             : template base_uint<256>& base_uint<256>::operator>>=(unsigned int);
     251             : template base_uint<256>& base_uint<256>::operator*=(uint32_t b32);
     252             : template base_uint<256>& base_uint<256>::operator*=(const base_uint<256>& b);
     253             : template base_uint<256>& base_uint<256>::operator/=(const base_uint<256>& b);
     254             : template int base_uint<256>::CompareTo(const base_uint<256>&) const;
     255             : template bool base_uint<256>::EqualTo(uint64_t) const;
     256             : template double base_uint<256>::getdouble() const;
     257             : template std::string base_uint<256>::GetHex() const;
     258             : template std::string base_uint<256>::ToString() const;
     259             : template void base_uint<256>::SetHex(const char*);
     260             : template void base_uint<256>::SetHex(const std::string&);
     261             : template unsigned int base_uint<256>::bits() const;
     262             : template std::string base_uint<256>::ToStringReverseEndian() const;
     263             : 
     264             : // Explicit instantiations for base_uint<512>
     265             : template base_uint<512>::base_uint(const std::string&);
     266             : template base_uint<512>& base_uint<512>::operator<<=(unsigned int);
     267             : template base_uint<512>& base_uint<512>::operator>>=(unsigned int);
     268             : template std::string base_uint<512>::GetHex() const;
     269             : template std::string base_uint<512>::ToString() const;
     270             : template std::string base_uint<512>::ToStringReverseEndian() const;
     271             : 
     272             : // This implementation directly uses shifts instead of going
     273             : // through an intermediate MPI representation.
     274      190013 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
     275             : {
     276      190013 :     int nSize = nCompact >> 24;
     277      190013 :     uint32_t nWord = nCompact & 0x007fffff;
     278      190013 :     if (nSize <= 3) {
     279          13 :         nWord >>= 8 * (3 - nSize);
     280         130 :         *this = nWord;
     281             :     } else {
     282     1900000 :         *this = nWord;
     283      190000 :         *this <<= 8 * (nSize - 3);
     284             :     }
     285      190013 :     if (pfNegative)
     286      355340 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
     287      190013 :     if (pfOverflow)
     288      355341 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
     289      177659 :                                      (nWord > 0xff && nSize > 33) ||
     290      177659 :                                      (nWord > 0xffff && nSize > 32));
     291      190013 :     return *this;
     292             : }
     293             : 
     294       39565 : uint32_t arith_uint256::GetCompact(bool fNegative) const
     295             : {
     296       39565 :     int nSize = (bits() + 7) / 8;
     297       39565 :     uint32_t nCompact = 0;
     298       39565 :     if (nSize <= 3) {
     299          16 :         nCompact = GetLow64() << 8 * (3 - nSize);
     300             :     } else {
     301       39549 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
     302       39549 :         nCompact = bn.GetLow64();
     303             :     }
     304             :     // The 0x00800000 bit denotes the sign.
     305             :     // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
     306       39565 :     if (nCompact & 0x00800000) {
     307       10275 :         nCompact >>= 8;
     308       10275 :         nSize++;
     309             :     }
     310       39565 :     assert((nCompact & ~0x007fffff) == 0);
     311       39565 :     assert(nSize < 256);
     312       39565 :     nCompact |= nSize << 24;
     313       39565 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
     314       39565 :     return nCompact;
     315             : }
     316             : 
     317        5683 : uint256 arith_uint512::trim256() const
     318             : {
     319        5683 :     std::vector<unsigned char> vch;
     320        5683 :     const unsigned char* p = this->begin();
     321      187539 :     for (unsigned int i = 0; i < 32; i++) {
     322      181856 :         vch.push_back(*p++);
     323             :     }
     324       11366 :     return uint256(vch);
     325             : }
     326             : 
     327      424937 : uint256 ArithToUint256(const arith_uint256 &a)
     328             : {
     329      424937 :     uint256 b;
     330     3824430 :     for(int x=0; x<a.WIDTH; ++x)
     331     3399500 :         WriteLE32(b.begin() + x*4, a.pn[x]);
     332      424937 :     return b;
     333             : }
     334      723912 : arith_uint256 UintToArith256(const uint256 &a)
     335             : {
     336      723912 :     arith_uint256 b;
     337     6515210 :     for(int x=0; x<b.WIDTH; ++x)
     338     5791290 :         b.pn[x] = ReadLE32(a.begin() + x*4);
     339      723912 :     return b;
     340             : }
     341             : 
     342           0 : uint512 ArithToUint512(const arith_uint512 &a)
     343             : {
     344           0 :     uint512 b;
     345           0 :     for(int x=0; x<a.WIDTH; ++x)
     346           0 :         WriteLE32(b.begin() + x*4, a.pn[x]);
     347           0 :     return b;
     348             : }
     349           0 : arith_uint512 UintToArith512(const uint512 &a)
     350             : {
     351           0 :     arith_uint512 b;
     352           0 :     for(int x=0; x<b.WIDTH; ++x)
     353           0 :         b.pn[x] = ReadLE32(a.begin() + x*4);
     354           0 :     return b;
     355             : }
     356             :