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:
- Find the last non equal character of both names and store the INDEX.
- 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.
- Otherwise compare each pair of characters until a difference is found.
- 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.
- 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); }