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 [ - - + - ]: 33697 : 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 : 12815822 : base_uint()
35 : : {
36 [ - - + + : 130676222 : for (int i = 0; i < WIDTH; i++)
+ + + + -
- - - + +
+ + - - ]
[ + + + +
# # # # #
# # # #
# ][ + + +
+ + + + +
+ + + + +
+ ][ + + +
+ + + ]
[ + + ]
37 : 117860400 : 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 : 2743025 : base_uint(uint64_t b)
44 : : {
45 : 2743025 : pn[0] = (unsigned int)b;
46 : 2743025 : pn[1] = (unsigned int)(b >> 32);
47 [ + + + + : 18359798 : for (int i = 2; i < WIDTH; i++)
+ + ][ + +
+ + + + +
+ ][ # # #
# # # # #
# # # # ]
[ + + + + ]
[ # # # #
# # # # #
# ][ + + +
+ + + + +
+ + ]
48 : 16458150 : pn[i] = 0;
49 : 0 : }
50 : :
51 : 699097 : base_uint operator~() const
52 : : {
53 : 6291873 : base_uint ret;
54 [ + + ]: 6291873 : for (int i = 0; i < WIDTH; i++)
55 : 5592776 : ret.pn[i] = ~pn[i];
56 : 699097 : return ret;
57 : : }
58 : :
59 : 7188065 : base_uint operator-() const
60 : : {
61 : 79820697 : base_uint ret;
62 [ + + ]: 79820697 : for (int i = 0; i < WIDTH; i++)
63 : 72632632 : ret.pn[i] = ~pn[i];
64 : 7188065 : ++ret;
65 : 7188065 : return ret;
66 : : }
67 : :
68 : : double getdouble() const;
69 : :
70 : 819268 : base_uint& operator=(uint64_t b)
71 : : {
72 : 819268 : pn[0] = (unsigned int)b;
73 : 819268 : pn[1] = (unsigned int)(b >> 32);
74 [ + + + + : 5775724 : for (int i = 2; i < WIDTH; i++)
- - - - -
- ]
75 : 4956456 : pn[i] = 0;
76 : 0 : return *this;
77 : : }
78 : :
79 : 0 : base_uint& operator^=(const base_uint& b)
80 : : {
81 [ # # ]: 0 : for (int i = 0; i < WIDTH; i++)
82 : 0 : pn[i] ^= b.pn[i];
83 : 0 : return *this;
84 : : }
85 : :
86 : 0 : base_uint& operator&=(const base_uint& b)
87 : : {
88 [ # # ]: 0 : for (int i = 0; i < WIDTH; i++)
89 : 0 : pn[i] &= b.pn[i];
90 : 0 : return *this;
91 : : }
92 : :
93 : 0 : base_uint& operator|=(const base_uint& b)
94 : : {
95 [ # # ]: 0 : for (int i = 0; i < WIDTH; i++)
96 : 0 : pn[i] |= b.pn[i];
97 : 0 : return *this;
98 : : }
99 : :
100 : 0 : base_uint& operator^=(uint64_t b)
101 : : {
102 : 0 : pn[0] ^= (unsigned int)b;
103 : 0 : pn[1] ^= (unsigned int)(b >> 32);
104 : 0 : return *this;
105 : : }
106 : :
107 : 0 : base_uint& operator|=(uint64_t b)
108 : : {
109 : 0 : pn[0] |= (unsigned int)b;
110 : 0 : 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 : 9257029 : base_uint& operator+=(const base_uint& b)
118 : : {
119 : 9257029 : uint64_t carry = 0;
120 [ + + ]: 98441373 : for (int i = 0; i < WIDTH; i++)
121 : : {
122 : 89184344 : uint64_t n = carry + pn[i] + b.pn[i];
123 : 89184344 : pn[i] = n & 0xffffffff;
124 : 89184344 : carry = n >> 32;
125 : : }
126 : 9257029 : return *this;
127 : : }
128 : :
129 : 7188065 : base_uint& operator-=(const base_uint& b)
130 : : {
131 : 7188065 : *this += -b;
132 : 7188065 : return *this;
133 : : }
134 : :
135 : 0 : base_uint& operator+=(uint64_t b64)
136 : : {
137 : 0 : base_uint b;
138 : 0 : b = b64;
139 : 0 : *this += b;
140 : 0 : return *this;
141 : : }
142 : :
143 : 0 : base_uint& operator-=(uint64_t b64)
144 : : {
145 : 0 : base_uint b;
146 : 0 : b = b64;
147 : 0 : *this += -b;
148 : 0 : 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 : 7188065 : base_uint& operator++()
156 : : {
157 : : // prefix operator
158 : 7188065 : int i = 0;
159 [ + + + + ]: 22075014 : while (i < WIDTH && ++pn[i] == 0)
160 : 14886949 : i++;
161 : 7188065 : return *this;
162 : : }
163 : :
164 : 0 : base_uint operator++(int)
165 : : {
166 : : // postfix operator
167 : 0 : const base_uint ret = *this;
168 : 0 : ++(*this);
169 : 0 : return ret;
170 : : }
171 : :
172 : 0 : base_uint& operator--()
173 : : {
174 : : // prefix operator
175 : 0 : int i = 0;
176 [ # # # # ]: 0 : while (i < WIDTH && --pn[i] == std::numeric_limits<uint32_t>::max())
177 : 0 : i++;
178 : 0 : return *this;
179 : : }
180 : :
181 : 0 : base_uint operator--(int)
182 : : {
183 : : // postfix operator
184 : 0 : const base_uint ret = *this;
185 : 0 : --(*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 : 1657073 : friend inline base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; }
194 : 82423 : friend inline base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; }
195 : 75532 : friend inline base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; }
196 : 758860 : friend inline base_uint operator/(const base_uint& a, const base_uint& b) { return base_uint(a) /= b; }
197 : : friend inline base_uint operator|(const base_uint& a, const base_uint& b) { return base_uint(a) |= b; }
198 : : friend inline base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; }
199 : : friend inline base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; }
200 : 687708 : friend inline base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; }
201 : 275 : friend inline base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
202 : 5028 : friend inline base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
203 [ + - # # ]: 7220 : friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
[ + + + +
- + ]
[ - + - + ]
204 [ + + + + ]: 327072627 : friend inline std::strong_ordering operator<=>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <=> 0; }
205 : 728068 : 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 : 741212 : uint64_t GetLow64() const
223 : : {
224 : : static_assert(WIDTH >= 2, "Assertion WIDTH >= 2 failed (WIDTH = BITS / 32). BITS is a template parameter.");
225 [ # # ]: 741212 : 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 [ + + ]: 12796089 : arith_uint256() = default;
[ + - + - ]
233 [ + - ]: 1750003 : arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {}
234 [ + - ]: 2441908 : 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
|
