242
edits
Changes
Jump to navigation
Jump to search
mLine 15:
Line 15: − + + + Line 58:
Line 60: + + Line 73:
Line 77: − + Line 93:
Line 97: − + Line 121:
Line 125: − + Line 173:
Line 177: − + + Line 187:
Line 192: − + Line 220:
Line 225: + + + + + − + Line 317:
Line 327: + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Line 366:
Line 548: − + + +
→Directory Hash Table & File Hash Table
== Layout Variants ==
== Layout Variants ==
Four variants of the file system layout has been identified. A summary diagram can be found here: [https://github.com/wwylele/3ds-save-tool/raw/master/inner-fat.png]
Four variants of the file system layout has been identified. A summary diagram:
[[File:Inner-fat.png]]
=== Savegame, <code>duplicate data = true</code> ===
=== Savegame, <code>duplicate data = true</code> ===
** file entry table as well
** file entry table as well
** normal subfiles are NOT in the data region. They are in their DIFF containers instead.
** normal subfiles are NOT in the data region. They are in their DIFF containers instead.
The special file <code>00000000/00000001</code> is configured as external IVFC level 4 disabled, and all other device files are configured as it enabled.
=== Title database ===
=== Title database ===
== Filesystem Header ==
== Filesystem Header ==
Offsets listed in the table below are all related to the beginning of the header. This is especially important for title database, as the offsets doesn't count the pre header there.
Offsets listed in the table below are all relative to the beginning of the header, while all "starting block index" are relative to the beginning of data region. This is especially important for title database, as the offsets doesn't count the pre header.
{| class="wikitable" border="1"
{| class="wikitable" border="1"
! Offset
! Offset
| 0x10
| 0x10
| 8
| 8
| Filesystem image size in blocks
| Filesystem image size in blocks (including pre header for title database)
|-
|-
| 0x18
| 0x18
| 0x30
| 0x30
| 4
| 4
| D of most recently mounted Extdata image
| ID of most recently mounted Extdata image
|-
|-
| 0x34
| 0x34
| Y + 0x30
| Y + 0x30
| 4
| 4
| File allocation table entry count
| File allocation table entry count
(excluding the leading 0th entry. See below)
|-
|-
| Y + 0x34
| Y + 0x34
| 4
| 4
| Data region block count
| Data region block count
(= number of file allocation table entries excluding the leading 0th entry. See below)
(= File allocation table entry count)
|-
|-
| Y + 0x44
| Y + 0x44
| Padding
| Padding
|}
|}
* For savegames, the file/directory bucket count & maximum count are specified by the parameters of [[FS:FormatSaveData]] or [[FS:CreateSystemSaveData]].
* For extdata, the maximum file/directory count are specified by the parameters of [[FS:CreateExtSaveData]]. The bucket count is likely calculated by the system.
* Directory & file entry tables are allocated in the data region as if they are two normal files (except for savegame <code>duplicate data = false</code> layout). However, only continuous allocation has been observed, so directly reading block_count * block_size bytes from data_region + starting_block_index * block_size should be safe.
* For title database (except for ticket), the range specified for data region seems overflow the file end by 0x80 bytes, which is exactly the size of the pre header. This makes it as if the data region offset should be relative to the pre header instead of the BDRI header. However, further investigation on the directory/file table allocated inside the data region shows that the data region offset is indeed relative to the BDRI header. It might be a bug in 3DS that the title database files miss 0x80-byte space at the end.
== Directory Entry Table ==
== Directory Entry Table ==
The directory entry table is an array of the entry type shown below. It describes the directory hierarchy of the file system. There are two variants of the directory entry type.
The directory entry table is an array of the entry type shown below. It describes the directory hierarchy of the file system. There are two variants of the directory entry type, and a dummy entry type.
=== Savegame/Extdata Variant===
=== Savegame/Extdata Variant===
The 0-th entry of the array is always a dummy entry, which functions as the head of the dummy entry linked list. The 1-st entry of the array is always the root. Therefore maximum entry count is two more than maximum directory count. Dummy entries are left there when deleting directories, and reserved for future use.
The 0-th entry of the array is always a dummy entry, which functions as the head of the dummy entry linked list. The 1-st entry of the array is always the root. Therefore maximum entry count is two more than maximum directory count. Dummy entries are left there when deleting directories, and reserved for future use.
== File Entry Table ==
The file entry table is an array of the entry type shown below. It contains information for each file. There are three variants of the file entry type, and a dummy entry type.
=== Savegame Variant ===
{| class="wikitable" border="1"
! Offset
! Length
! Description
|-
| 0x00
| 4
| Parent directory index in directory entry table
|-
| 0x04
| 16
| ASCII file name
|-
| 0x14
| 4
| Next sibling file index. 0 if this is the last one
|-
| 0x18
| 4
| Padding
|-
| 0x1C
| 4
| First block index in data region. 0x80000000 if the file is just created and has no data.
|-
| 0x20
| 8
| File Size
|-
| 0x28
| 4
| Padding?
|-
| 0x2C
| 4
| Index of the next file in the same hash table bucket. 0 if this is the last one
|}
=== Extdata Variant ===
{| class="wikitable" border="1"
! Offset
! Length
! Description
|-
| 0x00
| 4
| Parent directory index in directory entry table
|-
| 0x04
| 16
| ASCII file name
|-
| 0x14
| 4
| Next sibling file index. 0 if this is the last one
|-
| 0x18
| 4
| Padding
|-
| 0x1C
| 4
| Always 0x80000000
|-
| 0x20
| 8
| Unique identifier. See [[Extdata]]
|-
| 0x28
| 4
| Padding?
|-
| 0x2C
| 4
| Index of the next file in the same hash table bucket. 0 if this is the last one
|}
=== Title database Variant ===
{| class="wikitable" border="1"
! Offset
! Length
! Description
|-
| 0x00
| 4
| Parent directory index in directory entry table
|-
| 0x04
| 8
| Title ID
|-
| 0x0C
| 4
| Next sibling file index. 0 if this is the last one
|-
| 0x10
| 4
| Padding
|-
| 0x14
| 4
| First block index in data region.
|-
| 0x18
| 8
| File size
|-
| 0x20
| 8
| Padding?
|-
| 0x28
| 4
| Index of the next file in the same hash table bucket. 0 if this is the last one
|}
=== Dummy Entry ===
Like directory entry table, file entry table also has some dummy entries:
{| class="wikitable" border="1"
! Offset
! Length
! Description
|-
| 0x00
| 4
| Current total entry count
|-
| 0x04
| 4
| Maximum entry count = maximum file count + 1
|-
| 0x08
| 36/32
| Padding / All zero
|-
| 0x2C/0x28
| 4
| Index of the next dummy entry. 0 if this is the last one
|}
The 0-th entry of the array is always a dummy entry, which functions as the head of the dummy entry linked list. Therefore maximum entry count is one more than maximum file count. Dummy entries are left there when deleting files, and reserved for future use.
== Directory Hash Table & File Hash Table ==
This is a u32 array of size = bucket count, each of which is an index to the directory / file entry table. The directory / file name is hashed and its entry index is put to the corresponding bucket. If there is already a directory/file entry in the bucket, then it appends to the linked list formed by <code>Index of the next directory/file in the same hash table bucket</code> field in the directory/file entry table. i.e. this is a hash table using separate chaining with linked lists
The hash function takes the parent index and the ASCII name (or title ID for title database) as key. The function is equivalent to
<pre>uint32_t GetBucket(
uint8_t name[16 or 8], // For savegame/extdata, this takes all 16 bytes including trailing zeros; For title database, this is the 8-byte title ID
uint32_t parent_dir_index,
uint32_t bucket_count
) {
uint32_t hash = parent_dir_index ^ 0x091A2B3C;
for (int i = 0; i < 4 or 2; ++i) {
hash = (hash >> 1) | (hash << 31);
hash ^= (uint32_t)name[i * 4]
hash ^= (uint32_t)name[i * 4 + 1] << 8
hash ^= (uint32_t)name[i * 4 + 2] << 16
hash ^= (uint32_t)name[i * 4 + 3] << 24
}
return hash % bucket_count;
}
</pre>
== File Allocation Table ==
== File Allocation Table ==
All free blocks that are not allocated to any files also form a node chain in the allocation table. The head index of this "free chain" is recorded in <code>FAT[0].Index_V</code>. Other fields of <code>FAT[0]</code> are all zero
All free blocks that are not allocated to any files also form a node chain in the allocation table. The head index of this "free chain" is recorded in <code>FAT[0].Index_V</code>. Other fields of <code>FAT[0]</code> are all zero
Here is an example: [https://raw.githubusercontent.com/wwylele/3ds-save-tool/master/disa-fat.png]
Here is an example:
[[File:Disa-fat.png]]
For extdata, because only two "files" (directory and file entry tables) are allocated in the data region, and their size never changes once the extdata is created, they are guaranteed continuous in the data region, and the FAT degenerates to two big nodes. Therefore, instead of going through FAT, the offset and size of directory / file entry table can be found directly by offset = entry_table_starting block * data_region_block_size + data_region_offset and size = entry_table_block_count * data_region_block_size.
For extdata, because only two "files" (directory and file entry tables) are allocated in the data region, and their size never changes once the extdata is created, they are guaranteed continuous in the data region, and the FAT degenerates to two big nodes. Therefore, instead of going through FAT, the offset and size of directory / file entry table can be found directly by offset = entry_table_starting block * data_region_block_size + data_region_offset and size = entry_table_block_count * data_region_block_size.