九天雁翎的博客
如果你想在软件业获得成功,就使用你知道的最强大的语言,用它解决你知道的最难的问题,并且等待竞争对手的经理做出自甘平庸的选择。 -- Paul Graham

MPQ文档布局分析

MPQ文档布局分析(以暗黑破坏神2的一个补丁patch_d2.MPQ和燃烧远征的一个补丁patch-2.MPQ文档为实例,以下简称D2,P2)

 

说明:因为MPQ实际上是由很多文件数据组成,包含很多文件,为了区别好MPQ文件与一般文件,这里将MPQ文件在作为一个集合的时候称为文档(ARCHIVE),表示实际存储在硬盘上的一个文件时称为MPQ文件(file),而文件都指保存于MPQ中的一般文件.

 

说明2:intel x86系统的存储格式都是低位在前(Little-endian),比如一个int32型的数据44(00 00 00 2Ch)存储在文件和内存中实际为2C 00 00 00h,下面不再说明.

 

说明3:以下以[]后缀中表示此类型一共重复几次,()前缀表示一个此类型所占字节数.比如(1)char[4]表示此处有41个字节的char类型数据.

 

说明4:本文主要信息来自The MoPaQ File Format 1.0.txt,只是附带个人结合D2,P2后的分析,因为会经常提到原文件,以后简称其为MFF.另外也经常会提到http://www.zezula.net/en/mpq/mpqformat.html一文,简称为MFH.

 

说明5:在一段文本的开头的十六进制数字都表示文件中的偏移地址,在段中,都以offset +十六进制数字说明此处表示在原文件的偏移地址.

 

文档总体布局

-          文档头

-          文件数据

-          文件数据 特别文件

-          哈希(hash)

-          (block)

-          扩展块

-          强数字标志(strong digital signature)

 

文档头:

00H: (1)char[4]: 指示这个文件是MPQ文件,肯定是ASCII “MPQ” 1Ah.

D2前四个字节为4D 40 51 1Ah 吻合.

P2前四个字节为4D 40 51 1Ah吻合.

另外,MFH中知道,当第4个字节(1)1Ah的时候表示这里开始的是一个MPQ文档头,这里还可以为1Bh,表示这里开始的是一个MPQ shunt结构.

 

04H: (4) int32: 文档头文件的大小.

D220 00 00 00h,32个字节.

P2 2C 00 00 00h ,44个字节.

 

08H: (4)int32: 整个文档的大小,包括文档头信息.不包含强数字信息(假如有的话).在燃烧远征中是从文件头到文件尾的所有信息.

D225 1B 20 00h,2104101个字节, 从显示上来看,与文件大小一致,意思是此文件可能不包括强数字信息.

P210 CC 12 00h,1231888个字节,从显示上来看,与文件大小一致,意思是此文件可能不包括强数字信息.或者因为此文件为燃烧远征文件,所以为文件大小.

 

0CH: (2)int16: 版本信息,表示的是MoPaQ的版本.当其为负的时候,MPQAPI将不会打开文档.

已知版本:

原始版本:0,文档头应为32个字节,不支持大文档.

燃烧远征:1,文档头应为44个字节,支持大文档.

D200 00h,0,表示此MPQ文件为原始版本文件,另外,此文件的文档头从上面看的确为32各字节,吻合.

P201 00h,1,表示此MPQ文件为燃烧远征文档,另外,此文件的文档头从上面看的确为44个字节,吻合.

 

0EH: (1)int8 扇区偏移大小(SectorSizeShift):指示的是每一个文档的逻辑扇区的大小.总为512 * (2^扇区偏移大小).此处MFF指出,因为Storm librarybug,在其中规定只能为3,计算后为512* (2^3) = 4096字节.MFH可以知道,这里的意思其实就是指一个未经压缩的块大小,通常为4KB.但是假如一个文件经过了压缩,一个块就是变长的了.

D2,P2中此处值都为3,也就是指示此文档逻辑扇区的大小为4096字节,Storm library的规定的一样,可能因为大部分暴雪的MPQ文档中此值都为3,所以Storm library才会因为不经意的存在此bug,而且就算有此bug也没有太在意,因为不至于太影响使用.另外,MFF中说此处为(1)int8,并且在以后也没有说明offset 0FH处的数值含义,D2,P2中都为00h,怀疑offset 0EH处值应为(2)int16,结合0F一起, 03 00h,还是表示3,

 

10H: (4)int32 哈希表偏移值,指示从文档开始,到哈希表开始地址的偏移量.

D265 0E 1C 00h 1838693个字节, 从文档大小2104101个字节来看,处于文档的中部,并偏向尾部,与文档总体布局一致,因为很明显,文件数据和特别文件的数据才应该是占用文档空间的主要部分.

P250 CB 12 00h 1231696个字节,从文档大小1231888来看,处于文档的尾部,也符合以上推论,但是此是哈希表便宜值处于这么尾部而不是和D2一样处于相对中部的位置,说明P2的哈希表,块表,扩展块表比较小,一共才192个字节.可能是因为P2中所含文件较大,而文件的数量较小,所以需要用来索引的内容较小,从后面的分析来看是正确的.

 

14H: (4)int32 块表偏移值, 指示从文档开始,到块表开始地址的偏移量.

D265 0E 20 00,2100837个字节,处于哈希表偏移值1838693和文档大小2104101之间, 与文档总体布局一致.并且从此可以得出结论,D2的哈希表大小为262144个字节.最后块 Table 扩展块表加起来还有3264个字节.

P2D0 CB 12 00,1231824个字节, 处于哈希表偏移值1231696和文档大小1231888之间, 与文档总体布局一致.并且从此可以得出结论,D2的哈希表大小为128个字节. 最后块 Table 扩展块表加起来还有64个字节.

 

 

18H:(4)int32 哈希表入口数量,必须是2的幂,而且对于原始版本MPQ文件必须小于2^16,对于燃烧远征版本必须小于2^20.

D2中为00 40 00 00,16384,2^24.

P2中为08 00 00 00,8,2^3.

以上数据符合开始对于D2文件多,P2文件少的推论,结论有待下一步验证.另外,从这里也可以算出每个哈希表入口的大小为128/8 = 16个字节,16384 * 16 = 262144也可以得到验证.

 

1CH: (4)int32 块表入口数量.

D2中为CC 00 00 00,204,

P2中为04 00 00 00,4.

MFH中提到,块表的入口数量比块的数量要大一,最后一个入口被用来得到最后块的大小.并且每个入口为16个字节.

 

 

只在燃烧远征(P2)及其以后版本才出现的文档头文件为:

20H:(8)int64 从文档头开始的扩展块表偏移值,

因为D2此处已经是文件数据,从此一下不再说明.

P2中此处为00 00 00 00 00 00 00 00,即无扩展块表.

 

28H:(2)int16 大文档哈希表偏移值的高16位值.

P2中此处为00 00,因为P2并不是大文件,所以用不上此值.

 

2AH:(2)int16 大文档块表偏移值的高16位值,

P2中此处为00 00,因为P2并不是大文件,所以用不上此值.

 

最后通过20H2AH上面的分析,可以得出结论就是原始格式的MPQ文件并没有扩展块表,因为那里没有连扩展块表的偏移值都没有说明,另外,因为D2,P2中都没有扩展块表和强数字信息,所以块表实际就是文档的结尾,实际上通过块表入口数量*块表入口大小,也可以得出相同结论(16*204 = 3264 ,16*4 = 64)

 

在文档偏移量为0的时候,文档头是文档的第一个结构,然而,在包含文档的文件中,文档的偏移量不是必须为0.在文件中文档的偏移量在这里被称为文档偏移量(Archive Offset),假如文档不是文件的开头,就必须开始与一个磁盘扇区的边界(512个字节).

MFH中又可以知道,当处理MPQ的时候,应用程序只需要一个一个查找0x200h,0x400h(512的倍数)直到找到文档头,或者到达文件的末尾.这样可以方便的将MPQ文档储存在其他文件格式中,比如EXE,这样甚至可以在安装文件setup.exe,install.exe中假如MPQ文档.

早期版本的Storm库需要文档在文件的结尾(文档偏移量 + 文档大小 = 文件大小),但是在更新的版本中已经不需要了.(因为强数字信息不再被认为是文档的一部分).

以上即为全部的MPQ文件头分析.

 

 

块表:

块表包含文档内每个区域的入口,区域可能是文件,空闲空间,或者没有使用的块表入口,其中空白空间主要来自于删除的文件数据,可以被新文件覆盖.空闲空间入口应该有非零的块偏移值和块大小.和为零的文件大小,Flags.未使用的块表入口应该有为零的块大小,文件大小,Flags.块表是使用”(block table)”key的哈希算法加密的.

而各种数据实际上就是放在一个一个的由块表指定的块中.

 

首先,从文件头已经知道,D2的块表开始于00 20 0E 65h,P2的块表开始于00 12 CB D0h.对比分析从上面两个地址开始.为了更加明了,我将从MFF中的相对于块表的偏移量,(对于每个文档都适用)计算出绝对偏移量(当然只适用于D2,P2这两个文件,不过对于分析这两个文件来说,更加清晰,以下只分析了第一个入口).此表不是像我先想的那样有表头,从块表的一开始就是块的入口,和对此块的描述,偏移4个字节以后就是第二个入口,以此类推.

相关的函数为EncryptBlockTable()加密, DecryptBlockTable()解密.

在加密解密的时候有两个地方需要注意,而我开始没有注意的是:

1.       运行加解密算法前,需要先运行PrepareStormBuffer()函数,初始化好用来加解密的Buffer.

2.       Block加解密算法必须是一次从头开始对一整块数据进行,比如,可以一次解密第一个入口的第一个值(块偏移值),但是不能单独对第二个值(块大小)解密.可以一次解密整个第一个入口的4DWORD的值,但是不能单独对第二个入口进行解密,简而言之,在对后面数据解密的时候必须要有前面的数据.并且要得出正确的结果,那么前面的任何数据都不能有任何错误.很显然,加密的时候也需要这样,经过测试,的确如此.

第一个入口的结构如下:

00H:(4)int32 相对于文档开始的块偏移值.

D2中地址为00 20 0E 65h ,数据为AB 67 48 3DH,

P2中地址为00 12 CB D0h,数据为A7 67 48 3DH,

以上都为加密数据,但是其实我们是知道块的偏移值的,文档头下面就应该是块,D2中应该从32个字节以后,即从20H开始,P2应该是从44个字节以后,即从2CH开始.知道这些以后,正好可以验证一下Strom库的哈希算法 经检验,DecryptBlockTable解密数据后,和猜测吻合.

 

04H:(4)int32 块大小.假如块为文件,某些文档表示这里就是压缩过的文件的大小.

D2中的地址为00 20 0E 69H,数据为 B9 E4 08 CAH, 解密后为14104

P2中的地址为00 12 CB D4H,数据为 D9 0E 06 CAH, 解密后为974196

 

08H:(4)int32 储存在块中的文件数据大小,只有在块是一个文件的时候有效;不然的话无意义,而且应该为0.假如文件是压缩的,这里表示的是解压后的文件数据大小.

D2中的地址为00 20 0E 6DH,数据为 7F BF 34 F8H, 解密后为85652

P2中的地址为00 12 CB D8H,数据为37 7A 5B F8H, 解密后为2089956

 

0CH:(4)int32 块的位掩码标志位.

以下为已经确定的数值:

80 00 00 00H: 接下来有表示文件数据类型的位值,那么这个块是一个文件.不然块是一个空闲空间或者未使用的空间.假如这个块不是一个文件,所有其他的标志位应该为0.

01 00 00 00H: 文件作为单一单元储存,而不是分成很多扇区.

00 02 00 00H: 文件的密钥经过块偏移和文件大小调整.文件必须是加密的.

00 01 00 00H: 文件是加密的.

00 00 02 00H: 文件是压缩的.文件不能被imploded?

00 00 01 00H: 文件是imploded,文件不能被压缩.

D2中的地址为00 20 0E 71H, 数据为75 DB 3B E8H, 解密后为80 00 01 00H,按上面的意思来看,这表示D2的此块块为一个imploded的未压缩文件.

P2中的地址为00 12 CB DCH,数据为AD 16 3E EEH, 解密后为84 00 02 00H,上面的表没有说明04 00 00 00H位表示什么意思,但是可以看看出此文件是被压缩的文件.

 

哈希表:

为了快速存取,作为文件名的替代,MPQ中使用了以2的各次幂为大小的文件的哈希表.一个文件通过它的完整文件路径名,语言和平台唯一识别.一个文件在哈希表中的home入口用一个文件的完整文件路径名的哈希计算得到.当此入口已经被其他文件占用的时候,使用了顺序溢出方式(progressive overflow),这个文件被放置在下一个可用的哈希表入口.在哈希表中搜索一个想要的文件过程是,home入口直到这个文件被找到,或者搜寻整个哈希表.或者是碰到一个空的哈希表入口(文件块索引为FF FF FF FFH).哈希表通过以”(hash table)”keyhash运算加密.

以下内容与块表类似,也只看第一个入口,但是每一个入口的结构还是相同的.

相关的函数为加密哈希表:EncryptHashTable(),解密哈希表:DecryptHashTable(),文件完整路径名哈希值计算方法1(A):DecryptName1(),文件完整路径名计算方法2(B): DecryptName2(),得到一个文件的哈希表home入口:DecryptHashIndex(),得到一个文件真正的哈希表入口:GetHashEntry().

其中GetHashEntry()算法的在BlizzardMPQ文件格式搜索算法 - GameRes游戏开发论坛.htm一文中有详细描述:

1.计算出字符串的三个哈希值(一个用来确定位置,另外两个用来校验)
2. 
察看哈希表中的这个位置

3. 
哈希表中这个位置为空吗?如果为空,则肯定该字符串不存在,返回
4. 
如果存在,则检查其他两个哈希值是否也匹配,如果匹配,则表示找到了该字符串,返

5. 
移到下一个位置,如果已经越界,则表示没有找到,返回
6. 
看看是不是又回到了原来的位置,如果是,则返回没找到
7. 
回到3”

其中用来确定位置的哈希值,指的就是哈希表home入口.DecryptHashIndex()函数得到,两个用来效验的哈希值就是用算法A和算法B得到的哈希值,分别用DecryptName1(),DecryptName2(),函数得到,另外这三个值都是仅仅用来比较,所以都是单向的,函数源码的具体理解待理解源码的时候再去看.虽然在strom库里面被命名为DecryptName,其实是个从文件完整路径名到一个DWORD整数的哈希计算过程,更像是HashEncrypt.

 

从上面文档头的分析可知:

D2的哈希表位置开始于00 1C 0E 65H. P2的哈希表开始于00 12 CB 50H.

因为需要一块解密,所以4个字节的

00H:(4)int32 文件路径哈希值A: 用算法A得到的文件路径哈希值.

04H:(4)int32 文件路径哈希值B: 用算法B得到的文件路径哈希值.

08H:(2)int16 这个文件的语言.这是一个windows LANGID数据类型而且使用同样的值.0表示是默认语言(American English),或者这个文件是语言无关的.

0AH:(1)int8 平台:这个文件被用来使用的平台.0表示默认平台,目前没有看到过其他的值.(很明显应该为int16,估计是文档中的错误)

0CH:(4)int32 文件块索引:假如哈希表入口是有效地,这个是个到这个文件的块表的索引.不然的话,可能为下面两个值:

FF FF FF FFH: 哈希表入口为空的,而且一直是空的.结束搜索一个给定的文件.

FF FF FF FEH: 哈希表入口是空的,但是某些时候是有效的(意思就是说,这个文件以前被删除了).继续向下搜索给定的文件.

上面这个特性要说明的是,MPQ,一个文件被删除以后,实际上并不能回收空间,仅仅是删除了这个文件的路口,此时最后这个文件块索引就标志为FF FF FF FEH,那么这个文件后面还可能有文件,所以继续搜索.补充一点的就是,虽然空间不能被回收了,但是当新的文件增加进来的时候,只要这个文件比原来删除的文件要小,就可以放进空闲下来的空间.但是新的文件较大的时候新的文件将扩展.这点在频繁删除增加文件后会导致空间的很大浪费,唯一的解决办法就是先读出这个MPQ文档的数据,然后重新构建一个新的MPQ文档.感谢the MPQ API Library 2.0的创作者Justin Olbrantz(Quantam),他写了一个mpqcompactarchive()函数,用来解决此问题.另外他还写了另外两个有用的函数MpqRenameFile(),用来改变MPQ文档中已有文件的文件名, MpqAddWAVToArchive(),用来在添加WAV文件的时候对其进行特殊的更有效的压缩.

D2中此入口的数据为:

00H:33 30 C3 79

04H:28 D9 32 98

08H:BC 73

0AH:6F 9F

0CH:B2 88 4E E9

解密后,D2中连续两个入口都为全FF,没有办法判断.用了很久时间也没有办法改变这一点,可能是因为文件删除了,所以才会这样..............

P2中可以得出比较合理的结果,文件语言和平台都为0,块索引在最开始的两个哈希表入口中分别为02,所以推测是 文件块索引的表示不是相对于整个文件,而是相对于块表的开始而言.(MFF中没有描述),不然, DecryptHashTable()函数得出的结果都是错的.

而这里又暂时还不知道具体的文件名,没有办法通过EncryptHashTable()函数来检验P2中得到的结果是否正确.

 

以下内容基本上翻译自MFF,自己顺便理解并记录成中文.因为还没有通过实际代码编写调用函数来检验.因为下面内容不像文档头和哈希表,块表一样,能知道存储的是什么内容,光从文件中也不能反向计算哈希值前的文件完整路径名,所以只能暂时通过这种方式了解一下文档的大概结构.

 

文件数据:

每个文件的数据都由下面部分组成:

00H:(4)int32(文件中的扇区+1)扇区偏移值表(SectorOffsetTable: 相对于文件数据开始处每个扇区的偏移值.最后的入口包含文件的大小,使得它可能很容易的计算出任何给定扇区的大小.假如信息可以被计算出来,这个表是不会出现的.

扇区偏移值表后: 文件中每个扇区的数据,首尾相连的打包

通常来说,文件数据简单的分开存在扇区里.所有的扇区,将包含文档头扇区偏移大小确定大小的文件数据.依据整个文件数据的大小不同,最后的扇区可能少于这个数值.假如文件是压缩的或者imploeded,扇区将比他包含的文件的要小.在压缩或者imploded的文件的各个扇区中,也可能存储这未压缩的数据,当且仅当这个文件的这个扇区中的数据不能被需要的算法压缩时.这时,在扇区偏移值表中的扇区值就等于在扇区中的文件数据大小. 

各扇区的格式决定于扇区的种类.没有压缩的扇区仅仅是原始的文件数据.

Imploded扇区是原始压缩过的数据,再经过implode算法计算过的值.

压缩过的扇区中数据是用一个或两个压缩算法压缩过的.而且有以下的结构:

00H:压缩位掩码:指示了这个扇区的压缩种类,可以复合使用.它们以以下列表的顺序应用,而且应该用相反的顺序解压.这个字节从总共的扇区大小计算而来,意味如果数据不能被至少两个字节压缩,扇区将不能作为未压缩的方式存储数据.也就是说,这个字节是用扇区数据加密的,假如可以的话.

    40h: IMA ADPCM mono

    80h: IMA ADPCM stereo

    01h: Huffman encoded

    02h: Deflated (see ZLib)

    08h: Imploded (see PKWare Data Compression Library)

    10h: BZip2 compressed (see BZip2)

01h: byte(SectorSize - 1) SectorData : 这个扇区被压缩过的数据.

假如这个文件是作为单一单元存储的(在文件标志中有指示),那么这里只有一个存储了整个文件数据的单一扇区.

假如文件是加密的,每个扇区(假如可以应用的话,在压缩或implosion以后)是用filekey加密的.基本的文件key(base key)是不带路径的文件名,假如这个key是修改过的(就像在文件标志中指示的那样),最后的key通过((base key + 块偏移值 文档偏移值)XOR 文件大小)计算得到.(MFF原注:Strom库中使用AND替代XOR是不对的).每个扇区都是使用这个key + 在文件中以零为基础的扇区为索引.

 

假如存在扇区偏移值表(SectorOffsetTable)的话,是用值为-1key加密的.

扇区偏移值表在大小和在文件中所有扇区的偏移值可以从文件大小中计算出来的时候是被忽略的.这可能有数种情况:

假如文件是没有压缩/imploded过的,这时,大小和所有扇区的偏移值在扇区偏移值大小(SectorSizeShift)的基础上是已知的,假如文件作为单一的压缩/imploded单元存储,这时,扇区偏移值表被忽略,因为就如前面提到的那样,单一文件的扇区与块大小和文件大小相符.然而,假如文件是压缩/imploded过的而且不是作为单一的单元存储,甚至这个文件只有一个扇区,扇区偏移值表也要有.

 

文件列表:

文件列表是MPQ一个非常简单的扩展,包含文档中文件的(大部分)文件路径.文件的语言和平台不存储在文件列表里面.文件列表包含在文件”(listfile)”(默认的语言和平台),而且仅仅是一个简单的文本文件,在里面文件的路径通过’;’,0DH,0AH或它们的组合分隔.文件”(listfile)”可能不列在文件列表中.有了这个列表,就可以先通过这个列表了解文档中一共包含了哪些文件,这样就可以通过文件名的哈希计算来验证前面得到的哈希表是否正确了.当然,假如不知道前两个哈希表入口表示的是哪两个文件,要么就如同算法一样遍历哈希表,要么就遍历计算文件:)

 

附加属性:

可选属性,这些属性在MPQ文档格式已经确定了以后再加入进来,所以不是每个文档都必须有所有(任何)这些属性.假如一个文档包含一个给定的属性,将会有一个对每个在块表中的块分别适用的属性值,尽管当这个块不是文件的时候这个属性值将没有意义.属性值的顺序和块在块表重的顺序一样.属性总是以数组的形式存储在”(attributes”)文件中(默认的语言和平台).属性值对应的文件不是必须有效的.不像所有其他结构一样,在附加属性中入口不保证是相连的.并且,看到在一些文档中,为了防止别人对文档的查看,存在恶意的附加属性位置移动.

此结构的意义如下:

00H:(4)int32 版本:定义附加属性的版本,到目前位置肯定是100.

04H:(4)int32 存在的属性: 在附加属性中存在的位掩码.

00 00 00 01H: CRC32文件

00 00 00 02H: 时间戳(timestamps)文件

00 00 00 04H: MD5文件.

08H:(4)int32 块列表入口的CRC32.文档中每一个块未压缩的文件数据的CRC32.当文档没有CRC32的时候忽略.

CRC32以后:  文档中每一个块的时间戳.格式是windowsFILETIME格式.假如不存在,忽略.

在时间戳以后: MD5文档中每一个块的未压缩文件数据的MD5.没有的话,忽略.

 

 

分类:  游戏开发 
标签:  MPQ 

Posted By 九天雁翎 at 九天雁翎的博客 on 2008年06月02日

前一篇: MPQ Strom库使用及源代码理解文档 后一篇: SelfExtractor自解压模块理解文档