gzip-1.2.4程序分析- -
《algorithm.doc文件的部分翻譯》和《gzip-1.2.4程序分析》
2 bytes GZIP標志字節：0x1f, 0x8b (\037 \213)
1 byte 壓縮方法： (0..7 reserved, 8 = deflate)
1 byte 標志位：
bit 0 set: 文件可能是ASCII文本文件
bit 1 set: 附加多個(gè)gzip文件部分
bit 2 set: 存在有可選的附加 內容
bit 3 set: 提供了原始的文件名稱(chēng)
bit 4 set: 則提供有一個(gè)O－終結的文件內容
bit 5 set: 文件被加密
bit 6,7: 保留
4 bytes 文件更改時(shí)間(Unix時(shí)間)
1 byte 額外的標志，決定了壓縮方法。 2:使用最大的壓縮，最慢的算法
4:采用最快的算法
1 byte 這個(gè)標志指明了進(jìn)行壓縮時(shí)系統的類(lèi)型。
0 - FAT filesystem (MS-DOS, OS/2, NT/Win32)
1 - Amiga
2 - VMS (or OpenVMS)
3 - Unix
4 - VM/CMS
5 - Atari TOS
6 - HPFS filesystem (OS/2, NT)
7 - Macintosh
8 - Z-System
9 - CP/M
10 - TOPS-20
11 - NTFS filesystem (NT)
12 - QDOS
13 - Acorn RISCOS
255 - unknown
2 bytes optional part number (second part=1) 可選的序號
2 bytes optional extra field length 可選的附加內容的長(cháng)度
bytes optional extra field 可選的附加內容
bytes optional original file name, zero terminated
可選的原始文件名稱(chēng)，以'\0'結束
bytes optional file comment, zero terminated
可選文件內容(這部分不被解釋?zhuān)强勺x的供人使用的，以'\0'結束
12 bytes optional encryption header
bytes compressed data
4 bytes crc32 這個(gè)是未壓縮數據的循環(huán)冗余校驗值。
4 bytes uncompressed input size modulo 2^32 這是原始數據的長(cháng)度以2的32次方為模的值。
設計了一種可以單向編碼的格式，而不用反向查找，也不用預知未壓縮數據及輸出的
已壓縮數據的大小。如果輸入的數據不是一個(gè)文件，那么修改時(shí)間被設置為壓縮的開(kāi)
始時(shí)間。
The format was designed to allow single pass compression without any
backwards seek, and without a priori knowledge of the uncompressed
input size or the available size on the output media. If input does
not come from a regular disk file, the file modification time is set
to the time at which compression started.
時(shí)間戳主要是用在在網(wǎng)絡(luò )上傳輸gzip文件的情況下。在這種情況下，它不需要保存所有
者的屬性。在本地傳輸的時(shí)候，所有者的屬性在壓縮/解壓縮時(shí)由gzip所保存。忽略值為
0的時(shí)間戳。
The time stamp is useful mainly when one gzip file is transferred over
a network. In this case it would not help to keep ownership
attributes. In the local case, the ownership attributes are preserved
by gzip when compressing/decompressing the file. A time stamp of zero
is ignored.
標志位中，值為0的位是可選的，它可以使我們對輸入的數據做一個(gè)預先的了解。在不
確定的時(shí)候，要將標志位清除。對有不同文件格式(文本文件和二進(jìn)制文件)的系統來(lái)說(shuō)，
解碼時(shí)，可以使用標志位來(lái)選擇不同的格式。
Bit 0 in the flags is only an optional indication, which can be set by
a small lookahead in the input data. In case of doubt, the flag is
cleared indicating binary data. For systems which have different
file formats for ascii text and binary data, the decompressor can
use the flag to choose the appropriate format.
如果有附加內容，則它必須包含一個(gè)或多個(gè)子字段，每個(gè)子字段有如下格式：
The extra field, if present, must consist of one or more subfields,
each with the following format:
subfield id : 2 bytes 子字段ID
subfield size : 2 bytes (little-endian format)子字段長(cháng)度(小端字節序)
subfield data 子字段內容
子字段ID可以包含兩個(gè)可記住的字母。請發(fā)送一些這樣的ID給jloup@chorus.fr.
第二個(gè)字節為0的ID是被保留的。定義了如下的ID
The subfield id can consist of two letters with some mnemonic value.
Please send any such id to jloup@chorus.fr. Ids with a zero second
byte are reserved for future use. The following ids are defined:
Ap (0x41, 0x70) : Apollo file type information
子字段長(cháng)度是子字段內容的長(cháng)度，不包含ID及子字段長(cháng)度這四字節。但是
前面所說(shuō)的
"可選的附加內容的長(cháng)度
"則包含了ID及子字段長(cháng)度的四字節。
The subfield size is the size of the subfield data and does not
include the id and the size itself. The field 'extra field length' is
the total size of the extra field, including subfield ids and sizes.
必須可以在壓縮數據中找到數據結束的位置，而不論數據的實(shí)際長(cháng)度是多少。如果壓縮
數據不能夠放到一個(gè)文件中(如磁盤(pán)的情況)，每一部分都要由一個(gè)頭字段開(kāi)始，但是只
有最后一部分中有CRC32和原始數據的長(cháng)度。 解壓程序應該可以提示輸入另外的，存在
于多個(gè)壓縮文件中的數據。這是必要，但不是絕對的，因為當一部分數據毀壞時(shí)，還需
要得到其它部分的內容。
It must be possible to detect the end of the compressed data with any
compression format, regardless of the actual size of the compressed
data. If the compressed data cannot fit in one file (in particular for
diskettes), each part starts with a header as described above, but
only the last part has the crc32 and uncompressed size. A decompressor
may prompt for additional data for multipart compressed files. It is
desirable but not mandatory that multiple parts be extractable
independently so that partial data can be recovered if one of the
parts is damaged. This is possible only if no compression state is
kept from one part to the other. The compression-type dependent flags
can indicate this.
如果壓縮文件的系統對文件名的大小寫(xiě)不敏感，則原始文件名會(huì )會(huì )強制轉換成小寫(xiě)。
如果是從標準輸入讀入的數據，則沒(méi)有原始文件名。
If the file being compressed is on a file system with case insensitive
names, the original name field must be forced to lower case. There is
no original file name if the data was compressed from standard input.
即使壓縮后的文件會(huì )比原來(lái)的文件大，壓縮還是會(huì )完成的。
Compression is always performed, even if the compressed file is
slightly larger than the original. The worst case expansion is
a few bytes for the gzip file header, plus 5 bytes every 32K block,
or an expansion ratio of 0.015% for large files. Note that the actual
number of used disk blocks almost never increases.
The encryption is that of zip 1.9. For the encryption check, the
last byte of the decoded encryption header must be zero. The time
stamp of an encrypted file might be set to zero to avoid giving a clue
about the construction of the random header.
一點(diǎn)說(shuō)明：
在gzip.c中：
DECLARE(uch, inbuf, INBUFSIZ +INBUF_EXTRA);
DECLARE(uch, outbuf, OUTBUFSIZ+OUTBUF_EXTRA);
DECLARE(ush, d_buf, DIST_BUFSIZE);
DECLARE(uch, window, 2L*WSIZE);
#ifndef MAXSEG_64K
DECLARE(ush, tab_prefix, 1L<<BITS);
#else
DECLARE(ush, tab_prefix0, 1L<<(BITS-1));
DECLARE(ush, tab_prefix1, 1L<<(BITS-1));
#endif
實(shí)際上定義了一些數組：inbuf,outbuf,d_buf,window,tab_prefix,tab_prefix0,tabfix1.
1/
==================================================================================
入口程序：gzip-1.2.4/gzip.c
函數： int main (argc, argv)
int argc;
char **argv;
功能： 1)通過(guò)命令內容(gzip,gunzip,unzip等)，設置操作類(lèi)型(壓縮或是解壓縮)。
2)通過(guò)參數，設置一些全局變量的值，對我們而言，有用的是：ascii(表示
為文本文件，可以根據本地的換行符來(lái)代替解壓后的文件中的換行符)、decompress(表示進(jìn)行解壓操作)和level(轉換操作的級別
—進(jìn)行更快
的轉換還是進(jìn)行更大壓縮比的轉換，當然，這只對壓縮而言)。
3)為輸入、輸出及窗口的緩沖分配內存。
4)調用treat_file(argv[optind++]);對文件進(jìn)行操作。
2/
==================================================================================
函數： local void treat_file(iname)
char *iname;
參數： 為文件名稱(chēng)；
功能： 1)得到輸入的文件的狀態(tài)：name,size,time,mode等。
2)創(chuàng )建輸出文件的名稱(chēng)。
3)當進(jìn)行解壓操作時(shí)，調用 local int get_method(in) 來(lái)得到gz文件的壓縮方法。
4)如果命令行中的參數-l，則調用do_list()顯示文件信息。
5)調用local int create_outfile()創(chuàng )建輸出文件。
6) 調用(*work)(ifd, ofd)進(jìn)行壓縮、解壓縮的操作。這時(shí)的work指針被get_method()
函數置為unzip()函數(解壓時(shí))，或是為默認的zip()函數。在解壓縮時(shí)，
這個(gè)過(guò)程是在循環(huán)中的，因為可能會(huì )包含多個(gè)文件。
3/
==================================================================================
函數： local int get_method(in)
int in; /* input file descriptor */
參數： 文件名稱(chēng)
功能： 1)驗證第一第二字節是否為0x1F,0x8B。
2)驗證第三字節是否為0x08(deflate)。
3)設置函數指針work = unzip。(work的默認值是zip)
4)得到做為flags的第四字節。
5)如果設置了第1、5、6、7位，則給出錯誤提示。(編號0到7是從最低位開(kāi)始)
6)將第5到8字節中的時(shí)間值保存在全局變量time_stamp中。
7)跳過(guò)第9字節(壓縮時(shí)采用的算法
—更快或是比例更高)和
第10字節(壓縮時(shí)的操作系統)。
8)如果設置了flags的第1位，則得到當前文件的編號
9)如果設置了flags的第2位(存在有附加的內容)，則得到附加內容的長(cháng)度，
并跳過(guò)這部分內容。
10)如果設置了flags的第3位(存在有原始文件的名稱(chēng))，則得到原始文件的名稱(chēng)。
11)如果設置了flags的第4位(存在一段不用解析的內容，是給人提供可讀信息的)，
跳過(guò)這部分可讀信息。
12) 設置頭部信息的長(cháng)度：header_bytes，包括了最后的CRC及文件長(cháng)度部分。
返回： 函數壓縮方法(一般為"deflate
"，程序中的返回值為8)
4/
==================================================================================
在文件gzip-1.2.4/unzip.c中：
函數： int unzip(in, out)
int in, out; /* input and output file descriptors */
參數：為輸入、輸出文件。
功能： 1)初始化全局變量crc。
2)調用函數inflate()進(jìn)行解碼操作。
3)得到原來(lái)文件中保存的CRC及長(cháng)度值。如果與當前計算出的值不同，則產(chǎn)生提示。
5/
==================================================================================
在文件gzip-1.2.4/inflate.c中：
函數： int inflate()
說(shuō)明： ulg bb; /* 是 bit buffer */
unsigned bk; /* 是bit buffer中還有多少位，即剩余的位數 */
功能： 1) 循環(huán)調用inflate_block(&e)，一塊一塊的解壓數據。
2)若bk>-8,即bb中有完整的字節，則將此字節放回輸入中。
3)輸出解壓得到的內容。
6/
==================================================================================
在文件gzip-1.2.4/inflate.c中：
函數： int inflate_block(e)
int *e; /* last block flag */
參數：如果是1，是說(shuō)明當前塊是最后一塊。
功能： 1)得到第一位，這一位說(shuō)明當前塊是否為最后一塊(0，不是；1，是)并相應的設置參數。
2)得到下兩位的值：
0，本塊沒(méi)有壓縮，
1，用固定的Huffman編碼壓縮，見(jiàn)RFC1951的3.2.6節。
2，用動(dòng)態(tài)的Huffman編碼壓縮，見(jiàn)RFC1951的3.2.7節。
3)根據前面得到的值，調用不同的函數解壓：
inflate_stored(); 對于未壓縮的數據，調用這個(gè)函數。
inflate_fixed(); 對于用固定的Huffman編碼壓縮的數據，調用這個(gè)函數。
inflate_dynamic(); 對于用動(dòng)態(tài)的Huffman編碼壓縮的數據，調用這個(gè)函數。
7/
==================================================================================
在文件gzip-1.2.4/inflate.c中：
函數： int inflate_stored()
功能： 處理非壓縮的數據內容
1)丟棄不足一字節的位。由于非壓縮的數據中，內容都是以字節為單位的，所以原來(lái)按
位讀取的時(shí)候，會(huì )剩余不足一字節位內容，現在要去掉這些位。
2)讀入兩字節的內容，其值是未壓縮的數據長(cháng)度。再讀入兩字節的內容，其值應該是前
兩字節所表示的長(cháng)度的補碼，若不是，則錯誤。
3)逐字節的讀入內容，并輸出到輸出文件中。
8/
==================================================================================
在文件gzip-1.2.4/inflate.c中：
函數： int inflate_fixed()
功能： 用固定的Huffman編碼壓縮的數據
1) 為0至287的文字/length值設定編碼長(cháng)度:
Lit Value Bits Codes
--------- ---- -----
0 - 143 8 00110000 through
10111111
144 - 255 9 110010000 through
111111111
256 - 279 7 0000000 through
0010111
280 - 287 8 11000000 through
11000111
2) 調用huft_build()建造文字/length值的Huffman樹(shù)
3) 設置所有distance值(從0至29)的編碼長(cháng)度為5。
4) 調用huft_build()建造distance值的Huffman樹(shù)
5) 調用函數inflate_codes()進(jìn)行解碼。
9/
==================================================================================
在文件gzip-1.2.4/inflate.c中：
函數： int inflate_dynamic()
功能： 用動(dòng)態(tài)的Huffman編碼壓縮的數據
1)讀入5位的值HLIT，算出nl = 257+HLIT。這是需要編碼的最大值。
2)讀入5位的值HDIST，算出nd = 1+HDIST。這是distance的最大值。
3)讀入4位的值HCLEN，算出nb = 4+HCLEN。說(shuō)明有多少種編碼長(cháng)度。
4)再讀入3*nb位，每三位的值表示用多少位來(lái)表示所對應的編碼長(cháng)度。
5)調用huft_build()建造編碼長(cháng)度的Huffman樹(shù)。
6)利用這個(gè)Huffman樹(shù)，對接下來(lái)的若干位解碼出nl+nd個(gè)值，這些值依次是0~nl-1
的編碼長(cháng)度(對于文字/length平說(shuō))，及0~nd-1的編碼長(cháng)度(對于distance來(lái)說(shuō))。
7)利用上面解碼出的兩組長(cháng)度值，兩次調用huft_build()函數，建造兩個(gè)Huffman樹(shù)
(一個(gè)是為文字/length，另一個(gè)是為distance)。
8)調用函數inflate_codes()進(jìn)行解碼。
10/
==================================================================================
在文件gzip-1.2.4/inflate.c中：
函數： int inflate_codes(tl, td, bl, bd)
struct huft *tl, *td; /* literal/length and distance decoder tables */
int bl, bd; /* number of bits decoded by tl[] and td[] */
參數： tl,td是進(jìn)行Huffman編碼解碼時(shí)用到的結構體，由于length和distance用不同的編碼
方式，所以要有兩個(gè)指針進(jìn)行解碼。
在兩種編碼中，用struct huft結構編碼時(shí)，分別以bl,bd位進(jìn)行編碼。
功能： 用兩個(gè)以經(jīng)做好的鏈表來(lái)進(jìn)行解碼。
1） 解碼一個(gè)值X，如果0<=X<=255，則X是一個(gè)字符，輸出，循環(huán)1）。
2） 如果X==255，則說(shuō)明塊結束，函數返回。
3） X>255，則說(shuō)明讀到的是一個(gè)length值，根據這個(gè)值，及其后的附加位，得到真實(shí)的
length值。
4） 繼續讀入一個(gè)值，這個(gè)值是distance的標志值，根據這個(gè)值及其后的附加位得到真實(shí)
的distance。
5） 在已經(jīng)輸出的串中，向前查找distance個(gè)字節，拷貝length個(gè)字節到輸出串的末尾。
6） 循環(huán)1）
11/
==================================================================================
在文件gzip-1.2.4/inflate.c中：
函數： int huft_build() 和函數int huft_free()比較獨立，可以直接引用，不再分析。
功能： int huft_build() ：建立Huffman解碼鏈表。
int huft_free() ：清除鏈表。
12/
==================================================================================
在文件gzip-1.2.4/zip.c中：
函數： int zip(in, out)
int in, out; /* input and output file descriptors */
參數：為輸入、輸出文件。
功能：
1） 向輸出寫(xiě)入三字節：0x1F 0x8B 0x08。
2） 向輸出寫(xiě)入一個(gè)含有8個(gè)標志位的字節。
3） 向輸出寫(xiě)入4字節的系統時(shí)間。
4） 初始化CRC的值。
5） 調用bi_init(out)初始化讀入位串的程序。
6） 調用ct_init()進(jìn)行分配內存，初始化變量表，保存原始文件信息的
操作。
7） 調用lm_init()為新文件初始化"最長(cháng)匹配"的程序。
8） 再向輸出寫(xiě)入2字節，一個(gè)為額外的標志，一個(gè)為系統類(lèi)型。
9） 如果需要，則保存原始文件名稱(chēng)。
10) 保存頭部信息的長(cháng)度。
11) 調用函數deflate()壓縮。
12) 寫(xiě)入4字節的CRC值。
13) 寫(xiě)入4字節的原始內容長(cháng)度值。
14）修改前面保存的頭部信息長(cháng)度的值。
13/
==================================================================================
在文件gzip-1.2.4/deflate.c中：
函數： ulg deflate()
功能： 壓縮數據。此函數通過(guò)一些復雜的算法來(lái)進(jìn)行壓縮操作，可以直接引用。
1) 如果需要快速壓縮，則調用函數deflate_fast()，然后返回。
2) 將當前內容插入到哈希表中，并查找最長(cháng)匹配。
3) 若找到匹配內容，則輸出<length,distence>對的編碼，否則輸出字符編碼。
14/
==================================================================================
在文件gzip-1.2.4/deflate.c中：
函數： ulg deflate()
功能： 壓縮數據。此函數通過(guò)一些稍簡(jiǎn)單一些的算法來(lái)進(jìn)行壓縮操作，可以直接引用。
1）將當前內容插入到哈希表中，并查找最長(cháng)匹配。
2）若找到匹配內容，則輸出<length,distence>對的編碼，否則輸出字符編碼。
