| | | 1 | | // Licensed to the .NET Foundation under one or more agreements. |
| | | 2 | | // The .NET Foundation licenses this file to you under the MIT license. |
| | | 3 | | |
| | | 4 | | using System.Diagnostics; |
| | | 5 | | using System.Numerics; |
| | | 6 | | using System.Runtime; |
| | | 7 | | using System.Runtime.CompilerServices; |
| | | 8 | | using System.Runtime.InteropServices; |
| | | 9 | | using System.Runtime.Intrinsics; |
| | | 10 | | using System.Runtime.Intrinsics.Arm; |
| | | 11 | | using System.Runtime.Intrinsics.Wasm; |
| | | 12 | | using System.Runtime.Intrinsics.X86; |
| | | 13 | | |
| | | 14 | | namespace System.Buffers |
| | | 15 | | { |
| | | 16 | | /// <summary>Data structure used to optimize checks for whether a char is in a set of chars.</summary> |
| | | 17 | | /// <remarks> |
| | | 18 | | /// Like a Bloom filter, the idea is to create a bit map of the characters we are |
| | | 19 | | /// searching for and use this map as a "cheap" check to decide if the current |
| | | 20 | | /// character in the string exists in the array of input characters. There are |
| | | 21 | | /// 256 bits in the map, with each character mapped to 2 bits. Every character is |
| | | 22 | | /// divided into 2 bytes, and then every byte is mapped to 1 bit. The character map |
| | | 23 | | /// is an array of 8 integers acting as map blocks. The 3 lsb in each byte in the |
| | | 24 | | /// character is used to index into this map to get the right block, the value of |
| | | 25 | | /// the remaining 5 msb are used as the bit position inside this block. |
| | | 26 | | /// </remarks> |
| | | 27 | | [StructLayout(LayoutKind.Sequential)] |
| | | 28 | | internal readonly struct ProbabilisticMap |
| | | 29 | | { |
| | | 30 | | // The vectorized algorithm operates on bytes instead of uint32s. |
| | | 31 | | // The index and shift are adjusted so that we represent the structure |
| | | 32 | | // as "32 x uint8" instead of "8 x uint32". |
| | | 33 | | // We use the vectorized implementation when we have access to Sse41 or Arm64 intrinsics. |
| | | 34 | | private const uint VectorizedIndexMask = 31u; |
| | | 35 | | private const int VectorizedIndexShift = 5; |
| | | 36 | | |
| | | 37 | | // If we don't support vectorization, use uint32 to speed up |
| | | 38 | | // "IsCharBitSet" checks in scalar loops. |
| | | 39 | | private const uint PortableIndexMask = 7u; |
| | | 40 | | private const int PortableIndexShift = 3; |
| | | 41 | | |
| | | 42 | | private readonly uint _e0, _e1, _e2, _e3, _e4, _e5, _e6, _e7; |
| | | 43 | | |
| | | 44 | | public ProbabilisticMap(ReadOnlySpan<char> values) |
| | | 45 | | { |
| | 1831 | 46 | | bool hasAscii = false; |
| | 1831 | 47 | | ref uint charMap = ref _e0; |
| | | 48 | | |
| | 187432 | 49 | | for (int i = 0; i < values.Length; ++i) |
| | | 50 | | { |
| | 91885 | 51 | | int c = values[i]; |
| | | 52 | | |
| | | 53 | | // Map low bit |
| | 91885 | 54 | | SetCharBit(ref charMap, (byte)c); |
| | | 55 | | |
| | | 56 | | // Map high bit |
| | 91885 | 57 | | c >>= 8; |
| | | 58 | | |
| | 91885 | 59 | | if (c == 0) |
| | | 60 | | { |
| | 45396 | 61 | | hasAscii = true; |
| | | 62 | | } |
| | | 63 | | else |
| | | 64 | | { |
| | 46489 | 65 | | SetCharBit(ref charMap, (byte)c); |
| | | 66 | | } |
| | | 67 | | } |
| | | 68 | | |
| | 1831 | 69 | | if (hasAscii) |
| | | 70 | | { |
| | | 71 | | // Common to search for ASCII symbols. Just set the high value once. |
| | 1468 | 72 | | SetCharBit(ref charMap, 0); |
| | | 73 | | } |
| | 1831 | 74 | | } |
| | | 75 | | |
| | | 76 | | // SetCharBit and IsCharBitSet must bypass R2R because the set of supported intrinsics impacts how the type is c |
| | | 77 | | // so which branch is taken must never change during program execution as we're tiering up. Other methods in thi |
| | | 78 | | // intrinsics as a fast path where the fallback path behaves identically, so they are fine to compile R2R. |
| | | 79 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 80 | | [BypassReadyToRun] |
| | | 81 | | private static void SetCharBit(ref uint charMap, byte value) |
| | | 82 | | { |
| | 139842 | 83 | | if (Sse41.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.IsSupported) |
| | | 84 | | { |
| | 139842 | 85 | | Unsafe.Add(ref Unsafe.As<uint, byte>(ref charMap), value & VectorizedIndexMask) |= (byte)(1u << (value > |
| | | 86 | | } |
| | | 87 | | else |
| | | 88 | | { |
| | 0 | 89 | | Unsafe.Add(ref charMap, value & PortableIndexMask) |= 1u << (value >> PortableIndexShift); |
| | | 90 | | } |
| | 0 | 91 | | } |
| | | 92 | | |
| | | 93 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 94 | | [BypassReadyToRun] |
| | 0 | 95 | | private static bool IsCharBitSet(ref uint charMap, byte value) => Sse41.IsSupported || AdvSimd.Arm64.IsSupported |
| | 0 | 96 | | ? (Unsafe.Add(ref Unsafe.As<uint, byte>(ref charMap), value & VectorizedIndexMask) & (1u << (value >> Vector |
| | 0 | 97 | | : (Unsafe.Add(ref charMap, value & PortableIndexMask) & (1u << (value >> PortableIndexShift))) != 0; |
| | | 98 | | |
| | | 99 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 100 | | internal static bool Contains(ref uint charMap, ReadOnlySpan<char> values, int ch) => |
| | 0 | 101 | | IsCharBitSet(ref charMap, (byte)ch) && |
| | 0 | 102 | | IsCharBitSet(ref charMap, (byte)(ch >> 8)) && |
| | 0 | 103 | | Contains(values, (char)ch); |
| | | 104 | | |
| | | 105 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 106 | | internal static bool Contains(ReadOnlySpan<char> values, char ch) => |
| | 0 | 107 | | SpanHelpers.NonPackedContainsValueType( |
| | 0 | 108 | | ref Unsafe.As<char, short>(ref MemoryMarshal.GetReference(values)), |
| | 0 | 109 | | (short)ch, |
| | 0 | 110 | | values.Length); |
| | | 111 | | |
| | | 112 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 113 | | [CompExactlyDependsOn(typeof(Avx512Vbmi))] |
| | | 114 | | private static Vector512<byte> ContainsMask64CharsAvx512(Vector512<byte> charMap, ref char searchSpace0, ref cha |
| | | 115 | | { |
| | 12408 | 116 | | Vector512<ushort> source0 = Vector512.LoadUnsafe(ref searchSpace0); |
| | 12408 | 117 | | Vector512<ushort> source1 = Vector512.LoadUnsafe(ref searchSpace1); |
| | | 118 | | |
| | 12408 | 119 | | Vector512<byte> sourceLower = Avx512Vbmi.PermuteVar64x8x2(source0.AsByte(), Vector512.CreateSequence<byte>(0 |
| | 12408 | 120 | | Vector512<byte> sourceUpper = Avx512Vbmi.PermuteVar64x8x2(source0.AsByte(), Vector512.CreateSequence<byte>(1 |
| | | 121 | | |
| | 12408 | 122 | | Vector512<byte> resultLower = IsCharBitNotSetAvx512(charMap, sourceLower); |
| | 12408 | 123 | | Vector512<byte> resultUpper = IsCharBitNotSetAvx512(charMap, sourceUpper); |
| | | 124 | | |
| | 12408 | 125 | | return ~(resultLower | resultUpper); |
| | | 126 | | } |
| | | 127 | | |
| | | 128 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 129 | | [CompExactlyDependsOn(typeof(Avx512Vbmi))] |
| | | 130 | | private static Vector512<byte> IsCharBitNotSetAvx512(Vector512<byte> charMap, Vector512<byte> values) |
| | | 131 | | { |
| | | 132 | | // X86 does not have an instruction for right shifting 8-bit values, so it's instead emulated |
| | | 133 | | // by using a 32-bit value shift followed by an AND to mask off the bits that should be zeroed. |
| | | 134 | | // We're using PermuteVar64x8, which only looks at the lower 6 bits, so we can skip the AND. |
| | | 135 | | // Bits 4/5/6 will not affect the result as the bit positions vector is duplicated 8 times. |
| | 24816 | 136 | | Vector512<byte> shifted = (values.AsInt32() >>> VectorizedIndexShift).AsByte(); |
| | | 137 | | |
| | 24816 | 138 | | Vector512<byte> bitPositions = Avx512Vbmi.PermuteVar64x8(Vector512.Create(0x8040201008040201).AsByte(), shif |
| | | 139 | | |
| | | 140 | | // We want to select bytes from 'charMap' based on the low 5 bits of 'values' (values & VectorizedIndexMask) |
| | | 141 | | // PermuteVar64x8 will look at the low 6 bits, but the 6th bit will not affect the result as the 'charMap' i |
| | 24816 | 142 | | Vector512<byte> bitMask = Avx512Vbmi.PermuteVar64x8(charMap, values); |
| | | 143 | | |
| | 24816 | 144 | | return Vector512.Equals(bitMask & bitPositions, Vector512<byte>.Zero); |
| | | 145 | | } |
| | | 146 | | |
| | | 147 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 148 | | [CompExactlyDependsOn(typeof(Avx512Vbmi.VL))] |
| | | 149 | | private static Vector256<byte> ContainsMask32CharsAvx512(Vector256<byte> charMap, ref char searchSpace0, ref cha |
| | | 150 | | { |
| | 891 | 151 | | Vector256<ushort> source0 = Vector256.LoadUnsafe(ref searchSpace0); |
| | 891 | 152 | | Vector256<ushort> source1 = Vector256.LoadUnsafe(ref searchSpace1); |
| | | 153 | | |
| | 891 | 154 | | Vector256<byte> sourceLower = Avx512Vbmi.VL.PermuteVar32x8x2(source0.AsByte(), Vector256.CreateSequence<byte |
| | 891 | 155 | | Vector256<byte> sourceUpper = Avx512Vbmi.VL.PermuteVar32x8x2(source0.AsByte(), Vector256.CreateSequence<byte |
| | | 156 | | |
| | 891 | 157 | | Vector256<byte> resultLower = IsCharBitNotSetAvx512(charMap, sourceLower); |
| | 891 | 158 | | Vector256<byte> resultUpper = IsCharBitNotSetAvx512(charMap, sourceUpper); |
| | | 159 | | |
| | 891 | 160 | | return ~(resultLower | resultUpper); |
| | | 161 | | } |
| | | 162 | | |
| | | 163 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 164 | | [CompExactlyDependsOn(typeof(Avx512Vbmi.VL))] |
| | | 165 | | private static Vector256<byte> IsCharBitNotSetAvx512(Vector256<byte> charMap, Vector256<byte> values) |
| | | 166 | | { |
| | | 167 | | // X86 does not have an instruction for right shifting 8-bit values, so it's instead emulated |
| | | 168 | | // by using a 32-bit value shift followed by an AND to mask off the bits that should be zeroed. |
| | | 169 | | // We're using PermuteVar32x8, which only looks at the lower 5 bits, so we can skip the AND. |
| | | 170 | | // Bits 4/5 will not affect the result as the bit positions vector is duplicated 4 times |
| | 1782 | 171 | | Vector256<byte> shifted = (values.AsInt32() >>> VectorizedIndexShift).AsByte(); |
| | | 172 | | |
| | 1782 | 173 | | Vector256<byte> bitPositions = Avx512Vbmi.VL.PermuteVar32x8(Vector256.Create(0x8040201008040201).AsByte(), s |
| | | 174 | | |
| | | 175 | | // We want to select bytes from 'charMap' based on the low 5 bits of 'values' (values & VectorizedIndexMask) |
| | | 176 | | // PermuteVar32x8 already looks only at the low 5 bits, so we can skip the redundant AND. |
| | 1782 | 177 | | Vector256<byte> bitMask = Avx512Vbmi.VL.PermuteVar32x8(charMap, values); |
| | | 178 | | |
| | 1782 | 179 | | return Vector256.Equals(bitMask & bitPositions, Vector256<byte>.Zero); |
| | | 180 | | } |
| | | 181 | | |
| | | 182 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 183 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 184 | | private static Vector256<byte> ContainsMask32CharsAvx2(Vector256<byte> charMapLower, Vector256<byte> charMapUppe |
| | | 185 | | { |
| | 0 | 186 | | Vector256<ushort> source0 = Vector256.LoadUnsafe(ref searchSpace); |
| | 0 | 187 | | Vector256<ushort> source1 = Vector256.LoadUnsafe(ref searchSpace, (nuint)Vector256<ushort>.Count); |
| | | 188 | | |
| | 0 | 189 | | Vector256<byte> sourceLower = Avx2.PackUnsignedSaturate( |
| | 0 | 190 | | (source0 & Vector256.Create((ushort)255)).AsInt16(), |
| | 0 | 191 | | (source1 & Vector256.Create((ushort)255)).AsInt16()); |
| | | 192 | | |
| | 0 | 193 | | Vector256<byte> sourceUpper = Avx2.PackUnsignedSaturate( |
| | 0 | 194 | | (source0 >>> 8).AsInt16(), |
| | 0 | 195 | | (source1 >>> 8).AsInt16()); |
| | | 196 | | |
| | 0 | 197 | | Vector256<byte> resultLower = IsCharBitNotSetAvx2(charMapLower, charMapUpper, sourceLower); |
| | 0 | 198 | | Vector256<byte> resultUpper = IsCharBitNotSetAvx2(charMapLower, charMapUpper, sourceUpper); |
| | | 199 | | |
| | 0 | 200 | | return ~(resultLower | resultUpper); |
| | | 201 | | } |
| | | 202 | | |
| | | 203 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 204 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 205 | | private static Vector256<byte> IsCharBitNotSetAvx2(Vector256<byte> charMapLower, Vector256<byte> charMapUpper, V |
| | | 206 | | { |
| | 0 | 207 | | Vector256<byte> shifted = values >>> VectorizedIndexShift; |
| | | 208 | | |
| | 0 | 209 | | Vector256<byte> bitPositions = Avx2.Shuffle(Vector256.Create(0x8040201008040201).AsByte(), shifted); |
| | | 210 | | |
| | 0 | 211 | | Vector256<byte> index = values & Vector256.Create((byte)VectorizedIndexMask); |
| | 0 | 212 | | Vector256<byte> bitMaskLower = Avx2.Shuffle(charMapLower, index); |
| | 0 | 213 | | Vector256<byte> bitMaskUpper = Avx2.Shuffle(charMapUpper, index - Vector256.Create((byte)16)); |
| | 0 | 214 | | Vector256<byte> mask = Vector256.GreaterThan(index, Vector256.Create((byte)15)); |
| | 0 | 215 | | Vector256<byte> bitMask = Vector256.ConditionalSelect(mask, bitMaskUpper, bitMaskLower); |
| | | 216 | | |
| | 0 | 217 | | return Vector256.Equals(bitMask & bitPositions, Vector256<byte>.Zero); |
| | | 218 | | } |
| | | 219 | | |
| | | 220 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 221 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 222 | | [CompExactlyDependsOn(typeof(Sse2))] |
| | | 223 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 224 | | private static Vector128<byte> ContainsMask16Chars(Vector128<byte> charMapLower, Vector128<byte> charMapUpper, r |
| | | 225 | | { |
| | | 226 | | Vector128<ushort> source0 = Vector128.LoadUnsafe(ref searchSpace); |
| | 0 | 227 | | Vector128<ushort> source1 = Vector128.LoadUnsafe(ref searchSpace, (nuint)Vector128<ushort>.Count); |
| | | 228 | | |
| | | 229 | | Vector128<byte> sourceLower; |
| | | 230 | | Vector128<byte> sourceUpper; |
| | | 231 | | |
| | 0 | 232 | | if (Sse2.IsSupported) |
| | | 233 | | { |
| | 0 | 234 | | sourceLower = Sse2.PackUnsignedSaturate((source0 & Vector128.Create((ushort)255)).AsInt16(), (source1 & |
| | 0 | 235 | | sourceUpper = Sse2.PackUnsignedSaturate((source0 >>> 8).AsInt16(), (source1 >>> 8).AsInt16()); |
| | | 236 | | } |
| | | 237 | | else if (AdvSimd.Arm64.IsSupported) |
| | | 238 | | { |
| | | 239 | | sourceLower = AdvSimd.Arm64.UnzipEven(source0.AsByte(), source1.AsByte()); |
| | | 240 | | sourceUpper = AdvSimd.Arm64.UnzipOdd(source0.AsByte(), source1.AsByte()); |
| | | 241 | | } |
| | | 242 | | else if (PackedSimd.IsSupported) |
| | | 243 | | { |
| | | 244 | | sourceLower = PackedSimd.ConvertNarrowingSaturateUnsigned((source0 & Vector128.Create((ushort)255)).AsIn |
| | | 245 | | sourceUpper = PackedSimd.ConvertNarrowingSaturateUnsigned((source0 >>> 8).AsInt16(), (source1 >>> 8).AsI |
| | | 246 | | } |
| | | 247 | | else |
| | | 248 | | { |
| | | 249 | | // We explicitly recheck each IsSupported query to ensure that the trimmer can see which paths are live/ |
| | 0 | 250 | | ThrowHelper.ThrowUnreachableException(); |
| | | 251 | | |
| | | 252 | | sourceLower = default; |
| | | 253 | | sourceUpper = default; |
| | | 254 | | } |
| | | 255 | | |
| | 0 | 256 | | Vector128<byte> resultLower = IsCharBitNotSet(charMapLower, charMapUpper, sourceLower); |
| | 0 | 257 | | Vector128<byte> resultUpper = IsCharBitNotSet(charMapLower, charMapUpper, sourceUpper); |
| | | 258 | | |
| | 0 | 259 | | return ~(resultLower | resultUpper); |
| | | 260 | | } |
| | | 261 | | |
| | | 262 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 263 | | [CompExactlyDependsOn(typeof(Sse2))] |
| | | 264 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 265 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 266 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 267 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 268 | | private static Vector128<byte> IsCharBitNotSet(Vector128<byte> charMapLower, Vector128<byte> charMapUpper, Vecto |
| | | 269 | | { |
| | | 270 | | Vector128<byte> shifted = values >>> VectorizedIndexShift; |
| | | 271 | | |
| | 0 | 272 | | Vector128<byte> bitPositions = Vector128.ShuffleNative(Vector128.Create(0x8040201008040201).AsByte(), shifte |
| | | 273 | | |
| | 0 | 274 | | Vector128<byte> index = values & Vector128.Create((byte)VectorizedIndexMask); |
| | | 275 | | Vector128<byte> bitMask; |
| | | 276 | | |
| | | 277 | | if (AdvSimd.Arm64.IsSupported) |
| | | 278 | | { |
| | | 279 | | bitMask = AdvSimd.Arm64.VectorTableLookup((charMapLower, charMapUpper), index); |
| | | 280 | | } |
| | | 281 | | else |
| | | 282 | | { |
| | 0 | 283 | | Vector128<byte> bitMaskLower = Vector128.ShuffleNative(charMapLower, index); |
| | 0 | 284 | | Vector128<byte> bitMaskUpper = Vector128.ShuffleNative(charMapUpper, index - Vector128.Create((byte)16)) |
| | 0 | 285 | | Vector128<byte> mask = Vector128.GreaterThan(index, Vector128.Create((byte)15)); |
| | 0 | 286 | | bitMask = Vector128.ConditionalSelect(mask, bitMaskUpper, bitMaskLower); |
| | | 287 | | } |
| | | 288 | | |
| | 0 | 289 | | return Vector128.Equals(bitMask & bitPositions, Vector128<byte>.Zero); |
| | | 290 | | } |
| | | 291 | | |
| | | 292 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 293 | | private static bool ShouldUseSimpleLoop(int searchSpaceLength, int valuesLength) |
| | | 294 | | { |
| | | 295 | | // We can perform either |
| | | 296 | | // - a simple O(haystack * needle) search or |
| | | 297 | | // - compute a character map of the values in O(needle), followed by an O(haystack) search |
| | | 298 | | // As the constant factor to compute the character map is relatively high, it's more efficient |
| | | 299 | | // to perform a simple loop search for short inputs. |
| | | 300 | | // |
| | | 301 | | // The following check does an educated guess as to whether computing the bitmap is more expensive. |
| | | 302 | | // The limit of 20 on the haystack length is arbitrary, determined by experimentation. |
| | 0 | 303 | | return searchSpaceLength < Vector128<short>.Count |
| | 0 | 304 | | || (searchSpaceLength < 20 && searchSpaceLength < (valuesLength >> 1)); |
| | | 305 | | } |
| | | 306 | | |
| | | 307 | | public static int IndexOfAny(ref char searchSpace, int searchSpaceLength, ref char values, int valuesLength) |
| | | 308 | | { |
| | 0 | 309 | | var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); |
| | | 310 | | |
| | | 311 | | // If the search space is relatively short compared to the needle, do a simple O(n * m) search. |
| | 0 | 312 | | if (ShouldUseSimpleLoop(searchSpaceLength, valuesLength)) |
| | | 313 | | { |
| | 0 | 314 | | return IndexOfAnySimpleLoop<IndexOfAnyAsciiSearcher.DontNegate>(ref searchSpace, searchSpaceLength, valu |
| | | 315 | | } |
| | | 316 | | |
| | 0 | 317 | | if (IndexOfAnyAsciiSearcher.TryIndexOfAny(ref searchSpace, searchSpaceLength, valuesSpan, out int index)) |
| | | 318 | | { |
| | 0 | 319 | | return index; |
| | | 320 | | } |
| | | 321 | | |
| | 0 | 322 | | return ProbabilisticIndexOfAny(ref searchSpace, searchSpaceLength, ref values, valuesLength); |
| | | 323 | | } |
| | | 324 | | |
| | | 325 | | public static int IndexOfAnyExcept(ref char searchSpace, int searchSpaceLength, ref char values, int valuesLengt |
| | | 326 | | { |
| | 0 | 327 | | var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); |
| | | 328 | | |
| | 0 | 329 | | if (IndexOfAnyAsciiSearcher.IsVectorizationSupported && |
| | 0 | 330 | | !ShouldUseSimpleLoop(searchSpaceLength, valuesLength) && |
| | 0 | 331 | | IndexOfAnyAsciiSearcher.TryIndexOfAnyExcept(ref searchSpace, searchSpaceLength, valuesSpan, out int inde |
| | | 332 | | { |
| | 0 | 333 | | return index; |
| | | 334 | | } |
| | | 335 | | |
| | 0 | 336 | | return IndexOfAnySimpleLoop<IndexOfAnyAsciiSearcher.Negate>(ref searchSpace, searchSpaceLength, valuesSpan); |
| | | 337 | | } |
| | | 338 | | |
| | | 339 | | public static int LastIndexOfAny(ref char searchSpace, int searchSpaceLength, ref char values, int valuesLength) |
| | | 340 | | { |
| | 0 | 341 | | var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); |
| | | 342 | | |
| | | 343 | | // If the search space is relatively short compared to the needle, do a simple O(n * m) search. |
| | 0 | 344 | | if (ShouldUseSimpleLoop(searchSpaceLength, valuesLength)) |
| | | 345 | | { |
| | 0 | 346 | | return LastIndexOfAnySimpleLoop<IndexOfAnyAsciiSearcher.DontNegate>(ref searchSpace, searchSpaceLength, |
| | | 347 | | } |
| | | 348 | | |
| | 0 | 349 | | if (IndexOfAnyAsciiSearcher.TryLastIndexOfAny(ref searchSpace, searchSpaceLength, valuesSpan, out int index) |
| | | 350 | | { |
| | 0 | 351 | | return index; |
| | | 352 | | } |
| | | 353 | | |
| | 0 | 354 | | return ProbabilisticLastIndexOfAny(ref searchSpace, searchSpaceLength, ref values, valuesLength); |
| | | 355 | | } |
| | | 356 | | |
| | | 357 | | public static int LastIndexOfAnyExcept(ref char searchSpace, int searchSpaceLength, ref char values, int valuesL |
| | | 358 | | { |
| | 0 | 359 | | var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); |
| | | 360 | | |
| | 0 | 361 | | if (IndexOfAnyAsciiSearcher.IsVectorizationSupported && |
| | 0 | 362 | | !ShouldUseSimpleLoop(searchSpaceLength, valuesLength) && |
| | 0 | 363 | | IndexOfAnyAsciiSearcher.TryLastIndexOfAnyExcept(ref searchSpace, searchSpaceLength, valuesSpan, out int |
| | | 364 | | { |
| | 0 | 365 | | return index; |
| | | 366 | | } |
| | | 367 | | |
| | 0 | 368 | | return LastIndexOfAnySimpleLoop<IndexOfAnyAsciiSearcher.Negate>(ref searchSpace, searchSpaceLength, valuesSp |
| | | 369 | | } |
| | | 370 | | |
| | | 371 | | [MethodImpl(MethodImplOptions.NoInlining)] |
| | | 372 | | private static unsafe int ProbabilisticIndexOfAny(ref char searchSpace, int searchSpaceLength, ref char values, |
| | | 373 | | { |
| | 0 | 374 | | var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); |
| | | 375 | | |
| | | 376 | | // ProbabilisticMapState can hold either a precomputed hash table or a pointer to the values. |
| | | 377 | | // Precomputing the table is relatively expensive, so we only do it when using SearchValues where instances |
| | 0 | 378 | | var state = new ProbabilisticMapState(&valuesSpan); |
| | | 379 | | |
| | | 380 | | // The FalseConst here indicates that we can't use the fast character checks and must instead check the valu |
| | 0 | 381 | | return IndexOfAny<SearchValues.FalseConst>(ref searchSpace, searchSpaceLength, ref state); |
| | | 382 | | } |
| | | 383 | | |
| | | 384 | | [MethodImpl(MethodImplOptions.NoInlining)] |
| | | 385 | | private static unsafe int ProbabilisticLastIndexOfAny(ref char searchSpace, int searchSpaceLength, ref char valu |
| | | 386 | | { |
| | 0 | 387 | | var valuesSpan = new ReadOnlySpan<char>(ref values, valuesLength); |
| | | 388 | | |
| | | 389 | | // ProbabilisticMapState can hold either a precomputed hash table or a pointer to the values. |
| | | 390 | | // Precomputing the table is relatively expensive, so we only do it when using SearchValues where instances |
| | 0 | 391 | | var state = new ProbabilisticMapState(&valuesSpan); |
| | | 392 | | |
| | | 393 | | // The FalseConst here indicates that we can't use the fast character checks and must instead check the valu |
| | 0 | 394 | | return LastIndexOfAny<SearchValues.FalseConst>(ref searchSpace, searchSpaceLength, ref state); |
| | | 395 | | } |
| | | 396 | | |
| | | 397 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 398 | | internal static int IndexOfAny<TUseFastContains>(ref char searchSpace, int searchSpaceLength, ref ProbabilisticM |
| | | 399 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 400 | | { |
| | 6457 | 401 | | if ((Sse41.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.IsSupported) && searchSpaceLength >= 16) |
| | | 402 | | { |
| | 2709 | 403 | | return Vector512.IsHardwareAccelerated && Avx512Vbmi.VL.IsSupported |
| | 2709 | 404 | | ? IndexOfAnyVectorizedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, ref state) |
| | 2709 | 405 | | : IndexOfAnyVectorized<TUseFastContains>(ref searchSpace, searchSpaceLength, ref state); |
| | | 406 | | } |
| | | 407 | | |
| | 3748 | 408 | | return ProbabilisticMapState.IndexOfAnySimpleLoop<TUseFastContains, IndexOfAnyAsciiSearcher.DontNegate>(ref |
| | | 409 | | } |
| | | 410 | | |
| | | 411 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 412 | | internal static int LastIndexOfAny<TUseFastContains>(ref char searchSpace, int searchSpaceLength, ref Probabilis |
| | | 413 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 414 | | { |
| | 3398 | 415 | | if ((Sse41.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.IsSupported) && searchSpaceLength >= 16) |
| | | 416 | | { |
| | 1546 | 417 | | return Vector512.IsHardwareAccelerated && Avx512Vbmi.VL.IsSupported |
| | 1546 | 418 | | ? LastIndexOfAnyVectorizedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, ref state) |
| | 1546 | 419 | | : LastIndexOfAnyVectorized<TUseFastContains>(ref searchSpace, searchSpaceLength, ref state); |
| | | 420 | | } |
| | | 421 | | |
| | 1852 | 422 | | return ProbabilisticMapState.LastIndexOfAnySimpleLoop<TUseFastContains, IndexOfAnyAsciiSearcher.DontNegate>( |
| | | 423 | | } |
| | | 424 | | |
| | | 425 | | [CompExactlyDependsOn(typeof(Avx512Vbmi.VL))] |
| | | 426 | | private static int IndexOfAnyVectorizedAvx512<TUseFastContains>(ref char searchSpace, int searchSpaceLength, ref |
| | | 427 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 428 | | { |
| | 2709 | 429 | | Debug.Assert(Avx512Vbmi.VL.IsSupported); |
| | 2709 | 430 | | Debug.Assert(searchSpaceLength >= 16); |
| | | 431 | | |
| | 2709 | 432 | | ref char searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength); |
| | | 433 | | |
| | 2709 | 434 | | Vector256<byte> charMap256 = Vector256.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map)); |
| | | 435 | | |
| | 2709 | 436 | | if (searchSpaceLength > 32) |
| | | 437 | | { |
| | 2154 | 438 | | Vector512<byte> charMap512 = Vector512.Create(charMap256); |
| | | 439 | | |
| | 2154 | 440 | | if (searchSpaceLength > 64) |
| | | 441 | | { |
| | 1334 | 442 | | ref char cur = ref searchSpace; |
| | 1334 | 443 | | ref char lastStartVector = ref Unsafe.Subtract(ref searchSpaceEnd, 64); |
| | | 444 | | |
| | 591 | 445 | | while (true) |
| | | 446 | | { |
| | 6962 | 447 | | Vector512<byte> result = ContainsMask64CharsAvx512(charMap512, ref cur, ref Unsafe.Add(ref cur, |
| | | 448 | | |
| | 6962 | 449 | | if (result != Vector512<byte>.Zero) |
| | | 450 | | { |
| | 2687 | 451 | | if (TryFindMatchAvx512<TUseFastContains>(ref cur, result.ExtractMostSignificantBits(), ref s |
| | | 452 | | { |
| | 731 | 453 | | return MatchOffset(ref searchSpace, ref cur) + index; |
| | | 454 | | } |
| | | 455 | | } |
| | | 456 | | |
| | 6231 | 457 | | cur = ref Unsafe.Add(ref cur, 64); |
| | | 458 | | |
| | 6231 | 459 | | if (Unsafe.IsAddressGreaterThan(ref cur, ref lastStartVector)) |
| | | 460 | | { |
| | 1194 | 461 | | if (Unsafe.AreSame(ref cur, ref searchSpaceEnd)) |
| | | 462 | | { |
| | | 463 | | break; |
| | | 464 | | } |
| | | 465 | | |
| | | 466 | | // Adjust the current vector and do one last iteration. |
| | 591 | 467 | | cur = ref lastStartVector; |
| | | 468 | | } |
| | | 469 | | } |
| | | 470 | | } |
| | | 471 | | else |
| | | 472 | | { |
| | 820 | 473 | | Debug.Assert(searchSpaceLength is > 32 and <= 64); |
| | | 474 | | |
| | | 475 | | // Process the first and last vector in the search space. |
| | | 476 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 820 | 477 | | Vector512<byte> result = ContainsMask64CharsAvx512(charMap512, ref searchSpace, ref Unsafe.Subtract( |
| | | 478 | | |
| | 820 | 479 | | if (result != Vector512<byte>.Zero) |
| | | 480 | | { |
| | 805 | 481 | | if (TryFindMatchOverlappedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, result.Ex |
| | | 482 | | { |
| | 547 | 483 | | return index; |
| | | 484 | | } |
| | | 485 | | } |
| | | 486 | | } |
| | | 487 | | } |
| | | 488 | | else |
| | | 489 | | { |
| | 555 | 490 | | Debug.Assert(searchSpaceLength is >= 16 and <= 32); |
| | | 491 | | |
| | | 492 | | // Process the first and last vector in the search space. |
| | | 493 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 555 | 494 | | Vector256<byte> result = ContainsMask32CharsAvx512(charMap256, ref searchSpace, ref Unsafe.Subtract(ref |
| | | 495 | | |
| | 555 | 496 | | if (result != Vector256<byte>.Zero) |
| | | 497 | | { |
| | 531 | 498 | | if (TryFindMatchOverlappedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, result.Extrac |
| | | 499 | | { |
| | 363 | 500 | | return index; |
| | | 501 | | } |
| | | 502 | | } |
| | | 503 | | } |
| | | 504 | | |
| | 1068 | 505 | | return -1; |
| | | 506 | | } |
| | | 507 | | |
| | | 508 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 509 | | [CompExactlyDependsOn(typeof(Sse41))] |
| | | 510 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 511 | | private static int IndexOfAnyVectorized<TUseFastContains>(ref char searchSpace, int searchSpaceLength, ref Proba |
| | | 512 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 513 | | { |
| | 0 | 514 | | Debug.Assert(Sse41.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.IsSupported); |
| | 0 | 515 | | Debug.Assert(searchSpaceLength >= 16); |
| | | 516 | | |
| | 0 | 517 | | ref char searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength); |
| | 0 | 518 | | ref char cur = ref searchSpace; |
| | | 519 | | |
| | 0 | 520 | | Vector128<byte> charMapLower = Vector128.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map)); |
| | 0 | 521 | | Vector128<byte> charMapUpper = Vector128.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map), (n |
| | | 522 | | |
| | | 523 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // In this case, we have an else clau |
| | 0 | 524 | | if (Avx2.IsSupported && searchSpaceLength >= 32) |
| | | 525 | | #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 526 | | { |
| | 0 | 527 | | Vector256<byte> charMapLower256 = Vector256.Create(charMapLower); |
| | 0 | 528 | | Vector256<byte> charMapUpper256 = Vector256.Create(charMapUpper); |
| | | 529 | | |
| | 0 | 530 | | ref char lastStartVectorAvx2 = ref Unsafe.Subtract(ref searchSpaceEnd, 32); |
| | | 531 | | |
| | | 532 | | while (true) |
| | | 533 | | { |
| | 0 | 534 | | Vector256<byte> result = ContainsMask32CharsAvx2(charMapLower256, charMapUpper256, ref cur); |
| | | 535 | | |
| | 0 | 536 | | if (result != Vector256<byte>.Zero) |
| | | 537 | | { |
| | 0 | 538 | | if (TryFindMatch<TUseFastContains>(ref cur, PackedSpanHelpers.FixUpPackedVector256Result(result) |
| | | 539 | | { |
| | 0 | 540 | | return MatchOffset(ref searchSpace, ref cur) + index; |
| | | 541 | | } |
| | | 542 | | } |
| | | 543 | | |
| | 0 | 544 | | cur = ref Unsafe.Add(ref cur, 32); |
| | | 545 | | |
| | 0 | 546 | | if (Unsafe.IsAddressGreaterThan(ref cur, ref lastStartVectorAvx2)) |
| | | 547 | | { |
| | 0 | 548 | | if (Unsafe.AreSame(ref cur, ref searchSpaceEnd)) |
| | | 549 | | { |
| | 0 | 550 | | return -1; |
| | | 551 | | } |
| | | 552 | | |
| | 0 | 553 | | if (Unsafe.ByteOffset(ref cur, ref searchSpaceEnd) > 16 * sizeof(char)) |
| | | 554 | | { |
| | | 555 | | // If we have more than 16 characters left to process, we can |
| | | 556 | | // adjust the current vector and do one last iteration of Avx2. |
| | 0 | 557 | | cur = ref lastStartVectorAvx2; |
| | | 558 | | } |
| | | 559 | | else |
| | | 560 | | { |
| | | 561 | | // Otherwise adjust the vector such that we'll only need to do a single |
| | | 562 | | // iteration of ContainsMask16Chars below. |
| | 0 | 563 | | cur = ref Unsafe.Subtract(ref searchSpaceEnd, 16); |
| | | 564 | | break; |
| | | 565 | | } |
| | | 566 | | } |
| | | 567 | | } |
| | | 568 | | } |
| | | 569 | | |
| | 0 | 570 | | ref char lastStartVector = ref Unsafe.Subtract(ref searchSpaceEnd, 16); |
| | | 571 | | |
| | 0 | 572 | | while (true) |
| | | 573 | | { |
| | 0 | 574 | | Vector128<byte> result = ContainsMask16Chars(charMapLower, charMapUpper, ref cur); |
| | | 575 | | |
| | 0 | 576 | | if (result != Vector128<byte>.Zero) |
| | | 577 | | { |
| | 0 | 578 | | if (TryFindMatch<TUseFastContains>(ref cur, result.ExtractMostSignificantBits(), ref state, out int |
| | | 579 | | { |
| | 0 | 580 | | return MatchOffset(ref searchSpace, ref cur) + index; |
| | | 581 | | } |
| | | 582 | | } |
| | | 583 | | |
| | 0 | 584 | | cur = ref Unsafe.Add(ref cur, 16); |
| | | 585 | | |
| | 0 | 586 | | if (Unsafe.IsAddressGreaterThan(ref cur, ref lastStartVector)) |
| | | 587 | | { |
| | 0 | 588 | | if (Unsafe.AreSame(ref cur, ref searchSpaceEnd)) |
| | | 589 | | { |
| | | 590 | | break; |
| | | 591 | | } |
| | | 592 | | |
| | | 593 | | // Adjust the current vector and do one last iteration. |
| | 0 | 594 | | cur = ref lastStartVector; |
| | | 595 | | } |
| | | 596 | | } |
| | | 597 | | |
| | 0 | 598 | | return -1; |
| | | 599 | | } |
| | | 600 | | |
| | | 601 | | [CompExactlyDependsOn(typeof(Avx512Vbmi.VL))] |
| | | 602 | | private static int LastIndexOfAnyVectorizedAvx512<TUseFastContains>(ref char searchSpace, int searchSpaceLength, |
| | | 603 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 604 | | { |
| | 1546 | 605 | | Debug.Assert(Avx512Vbmi.VL.IsSupported); |
| | 1546 | 606 | | Debug.Assert(searchSpaceLength >= 16); |
| | | 607 | | |
| | 1546 | 608 | | ref char cur = ref Unsafe.Add(ref searchSpace, searchSpaceLength); |
| | | 609 | | |
| | 1546 | 610 | | Vector256<byte> charMap256 = Vector256.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map)); |
| | | 611 | | |
| | 1546 | 612 | | if (searchSpaceLength > 32) |
| | | 613 | | { |
| | 1210 | 614 | | Vector512<byte> charMap512 = Vector512.Create(charMap256); |
| | | 615 | | |
| | 1210 | 616 | | if (searchSpaceLength > 64) |
| | | 617 | | { |
| | 740 | 618 | | ref char lastStartVector = ref Unsafe.Add(ref searchSpace, 64); |
| | | 619 | | |
| | 400 | 620 | | while (true) |
| | | 621 | | { |
| | 4156 | 622 | | Debug.Assert(Unsafe.ByteOffset(ref searchSpace, ref cur) >= 64 * sizeof(char)); |
| | | 623 | | |
| | 4156 | 624 | | cur = ref Unsafe.Subtract(ref cur, 64); |
| | | 625 | | |
| | 4156 | 626 | | Vector512<byte> result = ContainsMask64CharsAvx512(charMap512, ref cur, ref Unsafe.Add(ref cur, |
| | | 627 | | |
| | 4156 | 628 | | if (result != Vector512<byte>.Zero) |
| | | 629 | | { |
| | 1510 | 630 | | if (TryFindLastMatchAvx512<TUseFastContains>(ref cur, result.ExtractMostSignificantBits(), r |
| | | 631 | | { |
| | 352 | 632 | | return MatchOffset(ref searchSpace, ref cur) + index; |
| | | 633 | | } |
| | | 634 | | } |
| | | 635 | | |
| | 3804 | 636 | | if (Unsafe.IsAddressLessThanOrEqualTo(ref cur, ref lastStartVector)) |
| | | 637 | | { |
| | 788 | 638 | | if (Unsafe.AreSame(ref cur, ref searchSpace)) |
| | | 639 | | { |
| | | 640 | | break; |
| | | 641 | | } |
| | | 642 | | |
| | | 643 | | // Adjust the current vector and do one last iteration. |
| | 400 | 644 | | cur = ref lastStartVector; |
| | | 645 | | } |
| | | 646 | | } |
| | | 647 | | } |
| | | 648 | | else |
| | | 649 | | { |
| | 470 | 650 | | Debug.Assert(searchSpaceLength is > 32 and <= 64); |
| | 470 | 651 | | Debug.Assert(Unsafe.ByteOffset(ref searchSpace, ref cur) >= 32 * sizeof(char)); |
| | | 652 | | |
| | | 653 | | // Process the first and last vector in the search space. |
| | | 654 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 470 | 655 | | Vector512<byte> result = ContainsMask64CharsAvx512(charMap512, ref searchSpace, ref Unsafe.Subtract( |
| | | 656 | | |
| | 470 | 657 | | if (result != Vector512<byte>.Zero) |
| | | 658 | | { |
| | 458 | 659 | | if (TryFindLastMatchOverlappedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, resul |
| | | 660 | | { |
| | 292 | 661 | | return index; |
| | | 662 | | } |
| | | 663 | | } |
| | | 664 | | } |
| | | 665 | | } |
| | | 666 | | else |
| | | 667 | | { |
| | 336 | 668 | | Debug.Assert(searchSpaceLength is >= 16 and <= 32); |
| | 336 | 669 | | Debug.Assert(Unsafe.ByteOffset(ref searchSpace, ref cur) >= 16 * sizeof(char)); |
| | | 670 | | |
| | | 671 | | // Process the first and last vector in the search space. |
| | | 672 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 336 | 673 | | Vector256<byte> result = ContainsMask32CharsAvx512(charMap256, ref searchSpace, ref Unsafe.Subtract(ref |
| | | 674 | | |
| | 336 | 675 | | if (result != Vector256<byte>.Zero) |
| | | 676 | | { |
| | 320 | 677 | | if (TryFindLastMatchOverlappedAvx512<TUseFastContains>(ref searchSpace, searchSpaceLength, result.Ex |
| | | 678 | | { |
| | 198 | 679 | | return index; |
| | | 680 | | } |
| | | 681 | | } |
| | | 682 | | } |
| | | 683 | | |
| | 704 | 684 | | return -1; |
| | | 685 | | } |
| | | 686 | | |
| | | 687 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 688 | | [CompExactlyDependsOn(typeof(Sse41))] |
| | | 689 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 690 | | private static int LastIndexOfAnyVectorized<TUseFastContains>(ref char searchSpace, int searchSpaceLength, ref P |
| | | 691 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 692 | | { |
| | 0 | 693 | | Debug.Assert(Sse41.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.IsSupported); |
| | 0 | 694 | | Debug.Assert(searchSpaceLength >= 16); |
| | | 695 | | |
| | 0 | 696 | | ref char cur = ref Unsafe.Add(ref searchSpace, searchSpaceLength); |
| | | 697 | | |
| | 0 | 698 | | Vector128<byte> charMapLower = Vector128.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map)); |
| | 0 | 699 | | Vector128<byte> charMapUpper = Vector128.LoadUnsafe(ref Unsafe.As<ProbabilisticMap, byte>(ref state.Map), (n |
| | | 700 | | |
| | | 701 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // In this case, we have an else clau |
| | 0 | 702 | | if (Avx2.IsSupported && searchSpaceLength >= 32) |
| | | 703 | | #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 704 | | { |
| | 0 | 705 | | Vector256<byte> charMapLower256 = Vector256.Create(charMapLower); |
| | 0 | 706 | | Vector256<byte> charMapUpper256 = Vector256.Create(charMapUpper); |
| | | 707 | | |
| | 0 | 708 | | ref char lastStartVectorAvx2 = ref Unsafe.Add(ref searchSpace, 32); |
| | | 709 | | |
| | | 710 | | while (true) |
| | | 711 | | { |
| | 0 | 712 | | Debug.Assert(Unsafe.ByteOffset(ref searchSpace, ref cur) >= 32 * sizeof(char)); |
| | | 713 | | |
| | 0 | 714 | | cur = ref Unsafe.Subtract(ref cur, 32); |
| | | 715 | | |
| | 0 | 716 | | Vector256<byte> result = ContainsMask32CharsAvx2(charMapLower256, charMapUpper256, ref cur); |
| | | 717 | | |
| | 0 | 718 | | if (result != Vector256<byte>.Zero) |
| | | 719 | | { |
| | 0 | 720 | | if (TryFindLastMatch<TUseFastContains>(ref cur, PackedSpanHelpers.FixUpPackedVector256Result(res |
| | | 721 | | { |
| | 0 | 722 | | return MatchOffset(ref searchSpace, ref cur) + index; |
| | | 723 | | } |
| | | 724 | | } |
| | | 725 | | |
| | 0 | 726 | | if (Unsafe.IsAddressLessThanOrEqualTo(ref cur, ref lastStartVectorAvx2)) |
| | | 727 | | { |
| | 0 | 728 | | if (Unsafe.AreSame(ref cur, ref searchSpace)) |
| | | 729 | | { |
| | 0 | 730 | | return -1; |
| | | 731 | | } |
| | | 732 | | |
| | 0 | 733 | | if (Unsafe.ByteOffset(ref searchSpace, ref cur) > 16 * sizeof(char)) |
| | | 734 | | { |
| | | 735 | | // If we have more than 16 characters left to process, we can |
| | | 736 | | // adjust the current vector and do one last iteration of Avx2. |
| | 0 | 737 | | cur = ref lastStartVectorAvx2; |
| | | 738 | | } |
| | | 739 | | else |
| | | 740 | | { |
| | | 741 | | // Otherwise adjust the vector such that we'll only need to do a single |
| | | 742 | | // iteration of ContainsMask16Chars below. |
| | 0 | 743 | | cur = ref Unsafe.Add(ref searchSpace, 16); |
| | | 744 | | break; |
| | | 745 | | } |
| | | 746 | | } |
| | | 747 | | } |
| | | 748 | | } |
| | | 749 | | |
| | 0 | 750 | | ref char lastStartVector = ref Unsafe.Add(ref searchSpace, 16); |
| | | 751 | | |
| | 0 | 752 | | while (true) |
| | | 753 | | { |
| | 0 | 754 | | Debug.Assert(Unsafe.ByteOffset(ref searchSpace, ref cur) >= 16 * sizeof(char)); |
| | | 755 | | |
| | 0 | 756 | | cur = ref Unsafe.Subtract(ref cur, 16); |
| | | 757 | | |
| | 0 | 758 | | Vector128<byte> result = ContainsMask16Chars(charMapLower, charMapUpper, ref cur); |
| | | 759 | | |
| | 0 | 760 | | if (result != Vector128<byte>.Zero) |
| | | 761 | | { |
| | 0 | 762 | | if (TryFindLastMatch<TUseFastContains>(ref cur, result.ExtractMostSignificantBits(), ref state, out |
| | | 763 | | { |
| | 0 | 764 | | return MatchOffset(ref searchSpace, ref cur) + index; |
| | | 765 | | } |
| | | 766 | | } |
| | | 767 | | |
| | 0 | 768 | | if (Unsafe.IsAddressLessThanOrEqualTo(ref cur, ref lastStartVector)) |
| | | 769 | | { |
| | 0 | 770 | | if (Unsafe.AreSame(ref cur, ref searchSpace)) |
| | | 771 | | { |
| | | 772 | | break; |
| | | 773 | | } |
| | | 774 | | |
| | | 775 | | // Adjust the current vector and do one last iteration. |
| | 0 | 776 | | cur = ref lastStartVector; |
| | | 777 | | } |
| | | 778 | | } |
| | | 779 | | |
| | 0 | 780 | | return -1; |
| | | 781 | | } |
| | | 782 | | |
| | | 783 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 784 | | private static int MatchOffset(ref char searchSpace, ref char cur) => |
| | 1083 | 785 | | (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref cur) / sizeof(char)); |
| | | 786 | | |
| | | 787 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 788 | | private static bool TryFindMatch<TUseFastContains>(ref char cur, uint mask, ref ProbabilisticMapState state, out |
| | | 789 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 790 | | { |
| | | 791 | | do |
| | | 792 | | { |
| | 0 | 793 | | index = BitOperations.TrailingZeroCount(mask); |
| | | 794 | | |
| | 0 | 795 | | if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) |
| | | 796 | | { |
| | 0 | 797 | | return true; |
| | | 798 | | } |
| | | 799 | | |
| | 0 | 800 | | mask = BitOperations.ResetLowestSetBit(mask); |
| | | 801 | | } |
| | 0 | 802 | | while (mask != 0); |
| | | 803 | | |
| | 0 | 804 | | index = 0; |
| | 0 | 805 | | return false; |
| | | 806 | | } |
| | | 807 | | |
| | | 808 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 809 | | private static bool TryFindMatchOverlappedAvx512<TUseFastContains>(ref char cur, int searchSpaceLength, uint mas |
| | | 810 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 811 | | { |
| | | 812 | | do |
| | | 813 | | { |
| | 3270 | 814 | | index = BitOperations.TrailingZeroCount(mask); |
| | | 815 | | |
| | 3270 | 816 | | if (index >= Vector256<ushort>.Count) |
| | | 817 | | { |
| | | 818 | | // The potential match is in the second vector. |
| | | 819 | | // Fixup the index to account for how we loaded the second overlapped vector. |
| | 1314 | 820 | | index += searchSpaceLength - (2 * Vector256<ushort>.Count); |
| | | 821 | | } |
| | | 822 | | |
| | 3270 | 823 | | if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) |
| | | 824 | | { |
| | 363 | 825 | | return true; |
| | | 826 | | } |
| | | 827 | | |
| | 2907 | 828 | | mask = BitOperations.ResetLowestSetBit(mask); |
| | | 829 | | } |
| | 2907 | 830 | | while (mask != 0); |
| | | 831 | | |
| | 168 | 832 | | index = 0; |
| | 168 | 833 | | return false; |
| | | 834 | | } |
| | | 835 | | |
| | | 836 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 837 | | private static bool TryFindMatchAvx512<TUseFastContains>(ref char cur, ulong mask, ref ProbabilisticMapState sta |
| | | 838 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 839 | | { |
| | | 840 | | do |
| | | 841 | | { |
| | 54407 | 842 | | index = BitOperations.TrailingZeroCount(mask); |
| | | 843 | | |
| | 54407 | 844 | | if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) |
| | | 845 | | { |
| | 731 | 846 | | return true; |
| | | 847 | | } |
| | | 848 | | |
| | 53676 | 849 | | mask = BitOperations.ResetLowestSetBit(mask); |
| | | 850 | | } |
| | 53676 | 851 | | while (mask != 0); |
| | | 852 | | |
| | 1956 | 853 | | index = 0; |
| | 1956 | 854 | | return false; |
| | | 855 | | } |
| | | 856 | | |
| | | 857 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 858 | | private static bool TryFindMatchOverlappedAvx512<TUseFastContains>(ref char cur, int searchSpaceLength, ulong ma |
| | | 859 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 860 | | { |
| | | 861 | | do |
| | | 862 | | { |
| | 8101 | 863 | | index = BitOperations.TrailingZeroCount(mask); |
| | | 864 | | |
| | 8101 | 865 | | if (index >= Vector512<ushort>.Count) |
| | | 866 | | { |
| | | 867 | | // The potential match is in the second vector. |
| | | 868 | | // Fixup the index to account for how we loaded the second overlapped vector. |
| | 3171 | 869 | | index += searchSpaceLength - (2 * Vector512<ushort>.Count); |
| | | 870 | | } |
| | | 871 | | |
| | 8101 | 872 | | if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) |
| | | 873 | | { |
| | 547 | 874 | | return true; |
| | | 875 | | } |
| | | 876 | | |
| | 7554 | 877 | | mask = BitOperations.ResetLowestSetBit(mask); |
| | | 878 | | } |
| | 7554 | 879 | | while (mask != 0); |
| | | 880 | | |
| | 258 | 881 | | index = 0; |
| | 258 | 882 | | return false; |
| | | 883 | | } |
| | | 884 | | |
| | | 885 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 886 | | private static bool TryFindLastMatch<TUseFastContains>(ref char cur, uint mask, ref ProbabilisticMapState state, |
| | | 887 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 888 | | { |
| | | 889 | | do |
| | | 890 | | { |
| | 0 | 891 | | index = 31 - BitOperations.LeadingZeroCount(mask); |
| | | 892 | | |
| | 0 | 893 | | if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) |
| | | 894 | | { |
| | 0 | 895 | | return true; |
| | | 896 | | } |
| | | 897 | | |
| | | 898 | | // Clear the highest set bit |
| | 0 | 899 | | mask = BitOperations.FlipBit(mask, index); |
| | | 900 | | } |
| | 0 | 901 | | while (mask != 0); |
| | | 902 | | |
| | 0 | 903 | | index = 0; |
| | 0 | 904 | | return false; |
| | | 905 | | } |
| | | 906 | | |
| | | 907 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 908 | | private static bool TryFindLastMatchOverlappedAvx512<TUseFastContains>(ref char cur, int searchSpaceLength, uint |
| | | 909 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 910 | | { |
| | | 911 | | do |
| | | 912 | | { |
| | 2182 | 913 | | index = 31 - BitOperations.LeadingZeroCount(mask); |
| | | 914 | | |
| | | 915 | | // Clear the highest set bit |
| | 2182 | 916 | | mask = BitOperations.FlipBit(mask, index); |
| | | 917 | | |
| | 2182 | 918 | | if (index >= Vector256<ushort>.Count) |
| | | 919 | | { |
| | | 920 | | // The potential match is in the second vector. |
| | | 921 | | // Fixup the index to account for how we loaded the second overlapped vector. |
| | 1270 | 922 | | index += searchSpaceLength - (2 * Vector256<ushort>.Count); |
| | | 923 | | } |
| | | 924 | | |
| | 2182 | 925 | | if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) |
| | | 926 | | { |
| | 198 | 927 | | return true; |
| | | 928 | | } |
| | | 929 | | } |
| | 1984 | 930 | | while (mask != 0); |
| | | 931 | | |
| | 122 | 932 | | index = 0; |
| | 122 | 933 | | return false; |
| | | 934 | | } |
| | | 935 | | |
| | | 936 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 937 | | private static bool TryFindLastMatchAvx512<TUseFastContains>(ref char cur, ulong mask, ref ProbabilisticMapState |
| | | 938 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 939 | | { |
| | | 940 | | do |
| | | 941 | | { |
| | 32170 | 942 | | index = 63 - BitOperations.LeadingZeroCount(mask); |
| | | 943 | | |
| | 32170 | 944 | | if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) |
| | | 945 | | { |
| | 352 | 946 | | return true; |
| | | 947 | | } |
| | | 948 | | |
| | | 949 | | // Clear the highest set bit |
| | 31818 | 950 | | mask = BitOperations.FlipBit(mask, index); |
| | | 951 | | } |
| | 31818 | 952 | | while (mask != 0); |
| | | 953 | | |
| | 1158 | 954 | | index = 0; |
| | 1158 | 955 | | return false; |
| | | 956 | | } |
| | | 957 | | |
| | | 958 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 959 | | private static bool TryFindLastMatchOverlappedAvx512<TUseFastContains>(ref char cur, int searchSpaceLength, ulon |
| | | 960 | | where TUseFastContains : struct, SearchValues.IRuntimeConst |
| | | 961 | | { |
| | | 962 | | do |
| | | 963 | | { |
| | 4420 | 964 | | index = 63 - BitOperations.LeadingZeroCount(mask); |
| | | 965 | | |
| | | 966 | | // Clear the highest set bit |
| | 4420 | 967 | | mask = BitOperations.FlipBit(mask, index); |
| | | 968 | | |
| | 4420 | 969 | | if (index >= Vector512<ushort>.Count) |
| | | 970 | | { |
| | | 971 | | // The potential match is in the second vector. |
| | | 972 | | // Fixup the index to account for how we loaded the second overlapped vector. |
| | 2528 | 973 | | index += searchSpaceLength - (2 * Vector512<ushort>.Count); |
| | | 974 | | } |
| | | 975 | | |
| | 4420 | 976 | | if (state.ConfirmProbabilisticMatch<TUseFastContains>(Unsafe.Add(ref cur, index))) |
| | | 977 | | { |
| | 292 | 978 | | return true; |
| | | 979 | | } |
| | | 980 | | } |
| | 4128 | 981 | | while (mask != 0); |
| | | 982 | | |
| | 166 | 983 | | index = 0; |
| | 166 | 984 | | return false; |
| | | 985 | | } |
| | | 986 | | |
| | | 987 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 988 | | internal static int IndexOfAnySimpleLoop<TNegator>(ref char searchSpace, int searchSpaceLength, ReadOnlySpan<cha |
| | | 989 | | where TNegator : struct, IndexOfAnyAsciiSearcher.INegator |
| | | 990 | | { |
| | 0 | 991 | | ref char searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength); |
| | 0 | 992 | | ref char cur = ref searchSpace; |
| | | 993 | | |
| | 0 | 994 | | while (!Unsafe.AreSame(ref cur, ref searchSpaceEnd)) |
| | | 995 | | { |
| | 0 | 996 | | char c = cur; |
| | 0 | 997 | | if (TNegator.NegateIfNeeded(Contains(values, c))) |
| | | 998 | | { |
| | 0 | 999 | | return MatchOffset(ref searchSpace, ref cur); |
| | | 1000 | | } |
| | | 1001 | | |
| | 0 | 1002 | | cur = ref Unsafe.Add(ref cur, 1); |
| | | 1003 | | } |
| | | 1004 | | |
| | 0 | 1005 | | return -1; |
| | | 1006 | | } |
| | | 1007 | | |
| | | 1008 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1009 | | internal static int LastIndexOfAnySimpleLoop<TNegator>(ref char searchSpace, int searchSpaceLength, ReadOnlySpan |
| | | 1010 | | where TNegator : struct, IndexOfAnyAsciiSearcher.INegator |
| | | 1011 | | { |
| | 0 | 1012 | | for (int i = searchSpaceLength - 1; i >= 0; i--) |
| | | 1013 | | { |
| | 0 | 1014 | | char c = Unsafe.Add(ref searchSpace, i); |
| | 0 | 1015 | | if (TNegator.NegateIfNeeded(Contains(values, c))) |
| | | 1016 | | { |
| | 0 | 1017 | | return i; |
| | | 1018 | | } |
| | | 1019 | | } |
| | | 1020 | | |
| | 0 | 1021 | | return -1; |
| | | 1022 | | } |
| | | 1023 | | } |
| | | 1024 | | } |
| | | 1025 | | |