Use ROSpan.IndexOf as the workhorse for string.IndexOf (#17284)

* Use ROSpan.IndexOf as the workhorse for string.IndexOf

* Make changes to Span.IndexOf to follow what string.IndexOf did.

* Address PR feedback.

* Use Unsafe.Read instead of Unsafe.ReadUnaligned.

* Remove special casing for count == 0

* Fix up debug assert to use vector count instead of intptr.size

* Use size of Vector<ushort> instead of Vector<byte>.Count

Signed-off-by: dotnet-bot <dotnet-bot@microsoft.com>

2 files changed, 73 insertions, 171 deletions

diff --git a/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs
index 2033d8b90..47e83b7b2 100644
--- a/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs
+++ b/src/System.Private.CoreLib/shared/System/SpanHelpers.Char.cs
@@ -84,79 +84,87 @@ namespace System
         {
             Debug.Assert(length >= 0);
 
-            uint uValue = value; // Use uint for comparisons to avoid unnecessary 8->32 extensions
-            IntPtr index = (IntPtr)0; // Use IntPtr for arithmetic to avoid unnecessary 64->32->64 truncations
-            IntPtr nLength = (IntPtr)length;
-#if !netstandard11
-            if (Vector.IsHardwareAccelerated && length >= Vector<ushort>.Count * 2)
+            fixed (char* pChars = &searchSpace)
             {
-                const int elementsPerByte = sizeof(ushort) / sizeof(byte);
-                int unaligned = ((int)Unsafe.AsPointer(ref searchSpace) & (Vector<byte>.Count - 1)) / elementsPerByte;
-                nLength = (IntPtr)((Vector<ushort>.Count - unaligned) & (Vector<ushort>.Count - 1));
-            }
-        SequentialScan:
+                char* pCh = pChars;
+                char* pEndCh = pCh + length;
+
+#if !netstandard11
+                if (Vector.IsHardwareAccelerated && length >= Vector<ushort>.Count * 2)
+                {
+                    const int elementsPerByte = sizeof(ushort) / sizeof(byte);
+                    int unaligned = ((int)pCh & (Unsafe.SizeOf<Vector<ushort>>() - 1)) / elementsPerByte;
+                    length = ((Vector<ushort>.Count - unaligned) & (Vector<ushort>.Count - 1));
+                }
+            SequentialScan:
 #endif
-            while ((byte*)nLength >= (byte*)4)
-            {
-                nLength -= 4;
-
-                if (uValue == Unsafe.Add(ref searchSpace, index))
-                    goto Found;
-                if (uValue == Unsafe.Add(ref searchSpace, index + 1))
-                    goto Found1;
-                if (uValue == Unsafe.Add(ref searchSpace, index + 2))
-                    goto Found2;
-                if (uValue == Unsafe.Add(ref searchSpace, index + 3))
-                    goto Found3;
-
-                index += 4;
-            }
+                while (length >= 4)
+                {
+                    length -= 4;
+
+                    if (*pCh == value)
+                        goto Found;
+                    if (*(pCh + 1) == value)
+                        goto Found1;
+                    if (*(pCh + 2) == value)
+                        goto Found2;
+                    if (*(pCh + 3) == value)
+                        goto Found3;
+
+                    pCh += 4;
+                }
 
-            while ((byte*)nLength > (byte*)0)
-            {
-                nLength -= 1;
+                while (length > 0)
+                {
+                    length -= 1;
 
-                if (uValue == Unsafe.Add(ref searchSpace, index))
-                    goto Found;
+                    if (*pCh == value)
+                        goto Found;
 
-                index += 1;
-            }
+                    pCh += 1;
+                }
 #if !netstandard11
-            if (Vector.IsHardwareAccelerated && ((int)(byte*)index < length))
-            {
-                nLength = (IntPtr)((length - (int)(byte*)index) & ~(Vector<ushort>.Count - 1));
+                // We get past SequentialScan only if IsHardwareAccelerated is true. However, we still have the redundant check to allow
+                // the JIT to see that the code is unreachable and eliminate it when the platform does not have hardware accelerated.
+                if (Vector.IsHardwareAccelerated && pCh < pEndCh)
+                {
+                    length = (int)((pEndCh - pCh) & ~(Vector<ushort>.Count - 1));
 
-                // Get comparison Vector
-                Vector<ushort> vComparison = new Vector<ushort>(value);
+                    // Get comparison Vector
+                    Vector<ushort> vComparison = new Vector<ushort>(value);
 
-                while ((byte*)nLength > (byte*)index)
-                {
-                    var vMatches = Vector.Equals(vComparison, Unsafe.ReadUnaligned<Vector<ushort>>(ref Unsafe.As<char, byte>(ref Unsafe.Add(ref searchSpace, index))));
-                    if (Vector<ushort>.Zero.Equals(vMatches))
+                    while (length > 0)
                     {
-                        index += Vector<ushort>.Count;
-                        continue;
+                        // Using Unsafe.Read instead of ReadUnaligned since the search space is pinned and pCh is always vector aligned
+                        Debug.Assert(((int)pCh & (Unsafe.SizeOf<Vector<ushort>>() - 1)) == 0);
+                        Vector<ushort> vMatches = Vector.Equals(vComparison, Unsafe.Read<Vector<ushort>>(pCh));
+                        if (Vector<ushort>.Zero.Equals(vMatches))
+                        {
+                            pCh += Vector<ushort>.Count;
+                            length -= Vector<ushort>.Count;
+                            continue;
+                        }
+                        // Find offset of first match
+                        return (int)(pCh - pChars) + LocateFirstFoundChar(vMatches);
                     }
-                    // Find offset of first match
-                    return (int)(byte*)index + LocateFirstFoundChar(vMatches);
-                }
 
-                if ((int)(byte*)index < length)
-                {
-                    nLength = (IntPtr)(length - (int)(byte*)index);
-                    goto SequentialScan;
+                    if (pCh < pEndCh)
+                    {
+                        length = (int)(pEndCh - pCh);
+                        goto SequentialScan;
+                    }
                 }
-            }
 #endif
-            return -1;
-        Found: // Workaround for https://github.com/dotnet/coreclr/issues/13549
-            return (int)(byte*)index;
-        Found1:
-            return (int)(byte*)(index + 1);
-        Found2:
-            return (int)(byte*)(index + 2);
-        Found3:
-            return (int)(byte*)(index + 3);
+                return -1;
+            Found3:
+                pCh++;
+            Found2:
+                pCh++;
+            Found1:
+                pCh++;
+            Found:
+                return (int)(pCh - pChars);
+            }
         }
 
 #if !netstandard11
diff --git a/src/System.Private.CoreLib/shared/System/String.Searching.cs b/src/System.Private.CoreLib/shared/System/String.Searching.cs
index cc6e218d8..a4e5bbb62 100644
--- a/src/System.Private.CoreLib/shared/System/String.Searching.cs
+++ b/src/System.Private.CoreLib/shared/System/String.Searching.cs
@@ -35,10 +35,7 @@ namespace System
         // Returns the index of the first occurrence of a specified character in the current instance.
         // The search starts at startIndex and runs thorough the next count characters.
         //
-        public int IndexOf(char value)
-        {
-            return IndexOf(value, 0, this.Length);
-        }
+        public int IndexOf(char value) => SpanHelpers.IndexOf(ref _firstChar, value, Length);
 
         public int IndexOf(char value, int startIndex)
         {
@@ -74,122 +71,19 @@ namespace System
 
         public unsafe int IndexOf(char value, int startIndex, int count)
         {
+            // These bounds checks are redundant since AsSpan does them already, but are required
+            // so that the correct parameter name is thrown as part of the exception.
             if ((uint)startIndex > (uint)Length)
                 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
 
             if ((uint)count > (uint)(Length - startIndex))
                 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
 
-            fixed (char* pChars = &_firstChar)
-            {
-                char* pCh = pChars + startIndex;
-                char* pEndCh = pCh + count;
-
-                if (Vector.IsHardwareAccelerated && count >= Vector<ushort>.Count * 2)
-                {
-                    unchecked
-                    {
-                        const int elementsPerByte = sizeof(ushort) / sizeof(byte);
-                        int unaligned = ((int)pCh & (Vector<byte>.Count - 1)) / elementsPerByte;
-                        count = ((Vector<ushort>.Count - unaligned) & (Vector<ushort>.Count - 1));
-                    }
-                }
-            SequentialScan:
-                while (count >= 4)
-                {
-                    if (*pCh == value) goto ReturnIndex;
-                    if (*(pCh + 1) == value) goto ReturnIndex1;
-                    if (*(pCh + 2) == value) goto ReturnIndex2;
-                    if (*(pCh + 3) == value) goto ReturnIndex3;
-
-                    count -= 4;
-                    pCh += 4;
-                }
-
-                while (count > 0)
-                {
-                    if (*pCh == value)
-                        goto ReturnIndex;
-
-                    count--;
-                    pCh++;
-                }
-
-                if (pCh < pEndCh)
-                {
-                    count = (int)((pEndCh - pCh) & ~(Vector<ushort>.Count - 1));
-                    // Get comparison Vector
-                    Vector<ushort> vComparison = new Vector<ushort>(value);
-                    while (count > 0)
-                    {
-                        var vMatches = Vector.Equals(vComparison, Unsafe.ReadUnaligned<Vector<ushort>>(pCh));
-                        if (Vector<ushort>.Zero.Equals(vMatches))
-                        {
-                            pCh += Vector<ushort>.Count;
-                            count -= Vector<ushort>.Count;
-                            continue;
-                        }
-                        // Find offset of first match
-                        return (int)(pCh - pChars) + LocateFirstFoundChar(vMatches);
-                    }
-
-                    if (pCh < pEndCh)
-                    {
-                        unchecked
-                        {
-                            count = (int)(pEndCh - pCh);
-                        }
-                        goto SequentialScan;
-                    }
-                }
-
-                return -1;
+            int result = SpanHelpers.IndexOf(ref Unsafe.Add(ref _firstChar, startIndex), value, count);
 
-            ReturnIndex3: pCh++;
-            ReturnIndex2: pCh++;
-            ReturnIndex1: pCh++;
-            ReturnIndex:
-                return (int)(pCh - pChars);
-            }
+            return result == -1 ? result : result + startIndex;
         }
 
-        // Vector sub-search adapted from https://github.com/aspnet/KestrelHttpServer/pull/1138
-        [MethodImpl(MethodImplOptions.AggressiveInlining)]
-        private static int LocateFirstFoundChar(Vector<ushort> match)
-        {
-            var vector64 = Vector.AsVectorUInt64(match);
-            ulong candidate = 0;
-            int i = 0;
-            // Pattern unrolled by jit https://github.com/dotnet/coreclr/pull/8001
-            for (; i < Vector<ulong>.Count; i++)
-            {
-                candidate = vector64[i];
-                if (candidate != 0)
-                {
-                    break;
-                }
-            }
-
-            // Single LEA instruction with jitted const (using function result)
-            return i * 4 + LocateFirstFoundChar(candidate);
-        }
-
-        [MethodImpl(MethodImplOptions.AggressiveInlining)]
-        private static int LocateFirstFoundChar(ulong match)
-        {
-            unchecked
-            {
-                // Flag least significant power of two bit
-                var powerOfTwoFlag = match ^ (match - 1);
-                // Shift all powers of two into the high byte and extract
-                return (int)((powerOfTwoFlag * XorPowerOfTwoToHighChar) >> 49);
-            }
-        }
-
-        private const ulong XorPowerOfTwoToHighChar = (0x03ul |
-                                                       0x02ul << 16 |
-                                                       0x01ul << 32) + 1;
-
         // Returns the index of the first occurrence of any specified character in the current instance.
         // The search starts at startIndex and runs to startIndex + count - 1.
         //