zlib源码分析—DEFLATE算法原理及实现

青旅半醒 2022-11-20 08:26 473阅读 0赞

从上一篇博客[zlib源码分析—compress函数][zlib_compress]学习了compress函数的代码，这一篇我们来详细分析一下deflate算法的流程。先从compress代码中所体现出来的deflate函数的返回值和输入参数看起。通过源数据长度来判别第二个参数是Z\_NO\_FLUSH还是Z\_FINISH（这里我们知道deflate第二个参数可以输入两个中参数Z\_NO\_FLUSH或Z\_FINISH），即如果源数据长度为0，第二个参数为Z\_FINISH，否则为Z\_NO\_FLUSH。deflate返回值为Z\_OK为正常状态，返回Z\_STREAM\_END，代表流结束（也就是全部压缩完毕），其他都为err状态。

do{ 
           ...
            err = deflate(&stream, sourceLen ? Z_NO_FLUSH : Z_FINISH);
        } while (err == Z_OK);
        ...
        return err == Z_STREAM_END ? Z_OK : err;
    
    // flush可选值
    /* Allowed flush values; see deflate() and inflate() below for details */
    #define Z_NO_FLUSH 0 // 不需要刷写数据
    #define Z_PARTIAL_FLUSH 1
    #define Z_SYNC_FLUSH 2
    #define Z_FULL_FLUSH 3
    #define Z_FINISH 4 // 没有源数据可供压缩
    #define Z_BLOCK 5
    #define Z_TREES 6
    
    /* Return codes for the compression/decompression functions. Negative values * are errors, positive values are used for special but normal events. */
    #define Z_OK 0 // deflate函数状态ok
    #define Z_STREAM_END 1 // 数据流结束，指示所有数据压缩完毕
    #define Z_NEED_DICT 2
    #define Z_ERRNO (-1)
    #define Z_STREAM_ERROR (-2)
    #define Z_DATA_ERROR (-3)
    #define Z_MEM_ERROR (-4)
    #define Z_BUF_ERROR (-5)
    #define Z_VERSION_ERROR (-6)
    
    // deflate状态
    #define INIT_STATE 42 /* zlib header -> BUSY_STATE */
    #ifdef GZIP
    # define GZIP_STATE 57 /* gzip header -> BUSY_STATE | EXTRA_STATE */
    #endif
    #define EXTRA_STATE 69 /* gzip extra block -> NAME_STATE */
    #define NAME_STATE 73 /* gzip file name -> COMMENT_STATE */
    #define COMMENT_STATE 91 /* gzip comment -> HCRC_STATE */
    #define HCRC_STATE 103 /* gzip header CRC -> BUSY_STATE */
    #define BUSY_STATE 113 /* deflate -> FINISH_STATE */
    #define FINISH_STATE 666 /* stream complete */

## deflate执行流程 ##

deflate函数前三个if语句用于判断参数的正确性，deflateStateCheck用于检查状态是否是deflate种允许的状态，**flush的取值需要处于\[Z\_NO\_FLUSH, Z\_BLOCK\]之间，剔除了取值Z\_TREES**。第二个if语句，用于过滤以下情况：输出缓冲next\_out指针为Z\_NULL的情况、avail\_in指示有输入数据，但是输入缓冲next\_in指针为Z\_NULL的情况、deflate状态为FINISH\_STATE而flush不为Z\_FINISH，并且这里层层递进的关系。第三个if就是过滤可获得的输出缓冲没有了的情况。

int ZEXPORT deflate (z_streamp strm, int flush) { 
        if (deflateStateCheck(strm) || flush > Z_BLOCK || flush < 0) { 
            return Z_STREAM_ERROR;
        }
    }
        if (strm->next_out == Z_NULL ||
            (strm->avail_in != 0 && strm->next_in == Z_NULL) ||
            (s->status == FINISH_STATE && flush != Z_FINISH)) { 
            ERR_RETURN(strm, Z_STREAM_ERROR);
        }
        if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);

下一步刷写pending\_buf，主要目的是尽量多地将数据刷出pending\_buf。如果调用后avail\_out等于零，也就是没有更多输出空间，deflate会以Z\_OK，last\_flush等于-1返回，以期望下次给更多的avail\_out输出空间。这不是非正常状态，只是正常流程中的正常操作。

if (s->pending != 0) { 
            flush_pending(strm);
            if (strm->avail_out == 0) { 
                s->last_flush = -1;
                return Z_OK;
            }

确保有事情要做，避免重复连续刷写。 对于使用Z\_FINISH进行的重复和无用的调用，我们将继续返回Z\_STREAM\_END而不是Z\_BUF\_ERROR。

} else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) &&
                   flush != Z_FINISH) { 
            ERR_RETURN(strm, Z_BUF_ERROR);
        }

用户在第一次进入FINISH状态后，一定不能再提供输入数据。

/* User must not provide more input after the first FINISH: */
        if (s->status == FINISH_STATE && strm->avail_in != 0) { 
            ERR_RETURN(strm, Z_BUF_ERROR);
        }

最终过滤后的情况：

*  next\_out输出缓冲必须分配好
 *  avail\_in不为零的情况下，也就是还有数据需要压缩，next\_in输入缓冲必须分配好
 *  avail\_in为零的情况下，也就是没有数据需要压缩，status状态为FINISH\_STATE时，flush必须为Z\_FINISH；status状态也可不为FINISH\_STATE
 *  avail\_out用于指示可获得的输出缓冲的大小必须大于0
 *  避免重复连续刷写
 *  用户在第一次进入FINISH状态后，一定不能再提供输入数据。

下一步进入BUSY\_STATE（工作模式），该段代码用于开启新的压缩块或继续当前块。第一段代码是IF判断，主要逻辑如下：

*  avail\_in不为零，就是有输入数据
 *  avail\_in为零，没有新输入数据，但是前向缓冲区里面有数据
 *  avail\_in为零，没有新输入数据，且前向缓冲区里面没有数据，flush不等于Z\_NO\_FLUSH且status不等于FINISH\_STATE

if (strm->avail_in != 0 || s->lookahead != 0 ||
            (flush != Z_NO_FLUSH && s->status != FINISH_STATE))

根据不同的压缩模式调用不同的函数，并取得返回值bstate。bstate的取值可以为need\_more、block\_done、finish\_start、finish\_done。从finish\_start和finish\_done说起，finish\_start就是压缩结束了，不接受任何新的压缩数据，但是需要输出缓冲空间以刷写压缩后的数据。finish\_done是压缩真正完成的标志，也就是不接受任何新的压缩数据，且所有压缩数据都已经刷写完毕。need\_more就是需要更多的输入数据和输出缓冲，如果需要更多输出缓冲，需要将last\_flush置为-1，最后都返回Z\_OK，进行下一次deflate。

bstate = s->level == 0 ? deflate_stored(s, flush) :
                     s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :
                     s->strategy == Z_RLE ? deflate_rle(s, flush) :
                     (*(configuration_table[s->level].func))(s, flush);
    
            if (bstate == finish_started || bstate == finish_done) { 
                s->status = FINISH_STATE;
            }
            if (bstate == need_more || bstate == finish_started) { 
                if (strm->avail_out == 0) { 
                    s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
                }
                return Z_OK;
            }

block\_done是指压缩块结束，需要根据flush的取值（Z\_PARTIAL\_FLUSH、FULL\_FLUSH or SYNC\_FLUSH），分别进行不同的刷新动作。正常情况下，不会走到Z\_PARTIAL\_FLUSH、FULL\_FLUSH、SYNC\_FLUSH分支，仅执行flush\_pending函数，并对avail\_out进行判断，如果没有可获得的空间，需要将last\_flush置为-1，返回Z\_OK，以期望执行下次deflate能获得更大空间。

if (bstate == block_done) { 
                if (flush == Z_PARTIAL_FLUSH) { 
                    _tr_align(s);
                } else if (flush != Z_BLOCK) {  /* FULL_FLUSH or SYNC_FLUSH */
                    _tr_stored_block(s, (char*)0, 0L, 0);
                    /* For a full flush, this empty block will be recognized * as a special marker by inflate_sync(). */
                    if (flush == Z_FULL_FLUSH) { 
                        CLEAR_HASH(s);             /* forget history */
                        if (s->lookahead == 0) { 
                            s->strstart = 0;
                            s->block_start = 0L;
                            s->insert = 0;
                        }
                    }
                }
                flush_pending(strm);
                if (strm->avail_out == 0) { 
                  s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
                  return Z_OK;
                }
            }

综上所述，deflate函数的主要逻辑用于处理输入数据大小、输出缓冲大小、刷新等问题。deflate函数的逻辑较为复杂，但是其主要的难点在于调用的一系列压缩函数，这些内容下一篇文章继续分析，主要关注是这些函数在什么时间返回finish\_started、finish\_done和block\_done。下图是deflate的zlib模式下3种状态的转换图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzbWFydGtpbGxlcg_size_16_color_FFFFFF_t_70_pic_center]

[zlib源码分析—输出Buffer机制][zlib_Buffer]

[zlib_compress]: https://feishujun.blog.csdn.net/article/details/109062940
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzbWFydGtpbGxlcg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/1e323dea046543ffaa312d78ce6f7080.png
[zlib_Buffer]: https://feishujun.blog.csdn.net/article/details/109330436