Większość gier komputerowych przetwarza ogromne ilości danych. Najłatwiej uzmysłowić to sobie w czasie oczekiwania na załadowanie kolejnego poziomu; w czasie tego -- irytującego, swoją drogą -- procesu komputer musi wczytać i przetworzyć setki megabajtów tekstur, siatek, skryptów i wszystkich innych plików z danymi. Tekst ten nie będzie jednak poświęcony zagadnieniu wczytywania poziomów (ani też metodom irytowania użytkownika). Powiemy sobie natomiast, jak można wygodnie zorganizować wszystkie pliki z danymi.
W tym celu zbudujemy wirtualny system plików (ang. virtual file system, VFS). W uproszczeniu można powiedzieć, że jest to dodatkowa warstwa na nasz fizyczny systemowy system plików, pośrednicząca między danymi na dysku a danymi w pamięci. Dzięki jej zastosowaniu wszystkie dane, z jakich będzie korzystać gra zostaną upakowane do jednego pliku. Jakie są korzyści z zastosowania VFS?
- krótszy czas instalacji gry (kopiowanie jednego dużego pliku zwykle trwa krócej niż kopiowanie setek małych plików)
- ochrona integralności danych gry (użytkownikowi ciężej będzie "dłubać" w naszym pliku niż gdyby miał do dyspozycji katalogi z poszczególnymi rodzajami danych)
- możliwość łatwego patchowania plików danych (o czym powiemy sobie pod koniec artykułu)
Trzeba się zastanowić, jakie będą założenia naszego VFS. W tym konkretnym przypadku chodzi o archiwum typu "read-only" -- nie przewidujemy możliwości zmiany zawartości istniejącego archiwum. Ma to istotny wpływ na implementację. Nie są nam też potrzebne dokładne nazwy plików -- zamiast nich wystarczą nam hashe (sumy kontrolne).
Ogólny schemat budowy wirtualnego systemu plików wyglądać będzie następująco:
- nagłówek -- tutaj umieszczone będą takie informacje jak wersja VFS, flagi kompresji, szyfrowania, etc.
- hashe plików -- tutaj znajdą się hashe nazw plików i adres odpowiadających im danych w VFS
- dane -- najważniejsza (i najbardziej obszerna część)
Przy wyciąganiu danych z VFS zazwyczaj będzie nam potrzebny strumień bajtów (czyli po prostu treść pliku) i jego długość. Stwórzmy więc następującą klasę:
class CVFile
{
void* mData;
int mLength;
public:
CVFile(void* data, int length);
~CVFile();
void* GetData() {return mData;}
int GetLength() {return
mLength;}
};
Aby uniknąć wycieków pamięci zastosujemy model RAII. Dane zawarte w pliku będziemy zwalniali w destruktorze, co uchroni nas przed niemiłymi efektami w sytuacjach wyjątkowych. Treść destruktora wygląda tak:
CVFile::~CVFile()
{
delete[] mData;
OK. Teraz przydałoby się mieć możliwość pobierania danych z naszego archiwum. Ale najpierw trzeba je stworzyć, prawda? W tym celu stworzymy aplikację C#.
Wróćmy więc na chwilę do fizycznego modelu danych. Struktura naszego pliku będzie wyglądać następująco:
- nagłówek:
- wersja archiwum (typ int32, w naszym przypadku zawsze 1)
- flagi (typ int32, wartość = 0)
- ilość plików (typ int32)
- tablica hashów;, dla każdego pliku:
- hash (128 bitów)
- pozycja danych w archiwum (int32)
- długość pliku (int32)
- dane; dla każdego pliku:
- treść pliku
Wersja archiwum może przydać się, gdy po różnego rodzaju ulepszeniach będziemy nadal chcieli móc korzystać ze starych archiwów -- wtedy nie obędzie się bez dopisania konwertera. Flagi to pole, w którym możemy przechowywać np. fakt kompresji plików. Dla uproszczenia w naszym przykładowym VFS taka funkcjonalność nie będzie dostępna, ale warto zarezerwować sobie na to miejsce.
Dla każdego pliku będziemy przechowywali hash, offset i długość. Offset będziemy wyliczali od początku pliku, aby maksymalnie uprościć implementację.
Przykładowy kod w C#, który tworzy archiwum będzie wyglądał więc następująco:
using System;
using System.Collections.Generic;
using System.IO;
using System.Security.Cryptography;
using System.Text;
namespace VFS1
{
static class Program
{
static void Main()
{
List<FileInfo>
FileList = new
List<FileInfo>();
FileInfo OutFile
= new FileInfo("data.vfs");
BinaryWriter Writer
= new BinaryWriter(OutFile.OpenWrite());
DirectoryInfo CurrentDir
= new DirectoryInfo(".");
foreach (DirectoryInfo
dir in CurrentDir.GetDirectories())
{
foreach (FileInfo file in dir.GetFiles())
{
FileList.Add(file);
}
}
int Version = 1;
int Flags = 0;
int FileCount = FileList.Count;
Writer.Write(Version);
Writer.Write(Flags);
Writer.Write(FileCount);
int SizeOfInt32 =
4;
int SizeOfHash =
16;
int FileInfoSize =
(SizeOfInt32 * 2 + SizeOfHash);
int Index = SizeOfInt32 * 3 + FileInfoSize
* FileCount;
foreach (FileInfo file in FileList)
{
string shortname =
file.Directory.Name +
"\\" + file.Name;
Writer.Write(GetMd5(shortname));
Writer.Write(Index);
Writer.Write((int)file.Length);
Index += (int)file.Length;
}
foreach (FileInfo file in FileList)
{
int length=(int)file.Length;
Stream reader =
file.OpenRead();
byte[] buffer = new byte[length];
reader.Read(buffer, 0, length);
Writer.Write(buffer);
reader.Close();
}
Writer.Close();
}
static byte[] GetMd5(string filename)
{
MD5 md5 = MD5.Create();
return md5.ComputeHash(Encoding.ASCII.GetBytes(filename));
}
}
Nasze archiwum jest utworzone i gotowe do użycia. Jeżeli nie wierzysz, możesz podejrzeć stworzony plik (nazywamy go data.vfs) w ulubionym edytorze hexów. Plik będzie miał opisaną wcześniej strukturę i będzie przechowywał wszystkie pliki we wszystkich podkatalogach katalogu bieżącego.
Do naszego projektu w C++ dodamy klasę pozwalającą na wyciąganie danych z archiwum.
class CVFS
{
public:
static CVFile GetData(std::string filename);
};
Stworzymy teraz funkcję, która będzie wyciągać dane z archiwum.
CVFile CVFS::GetData(std::string filename)
{
unsigned char md5[16];
CalcMD5(filename,
md5);
std::string ArchiveFilename = "data.vfs";
FILE * File = fopen(ArchiveFilename
.c_str(), "rb");
if (!File) throw "Archive not
found.";
int Version;
int Flags;
int FilesCount;
fread(&Version,
sizeof(int), 1,
File);
fread(&Flags,
sizeof(int), 1,
File);
fread(&FilesCount,
sizeof(int), 1,
File);
if (Version != 1) throw "Unsupported
version.";
int Pos = -1, Length;
for (int i = 0; i < FilesCount; i++)
{
unsigned char fmd5[16];
fread(fmd5, 1,
16, File);
bool ok = true;
for (int j = 0; j <
16; j++)
{
if (fmd5[j] != md5[j])
{
ok = false;
break;
}
}
fread(&Pos,
sizeof(int), 1,
File);
fread(&Length,
sizeof(int), 1,
File);
if (ok)
{
break;
}
else
{
Pos = -1;
}
}
if (Pos==-1) throw "File not
found.";
fseek(File, Pos, 0);
char * data = new char[Length];
fread(data, 1, Length, File);
fclose(File);
return CVFile(data, Length);
}
Do poprawnego działania będzie nam brakować funkcji CalcMD5. Jej nagłówek wygląda następująco:
void CalcMD5(std::string text, unsigned char *out);
Jej implementację pozostawiam Czytelnikowi. Ponieważ C++, w przeciwieństwie do C#, nie zawiera biblioteki udostępniającej funkcje kryptograficzne, to odpowiednią funkcję musimy dostarczyć sami. Być może w projekcie, w którym chcemy użyć VFS stosujemy już jakąś bibliotekę zawierającą MD5? Jeżeli nie, możemy skorzystać z tej implementacji. Możemy też oczywiście użyć innej niż MD5 funkcji skrótu. Możemy nawet sami zaimplementować jakiś prosty hash -- w końcu rzadko kiedy ilości plików idą w miliony, aby wystąpiło ryzyko kolizji.
Ostatnie, co zostało do dodania, to konstruktor CVFile.
CVFile::CVFile(void * data, int len)
{
this->mData = data;
this->mLength = len;
Możemy już w prosty sposób korzystać z naszego kodu. Aby wyciągnąć jakikolwiek plik z archiwum, wystarczy użyć następującej składni:
{
CVFile File = CVFS::GetData("dane\\plik.txt");
FILE *Out = fopen("test.dat",
"wb");
fwrite(File.GetData(), 1, File.GetLength(), Out);
fclose(Out);
Ponieważ już wiesz, że implementacja VFS nie jest zadaniem trudnym, to możesz w ramach chęci i potrzeb swojego projektu dodać dodatkową funkcjonalność do wirtualnego systemu plików. Przykładowe ulepszenia:
- możliwość dynamicznej modyfikacji archiwum -- dodawanie plików możemy rozwiązać w prosty sposób, dodając dane na końcu pliku. Musimy jednak pamiętać o wpisie w tabeli hashów. Być może warto zostawić na nią trochę wolnego miejsca, aby uniknąć jej ciągłej realokacji. Można też zaimplementować ją jako listę: na końcu tablicy hashów przechowywać adres i rozmiar kolejnej tablicy. Kolejnym problemem jest usuwanie i modyfikowanie plików: o ile zostawianie "dziur" nie jest trudne w implementacji, to szybko doprowadzi do fragmentacji archiwum. Cóż -- chcemy mieć potężny moduł VFS, to musimy zmierzyć się z takimi samymi problemami jak projektanci "rzeczywistych" systemów plików.
- szybsze szukanie plików -- jeżeli nasze archiwum nie ulega modyfikacjom, ale za to zawiera ogromne ilości drobnych plików, to wyszukiwanie liniowe przy każdym wczytywaniu pliku może okazać się zbyt wolne. Aby rozwiązać ten problem, możemy przechowywać kilka początkowych liter nazwy pliku w tabeli hashów i początkowo wyszukać binarnie zakres adresów, spod których hashe powinniśmy porównać z poszukiwanym.
- patchowanie -- z łatwością możemy dodać do VFS następujący algorytm:
- znajdź wszystkie pliki typu .vfs (w tym również np. na dyskach CD)
- przy poszukiwaniu pliku przeglądaj po kolei wszystkie archiwa, jeżeli pliku dotychczas nie znaleziono
- kompresja -- wystarczy przeznaczyć któryś z bitów flag na atrybut kompresji i przy jego zaznaczeniu dokonywać kompresji/dekompresji strumienia danych. Zaimplementowanie kompresji GZip nie będzie trudne, a może dać nam spory zysk w przypadku plików tekstowych.
- podgląd archiwum -- w tym przypadku będziemy potrzebować listy plików łącznie z nazwami. Możemy albo zmodyfikować tablicę hashów, albo umieścić w archiwum "wirtualny" plik z nazwami (__names.txt)
Na deser zostawiłem praktyczne zastosowanie VFS w połączeniu z kilkoma popularnymi bibliotekami.
OpenGL + DevIL
{
CVFile File = CVFS::GetData(filename);
if (!ilLoadL(IL_TYPE_UNKNOWN, File.GetData(), File.GetLength()))
{
throw "Texture loading error.";
}
// ...
OpenAL + ALUT
{
ALuint buffer;
ALenum format;
ALsizei size;
ALfloat freq;
ALvoid *data;
alGenBuffers(1,
&buffer);
CVFile file = CVFS::GetData(filename);
data=alutLoadMemoryFromFileImage
(file.GetData(),file.GetLength(),
&format, &size,
&freq);
//
...
freetype
{
FT_Library library;
if (FT_Init_FreeType(
&library ))
throw "FT_Init_FreeType
failed";
FT_Face face;
CVFile file = CVFS::GetData(filename);
if (FT_New_Memory_Face(library, (const FT_Byte*)file.GetData(), file.GetLength(), 0, &face))
throw "FT_New_Face
failed";
// ...
Materiały dodatkowe
Kody źródłowe wszystkich programów (ZIP, 2kB)
Będę wdzięczny za wszystkie komentarze i znalezione błędy. :)
Comments:
-
Ogólnie spoko, chociaż bardzo powierzchownie miło by było jakbyś rozbudował arta o m.in. doklejanie plików w locie, kompresje itd. itp.
Natomiast przyczepię się do składnii:
static CVFile GetData(std::string filename);
Jeśli już używasz czegoś takiego to warto, aby CVFile miało zaimplementowane konstruktor kopiujący, bo inaczej zaczną się dziać różne dziwne rzeczy ze zwalnianiem pamięci.
Zdecydowanie lepszym sposobem jest:
static CVFile* GetData(...);
a następnie:
std::auto_ptr<CVFile> file(CVFile::GetData(...));
Pozdrawiam
KT25.07.2008 02:22:21
-
auto_ptr? Aż takie rozwiązanie nie jest chyba potrzebne w tym wypadku. Dużo bardziej elegancko (moim zdaniem) byłoby po prostu "sprywatyzować" konstruktory w CData, a klasę CVFS z nią zaprzyjaźnić.
Tekst miał wprowadzić czytelnika w wirtualne systemy plików i wydaje mi się, że po takim "nakierowaniu" większość poradzi sobie z implementacją rozmaitych dodatków. Jeżeli jednak ktoś miałby jakieś problemy -- proszę pisać, z chęcią rozbuduję tekst.
Jedynie co do modyfikacji archiwum w locie mam mieszane uczucia (pod względem projektowym). Widząc bardzo rozbudowane systemy VFS zawsze zastanawiam się, czemu nie zastosowano po prostu natywnego sytemu plików -- przecież pisanie VFS z wszystkim, co posiada "prawdziwy" FS to silnikologia w czystym wydaniu. ;)11.08.2008 15:29:43
-
skaarj:
Ja w swoim VFSie użyłem nie hashy lecz zwykłych c-stringów jako nazw poszczególnych plików, dodatkowo w nagłówku mam nazwę plugina którym skompresowane jest archiwum.
12.08.2008 02:00:10
-
Pomysł z MD5 zamiast nazw plików przypadł mi do gustu ;> (dygresja: widziałem już coś takiego do obfuskacji importów w PE, natomiast w przypadku packfileów jeszcze nie ;> nice)
15.08.2008 20:31:59
