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í:

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:

• 'MPQ\x1A' znamená hlavičku MPQ
• 'MPQ\x1B' znamená hlavičku uživatelských dat v MPQ

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:

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:

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.

Copyright (c) Ladislav Zezula 2003 - 2011