BRRES Index Group (File Format)

Overview

The BRRES Index Group is a data structure that occurs very often within BRRES files and sections of BRRES. It can be used to point to more BRRES Index Groups in order to allow folder structure, as in the root section. It has a 0x08 byte header, as follows.

Offset	Type	Description
0x00	UInt32	Length of group in bytes.
0x04	UInt32	Number in group.

This is then followed by a number of entries equal to the number in the header. The first entry is never an actual data entry, but instead a reference point. Each entry is a 0x10 byte structure as follows. All offsets are relative to the start of the group.

Offset	Type	Description
0x00	UInt16	Entry ID. See below.
0x02	UInt16	Flag. Always 0?
0x04	UInt16	Left index. See below.
0x06	UInt16	Right index. See below.
0x08	Int32	Name pointer. Offset to the name of this entry in the BRRES name table. The length of this string is 4 bytes before this offset.
0x0c	Int32	Data pointer. Offset to the data of this entry.

The ID of each entry is not a unique number, but is calculated from the name comparing it to another name (see below) and used to search for a given entry. The entries form a binary search tree, with the first entry being the root. The left and right indicies describe this tree.

Calculation of the ID

The ID is calculated by comparing a filename (subject) to an other filename (object) using the following algorithm:

1. Find the last non equal character of both names and store the INDEX.
   1. If the length of the subject filename is greater than the length of the object filename, INDEX is the length of the subject filename minus 1.
   2. Otherwise compare each pair of characters until a difference is found.
2. Now compare both characters of position INDEX and find the highest bit that is not equal. If INDEX exceeds the length of object, assume character value 0. Store the bit index (7 for 0x80 .. 0 for 0x01) as BITNUM.
3. Calculate: ID := INDEX << 3 | BITNUM

Initially the subject filename is compared with the the root filename, which is always empty. If an ID with the same value is found while walking through the tree, then a new ID is calculated using the other filename as object.

GNU C example

This example is taken from Wiimms SZS Tools, file lib.szs.c:

typedef const char *  ccp;
typedef unsigned int  uint;
typedef unsigned char u8;
typedef u_int16_t     u16;

static u16 get_highest_bit ( u8 val )
{
    // 2do: use a lookup table if this is time critical
    u16 i;
    for ( i = 7; i > 0 && !( val & 0x80 ); i--, val <<= 1 )
        ;
    return i;
}

static u16 calc_brres_id
(
    ccp  object_name,
    uint object_len,
    ccp  subject_name,
    uint subject_len
)
{
    if ( object_len < subject_len )
        return subject_len - 1 << 3 | get_highest_bit(subject_name[subject_len-1]);

    while ( subject_len-- > 0 )
    {
        const u8 ch = object_name[subject_len] ^ subject_name[subject_len];
        if (ch)
            return subject_len << 3 | get_highest_bit(ch);
    }

    return ~(u16)0;
}

Calculation of left and right index

The left and right indexes are calculated with an iterative algorithm. Each element is inserted into the tree by traversing the virtual tree. As described above, the ID represents the last different bit of 2 strings. The status of this last bit decides if following the left (bit is cleared) or the right (bit is set) sub tree. For details see the following GNU C example.

GNU C example

This example is taken from Wiimms SZS Tools, file lib.szs.c:

typedef struct brres_info_t
{
    u16  id;          // id
    u16  left_idx;    // left index
    u16  right_idx;   // right index
    ccp  name;        // pointer to name
    uint nlen;        // lenght of name

} brres_info_t;

static bool get_brres_id_bit
(
    brres_info_t * info,
    u16 id
)
{
    ASSERT(info);
    const uint char_idx = id >> 3;
    return char_idx < info->nlen
        && info->name[char_idx] >> ( id & 7 ) & 1;
}

static void calc_brres_entry
(
    brres_info_t  * info,
    uint          entry_idx
)
{
    ASSERT(info);

    // setup 'entry' : item to insert
    brres_info_t * entry = info + entry_idx;
    entry->id = calc_brres_id(0,0,entry->name,entry->nlen);
    entry->left_idx = entry->right_idx = entry_idx;

    // setup 'prev' : the previuos 'current' item
    brres_info_t * prev = info;

    // setup 'current' : the current item whule walking through the tree
    uint current_idx = prev->left_idx;
    brres_info_t * current = info + current_idx;

    // last direction
    bool is_right = false;

    while ( entry->id <= current->id && current->id < prev->id )
    {
        if ( entry->id == current->id )
        {
            // calculate a new entry id
            entry->id = calc_brres_id( current->name, current->nlen,
                                      entry->name, entry->nlen );
            if (get_brres_id_bit(current,entry->id))
            {
                entry->left_idx  = entry_idx;
                entry->right_idx = current_idx;
            }
            else
            {
                entry->left_idx  = current_idx;
                entry->right_idx = entry_idx;
            }
        }

        prev = current;

        is_right = get_brres_id_bit(entry,current->id);
        current_idx = is_right ? current->right_idx : current->left_idx;
        current = info + current_idx;
    }

    if ( current->nlen == entry->nlen && get_brres_id_bit(current,entry->id) )
        entry->right_idx = current_idx;
    else
        entry->left_idx = current_idx;

    if (is_right)
        prev->right_idx = entry_idx;
    else
        prev->left_idx = entry_idx;
}

static void calc_brres_entries
(
    brres_info_t   * info,
    uint           n_entries
)
{
    ASSERT( info );
    ASSERT( n_entries > 0 );

    // setup root entry
    info->id = 0xffff;
    info->left_idx = info->right_idx = 0;

    int idx;
    for ( idx = 0; idx <= n_entries; idx++ )
	calc_brres_entry(info,idx);
}

All about BRRES files

BRRES file — Index Group — Sub Files

CHR0 — CLR0 — MDL0 — PAT0 — SCN0 — SHP0 — SRT0 — TEX0