From f1bbbcae39e99b127aaf063ed0bd80799155aa4d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Niels=20M=C3=B6ller?= Date: Sun, 8 Nov 2020 11:38:13 +0100 Subject: Reduce scratch need for ecc_add_jja --- ecc-add-jja.c | 87 ++++++++++++++++++++++++++++++++--------------------------- 1 file changed, 47 insertions(+), 40 deletions(-) (limited to 'ecc-add-jja.c') diff --git a/ecc-add-jja.c b/ecc-add-jja.c index a79f995e..570ea345 100644 --- a/ecc-add-jja.c +++ b/ecc-add-jja.c @@ -54,6 +54,16 @@ ecc_add_jja (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q, mp_limb_t *scratch) { +#define x1 p +#define y1 (p + ecc->p.size) +#define z1 (p + 2*ecc->p.size) +#define x2 q +#define y2 (q + ecc->p.size) + +#define x3 r +#define y3 (r + ecc->p.size) +#define z3 (r + 2*ecc->p.size) + /* Formulas, from djb, http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b): @@ -73,52 +83,49 @@ ecc_add_jja (const struct ecc_curve *ecc, */ #define zz scratch #define h (scratch + ecc->p.size) -#define hh (scratch + 2*ecc->p.size) -#define w (scratch + 3*ecc->p.size) -#define j (scratch + 4*ecc->p.size) -#define v scratch - -#define x1 p -#define y1 (p + ecc->p.size) -#define z1 (p + 2*ecc->p.size) -#define x2 q -#define y2 (q + ecc->p.size) +#define w (scratch + 2*ecc->p.size) +#define hh zz +#define i zz +#define v zz +#define j h +#define tp (scratch + 3*ecc->p.size) /* zz */ - ecc_mod_sqr (&ecc->p, zz, z1, zz); + ecc_mod_sqr (&ecc->p, zz, z1, tp); /* zz */ /* h*/ - ecc_mod_mul (&ecc->p, h, x2, zz, h); + ecc_mod_mul (&ecc->p, h, x2, zz, tp); /* zz, h */ ecc_mod_sub (&ecc->p, h, h, x1); - /* hh */ - ecc_mod_sqr (&ecc->p, hh, h, hh); /* Do z^3 early, store at w. */ - ecc_mod_mul (&ecc->p, w, zz, z1, w); - /* z_3, use j area for scratch */ - ecc_mod_add (&ecc->p, r + 2*ecc->p.size, p + 2*ecc->p.size, h); - ecc_mod_sqr (&ecc->p, j, r + 2*ecc->p.size, j); - ecc_mod_sub (&ecc->p, j, j, zz); - ecc_mod_sub (&ecc->p, r + 2*ecc->p.size, j, hh); + ecc_mod_mul (&ecc->p, w, zz, z1, tp); /* zz, h, w */ + /* z_3 */ + ecc_mod_add (&ecc->p, z3, z1, h); + ecc_mod_sqr (&ecc->p, z3, z3, tp); + ecc_mod_sub (&ecc->p, z3, z3, zz); /* h, w */ + /* hh */ + ecc_mod_sqr (&ecc->p, hh, h, tp); /* h, w, hh */ + ecc_mod_sub (&ecc->p, z3, z3, hh); /* w */ - ecc_mod_mul (&ecc->p, j, y2, w, j); - ecc_mod_sub (&ecc->p, w, j, y1); - ecc_mod_mul_1 (&ecc->p, w, w, 2); + ecc_mod_mul (&ecc->p, w, y2, w, tp); + ecc_mod_sub (&ecc->p, w, w, y1); + ecc_mod_add (&ecc->p, w, w, w); - /* i replaces hh, j */ - ecc_mod_mul_1 (&ecc->p, hh, hh, 4); - ecc_mod_mul (&ecc->p, j, hh, h, j); - - /* v */ - ecc_mod_mul (&ecc->p, v, x1, hh, v); - - /* x_3, use (h, hh) as sqratch */ - ecc_mod_sqr (&ecc->p, h, w, h); - ecc_mod_sub (&ecc->p, r, h, j); - ecc_mod_submul_1 (&ecc->p, r, v, 2); - - /* y_3, use (h, hh) as sqratch */ - ecc_mod_mul (&ecc->p, h, y1, j, h); /* frees j */ - ecc_mod_sub (&ecc->p, r + ecc->p.size, v, r); - ecc_mod_mul (&ecc->p, r + ecc->p.size, r + ecc->p.size, w, j); - ecc_mod_submul_1 (&ecc->p, r + ecc->p.size, h, 2); + /* i replaces hh */ + ecc_mod_mul_1 (&ecc->p, i, hh, 4); /* h, w, i */ + /* j replaces h */ + ecc_mod_mul (&ecc->p, j, i, h, tp); /* w, i, j */ + + /* v replaces i */ + ecc_mod_mul (&ecc->p, v, x1, i, tp); + + /* x_3 */ + ecc_mod_sqr (&ecc->p, x3, w, tp); + ecc_mod_sub (&ecc->p, x3, x3, j); + ecc_mod_submul_1 (&ecc->p, x3, v, 2); + + /* y_3 */ + ecc_mod_mul (&ecc->p, j, y1, j, tp); + ecc_mod_sub (&ecc->p, y3, v, x3); + ecc_mod_mul (&ecc->p, y3, y3, w, tp); + ecc_mod_submul_1 (&ecc->p, y3, j, 2); } -- cgit v1.2.1