src/impl/num_gmp.h

   1 #ifndef _SECP256K1_NUM_REPR_IMPL_H_
   2 #define _SECP256K1_NUM_REPR_IMPL_H_
   3
   4 #include <assert.h>
   5 #include <string.h>
   6 #include <stdlib.h>
   7 #include <gmp.h>
   8
   9 #include "num.h"
  10
  11 #ifdef VERIFY
  12 void static secp256k1_num_sanity(const secp256k1_num_t *a) {
  13     assert(a->limbs == 1 || (a->limbs > 1 && a->data[a->limbs-1] != 0));
  14 }
  15 #else
  16 #define secp256k1_num_sanity(a) do { } while(0)
  17 #endif
  18
  19 void static secp256k1_num_init(secp256k1_num_t *r) {
  20     r->neg = 0;
  21     r->limbs = 1;
  22     r->data[0] = 0;
  23 }
  24
  25 void static secp256k1_num_free(secp256k1_num_t *r) {
  26 }
  27
  28 void static secp256k1_num_copy(secp256k1_num_t *r, const secp256k1_num_t *a) {
  29     *r = *a;
  30 }
  31
  32 int static secp256k1_num_bits(const secp256k1_num_t *a) {
  33     int ret=(a->limbs-1)*GMP_NUMB_BITS;
  34     mp_limb_t x=a->data[a->limbs-1];
  35     while (x) {
  36         x >>= 1;
  37         ret++;
  38     }
  39     return ret;
  40 }
  41
  42
  43 void static secp256k1_num_get_bin(unsigned char *r, unsigned int rlen, const secp256k1_num_t *a) {
  44     unsigned char tmp[65];
  45     int len = mpn_get_str(tmp, 256, (mp_limb_t*)a->data, a->limbs);
  46     assert(len <= rlen);
  47     memset(r, 0, rlen - len);
  48     memcpy(r + rlen - len, tmp, len);
  49 }
  50
  51 void static secp256k1_num_set_bin(secp256k1_num_t *r, const unsigned char *a, unsigned int alen) {
  52     assert(alen > 0);
  53     assert(alen <= 64);
  54     int len = mpn_set_str(r->data, a, alen, 256);
  55     assert(len <= NUM_LIMBS*2);
  56     r->limbs = len;
  57     r->neg = 0;
  58     while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
  59 }
  60
  61 void static secp256k1_num_set_int(secp256k1_num_t *r, int a) {
  62     r->limbs = 1;
  63     r->neg = (a < 0);
  64     r->data[0] = (a < 0) ? -a : a;
  65 }
  66
  67 void static secp256k1_num_mod(secp256k1_num_t *r, const secp256k1_num_t *m) {
  68     secp256k1_num_sanity(r);
  69     secp256k1_num_sanity(m);
  70
  71     if (r->limbs >= m->limbs) {
  72         mp_limb_t t[2*NUM_LIMBS];
  73         mpn_tdiv_qr(t, r->data, 0, r->data, r->limbs, m->data, m->limbs);
  74         r->limbs = m->limbs;
  75         while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
  76         r->neg ^= m->neg;
  77     }
  78 }
  79
  80 void static secp256k1_num_mod_inverse(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *m) {
  81     secp256k1_num_sanity(a);
  82     secp256k1_num_sanity(m);
  83
  84 #ifdef VERIFY
  85     secp256k1_num_t a2 = *a;
  86     secp256k1_num_t m2 = *m;
  87 #endif
  88
  89     // mpn_gcdext computes: (G,S) = gcdext(U,V), where
  90     // * G = gcd(U,V)
  91     // * G = U*S + V*T
  92     // * U has equal or more limbs than V, and V has no padding
  93     // If we set U to be (a padded version of) a, and V = m:
  94     //   G = a*S + m*T
  95     //   G = a*S mod m
  96     // Assuming G=1:
  97     //   S = 1/a mod m
  98     assert(m->limbs <= NUM_LIMBS);
  99     assert(m->data[m->limbs-1] != 0);
 100     mp_limb_t g[NUM_LIMBS+1];
 101     mp_limb_t u[NUM_LIMBS+1];
 102     mp_limb_t v[NUM_LIMBS+1];
 103     for (int i=0; i < m->limbs; i++) {
 104         u[i] = (i < a->limbs) ? a->data[i] : 0;
 105         v[i] = m->data[i];
 106     }
 107     mp_size_t sn = NUM_LIMBS+1;
 108     mp_size_t gn = mpn_gcdext(g, r->data, &sn, u, m->limbs, v, m->limbs);
 109     assert(gn == 1);
 110     assert(g[0] == 1);
 111     r->neg = a->neg ^ m->neg;
 112     if (sn < 0) {
 113         mpn_sub(r->data, m->data, m->limbs, r->data, -sn);
 114         r->limbs = m->limbs;
 115         while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
 116     } else {
 117         r->limbs = sn;
 118     }
 119
 120 #ifdef VERIFY
 121     secp256k1_num_t c;
 122     secp256k1_num_mod_mul(&c, &a2, r, m);
 123     assert(c.limbs == 1 && c.data[0] == 1);
 124 #endif
 125 }
 126
 127 int static secp256k1_num_is_zero(const secp256k1_num_t *a) {
 128     return (a->limbs == 1 && a->data[0] == 0);
 129 }
 130
 131 int static secp256k1_num_is_odd(const secp256k1_num_t *a) {
 132     return a->data[0] & 1;
 133 }
 134
 135 int static secp256k1_num_is_neg(const secp256k1_num_t *a) {
 136     return (a->limbs > 1 || a->data[0] != 0) && a->neg;
 137 }
 138
 139 int static secp256k1_num_cmp(const secp256k1_num_t *a, const secp256k1_num_t *b) {
 140     if (a->limbs > b->limbs) return 1;
 141     if (a->limbs < b->limbs) return -1;
 142     return mpn_cmp(a->data, b->data, a->limbs);
 143 }
 144
 145 void static secp256k1_num_add_abs(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
 146     mp_limb_t c = mpn_add(r->data, a->data, a->limbs, b->data, b->limbs);
 147     r->limbs = a->limbs;
 148     if (c != 0) {
 149         assert(r->limbs < 2*NUM_LIMBS);
 150         r->data[r->limbs++] = c;
 151     }
 152 }
 153
 154 void static secp256k1_num_sub_abs(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
 155     mp_limb_t c = mpn_sub(r->data, a->data, a->limbs, b->data, b->limbs);
 156     assert(c == 0);
 157     r->limbs = a->limbs;
 158     while (r->limbs > 1 && r->data[r->limbs-1]==0) r->limbs--;
 159 }
 160
 161 void static secp256k1_num_subadd(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b, int bneg) {
 162     if (!(b->neg ^ bneg ^ a->neg)) { // a and b have the same sign
 163         r->neg = a->neg;
 164         if (a->limbs >= b->limbs) {
 165             secp256k1_num_add_abs(r, a, b);
 166         } else {
 167             secp256k1_num_add_abs(r, b, a);
 168         }
 169     } else {
 170         if (secp256k1_num_cmp(a, b) > 0) {
 171             r->neg = a->neg;
 172             secp256k1_num_sub_abs(r, a, b);
 173         } else {
 174             r->neg = b->neg ^ bneg;
 175             secp256k1_num_sub_abs(r, b, a);
 176         }
 177     }
 178 }
 179
 180 void static secp256k1_num_add(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
 181     secp256k1_num_sanity(a);
 182     secp256k1_num_sanity(b);
 183
 184 #ifdef VERIFY
 185     secp256k1_num_t a2 = *a;
 186     secp256k1_num_t b2 = *b;
 187 #endif
 188
 189     secp256k1_num_subadd(r, a, b, 0);
 190
 191 #ifdef VERIFY
 192     secp256k1_num_t c = *r;
 193     secp256k1_num_subadd(&c, &c, &b2, 1);
 194     assert(secp256k1_num_cmp(&c, &a2) == 0);
 195 #endif
 196 }
 197
 198 void static secp256k1_num_sub(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
 199 #ifdef VERIFY
 200     secp256k1_num_t a2 = *a;
 201     secp256k1_num_t b2 = *b;
 202 #endif
 203     secp256k1_num_sanity(a);
 204     secp256k1_num_sanity(b);
 205
 206     secp256k1_num_subadd(r, a, b, 1);
 207
 208 #ifdef VERIFY
 209     secp256k1_num_t c;
 210     secp256k1_num_subadd(&c, r, &b2, 0);
 211     assert(secp256k1_num_cmp(&c, &a2) == 0);
 212 #endif
 213 }
 214
 215 void static secp256k1_num_mul(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
 216 #ifdef VERIFY
 217     secp256k1_num_t a2 = *a;
 218     secp256k1_num_t b2 = *b;
 219 #endif
 220
 221     secp256k1_num_sanity(a);
 222     secp256k1_num_sanity(b);
 223
 224     mp_limb_t tmp[2*NUM_LIMBS+1];
 225     assert(a->limbs + b->limbs <= 2*NUM_LIMBS+1);
 226     if ((a->limbs==1 && a->data[0]==0) || (b->limbs==1 && b->data[0]==0)) {
 227         r->limbs = 1;
 228         r->neg = 0;
 229         r->data[0] = 0;
 230         return;
 231     }
 232     if (a->limbs >= b->limbs)
 233         mpn_mul(tmp, a->data, a->limbs, b->data, b->limbs);
 234     else
 235         mpn_mul(tmp, b->data, b->limbs, a->data, a->limbs);
 236     r->limbs = a->limbs + b->limbs;
 237     if (r->limbs > 1 && tmp[r->limbs - 1]==0) r->limbs--;
 238     assert(r->limbs <= 2*NUM_LIMBS);
 239     mpn_copyi(r->data, tmp, r->limbs);
 240     r->neg = a->neg ^ b->neg;
 241
 242     secp256k1_num_sanity(&a2);
 243     secp256k1_num_sanity(&b2);
 244
 245 #ifdef VERIFY
 246     secp256k1_num_t c;
 247     secp256k1_num_div(&c, r, &b2);
 248     assert(secp256k1_num_cmp(&a2, &c) == 0);
 249     secp256k1_num_div(&c, r, &a2);
 250     assert(secp256k1_num_cmp(&b2, &c) == 0);
 251 #endif
 252 }
 253
 254 void static secp256k1_num_div(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b) {
 255     secp256k1_num_sanity(a);
 256     secp256k1_num_sanity(b);
 257     if (b->limbs > a->limbs) {
 258         r->limbs = 1;
 259         r->data[0] = 0;
 260         r->neg = 0;
 261         return;
 262     }
 263
 264     mp_limb_t quo[2*NUM_LIMBS+1];
 265     mp_limb_t rem[2*NUM_LIMBS+1];
 266     mpn_tdiv_qr(quo, rem, 0, a->data, a->limbs, b->data, b->limbs);
 267     mpn_copyi(r->data, quo, a->limbs - b->limbs + 1);
 268     r->limbs = a->limbs - b->limbs + 1;
 269     while (r->limbs > 1 && r->data[r->limbs - 1]==0) r->limbs--;
 270     r->neg = a->neg ^ b->neg;
 271 }
 272
 273 void static secp256k1_num_mod_mul(secp256k1_num_t *r, const secp256k1_num_t *a, const secp256k1_num_t *b, const secp256k1_num_t *m) {
 274     secp256k1_num_mul(r, a, b);
 275     secp256k1_num_mod(r, m);
 276 }
 277
 278
 279 int static secp256k1_num_shift(secp256k1_num_t *r, int bits) {
 280     assert(bits <= GMP_NUMB_BITS);
 281     mp_limb_t ret = mpn_rshift(r->data, r->data, r->limbs, bits);
 282     if (r->limbs>1 && r->data[r->limbs-1]==0) r->limbs--;
 283     ret >>= (GMP_NUMB_BITS - bits);
 284     return ret;
 285 }
 286
 287 int static secp256k1_num_get_bit(const secp256k1_num_t *a, int pos) {
 288     return (a->limbs*GMP_NUMB_BITS > pos) && ((a->data[pos/GMP_NUMB_BITS] >> (pos % GMP_NUMB_BITS)) & 1);
 289 }
 290
 291 void static secp256k1_num_inc(secp256k1_num_t *r) {
 292     mp_limb_t ret = mpn_add_1(r->data, r->data, r->limbs, (mp_limb_t)1);
 293     if (ret) {
 294         assert(r->limbs < 2*NUM_LIMBS);
 295         r->data[r->limbs++] = ret;
 296     }
 297 }
 298
 299 void static secp256k1_num_set_hex(secp256k1_num_t *r, const char *a, int alen) {
 300     static const unsigned char cvt[256] = {
 301         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 302         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 303         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 304         0, 1, 2, 3, 4, 5, 6,7,8,9,0,0,0,0,0,0,
 305         0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0,
 306         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 307         0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0,
 308         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 309         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 310         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 311         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 312         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 313         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 314         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 315         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
 316         0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0
 317     };
 318     char num[257] = {};
 319     for (int i=0; i<alen; i++) {
 320         num[i] = cvt[a[i]];
 321     }
 322     r->limbs = mpn_set_str(r->data, num, alen, 16);
 323     while (r->limbs > 1 && r->data[r->limbs-1] == 0) r->limbs--;
 324 }
 325
 326 void static secp256k1_num_get_hex(char *r, int rlen, const secp256k1_num_t *a) {
 327     static const unsigned char cvt[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
 328     unsigned char *tmp = malloc(257);
 329     mp_size_t len = mpn_get_str(tmp, 16, (mp_limb_t*)a->data, a->limbs);
 330     assert(len <= rlen);
 331     for (int i=0; i<len; i++) {
 332         assert(rlen-len+i >= 0);
 333         assert(rlen-len+i < rlen);
 334         assert(tmp[i] >= 0);
 335         assert(tmp[i] < 16);
 336         r[rlen-len+i] = cvt[tmp[i]];
 337     }
 338     for (int i=0; i<rlen-len; i++) {
 339         assert(i >= 0);
 340         assert(i < rlen);
 341         r[i] = cvt[0];
 342     }
 343     free(tmp);
 344 }
 345
 346 void static secp256k1_num_split(secp256k1_num_t *rl, secp256k1_num_t *rh, const secp256k1_num_t *a, int bits) {
 347     assert(bits > 0);
 348     rh->neg = a->neg;
 349     if (bits >= a->limbs * GMP_NUMB_BITS) {
 350         *rl = *a;
 351         rh->limbs = 1;
 352         rh->data[0] = 0;
 353         return;
 354     }
 355     rl->limbs = 0;
 356     rl->neg = a->neg;
 357     int left = bits;
 358     while (left >= GMP_NUMB_BITS) {
 359         rl->data[rl->limbs] = a->data[rl->limbs];
 360         rl->limbs++;
 361         left -= GMP_NUMB_BITS;
 362     }
 363     if (left == 0) {
 364         mpn_copyi(rh->data, a->data + rl->limbs, a->limbs - rl->limbs);
 365         rh->limbs = a->limbs - rl->limbs;
 366     } else {
 367         mpn_rshift(rh->data, a->data + rl->limbs, a->limbs - rl->limbs, left);
 368         rh->limbs = a->limbs - rl->limbs;
 369         while (rh->limbs>1 && rh->data[rh->limbs-1]==0) rh->limbs--;
 370     }
 371     if (left > 0) {
 372         rl->data[rl->limbs] = a->data[rl->limbs] & ((((mp_limb_t)1) << left) - 1);
 373         rl->limbs++;
 374     }
 375     while (rl->limbs>1 && rl->data[rl->limbs-1]==0) rl->limbs--;
 376 }
 377
 378 void static secp256k1_num_negate(secp256k1_num_t *r) {
 379     r->neg ^= 1;
 380 }
 381
 382 #endif