魔兽改图MPQ技术内幕

邪恶叔

MPQ，也称MoPaQ，是Mike O'Brien发明的一种压缩文件格式。
在1996作为，MPQ应用在Diablo（暗黑破坏神）游戏中。
然而它的版权属于 Blizzard 的父公司 Havas Interactive，并且在Mike O'Brien离开暴雪后继续使用。 正是MPQs由于在Diablo（暗黑破坏神）中的出色表现，使其继续应用在Starcraft（星际争霸）, Warcraft 2（魔兽争霸2）, Diablo 2（暗黑破坏神2）, Lords of Magic（魔法大帝）中。

第二章 关于MPQ的介绍


MPQ内部包含了许多文件，包括坐标算法、声音、动画、字符串、数字数据和故事情节信息。
明显地，MPQ的潜力很大。要想利用MPQ，那么您就需要了解它。

在有MPQ格式之前，一直使用的是WAR格式，在Warcraft 2，甚至在Warcraft1中存放游戏数据。然而WAR格式是简单的，不精制的，是由缺乏经验的程序员所编写的文件格式(相信我，我知道)。文件在档案中仅使用参考序数和是否被压缩做为唯一可选择调用的方法。
尽管如此它仍然完成了它的任务。它提供了压缩格式下的文件调用。但是，很快缺点开始出现。调用时使用参考序数，意味着一长传文件接口的名单必须被保留和被咨询，当程序员需要使用其中一个文件，那么则需要级长的时间，工作变得越来越繁琐。
当时这些问题并没有那么严重，所以有人坚持使用WAR格式，但是一切在使用Battle.net（网络对战）后，问题变得不能接受。


MPQ的特点
如被提及以前，MPQ格式一直被用做修正WAR的设计缺陷。但是现在他们也想增加一些全新的特点到MPQ。在暴雪的游戏中，MPQ格式的特点总结为以下几点：

Security. 安全

暴雪一定不希望在游戏中玩家可以修改数据。或许他们提早知道MPQ格式可以为Starcraft使用。 不管怎样，安全是最重要的，由此他们显然做了级大的努力去维护游戏的安全性。

Efficiency. 效率

MPQs要求执行时先简单预先输入的各种各样的任务数据然后实时放出。对于预先输入数据，时间并不重要。 但是实时放出就是另一件事了，其中的数据必须快速地被解压使用。

Multilinguality.多语言的计算机处理

在最开始的时候，暴雪就计划发布其游戏在全球游戏市场，因此他们尽可能的做到多语言。 在创新时，他们决定设计多语种能写入MPQ格式。
。
Expandability.扩展

显然的，在游戏中需要使用独立的数据。太大的数据不仅是效率低并且减慢游戏速度，如果补丁修改了，也是很麻烦的。暴雪明白这个道理，因而MPQ格式的要求就是有能力完全，高效率的，从多个档案数据中调用需要的数据。


什么是strom
相比在程序模块中复制函数，多数程序员喜欢把相同代码放到shared libraries（共享程序库）里。shared libraries是包含了任意程序功能的函数模块。不仅能避免多余，并且能缩小程序大小。
正因为如此，暴雪使用一个称为Storm的共享程序库(PC机上为Storm.dll，MAC机为Storm.bin)。
所有现代的暴雪游戏中都使用strom存放重要功能，比如读取MPQ，Battle.net和一些图形化例程。
当暴雪要发布新版本的游戏，只需要增加功能到strom，无需改变原有功能。 这意味着旧版本的游戏只用升级新版本strom就可以了，这就是我们俗称的安装补丁。
就像所有共享程序库，任何想使用它的程序都可以访问到它的函数。这就是为什么strom只包含MPQ读取功能。


什么是 MPQ API Library DLL

虽然 Storm 没有包含任何编写MPQ的功能。
但是 StarEdit 包含，因为 SCM/SCX 文件也是 MoPaQ文件。
但是这些函数被加密了，所以只有知识渊博的黑客们才可以使用。
对于Blizzard 来说不幸的是，有一个这样的黑客，他的名字是 Andrey Lelikov(aka Lelik)。
他发现了一种访问这些宝贵的函数的途径，并把这个复杂的过程封装在
LMPQAPI.DLL（Lelik's MPQ API Library DLL）文件中。该文件自动破解
StarEdit，将这些函数展示在所有的程序员面前。

第三章 MPQ的基本原理

通过整个计算机发展史来看，绝大多数的进步都是在求解问题中发生的。
那么在这一章中，我们将采取看看一些涉及到MPQ的问题及其解决办法。

HASH (散列或哈希)

问题：你有一个非常大的字符串数组，和一个字符串
怎么知道字符串是否在数组中？

你可能会开始在数组中与其他字符串比较每个字符串，但是，当进行应用后，你会发现，这种方法在实际使用时是特别慢的。在此之前，你又怎能在没有与其他字符串比较的情况下，确定这个字符串是否存在？

解决方法：hash
hash是规模较小的数据类型（例如数字）能指向其他较大的数据类型（通常是字符串） 。在这种情况下，您可以在数组中先存储hash。然后再计算其他字符串的hash，并比较它存储的hash。通过字符串比较，如果hash在数组相匹配的新的hash，就可以核实存在。这就是所谓的索引查找，可以加快对于不同大小的数组和平均长度的字符串的搜索速度约100倍。

unsigned long HashString(char *lpszString) {
	unsigned long ulHash = 0xf1e2d3c4; while (*lpszString != 0) {
		ulHash <<= 1; ulHash += *lpszString++;
	} return ulHash;
} 上面的代码，体现了一个很简单的散列算法。 功能是在每个字符添加前，把哈希值向左移动1bit，并总计字符串中的字符。 使用这种算法，字符串“arr\ units.dat ”将散列为0x5a858026，“unit\neutral\ acritter.grp ”将散列为0x694cd020 。 无可否认，这是一个很简单的算法，但是不是非常实用。因为在较低的数字范围内会产生一个相对可预见的输出，以及出现大量的冲突。当多于一个字符串散列为相同值就会出现冲突。 MPQ格式使用一个非常复杂的散列算法（如下所示），产生完全不可预测的哈希值，这个算法十分有效，这就是所谓的单向散列。 就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。从预映射，能够简单迅速的得到散列值，而在计算上不可能构造一个预映射，使其散列结果等于某个特定的散列值。 即构造相应的任意长度明文=固定长度散列值-1（固定长度散列值）不可行。 故此使用特别算法，文件名“arr\ units.dat ”将散列为0xf4e6c69d ，和“unit\neutral\ acritter.grp ”将散列为0xa26067f3 。 [table]
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;
}

HASH TABLES(散列表或哈希表)

问题：您尝试在前面的示例中使用相同索引，您的程序一定会有中断现象发生，而且不够快。
您能做的只有让程序不去查询数组中的所有散列值。或者 您可以只做一次对比就可以得出在列表 中是否存在字符串。
听起来不错，真的么？
骗你的啦！！！

解决方案：a hash table

哈希表是数组中的一种特殊类型，也就是设定指定字符串的偏移量为那个字符串的散列值。
我的意思是，假如您设置一个字符串列表，使用一个单独的固定大小的数组作为哈希表。
您想查看新的字符串是否在前面的哈希表里。
那么您需要先计算要查看字符串的散列值，然后以哈希表大小的散列值为模求余数。
因此，如果您使用上面列出的简单散列算法，"arr\units.dat"将散列为0x5A858026，使其偏移量
0x26(0x5A858026 divided by 0x400 is 0x16A160, with a remainder of 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
}

现在在这方面的解释有一个明显的缺陷。您认为发生冲突时（两个不同的字符串哈希以同等价值的） ？显然，他们不能在哈希表占用相同的接口。通常，解决的方法是在哈希表每个接口作为一个指针到一个链表，然后将链表里所有接口的散列值设置相同。
MPQ使用一个关于文件名称的哈希表记录内部文件，但是这个哈希表的格式与普通哈希表有所不同。
首先，MPQ根本不保存文件名，用三个散列值代替保存散列值的偏移量和为了核查文件名保存真实的文件名。
而是使用三个不同哈希值：一个做为哈希表的偏移量，两个是做为核查。
两个做为核查的哈希值被用来代替真实的文件名称。当然，也有可能两个不同文件名称的散列值相同，
不过这种情况发生的可能性为平均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个散列值（一个冲突和两个检查）并将其存储在变量。
2.移动冲突散列值的接口
3.接口未使用的吗？如果是的话，停止搜寻，并传回'文件没有被发现' 。
4.两个检查是否匹配检查我们正在寻找文件的散列值呢？如果是的话，停止搜寻，并传回目前的接口。
5.如果在最后一个接口，移动到列表中的下一个接口，（wrapping around to the beginning ？？）。
6.刚移动的借口是否和冲突时的散列值相同（是否检查了整个哈希表？ ） ？如果是的话，停止搜寻，并传回'文件没有被发现' 。
7.回到第3步。
如果您很仔细的话，您可能会从我的解释和示例代码注意到，是因为mpq的哈希表已保留所有文件接口在MPQ 。那么您认为每一个哈希表项如何得到填补？答案可能出乎您的意料却显而易见：您不能继续添加文件。几个人都问我为什么有一个上限（所谓的档案限制），在一个MPQ中可以有多少档案， ，是否有任何的方式解决这个限制。那么，您已经有了第一个问题的答案。至于第二项;没有，您不能绕开该文件的限制。对这个问题，哈希表，甚至不能调整大小，除非您重新改造MPQ。在哈希表每个接口因为重新设置大小不同位置可能会改变。而且导致无法获得新的地址，因为地址是文件名的散列值，并且我们还可能不知道档案名称。


Compression 压缩
问题：您有一个很大的程序（比如说， 50 megs ） ，您要分发在互联网上。但50 megs是一个非常大的下载量，而且别人未必有兴趣等待四个半小时去下载这个程序。

解决方法：压缩。
压缩是一门艺术。是在更小的内存中重新放置等量的数据。
有数以百计不同的压缩算法，使用不同的方式。
MPQ实际使用的算法是the Data Compression Library, licensed from PKWare (one of the leaders in applied compression)，在此解释太过于复杂。相反，我会尝试解释一个更简单的压缩算法的例子。

本章节并不完全 ，因为作者没写完

toubing1

不明所以