Refactoring in BigInteger Monty code

1 files changed, 89 insertions, 59 deletions

diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs
index d61d702c1..42b5b5089 100644
--- a/crypto/src/math/BigInteger.cs
+++ b/crypto/src/math/BigInteger.cs
@@ -1180,7 +1180,7 @@ namespace Org.BouncyCastle.Math
                 ?  1
                 :  sign == 0
                 ?  0
-                :  sign * CompareNoLeadingZeroes(0, magnitude, 0, other.magnitude);
+                :  sign * CompareNoLeadingZeros(0, magnitude, 0, other.magnitude);
         }
 
         /**
@@ -1199,10 +1199,10 @@ namespace Org.BouncyCastle.Math
                 yIndx++;
             }
 
-            return CompareNoLeadingZeroes(xIndx, x, yIndx, y);
+            return CompareNoLeadingZeros(xIndx, x, yIndx, y);
         }
 
-        private static int CompareNoLeadingZeroes(int xIndx, uint[] x, int yIndx, uint[] y)
+        private static int CompareNoLeadingZeros(int xIndx, uint[] x, int yIndx, uint[] y)
         {
             int diff = (x.Length - y.Length) - (xIndx - yIndx);
 
@@ -1243,7 +1243,7 @@ namespace Org.BouncyCastle.Math
 
             Debug.Assert(yStart < y.Length);
 
-            int xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
+            int xyCmp = CompareNoLeadingZeros(xStart, x, yStart, y);
             uint[] count;
 
             if (xyCmp > 0)
@@ -1280,7 +1280,7 @@ namespace Org.BouncyCastle.Math
                 for (;;)
                 {
                     if (cBitLength < xBitLength
-                        || CompareNoLeadingZeroes(xStart, x, cStart, c) >= 0)
+                        || CompareNoLeadingZeros(xStart, x, cStart, c) >= 0)
                     {
                         Subtract(xStart, x, cStart, c);
                         AddMagnitudes(count, iCount);
@@ -1298,7 +1298,7 @@ namespace Org.BouncyCastle.Math
                             if (xBitLength < yBitLength)
                                 return count;
 
-                            xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
+                            xyCmp = CompareNoLeadingZeros(xStart, x, yStart, y);
 
                             if (xyCmp <= 0)
                                 break;
@@ -1632,6 +1632,8 @@ namespace Org.BouncyCastle.Math
             BigInteger montRadix = One.ShiftLeft(32 * n.magnitude.Length).Remainder(n);
             BigInteger minusMontRadix = n.Subtract(montRadix);
 
+            uint[] yAccum = new uint[n.magnitude.Length + 1];
+
             do
             {
                 BigInteger a;
@@ -1642,7 +1644,7 @@ namespace Org.BouncyCastle.Math
                 while (a.sign == 0 || a.CompareTo(n) >= 0
                     || a.IsEqualMagnitude(montRadix) || a.IsEqualMagnitude(minusMontRadix));
 
-                BigInteger y = ModPowMonty(a, r, n, false);
+                BigInteger y = ModPowMonty(yAccum, a, r, n, false);
 
                 if (!y.Equals(montRadix))
                 {
@@ -1652,7 +1654,7 @@ namespace Org.BouncyCastle.Math
                         if (++j == s)
                             return false;
 
-                        y = ModPowMonty(y, Two, n, false);
+                        y = ModSquareMonty(yAccum, y, n);
 
                         if (y.Equals(montRadix))
                             return false;
@@ -1734,12 +1736,12 @@ namespace Org.BouncyCastle.Math
 //				for (;;)
 //				{
 //					// While F is even, do F=F/u, C=C*u, k=k+1.
-//					int zeroes = F.GetLowestSetBit();
-//					if (zeroes > 0)
+//					int zeros = F.GetLowestSetBit();
+//					if (zeros > 0)
 //					{
-//						F = F.ShiftRight(zeroes);
-//						C = C.ShiftLeft(zeroes);
-//						k += zeroes;
+//						F = F.ShiftRight(zeros);
+//						C = C.ShiftLeft(zeros);
+//						k += zeros;
 //					}
 //
 //					// If F = 1, then return B,k.
@@ -1900,7 +1902,8 @@ namespace Org.BouncyCastle.Math
                 }
                 else
                 {
-                    result = ModPowMonty(result, e, m, true);
+                    uint[] yAccum = new uint[m.magnitude.Length + 1];
+                    result = ModPowMonty(yAccum, result, e, m, true);
                 }
             }
 
@@ -1934,17 +1937,17 @@ namespace Org.BouncyCastle.Math
                 oddPowers[i] = ReduceBarrett(oddPowers[i - 1].Multiply(b2), m, mr, yu);
             }
 
-            int[] windowList = GetWindowList(e.magnitude, extraBits);
+            uint[] windowList = GetWindowList(e.magnitude, extraBits);
             Debug.Assert(windowList.Length > 0);
 
-            int window = windowList[0];
-            int mult = window & 0xFF, lastZeroes = window >> 8;
+            uint window = windowList[0];
+            uint mult = window & 0xFFU, lastZeros = window >> 8;
 
             BigInteger y;
             if (mult == 1)
             {
                 y = b2;
-                --lastZeroes;
+                --lastZeros;
             }
             else
             {
@@ -1952,11 +1955,11 @@ namespace Org.BouncyCastle.Math
             }
 
             int windowPos = 1;
-            while ((window = windowList[windowPos++]) != -1)
+            while ((window = windowList[windowPos++]) != uint.MaxValue)
             {
                 mult = window & 0xFF;
 
-                int bits = lastZeroes + BitLen((byte)mult);
+                int bits = (int)lastZeros + BitLen((byte)mult);
                 for (int j = 0; j < bits; ++j)
                 {
                     y = ReduceBarrett(y.Square(), m, mr, yu);
@@ -1964,10 +1967,10 @@ namespace Org.BouncyCastle.Math
 
                 y = ReduceBarrett(y.Multiply(oddPowers[mult >> 1]), m, mr, yu);
 
-                lastZeroes = window >> 8;
+                lastZeros = window >> 8;
             }
 
-            for (int i = 0; i < lastZeroes; ++i)
+            for (int i = 0; i < lastZeros; ++i)
             {
                 y = ReduceBarrett(y.Square(), m, mr, yu);
             }
@@ -2008,7 +2011,7 @@ namespace Org.BouncyCastle.Math
             return x;
         }
 
-        private static BigInteger ModPowMonty(BigInteger b, BigInteger e, BigInteger m, bool convert)
+        private static BigInteger ModPowMonty(uint[] yAccum, BigInteger b, BigInteger e, BigInteger m, bool convert)
         {
             int n = m.magnitude.Length;
             int powR = 32 * n;
@@ -2021,7 +2024,7 @@ namespace Org.BouncyCastle.Math
                 b = b.ShiftLeft(powR).Remainder(m);
             }
 
-            uint[] yAccum = new uint[n + 1];
+            Debug.Assert(yAccum.Length == n + 1);
 
             uint[] zVal = b.magnitude;
             Debug.Assert(zVal.Length <= n);
@@ -2059,17 +2062,17 @@ namespace Org.BouncyCastle.Math
                 MultiplyMonty(yAccum, oddPowers[i], zSquared, m.magnitude, mDash, smallMontyModulus);
             }
 
-            int[] windowList = GetWindowList(e.magnitude, extraBits);
+            uint[] windowList = GetWindowList(e.magnitude, extraBits);
             Debug.Assert(windowList.Length > 1);
 
-            int window = windowList[0];
-            int mult = window & 0xFF, lastZeroes = window >> 8;
+            uint window = windowList[0];
+            uint mult = window & 0xFF, lastZeros = window >> 8;
 
             uint[] yVal;
             if (mult == 1)
             {
                 yVal = zSquared;
-                --lastZeroes;
+                --lastZeros;
             }
             else
             {
@@ -2077,11 +2080,11 @@ namespace Org.BouncyCastle.Math
             }
 
             int windowPos = 1;
-            while ((window = windowList[windowPos++]) != -1)
+            while ((window = windowList[windowPos++]) != uint.MaxValue)
             {
                 mult = window & 0xFF;
 
-                int bits = lastZeroes + BitLen((byte)mult);
+                int bits = (int)lastZeros + BitLen((byte)mult);
                 for (int j = 0; j < bits; ++j)
                 {
                     SquareMonty(yAccum, yVal, m.magnitude, mDash, smallMontyModulus);
@@ -2089,10 +2092,10 @@ namespace Org.BouncyCastle.Math
 
                 MultiplyMonty(yAccum, yVal, oddPowers[mult >> 1], m.magnitude, mDash, smallMontyModulus);
 
-                lastZeroes = window >> 8;
+                lastZeros = window >> 8;
             }
 
-            for (int i = 0; i < lastZeroes; ++i)
+            for (int i = 0; i < lastZeros; ++i)
             {
                 SquareMonty(yAccum, yVal, m.magnitude, mDash, smallMontyModulus);
             }
@@ -2110,22 +2113,49 @@ namespace Org.BouncyCastle.Math
             return new BigInteger(1, yVal, true);
         }
 
-        private static int[] GetWindowList(uint[] mag, int extraBits)
+        private static BigInteger ModSquareMonty(uint[] yAccum, BigInteger b, BigInteger m)
+        {
+            int n = m.magnitude.Length;
+            int powR = 32 * n;
+            bool smallMontyModulus = m.BitLength + 2 <= powR;
+            uint mDash = m.GetMQuote();
+
+            Debug.Assert(yAccum.Length == n + 1);
+
+            uint[] zVal = b.magnitude;
+            Debug.Assert(zVal.Length <= n);
+
+            uint[] yVal = new uint[n];
+            zVal.CopyTo(yVal, n - zVal.Length);
+
+            SquareMonty(yAccum, yVal, m.magnitude, mDash, smallMontyModulus);
+
+            if (smallMontyModulus && CompareTo(0, yVal, 0, m.magnitude) >= 0)
+            {
+                Subtract(0, yVal, 0, m.magnitude);
+            }
+
+            return new BigInteger(1, yVal, true);
+        }
+
+        private static uint[] GetWindowList(uint[] mag, int extraBits)
         {
-            int v = (int)mag[0];
-            Debug.Assert(v != 0);
+            uint v = mag[0];
+            Debug.Assert(v != 0U);
 
-            int leadingBits = BitLen((uint)v);
+            int leadingBits = BitLen(v);
+            int totalBits = ((mag.Length - 1) << 5) + leadingBits;
 
-            int resultSize = (((mag.Length - 1) << 5) + leadingBits) / (1 + extraBits) + 2;
-            int[] result = new int[resultSize];
+            int resultSize = (totalBits + extraBits) / (1 + extraBits) + 1;
+            uint[] result = new uint[resultSize];
             int resultPos = 0;
 
             int bitPos = 33 - leadingBits;
             v <<= bitPos;
 
-            int mult = 1, multLimit = 1 << extraBits;
-            int zeroes = 0;
+            uint mult = 1U;
+            uint multLimit = 1U << extraBits;
+            uint zeros = 0U;
 
             int i = 0;
             for (;;)
@@ -2134,17 +2164,17 @@ namespace Org.BouncyCastle.Math
                 {
                     if (mult < multLimit)
                     {
-                        mult = (mult << 1) | (int)((uint)v >> 31);
+                        mult = (mult << 1) | (v >> 31);
                     }
-                    else if (v < 0)
+                    else if ((int)v < 0)
                     {
-                        result[resultPos++] = CreateWindowEntry(mult, zeroes);
-                        mult = 1;
-                        zeroes = 0;
+                        result[resultPos++] = CreateWindowEntry(mult, zeros);
+                        mult = 1U;
+                        zeros = 0U;
                     }
                     else
                     {
-                        ++zeroes;
+                        ++zeros;
                     }
 
                     v <<= 1;
@@ -2152,35 +2182,35 @@ namespace Org.BouncyCastle.Math
 
                 if (++i == mag.Length)
                 {
-                    result[resultPos++] = CreateWindowEntry(mult, zeroes);
+                    result[resultPos++] = CreateWindowEntry(mult, zeros);
                     break;
                 }
 
-                v = (int)mag[i];
+                v = mag[i];
                 bitPos = 0;
             }
 
-            result[resultPos] = -1;
+            result[resultPos] = uint.MaxValue; // Sentinel value
             return result;
         }
 
-        private static int CreateWindowEntry(int mult, int zeroes)
+        private static uint CreateWindowEntry(uint mult, uint zeros)
         {
             Debug.Assert(mult > 0);
 
 #if NETCOREAPP3_0_OR_GREATER
             int tz = BitOperations.TrailingZeroCount(mult);
             mult >>= tz;
-            zeroes += tz;
+            zeros += (uint)tz;
 #else
-            while ((mult & 1) == 0)
+            while ((mult & 1U) == 0U)
             {
                 mult >>= 1;
-                ++zeroes;
+                ++zeros;
             }
 #endif
 
-            return mult | (zeroes << 8);
+            return mult | (zeros << 8);
         }
 
         /**
@@ -2691,7 +2721,7 @@ namespace Org.BouncyCastle.Math
 
             Debug.Assert(yStart < y.Length);
 
-            int xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
+            int xyCmp = CompareNoLeadingZeros(xStart, x, yStart, y);
 
             if (xyCmp > 0)
             {
@@ -2718,7 +2748,7 @@ namespace Org.BouncyCastle.Math
                 for (;;)
                 {
                     if (cBitLength < xBitLength
-                        || CompareNoLeadingZeroes(xStart, x, cStart, c) >= 0)
+                        || CompareNoLeadingZeros(xStart, x, cStart, c) >= 0)
                     {
                         Subtract(xStart, x, cStart, c);
 
@@ -2735,7 +2765,7 @@ namespace Org.BouncyCastle.Math
                             if (xBitLength < yBitLength)
                                 return x;
 
-                            xyCmp = CompareNoLeadingZeroes(xStart, x, yStart, y);
+                            xyCmp = CompareNoLeadingZeros(xStart, x, yStart, y);
 
                             if (xyCmp <= 0)
                                 break;
@@ -2808,7 +2838,7 @@ namespace Org.BouncyCastle.Math
                 }
             }
 
-            if (CompareNoLeadingZeroes(0, magnitude, 0, n.magnitude) < 0)
+            if (CompareNoLeadingZeros(0, magnitude, 0, n.magnitude) < 0)
                 return this;
 
             uint[] result;
@@ -3103,7 +3133,7 @@ namespace Org.BouncyCastle.Math
             if (this.sign != n.sign)
                 return Add(n.Negate());
 
-            int compare = CompareNoLeadingZeroes(0, magnitude, 0, n.magnitude);
+            int compare = CompareNoLeadingZeros(0, magnitude, 0, n.magnitude);
             if (compare == 0)
                 return Zero;