Bijou64：解决可变长度整数编码中的规范性问题
在二进制协议的世界里，高效编码整数是一项持续的平衡工作。大多数开发者都会使用可变长度整数编码（varints），以确保小数字不会浪费 8 字节的空间。然而，这些设计中普遍存在一种微妙但危险的缺陷：缺乏结构上的规范性。
当同一个数值可以用多种不同的字节序列表示时，安全漏洞就会出现——尤其在签名协议中。如果系统基于消息的字节来验证签名，而解码器将不同的字节序列视为相同的数值，攻击者就可以在不改变逻辑值的前提下修改消息字节，从而可能绕过安全检查或导致可塑性问题。这正是 bijou64 旨在解决的核心问题。
LEB128 的缺陷
要了解 bijou64，首先必须看看行业标准：LEB128。LEB128 将数字分成 7 位一段，并使用每个字节的最高位作为“续位”，以指示后面还有更多字节。
虽然实用，但 LEB128 本身并非规范的。例如，数字 0 可以编码为 0x00，但也可以编码为 0x80 0x00 或 0x80 0x80 0x00。大多数解码器都会欣然接受这些表示为零。这种非规范性已经导致关键系统中的真实漏洞，包括 ASN.1、X.509 证书和比特币交易。
传统上，解决办法是通过解码器的运行时检查来强制“规范形式”。但正如 bijou64 的作者指出的，那些检查常常被省略、在优化时去除，或在移植过程中忘记，从而导致安全性悄然下降。
Bijou64 如何实现规范性
Bijou64 通过两种主要机制——首字节标签和偏移量——消除每个整数可能出现的多重编码。
1. 首字节双重职责
在 bijou64 中，首字节承担两种功能。对于 0 到 247 之间的值，首字节 即 为该值。对于 248 及以上的值，首字节充当 标签，精确指示后面跟随多少字节。
这立刻带来性能提升：解码器能够在 $O(1)$ 时间内知道所需的精确内存分配，而 LEB128 必须在 $O(n)$ 时间内扫描续位。
2. 偏移技巧
为了防止像 0 这样的数字既可以用单字节 (0x00) 表示，又可以用带标签的序列（例如 0xF8 0x00）表示，bijou64 使用了偏移量。标签字节表示的数字不再从零开始，而是加上一个偏移值，以确保它们永不与前一层的范围重叠。
例如，如果标签指示的是 2 字节序列，则数值会偏移 248（0xF8）。这确保了最小的 2 字节编码表示 248，而不是 0。该模式对更大的整数同样可预测地延续，形成基于首字节的偏移查找表。
性能基准
令人惊讶的是，为安全性而设计也带来了显著的性能提升。在 ARM（Apple M2 Pro）和 x86（AMD Zen 5）上的基准测试表明，bijou64 通常比 LEB128 快得多。
- 解码速度： Bijou64 大约比 LEB128 快 2–10 倍。对于大规模
u64分布，它可以在约 3 $\mu$s 内处理 4096 个值的批次，而 LEB128 大约需要 30 $\mu$s。 - 一致性： 由于 bijou64 避免了续位扫描中不可预测的分支模式，其性能高度一致（在基准测试中表现为几乎垂直的 CDF 曲线）。
- 编码速度： 虽然在特定的“较小”分布（248 – 65,535）下 LEB128 稍快，但在其他情况下 bijou64 通常表现更佳。
这些提升来源于使用连续的大端负载，这使得现代 CPU 能够使用一次加载和 bswap 指令，而不必像 LEB128 的 7 位布局那样进行掩码和移位操作。
批判性视角与权衡
尽管基准测试令人印象深刻，社区仍提出了若干重要的反驳点：
SIMD 与并行化
有贡献者指出，虽然 bijou64 在标量操作上很快，但在使用 SIMD（单指令多数据）指令时，可能不如 LEB128 或基于哨兵的编码。并行化的机会往往偏好能够批量处理且不依赖首标签字节的格式。
空间效率
LEB128 在某些范围内更紧凑。例如，LEB128 对最高到 $2^{14}$ 的值仍保持 2 字节，而 bijou64 的 2 字节范围要小得多（最高到 500）。对于每个字节都至关重要且数值经常落在此中间范围的协议，LEB128 可能更合适。
“链接” 用例
在某些环境中，例如 DWARF 或 WASM，非规范编码实际上是一种特性。编译器常常发出最宽的 varint（例如 LEB128 的 5 字节）作为符号的占位符，因为其最终地址要等到链接时才确定。如果编码必须严格规范，链接器每次 varint 宽度变化时都必须移动所有后续代码，从而导致一连串的重新计算。
结论
Bijou64 体现了一种理念的转变：它不是在有缺陷的格式上添加检查，而是改造格式，使缺陷不可能出现。对于构建需要签名、内容寻址或实现之间严格一致性的新协议的开发者而言，bijou64 提供了一种结构上更安全且总体更快的 LEB128 替代方案。