diff options
author | Tanner Gooding <tagoo@outlook.com> | 2018-09-16 22:35:26 -0700 |
---|---|---|
committer | Tanner Gooding <tagoo@outlook.com> | 2018-09-20 13:12:46 -0700 |
commit | 520d408e2ce6a243779db51661a869af199908d4 (patch) | |
tree | b1e2620a74566aa66fb8f6a58d8ef30510907e5d /src | |
parent | b9e981c3e8fc1c718958ca3e0433ba6a6e3cf3cc (diff) | |
download | coreclr-520d408e2ce6a243779db51661a869af199908d4.tar.gz coreclr-520d408e2ce6a243779db51661a869af199908d4.tar.bz2 coreclr-520d408e2ce6a243779db51661a869af199908d4.zip |
Removing the Dragon4 and DoubleToNumber native implementation.
Diffstat (limited to 'src')
-rw-r--r-- | src/classlibnative/bcltype/CMakeLists.txt | 1 | ||||
-rw-r--r-- | src/classlibnative/bcltype/bignum.cpp | 599 | ||||
-rw-r--r-- | src/classlibnative/bcltype/bignum.h | 152 | ||||
-rw-r--r-- | src/classlibnative/bcltype/number.cpp | 306 | ||||
-rw-r--r-- | src/classlibnative/bcltype/number.h | 1 | ||||
-rw-r--r-- | src/vm/ecalllist.h | 1 |
6 files changed, 0 insertions, 1060 deletions
diff --git a/src/classlibnative/bcltype/CMakeLists.txt b/src/classlibnative/bcltype/CMakeLists.txt index 41cf3cffb5..ada524cca0 100644 --- a/src/classlibnative/bcltype/CMakeLists.txt +++ b/src/classlibnative/bcltype/CMakeLists.txt @@ -7,7 +7,6 @@ endif(PerfCountersSupportedBuild) set(BCLTYPE_SOURCES arraynative.cpp arrayhelpers.cpp - bignum.cpp diyfp.cpp grisu3.cpp number.cpp diff --git a/src/classlibnative/bcltype/bignum.cpp b/src/classlibnative/bcltype/bignum.cpp deleted file mode 100644 index c4aa534524..0000000000 --- a/src/classlibnative/bcltype/bignum.cpp +++ /dev/null @@ -1,599 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. -// -// File: bignum.cpp -// - -// - -#include "bignum.h" -#include <intrin.h> - -constexpr UINT32 BigNum::m_power10UInt32Table[UINT32POWER10NUM]; -BigNum BigNum::m_power10BigNumTable[BIGPOWER10NUM]; -BigNum::StaticInitializer BigNum::m_initializer; - -BigNum::BigNum() - :m_len(0) // Note: we do not zeroing m_blocks due to performance. -{ -} - -BigNum::BigNum(UINT32 value) -{ - SetUInt32(value); -} - -BigNum::BigNum(UINT64 value) -{ - SetUInt64(value); -} - -BigNum::~BigNum() -{ -} - -BigNum& BigNum::operator=(const BigNum &rhs) -{ - memcpy(m_blocks, rhs.m_blocks, ((UINT32)rhs.m_len) * sizeof(UINT32)); - m_len = rhs.m_len; - - return *this; -} - -int BigNum::Compare(const BigNum& lhs, const BigNum& rhs) -{ - _ASSERTE(lhs.m_len <= BIGSIZE); - _ASSERTE(rhs.m_len <= BIGSIZE); - - int lenDiff = (int)lhs.m_len - (int)rhs.m_len; - if (lenDiff != 0) - { - return lenDiff; - } - - if (lhs.m_len == 0) - { - _ASSERTE(rhs.m_len == 0); - - return 0; - } - - for (INT32 currentIndex = lhs.m_len - 1; currentIndex >= 0; --currentIndex) - { - INT64 diff = (INT64)(lhs.m_blocks[currentIndex]) - (INT64)(rhs.m_blocks[currentIndex]); - if (diff != 0) - { - return diff > 0 ? 1 : -1; - } - } - - return 0; -} - -void BigNum::ShiftLeft(UINT64 input, UINT32 shift, BigNum& output) -{ - if (shift == 0) - { - return; - } - - UINT32 shiftBlocks = shift / 32; - UINT32 remaningToShiftBits = shift % 32; - - if (shiftBlocks > 0) - { - // If blocks shifted, we should fill the corresponding blocks with zero. - output.ExtendBlocks(0, shiftBlocks); - } - - if (remaningToShiftBits == 0) - { - // We shift 32 * n (n >= 1) bits. No remaining bits. - output.ExtendBlock((UINT32)(input & 0xFFFFFFFF)); - - UINT32 highBits = (UINT32)(input >> 32); - if (highBits != 0) - { - output.ExtendBlock(highBits); - } - } - else - { - // Extract the high position bits which would be shifted out of range. - UINT32 highPositionBits = (UINT32)input >> (64 - remaningToShiftBits); - - // Shift the input. The result should be stored to current block. - UINT64 shiftedInput = input << remaningToShiftBits; - output.ExtendBlock(shiftedInput & 0xFFFFFFFF); - - UINT32 highBits = (UINT32)(input >> 32); - if (highBits != 0) - { - output.ExtendBlock(highBits); - } - - if (highPositionBits != 0) - { - // If the high position bits is not 0, we should store them to next block. - output.ExtendBlock(highPositionBits); - } - } -} - -void BigNum::ShiftLeft(UINT32 shift) -{ - if (m_len == 0 || shift == 0) - { - return; - } - - UINT32 shiftBlocks = shift / 32; - UINT32 shiftBits = shift % 32; - - // Process blocks high to low so that we can safely process in place - int inLength = m_len; - - // Check if the shift is block aligned - if (shiftBits == 0) - { - // Copy blocks from high to low - UINT32* pInCurrent = m_blocks + inLength; - UINT32* pOutCurrent = pInCurrent + shiftBlocks; - while (pInCurrent >= m_blocks) - { - *pOutCurrent = *pInCurrent; - - --pInCurrent; - --pOutCurrent; - } - - m_len += shiftBlocks; - - // Zero the remaining low blocks - memset(m_blocks, 0, shiftBlocks); - } - else - { - // We need to shift partial blocks - int inBlockIdx = inLength - 1; - UINT32 outBlockIdx = inLength + shiftBlocks; - - _ASSERTE(outBlockIdx < BIGSIZE); - - // Set the length to hold the shifted blocks - m_len = outBlockIdx + 1; - - // Output the initial blocks - const UINT32 lowBitsShift = (32 - shiftBits); - UINT32 highBits = 0; - UINT32 block = m_blocks[inBlockIdx]; - UINT32 lowBits = block >> lowBitsShift; - while (inBlockIdx > 0) - { - m_blocks[outBlockIdx] = highBits | lowBits; - highBits = block << shiftBits; - - --inBlockIdx; - --outBlockIdx; - - block = m_blocks[inBlockIdx]; - lowBits = block >> lowBitsShift; - } - - // Output the final blocks - m_blocks[outBlockIdx] = highBits | lowBits; - m_blocks[outBlockIdx - 1] = block << shiftBits; - - // Zero the remaining low blocks - memset(m_blocks, 0, shiftBlocks * sizeof(UINT32)); - - // Check if the terminating block has no set bits - if (m_blocks[m_len - 1] == 0) - { - --m_len; - } - } -} - -void BigNum::Pow10(int exp, BigNum& result) -{ - // We leverage two arrays - m_power10UInt32Table and m_power10BigNumTable to speed up the - // pow10 calculation. - // - // m_power10UInt32Table stores the results of 10^0 to 10^7. - // m_power10BigNumTable stores the results of 10^8, 10^16, 10^32, 10^64, 10^128 and 10^256. - // - // For example, let's say exp = (111111)2. We can split the exp to two parts, one is small exp, - // which 10^smallExp can be represented as UINT32, another part is 10^bigExp, which must be represented as BigNum. - // So the result should be 10^smallExp * 10^bigExp. - // - // Calculate 10^smallExp is simple, we just lookup the 10^smallExp from m_power10UInt32Table. - // But here's a bad news: although UINT32 can represent 10^9, exp 9's binary representation is 1001. - // That means 10^(1011), 10^(1101), 10^(1111) all cannot be stored as UINT32, we cannot easily say something like: - // "Any bits <= 3 is small exp, any bits > 3 is big exp". So instead of involving 10^8, 10^9 to m_power10UInt32Table, - // consider 10^8 and 10^9 as a bigNum, so they fall into m_power10BigNumTable. Now we can have a simple rule: - // "Any bits <= 3 is small exp, any bits > 3 is big exp". - // - // For (111111)2, we first calculate 10^(smallExp), which is 10^(7), now we can shift right 3 bits, prepare to calculate the bigExp part, - // the exp now becomes (000111)2. - // - // Apparently the lowest bit of bigExp should represent 10^8 because we have already shifted 3 bits for smallExp, so m_power10BigNumTable[0] = 10^8. - // Now let's shift exp right 1 bit, the lowest bit should represent 10^(8 * 2) = 10^16, and so on... - // - // That's why we just need the values of m_power10BigNumTable be power of 2. - // - // More details of this implementation can be found at: https://github.com/dotnet/coreclr/pull/12894#discussion_r128890596 - - BigNum temp1; - BigNum temp2; - - BigNum* pCurrentTemp = &temp1; - BigNum* pNextTemp = &temp2; - - // Extract small exp. - UINT32 smallExp = exp & 0x7; - pCurrentTemp->SetUInt32(m_power10UInt32Table[smallExp]); - - exp >>= 3; - UINT32 idx = 0; - - while (exp != 0) - { - // If the current bit is set, multiply it with the corresponding power of 10 - if (exp & 1) - { - // Multiply into the next temporary - Multiply(*pCurrentTemp, m_power10BigNumTable[idx], *pNextTemp); - - // Swap to the next temporary - BigNum* t = pNextTemp; - pNextTemp = pCurrentTemp; - pCurrentTemp = t; - } - - // Advance to the next bit - ++idx; - exp >>= 1; - } - - result = *pCurrentTemp; -} - -void BigNum::PrepareHeuristicDivide(BigNum* pDividend, BigNum* pDivisor) -{ - UINT32 hiBlock = pDivisor->m_blocks[pDivisor->m_len - 1]; - if (hiBlock < 8 || hiBlock > 429496729) - { - // Inspired by http://www.ryanjuckett.com/programming/printing-floating-point-numbers/ - // Perform a bit shift on all values to get the highest block of the divisor into - // the range [8,429496729]. We are more likely to make accurate quotient estimations - // in heuristicDivide() with higher divisor values so - // we shift the divisor to place the highest bit at index 27 of the highest block. - // This is safe because (2^28 - 1) = 268435455 which is less than 429496729. This means - // that all values with a highest bit at index 27 are within range. - UINT32 hiBlockLog2 = LogBase2(hiBlock); - UINT32 shift = (59 - hiBlockLog2) % 32; - - pDivisor->ShiftLeft(shift); - pDividend->ShiftLeft(shift); - } -} - -UINT32 BigNum::HeuristicDivide(BigNum* pDividend, const BigNum& divisor) -{ - UINT32 len = divisor.m_len; - if (pDividend->m_len < len) - { - return 0; - } - - const UINT32* pFinalDivisorBlock = divisor.m_blocks + len - 1; - UINT32* pFinalDividendBlock = pDividend->m_blocks + len - 1; - - // This is an estimated quotient. Its error should be less than 2. - // Reference inequality: - // a/b - floor(floor(a)/(floor(b) + 1)) < 2 - UINT32 quotient = *pFinalDividendBlock / (*pFinalDivisorBlock + 1); - - if (quotient != 0) - { - // Now we use our estimated quotient to update each block of dividend. - // dividend = dividend - divisor * quotient - const UINT32 *pDivisorCurrent = divisor.m_blocks; - UINT32 *pDividendCurrent = pDividend->m_blocks; - - UINT64 borrow = 0; - UINT64 carry = 0; - do - { - UINT64 product = (UINT64)*pDivisorCurrent * (UINT64)quotient + carry; - carry = product >> 32; - - UINT64 difference = (UINT64)*pDividendCurrent - (product & 0xFFFFFFFF) - borrow; - borrow = (difference >> 32) & 1; - - *pDividendCurrent = difference & 0xFFFFFFFF; - - ++pDivisorCurrent; - ++pDividendCurrent; - } while (pDivisorCurrent <= pFinalDivisorBlock); - - // Remove all leading zero blocks from dividend - while (len > 0 && pDividend->m_blocks[len - 1] == 0) - { - --len; - } - - pDividend->m_len = len; - } - - // If the dividend is still larger than the divisor, we overshot our estimate quotient. To correct, - // we increment the quotient and subtract one more divisor from the dividend (Because we guaranteed the error range). - if (BigNum::Compare(*pDividend, divisor) >= 0) - { - ++quotient; - - // dividend = dividend - divisor - const UINT32 *pDivisorCur = divisor.m_blocks; - UINT32 *pDividendCur = pDividend->m_blocks; - - UINT64 borrow = 0; - do - { - UINT64 difference = (UINT64)*pDividendCur - (UINT64)*pDivisorCur - borrow; - borrow = (difference >> 32) & 1; - - *pDividendCur = difference & 0xFFFFFFFF; - - ++pDivisorCur; - ++pDividendCur; - } while (pDivisorCur <= pFinalDivisorBlock); - - // Remove all leading zero blocks from dividend - while (len > 0 && pDividend->m_blocks[len - 1] == 0) - { - --len; - } - - pDividend->m_len = len; - } - - return quotient; -} - -void BigNum::Multiply(UINT32 value) -{ - Multiply(*this, value, *this); -} - -void BigNum::Multiply(const BigNum& value) -{ - BigNum temp; - BigNum::Multiply(*this, value, temp); - - memcpy(m_blocks, temp.m_blocks, ((UINT32)temp.m_len) * sizeof(UINT32)); - m_len = temp.m_len; -} - -void BigNum::Multiply(const BigNum& lhs, UINT32 value, BigNum& result) -{ - if (lhs.IsZero() || value == 1) - { - result = lhs; - - return; - } - - if (value == 0) - { - result.SetZero(); - - return; - } - - const UINT32* pCurrent = lhs.m_blocks; - const UINT32* pEnd = pCurrent + lhs.m_len; - UINT32* pResultCurrent = result.m_blocks; - - UINT64 carry = 0; - while (pCurrent != pEnd) - { - UINT64 product = (UINT64)(*pCurrent) * (UINT64)value + carry; - carry = product >> 32; - *pResultCurrent = (UINT32)(product & 0xFFFFFFFF); - - ++pResultCurrent; - ++pCurrent; - } - - if (carry != 0) - { - _ASSERTE(lhs.m_len + 1 <= BIGSIZE); - *pResultCurrent = (UINT32)carry; - result.m_len += lhs.m_len + 1; - } -} - -void BigNum::Multiply(const BigNum& lhs, const BigNum& rhs, BigNum& result) -{ - if (lhs.IsZero() || (rhs.m_len == 1 && rhs.m_blocks[0] == 1)) - { - result = lhs; - - return; - } - - if (rhs.IsZero()) - { - result.SetZero(); - - return; - } - - const BigNum* pLarge = NULL; - const BigNum* pSmall = NULL; - if (lhs.m_len < rhs.m_len) - { - pSmall = &lhs; - pLarge = &rhs; - } - else - { - pSmall = &rhs; - pLarge = &lhs; - } - - UINT32 maxResultLength = pSmall->m_len + pLarge->m_len; - _ASSERTE(maxResultLength <= BIGSIZE); - - // Zero out result internal blocks. - memset(result.m_blocks, 0, sizeof(UINT32) * BIGSIZE); - - const UINT32* pLargeBegin = pLarge->m_blocks; - const UINT32* pLargeEnd = pLarge->m_blocks + pLarge->m_len; - - UINT32* pResultStart = result.m_blocks; - const UINT32* pSmallCurrent = pSmall->m_blocks; - const UINT32* pSmallEnd = pSmallCurrent + pSmall->m_len; - - while (pSmallCurrent != pSmallEnd) - { - // Multiply each block of large BigNum. - if (*pSmallCurrent != 0) - { - const UINT32* pLargeCurrent = pLargeBegin; - UINT32* pResultCurrent = pResultStart; - UINT64 carry = 0; - - do - { - UINT64 product = (UINT64)(*pResultCurrent) + (UINT64)(*pSmallCurrent) * (UINT64)(*pLargeCurrent) + carry; - carry = product >> 32; - *pResultCurrent = (UINT32)(product & 0xFFFFFFFF); - - ++pResultCurrent; - ++pLargeCurrent; - } while (pLargeCurrent != pLargeEnd); - - *pResultCurrent = (UINT32)(carry & 0xFFFFFFFF); - } - - ++pSmallCurrent; - ++pResultStart; - } - - if (maxResultLength > 0 && result.m_blocks[maxResultLength - 1] == 0) - { - result.m_len = maxResultLength - 1; - } - else - { - result.m_len = maxResultLength; - } -} - -void BigNum::Multiply10() -{ - if (IsZero()) - { - return; - } - - const UINT32* pCurrent = m_blocks; - const UINT32* pEnd = pCurrent + m_len; - UINT32* pResultCurrent = m_blocks; - - UINT64 carry = 0; - while (pCurrent != pEnd) - { - UINT64 product = ((UINT64)(*pCurrent) << 3) + ((UINT64)(*pCurrent) << 1) + carry; - carry = product >> 32; - *pResultCurrent = (UINT32)(product & 0xFFFFFFFF); - - ++pResultCurrent; - ++pCurrent; - } - - if (carry != 0) - { - _ASSERTE(m_len + 1 <= BIGSIZE); - *pResultCurrent = (UINT32)carry; - m_len += 1; - } -} - -bool BigNum::IsZero() const -{ - return m_len == 0; -} - -void BigNum::SetUInt32(UINT32 value) -{ - m_len = 1; - m_blocks[0] = value; -} - -void BigNum::SetUInt64(UINT64 value) -{ - m_blocks[0] = (UINT32)(value & 0xFFFFFFFF); - m_blocks[1] = (UINT32)(value >> 32); - m_len = (m_blocks[1] == 0) ? 1 : 2; -} - -void BigNum::SetZero() -{ - m_len = 0; -} - -void BigNum::ExtendBlock(UINT32 blockValue) -{ - m_blocks[m_len] = blockValue; - ++m_len; -} - -void BigNum::ExtendBlocks(UINT32 blockValue, UINT32 blockCount) -{ - _ASSERTE(blockCount > 0); - - if (blockCount == 1) - { - ExtendBlock(blockValue); - - return; - } - - memset(m_blocks + m_len, 0, (blockCount - 1) * sizeof(UINT32)); - m_len += blockCount; - m_blocks[m_len - 1] = blockValue; -} - -UINT32 BigNum::LogBase2(UINT32 value) -{ - _ASSERTE(value != 0); - - DWORD r; - BitScanReverse(&r, (DWORD)value); - - return (UINT32)r; -} - -UINT32 BigNum::LogBase2(UINT64 value) -{ - _ASSERTE(value != 0); - -#if (defined(_X86_) || defined(_ARM_)) && !defined(FEATURE_PAL) - UINT64 temp = value >> 32; - if (temp != 0) - { - return 32 + LogBase2((UINT32)temp); - } - - return LogBase2((UINT32)value); -#else - DWORD r; - BitScanReverse64(&r, (DWORD64)value); - - return (UINT32)r; -#endif -} diff --git a/src/classlibnative/bcltype/bignum.h b/src/classlibnative/bcltype/bignum.h deleted file mode 100644 index 0af7710d6e..0000000000 --- a/src/classlibnative/bcltype/bignum.h +++ /dev/null @@ -1,152 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. -// -// File: bignum.h -// - -// - -#ifndef _BIGNUM_H_ -#define _BIGNUM_H_ - -#include <clrtypes.h> - -class BigNum -{ -public: - BigNum(); - BigNum(UINT32 value); - BigNum(UINT64 value); - ~BigNum(); - - BigNum & operator=(const BigNum &rhs); - - static UINT32 LogBase2(UINT32 val); - static UINT32 LogBase2(UINT64 val); - - static int Compare(const BigNum& lhs, const BigNum& rhs); - - static void ShiftLeft(UINT64 input, UINT32 shift, BigNum& output); - static void Pow10(int exp, BigNum& result); - static void PrepareHeuristicDivide(BigNum* pDividend, BigNum* divisor); - static UINT32 HeuristicDivide(BigNum* pDividend, const BigNum& divisor); - static void Multiply(const BigNum& lhs, UINT32 value, BigNum& result); - static void Multiply(const BigNum& lhs, const BigNum& rhs, BigNum& result); - - bool IsZero() const; - - void Multiply(UINT32 value); - void Multiply(const BigNum& value); - void Multiply10(); - void ShiftLeft(UINT32 shift); - void SetUInt32(UINT32 value); - void SetUInt64(UINT64 value); - void SetZero(); - void ExtendBlock(UINT32 blockValue); - void ExtendBlocks(UINT32 blockValue, UINT32 blockCount); - -private: - - static const UINT32 BIGSIZE = 35; - static const UINT32 UINT32POWER10NUM = 8; - static const UINT32 BIGPOWER10NUM = 6; - static constexpr UINT32 m_power10UInt32Table[UINT32POWER10NUM] = - { - 1, // 10^0 - 10, // 10^1 - 100, // 10^2 - 1000, // 10^3 - 10000, // 10^4 - 100000, // 10^5 - 1000000, // 10^6 - 10000000, // 10^7 - }; - static BigNum m_power10BigNumTable[BIGPOWER10NUM]; - - static class StaticInitializer - { - public: - StaticInitializer() - { - // 10^8 - m_power10BigNumTable[0].m_len = (UINT32)1; - m_power10BigNumTable[0].m_blocks[0] = (UINT32)100000000; - - // 10^16 - m_power10BigNumTable[1].m_len = (UINT32)2; - m_power10BigNumTable[1].m_blocks[0] = (UINT32)0x6fc10000; - m_power10BigNumTable[1].m_blocks[1] = (UINT32)0x002386f2; - - // 10^32 - m_power10BigNumTable[2].m_len = (UINT32)4; - m_power10BigNumTable[2].m_blocks[0] = (UINT32)0x00000000; - m_power10BigNumTable[2].m_blocks[1] = (UINT32)0x85acef81; - m_power10BigNumTable[2].m_blocks[2] = (UINT32)0x2d6d415b; - m_power10BigNumTable[2].m_blocks[3] = (UINT32)0x000004ee; - - // 10^64 - m_power10BigNumTable[3].m_len = (UINT32)7; - m_power10BigNumTable[3].m_blocks[0] = (UINT32)0x00000000; - m_power10BigNumTable[3].m_blocks[1] = (UINT32)0x00000000; - m_power10BigNumTable[3].m_blocks[2] = (UINT32)0xbf6a1f01; - m_power10BigNumTable[3].m_blocks[3] = (UINT32)0x6e38ed64; - m_power10BigNumTable[3].m_blocks[4] = (UINT32)0xdaa797ed; - m_power10BigNumTable[3].m_blocks[5] = (UINT32)0xe93ff9f4; - m_power10BigNumTable[3].m_blocks[6] = (UINT32)0x00184f03; - - // 10^128 - m_power10BigNumTable[4].m_len = (UINT32)14; - m_power10BigNumTable[4].m_blocks[0] = (UINT32)0x00000000; - m_power10BigNumTable[4].m_blocks[1] = (UINT32)0x00000000; - m_power10BigNumTable[4].m_blocks[2] = (UINT32)0x00000000; - m_power10BigNumTable[4].m_blocks[3] = (UINT32)0x00000000; - m_power10BigNumTable[4].m_blocks[4] = (UINT32)0x2e953e01; - m_power10BigNumTable[4].m_blocks[5] = (UINT32)0x03df9909; - m_power10BigNumTable[4].m_blocks[6] = (UINT32)0x0f1538fd; - m_power10BigNumTable[4].m_blocks[7] = (UINT32)0x2374e42f; - m_power10BigNumTable[4].m_blocks[8] = (UINT32)0xd3cff5ec; - m_power10BigNumTable[4].m_blocks[9] = (UINT32)0xc404dc08; - m_power10BigNumTable[4].m_blocks[10] = (UINT32)0xbccdb0da; - m_power10BigNumTable[4].m_blocks[11] = (UINT32)0xa6337f19; - m_power10BigNumTable[4].m_blocks[12] = (UINT32)0xe91f2603; - m_power10BigNumTable[4].m_blocks[13] = (UINT32)0x0000024e; - - // 10^256 - m_power10BigNumTable[5].m_len = (UINT32)27; - m_power10BigNumTable[5].m_blocks[0] = (UINT32)0x00000000; - m_power10BigNumTable[5].m_blocks[1] = (UINT32)0x00000000; - m_power10BigNumTable[5].m_blocks[2] = (UINT32)0x00000000; - m_power10BigNumTable[5].m_blocks[3] = (UINT32)0x00000000; - m_power10BigNumTable[5].m_blocks[4] = (UINT32)0x00000000; - m_power10BigNumTable[5].m_blocks[5] = (UINT32)0x00000000; - m_power10BigNumTable[5].m_blocks[6] = (UINT32)0x00000000; - m_power10BigNumTable[5].m_blocks[7] = (UINT32)0x00000000; - m_power10BigNumTable[5].m_blocks[8] = (UINT32)0x982e7c01; - m_power10BigNumTable[5].m_blocks[9] = (UINT32)0xbed3875b; - m_power10BigNumTable[5].m_blocks[10] = (UINT32)0xd8d99f72; - m_power10BigNumTable[5].m_blocks[11] = (UINT32)0x12152f87; - m_power10BigNumTable[5].m_blocks[12] = (UINT32)0x6bde50c6; - m_power10BigNumTable[5].m_blocks[13] = (UINT32)0xcf4a6e70; - m_power10BigNumTable[5].m_blocks[14] = (UINT32)0xd595d80f; - m_power10BigNumTable[5].m_blocks[15] = (UINT32)0x26b2716e; - m_power10BigNumTable[5].m_blocks[16] = (UINT32)0xadc666b0; - m_power10BigNumTable[5].m_blocks[17] = (UINT32)0x1d153624; - m_power10BigNumTable[5].m_blocks[18] = (UINT32)0x3c42d35a; - m_power10BigNumTable[5].m_blocks[19] = (UINT32)0x63ff540e; - m_power10BigNumTable[5].m_blocks[20] = (UINT32)0xcc5573c0; - m_power10BigNumTable[5].m_blocks[21] = (UINT32)0x65f9ef17; - m_power10BigNumTable[5].m_blocks[22] = (UINT32)0x55bc28f2; - m_power10BigNumTable[5].m_blocks[23] = (UINT32)0x80dcc7f7; - m_power10BigNumTable[5].m_blocks[24] = (UINT32)0xf46eeddc; - m_power10BigNumTable[5].m_blocks[25] = (UINT32)0x5fdcefce; - m_power10BigNumTable[5].m_blocks[26] = (UINT32)0x000553f7; - } - } m_initializer; - - UINT32 m_blocks[BIGSIZE]; - UINT32 m_len; -}; - - -#endif diff --git a/src/classlibnative/bcltype/number.cpp b/src/classlibnative/bcltype/number.cpp index e8db5ab52a..849c742c55 100644 --- a/src/classlibnative/bcltype/number.cpp +++ b/src/classlibnative/bcltype/number.cpp @@ -9,7 +9,6 @@ #include "common.h" #include "number.h" -#include "bignum.h" #include "grisu3.h" #include "fp.h" @@ -18,303 +17,6 @@ typedef wchar_t wchar; #define SCALE_NAN 0x80000000 #define SCALE_INF 0x7FFFFFFF -void Dragon4( double value, int count, int* dec, int* sign, wchar_t* digits ) -{ - // ======================================================================================================================================== - // This implementation is based on the paper: https://www.cs.indiana.edu/~dyb/pubs/FP-Printing-PLDI96.pdf - // Besides the paper, some of the code and ideas are modified from http://www.ryanjuckett.com/programming/printing-floating-point-numbers/ - // You must read these two materials to fully understand the code. - // - // Note: we only support fixed format input. - // ======================================================================================================================================== - // - // Overview: - // - // The input double number can be represented as: - // value = f * 2^e = r / s. - // - // f: the output mantissa. Note: f is not the 52 bits mantissa of the input double number. - // e: biased exponent. - // r: numerator. - // s: denominator. - // k: value = d0.d1d2 . . . dn * 10^k - - // Step 1: - // Extract meta data from the input double value. - // - // Refer to IEEE double precision floating point format. - UINT64 f = 0; - int e = 0; - ExtractFractionAndBiasedExponent(value, &f, &e); - - UINT32 mantissaHighBitIdx = 0; - if (((FPDOUBLE*)&value)->exp != 0) - { - mantissaHighBitIdx = 52; - } - else - { - mantissaHighBitIdx = BigNum::LogBase2(f); - } - - // Step 2: - // Estimate k. We'll verify it and fix any error later. - // - // This is an improvement of the estimation in the original paper. - // Inspired by http://www.ryanjuckett.com/programming/printing-floating-point-numbers/ - // - // LOG10V2 = 0.30102999566398119521373889472449 - // DRIFT_FACTOR = 0.69 = 1 - log10V2 - epsilon (a small number account for drift of floating point multiplication) - int k = (int)(ceil(double((int)mantissaHighBitIdx + e) * LOG10V2 - DRIFT_FACTOR)); - - // Step 3: - // Store the input double value in BigNum format. - // - // To keep the precision, we represent the double value as r/s. - // We have several optimization based on following table in the paper. - // - // ---------------------------------------------------------------------------------------------------------- - // | e >= 0 | e < 0 | - // ---------------------------------------------------------------------------------------------------------- - // | f != b^(P - 1) | f = b^(P - 1) | e = min exp or f != b^(P - 1) | e > min exp and f = b^(P - 1) | - // -------------------------------------------------------------------------------------------------------------- - // | r | f * b^e * 2 | f * b^(e + 1) * 2 | f * 2 | f * b * 2 | - // -------------------------------------------------------------------------------------------------------------- - // | s | 2 | b * 2 | b^(-e) * 2 | b^(-e + 1) * 2 | - // -------------------------------------------------------------------------------------------------------------- - // - // Note, we do not need m+ and m- because we only support fixed format input here. - // m+ and m- are used for free format input, which need to determine the exact range of values - // that would round to value when input so that we can generate the shortest correct digits. - // - // In our case, we just output digits until reaching the expected precision. - BigNum r(f); - BigNum s; - if (e >= 0) - { - // When f != b^(P - 1): - // r = f * b^e * 2 - // s = 2 - // value = r / s = f * b^e * 2 / 2 = f * b^e / 1 - // - // When f = b^(P - 1): - // r = f * b^(e + 1) * 2 - // s = b * 2 - // value = r / s = f * b^(e + 1) * 2 / b * 2 = f * b^e / 1 - // - // Therefore, we can simply say that when e >= 0: - // r = f * b^e = f * 2^e - // s = 1 - - r.ShiftLeft(e); - s.SetUInt64(1); - } - else - { - // When e = min exp or f != b^(P - 1): - // r = f * 2 - // s = b^(-e) * 2 - // value = r / s = f * 2 / b^(-e) * 2 = f / b^(-e) - // - // When e > min exp and f = b^(P - 1): - // r = f * b * 2 - // s = b^(-e + 1) * 2 - // value = r / s = f * b * 2 / b^(-e + 1) * 2 = f / b^(-e) - // - // Therefore, we can simply say that when e < 0: - // r = f - // s = b^(-e) = 2^(-e) - - BigNum::ShiftLeft(1, -e, s); - } - - // According to the paper, we should use k >= 0 instead of k > 0 here. - // However, if k = 0, both r and s won't be changed, we don't need to do any operation. - // - // Following are the Scheme code from the paper: - // -------------------------------------------------------------------------------- - // (if (>= est 0) - // (fixup r (* s (exptt B est)) m+ m− est B low-ok? high-ok? ) - // (let ([scale (exptt B (− est))]) - // (fixup (* r scale) s (* m+ scale) (* m− scale) est B low-ok? high-ok? )))) - // -------------------------------------------------------------------------------- - // - // If est is 0, (* s (exptt B est)) = s, (* r scale) = (* r (exptt B (− est)))) = r. - // - // So we just skip when k = 0. - - if (k > 0) - { - BigNum poweredValue; - BigNum::Pow10(k, poweredValue); - s.Multiply(poweredValue); - } - else if (k < 0) - { - BigNum poweredValue; - BigNum::Pow10(-k, poweredValue); - r.Multiply(poweredValue); - } - - if (BigNum::Compare(r, s) >= 0) - { - // The estimation was incorrect. Fix the error by increasing 1. - k += 1; - } - else - { - r.Multiply10(); - } - - *dec = k - 1; - - // This the prerequisite of calling BigNum::HeuristicDivide(). - BigNum::PrepareHeuristicDivide(&r, &s); - - // Step 4: - // Calculate digits. - // - // Output digits until reaching the last but one precision or the numerator becomes zero. - int digitsNum = 0; - int currentDigit = 0; - while (true) - { - currentDigit = BigNum::HeuristicDivide(&r, s); - if (r.IsZero() || digitsNum + 1 == count) - { - break; - } - - digits[digitsNum] = L'0' + currentDigit; - ++digitsNum; - - r.Multiply10(); - } - - // Step 5: - // Set the last digit. - // - // We round to the closest digit by comparing value with 0.5: - // compare( value, 0.5 ) - // = compare( r / s, 0.5 ) - // = compare( r, 0.5 * s) - // = compare(2 * r, s) - // = compare(r << 1, s) - r.ShiftLeft(1); - int compareResult = BigNum::Compare(r, s); - bool isRoundDown = compareResult < 0; - - // We are in the middle, round towards the even digit (i.e. IEEE rouding rules) - if (compareResult == 0) - { - isRoundDown = (currentDigit & 1) == 0; - } - - if (isRoundDown) - { - digits[digitsNum] = L'0' + currentDigit; - ++digitsNum; - } - else - { - wchar_t* pCurDigit = digits + digitsNum; - - // Rounding up for 9 is special. - if (currentDigit == 9) - { - // find the first non-nine prior digit - while (true) - { - // If we are at the first digit - if (pCurDigit == digits) - { - // Output 1 at the next highest exponent - *pCurDigit = L'1'; - ++digitsNum; - *dec += 1; - break; - } - - --pCurDigit; - --digitsNum; - if (*pCurDigit != L'9') - { - // increment the digit - *pCurDigit += 1; - ++digitsNum; - break; - } - } - } - else - { - // It's simple if the digit is not 9. - *pCurDigit = L'0' + currentDigit + 1; - ++digitsNum; - } - } - - while (digitsNum < count) - { - digits[digitsNum] = L'0'; - ++digitsNum; - } - - digits[count] = 0; - - ++*dec; - *sign = ((FPDOUBLE*)&value)->sign; -} - -// Convert a double value to a NUMBER struct. -// -// 1. You should ensure the input value is not infinity or NaN. -// 2. For 0.0, number->digits will be set as an empty string. i.e the value of the first bucket is 0. -void DoubleToNumberWorker( double value, int count, int* dec, int* sign, wchar_t* digits ) -{ - _ASSERTE(dec != nullptr && sign != nullptr && digits != nullptr); - - // The caller of DoubleToNumberWorker should already checked the Infinity and NAN values. - _ASSERTE(((FPDOUBLE*)&value)->exp != 0x7ff); - - // Shortcut for zero. - if (value == 0.0) - { - *dec = 0; - *sign = _signbit(value); - - // Instead of zeroing digits, we just make it as an empty string due to performance reason. - *digits = 0; - - return; - } - - // Try Grisu3 first. - if (Grisu3::Run(value, count, dec, sign, digits)) - { - return; - } - - // Grisu3 failed, fall back to Dragon4. - Dragon4(value, count, dec, sign, digits); -} - -void DoubleToNumber(double value, int precision, NUMBER* number) -{ - WRAPPER_NO_CONTRACT - _ASSERTE(number != NULL); - - number->precision = precision; - if (((FPDOUBLE*)&value)->exp == 0x7FF) { - number->scale = (((FPDOUBLE*)&value)->mantLo || ((FPDOUBLE*)&value)->mantHi) ? SCALE_NAN: SCALE_INF; - number->sign = ((FPDOUBLE*)&value)->sign; - number->digits[0] = 0; - } - else { - DoubleToNumberWorker(value, precision, &number->scale, &number->sign, number->digits); - } -} - /*=========================================================== Portable NumberToDouble implementation -------------------------------------- @@ -733,14 +435,6 @@ done: if (number->sign) *(UINT64*)value |= I64(0x8000000000000000); } -FCIMPL3_VII(void, COMNumber::DoubleToNumberFC, double value, int precision, NUMBER* number) -{ - FCALL_CONTRACT; - - DoubleToNumber(value, precision, number); -} -FCIMPLEND - FCIMPL1(double, COMNumber::NumberToDoubleFC, NUMBER* number) { FCALL_CONTRACT; diff --git a/src/classlibnative/bcltype/number.h b/src/classlibnative/bcltype/number.h index 480e6ad6a0..2359deb9ad 100644 --- a/src/classlibnative/bcltype/number.h +++ b/src/classlibnative/bcltype/number.h @@ -39,7 +39,6 @@ struct NUMBER { class COMNumber { public: - static FCDECL3_VII(void, DoubleToNumberFC, double value, int precision, NUMBER* number); static FCDECL1(double, NumberToDoubleFC, NUMBER* number); }; diff --git a/src/vm/ecalllist.h b/src/vm/ecalllist.h index 7a6cb315cf..7983f7f5a2 100644 --- a/src/vm/ecalllist.h +++ b/src/vm/ecalllist.h @@ -740,7 +740,6 @@ FCFuncStart(gWaitHandleFuncs) FCFuncEnd() FCFuncStart(gNumberFuncs) - FCFuncElement("DoubleToNumber", COMNumber::DoubleToNumberFC) FCFuncElement("NumberToDouble", COMNumber::NumberToDoubleFC) FCFuncEnd() |