BFEVFL: Difference between revisions

From ZeldaMods (Breath of the Wild)
Jump to navigation Jump to search
imported>Leoetlino
No edit summary
imported>Leoetlino
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.
A dictionary is 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.
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.

Revision as of 18:41, 12 September 2018

bfevfl is a binary file format for event flows.

Structures

bfevfl is a little endian format, so values are stored in little endian even on Wii U.

bfevfl uses pointers very heavily to refer to strings, to other sections, etc. All pointers are always 64 bit long -- since the same format is used on the Switch which is a 64 bit platform. They must be present in the #Relocation table if the file is to be loaded correctly by the official bfevfl code.

As a direct consequence, most sections don't have any fixed order. Therefore, this article will only document the data structures and mention the order Nintendo places sections in. For more details, it is recommended to look at the evfl library directly.

Another consequence is that sections must be aligned to 8-byte boundaries in most cases to avoid unaligned memory accesses (this is not as important for strings).

Header

Offset Type Description
0x0 char[8] Magic ("BFEVFL\x00\x00")
0x8 u16 Version (0x0300)
0xa u8 Unknown (must be zero)
0xb u8 Unknown
0xc u16 Byte order mark
0xe u8 Alignment (to get the actual value: 1 << raw_value)
0xf u8 Unknown
0x10 u32 File name offset
0x14 u16 Is relocated flag (set in memory)
0x16 u16 First block offset
0x18 u32 Relocation table offset
0x1c u32 File size
0x20 u16 Number of flowcharts
0x22 u16 Number of timelines
0x24 u32 Padding
0x28 Flowchart* Flowchart (nullptr if no flowchart)
0x30 Dictionary* Flowchart name dictionary
0x38 Timeline* Timeline (nullptr if no timeline)
0x40 Dictionary* Timeline name dictionary

Relocation table

Offset Type Description
0x0 char[4] Magic ("RELT")
0x4 u32 Offset to relocation table start
0x8 u32 Number of sections (almost always 1)
0xc u32 Padding
0x10 Section[num_sections] Sections

Relocation table section

Offset Type Description
0x0 void* Alternative base offset (unused by Nintendo)
0x8 u32 Used to calculate the base pointer if an alternative base offset is used
0xc u32 Data end offset (before alignment)
0x10 u32 Number of entries to skip
0x14 u32 Number of entries (includes skipped entries)
0x18 Entry[num_entries] Entries

Relocation table entry

Offset Type Description
0x0 u32 Offset to pointers to relocate
0x4 u32 Bit field that determines which pointers need to be relocated (up to 32 contiguous pointers starting from the listed offset)

String pool

The string pool starts with the STR magic and contains 2-byte aligned strings. The magic is not checked at all since strings are directly referred to using pointers.

All strings in the pool are Pascal string, i.e. length-prefixed strings. The length is an unsigned 16 bit integer. Strings are stored in reverse order of their binary representation.

Dictionary

A dictionary is 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.

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

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:

def get_compact_representation(bit_idx: int) -> int:
    byte_idx = bit_idx // 8
    return (byte_idx << 3) | (bit_idx - 8*byte_idx)

Container

Flowchart

Timeline

Section order

File

  • Header (0x48 bytes)
  • Flowchart* array if it exists
  • Flowchart dictionary (always)
  • Timeline* array if it exists
  • Timeline dictionary (always)
  • Timeline
  • Flowchart
  • String pool (STR )
  • Relocation table (RELT)

Timeline

Flowchart

  • Flowchart header
  • Actors
  • Argument name is put in the string pool.
  • Events
  • Entry point dictionary
  • Entry points
  • Event param containers, fork structs, etc. (in order)
  • Actor param containers, string pointer arrays (in order)
  • Entry point extra data
  • Sub flow event index arrays are written here
  • ptr_x10 data may be written here? (ptr_x10 has always been a nullptr in files that have been checked by leoetlino.)
  • The size for each entry point is sizeof(event_idx_array) rounded up to the nearest multiple of 8 + 0x18 bytes.

Container

  • Container header (variable size)
  • Container dictionary
  • Container items (+ values)

Tools

  • evfl: Python library for parsing and writing event flows
  • EventEditor: graphical editor for event flows