tls: optimize sp_256_mont_reduce_8 in P256

The code size decrease is small, but we eliminate ALL multiplies!

function                                             old     new   delta
sp_256_mont_reduce_8                                 268     262      -6

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>

1 files changed, 125 insertions, 21 deletions

diff --git a/networking/tls_sp_c32.c b/networking/tls_sp_c32.c
index e1c4cdd..0773a2d 100644
--- a/networking/tls_sp_c32.c
+++ b/networking/tls_sp_c32.c
@@ -488,19 +488,118 @@ static void sp_256_mont_shift_8(sp_digit* r, const sp_digit* a)
 }
 
 /* Mul a by scalar b and add into r. (r += a * b) */
-static int sp_256_mul_add_8(sp_digit* r, const sp_digit* a, sp_digit b)
+static int sp_256_mul_add_8(sp_digit* r /*, const sp_digit* a, sp_digit b*/)
 {
+//	const sp_digit* a = p256_mod;
+//a[7..0] = ffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff ffffffff
+	sp_digit b = r[0];
 	uint64_t t = 0;
-	int i;
 
-	for (i = 0; i < 8; i++) {
-		uint32_t t_hi;
-		uint64_t m = ((uint64_t)b * a[i]) + r[i];
+//	for (i = 0; i < 8; i++) {
+//		uint32_t t_hi;
+//		uint64_t m = ((uint64_t)b * a[i]) + r[i];
+//		t += m;
+//		t_hi = (t < m);
+//		r[i] = (sp_digit)t;
+//		t = (t >> 32) | ((uint64_t)t_hi << 32);
+//	}
+//	r[8] += (sp_digit)t;
+
+	// Unroll, then optimize the above loop:
+		//uint32_t t_hi;
+		uint64_t m;
+
+		//m = ((uint64_t)b * a[0]) + r[0];
+		//  Since b is r[0] and a[0] is ffffffff, the above optimizes to:
+		//  m = r[0] * ffffffff + r[0] = (r[0] * 100000000 - r[0]) + r[0] = r[0] << 32;
+		//t += m;
+		//  t = (uint64_t)r[0] << 32;
+		//t_hi = (t < m);
+		//  t_hi = 0;
+		//r[0] = (sp_digit)t;
+		r[0] = 0;
+		//t = (t >> 32) | ((uint64_t)t_hi << 32);
+		//  t = b;
+
+		//m = ((uint64_t)b * a[1]) + r[1];
+		//  Since a[1] is ffffffff, the above optimizes to:
+		//  m = b * ffffffff + r[1] = (b * 100000000 - b) + r[1] = (b << 32) - b + r[1];
+		//t += m;
+		//  t = b + (b << 32) - b + r[1] = (b << 32) + r[1];
+		//t_hi = (t < m);
+		//  t_hi = 0;
+		//r[1] = (sp_digit)t;
+		//  r[1] = r[1];
+		//t = (t >> 32) | ((uint64_t)t_hi << 32);
+		//  t = b;
+
+		//m = ((uint64_t)b * a[2]) + r[2];
+		//  Since a[2] is ffffffff, the above optimizes to:
+		//  m = b * ffffffff + r[2] = (b * 100000000 - b) + r[2] = (b << 32) - b + r[2];
+		//t += m;
+		//  t = b + (b << 32) - b + r[2] = (b << 32) + r[2]
+		//t_hi = (t < m);
+		//  t_hi = 0;
+		//r[2] = (sp_digit)t;
+		//  r[2] = r[2];
+		//t = (t >> 32) | ((uint64_t)t_hi << 32);
+		//  t = b;
+
+		//m = ((uint64_t)b * a[3]) + r[3];
+		//  Since a[3] is 00000000, the above optimizes to:
+		//  m = b * 0 + r[3] = r[3];
+		//t += m;
+		//  t += r[3];
+		//t_hi = (t < m);
+		//  t_hi = 0;
+		//r[3] = (sp_digit)t;
+		r[3] = r[3] + b;
+		//t = (t >> 32) | ((uint64_t)t_hi << 32);
+		t = (r[3] < b);
+
+		//m = ((uint64_t)b * a[4]) + r[4];
+		//  Since a[4] is 00000000, the above optimizes to:
+		//  m = b * 0 + r[4] = r[4];
+		//t += m;
+		t += r[4];
+		//t_hi = (t < m);
+		//  t_hi = 0;
+		r[4] = (sp_digit)t;
+		//t = (t >> 32) | ((uint64_t)t_hi << 32);
+		t = (t >> 32);
+
+		//m = ((uint64_t)b * a[5]) + r[5];
+		//  Since a[5] is 00000000, the above optimizes to:
+		//  m = b * 0 + r[5] = r[5];
+		//t += m;
+		t += r[5];
+		//t_hi = (t < m);
+		//  t_hi = 0;
+		r[5] = (sp_digit)t;
+		//t = (t >> 32) | ((uint64_t)t_hi << 32);
+		t = (t >> 32);
+
+		//m = ((uint64_t)b * a[6]) + r[6];
+		//  Since a[6] is 00000001, the above optimizes to:
+		m = (uint64_t)b + r[6]; // 33 bits at most
 		t += m;
-		t_hi = (t < m);
-		r[i] = (sp_digit)t;
-		t = (t >> 32) | ((uint64_t)t_hi << 32);
-	}
+		//t_hi = (t < m);
+		//  t_hi = 0; //32bit_value + 33bit_value can't overflow 64 bits
+		r[6] = (sp_digit)t;
+		//t = (t >> 32) | ((uint64_t)t_hi << 32);
+		t = (t >> 32);
+
+		//m = ((uint64_t)b * a[7]) + r[7];
+		//  Since a[7] is ffffffff, the above optimizes to:
+		//  m = b * ffffffff + r[7] = (b * 100000000 - b) + r[7]
+		m = ((uint64_t)b << 32) - b + r[7];
+		t += m;
+		//t_hi = (t < m);
+		//  t_hi in fact is always 0 here
+		r[7] = (sp_digit)t;
+		//t = (t >> 32) | ((uint64_t)t_hi << 32);
+		t = (t >> 32);
+
 	r[8] += (sp_digit)t;
 	return (r[8] < (sp_digit)t); /* 1 if addition overflowed */
 }
@@ -517,28 +616,33 @@ static void sp_256_mont_reduce_8(sp_digit* a/*, const sp_digit* m, sp_digit mp*/
 	sp_digit mp = p256_mp_mod;
 
 	int i;
-	sp_digit mu;
+//	sp_digit mu;
 
 	if (mp != 1) {
-		int too_wide;
-		for (i = 0; i < 7; i++) {
-			mu = (sp_digit)(a[i] * mp);
-			if (sp_256_mul_add_8(a+i, m, mu))
-				(a+i)[9]++;
+		sp_digit word16th = 0;
+		for (i = 0; i < 8; i++) {
+//			mu = (sp_digit)(a[i] * mp);
+			if (sp_256_mul_add_8(a+i /*, m, mu*/)) {
+				int j = i + 8;
+ inc_next_word0:
+				if (++j > 15) { /* a[16] array has no more words? */
+					word16th++;
+					continue;
+				}
+				if (++a[j] == 0) /* did this overflow too? */
+					goto inc_next_word0;
+			}
 		}
-		mu = (sp_digit)(a[7] * mp);
-		too_wide = sp_256_mul_add_8(a+7, m, mu);
 		sp_256_mont_shift_8(a, a);
-		if (too_wide)
+		if (word16th != 0)
 			sp_256_sub_8(a, a, m);
 		sp_256_norm_8(a);
 	}
 	else { /* Same code for explicit mp == 1 (which is always the case for P256) */
 		sp_digit word16th = 0;
 		for (i = 0; i < 8; i++) {
-			mu = a[i];
-//m = ffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff ffffffff
-			if (sp_256_mul_add_8(a+i, m, mu)) {
+//			mu = a[i];
+			if (sp_256_mul_add_8(a+i /*, m, mu*/)) {
 				int j = i + 8;
  inc_next_word:
 				if (++j > 15) { /* a[16] array has no more words? */