Bitcoin Core  0.20.99
P2P Digital Currency
arith_uint256.cpp
Go to the documentation of this file.
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2019 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 
12 template <unsigned int BITS>
13 base_uint<BITS>::base_uint(const std::string& str)
14 {
15  static_assert(BITS/32 > 0 && BITS%32 == 0, "Template parameter BITS must be a positive multiple of 32.");
16 
17  SetHex(str);
18 }
19 
20 template <unsigned int BITS>
22 {
23  base_uint<BITS> a(*this);
24  for (int i = 0; i < WIDTH; i++)
25  pn[i] = 0;
26  int k = shift / 32;
27  shift = shift % 32;
28  for (int i = 0; i < WIDTH; i++) {
29  if (i + k + 1 < WIDTH && shift != 0)
30  pn[i + k + 1] |= (a.pn[i] >> (32 - shift));
31  if (i + k < WIDTH)
32  pn[i + k] |= (a.pn[i] << shift);
33  }
34  return *this;
35 }
36 
37 template <unsigned int BITS>
39 {
40  base_uint<BITS> a(*this);
41  for (int i = 0; i < WIDTH; i++)
42  pn[i] = 0;
43  int k = shift / 32;
44  shift = shift % 32;
45  for (int i = 0; i < WIDTH; i++) {
46  if (i - k - 1 >= 0 && shift != 0)
47  pn[i - k - 1] |= (a.pn[i] << (32 - shift));
48  if (i - k >= 0)
49  pn[i - k] |= (a.pn[i] >> shift);
50  }
51  return *this;
52 }
53 
54 template <unsigned int BITS>
56 {
57  uint64_t carry = 0;
58  for (int i = 0; i < WIDTH; i++) {
59  uint64_t n = carry + (uint64_t)b32 * pn[i];
60  pn[i] = n & 0xffffffff;
61  carry = n >> 32;
62  }
63  return *this;
64 }
65 
66 template <unsigned int BITS>
68 {
70  for (int j = 0; j < WIDTH; j++) {
71  uint64_t carry = 0;
72  for (int i = 0; i + j < WIDTH; i++) {
73  uint64_t n = carry + a.pn[i + j] + (uint64_t)pn[j] * b.pn[i];
74  a.pn[i + j] = n & 0xffffffff;
75  carry = n >> 32;
76  }
77  }
78  *this = a;
79  return *this;
80 }
81 
82 template <unsigned int BITS>
84 {
85  base_uint<BITS> div = b; // make a copy, so we can shift.
86  base_uint<BITS> num = *this; // make a copy, so we can subtract.
87  *this = 0; // the quotient.
88  int num_bits = num.bits();
89  int div_bits = div.bits();
90  if (div_bits == 0)
91  throw uint_error("Division by zero");
92  if (div_bits > num_bits) // the result is certainly 0.
93  return *this;
94  int shift = num_bits - div_bits;
95  div <<= shift; // shift so that div and num align.
96  while (shift >= 0) {
97  if (num >= div) {
98  num -= div;
99  pn[shift / 32] |= (1 << (shift & 31)); // set a bit of the result.
100  }
101  div >>= 1; // shift back.
102  shift--;
103  }
104  // num now contains the remainder of the division.
105  return *this;
106 }
107 
108 template <unsigned int BITS>
110 {
111  for (int i = WIDTH - 1; i >= 0; i--) {
112  if (pn[i] < b.pn[i])
113  return -1;
114  if (pn[i] > b.pn[i])
115  return 1;
116  }
117  return 0;
118 }
119 
120 template <unsigned int BITS>
121 bool base_uint<BITS>::EqualTo(uint64_t b) const
122 {
123  for (int i = WIDTH - 1; i >= 2; i--) {
124  if (pn[i])
125  return false;
126  }
127  if (pn[1] != (b >> 32))
128  return false;
129  if (pn[0] != (b & 0xfffffffful))
130  return false;
131  return true;
132 }
133 
134 template <unsigned int BITS>
136 {
137  double ret = 0.0;
138  double fact = 1.0;
139  for (int i = 0; i < WIDTH; i++) {
140  ret += fact * pn[i];
141  fact *= 4294967296.0;
142  }
143  return ret;
144 }
145 
146 template <unsigned int BITS>
147 std::string base_uint<BITS>::GetHex() const
148 {
149  return ArithToUint256(*this).GetHex();
150 }
151 
152 template <unsigned int BITS>
153 void base_uint<BITS>::SetHex(const char* psz)
154 {
155  *this = UintToArith256(uint256S(psz));
156 }
157 
158 template <unsigned int BITS>
159 void base_uint<BITS>::SetHex(const std::string& str)
160 {
161  SetHex(str.c_str());
162 }
163 
164 template <unsigned int BITS>
165 std::string base_uint<BITS>::ToString() const
166 {
167  return (GetHex());
168 }
169 
170 template <unsigned int BITS>
171 unsigned int base_uint<BITS>::bits() const
172 {
173  for (int pos = WIDTH - 1; pos >= 0; pos--) {
174  if (pn[pos]) {
175  for (int nbits = 31; nbits > 0; nbits--) {
176  if (pn[pos] & 1U << nbits)
177  return 32 * pos + nbits + 1;
178  }
179  return 32 * pos + 1;
180  }
181  }
182  return 0;
183 }
184 
185 // Explicit instantiations for base_uint<256>
186 template base_uint<256>::base_uint(const std::string&);
187 template base_uint<256>& base_uint<256>::operator<<=(unsigned int);
188 template base_uint<256>& base_uint<256>::operator>>=(unsigned int);
189 template base_uint<256>& base_uint<256>::operator*=(uint32_t b32);
192 template int base_uint<256>::CompareTo(const base_uint<256>&) const;
193 template bool base_uint<256>::EqualTo(uint64_t) const;
194 template double base_uint<256>::getdouble() const;
195 template std::string base_uint<256>::GetHex() const;
196 template std::string base_uint<256>::ToString() const;
197 template void base_uint<256>::SetHex(const char*);
198 template void base_uint<256>::SetHex(const std::string&);
199 template unsigned int base_uint<256>::bits() const;
200 
201 // This implementation directly uses shifts instead of going
202 // through an intermediate MPI representation.
203 arith_uint256& arith_uint256::SetCompact(uint32_t nCompact, bool* pfNegative, bool* pfOverflow)
204 {
205  int nSize = nCompact >> 24;
206  uint32_t nWord = nCompact & 0x007fffff;
207  if (nSize <= 3) {
208  nWord >>= 8 * (3 - nSize);
209  *this = nWord;
210  } else {
211  *this = nWord;
212  *this <<= 8 * (nSize - 3);
213  }
214  if (pfNegative)
215  *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0;
216  if (pfOverflow)
217  *pfOverflow = nWord != 0 && ((nSize > 34) ||
218  (nWord > 0xff && nSize > 33) ||
219  (nWord > 0xffff && nSize > 32));
220  return *this;
221 }
222 
223 uint32_t arith_uint256::GetCompact(bool fNegative) const
224 {
225  int nSize = (bits() + 7) / 8;
226  uint32_t nCompact = 0;
227  if (nSize <= 3) {
228  nCompact = GetLow64() << 8 * (3 - nSize);
229  } else {
230  arith_uint256 bn = *this >> 8 * (nSize - 3);
231  nCompact = bn.GetLow64();
232  }
233  // The 0x00800000 bit denotes the sign.
234  // Thus, if it is already set, divide the mantissa by 256 and increase the exponent.
235  if (nCompact & 0x00800000) {
236  nCompact >>= 8;
237  nSize++;
238  }
239  assert((nCompact & ~0x007fffff) == 0);
240  assert(nSize < 256);
241  nCompact |= nSize << 24;
242  nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0);
243  return nCompact;
244 }
245 
247 {
248  uint256 b;
249  for(int x=0; x<a.WIDTH; ++x)
250  WriteLE32(b.begin() + x*4, a.pn[x]);
251  return b;
252 }
254 {
255  arith_uint256 b;
256  for(int x=0; x<b.WIDTH; ++x)
257  b.pn[x] = ReadLE32(a.begin() + x*4);
258  return b;
259 }
bool EqualTo(uint64_t b) const
void SetHex(const char *psz)
std::string ToString() const
base_uint & operator/=(const base_uint &b)
static constexpr int WIDTH
Definition: arith_uint256.h:27
static void WriteLE32(unsigned char *ptr, uint32_t x)
Definition: common.h:44
Template base class for unsigned big integers.
Definition: arith_uint256.h:24
base_uint & operator<<=(unsigned int shift)
unsigned char * begin()
Definition: uint256.h:54
uint32_t GetCompact(bool fNegative=false) const
arith_uint256 UintToArith256(const uint256 &a)
uint32_t pn[WIDTH]
Definition: arith_uint256.h:28
uint256 uint256S(const char *str)
Definition: uint256.h:130
int CompareTo(const base_uint &b) const
friend uint256 ArithToUint256(const arith_uint256 &)
256-bit unsigned big integer.
static uint32_t ReadLE32(const unsigned char *ptr)
Definition: common.h:24
256-bit opaque blob.
Definition: uint256.h:120
uint256 ArithToUint256(const arith_uint256 &a)
uint64_t GetLow64() const
std::string GetHex() const
Definition: uint256.cpp:20
base_uint & operator*=(uint32_t b32)
arith_uint256 & SetCompact(uint32_t nCompact, bool *pfNegative=nullptr, bool *pfOverflow=nullptr)
The "compact" format is a representation of a whole number N using an unsigned 32bit number similar t...
std::string GetHex() const
double getdouble() const
friend arith_uint256 UintToArith256(const uint256 &)
base_uint & operator>>=(unsigned int shift)
unsigned int bits() const
Returns the position of the highest bit set plus one, or zero if the value is zero.