搜索字符串中第一个定界符的有效方法是什么？

Question

我有一个 UTF-8 编码的字符串，我想遍历它，将其拆分为多个定界符之一。我也需要知道哪个个分隔符匹配，因为每个分隔符都有特定的含义。

用法示例：

algorithm("one, two; three") => Match("one")
algorithm(", two; three")    => Delimiter(",")
algorithm(" two; three")     => Match(" two")
algorithm("; three")         => Delimiter(";")
algorithm(" three")          => Match(" three")

附加信息：

我的分隔符都是单个ASCII字符，所以优化了需要的算法是可能的。
处理 UTF-8 子字符串的解决方案也将不胜感激，但不是必需的。
我计划多次调用该方法并且可能会很紧循环，所以理想的算法不需要分配任何内存。
算法应该return第一个匹配的字符串或分隔符我可以在下一次迭代中重新开始搜索。
一个理想的算法会天生就知道它是 return 匹配还是分隔符，但可以在事后检查。

我的目标语言是 Rust，但我希望得到任何答案具有类似的较低级别重点的语言。伪代码也很好，只要它能识别 UTF-8 文本的现实。解决方案使用深奥的十六进制技巧或 SIMD 指令也适用，但可能需要更多解释才能理解 ^_^。

Answer 1

对于特定于处理器的解决方案，具有 SSE4.2 的 X86-64 处理器包含 PCMPxSTRx 指令族。这些指令可用的模式之一是 Equal Any:

arg1 is a character set, arg2 is the string to search in. IntRes1[i] is set to 1 if arg2[i] is in the set represented by arg1

基本算法很简单：

用最多 16 个单字节填充 XMM 寄存器以搜索（指针）。
设置针字节数rax。
计算字符串开头的内存地址，包括偏移量。
在 rdx 中设置 haystack 字节数。
使用适当的控制字节调用 PCMPxSTRx。
检查 ecx 或控制代码标志之一的结果。
如果没有匹配项并且仍有字符串要搜索，则增加偏移量并循环。

但是有a complication around page boundaries。即，PCMPxSTRx 指令将总是读取 16 个字节的数据。如果您读入受保护的内存页，这可能会导致分段错误。一种解决方案是将所有读取对齐到字符串的 end，并处理开头的剩余字节。在开始上述算法之前，使用类似的东西：

用~0xF屏蔽字符串的开头地址。这将清除所有低位。
对前 16 个字节使用 PCMPxSTRM 指令（具有与上述算法类似的设置）。这 returns 匹配字符的掩码。您可以移动掩码以忽略不属于您的字符串的前导字符。
如果没有匹配项并且还有更多字符串需要搜索，则开始上述算法。

你可以在我的Rust library Jetscii中看到这个算法的完整例子。内联汇编用于调用 PCMPxSTRx 指令。

搜索字符串中第一个定界符的有效方法是什么？

What is an efficient way to search a string for the first of a set of delimiters?

string

algorithm

search

utf-8