跳到主要内容

11. 压缩器实现注意事项

  1. 压缩器实现注意事项

由于本文档旨在定义 Brotli 压缩数据格式, 而不引用任何特定压缩算法, 本节材料不属于该格式定义的一部分, 压缩器无需遵循本节内容即可符合规范.

11.1. 平凡压缩器

本节给出一个非常简单的算法, 它可产生表示任意未压缩字节序列的有效 Brotli 流. 该算法以以下 C++ 语言函数形式给出.

     string BrotliCompressTrivial(const string& u) \{
        if (u.empty()) \{
           return string(1, 6);
        \}
        int i;
        string c;
        c.append(1, 12);
        for (i = 0; i + 65535 < u.size(); i += 65536) \{
           c.append(1, 248);
           c.append(1, 255);
           c.append(1, 15);
           c.append(&u[i], 65536);
        \}
        if (i < u.size()) \{
           int r = u.size() - i - 1;
           c.append(1, (r & 31) << 3);
           c.append(1, r >> 5);
           c.append(1, 8 + (r >> 13));
           c.append(&u[i], r + 1);
        \}
        c.append(1, 3);
        return c;
     \}

注意, 这个简单算法实际上并不会压缩数据, 也就是说, Brotli 表示总是大于原始数据. 但它表明, 每个由 N 个未压缩字节组成的序列都可以用一个有效 Brotli 流表示, 且长度不超过 N + (3 * (N >> 16) + 5) 字节.

11.2. 将压缩元块对齐到字节边界

如第 9 节所述, 只有紧跟在未压缩元块或元数据元块之后的那些元块才能保证从字节边界开始. 在某些应用中, 可能要求每个非元数据元块都从字节边界开始. 这可以通过在每个未在字节边界结束的非元数据元块之后追加一个空元数据元块来实现.

11.3. 在压缩数据中创建自包含部分

在某些编码器实现中, 可能需要使 Brotli 流内的一段字节序列自包含, 也就是说, 它们可以独立于压缩数据的前面部分进行解压缩. 这是一个有用特性, 原因有三点. 首先, 如果一个大型压缩文件受损, 有可能恢复受损位置之后的部分文件. 其次, 这对压缩数据的差分传输很有用. 如果一段未压缩字节序列未发生变化, 且独立于之前数据进行压缩, 则其压缩表示也可能保持不变, 因而能够以很低成本传输. 第三, 如果未压缩字节序列被独立压缩, 除了对多个文件进行并行压缩之外, 还可以在同一个文件内并行压缩这些字节序列.

给定两个未压缩字节序列 U0 和 U1, 下面描述如何创建两个压缩字节序列 C0 和 C1, 使得 C0 与 C1 的串接是一个有效 Brotli 流, 并且 C0 与 C1 (连同 C0 中包含窗口大小的第一个字节) 可以彼此独立地解压缩为 U0 和 U1.

在压缩字节序列 U0 以产生 C0 时, 可以使用任何作用于完整未压缩字节集合 U0 的压缩器, 但需进行以下两项改变. 第一, C0 最后一个元块的 ISLAST 位不得置位. 第二, C0 必须在字节边界结束, 这可以像第 11.2 节那样通过向其追加一个空元数据元块来保证.

在压缩字节序列 U1 以产生 C1 时, 可以使用任何在 U0+U1 输入流中 U1 开始处启动新元块的压缩器, 但需进行以下两项改变. 第一, C1 中的向后距离不得引用静态字典词或 U0 中的未压缩字节. 即使 U1 中的某段字节序列会匹配某个静态字典词, 或匹配与 U0 重叠的字节序列, 压缩器也必须改用字面量插入和对 U1 中字节的向后引用组合来表示该字节序列. 第二, 最近四个距离的环形缓冲区必须先用 C1 中的距离重新填充, 然后才能用于编码 C1 中的其他距离. 注意, 产生 C0 和 C1 的两个压缩器必须使用相同窗口大小, 但流头部仅由产生 C0 的压缩器发出.

注意, 该方法可以很容易地推广到多于两个未压缩字节序列的情况.

Source: RFC 7932 Official Text: https://www.rfc-editor.org/rfc/rfc7932.txt

最后于 更新