diff options
Diffstat (limited to 'crypto')
| -rw-r--r-- | crypto/crypto.csproj | 9 | ||||
| -rw-r--r-- | crypto/src/math/ec/ECFieldElement.cs | 36 | ||||
| -rw-r--r-- | crypto/src/math/ec/IntArray.cs | 485 | ||||
| -rw-r--r-- | crypto/src/math/ec/Mod.cs | 115 | ||||
| -rw-r--r-- | crypto/src/math/ec/Nat.cs | 495 |
5 files changed, 643 insertions, 497 deletions
diff --git a/crypto/crypto.csproj b/crypto/crypto.csproj index abc4f6050..dc5c6eff6 100644 --- a/crypto/crypto.csproj +++ b/crypto/crypto.csproj @@ -4649,12 +4649,17 @@ BuildAction = "Compile" /> <File - RelPath = "src\math\ec\IntArray.cs" + RelPath = "src\math\ec\LongArray.cs" SubType = "Code" BuildAction = "Compile" /> <File - RelPath = "src\math\ec\LongArray.cs" + RelPath = "src\math\ec\Mod.cs" + SubType = "Code" + BuildAction = "Compile" + /> + <File + RelPath = "src\math\ec\Nat.cs" SubType = "Code" BuildAction = "Compile" /> diff --git a/crypto/src/math/ec/ECFieldElement.cs b/crypto/src/math/ec/ECFieldElement.cs index f31732aaf..93f63a435 100644 --- a/crypto/src/math/ec/ECFieldElement.cs +++ b/crypto/src/math/ec/ECFieldElement.cs @@ -138,13 +138,7 @@ namespace Org.BouncyCastle.Math.EC public override ECFieldElement Subtract( ECFieldElement b) { - BigInteger x2 = b.ToBigInteger(); - BigInteger x3 = x.Subtract(x2); - if (x3.SignValue < 0) - { - x3 = x3.Add(q); - } - return new FpFieldElement(q, r, x3); + return new FpFieldElement(q, r, ModSubtract(x, b.ToBigInteger())); } public override ECFieldElement Multiply( @@ -156,7 +150,7 @@ namespace Org.BouncyCastle.Math.EC public override ECFieldElement Divide( ECFieldElement b) { - return new FpFieldElement(q, r, ModMult(x, b.ToBigInteger().ModInverse(q))); + return new FpFieldElement(q, r, ModMult(x, ModInverse(b.ToBigInteger()))); } public override ECFieldElement Negate() @@ -172,7 +166,7 @@ namespace Org.BouncyCastle.Math.EC public override ECFieldElement Invert() { // TODO Modular inversion can be faster for a (Generalized) Mersenne Prime. - return new FpFieldElement(q, r, x.ModInverse(q)); + return new FpFieldElement(q, r, ModInverse(x)); } // D.1.4 91 @@ -318,6 +312,18 @@ namespace Org.BouncyCastle.Math.EC return _2x; } + protected virtual BigInteger ModInverse(BigInteger x) + { + // Our BigInteger.ModInverse performance is quite poor, so use the new Nat/Mod classes here + //return x.ModInverse(q); + int len = (FieldSize + 31) >> 5; + uint[] p = Nat.FromBigInteger(len, q); + uint[] n = Nat.FromBigInteger(len, x); + uint[] z = Nat.Create(len); + Mod.Invert(p, n, z); + return Nat.ToBigInteger(len, z); + } + protected virtual BigInteger ModMult(BigInteger x1, BigInteger x2) { return ModReduce(x1.Multiply(x2)); @@ -359,6 +365,16 @@ namespace Org.BouncyCastle.Math.EC return x; } + protected virtual BigInteger ModSubtract(BigInteger x1, BigInteger x2) + { + BigInteger x3 = x1.Subtract(x2); + if (x3.SignValue < 0) + { + x3 = x3.Add(q); + } + return x3; + } + public override bool Equals( object obj) { @@ -1067,7 +1083,7 @@ namespace Org.BouncyCastle.Math.EC public override ECFieldElement Multiply( ECFieldElement b) { - // Right-to-left comb multiplication in the IntArray + // Right-to-left comb multiplication in the LongArray // Input: Binary polynomials a(z) and b(z) of degree at most m-1 // Output: c(z) = a(z) * b(z) mod f(z) diff --git a/crypto/src/math/ec/IntArray.cs b/crypto/src/math/ec/IntArray.cs deleted file mode 100644 index 1089966a8..000000000 --- a/crypto/src/math/ec/IntArray.cs +++ /dev/null @@ -1,485 +0,0 @@ -using System; -using System.Text; - -namespace Org.BouncyCastle.Math.EC -{ - internal class IntArray - { - // TODO make m fixed for the IntArray, and hence compute T once and for all - - // TODO Use uint's internally? - private int[] m_ints; - - public IntArray(int intLen) - { - m_ints = new int[intLen]; - } - - private IntArray(int[] ints) - { - m_ints = ints; - } - - public IntArray(BigInteger bigInt) - : this(bigInt, 0) - { - } - - public IntArray(BigInteger bigInt, int minIntLen) - { - if (bigInt.SignValue == -1) - throw new ArgumentException("Only positive Integers allowed", "bigint"); - - if (bigInt.SignValue == 0) - { - m_ints = new int[] { 0 }; - return; - } - - byte[] barr = bigInt.ToByteArrayUnsigned(); - int barrLen = barr.Length; - - int intLen = (barrLen + 3) / 4; - m_ints = new int[System.Math.Max(intLen, minIntLen)]; - - int rem = barrLen % 4; - int barrI = 0; - - if (0 < rem) - { - int temp = (int) barr[barrI++]; - while (barrI < rem) - { - temp = temp << 8 | (int) barr[barrI++]; - } - m_ints[--intLen] = temp; - } - - while (intLen > 0) - { - int temp = (int) barr[barrI++]; - for (int i = 1; i < 4; i++) - { - temp = temp << 8 | (int) barr[barrI++]; - } - m_ints[--intLen] = temp; - } - } - - public int GetUsedLength() - { - int highestIntPos = m_ints.Length; - - if (highestIntPos < 1) - return 0; - - // Check if first element will act as sentinel - if (m_ints[0] != 0) - { - while (m_ints[--highestIntPos] == 0) - { - } - return highestIntPos + 1; - } - - do - { - if (m_ints[--highestIntPos] != 0) - { - return highestIntPos + 1; - } - } - while (highestIntPos > 0); - - return 0; - } - - public int BitLength - { - get - { - // JDK 1.5: see Integer.numberOfLeadingZeros() - int intLen = GetUsedLength(); - if (intLen == 0) - return 0; - - int last = intLen - 1; - uint highest = (uint) m_ints[last]; - int bits = (last << 5) + 1; - - // A couple of binary search steps - if (highest > 0x0000ffff) - { - if (highest > 0x00ffffff) - { - bits += 24; - highest >>= 24; - } - else - { - bits += 16; - highest >>= 16; - } - } - else if (highest > 0x000000ff) - { - bits += 8; - highest >>= 8; - } - - while (highest > 1) - { - ++bits; - highest >>= 1; - } - - return bits; - } - } - - private int[] resizedInts(int newLen) - { - int[] newInts = new int[newLen]; - int oldLen = m_ints.Length; - int copyLen = oldLen < newLen ? oldLen : newLen; - Array.Copy(m_ints, 0, newInts, 0, copyLen); - return newInts; - } - - public BigInteger ToBigInteger() - { - int usedLen = GetUsedLength(); - if (usedLen == 0) - { - return BigInteger.Zero; - } - - int highestInt = m_ints[usedLen - 1]; - byte[] temp = new byte[4]; - int barrI = 0; - bool trailingZeroBytesDone = false; - for (int j = 3; j >= 0; j--) - { - byte thisByte = (byte)((int)((uint) highestInt >> (8 * j))); - if (trailingZeroBytesDone || (thisByte != 0)) - { - trailingZeroBytesDone = true; - temp[barrI++] = thisByte; - } - } - - int barrLen = 4 * (usedLen - 1) + barrI; - byte[] barr = new byte[barrLen]; - for (int j = 0; j < barrI; j++) - { - barr[j] = temp[j]; - } - // Highest value int is done now - - for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--) - { - for (int j = 3; j >= 0; j--) - { - barr[barrI++] = (byte)((int)((uint)m_ints[iarrJ] >> (8 * j))); - } - } - return new BigInteger(1, barr); - } - - public void ShiftLeft() - { - int usedLen = GetUsedLength(); - if (usedLen == 0) - { - return; - } - if (m_ints[usedLen - 1] < 0) - { - // highest bit of highest used byte is set, so shifting left will - // make the IntArray one byte longer - usedLen++; - if (usedLen > m_ints.Length) - { - // make the m_ints one byte longer, because we need one more - // byte which is not available in m_ints - m_ints = resizedInts(m_ints.Length + 1); - } - } - - bool carry = false; - for (int i = 0; i < usedLen; i++) - { - // nextCarry is true if highest bit is set - bool nextCarry = m_ints[i] < 0; - m_ints[i] <<= 1; - if (carry) - { - // set lowest bit - m_ints[i] |= 1; - } - carry = nextCarry; - } - } - - public IntArray ShiftLeft(int n) - { - int usedLen = GetUsedLength(); - if (usedLen == 0) - { - return this; - } - - if (n == 0) - { - return this; - } - - if (n > 31) - { - throw new ArgumentException("shiftLeft() for max 31 bits " - + ", " + n + "bit shift is not possible", "n"); - } - - int[] newInts = new int[usedLen + 1]; - - int nm32 = 32 - n; - newInts[0] = m_ints[0] << n; - for (int i = 1; i < usedLen; i++) - { - newInts[i] = (m_ints[i] << n) | (int)((uint)m_ints[i - 1] >> nm32); - } - newInts[usedLen] = (int)((uint)m_ints[usedLen - 1] >> nm32); - - return new IntArray(newInts); - } - - public void AddShifted(IntArray other, int shift) - { - int usedLenOther = other.GetUsedLength(); - int newMinUsedLen = usedLenOther + shift; - if (newMinUsedLen > m_ints.Length) - { - m_ints = resizedInts(newMinUsedLen); - //Console.WriteLine("Resize required"); - } - - for (int i = 0; i < usedLenOther; i++) - { - m_ints[i + shift] ^= other.m_ints[i]; - } - } - - public int Length - { - get { return m_ints.Length; } - } - - public bool TestBit(int n) - { - // theInt = n / 32 - int theInt = n >> 5; - // theBit = n % 32 - int theBit = n & 0x1F; - int tester = 1 << theBit; - return ((m_ints[theInt] & tester) != 0); - } - - public void FlipBit(int n) - { - // theInt = n / 32 - int theInt = n >> 5; - // theBit = n % 32 - int theBit = n & 0x1F; - int flipper = 1 << theBit; - m_ints[theInt] ^= flipper; - } - - public void SetBit(int n) - { - // theInt = n / 32 - int theInt = n >> 5; - // theBit = n % 32 - int theBit = n & 0x1F; - int setter = 1 << theBit; - m_ints[theInt] |= setter; - } - - public IntArray Multiply(IntArray other, int m) - { - // Lenght of c is 2m bits rounded up to the next int (32 bit) - int t = (m + 31) >> 5; - if (m_ints.Length < t) - { - m_ints = resizedInts(t); - } - - IntArray b = new IntArray(other.resizedInts(other.Length + 1)); - IntArray c = new IntArray((m + m + 31) >> 5); - // IntArray c = new IntArray(t + t); - int testBit = 1; - for (int k = 0; k < 32; k++) - { - for (int j = 0; j < t; j++) - { - if ((m_ints[j] & testBit) != 0) - { - // The kth bit of m_ints[j] is set - c.AddShifted(b, j); - } - } - testBit <<= 1; - b.ShiftLeft(); - } - return c; - } - - // public IntArray multiplyLeftToRight(IntArray other, int m) { - // // Lenght of c is 2m bits rounded up to the next int (32 bit) - // int t = (m + 31) / 32; - // if (m_ints.Length < t) { - // m_ints = resizedInts(t); - // } - // - // IntArray b = new IntArray(other.resizedInts(other.getLength() + 1)); - // IntArray c = new IntArray((m + m + 31) / 32); - // // IntArray c = new IntArray(t + t); - // int testBit = 1 << 31; - // for (int k = 31; k >= 0; k--) { - // for (int j = 0; j < t; j++) { - // if ((m_ints[j] & testBit) != 0) { - // // The kth bit of m_ints[j] is set - // c.addShifted(b, j); - // } - // } - // testBit >>>= 1; - // if (k > 0) { - // c.shiftLeft(); - // } - // } - // return c; - // } - - // TODO note, redPol.Length must be 3 for TPB and 5 for PPB - public void Reduce(int m, int[] redPol) - { - for (int i = m + m - 2; i >= m; i--) - { - if (TestBit(i)) - { - int bit = i - m; - FlipBit(bit); - FlipBit(i); - int l = redPol.Length; - while (--l >= 0) - { - FlipBit(redPol[l] + bit); - } - } - } - m_ints = resizedInts((m + 31) >> 5); - } - - public IntArray Square(int m) - { - // TODO make the table static readonly - int[] table = { 0x0, 0x1, 0x4, 0x5, 0x10, 0x11, 0x14, 0x15, 0x40, - 0x41, 0x44, 0x45, 0x50, 0x51, 0x54, 0x55 }; - - int t = (m + 31) >> 5; - if (m_ints.Length < t) - { - m_ints = resizedInts(t); - } - - IntArray c = new IntArray(t + t); - - // TODO twice the same code, put in separate private method - for (int i = 0; i < t; i++) - { - int v0 = 0; - for (int j = 0; j < 4; j++) - { - v0 = (int)((uint) v0 >> 8); - int u = (int)((uint)m_ints[i] >> (j * 4)) & 0xF; - int w = table[u] << 24; - v0 |= w; - } - c.m_ints[i + i] = v0; - - v0 = 0; - int upper = (int)((uint) m_ints[i] >> 16); - for (int j = 0; j < 4; j++) - { - v0 = (int)((uint) v0 >> 8); - int u = (int)((uint)upper >> (j * 4)) & 0xF; - int w = table[u] << 24; - v0 |= w; - } - c.m_ints[i + i + 1] = v0; - } - return c; - } - - public override bool Equals(object o) - { - if (!(o is IntArray)) - { - return false; - } - IntArray other = (IntArray) o; - int usedLen = GetUsedLength(); - if (other.GetUsedLength() != usedLen) - { - return false; - } - for (int i = 0; i < usedLen; i++) - { - if (m_ints[i] != other.m_ints[i]) - { - return false; - } - } - return true; - } - - public override int GetHashCode() - { - int i = GetUsedLength(); - int hc = i; - while (--i >= 0) - { - hc *= 17; - hc ^= m_ints[i]; - } - return hc; - } - - internal IntArray Copy() - { - return new IntArray((int[]) m_ints.Clone()); - } - - public override string ToString() - { - int usedLen = GetUsedLength(); - if (usedLen == 0) - { - return "0"; - } - - StringBuilder sb = new StringBuilder(Convert.ToString(m_ints[usedLen - 1], 2)); - for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--) - { - string hexString = Convert.ToString(m_ints[iarrJ], 2); - - // Add leading zeroes, except for highest significant int - for (int i = hexString.Length; i < 8; i++) - { - hexString = "0" + hexString; - } - sb.Append(hexString); - } - return sb.ToString(); - } - } -} diff --git a/crypto/src/math/ec/Mod.cs b/crypto/src/math/ec/Mod.cs new file mode 100644 index 000000000..57f75ed12 --- /dev/null +++ b/crypto/src/math/ec/Mod.cs @@ -0,0 +1,115 @@ +using System; + +using Org.BouncyCastle.Utilities; + +namespace Org.BouncyCastle.Math.EC +{ + internal abstract class Mod + { + public static void Invert(uint[] p, uint[] x, uint[] z) + { + int len = p.Length; + if (Nat.IsOne(len, x)) + { + Array.Copy(x, 0, z, 0, len); + return; + } + + uint[] u = Nat.Copy(len, x); + uint[] a = Nat.Create(len); + a[0] = 1; + + if ((u[0] & 1) == 0) + { + InversionStep(p, u, a); + } + if (Nat.IsOne(len, u)) + { + Array.Copy(a, 0, z, 0, len); + return; + } + + uint[] v = Nat.Copy(len, p); + uint[] b = Nat.Create(len); + + for (;;) + { + if (Nat.Gte(len, u, v)) + { + Subtract(p, a, b, a); + Nat.Sub(len, u, v, u); + if ((u[0] & 1) == 0) + { + InversionStep(p, u, a); + } + if (Nat.IsOne(len, u)) + { + Array.Copy(a, 0, z, 0, len); + return; + } + } + else + { + Subtract(p, b, a, b); + Nat.Sub(len, v, u, v); + if ((v[0] & 1) == 0) + { + InversionStep(p, v, b); + } + if (Nat.IsOne(len, v)) + { + Array.Copy(b, 0, z, 0, len); + return; + } + } + } + } + + public static void Subtract(uint[] p, uint[] x, uint[] y, uint[] z) + { + int len = p.Length; + int c = Nat.Sub(len, x, y, z); + if (c != 0) + { + Nat.Add(len, z, p, z); + } + } + + private static void InversionStep(uint[] p, uint[] u, uint[] x) + { + int len = p.Length; + int count = 0; + while (u[0] == 0) + { + Nat.ShiftDownWord(u, len, 0); + count += 32; + } + + int zeroes = GetTrailingZeroes(u[0]); + if (zeroes > 0) + { + Nat.ShiftDownBits(u, len, zeroes, 0); + count += zeroes; + } + + for (int i = 0; i < count; ++i) + { + uint c = (x[0] & 1) == 0 ? 0 : Nat.Add(len, x, p, x); + Nat.ShiftDownBit(x, len, c); + } + } + + private static int GetTrailingZeroes(uint x) + { + // assert x != 0; + + int count = 0; + while ((x & 1) == 0) + { + x >>= 1; + ++count; + } + return count; + } + } +} diff --git a/crypto/src/math/ec/Nat.cs b/crypto/src/math/ec/Nat.cs new file mode 100644 index 000000000..cc8996dfc --- /dev/null +++ b/crypto/src/math/ec/Nat.cs @@ -0,0 +1,495 @@ +using System; + +using Org.BouncyCastle.Crypto.Utilities; +using Org.BouncyCastle.Math; + +namespace Org.BouncyCastle.Math.EC +{ + internal abstract class Nat + { + public static uint Add(int len, uint[] x, uint[] y, uint[] z) + { + ulong c = 0; + for (int i = 0; i < len; ++i) + { + c += (ulong)x[i] + y[i]; + z[i] = (uint)c; + c >>= 32; + } + return (uint)c; + } + + public static uint AddBothTo(int len, uint[] x, uint[] y, uint[] z) + { + ulong c = 0; + for (int i = 0; i < len; ++i) + { + c += (ulong)x[i] + y[i] + z[i]; + z[i] = (uint)c; + c >>= 32; + } + return (uint)c; + } + + public static uint AddDWord(int len, ulong x, uint[] z, int zOff) + { + // assert zOff < (len - 2); + ulong c = x; + c += (ulong)z[zOff + 0]; + z[zOff + 0] = (uint)c; + c >>= 32; + c += (ulong)z[zOff + 1]; + z[zOff + 1] = (uint)c; + c >>= 32; + return c == 0 ? 0 : Inc(len, z, zOff + 2); + } + + public static uint AddExt(int len, uint[] xx, uint[] yy, uint[] zz) + { + int extLen = len << 1; + ulong c = 0; + for (int i = 0; i < extLen; ++i) + { + c += (ulong)xx[i] + yy[i]; + zz[i] = (uint)c; + c >>= 32; + } + return (uint)c; + } + + public static uint AddToExt(int len, uint[] x, int xOff, uint[] zz, int zzOff) + { + // assert zzOff <= len; + ulong c = 0; + for (int i = 0; i < len; ++i) + { + c += (ulong)x[xOff + i] + zz[zzOff + i]; + zz[zzOff + i] = (uint)c; + c >>= 32; + } + return (uint)c; + } + + public static uint AddWordExt(int len, uint x, uint[] zz, int zzOff) + { + // assert zzOff < ((len << 1) - 1); + ulong c = (ulong)x + zz[zzOff]; + zz[zzOff] = (uint)c; + c >>= 32; + return c == 0 ? 0 : IncExt(len, zz, zzOff + 1); + } + + public static uint[] Copy(int len, uint[] x) + { + uint[] z = new uint[len]; + Array.Copy(x, 0, z, 0, len); + return z; + } + + public static uint[] Create(int len) + { + return new uint[len]; + } + + public static uint[] CreateExt(int len) + { + int extLen = len << 1; + return new uint[extLen]; + } + + public static int Dec(int len, uint[] z, int zOff) + { + // assert zOff < len; + int i = zOff; + do + { + if (--z[i] != uint.MaxValue) + { + return 0; + } + } + while (++i < len); + return -1; + } + + public static uint[] FromBigInteger(int len, BigInteger x) + { + if (x.SignValue < 0 || x.BitLength > (len << 5)) + throw new ArgumentException(); + + uint[] z = Create(len); + int i = 0; + while (x.SignValue != 0) + { + z[i++] = (uint)x.IntValue; + x = x.ShiftRight(32); + } + return z; + } + + public static uint GetBit(uint[] x, int bit) + { + if (bit == 0) + { + return x[0] & 1; + } + uint w = (uint)bit >> 5; + int b = bit & 31; + return (x[w] >> b) & 1; + } + + public static bool Gte(int len, uint[] x, uint[] y) + { + for (int i = len - 1; i >= 0; --i) + { + uint x_i = x[i], y_i = y[i]; + if (x_i < y_i) + return false; + if (x_i > y_i) + return true; + } + return false; + } + + public static bool GteExt(int len, uint[] xx, uint[] yy) + { + int extLen = len << 1; + for (int i = extLen - 1; i >= 0; --i) + { + uint xx_i = xx[i], yy_i = yy[i]; + if (xx_i < yy_i) + return false; + if (xx_i > yy_i) + return true; + } + return false; + } + + public static uint Inc(int len, uint[] z, int zOff) + { + // assert zOff < len; + for (int i = zOff; i < len; ++i) + { + if (++z[i] != 0) + { + return 0; + } + } + return 1; + } + + public static uint IncExt(int len, uint[] zz, int zzOff) + { + int extLen = len; + // assert zzOff < extLen; + for (int i = zzOff; i < extLen; ++i) + { + if (++zz[i] != 0) + { + return 0; + } + } + return 1; + } + + public static bool IsOne(int len, uint[] x) + { + if (x[0] != 1) + { + return false; + } + for (int i = 1; i < len; ++i) + { + if (x[i] != 0) + { + return false; + } + } + return true; + } + + public static bool IsZero(int len, uint[] x) + { + if (x[0] != 0) + { + return false; + } + for (int i = 1; i < len; ++i) + { + if (x[i] != 0) + { + return false; + } + } + return true; + } + + public static bool isZeroExt(int len, uint[] xx) + { + if (xx[0] != 0) + { + return false; + } + int extLen = len << 1; + for (int i = 1; i < extLen; ++i) + { + if (xx[i] != 0) + { + return false; + } + } + return true; + } + + public static void Mul(int len, uint[] x, uint[] y, uint[] zz) + { + zz[len] = (uint)MulWordExt(len, x[0], y, zz, 0); + + for (int i = 1; i < len; ++i) + { + zz[i + len] = (uint)MulWordAddExt(len, x[i], y, 0, zz, i); + } + } + + public static uint MulWordAddExt(int len, uint x, uint[] yy, int yyOff, uint[] zz, int zzOff) + { + // assert yyOff <= len; + // assert zzOff <= len; + ulong c = 0, xVal = (ulong)x; + int i = 0; + do + { + c += xVal * yy[yyOff + i] + zz[zzOff + i]; + zz[zzOff + i] = (uint)c; + c >>= 32; + } + while (++i < len); + return (uint)c; + } + + public static uint SquareWordAddExt(int len, uint[] x, int xPos, uint[] zz) + { + // assert xPos > 0 && xPos < len; + ulong c = 0, xVal = (ulong)x[xPos]; + int i = 0; + do + { + c += xVal * x[i] + zz[xPos + i]; + zz[xPos + i] = (uint)c; + c >>= 32; + } + while (++i < xPos); + return (uint)c; + } + + public static uint MulWordDwordAdd(int len, uint x, ulong y, uint[] z, int zOff) + { + // assert zOff < (len - 3); + ulong c = 0, xVal = (ulong)x; + c += xVal * (uint)y + z[zOff + 0]; + z[zOff + 0] = (uint)c; + c >>= 32; + c += xVal * (y >> 32) + z[zOff + 1]; + z[zOff + 1] = (uint)c; + c >>= 32; + c += (ulong)z[zOff + 2]; + z[zOff + 2] = (uint)c; + c >>= 32; + return c == 0 ? 0 : Inc(len, z, zOff + 3); + } + + public static uint MulWordExt(int len, uint x, uint[] y, uint[] zz, int zzOff) + { + // assert zzOff <= len; + ulong c = 0, xVal = (ulong)x; + int i = 0; + do + { + c += xVal * y[i]; + zz[zzOff + i] = (uint)c; + c >>= 32; + } + while (++i < len); + return (uint)c; + } + + public static uint ShiftDownBit(uint[] x, int xLen, uint c) + { + int i = xLen; + while (--i >= 0) + { + uint next = x[i]; + x[i] = (next >> 1) | (c << 31); + c = next; + } + return c << 31; + } + + public static uint ShiftDownBit(int len, uint[] x, uint c, uint[] z) + { + int i = len; + while (--i >= 0) + { + uint next = x[i]; + z[i] = (next >> 1) | (c << 31); + c = next; + } + return c << 31; + } + + public static uint ShiftDownBits(uint[] x, int xLen, int bits, uint c) + { + //assert bits > 0 && bits < 32; + int i = xLen; + while (--i >= 0) + { + uint next = x[i]; + x[i] = (next >> bits) | (c << -bits); + c = next; + } + return c << 32 - bits; + } + + public static uint ShiftDownWord(uint[] x, int xLen, uint c) + { + int i = xLen; + while (--i >= 0) + { + uint next = x[i]; + x[i] = c; + c = next; + } + return c; + } + + public static uint ShiftUpBit(uint[] x, int xLen, uint c) + { + for (int i = 0; i < xLen; ++i) + { + uint next = x[i]; + x[i] = (next << 1) | (c >> 31); + c = next; + } + return c >> 31; + } + + public static uint ShiftUpBit(int len, uint[] x, uint c, uint[] z) + { + for (int i = 0; i < len; ++i) + { + uint next = x[i]; + z[i] = (next << 1) | (c >> 31); + c = next; + } + return c >> 31; + } + + public static void Square(int len, uint[] x, uint[] zz) + { + int extLen = len << 1; + uint c = 0; + int j = len, k = extLen; + do + { + ulong xVal = (ulong)x[--j]; + ulong p = xVal * xVal; + zz[--k] = (c << 31) | (uint)(p >> 33); + zz[--k] = (uint)(p >> 1); + c = (uint)p; + } + while (j > 0); + + for (int i = 1; i < len; ++i) + { + c = SquareWordAddExt(len, x, i, zz); + AddWordExt(len, c, zz, i << 1); + } + + ShiftUpBit(zz, extLen, x[0] << 31); + } + + public static int Sub(int len, uint[] x, uint[] y, uint[] z) + { + long c = 0; + for (int i = 0; i < len; ++i) + { + c += (long)x[i] - y[i]; + z[i] = (uint)c; + c >>= 32; + } + return (int)c; + } + + public static int SubBothFrom(int len, uint[] x, uint[] y, uint[] z) + { + long c = 0; + for (int i = 0; i < len; ++i) + { + c += (long)z[i] - x[i] - y[i]; + z[i] = (uint)c; + c >>= 32; + } + return (int)c; + } + + public static int SubDWord(int len, ulong x, uint[] z) + { + long c = -(long)x; + c += (long)z[0]; + z[0] = (uint)c; + c >>= 32; + c += (long)z[1]; + z[1] = (uint)c; + c >>= 32; + return c == 0 ? 0 : Dec(len, z, 2); + } + + public static int SubExt(int len, uint[] xx, uint[] yy, uint[] zz) + { + int extLen = len << 1; + long c = 0; + for (int i = 0; i < extLen; ++i) + { + c += (long)xx[i] - yy[i]; + zz[i] = (uint)c; + c >>= 32; + } + return (int)c; + } + + public static uint SubFromExt(int len, uint[] x, int xOff, uint[] zz, int zzOff) + { + // assert zzOff <= len; + ulong c = 0; + for (int i = 0; i < len; ++i) + { + c += (ulong)zz[zzOff + i] - x[xOff + i]; + zz[zzOff + i] = (uint)c; + c >>= 32; + } + return (uint)c; + } + + public static BigInteger ToBigInteger(int len, uint[] x) + { + byte[] bs = new byte[len << 2]; + for (int i = 0; i < len; ++i) + { + uint x_i = x[i]; + if (x_i != 0) + { + Pack.UInt32_To_BE(x_i, bs, (len - 1 - i) << 2); + } + } + return new BigInteger(1, bs); + } + + public static void Zero(int len, uint[] z) + { + for (int i = 0; i < len; ++i) + { + z[i] = 0; + } + } + } +} |