1  // Copyright (c) 2009-2010 Satoshi Nakamoto
  2  // Copyright (c) 2009-present 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  #include <cassert>
 12  
 13  template <unsigned int BITS>
 14  base_uint<BITS>& base_uint<BITS>::operator<<=(unsigned int shift)
 15  {
 16      base_uint<BITS> a(*this);
 17      for (int i = 0; i < WIDTH; i++)
 18          pn[i] = 0;
 19      int k = shift / 32;
 20      shift = shift % 32;
 21      for (int i = 0; i < WIDTH; i++) {
 22          if (i + k + 1 < WIDTH && shift != 0)
 23              pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
 24          if (i + k < WIDTH)
 25              pn[i + k] |= (a.pn[i] << shift);
 26      }
 27      return *this;
 28  }
 29  
 30  template <unsigned int BITS>
 31  base_uint<BITS>& base_uint<BITS>::operator>>=(unsigned int shift)
 32  {
 33      base_uint<BITS> a(*this);
 34      for (int i = 0; i < WIDTH; i++)
 35          pn[i] = 0;
 36      int k = shift / 32;
 37      shift = shift % 32;
 38      for (int i = 0; i < WIDTH; i++) {
 39          if (i - k - 1 >= 0 && shift != 0)
 40              pn[i - k - 1] |= (a.pn[i] << (32 - shift));
 41          if (i - k >= 0)
 42              pn[i - k] |= (a.pn[i] >> shift);
 43      }
 44      return *this;
 45  }
 46  
 47  template <unsigned int BITS>
 48  base_uint<BITS>& base_uint<BITS>::operator*=(uint32_t b32)
 49  {
 50      uint64_t carry = 0;
 51      for (int i = 0; i < WIDTH; i++) {
 52          uint64_t n = carry + (uint64_t)b32 * pn[i];
 53          pn[i] = n & 0xffffffff;
 54          carry = n >> 32;
 55      }
 56      return *this;
 57  }
 58  
 59  template <unsigned int BITS>
 60  base_uint<BITS>& base_uint<BITS>::operator*=(const base_uint& b)
 61  {
 62      base_uint<BITS> a;
 63      for (int j = 0; j < WIDTH; j++) {
 64          uint64_t carry = 0;
 65          for (int i = 0; i + j < WIDTH; i++) {
 66              uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
 67              a.pn[i + j] = n & 0xffffffff;
 68              carry = n >> 32;
 69          }
 70      }
 71      *this = a;
 72      return *this;
 73  }
 74  
 75  template <unsigned int BITS>
 76  base_uint<BITS>& base_uint<BITS>::operator/=(const base_uint& b)
 77  {
 78      base_uint<BITS> div = b;     // make a copy, so we can shift.
 79      base_uint<BITS> num = *this; // make a copy, so we can subtract.
 80      *this = 0;                   // the quotient.
 81      int num_bits = num.bits();
 82      int div_bits = div.bits();
 83      if (div_bits == 0)
 84          throw uint_error("Division by zero");
 85      if (div_bits > num_bits) // the result is certainly 0.
 86          return *this;
 87      int shift = num_bits - div_bits;
 88      div <<= shift; // shift so that div and num align.
 89      while (shift >= 0) {
 90          if (num >= div) {
 91              num -= div;
 92              pn[shift / 32] |= (1U << (shift & 31)); // set a bit of the result.
 93          }
 94          div >>= 1; // shift back.
 95          shift--;
 96      }
 97      // num now contains the remainder of the division.
 98      return *this;
 99  }
100  
101  template <unsigned int BITS>
102  int base_uint<BITS>::CompareTo(const base_uint<BITS>& b) const
103  {
104      for (int i = WIDTH - 1; i >= 0; i--) {
105          if (pn[i] < b.pn[i])
106              return -1;
107          if (pn[i] > b.pn[i])
108              return 1;
109      }
110      return 0;
111  }
112  
113  template <unsigned int BITS>
114  bool base_uint<BITS>::EqualTo(uint64_t b) const
115  {
116      for (int i = WIDTH - 1; i >= 2; i--) {
117          if (pn[i])
118              return false;
119      }
120      if (pn[1] != (b >> 32))
121          return false;
122      if (pn[0] != (b & 0xfffffffful))
123          return false;
124      return true;
125  }
126  
127  template <unsigned int BITS>
128  double base_uint<BITS>::getdouble() const
129  {
130      double ret = 0.0;
131      double fact = 1.0;
132      for (int i = 0; i < WIDTH; i++) {
133          ret += fact * pn[i];
134          fact *= 4294967296.0;
135      }
136      return ret;
137  }
138  
139  template <unsigned int BITS>
140  std::string base_uint<BITS>::GetHex() const
141  {
142      base_blob<BITS> b;
143      for (int x = 0; x < this->WIDTH; ++x) {
144          WriteLE32(b.begin() + x*4, this->pn[x]);
145      }
146      return b.GetHex();
147  }
148  
149  template <unsigned int BITS>
150  std::string base_uint<BITS>::ToString() const
151  {
152      return GetHex();
153  }
154  
155  template <unsigned int BITS>
156  unsigned int base_uint<BITS>::bits() const
157  {
158      for (int pos = WIDTH - 1; pos >= 0; pos--) {
159          if (pn[pos]) {
160              for (int nbits = 31; nbits > 0; nbits--) {
161                  if (pn[pos] & 1U << nbits)
162                      return 32 * pos + nbits + 1;
163              }
164              return 32 * pos + 1;
165          }
166      }
167      return 0;
168  }
169  
170  // Explicit instantiations for base_uint<256>
171  template class base_uint<256>;
172  
173  // This implementation directly uses shifts instead of going
174  // through an intermediate MPI representation.
175  arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
176  {
177      int nSize = nCompact >> 24;
178      uint32_t nWord = nCompact & 0x007fffff;
179      if (nSize <= 3) {
180          nWord >>= 8 * (3 - nSize);
181          *this = nWord;
182      } else {
183          *this = nWord;
184          *this <<= 8 * (nSize - 3);
185      }
186      if (pfNegative)
187          *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
188      if (pfOverflow)
189          *pfOverflow = nWord != 0 && ((nSize > 34) ||
190                                       (nWord > 0xff && nSize > 33) ||
191                                       (nWord > 0xffff && nSize > 32));
192      return *this;
193  }
194  
195  uint32_t arith_uint256::GetCompact(bool fNegative) const
196  {
197      int nSize = (bits() + 7) / 8;
198      uint32_t nCompact = 0;
199      if (nSize <= 3) {
200          nCompact = GetLow64() << 8 * (3 - nSize);
201      } else {
202          arith_uint256 bn = *this >> 8 * (nSize - 3);
203          nCompact = bn.GetLow64();
204      }
205      // The 0x00800000 bit denotes the sign.
206      // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
207      if (nCompact & 0x00800000) {
208          nCompact >>= 8;
209          nSize++;
210      }
211      assert((nCompact & ~0x007fffffU) == 0);
212      assert(nSize < 256);
213      nCompact |= nSize << 24;
214      nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
215      return nCompact;
216  }
217  
218  uint256 ArithToUint256(const arith_uint256 &a)
219  {
220      uint256 b;
221      for(int x=0; x<a.WIDTH; ++x)
222          WriteLE32(b.begin() + x*4, a.pn[x]);
223      return b;
224  }
225  arith_uint256 UintToArith256(const uint256 &a)
226  {
227      arith_uint256 b;
228      for(int x=0; x<b.WIDTH; ++x)
229          b.pn[x] = ReadLE32(a.begin() + x*4);
230      return b;
231  }
232  
233  // Explicit instantiations for base_uint<6144> (used in test/fuzz/muhash.cpp).
234  template base_uint<6144>& base_uint<6144>::operator*=(const base_uint<6144>& b);
235  template base_uint<6144>& base_uint<6144>::operator/=(const base_uint<6144>& b);