有了文件的格式&＃xff0c;就可以按图索骥&＃xff0c;也就是根据文件的格式来分析压缩数据了。但文件格式只是一种存储的格式&＃xff0c;还需要算法才可以把数据解压出来&＃xff0c;下面就来理解gzip的压缩算法。gzip使用deflate的压缩算法来进行压缩数据&＃xff0c;这是一种无损的压缩算法&＃xff0c;主要组合LZ77和Huffman的压缩算法。
LZ77算法是基于这样的思路&＃xff1a;当一串字符中&＃xff0c;如果后面的字符串已经在前面出现&＃xff0c;那么后面的字符串只需要使用前面的位置和长度就表达相同的字符串&＃xff0c;从而达到字符串使用最少的空间。现在看一个简单的例子&＃xff0c;如下的字符串&＃xff1a;
AABABBBABAABABBBABBABB
在这个串中可以这样表示&＃xff0c;第一个块A写作&＃xff08;0&＃xff0c;A&＃xff09;&＃xff0c;第二个块AB&＃xff0c;就可以表达为索引和字母的方式&＃xff08;1&＃xff0c;B&＃xff09;&＃xff0c;依这样的编码&＃xff0c;就可以得到下面的表格&＃xff1a;
索引 块 压缩后表示
1 A (0,A)
2 AB (1,B)
3 ABB (2,B)
4 B (0,B)
5 ABA (2,A)
6 ABAB (5,B)
7 BB (4,B)
8 ABBA (3,A)
9 BB (7,0)
通过这样压缩处理后&＃xff0c;就可以减少原来字符串的大小&＃xff0c;并且没有数据损失。
Huffman算法是基于这样的思路&＃xff1a;当一串字符中&＃xff0c;如果某个字符出现的频率越高就使用最短的编码记号&＃xff0c;频率越低的就使用最长的编码记号&＃xff0c;经过这样编码后达到压缩的目的。可见Huffman算法是基于统计学来压缩的&＃xff0c;因此存在码表和统计的过程。不过&＃xff0c;Huffman算法也可以采用比较常见的预先定制静态码表来使用&＃xff0c;这样就不需要统计的过程了&＃xff0c;这种算法叫做静态Huffman算法&＃xff0c;反之叫做动态Huffman算法。
有了上面的基础&＃xff0c;就可以来学习gunzip函数的代码了&＃xff0c;这个函数的代码如下&＃xff1a;
/*
*Do the uncompression!
*/
staticint INIT gunzip(void)
{
uch flags;
unsigned char magic[2]; /* magicheader */
char method;
ulg orig_crc &＃61; 0; /* originalcrc */
ulg orig_len &＃61; 0; /* originaluncompressed length */
int res;
magic[0] &＃61; NEXTBYTE();
magic[1] &＃61; NEXTBYTE();
这两行代码是获取GZIP压缩的标识字母&＃xff0c;用来识别是否GZIP文件的格式。
method &＃61; NEXTBYTE();
这行代码是获取什么方式解压&＃xff0c;这里使用DEFATED方式。
if (magic[0] !&＃61; 037 ||
((magic[1]!&＃61; 0213) && (magic[1] !&＃61; 0236))) {
error("bad gzip magic numbers");
return -1;
}
这段代码是判断是否GZIP格式。
/* We only support method #8,DEFLATED */
if (method !&＃61; 8) {
error("internal error, invalid method");
return -1;
}
这段代码是判断是否为DEFLATED压缩方式。
flags &＃61; (uch)get_byte();
if ((flags & ENCRYPTED) !&＃61; 0) {
error("Input is encrypted");
return -1;
}
if ((flags & CONTINUATION) !&＃61; 0){
error("Multi part input");
return -1;
}
if ((flags & RESERVED) !&＃61; 0) {
error("Input has invalid flags");
return -1;
}
这段代码是判断是否使用特殊的标志压缩&＃xff0c;如果有用就不能执行&＃xff0c;因为这里解压代码比较简单。
NEXTBYTE(); /* Get timestamp */
NEXTBYTE();
NEXTBYTE();
NEXTBYTE();
这段代码跳过四个压缩数据时的时间。
(void)NEXTBYTE(); /* Ignore extraflags for the moment */
(void)NEXTBYTE(); /* Ignore OS typefor the moment */
这段代码是跳过额外的标志和操作系统类型。
if ((flags & EXTRA_FIELD) !&＃61; 0) {
unsigned len &＃61; (unsigned)NEXTBYTE();
len |&＃61; ((unsigned)NEXTBYTE())<<8;
while (len--) (void)NEXTBYTE();
}
这段代码把所有额外字段跳过&＃xff0c;不作任何处理。
/* Get original file name if it wastruncated */
if ((flags & ORIG_NAME) !&＃61; 0) {
/* Discard the old name */
while (NEXTBYTE() !&＃61; 0) /* null */ ;
}
这段代码跳过原来压缩文件的名称。
/* Discard file comment if any */
if ((flags & COMMENT) !&＃61; 0) {
while (NEXTBYTE() !&＃61; 0) /* null */ ;
}
这段代码是跳过所有注释的字符。
/* Decompress */
if ((res &＃61; inflate())) {
switch (res) {
case 0:
break;
case 1:
error("invalid compressed format (err&＃61;1)");
break;
case 2:
error("invalid compressed format (err&＃61;2)");
break;
case 3:
error("out of memory");
break;
case 4:
error("out of input data");
break;
default:
error("invalid compressed format (other)");
}
return -1;
}
这段代码是调用inflate来进行数据解压。
/* Get the crc and original length */
/* crc32 (see algorithm.doc)
* uncompressed input size modulo 2^32
*/
orig_crc &＃61; (ulg) NEXTBYTE();
orig_crc |&＃61; (ulg) NEXTBYTE() <<8;
orig_crc |&＃61; (ulg) NEXTBYTE() <<16;
orig_crc |&＃61; (ulg) NEXTBYTE() <<24;
这段代码是获取原来的CRC32检验码&＃xff0c;以便跟解压出来的数据计算的CRC32检验码比较。
orig_len &＃61; (ulg) NEXTBYTE();
orig_len |&＃61; (ulg) NEXTBYTE() <<8;
orig_len |&＃61; (ulg) NEXTBYTE() <<16;
orig_len |&＃61; (ulg) NEXTBYTE() <<24;
这段代码是获取压缩之前数据长度。
/* Validate decompression */
if (orig_crc !&＃61; CRC_VALUE) {
error("crc error");
return -1;
}
if (orig_len !&＃61; bytes_out) {
error("length error");
return -1;
}
这段代码是检查CRC32是否对&＃xff0c;解压后长度与压缩前的长度是否一致。
return 0;
underrun: /* NEXTBYTE() goto&＃39;s hereif needed */
error("out of input data");
return -1;
}
京公网安备 11010802041100号