diff options
Diffstat (limited to 'src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs')
| -rw-r--r-- | src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs | 420 |
1 files changed, 420 insertions, 0 deletions
diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs new file mode 100644 index 000000000..02df69feb --- /dev/null +++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs @@ -0,0 +1,420 @@ +// 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. + +using System.Diagnostics; +using System.Runtime.CompilerServices; +using System.Numerics; + +#if !netstandard +using Internal.Runtime.CompilerServices; +#endif + +namespace System +{ + internal static partial class SpanHelpers // .Char + { + public static unsafe int SequenceCompareTo(ref char first, int firstLength, ref char second, int secondLength) + { + Debug.Assert(firstLength >= 0); + Debug.Assert(secondLength >= 0); + + int lengthDelta = firstLength - secondLength; + + if (Unsafe.AreSame(ref first, ref second)) + goto Equal; + + IntPtr minLength = (IntPtr)((firstLength < secondLength) ? firstLength : secondLength); + IntPtr i = (IntPtr)0; // Use IntPtr for arithmetic to avoid unnecessary 64->32->64 truncations + + if ((byte*)minLength >= (byte*)(sizeof(UIntPtr) / sizeof(char))) + { + if (Vector.IsHardwareAccelerated && (byte*)minLength >= (byte*)Vector<ushort>.Count) + { + IntPtr nLength = minLength - Vector<ushort>.Count; + do + { + if (Unsafe.ReadUnaligned<Vector<ushort>>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref first, i))) != + Unsafe.ReadUnaligned<Vector<ushort>>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref second, i)))) + { + break; + } + i += Vector<ushort>.Count; + } + while ((byte*)nLength >= (byte*)i); + } + + while ((byte*)minLength >= (byte*)(i + sizeof(UIntPtr) / sizeof(char))) + { + if (Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref first, i))) != + Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref second, i)))) + { + break; + } + i += sizeof(UIntPtr) / sizeof(char); + } + } + + if (sizeof(UIntPtr) > sizeof(int) && (byte*)minLength >= (byte*)(i + sizeof(int) / sizeof(char))) + { + if (Unsafe.ReadUnaligned<int>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref first, i))) == + Unsafe.ReadUnaligned<int>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref second, i)))) + { + i += sizeof(int) / sizeof(char); + } + } + + while ((byte*)i < (byte*)minLength) + { + int result = Unsafe.Add(ref first, i).CompareTo(Unsafe.Add(ref second, i)); + if (result != 0) + return result; + i += 1; + } + + Equal: + return lengthDelta; + } + + // Adapted from IndexOf(...) + public static unsafe bool Contains(ref char searchSpace, char value, int length) + { + Debug.Assert(length >= 0); + + fixed (char* pChars = &searchSpace) + { + char* pCh = pChars; + char* pEndCh = pCh + length; + + if (Vector.IsHardwareAccelerated && length >= Vector<ushort>.Count * 2) + { + // Figure out how many characters to read sequentially until we are vector aligned + // This is equivalent to: + // unaligned = ((int)pCh % Unsafe.SizeOf<Vector<ushort>>()) / elementsPerByte + // length = (Vector<ushort>.Count - unaligned) % Vector<ushort>.Count + const int elementsPerByte = sizeof(ushort) / sizeof(byte); + int unaligned = ((int)pCh & (Unsafe.SizeOf<Vector<ushort>>() - 1)) / elementsPerByte; + length = (Vector<ushort>.Count - unaligned) & (Vector<ushort>.Count - 1); + } + + SequentialScan: + while (length >= 4) + { + length -= 4; + + if (value == *pCh || + value == *(pCh + 1) || + value == *(pCh + 2) || + value == *(pCh + 3)) + { + goto Found; + } + + pCh += 4; + } + + while (length > 0) + { + length -= 1; + + if (value == *pCh) + goto Found; + + pCh += 1; + } + + // We get past SequentialScan only if IsHardwareAccelerated is true. However, we still have the redundant check to allow + // the JIT to see that the code is unreachable and eliminate it when the platform does not have hardware accelerated. + if (Vector.IsHardwareAccelerated && pCh < pEndCh) + { + // Get the highest multiple of Vector<ushort>.Count that is within the search space. + // That will be how many times we iterate in the loop below. + // This is equivalent to: length = Vector<ushort>.Count * ((int)(pEndCh - pCh) / Vector<ushort>.Count) + length = (int)((pEndCh - pCh) & ~(Vector<ushort>.Count - 1)); + + // Get comparison Vector + Vector<ushort> vComparison = new Vector<ushort>(value); + + while (length > 0) + { + // Using Unsafe.Read instead of ReadUnaligned since the search space is pinned and pCh is always vector aligned + Debug.Assert(((int)pCh & (Unsafe.SizeOf<Vector<ushort>>() - 1)) == 0); + Vector<ushort> vMatches = Vector.Equals(vComparison, Unsafe.Read<Vector<ushort>>(pCh)); + if (Vector<ushort>.Zero.Equals(vMatches)) + { + pCh += Vector<ushort>.Count; + length -= Vector<ushort>.Count; + continue; + } + + goto Found; + } + + if (pCh < pEndCh) + { + length = (int)(pEndCh - pCh); + goto SequentialScan; + } + } + + return false; + + Found: + return true; + } + } + + public static unsafe int IndexOf(ref char searchSpace, char value, int length) + { + Debug.Assert(length >= 0); + + fixed (char* pChars = &searchSpace) + { + char* pCh = pChars; + char* pEndCh = pCh + length; + + if (Vector.IsHardwareAccelerated && length >= Vector<ushort>.Count * 2) + { + // Figure out how many characters to read sequentially until we are vector aligned + // This is equivalent to: + // unaligned = ((int)pCh % Unsafe.SizeOf<Vector<ushort>>()) / elementsPerByte + // length = (Vector<ushort>.Count - unaligned) % Vector<ushort>.Count + const int elementsPerByte = sizeof(ushort) / sizeof(byte); + int unaligned = ((int)pCh & (Unsafe.SizeOf<Vector<ushort>>() - 1)) / elementsPerByte; + length = (Vector<ushort>.Count - unaligned) & (Vector<ushort>.Count - 1); + } + + SequentialScan: + while (length >= 4) + { + length -= 4; + + if (*pCh == value) + goto Found; + if (*(pCh + 1) == value) + goto Found1; + if (*(pCh + 2) == value) + goto Found2; + if (*(pCh + 3) == value) + goto Found3; + + pCh += 4; + } + + while (length > 0) + { + length -= 1; + + if (*pCh == value) + goto Found; + + pCh += 1; + } + + // We get past SequentialScan only if IsHardwareAccelerated is true. However, we still have the redundant check to allow + // the JIT to see that the code is unreachable and eliminate it when the platform does not have hardware accelerated. + if (Vector.IsHardwareAccelerated && pCh < pEndCh) + { + // Get the highest multiple of Vector<ushort>.Count that is within the search space. + // That will be how many times we iterate in the loop below. + // This is equivalent to: length = Vector<ushort>.Count * ((int)(pEndCh - pCh) / Vector<ushort>.Count) + length = (int)((pEndCh - pCh) & ~(Vector<ushort>.Count - 1)); + + // Get comparison Vector + Vector<ushort> vComparison = new Vector<ushort>(value); + + while (length > 0) + { + // Using Unsafe.Read instead of ReadUnaligned since the search space is pinned and pCh is always vector aligned + Debug.Assert(((int)pCh & (Unsafe.SizeOf<Vector<ushort>>() - 1)) == 0); + Vector<ushort> vMatches = Vector.Equals(vComparison, Unsafe.Read<Vector<ushort>>(pCh)); + if (Vector<ushort>.Zero.Equals(vMatches)) + { + pCh += Vector<ushort>.Count; + length -= Vector<ushort>.Count; + continue; + } + // Find offset of first match + return (int)(pCh - pChars) + LocateFirstFoundChar(vMatches); + } + + if (pCh < pEndCh) + { + length = (int)(pEndCh - pCh); + goto SequentialScan; + } + } + + return -1; + Found3: + pCh++; + Found2: + pCh++; + Found1: + pCh++; + Found: + return (int)(pCh - pChars); + } + } + + public static unsafe int LastIndexOf(ref char searchSpace, char value, int length) + { + Debug.Assert(length >= 0); + + fixed (char* pChars = &searchSpace) + { + char* pCh = pChars + length; + char* pEndCh = pChars; + + if (Vector.IsHardwareAccelerated && length >= Vector<ushort>.Count * 2) + { + // Figure out how many characters to read sequentially from the end until we are vector aligned + // This is equivalent to: length = ((int)pCh % Unsafe.SizeOf<Vector<ushort>>()) / elementsPerByte + const int elementsPerByte = sizeof(ushort) / sizeof(byte); + length = ((int)pCh & (Unsafe.SizeOf<Vector<ushort>>() - 1)) / elementsPerByte; + } + + SequentialScan: + while (length >= 4) + { + length -= 4; + pCh -= 4; + + if (*(pCh + 3) == value) + goto Found3; + if (*(pCh + 2) == value) + goto Found2; + if (*(pCh + 1) == value) + goto Found1; + if (*pCh == value) + goto Found; + } + + while (length > 0) + { + length -= 1; + pCh -= 1; + + if (*pCh == value) + goto Found; + } + + // We get past SequentialScan only if IsHardwareAccelerated is true. However, we still have the redundant check to allow + // the JIT to see that the code is unreachable and eliminate it when the platform does not have hardware accelerated. + if (Vector.IsHardwareAccelerated && pCh > pEndCh) + { + // Get the highest multiple of Vector<ushort>.Count that is within the search space. + // That will be how many times we iterate in the loop below. + // This is equivalent to: length = Vector<ushort>.Count * ((int)(pCh - pEndCh) / Vector<ushort>.Count) + length = (int)((pCh - pEndCh) & ~(Vector<ushort>.Count - 1)); + + // Get comparison Vector + Vector<ushort> vComparison = new Vector<ushort>(value); + + while (length > 0) + { + char* pStart = pCh - Vector<ushort>.Count; + // Using Unsafe.Read instead of ReadUnaligned since the search space is pinned and pCh (and hence pSart) is always vector aligned + Debug.Assert(((int)pStart & (Unsafe.SizeOf<Vector<ushort>>() - 1)) == 0); + Vector<ushort> vMatches = Vector.Equals(vComparison, Unsafe.Read<Vector<ushort>>(pStart)); + if (Vector<ushort>.Zero.Equals(vMatches)) + { + pCh -= Vector<ushort>.Count; + length -= Vector<ushort>.Count; + continue; + } + // Find offset of last match + return (int)(pStart - pEndCh) + LocateLastFoundChar(vMatches); + } + + if (pCh > pEndCh) + { + length = (int)(pCh - pEndCh); + goto SequentialScan; + } + } + + return -1; + Found: + return (int)(pCh - pEndCh); + Found1: + return (int)(pCh - pEndCh) + 1; + Found2: + return (int)(pCh - pEndCh) + 2; + Found3: + return (int)(pCh - pEndCh) + 3; + } + } + + // Vector sub-search adapted from https://github.com/aspnet/KestrelHttpServer/pull/1138 + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static int LocateFirstFoundChar(Vector<ushort> match) + { + var vector64 = Vector.AsVectorUInt64(match); + ulong candidate = 0; + int i = 0; + // Pattern unrolled by jit https://github.com/dotnet/coreclr/pull/8001 + for (; i < Vector<ulong>.Count; i++) + { + candidate = vector64[i]; + if (candidate != 0) + { + break; + } + } + + // Single LEA instruction with jitted const (using function result) + return i * 4 + LocateFirstFoundChar(candidate); + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static int LocateFirstFoundChar(ulong match) + { + unchecked + { + // Flag least significant power of two bit + var powerOfTwoFlag = match ^ (match - 1); + // Shift all powers of two into the high byte and extract + return (int)((powerOfTwoFlag * XorPowerOfTwoToHighChar) >> 49); + } + } + + private const ulong XorPowerOfTwoToHighChar = (0x03ul | + 0x02ul << 16 | + 0x01ul << 32) + 1; + + // Vector sub-search adapted from https://github.com/aspnet/KestrelHttpServer/pull/1138 + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static int LocateLastFoundChar(Vector<ushort> match) + { + var vector64 = Vector.AsVectorUInt64(match); + ulong candidate = 0; + int i = Vector<ulong>.Count - 1; + // Pattern unrolled by jit https://github.com/dotnet/coreclr/pull/8001 + for (; i >= 0; i--) + { + candidate = vector64[i]; + if (candidate != 0) + { + break; + } + } + + // Single LEA instruction with jitted const (using function result) + return i * 4 + LocateLastFoundChar(candidate); + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static int LocateLastFoundChar(ulong match) + { + // Find the most significant char that has its highest bit set + int index = 3; + while ((long)match > 0) + { + match = match << 16; + index--; + } + return index; + } + } +} |