Difference between revisions of "RomFS"

From 3dbrew
Jump to navigation Jump to search
(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
 
(12 intermediate revisions by 7 users not shown)
Line 1: Line 1:
−
{{Stub}}
 
 
=== Overview ===
 
=== Overview ===
−
RomFS or Read-Only Filesystem is part of the [[NCCH]] format, and is used as external file storage.
+
RomFS (or Read-Only Filesystem) is part of the [[NCCH]] format, and is used as external file storage.
  
 
RomFS can be used:
 
RomFS can be used:
Line 9: Line 8:
 
*to contain the game manual accessible from the [[Home Menu]]
 
*to contain the game manual accessible from the [[Home Menu]]
  
−
*to contain the [[Download Play#Broadcasted application data|DLP Child CIA]]
+
*to contain the [[Download Play#Broadcasted application data|DLP Child CIA]])
  
 
*or to contain game cartridge update data
 
*or to contain game cartridge update data
  
 
(There may be more implementations in the future)
 
(There may be more implementations in the future)
−
 
  
 
=== Format ===
 
=== Format ===
  
−
All of the content (including the header) in RomFS appears to be aligned to 0x1000 byte blocks, the first block starts at 0x1000. Starting with the second block, every block begins with a SHA-256 hash. This hashes the whole 0x1000-byte block following this block. For the last block, this hash hashes the first block at 0x1000. The total RomFS filesize is always at least 0x4000.
+
The RomFS is wrapped inside a IVFC hash-tree container, and the actual data is structured like a node-based tree, starting at the root level directory node, moving down to other directory and file nodes. Each directory node  has pointers to child directory nodes and siblings, together with a pointer to the first file node for that directory. Each file node has pointers to their next file node, together with information about the actual file data.
  
−
The RomFS header is 0x80 bytes long and following is known about the structure:
+
The RomFS IVFC hash-tree header is 0x5C bytes long and is structured as follows:
  
 
{| class="wikitable" border="1"
 
{| class="wikitable" border="1"
Line 38: Line 36:
 
| 0x08
 
| 0x08
 
| 0x4
 
| 0x4
−
| Level 1 size
+
| Master hash size
 +
|-
 +
| 0x0C
 +
| 0x8
 +
| Level 1 logical offset
 +
|-
 +
| 0x14
 +
| 0x8
 +
| Level 1 hashdata size
 +
|-
 +
| 0x1C
 +
| 0x4
 +
| Level 1 block size, in log2
 +
|-
 +
| 0x20
 +
| 0x4
 +
| Reserved
 +
|-
 +
| 0x24
 +
| 0x8
 +
| Level 2 logical offset
 +
|-
 +
| 0x2C
 +
| 0x8
 +
| Level 2 hashdata size
 +
|-
 +
| 0x34
 +
| 0x4
 +
| Level 2 block size, in log2.
 +
|-
 +
| 0x38
 +
| 0x4
 +
| Reserved
 +
|-
 +
| 0x3C
 +
| 0x8
 +
| Level 3 logical offset
 +
|-
 +
| 0x44
 +
| 0x8
 +
| Level 3 hashdata size
 +
|-
 +
| 0x4C
 +
| 0x4
 +
| Level 3 block size, in log2.
 +
|-
 +
| 0x50
 +
| 0x4
 +
| Reserved
 +
|-
 +
| 0x54
 +
| 0x4
 +
| Reserved
 +
|-
 +
| 0x58
 +
| 0x4
 +
| Optional info size.
 +
|}
 +
 
 +
=== Level 3 Format ===
 +
 
 +
The Level 3 partition of a RomFS consists of a header specifying offsets to four tables, followed by filedata (aligned to 16-bytes). Though their size varies by RomFS contents, the tables are always sequential and in the same order, as follows:
 +
 
 +
{| class="wikitable" border="1"
 +
|-
 +
!  START
 +
!  SIZE
 +
!  DESCRIPTION
 +
|-
 +
|  0x0
 +
|  0x28
 +
|  Header
 +
|-
 +
|  0x28
 +
|  Varies
 +
|  Directory HashKey Table
 +
|-
 +
|  Varies
 +
|  Varies
 +
|  Directory Metadata Table
 +
|-
 +
|  Varies
 +
|  Varies
 +
|  File HashKey Table
 +
|-
 +
|  Varies
 +
|  Varies
 +
|  File Metadata Table
 +
|-
 +
|  Varies
 +
|  Varies
 +
|  File Data
 +
|}
 +
 
 +
=== Level 3 Header Format ===
 +
 
 +
RomFS Header data is always 0x28 bytes long, and follows this layout (offsets are from the start of the header):
 +
 
 +
{| class="wikitable" border="1"
 +
|-
 +
!  START
 +
!  SIZE
 +
!  DESCRIPTION
 +
|-
 +
|  0x0
 +
|  0x4
 +
|  Header Length
 +
|-
 +
|  0x4
 +
|  0x4
 +
|  Directory Hash Table Offset
 +
|-
 +
|  0x8
 +
|  0x4
 +
|  Directory Hash Table Length
 +
|-
 +
|  0xC
 +
|  0x4
 +
|  Directory Metadata Table Offset
 +
|-
 +
|  0x10
 +
|  0x4
 +
|  Directory Metadata Table Length
 
|-
 
|-
 
|  0x14
 
|  0x14
 
|  0x4
 
|  0x4
−
|  2nd content size
+
|  File Hash Table Offset
 +
|-
 +
|  0x18
 +
|  0x4
 +
|  File Hash Table Length
 
|-
 
|-
 
|  0x1C
 
|  0x1C
 
|  0x4
 
|  0x4
−
|  Level 1 block size, in log2.
+
|  File Metadata Table Offset
 
|-
 
|-
−
|  0x2C
+
|  0x20
 
|  0x4
 
|  0x4
−
|  3rd content size
+
|  File Metadata Table Length
 
|-
 
|-
−
|  0x34
+
|  0x24
 
|  0x4
 
|  0x4
−
|  Level 2 block size, in log2.
+
|  File Data Offset
 +
|}
 +
 
 +
=== Directory Metadata Structure ===
 +
 
 +
When a RomFS is built, directories are added recursively starting with the root. When a directory is added, all of its files are added to the File Metadata Table, then all of its subdirectories (if any), are added to the table. If any of the directory's subdirectories have their own subdirectories, the current directory's subdirectories are all added before the subdirectories' subdirectories are added.
 +
 
 +
A Metadata entry for a directory has the following structure (all values are initialized to 0xFFFFFFFF, and remain that way when unused):
 +
 
 +
{| class="wikitable" border="1"
 
|-
 
|-
−
|  0x44
+
!  START
 +
!  SIZE
 +
!  DESCRIPTION
 +
|-
 +
|  0x0
 
|  0x4
 
|  0x4
−
|  Level 3 size
+
|  Offset of Parent Directory (self if Root)
 
|-
 
|-
−
|  0x4C
 
 
|  0x4
 
|  0x4
−
|  Level 3 block size, in log2.
+
|  0x4
 +
|  Offset of next Sibling Directory
 
|-
 
|-
−
|  0x58
+
|  0x8
 
|  0x4
 
|  0x4
−
|  Optional info size.
+
|  Offset of first Child Directory (Subdirectory)
 +
|-
 +
|  0xC
 +
|  0x4
 +
|  Offset of first File (in File Metadata Table)
 +
|-
 +
|  0x10
 +
|  0x4
 +
|  Offset of next Directory in the same Hash Table bucket
 +
|-
 +
|  0x14
 +
|  0x4
 +
|  Name Length
 +
|-
 +
|  0x18
 +
|  Name Length (rounded up to multiple of 4)
 +
|  Directory Name (Unicode)
 +
|}
 +
 
 +
=== File Metadata Structure ===
 +
 
 +
A Metadata entry for a file has the following structure (all values are initialized to 0xFFFFFFFF, and remain that way when unused):
 +
 
 +
{| class="wikitable" border="1"
 +
|-
 +
!  START
 +
!  SIZE
 +
!  DESCRIPTION
 +
|-
 +
|  0x0
 +
|  0x4
 +
|  Offset of Containing Directory (within Directory Metadata Table)
 +
|-
 +
|  0x4
 +
|  0x4
 +
|  Offset of next Sibling File
 +
|-
 +
|  0x8
 +
|  0x8
 +
|  Offset of File's Data
 +
|-
 +
|  0x10
 +
|  0x8
 +
|  Length of File's Data
 +
|-
 +
|  0x18
 +
|  0x4
 +
|  Offset of next File in the same Hash Table bucket
 +
|-
 +
|  0x1C
 +
|  0x4
 +
|  Name Length
 
|-
 
|-
−
|  0x60
 
 
|  0x20
 
|  0x20
−
|  Second block hash
+
|  Name Length (rounded up to multiple of 4)
 +
|  File Name (Unicode)
 
|}
 
|}
  
−
level1offset = align(0x5C, 8).
+
=== Hash Table Structure ===
−
level3offset = align(Level1offset, level1blocksize).
+
 
−
+
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 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>
 +
public static byte[] GetHashTableLength(uint numEntries)
 +
{
 +
uint count = numEntries;
 +
if (numEntries < 3)
 +
count = 3;
 +
else if (numEntries < 19)
 +
count |= 1;
 +
else
 +
{
 +
while (count % 2 == 0
 +
|| count % 3 == 0
 +
|| count % 5 == 0
 +
|| count % 7 == 0
 +
|| count % 11 == 0
 +
|| count % 13 == 0
 +
|| count % 17 == 0)
 +
{
 +
count++;
 +
}
 +
}
 +
return count;
 +
}
 +
</pre>
 +
 
 +
The hash function is based off directory/file name (byte array taken from Metadata entry) and Parent Directory's offset (C#):
 +
 
 +
<pre>
 +
public static uint CalcPathHash(byte[] Name, uint ParentOffset)
 +
{
 +
uint hash = ParentOffset ^ 123456789;
 +
for (int i = 0; i < Name.Length; i += 2)
 +
{
 +
hash = (hash >> 5) | (hash << 27);
 +
hash ^= (ushort)((Name[i]) | (Name[i + 1] << 8));
 +
}
 +
return hash;
 +
}
 +
</pre>
  
−
The block hash from the header hashes the second block at 0x2000.
+
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.

Latest revision as of 16:58, 24 January 2020

Overview[edit]

RomFS (or Read-Only Filesystem) is part of the NCCH format, and is used as external file storage.

RomFS can be used:

  • in conjunction with the ExeFS of a NCCH
  • to contain the game manual accessible from the Home Menu
  • or to contain game cartridge update data

(There may be more implementations in the future)

Format[edit]

The RomFS is wrapped inside a IVFC hash-tree container, and the actual data is structured like a node-based tree, starting at the root level directory node, moving down to other directory and file nodes. Each directory node has pointers to child directory nodes and siblings, together with a pointer to the first file node for that directory. Each file node has pointers to their next file node, together with information about the actual file data.

The RomFS IVFC hash-tree header is 0x5C bytes long and is structured as follows:

START SIZE DESCRIPTION
0x00 0x4 Magic "IVFC"
0x04 0x4 Magic number 0x10000
0x08 0x4 Master hash size
0x0C 0x8 Level 1 logical offset
0x14 0x8 Level 1 hashdata size
0x1C 0x4 Level 1 block size, in log2
0x20 0x4 Reserved
0x24 0x8 Level 2 logical offset
0x2C 0x8 Level 2 hashdata size
0x34 0x4 Level 2 block size, in log2.
0x38 0x4 Reserved
0x3C 0x8 Level 3 logical offset
0x44 0x8 Level 3 hashdata size
0x4C 0x4 Level 3 block size, in log2.
0x50 0x4 Reserved
0x54 0x4 Reserved
0x58 0x4 Optional info size.

Level 3 Format[edit]

The Level 3 partition of a RomFS consists of a header specifying offsets to four tables, followed by filedata (aligned to 16-bytes). Though their size varies by RomFS contents, the tables are always sequential and in the same order, as follows:

START SIZE DESCRIPTION
0x0 0x28 Header
0x28 Varies Directory HashKey Table
Varies Varies Directory Metadata Table
Varies Varies File HashKey Table
Varies Varies File Metadata Table
Varies Varies File Data

Level 3 Header Format[edit]

RomFS Header data is always 0x28 bytes long, and follows this layout (offsets are from the start of the header):

START SIZE DESCRIPTION
0x0 0x4 Header Length
0x4 0x4 Directory Hash Table Offset
0x8 0x4 Directory Hash Table Length
0xC 0x4 Directory Metadata Table Offset
0x10 0x4 Directory Metadata Table Length
0x14 0x4 File Hash Table Offset
0x18 0x4 File Hash Table Length
0x1C 0x4 File Metadata Table Offset
0x20 0x4 File Metadata Table Length
0x24 0x4 File Data Offset

Directory Metadata Structure[edit]

When a RomFS is built, directories are added recursively starting with the root. When a directory is added, all of its files are added to the File Metadata Table, then all of its subdirectories (if any), are added to the table. If any of the directory's subdirectories have their own subdirectories, the current directory's subdirectories are all added before the subdirectories' subdirectories are added.

A Metadata entry for a directory has the following structure (all values are initialized to 0xFFFFFFFF, and remain that way when unused):

START SIZE DESCRIPTION
0x0 0x4 Offset of Parent Directory (self if Root)
0x4 0x4 Offset of next Sibling Directory
0x8 0x4 Offset of first Child Directory (Subdirectory)
0xC 0x4 Offset of first File (in File Metadata Table)
0x10 0x4 Offset of next Directory in the same Hash Table bucket
0x14 0x4 Name Length
0x18 Name Length (rounded up to multiple of 4) Directory Name (Unicode)

File Metadata Structure[edit]

A Metadata entry for a file has the following structure (all values are initialized to 0xFFFFFFFF, and remain that way when unused):

START SIZE DESCRIPTION
0x0 0x4 Offset of Containing Directory (within Directory Metadata Table)
0x4 0x4 Offset of next Sibling File
0x8 0x8 Offset of File's Data
0x10 0x8 Length of File's Data
0x18 0x4 Offset of next File in the same Hash Table bucket
0x1C 0x4 Name Length
0x20 Name Length (rounded up to multiple of 4) File Name (Unicode)

Hash Table Structure[edit]

For both files and directories, a separate chaining hash table is created for quick lookup.

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#): 

		public static byte[] GetHashTableLength(uint numEntries)
		{
			uint count = numEntries;
			if (numEntries < 3)
				count = 3;
			else if (numEntries < 19)
				count |= 1;
			else
			{
				while (count % 2 == 0 
					|| count % 3 == 0 
					|| count % 5 == 0 
					|| count % 7 == 0 
					|| count % 11 == 0 
					|| count % 13 == 0 
					|| count % 17 == 0)
				{
					count++;
				}
			}
			return count;
		}

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

		public static uint CalcPathHash(byte[] Name, uint ParentOffset)
		{
			uint hash = ParentOffset ^ 123456789;
			for (int i = 0; i < Name.Length; i += 2)
			{
				hash = (hash >> 5) | (hash << 27);
				hash ^= (ushort)((Name[i]) | (Name[i + 1] << 8));
			}
			return hash;
		}

Each directory/file is put into the ith 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/w/index.php?title=RomFS&oldid=21155"