diff options
Diffstat (limited to 'runtime/VMProtect.Runtime/Numerics')
| -rw-r--r-- | runtime/VMProtect.Runtime/Numerics/BigInteger.cs | 2012 | ||||
| -rw-r--r-- | runtime/VMProtect.Runtime/Numerics/BigIntegerBuilder.cs | 1529 | ||||
| -rw-r--r-- | runtime/VMProtect.Runtime/Numerics/NumericHelpers.cs | 425 |
3 files changed, 3966 insertions, 0 deletions
diff --git a/runtime/VMProtect.Runtime/Numerics/BigInteger.cs b/runtime/VMProtect.Runtime/Numerics/BigInteger.cs new file mode 100644 index 0000000..b124460 --- /dev/null +++ b/runtime/VMProtect.Runtime/Numerics/BigInteger.cs @@ -0,0 +1,2012 @@ +// ==++== +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// +// ==--== +/*============================================================================= +** +** Struct: BigInteger +** +** Purpose: Represents an arbitrary precision integer. +** +=============================================================================*/ + +using System; + +using Contracts = System.Diagnostics.Debug; +using Contract = System.Diagnostics.Debug; +//using System.Globalization; +// ReSharper disable InconsistentNaming + +// ReSharper disable once CheckNamespace +namespace Numerics +{ +#if !SILVERLIGHT + [Serializable] +#endif // !SILVERLIGHT + internal struct BigInteger /*: IFormattable, IComparable, IComparable<BigInteger>, IEquatable<BigInteger>*/ + { + // ---- SECTION: members supporting exposed properties -------------* + #region members supporting exposed properties + private const uint kuMaskHighBit = unchecked((uint)int.MinValue); + private const int kcbitUint = 32; + //private const int kcbitUlong = 64; + //private const int DecimalScaleFactorMask = 0x00FF0000; + //private const int DecimalSignMask = unchecked((int)0x80000000); + + // For values int.MinValue < n <= int.MaxValue, the value is stored in sign + // and _bits is null. For all other values, sign is +1 or -1 and the bits are in _bits + private readonly int _sign; + private readonly uint[] _bits; + + // We have to make a choice of how to represent int.MinValue. This is the one + // value that fits in an int, but whose negation does not fit in an int. + // We choose to use a large representation, so we're symmetric with respect to negation. + private static readonly BigInteger s_bnMinInt = new BigInteger(-1, new[] { kuMaskHighBit }); + private static readonly BigInteger s_bnOneInt = new BigInteger(1); + private static readonly BigInteger s_bnZeroInt = new BigInteger(0); + private static readonly BigInteger s_bnMinusOneInt = new BigInteger(-1); + +#if CONTRACTS_FULL + [ContractInvariantMethod] + private void ObjectInvariant() + { + Contract.Invariant((_bits == null) ? _sign > Int32.MinValue : + ((_sign == 1 || _sign == -1) && Length(_bits) > 0)); + Contract.Invariant(_bits == null || Length(_bits) > 1 || _bits[0] >= kuMaskHighBit + , "One element array stores integers whose absolute value is between 0x80000000 and 0xFFFFFFFF"); + } +#endif + + [System.Diagnostics.Conditional("DEBUG")] + private void AssertValid() + { + if (_bits != null) + { + Contracts.Assert(_sign == 1 || _sign == -1 /*, "_sign must be +1 or -1 when _bits is non-null"*/); + Contracts.Assert(Length(_bits) > 0 /*, "_bits must contain at least 1 element or be null"*/); + if (Length(_bits) == 1) + Contracts.Assert(_bits[0] >= kuMaskHighBit /*, "Wasted space _bits[0] could have been packed into _sign"*/); + } + else + Contracts.Assert(_sign > int.MinValue /*, "Int32.MinValue should not be stored in the _sign field"*/); + } + #endregion members supporting exposed properties + + // ---- SECTION: internal properties --------------* + #region internal properties + + /*internal static BigInteger Zero + { + get { return s_bnZeroInt; } + }*/ + + private static BigInteger One + { + get { return s_bnOneInt; } + } + +/* + internal static BigInteger MinusOne + { + get { return s_bnMinusOneInt; } + } + + internal bool IsPowerOfTwo + { + get + { + AssertValid(); + + if (_bits == null) + return (_sign & (_sign - 1)) == 0 && _sign != 0; + + if (_sign != 1) + return false; + int iu = Length(_bits) - 1; + if ((_bits[iu] & (_bits[iu] - 1)) != 0) + return false; + while (--iu >= 0) + { + if (_bits[iu] != 0) + return false; + } + return true; + } + } +*/ + +/* + internal bool IsZero { get { AssertValid(); return _sign == 0; } } +*/ + +/* + internal bool IsOne { get { AssertValid(); return _sign == 1 && _bits == null; } } +*/ + + private bool IsEven { get { AssertValid(); return _bits == null ? (_sign & 1) == 0 : (_bits[0] & 1) == 0; } } + + private int Sign + { + get { AssertValid(); return (_sign >> (kcbitUint - 1)) - (-_sign >> (kcbitUint - 1)); } + } + + #endregion internal properties + + + // ---- SECTION: internal instance methods --------------* + #region internal instance methods + + public override bool Equals(object obj) + { + AssertValid(); + + if (!(obj is BigInteger)) + return false; + return Equals((BigInteger)obj); + } + + public override int GetHashCode() + { + AssertValid(); + + // ReSharper disable NonReadonlyMemberInGetHashCode + if (_bits == null) + return _sign; + var hash = _sign; + for (var iv = Length(_bits); --iv >= 0; ) + hash = NumericsHelpers.CombineHash(hash, (int)_bits[iv]); + return hash; + } + + /*public bool Equals(Int64 other) + { + AssertValid(); + + if (_bits == null) + return _sign == other; + + int cu; + if ((_sign ^ other) < 0 || (cu = Length(_bits)) > 2) + return false; + + var uu = other < 0 ? (ulong)-other : (ulong)other; + if (cu == 1) + return _bits[0] == uu; + + return NumericsHelpers.MakeUlong(_bits[1], _bits[0]) == uu; + } + + public bool Equals(UInt64 other) + { + AssertValid(); + + if (_sign < 0) + return false; + if (_bits == null) + return (ulong)_sign == other; + + var cu = Length(_bits); + if (cu > 2) + return false; + if (cu == 1) + return _bits[0] == other; + return NumericsHelpers.MakeUlong(_bits[1], _bits[0]) == other; + }*/ + + /*public bool Equals(BigInteger other) + { + AssertValid(); + other.AssertValid(); + + if (_sign != other._sign) + return false; + if (_bits == other._bits) + // _sign == other._sign && _bits == null && other._bits == null + return true; + + if (_bits == null || other._bits == null) + return false; + var cu = Length(_bits); + if (cu != Length(other._bits)) + return false; + var cuDiff = GetDiffLength(_bits, other._bits, cu); + return cuDiff == 0; + }*/ + + /*internal int CompareTo(Int64 other) + { + AssertValid(); + + if (_bits == null) + return ((long)_sign).CompareTo(other); + int cu; + if ((_sign ^ other) < 0 || (cu = Length(_bits)) > 2) + return _sign; + var uu = other < 0 ? (ulong)-other : (ulong)other; + var uuTmp = cu == 2 ? NumericsHelpers.MakeUlong(_bits[1], _bits[0]) : _bits[0]; + return _sign * uuTmp.CompareTo(uu); + } + + internal int CompareTo(UInt64 other) + { + AssertValid(); + + if (_sign < 0) + return -1; + if (_bits == null) + return ((ulong)_sign).CompareTo(other); + var cu = Length(_bits); + if (cu > 2) + return +1; + var uuTmp = cu == 2 ? NumericsHelpers.MakeUlong(_bits[1], _bits[0]) : _bits[0]; + return uuTmp.CompareTo(other); + }*/ + + private int CompareTo(BigInteger other) + { + AssertValid(); + other.AssertValid(); + + if ((_sign ^ other._sign) < 0) + { + // Different signs, so the comparison is easy. + return _sign < 0 ? -1 : +1; + } + + // Same signs + if (_bits == null) + { + if (other._bits == null) + return _sign < other._sign ? -1 : _sign > other._sign ? +1 : 0; + return -other._sign; + } + int cuThis, cuOther; + if (other._bits == null || (cuThis = Length(_bits)) > (cuOther = Length(other._bits))) + return _sign; + if (cuThis < cuOther) + return -_sign; + + var cuDiff = GetDiffLength(_bits, other._bits, cuThis); + if (cuDiff == 0) + return 0; + return _bits[cuDiff - 1] < other._bits[cuDiff - 1] ? -_sign : _sign; + } + +/* + public int CompareTo(Object obj) + { + if (obj == null) + return 1; + if (!(obj is BigInteger)) + throw new ArgumentException("Argument must be BigInteger", "obj"); + return CompareTo((BigInteger)obj); + } +*/ + + + // Return the value of this BigInteger as a little-endian twos-complement + // byte array, using the fewest number of bytes possible. If the value is zero, + // return an array of one byte whose element is 0x00. + internal byte[] ToByteArray() + { + if (_bits == null && _sign == 0) + return new byte[] { 0 }; + + // We could probably make this more efficient by eliminating one of the passes. + // The current code does one pass for uint array -> byte array conversion, + // and then another pass to remove unneeded bytes at the top of the array. + uint[] dwords; + byte highByte; + + if (_bits == null) + { + dwords = new[] { (uint)_sign }; + highByte = (byte)(_sign < 0 ? 0xff : 0x00); + } + else if (_sign == -1) + { + dwords = (uint[])_bits.Clone(); + NumericsHelpers.DangerousMakeTwosComplement(dwords); // mutates dwords + highByte = 0xff; + } + else + { + dwords = _bits; + highByte = 0x00; + } + + var bytes = new byte[checked(4 * dwords.Length)]; + var curByte = 0; + foreach (var t in dwords) + { + var dword = t; + for (var j = 0; j < 4; j++) + { + bytes[curByte++] = (byte)(dword & 0xff); + dword >>= 8; + } + } + + // ensure high bit is 0 if positive, 1 if negative + if ((bytes[bytes.Length - 1] & 0x80) == (highByte & 0x80)) + return bytes; + + var trimmedBytes = new byte[bytes.Length + 1]; + Array.Copy(bytes, trimmedBytes, bytes.Length); + trimmedBytes[trimmedBytes.Length - 1] = highByte; + return trimmedBytes; + } + + // Return the value of this BigInteger as a little-endian twos-complement + // uint array, using the fewest number of uints possible. If the value is zero, + // return an array of one uint whose element is 0. +/* + private UInt32[] ToUInt32Array() + { + if (_bits == null && _sign == 0) + return new uint[] { 0 }; + + uint[] dwords; + uint highDWord; + + if (_bits == null) + { + dwords = new[] { (uint)_sign }; + highDWord = _sign < 0 ? UInt32.MaxValue : 0; + } + else if (_sign == -1) + { + dwords = (uint[])_bits.Clone(); + NumericsHelpers.DangerousMakeTwosComplement(dwords); // mutates dwords + highDWord = UInt32.MaxValue; + } + else + { + dwords = _bits; + highDWord = 0; + } + + // find highest significant byte + int msb; + for (msb = dwords.Length - 1; msb > 0; msb--) + { + if (dwords[msb] != highDWord) break; + } + // ensure high bit is 0 if positive, 1 if negative + var needExtraByte = (dwords[msb] & 0x80000000) != (highDWord & 0x80000000); + + var trimmed = new uint[msb + 1 + (needExtraByte ? 1 : 0)]; + Array.Copy(dwords, trimmed, msb + 1); + + if (needExtraByte) trimmed[trimmed.Length - 1] = highDWord; + return trimmed; + } +*/ + + /*public override String ToString() + { + return BigNumber.FormatBigInteger(this, null, NumberFormatInfo.CurrentInfo); + } + + internal String ToString(IFormatProvider provider) + { + return BigNumber.FormatBigInteger(this, null, NumberFormatInfo.GetInstance(provider)); + } + + internal String ToString(String format) + { + return BigNumber.FormatBigInteger(this, format, NumberFormatInfo.CurrentInfo); + } + + public String ToString(String format, IFormatProvider provider) + { + return BigNumber.FormatBigInteger(this, format, NumberFormatInfo.GetInstance(provider)); + }*/ + #endregion internal instance methods + + // -------- SECTION: constructors -----------------* + #region constructors + + private BigInteger(int value) + { + if (value == Int32.MinValue) + this = s_bnMinInt; + else + { + _sign = value; + _bits = null; + } + AssertValid(); + } + +/* + internal BigInteger(uint value) + { + if (value <= Int32.MaxValue) + { + _sign = (int)value; + _bits = null; + } + else + { + _sign = +1; + _bits = new uint[1]; + _bits[0] = value; + } + AssertValid(); + } +*/ + +/* + internal BigInteger(Int64 value) + { + if (Int32.MinValue <= value && value <= Int32.MaxValue) + { + if (value == Int32.MinValue) + this = s_bnMinInt; + else + { + _sign = (int)value; + _bits = null; + } + AssertValid(); + return; + } + + ulong x; + if (value < 0) + { + x = (ulong)-value; + _sign = -1; + } + else + { + Contract.Assert(value != 0); + x = (ulong)value; + _sign = +1; + } + + _bits = new uint[2]; + _bits[0] = (uint)x; + _bits[1] = (uint)(x >> kcbitUint); + AssertValid(); + } +*/ + +/* + internal BigInteger(UInt64 value) + { + if (value <= Int32.MaxValue) + { + _sign = (int)value; + _bits = null; + } + else + { + _sign = +1; + _bits = new uint[2]; + _bits[0] = (uint)value; + _bits[1] = (uint)(value >> kcbitUint); + } + AssertValid(); + } +*/ + + /*internal BigInteger(Single value) + { + if (Single.IsInfinity(value)) + throw new OverflowException("Overflow BigIntInfinity"); + if (Single.IsNaN(value)) + throw new OverflowException("Overflow not a number"); + ////Contract.EndContractBlock(); + + _sign = 0; + _bits = null; + // ReSharper disable once ExpressionIsAlwaysNull + SetBitsFromDouble(value); + AssertValid(); + } + + internal BigInteger(Double value) + { + if (Double.IsInfinity(value)) + throw new OverflowException("Overflow BigIntInfinity"); + if (Double.IsNaN(value)) + throw new OverflowException("Overflow not a number"); + ////Contract.EndContractBlock(); + + _sign = 0; + _bits = null; + // ReSharper disable once ExpressionIsAlwaysNull + SetBitsFromDouble(value); + AssertValid(); + }*/ + + /*internal BigInteger(Decimal value) + { + // First truncate to get scale to 0 and extract bits + var bits = Decimal.GetBits(Decimal.Truncate(value)); + + Contract.Assert(bits.Length == 4 && (bits[3] & DecimalScaleFactorMask) == 0); + + var size = 3; + while (size > 0 && bits[size - 1] == 0) + size--; + if (size == 0) + { + this = s_bnZeroInt; + } + else if (size == 1 && bits[0] > 0) + { + // bits[0] is the absolute value of this decimal + // if bits[0] < 0 then it is too large to be packed into _sign + _sign = bits[0]; + _sign *= (bits[3] & DecimalSignMask) != 0 ? -1 : +1; + _bits = null; + } + else + { + _bits = new UInt32[size]; + _bits[0] = (UInt32)bits[0]; + if (size > 1) + _bits[1] = (UInt32)bits[1]; + if (size > 2) + _bits[2] = (UInt32)bits[2]; + _sign = (bits[3] & DecimalSignMask) != 0 ? -1 : +1; + } + AssertValid(); + }*/ + + // + // Create a BigInteger from a little-endian twos-complement byte array + // + internal BigInteger(Byte[] value) + { + if (value == null) + throw new ArgumentNullException("value"); + //Contract.EndContractBlock(); + + var byteCount = value.Length; + var isNegative = byteCount > 0 && ((value[byteCount - 1] & 0x80) == 0x80); + + // Try to conserve space as much as possible by checking for wasted leading byte[] entries + while (byteCount > 0 && value[byteCount - 1] == 0) byteCount--; + + if (byteCount == 0) + { + // BigInteger.Zero + _sign = 0; + _bits = null; + // ReSharper disable once ExpressionIsAlwaysNull + AssertValid(); + return; + } + + + if (byteCount <= 4) + { + if (isNegative) + _sign = unchecked((int)0xffffffff); + else + _sign = 0; + for (var i = byteCount - 1; i >= 0; i--) + { + _sign <<= 8; + _sign |= value[i]; + } + _bits = null; + + if (_sign < 0 && !isNegative) + { + // int32 overflow + // example: Int64 value 2362232011 (0xCB, 0xCC, 0xCC, 0x8C, 0x0) + // can be naively packed into 4 bytes (due to the leading 0x0) + // it overflows into the int32 sign bit + _bits = new uint[1]; + _bits[0] = (uint)_sign; + _sign = +1; + } + if (_sign == Int32.MinValue) + this = s_bnMinInt; + } + else + { + var unalignedBytes = byteCount % 4; + var dwordCount = byteCount / 4 + (unalignedBytes == 0 ? 0 : 1); + var isZero = true; + var val = new uint[dwordCount]; + + // Copy all dwords, except but don't do the last one if it's not a full four bytes + int curDword; + var curByte = 3; + for (curDword = 0; curDword < dwordCount - (unalignedBytes == 0 ? 0 : 1); curDword++) + { + var byteInDword = 0; + while (byteInDword < 4) + { + if (value[curByte] != 0x00) isZero = false; + val[curDword] <<= 8; + val[curDword] |= value[curByte]; + curByte--; + byteInDword++; + } + curByte += 8; + } + + // Copy the last dword specially if it's not aligned + if (unalignedBytes != 0) + { + if (isNegative) val[dwordCount - 1] = 0xffffffff; + for (curByte = byteCount - 1; curByte >= byteCount - unalignedBytes; curByte--) + { + if (value[curByte] != 0x00) isZero = false; + val[curDword] <<= 8; + val[curDword] |= value[curByte]; + } + } + + if (isZero) + { + this = s_bnZeroInt; + } + else if (isNegative) + { + NumericsHelpers.DangerousMakeTwosComplement(val); // mutates val + + // pack _bits to remove any wasted space after the twos complement + var len = val.Length; + while (len > 0 && val[len - 1] == 0) + len--; + if (len == 1 && (int)val[0] > 0) + { + if (val[0] == 1 /* abs(-1) */) + { + this = s_bnMinusOneInt; + } + else if (val[0] == kuMaskHighBit /* abs(Int32.MinValue) */) //TODO: V3022 https://www.viva64.com/en/w/V3022 Expression 'val[0] == kuMaskHighBit' is always false. + { + this = s_bnMinInt; + } + else + { + _sign = -1 * (int)val[0]; + _bits = null; + } + } + else if (len != val.Length) + { + _sign = -1; + _bits = new uint[len]; + Array.Copy(val, _bits, len); + } + else + { + _sign = -1; + _bits = val; + } + } + else + { + _sign = +1; + _bits = val; + } + } + AssertValid(); + } + + internal BigInteger(int n, uint[] rgu) + { + _sign = n; + _bits = rgu; + AssertValid(); + } + + // + // BigInteger(uint[] value, bool negative) + // + // Constructor used during bit manipulation and arithmetic + // + // The uint[] value is expected to be the absolute value of the number + // with the bool negative indicating the Sign of the value. + // + // When possible the uint[] will be packed into _sign to conserve space + // +/* + internal BigInteger(uint[] value, bool negative) + { + if (value == null) + throw new ArgumentNullException("value"); + //Contract.EndContractBlock(); + + int len; + + // Try to conserve space as much as possible by checking for wasted leading uint[] entries + // sometimes the uint[] has leading zeros from bit manipulation operations & and ^ + for (len = value.Length; len > 0 && value[len - 1] == 0; len--) + { + } + + if (len == 0) + this = s_bnZeroInt; + // values like (Int32.MaxValue+1) are stored as "0x80000000" and as such cannot be packed into _sign + else if (len == 1 && value[0] < kuMaskHighBit) + { + _sign = negative ? -(int)value[0] : (int)value[0]; + _bits = null; + // Although Int32.MinValue fits in _sign, we represent this case differently for negate + if (_sign == Int32.MinValue) + this = s_bnMinInt; + } + else + { + _sign = negative ? -1 : +1; + _bits = new uint[len]; + Array.Copy(value, _bits, len); + } + AssertValid(); + } +*/ + + + // + // Create a BigInteger from a little-endian twos-complement UInt32 array + // When possible, value is assigned directly to this._bits without an array copy + // so use this ctor with care + // +// private BigInteger(uint[] value) +// { +// if (value == null) +// throw new ArgumentNullException("value"); +// +// var dwordCount = value.Length; +// var isNegative = dwordCount > 0 && ((value[dwordCount - 1] & 0x80000000) == 0x80000000); +// +// // Try to conserve space as much as possible by checking for wasted leading uint[] entries +// while (dwordCount > 0 && value[dwordCount - 1] == 0) dwordCount--; +// +// if (dwordCount == 0) +// { +// // BigInteger.Zero +// this = s_bnZeroInt; +// AssertValid(); +// return; +// } +// if (dwordCount == 1) +// { +// if ((int)value[0] < 0 && !isNegative) +// { +// _bits = new uint[1]; +// _bits[0] = value[0]; +// _sign = +1; +// } +// // handle the special cases where the BigInteger likely fits into _sign +// else if (Int32.MinValue == (int)value[0]) +// { +// this = s_bnMinInt; +// } +// else +// { +// _sign = (int)value[0]; +// _bits = null; +// } +// AssertValid(); +// return; +// } +// +// if (!isNegative) +// { +// // handle the simple postive value cases where the input is already in sign magnitude +// if (dwordCount != value.Length) +// { +// _sign = +1; +// _bits = new uint[dwordCount]; +// Array.Copy(value, _bits, dwordCount); +// } +// // no trimming is possible. Assign value directly to _bits. +// else +// { +// _sign = +1; +// _bits = value; +// } +// AssertValid(); +// return; +// } +// +// +// // finally handle the more complex cases where we must transform the input into sign magnitude +// NumericsHelpers.DangerousMakeTwosComplement(value); // mutates val +// +// // pack _bits to remove any wasted space after the twos complement +// var len = value.Length; +// while (len > 0 && value[len - 1] == 0) len--; +// +// // the number is represented by a single dword +// if (len == 1 && (int)value[0] > 0) +// { +// if (value[0] == 1 /* abs(-1) */) +// { +// this = s_bnMinusOneInt; +// } +// else if (value[0] == kuMaskHighBit /* abs(Int32.MinValue) */) +// { +// this = s_bnMinInt; +// } +// else +// { +// _sign = -1 * (int)value[0]; +// _bits = null; +// } +// } +// // the number is represented by multiple dwords +// // trim off any wasted uint values when possible +// else if (len != value.Length) +// { +// _sign = -1; +// _bits = new uint[len]; +// Array.Copy(value, _bits, len); +// } +// // no trimming is possible. Assign value directly to _bits. +// else +// { +// _sign = -1; +// _bits = value; +// } +// AssertValid(); +// } + + + #endregion constructors + + + // -------- SECTION: internal static methods -----------------* + #region internal static methods +#if !SILVERLIGHT || FEATURE_NETCORE +/* + internal static BigInteger Parse(String value) + { + return BigNumber.ParseBigInteger(value, NumberStyles.Integer, NumberFormatInfo.CurrentInfo); + } +*/ + +/* + internal static BigInteger Parse(String value, NumberStyles style) + { + return BigNumber.ParseBigInteger(value, style, NumberFormatInfo.CurrentInfo); + } +*/ + +/* + internal static BigInteger Parse(String value, IFormatProvider provider) + { + return BigNumber.ParseBigInteger(value, NumberStyles.Integer, NumberFormatInfo.GetInstance(provider)); + } +*/ + +/* + internal static BigInteger Parse(String value, NumberStyles style, IFormatProvider provider) + { + return BigNumber.ParseBigInteger(value, style, NumberFormatInfo.GetInstance(provider)); + } +*/ + +/* + internal static Boolean TryParse(String value, out BigInteger result) + { + return BigNumber.TryParseBigInteger(value, NumberStyles.Integer, NumberFormatInfo.CurrentInfo, out result); + } +*/ + +/* + internal static Boolean TryParse(String value, NumberStyles style, IFormatProvider provider, out BigInteger result) + { + return BigNumber.TryParseBigInteger(value, style, NumberFormatInfo.GetInstance(provider), out result); + } +*/ +#endif //!SILVERLIGHT || FEATURE_NETCORE + +/* + internal static Int32 Compare(BigInteger left, BigInteger right) + { + return left.CompareTo(right); + } +*/ + +/* + internal static BigInteger Abs(BigInteger value) + { + return value >= Zero ? value : -value; + } +*/ + +/* + internal static BigInteger Add(BigInteger left, BigInteger right) + { + return left + right; + } +*/ + +/* + internal static BigInteger Subtract(BigInteger left, BigInteger right) + { + return left - right; + } +*/ + +/* + internal static BigInteger Multiply(BigInteger left, BigInteger right) + { + return left * right; + } +*/ + +/* + internal static BigInteger Divide(BigInteger dividend, BigInteger divisor) + { + return dividend / divisor; + } +*/ + +/* + internal static BigInteger Remainder(BigInteger dividend, BigInteger divisor) + { + return dividend % divisor; + } +*/ + +/* + internal static BigInteger DivRem(BigInteger dividend, BigInteger divisor, out BigInteger remainder) + { + dividend.AssertValid(); + divisor.AssertValid(); + + var signNum = +1; + var signDen = +1; + var regNum = new BigIntegerBuilder(dividend, ref signNum); + var regDen = new BigIntegerBuilder(divisor, ref signDen); + var regQuo = new BigIntegerBuilder(); + + // regNum and regQuo are overwritten with the remainder and quotient, respectively + regNum.ModDiv(ref regDen, ref regQuo); + remainder = regNum.GetInteger(signNum); + return regQuo.GetInteger(signNum * signDen); + } +*/ + + +/* + internal static BigInteger Negate(BigInteger value) + { + return -value; + } +*/ + + // Returns the natural (base e) logarithm of a specified number. +/* + internal static Double Log(BigInteger value, Double baseValue = Math.E) + { + // ReSharper disable CompareOfFloatsByEqualityOperator + if (value._sign < 0 || baseValue == 1.0D) + return Double.NaN; + if (baseValue == Double.PositiveInfinity) + return value.IsOne ? 0.0D : Double.NaN; + if (baseValue == 0.0D && !value.IsOne) + return Double.NaN; + if (value._bits == null) + return Math.Log(value._sign, baseValue); + // ReSharper restore CompareOfFloatsByEqualityOperator + + Double c = 0, d = 0.5D; + const Double log2 = 0.69314718055994529D; + + var uintLength = Length(value._bits); + var topbits = BitLengthOfUInt(value._bits[uintLength - 1]); + var bitlen = (uintLength - 1) * kcbitUint + topbits; + var indbit = (uint)(1 << (topbits - 1)); + + for (var index = uintLength - 1; index >= 0; --index) + { + while (indbit != 0) + { + if ((value._bits[index] & indbit) != 0) + c += d; + d *= 0.5; + indbit >>= 1; + } + indbit = 0x80000000; + } + return (Math.Log(c) + log2 * bitlen) / Math.Log(baseValue); + } +*/ + + +/* + internal static Double Log10(BigInteger value) + { + return Log(value, 10); + } +*/ + +/* + internal static BigInteger GreatestCommonDivisor(BigInteger left, BigInteger right) + { + left.AssertValid(); + right.AssertValid(); + + // gcd(0, 0) = 0 + // gcd(a, 0) = |a|, for a != 0, since any number is a divisor of 0, and the greatest divisor of a is |a| + if (left._sign == 0) return Abs(right); + if (right._sign == 0) return Abs(left); + + var reg1 = new BigIntegerBuilder(left); + var reg2 = new BigIntegerBuilder(right); + BigIntegerBuilder.GCD(ref reg1, ref reg2); + + return reg1.GetInteger(+1); + } +*/ + +/* + internal static BigInteger Max(BigInteger left, BigInteger right) + { + if (left.CompareTo(right) < 0) + return right; + return left; + } +*/ + +/* + internal static BigInteger Min(BigInteger left, BigInteger right) + { + if (left.CompareTo(right) <= 0) + return left; + return right; + } +*/ + + + private static void ModPowUpdateResult(ref BigIntegerBuilder regRes, ref BigIntegerBuilder regVal, ref BigIntegerBuilder regMod, ref BigIntegerBuilder regTmp) + { + NumericsHelpers.Swap(ref regRes, ref regTmp); + regRes.Mul(ref regTmp, ref regVal); // result = result * value; + regRes.Mod(ref regMod); // result = result % modulus; + } + + private static void ModPowSquareModValue(ref BigIntegerBuilder regVal, ref BigIntegerBuilder regMod, ref BigIntegerBuilder regTmp) + { + NumericsHelpers.Swap(ref regVal, ref regTmp); + regVal.Mul(ref regTmp, ref regTmp); // value = value * value; + regVal.Mod(ref regMod); // value = value % modulus; + } + + private static void ModPowInner(uint exp, ref BigIntegerBuilder regRes, ref BigIntegerBuilder regVal, ref BigIntegerBuilder regMod, ref BigIntegerBuilder regTmp) + { + while (exp != 0) // !(Exponent.IsZero) + { + if ((exp & 1) == 1) // !(Exponent.IsEven) + ModPowUpdateResult(ref regRes, ref regVal, ref regMod, ref regTmp); + if (exp == 1) // Exponent.IsOne - we can exit early + break; + ModPowSquareModValue(ref regVal, ref regMod, ref regTmp); + exp >>= 1; + } + } + + private static void ModPowInner32(uint exp, ref BigIntegerBuilder regRes, ref BigIntegerBuilder regVal, ref BigIntegerBuilder regMod, ref BigIntegerBuilder regTmp) + { + for (var i = 0; i < 32; i++) + { + if ((exp & 1) == 1) // !(Exponent.IsEven) + ModPowUpdateResult(ref regRes, ref regVal, ref regMod, ref regTmp); + ModPowSquareModValue(ref regVal, ref regMod, ref regTmp); + exp >>= 1; + } + } + + internal static BigInteger ModPow(BigInteger value, BigInteger exponent, BigInteger modulus) + { + if (exponent.Sign < 0) + throw new ArgumentOutOfRangeException("exponent", "ArgumentOutOfRange must be non negative"); + //Contract.EndContractBlock(); + + value.AssertValid(); + exponent.AssertValid(); + modulus.AssertValid(); + + var signRes = +1; + var signVal = +1; + var signMod = +1; + var expIsEven = exponent.IsEven; + var regRes = new BigIntegerBuilder(One, ref signRes); + var regVal = new BigIntegerBuilder(value, ref signVal); + var regMod = new BigIntegerBuilder(modulus, ref signMod); + var regTmp = new BigIntegerBuilder(regVal.Size); + + regRes.Mod(ref regMod); // Handle special case of exponent=0, modulus=1 + + if (exponent._bits == null) + { // exponent fits into an Int32 + ModPowInner((uint)exponent._sign, ref regRes, ref regVal, ref regMod, ref regTmp); + } + else + { // very large exponent + var len = Length(exponent._bits); + for (var i = 0; i < len - 1; i++) + { + var exp = exponent._bits[i]; + ModPowInner32(exp, ref regRes, ref regVal, ref regMod, ref regTmp); + } + ModPowInner(exponent._bits[len - 1], ref regRes, ref regVal, ref regMod, ref regTmp); + } + + return regRes.GetInteger(value._sign > 0 ? +1 : expIsEven ? +1 : -1); + } + +/* + internal static BigInteger Pow(BigInteger value, Int32 exponent) + { + if (exponent < 0) + throw new ArgumentOutOfRangeException("exponent", "ArgumentOutOfRange must be non negative"); + //Contract.EndContractBlock(); + + value.AssertValid(); + + if (exponent == 0) + return One; + if (exponent == 1) + return value; + if (value._bits == null) + { + if (value._sign == 1) + return value; + if (value._sign == -1) + return (exponent & 1) != 0 ? value : 1; + if (value._sign == 0) + return value; + } + + var sign = +1; + var regSquare = new BigIntegerBuilder(value, ref sign); + + // Get an estimate of the size needed for regSquare and regRes, so we can minimize allocations. + var cuSquareMin = regSquare.Size; + var cuSquareMax = cuSquareMin; + var uSquareMin = regSquare.High; + var uSquareMax = uSquareMin + 1; + if (uSquareMax == 0) + { + cuSquareMax++; + uSquareMax = 1; + } + var cuResMin = 1; + var cuResMax = 1; + uint uResMin = 1; + uint uResMax = 1; + + for (var expTmp = exponent; ; ) + { + if ((expTmp & 1) != 0) + { + MulUpper(ref uResMax, ref cuResMax, uSquareMax, cuSquareMax); + MulLower(ref uResMin, ref cuResMin, uSquareMin, cuSquareMin); + } + + if ((expTmp >>= 1) == 0) + break; + + MulUpper(ref uSquareMax, ref cuSquareMax, uSquareMax, cuSquareMax); + MulLower(ref uSquareMin, ref cuSquareMin, uSquareMin, cuSquareMin); + } + + if (cuResMax > 1) + regSquare.EnsureWritable(cuResMax, 0); + var regTmp = new BigIntegerBuilder(cuResMax); + var regRes = new BigIntegerBuilder(cuResMax); + regRes.Set(1); + + if ((exponent & 1) == 0) + sign = +1; + + for (var expTmp = exponent; ; ) + { + if ((expTmp & 1) != 0) + { + NumericsHelpers.Swap(ref regRes, ref regTmp); + regRes.Mul(ref regSquare, ref regTmp); + } + if ((expTmp >>= 1) == 0) + break; + NumericsHelpers.Swap(ref regSquare, ref regTmp); + regSquare.Mul(ref regTmp, ref regTmp); + } + + return regRes.GetInteger(sign); + } +*/ + + #endregion internal static methods + + // -------- SECTION: internal static operators -----------------* + #region internal static operators + /*public static implicit operator BigInteger(Byte value) + { + return new BigInteger(value); + } + + public static implicit operator BigInteger(SByte value) + { + return new BigInteger(value); + } + + public static implicit operator BigInteger(Int16 value) + { + return new BigInteger(value); + } + + public static implicit operator BigInteger(UInt16 value) + { + return new BigInteger(value); + } + + public static implicit operator BigInteger(int value) + { + return new BigInteger(value); + } + + public static implicit operator BigInteger(uint value) + { + return new BigInteger(value); + } + + public static implicit operator BigInteger(long value) + { + return new BigInteger(value); + } + + public static implicit operator BigInteger(ulong value) + { + return new BigInteger(value); + }*/ + + /*public static explicit operator BigInteger(Single value) + { + return new BigInteger(value); + } + + public static explicit operator BigInteger(Double value) + { + return new BigInteger(value); + } + + public static explicit operator BigInteger(Decimal value) + { + return new BigInteger(value); + } + + public static explicit operator Byte(BigInteger value) + { + return checked((byte)(int)value); + } + + public static explicit operator SByte(BigInteger value) + { + return checked((sbyte)(int)value); + } + + public static explicit operator Int16(BigInteger value) + { + return checked((short)(int)value); + } + + public static explicit operator UInt16(BigInteger value) + { + return checked((ushort)(int)value); + } + + public static explicit operator Int32(BigInteger value) + { + value.AssertValid(); + if (value._bits == null) + { + return value._sign; // value packed into int32 sign + } + else if (Length(value._bits) > 1) + { // more than 32 bits + throw new OverflowException("Overflow Int32"); + } + else if (value._sign > 0) + { + return checked((int)value._bits[0]); + } + else + { + if (value._bits[0] > kuMaskHighBit) + { // value > Int32.MinValue + throw new OverflowException("Overflow Int32"); + } + return unchecked(-(int)value._bits[0]); + } + } + + public static explicit operator UInt32(BigInteger value) + { + value.AssertValid(); + if (value._bits == null) + { + return checked((uint)value._sign); + } + else if (Length(value._bits) > 1 || value._sign < 0) + { + throw new OverflowException("Overflow UInt32"); + } + else + { + return value._bits[0]; + } + } + + public static explicit operator Int64(BigInteger value) + { + value.AssertValid(); + if (value._bits == null) + { + return value._sign; + } + + var len = Length(value._bits); + if (len > 2) + { + throw new OverflowException("Overflow Int64"); + } + + var uu = len > 1 ? NumericsHelpers.MakeUlong(value._bits[1], value._bits[0]) : value._bits[0]; + + var ll = value._sign > 0 ? (long)uu : -(long)uu; + if ((ll > 0 && value._sign > 0) || (ll < 0 && value._sign < 0)) + { + // signs match, no overflow + return ll; + } + throw new OverflowException("Overflow Int64"); + } + + public static explicit operator UInt64(BigInteger value) + { + value.AssertValid(); + if (value._bits == null) + { + return checked((ulong)value._sign); + } + + var len = Length(value._bits); + if (len > 2 || value._sign < 0) + { + throw new OverflowException("Overflow UInt64"); + } + + if (len > 1) + { + return NumericsHelpers.MakeUlong(value._bits[1], value._bits[0]); + } + else + { + return value._bits[0]; + } + }*/ + + /*public static explicit operator Single(BigInteger value) + { + return (Single)(Double)value; + }*/ + + /*public static explicit operator Double(BigInteger value) + { + value.AssertValid(); + if (value._bits == null) + return value._sign; + + ulong man; + int exp; + var sign = +1; + var reg = new BigIntegerBuilder(value, ref sign); + reg.GetApproxParts(out exp, out man); + return NumericsHelpers.GetDoubleFromParts(sign, exp, man); + } + + public static explicit operator Decimal(BigInteger value) + { + value.AssertValid(); + if (value._bits == null) + return value._sign; + + var length = Length(value._bits); + if (length > 3) throw new OverflowException("Overflow Decimal"); + + int lo = 0, mi = 0, hi = 0; + if (length > 2) hi = (Int32)value._bits[2]; + if (length > 1) mi = (Int32)value._bits[1]; + if (length > 0) lo = (Int32)value._bits[0]; + + return new Decimal(lo, mi, hi, value._sign < 0, 0); + } + + public static BigInteger operator &(BigInteger left, BigInteger right) + { + if (left.IsZero || right.IsZero) + { + return Zero; + } + + var x = left.ToUInt32Array(); + var y = right.ToUInt32Array(); + var z = new uint[Math.Max(x.Length, y.Length)]; + var xExtend = left._sign < 0 ? UInt32.MaxValue : 0; + var yExtend = right._sign < 0 ? UInt32.MaxValue : 0; + + for (var i = 0; i < z.Length; i++) + { + var xu = i < x.Length ? x[i] : xExtend; + var yu = i < y.Length ? y[i] : yExtend; + z[i] = xu & yu; + } + return new BigInteger(z); + } + + public static BigInteger operator |(BigInteger left, BigInteger right) + { + if (left.IsZero) + return right; + if (right.IsZero) + return left; + + var x = left.ToUInt32Array(); + var y = right.ToUInt32Array(); + var z = new uint[Math.Max(x.Length, y.Length)]; + var xExtend = left._sign < 0 ? UInt32.MaxValue : 0; + var yExtend = right._sign < 0 ? UInt32.MaxValue : 0; + + for (var i = 0; i < z.Length; i++) + { + var xu = i < x.Length ? x[i] : xExtend; + var yu = i < y.Length ? y[i] : yExtend; + z[i] = xu | yu; + } + return new BigInteger(z); + } + + public static BigInteger operator ^(BigInteger left, BigInteger right) + { + var x = left.ToUInt32Array(); + var y = right.ToUInt32Array(); + var z = new uint[Math.Max(x.Length, y.Length)]; + var xExtend = left._sign < 0 ? UInt32.MaxValue : 0; + var yExtend = right._sign < 0 ? UInt32.MaxValue : 0; + + for (var i = 0; i < z.Length; i++) + { + var xu = i < x.Length ? x[i] : xExtend; + var yu = i < y.Length ? y[i] : yExtend; + z[i] = xu ^ yu; + } + + return new BigInteger(z); + } + + public static BigInteger operator <<(BigInteger value, int shift) + { + + if (shift == 0) return value; + else if (shift == Int32.MinValue) return value >> Int32.MaxValue >> 1; + else if (shift < 0) return value >> -shift; + + var digitShift = shift / kcbitUint; + var smallShift = shift - digitShift * kcbitUint; + + uint[] xd; int xl; + var negx = GetPartsForBitManipulation(ref value, out xd, out xl); + + var zl = xl + digitShift + 1; + var zd = new uint[zl]; + + if (smallShift == 0) + { + for (var i = 0; i < xl; i++) + { + zd[i + digitShift] = xd[i]; + } + } + else + { + var carryShift = kcbitUint - smallShift; + uint carry = 0; + int i; + for (i = 0; i < xl; i++) + { + var rot = xd[i]; + zd[i + digitShift] = rot << smallShift | carry; + carry = rot >> carryShift; + } + zd[i + digitShift] = carry; + } + return new BigInteger(zd, negx); + } + + public static BigInteger operator >>(BigInteger value, int shift) + { + if (shift == 0) return value; + else if (shift == Int32.MinValue) return value << Int32.MaxValue << 1; + else if (shift < 0) return value << -shift; + + var digitShift = shift / kcbitUint; + var smallShift = shift - digitShift * kcbitUint; + + uint[] xd; int xl; + var negx = GetPartsForBitManipulation(ref value, out xd, out xl); + + if (negx) + { + if (shift >= kcbitUint * xl) + { + return MinusOne; + } + var temp = new uint[xl]; + Array.Copy(xd , temp , xl ); // make a copy of immutable value._bits + xd = temp; + NumericsHelpers.DangerousMakeTwosComplement(xd); // mutates xd + } + + var zl = xl - digitShift; + if (zl < 0) zl = 0; + var zd = new uint[zl]; + + if (smallShift == 0) + { + for (var i = xl - 1; i >= digitShift; i--) + { + zd[i - digitShift] = xd[i]; + } + } + else + { + var carryShift = kcbitUint - smallShift; + uint carry = 0; + for (var i = xl - 1; i >= digitShift; i--) + { + var rot = xd[i]; + if (negx && i == xl - 1) + // sign-extend the first shift for negative ints then let the carry propagate + zd[i - digitShift] = (rot >> smallShift) | (0xFFFFFFFF << carryShift); + else + zd[i - digitShift] = (rot >> smallShift) | carry; + carry = rot << carryShift; + } + } + if (negx) + { + NumericsHelpers.DangerousMakeTwosComplement(zd); // mutates zd + } + return new BigInteger(zd, negx); + } + + + public static BigInteger operator ~(BigInteger value) + { + return -(value + One); + } + + public static BigInteger operator -(BigInteger value) + { + value.AssertValid(); + value._sign = -value._sign; + value.AssertValid(); + return value; + } + + public static BigInteger operator +(BigInteger value) + { + value.AssertValid(); + return value; + } + + + public static BigInteger operator ++(BigInteger value) + { + return value + One; + } + + public static BigInteger operator --(BigInteger value) + { + return value - One; + } + + + public static BigInteger operator +(BigInteger left, BigInteger right) + { + left.AssertValid(); + right.AssertValid(); + + if (right.IsZero) return left; + if (left.IsZero) return right; + + var sign1 = +1; + var sign2 = +1; + var reg1 = new BigIntegerBuilder(left, ref sign1); + var reg2 = new BigIntegerBuilder(right, ref sign2); + + if (sign1 == sign2) + reg1.Add(ref reg2); + else + reg1.Sub(ref sign1, ref reg2); + + return reg1.GetInteger(sign1); + } + + public static BigInteger operator -(BigInteger left, BigInteger right) + { + left.AssertValid(); + right.AssertValid(); + + if (right.IsZero) return left; + if (left.IsZero) return -right; + + var sign1 = +1; + var sign2 = -1; + var reg1 = new BigIntegerBuilder(left, ref sign1); + var reg2 = new BigIntegerBuilder(right, ref sign2); + + if (sign1 == sign2) + reg1.Add(ref reg2); + else + reg1.Sub(ref sign1, ref reg2); + + return reg1.GetInteger(sign1); + } + + public static BigInteger operator *(BigInteger left, BigInteger right) + { + left.AssertValid(); + right.AssertValid(); + + var sign = +1; + var reg1 = new BigIntegerBuilder(left, ref sign); + var reg2 = new BigIntegerBuilder(right, ref sign); + + reg1.Mul(ref reg2); + return reg1.GetInteger(sign); + } + + public static BigInteger operator /(BigInteger dividend, BigInteger divisor) + { + dividend.AssertValid(); + divisor.AssertValid(); + + var sign = +1; + var regNum = new BigIntegerBuilder(dividend, ref sign); + var regDen = new BigIntegerBuilder(divisor, ref sign); + + regNum.Div(ref regDen); + return regNum.GetInteger(sign); + } + + public static BigInteger operator %(BigInteger dividend, BigInteger divisor) + { + dividend.AssertValid(); + divisor.AssertValid(); + + var signNum = +1; + var signDen = +1; + var regNum = new BigIntegerBuilder(dividend, ref signNum); + var regDen = new BigIntegerBuilder(divisor, ref signDen); + + regNum.Mod(ref regDen); + return regNum.GetInteger(signNum); + }*/ + + public static bool operator <(BigInteger left, BigInteger right) + { + return left.CompareTo(right) < 0; + } + public static bool operator <=(BigInteger left, BigInteger right) + { + return left.CompareTo(right) <= 0; + } + public static bool operator >(BigInteger left, BigInteger right) + { + return left.CompareTo(right) > 0; + } + public static bool operator >=(BigInteger left, BigInteger right) + { + return left.CompareTo(right) >= 0; + } + public static bool operator ==(BigInteger left, BigInteger right) + { + return left.Equals(right); + } + public static bool operator !=(BigInteger left, BigInteger right) + { + return !left.Equals(right); + } + + /*public static bool operator <(BigInteger left, Int64 right) + { + return left.CompareTo(right) < 0; + } + public static bool operator <=(BigInteger left, Int64 right) + { + return left.CompareTo(right) <= 0; + } + public static bool operator >(BigInteger left, Int64 right) + { + return left.CompareTo(right) > 0; + } + public static bool operator >=(BigInteger left, Int64 right) + { + return left.CompareTo(right) >= 0; + } + public static bool operator ==(BigInteger left, Int64 right) + { + return left.Equals(right); + } + public static bool operator !=(BigInteger left, Int64 right) + { + return !left.Equals(right); + } + + public static bool operator <(Int64 left, BigInteger right) + { + return right.CompareTo(left) > 0; + } + public static bool operator <=(Int64 left, BigInteger right) + { + return right.CompareTo(left) >= 0; + } + public static bool operator >(Int64 left, BigInteger right) + { + return right.CompareTo(left) < 0; + } + public static bool operator >=(Int64 left, BigInteger right) + { + return right.CompareTo(left) <= 0; + } + public static bool operator ==(Int64 left, BigInteger right) + { + return right.Equals(left); + } + public static bool operator !=(Int64 left, BigInteger right) + { + return !right.Equals(left); + } + + public static bool operator <(BigInteger left, UInt64 right) + { + return left.CompareTo(right) < 0; + } + public static bool operator <=(BigInteger left, UInt64 right) + { + return left.CompareTo(right) <= 0; + } + public static bool operator >(BigInteger left, UInt64 right) + { + return left.CompareTo(right) > 0; + } + public static bool operator >=(BigInteger left, UInt64 right) + { + return left.CompareTo(right) >= 0; + } + public static bool operator ==(BigInteger left, UInt64 right) + { + return left.Equals(right); + } + public static bool operator !=(BigInteger left, UInt64 right) + { + return !left.Equals(right); + } + + public static bool operator <(UInt64 left, BigInteger right) + { + return right.CompareTo(left) > 0; + } + public static bool operator <=(UInt64 left, BigInteger right) + { + return right.CompareTo(left) >= 0; + } + public static bool operator >(UInt64 left, BigInteger right) + { + return right.CompareTo(left) < 0; + } + public static bool operator >=(UInt64 left, BigInteger right) + { + return right.CompareTo(left) <= 0; + } + public static bool operator ==(UInt64 left, BigInteger right) + { + return right.Equals(left); + } + public static bool operator !=(UInt64 left, BigInteger right) + { + return !right.Equals(left); + }*/ + + #endregion internal static operators + + + // ----- SECTION: private serialization instance methods ---------------- + #region private serialization instance methods + #endregion private serialization instance methods + + + // ----- SECTION: internal instance utility methods ----------------* + #region internal instance utility methods + + /*private void SetBitsFromDouble(Double value) + { + int sign, exp; + ulong man; + bool fFinite; + NumericsHelpers.GetDoubleParts(value, out sign, out exp, out man, out fFinite); + Contract.Assert(sign == +1 || sign == -1); + + if (man == 0) + { + this = Zero; + return; + } + + Contract.Assert(man < 1UL << 53); + Contract.Assert(exp <= 0 || man >= 1UL << 52); + + if (exp <= 0) + { + if (exp <= -kcbitUlong) + { + this = Zero; + return; + } + this = man >> -exp; + if (sign < 0) + _sign = -_sign; + } + else if (exp <= 11) + { + this = man << exp; + if (sign < 0) + _sign = -_sign; + } + else + { + // Overflow into at least 3 uints. + // Move the leading 1 to the high bit. + man <<= 11; + exp -= 11; + + // Compute cu and cbit so that exp == 32 * cu - cbit and 0 <= cbit < 32. + var cu = (exp - 1) / kcbitUint + 1; + var cbit = cu * kcbitUint - exp; + Contract.Assert(0 <= cbit && cbit < kcbitUint); + Contract.Assert(cu >= 1); + + // Populate the uints. + _bits = new uint[cu + 2]; + _bits[cu + 1] = (uint)(man >> (cbit + kcbitUint)); + _bits[cu] = (uint)(man >> cbit); + if (cbit > 0) + _bits[cu - 1] = (uint)man << (kcbitUint - cbit); + _sign = sign; + } + }*/ + #endregion internal instance utility methods + + + // ----- SECTION: internal static utility methods ----------------* + #region internal static utility methods + //[Pure] + private static int Length(uint[] rgu) + { + var cu = rgu.Length; + if (rgu[cu - 1] != 0) + return cu; + Contract.Assert(cu >= 2 && rgu[cu - 2] != 0); + return cu - 1; + } + + internal int _Sign { get { return _sign; } } + internal uint[] _Bits { get { return _bits; } } + + +/* + internal static int BitLengthOfUInt(uint x) + { + var numBits = 0; + while (x > 0) + { + x >>= 1; + numBits++; + } + return numBits; + } +*/ + + // + // GetPartsForBitManipulation - + // + // Encapsulate the logic of normalizing the "small" and "large" forms of BigInteger + // into the "large" form so that Bit Manipulation algorithms can be simplified + // + // uint[] xd = the UInt32 array containing the entire big integer in "large" (denormalized) form + // E.g., the number one (1) and negative one (-1) are both stored as 0x00000001 + // BigInteger values Int32.MinValue < x <= Int32.MaxValue are converted to this + // format for convenience. + // int xl = the length of xd + // return bool = true for negative numbers + // + /*private static bool GetPartsForBitManipulation(ref BigInteger x, out uint[] xd, out int xl) + { + if (x._bits == null) + { + xd = x._sign < 0 ? new[] { (uint)-x._sign } : new[] { (uint)x._sign }; + } + else + { + xd = x._bits; + } + xl = x._bits == null ? 1 : x._bits.Length; + return x._sign < 0; + }*/ + + // Gets an upper bound on the product of uHiRes * (2^32)^(cuRes-1) and uHiMul * (2^32)^(cuMul-1). + // The result is put int uHiRes and cuRes. +/* + private static void MulUpper(ref uint uHiRes, ref int cuRes, uint uHiMul, int cuMul) + { + var uu = (ulong)uHiRes * uHiMul; + var uHi = NumericsHelpers.GetHi(uu); + if (uHi != 0) + { + if (NumericsHelpers.GetLo(uu) != 0 && ++uHi == 0) + { + uHi = 1; + cuRes++; + } + uHiRes = uHi; + cuRes += cuMul; + } + else + { + uHiRes = NumericsHelpers.GetLo(uu); + cuRes += cuMul - 1; + } + } +*/ + + // Gets a lower bound on the product of uHiRes * (2^32)^(cuRes-1) and uHiMul * (2^32)^(cuMul-1). + // The result is put int uHiRes and cuRes. +/* + private static void MulLower(ref uint uHiRes, ref int cuRes, uint uHiMul, int cuMul) + { + var uu = (ulong)uHiRes * uHiMul; + var uHi = NumericsHelpers.GetHi(uu); + if (uHi != 0) + { + uHiRes = uHi; + cuRes += cuMul; + } + else + { + uHiRes = NumericsHelpers.GetLo(uu); + cuRes += cuMul - 1; + } + } +*/ + + private static int GetDiffLength(uint[] rgu1, uint[] rgu2, int cu) + { + for (var iv = cu; --iv >= 0; ) + { + if (rgu1[iv] != rgu2[iv]) + return iv + 1; + } + return 0; + } + #endregion internal static utility methods + } +}
\ No newline at end of file diff --git a/runtime/VMProtect.Runtime/Numerics/BigIntegerBuilder.cs b/runtime/VMProtect.Runtime/Numerics/BigIntegerBuilder.cs new file mode 100644 index 0000000..02ec6aa --- /dev/null +++ b/runtime/VMProtect.Runtime/Numerics/BigIntegerBuilder.cs @@ -0,0 +1,1529 @@ +// ==++== +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// +// ==--== + +using System; + +using Contracts = System.Diagnostics.Debug; +using Contract = System.Diagnostics.Debug; +using Conditional = System.Diagnostics.ConditionalAttribute; + +// ReSharper disable once CheckNamespace +namespace Numerics +{ + /// <summary> + /// BigIntegerBuilder holds a multiprecision unsigned integer value. It is mutable and + /// supports common arithmetic operations. Be careful NOT to simply assign one + /// BigIntegerBuilder to another, unless you really know what you are doing. The proper + /// way to replicate a BigIntegerBuilder is via the constructor "BigIntegerBuilder(ref BigIntegerBuilder reg)", + /// or with reg1.Load(ref reg2). Using the ctor marks the buffer as shared so changing the + /// value of one register will not affect the other. Using Load copies the contents from + /// one to the other. Either way, the internal buffer isn't aliased incorrectly. + /// </summary> + internal struct BigIntegerBuilder + { + // ReSharper disable once InconsistentNaming + private const int kcbitUint = 32; + + // For a single uint, _iuLast is 0. + private int _iuLast; + + // Used if _iuLast == 0. + private uint _uSmall; + + // Used if _iuLast > 0. + private uint[] _rgu; + + // This is false whenever _rgu is null or is shared with a NewBigInteger + // or with another BigIntegerBuilder. + private bool _fWritable; + + [Conditional("DEBUG")] + // ReSharper disable once UnusedParameter.Local + private void AssertValid(bool fTrimmed) + { + if (_iuLast <= 0) + { + Contract.Assert(_iuLast == 0); + Contract.Assert(!_fWritable || _rgu != null); + } + else + { + Contract.Assert(_rgu != null && _rgu.Length > _iuLast); + Contract.Assert(!fTrimmed || _rgu[_iuLast] != 0); + } + } + +#if CONTRACTS_FULL + [ContractInvariantMethod] + private void ObjectInvariant() + { + Contract.Invariant(_iuLast >=0); + Contract.Invariant(!(_iuLast == 0) || (!_fWritable || _rgu != null)); + Contract.Invariant(!(_iuLast > 0) || (_rgu != null && _rgu.Length > _iuLast)); + } +#endif + +/* + internal BigIntegerBuilder(ref BigIntegerBuilder reg) + { + reg.AssertValid(true); + this = reg; + if (_fWritable) + { + _fWritable = false; + if (_iuLast == 0) + _rgu = null; + else + reg._fWritable = false; + } + AssertValid(true); + } +*/ + + internal BigIntegerBuilder(int cuAlloc) + { + _iuLast = 0; + _uSmall = 0; + if (cuAlloc > 1) + { + _rgu = new uint[cuAlloc]; + _fWritable = true; + } + else + { + _rgu = null; + _fWritable = false; + } + AssertValid(true); + } + +/* + internal BigIntegerBuilder(BigInteger bn) + { + _fWritable = false; + _rgu = bn._Bits; + if (_rgu == null) + { + _iuLast = 0; + _uSmall = NumericsHelpers.Abs(bn._Sign); + } + else + { + _iuLast = _rgu.Length - 1; + _uSmall = _rgu[0]; + while (_iuLast > 0 && _rgu[_iuLast] == 0) + --_iuLast; + } + AssertValid(true); + } +*/ + + internal BigIntegerBuilder(BigInteger bn, ref int sign) + { + Contract.Assert(sign == +1 || sign == -1); + + _fWritable = false; + _rgu = bn._Bits; + int n = bn._Sign; + int mask = n >> (kcbitUint - 1); + sign = (sign ^ mask) - mask; + if (_rgu == null) + { + _iuLast = 0; + _uSmall = (uint)((n ^ mask) - mask); + } + else + { + _iuLast = _rgu.Length - 1; + _uSmall = _rgu[0]; + while (_iuLast > 0 && _rgu[_iuLast] == 0) + --_iuLast; + } + AssertValid(true); + } + + internal BigInteger GetInteger(int sign) + { + Contract.Assert(sign == +1 || sign == -1); + AssertValid(true); + + uint[] bits; + GetIntegerParts(sign, out sign, out bits); + return new BigInteger(sign, bits); + } + + private void GetIntegerParts(int signSrc, out int sign, out uint[] bits) + { + Contract.Assert(signSrc == +1 || signSrc == -1); + AssertValid(true); + + if (_iuLast == 0) + { + if (_uSmall <= int.MaxValue) + { + sign = signSrc * (int)_uSmall; + bits = null; + return; + } + if (_rgu == null) + _rgu = new[] { _uSmall }; + else if (_fWritable) + _rgu[0] = _uSmall; + else if (_rgu[0] != _uSmall) + _rgu = new[] { _uSmall }; + } + + // The sign is +/- 1. + sign = signSrc; + + int cuExtra = _rgu.Length - _iuLast - 1; + Contract.Assert(cuExtra >= 0); + if (cuExtra <= 1) + { + if (cuExtra == 0 || _rgu[_iuLast + 1] == 0) + { + _fWritable = false; + bits = _rgu; + return; + } + if (_fWritable) + { + _rgu[_iuLast + 1] = 0; + _fWritable = false; + bits = _rgu; + return; + } + // The buffer isn't writable, but has an extra uint that is non-zero, + // so we have to allocate a new buffer. + } + + // Keep the bigger buffer (if it is writable), but create a smaller one for the BigInteger. + bits = _rgu; + Array.Resize(ref bits, _iuLast + 1); + if (!_fWritable) + _rgu = bits; + } + + private void Set(uint u) + { + _uSmall = u; + _iuLast = 0; + AssertValid(true); + } + + private void Set(ulong uu) + { + uint uHi = NumericsHelpers.GetHi(uu); + if (uHi == 0) + { + _uSmall = NumericsHelpers.GetLo(uu); + _iuLast = 0; + } + else + { + SetSizeLazy(2); + _rgu[0] = (uint) uu; + _rgu[1] = uHi; + } + } + + internal int Size { get { return _iuLast + 1; } } + + //internal uint High { get { return _iuLast == 0 ? _uSmall : _rgu[_iuLast]; } } + + + /*internal void GetApproxParts(out int exp, out ulong man) + { + AssertValid(true); + if (_iuLast == 0) + { + man = _uSmall; + exp = 0; + return; + } + + int cuLeft = _iuLast - 1; + man = NumericsHelpers.MakeUlong(_rgu[cuLeft + 1], _rgu[cuLeft]); + exp = cuLeft * kcbitUint; + + int cbit; + if (cuLeft > 0 && (cbit = NumericsHelpers.CbitHighZero(_rgu[cuLeft + 1])) > 0) + { + // Get 64 bits. + Contract.Assert(cbit < kcbitUint); + man = (man << cbit) | (_rgu[cuLeft - 1] >> (kcbitUint - cbit)); + exp -= cbit; + } + }*/ + + private void Trim() + { + AssertValid(false); + if (_iuLast > 0 && _rgu[_iuLast] == 0) + { + _uSmall = _rgu[0]; + while (--_iuLast > 0 && _rgu[_iuLast] == 0) + { + } + } + AssertValid(true); + } + + private int CuNonZero + { + get + { + Contract.Assert(_iuLast > 0); + int cu = 0; + for (int iu = _iuLast; iu >= 0; --iu) + { + if (_rgu[iu] != 0) + cu++; + } + return cu; + } + } + + // Sets the size to cu and makes sure the buffer is writable (if cu > 1), + // but makes no guarantees about the contents of the buffer. + private void SetSizeLazy(int cu) + { + Contract.Assert(cu > 0); + AssertValid(false); + if (cu <= 1) + { + _iuLast = 0; + return; + } + if (!_fWritable || _rgu.Length < cu) + { + _rgu = new uint[cu]; + _fWritable = true; + } + _iuLast = cu - 1; + AssertValid(false); + } + + // Sets the size to cu, makes sure the buffer is writable (if cu > 1), + // and set the contents to all zero. + private void SetSizeClear(int cu) + { + Contract.Assert(cu > 0); + AssertValid(false); + if (cu <= 1) + { + _iuLast = 0; + _uSmall = 0; + return; + } + if (!_fWritable || _rgu.Length < cu) + { + _rgu = new uint[cu]; + _fWritable = true; + } + else + Array.Clear(_rgu, 0, cu); + _iuLast = cu - 1; + AssertValid(false); + } + + // Sets the size to cu, makes sure the buffer is writable (if cu > 1), + // and maintains the contents. If the buffer is reallocated, cuExtra + // uints are also allocated. + private void SetSizeKeep(int cu, int cuExtra) + { + Contract.Assert(cu > 0 && cuExtra >= 0); + AssertValid(false); + + if (cu <= 1) + { + if (_iuLast > 0) + _uSmall = _rgu[0]; + _iuLast = 0; + return; + } + if (!_fWritable || _rgu.Length < cu) + { + uint[] rgu = new uint[cu + cuExtra]; + if (_iuLast == 0) + rgu[0] = _uSmall; + else + Array.Copy(_rgu, rgu, Math.Min(cu, _iuLast + 1)); + _rgu = rgu; + _fWritable = true; + } + else if (_iuLast + 1 < cu) + { + Array.Clear(_rgu, _iuLast + 1, cu - _iuLast - 1); + if (_iuLast == 0) + _rgu[0] = _uSmall; + } + _iuLast = cu - 1; + AssertValid(false); + } + + // Makes sure the buffer is writable and can support cu uints. + // Preserves the contents of the buffer up to min(_iuLast + 1, cu). + // Changes the size if cu <= _iuLast and the buffer needs to be allocated. +/* + internal void EnsureWritable(int cu, int cuExtra) + { + Contract.Assert(cu > 1 && cuExtra >= 0); + AssertValid(false); + + if (_fWritable && _rgu.Length >= cu) + return; + + uint[] rgu = new uint[cu + cuExtra]; + if (_iuLast > 0) + { + if (_iuLast >= cu) + _iuLast = cu - 1; + Array.Copy(_rgu, rgu, _iuLast + 1); + } + _rgu = rgu; + _fWritable = true; + AssertValid(false); + } +*/ + + // Makes sure the buffer is writable and can support _iuLast + 1 uints. + // Preserves the contents of the buffer. + private void EnsureWritable(int cuExtra = 0) + { + Contract.Assert(cuExtra >= 0); + AssertValid(false); + Contract.Assert(_iuLast > 0); + + if (_fWritable) + return; + + uint[] rgu = new uint[_iuLast + 1 + cuExtra]; + Array.Copy(_rgu, rgu, _iuLast + 1); + _rgu = rgu; + _fWritable = true; + AssertValid(false); + } + + // Loads the value of reg into this register. + /*internal void Load(ref BigIntegerBuilder reg) + { + Load(ref reg, 0); + }*/ + + // Loads the value of reg into this register. If we need to allocate memory + // to perform the load, allocate cuExtra elements. + private void Load(ref BigIntegerBuilder reg, int cuExtra) + { + Contract.Assert(cuExtra >= 0); + AssertValid(false); + reg.AssertValid(true); + + if (reg._iuLast == 0) + { + _uSmall = reg._uSmall; + _iuLast = 0; + } + else + { + if (!_fWritable || _rgu.Length <= reg._iuLast) + { + _rgu = new uint[reg._iuLast + 1 + cuExtra]; + _fWritable = true; + } + _iuLast = reg._iuLast; + Array.Copy(reg._rgu, _rgu, _iuLast + 1); + } + AssertValid(true); + } + + /*internal void Add(uint u) + { + AssertValid(true); + if (_iuLast == 0) + { + if ((_uSmall += u) >= u) + return; + SetSizeLazy(2); + _rgu[0] = _uSmall; + _rgu[1] = 1; + return; + } + + if (u == 0) + return; + + uint uNew = _rgu[0] + u; + if (uNew < u) + { + // Have carry. + EnsureWritable(1); + ApplyCarry(1); + } + else if (!_fWritable) + EnsureWritable(); + _rgu[0] = uNew; + AssertValid(true); + } + + internal void Add(ref BigIntegerBuilder reg) + { + AssertValid(true); + reg.AssertValid(true); + + if (reg._iuLast == 0) + { + Add(reg._uSmall); + return; + } + if (_iuLast == 0) + { + uint u = _uSmall; + if (u == 0) + this = new BigIntegerBuilder(ref reg); + else + { + Load(ref reg, 1); + Add(u); + } + return; + } + + EnsureWritable(Math.Max(_iuLast, reg._iuLast) + 1, 1); + + int cuAdd = reg._iuLast + 1; + if (_iuLast < reg._iuLast) + { + cuAdd = _iuLast + 1; + Array.Copy(reg._rgu, _iuLast + 1, _rgu, _iuLast + 1, reg._iuLast - _iuLast); + Contract.Assert(_iuLast > 0); + _iuLast = reg._iuLast; + } + + // Add, tracking carry. + uint uCarry = 0; + for (int iu = 0; iu < cuAdd; iu++) + { + uCarry = AddCarry(ref _rgu[iu], reg._rgu[iu], uCarry); + Contract.Assert(uCarry <= 1); + } + + // Deal with extra carry. + if (uCarry != 0) + ApplyCarry(cuAdd); + AssertValid(true); + } + + internal void Sub(ref int sign, uint u) + { + Contract.Assert(sign == +1 || sign == -1); + AssertValid(true); + if (_iuLast == 0) + { + if (u <= _uSmall) + _uSmall -= u; + else + { + _uSmall = u - _uSmall; + sign = -sign; + } + AssertValid(true); + return; + } + + if (u == 0) + return; + + EnsureWritable(); + + uint uTmp = _rgu[0]; + _rgu[0] = uTmp - u; + if (uTmp < u) + { + ApplyBorrow(1); + Trim(); + } + AssertValid(true); + } + + internal void Sub(ref int sign, ref BigIntegerBuilder reg) + { + Contract.Assert(sign == +1 || sign == -1); + AssertValid(true); + reg.AssertValid(true); + + if (reg._iuLast == 0) + { + Sub(ref sign, reg._uSmall); + return; + } + if (_iuLast == 0) + { + uint u = _uSmall; + if (u == 0) + this = new BigIntegerBuilder(ref reg); + else + { + Load(ref reg); + Sub(ref sign, u); + } + sign = -sign; + return; + } + + if (_iuLast < reg._iuLast) + { + SubRev(ref reg); + sign = -sign; + return; + } + + int cuSub = reg._iuLast + 1; + if (_iuLast == reg._iuLast) + { + // Determine which is larger. + _iuLast = BigInteger.GetDiffLength(_rgu, reg._rgu, _iuLast + 1) - 1; + if (_iuLast < 0) + { + _iuLast = 0; + _uSmall = 0; + return; + } + + uint u1 = _rgu[_iuLast]; + uint u2 = reg._rgu[_iuLast]; + if (_iuLast == 0) + { + if (u1 < u2) + { + _uSmall = u2 - u1; + sign = -sign; + } + else + _uSmall = u1 - u2; + AssertValid(true); + return; + } + + if (u1 < u2) + { + Contract.Assert(_iuLast > 0); + reg._iuLast = _iuLast; + SubRev(ref reg); + reg._iuLast = cuSub - 1; + Contract.Assert(reg._iuLast > 0); + sign = -sign; + return; + } + cuSub = _iuLast + 1; + } + + EnsureWritable(); + + // Subtract, tracking borrow. + uint uBorrow = 0; + for (int iu = 0; iu < cuSub; iu++) + { + uBorrow = SubBorrow(ref _rgu[iu], reg._rgu[iu], uBorrow); + Contract.Assert(uBorrow <= 1); + } + if (uBorrow != 0) + { + Contract.Assert(uBorrow == 1 && cuSub <= _iuLast); + ApplyBorrow(cuSub); + } + Trim(); + } + + // Subtract this register from the given one and put the result in this one. + // Asserts that reg is larger in the most significant uint. + private void SubRev(ref BigIntegerBuilder reg) + { + Contract.Assert(0 < _iuLast && _iuLast <= reg._iuLast); + Contract.Assert(_iuLast < reg._iuLast || _rgu[_iuLast] < reg._rgu[_iuLast]); + + EnsureWritable(reg._iuLast + 1, 0); + + int cuSub = _iuLast + 1; + if (_iuLast < reg._iuLast) + { + Array.Copy(reg._rgu, _iuLast + 1, _rgu, _iuLast + 1, reg._iuLast - _iuLast); + Contract.Assert(_iuLast > 0); + _iuLast = reg._iuLast; + } + + uint uBorrow = 0; + for (int iu = 0; iu < cuSub; iu++) + { + uBorrow = SubRevBorrow(ref _rgu[iu], reg._rgu[iu], uBorrow); + Contract.Assert(uBorrow <= 1); + } + if (uBorrow != 0) + { + Contract.Assert(uBorrow == 1); + ApplyBorrow(cuSub); + } + Trim(); + }*/ + + private void Mul(uint u) + { + if (u == 0) + { + Set(0); + return; + } + if (u == 1) + return; + + if (_iuLast == 0) + { + Set((ulong)_uSmall * u); + return; + } + + EnsureWritable(1); + + uint uCarry = 0; + for (int iu = 0; iu <= _iuLast; iu++) + uCarry = MulCarry(ref _rgu[iu], u, uCarry); + + if (uCarry != 0) + { + SetSizeKeep(_iuLast + 2, 0); + _rgu[_iuLast] = uCarry; + } + } + + // This version may share memory with regMul. + /*internal void Mul(ref BigIntegerBuilder regMul) + { + AssertValid(true); + regMul.AssertValid(true); + + if (regMul._iuLast == 0) + Mul(regMul._uSmall); + else if (_iuLast == 0) + { + uint u = _uSmall; + if (u == 1) + this = new BigIntegerBuilder(ref regMul); + else if (u != 0) + { + Load(ref regMul, 1); + Mul(u); + } + } + else + { + int cuBase = _iuLast + 1; + SetSizeKeep(cuBase + regMul._iuLast, 1); + + for (int iu = cuBase; --iu >= 0; ) + { + uint uMul = _rgu[iu]; + _rgu[iu] = 0; + uint uCarry = 0; + for (int iuSrc = 0; iuSrc <= regMul._iuLast; iuSrc++) + uCarry = AddMulCarry(ref _rgu[iu + iuSrc], regMul._rgu[iuSrc], uMul, uCarry); + if (uCarry != 0) + { + for (int iuDst = iu + regMul._iuLast + 1; uCarry != 0 && iuDst <= _iuLast; iuDst++) + uCarry = AddCarry(ref _rgu[iuDst], 0, uCarry); + if (uCarry != 0) + { + SetSizeKeep(_iuLast + 2, 0); + _rgu[_iuLast] = uCarry; + } + } + } + AssertValid(true); + } + }*/ + + // Multiply reg1 times reg2, putting the result in 'this'. This version never shares memory + // with either of the operands. This is useful when performing a series of arithmetic operations + // and large working buffers are allocated up front. + internal void Mul(ref BigIntegerBuilder reg1, ref BigIntegerBuilder reg2) + { + AssertValid(true); + reg1.AssertValid(true); + reg2.AssertValid(true); + + if (reg1._iuLast == 0) + { + if (reg2._iuLast == 0) + Set((ulong)reg1._uSmall * reg2._uSmall); + else + { + Load(ref reg2, 1); + Mul(reg1._uSmall); + } + } + else if (reg2._iuLast == 0) + { + Load(ref reg1, 1); + Mul(reg2._uSmall); + } + else + { + Contract.Assert(reg1._iuLast > 0 && reg2._iuLast > 0); + SetSizeClear(reg1._iuLast + reg2._iuLast + 2); + + uint[] rgu1, rgu2; + int cu1, cu2; + + // We prefer more iterations on the inner loop and fewer on the outer. + if (reg1.CuNonZero <= reg2.CuNonZero) + { + rgu1 = reg1._rgu; cu1 = reg1._iuLast + 1; + rgu2 = reg2._rgu; cu2 = reg2._iuLast + 1; + } + else + { + rgu1 = reg2._rgu; cu1 = reg2._iuLast + 1; + rgu2 = reg1._rgu; cu2 = reg1._iuLast + 1; + } + + for (int iu1 = 0; iu1 < cu1; iu1++) + { + uint uCur = rgu1[iu1]; + if (uCur == 0) + continue; + + uint uCarry = 0; + int iuRes = iu1; + for (int iu2 = 0; iu2 < cu2; iu2++, iuRes++) + uCarry = AddMulCarry(ref _rgu[iuRes], uCur, rgu2[iu2], uCarry); + while (uCarry != 0) + uCarry = AddCarry(ref _rgu[iuRes++], 0, uCarry); + } + Trim(); + } + } + + // Divide 'this' by uDen, leaving the quotient in 'this' and returning the remainder. + /*internal uint DivMod(uint uDen) + { + AssertValid(true); + + if (uDen == 1) + return 0; + if (_iuLast == 0) + { + uint uTmp = _uSmall; + _uSmall = uTmp / uDen; + return uTmp % uDen; + } + + EnsureWritable(); + + ulong uu = 0; + for (int iv = _iuLast; iv >= 0; iv--) + { + uu = NumericsHelpers.MakeUlong((uint)uu, _rgu[iv]); + _rgu[iv] = (uint)(uu / uDen); + uu %= uDen; + } + Trim(); + return (uint)uu; + }*/ + + // Divide regNum by uDen, returning the remainder and tossing the quotient. + private static uint Mod(ref BigIntegerBuilder regNum, uint uDen) + { + regNum.AssertValid(true); + + if (uDen == 1) + return 0; + if (regNum._iuLast == 0) + return regNum._uSmall % uDen; + + ulong uu = 0; + for (int iv = regNum._iuLast; iv >= 0; iv--) + { + uu = NumericsHelpers.MakeUlong((uint)uu, regNum._rgu[iv]); + uu %= uDen; + } + return (uint)uu; + } + + // Divide 'this' by regDen, leaving the remainder in 'this' and tossing the quotient. + internal void Mod(ref BigIntegerBuilder regDen) + { + AssertValid(true); + regDen.AssertValid(true); + + if (regDen._iuLast == 0) + { + Set(Mod(ref this, regDen._uSmall)); + return; + } + if (_iuLast == 0) + return; + + BigIntegerBuilder regTmp = new BigIntegerBuilder(); + ModDivCore(ref this, ref regDen, false, ref regTmp); + } + + // Divide 'this' by regDen, leaving the quotient in 'this' and tossing the remainder. + /*internal void Div(ref BigIntegerBuilder regDen) + { + AssertValid(true); + regDen.AssertValid(true); + + if (regDen._iuLast == 0) + { + DivMod(regDen._uSmall); + return; + } + if (_iuLast == 0) + { + _uSmall = 0; + return; + } + + BigIntegerBuilder regTmp = new BigIntegerBuilder(); + ModDivCore(ref this, ref regDen, true, ref regTmp); + NumericsHelpers.Swap(ref this, ref regTmp); + }*/ + + // Divide regNum by regDen, leaving the remainder in regNum and the quotient in regQuo (if fQuo is true). +/* + internal void ModDiv(ref BigIntegerBuilder regDen, ref BigIntegerBuilder regQuo) + { + if (regDen._iuLast == 0) + { + regQuo.Set(DivMod(regDen._uSmall)); + NumericsHelpers.Swap(ref this, ref regQuo); + return; + } + if (_iuLast == 0) + return; + + ModDivCore(ref this, ref regDen, true, ref regQuo); + } +*/ + + private static void ModDivCore(ref BigIntegerBuilder regNum, ref BigIntegerBuilder regDen, bool fQuo, ref BigIntegerBuilder regQuo) + { + Contract.Assert(regNum._iuLast > 0 && regDen._iuLast > 0); + + regQuo.Set(0); + if (regNum._iuLast < regDen._iuLast) + return; + + Contract.Assert(0 < regDen._iuLast && regDen._iuLast <= regNum._iuLast); + int cuDen = regDen._iuLast + 1; + int cuDiff = regNum._iuLast - regDen._iuLast; + + // Determine whether the result will have cuDiff "digits" or cuDiff+1 "digits". + int cuQuo = cuDiff; + for (int iu = regNum._iuLast; ; iu--) + { + if (iu < cuDiff) + { + cuQuo++; + break; + } + if (regDen._rgu[iu - cuDiff] != regNum._rgu[iu]) + { + if (regDen._rgu[iu - cuDiff] < regNum._rgu[iu]) + cuQuo++; + break; + } + } + + if (cuQuo == 0) + return; + + if (fQuo) + regQuo.SetSizeLazy(cuQuo); + + // Get the uint to use for the trial divisions. We normalize so the high bit is set. + uint uDen = regDen._rgu[cuDen - 1]; + uint uDenNext = regDen._rgu[cuDen - 2]; + int cbitShiftLeft = NumericsHelpers.CbitHighZero(uDen); + int cbitShiftRight = kcbitUint - cbitShiftLeft; + if (cbitShiftLeft > 0) + { + uDen = (uDen << cbitShiftLeft) | (uDenNext >> cbitShiftRight); + uDenNext <<= cbitShiftLeft; + if (cuDen > 2) + uDenNext |= regDen._rgu[cuDen - 3] >> cbitShiftRight; + } + Contract.Assert((uDen & 0x80000000) != 0); + + // Allocate and initialize working space. + Contract.Assert(cuQuo + cuDen == regNum._iuLast + 1 || cuQuo + cuDen == regNum._iuLast + 2); + regNum.EnsureWritable(); + + for (int iu = cuQuo; --iu >= 0; ) + { + // Get the high (normalized) bits of regNum. + uint uNumHi = iu + cuDen <= regNum._iuLast ? regNum._rgu[iu + cuDen] : 0; + Contract.Assert(uNumHi <= regDen._rgu[cuDen - 1]); + + ulong uuNum = NumericsHelpers.MakeUlong(uNumHi, regNum._rgu[iu + cuDen - 1]); + uint uNumNext = regNum._rgu[iu + cuDen - 2]; + if (cbitShiftLeft > 0) + { + uuNum = (uuNum << cbitShiftLeft) | (uNumNext >> cbitShiftRight); + uNumNext <<= cbitShiftLeft; + if (iu + cuDen >= 3) + uNumNext |= regNum._rgu[iu + cuDen - 3] >> cbitShiftRight; + } + + // Divide to get the quotient digit. + ulong uuQuo = uuNum / uDen; + ulong uuRem = (uint)(uuNum % uDen); + Contract.Assert(uuQuo <= (ulong)uint.MaxValue + 2); + if (uuQuo > uint.MaxValue) + { + uuRem += uDen * (uuQuo - uint.MaxValue); + uuQuo = uint.MaxValue; + } + while (uuRem <= uint.MaxValue && uuQuo * uDenNext > NumericsHelpers.MakeUlong((uint)uuRem, uNumNext)) + { + uuQuo--; + uuRem += uDen; + } + + // Multiply and subtract. Note that uuQuo may be 1 too large. If we have a borrow + // at the end, we'll add the denominator back on and decrement uuQuo. + if (uuQuo > 0) + { + ulong uuBorrow = 0; + for (int iu2 = 0; iu2 < cuDen; iu2++) + { + uuBorrow += regDen._rgu[iu2] * uuQuo; + uint uSub = (uint)uuBorrow; + uuBorrow >>= kcbitUint; + if (regNum._rgu[iu + iu2] < uSub) + uuBorrow++; + regNum._rgu[iu + iu2] -= uSub; + } + + Contract.Assert(uNumHi == uuBorrow || uNumHi == uuBorrow - 1); + if (uNumHi < uuBorrow) + { + // Add, tracking carry. + uint uCarry = 0; + for (int iu2 = 0; iu2 < cuDen; iu2++) + { + uCarry = AddCarry(ref regNum._rgu[iu + iu2], regDen._rgu[iu2], uCarry); + Contract.Assert(uCarry <= 1); + } + Contract.Assert(uCarry == 1); + uuQuo--; + } + regNum._iuLast = iu + cuDen - 1; + } + + if (fQuo) + { + if (cuQuo == 1) + regQuo._uSmall = (uint)uuQuo; + else + regQuo._rgu[iu] = (uint)uuQuo; + } + } + + Contract.Assert(cuDen > 1 && regNum._iuLast > 0); + regNum._iuLast = cuDen - 1; + regNum.Trim(); + } + + //private static readonly double kdblLn2To32 = 32 * Math.Log(2); + + /*internal void ShiftRight(int cbit) + { + AssertValid(true); + if (cbit <= 0) + { + if (cbit < 0) + ShiftLeft(-cbit); + return; + } + ShiftRight(cbit / kcbitUint, cbit % kcbitUint); + } + + internal void ShiftRight(int cuShift, int cbitShift) + { + Contract.Assert(cuShift >= 0); + Contract.Assert(0 <= cbitShift); + Contract.Assert(cbitShift < kcbitUint); + AssertValid(true); + + if ((cuShift | cbitShift) == 0) + return; + if (cuShift > _iuLast) + { + Set(0); + return; + } + if (_iuLast == 0) + { + _uSmall >>= cbitShift; + AssertValid(true); + return; + } + + uint[] rguSrc = _rgu; + int cuSrc = _iuLast + 1; + _iuLast -= cuShift; + if (_iuLast == 0) + _uSmall = rguSrc[cuShift] >> cbitShift; + else + { + Contract.Assert(_rgu.Length > _iuLast); + if (!_fWritable) + { + _rgu = new uint[_iuLast + 1]; + _fWritable = true; + } + if (cbitShift > 0) + { + for (int iuSrc = cuShift + 1, iuDst = 0; iuSrc < cuSrc; iuSrc++, iuDst++) + _rgu[iuDst] = (rguSrc[iuSrc - 1] >> cbitShift) | (rguSrc[iuSrc] << (kcbitUint - cbitShift)); + _rgu[_iuLast] = rguSrc[cuSrc - 1] >> cbitShift; + Trim(); + } + else + Array.Copy(rguSrc, cuShift, _rgu, 0, _iuLast + 1); + } + AssertValid(true); + }*/ + + /*internal void ShiftLeft(int cbit) + { + AssertValid(true); + if (cbit <= 0) + { + if (cbit < 0) + ShiftRight(-cbit); + return; + } + ShiftLeft(cbit / kcbitUint, cbit % kcbitUint); + } + + internal void ShiftLeft(int cuShift, int cbitShift) + { + Contract.Assert(cuShift >= 0); + Contract.Assert(0 <= cbitShift); + Contract.Assert(cbitShift < kcbitUint); + AssertValid(true); + + int iuLastNew = _iuLast + cuShift; + uint uHigh = 0; + if (cbitShift > 0) + { + uHigh = High >> (kcbitUint - cbitShift); + if (uHigh != 0) + iuLastNew++; + } + if (iuLastNew == 0) + { + _uSmall <<= cbitShift; + return; + } + + uint[] rguSrc = _rgu; + bool fClearLow = cuShift > 0; + if (!_fWritable || _rgu.Length <= iuLastNew) + { + _rgu = new uint[iuLastNew + 1]; + _fWritable = true; + fClearLow = false; + } + if (_iuLast == 0) + { + if (uHigh != 0) + _rgu[cuShift + 1] = uHigh; + _rgu[cuShift] = _uSmall << cbitShift; + } + else if (cbitShift == 0) + Array.Copy(rguSrc, 0, _rgu, cuShift, _iuLast + 1); + else + { + int iuSrc = _iuLast; + int iuDst = _iuLast + cuShift; + if (iuDst < iuLastNew) + _rgu[iuLastNew] = uHigh; + for (; iuSrc > 0; iuSrc--, iuDst--) + _rgu[iuDst] = (rguSrc[iuSrc] << cbitShift) | (rguSrc[iuSrc - 1] >> (kcbitUint - cbitShift)); + _rgu[cuShift] = rguSrc[0] << cbitShift; + } + _iuLast = iuLastNew; + if (fClearLow) + Array.Clear(_rgu, 0, cuShift); + }*/ + + // Get the high two uints, combined into a ulong, zero extending to + // length cu if necessary. Asserts cu > _iuLast and _iuLast > 0. +/* + private ulong GetHigh2(int cu) + { + Contract.Assert(cu >= 2); + Contract.Assert(_iuLast > 0); + Contract.Assert(cu > _iuLast); + + if (cu - 1 <= _iuLast) + return NumericsHelpers.MakeUlong(_rgu[cu - 1], _rgu[cu - 2]); + if (cu - 2 == _iuLast) + return _rgu[cu - 2]; + return 0; + } +*/ + + // Apply a single carry starting at iu, extending the register + // if needed. +/* + private void ApplyCarry(int iu) + { + Contract.Assert(0 <= iu); + Contract.Assert(_fWritable && _iuLast > 0); + Contract.Assert(iu <= _iuLast + 1); + + for (; ; iu++) + { + if (iu > _iuLast) + { + if (_iuLast + 1 == _rgu.Length) + Array.Resize(ref _rgu, _iuLast + 2); + _rgu[++_iuLast] = 1; + break; + } + if (++_rgu[iu] > 0) + break; + } + } +*/ + + // Apply a single borrow starting at iu. This does NOT trim the result. +/* + private void ApplyBorrow(int iuMin) + { + Contract.Assert(0 < iuMin); + Contract.Assert(_fWritable && _iuLast > 0); + Contract.Assert(iuMin <= _iuLast); + + for (int iu = iuMin; iu <= _iuLast; iu++) + { + uint u = _rgu[iu]--; + if (u > 0) + return; + } + // Borrowed off the end! + Contract.Assert(false, "Invalid call to ApplyBorrow"); + } +*/ + + private static uint AddCarry(ref uint u1, uint u2, uint uCarry) + { + ulong uu = (ulong)u1 + u2 + uCarry; + u1 = (uint)uu; + return (uint)(uu >> kcbitUint); + } + + /*private static uint SubBorrow(ref uint u1, uint u2, uint uBorrow) + { + ulong uu = (ulong)u1 - u2 - uBorrow; + u1 = (uint)uu; + return (uint)-(int)(uu >> kcbitUint); + } + + private static uint SubRevBorrow(ref uint u1, uint u2, uint uBorrow) + { + ulong uu = (ulong)u2 - u1 - uBorrow; + u1 = (uint)uu; + return (uint)-(int)(uu >> kcbitUint); + }*/ + + private static uint MulCarry(ref uint u1, uint u2, uint uCarry) + { + // This is guaranteed not to overflow. + ulong uuRes = (ulong)u1 * u2 + uCarry; + u1 = (uint)uuRes; + return (uint)(uuRes >> kcbitUint); + } + + private static uint AddMulCarry(ref uint uAdd, uint uMul1, uint uMul2, uint uCarry) + { + // This is guaranteed not to overflow. + ulong uuRes = (ulong)uMul1 * uMul2 + uAdd + uCarry; + uAdd = (uint)uuRes; + return (uint)(uuRes >> kcbitUint); + } + + // ReSharper disable once InconsistentNaming +/* + internal static void GCD(ref BigIntegerBuilder reg1, ref BigIntegerBuilder reg2) + { + // Use Lehmer's GCD, with improvements, after eliminating common powers of 2. + if (reg1._iuLast > 0 && reg1._rgu[0] == 0 || reg2._iuLast > 0 && reg2._rgu[0] == 0) + { + int cbit1 = reg1.MakeOdd(); + int cbit2 = reg2.MakeOdd(); + LehmerGcd(ref reg1, ref reg2); + int cbitMin = Math.Min(cbit1, cbit2); + if (cbitMin > 0) + reg1.ShiftLeft(cbitMin); + } + else + LehmerGcd(ref reg1, ref reg2); + } +*/ + + // This leaves the GCD in reg1 and trash in reg2. + // This uses Lehmer's method, with test due to Jebelean / Belnkiy and Vidunas. + // See Knuth, vol 2, page 345; Jebelean (1993) "Improving the Multiprecision Euclidean Algorithm"; + // and Belenkiy & Vidunas (1998) "A Greatest Common Divisor Algorithm". +/* + private static void LehmerGcd(ref BigIntegerBuilder reg1, ref BigIntegerBuilder reg2) + { + // This value has no real significance. Occ----ionally we want to subtract + // the two registers and keep the absolute value of the difference. To do + // so we need to pass a ref sign to Sub. + int signTmp = +1; + + for (; ; ) + { + reg1.AssertValid(true); + reg2.AssertValid(true); + + int cuMax = reg1._iuLast + 1; + int cuMin = reg2._iuLast + 1; + if (cuMax < cuMin) + { + NumericsHelpers.Swap(ref reg1, ref reg2); + NumericsHelpers.Swap(ref cuMax, ref cuMin); + } + Contract.Assert(cuMax == reg1._iuLast + 1); + Contract.Assert(cuMin == reg2._iuLast + 1); + + if (cuMin == 1) + { + if (cuMax == 1) + reg1._uSmall = NumericsHelpers.GCD(reg1._uSmall, reg2._uSmall); + else if (reg2._uSmall != 0) + reg1.Set(NumericsHelpers.GCD(Mod(ref reg1, reg2._uSmall), reg2._uSmall)); + return; + } + + if (cuMax == 2) + { + reg1.Set(NumericsHelpers.GCD(reg1.GetHigh2(2), reg2.GetHigh2(2))); + return; + } + + if (cuMin <= cuMax - 2) + { + // reg1 is much larger than reg2, so just mod. + reg1.Mod(ref reg2); + continue; + } + + ulong uu1 = reg1.GetHigh2(cuMax); + ulong uu2 = reg2.GetHigh2(cuMax); + Contract.Assert(uu1 != 0 && uu2 != 0); + + int cbit = NumericsHelpers.CbitHighZero(uu1 | uu2); + if (cbit > 0) + { + uu1 = (uu1 << cbit) | (reg1._rgu[cuMax - 3] >> (kcbitUint - cbit)); + // Note that [cuMax - 3] is correct, NOT [cuMin - 3]. + uu2 = (uu2 << cbit) | (reg2._rgu[cuMax - 3] >> (kcbitUint - cbit)); + } + if (uu1 < uu2) + { + NumericsHelpers.Swap(ref uu1, ref uu2); + NumericsHelpers.Swap(ref reg1, ref reg2); + } + + // Make sure we don't overflow. + if (uu1 == ulong.MaxValue || uu2 == ulong.MaxValue) + { + uu1 >>= 1; + uu2 >>= 1; + } + Contract.Assert(uu1 >= uu2); // We ensured this above. + if (uu1 == uu2) + { + // The high bits are the same, so we don't know which + // is larger. No matter, just subtract one from the other + // and keep the absolute value of the result. + Contract.Assert(cuMax == cuMin); + reg1.Sub(ref signTmp, ref reg2); + Contract.Assert(reg1._iuLast < cuMin - 1); + continue; + } + if (NumericsHelpers.GetHi(uu2) == 0) + { + // reg1 is much larger than reg2, so just mod. + reg1.Mod(ref reg2); + continue; + } + + // These are the coefficients to apply to reg1 and reg2 to get + // the new values, using: a * reg1 - b * reg2 and -c * reg1 + d * reg2. + uint a = 1, b = 0; + uint c = 0, d = 1; + + for (; ; ) + { + Contract.Assert(uu1 + a > a); // no overflow + Contract.Assert(uu2 + d > d); + Contract.Assert(uu1 > b); + Contract.Assert(uu2 > c); + Contract.Assert(uu2 + d <= uu1 - b); + + uint uQuo = 1; + ulong uuNew = uu1 - uu2; + while (uuNew >= uu2 && uQuo < 32) + { + uuNew -= uu2; + uQuo++; + } + if (uuNew >= uu2) + { + ulong uuQuo = uu1 / uu2; + if (uuQuo > uint.MaxValue) + break; + uQuo = (uint)uuQuo; + uuNew = uu1 - uQuo * uu2; + } + ulong uuAdNew = a + (ulong)uQuo * c; + ulong uuBcNew = b + (ulong)uQuo * d; + if (uuAdNew > int.MaxValue || uuBcNew > int.MaxValue) + break; + // Jebelean / Belenkiy-Vidunas conditions + if (uuNew < uuBcNew || uuNew + uuAdNew > uu2 - c) + break; + + Contract.Assert(uQuo == (uu1 + a - 1) / (uu2 - c)); + Contract.Assert(uQuo == (uu1 - b) / (uu2 + d)); + + a = (uint)uuAdNew; + b = (uint)uuBcNew; + uu1 = uuNew; + + if (uu1 <= b) + { + Contract.Assert(uu1 == b); + break; + } + + Contract.Assert(uu1 + a > a); // no overflow + Contract.Assert(uu2 + d > d); + Contract.Assert(uu2 > c); + Contract.Assert(uu1 > b); + Contract.Assert(uu1 + a <= uu2 - c); + + uQuo = 1; + uuNew = uu2 - uu1; + while (uuNew >= uu1 && uQuo < 32) + { + uuNew -= uu1; + uQuo++; + } + if (uuNew >= uu1) + { + ulong uuQuo = uu2 / uu1; + if (uuQuo > uint.MaxValue) + break; + uQuo = (uint)uuQuo; + uuNew = uu2 - uQuo * uu1; + } + uuAdNew = d + (ulong)uQuo * b; + uuBcNew = c + (ulong)uQuo * a; + if (uuAdNew > int.MaxValue || uuBcNew > int.MaxValue) + break; + // Jebelean / Belenkiy-Vidunas conditions + if (uuNew < uuBcNew || uuNew + uuAdNew > uu1 - b) + break; + + Contract.Assert(uQuo == (uu2 + d - 1) / (uu1 - b)); + Contract.Assert(uQuo == (uu2 - c) / (uu1 + a)); + + d = (uint)uuAdNew; + c = (uint)uuBcNew; + uu2 = uuNew; + + if (uu2 <= c) + { + Contract.Assert(uu2 == c); + break; + } + } + + if (b == 0) + { + Contract.Assert(a == 1 && c == 0 && d == 1); + Contract.Assert(uu1 > uu2); // We ensured this above. + if (uu1 / 2 >= uu2) + reg1.Mod(ref reg2); + else + reg1.Sub(ref signTmp, ref reg2); + } + else + { + // Replace reg1 with a * reg1 - b * reg2. + // Replace reg2 with -c * reg1 + d * reg2. + // Do everything mod cuMin uint's. + reg1.SetSizeKeep(cuMin, 0); + reg2.SetSizeKeep(cuMin, 0); + int nCarry1 = 0; + int nCarry2 = 0; + for (int iu = 0; iu < cuMin; iu++) + { + uint u1 = reg1._rgu[iu]; + uint u2 = reg2._rgu[iu]; + long nn1 = (long)u1 * a - (long)u2 * b + nCarry1; + long nn2 = (long)u2 * d - (long)u1 * c + nCarry2; + nCarry1 = (int)(nn1 >> kcbitUint); + nCarry2 = (int)(nn2 >> kcbitUint); + reg1._rgu[iu] = (uint)nn1; + reg2._rgu[iu] = (uint)nn2; + } + reg1.Trim(); + reg2.Trim(); + } + } + } +*/ + + /*internal int CbitLowZero() + { + AssertValid(true); + if (_iuLast == 0) + { + if ((_uSmall & 1) != 0 || _uSmall == 0) + return 0; + return NumericsHelpers.CbitLowZero(_uSmall); + } + + int iuMin = 0; + while (_rgu[iuMin] == 0) + iuMin++; + int cbit = NumericsHelpers.CbitLowZero(_rgu[iuMin]); + return cbit + iuMin * kcbitUint; + }*/ + + // Shift right until the number is odd. Return the number of bits + // shifted. Asserts that the register is trimmed. +/* + internal int MakeOdd() + { + AssertValid(true); + int cbit = CbitLowZero(); + if (cbit > 0) + ShiftRight(cbit); + return cbit; + } +*/ + } +} diff --git a/runtime/VMProtect.Runtime/Numerics/NumericHelpers.cs b/runtime/VMProtect.Runtime/Numerics/NumericHelpers.cs new file mode 100644 index 0000000..68c61bc --- /dev/null +++ b/runtime/VMProtect.Runtime/Numerics/NumericHelpers.cs @@ -0,0 +1,425 @@ +// ==++== +// +// Copyright (c) Microsoft Corporation. All rights reserved. +// +// ==--== + +using System; + +using Contracts = System.Diagnostics.Debug; +using Contract = System.Diagnostics.Debug; +//using System.Runtime.InteropServices; + +// ReSharper disable once CheckNamespace +namespace Numerics +{ + +/* + [StructLayout(LayoutKind.Explicit)] + internal struct DoubleUlong + { + [FieldOffset(0)] + internal double dbl; + [FieldOffset(0)] + internal ulong uu; + } +*/ + + + internal static class NumericsHelpers + { + private const int KcbitUint = 32; + + /*internal static void GetDoubleParts(double dbl, out int sign, out int exp, out ulong man, out bool fFinite) + { + //Contract.Ensures(Contract.ValueAtReturn(out sign) == +1 || Contract.ValueAtReturn(out sign) == -1); + + DoubleUlong du; + du.uu = 0; + du.dbl = dbl; + + sign = 1 - ((int)(du.uu >> 62) & 2); + man = du.uu & 0x000FFFFFFFFFFFFF; + exp = (int)(du.uu >> 52) & 0x7FF; + if (exp == 0) + { + // Denormalized number. + fFinite = true; + if (man != 0) + exp = -1074; + } + else if (exp == 0x7FF) + { + // NaN or Inifite. + fFinite = false; + exp = int.MaxValue; + } + else + { + fFinite = true; + man |= 0x0010000000000000; + exp -= 1075; + } + } + + internal static double GetDoubleFromParts(int sign, int exp, ulong man) + { + DoubleUlong du; + du.dbl = 0; + + if (man == 0) + du.uu = 0; + else + { + // Normalize so that 0x0010 0000 0000 0000 is the highest bit set. + int cbitShift = CbitHighZero(man) - 11; + if (cbitShift < 0) + man >>= -cbitShift; + else + man <<= cbitShift; + exp -= cbitShift; + Contract.Assert((man & 0xFFF0000000000000) == 0x0010000000000000); + + // Move the point to just behind the leading 1: 0x001.0 0000 0000 0000 + // (52 bits) and skew the exponent (by 0x3FF == 1023). + exp += 1075; + + if (exp >= 0x7FF) + { + // Infinity. + du.uu = 0x7FF0000000000000; + } + else if (exp <= 0) + { + // Denormalized. + exp--; + if (exp < -52) + { + // Underflow to zero. + du.uu = 0; + } + else + { + du.uu = man >> -exp; + Contract.Assert(du.uu != 0); + } + } + else + { + // Mask off the implicit high bit. + du.uu = (man & 0x000FFFFFFFFFFFFF) | ((ulong)exp << 52); + } + } + + if (sign < 0) + du.uu |= 0x8000000000000000; + + return du.dbl; + } + */ + + + // Do an in-place twos complement of d and also return the result. + // "Dangerous" because it causes a mutation and needs to be used + // with care for immutable types + internal static void DangerousMakeTwosComplement(uint[] d) + { + // first do complement and +1 as long as carry is needed + int i = 0; + uint v = 0; + for (; i < d.Length; i++) + { + v = ~d[i] + 1; + d[i] = v; + if (v != 0) { i++; break; } + } + if (v != 0) + { + // now ones complement is sufficient + for (; i < d.Length; i++) + { + d[i] = ~d[i]; + } + } + else + { + //??? this is weird + d = resize(d, d.Length + 1); + d[d.Length - 1] = 1; + } + } + + // ReSharper disable once InconsistentNaming + private static uint[] resize(uint[] v, int len) + { + if (v.Length == len) return v; + uint[] ret = new uint[len]; + int n = Math.Min(v.Length, len); + for (int i = 0; i < n; i++) + { + ret[i] = v[i]; + } + return ret; + } + + internal static void Swap<T>(ref T a, ref T b) + { + T tmp = a; + a = b; + b = tmp; + } + + // ReSharper disable once InconsistentNaming +/* + internal static uint GCD(uint u1, uint u2) + { + const int cvMax = 32; + if (u1 < u2) + goto LOther; + LTop: + Contract.Assert(u2 <= u1); + if (u2 == 0) + return u1; + for (int cv = cvMax; ; ) + { + u1 -= u2; + if (u1 < u2) + break; + if (--cv == 0) + { + u1 %= u2; + break; + } + } + LOther: + Contract.Assert(u1 < u2); + if (u1 == 0) + return u2; + for (int cv = cvMax; ; ) + { + u2 -= u1; + if (u2 < u1) + break; + if (--cv == 0) + { + u2 %= u1; + break; + } + } + goto LTop; + } +*/ + + // ReSharper disable once InconsistentNaming +/* + internal static ulong GCD(ulong uu1, ulong uu2) + { + const int cvMax = 32; + if (uu1 < uu2) + goto LOther; + LTop: + Contract.Assert(uu2 <= uu1); + if (uu1 <= uint.MaxValue) + goto LSmall; + if (uu2 == 0) + return uu1; + for (int cv = cvMax; ; ) + { + uu1 -= uu2; + if (uu1 < uu2) + break; + if (--cv == 0) + { + uu1 %= uu2; + break; + } + } + LOther: + Contract.Assert(uu1 < uu2); + if (uu2 <= uint.MaxValue) + goto LSmall; + if (uu1 == 0) + return uu2; + for (int cv = cvMax; ; ) + { + uu2 -= uu1; + if (uu2 < uu1) + break; + if (--cv == 0) + { + uu2 %= uu1; + break; + } + } + goto LTop; + + LSmall: + uint u1 = (uint)uu1; + uint u2 = (uint)uu2; + if (u1 < u2) + goto LOtherSmall; + LTopSmall: + Contract.Assert(u2 <= u1); + if (u2 == 0) + return u1; + for (int cv = cvMax; ; ) + { + u1 -= u2; + if (u1 < u2) + break; + if (--cv == 0) + { + u1 %= u2; + break; + } + } + LOtherSmall: + Contract.Assert(u1 < u2); + if (u1 == 0) + return u2; + for (int cv = cvMax; ; ) + { + u2 -= u1; + if (u2 < u1) + break; + if (--cv == 0) + { + u2 %= u1; + break; + } + } + goto LTopSmall; + } +*/ + + internal static ulong MakeUlong(uint uHi, uint uLo) + { + return ((ulong)uHi << KcbitUint) | uLo; + } + + internal static uint GetLo(ulong uu) + { + return (uint)uu; + } + + internal static uint GetHi(ulong uu) + { + return (uint)(uu >> KcbitUint); + } + +/* + internal static uint Abs(int a) + { + uint mask = (uint)(a >> 31); + return ((uint)a ^ mask) - mask; + } +*/ + + // internal static ulong Abs(long a) { + // ulong mask = (ulong)(a >> 63); + // return ((ulong)a ^ mask) - mask; + // } + + private static uint CombineHash(uint u1, uint u2) + { + return ((u1 << 7) | (u1 >> 25)) ^ u2; + } + + internal static int CombineHash(int n1, int n2) + { + return (int)CombineHash((uint)n1, (uint)n2); + } + internal static int CbitHighZero(uint u) + { + if (u == 0) + return 32; + + int cbit = 0; + if ((u & 0xFFFF0000) == 0) + { + cbit += 16; + u <<= 16; + } + if ((u & 0xFF000000) == 0) + { + cbit += 8; + u <<= 8; + } + if ((u & 0xF0000000) == 0) + { + cbit += 4; + u <<= 4; + } + if ((u & 0xC0000000) == 0) + { + cbit += 2; + u <<= 2; + } + if ((u & 0x80000000) == 0) + cbit += 1; + return cbit; + } + + /*internal static int CbitLowZero(uint u) + { + if (u == 0) + return 32; + + int cbit = 0; + if ((u & 0x0000FFFF) == 0) + { + cbit += 16; + u >>= 16; + } + if ((u & 0x000000FF) == 0) + { + cbit += 8; + u >>= 8; + } + if ((u & 0x0000000F) == 0) + { + cbit += 4; + u >>= 4; + } + if ((u & 0x00000003) == 0) + { + cbit += 2; + u >>= 2; + } + if ((u & 0x00000001) == 0) + cbit += 1; + return cbit; + } + + internal static int CbitHighZero(ulong uu) + { + if ((uu & 0xFFFFFFFF00000000) == 0) + return 32 + CbitHighZero((uint)uu); + return CbitHighZero((uint)(uu >> 32)); + }*/ + + // internal static int CbitLowZero(ulong uu) { + // if ((uint)uu == 0) + // return 32 + CbitLowZero((uint)(uu >> 32)); + // return CbitLowZero((uint)uu); + // } + // + // internal static int Cbit(uint u) { + // u = (u & 0x55555555) + ((u >> 1) & 0x55555555); + // u = (u & 0x33333333) + ((u >> 2) & 0x33333333); + // u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F); + // u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF); + // return (int)((ushort)u + (ushort)(u >> 16)); + // } + // + // static int Cbit(ulong uu) { + // uu = (uu & 0x5555555555555555) + ((uu >> 1) & 0x5555555555555555); + // uu = (uu & 0x3333333333333333) + ((uu >> 2) & 0x3333333333333333); + // uu = (uu & 0x0F0F0F0F0F0F0F0F) + ((uu >> 4) & 0x0F0F0F0F0F0F0F0F); + // uu = (uu & 0x00FF00FF00FF00FF) + ((uu >> 8) & 0x00FF00FF00FF00FF); + // uu = (uu & 0x0000FFFF0000FFFF) + ((uu >> 16) & 0x0000FFFF0000FFFF); + // return (int)((uint)uu + (uint)(uu >> 32)); + // } + } +} + |