From 3ede95bd80e0f297c054c24e953e5d9acb24e9c3 Mon Sep 17 00:00:00 2001 From: Pent Ploompuu Date: Fri, 8 Jun 2018 03:47:44 +0300 Subject: [PATCH] Fixed and optimized Decimal.GetHashCode (dotnet/coreclr#18288) Commit migrated from https://github.com/dotnet/coreclr/commit/1b2040c880733c3d7735f9c9533e5a66fde8e13c --- .../src/System/Decimal.DecCalc.cs | 69 ++++++++++++++++++++++ .../System.Private.CoreLib/src/System/Decimal.cs | 3 +- src/coreclr/src/classlibnative/bcltype/decimal.cpp | 27 --------- src/coreclr/src/classlibnative/bcltype/decimal.h | 1 - src/coreclr/src/vm/ecalllist.h | 1 - 5 files changed, 70 insertions(+), 31 deletions(-) diff --git a/src/coreclr/src/System.Private.CoreLib/src/System/Decimal.DecCalc.cs b/src/coreclr/src/System.Private.CoreLib/src/System/Decimal.DecCalc.cs index 6d1a7a5..d18a52e 100644 --- a/src/coreclr/src/System.Private.CoreLib/src/System/Decimal.DecCalc.cs +++ b/src/coreclr/src/System.Private.CoreLib/src/System/Decimal.DecCalc.cs @@ -23,5 +23,74 @@ namespace System return (uint)(n % 1000000000); } } + + private static int GetHashCode(ref decimal d) + { + if ((d.Low | d.Mid | d.High) == 0) + return 0; + + uint flags = (uint)d.flags; + if ((flags & ScaleMask) == 0 || (d.Low & 1) != 0) + return (int)(flags ^ d.High ^ d.Mid ^ d.Low); + + int scale = (byte)(flags >> ScaleShift); + uint low = d.Low; + ulong high64 = ((ulong)d.High << 32) | d.Mid; + + Unscale(ref low, ref high64, ref scale); + + flags = ((flags) & ~(uint)ScaleMask) | (uint)scale << ScaleShift; + return (int)(flags ^ (uint)(high64 >> 32) ^ (uint)high64 ^ low); + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static bool Div96ByConst(ref ulong high64, ref uint low, uint pow) + { + ulong div64; +#if !BIT64 + if (high64 <= uint.MaxValue) + { + div64 = ((high64 << 32) | low) / pow; + if (low == (uint)div64 * pow) + { + low = (uint)div64; + high64 = div64 >> 32; + return true; + } + return false; + } +#endif + div64 = high64 / pow; + uint div = (uint)((((high64 - (uint)div64 * pow) << 32) | low) / pow); + if (low == div * pow) + { + high64 = div64; + low = div; + return true; + } + return false; + } + + // Normalize (unscale) the number by trying to divide out 10^8, 10^4, 10^2, and 10^1. + // If a division by one of these powers returns a zero remainder, then we keep the quotient. + // + // Since 10 = 2 * 5, there must be a factor of 2 for every power of 10 we can extract. + // We use this as a quick test on whether to try a given power. + // + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static void Unscale(ref uint low, ref ulong high64, ref int scale) + { + while ((byte)low == 0 && scale >= 8 && Div96ByConst(ref high64, ref low, 100000000)) + scale -= 8; + + if ((low & 0xF) == 0 && scale >= 4 && Div96ByConst(ref high64, ref low, 10000)) + scale -= 4; + + if ((low & 3) == 0 && scale >= 2 && Div96ByConst(ref high64, ref low, 100)) + scale -= 2; + + if ((low & 1) == 0 && scale >= 1 && Div96ByConst(ref high64, ref low, 10)) + scale--; + } } } diff --git a/src/coreclr/src/System.Private.CoreLib/src/System/Decimal.cs b/src/coreclr/src/System.Private.CoreLib/src/System/Decimal.cs index baab51c..18ea74a 100644 --- a/src/coreclr/src/System.Private.CoreLib/src/System/Decimal.cs +++ b/src/coreclr/src/System.Private.CoreLib/src/System/Decimal.cs @@ -453,8 +453,7 @@ namespace System // Returns the hash code for this Decimal. // - [MethodImplAttribute(MethodImplOptions.InternalCall)] - public extern override int GetHashCode(); + public override int GetHashCode() => GetHashCode(ref this); // Compares two Decimal values for equality. Returns true if the two // Decimal values are equal, or false if they are not equal. diff --git a/src/coreclr/src/classlibnative/bcltype/decimal.cpp b/src/coreclr/src/classlibnative/bcltype/decimal.cpp index c338e5d..729b19f3 100644 --- a/src/coreclr/src/classlibnative/bcltype/decimal.cpp +++ b/src/coreclr/src/classlibnative/bcltype/decimal.cpp @@ -99,33 +99,6 @@ FCIMPL1(void, COMDecimal::DoFloor, DECIMAL * d) } FCIMPLEND -FCIMPL1(INT32, COMDecimal::GetHashCode, DECIMAL *d) -{ - FCALL_CONTRACT; - - ENSURE_OLEAUT32_LOADED(); - - _ASSERTE(d != NULL); - double dbl; - VarR8FromDec(d, &dbl); - if (dbl == 0.0) { - // Ensure 0 and -0 have the same hash code - return 0; - } - // conversion to double is lossy and produces rounding errors so we mask off the lowest 4 bits - // - // For example these two numerically equal decimals with different internal representations produce - // slightly different results when converted to double: - // - // decimal a = new decimal(new int[] { 0x76969696, 0x2fdd49fa, 0x409783ff, 0x00160000 }); - // => (decimal)1999021.176470588235294117647000000000 => (double)1999021.176470588 - // decimal b = new decimal(new int[] { 0x3f0f0f0f, 0x1e62edcc, 0x06758d33, 0x00150000 }); - // => (decimal)1999021.176470588235294117647000000000 => (double)1999021.1764705882 - // - return ((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1]; -} -FCIMPLEND - FCIMPL3(void, COMDecimal::DoMultiply, DECIMAL * d1, DECIMAL * d2, CLR_BOOL * overflowed) { FCALL_CONTRACT; diff --git a/src/coreclr/src/classlibnative/bcltype/decimal.h b/src/coreclr/src/classlibnative/bcltype/decimal.h index b932420..f037fd3 100644 --- a/src/coreclr/src/classlibnative/bcltype/decimal.h +++ b/src/coreclr/src/classlibnative/bcltype/decimal.h @@ -23,7 +23,6 @@ public: static FCDECL2_IV(void, InitSingle, DECIMAL *_this, float value); static FCDECL2_IV(void, InitDouble, DECIMAL *_this, double value); static FCDECL2(INT32, DoCompare, DECIMAL * d1, DECIMAL * d2); - static FCDECL1(INT32, GetHashCode, DECIMAL *d); static FCDECL3(void, DoAddSubThrow, DECIMAL * d1, DECIMAL * d2, UINT8 bSign); static FCDECL2(void, DoDivideThrow, DECIMAL * d1, DECIMAL * d2); diff --git a/src/coreclr/src/vm/ecalllist.h b/src/coreclr/src/vm/ecalllist.h index 528780e..df69bef 100644 --- a/src/coreclr/src/vm/ecalllist.h +++ b/src/coreclr/src/vm/ecalllist.h @@ -768,7 +768,6 @@ FCFuncStart(gDecimalFuncs) FCFuncElement("FCallDivide", COMDecimal::DoDivideThrow) FCFuncElement("FCallCompare", COMDecimal::DoCompare) FCFuncElement("FCallFloor", COMDecimal::DoFloor) - FCFuncElement("GetHashCode", COMDecimal::GetHashCode) FCFuncElement("FCallRound", COMDecimal::DoRound) FCFuncElement("FCallToCurrency", COMDecimal::DoToCurrency) FCFuncElement("FCallToInt32", COMDecimal::ToInt32) -- 2.7.4