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 : 22065212 : base_uint()
35 : : {
36 [ + + ][ + + : 198586908 : for (int i = 0; i < WIDTH; i++)
+ + + + +
+ + + + +
+ + ]
[ + + + + ]
[ + + + +
+ + ][ - -
- - + + +
+ + + + +
+ + + + -
- ][ + + +
+ + + +
+ ]
37 : 176521696 : pn[i] = 0;
38 : 0 : }
39 : :
40 : 14960511 : base_uint(const base_uint& b)
41 : : {
42 [ + + ][ - - : 152602927 : for (int i = 0; i < WIDTH; i++)
- - - - -
- + + + +
- - - - +
+ + + + +
+ + ][ + +
+ + # # #
# # # # #
# # # # ]
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + ][ -
- - - + +
+ + ][ + +
- - - - -
- + + + +
+ + + + ]
[ - - - -
+ + + + +
+ + + +
+ ][ - - -
- + + + +
- - - - +
+ - - - -
+ + + + +
+ + + -
- ][ - - +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
[ - - - -
- - - - +
+ ]
43 : 136296624 : pn[i] = b.pn[i];
44 : 0 : }
45 : :
46 : 3030670 : base_uint& operator=(const base_uint& b)
47 : : {
48 [ # # ]: 295248 : if (this != &b) {
49 [ + + + + : 28554246 : for (int i = 0; i < WIDTH; i++)
+ + ]
[ + + # # ]
[ + + + + ]
[ - - + +
+ + + + -
- ][ + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
50 : 25381552 : pn[i] = b.pn[i];
51 : : }
52 : 0 : return *this;
53 : : }
54 : :
55 : 4726044 : base_uint(uint64_t b)
56 : : {
57 : 4726044 : pn[0] = (unsigned int)b;
58 : 4726044 : pn[1] = (unsigned int)(b >> 32);
59 [ + + + + : 32357941 : for (int i = 2; i < WIDTH; i++)
+ + ][ + +
+ + + + +
+ ]
[ + + + + ]
[ + + # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ][ +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ ]
60 : 28356264 : pn[i] = 0;
61 : 0 : }
62 : :
63 : 724414 : base_uint operator~() const
64 : : {
65 : 6519726 : base_uint ret;
66 [ + + ]: 6519726 : for (int i = 0; i < WIDTH; i++)
67 : 5795312 : ret.pn[i] = ~pn[i];
68 : 724414 : return ret;
69 : : }
70 : :
71 : 811259 : base_uint operator-() const
72 : : {
73 : 7301331 : base_uint ret;
74 [ + + ]: 7301331 : for (int i = 0; i < WIDTH; i++)
75 : 6490072 : ret.pn[i] = ~pn[i];
76 : 811259 : ++ret;
77 : 811259 : return ret;
78 : : }
79 : :
80 : : double getdouble() const;
81 : :
82 : 726026 : base_uint& operator=(uint64_t b)
83 : : {
84 : 726026 : pn[0] = (unsigned int)b;
85 : 726026 : pn[1] = (unsigned int)(b >> 32);
86 [ - - + + : 5082182 : for (int i = 2; i < WIDTH; i++)
+ + + + -
- ]
87 : 4356156 : pn[i] = 0;
88 : 0 : return *this;
89 : : }
90 : :
91 : 0 : base_uint& operator^=(const base_uint& b)
92 : : {
93 [ # # ][ + + : 45 : for (int i = 0; i < WIDTH; i++)
+ + + + +
+ + + ]
94 : 4272 : pn[i] ^= b.pn[i];
95 : 0 : return *this;
96 : : }
97 : :
98 : 0 : base_uint& operator&=(const base_uint& b)
99 : : {
100 [ # # ][ + + : 45 : for (int i = 0; i < WIDTH; i++)
+ + + + +
+ + + ]
101 : 144 : pn[i] &= b.pn[i];
102 : 0 : return *this;
103 : : }
104 : :
105 : 0 : base_uint& operator|=(const base_uint& b)
106 : : {
107 [ # # ][ + + : 2349 : for (int i = 0; i < WIDTH; i++)
+ + + + +
+ + + +
+ ]
108 : 2192 : pn[i] |= b.pn[i];
109 : 0 : return *this;
110 : : }
111 : :
112 : 1 : base_uint& operator^=(uint64_t b)
113 : : {
114 : 1 : pn[0] ^= (unsigned int)b;
115 : 1 : pn[1] ^= (unsigned int)(b >> 32);
116 : 0 : return *this;
117 : : }
118 : :
119 : 1 : base_uint& operator|=(uint64_t b)
120 : : {
121 : 1 : pn[0] |= (unsigned int)b;
122 : 1 : pn[1] |= (unsigned int)(b >> 32);
123 : 0 : return *this;
124 : : }
125 : :
126 : : base_uint& operator<<=(unsigned int shift);
127 : : base_uint& operator>>=(unsigned int shift);
128 : :
129 : 3033526 : base_uint& operator+=(const base_uint& b)
130 : : {
131 : 3033526 : uint64_t carry = 0;
132 [ + + ]: 27301734 : for (int i = 0; i < WIDTH; i++)
133 : : {
134 : 24268208 : uint64_t n = carry + pn[i] + b.pn[i];
135 : 24268208 : pn[i] = n & 0xffffffff;
136 : 24268208 : carry = n >> 32;
137 : : }
138 : 3033526 : return *this;
139 : : }
140 : :
141 : 810740 : base_uint& operator-=(const base_uint& b)
142 : : {
143 : 810740 : *this += -b;
144 : 810740 : return *this;
145 : : }
146 : :
147 : 256 : base_uint& operator+=(uint64_t b64)
148 : : {
149 : 256 : base_uint b;
150 : 256 : b = b64;
151 : 256 : *this += b;
152 : 256 : return *this;
153 : : }
154 : :
155 : 1 : base_uint& operator-=(uint64_t b64)
156 : : {
157 : 1 : base_uint b;
158 : 1 : b = b64;
159 : 1 : *this += -b;
160 : 1 : return *this;
161 : : }
162 : :
163 : : base_uint& operator*=(uint32_t b32);
164 : : base_uint& operator*=(const base_uint& b);
165 : : base_uint& operator/=(const base_uint& b);
166 : :
167 : 811515 : base_uint& operator++()
168 : : {
169 : : // prefix operator
170 : 811515 : int i = 0;
171 [ + + + + ]: 821288 : while (i < WIDTH && ++pn[i] == 0)
172 : 9773 : i++;
173 : 811514 : return *this;
174 : : }
175 : :
176 : 0 : base_uint operator++(int)
177 : : {
178 : : // postfix operator
179 : 255 : const base_uint ret = *this;
180 : 255 : ++(*this);
181 : 0 : return ret;
182 : : }
183 : :
184 : 256 : base_uint& operator--()
185 : : {
186 : : // prefix operator
187 : 256 : int i = 0;
188 [ + - + + ]: 2303 : while (i < WIDTH && --pn[i] == std::numeric_limits<uint32_t>::max())
[ + - + +
+ - - + ]
189 : 1792 : i++;
190 : 255 : return *this;
191 : : }
192 : :
193 : 0 : base_uint operator--(int)
194 : : {
195 : : // postfix operator
196 : 255 : const base_uint ret = *this;
197 : 255 : --(*this);
198 : 0 : return ret;
199 : : }
200 : :
201 : : /** Numeric ordering (unlike \ref base_blob::Compare) */
202 : : int CompareTo(const base_uint& b) const;
203 : : bool EqualTo(uint64_t b) const;
204 : :
205 : 3752040 : friend inline base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; }
206 : 140144 : friend inline base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; }
207 : 139106 : friend inline base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; }
208 : 1451496 : 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 [ + + + + ]: 247 : friend inline base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; }
211 [ + + + + ]: 10051 : friend inline base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; }
212 : 576580 : friend inline base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; }
213 : 109230 : friend inline base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
214 : 26788 : friend inline base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
215 [ + - + - : 8304 : friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + + +
- + + + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - ][ - + ]
216 [ + + + + ]: 1533005754 : friend inline std::strong_ordering operator<=>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <=> 0; }
217 [ + - + - : 2732005 : friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
+ - + - +
- + - +
- ][ + - ]
218 : :
219 : : /** Hex encoding of the number (with the most significant digits first). */
220 : : std::string GetHex() const;
221 : : std::string ToString() const;
222 : :
223 : 0 : unsigned int size() const
224 : : {
225 : 0 : return sizeof(pn);
226 : : }
227 : :
228 : : /**
229 : : * Returns the position of the highest bit set plus one, or zero if the
230 : : * value is zero.
231 : : */
232 : : unsigned int bits() const;
233 : :
234 : 436812 : uint64_t GetLow64() const
235 : : {
236 : : static_assert(WIDTH >= 2, "Assertion WIDTH >= 2 failed (WIDTH = BITS / 32). BITS is a template parameter.");
237 [ + - + - : 435414 : return pn[0] | (uint64_t)pn[1] << 32;
+ - ][ + -
+ - + - +
- + - ]
238 : : }
239 : : };
240 : :
241 : : /** 256-bit unsigned big integer. */
242 [ + - # # : 6838305 : class arith_uint256 : public base_uint<256> {
# # ]
[ + - + + ]
[ + - + +
+ + ][ + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + - + -
+ - ]
243 : : public:
244 [ + + ][ + + : 111438101 : arith_uint256() = default;
+ + + + ]
[ + - + - ]
245 [ + + + + : 2842476 : arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {}
+ + ]
[ + - + + ]
[ + + + +
+ + + + +
+ + + + +
+ - + + +
+ + + +
+ ][ + - ]
246 [ + - + - ]: 6532416 : arith_uint256(uint64_t b) : base_uint<256>(b) {}
[ + - + -
+ - + - +
+ + + + -
+ - + - +
- + - + -
+ - + - ]
[ + - # #
# # ][ + -
+ - + - ]
247 : :
248 : : /**
249 : : * The "compact" format is a representation of a whole
250 : : * number N using an unsigned 32bit number similar to a
251 : : * floating point format.
252 : : * The most significant 8 bits are the unsigned exponent of base 256.
253 : : * This exponent can be thought of as "number of bytes of N".
254 : : * The lower 23 bits are the mantissa.
255 : : * Bit number 24 (0x800000) represents the sign of N.
256 : : * N = (-1^sign) * mantissa * 256^(exponent-3)
257 : : *
258 : : * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn().
259 : : * MPI uses the most significant bit of the first byte as sign.
260 : : * Thus 0x1234560000 is compact (0x05123456)
261 : : * and 0xc0de000000 is compact (0x0600c0de)
262 : : *
263 : : * Bitcoin only uses this "compact" format for encoding difficulty
264 : : * targets, which are unsigned 256bit quantities. Thus, all the
265 : : * complexities of the sign bit and using base 256 are probably an
266 : : * implementation accident.
267 : : */
268 : : arith_uint256& SetCompact(uint32_t nCompact, bool *pfNegative = nullptr, bool *pfOverflow = nullptr);
269 : : uint32_t GetCompact(bool fNegative = false) const;
270 : :
271 : : friend uint256 ArithToUint256(const arith_uint256 &);
272 : : friend arith_uint256 UintToArith256(const uint256 &);
273 : : };
274 : :
275 : : uint256 ArithToUint256(const arith_uint256 &);
276 : : arith_uint256 UintToArith256(const uint256 &);
277 : :
278 : : extern template class base_uint<256>;
279 : :
280 : : #endif // BITCOIN_ARITH_UINT256_H
|
