| | | 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.Collections.Generic; |
| | | 5 | | using System.Diagnostics; |
| | | 6 | | using System.Numerics; |
| | | 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 | | using static System.Buffers.StringSearchValuesHelper; |
| | | 14 | | using static System.Buffers.TeddyHelper; |
| | | 15 | | |
| | | 16 | | namespace System.Buffers |
| | | 17 | | { |
| | | 18 | | // This is an implementation of the "Teddy" vectorized multi-substring matching algorithm. |
| | | 19 | | // |
| | | 20 | | // We have several vectorized string searching approaches implemented as part of SearchValues, among them are: |
| | | 21 | | // - 'IndexOfAnyAsciiSearcher', which can quickly find the next position of any character in a set. |
| | | 22 | | // - 'SingleStringSearchValuesThreeChars', which can determine the likely positions where a value may start. |
| | | 23 | | // The fast scan for starting positions is followed by a verification step that rules out false positives. |
| | | 24 | | // To reduce the number of false positives, the initial scan looks for multiple characters at different positions, |
| | | 25 | | // and only considers candidates where all of those match at the same time. |
| | | 26 | | // |
| | | 27 | | // Teddy combines the two to search for multiple values at the same time. |
| | | 28 | | // Similar to 'SingleStringSearchValuesThreeChars', it employs the starting positions scan and verification steps. |
| | | 29 | | // To reduce the number of values we have to check during verification, it also checks multiple characters in the in |
| | | 30 | | // We could implement that by just merging the two approaches: check for any of the value characters at position 0, |
| | | 31 | | // AND those results together and verify potential matches. The issue with this approach is that we would always hav |
| | | 32 | | // all values in the verification step, and we would be hitting many false positives as the number of values increas |
| | | 33 | | // For example, if you are searching for "Teddy" and "Bear", position 0 could be either 'T' or 'B', position 1 could |
| | | 34 | | // and position 2 could be 'd' or 'a'. We would do separate comparisons for each of those positions and then AND tog |
| | | 35 | | // Because there is no correlation between the values, we would get false positives for inputs like "Bed" and "Tea", |
| | | 36 | | // and we wouldn't know whether the match location was because of "Teddy" or "Bear", and thus which to proceed to ve |
| | | 37 | | // |
| | | 38 | | // What is special about Teddy is how we perform that initial scan to not only determine the possible starting locat |
| | | 39 | | // but also which values are the potential matches at each of those offsets. |
| | | 40 | | // Instead of encoding all starting characters at a given position into a bitmap that can only answer yes/no whether |
| | | 41 | | // character is present in the set, we want to encode both the character and the values in which it appears. |
| | | 42 | | // We only have 128* bits to work with, so we do this by encoding 8 bits of information for each nibble (half byte). |
| | | 43 | | // Those 8 bits represent a bitmask of values that contain that nibble at that location. |
| | | 44 | | // If we compare the input against two such bitmaps and AND the results together, we can determine which positions i |
| | | 45 | | // contained a matching character, and which of our values matched said character at that position. |
| | | 46 | | // We repeat this a few more times (checking 3 bytes or 6 nibbles for N=3) at different offsets to reduce the number |
| | | 47 | | // See 'TeddyBucketizer.GenerateNonBucketizedFingerprint' for details around how such a bitmap is constructed. |
| | | 48 | | // |
| | | 49 | | // For example if we are searching for strings "Teddy" and "Bear", we will look for 'T' or 'B' at position 0, 'e' at |
| | | 50 | | // To look for 'T' (0x54) or 'B' (0x42), we will check for a high nibble of 5 or 4, and lower nibble of 4 or 2. |
| | | 51 | | // Each value's presence is indicated by 1 bit. We will use 1 (0b00000001) for the first value ("Teddy") and 2 (0b00 |
| | | 52 | | // Our bitmaps will look like so (1 is set for high 5 and low 4, 2 is set for high 4 and low 2): |
| | | 53 | | // bitmapHigh: [0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] |
| | | 54 | | // bitmapLow: [0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] |
| | | 55 | | // ^ ^ ^ ^ |
| | | 56 | | // |
| | | 57 | | // To map an input nibble to its corresponding bitmask, we use 'Shuffle(bitmap, nibble)'. |
| | | 58 | | // For an input like "TeddyBearFactory", our result will be |
| | | 59 | | // input: [T, e, d, d, y, B, e, a, r, F, a, c, t, o, r, y] |
| | | 60 | | // inputHigh: [5, 6, 6, 6, 7, 4, 6, 6, 7, 4, 6, 6, 7, 6, 7, 7] (values in hex) |
| | | 61 | | // inputLow: [4, 5, 4, 4, 9, 2, 5, 1, 2, 6, 1, 3, 4, F, 2, 9] (values in hex) |
| | | 62 | | // resultHigh: [1, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0] |
| | | 63 | | // resultLow: [1, 0, 1, 1, 0, 2, 0, 0, 2, 0, 0, 0, 1, 0, 2, 0] |
| | | 64 | | // result: [1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (resultHigh & resultLow) |
| | | 65 | | // ^ ^ |
| | | 66 | | // Note how we had quite a few false positives for individual nibbles that we ruled away after checking both nibbles |
| | | 67 | | // See 'TeddyHelper.ProcessInputN3' for details about how we combine results for multiple characters at different of |
| | | 68 | | // |
| | | 69 | | // The description above states that we can only encode the information about 8 values. To get around that limitatio |
| | | 70 | | // we group multiple values together into buckets. Instead of looking for positions where a single value may match, |
| | | 71 | | // we look for positions where any value from a given bucket may match. |
| | | 72 | | // When creating the bitmap we don't set the bit for just one nibble value, but for each of the values in that bucke |
| | | 73 | | // For example if "Teddy" and "Bear" were both in the same bucket, the high nibble bitmap would map both 5 and 4 to |
| | | 74 | | // We may see more false positives ('R' (0x52) and 'D' (0x44) would now also map to the same bucket), but we get to |
| | | 75 | | // many more values at the same time. Instead of 8 values, we are now capable of looking for 8 buckets of values at |
| | | 76 | | // See 'TeddyBucketizer.Bucketize' for details about how values are grouped into buckets. |
| | | 77 | | // See 'TeddyBucketizer.GenerateBucketizedFingerprint' for details around how such a bitmap is constructed. |
| | | 78 | | // |
| | | 79 | | // Teddy works in terms of bytes, but .NET chars represent UTF-16 code units. |
| | | 80 | | // We currently only use Teddy if the 2 or 3 starting characters are all ASCII. This limitation could be lifted in t |
| | | 81 | | // Since we know that all of the characters we are looking for are ASCII, we also know that only other ASCII charact |
| | | 82 | | // Making use of that fact, we narrow UTF-16 code units into bytes when reading the input (see 'TeddyHelper.LoadAndP |
| | | 83 | | // While such narrowing does corrupt non-ASCII values, they are all mapped to values outside of ASCII, so they won't |
| | | 84 | | // ASCII values remain unaffected since their high byte in UTF-16 representation is 0. |
| | | 85 | | // |
| | | 86 | | // To handle case-insensitive matching, all values are normalized to their uppercase equivalents ahead of time and t |
| | | 87 | | // generated as if all characters were uppercase. During the search, the input is also transformed into uppercase be |
| | | 88 | | // |
| | | 89 | | // * With wider vectors (256- and 512-bit), we have more bits available, but we currently only duplicate the origina |
| | | 90 | | // and perform the search on more characters at a time. We could instead choose to encode more information per nibbl |
| | | 91 | | // the number of characters we check per loop iteration for fewer false positives we then have to rule out during th |
| | | 92 | | // |
| | | 93 | | // For an alternative description of the algorithm, see |
| | | 94 | | // https://github.com/BurntSushi/aho-corasick/blob/8d735471fc12f0ca570cead8e17342274fae6331/src/packed/teddy/README. |
| | | 95 | | // Has an O(i * m) worst-case, with the expected time closer to O(i) for good bucket distributions. |
| | | 96 | | internal abstract class AsciiStringSearchValuesTeddyBase<TBucketized, TStartCaseSensitivity, TCaseSensitivity> : Str |
| | | 97 | | where TBucketized : struct, SearchValues.IRuntimeConst |
| | | 98 | | where TStartCaseSensitivity : struct, ICaseSensitivity // Refers to the characters being matched by Teddy |
| | | 99 | | where TCaseSensitivity : struct, ICaseSensitivity // Refers to the rest of the value for the verification |
| | | 100 | | { |
| | | 101 | | // We may be using N2 or N3 mode depending on whether we're checking 2 or 3 starting bytes for each bucket. |
| | | 102 | | // The result of ProcessInputN2 and ProcessInputN3 are offset by 1 and 2 positions respectively (MatchStartOffse |
| | | 103 | | // See the full description of TeddyHelper.ProcessInputN3 for more details about why these constants exist. |
| | | 104 | | private const int MatchStartOffsetN2 = 1; |
| | | 105 | | private const int MatchStartOffsetN3 = 2; |
| | | 106 | | private const int CharsPerIterationVector128 = 16; |
| | | 107 | | private const int CharsPerIterationAvx2 = 32; |
| | | 108 | | private const int CharsPerIterationAvx512 = 64; |
| | | 109 | | |
| | | 110 | | // We may have up to 8 buckets. |
| | | 111 | | // If we have <= 8 strings, the buckets will be the strings themselves, and TBucketized.Value will be false. |
| | | 112 | | // If we have more than 8, the buckets will be string[], and TBucketized.Value will be true. |
| | | 113 | | private readonly InlineArray8<object?> _buckets; |
| | | 114 | | |
| | | 115 | | private readonly Vector512<byte> |
| | | 116 | | _n0Low, _n0High, |
| | | 117 | | _n1Low, _n1High, |
| | | 118 | | _n2Low, _n2High; |
| | | 119 | | |
| | 0 | 120 | | protected AsciiStringSearchValuesTeddyBase(ReadOnlySpan<string> values, HashSet<string> uniqueValues, int n) : b |
| | | 121 | | { |
| | 0 | 122 | | Debug.Assert(!TBucketized.Value); |
| | 0 | 123 | | Debug.Assert(n is 2 or 3); |
| | | 124 | | |
| | 0 | 125 | | ReadOnlySpan<object?>.CastUp(values).CopyTo(_buckets); |
| | | 126 | | |
| | 0 | 127 | | (_n0Low, _n0High) = TeddyBucketizer.GenerateNonBucketizedFingerprint(values, offset: 0); |
| | 0 | 128 | | (_n1Low, _n1High) = TeddyBucketizer.GenerateNonBucketizedFingerprint(values, offset: 1); |
| | | 129 | | |
| | 0 | 130 | | if (n == 3) |
| | | 131 | | { |
| | 0 | 132 | | (_n2Low, _n2High) = TeddyBucketizer.GenerateNonBucketizedFingerprint(values, offset: 2); |
| | | 133 | | } |
| | 0 | 134 | | } |
| | | 135 | | |
| | 0 | 136 | | protected AsciiStringSearchValuesTeddyBase(string[][] buckets, ReadOnlySpan<string> values, HashSet<string> uniq |
| | | 137 | | { |
| | 0 | 138 | | Debug.Assert(TBucketized.Value); |
| | 0 | 139 | | Debug.Assert(n is 2 or 3); |
| | | 140 | | |
| | 0 | 141 | | ((ReadOnlySpan<object?>)buckets).CopyTo(_buckets); |
| | | 142 | | |
| | 0 | 143 | | (_n0Low, _n0High) = TeddyBucketizer.GenerateBucketizedFingerprint(buckets, offset: 0); |
| | 0 | 144 | | (_n1Low, _n1High) = TeddyBucketizer.GenerateBucketizedFingerprint(buckets, offset: 1); |
| | | 145 | | |
| | 0 | 146 | | if (n == 3) |
| | | 147 | | { |
| | 0 | 148 | | (_n2Low, _n2High) = TeddyBucketizer.GenerateBucketizedFingerprint(buckets, offset: 2); |
| | | 149 | | } |
| | 0 | 150 | | } |
| | | 151 | | |
| | | 152 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 153 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 154 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 155 | | protected int IndexOfAnyN2(ReadOnlySpan<char> span) |
| | | 156 | | { |
| | | 157 | | // The behavior of the rest of the function remains the same if Avx2 or Avx512BW aren't supported |
| | | 158 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | 0 | 159 | | if (Vector512.IsHardwareAccelerated && Avx512Vbmi.IsSupported && span.Length >= CharsPerIterationAvx512 + Ma |
| | | 160 | | { |
| | 0 | 161 | | return IndexOfAnyN2Avx512(span); |
| | | 162 | | } |
| | | 163 | | |
| | 0 | 164 | | if (Avx2.IsSupported && span.Length >= CharsPerIterationAvx2 + MatchStartOffsetN2) |
| | | 165 | | { |
| | 0 | 166 | | return IndexOfAnyN2Avx2(span); |
| | | 167 | | } |
| | | 168 | | #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 169 | | |
| | 0 | 170 | | return IndexOfAnyN2Vector128(span); |
| | | 171 | | } |
| | | 172 | | |
| | | 173 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 174 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 175 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 176 | | protected int IndexOfAnyN3(ReadOnlySpan<char> span) |
| | | 177 | | { |
| | | 178 | | // The behavior of the rest of the function remains the same if Avx2 or Avx512BW aren't supported |
| | | 179 | | #pragma warning disable IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | 0 | 180 | | if (Vector512.IsHardwareAccelerated && Avx512Vbmi.IsSupported && span.Length >= CharsPerIterationAvx512 + Ma |
| | | 181 | | { |
| | 0 | 182 | | return IndexOfAnyN3Avx512(span); |
| | | 183 | | } |
| | | 184 | | |
| | 0 | 185 | | if (Avx2.IsSupported && span.Length >= CharsPerIterationAvx2 + MatchStartOffsetN3) |
| | | 186 | | { |
| | 0 | 187 | | return IndexOfAnyN3Avx2(span); |
| | | 188 | | } |
| | | 189 | | #pragma warning restore IntrinsicsInSystemPrivateCoreLibAttributeNotSpecificEnough |
| | | 190 | | |
| | 0 | 191 | | return IndexOfAnyN3Vector128(span); |
| | | 192 | | } |
| | | 193 | | |
| | | 194 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 195 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 196 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 197 | | private int IndexOfAnyN2Vector128(ReadOnlySpan<char> span) |
| | | 198 | | { |
| | | 199 | | // See comments in 'IndexOfAnyN3Vector128' below. |
| | | 200 | | // This method is the same, but compares 2 starting chars instead of 3. |
| | 0 | 201 | | if (span.Length < CharsPerIterationVector128 + MatchStartOffsetN2) |
| | | 202 | | { |
| | 0 | 203 | | return ShortInputFallback(span); |
| | | 204 | | } |
| | | 205 | | |
| | 0 | 206 | | ref char searchSpace = ref MemoryMarshal.GetReference(span); |
| | 0 | 207 | | ref char lastSearchSpaceStart = ref Unsafe.Add(ref searchSpace, span.Length - CharsPerIterationVector128); |
| | | 208 | | |
| | 0 | 209 | | searchSpace = ref Unsafe.Add(ref searchSpace, MatchStartOffsetN2); |
| | | 210 | | |
| | 0 | 211 | | Vector128<byte> n0Low = _n0Low._lower._lower, n0High = _n0High._lower._lower; |
| | 0 | 212 | | Vector128<byte> n1Low = _n1Low._lower._lower, n1High = _n1High._lower._lower; |
| | 0 | 213 | | Vector128<byte> prev0 = Vector128<byte>.AllBitsSet; |
| | | 214 | | |
| | | 215 | | Loop: |
| | 0 | 216 | | ValidateReadPosition(span, ref searchSpace); |
| | 0 | 217 | | Vector128<byte> input = TStartCaseSensitivity.TransformInput(LoadAndPack16AsciiChars(ref searchSpace)); |
| | | 218 | | |
| | 0 | 219 | | (Vector128<byte> result, prev0) = ProcessInputN2(input, prev0, n0Low, n0High, n1Low, n1High); |
| | | 220 | | |
| | 0 | 221 | | if (result != Vector128<byte>.Zero) |
| | | 222 | | { |
| | | 223 | | goto CandidateFound; |
| | | 224 | | } |
| | | 225 | | |
| | | 226 | | ContinueLoop: |
| | 0 | 227 | | searchSpace = ref Unsafe.Add(ref searchSpace, CharsPerIterationVector128); |
| | | 228 | | |
| | 0 | 229 | | if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpaceStart)) |
| | | 230 | | { |
| | 0 | 231 | | if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpaceStart, CharsPerIterationVector128) |
| | | 232 | | { |
| | 0 | 233 | | return -1; |
| | | 234 | | } |
| | | 235 | | |
| | | 236 | | // We're switching which characters we will process in the next iteration. |
| | | 237 | | // prev0 no longer points to the characters just before the current input, so we must reset it. |
| | 0 | 238 | | prev0 = Vector128<byte>.AllBitsSet; |
| | 0 | 239 | | searchSpace = ref lastSearchSpaceStart; |
| | | 240 | | } |
| | 0 | 241 | | goto Loop; |
| | | 242 | | |
| | | 243 | | CandidateFound: |
| | 0 | 244 | | if (TryFindMatch(span, ref searchSpace, result, MatchStartOffsetN2, out int offset)) |
| | | 245 | | { |
| | 0 | 246 | | return offset; |
| | | 247 | | } |
| | | 248 | | goto ContinueLoop; |
| | | 249 | | } |
| | | 250 | | |
| | | 251 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 252 | | private int IndexOfAnyN2Avx2(ReadOnlySpan<char> span) |
| | | 253 | | { |
| | | 254 | | // See comments in 'IndexOfAnyN3Vector128' below. |
| | | 255 | | // This method is the same, but operates on 32 input characters at a time and compares 2 starting chars inst |
| | 0 | 256 | | Debug.Assert(span.Length >= CharsPerIterationAvx2 + MatchStartOffsetN2); |
| | | 257 | | |
| | 0 | 258 | | ref char searchSpace = ref MemoryMarshal.GetReference(span); |
| | 0 | 259 | | ref char lastSearchSpaceStart = ref Unsafe.Add(ref searchSpace, span.Length - CharsPerIterationAvx2); |
| | | 260 | | |
| | 0 | 261 | | searchSpace = ref Unsafe.Add(ref searchSpace, MatchStartOffsetN2); |
| | | 262 | | |
| | 0 | 263 | | Vector256<byte> n0Low = _n0Low._lower, n0High = _n0High._lower; |
| | 0 | 264 | | Vector256<byte> n1Low = _n1Low._lower, n1High = _n1High._lower; |
| | 0 | 265 | | Vector256<byte> prev0 = Vector256<byte>.AllBitsSet; |
| | | 266 | | |
| | | 267 | | Loop: |
| | 0 | 268 | | ValidateReadPosition(span, ref searchSpace); |
| | 0 | 269 | | Vector256<byte> input = TStartCaseSensitivity.TransformInput(LoadAndPack32AsciiChars(ref searchSpace)); |
| | | 270 | | |
| | 0 | 271 | | (Vector256<byte> result, prev0) = ProcessInputN2(input, prev0, n0Low, n0High, n1Low, n1High); |
| | | 272 | | |
| | 0 | 273 | | if (result != Vector256<byte>.Zero) |
| | | 274 | | { |
| | | 275 | | goto CandidateFound; |
| | | 276 | | } |
| | | 277 | | |
| | | 278 | | ContinueLoop: |
| | 0 | 279 | | searchSpace = ref Unsafe.Add(ref searchSpace, CharsPerIterationAvx2); |
| | | 280 | | |
| | 0 | 281 | | if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpaceStart)) |
| | | 282 | | { |
| | 0 | 283 | | if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpaceStart, CharsPerIterationAvx2))) |
| | | 284 | | { |
| | 0 | 285 | | return -1; |
| | | 286 | | } |
| | | 287 | | |
| | | 288 | | // We're switching which characters we will process in the next iteration. |
| | | 289 | | // prev0 no longer points to the characters just before the current input, so we must reset it. |
| | 0 | 290 | | prev0 = Vector256<byte>.AllBitsSet; |
| | 0 | 291 | | searchSpace = ref lastSearchSpaceStart; |
| | | 292 | | } |
| | 0 | 293 | | goto Loop; |
| | | 294 | | |
| | | 295 | | CandidateFound: |
| | 0 | 296 | | if (TryFindMatch(span, ref searchSpace, result, MatchStartOffsetN2, out int offset)) |
| | | 297 | | { |
| | 0 | 298 | | return offset; |
| | | 299 | | } |
| | | 300 | | goto ContinueLoop; |
| | | 301 | | } |
| | | 302 | | |
| | | 303 | | [CompExactlyDependsOn(typeof(Avx512Vbmi))] |
| | | 304 | | private int IndexOfAnyN2Avx512(ReadOnlySpan<char> span) |
| | | 305 | | { |
| | | 306 | | // See comments in 'IndexOfAnyN3Vector128' below. |
| | | 307 | | // This method is the same, but operates on 64 input characters at a time and compares 2 starting chars inst |
| | 0 | 308 | | Debug.Assert(span.Length >= CharsPerIterationAvx512 + MatchStartOffsetN2); |
| | | 309 | | |
| | 0 | 310 | | ref char searchSpace = ref MemoryMarshal.GetReference(span); |
| | 0 | 311 | | ref char lastSearchSpaceStart = ref Unsafe.Add(ref searchSpace, span.Length - CharsPerIterationAvx512); |
| | | 312 | | |
| | 0 | 313 | | searchSpace = ref Unsafe.Add(ref searchSpace, MatchStartOffsetN2); |
| | | 314 | | |
| | 0 | 315 | | Vector512<byte> n0Low = _n0Low, n0High = _n0High; |
| | 0 | 316 | | Vector512<byte> n1Low = _n1Low, n1High = _n1High; |
| | 0 | 317 | | Vector512<byte> prev0 = Vector512<byte>.AllBitsSet; |
| | | 318 | | |
| | | 319 | | Loop: |
| | 0 | 320 | | ValidateReadPosition(span, ref searchSpace); |
| | 0 | 321 | | Vector512<byte> input = TStartCaseSensitivity.TransformInput(LoadAndPack64AsciiChars(ref searchSpace)); |
| | | 322 | | |
| | 0 | 323 | | (Vector512<byte> result, prev0) = ProcessInputN2(input, prev0, n0Low, n0High, n1Low, n1High); |
| | | 324 | | |
| | 0 | 325 | | if (result != Vector512<byte>.Zero) |
| | | 326 | | { |
| | | 327 | | goto CandidateFound; |
| | | 328 | | } |
| | | 329 | | |
| | | 330 | | ContinueLoop: |
| | 0 | 331 | | searchSpace = ref Unsafe.Add(ref searchSpace, CharsPerIterationAvx512); |
| | | 332 | | |
| | 0 | 333 | | if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpaceStart)) |
| | | 334 | | { |
| | 0 | 335 | | if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpaceStart, CharsPerIterationAvx512))) |
| | | 336 | | { |
| | 0 | 337 | | return -1; |
| | | 338 | | } |
| | | 339 | | |
| | | 340 | | // We're switching which characters we will process in the next iteration. |
| | | 341 | | // prev0 no longer points to the characters just before the current input, so we must reset it. |
| | 0 | 342 | | prev0 = Vector512<byte>.AllBitsSet; |
| | 0 | 343 | | searchSpace = ref lastSearchSpaceStart; |
| | | 344 | | } |
| | 0 | 345 | | goto Loop; |
| | | 346 | | |
| | | 347 | | CandidateFound: |
| | 0 | 348 | | if (TryFindMatch(span, ref searchSpace, result, MatchStartOffsetN2, out int offset)) |
| | | 349 | | { |
| | 0 | 350 | | return offset; |
| | | 351 | | } |
| | | 352 | | goto ContinueLoop; |
| | | 353 | | } |
| | | 354 | | |
| | | 355 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 356 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 357 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 358 | | private int IndexOfAnyN3Vector128(ReadOnlySpan<char> span) |
| | | 359 | | { |
| | | 360 | | // We can't process inputs shorter than 18 characters in a vectorized manner here. |
| | 0 | 361 | | if (span.Length < CharsPerIterationVector128 + MatchStartOffsetN3) |
| | | 362 | | { |
| | 0 | 363 | | return ShortInputFallback(span); |
| | | 364 | | } |
| | | 365 | | |
| | 0 | 366 | | ref char searchSpace = ref MemoryMarshal.GetReference(span); |
| | 0 | 367 | | ref char lastSearchSpaceStart = ref Unsafe.Add(ref searchSpace, span.Length - CharsPerIterationVector128); |
| | | 368 | | |
| | 0 | 369 | | searchSpace = ref Unsafe.Add(ref searchSpace, MatchStartOffsetN3); |
| | | 370 | | |
| | | 371 | | // All the input bitmaps are Vector128<byte>, duplicated 4 times up to Vector512<byte>. |
| | | 372 | | // They are stored as Vector512 to lower the overhead of routines that do load the full Vector512<byte>. |
| | | 373 | | // When using the Vector128 routine, we just load the first of those duplicates (._lower._lower). |
| | 0 | 374 | | Vector128<byte> n0Low = _n0Low._lower._lower, n0High = _n0High._lower._lower; |
| | 0 | 375 | | Vector128<byte> n1Low = _n1Low._lower._lower, n1High = _n1High._lower._lower; |
| | 0 | 376 | | Vector128<byte> n2Low = _n2Low._lower._lower, n2High = _n2High._lower._lower; |
| | | 377 | | |
| | | 378 | | // As matching is offset by 2 positions (MatchStartOffsetN3), we must remember the result of the previous lo |
| | | 379 | | // See the full description of TeddyHelper.ProcessInputN3 for more details about why these exist. |
| | | 380 | | // When doing the first loop iteration, there is no previous iteration, so we have to assume that the input |
| | | 381 | | // for those positions. This makes it more likely to hit a false-positive at the very beginning, but TryFind |
| | 0 | 382 | | Vector128<byte> prev0 = Vector128<byte>.AllBitsSet; |
| | 0 | 383 | | Vector128<byte> prev1 = Vector128<byte>.AllBitsSet; |
| | | 384 | | |
| | | 385 | | Loop: |
| | | 386 | | // Load the input characters and normalize them to their uppercase variant if we're ignoring casing. |
| | | 387 | | // These characters may not be ASCII, but we know that the starting 3 characters of each value are. |
| | 0 | 388 | | ValidateReadPosition(span, ref searchSpace); |
| | 0 | 389 | | Vector128<byte> input = TStartCaseSensitivity.TransformInput(LoadAndPack16AsciiChars(ref searchSpace)); |
| | | 390 | | |
| | | 391 | | // Find which buckets contain potential matches for each input position. |
| | | 392 | | // For a bucket to be marked as a potential match, its fingerprint must match for all 3 starting characters |
| | 0 | 393 | | (Vector128<byte> result, prev0, prev1) = ProcessInputN3(input, prev0, prev1, n0Low, n0High, n1Low, n1High, n |
| | | 394 | | |
| | 0 | 395 | | if (result != Vector128<byte>.Zero) |
| | | 396 | | { |
| | | 397 | | goto CandidateFound; |
| | | 398 | | } |
| | | 399 | | |
| | | 400 | | ContinueLoop: |
| | | 401 | | // We haven't found a match. Update the input position and check if we've reached the end. |
| | 0 | 402 | | searchSpace = ref Unsafe.Add(ref searchSpace, CharsPerIterationVector128); |
| | | 403 | | |
| | 0 | 404 | | if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpaceStart)) |
| | | 405 | | { |
| | 0 | 406 | | if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpaceStart, CharsPerIterationVector128) |
| | | 407 | | { |
| | 0 | 408 | | return -1; |
| | | 409 | | } |
| | | 410 | | |
| | | 411 | | // We're switching which characters we will process in the next iteration. |
| | | 412 | | // prev0 and prev1 no longer point to the characters just before the current input, so we must reset the |
| | | 413 | | // Just like with the first iteration, we must assume that these positions did match (AllBitsSet). |
| | 0 | 414 | | prev0 = Vector128<byte>.AllBitsSet; |
| | 0 | 415 | | prev1 = Vector128<byte>.AllBitsSet; |
| | 0 | 416 | | searchSpace = ref lastSearchSpaceStart; |
| | | 417 | | } |
| | 0 | 418 | | goto Loop; |
| | | 419 | | |
| | | 420 | | CandidateFound: |
| | | 421 | | // We found potential matches, but they may be false-positives, so we must verify each one. |
| | 0 | 422 | | if (TryFindMatch(span, ref searchSpace, result, MatchStartOffsetN3, out int offset)) |
| | | 423 | | { |
| | 0 | 424 | | return offset; |
| | | 425 | | } |
| | | 426 | | goto ContinueLoop; |
| | | 427 | | } |
| | | 428 | | |
| | | 429 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 430 | | private int IndexOfAnyN3Avx2(ReadOnlySpan<char> span) |
| | | 431 | | { |
| | | 432 | | // See comments in 'IndexOfAnyN3Vector128' above. |
| | | 433 | | // This method is the same, but operates on 32 input characters at a time. |
| | 0 | 434 | | Debug.Assert(span.Length >= CharsPerIterationAvx2 + MatchStartOffsetN3); |
| | | 435 | | |
| | 0 | 436 | | ref char searchSpace = ref MemoryMarshal.GetReference(span); |
| | 0 | 437 | | ref char lastSearchSpaceStart = ref Unsafe.Add(ref searchSpace, span.Length - CharsPerIterationAvx2); |
| | | 438 | | |
| | 0 | 439 | | searchSpace = ref Unsafe.Add(ref searchSpace, MatchStartOffsetN3); |
| | | 440 | | |
| | 0 | 441 | | Vector256<byte> n0Low = _n0Low._lower, n0High = _n0High._lower; |
| | 0 | 442 | | Vector256<byte> n1Low = _n1Low._lower, n1High = _n1High._lower; |
| | 0 | 443 | | Vector256<byte> n2Low = _n2Low._lower, n2High = _n2High._lower; |
| | 0 | 444 | | Vector256<byte> prev0 = Vector256<byte>.AllBitsSet; |
| | 0 | 445 | | Vector256<byte> prev1 = Vector256<byte>.AllBitsSet; |
| | | 446 | | |
| | | 447 | | Loop: |
| | 0 | 448 | | ValidateReadPosition(span, ref searchSpace); |
| | 0 | 449 | | Vector256<byte> input = TStartCaseSensitivity.TransformInput(LoadAndPack32AsciiChars(ref searchSpace)); |
| | | 450 | | |
| | 0 | 451 | | (Vector256<byte> result, prev0, prev1) = ProcessInputN3(input, prev0, prev1, n0Low, n0High, n1Low, n1High, n |
| | | 452 | | |
| | 0 | 453 | | if (result != Vector256<byte>.Zero) |
| | | 454 | | { |
| | | 455 | | goto CandidateFound; |
| | | 456 | | } |
| | | 457 | | |
| | | 458 | | ContinueLoop: |
| | 0 | 459 | | searchSpace = ref Unsafe.Add(ref searchSpace, CharsPerIterationAvx2); |
| | | 460 | | |
| | 0 | 461 | | if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpaceStart)) |
| | | 462 | | { |
| | 0 | 463 | | if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpaceStart, CharsPerIterationAvx2))) |
| | | 464 | | { |
| | 0 | 465 | | return -1; |
| | | 466 | | } |
| | | 467 | | |
| | | 468 | | // We're switching which characters we will process in the next iteration. |
| | | 469 | | // prev0 and prev1 no longer point to the characters just before the current input, so we must reset the |
| | 0 | 470 | | prev0 = Vector256<byte>.AllBitsSet; |
| | 0 | 471 | | prev1 = Vector256<byte>.AllBitsSet; |
| | 0 | 472 | | searchSpace = ref lastSearchSpaceStart; |
| | | 473 | | } |
| | 0 | 474 | | goto Loop; |
| | | 475 | | |
| | | 476 | | CandidateFound: |
| | 0 | 477 | | if (TryFindMatch(span, ref searchSpace, result, MatchStartOffsetN3, out int offset)) |
| | | 478 | | { |
| | 0 | 479 | | return offset; |
| | | 480 | | } |
| | | 481 | | goto ContinueLoop; |
| | | 482 | | } |
| | | 483 | | |
| | | 484 | | [CompExactlyDependsOn(typeof(Avx512Vbmi))] |
| | | 485 | | private int IndexOfAnyN3Avx512(ReadOnlySpan<char> span) |
| | | 486 | | { |
| | | 487 | | // See comments in 'IndexOfAnyN3Vector128' above. |
| | | 488 | | // This method is the same, but operates on 64 input characters at a time. |
| | 0 | 489 | | Debug.Assert(span.Length >= CharsPerIterationAvx512 + MatchStartOffsetN3); |
| | | 490 | | |
| | 0 | 491 | | ref char searchSpace = ref MemoryMarshal.GetReference(span); |
| | 0 | 492 | | ref char lastSearchSpaceStart = ref Unsafe.Add(ref searchSpace, span.Length - CharsPerIterationAvx512); |
| | | 493 | | |
| | 0 | 494 | | searchSpace = ref Unsafe.Add(ref searchSpace, MatchStartOffsetN3); |
| | | 495 | | |
| | 0 | 496 | | Vector512<byte> n0Low = _n0Low, n0High = _n0High; |
| | 0 | 497 | | Vector512<byte> n1Low = _n1Low, n1High = _n1High; |
| | 0 | 498 | | Vector512<byte> n2Low = _n2Low, n2High = _n2High; |
| | 0 | 499 | | Vector512<byte> prev0 = Vector512<byte>.AllBitsSet; |
| | 0 | 500 | | Vector512<byte> prev1 = Vector512<byte>.AllBitsSet; |
| | | 501 | | |
| | | 502 | | Loop: |
| | 0 | 503 | | ValidateReadPosition(span, ref searchSpace); |
| | 0 | 504 | | Vector512<byte> input = TStartCaseSensitivity.TransformInput(LoadAndPack64AsciiChars(ref searchSpace)); |
| | | 505 | | |
| | 0 | 506 | | (Vector512<byte> result, prev0, prev1) = ProcessInputN3(input, prev0, prev1, n0Low, n0High, n1Low, n1High, n |
| | | 507 | | |
| | 0 | 508 | | if (result != Vector512<byte>.Zero) |
| | | 509 | | { |
| | | 510 | | goto CandidateFound; |
| | | 511 | | } |
| | | 512 | | |
| | | 513 | | ContinueLoop: |
| | 0 | 514 | | searchSpace = ref Unsafe.Add(ref searchSpace, CharsPerIterationAvx512); |
| | | 515 | | |
| | 0 | 516 | | if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpaceStart)) |
| | | 517 | | { |
| | 0 | 518 | | if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpaceStart, CharsPerIterationAvx512))) |
| | | 519 | | { |
| | 0 | 520 | | return -1; |
| | | 521 | | } |
| | | 522 | | |
| | | 523 | | // We're switching which characters we will process in the next iteration. |
| | | 524 | | // prev0 and prev1 no longer point to the characters just before the current input, so we must reset the |
| | 0 | 525 | | prev0 = Vector512<byte>.AllBitsSet; |
| | 0 | 526 | | prev1 = Vector512<byte>.AllBitsSet; |
| | 0 | 527 | | searchSpace = ref lastSearchSpaceStart; |
| | | 528 | | } |
| | 0 | 529 | | goto Loop; |
| | | 530 | | |
| | | 531 | | CandidateFound: |
| | 0 | 532 | | if (TryFindMatch(span, ref searchSpace, result, MatchStartOffsetN3, out int offset)) |
| | | 533 | | { |
| | 0 | 534 | | return offset; |
| | | 535 | | } |
| | | 536 | | goto ContinueLoop; |
| | | 537 | | } |
| | | 538 | | |
| | | 539 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 540 | | private bool TryFindMatch(ReadOnlySpan<char> span, ref char searchSpace, Vector128<byte> result, int matchStartO |
| | | 541 | | { |
| | | 542 | | // 'resultMask' encodes the input positions where at least one bucket may contain a match. |
| | | 543 | | // These positions are offset by 'matchStartOffset' places. |
| | 0 | 544 | | uint resultMask = (~Vector128.Equals(result, Vector128<byte>.Zero)).ExtractMostSignificantBits(); |
| | | 545 | | |
| | | 546 | | do |
| | | 547 | | { |
| | 0 | 548 | | int matchOffset = BitOperations.TrailingZeroCount(resultMask); |
| | | 549 | | |
| | | 550 | | // Calculate where in the input span this potential match begins. |
| | 0 | 551 | | ref char matchRef = ref Unsafe.Add(ref searchSpace, matchOffset - matchStartOffset); |
| | 0 | 552 | | offsetFromStart = (int)((nuint)Unsafe.ByteOffset(ref MemoryMarshal.GetReference(span), ref matchRef) / 2 |
| | 0 | 553 | | int lengthRemaining = span.Length - offsetFromStart; |
| | | 554 | | |
| | 0 | 555 | | ValidateReadPosition(span, ref matchRef, lengthRemaining); |
| | | 556 | | |
| | | 557 | | // 'candidateMask' encodes which buckets contain potential matches, starting at 'matchRef'. |
| | 0 | 558 | | uint candidateMask = result.GetElementUnsafe(matchOffset); |
| | | 559 | | |
| | | 560 | | do |
| | | 561 | | { |
| | | 562 | | // Verify each bucket to see if we've found a match. |
| | 0 | 563 | | int candidateOffset = BitOperations.TrailingZeroCount(candidateMask); |
| | | 564 | | |
| | 0 | 565 | | object? bucket = _buckets[candidateOffset]; |
| | 0 | 566 | | Debug.Assert(bucket is not null); |
| | | 567 | | |
| | 0 | 568 | | if (TBucketized.Value |
| | 0 | 569 | | ? StartsWith<TCaseSensitivity>(ref matchRef, lengthRemaining, Unsafe.As<string[]>(bucket)) |
| | 0 | 570 | | : StartsWith<TCaseSensitivity>(ref matchRef, lengthRemaining, Unsafe.As<string>(bucket))) |
| | | 571 | | { |
| | 0 | 572 | | return true; |
| | | 573 | | } |
| | | 574 | | |
| | 0 | 575 | | candidateMask = BitOperations.ResetLowestSetBit(candidateMask); |
| | | 576 | | } |
| | 0 | 577 | | while (candidateMask != 0); |
| | | 578 | | |
| | 0 | 579 | | resultMask = BitOperations.ResetLowestSetBit(resultMask); |
| | | 580 | | } |
| | 0 | 581 | | while (resultMask != 0); |
| | | 582 | | |
| | 0 | 583 | | offsetFromStart = 0; |
| | 0 | 584 | | return false; |
| | | 585 | | } |
| | | 586 | | |
| | | 587 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 588 | | private bool TryFindMatch(ReadOnlySpan<char> span, ref char searchSpace, Vector256<byte> result, int matchStartO |
| | | 589 | | { |
| | | 590 | | // See comments in 'TryFindMatch' for Vector128<byte> above. |
| | | 591 | | // This method is the same, but checks the potential matches for 32 input positions. |
| | 0 | 592 | | uint resultMask = (~Vector256.Equals(result, Vector256<byte>.Zero)).ExtractMostSignificantBits(); |
| | | 593 | | |
| | | 594 | | do |
| | | 595 | | { |
| | 0 | 596 | | int matchOffset = BitOperations.TrailingZeroCount(resultMask); |
| | | 597 | | |
| | 0 | 598 | | ref char matchRef = ref Unsafe.Add(ref searchSpace, matchOffset - matchStartOffset); |
| | 0 | 599 | | offsetFromStart = (int)((nuint)Unsafe.ByteOffset(ref MemoryMarshal.GetReference(span), ref matchRef) / 2 |
| | 0 | 600 | | int lengthRemaining = span.Length - offsetFromStart; |
| | | 601 | | |
| | 0 | 602 | | ValidateReadPosition(span, ref matchRef, lengthRemaining); |
| | | 603 | | |
| | 0 | 604 | | uint candidateMask = result.GetElementUnsafe(matchOffset); |
| | | 605 | | |
| | | 606 | | do |
| | | 607 | | { |
| | 0 | 608 | | int candidateOffset = BitOperations.TrailingZeroCount(candidateMask); |
| | | 609 | | |
| | 0 | 610 | | object? bucket = _buckets[candidateOffset]; |
| | 0 | 611 | | Debug.Assert(bucket is not null); |
| | | 612 | | |
| | 0 | 613 | | if (TBucketized.Value |
| | 0 | 614 | | ? StartsWith<TCaseSensitivity>(ref matchRef, lengthRemaining, Unsafe.As<string[]>(bucket)) |
| | 0 | 615 | | : StartsWith<TCaseSensitivity>(ref matchRef, lengthRemaining, Unsafe.As<string>(bucket))) |
| | | 616 | | { |
| | 0 | 617 | | return true; |
| | | 618 | | } |
| | | 619 | | |
| | 0 | 620 | | candidateMask = BitOperations.ResetLowestSetBit(candidateMask); |
| | | 621 | | } |
| | 0 | 622 | | while (candidateMask != 0); |
| | | 623 | | |
| | 0 | 624 | | resultMask = BitOperations.ResetLowestSetBit(resultMask); |
| | | 625 | | } |
| | 0 | 626 | | while (resultMask != 0); |
| | | 627 | | |
| | 0 | 628 | | offsetFromStart = 0; |
| | 0 | 629 | | return false; |
| | | 630 | | } |
| | | 631 | | |
| | | 632 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 633 | | private bool TryFindMatch(ReadOnlySpan<char> span, ref char searchSpace, Vector512<byte> result, int matchStartO |
| | | 634 | | { |
| | | 635 | | // See comments in 'TryFindMatch' for Vector128<byte> above. |
| | | 636 | | // This method is the same, but checks the potential matches for 64 input positions. |
| | 0 | 637 | | ulong resultMask = (~Vector512.Equals(result, Vector512<byte>.Zero)).ExtractMostSignificantBits(); |
| | | 638 | | |
| | | 639 | | do |
| | | 640 | | { |
| | 0 | 641 | | int matchOffset = BitOperations.TrailingZeroCount(resultMask); |
| | | 642 | | |
| | 0 | 643 | | ref char matchRef = ref Unsafe.Add(ref searchSpace, matchOffset - matchStartOffset); |
| | 0 | 644 | | offsetFromStart = (int)((nuint)Unsafe.ByteOffset(ref MemoryMarshal.GetReference(span), ref matchRef) / 2 |
| | 0 | 645 | | int lengthRemaining = span.Length - offsetFromStart; |
| | | 646 | | |
| | 0 | 647 | | ValidateReadPosition(span, ref matchRef, lengthRemaining); |
| | | 648 | | |
| | 0 | 649 | | uint candidateMask = result.GetElementUnsafe(matchOffset); |
| | | 650 | | |
| | | 651 | | do |
| | | 652 | | { |
| | 0 | 653 | | int candidateOffset = BitOperations.TrailingZeroCount(candidateMask); |
| | | 654 | | |
| | 0 | 655 | | object? bucket = _buckets[candidateOffset]; |
| | 0 | 656 | | Debug.Assert(bucket is not null); |
| | | 657 | | |
| | 0 | 658 | | if (TBucketized.Value |
| | 0 | 659 | | ? StartsWith<TCaseSensitivity>(ref matchRef, lengthRemaining, Unsafe.As<string[]>(bucket)) |
| | 0 | 660 | | : StartsWith<TCaseSensitivity>(ref matchRef, lengthRemaining, Unsafe.As<string>(bucket))) |
| | | 661 | | { |
| | 0 | 662 | | return true; |
| | | 663 | | } |
| | | 664 | | |
| | 0 | 665 | | candidateMask = BitOperations.ResetLowestSetBit(candidateMask); |
| | | 666 | | } |
| | 0 | 667 | | while (candidateMask != 0); |
| | | 668 | | |
| | 0 | 669 | | resultMask = BitOperations.ResetLowestSetBit(resultMask); |
| | | 670 | | } |
| | 0 | 671 | | while (resultMask != 0); |
| | | 672 | | |
| | 0 | 673 | | offsetFromStart = 0; |
| | 0 | 674 | | return false; |
| | | 675 | | } |
| | | 676 | | } |
| | | 677 | | } |
| | | 678 | | |