MPQ 檔格式 (未完成)

[edwar (海邊的野孩子)]

之前要用 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 用的是一樣的.


--
結束了 ^^

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.138.156.138
推 Forcast:◆ 這一篇文章值 230 銀
推 jimmylee7775:推
推 waterfantasy:我的眼睛花了
推 red0210:眼睛都花了
推 MeauD2:這篇  很難>"<  應屬於大內高手流
推 micado:我只看到一推程式設定碼
推 ericinttu:雖然我看不懂,但真是高手才辦得到  Orz
推 GGL:@@"
推 pocky0511:第一行就看不懂 第二頁就按END
推 micado:不過我還是想說"帥ㄚ~老皮!"
→ edwar:大量中英夾雜, 很難排版 >"<  我自己留的每段分開, 較不傷眼
推 omarandy:完全...不懂ˊˋ
推 ScorAlan:大師讓小弟拜一下Orz
推 Joybo:我走到了Programming版了嗎
推 Joybo:沒學過perl，很好奇他怎知道Encode / Decode的方式，組語？
→ edwar:perl 的部分是留著我自己以後要看的 XD
→ edwar:Encode/Decode 也許是 trace 出來的?
→ edwar:樓上有人看不懂沒關係, 只要有人能看懂再寫好用的工具程式
→ edwar:就好了 XD