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