Projects : bitcoin : bitcoin_dumpblock_no_losers
1 | // Copyright (c) 2009-2010 Satoshi Nakamoto |
2 | // Copyright (c) 2011 The Bitcoin developers |
3 | // Distributed under the MIT/X11 software license, see the accompanying |
4 | // file license.txt or http://www.opensource.org/licenses/mit-license.php. |
5 | #ifndef BITCOIN_BIGNUM_H |
6 | #define BITCOIN_BIGNUM_H |
7 | |
8 | #include <stdexcept> |
9 | #include <vector> |
10 | #include <openssl/bn.h> |
11 | |
12 | #include "util.h" |
13 | |
14 | class bignum_error : public std::runtime_error |
15 | { |
16 | public: |
17 | explicit bignum_error(const std::string& str) : std::runtime_error(str) {} |
18 | }; |
19 | |
20 | |
21 | |
22 | class CAutoBN_CTX |
23 | { |
24 | protected: |
25 | BN_CTX* pctx; |
26 | BN_CTX* operator=(BN_CTX* pnew) { return pctx = pnew; } |
27 | |
28 | public: |
29 | CAutoBN_CTX() |
30 | { |
31 | pctx = BN_CTX_new(); |
32 | if (pctx == NULL) |
33 | throw bignum_error("CAutoBN_CTX : BN_CTX_new() returned NULL"); |
34 | } |
35 | |
36 | ~CAutoBN_CTX() |
37 | { |
38 | if (pctx != NULL) |
39 | BN_CTX_free(pctx); |
40 | } |
41 | |
42 | operator BN_CTX*() { return pctx; } |
43 | BN_CTX& operator*() { return *pctx; } |
44 | BN_CTX** operator&() { return &pctx; } |
45 | bool operator!() { return (pctx == NULL); } |
46 | }; |
47 | |
48 | |
49 | |
50 | class CBigNum : public BIGNUM |
51 | { |
52 | public: |
53 | CBigNum() |
54 | { |
55 | BN_init(this); |
56 | } |
57 | |
58 | CBigNum(const CBigNum& b) |
59 | { |
60 | BN_init(this); |
61 | if (!BN_copy(this, &b)) |
62 | { |
63 | BN_clear_free(this); |
64 | throw bignum_error("CBigNum::CBigNum(const CBigNum&) : BN_copy failed"); |
65 | } |
66 | } |
67 | |
68 | CBigNum& operator=(const CBigNum& b) |
69 | { |
70 | if (!BN_copy(this, &b)) |
71 | throw bignum_error("CBigNum::operator= : BN_copy failed"); |
72 | return (*this); |
73 | } |
74 | |
75 | ~CBigNum() |
76 | { |
77 | BN_clear_free(this); |
78 | } |
79 | |
80 | CBigNum(char n) { BN_init(this); if (n >= 0) setulong(n); else setint64(n); } |
81 | CBigNum(short n) { BN_init(this); if (n >= 0) setulong(n); else setint64(n); } |
82 | CBigNum(int n) { BN_init(this); if (n >= 0) setulong(n); else setint64(n); } |
83 | CBigNum(long n) { BN_init(this); if (n >= 0) setulong(n); else setint64(n); } |
84 | CBigNum(int64 n) { BN_init(this); setint64(n); } |
85 | CBigNum(unsigned char n) { BN_init(this); setulong(n); } |
86 | CBigNum(unsigned short n) { BN_init(this); setulong(n); } |
87 | CBigNum(unsigned int n) { BN_init(this); setulong(n); } |
88 | CBigNum(unsigned long n) { BN_init(this); setulong(n); } |
89 | CBigNum(uint64 n) { BN_init(this); setuint64(n); } |
90 | explicit CBigNum(uint256 n) { BN_init(this); setuint256(n); } |
91 | |
92 | explicit CBigNum(const std::vector<unsigned char>& vch) |
93 | { |
94 | BN_init(this); |
95 | setvch(vch); |
96 | } |
97 | |
98 | void setulong(unsigned long n) |
99 | { |
100 | if (!BN_set_word(this, n)) |
101 | throw bignum_error("CBigNum conversion from unsigned long : BN_set_word failed"); |
102 | } |
103 | |
104 | unsigned long getulong() const |
105 | { |
106 | return BN_get_word(this); |
107 | } |
108 | |
109 | unsigned int getuint() const |
110 | { |
111 | return BN_get_word(this); |
112 | } |
113 | |
114 | int getint() const |
115 | { |
116 | unsigned long n = BN_get_word(this); |
117 | if (!BN_is_negative(this)) |
118 | return (n > INT_MAX ? INT_MAX : n); |
119 | else |
120 | return (n > INT_MAX ? INT_MIN : -(int)n); |
121 | } |
122 | |
123 | void setint64(int64 n) |
124 | { |
125 | unsigned char pch[sizeof(n) + 6]; |
126 | unsigned char* p = pch + 4; |
127 | bool fNegative = false; |
128 | if (n < (int64)0) |
129 | { |
130 | n = -n; |
131 | fNegative = true; |
132 | } |
133 | bool fLeadingZeroes = true; |
134 | for (int i = 0; i < 8; i++) |
135 | { |
136 | unsigned char c = (n >> 56) & 0xff; |
137 | n <<= 8; |
138 | if (fLeadingZeroes) |
139 | { |
140 | if (c == 0) |
141 | continue; |
142 | if (c & 0x80) |
143 | *p++ = (fNegative ? 0x80 : 0); |
144 | else if (fNegative) |
145 | c |= 0x80; |
146 | fLeadingZeroes = false; |
147 | } |
148 | *p++ = c; |
149 | } |
150 | unsigned int nSize = p - (pch + 4); |
151 | pch[0] = (nSize >> 24) & 0xff; |
152 | pch[1] = (nSize >> 16) & 0xff; |
153 | pch[2] = (nSize >> 8) & 0xff; |
154 | pch[3] = (nSize) & 0xff; |
155 | BN_mpi2bn(pch, p - pch, this); |
156 | } |
157 | |
158 | void setuint64(uint64 n) |
159 | { |
160 | unsigned char pch[sizeof(n) + 6]; |
161 | unsigned char* p = pch + 4; |
162 | bool fLeadingZeroes = true; |
163 | for (int i = 0; i < 8; i++) |
164 | { |
165 | unsigned char c = (n >> 56) & 0xff; |
166 | n <<= 8; |
167 | if (fLeadingZeroes) |
168 | { |
169 | if (c == 0) |
170 | continue; |
171 | if (c & 0x80) |
172 | *p++ = 0; |
173 | fLeadingZeroes = false; |
174 | } |
175 | *p++ = c; |
176 | } |
177 | unsigned int nSize = p - (pch + 4); |
178 | pch[0] = (nSize >> 24) & 0xff; |
179 | pch[1] = (nSize >> 16) & 0xff; |
180 | pch[2] = (nSize >> 8) & 0xff; |
181 | pch[3] = (nSize) & 0xff; |
182 | BN_mpi2bn(pch, p - pch, this); |
183 | } |
184 | |
185 | void setuint256(uint256 n) |
186 | { |
187 | unsigned char pch[sizeof(n) + 6]; |
188 | unsigned char* p = pch + 4; |
189 | bool fLeadingZeroes = true; |
190 | unsigned char* pbegin = (unsigned char*)&n; |
191 | unsigned char* psrc = pbegin + sizeof(n); |
192 | while (psrc != pbegin) |
193 | { |
194 | unsigned char c = *(--psrc); |
195 | if (fLeadingZeroes) |
196 | { |
197 | if (c == 0) |
198 | continue; |
199 | if (c & 0x80) |
200 | *p++ = 0; |
201 | fLeadingZeroes = false; |
202 | } |
203 | *p++ = c; |
204 | } |
205 | unsigned int nSize = p - (pch + 4); |
206 | pch[0] = (nSize >> 24) & 0xff; |
207 | pch[1] = (nSize >> 16) & 0xff; |
208 | pch[2] = (nSize >> 8) & 0xff; |
209 | pch[3] = (nSize >> 0) & 0xff; |
210 | BN_mpi2bn(pch, p - pch, this); |
211 | } |
212 | |
213 | uint256 getuint256() |
214 | { |
215 | unsigned int nSize = BN_bn2mpi(this, NULL); |
216 | if (nSize < 4) |
217 | return 0; |
218 | std::vector<unsigned char> vch(nSize); |
219 | BN_bn2mpi(this, &vch[0]); |
220 | if (vch.size() > 4) |
221 | vch[4] &= 0x7f; |
222 | uint256 n = 0; |
223 | for (int i = 0, j = vch.size()-1; i < sizeof(n) && j >= 4; i++, j--) |
224 | ((unsigned char*)&n)[i] = vch[j]; |
225 | return n; |
226 | } |
227 | |
228 | void setvch(const std::vector<unsigned char>& vch) |
229 | { |
230 | std::vector<unsigned char> vch2(vch.size() + 4); |
231 | unsigned int nSize = vch.size(); |
232 | // BIGNUM's byte stream format expects 4 bytes of |
233 | // big endian size data info at the front |
234 | vch2[0] = (nSize >> 24) & 0xff; |
235 | vch2[1] = (nSize >> 16) & 0xff; |
236 | vch2[2] = (nSize >> 8) & 0xff; |
237 | vch2[3] = (nSize >> 0) & 0xff; |
238 | // swap data to big endian |
239 | reverse_copy(vch.begin(), vch.end(), vch2.begin() + 4); |
240 | BN_mpi2bn(&vch2[0], vch2.size(), this); |
241 | } |
242 | |
243 | std::vector<unsigned char> getvch() const |
244 | { |
245 | unsigned int nSize = BN_bn2mpi(this, NULL); |
246 | if (nSize < 4) |
247 | return std::vector<unsigned char>(); |
248 | std::vector<unsigned char> vch(nSize); |
249 | BN_bn2mpi(this, &vch[0]); |
250 | vch.erase(vch.begin(), vch.begin() + 4); |
251 | reverse(vch.begin(), vch.end()); |
252 | return vch; |
253 | } |
254 | |
255 | CBigNum& SetCompact(unsigned int nCompact) |
256 | { |
257 | unsigned int nSize = nCompact >> 24; |
258 | std::vector<unsigned char> vch(4 + nSize); |
259 | vch[3] = nSize; |
260 | if (nSize >= 1) vch[4] = (nCompact >> 16) & 0xff; |
261 | if (nSize >= 2) vch[5] = (nCompact >> 8) & 0xff; |
262 | if (nSize >= 3) vch[6] = (nCompact >> 0) & 0xff; |
263 | BN_mpi2bn(&vch[0], vch.size(), this); |
264 | return *this; |
265 | } |
266 | |
267 | unsigned int GetCompact() const |
268 | { |
269 | unsigned int nSize = BN_bn2mpi(this, NULL); |
270 | std::vector<unsigned char> vch(nSize); |
271 | nSize -= 4; |
272 | BN_bn2mpi(this, &vch[0]); |
273 | unsigned int nCompact = nSize << 24; |
274 | if (nSize >= 1) nCompact |= (vch[4] << 16); |
275 | if (nSize >= 2) nCompact |= (vch[5] << 8); |
276 | if (nSize >= 3) nCompact |= (vch[6] << 0); |
277 | return nCompact; |
278 | } |
279 | |
280 | void SetHex(const std::string& str) |
281 | { |
282 | // skip 0x |
283 | const char* psz = str.c_str(); |
284 | while (isspace(*psz)) |
285 | psz++; |
286 | bool fNegative = false; |
287 | if (*psz == '-') |
288 | { |
289 | fNegative = true; |
290 | psz++; |
291 | } |
292 | if (psz[0] == '0' && tolower(psz[1]) == 'x') |
293 | psz += 2; |
294 | while (isspace(*psz)) |
295 | psz++; |
296 | |
297 | // hex string to bignum |
298 | static char phexdigit[256] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0 }; |
299 | *this = 0; |
300 | while (isxdigit(*psz)) |
301 | { |
302 | *this <<= 4; |
303 | int n = phexdigit[*psz++]; |
304 | *this += n; |
305 | } |
306 | if (fNegative) |
307 | *this = 0 - *this; |
308 | } |
309 | |
310 | std::string ToString(int nBase=10) const |
311 | { |
312 | CAutoBN_CTX pctx; |
313 | CBigNum bnBase = nBase; |
314 | CBigNum bn0 = 0; |
315 | std::string str; |
316 | CBigNum bn = *this; |
317 | BN_set_negative(&bn, false); |
318 | CBigNum dv; |
319 | CBigNum rem; |
320 | if (BN_cmp(&bn, &bn0) == 0) |
321 | return "0"; |
322 | while (BN_cmp(&bn, &bn0) > 0) |
323 | { |
324 | if (!BN_div(&dv, &rem, &bn, &bnBase, pctx)) |
325 | throw bignum_error("CBigNum::ToString() : BN_div failed"); |
326 | bn = dv; |
327 | unsigned int c = rem.getulong(); |
328 | str += "0123456789abcdef"[c]; |
329 | } |
330 | if (BN_is_negative(this)) |
331 | str += "-"; |
332 | reverse(str.begin(), str.end()); |
333 | return str; |
334 | } |
335 | |
336 | std::string GetHex() const |
337 | { |
338 | return ToString(16); |
339 | } |
340 | |
341 | unsigned int GetSerializeSize(int nType=0, int nVersion=VERSION) const |
342 | { |
343 | return ::GetSerializeSize(getvch(), nType, nVersion); |
344 | } |
345 | |
346 | template<typename Stream> |
347 | void Serialize(Stream& s, int nType=0, int nVersion=VERSION) const |
348 | { |
349 | ::Serialize(s, getvch(), nType, nVersion); |
350 | } |
351 | |
352 | template<typename Stream> |
353 | void Unserialize(Stream& s, int nType=0, int nVersion=VERSION) |
354 | { |
355 | std::vector<unsigned char> vch; |
356 | ::Unserialize(s, vch, nType, nVersion); |
357 | setvch(vch); |
358 | } |
359 | |
360 | |
361 | bool operator!() const |
362 | { |
363 | return BN_is_zero(this); |
364 | } |
365 | |
366 | CBigNum& operator+=(const CBigNum& b) |
367 | { |
368 | if (!BN_add(this, this, &b)) |
369 | throw bignum_error("CBigNum::operator+= : BN_add failed"); |
370 | return *this; |
371 | } |
372 | |
373 | CBigNum& operator-=(const CBigNum& b) |
374 | { |
375 | *this = *this - b; |
376 | return *this; |
377 | } |
378 | |
379 | CBigNum& operator*=(const CBigNum& b) |
380 | { |
381 | CAutoBN_CTX pctx; |
382 | if (!BN_mul(this, this, &b, pctx)) |
383 | throw bignum_error("CBigNum::operator*= : BN_mul failed"); |
384 | return *this; |
385 | } |
386 | |
387 | CBigNum& operator/=(const CBigNum& b) |
388 | { |
389 | *this = *this / b; |
390 | return *this; |
391 | } |
392 | |
393 | CBigNum& operator%=(const CBigNum& b) |
394 | { |
395 | *this = *this % b; |
396 | return *this; |
397 | } |
398 | |
399 | CBigNum& operator<<=(unsigned int shift) |
400 | { |
401 | if (!BN_lshift(this, this, shift)) |
402 | throw bignum_error("CBigNum:operator<<= : BN_lshift failed"); |
403 | return *this; |
404 | } |
405 | |
406 | CBigNum& operator>>=(unsigned int shift) |
407 | { |
408 | // Note: BN_rshift segfaults on 64-bit if 2^shift is greater than the number |
409 | // if built on ubuntu 9.04 or 9.10, probably depends on version of openssl |
410 | CBigNum a = 1; |
411 | a <<= shift; |
412 | if (BN_cmp(&a, this) > 0) |
413 | { |
414 | *this = 0; |
415 | return *this; |
416 | } |
417 | |
418 | if (!BN_rshift(this, this, shift)) |
419 | throw bignum_error("CBigNum:operator>>= : BN_rshift failed"); |
420 | return *this; |
421 | } |
422 | |
423 | |
424 | CBigNum& operator++() |
425 | { |
426 | // prefix operator |
427 | if (!BN_add(this, this, BN_value_one())) |
428 | throw bignum_error("CBigNum::operator++ : BN_add failed"); |
429 | return *this; |
430 | } |
431 | |
432 | const CBigNum operator++(int) |
433 | { |
434 | // postfix operator |
435 | const CBigNum ret = *this; |
436 | ++(*this); |
437 | return ret; |
438 | } |
439 | |
440 | CBigNum& operator--() |
441 | { |
442 | // prefix operator |
443 | CBigNum r; |
444 | if (!BN_sub(&r, this, BN_value_one())) |
445 | throw bignum_error("CBigNum::operator-- : BN_sub failed"); |
446 | *this = r; |
447 | return *this; |
448 | } |
449 | |
450 | const CBigNum operator--(int) |
451 | { |
452 | // postfix operator |
453 | const CBigNum ret = *this; |
454 | --(*this); |
455 | return ret; |
456 | } |
457 | |
458 | |
459 | friend inline const CBigNum operator-(const CBigNum& a, const CBigNum& b); |
460 | friend inline const CBigNum operator/(const CBigNum& a, const CBigNum& b); |
461 | friend inline const CBigNum operator%(const CBigNum& a, const CBigNum& b); |
462 | }; |
463 | |
464 | |
465 | |
466 | inline const CBigNum operator+(const CBigNum& a, const CBigNum& b) |
467 | { |
468 | CBigNum r; |
469 | if (!BN_add(&r, &a, &b)) |
470 | throw bignum_error("CBigNum::operator+ : BN_add failed"); |
471 | return r; |
472 | } |
473 | |
474 | inline const CBigNum operator-(const CBigNum& a, const CBigNum& b) |
475 | { |
476 | CBigNum r; |
477 | if (!BN_sub(&r, &a, &b)) |
478 | throw bignum_error("CBigNum::operator- : BN_sub failed"); |
479 | return r; |
480 | } |
481 | |
482 | inline const CBigNum operator-(const CBigNum& a) |
483 | { |
484 | CBigNum r(a); |
485 | BN_set_negative(&r, !BN_is_negative(&r)); |
486 | return r; |
487 | } |
488 | |
489 | inline const CBigNum operator*(const CBigNum& a, const CBigNum& b) |
490 | { |
491 | CAutoBN_CTX pctx; |
492 | CBigNum r; |
493 | if (!BN_mul(&r, &a, &b, pctx)) |
494 | throw bignum_error("CBigNum::operator* : BN_mul failed"); |
495 | return r; |
496 | } |
497 | |
498 | inline const CBigNum operator/(const CBigNum& a, const CBigNum& b) |
499 | { |
500 | CAutoBN_CTX pctx; |
501 | CBigNum r; |
502 | if (!BN_div(&r, NULL, &a, &b, pctx)) |
503 | throw bignum_error("CBigNum::operator/ : BN_div failed"); |
504 | return r; |
505 | } |
506 | |
507 | inline const CBigNum operator%(const CBigNum& a, const CBigNum& b) |
508 | { |
509 | CAutoBN_CTX pctx; |
510 | CBigNum r; |
511 | if (!BN_mod(&r, &a, &b, pctx)) |
512 | throw bignum_error("CBigNum::operator% : BN_div failed"); |
513 | return r; |
514 | } |
515 | |
516 | inline const CBigNum operator<<(const CBigNum& a, unsigned int shift) |
517 | { |
518 | CBigNum r; |
519 | if (!BN_lshift(&r, &a, shift)) |
520 | throw bignum_error("CBigNum:operator<< : BN_lshift failed"); |
521 | return r; |
522 | } |
523 | |
524 | inline const CBigNum operator>>(const CBigNum& a, unsigned int shift) |
525 | { |
526 | CBigNum r = a; |
527 | r >>= shift; |
528 | return r; |
529 | } |
530 | |
531 | inline bool operator==(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) == 0); } |
532 | inline bool operator!=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) != 0); } |
533 | inline bool operator<=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) <= 0); } |
534 | inline bool operator>=(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) >= 0); } |
535 | inline bool operator<(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) < 0); } |
536 | inline bool operator>(const CBigNum& a, const CBigNum& b) { return (BN_cmp(&a, &b) > 0); } |
537 | |
538 | #endif |