From 3709f7955d5d52033464831d5c07fc31783479d0 Mon Sep 17 00:00:00 2001
From: Mark Wooding <mdw@distorted.org.uk>
Date: Wed, 10 May 2017 21:15:56 +0100
Subject: [PATCH] pub/ed25519.c: Rearrange `ptadd' to use fewer registers.

Taking a little inspiration from the three-address code in the
paper (which I can't use as-is, because it clobbers one of its inputs) I
managed to delete two of the temporary registers.
---
 pub/ed25519.c | 32 ++++++++++++++++----------------
 1 file changed, 16 insertions(+), 16 deletions(-)

diff --git a/pub/ed25519.c b/pub/ed25519.c
index 4680a537..c6b805c4 100644
--- a/pub/ed25519.c
+++ b/pub/ed25519.c
@@ -172,7 +172,7 @@ static void ptadd(f25519 *X, f25519 *Y, f25519 *Z,
 		  const f25519 *X0, const f25519 *Y0, const f25519 *Z0,
 		  const f25519 *X1, const f25519 *Y1, const f25519 *Z1)
 {
-  f25519 t0, t1, t2, t3, t4, t5;
+  f25519 t0, t1, t2, t3;
 
   /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
    * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the
@@ -187,23 +187,23 @@ static void ptadd(f25519 *X, f25519 *Y, f25519 *Z,
    */
 
   f25519_mul(&t0, Z0, Z1);		/* t0 = A = Z0 Z1 */
-  f25519_sqr(&t1, &t0);			/* t1 = B = A^2 */
+  f25519_add(&t1, X0, Y0);		/* t1 = X0 + Y0 */
+  f25519_add(&t2, X1, Y1);		/* t2 = X1 + Y1 */
+  f25519_mul(&t1, &t1, &t2);		/* t1 = (X0 + Y0) (X1 + Y1) */
   f25519_mul(&t2, X0, X1);		/* t2 = C = X0 X1 */
   f25519_mul(&t3, Y0, Y1);		/* t3 = D = Y0 Y1 */
-  f25519_mul(&t4, &t2, &t3);		/* t4 = C D */
-  f25519_mul(&t4, &t4, D);		/* t4 = E = d C D */
-  f25519_sub(&t5, &t1, &t4);		/* t5 = F = B - E */
-  f25519_add(&t4, &t1, &t4);		/* t4 = G = B + E */
-  f25519_add(&t1, &t2, &t3);		/* t1 = C + D */
-  f25519_add(&t2, X0, Y0);		/* t2 = X0 + Y0 */
-  f25519_add(&t3, X1, Y1);		/* t3 = X1 + Y1 */
-  f25519_mul(X, &t0, &t5);		/* X = A F */
-  f25519_mul(Y, &t0, &t4);		/* Y = A G */
-  f25519_mul(Z, &t5, &t4);		/* Z = F G */
-  f25519_mul(Y, Y, &t1);		/* Y = A G (C + D) = A G (D - a C) */
-  f25519_mul(&t0, &t2, &t3);		/* t0 = (X0 + Y0) (X1 + Y1) */
-  f25519_sub(&t0, &t0, &t1);	       /* t0 = (X0 + Y0) (X1 + Y1) - C - D */
-  f25519_mul(X, X, &t0);	  /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
+  f25519_add(Y, &t2, &t3);		/* Y = C + D = D - a C */
+  f25519_sub(X, &t1, Y);		/* X = (X0 + Y0) (X1 + Y1) - C - D */
+  f25519_mul(X, X, &t0);	    /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */
+  f25519_mul(Y, Y, &t0);		/* Y = A (D - a C) */
+  f25519_sqr(&t0, &t0);			/* t0 = B = A^2 */
+  f25519_mul(&t1, &t2, &t3);		/* t1 = C D */
+  f25519_mul(&t1, &t1, D);		/* t1 = E = d C D */
+  f25519_sub(&t2, &t0, &t1);		/* t2 = F = B - E */
+  f25519_add(&t1, &t0, &t1);		/* t1 = G = B + E */
+  f25519_mul(X, X, &t2);	  /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
+  f25519_mul(Y, Y, &t1);		/* Y = A G (D - a C) */
+  f25519_mul(Z, &t1, &t2);		/* Z = F G */
 }
 
 static void ptdbl(f25519 *X, f25519 *Y, f25519 *Z,
-- 
2.11.0