Bitcoin Core  0.20.99
P2P Digital Currency
num_gmp_impl.h
Go to the documentation of this file.
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) {
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) {
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 
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;
110 
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;
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) {
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) {
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];
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 
285  r->neg ^= 1;
286 }
287 
288 #endif /* SECP256K1_NUM_REPR_IMPL_H */
#define VERIFY_CHECK(cond)
Definition: util.h:68
static int secp256k1_num_jacobi(const secp256k1_num *a, const secp256k1_num *b)
Definition: num_gmp_impl.h:147
static int secp256k1_num_cmp(const secp256k1_num *a, const secp256k1_num *b)
Definition: num_gmp_impl.h:181
static void secp256k1_num_mul(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b)
Definition: num_gmp_impl.h:235
static void secp256k1_num_subadd(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b, int bneg)
Definition: num_gmp_impl.h:204
static void secp256k1_num_copy(secp256k1_num *r, const secp256k1_num *a)
Definition: num_gmp_impl.h:25
static void secp256k1_num_sub(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b)
Definition: num_gmp_impl.h:229
#define NUM_LIMBS
Definition: num_gmp.h:12
mp_limb_t data[2 *NUM_LIMBS]
Definition: num_gmp.h:15
static void secp256k1_num_add_abs(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b)
Definition: num_gmp_impl.h:62
static int secp256k1_num_is_one(const secp256k1_num *a)
Definition: num_gmp_impl.h:169
static void secp256k1_num_sub_abs(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b)
Definition: num_gmp_impl.h:71
static void secp256k1_num_shift(secp256k1_num *r, int bits)
Definition: num_gmp_impl.h:262
static void secp256k1_num_add(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *b)
Definition: num_gmp_impl.h:223
#define secp256k1_num_sanity(a)
Definition: num_gmp_impl.h:22
static int secp256k1_num_is_zero(const secp256k1_num *a)
Definition: num_gmp_impl.h:173
static void secp256k1_num_negate(secp256k1_num *r)
Definition: num_gmp_impl.h:284
static void secp256k1_num_mod_inverse(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *m)
Definition: num_gmp_impl.h:101
static void secp256k1_num_set_bin(secp256k1_num *r, const unsigned char *a, unsigned int alen)
Definition: num_gmp_impl.h:45
static void secp256k1_num_get_bin(unsigned char *r, unsigned int rlen, const secp256k1_num *a)
Definition: num_gmp_impl.h:29
static void secp256k1_num_mod(secp256k1_num *r, const secp256k1_num *m)
Definition: num_gmp_impl.h:81
void * memcpy(void *a, const void *b, size_t c)
static int secp256k1_num_eq(const secp256k1_num *a, const secp256k1_num *b)
Definition: num_gmp_impl.h:191
static int secp256k1_num_is_neg(const secp256k1_num *a)
Definition: num_gmp_impl.h:177