Superpack：突破 Facebook 移动应用程序的压缩极限( 二 ) 作者|SapanBhatia译者|张健欣策划

在被压缩的程序中， Superpack通过基于AST对数据进行分组来实现这些改进。例如，在以下指令序列中，最长重复序列的长度为2 。然而，当根据AST类型（即操作码和寄存器，小表中的组1）和立即数（下表中的组2）进行分组时，长度增加到4 。在原始数据的原始解析中，重复序列之间的距离是2条指令。但在分组后的版本中，距离为0 。更小的距离通常使用更少的位数，更长的序列匹配通过在给定指针中捕获更多的输入数据来节省空间。因此， Superpack生成的指针比简单计算的指针要小。

文章图片
但是，我们如何决定何时分隔代码流以及何时保持原封不动？Superpack最近的工作中引入了分层压缩，这将此决策合并到LZ解析的优化组件中，称为最优解析。在下面编辑过的代码中，最好将代码段的最后一段保留为原始形式，并生成一个指向前五条指令的指针的匹配项，同时拆分代码段的其余部分。在拆分余数中，利用寄存器组合的稀疏性来生成更长的匹配。以这种方式对代码进行分组还可以通过计算重复序列之间的逻辑单元数量（沿AST测量）而不是测量字节数，来进一步缩短距离。

文章图片
改进的熵编码
重复的字节序列被指向上一次出现的序列的指针有效地替换。但是压缩器对非重复序列或比指针表示更短的短序列能做些什么呢？在这种情况下，压缩器通过对数据中的值进行编码来表示数据。用来表示序列的位数，利用了序列可以假定的值的分布。熵编码是用数据中的值的熵的位数来表示一个值的过程。压缩器为此目的使用的一些众所周知的技术包括哈夫曼编码、算术编码、距离编码和非对称数字系统（asymmetircalnumberalsystems ， ANS）。
Superpack有一个内置的ANS编码器，还有一个可插拔的架构，支持多个这样的编码后端。 Superpack通过识别上下文（其中要表示的序列由较低的熵）来改进熵编码。与LZ解析类似，这些上下文是从Superpack对通过编译器分析提取的数据结构的了解中派生出来的。在下面简化的指令序列中，有七个不同的地址，每个地址都有前缀0x 。在该编码的大量不同排列中，常规编码器用于表示地址字段的位数将接近3 。
然而，我们注意到，七个地址中有三个与BL操作码配对，而另外三个与B操作码关联。只有一个地址与两者都耦合。如果这个模式在整个代码体中都成立，那么操作码可以用作编码上下文。在这种情况下，表示这七个地址的位数接近2而不是3 。下表显示了带上下文和不带上下文的编码。在第三列中的Superpack压缩情况下，可以将操作码视为预测丢失的位。这个简单的示例旨在说明如何使用编译器上下文来改进编码。在实际数据中，获得的位数通常是分数，上下文和数据之间的映射很少像本例中那样直接。

文章图片
作为压缩表示的程序
我们解释了当被压缩的数据由代码组成时， Superpack如何改进LZ解析和熵编码。但当数据包含非结构化值时会发生什么？在这种情况下， Superpack试图通过在压缩时将值转换为程序来添加值结构。然后，在解压时，将程序进行解析来恢复原始数据。这种技术的一个例子是Dex索引的压缩， Dex索引是Dex编码中已知值的标签。 Dex索引具有高度的局部性。为了利用这种局部性，我们将索引转换为一种将最近的值存储在逻辑寄存器中的语言，并将即将出现的值作为固定值的增量发布。