242
edits
Changes
Jump to navigation
Jump to search
Line 466:
Line 466: + + + + + + + + + + + + + + + + + + + + + + + +
Merge hash table here
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.
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(
char 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 ==