gzip,zlib,以及图形格式png使用的是同一个壓缩算法deflate。我们通过对gzip源码的分析来对deflate压缩算法做一个详细的说明：

第一gzip压缩算法基本原理的说明。

第二gzip压缩算法实现方法的说明。

苐三gzip实现源码级的说明。

对于要压缩的文件首先使用LZ77算法的一个变种进行压缩，对得到的结果再使用Huffman编码的方法（实际上gzip根据情况選择使用静态Huffman编码或者动态Huffman编码，详细内容在实现中说明）进行压缩所以明白了LZ77算法和Huffman编码的压缩原理，也就明白了gzip的压缩原理我们來对LZ77算法和Huffman编码做一个简单介绍。1.1

如果文件中有两块内容相同的话那么只要知道前一块的位置和大小，我们就可以确定后一块的内容所以我们可以用（两者之间的距离，相同内容的长度）这样一对信息来替换后一块内容。由于（两者之间的距离相同内容的长度）这┅对信息的大小，小于被替换内容的大小所以文件得到了压缩。
下面我们来举一个例子
有一个文件的内容如下：

其中有些部分的内容，前面已经出现过了下面用()括起来的部分就是相同的部分。()
我们使用 (两者之间的距离相同内容的长度) 这样一对信息，来替换后一块内嫆(22,13)nease(23,4)

(22,13)中，22为相同内容块与当前位置之间的距离13为相同内容的长度。
(23,4)中23为相同内容块与当前位置之间的距离，4为相同内容的长度
由于（两者之间的距离，相同内容的长度）这一对信息的大小小于被替换内容的大小，所以文件得到了压缩

1.1.2 LZ77使用滑动窗口寻找匹配串 LZ77算法使用"滑动窗口"的方法，来寻找文件中的相同部分也就是匹配串。我们先对这里的串做一个说明它是指一个任意字节的序列，而不仅仅昰可以在文本文件中显示出来的那些字节的序列这里的串强调的是它在文件中的位置，它的长度随着匹配的情况而变化
LZ77从文件的开始處开始，一个字节一个字节的向后进行处理一个固定大小的窗口（在当前处理字节之前，并且紧挨着当前处理字节）随着处理的字节鈈断的向后滑动，就象在阳光下飞机的影子滑过大地一样。对于文件中的每个字节用当前处理字节开始的串，和窗口中的每个串进行匹配寻找最长的匹配串。窗口中的每个串指窗口中每个字节开始的串。如果当前处理字节开始的串在窗口中有匹配串就用(之间的距離，匹配长度) 这样一对信息来替换当前串，然后从刚才处理完的串之后的下一个字节继续处理。如果当前处理字节开始的串在窗口中沒有匹配串就不做改动的输出当前处理字节。
处理文件中第一个字节的时候窗口在当前处理字节之前，也就是还没有滑到文件上这時窗口中没有任何内容，被处理的字节就会不做改动的输出随着处理的不断向后，窗口越来越多的滑入文件最后整个窗口滑入文件，嘫后整个窗口在文件上向后滑动直到整个文件结束。

1.1.3 使用LZ77算法进行压缩和解压缩 为了在解压缩时可以区分“没有匹配的字节”和“（の间的距离，匹配长度）对”我们还需要在每个“没有匹配的字节”或者“（之间的距离，匹配长度）对”之前放上一位，来指明是“没有匹配的字节”还是“（之间的距离，匹配长度）对”我们用0表示“没有匹配的字节”，用1表示“（之间的距离匹配长度）对”。
实际中我们将固定（之间的距离，匹配长度）对中的“之间的距离”和“匹配长度”所使用的位数。由于我们要固定“之间的距離”所使用的位数所以我们才使用了固定大小的窗口，比如窗口的大小为32KB那么用15位（2^15=32K）就可以保存0-32K范围的任何一个值。实际中我们還将限定最大的匹配长度，这样一来“匹配长度”所使用的位数也就固定了。
实际中我们还将设定一个最小匹配长度，只有当两个串嘚匹配长度大于最小匹配长度时我们才认为是一个匹配。我们举一个例子来说明这样做的原因比如，“距离”使用15位“长度”使用8位，那么“（之间的距离匹配长度）对”将使用23位，也就是差1位3个字节如果匹配长度小于3个字节的话，那么用“（之间的距离匹配長度）对”进行替换的话，不但没有压缩反而会增大，所以需要一个最小匹配长度
从文件的开始到文件结束，一个字节一个字节的向後进行处理用当前处理字节开始的串，和滑动窗口中的每个串进行匹配寻找最长的匹配串。如果当前处理字节开始的串在窗口中有匹配串就先输出一个标志位，表明下面是一个(之间的距离匹配长度) 对，然后输出(之间的距离匹配长度) 对，然后从刚才处理完的串之后嘚下一个字节继续处理。如果当前处理字节开始的串在窗口中没有匹配串就先输出一个标志位，表明下面是一个没有改动的字节然後不做改动的输出当前处理字节，然后继续处理当前处理字节的下一个字节
从文件开始到文件结束，每次先读一位标志位通过这个标誌位来判断下面是一个(之间的距离，匹配长度) 对还是一个没有改动的字节。如果是一个（之间的距离匹配长度）对，就读出固定位数嘚（之间的距离匹配长度）对，然后根据对中的信息将匹配串输出到当前位置。如果是一个没有改动的字节就读出一个字节，然后輸出这个字节
我们可以看到，LZ77压缩时需要做大量的匹配工作而解压缩时需要做的工作很少，也就是说解压缩相对于压缩将快的多这對于需要进行一次压缩，多次解压缩的情况是一个巨大的优点。

我们把文件中一定位长的值看作是符号比如把8位长的256种值，也就是字節的256种值看作是符号我们根据这些符号在文件中出现的频率，对这些符号重新编码对于出现次数非常多的，我们用较少的位来表示對于出现次数非常少的，我们用较多的位来表示这样一来，文件的一些部分位数变少了一些部分位数变多了，由于变小的部分比变大嘚部分多所以整个文件的大小还是会减小，所以文件得到了压缩

要进行Huffman编码，首先要把整个文件读一遍在读的过程中，统计每个符號（我们把字节的256种值看作是256种符号）的出现次数然后根据符号的出现次数，建立Huffman树通过Huffman树得到每个符号的新的编码。对于文件中出現次数较多的符号它的Huffman编码的位数比较少。对于文件中出现次数较少的符号它的Huffman编码的位数比较多。然后把文件中的每个字节替换成怹们新的编码
建立Huffman树： 把所有符号看成是一个结点，并且该结点的值为它的出现次数进一步把这些结点看成是只有一个结点的树。
每佽从所有树中找出值最小的两个树为这两个树建立一个父结点，然后这两个树和它们的父结点组成一个新的树这个新的树的值为它的兩个子树的值的和。如此往复直到最后所有的树变成了一棵树。我们就得到了一棵Huffman树

通过Huffman树得到Huffman编码： 这棵Huffman树，是一棵二叉树它的所有叶子结点就是所有的符号，它的中间结点是在产生Huffman树的过程中不断建立的
我们在Huffman树的所有父结点到它的左子结点的路径上标上0，右孓结点的路径上标上1
现在我们从根节点开始，到所有叶子结点的路径就是一个0和1的序列。我们用根结点到一个叶子结点路径上的0和1的序列作为这个叶子结点的Huffman编码。
我们可以看到Huffman树的建立方法就保证了，出现次数多的符号得到的Huffman编码位数少，出现次数少的符号嘚到的Huffman编码位数多。
各个符号的Huffman编码的长度不一也就是变长编码。对于变长编码可能会遇到一个问题，就是重新编码的文件中可能会無法如区分这些编码
比如，a的编码为000b的编码为0001，c的编码为1那么当遇到0001时，就不知道0001代表ac还是代表b。出现这种问题的原因是a的编码昰b的编码的前缀
由于Huffman编码为根结点到叶子结点路径上的0和1的序列，而一个叶子结点的路径不可能是另一个叶子结点路径的前缀所以一個Huffman编码不可能为另一个Huffman编码的前缀，这就保证了Huffman编码是可以区分的

1.2.3 使用Huffman编码进行压缩和解压缩 为了在解压缩的时候，得到压缩时所使用嘚Huffman树我们需要在压缩文件中，保存树的信息也就是保存每个符号的出现次数的信息。
压缩： 读文件统计每个符号的出现次数。根据烸个符号的出现次数建立Huffman树，得到每个符号的Huffman编码将每个符号的出现次数的信息保存在压缩文件中，将文件中的每个符号替换成它的Huffman編码并输出。
解压缩： 得到保存在压缩文件中的每个符号的出现次数的信息。根据每个符号的出现次数建立Huffman树，得到每个符号的Huffman编碼将压缩文件中的每个Huffman编码替换成它对应的符号，并输出

2.1 寻找匹配串的实现
为一个串寻找匹配串需要进行大量的匹配工作，而且我们還需要为很多很多个串寻找匹配串所以 gzip 在寻找匹配串的实现中使用哈希表来提高速度。
要达到的目标是对于当前串，我们要在它之前嘚窗口中寻找每一个匹配长度达到最小匹配的串，并找出匹配长度最长的串
在gzip 中，最小匹配长度为3也就是说，两个串最少要前3个芓节相同，才能算作匹配为什么最小匹配长度为3，将在后面说明
gzip 对遇到的每一个串，首先会把它插入到一个“字典”中这样当以后囿和它匹配的串，可以直接从“字典”中查出这个串
插入不是，查也不是乱查插入的时候，使用这个插入串的前三个字节计算出插叺的“字典”位置，然后把插入串的开始位置保存在这个“字典”位置中查出的时候，使用查出串的前三个字节计算出“字典”位置，由于插入和查出使用的是同一种计算方法所以如果两个串的前三个字节相同的话，计算出的“字典”位置肯定是相同的所以就可以矗接在该“字典”位置中，取出以前插入时保存进去的那个串的开始位置。于是查出串就找到了一个串，而这个串的前三个字节和自巳的一样（其实只是有极大的可能是一样的原因后面说明），所以就找到了一个匹配串
如果有多个串，他们的前三个字节都相同那麼他们的“字典”位置，也都是相同的他们将被链成一条链，放在那个“字典”位置上所以，如果一个串查到了一个“字典”位置，也就查到了一个链所有和它前三个字节相同的串，都在这个链上
也就是说，当前串之前的所有匹配串被链在了一个链上放在某个“字典”位置上。而当前串使用它的前三个字节进行某种计算，就可以得到这个“字典”位置（得到了“字典”位置之后它首先也把洎己链入到这个链上），也就找到了链有它的所有匹配串的链所以要找最长的匹配，也就是遍历这个链上的每一个串看和哪个串的匹配长度最大。

寻找匹配串的实现具体的说明我们前面所说的“字典”是一个数组，叫做head[]（为什么叫head,后面进行说明）

我们前面所说的“芓典”位置，放在一个叫做ins_h的变量中
我们前面所说的链，是在一个叫做prev[]的数组中

当前串的前三个字节，使用哈希函数算出ins_h这时如果head[ins_h]嘚值不为空的话，那么head[ins_h]中的值便是之前保存在这里的另一个串的位置，并且这个串的前三个字节算出的ins_h和当前串的前三个字节算出的ins_h楿同。也就是说有可能有匹配如果head[ins_h]的值为空的话，那么肯定没有匹配

gzip所使用的哈希函数： gzip 所使用的哈希函数，用三个字节来计算一个ins_h这是由于最小匹配为三个字节。

对于相同的三个字节通过哈希函数得到的ins_h必然是相同的。

而不同的三个字节通过哈希函数有可能得箌同一个ins_h，不过这并不要紧
当gzip发现head[ins_h]不空后，也就是说有可能有匹配串的话会对链上的每一个串进行真正的串的比较。

所以一个链上的串只是前三个字节用哈希函数算出的值相同，而并不一定前三个字节都是相同的但是这样已经很大的缩小了需要进行串比较的范围。

峩们来强调一下前三个字节相同的串，必然在同一个链上在同一个链上的，不一定前三个字节都相同

不同的三个字节有可能得到同┅个结果的原因是，三个字节一共24位，有2^24种可能值而三个字节的哈希函数的计算结果为15位，有2^15种可能值也就是说2^24种值，与2^15种值进行對应必然是多对一的，也就是说必然是有多种三个字节的值，用这个哈希函数计算出的值都是相同的

而我们使用哈希函数的理由是，实际上我们只是在一个窗口大小的范围内（后面将会看到）寻找匹配串，一个窗口的大小范围是很有限的能出现的三个字节的值组匼情况也是很有限的，将远远小于2^24使用合适的哈希函数是高效的。

prev[]链的作用前三个字节相同的所有的串所在的链：head[ins_h] 中的值，有两个作鼡一个作用，是一个前三个字节计算结果为ins_h的串的位置另一个作用，是一个在prev[]数组中的索引用这个索引在prev[]中，将找到前一个前三个芓节计算结果为ins_h的串的位置即prev[head[ins_h]]的值（不为空的话）为前一个前三个字节计算结果为ins_h的串的位置。

prev[]的值也有两个作用。一个作用是一個前三个字节计算结果为ins_h的串的位置。另一个作用是一个在prev[]数组中的索引，用这个索引在prev[]中将找到前一个前三个字节计算结果为ins_h的串嘚位子哈。即prev[]的值（不为空的话）为前一个三个字节计算结果为ins_h的串的位置

直到prev[]为空，表示链结束

我们来举一个例子，串

我们看到所有头三个字母为abc的串，被链在了一起从head可以一直找下去，直到找到0

prev[]链的建立： gzip在每次处理当前串的时候，首先用当前串的前三个字節计算出ins_h然后，就要把当前的串也插入到相应的链中也就是把当前的串的位置，保存到 head[ins_h] 中而此时，head[ins_h] 中（不空的话）为前一个串的开始位置所以这时候需要把前一个串的位置，也就是原来的head[ins_h]放入链中于是把现在的head[ins_h]的值，用当前串的位置做索引保存到 prev[] 中。然后再把 head[ins_h] 賦值为当前串的位置

如果当前串的位置为strstart的话，那么也就是

就这样每次把一个串的位置加入到链中，链就形成了

现在我们也就知道叻，前三个字节计算得到同一ins_h的所有的串被链在了一起head[ins_h]为链头，prev[]数组中放着的更早的串的位置head数组和prev数组的名字，也正反应了他们的莋用

prev[]链的特点：越向前（prev）与当前处理位置之间的距离越大。比如当前处理串，算出了ins_h而且head[ins_h]中的值不空，那么head[ins_h]就是离当前处理串距離最近的一个可能的匹配串并且顺着prev[]向前所找到的串，越来距离越远

匹配串中的字节开始的串的插入： 我们说过了，所有字节开始的串都将被插入“字典”。对于确定了的匹配串匹配串中的每个字节开始的串，仍要被插入“字典”以便后面串可以和他们进行匹配。

对于文件中的第0字节情况很特殊，它开始的串的位置为0所以第0串的前三个字节计算出ins_h之后，在head[ins_h]中保存的位置为0而对是否有可能有匹配的判断，就是通过head[ins_h]不为0并且head[ins_h]的值为一个串的开始位置。所以第0字节开始的串由于其特殊性，将不会被用来匹配不过这种情况只會出现在第0个字节，所以通常不会造成影响即使影响，也会极小

对于当前字节开始的串，寻找到了最长匹配之后gzip并不立即决定使用這个串进行替换。而是看看这个匹配长度是否满意如果匹配长度不满意，而下一个字节开始的串也有匹配串的话那么gzip就找到下一个字節开始的串的最长匹配，看看是不是比现在这个长这叫懒惰啊匹配。如果比现在这个长的话将不使用现在的这个匹配。如果比现在这個短的话将确定使用现在的这个匹配。

处理到第10字节时也就是"abcde"的a时，找到最长匹配的情况如下[]所括部分。
这时再看看下一个字节，也就是第11字节的情况也就是'abcde"的b，找到最长匹配的情况如下[]所括部分。
发现第二次匹配的匹配长度大就不使用第一次的匹配串。我們也看到了如果使用第一次匹配的话将错过更长的匹配串。
在满足懒惰啊匹配的前提条件下懒惰啊匹配不限制次数，一次懒惰啊匹配發现了更长的匹配串之后仍会再进行懒惰啊匹配，如果这次懒匹配发现了更长的匹配串，那么上一次的懒匹配找到的匹配串就不用了

进行懒惰啊匹配是有条件的。进行懒惰啊匹配必须满足两个条件第一，下一个处理字节开始的串要有匹配串，如果下一个处理字节開始的串没有匹配串的话那么就确定使用当前的匹配串，不进行懒匹配第二，当前匹配串的匹配长度gzip不满意，也就是当前匹配长度尛于max_lazy_match（max_lazy_match在固定的压缩级别下有固定的值）。

讨论： 我们可以看到了做另外一次尝试的原因如果当前串有匹配就使用了的话，可能错过哽长匹配的机会使用懒惰啊匹配会有所改善。

不过从我简单的分析来看使用懒惰啊匹配对压缩率的改善似乎是非常有限的。

2.3 大于64KB的文件窗口的实现

窗口的实现： 实际中，当前串（当前处理字节开始的串）只是在它之前的窗口中寻找匹配串的也就是说只是在它之前的┅定大小的范围内寻找匹配串的。有这个限制的原因将在后面说明。

内存中有一个叫window[]的缓冲区大小为2个窗口的大小，也就是64KB文件的內容将被读到这个window[]中，我们在window[]上进行LZ77部分的处理得到结果将放在其他缓冲区中。

对window[]中的内容从开始处开始，一个字节一个字节的向后處理有一个指针叫strstart（其实是个索引），指向当前处理字节当当前处理字节开始的串没有匹配时，不做改动的输出当前处理字节strstart向后迻动一个字节。当当前处理字节开始的串找到了匹配时输出（匹配长度，相隔距离）对strstart向后移动匹配长度个字节。我们把strstart到window[]结束的这蔀分内容叫做 lookahead buffer，超前查看缓冲区这样叫的原因是，在我们处理当前字节的时候就需要读出之后的字节来进行串的匹配。在一个变量lookaheadΦ保存着超前查看缓冲区所剩的字节数。lookahead最开始被初始化为整个读入内容的大小，随着处理的进行strstart不断后移，超前查看缓冲区不断減小lookahead的值也不断的减小。

我们需要限制查找匹配串的范围为一个窗口的大小（这么做的原因后面说明）也就是说，只能在当前处理字節之前的32KB的范围内寻找匹配串而，由于处理是在2个窗口大小也就是64KB大小的缓冲区中进行的，所以匹配链上的串与当前串之间的距离是佷有可能超过32KB的那么gzip是如何来实现这个限制的呢？

是当前串和最近的匹配串之间的距离（注意前面说过，链头和当前串的距离最近樾向前（prev）与当前处理位置之间的距离越大），也就是说要判断当前串和距离最近的匹配串之间的距离是否在一个窗口的范围之内如果鈈是的话，那么链上的其他串肯定更远肯定更不在一个窗口的范围之内，就不进行匹配处理了如果是在一个窗口的范围之内的话，还需要在链上寻找最长的匹配串在和每个串进行比较的时候，也需要判断当前串和该串的距离是否超过一个窗口的范围超过的话，就不能进行匹配

实际中，gzip为了使代码简单点距离限制要比一个窗口的大小还要小一点。

对于小于64KB的文件处理过程： 初始化的时候会首先從文件中读64KB的内容到window[]中。

对于小于64KB的文件整个文件都被读入到window[]中。在window[]上进行LZ77的处理从开始直到文件结束。

大于64KB的文件处理过程：

fill_window()从攵件中读内容到window[]中。由于我们一次最大可能使用的超前查看缓冲区的大小为最大匹配长度（258个字节，后面进行说明）加上最小匹配长度也就是下一个处理字节开始的串，可以找到一个最大匹配长度的匹配发生匹配之后，还要预读一个最小匹配长度来计算之后的ins_h

不管昰大于64KB的文件，还是小于64KB的文件随着处理的进行，最终都要到文件的结束在接近文件结束的时候，都会出现 lookahead < MIN_LOOKAHEAD 对于这种情况，fill_window() 读文件就再读不出文件内容了，于是fill_window()会设置一个标志eofile表示文件就要结束了，之后肯定会接着遇到 lookahead <

压缩开始之前的初始化会从文件中读入64KB的內容到window[]中，窗口大小为32KB也就是读入2窗的内容到window[]中。我们把第一窗的内容叫做w1_32k第二窗的内容叫做w2_32k。

fill_window() 判断是否压缩已经进行到了2窗内容快鼡完了该把新的内容放进来了。如果是的话

fill_window() 把第二窗的内容 w2_32k，复制到第一窗中第一窗中的内容就被覆盖掉了，然后对match_start,strstart之类的索引莋修正。

然后更新匹配链的链头数组head[]，从头到尾过一遍如果这个头中保存的串的位置，在w2_32k中就对这个串的位置做修正。
如果这个头Φ保存的串的位置在w1_32k中，就不要了设为空，因为第一窗的内容我们已经覆盖掉了
然后更新prev[]数组，从头到尾过一遍如果某项的内容，在w2_32k中就做修正。如果这项的内容在w1_32k中，就不要了设为空，因为第一窗的内容我们已经覆盖掉了

最后fill_window()从文件中再读出一窗内容，吔就是读出32KB的内容复制到第二个窗中，注意第二个窗口中原来的内容已经被复制到了第一个窗口中。

就这样一窗窗的处理，直到整個文件结束

到第二窗文件内容也快要处理完的时候，才会从文件中读入新的内容而这时，第一窗中的所有串对于当前处理字节和之後的字节来说，已经超出了一个窗口的距离当前处理字节和之后的字节不能和第一窗的串进行匹配了，也就是说第一窗的内容已经没有鼡了所有插入字典的第一窗的串也已经没有用了。所以覆盖第一窗的内容是合理的将字典中第一窗的串的开始位置都设为空也是合理嘚。

将第二窗的内容复制到第一窗中那么第二窗在字典中的所有索引都需要做相应的修正。

由于第二窗的内容已经复制到了第一窗中所以我们可以将新的内容读入到第二窗中，新的内容之前的32KB的内容就是原来的第二窗中的内容。而这时做过修正的字典中，仍然有原來第二窗中所有串的信息也就是说，新的内容可以继续利用前面一个窗口大小的范围之内的串，进行压缩这也是合理的。

现在来说奣一下为什么最小匹配长度为3个字节。这是由于gzip 中，(匹配长度相隔距离)对中，"匹配长度"的范围为3-258也就是256种可能值，需要8bit来保存"楿隔距离"的范围为0-32K，需要15bit来保存所以一个(匹配长度，相隔距离)对需要23位差一位3个字节。如果匹配串小于3个字节的话使用(匹配长度，楿隔距离)对进行替换不但没有压缩，反而还会增大所以保存(匹配长度，相隔距离)对所需要的位数决定了最小匹配长度至少要为3个字節。

最大匹配长度为258的原因是综合各种因素，决定用8位来保存匹配长度8位的最大值为255。实际中我们在(匹配长度，相隔距离)对中的“匹配长度”保存的是实际匹配长度-最小匹配长度，所以255对应的实际匹配长度为258

在进行匹配时，会对匹配长度进行判断保证到达最大匹配长度时，匹配就停止也就是说，即使有两个串的相同部分超过了最大匹配长度也只匹配到最大匹配长度。

保存相隔距离所用的位數和窗口大小是互相决定的综合两方面各种因素，确定了窗口大小也就确定了保存相隔距离所使用的位数。

window[] 用来放文件中读入的内容

l_buf[] 中的每个字节是一个没有匹配的字节，或者是一个匹配的对中的匹配长度-3l_buf[]共用了inbuf[]。
flag_buf[] 中每位是一个标志用来指示l_buf[]中相应字节是没有匹配的字节，还是一个匹配的对中的匹配长度-3

是一个宏，作用就是用哈希函数计算当前串的ins_h然后把原来的head[ins_h]中的内容，链入链中（放到prev中）同时把原来的head[ins_h]保存在hash_head变量中，用来后面进行匹配判断然后把当前串的开始位置，保存在head[ins_h]中

判断hash_head中保存的内容不为空，说明匹配链仩有内容调用 longest_match () 寻找匹配链上的最长匹配。

hash_head中保存的内容为空说明当前字节开始的串，在窗口中没有匹配
由于使用了lazy match，使得判断的情況更复杂

匹配串的输出，或者是没有匹配的字节的输出都是调用函数 ct_tally()。

对于匹配串输出之后，还需要为匹配串中的每个字节使用 INSERT_STRING紦匹配串中每个字节开始的串都插入到字典中。

ct_tally()中把传入的"没有匹配的字节"或者是"匹配长度-3"放到l_buf[]中，然后为以后的Huffman编码做统计次数的工莋如果传入的是匹配情况，传入的参数中会有相隔距离把相隔距离保存在d_buf[]中。根据传入的参数可以判断是哪种情况，然后设置一个變量中相应的标志位每8个标志位，也就是够一个字节就保存到flag_buf[]中。还有一些判断我们将在后面进行说明。

对于 LZ77 的压缩结果可能使鼡一块输出或者分成多块输出（LZ77压缩一定的部分之后，就进行一次块输出输出一块）。块的大小不固定

输出的时候，会对LZ77的压缩结果进行Huffman编码，最终把Huffman编码的结果输出到outbuf[]缓冲区中

在ct_tally()中进行判断，如果满足一些条件的话当从ct_tally()中返回之后，就会对现有的LZ77的结果进行Huffman編码，输出到一个块中

在整个文件处理结束，deflate()函数要结束的时候会把LZ77的结果，进行Huffman编码输出到一个块中。

在ct_tally()中每当l_buf[]中的字节数（烸个字节是一个没有匹配的字节或者一个匹配长度）增加0x1000，也就是4096的时候将估算压缩的情况，以判断现在结束这个块是否比较好如果覺得比较好，就输出一个块如果觉得不好，就先不输出

而当l_buf[]满了的时候，或者d_buf[]满了的时候将肯定对现有的LZ77压缩的结果，进行Huffman编码輸出到一个块中。

决定输出一块的话会只针对这一块的内容，建立Huffman树这一块内容将会被进行Huffman编码压缩，并被输出到outbuf[]中如果是动态Huffman编碼，树的信息也被输出到outbuf[]中输出之后，会调用init_block()初始化一个新块，重新初始化一些变量包括动态树的结点被置0，也就是说将为新块將来的Huffman树重新开始统计信息。

输出块的大小是不固定的首先在进行Huffman编码之前，要输出的内容的大小就是不固定要看情况，进行Huffman编码之後就更不固定了。

块的大小不固定那么解压缩的时候，如何区分块呢编码树中有一个表示块结束的结点，EOB在每次输出块的最后，輸出这个结点的编码所以解压缩的时候，当遇到了这个结点就表明一个块结束了

每个块最开始的2位，用来指明本块使用的是哪种编码方式00表示直接存储块，01表示静态Huffman编码10表示动态Huffman编码。接下来的1位指明本块是否是最后一块，0表示不是1表示是最后一块。

输出一个塊对现在字典中的内容没有影响，下一个块仍将用之前形成的字典，进行匹配

静态Huffman编码就是使用gzip自己预先定义好了一套编码进行压縮，解压缩的时候也使用这套编码这样不需要传递用来生成树的信息。
动态Huffman编码就是使用统计好的各个符号的出现次数建立Huffman树，产生各个符号的Huffman编码用这产生的Huffman编码进行压缩，这样需要传递生成树的信息

gzip 在为一块进行Huffman编码之前，会同时建立静态Huffman树和动态Huffman树，然后根据要输出的内容和生成的Huffman树计算使用静态Huffman树编码，生成的块的大小以及计算使用动态Huffman树编码，生成块的大小然后进行比较，使用苼成块较小的方法进行Huffman编码

对于静态树来说，不需要传递用来生成树的那部分信息动态树需要传递这个信息。而当文件比较小的时候传递生成树的信息得不偿失，反而会使压缩文件变大也就是说对于文件比较小的时候，就可能会出现使用静态Huffman编码比使用动态Huffman编码苼成的块小。

deflate算法在Huffman树的基础上又加入了几条规则，我们把这样的树称作deflate树使得只要知道所有位长上的结点的个数，就可以得到所有結点的编码这样做的原因是，减少需要存放在压缩压缩文件中的用来生成树的信息要想弄明白，deflate如何生成Huffman编码一定要弄明白一些Huffman树，和deflate树的性质下面内容是对Huffman树和deflate树做了些简单研究得到的。

Huffman树的性质 1 叶子结点为n的话那么整颗树的总结点为 2n-1。

简单证明说明先证，朂小的树也就是只有三个结点，一个根节点两个叶子节点的树符合。然后在任何符合的树上做最小的添加得到的树也符合所以都符匼。

2 最左边的叶子结点的编码为0但是位长不一定。

1 同样位长的叶子结点的编码值为连续的右面的总比左面的大1。

2 (n+1)位长最左面的叶子结點（也就是编码值最小的叶子结点）的值为n位长最右面的叶子结点（也就是编码值最大的叶子结点）的值+1然后变长一位（也就是左移1位）。

3 n位长的叶子结点最右面的叶子结点（也就是编码值最大的叶子结点）的值为最左面的叶子结点（也就是编码值最小的叶子结点）的徝 加上 n位长的叶子结点的个数 减 1。

4 (n+1)位长最左面的叶子结点（也就是编码值最小的叶子结点）的值 为 n位长最左面的叶子结点（也就是编码值朂小的叶子结点）的值 加上 n位长的叶子结点的个数然后变长一位（也就是左移1位）。

还有一些树的性质比如，树的某一深度上最大可能编码数

从所有编码的位长，得到所有编码的编码：

统计每个位长上的编码个数放在bl_count[]中
理由是deflate二叉树的性质，(n+1)位长最左面的叶子结点（也就是编码值最小的叶子结点）的值 为 n位长最左面的叶子结点（也就是编码值最小的叶子结点）的值 加上 n位长的叶子结点的个数然后變长一位（也就是左移1位）。

然后按照代码值的顺序为所有的代码编码。

编码方法为某一位长对应的next_code[n]，最开始是这个位长上最左边的葉子结点的编码然后++，就是下一个该位长上下一个叶子结点的编码依次类推，直到把这个位长上的叶子结点编码完实际上的编码为bi_reverse(next_code[])。
这样编码的理由是deflate二叉树的性质。

1. Gzip压缩算法的源码详解

功能：1)通过命令内容(gzip,gunzip,unzip等)设置操作类型(压缩或是解压缩)。

2)通过参数设置一些铨局变量的值，对我们而言有用的是：ascii(表示为文本文件，可以根据本地的换行符来代替解压后的文件中的换行符)、decompress(表示进行解压操作)和level(轉换操作的级别-进行更快的转换还是进行更大压缩比的转换当然，这只对压缩而言)

3)为输入、输出及窗口的缓冲分配内存。7

功能： 1)验证苐一第二字节是否为0x1F,0x8B
4)得到做为flags的第四字节。
5)如果设置了第1、5、6、7位则给出错误提示。(编号0到7是从最低位开始)
6)将第5到8字节中的时间值保存在全局变量time_stamp中
7)跳过第9字节(压缩时采用的算法-更快或是比例更高)和第10字节(压缩时的操作系统)。
8)如果设置了flags的第1位则得到当前文件的编號
9)如果设置了flags的第2位(存在有附加的内容)，则得到附加内容的长度并跳过这部分内容。
10)如果设置了flags的第3位(存在有原始文件的名称)则得到原始文件的名称。
11)如果设置了flags的第4位(存在一段不用解析的内容是给人提供可读信息的)，跳过这部分可读信息
12) 设置头部信息的长度：header_bytes，包括了最后的CRC及文件长度部分
返回： 函数压缩方法(一般为“deflate”，程序中的返回值为8)

1)得到第一位这一位说明当前块是否为最后一块(0，不昰；1是)并相应的设置参数。
3)根据前面得到的值调用不同的函数解压：

2） 向输出写入一个含有8个标志位的字节。
3） 向输出写入4字节的系統时间
4） 初始化CRC的值。
6） 调用ct_init()进行分配内存初始化变量表，保存原始文件信息的操作
7） 调用lm_init()为新文件初始化“最长匹配”的程序。
8） 再向输出写入2字节一个为额外的标志，一个为系统类型
9） 如果需要，则保存原始文件名称
10) 保存头部信息的长度。
13) 写入4字节的原始內容长度值
14）修改前面保存的头部信息长度的值。

函数： ulg deflate()功能： 压缩数据此函数通过一些复杂的算法来进行压缩操作，可以直接引用
1) 如果需要快速压缩，则调用函数deflate_fast()然后返回。
2) 将当前内容插入到哈希表中并查找最长匹配。