跳到主要内容

4. 距离的编码 (Encoding of Distances)

4. 距离的编码 (Encoding of Distances)​

如 Section 2 所述, compressed meta-block 的一个组成部分是一系列向后距离 (backward distance). 本节提供 distance 编码的细节.

meta-block 的 compressed data part 中的每个 distance 都用一个 <distance code, extra bits> 对表示. distance code 和 extra bits 前后相接编码. distance code 使用 distance alphabet 上的 prefix code 编码, 而 extra bits 值编码为固定宽度整数值. extra bits 的数量可以为 0..24, 且取决于 distance code.

为了把 distance code 及其关联的 extra bits 转换为 backward distance, 我们需要 past distance 序列和两个附加参数: "postfix bits" 的数量, 记为 NPOSTFIX (0..3), 以及 direct distance code 的数量, 记为 NDIRECT (0..120). 这两个参数都编码在 meta-block header 中. 我们还将使用以下派生参数:

   POSTFIX_MASK = (1 `<<` NPOSTFIX) - 1

前 16 个 distance symbol 是引用 past distance 的特殊符号, 如下:

   0: last distance
   1: second-to-last distance
   2: third-to-last distance
   3: fourth-to-last distance
   4: last distance - 1
   5: last distance + 1
   6: last distance - 2
   7: last distance + 2
   8: last distance - 3
   9: last distance + 3
  10: second-to-last distance - 1
  11: second-to-last distance + 1
  12: second-to-last distance - 2
  13: second-to-last distance + 2
  14: second-to-last distance - 3
  15: second-to-last distance + 3

四个 last distance 的 ring buffer 在 stream 开始处初始化为 16, 15, 11 和 4 (也就是说, fourth-to-last 设置为 16, third-to-last 设置为 15, second-to-last 设置为 11, last distance 设置为 4), 而不是在 meta-block 开始处初始化, 且不会在 meta-block 边界重置. 当出现 distance symbol 0 时, 它表示的 distance (即 distance 序列中的 last distance) 不会被压入 last distance 的 ring buffer. 换言之, 表达式 "second-to-last distance" 表示不是由 0 distance symbol 表示的倒数第二个 distance ("third-to-last distance" 和 "fourth-to-last distance" 也类似). 同样, 表示静态字典词的 distance (见 Section 8) 不会被压入 last distance 的 ring buffer.

如果一个特殊 distance symbol 解析为零或负值, 则应将该 stream 拒绝为无效.

如果 NDIRECT 大于零, 则接下来的 NDIRECT 个 distance symbol, 从 16 到 15 + NDIRECT, 表示从 1 到 NDIRECT 的 distance. 特殊 distance symbol 和 NDIRECT direct distance symbol 后面都不跟随任何 extra bits.

distance symbol 16 + NDIRECT 及更大的符号都有 extra bits. 对于 distance symbol "dcode", extra bits 的数量由以下公式给出:

   ndistbits = 1 + ((dcode - NDIRECT - 16) >`> (NPOSTFIX + 1))

extra bits 的最大数量为 24; 因此, distance symbol alphabet 的大小为 (16 + NDIRECT + (48 << NPOSTFIX)).

给定 distance symbol "dcode" (>`= 16 + NDIRECT) 和 extra bits "dextra", backward distance 由以下公式给出:

     hcode = (dcode - NDIRECT - 16) >> NPOSTFIX
     lcode = (dcode - NDIRECT - 16) & POSTFIX_MASK
     offset = ((2 + (hcode & 1)) << ndistbits) - 4
     distance = ((offset + dextra) << NPOSTFIX) + lcode + NDIRECT + 1

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

最后于 更新