Archivy MPQ

Formát souborů MPQ

Formát MoPaQ na Wiki

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

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 ofsetech 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, jako to mu je u instalačního souboru 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
{
    // The ID_MPQ_USERDATA ('MPQ\x1B') signature
    DWORD dwID;

    // Maximum size of the user data
    DWORD cbUserDataSize;

    // Offset of the MPQ header, relative to the begin of this header
    DWORD dwHeaderOffs;

    // Appears to be size of user data header (Starcraft II maps)
    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 V1
    // 1 = Formát V2 (The Burning Crusade a novější)
    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.
    // Kvůli chybě v knihovně Storm.dll musí hodnota tohoto pole být 3 (tedy 4096
    // bytů v každém bloku souboru).
    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;
};

// Rozšířená hlavička MPQ pro formát V2.
struct TMPQHeader2 : public TMPQHeader
{
    // Ofset rozšířené block tabulky, relativní k offsetu hlavičky MPQ.
    LARGE_INTEGER ExtBlockTablePos;

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

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

Hašovací tabulka (Hash Table)

Při prohledání pole řetězců je nutné provést velké množství řetězcových porovnávání, což vede ke snížení rychlosti programu. Aby se při otevírání archivovaných souborů podle jména zabránilo procházení řetězcového pole, byla do formátu MPQ zavedena tzv. hašovací tabulka. Hash je datový typ (obvykle číslo), které reprezentuje větší typ, např. řetězec. Ze zadaného řetězce se vypočítá jeho tzv. hash hodnota (32-bitové číslo), podle které se pak hledá. V MPQ archivu tedy nenaleznete jména archivovaných souboru, ale pouze jejich hašovací hodnoty. A protože výpočet hashovací hodnoty je jednostranný (není možné z hashového čísla dostat zpět původní řetězec), není tedy žádným způsobem možné vyhledat z archivu jména archivovaných souborů. Hashovací tabulka v souborech MPQ obsahuje dvě kontrolní hašové hodnoty pro kontrolu jména souboru, jazykovou verzi souboru a index do block tabulky. Velikost položky v hašovací tabulce je 16 bytů. Její struktura je následující:

// Položka v hašovací tabulce. Všechny soubory jsou hledány nikoliv podle jména, ale podle haše.
struct TMPQHash
{
    // Hash jména souboru, vypočítaná metodou A
    DWORD dwName1;
    
    // Hash jména souboru, vypočítaná metodou B
    DWORD dwName2;
    
    // Jazyková verze souboru. Hodnota odpovídá typu LANGID z Windows, a také používá stejné hodnoty.
    // 0 znamená výchozí jazyk (americká angličtina), nebo jazykově neutrální soubor.
    USHORT lcLocale;

    // Platforma pro kterou je soubor použit. 0 znamená výchozí platformu.
    // Zatím nebyly pozorovány žádné jiné hosnoty.
    USHORT wPlatform;

    // Pokud je tato položka platná, jde o index v block tabulce.
    // Proměnná může obsahovat dvě speciální hodnoty:
    //  - FFFFFFFFh: Položka je prázdná a vždy byla prázdná.
    //               Při hledání souboru podle hashe se na této položce hledání zastaví.
    //  - FFFFFFFEh: Položka je prázdná, ale v minulosti byla platná (smazaný soubor).
    //               Při hledání souboru podle hashe se hledání na této položce nezastaví.
    DWORD dwBlockIndex;
};

Pokud je v jednom souboru více jazykových verzí, jejich haše následují v tabulce za sebou, a liší se pouze hodnotou lcLocale. Příkladu jazykových verzí obsahuje následující tabulka:

Tato tabulka je zakódovaná, 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)

Tabulka bloků (Block Table)

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 podobně jako u hash tabulky 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)

Rozšířená block tabulka

Od vydání hry World of Warcraft, Blizzard rozšířil formát archivů MPQ tak, aby podporoval soubory o velikosti větší než 4 GB. Rosžířená block tabulka obsahuje pole horních 16-bitů pozice souboru v MPQ. Tato tabulka 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 - 2010