深入解析 Fast UTF-8 Validation with Range Algorithm:基于 SIMD 的 UTF-8 快速校验算法
深入解析 Fast UTF-8 Validation with Range Algorithm:基于 SIMD 的 UTF-8 快速校验算法
Range 算法是一种利用 SIMD(单指令多数据)指令集对 UTF-8 字符串进行快速校验的全新算法,同时提供 NEON(armv8a)、SSE4 与 AVX2 三种实现,并通过“范围表 + 查表法”将 16 字节的输入一次性完成合法性判定。在 MongoDB 仓库中,该算法以独立的 utf8_range 组件形式内嵌于 protobuf 第三方依赖(src/third_party/protobuf/dist/third_party/utf8_range),用于 protobuf 解析与序列化链路中字符串字段的结构合法性校验。读完本文,你将掌握 Range 算法从 UTF-8 编码格式到范围表设计、SIMD 指令实现、边界与错误处理、基准测试与回归测试的完整技术细节,并能在自己的项目中复现其基准与正确性验证。
一、算法概述:Range 与 Lemire、Lookup、Naive 的对比
Range 算法在 x86 与 Arm 两大平台上一共对比了四种 UTF-8 校验方法,覆盖从最简单到最复杂的不同实现层次:
| 实现 | 文件 | 说明 |
|---|---|---|
| Range 算法 | range-neon.c、range-sse.c、range-avx2.c | NEON / SSE4 / AVX2 三个版本,单次迭代处理一个 16 字节块 |
| Range2 算法 | range2-neon.c、range2-sse.c | 单次迭代处理两个 16 字节块的增强版 |
| Lemire 的 SIMD 实现 | lemire-sse.c、lemire-avx2.c、lemire-neon.c | 著名的 fastvalidate-utf-8 方案移植 |
| 朴素逐字节实现 | naive.c | 逐字节校验,作为性能基线 |
| 查表法(DFA) | lookup.c | 基于 Höhrmann 的 DFA 查表法 |
README 中给出的 Benchmark 结论是:Range 算法是 Arm 平台上的最优解,而在 x86 上可以达到与 Lemire 方案同等的性能。range2 变体(一次处理两块)在绝大多数测试规模下又能把 Range 算法再推高几个百分点。
从基准测试的驱动代码看(main.c),bench 子命令会以“循环校验直到累计检查满 1G 字节”的方式计算吞吐量:先根据测试文件或指定缓冲区大小生成 UTF-8 测试缓冲,然后反复调用校验子程序,最后以 size / time 得出 MB/s 的带宽指标。
二、构建与命令行用法
构建与使用方式非常简单,README 中给出三条核心命令,在仓库中均有对应的代码实现:
# 1. 编译。已用 gcc-7.3 构建并通过测试
make
# 2. 查看全部命令行选项
./utf8
# 3. 基准测试:用默认测试文件 UTF-8-demo.txt 测试所有算法
./utf8 bench
# 4. 基准测试:指定字符串大小(单位为字节,合法范围 1 ~ 67108864,即 64M)
./utf8 bench size NUM
# 5. 正确性测试:用正负用例测试所有算法
./utf8 test
# 6. 只针对某一个算法测试或基准,例如 range
./utf8 bench range
从 main.c 的 usage() 可以看到完整参数约定:./utf8 test [alg] 测试全部或单个算法,./utf8 bench [alg] 基准全部或单个算法,./utf8 bench size NUM 用指定缓冲区大小做基准,其中 NUM 必须在 1 ~ 67108864(64M)之间,超出会被判为非法参数。可选的算法名为 naive、lookup、lemire、range、range2,若编译时定义了 __AVX2__ 还会追加 lemire_avx2、range_avx2。
基准流程内部(main.c)的细节是:
- 由测试文件或指定 size 生成测试缓冲;
- 在一个循环中反复调用校验子程序,直到累计校验 1G 字节;
- 用
gettimeofday统计耗时,计算校验吞吐 MB/s,并打印time、data、BW三个指标。
默认测试文件为仓库自带的 UTF-8-demo.txt,在 bench size NUM 模式下则会用固定四字节序列 \xF0\x90\xBF\x80(U+10300,属于 4 字节码位)循环填充缓冲,尾部不足 4 字节处以 0x7F(ASCII)补齐(见 main.c)。
三、基准测试结果解读(MB/s)
README 在 x86(E5-2650,SSE4)与 Arm(armv8a,NEON)两个平台各测了一组数据,下表完整摘录,加粗为每个测试规模下的最优值。
NEON(armv8a)
| 测试用例 | naive | lookup | lemire | range | range2 |
|---|---|---|---|---|---|
| UTF-8-demo.txt | 562.25 | 412.84 | 1198.50 | 1411.72 | 1579.85 |
| 32 bytes | 651.55 | 441.70 | 891.38 | 1003.95 | 1043.58 |
| 33 bytes | 660.00 | 446.78 | 588.77 | 1009.31 | 1048.12 |
| 129 bytes | 771.89 | 402.55 | 938.07 | 1283.77 | 1401.76 |
| 1K bytes | 811.92 | 411.58 | 1188.96 | 1398.15 | 1560.23 |
| 8K bytes | 812.25 | 412.74 | 1198.90 | 1412.18 | 1580.65 |
| 64K bytes | 817.35 | 412.24 | 1200.20 | 1415.11 | 1583.86 |
| 1M bytes | 815.70 | 411.93 | 1200.93 | 1415.65 | 1585.40 |
SSE4(E5-2650)
| 测试用例 | naive | lookup | lemire | range | range2 |
|---|---|---|---|---|---|
| UTF-8-demo.txt | 753.70 | 310.41 | 3954.74 | 3945.60 | 3986.13 |
| 32 bytes | 1135.76 | 364.07 | 2890.52 | 2351.81 | 2173.02 |
| 33 bytes | 1161.85 | 376.29 | 1352.95 | 2239.55 | 2041.43 |
| 129 bytes | 1161.22 | 322.47 | 2742.49 | 3315.33 | 3249.35 |
| 1K bytes | 1310.95 | 310.72 | 3755.88 | 3781.23 | 3874.17 |
| 8K bytes | 1348.32 | 307.93 | 3860.71 | 3922.81 | 3968.93 |
| 64K bytes | 1301.34 | 308.39 | 3935.15 | 3973.50 | 3983.44 |
| 1M bytes | 1279.78 | 309.06 | 3923.51 | 3953.00 | 3960.49 |
值得注意的规律:
- Arm 上 Range 全面胜出:在全部 7 个测试规模中,range2 均为最优;lookup 在 Arm 上反而慢于 naive,而 Range 相比 Lemire 有约 18%~42% 的提升(视字符串规模而定)。
- x86 上 Range 与 Lemire 互有胜负:短串(32 bytes)Lemire 领先,而 33/129 bytes 时 Range 反超,长串上两者基本持平、range2 微弱领先。这与 README“Range 在 x86 上达到与 Lemire 同等性能”的结论一致。
- SIMD 对短串的收益有限甚至为负:32 bytes 时 naive 反而高达 1135 MB/s,说明 SIMD 初始化与对齐开销在小输入上不划算——这也是下文“剩余字节回退到逐字节校验”设计的依据。
四、Range 算法核心原理
Range 算法的基本思想可以概括为三步:
- 一次加载 16 字节;
- 借助 SIMD 指令高效地为每个字节计算出其合法的“值域”;
- 一次性校验 16 字节是否全部落在各自的值域内。
4.1 UTF-8 编码格式(Well-Formed UTF-8 Byte Sequences)
Range 算法依据 Unicode 6.0 规范(Table 3-7)中“Well-Formed UTF-8 Byte Sequences”定义合法编码。README 完整摘录了该表:
| Code Points | First Byte | Second Byte | Third Byte | Fourth Byte |
|---|---|---|---|---|
| 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 |
从中可归纳出四条校验规则:
- 首字节决定了字符长度:
C0..DF为 2 字节、E0..EF为 3 字节、F0..F4为 4 字节; C0、C1、F5..FF属于非法首字节,永不出现;- 第二、三、四字节必须落在
80..BF; - 存在四个特例首字节(表中加粗斜体):
E0、ED、F0、F4之后的第二字节范围被收紧,分别是A0..BF、80..9F、90..BF、80..8F。
4.2 范围表(Range Table)
范围表把“范围索引 0 ~ 15”映射到每个索引允许的最小值与最大值。算法的任务就是观察输入串,识别模式并为每个字节设置正确的范围索引,最后统一校验:
| Index | Min | Max | Byte type |
|---|---|---|---|
| 0 | 00 | 7F | First Byte, ASCII |
| 1,2,3 | 80 | BF | Second, Third, Fourth Bytes |
| 4 | A0 | BF | Second Byte after E0 |
| 5 | 80 | 9F | Second Byte after ED |
| 6 | 90 | BF | Second Byte after F0 |
| 7 | 80 | 8F | Second Byte after F4 |
| 8 | C2 | F4 | First Byte, non-ASCII |
| 9..15 (NEON) | FF | 00 | 非法:无符号字节 ≥ 255 且 ≤ 0 |
| 9..15 (SSE) | 7F | 80 | 非法:有符号字节 ≥ 127 且 ≤ -128 |
索引 9~15 被刻意设计为“空范围”(min > max),因此任何落到这些索引上的字节都会必然触发越界错误——这正是错误检测的基石。SSE 与 NEON 对非法索引的 min/max 取值不同(7F/80 vs FF/00),是为了分别配合有符号与无符号比较指令的语义。
4.3 计算字节范围(忽略特例)
先忽略 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 高效实现上述操作,README 给出了关键技巧——用查表 + 移位 + 饱和减法一次性算出四种索引:
- 对 16 个输入字节,用查表法把
C0..DF映射为 1、E0..EF映射为 2、F0..FF映射为 3、其余映射为 0,得到first_len; - 把
C0..FF映射为 8,得到各首字节的范围索引; first_len右移 1 字节,得到第二字节的范围索引;first_len饱和减 1(3→2, 2→1, 1→0, 0→0)后再右移 2 字节,得到第三字节的范围索引;first_len饱和减 2(3→1, 其余→0)后再右移 3 字节,得到第四字节的范围索引。
README 给出了完整示例(假设前面没有残留数据):
| Input | 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 | ... |
最终每个字节的范围索引由四者按位或得到:
Range_index = First_Byte | Second_Byte | Third_Byte | Fourth_Byte
SSE 版源码中的注释(utf8_range_sse.inc)给出了一个更丰富的 16 字节示例:输入 C3 80 68 E2 80 20 A6 F0 A0 80 AC 20 F0 93 80 80,最终得到索引序列 8 1 0 8 2 1 0 8 3 2 1 0 8 3 2 1——可见索引值完全按照字符长度对后续续字节进行标注。
错误处理
C0、C1、F5..FF不在范围表内,必然被检出;- 非法续字节
80..BF会被标成索引 0(00..7F),从而被检出; - 基于首字节,对应的第二、三、四字节分别获得索引 1/2/3,强制其必须落在
80..BF; - 若两个非 ASCII 首字节发生重叠,算法会把后一个首字节的范围索引抬升到 9、10、11 等非法区间而自动报错。README 的例子:
| Input | 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 |
这里索引 10 表示错误——C2 作为首字节出现在前一个 4 字节字符的续字节位置上,属于重叠的非法编码。
4.4 特例首字节的第二字节范围调整
四个特例首字节会使第二字节的合法范围收紧,因此需要额外调整:
| First Byte | Second Byte | Before adjustment | Correct index | Adjustment |
|---|---|---|---|---|
| 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。
朴素的 SIMD 做法是逐字节比较 + 掩码求和:分别把 16 字节与 E0/ED/F0/F4 比较得到掩码(相等为 FF,否则 00),再与对应调整值做与运算后累加,至少需要 8 条指令。由于这四个特殊字节在数值上彼此接近,用查表法可以大幅压缩指令数。
NEON:两步完成
NEON 的 tbl 指令非常适合查表:
- 表最大可达 16×4 字节;
- 索引越界时返回 0。
利用这两点,问题可缩减到两条操作:
- 预建 16×2 查表:
table[0]=2(E0)、table[13]=3(ED)、table[16]=3(F0)、table[20]=4(F4)、其余为 0; - 输入字节减去
E0(E0→0, ED→13, F0→16, F4→20); - 以减后的字节为索引直接查表得到调整值:小于 32 的索引要么得到 0 要么得到正确的调整值,越界索引按
tbl的语义返回 0。
实际实现见 utf8_range_neon.inc:range_adjust_tbl_data 用 16×2 交错布局(vld2q_u8 加载),第 1 列对应 E0..EF 的调整(E0→2、ED→3),第 2 列对应 F0..FF 的调整(F0→3、F4→4),随后 vsubq_u8(shift1, const_e0) 后直接用 vqtbl2q_u8 查表。
SSE:五步完成
SSE 的 pshufb 不如 NEON tbl 友好:
- 表只能是 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)得到临时索引; - 求
E0、ED的调整:临时索引饱和减 240(E0→1, ED→14,小于 240 的值归 0),再用结果查table_df; - 求
F0、F4的调整:临时索引饱和加 112(0x70)(F0→0x71, F4→0x75,大于 16 的值第 7 位都会置位),再用结果查table_ef,按pshufb的语义,索引0x71、0x75返回第 1、5 个元素。
SSE 实现中的两表即 utf8_range_sse.inc 的 df_ee_table(df_ee_table[1]→E0、df_ee_table[14]→ED)与 ef_fe_table(ef_fe_table[1]→F0、ef_fe_table[5]→F4),后续用 _mm_subs_epu8(饱和减)、_mm_adds_epu8(饱和加)与两次 _mm_shuffle_epi8 完成调整。
调整后的错误处理
对于重叠的非 ASCII 首字节,调整前的范围索引为 9、10、11;调整(加 2、3、4 或 0)后变为 9 ~ 15,依然落在范围表的非法区间(min > max),因此错误必然被检出。SSE 注释中的例子:F1 80 C2 90 → 8 3 10 2,其中 10 指示错误。
4.5 剩余字节的处理
对于不足 16 字节的剩余输入,算法回退到逐字节的朴素校验——对这么短的尾巴,朴素方式反而比 SIMD 更快:
- 回看最近 16 字节的缓冲以找到真正的首字节,最多需要回看 3 字节(4 字节字符的最长续字节数)。若回看过程中恰好落在字符边界,则说明要么本就处于边界、要么前面已有被检出的错误;
- 从找到的首字节开始逐字节校验字符串。
SSE 实现中,循环结束后通过 utf8_range_CodepointSkipBackwards(_mm_extract_epi32(prev_input, 3)) 回退到上一个码位边界,再调用 utf8_range_ValidateUTF8Naive 校验尾部;错误标志 error 累积的 _mm_testz_si128 判定决定整个串是否有效(utf8_range_sse.inc)。NEON 版本逻辑相同,只是用 vgetq_lane_s32 + vmaxvq_u32 完成相同的检查(utf8_range_neon.inc)。
五、生产级封装:utf8_range 的公共 API
在 MongoDB 仓库内嵌的这份代码中,上游 README 描述的是独立仓库的评测/演示形态,而其“产品化”形态是 Google 改造后的包装层 utf8_range.c。它对外只暴露两个 C API(utf8_range.h):
// 返回 1 表示整个字节序列是合法 UTF-8,否则返回 0
int utf8_range_IsValid(const char* data, size_t len);
// 返回 str 中全部为结构合法 UTF-8 的前缀的字节长度
size_t utf8_range_ValidPrefix(const char* data, size_t len);
包装层的设计要点:
- ASCII 快速通道:
utf8_range_SkipAscii每 8 字节一次用UnalignedLoad64读取 64 位,检查高位置 1 的掩码0x8080808080808080是否为零来批量跳过纯 ASCII 段(utf8_range.c)。这是针对“绝大多数真实字符串都是纯 ASCII”这一观察的刻意优化。 - SIMD 与朴素的分界点:
utf8_range_Validate在 ASCII 跳过之后,若剩余不足 16 字节则直接走朴素校验;否则在__SSE4_1__(x86)或__ARM_NEON && __ARM_64BIT_STATE(Arm 64)编译条件下进入 SIMD 路径(utf8_range.c)。 - 平台分派:SIMD 内核按编译宏分别内联 utf8_range_sse.inc 与 utf8_range_neon.inc,两者共用同一套朴素校验与回退逻辑。
- 朴素校验本身就是完整实现:
utf8_range_ValidateUTF8Naive(utf8_range.c)按 1/2/3/4 字节码位的规则逐一验证,并把 README 中E0/ED/F0/F4四个特例直接编码为显式分支(如byte1 == 0xE0 && byte2 >= 0xA0),既是 SIMD 路径的兜底,也是无 SIMD 平台上的完整实现。
在上层,Google 还提供了 C++ 包装头 utf8_validity.h,把两个 C API 封装为接受 absl::string_view 的 IsStructurallyValid 与 SpanStructurallyValid,并以 Bazel 目标 utf8_range、utf8_validity、utf8_validity_test 组织(见 BUILD.bazel)。
在 protobuf 解析链路中的实际用途
在 protobuf 中,utf8_range 被用于字符串字段的结构合法性校验。以 parse_context.cc 为例,SpanStructurallyValid 与 IsStructurallyValid 被用于解析片段时定位首个非法字节位置、以及校验字符串字段是否整体合法(如第 275、287、294、312、538 行)。这意味着 Range 算法实际支撑着 protobuf 反序列化时对 UTF-8 字段的快速验证——这正是它被引入 protobuf 第三方依赖的原因。
六、测试设计:正向与负向用例
README 强调“测试用例必须尽可能覆盖边界情况”,并给出了系统化的正负用例设计方法。
正向用例
- 准备若干正确字符;
- 校验这些正确字符;
- 校验长字符串:
- 从第一个字符开始循环拼接直到 1024 字节;
- 校验 1024 字节串;
- 每次前移 1 字节,校验 1025 字节串;
- 每次前移 2 字节,校验 1026 字节串;
- …… 依次前移到 16 字节,校验 1040 字节串;
- 重复步骤 3,从第二个字符起头测试;
- 重复步骤 3,从第三个字符起头测试;
- 依次类推。
负向用例
- 准备坏字符与坏字符串:
- 单个坏字符;
- 跨越 16 字节边界的坏字符;
- 跨越“最后 16 字节”与“剩余字节”边界的坏字符;
- 长字符串测试:
- 按正向用例准备正确长串;
- 追加坏字符;
- 每轮前移 1 字节;
- 校验每个移位版本。
仓库中的实际测试实现
在评测程序 main.c 中,test_manual 实现了上述策略:
- 正例 token 集(
pos[]):覆盖空串、\x00、\x7F等 ASCII,2 字节\xC2\x80/\xDF\xBF,3 字节\xE0\xA0\x80/\xED\x9F\x80(注意刻意选在 ED 的 9F 边界内)等,4 字节\xF0\x90\xBF\x80、\xF4\x8F\x88\xAA; - 负例 token 集(
neg[]):非法裸续字节\x80/\xBF、非最短形式\xC0\x80/\xC1\x00/\xE0\x80\x80/\xF0\x80\x80\x80、越界首字节\xF4\x90\x88\xAA、代理区\xED\xA0\x80,以及特意构造的跨 16 字节边界坏字符(如 32、33、34、35 字节长度的用例); - 所有 token 会按“从每个起始字符开始、循环填充到 1024 字节、再逐字节移位到 1040 字节”的方式全量验证,负例则采用“正确长串 + 追加一个错误 token + 逐字节移位”的方式,保证 SIMD 块对齐、块间边界、尾部回退路径都被覆盖。
此外,仓库还提供基于 libFuzzer 的持续模糊测试入口 fuzz/utf8_validity_fuzzer.cc,对 IsStructurallyValid 与 SpanStructurallyValid 两个 API 做随机输入压力测试,配套 fuzz/BUILD.bazel 与 UTF-8 语料(utf8_corpus_durst.txt、utf8_corpus_kuhn.txt)。
在 C++ 单测 utf8_validity_test.cc 中,SpanStructurallyValid 与 IsStructurallyValid 的用例覆盖了:
- 合法串:ASCII、内嵌
\0的 4 字节串、2/3/4 字节码位; - 坏字符/截断串:
abc\x80、abc\xc2(2 字节截断)、ab\xe2\x81(3 字节截断)、a\xf2\x81\x81(4 字节截断); - 非最短形式(overlong encoding):
\xc0\x80、\xc1\xbf、\xe0\x80\x80、\xe0\x9f\xbf、\xf0\x80\x80\x80、\xf0\x83\xbf\xbf全部应判非法; - 代理区:
\xED\xA0\x80(U+D800)与\xED\xBF\xBF(U+DFFF)应判非法; - 越界码位:
\xF4\xBF\xBF\xBF应判非法; - 一个历史回归用例:
\xc7\xc8\xcd\xcb这一非法序列曾在 2006 年 7 月导致 GWS 崩溃,测试明确要求其被判非法。
这些用例与 README 中“正向/负向”测试方法论一一对应,可直接作为接入方正确性验证的参考清单。
七、代码逐块拆解(Code Breakdown)
README 用一张流程图展示 16 字节输入的处理步骤,对应实现为 range-neon.c。结合 SSE 源码(utf8_range_sse.inc),核心流水线可归纳为:
- 加载与高半字节提取:
_mm_loadu_si128无对齐加载 16 字节,_mm_srli_epi16(input, 4)与掩码0x0F相与得到每个字节的高 4 位(high_nibbles)。 - first_len 查表:用
_mm_shuffle_epi8(first_len_table, high_nibbles)得到字符长度减 1 的映射(0x00~0xBF→0, 0xC0~0xDF→1, 0xE0~0xEF→2, 0xF0~0xFF→3),即first_len_table = {0,...,0,1,1,2,3}。 - 首字节索引:
first_range_table = {0,...,0,8,8,8,8}查表,把C0..FF映射为索引 8。 - 第二/三/四字节索引:利用
_mm_alignr_epi8做字节级右移拼接,把first_len与其前一块的prev_first_len组合:移位 1 字节得到第二字节索引;_mm_subs_epu8(饱和减 1)后移位 2 字节得到第三字节索引;饱和减 2 后移位 3 字节得到第四字节索引。 - 特例调整:将
input与prev_input拼接后移位 1 字节得到shift1(即“前一块最后一个字节 + 本块前 15 字节”),减去0xEF后分别做饱和减 240 与饱和加 112,查df_ee_table与ef_fe_table并把两次调整值累加到range2,再_mm_add_epi8(range, range2)。 - 范围校验:用最终
range查range_min_table/range_max_table得到每个字节的合法区间,再用_mm_cmplt_epi8/_mm_cmpgt_epi8比较输入字节是否越界。return_position模式下发现首个错误立即break(约有 5% 的性能开销),否则把错误累积进error掩码、循环结束后统一判定。 - 尾部回退:循环结束后回退到上一个码位边界(
CodepointSkipBackwards),对剩余字节走朴素校验,并在需要时返回首个非法位置。
NEON 版本(utf8_range_neon.inc)逻辑与 SSE 几乎一致,唯一区别在范围调整步骤:NEON 的 vqtbl2q_u8 直接支持更大的查表,因此用一条 vsubq_u8 + 一次查表即可完成特例调整,比 SSE 的五步方案更简洁。
八、在 MongoDB 仓库中如何查看与验证
该组件作为 protobuf 的第三方依赖存在于 MongoDB 仓库中,读者可以按以下方式在本地查看与验证:
# 查看组件目录结构与全部源码
ls src/third_party/protobuf/dist/third_party/utf8_range/
# 阅读算法说明(本文对应文档)
# 见 src/third_party/protobuf/dist/third_party/utf8_range/README.md
# 以 Bazel 运行 C++ 单测(需在具备 Bazel 与依赖的环境中)
# 目标定义见 BUILD.bazel 中的 utf8_validity_test
bazel test //third_party/utf8_range:utf8_validity_test
# 使用独立评测程序(在组件目录下)
make
./utf8 test
./utf8 bench
./utf8 bench size 1024
./utf8 bench range
需要说明的是:
- 依赖该库的 protobuf 调用方(如 parse_context.cc)需要在编译时具备
__SSE4_1__(x86)或__ARM_NEON && __ARM_64BIT_STATE(Arm 64)才能启用 SIMD 快路径;无 SIMD 平台上自动回退到纯 C 的朴素实现,正确性不受影响,仅吞吐下降。 - 文章引用的基准数据来自上游 README 记录的原始环境(gcc-7.3、armv8a 与 E5-2650),在不同编译器、CPU 微架构与 SIMD 支持级别下,具体数值会变化,但算法层面的相对结论(Arm 上 Range 占优、x86 上与 Lemire 持平)具有参考意义。
九、总结
Range 算法用一个“16 字节查表 + 移位 + 饱和运算”的 SIMD 流水线,把 UTF-8 结构校验从逐字节的分支判断压缩为几条向量指令,并通过“非法索引空范围”这一巧妙设计统一了普通错误与首字节重叠错误的检测;对不足 16 字节的尾巴则回退到朴素校验,兼顾了短串场景的效率。它在 Arm NEON 上通过 tbl 的两步特例调整成为基准测试中的最优方案,在 x86 SSE4/AVX2 上也与业界公认的 Lemire 方案旗鼓相当。而在 MongoDB 仓库内,这套算法已被包装为稳定的 C/C++ API 并内嵌于 protobuf 解析链路,成为字符串字段 UTF-8 合法性校验的底层加速引擎——理解了 Range 算法,也就理解了现代数据库与序列化框架中“高吞吐文本校验”的典型工程范式。