Bijou64是一种变长整数编码，最初为解决Subduction协议签名验证问题而设计，通过确保数字唯一表示方式修复漏洞。意外发现其性能优于常见的LEB128编码，因设计约束减少了计算量。该编码在保证规范性的同时，兼顾了小数值压缩和大数值处理的需求。

bijou64：一种高效且规范化的变长整数编码方案

bijou64是我们为Subduction CRDT同步协议开发的一种变长整数(varint)编码方案。它最初旨在通过确保每个数字只有唯一编码方式来解决签名验证漏洞，但意外地获得了比常见LEB128编码快数倍的性能优势。

技术背景

变长整数编码允许用紧凑方式表示通常较小但偶尔较大的整数。传统方案如LEB128采用7位分段编码，每个字节的最高位作为继续标志。这种方式存在一个关键问题：同一个数字可以有多种编码形式（如数字0可表示为0x00、0x80 0x00等），这在需要精确字节匹配的场景（如数字签名）会带来安全隐患。

bijou64的创新设计

bijou64通过两项关键技术确保编码唯一性：

1. 首字节双重功能：首字节直接表示0-247的值；248-255则作为标记，指示后续字节数量。这种设计使解码器能立即确定需要读取的字节数（O(1)复杂度），而LEB128需要持续扫描直到遇到终止字节（O(n)复杂度）。

2. 偏移量机制：通过数学偏移确保每个数值只有唯一编码形式。例如标记字节0xF8对应的数值不是0而是248，这样就从结构上消除了冗余编码的可能性。

性能表现

在x86（AMD Zen5）和ARM（Apple M2 Pro）平台上的基准测试显示： - 解码速度：比LEB128快2-10倍，处理4096个数值仅需约3µs（约0.75ns/值） - 编码速度：除极小数值范围外均优于LEB128 - 稳定性：执行时间高度集中，波动远小于LEB128

应用价值

bijou64特别适合需要确保编码规范性的场景： - 数字签名验证 - 内容寻址系统 - 需要跨实现字节一致性的协议

虽然LEB128仍是成熟稳定的选择，但bijou64在需要规范化保证的新项目中展现出独特优势。项目已开源发布（MIT/Apache-2.0双许可），提供Rust实现和Wasm/JavaScript封装。

注：bijou64作为新方案尚未经过广泛实战检验，用户需根据具体需求评估采用。完整技术规范参见项目仓库。

以下是评论内容的总结：

支持观点

1. 编码简洁性与明确长度

   • 新方案通过首字节即可确定整数长度，且每个数值有唯一规范表示（评论4、12）
     引用：
     "the size of the integer is apparent upon reading the first byte, and every number has exactly one canonical representation"
     "One nice upside of having a single way to encode a value is fuzzing"

2. 实用性与性能

   • 相比LEB128，新方案在常见用例中更友好，支持完整uint64范围且无需额外字节（评论2）
     引用：
     "this looks so much nicer for most use-cases... supports the full uint64 range without that extra 10th byte"

反对/质疑观点

1. 编码空间效率不足

   • LEB128在较大数值时（如2^14范围内）保持2字节，而新方案仅支持500个2字节数值（评论2、6）
     引用：
     "bijou64 only gives you 500 <= 2 byte numbers"
     "it is faster by being able to tell the total length from the first byte... while some other formats can store arbitrarily large integers"

2. SIMD兼容性问题

   • 类似设计在SIMD指令下性能不如ULEB128或哨兵值（评论9）
     引用：
     "when you move to SIMD instructions, ULEB128... win every time because of the parallelization opportunities"

3. 安全性隐患

   • 可能被恶意输入利用（如声明255标签但无后续字节）（评论13）
     引用：
     "tricking the payload parser into an incorrect offset and reading straight off into followup memory"

中立/补充观点

1. 与其他编码方案的比较

   • 类似设计存在于SQLite varint（评论15、17）、修正UTF-8（评论7）和Elias omega编码（评论14）
     引用：
     "I'm surprised there's no mention... about SQLite's varint encoding"
     "This is pretty close to SQLite's varints"

2. 非规范编码的用途

   • LEB128的非规范编码在编译器链接等场景中有独特优势（评论16）
     引用：
     "Non-canonical encodings are actually quite useful for some applications... like DWARF and WASM"

总结：评论对新编码方案的规范性和易用性表示认可，但对其空间效率、SIMD兼容性及安全性存在担忧，同时建议参考其他现有编码方案的设计思路。