diff options
author | Ahson Khan <ahkha@microsoft.com> | 2018-02-27 21:41:47 +0300 |
---|---|---|
committer | Ahson Khan <ahkha@microsoft.com> | 2018-02-28 00:13:47 +0300 |
commit | 52f2faa6f1909456c771f71eab7bae35dd6a8745 (patch) | |
tree | 09c8d6091848dcbce36e7ebe3860dc5d75e6eccf | |
parent | d52d8d6fed87c894d18b33a1a058cc74fc76a2c5 (diff) |
Add MemoryExtensions to CoreLib along with necessary SpanHelpers (#16521)
* Add MemoryExtensions to CoreLib along with necessary SpanHelpers
* Make the newly added AsSpan/AsMemory into array extension methods.
* Remove StringSpanHelpers.Trim
* Leftover AsReadOnlySpan -> AsSpan for *Unix.cs files
* Address PR feedback.
* Remove duplicate methods in the Span class.
* Temporarily disable AsBytes SpanBench test.
* Add back AsBytes
* Re-enable AsBytes SpanBench test
Signed-off-by: dotnet-bot <dotnet-bot@microsoft.com>
11 files changed, 4103 insertions, 1046 deletions
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 4ecd5fe51..b86412112 100644 --- a/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems +++ b/src/System.Private.CoreLib/shared/System.Private.CoreLib.Shared.projitems @@ -241,6 +241,8 @@ <Compile Include="$(MSBuildThisFileDirectory)System\MemberAccessException.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\Memory.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\MemoryDebugView.cs" /> + <Compile Include="$(MSBuildThisFileDirectory)System\MemoryExtensions.cs" /> + <Compile Include="$(MSBuildThisFileDirectory)System\MemoryExtensions.Fast.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\MethodAccessException.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\MidpointRounding.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\MissingMethodException.cs" /> @@ -485,8 +487,12 @@ <Compile Include="$(MSBuildThisFileDirectory)System\Single.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\Span.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\Span.Fast.cs" /> - <Compile Include="$(MSBuildThisFileDirectory)System\SpanDebugView.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\Span.NonGeneric.cs" /> + <Compile Include="$(MSBuildThisFileDirectory)System\SpanDebugView.cs" /> + <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.cs" /> + <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.BinarySearch.cs" /> + <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.Byte.cs" /> + <Compile Include="$(MSBuildThisFileDirectory)System\SpanHelpers.T.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\String.Manipulation.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\String.Searching.cs" /> <Compile Include="$(MSBuildThisFileDirectory)System\StringSpanHelpers.cs" /> diff --git a/src/System.Private.CoreLib/shared/System/Double.cs b/src/System.Private.CoreLib/shared/System/Double.cs index 808f626da..146ee4600 100644 --- a/src/System.Private.CoreLib/shared/System/Double.cs +++ b/src/System.Private.CoreLib/shared/System/Double.cs @@ -345,7 +345,7 @@ namespace System bool success = Number.TryParseDouble(s, style, info, out result); if (!success) { - ReadOnlySpan<char> sTrim = StringSpanHelpers.Trim(s); + ReadOnlySpan<char> sTrim = s.Trim(); if (StringSpanHelpers.Equals(sTrim, info.PositiveInfinitySymbol)) { result = PositiveInfinity; diff --git a/src/System.Private.CoreLib/shared/System/MemoryExtensions.Fast.cs b/src/System.Private.CoreLib/shared/System/MemoryExtensions.Fast.cs new file mode 100644 index 000000000..4b330b7b1 --- /dev/null +++ b/src/System.Private.CoreLib/shared/System/MemoryExtensions.Fast.cs @@ -0,0 +1,540 @@ +// 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.Globalization; +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; + +using Internal.Runtime.CompilerServices; + +namespace System +{ + /// <summary> + /// Extension methods for Span{T}, Memory{T}, and friends. + /// </summary> + public static partial class MemoryExtensions + { + /// <summary> + /// Returns a value indicating whether the specified <paramref name="value"/> occurs within the <paramref name="span"/>. + /// <param name="span">The source span.</param> + /// <param name="value">The value to seek within the source span.</param> + /// <param name="comparisonType">One of the enumeration values that determines how the <paramref name="span"/> and <paramref name="value"/> are compared.</param> + /// </summary> + public static bool Contains(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) + { + return (IndexOf(span, value, comparisonType) >= 0); + } + + /// <summary> + /// Determines whether this <paramref name="span"/> and the specified <paramref name="value"/> span have the same characters + /// when compared using the specified <paramref name="comparisonType"/> option. + /// <param name="span">The source span.</param> + /// <param name="value">The value to compare with the source span.</param> + /// <param name="comparisonType">One of the enumeration values that determines how the <paramref name="span"/> and <paramref name="value"/> are compared.</param> + /// </summary> + public static bool Equals(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) + { + StringSpanHelpers.CheckStringComparison(comparisonType); + + switch (comparisonType) + { + case StringComparison.CurrentCulture: + return (CultureInfo.CurrentCulture.CompareInfo.Compare(span, value, CompareOptions.None) == 0); + + case StringComparison.CurrentCultureIgnoreCase: + return (CultureInfo.CurrentCulture.CompareInfo.Compare(span, value, CompareOptions.IgnoreCase) == 0); + + case StringComparison.InvariantCulture: + return (CompareInfo.Invariant.Compare(span, value, CompareOptions.None) == 0); + + case StringComparison.InvariantCultureIgnoreCase: + return (CompareInfo.Invariant.Compare(span, value, CompareOptions.IgnoreCase) == 0); + + case StringComparison.Ordinal: + if (span.Length != value.Length) + return false; + if (value.Length == 0) // span.Length == value.Length == 0 + return true; + return span.SequenceEqual(value); //TODO: Optimize - https://github.com/dotnet/corefx/issues/27487 + + case StringComparison.OrdinalIgnoreCase: + if (span.Length != value.Length) + return false; + if (value.Length == 0) // span.Length == value.Length == 0 + return true; + return (CompareInfo.CompareOrdinalIgnoreCase(span, value) == 0); + } + + Debug.Fail("StringComparison outside range"); + return false; + } + + /// <summary> + /// Compares the specified <paramref name="span"/> and <paramref name="value"/> using the specified <paramref name="comparisonType"/>, + /// and returns an integer that indicates their relative position in the sort order. + /// <param name="span">The source span.</param> + /// <param name="value">The value to compare with the source span.</param> + /// <param name="comparisonType">One of the enumeration values that determines how the <paramref name="span"/> and <paramref name="value"/> are compared.</param> + /// </summary> + public static int CompareTo(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) + { + StringSpanHelpers.CheckStringComparison(comparisonType); + + switch (comparisonType) + { + case StringComparison.CurrentCulture: + return CultureInfo.CurrentCulture.CompareInfo.Compare(span, value, CompareOptions.None); + + case StringComparison.CurrentCultureIgnoreCase: + return CultureInfo.CurrentCulture.CompareInfo.Compare(span, value, CompareOptions.IgnoreCase); + + case StringComparison.InvariantCulture: + return CompareInfo.Invariant.Compare(span, value, CompareOptions.None); + + case StringComparison.InvariantCultureIgnoreCase: + return CompareInfo.Invariant.Compare(span, value, CompareOptions.IgnoreCase); + + case StringComparison.Ordinal: + if (span.Length == 0 || value.Length == 0) + return span.Length - value.Length; + return string.CompareOrdinal(span, value); + + case StringComparison.OrdinalIgnoreCase: + return CompareInfo.CompareOrdinalIgnoreCase(span, value); + } + + Debug.Fail("StringComparison outside range"); + return 0; + } + + /// <summary> + /// Reports the zero-based index of the first occurrence of the specified <paramref name="value"/> in the current <paramref name="span"/>. + /// <param name="span">The source span.</param> + /// <param name="value">The value to seek within the source span.</param> + /// <param name="comparisonType">One of the enumeration values that determines how the <paramref name="span"/> and <paramref name="value"/> are compared.</param> + /// </summary> + public static int IndexOf(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) + { + StringSpanHelpers.CheckStringComparison(comparisonType); + + if (value.Length == 0) + { + return 0; + } + + if (span.Length == 0) + { + return -1; + } + + switch (comparisonType) + { + case StringComparison.CurrentCulture: + return SpanHelpers.IndexOfCultureHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); + + case StringComparison.CurrentCultureIgnoreCase: + return SpanHelpers.IndexOfCultureIgnoreCaseHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); + + case StringComparison.InvariantCulture: + return SpanHelpers.IndexOfCultureHelper(span, value, CompareInfo.Invariant); + + case StringComparison.InvariantCultureIgnoreCase: + return SpanHelpers.IndexOfCultureIgnoreCaseHelper(span, value, CompareInfo.Invariant); + + case StringComparison.Ordinal: + return SpanHelpers.IndexOfOrdinalHelper(span, value, ignoreCase: false); + + case StringComparison.OrdinalIgnoreCase: + return SpanHelpers.IndexOfOrdinalHelper(span, value, ignoreCase: true); + } + + Debug.Fail("StringComparison outside range"); + return -1; + } + + /// <summary> + /// Copies the characters from the source span into the destination, converting each character to lowercase, + /// using the casing rules of the specified culture. + /// </summary> + /// <param name="source">The source span.</param> + /// <param name="destination">The destination span which contains the transformed characters.</param> + /// <param name="culture">An object that supplies culture-specific casing rules.</param> + /// <remarks>If the source and destinations overlap, this method behaves as if the original values are in + /// a temporary location before the destination is overwritten.</remarks> + /// <exception cref="System.ArgumentNullException"> + /// Thrown when <paramref name="culture"/> is null. + /// </exception> + public static int ToLower(this ReadOnlySpan<char> source, Span<char> destination, CultureInfo culture) + { + if (culture == null) + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.culture); + + // Assuming that changing case does not affect length + if (destination.Length < source.Length) + return -1; + + if (GlobalizationMode.Invariant) + culture.TextInfo.ToLowerAsciiInvariant(source, destination); + else + culture.TextInfo.ChangeCase(source, destination, toUpper: false); + return source.Length; + } + + /// <summary> + /// Copies the characters from the source span into the destination, converting each character to lowercase, + /// using the casing rules of the invariant culture. + /// </summary> + /// <param name="source">The source span.</param> + /// <param name="destination">The destination span which contains the transformed characters.</param> + /// <remarks>If the source and destinations overlap, this method behaves as if the original values are in + /// a temporary location before the destination is overwritten.</remarks> + public static int ToLowerInvariant(this ReadOnlySpan<char> source, Span<char> destination) + { + // Assuming that changing case does not affect length + if (destination.Length < source.Length) + return -1; + + if (GlobalizationMode.Invariant) + CultureInfo.InvariantCulture.TextInfo.ToLowerAsciiInvariant(source, destination); + else + CultureInfo.InvariantCulture.TextInfo.ChangeCase(source, destination, toUpper: false); + return source.Length; + } + + /// <summary> + /// Copies the characters from the source span into the destination, converting each character to uppercase, + /// using the casing rules of the specified culture. + /// </summary> + /// <param name="source">The source span.</param> + /// <param name="destination">The destination span which contains the transformed characters.</param> + /// <param name="culture">An object that supplies culture-specific casing rules.</param> + /// <remarks>If the source and destinations overlap, this method behaves as if the original values are in + /// a temporary location before the destination is overwritten.</remarks> + /// <exception cref="System.ArgumentNullException"> + /// Thrown when <paramref name="culture"/> is null. + /// </exception> + public static int ToUpper(this ReadOnlySpan<char> source, Span<char> destination, CultureInfo culture) + { + if (culture == null) + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.culture); + + // Assuming that changing case does not affect length + if (destination.Length < source.Length) + return -1; + + if (GlobalizationMode.Invariant) + culture.TextInfo.ToUpperAsciiInvariant(source, destination); + else + culture.TextInfo.ChangeCase(source, destination, toUpper: true); + return source.Length; + } + + /// <summary> + /// Copies the characters from the source span into the destination, converting each character to uppercase + /// using the casing rules of the invariant culture. + /// </summary> + /// <param name="source">The source span.</param> + /// <param name="destination">The destination span which contains the transformed characters.</param> + /// <remarks>If the source and destinations overlap, this method behaves as if the original values are in + /// a temporary location before the destination is overwritten.</remarks> + public static int ToUpperInvariant(this ReadOnlySpan<char> source, Span<char> destination) + { + // Assuming that changing case does not affect length + if (destination.Length < source.Length) + return -1; + + if (GlobalizationMode.Invariant) + CultureInfo.InvariantCulture.TextInfo.ToUpperAsciiInvariant(source, destination); + else + CultureInfo.InvariantCulture.TextInfo.ChangeCase(source, destination, toUpper: true); + return source.Length; + } + + /// <summary> + /// Determines whether the end of the <paramref name="span"/> matches the specified <paramref name="value"/> when compared using the specified <paramref name="comparisonType"/> option. + /// </summary> + /// <param name="span">The source span.</param> + /// <param name="value">The sequence to compare to the end of the source span.</param> + /// <param name="comparisonType">One of the enumeration values that determines how the <paramref name="span"/> and <paramref name="value"/> are compared.</param> + public static bool EndsWith(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) + { + if (value.Length == 0) + { + StringSpanHelpers.CheckStringComparison(comparisonType); + return true; + } + + switch (comparisonType) + { + case StringComparison.CurrentCulture: + return SpanHelpers.EndsWithCultureHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); + + case StringComparison.CurrentCultureIgnoreCase: + return SpanHelpers.EndsWithCultureIgnoreCaseHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); + + case StringComparison.InvariantCulture: + return SpanHelpers.EndsWithCultureHelper(span, value, CompareInfo.Invariant); + + case StringComparison.InvariantCultureIgnoreCase: + return SpanHelpers.EndsWithCultureIgnoreCaseHelper(span, value, CompareInfo.Invariant); + + case StringComparison.Ordinal: + return span.EndsWith(value); //TODO: Optimize - https://github.com/dotnet/corefx/issues/27487 + + case StringComparison.OrdinalIgnoreCase: + return SpanHelpers.EndsWithOrdinalIgnoreCaseHelper(span, value); + + default: + throw new ArgumentException(SR.NotSupported_StringComparison, nameof(comparisonType)); + } + } + + /// <summary> + /// Determines whether the beginning of the <paramref name="span"/> matches the specified <paramref name="value"/> when compared using the specified <paramref name="comparisonType"/> option. + /// </summary> + /// <param name="span">The source span.</param> + /// <param name="value">The sequence to compare to the beginning of the source span.</param> + /// <param name="comparisonType">One of the enumeration values that determines how the <paramref name="span"/> and <paramref name="value"/> are compared.</param> + public static bool StartsWith(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) + { + if (value.Length == 0) + { + StringSpanHelpers.CheckStringComparison(comparisonType); + return true; + } + + switch (comparisonType) + { + case StringComparison.CurrentCulture: + return SpanHelpers.StartsWithCultureHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); + + case StringComparison.CurrentCultureIgnoreCase: + return SpanHelpers.StartsWithCultureIgnoreCaseHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); + + case StringComparison.InvariantCulture: + return SpanHelpers.StartsWithCultureHelper(span, value, CompareInfo.Invariant); + + case StringComparison.InvariantCultureIgnoreCase: + return SpanHelpers.StartsWithCultureIgnoreCaseHelper(span, value, CompareInfo.Invariant); + + case StringComparison.Ordinal: + return span.StartsWith(value); //TODO: Optimize - https://github.com/dotnet/corefx/issues/27487 + + case StringComparison.OrdinalIgnoreCase: + return SpanHelpers.StartsWithOrdinalIgnoreCaseHelper(span, value); + + default: + throw new ArgumentException(SR.NotSupported_StringComparison, nameof(comparisonType)); + } + } + + /// <summary> + /// Casts a Span of one primitive type <typeparamref name="T"/> to Span of bytes. + /// That type may not contain pointers or references. This is checked at runtime in order to preserve type safety. + /// </summary> + /// <param name="source">The source slice, of type <typeparamref name="T"/>.</param> + /// <exception cref="System.ArgumentException"> + /// Thrown when <typeparamref name="T"/> contains pointers. + /// </exception> + /// <exception cref="System.OverflowException"> + /// Thrown if the Length property of the new Span would exceed Int32.MaxValue. + /// </exception> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static Span<byte> AsBytes<T>(this Span<T> source) + where T : struct + { + if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) + ThrowHelper.ThrowInvalidTypeWithPointersNotSupported(typeof(T)); + + return new Span<byte>( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(source)), + checked(source.Length * Unsafe.SizeOf<T>())); + } + + /// <summary> + /// Casts a ReadOnlySpan of one primitive type <typeparamref name="T"/> to ReadOnlySpan of bytes. + /// That type may not contain pointers or references. This is checked at runtime in order to preserve type safety. + /// </summary> + /// <param name="source">The source slice, of type <typeparamref name="T"/>.</param> + /// <exception cref="System.ArgumentException"> + /// Thrown when <typeparamref name="T"/> contains pointers. + /// </exception> + /// <exception cref="System.OverflowException"> + /// Thrown if the Length property of the new Span would exceed Int32.MaxValue. + /// </exception> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static ReadOnlySpan<byte> AsBytes<T>(this ReadOnlySpan<T> source) + where T : struct + { + if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) + ThrowHelper.ThrowInvalidTypeWithPointersNotSupported(typeof(T)); + + return new ReadOnlySpan<byte>( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(source)), + checked(source.Length * Unsafe.SizeOf<T>())); + } + + /// <summary> + /// Creates a new span over the portion of the target array. + /// </summary> + public static Span<T> AsSpan<T>(this T[] array, int start) + { + if (array == null) + { + if (start != 0) + ThrowHelper.ThrowArgumentOutOfRangeException(); + return default; + } + if (default(T) == null && array.GetType() != typeof(T[])) + ThrowHelper.ThrowArrayTypeMismatchException(); + if ((uint)start > (uint)array.Length) + ThrowHelper.ThrowArgumentOutOfRangeException(); + + return new Span<T>(ref Unsafe.Add(ref Unsafe.As<byte, T>(ref array.GetRawSzArrayData()), start), array.Length - start); + } + + /// <summary> + /// Creates a new readonly span over the portion of the target string. + /// </summary> + /// <param name="text">The target string.</param> + /// <remarks>Returns default when <paramref name="text"/> is null.</remarks> + public static ReadOnlySpan<char> AsSpan(this string text) + { + if (text == null) + return default; + + return new ReadOnlySpan<char>(ref text.GetRawStringData(), text.Length); + } + + /// <summary> + /// Creates a new readonly span over the portion of the target string. + /// </summary> + /// <param name="text">The target string.</param> + /// <param name="start">The index at which to begin this slice.</param> + /// <exception cref="System.ArgumentNullException">Thrown when <paramref name="text"/> is null.</exception> + /// <exception cref="System.ArgumentOutOfRangeException"> + /// Thrown when the specified <paramref name="start"/> index is not in range (<0 or >text.Length). + /// </exception> + public static ReadOnlySpan<char> AsSpan(this string text, int start) + { + if (text == null) + { + if (start != 0) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); + return default; + } + + if ((uint)start > (uint)text.Length) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); + + return new ReadOnlySpan<char>(ref Unsafe.Add(ref text.GetRawStringData(), start), text.Length - start); + } + + /// <summary> + /// Creates a new readonly span over the portion of the target string. + /// </summary> + /// <param name="text">The target string.</param> + /// <param name="start">The index at which to begin this slice.</param> + /// <param name="length">The desired length for the slice (exclusive).</param> + /// <remarks>Returns default when <paramref name="text"/> is null.</remarks> + /// <exception cref="System.ArgumentOutOfRangeException"> + /// Thrown when the specified <paramref name="start"/> index or <paramref name="length"/> is not in range. + /// </exception> + public static ReadOnlySpan<char> AsSpan(this string text, int start, int length) + { + if (text == null) + { + if (start != 0 || length != 0) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); + return default; + } + + if ((uint)start > (uint)text.Length || (uint)length > (uint)(text.Length - start)) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); + + return new ReadOnlySpan<char>(ref Unsafe.Add(ref text.GetRawStringData(), start), length); + } + + /// <summary>Creates a new <see cref="ReadOnlyMemory{T}"/> over the portion of the target string.</summary> + /// <param name="text">The target string.</param> + /// <remarks>Returns default when <paramref name="text"/> is null.</remarks> + public static ReadOnlyMemory<char> AsMemory(this string text) + { + if (text == null) + return default; + + return new ReadOnlyMemory<char>(text, 0, text.Length); + } + + /// <summary>Creates a new <see cref="ReadOnlyMemory{T}"/> over the portion of the target string.</summary> + /// <param name="text">The target string.</param> + /// <param name="start">The index at which to begin this slice.</param> + /// <remarks>Returns default when <paramref name="text"/> is null.</remarks> + /// <exception cref="System.ArgumentOutOfRangeException"> + /// Thrown when the specified <paramref name="start"/> index is not in range (<0 or >text.Length). + /// </exception> + public static ReadOnlyMemory<char> AsMemory(this string text, int start) + { + if (text == null) + { + if (start != 0) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); + return default; + } + + if ((uint)start > (uint)text.Length) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); + + return new ReadOnlyMemory<char>(text, start, text.Length - start); + } + + /// <summary>Creates a new <see cref="ReadOnlyMemory{T}"/> over the portion of the target string.</summary> + /// <param name="text">The target string.</param> + /// <param name="start">The index at which to begin this slice.</param> + /// <param name="length">The desired length for the slice (exclusive).</param> + /// <remarks>Returns default when <paramref name="text"/> is null.</remarks> + /// <exception cref="System.ArgumentOutOfRangeException"> + /// Thrown when the specified <paramref name="start"/> index or <paramref name="length"/> is not in range. + /// </exception> + public static ReadOnlyMemory<char> AsMemory(this string text, int start, int length) + { + if (text == null) + { + if (start != 0 || length != 0) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); + return default; + } + + if ((uint)start > (uint)text.Length || (uint)length > (uint)(text.Length - start)) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); + + return new ReadOnlyMemory<char>(text, start, length); + } + + /// <summary>Attempts to get the underlying <see cref="string"/> from a <see cref="ReadOnlyMemory{T}"/>.</summary> + /// <param name="readOnlyMemory">The memory that may be wrapping a <see cref="string"/> object.</param> + /// <param name="text">The string.</param> + /// <param name="start">The starting location in <paramref name="text"/>.</param> + /// <param name="length">The number of items in <paramref name="text"/>.</param> + /// <returns></returns> + public static bool TryGetString(this ReadOnlyMemory<char> readOnlyMemory, out string text, out int start, out int length) + { + if (readOnlyMemory.GetObjectStartLength(out int offset, out int count) is string s) + { + text = s; + start = offset; + length = count; + return true; + } + else + { + text = null; + start = 0; + length = 0; + return false; + } + } + } +} diff --git a/src/System.Private.CoreLib/shared/System/MemoryExtensions.cs b/src/System.Private.CoreLib/shared/System/MemoryExtensions.cs new file mode 100644 index 000000000..effdecf92 --- /dev/null +++ b/src/System.Private.CoreLib/shared/System/MemoryExtensions.cs @@ -0,0 +1,1170 @@ +// 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.Collections.Generic; +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; + +#if !netstandard +using Internal.Runtime.CompilerServices; +#endif + +namespace System +{ + /// <summary> + /// Extension methods for Span{T}, Memory{T}, and friends. + /// </summary> + public static partial class MemoryExtensions + { + /// <summary> + /// Removes all leading and trailing white-space characters from the span. + /// </summary> + public static ReadOnlySpan<char> Trim(this ReadOnlySpan<char> span) + { + return span.TrimStart().TrimEnd(); + } + + /// <summary> + /// Removes all leading white-space characters from the span. + /// </summary> + public static ReadOnlySpan<char> TrimStart(this ReadOnlySpan<char> span) + { + int start = 0; + for (; start < span.Length; start++) + { + if (!char.IsWhiteSpace(span[start])) + break; + } + return span.Slice(start); + } + + /// <summary> + /// Removes all trailing white-space characters from the span. + /// </summary> + public static ReadOnlySpan<char> TrimEnd(this ReadOnlySpan<char> span) + { + int end = span.Length - 1; + for (; end >= 0; end--) + { + if (!char.IsWhiteSpace(span[end])) + break; + } + return span.Slice(0, end + 1); + } + + /// <summary> + /// Removes all leading and trailing occurrences of a specified character. + /// </summary> + /// <param name="span">The source span from which the character is removed.</param> + /// <param name="trimChar">The specified character to look for and remove.</param> + //[MethodImpl(MethodImplOptions.AggressiveInlining)] + public static ReadOnlySpan<char> Trim(this ReadOnlySpan<char> span, char trimChar) + { + return span.TrimStart(trimChar).TrimEnd(trimChar); + } + + /// <summary> + /// Removes all leading occurrences of a specified character. + /// </summary> + /// <param name="span">The source span from which the character is removed.</param> + /// <param name="trimChar">The specified character to look for and remove.</param> + //[MethodImpl(MethodImplOptions.AggressiveInlining)] + public static ReadOnlySpan<char> TrimStart(this ReadOnlySpan<char> span, char trimChar) + { + int start = 0; + for (; start < span.Length; start++) + { + if (span[start] != trimChar) + break; + } + return span.Slice(start); + } + + /// <summary> + /// Removes all trailing occurrences of a specified character. + /// </summary> + /// <param name="span">The source span from which the character is removed.</param> + /// <param name="trimChar">The specified character to look for and remove.</param> + public static ReadOnlySpan<char> TrimEnd(this ReadOnlySpan<char> span, char trimChar) + { + int end = span.Length - 1; + for (; end >= 0; end--) + { + if (span[end] != trimChar) + break; + } + return span.Slice(0, end + 1); + } + + /// <summary> + /// Removes all leading and trailing occurrences of a set of characters specified + /// in a readonly span from the span. + /// </summary> + /// <param name="span">The source span from which the characters are removed.</param> + /// <param name="trimChars">The span which contains the set of characters to remove.</param> + public static ReadOnlySpan<char> Trim(this ReadOnlySpan<char> span, ReadOnlySpan<char> trimChars) + { + return span.TrimStart(trimChars).TrimEnd(trimChars); + } + + /// <summary> + /// Removes all leading occurrences of a set of characters specified + /// in a readonly span from the span. + /// </summary> + /// <param name="span">The source span from which the characters are removed.</param> + /// <param name="trimChars">The span which contains the set of characters to remove.</param> + public static ReadOnlySpan<char> TrimStart(this ReadOnlySpan<char> span, ReadOnlySpan<char> trimChars) + { + int start = 0; + for (; start < span.Length; start++) + { + for (int i = 0; i < trimChars.Length; i++) + { + if (span[start] == trimChars[i]) + goto Next; + } + break; + Next: + ; + } + return span.Slice(start); + } + + /// <summary> + /// Removes all trailing occurrences of a set of characters specified + /// in a readonly span from the span. + /// </summary> + /// <param name="span">The source span from which the characters are removed.</param> + /// <param name="trimChars">The span which contains the set of characters to remove.</param> + public static ReadOnlySpan<char> TrimEnd(this ReadOnlySpan<char> span, ReadOnlySpan<char> trimChars) + { + int end = span.Length - 1; + for (; end >= 0; end--) + { + for (int i = 0; i < trimChars.Length; i++) + { + if (span[end] == trimChars[i]) + goto Next; + } + break; + Next: + ; + } + return span.Slice(0, end + 1); + } + + /// <summary> + /// Indicates whether the specified span contains only white-space characters. + /// </summary> + public static bool IsWhiteSpace(this ReadOnlySpan<char> span) + { + for (int i = 0; i < span.Length; i++) + { + if (!char.IsWhiteSpace(span[i])) + return false; + } + return true; + } + + /// <summary> + /// Searches for the specified value and returns the index of its first occurrence. If not found, returns -1. Values are compared using IEquatable{T}.Equals(T). + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value">The value to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int IndexOf<T>(this Span<T> span, T value) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.IndexOf( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value), + span.Length); + return SpanHelpers.IndexOf<T>(ref MemoryMarshal.GetReference(span), value, span.Length); + } + + /// <summary> + /// Searches for the specified sequence and returns the index of its first occurrence. If not found, returns -1. Values are compared using IEquatable{T}.Equals(T). + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value">The sequence to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int IndexOf<T>(this Span<T> span, ReadOnlySpan<T> value) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.IndexOf( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + span.Length, + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(value)), + value.Length); + return SpanHelpers.IndexOf<T>(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(value), value.Length); + } + + /// <summary> + /// Searches for the specified value and returns the index of its last occurrence. If not found, returns -1. Values are compared using IEquatable{T}.Equals(T). + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value">The value to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int LastIndexOf<T>(this Span<T> span, T value) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.LastIndexOf( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value), + span.Length); + return SpanHelpers.LastIndexOf<T>(ref MemoryMarshal.GetReference(span), value, span.Length); + } + + /// <summary> + /// Searches for the specified sequence and returns the index of its last occurrence. If not found, returns -1. Values are compared using IEquatable{T}.Equals(T). + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value">The sequence to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int LastIndexOf<T>(this Span<T> span, ReadOnlySpan<T> value) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.LastIndexOf( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + span.Length, + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(value)), + value.Length); + return SpanHelpers.LastIndexOf<T>(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(value), value.Length); + } + + /// <summary> + /// Determines whether two sequences are equal by comparing the elements using IEquatable{T}.Equals(T). + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static bool SequenceEqual<T>(this Span<T> first, ReadOnlySpan<T> second) + where T : IEquatable<T> + { + int length = first.Length; + if (typeof(T) == typeof(byte)) + return length == second.Length && + SpanHelpers.SequenceEqual( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(first)), + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(second)), + length); + return length == second.Length && SpanHelpers.SequenceEqual(ref MemoryMarshal.GetReference(first), ref MemoryMarshal.GetReference(second), length); + } + + /// <summary> + /// Determines the relative order of the sequences being compared by comparing the elements using IComparable{T}.CompareTo(T). + /// </summary> + public static int SequenceCompareTo<T>(this Span<T> first, ReadOnlySpan<T> second) + where T : IComparable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.SequenceCompareTo( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(first)), + first.Length, + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(second)), + second.Length); + return SpanHelpers.SequenceCompareTo(ref MemoryMarshal.GetReference(first), first.Length, ref MemoryMarshal.GetReference(second), second.Length); + } + + /// <summary> + /// Reverses the sequence of the elements in the entire span. + /// </summary> + public static void Reverse<T>(this Span<T> span) + { + ref T p = ref MemoryMarshal.GetReference(span); + int i = 0; + int j = span.Length - 1; + while (i < j) + { + T temp = Unsafe.Add(ref p, i); + Unsafe.Add(ref p, i) = Unsafe.Add(ref p, j); + Unsafe.Add(ref p, j) = temp; + i++; + j--; + } + } + + /// <summary> + /// Searches for the specified value and returns the index of its first occurrence. If not found, returns -1. Values are compared using IEquatable{T}.Equals(T). + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value">The value to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int IndexOf<T>(this ReadOnlySpan<T> span, T value) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.IndexOf( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value), + span.Length); + return SpanHelpers.IndexOf<T>(ref MemoryMarshal.GetReference(span), value, span.Length); + } + + /// <summary> + /// Searches for the specified sequence and returns the index of its first occurrence. If not found, returns -1. Values are compared using IEquatable{T}.Equals(T). + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value">The sequence to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int IndexOf<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> value) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.IndexOf( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + span.Length, + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(value)), + value.Length); + return SpanHelpers.IndexOf<T>(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(value), value.Length); + } + + /// <summary> + /// Searches for the specified value and returns the index of its last occurrence. If not found, returns -1. Values are compared using IEquatable{T}.Equals(T). + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value">The value to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int LastIndexOf<T>(this ReadOnlySpan<T> span, T value) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.LastIndexOf( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value), + span.Length); + return SpanHelpers.LastIndexOf<T>(ref MemoryMarshal.GetReference(span), value, span.Length); + } + + /// <summary> + /// Searches for the specified sequence and returns the index of its last occurrence. If not found, returns -1. Values are compared using IEquatable{T}.Equals(T). + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value">The sequence to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int LastIndexOf<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> value) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.LastIndexOf( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + span.Length, + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(value)), + value.Length); + return SpanHelpers.LastIndexOf<T>(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(value), value.Length); + } + + /// <summary> + /// Searches for the first index of any of the specified values similar to calling IndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value0">One of the values to search for.</param> + /// <param name="value1">One of the values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int IndexOfAny<T>(this Span<T> span, T value0, T value1) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.IndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value0), + Unsafe.As<T, byte>(ref value1), + span.Length); + + return SpanHelpers.IndexOfAny(ref MemoryMarshal.GetReference(span), value0, value1, span.Length); + } + + /// <summary> + /// Searches for the first index of any of the specified values similar to calling IndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value0">One of the values to search for.</param> + /// <param name="value1">One of the values to search for.</param> + /// <param name="value2">One of the values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int IndexOfAny<T>(this Span<T> span, T value0, T value1, T value2) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.IndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value0), + Unsafe.As<T, byte>(ref value1), + Unsafe.As<T, byte>(ref value2), + span.Length); + + return SpanHelpers.IndexOfAny(ref MemoryMarshal.GetReference(span), value0, value1, value2, span.Length); + } + + /// <summary> + /// Searches for the first index of any of the specified values similar to calling IndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="values">The set of values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int IndexOfAny<T>(this Span<T> span, ReadOnlySpan<T> values) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.IndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + span.Length, + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(values)), + values.Length); + + return SpanHelpers.IndexOfAny(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(values), values.Length); + } + + /// <summary> + /// Searches for the first index of any of the specified values similar to calling IndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value0">One of the values to search for.</param> + /// <param name="value1">One of the values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int IndexOfAny<T>(this ReadOnlySpan<T> span, T value0, T value1) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.IndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value0), + Unsafe.As<T, byte>(ref value1), + span.Length); + + return SpanHelpers.IndexOfAny(ref MemoryMarshal.GetReference(span), value0, value1, span.Length); + } + + /// <summary> + /// Searches for the first index of any of the specified values similar to calling IndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value0">One of the values to search for.</param> + /// <param name="value1">One of the values to search for.</param> + /// <param name="value2">One of the values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int IndexOfAny<T>(this ReadOnlySpan<T> span, T value0, T value1, T value2) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.IndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value0), + Unsafe.As<T, byte>(ref value1), + Unsafe.As<T, byte>(ref value2), + span.Length); + + return SpanHelpers.IndexOfAny(ref MemoryMarshal.GetReference(span), value0, value1, value2, span.Length); + } + + /// <summary> + /// Searches for the first index of any of the specified values similar to calling IndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="values">The set of values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int IndexOfAny<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> values) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.IndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + span.Length, + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(values)), + values.Length); + + return SpanHelpers.IndexOfAny(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(values), values.Length); + } + + /// <summary> + /// Searches for the last index of any of the specified values similar to calling LastIndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value0">One of the values to search for.</param> + /// <param name="value1">One of the values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int LastIndexOfAny<T>(this Span<T> span, T value0, T value1) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.LastIndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value0), + Unsafe.As<T, byte>(ref value1), + span.Length); + return SpanHelpers.LastIndexOfAny(ref MemoryMarshal.GetReference(span), value0, value1, span.Length); + } + + /// <summary> + /// Searches for the last index of any of the specified values similar to calling LastIndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value0">One of the values to search for.</param> + /// <param name="value1">One of the values to search for.</param> + /// <param name="value2">One of the values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int LastIndexOfAny<T>(this Span<T> span, T value0, T value1, T value2) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.LastIndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value0), + Unsafe.As<T, byte>(ref value1), + Unsafe.As<T, byte>(ref value2), + span.Length); + return SpanHelpers.LastIndexOfAny(ref MemoryMarshal.GetReference(span), value0, value1, value2, span.Length); + } + + /// <summary> + /// Searches for the last index of any of the specified values similar to calling LastIndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="values">The set of values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int LastIndexOfAny<T>(this Span<T> span, ReadOnlySpan<T> values) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.LastIndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + span.Length, + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(values)), + values.Length); + return SpanHelpers.LastIndexOfAny(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(values), values.Length); + } + + /// <summary> + /// Searches for the last index of any of the specified values similar to calling LastIndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value0">One of the values to search for.</param> + /// <param name="value1">One of the values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int LastIndexOfAny<T>(this ReadOnlySpan<T> span, T value0, T value1) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.LastIndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value0), + Unsafe.As<T, byte>(ref value1), + span.Length); + return SpanHelpers.LastIndexOfAny(ref MemoryMarshal.GetReference(span), value0, value1, span.Length); + } + + /// <summary> + /// Searches for the last index of any of the specified values similar to calling LastIndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="value0">One of the values to search for.</param> + /// <param name="value1">One of the values to search for.</param> + /// <param name="value2">One of the values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int LastIndexOfAny<T>(this ReadOnlySpan<T> span, T value0, T value1, T value2) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.LastIndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + Unsafe.As<T, byte>(ref value0), + Unsafe.As<T, byte>(ref value1), + Unsafe.As<T, byte>(ref value2), + span.Length); + return SpanHelpers.LastIndexOfAny(ref MemoryMarshal.GetReference(span), value0, value1, value2, span.Length); + } + + /// <summary> + /// Searches for the last index of any of the specified values similar to calling LastIndexOf several times with the logical OR operator. If not found, returns -1. + /// </summary> + /// <param name="span">The span to search.</param> + /// <param name="values">The set of values to search for.</param> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int LastIndexOfAny<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> values) + where T : IEquatable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.LastIndexOfAny( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + span.Length, + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(values)), + values.Length); + return SpanHelpers.LastIndexOfAny<T>(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(values), values.Length); + } + + /// <summary> + /// Determines whether two sequences are equal by comparing the elements using IEquatable{T}.Equals(T). + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static bool SequenceEqual<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second) + where T : IEquatable<T> + { + int length = first.Length; + if (typeof(T) == typeof(byte)) + return length == second.Length && + SpanHelpers.SequenceEqual( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(first)), + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(second)), + length); + return length == second.Length && SpanHelpers.SequenceEqual(ref MemoryMarshal.GetReference(first), ref MemoryMarshal.GetReference(second), length); + } + + /// <summary> + /// Determines the relative order of the sequences being compared by comparing the elements using IComparable{T}.CompareTo(T). + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int SequenceCompareTo<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second) + where T : IComparable<T> + { + if (typeof(T) == typeof(byte)) + return SpanHelpers.SequenceCompareTo( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(first)), + first.Length, + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(second)), + second.Length); + return SpanHelpers.SequenceCompareTo(ref MemoryMarshal.GetReference(first), first.Length, ref MemoryMarshal.GetReference(second), second.Length); + } + + /// <summary> + /// Determines whether the specified sequence appears at the start of the span. + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static bool StartsWith<T>(this Span<T> span, ReadOnlySpan<T> value) + where T : IEquatable<T> + { + int valueLength = value.Length; + if (typeof(T) == typeof(byte)) + return valueLength <= span.Length && + SpanHelpers.SequenceEqual( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(value)), + valueLength); + return valueLength <= span.Length && SpanHelpers.SequenceEqual(ref MemoryMarshal.GetReference(span), ref MemoryMarshal.GetReference(value), valueLength); + } + + /// <summary> + /// Determines whether the specified sequence appears at the start of the span. + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static bool StartsWith<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> value) + where T : IEquatable<T> + { + int valueLength = value.Length; + if (typeof(T) == typeof(byte)) + return valueLength <= span.Length && + SpanHelpers.SequenceEqual( + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(span)), + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(value)), + valueLength); + return valueLength <= span.Length && SpanHelpers.SequenceEqual(ref MemoryMarshal.GetReference(span), ref MemoryMarshal.GetReference(value), valueLength); + } + + /// <summary> + /// Determines whether the specified sequence appears at the end of the span. + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static bool EndsWith<T>(this Span<T> span, ReadOnlySpan<T> value) + where T : IEquatable<T> + { + int spanLength = span.Length; + int valueLength = value.Length; + if (typeof(T) == typeof(byte)) + return valueLength <= spanLength && + SpanHelpers.SequenceEqual( + ref Unsafe.As<T, byte>(ref Unsafe.Add(ref MemoryMarshal.GetReference(span), spanLength - valueLength)), + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(value)), + valueLength); + return valueLength <= spanLength && + SpanHelpers.SequenceEqual( + ref Unsafe.Add(ref MemoryMarshal.GetReference(span), spanLength - valueLength), + ref MemoryMarshal.GetReference(value), + valueLength); + } + + /// <summary> + /// Determines whether the specified sequence appears at the end of the span. + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static bool EndsWith<T>(this ReadOnlySpan<T> span, ReadOnlySpan<T> value) + where T : IEquatable<T> + { + int spanLength = span.Length; + int valueLength = value.Length; + if (typeof(T) == typeof(byte)) + return valueLength <= spanLength && + SpanHelpers.SequenceEqual( + ref Unsafe.As<T, byte>(ref Unsafe.Add(ref MemoryMarshal.GetReference(span), spanLength - valueLength)), + ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(value)), + valueLength); + return valueLength <= spanLength && + SpanHelpers.SequenceEqual( + ref Unsafe.Add(ref MemoryMarshal.GetReference(span), spanLength - valueLength), + ref MemoryMarshal.GetReference(value), + valueLength); + } + + /// <summary> + /// Creates a new span over the portion of the target array. + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static Span<T> AsSpan<T>(this T[] array) + { + return new Span<T>(array); + } + + /// <summary> + /// Creates a new span over the portion of the target array segment. + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static Span<T> AsSpan<T>(this ArraySegment<T> arraySegment) + { + return new Span<T>(arraySegment.Array, arraySegment.Offset, arraySegment.Count); + } + + /// <summary> + /// Creates a new readonly span over the entire target array. + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static ReadOnlySpan<T> AsReadOnlySpan<T>(this T[] array) + { + return new ReadOnlySpan<T>(array); + } + + /// <summary> + /// Creates a new readonly span over the entire target span. + /// </summary> + public static ReadOnlySpan<T> AsReadOnlySpan<T>(this Span<T> span) => span; + + /// <summary> + /// Creates a new readonly span over the target array segment. + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static ReadOnlySpan<T> AsReadOnlySpan<T>(this ArraySegment<T> arraySegment) + { + return new ReadOnlySpan<T>(arraySegment.Array, arraySegment.Offset, arraySegment.Count); + } + + /// <summary> + /// Creates a new readonly memory over the entire target memory. + /// </summary> + public static ReadOnlyMemory<T> AsReadOnlyMemory<T>(this Memory<T> memory) => memory; + + /// <summary> + /// Creates a new memory over the portion of the target array. + /// </summary> + public static Memory<T> AsMemory<T>(this T[] array, int start) => new Memory<T>(array, start); + + /// <summary> + /// Copies the contents of the array into the span. If the source + /// and destinations overlap, this method behaves as if the original values in + /// a temporary location before the destination is overwritten. + /// + ///<param name="array">The array to copy items from.</param> + /// <param name="destination">The span to copy items into.</param> + /// <exception cref="System.ArgumentException"> + /// Thrown when the destination Span is shorter than the source array. + /// </exception> + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static void CopyTo<T>(this T[] array, Span<T> destination) + { + new ReadOnlySpan<T>(array).CopyTo(destination); + } + + /// <summary> + /// Copies the contents of the array into the memory. If the source + /// and destinations overlap, this method behaves as if the original values are in + /// a temporary location before the destination is overwritten. + /// + ///<param name="array">The array to copy items from.</param> + /// <param name="destination">The memory to copy items into.</param> + /// <exception cref="System.ArgumentException"> + /// Thrown when the destination is shorter than the source array. + /// </exception> + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static void CopyTo<T>(this T[] array, Memory<T> destination) + { + array.CopyTo(destination.Span); + } + + // + // Overlaps + // ======== + // + // The following methods can be used to determine if two sequences + // overlap in memory. + // + // Two sequences overlap if they have positions in common and neither + // is empty. Empty sequences do not overlap with any other sequence. + // + // If two sequences overlap, the element offset is the number of + // elements by which the second sequence is offset from the first + // sequence (i.e., second minus first). An exception is thrown if the + // number is not a whole number, which can happen when a sequence of a + // smaller type is cast to a sequence of a larger type with unsafe code + // or NonPortableCast. If the sequences do not overlap, the offset is + // meaningless and arbitrarily set to zero. + // + // Implementation + // -------------- + // + // Implementing this correctly is quite tricky due of two problems: + // + // * If the sequences refer to two different objects on the managed + // heap, the garbage collector can move them freely around or change + // their relative order in memory. + // + // * The distance between two sequences can be greater than + // int.MaxValue (on a 32-bit system) or long.MaxValue (on a 64-bit + // system). + // + // (For simplicity, the following text assumes a 32-bit system, but + // everything also applies to a 64-bit system if every 32 is replaced a + // 64.) + // + // The first problem is solved by calculating the distance with exactly + // one atomic operation. If the garbage collector happens to move the + // sequences afterwards and the sequences overlapped before, they will + // still overlap after the move and their distance hasn't changed. If + // the sequences did not overlap, the distance can change but the + // sequences still won't overlap. + // + // The second problem is solved by making all addresses relative to the + // start of the first sequence and performing all operations in + // unsigned integer arithmetic modulo 2³². + // + // Example + // ------- + // + // Let's say there are two sequences, x and y. Let + // + // ref T xRef = MemoryMarshal.GetReference(x) + // uint xLength = x.Length * Unsafe.SizeOf<T>() + // ref T yRef = MemoryMarshal.GetReference(y) + // uint yLength = y.Length * Unsafe.SizeOf<T>() + // + // Visually, the two sequences are located somewhere in the 32-bit + // address space as follows: + // + // [----------------------------------------------) normal address space + // 0 2³² + // [------------------) first sequence + // xRef xRef + xLength + // [--------------------------) . second sequence + // yRef . yRef + yLength + // : . . . + // : . . . + // . . . + // . . . + // . . . + // [----------------------------------------------) relative address space + // 0 . . 2³² + // [------------------) : first sequence + // x1 . x2 : + // -------------) [------------- second sequence + // y2 y1 + // + // The idea is to make all addresses relative to xRef: Let x1 be the + // start address of x in this relative address space, x2 the end + // address of x, y1 the start address of y, and y2 the end address of + // y: + // + // nuint x1 = 0 + // nuint x2 = xLength + // nuint y1 = (nuint)Unsafe.ByteOffset(xRef, yRef) + // nuint y2 = y1 + yLength + // + // xRef relative to xRef is 0. + // + // x2 is simply x1 + xLength. This cannot overflow. + // + // yRef relative to xRef is (yRef - xRef). If (yRef - xRef) is + // negative, casting it to an unsigned 32-bit integer turns it into + // (yRef - xRef + 2³²). So, in the example above, y1 moves to the right + // of x2. + // + // y2 is simply y1 + yLength. Note that this can overflow, as in the + // example above, which must be avoided. + // + // The two sequences do *not* overlap if y is entirely in the space + // right of x in the relative address space. (It can't be left of it!) + // + // (y1 >= x2) && (y2 <= 2³²) + // + // Inversely, they do overlap if + // + // (y1 < x2) || (y2 > 2³²) + // + // After substituting x2 and y2 with their respective definition: + // + // == (y1 < xLength) || (y1 + yLength > 2³²) + // + // Since yLength can't be greater than the size of the address space, + // the overflow can be avoided as follows: + // + // == (y1 < xLength) || (y1 > 2³² - yLength) + // + // However, 2³² cannot be stored in an unsigned 32-bit integer, so one + // more change is needed to keep doing everything with unsigned 32-bit + // integers: + // + // == (y1 < xLength) || (y1 > -yLength) + // + // Due to modulo arithmetic, this gives exactly same result *except* if + // yLength is zero, since 2³² - 0 is 0 and not 2³². So the case + // y.IsEmpty must be handled separately first. + // + + /// <summary> + /// Determines whether two sequences overlap in memory. + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static bool Overlaps<T>(this Span<T> first, ReadOnlySpan<T> second) + { + return Overlaps((ReadOnlySpan<T>)first, second); + } + + /// <summary> + /// Determines whether two sequences overlap in memory and outputs the element offset. + /// </summary> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static bool Overlaps<T>(this Span<T> first, ReadOnlySpan<T> second, out int elementOffset) + { + return Overlaps((ReadOnlySpan<T>)first, second, out elementOffset); + } + + /// <summary> + /// Determines whether two sequences overlap in memory. + /// </summary> + public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second) + { + if (first.IsEmpty || second.IsEmpty) + { + return false; + } + + IntPtr byteOffset = Unsafe.ByteOffset( + ref MemoryMarshal.GetReference(first), + ref MemoryMarshal.GetReference(second)); + + if (Unsafe.SizeOf<IntPtr>() == sizeof(int)) + { + return (uint)byteOffset < (uint)(first.Length * Unsafe.SizeOf<T>()) || + (uint)byteOffset > (uint)-(second.Length * Unsafe.SizeOf<T>()); + } + else + { + return (ulong)byteOffset < (ulong)((long)first.Length * Unsafe.SizeOf<T>()) || + (ulong)byteOffset > (ulong)-((long)second.Length * Unsafe.SizeOf<T>()); + } + } + + /// <summary> + /// Determines whether two sequences overlap in memory and outputs the element offset. + /// </summary> + public static bool Overlaps<T>(this ReadOnlySpan<T> first, ReadOnlySpan<T> second, out int elementOffset) + { + if (first.IsEmpty || second.IsEmpty) + { + elementOffset = 0; + return false; + } + + IntPtr byteOffset = Unsafe.ByteOffset( + ref MemoryMarshal.GetReference(first), + ref MemoryMarshal.GetReference(second)); + + if (Unsafe.SizeOf<IntPtr>() == sizeof(int)) + { + if ((uint)byteOffset < (uint)(first.Length * Unsafe.SizeOf<T>()) || + (uint)byteOffset > (uint)-(second.Length * Unsafe.SizeOf<T>())) + { + if ((int)byteOffset % Unsafe.SizeOf<T>() != 0) + ThrowHelper.ThrowArgumentException_OverlapAlignmentMismatch(); + + elementOffset = (int)byteOffset / Unsafe.SizeOf<T>(); + return true; + } + else + { + elementOffset = 0; + return false; + } + } + else + { + if ((ulong)byteOffset < (ulong)((long)first.Length * Unsafe.SizeOf<T>()) || + (ulong)byteOffset > (ulong)-((long)second.Length * Unsafe.SizeOf<T>())) + { + if ((long)byteOffset % Unsafe.SizeOf<T>() != 0) + ThrowHelper.ThrowArgumentException_OverlapAlignmentMismatch(); + + elementOffset = (int)((long)byteOffset / Unsafe.SizeOf<T>()); + return true; + } + else + { + elementOffset = 0; + return false; + } + } + } + + /// <summary> + /// Searches an entire sorted <see cref="Span{T}"/> for a value + /// using the specified <see cref="IComparable{T}"/> generic interface. + /// </summary> + /// <typeparam name="T">The element type of the span.</typeparam> + /// <param name="span">The sorted <see cref="Span{T}"/> to search.</param> + /// <param name="comparable">The <see cref="IComparable{T}"/> to use when comparing.</param> + /// <returns> + /// The zero-based index of <paramref name="comparable"/> in the sorted <paramref name="span"/>, + /// if <paramref name="comparable"/> is found; otherwise, a negative number that is the bitwise complement + /// of the index of the next element that is larger than <paramref name="comparable"/> or, if there is + /// no larger element, the bitwise complement of <see cref="Span{T}.Length"/>. + /// </returns> + /// <exception cref="T:System.ArgumentNullException"> + /// <paramref name = "comparable" /> is <see langword="null"/> . + /// </exception> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int BinarySearch<T>( + this Span<T> span, IComparable<T> comparable) + { + return BinarySearch<T, IComparable<T>>(span, comparable); + } + + /// <summary> + /// Searches an entire sorted <see cref="Span{T}"/> for a value + /// using the specified <typeparamref name="TComparable"/> generic type. + /// </summary> + /// <typeparam name="T">The element type of the span.</typeparam> + /// <typeparam name="TComparable">The specific type of <see cref="IComparable{T}"/>.</typeparam> + /// <param name="span">The sorted <see cref="Span{T}"/> to search.</param> + /// <param name="comparable">The <typeparamref name="TComparable"/> to use when comparing.</param> + /// <returns> + /// The zero-based index of <paramref name="comparable"/> in the sorted <paramref name="span"/>, + /// if <paramref name="comparable"/> is found; otherwise, a negative number that is the bitwise complement + /// of the index of the next element that is larger than <paramref name="comparable"/> or, if there is + /// no larger element, the bitwise complement of <see cref="Span{T}.Length"/>. + /// </returns> + /// <exception cref="T:System.ArgumentNullException"> + /// <paramref name = "comparable" /> is <see langword="null"/> . + /// </exception> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int BinarySearch<T, TComparable>( + this Span<T> span, TComparable comparable) + where TComparable : IComparable<T> + { + return BinarySearch((ReadOnlySpan<T>)span, comparable); + } + + /// <summary> + /// Searches an entire sorted <see cref="Span{T}"/> for the specified <paramref name="value"/> + /// using the specified <typeparamref name="TComparer"/> generic type. + /// </summary> + /// <typeparam name="T">The element type of the span.</typeparam> + /// <typeparam name="TComparer">The specific type of <see cref="IComparer{T}"/>.</typeparam> + /// <param name="span">The sorted <see cref="Span{T}"/> to search.</param> + /// <param name="value">The object to locate. The value can be null for reference types.</param> + /// <param name="comparer">The <typeparamref name="TComparer"/> to use when comparing.</param> + /// /// <returns> + /// The zero-based index of <paramref name="value"/> in the sorted <paramref name="span"/>, + /// if <paramref name="value"/> is found; otherwise, a negative number that is the bitwise complement + /// of the index of the next element that is larger than <paramref name="value"/> or, if there is + /// no larger element, the bitwise complement of <see cref="Span{T}.Length"/>. + /// </returns> + /// <exception cref="T:System.ArgumentNullException"> + /// <paramref name = "comparer" /> is <see langword="null"/> . + /// </exception> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int BinarySearch<T, TComparer>( + this Span<T> span, T value, TComparer comparer) + where TComparer : IComparer<T> + { + return BinarySearch((ReadOnlySpan<T>)span, value, comparer); + } + + /// <summary> + /// Searches an entire sorted <see cref="ReadOnlySpan{T}"/> for a value + /// using the specified <see cref="IComparable{T}"/> generic interface. + /// </summary> + /// <typeparam name="T">The element type of the span.</typeparam> + /// <param name="span">The sorted <see cref="ReadOnlySpan{T}"/> to search.</param> + /// <param name="comparable">The <see cref="IComparable{T}"/> to use when comparing.</param> + /// <returns> + /// The zero-based index of <paramref name="comparable"/> in the sorted <paramref name="span"/>, + /// if <paramref name="comparable"/> is found; otherwise, a negative number that is the bitwise complement + /// of the index of the next element that is larger than <paramref name="comparable"/> or, if there is + /// no larger element, the bitwise complement of <see cref="ReadOnlySpan{T}.Length"/>. + /// </returns> + /// <exception cref="T:System.ArgumentNullException"> + /// <paramref name = "comparable" /> is <see langword="null"/> . + /// </exception> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int BinarySearch<T>( + this ReadOnlySpan<T> span, IComparable<T> comparable) + { + return BinarySearch<T, IComparable<T>>(span, comparable); + } + + /// <summary> + /// Searches an entire sorted <see cref="ReadOnlySpan{T}"/> for a value + /// using the specified <typeparamref name="TComparable"/> generic type. + /// </summary> + /// <typeparam name="T">The element type of the span.</typeparam> + /// <typeparam name="TComparable">The specific type of <see cref="IComparable{T}"/>.</typeparam> + /// <param name="span">The sorted <see cref="ReadOnlySpan{T}"/> to search.</param> + /// <param name="comparable">The <typeparamref name="TComparable"/> to use when comparing.</param> + /// <returns> + /// The zero-based index of <paramref name="comparable"/> in the sorted <paramref name="span"/>, + /// if <paramref name="comparable"/> is found; otherwise, a negative number that is the bitwise complement + /// of the index of the next element that is larger than <paramref name="comparable"/> or, if there is + /// no larger element, the bitwise complement of <see cref="ReadOnlySpan{T}.Length"/>. + /// </returns> + /// <exception cref="T:System.ArgumentNullException"> + /// <paramref name = "comparable" /> is <see langword="null"/> . + /// </exception> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int BinarySearch<T, TComparable>( + this ReadOnlySpan<T> span, TComparable comparable) + where TComparable : IComparable<T> + { + return SpanHelpers.BinarySearch(span, comparable); + } + + /// <summary> + /// Searches an entire sorted <see cref="ReadOnlySpan{T}"/> for the specified <paramref name="value"/> + /// using the specified <typeparamref name="TComparer"/> generic type. + /// </summary> + /// <typeparam name="T">The element type of the span.</typeparam> + /// <typeparam name="TComparer">The specific type of <see cref="IComparer{T}"/>.</typeparam> + /// <param name="span">The sorted <see cref="ReadOnlySpan{T}"/> to search.</param> + /// <param name="value">The object to locate. The value can be null for reference types.</param> + /// <param name="comparer">The <typeparamref name="TComparer"/> to use when comparing.</param> + /// /// <returns> + /// The zero-based index of <paramref name="value"/> in the sorted <paramref name="span"/>, + /// if <paramref name="value"/> is found; otherwise, a negative number that is the bitwise complement + /// of the index of the next element that is larger than <paramref name="value"/> or, if there is + /// no larger element, the bitwise complement of <see cref="ReadOnlySpan{T}.Length"/>. + /// </returns> + /// <exception cref="T:System.ArgumentNullException"> + /// <paramref name = "comparer" /> is <see langword="null"/> . + /// </exception> + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int BinarySearch<T, TComparer>( + this ReadOnlySpan<T> span, T value, TComparer comparer) + where TComparer : IComparer<T> + { + if (comparer == null) + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.comparer); + + var comparable = new SpanHelpers.ComparerComparable<T, TComparer>( + value, comparer); + return BinarySearch(span, comparable); + } + } +} diff --git a/src/System.Private.CoreLib/shared/System/Span.Fast.cs b/src/System.Private.CoreLib/shared/System/Span.Fast.cs index 36493cd88..0ae1922fd 100644 --- a/src/System.Private.CoreLib/shared/System/Span.Fast.cs +++ b/src/System.Private.CoreLib/shared/System/Span.Fast.cs @@ -162,11 +162,11 @@ namespace System { if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) { - Span.ClearWithReferences(ref Unsafe.As<T, IntPtr>(ref _pointer.Value), (nuint)_length * (nuint)(Unsafe.SizeOf<T>() / sizeof(nuint))); + SpanHelpers.ClearWithReferences(ref Unsafe.As<T, IntPtr>(ref _pointer.Value), (nuint)_length * (nuint)(Unsafe.SizeOf<T>() / sizeof(nuint))); } else { - Span.ClearWithoutReferences(ref Unsafe.As<T, byte>(ref _pointer.Value), (nuint)_length * (nuint)Unsafe.SizeOf<T>()); + SpanHelpers.ClearWithoutReferences(ref Unsafe.As<T, byte>(ref _pointer.Value), (nuint)_length * (nuint)Unsafe.SizeOf<T>()); } } diff --git a/src/System.Private.CoreLib/shared/System/Span.NonGeneric.cs b/src/System.Private.CoreLib/shared/System/Span.NonGeneric.cs index ff2d77301..4f2892d4c 100644 --- a/src/System.Private.CoreLib/shared/System/Span.NonGeneric.cs +++ b/src/System.Private.CoreLib/shared/System/Span.NonGeneric.cs @@ -23,1034 +23,19 @@ namespace System /// </summary> public static class Span { - public static bool Contains(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) - { - return (IndexOf(span, value, comparisonType) >= 0); - } + public static Span<byte> AsBytes<T>(Span<T> source) + where T : struct => source.AsBytes(); - public static bool Equals(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) - { - StringSpanHelpers.CheckStringComparison(comparisonType); - - switch (comparisonType) - { - case StringComparison.CurrentCulture: - return (CultureInfo.CurrentCulture.CompareInfo.Compare(span, value, CompareOptions.None) == 0); - - case StringComparison.CurrentCultureIgnoreCase: - return (CultureInfo.CurrentCulture.CompareInfo.Compare(span, value, CompareOptions.IgnoreCase) == 0); - - case StringComparison.InvariantCulture: - return (CompareInfo.Invariant.Compare(span, value, CompareOptions.None) == 0); - - case StringComparison.InvariantCultureIgnoreCase: - return (CompareInfo.Invariant.Compare(span, value, CompareOptions.IgnoreCase) == 0); - - case StringComparison.Ordinal: - if (span.Length != value.Length) - return false; - if (value.Length == 0) // span.Length == value.Length == 0 - return true; - return OrdinalHelper(span, value, value.Length); - - case StringComparison.OrdinalIgnoreCase: - if (span.Length != value.Length) - return false; - if (value.Length == 0) // span.Length == value.Length == 0 - return true; - return (CompareInfo.CompareOrdinalIgnoreCase(span, value) == 0); - } - - Debug.Fail("StringComparison outside range"); - return false; - } - - public static int CompareTo(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) - { - StringSpanHelpers.CheckStringComparison(comparisonType); - - switch (comparisonType) - { - case StringComparison.CurrentCulture: - return CultureInfo.CurrentCulture.CompareInfo.Compare(span, value, CompareOptions.None); - - case StringComparison.CurrentCultureIgnoreCase: - return CultureInfo.CurrentCulture.CompareInfo.Compare(span, value, CompareOptions.IgnoreCase); - - case StringComparison.InvariantCulture: - return CompareInfo.Invariant.Compare(span, value, CompareOptions.None); - - case StringComparison.InvariantCultureIgnoreCase: - return CompareInfo.Invariant.Compare(span, value, CompareOptions.IgnoreCase); - - case StringComparison.Ordinal: - if (span.Length == 0 || value.Length == 0) - return span.Length - value.Length; - return string.CompareOrdinal(span, value); - - case StringComparison.OrdinalIgnoreCase: - return CompareInfo.CompareOrdinalIgnoreCase(span, value); - } - - Debug.Fail("StringComparison outside range"); - return 0; - } - - public static int IndexOf(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) - { - StringSpanHelpers.CheckStringComparison(comparisonType); - - if (value.Length == 0) - { - return 0; - } - - if (span.Length == 0) - { - return -1; - } - - switch (comparisonType) - { - case StringComparison.CurrentCulture: - return IndexOfCultureHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); - - case StringComparison.CurrentCultureIgnoreCase: - return IndexOfCultureIgnoreCaseHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); - - case StringComparison.InvariantCulture: - return IndexOfCultureHelper(span, value, CompareInfo.Invariant); - - case StringComparison.InvariantCultureIgnoreCase: - return IndexOfCultureIgnoreCaseHelper(span, value, CompareInfo.Invariant); - - case StringComparison.Ordinal: - return IndexOfOrdinalHelper(span, value, ignoreCase: false); - - case StringComparison.OrdinalIgnoreCase: - return IndexOfOrdinalHelper(span, value, ignoreCase: true); - } - - Debug.Fail("StringComparison outside range"); - return -1; - } - - internal static int IndexOfCultureHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) - { - Debug.Assert(span.Length != 0); - Debug.Assert(value.Length != 0); - - if (GlobalizationMode.Invariant) - { - return CompareInfo.InvariantIndexOf(span, value, ignoreCase: false); - } - - return compareInfo.IndexOf(span, value, CompareOptions.None); - } - - internal static int IndexOfCultureIgnoreCaseHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) - { - Debug.Assert(span.Length != 0); - Debug.Assert(value.Length != 0); - - if (GlobalizationMode.Invariant) - { - return CompareInfo.InvariantIndexOf(span, value, ignoreCase: true); - } - - return compareInfo.IndexOf(span, value, CompareOptions.IgnoreCase); - } - - internal static int IndexOfOrdinalHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, bool ignoreCase) - { - Debug.Assert(span.Length != 0); - Debug.Assert(value.Length != 0); - - if (GlobalizationMode.Invariant) - { - return CompareInfo.InvariantIndexOf(span, value, ignoreCase); - } - - return CompareInfo.Invariant.IndexOfOrdinal(span, value, ignoreCase); - } - - /// <summary> - /// Copies the characters from the source span into the destination, converting each character to lowercase. - /// </summary> - public static int ToLower(this ReadOnlySpan<char> source, Span<char> destination, CultureInfo culture) - { - if (culture == null) - ThrowHelper.ThrowArgumentNullException(ExceptionArgument.culture); - - // Assuming that changing case does not affect length - if (destination.Length < source.Length) - return -1; - - if (GlobalizationMode.Invariant) - culture.TextInfo.ToLowerAsciiInvariant(source, destination); - else - culture.TextInfo.ChangeCase(source, destination, toUpper: false); - return source.Length; - } - - /// <summary> - /// Copies the characters from the source span into the destination, converting each character to lowercase - /// using the casing rules of the invariant culture. - /// </summary> - public static int ToLowerInvariant(this ReadOnlySpan<char> source, Span<char> destination) - { - // Assuming that changing case does not affect length - if (destination.Length < source.Length) - return -1; - - if (GlobalizationMode.Invariant) - CultureInfo.InvariantCulture.TextInfo.ToLowerAsciiInvariant(source, destination); - else - CultureInfo.InvariantCulture.TextInfo.ChangeCase(source, destination, toUpper: false); - return source.Length; - } - - /// <summary> - /// Copies the characters from the source span into the destination, converting each character to uppercase. - /// </summary> - public static int ToUpper(this ReadOnlySpan<char> source, Span<char> destination, CultureInfo culture) - { - if (culture == null) - ThrowHelper.ThrowArgumentNullException(ExceptionArgument.culture); - - // Assuming that changing case does not affect length - if (destination.Length < source.Length) - return -1; - - if (GlobalizationMode.Invariant) - culture.TextInfo.ToUpperAsciiInvariant(source, destination); - else - culture.TextInfo.ChangeCase(source, destination, toUpper: true); - return source.Length; - } - - /// <summary> - /// Copies the characters from the source span into the destination, converting each character to uppercase - /// using the casing rules of the invariant culture. - /// </summary> - public static int ToUpperInvariant(this ReadOnlySpan<char> source, Span<char> destination) - { - // Assuming that changing case does not affect length - if (destination.Length < source.Length) - return -1; - - if (GlobalizationMode.Invariant) - CultureInfo.InvariantCulture.TextInfo.ToUpperAsciiInvariant(source, destination); - else - CultureInfo.InvariantCulture.TextInfo.ChangeCase(source, destination, toUpper: true); - return source.Length; - } - - /// <summary> - /// Determines whether the beginning of the span matches the specified value when compared using the specified comparison option. - /// </summary> - public static bool StartsWith(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) - { - if (value.Length == 0) - { - StringSpanHelpers.CheckStringComparison(comparisonType); - return true; - } - - switch (comparisonType) - { - case StringComparison.CurrentCulture: - return StartsWithCultureHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); - - case StringComparison.CurrentCultureIgnoreCase: - return StartsWithCultureIgnoreCaseHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); - - case StringComparison.InvariantCulture: - return StartsWithCultureHelper(span, value, CompareInfo.Invariant); - - case StringComparison.InvariantCultureIgnoreCase: - return StartsWithCultureIgnoreCaseHelper(span, value, CompareInfo.Invariant); - - case StringComparison.Ordinal: - return StartsWithOrdinalHelper(span, value); - - case StringComparison.OrdinalIgnoreCase: - return StartsWithOrdinalIgnoreCaseHelper(span, value); - - default: - throw new ArgumentException(SR.NotSupported_StringComparison, nameof(comparisonType)); - } - } - - internal static bool StartsWithCultureHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) - { - Debug.Assert(value.Length != 0); - - if (GlobalizationMode.Invariant) - { - return StartsWithOrdinalHelper(span, value); - } - if (span.Length == 0) - { - return false; - } - return compareInfo.IsPrefix(span, value, CompareOptions.None); - } - - internal static bool StartsWithCultureIgnoreCaseHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) - { - Debug.Assert(value.Length != 0); - - if (GlobalizationMode.Invariant) - { - return StartsWithOrdinalIgnoreCaseHelper(span, value); - } - if (span.Length == 0) - { - return false; - } - return compareInfo.IsPrefix(span, value, CompareOptions.IgnoreCase); - } - - internal static bool StartsWithOrdinalIgnoreCaseHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value) - { - Debug.Assert(value.Length != 0); - - if (span.Length < value.Length) - { - return false; - } - return CompareInfo.CompareOrdinalIgnoreCase(span.Slice(0, value.Length), value) == 0; - } - - internal static bool StartsWithOrdinalHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value) - { - Debug.Assert(value.Length != 0); - - if (span.Length < value.Length) - { - return false; - } - return OrdinalHelper(span, value, value.Length); - } - - internal static unsafe bool OrdinalHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, int length) - { - Debug.Assert(length != 0); - Debug.Assert(span.Length >= length); - - fixed (char* ap = &MemoryMarshal.GetReference(span)) - fixed (char* bp = &MemoryMarshal.GetReference(value)) - { - char* a = ap; - char* b = bp; - -#if BIT64 - // Single int read aligns pointers for the following long reads - if (length >= 2) - { - if (*(int*)a != *(int*)b) - return false; - length -= 2; - a += 2; - b += 2; - } - - while (length >= 12) - { - if (*(long*)a != *(long*)b) - return false; - if (*(long*)(a + 4) != *(long*)(b + 4)) - return false; - if (*(long*)(a + 8) != *(long*)(b + 8)) - return false; - length -= 12; - a += 12; - b += 12; - } -#else - while (length >= 10) - { - if (*(int*)a != *(int*)b) return false; - if (*(int*)(a+2) != *(int*)(b+2)) return false; - if (*(int*)(a+4) != *(int*)(b+4)) return false; - if (*(int*)(a+6) != *(int*)(b+6)) return false; - if (*(int*)(a+8) != *(int*)(b+8)) return false; - length -= 10; a += 10; b += 10; - } -#endif - - while (length >= 2) - { - if (*(int*)a != *(int*)b) - return false; - length -= 2; - a += 2; - b += 2; - } - - // PERF: This depends on the fact that the String objects are always zero terminated - // and that the terminating zero is not included in the length. For even string sizes - // this compare can include the zero terminator. Bitwise OR avoids a branch. - return length == 0 | *a == *b; - } - } - - /// <summary> - /// Determines whether the end of the span matches the specified value when compared using the specified comparison option. - /// </summary> - public static bool EndsWith(this ReadOnlySpan<char> span, ReadOnlySpan<char> value, StringComparison comparisonType) - { - if (value.Length == 0) - { - StringSpanHelpers.CheckStringComparison(comparisonType); - return true; - } - - switch (comparisonType) - { - case StringComparison.CurrentCulture: - return EndsWithCultureHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); - - case StringComparison.CurrentCultureIgnoreCase: - return EndsWithCultureIgnoreCaseHelper(span, value, CultureInfo.CurrentCulture.CompareInfo); - - case StringComparison.InvariantCulture: - return EndsWithCultureHelper(span, value, CompareInfo.Invariant); - - case StringComparison.InvariantCultureIgnoreCase: - return EndsWithCultureIgnoreCaseHelper(span, value, CompareInfo.Invariant); - - case StringComparison.Ordinal: - return EndsWithOrdinalHelper(span, value); - - case StringComparison.OrdinalIgnoreCase: - return EndsWithOrdinalIgnoreCaseHelper(span, value); - - default: - throw new ArgumentException(SR.NotSupported_StringComparison, nameof(comparisonType)); - } - } - - internal static bool EndsWithCultureHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) - { - Debug.Assert(value.Length != 0); - - if (GlobalizationMode.Invariant) - { - return EndsWithOrdinalHelper(span, value); - } - if (span.Length == 0) - { - return false; - } - return compareInfo.IsSuffix(span, value, CompareOptions.None); - } - - internal static bool EndsWithCultureIgnoreCaseHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) - { - Debug.Assert(value.Length != 0); - - if (GlobalizationMode.Invariant) - { - return EndsWithOrdinalIgnoreCaseHelper(span, value); - } - if (span.Length == 0) - { - return false; - } - return compareInfo.IsSuffix(span, value, CompareOptions.IgnoreCase); - } - - internal static bool EndsWithOrdinalIgnoreCaseHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value) - { - Debug.Assert(value.Length != 0); - - if (span.Length < value.Length) - { - return false; - } - return (CompareInfo.CompareOrdinalIgnoreCase(span.Slice(span.Length - value.Length), value) == 0); - } - - internal static bool EndsWithOrdinalHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value) - { - Debug.Assert(value.Length != 0); - - if (span.Length < value.Length) - { - return false; - } - return OrdinalHelper(span.Slice(span.Length - value.Length), value, value.Length); - } - - /// <summary> - /// Helper method for MemoryExtensions.AsSpan(T[] array, int start). - /// </summary> - public static Span<T> AsSpan<T>(T[] array, int start) - { - if (array == null) - { - if (start != 0) - ThrowHelper.ThrowArgumentOutOfRangeException(); - return default; - } - if (default(T) == null && array.GetType() != typeof(T[])) - ThrowHelper.ThrowArrayTypeMismatchException(); - if ((uint)start > (uint)array.Length) - ThrowHelper.ThrowArgumentOutOfRangeException(); - - return new Span<T>(ref Unsafe.Add(ref Unsafe.As<byte, T>(ref array.GetRawSzArrayData()), start), array.Length - start); - } - - /// <summary> - /// Helper method for MemoryExtensions.AsMemory(T[] array, int start). - /// </summary> - public static Memory<T> AsMemory<T>(T[] array, int start) => new Memory<T>(array, start); - - /// <summary>Creates a new <see cref="ReadOnlyMemory{char}"/> over the portion of the target string.</summary> - /// <param name="text">The target string.</param> - /// <remarks>Returns default when <paramref name="text"/> is null.</remarks> - public static ReadOnlyMemory<char> AsReadOnlyMemory(this string text) - { - if (text == null) - return default; - - return new ReadOnlyMemory<char>(text, 0, text.Length); - } - - /// <summary>Creates a new <see cref="ReadOnlyMemory{char}"/> over the portion of the target string.</summary> - /// <param name="text">The target string.</param> - /// <remarks>Returns default when <paramref name="text"/> is null.</remarks> - /// <exception cref="System.ArgumentOutOfRangeException"> - /// Thrown when the specified <paramref name="start"/> index is not in range (<0 or >text.Length). - /// </exception> - public static ReadOnlyMemory<char> AsReadOnlyMemory(this string text, int start) - { - if (text == null) - { - if (start != 0) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); - return default; - } - - if ((uint)start > (uint)text.Length) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); - - return new ReadOnlyMemory<char>(text, start, text.Length - start); - } - - /// <summary>Creates a new <see cref="ReadOnlyMemory{char}"/> over the portion of the target string.</summary> - /// <param name="text">The target string.</param> - /// <remarks>Returns default when <paramref name="text"/> is null.</remarks> - /// <exception cref="System.ArgumentOutOfRangeException"> - /// Thrown when the specified <paramref name="start"/> index or <paramref name="length"/> is not in range. - /// </exception> - public static ReadOnlyMemory<char> AsReadOnlyMemory(this string text, int start, int length) - { - if (text == null) - { - if (start != 0 || length != 0) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); - return default; - } - - if ((uint)start > (uint)text.Length || (uint)length > (uint)(text.Length - start)) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); - - return new ReadOnlyMemory<char>(text, start, length); - } - - /// <summary>Attempts to get the underlying <see cref="string"/> from a <see cref="ReadOnlyMemory{T}"/>.</summary> - /// <param name="readOnlyMemory">The memory that may be wrapping a <see cref="string"/> object.</param> - /// <param name="text">The string.</param> - /// <param name="start">The starting location in <paramref name="text"/>.</param> - /// <param name="length">The number of items in <paramref name="text"/>.</param> - /// <returns></returns> - public static bool TryGetString(this ReadOnlyMemory<char> readOnlyMemory, out string text, out int start, out int length) - { - if (readOnlyMemory.GetObjectStartLength(out int offset, out int count) is string s) - { - text = s; - start = offset; - length = count; - return true; - } - else - { - text = null; - start = 0; - length = 0; - return false; - } - } - - /// <summary> - /// Casts a Span of one primitive type <typeparamref name="T"/> to Span of bytes. - /// That type may not contain pointers or references. This is checked at runtime in order to preserve type safety. - /// </summary> - /// <param name="source">The source slice, of type <typeparamref name="T"/>.</param> - /// <exception cref="System.ArgumentException"> - /// Thrown when <typeparamref name="T"/> contains pointers. - /// </exception> - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static Span<byte> AsBytes<T>(this Span<T> source) - where T : struct - { - if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) - ThrowHelper.ThrowInvalidTypeWithPointersNotSupported(typeof(T)); - - return new Span<byte>( - ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(source)), - checked(source.Length * Unsafe.SizeOf<T>())); - } - - /// <summary> - /// Casts a ReadOnlySpan of one primitive type <typeparamref name="T"/> to ReadOnlySpan of bytes. - /// That type may not contain pointers or references. This is checked at runtime in order to preserve type safety. - /// </summary> - /// <param name="source">The source slice, of type <typeparamref name="T"/>.</param> - /// <exception cref="System.ArgumentException"> - /// Thrown when <typeparamref name="T"/> contains pointers. - /// </exception> - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static ReadOnlySpan<byte> AsBytes<T>(this ReadOnlySpan<T> source) - where T : struct - { - if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) - ThrowHelper.ThrowInvalidTypeWithPointersNotSupported(typeof(T)); - - return new ReadOnlySpan<byte>( - ref Unsafe.As<T, byte>(ref MemoryMarshal.GetReference(source)), - checked(source.Length * Unsafe.SizeOf<T>())); - } - - /// <summary> - /// Creates a new readonly span over the portion of the target string. - /// </summary> - /// <param name="text">The target string.</param> - /// <remarks>Returns default when <paramref name="text"/> is null.</remarks> - /// reference (Nothing in Visual Basic).</exception> - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static ReadOnlySpan<char> AsSpan(this string text) - { - if (text == null) - return default; - - return new ReadOnlySpan<char>(ref text.GetRawStringData(), text.Length); - } - - /// <summary> - /// Creates a new readonly span over the portion of the target string. - /// </summary> - /// <param name="text">The target string.</param> - /// <remarks>Returns default when <paramref name="text"/> is null.</remarks> - /// <exception cref="System.ArgumentOutOfRangeException"> - /// Thrown when the specified <paramref name="start"/> index is not in range (<0 or >text.Length). - /// </exception> - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static ReadOnlySpan<char> AsSpan(this string text, int start) - { - if (text == null) - { - if (start != 0) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); - return default; - } - - if ((uint)start > (uint)text.Length) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); - - return new ReadOnlySpan<char>(ref Unsafe.Add(ref text.GetRawStringData(), start), text.Length - start); - } - - /// <summary> - /// Creates a new readonly span over the portion of the target string. - /// </summary> - /// <param name="text">The target string.</param> - /// <remarks>Returns default when <paramref name="text"/> is null.</remarks> - /// <exception cref="System.ArgumentOutOfRangeException"> - /// Thrown when the specified <paramref name="start"/> index or <paramref name="length"/> is not in range. - /// </exception> - [MethodImpl(MethodImplOptions.AggressiveInlining)] - public static ReadOnlySpan<char> AsSpan(this string text, int start, int length) - { - if (text == null) - { - if (start != 0 || length != 0) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); - return default; - } - - if ((uint)start > (uint)text.Length || (uint)length > (uint)(text.Length - start)) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.start); - - return new ReadOnlySpan<char>(ref Unsafe.Add(ref text.GetRawStringData(), start), length); - } + public static ReadOnlySpan<byte> AsBytes<T>(ReadOnlySpan<T> source) + where T : struct => source.AsBytes(); // TODO: Delete once the AsReadOnlySpan -> AsSpan rename propages through the system - public static ReadOnlySpan<char> AsReadOnlySpan(this string text) => AsSpan(text); - public static ReadOnlySpan<char> AsReadOnlySpan(this string text, int start) => AsSpan(text, start); - public static ReadOnlySpan<char> AsReadOnlySpan(this string text, int start, int length) => AsSpan(text, start, length); - - internal static unsafe void ClearWithoutReferences(ref byte b, nuint byteLength) - { - if (byteLength == 0) - return; - -#if CORECLR && (AMD64 || ARM64) - if (byteLength > 4096) - goto PInvoke; - Unsafe.InitBlockUnaligned(ref b, 0, (uint)byteLength); - return; -#else - // TODO: Optimize other platforms to be on par with AMD64 CoreCLR - // Note: It's important that this switch handles lengths at least up to 22. - // See notes below near the main loop for why. - - // The switch will be very fast since it can be implemented using a jump - // table in assembly. See http://stackoverflow.com/a/449297/4077294 for more info. - - switch (byteLength) - { - case 1: - b = 0; - return; - case 2: - Unsafe.As<byte, short>(ref b) = 0; - return; - case 3: - Unsafe.As<byte, short>(ref b) = 0; - Unsafe.Add<byte>(ref b, 2) = 0; - return; - case 4: - Unsafe.As<byte, int>(ref b) = 0; - return; - case 5: - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.Add<byte>(ref b, 4) = 0; - return; - case 6: - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 4)) = 0; - return; - case 7: - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 4)) = 0; - Unsafe.Add<byte>(ref b, 6) = 0; - return; - case 8: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; -#endif - return; - case 9: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; -#endif - Unsafe.Add<byte>(ref b, 8) = 0; - return; - case 10: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; -#endif - Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - return; - case 11: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; -#endif - Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - Unsafe.Add<byte>(ref b, 10) = 0; - return; - case 12: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; -#endif - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - return; - case 13: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; -#endif - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - Unsafe.Add<byte>(ref b, 12) = 0; - return; - case 14: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; -#endif - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 12)) = 0; - return; - case 15: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; -#endif - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 12)) = 0; - Unsafe.Add<byte>(ref b, 14) = 0; - return; - case 16: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; - Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; -#endif - return; - case 17: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; - Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; -#endif - Unsafe.Add<byte>(ref b, 16) = 0; - return; - case 18: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; - Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; -#endif - Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 16)) = 0; - return; - case 19: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; - Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; -#endif - Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 16)) = 0; - Unsafe.Add<byte>(ref b, 18) = 0; - return; - case 20: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; - Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; -#endif - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 16)) = 0; - return; - case 21: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; - Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; -#endif - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 16)) = 0; - Unsafe.Add<byte>(ref b, 20) = 0; - return; - case 22: -#if BIT64 - Unsafe.As<byte, long>(ref b) = 0; - Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; -#else - Unsafe.As<byte, int>(ref b) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; -#endif - Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 16)) = 0; - Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 20)) = 0; - return; - } - - // P/Invoke into the native version for large lengths - if (byteLength >= 512) goto PInvoke; - - nuint i = 0; // byte offset at which we're copying - - if ((Unsafe.As<byte, int>(ref b) & 3) != 0) - { - if ((Unsafe.As<byte, int>(ref b) & 1) != 0) - { - Unsafe.AddByteOffset<byte>(ref b, i) = 0; - i += 1; - if ((Unsafe.As<byte, int>(ref b) & 2) != 0) - goto IntAligned; - } - Unsafe.As<byte, short>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; - i += 2; - } - - IntAligned: - - // On 64-bit IntPtr.Size == 8, so we want to advance to the next 8-aligned address. If - // (int)b % 8 is 0, 5, 6, or 7, we will already have advanced by 0, 3, 2, or 1 - // bytes to the next aligned address (respectively), so do nothing. On the other hand, - // if it is 1, 2, 3, or 4 we will want to copy-and-advance another 4 bytes until - // we're aligned. - // The thing 1, 2, 3, and 4 have in common that the others don't is that if you - // subtract one from them, their 3rd lsb will not be set. Hence, the below check. - - if (((Unsafe.As<byte, int>(ref b) - 1) & 4) == 0) - { - Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; - i += 4; - } - - nuint end = byteLength - 16; - byteLength -= i; // lower 4 bits of byteLength represent how many bytes are left *after* the unrolled loop - - // We know due to the above switch-case that this loop will always run 1 iteration; max - // bytes we clear before checking is 23 (7 to align the pointers, 16 for 1 iteration) so - // the switch handles lengths 0-22. - Debug.Assert(end >= 7 && i <= end); - - // This is separated out into a different variable, so the i + 16 addition can be - // performed at the start of the pipeline and the loop condition does not have - // a dependency on the writes. - nuint counter; - - do - { - counter = i + 16; - - // This loop looks very costly since there appear to be a bunch of temporary values - // being created with the adds, but the jit (for x86 anyways) will convert each of - // these to use memory addressing operands. - - // So the only cost is a bit of code size, which is made up for by the fact that - // we save on writes to b. - -#if BIT64 - Unsafe.As<byte, long>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; - Unsafe.As<byte, long>(ref Unsafe.AddByteOffset<byte>(ref b, i + 8)) = 0; -#else - Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; - Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i + 4)) = 0; - Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i + 8)) = 0; - Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i + 12)) = 0; -#endif - - i = counter; - - // See notes above for why this wasn't used instead - // i += 16; - } - while (counter <= end); - - if ((byteLength & 8) != 0) - { -#if BIT64 - Unsafe.As<byte, long>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; -#else - Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; - Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i + 4)) = 0; -#endif - i += 8; - } - if ((byteLength & 4) != 0) - { - Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; - i += 4; - } - if ((byteLength & 2) != 0) - { - Unsafe.As<byte, short>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; - i += 2; - } - if ((byteLength & 1) != 0) - { - Unsafe.AddByteOffset<byte>(ref b, i) = 0; - // We're not using i after this, so not needed - // i += 1; - } - - return; -#endif - - PInvoke: - RuntimeImports.RhZeroMemory(ref b, byteLength); - } - - internal static unsafe void ClearWithReferences(ref IntPtr ip, nuint pointerSizeLength) - { - if (pointerSizeLength == 0) - return; - - // TODO: Perhaps do switch casing to improve small size perf + public static ReadOnlySpan<char> AsReadOnlySpan(this string text) => text.AsSpan(); + public static ReadOnlySpan<char> AsReadOnlySpan(this string text, int start) => text.AsSpan(start); + public static ReadOnlySpan<char> AsReadOnlySpan(this string text, int start, int length) => text.AsSpan(start, length); - nuint i = 0; - nuint n = 0; - while ((n = i + 8) <= (pointerSizeLength)) - { - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 0) * (nuint)sizeof(IntPtr)) = default(IntPtr); - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 1) * (nuint)sizeof(IntPtr)) = default(IntPtr); - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 2) * (nuint)sizeof(IntPtr)) = default(IntPtr); - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 3) * (nuint)sizeof(IntPtr)) = default(IntPtr); - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 4) * (nuint)sizeof(IntPtr)) = default(IntPtr); - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 5) * (nuint)sizeof(IntPtr)) = default(IntPtr); - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 6) * (nuint)sizeof(IntPtr)) = default(IntPtr); - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 7) * (nuint)sizeof(IntPtr)) = default(IntPtr); - i = n; - } - if ((n = i + 4) <= (pointerSizeLength)) - { - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 0) * (nuint)sizeof(IntPtr)) = default(IntPtr); - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 1) * (nuint)sizeof(IntPtr)) = default(IntPtr); - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 2) * (nuint)sizeof(IntPtr)) = default(IntPtr); - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 3) * (nuint)sizeof(IntPtr)) = default(IntPtr); - i = n; - } - if ((n = i + 2) <= (pointerSizeLength)) - { - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 0) * (nuint)sizeof(IntPtr)) = default(IntPtr); - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 1) * (nuint)sizeof(IntPtr)) = default(IntPtr); - i = n; - } - if ((i + 1) <= (pointerSizeLength)) - { - Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 0) * (nuint)sizeof(IntPtr)) = default(IntPtr); - } - } + public static ReadOnlyMemory<char> AsReadOnlyMemory(this string text) => text.AsMemory(); + public static ReadOnlyMemory<char> AsReadOnlyMemory(this string text, int start) => text.AsMemory(start); + public static ReadOnlyMemory<char> AsReadOnlyMemory(this string text, int start, int length) => text.AsMemory(start, length); } } diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.BinarySearch.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.BinarySearch.cs new file mode 100644 index 000000000..656b864e2 --- /dev/null +++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.BinarySearch.cs @@ -0,0 +1,83 @@ +// 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.Collections.Generic; +using System.Runtime.CompilerServices; +using System.Runtime.InteropServices; + +#if !netstandard +using Internal.Runtime.CompilerServices; +#endif + +namespace System +{ + internal static partial class SpanHelpers + { + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public static int BinarySearch<T, TComparable>( + this ReadOnlySpan<T> span, TComparable comparable) + where TComparable : IComparable<T> + { + if (comparable == null) + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.comparable); + + return BinarySearch(ref MemoryMarshal.GetReference(span), span.Length, comparable); + } + + public static int BinarySearch<T, TComparable>( + ref T spanStart, int length, TComparable comparable) + where TComparable : IComparable<T> + { + int lo = 0; + int hi = length - 1; + // If length == 0, hi == -1, and loop will not be entered + while (lo <= hi) + { + // PERF: `lo` or `hi` will never be negative inside the loop, + // so computing median using uints is safe since we know + // `length <= int.MaxValue`, and indices are >= 0 + // and thus cannot overflow an uint. + // Saves one subtraction per loop compared to + // `int i = lo + ((hi - lo) >> 1);` + int i = (int)(((uint)hi + (uint)lo) >> 1); + + int c = comparable.CompareTo(Unsafe.Add(ref spanStart, i)); + if (c == 0) + { + return i; + } + else if (c > 0) + { + lo = i + 1; + } + else + { + hi = i - 1; + } + } + // If none found, then a negative number that is the bitwise complement + // of the index of the next element that is larger than or, if there is + // no larger element, the bitwise complement of `length`, which + // is `lo` at this point. + return ~lo; + } + + // Helper to allow sharing all code via IComparable<T> inlineable + internal struct ComparerComparable<T, TComparer> : IComparable<T> + where TComparer : IComparer<T> + { + readonly T _value; + readonly TComparer _comparer; + + public ComparerComparable(T value, TComparer comparer) + { + _value = value; + _comparer = comparer; + } + + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public int CompareTo(T other) => _comparer.Compare(_value, other); + } + } +} diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.Byte.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.Byte.cs new file mode 100644 index 000000000..860b2efa0 --- /dev/null +++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.Byte.cs @@ -0,0 +1,1104 @@ +// 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; + +#if !netstandard +using Internal.Runtime.CompilerServices; +#endif + +#if !netstandard11 +using System.Numerics; +#endif + +namespace System +{ + internal static partial class SpanHelpers + { + public static int IndexOf(ref byte searchSpace, int searchSpaceLength, ref byte value, int valueLength) + { + Debug.Assert(searchSpaceLength >= 0); + Debug.Assert(valueLength >= 0); + + if (valueLength == 0) + return 0; // A zero-length sequence is always treated as "found" at the start of the search space. + + byte valueHead = value; + ref byte valueTail = ref Unsafe.Add(ref value, 1); + int valueTailLength = valueLength - 1; + + int index = 0; + for (; ; ) + { + Debug.Assert(0 <= index && index <= searchSpaceLength); // Ensures no deceptive underflows in the computation of "remainingSearchSpaceLength". + int remainingSearchSpaceLength = searchSpaceLength - index - valueTailLength; + if (remainingSearchSpaceLength <= 0) + break; // The unsearched portion is now shorter than the sequence we're looking for. So it can't be there. + + // Do a quick search for the first element of "value". + int relativeIndex = IndexOf(ref Unsafe.Add(ref searchSpace, index), valueHead, remainingSearchSpaceLength); + if (relativeIndex == -1) + break; + index += relativeIndex; + + // Found the first element of "value". See if the tail matches. + if (SequenceEqual(ref Unsafe.Add(ref searchSpace, index + 1), ref valueTail, valueTailLength)) + return index; // The tail matched. Return a successful find. + + index++; + } + return -1; + } + + public static int IndexOfAny(ref byte searchSpace, int searchSpaceLength, ref byte value, int valueLength) + { + Debug.Assert(searchSpaceLength >= 0); + Debug.Assert(valueLength >= 0); + + if (valueLength == 0) + return 0; // A zero-length sequence is always treated as "found" at the start of the search space. + + int index = -1; + for (int i = 0; i < valueLength; i++) + { + var tempIndex = IndexOf(ref searchSpace, Unsafe.Add(ref value, i), searchSpaceLength); + if ((uint)tempIndex < (uint)index) + { + index = tempIndex; + // Reduce space for search, cause we don't care if we find the search value after the index of a previously found value + searchSpaceLength = tempIndex; + + if (index == 0) break; + } + } + return index; + } + + public static int LastIndexOfAny(ref byte searchSpace, int searchSpaceLength, ref byte value, int valueLength) + { + Debug.Assert(searchSpaceLength >= 0); + Debug.Assert(valueLength >= 0); + + if (valueLength == 0) + return 0; // A zero-length sequence is always treated as "found" at the start of the search space. + + int index = -1; + for (int i = 0; i < valueLength; i++) + { + var tempIndex = LastIndexOf(ref searchSpace, Unsafe.Add(ref value, i), searchSpaceLength); + if (tempIndex > index) index = tempIndex; + } + return index; + } + + public static unsafe int IndexOf(ref byte searchSpace, byte value, int length) + { + Debug.Assert(length >= 0); + + uint uValue = value; // Use uint for comparisons to avoid unnecessary 8->32 extensions + IntPtr index = (IntPtr)0; // Use UIntPtr for arithmetic to avoid unnecessary 64->32->64 truncations + IntPtr nLength = (IntPtr)(uint)length; +#if !netstandard11 + if (Vector.IsHardwareAccelerated && length >= Vector<byte>.Count * 2) + { + unchecked + { + int unaligned = (int)(byte*)Unsafe.AsPointer(ref searchSpace) & (Vector<byte>.Count - 1); + nLength = (IntPtr)(uint)((Vector<byte>.Count - unaligned) & (Vector<byte>.Count - 1)); + } + } + SequentialScan: +#endif + while ((byte*)nLength >= (byte*)8) + { + nLength -= 8; + + if (uValue == Unsafe.Add(ref searchSpace, index)) + goto Found; + if (uValue == Unsafe.Add(ref searchSpace, index + 1)) + goto Found1; + if (uValue == Unsafe.Add(ref searchSpace, index + 2)) + goto Found2; + if (uValue == Unsafe.Add(ref searchSpace, index + 3)) + goto Found3; + if (uValue == Unsafe.Add(ref searchSpace, index + 4)) + goto Found4; + if (uValue == Unsafe.Add(ref searchSpace, index + 5)) + goto Found5; + if (uValue == Unsafe.Add(ref searchSpace, index + 6)) + goto Found6; + if (uValue == Unsafe.Add(ref searchSpace, index + 7)) + goto Found7; + + index += 8; + } + + if ((byte*)nLength >= (byte*)4) + { + nLength -= 4; + + if (uValue == Unsafe.Add(ref searchSpace, index)) + goto Found; + if (uValue == Unsafe.Add(ref searchSpace, index + 1)) + goto Found1; + if (uValue == Unsafe.Add(ref searchSpace, index + 2)) + goto Found2; + if (uValue == Unsafe.Add(ref searchSpace, index + 3)) + goto Found3; + + index += 4; + } + + while ((byte*)nLength > (byte*)0) + { + nLength -= 1; + + if (uValue == Unsafe.Add(ref searchSpace, index)) + goto Found; + + index += 1; + } +#if !netstandard11 + if (Vector.IsHardwareAccelerated && ((int)(byte*)index < length)) + { + nLength = (IntPtr)(uint)((length - (uint)index) & ~(Vector<byte>.Count - 1)); + // Get comparison Vector + Vector<byte> vComparison = GetVector(value); + while ((byte*)nLength > (byte*)index) + { + var vMatches = Vector.Equals(vComparison, Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref searchSpace, index))); + if (Vector<byte>.Zero.Equals(vMatches)) + { + index += Vector<byte>.Count; + continue; + } + // Find offset of first match + return (int)(byte*)index + LocateFirstFoundByte(vMatches); + } + + if ((int)(byte*)index < length) + { + unchecked + { + nLength = (IntPtr)(length - (int)(byte*)index); + } + goto SequentialScan; + } + } +#endif + return -1; + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return (int)(byte*)index; + Found1: + return (int)(byte*)(index + 1); + Found2: + return (int)(byte*)(index + 2); + Found3: + return (int)(byte*)(index + 3); + Found4: + return (int)(byte*)(index + 4); + Found5: + return (int)(byte*)(index + 5); + Found6: + return (int)(byte*)(index + 6); + Found7: + return (int)(byte*)(index + 7); + } + + public static int LastIndexOf(ref byte searchSpace, int searchSpaceLength, ref byte value, int valueLength) + { + Debug.Assert(searchSpaceLength >= 0); + Debug.Assert(valueLength >= 0); + + if (valueLength == 0) + return 0; // A zero-length sequence is always treated as "found" at the start of the search space. + + byte valueHead = value; + ref byte valueTail = ref Unsafe.Add(ref value, 1); + int valueTailLength = valueLength - 1; + + int index = 0; + for (; ; ) + { + Debug.Assert(0 <= index && index <= searchSpaceLength); // Ensures no deceptive underflows in the computation of "remainingSearchSpaceLength". + int remainingSearchSpaceLength = searchSpaceLength - index - valueTailLength; + if (remainingSearchSpaceLength <= 0) + break; // The unsearched portion is now shorter than the sequence we're looking for. So it can't be there. + + // Do a quick search for the first element of "value". + int relativeIndex = LastIndexOf(ref searchSpace, valueHead, remainingSearchSpaceLength); + if (relativeIndex == -1) + break; + + // Found the first element of "value". See if the tail matches. + if (SequenceEqual(ref Unsafe.Add(ref searchSpace, relativeIndex + 1), ref valueTail, valueTailLength)) + return relativeIndex; // The tail matched. Return a successful find. + + index += remainingSearchSpaceLength - relativeIndex; + } + return -1; + } + + public static unsafe int LastIndexOf(ref byte searchSpace, byte value, int length) + { + Debug.Assert(length >= 0); + + uint uValue = value; // Use uint for comparisons to avoid unnecessary 8->32 extensions + IntPtr index = (IntPtr)(uint)length; // Use UIntPtr for arithmetic to avoid unnecessary 64->32->64 truncations + IntPtr nLength = (IntPtr)(uint)length; +#if !netstandard11 + if (Vector.IsHardwareAccelerated && length >= Vector<byte>.Count * 2) + { + unchecked + { + int unaligned = (int)(byte*)Unsafe.AsPointer(ref searchSpace) & (Vector<byte>.Count - 1); + nLength = (IntPtr)(((length & (Vector<byte>.Count - 1)) + unaligned) & (Vector<byte>.Count - 1)); + } + } + SequentialScan: +#endif + while ((byte*)nLength >= (byte*)8) + { + nLength -= 8; + index -= 8; + + if (uValue == Unsafe.Add(ref searchSpace, index + 7)) + goto Found7; + if (uValue == Unsafe.Add(ref searchSpace, index + 6)) + goto Found6; + if (uValue == Unsafe.Add(ref searchSpace, index + 5)) + goto Found5; + if (uValue == Unsafe.Add(ref searchSpace, index + 4)) + goto Found4; + if (uValue == Unsafe.Add(ref searchSpace, index + 3)) + goto Found3; + if (uValue == Unsafe.Add(ref searchSpace, index + 2)) + goto Found2; + if (uValue == Unsafe.Add(ref searchSpace, index + 1)) + goto Found1; + if (uValue == Unsafe.Add(ref searchSpace, index)) + goto Found; + } + + if ((byte*)nLength >= (byte*)4) + { + nLength -= 4; + index -= 4; + + if (uValue == Unsafe.Add(ref searchSpace, index + 3)) + goto Found3; + if (uValue == Unsafe.Add(ref searchSpace, index + 2)) + goto Found2; + if (uValue == Unsafe.Add(ref searchSpace, index + 1)) + goto Found1; + if (uValue == Unsafe.Add(ref searchSpace, index)) + goto Found; + } + + while ((byte*)nLength > (byte*)0) + { + nLength -= 1; + index -= 1; + + if (uValue == Unsafe.Add(ref searchSpace, index)) + goto Found; + } +#if !netstandard11 + if (Vector.IsHardwareAccelerated && ((int)(byte*)index > 0)) + { + nLength = (IntPtr)(uint)((uint)index & ~(Vector<byte>.Count - 1)); + + // Get comparison Vector + Vector<byte> vComparison = GetVector(value); + while ((byte*)nLength > (byte*)(Vector<byte>.Count - 1)) + { + var vMatches = Vector.Equals(vComparison, Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref searchSpace, index - Vector<byte>.Count))); + if (Vector<byte>.Zero.Equals(vMatches)) + { + index -= Vector<byte>.Count; + nLength -= Vector<byte>.Count; + continue; + } + // Find offset of first match + return (int)(byte*)(index) - Vector<byte>.Count + LocateLastFoundByte(vMatches); + } + if ((int)(byte*)index > 0) + { + nLength = index; + goto SequentialScan; + } + } +#endif + return -1; + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return (int)(byte*)index; + Found1: + return (int)(byte*)(index + 1); + Found2: + return (int)(byte*)(index + 2); + Found3: + return (int)(byte*)(index + 3); + Found4: + return (int)(byte*)(index + 4); + Found5: + return (int)(byte*)(index + 5); + Found6: + return (int)(byte*)(index + 6); + Found7: + return (int)(byte*)(index + 7); + } + + public static unsafe int IndexOfAny(ref byte searchSpace, byte value0, byte value1, int length) + { + Debug.Assert(length >= 0); + + uint uValue0 = value0; // Use uint for comparisons to avoid unnecessary 8->32 extensions + uint uValue1 = value1; // Use uint for comparisons to avoid unnecessary 8->32 extensions + IntPtr index = (IntPtr)0; // Use UIntPtr for arithmetic to avoid unnecessary 64->32->64 truncations + IntPtr nLength = (IntPtr)(uint)length; +#if !netstandard11 + if (Vector.IsHardwareAccelerated && length >= Vector<byte>.Count * 2) + { + unchecked + { + int unaligned = (int)(byte*)Unsafe.AsPointer(ref searchSpace) & (Vector<byte>.Count - 1); + nLength = (IntPtr)(uint)((Vector<byte>.Count - unaligned) & (Vector<byte>.Count - 1)); + } + } + SequentialScan: +#endif + uint lookUp; + while ((byte*)nLength >= (byte*)8) + { + nLength -= 8; + + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, index + 4); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found4; + lookUp = Unsafe.Add(ref searchSpace, index + 5); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found5; + lookUp = Unsafe.Add(ref searchSpace, index + 6); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found6; + lookUp = Unsafe.Add(ref searchSpace, index + 7); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found7; + + index += 8; + } + + if ((byte*)nLength >= (byte*)4) + { + nLength -= 4; + + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found3; + + index += 4; + } + + while ((byte*)nLength > (byte*)0) + { + nLength -= 1; + + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found; + + index += 1; + } +#if !netstandard11 + if (Vector.IsHardwareAccelerated && ((int)(byte*)index < length)) + { + nLength = (IntPtr)(uint)((length - (uint)index) & ~(Vector<byte>.Count - 1)); + // Get comparison Vector + Vector<byte> values0 = GetVector(value0); + Vector<byte> values1 = GetVector(value1); + + while ((byte*)nLength > (byte*)index) + { + Vector<byte> vData = Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref searchSpace, index)); + var vMatches = Vector.BitwiseOr( + Vector.Equals(vData, values0), + Vector.Equals(vData, values1)); + if (Vector<byte>.Zero.Equals(vMatches)) + { + index += Vector<byte>.Count; + continue; + } + // Find offset of first match + return (int)(byte*)index + LocateFirstFoundByte(vMatches); + } + + if ((int)(byte*)index < length) + { + unchecked + { + nLength = (IntPtr)(length - (int)(byte*)index); + } + goto SequentialScan; + } + } +#endif + return -1; + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return (int)(byte*)index; + Found1: + return (int)(byte*)(index + 1); + Found2: + return (int)(byte*)(index + 2); + Found3: + return (int)(byte*)(index + 3); + Found4: + return (int)(byte*)(index + 4); + Found5: + return (int)(byte*)(index + 5); + Found6: + return (int)(byte*)(index + 6); + Found7: + return (int)(byte*)(index + 7); + } + + public static unsafe int IndexOfAny(ref byte searchSpace, byte value0, byte value1, byte value2, int length) + { + Debug.Assert(length >= 0); + + uint uValue0 = value0; // Use uint for comparisons to avoid unnecessary 8->32 extensions + uint uValue1 = value1; // Use uint for comparisons to avoid unnecessary 8->32 extensions + uint uValue2 = value2; // Use uint for comparisons to avoid unnecessary 8->32 extensions + IntPtr index = (IntPtr)0; // Use UIntPtr for arithmetic to avoid unnecessary 64->32->64 truncations + IntPtr nLength = (IntPtr)(uint)length; +#if !netstandard11 + if (Vector.IsHardwareAccelerated && length >= Vector<byte>.Count * 2) + { + unchecked + { + int unaligned = (int)(byte*)Unsafe.AsPointer(ref searchSpace) & (Vector<byte>.Count - 1); + nLength = (IntPtr)(uint)((Vector<byte>.Count - unaligned) & (Vector<byte>.Count - 1)); + } + } + SequentialScan: +#endif + uint lookUp; + while ((byte*)nLength >= (byte*)8) + { + nLength -= 8; + + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, index + 4); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found4; + lookUp = Unsafe.Add(ref searchSpace, index + 5); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found5; + lookUp = Unsafe.Add(ref searchSpace, index + 6); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found6; + lookUp = Unsafe.Add(ref searchSpace, index + 7); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found7; + + index += 8; + } + + if ((byte*)nLength >= (byte*)4) + { + nLength -= 4; + + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found3; + + index += 4; + } + + while ((byte*)nLength > (byte*)0) + { + nLength -= 1; + + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found; + + index += 1; + } +#if !netstandard11 + if (Vector.IsHardwareAccelerated && ((int)(byte*)index < length)) + { + nLength = (IntPtr)(uint)((length - (uint)index) & ~(Vector<byte>.Count - 1)); + // Get comparison Vector + Vector<byte> values0 = GetVector(value0); + Vector<byte> values1 = GetVector(value1); + Vector<byte> values2 = GetVector(value2); + while ((byte*)nLength > (byte*)index) + { + Vector<byte> vData = Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref searchSpace, index)); + + var vMatches = Vector.BitwiseOr( + Vector.BitwiseOr( + Vector.Equals(vData, values0), + Vector.Equals(vData, values1)), + Vector.Equals(vData, values2)); + + if (Vector<byte>.Zero.Equals(vMatches)) + { + index += Vector<byte>.Count; + continue; + } + // Find offset of first match + return (int)(byte*)index + LocateFirstFoundByte(vMatches); + } + + if ((int)(byte*)index < length) + { + unchecked + { + nLength = (IntPtr)(length - (int)(byte*)index); + } + goto SequentialScan; + } + } +#endif + return -1; + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return (int)(byte*)index; + Found1: + return (int)(byte*)(index + 1); + Found2: + return (int)(byte*)(index + 2); + Found3: + return (int)(byte*)(index + 3); + Found4: + return (int)(byte*)(index + 4); + Found5: + return (int)(byte*)(index + 5); + Found6: + return (int)(byte*)(index + 6); + Found7: + return (int)(byte*)(index + 7); + } + + public static unsafe int LastIndexOfAny(ref byte searchSpace, byte value0, byte value1, int length) + { + Debug.Assert(length >= 0); + + uint uValue0 = value0; // Use uint for comparisons to avoid unnecessary 8->32 extensions + uint uValue1 = value1; // Use uint for comparisons to avoid unnecessary 8->32 extensions + IntPtr index = (IntPtr)(uint)length; // Use UIntPtr for arithmetic to avoid unnecessary 64->32->64 truncations + IntPtr nLength = (IntPtr)(uint)length; +#if !netstandard11 + if (Vector.IsHardwareAccelerated && length >= Vector<byte>.Count * 2) + { + unchecked + { + int unaligned = (int)(byte*)Unsafe.AsPointer(ref searchSpace) & (Vector<byte>.Count - 1); + nLength = (IntPtr)(((length & (Vector<byte>.Count - 1)) + unaligned) & (Vector<byte>.Count - 1)); + } + } + SequentialScan: +#endif + uint lookUp; + while ((byte*)nLength >= (byte*)8) + { + nLength -= 8; + index -= 8; + + lookUp = Unsafe.Add(ref searchSpace, index + 7); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found7; + lookUp = Unsafe.Add(ref searchSpace, index + 6); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found6; + lookUp = Unsafe.Add(ref searchSpace, index + 5); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found5; + lookUp = Unsafe.Add(ref searchSpace, index + 4); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found4; + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found; + } + + if ((byte*)nLength >= (byte*)4) + { + nLength -= 4; + index -= 4; + + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found; + } + + while ((byte*)nLength > (byte*)0) + { + nLength -= 1; + index -= 1; + + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp) + goto Found; + } +#if !netstandard11 + if (Vector.IsHardwareAccelerated && ((int)(byte*)index > 0)) + { + nLength = (IntPtr)(uint)((uint)index & ~(Vector<byte>.Count - 1)); + // Get comparison Vector + Vector<byte> values0 = GetVector(value0); + Vector<byte> values1 = GetVector(value1); + + while ((byte*)nLength > (byte*)(Vector<byte>.Count - 1)) + { + Vector<byte> vData = Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref searchSpace, index - Vector<byte>.Count)); + var vMatches = Vector.BitwiseOr( + Vector.Equals(vData, values0), + Vector.Equals(vData, values1)); + if (Vector<byte>.Zero.Equals(vMatches)) + { + index -= Vector<byte>.Count; + nLength -= Vector<byte>.Count; + continue; + } + // Find offset of first match + return (int)(byte*)(index) - Vector<byte>.Count + LocateLastFoundByte(vMatches); + } + + if ((int)(byte*)index > 0) + { + nLength = index; + goto SequentialScan; + } + } +#endif + return -1; + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return (int)(byte*)index; + Found1: + return (int)(byte*)(index + 1); + Found2: + return (int)(byte*)(index + 2); + Found3: + return (int)(byte*)(index + 3); + Found4: + return (int)(byte*)(index + 4); + Found5: + return (int)(byte*)(index + 5); + Found6: + return (int)(byte*)(index + 6); + Found7: + return (int)(byte*)(index + 7); + } + + public static unsafe int LastIndexOfAny(ref byte searchSpace, byte value0, byte value1, byte value2, int length) + { + Debug.Assert(length >= 0); + + uint uValue0 = value0; // Use uint for comparisons to avoid unnecessary 8->32 extensions + uint uValue1 = value1; // Use uint for comparisons to avoid unnecessary 8->32 extensions + uint uValue2 = value2; // Use uint for comparisons to avoid unnecessary 8->32 extensions + IntPtr index = (IntPtr)(uint)length; // Use UIntPtr for arithmetic to avoid unnecessary 64->32->64 truncations + IntPtr nLength = (IntPtr)(uint)length; +#if !netstandard11 + if (Vector.IsHardwareAccelerated && length >= Vector<byte>.Count * 2) + { + unchecked + { + int unaligned = (int)(byte*)Unsafe.AsPointer(ref searchSpace) & (Vector<byte>.Count - 1); + nLength = (IntPtr)(((length & (Vector<byte>.Count - 1)) + unaligned) & (Vector<byte>.Count - 1)); + } + } + SequentialScan: +#endif + uint lookUp; + while ((byte*)nLength >= (byte*)8) + { + nLength -= 8; + index -= 8; + + lookUp = Unsafe.Add(ref searchSpace, index + 7); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found7; + lookUp = Unsafe.Add(ref searchSpace, index + 6); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found6; + lookUp = Unsafe.Add(ref searchSpace, index + 5); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found5; + lookUp = Unsafe.Add(ref searchSpace, index + 4); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found4; + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found; + } + + if ((byte*)nLength >= (byte*)4) + { + nLength -= 4; + index -= 4; + + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found; + } + + while ((byte*)nLength > (byte*)0) + { + nLength -= 1; + index -= 1; + + lookUp = Unsafe.Add(ref searchSpace, index); + if (uValue0 == lookUp || uValue1 == lookUp || uValue2 == lookUp) + goto Found; + } +#if !netstandard11 + if (Vector.IsHardwareAccelerated && ((int)(byte*)index > 0)) + { + nLength = (IntPtr)(uint)((uint)index & ~(Vector<byte>.Count - 1)); + // Get comparison Vector + Vector<byte> values0 = GetVector(value0); + Vector<byte> values1 = GetVector(value1); + Vector<byte> values2 = GetVector(value2); + while ((byte*)nLength > (byte*)(Vector<byte>.Count - 1)) + { + Vector<byte> vData = Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref searchSpace, index - Vector<byte>.Count)); + + var vMatches = Vector.BitwiseOr( + Vector.BitwiseOr( + Vector.Equals(vData, values0), + Vector.Equals(vData, values1)), + Vector.Equals(vData, values2)); + + if (Vector<byte>.Zero.Equals(vMatches)) + { + index -= Vector<byte>.Count; + nLength -= Vector<byte>.Count; + continue; + } + // Find offset of first match + return (int)(byte*)(index) - Vector<byte>.Count + LocateLastFoundByte(vMatches); + } + + if ((int)(byte*)index > 0) + { + nLength = index; + goto SequentialScan; + } + } +#endif + return -1; + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return (int)(byte*)index; + Found1: + return (int)(byte*)(index + 1); + Found2: + return (int)(byte*)(index + 2); + Found3: + return (int)(byte*)(index + 3); + Found4: + return (int)(byte*)(index + 4); + Found5: + return (int)(byte*)(index + 5); + Found6: + return (int)(byte*)(index + 6); + Found7: + return (int)(byte*)(index + 7); + } + + public static unsafe bool SequenceEqual(ref byte first, ref byte second, int length) + { + Debug.Assert(length >= 0); + + if (Unsafe.AreSame(ref first, ref second)) + goto Equal; + + IntPtr i = (IntPtr)0; // Use IntPtr and byte* for arithmetic to avoid unnecessary 64->32->64 truncations + IntPtr n = (IntPtr)length; + +#if !netstandard11 + if (Vector.IsHardwareAccelerated && (byte*)n >= (byte*)Vector<byte>.Count) + { + n -= Vector<byte>.Count; + while ((byte*)n > (byte*)i) + { + if (Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref first, i)) != + Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref second, i))) + { + goto NotEqual; + } + i += Vector<byte>.Count; + } + return Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref first, n)) == + Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref second, n)); + } +#endif + + if ((byte*)n >= (byte*)sizeof(UIntPtr)) + { + n -= sizeof(UIntPtr); + while ((byte*)n > (byte*)i) + { + if (Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.AddByteOffset(ref first, i)) != + Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.AddByteOffset(ref second, i))) + { + goto NotEqual; + } + i += sizeof(UIntPtr); + } + return Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.AddByteOffset(ref first, n)) == + Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.AddByteOffset(ref second, n)); + } + + while ((byte*)n > (byte*)i) + { + if (Unsafe.AddByteOffset(ref first, i) != Unsafe.AddByteOffset(ref second, i)) + goto NotEqual; + i += 1; + } + + Equal: + return true; + + NotEqual: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return false; + } + +#if !netstandard11 + // Vector sub-search adapted from https://github.com/aspnet/KestrelHttpServer/pull/1138 + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static int LocateFirstFoundByte(Vector<byte> 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 * 8 + LocateFirstFoundByte(candidate); + } +#endif + + public static unsafe int SequenceCompareTo(ref byte first, int firstLength, ref byte second, int secondLength) + { + Debug.Assert(firstLength >= 0); + Debug.Assert(secondLength >= 0); + + if (Unsafe.AreSame(ref first, ref second)) + goto Equal; + + var minLength = firstLength; + if (minLength > secondLength) minLength = secondLength; + + IntPtr i = (IntPtr)0; // Use IntPtr and byte* for arithmetic to avoid unnecessary 64->32->64 truncations + IntPtr n = (IntPtr)minLength; + +#if !netstandard11 + if (Vector.IsHardwareAccelerated && (byte*)n > (byte*)Vector<byte>.Count) + { + n -= Vector<byte>.Count; + while ((byte*)n > (byte*)i) + { + if (Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref first, i)) != + Unsafe.ReadUnaligned<Vector<byte>>(ref Unsafe.AddByteOffset(ref second, i))) + { + goto NotEqual; + } + i += Vector<byte>.Count; + } + goto NotEqual; + } +#endif + + if ((byte*)n > (byte*)sizeof(UIntPtr)) + { + n -= sizeof(UIntPtr); + while ((byte*)n > (byte*)i) + { + if (Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.AddByteOffset(ref first, i)) != + Unsafe.ReadUnaligned<UIntPtr>(ref Unsafe.AddByteOffset(ref second, i))) + { + goto NotEqual; + } + i += sizeof(UIntPtr); + } + } + + NotEqual: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + while((byte*)minLength > (byte*)i) + { + int result = Unsafe.AddByteOffset(ref first, i).CompareTo(Unsafe.AddByteOffset(ref second, i)); + if (result != 0) return result; + i += 1; + } + + Equal: + return firstLength - secondLength; + } + +#if !netstandard11 + // Vector sub-search adapted from https://github.com/aspnet/KestrelHttpServer/pull/1138 + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static int LocateLastFoundByte(Vector<byte> 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 * 8 + LocateLastFoundByte(candidate); + } +#endif + +#if !netstandard11 + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static int LocateFirstFoundByte(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 * XorPowerOfTwoToHighByte) >> 57); + } + } +#endif + +#if !netstandard11 + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static int LocateLastFoundByte(ulong match) + { + // Find the most significant byte that has its highest bit set + int index = 7; + while ((long)match > 0) + { + match = match << 8; + index--; + } + return index; + } +#endif + +#if !netstandard11 + [MethodImpl(MethodImplOptions.AggressiveInlining)] + private static Vector<byte> GetVector(byte vectorByte) + { +#if !netcoreapp + // Vector<byte> .ctor doesn't become an intrinsic due to detection issue + // However this does cause it to become an intrinsic (with additional multiply and reg->reg copy) + // https://github.com/dotnet/coreclr/issues/7459#issuecomment-253965670 + return Vector.AsVectorByte(new Vector<uint>(vectorByte * 0x01010101u)); +#else + return new Vector<byte>(vectorByte); +#endif + } +#endif + +#if !netstandard11 + private const ulong XorPowerOfTwoToHighByte = (0x07ul | + 0x06ul << 8 | + 0x05ul << 16 | + 0x04ul << 24 | + 0x03ul << 32 | + 0x02ul << 40 | + 0x01ul << 48) + 1; +#endif + } +} diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.T.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.T.cs new file mode 100644 index 000000000..d1c62c8d5 --- /dev/null +++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.T.cs @@ -0,0 +1,683 @@ +// 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; + +#if !netstandard +using Internal.Runtime.CompilerServices; +#else +using System.Runtime.CompilerServices; +#endif + +namespace System +{ + internal static partial class SpanHelpers + { + public static int IndexOf<T>(ref T searchSpace, int searchSpaceLength, ref T value, int valueLength) + where T : IEquatable<T> + { + Debug.Assert(searchSpaceLength >= 0); + Debug.Assert(valueLength >= 0); + + if (valueLength == 0) + return 0; // A zero-length sequence is always treated as "found" at the start of the search space. + + T valueHead = value; + ref T valueTail = ref Unsafe.Add(ref value, 1); + int valueTailLength = valueLength - 1; + + int index = 0; + for (; ; ) + { + Debug.Assert(0 <= index && index <= searchSpaceLength); // Ensures no deceptive underflows in the computation of "remainingSearchSpaceLength". + int remainingSearchSpaceLength = searchSpaceLength - index - valueTailLength; + if (remainingSearchSpaceLength <= 0) + break; // The unsearched portion is now shorter than the sequence we're looking for. So it can't be there. + + // Do a quick search for the first element of "value". + int relativeIndex = IndexOf(ref Unsafe.Add(ref searchSpace, index), valueHead, remainingSearchSpaceLength); + if (relativeIndex == -1) + break; + index += relativeIndex; + + // Found the first element of "value". See if the tail matches. + if (SequenceEqual(ref Unsafe.Add(ref searchSpace, index + 1), ref valueTail, valueTailLength)) + return index; // The tail matched. Return a successful find. + + index++; + } + return -1; + } + + public static unsafe int IndexOf<T>(ref T searchSpace, T value, int length) + where T : IEquatable<T> + { + Debug.Assert(length >= 0); + + IntPtr index = (IntPtr)0; // Use IntPtr for arithmetic to avoid unnecessary 64->32->64 truncations + while (length >= 8) + { + length -= 8; + + if (value.Equals(Unsafe.Add(ref searchSpace, index))) + goto Found; + if (value.Equals(Unsafe.Add(ref searchSpace, index + 1))) + goto Found1; + if (value.Equals(Unsafe.Add(ref searchSpace, index + 2))) + goto Found2; + if (value.Equals(Unsafe.Add(ref searchSpace, index + 3))) + goto Found3; + if (value.Equals(Unsafe.Add(ref searchSpace, index + 4))) + goto Found4; + if (value.Equals(Unsafe.Add(ref searchSpace, index + 5))) + goto Found5; + if (value.Equals(Unsafe.Add(ref searchSpace, index + 6))) + goto Found6; + if (value.Equals(Unsafe.Add(ref searchSpace, index + 7))) + goto Found7; + + index += 8; + } + + if (length >= 4) + { + length -= 4; + + if (value.Equals(Unsafe.Add(ref searchSpace, index))) + goto Found; + if (value.Equals(Unsafe.Add(ref searchSpace, index + 1))) + goto Found1; + if (value.Equals(Unsafe.Add(ref searchSpace, index + 2))) + goto Found2; + if (value.Equals(Unsafe.Add(ref searchSpace, index + 3))) + goto Found3; + + index += 4; + } + + while (length > 0) + { + if (value.Equals(Unsafe.Add(ref searchSpace, index))) + goto Found; + + index += 1; + length--; + } + return -1; + + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return (int)(byte*)index; + Found1: + return (int)(byte*)(index + 1); + Found2: + return (int)(byte*)(index + 2); + Found3: + return (int)(byte*)(index + 3); + Found4: + return (int)(byte*)(index + 4); + Found5: + return (int)(byte*)(index + 5); + Found6: + return (int)(byte*)(index + 6); + Found7: + return (int)(byte*)(index + 7); + } + + public static int IndexOfAny<T>(ref T searchSpace, T value0, T value1, int length) + where T : IEquatable<T> + { + Debug.Assert(length >= 0); + + T lookUp; + int index = 0; + while ((length - index) >= 8) + { + lookUp = Unsafe.Add(ref searchSpace, index); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, index + 4); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found4; + lookUp = Unsafe.Add(ref searchSpace, index + 5); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found5; + lookUp = Unsafe.Add(ref searchSpace, index + 6); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found6; + lookUp = Unsafe.Add(ref searchSpace, index + 7); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found7; + + index += 8; + } + + if ((length - index) >= 4) + { + lookUp = Unsafe.Add(ref searchSpace, index); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found3; + + index += 4; + } + + while (index < length) + { + lookUp = Unsafe.Add(ref searchSpace, index); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found; + + index++; + } + return -1; + + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return index; + Found1: + return index + 1; + Found2: + return index + 2; + Found3: + return index + 3; + Found4: + return index + 4; + Found5: + return index + 5; + Found6: + return index + 6; + Found7: + return index + 7; + } + + public static int IndexOfAny<T>(ref T searchSpace, T value0, T value1, T value2, int length) + where T : IEquatable<T> + { + Debug.Assert(length >= 0); + + T lookUp; + int index = 0; + while ((length - index) >= 8) + { + lookUp = Unsafe.Add(ref searchSpace, index); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, index + 4); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found4; + lookUp = Unsafe.Add(ref searchSpace, index + 5); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found5; + lookUp = Unsafe.Add(ref searchSpace, index + 6); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found6; + lookUp = Unsafe.Add(ref searchSpace, index + 7); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found7; + + index += 8; + } + + if ((length - index) >= 4) + { + lookUp = Unsafe.Add(ref searchSpace, index); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found; + lookUp = Unsafe.Add(ref searchSpace, index + 1); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, index + 2); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, index + 3); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found3; + + index += 4; + } + + while (index < length) + { + lookUp = Unsafe.Add(ref searchSpace, index); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found; + + index++; + } + return -1; + + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return index; + Found1: + return index + 1; + Found2: + return index + 2; + Found3: + return index + 3; + Found4: + return index + 4; + Found5: + return index + 5; + Found6: + return index + 6; + Found7: + return index + 7; + } + + public static int IndexOfAny<T>(ref T searchSpace, int searchSpaceLength, ref T value, int valueLength) + where T : IEquatable<T> + { + Debug.Assert(searchSpaceLength >= 0); + Debug.Assert(valueLength >= 0); + + if (valueLength == 0) + return 0; // A zero-length sequence is always treated as "found" at the start of the search space. + + int index = -1; + for (int i = 0; i < valueLength; i++) + { + var tempIndex = IndexOf(ref searchSpace, Unsafe.Add(ref value, i), searchSpaceLength); + if ((uint)tempIndex < (uint)index) + { + index = tempIndex; + // Reduce space for search, cause we don't care if we find the search value after the index of a previously found value + searchSpaceLength = tempIndex; + + if (index == 0) break; + } + } + return index; + } + + public static int LastIndexOf<T>(ref T searchSpace, int searchSpaceLength, ref T value, int valueLength) + where T : IEquatable<T> + { + Debug.Assert(searchSpaceLength >= 0); + Debug.Assert(valueLength >= 0); + + if (valueLength == 0) + return 0; // A zero-length sequence is always treated as "found" at the start of the search space. + + T valueHead = value; + ref T valueTail = ref Unsafe.Add(ref value, 1); + int valueTailLength = valueLength - 1; + + int index = 0; + for (; ; ) + { + Debug.Assert(0 <= index && index <= searchSpaceLength); // Ensures no deceptive underflows in the computation of "remainingSearchSpaceLength". + int remainingSearchSpaceLength = searchSpaceLength - index - valueTailLength; + if (remainingSearchSpaceLength <= 0) + break; // The unsearched portion is now shorter than the sequence we're looking for. So it can't be there. + + // Do a quick search for the first element of "value". + int relativeIndex = LastIndexOf(ref searchSpace, valueHead, remainingSearchSpaceLength); + if (relativeIndex == -1) + break; + + // Found the first element of "value". See if the tail matches. + if (SequenceEqual(ref Unsafe.Add(ref searchSpace, relativeIndex + 1), ref valueTail, valueTailLength)) + return relativeIndex; // The tail matched. Return a successful find. + + index += remainingSearchSpaceLength - relativeIndex; + } + return -1; + } + + public static int LastIndexOf<T>(ref T searchSpace, T value, int length) + where T : IEquatable<T> + { + Debug.Assert(length >= 0); + + while (length >= 8) + { + length -= 8; + + if (value.Equals(Unsafe.Add(ref searchSpace, length + 7))) + goto Found7; + if (value.Equals(Unsafe.Add(ref searchSpace, length + 6))) + goto Found6; + if (value.Equals(Unsafe.Add(ref searchSpace, length + 5))) + goto Found5; + if (value.Equals(Unsafe.Add(ref searchSpace, length + 4))) + goto Found4; + if (value.Equals(Unsafe.Add(ref searchSpace, length + 3))) + goto Found3; + if (value.Equals(Unsafe.Add(ref searchSpace, length + 2))) + goto Found2; + if (value.Equals(Unsafe.Add(ref searchSpace, length + 1))) + goto Found1; + if (value.Equals(Unsafe.Add(ref searchSpace, length))) + goto Found; + } + + if (length >= 4) + { + length -= 4; + + if (value.Equals(Unsafe.Add(ref searchSpace, length + 3))) + goto Found3; + if (value.Equals(Unsafe.Add(ref searchSpace, length + 2))) + goto Found2; + if (value.Equals(Unsafe.Add(ref searchSpace, length + 1))) + goto Found1; + if (value.Equals(Unsafe.Add(ref searchSpace, length))) + goto Found; + } + + while (length > 0) + { + length--; + + if (value.Equals(Unsafe.Add(ref searchSpace, length))) + goto Found; + } + return -1; + + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return length; + Found1: + return length + 1; + Found2: + return length + 2; + Found3: + return length + 3; + Found4: + return length + 4; + Found5: + return length + 5; + Found6: + return length + 6; + Found7: + return length + 7; + } + + public static int LastIndexOfAny<T>(ref T searchSpace, T value0, T value1, int length) + where T : IEquatable<T> + { + Debug.Assert(length >= 0); + + T lookUp; + while (length >= 8) + { + length -= 8; + + lookUp = Unsafe.Add(ref searchSpace, length + 7); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found7; + lookUp = Unsafe.Add(ref searchSpace, length + 6); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found6; + lookUp = Unsafe.Add(ref searchSpace, length + 5); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found5; + lookUp = Unsafe.Add(ref searchSpace, length + 4); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found4; + lookUp = Unsafe.Add(ref searchSpace, length + 3); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, length + 2); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, length + 1); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, length); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found; + } + + if (length >= 4) + { + length -= 4; + + lookUp = Unsafe.Add(ref searchSpace, length + 3); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, length + 2); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, length + 1); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, length); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found; + } + + while (length > 0) + { + length--; + + lookUp = Unsafe.Add(ref searchSpace, length); + if (value0.Equals(lookUp) || value1.Equals(lookUp)) + goto Found; + } + return -1; + + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return length; + Found1: + return length + 1; + Found2: + return length + 2; + Found3: + return length + 3; + Found4: + return length + 4; + Found5: + return length + 5; + Found6: + return length + 6; + Found7: + return length + 7; + } + + public static int LastIndexOfAny<T>(ref T searchSpace, T value0, T value1, T value2, int length) + where T : IEquatable<T> + { + Debug.Assert(length >= 0); + + T lookUp; + while (length >= 8) + { + length -= 8; + + lookUp = Unsafe.Add(ref searchSpace, length + 7); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found7; + lookUp = Unsafe.Add(ref searchSpace, length + 6); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found6; + lookUp = Unsafe.Add(ref searchSpace, length + 5); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found5; + lookUp = Unsafe.Add(ref searchSpace, length + 4); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found4; + lookUp = Unsafe.Add(ref searchSpace, length + 3); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, length + 2); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, length + 1); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, length); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found; + } + + if (length >= 4) + { + length -= 4; + + lookUp = Unsafe.Add(ref searchSpace, length + 3); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found3; + lookUp = Unsafe.Add(ref searchSpace, length + 2); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found2; + lookUp = Unsafe.Add(ref searchSpace, length + 1); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found1; + lookUp = Unsafe.Add(ref searchSpace, length); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found; + } + + while (length > 0) + { + length--; + + lookUp = Unsafe.Add(ref searchSpace, length); + if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) + goto Found; + } + return -1; + + Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return length; + Found1: + return length + 1; + Found2: + return length + 2; + Found3: + return length + 3; + Found4: + return length + 4; + Found5: + return length + 5; + Found6: + return length + 6; + Found7: + return length + 7; + } + + public static int LastIndexOfAny<T>(ref T searchSpace, int searchSpaceLength, ref T value, int valueLength) + where T : IEquatable<T> + { + Debug.Assert(searchSpaceLength >= 0); + Debug.Assert(valueLength >= 0); + + if (valueLength == 0) + return 0; // A zero-length sequence is always treated as "found" at the start of the search space. + + int index = -1; + for (int i = 0; i < valueLength; i++) + { + var tempIndex = LastIndexOf(ref searchSpace, Unsafe.Add(ref value, i), searchSpaceLength); + if (tempIndex > index) index = tempIndex; + } + return index; + } + + public static bool SequenceEqual<T>(ref T first, ref T second, int length) + where T : IEquatable<T> + { + Debug.Assert(length >= 0); + + if (Unsafe.AreSame(ref first, ref second)) + goto Equal; + + IntPtr index = (IntPtr)0; // Use IntPtr for arithmetic to avoid unnecessary 64->32->64 truncations + while (length >= 8) + { + length -= 8; + + if (!Unsafe.Add(ref first, index).Equals(Unsafe.Add(ref second, index))) + goto NotEqual; + if (!Unsafe.Add(ref first, index + 1).Equals(Unsafe.Add(ref second, index + 1))) + goto NotEqual; + if (!Unsafe.Add(ref first, index + 2).Equals(Unsafe.Add(ref second, index + 2))) + goto NotEqual; + if (!Unsafe.Add(ref first, index + 3).Equals(Unsafe.Add(ref second, index + 3))) + goto NotEqual; + if (!Unsafe.Add(ref first, index + 4).Equals(Unsafe.Add(ref second, index + 4))) + goto NotEqual; + if (!Unsafe.Add(ref first, index + 5).Equals(Unsafe.Add(ref second, index + 5))) + goto NotEqual; + if (!Unsafe.Add(ref first, index + 6).Equals(Unsafe.Add(ref second, index + 6))) + goto NotEqual; + if (!Unsafe.Add(ref first, index + 7).Equals(Unsafe.Add(ref second, index + 7))) + goto NotEqual; + + index += 8; + } + + if (length >= 4) + { + length -= 4; + + if (!Unsafe.Add(ref first, index).Equals(Unsafe.Add(ref second, index))) + goto NotEqual; + if (!Unsafe.Add(ref first, index + 1).Equals(Unsafe.Add(ref second, index + 1))) + goto NotEqual; + if (!Unsafe.Add(ref first, index + 2).Equals(Unsafe.Add(ref second, index + 2))) + goto NotEqual; + if (!Unsafe.Add(ref first, index + 3).Equals(Unsafe.Add(ref second, index + 3))) + goto NotEqual; + + index += 4; + } + + while (length > 0) + { + if (!Unsafe.Add(ref first, index).Equals(Unsafe.Add(ref second, index))) + goto NotEqual; + index += 1; + length--; + } + + Equal: + return true; + + NotEqual: // Workaround for https://github.com/dotnet/coreclr/issues/13549 + return false; + } + + public static int SequenceCompareTo<T>(ref T first, int firstLength, ref T second, int secondLength) + where T : IComparable<T> + { + Debug.Assert(firstLength >= 0); + Debug.Assert(secondLength >= 0); + + var minLength = firstLength; + if (minLength > secondLength) minLength = secondLength; + for (int i = 0; i < minLength; i++) + { + int result = Unsafe.Add(ref first, i).CompareTo(Unsafe.Add(ref second, i)); + if (result != 0) return result; + } + return firstLength.CompareTo(secondLength); + } + } +} diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.cs new file mode 100644 index 000000000..dad0f6294 --- /dev/null +++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.cs @@ -0,0 +1,503 @@ +// 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.Globalization; +using System.Runtime; +using System.Runtime.InteropServices; + +using Internal.Runtime.CompilerServices; + +#if BIT64 +using nuint = System.UInt64; +#else +using nuint = System.UInt32; +#endif + +namespace System +{ + internal static partial class SpanHelpers + { + public static int IndexOfCultureHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) + { + Debug.Assert(span.Length != 0); + Debug.Assert(value.Length != 0); + + if (GlobalizationMode.Invariant) + { + return CompareInfo.InvariantIndexOf(span, value, ignoreCase: false); + } + + return compareInfo.IndexOf(span, value, CompareOptions.None); + } + + public static int IndexOfCultureIgnoreCaseHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) + { + Debug.Assert(span.Length != 0); + Debug.Assert(value.Length != 0); + + if (GlobalizationMode.Invariant) + { + return CompareInfo.InvariantIndexOf(span, value, ignoreCase: true); + } + + return compareInfo.IndexOf(span, value, CompareOptions.IgnoreCase); + } + + public static int IndexOfOrdinalHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, bool ignoreCase) + { + Debug.Assert(span.Length != 0); + Debug.Assert(value.Length != 0); + + if (GlobalizationMode.Invariant) + { + return CompareInfo.InvariantIndexOf(span, value, ignoreCase); + } + + return CompareInfo.Invariant.IndexOfOrdinal(span, value, ignoreCase); + } + + public static bool StartsWithCultureHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) + { + Debug.Assert(value.Length != 0); + + if (GlobalizationMode.Invariant) + { + return span.StartsWith(value); + } + if (span.Length == 0) + { + return false; + } + return compareInfo.IsPrefix(span, value, CompareOptions.None); + } + + public static bool StartsWithCultureIgnoreCaseHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) + { + Debug.Assert(value.Length != 0); + + if (GlobalizationMode.Invariant) + { + return StartsWithOrdinalIgnoreCaseHelper(span, value); + } + if (span.Length == 0) + { + return false; + } + return compareInfo.IsPrefix(span, value, CompareOptions.IgnoreCase); + } + + public static bool StartsWithOrdinalIgnoreCaseHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value) + { + Debug.Assert(value.Length != 0); + + if (span.Length < value.Length) + { + return false; + } + return CompareInfo.CompareOrdinalIgnoreCase(span.Slice(0, value.Length), value) == 0; + } + + public static bool EndsWithCultureHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) + { + Debug.Assert(value.Length != 0); + + if (GlobalizationMode.Invariant) + { + return span.EndsWith(value); + } + if (span.Length == 0) + { + return false; + } + return compareInfo.IsSuffix(span, value, CompareOptions.None); + } + + public static bool EndsWithCultureIgnoreCaseHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value, CompareInfo compareInfo) + { + Debug.Assert(value.Length != 0); + + if (GlobalizationMode.Invariant) + { + return EndsWithOrdinalIgnoreCaseHelper(span, value); + } + if (span.Length == 0) + { + return false; + } + return compareInfo.IsSuffix(span, value, CompareOptions.IgnoreCase); + } + + public static bool EndsWithOrdinalIgnoreCaseHelper(ReadOnlySpan<char> span, ReadOnlySpan<char> value) + { + Debug.Assert(value.Length != 0); + + if (span.Length < value.Length) + { + return false; + } + return (CompareInfo.CompareOrdinalIgnoreCase(span.Slice(span.Length - value.Length), value) == 0); + } + + public static unsafe void ClearWithoutReferences(ref byte b, nuint byteLength) + { + if (byteLength == 0) + return; + +#if CORECLR && (AMD64 || ARM64) + if (byteLength > 4096) + goto PInvoke; + Unsafe.InitBlockUnaligned(ref b, 0, (uint)byteLength); + return; +#else + // TODO: Optimize other platforms to be on par with AMD64 CoreCLR + // Note: It's important that this switch handles lengths at least up to 22. + // See notes below near the main loop for why. + + // The switch will be very fast since it can be implemented using a jump + // table in assembly. See http://stackoverflow.com/a/449297/4077294 for more info. + + switch (byteLength) + { + case 1: + b = 0; + return; + case 2: + Unsafe.As<byte, short>(ref b) = 0; + return; + case 3: + Unsafe.As<byte, short>(ref b) = 0; + Unsafe.Add<byte>(ref b, 2) = 0; + return; + case 4: + Unsafe.As<byte, int>(ref b) = 0; + return; + case 5: + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.Add<byte>(ref b, 4) = 0; + return; + case 6: + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 4)) = 0; + return; + case 7: + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 4)) = 0; + Unsafe.Add<byte>(ref b, 6) = 0; + return; + case 8: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; +#endif + return; + case 9: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; +#endif + Unsafe.Add<byte>(ref b, 8) = 0; + return; + case 10: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; +#endif + Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + return; + case 11: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; +#endif + Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + Unsafe.Add<byte>(ref b, 10) = 0; + return; + case 12: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; +#endif + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + return; + case 13: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; +#endif + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + Unsafe.Add<byte>(ref b, 12) = 0; + return; + case 14: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; +#endif + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 12)) = 0; + return; + case 15: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; +#endif + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 12)) = 0; + Unsafe.Add<byte>(ref b, 14) = 0; + return; + case 16: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; + Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; +#endif + return; + case 17: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; + Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; +#endif + Unsafe.Add<byte>(ref b, 16) = 0; + return; + case 18: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; + Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; +#endif + Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 16)) = 0; + return; + case 19: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; + Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; +#endif + Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 16)) = 0; + Unsafe.Add<byte>(ref b, 18) = 0; + return; + case 20: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; + Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; +#endif + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 16)) = 0; + return; + case 21: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; + Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; +#endif + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 16)) = 0; + Unsafe.Add<byte>(ref b, 20) = 0; + return; + case 22: +#if BIT64 + Unsafe.As<byte, long>(ref b) = 0; + Unsafe.As<byte, long>(ref Unsafe.Add<byte>(ref b, 8)) = 0; +#else + Unsafe.As<byte, int>(ref b) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 4)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 8)) = 0; + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 12)) = 0; +#endif + Unsafe.As<byte, int>(ref Unsafe.Add<byte>(ref b, 16)) = 0; + Unsafe.As<byte, short>(ref Unsafe.Add<byte>(ref b, 20)) = 0; + return; + } + + // P/Invoke into the native version for large lengths + if (byteLength >= 512) goto PInvoke; + + nuint i = 0; // byte offset at which we're copying + + if ((Unsafe.As<byte, int>(ref b) & 3) != 0) + { + if ((Unsafe.As<byte, int>(ref b) & 1) != 0) + { + Unsafe.AddByteOffset<byte>(ref b, i) = 0; + i += 1; + if ((Unsafe.As<byte, int>(ref b) & 2) != 0) + goto IntAligned; + } + Unsafe.As<byte, short>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; + i += 2; + } + + IntAligned: + + // On 64-bit IntPtr.Size == 8, so we want to advance to the next 8-aligned address. If + // (int)b % 8 is 0, 5, 6, or 7, we will already have advanced by 0, 3, 2, or 1 + // bytes to the next aligned address (respectively), so do nothing. On the other hand, + // if it is 1, 2, 3, or 4 we will want to copy-and-advance another 4 bytes until + // we're aligned. + // The thing 1, 2, 3, and 4 have in common that the others don't is that if you + // subtract one from them, their 3rd lsb will not be set. Hence, the below check. + + if (((Unsafe.As<byte, int>(ref b) - 1) & 4) == 0) + { + Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; + i += 4; + } + + nuint end = byteLength - 16; + byteLength -= i; // lower 4 bits of byteLength represent how many bytes are left *after* the unrolled loop + + // We know due to the above switch-case that this loop will always run 1 iteration; max + // bytes we clear before checking is 23 (7 to align the pointers, 16 for 1 iteration) so + // the switch handles lengths 0-22. + Debug.Assert(end >= 7 && i <= end); + + // This is separated out into a different variable, so the i + 16 addition can be + // performed at the start of the pipeline and the loop condition does not have + // a dependency on the writes. + nuint counter; + + do + { + counter = i + 16; + + // This loop looks very costly since there appear to be a bunch of temporary values + // being created with the adds, but the jit (for x86 anyways) will convert each of + // these to use memory addressing operands. + + // So the only cost is a bit of code size, which is made up for by the fact that + // we save on writes to b. + +#if BIT64 + Unsafe.As<byte, long>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; + Unsafe.As<byte, long>(ref Unsafe.AddByteOffset<byte>(ref b, i + 8)) = 0; +#else + Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; + Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i + 4)) = 0; + Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i + 8)) = 0; + Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i + 12)) = 0; +#endif + + i = counter; + + // See notes above for why this wasn't used instead + // i += 16; + } + while (counter <= end); + + if ((byteLength & 8) != 0) + { +#if BIT64 + Unsafe.As<byte, long>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; +#else + Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; + Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i + 4)) = 0; +#endif + i += 8; + } + if ((byteLength & 4) != 0) + { + Unsafe.As<byte, int>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; + i += 4; + } + if ((byteLength & 2) != 0) + { + Unsafe.As<byte, short>(ref Unsafe.AddByteOffset<byte>(ref b, i)) = 0; + i += 2; + } + if ((byteLength & 1) != 0) + { + Unsafe.AddByteOffset<byte>(ref b, i) = 0; + // We're not using i after this, so not needed + // i += 1; + } + + return; +#endif + + PInvoke: + RuntimeImports.RhZeroMemory(ref b, byteLength); + } + + public static unsafe void ClearWithReferences(ref IntPtr ip, nuint pointerSizeLength) + { + if (pointerSizeLength == 0) + return; + + // TODO: Perhaps do switch casing to improve small size perf + + nuint i = 0; + nuint n = 0; + while ((n = i + 8) <= (pointerSizeLength)) + { + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 0) * (nuint)sizeof(IntPtr)) = default(IntPtr); + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 1) * (nuint)sizeof(IntPtr)) = default(IntPtr); + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 2) * (nuint)sizeof(IntPtr)) = default(IntPtr); + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 3) * (nuint)sizeof(IntPtr)) = default(IntPtr); + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 4) * (nuint)sizeof(IntPtr)) = default(IntPtr); + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 5) * (nuint)sizeof(IntPtr)) = default(IntPtr); + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 6) * (nuint)sizeof(IntPtr)) = default(IntPtr); + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 7) * (nuint)sizeof(IntPtr)) = default(IntPtr); + i = n; + } + if ((n = i + 4) <= (pointerSizeLength)) + { + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 0) * (nuint)sizeof(IntPtr)) = default(IntPtr); + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 1) * (nuint)sizeof(IntPtr)) = default(IntPtr); + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 2) * (nuint)sizeof(IntPtr)) = default(IntPtr); + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 3) * (nuint)sizeof(IntPtr)) = default(IntPtr); + i = n; + } + if ((n = i + 2) <= (pointerSizeLength)) + { + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 0) * (nuint)sizeof(IntPtr)) = default(IntPtr); + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 1) * (nuint)sizeof(IntPtr)) = default(IntPtr); + i = n; + } + if ((i + 1) <= (pointerSizeLength)) + { + Unsafe.AddByteOffset<IntPtr>(ref ip, (i + 0) * (nuint)sizeof(IntPtr)) = default(IntPtr); + } + } + } +} diff --git a/src/System.Private.CoreLib/shared/System/StringSpanHelpers.cs b/src/System.Private.CoreLib/shared/System/StringSpanHelpers.cs index 58820a81f..2d6152de5 100644 --- a/src/System.Private.CoreLib/shared/System/StringSpanHelpers.cs +++ b/src/System.Private.CoreLib/shared/System/StringSpanHelpers.cs @@ -57,23 +57,6 @@ namespace System return true; } - public static ReadOnlySpan<char> Trim(this ReadOnlySpan<char> source) - { - int startIndex = 0, endIndex = source.Length - 1; - - while (startIndex <= endIndex && char.IsWhiteSpace(source[startIndex])) - { - startIndex++; - } - - while (endIndex >= startIndex && char.IsWhiteSpace(source[endIndex])) - { - endIndex--; - } - - return source.Slice(startIndex, endIndex - startIndex + 1); - } - public static int IndexOf(this ReadOnlySpan<char> source, char value) => IndexOf(source, value, 0); |