3dbrew

RomFS: Difference between revisions

← Older edit
Wwylele (talk | contribs)
242 edits
Undo revision 21154 by Marius851000 (talk) This is not true. I opened one of RomFS of an official game I have. The root directory has the "Offset of first Child Directory" = 0x18, implying the root directory entry located at offset 0 is 0x18 bytes, which would contain the "Name Length" field. The said field also has value 0 as expected.
Tag: Undo
 
(2 intermediate revisions by 2 users not shown)
Line 146: Line 146:
|  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
Line 162: Line 162:
|  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
Line 211: Line 211:
|  0x10
|  0x10
|  0x4
|  0x4
|  Directory HashKey Table Pointer
|  Offset of next Directory in the same Hash Table bucket
|-
|-
|  0x14
|  0x14
Line 250: Line 250:
|  0x18
|  0x18
|  0x4
|  0x4
|  File HashKey Table Pointer
|  Offset of next File in the same Hash Table bucket
|-
|-
|  0x1C
|  0x1C
Line 261: Line 261:
|}
|}


=== 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;
Line 292: Line 292:
</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>
Line 307: Line 307:
</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.
Retrieved from "https://www.3dbrew.org/wiki/RomFS"