MPQ 檔格式 (未完成) - 暗黑

之前要用 mpq2k 看某些 mpq 檔裡的東西, 突然發現 mpq2k 幾乎看不到什麼檔
案了, 尤其在 d2exp 1.10 以後, patch_d2.mpq 讓它找只能找到一個檔案, 因
為 mpq2k 的作者已經不再做任何維護的動作了, 只能自己手動來, 所以才有想
了解這個檔案格式的動力, 想看看能否突破 mpq2k 現有的限制.
(之前有想看, 但就是懶 (-,-))))).

目前針對 mpq2k 的一些嚐試已經告一段落, 想做的事也差不多了, 繼續研究的
動力也沒了, 所以把目前的東西整理一下, 希望對想研究的人有一些幫助.
* 這篇文章最有用的應該是參考資料, 其他都是廢話 XD

這篇文章可自由轉載, 但請保留出處(ptt.cc diablo 板)及作者(edwar).


參考資料
--------

Inside MoPaQ
http://www.campaigncreations.org/starcraft/inside_mopaq/
這是 mpq2k 作者所寫的網頁, 但是似乎沒有再更新了.
(聽說作者不希望有人煩他 mpq2k 相關的事)


從 Inside MoPaQ 提供的 Stormless MPQ Editor 連結拿到的 MpqView
原始碼也很有用. 網頁:
http://www.angelfire.com/sc/mpq/


MPQ 檔的一些特性
----------------
* Blizzard 所使用的一種檔案格式, 存放一些遊戲的資訊檔, 如聲音、動畫
* 用於將多個檔案放進一個檔案裡
* 給一個檔名, 可以檢查一個 MPQ 檔有沒有那個檔, 但是無演算法可從一個
MPQ 檔逆推求得該 MPQ 檔含有那些檔案.
- MPQ 使用三個不同參數得到的 32bit hash 來取代檔名這項資訊, 如果
有碰撞產生就認了, 所以無法逆推.
* 檔名不分大小寫


檔頭
----
offset |length | content
(hex) | |
---------|-------|-------------------
00000000 | 4 | 4D 50 51 1A ('MPQ'?)
00000004 | 4 | 20 00 00 00
00000008 | 4 | mpq file size ?
0000000C | 4 | unknown (00 00 03 00)
00000010 | 4 | htbl offset: hash table 位置
00000014 | 4 | btbl offset: block table 位置
00000018 | 4 | htbl_len: hash table 大小 / 能容納的檔案數
0000001C | 4 | btbl_len: 現有檔案數

依 MpqView source code 來看, 4D 50 51 1A 字串只需位於 4-word aligned
開始的地方, 開檔案後要先找到這個字串, 之後的其他資訊都是相對於此字串
的相對位置.



hash table (htbl)
-----------------
hash table 每筆資料含有四個 32bit 的值
offset |length | content
(hex) | |
---------|-------|-------------------
00000000 | 4 | hash2
00000004 | 4 | hash3
00000008 | 4 | unknown (好像都是 00 00 00 00 或 FF FF FF FF)
0000000C | 4 | 位於 block table 的那一筆 entry, 從 0 開始算

共有 htbl_len 筆記錄, 如果該筆記錄未被使用, 四個欄位似乎都會是
FF FF FF FF. 能容納多少筆記錄在該 MPQ 檔建立之初就已決定, 只要開始加
檔案就無法變動了, 這也是該檔能夠容納的檔案數.

若是實際上用 hex editor 去看 MPQ 檔, hash table 應該是一堆看起來雜亂
無章的資料, 需要經過 decrypt 的過程轉成正常的樣子. 參考 encrypt /
decrypt 部份的說明.

由檔名得到 block entry
======================
由檔名可以求得三個 32bit hash (參考 hash function, 該處提到的 $scrc1
/ $scrc2 / $scrc3 即為所求, 分別當做這裡的 hash1, hash2, hash3), 再
由這三個值找出位於 hash table 何處:
1. hash1 除以 htbl_len 的餘數: 此數告訴你要從 hash table 的那一筆記
錄開始找. (從零開始算)
2. 檢查這筆記錄是否已被使用, 可能是看 offset 0008h 的數值:
(a) 00000000h 表示有使用, 進行步驟 3.
(b) FFFFFFFFh 則是未被使用, 跳至步驟 4.
3. 檢查 hash2 和 hash3 是否均符合:
(a) 是, 均符合: 找到檔案了, offset 000Ch 為該檔的 block entry.
(b) 否: 還未找到, 跳到步驟 4
4. 看看是否已經整個 hash table 的每筆記錄都找過卻找不到, 若是, 該檔
不存在 -> 跳出.
5. 繼續下一筆記錄, 跳至步驟 2. 如果是在 hash table 最後一筆, 下一筆
記錄則是第 0 筆記錄.

由於 mpq 處理 hash collision(碰撞)的方式是繼續往後找, 直至有空的位置
可以存放就儲存. 如果碰撞後又有做 delete(刪除)的動作, 可能會產生空洞.
所以步驟 2-(b) 發現該位置未使用也只是跳過去而已.

接下來
======
* 如果只是要知道該檔名存在與否, 那以上的[由檔名得到 block entry]應
該就可以了.
* 還要再得到那個檔案的內容的話, 由此 block entry, 再到 block table
裡找相關的檔案儲存資訊.



block table (btbl)
------------------
block table 每筆資料含有四個 32bit 的值
offset |length | content
(hex) | |
---------|-------|-------------------
00000000 | 4 | 存放的位置, 相對於檔頭開始(4D 50 51 1A)
00000004 | 4 | 壓縮後的檔案大小; 若未壓縮, 則同未壓縮的檔案大小
00000008 | 4 | 未壓縮的檔案大小
0000000C | 4 | block 屬性, 如有無壓縮、有無編碼等等

共有 btbl_len 筆記錄, 從 0 開始算.

若用 hex editor 去看 MPQ 檔, block table 應該像 hash table 一樣, 看起
來像一堆雜亂無章的資料, 需要經過 decrypt 的過程轉成正常的樣子. 參考
encrypt / decrypt 部份的說明.

屬性
====
目前找到的 block 屬性值有:
------
00000000h
80000000h - 未壓縮, 未編碼
80000100h - from Diablo I MPQ, DCL 壓縮
80000200h - Starcraft MPQ (or Diablo II), 要另外讀壓縮方式
80010200h
80030000h
80030200h
======

bit value | attribute
(hex) |
----------|----------------------------------------
00000000 | 不知, 也許無任何特性
00000100 | PACK, Diablo I MPQ, always compressed with DCL
00000200 | PACK, Starcraft MPQ (or Diablo II), 某處會記錄壓縮方式
00010000 | coded (是指 encrypted?)
00020000 | coded (是指 encrypted?)
80000000 | 不知

(各屬性值意義在 MpqView 的原始檔有更詳盡的解釋)



hash function
-------------
預備知識: hash function 概念

MPQ 檔使用一個不錯的單向 hash function 將檔名轉成三個 32bit hash, 此
hash function 也可以用不同的參數就改變輸出的結果, 檔案轉換後的三個 hash
就是三個相異參數得到的.

底下使用 perl 程式碼呈現如何產生 hash:
(C 的程式碼請參考 MpqView 原始檔)

--- get hash -------------
my @massive_base;
sub BuildBaseMassive {
my $s1;
my ($i, $j);
my $rem;
$rem = 0x100001;
for $i (0 .. 0x100-1) {
for $j (0 .. 4) {
$rem = ($rem*125+3) % 0x002AAAAB;
$s1 = ($rem & 0xFFFF) << 0x10;
$rem = ($rem*125+3) % 0x002AAAAB;
$s1 |= ($rem & 0xFFFF);
$massive_base[$i+0x100*$j] = $s1;
}
}
}

sub Crc ($$$) {
my $string = shift;
my $refMassive_base = shift;
my $massive_base_offset = shift;

my $byte;
my $crc = 0x7fed7fed;
my $s1 = 0xEEEEEEEE;

foreach (split(//, $string)) {
$byte = ord;
last if $byte == 0;
if ($byte > 0x60 && $byte < 0x7B) {
$byte -= 0x20;
}
$crc = $$refMassive_base[$massive_base_offset+$byte]^($crc+$s1);
$crc &= 0xFFFFFFFF;
$s1 += $crc+($s1<<5)+$byte+3;
$s1 &= 0xFFFFFFFF;
}
return $crc;
}

&BuildBaseMassive;
my $filename = 'This\is\a\test\file';
my ($scrc1, $scrc2, $scrc3);
$scrc1 = &Crc($filename, \@massive_base, 0);
$scrc2 = &Crc($filename, \@massive_base, 0x100);
$scrc3 = &Crc($filename, \@massive_base, 0x200);
=== get hash =============

$scrc1, $scrc2, $scrc3 就是由檔名轉換得到的三個 32bit hash, 分別由調整參數
為 0, 0x100, 0x200 得到.



encryption/decryption: hash & block table
-----------------------------------------

如果直接用 hex editors 去看 hash table 和 block table, 看到的資料應該是
很雜亂的, 這兩個 table 在寫進來 MPQ 檔之前, 已經被 Encrypt 過了, 所以想
要看到正確的資料, 就要先 Decrypt.

以下是 Encrypt / Decrypt 的 perl code:
(此處 sub Decode 是 Decrypt 程式; sub Encode 是 Encrypt 程式)
(C 程式碼 Decrypt 部分同樣參考 MpqView 原始碼)

--- Encrypt / Decrypt -----------
sub Decode ($$$$) {
my $refDataIn = shift;
my $refMassive_base = shift;
my $crc = shift;
my $lenght = shift;

my ($i, $dec);
my $s1 = 0xEEEEEEEE;
for $i (0 .. $lenght-1) {
$s1 += $$refMassive_base[0x400+($crc & 0xFF)];
$s1 &= 0xFFFFFFFF;
$dec = $$refDataIn[$i]^($s1+$crc);
$dec &= 0xFFFFFFFF;
$s1 += $dec+($s1<<5)+3;
$s1 &= 0xFFFFFFFF;
$$refDataIn[$i] = $dec;
$crc = ($crc>>0x0b) | ((0x11111111+(($crc^0x7FF)<<0x15)) &
0xFFFFFFFF);
}
}

sub Encode ($$$$) {
my $refDataIn = shift;
my $refMassive_base = shift;
my $crc = shift;
my $lenght = shift;

my ($i, $dec);
my $s1 = 0xEEEEEEEE;
for $i (0 .. $lenght-1) {
$s1 += $$refMassive_base[0x400+($crc & 0xFF)];
$s1 &= 0xFFFFFFFF;
$dec = $$refDataIn[$i];
$$refDataIn[$i] = ($dec^($s1+$crc)) & 0xFFFFFFFF;
$s1 += $dec+($s1<<5)+3;
$s1 &= 0xFFFFFFFF;
$crc = ($crc>>0x0b) | ((0x11111111+(($crc^0x7FF)<<0x15)) &
0xFFFFFFFF);
}
}

my $name_htable = "(hash table)";
my $name_btable = "(block table)";
seek(MPQ, $offset_mpq+$offset_htbl, 0);
read(MPQ, $tmp, 4*4*$lenght_htbl); @hash_table = unpack("L*", $tmp);
seek(MPQ, $offset_mpq+$offset_btbl, 0);
read(MPQ, $tmp, 4*4*$lenght_btbl); @block_table = unpack("L*", $tmp);

$tmp = &Crc($name_htable, \@massive_base, 0x300);
&Decode(\@hash_table, \@massive_base, $tmp, 4*$lenght_htbl);
$tmp = &Crc($name_btable, \@massive_base, 0x300);
&Decode(\@block_table, \@massive_base, $tmp, 4*$lenght_btbl);

# my @tblock_table = @block_table;
# $tmp = &Crc($name_btable, \@massive_base, 0x300);
# &Encode(\@tblock_table, \@massive_base, $tmp, 4*$lenght_btbl);
=== Encrypt / Decrypt ===========

@massive_base 和 &Crc(...) 跟 hash function 用的是一樣的.


--
結束了 ^^

--