Bijou64：一种变长整数编码 - CodeMart

当你致力于安全性时，却意外地免费获得了一些性能，这感觉很好。本文讲述了一个名为 bijou64 的小型编码的故事——一种我们为 Subduction CRDT 同步协议开发的变长整数（varint）编码。它旨在通过使每个数字只有一种表示方式来修复一个微妙的签名验证错误。结果发现，它运行起来比更常见的 varint LEB128 还要快几倍。我们最初并不是要写一个快速的 varint，但事实证明，我们的设计约束使得编码需要做的工作更少。

问题

许多二进制协议需要一种紧凑的方式来编码那些通常很小但偶尔很大的整数。变长整数编码（"varints"）解决了这个问题，但大多数设计都将规范性视为事后考虑——由解码器中的运行时检查强制执行，而不是由编码本身的结构来保证。由于 LEB128 是最常见的 varint，我们将在这里对它进行一些讨论。我想强调的是，LEB128 对于许多项目来说是一个很好的选择，而它不适合我们的原因也适用于我们考察过的其他格式。只是它恰好不完美地契合我们的用例。

LEB128 将数字编码为 7 位段序列，每个字节的高位表示“后面还有更多字节”（下面只展示了 2 个段，但实际上可以有多个这样的连续段）。这让你在表示一个小数字时（大部分是零），避免总是写入 8 字节（64 位）。这就像为了得到正确的字符数而写 5 而不是 000000005。抛开 7 位工作方式的奇怪之处，这是一个实用的解决方案！

LEB128 布局

但有一个问题：数字 0 可以编码为单个字节 0x00，但也可以编码为 0x80 0x00。或者 0x80 0x80 0x00。或者任何以零字节结尾的更长的 0x80 序列。0x80 是 1 0000000，所以你可以有任意多个这样的字节，仍然得到 0！大多数 LEB128 解码器都会愉快地接受它们中的任何一个。这并不只限于零；LEB128 中的几乎每个数字都可以用多种方式表示。

LEB128 中零的两种表示

这会给签名数据带来问题，如果你想要做诸如压缩之类的事情，因为你需要知道被签名的确切字节。多一个 0x80 会导致不同的签名。如果你只有一种唯一的方式来表示一个数字，那么你可以在存储时对数字序列进行去重，而无需保留整个原始数据。

规范化

一种解决方案是简单地强制使用特殊的“规范”形式。在编码 varint 时，必须确保使用规范编码（并非所有库都会始终这样做）。在解码时，必须验证它是否符合预期格式。能够不用做额外的检查真的很好。

那么后果呢？

你可能会合理地问：究竟谁会带着对抗性的 varint 出现？答案是“任何能从你的协议将两个不同的字节串误认为相同值中获益的人”。对于签名协议，那可能是很多人。虽然不专门针对 varint，但教科书般的案例是 ASN.1（X.509 证书、LDAP 和许多其他广泛依赖的东西背后的抽象语法表示法）。规范化攻击已被用于针对 PKCS#1 v1.5、Mozilla NSS、GnuTLS、JWT 和比特币交易。所有这些中的模式大致如下：规范说：“规范编码是 X；任何其他编码都必须被拒绝。”实现有一个或多个 if 来强制执行这一点。该检查可以从解析器的其余部分中单独删除。删除它不会破坏往返测试；不会破坏使用诚实编码数据的测试；不会破坏性能基准测试。它只在对抗性输入下才会被破坏，而这种输入很少出现在测试套件中。该检查被遗忘、优化掉或从未移植。协议的安全属性悄无声息地降级了。

这是 bijou64 旨在使其不可能出现的错误类别。不是通过添加更多检查，而是通过移除那个重要的检查——并使格式如此设计，以至于在完全没有规范性检查的情况下，任何给定值存在的唯一编码就是规范编码。

（几乎）天生规范

bijou64 消除了每个整数有多个编码的可能性。就像我们正常的书面数字系统一样，每个数字只有一种写法。Bijou 使用了两个技巧：

第一个字节双重职责第一个字节正常表示 0–247。如果你得到 0x42，它就解码为 0x42。248–255 切换到另一种模式：它们是标签，表示第一个字节之后还有多少个字节来表示数字。这对解码非常友好，因为一旦读到第一个字节，我们就知道要分配多少内存（O(1)）。相比之下，LEB128 必须一直读取字节，直到看到没有设置继续位的字节（O(n)）。

字节/标签结构
偏移量仅靠标签不足以保证规范性，但它指明了方向：不是在第二个字节中重复 0-247（0xF8 0x00 == 0x00），而是将下一个字节偏移 248（0xF8）。这意味着 0xF8 0x00 == 0xF8 == 248，而不是 0（因为 0 已经表示为 0x00）。

下面是解码 1738 的一个工作示例，它需要标签加上两个字节：

工作示例

所有此长度（总共 3 字节，即标签 + 2 个数据字节）的数字都偏移了 504（0x1F8）。每个后续长度都会以可预测的模式增加偏移量。看看你是否能发现它：

总长度偏移量 1 0x00 2 0xF8 3 0x01F8 4 0x0101F8 5 0x010101F8 6 0x01010101F8 7 0x0101010101F8 8 0x010101010101F8 9 0x01010101010101F8

这是基于第一个字节的查找表！有一个例外：由于数字总是向下偏移，最大值（9 字节）需要手动检查它们是否在范围内。由于偏移，9 字节（标签 + 8 字节数据）槽实际上可以表示大于 2⁶⁴ 的数字，但鉴于 bijou64 目标是 u64，我们将其限制在那里。这不是之前提到的规范性问题——每个范围内的数字仍然只有一种编码——我们只是切掉了我们不想要的额外空间。所以当标签是 255（最大的那个）时，解码器检查该值是否低于截止点。

基准测试

Bijou64 必须做所有这些位操作、标签查找等等。所有这些都需要成本，而且与常规的固定长度 64 位数字相比确实有成本。它肯定比广泛使用的编码（如 LEB128 和非常巧妙的 vu128）慢，对吗？我们在 ARM（Apple M2 Pro）和 x86（AMD Zen 5）上进行了基准测试，得到的结果出乎意料。

解码

每批 4096 个值的中位数解码时间。越低越好。分布描述见方法论。

bijou64 相当快！即使不考虑 LEB128 上规范性检查的开销，它的解码速度大约比 LEB128 快 2-10 倍。在这些基准测试中，小数字（编码为单个 LEB128 字节）大约快两倍。较大的数字（迫使 LEB128 跨多个字节扫描继续位）大约快 8-10 倍。在均匀的全 u64 分布上（几乎是基准测试中最具对抗性的情况），bijou64 处理一批 4096 个值大约需要 3 µs（每个值约 0.75 ns），而 LEB128 需要约 30 µs（每个值约 7.3 ns）。

然而，柱状图只显示了中位数。下面的 CDF 才是方差所在：

每批 4096 个值的解码时间，绘制为每个库 × 分布单元的 CDF。曲线越靠左越快。曲线越陡峭，性能越一致。在这些基准测试中，bijou64 的 CDF 几乎是垂直的——每次记录的批次时间都位于中位数附近的一个微小带内。LEB128 的曲线倾斜并向右拖尾，因为继续位扫描长度取决于值，并且分支预测器永远没有机会锁定。

正如你所想象的，在进行规范解码时，差异更大，因为 bijou64 由于其编码（除了最大的数字）而“免费”获得了这一点：

每批 4096 个值的规范解码时间——即解码加上需要检查的库的运行时过长拒绝检查。在 bijou64 中，规范解码就是解码——规范性检查就是格式本身。在其他库中，规范性检查是额外的工作。

编码

编码通常也更快，但有一个例外：

每批 4096 个值的中位数编码时间。在“小”分布（248 – 65,535）上，LEB128 大约快 1.24 倍。

编码大小

bijou64 并非在所有分布上都是最紧凑的 varint。除了层级边界差异外，在现实工作负载下，bijou64 和 LEB128 产生的线缆字节数相差在几个百分点之内。

表示某些数字的长度。这些是特意选择来展示它们不同的地方；绝大多数数字的长度相同。

为什么？

事后看来，这有点合理：

长度来自第一个字节：由于不需要扫描继续位，解码器立即知道要读取多少字节；编码器立即知道要写入多少字节。LEB128 的解码器必须扫描每个字节的高位，直到找到终止符。分支预测器喜欢 bijou64 的模式；它们讨厌 LEB128 的模式，尤其是对于继续链很长的大值。
大端、连续的有效载荷：有效载荷是一个连续的大端整数，而不是散布着记账位的 7 位块。现代 CPU 有专门的字节交换指令；编译器将读取转换为单个 load + bswap。LEB128 的每字节 7 位布局迫使解码器对每个字节进行掩码和移位。
可预测的分支：层级选择是一个小的固定匹配。对于任何单一工作负载，分支预测几乎立即稳定在一个稳定模式中——正是那些陡峭的 CDF 曲线所显示的。
算术成本低：添加 OFFSET[tier] 是一个常量加载和加法（如果是编码则是减法）。早期版本有 if 和一些分支，但算术版本在大多数现代 CPU 的热路径中实际上指令更少。

你应该使用 bijou64 吗？

也许！像大多数有趣的问题一样，这取决于你的目标。这是一个全新的格式，并且还没有像 LEB128 那样经过实战测试，LEB128 在每种主流语言中都有成熟且经过充分验证的实现。我们的基准测试令人鼓舞，但大话需要大证据——我们目前只测试了三款 CPU（M2 Pro 和 Zen 5 在已发布的基准测试中；我们尝试的 Zen 3 看起来与 Zen 5 类似）。LEB128 不会消失，也不应该消失。但是，如果你正在设计一个新的格式，并且规范性很重要——对于签名、内容寻址或任何“两个实现必须在字节上达成一致”的属性——有一个结构上更安全、在我们抛给它的所有基准测试中运行更快的替代方案。

该库已作为 bijou64 发布在 crates.io 上，采用 MIT / Apache-2.0 双许可，规范采用 CC BY-SA 4.0，如果你想移植的话。还有一个 Wasm/JavaScript 包装器，并且在规范的未来扩展部分中概述了一系列宽度扩展（bijou32、bijou128）。如果你发现了一个 bug——或者更有趣的是，一个 bijou64 在我们基准测试中输给其他东西的工作负载——我们很乐意听到！