Here are the things I have or have done so far.
1) I have the ELF for the game.
2) I found the decompress routine inside the ELF.
3) I dumped the final decompressed binary from memory.
4) I have started to look at the code for the decompress.
What I have found so far reversing the decompress.
1) It reads data from the input buffer in 512 byte chunks.
2) It saves a window size of 0x20000 for the working dictionary.
3) It creates a sequence of numbers 0, 1, 1, 2, 2, 3, 3, 4, 4, ... 0xFF, 0xFF, 0x100.
4) It uses the same decompress routine over and over again.
5) The game literally calls the decompress routine once to get the first 4 bytes, which is the datasize of the rest of the stream decompressed.
6) Even though it only reads the first 4 bytes, it has already decompressed the data up to the block size 0x10000 (more on why it's not 0x20000 below).
7) Then it calls the same decompress routine in chunk sizes of 0x10000 until datasize is exhausted.
Not sure how you could go about sharing the code for the decompression routine, since the ELF file would not be able to be posted due to legal issues I would assume.
I have attached my test file and the decompressed version. I don't know enough about compression algorithms, so I'm posting it here in the hopes that someone will.
It seems to be a sliding window type of compression from what I've seen while debugging it.
Code: Select all
// decompress
void decompress(void *ctx, void *output, int length);
So the game calls:
Code: Select all
decompress(&ctx, &datasize, 0x04);
while (datasize > 0)
{
if (datasize > 0x10000)
chunksize = 0x10000;
else
chunksize = datasize;
decompress(&ctx, &output, chunksize);
datasize -= chunksize;
output += chunksize;
}
Inside the ctx it stores all of the info. Including input buffer location and input stream size. As well as the 0x20000 byte sliding window.
The pseudo code for the decompress is something like
Code: Select all
void decompress(void *ctx, void *output, int length)
{
if (!ctx->decoded)
decompress_block(ctx);
while (length > 0)
{
memcpy(output, ctx->window, ctx->window_size);
decompress_block(ctx);
length -= ctx->window_size;
}
memcpy(output, ctx->window, ctx->window_size);
}
It has some other stuff inside like updating pointers for input buffer stream read size, and such as well.
The decompress_block code will then read 0x200 bytes from the input buffer stream.
Then it creates the 0, 1, 1, 2, 2, table.
Then it does some stuff with the table and starts saving the results to a 0x4000 sized buffer.
As it finishes the 0x200 bytes, it will then re-read another 0x200 bytes, and saves the results, until this 0x4000 buffer is full.
After it's filled the 0x4000 buffer, it then increases the 0, 1, 1, 2, 2, table values by 1.
Then it reads the last entry in the 0, 1, 1, 2, 2 table, and saves one byte to the output table.
I noticed something peculiar too. It seems the data in the window is stored in big endian 16-bit mode as well.
As when it copies to the 0x20000 window, it skips the first 0x00 for every byte, and then saves only the next byte into the 0x20000 window.
So my decompressed.bin file is after it has stripped the 0x00's before every byte.
I'm sure this has to be an open source compression engine somewhere, but I do not know what it is.
I am posting this here, so that someone with more knowledge on compression algorithms could possibly see right away what this is with the info I have provided.
If you have any ideas on this, I am all ears.
-CMX