如何手动解压压缩包(雾)--GZ文件格式详解

如何手解压缩包（雾）–GZIP 文件结构

概述

一个GZIP文件主体分为三个部分,如下图所示：

1
[header][deflate block|...][header]

其中头部是元数据，中间是deflate的压缩数据块，尾部是固定8byte的元数据，接下来具体详细地介绍这三个部分。

和其他格式一样，Gzip文件的头部定义了该文件的元数据信息。该部分的长度不固定，至少10byte大小，其格式如下表所示：

Offset Size(byte) Description
0 2 .gz格式的魔数，一定为0x1f 0x8b
2 1 使用的压缩算法，0x8表示使用deflate，其他值暂时不合法
3 1 File flag
4 4 时间戳
8 1 压缩flag
9 1 操作系统flag,3表示unix
10 未知 依据File flag的格式而定

这个flag定义了header中超过10字节的部分的含义，依据不同的值，其表示的含义也不同。一般来说File flag的值都是0x08，表示了header中10byte偏移之后的部分是文件名（使用C风格字符串表示，读到0为止）。

Deflate Block

紧接着header之后的就是Deflate压缩块序列。

注意

  1. 这里讨论的是动态霍夫曼编码压缩块的结构，静态和不压缩的deflate block由于比较简单这里不再详述，感兴趣的读者可以参考相关RFC。
  2. 在读取相关信息时要提前将数据流以字节单位的小端序处理。如读出来的内容是 111110000 11001111....,后面实际进行处理的序列为00001111 11110011。
  3. deflate压缩块之间和都不会进行字节对齐。

概述

一个deflate压缩块依次包含如下五个部分，每个部分之间不会进行字节对齐：

1
2
3
4
[ Deflate block metadata   ]
[ Huffman's code table     ]
[  encoded huffman table   ] 
[  Compressed content      ]

其中Deflate block metadata 给出了块内的一些元数据，而Huffman’s code table给出了解码霍夫曼编码表的编码表， encoded huffman table是被编码过的霍夫曼编码表，用于实际内容的解码，Compressed content就是实际的编码后的内容。

Deflate tree

为了能看懂整个压缩块的结构，这里需要首先介绍deflate使用的编码算法，该算法是huffman编码的一个变种，可以使用更少的信息构建一颗霍夫曼树，以下将这种变种的huffman树称之为deflate 树。

传统的霍夫曼编码表是这样的：

值 编码
2 01
3 001
4 000
… …

对于编码本身而言，霍夫曼编码唯一的规定是任意两个编码都不会构成前后缀的关系.

而deflate使用的编码表是这样的：

值 长度
2 3
3 1
4 2

可以看到，deflate编码表并没有规定每个值的具体编码，而是只规定了每个值的编码的长度。在deflate的规则下，算法能够根据每个值的长度信息计算处每个值的唯一编码且保证任意两个编码都不会构成前后缀关系。

deflate定义的额外规则如下所示：

  • 对于同编码长度的所有值，它们的编码按照值的大小依次递增。举个例子，如果规定值2 4 3的编码都是3位，且2的编码是000的话，那么3的编码是000+1 = 001，4的编码值是000+2=010。
  • n位长的最小编码的值等于n-1位长的编码的最大值加上1然后左移一位。接着上面的例子，如果规定1，5的编码长度是4位，那么1的编码就是(010+1)<<1 =0110

在以下两条规则下，程序就能根据每个值的编码长度为每个值定义编码了。下面举个例子来复现上述过程，如果定义字符1 2 3 4 5 6 7 8这8个字符的编码长度分别为3 3 3 3 3 2 4 4，那么编码计算过程如下所示：

  1. 统计每种长度的编码出现的次数：

    1
    2
    3
    4
    5
     N   值     		出现次数
    -  ------ 		--------
    2    6      		1
    3    1 2 3 4 5      5
    4    7 8            2

  2. 依据规则2计算每种长度内的最小编码

    这里每种长度的最小编码就是计算6 1 7的编码(分别为 2 3 4位下的最小值)。

    计算过程如下所示

    1. 首先定义1位长度的最大编码为0
    2. 2位的最小编码为(1+1) << 1 = 0 << 1 = 00 ，2位的最大编码也是00(只有6这一个数字，最大最小也一样)
    3. 3位的最小编码为(00+1)<<1 = 01 <<1 = 010,3位的最大编码位010+5-1=110
    4. 4位的最小编码为(110+1)<<1 = 1110

  3. 依据规则1计算其它编码，得到的表如下所示：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Symbol Length   Code
    ------ ------   ----
    1       3        010
    2       3        011
    3       3        100
    4       3        101
    5       3        110
    6       2         00
    7       4       1110
    8       4       1111

在介绍上面的算法后就能看懂deflate压缩块的结构了。

如果不清楚细节的话至少需要明确一点：一个编码表是一个<值，编码长度>的列表。

Deflate block metadata

块内元数据这一部分固定只有1+2+5+5+4=17个bit，下表给出了这个17个bit每一部分的偏移，大小和含义。

偏移
(相当当前块的开头)		 符号表示 大小(bit) 描述
0 BFINAL 1 当前是否为最后一个deflate块
1 BFINAL 2 压缩类型
3 HLIT 5 字面量/长度编码的个数-257
8 HDIST 5 距离编码的个数-1
13 HCLEN 4 霍夫曼表编码的个数-4

注意读取这些数据后要进行反向，如读出来压缩类型是01时要反向成为10

压缩类型一共有4个值：

  • 00 不压缩
  • 01 使用内置的霍夫曼编码做压缩
  • 10 使用动态霍夫曼编码进行压缩
  • 11 保留不使用

HLIT，HDIST，HCLEN这三个值定义了各种情况下需要读出的编码个数，用到时再详细解释。

Huffman’s code table

该部分的长度为(HCLEN+4)*3 bit.

这部分是用于解码霍夫曼编码表的编码表。由于RFC规了这个编码表面的值(值是什么含义看后面)序列固定为

1
16, 17, 18,0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15

因此压缩快中只给出了上述序列前(HCLEN+4)个值对应的编码长度，每个长度信息固定为3bit。

举个例子,如果HCLEN = 8,那么我们就需要从块内读取(8+4)*3=36个bit且如下所示，形成如下的编码表(码长需要逆转编码)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Bit 码长	值
011	6	16
111	7	17
111	7	18
110	3	0
110	3	8
010	2	7
110	3	9
110	3	6
001	4	10
001	4	5
101	5	11
001	4	4

得到这张码表后就能根据上文提到的算法算出每一个值的编码：

1
2
3
4
5
6
7
8
9
10
11
12
010: 0
1100: 4
1101: 5
011: 6
00: 7
100: 8
101: 9
1110: 10
11110: 11
111110: 16
1111110: 17
1111111: 18

这张表会用于后续霍夫曼编码表读取。

encoded huffman table

到了这里终于可以读取霍夫曼编码表了，该表分字面量/长度编码表和距离编码表两个部分，其编码个数分别为HLIT+257以及HDIST+1。

字面量/长度编码表

使用上一节提供的编码表遍历接下来的字节流，并生成一个编码长度序列L，该序列的生成规则如下所示：

  1. 如果值x在0-15内，那么往L中加入x即可
  2. 如果值x == 16,那么需要往后读2bit的扩展值e，并将L内的最后一个值重复(e+3)次
  3. 如果值x == 17,那么需要往后读3bit的扩展值e,并往L中加入(e+3)个0
  4. 如果值x==18,那么需要往后读7bit的扩展值e,并往L中加入(e+11)个0

直到序列长度为HLIT+257为止。

这个HLIT+257长度的值就是[0, HLIT+257)这些值的编码长度。

也就是说，字面量/长度编码表如下所示：

值 长度
0 L[0]
1 L[1]
… …
n L[n]
… ….

使用这个表便可以构造[0,HLIT+257)中非0值的编码。

距离编码表

在读完字面量/长度编码表后，使用完全相同的方法读取HDIST+1个编码长度即可。形成的编码表和上方完全相同。

使用这个表便可以构造[0,HDIST+1)中非0值的编码。

Compressed content

到目前为止终于读出并计算出来两类数据的编码了。下面介绍如何根据这两种霍夫曼编码来读取实际的内容。

这部分比较简单，使用字面量/长度编码从压缩块中读数据，从上文可知，这个数据x的范围是[0,HLIT+257)，对于该数据的大小，我们做如下判定：

  • 如果0 <= x <= 255，我们认为它是一个ascii字符，作为LZ7编码串的字面量部分存在

  • 如果257<=x<HLIT+257,我们认为这是一个匹配对的距离，并根据x的值读取不同长度的扩展位以计算具体的长度下，每个值对应的扩展位的长度如下表所示：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    Extra               Extra               Extra
    Code Bits Length(s) Code Bits Lengths   Code Bits Length(s)
    ---- ---- ------     ---- ---- -------   ---- ---- -------
    257   0     3       267   1   15,16     277   4   67-82
    258   0     4       268   1   17,18     278   4   83-98
    259   0     5       269   2   19-22     279   4   99-114
    260   0     6       270   2   23-26     280   4  115-130
    261   0     7       271   2   27-30     281   5  131-162
    262   0     8       272   2   31-34     282   5  163-194
    263   0     9       273   3   35-42     283   5  195-226
    264   0    10       274   3   43-50     284   5  227-257
    265   1  11,12      275   3   51-58     285   0    258
    266   1  13,14      276   3   59-66

    举个例子，如果x = 273,那么我们需要往后读3bit的值e，然后e+35作为这个匹配对的长度len

    读取完拓展1位后需要使用距离编码读取这个匹配对的距离d，并根据d取值的不同读取相应的扩展位以计算具体的长度，每个d值对应的扩展位以及计算方法如下所示：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    Extra           Extra               Extra
    Code Bits Dist  Code Bits   Dist     Code Bits Distance
    ---- ---- ----  ---- ----  ------    ---- ---- --------
    0   0    1     10   4     33-48    20    9   1025-1536
    1   0    2     11   4     49-64    21    9   1537-2048
    2   0    3     12   5     65-96    22   10   2049-3072
    3   0    4     13   5     97-128   23   10   3073-4096
    4   1   5,6    14   6    129-192   24   11   4097-6144
    5   1   7,8    15   6    193-256   25   11   6145-8192
    6   2   9-12   16   7    257-384   26   12  8193-12288
    7   2  13-16   17   7    385-512   27   12 12289-16384
    8   3  17-24   18   8    513-768   28   13 16385-24576
    9   3  25-32   19   8   769-1024   29   13 24577-32768

    举个例子，如果d = 9,那么我们需要往后读3bit的值e，然后e+25作为这个匹配对的匹配距离distance

    读取完<len,distance>后这部分就结束了

  • 如果x == 256表示这个gzip压缩块结束了。

在读完最后一个压缩块后，就进入了footer部分，由于压缩块不是字节对齐的，因此这里需要往后填充1-7个0直到字节对齐然后读取footer。footer固定为8byte,其中前4byte为文件的CRC32校验码，后4字节为原始未压缩文件的大小。

参考资料

  1. RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3 (ietf.org)
  2. Dissecting the GZIP format (commandlinefanatic.com)
  3. A Completely Dissected GZIP File (commandlinefanatic.com)
  4. gzip实现源代码分析 (ustc.edu.cn)
  5. https://docs.fileformat.com/compression/gz/