超快的Unicode(UTF-8)验证

编程中最常见的“数据类型”之一是文本字符串。当程序员想到字符串时，他们会想象自己在处理一个列表或一个字符数组。这通常是一个“足够好”的近似值，但实际情况要复杂得多。

字符必须以某种方式编码成位。互联网上的大多数字符串，包括这篇博客文章，都是使用一种名为UTF-8的标准进行编码的。UTF-8格式使用1、2、3或4个字节表示“字符”。它是ASCII标准的推广，每个字符只使用一个字节。也就是说，ASCII字符串也是UTF-8字符串。

它稍微复杂一些，因为从技术上讲，utf-8描述的是代码点，一个可见字符(如表情符号)可以由几个代码点…组成。但对于大多数程序员来说，这是一个迂腐的区别。

还有其他标准。一些较老的编程语言(如C#和Java)依赖于UTF-16。在UTF-16中，每个字符使用两个或四个字节。这在当时看起来是个好主意，但我相信，共识正越来越多地朝着随时随地使用UTF-8的方向发展。

大多数字符编码的共同点是它们受到约束，并且这些约束必须强制执行。换句话说，并不是任何随机位序列都是UTF-8。因此，您必须验证收到的字符串是有效的UTF-8。

有关系吗？的确如此。例如，Microsoft的Web服务器存在安全漏洞，而用户可以发送在安全检查看来是有效和安全的URI，但一旦被服务器解释，就会允许攻击者在服务器的磁盘上导航。即使安全性不是问题，您几乎肯定希望在将无效字符串存储到数据库之前拒绝它们，因为这是一种损坏形式。

因此，您的编程语言、Web服务器、浏览器、数据库引擎一直都在验证UTF-8。

如果您的字符串大多只是ASCII字符串，那么检查速度会相当快，UTF-8验证是没有问题的。然而，所有字符串都是可靠的ASCII字符串的日子已经一去不复返了。我们生活在表情符号和国际字符的世界里。

早在2018年，我就开始想知道…。验证UTF-8字符串的速度有多快？我当时得到的答案是每个字符需要几个CPU周期。这可能看起来令人满意，但我并不高兴。

这花了几年时间，但我相信我们现在已经达到了可能是人们所能做的最好的东西：查找算法。它可以比常见的FAST替代产品快十倍以上。我们写了一篇关于它的研究论文：在每个字节少于一条指令的情况下验证UTF-8(将出现在软件：实践和体验中)。我们还发布了我们的基准软件。

因为我们有一整篇研究论文来解释，所以我不会深入细节，但是核心的洞察力是相当整齐的。大多数UTF-8验证可以通过查看成对的连续字节来完成。一旦您确定了通过查看所有连续字节对可以检测到的所有违规，剩下的工作就相对较少了(每个字节)。

我们的处理器都有快速的SIMD指令。它们是在宽寄存器(128位、256位等)上操作的指令。它们中的大多数都有一个“矢量化查找”指令，该指令可以获取16字节值(在0到16的范围内)，然后在16字节表中查找它们。英特尔和AMD处理器具有与此描述匹配的pShufb指令。范围在0到16之间的值有时称为半字节，它跨越4位。一个字节由两个半字节(低半字节和高半字节)组成。

在查找算法中，我们调用矢量化查找指令三次：一次在低位半字节上，一次在高位半字节上，一次在下一个字节的高位半字节上。我们有三个相应的16字节查找表。通过恰到好处地选择它们，三个查找中的逐位AND将允许我们发现任何错误。

有关更多详细信息，请参阅本文，但最终结果是，您可以使用大约5行快速C++代码验证几乎全部的UTf-8字符串，而无需任何分支…。并且这5行一次验证大小为32字节的块…。

Simd8分类(simd8输入，simd8上一次输入){ AUTO PROVER1=输入.prev<；1>；(Previous_Input)； AUTO BYTE_1_HIGH=优先1.Shift_Right<；4>；().lookup_16(表1)； AUTO BYTE_1_LOW=(优先1&；0x0F).lookup_16(表2)； AUTO BYTE_2_HIGH=输入.Shift_Right<；4>；().lookup_16(表3)； RETURN(BYTE_1_HIGH&；BYTE_1_LOW&；BYTE_2_HIGH)； }。

目前还不清楚这是否足够和100%安全。但它是。您只需要几个便宜的额外技术步骤。

最终结果是，在最新的Intel/AMD处理器上，即使是更糟糕的随机输入，也只需要每字节不到一条指令就可以验证，而且由于代码非常精简，每个周期可以停用三条以上这样的指令。因此，我们始终实现超过12 Gb/s的速度。

教训是，虽然查找表很有用，但矢量化查找表是高速算法的基本构建块。

如果您需要在生产设置中使用快速查找UTF-8验证功能，我们建议您查看simdjson库(0.5版或更高版本)。它经过了很好的测试，并且有一些功能可以让您的生活变得更轻松，比如运行时调度。虽然simdjson库是由JSON解析驱动的，但是即使在看不到JSON的情况下，您也可以使用它来验证UTF-8。Simdjson支持64位ARM和x64处理器，具有其他系统的后备功能。我们将其打包为单个头文件和单个源文件；因此，您几乎可以将其放入您的C++项目中。

功劳：Muł比任何人都普及了矢量化分类技术，这是查找算法的关键。据我所知，Keiser最先提出了三查策略。据我所知，第一个实用的(非破解的)基于SIMD的UTF-8验证算法是由K.Willets设计的。包括Z.Wegner在内的几个人表明，你可以做得更好。特拉维斯·唐斯还就如何加速传统算法提供了聪明的见解。

进一步阅读：如果您喜欢这项工作，您可能会喜欢以几乎与内存副本相同的速度进行Base64编码和解码(软件：实践和经验50(2)，2020)和每秒解析千兆字节的JSON(VLDB Journal 28(6)，2019年)。