tls: shrink sp_256_mod_mul_norm_10

function                                             old     new   delta
sp_256_mod_mul_norm_10                              1439    1405     -34

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

2 files changed, 85 insertions, 202 deletions

diff --git a/networking/tls_sp_c32.c b/networking/tls_sp_c32.c
index f9c66b186..c5e887aad 100644
--- a/networking/tls_sp_c32.c
+++ b/networking/tls_sp_c32.c
@@ -460,51 +460,90 @@ static void sp_256_mont_inv_10(sp_digit* r, sp_digit* a)
 static void sp_256_mod_mul_norm_10(sp_digit* r, const sp_digit* a)
 {
         int64_t t[8];
-        int64_t a32[8];
         int64_t o;
-
-        a32[0] = a[0];
-        a32[0] |= a[1] << 26;
-        a32[0] &= 0xffffffff;
-        a32[1] = (sp_digit)(a[1] >> 6);
-        a32[1] |= a[2] << 20;
-        a32[1] &= 0xffffffff;
-        a32[2] = (sp_digit)(a[2] >> 12);
-        a32[2] |= a[3] << 14;
-        a32[2] &= 0xffffffff;
-        a32[3] = (sp_digit)(a[3] >> 18);
-        a32[3] |= a[4] << 8;
-        a32[3] &= 0xffffffff;
-        a32[4] = (sp_digit)(a[4] >> 24);
-        a32[4] |= a[5] << 2;
-        a32[4] |= a[6] << 28;
-        a32[4] &= 0xffffffff;
-        a32[5] = (sp_digit)(a[6] >> 4);
-        a32[5] |= a[7] << 22;
-        a32[5] &= 0xffffffff;
-        a32[6] = (sp_digit)(a[7] >> 10);
-        a32[6] |= a[8] << 16;
-        a32[6] &= 0xffffffff;
-        a32[7] = (sp_digit)(a[8] >> 16);
-        a32[7] |= a[9] << 10;
-        a32[7] &= 0xffffffff;
+        uint32_t a32;
 
         /*  1  1  0 -1 -1 -1 -1  0 */
-        t[0] = 0 + a32[0] + a32[1] - a32[3] - a32[4] - a32[5] - a32[6];
         /*  0  1  1  0 -1 -1 -1 -1 */
-        t[1] = 0 + a32[1] + a32[2] - a32[4] - a32[5] - a32[6] - a32[7];
         /*  0  0  1  1  0 -1 -1 -1 */
-        t[2] = 0 + a32[2] + a32[3] - a32[5] - a32[6] - a32[7];
         /* -1 -1  0  2  2  1  0 -1 */
-        t[3] = 0 - a32[0] - a32[1] + 2 * a32[3] + 2 * a32[4] + a32[5] - a32[7];
         /*  0 -1 -1  0  2  2  1  0 */
-        t[4] = 0 - a32[1] - a32[2] + 2 * a32[4] + 2 * a32[5] + a32[6];
         /*  0  0 -1 -1  0  2  2  1 */
-        t[5] = 0 - a32[2] - a32[3] + 2 * a32[5] + 2 * a32[6] + a32[7];
         /* -1 -1  0  0  0  1  3  2 */
-        t[6] = 0 - a32[0] - a32[1] + a32[5] + 3 * a32[6] + 2 * a32[7];
         /*  1  0 -1 -1 -1 -1  0  3 */
-        t[7] = 0 + a32[0] - a32[2] - a32[3] - a32[4] - a32[5] + 3 * a32[7];
+        // t[] should be calculated from "a" (converted from 26-bit to 32-bit vector a32[8])
+        // according to the above matrix:
+        //t[0] = 0 + a32[0] + a32[1]            - a32[3]   - a32[4]   - a32[5]   - a32[6]             ;
+        //t[1] = 0          + a32[1] + a32[2]              - a32[4]   - a32[5]   - a32[6]   - a32[7]  ;
+        //t[2] = 0                   + a32[2]   + a32[3]              - a32[5]   - a32[6]   - a32[7]  ;
+        //t[3] = 0 - a32[0] - a32[1]            + 2*a32[3] + 2*a32[4] + a32[5]              - a32[7]  ;
+        //t[4] = 0          - a32[1] - a32[2]              + 2*a32[4] + 2*a32[5] + a32[6]             ;
+        //t[5] = 0                   - a32[2]   - a32[3]              + 2*a32[5] + 2*a32[6] + a32[7]  ;
+        //t[6] = 0 - a32[0] - a32[1]                                  + a32[5]   + 3*a32[6] + 2*a32[7];
+        //t[7] = 0 + a32[0]          - a32[2]   - a32[3]   - a32[4]   - a32[5]              + 3*a32[7];
+        // We can do it "piecemeal" after each a32[i] is known, no need to store entire a32[8] vector:
+
+#define A32 (int64_t)a32
+        a32 = a[0] | (a[1] << 26);
+        t[0] = 0 + A32;
+        t[3] = 0 - A32;
+        t[6] = 0 - A32;
+        t[7] = 0 + A32;
+
+        a32 = (a[1] >> 6) | (a[2] << 20);
+        t[0] += A32    ;
+        t[1]  = 0 + A32;
+        t[3] -= A32    ;
+        t[4]  = 0 - A32;
+        t[6] -= A32    ;
+
+        a32 = (a[2] >> 12) | (a[3] << 14);
+        t[1] += A32    ;
+        t[2]  = 0 + A32;
+        t[4] -= A32    ;
+        t[5]  = 0 - A32;
+        t[7] -= A32    ;
+
+        a32 = (a[3] >> 18) | (a[4] << 8);
+        t[0] -= A32  ;
+        t[2] += A32  ;
+        t[3] += 2*A32;
+        t[5] -= A32  ;
+        t[7] -= A32  ;
+
+        a32 = (a[4] >> 24) | (a[5] << 2) | (a[6] << 28);
+        t[0] -= A32  ;
+        t[1] -= A32  ;
+        t[3] += 2*A32;
+        t[4] += 2*A32;
+        t[7] -= A32  ;
+
+        a32 = (a[6] >> 4) | (a[7] << 22);
+        t[0] -= A32  ;
+        t[1] -= A32  ;
+        t[2] -= A32  ;
+        t[3] += A32  ;
+        t[4] += 2*A32;
+        t[5] += 2*A32;
+        t[6] += A32  ;
+        t[7] -= A32  ;
+
+        a32 = (a[7] >> 10) | (a[8] << 16);
+        t[0] -= A32  ;
+        t[1] -= A32  ;
+        t[2] -= A32  ;
+        t[4] += A32  ;
+        t[5] += 2*A32;
+        t[6] += 3*A32;
+
+        a32 = (a[8] >> 16) | (a[9] << 10);
+        t[1] -= A32  ;
+        t[2] -= A32  ;
+        t[3] -= A32  ;
+        t[5] += A32  ;
+        t[6] += 2*A32;
+        t[7] += 3*A32;
+#undef A32
 
         t[1] += t[0] >> 32; t[0] &= 0xffffffff;
         t[2] += t[1] >> 32; t[1] &= 0xffffffff;
@@ -526,30 +565,16 @@ static void sp_256_mod_mul_norm_10(sp_digit* r, const sp_digit* a)
         t[6] += t[5] >> 32; t[5] &= 0xffffffff;
         t[7] += t[6] >> 32; t[6] &= 0xffffffff;
 
-        r[0] = (sp_digit)(t[0]) & 0x3ffffff;
-        r[1] = (sp_digit)(t[0] >> 26);
-        r[1] |= t[1] << 6;
-        r[1] &= 0x3ffffff;
-        r[2] = (sp_digit)(t[1] >> 20);
-        r[2] |= t[2] << 12;
-        r[2] &= 0x3ffffff;
-        r[3] = (sp_digit)(t[2] >> 14);
-        r[3] |= t[3] << 18;
-        r[3] &= 0x3ffffff;
-        r[4] = (sp_digit)(t[3] >> 8);
-        r[4] |= t[4] << 24;
-        r[4] &= 0x3ffffff;
-        r[5] = (sp_digit)(t[4] >> 2) & 0x3ffffff;
-        r[6] = (sp_digit)(t[4] >> 28);
-        r[6] |= t[5] << 4;
-        r[6] &= 0x3ffffff;
-        r[7] = (sp_digit)(t[5] >> 22);
-        r[7] |= t[6] << 10;
-        r[7] &= 0x3ffffff;
-        r[8] = (sp_digit)(t[6] >> 16);
-        r[8] |= t[7] << 16;
-        r[8] &= 0x3ffffff;
-        r[9] = (sp_digit)(t[7] >> 10);
+        r[0] = 0x3ffffff & ((sp_digit)(t[0]));
+        r[1] = 0x3ffffff & ((sp_digit)(t[0] >> 26) | ((sp_digit)t[1] <<  6));
+        r[2] = 0x3ffffff & ((sp_digit)(t[1] >> 20) | ((sp_digit)t[2] << 12));
+        r[3] = 0x3ffffff & ((sp_digit)(t[2] >> 14) | ((sp_digit)t[3] << 18));
+        r[4] = 0x3ffffff & ((sp_digit)(t[3] >>  8) | ((sp_digit)t[4] << 24));
+        r[5] = 0x3ffffff & ((sp_digit)t[4]  >>  2); /* small shift, ok to cast t[4] to narrower type */
+        r[6] = 0x3ffffff & ((sp_digit)(t[4] >> 28) | ((sp_digit)t[5] <<  4));
+        r[7] = 0x3ffffff & ((sp_digit)(t[5] >> 22) | ((sp_digit)t[6] << 10));
+        r[8] = 0x3ffffff & ((sp_digit)(t[6] >> 16) | ((sp_digit)t[7] << 16));
+        r[9] =             ((sp_digit)(t[7] >> 10));
 }
 
 /* Map the Montgomery form projective co-ordinate point to an affine point.
@@ -795,7 +820,7 @@ static void sp_256_ecc_mulmod_base_10(sp_point* r, sp_digit* k /*, int map*/)
                 0x6b,0x17,0xd1,0xf2,0xe1,0x2c,0x42,0x47,0xf8,0xbc,0xe6,0xe5,0x63,0xa4,0x40,0xf2,0x77,0x03,0x7d,0x81,0x2d,0xeb,0x33,0xa0,0xf4,0xa1,0x39,0x45,0xd8,0x98,0xc2,0x96,
                 /* y */
                 0x4f,0xe3,0x42,0xe2,0xfe,0x1a,0x7f,0x9b,0x8e,0xe7,0xeb,0x4a,0x7c,0x0f,0x9e,0x16,0x2b,0xce,0x33,0x57,0x6b,0x31,0x5e,0xce,0xcb,0xb6,0x40,0x68,0x37,0xbf,0x51,0xf5,
-                /* z will be set to 0, infinity flag to "false" */
+                /* z will be set to 1, infinity flag to "false" */
         };
         sp_point p256_base;
 
diff --git a/networking/tls_sp_c32.patch b/networking/tls_sp_c32.patch
deleted file mode 100644
index 7559586c9..000000000
--- a/networking/tls_sp_c32.patch
+++ /dev/null
@@ -1,142 +0,0 @@
-Somehow, gcc 6+ does this optimization same or better than the below
-hand-written optimized code (gcc seem to eliminate a32[] array, uses 32-bit
-registers/memory for "lower halves" of a32[i] elements).
-
-But there can be arches where gcc won't be this good?
-
-diff --git a/networking/tls_sp_c32.c b/networking/tls_sp_c32.c
-index 72a3be537..e8a011ad1 100644
---- a/networking/tls_sp_c32.c
-+++ b/networking/tls_sp_c32.c
-@@ -228,51 +228,96 @@ static void sp_256_rshift1_10(sp_digit* r, sp_digit* a)
- static void sp_256_mod_mul_norm_10(sp_digit* r, const sp_digit* a)
- {
-        int64_t t[8];
--       int64_t a32[8];
-+       uint32_t a32;
-        int64_t o;
- 
--       a32[0] = a[0];
--       a32[0] |= a[1] << 26;
--       a32[0] &= 0xffffffff;
--       a32[1] = (sp_digit)(a[1] >> 6);
--       a32[1] |= a[2] << 20;
--       a32[1] &= 0xffffffff;
--       a32[2] = (sp_digit)(a[2] >> 12);
--       a32[2] |= a[3] << 14;
--       a32[2] &= 0xffffffff;
--       a32[3] = (sp_digit)(a[3] >> 18);
--       a32[3] |= a[4] << 8;
--       a32[3] &= 0xffffffff;
--       a32[4] = (sp_digit)(a[4] >> 24);
--       a32[4] |= a[5] << 2;
--       a32[4] |= a[6] << 28;
--       a32[4] &= 0xffffffff;
--       a32[5] = (sp_digit)(a[6] >> 4);
--       a32[5] |= a[7] << 22;
--       a32[5] &= 0xffffffff;
--       a32[6] = (sp_digit)(a[7] >> 10);
--       a32[6] |= a[8] << 16;
--       a32[6] &= 0xffffffff;
--       a32[7] = (sp_digit)(a[8] >> 16);
--       a32[7] |= a[9] << 10;
--       a32[7] &= 0xffffffff;
--
-        /*  1  1  0 -1 -1 -1 -1  0 */
--       t[0] = 0 + a32[0] + a32[1] - a32[3] - a32[4] - a32[5] - a32[6];
-        /*  0  1  1  0 -1 -1 -1 -1 */
--       t[1] = 0 + a32[1] + a32[2] - a32[4] - a32[5] - a32[6] - a32[7];
-        /*  0  0  1  1  0 -1 -1 -1 */
--       t[2] = 0 + a32[2] + a32[3] - a32[5] - a32[6] - a32[7];
-        /* -1 -1  0  2  2  1  0 -1 */
--       t[3] = 0 - a32[0] - a32[1] + 2 * a32[3] + 2 * a32[4] + a32[5] - a32[7];
-        /*  0 -1 -1  0  2  2  1  0 */
--       t[4] = 0 - a32[1] - a32[2] + 2 * a32[4] + 2 * a32[5] + a32[6];
-        /*  0  0 -1 -1  0  2  2  1 */
--       t[5] = 0 - a32[2] - a32[3] + 2 * a32[5] + 2 * a32[6] + a32[7];
-        /* -1 -1  0  0  0  1  3  2 */
--       t[6] = 0 - a32[0] - a32[1] + a32[5] + 3 * a32[6] + 2 * a32[7];
-        /*  1  0 -1 -1 -1 -1  0  3 */
--       t[7] = 0 + a32[0] - a32[2] - a32[3] - a32[4] - a32[5] + 3 * a32[7];
-+       //t[0] = 0 + a32[0] + a32[1]            - a32[3]   - a32[4]   - a32[5]   - a32[6]             ;
-+       //t[1] = 0          + a32[1] + a32[2]              - a32[4]   - a32[5]   - a32[6]   - a32[7]  ;
-+       //t[2] = 0                   + a32[2]   + a32[3]              - a32[5]   - a32[6]   - a32[7]  ;
-+       //t[3] = 0 - a32[0] - a32[1]            + 2*a32[3] + 2*a32[4] + a32[5]              - a32[7]  ;
-+       //t[4] = 0          - a32[1] - a32[2]              + 2*a32[4] + 2*a32[5] + a32[6]             ;
-+       //t[5] = 0                   - a32[2]   - a32[3]              + 2*a32[5] + 2*a32[6] + a32[7]  ;
-+       //t[6] = 0 - a32[0] - a32[1]                                  + a32[5]   + 3*a32[6] + 2*a32[7];
-+       //t[7] = 0 + a32[0]          - a32[2]   - a32[3]   - a32[4]   - a32[5]              + 3*a32[7];
-+
-+#define A32 (int64_t)a32
-+       a32 = a[0];
-+       a32 |= a[1] << 26;
-+       t[0] = 0 + A32;
-+       t[3] = 0 - A32;
-+       t[6] = 0 - A32;
-+       t[7] = 0 + A32;
-+
-+       a32 = (sp_digit)(a[1] >> 6);
-+       a32 |= a[2] << 20;
-+       t[0] += A32    ;
-+       t[1]  = 0 + A32;
-+       t[3] -= A32    ;
-+       t[4]  = 0 - A32;
-+       t[6] -= A32    ;
-+
-+       a32 = (sp_digit)(a[2] >> 12);
-+       a32 |= a[3] << 14;
-+       t[1] += A32    ;
-+       t[2]  = 0 + A32;
-+       t[4] -= A32    ;
-+       t[5]  = 0 - A32;
-+       t[7] -= A32    ;
-+
-+       a32 = (sp_digit)(a[3] >> 18);
-+       a32 |= a[4] << 8;
-+       t[0] -= A32  ;
-+       t[2] += A32  ;
-+       t[3] += 2*A32;
-+       t[5] -= A32  ;
-+       t[7] -= A32  ;
-+
-+       a32 = (sp_digit)(a[4] >> 24);
-+       a32 |= a[5] << 2;
-+       a32 |= a[6] << 28;
-+       t[0] -= A32  ;
-+       t[1] -= A32  ;
-+       t[3] += 2*A32;
-+       t[4] += 2*A32;
-+       t[7] -= A32  ;
-+
-+       a32 = (sp_digit)(a[6] >> 4);
-+       a32 |= a[7] << 22;
-+       t[0] -= A32  ;
-+       t[1] -= A32  ;
-+       t[2] -= A32  ;
-+       t[3] += A32  ;
-+       t[4] += 2*A32;
-+       t[5] += 2*A32;
-+       t[6] += A32  ;
-+       t[7] -= A32  ;
-+
-+       a32 = (sp_digit)(a[7] >> 10);
-+       a32 |= a[8] << 16;
-+       t[0] -= A32  ;
-+       t[1] -= A32  ;
-+       t[2] -= A32  ;
-+       t[4] += A32  ;
-+       t[5] += 2*A32;
-+       t[6] += 3*A32;
-+
-+       a32 = (sp_digit)(a[8] >> 16);
-+       a32 |= a[9] << 10;
-+       t[1] -= A32  ;
-+       t[2] -= A32  ;
-+       t[3] -= A32  ;
-+       t[5] += A32  ;
-+       t[6] += 2*A32;
-+       t[7] += 3*A32;
-+#undef A32
- 
-        t[1] += t[0] >> 32; t[0] &= 0xffffffff;
-        t[2] += t[1] >> 32; t[1] &= 0xffffffff;