c# - UTF8 字节的 ReadOnlySpan 内的 IndexOf char

Question

我正在寻找一种高效、免分配(!)的实现

public static int IndexOf(this ReadOnlySpan<byte> utf8Bytes, char @char)
{
   // Should return the index of the first byte of @char within utf8Bytes
   // (not the character index of @char within the string)
}

我还没有找到一种方法来逐个字符地遍历跨度。 Utf8Parser 没有支持单个字符的重载。System.Text.Encoding 似乎主要在整个跨度上工作，并且在这样做时确实在内部分配。

是否有任何我还没有发现的内置功能？如果没有，有人能想到一个合理的自定义实现吗？

Answer 1

而不是尝试迭代 utf8Bytes逐个字符，将字符转换为短的 stackalloc'ed utf8 字节序列并搜索它可能会更容易:

public static class StringExtensions
{
    const int MaxBytes = 4;

    public static int IndexOf(this ReadOnlySpan<byte> utf8Bytes, char @char)
    {
        Rune rune;
        try
        {
            rune = new Rune(@char);
        }
        catch (ArgumentOutOfRangeException)
        {
            // Malformed unicode character, return -1 or throw?
            return -1;
        }
        return utf8Bytes.IndexOf(rune);
    }       
    
    public static int IndexOf(this ReadOnlySpan<byte> utf8Bytes, Rune @char)
    {
        Span<byte> charBytes = stackalloc byte[MaxBytes];
        var n = @char.EncodeToUtf8(charBytes);
        charBytes = charBytes.Slice(0, n);
        
        for (int i = 0, thisLength = 1; i <= utf8Bytes.Length - charBytes.Length; i += thisLength)
        {
            thisLength = Utf8ByteSequenceLength(utf8Bytes[i]);
            if (thisLength == charBytes.Length && charBytes.CommonPrefixLength(utf8Bytes.Slice(i)) == charBytes.Length)
                return i;
        }
        return -1;
    }       
    
    static int Utf8ByteSequenceLength(byte firstByte)
    {
        //https://en.wikipedia.org/wiki/UTF-8#Encoding
        if (     (firstByte & 0b11111000) == 0b11110000) // 11110xxx
            return 4;
        else if ((firstByte & 0b11110000) == 0b11100000) // 1110xxxx
            return 3;
        else if ((firstByte & 0b11100000) == 0b11000000) // 110xxxxx
            return 2;
        return 1; // Either a 1-byte sequence (matching 0xxxxxxx) or an invalid start byte.
    }
}

注释:

• Rune 是 .NET Core 3.x 中引入的一个结构体，表示 Unicode 标量值。如果您需要搜索您的utf8Bytes对于不在 basic multilingual plane 中的 Unicode 代码点，你将需要使用 rune 。

  Rune其方法 Rune.TryEncodeToUtf8() 具有额外的优点是轻量级且免分配的。

• 如果 char @char是无效的 Unicode 字符，如果您尝试构造 Rune，.NET 编码算法将引发异常。从中。上面的代码捕获异常并返回-1 。您可能希望重新抛出异常。

• 作为替代方案， Rune.DecodeFromUtf8(ReadOnlySpan<Byte>, Rune, Int32) 可用于逐个 Rune 迭代 utf8 字节范围。您可以使用它通过索引来定位传入的 rune 。不过，我怀疑这样做的效率会比上面的方法低。

演示 fiddle here .