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      427403 : base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
      31             : {
      32     3836020 :     base_uint<BITS> a(*this);
      33     3836020 :     for (int i = 0; i < WIDTH; i++)
      34     3408622 :         pn[i] = 0;
      35      427403 :     int k = shift / 32;
      36      427403 :     shift = shift % 32;
      37     3836020 :     for (int i = 0; i < WIDTH; i++) {
      38     3408622 :         if (i + k + 1 < WIDTH && shift != 0)
      39      690648 :             pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
      40     3408622 :         if (i + k < WIDTH)
      41     1268950 :             pn[i + k] |= (a.pn[i] << shift);
      42             :     }
      43      427403 :     return *this;
      44             : }
      45             : 
      46             : template <unsigned int BITS>
      47      788944 : base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
      48             : {
      49     7084188 :     base_uint<BITS> a(*this);
      50     7084188 :     for (int i = 0; i < WIDTH; i++)
      51     6295237 :         pn[i] = 0;
      52      788944 :     int k = shift / 32;
      53      788944 :     shift = shift % 32;
      54     7084188 :     for (int i = 0; i < WIDTH; i++) {
      55     6295237 :         if (i - k - 1 >= 0 && shift != 0)
      56     5158960 :             pn[i - k - 1] |= (a.pn[i] << (32 - shift));
      57     6295237 :         if (i - k >= 0)
      58     5950228 :             pn[i - k] |= (a.pn[i] >> shift);
      59             :     }
      60      788944 :     return *this;
      61             : }
      62             : 
      63             : template <unsigned int BITS>
      64         609 : base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
      65             : {
      66         609 :     uint64_t carry = 0;
      67        5469 :     for (int i = 0; i < WIDTH; i++) {
      68        4860 :         uint64_t n = carry + (uint64_t)b32 * pn[i];
      69        4860 :         pn[i] = n & 0xffffffff;
      70        4860 :         carry = n >> 32;
      71             :     }
      72         609 :     return *this;
      73             : }
      74             : 
      75             : template <unsigned int BITS>
      76       20178 : base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
      77             : {
      78      181566 :     base_uint<BITS> a;
      79      181566 :     for (int j = 0; j < WIDTH; j++) {
      80             :         uint64_t carry = 0;
      81      887544 :         for (int i = 0; i + j < WIDTH; i++) {
      82      726156 :             uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
      83      726156 :             a.pn[i + j] = n & 0xffffffff;
      84      726156 :             carry = n >> 32;
      85             :         }
      86             :     }
      87       20178 :     *this = a;
      88       20178 :     return *this;
      89             : }
      90             : 
      91             : template <unsigned int BITS>
      92       94835 : base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
      93             : {
      94       94835 :     base_uint<BITS> div = b;     // make a copy, so we can shift.
      95       94835 :     base_uint<BITS> num = *this; // make a copy, so we can subtract.
      96       94835 :     *this = 0;                   // the quotient.
      97       94835 :     int num_bits = num.bits();
      98       94835 :     int div_bits = div.bits();
      99       94835 :     if (div_bits == 0)
     100          12 :         throw uint_error("Division by zero");
     101       94831 :     if (div_bits > num_bits) // the result is certainly 0.
     102             :         return *this;
     103       94830 :     int shift = num_bits - div_bits;
     104       94830 :     div <<= shift; // shift so that div and num align.
     105      827120 :     while (shift >= 0) {
     106      732290 :         if (num >= div) {
     107      330859 :             num -= div;
     108      330859 :             pn[shift / 32] |= (1 << (shift & 31)); // set a bit of the result.
     109             :         }
     110      732290 :         div >>= 1; // shift back.
     111      732290 :         shift--;
     112             :     }
     113             :     // num now contains the remainder of the division.
     114             :     return *this;
     115             : }
     116             : 
     117             : template <unsigned int BITS>
     118   189939944 : int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
     119             : {
     120  1514323454 :     for (int i = WIDTH - 1; i >= 0; i--) {
     121  1512605100 :         if (pn[i] < b.pn[i])
     122             :             return -1;
     123  1387730839 :         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       42602 : double base_uint<BITS>::getdouble() const
     145             : {
     146       42602 :     double ret = 0.0;
     147       42602 :     double fact = 1.0;
     148      382455 :     for (int i = 0; i < WIDTH; i++) {
     149      339853 :         ret += fact * pn[i];
     150      339853 :         fact *= 4294967296.0;
     151             :     }
     152       42602 :     return ret;
     153             : }
     154             : 
     155             : template <unsigned int BITS>
     156       17218 : std::string base_uint<BITS>::GetHex() const
     157             : {
     158             :     char psz[sizeof(pn) * 2 + 1];
     159      567786 :     for (unsigned int i = 0; i < sizeof(pn); i++)
     160      550568 :         sprintf(psz + i * 2, "%02x", ((unsigned char*)pn)[sizeof(pn) - i - 1]);
     161       17218 :     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      233883 : unsigned int base_uint<BITS>::bits() const
     216             : {
     217      497687 :     for (int pos = WIDTH - 1; pos >= 0; pos--) {
     218      497672 :         if (pn[pos]) {
     219     1427882 :             for (int bits = 31; bits > 0; bits--) {
     220     1427798 :                 if (pn[pos] & 1 << bits)
     221      233792 :                     return 32 * pos + bits + 1;
     222             :             }
     223          76 :             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      273453 : arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
     275             : {
     276      273453 :     int nSize = nCompact >> 24;
     277      273453 :     uint32_t nWord = nCompact & 0x007fffff;
     278      273453 :     if (nSize <= 3) {
     279          13 :         nWord >>= 8 * (3 - nSize);
     280         130 :         *this = nWord;
     281             :     } else {
     282     2734400 :         *this = nWord;
     283      273440 :         *this <<= 8 * (nSize - 3);
     284             :     }
     285      273453 :     if (pfNegative)
     286      506598 :         *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
     287      273453 :     if (pfOverflow)
     288      506599 :         *pfOverflow = nWord != 0 && ((nSize > 34) ||
     289      253288 :                                      (nWord > 0xff && nSize > 33) ||
     290      253288 :                                      (nWord > 0xffff && nSize > 32));
     291      273453 :     return *this;
     292             : }
     293             : 
     294       44213 : uint32_t arith_uint256::GetCompact(bool fNegative) const
     295             : {
     296       44213 :     int nSize = (bits() + 7) / 8;
     297       44213 :     uint32_t nCompact = 0;
     298       44213 :     if (nSize <= 3) {
     299          16 :         nCompact = GetLow64() << 8 * (3 - nSize);
     300             :     } else {
     301       44197 :         arith_uint256 bn = *this >> 8 * (nSize - 3);
     302       44197 :         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       44213 :     if (nCompact & 0x00800000) {
     307       11133 :         nCompact >>= 8;
     308       11133 :         nSize++;
     309             :     }
     310       44213 :     assert((nCompact & ~0x007fffff) == 0);
     311       44213 :     assert(nSize < 256);
     312       44213 :     nCompact |= nSize << 24;
     313       44213 :     nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
     314       44213 :     return nCompact;
     315             : }
     316             : 
     317        6657 : uint256 arith_uint512::trim256() const
     318             : {
     319        6657 :     std::vector<unsigned char> vch;
     320        6657 :     const unsigned char* p = this->begin();
     321      219681 :     for (unsigned int i = 0; i < 32; i++) {
     322      213024 :         vch.push_back(*p++);
     323             :     }
     324       13314 :     return uint256(vch);
     325             : }
     326             : 
     327      557641 : uint256 ArithToUint256(const arith_uint256 &a)
     328             : {
     329      557641 :     uint256 b;
     330     5018770 :     for(int x=0; x<a.WIDTH; ++x)
     331     4461130 :         WriteLE32(b.begin() + x*4, a.pn[x]);
     332      557641 :     return b;
     333             : }
     334     1273803 : arith_uint256 UintToArith256(const uint256 &a)
     335             : {
     336     1273803 :     arith_uint256 b;
     337    11464220 :     for(int x=0; x<b.WIDTH; ++x)
     338    10190430 :         b.pn[x] = ReadLE32(a.begin() + x*4);
     339     1273803 :     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             :