Falcom Compression Tools

var prgmr == true;
var i = int;
for (i = 0; i < prgmr.knwldge; i++) {
prgrmr + i";
}
Post Reply
flamethrower
Programmer
Posts: 790
Joined: Mon Mar 09, 2015 3:03 pm

Falcom Compression Tools

Post by flamethrower » Wed Aug 31, 2016 11:35 am

These tools are copied from the C version written by EsperKnight.
Developed by me is the full compression implementation extended from EsperKnight's code which was a partial implementation.
Here's the v2 of Falcom decompress: http://pastebin.com/NJcrmM3d
I added a function decompress_FALCOM2_1 to handle chains of FALCOM2 that's found in Sorcerian Forever.
I added comments to the code for function decompress.

Here is the Falcom compression tool: http://pastebin.com/hE5f3i6L
Implemented right now is copy byte and short look-back (window size 0xFF). I will see if I can implement long look-back (window size 0x1FFF) which should give better performance.
--------------------------------
Efficiency:
To encode match of size 2 with short look-back (distance 0xFF or less) it takes 1 byte and 3 bits, so that's great.
To encode match of size 2 with long look-back (distance > 0xFF and < 0x2000) it takes 1 byte and 8 bits. This is still a good deal because to encode two raw bytes it takes 2 bytes and 2 bits.
To encode a repeating sequence of size 3:
--This is done by encoding a raw byte (1 byte and 1 bit)
--Then encoding a repeating sequence of length 2 with a look-back of 1 (1 byte and 3 bits)
Total: 2 bytes and 4 bits. So this is a good deal. Encoding a repeating sequence of two bytes isn't worth it.
A match (long look-back) of size 3 requires 1 byte and 9 bits; short look-back is even better than this. So this is a really good deal. Still, it's not at least 8 bits better. So for sequences of the same length, match should be prioritized. Otherwise, the longest sequence (that's over the minimum threshold) should be used.
---------------------------------
The Falcom encoder is blind. It will happily encode a sequence and produce an output greater in size than the input (even excluding header data). This is most common with palette data.
---------------------------------
Program structure:
A function called compress that manages overall flow of the program
A function called updateflags which manages the flags that tell the decompression routine what to do
--updateflags is a "generator object" which is a special Python thing that's sort of like a function, you can google it. I heard about it before and it seemed appropriate for this application.
A function called find_match which searches for matches
A function called find_repeat which searches for repeating sequences
A function called encode_match which does what the name says
A function called encode_repeat which does what the name says
The main program, compress, handles deciding which encoder to use and also encoding raw bytes.
-------------------------------------
For very big files, mine compresses better than Falcom's probably because it flushes the dictionary less often. I got file that's 97.3% of the size of Falcom's on mp_0110.mpp (one of the biggest files).

For "our" files, they are generally bigger than Falcom's uncompressed because they have English text in them. Compressed, they're bigger too, by a little bit. I need to test the compressed one in-game.

Tested in game and no issues.

flamethrower
Programmer
Posts: 790
Joined: Mon Mar 09, 2015 3:03 pm

Re: Falcom Compression Tools

Post by flamethrower » Sat Sep 03, 2016 7:57 am


Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest