2个稳定版本
| 新版本 1.1.0 | 2024年8月13日 |
|---|---|
| 1.0.0 | 2024年5月29日 |
#1097 在 编码
每月 107 次下载
34KB
627 行
vu128：高效变长整数
vu128是一种变长整数编码，较小的值使用更少的字节进行编码。支持128位以内的整数。与广泛使用的VLQ和LEB128编码相比，vu128的压缩比相等或更高，并且在现代流水线架构上运行更快。
编码细节
范围在[0, 2^7)内的值以与原始值相同的位编码为单个字节。
范围在[2^7, 2^28)内的值编码为前缀长度，后跟(length*7)位，以小端序排列。这从概念上类似于LEB128，但延续位放在初始字节的上半部分。这种安排也称为“前缀varint”。
MSB ------------------ LSB
10101011110011011110 Input value (0xABCDE)
0101010 1111001 1011110 Zero-padded to a multiple of 7 bits
01010101 11100110 ___11110 Grouped into octets, with 3 continuation bits
01010101 11100110 11011110 Continuation bits `110` added
0x55 0xE6 0xDE In hexadecimal
[0xDE, 0xE6, 0x55] Encoded output (order is little-endian)
范围在[2^28, 2^128)内的值编码为二进制长度前缀，后跟有效载荷字节，以小端序排列。为了将此格式与较小值的格式区分开来，第一个字节的前4位被设置。长度前缀值是有效载荷字节的数目减一；或者说是编码值的总长度减去两个。
MSB ------------------------------------ LSB
10010001101000101011001111000 Input value (0x12345678)
00010010 00110100 01010110 01111000 Zero-padded to a multiple of 8 bits
00010010 00110100 01010110 01111000 11110011 Prefix byte is `0xF0 | (4 - 1)`
0x12 0x34 0x56 0x78 0xF3 In hexadecimal
[0xF3, 0x78, 0x56, 0x34, 0x12] Encoded output (order is little-endian)
处理超长编码
vu128格式允许超长编码，这种编码使用不必要的字节序列来表示值。
- 超出7或8位倍数所需零填充。
- 使用长度前缀字节来表示范围
[0, 2^7)内的值。 - 使用二进制长度前缀字节来表示范围
[0, 2^28)内的值。
本模块中的 encode_* 函数将不会生成此类过长的编码，但 decode_* 函数将接受它们。这是为了允许在写入值之前将 vu128 值放入缓冲区。需要为任何给定值执行单个规范编码的应用程序应在自己的代码中进行适当的检查。
有符号整数和浮点值
有符号整数和 IEEE-754 浮点值可以通过将它们映射到无符号整数来使用 vu128 进行编码。建议选择映射函数时，尽量减少高位零的数量，这有助于更好地压缩。
此库包括使用 Protocol Buffer 的 "ZigZag" 编码 对有符号整数和反向端序布局对浮点数进行编码的辅助函数。