3dbrew

RomFS: Difference between revisions

← Older edit
m →Overall RomFS file structure: Forgot to add the proper amounts of zeros 0x0000 -> 0x00000
 
(4 intermediate revisions by 3 users not shown)
Line 13: Line 13:


(There may be more implementations in the future)
(There may be more implementations in the future)
=== Overall RomFS file structure ===
The overall structure of the RomFS is as follows:
{| class="wikitable" border="1"
|-
!  START
!  SIZE
!  DESCRIPTION
!  TYPE
|-
|  0x00000
|  0x5C
|  RomFS Header (see below)
|  Header
|-
| 0x0005C
| 0x4
| Padding to the 0x20-byte boundary (0)
| Padding
|-
| 0x00060
| 0x20*N
| SHA256's on the 0x1000-byte block(s) at 0xXX000
| Master Hash
|-
| ...
| ..
| Padding to block-byte boundary (0)
| Padding
|-
| 0x01000
| ....
| RomFS Directory/Files (see below)
| Level 3
|-
| ...
| ..
| Padding to block-byte boundary (0)
| Padding
|-
| 0xXX000
| 0x20*NN
| SHA256's on each 0x1000-byte block at 0xYY000 and up.
| Level 1
|-
| ...
| ..
| Padding to block-byte boundary (0)
| Padding
|-
| 0xYY000
| 0x20*NNN
| SHA256's on each 0x1000-byte block at 0x1000 and up.
| Level 2
|}


=== Format ===
=== Format ===
Line 146: Line 202:
|  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 218:
|  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 267:
|  0x10
|  0x10
|  0x4
|  0x4
|  Directory HashKey Table Pointer
|  Offset of next Directory in the same Hash Table bucket
|-
|-
|  0x14
|  0x14
Line 250: Line 306:
|  0x18
|  0x18
|  0x4
|  0x4
|  File HashKey Table Pointer
|  Offset of next File in the same Hash Table bucket
|-
|-
|  0x1C
|  0x1C
Line 261: Line 317:
|}
|}


=== 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 348:
</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 363:
</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"