Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2014 The Bitcoin 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 <assert.h>
10 : #include <cstring>
11 : #include <stdexcept>
12 : #include <stdint.h>
13 : #include <string>
14 : #include <vector>
15 :
16 : class uint256;
17 :
18 2 : 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 : enum { WIDTH=BITS/32 };
29 : uint32_t pn[WIDTH];
30 : public:
31 :
32 0 : base_uint()
33 : {
34 4599985 : for (int i = 0; i < WIDTH; i++)
35 4088944 : pn[i] = 0;
36 0 : }
37 :
38 0 : base_uint(const base_uint& b)
39 : {
40 12322831 : for (int i = 0; i < WIDTH; i++)
41 11313672 : pn[i] = b.pn[i];
42 0 : }
43 :
44 : base_uint& operator=(const base_uint& b)
45 : {
46 1229099 : for (int i = 0; i < WIDTH; i++)
47 1202424 : pn[i] = b.pn[i];
48 : return *this;
49 : }
50 :
51 0 : base_uint(uint64_t b)
52 : {
53 357261 : pn[0] = (unsigned int)b;
54 357261 : pn[1] = (unsigned int)(b >> 32);
55 2500827 : for (int i = 2; i < WIDTH; i++)
56 2143566 : pn[i] = 0;
57 0 : }
58 :
59 : explicit base_uint(const std::string& str);
60 :
61 : bool operator!() const
62 : {
63 904 : for (int i = 0; i < WIDTH; i++)
64 1164 : if (pn[i] != 0)
65 : return false;
66 : return true;
67 : }
68 :
69 : const base_uint operator~() const
70 : {
71 : base_uint ret;
72 222464 : for (int i = 0; i < WIDTH; i++)
73 222464 : ret.pn[i] = ~pn[i];
74 : return ret;
75 : }
76 :
77 40052 : const base_uint operator-() const
78 : {
79 : base_uint ret;
80 320416 : for (int i = 0; i < WIDTH; i++)
81 320416 : ret.pn[i] = ~pn[i];
82 : ret++;
83 40052 : return ret;
84 : }
85 :
86 : double getdouble() const;
87 :
88 : base_uint& operator=(uint64_t b)
89 : {
90 30043 : pn[0] = (unsigned int)b;
91 30043 : pn[1] = (unsigned int)(b >> 32);
92 210301 : for (int i = 2; i < WIDTH; i++)
93 180258 : pn[i] = 0;
94 : return *this;
95 : }
96 :
97 : base_uint& operator^=(const base_uint& b)
98 : {
99 21656 : for (int i = 0; i < WIDTH; i++)
100 21656 : pn[i] ^= b.pn[i];
101 : return *this;
102 : }
103 :
104 : base_uint& operator&=(const base_uint& b)
105 : {
106 17528 : for (int i = 0; i < WIDTH; i++)
107 17528 : pn[i] &= b.pn[i];
108 : return *this;
109 : }
110 :
111 : base_uint& operator|=(const base_uint& b)
112 : {
113 2192 : for (int i = 0; i < WIDTH; i++)
114 2192 : pn[i] |= b.pn[i];
115 : return *this;
116 : }
117 :
118 : base_uint& operator^=(uint64_t b)
119 : {
120 1 : pn[0] ^= (unsigned int)b;
121 1 : pn[1] ^= (unsigned int)(b >> 32);
122 : return *this;
123 : }
124 :
125 : base_uint& operator|=(uint64_t b)
126 : {
127 2 : pn[0] |= (unsigned int)b;
128 2 : pn[1] |= (unsigned int)(b >> 32);
129 : return *this;
130 : }
131 :
132 : base_uint& operator<<=(unsigned int shift);
133 : base_uint& operator>>=(unsigned int shift);
134 :
135 : base_uint& operator+=(const base_uint& b)
136 : {
137 39789 : uint64_t carry = 0;
138 1422405 : for (int i = 0; i < WIDTH; i++)
139 : {
140 1382616 : uint64_t n = carry + pn[i] + b.pn[i];
141 1382616 : pn[i] = n & 0xffffffff;
142 1382616 : carry = n >> 32;
143 : }
144 : return *this;
145 : }
146 :
147 39533 : base_uint& operator-=(const base_uint& b)
148 : {
149 79066 : *this += -b;
150 39533 : return *this;
151 : }
152 :
153 256 : base_uint& operator+=(uint64_t b64)
154 : {
155 : base_uint b;
156 : b = b64;
157 : *this += b;
158 256 : return *this;
159 : }
160 :
161 1 : base_uint& operator-=(uint64_t b64)
162 : {
163 : base_uint b;
164 : b = b64;
165 2 : *this += -b;
166 1 : return *this;
167 : }
168 :
169 : base_uint& operator*=(uint32_t b32);
170 : base_uint& operator*=(const base_uint& b);
171 : base_uint& operator/=(const base_uint& b);
172 :
173 : base_uint& operator++()
174 : {
175 : // prefix operator
176 1 : int i = 0;
177 45195 : while (++pn[i] == 0 && i < WIDTH-1)
178 4887 : i++;
179 : return *this;
180 : }
181 :
182 0 : const base_uint operator++(int)
183 : {
184 : // postfix operator
185 : const base_uint ret = *this;
186 : ++(*this);
187 0 : return ret;
188 : }
189 :
190 : base_uint& operator--()
191 : {
192 : // prefix operator
193 1 : int i = 0;
194 2303 : while (--pn[i] == (uint32_t)-1 && i < WIDTH-1)
195 1792 : i++;
196 : return *this;
197 : }
198 :
199 0 : const base_uint operator--(int)
200 : {
201 : // postfix operator
202 : const base_uint ret = *this;
203 : --(*this);
204 0 : return ret;
205 : }
206 :
207 : int CompareTo(const base_uint& b) const;
208 : bool EqualTo(uint64_t b) const;
209 :
210 132780 : friend inline const base_uint operator+(const base_uint& a, const base_uint& b) { return base_uint(a) += b; }
211 4596 : friend inline const base_uint operator-(const base_uint& a, const base_uint& b) { return base_uint(a) -= b; }
212 3036 : friend inline const base_uint operator*(const base_uint& a, const base_uint& b) { return base_uint(a) *= b; }
213 86308 : friend inline const base_uint operator/(const base_uint& a, const base_uint& b) { return base_uint(a) /= b; }
214 13 : friend inline const base_uint operator|(const base_uint& a, const base_uint& b) { return base_uint(a) |= b; }
215 2186 : friend inline const base_uint operator&(const base_uint& a, const base_uint& b) { return base_uint(a) &= b; }
216 2702 : friend inline const base_uint operator^(const base_uint& a, const base_uint& b) { return base_uint(a) ^= b; }
217 48897 : friend inline const base_uint operator>>(const base_uint& a, int shift) { return base_uint(a) >>= shift; }
218 164220 : friend inline const base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
219 264 : friend inline const base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
220 7515 : friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
221 774 : friend inline bool operator!=(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) != 0; }
222 4739061 : friend inline bool operator>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) > 0; }
223 2893160 : friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; }
224 1588033 : friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; }
225 901 : friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; }
226 89218 : friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
227 2429 : friend inline bool operator!=(const base_uint& a, uint64_t b) { return !a.EqualTo(b); }
228 :
229 : std::string GetHex() const;
230 : void SetHex(const char* psz);
231 : void SetHex(const std::string& str);
232 : std::string ToString() const;
233 :
234 0 : unsigned int size() const
235 : {
236 0 : return sizeof(pn);
237 : }
238 :
239 : /**
240 : * Returns the position of the highest bit set plus one, or zero if the
241 : * value is zero.
242 : */
243 : unsigned int bits() const;
244 :
245 0 : uint64_t GetLow64() const
246 : {
247 : assert(WIDTH >= 2);
248 164494 : return pn[0] | (uint64_t)pn[1] << 32;
249 : }
250 : };
251 :
252 : /** 256-bit unsigned big integer. */
253 491998 : class arith_uint256 : public base_uint<256> {
254 : public:
255 442972 : arith_uint256() {}
256 117223 : arith_uint256(const base_uint<256>& b) : base_uint<256>(b) {}
257 240638 : arith_uint256(uint64_t b) : base_uint<256>(b) {}
258 16 : explicit arith_uint256(const std::string& str) : base_uint<256>(str) {}
259 :
260 : /**
261 : * The "compact" format is a representation of a whole
262 : * number N using an unsigned 32bit number similar to a
263 : * floating point format.
264 : * The most significant 8 bits are the unsigned exponent of base 256.
265 : * This exponent can be thought of as "number of bytes of N".
266 : * The lower 23 bits are the mantissa.
267 : * Bit number 24 (0x800000) represents the sign of N.
268 : * N = (-1^sign) * mantissa * 256^(exponent-3)
269 : *
270 : * Satoshi's original implementation used BN_bn2mpi() and BN_mpi2bn().
271 : * MPI uses the most significant bit of the first byte as sign.
272 : * Thus 0x1234560000 is compact (0x05123456)
273 : * and 0xc0de000000 is compact (0x0600c0de)
274 : *
275 : * Bitcoin only uses this "compact" format for encoding difficulty
276 : * targets, which are unsigned 256bit quantities. Thus, all the
277 : * complexities of the sign bit and using base 256 are probably an
278 : * implementation accident.
279 : */
280 : arith_uint256& SetCompact(uint32_t nCompact, bool *pfNegative = NULL, bool *pfOverflow = NULL);
281 : uint32_t GetCompact(bool fNegative = false) const;
282 :
283 : friend uint256 ArithToUint256(const arith_uint256 &);
284 : friend arith_uint256 UintToArith256(const uint256 &);
285 : };
286 :
287 : uint256 ArithToUint256(const arith_uint256 &);
288 : arith_uint256 UintToArith256(const uint256 &);
289 :
290 : #endif // BITCOIN_ARITH_UINT256_H
|
