LeVarInt64

LeVarInt64是一个库，用于在通常小于八字节的情况下编码和解码u64（和i64）。

通常用于序列化“计数”字段，当编译时不知道后续字节数量时。计数通常只需要一两个字节进行序列化，但u64::MAX需要九个字节。

编码格式设计用于在little-endian架构上高效编码和解码

                   Encoding                                 Values
    
b[8] b[7] b[6] b[5] b[4] b[3] b[2] b[1]    b[0]  
    
                                        0b???????1           0 - 127
                                   0x?? 0b??????10         128 - 16,511
                              0x?? 0x?? 0b?????100      16,512 - 2,113,663
                         0x?? 0x?? 0x?? 0b????1000   2,113,663 - 270,549,119
                    0x?? 0x?? 0x?? 0x?? 0b???10000 270,549,120 - 3.5e10
               0x?? 0x?? 0x?? 0x?? 0x?? 0b??100000      3.5e10 - 4.4e12
          0x?? 0x?? 0x?? 0x?? 0x?? 0x?? 0b?1000000      4.4e12 - 5.7e14
     0x?? 0x?? 0x?? 0x?? 0x?? 0x?? 0x?? 0b10000000      5.7e14 - 7.3e16
0x?? 0x?? 0x?? 0x?? 0x?? 0x?? 0x?? 0x?? 0b00000000           0 - 1.8e19
     \___________________low_u64_________________/
\______________high_u64_______________/

选择尾部零作为长度指示符的原因是

• 在x86_64架构上，计数尾部零是最有效的位计数。
• 它是Aarch64上的第二有效位计数，只需一个额外的指令。
• 位计数的汇编指令。

解码

• 如果low_u64.trailing_zeros() > 7，则返回high_u64。
• 否则
  • 左移以清除不需要的最高位。
  • 右移以清除最后的1和重复的零。
  • 根据前面的尾部零数量添加偏移量。

编码

• 如果值 > 5.7e14，写入0x00和八字节值（high_u64）。
• 否则
  • 计算存储它所需的字节数。
  • 从值中减去偏移量。
  • 左移一位并设置最低位。
  • 左移剩余的位置，这些位置将被填充为零。
  • 将值作为1-8字节（low_u64）写入。

备注

• LeVarInts受到Protobuf的VarInts的启发，但使用小端格式以允许更有效的处理。
• 与VarInts不同，LeVarInts使用偏移量以牺牲一个汇编“add/sub immediate”指令为代价获得约1%的空间效率。
• 九字节编码是一个特殊情况。
  • 如果遵循了模式
    • 它将使用73位（10字节）而不是九位，并且
    • 高64位中的零值将表示OFFSET8而不是重复的零。
  • 相反，因为我们知道u64不能超过8字节
    • 我们省略了移位，
    • 直接在高位八字节中存储八字节的值。
  • LeVarInt128会更复杂。

API

• 对于该软件包的第一个版本，仅提供了非常底层的encode_u64_to_array_ref()和decode_u64_from_array_ref()。
  • 它们是最有效的，因为边界检查已被优化掉。
  • 它们不友好。
  • 更好的API是什么？
    • [u8]切片？
    • 迭代器？

感谢

• 感谢 Masklinn 和 Chayim Friedman 的帮助，他们帮助我解决了 https://stackoverflow.com/questions/75370230
• 感谢 PitaJ 回答 https://stackoverflow.com/questions/75496635