位操作

好了,前面两个章节我们简要的阐述了一下huffman和lz77压缩算法,那么前期的基础准备工作也算基本做完了,现在我们正式进入DEFLATE麻烦的部分.

在此之前,我们先简略对位操作做个定义,众所周知,一字节为8个bits,如果我们将二进制位视作一个流式的过程,我们从左到右依次写入 1010 0101 1111 0000 那么是怎么样的呢?

我们定义,流式的二进制写入从低位开始,然后是高位,直到写满8字节,再到第二个字节里的低位开始写,因此,上述二进制bits写入后,按一般的低位在右,高位在左的表达方式,上面的二进制流在字节流一般表示为


1010	0101	0000	1111
A	5	0	F

即字节序列A5 0F

我们定义2个函数ReadBits(x,b)和WriteBits(x,b),其中ReadBits(x,b)表示从缓存区x中流式的读取b个bits
同样的,先读取到的比特会放入字节的低位,后读到的放入高位,WriteBit表示写入二进制位,x是一个字节流,b表示写入的位数,例如WriteBits(5,3)表示写入101.

压缩方式速读

Deflate的压缩是分块压缩的,什么意思捏,例如你想要压缩数据100字节,Deflate压缩可能会把它分成3个块,第一个块压缩20个字节,第二个块压缩30字节,第三个块压缩50字节

如果我们把每个块的字节序列表示成x,那么,x的第一个bit表示这个是不是最后一个块

ReadBits(x,1)	意义
0	不是最后一个block
1	最后一个block

紧接着接下来2个bits表示这个block的压缩方式

ReadBits(x,2)	意义
0	无压缩
1	固定huffman压缩
2	动态huffman压缩

观众朋友可以要问了,为什么有三种方式呢,显然的,范式huffman树的bit length本身也要占用空间,如果一段数据的信息熵很高,那么huffman压缩后加上存储bit length比原数据还大,那还不如不压缩,固定huffman是内置的bit length编码,可能会比不压缩稍微好一点,但有时也会压得比原数据还大,第三种就是存储范式huffman bit length,总的来说,三种压缩方式中,我们选取压缩率最低的,以获取更优压缩率.

无压缩编码格式

无压缩格式的解析是三种中最简单的格式

当你读完前3个bits之后,跳过之后的5个没有实际意义的bits凑够1字节,之后你就可以读取无压缩block的长度了,如下表所示

Block第1个字节	第二个字节	第三个字节
前3 bits为压缩方式	无压缩数据低位	无压缩数据高位

如果我们用block[]数组表示Block的字节序列,那么,无压缩数据的长度len可以表示为
len=block[1]+(block[2]<<8)
接下来我们还要继续读取第三第四个字节并将它拼接为nlen
nlen=block[3]+(block[4]<<8)
其中
len+nlen须等于65535
之后就只需要根据len读取后面的字节,这些字节都是无压缩的,不需要额外的处理

LZ77压缩后的数据

在讨论完无压缩编码格式后,下面将要讨论的固定huffman压缩和动态huffman压缩,都是处理LZ77压缩后的数据

在deflate中的symbol是以字节为单位的,而1字节8位,其范围是0-255,但除了0-255,我们还需要存储lz77压缩后的(长度,位置),因此我们每一个数据还得继续扩大,并给予大于255的数值一些额外的意义

在DEFLATE中,我们把每一个数字叫做lz77_code

注意!注意!注意!这里有一个重点

DEFLATE的编码/解码使用2套不同的huffman tree,我们分别把它们叫literal tree和 distance tree,前面那个tree用于编码0-285的lz77_code,后面那个tree比较小,编码一个0-30的lz77_code,它仅在指示lz77的(length,distance)时会被用到

在解码开始时,我们先用literal tree对原比特流进行解码,得到一个lz77_code,当:

lz77_code=256时表示这段数据的结束,也就是当你读到256时,表示这个Block已经解压缩完成了

lz77_code大于256小于286的数据,表示这是一个LZ77的(长度 length,位置距离 distance)指示器(不明白的请翻阅前一章节内容),要求其长度和距离怎么办呢,在这之前,我们需要先打4张表,它们分别是

//长度表
unsigned int length_table[29] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,67, 83, 99, 115, 131, 163, 195, 227, 258};

unsigned int  length_extra[29] = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5,5, 5, 5, 0};

//距离表
unsigned int  distance_table[30] = {1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577};

unsigned int  distance_extra[30] = {0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,11, 11, 12, 12, 13, 13};

为了方便说明,让我们举一个例子怎么通过lz77_code求解出(length,distance),我们假设通过literal tree解码得到的:
lz77_code=265;
1.index=lz77_code-257; 显然的,index=8
2.length=length_table[index]; 读取长度的第一部分,参照第一个长度表
3.length=length+PX_ReadBits(x,length_extra[index]); 通过查第二个表得知,length_extra[8]还有1个bit,因此我们再读取1个bit,并加到length上,最终得到完整的length
4.注意,然后通过distance tree继续读取下一个lz77_code
5.index=lz77_code;
6.distance=distance_table[index];//和length表类似的做法
7.distance=distance+PX_ReadBits(x,distance_extra[index]);//如上,得到最终的distance

这样我们最终就能得到完整的lz77压缩数据了

固定huffman压缩

固定huffman压缩顾名思义,即huffman的code和bit length是固定的,这类huffman会基于统计意义生成一个尽可能适合大部分数据编码的huffman树,这样就能够节省保存huffman树结构的空间.

那么,这个huffman树的 symbol(下表中的lit value),bits length(下表中的 bits),code (下表中的codes)对照图如下所示

Huffman树

如果你不太明白,c语言构造代码如下

px_void PX_HuffmanBuildFixedSymbolTable(px_dword code_table[288], px_dword code_bit_length[288])
{
	px_dword i,t;
	t = 0;
	for (i=48;i<=191;i++)
	{
		code_bit_length[t] = 8;
		code_table[t] = i;
		t++;
	}


	for (i = 400; i <= 511; i++)
	{
		code_bit_length[t] = 9;
		code_table[t] = i;
		t++;
	}


	for (i=0;i<=23;i++)
	{
		code_bit_length[t] = 7;
		code_table[t] = i;
		t++;
	}


	for (i = 192; i <= 199; i++)
	{
		code_bit_length[t] = 8;
		code_table[t] = i;
		t++;
	}

}

两个细节要点

注意! ReadBits是从低位开始向高位读的,但Huffman Code是从高位开始向低位读的,例如,我们读取到了一个Code的二进制表示为 100,那么我们要对其进行huffman树的编码解码,读取到的第一个bit是最左边的1而不是最右边的0,至于1表示树的坐标还是右边,这个倒并不重要并不会影响编码或解码的结果.

注意!symbol(上面中的lit value)范围是0-287,但动态huffman的值范围是0-285,其中286,287并用不到,但是!如果在存储动态huffman的过程中,literal tree的bits_length_table长度超过286,那么在调用Zlib进行解码的库中,将会直接报错!