Refactoring around Math.Raw.Mod

3 files changed, 78 insertions, 45 deletions

diff --git a/crypto/src/math/raw/Mod.cs b/crypto/src/math/raw/Mod.cs
index 20f445154..bc5942711 100644
--- a/crypto/src/math/raw/Mod.cs
+++ b/crypto/src/math/raw/Mod.cs
@@ -17,6 +17,8 @@ namespace Org.BouncyCastle.Math.Raw
         private const int M30 = 0x3FFFFFFF;
         private const ulong M32UL = 0xFFFFFFFFUL;
 
+        private static readonly int MaxStackAlloc = Platform.Is64BitProcess ? 4096 : 1024;
+
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
         public static void CheckedModOddInverse(ReadOnlySpan<uint> m, ReadOnlySpan<uint> x, Span<uint> z)
 #else
@@ -125,9 +127,10 @@ namespace Org.BouncyCastle.Math.Raw
             int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]);
             int len30 = (bits + 29) / 30;
 
-            Span<int> alloc = len30 <= 50
-                ? stackalloc int[len30 * 5]
-                : new int[len30 * 5];
+            int allocSize = len30 * 5;
+            Span<int> alloc = (allocSize * Integers.NumBytes <= MaxStackAlloc)
+                ? stackalloc int[allocSize]
+                : new int[allocSize];
 
             Span<int> t = stackalloc int[4];
             Span<int> D = alloc[..len30]; alloc = alloc[len30..];
@@ -189,11 +192,11 @@ namespace Org.BouncyCastle.Math.Raw
             Encode30(bits, m, 0, M, 0);
             Array.Copy(M, 0, F, 0, len30);
 
-            int clzG = Integers.NumberOfLeadingZeros(G[len30 - 1] | 1) - (len30 * 30 + 2 - bits);
-            int eta = -1 - clzG;
+            int clz = System.Math.Max(0, bits - 1 - Nat.GetBitLength(len32, x));
+            int eta = -1 - clz;
             int lenDE = len30, lenFG = len30;
             int m0Inv32 = (int)Inverse32((uint)M[0]);
-            int maxDivsteps = GetMaximumDivsteps(bits);
+            int maxDivsteps = GetMaximumDivsteps(bits) - clz;
 
             int divsteps = 0;
             while (!EqualToZeroVar_Unlikely(lenFG, G))
@@ -206,20 +209,7 @@ namespace Org.BouncyCastle.Math.Raw
                 eta = Divsteps30Var(eta, F[0], G[0], t);
                 UpdateDE30(lenDE, D, E, t, m0Inv32, M);
                 UpdateFG30(lenFG, F, G, t);
-
-                int fn = F[lenFG - 1];
-                int gn = G[lenFG - 1];
-
-                int cond = (lenFG - 2) >> 31;
-                cond |= fn ^ (fn >> 31);
-                cond |= gn ^ (gn >> 31);
-
-                if (cond == 0)
-                {
-                    F[lenFG - 2] |= fn << 30;
-                    G[lenFG - 2] |= gn << 30;
-                    --lenFG;
-                }
+                lenFG = TrimFG30Var(lenFG, F, G);
             }
 
             int signF = F[lenFG - 1] >> 31;
@@ -268,9 +258,10 @@ namespace Org.BouncyCastle.Math.Raw
             int bits = (len32 << 5) - Integers.NumberOfLeadingZeros((int)m[len32 - 1]);
             int len30 = (bits + 29) / 30;
 
-            Span<int> alloc = len30 <= 50
-                ? stackalloc int[len30 * 5]
-                : new int[len30 * 5];
+            int allocSize = len30 * 5;
+            Span<int> alloc = (allocSize * Integers.NumBytes <= MaxStackAlloc)
+                ? stackalloc int[allocSize]
+                : new int[allocSize];
 
             Span<int> t = stackalloc int[4];
             Span<int> D = alloc[..len30]; alloc = alloc[len30..];
@@ -284,11 +275,11 @@ namespace Org.BouncyCastle.Math.Raw
             Encode30(bits, m, M);
             M.CopyTo(F);
 
-            int clzG = Integers.NumberOfLeadingZeros(G[len30 - 1] | 1) - (len30 * 30 + 2 - bits);
-            int eta = -1 - clzG;
+            int clz = System.Math.Max(0, bits - 1 - Nat.GetBitLength(len32, x));
+            int eta = -1 - clz;
             int lenDE = len30, lenFG = len30;
             int m0Inv32 = (int)Inverse32((uint)M[0]);
-            int maxDivsteps = GetMaximumDivsteps(bits);
+            int maxDivsteps = GetMaximumDivsteps(bits) - clz;
 
             int divsteps = 0;
             while (!EqualToZeroVar_Unlikely(lenFG, G))
@@ -301,20 +292,7 @@ namespace Org.BouncyCastle.Math.Raw
                 eta = Divsteps30Var(eta, F[0], G[0], t);
                 UpdateDE30(lenDE, D, E, t, m0Inv32, M);
                 UpdateFG30(lenFG, F, G, t);
-
-                int fn = F[lenFG - 1];
-                int gn = G[lenFG - 1];
-
-                int cond = (lenFG - 2) >> 31;
-                cond |= fn ^ (fn >> 31);
-                cond |= gn ^ (gn >> 31);
-
-                if (cond == 0)
-                {
-                    F[lenFG - 2] |= fn << 30;
-                    G[lenFG - 2] |= gn << 30;
-                    --lenFG;
-                }
+                lenFG = TrimFG30Var(lenFG, F, G);
             }
 
             int signF = F[lenFG - 1] >> 31;
@@ -392,9 +370,10 @@ namespace Org.BouncyCastle.Math.Raw
             m |= m >> 8;
             m |= m >> 16;
 
-            Span<byte> bytes = len <= 256
-                ? stackalloc byte[len << 2]
-                : new byte[len << 2];
+            int allocSize = len * Integers.NumBytes;
+            Span<byte> bytes = allocSize <= MaxStackAlloc
+                ? stackalloc byte[allocSize]
+                : new byte[allocSize];
 
             do
             {
@@ -784,6 +763,33 @@ namespace Org.BouncyCastle.Math.Raw
         }
 
 #if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        private static int TrimFG30Var(int len30, Span<int> F, Span<int> G)
+#else
+        private static int TrimFG30Var(int len30, int[] F, int[] G)
+#endif
+        {
+            Debug.Assert(len30 > 0);
+            Debug.Assert(F.Length >= len30);
+            Debug.Assert(G.Length >= len30);
+
+            int fn = F[len30 - 1];
+            int gn = G[len30 - 1];
+
+            int cond = (len30 - 2) >> 31;
+            cond |= fn ^ (fn >> 31);
+            cond |= gn ^ (gn >> 31);
+
+            if (cond == 0)
+            {
+                F[len30 - 2] |= fn << 30;
+                G[len30 - 2] |= gn << 30;
+                --len30;
+            }
+
+            return len30;
+        }
+
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
         private static void UpdateDE30(int len30, Span<int> D, Span<int> E, ReadOnlySpan<int> t, int m0Inv32,
             ReadOnlySpan<int> M)
 #else
diff --git a/crypto/src/math/raw/Nat.cs b/crypto/src/math/raw/Nat.cs
index 0f53b1a8b..80ea6d7ce 100644
--- a/crypto/src/math/raw/Nat.cs
+++ b/crypto/src/math/raw/Nat.cs
@@ -6,6 +6,7 @@ using System.Runtime.InteropServices;
 #endif
 
 using Org.BouncyCastle.Crypto.Utilities;
+using Org.BouncyCastle.Utilities;
 
 namespace Org.BouncyCastle.Math.Raw
 {
@@ -954,6 +955,32 @@ namespace Org.BouncyCastle.Math.Raw
         }
 #endif
 
+#if NETCOREAPP2_1_OR_GREATER || NETSTANDARD2_1_OR_GREATER
+        public static int GetBitLength(int len, ReadOnlySpan<uint> x)
+#else
+        public static int GetBitLength(int len, uint[] x)
+#endif
+        {
+            for (int i = len - 1; i >= 0; --i)
+            {
+                uint x_i = x[i];
+                if (x_i != 0)
+                    return i * 32 + 32 - Integers.NumberOfLeadingZeros((int)x_i);
+            }
+            return 0;
+        }
+
+        public static int GetBitLength(int len, uint[] x, int xOff)
+        {
+            for (int i = len - 1; i >= 0; --i)
+            {
+                uint x_i = x[xOff + i];
+                if (x_i != 0)
+                    return i * 32 + 32 - Integers.NumberOfLeadingZeros((int)x_i);
+            }
+            return 0;
+        }
+
         public static int GetLengthForBits(int bits)
         {
             if (bits < 1)
diff --git a/crypto/src/util/BigIntegers.cs b/crypto/src/util/BigIntegers.cs
index 9c5477e6a..d1b15f869 100644
--- a/crypto/src/util/BigIntegers.cs
+++ b/crypto/src/util/BigIntegers.cs
@@ -187,7 +187,7 @@ namespace Org.BouncyCastle.Utilities
         public static BigInteger ModOddInverse(BigInteger M, BigInteger X)
         {
             if (!M.TestBit(0))
-                throw new ArgumentException("must be odd", "M");
+                throw new ArgumentException("must be odd", nameof(M));
             if (M.SignValue != 1)
                 throw new ArithmeticException("BigInteger: modulus not positive");
             if (X.SignValue < 0 || X.CompareTo(M) >= 0)
@@ -226,7 +226,7 @@ namespace Org.BouncyCastle.Utilities
         public static BigInteger ModOddInverseVar(BigInteger M, BigInteger X)
         {
             if (!M.TestBit(0))
-                throw new ArgumentException("must be odd", "M");
+                throw new ArgumentException("must be odd", nameof(M));
             if (M.SignValue != 1)
                 throw new ArithmeticException("BigInteger: modulus not positive");
             if (M.Equals(One))