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 : : /** Big integer represented with 32-bit digits, least-significant first. */
30 : : uint32_t pn[WIDTH];
31 : : public:
32 : :
33 : 18859199 : base_uint()
34 : : {
35 [ + + + + : 169732791 : for (int i = 0; i < WIDTH; i++)
- - - - +
+ + + -
- ]
[ + + + + ]
[ + + + +
+ + + + ]
[ + + + +
+ + + + +
+ + + +
+ ][ # # #
# # # ]
36 : 150873592 : pn[i] = 0;
37 : 0 : }
38 : :
39 : 13571539 : base_uint(const base_uint& b)
40 : : {
41 [ + + + + : 121518112 : for (int i = 0; i < WIDTH; i++)
+ + - - -
- + + + +
+ + + + -
- ][ + + -
- - - - -
+ + # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ + + - -
+ + + + +
+ + + + +
+ + ][ - -
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ][ + + +
+ + + + +
+ + + + +
+ ][ + + +
+ + + - -
- - + + +
+ + + + +
- - ][ + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
# # ][ - -
- - + + +
+ - - - -
- - - - +
+ + + + +
+ + ][ - -
- - + + +
+ + + + +
+ + # # ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # ]
42 : 108580944 : pn[i] = b.pn[i];
43 : 0 : }
44 : :
45 : 2804239 : base_uint& operator=(const base_uint& b)
46 : : {
47 [ # # ]: 288417 : if (this != &b) {
48 [ + + + + : 26496288 : for (int i = 0; i < WIDTH; i++)
+ + - - #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ ][ + + +
+ + + -
- ][ + + +
+ + + ]
[ + + + + ]
49 : 23552256 : pn[i] = b.pn[i];
50 : : }
51 : 0 : return *this;
52 : : }
53 : :
54 : 4308823 : base_uint(uint64_t b)
55 : : {
56 : 4308823 : pn[0] = (unsigned int)b;
57 : 4308823 : pn[1] = (unsigned int)(b >> 32);
58 [ + + + + : 29532719 : for (int i = 2; i < WIDTH; i++)
+ + + + #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ + + #
# ][ + + +
+ + + +
+ ][ + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
[ + + + + ]
59 : 25852938 : pn[i] = 0;
60 : 0 : }
61 : :
62 : 629089 : base_uint operator~() const
63 : : {
64 : 5661801 : base_uint ret;
65 [ + + ]: 5661801 : for (int i = 0; i < WIDTH; i++)
66 : 5032712 : ret.pn[i] = ~pn[i];
67 : 629089 : return ret;
68 : : }
69 : :
70 : 713538 : base_uint operator-() const
71 : : {
72 : 6421842 : base_uint ret;
73 [ + + ]: 6421842 : for (int i = 0; i < WIDTH; i++)
74 : 5708304 : ret.pn[i] = ~pn[i];
75 : 713538 : ++ret;
76 : 713538 : return ret;
77 : : }
78 : :
79 : : double getdouble() const;
80 : :
81 : 630702 : base_uint& operator=(uint64_t b)
82 : : {
83 : 630702 : pn[0] = (unsigned int)b;
84 : 630702 : pn[1] = (unsigned int)(b >> 32);
85 [ + + + + : 4414914 : for (int i = 2; i < WIDTH; i++)
+ + - - ]
86 : 3784212 : pn[i] = 0;
87 : 0 : return *this;
88 : : }
89 : :
90 : 0 : base_uint& operator^=(const base_uint& b)
91 : : {
92 [ + + + + : 45 : for (int i = 0; i < WIDTH; i++)
+ + + + +
+ ][ # # ]
93 : 4272 : pn[i] ^= b.pn[i];
94 : 0 : return *this;
95 : : }
96 : :
97 : 0 : base_uint& operator&=(const base_uint& b)
98 : : {
99 [ + + + + : 45 : for (int i = 0; i < WIDTH; i++)
+ + + + +
+ ][ # # ]
100 : 144 : pn[i] &= b.pn[i];
101 : 0 : return *this;
102 : : }
103 : :
104 : 0 : base_uint& operator|=(const base_uint& b)
105 : : {
106 [ + + + + : 2349 : for (int i = 0; i < WIDTH; i++)
+ + + + +
+ + + ]
[ # # ]
107 : 2192 : pn[i] |= b.pn[i];
108 : 0 : return *this;
109 : : }
110 : :
111 : 1 : base_uint& operator^=(uint64_t b)
112 : : {
113 : 1 : pn[0] ^= (unsigned int)b;
114 : 1 : pn[1] ^= (unsigned int)(b >> 32);
115 : 0 : return *this;
116 : : }
117 : :
118 : 1 : base_uint& operator|=(uint64_t b)
119 : : {
120 : 1 : pn[0] |= (unsigned int)b;
121 : 1 : pn[1] |= (unsigned int)(b >> 32);
122 : 0 : return *this;
123 : : }
124 : :
125 : : base_uint& operator<<=(unsigned int shift);
126 : : base_uint& operator>>=(unsigned int shift);
127 : :
128 : 2649828 : base_uint& operator+=(const base_uint& b)
129 : : {
130 : 2649828 : uint64_t carry = 0;
131 [ + + ]: 23848452 : for (int i = 0; i < WIDTH; i++)
132 : : {
133 : 21198624 : uint64_t n = carry + pn[i] + b.pn[i];
134 : 21198624 : pn[i] = n & 0xffffffff;
135 : 21198624 : carry = n >> 32;
136 : : }
137 : 2649828 : return *this;
138 : : }
139 : :
140 : 713019 : base_uint& operator-=(const base_uint& b)
141 : : {
142 : 713019 : *this += -b;
143 : 713019 : return *this;
144 : : }
145 : :
146 : 256 : base_uint& operator+=(uint64_t b64)
147 : : {
148 : 256 : base_uint b;
149 : 256 : b = b64;
150 : 256 : *this += b;
151 : 256 : return *this;
152 : : }
153 : :
154 : 1 : base_uint& operator-=(uint64_t b64)
155 : : {
156 : 1 : base_uint b;
157 : 1 : b = b64;
158 : 1 : *this += -b;
159 : 1 : return *this;
160 : : }
161 : :
162 : : base_uint& operator*=(uint32_t b32);
163 : : base_uint& operator*=(const base_uint& b);
164 : : base_uint& operator/=(const base_uint& b);
165 : :
166 : 713794 : base_uint& operator++()
167 : : {
168 : : // prefix operator
169 : 713794 : int i = 0;
170 [ + + + + ]: 723105 : while (i < WIDTH && ++pn[i] == 0)
171 : 9311 : i++;
172 : 713793 : return *this;
173 : : }
174 : :
175 : 0 : base_uint operator++(int)
176 : : {
177 : : // postfix operator
178 : 255 : const base_uint ret = *this;
179 : 255 : ++(*this);
180 : 0 : return ret;
181 : : }
182 : :
183 : 256 : base_uint& operator--()
184 : : {
185 : : // prefix operator
186 : 256 : int i = 0;
187 [ + - + + : 2303 : while (i < WIDTH && --pn[i] == std::numeric_limits<uint32_t>::max())
+ - - + ]
[ + - + + ]
188 : 1792 : i++;
189 : 255 : return *this;
190 : : }
191 : :
192 : 0 : base_uint operator--(int)
193 : : {
194 : : // postfix operator
195 : 255 : const base_uint ret = *this;
196 : 255 : --(*this);
197 : 0 : return ret;
198 : : }
199 : :
200 : : /** Numeric ordering (unlike \ref base_blob::Compare) */
201 : : int CompareTo(const base_uint& b) const;
202 : : bool EqualTo(uint64_t b) const;
203 : :
204 : 3352974 : friend inline base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; }
205 : 136354 : friend inline base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; }
206 : 135318 : friend inline base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; }
207 : 1260850 : 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 [ + + + + ]: 247 : friend inline base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; }
210 [ + + + + ]: 10051 : friend inline base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; }
211 : 569892 : friend inline base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; }
212 : 109226 : friend inline base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
213 : 26472 : friend inline base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
214 [ + - + - : 7018 : friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + + + +
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - +
- ][ - + ]
215 [ + - + - : 774 : friend inline bool operator!=(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) != 0; }
+ - + - +
- + - + -
+ - + - ]
216 [ + - + - : 772681694 : friend inline bool operator>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) > 0; }
+ - # # #
# # # #
# ][ + - +
- + - + -
+ - + - +
- ][ - - -
- + - ]
217 [ + - + - : 507802873 : friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; }
# # # # #
# # # # #
# # # # ]
[ + - + -
+ - + - +
- + - + -
+ - + - ]
[ # # # #
# # # # #
# ]
218 [ + + + - : 251664235 : friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; }
# # # # #
# # # # #
# # # # ]
[ + - + -
+ - + - +
- + - + -
+ - + - ]
[ + + ]
219 [ + - + - : 2932060 : friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; }
+ - + - +
- + - + -
+ - + - ]
[ # # # # ]
220 [ + - + - : 2513706 : friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
+ - + - +
- + - ]
221 [ + - # # ]: 261 : friend inline bool operator!=(const base_uint& a, uint64_t b) { return !a.EqualTo(b); }
[ + - + - ]
222 : :
223 : : /** Hex encoding of the number (with the most significant digits first). */
224 : : std::string GetHex() const;
225 : : std::string ToString() const;
226 : :
227 : 0 : unsigned int size() const
228 : : {
229 : 0 : return sizeof(pn);
230 : : }
231 : :
232 : : /**
233 : : * Returns the position of the highest bit set plus one, or zero if the
234 : : * value is zero.
235 : : */
236 : : unsigned int bits() const;
237 : :
238 : 433458 : uint64_t GetLow64() const
239 : : {
240 : : static_assert(WIDTH >= 2, "Assertion WIDTH >= 2 failed (WIDTH = BITS / 32). BITS is a template parameter.");
241 [ + - + - : 432066 : return pn[0] | (uint64_t)pn[1] << 32;
+ - + - +
- ][ + - +
- + - # #
# # ]
242 : : }
243 : : };
244 : :
245 : : /** 256-bit unsigned big integer. */
246 [ + - + + : 6458588 : class arith_uint256 : public base_uint<256> {
+ + # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ][ + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + -
+ - + - ]
[ + - + +
+ + ]
247 : : public:
248 [ + + # # : 83953308 : arith_uint256() = default;
# # ][ + +
+ + + + ]
[ + - + - ]
249 [ + + - - : 2703591 : arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {}
+ + # # #
# # # # #
# # # # #
# # # #
# ][ + + +
+ + + + +
+ + + + +
+ + - + +
+ + + + +
+ ][ + + +
+ + + ]
[ + - + - ]
250 [ + - + - : 6081843 : arith_uint256(uint64_t b) : base_uint<256>(b) {}
+ - # # #
# # # # #
# # # # #
# # # # #
# # # # ]
[ + - ][ + -
+ - + - +
- + + + +
+ - + - +
- + - + -
+ - + - +
- ]
[ + - + - ]
251 : :
252 : : /**
253 : : * The "compact" format is a representation of a whole
254 : : * number N using an unsigned 32bit number similar to a
255 : : * floating point format.
256 : : * The most significant 8 bits are the unsigned exponent of base 256.
257 : : * This exponent can be thought of as "number of bytes of N".
258 : : * The lower 23 bits are the mantissa.
259 : : * Bit number 24 (0x800000) represents the sign of N.
260 : : * N = (-1^sign) * mantissa * 256^(exponent-3)
261 : : *
262 : : * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn().
263 : : * MPI uses the most significant bit of the first byte as sign.
264 : : * Thus 0x1234560000 is compact (0x05123456)
265 : : * and 0xc0de000000 is compact (0x0600c0de)
266 : : *
267 : : * Bitcoin only uses this "compact" format for encoding difficulty
268 : : * targets, which are unsigned 256bit quantities. Thus, all the
269 : : * complexities of the sign bit and using base 256 are probably an
270 : : * implementation accident.
271 : : */
272 : : arith_uint256& SetCompact(uint32_t nCompact, bool *pfNegative = nullptr, bool *pfOverflow = nullptr);
273 : : uint32_t GetCompact(bool fNegative = false) const;
274 : :
275 : : friend uint256 ArithToUint256(const arith_uint256 &);
276 : : friend arith_uint256 UintToArith256(const uint256 &);
277 : : };
278 : :
279 : : uint256 ArithToUint256(const arith_uint256 &);
280 : : arith_uint256 UintToArith256(const uint256 &);
281 : :
282 : : extern template class base_uint<256>;
283 : :
284 : : #endif // BITCOIN_ARITH_UINT256_H
|
