Just another WordPress.com site

Alright! Starting from here on, we’ll now be covering the FileSystem’s public and private methods which will require a rather lengthy explanation. But as i said before, don’t worry because most of the code are trivial thanks to how we abstracted out most of the work through delegation(private utility methods) and composition(internal data structures).

The FileSystem’s constructor simply sets the default value to NULL or FALSE as their default value while the destructor calls the ReleaseResources() method to cleanup and release the allocated memory.

FileSystem method – Create()

Next, we’ll take a look at the Create() method. By looking at this first, we’ll have a better understanding on how our internal PAK file structure will be organized.

First we check if the directory path specified by the user is valid. Then before we start allocating memory, make sure we don’t mess anything up by releasing already allocated resources by calling ReleaseResources(). If we don’t call ReleaseResources() here and the user calls Open() then create, we would leak memory and that is very very bad. Next we initialize our filters specified in fBitFlag so that we can use them later when we individually encode our files. The next few lines of code follows the allocation and setting up the necessary data members for creating our PAK file like m_pHeader, m_pGenDirs, m_pGenFiles. After we have allocated the necessary resources, we set up our header information. We set the header to have the right signature, ID, version, and the filters used values.

1. BOOL FileSystem::Create( const CHAR *pDirectory, const CHAR *pOutputPath, OnProcessFileCallback pOnProcessFileCallback /* = NULL */, FilterFlag fBitFlag /*= FILTER_TYPE_DEFAULT*/ )
2.     {
3.         String    directory    = pDirectory;
4.         BOOL    bReturn        = TRUE;
5.  
6.         // Make sure pDirectory isn’t empty and the path exists
7.         if ( !pDirectory || !System::IsDirectoryExist( pDirectory ) )
8.             return FALSE;
9.  
10.         ReleaseResources();
11.  
12.         InitializeFilters( fBitFlag );
13.  
14.         m_pOnProcessFile = pOnProcessFileCallback;
15.  
16.         m_pHeader    = new FileHeader;
17.         m_pGenDirs    = new PAKGenDirList;
18.         m_pGenFiles    = new PAKGenFilePairList;
19.  
20.         PSX_Assert( m_pHeader && m_pGenDirs && m_pGenFiles, "Failed to allocate memory." );
21.  
22.         // Setup header information
23.         m_pHeader->m_signature = FileSystem::SIGNATURE;
24.         PSX_StrCpy( m_pHeader->m_ID, "pfs", 4 );
25.         m_pHeader->m_version = 0×000100; // TODO:  Create macro to generate pfs version
26.         m_pHeader->m_filterBitField = fBitFlag;

Error checking and initialization code.

Next. You have to take note that all the files processed and packed in the PAK file will have all their absolute paths invalidated. What is important is their relative path instead. The file’s path should have the path relative to pDirectory as their root path. Let us say that pDirectory is “c:\music\” and we are currently in “c\music\michael jackson\”. Then pPAKPath is “music\michael jackson\”.

1. // Get the relative root directory ( choosen directly )
2. INT len = PSX_StrLen( directory.GetCString() );
3. CHAR *pPtr = const_cast< CHAR*>( directory.GetCString() + len );
4. CHAR *pRootSeparator = const_cast< CHAR*>(directory.GetCString() + 2); // get the first separator( i.e c:\ )
5. String pPAKPath;
6.  
7. // Look for a seperator that’s not the root
8. while ( pPtr != pRootSeparator && *pPtr != PSX_String(‘\\’) )
9.     –pPtr;
10.  
11. // If not the root separator then we need to remove the last separator in the string.
12. if ( pPtr != pRootSeparator && PSX_StrLen( pPtr + 1 ) == 0 )
13. {
14.     directory[ pPtr - directory.GetCString() ] = PSX_String(”);
15.  
16.     // Look again for the next seperator that’s not the root
17.     while ( pPtr != pRootSeparator && *pPtr != PSX_String(‘\\’) )
18.         –pPtr;
19. }
21. // Move one char forward starting either to the first char of dir name or null(empty).
22. ++pPtr;
23.  
24. // There could be no directory.
25. // Then pPAKPath is empty
26. if ( PSX_StrLen( pPtr ) )
27.     pPAKPath = pPAKPath + pPtr;

Extracting the relative path by making pDirectory as the root path.

Finally, after we have all the necessary information set up, we can now start generating the table entries then create the PAK file.

1.     // Generate PAK folder and file entries then create the Pulse PAK File
2.     if ( !_GenerateTableEntries( directory.GetCString(), pPAKPath.GetCString() ) )
3.     {
4.         bReturn = FALSE;
5.         goto EndCreatePAK;
6.     }
7.  
8.     if ( !_CreatePulseFile( pOutputPath ) )
9.     {
10.         bReturn = FALSE;
11.         goto EndCreatePAK;
12.     }
13.  
14. EndCreatePAK:
15.     ReleaseFilters();
16.     PSX_SafeDelete( m_pGenFiles );
17.     PSX_SafeDelete( m_pGenDirs );
18.     PSX_SafeDelete( m_pHeader );
19.  
20.     return bReturn;
21. }

Generate table entries by calling _GeneratetableEntries then creating the PAK file by calling _CreatePulseFile(). If one of these functions fail, it sets bReturn to false then immediately jumps to EndcreatePAK: where it makes sure we don’t leak any memory before we pop out of this function.

We’ll take a look at _GenerateTableEntries() then _CreatePulseFile() next.

FileSystem method – _GenerateTableEntries()

_GenerateTableEntries() is the crème of the crop of our algorithm. This method is the one responsible for recursively going through each directory and files generating directory and file entries for our _CreatePulseFile() method to use.

As usual, we declare our needed temporary variables to use first.

1. BOOL FileSystem::_GenerateTableEntries( const CHAR *pFolderPath, const CHAR *pPAKPath )
2.     {
3.         // Iterate through each file in the folder
4.         DirEntryPointer pNewDir;
5.         WIN32_FIND_DATA nextFile;
6.         HANDLE            hFind;
7.         DirList            tempFolderPaths;    // Temporarily store found folders here   
8.         String            dirBuff;
9.         String            newDirPAKPath;
10.         String            newDirFolderPath;
11.         DirPathPointer    fileDirPath;        // File entries needs this when we’re about to parse each file later
12.         BOOL            bAddSeparator = TRUE;
13.         BOOL            bReturn = TRUE;
14.  
15.         fileDirPath =  new DirPath;
16.         *fileDirPath = pFolderPath;
• DirEntryPointer pNewDir : pNewDir will be used to hold our generated Directory Entry.
• WIN32_FIND_DATA nextFile : This is a win32 specific data structure that holds information about the found file.
• HANDLE hFind : This find handle is used by windows to keep track of what file or directory we’re currently traversing.
• DirList tempFolderPaths : tempFolderPaths may look confusing (which it is) but this is basically just a string contained in a smartpointer that is contained in a list. This will be used later on as a temporary storage for every directory that we find.
• String dirBuff : temporary string buffer used for formatting the string path for file and directory searching.
• String newDirPAKPath : temporary string buffer used to generate the relative path (from pDirectory as root) for recursively calling _GenerateTableEntries()
• String newDirFolderPath : temporary string buffer used to generate the absolute path for recursively calling _GenerateTableEntries()
• DirPathPointer fileDirPath : temporary string buffer stored in a SmartPointer<> used to hold pFolderPath. We use SmartPointer so that there will only be one copy of it per directory. And we also don’t have to worry about deleting it later.
• BOOL bAddSeperator : pFolder path could end with a separator ( ‘\’ for windows and ‘/’ for linux ). This makes sure that we don’t double appened our separator for generating our paths.
• BOOL bReturn :  Is simple used as a return value to indicate if successful(true) or not(false).

We first check the passed in pFolder path if it ends with a separator or not. This could happen if, for example, the user could pass in a root drive path like “c:\”. In that case, we don’t need to add another separator because it would look like “c:\\” which is not valid. Remember that this function is responsible for generating the directory and file tables. Since we have pPAKPath wich is the path relative to pDirectory(Create()) we need to store it into the list (m_pGenDirs).

1. if ( *(pFolderPath + PSX_StrLen( pFolderPath ) – 1) == PSX_String( ‘\\’ ) )
2.     bAddSeparator = FALSE;
3.  
4. // Insert new directory
5. pNewDir = new DirEntry;
6.  
7. if ( pPAKPath && PSX_StrLen( pPAKPath ) )
8. {
9.     pNewDir->m_PAKData.m_nameLen = PSX_StrLen( pPAKPath );
10.     pNewDir->m_name                 = pPAKPath;
11. }
12. else
13. {
14.     // Insert anyway since we’re now using path index for file entries.
15.     pNewDir->m_PAKData.m_nameLen = 0;
16.     pNewDir->m_name                 = PSX_String("");
17. }
18.  
19. // Put in the list then Increment num directories
20. m_pGenDirs->PushBack( pNewDir );
21. ++m_pHeader->m_numDirs;

Checking for a separator and creating a new directory entry.

Next we now prepare for finding each file and directory in pFolderPath. We do this by first making sure that the pFolderPath string has an * appended at the end of the string indicating we’re searching for all items in the current directory path. To begin searching, we’ll be using the help of the Win32 API function called FindFirstFile() and FindNextFile() functions. We only need to call FindFirstFile() once to let windows know we’re starting from the start. Then we enter into a loop calling FindNextFile() until it returns 0 indicating we’ve finished searching(or a fatal error has occurred). Inside the loop, it simply checks if the found object meets the attributes. It can’t be itself(.), a previous directory(..), a system file, or hidden. If it passes, then we’re sure that it could either be a directory or a file. If it is a, directory we simply add it into a temporary list for processing later. If it is a file then we generate a new file entry and insert it into the list(m_pGenFiles).

1. // Prepare string path to allow for file searching
2. dirBuff = String(pFolderPath) + PSX_String("\\*");
3. PSX_ZeroMem( &nextFile, sizeof( WIN32_FIND_DATA ) );
4. hFind = FindFirstFile( dirBuff.GetCString(), &nextFile );
5.  
6. if ( hFind == INVALID_HANDLE_VALUE )
7.     return FALSE;
9. do
10. {
11.     // Don’t include the following attributes and directories
12.     if ( PSX_StrCmp( nextFile.cFileName, PSX_String(".") ) == 0 ||
13.         PSX_StrCmp( nextFile.cFileName, PSX_String("..") ) == 0 ||
14.         (nextFile.dwFileAttributes & FILE_ATTRIBUTE_SYSTEM)        ||
15.         (nextFile.dwFileAttributes & FILE_ATTRIBUTE_HIDDEN) )
16.         continue;
17.  
18.     // If a directory…
19.     if ( nextFile.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY )
20.     {
21.         // Store Folder name and traverse them later
22.         DirPointer newFolder = new Directory;
23.  
24.         *newFolder = nextFile.cFileName;
25.         tempFolderPaths.PushBack( newFolder );
26.     }
27.     else // If a file…
28.     {
29.         // New File entry
30.         FileEntryPointer    pNewFileEntry    = new DirFileEntry;
31.         DirPathPointer        pnewFileDirPath    = new DirPath;
32.  
33.         // Copy File entry info
34.         pNewFileEntry->m_PAKData.m_size         = nextFile.nFileSizeLow;
35.         pNewFileEntry->m_PAKData.m_size         += nextFile.nFileSizeHigh; // Zero if not greater than DWORD
36.         pNewFileEntry->m_name                 = nextFile.cFileName;
37.         pNewFileEntry->m_PAKData.m_nameLen     = pNewFileEntry->m_name.GetLength();
38.         pNewFileEntry->m_PAKData.m_pathIndex = m_pHeader->m_numDirs – 1;    // Zero based index
39.  
40.         // Store pointer to the file’s directory path
41.         pnewFileDirPath = fileDirPath;
42.  
43.         // Finally insert in the list
44.         m_pGenFiles->PushBack( FileEntryPair( pNewFileEntry, pnewFileDirPath ) );
45.  
46.         // Update header information
47.         ++m_pHeader->m_numFiles;
48.     }
49.  
50. } while ( FindNextFile( hFind, &nextFile ) != 0 );
51.  
52. // If not ERROR_NO_MORE_FILES then something bad happened.
53. if ( GetLastError() != ERROR_NO_MORE_FILES )
54. {
55.     FindClose( hFind );
56.     bReturn = FALSE;
57.     goto EndGenerateTable;
58. }
59.  
60. // This find handle isn’t needed anymore.
61. FindClose( hFind );

Looking for files and directories inside the specified directory path.

The last remaining code simply traverses through tempFolderPaths list then calls itself(_GenerateTableEntries()), with proper path formatting, until it reaches the last item in the tempFolderPaths list. After its done traversing though the list, it simply clears out the allocated memory for tempFolderPaths and returns the value of bReturn.

1.     // Now traverse through each of the folders
2.     DirPathList::Iterator iter        = tempFolderPaths.IteratorBegin();
3.     DirPathList::Iterator iterEnd    = tempFolderPaths.IteratorEnd();
4.  
5.     while ( iter != iterEnd )
6.     {
7.         // Prepare the included directory
8.         // Don’t add separator if there’s already one at the end.
9.         if ( bAddSeparator )
10.         {
11.             newDirFolderPath    = String( pFolderPath ) + PSX_String("\\") + (*iter)->GetCString();
12.             newDirPAKPath        = String( pPAKPath ) + PSX_String("\\") + (*iter)->GetCString();
13.         }
14.         else
15.         {
16.             newDirFolderPath    = String( pFolderPath ) + (*iter)->GetCString();
17.             newDirPAKPath        = String( pPAKPath ) + (*iter)->GetCString();
18.         }
19.  
20.         if ( !_GenerateTableEntries( newDirFolderPath.GetCString(), newDirPAKPath.GetCString() ) )
21.         {
22.             bReturn = FALSE;
23.             goto EndGenerateTable;
24.         }
25.  
26.         ++iter;
27.     }
28.  
29. EndGenerateTable:
30.     tempFolderPaths.Clear();
31.  
32.     return bReturn;

See Virtual File System – Part 5 for the continuation of this article.

Internal Data Structures

Okay, I think I can hear your voice screaming now! Calm down! Take a deep breath and just relax… because most of these internal data structures are just small containers with one or two methods consisting of a few, straight-forward lines of code. First, let’s concentrate on the internal data structures.

• FileHeader : This structure contains all the important high-level information of a PAK file.

1.     // NOTE: This is exactly 56 bytes in size. We can get away with this w/o
2.     // doing a #pragma pack(1).
3.     struct FileSystem::FileHeader
4.     {
5.         Signature    m_signature;        // 16 bit GUID signature check.
6.         Char        m_ID[4];            // 3 letter file format for format check.
7.         DWORD        m_version;            // Version of this Pulse File.
8.         WORD        m_numDirs;            // Number of directories.
9.         WORD        m_numFiles;            // Number of files.
10.         I32            m_filterBitField;    // Max of 32 possible filter algorithms to choose from.
11.         SIZE_T64    m_size;                // Size of the file.
12.         POS_T64        m_dirDiskStart;
13.         POS_T64        m_fileDiskStart;
14.  
15.         FileHeader( void )
16.         {
17.             PSX_ZeroMem( this, sizeof( FileHeader ) );
18.         }
19.  
20.         void WriteData( FileSystem::IWriter *pWriter );
21.         void ReadData( FileSystem::IReader *pReader );
22.     };

 

 

 

 

 

 

 

 

 

 

 

 

Most of the data members are self explanatory. The Signature 16-bit size data type is just a structure that stores a GUID or Global Unique Identifier. This is used as a signature check to make sure that the file being opened is truly our version of a PAK file. You can read more information about Microsoft’s GUID here:
http://msdn.microsoft.com/en-us/library/aa373931(VS.85).aspx
http://en.wikipedia.org/wiki/Globally_Unique_Identifier

• DirEntry : The PAK file internal format contains two tables. The first one stores the directory entries. While the second one stores the file entries. DirEntry simply stores the directory name for now. I can’t think of anything that we need to add in here right now.

1. struct FileSystem::DirEntry
2. {
3.     struct PAKData
4.     {
5.         WORD m_nameLen;
6.     };
7.  
8.     String m_name;
9.     PAKData m_PAKData;
10.  
11.     void WriteData( FileSystem::IWriter *pWriter );
12.     void ReadData( FileSystem::IReader *pReader );
13. };

There is one odd thing with this though. We have m_name that stores the name and m_nameLen that stores the length of the directory name WHICH is interestingly encapsulated inside a structure called PAKData. The reason we want to encapsulate this inside a separate structure has something to do with how we will read/write our data from/into a PAK file. We want to minimize read/write calls by simply writing or reading all of the bits if possible. m_name isn’t included because of its internal data structures. The String class dynamically allocates memory for storing and manipulating its string. If we simple read or write it directly, it would cause some problems with since its pointer would point in some random memory and could possible crash your application. Although it’s kind of redundant since there’s only one data contained in struct PAKData, this is still helpful in case we want to add some additional info in the future. The next structure, shows how struct PAKData  is effectively used in DirFileEntry.

• DirFileEntry : This structure contains all the important information about a file stored in a PAK file.

1. struct FileSystem::DirFileEntry
2. {
3.     //#pragma pack( 1 ) // Needed to pack this for direct read and write
4.     // I am trusting the data alignment and size of this struct in the hands of the compiler.
5.     // This struct should have a size of 50 bytes. So that we won’t suffer any performance
6.     // from reading in memory.
7.     struct PAKData
8.     {
9.         SIZE_T64    m_size;
10.         SIZE_T64    m_compressedSize;
11.         SIZE_T64    m_diskStart;
12.         DWORD        m_filterBit;
13.         DWORD        m_pathIndex;        // Points to the position of the dirpath entries
14.         DWORD        m_nameLen;
15.         BYTE        _padd[4];
16.  
17.         PAKData( void ) { PSX_ZeroMem( this, sizeof( PAKData ) ); }
18.     };
19.     //#pragma pack()
20.  
21.     String    m_name;
22.     PAKData m_PAKData;
23.  
24.     void WriteData( FileSystem::IWriter *pWriter );
25.     void ReadData( FileSystem::IReader *pReader );
26. };

Notice all but m_name are all stored inside struct PAKData. Instead of writing each data member we could just simply do something like this
fstream.write( m&_PAKData, sizeof(PAKData) );

Here is a diagram showing how a PAK file is composed of these important data structures:

Internal structure of a PAK file

• DataFilter, ZLibtest: DataFilter is a base class for derived(or concrete) filter classes. As an example we have a test filter called ZLibtest. This filter uses the infamous deflate and inflate algorithm to compress and decompress data when needed.
• IReader, IWriter : These interface classes serves as an abstraction layer for reading from and writing to sources. This makes our reads and writes easier by not caring about whether we’re reading from a file or memory or writing to a file or memory. FileReader, MemoryReader, FileWriter, MemoryWriter are derived classes designed to handle the reads and writes either from/to a memory or file. Below are the interfaces for the IReader and IWriter classes.

• A bunch of typedefs : After the class declarations, billions of typedefs follows. I really apologize for the unnecessary confusion. But while i was still  developing this system, i was experimenting with what class helpers and containers to use. The typedefs made it easier for me to quicky change from one data type to another with minimum changes. One thing you may notice aside from the normal container classes is the SmartPointer<> class. The SmartPointer<> class acts like the c++ boost’s shared_ptr. Basically, this container class will keep track anything that uses this object then automatically deletes it when no one is using it anymore. It is able to do this by using reference count. We’ll be using this to store our data structures so that we don’t have to worry manually deleting our allocated resources contained in our containers. Here is a quick example

1. int main( void )
2. {
3.     // Store dynamically allocated int in SmartPointer
4.     SmartPointer< int * > pInt1( new int );  // Internal ref is set to 1
5.  
6.     {
7.         SmartPointer< int * > pInt2( pInt1 ); // Internal ref is now set to 2.
8.         // When pInt2 gets destroyed ref is automatically deremented by 1.
9.     }
10.  
11.     //pInt1 gets destroyed when it falls out of scope here… ref is 0 then it gets automatially
12.     // delete w/o requiring us to do anything…
13. }

You can learn more about shared_ptr or SmartPointers in this link http://www.boost.org/doc/libs/1_41_0/libs/smart_ptr/shared_ptr.htm

• VFS Data Members : Now that we now know what data types we’ll be using, our VFS will be storing data members shown below. The class declaration and typedefs are also included as a reference.

Before we move on to the internal utility methods, i suggest taking the time to get familiarized with the insane amount of typedefs so you won’t get confused when we get to the actual implementations. Most of them are just simple data types stored in SmartPointers then contained in a map or list.

For the continuation of this article, see Virtual Fule System – Part 3