BigInteger improvements

1 files changed, 68 insertions, 92 deletions

diff --git a/crypto/src/math/BigInteger.cs b/crypto/src/math/BigInteger.cs
index caf78843e..53537f0c8 100644
--- a/crypto/src/math/BigInteger.cs
+++ b/crypto/src/math/BigInteger.cs
@@ -3,11 +3,11 @@ using System.Collections.Generic;
 using System.Diagnostics;
 using System.Globalization;
 #if NETCOREAPP3_0_OR_GREATER
-using System.Runtime.Intrinsics.X86;
+using System.Numerics;
 #endif
 using System.Runtime.Serialization;
 using System.Text;
-using Org.BouncyCastle.Crypto.Prng;
+using Org.BouncyCastle.Crypto.Utilities;
 using Org.BouncyCastle.Security;
 using Org.BouncyCastle.Utilities;
 
@@ -15,6 +15,7 @@ namespace Org.BouncyCastle.Math
 {
     [Serializable]
     public sealed class BigInteger
+        : IComparable<BigInteger>, IEquatable<BigInteger>
     {
         // The first few odd primes
         /*
@@ -139,6 +140,7 @@ namespace Org.BouncyCastle.Math
         public static readonly BigInteger Four;
         public static readonly BigInteger Ten;
 
+#if !NETCOREAPP3_0_OR_GREATER
         private readonly static byte[] BitLengthTable =
         {
             0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
@@ -158,6 +160,7 @@ namespace Org.BouncyCastle.Math
             8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
             8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
         };
+#endif
 
         // TODO Parse radix-2 64 bits at a time and radix-8 63 bits at a time
         private const int chunk2 = 1, chunk8 = 1, chunk10 = 19, chunk16 = 16;
@@ -224,15 +227,12 @@ namespace Org.BouncyCastle.Math
         private int nBits = -1; // cache BitCount() value
         [NonSerialized]
         private int nBitLength = -1; // cache BitLength() value
-        [NonSerialized]
-        private int mQuote = 0; // -m^(-1) mod b, b = 2^32 (see Montgomery mult.), 0 when uninitialised
 
         [OnDeserialized]
         private void OnDeserialized(StreamingContext context)
         {
             this.nBits = -1;
             this.nBitLength = -1;
-            this.mQuote = 0;
         }
 
         private static int GetByteLength(int nBits)
@@ -778,7 +778,6 @@ namespace Org.BouncyCastle.Math
 
                 this.magnitude = MakeMagnitude(b);
                 this.nBits = -1;
-                this.mQuote = 0;
 
                 if (certainty < 1)
                     break;
@@ -979,12 +978,8 @@ namespace Org.BouncyCastle.Math
         public static int BitCnt(int i)
         {
 #if NETCOREAPP3_0_OR_GREATER
-            if (Popcnt.IsSupported)
-            {
-                return (int)Popcnt.PopCount((uint)i);
-            }
-#endif
-
+            return BitOperations.PopCount((uint)i);
+#else
             uint u = (uint)i;
             u = u - ((u >> 1) & 0x55555555);
             u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
@@ -993,6 +988,7 @@ namespace Org.BouncyCastle.Math
             u += (u >> 16);
             u &= 0x3f;
             return (int)u;
+#endif
         }
 
         private static int CalcBitLength(int sign, int indx, int[]	mag)
@@ -1047,18 +1043,20 @@ namespace Org.BouncyCastle.Math
             }
         }
 
-        //
-        // BitLen(value) is the number of bits in value.
-        //
-        private static int BitLen(int w)
+        private static int BitLen(byte b)
         {
 #if NETCOREAPP3_0_OR_GREATER
-            if (Lzcnt.IsSupported)
-            {
-                return 32 - (int)Lzcnt.LeadingZeroCount((uint)w);
-            }
+            return 32 - BitOperations.LeadingZeroCount((uint)b);
+#else
+            return BitLengthTable[b];
 #endif
+        }
 
+        private static int BitLen(int w)
+        {
+#if NETCOREAPP3_0_OR_GREATER
+            return 32 - BitOperations.LeadingZeroCount((uint)w);
+#else
             uint v = (uint)w;
             uint t = v >> 24;
             if (t != 0)
@@ -1070,6 +1068,7 @@ namespace Org.BouncyCastle.Math
             if (t != 0)
                 return 8 + BitLengthTable[t];
             return BitLengthTable[v];
+#endif
         }
 
         private bool QuickPow2Check()
@@ -1077,10 +1076,18 @@ namespace Org.BouncyCastle.Math
             return sign > 0 && nBits == 1;
         }
 
-        public int CompareTo(
-            object obj)
+        public int CompareTo(BigInteger other)
         {
-            return CompareTo((BigInteger)obj);
+            if (other == null)
+                return 1;
+
+            return sign < other.sign
+                ?  -1
+                :  sign > other.sign
+                ?  1
+                :  sign == 0
+                ?  0
+                :  sign * CompareNoLeadingZeroes(0, magnitude, 0, other.magnitude);
         }
 
         /**
@@ -1133,15 +1140,6 @@ namespace Org.BouncyCastle.Math
             return 0;
         }
 
-        public int CompareTo(
-            BigInteger value)
-        {
-            return sign < value.sign ? -1
-                : sign > value.sign ? 1
-                : sign == 0 ? 0
-                : sign * CompareNoLeadingZeroes(0, magnitude, 0, value.magnitude);
-        }
-
         /**
          * return z = x / y - done in place (z value preserved, x contains the
          * remainder)
@@ -1332,19 +1330,26 @@ namespace Org.BouncyCastle.Math
             return biggies;
         }
 
-        public override bool Equals(
-            object obj)
+        public override bool Equals(object obj)
         {
             if (obj == this)
                 return true;
-
-            BigInteger biggie = obj as BigInteger;
-            if (biggie == null)
+            if (!(obj is BigInteger biggie))
                 return false;
 
             return sign == biggie.sign && IsEqualMagnitude(biggie);
         }
 
+        public bool Equals(BigInteger other)
+        {
+            if (other == this)
+                return true;
+            if (other == null)
+                return false;
+
+            return sign == other.sign && IsEqualMagnitude(other);
+        }
+
         private bool IsEqualMagnitude(BigInteger x)
         {
             int[] xMag = x.magnitude;
@@ -1754,7 +1759,7 @@ namespace Org.BouncyCastle.Math
 //					if (F.Equals(One))
 //					{
 //						BigInteger half = m.Add(One).ShiftRight(1);
-//						BigInteger halfK = half.ModPow(BigInteger.ValueOf(k), m);
+//						BigInteger halfK = half.ModPow(ValueOf(k), m);
 //						return B.Multiply(halfK).Mod(m);
 //					}
 //
@@ -1801,13 +1806,13 @@ namespace Org.BouncyCastle.Math
 
             int pow = m.BitLength - 1;
 
-            long inv64 = ModInverse64(LongValue);
+            long inv64 = (long)Raw.Mod.Inverse64((ulong)LongValue);
             if (pow < 64)
             {
                 inv64 &= ((1L << pow) - 1);
             }
 
-            BigInteger x = BigInteger.ValueOf(inv64);
+            BigInteger x = ValueOf(inv64);
 
             if (pow > 64)
             {
@@ -1831,33 +1836,6 @@ namespace Org.BouncyCastle.Math
             return x;
         }
 
-        private static int ModInverse32(int d)
-        {
-            // Newton's method with initial estimate "correct to 4 bits"
-            Debug.Assert((d & 1) != 0);
-            int x = d + (((d + 1) & 4) << 1);   // d.x == 1 mod 2**4
-            Debug.Assert(((d * x) & 15) == 1);
-            x *= 2 - d * x;                     // d.x == 1 mod 2**8
-            x *= 2 - d * x;                     // d.x == 1 mod 2**16
-            x *= 2 - d * x;                     // d.x == 1 mod 2**32
-            Debug.Assert(d * x == 1);
-            return x;
-        }
-
-        private static long ModInverse64(long d)
-        {
-            // Newton's method with initial estimate "correct to 4 bits"
-            Debug.Assert((d & 1L) != 0);
-            long x = d + (((d + 1L) & 4L) << 1);    // d.x == 1 mod 2**4
-            Debug.Assert(((d * x) & 15L) == 1L);
-            x *= 2 - d * x;                         // d.x == 1 mod 2**8
-            x *= 2 - d * x;                         // d.x == 1 mod 2**16
-            x *= 2 - d * x;                         // d.x == 1 mod 2**32
-            x *= 2 - d * x;                         // d.x == 1 mod 2**64
-            Debug.Assert(d * x == 1L);
-            return x;
-        }
-
         /**
          * Calculate the numbers u1, u2, and u3 such that:
          *
@@ -1991,7 +1969,7 @@ namespace Org.BouncyCastle.Math
             {
                 mult = window & 0xFF;
 
-                int bits = lastZeroes + BitLengthTable[mult];
+                int bits = lastZeroes + BitLen((byte)mult);
                 for (int j = 0; j < bits; ++j)
                 {
                     y = ReduceBarrett(y.Square(), m, mr, yu);
@@ -2116,7 +2094,7 @@ namespace Org.BouncyCastle.Math
             {
                 mult = window & 0xFF;
 
-                int bits = lastZeroes + BitLengthTable[mult];
+                int bits = lastZeroes + BitLen((byte)mult);
                 for (int j = 0; j < bits; ++j)
                 {
                     SquareMonty(yAccum, yVal, m.magnitude, mDash, smallMontyModulus);
@@ -2201,11 +2179,19 @@ namespace Org.BouncyCastle.Math
 
         private static int CreateWindowEntry(int mult, int zeroes)
         {
+            Debug.Assert(mult > 0);
+
+#if NETCOREAPP3_0_OR_GREATER
+            int tz = BitOperations.TrailingZeroCount(mult);
+            mult >>= tz;
+            zeroes += tz;
+#else
             while ((mult & 1) == 0)
             {
                 mult >>= 1;
                 ++zeroes;
             }
+#endif
 
             return mult | (zeroes << 8);
         }
@@ -2324,18 +2310,13 @@ namespace Org.BouncyCastle.Math
          */
         private int GetMQuote()
         {
-            if (mQuote != 0)
-            {
-                return mQuote; // already calculated
-            }
-
             Debug.Assert(this.sign > 0);
 
             int d = -magnitude[magnitude.Length - 1];
 
             Debug.Assert((d & 1) != 0);
 
-            return mQuote = ModInverse32(d);
+            return (int)Raw.Mod.Inverse32((uint)d);
         }
 
         private static void MontgomeryReduce(int[] x, int[] m, uint mDash) // mDash = -m^(-1) mod b
@@ -3246,10 +3227,8 @@ namespace Org.BouncyCastle.Math
                 while (magIndex > 1)
                 {
                     uint mag = (uint) magnitude[--magIndex];
-                    bytes[--bytesIndex] = (byte) mag;
-                    bytes[--bytesIndex] = (byte)(mag >> 8);
-                    bytes[--bytesIndex] = (byte)(mag >> 16);
-                    bytes[--bytesIndex] = (byte)(mag >> 24);
+                    bytesIndex -= 4;
+                    Pack.UInt32_To_BE(mag, bytes, bytesIndex);
                 }
 
                 uint lastMag = (uint) magnitude[0];
@@ -3274,10 +3253,8 @@ namespace Org.BouncyCastle.Math
                         carry = (++mag == uint.MinValue);
                     }
 
-                    bytes[--bytesIndex] = (byte) mag;
-                    bytes[--bytesIndex] = (byte)(mag >> 8);
-                    bytes[--bytesIndex] = (byte)(mag >> 16);
-                    bytes[--bytesIndex] = (byte)(mag >> 24);
+                    bytesIndex -= 4;
+                    Pack.UInt32_To_BE(mag, bytes, bytesIndex);
                 }
 
                 uint lastMag = (uint) magnitude[0];
@@ -3331,10 +3308,8 @@ namespace Org.BouncyCastle.Math
                 while (magIndex > 1)
                 {
                     uint mag = (uint) magnitude[--magIndex];
-                    output[--bytesIndex] = (byte) mag;
-                    output[--bytesIndex] = (byte)(mag >> 8);
-                    output[--bytesIndex] = (byte)(mag >> 16);
-                    output[--bytesIndex] = (byte)(mag >> 24);
+                    bytesIndex -= 4;
+                    Pack.UInt32_To_BE(mag, output[bytesIndex..]);
                 }
 
                 uint lastMag = (uint)magnitude[0];
@@ -3359,10 +3334,8 @@ namespace Org.BouncyCastle.Math
                         carry = (++mag == uint.MinValue);
                     }
 
-                    output[--bytesIndex] = (byte) mag;
-                    output[--bytesIndex] = (byte)(mag >> 8);
-                    output[--bytesIndex] = (byte)(mag >> 16);
-                    output[--bytesIndex] = (byte)(mag >> 24);
+                    bytesIndex -= 4;
+                    Pack.UInt32_To_BE(mag, output[bytesIndex..]);
                 }
 
                 uint lastMag = (uint)magnitude[0];
@@ -3613,6 +3586,9 @@ namespace Org.BouncyCastle.Math
                 offset += 32;
             }
 
+#if NETCOREAPP3_0_OR_GREATER
+            offset += BitOperations.TrailingZeroCount(word);
+#else
             while ((word & 0xFF) == 0)
             {
                 word >>= 8;
@@ -3625,6 +3601,7 @@ namespace Org.BouncyCastle.Math
                 ++offset;
             }
 
+#endif
             return offset;
         }
 
@@ -3816,7 +3793,6 @@ namespace Org.BouncyCastle.Math
 
             int[] mag = (int[]) this.magnitude.Clone();
             mag[mag.Length - 1 - (n >> 5)] ^= (1 << (n & 31)); // Flip bit
-            //mag[mag.Length - 1 - (n / 32)] ^= (1 << (n % 32));
             return new BigInteger(this.sign, mag, false);
         }
     }