7 #ifndef SECP256K1_MODINV64_IMPL_H
8 #define SECP256K1_MODINV64_IMPL_H
24 static int64_t secp256k1_modinv64_abs(int64_t v) {
34 const int64_t M62 = (int64_t)(UINT64_MAX >> 2);
37 for (i = 0; i < 4; ++i) {
38 if (i < alen) c += (int128_t)a->
v[i] * factor;
39 r->
v[i] = (int64_t)c & M62; c >>= 62;
41 if (4 < alen) c += (int128_t)a->
v[4] * factor;
50 secp256k1_modinv64_mul_62(&am, a, alen, 1);
51 secp256k1_modinv64_mul_62(&bm, b, 5, factor);
52 for (i = 0; i < 4; ++i) {
57 for (i = 4; i >= 0; --i) {
58 if (am.
v[i] < bm.
v[i])
return -1;
59 if (am.
v[i] > bm.
v[i])
return 1;
70 const int64_t M62 = (int64_t)(UINT64_MAX >> 2);
71 int64_t r0 = r->
v[0], r1 = r->
v[1], r2 = r->
v[2], r3 = r->
v[3], r4 = r->
v[4];
72 int64_t cond_add, cond_negate;
77 for (i = 0; i < 5; ++i) {
91 r0 += modinfo->
modulus.
v[0] & cond_add;
92 r1 += modinfo->
modulus.
v[1] & cond_add;
93 r2 += modinfo->
modulus.
v[2] & cond_add;
94 r3 += modinfo->
modulus.
v[3] & cond_add;
95 r4 += modinfo->
modulus.
v[4] & cond_add;
96 cond_negate = sign >> 63;
97 r0 = (r0 ^ cond_negate) - cond_negate;
98 r1 = (r1 ^ cond_negate) - cond_negate;
99 r2 = (r2 ^ cond_negate) - cond_negate;
100 r3 = (r3 ^ cond_negate) - cond_negate;
101 r4 = (r4 ^ cond_negate) - cond_negate;
103 r1 += r0 >> 62; r0 &= M62;
104 r2 += r1 >> 62; r1 &= M62;
105 r3 += r2 >> 62; r2 &= M62;
106 r4 += r3 >> 62; r3 &= M62;
111 r0 += modinfo->
modulus.
v[0] & cond_add;
112 r1 += modinfo->
modulus.
v[1] & cond_add;
113 r2 += modinfo->
modulus.
v[2] & cond_add;
114 r3 += modinfo->
modulus.
v[3] & cond_add;
115 r4 += modinfo->
modulus.
v[4] & cond_add;
117 r1 += r0 >> 62; r0 &= M62;
118 r2 += r1 >> 62; r1 &= M62;
119 r3 += r2 >> 62; r2 &= M62;
120 r4 += r3 >> 62; r3 &= M62;
167 uint64_t u = 8, v = 0, q = 0, r = 8;
168 uint64_t c1, c2, f = f0,
g = g0, x, y, z;
171 for (i = 3; i < 62; ++i) {
189 zeta = (zeta ^ c1) - 1;
212 VERIFY_CHECK((int128_t)
t->u *
t->r - (int128_t)
t->v *
t->q == ((int128_t)1) << 65);
228 uint64_t u = 1, v = 0, q = 0, r = 1;
229 uint64_t f = f0,
g = g0,
m;
231 int i = 62, limit, zeros;
254 tmp = f; f =
g;
g = -tmp;
255 tmp = u; u = q; q = -tmp;
256 tmp = v; v = r; r = -tmp;
260 limit = ((int)eta + 1) > i ? i : ((int)eta + 1);
263 m = (UINT64_MAX >> (64 - limit)) & 63U;
266 w = (f *
g * (f * f - 2)) &
m;
270 limit = ((int)eta + 1) > i ? i : ((int)eta + 1);
273 m = (UINT64_MAX >> (64 - limit)) & 15U;
276 w = f + (((f + 1) & 4) << 1);
293 VERIFY_CHECK((int128_t)
t->u *
t->r - (int128_t)
t->v *
t->q == ((int128_t)1) << 62);
305 const int64_t M62 = (int64_t)(UINT64_MAX >> 2);
306 const int64_t d0 = d->
v[0], d1 = d->
v[1], d2 = d->
v[2], d3 = d->
v[3], d4 = d->
v[4];
307 const int64_t e0 = e->
v[0], e1 = e->
v[1], e2 = e->
v[2], e3 = e->
v[3], e4 = e->
v[4];
308 const int64_t u =
t->u, v =
t->v, q =
t->q, r =
t->r;
309 int64_t md, me, sd, se;
316 VERIFY_CHECK((secp256k1_modinv64_abs(u) + secp256k1_modinv64_abs(v)) >= 0);
317 VERIFY_CHECK((secp256k1_modinv64_abs(q) + secp256k1_modinv64_abs(r)) >= 0);
318 VERIFY_CHECK((secp256k1_modinv64_abs(u) + secp256k1_modinv64_abs(v)) <= M62 + 1);
319 VERIFY_CHECK((secp256k1_modinv64_abs(q) + secp256k1_modinv64_abs(r)) <= M62 + 1);
324 md = (u & sd) + (v & se);
325 me = (q & sd) + (r & se);
327 cd = (int128_t)u * d0 + (int128_t)v * e0;
328 ce = (int128_t)q * d0 + (int128_t)r * e0;
333 cd += (int128_t)modinfo->
modulus.
v[0] * md;
334 ce += (int128_t)modinfo->
modulus.
v[0] * me;
339 cd += (int128_t)u * d1 + (int128_t)v * e1;
340 ce += (int128_t)q * d1 + (int128_t)r * e1;
342 cd += (int128_t)modinfo->
modulus.
v[1] * md;
343 ce += (int128_t)modinfo->
modulus.
v[1] * me;
345 d->
v[0] = (int64_t)cd & M62; cd >>= 62;
346 e->
v[0] = (int64_t)ce & M62; ce >>= 62;
348 cd += (int128_t)u * d2 + (int128_t)v * e2;
349 ce += (int128_t)q * d2 + (int128_t)r * e2;
351 cd += (int128_t)modinfo->
modulus.
v[2] * md;
352 ce += (int128_t)modinfo->
modulus.
v[2] * me;
354 d->
v[1] = (int64_t)cd & M62; cd >>= 62;
355 e->
v[1] = (int64_t)ce & M62; ce >>= 62;
357 cd += (int128_t)u * d3 + (int128_t)v * e3;
358 ce += (int128_t)q * d3 + (int128_t)r * e3;
360 cd += (int128_t)modinfo->
modulus.
v[3] * md;
361 ce += (int128_t)modinfo->
modulus.
v[3] * me;
363 d->
v[2] = (int64_t)cd & M62; cd >>= 62;
364 e->
v[2] = (int64_t)ce & M62; ce >>= 62;
366 cd += (int128_t)u * d4 + (int128_t)v * e4;
367 ce += (int128_t)q * d4 + (int128_t)r * e4;
368 cd += (int128_t)modinfo->
modulus.
v[4] * md;
369 ce += (int128_t)modinfo->
modulus.
v[4] * me;
370 d->
v[3] = (int64_t)cd & M62; cd >>= 62;
371 e->
v[3] = (int64_t)ce & M62; ce >>= 62;
373 d->
v[4] = (int64_t)cd;
374 e->
v[4] = (int64_t)ce;
388 const int64_t M62 = (int64_t)(UINT64_MAX >> 2);
389 const int64_t f0 = f->
v[0], f1 = f->
v[1], f2 = f->
v[2], f3 = f->
v[3], f4 = f->
v[4];
390 const int64_t g0 =
g->v[0], g1 =
g->v[1], g2 =
g->v[2], g3 =
g->v[3], g4 =
g->v[4];
391 const int64_t u =
t->u, v =
t->v, q =
t->q, r =
t->r;
394 cf = (int128_t)u * f0 + (int128_t)v * g0;
395 cg = (int128_t)q * f0 + (int128_t)r * g0;
400 cf += (int128_t)u * f1 + (int128_t)v * g1;
401 cg += (int128_t)q * f1 + (int128_t)r * g1;
402 f->
v[0] = (int64_t)cf & M62; cf >>= 62;
403 g->v[0] = (int64_t)cg & M62; cg >>= 62;
405 cf += (int128_t)u * f2 + (int128_t)v * g2;
406 cg += (int128_t)q * f2 + (int128_t)r * g2;
407 f->
v[1] = (int64_t)cf & M62; cf >>= 62;
408 g->v[1] = (int64_t)cg & M62; cg >>= 62;
410 cf += (int128_t)u * f3 + (int128_t)v * g3;
411 cg += (int128_t)q * f3 + (int128_t)r * g3;
412 f->
v[2] = (int64_t)cf & M62; cf >>= 62;
413 g->v[2] = (int64_t)cg & M62; cg >>= 62;
415 cf += (int128_t)u * f4 + (int128_t)v * g4;
416 cg += (int128_t)q * f4 + (int128_t)r * g4;
417 f->
v[3] = (int64_t)cf & M62; cf >>= 62;
418 g->v[3] = (int64_t)cg & M62; cg >>= 62;
420 f->
v[4] = (int64_t)cf;
421 g->v[4] = (int64_t)cg;
431 const int64_t M62 = (int64_t)(UINT64_MAX >> 2);
432 const int64_t u =
t->u, v =
t->v, q =
t->q, r =
t->r;
440 cf = (int128_t)u * fi + (int128_t)v * gi;
441 cg = (int128_t)q * fi + (int128_t)r * gi;
447 for (i = 1; i < len; ++i) {
450 cf += (int128_t)u * fi + (int128_t)v * gi;
451 cg += (int128_t)q * fi + (int128_t)r * gi;
452 f->
v[i - 1] = (int64_t)cf & M62; cf >>= 62;
453 g->v[i - 1] = (int64_t)cg & M62; cg >>= 62;
456 f->
v[len - 1] = (int64_t)cf;
457 g->v[len - 1] = (int64_t)cg;
471 for (i = 0; i < 10; ++i) {
498 VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&
g, 5, &SECP256K1_SIGNED62_ONE, 0) == 0);
500 VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, 5, &SECP256K1_SIGNED62_ONE, -1) == 0 ||
501 secp256k1_modinv64_mul_cmp_62(&f, 5, &SECP256K1_SIGNED62_ONE, 1) == 0 ||
502 (secp256k1_modinv64_mul_cmp_62(x, 5, &SECP256K1_SIGNED62_ONE, 0) == 0 &&
503 secp256k1_modinv64_mul_cmp_62(&d, 5, &SECP256K1_SIGNED62_ONE, 0) == 0 &&
504 (secp256k1_modinv64_mul_cmp_62(&f, 5, &modinfo->
modulus, 1) == 0 ||
505 secp256k1_modinv64_mul_cmp_62(&f, 5, &modinfo->
modulus, -1) == 0)));
525 int64_t cond, fn, gn;
546 for (j = 1; j < len; ++j) {
550 if (cond == 0)
break;
556 cond = ((int64_t)len - 2) >> 63;
557 cond |= fn ^ (fn >> 63);
558 cond |= gn ^ (gn >> 63);
561 f.
v[len - 2] |= (uint64_t)fn << 62;
562 g.v[len - 2] |= (uint64_t)gn << 62;
578 VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&
g, len, &SECP256K1_SIGNED62_ONE, 0) == 0);
580 VERIFY_CHECK(secp256k1_modinv64_mul_cmp_62(&f, len, &SECP256K1_SIGNED62_ONE, -1) == 0 ||
581 secp256k1_modinv64_mul_cmp_62(&f, len, &SECP256K1_SIGNED62_ONE, 1) == 0 ||
582 (secp256k1_modinv64_mul_cmp_62(x, 5, &SECP256K1_SIGNED62_ONE, 0) == 0 &&
583 secp256k1_modinv64_mul_cmp_62(&d, 5, &SECP256K1_SIGNED62_ONE, 0) == 0 &&
584 (secp256k1_modinv64_mul_cmp_62(&f, len, &modinfo->
modulus, 1) == 0 ||
585 secp256k1_modinv64_mul_cmp_62(&f, len, &modinfo->
modulus, -1) == 0)));