，最近正好对mpq发生兴致，看到一片文章叫做 inside MPQ,于是翻译一下，就当锤炼本人吧。这篇文章十分的不厚道，在要害处所戛然而止，而且不更新的迹象。让人愁闷无比。然而仍是比国内一些研讨MPQ的少的可怜的文章要好些。看了这些文章，无比可惜海内技巧的滞后跟黑客技术，逆向工程技术的贫乏。咱们老是拿来主义，做利用。自己的原创真的太少了。

　　LEGAL COPYRIGHTS

　　The MPQ Format The copyrights to the MPQ format are held by Havas Interactive, Blizzard Entertainment's parent company, all rights reserved This Article The copyrights to this document and content are held by Justin Olbrantz(Quantam), all rights reserved. You may freely distribute this document provided that you do not derive profit from the distribution, and that the document remains complete and unchanged. You may quote this document ONLY with my explicit permission. Contact me to obtain permission to quote.Also, although I would appreciate recognition for your use of this information, I will not be held legally responsible for anything you may do with it. Anyway that you misuse this information is your problem, and I will not be responsible for it.

　　这个LEGAL COPYRIGHTS我就不做翻译了。a

　　对于我这篇翻译的文章，声名如下：

　　可以转载，但要注明作者是王宇，并且保证整个内容包括上面几段内容的完全性。并且我对所有成果不承当义务。

　　MPQ 技术内情

　　作者 Justin Olbrantz(Quantam)

　　译者 王宇

　　第1章

　　MPQ简介

　　MPQ 或者称作 MoPaQ 是Mike O'Brien创建的领有私人版权的档案文件格式。Mike O'Brien是暴雪公司的多人游戏引擎方面的蠢才。他在1996年，为了暗黑破坏神而开发出这种档案文件格式。并且自恋的以自己的名字"Mike O'brien PaCK"给这种格式命名MPQ。但是文档的版权却由Havas Interactive（暴雪的父公司）所有。所以，即使现在Mike分开了暴雪，暴雪仍旧占有MPQ格式的使用权。MPQ格式在暗黑破坏神，星际争霸，魔兽争霸2，3，暗黑损坏神2，BNE（译者备注：我不知道这是什么游戏），Lords of Magic（由sierra公司开发，这个公司同样附属于Havas）等游戏中都有运用。

　　一个档案文件是指一个包含其余文件在内的文件，并且它常常是以压缩的情势存在的。Havas用MPQ包含了游戏中简直所有的东西。比如装置文件，游戏数据等等。其中游戏数据的MPQ封装是非常重要的。这些MPQ当中包含了图像，声音，等级，字符串，故事线信息等等。Obviously, the potential for customization is astounding. （译者备注：这句不好翻）但是，为了用MPQ，你必须首先理解它。

　　在MPQ之前

　　在MPQ创造之前很长一段时光，有一种个是叫做WAR（Warcraft ARchive）格式。这种格式是在魔兽争霸2甚至1中存储数据的格式。这种雏鸟格式非常的简单，也没有优化，总是看起来就是一个实切实在的新手文件格式。档案中的文件是按照坐标来寻址的，独一的一点点优化就是用了一些压缩技术。但是，虽然它简单，它完成了它需要完成的任务。它提供了一种疾速但是龌龊的方法压缩的存储了很多文件。但是未几，毛病就开始裸露出来了。依照坐标来寻址意味着必须保存一个很长的进口表来供程序员使用档案中某些文件的时候调用。当这个表越来越长的时候，工作就变得越来越漫长。而且这种简单的格式意味着黑客可以很容易的在15分钟内破解除这种格式，然后可以为所欲为的在这些文件上做一些事。这些问题一开始看起来可能还不太糟，但是当暗黑破坏神所请求的persistent characters（译者备注：这个我不懂），站网的遍及让这些问题变得无奈接收了。

　　为什么是MPQ

　　正如前面所说，MPQ格式是为了补充一些WAR异常重大的缺点设计的。但是它依然增加了许多新的特征。总的说来，MPQ的特色如下：

　　平安性：暴雪最不乐意的就是人们象破解魔兽争霸2那样破解它以后的游戏。而且暴雪很可能已经感到要把MPQ格式应用到星际争霸上面。无论怎么样，安全性是最最重要的。这点可以从那些暴雪保护这种格式的折磨人的努力中看出来。

　　效力：MPQ需要实现一系列工作，从最简略的预读数据到复杂的实时流。对于预读数据倒还没什么，但是对实时流，因为数据必需以很快的速度一边玩游戏一边解紧缩，所以，速度是强迫的。

　　多语言：在最一开端，暴雪就打算把它的产品推向世界市场，所以，它愿望它的游戏的翻译能尽量轻易。于是它用了一种改革的方式，就是把多语言性的本事放在MPQ格局里面。

　　可扩大性：很显然的，把一个游戏所有的数据放入一个档案是很傻的。不仅没有效率，速度很慢，而且售后升级会变得非常麻烦。暴雪当然知道这点，因此，为了使售后进级简单，有效，优雅，它在MPQ格式的设计上就斟酌到了这个问题。

　　风暴 Storm

　　良多程序员为了避免冗余代码，通常会把一些常用的代码封装到共享库里面。这些共享库可以供给程序员常用的函数。这样可以减少冗余和程序体积。所以，暴雪用一个共享库叫做Storm（在微软平台上叫做Storm.dll, 在苹果平台上叫做Storm.bin）这个库被当初的暴雪游戏用来贮存主要函数，比方MPQ的读入，战网，甚至是图像路由。当暴雪宣布一个新游戏的时候，它会在storm里面参加函数，但是不会修正旧的函数。这象征着一个老的游戏能够用新的Storm库而不会出问题。像任何共享库一样，Storm的函数可以被任何人使用，这样就使它的保险性变得很差。这就是Storm只包括MPQ的读取函数而MPQ的写入函数却是暴雪的私家财产，它不会容许任何人去应用的起因了。

　　星际争霸的义务编纂器

　　大家都晓得星际争霸的任务编辑器可以编辑任务。但是星际争霸的任务就是MPQ！这意味星际的任务编辑器可以创建MPQ，所以其中有MPQ的创立函数。不外星际争霸的任务编辑器不是一个共享库，所以要用一系列诡异的黑客技术去破解它。于是有了MPQ API 库。

　　第2章

　　基本

　　大多数计算机历史上的提高是因为有特别的问题需要解决。在这章，我们将懂得一下对于MPQ格式的问题和它们的解决方案。

　　哈希

　　问题：你有一个很大的字符窜数组。你有另一个字符窜str需要判断是否存在于这个数组里面。可能你就会按照次序一个一个的比较数组里面的内容。但是在实际应用中，你会发现这种方法远慢于实际需要。必须对此做一些优化。但是如何你才干知道这个字符窜是否存在却不必把它同数组中的所有其它字符窜比较呢？

　　解决计划：哈希。哈希是用来取代大一些的数据类型（好比字符窜）的小一些的数据类型（比如数字）。在我们这个问题里，你可以把字符窜数组储存为哈希数组。而后你就可以比拟另外的那个字符窜str的哈希同储存的哈希数组中所有的哈希。如果哈希数组中的一个哈希同str的哈希匹配，那么这个哈希所代表的字符窜就可以同str进行比较来断定到底是否相同。这种办法叫作下标（indexing），依据数组大小和字符窜长度的不同，它可以把速度晋升将近100倍。 unsigned long HashString(char *lpszString)

　　{

　　unsigned long ulHash = 0xf1e2d3c4;

　　while (*lpszString != 0)

　　

　　ulHash <<= 1;

　　ulHash += *lpszString++;

　　

　　return ulHash;

　　}

　　以上的代码展现了一个非常简单的哈希算法。函数计算了字符窜中的字符个数，在每个字符加入之前把哈希值左移1位。应用这个算法，字符窜"arr\units.dat"将会被哈希成0x5A858026，而"unit\neutral\acritter.grp" 将会被哈希成0x694CD020。不可否定，现在这个算法非常的简单，而且没有什么用途。因为它产生了一个绝对可以预感的成果,传奇私服合击版。而且会有很多冲突。chogntu 是指多个字符窜哈希到同样一个数值。 而另一方面，MPQ格式却用了一种非常复杂的哈希算法（如下所示）去天生一个完全不可预感的哈希值。事实上，这种哈希算法叫做单行道哈希（one-way hash）。单行道哈希是指根据哈希值不能推回去找到源字符窜的哈希算法。应用这种MPQ算法，文件名"arr\units.dat" 将被哈希为0xF4E6C69D，而"unit\neutral\acritter.grp"将被哈希为0xA26067F3. unsigned long HashString(char *lpszFileName, unsigned long dwHashType)

　　{

　　unsigned char *key = (unsigned char *)lpszFileName;

　　unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;

　　int ch;

　　while(*key != 0)

　　

　　ch = toupper(*key++);

　　seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);

　　seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;

　　

　　return seed1;

　　}

　　哈希表

　　问题：你试图使用之前例子里面的下标法，但是你的程序需要无比严厉的速度限度。这时候你就会发明下标法不够快了。这时候你让它变得更快的方法只能是不让它检查数组中所有的哈希。或者，更好的是只让字符串同数组中的某个元素比较1次就能判定出这个字符窜是否存在于这个数组。听起来太好了甚至于不可能对错误？

　　解决方案：哈希表。哈希表是一种下标为字符串哈希值得数组。我的意思是说，我们为这个哈希表构建一个不同于字符串数组的定长数组（我们把它的元素个数定位1024，2的偶数次幂）。这时候，当你想要知道一个字符串是否在哈希表中时，你得首先计算这个字符串如果在哈希表中，那么它的位置是多少。首先我们计算这个字符串的哈希，然后用哈希模取之前的表长（1024）就得到了位置值。因而，如果你用之前的简单哈希算法，"arr\units.dat"将被哈希为0x5A858026，得到它得位置值为 0x26 (0x5A858026 模取 0x400 商为 0x16A160余数为0x26）。0x26这个位置的字符串（如果有的话）将被读出来与目标字符串比较。如果0x26这个字符串与目的字符串不匹配或者0x26的这个字符串不存在，则这个目标字符串不存在于这个数组中。以下的代码阐明了这点： int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)

　　

　　int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;

　　if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))

　　return nHashPos;

　　else

　　return -1; //Error value

　　

　　可是现在，这个算法有一个宏大的缺陷。你以为当摩擦（2个字符窜哈希到同样一个值）发生的时候会怎么样？显然它们不能占用哈希表中的统一个元素。个别,传奇sf第一家族，这种缺陷通过使哈希表中的每一个元素成为一个链表来实现。每个链标中将寄存哈希值相同的字符窜。MPQ使用文件名哈希表来跟踪内部的所有文件。但是这个表的格式与畸形的哈希表有一些不同。首先，它没有使用哈希作为下标，把实际的文件名存储在表顶用于验证，实际上它基本就没有存储文件名。而是使用了3种不同的哈希：一个用于哈希表的下标，两个用于验证。这两个验证哈希替换了实际文件名。当然了，这样仍旧会呈现2个不同的文件名哈希到3个同样的哈希。但是这种情况发生的概率均匀是1:18889465931478580854784，这个概率对于任何人来说应当都是足够小的咯。MPQ哈希表不同用通常的链表抵触解决法，当矛盾发生时，元素将被下移到下一个空着的位置。请看下面的代码，根本就是MPQ定位文件名的方法： int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)

　　{

　　const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;

　　int nHash = HashString(lpszString, HASH_OFFSET),

　　nHashA = HashString(lpszString, HASH_A),

　　nHashB = HashString(lpszString, HASH_B),

　　nHashStart = nHash % nTableSize,

　　nHashPos = nHashStart;

　　while (lpTable[nHashPos].bExists)

　　

　　if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)

　　return nHashPos;

　　else

　　nHashPos = (nHashPos + 1) % nTableSize;

　　if (nHashPos == nHashStart)

　　break;

　　

　　return -1; //Error value

　　}

　　固然这段代码可能看起来让你费解，但是它背地的实践却并不庞杂。它在读取一个文件的时候基础遵守了以下的步骤：

　　1 盘算3个哈希（1个下标哈希和2个检查哈希）并且把他们存入变量

　　2 移动到下标哈希所指的元素

　　3 这个元素存在吗◆如果不存在，停滞搜索，返回"文件没有找到"

　　4 元素的两个检查哈希是否我们搜索的文件的检讨哈希相匹配？如果相匹配，就返回当前的元素。

　　5 挪动当前下标到下一个，如果到达最后一个下标，则回到第1个

　　6 我们刚一动到的元素的下标哈希是否雷同（我们是否搜寻了全部表）假如是，结束搜索，返回"文件没有找到"

　　7 回到第3步

　　如果你留意了，你会发现，在我的解释和例子中MPQ哈希表需要保留所有的文件名。但是，你有没有想过当所有的哈希表行全体都填满的时候会发生什么？答案可能会让你非常惊奇：你将不能再增添任何文件。有人问我为什么一个MPQ会有文件数目限制，有没有什么方法可以解决这种制约。你已经直到第一个问题的谜底了，对于第2个问题，很遗憾，你不能解决这种文件数量限制。因为哈希表不能再不影响整个文件改变的情形下改变大小。这是因为哈希表中每个元素的哈希都因为哈希表大小的变更产生转变，这样我们就不能得到文件在新的哈希表中的地位，于是我们就不能得到文件名了。

　　压缩

　　问题：你有一个很大的程序（比如50MB）你现在生机把它发不到Inter网上。但是50MB将会是非常大的下载，人们可能就不会乐意等上多少个小时去下载这么一个货色。

　　解决方案：压缩。压缩是指把一大堆数据用一种很小的格式表白出来。世界上有很多种压缩算法，每一种都用不同的方法工作。而我们的MPQ使用的数据压缩算法是PKWare的数据压缩库。而这个库在这里解释的话就太复杂了。所以，我在这里想解释一种相对简单的夺得压缩算法。

　　此节因为作者的能力原因，没有完成。

　　加密

　　一个体系对于特务之眼窥视的防护始终是永恒的话题。人们已经尽力传递私人信息给别人了上百年。从古希腊信使步行传送的手写书信到2战时纳粹潜艇的无线电，再到今天网络信誉卡交易。保障别人不能得到你的信息的才能长短常必要的。这种复杂的维护方法叫做加密。虽然我们不知道第一个加密算法是谁发现的，但是我们知道世界上游多的数不过来的加密算法。任何事物，从简单的数据编码到解密算法都是被使用了一次又一次的。这篇文章，当然没有解释，也不冀望解释一个加密算法，但是懂得加密是你接触MPQ工作的必须。

　　我们首先来看一个发布在 Basic Lab Notes上的加密算法： void EncryptBlock(void *lpvBlock, int nBlockLen, char *lpszPassword)

　　{

　　int nPWLen = strlen(lpszPassword), nCount = 0;

　　char *lpsPassBuff = (char *)_alloca(nPWLen);

　　memcpy(lpsPassBuff, lpszPassword, nPWLen);

　　for (int nChar = 0; nCount < nBlockLen; nCount++)

　　

　　char cPW = lpsPassBuff[nCount];

　　lpvBlock[nChar] ^= cPW;

　　lpsPassBuff[nCount] = cPW + 13;

　　nCount = (nCount + 1) % nPWLen;

　　

　　return;

　　}

　　正如展示的哈希代码那样，这段代码也非常的简单，当然也就不能用在需要安全性的实际程序中。即使这段代码看起来很神秘，它做的事件却非常简单。它将整个的输入块加密。异或密码的每一个字节。然后把所得加上13（之所以抉择13是因为13是质数）。这样就可以使代码更加难以确认。在这种情况下，字符串"encryption" (65 6E 63 72 79 70 74 69 6F 6E)在密码"MPQ" (4D 50 51)下将会被加密成为(28 3E 32 28 24 2E 13 03 04 1A)现在，这段代码是对称的。对称意味着加密的密钥和解密的密钥是相同的。实际上，因为异或是一个对称的操作，所以同加密相同的算法可以被用来解密。留神到大局部对称加密算法并非完全对称，所以需要加密和解密的函数不相同。好，现在事情开始变得麻烦了。如果你希望直接的使用MPQ格式，那么你必须知道它的加密和解密算法。而我就来教你如何使用它.MPQ的加密算法是一些其他加密算法有趣的杂交。它创建一个加密表（也用在哈希函数里面），然后用一个文件的加密钥去从加密表中去除某些数字，再把这些数字同加秘数据进行异或。现在这种做事的方法是非常非常奇异的，所以可能一些代码看起来非常的复杂。以下的代码生成一个长度为0x500的加密表。

　　void prepareCryptTable()

　　{

　　unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;

　　for(index1 = 0; index1 < 0x100; index1++)

　　{

　　for(index2 = index1, i = 0; i < 5; i++, index2 += 0x100)

　　temp2);

　　

　　}

　　}

　　你是否有点感觉到暴雪雇佣了一个超级没有人品的微积分教学撰写了这个代码？至少我是这么感到的。还好即便你不能看懂这段代码也没有什么大问题。如果你盼望可能直接使用MPQ，那么你可能会须要这些函数。你没有必要完整看清楚他们。不论怎么样，当加密表初始化当前，我们就可以用下面的函数来解密MPQ数据（不要指望我会向你说明这个代码，由于我也没有看懂）： void DecryptBlock(void *block, long length, unsigned long key)

　　{

　　unsigned long seed = 0xEEEEEEEE, unsigned long ch;

　　unsigned long *castBlock = (unsigned long *)block;

　　// Round to longs

　　length >>= 2;

　　while(length-- > 0)

　　(key >> 0x0B);

　　seed = ch + seed + (seed << 5) + 3;

　　*castBlock++ = ch;

　　

　　}

　　翻译后记：

　　这只是我闲来无事翻译着玩的东西，都没有当真的斟酌翻译的语句，甚至有一些语句我是没有看懂的，或者明明知道这样翻译是不好的但还是写上去了。甚至我都没有兴趣自己从头到尾把这篇文章再看1遍。之所以只翻译道第2章是因为第3，4章分辨讲述Storm和Starcraft Campaign Editor and the MPQ API Library是如何使用的，没有什么翻译的价值。而真正出色的5，6两章作者又没有写完。所以说作者真实 未审不厚道。一下给出英文源出处，希望我的翻译只是抛砖引玉，能激发大家越读英文原版的豪情。很多时候翻译的进程中丧失的信息还是相称严峻的。