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 <compare>
10 : : #include <cstdint>
11 : : #include <cstring>
12 : : #include <limits>
13 : : #include <stdexcept>
14 : : #include <string>
15 : :
16 : : class uint256;
17 : :
18 : : class uint_error : public std::runtime_error {
19 : : public:
20 [ - - + - ]: 2 : explicit uint_error(const std::string& str) : std::runtime_error(str) {}
21 : : };
22 : :
23 : : /** Template base class for unsigned big integers. */
24 : : template<unsigned int BITS>
25 : : class base_uint
26 : : {
27 : : protected:
28 : : static_assert(BITS / 32 > 0 && BITS % 32 == 0, "Template parameter BITS must be a positive multiple of 32.");
29 : : static constexpr int WIDTH = BITS / 32;
30 : : /** Big integer represented with 32-bit digits, least-significant first. */
31 : : uint32_t pn[WIDTH];
32 : : public:
33 : :
34 : 84336570 : base_uint()
35 : : {
36 [ + + + + ]: 759029130 : for (int i = 0; i < WIDTH; i++)
[ + + + +
+ + ][ + +
+ + + + +
+ + + + +
+ + ][ - -
- - + + +
+ + + + +
+ + + + -
- ][ + + ]
[ + + + +
+ + + + ]
37 : 674692560 : pn[i] = 0;
38 : 0 : }
39 : :
40 : : base_uint(const base_uint& b) = default;
41 : : base_uint& operator=(const base_uint& b) = default;
42 : :
43 : 4235160 : base_uint(uint64_t b)
44 : : {
45 : 4235160 : pn[0] = (unsigned int)b;
46 : 4235160 : pn[1] = (unsigned int)(b >> 32);
47 [ + + + + ]: 28938443 : for (int i = 2; i < WIDTH; i++)
[ + + + +
+ + ][ + +
+ + + + +
+ ][ + + +
+ + + + +
+ + + + ]
[ + + ][ + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
48 : 25410960 : pn[i] = 0;
49 : 0 : }
50 : :
51 : 707208 : base_uint operator~() const
52 : : {
53 : 6364872 : base_uint ret;
54 [ + + ]: 6364872 : for (int i = 0; i < WIDTH; i++)
55 : 5657664 : ret.pn[i] = ~pn[i];
56 : 707208 : return ret;
57 : : }
58 : :
59 : 803485 : base_uint operator-() const
60 : : {
61 : 7231365 : base_uint ret;
62 [ + + ]: 7231365 : for (int i = 0; i < WIDTH; i++)
63 : 6427880 : ret.pn[i] = ~pn[i];
64 : 803485 : ++ret;
65 : 803485 : return ret;
66 : : }
67 : :
68 : : double getdouble() const;
69 : :
70 : 720919 : base_uint& operator=(uint64_t b)
71 : : {
72 : 720919 : pn[0] = (unsigned int)b;
73 : 720919 : pn[1] = (unsigned int)(b >> 32);
74 [ - - + + : 5046433 : for (int i = 2; i < WIDTH; i++)
+ + + + -
- ]
75 : 4325514 : pn[i] = 0;
76 : 0 : return *this;
77 : : }
78 : :
79 : 534 : base_uint& operator^=(const base_uint& b)
80 : : {
81 [ # # ][ + + : 4806 : for (int i = 0; i < WIDTH; i++)
+ + + + +
+ + + +
+ ]
82 : 4272 : pn[i] ^= b.pn[i];
83 : 0 : return *this;
84 : : }
85 : :
86 : 18 : base_uint& operator&=(const base_uint& b)
87 : : {
88 [ # # ][ + + : 162 : for (int i = 0; i < WIDTH; i++)
+ + + + +
+ + + +
+ ]
89 : 144 : pn[i] &= b.pn[i];
90 : 0 : return *this;
91 : : }
92 : :
93 : 274 : base_uint& operator|=(const base_uint& b)
94 : : {
95 [ # # ][ + + : 2466 : for (int i = 0; i < WIDTH; i++)
+ + + + +
+ + + + +
+ + ]
96 : 2192 : pn[i] |= b.pn[i];
97 : 0 : return *this;
98 : : }
99 : :
100 : 1 : base_uint& operator^=(uint64_t b)
101 : : {
102 : 1 : pn[0] ^= (unsigned int)b;
103 : 1 : pn[1] ^= (unsigned int)(b >> 32);
104 : 0 : return *this;
105 : : }
106 : :
107 : 1 : base_uint& operator|=(uint64_t b)
108 : : {
109 : 1 : pn[0] |= (unsigned int)b;
110 : 1 : pn[1] |= (unsigned int)(b >> 32);
111 : 0 : return *this;
112 : : }
113 : :
114 : : base_uint& operator<<=(unsigned int shift);
115 : : base_uint& operator>>=(unsigned int shift);
116 : :
117 : 3021079 : base_uint& operator+=(const base_uint& b)
118 : : {
119 : 3021079 : uint64_t carry = 0;
120 [ + + ]: 27189711 : for (int i = 0; i < WIDTH; i++)
121 : : {
122 : 24168632 : uint64_t n = carry + pn[i] + b.pn[i];
123 : 24168632 : pn[i] = n & 0xffffffff;
124 : 24168632 : carry = n >> 32;
125 : : }
126 : 3021079 : return *this;
127 : : }
128 : :
129 : 802966 : base_uint& operator-=(const base_uint& b)
130 : : {
131 : 802966 : *this += -b;
132 : 802966 : return *this;
133 : : }
134 : :
135 : 12354 : base_uint& operator+=(uint64_t b64)
136 : : {
137 : 12354 : base_uint b;
138 : 12354 : b = b64;
139 : 12354 : *this += b;
140 : 12354 : return *this;
141 : : }
142 : :
143 : 1 : base_uint& operator-=(uint64_t b64)
144 : : {
145 : 1 : base_uint b;
146 : 1 : b = b64;
147 : 1 : *this += -b;
148 : 1 : return *this;
149 : : }
150 : :
151 : : base_uint& operator*=(uint32_t b32);
152 : : base_uint& operator*=(const base_uint& b);
153 : : base_uint& operator/=(const base_uint& b);
154 : :
155 : 803741 : base_uint& operator++()
156 : : {
157 : : // prefix operator
158 : 803741 : int i = 0;
159 [ + + + + ]: 813838 : while (i < WIDTH && ++pn[i] == 0)
160 : 10097 : i++;
161 : 803740 : return *this;
162 : : }
163 : :
164 : 255 : base_uint operator++(int)
165 : : {
166 : : // postfix operator
167 : 255 : const base_uint ret = *this;
168 : 255 : ++(*this);
169 : 0 : return ret;
170 : : }
171 : :
172 : 256 : base_uint& operator--()
173 : : {
174 : : // prefix operator
175 : 256 : int i = 0;
176 [ + - + + ]: 2303 : while (i < WIDTH && --pn[i] == std::numeric_limits<uint32_t>::max())
[ + - + +
+ - - + ]
177 : 1792 : i++;
178 : 255 : return *this;
179 : : }
180 : :
181 : 255 : base_uint operator--(int)
182 : : {
183 : : // postfix operator
184 : 255 : const base_uint ret = *this;
185 : 255 : --(*this);
186 : 0 : return ret;
187 : : }
188 : :
189 : : /** Numeric ordering (unlike \ref base_blob::Compare) */
190 : : int CompareTo(const base_uint& b) const;
191 : : bool EqualTo(uint64_t b) const;
192 : :
193 : 1891174 : friend inline base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; }
194 : 79431 : friend inline base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; }
195 : 67182 : friend inline base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; }
196 : 708543 : friend inline base_uint operator/(const base_uint& a, const base_uint& b) { return base_uint(a) /= b; }
197 : 13 : friend inline base_uint operator|(const base_uint& a, const base_uint& b) { return base_uint(a) |= b; }
198 : 13 : friend inline base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; }
199 : 529 : friend inline base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; }
200 : 291415 : friend inline base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; }
201 : 54624 : friend inline base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
202 : 13595 : friend inline base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
203 [ - + ][ + - : 8304 : friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
+ + - + +
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - ]
204 [ + + + + ]: 1860928844 : friend inline std::strong_ordering operator<=>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <=> 0; }
205 [ + - # # : 2248665 : friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
# # # # #
# # # #
# ][ + - +
- + - + -
+ - + - +
- ]
206 : :
207 : : /** Hex encoding of the number (with the most significant digits first). */
208 : : std::string GetHex() const;
209 : : std::string ToString() const;
210 : :
211 : 0 : unsigned int size() const
212 : : {
213 : 0 : return sizeof(pn);
214 : : }
215 : :
216 : : /**
217 : : * Returns the position of the highest bit set plus one, or zero if the
218 : : * value is zero.
219 : : */
220 : : unsigned int bits() const;
221 : :
222 : 451631 : uint64_t GetLow64() const
223 : : {
224 : : static_assert(WIDTH >= 2, "Assertion WIDTH >= 2 failed (WIDTH = BITS / 32). BITS is a template parameter.");
225 [ + - ][ + - : 450212 : return pn[0] | (uint64_t)pn[1] << 32;
+ - + - +
- + - ][ +
- + - + -
# # # # ]
226 : : }
227 : : };
228 : :
229 : : /** 256-bit unsigned big integer. */
230 : : class arith_uint256 : public base_uint<256> {
231 : : public:
232 [ + + # # ]: 738133016 : arith_uint256() = default;
[ + + + + ]
233 [ + + ]: 1502951 : arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {}
234 [ + - ][ + - : 5597380 : arith_uint256(uint64_t b) : base_uint<256>(b) {}
+ - + - #
# # # # #
# # # # #
# # # # #
# # ][ + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - ]
235 : :
236 : : /**
237 : : * The "compact" format is a representation of a whole
238 : : * number N using an unsigned 32bit number similar to a
239 : : * floating point format.
240 : : * The most significant 8 bits are the unsigned exponent of base 256.
241 : : * This exponent can be thought of as "number of bytes of N".
242 : : * The lower 23 bits are the mantissa.
243 : : * Bit number 24 (0x800000) represents the sign of N.
244 : : * N = (-1^sign) * mantissa * 256^(exponent-3)
245 : : *
246 : : * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn().
247 : : * MPI uses the most significant bit of the first byte as sign.
248 : : * Thus 0x1234560000 is compact (0x05123456)
249 : : * and 0xc0de000000 is compact (0x0600c0de)
250 : : *
251 : : * Bitcoin only uses this "compact" format for encoding difficulty
252 : : * targets, which are unsigned 256bit quantities. Thus, all the
253 : : * complexities of the sign bit and using base 256 are probably an
254 : : * implementation accident.
255 : : */
256 : : arith_uint256& SetCompact(uint32_t nCompact, bool *pfNegative = nullptr, bool *pfOverflow = nullptr);
257 : : uint32_t GetCompact(bool fNegative = false) const;
258 : :
259 : : friend uint256 ArithToUint256(const arith_uint256 &);
260 : : friend arith_uint256 UintToArith256(const uint256 &);
261 : : };
262 : :
263 : : // Keeping the trivially copyable property is beneficial for performance
264 : : static_assert(std::is_trivially_copyable_v<arith_uint256>);
265 : :
266 : : uint256 ArithToUint256(const arith_uint256 &);
267 : : arith_uint256 UintToArith256(const uint256 &);
268 : :
269 : : extern template class base_uint<256>;
270 : :
271 : : #endif // BITCOIN_ARITH_UINT256_H
|
