BFEVFL: Difference between revisions
Jump to navigation
Jump to search
no edit summary
imported>Leoetlino No edit summary |
imported>Leoetlino No edit summary |
||
| Line 100: | Line 100: | ||
=== Dictionary === | === Dictionary === | ||
{{ | Dictionaries are a data structure that is used to quickly look up the index of an element based on its name. Thus, they are always used in conjunction with an array of elements. However, the way the dictionary and the array are associated depends on the structure. | ||
BFEVFL dictionaries are essentially binary radix trees (also called PATRICIA trees or tries). The structure contains a binary search tree and bit-by-bit comparisons of strings are done to navigate through it. It is extremely similar to the Wii U bfres "index group" structure, but with significant changes to the algorithm. The Switch bfres format shares the same algorithm. | |||
{|class="wikitable" | |||
! Offset !! Type !! Description | |||
|- | |||
| 0x0 || char[4] || Magic ("DIC ") | |||
|- | |||
| 0x4 || u32 || Number of entries (ignoring root entry) | |||
|- | |||
| 0x8 || Entry || Root entry | |||
|- | |||
| 0x18 || Entry[num_entries] || Entries | |||
|} | |||
==== Dictionary entry ==== | |||
{|class="wikitable" | |||
! Offset !! Type !! Description | |||
|- | |||
| 0x0 || u32 || Compact representation of bit index | |||
|- | |||
| 0x4 || u16 || Next index if bit is 0 | |||
|- | |||
| 0x6 || u16 || Next index if bit is 1 | |||
|- | |||
| 0x8 || PascalString* || Name | |||
|} | |||
The compact representation of the bit index has two parts: | |||
* Bits 3-7: index of the byte that should be checked | |||
* Bits 0-2: index of the bit in that byte | |||
A bit index can be translated to its compact representation using: | |||
<syntaxhighlight lang="python"> | |||
def get_compact_representation(bit_idx: int) -> int: | |||
byte_idx = bit_idx // 8 | |||
return (byte_idx << 3) | (bit_idx - 8*byte_idx) | |||
</syntaxhighlight> | |||
=== Container === | === Container === | ||