之前要用 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