Skip to content

Commit d42a835

Browse files
EgorBoCopilot
andauthored
Use safe code for UTF-8 StartsWith(OrdinalIgnoreCase) (#134857)
Rewrites `Ordinal.StartsWithIgnoreCaseUtf8`, which backs `MemoryExtensions.StartsWithOrdinalIgnoreCaseUtf8`, using safe span-based code. There's no `Unsafe.*` or `MemoryMarshal.*`. Its only caller is UTF-8 floating-point parsing: once the numeric parse fails, the parser matches `NumberFormatInfo.PositiveSign`/`NegativeSign`. Across all 890 ICU cultures, these signs are 1 byte in ~94% of cultures and at most 7 bytes (`U+200E + U+200E`). So the vectorized and unrolled paths are replaced with: - **An inlined fast path for a single ASCII byte prefix:** it's inlined into the parsing code, so the common `+`/`-` case doesn't call out of line. - **A single loop for everything else:** ASCII bytes are compared inline, and runes are decoded only when both sides are non-ASCII. ### Behavior changes - **`Rune.ToUpperOrdinal` instead of `Rune.ToUpperInvariant`:** non-ASCII runes now use the same casing as UTF-16 `OrdinalIgnoreCase`, with no ICU call per rune. - `ſ` (U+017F) no longer matches `s`. - Some newer scalars (e.g. Garay U+10D70–U+10D85) now match their uppercase forms, as they do in UTF-16. - **Immediate rejection of an ASCII byte against a non-ASCII byte:** no non-ASCII scalar uppercases to ASCII under ordinal casing. - **Fixes for bugs in the previous implementation:** - **3-byte tail with non-ASCII data:** it created spans extending up to 2 bytes past the end of both inputs. For example, `"aé"`/`"aÉ"` returned `false` and `"aé"`/`"bé"` returned `true`. - **Prefix longer than the source (both ≥ 16 bytes):** it could match. For example, `"Content-Length: 1234"`/`"content-length: 1234x"` returned `true`. - **ASCII vs. non-ASCII:** results depended on block alignment. ### Benchmarks `double.TryParse` on UTF-8 input; [EgorBot results](EgorBot/Benchmarks#629). `PR/main` below 1.00 is faster. #### macOS arm64 — Apple M4 | Case | PositiveSign / NegativeSign | Input | main | PR | PR/main | |---|---|---|---:|---:|---:| | Inv_PlusInfinity | `+` / `-` | `+infinity` | 19.68 ns | 19.43 ns | 0.99 | | Inv_PlusNaN_Upper | `+` / `-` | `+NAN` | 18.80 ns | 17.99 ns | 0.96 | | Inv_MinusNaN | `+` / `-` | `-nan` | 24.20 ns | 22.74 ns | 0.94 | | Inv_Invalid | `+` / `-` | `abc` | 22.40 ns | 20.70 ns | 0.92 | | Inv_NonAsciiInput | `+` / `-` | `∞` | 22.61 ns | 21.15 ns | 0.94 | | U2212_MinusNaN | `+` / `U+2212` | `U+2212` `nan` | 26.44 ns | 27.07 ns | 1.02 | | U2212_HyphenNaN | `+` / `U+2212` | `-nan` | 26.40 ns | 25.09 ns | 0.95 | | U2212_Invalid | `+` / `U+2212` | `abc` | 22.32 ns | 21.41 ns | 0.96 | | LRM_PlusInfinity | `LRM+LRM` / `LRM-LRM` | `LRM+LRMinfinity` | 61.32 ns | 29.04 ns | 0.47 | | LRM_PlainPlusInfinity | `LRM+LRM` / `LRM-LRM` | `+infinity` | 22.60 ns | 22.50 ns | 1.00 | | LRM_Invalid | `LRM+LRM` / `LRM-LRM` | `abc` | 21.81 ns | 21.20 ns | 0.97 | | `double.Parse("-nan"u8)` | invariant | `-nan` | 24.81 ns | 23.30 ns | 0.94 | #### Linux x64 — AMD EPYC 9V45 | Case | PositiveSign / NegativeSign | Input | main | PR | PR/main | |---|---|---|---:|---:|---:| | Inv_PlusInfinity | `+` / `-` | `+infinity` | 25.75 ns | 24.72 ns | 0.96 | | Inv_PlusNaN_Upper | `+` / `-` | `+NAN` | 21.73 ns | 22.38 ns | 1.03 | | Inv_MinusNaN | `+` / `-` | `-nan` | 26.57 ns | 30.05 ns | 1.13 | | Inv_Invalid | `+` / `-` | `abc` | 24.00 ns | 23.41 ns | 0.98 | | Inv_NonAsciiInput | `+` / `-` | `∞` | 25.23 ns | 24.75 ns | 0.98 | | U2212_MinusNaN | `+` / `U+2212` | `U+2212` `nan` | 27.56 ns | 30.75 ns | 1.12 | | U2212_HyphenNaN | `+` / `U+2212` | `-nan` | 29.25 ns | 29.06 ns | 0.99 | | U2212_Invalid | `+` / `U+2212` | `abc` | 24.97 ns | 23.98 ns | 0.96 | | LRM_PlusInfinity | `LRM+LRM` / `LRM-LRM` | `LRM+LRMinfinity` | 69.76 ns | 31.65 ns | 0.45 | | LRM_PlainPlusInfinity | `LRM+LRM` / `LRM-LRM` | `+infinity` | 26.33 ns | 27.20 ns | 1.03 | | LRM_Invalid | `LRM+LRM` / `LRM-LRM` | `abc` | 25.21 ns | 24.75 ns | 0.98 | | `double.Parse("-nan"u8)` | invariant | `-nan` | 26.90 ns | 26.05 ns | 0.97 | #### Windows x64 — AMD EPYC 9V45 | Case | PositiveSign / NegativeSign | Input | main | PR | PR/main | |---|---|---|---:|---:|---:| | Inv_PlusInfinity | `+` / `-` | `+infinity` | 30.96 ns | 30.79 ns | 0.99 | | Inv_PlusNaN_Upper | `+` / `-` | `+NAN` | 27.33 ns | 27.89 ns | 1.02 | | Inv_MinusNaN | `+` / `-` | `-nan` | 32.68 ns | 32.47 ns | 0.99 | | Inv_Invalid | `+` / `-` | `abc` | 31.75 ns | 28.53 ns | 0.90 | | Inv_NonAsciiInput | `+` / `-` | `∞` | 32.68 ns | 34.31 ns | 1.05 | | U2212_MinusNaN | `+` / `U+2212` | `U+2212` `nan` | 34.11 ns | 37.55 ns | 1.10 | | U2212_HyphenNaN | `+` / `U+2212` | `-nan` | 36.61 ns | 39.84 ns | 1.09 | | U2212_Invalid | `+` / `U+2212` | `abc` | 29.60 ns | 29.22 ns | 0.99 | | LRM_PlusInfinity | `LRM+LRM` / `LRM-LRM` | `LRM+LRMinfinity` | 80.27 ns | 37.68 ns | 0.47 | | LRM_PlainPlusInfinity | `LRM+LRM` / `LRM-LRM` | `+infinity` | 31.53 ns | 33.44 ns | 1.06 | | LRM_Invalid | `LRM+LRM` / `LRM-LRM` | `abc` | 38.33 ns | 30.76 ns | 0.80 | | `double.Parse("-nan"u8)` | invariant | `-nan` | 33.84 ns | 36.07 ns | 1.07 | `LRM` is U+200E. --------- Co-authored-by: Copilot <[email protected]> Copilot-Session: 48e318b5-e3dd-40ea-84a9-c5c0b0592660
1 parent a1cdbbb commit d42a835

3 files changed

Lines changed: 69 additions & 285 deletions

File tree

‎src/libraries/System.Private.CoreLib/src/System/Globalization/Ordinal.Utf8.cs‎

Lines changed: 29 additions & 276 deletions
Original file line numberDiff line numberDiff line change
@@ -326,318 +326,71 @@ internal static bool EqualsIgnoreCaseUtf8_Scalar(ref byte charA, int lengthA, re
326326
return EqualsStringIgnoreCaseUtf8(ref Unsafe.AddByteOffset(ref charA, byteOffset), lengthA - range, ref Unsafe.AddByteOffset(ref charB, byteOffset), lengthB - range);
327327
}
328328

329-
internal static bool StartsWithStringIgnoreCaseUtf8(ref byte source, int sourceLength, ref byte prefix, int prefixLength)
329+
// Not optimized for large inputs yet: the only callers (number parsing) pass short sign symbols.
330+
internal static bool StartsWithIgnoreCaseUtf8(ReadOnlySpan<byte> source, ReadOnlySpan<byte> prefix)
330331
{
331332
// NOTE: Two UTF-8 inputs of different length might compare as equal under
332333
// the OrdinalIgnoreCase comparer. This is distinct from UTF-16, where the
333334
// inputs being different length will mean that they can never compare as
334335
// equal under an OrdinalIgnoreCase comparer.
335336

336-
int length = Math.Min(sourceLength, prefixLength);
337-
int range = length;
338-
339-
const byte maxChar = 0x7F;
340-
341-
while ((length != 0) && (source <= maxChar) && (prefix <= maxChar))
337+
while (!prefix.IsEmpty)
342338
{
343-
// Ordinal equals or lowercase equals if the result ends up in the a-z range
344-
if (source == prefix ||
345-
((source | 0x20) == (prefix | 0x20) && char.IsAsciiLetter((char)source)))
346-
{
347-
length--;
348-
source = ref Unsafe.Add(ref source, 1);
349-
prefix = ref Unsafe.Add(ref prefix, 1);
350-
}
351-
else
339+
if (source.IsEmpty)
352340
{
341+
// The source ended before the prefix
353342
return false;
354343
}
355-
}
356344

357-
if (length == 0)
358-
{
359-
// Success if we reached the end of the prefix
360-
return prefixLength == 0;
361-
}
345+
uint a = source[0];
346+
uint b = prefix[0];
362347

363-
range -= length;
364-
return StartsWithStringIgnoreCaseNonAsciiUtf8(ref source, sourceLength - range, ref prefix, prefixLength - range);
365-
}
366-
367-
internal static bool StartsWithStringIgnoreCaseNonAsciiUtf8(ref byte source, int sourceLength, ref byte prefix, int prefixLength)
368-
{
369-
// NLS/ICU doesn't provide native UTF-8 support so we need to do our own corresponding ordinal comparison
370-
371-
ReadOnlySpan<byte> spanA = MemoryMarshal.CreateReadOnlySpan(ref source, sourceLength);
372-
ReadOnlySpan<byte> spanB = MemoryMarshal.CreateReadOnlySpan(ref prefix, prefixLength);
373-
374-
do
375-
{
376-
OperationStatus statusA = Rune.DecodeFromUtf8(spanA, out Rune runeA, out int bytesConsumedA);
377-
OperationStatus statusB = Rune.DecodeFromUtf8(spanB, out Rune runeB, out int bytesConsumedB);
378-
379-
if (statusA != statusB)
348+
if ((a | b) <= 0x7F)
380349
{
381-
// OperationStatus don't match; fail immediately
382-
return false;
383-
}
384-
385-
if (statusA == OperationStatus.Done)
386-
{
387-
if (Rune.ToUpperInvariant(runeA) != Rune.ToUpperInvariant(runeB))
350+
// Ordinal equals or lowercase equals if the result ends up in the a-z range
351+
if ((a != b) && (((a | 0x20) != (b | 0x20)) || !char.IsAsciiLetter((char)a)))
388352
{
389-
// Runes don't match when ignoring case; fail immediately
390353
return false;
391354
}
392-
}
393-
else if (!spanA.Slice(0, bytesConsumedA).SequenceEqual(spanB.Slice(0, bytesConsumedB)))
394-
{
395-
// OperationStatus match, but bytesConsumed or the sequence of bytes consumed do not; fail immediately
396-
return false;
397-
}
398-
399-
// The current runes or invalid byte sequences matched, slice and continue.
400-
// We'll exit the loop when the entirety of spanB has been processed.
401-
//
402-
// In the scenario where spanB is empty before spanB, we'll end up with that
403-
// span returning OperationStatus.NeedsMoreData and bytesConsumed=0 while spanB
404-
// will return a different OperationStatus or different bytesConsumed and thus
405-
// fail the operation.
406-
407-
spanA = spanA.Slice(bytesConsumedA);
408-
spanB = spanB.Slice(bytesConsumedB);
409-
}
410-
while (spanB.Length != 0);
411-
412-
return true;
413-
}
414-
415-
private static bool StartsWithIgnoreCaseUtf8_Vector128(ref byte source, int sourceLength, ref byte prefix, int prefixLength)
416-
{
417-
Debug.Assert(sourceLength >= Vector128<byte>.Count);
418-
Debug.Assert(prefixLength >= Vector128<byte>.Count);
419-
Debug.Assert(Vector128.IsHardwareAccelerated);
420-
421-
nuint lengthU = Math.Min((uint)sourceLength, (uint)prefixLength);
422-
nuint lengthToExamine = lengthU - (nuint)Vector128<byte>.Count;
423-
424-
nuint i = 0;
425-
426-
Vector128<byte> vec1;
427-
Vector128<byte> vec2;
428-
429-
do
430-
{
431-
vec1 = Vector128.LoadUnsafe(ref source, i);
432-
vec2 = Vector128.LoadUnsafe(ref prefix, i);
433-
434-
if (!Utf8Utility.AllBytesInVector128AreAscii(vec1 | vec2))
435-
{
436-
goto NON_ASCII;
437-
}
438-
439-
if (!Utf8Utility.Vector128OrdinalIgnoreCaseAscii(vec1, vec2))
440-
{
441-
return false;
442-
}
443-
444-
i += (nuint)Vector128<byte>.Count;
445-
}
446-
while (i <= lengthToExamine);
447-
448-
if (i == (uint)prefixLength)
449-
{
450-
// success if we reached the end of the prefix
451-
return true;
452-
}
453-
454-
// Use scalar path for trailing elements
455-
return StartsWithIgnoreCaseUtf8_Scalar(ref Unsafe.Add(ref source, i), (int)(lengthU - i), ref Unsafe.Add(ref prefix, i), (int)(lengthU - i));
456-
457-
NON_ASCII:
458-
if (Utf8Utility.AllBytesInVector128AreAscii(vec1) || Utf8Utility.AllBytesInVector128AreAscii(vec2))
459-
{
460-
// No need to use the fallback if one of the inputs is full-ASCII
461-
return false;
462-
}
463-
464-
// Fallback for Non-ASCII inputs
465-
return StartsWithStringIgnoreCaseUtf8(
466-
ref Unsafe.Add(ref source, i), sourceLength - (int)i,
467-
ref Unsafe.Add(ref prefix, i), prefixLength - (int)i
468-
);
469-
}
470-
471-
[MethodImpl(MethodImplOptions.AggressiveInlining)]
472-
internal static bool StartsWithIgnoreCaseUtf8(ref byte source, int sourceLength, ref byte prefix, int prefixLength)
473-
{
474-
if (!Vector128.IsHardwareAccelerated || (sourceLength < Vector128<byte>.Count) || (prefixLength < Vector128<byte>.Count))
475-
{
476-
return StartsWithIgnoreCaseUtf8_Scalar(ref source, sourceLength, ref prefix, prefixLength);
477-
}
478-
479-
return StartsWithIgnoreCaseUtf8_Vector128(ref source, sourceLength, ref prefix, prefixLength);
480-
}
481-
482-
internal static bool StartsWithIgnoreCaseUtf8_Scalar(ref byte source, int sourceLength, ref byte prefix, int prefixLength)
483-
{
484-
IntPtr byteOffset = IntPtr.Zero;
485-
486-
int length = Math.Min(sourceLength, prefixLength);
487-
int range = length;
488-
489-
#if TARGET_64BIT
490-
ulong valueAu64 = 0;
491-
ulong valueBu64 = 0;
492-
493-
// Read 8 chars (64 bits) at a time from each string
494-
while ((uint)length >= 8)
495-
{
496-
valueAu64 = Unsafe.ReadUnaligned<ulong>(ref Unsafe.AddByteOffset(ref source, byteOffset));
497-
valueBu64 = Unsafe.ReadUnaligned<ulong>(ref Unsafe.AddByteOffset(ref prefix, byteOffset));
498355

499-
// A 32-bit test - even with the bit-twiddling here - is more efficient than a 64-bit test.
500-
ulong temp = valueAu64 | valueBu64;
501-
502-
if (!Utf8Utility.AllBytesInUInt32AreAscii((uint)temp | (uint)(temp >> 32)))
503-
{
504-
// one of the inputs contains non-ASCII data
505-
goto NonAscii64;
356+
source = source.Slice(1);
357+
prefix = prefix.Slice(1);
358+
continue;
506359
}
507360

508-
// Generally, the caller has likely performed a first-pass check that the input strings
509-
// are likely equal. Consider a dictionary which computes the hash code of its key before
510-
// performing a proper deep equality check of the string contents. We want to optimize for
511-
// the case where the equality check is likely to succeed, which means that we want to avoid
512-
// branching within this loop unless we're about to exit the loop, either due to failure or
513-
// due to us running out of input data.
514-
515-
if (!Utf8Utility.UInt64OrdinalIgnoreCaseAscii(valueAu64, valueBu64))
361+
if ((a ^ b) > 0x7F)
516362
{
363+
// No non-ASCII scalar is equal to an ASCII one under ordinal casing
517364
return false;
518365
}
519366

520-
byteOffset += 8;
521-
length -= 8;
522-
}
523-
#endif
524-
525-
uint valueAu32 = 0;
526-
uint valueBu32 = 0;
367+
// NLS/ICU doesn't provide native UTF-8 support so we need to do our own corresponding ordinal comparison
368+
OperationStatus statusA = Rune.DecodeFromUtf8(source, out Rune runeA, out int bytesConsumedA);
369+
OperationStatus statusB = Rune.DecodeFromUtf8(prefix, out Rune runeB, out int bytesConsumedB);
527370

528-
// Read 4 chars (32 bits) at a time from each string
529-
#if TARGET_64BIT
530-
if ((uint)length >= 4)
531-
#else
532-
while ((uint)length >= 4)
533-
#endif
534-
{
535-
valueAu32 = Unsafe.ReadUnaligned<uint>(ref Unsafe.AddByteOffset(ref source, byteOffset));
536-
valueBu32 = Unsafe.ReadUnaligned<uint>(ref Unsafe.AddByteOffset(ref prefix, byteOffset));
537-
538-
if (!Utf8Utility.AllBytesInUInt32AreAscii(valueAu32 | valueBu32))
539-
{
540-
// one of the inputs contains non-ASCII data
541-
goto NonAscii32;
542-
}
543-
544-
// Generally, the caller has likely performed a first-pass check that the input strings
545-
// are likely equal. Consider a dictionary which computes the hash code of its key before
546-
// performing a proper deep equality check of the string contents. We want to optimize for
547-
// the case where the equality check is likely to succeed, which means that we want to avoid
548-
// branching within this loop unless we're about to exit the loop, either due to failure or
549-
// due to us running out of input data.
550-
551-
if (!Utf8Utility.UInt32OrdinalIgnoreCaseAscii(valueAu32, valueBu32))
552-
{
553-
return false;
554-
}
555-
556-
byteOffset += 4;
557-
length -= 4;
558-
}
559-
560-
if (length != 0)
561-
{
562-
// We have 1, 2, or 3 bytes remaining. We can't do anything fancy
563-
// like backtracking since we could have only had 1-3 bytes. So,
564-
// instead we'll do 1 or 2 reads to get all 3 bytes. Endianness
565-
// doesn't matter here since we only compare if all bytes are ascii
566-
// and the ordering will be consistent between the two comparisons
567-
568-
if (length == 3)
569-
{
570-
valueAu32 = Unsafe.ReadUnaligned<ushort>(ref Unsafe.AddByteOffset(ref source, byteOffset));
571-
valueBu32 = Unsafe.ReadUnaligned<ushort>(ref Unsafe.AddByteOffset(ref prefix, byteOffset));
572-
573-
byteOffset += 2;
574-
575-
valueAu32 |= (uint)(Unsafe.AddByteOffset(ref source, byteOffset) << 16);
576-
valueBu32 |= (uint)(Unsafe.AddByteOffset(ref prefix, byteOffset) << 16);
577-
}
578-
else if (length == 2)
579-
{
580-
valueAu32 = Unsafe.ReadUnaligned<ushort>(ref Unsafe.AddByteOffset(ref source, byteOffset));
581-
valueBu32 = Unsafe.ReadUnaligned<ushort>(ref Unsafe.AddByteOffset(ref prefix, byteOffset));
582-
}
583-
else
584-
{
585-
Debug.Assert(length == 1);
586-
587-
valueAu32 = Unsafe.AddByteOffset(ref source, byteOffset);
588-
valueBu32 = Unsafe.AddByteOffset(ref prefix, byteOffset);
589-
}
590-
591-
if (!Utf8Utility.AllBytesInUInt32AreAscii(valueAu32 | valueBu32))
592-
{
593-
goto NonAscii32; // one of the inputs contains non-ASCII data
594-
}
595-
596-
if (range != prefixLength)
371+
if (statusA != statusB)
597372
{
598-
// Failure if we didn't reach the end of the prefix
599373
return false;
600374
}
601375

602-
if (valueAu32 == valueBu32)
376+
if (statusA == OperationStatus.Done)
603377
{
604-
return true; // exact match
378+
if ((runeA != runeB) && (Rune.ToUpperOrdinal(runeA) != Rune.ToUpperOrdinal(runeB)))
379+
{
380+
return false;
381+
}
605382
}
606-
607-
if (!Utf8Utility.UInt32OrdinalIgnoreCaseAscii(valueAu32, valueBu32))
383+
else if (!source.Slice(0, bytesConsumedA).SequenceEqual(prefix.Slice(0, bytesConsumedB)))
608384
{
385+
// Invalid sequences must match exactly
609386
return false;
610387
}
611388

612-
byteOffset += 4;
613-
length -= 4;
614-
}
615-
616-
Debug.Assert(length == 0);
617-
return prefixLength <= sourceLength;
618-
619-
NonAscii32:
620-
// Both values have to be non-ASCII to use the slow fallback, in case if one of them is not we return false
621-
if (Utf8Utility.AllBytesInUInt32AreAscii(valueAu32) || Utf8Utility.AllBytesInUInt32AreAscii(valueBu32))
622-
{
623-
return false;
624-
}
625-
goto NonAscii;
626-
627-
#if TARGET_64BIT
628-
NonAscii64:
629-
// Both values have to be non-ASCII to use the slow fallback, in case if one of them is not we return false
630-
if (Utf8Utility.AllBytesInUInt64AreAscii(valueAu64) || Utf8Utility.AllBytesInUInt64AreAscii(valueBu64))
631-
{
632-
return false;
389+
source = source.Slice(bytesConsumedA);
390+
prefix = prefix.Slice(bytesConsumedB);
633391
}
634-
#endif
635-
NonAscii:
636-
range -= length;
637392

638-
// The non-ASCII case is factored out into its own helper method so that the JIT
639-
// doesn't need to emit a complex prolog for its caller (this method).
640-
return StartsWithStringIgnoreCaseUtf8(ref Unsafe.AddByteOffset(ref source, byteOffset), sourceLength - range, ref Unsafe.AddByteOffset(ref prefix, byteOffset), prefixLength - range);
393+
return true;
641394
}
642395
}
643396
}

‎src/libraries/System.Private.CoreLib/src/System/MemoryExtensions.Globalization.Utf8.cs‎

Lines changed: 1 addition & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -64,15 +64,7 @@ internal static bool StartsWithUtf8(this ReadOnlySpan<byte> span, ReadOnlySpan<b
6464
[MethodImpl(MethodImplOptions.AggressiveInlining)]
6565
internal static bool StartsWithOrdinalIgnoreCaseUtf8(this ReadOnlySpan<byte> span, ReadOnlySpan<byte> value)
6666
{
67-
// For UTF-8 ist is possible for two spans of different byte length
68-
// to compare as equal under an OrdinalIgnoreCase comparison.
69-
70-
if ((span.Length | value.Length) == 0) // span.Length == value.Length == 0
71-
{
72-
return true;
73-
}
74-
75-
return Ordinal.StartsWithIgnoreCaseUtf8(ref MemoryMarshal.GetReference(span), span.Length, ref MemoryMarshal.GetReference(value), value.Length);
67+
return Ordinal.StartsWithIgnoreCaseUtf8(span, value);
7668
}
7769
}
7870
}

0 commit comments

Comments
 (0)