text: // Copyright (c) 2009-2010 Satoshi Nakamoto
  // Copyright (c) 2009-2014 The Bitcoin developers
  // Distributed under the MIT software license, see the accompanying
  // file COPYING or http://www.opensource.org/licenses/mit-license.php.
  
  #include "arith_uint256.h"
  
  #include "crypto/common.h"
  #include "utilstrencodings.h"
  
  #include <stdio.h>
  #include <string.h>
  
  template <unsigned int BITS>
  base_uint<BITS>::base_uint(const std::string& str)
  {
      SetHex(str);
  }
  
  template <unsigned int BITS>
  base_uint<BITS>::base_uint(const std::vector<unsigned char>& vch)
  {
      if (vch.size() != sizeof(pn))
          throw uint_error("Converting vector of wrong size to base_uint");
      memcpy(pn, &vch[0], sizeof(pn));
  }
  
  template <unsigned int BITS>
  base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
  {
      base_uint<BITS> a(*this);
      for (int i = 0; i < WIDTH; i++)
          pn[i] = 0;
      int k = shift / 32;
      shift = shift % 32;
      for (int i = 0; i < WIDTH; i++) {
          if (i + k + 1 < WIDTH && shift != 0)
              pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
          if (i + k < WIDTH)
              pn[i + k] |= (a.pn[i] << shift);
      }
      return *this;
  }
  
  template <unsigned int BITS>
  base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
  {
      base_uint<BITS> a(*this);
      for (int i = 0; i < WIDTH; i++)
          pn[i] = 0;
      int k = shift / 32;
      shift = shift % 32;
      for (int i = 0; i < WIDTH; i++) {
          if (i - k - 1 >= 0 && shift != 0)
              pn[i - k - 1] |= (a.pn[i] << (32 - shift));
          if (i - k >= 0)
              pn[i - k] |= (a.pn[i] >> shift);
      }
      return *this;
  }
  
  template <unsigned int BITS>
  base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
  {
      uint64_t carry = 0;
      for (int i = 0; i < WIDTH; i++) {
          uint64_t n = carry + (uint64_t)b32 * pn[i];
          pn[i] = n & 0xffffffff;
          carry = n >> 32;
      }
      return *this;
  }
  
  template <unsigned int BITS>
  base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
  {
      base_uint<BITS> a = *this;
      *this = 0;
      for (int j = 0; j < WIDTH; j++) {
          uint64_t carry = 0;
          for (int i = 0; i + j < WIDTH; i++) {
              uint64_t n = carry + pn[i + j] + (uint64_t)a.pn[j] * b.pn[i];
              pn[i + j] = n & 0xffffffff;
              carry = n >> 32;
          }
      }
      return *this;
  }
  
  template <unsigned int BITS>
  base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
  {
      base_uint<BITS> div = b;     // make a copy, so we can shift.
      base_uint<BITS> num = *this; // make a copy, so we can subtract.
      *this = 0;                   // the quotient.
      int num_bits = num.bits();
      int div_bits = div.bits();
      if (div_bits == 0)
          throw uint_error("Division by zero");
      if (div_bits > num_bits) // the result is certainly 0.
          return *this;
      int shift = num_bits - div_bits;
      div <<= shift; // shift so that div and num align.
      while (shift >= 0) {
          if (num >= div) {
              num -= div;
              pn[shift / 32] |= (1 << (shift & 31)); // set a bit of the result.
          }
          div >>= 1; // shift back.
          shift--;
      }
      // num now contains the remainder of the division.
      return *this;
  }
  
  template <unsigned int BITS>
  int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
  {
      for (int i = WIDTH - 1; i >= 0; i--) {
          if (pn[i] < b.pn[i])
              return -1;
          if (pn[i] > b.pn[i])
              return 1;
      }
      return 0;
  }
  
  template <unsigned int BITS>
  bool base_uint<BITS>::EqualTo(uint64_t b) const
  {
      for (int i = WIDTH - 1; i >= 2; i--) {
          if (pn[i])
              return false;
      }
      if (pn[1] != (b >> 32))
          return false;
      if (pn[0] != (b & 0xfffffffful))
          return false;
      return true;
  }
  
  template <unsigned int BITS>
  double base_uint<BITS>::getdouble() const
  {
      double ret = 0.0;
      double fact = 1.0;
      for (int i = 0; i < WIDTH; i++) {
          ret += fact * pn[i];
          fact *= 4294967296.0;
      }
      return ret;
  }
  
  template <unsigned int BITS>
  std::string base_uint<BITS>::GetHex() const
  {
      char psz[sizeof(pn) * 2 + 1];
      for (unsigned int i = 0; i < sizeof(pn); i++)
          sprintf(psz + i * 2, "%02x", ((unsigned char*)pn)[sizeof(pn) - i - 1]);
      return std::string(psz, psz + sizeof(pn) * 2);
  }
  
  template <unsigned int BITS>
  void base_uint<BITS>::SetHex(const char* psz)
  {
      memset(pn, 0, sizeof(pn));
  
      // skip leading spaces
      while (isspace(*psz))
          psz++;
  
      // skip 0x
      if (psz[0] == '0' && tolower(psz[1]) == 'x')
          psz += 2;
  
      // hex string to uint
      const char* pbegin = psz;
      while (::HexDigit(*psz) != -1)
          psz++;
      psz--;
      unsigned char* p1 = (unsigned char*)pn;
      unsigned char* pend = p1 + WIDTH * 4;
      while (psz >= pbegin && p1 < pend) {
          *p1 = ::HexDigit(*psz--);
          if (psz >= pbegin) {
              *p1 |= ((unsigned char)::HexDigit(*psz--) << 4);
              p1++;
          }
      }
  }
  
  template <unsigned int BITS>
  void base_uint<BITS>::SetHex(const std::string& str)
  {
      SetHex(str.c_str());
  }
  
  template <unsigned int BITS>
  std::string base_uint<BITS>::ToString() const
  {
      return (GetHex());
  }
  
  template <unsigned int BITS>
  std::string base_uint<BITS>::ToStringReverseEndian() const
  {
      char psz[sizeof(pn) * 2 + 1];
      for (unsigned int i = 0; i < sizeof(pn); i++)
          sprintf(psz + i * 2, "%02x", ((unsigned char*)pn)[i]);
      return std::string(psz, psz + sizeof(pn) * 2);
  }
  
  template <unsigned int BITS>
  unsigned int base_uint<BITS>::bits() const
  {
      for (int pos = WIDTH - 1; pos >= 0; pos--) {
          if (pn[pos]) {
              for (int bits = 31; bits > 0; bits--) {
                  if (pn[pos] & 1 << bits)
                      return 32 * pos + bits + 1;
              }
              return 32 * pos + 1;
          }
      }
      return 0;
  }
  
  // Explicit instantiations for base_uint<160>
  template base_uint<160>::base_uint(const std::string&);
  template base_uint<160>::base_uint(const std::vector<unsigned char>&);
  template base_uint<160>& base_uint<160>::operator<<=(unsigned int);
  template base_uint<160>& base_uint<160>::operator>>=(unsigned int);
  template base_uint<160>& base_uint<160>::operator*=(uint32_t b32);
  template base_uint<160>& base_uint<160>::operator*=(const base_uint<160>& b);
  template base_uint<160>& base_uint<160>::operator/=(const base_uint<160>& b);
  template int base_uint<160>::CompareTo(const base_uint<160>&) const;
  template bool base_uint<160>::EqualTo(uint64_t) const;
  template double base_uint<160>::getdouble() const;
  template std::string base_uint<160>::GetHex() const;
  template std::string base_uint<160>::ToString() const;
  template void base_uint<160>::SetHex(const char*);
  template void base_uint<160>::SetHex(const std::string&);
  template unsigned int base_uint<160>::bits() const;
  
  // Explicit instantiations for base_uint<256>
  template base_uint<256>::base_uint(const std::string&);
  template base_uint<256>::base_uint(const std::vector<unsigned char>&);
  template base_uint<256>& base_uint<256>::operator<<=(unsigned int);
  template base_uint<256>& base_uint<256>::operator>>=(unsigned int);
  template base_uint<256>& base_uint<256>::operator*=(uint32_t b32);
  template base_uint<256>& base_uint<256>::operator*=(const base_uint<256>& b);
  template base_uint<256>& base_uint<256>::operator/=(const base_uint<256>& b);
  template int base_uint<256>::CompareTo(const base_uint<256>&) const;
  template bool base_uint<256>::EqualTo(uint64_t) const;
  template double base_uint<256>::getdouble() const;
  template std::string base_uint<256>::GetHex() const;
  template std::string base_uint<256>::ToString() const;
  template void base_uint<256>::SetHex(const char*);
  template void base_uint<256>::SetHex(const std::string&);
  template unsigned int base_uint<256>::bits() const;
  template std::string base_uint<256>::ToStringReverseEndian() const;
  
  // Explicit instantiations for base_uint<512>
  template base_uint<512>::base_uint(const std::string&);
  template base_uint<512>& base_uint<512>::operator<<=(unsigned int);
  template base_uint<512>& base_uint<512>::operator>>=(unsigned int);
  template std::string base_uint<512>::GetHex() const;
  template std::string base_uint<512>::ToString() const;
  template std::string base_uint<512>::ToStringReverseEndian() const;
  
  // This implementation directly uses shifts instead of going
  // through an intermediate MPI representation.
  arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
  {
      int nSize = nCompact >> 24;
      uint32_t nWord = nCompact & 0x007fffff;
      if (nSize <= 3) {
          nWord >>= 8 * (3 - nSize);
          *this = nWord;
      } else {
          *this = nWord;
          *this <<= 8 * (nSize - 3);
      }
      if (pfNegative)
          *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
      if (pfOverflow)
          *pfOverflow = nWord != 0 && ((nSize > 34) ||
                                       (nWord > 0xff && nSize > 33) ||
                                       (nWord > 0xffff && nSize > 32));
      return *this;
  }
  
  uint32_t arith_uint256::GetCompact(bool fNegative) const
  {
      int nSize = (bits() + 7) / 8;
      uint32_t nCompact = 0;
      if (nSize <= 3) {
          nCompact = GetLow64() << 8 * (3 - nSize);
      } else {
          arith_uint256 bn = *this >> 8 * (nSize - 3);
          nCompact = bn.GetLow64();
      }
      // The 0x00800000 bit denotes the sign.
      // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
      if (nCompact & 0x00800000) {
          nCompact >>= 8;
          nSize++;
      }
      assert((nCompact & ~0x007fffff) == 0);
      assert(nSize < 256);
      nCompact |= nSize << 24;
      nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
      return nCompact;
  }
  
  static void inline HashMix(uint32_t& a, uint32_t& b, uint32_t& c)
  {
      // Taken from lookup3, by Bob Jenkins.
      a -= c;
      a ^= ((c << 4) | (c >> 28));
      c += b;
      b -= a;
      b ^= ((a << 6) | (a >> 26));
      a += c;
      c -= b;
      c ^= ((b << 8) | (b >> 24));
      b += a;
      a -= c;
      a ^= ((c << 16) | (c >> 16));
      c += b;
      b -= a;
      b ^= ((a << 19) | (a >> 13));
      a += c;
      c -= b;
      c ^= ((b << 4) | (b >> 28));
      b += a;
  }
  
  static void inline HashFinal(uint32_t& a, uint32_t& b, uint32_t& c)
  {
      // Taken from lookup3, by Bob Jenkins.
      c ^= b;
      c -= ((b << 14) | (b >> 18));
      a ^= c;
      a -= ((c << 11) | (c >> 21));
      b ^= a;
      b -= ((a << 25) | (a >> 7));
      c ^= b;
      c -= ((b << 16) | (b >> 16));
      a ^= c;
      a -= ((c << 4) | (c >> 28));
      b ^= a;
      b -= ((a << 14) | (a >> 18));
      c ^= b;
      c -= ((b << 24) | (b >> 8));
  }
  
  uint64_t arith_uint256::GetHash(const arith_uint256& salt) const
  {
      uint32_t a, b, c;
      a = b = c = 0xdeadbeef + (WIDTH << 2);
  
      a += pn[0] ^ salt.pn[0];
      b += pn[1] ^ salt.pn[1];
      c += pn[2] ^ salt.pn[2];
      HashMix(a, b, c);
      a += pn[3] ^ salt.pn[3];
      b += pn[4] ^ salt.pn[4];
      c += pn[5] ^ salt.pn[5];
      HashMix(a, b, c);
      a += pn[6] ^ salt.pn[6];
      b += pn[7] ^ salt.pn[7];
      HashFinal(a, b, c);
  
      return ((((uint64_t)b) << 32) | c);
  }
  