Archivy MPQ

Formát souborů MPQ

Formát souborů v archivech MPQ

Dříve než se začnu zabývat samotným formátem archivů MPQ, krátce se zmíním o formátu uložených souborů

Obrázky použité ve hrách společnosti Blizzard jsou buďto ve formátu PCX (úvodní obrazovky a velké plochy, jako např. inventář v Diablu II). Tyto obrázky je možné zobrazit v jakémkoliv prohlížeči (IrfanView, ACDSee32) nebo editoru (Painbrush, Microsoft Proto Editor, ...). Ikony kouzel, postavičky a ostatní drobné obrázku jsou uloženy v interních formátech, jako např. CEL, CL2, GRP, DC6. Formáty těchto souborů se podrobně zabývá TeLAMoN, který na svých stránkách zveřejnil specifikace některých formátů. Napsal také program, který umožňuje prohlížení těchto souborů.

Hudba, mluvené sekvence a zvuky jsou ve všech dosavadních hrách ve formátech WAV a MP3 (od Warcrafta III), které umí přehrát každý hudební přehrávač (např. Winamp). Není tedy problém hudbu extrahovat a použít.

Videa (vč. např. animovaných portrétů ve StarCraftu) jsou uloženy ve formátu Smacker Video nebo Bink Video. Standardní přehrávače videa tento formát (aspoň zatím) nepodporují. K přehrání těchto souborů je nutné si nainstalovat software od firmy Rad Game Tools, který je k dispozici volně na jejich internetových stránkách. Počínaje hrou Warcraft III, společnost Blizzard se rozhodla pro videa ve svých hrách zakoupit licenci pro formát DivX. Pro přehrání videa v tomto formátu je nutné nainstalovat kodek DivX.

Textury pro 3D hry (Warcraft III a novější) jsou uloženy ve formátu BLP.

Hlavička (header) a posunutí (shunt) archivů 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 0x0, 0x200, 0x400, 0x600 atd., dokud není nalezena hlavička nebo dokud není dosaženo konce souboru. Tento způsob hledání umožňuje kompinovat 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 posunutí:

• 'MPQ\x1A' znamená hlavičku MPQ (TMPQHeader)
• 'MPQ\x1B' znamená posunutí MPQ (TMPQShunt)

// Posunutí MPQ
struct TMPQShunt
{
    // Identifikátor struktury (ID_MPQ_SHUNT, 'MPQ\x1B')
    DWORD dwID;

    DWORD dwUnknown;

    // Pozice struktury TMPQHeader, relativně k offsetu struktury TMPQShunt
    DWORD dwHeaderPos;
};

// Hlavička souboru MPQ
struct TMPQHeader
{
    // // Identifikátor struktury (ID_MPQ_HEADER, 'MPQ\x1A')
    DWORD dwID;                         

    // Velikost hlavičku
    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.

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:

Rosžíř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ček 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.

Příklad

Zde je příklad funkce, která extrahuje jeden archivovaný soubor.

//-----------------------------------------------------------------------------
// Extracts one of the archived files and saves it to the disk.
//
// Parameters :
//
//   char * szArchiveName  - Archive file name
//   char * szArchivedFile - Name/number of archived file.
//   char * szFileName     - Name of the target disk file.

static int ExtractFile(char * szArchiveName, char * szArchivedFile, char * szFileName)
{
    HANDLE hMpq   = NULL;          // Open archive handle
    HANDLE hFile  = NULL;          // Archived file handle
    HANDLE handle = NULL;          // Disk file handle
    int    nError = ERROR_SUCCESS; // Result value

    // Open an archive, e.g. "d2music.mpq"
    if(nError == ERROR_SUCCESS)
    {
        if(!SFileOpenArchive(szArchiveName, 0, 0, &hMpq))
            nError = GetLastError();
    }
    
    // Open a file in the archive, e.g. "data\global\music\Act1\tristram.wav"
    if(nError == ERROR_SUCCESS)            
    {
        if(!SFileOpenFileEx(hMpq, szArchivedFile, 0, &hFile))
            nError = GetLastError()
    }

    // Create the target file
    if(nError == ERROR_SUCCESS)
    {
        handle = CreateFile(szFileName, GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, 0, NULL);
        if(handle == INVALID_HANDLE_VALUE)
            nError = GetLastError();
    }

    // Read the file from the archive
    if(nError == ERROR_SUCCESS)
    {
        char  szBuffer[0x10000];
        DWORD dwBytes = 1;

        while(dwBytes > 0)
        {
            SFileReadFile(hFile, szBuffer, sizeof(szBuffer), &dwBytes, NULL);
            if(dwBytes > 0)
                WriteFile(handle, szBuffer, dwBytes, &dwBytes, NULL);
        }
    }        

    // Cleanup and exit
    if(handle != NULL)
        CloseHandle(handle);
    if(hFile != NULL)
        SFileCloseFile(hFile);
    if(hMpq != NULL)
        SFileCloseArchive(hMpq);

    return nError;
}