这篇文章上次修改于 409 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
本文讲述整数压缩算法 TurboPFor。
原作者写了个示例，以方便理解：https://github.com/stapelberg/goturbopfor
1 压缩后的格式
以 TurboPFor256 为例，每个 block 包含 256 个整数，最后一个 block 可能不足 256 个整数：
最后一个 block 使用一般的bitpacking，其它 block 使用 SIMD bitpacking。
每个 block 的前 2 个 bit 标识该 block 的类型：
- 11: constant
- 00: bitpacking
- 10: bitpacking with exceptions (bitmap)
- 01: bitpacking with exceptions (variable byte)
需注意，block 中不会存放被编码的数据个数，使用者需要自己知道有多少个数据要被解码，还需要知道应将多少个字节喂给 TurboPFor，所以使用者需要自己额外定一个容器格式。
TurboFor 会自动为每个 block 选择最好的 block 类型。
Constant block
一个 constant block 中记录了一个位宽 <= 32 的值。
- 第 1 个字节的后 6 位存储 constant 的位宽
- 后面的字节存储 constant
例如调用 decode(input, 3, output)，其中 input 如下所示：
可以看到被解码的数据的位宽是 32，所以读取随后的 4 个 block，采用小端方式得到数字的二进制形式为 10111000-10010001-00100110-00110110， 其十六进制格式为 0xB8912636。因为 decode() 的第 2 个参数是 3，可知是 3 个 0xB8912636 被压缩了，所以解压后得到 output = {0xB8912636, 0xB8912636, 0xB8912636}
Bitpacking block
第 1 个 bitpacking block 指定了位宽 <= 32，随后跟着的是被压缩的数据。
- 第 1 个字节的后 6 位存储 value 的位宽
- 后面的字节存储 n 个 value
每个值都是小端方式存储，例如位宽是 3，那么 110，110，000 拼接后会变成 000110110
Bitpacking with exceptions (bitmap) block
如果大部分数字都可以用 3 bit 表示，但是只有少量数字用 8 bit 表示，那么就可以将数据分为两部分：value 和 exception。
假如压缩了 n 个数据
- 第 1 个字节的后 6 位存储 value 的位宽
- 第 2 个字节存储 exception 的位宽
- 接下来的 n 个 bit 是 exception map，如果第 i 个数字 exception 和 value 的拼接，那么第 i 个 bit 为 1，假如 bit 为 1 的个数是 m
- 接下来是 m 个 exception
- 接下来是 n 个 value
如下例子中，在解码第 3 个整数 out2(000b) 时，还需要与 exception ex0(10110b) 结合到一起，因为在 bitmap 中第 3 位是 1，最终得到 10110000b。
exception 的数量可通过统计 bitmap 中 1 的数量得到，统计的方法可参考 popcount instruction。
Bitpacking with exceptions (variable byte)
如果 exception 的位宽不统一，就使用 variable byte 编码。
假如压缩了 n 个数据
- 第 1 个字节的后 6 位存储 value 的位宽
- 第 2 个字节存储 exception 的数量 m
- 从第 3 个字节起，存储 n 个 value
- 接下来存储 m 个 exception
- 接下来存储 exception 的下标 i，说明当前 exception 可以与第 i 个 value 拼接成一个数字
2 解码变长字节
第一个字节 b[0] 用来存储区分范围
[0 - 176]：值是 b[0]
0 -- 10110000
[177 - 240]：14 bit 的值，其中高 6 bit 位于 b[0]，低 8 bit 位于 b[1]
0 -- 11110000
[241 - 248]：19 bit 的值，其中高 3 bit 位于 b[0]，b[1] 和 b[2] 存储低 16 bit
11110001 -- 11111000
[249 - 255] ：32 bit 的值，存储在 b[1], b[2], b[3]，也有可能会有 b[4]
11111001 -- 11111111
值的存储空间：
[0 - 176]：1 byte
0 -- 10110000
[177—16560]：2 byte，高 6 bit 会加到 177
10110001 -- 1000000-10110000
[16561—540848]：3 byte，高 3 bit 加到 241
1000000-10110001 -- 1000-01000000-10110000
[540849—16777215] ：4 byte，0 会加到 249
1000-01000000-10110001 -- 11111111-11111111-11111111
[16777216—4294967295] ：5 byte，1 加到 249
1-00000000-00000000-00000000 -- 11111111-11111111-11111111-11111111
3 解码：bitpacking
一般的 bitpacking
整数按照顺序存储，例如，bitpack 3 bit 的整数：
SIMD bitpacking (256v32)
SIMD bitpacking 会一次性处理 8 个小端序的 uint32：
4 TurboPFor-Integer-Compression
源码：TurboPFor-Integer-Compression
所有的编解码函数定义都可以位于 include/ic.h，实现部分位于 lib/vp4c.c 和 lib/vp4d.c，是使用宏实现的。例如对于 size_t p4nd1enc128v32(uint32_t *__restrict in, size_t n, unsigned char *__restrict out);，无法直接通过函数名直接搜到其实现，需通过如下方式拼接得到函数名。
在 vp4c.c 中可以看到如下函数：
size_t T2(P4NENC, USIZE)(uint_t *__restrict in, size_t n, unsigned char *__restrict out) {
...
}其中，T2 在 lib/include_/conf.h 中定义如下：
#define T2_(_x_, _y_) _x_##_y_
#define T2(_x_, _y_) T2_(_x_,_y_)仅仅用于拼接两个字符串。
P4NENC 和 USIZE 在 lib/vp4c.c 中定义如下：
#define P4NENC p4ndenc128v
#define USIZE 32进行宏替换 T2(P4NENC, USIZE) --> p4ndenc128v32 后就得到了函数名。
也可以使用 cpp vp4c.c > cp4c.i 得到宏扩展后的文件，不过如果有的宏的符号没找到的话，扩展后会缺失。
没有评论