| | | 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.Diagnostics.CodeAnalysis; |
| | | 6 | | using System.Numerics; |
| | | 7 | | using System.Runtime.CompilerServices; |
| | | 8 | | using System.Runtime.Intrinsics; |
| | | 9 | | using System.Runtime.Intrinsics.Arm; |
| | | 10 | | using System.Runtime.Intrinsics.Wasm; |
| | | 11 | | using System.Runtime.Intrinsics.X86; |
| | | 12 | | |
| | | 13 | | namespace System.Buffers |
| | | 14 | | { |
| | | 15 | | internal static class IndexOfAnyAsciiSearcher |
| | | 16 | | { |
| | | 17 | | // Reused for both ASCII and UniqueLowNibble searches since the state looks the same (a Vector128<byte>). |
| | | 18 | | public struct AsciiState(Vector128<byte> bitmap, BitVector256 lookup) |
| | | 19 | | { |
| | 0 | 20 | | public Vector256<byte> Bitmap = Vector256.Create(bitmap); |
| | 0 | 21 | | public readonly BitVector256 Lookup = lookup; |
| | | 22 | | |
| | | 23 | | public readonly AsciiState CreateInverse() => |
| | 0 | 24 | | new AsciiState(~Bitmap._lower, Lookup.CreateInverse()); |
| | | 25 | | } |
| | | 26 | | |
| | | 27 | | public readonly struct AnyByteState(Vector128<byte> bitmap0, Vector128<byte> bitmap1, BitVector256 lookup) |
| | | 28 | | { |
| | 0 | 29 | | public readonly Vector256<byte> Bitmap0 = Vector256.Create(bitmap0); |
| | 0 | 30 | | public readonly Vector256<byte> Bitmap1 = Vector256.Create(bitmap1); |
| | 0 | 31 | | public readonly BitVector256 Lookup = lookup; |
| | | 32 | | } |
| | | 33 | | |
| | 0 | 34 | | internal static bool IsVectorizationSupported => Ssse3.IsSupported || AdvSimd.Arm64.IsSupported || PackedSimd.Is |
| | | 35 | | |
| | | 36 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 37 | | private static void SetBitmapBit(ref InlineArray16<byte> bitmap, int value) |
| | | 38 | | { |
| | 0 | 39 | | Debug.Assert((uint)value <= 127); |
| | | 40 | | |
| | 0 | 41 | | int highNibble = value >> 4; |
| | 0 | 42 | | int lowNibble = value & 0xF; |
| | 0 | 43 | | bitmap[lowNibble] |= (byte)(1 << highNibble); |
| | 0 | 44 | | } |
| | | 45 | | |
| | | 46 | | internal static void ComputeAnyByteState(ReadOnlySpan<byte> values, out AnyByteState state) |
| | | 47 | | { |
| | | 48 | | // The exact format of these bitmaps differs from the other ComputeBitmap overloads as it's meant for the fu |
| | | 49 | | // See http://0x80.pl/articles/simd-byte-lookup.html#universal-algorithm |
| | | 50 | | |
| | 0 | 51 | | InlineArray16<byte> bitmapSpace0 = default; |
| | 0 | 52 | | InlineArray16<byte> bitmapSpace1 = default; |
| | 0 | 53 | | BitVector256 lookupLocal = default; |
| | | 54 | | |
| | 0 | 55 | | foreach (byte b in values) |
| | | 56 | | { |
| | 0 | 57 | | lookupLocal.Set(b); |
| | | 58 | | |
| | 0 | 59 | | if (b < 128) |
| | | 60 | | { |
| | 0 | 61 | | SetBitmapBit(ref bitmapSpace0, b); |
| | | 62 | | } |
| | | 63 | | else |
| | | 64 | | { |
| | 0 | 65 | | SetBitmapBit(ref bitmapSpace1, b - 128); |
| | | 66 | | } |
| | | 67 | | } |
| | | 68 | | |
| | 0 | 69 | | state = new AnyByteState(Vector128.Create<byte>(bitmapSpace0), Vector128.Create<byte>(bitmapSpace1), lookupL |
| | 0 | 70 | | } |
| | | 71 | | |
| | | 72 | | internal static void ComputeAsciiState<T>(ReadOnlySpan<T> values, out AsciiState state) |
| | | 73 | | where T : struct, IUnsignedNumber<T> |
| | | 74 | | { |
| | 0 | 75 | | Debug.Assert(typeof(T) == typeof(byte) || typeof(T) == typeof(char)); |
| | | 76 | | |
| | 0 | 77 | | InlineArray16<byte> bitmapSpace = default; |
| | 0 | 78 | | BitVector256 lookupLocal = default; |
| | | 79 | | |
| | 0 | 80 | | foreach (T tValue in values) |
| | | 81 | | { |
| | 0 | 82 | | int value = int.CreateChecked(tValue); |
| | | 83 | | |
| | 0 | 84 | | if (value > 127) |
| | | 85 | | { |
| | | 86 | | continue; |
| | | 87 | | } |
| | | 88 | | |
| | 0 | 89 | | lookupLocal.Set(value); |
| | 0 | 90 | | SetBitmapBit(ref bitmapSpace, value); |
| | | 91 | | } |
| | | 92 | | |
| | 0 | 93 | | state = new AsciiState(Vector128.Create<byte>(bitmapSpace), lookupLocal); |
| | 0 | 94 | | } |
| | | 95 | | |
| | | 96 | | public static bool CanUseUniqueLowNibbleSearch<T>(ReadOnlySpan<T> values, int maxInclusive) |
| | | 97 | | where T : struct, IUnsignedNumber<T> |
| | | 98 | | { |
| | 0 | 99 | | Debug.Assert(typeof(T) == typeof(byte) || typeof(T) == typeof(char)); |
| | | 100 | | |
| | 0 | 101 | | if (!IsVectorizationSupported || values.Length > 16) |
| | | 102 | | { |
| | 0 | 103 | | return false; |
| | | 104 | | } |
| | | 105 | | |
| | 0 | 106 | | if (Ssse3.IsSupported && maxInclusive > 127) |
| | | 107 | | { |
| | | 108 | | // We could support values higher than 127 if we did the "& 0xF" before calling into Shuffle in IndexOfA |
| | | 109 | | // We currently optimize for the common case of ASCII characters instead, saving an instruction there. |
| | 0 | 110 | | return false; |
| | | 111 | | } |
| | | 112 | | |
| | 0 | 113 | | if (typeof(T) == typeof(char) && maxInclusive >= byte.MaxValue) |
| | | 114 | | { |
| | | 115 | | // When packing UTF-16 characters into bytes, values may saturate to 255 (false positives), hence ">=" i |
| | 0 | 116 | | return false; |
| | | 117 | | } |
| | | 118 | | |
| | | 119 | | // We assume there are no duplicates to simplify the logic (if there are any, they just won't use this searc |
| | 0 | 120 | | int seenNibbles = 0; |
| | | 121 | | |
| | 0 | 122 | | foreach (T tValue in values) |
| | | 123 | | { |
| | 0 | 124 | | int bit = 1 << (int.CreateChecked(tValue) & 0xF); |
| | | 125 | | |
| | 0 | 126 | | if ((seenNibbles & bit) != 0) |
| | | 127 | | { |
| | | 128 | | // We already saw a value with the same low nibble. |
| | 0 | 129 | | return false; |
| | | 130 | | } |
| | | 131 | | |
| | 0 | 132 | | seenNibbles |= bit; |
| | | 133 | | } |
| | | 134 | | |
| | 0 | 135 | | return true; |
| | | 136 | | } |
| | | 137 | | |
| | | 138 | | public static void ComputeUniqueLowNibbleState<T>(ReadOnlySpan<T> values, out AsciiState state) |
| | | 139 | | where T : struct, IUnsignedNumber<T> |
| | | 140 | | { |
| | 0 | 141 | | Debug.Assert(typeof(T) == typeof(byte) || typeof(T) == typeof(char)); |
| | | 142 | | |
| | 0 | 143 | | InlineArray16<byte> valuesByLowNibble = default; |
| | 0 | 144 | | BitVector256 lookup = default; |
| | | 145 | | |
| | 0 | 146 | | foreach (T tValue in values) |
| | | 147 | | { |
| | 0 | 148 | | byte value = byte.CreateTruncating(tValue); |
| | 0 | 149 | | lookup.Set(value); |
| | 0 | 150 | | valuesByLowNibble[value & 0xF] = value; |
| | | 151 | | } |
| | | 152 | | |
| | | 153 | | // Elements of 'valuesByLowNibble' where no value had that low nibble will be left uninitialized at 0. |
| | | 154 | | // For most, that is okay, as only the zero character in the input could ever match against them, |
| | | 155 | | // but where such input characters will always be mapped to the 0th element of 'valuesByLowNibble'. |
| | | 156 | | // |
| | | 157 | | // That does mean we could still see false positivies if none of the values had a low nibble of zero. |
| | | 158 | | // To avoid that, we can replace the 0th element with any other byte that has a non-zero low nibble. |
| | | 159 | | // The zero character will no longer match, and the new value we pick won't match either as |
| | | 160 | | // it will be mapped to a different element in 'valuesByLowNibble' given its non-zero low nibble. |
| | 0 | 161 | | if (valuesByLowNibble[0] == 0 && !lookup.Contains(0)) |
| | | 162 | | { |
| | 0 | 163 | | valuesByLowNibble[0] = 1; |
| | | 164 | | } |
| | | 165 | | |
| | 0 | 166 | | state = new AsciiState(Vector128.Create<byte>(valuesByLowNibble), lookup); |
| | 0 | 167 | | } |
| | | 168 | | |
| | | 169 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 170 | | private static unsafe bool TryComputeBitmap(ReadOnlySpan<char> values, byte* bitmap, out bool needleContainsZero |
| | | 171 | | { |
| | 0 | 172 | | byte* bitmapLocal = bitmap; // https://github.com/dotnet/runtime/issues/9040 |
| | | 173 | | |
| | 0 | 174 | | foreach (char c in values) |
| | | 175 | | { |
| | 0 | 176 | | if (c > 127) |
| | | 177 | | { |
| | 0 | 178 | | needleContainsZero = false; |
| | 0 | 179 | | return false; |
| | | 180 | | } |
| | | 181 | | |
| | 0 | 182 | | bitmapLocal[c & 0xF] |= (byte)(1 << (c >> 4)); |
| | | 183 | | } |
| | | 184 | | |
| | 0 | 185 | | needleContainsZero = (bitmap[0] & 1) != 0; |
| | 0 | 186 | | return true; |
| | | 187 | | } |
| | | 188 | | |
| | | 189 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 190 | | public static bool TryIndexOfAny(ref char searchSpace, int searchSpaceLength, ReadOnlySpan<char> asciiValues, ou |
| | 0 | 191 | | TryIndexOfAny<DontNegate>(ref Unsafe.As<char, short>(ref searchSpace), searchSpaceLength, asciiValues, out i |
| | | 192 | | |
| | | 193 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 194 | | public static bool TryIndexOfAnyExcept(ref char searchSpace, int searchSpaceLength, ReadOnlySpan<char> asciiValu |
| | 0 | 195 | | TryIndexOfAny<Negate>(ref Unsafe.As<char, short>(ref searchSpace), searchSpaceLength, asciiValues, out index |
| | | 196 | | |
| | | 197 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 198 | | public static bool TryLastIndexOfAny(ref char searchSpace, int searchSpaceLength, ReadOnlySpan<char> asciiValues |
| | 0 | 199 | | TryLastIndexOfAny<DontNegate>(ref Unsafe.As<char, short>(ref searchSpace), searchSpaceLength, asciiValues, o |
| | | 200 | | |
| | | 201 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 202 | | public static bool TryLastIndexOfAnyExcept(ref char searchSpace, int searchSpaceLength, ReadOnlySpan<char> ascii |
| | 0 | 203 | | TryLastIndexOfAny<Negate>(ref Unsafe.As<char, short>(ref searchSpace), searchSpaceLength, asciiValues, out i |
| | | 204 | | |
| | | 205 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 206 | | private static unsafe bool TryIndexOfAny<TNegator>(ref short searchSpace, int searchSpaceLength, ReadOnlySpan<ch |
| | | 207 | | where TNegator : struct, INegator |
| | | 208 | | { |
| | 0 | 209 | | Debug.Assert(searchSpaceLength >= Vector128<short>.Count); |
| | | 210 | | |
| | 0 | 211 | | if (IsVectorizationSupported) |
| | | 212 | | { |
| | 0 | 213 | | AsciiState state = default; |
| | | 214 | | |
| | 0 | 215 | | if (TryComputeBitmap(asciiValues, (byte*)&state.Bitmap._lower, out bool needleContainsZero)) |
| | | 216 | | { |
| | | 217 | | // Only initializing the bitmap here is okay as we can only get here if the search space is long eno |
| | | 218 | | // and we support vectorization, so the IndexOfAnyVectorized implementation will never touch state.L |
| | 0 | 219 | | state.Bitmap = Vector256.Create(state.Bitmap.GetLower()); |
| | | 220 | | |
| | 0 | 221 | | index = (Ssse3.IsSupported || PackedSimd.IsSupported) && needleContainsZero |
| | 0 | 222 | | ? IndexOfAny<TNegator, Ssse3AndWasmHandleZeroInNeedle, SearchValues.FalseConst>(ref searchSpace, |
| | 0 | 223 | | : IndexOfAny<TNegator, Default, SearchValues.FalseConst>(ref searchSpace, searchSpaceLength, ref |
| | 0 | 224 | | return true; |
| | | 225 | | } |
| | | 226 | | } |
| | | 227 | | |
| | 0 | 228 | | index = default; |
| | 0 | 229 | | return false; |
| | | 230 | | } |
| | | 231 | | |
| | | 232 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 233 | | private static unsafe bool TryLastIndexOfAny<TNegator>(ref short searchSpace, int searchSpaceLength, ReadOnlySpa |
| | | 234 | | where TNegator : struct, INegator |
| | | 235 | | { |
| | 0 | 236 | | Debug.Assert(searchSpaceLength >= Vector128<short>.Count); |
| | | 237 | | |
| | 0 | 238 | | if (IsVectorizationSupported) |
| | | 239 | | { |
| | 0 | 240 | | AsciiState state = default; |
| | | 241 | | |
| | 0 | 242 | | if (TryComputeBitmap(asciiValues, (byte*)&state.Bitmap._lower, out bool needleContainsZero)) |
| | | 243 | | { |
| | | 244 | | // Only initializing the bitmap here is okay as we can only get here if the search space is long eno |
| | | 245 | | // and we support vectorization, so the LastIndexOfAnyVectorized implementation will never touch sta |
| | 0 | 246 | | state.Bitmap = Vector256.Create(state.Bitmap.GetLower()); |
| | | 247 | | |
| | 0 | 248 | | index = (Ssse3.IsSupported || PackedSimd.IsSupported) && needleContainsZero |
| | 0 | 249 | | ? LastIndexOfAny<TNegator, Ssse3AndWasmHandleZeroInNeedle, SearchValues.FalseConst>(ref searchSp |
| | 0 | 250 | | : LastIndexOfAny<TNegator, Default, SearchValues.FalseConst>(ref searchSpace, searchSpaceLength, |
| | 0 | 251 | | return true; |
| | | 252 | | } |
| | | 253 | | } |
| | | 254 | | |
| | 0 | 255 | | index = default; |
| | 0 | 256 | | return false; |
| | | 257 | | } |
| | | 258 | | |
| | | 259 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 260 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 261 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 262 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 263 | | public static bool ContainsAny<TNegator, TOptimizations, TUniqueLowNibble>(ref short searchSpace, int searchSpac |
| | | 264 | | where TNegator : struct, INegator |
| | | 265 | | where TOptimizations : struct, IOptimizations |
| | | 266 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst => |
| | 0 | 267 | | IndexOfAnyCore<bool, TNegator, TOptimizations, TUniqueLowNibble, ContainsAnyResultMapper<short>>(ref searchS |
| | | 268 | | |
| | | 269 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 270 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 271 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 272 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 273 | | public static int IndexOfAny<TNegator, TOptimizations, TUniqueLowNibble>(ref short searchSpace, int searchSpaceL |
| | | 274 | | where TNegator : struct, INegator |
| | | 275 | | where TOptimizations : struct, IOptimizations |
| | | 276 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst => |
| | 0 | 277 | | IndexOfAnyCore<int, TNegator, TOptimizations, TUniqueLowNibble, IndexOfAnyResultMapper<short>>(ref searchSpa |
| | | 278 | | |
| | | 279 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 280 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 281 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 282 | | private static TResult IndexOfAnyCore<TResult, TNegator, TOptimizations, TUniqueLowNibble, TResultMapper>(ref sh |
| | | 283 | | where TResult : struct |
| | | 284 | | where TNegator : struct, INegator |
| | | 285 | | where TOptimizations : struct, IOptimizations |
| | | 286 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst |
| | | 287 | | where TResultMapper : struct, IResultMapper<short, TResult> |
| | | 288 | | { |
| | 0 | 289 | | ref short currentSearchSpace = ref searchSpace; |
| | | 290 | | |
| | 0 | 291 | | if (searchSpaceLength < Vector128<ushort>.Count) |
| | | 292 | | { |
| | 0 | 293 | | ref short searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength); |
| | | 294 | | |
| | 0 | 295 | | while (!Unsafe.AreSame(ref currentSearchSpace, ref searchSpaceEnd)) |
| | | 296 | | { |
| | 0 | 297 | | char c = (char)currentSearchSpace; |
| | 0 | 298 | | if (TNegator.NegateIfNeeded(state.Lookup.Contains256(c))) |
| | | 299 | | { |
| | 0 | 300 | | return TResultMapper.ScalarResult(ref searchSpace, ref currentSearchSpace); |
| | | 301 | | } |
| | | 302 | | |
| | 0 | 303 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, 1); |
| | | 304 | | } |
| | | 305 | | |
| | 0 | 306 | | return TResultMapper.NotFound; |
| | | 307 | | } |
| | | 308 | | |
| | | 309 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // The behavior of the rest of the fu |
| | 0 | 310 | | if (Avx2.IsSupported && searchSpaceLength > 2 * Vector128<short>.Count) |
| | | 311 | | #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 312 | | { |
| | 0 | 313 | | Vector256<byte> bitmap256 = state.Bitmap; |
| | | 314 | | |
| | 0 | 315 | | if (searchSpaceLength > 2 * Vector256<short>.Count) |
| | | 316 | | { |
| | | 317 | | // Process the input in chunks of 32 characters (2 * Vector256<short>). |
| | | 318 | | // We're mainly interested in a single byte of each character, and the core lookup operates on a Vec |
| | | 319 | | // As packing two Vector256<short>s into a Vector256<byte> is cheap compared to the lookup, we can e |
| | | 320 | | // If the input length is a multiple of 32, don't consume the last 32 characters in this loop. |
| | | 321 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 322 | | // ">" instead of ">=" above, and why "IsAddressLessThan" is used instead of "IsAddressLessThanOrEqu |
| | 0 | 323 | | ref short twoVectorsAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - (2 * Vector256 |
| | | 324 | | |
| | | 325 | | do |
| | | 326 | | { |
| | 0 | 327 | | Vector256<short> source0 = Vector256.LoadUnsafe(ref currentSearchSpace); |
| | 0 | 328 | | Vector256<short> source1 = Vector256.LoadUnsafe(ref currentSearchSpace, (nuint)Vector256<short>. |
| | | 329 | | |
| | 0 | 330 | | Vector256<byte> result = IndexOfAnyLookup<TNegator, TOptimizations, TUniqueLowNibble>(source0, s |
| | 0 | 331 | | if (result != Vector256<byte>.Zero) |
| | | 332 | | { |
| | 0 | 333 | | return TResultMapper.FirstIndex<TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 334 | | } |
| | | 335 | | |
| | 0 | 336 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, 2 * Vector256<short>.Count); |
| | | 337 | | } |
| | 0 | 338 | | while (Unsafe.IsAddressLessThan(ref currentSearchSpace, ref twoVectorsAwayFromEnd)); |
| | | 339 | | } |
| | | 340 | | |
| | | 341 | | // We have 1-32 characters remaining. Process the first and last vector in the search space. |
| | | 342 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 343 | | Debug.Assert(searchSpaceLength >= Vector256<short>.Count, "We expect that the input is long enough for u |
| | | 344 | | { |
| | 0 | 345 | | ref short oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - Vector256<short |
| | | 346 | | |
| | 0 | 347 | | ref short firstVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref oneVectorAwayFro |
| | 0 | 348 | | ? ref oneVectorAwayFromEnd |
| | 0 | 349 | | : ref currentSearchSpace; |
| | | 350 | | |
| | 0 | 351 | | Vector256<short> source0 = Vector256.LoadUnsafe(ref firstVector); |
| | 0 | 352 | | Vector256<short> source1 = Vector256.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | | 353 | | |
| | 0 | 354 | | Vector256<byte> result = IndexOfAnyLookup<TNegator, TOptimizations, TUniqueLowNibble>(source0, sourc |
| | 0 | 355 | | if (result != Vector256<byte>.Zero) |
| | | 356 | | { |
| | 0 | 357 | | return TResultMapper.FirstIndexOverlapped<TNegator>(ref searchSpace, ref firstVector, ref oneVec |
| | | 358 | | } |
| | | 359 | | } |
| | | 360 | | |
| | 0 | 361 | | return TResultMapper.NotFound; |
| | | 362 | | } |
| | | 363 | | |
| | 0 | 364 | | Vector128<byte> bitmap = state.Bitmap._lower; |
| | | 365 | | |
| | | 366 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // The behavior of the rest of the fu |
| | 0 | 367 | | if (!Avx2.IsSupported && searchSpaceLength > 2 * Vector128<short>.Count) |
| | | 368 | | #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 369 | | { |
| | | 370 | | // Process the input in chunks of 16 characters (2 * Vector128<short>). |
| | | 371 | | // We're mainly interested in a single byte of each character, and the core lookup operates on a Vector1 |
| | | 372 | | // As packing two Vector128<short>s into a Vector128<byte> is cheap compared to the lookup, we can effec |
| | | 373 | | // If the input length is a multiple of 16, don't consume the last 16 characters in this loop. |
| | | 374 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 375 | | // ">" instead of ">=" above, and why "IsAddressLessThan" is used instead of "IsAddressLessThanOrEqualTo |
| | 0 | 376 | | ref short twoVectorsAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - (2 * Vector128<sho |
| | | 377 | | |
| | | 378 | | do |
| | | 379 | | { |
| | 0 | 380 | | Vector128<short> source0 = Vector128.LoadUnsafe(ref currentSearchSpace); |
| | 0 | 381 | | Vector128<short> source1 = Vector128.LoadUnsafe(ref currentSearchSpace, (nuint)Vector128<short>.Coun |
| | | 382 | | |
| | 0 | 383 | | Vector128<byte> result = IndexOfAnyLookup<TNegator, TOptimizations, TUniqueLowNibble>(source0, sourc |
| | 0 | 384 | | if (result != Vector128<byte>.Zero) |
| | | 385 | | { |
| | 0 | 386 | | return TResultMapper.FirstIndex<TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 387 | | } |
| | | 388 | | |
| | 0 | 389 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, 2 * Vector128<short>.Count); |
| | | 390 | | } |
| | 0 | 391 | | while (Unsafe.IsAddressLessThan(ref currentSearchSpace, ref twoVectorsAwayFromEnd)); |
| | | 392 | | } |
| | | 393 | | |
| | | 394 | | // We have 1-16 characters remaining. Process the first and last vector in the search space. |
| | | 395 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 396 | | Debug.Assert(searchSpaceLength >= Vector128<short>.Count, "We expect that the input is long enough for us to |
| | | 397 | | { |
| | 0 | 398 | | ref short oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - Vector128<short>.Co |
| | | 399 | | |
| | 0 | 400 | | ref short firstVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref oneVectorAwayFromEnd |
| | 0 | 401 | | ? ref oneVectorAwayFromEnd |
| | 0 | 402 | | : ref currentSearchSpace; |
| | | 403 | | |
| | 0 | 404 | | Vector128<short> source0 = Vector128.LoadUnsafe(ref firstVector); |
| | 0 | 405 | | Vector128<short> source1 = Vector128.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | | 406 | | |
| | 0 | 407 | | Vector128<byte> result = IndexOfAnyLookup<TNegator, TOptimizations, TUniqueLowNibble>(source0, source1, |
| | 0 | 408 | | if (result != Vector128<byte>.Zero) |
| | | 409 | | { |
| | 0 | 410 | | return TResultMapper.FirstIndexOverlapped<TNegator>(ref searchSpace, ref firstVector, ref oneVectorA |
| | | 411 | | } |
| | | 412 | | } |
| | | 413 | | |
| | 0 | 414 | | return TResultMapper.NotFound; |
| | | 415 | | } |
| | | 416 | | |
| | | 417 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 418 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 419 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 420 | | public static int LastIndexOfAny<TNegator, TOptimizations, TUniqueLowNibble>(ref short searchSpace, int searchSp |
| | | 421 | | where TNegator : struct, INegator |
| | | 422 | | where TOptimizations : struct, IOptimizations |
| | | 423 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst |
| | | 424 | | { |
| | 0 | 425 | | if (searchSpaceLength < Vector128<ushort>.Count) |
| | | 426 | | { |
| | 0 | 427 | | for (int i = searchSpaceLength - 1; i >= 0; i--) |
| | | 428 | | { |
| | 0 | 429 | | char c = (char)Unsafe.Add(ref searchSpace, i); |
| | 0 | 430 | | if (TNegator.NegateIfNeeded(state.Lookup.Contains256(c))) |
| | | 431 | | { |
| | 0 | 432 | | return i; |
| | | 433 | | } |
| | | 434 | | } |
| | | 435 | | |
| | 0 | 436 | | return -1; |
| | | 437 | | } |
| | | 438 | | |
| | 0 | 439 | | ref short currentSearchSpace = ref Unsafe.Add(ref searchSpace, searchSpaceLength); |
| | | 440 | | |
| | | 441 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // The else clause is semantically eq |
| | 0 | 442 | | if (Avx2.IsSupported && searchSpaceLength > 2 * Vector128<short>.Count) |
| | | 443 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 444 | | { |
| | 0 | 445 | | Vector256<byte> bitmap256 = state.Bitmap; |
| | | 446 | | |
| | 0 | 447 | | if (searchSpaceLength > 2 * Vector256<short>.Count) |
| | | 448 | | { |
| | | 449 | | // Process the input in chunks of 32 characters (2 * Vector256<short>). |
| | | 450 | | // We're mainly interested in a single byte of each character, and the core lookup operates on a Vec |
| | | 451 | | // As packing two Vector256<short>s into a Vector256<byte> is cheap compared to the lookup, we can e |
| | | 452 | | // If the input length is a multiple of 32, don't consume the last 32 characters in this loop. |
| | | 453 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 454 | | // ">" instead of ">=" above, and why "IsAddressGreaterThan" is used instead of "IsAddressGreaterTha |
| | 0 | 455 | | ref short twoVectorsAfterStart = ref Unsafe.Add(ref searchSpace, 2 * Vector256<short>.Count); |
| | | 456 | | |
| | | 457 | | do |
| | | 458 | | { |
| | 0 | 459 | | currentSearchSpace = ref Unsafe.Subtract(ref currentSearchSpace, 2 * Vector256<short>.Count); |
| | | 460 | | |
| | 0 | 461 | | Vector256<short> source0 = Vector256.LoadUnsafe(ref currentSearchSpace); |
| | 0 | 462 | | Vector256<short> source1 = Vector256.LoadUnsafe(ref currentSearchSpace, (nuint)Vector256<short>. |
| | | 463 | | |
| | 0 | 464 | | Vector256<byte> result = IndexOfAnyLookup<TNegator, TOptimizations, TUniqueLowNibble>(source0, s |
| | 0 | 465 | | if (result != Vector256<byte>.Zero) |
| | | 466 | | { |
| | 0 | 467 | | return ComputeLastIndex<short, TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 468 | | } |
| | | 469 | | } |
| | 0 | 470 | | while (Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref twoVectorsAfterStart)); |
| | | 471 | | } |
| | | 472 | | |
| | | 473 | | // We have 1-32 characters remaining. Process the first and last vector in the search space. |
| | | 474 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 475 | | Debug.Assert(searchSpaceLength >= Vector256<short>.Count, "We expect that the input is long enough for u |
| | | 476 | | { |
| | 0 | 477 | | ref short oneVectorAfterStart = ref Unsafe.Add(ref searchSpace, Vector256<short>.Count); |
| | | 478 | | |
| | 0 | 479 | | ref short secondVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref oneVectorAfterS |
| | 0 | 480 | | ? ref Unsafe.Subtract(ref currentSearchSpace, Vector256<short>.Count) |
| | 0 | 481 | | : ref searchSpace; |
| | | 482 | | |
| | 0 | 483 | | Vector256<short> source0 = Vector256.LoadUnsafe(ref searchSpace); |
| | 0 | 484 | | Vector256<short> source1 = Vector256.LoadUnsafe(ref secondVector); |
| | | 485 | | |
| | 0 | 486 | | Vector256<byte> result = IndexOfAnyLookup<TNegator, TOptimizations, TUniqueLowNibble>(source0, sourc |
| | 0 | 487 | | if (result != Vector256<byte>.Zero) |
| | | 488 | | { |
| | 0 | 489 | | return ComputeLastIndexOverlapped<short, TNegator>(ref searchSpace, ref secondVector, result); |
| | | 490 | | } |
| | | 491 | | } |
| | | 492 | | |
| | 0 | 493 | | return -1; |
| | | 494 | | } |
| | | 495 | | |
| | 0 | 496 | | Vector128<byte> bitmap = state.Bitmap._lower; |
| | | 497 | | |
| | 0 | 498 | | if (!Avx2.IsSupported && searchSpaceLength > 2 * Vector128<short>.Count) |
| | | 499 | | { |
| | | 500 | | // Process the input in chunks of 16 characters (2 * Vector128<short>). |
| | | 501 | | // We're mainly interested in a single byte of each character, and the core lookup operates on a Vector1 |
| | | 502 | | // As packing two Vector128<short>s into a Vector128<byte> is cheap compared to the lookup, we can effec |
| | | 503 | | // If the input length is a multiple of 16, don't consume the last 16 characters in this loop. |
| | | 504 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 505 | | // ">" instead of ">=" above, and why "IsAddressGreaterThan" is used instead of "IsAddressGreaterThanOrE |
| | 0 | 506 | | ref short twoVectorsAfterStart = ref Unsafe.Add(ref searchSpace, 2 * Vector128<short>.Count); |
| | | 507 | | |
| | | 508 | | do |
| | | 509 | | { |
| | 0 | 510 | | currentSearchSpace = ref Unsafe.Subtract(ref currentSearchSpace, 2 * Vector128<short>.Count); |
| | | 511 | | |
| | 0 | 512 | | Vector128<short> source0 = Vector128.LoadUnsafe(ref currentSearchSpace); |
| | 0 | 513 | | Vector128<short> source1 = Vector128.LoadUnsafe(ref currentSearchSpace, (nuint)Vector128<short>.Coun |
| | | 514 | | |
| | 0 | 515 | | Vector128<byte> result = IndexOfAnyLookup<TNegator, TOptimizations, TUniqueLowNibble>(source0, sourc |
| | 0 | 516 | | if (result != Vector128<byte>.Zero) |
| | | 517 | | { |
| | 0 | 518 | | return ComputeLastIndex<short, TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 519 | | } |
| | | 520 | | } |
| | 0 | 521 | | while (Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref twoVectorsAfterStart)); |
| | | 522 | | } |
| | | 523 | | |
| | | 524 | | // We have 1-16 characters remaining. Process the first and last vector in the search space. |
| | | 525 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 526 | | Debug.Assert(searchSpaceLength >= Vector128<short>.Count, "We expect that the input is long enough for us to |
| | | 527 | | { |
| | 0 | 528 | | ref short oneVectorAfterStart = ref Unsafe.Add(ref searchSpace, Vector128<short>.Count); |
| | | 529 | | |
| | 0 | 530 | | ref short secondVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref oneVectorAfterStart |
| | 0 | 531 | | ? ref Unsafe.Subtract(ref currentSearchSpace, Vector128<short>.Count) |
| | 0 | 532 | | : ref searchSpace; |
| | | 533 | | |
| | 0 | 534 | | Vector128<short> source0 = Vector128.LoadUnsafe(ref searchSpace); |
| | 0 | 535 | | Vector128<short> source1 = Vector128.LoadUnsafe(ref secondVector); |
| | | 536 | | |
| | 0 | 537 | | Vector128<byte> result = IndexOfAnyLookup<TNegator, TOptimizations, TUniqueLowNibble>(source0, source1, |
| | 0 | 538 | | if (result != Vector128<byte>.Zero) |
| | | 539 | | { |
| | 0 | 540 | | return ComputeLastIndexOverlapped<short, TNegator>(ref searchSpace, ref secondVector, result); |
| | | 541 | | } |
| | | 542 | | } |
| | | 543 | | |
| | 0 | 544 | | return -1; |
| | | 545 | | } |
| | | 546 | | |
| | | 547 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 548 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 549 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 550 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 551 | | public static bool ContainsAny<TNegator, TUniqueLowNibble>(ref byte searchSpace, int searchSpaceLength, ref Asci |
| | | 552 | | where TNegator : struct, INegator |
| | | 553 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst => |
| | 0 | 554 | | IndexOfAnyCore<bool, TNegator, TUniqueLowNibble, ContainsAnyResultMapper<byte>>(ref searchSpace, searchSpace |
| | | 555 | | |
| | | 556 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 557 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 558 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 559 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 560 | | public static int IndexOfAny<TNegator, TUniqueLowNibble>(ref byte searchSpace, int searchSpaceLength, ref AsciiS |
| | | 561 | | where TNegator : struct, INegator |
| | | 562 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst => |
| | 0 | 563 | | IndexOfAnyCore<int, TNegator, TUniqueLowNibble, IndexOfAnyResultMapper<byte>>(ref searchSpace, searchSpaceLe |
| | | 564 | | |
| | | 565 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 566 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 567 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 568 | | private static TResult IndexOfAnyCore<TResult, TNegator, TUniqueLowNibble, TResultMapper>(ref byte searchSpace, |
| | | 569 | | where TResult : struct |
| | | 570 | | where TNegator : struct, INegator |
| | | 571 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst |
| | | 572 | | where TResultMapper : struct, IResultMapper<byte, TResult> |
| | | 573 | | { |
| | 0 | 574 | | ref byte currentSearchSpace = ref searchSpace; |
| | | 575 | | |
| | 0 | 576 | | if (searchSpaceLength < sizeof(ulong)) |
| | | 577 | | { |
| | 0 | 578 | | ref byte searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength); |
| | | 579 | | |
| | 0 | 580 | | while (!Unsafe.AreSame(ref currentSearchSpace, ref searchSpaceEnd)) |
| | | 581 | | { |
| | 0 | 582 | | byte b = currentSearchSpace; |
| | 0 | 583 | | if (TNegator.NegateIfNeeded(state.Lookup.Contains(b))) |
| | | 584 | | { |
| | 0 | 585 | | return TResultMapper.ScalarResult(ref searchSpace, ref currentSearchSpace); |
| | | 586 | | } |
| | | 587 | | |
| | 0 | 588 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, 1); |
| | | 589 | | } |
| | | 590 | | |
| | 0 | 591 | | return TResultMapper.NotFound; |
| | | 592 | | } |
| | | 593 | | |
| | | 594 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // The behavior of the rest of the fu |
| | 0 | 595 | | if (Avx2.IsSupported && searchSpaceLength > Vector128<byte>.Count) |
| | | 596 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 597 | | { |
| | 0 | 598 | | Vector256<byte> bitmap256 = state.Bitmap; |
| | | 599 | | |
| | 0 | 600 | | if (searchSpaceLength > Vector256<byte>.Count) |
| | | 601 | | { |
| | | 602 | | // Process the input in chunks of 32 bytes. |
| | | 603 | | // If the input length is a multiple of 32, don't consume the last 32 characters in this loop. |
| | | 604 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 605 | | // ">" instead of ">=" above, and why "IsAddressLessThan" is used instead of "IsAddressLessThanOrEqu |
| | 0 | 606 | | ref byte vectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - Vector256<byte>.Cou |
| | | 607 | | |
| | | 608 | | do |
| | | 609 | | { |
| | 0 | 610 | | Vector256<byte> source = Vector256.LoadUnsafe(ref currentSearchSpace); |
| | | 611 | | |
| | 0 | 612 | | Vector256<byte> result = TNegator.NegateIfNeeded(IndexOfAnyLookupCore<TUniqueLowNibble>(source, |
| | 0 | 613 | | if (result != Vector256<byte>.Zero) |
| | | 614 | | { |
| | 0 | 615 | | return TResultMapper.FirstIndex<TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 616 | | } |
| | | 617 | | |
| | 0 | 618 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector256<byte>.Count); |
| | | 619 | | } |
| | 0 | 620 | | while (Unsafe.IsAddressLessThan(ref currentSearchSpace, ref vectorAwayFromEnd)); |
| | | 621 | | } |
| | | 622 | | |
| | | 623 | | // We have 1-32 bytes remaining. Process the first and last half vectors in the search space. |
| | | 624 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 625 | | Debug.Assert(searchSpaceLength >= Vector128<byte>.Count, "We expect that the input is long enough for us |
| | | 626 | | { |
| | 0 | 627 | | ref byte halfVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - Vector128<byte> |
| | | 628 | | |
| | 0 | 629 | | ref byte firstVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref halfVectorAwayFro |
| | 0 | 630 | | ? ref halfVectorAwayFromEnd |
| | 0 | 631 | | : ref currentSearchSpace; |
| | | 632 | | |
| | 0 | 633 | | Vector128<byte> source0 = Vector128.LoadUnsafe(ref firstVector); |
| | 0 | 634 | | Vector128<byte> source1 = Vector128.LoadUnsafe(ref halfVectorAwayFromEnd); |
| | 0 | 635 | | Vector256<byte> source = Vector256.Create(source0, source1); |
| | | 636 | | |
| | 0 | 637 | | Vector256<byte> result = TNegator.NegateIfNeeded(IndexOfAnyLookupCore<TUniqueLowNibble>(source, bitm |
| | 0 | 638 | | if (result != Vector256<byte>.Zero) |
| | | 639 | | { |
| | 0 | 640 | | return TResultMapper.FirstIndexOverlapped<TNegator>(ref searchSpace, ref firstVector, ref halfVe |
| | | 641 | | } |
| | | 642 | | } |
| | | 643 | | |
| | 0 | 644 | | return TResultMapper.NotFound; |
| | | 645 | | } |
| | | 646 | | |
| | 0 | 647 | | Vector128<byte> bitmap = state.Bitmap._lower; |
| | | 648 | | |
| | 0 | 649 | | if (!Avx2.IsSupported && searchSpaceLength > Vector128<byte>.Count) |
| | | 650 | | { |
| | | 651 | | // Process the input in chunks of 16 bytes. |
| | | 652 | | // If the input length is a multiple of 16, don't consume the last 16 characters in this loop. |
| | | 653 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 654 | | // ">" instead of ">=" above, and why "IsAddressLessThan" is used instead of "IsAddressLessThanOrEqualTo |
| | 0 | 655 | | ref byte vectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - Vector128<byte>.Count); |
| | | 656 | | |
| | | 657 | | do |
| | | 658 | | { |
| | 0 | 659 | | Vector128<byte> source = Vector128.LoadUnsafe(ref currentSearchSpace); |
| | | 660 | | |
| | 0 | 661 | | Vector128<byte> result = TNegator.NegateIfNeeded(IndexOfAnyLookupCore<TUniqueLowNibble>(source, bitm |
| | 0 | 662 | | if (result != Vector128<byte>.Zero) |
| | | 663 | | { |
| | 0 | 664 | | return TResultMapper.FirstIndex<TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 665 | | } |
| | | 666 | | |
| | 0 | 667 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector128<byte>.Count); |
| | | 668 | | } |
| | 0 | 669 | | while (Unsafe.IsAddressLessThan(ref currentSearchSpace, ref vectorAwayFromEnd)); |
| | | 670 | | } |
| | | 671 | | |
| | | 672 | | // We have 1-16 bytes remaining. Process the first and last half vectors in the search space. |
| | | 673 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 674 | | Debug.Assert(searchSpaceLength >= sizeof(ulong), "We expect that the input is long enough for us to load a u |
| | | 675 | | { |
| | 0 | 676 | | ref byte halfVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - sizeof(ulong)); |
| | | 677 | | |
| | 0 | 678 | | ref byte firstVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref halfVectorAwayFromEnd |
| | 0 | 679 | | ? ref halfVectorAwayFromEnd |
| | 0 | 680 | | : ref currentSearchSpace; |
| | | 681 | | |
| | 0 | 682 | | ulong source0 = Unsafe.ReadUnaligned<ulong>(ref firstVector); |
| | 0 | 683 | | ulong source1 = Unsafe.ReadUnaligned<ulong>(ref halfVectorAwayFromEnd); |
| | 0 | 684 | | Vector128<byte> source = Vector128.Create(source0, source1).AsByte(); |
| | | 685 | | |
| | 0 | 686 | | Vector128<byte> result = TNegator.NegateIfNeeded(IndexOfAnyLookupCore<TUniqueLowNibble>(source, bitmap)) |
| | 0 | 687 | | if (result != Vector128<byte>.Zero) |
| | | 688 | | { |
| | 0 | 689 | | return TResultMapper.FirstIndexOverlapped<TNegator>(ref searchSpace, ref firstVector, ref halfVector |
| | | 690 | | } |
| | | 691 | | } |
| | | 692 | | |
| | 0 | 693 | | return TResultMapper.NotFound; |
| | | 694 | | } |
| | | 695 | | |
| | | 696 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 697 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 698 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 699 | | public static int LastIndexOfAny<TNegator, TUniqueLowNibble>(ref byte searchSpace, int searchSpaceLength, ref As |
| | | 700 | | where TNegator : struct, INegator |
| | | 701 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst |
| | | 702 | | { |
| | 0 | 703 | | if (searchSpaceLength < sizeof(ulong)) |
| | | 704 | | { |
| | 0 | 705 | | for (int i = searchSpaceLength - 1; i >= 0; i--) |
| | | 706 | | { |
| | 0 | 707 | | byte b = Unsafe.Add(ref searchSpace, i); |
| | 0 | 708 | | if (TNegator.NegateIfNeeded(state.Lookup.Contains(b))) |
| | | 709 | | { |
| | 0 | 710 | | return i; |
| | | 711 | | } |
| | | 712 | | } |
| | | 713 | | |
| | 0 | 714 | | return -1; |
| | | 715 | | } |
| | | 716 | | |
| | 0 | 717 | | ref byte currentSearchSpace = ref Unsafe.Add(ref searchSpace, searchSpaceLength); |
| | | 718 | | |
| | | 719 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // The behavior of the rest of the fu |
| | 0 | 720 | | if (Avx2.IsSupported && searchSpaceLength > Vector128<byte>.Count) |
| | | 721 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 722 | | { |
| | 0 | 723 | | Vector256<byte> bitmap256 = state.Bitmap; |
| | | 724 | | |
| | 0 | 725 | | if (searchSpaceLength > Vector256<byte>.Count) |
| | | 726 | | { |
| | | 727 | | // Process the input in chunks of 32 bytes. |
| | | 728 | | // If the input length is a multiple of 32, don't consume the last 32 characters in this loop. |
| | | 729 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 730 | | // ">" instead of ">=" above, and why "IsAddressGreaterThan" is used instead of "IsAddressGreaterTha |
| | 0 | 731 | | ref byte vectorAfterStart = ref Unsafe.Add(ref searchSpace, Vector256<byte>.Count); |
| | | 732 | | |
| | | 733 | | do |
| | | 734 | | { |
| | 0 | 735 | | currentSearchSpace = ref Unsafe.Subtract(ref currentSearchSpace, Vector256<byte>.Count); |
| | | 736 | | |
| | 0 | 737 | | Vector256<byte> source = Vector256.LoadUnsafe(ref currentSearchSpace); |
| | | 738 | | |
| | 0 | 739 | | Vector256<byte> result = TNegator.NegateIfNeeded(IndexOfAnyLookupCore<TUniqueLowNibble>(source, |
| | 0 | 740 | | if (result != Vector256<byte>.Zero) |
| | | 741 | | { |
| | 0 | 742 | | return ComputeLastIndex<byte, TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 743 | | } |
| | | 744 | | } |
| | 0 | 745 | | while (Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref vectorAfterStart)); |
| | | 746 | | } |
| | | 747 | | |
| | | 748 | | // We have 1-32 bytes remaining. Process the first and last half vectors in the search space. |
| | | 749 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 750 | | Debug.Assert(searchSpaceLength >= Vector128<byte>.Count, "We expect that the input is long enough for us |
| | | 751 | | { |
| | 0 | 752 | | ref byte halfVectorAfterStart = ref Unsafe.Add(ref searchSpace, Vector128<byte>.Count); |
| | | 753 | | |
| | 0 | 754 | | ref byte secondVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref halfVectorAfterS |
| | 0 | 755 | | ? ref Unsafe.Subtract(ref currentSearchSpace, Vector128<byte>.Count) |
| | 0 | 756 | | : ref searchSpace; |
| | | 757 | | |
| | 0 | 758 | | Vector128<byte> source0 = Vector128.LoadUnsafe(ref searchSpace); |
| | 0 | 759 | | Vector128<byte> source1 = Vector128.LoadUnsafe(ref secondVector); |
| | 0 | 760 | | Vector256<byte> source = Vector256.Create(source0, source1); |
| | | 761 | | |
| | 0 | 762 | | Vector256<byte> result = TNegator.NegateIfNeeded(IndexOfAnyLookupCore<TUniqueLowNibble>(source, bitm |
| | 0 | 763 | | if (result != Vector256<byte>.Zero) |
| | | 764 | | { |
| | 0 | 765 | | return ComputeLastIndexOverlapped<byte, TNegator>(ref searchSpace, ref secondVector, result); |
| | | 766 | | } |
| | | 767 | | } |
| | | 768 | | |
| | 0 | 769 | | return -1; |
| | | 770 | | } |
| | | 771 | | |
| | 0 | 772 | | Vector128<byte> bitmap = state.Bitmap._lower; |
| | | 773 | | |
| | 0 | 774 | | if (!Avx2.IsSupported && searchSpaceLength > Vector128<byte>.Count) |
| | | 775 | | { |
| | | 776 | | // Process the input in chunks of 16 bytes. |
| | | 777 | | // If the input length is a multiple of 16, don't consume the last 16 characters in this loop. |
| | | 778 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 779 | | // ">" instead of ">=" above, and why "IsAddressGreaterThan" is used instead of "IsAddressGreaterThanOrE |
| | 0 | 780 | | ref byte vectorAfterStart = ref Unsafe.Add(ref searchSpace, Vector128<byte>.Count); |
| | | 781 | | |
| | | 782 | | do |
| | | 783 | | { |
| | 0 | 784 | | currentSearchSpace = ref Unsafe.Subtract(ref currentSearchSpace, Vector128<byte>.Count); |
| | | 785 | | |
| | 0 | 786 | | Vector128<byte> source = Vector128.LoadUnsafe(ref currentSearchSpace); |
| | | 787 | | |
| | 0 | 788 | | Vector128<byte> result = TNegator.NegateIfNeeded(IndexOfAnyLookupCore<TUniqueLowNibble>(source, bitm |
| | 0 | 789 | | if (result != Vector128<byte>.Zero) |
| | | 790 | | { |
| | 0 | 791 | | return ComputeLastIndex<byte, TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 792 | | } |
| | | 793 | | } |
| | 0 | 794 | | while (Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref vectorAfterStart)); |
| | | 795 | | } |
| | | 796 | | |
| | | 797 | | // We have 1-16 bytes remaining. Process the first and last half vectors in the search space. |
| | | 798 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 799 | | Debug.Assert(searchSpaceLength >= sizeof(ulong), "We expect that the input is long enough for us to load a u |
| | | 800 | | { |
| | 0 | 801 | | ref byte halfVectorAfterStart = ref Unsafe.Add(ref searchSpace, sizeof(ulong)); |
| | | 802 | | |
| | 0 | 803 | | ref byte secondVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref halfVectorAfterStart |
| | 0 | 804 | | ? ref Unsafe.Subtract(ref currentSearchSpace, sizeof(ulong)) |
| | 0 | 805 | | : ref searchSpace; |
| | | 806 | | |
| | 0 | 807 | | ulong source0 = Unsafe.ReadUnaligned<ulong>(ref searchSpace); |
| | 0 | 808 | | ulong source1 = Unsafe.ReadUnaligned<ulong>(ref secondVector); |
| | 0 | 809 | | Vector128<byte> source = Vector128.Create(source0, source1).AsByte(); |
| | | 810 | | |
| | 0 | 811 | | Vector128<byte> result = TNegator.NegateIfNeeded(IndexOfAnyLookupCore<TUniqueLowNibble>(source, bitmap)) |
| | 0 | 812 | | if (result != Vector128<byte>.Zero) |
| | | 813 | | { |
| | 0 | 814 | | return ComputeLastIndexOverlapped<byte, TNegator>(ref searchSpace, ref secondVector, result); |
| | | 815 | | } |
| | | 816 | | } |
| | | 817 | | |
| | 0 | 818 | | return -1; |
| | | 819 | | } |
| | | 820 | | |
| | | 821 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 822 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 823 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 824 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 825 | | public static bool ContainsAny<TNegator>(ref byte searchSpace, int searchSpaceLength, ref AnyByteState state) |
| | | 826 | | where TNegator : struct, INegator => |
| | 0 | 827 | | IndexOfAnyCore<bool, TNegator, ContainsAnyResultMapper<byte>>(ref searchSpace, searchSpaceLength, ref state) |
| | | 828 | | |
| | | 829 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 830 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 831 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 832 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 833 | | public static int IndexOfAny<TNegator>(ref byte searchSpace, int searchSpaceLength, ref AnyByteState state) |
| | | 834 | | where TNegator : struct, INegator => |
| | 0 | 835 | | IndexOfAnyCore<int, TNegator, IndexOfAnyResultMapper<byte>>(ref searchSpace, searchSpaceLength, ref state); |
| | | 836 | | |
| | | 837 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 838 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 839 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 840 | | private static TResult IndexOfAnyCore<TResult, TNegator, TResultMapper>(ref byte searchSpace, int searchSpaceLen |
| | | 841 | | where TResult : struct |
| | | 842 | | where TNegator : struct, INegator |
| | | 843 | | where TResultMapper : struct, IResultMapper<byte, TResult> |
| | | 844 | | { |
| | 0 | 845 | | ref byte currentSearchSpace = ref searchSpace; |
| | | 846 | | |
| | 0 | 847 | | if (!IsVectorizationSupported || searchSpaceLength < sizeof(ulong)) |
| | | 848 | | { |
| | 0 | 849 | | ref byte searchSpaceEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength); |
| | | 850 | | |
| | 0 | 851 | | while (!Unsafe.AreSame(ref currentSearchSpace, ref searchSpaceEnd)) |
| | | 852 | | { |
| | 0 | 853 | | byte b = currentSearchSpace; |
| | 0 | 854 | | if (TNegator.NegateIfNeeded(state.Lookup.Contains(b))) |
| | | 855 | | { |
| | 0 | 856 | | return TResultMapper.ScalarResult(ref searchSpace, ref currentSearchSpace); |
| | | 857 | | } |
| | | 858 | | |
| | 0 | 859 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, 1); |
| | | 860 | | } |
| | | 861 | | |
| | 0 | 862 | | return TResultMapper.NotFound; |
| | | 863 | | } |
| | | 864 | | |
| | | 865 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // The behavior of the rest of the fu |
| | 0 | 866 | | if (Avx2.IsSupported && searchSpaceLength > Vector128<byte>.Count) |
| | | 867 | | #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 868 | | { |
| | 0 | 869 | | Vector256<byte> bitmap256_0 = state.Bitmap0; |
| | 0 | 870 | | Vector256<byte> bitmap256_1 = state.Bitmap1; |
| | | 871 | | |
| | 0 | 872 | | if (searchSpaceLength > Vector256<byte>.Count) |
| | | 873 | | { |
| | | 874 | | // Process the input in chunks of 32 bytes. |
| | | 875 | | // If the input length is a multiple of 32, don't consume the last 32 characters in this loop. |
| | | 876 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 877 | | // ">" instead of ">=" above, and why "IsAddressLessThan" is used instead of "IsAddressLessThanOrEqu |
| | 0 | 878 | | ref byte vectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - Vector256<byte>.Cou |
| | | 879 | | |
| | | 880 | | do |
| | | 881 | | { |
| | 0 | 882 | | Vector256<byte> source = Vector256.LoadUnsafe(ref currentSearchSpace); |
| | | 883 | | |
| | 0 | 884 | | Vector256<byte> result = IndexOfAnyLookup<TNegator>(source, bitmap256_0, bitmap256_1); |
| | 0 | 885 | | if (result != Vector256<byte>.Zero) |
| | | 886 | | { |
| | 0 | 887 | | return TResultMapper.FirstIndex<TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 888 | | } |
| | | 889 | | |
| | 0 | 890 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector256<byte>.Count); |
| | | 891 | | } |
| | 0 | 892 | | while (Unsafe.IsAddressLessThan(ref currentSearchSpace, ref vectorAwayFromEnd)); |
| | | 893 | | } |
| | | 894 | | |
| | | 895 | | // We have 1-32 bytes remaining. Process the first and last half vectors in the search space. |
| | | 896 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 897 | | Debug.Assert(searchSpaceLength >= Vector128<byte>.Count, "We expect that the input is long enough for us |
| | | 898 | | { |
| | 0 | 899 | | ref byte halfVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - Vector128<byte> |
| | | 900 | | |
| | 0 | 901 | | ref byte firstVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref halfVectorAwayFro |
| | 0 | 902 | | ? ref halfVectorAwayFromEnd |
| | 0 | 903 | | : ref currentSearchSpace; |
| | | 904 | | |
| | 0 | 905 | | Vector128<byte> source0 = Vector128.LoadUnsafe(ref firstVector); |
| | 0 | 906 | | Vector128<byte> source1 = Vector128.LoadUnsafe(ref halfVectorAwayFromEnd); |
| | 0 | 907 | | Vector256<byte> source = Vector256.Create(source0, source1); |
| | | 908 | | |
| | 0 | 909 | | Vector256<byte> result = IndexOfAnyLookup<TNegator>(source, bitmap256_0, bitmap256_1); |
| | 0 | 910 | | if (result != Vector256<byte>.Zero) |
| | | 911 | | { |
| | 0 | 912 | | return TResultMapper.FirstIndexOverlapped<TNegator>(ref searchSpace, ref firstVector, ref halfVe |
| | | 913 | | } |
| | | 914 | | } |
| | | 915 | | |
| | 0 | 916 | | return TResultMapper.NotFound; |
| | | 917 | | } |
| | | 918 | | |
| | 0 | 919 | | Vector128<byte> bitmap0 = state.Bitmap0._lower; |
| | 0 | 920 | | Vector128<byte> bitmap1 = state.Bitmap1._lower; |
| | | 921 | | |
| | | 922 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // The behavior of the rest of the fu |
| | 0 | 923 | | if (!Avx2.IsSupported && searchSpaceLength > Vector128<byte>.Count) |
| | | 924 | | #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 925 | | { |
| | | 926 | | // Process the input in chunks of 16 bytes. |
| | | 927 | | // If the input length is a multiple of 16, don't consume the last 16 characters in this loop. |
| | | 928 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 929 | | // ">" instead of ">=" above, and why "IsAddressLessThan" is used instead of "IsAddressLessThanOrEqualTo |
| | 0 | 930 | | ref byte vectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - Vector128<byte>.Count); |
| | | 931 | | |
| | | 932 | | do |
| | | 933 | | { |
| | 0 | 934 | | Vector128<byte> source = Vector128.LoadUnsafe(ref currentSearchSpace); |
| | | 935 | | |
| | 0 | 936 | | Vector128<byte> result = IndexOfAnyLookup<TNegator>(source, bitmap0, bitmap1); |
| | 0 | 937 | | if (result != Vector128<byte>.Zero) |
| | | 938 | | { |
| | 0 | 939 | | return TResultMapper.FirstIndex<TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 940 | | } |
| | | 941 | | |
| | 0 | 942 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector128<byte>.Count); |
| | | 943 | | } |
| | 0 | 944 | | while (Unsafe.IsAddressLessThan(ref currentSearchSpace, ref vectorAwayFromEnd)); |
| | | 945 | | } |
| | | 946 | | |
| | | 947 | | // We have 1-16 bytes remaining. Process the first and last half vectors in the search space. |
| | | 948 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 949 | | Debug.Assert(searchSpaceLength >= sizeof(ulong), "We expect that the input is long enough for us to load a u |
| | | 950 | | { |
| | 0 | 951 | | ref byte halfVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, searchSpaceLength - sizeof(ulong)); |
| | | 952 | | |
| | 0 | 953 | | ref byte firstVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref halfVectorAwayFromEnd |
| | 0 | 954 | | ? ref halfVectorAwayFromEnd |
| | 0 | 955 | | : ref currentSearchSpace; |
| | | 956 | | |
| | 0 | 957 | | ulong source0 = Unsafe.ReadUnaligned<ulong>(ref firstVector); |
| | 0 | 958 | | ulong source1 = Unsafe.ReadUnaligned<ulong>(ref halfVectorAwayFromEnd); |
| | 0 | 959 | | Vector128<byte> source = Vector128.Create(source0, source1).AsByte(); |
| | | 960 | | |
| | 0 | 961 | | Vector128<byte> result = IndexOfAnyLookup<TNegator>(source, bitmap0, bitmap1); |
| | 0 | 962 | | if (result != Vector128<byte>.Zero) |
| | | 963 | | { |
| | 0 | 964 | | return TResultMapper.FirstIndexOverlapped<TNegator>(ref searchSpace, ref firstVector, ref halfVector |
| | | 965 | | } |
| | | 966 | | } |
| | | 967 | | |
| | 0 | 968 | | return TResultMapper.NotFound; |
| | | 969 | | } |
| | | 970 | | |
| | | 971 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 972 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 973 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 974 | | public static int LastIndexOfAny<TNegator>(ref byte searchSpace, int searchSpaceLength, ref AnyByteState state) |
| | | 975 | | where TNegator : struct, INegator |
| | | 976 | | { |
| | 0 | 977 | | if (!IsVectorizationSupported || searchSpaceLength < sizeof(ulong)) |
| | | 978 | | { |
| | 0 | 979 | | for (int i = searchSpaceLength - 1; i >= 0; i--) |
| | | 980 | | { |
| | 0 | 981 | | byte b = Unsafe.Add(ref searchSpace, i); |
| | 0 | 982 | | if (TNegator.NegateIfNeeded(state.Lookup.Contains(b))) |
| | | 983 | | { |
| | 0 | 984 | | return i; |
| | | 985 | | } |
| | | 986 | | } |
| | | 987 | | |
| | 0 | 988 | | return -1; |
| | | 989 | | } |
| | | 990 | | |
| | 0 | 991 | | ref byte currentSearchSpace = ref Unsafe.Add(ref searchSpace, searchSpaceLength); |
| | | 992 | | |
| | | 993 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // The behavior of the rest of the fu |
| | 0 | 994 | | if (Avx2.IsSupported && searchSpaceLength > Vector128<byte>.Count) |
| | | 995 | | { |
| | | 996 | | #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | 0 | 997 | | Vector256<byte> bitmap256_0 = state.Bitmap0; |
| | 0 | 998 | | Vector256<byte> bitmap256_1 = state.Bitmap1; |
| | | 999 | | |
| | 0 | 1000 | | if (searchSpaceLength > Vector256<byte>.Count) |
| | | 1001 | | { |
| | | 1002 | | // Process the input in chunks of 32 bytes. |
| | | 1003 | | // If the input length is a multiple of 32, don't consume the last 32 characters in this loop. |
| | | 1004 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 1005 | | // ">" instead of ">=" above, and why "IsAddressGreaterThan" is used instead of "IsAddressGreaterTha |
| | 0 | 1006 | | ref byte vectorAfterStart = ref Unsafe.Add(ref searchSpace, Vector256<byte>.Count); |
| | | 1007 | | |
| | | 1008 | | do |
| | | 1009 | | { |
| | 0 | 1010 | | currentSearchSpace = ref Unsafe.Subtract(ref currentSearchSpace, Vector256<byte>.Count); |
| | | 1011 | | |
| | 0 | 1012 | | Vector256<byte> source = Vector256.LoadUnsafe(ref currentSearchSpace); |
| | | 1013 | | |
| | 0 | 1014 | | Vector256<byte> result = IndexOfAnyLookup<TNegator>(source, bitmap256_0, bitmap256_1); |
| | 0 | 1015 | | if (result != Vector256<byte>.Zero) |
| | | 1016 | | { |
| | 0 | 1017 | | return ComputeLastIndex<byte, TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 1018 | | } |
| | | 1019 | | } |
| | 0 | 1020 | | while (Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref vectorAfterStart)); |
| | | 1021 | | } |
| | | 1022 | | |
| | | 1023 | | // We have 1-32 bytes remaining. Process the first and last half vectors in the search space. |
| | | 1024 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 1025 | | Debug.Assert(searchSpaceLength >= Vector128<byte>.Count, "We expect that the input is long enough for us |
| | | 1026 | | { |
| | 0 | 1027 | | ref byte halfVectorAfterStart = ref Unsafe.Add(ref searchSpace, Vector128<byte>.Count); |
| | | 1028 | | |
| | 0 | 1029 | | ref byte secondVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref halfVectorAfterS |
| | 0 | 1030 | | ? ref Unsafe.Subtract(ref currentSearchSpace, Vector128<byte>.Count) |
| | 0 | 1031 | | : ref searchSpace; |
| | | 1032 | | |
| | 0 | 1033 | | Vector128<byte> source0 = Vector128.LoadUnsafe(ref searchSpace); |
| | 0 | 1034 | | Vector128<byte> source1 = Vector128.LoadUnsafe(ref secondVector); |
| | 0 | 1035 | | Vector256<byte> source = Vector256.Create(source0, source1); |
| | | 1036 | | |
| | 0 | 1037 | | Vector256<byte> result = IndexOfAnyLookup<TNegator>(source, bitmap256_0, bitmap256_1); |
| | 0 | 1038 | | if (result != Vector256<byte>.Zero) |
| | | 1039 | | { |
| | 0 | 1040 | | return ComputeLastIndexOverlapped<byte, TNegator>(ref searchSpace, ref secondVector, result); |
| | | 1041 | | } |
| | | 1042 | | } |
| | | 1043 | | |
| | 0 | 1044 | | return -1; |
| | | 1045 | | } |
| | | 1046 | | |
| | 0 | 1047 | | Vector128<byte> bitmap0 = state.Bitmap0._lower; |
| | 0 | 1048 | | Vector128<byte> bitmap1 = state.Bitmap1._lower; |
| | | 1049 | | |
| | | 1050 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough // The behavior of the rest of the fu |
| | 0 | 1051 | | if (!Avx2.IsSupported && searchSpaceLength > Vector128<byte>.Count) |
| | | 1052 | | #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 1053 | | { |
| | | 1054 | | // Process the input in chunks of 16 bytes. |
| | | 1055 | | // If the input length is a multiple of 16, don't consume the last 16 characters in this loop. |
| | | 1056 | | // Let the fallback below handle it instead. This is why the condition is |
| | | 1057 | | // ">" instead of ">=" above, and why "IsAddressGreaterThan" is used instead of "IsAddressGreaterThanOrE |
| | 0 | 1058 | | ref byte vectorAfterStart = ref Unsafe.Add(ref searchSpace, Vector128<byte>.Count); |
| | | 1059 | | |
| | | 1060 | | do |
| | | 1061 | | { |
| | 0 | 1062 | | currentSearchSpace = ref Unsafe.Subtract(ref currentSearchSpace, Vector128<byte>.Count); |
| | | 1063 | | |
| | 0 | 1064 | | Vector128<byte> source = Vector128.LoadUnsafe(ref currentSearchSpace); |
| | | 1065 | | |
| | 0 | 1066 | | Vector128<byte> result = IndexOfAnyLookup<TNegator>(source, bitmap0, bitmap1); |
| | 0 | 1067 | | if (result != Vector128<byte>.Zero) |
| | | 1068 | | { |
| | 0 | 1069 | | return ComputeLastIndex<byte, TNegator>(ref searchSpace, ref currentSearchSpace, result); |
| | | 1070 | | } |
| | | 1071 | | } |
| | 0 | 1072 | | while (Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref vectorAfterStart)); |
| | | 1073 | | } |
| | | 1074 | | |
| | | 1075 | | // We have 1-16 bytes remaining. Process the first and last half vectors in the search space. |
| | | 1076 | | // They may overlap, but we'll handle that in the index calculation if we do get a match. |
| | 0 | 1077 | | Debug.Assert(searchSpaceLength >= sizeof(ulong), "We expect that the input is long enough for us to load a u |
| | | 1078 | | { |
| | 0 | 1079 | | ref byte halfVectorAfterStart = ref Unsafe.Add(ref searchSpace, sizeof(ulong)); |
| | | 1080 | | |
| | 0 | 1081 | | ref byte secondVector = ref Unsafe.IsAddressGreaterThan(ref currentSearchSpace, ref halfVectorAfterStart |
| | 0 | 1082 | | ? ref Unsafe.Subtract(ref currentSearchSpace, sizeof(ulong)) |
| | 0 | 1083 | | : ref searchSpace; |
| | | 1084 | | |
| | 0 | 1085 | | ulong source0 = Unsafe.ReadUnaligned<ulong>(ref searchSpace); |
| | 0 | 1086 | | ulong source1 = Unsafe.ReadUnaligned<ulong>(ref secondVector); |
| | 0 | 1087 | | Vector128<byte> source = Vector128.Create(source0, source1).AsByte(); |
| | | 1088 | | |
| | 0 | 1089 | | Vector128<byte> result = IndexOfAnyLookup<TNegator>(source, bitmap0, bitmap1); |
| | 0 | 1090 | | if (result != Vector128<byte>.Zero) |
| | | 1091 | | { |
| | 0 | 1092 | | return ComputeLastIndexOverlapped<byte, TNegator>(ref searchSpace, ref secondVector, result); |
| | | 1093 | | } |
| | | 1094 | | } |
| | | 1095 | | |
| | 0 | 1096 | | return -1; |
| | | 1097 | | } |
| | | 1098 | | |
| | | 1099 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1100 | | [CompExactlyDependsOn(typeof(Sse2))] |
| | | 1101 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 1102 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 1103 | | private static Vector128<byte> IndexOfAnyLookup<TNegator, TOptimizations, TUniqueLowNibble>(Vector128<short> sou |
| | | 1104 | | where TNegator : struct, INegator |
| | | 1105 | | where TOptimizations : struct, IOptimizations |
| | | 1106 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst |
| | | 1107 | | { |
| | 0 | 1108 | | Vector128<byte> source = TOptimizations.PackSources(source0.AsUInt16(), source1.AsUInt16()); |
| | | 1109 | | |
| | 0 | 1110 | | Vector128<byte> result = IndexOfAnyLookupCore<TUniqueLowNibble>(source, bitmapLookup); |
| | | 1111 | | |
| | 0 | 1112 | | return TNegator.NegateIfNeeded(result); |
| | | 1113 | | } |
| | | 1114 | | |
| | | 1115 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1116 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 1117 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 1118 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 1119 | | private static Vector128<byte> IndexOfAnyLookupCore<TUniqueLowNibble>(Vector128<byte> source, Vector128<byte> bi |
| | | 1120 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst |
| | | 1121 | | { |
| | | 1122 | | if (TUniqueLowNibble.Value) |
| | | 1123 | | { |
| | | 1124 | | // Based on http://0x80.pl/articles/simd-byte-lookup.html#special-case-3-unique-lower-and-higher-nibbles |
| | | 1125 | | |
| | | 1126 | | // On X86, the Ssse3.Shuffle instruction will already perform an implicit 'AND 0xF' on the indices, so w |
| | | 1127 | | // For values above 127, Ssse3.Shuffle will also set the result to 0. This is fine as we only use this a |
| | | 1128 | | // all values are <= 127 when Ssse3 is supported (see CanUseUniqueLowNibbleSearch). |
| | | 1129 | | // False positives from values mapped to 0 will be ruled out by the Vector128.Equals comparison below. |
| | 0 | 1130 | | Vector128<byte> lowNibbles = Ssse3.IsSupported |
| | 0 | 1131 | | ? source |
| | 0 | 1132 | | : source & Vector128.Create((byte)0xF); |
| | | 1133 | | |
| | | 1134 | | // We use a shuffle to look up potential matches for each byte based on its low nibble. |
| | | 1135 | | // Since all values have a unique low nibble, there's at most one potential match per nibble. |
| | 0 | 1136 | | Vector128<byte> values = SearchValues.ShuffleNativeModified(bitmapLookup, lowNibbles); |
| | | 1137 | | |
| | | 1138 | | // Compare potential matches with the source to rule out false positives that have a different high nibb |
| | 0 | 1139 | | return Vector128.Equals(source, values); |
| | | 1140 | | } |
| | | 1141 | | else |
| | | 1142 | | { |
| | | 1143 | | // On X86, the Ssse3.Shuffle instruction will already perform an implicit 'AND 0xF' on the indices, so w |
| | | 1144 | | // For values above 127, Ssse3.Shuffle will also set the result to 0. This is fine as we don't want non- |
| | 0 | 1145 | | Vector128<byte> lowNibbles = Ssse3.IsSupported |
| | 0 | 1146 | | ? source |
| | 0 | 1147 | | : source & Vector128.Create((byte)0xF); |
| | | 1148 | | |
| | | 1149 | | // On ARM, we have an instruction for an arithmetic right shift of 1-byte signed values. |
| | | 1150 | | // The shift will map values above 127 to values above 16, which the shuffle will then map to 0. |
| | | 1151 | | // On X86 and WASM, use a logical right shift instead. |
| | | 1152 | | Vector128<byte> highNibbles = AdvSimd.IsSupported |
| | | 1153 | | ? (source.AsSByte() >> 4).AsByte() |
| | | 1154 | | : source >>> 4; |
| | | 1155 | | |
| | | 1156 | | // The bitmapLookup represents a 8x16 table of bits, indicating whether a character is present in the ne |
| | | 1157 | | // Lookup the rows via the lower nibble and the column via the higher nibble. |
| | 0 | 1158 | | Vector128<byte> bitMask = SearchValues.ShuffleNativeModified(bitmapLookup, lowNibbles); |
| | | 1159 | | |
| | | 1160 | | // For values above 127, the high nibble will be above 7. We construct the positions vector for the shuf |
| | 0 | 1161 | | Vector128<byte> bitPositions = SearchValues.ShuffleNativeModified(Vector128.Create(0x8040201008040201, 0 |
| | | 1162 | | |
| | 0 | 1163 | | return bitMask & bitPositions; |
| | | 1164 | | } |
| | | 1165 | | } |
| | | 1166 | | |
| | | 1167 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1168 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 1169 | | private static Vector256<byte> IndexOfAnyLookup<TNegator, TOptimizations, TUniqueLowNibble>(Vector256<short> sou |
| | | 1170 | | where TNegator : struct, INegator |
| | | 1171 | | where TOptimizations : struct, IOptimizations |
| | | 1172 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst |
| | | 1173 | | { |
| | 0 | 1174 | | Vector256<byte> source = TOptimizations.PackSources(source0.AsUInt16(), source1.AsUInt16()); |
| | | 1175 | | |
| | 0 | 1176 | | Vector256<byte> result = IndexOfAnyLookupCore<TUniqueLowNibble>(source, bitmapLookup); |
| | | 1177 | | |
| | 0 | 1178 | | return TNegator.NegateIfNeeded(result); |
| | | 1179 | | } |
| | | 1180 | | |
| | | 1181 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1182 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 1183 | | private static Vector256<byte> IndexOfAnyLookupCore<TUniqueLowNibble>(Vector256<byte> source, Vector256<byte> bi |
| | | 1184 | | where TUniqueLowNibble : struct, SearchValues.IRuntimeConst |
| | | 1185 | | { |
| | | 1186 | | // See comments in IndexOfAnyLookupCore(Vector128<byte>) above for more details. |
| | 0 | 1187 | | if (TUniqueLowNibble.Value) |
| | | 1188 | | { |
| | 0 | 1189 | | Vector256<byte> values = Avx2.Shuffle(bitmapLookup, source); |
| | 0 | 1190 | | return Vector256.Equals(source, values); |
| | | 1191 | | } |
| | | 1192 | | else |
| | | 1193 | | { |
| | 0 | 1194 | | Vector256<byte> highNibbles = source >>> 4; |
| | 0 | 1195 | | Vector256<byte> bitMask = Avx2.Shuffle(bitmapLookup, source); |
| | 0 | 1196 | | Vector256<byte> bitPositions = Avx2.Shuffle(Vector256.Create(0x8040201008040201).AsByte(), highNibbles); |
| | 0 | 1197 | | return bitMask & bitPositions; |
| | | 1198 | | } |
| | | 1199 | | } |
| | | 1200 | | |
| | | 1201 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1202 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 1203 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 1204 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 1205 | | private static Vector128<byte> IndexOfAnyLookup<TNegator>(Vector128<byte> source, Vector128<byte> bitmapLookup0, |
| | | 1206 | | where TNegator : struct, INegator |
| | | 1207 | | { |
| | | 1208 | | // http://0x80.pl/articles/simd-byte-lookup.html#universal-algorithm |
| | | 1209 | | |
| | 0 | 1210 | | Vector128<byte> lowNibbles = source & Vector128.Create((byte)0xF); |
| | 0 | 1211 | | Vector128<byte> highNibbles = source >>> 4; |
| | | 1212 | | |
| | 0 | 1213 | | Vector128<byte> row0 = Vector128.ShuffleNative(bitmapLookup0, lowNibbles); |
| | 0 | 1214 | | Vector128<byte> row1 = Vector128.ShuffleNative(bitmapLookup1, lowNibbles); |
| | | 1215 | | |
| | 0 | 1216 | | Vector128<byte> bitmask = Vector128.ShuffleNative(Vector128.Create(0x8040201008040201).AsByte(), highNibbles |
| | | 1217 | | |
| | 0 | 1218 | | Vector128<byte> mask = Vector128.GreaterThan(highNibbles.AsSByte(), Vector128.Create((sbyte)0x7)).AsByte(); |
| | 0 | 1219 | | Vector128<byte> bitsets = Vector128.ConditionalSelect(mask, row1, row0); |
| | | 1220 | | |
| | 0 | 1221 | | Vector128<byte> result = Vector128.Equals(bitsets & bitmask, bitmask); |
| | | 1222 | | |
| | 0 | 1223 | | return TNegator.NegateIfNeeded(result); |
| | | 1224 | | } |
| | | 1225 | | |
| | | 1226 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1227 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 1228 | | private static Vector256<byte> IndexOfAnyLookup<TNegator>(Vector256<byte> source, Vector256<byte> bitmapLookup0, |
| | | 1229 | | where TNegator : struct, INegator |
| | | 1230 | | { |
| | | 1231 | | // http://0x80.pl/articles/simd-byte-lookup.html#universal-algorithm |
| | | 1232 | | |
| | 0 | 1233 | | Vector256<byte> lowNibbles = source & Vector256.Create((byte)0xF); |
| | 0 | 1234 | | Vector256<byte> highNibbles = source >>> 4; |
| | | 1235 | | |
| | 0 | 1236 | | Vector256<byte> row0 = Avx2.Shuffle(bitmapLookup0, lowNibbles); |
| | 0 | 1237 | | Vector256<byte> row1 = Avx2.Shuffle(bitmapLookup1, lowNibbles); |
| | | 1238 | | |
| | 0 | 1239 | | Vector256<byte> bitmask = Avx2.Shuffle(Vector256.Create(0x8040201008040201).AsByte(), highNibbles); |
| | | 1240 | | |
| | 0 | 1241 | | Vector256<byte> mask = Vector256.GreaterThan(highNibbles.AsSByte(), Vector256.Create((sbyte)0x7)).AsByte(); |
| | 0 | 1242 | | Vector256<byte> bitsets = Vector256.ConditionalSelect(mask, row1, row0); |
| | | 1243 | | |
| | 0 | 1244 | | Vector256<byte> result = Vector256.Equals(bitsets & bitmask, bitmask); |
| | | 1245 | | |
| | 0 | 1246 | | return TNegator.NegateIfNeeded(result); |
| | | 1247 | | } |
| | | 1248 | | |
| | | 1249 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1250 | | private static unsafe int ComputeLastIndex<T, TNegator>(ref T searchSpace, ref T current, Vector128<byte> result |
| | | 1251 | | where TNegator : struct, INegator |
| | | 1252 | | { |
| | 0 | 1253 | | int offsetInVector = TNegator.IndexOfLastMatch(result); |
| | 0 | 1254 | | return offsetInVector + (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref current) / (nuint)sizeof(T)); |
| | | 1255 | | } |
| | | 1256 | | |
| | | 1257 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1258 | | private static unsafe int ComputeLastIndexOverlapped<T, TNegator>(ref T searchSpace, ref T secondVector, Vector1 |
| | | 1259 | | where TNegator : struct, INegator |
| | | 1260 | | { |
| | 0 | 1261 | | int offsetInVector = TNegator.IndexOfLastMatch(result); |
| | | 1262 | | |
| | 0 | 1263 | | if (offsetInVector < Vector128<short>.Count) |
| | | 1264 | | { |
| | 0 | 1265 | | return offsetInVector; |
| | | 1266 | | } |
| | | 1267 | | |
| | | 1268 | | // We matched within the second vector |
| | 0 | 1269 | | return offsetInVector - Vector128<short>.Count + (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref secondV |
| | | 1270 | | } |
| | | 1271 | | |
| | | 1272 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1273 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 1274 | | private static unsafe int ComputeLastIndex<T, TNegator>(ref T searchSpace, ref T current, Vector256<byte> result |
| | | 1275 | | where TNegator : struct, INegator |
| | | 1276 | | { |
| | 0 | 1277 | | if (typeof(T) == typeof(short)) |
| | | 1278 | | { |
| | 0 | 1279 | | result = PackedSpanHelpers.FixUpPackedVector256Result(result); |
| | | 1280 | | } |
| | | 1281 | | |
| | 0 | 1282 | | int offsetInVector = TNegator.IndexOfLastMatch(result); |
| | 0 | 1283 | | return offsetInVector + (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref current) / (nuint)sizeof(T)); |
| | | 1284 | | } |
| | | 1285 | | |
| | | 1286 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1287 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 1288 | | private static unsafe int ComputeLastIndexOverlapped<T, TNegator>(ref T searchSpace, ref T secondVector, Vector2 |
| | | 1289 | | where TNegator : struct, INegator |
| | | 1290 | | { |
| | 0 | 1291 | | if (typeof(T) == typeof(short)) |
| | | 1292 | | { |
| | 0 | 1293 | | result = PackedSpanHelpers.FixUpPackedVector256Result(result); |
| | | 1294 | | } |
| | | 1295 | | |
| | 0 | 1296 | | int offsetInVector = TNegator.IndexOfLastMatch(result); |
| | | 1297 | | |
| | 0 | 1298 | | if (offsetInVector < Vector256<short>.Count) |
| | | 1299 | | { |
| | 0 | 1300 | | return offsetInVector; |
| | | 1301 | | } |
| | | 1302 | | |
| | | 1303 | | // We matched within the second vector |
| | 0 | 1304 | | return offsetInVector - Vector256<short>.Count + (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref secondV |
| | | 1305 | | } |
| | | 1306 | | |
| | | 1307 | | internal interface INegator |
| | | 1308 | | { |
| | | 1309 | | static abstract bool NegateIfNeeded(bool result); |
| | | 1310 | | static abstract Vector128<byte> NegateIfNeeded(Vector128<byte> result); |
| | | 1311 | | static abstract Vector256<byte> NegateIfNeeded(Vector256<byte> result); |
| | | 1312 | | static abstract int IndexOfFirstMatch(Vector128<byte> result); |
| | | 1313 | | static abstract int IndexOfFirstMatch(Vector256<byte> result); |
| | | 1314 | | static abstract int IndexOfLastMatch(Vector128<byte> result); |
| | | 1315 | | static abstract int IndexOfLastMatch(Vector256<byte> result); |
| | | 1316 | | } |
| | | 1317 | | |
| | | 1318 | | internal readonly struct DontNegate : INegator |
| | | 1319 | | { |
| | 0 | 1320 | | public static bool NegateIfNeeded(bool result) => result; |
| | 0 | 1321 | | public static Vector128<byte> NegateIfNeeded(Vector128<byte> result) => result; |
| | 0 | 1322 | | public static Vector256<byte> NegateIfNeeded(Vector256<byte> result) => result; |
| | | 1323 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 0 | 1324 | | public static int IndexOfFirstMatch(Vector128<byte> result) => Vector128.IndexOfFirstMatch(~Vector128.Equals |
| | | 1325 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 0 | 1326 | | public static int IndexOfFirstMatch(Vector256<byte> result) => Vector256.IndexOfFirstMatch(~Vector256.Equals |
| | | 1327 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 0 | 1328 | | public static int IndexOfLastMatch(Vector128<byte> result) => Vector128.IndexOfLastMatch(~Vector128.Equals(r |
| | | 1329 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 0 | 1330 | | public static int IndexOfLastMatch(Vector256<byte> result) => Vector256.IndexOfLastMatch(~Vector256.Equals(r |
| | | 1331 | | } |
| | | 1332 | | |
| | | 1333 | | internal readonly struct Negate : INegator |
| | | 1334 | | { |
| | | 1335 | | // AdvSimd expects that a given element is strictly Zero or AllBitsSet |
| | | 1336 | | // so we need to ensure that we normalize the input prior to calling |
| | | 1337 | | // IndexOfFirstMatch or IndexOfLastMatch |
| | | 1338 | | |
| | 0 | 1339 | | public static bool NegateIfNeeded(bool result) => !result; |
| | | 1340 | | // This is intentionally testing for equality with 0 instead of "~result". |
| | | 1341 | | // We want to know if any character didn't match, as that means it should be treated as a match for the -Exc |
| | | 1342 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 0 | 1343 | | public static Vector128<byte> NegateIfNeeded(Vector128<byte> result) => Vector128.Equals(result, Vector128<b |
| | | 1344 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 0 | 1345 | | public static Vector256<byte> NegateIfNeeded(Vector256<byte> result) => Vector256.Equals(result, Vector256<b |
| | | 1346 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1347 | | public static int IndexOfFirstMatch(Vector128<byte> result) |
| | | 1348 | | { |
| | | 1349 | | if (AdvSimd.IsSupported) |
| | | 1350 | | { |
| | | 1351 | | result = (result.AsSByte() >> 7).AsByte(); |
| | | 1352 | | } |
| | 0 | 1353 | | return Vector128.IndexOfFirstMatch(result); |
| | | 1354 | | } |
| | | 1355 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 0 | 1356 | | public static int IndexOfFirstMatch(Vector256<byte> result) => Vector256.IndexOfFirstMatch(result); |
| | | 1357 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1358 | | public static int IndexOfLastMatch(Vector128<byte> result) |
| | | 1359 | | { |
| | | 1360 | | if (AdvSimd.IsSupported) |
| | | 1361 | | { |
| | | 1362 | | result = (result.AsSByte() >> 7).AsByte(); |
| | | 1363 | | } |
| | 0 | 1364 | | return Vector128.IndexOfLastMatch(result); |
| | | 1365 | | } |
| | | 1366 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | 0 | 1367 | | public static int IndexOfLastMatch(Vector256<byte> result) => Vector256.IndexOfLastMatch(result); |
| | | 1368 | | } |
| | | 1369 | | |
| | | 1370 | | internal interface IOptimizations |
| | | 1371 | | { |
| | | 1372 | | // Pack two vectors of characters into bytes. |
| | | 1373 | | // X86 and WASM when the needle does not contain 0: Downcast every character using saturation. |
| | | 1374 | | // - Values <= 32767 result in min(value, 255). |
| | | 1375 | | // - Values > 32767 result in 0. Because of this we must do more work to handle needles that contain 0. |
| | | 1376 | | // Otherwise: Do narrowing saturation over unsigned values. |
| | | 1377 | | // - All values result in min(value, 255) |
| | | 1378 | | static abstract Vector128<byte> PackSources(Vector128<ushort> lower, Vector128<ushort> upper); |
| | | 1379 | | static abstract Vector256<byte> PackSources(Vector256<ushort> lower, Vector256<ushort> upper); |
| | | 1380 | | } |
| | | 1381 | | |
| | | 1382 | | internal readonly struct Ssse3AndWasmHandleZeroInNeedle : IOptimizations |
| | | 1383 | | { |
| | | 1384 | | // Replace with Vector128.NarrowWithSaturation once https://github.com/dotnet/runtime/issues/75724 is implem |
| | | 1385 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1386 | | [CompExactlyDependsOn(typeof(Sse2))] |
| | | 1387 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 1388 | | public static Vector128<byte> PackSources(Vector128<ushort> lower, Vector128<ushort> upper) |
| | | 1389 | | { |
| | | 1390 | | Vector128<short> lowerMin = Vector128.Min(lower, Vector128.Create((ushort)255)).AsInt16(); |
| | 0 | 1391 | | Vector128<short> upperMin = Vector128.Min(upper, Vector128.Create((ushort)255)).AsInt16(); |
| | | 1392 | | |
| | 0 | 1393 | | if (Sse2.IsSupported) |
| | | 1394 | | { |
| | 0 | 1395 | | return Sse2.PackUnsignedSaturate(lowerMin, upperMin); |
| | | 1396 | | } |
| | | 1397 | | else if (PackedSimd.IsSupported) |
| | | 1398 | | { |
| | | 1399 | | return PackedSimd.ConvertNarrowingSaturateUnsigned(lowerMin, upperMin); |
| | | 1400 | | } |
| | | 1401 | | else |
| | | 1402 | | { |
| | | 1403 | | // We explicitly recheck each IsSupported query to ensure that the trimmer can see which paths are l |
| | 0 | 1404 | | ThrowHelper.ThrowUnreachableException(); |
| | | 1405 | | return default; |
| | | 1406 | | } |
| | | 1407 | | } |
| | | 1408 | | |
| | | 1409 | | // Replace with Vector256.NarrowWithSaturation once https://github.com/dotnet/runtime/issues/75724 is implem |
| | | 1410 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 1411 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1412 | | public static Vector256<byte> PackSources(Vector256<ushort> lower, Vector256<ushort> upper) |
| | | 1413 | | { |
| | 0 | 1414 | | return Avx2.PackUnsignedSaturate( |
| | 0 | 1415 | | Vector256.Min(lower, Vector256.Create((ushort)255)).AsInt16(), |
| | 0 | 1416 | | Vector256.Min(upper, Vector256.Create((ushort)255)).AsInt16()); |
| | | 1417 | | } |
| | | 1418 | | } |
| | | 1419 | | |
| | | 1420 | | internal readonly struct Default : IOptimizations |
| | | 1421 | | { |
| | | 1422 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1423 | | [CompExactlyDependsOn(typeof(Sse2))] |
| | | 1424 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 1425 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 1426 | | public static Vector128<byte> PackSources(Vector128<ushort> lower, Vector128<ushort> upper) |
| | | 1427 | | { |
| | | 1428 | | if (Sse2.IsSupported) |
| | | 1429 | | { |
| | 0 | 1430 | | return Sse2.PackUnsignedSaturate(lower.AsInt16(), upper.AsInt16()); |
| | | 1431 | | } |
| | | 1432 | | else if (AdvSimd.IsSupported) |
| | | 1433 | | { |
| | | 1434 | | return AdvSimd.ExtractNarrowingSaturateUpper(AdvSimd.ExtractNarrowingSaturateLower(lower), upper); |
| | | 1435 | | } |
| | | 1436 | | else if (PackedSimd.IsSupported) |
| | | 1437 | | { |
| | | 1438 | | return PackedSimd.ConvertNarrowingSaturateUnsigned(lower.AsInt16(), upper.AsInt16()); |
| | | 1439 | | } |
| | | 1440 | | else |
| | | 1441 | | { |
| | | 1442 | | // We explicitly recheck each IsSupported query to ensure that the trimmer can see which paths are l |
| | 0 | 1443 | | ThrowHelper.ThrowUnreachableException(); |
| | | 1444 | | return default; |
| | | 1445 | | } |
| | | 1446 | | } |
| | | 1447 | | |
| | | 1448 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 1449 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1450 | | public static Vector256<byte> PackSources(Vector256<ushort> lower, Vector256<ushort> upper) |
| | | 1451 | | { |
| | 0 | 1452 | | return Avx2.PackUnsignedSaturate(lower.AsInt16(), upper.AsInt16()); |
| | | 1453 | | } |
| | | 1454 | | } |
| | | 1455 | | |
| | | 1456 | | private interface IResultMapper<T, TResult> |
| | | 1457 | | where TResult : struct |
| | | 1458 | | { |
| | | 1459 | | static abstract TResult NotFound { get; } |
| | | 1460 | | |
| | | 1461 | | static abstract TResult ScalarResult(ref T searchSpace, ref T current); |
| | | 1462 | | static abstract TResult FirstIndex<TNegator>(ref T searchSpace, ref T current, Vector128<byte> result) where |
| | | 1463 | | static abstract TResult FirstIndex<TNegator>(ref T searchSpace, ref T current, Vector256<byte> result) where |
| | | 1464 | | static abstract TResult FirstIndexOverlapped<TNegator>(ref T searchSpace, ref T current0, ref T current1, Ve |
| | | 1465 | | static abstract TResult FirstIndexOverlapped<TNegator>(ref T searchSpace, ref T current0, ref T current1, Ve |
| | | 1466 | | } |
| | | 1467 | | |
| | | 1468 | | private readonly struct ContainsAnyResultMapper<T> : IResultMapper<T, bool> |
| | | 1469 | | { |
| | 0 | 1470 | | public static bool NotFound => false; |
| | | 1471 | | |
| | 0 | 1472 | | public static bool ScalarResult(ref T searchSpace, ref T current) => true; |
| | 0 | 1473 | | public static bool FirstIndex<TNegator>(ref T searchSpace, ref T current, Vector128<byte> result) where TNeg |
| | 0 | 1474 | | public static bool FirstIndex<TNegator>(ref T searchSpace, ref T current, Vector256<byte> result) where TNeg |
| | 0 | 1475 | | public static bool FirstIndexOverlapped<TNegator>(ref T searchSpace, ref T current0, ref T current1, Vector1 |
| | 0 | 1476 | | public static bool FirstIndexOverlapped<TNegator>(ref T searchSpace, ref T current0, ref T current1, Vector2 |
| | | 1477 | | } |
| | | 1478 | | |
| | | 1479 | | private readonly unsafe struct IndexOfAnyResultMapper<T> : IResultMapper<T, int> |
| | | 1480 | | { |
| | 0 | 1481 | | public static int NotFound => -1; |
| | | 1482 | | |
| | | 1483 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1484 | | public static int ScalarResult(ref T searchSpace, ref T current) |
| | | 1485 | | { |
| | 0 | 1486 | | return (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref current) / (nuint)sizeof(T)); |
| | | 1487 | | } |
| | | 1488 | | |
| | | 1489 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1490 | | public static int FirstIndex<TNegator>(ref T searchSpace, ref T current, Vector128<byte> result) where TNega |
| | | 1491 | | { |
| | 0 | 1492 | | int offsetInVector = TNegator.IndexOfFirstMatch(result); |
| | 0 | 1493 | | return offsetInVector + (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref current) / (nuint)sizeof(T)) |
| | | 1494 | | } |
| | | 1495 | | |
| | | 1496 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1497 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 1498 | | public static int FirstIndex<TNegator>(ref T searchSpace, ref T current, Vector256<byte> result) where TNega |
| | | 1499 | | { |
| | 0 | 1500 | | if (typeof(T) == typeof(short)) |
| | | 1501 | | { |
| | 0 | 1502 | | result = PackedSpanHelpers.FixUpPackedVector256Result(result); |
| | | 1503 | | } |
| | | 1504 | | |
| | 0 | 1505 | | int offsetInVector = TNegator.IndexOfFirstMatch(result); |
| | 0 | 1506 | | return offsetInVector + (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref current) / (nuint)sizeof(T)) |
| | | 1507 | | } |
| | | 1508 | | |
| | | 1509 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1510 | | public static int FirstIndexOverlapped<TNegator>(ref T searchSpace, ref T current0, ref T current1, Vector12 |
| | | 1511 | | { |
| | 0 | 1512 | | int offsetInVector = TNegator.IndexOfFirstMatch(result); |
| | | 1513 | | |
| | 0 | 1514 | | if (offsetInVector >= Vector128<short>.Count) |
| | | 1515 | | { |
| | | 1516 | | // We matched within the second vector |
| | 0 | 1517 | | current0 = ref current1; |
| | 0 | 1518 | | offsetInVector -= Vector128<short>.Count; |
| | | 1519 | | } |
| | 0 | 1520 | | return offsetInVector + (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref current0) / (nuint)sizeof(T) |
| | | 1521 | | } |
| | | 1522 | | |
| | | 1523 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1524 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 1525 | | public static int FirstIndexOverlapped<TNegator>(ref T searchSpace, ref T current0, ref T current1, Vector25 |
| | | 1526 | | { |
| | 0 | 1527 | | if (typeof(T) == typeof(short)) |
| | | 1528 | | { |
| | 0 | 1529 | | result = PackedSpanHelpers.FixUpPackedVector256Result(result); |
| | | 1530 | | } |
| | | 1531 | | |
| | 0 | 1532 | | int offsetInVector = TNegator.IndexOfFirstMatch(result); |
| | | 1533 | | |
| | 0 | 1534 | | if (offsetInVector >= Vector256<short>.Count) |
| | | 1535 | | { |
| | | 1536 | | // We matched within the second vector |
| | 0 | 1537 | | current0 = ref current1; |
| | 0 | 1538 | | offsetInVector -= Vector256<short>.Count; |
| | | 1539 | | } |
| | 0 | 1540 | | return offsetInVector + (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref current0) / (nuint)sizeof(T) |
| | | 1541 | | } |
| | | 1542 | | } |
| | | 1543 | | } |
| | | 1544 | | } |
| | | 1545 | | |