protobuf 中 Range SIMD 算法实战解析：third_party/utf8_range 的高速 UTF-8 校验实现（NEON / SSE4 / AVX2）

本文围绕 protobuf 仓库的 third_party/utf8_range/README.md 展开，系统讲解其核心贡献——基于"区间表 + 查找表"的 Range 算法如何用 SIMD（NEON/SSE4/AVX2）一次校验 16 字节 UTF-8 字符串，并完整继承原文档的编码格式表、区间表、基准测试数据与测试用例设计方法，同时结合仓库内 utf8_range.c、utf8_range_sse.inc 等运行时源码，说明该算法在 protobuf 实际解析路径中的调用关系。读完本文，你将掌握：Range 算法的完整数学原理与逐字节推演、基准测试工具 ./utf8 bench / ./utf8 test 的使用方式、以及该库在 protobuf 中作为字符串字段合法性热路径的集成方式。

1. 这个库在 protobuf 中扮演什么角色

Protocol Buffers 在 wire format 中大量传输 string 与 bytes(string) 字段。按照 proto3 语义与 JSON 映射规则，字符串字段必须是结构上合法的 UTF-8 序列，因此"校验一段字节是否为合法 UTF-8"会出现在消息解析、JSON 编解码、text format 等高频路径上——校验速度直接影响整体解析性能。third_party/utf8_range 就是 protobuf 为此引入的 SIMD 加速 UTF-8 校验库。

它对外暴露两层接口：

1. C 接口，定义在 utf8_range.h：
   • bool utf8_range_IsValid(const char* data, size_t len)：整段是否为合法 UTF-8，是返回 1，否则 0；
   • size_t utf8_range_ValidPrefix(const char* data, size_t len)：返回"从开头到第一个非法字节之前的最长合法前缀"的字节长度，供解析器定位错误位置使用。
2. C++ 包装，定义在 utf8_validity.h：
   • utf8_range::IsStructurallyValid(absl::string_view)
   • utf8_range::SpanStructurallyValid(absl::string_view)

这两个函数在 protobuf 源码中的真实调用点包括：

• 二进制解析上下文 parse_context.cc 用 SpanStructurallyValid 计算字符串字段中合法的剩余字节跨度，从而决定"读到哪算一个完整字段、哪段算 unknown data"；
• generated_message_tctable_lite.cc 在生成代码的字符串字段解析中调用 IsStructurallyValid 做合法性把关；
• JSON 词法器 json/internal/lexer.cc、json/internal/untyped_message.cc、text_format.cc、wire_format_lite.cc 以及扩展字段设置 extension_set_inl.h 均依赖它做 UTF-8 结构校验。

构建层面，third_party/utf8_range/BUILD.bazel 定义了三个目标：utf8_range（核心 C 库）、utf8_validity（依赖 abseil 的 C++ 头文件包装）、utf8_validity_test（gTest 单测）；CMake 用户则通过 cmake/utf8_range.cmake 参与构建，安装的 pkg-config 模板见 cmake/utf8_range.pc.cmake（Requires: absl_strings，Libs: -lutf8_validity -lutf8_range）。

2. 四种 UTF-8 校验算法与基准测试工具

README 将该目录定位为一个算法对比基准：在同一份测试数据上比较四种 UTF-8 校验实现，结论是 Range 算法在 Arm 上是最佳方案，在 x86 上与 Lemire 的位运算方案打平。四种方法及对应源文件：

算法	说明	源文件
Range 算法	用 SIMD 计算每字节"值域区间"后一次校验 16 字节	range-neon.c（NEON）、range-sse.c（SSE4）、range-avx2.c（AVX2，由社区贡献）
Range2	Range 的增强版，一次迭代处理两个 16 字节块	range2-neon.c、range2-sse.c
Lemire 方案	基于位运算的 SIMD 校验（原文为 SSE，此处含 NEON 移植与 AVX2 版）	lemire-sse.c、lemire-avx2.c、lemire-neon.c
naive	逐字节顺序校验	naive.c
lookup	基于 DFA 查找表的经典方法	lookup.c

命令行用法

按照 README 的 "About the code" 一节，完整操作流程为：

# 构建（README 注明使用 gcc-7.3 构建并测试过）
make

# 查看全部命令行选项
./utf8

# 基准测试：用默认测试文件 UTF-8-demo.txt 对比全部算法
./utf8 bench

# 基准测试：指定字符串长度（字节数）进行对比
./utf8 bench size NUM

# 正确性测试：用正/负样例测试全部算法
./utf8 test

# 只基准测试/测试某个指定算法
./utf8 bench range

其中默认测试文件即仓库中的 UTF-8-demo.txt。测试/基准的驱动逻辑在 main.c 中：它维护一张 ftab 函数分派表（naive、lookup、lemire、range、range2，开启 AVX2 编译时还会注册 lemire_avx2、range_avx2），bench 子命令以 UTF-8-demo.txt 或按 size NUM 生成的缓冲区为输入反复校验直至处理满 1GB 数据，test 子命令则遍历内置的正负样例集（见 main.c 中 pos/neg 数组：""、\xC2\x80、\xDF\xBF、\xE0\xA0\x80、\xED\x9F\x80、\xF0\x90\xBF\x80、\xF4\x8F\x88\xAA 等边界合法串，以及 \x80、\xBF、\xC0\x80 等非法串）。

3. Range 算法原理（核心章节）

3.1 基本思路

README 用三句话概括了 Range 算法的骨架：

• Load 16 bytes：一次载入 16 字节；
• Leverage SIMD to calculate value range for each byte efficiently：用 SIMD 高效地为每个字节算出它"应处的值域区间"；
• Validate 16 bytes at once：用一对比较指令把 16 字节一次性校验完。

其数学本质是：把"每个字节合法吗"转化为"每个字节落在哪个区间索引，该区间的 [min, max] 是否包含该字节值"，而区间索引的推导只需要移位、饱和减法和按字节查找表（pshufb/tbl）——全都是 SIMD 友好操作。

3.2 UTF-8 编码格式

这是 Range 算法的设计依据（源自 Unicode 标准 Table 3-7"良构 UTF-8 字节序列"，README 中完整给出）：

码点范围	首字节	第 2 字节	第 3 字节	第 4 字节
U+0000..U+007F	00..7F
U+0080..U+07FF	C2..DF	80..BF
U+0800..U+0FFF	E0	A0..BF	80..BF
U+1000..U+CFFF	E1..EC	80..BF	80..BF
U+D000..U+D7FF	ED	80..9F	80..BF
U+E000..U+FFFF	EE..EF	80..BF	80..BF
U+10000..U+3FFFF	F0	90..BF	80..BF	80..BF
U+40000..U+FFFFF	F1..F3	80..BF	80..BF	80..BF
U+100000..U+10FFFF	F4	80..8F	80..BF	80..BF

由此归纳出 UTF-8 的三条结构与四条特例：

• 根据首字节决定字符长度：C0..DF → 2 字节；E0..EF → 3 字节；F0..F4 → 4 字节；
• C0、C1、F5..FF 一律不合法；
• 第 2、3、4 字节必须落在 80..BF；
• 四个特例（加粗处）：E0 后第 2 字节须 ≥A0；ED 后第 2 字节须 ≤9F（避开代理区）；F0 后第 2 字节须 ≥90；F4 后第 2 字节须 ≤8F（避开超出 U+10FFFF 的码点）。

3.3 区间表（Range table）

区间表把"区间索引 0..15"映射到"该位置字节允许的最小/最大值"。算法的任务变成：观察输入串，为每个字节设定正确的区间索引，再统一比较。

索引	Min	Max	字节类型
0	00	7F	首字节（ASCII）
1,2,3	80	BF	第 2、3、4 字节
4	A0	BF	E0 之后的第 2 字节
5	80	9F	ED 之后的第 2 字节
6	90	BF	F0 之后的第 2 字节
7	80	8F	F4 之后的第 2 字节
8	C2	F4	首字节（非 ASCII）
9..15（NEON）	FF	00	非法（无符号语义下"≥255 且 ≤0"，永远不满足）
9..15（SSE）	7F	80	非法（有符号语义下"≥127 且 ≤-128"，永远不满足）

注意 NEON 与 SSE 对"非法区间"9..15 的取值不同，根因是两平台的比较指令符号语义不同：SSE 的 pcmpgtb/pcmpgtb 按有符号比较，0x80 即 -128；NEON 侧则用无符号 min=0xFF、max=0x00 的"倒挂区间"表达永远失败。这个细节在运行时源码 utf8_range_sse.inc 中可以原样看到：

const __m128i range_min_table =
    _mm_setr_epi8(0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, 0x90, 0x80, 0xC2, 0x7F,
                  0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F);
const __m128i range_max_table =
    _mm_setr_epi8(0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, 0xBF, 0x8F, 0xF4, 0x80,
                  0x80, 0x80, 0x80, 0x80, 0x80, 0x80);

3.4 计算每字节的区间索引（先忽略四个特例）

忽略 E0/ED/F0/F4 特例时，规则非常直接：

• 默认所有字节区间索引为 0（00..7F）；
• 非 ASCII 首字节（C0..FF）设为 8（C2..F4）；
• C0..DF 首字节的下一字节设为 1（80..BF）；
• E0..EF 首字节的后两字节依次设为 2、1；
• F0..FF 首字节的后三字节依次设为 3、2、1。

用 SIMD 高效实现这套"向后传播"，步骤如下：

1. 对 16 个输入字节，用查找表把 C0..DF 映射为 1、E0..EF 映射为 2、F0..FF 映射为 3、其余为 0，得到 first_len；
2. 再用一张表把 C0..FF 映射为 8，即所有首字节的区间索引；
3. 把 first_len 左移 1 字节，得到所有第 2 字节的索引；
4. 把 first_len 饱和减 1（3→2、2→1、1→0、0→0）后左移 2 字节，得到第 3 字节的索引；
5. 把 first_len 饱和减 2（3→1、2→0、1→0、0→0）后左移 3 字节，得到第 4 字节的索引。

四个索引向量按位或起来，即得每字节最终区间索引：

Range_index = First_Byte | Second_Byte | Third_Byte | Fourth_Byte

（按位或即可，是因为同一位置最多只有"首字节"与"第 k 字节"两种身份之一非零；两种身份同时非零恰好就是重叠错误——见 3.5。）

推演示例（README 原表，假设前面无残留数据）：

	F1	80	80	80	80	C2	80	80	...
first_len	3	0	0	0	0	1	0	0	...
First Byte	8	0	0	0	0	8	0	0	...
Second Byte	0	3	0	0	0	0	1	0	...
Third Byte	0	0	2	0	0	0	0	0	...
Fourth Byte	0	0	0	1	0	0	0	0	...
Range index	8	3	2	1	0	8	1	0	...

即 F1 80 80 80（一个合法 4 字节字符）得到索引 8,3,2,1，恰好对应区间表中的 [C2..F4]、[80..BF]、[80..BF]、[80..BF]。

这套逻辑在 utf8_range_sse.inc 中的对应实现是：用高半字节查 first_len_table（_mm_shuffle_epi8）得到 first_len；用 first_range_table 查得首字节索引 8；再用 _mm_alignr_epi8 做跨块拼接的字节移位、_mm_subs_epu8 做饱和减法，最后三次 _mm_or_si128 合并。_mm_alignr_epi8 同时拼接上一轮的 prev_first_len，从而让跨 16 字节块边界的字符也能正确传播——这正是"忽略特例"部分唯一需要跨块状态的地方。

3.5 错误处理（特例之外）

README 给出了四条错误必然被检出的论证：

• C0、C1、F5..FF 根本不在区间表索引 8 的 [C2..F4] 范围内，必被检出；
• 非法出现的孤立 80..BF 尾字节会拿到区间索引 0（00..7F），必被检出；
• 依据首字节，后续第 2/3/4 字节会被强制索引到 1/2/3（80..BF），不满足即报错；
• 非 ASCII 首字节重叠：后一个首字节会同时叠加前一个字符的"第 k 字节"身份，或出 9、10、11 等非法索引。

README 的重叠示例（F1 80 C2 90，一个 4 字节字符紧接 2 字节字符，第 3 字节处冲突）：

	F1	80	C2	90
first_len	3	0	1	0
First Byte	8	0	8	0
Second Byte	0	3	0	1
Third Byte	0	0	2	0
Fourth Byte	0	0	0	1
Range index	8	3	10	1

第 3 字节同时被标为"首字节(8)"和"第三字节(2)"，或出 10 落入非法区 9..15，错误被捕获。

3.6 特例修正：第 2 字节的区间索引调整

四个特例需要把第 2 字节的索引从"通用的 2 或 3"替换为专用的 4/5/6/7：

首字节	第 2 字节	调整前索引	正确索引	调整量
E0	A0..BF	2	4	2
ED	80..9F	2	5	3
F0	90..BF	3	6	3
F4	80..8F	3	7	4

问题因此归结为：给定 16 字节，把 E0 换成 2、ED 换成 3、F0 换成 3、F4 换成 4，其余换成 0。 朴素做法（逐值比较取掩码再与调整量相与）至少需要 8 条 SIMD 操作；利用"这四个特殊字节彼此很接近"这一事实，可以大幅压缩：

NEON 版（2 条操作）。NEON 的 tbl 指令特性：表最大 16×4 字节；索引越界时返回 0。据此预建一张 16×2 的表：table[0]=2, table[13]=3, table[16]=3, table[20]=4, 其余=0。然后把输入字节统一减去 E0（E0→0、ED→13、F0→16、F4→20），直接作为 tbl 索引查表：

• 索引小于 32 的，逐字节命中 0 或应有的调整值；
• 越界索引按 tbl 行为自动返回 0。

SSE 版（5 条操作）。SSE 的 pshufb 没有"越界返回 0"这么友好的语义：表只有 16 字节；索引第 7 位为 0 时取低 4 位（如 0x73 返回第 3 项）；第 7 位为 1 时返回 0（如 0x83 返回 0）。利用这一点，预建两张表：

• table_df[1]=2, table_df[14]=3，其余 0；
• table_ef[1]=3, table_ef[5]=4，其余 0。

步骤：先把输入字节减去 EF（E0→241、ED→254、F0→1、F4→5）得到临时索引；再分两路处理：

1. 对 E0/ED：临时索引饱和减 240（E0→1、ED→14，小于 240 的值全部归 0），查 table_df 得到调整值；
2. 对 F0/F4：临时索引饱和加 112（0x70）（F0→0x71、F4→0x75，任何大于 16 的值都会超过 128 使第 7 位置位从而查表返回 0），查 table_ef 得到调整值（0x71、0x75 的低 4 位正好是第 1、5 项）。

utf8_range_sse.inc 正是这一思路的实现：pos = shift1 - 0xEF 之后，_mm_subs_epu8(pos, 0xF0) 查 df_ee_table，_mm_adds_epu8(pos, 112) 查 ef_fe_table，两路结果相加再整体加到 range 上。其中 shift1 同样由 _mm_alignr_epi8(input, prev_input, 15) 生成，保证跨块边界的 E0/ED/F0/F4 也能被修正。

修正后的错误处理：发生首字节重叠时，调整前的索引是 9、10、11，加上调整量（0/2/3/4）后落在 9..15，仍然处于非法区间，错误依旧被检出——特例修正不会"洗白"重叠错误。

3.7 剩余字节（尾部）的处理

不足 16 字节的剩余输入不进入 SIMD 主循环，而是回退到逐字节校验——README 指出这对短尾数据实际上比 SIMD 更快。回退前需要找回"当前字符的首字节"：

• 回看最后 16 字节缓冲，最多回看 3 字节即可找到首字节：要么落在字符边界上，要么错误已在前面被检出；
• 从该首字节开始逐字节校验整个尾部。

4. 基准测试：方法与数据

README 的基准方法分三步：

1. 按 UTF-8-demo.txt 或指定缓冲区大小生成 UTF-8 测试缓冲；
2. 循环调用校验子过程，直到累计检查 1GB 字节；
3. 统计校验速度（MB/s）。

NEON（armv8a）

测试用例	naive	lookup	lemire	range	range2
UTF-demo.txt	562.25	412.84	1198.50	1411.72	1579.85
32 字节	651.55	441.70	891.38	1003.95	1043.58
33 字节	660.00	446.78	588.77	1009.31	1048.12
129 字节	771.89	402.55	938.07	1283.77	1401.76
1K 字节	811.92	411.58	1188.96	1398.15	1560.23
8K 字节	812.25	412.74	1198.90	1412.18	1580.65
64K 字节	817.35	412.24	1200.20	1415.11	1583.86
1M 字节	815.70	411.93	1200.93	1415.65	1585.40

SSE4（E5-2650）

测试用例	naive	lookup	lemire	range	range2
UTF-demo.txt	753.70	310.41	3954.74	3945.60	3986.13
32 字节	1135.76	364.07	2890.52	2351.81	2173.02
33 字节	1161.85	376.29	1352.95	2239.55	2041.43
129 字节	1161.22	322.47	2742.49	3315.33	3249.35
1K 字节	1310.95	310.72	3755.88	3781.23	3874.17
8K 字节	1348.32	307.93	3860.71	3922.81	3968.93
64K 字节	1301.34	308.39	3935.15	3973.50	3983.44
1M 字节	1279.78	309.06	3923.51	3953.00	3960.49

（以上为 README 记录的原始测试数据，MB/s；结果与测试时的 CPU 型号相关。）

两张表共同印证了 README 的结论：

• Arm 上 Range/range2 全面胜出，比次优的 lemire 快约 25%～33%；
• x86 上 range 与 lemire 基本持平，长字符串（≥1K）场景 range2 略优；
• 32/33 字节这类"恰好一个块±1"的短串上各算法波动最大，说明跨块状态传递的代价在小输入下占比更高；
• naive 与 lookup 在 SIMD 平台被拉开一个数量级差距，说明纯查表/逐字节方案不适合高频校验路径。

5. 测试设计：如何覆盖边角情况

README 的测试方法论本身值得借鉴，核心思想是用"平移窗口"把每个字节都逼进 SIMD 处理器的每个相位：

正向用例（Positive cases）

1. 准备一组正确的 UTF-8 字符（覆盖 1/2/3/4 字节及边界码点，如 main.c 中的 \xE0\xA0\x80、\xED\x9F\x80、\xF4\x8F\x88\xAA）；
2. 逐个校验这些正确字符；
3. 构造长串：从第一个字符起循环拼接至 1024 字节 → 校验；左移 1 字节再校验 1025 字节串；再移 2 字节……直到移 16 字节（1040 字节串）。一个 16 字节周期恰好覆盖 SIMD 块的所有对齐相位；
4. 从第二个字符起重复第 3 步；
5. 从第三个字符起重复第 3 步；
6. 依此类推（对每个起始字符重复一遍）。

负向用例（Negative cases）

1. 准备坏字符与坏串，重点覆盖三类边界：单字节坏字符、跨越 16 字节块边界的坏字符、跨越"最后 16 字节与剩余字节"边界的坏字符（后两类专门针对跨块状态传递与尾部回退逻辑）；
2. 长串测试：按正向用例同样方式准备合法长串 → 在尾部追加坏字符 → 每轮左移 1 字节 → 逐位移位后校验，期望每个错位都报出错误。

仓库内 main.c 的 prepare_test_buf 正是"循环拼接到 1024 字节"的实现，而 utf8_validity_test.cc 以 gTest 形式对 utf8_range_IsValid / utf8_range_ValidPrefix 做了等价的回归验证；此外还有模糊测试 fuzz/utf8_validity_fuzzer.cc（配套字典 fuzz/utf8_fuzzer.dict）持续喂入畸形字节流。

6. 运行时实现：从 README 原理到 protobuf 生产代码

README 描述的基准实现（range-sse.c 等）用于对比，而 protobuf 实际编译进运行库的是经过 Google 改造的包装层 utf8_range.c。文件头注释明确说明：它是 range-sse 算法的包装，"关键差异是先尽可能多地跳过 ASCII 符号，再回退到 range-sse 算法"，改动"主要是为了诱导 clang 生成最优代码"。其主流程（utf8_range.c）：

1. ASCII 快速通道：utf8_range_SkipAscii 每 8 字节取一次非对齐 64 位字，与 0x8080808080808080 做与运算判断整 8 字节是否全是 ASCII，是则直接前移。注释指出"绝大多数被校验的字符串只含 1 字节码点"，所以这条通道对真实负载至关重要；
2. 短串回退：跳过 ASCII 后剩余不足 16 字节时，直接走逐字节的 utf8_range_ValidateUTF8Naive（与 README "Handling remaining bytes" 的策略一致：短尾逐字节反而更快）；
3. SIMD 主循环：仅在定义了 __SSE4_1__ 或 __ARM_NEON && __ARM_64BIT_STATE 时编译，通过条件 include 引入 utf8_range_sse.inc 或 utf8_range_neon.inc，否则整体回退 naive 实现——这意味着在既无 SSE4.1 也无 ARM64 NEON 的平台，库仍可用，只是没有 SIMD 加速；
4. 尾部收尾：SIMD 循环结束后，用 utf8_range_CodepointSkipBackwards 从上一轮 16 字节块的最后 4 字节中回看最多 3 字节找回首字节，再从那里逐字节校验剩余部分，与 README 3.7 节的描述逐句对应。

还有一个值得注意的工程细节：utf8_range_ValidPrefix 与 utf8_range_IsValid 共用同一核心（return_position 参数切换）。在需要返回前缀长度的路径上，utf8_range_sse.inc 发现错误块时会 break 提前跳出主循环以精确定位错误位置，源码注释标注这一条件分支带来约 5% 的性能开销——即"纯判合法"比"定位合法前缀"更快，调用方（如 parse_context.cc 中解析 unknown/残留数据时的 SpanStructurallyValid 调用）天然需要后者。

需要说明的边界：utf8_range_IsValid 校验的是结构合法性（structural validity），即字节序列是否良构 UTF-8，并不校验码点是否被 Unicode 定义（BMP 内的未分配码点、以及经 E0/ED/F0/F4 特例收敛后的合法代理区写法等均按结构规则处理）；README 的"Code breakdown"一节引用的逐步处理示意图在原文中以外部图片形式给出，本仓库未随附该图，但其内容与 3.4 节的推演示例一致。

7. 小结与使用注意

• 想理解算法：按 3.2 → 3.3 → 3.4 → 3.6 的顺序读，核心是"首字节查表得 first_len → 移位/饱和减传播出 2/3/4 字节索引 → 或合并 → 特例查表修正 → min/max 双表比较"，每一步都能一一对应到 utf8_range_sse.inc 的具体 intrinsics。
• 想复现基准：在 third_party/utf8_range 下 make 后运行 ./utf8 bench、./utf8 bench size NUM、./utf8 test（AVX2 版需编译器开启 -mavx2，range2 仅 NEON/SSE 存在）。
• 想在 protobuf 中使用：Bazel 目标为 //third_party/utf8_range:utf8_validity（C++ 包装）与 :utf8_range（C 核心）；CMake 侧由 cmake/utf8_range.cmake 构建安装，链接 utf8_validity/utf8_range 两个库并依赖 absl_strings。
• 注意事项：SIMD 路径要求 SSE4.1 或 ARMv8-A 64 位 NEON，其余平台自动回退逐字节实现，功能不受影响；对 <16 字节的输入直接走 naive 路径，这是刻意的设计而非缺陷；IsValid 与 ValidPrefix 语义不同（后者多付出约 5% 的前缀定位开销），选择接口时留意调用场景。