Archivy MPQ

Formát souborů MPQ

Formát MoPaQ na Wiki

Justin Olbrantz (Quantam) a Jean-Francois Roy (BahamutZERO) publikovali detailní popis formátu MPQ. Můžete jej najít na Devklog.com.

Obecné rozvržení souboru MPQ

Obecná struktura souboru MPQ je následující:

Data před archivem MPQ
(nepovinné)
Archiv MPQ nemusí začínat na začátku souboru. Např. instalační balíky nebo aktualizace obvykle obsahují archiv MPQ připojený na konci instalátoru, což je soubor EXE. Pokud MPQ nezačíná na offsetu 0, musí začínat na offsetu dělitelném 512ti (0x200).
MPQ User Data
(nepovinné)
V knihovně StormLib je hlavička MPQ User Data definována strukturou TMPQUserData, popsanou níže. MPQ User Data jsou nepovinná, a jsou běžně použita v mapách pro Starcraft II. Pokud je přítomna hlavička MPQ User Data, pak obsahuje offset, odkud je třeba pokračovat v hledání hlavičky MPQ.
Hlavička MPQ
(povinná)
MPQ Header je v knihovně StormLib popsán strukturou TMPQHeader. Velikost hlavičky MPQ závisí na verzi formátu MPQ:
  • Pro formát MPQ verze 1, velikost hlavičky MPQ je 32 (0x20) bytů.
  • Pro formát MPQ verze 2, velikost hlavičky MPQ je 44 (0x2C) bytů.
  • Pro formát MPQ verze 3, velikost hlavičky MPQ je musí výt větší nebo roven 44 (0x2C) bytů.
  • Pro formát MPQ verze 4, velikost hlavičky MPQ je 208 (0xD0) bytů.
MPQ Header je jediná povinná část souboru MPQ. Byly pozorovány prázdné archivy MPQ o velikosti 44 bytů, které obsahovaly pouze hlavičku MPQ.
Soubory v archivu MPQ
(nepovinné)
Soubory jsou v archivech MPQ obvykle uloženy za hlavičkou. Není to povinné ale jediná známá vyjímka jsou uložené hry pro Diablo I, kde těsně za hlavičkou následuje hash a block tabulka.
Speciální soubory
(nepovinné)
Speciální soubory zahrnují (listfile), (attributes), (signature) a (user data).
Tabulka HET
(nepovinná)
Tato tabulka se objevila v archivech verze 3. Jde o novou verzi hash tabulky.
Tabulka BET
(nepovinná)
Tato tabulka se objevila v archivech verze 3. Jde o novou verzi block tabulky.
Hash tabulka
(nepovinná)
Hash tabulka je základní tabulkou pro vyhledávání souborů v MPQ podle jména. Položka tabulky je v knihovně StormLib popsána strukturou TMPQHash. Počínaje verzí 3 formátu MPQ, hash tabulka je nepovinná a může být plně nahrazena tabulkou HET.
Block Table
(nepovinná)
Block tabulka obsahuje záznam pro každý soubor uložený v MPQ. Záznam obsahuje pozici dat souboru v MPQ, velikost souboru, komprimovanou velikost, a vlastnosti souboru. Položka tabulky je v knihovně StormLib popsána strukturou TMPQBlock. Počínaje hrou Starcraft II, block tabulka musí následovat za hash tabulkou. Od MPQ formátu 3 je block tabulka nepovinná a může být plně nahrazena tabulkou BET.
Tabulka Hi-Block
(nepovinná)
Počínaje formátem 2, archiv může obsahovat tabulku hi-block. Je to pole 16-ti bitových hodnot, obsahující horní část offsetu dat v MPQ. Pokud je tabulka hi-block přítomna, obvykle následuje za block tabulkou.
Silný digitální podpis
(nepovinný)
Pro archivy pro World of Warcraft, digitální podpis následuje za koncem archivu MPQ.

Hlavička MPQ a uživatelská data v MPQ

Velká většina souborových formátů začíná nějakou hlavičkou, formát MPQ není výjimkou. Velikost hlavičky souboru MPQ je nejméně 32 bytů (0x20). Při otevírání archivů MPQ se hledá hlavička nebo posunutí na offsetech dělitelných 512ti (0x200), dokud není nalezena hlavička nebo dokud není dosaženo konce souboru. Tento způsob hledání umožňuje kombinovat archivy MPQ se spustitelnými soubory, např. u instalátoru pro Starcraft (Install.exe). Na prohledávaných offsetech se hledá 32-bitová signatura, znamenající buďto hlavičku nebo uživatelská data:

Obě struktury, zapsány ve formátu C/C++, vypadají následovně:

// Uživatelská data MPQ
struct TMPQUserData
{
    // Signatura - ID_MPQ_USERDATA ('MPQ\x1B')
    DWORD dwID;

    // Maximální velikost dat
    DWORD cbUserDataSize;

    // Offset havičky MPQ, relativní od začátku této hlavičky
    DWORD dwHeaderOffs;

    // Pravděpodobně velikost hlavičky (Mapy pro Starcraft II)
    DWORD cbUserDataHeader;
};
// Hlavička souboru MPQ
struct TMPQHeader
{
    // // Identifikátor struktury (ID_MPQ_HEADER, 'MPQ\x1A')
    DWORD dwID;                         

    // Velikost hlavičky
    DWORD dwHeaderSize;                   

    // Velikost archivu MPQ
    // Tato proměnná je ve formátu V2 zastaralá, a velikost archivu se počítá jako rozdíl pozice
    // hlavičky MPQ a hašovací tabulky, block tabulky, nebo rozšířené block (podle toho, která ze tří
    // tabulek je na konci archivu).
    DWORD dwArchiveSize;

    // 0 = Formát 1
    // 1 = Formát 2 (The Burning Crusade a novější)
    // 2 = Formát 3 (WoW - Cataclysm beta a novější)
    // 3 = Formát 4 (WoW - Cataclysm)
    USHORT wFormatVersion;

    // Mocnina dvou, specifikující počet 512-bytových sektorů v každém bloku souboru.
    // Velikost bloku souboru je 512 * 2^wBlockSize.
    USHORT wBlockSize;

    // Ofset začátku hašovací tabulky, relativní k offsetu hlavičky MPQ
    DWORD dwHashTablePos;
    
    // Ofset začátku block tabulky, relativní k offsetu hlavičky MPQ
    DWORD dwBlockTablePos;
    
    // Počer položek v hašovací tabulce. Musí být mocnina dvou, a musí být v menší než 2^16
    // for formát V1 a menší než 2^20 pro formát V2.
    DWORD dwHashTableSize;
    
    // Počet položek v block tabulce
    DWORD dwBlockTableSize;

    //-- MPQ HEADER v 2 -------------------------------------------

    // Ofset tabulky hi-block, relativní k offsetu hlavičky MPQ.
    ULONGLONG HiBlockTablePos64;

    // Horních 16 bitů offsetu hašovací tabulky pro archive o velikosti > 4 GB.
    USHORT wHashTablePosHi;

    // Horních 16 bitů offsetu block tabulky pro archivy o velikosti > 4 GB.
    USHORT wBlockTablePosHi;

    //-- MPQ HEADER v 3 -------------------------------------------

    // 64-bitová hodnota velikosti archivu
    ULONGLONG ArchiveSize64;

    // 64-bitová pozice tabulky BET
    ULONGLONG BetTablePos64;

    // 64-bitová pozice tabulky HET
    ULONGLONG HetTablePos64;

    //-- MPQ HEADER v 4 -------------------------------------------

    // Komprimovaná velikost hašovací tabulky
    ULONGLONG HashTableSize64;

    // Komprimovaná velikost block tabulky
    ULONGLONG BlockTableSize64;

    // Komprimovaná velikost tabulky hi-block
    ULONGLONG HiBlockTableSize64;

    // Komprimovaná velikost tabulky HET
    ULONGLONG HetTableSize64;

    // Komprimovaná velikost tabulky BET
    ULONGLONG BetTableSize64;

    // Size of raw data chunk to calculate MD5.
    // MD5 of each data chunk follows the raw file data.
    DWORD dwRawChunkSize;                                 

    // Pole hodnot MD5
    unsigned char MD5_BlockTable[MD5_DIGEST_SIZE];      // MD5 zašifrované block tabulky
    unsigned char MD5_HashTable[MD5_DIGEST_SIZE];       // MD5 zašifrované hašovací tabulky
    unsigned char MD5_HiBlockTable[MD5_DIGEST_SIZE];    // MD5 tabulky hi-block
    unsigned char MD5_BetTable[MD5_DIGEST_SIZE];        // MD5 zašifrované BET tabulky
    unsigned char MD5_HetTable[MD5_DIGEST_SIZE];        // MD5 zašifrované HET tabulky
    unsigned char MD5_MpqHeader[MD5_DIGEST_SIZE];       // MD5 hlavičky MPQ, od začátku po hodnotu MD5_HetTable (včetně)

};

Tabulka HET

Počínaje formátem 3 (poprvé pozorován během beta testování World of Warcraft - Cataclysm), MPQ může obsahovat tabulku HET. Tato tabulka je přítomna, pokud je hodnota HetTablePos64 v hlavičce MPQ nenulová. Tato tabulka může plně nahradit hash tabulku. V závislosti na celkové velikosti MPQ, dvojice tabulek HET&BET může být efektivnější než dvojice Hash&Block. Tabulka HET může být šifrovaná a také komprimovaná.

Struktura tabulky HET, uložená v archivu MPQ je následující:

    // Společná část pro tabulku HET a BET
    DWORD dwSignature;                      // 'HET\x1A'
    DWORD dwVersion;                        // Verze. Zatím je vždy nastavena na 1
    DWORD dwDataSize;                       // Velikost tabulky

    DWORD dwTableSize;                      // Velikost tabulky HET, včetně hlavičky (v bytech)
    DWORD dwMaxFileCount;                   // Max. počet souborů v MPQ
    DWORD dwHashTableSize;                  // Velikost hash tabulky (bytů)
    DWORD dwHashEntrySize;                  // Efektivní velikost položky v poli hash hodnot
    DWORD dwTotalIndexSize;                 // Celková velikost indexu souboru (v bitech)
    DWORD dwIndexSizeExtra;                 // Rezervované bity v indexu souboru
    DWORD dwIndexSize;                      // Efektivní velikost indexu souboru (v bitech)
    DWORD dwBlockTableSize;                 // Velikost tabulky indexů (v bytech)
    
    // Tabulka hash hodnot. Každá položká má 8 bitů.
    BYTE  HetHashTable[dwHashTableSize];
    
    // Pole indexů souborů. Bitová velikost každé položky je brána z dwTotalIndexSize.
    // Počet položek je brán z dwHashTableSize.

Tabulka BET

Počínaje formátem 3, archiv MPQ může obsahovat tabulku BET. Tato tabulka je přítomna, pokud je hodnota BetTablePos64 v hlavičce nenulová. Tabulka BET je následník block tabulky a může ji plně nahradit. Měla by také být efektivnější. Struktura tabulky BET v archivu je následující:

    // Společná část pro tabulku HET a BET
    DWORD dwSignature;                      // 'BET\x1A'
    DWORD dwVersion;                        // Verze. Zatím je vždy nastavena na 1
    DWORD dwDataSize;                       // Velikost tabulky

    DWORD dwTableSize;                      // Velikost celé tabulky BET, vč. hlavičky (v bytech)
    DWORD dwFileCount;                      // Počet souborů v tabulce HET
    DWORD dwUnknown08;                      // Neznámý, nastaven na 0x10
    DWORD dwTableEntrySize;                 // Velkost jedné položky v tabulce souborů (v bitech)
    DWORD dwBitIndex_FilePos;               // Bitový index pozice souboru (v záznamu souboru)
    DWORD dwBitIndex_FileSize;              // Bitový index velikosti souboru (v záznamu souboru)
    DWORD dwBitIndex_CmpSize;               // Bitový index komprimované velikosti (v záznamu souboru)
    DWORD dwBitIndex_FlagIndex;             // Bitový index indexu flagů (v záznamu souboru)
    DWORD dwBitIndex_Unknown;               // Bitový index ??? (v záznamu souboru)
    DWORD dwBitCount_FilePos;               // Počet bitů pozice souboru (v záznamu souboru)
    DWORD dwBitCount_FileSize;              // Počet bitů velikosti souboru (v záznamu souboru)
    DWORD dwBitCount_CmpSize;               // Počet bitů komprimované velikosti (v záznamu souboru)
    DWORD dwBitCount_FlagIndex;             // Počet bitů indexu flagů (v záznamu souboru)
    DWORD dwBitCount_Unknown;               // Počet bitů ??? (v záznamu souboru)
    DWORD dwTotalBetHashSize;               // Velikost hashe v BET tabulce
    DWORD dwBetHashSizeExtra;               // Rezervované bity v tabulce BET
    DWORD dwBetHashSize;                    // Efektivní velikost hashe BET (bitů)
    DWORD dwBetHashArraySize;               // Velikost pole BET hashů, v bytech
    DWORD dwFlagCount;                      // Počet flagů následujících za hlavičkou
    
    // Následuje pole flagů. Každá položka v poli má velikost 32 bitů a má stejný vyxnam jako
    // položka 'dwFlags' v block tabulce.
    DWORD dwFlagsArray[dwFlagCount];
    
    // Tabulka souborů. Velikost položky je brána z dwTableEntrySize.
    // Velikost tabulky je (dwTableEntrySize * dwMaxFileCount), zaokrouhlená nahoru na 8.

    // Pole hashů BET. Velikost tabulky je brána dwMaxFileCount v tabulce HET

Hledání souboru s použitím tabulek HET a BET

Algoritmus hledání souboru v HET a BET tabulce je následující:

  1. Z plného jména souboru se vypočítá 64-bitová hash hodnota, použitím Jenkinsova algoritmu v 2. Písmena jsou převedena na malá, lomítka jsou převedena na obrácená lomítka.
  2. Hash hodnota je ořezána na počet bitů specifikovaný hodnotou dwHashEntrySize a nastavit nejvyšší bit:
    FileNameHash = (HashStringJenkins(szFileName) & AndMask64) | OrMask64;
  3. Hash hodnota je rozdělena na HET hash (horních 8 bitů) a BET hash (všechny zbývající bity).
    HetHash = (BYTE)(FileNameHash >> (dwHashBitSize - 8));
    BetHash = FileNameHash & (AndMask64 >> 0x08);
  4. Zjistit počáteční index jako zbytek po dělení hash hodnoty velikostí hash tabulky:
    StartIndex = (DWORD)(FileNameHash % dwHashTableSize);
  5. Otestovat hodnotu HET hash na aktuální pozici v poli HET hashů
  6. Pokud je nalezena shodná hodnota, zjistit BET index z pole indexů. Tabilka indexů je bitové orientovaná a nemusí být zarovnána na 8 bitů.
  7. S použitím BET indexu získat hodnotu BET hash z tabulky BET.
  8. Pokud jsou obě hodnoty shodné, soubor byl nalezen. V opačném případě pokračovat krokem 5). Postup opakovat dokud není nalezen HET hash o dané hodnotě, nebylo dosaženo počátečního indexů, nebo dokud nebyla nalezena položka s hodnotou 0.

Hash Tabulka

Hash tabulka je použita k hledání souborů v MPQ podle jména. Jméno souboru je přepočítáno na dvě 32-bitové hash hodnoty, které jsou následně použity k hledání v tabulce. Počet položek v hash tabulce musí být mocnina dvou. Každá položka v hash tabulce také obsahuje jazyk souboru a index záznamu v block tabulce. Velikost položky v hash tabulce je 16 bytů, struktura je definována následovně:

// Hash entry. All files in the archive are searched by their hashes.
struct TMPQHash
{
    // The hash of the full file name (part A)
    DWORD dwName1;
    
    // The hash of the full file name (part B)
    DWORD dwName2;
    
    // The language of the file. This is a Windows LANGID data type, and uses the same values.
    // 0 indicates the default language (American English), or that the file is language-neutral.
    USHORT lcLocale;

    // The platform the file is used for. 0 indicates the default platform.
    // No other values have been observed.
    USHORT wPlatform;

    // If the hash table entry is valid, this is the index into the block table of the file.
    // Otherwise, one of the following two values:
    //  - FFFFFFFFh: Hash table entry is empty, and has always been empty.
    //               Terminates searches for a given file.
    //  - FFFFFFFEh: Hash table entry is empty, but was valid at some point (a deleted file).
    //               Does not terminate searches for a given file.
    DWORD dwBlockIndex;
};

Pokud je v MPQ přítomno více jazykových verzí stejného souboru, jejich položky v hash tabulce následují za sebou a liší se pouze hodnotou lcLocale. Jazykové verze jsou ukázány v následující tabulce:

Hodnota Jazyková verze Hodnota Jazyková verze
0Neutrální/Anglická (USA) 0x404Čínská (Tchajwan)
0x405Česká 0x407Německá
0x409Anglická 0x40aŠpanělská
0x40cFrancouzská 0x410Italská
0x411Japonská 0x412Korejská
0x415Polská 0x416Portugalská
0x419Ruská 0x809Anglická (VB)

Tato tabulka je zašifrovaná, není možné ji v archivu rozeznat. Počet položek v této tabulce je uložen v hlavičce MPQ archivu. Podrobnější informace o teorii hashování obsahuje článek s technickými podrobnostmi.

Ve hře World of Warcraft (jeden z neúplných archivů zkušební verze) byla hašovací tabulka zkomprimovaná. Komprimovaná velikost je spočítána jako:

CompressedHashTableSize = (pMpqHeader->dwBlockTablePos - pMpqHeader->dwHashTablePos)

Block Tabulka

Block Tabulka obsahuje informace o velikosti a typu uložení souboru v archivu, a také polohu dat souboru v archivu. Velikost položky této tabulky je 16 bytů s následující strukturou:

// Položka v block tabulce, obsahující informaci o uložení souboru.
struct TMPQBlock
{
    // Ofset začátku uloženého souboru, relativně k začátku archivu
    DWORD dwFilePos;
    
    // Velikost komprimovaného souboru
    DWORD dwCSize;
    
    // Nekomprimovaná velikost souboru
    DWORD dwFSize;                      
    
    // Příznaky uložení souboru v archivu. Více informací viz tabulka.
    DWORD dwFlags;                      
};

Významy proměnné dwFlags:

Jméno příznaku Hodnota Význam
MPQ_FILE_IMPLODE 0x00000100 Soubor je komprimován pomocí PKWARE Data compression library
MPQ_FILE_COMPRESS 0x00000200 Soubor je komprimován s použitím kombinace různých metod
MPQ_FILE_ENCRYPTED 0x00010000 Soubor je zašifrován
MPQ_FILE_FIX_KEY 0x00020000 Dešifrovací klíč pro soubor je pozměněn podle pozice souboru v MPQ archivu
MPQ_FILE_PATCH_FILE 0x00100000 Soubor obsahuje inkrementální aktualizaci existujícího souboru v základním MPQ
MPQ_FILE_SINGLE_UNIT 0x01000000 Namísto uložení souboru v blocích po 0x1000 bytech, soubor je v archivu uložen jako jeden blok.
MPQ_FILE_DELETE_MARKER 0x02000000 Soubor byl smazán. Vyskytuje se v aktializacích (patch), a způsobí že soubory v MPQ s nižší vyhledávací prioritou jsou považovány za smazané. Takový soubor má velikost 0 nebo 1 byte, a jeho jméno je pouze hash.
MPQ_FILE_SECTOR_CRC 0x04000000 Soubor obsahuje checksum pro každý blok. Ignorováno, pokud soubor není komprimován.
MPQ_FILE_EXISTS 0x80000000 Nastaven, pokud soubor existuje. Pokud není nastaven, znamená to, že tato hash položka je prázdná.

Ve hře World of Warcraft (jeden z neúplných archivů zkušební verze) byla block tabulka zkomprimovaná. Komprimovaná velikost je spočítána jako:

CompressedBlockTableSize = (pMpqHeader->dwArchiveSize - pMpqHeader->dwBlockTablePos)

Hledání souboru s použitím tabulek Hash & Block

Hledání souborů v MPQ podle jména probíhá pomocí tohoto algoritmu:

  1. Z plného jména souboru se vypočítají tři hash hodnoty, s použitím proprietálního algoritmu společnosti Blizzard:
    DWORD dwIndex = HashString(szFileName, MPQ_HASH_TABLE_INDEX);
    DWORD dwName1 = HashString(szFileName, MPQ_HASH_NAME_A);
    DWORD dwName2 = HashString(szFileName, MPQ_HASH_NAME_B);
  2. Spočítat počáteční pozici pro hledání v hash tabulce:
    pStartHash = pHashTable + (dwIndex & (dwHashTableSize - 1));
  3. Na aktuální pozici porovnat, zda jsou hodnoty pHash->dwName1 a pHash->dwName2 shodné s druhou a třetí hodnotou vypočítanuo v bodě 1). Pokud nesouhlasí, přejít na další položku v hash tabulce, dokud není nalezena položka, která má hodnotu dwBlockIndex nastavenu na 0xFFFFFFFF.
  4. Pokud jsou shodné, soubor byl nalezen. Hodnota dwBlockIndex obsahuje index fo block tabulky.

Hi-block Tabulka

Od datadisku World of Warcraft - The Burning Crusade, Blizzard rozšířil formát MPQ, aby podporoval MPQ archivy o velikosti větší než 4 GB. Tabulka hi-block obsahuje pole 16-bitových hodnot pozic souborů v archivu MPQ. Tabulka hi-block není šifrovaná.

Uložení souborů v archivu

Každý soubor, který je v archivu uložen, je rozdělen na bloky. Velikost nekomprimovaného bloku udává hlavička MPQ archivu, používá se 4 KB. Pokud je soubor komprimován, bloky jsou uloženy s proměnnou délkou. V takovém případě je na začátku dat souboru tabulka, která obsahuje začátky jednotlivých bloků vztažené relativně k počátku souboru v archivu. Počet položek v tabulce je o 1 větší než počet bloků; nadbytečná položka je nutná pro zjištění velikosti posledního bloku. Velikost jedné položky je 4 byty (32bitová hodnota). Každý blok je zvlášť komprimován a zakódován (pokud jsou v block tabulce nastaveny příslušné bity). Většina souborů v MPQ archivu je kódovaných, vyjímku tvoří např. videa (soubory typu SMK). Podrobnosti o dekódování a dekompresi jsou uvedeny v článku Technické podrobnosti.