From 0ded32192e076de0aed888a451fa355f6c851b5c Mon Sep 17 00:00:00 2001
From: Jeffrey Walton <noloader@gmail.com>
Date: Tue, 6 Aug 2019 03:14:03 -0400
Subject: Avoid branches in Montgomery Add() (GH #869)

---
 ecp.cpp | 54 ++++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 42 insertions(+), 12 deletions(-)

(limited to 'ecp.cpp')

diff --git a/ecp.cpp b/ecp.cpp
index cc6f7a13..7b5249b0 100644
--- a/ecp.cpp
+++ b/ecp.cpp
@@ -868,22 +868,52 @@ ECP::Point ECP::AdditionFunction::operator()(const Point& P, const Point& Q) con
 	}
 	else  // A_Montgomery
 	{
-		ECP::Point& m_R = m_ecp.m_R;
 		const ECP::Field& field = m_ecp.GetField();
+		const FieldElement& a = m_ecp.m_a;
+		ECP::Point& R = m_ecp.m_R, S = m_ecp.m_R, T;
 
-		if (P.identity) return Q;
-		if (Q.identity) return P;
-		if (field.Equal(P.x, Q.x))
-			return field.Equal(P.y, Q.y) ? m_ecp.Double(P) : m_ecp.Identity();
+		// More gyrations
+		bool return_Q = P.identity;
+		bool return_P = Q.identity;
+		bool double_P = field.Equal(P.x, Q.x) && field.Equal(P.y, Q.y);
+		bool identity = field.Equal(P.x, Q.x) && !field.Equal(P.y, Q.y);
 
-		FieldElement t =  field.Subtract(Q.y, P.y);
-		t =  field.Divide(t,  field.Subtract(Q.x, P.x));
-		FieldElement x =  field.Subtract(field.Subtract(field.Square(t), P.x), Q.x);
-		m_R.y =  field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);
+		// This code taken from Double(P)
+		identity |= double_P * (P.identity | P.y==field.Identity());
 
-		m_R.x.swap(x);
-		m_R.identity = false;
-		return m_R;
+		if (double_P)
+		{
+			// This code taken from Double(P)
+			FieldElement t = field.Square(P.x);
+			t = field.Add(field.Add(field.Double(t), t), a);
+			t = field.Divide(t, field.Double(P.y));
+			FieldElement x = field.Subtract(field.Subtract(field.Square(t), P.x), P.x);
+			T.y = field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);
+			T.x.swap(x);
+		}
+		else
+		{
+			// Original Double (P,Q) code
+			FieldElement t = field.Subtract(Q.y, P.y);
+			t = field.Divide(t, field.Subtract(Q.x, P.x));
+			FieldElement x = field.Subtract(field.Subtract(field.Square(t), P.x), Q.x);
+			R.y = field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);
+			R.x.swap(x);
+		}
+
+		// More gyrations
+		R.x = R.x * IdentityToInteger(!identity);
+		R.y = R.y * IdentityToInteger(!identity);
+		R.identity = identity;
+
+		if (return_Q)
+			return (R = S), Q;
+		else if (return_P)
+			return (R = S), P;
+		else if (double_P)
+			return (T = R), R;
+		else
+			return (T = R), R;
 	}
 }
 
-- 
cgit v1.2.1