Branch data Line data Source code
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 : : #ifndef BITCOIN_ARITH_UINT256_H
7 : : #define BITCOIN_ARITH_UINT256_H
8 : :
9 : : #include <cstdint>
10 : : #include <cstring>
11 : : #include <limits>
12 : : #include <stdexcept>
13 : : #include <string>
14 : :
15 : : class uint256;
16 : :
17 : : class uint_error : public std::runtime_error {
18 : : public:
19 [ + - ]: 2 : explicit uint_error(const std::string& str) : std::runtime_error(str) {}
20 : : };
21 : :
22 : : /** Template base class for unsigned big integers. */
23 : : template<unsigned int BITS>
24 : : class base_uint
25 : : {
26 : : protected:
27 : : static_assert(BITS / 32 > 0 && BITS % 32 == 0, "Template parameter BITS must be a positive multiple of 32.");
28 : : static constexpr int WIDTH = BITS / 32;
29 : : uint32_t pn[WIDTH];
30 : : public:
31 : :
32 : 7831061 : base_uint()
33 : : {
34 [ + + + + : 70479549 : for (int i = 0; i < WIDTH; i++)
+ + + + +
+ + + +
+ ][ + + #
# # # # #
# # # # #
# ]
[ + + + + ]
[ # # # #
# # ][ + +
+ + + + +
+ ]
35 : 62648488 : pn[i] = 0;
36 : 0 : }
37 : :
38 : 1701628 : base_uint(const base_uint& b)
39 : : {
40 [ - - - - : 15237726 : for (int i = 0; i < WIDTH; i++)
- - - - -
- - - - -
- - + + +
+ + + +
+ ][ # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ][ + + +
+ # # # #
# # # # #
# # # # #
# # # # ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ # # # #
# # # # #
# # # ][ -
- - - + +
+ + + + +
+ + + ][ -
- - - + +
- - - - +
+ + + + +
+ + - - ]
[ - - - -
+ + + + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ ][ - - -
- - - - -
+ + # # #
# # # # #
# # ]
41 : 13621528 : pn[i] = b.pn[i];
42 : 0 : }
43 : :
44 : 192517 : base_uint& operator=(const base_uint& b)
45 : : {
46 [ # # ]: 18470 : if (this != &b) {
47 [ + + + + : 1773648 : for (int i = 0; i < WIDTH; i++)
+ + ]
[ + + + + ]
[ + + ][ + +
+ + + + -
- # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ][ + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
48 : 1576576 : pn[i] = b.pn[i];
49 : : }
50 : 0 : return *this;
51 : : }
52 : :
53 : 636078 : base_uint(uint64_t b)
54 : : {
55 : 636078 : pn[0] = (unsigned int)b;
56 : 636078 : pn[1] = (unsigned int)(b >> 32);
57 [ + + + + : 4372082 : for (int i = 2; i < WIDTH; i++)
+ + ][ + +
+ + + + +
+ ][ + + +
+ # # #
# ][ + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ ][ + + ]
58 : 3816468 : pn[i] = 0;
59 : 0 : }
60 : :
61 : 80513 : base_uint operator~() const
62 : : {
63 : 724617 : base_uint ret;
64 [ + + ]: 724617 : for (int i = 0; i < WIDTH; i++)
65 : 644104 : ret.pn[i] = ~pn[i];
66 : 80513 : return ret;
67 : : }
68 : :
69 : 93515 : base_uint operator-() const
70 : : {
71 : 841635 : base_uint ret;
72 [ + + ]: 841635 : for (int i = 0; i < WIDTH; i++)
73 : 748120 : ret.pn[i] = ~pn[i];
74 : 93515 : ++ret;
75 : 93515 : return ret;
76 : : }
77 : :
78 : : double getdouble() const;
79 : :
80 : 81752 : base_uint& operator=(uint64_t b)
81 : : {
82 : 81752 : pn[0] = (unsigned int)b;
83 : 81752 : pn[1] = (unsigned int)(b >> 32);
84 [ + + + + : 572264 : for (int i = 2; i < WIDTH; i++)
+ + - - ]
85 : 490512 : pn[i] = 0;
86 : 0 : return *this;
87 : : }
88 : :
89 : 0 : base_uint& operator^=(const base_uint& b)
90 : : {
91 [ # # # # : 45 : for (int i = 0; i < WIDTH; i++)
# # # # #
# ][ + + +
+ + + + +
+ + ]
92 : 4272 : pn[i] ^= b.pn[i];
93 : 0 : return *this;
94 : : }
95 : :
96 : 0 : base_uint& operator&=(const base_uint& b)
97 : : {
98 [ # # # # : 45 : for (int i = 0; i < WIDTH; i++)
# # # # #
# ][ + + +
+ + + + +
+ + ]
99 : 144 : pn[i] &= b.pn[i];
100 : 0 : return *this;
101 : : }
102 : :
103 : 0 : base_uint& operator|=(const base_uint& b)
104 : : {
105 [ # # # # : 2349 : for (int i = 0; i < WIDTH; i++)
# # # # #
# # # ][ +
+ + + + +
+ + + + +
+ ]
106 : 2192 : pn[i] |= b.pn[i];
107 : 0 : return *this;
108 : : }
109 : :
110 : 1 : base_uint& operator^=(uint64_t b)
111 : : {
112 : 1 : pn[0] ^= (unsigned int)b;
113 : 1 : pn[1] ^= (unsigned int)(b >> 32);
114 : 0 : return *this;
115 : : }
116 : :
117 : 1 : base_uint& operator|=(uint64_t b)
118 : : {
119 : 1 : pn[0] |= (unsigned int)b;
120 : 1 : pn[1] |= (unsigned int)(b >> 32);
121 : 0 : return *this;
122 : : }
123 : :
124 : : base_uint& operator<<=(unsigned int shift);
125 : : base_uint& operator>>=(unsigned int shift);
126 : :
127 : 384422 : base_uint& operator+=(const base_uint& b)
128 : : {
129 : 384422 : uint64_t carry = 0;
130 [ + + ]: 3459798 : for (int i = 0; i < WIDTH; i++)
131 : : {
132 : 3075376 : uint64_t n = carry + pn[i] + b.pn[i];
133 : 3075376 : pn[i] = n & 0xffffffff;
134 : 3075376 : carry = n >> 32;
135 : : }
136 : 384422 : return *this;
137 : : }
138 : :
139 : 92996 : base_uint& operator-=(const base_uint& b)
140 : : {
141 : 92996 : *this += -b;
142 : 92996 : return *this;
143 : : }
144 : :
145 : 256 : base_uint& operator+=(uint64_t b64)
146 : : {
147 : 256 : base_uint b;
148 : 256 : b = b64;
149 : 256 : *this += b;
150 : 256 : return *this;
151 : : }
152 : :
153 : 1 : base_uint& operator-=(uint64_t b64)
154 : : {
155 : 1 : base_uint b;
156 : 1 : b = b64;
157 : 1 : *this += -b;
158 : 1 : return *this;
159 : : }
160 : :
161 : : base_uint& operator*=(uint32_t b32);
162 : : base_uint& operator*=(const base_uint& b);
163 : : base_uint& operator/=(const base_uint& b);
164 : :
165 : 93771 : base_uint& operator++()
166 : : {
167 : : // prefix operator
168 : 93771 : int i = 0;
169 [ + + + + ]: 101418 : while (i < WIDTH && ++pn[i] == 0)
170 : 7647 : i++;
171 : 93770 : return *this;
172 : : }
173 : :
174 : 0 : base_uint operator++(int)
175 : : {
176 : : // postfix operator
177 : 255 : const base_uint ret = *this;
178 : 255 : ++(*this);
179 : 0 : return ret;
180 : : }
181 : :
182 : 256 : base_uint& operator--()
183 : : {
184 : : // prefix operator
185 : 256 : int i = 0;
186 [ + - + + : 2303 : while (i < WIDTH && --pn[i] == std::numeric_limits<uint32_t>::max())
# # # # ]
[ + - + +
+ - - + ]
187 : 1792 : i++;
188 : 255 : return *this;
189 : : }
190 : :
191 : 0 : base_uint operator--(int)
192 : : {
193 : : // postfix operator
194 : 255 : const base_uint ret = *this;
195 : 255 : --(*this);
196 : 0 : return ret;
197 : : }
198 : :
199 : : /** Numeric ordering (unlike \ref base_blob::Compare) */
200 : : int CompareTo(const base_uint& b) const;
201 : : bool EqualTo(uint64_t b) const;
202 : :
203 : 459898 : friend inline base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; }
204 : 3032 : friend inline base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; }
205 : 2024 : friend inline base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; }
206 : 162950 : friend inline base_uint operator/(const base_uint& a, const base_uint& b) { return base_uint(a) /= b; }
207 [ + + + + ]: 247 : friend inline base_uint operator|(const base_uint& a, const base_uint& b) { return base_uint(a) |= b; }
208 [ + + + + ]: 247 : friend inline base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; }
209 [ + + + + ]: 10051 : friend inline base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; }
210 : 70768 : friend inline base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; }
211 : 109222 : friend inline base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
212 : 76 : friend inline base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
213 [ + - # # : 7008 : friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
+ + + + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - ]
214 [ + - + - : 774 : friend inline bool operator!=(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) != 0; }
+ - + - +
- + - + -
+ - + - ]
215 [ - - - - : 19533267 : friend inline bool operator>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) > 0; }
+ - ][ + -
+ - + - +
- + - + -
+ - ]
[ + - + - ]
[ # # ]
216 [ + - + - ]: 12825948 : friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; }
[ # # # #
# # # # #
# ][ + - +
- + - + -
+ - + - +
- + - +
- ]
217 [ + - + - ]: 6542879 : friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; }
[ + + # #
# # # # #
# # # # #
# # # # ]
[ + - + -
+ - + - +
- + - + -
+ - + - ]
218 [ # # # # ]: 901 : friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; }
[ + - + -
+ - + - +
- + - + -
+ - + - ]
219 [ + - # # : 172439 : friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
# # # # #
# ][ + - +
- + - + -
+ - ]
220 [ + - ]: 261 : friend inline bool operator!=(const base_uint& a, uint64_t b) { return !a.EqualTo(b); }
[ + - + - ]
221 : :
222 : : /** Hex encoding of the number (with the most significant digits first). */
223 : : std::string GetHex() const;
224 : : std::string ToString() const;
225 : :
226 : 0 : unsigned int size() const
227 : : {
228 : 0 : return sizeof(pn);
229 : : }
230 : :
231 : : /**
232 : : * Returns the position of the highest bit set plus one, or zero if the
233 : : * value is zero.
234 : : */
235 : : unsigned int bits() const;
236 : :
237 : 183579 : uint64_t GetLow64() const
238 : : {
239 : : static_assert(WIDTH >= 2, "Assertion WIDTH >= 2 failed (WIDTH = BITS / 32). BITS is a template parameter.");
240 [ + - + - : 182160 : return pn[0] | (uint64_t)pn[1] << 32;
+ - ][ + -
+ - + - +
- + - ]
241 : : }
242 : : };
243 : :
244 : : /** 256-bit unsigned big integer. */
245 [ + - + + : 404238 : class arith_uint256 : public base_uint<256> {
+ + ][ + - ]
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
- + - +
- ]
246 : : public:
247 [ + + ][ + + : 11148945 : arith_uint256() = default;
+ + + + ]
248 [ + + + + : 310117 : arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {}
+ + ]
[ + - + - ]
[ + - ][ + +
+ + + + +
+ + + + +
+ + + - +
+ + + + +
+ + ]
249 [ + - + - ]: 856522 : arith_uint256(uint64_t b) : base_uint<256>(b) {}
[ + - # #
# # # # #
# # # # #
# # # # #
# ][ + + +
+ + - + -
+ - + - +
- + - + -
+ - ][ + -
+ - + - ]
250 : :
251 : : /**
252 : : * The "compact" format is a representation of a whole
253 : : * number N using an unsigned 32bit number similar to a
254 : : * floating point format.
255 : : * The most significant 8 bits are the unsigned exponent of base 256.
256 : : * This exponent can be thought of as "number of bytes of N".
257 : : * The lower 23 bits are the mantissa.
258 : : * Bit number 24 (0x800000) represents the sign of N.
259 : : * N = (-1^sign) * mantissa * 256^(exponent-3)
260 : : *
261 : : * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn().
262 : : * MPI uses the most significant bit of the first byte as sign.
263 : : * Thus 0x1234560000 is compact (0x05123456)
264 : : * and 0xc0de000000 is compact (0x0600c0de)
265 : : *
266 : : * Bitcoin only uses this "compact" format for encoding difficulty
267 : : * targets, which are unsigned 256bit quantities. Thus, all the
268 : : * complexities of the sign bit and using base 256 are probably an
269 : : * implementation accident.
270 : : */
271 : : arith_uint256& SetCompact(uint32_t nCompact, bool *pfNegative = nullptr, bool *pfOverflow = nullptr);
272 : : uint32_t GetCompact(bool fNegative = false) const;
273 : :
274 : : friend uint256 ArithToUint256(const arith_uint256 &);
275 : : friend arith_uint256 UintToArith256(const uint256 &);
276 : : };
277 : :
278 : : uint256 ArithToUint256(const arith_uint256 &);
279 : : arith_uint256 UintToArith256(const uint256 &);
280 : :
281 : : extern template class base_uint<256>;
282 : :
283 : : #endif // BITCOIN_ARITH_UINT256_H
|
