< Summary

Line coverage
0%
Covered lines: 0
Uncovered lines: 154
Coverable lines: 154
Total lines: 418
Line coverage: 0%
Branch coverage
0%
Covered branches: 0
Total branches: 92
Branch coverage: 0%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity NPath complexity Sequence coverage
.ctor(...)0%10100%
IndexOfAnyMultiString(...)100%110%
IndexOf(...)0%50500%
GetComparisonResult(...)0%220%
GetComparisonResult(...)0%220%
GetComparisonResult(...)0%220%
TryMatch(...)0%660%
TryMatch(...)0%660%
ContainsCore(...)0%440%
GetValues()0%220%
LoadPacked128(...)0%220%
LoadPacked256(...)100%110%
LoadPacked512(...)100%110%

File(s)

https://raw.githubusercontent.com/dotnet/runtime/811a7eabb75c42db53440e8ba3f60c07511cfd1f/src/libraries/System.Private.CoreLib/src/System/SearchValues/Strings/SingleStringSearchValuesPackedThreeChars.cs

#LineLine coverage
 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
 4using System.Collections.Generic;
 5using System.Diagnostics;
 6using System.Numerics;
 7using System.Runtime.CompilerServices;
 8using System.Runtime.InteropServices;
 9using System.Runtime.Intrinsics;
 10using System.Runtime.Intrinsics.Arm;
 11using System.Runtime.Intrinsics.X86;
 12using static System.Buffers.StringSearchValuesHelper;
 13
 14namespace System.Buffers
 15{
 16    /// <summary>
 17    /// Same as <see cref="SingleStringSearchValuesThreeChars{TValueLength, TCaseSensitivity}"/>, but using packed compa
 18    /// </summary>
 19    internal sealed class SingleStringSearchValuesPackedThreeChars<TValueLength, TCaseSensitivity> : StringSearchValuesB
 20        where TValueLength : struct, IValueLength
 21        where TCaseSensitivity : struct, ICaseSensitivity
 22    {
 23        private const byte CaseConversionMask = unchecked((byte)~0x20);
 24
 25        private readonly SingleValueState _valueState;
 26        private readonly nint _minusValueTailLength;
 27        private readonly nuint _ch2ByteOffset;
 28        private readonly nuint _ch3ByteOffset;
 29        private readonly byte _ch1;
 30        private readonly byte _ch2;
 31        private readonly byte _ch3;
 32
 033        private static bool IgnoreCase => typeof(TCaseSensitivity) != typeof(CaseSensitive);
 34
 35        // If the value is short (ValueLengthLessThan4 => 2 or 3 characters), the anchors already represent the whole va
 36        // With case-sensitive comparisons, we've therefore already confirmed the match, so we can skip doing so here.
 37        // With case-insensitive comparisons, we applied a mask to the input, so while the anchors likely matched, we ca
 38        // If the value is composed of only ASCII letters, masking the input can't produce false positives, so we can al
 39        // We only do this when running on X86 and not ARM64, as the latter uses UnzipEven when packing inputs, which ma
 40        // We use that instead of ExtractNarrowingSaturate because it allows for higher searching throughput.
 41        private static bool CanSkipAnchorMatchVerification
 42        {
 43            [MethodImpl(MethodImplOptions.AggressiveInlining)]
 44            get =>
 045                Sse2.IsSupported &&
 046                typeof(TValueLength) == typeof(ValueLengthLessThan4) &&
 047                (typeof(TCaseSensitivity) == typeof(CaseSensitive) || typeof(TCaseSensitivity) == typeof(CaseInsensitive
 48        }
 49
 050        public SingleStringSearchValuesPackedThreeChars(HashSet<string>? uniqueValues, string value, int ch2Offset, int 
 51        {
 052            Debug.Assert(Sse2.IsSupported || AdvSimd.Arm64.IsSupported);
 53
 54            // We could have more than one entry in 'uniqueValues' if this value is an exact prefix of all the others.
 055            Debug.Assert(value.Length > 1);
 056            Debug.Assert(ch3Offset == 0 || ch3Offset > ch2Offset);
 057            Debug.Assert(value[0] <= byte.MaxValue && value[ch2Offset] <= byte.MaxValue && value[ch3Offset] <= byte.MaxV
 58
 059            _valueState = new SingleValueState(value, IgnoreCase);
 060            _minusValueTailLength = -(value.Length - 1);
 61
 062            _ch1 = (byte)value[0];
 063            _ch2 = (byte)value[ch2Offset];
 064            _ch3 = (byte)value[ch3Offset];
 65
 066            if (IgnoreCase)
 67            {
 068                _ch1 &= CaseConversionMask;
 069                _ch2 &= CaseConversionMask;
 070                _ch3 &= CaseConversionMask;
 71            }
 72
 073            _ch2ByteOffset = (nuint)ch2Offset * 2;
 074            _ch3ByteOffset = (nuint)ch3Offset * 2;
 075        }
 76
 77        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 78        internal override int IndexOfAnyMultiString(ReadOnlySpan<char> span) =>
 079            IndexOf(ref MemoryMarshal.GetReference(span), span.Length);
 80
 81        private int IndexOf(ref char searchSpace, int searchSpaceLength)
 82        {
 083            ref char searchSpaceStart = ref searchSpace;
 84
 085            nint searchSpaceMinusValueTailLength = searchSpaceLength + _minusValueTailLength;
 86
 087            nuint ch2ByteOffset = _ch2ByteOffset;
 088            nuint ch3ByteOffset = _ch3ByteOffset;
 89
 090            if (Vector512.IsHardwareAccelerated && Avx512BW.IsSupported && searchSpaceMinusValueTailLength - Vector512<b
 91            {
 092                Vector512<byte> ch1 = Vector512.Create(_ch1);
 093                Vector512<byte> ch2 = Vector512.Create(_ch2);
 094                Vector512<byte> ch3 = Vector512.Create(_ch3);
 95
 096                ref char lastSearchSpace = ref Unsafe.Add(ref searchSpace, searchSpaceMinusValueTailLength - Vector512<b
 97
 98                while (true)
 99                {
 0100                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector512<byte>.Count
 0101                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector512<byte>.Count
 0102                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector512<byte>.Count
 103
 104                    // Find which starting positions likely contain a match (likely match all 3 anchor characters).
 0105                    Vector512<byte> result = GetComparisonResult(ref searchSpace, ch2ByteOffset, ch3ByteOffset, ch1, ch2
 106
 0107                    if (result != Vector512<byte>.Zero)
 108                    {
 109                        goto CandidateFound;
 110                    }
 111
 112                LoopFooter:
 113                    // We haven't found a match. Update the input position and check if we've reached the end.
 0114                    searchSpace = ref Unsafe.Add(ref searchSpace, Vector512<byte>.Count);
 115
 0116                    if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpace))
 117                    {
 0118                        if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpace, Vector512<byte>.Count)))
 119                        {
 0120                            return -1;
 121                        }
 122
 123                        // We have fewer than 64 characters remaining. Adjust the input position such that we will do on
 0124                        searchSpace = ref lastSearchSpace;
 125                    }
 126
 0127                    continue;
 128
 129                CandidateFound:
 130                    // We found potential matches, but they may be false-positives, so we must verify each one.
 0131                    if (TryMatch(ref searchSpaceStart, searchSpaceLength, ref searchSpace, PackedSpanHelpers.FixUpPacked
 132                    {
 0133                        return offset;
 134                    }
 135                    goto LoopFooter;
 136                }
 137            }
 0138            else if (Vector256.IsHardwareAccelerated && Avx2.IsSupported && searchSpaceMinusValueTailLength - Vector256<
 139            {
 0140                Vector256<byte> ch1 = Vector256.Create(_ch1);
 0141                Vector256<byte> ch2 = Vector256.Create(_ch2);
 0142                Vector256<byte> ch3 = Vector256.Create(_ch3);
 143
 0144                ref char lastSearchSpace = ref Unsafe.Add(ref searchSpace, searchSpaceMinusValueTailLength - Vector256<b
 145
 146                while (true)
 147                {
 0148                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector256<byte>.Count
 0149                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector256<byte>.Count
 0150                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector256<byte>.Count
 151
 152                    // Find which starting positions likely contain a match (likely match all 3 anchor characters).
 0153                    Vector256<byte> result = GetComparisonResult(ref searchSpace, ch2ByteOffset, ch3ByteOffset, ch1, ch2
 154
 0155                    if (result != Vector256<byte>.Zero)
 156                    {
 157                        goto CandidateFound;
 158                    }
 159
 160                LoopFooter:
 0161                    searchSpace = ref Unsafe.Add(ref searchSpace, Vector256<byte>.Count);
 162
 0163                    if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpace))
 164                    {
 0165                        if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpace, Vector256<byte>.Count)))
 166                        {
 0167                            return -1;
 168                        }
 169
 170                        // We have fewer than 32 characters remaining. Adjust the input position such that we will do on
 0171                        searchSpace = ref lastSearchSpace;
 172                    }
 173
 0174                    continue;
 175
 176                CandidateFound:
 177                    // We found potential matches, but they may be false-positives, so we must verify each one.
 0178                    if (TryMatch(ref searchSpaceStart, searchSpaceLength, ref searchSpace, PackedSpanHelpers.FixUpPacked
 179                    {
 0180                        return offset;
 181                    }
 182                    goto LoopFooter;
 183                }
 184            }
 0185            else if ((Sse2.IsSupported || AdvSimd.Arm64.IsSupported) && searchSpaceMinusValueTailLength - Vector128<byte
 186            {
 0187                Vector128<byte> ch1 = Vector128.Create(_ch1);
 0188                Vector128<byte> ch2 = Vector128.Create(_ch2);
 0189                Vector128<byte> ch3 = Vector128.Create(_ch3);
 190
 0191                ref char lastSearchSpace = ref Unsafe.Add(ref searchSpace, searchSpaceMinusValueTailLength - Vector128<b
 192
 193                while (true)
 194                {
 0195                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector128<byte>.Count
 0196                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector128<byte>.Count
 0197                    ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref searchSpace, Vector128<byte>.Count
 198
 199                    // Find which starting positions likely contain a match (likely match all 3 anchor characters).
 0200                    Vector128<byte> result = GetComparisonResult(ref searchSpace, ch2ByteOffset, ch3ByteOffset, ch1, ch2
 201
 0202                    if (result != Vector128<byte>.Zero)
 203                    {
 204                        goto CandidateFound;
 205                    }
 206
 207                LoopFooter:
 0208                    searchSpace = ref Unsafe.Add(ref searchSpace, Vector128<byte>.Count);
 209
 0210                    if (Unsafe.IsAddressGreaterThan(ref searchSpace, ref lastSearchSpace))
 211                    {
 0212                        if (Unsafe.AreSame(ref searchSpace, ref Unsafe.Add(ref lastSearchSpace, Vector128<byte>.Count)))
 213                        {
 0214                            return -1;
 215                        }
 216
 217                        // We have fewer than 16 characters remaining. Adjust the input position such that we will do on
 0218                        searchSpace = ref lastSearchSpace;
 219                    }
 220
 0221                    continue;
 222
 223                CandidateFound:
 224                    // We found potential matches, but they may be false-positives, so we must verify each one.
 0225                    if (TryMatch(ref searchSpaceStart, searchSpaceLength, ref searchSpace, result.ExtractMostSignificant
 226                    {
 0227                        return offset;
 228                    }
 229                    goto LoopFooter;
 230                }
 231            }
 232
 0233            char valueHead = _valueState.Value.GetRawStringData();
 234
 0235            for (nint i = 0; i < searchSpaceMinusValueTailLength; i++)
 236            {
 0237                ref char cur = ref Unsafe.Add(ref searchSpace, i);
 238
 239                // CaseInsensitiveUnicode doesn't support single-character transformations, so we skip checking the firs
 0240                if ((typeof(TCaseSensitivity) == typeof(CaseInsensitiveUnicode) || TCaseSensitivity.TransformInput(cur) 
 0241                    TCaseSensitivity.Equals<TValueLength>(ref cur, in _valueState))
 242                {
 0243                    return (int)i;
 244                }
 245            }
 246
 0247            return -1;
 248        }
 249
 250        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 251        [CompExactlyDependsOn(typeof(Sse2))]
 252        [CompExactlyDependsOn(typeof(AdvSimd.Arm64))]
 253        private static Vector128<byte> GetComparisonResult(ref char searchSpace, nuint ch2ByteOffset, nuint ch3ByteOffse
 254        {
 255            // Load 3 vectors from the input.
 256            // One from the current search space, the other two at an offset based on the distance of those characters f
 0257            if (typeof(TCaseSensitivity) == typeof(CaseSensitive))
 258            {
 0259                Vector128<byte> cmpCh1 = Vector128.Equals(ch1, LoadPacked128(ref searchSpace, 0));
 0260                Vector128<byte> cmpCh2 = Vector128.Equals(ch2, LoadPacked128(ref searchSpace, ch2ByteOffset));
 0261                Vector128<byte> cmpCh3 = Vector128.Equals(ch3, LoadPacked128(ref searchSpace, ch3ByteOffset));
 262                // AND all 3 together to get a mask of possible match positions that match in at least 3 places.
 0263                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 264            }
 265            else
 266            {
 267                // For each, AND the value with ~0x20 so that letters are uppercased.
 268                // For characters that aren't ASCII letters, this may produce wrong results, but only false-positives.
 269                // We will take care of those in the verification step if the other characters also indicate a possible 
 0270                Vector128<byte> caseConversion = Vector128.Create(CaseConversionMask);
 271
 0272                Vector128<byte> cmpCh1 = Vector128.Equals(ch1, LoadPacked128(ref searchSpace, 0) & caseConversion);
 0273                Vector128<byte> cmpCh2 = Vector128.Equals(ch2, LoadPacked128(ref searchSpace, ch2ByteOffset) & caseConve
 0274                Vector128<byte> cmpCh3 = Vector128.Equals(ch3, LoadPacked128(ref searchSpace, ch3ByteOffset) & caseConve
 275                // AND all 3 together to get a mask of possible match positions that likely match in at least 3 places.
 0276                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 277            }
 278        }
 279
 280        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 281        [CompExactlyDependsOn(typeof(Avx2))]
 282        private static Vector256<byte> GetComparisonResult(ref char searchSpace, nuint ch2ByteOffset, nuint ch3ByteOffse
 283        {
 284            // See comments in 'GetComparisonResult' for Vector128<byte> above.
 285            // This method is the same, but operates on 32 input characters at a time.
 0286            if (typeof(TCaseSensitivity) == typeof(CaseSensitive))
 287            {
 0288                Vector256<byte> cmpCh1 = Vector256.Equals(ch1, LoadPacked256(ref searchSpace, 0));
 0289                Vector256<byte> cmpCh2 = Vector256.Equals(ch2, LoadPacked256(ref searchSpace, ch2ByteOffset));
 0290                Vector256<byte> cmpCh3 = Vector256.Equals(ch3, LoadPacked256(ref searchSpace, ch3ByteOffset));
 0291                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 292            }
 293            else
 294            {
 0295                Vector256<byte> caseConversion = Vector256.Create(CaseConversionMask);
 296
 0297                Vector256<byte> cmpCh1 = Vector256.Equals(ch1, LoadPacked256(ref searchSpace, 0) & caseConversion);
 0298                Vector256<byte> cmpCh2 = Vector256.Equals(ch2, LoadPacked256(ref searchSpace, ch2ByteOffset) & caseConve
 0299                Vector256<byte> cmpCh3 = Vector256.Equals(ch3, LoadPacked256(ref searchSpace, ch3ByteOffset) & caseConve
 0300                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 301            }
 302        }
 303
 304        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 305        [CompExactlyDependsOn(typeof(Avx512BW))]
 306        private static Vector512<byte> GetComparisonResult(ref char searchSpace, nuint ch2ByteOffset, nuint ch3ByteOffse
 307        {
 308            // See comments in 'GetComparisonResult' for Vector128<byte> above.
 309            // This method is the same, but operates on 64 input characters at a time.
 0310            if (typeof(TCaseSensitivity) == typeof(CaseSensitive))
 311            {
 0312                Vector512<byte> cmpCh1 = Vector512.Equals(ch1, LoadPacked512(ref searchSpace, 0));
 0313                Vector512<byte> cmpCh2 = Vector512.Equals(ch2, LoadPacked512(ref searchSpace, ch2ByteOffset));
 0314                Vector512<byte> cmpCh3 = Vector512.Equals(ch3, LoadPacked512(ref searchSpace, ch3ByteOffset));
 0315                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 316            }
 317            else
 318            {
 0319                Vector512<byte> caseConversion = Vector512.Create(CaseConversionMask);
 320
 0321                Vector512<byte> cmpCh1 = Vector512.Equals(ch1, LoadPacked512(ref searchSpace, 0) & caseConversion);
 0322                Vector512<byte> cmpCh2 = Vector512.Equals(ch2, LoadPacked512(ref searchSpace, ch2ByteOffset) & caseConve
 0323                Vector512<byte> cmpCh3 = Vector512.Equals(ch3, LoadPacked512(ref searchSpace, ch3ByteOffset) & caseConve
 0324                return (cmpCh1 & cmpCh2 & cmpCh3).AsByte();
 325            }
 326        }
 327
 328        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 329        private bool TryMatch(ref char searchSpaceStart, int searchSpaceLength, ref char searchSpace, uint mask, out int
 330        {
 331            // 'mask' encodes the input positions where at least 3 characters likely matched.
 332            // Verify each one to see if we've found a match, otherwise return back to the vectorized loop.
 333            do
 334            {
 0335                int bitPos = BitOperations.TrailingZeroCount(mask);
 336
 0337                ref char matchRef = ref Unsafe.Add(ref searchSpace, bitPos);
 338
 0339                ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref matchRef, _valueState.Value.Length);
 340
 0341                if (CanSkipAnchorMatchVerification || TCaseSensitivity.Equals<TValueLength>(ref matchRef, in _valueState
 342                {
 0343                    offsetFromStart = (int)((nuint)Unsafe.ByteOffset(ref searchSpaceStart, ref matchRef) / sizeof(char))
 0344                    return true;
 345                }
 346
 0347                mask = BitOperations.ResetLowestSetBit(mask);
 348            }
 0349            while (mask != 0);
 350
 0351            offsetFromStart = 0;
 0352            return false;
 353        }
 354
 355        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 356        private bool TryMatch(ref char searchSpaceStart, int searchSpaceLength, ref char searchSpace, ulong mask, out in
 357        {
 358            // 'mask' encodes the input positions where at least 3 characters likely matched.
 359            // Verify each one to see if we've found a match, otherwise return back to the vectorized loop.
 360            do
 361            {
 0362                int bitPos = BitOperations.TrailingZeroCount(mask);
 363
 0364                ref char matchRef = ref Unsafe.Add(ref searchSpace, bitPos);
 365
 0366                ValidateReadPosition(ref searchSpaceStart, searchSpaceLength, ref matchRef, _valueState.Value.Length);
 367
 0368                if (CanSkipAnchorMatchVerification || TCaseSensitivity.Equals<TValueLength>(ref matchRef, in _valueState
 369                {
 0370                    offsetFromStart = (int)((nuint)Unsafe.ByteOffset(ref searchSpaceStart, ref matchRef) / sizeof(char))
 0371                    return true;
 372                }
 373
 0374                mask = BitOperations.ResetLowestSetBit(mask);
 375            }
 0376            while (mask != 0);
 377
 0378            offsetFromStart = 0;
 0379            return false;
 380        }
 381
 0382        internal override bool ContainsCore(string value) => HasUniqueValues
 0383            ? base.ContainsCore(value)
 0384            : _valueState.Value.Equals(value, IgnoreCase ? StringComparison.OrdinalIgnoreCase : StringComparison.Ordinal
 385
 0386        internal override string[] GetValues() => HasUniqueValues
 0387            ? base.GetValues()
 0388            : [_valueState.Value];
 389
 390        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 391        [CompExactlyDependsOn(typeof(Sse2))]
 392        [CompExactlyDependsOn(typeof(AdvSimd.Arm64))]
 393        private static Vector128<byte> LoadPacked128(ref char searchSpace, nuint byteOffset)
 394        {
 0395            Vector128<ushort> input0 = Vector128.LoadUnsafe(ref Unsafe.AddByteOffset(ref searchSpace, byteOffset));
 0396            Vector128<ushort> input1 = Vector128.LoadUnsafe(ref Unsafe.AddByteOffset(ref searchSpace, byteOffset + (uint
 397
 0398            return Sse2.IsSupported
 0399                ? Sse2.PackUnsignedSaturate(input0.AsInt16(), input1.AsInt16())
 0400                : AdvSimd.Arm64.UnzipEven(input0.AsByte(), input1.AsByte());
 401        }
 402
 403        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 404        [CompExactlyDependsOn(typeof(Avx2))]
 405        private static Vector256<byte> LoadPacked256(ref char searchSpace, nuint byteOffset) =>
 0406            Avx2.PackUnsignedSaturate(
 0407                Vector256.LoadUnsafe(ref Unsafe.AddByteOffset(ref searchSpace, byteOffset)).AsInt16(),
 0408                Vector256.LoadUnsafe(ref Unsafe.AddByteOffset(ref searchSpace, byteOffset + (uint)Vector256<byte>.Count)
 409
 410        [MethodImpl(MethodImplOptions.AggressiveInlining)]
 411        [CompExactlyDependsOn(typeof(Avx512BW))]
 412        private static Vector512<byte> LoadPacked512(ref char searchSpace, nuint byteOffset) =>
 0413            Avx512BW.PackUnsignedSaturate(
 0414                Vector512.LoadUnsafe(ref Unsafe.AddByteOffset(ref searchSpace, byteOffset)).AsInt16(),
 0415                Vector512.LoadUnsafe(ref Unsafe.AddByteOffset(ref searchSpace, byteOffset + (uint)Vector512<byte>.Count)
 416    }
 417}
 418