From 95eb6a45d50a3b104b5c8c22ff053d076f034271 Mon Sep 17 00:00:00 2001 From: Grant Date: Tue, 26 Feb 2019 21:04:37 -0800 Subject: [PATCH] Make BitOperations public (CoreCLR) (#22864) * Make BitOps public * Update name to BitOperations * Change namespace to System.Numerics * Fix file name * Alphabetical --- .../shared/System.Private.CoreLib.Shared.projitems | 2 +- .../shared/System/Buffers/Binary/Reader.cs | 5 +- .../Buffers/Text/FormattingHelpers.CountDigits.cs | 3 +- .../shared/System/Buffers/Utilities.cs | 3 +- .../shared/System/Decimal.DecCalc.cs | 7 +- .../shared/System/Decimal.cs | 1 - .../System/Diagnostics/Tracing/EventSource.cs | 11 +- .../shared/System/HashCode.cs | 7 +- src/System.Private.CoreLib/shared/System/Marvin.cs | 9 +- .../shared/System/Number.BigInteger.cs | 7 +- .../shared/System/Number.DiyFp.cs | 3 +- .../shared/System/Number.Dragon4.cs | 7 +- .../{BitOps.cs => Numerics/BitOperations.cs} | 294 +++++++++++---------- .../shared/System/SpanHelpers.Byte.cs | 30 +-- .../shared/System/SpanHelpers.Char.cs | 4 +- .../shared/System/String.Comparison.cs | 7 +- 16 files changed, 211 insertions(+), 189 deletions(-) rename src/System.Private.CoreLib/shared/System/{BitOps.cs => Numerics/BitOperations.cs} (97%) diff --git a/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems b/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems index 97c1206..0389fb6 100644 --- a/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems +++ b/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems @@ -49,7 +49,6 @@ - @@ -370,6 +369,7 @@ + diff --git a/src/System.Private.CoreLib/shared/System/Buffers/Binary/Reader.cs b/src/System.Private.CoreLib/shared/System/Buffers/Binary/Reader.cs index b72d765..49d0a2d 100644 --- a/src/System.Private.CoreLib/shared/System/Buffers/Binary/Reader.cs +++ b/src/System.Private.CoreLib/shared/System/Buffers/Binary/Reader.cs @@ -2,6 +2,7 @@ // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. +using System.Numerics; using System.Runtime.CompilerServices; namespace System.Buffers.Binary @@ -105,8 +106,8 @@ namespace System.Buffers.Binary // Testing shows that throughput increases if the AND // is performed before the ROL / ROR. - return BitOps.RotateRight(value & 0x00FF00FFu, 8) // xx zz - + BitOps.RotateLeft(value & 0xFF00FF00u, 8); // ww yy + return BitOperations.RotateRight(value & 0x00FF00FFu, 8) // xx zz + + BitOperations.RotateLeft(value & 0xFF00FF00u, 8); // ww yy } /// diff --git a/src/System.Private.CoreLib/shared/System/Buffers/Text/FormattingHelpers.CountDigits.cs b/src/System.Private.CoreLib/shared/System/Buffers/Text/FormattingHelpers.CountDigits.cs index 16e737a..ac45347 100644 --- a/src/System.Private.CoreLib/shared/System/Buffers/Text/FormattingHelpers.CountDigits.cs +++ b/src/System.Private.CoreLib/shared/System/Buffers/Text/FormattingHelpers.CountDigits.cs @@ -3,6 +3,7 @@ // See the LICENSE file in the project root for more information. using System.Diagnostics; +using System.Numerics; using System.Runtime.CompilerServices; namespace System.Buffers.Text @@ -103,7 +104,7 @@ namespace System.Buffers.Text [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int CountHexDigits(ulong value) { - return (64 - BitOps.LeadingZeroCount(value | 1) + 3) >> 2; + return (64 - BitOperations.LeadingZeroCount(value | 1) + 3) >> 2; } // Counts the number of trailing '0' digits in a decimal number. diff --git a/src/System.Private.CoreLib/shared/System/Buffers/Utilities.cs b/src/System.Private.CoreLib/shared/System/Buffers/Utilities.cs index c9cc8f5..7e1caa0 100644 --- a/src/System.Private.CoreLib/shared/System/Buffers/Utilities.cs +++ b/src/System.Private.CoreLib/shared/System/Buffers/Utilities.cs @@ -3,6 +3,7 @@ // See the LICENSE file in the project root for more information. using System.Diagnostics; +using System.Numerics; using System.Runtime.CompilerServices; namespace System.Buffers @@ -14,7 +15,7 @@ namespace System.Buffers { Debug.Assert(bufferSize >= 0); uint bits = ((uint)bufferSize - 1) >> 4; - return 32 - BitOps.LeadingZeroCount(bits); + return 32 - BitOperations.LeadingZeroCount(bits); } [MethodImpl(MethodImplOptions.AggressiveInlining)] diff --git a/src/System.Private.CoreLib/shared/System/Decimal.DecCalc.cs b/src/System.Private.CoreLib/shared/System/Decimal.DecCalc.cs index a2bd04b..342aec9 100644 --- a/src/System.Private.CoreLib/shared/System/Decimal.DecCalc.cs +++ b/src/System.Private.CoreLib/shared/System/Decimal.DecCalc.cs @@ -3,6 +3,7 @@ // See the LICENSE file in the project root for more information. using System.Diagnostics; +using System.Numerics; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using Internal.Runtime.CompilerServices; @@ -547,7 +548,7 @@ PosRem: if (hiRes > 2) { newScale = (int)hiRes * 32 - 64 - 1; - newScale -= BitOps.LeadingZeroCount(result[hiRes]); + newScale -= BitOperations.LeadingZeroCount(result[hiRes]); // Multiply bit position by log10(2) to figure it's power of 10. // We scale the log by 256. log(2) = .30103, * 256 = 77. Doing this @@ -2019,7 +2020,7 @@ ReturnZero: if (tmp == 0) tmp = d2.Mid; - curScale = BitOps.LeadingZeroCount(tmp); + curScale = BitOperations.LeadingZeroCount(tmp); // Shift both dividend and divisor left by curScale. // @@ -2300,7 +2301,7 @@ ThrowOverflow: uint tmp = d2.High; if (tmp == 0) tmp = d2.Mid; - int shift = BitOps.LeadingZeroCount(tmp); + int shift = BitOperations.LeadingZeroCount(tmp); Buf28 b; _ = &b; // workaround for CS0165 diff --git a/src/System.Private.CoreLib/shared/System/Decimal.cs b/src/System.Private.CoreLib/shared/System/Decimal.cs index cfcb12d..eb8c4cd 100644 --- a/src/System.Private.CoreLib/shared/System/Decimal.cs +++ b/src/System.Private.CoreLib/shared/System/Decimal.cs @@ -881,7 +881,6 @@ namespace System return new decimal(value); } - public static explicit operator decimal(float value) { return new decimal(value); diff --git a/src/System.Private.CoreLib/shared/System/Diagnostics/Tracing/EventSource.cs b/src/System.Private.CoreLib/shared/System/Diagnostics/Tracing/EventSource.cs index 7909e8d..47cc8f7 100644 --- a/src/System.Private.CoreLib/shared/System/Diagnostics/Tracing/EventSource.cs +++ b/src/System.Private.CoreLib/shared/System/Diagnostics/Tracing/EventSource.cs @@ -171,6 +171,7 @@ using System.Collections.ObjectModel; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.Globalization; +using System.Numerics; using System.Reflection; using System.Resources; using System.Security; @@ -1580,7 +1581,7 @@ namespace System.Diagnostics.Tracing { for (int i = 16; i != 80; i++) { - this.w[i] = BitOps.RotateLeft((this.w[i - 3] ^ this.w[i - 8] ^ this.w[i - 14] ^ this.w[i - 16]), 1); + this.w[i] = BitOperations.RotateLeft((this.w[i - 3] ^ this.w[i - 8] ^ this.w[i - 14] ^ this.w[i - 16]), 1); } unchecked @@ -1595,28 +1596,28 @@ namespace System.Diagnostics.Tracing { const uint k = 0x5A827999; uint f = (b & c) | ((~b) & d); - uint temp = BitOps.RotateLeft(a, 5) + f + e + k + this.w[i]; e = d; d = c; c = BitOps.RotateLeft(b, 30); b = a; a = temp; + uint temp = BitOperations.RotateLeft(a, 5) + f + e + k + this.w[i]; e = d; d = c; c = BitOperations.RotateLeft(b, 30); b = a; a = temp; } for (int i = 20; i != 40; i++) { uint f = b ^ c ^ d; const uint k = 0x6ED9EBA1; - uint temp = BitOps.RotateLeft(a, 5) + f + e + k + this.w[i]; e = d; d = c; c = BitOps.RotateLeft(b, 30); b = a; a = temp; + uint temp = BitOperations.RotateLeft(a, 5) + f + e + k + this.w[i]; e = d; d = c; c = BitOperations.RotateLeft(b, 30); b = a; a = temp; } for (int i = 40; i != 60; i++) { uint f = (b & c) | (b & d) | (c & d); const uint k = 0x8F1BBCDC; - uint temp = BitOps.RotateLeft(a, 5) + f + e + k + this.w[i]; e = d; d = c; c = BitOps.RotateLeft(b, 30); b = a; a = temp; + uint temp = BitOperations.RotateLeft(a, 5) + f + e + k + this.w[i]; e = d; d = c; c = BitOperations.RotateLeft(b, 30); b = a; a = temp; } for (int i = 60; i != 80; i++) { uint f = b ^ c ^ d; const uint k = 0xCA62C1D6; - uint temp = BitOps.RotateLeft(a, 5) + f + e + k + this.w[i]; e = d; d = c; c = BitOps.RotateLeft(b, 30); b = a; a = temp; + uint temp = BitOperations.RotateLeft(a, 5) + f + e + k + this.w[i]; e = d; d = c; c = BitOperations.RotateLeft(b, 30); b = a; a = temp; } this.w[80] += a; diff --git a/src/System.Private.CoreLib/shared/System/HashCode.cs b/src/System.Private.CoreLib/shared/System/HashCode.cs index a534232..39a905b 100644 --- a/src/System.Private.CoreLib/shared/System/HashCode.cs +++ b/src/System.Private.CoreLib/shared/System/HashCode.cs @@ -43,6 +43,7 @@ https://raw.githubusercontent.com/Cyan4973/xxHash/5c174cfa4e45a42f94082dc0d4539b using System.Collections.Generic; using System.ComponentModel; +using System.Numerics; using System.Runtime.CompilerServices; namespace System @@ -264,19 +265,19 @@ namespace System [MethodImpl(MethodImplOptions.AggressiveInlining)] private static uint Round(uint hash, uint input) { - return BitOps.RotateLeft(hash + input * Prime2, 13) * Prime1; + return BitOperations.RotateLeft(hash + input * Prime2, 13) * Prime1; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static uint QueueRound(uint hash, uint queuedValue) { - return BitOps.RotateLeft(hash + queuedValue * Prime3, 17) * Prime4; + return BitOperations.RotateLeft(hash + queuedValue * Prime3, 17) * Prime4; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static uint MixState(uint v1, uint v2, uint v3, uint v4) { - return BitOps.RotateLeft(v1, 1) + BitOps.RotateLeft(v2, 7) + BitOps.RotateLeft(v3, 12) + BitOps.RotateLeft(v4, 18); + return BitOperations.RotateLeft(v1, 1) + BitOperations.RotateLeft(v2, 7) + BitOperations.RotateLeft(v3, 12) + BitOperations.RotateLeft(v4, 18); } private static uint MixEmptyState() diff --git a/src/System.Private.CoreLib/shared/System/Marvin.cs b/src/System.Private.CoreLib/shared/System/Marvin.cs index b9f6792..6cf2040 100644 --- a/src/System.Private.CoreLib/shared/System/Marvin.cs +++ b/src/System.Private.CoreLib/shared/System/Marvin.cs @@ -3,6 +3,7 @@ // See the LICENSE file in the project root for more information. using System.Diagnostics; +using System.Numerics; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using Internal.Runtime.CompilerServices; @@ -102,16 +103,16 @@ namespace System uint p1 = rp1; p1 ^= p0; - p0 = BitOps.RotateLeft(p0, 20); + p0 = BitOperations.RotateLeft(p0, 20); p0 += p1; - p1 = BitOps.RotateLeft(p1, 9); + p1 = BitOperations.RotateLeft(p1, 9); p1 ^= p0; - p0 = BitOps.RotateLeft(p0, 27); + p0 = BitOperations.RotateLeft(p0, 27); p0 += p1; - p1 = BitOps.RotateLeft(p1, 19); + p1 = BitOperations.RotateLeft(p1, 19); rp0 = p0; rp1 = p1; diff --git a/src/System.Private.CoreLib/shared/System/Number.BigInteger.cs b/src/System.Private.CoreLib/shared/System/Number.BigInteger.cs index 07c4112..06ae1e7 100644 --- a/src/System.Private.CoreLib/shared/System/Number.BigInteger.cs +++ b/src/System.Private.CoreLib/shared/System/Number.BigInteger.cs @@ -3,6 +3,7 @@ // See the LICENSE file in the project root for more information. using System.Diagnostics; +using System.Numerics; using System.Runtime.InteropServices; using Internal.Runtime.CompilerServices; @@ -455,12 +456,12 @@ namespace System public static uint CountSignificantBits(uint value) { - return 32 - (uint)BitOps.LeadingZeroCount(value); + return 32 - (uint)BitOperations.LeadingZeroCount(value); } public static uint CountSignificantBits(ulong value) { - return 64 - (uint)BitOps.LeadingZeroCount(value); + return 64 - (uint)BitOperations.LeadingZeroCount(value); } public static uint CountSignificantBits(ref BigInteger value) @@ -553,7 +554,7 @@ namespace System uint divLo = rhs._blocks[rhsLength - 2]; // We measure the leading zeros of the divisor - int shiftLeft = BitOps.LeadingZeroCount(divHi); + int shiftLeft = BitOperations.LeadingZeroCount(divHi); int shiftRight = 32 - shiftLeft; // And, we make sure the most significant bit is set diff --git a/src/System.Private.CoreLib/shared/System/Number.DiyFp.cs b/src/System.Private.CoreLib/shared/System/Number.DiyFp.cs index b8f2fdc..bb9fc09 100644 --- a/src/System.Private.CoreLib/shared/System/Number.DiyFp.cs +++ b/src/System.Private.CoreLib/shared/System/Number.DiyFp.cs @@ -3,6 +3,7 @@ // See the LICENSE file in the project root for more information. using System.Diagnostics; +using System.Numerics; namespace System { @@ -111,7 +112,7 @@ namespace System // and subtract once. Debug.Assert(f != 0); - int lzcnt = BitOps.LeadingZeroCount(f); + int lzcnt = BitOperations.LeadingZeroCount(f); return new DiyFp((f << lzcnt), (e - lzcnt)); } diff --git a/src/System.Private.CoreLib/shared/System/Number.Dragon4.cs b/src/System.Private.CoreLib/shared/System/Number.Dragon4.cs index 7682506..3070497 100644 --- a/src/System.Private.CoreLib/shared/System/Number.Dragon4.cs +++ b/src/System.Private.CoreLib/shared/System/Number.Dragon4.cs @@ -3,6 +3,7 @@ // See the LICENSE file in the project root for more information. using System.Diagnostics; +using System.Numerics; using Internal.Runtime.CompilerServices; namespace System @@ -31,7 +32,7 @@ namespace System else { Debug.Assert(mantissa != 0); - mantissaHighBitIdx = (uint)BitOps.Log2(mantissa); + mantissaHighBitIdx = (uint)BitOperations.Log2(mantissa); } int length = (int)(Dragon4(mantissa, exponent, mantissaHighBitIdx, hasUnequalMargins, cutoffNumber, isSignificantDigits, number.Digits, out int decimalExponent)); @@ -61,7 +62,7 @@ namespace System else { Debug.Assert(mantissa != 0); - mantissaHighBitIdx = (uint)BitOps.Log2(mantissa); + mantissaHighBitIdx = (uint)BitOperations.Log2(mantissa); } int length = (int)(Dragon4(mantissa, exponent, mantissaHighBitIdx, hasUnequalMargins, cutoffNumber, isSignificantDigits, number.Digits, out int decimalExponent)); @@ -292,7 +293,7 @@ namespace System // 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. Debug.Assert(hiBlock != 0); - uint hiBlockLog2 = (uint)BitOps.Log2(hiBlock); + uint hiBlockLog2 = (uint)BitOperations.Log2(hiBlock); Debug.Assert((hiBlockLog2 < 3) || (hiBlockLog2 > 27)); uint shift = (32 + 27 - hiBlockLog2) % 32; diff --git a/src/System.Private.CoreLib/shared/System/BitOps.cs b/src/System.Private.CoreLib/shared/System/Numerics/BitOperations.cs similarity index 97% rename from src/System.Private.CoreLib/shared/System/BitOps.cs rename to src/System.Private.CoreLib/shared/System/Numerics/BitOperations.cs index d85f3f5..06bfca0 100644 --- a/src/System.Private.CoreLib/shared/System/BitOps.cs +++ b/src/System.Private.CoreLib/shared/System/Numerics/BitOperations.cs @@ -11,14 +11,14 @@ using Internal.Runtime.CompilerServices; // Some routines inspired by the Stanford Bit Twiddling Hacks by Sean Eron Anderson: // http://graphics.stanford.edu/~seander/bithacks.html -namespace System +namespace System.Numerics { /// /// Utility methods for intrinsic bit-twiddling operations. /// The methods use hardware intrinsics when available on the underlying platform, /// otherwise they use optimized software fallbacks. /// - internal static class BitOps + public static class BitOperations { // C# no-alloc optimization that directly wraps the data section of the dll (similar to string constants) // https://github.com/dotnet/roslyn/pull/24621 @@ -40,81 +40,12 @@ namespace System }; /// - /// Count the number of trailing zero bits in an integer value. - /// Similar in behavior to the x86 instruction TZCNT. - /// - /// The value. - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static int TrailingZeroCount(int value) - => TrailingZeroCount((uint)value); - - /// - /// Count the number of trailing zero bits in an integer value. - /// Similar in behavior to the x86 instruction TZCNT. - /// - /// The value. - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static int TrailingZeroCount(uint value) - { - if (Bmi1.IsSupported) - { - // TZCNT contract is 0->32 - return (int)Bmi1.TrailingZeroCount(value); - } - - // Unguarded fallback contract is 0->0 - if (value == 0) - { - return 32; - } - - // uint.MaxValue >> 27 is always in range [0 - 31] so we use Unsafe.AddByteOffset to avoid bounds check - return Unsafe.AddByteOffset( - // Using deBruijn sequence, k=2, n=5 (2^5=32) : 0b_0000_0111_0111_1100_1011_0101_0011_0001u - ref MemoryMarshal.GetReference(s_TrailingZeroCountDeBruijn), - // uint|long -> IntPtr cast on 32-bit platforms does expensive overflow checks not needed here - (IntPtr)(int)(((value & (uint)-(int)value) * 0x077CB531u) >> 27)); // Multi-cast mitigates redundant conv.u8 - } - - /// - /// Count the number of trailing zero bits in a mask. - /// Similar in behavior to the x86 instruction TZCNT. - /// - /// The value. - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static int TrailingZeroCount(long value) - => TrailingZeroCount((ulong)value); - - /// - /// Count the number of trailing zero bits in a mask. - /// Similar in behavior to the x86 instruction TZCNT. - /// - /// The value. - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static int TrailingZeroCount(ulong value) - { - if (Bmi1.X64.IsSupported) - { - // TZCNT contract is 0->64 - return (int)Bmi1.X64.TrailingZeroCount(value); - } - - uint lo = (uint)value; - - if (lo == 0) - { - return 32 + TrailingZeroCount((uint)(value >> 32)); - } - - return TrailingZeroCount(lo); - } - - /// /// Count the number of leading zero bits in a mask. /// Similar in behavior to the x86 instruction LZCNT. /// /// The value. [MethodImpl(MethodImplOptions.AggressiveInlining)] + [CLSCompliant(false)] public static int LeadingZeroCount(uint value) { if (Lzcnt.IsSupported) @@ -138,6 +69,7 @@ namespace System /// /// The value. [MethodImpl(MethodImplOptions.AggressiveInlining)] + [CLSCompliant(false)] public static int LeadingZeroCount(ulong value) { if (Lzcnt.X64.IsSupported) @@ -162,6 +94,7 @@ namespace System /// /// The value. [MethodImpl(MethodImplOptions.AggressiveInlining)] + [CLSCompliant(false)] public static int Log2(uint value) { // value lzcnt actual expected @@ -190,35 +123,10 @@ namespace System /// /// Returns the integer (floor) log of the specified value, base 2. /// Note that by convention, input value 0 returns 0 since Log(0) is undefined. - /// Does not directly use any hardware intrinsics, nor does it incur branching. - /// - /// The value. - private static int Log2SoftwareFallback(uint value) - { - // No AggressiveInlining due to large method size - // Has conventional contract 0->0 (Log(0) is undefined) - - // Fill trailing zeros with ones, eg 00010010 becomes 00011111 - value |= value >> 01; - value |= value >> 02; - value |= value >> 04; - value |= value >> 08; - value |= value >> 16; - - // uint.MaxValue >> 27 is always in range [0 - 31] so we use Unsafe.AddByteOffset to avoid bounds check - return Unsafe.AddByteOffset( - // Using deBruijn sequence, k=2, n=5 (2^5=32) : 0b_0000_0111_1100_0100_1010_1100_1101_1101u - ref MemoryMarshal.GetReference(s_Log2DeBruijn), - // uint|long -> IntPtr cast on 32-bit platforms does expensive overflow checks not needed here - (IntPtr)(int)((value * 0x07C4ACDDu) >> 27)); - } - - /// - /// Returns the integer (floor) log of the specified value, base 2. - /// Note that by convention, input value 0 returns 0 since Log(0) is undefined. /// /// The value. [MethodImpl(MethodImplOptions.AggressiveInlining)] + [CLSCompliant(false)] public static int Log2(ulong value) { if (Lzcnt.X64.IsSupported) @@ -244,52 +152,30 @@ namespace System } /// - /// Rotates the specified value left by the specified number of bits. - /// Similar in behavior to the x86 instruction ROL. - /// - /// The value to rotate. - /// The number of bits to rotate by. - /// Any value outside the range [0..31] is treated as congruent mod 32. - /// The rotated value. - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static uint RotateLeft(uint value, int offset) - => (value << offset) | (value >> (32 - offset)); - - /// - /// Rotates the specified value left by the specified number of bits. - /// Similar in behavior to the x86 instruction ROL. + /// Returns the integer (floor) log of the specified value, base 2. + /// Note that by convention, input value 0 returns 0 since Log(0) is undefined. + /// Does not directly use any hardware intrinsics, nor does it incur branching. /// - /// The value to rotate. - /// The number of bits to rotate by. - /// Any value outside the range [0..63] is treated as congruent mod 64. - /// The rotated value. - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static ulong RotateLeft(ulong value, int offset) - => (value << offset) | (value >> (64 - offset)); + /// The value. + private static int Log2SoftwareFallback(uint value) + { + // No AggressiveInlining due to large method size + // Has conventional contract 0->0 (Log(0) is undefined) - /// - /// Rotates the specified value right by the specified number of bits. - /// Similar in behavior to the x86 instruction ROR. - /// - /// The value to rotate. - /// The number of bits to rotate by. - /// Any value outside the range [0..31] is treated as congruent mod 32. - /// The rotated value. - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static uint RotateRight(uint value, int offset) - => (value >> offset) | (value << (32 - offset)); + // Fill trailing zeros with ones, eg 00010010 becomes 00011111 + value |= value >> 01; + value |= value >> 02; + value |= value >> 04; + value |= value >> 08; + value |= value >> 16; - /// - /// Rotates the specified value right by the specified number of bits. - /// Similar in behavior to the x86 instruction ROR. - /// - /// The value to rotate. - /// The number of bits to rotate by. - /// Any value outside the range [0..63] is treated as congruent mod 64. - /// The rotated value. - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static ulong RotateRight(ulong value, int offset) - => (value >> offset) | (value << (64 - offset)); + // uint.MaxValue >> 27 is always in range [0 - 31] so we use Unsafe.AddByteOffset to avoid bounds check + return Unsafe.AddByteOffset( + // Using deBruijn sequence, k=2, n=5 (2^5=32) : 0b_0000_0111_1100_0100_1010_1100_1101_1101u + ref MemoryMarshal.GetReference(s_Log2DeBruijn), + // uint|long -> IntPtr cast on 32-bit platforms does expensive overflow checks not needed here + (IntPtr)(int)((value * 0x07C4ACDDu) >> 27)); + } /// /// Returns the population count (number of bits set) of a mask. @@ -297,6 +183,7 @@ namespace System /// /// The value. [MethodImpl(MethodImplOptions.AggressiveInlining)] + [CLSCompliant(false)] public static int PopCount(uint value) { if (Popcnt.IsSupported) @@ -327,6 +214,7 @@ namespace System /// /// The value. [MethodImpl(MethodImplOptions.AggressiveInlining)] + [CLSCompliant(false)] public static int PopCount(ulong value) { if (Popcnt.X64.IsSupported) @@ -355,5 +243,129 @@ namespace System } #endif } + + /// + /// Count the number of trailing zero bits in an integer value. + /// Similar in behavior to the x86 instruction TZCNT. + /// + /// The value. + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int TrailingZeroCount(int value) + => TrailingZeroCount((uint)value); + + /// + /// Count the number of trailing zero bits in an integer value. + /// Similar in behavior to the x86 instruction TZCNT. + /// + /// The value. + [CLSCompliant(false)] + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int TrailingZeroCount(uint value) + { + if (Bmi1.IsSupported) + { + // TZCNT contract is 0->32 + return (int)Bmi1.TrailingZeroCount(value); + } + + // Unguarded fallback contract is 0->0 + if (value == 0) + { + return 32; + } + + // uint.MaxValue >> 27 is always in range [0 - 31] so we use Unsafe.AddByteOffset to avoid bounds check + return Unsafe.AddByteOffset( + // Using deBruijn sequence, k=2, n=5 (2^5=32) : 0b_0000_0111_0111_1100_1011_0101_0011_0001u + ref MemoryMarshal.GetReference(s_TrailingZeroCountDeBruijn), + // uint|long -> IntPtr cast on 32-bit platforms does expensive overflow checks not needed here + (IntPtr)(int)(((value & (uint)-(int)value) * 0x077CB531u) >> 27)); // Multi-cast mitigates redundant conv.u8 + } + + /// + /// Count the number of trailing zero bits in a mask. + /// Similar in behavior to the x86 instruction TZCNT. + /// + /// The value. + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int TrailingZeroCount(long value) + => TrailingZeroCount((ulong)value); + + /// + /// Count the number of trailing zero bits in a mask. + /// Similar in behavior to the x86 instruction TZCNT. + /// + /// The value. + [MethodImpl(MethodImplOptions.AggressiveInlining)] + [CLSCompliant(false)] + public static int TrailingZeroCount(ulong value) + { + if (Bmi1.X64.IsSupported) + { + // TZCNT contract is 0->64 + return (int)Bmi1.X64.TrailingZeroCount(value); + } + + uint lo = (uint)value; + + if (lo == 0) + { + return 32 + TrailingZeroCount((uint)(value >> 32)); + } + + return TrailingZeroCount(lo); + } + + /// + /// Rotates the specified value left by the specified number of bits. + /// Similar in behavior to the x86 instruction ROL. + /// + /// The value to rotate. + /// The number of bits to rotate by. + /// Any value outside the range [0..31] is treated as congruent mod 32. + /// The rotated value. + [MethodImpl(MethodImplOptions.AggressiveInlining)] + [CLSCompliant(false)] + public static uint RotateLeft(uint value, int offset) + => (value << offset) | (value >> (32 - offset)); + + /// + /// Rotates the specified value left by the specified number of bits. + /// Similar in behavior to the x86 instruction ROL. + /// + /// The value to rotate. + /// The number of bits to rotate by. + /// Any value outside the range [0..63] is treated as congruent mod 64. + /// The rotated value. + [MethodImpl(MethodImplOptions.AggressiveInlining)] + [CLSCompliant(false)] + public static ulong RotateLeft(ulong value, int offset) + => (value << offset) | (value >> (64 - offset)); + + /// + /// Rotates the specified value right by the specified number of bits. + /// Similar in behavior to the x86 instruction ROR. + /// + /// The value to rotate. + /// The number of bits to rotate by. + /// Any value outside the range [0..31] is treated as congruent mod 32. + /// The rotated value. + [MethodImpl(MethodImplOptions.AggressiveInlining)] + [CLSCompliant(false)] + public static uint RotateRight(uint value, int offset) + => (value >> offset) | (value << (32 - offset)); + + /// + /// Rotates the specified value right by the specified number of bits. + /// Similar in behavior to the x86 instruction ROR. + /// + /// The value to rotate. + /// The number of bits to rotate by. + /// Any value outside the range [0..63] is treated as congruent mod 64. + /// The rotated value. + [MethodImpl(MethodImplOptions.AggressiveInlining)] + [CLSCompliant(false)] + public static ulong RotateRight(ulong value, int offset) + => (value >> offset) | (value << (64 - offset)); } } diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.Byte.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.Byte.cs index bac4ef4..4104d93 100644 --- a/src/System.Private.CoreLib/shared/System/SpanHelpers.Byte.cs +++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.Byte.cs @@ -3,8 +3,8 @@ // See the LICENSE file in the project root for more information. using System.Diagnostics; -using System.Runtime.CompilerServices; using System.Numerics; +using System.Runtime.CompilerServices; using System.Runtime.Intrinsics; using System.Runtime.Intrinsics.X86; @@ -292,7 +292,7 @@ namespace System else { // Find bitflag offset of first match and add to current offset - return ((int)(byte*)offset) + BitOps.TrailingZeroCount(matches); + return ((int)(byte*)offset) + BitOperations.TrailingZeroCount(matches); } } @@ -314,7 +314,7 @@ namespace System } // Find bitflag offset of first match and add to current offset - return ((int)(byte*)offset) + BitOps.TrailingZeroCount(matches); + return ((int)(byte*)offset) + BitOperations.TrailingZeroCount(matches); } while ((byte*)lengthToExamine > (byte*)offset); } @@ -334,7 +334,7 @@ namespace System else { // Find bitflag offset of first match and add to current offset - return ((int)(byte*)offset) + BitOps.TrailingZeroCount(matches); + return ((int)(byte*)offset) + BitOperations.TrailingZeroCount(matches); } } @@ -366,7 +366,7 @@ namespace System } // Find bitflag offset of first match and add to current offset - return ((int)(byte*)offset) + BitOps.TrailingZeroCount(matches); + return ((int)(byte*)offset) + BitOperations.TrailingZeroCount(matches); } if ((int)(byte*)offset < length) @@ -682,7 +682,7 @@ namespace System } // Find bitflag offset of first match and add to current offset - return ((int)(byte*)offset) + BitOps.TrailingZeroCount(matches); + return ((int)(byte*)offset) + BitOperations.TrailingZeroCount(matches); } while ((byte*)lengthToExamine > (byte*)offset); } @@ -706,7 +706,7 @@ namespace System else { // Find bitflag offset of first match and add to current offset - return ((int)(byte*)offset) + BitOps.TrailingZeroCount(matches); + return ((int)(byte*)offset) + BitOperations.TrailingZeroCount(matches); } } @@ -742,7 +742,7 @@ namespace System } // Find bitflag offset of first match and add to current offset - return ((int)(byte*)offset) + BitOps.TrailingZeroCount(matches); + return ((int)(byte*)offset) + BitOperations.TrailingZeroCount(matches); } if ((int)(byte*)offset < length) @@ -923,7 +923,7 @@ namespace System } // Find bitflag offset of first match and add to current offset - return ((int)(byte*)offset) + BitOps.TrailingZeroCount(matches); + return ((int)(byte*)offset) + BitOperations.TrailingZeroCount(matches); } while ((byte*)lengthToExamine > (byte*)offset); } @@ -949,7 +949,7 @@ namespace System else { // Find bitflag offset of first match and add to current offset - return ((int)(byte*)offset) + BitOps.TrailingZeroCount(matches); + return ((int)(byte*)offset) + BitOperations.TrailingZeroCount(matches); } } @@ -987,7 +987,7 @@ namespace System } // Find bitflag offset of first match and add to current offset - return ((int)(byte*)offset) + BitOps.TrailingZeroCount(matches); + return ((int)(byte*)offset) + BitOperations.TrailingZeroCount(matches); } if ((int)(byte*)offset < length) @@ -1429,7 +1429,7 @@ namespace System // Invert matches to find differences uint differences = ~matches; // Find bitflag offset of first difference and add to current offset - offset = (IntPtr)((int)(byte*)offset + BitOps.TrailingZeroCount((int)differences)); + offset = (IntPtr)((int)(byte*)offset + BitOperations.TrailingZeroCount((int)differences)); int result = Unsafe.AddByteOffset(ref first, offset).CompareTo(Unsafe.AddByteOffset(ref second, offset)); Debug.Assert(result != 0); @@ -1471,7 +1471,7 @@ namespace System // Invert matches to find differences uint differences = ~matches; // Find bitflag offset of first difference and add to current offset - offset = (IntPtr)((int)(byte*)offset + BitOps.TrailingZeroCount((int)differences)); + offset = (IntPtr)((int)(byte*)offset + BitOperations.TrailingZeroCount((int)differences)); int result = Unsafe.AddByteOffset(ref first, offset).CompareTo(Unsafe.AddByteOffset(ref second, offset)); Debug.Assert(result != 0); @@ -1514,7 +1514,7 @@ namespace System // Invert matches to find differences uint differences = ~matches; // Find bitflag offset of first difference and add to current offset - offset = (IntPtr)((int)(byte*)offset + BitOps.TrailingZeroCount((int)differences)); + offset = (IntPtr)((int)(byte*)offset + BitOperations.TrailingZeroCount((int)differences)); int result = Unsafe.AddByteOffset(ref first, offset).CompareTo(Unsafe.AddByteOffset(ref second, offset)); Debug.Assert(result != 0); @@ -1605,7 +1605,7 @@ namespace System [MethodImpl(MethodImplOptions.AggressiveInlining)] private static int LocateLastFoundByte(ulong match) { - return 7 - (BitOps.LeadingZeroCount(match) >> 3); + return 7 - (BitOperations.LeadingZeroCount(match) >> 3); } private const ulong XorPowerOfTwoToHighByte = (0x07ul | diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs index 6a2af73..9bf1c57 100644 --- a/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs +++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs @@ -3,8 +3,8 @@ // See the LICENSE file in the project root for more information. using System.Diagnostics; -using System.Runtime.CompilerServices; using System.Numerics; +using System.Runtime.CompilerServices; using System.Runtime.Intrinsics.X86; using Internal.Runtime.CompilerServices; @@ -874,7 +874,7 @@ namespace System [MethodImpl(MethodImplOptions.AggressiveInlining)] private static int LocateLastFoundChar(ulong match) { - return 3 - (BitOps.LeadingZeroCount(match) >> 4); + return 3 - (BitOperations.LeadingZeroCount(match) >> 4); } } } diff --git a/src/System.Private.CoreLib/shared/System/String.Comparison.cs b/src/System.Private.CoreLib/shared/System/String.Comparison.cs index 733319e..dde5cad 100644 --- a/src/System.Private.CoreLib/shared/System/String.Comparison.cs +++ b/src/System.Private.CoreLib/shared/System/String.Comparison.cs @@ -4,6 +4,7 @@ using System.Diagnostics; using System.Globalization; +using System.Numerics; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; @@ -820,15 +821,15 @@ namespace System { length -= 4; // Where length is 4n-1 (e.g. 3,7,11,15,19) this additionally consumes the null terminator - hash1 = (BitOps.RotateLeft(hash1, 5) + hash1) ^ ptr[0]; - hash2 = (BitOps.RotateLeft(hash2, 5) + hash2) ^ ptr[1]; + hash1 = (BitOperations.RotateLeft(hash1, 5) + hash1) ^ ptr[0]; + hash2 = (BitOperations.RotateLeft(hash2, 5) + hash2) ^ ptr[1]; ptr += 2; } if (length > 0) { // Where length is 4n-3 (e.g. 1,5,9,13,17) this additionally consumes the null terminator - hash2 = (BitOps.RotateLeft(hash2, 5) + hash2) ^ ptr[0]; + hash2 = (BitOperations.RotateLeft(hash2, 5) + hash2) ^ ptr[0]; } return (int)(hash1 + (hash2 * 1566083941)); -- 2.7.4