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);
}
}
|
