Reverse Engineering Quake3-based formats

[snake-biscuits]

I usually get started hunting for .bsp lump loads in the main .exe of whateve game

An easy way to locate relevant functions is to search for "CM_Load" strings
CM_Load functions are defined in qcommon/cm_load.c
They contain multiple sizeof etc. checks against lump data, naming the function in any errors reported; e.g:

if (l->filelen % sizeof(*in)) { Com_Error(ERR_DROP, "CMod_LoadSubmodels: funny lump size"); }
count = l->filelen / sizeof(*in);
if (count < 1) { Com_Error(ERR_DROP, "Map with no models"); }
cm.cmodels = Hunk_Alloc(count * sizeof(*cm.cmodels), h_high);
cm.numSubModels = count;
if (count > MAX_SUBMODELS) { Com_Error(ERR_DROP, "MAX_SUBMODELS exceeded"); }

As you can see, we also occasionally get bounds checking on engine MAX limits
These can be helpful for tracing which lump index other lumps
This can also be implied by the order in which lumps are loaded

Working out the order of lump names can be a little trickier, some CM_Load functions are fed lump_t headers
The Titanfalls take lump indices as arguments

Yes, Titanfall comes from a fork of the Source Engine
But Respawn seem to have brought the engine closer to their familiar Quake 3 roots

[snake-biscuits]

TODO: screenshots of a CM_Load function in ida, showing how to derive lump length from the asm

ASM sample

movsxd  r9,  LUMP_size
mov     rax, 0xAAAAAAAAAAAAAAAB  ; magic 1 / (1.5)
mul     r9                       ; rdx:rax = rax * r9
                                 ; rdx = 1 / (1.5) * r9 = r9 / (1.5)
                                 ; rax = remainder
shr     rdx, 3                   ; 1.5 * (2 ** 3) = 12
lea     rcx, rdx * 3
shl     rcx, 2
cmp     r9 , rcx
jz      valid_lump_size

Checking math in python

To use this, I fed in a range of ints and found values where r9 == rcx

def is_valid(LUMP_size: int) -> (int, int):
    r9, rax = LUMP_size, 0xAAAAAAAAAAAAAAAB
    rdxrax = rax * r9
    rdx, rax = rdxrax >> 64, rdxrax & ((2 ** 64) - 1)
    rdx >>= 3
    rcx = rdx * 12
    return r9, rcx


fraction = lambda h: sum([ 1 / (1 << (i + 1)) for i, x in enumerate(f"{h:032b}") if x != "0"])

Common integer division fraction constants

The hexadecimal fraction always rounds up, but otherwise is recurring

0x47AE147AE147AE15 = 0.560000 = 14 / 25 (    56 / 100   )
0x97B425ED097B425F = 0.592592 = 16 / 27 (   592 / 999   )
0x2492492492492493 = 0.571428 =  4 / 7  (571428 / 999999)
0xAAAAAAAAAAAAAAAB = 0.666666 =  2 / 3  (     6 / 9     )
0x2E8BA2E8BA2E8BA3 = 0.727272 =  8 / 11 (    72 / 99    )
0xCCCCCCCCCCCCCCCD = 0.800000 =  8 / 10 (     8 / 10    )

NOTE: turning recurring decimals into fractions (XXX/999 etc.) is a very useful skill
-- same goes for reducing fractions

4 / 7 = 0.571428 | 999999 / 7 = 142857 | 1 / 7 = 0.142857

Third & Sevenths are crazy (or just prime fractions in general)

[snake-biscuits]

cmp     r9 , rcx
jz      valid_lump_size

This checks r9 == rcx, jz jumps past the call to the error function (if(False) { Error("...") } /* go here */)
r9 holds the original lump size, while rcx holds the largest valid lump size less than r9
The fancy integer division trick the compiler is doing here also stores the remainder in a register, very neat