分类目录归档:数据压缩(zip-7z)

数据压缩,解压算法。zip文件格式,7z文件格式

7z文件格式及其源码的分析(六)-完结篇

上一篇在这里 7z文件格式及其源码的分析(五)

这一篇主要介绍7z的流式压缩和解压原理.

对于流式处理来讲, 主要问题是要处理好文件头的问题. 因为是流式的, 所以,不可能走回头路. 也就不可能说压缩完了之后回到开头来修改头的信息.

7z文件的文件头其实是分为两部分的, 这两部分文件头在前面的几篇分析中都有介绍:

  1. 头Header, 就是写在文件前面的 Header. 这个头比较小, 主要记录了文件的版本信息, 以及尾header的位置偏移和校验和等等. 其主要作用是文件类型识别和查找到尾Header

  2. 尾Header, 就是写在文件末尾的 Header. 这里记录了 7z 文件的全部压缩信息, 解压主要就靠这里面的信息了.

7z 常见的压缩过程是: 先把 头Header 的一些位置保留, 然后压缩数据. 压缩完之后, 尾Header 写完之后, 再把 尾Header 的大小,偏移,校验和写回到 头Header 中去.

在流式环境下, 最后一步回头写 头Header 的过程显然不可能完成. 因为已经流过了.

那 7z 是怎么处理这个问题的呢? 7z 支持流式压缩吗?

7z 的文档里,并没有明确的回答这个问题. 我们还是让它的代码回答吧.

我们找到 7z 的解压代码, 7zIn.cpp 文件. 找到 HRESULT CInArchive::ReadDatabase2() 函数. 大概在 1136 行.

这个函数就是在读取 头Header 信息, 并查找 尾Header 位置.

我们截取它开头的一部分代码片段:

HRESULT CInArchive::ReadDatabase2(
    DECL_EXTERNAL_CODECS_LOC_VARS
    CArchiveDatabaseEx &db
    #ifndef _NO_CRYPTO
    , ICryptoGetTextPassword *getTextPassword, bool &passwordIsDefined
    #endif
    )
{
  db.Clear();
  db.ArchiveInfo.StartPosition = _arhiveBeginStreamPosition;

  db.ArchiveInfo.Version.Major = _header[6];
  db.ArchiveInfo.Version.Minor = _header[7];

  if (db.ArchiveInfo.Version.Major != kMajorVersion)
    ThrowUnsupportedVersion();

  UInt32 crcFromArchive = Get32(_header + 8);
  UInt64 nextHeaderOffset = Get64(_header + 0xC);
  UInt64 nextHeaderSize = Get64(_header + 0x14);
  UInt32 nextHeaderCRC = Get32(_header + 0x1C);
  UInt32 crc = CrcCalc(_header + 0xC, 20);

  #ifdef FORMAT_7Z_RECOVERY
  if (crcFromArchive == 0 && nextHeaderOffset == 0 && nextHeaderSize == 0 && nextHeaderCRC == 0)
  {
    UInt64 cur, cur2;
    RINOK(_stream->Seek(0, STREAM_SEEK_CUR, &cur));
    const int kCheckSize = 500;
    Byte buf[kCheckSize];
    RINOK(_stream->Seek(0, STREAM_SEEK_END, &cur2));
    int checkSize = kCheckSize;
    if (cur2 - cur < kCheckSize)
      checkSize = (int)(cur2 - cur);
    RINOK(_stream->Seek(-checkSize, STREAM_SEEK_END, &cur2));

    RINOK(ReadStream_FALSE(_stream, buf, (size_t)checkSize));

    int i;
    for (i = (int)checkSize - 2; i >= 0; i--)
      if (buf[i] == 0x17 && buf[i + 1] == 0x6 || buf[i] == 0x01 && buf[i + 1] == 0x04)
        break;
    if (i < 0)
      return S_FALSE;
    nextHeaderSize = checkSize - i;
    nextHeaderOffset = cur2 - cur + i;
    nextHeaderCRC = CrcCalc(buf + i, (size_t)nextHeaderSize);
    RINOK(_stream->Seek(cur, STREAM_SEEK_SET, NULL));
  }
  else
  #endif
  {
    if (crc != crcFromArchive)
      ThrowIncorrect();
  }

  db.ArchiveInfo.StartPositionAfterHeader = _arhiveBeginStreamPosition + kHeaderSize;


(...)

}

可以看到, 下面这几句是在从 头Header 上读取 尾Header 信息.

  UInt32 crcFromArchive = Get32(_header + 8);
  UInt64 nextHeaderOffset = Get64(_header + 0xC);
  UInt64 nextHeaderSize = Get64(_header + 0x14);
  UInt32 nextHeaderCRC = Get32(_header + 0x1C);
  UInt32 crc = CrcCalc(_header + 0xC, 20);

紧接着, 后面又有一句判断:

if (crcFromArchive == 0 && nextHeaderOffset == 0 && nextHeaderSize == 0 && nextHeaderCRC == 0)

如果这几个都读不到怎么办.

看代码, 接下来, 它会从文件末尾开始, 倒着向前查找特征字符:

if (buf[i] == 0x17 && buf[i + 1] == 0x6 || buf[i] == 0x01 && buf[i + 1] == 0x04)

这就是在找 0x17 0x06 或者 0x01 0x04 这两个特征串.

代码已经很明确了:

如果找到这其中之一, 就算是找到 尾Header 了.

为什么能这么做呢, 这两个串代表什么呢?

通过查看7z的文档(事实上, 前面讲的 尾Header 的结构的时候也能发现)知道.

  1. 0x17 是代表压缩Header的标记 kEncodedHeader. 后面的 0x06 是 packstream 的标记 kPackInfo.
  2. 0x01 是代表普通Header的标记 kHeader. 而 0x04 是 mainstream 的标记 kMainStreamsInfo.

这正是 7z 的两种 尾Header 的格式.

到这里, 可以总结一下了:

7z 流式压缩
压缩时可以把 头Header 中的 偏移量和 crc 和等 留空.
在解压时, 如果检测到这些留空了, 则会从文件末尾开始查找 尾Header 特征串.

这种方法可以一定程度实现 流式压缩. 虽然 7z 的文件结构本身,限制它不适合流式压缩的.

欢迎大家讨论交流: Neil 的博客

byNeil
byNeil.com

原文来自 Blog by Neil, post 7z文件格式及其源码的分析(六)-完结篇 转载请注明出处。本站保留一切权力

7z文件格式及其源码的分析(五)

这是7z文件格式及其源码的分析系列的第五篇. 上一篇讲到了7z文件压缩流程。最近太忙了,好久没更新,都快忘了写到哪了。:)

这一篇就说说7z文件的尾头的生成方式吧。 上一篇已经讲了尾header的结构了。它其实就是记录了压缩文件详细信息。

那么尾header是如何存储的呢?

先看一个图:

1

这是整个7z文件的结构。  最后面的绿色“尾文件头” 就是我们要说的目标。

7z的尾文件头有两种存储方式。

第一,  最简单的, 就是把尾文件头的内容直接写在后面, 不做任何处理。

这种方式最简单,但是却最不常用。 原因是什么。 我们看上一篇中说到的尾文件头的内容就知道了。 举个简单的例子, 比方说你要压缩大量的文件,比如100个文件吧。 为文件头里面就会有大量的空间用来存储文件名,文件大小,文件时间等等。  通常这些信息很多,但是有个共同特点就是重复信息多。 我们知道,对于这些简单的文本信息,其可压缩性非常强。 换句话说,这些信息的压缩比特别大。  于是, 这就引出了,另一种压缩方式。

第二, 把原始的尾header信息用lzma算法再压缩一次。这样可以显著的减少尾header的大小。尤其是在大量文件的时候。

我们来看一个图:

2

实际怎么生成的呢。 这其实是一个递归过程。

尾文件头压缩的思路就是把原始的尾文件头数据当做一个单独的文件流来进行一次前面的压缩过程。就是重复一次前面的7z的压缩过程。 不过这一次只有一个文件,因此只划分一个Folder. 而且压缩方法是指定的LZMA。也就是说只有一个Coder参与。   当然,原始尾文件头的内容可能有敏感信息。 比如里面的文件名等等信息。因此,7z也提供能力在压缩尾文件头的时候同时加密它。 所以压缩尾文件头的时候如果选择加密头信息,则会加入AES Coder加密。

3

 

所以实际尾header就是这样存储的,上面的 PH, 和HH。

 

用户在压缩7z文件的时候,可以选择是否加密文件, 并且可以同时选择是否加密文件头。

如果用户只加密文件,而不加密文件头。 这样的文件,双击直接用7z打开,可以看到里面的文件结构。文件详细信息,但是不能解压文件出来,除非有密码。

如果同时选择加密文件和文件头。 双击这样的文件,7z会直接提示请输入密码,否则连文件结构都看不见。 原因就在这里。 因为文件的结构信息也被加密了,没有密码,连文件头都解压不开。

这一点必zip文件先进, zip只支持文件内容加密。

暂时就到这吧。欢迎大家访问我的个人独立博客:http://byNeil.com 

下一篇给大家介绍7z如何实现流式压缩和解压的, 以及其他一些7z的trick。

 
byNeil
byNeil.com

原文来自 Blog by Neil, post 7z文件格式及其源码的分析(五) 转载请注明出处。本站保留一切权力

zip 压缩文件名的unicode(utf-8)支持

参见:http://www.pkware.com/documents/casestudies/APPNOTE.TXT

        Bit 11: Language encoding flag (EFS).  If this bit is set,
                the filename and comment fields for this file
                MUST be encoded using UTF-8. (see APPENDIX D)
D.1 The ZIP format has historically supported only the original IBM PC character 
encoding set, commonly referred to as IBM Code Page 437.  This limits storing 
file name characters to only those within the original MS-DOS range of values 
and does not properly support file names in other character encodings, or 
languages. To address this limitation, this specification will support the 
following change.

zip 文件头标志位的第11个位表示是否支持unicode文件名.

如果为0, 表示默认的使用 IBM 437 编码,

如果为1, 表示使用unicode文件名, 并且  文件名一定使用的是utf-8编码.

概括起来,  zip格式本来只支持英文 IBM437编码.  后来扩展了这个标记. 表示文件名是用utf-8编码表示的.

并且zip只支持utf-8.

 
byNeil
byNeil.com

原文来自 Blog by Neil, post zip 压缩文件名的unicode(utf-8)支持 转载请注明出处。本站保留一切权力

7z文件格式及其源码的分析(四)

这是7z文件格式及其源码的分析系列的第四篇. 上一篇讲到了7z文件静态结构的尾header部分.这一篇开始,将从7z实际压缩流程开始详细介绍7z文件尾header的详细结构.

一, 第一个概念: coder.

在7z的压缩过程中, 一个非常核心的概念就是coder.  一个coder代表一个算法, 通常是指一个压缩或解压算法(也包括过滤算法和加密算法等). 例如, 在7z中lzma算法就是一个coder,  deflate算法也是一个coder.  7z中用于加密的AES256算法也是一个coder.  

所以概念上讲, 能处理一个文件流的算法就是一个coder.  这个"处理"的概念可以是压缩/解压, 加密等等.

(图1)

通常来讲, 一个coder只能处理一个输入流, 并且只有一个输出流.  比如把一个文件流压缩成一个输出流.  但是, 7z中有的coder可以把一个输入流处理成多个输出流, 反过来也可以把多个流处理成一个流. 比如7z的 BCJ2 coder,  它是一个过滤coder, 可以把一个exe文件过滤成四个输出流.  这样的话, 7z的coder概念得到了扩展.  就是可能同时处理多个输入流, 并且可能输出多个流:

(图2)

这里可以先简单的体验一下压缩的过程了:

1. 简单压缩过程,  把文件流交给lzma coder压缩.

(图3)

2. 多coder串联, 理论上可以串联任何两个coder, 而且串联的级数也是没有限制的, 可以串联任意多级. 当然, 由于熵的存在, 串联过个压缩coder是没有意义的.

这里示例的是最常用的一种方式,就是压缩并且加密.

(图4)

注意上图中的o1, 和 i2.   o1是第一个coder的输出流, i2是第二个coder的输入流. 在实际操作中, 这两个流其实是同一个流, 直接把第一个的输出当做第二个的输入.

解压的过程就是上面的逆过程.

上图就是比较完整的一次压缩过程了.

 

二, 第二个概念 Folder, 不是文件夹.

这里的Folder要特别注意,  它不是我们通常指的文件夹.  它也不是任何物理上存在的东西.  

7z在开始压缩之前, 会把文件分类,  大体上是按文件类型以及文件是否需要加密来分类的.   比如说, 把所有的exe文件分成一类(一个Folder), 或者把所有需要加密的文件分在一起. 等等. 具体分类方法以后再说.  这个分类方法并不重要, 7z的实现用的方法比较简单. 实际上如果要实现7z的压缩器的话, 这个分类方法你说了算. 你可以给每个文件划分成一个Folder.

 我们看一个例子:

(图5)

 在这个例子中, 我们共有5个文件需要压缩. 

1. 首先, 通过一定的分组方法, 我们分成了两个Folder,  第一个Folder包括: a.exe, b.exe 和 c.dll 三个文件.  第二个Folder包括:a.txt 和 b.txt.

2. 对Folder1来说, 它包含三个文件, Folder1就简单的把三个文件串联起来,当做一个大文件, 作为输入流 i1 给Coder1 用. 后面的过程就就是上面的 图4 的内容了.

在7z源码的: \CPP\7zip\Archive\7z\ 这个目录下,有 7zFolderInStream.h 和7zFolderInStream.cpp 专门处理把多个文件串联伪装成一个文件的任务. 从Coder1 的角度看, 它只知道有个文件流 i1, 并不知道这个i1 是一个真实的文件 还是由一个Folder伪装的.

 

实际上, 7z概念上最小的压缩单位不是文件, 而是Folder,  它会先把所有的文件都归到一个相应的Folder中, 然后 让这个Folder作为文件流, 流过若干个Coder.  我们再抽象一下上面的压缩过程:

(图 6)

上图中的字母 'i' 表示输入的意思, 'o' 表示输出. 后面的数字表示序号.   简单解释一下, 这个Folder流最初是作为Coder1 的输入流i1. Coder1 的输出流是o1. 这个o1又作为 i2 输入给Coder2用,  然后又是Coder3.    

值得注意的是最后一个coder的输出流 o3.  它就是压缩的最终输出结果了.  它在7z中叫做一个PackedStream. 就是打包的流.  我们叫做p1吧.  如果有多个Folder, 那每个Folder就会有一个或多个PackedStream.  所以所有文件压缩之后就会有 pn.  这n个packedStream会被按顺序存储在 7z的文件主体, 就是上一篇文章中介绍的第二部分.

 

每个Folder 包含了哪些文件, 每个文件大小等等这些详细信息都存贮在7z的尾文件头中了. 在7zformat.txt中有这一段:

      NumFolders
      Folders[NumFolders]
      {
        NumCoders
        CodersInfo[NumCoders]
        {
          ID
          NumInStreams; //表示这个coder 所接受的输入流的个数, 一般是1个
          NumOutStreams; //表示这个coder的输出流的个数, 一般是1个.
          PropertiesSize //一个int值, 表示后面Properties的字节长度
          Properties[PropertiesSize] // 字节数组, 表示这个coder的一些设置信息, 比如压缩级别, 或者AES加密的IV等等. 
        }
        NumBindPairs  // 表示bindpair 的个数. bindpair表示输入流和输出流的绑定关系.  例如上面的图6中, o1和i2是绑定的, o2和i3是绑定的.
        BindPairsInfo[NumBindPairs] //bindpair的数组, 记录每一个bindpair.
        {
          InIndex;  //这个绑定的输入index,  就是上图中对应的 i后面的序号. (不好意思, 画图的时候没注意,图上下表是从1开始的,但是实际上,你懂的, 都是从0开始的.所有上面图中的下标都要减一.)
          OutIndex; //绑定对应的输出index, 就是对应上图中o后面的序号.  同上. 
        }
        PackedIndices //这表示这个folder最终输出的packstream在所有packstream中的序号.
      }
      UnPackSize[Folders][Folders.NumOutstreams] // 这是一个二位数组, 记录每个Folder对应的输出流的个数.
      CRCs[NumFolders] //这是一个Crc的数组, 没个folder 流的crc, 7z目前没有使用这一个字段. 

稍微解释一下上面的结构:

1. NumFolders, 显示一个int32值, 它记录了7z文件中共有多少个Folder.

2. 后面那是folder数组, 一次排布每个Folder. 每个Folder结构如下:

3. NumCoders, int32值, 记录了这个Folder总共进过了几个coder.

4. 后面就是它的所有Coder的数组, 每个coder的结构:  显示一个coder 的id. 就是coder的唯一标示符. 这个id的定义在: DOC/目录下的 methods.txt. 

5. 更详细的信息, 请看上面代码后面的注释吧.

6. 我再强调一点,我画图的时候没有注意,所以图中的i和o后面的序号都是从1开始的, 实际上,你懂的, 每个存储的序号都是从0开始的, 没有例外. 如果你发现哪里的序号和我说的不一样, 请检查这个.  没有例外, 所有的序号都是从0开始的. 包括以后我可能会画的图. 记住都是从0开始的.

 

7, 再有一点就是, 比如上图中的folder经过了 coder1, coder2 和coder3 这三个coder. 实际才存储这三个coder的时候, 是按逆序存储的, 就是先存Coder3, 然后是coder2, 最后是coder1.  这是为了方便解压.

 

 

上面的图6就是一次比较完整的压缩流程,    解压的流程就是反过来, 先分别构建coder1, coder2 和coder3, 然后逆向流动就最终解压了.

每个Folder都会经过一次完整的压缩过程.

 

好了, 主要的压缩过程和结构已经介绍完了.   下一篇将给大家介绍剩下的文件详细信息的存储方式, 以及最终的Header的生成方式.

最后还是欢迎大家访问我的独立博客: http://byNeil.com 

 

写这么多字, 画图都不容易,  帮顶一下吧, 小伙伴们.

 

 

 

byNeil
byNeil.com

原文来自 Blog by Neil, post 7z文件格式及其源码的分析(四) 转载请注明出处。本站保留一切权力

7z文件格式及其源码的分析(三)

上一篇在这里.  这是7z文件格式分析的第三篇, 相信有了前两篇的准备,你已经了解了7z源码的大致结构, 以及如何简单调试7z的源码了. 很多同学是不是迫不及待想要拔去7z的神秘外衣,看看究竟了. 好, 这就带你们一探乾坤. 本文开始,我们详细介绍7z的文件存储结构.

要了解7z的结构,  当然最好从官方的说明开始, 尽管这个说明非常简略, 但它的确是我入门时的救命稻草.

打开源码的 "DOC" 目录.  这里面就是官方所有的文档了. 其中只有二个文档跟结构相关:

1. 7zFormat.txt,   这是我们的主角, 里面介绍了7z文件的大体结构.

2. Methods.txt,  这里面介绍了7z压缩算法id的编码规则, 以后会用到.

 

我们从7zFormat.txt文件开始.

Archive structure
~~~~~~~~~~~~~~~~~ 
SignatureHeader
[PackedStreams]
[PackedStreamsForHeaders]
[
 Header 
 or 
 {
 Packed Header
 HeaderInfo
 }
]

 

上面就是7z文件的总体结构了.  我来稍微解释一下.  上面的代码中, 从波浪线往后开始算.    7z的文件结构基本上分为三部分:

1. 前文件头(就是最前面的header).

2. 压缩数据.

3. 尾文件头(就是放在文件末尾的header).

 

一, 前文件头就是上图中的 "SignatureHeader".  它是32个字节定长的.    前文件头其实记录的信息很少, 它的主要目的是记录尾文件头的位置, 压缩的主要结构都是存在尾文件头中.

它的结构如下:

SignatureHeader
~~~~~~~~~~~~~~~
 BYTE kSignature[6] = {'7', 'z', 0xBC, 0xAF, 0x27, 0x1C};
ArchiveVersion
 {
 BYTE Major; // now = 0
 BYTE Minor; // now = 2
 };
UINT32 StartHeaderCRC;
StartHeader
 {
 REAL_UINT64 NextHeaderOffset
 REAL_UINT64 NextHeaderSize
 UINT32 NextHeaderCRC
 }

 

先是固定的6个字节的值, 前两个字节的值是字母 '7' 和'z' 的ascii值.  后面四个字节是固定的: 0xbc, 0xaf, 0x27, 0x1c

然后是两个字节的版本号, 注意主版本号在前面, 次版本号在后面. 目前的版本号是: 0.2,  注意这是7z文件格式的版本号, 不是7z软件的版本号.

然后是四个字节的 UINT32 的值, (注意, 7z的所有数据都是采用小端在前的存储, 所以要注意这四个字节的实际存储顺序是低位字节在前面, 高位字节在后.  后面的所有数据都是这种结构, 所以以后就不再强调了.  ) .  这4个字节的值是做什么的呢?  先抛开这四个字节本身,   前文件头的32个字节中, 已经用去了 6 + 2 +4 =12 个, 还剩下20个字节.  对了, 这四个字节就是剩下的20个字节的CRC校验值.  具体的CRC算法源码, 在源码中的 "C" 文件夹下的 '7zCrc.c' 和 '7zCrc.h'.

最后这20个字节要一起介绍了.   先是8个字节的UINT64的值, 它记录的是尾文件头(上图中的NextHeader)与前文件头的距离, 这个距离是不算前面这32个字节头的, 也就是抛开前面32个字节开始计数的(解压器通过读取这个值,然后从第33个字节开始直接跳过这个距离, 就可以找到尾文件头了).  然后是8个字节的值, 记录了尾文件头的大小(解压的时候, 通过这个值就能读出尾文件头的长度了).  最后还有4个字节的值, 它也是一个Crc校验值,  是整个尾文件头的校验值.

这里需要注意的是, 上图中用的是 "REAL_UINT64" 这个表达方式, 它的意思就是我们通常理解的占8个字节的UInT64的值(当然是小端存储的啦).  这里用了"real", 真.  那是不是还有"假"的InT64呢. 答案是肯定的.   7z为了兼容压缩大文件(大于4G),这个问题曾一度是zip文件的噩梦,  早期的zip只能压缩小于4G的文件, 并且压缩后的总文件大小也不能超过4G, 后来专门做了标准升级. 好了扯远了.   7z一早设计就考虑到了大文件的问题, 所以很多地方都必须用int64来表达,  这样也会带来一个问题, 就是绝大多数case下, 都不可能超过4G(试问一下,你平时有多少压缩文件超过4G 呢),  所以呢, 就会造成8个字节的int64根本用不上, 多余的字节浪费了. 尤其在小文件压缩的时候,  很影响压缩比.  所以呢, 7z采取了一种巧妙的方法. 就是int64并不是都用8个字节存储, 它用一种简单的编码方式,进行变长存储. 在这个文件中也有描述:

REAL_UINT64 means real UINT64.
UINT64 means real UINT64 encoded with the following scheme:
Size of encoding sequence depends from first byte:
 First_Byte Extra_Bytes Value
 (binary) 
 0xxxxxxx : ( xxxxxxx )
 10xxxxxx BYTE y[1] : ( xxxxxx << (8 * 1)) + y
 110xxxxx BYTE y[2] : ( xxxxx << (8 * 2)) + y
 ...
 1111110x BYTE y[6] : ( x << (8 * 6)) + y
 11111110 BYTE y[7] : y
 11111111 BYTE y[8] : y

 

上面就是编码方式: 就是根据第一个字节的内容来判断后面还有多少个字节.

如果第一个字节的最高位是 0, 那后面就没有字节了. 范围在 0-127.

如果第一个字节的最高两位是 1, 0, 表示它后面还有一个字节.  读取方式是: ( xxxxxx << (8 * 1)) + y

依次类推, 不再详细介绍了.

它的写入方法在: \CPP\7zip\Archive\7z\7zOut.cpp 文件的 第204行:

void COutArchive::WriteNumber(UInt64 value)
{
  Byte firstByte = 0;
  Byte mask = 0x80;
  int i;
  for (i = 0; i < 8; i++)
  {
    if (value < ((UInt64(1) << ( 7  * (i + 1)))))
    {
      firstByte |= Byte(value >> (8 * i));
      break;
    }
    firstByte |= mask;
    mask >>= 1;
  }
  WriteByte(firstByte);
  for (;i > 0; i--)
  {
    WriteByte((Byte)value);
    value >>= 8;
  }
}

 

它的读取方法在: 7zIn.cpp 的第210行:

UInt64 CInByte2::ReadNumber()
{
  if (_pos >= _size)
    ThrowEndOfData();
  Byte firstByte = _buffer[_pos++];
  Byte mask = 0x80;
  UInt64 value = 0;
  for (int i = 0; i < 8; i++)
  {
    if ((firstByte & mask) == 0)
    {
      UInt64 highPart = firstByte & (mask - 1);
      value += (highPart << (i * 8));
      return value;
    }
    if (_pos >= _size)
      ThrowEndOfData();
    value |= ((UInt64)_buffer[_pos++] << (8 * i));
    mask >>= 1;
  }
  return value;
}

 

这里贴出来给大家参考一下.   其实, 后面提到的Uint64如果没有特别说明是8个字节, 那它都是采用这种压缩方式存储的. 但是注意UInt32 无论何时都是占4个字节的, 没有采用压缩.

 

二, 第二部分比较简单, 它会比较大, 简单的说, 它就是文件压缩后的压缩数据存放地点. 结构如下:

[PackedStreams]
[PackedStreamsForHeaders]

简单的说, 7z会把文件压缩成若干个"Pack", 就是包的意思, 这里就是按顺序存储这些pack的. 每个pack的位置和大小信息都会记录在尾header中, 解压的时候就会从这里读出pack,然后解压出来.   这里都是简单的排布压缩后的数据, 所以没有多少细节需要介绍的.

 

三, 真正复杂的主角出场了, 尾文件头,  就是7z中所谓的 nextHeader.

Header structure
~~~~~~~~~~~~~~~~
{
ArchiveProperties
AdditionalStreams
{
PackInfo
{
PackPos
NumPackStreams
Sizes[NumPackStreams]
CRCs[NumPackStreams]
}
CodersInfo
{
NumFolders
Folders[NumFolders]
{
NumCoders
CodersInfo[NumCoders]
{
ID
NumInStreams;
NumOutStreams;
PropertiesSize
Properties[PropertiesSize]
}
NumBindPairs
BindPairsInfo[NumBindPairs]
{
InIndex;
OutIndex;
}
PackedIndices
}
UnPackSize[Folders][Folders.NumOutstreams]
CRCs[NumFolders]
}
SubStreamsInfo
{
NumUnPackStreamsInFolders[NumFolders];
UnPackSizes[]
CRCs[]
}
}
MainStreamsInfo
{
(Same as in AdditionalStreams)
}
FilesInfo
{
NumFiles
Properties[]
{
ID
Size
Data
}
}
}

尾header的结构非常复杂,  里面有很多压缩概念,   如若没有理解压缩过程, 单独的纯字节层面介绍是没有意义的.

我们下一篇开始介绍详细的7z压缩流程,  介绍7z是如何把一系列的文件, 压缩成一个大文件的,  怎样利用压缩算放, 怎样排布文件结构.  同时我们再一边来介绍这个尾header的结构.

希望大家多多支持,  给我动力写下去.

欢迎大家访问我的个人独立博客: http://byNeil.com

 

记得顶啊, 小伙伴们.

 

 

 

 

 

 

 

 
byNeil
byNeil.com

原文来自 Blog by Neil, post 7z文件格式及其源码的分析(三) 转载请注明出处。本站保留一切权力

7z文件格式及其源码的分析(二)

这是第二篇, 第一篇在这里: 这一篇开始分析7z的源码结构.

一. 准备工作:

1. 源码下载:

可以从官方中文主页下载:http://sparanoid.com/lab/7z/.  为了方便, 这里直接给出下载链接: http://downloads.sourceforge.net/sevenzip/7z920.tar.bz2 .

2. 工具准备:

源码中给的工程文件都是vc6.0的工程.  作者说他不喜欢新vs的界面. 哎.  不过没关系, 我们使用VS2008也一样可以. 有极少地方需要修改一下.  我们使用VS2008 sp1 作为开发环境.

 

二. HelloWorld:

我们在根目录下新建一个目录"7z", 把源码都解压到这个位置.

我们稍后再详细解释这些目录的意思.   先来一个helloworld, 程序员的最爱.

请直接打开这个路径: 7z\CPP\7zip\Bundles\Alone\

用vs打开其中的 Alone.dsw 文件.   提示要转换工程文件. 点击同意.   然后编译这个工程. 如果不出意外的话, 应该提示你编译成功了.

这个时候, 打开 c:\util\  目录.  里面已经生成7za.exe.    注意, 这里是C盘的绝对路径 :  c:\UTIL\7za.exe

好了, 这个7za.exe  就是一个包含全部7z功能的压缩,解压命令行工具了.

我们可以从命令行进入该目录. 输入 7za.exe 回车. 就能看到它的帮助信息啦.

 

我们先拷贝一个文件到这个目录, 比如拷贝一个test.txt 到c:\util\ 里面去.  我们用命令行来压缩它.

==============

c:\util>7za.exe  a  test.7z  test.txt

==============

这个命令把test.txt  压缩成test.7z.   这两个文件名都是可以带路径的,  为了方便, 我们都拷贝到当前目录了.

恩, 我们再来试试解压.

==============

c:\util>7za.exe x  test.7z  -oout

==============

这个命令可以吧test.7z 解压到当前的out目录下.

试试这两个命令吧, 是不是还不错.

 

三, 目录结构详解:

我们先回到最外层目录:

7z源码基本上是按文件类型分类的.

1.  上面的ASM目录, 其中保存汇编代码.  为了极限的性能, 7z使用了部分汇编代码, crc计算, 和aes加密.  这两点都不是必须的, 实际上, 它们都有c语言的实现. 7z会检测, 如果cpu提供了硬件的aes指令, 就会使用硬件aes汇编指令, 而不会使用自己的aes函数.

2. "C" 目录是7z的核心.   实际上, 7z所有的核心算法都是用c语言实现的. 包括所有的压缩算法, 以及我们的主角7z打包算法.   这些c代码非常强悍, 部分代码可以跨平台编译, 甚至能在嵌入式平台上编译.

(a)  这里面有几个工程文件值得我们注意, 找到这个位置: 7z\C\Util\7z

我们来编译它. 它会在debug目录下生成  7zdec.exe

这是一个最小化的指包含7z解压器的独立exe程序.  有了它就可以解压文件了.

 

(b) 找到这个目录,  7z\C\Util\Lzma

编译之后也会在绝对目录生成.   c:\util\7lzma.exe.  这是一个lzma压缩算法的工具.  只能压缩或解压单个文件. 只包含lzma算法.

这可以用来测试lzma算法.

 

(c) 打开这个目录 7z\C\Util\LzmaLib.

这个工程用来生成 只包含lzma算法的 dll.  以便你的程序调用lzma算法.

 

3. "CPP" 目录是也是7z的重点.

前面说了核心的算法都在C目录下面.  那么CPP目录是做什么的呢.   除了核心的算法之外, 7z还有非常丰富的外围功能.  就是他的文件管理器, 以及右键菜单支持等等. 这些与UI和系统相关的功能都是用c++实现的.     此外, C中的核心算法在cpp目录中都有c++的面向对象的封装.  我们来逐一介绍它的子目录:

a ) "Windows" 目录.

其中包含了与windows集成的功能. 包括菜单集成, 剪贴板支持, 文件io,等等.

 

b) "Common" 目录.

通用的工具类.

 

c ) 我们重点介绍 7zip 目录:

 

(1) "Archive" 目录. 包含各种 archive ("打包") 算法的代码.   因为7z不光支持7z文件,  还支持zip, rar, chm等等其他的打包文件格式.

这里面每个目录就是一种格式.   7z目录当然就是我们的主角7z格式了. ( 这里面的代码是对C文件夹里面的代码的c++封装. )  这里面有一个工程文件.

打开这个工程文件, 然后在工程上面点右键,查看属性:

可以看到, 它的输出路径是: C:\Program Files\7-zip\Formats\7z.dll

这是什么意思呢?   对,  这个工程就是封装7z格式的dll.  这个工程的目的就是给我们演示如何让7z支持我们的自定义格式.   具体怎么实现自定义格式, 可以参考这个工程以及 它周围的其他文件夹格式, 比如:Cab, Chm, 等等. 实现相应的com接口, 然后编译到这个目录下, 7z就能自动调用了.  以后有时间我们再详细介绍这个.

 

(2) 再来看 "Bundles" 目录.

这里面的Alone目录, 我们在前面 写 helloworld 的时候已经见识过了. 它是一个包含全部7z功能的console 的exe.

其中我们再介绍另一个重要的目录,  就是Format7zF.

打开它, 编译,  会提示几个链接错误.  原因是因为作者使用的是vc6. 和我们使用的vs2008一些编译选项不支持了.

分别在这几个汇编文件上点击右键:

找到"CommandLine" 参数, 把其中的参数删除:  -omf -WX -W3,  只保留 -c

 

然后再编译就会成功了.

编译完成之后, 它会在绝对目录下生成一个dll.  C:\Program Files\7-Zip\7z.dll

这个dll是做什么的呢?

它是包含7z全部功能的dll.   第三方的程序可以调用这个dll实现7z的所有功能.   包括7z自己本身的文件管理器 都是通过这种方式调用的.

 

好了, 基本上 7z源码的主要目录都介绍完了.  大家有什么疑问可以留言交流.

我们之后的讲解都将使用: 7z\CPP\7zip\Bundles\Alone 这个目录下的工程配合命令行参数来调试讲解. 因为这是一个包含7z全部功能的console程序, 简单好调试.

 

如果你不想了解7z的文件结构,  只是想在你的程序中集成进处理7z文件的功能. 那么已经足够了.  可以打开上面介绍的相应工程,  把源码集成到你的工程中, 或者直接调用: 7z\CPP\7zip\Bundles\Format7zF 生成的dll. 都是不错的选择.

 

下一节开始, 我们将开始讲解7z的文件格式结构了.  完成以后, 我会把地址更新到这里.

欢迎大家访问我的独立博客交流讨论. http://byNeil.com
byNeil
byNeil.com

原文来自 Blog by Neil, post 7z文件格式及其源码的分析(二) 转载请注明出处。本站保留一切权力

7z文件格式及其源码的分析

本文是一个系列. 主要是分享我最近一年做7z文件开发的经验. 主要包括7z官方源码的结构分析, 以及7z文件格式的分析. 其中涉及到7z源码结构的各个细节, 以及7z文件格式的具体细节. 本文适合对象: 想要了解学习7z源码的开发人员, 想要了解7z文件格式细节, 做7z文件压缩器和解压器的开发人员, 以及其他压缩文件爱好者等等.

目前7z的最新稳定版是9.20, 而9.30版本还在alpha版本. 所以本文是基于其9.20版本.  我将尽可能详细的描述所有细节, 但到目前为止我了解到的细节大概能到八成到九成的样子. 也不是百分百.  希望能和大家共同讨论学习.  这些信息足以开发一个工业级别的高兼容性的7z压缩器和解压器了.

本文首发在我的个人独立博客  http://byNeil.com 以及博客园.  欢迎大家浏览我的独立博客, 留言交流. 转载请注明出处链接. 本人保留一切权利.  但本人不对使用本文提供的代码造成的损失负责.

好了, 憋死我了, 前面的客套话终于说完了.  有人可能要问, 为什么要分析7z文件格式? 这个不是开放的吗? 为什么我前面说我只了解到八,九成, 而不是百分百呢?

我先来解释这几个问题, 这能说明本文的必要性, 以及看下去的必要性.  首先7z的确是开放的. 但他的格式说明非常简单, 简直是简陋. 简单的一个txt文件,寥寥几十行算不上说明的符号, 对复杂的7z格式来说, 简直就是天书.( 后面分析7z源码的时候会详细说道这一点. )  所以如果你接到老板的一个通知:"我们要做7z兼容的压缩解压器" 的时候, 你就要崩溃了.  因为相对于zip这些经过标准化的文件格式来说, 7z几乎就是一个黑洞.(zip有标准化的 spec, 里面有详细到字节级别的说明).   所以我分析7z格式可以说有一半是通过阅读源码逆向推测出文件格式的, 再经过反复和源码对比测试证明其正确性的.  所以我只能说了解到了八九成, 而不是百分百.

先分享一些有用的链接:

7z的官方主页: http://www.7-zip.org/  (它托管在sourceforge的虚拟机上, 本来能打开的, 但是前一段时间开始被墙了, 我实在想不到墙它的理由, 可能是被sourceforge主机上其他的网站拖累的吧,你懂的).

这是sourceforge上7z的论坛: http://sourceforge.net/p/sevenzip/discussion/45797  . 论坛比较活跃, 每天都有新帖. 而且7z作者也在上面每天亲自回帖.  由于作者是俄罗斯人, 所以时区跟我们差的不多.  一般留言4个小时左右,  作者就能回复吧. 我问过几个问题, 都是这样的. 当然也有些帖子作者懒得回, 那就另当别论了. 呵呵.

7z的官方中文镜像: http://sparanoid.com/lab/7z/    这个不需要翻墙.  是官方给出的中文版链接. 值得信赖. 上面的内容基本和官方主页保持一致.

 

我们先从几个概念开始吧 :    7z软件 和7z文件.   7z文件指的是一种后缀名为.7z的文件.    7z软件指的是作者开发的生成和操作7z文件的工具.  但是现在7z软件已经发展到不光支持7z格式的文件了, 还能额外的生成和编辑另外几十种文件格式了. 其中包括我们熟知的zip格式, rar格式, iso格式等等,  也包括一些不可思议的格式, 比如: CAB, CHM, CPIO, CramFS, DEB, DMG, FAT . 看眼花了吧.  好吧, 本文主要讨论 7z文件格式, 以及7z软件中主要和7z文件相关的功能. 当然也会粗略的涉及到其他的一些有用的功能,  比如如何给7z软件写插件, 让他支持我们自己定义的文件格式.

 

再来几个概念.  说到压缩文件, 一般会遇到两个概念,   一个是 "Compress"(压缩) 和"Archive" (存档).    "存档" 这个词个人觉得不好理解. 我个人把 "Archive" 叫做 "打包".

举个例子,  比如有一堆毛巾,  每一条毛巾代表一个文件.    "Compress"(压缩)的意思就是把毛巾里面的水拧干, 达到压缩的目的.  而"Archive"(打包) 的意思就是把这些毛巾包成一个大包, 便于运输.     所以你可能想到了, 要运输一堆这样的毛巾可能有两种方法: 第一种: 先把每条毛巾拧干并折成方块(压缩), 再把这些方块组合成一个大包(打包).  第二种, 先把这些毛巾包成一个大包(打包),  然后再把这个大包拧干.    凭经验你可能已经意识到, 前一种方法比较好处理, 而且压缩比比较大.  后一种方法就弱一点了.

对了, 前一种就是先压缩后打包的方式. 7z, zip 和rar等就是用的这种方法.   后一种就是先打包, 后压缩的方法. 常见的tar.gz的文件就是用这种方法的. 先用tar打包, 在用gz压缩.

 

对于7z 我们再具体解释一下 "压缩" 和 "打包" 的概念.

 

7z 文件格式严格的说是一种"打包"的格式,  它规定了打包的方法.   而"压缩"的任务是由不同的算法完成的.    "压缩算法"负责把毛巾里的水拧干. 具体来讲就是把一个文件按照一定规则变小.  压缩算法一般只能处理单个文件, 对于多个文件, 只能单个文件压缩, 然后再打包.

(当然,前面也说到了, 第二种方法就是先把文件打包, 然后再压缩. tar.gz就是这样的. tar工具就是简单的把所有的文件首尾相接, 变成一个大文件, 然后再用压缩算法一次压缩的.  这个不是本文的讨论对象, 所以以后就不提了.)

 

7z默认使用的是lzma压缩算法.   单个文件会先用lzma压缩算法压缩,  然后7z负责把压缩过后的文件打包.   (这个跟zip类似, zip文件也是打包格式, 它默认使用deflate算法压缩.)  7z还支持封装其他几种压缩算法, 比如: Lzma2, ppmd, bzip2和deflate.

这些压缩算法在7z里面都有源码,  也不是本文要讨论的重点.  我们将重点讨论7z的打包格式. 就是介绍7z具体是怎样把压缩过后的文件封装打包的.  期间也会夹杂介绍其中一些算法.  后面如果有时间, 我会再单独介绍这些算法的具体实现.

终于把前期准备介绍完了,   有点繁琐.

下一篇我们将开始具体分析介绍7z的源码.    完成之后, 我会把第二篇的链接更新到这里. 当然你也可以在我的博客中搜索到.

大家多多支持哦.

 

 

 

 

 

 

 

 

 

 

 
byNeil
byNeil.com

原文来自 Blog by Neil, post 7z文件格式及其源码的分析 转载请注明出处。本站保留一切权力

翻译一篇很好的理解deflate算法的文章

最近做压缩算法. 用到了deflate压缩算法,  找了很多资料,  这篇文章算是讲的比较易懂的, 这篇文章不长,但却浅显易懂, 基本上涵盖了我想要知道的所有要点. 翻译出来, 留存.    可能对正在学习或者准备学习deflate算法的童鞋有所帮助.

先说一下deflate算法吧.  deflate是zip压缩文件的默认算法.   其实deflate现在不光用在zip文件中, 在7z, xz等其他的压缩文件中都用.   实际上deflate只是一种压缩数据流的算法. 任何需要流式压缩的地方都可以用.          deflate 还有微型改进版本deflate64. "微型改进型" 这个名词是我发明的, 为什么这么说, 因为改进实在太小了, 而性能提高也非常小. 以至于大名鼎鼎的开源zlib库到现在都不支持deflate64.      http://zlib.net/zlib_faq.html#faq40

开始正题, 原文地址: http://zlib.net/feldspar.html ,  我尽量按照原文直译,但是有些地方实在没必要就简单意译了. 有需要想交流的童鞋欢迎访问我的独立博客留言交流: http://byNeil.com

==========================华丽的分割线====================

Deflate 算法的介绍

作者: Antaeus Feldspar   feldspar@netcom.com

在理解deflate之前, 先理解它的两个组成算法非常重要: Huffman 编码 和 LZ77压缩

Huffman 编码

Huffman编码是一种前缀编码, 你其实知道, 但你可能不觉得. 比如打电话时, 从拨号开始, 你按下一串号码, 或许是5781112 或者别的号码. 一串号码就就能到达另一部特定的电话.  (翻译: 这个比方太罗嗦,本来不想翻译过来的.)

(这一段就不翻译了,没有实际内容.) Now suppose you're in an office setting with an internal switchboard, as many large companies do. All other phones within the bank only require five numbers to dial, instead of seven -- that's because it's expected that you'll be calling those numbers more often. You may still need to call other numbers, though -- so all of those numbers have a `9' added to the front.

...这就是前缀编码. 每一个你想要指定的元素都有一个由数字组成的代码. 由于每个代码都不可能是另外一个代码的前缀, 所以当你输入的时候,不会有歧义.

Huffman 编码是由一个特定算法生成的前缀编码. (翻译: 后面简单介绍如何生成Huffman编码, 都是教课书上的内容, 不翻译了, 自己看图, 直接跳过:) Here, instead of each code being a series of numbers between 0 and 9, each code is a series of bits, either 0 or 1. Instead of each code representing a phone, each code represents an element in a specific ``alphabet'' (such as the set of ASCII characters, which is the primary but not the only use of Huffman coding in DEFLATE).

A Huffman algorithm starts by assembling the elements of the ``alphabet,'' each one being assigned a ``weight'' -- a number that represents its relative frequency within the data to be compressed. These weights may be guessed at beforehand, or they may be measured exactly from passes through the data, or some combination of the two. In any case, the elements are selected two at a time, the elements with the lowest weights being chosen. The two elements are made to be leaf nodes of a node with two branches (I really hope you know nodes and trees...) Anyway, suppose we had a set of elements and weights that looked like this:

A 16
B 32
C 32
D 8
E 8
We would pick D and E first, and make them branches of a single node -- one being the `0' branch, and one the `1' branch.

( )
0 / \ 1
D E

...... (翻译中间省略无数废话,  都是在介绍怎么生成huffman树, 这个上过课的人都知道, 所以就不翻译了, 细节非常繁琐. 下面直接从 课本上没有的另一个算法 Lz77开始:)

LZ77 压缩
LZ77压缩算法靠查找重复的序列. 这里使用术语:"滑动窗口", 它的意思是:在任何的数据点上, 都记录了在此之前的字符. 32k的滑动窗口表示压缩器(解压器)能记录前32768个字符. 当下一个需要压缩的字符序列能够在滑动窗口中找到, 这个序列会被两个数字代替: 一个是距离,表示这个序列在窗口中的起始位置离窗口的距离, 一个是长度, 字符串的长度.

我觉得 看 比 说 更容易. 我们看看一些高压缩比的数据:

Blah blah blah blah blah!

字符流开始于: `B,' `l,' `a,' `h,' ` ,' and `b.' , 看看接下来的5个字符:

vvvvv
Blah blah blah blah blah!
^^^^^
接下来的5个字符正好和已经在数据流中的字符串相等, 而且刚好在当前数据点的前5个字符开始. 在这个case中,我们可以在数据流中输出特殊的字符, 一个长度数字 和一个距离数字.
目前数据是:
Blah blah b
压缩后的格式是:
Blah b[D=5,L=5]
压缩还能继续增加, 尽管要利用其全部的优势需要压缩器方面的智慧. 对比这两个相同的字符串, 对比它们各自的下一个字符,都是'l', 所以,我们可以把长度更新为6, 而不仅仅是5. 如果我们继续比较,发现下一个, 下下一个, 下下下一个都是一样的. 尽管前面的字符换已经延伸覆盖到了后面的字符串(需要压缩的字符串).
最终我们发现, 有18个字符相等. 当我们解压的时候, 当读到长度和距离对时, 我们并不知道这18个字符将会是什么. 但是如果我们把已有的字符放回去, 我们就知道更多. 而这有会让更多的字符放回去, 或者知道任何长度大于距离的数据对都会不断的重复数据. 所以解压器就可以这样做.
最终我们的高压缩性的数据能压缩成如下的样子:
Blah b[D=5, L=18]!
联合起来(翻译: 指的是把huffman编码和 lz77压缩算法联合起来用):
deflate 压缩器在怎样压缩数据上有非常大的灵活性. 程序员必须处理设计聪明的算法所面临的问题以做出正确的选择. 但是压缩器的确有一些选择.
压缩器有三种压缩模型:
1. 不压缩数据, 对于已经压缩过的数据,这是一个明智的选择. 这样的数据会会稍稍增加, 但是会小于在其上再应用一种压缩算法.
2. 压缩, 先用Lz77, 然后用huffman编码. 在这个模型中压缩的树是Deflate 规范规定定义的, 所以不需要额外的空间来存储这个树.
3. 压缩, 先用LZ77, 然后用huffman编码. 压缩树是由压缩器生成的, 并与数据一起存储.

数据被分割成不同的块, 每个块使用单一的压缩模式. 如过压缩器要在这三种压缩模式中相互切换, 必须先结束当前的块, 重新开始一个新的块.

关于Lz77和huffman如何一起工作的细节需要更进一步的检查. 一旦原始数据被转换成了字符和长度距离对组成的串, 这些数据必须由huffman编码表示.
尽管这不是一个标砖术语, 把开始读数据的点叫"拨号音", 毕竟在我们的类推中, 拨号音的确是我们指定一个电话的的拨号的开始点. 所以我们把这个起始点叫"拨号音". 在起始点之后, 只可能有三种元素能出现:字符, 长度距离对, 或者是块的结束标志. 因为我们必须能够区分它是什么. 所有可能的字符(字面量), 表示可能长度的区域, 以及特殊的块结束标记都被合并到同一个字母表中. 这个字母表就是huffman树的基础. 距离不需要包含在字母表中, 因为它只能出现在长度的后面. 一点字面量被解压, 或者长度距离对解压出来, 我们就开始了另一个拨号音, 重新开始读取. 当然,如果遇到块结束标志的话, 就会开始另外一个块,或者到达了压缩数据的末尾.
长度或者距离的编码实际上可以是: 一个基地址,后面跟上额外的bits(整数的形式,表示基地址后面的偏移),

可能deflate规范中最难理解的部分就是当数据时被特殊的树压缩的时候, 树与数据一起的压缩方式.
树 通过 编码长度(codelengths)来传输, 正如前面讨论的. 代码长度被全部放在一个由0到15之间的数字组成的序列中(huffman树种,代码长度必须不大于15, 这是最复杂部分, 而不是怎样约束元素的顺序).

并不是所有的元素都必须有一个代码长度. 如果字母表的最后的那些元素代码长度都是0, 他们能并且应该被忽略. 由于每个字母表中元素的个数都会被传输, 所以这两个字母表会被链接成单一的序列.

一旦编码长度序列组合完成,  它会被一种叫做 run-length 的压缩方式压缩. 当一行中的多个元素拥有一样的代码长度(常常是0) 的时候, 特殊的符号会用来表示这个长度的元素的个数.  现在这个序列式0到18之间的数字组成的了(可能带有额外的位组成修改基地址的值).

huffman 树就是为这个0到18的字母表创建的.

huffman树需要包含在数据中, 当然.  正如其他的huffman树一样, 它会被记录代码长度的形式包含进来.   然而, 它们的顺序不是 0, 1, 2, 3, 4 ... 16, 17, 18. 而是一个特殊的顺序:16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15.  这背后的逻辑是:越靠近序列末尾的代码,越可能是长度为0. 如果它们的确是0, 就能被省略掉. 直接记录的元素的个数也会包含在数据中.

这些就是我觉得在deflate 规范中的难点. 多花时间读规范,应该能帮助了解. 有任何别的问题请联系: - Antaeus Feldspar ( feldspar@netcom.com)

 

 

======================分割线 完==================

 

 

 
byNeil
byNeil.com

原文来自 Blog by Neil, post 翻译一篇很好的理解deflate算法的文章 转载请注明出处。本站保留一切权力