Warsztat.GDCompo!ProjektyMediaArtykułyQ&AForumOferty pracyPobieranie

Opisz napotkaną sytuację, a redakcja niezwłocznie znajdzie rozwiązanie!

wyślij anuluj

Wirtualny system plików

Tekst został importowany z Warsztatowych artykułów. Jego oryginalnym autorem jest Tomasz Dąbrowski. Jeżeli został importowany poprawnie, usuń ten szablon!

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:

Struktura VFS

  • 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
    Dzięki temu w przypadku wydania patcha lub dodatku, wystarczy podmienić kilka plików i wgrać je do nowego archiwum (np. data01.vfs), a przy szukaniu pliku przeglądać archiwa od najnowszego. Na końcu możemy sprawdzić archiwum na płycie CD -- dzięki temu będziemy przy instalacji mogli dać użytkownikowi możliwość oszczędzenia miejsca na dysku dzięki doczytywaniu rzadziej używanych plików z płyty.
  • 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. :)

http://dabroz.scythe.pl/2008/07/17/wirtualny-system-plikow-vfs

Tekst dodał:
Tomasz Dąbrowski
18.07.2008 19:37

Ostatnia edycja:
Tomasz Dąbrowski
18.07.2008 19:37

Kategorie:

Aby edytować tekst, musisz się zalogować.

# Edytuj Porównaj Czas Autor Rozmiar
#1 edytuj 18.07.2008 19:37 Tomasz Dąbrowski 36.74 KB
Zwykły
Do sprawdzenia
Do akceptacji
  • ~:/ 19 stycznia 2009 18:37
    Link nie działa :/
  • Tomasz Dąbrowski (@Dab) 03 lutego 2009 02:34
    Trzeba mieć farta, żeby trafić na 5-minutowy przestój serwera. ;)
  • Ciunkos (@Ciunkos) 07 lutego 2009 02:52
    Tekst fajny - przydał się w praktyce i za to + ;)
  • Napisz komentarz:
    Aby dodać swój komentarz, musisz się zalogować.
Licencja Creative Commons

Warsztat używa plików cookies. | Copyright © 2006-2017 Warsztat · Kontakt · Regulamin i polityka prywatności
build #ff080b4740 (Tue Mar 25 11:39:28 CET 2014)