|
// ==++==
//
// Copyright (c) Microsoft Corporation. All rights reserved.
//
// ==--==
// The BigNumber class implements methods for formatting and parsing
// big numeric values. To format and parse numeric values, applications should
// use the Format and Parse methods provided by the numeric
// classes (BigInteger). Those
// Format and Parse methods share a common implementation
// provided by this class, and are thus documented in detail here.
//
// Formatting
//
// The Format methods provided by the numeric classes are all of the
// form
//
// public static String Format(XXX value, String format);
// public static String Format(XXX value, String format, NumberFormatInfo info);
//
// where XXX is the name of the particular numeric class. The methods convert
// the numeric value to a string using the format string given by the
// format parameter. If the format parameter is null or
// an empty string, the number is formatted as if the string "G" (general
// format) was specified. The info parameter specifies the
// NumberFormatInfo instance to use when formatting the number. If the
// info parameter is null or omitted, the numeric formatting information
// is obtained from the current culture. The NumberFormatInfo supplies
// such information as the characters to use for decimal and thousand
// separators, and the spelling and placement of currency symbols in monetary
// values.
//
// Format strings fall into two categories: Standard format strings and
// user-defined format strings. A format string consisting of a single
// alphabetic character (A-Z or a-z), optionally followed by a sequence of
// digits (0-9), is a standard format string. All other format strings are
// used-defined format strings.
//
// A standard format string takes the form Axx, where A is an
// alphabetic character called the format specifier and xx is a
// sequence of digits called the precision specifier. The format
// specifier controls the type of formatting applied to the number and the
// precision specifier controls the number of significant digits or decimal
// places of the formatting operation. The following table describes the
// supported standard formats.
//
// C c - Currency format. The number is
// converted to a string that represents a currency amount. The conversion is
// controlled by the currency format information of the NumberFormatInfo
// used to format the number. The precision specifier indicates the desired
// number of decimal places. If the precision specifier is omitted, the default
// currency precision given by the NumberFormatInfo is used.
//
// D d - Decimal format. This format is
// supported for integral types only. The number is converted to a string of
// decimal digits, prefixed by a minus sign if the number is negative. The
// precision specifier indicates the minimum number of digits desired in the
// resulting string. If required, the number will be left-padded with zeros to
// produce the number of digits given by the precision specifier.
//
// E e Engineering (scientific) format.
// The number is converted to a string of the form
// "-d.ddd...E+ddd" or "-d.ddd...e+ddd", where each
// 'd' indicates a digit (0-9). The string starts with a minus sign if the
// number is negative, and one digit always precedes the decimal point. The
// precision specifier indicates the desired number of digits after the decimal
// point. If the precision specifier is omitted, a default of 6 digits after
// the decimal point is used. The format specifier indicates whether to prefix
// the exponent with an 'E' or an 'e'. The exponent is always consists of a
// plus or minus sign and three digits.
//
// F f Fixed point format. The number is
// converted to a string of the form "-ddd.ddd....", where each
// 'd' indicates a digit (0-9). The string starts with a minus sign if the
// number is negative. The precision specifier indicates the desired number of
// decimal places. If the precision specifier is omitted, the default numeric
// precision given by the NumberFormatInfo is used.
//
// G g - General format. The number is
// converted to the shortest possible decimal representation using fixed point
// or scientific format. The precision specifier determines the number of
// significant digits in the resulting string. If the precision specifier is
// omitted, the number of significant digits is determined by the type of the
// number being converted (10 for int, 19 for long, 7 for
// float, 15 for double, 19 for Currency, and 29 for
// Decimal). Trailing zeros after the decimal point are removed, and the
// resulting string contains a decimal point only if required. The resulting
// string uses fixed point format if the exponent of the number is less than
// the number of significant digits and greater than or equal to -4. Otherwise,
// the resulting string uses scientific format, and the case of the format
// specifier controls whether the exponent is prefixed with an 'E' or an
// 'e'.
//
// N n Number format. The number is
// converted to a string of the form "-d,ddd,ddd.ddd....", where
// each 'd' indicates a digit (0-9). The string starts with a minus sign if the
// number is negative. Thousand separators are inserted between each group of
// three digits to the left of the decimal point. The precision specifier
// indicates the desired number of decimal places. If the precision specifier
// is omitted, the default numeric precision given by the
// NumberFormatInfo is used.
//
// X x - Hexadecimal format. This format is
// supported for integral types only. The number is converted to a string of
// hexadecimal digits. The format specifier indicates whether to use upper or
// lower case characters for the hexadecimal digits above 9 ('X' for 'ABCDEF',
// and 'x' for 'abcdef'). The precision specifier indicates the minimum number
// of digits desired in the resulting string. If required, the number will be
// left-padded with zeros to produce the number of digits given by the
// precision specifier.
//
// Some examples of standard format strings and their results are shown in the
// table below. (The examples all assume a default NumberFormatInfo.)
//
// Value Format Result
// 12345.6789 C $12,345.68
// -12345.6789 C ($12,345.68)
// 12345 D 12345
// 12345 D8 00012345
// 12345.6789 E 1.234568E+004
// 12345.6789 E10 1.2345678900E+004
// 12345.6789 e4 1.2346e+004
// 12345.6789 F 12345.68
// 12345.6789 F0 12346
// 12345.6789 F6 12345.678900
// 12345.6789 G 12345.6789
// 12345.6789 G7 12345.68
// 123456789 G7 1.234568E8
// 12345.6789 N 12,345.68
// 123456789 N4 123,456,789.0000
// 0x2c45e x 2c45e
// 0x2c45e X 2C45E
// 0x2c45e X8 0002C45E
//
// Format strings that do not start with an alphabetic character, or that start
// with an alphabetic character followed by a non-digit, are called
// user-defined format strings. The following table describes the formatting
// characters that are supported in user defined format strings.
//
//
// 0 - Digit placeholder. If the value being
// formatted has a digit in the position where the '0' appears in the format
// string, then that digit is copied to the output string. Otherwise, a '0' is
// stored in that position in the output string. The position of the leftmost
// '0' before the decimal point and the rightmost '0' after the decimal point
// determines the range of digits that are always present in the output
// string.
//
// # - Digit placeholder. If the value being
// formatted has a digit in the position where the '#' appears in the format
// string, then that digit is copied to the output string. Otherwise, nothing
// is stored in that position in the output string.
//
// . - Decimal point. The first '.' character
// in the format string determines the location of the decimal separator in the
// formatted value; any additional '.' characters are ignored. The actual
// character used as a the decimal separator in the output string is given by
// the NumberFormatInfo used to format the number.
//
// , - Thousand separator and number scaling.
// The ',' character serves two purposes. First, if the format string contains
// a ',' character between two digit placeholders (0 or #) and to the left of
// the decimal point if one is present, then the output will have thousand
// separators inserted between each group of three digits to the left of the
// decimal separator. The actual character used as a the decimal separator in
// the output string is given by the NumberFormatInfo used to format the
// number. Second, if the format string contains one or more ',' characters
// immediately to the left of the decimal point, or after the last digit
// placeholder if there is no decimal point, then the number will be divided by
// 1000 times the number of ',' characters before it is formatted. For example,
// the format string '0,,' will represent 100 million as just 100. Use of the
// ',' character to indicate scaling does not also cause the formatted number
// to have thousand separators. Thus, to scale a number by 1 million and insert
// thousand separators you would use the format string '#,##0,,'.
//
// % - Percentage placeholder. The presence of
// a '%' character in the format string causes the number to be multiplied by
// 100 before it is formatted. The '%' character itself is inserted in the
// output string where it appears in the format string.
//
// E+ E- e+ e- - Scientific notation.
// If any of the strings 'E+', 'E-', 'e+', or 'e-' are present in the format
// string and are immediately followed by at least one '0' character, then the
// number is formatted using scientific notation with an 'E' or 'e' inserted
// between the number and the exponent. The number of '0' characters following
// the scientific notation indicator determines the minimum number of digits to
// output for the exponent. The 'E+' and 'e+' formats indicate that a sign
// character (plus or minus) should always precede the exponent. The 'E-' and
// 'e-' formats indicate that a sign character should only precede negative
// exponents.
//
// \ - Literal character. A backslash character
// causes the next character in the format string to be copied to the output
// string as-is. The backslash itself isn't copied, so to place a backslash
// character in the output string, use two backslashes (\\) in the format
// string.
//
// 'ABC' "ABC" - Literal string. Characters
// enclosed in single or double quotation marks are copied to the output string
// as-is and do not affect formatting.
//
// ; - Section separator. The ';' character is
// used to separate sections for positive, negative, and zero numbers in the
// format string.
//
// Other - All other characters are copied to
// the output string in the position they appear.
//
// For fixed point formats (formats not containing an 'E+', 'E-', 'e+', or
// 'e-'), the number is rounded to as many decimal places as there are digit
// placeholders to the right of the decimal point. If the format string does
// not contain a decimal point, the number is rounded to the nearest
// integer. If the number has more digits than there are digit placeholders to
// the left of the decimal point, the extra digits are copied to the output
// string immediately before the first digit placeholder.
//
// For scientific formats, the number is rounded to as many significant digits
// as there are digit placeholders in the format string.
//
// To allow for different formatting of positive, negative, and zero values, a
// user-defined format string may contain up to three sections separated by
// semicolons. The results of having one, two, or three sections in the format
// string are described in the table below.
//
// Sections:
//
// One - The format string applies to all values.
//
// Two - The first section applies to positive values
// and zeros, and the second section applies to negative values. If the number
// to be formatted is negative, but becomes zero after rounding according to
// the format in the second section, then the resulting zero is formatted
// according to the first section.
//
// Three - The first section applies to positive
// values, the second section applies to negative values, and the third section
// applies to zeros. The second section may be left empty (by having no
// characters between the semicolons), in which case the first section applies
// to all non-zero values. If the number to be formatted is non-zero, but
// becomes zero after rounding according to the format in the first or second
// section, then the resulting zero is formatted according to the third
// section.
//
// For both standard and user-defined formatting operations on values of type
// float and double, if the value being formatted is a NaN (Not
// a Number) or a positive or negative infinity, then regardless of the format
// string, the resulting string is given by the NaNSymbol,
// PositiveInfinitySymbol, or NegativeInfinitySymbol property of
// the NumberFormatInfo used to format the number.
//
// Parsing
//
// The Parse methods provided by the numeric classes are all of the form
//
// public static XXX Parse(String s);
// public static XXX Parse(String s, int style);
// public static XXX Parse(String s, int style, NumberFormatInfo info);
//
// where XXX is the name of the particular numeric class. The methods convert a
// string to a numeric value. The optional style parameter specifies the
// permitted style of the numeric string. It must be a combination of bit flags
// from the NumberStyles enumeration. The optional info parameter
// specifies the NumberFormatInfo instance to use when parsing the
// string. If the info parameter is null or omitted, the numeric
// formatting information is obtained from the current culture.
//
// Numeric strings produced by the Format methods using the Currency,
// Decimal, Engineering, Fixed point, General, or Number standard formats
// (the C, D, E, F, G, and N format specifiers) are guaranteed to be parseable
// by the Parse methods if the NumberStyles.Any style is
// specified. Note, however, that the Parse methods do not accept
// NaNs or Infinities.
//
namespace System.Numerics {
using System;
using System.Diagnostics.Contracts;
using System.Globalization;
using System.Runtime.CompilerServices;
using System.Security;
using System.Text;
using Conditional = System.Diagnostics.ConditionalAttribute;
internal static class BigNumber {
#if !SILVERLIGHT || FEATURE_NETCORE
private const NumberStyles InvalidNumberStyles = ~(NumberStyles.AllowLeadingWhite | NumberStyles.AllowTrailingWhite
| NumberStyles.AllowLeadingSign | NumberStyles.AllowTrailingSign
| NumberStyles.AllowParentheses | NumberStyles.AllowDecimalPoint
| NumberStyles.AllowThousands | NumberStyles.AllowExponent
| NumberStyles.AllowCurrencySymbol | NumberStyles.AllowHexSpecifier);
internal struct BigNumberBuffer {
public StringBuilder digits;
public int precision;
public int scale;
public bool sign; // negative sign exists
public static BigNumberBuffer Create() {
BigNumberBuffer number = new BigNumberBuffer();
number.digits = new StringBuilder();
return number;
}
}
internal static bool TryValidateParseStyleInteger(NumberStyles style, out ArgumentException e) {
// Check for undefined flags
if ((style & InvalidNumberStyles) != 0) {
e = new ArgumentException(SR.GetString(SR.Argument_InvalidNumberStyles, "style"));
return false;
}
if ((style & NumberStyles.AllowHexSpecifier) != 0) { // Check for hex number
if ((style & ~NumberStyles.HexNumber) != 0) {
e = new ArgumentException(SR.GetString(SR.Argument_InvalidHexStyle));
return false;
}
}
e = null;
return true;
}
[SecuritySafeCritical]
internal unsafe static Boolean TryParseBigInteger(String value, NumberStyles style, NumberFormatInfo info, out BigInteger result) {
result = BigInteger.Zero;
ArgumentException e;
if (!TryValidateParseStyleInteger(style, out e))
throw e; // TryParse still throws ArgumentException on invalid NumberStyles
BigNumberBuffer bignumber = BigNumberBuffer.Create();
Byte * numberBufferBytes = stackalloc Byte[Number.NumberBuffer.NumberBufferBytes];
Number.NumberBuffer number = new Number.NumberBuffer(numberBufferBytes);
result = 0;
if (!Number.TryStringToNumber(value, style, ref number, bignumber.digits, info, false)) {
return false;
}
bignumber.precision = number.precision;
bignumber.scale = number.scale;
bignumber.sign = number.sign;
if ((style & NumberStyles.AllowHexSpecifier) != 0) {
if (!HexNumberToBigInteger(ref bignumber, ref result)) {
return false;
}
}
else {
if (!NumberToBigInteger(ref bignumber, ref result)) {
return false;
}
}
return true;
}
internal unsafe static BigInteger ParseBigInteger(String value, NumberStyles style, NumberFormatInfo info) {
if (value == null)
throw new ArgumentNullException("value");
ArgumentException e;
if (!TryValidateParseStyleInteger(style, out e))
throw e;
BigInteger result = BigInteger.Zero;
if (!TryParseBigInteger(value, style, info, out result)) {
throw new FormatException(SR.GetString(SR.Overflow_ParseBigInteger));
}
return result;
}
private unsafe static Boolean HexNumberToBigInteger(ref BigNumberBuffer number, ref BigInteger value) {
if (number.digits == null || number.digits.Length == 0)
return false;
int len = number.digits.Length - 1; // ignore trailing '\0'
byte[] bits = new byte[(len / 2) + (len % 2)];
bool shift = false;
bool isNegative = false;
int bitIndex = 0;
// parse the string into a little-endian two's complement byte array
// string value : O F E B 7 \0
// string index (i) : 0 1 2 3 4 5 <--
// byte[] (bitIndex): 2 1 1 0 0 <--
//
for (int i = len-1; i > -1; i--) {
char c = number.digits[i];
byte b;
if (c >= '0' && c <= '9') {
b = (byte)(c - '0');
}
else if (c >= 'A' && c <= 'F') {
b = (byte)((c - 'A') + 10);
}
else {
Contract.Assert(c >= 'a' && c <= 'f');
b = (byte)((c - 'a') + 10);
}
if (i == 0 && (b & 0x08) == 0x08)
isNegative = true;
if (shift) {
bits[bitIndex] = (byte)(bits[bitIndex] | (b << 4));
bitIndex++;
}
else {
bits[bitIndex] = isNegative ? (byte)(b | 0xF0) : (b);
}
shift = !shift;
}
value = new BigInteger(bits);
return true;
}
private unsafe static Boolean NumberToBigInteger(ref BigNumberBuffer number, ref BigInteger value) {
Int32 i = number.scale;
Int32 cur = 0;
value = 0;
while (--i >= 0) {
value *= 10;
if (number.digits[cur] != '\0') {
value += (Int32)(number.digits[cur++] - '0');
}
}
while (number.digits[cur] != '\0') {
if (number.digits[cur++] != '0') return false; // disallow non-zero trailing decimal places
}
if (number.sign) {
value = -value;
}
return true;
}
#endif //!SILVERLIGHT ||FEATURE_NETCORE
// this function is consistent with VM\COMNumber.cpp!COMNumber::ParseFormatSpecifier
internal static char ParseFormatSpecifier(String format, out Int32 digits) {
digits = -1;
if (String.IsNullOrEmpty(format)) {
return 'R';
}
int i = 0;
char ch = format[i];
if (ch >= 'A' && ch <= 'Z' || ch >= 'a' && ch <= 'z') {
i++;
int n = -1;
if (i < format.Length && format[i] >= '0' && format[i] <= '9') {
n = format[i++] - '0';
while (i < format.Length && format[i] >= '0' && format[i] <= '9') {
n = n * 10 + (format[i++] - '0');
if (n >= 10)
break;
}
}
if (i >= format.Length || format[i] == '\0') {
digits = n;
return ch;
}
}
return (char)0; // custom format
}
private static String FormatBigIntegerToHexString(BigInteger value, char format, int digits, NumberFormatInfo info) {
StringBuilder sb = new StringBuilder();
byte[] bits = value.ToByteArray();
String fmt = null;
int cur = bits.Length-1;
if (cur > -1) {
// [FF..F8] drop the high F as the two's complement negative number remains clear
// [F7..08] retain the high bits as the two's complement number is wrong without it
// [07..00] drop the high 0 as the two's complement positive number remains clear
bool clearHighF = false;
byte head = bits[cur];
if (head > 0xF7) {
head -= 0xF0;
clearHighF = true;
}
if (head < 0x08 || clearHighF) {
// {0xF8-0xFF} print as {8-F}
// {0x00-0x07} print as {0-7}
fmt = String.Format(CultureInfo.InvariantCulture, "{0}1", format);
sb.Append(head.ToString(fmt, info));
cur--;
}
}
if (cur > -1) {
fmt = String.Format(CultureInfo.InvariantCulture, "{0}2", format);
while (cur > -1) {
sb.Append(bits[cur--].ToString(fmt, info));
}
}
if (digits > 0 && digits > sb.Length) {
// insert leading zeros. User specified "X5" so we create "0ABCD" instead of "ABCD"
sb.Insert(0, (value._sign >= 0 ? ("0") : (format == 'x' ? "f" : "F")), digits - sb.Length);
}
return sb.ToString();
}
//
// internal [unsafe] static String FormatBigInteger(BigInteger value, String format, NumberFormatInfo info) {
//
#if !SILVERLIGHT ||FEATURE_NETCORE
[SecuritySafeCritical]
#endif // !SILVERLIGHT ||FEATURE_NETCORE
internal
#if !SILVERLIGHT ||FEATURE_NETCORE
unsafe
#endif //!SILVERLIGHT ||FEATURE_NETCORE
static String FormatBigInteger(BigInteger value, String format, NumberFormatInfo info) {
int digits = 0;
char fmt = ParseFormatSpecifier(format, out digits);
if (fmt == 'x' || fmt == 'X')
return FormatBigIntegerToHexString(value, fmt, digits, info);
bool decimalFmt = (fmt == 'g' || fmt == 'G' || fmt == 'd' || fmt == 'D' || fmt == 'r' || fmt == 'R');
#if SILVERLIGHT ||FEATURE_NETCORE
if (!decimalFmt) {
// Silverlight supports invariant formats only
throw new FormatException(SR.GetString(SR.Format_InvalidFormatSpecifier));
}
#endif //SILVERLIGHT ||FEATURE_NETCORE
if (value._bits == null) {
if (fmt == 'g' || fmt == 'G' || fmt == 'r' || fmt == 'R') {
if (digits > 0)
format = String.Format(CultureInfo.InvariantCulture, "D{0}", digits.ToString(CultureInfo.InvariantCulture));
else
format = "D";
}
return value._sign.ToString(format, info);
}
// First convert to base 10^9.
const uint kuBase = 1000000000; // 10^9
const int kcchBase = 9;
int cuSrc = BigInteger.Length(value._bits);
int cuMax;
try {
cuMax = checked(cuSrc * 10 / 9 + 2);
}
catch (OverflowException e) { throw new FormatException(SR.GetString(SR.Format_TooLarge), e); }
uint[] rguDst = new uint[cuMax];
int cuDst = 0;
for (int iuSrc = cuSrc; --iuSrc >= 0; ) {
uint uCarry = value._bits[iuSrc];
for (int iuDst = 0; iuDst < cuDst; iuDst++) {
Contract.Assert(rguDst[iuDst] < kuBase);
ulong uuRes = NumericsHelpers.MakeUlong(rguDst[iuDst], uCarry);
rguDst[iuDst] = (uint)(uuRes % kuBase);
uCarry = (uint)(uuRes / kuBase);
}
if (uCarry != 0) {
rguDst[cuDst++] = uCarry % kuBase;
uCarry /= kuBase;
if (uCarry != 0)
rguDst[cuDst++] = uCarry;
}
}
int cchMax;
try {
// Each uint contributes at most 9 digits to the decimal representation.
cchMax = checked(cuDst * kcchBase);
}
catch (OverflowException e) { throw new FormatException(SR.GetString(SR.Format_TooLarge), e); }
if (decimalFmt) {
if (digits > 0 && digits > cchMax)
cchMax = digits;
if (value._sign < 0) {
try {
// Leave an extra slot for a minus sign.
cchMax = checked(cchMax + info.NegativeSign.Length);
}
catch (OverflowException e) { throw new FormatException(SR.GetString(SR.Format_TooLarge), e); }
}
}
int rgchBufSize;
try {
// We'll pass the rgch buffer to native code, which is going to treat it like a string of digits, so it needs
// to be null terminated. Let's ensure that we can allocate a buffer of that size.
rgchBufSize = checked(cchMax + 1);
} catch (OverflowException e) { throw new FormatException(SR.GetString(SR.Format_TooLarge), e); }
char[] rgch = new char[rgchBufSize];
int ichDst = cchMax;
for (int iuDst = 0; iuDst < cuDst - 1; iuDst++) {
uint uDig = rguDst[iuDst];
Contract.Assert(uDig < kuBase);
for (int cch = kcchBase; --cch >= 0; ) {
rgch[--ichDst] = (char)('0' + uDig % 10);
uDig /= 10;
}
}
for (uint uDig = rguDst[cuDst - 1]; uDig != 0; ) {
rgch[--ichDst] = (char)('0' + uDig % 10);
uDig /= 10;
}
#if !SILVERLIGHT ||FEATURE_NETCORE
if (!decimalFmt) {
//
// Go to the VM for GlobLoc aware formatting
//
Byte * numberBufferBytes = stackalloc Byte[Number.NumberBuffer.NumberBufferBytes];
Number.NumberBuffer number = new Number.NumberBuffer(numberBufferBytes);
// sign = true for negative and false for 0 and positive values
number.sign = (value._sign < 0);
// the cut-off point to switch (G)eneral from (F)ixed-point to (E)xponential form
number.precision = 29;
number.digits[0] = '\0';
number.scale = cchMax - ichDst;
int maxDigits = Math.Min(ichDst + 50, cchMax);
for (int i = ichDst; i < maxDigits; i++) {
number.digits[i - ichDst] = rgch[i];
}
fixed(char* pinnedExtraDigits = rgch) {
return Number.FormatNumberBuffer(number.PackForNative(), format, info, pinnedExtraDigits + ichDst);
}
}
#endif //!SILVERLIGHT ||FEATURE_NETCORE
// Format Round-trip decimal
// This format is supported for integral types only. The number is converted to a string of
// decimal digits (0-9), prefixed by a minus sign if the number is negative. The precision
// specifier indicates the minimum number of digits desired in the resulting string. If required,
// the number is padded with zeros to its left to produce the number of digits given by the
// precision specifier.
int numDigitsPrinted = cchMax - ichDst;
while (digits > 0 && digits > numDigitsPrinted) {
// pad leading zeros
rgch[--ichDst] = '0';
digits--;
}
if (value._sign < 0) {
String negativeSign = info.NegativeSign;
for (int i = info.NegativeSign.Length - 1; i > -1; i--)
rgch[--ichDst] = info.NegativeSign[i];
}
return new String(rgch, ichDst, cchMax - ichDst);
}
}
}
|