// Licensed to the .NET Foundation under one or more agreements. // The .NET Foundation licenses this file to you under the MIT license. using System.Diagnostics; using System.Globalization; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using System.Runtime.Intrinsics; using System.Runtime.Intrinsics.Arm; using System.Text; namespace System.Buffers { // Provides implementations for helpers shared across multiple SearchValues<string> implementations, // such as normalizing and matching values under different case sensitivity rules. internal static class StringSearchValuesHelper { [Conditional("DEBUG")] public static void ValidateReadPosition(ref char searchSpaceStart, int searchSpaceLength, ref char searchSpace, int offset = 0) { Debug.Assert(searchSpaceLength >= 0); ValidateReadPosition(MemoryMarshal.CreateReadOnlySpan(ref searchSpaceStart, searchSpaceLength), ref searchSpace, offset); } [Conditional("DEBUG")] public static void ValidateReadPosition(ReadOnlySpan<char> span, ref char searchSpace, int offset = 0) { Debug.Assert(offset >= 0); nint currentByteOffset = Unsafe.ByteOffset(ref MemoryMarshal.GetReference(span), ref searchSpace); Debug.Assert(currentByteOffset >= 0); Debug.Assert((currentByteOffset & 1) == 0); int currentOffset = (int)(currentByteOffset / 2); int availableLength = span.Length - currentOffset; Debug.Assert(offset <= availableLength); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool StartsWith<TCaseSensitivity>(ref char matchStart, int lengthRemaining, string[] candidates) where TCaseSensitivity : struct, ICaseSensitivity { foreach (string candidate in candidates) { if (StartsWith<TCaseSensitivity>(ref matchStart, lengthRemaining, candidate)) { return true; } } return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool StartsWith<TCaseSensitivity>(ref char matchStart, int lengthRemaining, string candidate) where TCaseSensitivity : struct, ICaseSensitivity { Debug.Assert(lengthRemaining > 0); if (lengthRemaining < candidate.Length) { return false; } return UnknownLengthEquals<TCaseSensitivity>(ref matchStart, candidate); } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool UnknownLengthEquals<TCaseSensitivity>(ref char matchStart, string candidate) where TCaseSensitivity : struct, ICaseSensitivity { if (typeof(TCaseSensitivity) == typeof(CaseSensitive)) { return SpanHelpers.SequenceEqual( ref Unsafe.As<char, byte>(ref matchStart), ref candidate.GetRawStringDataAsUInt8(), (uint)candidate.Length * sizeof(char)); } if (typeof(TCaseSensitivity) == typeof(CaseInsensitiveAscii) || typeof(TCaseSensitivity) == typeof(CaseInsensitiveAsciiLetters)) { return Ascii.EqualsIgnoreCase(ref matchStart, ref candidate.GetRawStringData(), (uint)candidate.Length); } Debug.Assert(typeof(TCaseSensitivity) == typeof(CaseInsensitiveUnicode)); return Ordinal.EqualsIgnoreCase(ref matchStart, ref candidate.GetRawStringData(), candidate.Length); } public interface IValueLength { } public readonly struct ValueLengthLessThan4 : IValueLength { } public readonly struct ValueLength4To8 : IValueLength { } public readonly struct ValueLength9To16 : IValueLength { } // "Unknown" is currently only used by Teddy when confirming matches. public readonly struct ValueLengthLongOrUnknown : IValueLength { } public readonly struct SingleValueState { public readonly string Value; public readonly nint SecondReadByteOffset; public readonly Vector256<ushort> Value256; public readonly Vector256<ushort> ToUpperMask256; public readonly ulong Value64_0 => Value256.AsUInt64()[0]; public readonly ulong Value64_1 => Value256.AsUInt64()[1]; public readonly uint Value32_0 => Value256.AsUInt32()[0]; public readonly uint Value32_1 => Value256.AsUInt32()[1]; public readonly ulong ToUpperMask64_0 => ToUpperMask256.AsUInt64()[0]; public readonly ulong ToUpperMask64_1 => ToUpperMask256.AsUInt64()[1]; public readonly uint ToUpperMask32_0 => ToUpperMask256.AsUInt32()[0]; public readonly uint ToUpperMask32_1 => ToUpperMask256.AsUInt32()[1]; public SingleValueState(string value, bool ignoreCase) { Debug.Assert(value.Length >= 2); Value = value; // We precompute vectors specific to this value to speed up later comparisons. // We group values depending on their length (2-3, 4-8, 9-16). // For any of those lengths, we can load the whole value with two overlapped reads (e.g. 2x 8 characters for lengths 9-16). // For a string "Hello World", we would load // [Hello Wo] // [lo World] // SecondReadByteOffset: 6 bytes (3 characters) // We then precompute a mask that converts any potential input to the uppercase variant, specific to this value. // We must ensure that the ASCII letter mask only applies to the letters, not the space character. // Value256: [HELLO WOLO WORLD] (note that the value is already converted to uppercase if we're ignoring casing) // ToUpperMask256: [xxxxx xxxx xxxxx] (x = ~0x20 for ASCII letters, 0xFFFF otherwise) // // Given a potential match, we can now confirm whether we found a match by loading the candidate in the same way and applying this mask: // Vector256 input = [Vector128.Load(candidate), Vector128.Load(candidate + 6 bytes)]; // bool matches = (input & ToUpperMask256) == Value256; // The two vectors may overlap completely for Length == 2 or Length == 4, and that's fine. // The second comparison during validation is redundant in such cases, but the alternative is to introduce more IValueLength specializations. if (value.Length <= 16) { if (value.Length > 8) { SecondReadByteOffset = (value.Length - 8) * sizeof(char); Value256 = Vector256.Create( Vector128.LoadUnsafe(ref value.GetRawStringDataAsUInt16()), Vector128.LoadUnsafe(ref Unsafe.AddByteOffset(ref value.GetRawStringDataAsUInt16(), SecondReadByteOffset))); } else if (value.Length >= 4) { SecondReadByteOffset = (value.Length - 4) * sizeof(char); Value256 = Vector256.Create(Vector128.Create( Unsafe.ReadUnaligned<ulong>(ref value.GetRawStringDataAsUInt8()), Unsafe.ReadUnaligned<ulong>(ref Unsafe.Add(ref value.GetRawStringDataAsUInt8(), SecondReadByteOffset)) )).AsUInt16(); } else { Debug.Assert(value.Length is 2 or 3); SecondReadByteOffset = (value.Length - 2) * sizeof(char); Value256 = Vector256.Create(Vector128.Create(Vector64.Create( Unsafe.ReadUnaligned<uint>(ref value.GetRawStringDataAsUInt8()), Unsafe.ReadUnaligned<uint>(ref Unsafe.Add(ref value.GetRawStringDataAsUInt8(), SecondReadByteOffset)) ))).AsUInt16(); } if (ignoreCase) { Vector256<ushort> isAsciiLetter = Vector256.GreaterThanOrEqual(Value256, Vector256.Create((ushort)'A')) & Vector256.LessThanOrEqual(Value256, Vector256.Create((ushort)'Z')); ToUpperMask256 = Vector256.ConditionalSelect(isAsciiLetter, Vector256.Create(unchecked((ushort)~0x20)), Vector256.Create(ushort.MaxValue)); } } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool MatchesLength9To16_CaseSensitive(ref char matchStart) { Debug.Assert(Value.Length is >= 9 and <= 16); Debug.Assert(ToUpperMask256 == default); if (Vector256.IsHardwareAccelerated) { Vector256<ushort> input = Vector256.Create( Vector128.LoadUnsafe(ref matchStart), Vector128.LoadUnsafe(ref Unsafe.AddByteOffset(ref matchStart, SecondReadByteOffset))); return input == Value256; } else { Vector128<ushort> different = Vector128.LoadUnsafe(ref matchStart) ^ Value256.GetLower(); different |= Vector128.LoadUnsafe(ref Unsafe.AddByteOffset(ref matchStart, SecondReadByteOffset)) ^ Value256.GetUpper(); return different == Vector128<ushort>.Zero; } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public bool MatchesLength9To16_CaseInsensitiveAscii(ref char matchStart) { Debug.Assert(Value.Length is >= 9 and <= 16); Debug.Assert(ToUpperMask256 != default); if (Vector256.IsHardwareAccelerated) { Vector256<ushort> input = Vector256.Create( Vector128.LoadUnsafe(ref matchStart), Vector128.LoadUnsafe(ref Unsafe.AddByteOffset(ref matchStart, SecondReadByteOffset))); return (input & ToUpperMask256) == Value256; } else { Vector128<ushort> different = (Vector128.LoadUnsafe(ref matchStart) & ToUpperMask256.GetLower()) ^ Value256.GetLower(); different |= (Vector128.LoadUnsafe(ref Unsafe.AddByteOffset(ref matchStart, SecondReadByteOffset)) & ToUpperMask256.GetUpper()) ^ Value256.GetUpper(); return different == Vector128<ushort>.Zero; } } } public interface ICaseSensitivity { static abstract char TransformInput(char input); static abstract Vector128<byte> TransformInput(Vector128<byte> input); static abstract Vector256<byte> TransformInput(Vector256<byte> input); static abstract Vector512<byte> TransformInput(Vector512<byte> input); static abstract bool Equals<TValueLength>(ref char matchStart, ref readonly SingleValueState state) where TValueLength : struct, IValueLength; } // Performs no case transformations. public readonly struct CaseSensitive : ICaseSensitivity { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static char TransformInput(char input) => input; [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Vector128<byte> TransformInput(Vector128<byte> input) => input; [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Vector256<byte> TransformInput(Vector256<byte> input) => input; [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Vector512<byte> TransformInput(Vector512<byte> input) => input; [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Equals<TValueLength>(ref char matchStart, ref readonly SingleValueState state) where TValueLength : struct, IValueLength { if (typeof(TValueLength) == typeof(ValueLengthLongOrUnknown)) { return UnknownLengthEquals<CaseSensitive>(ref matchStart, state.Value); } else if (typeof(TValueLength) == typeof(ValueLength9To16)) { return state.MatchesLength9To16_CaseSensitive(ref matchStart); } else if (typeof(TValueLength) == typeof(ValueLength4To8)) { ref byte matchByteStart = ref Unsafe.As<char, byte>(ref matchStart); ulong differentBits = Unsafe.ReadUnaligned<ulong>(ref matchByteStart) - state.Value64_0; differentBits |= Unsafe.ReadUnaligned<ulong>(ref Unsafe.Add(ref matchByteStart, state.SecondReadByteOffset)) - state.Value64_1; return differentBits == 0; } else { Debug.Assert(state.Value.Length is 2 or 3); ref byte matchByteStart = ref Unsafe.As<char, byte>(ref matchStart); if (AdvSimd.IsSupported) { // See comments on SingleStringSearchValuesPackedThreeChars.CanSkipAnchorMatchVerification. // When running on Arm64, this helper is also used to confirm vectorized anchor matches. // We do so because we're using UnzipEven when packing inputs, which may produce false positive anchor matches. // When called from SingleStringSearchValuesThreeChars (non-packed), we could skip to the else branch instead. Debug.Assert(matchStart == state.Value[0] || (matchStart & 0xFF) == state.Value[0]); uint differentBits = Unsafe.ReadUnaligned<uint>(ref matchByteStart) - state.Value32_0; differentBits |= Unsafe.ReadUnaligned<uint>(ref Unsafe.Add(ref matchByteStart, state.SecondReadByteOffset)) - state.Value32_1; return differentBits == 0; } else { // Otherwise, this path is not used when confirming vectorized anchor matches. // It's only used as part of the scalar search loop, which always checks that the first character matches before calling this helper. // We know that the candidate is 2 or 3 characters long, and that the first character has already been checked. // We only have to to check whether the last 2 characters also match. Debug.Assert(matchStart == state.Value[0], "This should only be called after the first character has been checked"); return Unsafe.ReadUnaligned<uint>(ref Unsafe.Add(ref matchByteStart, state.SecondReadByteOffset)) == state.Value32_1; } } } } // Transforms inputs to their uppercase variants with the assumption that all input characters are ASCII letters. // These helpers may produce wrong results for other characters, and the callers must account for that. public readonly struct CaseInsensitiveAsciiLetters : ICaseSensitivity { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static char TransformInput(char input) => (char)(input & ~0x20); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Vector128<byte> TransformInput(Vector128<byte> input) => input & Vector128.Create(unchecked((byte)~0x20)); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Vector256<byte> TransformInput(Vector256<byte> input) => input & Vector256.Create(unchecked((byte)~0x20)); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Vector512<byte> TransformInput(Vector512<byte> input) => input & Vector512.Create(unchecked((byte)~0x20)); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Equals<TValueLength>(ref char matchStart, ref readonly SingleValueState state) where TValueLength : struct, IValueLength { if (typeof(TValueLength) == typeof(ValueLengthLongOrUnknown)) { return UnknownLengthEquals<CaseInsensitiveAsciiLetters>(ref matchStart, state.Value); } else if (typeof(TValueLength) == typeof(ValueLength9To16)) { return state.MatchesLength9To16_CaseInsensitiveAscii(ref matchStart); } else if (typeof(TValueLength) == typeof(ValueLength4To8)) { const ulong CaseMask = ~0x20002000200020u; ref byte matchByteStart = ref Unsafe.As<char, byte>(ref matchStart); ulong differentBits = (Unsafe.ReadUnaligned<ulong>(ref matchByteStart) & CaseMask) - state.Value64_0; differentBits |= (Unsafe.ReadUnaligned<ulong>(ref Unsafe.Add(ref matchByteStart, state.SecondReadByteOffset)) & CaseMask) - state.Value64_1; return differentBits == 0; } else { Debug.Assert(state.Value.Length is 2 or 3); const uint CaseMask = ~0x200020u; ref byte matchByteStart = ref Unsafe.As<char, byte>(ref matchStart); if (AdvSimd.IsSupported) { // See comments on SingleStringSearchValuesPackedThreeChars.CanSkipAnchorMatchVerification. // When running on Arm64, this helper is also used to confirm vectorized anchor matches. // We do so because we're using UnzipEven when packing inputs, which may produce false positive anchor matches. // When called from SingleStringSearchValuesThreeChars (non-packed), we could skip to the else branch instead. Debug.Assert(TransformInput((char)(matchStart & 0xFF)) == state.Value[0]); uint differentBits = (Unsafe.ReadUnaligned<uint>(ref matchByteStart) & CaseMask) - state.Value32_0; differentBits |= (Unsafe.ReadUnaligned<uint>(ref Unsafe.Add(ref matchByteStart, state.SecondReadByteOffset)) & CaseMask) - state.Value32_1; return differentBits == 0; } else { // Otherwise, this path is not used when confirming vectorized anchor matches. // It's only used as part of the scalar search loop, which always checks that the first character matches before calling this helper. // We know that the candidate is 2 or 3 characters long, and that the first character has already been checked. // We only have to to check whether the last 2 characters also match. Debug.Assert(TransformInput(matchStart) == state.Value[0], "This should only be called after the first character has been checked"); return (Unsafe.ReadUnaligned<uint>(ref Unsafe.Add(ref matchByteStart, state.SecondReadByteOffset)) & CaseMask) == state.Value32_1; } } } } // Transforms inputs to their uppercase variants with the assumption that all input characters are ASCII. // These helpers may produce wrong results for non-ASCII inputs, and the callers must account for that. public readonly struct CaseInsensitiveAscii : ICaseSensitivity { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static char TransformInput(char input) => TextInfo.ToUpperAsciiInvariant(input); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Vector128<byte> TransformInput(Vector128<byte> input) { Vector128<byte> subtraction = Vector128.Create((byte)(128 + 'a')); Vector128<byte> comparison = Vector128.Create((byte)(128 + 26)); Vector128<byte> caseConversion = Vector128.Create((byte)0x20); Vector128<byte> matches = Vector128.LessThan((input - subtraction).AsSByte(), comparison.AsSByte()).AsByte(); return input ^ (matches & caseConversion); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Vector256<byte> TransformInput(Vector256<byte> input) { Vector256<byte> subtraction = Vector256.Create((byte)(128 + 'a')); Vector256<byte> comparison = Vector256.Create((byte)(128 + 26)); Vector256<byte> caseConversion = Vector256.Create((byte)0x20); Vector256<byte> matches = Vector256.LessThan((input - subtraction).AsSByte(), comparison.AsSByte()).AsByte(); return input ^ (matches & caseConversion); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Vector512<byte> TransformInput(Vector512<byte> input) { Vector512<byte> subtraction = Vector512.Create((byte)(128 + 'a')); Vector512<byte> comparison = Vector512.Create((byte)(128 + 26)); Vector512<byte> caseConversion = Vector512.Create((byte)0x20); Vector512<byte> matches = Vector512.LessThan((input - subtraction).AsSByte(), comparison.AsSByte()).AsByte(); return input ^ (matches & caseConversion); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Equals<TValueLength>(ref char matchStart, ref readonly SingleValueState state) where TValueLength : struct, IValueLength { if (typeof(TValueLength) == typeof(ValueLengthLongOrUnknown)) { return UnknownLengthEquals<CaseInsensitiveAscii>(ref matchStart, state.Value); } else if (typeof(TValueLength) == typeof(ValueLength9To16)) { return state.MatchesLength9To16_CaseInsensitiveAscii(ref matchStart); } else if (typeof(TValueLength) == typeof(ValueLength4To8)) { ref byte matchByteStart = ref Unsafe.As<char, byte>(ref matchStart); ulong differentBits = (Unsafe.ReadUnaligned<ulong>(ref matchByteStart) & state.ToUpperMask64_0) - state.Value64_0; differentBits |= (Unsafe.ReadUnaligned<ulong>(ref Unsafe.Add(ref matchByteStart, state.SecondReadByteOffset)) & state.ToUpperMask64_1) - state.Value64_1; return differentBits == 0; } else { Debug.Assert(state.Value.Length is 2 or 3); ref byte matchByteStart = ref Unsafe.As<char, byte>(ref matchStart); uint differentBits = (Unsafe.ReadUnaligned<uint>(ref matchByteStart) & state.ToUpperMask32_0) - state.Value32_0; differentBits |= (Unsafe.ReadUnaligned<uint>(ref Unsafe.Add(ref matchByteStart, state.SecondReadByteOffset)) & state.ToUpperMask32_1) - state.Value32_1; return differentBits == 0; } } } // We can't efficiently map non-ASCII inputs to their Ordinal uppercase variants, // so this helper is only used for the verification of the whole input. public readonly struct CaseInsensitiveUnicode : ICaseSensitivity { public static char TransformInput(char input) => throw new UnreachableException(); public static Vector128<byte> TransformInput(Vector128<byte> input) => throw new UnreachableException(); public static Vector256<byte> TransformInput(Vector256<byte> input) => throw new UnreachableException(); public static Vector512<byte> TransformInput(Vector512<byte> input) => throw new UnreachableException(); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool Equals<TValueLength>(ref char matchStart, ref readonly SingleValueState state) where TValueLength : struct, IValueLength { if (typeof(TValueLength) == typeof(ValueLengthLongOrUnknown)) { return UnknownLengthEquals<CaseInsensitiveUnicode>(ref matchStart, state.Value); } else { return Ordinal.EqualsIgnoreCase_Scalar(ref matchStart, ref state.Value.GetRawStringData(), state.Value.Length); } } } } } |