MPQ技术内幕
開始嘗試翻譯一些英文文章，最近正好對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?longHashString(char*lpszString){?
????unsigned?longulHash?=0xf1e2d3c4;
????while(*lpszString?!=0)
????{?
????????ulHash?<<=1;
????????ulHash?+=*lpszString++;?
????}
????returnulHash;?
}?
?以上的代碼展示了一個非常簡單的哈希算法。函數計算了字符竄中的字符個數，在每個字符加入之前把哈希值左移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?longHashString(char*lpszFileName,?unsigned?longdwHashType){?
????unsigned?char*key?=(unsigned?char*)lpszFileName;
????unsigned?longseed1?=0x7FED7FED,?seed2?=0xEEEEEEEE;
????intch;
????while(*key?!=0)
????{?
????????ch?=toupper(*key++);
????????seed1?=cryptTable[(dwHashType?<<8)?+ch]?^(seed1?+seed2);
????????seed2?=ch?+seed1?+seed2?+(seed2?<<5)?+3;?
????}
????returnseed1;?
}?
?
?哈希表
問題：你試圖使用之前例子里面的下標法，但是你的程序需要非常嚴格的速度限制。這時候你就會發現下標法不夠快了。這時候你讓它變得更快的方法只能是不讓它檢查數組中所有的哈希。或者，更好的是只讓字符串同數組中的某個元素比較1次就能判斷出這個字符竄是否存在于這個數組。聽起來太好了以至于不可能對不對？
解決方案：哈希表。哈希表是一種下標為字符串哈希值得數組。我的意思是說，我們為這個哈希表構建一個不同于字符串數組的定長數組（我們把它的元素個數定位1024，2的偶數次冪）。這時候，當你想要知道一個字符串是否在哈希表中時，你得首先計算這個字符串如果在哈希表中，那么它的位置是多少。首先我們計算這個字符串的哈希，然后用哈希模取之前的表長（1024）就得到了位置值。因此，如果你用之前的簡單哈希算法，"arr\units.dat"將被哈希為0x5A858026，得到它得位置值為 0x26 (0x5A858026 模取 0x400 商為 0x16A160余數為0x26）。0x26這個位置的字符串（如果有的話）將被讀出來與目標字符串比較。如果0x26這個字符串與目標字符串不匹配或者0x26的這個字符串不存在，則這個目標字符串不存在于這個數組中。以下的代碼說明了這點：
intGetHashTablePos(char*lpszString,?SOMESTRUCTURE?*lpTable,?intnTableSize){?
intnHash?=HashString(lpszString),?nHashPos?=nHash?%nTableSize;
if(lpTable[nHashPos].bExists?&&!strcmp(lpTable[nHashPos].pString,?lpszString))?
returnnHashPos;?
else
return-1;?//Error?value?
}?
可是現在，這個算法有一個巨大的缺陷。你認為當沖突（2個字符竄哈希到同樣一個值）發生的時候會怎么樣？顯然它們不能占用哈希表中的同一個元素。一般，這種缺陷通過使哈希表中的每一個元素成為一個鏈表來實現。每個鏈標中將存放哈希值相同的字符竄。MPQ使用文件名哈希表來跟蹤內部的所有文件。但是這個表的格式與正常的哈希表有一些不同。首先，它沒有使用哈希作為下標，把實際的文件名存儲在表中用于驗證，實際上它根本就沒有存儲文件名。而是使用了3種不同的哈希：一個用于哈希表的下標，兩個用于驗證。這兩個驗證哈希替代了實際文件名。當然了，這樣仍然會出現2個不同的文件名哈希到3個同樣的哈希。但是這種情況發生的概率平均是1:18889465931478580854784，這個概率對于任何人來說應該都是足夠小的咯。MPQ哈希表不同用通常的鏈表沖突解決法，當沖突發生時，元素將被下移到下一個空著的位置。請看下面的代碼，基本就是MPQ定位文件名的方法：
intGetHashTablePos(char*lpszString,?MPQHASHTABLE?*lpTable,?intnTableSize){?
????constintHASH_OFFSET?=0,?HASH_A?=1,?HASH_B?=2;
????intnHash?=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)?
????????????returnnHashPos;?
????????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上的加密算法：
voidEncryptBlock(void*lpvBlock,?intnBlockLen,?char*lpszPassword){?
????intnPWLen?=strlen(lpszPassword),?nCount?=0;
????char*lpsPassBuff?=(char*)_alloca(nPWLen);
????memcpy(lpsPassBuff,?lpszPassword,?nPWLen);
????for(intnChar?=0;?nCount?<nBlockLen;?nCount++)
????{?
????????charcPW?=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的加密表。
?
voidprepareCryptTable(){?
????unsigned?longseed?=0x00100001,?index1?=0,?index2?=0,?i;
????for(index1?=0;?index1?<0x100;?index1++)
????{?
????????for(index2?=index1,?i?=0;?i?<5;?i++,?index2?+=0x100)
????????{?
????????????unsigned?longtemp1,?temp2;
????????????seed?=(seed?*125+3)?%0x2AAAAB;
????????????temp1?=(seed?&0xFFFF)?<<0x10;
????????????seed?=(seed?*125+3)?%0x2AAAAB;
????????????temp2?=(seed?&0xFFFF);
????????????cryptTable[index2]?=(temp1?|temp2);?
????????}?
????}?
}
你是否有點感覺到暴雪雇傭了一個超級沒有人品的微積分教授撰寫了這個代碼？至少我是這么感覺的。還好即使你不能看懂這段代碼也沒有什么大問題。如果你希望能夠直接使用MPQ，那么你可能會需要這些函數。你沒有必要完全看明白他們。不管怎么樣，當加密表初始化以后，我們就可以用下面的函數來解密MPQ數據（不要指望我會向你解釋這個代碼，因為我也沒有看懂）：
voidDecryptBlock(void*block,?longlength,?unsigned?longkey){?
????unsigned?longseed?=0xEEEEEEEE,?unsigned?longch;
????unsigned?long*castBlock?=(unsigned?long*)block;
????//Round?to?longs
length?>>=2;
????while(length-->0)
????{?
????????seed?+=stormBuffer[0x400+(key?&0xFF)];
????????ch?=*castBlock?^(key?+seed);
????????key?=((~key?<<0x15)?+0x11111111)?|(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兩章作者又沒有寫完。所以說作者實在不厚道。一下給出英文源出處，希望我的翻譯只是拋磚引玉，能激發大家越讀英文原版的激情。很多時候翻譯的過程中損失的信息還是相當嚴重的。
轉載于:https://www.cnblogs.com/kex1n/archive/2011/12/30/2307812.html
總結
- 上一篇： 计算机组成原理1（现代计算机细分组成框图
- 下一篇： php smarty 语法,5. Sma