在 (HCLEN + 4) x 3 位之后解码放气块

Question

所以在 deflate 算法中，每个块都以 3 位开始 header:

     Each block of compressed data begins with 3 header bits
     containing the following data:

        first bit       BFINAL
        next 2 bits     BTYPE

假设BTYPE为10（动态霍夫曼编码压缩）则接下来的14位如下：

           5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286)
           5 Bits: HDIST, # of Distance codes - 1        (1 - 32)
           4 Bits: HCLEN, # of Code Length codes - 4     (4 - 19)

接下来的 (HCLEN + 4) x 4 位表示代码长度。

之后发生的事情我不太清楚。

RFC1951 § 3.2.7。使用动态霍夫曼编码 (BTYPE=10) 的压缩是这样说的：

           HLIT + 257 code lengths for the literal/length alphabet,
              encoded using the code length Huffman code

           HDIST + 1 code lengths for the distance alphabet,
              encoded using the code length Huffman code

在 1589c11100000cc166a3cc61ff2dca237709880c45e52c2b08eb043dedb78db8851e 上执行 infgen -ddis（通过执行 gzdeflate('A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_BED') 生成）给出：

zeros 65                ! 0110110 110
lens 3                  ! 0
lens 3                  ! 0
lens 4                  ! 101
lens 3                  ! 0
lens 3                  ! 0
zeros 25                ! 0001110 110
lens 3                  ! 0
zeros 138               ! 1111111 110
zeros 22                ! 0001011 110
lens 4                  ! 101
lens 3                  ! 0
lens 3                  ! 0
zeros 3                 ! 000 1111
lens 2                  ! 100
lens 0                  ! 1110
lens 0                  ! 1110
lens 2                  ! 100
lens 2                  ! 100
lens 3                  ! 0
lens 3                  ! 0

我注意到 65 是 ASCII 中“A”的十六进制编码，这大概解释了“zeros 65”。

"lens"出现16次，等于HCLEN + 4.

在 RFC1951 § 3.2.2 中。在“deflate”格式中使用霍夫曼编码是这样的：

     2)  Find the numerical value of the smallest code for each
         code length:

            code = 0;
            bl_count[0] = 0;
            for (bits = 1; bits <= MAX_BITS; bits++) {
                code = (code + bl_count[bits-1]) << 1;
                next_code[bits] = code;
            }

也许这就是“zeros 65”的含义，但是“zeros 25”、“zeros 138”和“zeros 22”又如何呢？ ASCII 中的 25、138 和 22 不会出现在压缩文本中。

有什么想法吗？

Answer 1

接下来的 (HCLEN + 4) x 3 位表示代码长度。

lens的数量与HCLEN无关。 zeros和lens的序列表示269（259+10）literal/length和距离码的码长。如果将零和 lens 的数量相加，您将得到 269。

零长度符号表示它不会出现在压缩数据中。 0..64 范围内的数据中没有文字字节，因此它以 65 个零开头。编码的第一个符号是 'A'，长度为 3.

在 (HCLEN + 4) x 3 位之后解码放气块

decoding deflate blocks after (HCLEN + 4) x 3 bits

deflate