Gzip程序理解

说明：下面的提高篇不作为程序理解的基本要求，鼓励学有余力的同学对提高篇进一步钻研。

阶段1要求 | 阶段2要求 | 讲稿撰写要求 | 1,2阶段检查 | 阶段3要求 | 阶段4要求 | 最后检查要求

最后检查要求

• 每组撰写一份程序理解总结报告，说明:
  • 对程序模块、数据结构、算法等的理解情况;
  • 各组员的分工、执行情况
  • 各组员在这项活动中的收获（每个人单独写）
  • 对这项活动的利弊总结与建议
• 2005年12月31日22:00前交
• 2006年1月8日22:00前以组为单位提交:
  • 组内成员互评成绩
  • 各组互评成绩
  成绩表下载

第4阶段

• 重点理解deflate.c
  • 哈希表及其处理: ins_h, UPDATE_HASH, INSERT_STRING
  • deflate算法　
• Gzip中所使用的算法对LZ77的改进
  1. 压缩码的存储结构改为由(distance，length)组成，distance表示当前串和前一匹配串的距离。distance不超过32K，length不超过258。
  2. 用一个32K的缓冲区window和一个hash表来代替工作缓冲区，先输入32K字节填充window，再用hash表来寻找匹配串，所有长度超过3的串都插入hash表（实际上只记录该串在window中的起始位置）。当一个长度超过3的串到来时，计算一个hash索引，如果该位置的hash链不为空，则寻找该链上的与输入串的最大匹配串。无论匹配串是否找到，该串都被插入hash表。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树也以压缩形式存储于每个压缩块的头部，压缩块的大小可变，由算法决定。

第3阶段

• 重点理解tree.c——huffman树的结构定义以及处理
  • 数据类型：tree_desc、ct_data
  • 静态全局变量
    • l_desc、d_desc、bl_desc
    • bl_count
    • heap、heap_len、heap_max
  • 函数：build_tree、build_bl_tree、...
• gzip原理和实现
• DEFLATE Compressed Data Format Specification version 1.3
• An Explanation of the DEFLATE Algorithm

第1,2阶段检查

评分要求 | 讲稿修改建议 | 各组讲稿 | 小结

评分要求

• 比例
  • 30% 团队得分，各组互评
  • 30% 组内成员互评得分
  • 40% 老师、助教打分
• 迟交
  • 这次得分折半
  • 下次得分为0
• 分数提交时间
  • 组内成员互评：10月27日下课时
  • 各组互评
    • 10月27日下课时提交对各演讲组的评分
    • 11月1日下课前提交对其他组的评分
    • 要求：给出每一成员对其他组的评分和小组汇总后的得分
  • 助教打分的提交时间：10月30日截止
• 若学生未参与阅读、评分，其得分将被减免

对各组讲稿的一些修改建议

• 分工、进展、时间放在开头介绍；
• 将所理解的内容分类,在详细介绍前给出一个提纲页；
• 针对每一类,是否有自己的一些体会和评价?如果有,不妨写出来；
• 每一类的细节不必逐一给出,选择有代表性的细讲,其他可以一带而过；
• 作为讲稿,字体最好用粗体,尺寸大一些,留一些行间距；
• 如果小组讨论的时间比较多,能否说一下小组主要讨论什么,收效如何?

各组讲稿

• 讲稿打包下载, 各组情况简介
• 演讲组顺序:17,23,26,2,3,6,7

小结

• 关于程序理解的目标
  • 进一步学习C语言
  • 学习如何阅读比较大的源代码：流程、数据
  • 尝试与人合作，增强团队意识
  • 学习做ppt和演讲，展示自己的成果
  • 自主地学习，主动询问，多思考
  • 程序理解的任务是弹性的
• 关于态度
  • 大部分同学能客观地评价自己和他人；
  • 小部分同学宽于待己，严于律人
  • 部分同学要消除＂畏难＂情绪
  • 同学间要互相帮助，共同进步
  • 各位同学要正确地对自己进行定位

讲稿撰写要求

• 准备５～８分钟的ppt讲稿；
• 说明小组成员及分工；
• 说明每一成员投入时间及小组讨论时间；
• 说明本组对程序理解的状况；
• 举例说明本组在程序理解中的收获和存在的问题。

第2阶段

• 理解一些标识符的含义和意义
  • EXTERN、DECLARE、ALLOC、FREE
  • OF
  • work(在gzip.c中定义，见下)
    int (*work) OF((int infile, int outfile)) = zip; /* function to call */
• 理解文件操作
  • 文件名：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

第1阶段

• 了解Gzip的功能及命令行参数
• 熟悉Visual C++集成环境下Gzip工程的创建、编译和运行
  • 提高篇：学习makefile的编写，命令行方式下的编译和运行
  • 熟悉在Visual C++中设置断点、运行到断点、单步调试等
  • 学会在debug状态下，查看变量的值、内存的状态、函数调用栈等信息
  • 熟悉输入、输出的重定向
• 阅读Gzip源代码中对命令行参数的处理，掌握带参的main的编程与运行
• 学习使用SourceInsight阅读源代码