?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Squashed 'src/secp256k1/' changes from 84973d393..0b7024185
[bitcoinplatinum.git] / src / num_gmp_impl.h
blob0ae2a8ba0ecb7b5b61aca0f94676dd7cbf86c437
1 /**********************************************************************
2 * Copyright (c) 2013, 2014 Pieter Wuille *
3 * Distributed under the MIT software license, see the accompanying *
4 * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
5 **********************************************************************/
6
7 #ifndef SECP256K1_NUM_REPR_IMPL_H
8 #define SECP256K1_NUM_REPR_IMPL_H
9
10 #include <string.h>
11 #include <stdlib.h>
12 #include <gmp.h>
13
14 #include "util.h"
15 #include "num.h"
16
17 #ifdef VERIFY
18 static void secp256k1_num_sanity(const secp256k1_num *a) {
19 VERIFY_CHECK(a->limbs == 1 || (a->limbs > 1 && a->data[a->limbs-1] != 0));
20 }
21 #else
22 #define secp256k1_num_sanity(a) do { } while(0)
23 #endif
24
25 static void secp256k1_num_copy(secp256k1_num *r, const secp256k1_num *a) {
26 *r = *a;
27 }
28
29 static void secp256k1_num_get_bin(unsigned char *r, unsigned int rlen, const secp256k1_num *a) {
30 unsigned char tmp[65];
31 int len = 0;
32 int shift = 0;
33 if (a->limbs>1 || a->data[0] != 0) {
34 len = mpn_get_str(tmp, 256, (mp_limb_t*)a->data, a->limbs);
35 }
36 while (shift < len && tmp[shift] == 0) shift++;
37 VERIFY_CHECK(len-shift <= (int)rlen);
38 memset(r, 0, rlen - len + shift);
39 if (len > shift) {
40 memcpy(r + rlen - len + shift, tmp + shift, len - shift);
41 }
42 memset(tmp, 0, sizeof(tmp));
43 }
44
45 static void secp256k1_num_set_bin(secp256k1_num *r, const unsigned char *a, unsigned int alen) {
46 int len;
47 VERIFY_CHECK(alen > 0);
48 VERIFY_CHECK(alen <= 64);
49 len = mpn_set_str(r->data, a, alen, 256);
50 if (len == 0) {
51 r->data[0] = 0;
52 len = 1;
53 }
54 VERIFY_CHECK(len <= NUM_LIMBS*2);
55 r->limbs = len;
56 r->neg = 0;
57 while (r->limbs > 1 && r->data[r->limbs-1]==0) {
58 r->limbs--;
59 }
60 }
61
62 static void secp256k1_num_add_abs(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b) {
63 mp_limb_t c = mpn_add(r->data, a->data, a->limbs, b->data, b->limbs);
64 r->limbs = a->limbs;
65 if (c != 0) {
66 VERIFY_CHECK(r->limbs < 2*NUM_LIMBS);
67 r->data[r->limbs++] = c;
68 }
69 }
70
71 static void secp256k1_num_sub_abs(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b) {
72 mp_limb_t c = mpn_sub(r->data, a->data, a->limbs, b->data, b->limbs);
73 (void)c;
74 VERIFY_CHECK(c == 0);
75 r->limbs = a->limbs;
76 while (r->limbs > 1 && r->data[r->limbs-1]==0) {
77 r->limbs--;
78 }
79 }
80
81 static void secp256k1_num_mod(secp256k1_num *r, const secp256k1_num *m) {
82 secp256k1_num_sanity(r);
83 secp256k1_num_sanity(m);
84
85 if (r->limbs >= m->limbs) {
86 mp_limb_t t[2*NUM_LIMBS];
87 mpn_tdiv_qr(t, r->data, 0, r->data, r->limbs, m->data, m->limbs);
88 memset(t, 0, sizeof(t));
89 r->limbs = m->limbs;
90 while (r->limbs > 1 && r->data[r->limbs-1]==0) {
91 r->limbs--;
92 }
93 }
94
95 if (r->neg && (r->limbs > 1 || r->data[0] != 0)) {
96 secp256k1_num_sub_abs(r, m, r);
97 r->neg = 0;
98 }
99 }
100
101 static void secp256k1_num_mod_inverse(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *m) {
102 int i;
103 mp_limb_t g[NUM_LIMBS+1];
104 mp_limb_t u[NUM_LIMBS+1];
105 mp_limb_t v[NUM_LIMBS+1];
106 mp_size_t sn;
107 mp_size_t gn;
108 secp256k1_num_sanity(a);
109 secp256k1_num_sanity(m);
110
111 /** mpn_gcdext computes: (G,S) = gcdext(U,V), where
112 * * G = gcd(U,V)
113 * * G = U*S + V*T
114 * * U has equal or more limbs than V, and V has no padding
115 * If we set U to be (a padded version of) a, and V = m:
116 * G = a*S + m*T
117 * G = a*S mod m
118 * Assuming G=1:
119 * S = 1/a mod m
120 */
121 VERIFY_CHECK(m->limbs <= NUM_LIMBS);
122 VERIFY_CHECK(m->data[m->limbs-1] != 0);
123 for (i = 0; i < m->limbs; i++) {
124 u[i] = (i < a->limbs) ? a->data[i] : 0;
125 v[i] = m->data[i];
126 }
127 sn = NUM_LIMBS+1;
128 gn = mpn_gcdext(g, r->data, &sn, u, m->limbs, v, m->limbs);
129 (void)gn;
130 VERIFY_CHECK(gn == 1);
131 VERIFY_CHECK(g[0] == 1);
132 r->neg = a->neg ^ m->neg;
133 if (sn < 0) {
134 mpn_sub(r->data, m->data, m->limbs, r->data, -sn);
135 r->limbs = m->limbs;
136 while (r->limbs > 1 && r->data[r->limbs-1]==0) {
137 r->limbs--;
138 }
139 } else {
140 r->limbs = sn;
141 }
142 memset(g, 0, sizeof(g));
143 memset(u, 0, sizeof(u));
144 memset(v, 0, sizeof(v));
145 }
146
147 static int secp256k1_num_jacobi(const secp256k1_num *a, const secp256k1_num *b) {
148 int ret;
149 mpz_t ga, gb;
150 secp256k1_num_sanity(a);
151 secp256k1_num_sanity(b);
152 VERIFY_CHECK(!b->neg && (b->limbs > 0) && (b->data[0] & 1));
153
154 mpz_inits(ga, gb, NULL);
155
156 mpz_import(gb, b->limbs, -1, sizeof(mp_limb_t), 0, 0, b->data);
157 mpz_import(ga, a->limbs, -1, sizeof(mp_limb_t), 0, 0, a->data);
158 if (a->neg) {
159 mpz_neg(ga, ga);
160 }
161
162 ret = mpz_jacobi(ga, gb);
163
164 mpz_clears(ga, gb, NULL);
165
166 return ret;
167 }
168
169 static int secp256k1_num_is_one(const secp256k1_num *a) {
170 return (a->limbs == 1 && a->data[0] == 1);
171 }
172
173 static int secp256k1_num_is_zero(const secp256k1_num *a) {
174 return (a->limbs == 1 && a->data[0] == 0);
175 }
176
177 static int secp256k1_num_is_neg(const secp256k1_num *a) {
178 return (a->limbs > 1 || a->data[0] != 0) && a->neg;
179 }
180
181 static int secp256k1_num_cmp(const secp256k1_num *a, const secp256k1_num *b) {
182 if (a->limbs > b->limbs) {
183 return 1;
184 }
185 if (a->limbs < b->limbs) {
186 return -1;
187 }
188 return mpn_cmp(a->data, b->data, a->limbs);
189 }
190
191 static int secp256k1_num_eq(const secp256k1_num *a, const secp256k1_num *b) {
192 if (a->limbs > b->limbs) {
193 return 0;
194 }
195 if (a->limbs < b->limbs) {
196 return 0;
197 }
198 if ((a->neg && !secp256k1_num_is_zero(a)) != (b->neg && !secp256k1_num_is_zero(b))) {
199 return 0;
200 }
201 return mpn_cmp(a->data, b->data, a->limbs) == 0;
202 }
203
204 static void secp256k1_num_subadd(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b, int bneg) {
205 if (!(b->neg ^ bneg ^ a->neg)) { /* a and b have the same sign */
206 r->neg = a->neg;
207 if (a->limbs >= b->limbs) {
208 secp256k1_num_add_abs(r, a, b);
209 } else {
210 secp256k1_num_add_abs(r, b, a);
211 }
212 } else {
213 if (secp256k1_num_cmp(a, b) > 0) {
214 r->neg = a->neg;
215 secp256k1_num_sub_abs(r, a, b);
216 } else {
217 r->neg = b->neg ^ bneg;
218 secp256k1_num_sub_abs(r, b, a);
219 }
220 }
221 }
222
223 static void secp256k1_num_add(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b) {
224 secp256k1_num_sanity(a);
225 secp256k1_num_sanity(b);
226 secp256k1_num_subadd(r, a, b, 0);
227 }
228
229 static void secp256k1_num_sub(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b) {
230 secp256k1_num_sanity(a);
231 secp256k1_num_sanity(b);
232 secp256k1_num_subadd(r, a, b, 1);
233 }
234
235 static void secp256k1_num_mul(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b) {
236 mp_limb_t tmp[2*NUM_LIMBS+1];
237 secp256k1_num_sanity(a);
238 secp256k1_num_sanity(b);
239
240 VERIFY_CHECK(a->limbs + b->limbs <= 2*NUM_LIMBS+1);
241 if ((a->limbs==1 && a->data[0]==0) || (b->limbs==1 && b->data[0]==0)) {
242 r->limbs = 1;
243 r->neg = 0;
244 r->data[0] = 0;
245 return;
246 }
247 if (a->limbs >= b->limbs) {
248 mpn_mul(tmp, a->data, a->limbs, b->data, b->limbs);
249 } else {
250 mpn_mul(tmp, b->data, b->limbs, a->data, a->limbs);
251 }
252 r->limbs = a->limbs + b->limbs;
253 if (r->limbs > 1 && tmp[r->limbs - 1]==0) {
254 r->limbs--;
255 }
256 VERIFY_CHECK(r->limbs <= 2*NUM_LIMBS);
257 mpn_copyi(r->data, tmp, r->limbs);
258 r->neg = a->neg ^ b->neg;
259 memset(tmp, 0, sizeof(tmp));
260 }
261
262 static void secp256k1_num_shift(secp256k1_num *r, int bits) {
263 if (bits % GMP_NUMB_BITS) {
264 /* Shift within limbs. */
265 mpn_rshift(r->data, r->data, r->limbs, bits % GMP_NUMB_BITS);
266 }
267 if (bits >= GMP_NUMB_BITS) {
268 int i;
269 /* Shift full limbs. */
270 for (i = 0; i < r->limbs; i++) {
271 int index = i + (bits / GMP_NUMB_BITS);
272 if (index < r->limbs && index < 2*NUM_LIMBS) {
273 r->data[i] = r->data[index];
274 } else {
275 r->data[i] = 0;
276 }
277 }
278 }
279 while (r->limbs>1 && r->data[r->limbs-1]==0) {
280 r->limbs--;
281 }
282 }
283
284 static void secp256k1_num_negate(secp256k1_num *r) {
285 r->neg ^= 1;
286 }
287
288 #endif /* SECP256K1_NUM_REPR_IMPL_H */