// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
-// The Multiply and Div code comes the DLR (as hosted in http://ironpython.codeplex.com),
+// A big chuck of code comes the DLR (as hosted in http://ironpython.codeplex.com),
// which has the following License:
//
/* ****************************************************************************
*
* ***************************************************************************/
-using System;\r
-using System.Collections.Generic;\r
-using System.Diagnostics;\r
-using System.Diagnostics.CodeAnalysis;\r
-using System.Globalization;\r
-using System.Text;\r
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Diagnostics.CodeAnalysis;
+using System.Globalization;
+using System.Text;
+using System.Threading;
/*
Optimization
Optimize BitScanBackward
Use a carry variable to make shift opts do half the number of array ops.
Schoolbook multiply is O(n^2), use Karatsuba /Toom-3 for large numbers
-*/\r
-namespace System.Numerics {\r
- public struct BigInteger : IComparable, IComparable<BigInteger>, IEquatable<BigInteger>
+*/
+namespace System.Numerics {
+ public struct BigInteger : IComparable, IFormattable, IComparable<BigInteger>, IEquatable<BigInteger>
{
//LSB on [0]
readonly uint[] data;
}
}
+
+ static bool Negative (byte[] v)
+ {
+ return ((v[7] & 0x80) != 0);
+ }
+
+ static ushort Exponent (byte[] v)
+ {
+ return (ushort)((((ushort)(v[7] & 0x7F)) << (ushort)4) | (((ushort)(v[6] & 0xF0)) >> 4));
+ }
+
+ static ulong Mantissa(byte[] v)
+ {
+ uint i1 = ((uint)v[0] | ((uint)v[1] << 8) | ((uint)v[2] << 16) | ((uint)v[3] << 24));
+ uint i2 = ((uint)v[4] | ((uint)v[5] << 8) | ((uint)(v[6] & 0xF) << 16));
+
+ return (ulong)((ulong)i1 | ((ulong)i2 << 32));
+ }
+
+ const int bias = 1075;
+ public BigInteger (double value)
+ {
+ if (double.IsNaN (value) || Double.IsInfinity (value))
+ throw new OverflowException ();
+
+ byte[] bytes = BitConverter.GetBytes (value);
+ ulong mantissa = Mantissa (bytes);
+ if (mantissa == 0) {
+ // 1.0 * 2**exp, we have a power of 2
+ int exponent = Exponent (bytes);
+ if (exponent == 0) {
+ sign = 0;
+ data = ZERO;
+ return;
+ }
+
+ BigInteger res = Negative (bytes) ? MinusOne : One;
+ res = res << (exponent - 0x3ff);
+ this.sign = res.sign;
+ this.data = res.data;
+ } else {
+ // 1.mantissa * 2**exp
+ int exponent = Exponent(bytes);
+ mantissa |= 0x10000000000000ul;
+ BigInteger res = mantissa;
+ res = exponent > bias ? res << (exponent - bias) : res >> (bias - exponent);
+
+ this.sign = (short) (Negative (bytes) ? -1 : 1);
+ this.data = res.data;
+ }
+ }
+
+ public BigInteger (float value) : this ((double)value)
+ {
+ }
+
+ const Int32 DecimalScaleFactorMask = 0x00FF0000;
+ const Int32 DecimalSignMask = unchecked((Int32)0x80000000);
+
+ public BigInteger (decimal value)
+ {
+ // First truncate to get scale to 0 and extract bits
+ int[] bits = Decimal.GetBits(Decimal.Truncate(value));
+
+ int size = 3;
+ while (size > 0 && bits[size - 1] == 0) size--;
+
+ if (size == 0) {
+ sign = 0;
+ data = ZERO;
+ return;
+ }
+
+ sign = (short) ((bits [3] & DecimalSignMask) != 0 ? -1 : 1);
+
+ data = new uint [size];
+ data [0] = (uint)bits [0];
+ if (size > 1)
+ data [1] = (uint)bits [1];
+ if (size > 2)
+ data [2] = (uint)bits [2];
+ }
+
[CLSCompliantAttribute (false)]
public BigInteger (byte[] value)
{
sign = 1;
if (sign == 1) {
- while (value [len - 1] == 0)
- --len;
+ while (value [len - 1] == 0) {
+ if (--len == 0) {
+ sign = 0;
+ data = ZERO;
+ return;
+ }
+ }
int full_words, size;
full_words = size = len / 4;
}
public bool IsEven {
- get { return (data [0] & 0x1) == 0; }
+ get { return sign == 0 || (data [0] & 0x1) == 0; }
}
public bool IsOne {
public static explicit operator int (BigInteger value)
{
+ if (value.sign == 0)
+ return 0;
if (value.data.Length > 1)
throw new OverflowException ();
uint data = value.data [0];
[CLSCompliantAttribute (false)]
public static explicit operator uint (BigInteger value)
{
+ if (value.sign == 0)
+ return 0;
if (value.data.Length > 1 || value.sign == -1)
throw new OverflowException ();
return value.data [0];
return (((long)high) << 32) | low;
}
- if (high > 0x80000000u)
- throw new OverflowException ();
+ /*
+ We cannot represent negative numbers smaller than long.MinValue.
+ Those values are encoded into what look negative numbers, so negating
+ them produces a positive value, that's why it's safe to check for that
+ condition.
+
+ long.MinValue works fine since it's bigint encoding looks like a negative
+ number, but since long.MinValue == -long.MinValue, we're good.
+ */
- return - ((((long)high) << 32) | (long)low);
+ long result = - ((((long)high) << 32) | (long)low);
+ if (result > 0)
+ throw new OverflowException ();
+ return result;
}
[CLSCompliantAttribute (false)]
public static explicit operator ulong (BigInteger value)
{
+ if (value.sign == 0)
+ return 0;
if (value.data.Length > 2 || value.sign == -1)
throw new OverflowException ();
return (((ulong)high) << 32) | low;
}
+ public static explicit operator double (BigInteger value)
+ {
+ //FIXME
+ try {
+ return double.Parse (value.ToString (),
+ System.Globalization.CultureInfo.InvariantCulture.NumberFormat);
+ } catch (OverflowException) {
+ return value.sign == -1 ? double.NegativeInfinity : double.PositiveInfinity;
+ }
+ }
+
+ public static explicit operator float (BigInteger value)
+ {
+ //FIXME
+ try {
+ return float.Parse (value.ToString (),
+ System.Globalization.CultureInfo.InvariantCulture.NumberFormat);
+ } catch (OverflowException) {
+ return value.sign == -1 ? float.NegativeInfinity : float.PositiveInfinity;
+ }
+ }
+
+ public static explicit operator decimal (BigInteger value)
+ {
+ if (value.sign == 0)
+ return Decimal.Zero;
+
+ uint[] data = value.data;
+ if (data.Length > 3)
+ throw new OverflowException ();
+
+ int lo = 0, mi = 0, hi = 0;
+ if (data.Length > 2)
+ hi = (Int32)data [2];
+ if (data.Length > 1)
+ mi = (Int32)data [1];
+ if (data.Length > 0)
+ lo = (Int32)data [0];
+
+ return new Decimal(lo, mi, hi, value.sign < 0, 0);
+ }
public static implicit operator BigInteger (int value)
{
return new BigInteger (value);
}
+ public static explicit operator BigInteger (double value)
+ {
+ return new BigInteger (value);
+ }
+
+ public static explicit operator BigInteger (float value)
+ {
+ return new BigInteger (value);
+ }
+
+ public static explicit operator BigInteger (decimal value)
+ {
+ return new BigInteger (value);
+ }
+
public static BigInteger operator+ (BigInteger left, BigInteger right)
{
if (left.sign == 0)
public static BigInteger operator++ (BigInteger value)
{
+ if (value.sign == 0)
+ return One;
+
short sign = value.sign;
uint[] data = value.data;
if (data.Length == 1) {
public static BigInteger operator-- (BigInteger value)
{
+ if (value.sign == 0)
+ return MinusOne;
+
short sign = value.sign;
uint[] data = value.data;
if (data.Length == 1) {
int bit_shift = shift & 0x1F;
int carry_shift = 32 - bit_shift;
- for (int i = 0; i < data.Length; ++i) {
- uint word = data [i];
- res [i + idx_shift] |= word << bit_shift;
- if (i + idx_shift + 1 < res.Length)
- res [i + idx_shift + 1] = word >> carry_shift;
+ if (carry_shift == 32) {
+ for (int i = 0; i < data.Length; ++i) {
+ uint word = data [i];
+ res [i + idx_shift] |= word << bit_shift;
+ }
+ } else {
+ for (int i = 0; i < data.Length; ++i) {
+ uint word = data [i];
+ res [i + idx_shift] |= word << bit_shift;
+ if (i + idx_shift + 1 < res.Length)
+ res [i + idx_shift + 1] = word >> carry_shift;
+ }
}
return new BigInteger ((short)sign, res);
uint[] res = new uint [size];
int carry_shift = 32 - bit_shift;
- for (int i = data.Length - 1; i >= idx_shift; --i) {
- uint word = data [i];
+ if (carry_shift == 32) {
+ for (int i = data.Length - 1; i >= idx_shift; --i) {
+ uint word = data [i];
+
+ if (i - idx_shift < res.Length)
+ res [i - idx_shift] |= word >> bit_shift;
+ }
+ } else {
+ for (int i = data.Length - 1; i >= idx_shift; --i) {
+ uint word = data [i];
+
+ if (i - idx_shift < res.Length)
+ res [i - idx_shift] |= word >> bit_shift;
+ if (i - idx_shift - 1 >= 0)
+ res [i - idx_shift - 1] = word << carry_shift;
+ }
- if (i - idx_shift < res.Length)
- res [i - idx_shift] |= word >> bit_shift;
- if (i - idx_shift - 1 >= 0)
- res [i - idx_shift - 1] = word << carry_shift;
}
//Round down instead of toward zero
{
if (sign != other.sign)
return false;
- if (data.Length != other.data.Length)
+
+ int alen = data != null ? data.Length : 0;
+ int blen = other.data != null ? other.data.Length : 0;
+
+ if (alen != blen)
return false;
- for (int i = 0; i < data.Length; ++i) {
+ for (int i = 0; i < alen; ++i) {
if (data [i] != other.data [i])
return false;
}
return CompareTo (other) == 0;
}
+ public override string ToString ()
+ {
+ return ToString (10, null);
+ }
+
+ string ToStringWithPadding (string format, uint radix, IFormatProvider provider)
+ {
+ if (format.Length > 1) {
+ int precision = Convert.ToInt32(format.Substring (1), CultureInfo.InvariantCulture.NumberFormat);
+ string baseStr = ToString (radix, provider);
+ if (baseStr.Length < precision) {
+ string additional = new String ('0', precision - baseStr.Length);
+ if (baseStr[0] != '-') {
+ return additional + baseStr;
+ } else {
+ return "-" + additional + baseStr.Substring (1);
+ }
+ }
+ return baseStr;
+ }
+ return ToString (radix, provider);
+ }
+
+ public string ToString (string format)
+ {
+ return ToString (format, null);
+ }
+
+ public string ToString (IFormatProvider provider)
+ {
+ return ToString (null, provider);
+ }
+
+
+ public string ToString (string format, IFormatProvider provider)
+ {
+ if (format == null || format == "")
+ return ToString (10, provider);
+
+ switch (format[0]) {
+ case 'd':
+ case 'D':
+ case 'g':
+ case 'G':
+ case 'r':
+ case 'R':
+ return ToStringWithPadding (format, 10, provider);
+ case 'x':
+ case 'X':
+ return ToStringWithPadding (format, 16, null);
+ default:
+ throw new FormatException (string.Format ("format '{0}' not implemented", format));
+ }
+ }
+
+ static uint[] MakeTwoComplement (uint[] v)
+ {
+ uint[] res = new uint [v.Length];
+
+ ulong carry = 1;
+ for (int i = 0; i < v.Length; ++i) {
+ uint word = v [i];
+ carry = (ulong)~word + carry;
+ word = (uint)carry;
+ carry = (uint)(carry >> 32);
+ res [i] = word;
+ }
+
+ uint last = res [res.Length - 1];
+ int idx = FirstNonFFByte (last);
+ uint mask = 0xFF;
+ for (int i = 1; i < idx; ++i)
+ mask = (mask << 8) | 0xFF;
+
+ res [res.Length - 1] = last & mask;
+ return res;
+ }
+
+ string ToString (uint radix, IFormatProvider provider)
+ {
+ const string characterSet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
+
+ if (characterSet.Length < radix)
+ throw new ArgumentException ("charSet length less than radix", "characterSet");
+ if (radix == 1)
+ throw new ArgumentException ("There is no such thing as radix one notation", "radix");
+
+ if (sign == 0)
+ return "0";
+ if (data.Length == 1 && data [0] == 1)
+ return sign == 1 ? "1" : "-1";
+
+ List<char> digits = new List<char> (1 + data.Length * 3 / 10);
+
+ BigInteger a;
+ if (sign == 1)
+ a = this;
+ else {
+ uint[] dt = data;
+ if (radix > 10)
+ dt = MakeTwoComplement (dt);
+ a = new BigInteger (1, dt);
+ }
+
+ while (a != 0) {
+ BigInteger rem;
+ a = DivRem (a, radix, out rem);
+ digits.Add (characterSet [(int) rem]);
+ }
+
+ if (sign == -1 && radix == 10) {
+ NumberFormatInfo info = null;
+ if (provider != null)
+ info = provider.GetFormat (typeof (NumberFormatInfo)) as NumberFormatInfo;
+ if (info != null) {
+ string str = info.NegativeSign;
+ for (int i = str.Length - 1; i >= 0; --i)
+ digits.Add (str [i]);
+ } else {
+ digits.Add ('-');
+ }
+ }
+
+ char last = digits [digits.Count - 1];
+ if (sign == 1 && radix > 10 && (last < '0' || last > '9'))
+ digits.Add ('0');
+
+ digits.Reverse ();
+
+ return new String (digits.ToArray ());
+ }
+
+ public static BigInteger Parse (string value)
+ {
+ Exception ex;
+ BigInteger result;
+
+ if (!Parse (value, false, out result, out ex))
+ throw ex;
+ return result;
+ }
+
+ public static bool TryParse (string value, out BigInteger result)
+ {
+ Exception ex;
+ return Parse (value, true, out result, out ex);
+ }
+
+ public static BigInteger Parse (string value, NumberStyles style)
+ {
+ return Parse (value, style, null);
+ }
+
+ public static BigInteger Parse (string value, IFormatProvider provider)
+ {
+ return Parse (value, NumberStyles.Integer, provider);
+ }
+
+ public static BigInteger Parse (
+ string value, NumberStyles style, IFormatProvider provider)
+ {
+ Exception exc;
+ BigInteger res;
+
+ if (!Parse (value, style, provider, false, out res, out exc))
+ throw exc;
+
+ return res;
+ }
+
+ public static bool TryParse (
+ string value, NumberStyles style, IFormatProvider provider,
+ out BigInteger result)
+ {
+ Exception exc;
+ if (!Parse (value, style, provider, true, out result, out exc)) {
+ result = Zero;
+ return false;
+ }
+
+ return true;
+ }
+
+ internal static bool Parse (string s, NumberStyles style, IFormatProvider fp, bool tryParse, out BigInteger result, out Exception exc)
+ {
+ result = Zero;
+ exc = null;
+
+ if (s == null) {
+ if (!tryParse)
+ exc = new ArgumentNullException ("s");
+ return false;
+ }
+
+ if (s.Length == 0) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ NumberFormatInfo nfi = null;
+ if (fp != null) {
+ Type typeNFI = typeof(System.Globalization.NumberFormatInfo);
+ nfi = (NumberFormatInfo)fp.GetFormat (typeNFI);
+ }
+ if (nfi == null)
+ nfi = Thread.CurrentThread.CurrentCulture.NumberFormat;
+
+ if (!CheckStyle (style, tryParse, ref exc))
+ return false;
+
+ bool AllowCurrencySymbol = (style & NumberStyles.AllowCurrencySymbol) != 0;
+ bool AllowHexSpecifier = (style & NumberStyles.AllowHexSpecifier) != 0;
+ bool AllowThousands = (style & NumberStyles.AllowThousands) != 0;
+ bool AllowDecimalPoint = (style & NumberStyles.AllowDecimalPoint) != 0;
+ bool AllowParentheses = (style & NumberStyles.AllowParentheses) != 0;
+ bool AllowTrailingSign = (style & NumberStyles.AllowTrailingSign) != 0;
+ bool AllowLeadingSign = (style & NumberStyles.AllowLeadingSign) != 0;
+ bool AllowTrailingWhite = (style & NumberStyles.AllowTrailingWhite) != 0;
+ bool AllowLeadingWhite = (style & NumberStyles.AllowLeadingWhite) != 0;
+ bool AllowExponent = (style & NumberStyles.AllowExponent) != 0;
+
+ int pos = 0;
+
+ if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+
+ bool foundOpenParentheses = false;
+ bool negative = false;
+ bool foundSign = false;
+ bool foundCurrency = false;
+
+ // Pre-number stuff
+ if (AllowParentheses && s [pos] == '(') {
+ foundOpenParentheses = true;
+ foundSign = true;
+ negative = true; // MS always make the number negative when there parentheses
+ // even when NumberFormatInfo.NumberNegativePattern != 0!!!
+ pos++;
+ if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+
+ if (s.Substring (pos, nfi.NegativeSign.Length) == nfi.NegativeSign) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ if (s.Substring (pos, nfi.PositiveSign.Length) == nfi.PositiveSign) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+ }
+
+ if (AllowLeadingSign && !foundSign) {
+ // Sign + Currency
+ FindSign (ref pos, s, nfi, ref foundSign, ref negative);
+ if (foundSign) {
+ if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ if (AllowCurrencySymbol) {
+ FindCurrency (ref pos, s, nfi,
+ ref foundCurrency);
+ if (foundCurrency && AllowLeadingWhite &&
+ !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ }
+ }
+ }
+
+ if (AllowCurrencySymbol && !foundCurrency) {
+ // Currency + sign
+ FindCurrency (ref pos, s, nfi, ref foundCurrency);
+ if (foundCurrency) {
+ if (AllowLeadingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ if (foundCurrency) {
+ if (!foundSign && AllowLeadingSign) {
+ FindSign (ref pos, s, nfi, ref foundSign,
+ ref negative);
+ if (foundSign && AllowLeadingWhite &&
+ !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ }
+ }
+ }
+ }
+
+ BigInteger number = Zero;
+ int nDigits = 0;
+ int decimalPointPos = -1;
+ byte digitValue;
+ char hexDigit;
+ bool firstHexDigit = true;
+
+ // Number stuff
+ while (pos < s.Length) {
+
+ if (!ValidDigit (s [pos], AllowHexSpecifier)) {
+ if (AllowThousands &&
+ (FindOther (ref pos, s, nfi.NumberGroupSeparator)
+ || FindOther (ref pos, s, nfi.CurrencyGroupSeparator)))
+ continue;
+
+ if (AllowDecimalPoint && decimalPointPos < 0 &&
+ (FindOther (ref pos, s, nfi.NumberDecimalSeparator)
+ || FindOther (ref pos, s, nfi.CurrencyDecimalSeparator))) {
+ decimalPointPos = nDigits;
+ continue;
+ }
+
+ break;
+ }
+
+ nDigits++;
+
+ if (AllowHexSpecifier) {
+ hexDigit = s [pos++];
+ if (Char.IsDigit (hexDigit))
+ digitValue = (byte)(hexDigit - '0');
+ else if (Char.IsLower (hexDigit))
+ digitValue = (byte)(hexDigit - 'a' + 10);
+ else
+ digitValue = (byte)(hexDigit - 'A' + 10);
+
+ if (firstHexDigit && (byte)digitValue >= 8)
+ negative = true;
+
+ number = number * 16 + digitValue;
+ firstHexDigit = false;
+ continue;
+ }
+
+ number = number * 10 + (byte)(s [pos++] - '0');
+ }
+
+ // Post number stuff
+ if (nDigits == 0) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ //signed hex value
+ if (AllowHexSpecifier && negative) {
+ //number = 123456;
+ BigInteger mask = BigInteger.Pow(16, nDigits) - 1;
+ number = (number ^ mask) + 1;
+ }
+
+ int exponent = 0;
+ if (AllowExponent)
+ if (FindExponent (ref pos, s, ref exponent, tryParse, ref exc) && exc != null)
+ return false;
+
+ if (AllowTrailingSign && !foundSign) {
+ // Sign + Currency
+ FindSign (ref pos, s, nfi, ref foundSign, ref negative);
+ if (foundSign && pos < s.Length) {
+ if (AllowTrailingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ }
+ }
+
+ if (AllowCurrencySymbol && !foundCurrency) {
+ if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
+ return false;
+
+ // Currency + sign
+ FindCurrency (ref pos, s, nfi, ref foundCurrency);
+ if (foundCurrency && pos < s.Length) {
+ if (AllowTrailingWhite && !JumpOverWhite (ref pos, s, true, tryParse, ref exc))
+ return false;
+ if (!foundSign && AllowTrailingSign)
+ FindSign (ref pos, s, nfi, ref foundSign,
+ ref negative);
+ }
+ }
+
+ if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
+ return false;
+
+ if (foundOpenParentheses) {
+ if (pos >= s.Length || s [pos++] != ')') {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+ if (AllowTrailingWhite && pos < s.Length && !JumpOverWhite (ref pos, s, false, tryParse, ref exc))
+ return false;
+ }
+
+ if (pos < s.Length && s [pos] != '\u0000') {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ if (decimalPointPos >= 0)
+ exponent = exponent - nDigits + decimalPointPos;
+
+ if (exponent < 0) {
+ //
+ // Any non-zero values after decimal point are not allowed
+ //
+ BigInteger remainder;
+ number = BigInteger.DivRem(number, BigInteger.Pow(10, -exponent), out remainder);
+
+ if (!remainder.IsZero) {
+ if (!tryParse)
+ exc = new OverflowException ("Value too large or too small. exp="+exponent+" rem = " + remainder + " pow = " + BigInteger.Pow(10, -exponent));
+ return false;
+ }
+ } else if (exponent > 0) {
+ number = BigInteger.Pow(10, exponent) * number;
+ }
+
+ if (number.sign == 0)
+ result = number;
+ else if (negative)
+ result = new BigInteger (-1, number.data);
+ else
+ result = new BigInteger (1, number.data);
+
+ return true;
+ }
+
+ internal static bool CheckStyle (NumberStyles style, bool tryParse, ref Exception exc)
+ {
+ if ((style & NumberStyles.AllowHexSpecifier) != 0) {
+ NumberStyles ne = style ^ NumberStyles.AllowHexSpecifier;
+ if ((ne & NumberStyles.AllowLeadingWhite) != 0)
+ ne ^= NumberStyles.AllowLeadingWhite;
+ if ((ne & NumberStyles.AllowTrailingWhite) != 0)
+ ne ^= NumberStyles.AllowTrailingWhite;
+ if (ne != 0) {
+ if (!tryParse)
+ exc = new ArgumentException (
+ "With AllowHexSpecifier only " +
+ "AllowLeadingWhite and AllowTrailingWhite " +
+ "are permitted.");
+ return false;
+ }
+ } else if ((uint) style > (uint) NumberStyles.Any){
+ if (!tryParse)
+ exc = new ArgumentException ("Not a valid number style");
+ return false;
+ }
+
+ return true;
+ }
+
+ internal static bool JumpOverWhite (ref int pos, string s, bool reportError, bool tryParse, ref Exception exc)
+ {
+ while (pos < s.Length && Char.IsWhiteSpace (s [pos]))
+ pos++;
+
+ if (reportError && pos >= s.Length) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ return true;
+ }
+
+ internal static void FindSign (ref int pos, string s, NumberFormatInfo nfi,
+ ref bool foundSign, ref bool negative)
+ {
+ if ((pos + nfi.NegativeSign.Length) <= s.Length &&
+ string.CompareOrdinal(s, pos, nfi.NegativeSign, 0, nfi.NegativeSign.Length) == 0) {
+ negative = true;
+ foundSign = true;
+ pos += nfi.NegativeSign.Length;
+ } else if ((pos + nfi.PositiveSign.Length) <= s.Length &&
+ string.CompareOrdinal(s, pos, nfi.PositiveSign, 0, nfi.PositiveSign.Length) == 0) {
+ negative = false;
+ pos += nfi.PositiveSign.Length;
+ foundSign = true;
+ }
+ }
+
+ internal static void FindCurrency (ref int pos,
+ string s,
+ NumberFormatInfo nfi,
+ ref bool foundCurrency)
+ {
+ if ((pos + nfi.CurrencySymbol.Length) <= s.Length &&
+ s.Substring (pos, nfi.CurrencySymbol.Length) == nfi.CurrencySymbol) {
+ foundCurrency = true;
+ pos += nfi.CurrencySymbol.Length;
+ }
+ }
+
+ internal static bool FindExponent (ref int pos, string s, ref int exponent, bool tryParse, ref Exception exc)
+ {
+ exponent = 0;
+
+ if (pos >= s.Length || (s [pos] != 'e' && s[pos] != 'E')) {
+ exc = null;
+ return false;
+ }
+
+ var i = pos + 1;
+ if (i == s.Length) {
+ exc = tryParse ? null : GetFormatException ();
+ return true;
+ }
+
+ bool negative = false;
+ if (s [i] == '-') {
+ negative = true;
+ if(++i == s.Length){
+ exc = tryParse ? null : GetFormatException ();
+ return true;
+ }
+ }
+
+ if (s [i] == '+' && ++i == s.Length) {
+ exc = tryParse ? null : GetFormatException ();
+ return true;
+ }
+
+ long exp = 0; // temp long value
+ for (; i < s.Length; i++) {
+ if (!Char.IsDigit (s [i])) {
+ exc = tryParse ? null : GetFormatException ();
+ return true;
+ }
+
+ // Reduce the risk of throwing an overflow exc
+ exp = checked (exp * 10 - (int) (s [i] - '0'));
+ if (exp < Int32.MinValue || exp > Int32.MaxValue) {
+ exc = tryParse ? null : new OverflowException ("Value too large or too small.");
+ return true;
+ }
+ }
+
+ // exp value saved as negative
+ if(!negative)
+ exp = -exp;
+
+ exc = null;
+ exponent = (int)exp;
+ pos = i;
+ return true;
+ }
+
+ internal static bool FindOther (ref int pos, string s, string other)
+ {
+ if ((pos + other.Length) <= s.Length &&
+ s.Substring (pos, other.Length) == other) {
+ pos += other.Length;
+ return true;
+ }
+
+ return false;
+ }
+
+ internal static bool ValidDigit (char e, bool allowHex)
+ {
+ if (allowHex)
+ return Char.IsDigit (e) || (e >= 'A' && e <= 'F') || (e >= 'a' && e <= 'f');
+
+ return Char.IsDigit (e);
+ }
+
+ static Exception GetFormatException ()
+ {
+ return new FormatException ("Input string was not in the correct format");
+ }
+
+ static bool ProcessTrailingWhitespace (bool tryParse, string s, int position, ref Exception exc)
+ {
+ int len = s.Length;
+
+ for (int i = position; i < len; i++){
+ char c = s [i];
+
+ if (c != 0 && !Char.IsWhiteSpace (c)){
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+ }
+ return true;
+ }
+
+ static bool Parse (string s, bool tryParse, out BigInteger result, out Exception exc)
+ {
+ int len;
+ int i, sign = 1;
+ bool digits_seen = false;
+
+ result = Zero;
+ exc = null;
+
+ if (s == null) {
+ if (!tryParse)
+ exc = new ArgumentNullException ("value");
+ return false;
+ }
+
+ len = s.Length;
+
+ char c;
+ for (i = 0; i < len; i++){
+ c = s [i];
+ if (!Char.IsWhiteSpace (c))
+ break;
+ }
+
+ if (i == len) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ var info = Thread.CurrentThread.CurrentCulture.NumberFormat;
+
+ string negative = info.NegativeSign;
+ string positive = info.PositiveSign;
+
+ if (string.CompareOrdinal (s, i, positive, 0, positive.Length) == 0)
+ i += positive.Length;
+ else if (string.CompareOrdinal (s, i, negative, 0, negative.Length) == 0) {
+ sign = -1;
+ i += negative.Length;
+ }
+
+ BigInteger val = Zero;
+ for (; i < len; i++){
+ c = s [i];
+
+ if (c == '\0') {
+ i = len;
+ continue;
+ }
+
+ if (c >= '0' && c <= '9'){
+ byte d = (byte) (c - '0');
+
+ val = val * 10 + d;
+
+ digits_seen = true;
+ } else if (!ProcessTrailingWhitespace (tryParse, s, i, ref exc))
+ return false;
+ }
+
+ if (!digits_seen) {
+ if (!tryParse)
+ exc = GetFormatException ();
+ return false;
+ }
+
+ if (val.sign == 0)
+ result = val;
+ else if (sign == -1)
+ result = new BigInteger (-1, val.data);
+ else
+ result = new BigInteger (1, val.data);
+
+ return true;
+ }
+
public static BigInteger Min (BigInteger left, BigInteger right)
{
int ls = left.sign;
public static BigInteger GreatestCommonDivisor (BigInteger left, BigInteger right)
{
- if (left.data.Length == 1 && left.data [0] == 1)
+ if (left.sign != 0 && left.data.Length == 1 && left.data [0] == 1)
return new BigInteger (1, ONE);
- if (right.data.Length == 1 && right.data [0] == 1)
+ if (right.sign != 0 && right.data.Length == 1 && right.data [0] == 1)
return new BigInteger (1, ONE);
if (left.IsZero)
- return right;
+ return Abs(right);
if (right.IsZero)
- return left;
+ return Abs(left);
BigInteger x = new BigInteger (1, left.data);
BigInteger y = new BigInteger (1, right.data);
public override int GetHashCode ()
{
uint hash = (uint)(sign * 0x01010101u);
+ int len = data != null ? data.Length : 0;
- for (int i = 0; i < data.Length; ++i)
+ for (int i = 0; i < len; ++i)
hash ^= data [i];
return (int)hash;
}
return 0;
if (data.Length > 2)
- return -sign;
+ return sign;
if (other < 0)
other = -other;
}
static byte[] Resize (byte[] v, int len)
- {\r
- byte[] res = new byte [len];\r
- Array.Copy (v, res, Math.Min (v.Length, len));\r
- return res;\r
+ {
+ byte[] res = new byte [len];
+ Array.Copy (v, res, Math.Min (v.Length, len));
+ return res;
}
static uint[] Resize (uint[] v, int len)
{
- uint[] res = new uint [len];\r
- Array.Copy (v, res, Math.Min (v.Length, len));\r
- return res;\r
+ uint[] res = new uint [len];
+ Array.Copy (v, res, Math.Min (v.Length, len));
+ return res;
}
static uint[] CoreAdd (uint[] a, uint[] b)
static int CoreCompare (uint[] a, uint[] b)
{
- int al = a.Length;
- int bl = b.Length;
+ int al = a != null ? a.Length : 0;
+ int bl = b != null ? b.Length : 0;
if (al > bl)
return 1;
}
}
}
-}\r
+}
projects / mono.git / blobdiff