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      427170 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
      31             : {
      32     3833925 :     base_uint<BITS> a(*this);
      33     3833925 :     for (int i = 0; i < WIDTH; i++)
      34     3406762 :         pn[i] = 0;
      35      427170 :     int k = shift / 32;
      36      427170 :     shift = shift % 32;
      37     3833925 :     for (int i = 0; i < WIDTH; i++) {
      38     3406762 :         if (i + k + 1 < WIDTH && shift != 0)
      39      687554 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
      40     3406762 :         if (i + k < WIDTH)
      41     1265629 :             pn[i + k] |= (a.pn[i] << shift);
      42             :     }
      43      427170 :     return *this;
      44             : }
      45             : 
      46             : template <unsigned int BITS>
      47      768655 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
      48             : {
      49     6901589 :     base_uint<BITS> a(*this);
      50     6901589 :     for (int i = 0; i < WIDTH; i++)
      51     6132929 :         pn[i] = 0;
      52      768655 :     int k = shift / 32;
      53      768655 :     shift = shift % 32;
      54     6901589 :     for (int i = 0; i < WIDTH; i++) {
      55     6132929 :         if (i - k - 1 >= 0 && shift != 0)
      56     5016533 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
      57     6132929 :         if (i - k >= 0)
      58     5787510 :             pn[i - k] |= (a.pn[i] >> shift);
      59             :     }
      60      768655 :     return *this;
      61             : }
      62             : 
      63             : template <unsigned int BITS>
      64         628 : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
      65             : {
      66         628 :     uint64_t carry = 0;
      67        5640 :     for (int i = 0; i < WIDTH; i++) {
      68        5012 :         uint64_t n = carry + (uint64_t)b32 * pn[i];
      69        5012 :         pn[i] = n & 0xffffffff;
      70        5012 :         carry = n >> 32;
      71             :     }
      72         628 :     return *this;
      73             : }
      74             : 
      75             : template <unsigned int BITS>
      76       19471 : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
      77             : {
      78      175203 :     base_uint<BITS> a;
      79      175203 :     for (int j = 0; j < WIDTH; j++) {
      80             :         uint64_t carry = 0;
      81      856436 :         for (int i = 0; i + j < WIDTH; i++) {
      82      700704 :             uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
      83      700704 :             a.pn[i + j] = n & 0xffffffff;
      84      700704 :             carry = n >> 32;
      85             :         }
      86             :     }
      87       19471 :     *this = a;
      88       19471 :     return *this;
      89             : }
      90             : 
      91             : template <unsigned int BITS>
      92       94394 : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
      93             : {
      94       94394 :     base_uint<BITS> div = b;     // make a copy, so we can shift.
      95       94394 :     base_uint<BITS> num = *this; // make a copy, so we can subtract.
      96       94394 :     *this = 0;                   // the quotient.
      97       94394 :     int num_bits = num.bits();
      98       94394 :     int div_bits = div.bits();
      99       94394 :     if (div_bits == 0)
     100          12 :         throw uint_error("Division by zero");
     101       94390 :     if (div_bits > num_bits) // the result is certainly 0.
     102             :         return *this;
     103       94389 :     int shift = num_bits - div_bits;
     104       94389 :     div <<= shift; // shift so that div and num align.
     105      806332 :     while (shift >= 0) {
     106      711943 :         if (num >= div) {
     107      322010 :             num -= div;
     108      322010 :             pn[shift / 32] |= (1 << (shift & 31)); // set a bit of the result.
     109             :         }
     110      711943 :         div >>= 1; // shift back.
     111      711943 :         shift--;
     112             :     }
     113             :     // num now contains the remainder of the division.
     114             :     return *this;
     115             : }
     116             : 
     117             : template <unsigned int BITS>
     118   193932504 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
     119             : {
     120  1543739554 :     for (int i = WIDTH - 1; i >= 0; i--) {
     121  1542021500 :         if (pn[i] < b.pn[i])
     122             :             return -1;
     123  1414695439 :         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       42976 : double base_uint<BITS>::getdouble() const
     145             : {
     146       42976 :     double ret = 0.0;
     147       42976 :     double fact = 1.0;
     148      385821 :     for (int i = 0; i < WIDTH; i++) {
     149      342845 :         ret += fact * pn[i];
     150      342845 :         fact *= 4294967296.0;
     151             :     }
     152       42976 :     return ret;
     153             : }
     154             : 
     155             : template <unsigned int BITS>
     156       17560 : std::string base_uint<BITS>::GetHex() const
     157             : {
     158             :     char psz[sizeof(pn) * 2 + 1];
     159      579072 :     for (unsigned int i = 0; i < sizeof(pn); i++)
     160      561512 :         sprintf(psz + i * 2, "%02x", ((unsigned char*)pn)[sizeof(pn) - i - 1]);
     161       17560 :     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      233059 : unsigned int base_uint<BITS>::bits() const
     216             : {
     217      487714 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
     218      487699 :         if (pn[pos]) {
     219     1388186 :             for (int bits = 31; bits > 0; bits--) {
     220     1388132 :                 if (pn[pos] & 1 << bits)
     221      232989 :                     return 32 * pos + bits + 1;
     222             :             }
     223          55 :             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      273661 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
     275             : {
     276      273661 :     int nSize = nCompact >> 24;
     277      273661 :     uint32_t nWord = nCompact & 0x007fffff;
     278      273661 :     if (nSize <= 3) {
     279          13 :         nWord >>= 8 * (3 - nSize);
     280         130 :         *this = nWord;
     281             :     } else {
     282     2736480 :         *this = nWord;
     283      273648 :         *this <<= 8 * (nSize - 3);
     284             :     }
     285      273661 :     if (pfNegative)
     286      508428 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
     287      273661 :     if (pfOverflow)
     288      508429 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
     289      254203 :                                      (nWord > 0xff && nSize > 33) ||
     290      254203 :                                      (nWord > 0xffff && nSize > 32));
     291      273661 :     return *this;
     292             : }
     293             : 
     294       44271 : uint32_t arith_uint256::GetCompact(bool fNegative) const
     295             : {
     296       44271 :     int nSize = (bits() + 7) / 8;
     297       44271 :     uint32_t nCompact = 0;
     298       44271 :     if (nSize <= 3) {
     299          16 :         nCompact = GetLow64() << 8 * (3 - nSize);
     300             :     } else {
     301       44255 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
     302       44255 :         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       44271 :     if (nCompact & 0x00800000) {
     307       10741 :         nCompact >>= 8;
     308       10741 :         nSize++;
     309             :     }
     310       44271 :     assert((nCompact & ~0x007fffff) == 0);
     311       44271 :     assert(nSize < 256);
     312       44271 :     nCompact |= nSize << 24;
     313       44271 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
     314       44271 :     return nCompact;
     315             : }
     316             : 
     317        6668 : uint256 arith_uint512::trim256() const
     318             : {
     319        6668 :     std::vector<unsigned char> vch;
     320        6668 :     const unsigned char* p = this->begin();
     321      220044 :     for (unsigned int i = 0; i < 32; i++) {
     322      213376 :         vch.push_back(*p++);
     323             :     }
     324       13336 :     return uint256(vch);
     325             : }
     326             : 
     327      599865 : uint256 ArithToUint256(const arith_uint256 &a)
     328             : {
     329      599865 :     uint256 b;
     330     5398790 :     for(int x=0; x<a.WIDTH; ++x)
     331     4798920 :         WriteLE32(b.begin() + x*4, a.pn[x]);
     332      599865 :     return b;
     333             : }
     334     1699381 : arith_uint256 UintToArith256(const uint256 &a)
     335             : {
     336     1699381 :     arith_uint256 b;
     337    15294410 :     for(int x=0; x<b.WIDTH; ++x)
     338    13595010 :         b.pn[x] = ReadLE32(a.begin() + x*4);
     339     1699381 :     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             :