Bijou64：一种变量长度整数编码的深度解读

背景

在二进制协议的设计中，如何高效地编码整数是一个经典问题。许多协议需要一种紧凑的方式来表示那些“通常很小，但偶尔很大”的整数。变量长度整数编码（Variable-length integer encodings，简称 varints）正是为了解决这一问题而诞生的。

长期以来，业界广泛使用的 LEB128 编码因其简洁性而被大量采用。然而，LEB128 及其类似的设计往往将“规范形式”（Canonicality）视为事后补充——即通过解码器中的运行时检查来强制规范，而非通过编码结构本身来保证。这种设计在安全性上存在隐患，尤其是在涉及数字签名和数据压缩的场景中，非规范编码可能导致签名验证失败或压缩效率低下。

此外，历史上曾发生过因未能正确实施规范检查而导致的安全漏洞，例如在 ASN.1（X.509 证书、LDAP 等广泛依赖的基础设施背后的抽象语法标记）中出现的规范攻击。这些攻击利用了实现中可被删除或优化的检查逻辑，使得协议在对抗性输入下 silently degrade（静默降级）。

Bijou64 正是在这样的背景下被提出。它并非旨在单纯追求极致的编码速度，而是在设计约束下意外获得了一种“不得不少做工作”的编码结构。其核心目标是消除多义性，从结构上保证每个整数只有一种唯一的编码方式，从而在不增加额外检查开销的前提下，提升安全性和性能。

核心内容

Bijou64 是一种针对无符号 64 位整数（u64）设计的变量长度整数编码方案。它通过两个关键技巧消除了 LEB128 等多义编码的问题，实现了“构造即规范”（Canonical by Construction）。

1. 消除多义性：构造即规范

在 LEB128 中，数字 0 可以编码为 0x00，也可以编码为 0x80 0x00、0x80 0x80 0x00 等任意数量的 0x80 后跟一个零字节。这种多义性对于需要精确字节序列的场景（如数字签名）是致命的，因为额外的 0x80 会导致签名完全不同。

Bijou64 通过以下机制确保每个数值有且仅有一种编码：

• 首字节双重职责（First Byte Double Duty）：

  • 第一个字节直接表示 0–247 的数值。例如，0x42 直接解码为 66。
  • 如果第一个字节的值在 248–255 之间，它不再表示数值本身，而是作为一个“标签”（Tag），指示后续需要读取多少个字节来表示数值。
  • 优势：解码器在读取第一个字节后，即可立即知道需要分配多少内存（O(1) 复杂度），无需像 LEB128 那样持续扫描直到找到没有延续位的字节（O(n) 复杂度）。

• 偏移量机制（Offsets）：

  • 仅靠标签不足以保证规范形式。例如，在 LEB128 中，0xF8 0x00 可能被解释为 0，但这与 0x00 冲突。
  • Bijou64 引入了偏移量。当使用标签时，后续字节的数据部分会加上一个基于标签值的偏移量。
  • 例如，标签 0xF8（248）表示后续跟随 1 个字节。此时，后续字节的值会被加上 248 的偏移。因此，0xF8 0x00 解码为 0x00 + 248 = 248，而不是 0。数字 0 依然唯一地由 0x00 表示。
  • 这种偏移量随着标签值（即后续字节数量）的增加而按可预测的模式递增。实际上，这可以看作是一个基于首字节的查找表。

• 边界处理：

  • 对于最大的 9 字节编码（标签 + 8 个数据字节），由于偏移量的存在，理论上可以表示大于 $2^{64}$ 的数值。但由于 Bijou64 的目标是 u64，解码器会进行手动检查，确保值在 $2^{64}$ 以下。这并非规范性问题，而是范围裁剪，确保在范围内的每个数字仍保持唯一编码。

2. 性能基准测试

Bijou64 在解码和编码速度上均表现出色，尤其是在处理大规模或对抗性数据时。

• 解码性能：

  • 整体速度：Bijou64 的解码速度比 LEB128 快 2 到 10 倍。
  • 小数值：对于编码为单字节的 LEB128 小数值，Bijou64 快约 2 倍。
  • 大数值：对于迫使 LEB128 扫描多个延续位的大数值，Bijou64 快 8–10 倍。
  • 对抗性分布：在均匀分布的完整 u64 数据集（最具对抗性的基准测试场景）中，Bijou64 处理 4096 个值仅需约 3 µs（每个值约 0.75 ns），而 LEB128 需要约 30 µs（每个值约 7.3 ns）。
  • 稳定性：Bijou64 的累积分布函数（CDF）几乎垂直，表明其性能波动极小。相比之下，LEB128 的曲线向右倾斜，因为其性能依赖于延续位扫描的长度，分支预测器难以锁定模式。

• 编码性能：

  • 总体而言，Bijou64 的编码速度也更快。
  • 例外情况：在“小数值”分布（248 – 65,535）中，LEB128 以约 1.24 倍的速度略微领先。

• 编码大小：

  • Bijou64 并非在所有分布下都是最紧凑的 varint。但在现实工作负载中，Bijou64 和 LEB128 产生的字节数差异仅在百分之几以内。

3. 安全优势：免费的规范检查

Bijou64 最大的优势在于其安全性是“免费”获得的。

• LEB128 的困境：在 LEB128 中，规范检查是额外的逻辑工作。如果开发者忘记添加、优化掉了该检查，或者该检查未被移植，协议的安全性就会降级。这种检查通常只在对抗性输入下才会暴露出问题，而这类测试很少包含在常规测试套件中。
• Bijou64 的优势：对于 Bijou64，规范解码就是解码本身。格式结构保证了唯一性，无需额外的规范检查逻辑。这意味着无论输入如何，解码器都不会接受非规范编码，从而从根本上杜绝了因规范检查缺失而导致的安全漏洞。

关键要点

• 结构即安全：Bijou64 通过编码结构本身保证每个整数只有一种唯一的表示形式，消除了对运行时规范检查的依赖，从而防止了因检查缺失或优化导致的安全漏洞。
• O(1) 解码优势：首字节直接指示后续数据长度，使得解码器无需扫描延续位即可确定内存分配大小，显著提升了处理效率，尤其是对于大数值。
• 性能显著优于 LEB128：在大多数场景下，Bijou64 的解码速度比 LEB128 快 2–10 倍，且在处理均匀分布的大数值时优势更为明显（快 8–10 倍）。
• 分支预测友好：Bijou64 的解码模式具有高度可预测性，有利于 CPU 分支预测器工作，而 LEB128 的变长扫描模式会导致分支预测失败，影响性能稳定性。