Archivy MPQ
Technické podrobnosti
Tento článek obsahuje některé technické podrobnosti týkající se formátu MPQ. Autorem těchto podrobností je Quantam.
Problém: Máme velmi velké pole řetězců. Úkolem je zjistit, zda hledaný řetězec je součástí pole. Někteří programátoři tento problém vyřeší porovnáváním hledaného řetězce s každým prvkem v poli. Při vyzkoušení této metody v praxi zjistíte, že je velice pomalá (pokud ovšem nehledáte řetězec, který je hned ze začátku pole). Jak to tedy udělat, aby nebylo nutné porovnávat řetězce ?
Řešení: Hashe. Hash je malý datový typ (obyčejně 32bitové číslo), které zastupuje větší datový typ (obvykle řetězec). Při řešení výše uvedeného problému je nutné, aby pole řetězců bylo uloženo společně s jejich hashovými hodnotami. Při porovnávání, zda je řetězec součástí pole je nutné spočítat hashovací hodnotu hledaného řetězce a pak ji porovnávat s hashovými hodnotami řetězců v poli. Tato metoda urychlí hledání řetězců v poli více než 100krát, v závislosti na velikosti jednotlivých řetězců a jejich počtu.
unsigned long HashString(char *lpszString)
{
unsigned long ulHash = 0xf1e2d3c4;
while (*lpszString != 0)
{
ulHash <<= 1;
ulHash += *lpszString++;
}
return ulHash;
}
Předchozí příklad znázorňuje velmi jednoduchý hashovací algoritmus. Funkce sčítá všechny znaky řetězce a po každém znaku posune celkovou hodnotu o jeden bit doleva. Při použití tohoto algoritmu ze stringu "arr\units.dat" vypočítáme hodnotu 0x5A858026, ze stringu "unit\neutral\acritter.grp" nám vyjde číslo 0x694CD020. Tento algoritmus není příliš použitelný, protože výsledek funkce je velice dobře předvídatelný. Navíc při relativně malém počtu řetězců dojde k častým kolizím (dva různé řetězce dávají stejnou hashovací hodnotu).
Funkce použitá k výpočtu hashových hodnot u formátu MPQ používá podstatně komplikovanější algoritmus (viz níže). Hashovací algoritmus je tzv. jednocestný, což znamená, že není téměř možné zjistit jméno souboru z hashovací hodnoty. Při použití tohoto algoritmu řetězec "arr\units.dat" dává hashovou hodnotu 0xF4E6C69D, řetězec "unit\neutral\acritter.grp" hodnotu 0xA26067F3.
unsigned long HashString(char *lpszFileName, unsigned long dwHashType)
{
unsigned char *key = (unsigned char *)lpszFileName;
unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
int ch;
while(*key != 0)
{
ch = toupper(*key++);
seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
}
return seed1;
}
Problém: Při vyhledávání řetězce je nutná co nejvyšší rychlost hledání, porovnávání hashových hodnot nestačí. Jediný způsob, jak porovnávací metodu urychlit, je neporovnávat všechny hodnoty v poli. Zní to příliš jednoduše na to, aby to byla pravda ?
Řešení: Hashovací tabulka. Hashovací tabulka je speciální typ pole, ve kterém hashovací hodnota je offsetem vyhledávaného řetězce. Řekněme, že vytvoříme pole řetězců o nějakém pevném počtu prvků (dejme tomu 1024 prvků, aby to byla mocnina dvou). Chceme vědět, zda hledaný řetězec je v této tabulce. Pro zjištění pozice řetězce v poli vypočítáme hashovou hodnotu hledaného řetězce a tuto hodnotu vydělíme modulo počtem prvků v hashovací tabulce. Při použití jednoduššího hashovacího algoritmu (první příklad) z řetězce "arr\units.dat" dostaneme hodnotu 0x5A858026, která nám dá offset 0x26 (0x5A858026 modulo 0x400 je 0x26). Řetězec na této pozici pak porovnáme s hledaným řetězcem. Pokud řetězce nesouhlasí, znamená to, že řetězec v poli není. Tento postup je znázorněn následujícím kódem:
int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)
{
int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;
if(lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))
return nHashPos;
// Error value
return -1;
}
Zbývá vyřešit poslední problém: Co se stane, pokud dva různé řetězce dávají stejné offsety ? Tyto řetězce evidentně nemohou sdílet stejnou položku v hashovací tabulce. Normálně se tento problém řeší tak, že každá položka v seznamu je ukazatelem na spojový seznam, který obsahuje všechny řetězce, které dávají stejný offset.
Archivy MPQ používají seznam uložených souborů jako hashovací tabulku. Formát této tabulky je však poněkud odlišný od běžně používaného formátu hashovacích tabulek. Namísto použití hashové hodnoty jako offsetu a uložení jména souboru pro porovnání, archivy vůbec neobsahují jména uložených souborů, ale používají tři různe hashové hodnoty; Jednu pro offset do hashovací tabulky a dvě pro ověření jména souboru. Tyto dvě hashové hodnoty jsou použity pro ověření jména souboru. Tím je pravděpodobnost, že dvě různá jména souborů povedou ke stejné hashové hodnotě průměrně 1:18889465931478580854784, což by mělo být dostatečně bezpečné.
Druhá odlišnost hashovacích tabulek v archivech MPQ spočívá v řešení kolizních případů. V případě kolize je ukazatel posunut na další prvek hashovací tabulky a proces se opakuje, dokud není nalezeno volné místo. Následující kód ukazuje způsob hledání pozice archivovaného souboru v archivu MPQ:
int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
{
const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
int nHash = HashString(lpszString, HASH_OFFSET);
int nHashA = HashString(lpszString, HASH_A);
int nHashB = HashString(lpszString, HASH_B);
int nHashStart = nHash % nTableSize;
int nHashPos = nHashStart;
while (lpTable[nHashPos].bExists)
{
if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
return nHashPos;
else
nHashPos = (nHashPos + 1) % nTableSize;
if (nHashPos == nHashStart)
break;
}
// Error value
return -1;
}
Možná že uvedený kód vypadá složitě, teorie za ním je docela jednoduchá. Algoritmus v podstatě souhlasí s postupem, jak načíst soubor z archivu:
Z předchozího výkladu vyplývá, že archivní soubor MPQ musí obsahovat hashovací tabulku, která musí obsahovat položky pro všechny soubory. Co se však stane, když je každá položka v hashové tabulce použita ? V takovém případě není možné do archivu přidat další soubor(-y). Pokud je to přesto nutné, celý archiv MPQ musí být znovu sestaven.
Problém: Na internetu chceme uveřejnic velký program (např. 50 MB). To je pro stahování z internetu hodně, a ne každý má takové připojení k internetu, které na to stačí.
Řešení: Komprese. Komprese je metoda uložení určitého množství dat do menšího prostoru. Pro kompresi byly vyvinuty stovků různých algoritmů, každá pracuje jiným způsobem. V archivech MPQ jsou použity dva druhy komprese. Ke kompresi dat je použita knihovna PKWARE Data Compression Library, ke kompresi zvukových souborů je použita kompresní metoda pvyvinutá pravděpodobně společností Blizzard.
Potřeba chránit data před zvědavýma očima stará jako lidstvo samo. Lidé odpradávna potřebovali předat informace někomu jinému. Od ručně psaných dopisů nesených na nohou kurýrem po platby elektronickými kartami přes Internet. Metoda ochrany dat se nazývá šifrování. Nevíme sice, kdy byl vyvinut úplně první algoritmus na šifrování dat, víme, že takových algoritmů je příliš mnoho na spočítání. Tento článek se nesnaží vysvětlovat principy šifrování dat, pouze se snaží vysvětlit šifrování použité v archivech MPQ.
Začneme s jednoduchým algoritmem, který byl publikován v Basic Lab Notes, převedeným do jazyka C:
void EncryptBlock(void *lpvBlock, int nBlockLen, char *lpszPassword)
{
int nPWLen = strlen(lpszPassword), nCount = 0;
char *lpsPassBuff = (char *)malloc(nPWLen);
memcpy(lpsPassBuff, lpszPassword, nPWLen);
for (int nChar = 0; nCount < nBlockLen; nCount++)
{
char cPW = lpsPassBuff[nCount];
lpvBlock[nChar] ^= cPW;
lpsPassBuff[nCount] = cPW + 13;
nCount = (nCount + 1) % nPWLen;
}
free(lpsPassBuff);
return;
}
Podobně jako první příklad s výpočtem hashové hodnoty, tento kód je extrémně jednoduchý, a není možné jej použít v současném programu, kde je vyžadována skutečná bezpečnost dat. Tento program prochází šifrovaným blokem a XORuje každý byte dat odpovídajícím bytem hesla. Dále pak mění byte v heslu přičtením 13ti (13 bylo vybráno, protože jde o prvočíslo). To způsobuje, že princip šifrovacího kódu je obtížněji rozpoznatelný. Při použití tohoto algoritmu z řetězce "encryption" (65 6E 63 72 79 70 74 69 6F 6E) a hesla "MPQ" (4D 50 51) dostaneme jeho zašifrovanou hodnotu (28 3E 32 28 24 2E 13 03 04 1A). Tento algoritmus je tzv. symetrický, tj. heslo použité k zašifrování dat je stejné jako heslo použité k jejich dešifrování. Vzhledem k tomu, že XOR je symetrická operace, pro dešifrování může být použit ten stejný algoritmus jako pro šifrování.
Pokud je nutné pracovat s archivy MPQ, je nutné znát šifrovací mechanismus. Algoritmus použitý pro šifrování dat je zajímavým hybridem sůzných šifrovacích metod. Dešifrovací funkce vytváření šifrovací tabulku (použitou také v hashovací funkci) a používají jméno souboru jako klíč pro vyzvedávání prvků šifrovací tabulky. Následně jsou data určená k zašifrování XORována s prvky tabulky. Zvláštní metoda. Kód, který vytvoří šifrovací tabulku o velikosti 500 dvojslov (DWORDů) v jazyce C je zde:
void prepareCryptTable()
{
unsigned long seed = 0x00100001, index1 = 0, index2 = 0, i;
for(index1 = 0; index1 < 0x100; index1++)
{
for(index2 = index1, i = 0; i < 5; i++, index2 += 0x100)
{
unsigned long temp1, temp2;
seed = (seed * 125 + 3) % 0x2AAAAB;
temp1 = (seed & 0xFFFF) << 0x10;
seed = (seed * 125 + 3) % 0x2AAAAB;
temp2 = (seed & 0xFFFF);
cryptTable[index2] = (temp1 | temp2);
}
}
}
Máte dojem, že Blizzard najal pro vytvoření šifrovací techniky nějakého rozmrzelého profesora matematiky ? Vypadá to tak. Naštěstí není problém, pokud nerozumíte tomuto kódu. Pokud chcete pracovat s archivy MPQ, tyto funkce sice potřebujete, ale není nutné znát princip, na kterém fungují. Poté, co je šifrovací tabulka inizializována, data z archivu MPQ mohou být dešifrována pomocí následující funkce (nechtějte vědět podrobnosti o tom, jak to funguje, sám to nevím)
void DecryptBlock(void *block, long length, unsigned long key)
{
unsigned long seed = 0xEEEEEEEE, unsigned long ch;
unsigned long *castBlock = (unsigned long *)block;
// Round to longs
length >>= 2;
while(length-- > 0)
{
seed += stormBuffer[0x400 + (key & 0xFF)];
ch = *castBlock ^ (key + seed);
key = ((~key << 0x15) + 0x11111111) | (key >> 0x0B);
seed = ch + seed + (seed << 5) + 3;
*castBlock++ = ch;
}
}
Copyright (c) Quantam a Ladislav Zezula 2003 - 2010