字符必须以某种方式编码为位。互联网上的大多数字符串，包括有关Habré的帖子，都以UTF-8编码。 UTF-8格式以一个，两个，三个或四个字节表示“字符”。这是ASCII标准的概括，每个字符仅使用一个字节。也就是说，ASCII字符串也是UTF-8字符串。
实际上有点复杂，因为从技术上讲UTF-8描述了代码点。像表情符号这样的可见字符可以包含多个代码点……但是大多数程序员不需要这些繁琐的措辞。
还有其他标准。一些较旧的编程语言，例如C＃和Java依赖于UTF-16。每个字符使用两个或四个字节。当时似乎是个好主意，但现在共识正在朝着随时随地使用UTF-8的方向发展。
大多数编码都有强制性的限制。换句话说，没有任何随机的位序列可以进入UTF-8。因此，您需要验证字符串-检查它是否确实是UTF-8。
有什么关系？大。例如，Microsoft的Web服务器具有此漏洞：它接受看似有效且安全的URI，但是当服务器解释该URI时，它将为攻击者提供对磁盘的远程访问。即使不考虑安全问题，您几乎肯定也不想在数据库中存储无效的行。
因此，编程语言，Web服务器，浏览器和数据库引擎一直在验证UTF-8。
如果您的字符串大多只是ASCII，则检查速度非常快，并且UTF-8检查也不成问题。大多数字符串都是ASCII编码的日子已经一去不复返了。我们生活在一个表情符号和许多国家字母的世界中。
早在2018年，我问自己：UTF-8字符串能被验证多快？当时，我找到了一个验证选项，每个符号有几个CPU周期。一个人可以对此冷静下来，但是这个答案让我不满意。
这项工作花了几年时间，但现在看来我们已经有了一个接近理想的版本。新算法比其他快速搜索选项快一个数量级。我们准备了一份白皮书：“每字节少于一条指令的UTF-8验证”（将在软件中发布：实践和经验），并且还发布了基准实用程序。
所有细节都在科学文章中进行了解释，因此在此我们将不再赘述，而仅简要考虑其实质。 UTF-8验证的主要部分是通过查找成对的连续字节来完成的。在检查了所有字节对并确定了可以从该信息中找到的任何可能的违规之后，剩下的工作相对较少。
所有处理器均具有快速SIMD指令。它们与宽寄存器（128位，256位等）一起使用。大多数集合都有一个``向量化查找''指令，该指令接受16字节的值（范围从0到16），并在16字节的表中搜索它们。在Intel和AMD处理器中，此描述对应于以下说明
pshufb... 0到16之间的值有时称为半字节，跨度为4位。该字节由两个半字节（低和高）组成。
在我们的搜索算法中，向量化的搜索指令被调用了三次：一次用于低位半字节，一次用于高位半字节，一次用于高位半字节。我们有三个对应的16字节查找表。如果正确选择它们，则三个搜索的按位与将发现任何错误。
有关更多详细信息，请参见科学文章，但最终仅用五行快速C ++代码完成了几乎完整的UTF-8验证，而没有任何分支...并且这五行一次检查了最多32个字节的块...
simd8 classify(simd8 input, simd8 previous_input) {
auto prev1 = input.prev<1>(previous_input);
auto byte_1_high = prev1.shift_right <4>().lookup_16(table1);
auto byte_1_low = (prev1 & 0x0F).lookup_16(table2);
auto byte_2_high = input.shift_right <4>().lookup_16(table3);
return (byte_1_high & byte_1_low & byte_2_high);
}尽管不是很明显，但这种验证是足够的，而且100％安全。真的是。仅剩一些廉价的附加技术步骤。
结果，在最新的Intel / AMD处理器上，即使要验证最垃圾的随机输入，每字节所需的指令也要少于一个字节。由于代码经过了非常优化，因此每个周期最多可以增加3条指令，甚至更多。也就是说，在现代CPU上，每个输入字节我们只使用一小部分周期（少于三分之一）。因此，处理速度可靠地保持在12 GB / s以上。
课程是，常规查找表很有用，但矢量化表是高速算法的基本构建块。
如果您需要在生产中使用快速UTF-8验证功能，建议您使用simdjson库（0.5或更高版本）。它经过了充分的测试，并具有有用的内置功能，例如运行时调度。尽管该库旨在解析JSON，但即使根本没有JSON，也可以将其纯粹用于UTF-8验证。它支持64位ARM和x64处理器，还具有对其他CPU的回退处理。我们将其与一个源文件一起打包到一个头文件中；因此您可以将其放入C ++项目中。
之前的工作... 推广向量化分类方法的主要优点（属于搜索算法）属于Mula。据我所知，Keizer率先提出了我们的三重搜索策略。K. Willets创建了第一个基于SIMD的实用UTF-8验证算法。包括Z. Wegner在内的几个人对此进行了改进。Travis Downs提出了有关如何加快传统算法速度的明智想法。
进一步阅读。如果您喜欢这项工作，则可能会喜欢其他与以下主题相关的文章：“以接近于内存的速度进行Base64编码和解码”（软件：Practice and Experience，50（2），2020年）和“每秒解析JSON千兆字节”（ VLDB杂志，28（6），2019）。