bijou64：一种可变长度整数编码

# bijou64 来源：https://www.inkandswitch.com/tangents/bijou64/ 搞安全研究时意外捎带脚获得了性能提升，这种感觉真不错。这里要讲的是一个叫 `bijou64` (https://github.com/inkandswitch/bijou/tree/main/bijou64) 的小型编码方案——一种用于 [Subduction](https://github.com/inkandswitch/subduction)CRDT 同步协议的可变长整数（varint）编码。它的初衷是修复一个微妙的签名验证 bug，通过确保每个数字只有唯一的表示方式。结果它运行起来竟然比更常用的 varint [LEB128](https://en.wikipedia.org/wiki/LEB128) 快了好几倍。 我们并不是打算写一个快速的 varint，但结果我们的设计约束使得编码要做的工作更少。 ## 问题 许多二进制协议需要一种紧凑的方式来编码整数，这些整数 *通常* 很小，但 *偶尔* 很大。可变长整数编码（“varints”）解决了这个问题，但大多数设计都把规范形式（canonicality）当作事后补充——由解码器在运行时检查来保证，而不是由编码结构本身来保证。 因为 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 解码器都会愉快地接受其中任何一种。这并非 `0` 独有的问题；LEB128 中几乎所有的数字都可以有多种表示方式。 零在 LEB128 中的两种表示方式如果你要对签名数据做压缩之类的操作，这会带来问题，因为你必须知道被签名数据的 *确切* 字节。多一个 `0x80` 会导致签名不同。 如果你只有一种唯一的数字表示方式，那么在做去重等操作时，就不需要保留完整的原始数据。 ## 规范化（Canonicalisation） 一种解决方案是强制实施一种特殊的“规范”形式。在编码 varint 时，必须确保使用规范编码（并非所有库都会这样做）。在解码时，必须验证它是否符合预期的格式。如果不需要做这些额外工作，那就太好了。 ## 那又怎样？ 你可能会合理地问：谁会真的带着对抗性的 varint 出现呢？答案是：“任何能从你的协议将两个不同的字节串误认为相同值中获益的人。”对于签名协议，那可能有很多人。 虽然不完全是针对 varint，但教科书式的案例是 ASN.1（X.509 证书、LDAP 以及许多广泛依赖的其他东西背后的抽象语法表示法）。规范形攻击曾被用于针对 [PKCS#1 v1.5](https://www.imperialviolet.org/2014/09/26/pkcs1.html)、[Mozilla NSS](https://nvd.nist.gov/vuln/detail/CVE-2014-1568)、[GnuTLS](https://nvd.nist.gov/vuln/detail/CVE-2008-1950)、[JWT](https://auth0.com/blog/critical-vulnerabilities-in-json-web-token-libraries/) 和 [Bitcoin 交易](https://en.bitcoin.it/wiki/Transaction_malleability)。 所有这些案例的模式大致是这样的： 1. 规范说：“规范编码是 X；必须拒绝任何其他编码。” 2. 实现中包含一个或多个 `if` 语句来强制执行这一要求。 3. 该检查是 *可被单独删除的*，不影响解析器的其余部分。删除它不会破坏往返测试；不会破坏使用诚实编码数据的测试；不会破坏性能基准测试。它只会在对抗性输入下失效，而这种输入很少出现在测试套件中。 4. 这个检查被遗忘、被优化掉，或者从未被移植。协议的安全属性无声地降级。这正是 bijou64 旨在使其*不可能*发生的 bug 类别。不是通过添加 *更多* 检查，而是通过移除那个关键检查——并设计格式使得，在根本没有规范形检查的情况下，对于任何给定值，唯一存在的编码 *就是* 规范编码。 ## （几乎）由构造保证规范形 bijou64 消除了每个整数有多个编码的可能性。就像我们普通的数字书写系统一样，每个数字有且只有一种书写方式。Bijou 使用了两个技巧： ## 1. 首字节双重职责 第一个字节正常表示 0–247。如果你得到 `0x42`，解码就是 `0x42`。248–255 则切换到另一种模式：它们是一个*标签*，指示此首字节之后还有多少字节，这些字节将表示数字。这对于解码非常友好，因为我们在读取第一个字节后就知道要分配多少内存（`O(1)`）。相比之下，LEB128 必须持续读取字节，直到看到一个没有设置延续位的字节（`O(n)`）。 字节/标签结构## 2. 偏移量 仅有标签还不足以保证规范形，但它指明了方向：不是让第二个字节重复 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^64 的数字，但因为 bijou64 针对 `u64`，我们在此截断。这不是之前所说的规范形问题——每个范围内的数字仍然有唯一的编码——我们只是剪掉了我们不需要的额外空间。所以当标签是 255（最大值）时，解码器会检查值是否低于上限。 ## 基准测试 Bijou64 需要做所有这些位运算、标签查找等等。所有这些都是有代价的，而且相对于常规的固定长度 64 位数字来说，确实有代价。它肯定比广泛使用的编码如 LEB128 和非常巧妙的 [vu128](https://john-millikin.com/vu128-efficient-variable-length-integers) 要慢，对吧？我们在 ARM（Apple M2 Pro）和 x86（AMD Zen 5）上进行了测试，结果出乎意料。 ## 解码 [](https://github.com/inkandswitch/bijou/raw/ae834fe465d8cea5b506a8b69f90bcd236f7b984/bijou64/charts/x86/decode_bar.svg) 每批 4096 个值的中位数解码时间。越低越好。分布描述见 [方法说明](https://github.com/inkandswitch/bijou/blob/main/bijou64/SHOOTOUT_ANALYSIS_X86.md)。 bijou64 表现得相当快！ 它的解码速度大约是 LEB128 的 2 到 10 倍，*甚至在不考虑 LEB128 的规范形检查开销的情况下*。小的数字（编码为单个 LEB128 字节）在这些基准测试中大约快两倍。较大的数字，强制 LEB128 跨多个字节扫描延续位，速度大约快 8 到 10 倍。在均匀的全 `u64` 分布上——差不多是基准测试中最具对抗性的情况——bijou64 处理一批 4096 个值大约需要 3 μs（约 0.75 ns 每个值），而 LEB128 需要大约 30 μs（约 7.3 ns 每个值）。 不过条形图只显示了中位数。下面的 CDF 图才是方差所在： [](https://github.com/inkandswitch/bijou/raw/ae834fe465d8cea5b506a8b69f90bcd236f7b984/bijou64/charts/x86/decode_cdf.svg) 每批 4096 个值的解码时间，以每个库×分布单元格的 CDF 形式绘制。曲线越靠左越快。曲线上升越陡峭，性能越一致。 在这些基准测试中，bijou64 的 CDF 几乎是垂直的——所有记录的批次时间都落在中位数附近的一个狭窄区间内。LEB128 的曲线向右倾斜并拖尾，因为延续位扫描长度取决于值，而分支预测器永远没有机会锁定。 可以想象，当进行 *规范* 解码时，差异会更大，因为 bijou64 由于其编码设计，对于除最大数字外的所有数字都“免费”获得了规范形： [](https://github.com/inkandswitch/bijou/raw/ae834fe465d8cea5b506a8b69f90bcd236f7b984/bijou64/charts/x86/canonical_decode_bar.svg) 每批 4096 个值的规范解码时间——即解码加上运行时的超长拒检检查（对于需要检查的库而言）。 在 bijou64 中，规范解码 *就是* 解码——规范形检查 *就是* 格式本身。而在其他格式中，规范形检查是额外的工作。 ## 编码 编码通常也更快，只有一个例外： [](https://github.com/inkandswitch/bijou/raw/ae834fe465d8cea5b506a8b69f90bcd236f7b984/bijou64/charts/x86/encode_bar.svg) 每批 4096 个值的中位数编码时间。 在“小”分布（248 – 65,535）上，LEB128 以约 1.24 倍的差距获胜。 ## 编码尺寸 对于每个分布来说，bijou64 并不是最紧凑的 varint。除了层级边界差异之外，在现实工作负载下，bijou64 和 LEB128 产生的有线字节数相差在几个百分点以内。 [](https://github.com/inkandswitch/bijou/raw/ae834fe465d8cea5b506a8b69f90bcd236f7b984/bijou64/charts/size/heatmap.svg) 表示某些数字所需的长度。这些数字特意选择来显示差异；绝大多数数字的长度相同。 ## 为什么？ 事后看来，这有一定道理： ### 从首字节得知长度 因为没有延续位扫描。解码器立即知道要读多少字节；编码器立即知道要写多少字节。LEB128 的解码器必须扫描每个字节的高位，直到找到终止符。分支预测器喜欢 bijou64 的模式；但讨厌 LEB128 的模式，特别是对于延续链很长的较大值。 ### 大端序、连续的负载 负载是一个连续的大端序整数，而不是零散分散着记账位的 7 位块。现代 CPU 正好有字节交换指令；编译器可以将读取转换为单个 `load` + `bswap`。LEB128 的每字节 7 位布局强制解码器对每个字节进行掩码和移位。 ### 可预测的分支 层级选择是一个小的固定匹配。对于任何一个工作负载，分支预测几乎立即稳定到一个稳定的模式——这正是那些陡峭的 CDF 曲线所显示的。 ### 算术运算廉价 加上 `OFFSET[tier]` 是一个常量加载和一个 `add`（如果编码则是 `sub`）。以前的版本有一个 `if` 和一些分支，但算术版本在大多数现代 CPU 的热路径上实际上拥有 *更少* 的指令。 ## 你*应该*使用 bijou64 吗？ 也许！像大多数有趣的问题一样，这取决于你的目标。这是一个全新的格式，它还没有像 LEB128 那样经过充分的实战检验，LEB128 在每种主流语言中都有成熟且经过充分测试的实现。我们的基准测试令人鼓舞，但重大主张需要重大证据——而且我们目前只测试了三种 CPU（M2 Pro 和 Zen 5 在已发布的基准测试中；我们试过的 Zen 3 看起来与 Zen 5 类似）。 LEB128 不会消失，也不应该消失。但如果你正在设计一个新格式，并且规范形很重要——对于签名、内容寻址或任何“两个实现必须对字节达成一致”的特性——那么有一种替代方案在结构上更安全，*并且*在我们扔给它的每一个基准测试中都运行得更快。 该库以 `bijou64` 的名称发布在 [crates.io](https://crates.io/crates/bijou64) 上，采用 MIT / Apache-2.0 双许可证，规格说明采用 [CC BY-SA 4.0](https://github.com/inkandswitch/bijou/blob/main/bijou64/SPEC.md)，如果你想移植的话。存在一个 Wasm/JavaScript 包装器，并且规范的未来扩展部分中勾勒了一系列宽度扩展（`bijou32`、`bijou128`）。如果你发现了一个 bug——或者更有趣的是，发现了一个 bijou64 *输给* 我们基准测试中某些东西的工作负载——我们很乐意听取你的意见！