ToD and LZSS compression

[coreyh2]

I've been reading through the Tales of Dagur source code to help learn NDS homebrew programming. I have a few questions about the compression in ToD. I've read that ToD isn’t playable on a emulator because it “uses LZ77 compression which none of the emulators support”. There is a example that comes with libnds called 16bit_color_bmp that uses LZ77 that runs in no$gba. So I'm wondering what the whole reason for ToD not working in a emulator.

The 16bit_color_bmp uses grit instead of gfx2gba.exe and GBACrusher.exe. Also there is this code from ToD in background.cpp that I'm unable to understand.

Code: Select all

int getSize(uint8 * source, uint16 * dest, uint32 r2)
{
       u32 size = *((u32*)source) >> 8;
       return (size<<8) | 16;
}

The 16bit_color_bmp example has this code instead from decompress.c from libnds

Code: Select all

int getHeader(uint8 *source, uint16 *dest, uint32 arg) {
  return *(uint32*)source;
}

They are both put into the decStream structure that swiDecompressLZSSVram uses in the first position.

Code: Select all

int getHeader(uint8 *source, uint16 *dest, uint32 arg) {
   return *(uint32*)source;
}

uint8 readByte(uint8 *source) {
   return *source;
}
TDecompressionStream decomStream = {
   getHeader,
   0,
   readByte
};

swiDecompressLZSSVram((void*)data, (void*)dst, 0, &decomStream);

GetSize is where getHeader is.


Could you explain what those shifts and OR are doing in getSize? I haven't done much low level memory programming so they are beyond me.

The reason I'm asking about this is I plan to make something in a rpg style and was hoping to make it work in a emulator so that people without a flash cart could play it. I'm assuming compression is important in a game with many sprites. I don't completely understand the memory limits yet.

[vuurrobin]

the compression routines are stored in the nds bootcode. because its illegal to distribute the bootcode, most (all?) emulators don't have them by default but instead give the option to let the user dump/download the code. if you can run it on no$gba, then that means you have the bootcode.

as for ToD source code, the code is fairly old so it probably does things that were later included or changed in libnds. its better to just follow the examples.

[coreyh2]

thanks for the help.

Liran Nuna got back to me today and I have the answer.

ToD uses a very unique trick to decompress data assets directly to VRAM.

There are two BIOS decompression routines, both using the LZ77 algorithm with 4096 bytes sized windows, the main difference is the unpacking.
One of the BIOS calls unpacks in 8bits - since the VRAM's memory bus is 16bit wide, it is impossible to extract data to VRAM directly - that's why there's another call, which extracts either 16bit or 32bit according to your preference.

Many emulators do not emulate the VRAM safe method because no game uses it except ToD
I know that one revision of dualis had experimental support, but dualis is very very old by now...

If you want to have the most compatible code, you should extract to RAM and perform a copy to VRAM using either DMA or the CPU. The normal decompression routine is the same except for the header.
The bitwise shifts are infact that header, if you compose it in a special way, the BIOS performs a different window size decompression.