// 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.Numerics; using System.Runtime; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using System.Runtime.Intrinsics; using System.Runtime.Intrinsics.Arm; using System.Runtime.Intrinsics.Wasm; using System.Runtime.Intrinsics.X86; namespace System.Buffers { /// <summary>Data structure used to optimize checks for whether a char is in a set of chars.</summary> /// <remarks> /// Like a Bloom filter, the idea is to create a bit map of the characters we are /// searching for and use this map as a "cheap" check to decide if the current /// character in the string exists in the array of input characters. There are /// 256 bits in the map, with each character mapped to 2 bits. Every character is /// divided into 2 bytes, and then every byte is mapped to 1 bit. The character map /// is an array of 8 integers acting as map blocks. The 3 lsb in each byte in the /// character is used to index into this map to get the right block, the value of /// the remaining 5 msb are used as the bit position inside this block. /// </remarks> [StructLayout(LayoutKind.Sequential)] internal readonly struct ProbabilisticMap { // The vectorized algorithm operates on bytes instead of uint32s. // The index and shift are adjusted so that we represent the structure // as "32 x uint8" instead of "8 x uint32". // We use the vectorized implementation when we have access to Sse41 or Arm64 intrinsics. private const uint VectorizedIndexMask = 31u; private const int VectorizedIndexShift = 5; // If we don't support vectorization, use uint32 to speed up // "IsCharBitSet" checks in scalar loops. private const uint PortableIndexMask = 7u; private const int PortableIndexShift = 3; private readonly uint _e0, _e1, _e2, _e3, _e4, _e5, _e6, _e7; public ProbabilisticMap(ReadOnlySpan<char> values) { bool hasAscii = false; ref uint charMap = ref _e0; for (int i = 0; i < values.Length; ++i) { int c = values[i]; // Map low bit SetCharBit(ref charMap, (byte)c); // Map high bit c >>= 8; if (c == 0) { hasAscii = true; } else { SetCharBit(ref charMap, (byte)c); } } if (hasAscii) { // Common to search for ASCII symbols. Just set the high value once. SetCharBit(ref charMap, 0); } } // SetCharBit and IsCharBitSet must bypass R2R because the set of supported intrinsics impacts how the type is constructed in memory, // so which branch is taken must never change during program execution as we're tiering up. Other methods in this type only check for // intrinsics as a fast path where the fallback path behaves identically, so they are fine to compile R2R. [MethodImpl(MethodImplOptions.AggressiveInlining)] [BypassReadyToRun] private static void SetCharBit(ref uint charMap, byte value) { if (Sse41.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.IsSupported) { Unsafe.Add(ref Unsafe.As<uint, byte>(ref charMap), value & VectorizedIndexMask) |= (byte)(1u << (value >> VectorizedIndexShift)); } else { Unsafe.Add(ref charMap, value & PortableIndexMask) |= 1u << (value >> PortableIndexShift); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] [BypassReadyToRun] private static bool IsCharBitSet(ref uint charMap, byte value) => Sse41.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.IsSupported ? (Unsafe.Add(ref Unsafe.As<uint, byte>(ref charMap), value & VectorizedIndexMask) & (1u << (value >> VectorizedIndexShift))) != 0 : (Unsafe.Add(ref charMap, value & PortableIndexMask) & (1u << (value >> PortableIndexShift))) != 0; [MethodImpl(MethodImplOptions.AggressiveInlining)] internal static bool Contains(ref uint charMap, ReadOnlySpan<char> values, int ch) => IsCharBitSet(ref charMap, (byte)ch) && IsCharBitSet(ref charMap, (byte)(ch >> 8)) && Contains(values, (char)ch); [MethodImpl(MethodImplOptions.AggressiveInlining)] internal static bool Contains(ReadOnlySpan<char> values, char ch) => SpanHelpers.NonPackedContainsValueType( ref Unsafe.As<char, short>(ref MemoryMarshal.GetReference(values)), (short)ch, values.Length); [MethodImpl(MethodImplOptions.AggressiveInlining)] [CompExactlyDependsOn(typeof(Avx512Vbmi))] private static Vector512<byte> ContainsMask64CharsAvx512(Vector512<byte> charMap, ref char searchSpace0, ref char searchSpace1) { Vector512<ushort> source0 = Vector512.LoadUnsafe(ref searchSpace0); Vector512<ushort> source1 = Vector512.LoadUnsafe(ref searchSpace1); Vector512<byte> sourceLower = Avx512Vbmi.PermuteVar64x8x2(source0.AsByte(), Vector512.CreateSequence<byte>(0, 2), source1.AsByte()); Vector512<byte> sourceUpper = Avx512Vbmi.PermuteVar64x8x2(source0.AsByte(), Vector512.CreateSequence<byte>(1, 2), source1.AsByte()); Vector512<byte> resultLower = IsCharBitNotSetAvx512(charMap, sourceLower); Vector512<byte> resultUpper = IsCharBitNotSetAvx512(charMap, sourceUpper); return ~(resultLower | resultUpper); } [MethodImpl(MethodImplOptions.AggressiveInlining)] [CompExactlyDependsOn(typeof(Avx512Vbmi))] private static Vector512<byte> IsCharBitNotSetAvx512(Vector512<byte> charMap, Vector512<byte> values) { // X86 does not have an instruction for right shifting 8-bit values, so it's instead emulated // by using a 32-bit value shift followed by an AND to mask off the bits that should be zeroed. // We're using PermuteVar64x8, which only looks at the lower 6 bits, so we can skip the AND. // Bits 4/5/6 will not affect the result as the bit positions vector is duplicated 8 times. Vector512<byte> shifted = (values.AsInt32() >>> VectorizedIndexShift).AsByte(); Vector512<byte> bitPositions = Avx512Vbmi.PermuteVar64x8(Vector512.Create(0x8040201008040201).AsByte(), shifted); // We want to select bytes from 'charMap' based on the low 5 bits of 'values' (values & VectorizedIndexMask). // PermuteVar64x8 will look at the low 6 bits, but the 6th bit will not affect the result as the 'charMap' is duplicated. Vector512<byte> bitMask = Avx512Vbmi.PermuteVar64x8(charMap, values); return Vector512.Equals(bitMask & bitPositions, Vector512<byte>.Zero); } [MethodImpl(MethodImplOptions.AggressiveInlining)] [CompExactlyDependsOn(typeof(Avx512Vbmi.VL))] private static Vector256<byte> ContainsMask32CharsAvx512(Vector256<byte> charMap, ref char searchSpace0, ref char searchSpace1) { Vector256<ushort> source0 = Vector256.LoadUnsafe(ref searchSpace0); Vector256<ushort> source1 = Vector256.LoadUnsafe(ref searchSpace1); Vector256<byte> sourceLower = Avx512Vbmi.VL.PermuteVar32x8x2(source0.AsByte(), Vector256.CreateSequence<byte>(0, 2), source1.AsByte()); Vector256<byte> sourceUpper = Avx512Vbmi.VL.PermuteVar32x8x2(source0.AsByte(), Vector256.CreateSequence<byte>(1, 2), source1.AsByte()); Vector256<byte> resultLower = IsCharBitNotSetAvx512(charMap, sourceLower); Vector256<byte> resultUpper = IsCharBitNotSetAvx512(charMap, sourceUpper); return ~(resultLower | resultUpper); } [MethodImpl(MethodImplOptions.AggressiveInlining)] [CompExactlyDependsOn(typeof(Avx512Vbmi.VL))] private static Vector256<byte> IsCharBitNotSetAvx512(Vector256<byte> charMap, Vector256<byte> values) { // X86 does not have an instruction for right shifting 8-bit values, so it's instead emulated // by using a 32-bit value shift followed by an AND to mask off the bits that should be zeroed. // We're using PermuteVar32x8, which only looks at the lower 5 bits, so we can skip the AND. // Bits 4/5 will not affect the result as the bit positions vector is duplicated 4 times Vector256<byte> shifted = (values.AsInt32() >>> VectorizedIndexShift).AsByte(); Vector256<byte> bitPositions = Avx512Vbmi.VL.PermuteVar32x8(Vector256.Create(0x8040201008040201).AsByte(), shifted); // We want to select bytes from 'charMap' based on the low 5 bits of 'values' (values & VectorizedIndexMask). // PermuteVar32x8 already looks only at the low 5 bits, so we can skip the redundant AND. Vector256<byte> bitMask = Avx512Vbmi.VL.PermuteVar32x8(charMap, values); return Vector256.Equals(bitMask & bitPositions, Vector256<byte>.Zero); } [MethodImpl(MethodImplOptions.AggressiveInlining)] [CompExactlyDependsOn(typeof(Avx2))] private static Vector256<byte> ContainsMask32CharsAvx2(Vector256<byte> charMapLower, Vector256<byte> charMapUpper, ref char searchSpace) { Vector256<ushort> source0 = Vector256.LoadUnsafe(ref searchSpace); Vector256<ushort> source1 = Vector256.LoadUnsafe(ref searchSpace, (nuint)Vector256<ushort>.Count); Vector256<byte> sourceLower = Avx2.PackUnsignedSaturate( (source0 & Vector256.Create((ushort)255)).AsInt16(), (source1 & Vector256.Create((ushort)255)).AsInt16()); Vector256<byte> sourceUpper = Avx2.PackUnsignedSaturate( (source0 >>> 8).AsInt16(), (source1 >>> 8).AsInt16()); Vector256<byte> resultLower = IsCharBitNotSetAvx2(charMapLower, charMapUpper, sourceLower); Vector256<byte> resultUpper = IsCharBitNotSetAvx2(charMapLower, charMapUpper, sourceUpper); return ~(resultLower | resultUpper); } [MethodImpl(MethodImplOptions.AggressiveInlining)] [CompExactlyDependsOn(typeof(Avx2))] private static Vector256<byte> IsCharBitNotSetAvx2(Vector256<byte> charMapLower, Vector256<byte> charMapUpper, Vector256<byte> values) { Vector256<byte> shifted = values >>> VectorizedIndexShift; Vector256<byte> bitPositions = Avx2.Shuffle(Vector256.Create(0x8040201008040201).AsByte(), shifted); Vector256<byte> index = values & Vector256.Create((byte)VectorizedIndexMask); Vector256<byte> bitMaskLower = Avx2.Shuffle(charMapLower, index); Vector256<byte> bitMaskUpper = Avx2.Shuffle(charMapUpper, index - Vector256.Create((byte)16)); Vector256<byte> mask = Vector256.GreaterThan(index, Vector256.Create((byte)15)); Vector256<byte> bitMask = Vector256.ConditionalSelect(mask, bitMaskUpper, bitMaskLower); return Vector256.Equals(bitMask & bitPositions, Vector256<byte>.Zero); } [MethodImpl(MethodImplOptions.AggressiveInlining)] [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] [CompExactlyDependsOn(typeof(Sse2))] [CompExactlyDependsOn(typeof(PackedSimd))] private static Vector128<byte> ContainsMask16Chars(Vector128<byte> charMapLower, Vector128<byte> charMapUpper, ref char searchSpace) { Vector128<ushort> source0 = Vector128.LoadUnsafe(ref searchSpace); Vector128<ushort> source1 = Vector128.LoadUnsafe(ref searchSpace, (nuint)Vector128<ushort>.Count); Vector128<byte> sourceLower; Vector128<byte> sourceUpper; if (Sse2.IsSupported) { sourceLower = Sse2.PackUnsignedSaturate((source0 & Vector128.Create((ushort)255)).AsInt16(), (source1 & Vector128.Create((ushort)255)).AsInt16()); sourceUpper = Sse2.PackUnsignedSaturate((source0 >>> 8).AsInt16(), (source1 >>> 8).AsInt16()); } else if (AdvSimd.Arm64.IsSupported) { sourceLower = AdvSimd.Arm64.UnzipEven(source0.AsByte(), source1.AsByte()); sourceUpper = AdvSimd.Arm64.UnzipOdd(source0.AsByte(), source1.AsByte()); } else if (PackedSimd.IsSupported) { sourceLower = PackedSimd.ConvertNarrowingSaturateUnsigned((source0 & Vector128.Create((ushort)255)).AsInt16(), (source1 & Vector128.Create((ushort)255)).AsInt16()); sourceUpper = PackedSimd.ConvertNarrowingSaturateUnsigned((source0 >>> 8).AsInt16(), (source1 >>> 8).AsInt16()); } else { // We explicitly recheck each IsSupported query to ensure that the trimmer can see which paths are live/dead ThrowHelper.ThrowUnreachableException(); sourceLower = default; sourceUpper = default; } Vector128<byte> resultLower = IsCharBitNotSet(charMapLower, charMapUpper, sourceLower); Vector128<byte> resultUpper = IsCharBitNotSet(charMapLower, charMapUpper, sourceUpper); return ~(resultLower | resultUpper); } [MethodImpl(MethodImplOptions.AggressiveInlining)] [CompExactlyDependsOn(typeof(Sse2))] [CompExactlyDependsOn(typeof(Ssse3))] [CompExactlyDependsOn(typeof(AdvSimd))] [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] [CompExactlyDependsOn(typeof(PackedSimd))] private static Vector128<byte> IsCharBitNotSet(Vector128<byte> charMapLower, Vector128<byte> charMapUpper, Vector128<byte> values) { Vector128<byte> shifted = values >>> VectorizedIndexShift; Vector128<byte> bitPositions = Vector128.ShuffleNative(Vector128.Create(0x8040201008040201).AsByte(), shifted); Vector128<byte> index = values & Vector128.Create((byte)VectorizedIndexMask); Vector128<byte> bitMask; if (AdvSimd.Arm64.IsSupported) { bitMask = AdvSimd.Arm64.VectorTableLookup((charMapLower, charMapUpper), index); } else { Vector128<byte> bitMaskLower = Vector128.ShuffleNative(charMapLower, index); Vector128<byte> bitMaskUpper = Vector128.ShuffleNative(charMapUpper, index - Vector128.Create((byte)16)); Vector128<byte> mask = Vector128.GreaterThan(index, Vector128.Create((byte)15)); bitMask = Vector128.ConditionalSelect(mask, bitMaskUpper, bitMaskLower); } return Vector128.Equals(bitMask & bitPositions, Vector128<byte>.Zero); } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool ShouldUseSimpleLoop(int searchSpaceLength, int valuesLength) { // We can perform either // - a simple O(haystack * needle) search or // - compute a character map of the values in O(needle), followed by an O(haystack) search // As the constant factor to compute the character map is relatively high, it's more efficient // to perform a simple loop search for short inputs. // // The following check does an educated guess as to whether computing the bitmap is more expensive. // The limit of 20 on the haystack length is arbitrary, determined by experimentation. return searchSpaceLength < Vector128<short>.Count || (searchSpaceLength < 20 && searchSpaceLength < (valuesLength >> 1)); } public static int IndexOfAny(ref char searchSpace, int searchSpaceLength, ref char values, int valuesLength) { var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); // If the search space is relatively short compared to the needle, do a simple O(n * m) search. if (ShouldUseSimpleLoop(searchSpaceLength, valuesLength)) { return IndexOfAnySimpleLoop<IndexOfAnyAsciiSearcher.DontNegate>(ref searchSpace, searchSpaceLength, valuesSpan); } if (IndexOfAnyAsciiSearcher.TryIndexOfAny(ref searchSpace, searchSpaceLength, valuesSpan, out int index)) { return index; } return ProbabilisticIndexOfAny(ref searchSpace, searchSpaceLength, ref values, valuesLength); } public static int IndexOfAnyExcept(ref char searchSpace, int searchSpaceLength, ref char values, int valuesLength) { var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); if (IndexOfAnyAsciiSearcher.IsVectorizationSupported && !ShouldUseSimpleLoop(searchSpaceLength, valuesLength) && IndexOfAnyAsciiSearcher.TryIndexOfAnyExcept(ref searchSpace, searchSpaceLength, valuesSpan, out int index)) { return index; } return IndexOfAnySimpleLoop<IndexOfAnyAsciiSearcher.Negate>(ref searchSpace, searchSpaceLength, valuesSpan); } public static int LastIndexOfAny(ref char searchSpace, int searchSpaceLength, ref char values, int valuesLength) { var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); // If the search space is relatively short compared to the needle, do a simple O(n * m) search. if (ShouldUseSimpleLoop(searchSpaceLength, valuesLength)) { return LastIndexOfAnySimpleLoop<IndexOfAnyAsciiSearcher.DontNegate>(ref searchSpace, searchSpaceLength, valuesSpan); } if (IndexOfAnyAsciiSearcher.TryLastIndexOfAny(ref searchSpace, searchSpaceLength, valuesSpan, out int index)) { return index; } return ProbabilisticLastIndexOfAny(ref searchSpace, searchSpaceLength, ref values, valuesLength); } public static int LastIndexOfAnyExcept(ref char searchSpace, int searchSpaceLength, ref char values, int valuesLength) { var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); if (IndexOfAnyAsciiSearcher.IsVectorizationSupported && !ShouldUseSimpleLoop(searchSpaceLength, valuesLength) && IndexOfAnyAsciiSearcher.TryLastIndexOfAnyExcept(ref searchSpace, searchSpaceLength, valuesSpan, out int index)) { return index; } return LastIndexOfAnySimpleLoop<IndexOfAnyAsciiSearcher.Negate>(ref searchSpace, searchSpaceLength, valuesSpan); } [MethodImpl(MethodImplOptions.NoInlining)] private static unsafe int ProbabilisticIndexOfAny(ref char searchSpace, int searchSpaceLength, ref char values, int valuesLength) { var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); // ProbabilisticMapState can hold either a precomputed hash table or a pointer to the values. // Precomputing the table is relatively expensive, so we only do it when using SearchValues where instances can be reused. var state = new ProbabilisticMapState(&valuesSpan); // The FalseConst here indicates that we can't use the fast character checks and must instead check the values span. return IndexOfAny<SearchValues.FalseConst>(ref searchSpace, searchSpaceLength, ref state); } [MethodImpl(MethodImplOptions.NoInlining)] private static unsafe int ProbabilisticLastIndexOfAny(ref char searchSpace, int searchSpaceLength, ref char values, int valuesLength) { var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); // ProbabilisticMapState can hold either a precomputed hash table or a pointer to the values. // Precomputing the table is relatively expensive, so we only do it when using SearchValues where instances can be reused. var state = new ProbabilisticMapState(&valuesSpan); // The FalseConst here indicates that we can't use the fast character checks and must instead check the values span. return LastIndexOfAny<SearchValues.FalseConst>(ref searchSpace, searchSpaceLength, ref state); } [MethodImpl(MethodImplOptions.AggressiveInlining)] internal static int IndexOfAny<TUseFastContains>(ref char searchSpace, int searchSpaceLength, ref ProbabilisticMapState state) where TUseFastContains : struct, SearchValues.IRuntimeConst { if ((Sse41.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.IsSupported) && searchSpaceLength >= 16) { return Vector512.IsHardwareAccelerated && Avx512Vbmi.VL.IsSupported ? IndexOfAnyVectorizedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, ref state) : IndexOfAnyVectorized<TUseFastContains>(ref searchSpace, searchSpaceLength, ref state); } return ProbabilisticMapState.IndexOfAnySimpleLoop<TUseFastContains, IndexOfAnyAsciiSearcher.DontNegate>(ref searchSpace, searchSpaceLength, ref state); } [MethodImpl(MethodImplOptions.AggressiveInlining)] internal static int LastIndexOfAny<TUseFastContains>(ref char searchSpace, int searchSpaceLength, ref ProbabilisticMapState state) where TUseFastContains : struct, SearchValues.IRuntimeConst { if ((Sse41.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.IsSupported) && searchSpaceLength >= 16) { return Vector512.IsHardwareAccelerated && Avx512Vbmi.VL.IsSupported ? LastIndexOfAnyVectorizedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, ref state) : LastIndexOfAnyVectorized<TUseFastContains>(ref searchSpace, searchSpaceLength, ref state); } return ProbabilisticMapState.LastIndexOfAnySimpleLoop<TUseFastContains, IndexOfAnyAsciiSearcher.DontNegate>(ref searchSpace, searchSpaceLength, ref state); } [CompExactlyDependsOn(typeof(Avx512Vbmi.VL))] private static int IndexOfAnyVectorizedAvx512<TUseFastContains>(ref char searchSpace, int searchSpaceLength, ref ProbabilisticMapState state) where TUseFastContains : struct, SearchValues.IRuntimeConst { Debug.Assert(Avx512Vbmi.VL.IsSupported); Debug.Assert(searchSpaceLength >= 16); ref char searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength); Vector256<byte> charMap256 = Vector256.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map)); if (searchSpaceLength > 32) { Vector512<byte> charMap512 = Vector512.Create(charMap256); if (searchSpaceLength > 64) { ref char cur = ref searchSpace; ref char lastStartVector = ref Unsafe.Subtract(ref searchSpaceEnd, 64); while (true) { Vector512<byte> result = ContainsMask64CharsAvx512(charMap512, ref cur, ref Unsafe.Add(ref cur, Vector512<ushort>.Count)); if (result != Vector512<byte>.Zero) { if (TryFindMatchAvx512<TUseFastContains>(ref cur, result.ExtractMostSignificantBits(), ref state, out int index)) { return MatchOffset(ref searchSpace, ref cur) + index; } } cur = ref Unsafe.Add(ref cur, 64); if (Unsafe.IsAddressGreaterThan(ref cur, ref lastStartVector)) { if (Unsafe.AreSame(ref cur, ref searchSpaceEnd)) { break; } // Adjust the current vector and do one last iteration. cur = ref lastStartVector; } } } else { Debug.Assert(searchSpaceLength is > 32 and <= 64); // Process the first and last vector in the search space. // They may overlap, but we'll handle that in the index calculation if we do get a match. Vector512<byte> result = ContainsMask64CharsAvx512(charMap512, ref searchSpace, ref Unsafe.Subtract(ref searchSpaceEnd, Vector512<ushort>.Count)); if (result != Vector512<byte>.Zero) { if (TryFindMatchOverlappedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, result.ExtractMostSignificantBits(), ref state, out int index)) { return index; } } } } else { Debug.Assert(searchSpaceLength is >= 16 and <= 32); // Process the first and last vector in the search space. // They may overlap, but we'll handle that in the index calculation if we do get a match. Vector256<byte> result = ContainsMask32CharsAvx512(charMap256, ref searchSpace, ref Unsafe.Subtract(ref searchSpaceEnd, Vector256<ushort>.Count)); if (result != Vector256<byte>.Zero) { if (TryFindMatchOverlappedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, result.ExtractMostSignificantBits(), ref state, out int index)) { return index; } } } return -1; } [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] [CompExactlyDependsOn(typeof(Sse41))] [CompExactlyDependsOn(typeof(PackedSimd))] private static int IndexOfAnyVectorized<TUseFastContains>(ref char searchSpace, int searchSpaceLength, ref ProbabilisticMapState state) where TUseFastContains : struct, SearchValues.IRuntimeConst { Debug.Assert(Sse41.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.IsSupported); Debug.Assert(searchSpaceLength >= 16); ref char searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength); ref char cur = ref searchSpace; Vector128<byte> charMapLower = Vector128.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map)); Vector128<byte> charMapUpper = Vector128.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map), (nuint)Vector128<byte>.Count); #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // In this case, we have an else clause which has the same semantic meaning whether or not Avx2 is considered supported or unsupported if (Avx2.IsSupported && searchSpaceLength >= 32) #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough { Vector256<byte> charMapLower256 = Vector256.Create(charMapLower); Vector256<byte> charMapUpper256 = Vector256.Create(charMapUpper); ref char lastStartVectorAvx2 = ref Unsafe.Subtract(ref searchSpaceEnd, 32); while (true) { Vector256<byte> result = ContainsMask32CharsAvx2(charMapLower256, charMapUpper256, ref cur); if (result != Vector256<byte>.Zero) { if (TryFindMatch<TUseFastContains>(ref cur, PackedSpanHelpers.FixUpPackedVector256Result(result).ExtractMostSignificantBits(), ref state, out int index)) { return MatchOffset(ref searchSpace, ref cur) + index; } } cur = ref Unsafe.Add(ref cur, 32); if (Unsafe.IsAddressGreaterThan(ref cur, ref lastStartVectorAvx2)) { if (Unsafe.AreSame(ref cur, ref searchSpaceEnd)) { return -1; } if (Unsafe.ByteOffset(ref cur, ref searchSpaceEnd) > 16 * sizeof(char)) { // If we have more than 16 characters left to process, we can // adjust the current vector and do one last iteration of Avx2. cur = ref lastStartVectorAvx2; } else { // Otherwise adjust the vector such that we'll only need to do a single // iteration of ContainsMask16Chars below. cur = ref Unsafe.Subtract(ref searchSpaceEnd, 16); break; } } } } ref char lastStartVector = ref Unsafe.Subtract(ref searchSpaceEnd, 16); while (true) { Vector128<byte> result = ContainsMask16Chars(charMapLower, charMapUpper, ref cur); if (result != Vector128<byte>.Zero) { if (TryFindMatch<TUseFastContains>(ref cur, result.ExtractMostSignificantBits(), ref state, out int index)) { return MatchOffset(ref searchSpace, ref cur) + index; } } cur = ref Unsafe.Add(ref cur, 16); if (Unsafe.IsAddressGreaterThan(ref cur, ref lastStartVector)) { if (Unsafe.AreSame(ref cur, ref searchSpaceEnd)) { break; } // Adjust the current vector and do one last iteration. cur = ref lastStartVector; } } return -1; } [CompExactlyDependsOn(typeof(Avx512Vbmi.VL))] private static int LastIndexOfAnyVectorizedAvx512<TUseFastContains>(ref char searchSpace, int searchSpaceLength, ref ProbabilisticMapState state) where TUseFastContains : struct, SearchValues.IRuntimeConst { Debug.Assert(Avx512Vbmi.VL.IsSupported); Debug.Assert(searchSpaceLength >= 16); ref char cur = ref Unsafe.Add(ref searchSpace, searchSpaceLength); Vector256<byte> charMap256 = Vector256.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map)); if (searchSpaceLength > 32) { Vector512<byte> charMap512 = Vector512.Create(charMap256); if (searchSpaceLength > 64) { ref char lastStartVector = ref Unsafe.Add(ref searchSpace, 64); while (true) { Debug.Assert(Unsafe.ByteOffset(ref searchSpace, ref cur) >= 64 * sizeof(char)); cur = ref Unsafe.Subtract(ref cur, 64); Vector512<byte> result = ContainsMask64CharsAvx512(charMap512, ref cur, ref Unsafe.Add(ref cur, Vector512<ushort>.Count)); if (result != Vector512<byte>.Zero) { if (TryFindLastMatchAvx512<TUseFastContains>(ref cur, result.ExtractMostSignificantBits(), ref state, out int index)) { return MatchOffset(ref searchSpace, ref cur) + index; } } if (Unsafe.IsAddressLessThanOrEqualTo(ref cur, ref lastStartVector)) { if (Unsafe.AreSame(ref cur, ref searchSpace)) { break; } // Adjust the current vector and do one last iteration. cur = ref lastStartVector; } } } else { Debug.Assert(searchSpaceLength is > 32 and <= 64); Debug.Assert(Unsafe.ByteOffset(ref searchSpace, ref cur) >= 32 * sizeof(char)); // Process the first and last vector in the search space. // They may overlap, but we'll handle that in the index calculation if we do get a match. Vector512<byte> result = ContainsMask64CharsAvx512(charMap512, ref searchSpace, ref Unsafe.Subtract(ref cur, Vector512<ushort>.Count)); if (result != Vector512<byte>.Zero) { if (TryFindLastMatchOverlappedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, result.ExtractMostSignificantBits(), ref state, out int index)) { return index; } } } } else { Debug.Assert(searchSpaceLength is >= 16 and <= 32); Debug.Assert(Unsafe.ByteOffset(ref searchSpace, ref cur) >= 16 * sizeof(char)); // Process the first and last vector in the search space. // They may overlap, but we'll handle that in the index calculation if we do get a match. Vector256<byte> result = ContainsMask32CharsAvx512(charMap256, ref searchSpace, ref Unsafe.Subtract(ref cur, Vector256<ushort>.Count)); if (result != Vector256<byte>.Zero) { if (TryFindLastMatchOverlappedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, result.ExtractMostSignificantBits(), ref state, out int index)) { return index; } } } return -1; } [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] [CompExactlyDependsOn(typeof(Sse41))] [CompExactlyDependsOn(typeof(PackedSimd))] private static int LastIndexOfAnyVectorized<TUseFastContains>(ref char searchSpace, int searchSpaceLength, ref ProbabilisticMapState state) where TUseFastContains : struct, SearchValues.IRuntimeConst { Debug.Assert(Sse41.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.IsSupported); Debug.Assert(searchSpaceLength >= 16); ref char cur = ref Unsafe.Add(ref searchSpace, searchSpaceLength); Vector128<byte> charMapLower = Vector128.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map)); Vector128<byte> charMapUpper = Vector128.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map), (nuint)Vector128<byte>.Count); #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // In this case, we have an else clause which has the same semantic meaning whether or not Avx2 is considered supported or unsupported if (Avx2.IsSupported && searchSpaceLength >= 32) #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough { Vector256<byte> charMapLower256 = Vector256.Create(charMapLower); Vector256<byte> charMapUpper256 = Vector256.Create(charMapUpper); ref char lastStartVectorAvx2 = ref Unsafe.Add(ref searchSpace, 32); while (true) { Debug.Assert(Unsafe.ByteOffset(ref searchSpace, ref cur) >= 32 * sizeof(char)); cur = ref Unsafe.Subtract(ref cur, 32); Vector256<byte> result = ContainsMask32CharsAvx2(charMapLower256, charMapUpper256, ref cur); if (result != Vector256<byte>.Zero) { if (TryFindLastMatch<TUseFastContains>(ref cur, PackedSpanHelpers.FixUpPackedVector256Result(result).ExtractMostSignificantBits(), ref state, out int index)) { return MatchOffset(ref searchSpace, ref cur) + index; } } if (Unsafe.IsAddressLessThanOrEqualTo(ref cur, ref lastStartVectorAvx2)) { if (Unsafe.AreSame(ref cur, ref searchSpace)) { return -1; } if (Unsafe.ByteOffset(ref searchSpace, ref cur) > 16 * sizeof(char)) { // If we have more than 16 characters left to process, we can // adjust the current vector and do one last iteration of Avx2. cur = ref lastStartVectorAvx2; } else { // Otherwise adjust the vector such that we'll only need to do a single // iteration of ContainsMask16Chars below. cur = ref Unsafe.Add(ref searchSpace, 16); break; } } } } ref char lastStartVector = ref Unsafe.Add(ref searchSpace, 16); while (true) { Debug.Assert(Unsafe.ByteOffset(ref searchSpace, ref cur) >= 16 * sizeof(char)); cur = ref Unsafe.Subtract(ref cur, 16); Vector128<byte> result = ContainsMask16Chars(charMapLower, charMapUpper, ref cur); if (result != Vector128<byte>.Zero) { if (TryFindLastMatch<TUseFastContains>(ref cur, result.ExtractMostSignificantBits(), ref state, out int index)) { return MatchOffset(ref searchSpace, ref cur) + index; } } if (Unsafe.IsAddressLessThanOrEqualTo(ref cur, ref lastStartVector)) { if (Unsafe.AreSame(ref cur, ref searchSpace)) { break; } // Adjust the current vector and do one last iteration. cur = ref lastStartVector; } } return -1; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static int MatchOffset(ref char searchSpace, ref char cur) => (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref cur) / sizeof(char)); [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool TryFindMatch<TUseFastContains>(ref char cur, uint mask, ref ProbabilisticMapState state, out int index) where TUseFastContains : struct, SearchValues.IRuntimeConst { do { index = BitOperations.TrailingZeroCount(mask); if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) { return true; } mask = BitOperations.ResetLowestSetBit(mask); } while (mask != 0); index = 0; return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool TryFindMatchOverlappedAvx512<TUseFastContains>(ref char cur, int searchSpaceLength, uint mask, ref ProbabilisticMapState state, out int index) where TUseFastContains : struct, SearchValues.IRuntimeConst { do { index = BitOperations.TrailingZeroCount(mask); if (index >= Vector256<ushort>.Count) { // The potential match is in the second vector. // Fixup the index to account for how we loaded the second overlapped vector. index += searchSpaceLength - (2 * Vector256<ushort>.Count); } if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) { return true; } mask = BitOperations.ResetLowestSetBit(mask); } while (mask != 0); index = 0; return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool TryFindMatchAvx512<TUseFastContains>(ref char cur, ulong mask, ref ProbabilisticMapState state, out int index) where TUseFastContains : struct, SearchValues.IRuntimeConst { do { index = BitOperations.TrailingZeroCount(mask); if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) { return true; } mask = BitOperations.ResetLowestSetBit(mask); } while (mask != 0); index = 0; return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool TryFindMatchOverlappedAvx512<TUseFastContains>(ref char cur, int searchSpaceLength, ulong mask, ref ProbabilisticMapState state, out int index) where TUseFastContains : struct, SearchValues.IRuntimeConst { do { index = BitOperations.TrailingZeroCount(mask); if (index >= Vector512<ushort>.Count) { // The potential match is in the second vector. // Fixup the index to account for how we loaded the second overlapped vector. index += searchSpaceLength - (2 * Vector512<ushort>.Count); } if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) { return true; } mask = BitOperations.ResetLowestSetBit(mask); } while (mask != 0); index = 0; return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool TryFindLastMatch<TUseFastContains>(ref char cur, uint mask, ref ProbabilisticMapState state, out int index) where TUseFastContains : struct, SearchValues.IRuntimeConst { do { index = 31 - BitOperations.LeadingZeroCount(mask); if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) { return true; } // Clear the highest set bit mask = BitOperations.FlipBit(mask, index); } while (mask != 0); index = 0; return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool TryFindLastMatchOverlappedAvx512<TUseFastContains>(ref char cur, int searchSpaceLength, uint mask, ref ProbabilisticMapState state, out int index) where TUseFastContains : struct, SearchValues.IRuntimeConst { do { index = 31 - BitOperations.LeadingZeroCount(mask); // Clear the highest set bit mask = BitOperations.FlipBit(mask, index); if (index >= Vector256<ushort>.Count) { // The potential match is in the second vector. // Fixup the index to account for how we loaded the second overlapped vector. index += searchSpaceLength - (2 * Vector256<ushort>.Count); } if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) { return true; } } while (mask != 0); index = 0; return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool TryFindLastMatchAvx512<TUseFastContains>(ref char cur, ulong mask, ref ProbabilisticMapState state, out int index) where TUseFastContains : struct, SearchValues.IRuntimeConst { do { index = 63 - BitOperations.LeadingZeroCount(mask); if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) { return true; } // Clear the highest set bit mask = BitOperations.FlipBit(mask, index); } while (mask != 0); index = 0; return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static bool TryFindLastMatchOverlappedAvx512<TUseFastContains>(ref char cur, int searchSpaceLength, ulong mask, ref ProbabilisticMapState state, out int index) where TUseFastContains : struct, SearchValues.IRuntimeConst { do { index = 63 - BitOperations.LeadingZeroCount(mask); // Clear the highest set bit mask = BitOperations.FlipBit(mask, index); if (index >= Vector512<ushort>.Count) { // The potential match is in the second vector. // Fixup the index to account for how we loaded the second overlapped vector. index += searchSpaceLength - (2 * Vector512<ushort>.Count); } if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) { return true; } } while (mask != 0); index = 0; return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] internal static int IndexOfAnySimpleLoop<TNegator>(ref char searchSpace, int searchSpaceLength, ReadOnlySpan<char> values) where TNegator : struct, IndexOfAnyAsciiSearcher.INegator { ref char searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength); ref char cur = ref searchSpace; while (!Unsafe.AreSame(ref cur, ref searchSpaceEnd)) { char c = cur; if (TNegator.NegateIfNeeded(Contains(values, c))) { return MatchOffset(ref searchSpace, ref cur); } cur = ref Unsafe.Add(ref cur, 1); } return -1; } [MethodImpl(MethodImplOptions.AggressiveInlining)] internal static int LastIndexOfAnySimpleLoop<TNegator>(ref char searchSpace, int searchSpaceLength, ReadOnlySpan<char> values) where TNegator : struct, IndexOfAnyAsciiSearcher.INegator { for (int i = searchSpaceLength - 1; i >= 0; i--) { char c = Unsafe.Add(ref searchSpace, i); if (TNegator.NegateIfNeeded(Contains(values, c))) { return i; } } return -1; } } }