Gzip程序理解

目标与态度 | 阶段1要求 | 阶段2要求 | Gzip考试要求

• 工具：SourceInsight, Visual C++ 6.0
• Gzip
  • Gzip v1.2.4源程序( 本地下载),
  • gzip原理和实现
  • 关于Lempel-Ziv77压缩算法及其实现的研究，计算机研究与发展，33(5):329-340，1996.5.
• 关于Gzip程序理解实践的教研论文

目标与态度

关于程序理解的目标

• 进一步学习C语言
• 学习如何从数据结构和流程出发阅读比较大的源代码
• 熟练使用程序阅读和编译调试工具
• 尝试与人合作，增强团队意识
• 学做电子讲稿并演讲，展示自己的成果
• 了解数据结构在实际中的使用
• 自主地学习，主动询问，多思考
  ——程序理解的任务是弹性的!
  希望各位同学应能宏观把握Gzip程序，了解其中涉及的主要数据结构和主要的算法，这些数据结构在表示和实现上的特点，主要算法与数据结构之间的关系（算法中如何运用数据结构进行问题求解）。

关于态度

• 各位同学应能客观地评价自己和他人，正确地对自己进行定位；
• 不希望同学宽于待己，严于律人；
• 部分同学要消除＂畏难＂情绪；
• 同学之间要互相帮助，共同进步(建议班干部带头帮助合理组建学习交流小组)。

第2阶段

• gzip原理和实现
• Gzip中所使用的算法对LZ77的改进
  1. 压缩码的存储结构改为由(distance，length)组成，distance表示当前串和前一匹配串的距离。distance不超过32K，length的范围为3~258。
  2. 用一个32K的缓冲区window和一个hash表来代替工作缓冲区，先输入32K字节填充window，再用hash表来寻找匹配串，所有长度超过3的串都插入hash表（实际上只记录该串在window中的起始位置）。当一个长度超过3的串到来时，计算一个hash索引，如果该位置的hash链不为空，则寻找该链上的与输入串的最大匹配串。无论匹配串是否找到，该串都被插入hash表。Hash函数(即UPDATE_HASH)的key是由hash表索引ins_h和该串第三个字节的值组成的，可保证前三个字节相同的串都有相同的hash索引，但不保证该hash链上的所有元素前三个字节都相同。
  3. Hash表以链地址法解决冲突，所有key为同义词的串存储在同一个hash链上。hash链上的第一个元素是最近插入该位置的串，进行匹配时总是从该串找起，链上的其他元素按插入时间依次存放。Hash表头即head[]，是unsign short类型数组，（定义方法： # define head (prev+WSIZE)，prev是unsign short 类型数组，长度为WSIZE=32K），其中存放hash链第一个元素（以该串第一字节在window中的位置表示），prev[]存放下一个元素，例如：若某元素为s（以在window中的位置表示），则prev[s]表示某条hash链上s之后的那个元素（也以在window中的位置表示），prev[prev[s]]表示hash链上再下一个元素。Hash链不删除元素，除非该元素太老而被自然覆盖。为避免最坏情况，算法对hash链长有限制，有时候，hash链长可能被人为缩短。
  4. 在级别为4—9的压缩中，算法采用一种lazy evaluation机制寻找匹配。具体过程为：当算法在当前输入找到一个长度为N的最长匹配串时，它并不急于输出，而是在下一个输入位置继续寻找最长匹配串，如果下一个输入位置找到一个大于N的匹配串，则放弃刚才的长度为N的匹配串，而只输出一个字节（即前一个输入位置的字节），并选择这个更长的匹配串输出。如果没有找到比N更长的匹配串，则输出上次找到的长度为N的匹配串，且下一次的匹配过程从N字节之后开始。级别更低的压缩不采用这种机制。
  5. 级别为1—3的压缩采用快速压缩方法，不采用lazy evaluation机制，它们只在找不到匹配串或找到的匹配串长度较短的情况下才将新串插入hash表。牺牲了压缩率但换来了高速度。
  6. 压缩产生的输出literals(找不到匹配串时，算法输出的字节)、length和distance被huffman树再次压缩，其中，literals和length被一棵huffman树压缩，distance被另一棵huffman树压缩。这两棵huffman树也以压缩形式存储于每个压缩块的头部，压缩块的大小可变，由算法决定。
• 理解tree.c——huffman树的结构定义以及处理
  • 数据类型：tree_desc、ct_data
  • 静态全局变量
    • 五棵Huffman树：static_ltree、static_dtree、dyn_ltree、dyn_dtree、bl_tree
    • l_desc、d_desc、bl_desc
    • bl_count
    • heap、heap_len、heap_max
  • 函数：build_tree、build_bl_tree、...
• 理解deflate.c
  • 哈希表及其处理: ins_h, UPDATE_HASH, INSERT_STRING
  • deflate算法
    • DEFLATE Compressed Data Format Specification version 1.3
    • An Explanation of the DEFLATE Algorithm

第一阶段

任务 | 阅读方法 | 报告(讲稿)撰写要求 | 评分要求 | 检查时间

任务

• Gzip及其开发运行环境的熟悉
  • 了解Gzip的功能、文件组织及命令行参数，阅读Gzip源代码中对命令行参数的处理，掌握带参的main的编程与运行
  • 学习使用SourceInsight阅读源代码
  • 熟悉Visual C++集成环境下Gzip工程的创建、编译和运行
    • 熟悉在Visual C++中设置断点以及调试(debug)等
    • 学会在debug状态下，查看变量的值、内存的状态、函数调用栈等信息
    • 学会输入、输出的重定向
    • 提高篇：学习makefile的编写，进行命令行方式下的编译和运行
• 理解Gzip的主要流程和一些缓冲区
  • 阅读gzip原理和实现
  • 阅读main函数，了解Gzip的主要处理流程
  • 理解一些标识符的含义和意义
    如：EXTERN、DECLARE、ALLOC、FREE、OF、work(在gzip.c中定义)
  • 理解文件操作
    • 文件名：ifname、ofname
    • 文件基本操作：fileno、setmode、perror、OPEN、fflush、fgets、fprintf、read、opendir、closedir
    • treat_file、treat_dir......
  • 理解输入缓冲区inbuf及相关操作
    • inbuf的定义(在gzip.c中定义，见下)
      DECLARE(uch, inbuf, INBUFSIZ+INBUF_EXTRA);
    • 相关变量：inptr、insize
    • 相关的操作：clear_bufs、get_byte、fill_inbuf、try_byte......
  • 其他缓冲区:outbuf、d_buf、window

Gzip考试要求

• 理解大型程序阅读方法
• Gzip压缩的主要原理，涉及的数据结构（huffman树、hash表）及存储特性
• 一些宏的使用
• 对所给程序片段能按要求进行分析和说明

程序阅读方法

• 先阅读main函数,了解其主要处理阶段，识别出各阶段的数据传递关系
• 当理解一个基本操作所在的函数时,可按如下步骤进行:
  1. 辨别函数中各个变量的作用域,将全局变量识别出来;
  2. 理解全局变量的类型以及函数参数和返回值的类型,这些是该函数与外界的接口;
  3. 在2的基础上总结该函数操纵的对象,输入和输出,结合程序的注释了解该函数的简要功能;
  4. 利用sourceinsight工具看该函数被哪些函数调用;另一方面,理出从main到该函数的调用路线图;
  5. 细看该函数的处理流程,结合4)进一步总结该函数的作用和意义.

报告(讲稿)撰写要求

• 准备５～８分钟的ppt讲稿，注意：字体最好用粗体,尺寸大一些,留一些行间距；
• 说明小组成员、组长及分工；
• 说明每一成员投入时间及小组讨论时间；
• 说明本组对程序理解的状况；
• 分工、进展、时间放在开头介绍；
• 举例说明本组在程序理解中的收获和存在的问题；
• 将所理解的内容分类,在详细介绍前给出一个提纲页；
• 针对每一类,是否有自己的一些体会和评价?如果有,不妨写出来；
• 每一类的细节不必逐一给出,选择有代表性的细讲,其他可以一带而过；
• 如果小组讨论的时间比较多,能否说一下小组主要讨论什么,收效如何?

评分要求

• 比例
  • 30% 团队得分，各组互评
  • 30% 组内成员互评得分
  • 40% 老师、助教打分
• 迟交
  • 这次得分折半
  • 下次得分为0
• 若学生未参与阅读、评分，其得分将被减免

检查时间

• 各组讲稿提交时间：10月28日23:00前
• 分数提交时间
  • 组内成员互评：11月5日截止（email给主讲老师）
  • 各组互评：以组为单位，11月5日截止（email给主讲老师）
  • 助教对学生的评分：11月6日截止