Bitcoin Core  26.99.0
P2P Digital Currency
arith_uint256.cpp
Go to the documentation of this file.
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2022 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>
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>
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>
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>
61 {
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>
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>
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>
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 
219 {
221  for(int x=0; x<a.WIDTH; ++x)
222  WriteLE32(b.begin() + x*4, a.pn[x]);
223  return b;
224 }
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 }
arith_uint256 UintToArith256(const uint256 &a)
uint256 ArithToUint256(const arith_uint256 &a)
int ret
256-bit unsigned big integer.
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...
uint32_t GetCompact(bool fNegative=false) const
Template base class for fixed-sized opaque blobs.
Definition: uint256.h:22
constexpr unsigned char * begin()
Definition: uint256.h:68
std::string GetHex() const
Definition: uint256.cpp:11
Template base class for unsigned big integers.
Definition: arith_uint256.h:25
uint32_t pn[WIDTH]
Definition: arith_uint256.h:29
int CompareTo(const base_uint &b) const
base_uint & operator>>=(unsigned int shift)
static constexpr int WIDTH
Definition: arith_uint256.h:28
base_uint & operator*=(uint32_t b32)
bool EqualTo(uint64_t b) const
double getdouble() const
base_uint & operator<<=(unsigned int shift)
std::string ToString() const
base_uint & operator/=(const base_uint &b)
uint64_t GetLow64() const
std::string GetHex() const
unsigned int bits() const
Returns the position of the highest bit set plus one, or zero if the value is zero.
256-bit opaque blob.
Definition: uint256.h:106
static uint32_t ReadLE32(const unsigned char *ptr)
Definition: common.h:24
static void WriteLE32(unsigned char *ptr, uint32_t x)
Definition: common.h:44
assert(!tx.IsCoinBase())