Changes

|  0x4

|  0x4

|  0x4

|  0x4

|  Directory HashKey Table Offset

|  Directory Hash Table Offset

|-

|-

|  0x8

|  0x8

|  0x4

|  0x4

|  Directory HashKey Table Length

|  Directory Hash Table Length

|-

|-

|  0xC

|  0xC

|  0x14

|  0x14

|  0x4

|  0x4

|  File HashKey Table Offset

|  File Hash Table Offset

|-

|-

|  0x18

|  0x18

|  0x4

|  0x4

|  File HashKey Table Length

|  File Hash Table Length

|-

|-

|  0x1C

|  0x1C

|  0x10

|  0x10

|  0x4

|  0x4

|  Directory HashKey Table Pointer

|  Offset of next Directory in the same Hash Table bucket

|-

|-

|  0x14

|  0x14

|  0x18

|  0x18

|  0x4

|  0x4

|  File HashKey Table Pointer

|  Offset of next File in the same Hash Table bucket

|-

|-

|  0x1C

|  0x1C

|}

|}

=== HashKey Table Structure ===

=== Hash Table Structure ===

For both files and directories, a HashKey table is created for MetaData verification.

For both files and directories, a [https://en.wikipedia.org/wiki/Hash_table#Collision_resolution separate chaining hash table] is created for quick lookup.

A HashKey table consists of a number of uints, all initialized to 0xFFFFFFFF. The size of the table is dependent on the number of entries in the relevant MetaData table (it's probably intended to always be the smallest prime number greater than or equal to the number of entries, but the implementation was lazy), illustrated by the following code (C#):

A hash table consists of a number of buckets, all initialized to 0xFFFFFFFF. The size of the table is dependent on the number of entries in the relevant MetaData table (it's probably intended to always be the smallest prime number greater than or equal to the number of entries, but the implementation was lazy), illustrated by the following code (C#):

<pre>

<pre>

public static byte[] GetHashKeyTableLength(uint numEntries)

public static byte[] GetHashTableLength(uint numEntries)

{

{

uint count = numEntries;

uint count = numEntries;

</pre>

</pre>

Once the table is initialized, each File/Directory has a hash taken based off its name (byte array taken from Metadata entry) and Parent Directory's offset (C#):

The hash function is based off directory/file name (byte array taken from Metadata entry) and Parent Directory's offset (C#):

<pre>

<pre>

</pre>

</pre>

Each hash is then taken modulus the number of uints in the HashKey Table. If the HashKeyTable's value at that index is 0xFFFFFFFF (unused), the offset for the relevant directory/file is inserted into the table at that offset. Otherwise, after inserting the relevant directory/file's offset, the directory/file has its HashKey Pointer set to the offset of the directory/file that previously occupied the HashKey Table at that index.

Each directory/file is put into the ''i''th bucket, where ''i'' is the hash taken modulus of bucket count. The directories/files in the same bucket form a linked list, with the value in hash table as the offset to the head element. When creating the hash table, a latter added directory/file is always added as the head element of the linked list.