本文讲述整数压缩算法 TurboPFor。
原作者写了个示例,以方便理解:https://github.com/stapelberg/goturbopfor
以 TurboPFor256 为例,每个 block 包含 256 个整数,最后一个 block 可能不足 256 个整数:
最后一个 block 使用一般的bitpacking,其它 block 使用 SIMD bitpacking。
每个 block 的前 2 个 bit 标识该 block 的类型:
需注意,block 中不会存放被编码的数据个数,使用者需要自己知道有多少个数据要被解码,还需要知道应将多少个字节喂给 TurboPFor,所以使用者需要自己额外定一个容器格式。
TurboFor 会自动为每个 block 选择最好的 block 类型。
Constant block
一个 constant block 中记录了一个位宽 <= 32 的值。
例如调用 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,随后跟着的是被压缩的数据。
每个值都是小端方式存储,例如位宽是 3,那么 110,110,000 拼接后会变成 000110110
Bitpacking with exceptions (bitmap) block
如果大部分数字都可以用 3 bit 表示,但是只有少量数字用 8 bit 表示,那么就可以将数据分为两部分:value 和 exception。
假如压缩了 n 个数据
如下例子中,在解码第 3 个整数 out2(000b)
时,还需要与 exception ex0(10110b)
结合到一起,因为在 bitmap 中第 3 位是 1,最终得到 10110000b
。
exception 的数量可通过统计 bitmap 中 1 的数量得到,统计的方法可参考 popcount instruction。
Bitpacking with exceptions (variable byte)
如果 exception 的位宽不统一,就使用 variable byte 编码。
假如压缩了 n 个数据
第一个字节 b[0] 用来存储区分范围
值的存储空间:
一般的 bitpacking
整数按照顺序存储,例如,bitpack 3 bit 的整数:
SIMD bitpacking (256v32)
SIMD bitpacking 会一次性处理 8 个小端序的 uint32:
源码: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
得到宏扩展后的文件,不过如果有的宏的符号没找到的话,扩展后会缺失。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。