Line data Source code
1 : // Copyright (c) 2009-2010 Satoshi Nakamoto
2 : // Copyright (c) 2009-2012 The Bitcoin developers
3 : // Copyright (c) 2017-2021 The PIVX Core developers
4 : // Distributed under the MIT/X11 software license, see the accompanying
5 : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
6 :
7 : #include "bignum.h"
8 :
9 : /** C++ wrapper for BIGNUM (Gmp bignum) */
10 3640811 : CBigNum::CBigNum()
11 : {
12 3640811 : mpz_init(bn);
13 3640811 : }
14 :
15 2552 : CBigNum::CBigNum(const CBigNum& b)
16 : {
17 2552 : mpz_init(bn);
18 2552 : mpz_set(bn, b.bn);
19 2552 : }
20 :
21 544330 : CBigNum& CBigNum::operator=(const CBigNum& b)
22 : {
23 544330 : mpz_set(bn, b.bn);
24 544330 : return (*this);
25 : }
26 :
27 10426280 : CBigNum::~CBigNum()
28 : {
29 5213140 : mpz_clear(bn);
30 5213140 : }
31 :
32 : //CBigNum(char n) is not portable. Use 'signed char' or 'unsigned char'.
33 0 : CBigNum::CBigNum(signed char n) { mpz_init(bn); if (n >= 0) mpz_set_ui(bn, n); else mpz_set_si(bn, n); }
34 0 : CBigNum::CBigNum(short n) { mpz_init(bn); if (n >= 0) mpz_set_ui(bn, n); else mpz_set_si(bn, n); }
35 1089022 : CBigNum::CBigNum(int n) { mpz_init(bn); if (n >= 0) mpz_set_ui(bn, n); else mpz_set_si(bn, n); }
36 13338 : CBigNum::CBigNum(long n) { mpz_init(bn); if (n >= 0) mpz_set_ui(bn, n); else mpz_set_si(bn, n); }
37 0 : CBigNum::CBigNum(long long n) { mpz_init(bn); mpz_set_si(bn, n); }
38 0 : CBigNum::CBigNum(unsigned char n) { mpz_init(bn); mpz_set_ui(bn, n); }
39 0 : CBigNum::CBigNum(unsigned short n) { mpz_init(bn); mpz_set_ui(bn, n); }
40 116696 : CBigNum::CBigNum(unsigned int n) { mpz_init(bn); mpz_set_ui(bn, n); }
41 0 : CBigNum::CBigNum(unsigned long n) { mpz_init(bn); mpz_set_ui(bn, n); }
42 :
43 350088 : CBigNum::CBigNum(uint256 n) { mpz_init(bn); setuint256(n); }
44 :
45 631 : CBigNum::CBigNum(const std::vector<unsigned char>& vch)
46 : {
47 631 : mpz_init(bn);
48 631 : setvch(vch);
49 631 : }
50 :
51 : /** PRNGs use GMP for consistency with seed initialization **/
52 :
53 : /** Generates a cryptographically secure random number between zero and range-1 (inclusive)
54 : * i.e. 0 <= returned number < range
55 : * @param range The upper bound on the number.
56 : * @return
57 : */
58 1 : CBigNum CBigNum::randBignum(const CBigNum& range)
59 : {
60 1 : if (range < 2)
61 0 : return 0;
62 :
63 1 : size_t size = (mpz_sizeinbase (range.bn, 2) + CHAR_BIT-1) / CHAR_BIT;
64 2 : std::vector<unsigned char> buf(size);
65 :
66 1 : GetStrongRandBytes(buf.data(), size);
67 :
68 2 : CBigNum ret(buf);
69 1 : if (ret < 0)
70 1 : mpz_neg(ret.bn, ret.bn);
71 1 : return (ret % range);
72 : }
73 :
74 : /**Returns the size in bits of the underlying bignum.
75 : *
76 : * @return the size
77 : */
78 102254 : int CBigNum::bitSize() const
79 : {
80 102254 : return mpz_sizeinbase(bn, 2);
81 : }
82 :
83 0 : void CBigNum::setulong(unsigned long n)
84 : {
85 0 : mpz_set_ui(bn, n);
86 0 : }
87 :
88 17559 : unsigned long CBigNum::getulong() const
89 : {
90 17559 : return mpz_get_ui(bn);
91 : }
92 :
93 0 : unsigned int CBigNum::getuint() const
94 : {
95 0 : return mpz_get_ui(bn);
96 : }
97 :
98 14949 : int CBigNum::getint() const
99 : {
100 14949 : unsigned long n = getulong();
101 14949 : if (mpz_cmp(bn, BN_ZERO.bn) >= 0) {
102 9416 : return (n > (unsigned long)std::numeric_limits<int>::max() ? std::numeric_limits<int>::max() : n);
103 : } else {
104 5533 : return (n > (unsigned long)std::numeric_limits<int>::max() ? std::numeric_limits<int>::min() : -(int)n);
105 : }
106 : }
107 :
108 350088 : void CBigNum::setuint256(uint256 n)
109 : {
110 350088 : mpz_import(bn, n.size(), -1, 1, 0, 0, (unsigned char*)&n);
111 350088 : }
112 :
113 0 : arith_uint256 CBigNum::getuint256() const
114 : {
115 0 : if(bitSize() > 256) {
116 0 : throw std::range_error("cannot convert to uint256, bignum longer than 256 bits");
117 : }
118 0 : uint256 n = UINT256_ZERO;
119 0 : mpz_export((unsigned char*)&n, nullptr, -1, 1, 0, 0, bn);
120 0 : return UintToArith256(n);
121 : }
122 :
123 631 : void CBigNum::setvch(const std::vector<unsigned char>& vch)
124 : {
125 631 : std::vector<unsigned char> vch2 = vch;
126 631 : unsigned char sign = 0;
127 631 : if (vch2.size() > 0) {
128 603 : sign = vch2[vch2.size()-1] & 0x80;
129 603 : vch2[vch2.size()-1] = vch2[vch2.size()-1] & 0x7f;
130 603 : mpz_import(bn, vch2.size(), -1, 1, 0, 0, vch2.data());
131 603 : if (sign)
132 631 : mpz_neg(bn, bn);
133 : }
134 : else {
135 28 : mpz_set_si(bn, 0);
136 : }
137 631 : }
138 :
139 14756 : std::vector<unsigned char> CBigNum::getvch() const
140 : {
141 14756 : if (mpz_cmp(bn, BN_ZERO.bn) == 0) {
142 2432 : return std::vector<unsigned char>(0);
143 : }
144 12324 : size_t size = (mpz_sizeinbase (bn, 2) + CHAR_BIT-1) / CHAR_BIT;
145 12324 : if (size <= 0)
146 0 : return std::vector<unsigned char>();
147 27080 : std::vector<unsigned char> v(size + 1);
148 12324 : mpz_export(v.data(), &size, -1, 1, 0, 0, bn);
149 12324 : if (v[v.size()-2] & 0x80) {
150 4518 : if (mpz_sgn(bn)<0) {
151 1886 : v[v.size()-1] = 0x80;
152 : } else {
153 2632 : v[v.size()-1] = 0x00;
154 : }
155 : } else {
156 7806 : v.pop_back();
157 7806 : if (mpz_sgn(bn)<0) {
158 3358 : v[v.size()-1] |= 0x80;
159 : }
160 : }
161 12324 : return v;
162 : }
163 :
164 58 : void CBigNum::SetDec(const std::string& str)
165 : {
166 58 : const char* psz = str.c_str();
167 58 : mpz_set_str(bn, psz, 10);
168 58 : }
169 :
170 58 : bool CBigNum::SetHexBool(const std::string& str)
171 : {
172 58 : const char* psz = str.c_str();
173 58 : int ret = 1 + mpz_set_str(bn, psz, 16);
174 58 : return (bool) ret;
175 : }
176 :
177 0 : std::string CBigNum::ToString(int nBase) const
178 : {
179 0 : char* c_str = mpz_get_str(nullptr, nBase, bn);
180 0 : std::string str(c_str);
181 : // Free c_str with the right free function:
182 0 : void (*freefunc)(void *, size_t);
183 0 : mp_get_memory_functions (nullptr, nullptr, &freefunc);
184 0 : freefunc(c_str, strlen(c_str) + 1);
185 :
186 0 : return str;
187 : }
188 :
189 : /**
190 : * exponentiation this^e
191 : * @param e the exponent
192 : * @return
193 : */
194 796572 : CBigNum CBigNum::pow(const CBigNum& e) const
195 : {
196 796572 : CBigNum ret;
197 796572 : long unsigned int ei = mpz_get_ui (e.bn);
198 796572 : mpz_pow_ui(ret.bn, bn, ei);
199 796572 : return ret;
200 : }
201 :
202 : /**
203 : * modular multiplication: (this * b) mod m
204 : * @param b operand
205 : * @param m modulus
206 : */
207 0 : CBigNum CBigNum::mul_mod(const CBigNum& b, const CBigNum& m) const
208 : {
209 0 : CBigNum ret;
210 0 : mpz_mul (ret.bn, bn, b.bn);
211 0 : mpz_mod (ret.bn, ret.bn, m.bn);
212 0 : return ret;
213 : }
214 :
215 : /**
216 : * modular exponentiation: this^e mod n
217 : * @param e exponent
218 : * @param m modulus
219 : */
220 226026 : CBigNum CBigNum::pow_mod(const CBigNum& e, const CBigNum& m) const
221 : {
222 226026 : CBigNum ret;
223 226026 : if (e > BN_ZERO && mpz_odd_p(m.bn))
224 226026 : mpz_powm_sec (ret.bn, bn, e.bn, m.bn);
225 : else
226 0 : mpz_powm (ret.bn, bn, e.bn, m.bn);
227 226026 : return ret;
228 : }
229 :
230 : /**
231 : * Calculates the inverse of this element mod m.
232 : * i.e. i such this*i = 1 mod m
233 : * @param m the modu
234 : * @return the inverse
235 : */
236 0 : CBigNum CBigNum::inverse(const CBigNum& m) const
237 : {
238 0 : CBigNum ret;
239 0 : mpz_invert(ret.bn, bn, m.bn);
240 0 : return ret;
241 : }
242 :
243 : /**
244 : * Calculates the greatest common divisor (GCD) of two numbers.
245 : * @param m the second element
246 : * @return the GCD
247 : */
248 145580 : CBigNum CBigNum::gcd( const CBigNum& b) const
249 : {
250 145580 : CBigNum ret;
251 145580 : mpz_gcd(ret.bn, bn, b.bn);
252 145580 : return ret;
253 : }
254 :
255 : /**
256 : * Miller-Rabin primality test on this element
257 : * @param checks: optional, the number of Miller-Rabin tests to run
258 : * default causes error rate of 2^-80.
259 : * @return true if prime
260 : */
261 15370 : bool CBigNum::isPrime(const int checks) const
262 : {
263 15370 : int ret = mpz_probab_prime_p(bn, checks);
264 15370 : return ret;
265 : }
266 :
267 225562 : bool CBigNum::isOne() const
268 : {
269 225562 : return mpz_cmp(bn, BN_ONE.bn) == 0;
270 : }
271 :
272 13436 : bool CBigNum::operator!() const
273 : {
274 13436 : return mpz_cmp(bn, BN_ZERO.bn) == 0;
275 : }
276 :
277 349392 : CBigNum& CBigNum::operator+=(const CBigNum& b)
278 : {
279 349392 : mpz_add(bn, bn, b.bn);
280 349392 : return *this;
281 : }
282 :
283 0 : CBigNum& CBigNum::operator-=(const CBigNum& b)
284 : {
285 0 : mpz_sub(bn, bn, b.bn);
286 0 : return *this;
287 : }
288 :
289 0 : CBigNum& CBigNum::operator*=(const CBigNum& b)
290 : {
291 0 : mpz_mul(bn, bn, b.bn);
292 0 : return *this;
293 : }
294 :
295 0 : CBigNum& CBigNum::operator<<=(unsigned int shift)
296 : {
297 0 : mpz_mul_2exp(bn, bn, shift);
298 0 : return *this;
299 : }
300 :
301 0 : CBigNum& CBigNum::operator>>=(unsigned int shift)
302 : {
303 0 : mpz_div_2exp(bn, bn, shift);
304 0 : return *this;
305 : }
306 :
307 0 : CBigNum& CBigNum::operator++()
308 : {
309 : // prefix operator
310 0 : mpz_add(bn, bn, BN_ONE.bn);
311 0 : return *this;
312 : }
313 :
314 0 : CBigNum& CBigNum::operator--()
315 : {
316 : // prefix operator
317 0 : mpz_sub(bn, bn, BN_ONE.bn);
318 0 : return *this;
319 : }
320 :
321 0 : std::string CBigNum::GetHex() const
322 : {
323 0 : return ToString(16);
324 : }
325 :
326 0 : std::string CBigNum::GetDec() const
327 : {
328 0 : return ToString(10);
329 : }
330 :
331 695014 : CBigNum CBigNum::pow(const int e) const
332 : {
333 695014 : return this->pow(CBigNum(e));
334 : }
335 :
336 58 : void CBigNum::SetHex(const std::string& str)
337 : {
338 58 : SetHexBool(str);
339 58 : }
340 :
341 0 : CBigNum& CBigNum::operator/=(const CBigNum& b)
342 : {
343 0 : *this = *this / b;
344 0 : return *this;
345 : }
346 :
347 0 : CBigNum& CBigNum::operator%=(const CBigNum& b)
348 : {
349 0 : *this = *this % b;
350 0 : return *this;
351 : }
352 :
353 0 : const CBigNum CBigNum::operator++(int)
354 : {
355 : // postfix operator
356 0 : const CBigNum ret = *this;
357 0 : ++(*this);
358 0 : return ret;
359 : }
360 :
361 0 : const CBigNum CBigNum::operator--(int)
362 : {
363 : // postfix operator
364 0 : const CBigNum ret = *this;
365 0 : --(*this);
366 0 : return ret;
367 : }
|
