Tnaf perf. opts.

3 files changed, 211 insertions, 49 deletions

diff --git a/crypto/src/math/ec/abc/Tnaf.cs b/crypto/src/math/ec/abc/Tnaf.cs
index 944f0e229..fd073bb7b 100644
--- a/crypto/src/math/ec/abc/Tnaf.cs
+++ b/crypto/src/math/ec/abc/Tnaf.cs
@@ -1,6 +1,8 @@
 using System;
 
 using Org.BouncyCastle.Math.EC.Multiplier;
+using Org.BouncyCastle.Math.Raw;
+using Org.BouncyCastle.Utilities;
 
 namespace Org.BouncyCastle.Math.EC.Abc
 {
@@ -38,11 +40,14 @@ namespace Org.BouncyCastle.Math.EC.Abc
         */
         public static readonly ZTauElement[] Alpha0 =
         {
-            null,
-            new ZTauElement(BigInteger.One, BigInteger.Zero), null,
-            new ZTauElement(MinusThree, MinusOne), null,
-            new ZTauElement(MinusOne, MinusOne), null,
-            new ZTauElement(BigInteger.One, MinusOne), null
+            null, new ZTauElement(BigInteger.One, BigInteger.Zero),
+            null, new ZTauElement(MinusThree, MinusOne),
+            null, new ZTauElement(MinusOne, MinusOne),
+            null, new ZTauElement(BigInteger.One, MinusOne),
+            null, new ZTauElement(MinusOne, BigInteger.One),
+            null, new ZTauElement(BigInteger.One, BigInteger.One),
+            null, new ZTauElement(BigInteger.Three, BigInteger.One),
+            null, new ZTauElement(MinusOne, BigInteger.Zero),
         };
 
         /**
@@ -60,11 +65,14 @@ namespace Org.BouncyCastle.Math.EC.Abc
         */
         public static readonly ZTauElement[] Alpha1 =
         {
-            null,
-            new ZTauElement(BigInteger.One, BigInteger.Zero), null,
-            new ZTauElement(MinusThree, BigInteger.One), null,
-            new ZTauElement(MinusOne, BigInteger.One), null,
-            new ZTauElement(BigInteger.One, BigInteger.One), null
+            null, new ZTauElement(BigInteger.One, BigInteger.Zero),
+            null, new ZTauElement(MinusThree, BigInteger.One),
+            null, new ZTauElement(MinusOne, BigInteger.One),
+            null, new ZTauElement(BigInteger.One, BigInteger.One),
+            null, new ZTauElement(MinusOne, MinusOne),
+            null, new ZTauElement(BigInteger.One, MinusOne),
+            null, new ZTauElement(BigInteger.Three, MinusOne),
+            null, new ZTauElement(MinusOne, BigInteger.Zero),
         };
 
         /**
@@ -86,31 +94,29 @@ namespace Org.BouncyCastle.Math.EC.Abc
         */
         public static BigInteger Norm(sbyte mu, ZTauElement lambda)
         {
-            BigInteger norm;
-
             // s1 = u^2
-            BigInteger s1 = lambda.u.Multiply(lambda.u);
+            BigInteger s1 = lambda.u.Square();
 
             // s2 = u * v
-            BigInteger s2 = lambda.u.Multiply(lambda.v);
+            //BigInteger s2 = lambda.u.Multiply(lambda.v);
 
             // s3 = 2 * v^2
-            BigInteger s3 = lambda.v.Multiply(lambda.v).ShiftLeft(1);
+            //BigInteger s3 = lambda.v.Square().ShiftLeft(1);
 
             if (mu == 1)
             {
-                norm = s1.Add(s2).Add(s3);
+                //return s1.Add(s2).Add(s3);
+                return lambda.v.ShiftLeft(1).Add(lambda.u).Multiply(lambda.v).Add(s1);
             }
             else if (mu == -1)
             {
-                norm = s1.Subtract(s2).Add(s3);
+                //return s1.Subtract(s2).Add(s3);
+                return lambda.v.ShiftLeft(1).Subtract(lambda.u).Multiply(lambda.v).Add(s1);
             }
             else
             {
                 throw new ArgumentException("mu must be 1 or -1");
             }
-
-            return norm;
         }
 
         /**
@@ -640,10 +646,11 @@ namespace Org.BouncyCastle.Math.EC.Abc
         public static AbstractF2mPoint MultiplyTnaf(AbstractF2mPoint p, ZTauElement lambda)
         {
             AbstractF2mCurve curve = (AbstractF2mCurve)p.Curve;
+            AbstractF2mPoint pNeg = (AbstractF2mPoint)p.Negate();
             sbyte mu = GetMu(curve.A);
             sbyte[] u = TauAdicNaf(mu, lambda);
 
-            return MultiplyFromTnaf(p, u);
+            return MultiplyFromTnaf(p, pNeg, u);
         }
 
         /**
@@ -655,11 +662,10 @@ namespace Org.BouncyCastle.Math.EC.Abc
         * @param u The the TNAF of <code>&#955;</code>..
         * @return <code>&#955; * p</code>
         */
-        public static AbstractF2mPoint MultiplyFromTnaf(AbstractF2mPoint p, sbyte[] u)
+        public static AbstractF2mPoint MultiplyFromTnaf(AbstractF2mPoint p, AbstractF2mPoint pNeg, sbyte[] u)
         {
             ECCurve curve = p.Curve;
             AbstractF2mPoint q = (AbstractF2mPoint)curve.Infinity;
-            AbstractF2mPoint pNeg = (AbstractF2mPoint)p.Negate();
             int tauCount = 0;
             for (int i = u.Length - 1; i >= 0; i--)
             {
@@ -712,50 +718,144 @@ namespace Org.BouncyCastle.Math.EC.Abc
             sbyte[] u = new sbyte[maxLength];
 
             int pow2Width = 1 << width;
-
-            // 2^(width - 1)
-            int pow2wMin1 = pow2Width >> 1;
+            int pow2Mask = pow2Width - 1;
+            int s = 32 - width;
 
             // Split lambda into two BigIntegers to simplify calculations
-            BigInteger r0 = lambda.u;
-            BigInteger r1 = lambda.v;
-            int i = 0;
+            BigInteger R0 = lambda.u;
+            BigInteger R1 = lambda.v;
+            int uPos = 0;
 
-            // while lambda <> (0, 0)
-            while ((r0.SignValue | r1.SignValue) != 0)
+            long r0_64, r1_64;
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            Span<int> alphaUs = stackalloc int[alpha.Length];
+            Span<int> alphaVs = stackalloc int[alpha.Length];
+#else
+            int[] alphaUs = new int[alpha.Length];
+            int[] alphaVs = new int[alpha.Length];
+#endif
+            for (int i = 1; i < alpha.Length; i += 2)
             {
-                // if r0 is odd
-                if (r0.TestBit(0)) 
+                alphaUs[i] = alpha[i].u.IntValueExact;
+                alphaVs[i] = alpha[i].v.IntValueExact;
+            }
+
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+            int len = (System.Math.Max(R0.BitLength, R1.BitLength) + 33) >> 5;
+            if (len <= 2)
+            {
+                r0_64 = R0.LongValueExact;
+                r1_64 = R1.LongValueExact;
+            }
+            else
+            {
+                Span<uint> r0 = len <= 32 ? stackalloc uint[len] : new uint[len];
+                Span<uint> r1 = len <= 32 ? stackalloc uint[len] : new uint[len];
+                Span<uint> rt = len <= 32 ? stackalloc uint[len] : new uint[len];
+
+                BigIntegers.AsUint32ArrayLittleEndian(R0, r0);
+                BigIntegers.AsUint32ArrayLittleEndian(R1, r1);
+
+                long muMask = mu < 0 ? -1L : 0L;
+
+                while (len > 2)
                 {
-                    int uUnMod = (r0.IntValue + (r1.IntValue * tw)) & (pow2Width - 1);
+                    if ((r0[0] & 1U) != 0U)
+                    {
+                        int uVal = (int)r0[0] + ((int)r1[0] * tw);
+                        int alphaPos = uVal & pow2Mask;
+
+                        u[uPos] = (sbyte)((uVal << s) >> s);
+                        Nat.SubInt32From(len, alphaUs[alphaPos], r0);
+                        Nat.SubInt32From(len, alphaVs[alphaPos], r1);
+                    }
 
-                    if (uUnMod >= pow2wMin1)
+                    ++uPos;
+
+                    Nat.ShiftDownBit(len, r0, r0[len - 1] >> 31, rt);
+                    if (mu == 1)
                     {
-                        u[i] = (sbyte)(uUnMod - pow2Width);
-                        r0 = r0.Add(alpha[pow2Width - uUnMod].u);
-                        r1 = r1.Add(alpha[pow2Width - uUnMod].v);
+                        Nat.Add(len, r1, rt, r0);
                     }
-                    else
+                    else // mu == -1
                     {
-                        u[i] = (sbyte)uUnMod;
-                        r0 = r0.Subtract(alpha[uUnMod].u);
-                        r1 = r1.Subtract(alpha[uUnMod].v);
+                        Nat.Sub(len, r1, rt, r0);
                     }
+                    Nat.Negate(len, rt, r1);
+
+                    int r0Sign = (int)r0[len - 1] >> 31;
+                    int r1Sign = (int)r1[len - 1] >> 31;
+
+                    int check = ((int)r0[len - 1] ^ r0Sign)
+                              | (((int)r0[len - 2] >> 30) ^ r0Sign)
+                              | ((int)r1[len - 1] ^ r1Sign)
+                              | (((int)r1[len - 2] >> 30) ^ r1Sign);
+
+                    len -= Convert.ToInt32(check == 0);
+                }
+
+                r0_64 = (long)r0[1] << 32 | r0[0];
+                r1_64 = (long)r1[1] << 32 | r1[0];
+            }
+#else
+            // while lambda <> (0, 0)
+            while (R0.BitLength > 62 || R1.BitLength > 62)
+            {
+                if (R0.TestBit(0)) 
+                {
+                    int uVal = R0.IntValue + (R1.IntValue * tw);
+                    int alphaPos = uVal & pow2Mask;
+
+                    u[uPos] = (sbyte)((uVal << s) >> s);
+                    R0 = R0.Subtract(alpha[alphaPos].u);
+                    R1 = R1.Subtract(alpha[alphaPos].v);
                 }
 
-                ++i;
+                ++uPos;
 
-                BigInteger t = r0.ShiftRight(1);
+                BigInteger t = R0.ShiftRight(1);
                 if (mu == 1)
                 {
-                    r0 = r1.Add(t);
+                    R0 = R1.Add(t);
                 }
                 else // mu == -1
                 {
-                    r0 = r1.Subtract(t);
+                    R0 = R1.Subtract(t);
                 }
-                r1 = t.Negate();
+                R1 = t.Negate();
             }
+
+            r0_64 = R0.LongValueExact;
+            r1_64 = R1.LongValueExact;
+#endif
+
+            // while lambda <> (0, 0)
+            while ((r0_64 | r1_64) != 0L)
+            {
+                if ((r0_64 & 1L) != 0L)
+                {
+                    int uVal = (int)r0_64 + ((int)r1_64 * tw);
+                    int alphaPos = uVal & pow2Mask;
+
+                    u[uPos] = (sbyte)((uVal << s) >> s);
+                    r0_64 -= alphaUs[alphaPos];
+                    r1_64 -= alphaVs[alphaPos];
+                }
+
+                ++uPos;
+
+                long t_64 = r0_64 >> 1;
+                if (mu == 1)
+                {
+                    r0_64 = r1_64 + t_64;
+                }
+                else // mu == -1
+                {
+                    r0_64 = r1_64 - t_64;
+                }
+                r1_64 = -t_64;
+            }
+
             return u;
         }
 
@@ -767,6 +867,7 @@ namespace Org.BouncyCastle.Math.EC.Abc
         */
         public static AbstractF2mPoint[] GetPreComp(AbstractF2mPoint p, sbyte a)
         {
+            AbstractF2mPoint pNeg = (AbstractF2mPoint)p.Negate();
             sbyte[][] alphaTnaf = (a == 0) ? Tnaf.Alpha0Tnaf : Tnaf.Alpha1Tnaf;
 
             AbstractF2mPoint[] pu = new AbstractF2mPoint[(uint)(alphaTnaf.Length + 1) >> 1];
@@ -775,7 +876,7 @@ namespace Org.BouncyCastle.Math.EC.Abc
             int precompLen = alphaTnaf.Length;
             for (uint i = 3; i < precompLen; i += 2)
             {
-                pu[i >> 1] = Tnaf.MultiplyFromTnaf(p, alphaTnaf[i]);
+                pu[i >> 1] = Tnaf.MultiplyFromTnaf(p, pNeg, alphaTnaf[i]);
             }
 
             p.Curve.NormalizeAll(pu);
diff --git a/crypto/src/math/raw/Nat.cs b/crypto/src/math/raw/Nat.cs
index 4600f247f..fa76f305e 100644
--- a/crypto/src/math/raw/Nat.cs
+++ b/crypto/src/math/raw/Nat.cs
@@ -14,7 +14,7 @@ namespace Org.BouncyCastle.Math.Raw
 
         public static uint Add(int len, uint[] x, uint[] y, uint[] z)
         {
-            ulong c = 0;
+            ulong c = 0UL;
             for (int i = 0; i < len; ++i)
             {
                 c += (ulong)x[i] + y[i];
@@ -27,7 +27,7 @@ namespace Org.BouncyCastle.Math.Raw
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
         public static uint Add(int len, ReadOnlySpan<uint> x, ReadOnlySpan<uint> y, Span<uint> z)
         {
-            ulong c = 0;
+            ulong c = 0UL;
             for (int i = 0; i < len; ++i)
             {
                 c += (ulong)x[i] + y[i];
@@ -1398,6 +1398,32 @@ namespace Org.BouncyCastle.Math.Raw
         }
 #endif
 
+        public static int Negate(int len, uint[] x, uint[] z)
+        {
+            long c = 0L;
+            for (int i = 0; i < len; ++i)
+            {
+                c -= x[i];
+                z[i] = (uint)c;
+                c >>= 32;
+            }
+            return (int)c;
+        }
+
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        public static int Negate(int len, ReadOnlySpan<uint> x, Span<uint> z)
+        {
+            long c = 0L;
+            for (int i = 0; i < len; ++i)
+            {
+                c -= x[i];
+                z[i] = (uint)c;
+                c >>= 32;
+            }
+            return (int)c;
+        }
+#endif
+
         public static uint ShiftDownBit(int len, uint[] z, uint c)
         {
             int i = len;
@@ -2610,6 +2636,25 @@ namespace Org.BouncyCastle.Math.Raw
         }
 #endif
 
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        public static int SubInt32From(int len, int x, Span<uint> z)
+        {
+            long c = (long)z[0] - x;
+            z[0] = (uint)c;
+            c >>= 32;
+
+            int i = 1;
+            while (c != 0L && i < len)
+            {
+                c += z[i];
+                z[i++] = (uint)c;
+                c >>= 32;
+            }
+
+            return (int)c;
+        }
+#endif
+
         public static int SubWordAt(int len, uint x, uint[] z, int zPos)
         {
             Debug.Assert(zPos <= (len - 1));
diff --git a/crypto/src/util/BigIntegers.cs b/crypto/src/util/BigIntegers.cs
index e63af7c7c..668d92246 100644
--- a/crypto/src/util/BigIntegers.cs
+++ b/crypto/src/util/BigIntegers.cs
@@ -16,6 +16,22 @@ namespace Org.BouncyCastle.Utilities
 
         private const int MaxIterations = 1000;
 
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        [CLSCompliant(false)]
+        public static void AsUint32ArrayLittleEndian(BigInteger n, Span<uint> buf)
+        {
+            int uintsLength = n.GetLengthofUInt32Array();
+
+            if (uintsLength > buf.Length)
+                throw new ArgumentException("standard length exceeded", nameof(n));
+
+            n.ToUInt32ArrayLittleEndian(buf);
+
+            int sign = (int)buf[uintsLength - 1] >> 31;
+            buf[uintsLength..].Fill((uint)sign);
+        }
+#endif
+
         /**
         * Return the passed in value as an unsigned byte array.
         *