I'd definitely be interested in Cyb's observations. It does appear that the "sliding window" typical of LZS compression is coming into play with this graphics data. I don't think Ficedula referred to the method as a "sliding window," but I think that's what's described in his notes -- when the decompression algorithm reaches a section of compressed reference data, that reference data tells the algorithm to fish around in the uncompressed file up to that point and regurgitate a specific run of bytes that fall within the "window".
While tinkering with the compressed data and its expanded VRAM equivalent, I cobbled together a mock "freeze frame" of one of the portrait files in mid-decompression. Whatever decompression algorithm is used would encounter the reference bytes D4 03 08 05 at offset 0x1066 (0x1066 bytes had been decompressed up to this point), and these reference bytes magically transform into a BF followed by twenty-one 00s in the uncompressed file. Lo and behold, there are two instances earlier in the decompressed data of one BF followed by twenty-one 00s! Thus it is extremely likely that the reference bytes instruct the decompressor to re-create that previous run of bytes. It's a fascinating compression scheme.
For now I'll presume that the size of the "sliding window" is 4096 (0x1000) bytes as in Ficedula's FF7 notes. The next step will be to do some thought experiments to determine which earlier BF 00 00... is being targeted (both instances of these runs are within the sliding window, at addresses 0x326 and 0x863) and explore the possible ways in which bitwise operations could be used to get those four reference bytes to point at the target. How I enjoy logic games when there's a treasure at the end!
EDIT: Oooh, I just realized I should do the thought experiment with the BF 00 00... run that occurs just prior to the one I've been looking at. That way I'll know that it's definitely a duplicate of the first one starting out, so I can cut the theoretical work in half. This is why typing-while-thinking is important.
I will report my findings for everyone's amusement. Hopefully compression won't be as hard to work with as I had originally feared. The key is probably just having the "before decompression" and "after decompression" examples on hand to look at, although really experienced hackers can just trace the decompression algorithms in an emulator and be done with it.
SUPER EDIT: Ooh! Ooh! I've got part of it now! And more imporantly, I didn't even accidently double-post in my excitement!
Here's two situations to illustrate some of what's going on with the decompression algorithm.
Situation 1The decompression algorithm has worked its way to offset 0x1066, where it encounters the reference instruction D4
03 08 05. Now the algorithm reads those middle two bytes in little endian and goes 0x803 bytes back into the sliding window. Guess what's at offset (x1066 - x803) = x863? Yes! It's the BF 00 00... run we're looking for.
Situation 2Earlier, the decompression algorithm worked its way to offset 0x863, where it encountered the reference instruction D7
3D 05 29. 0x863 - 0x53D = 0x326, which is -- yee-haw! -- the offset of the first BF 00 00... run!
Wow, this is fun. Now to figure out what the first and last bytes in the reference instructions do, and why reference instructions may be odd or even lengths, and why they may even appear like straight-out RLE instructions at times. But I guess the use of a sliding window proves that this is an LZS derivative, eh?
Mega Edit: The last byte in a four-byte reference specifies the number of literal bytes following the reference, in essence pointing the algorithm to the next control byte. For example, 0x5 literal bytes follow the reference in Situation 1 above, and 0x29 literal bytes follow the reference in Situation 2.
This end-byte rule applies to all compression references, regardless of their length. The last byte
always tells the algorithm how many literal bytes come after the reference. Now to figure out what the first (the "control") byte does, exactly...
For one thing, I've discovered that a three-byte reference can act as follows: Control; NegativeOffset; #LiteralsFollowing. In other words, at times only one byte is needed to specify the negative offset for copying because that offset is less than x100. The control must serve the following functions, at the very least...
*Specify the number of bytes to regurgitate from earlier in the uncompressing file.
*Specify the number of bytes needed for the NegativeOffset.
This is where bitwise operations will probably come into play. Time to look at some 1s and 0s!
Another EDIT:Decomposing some control bytes into bits reveals the following pattern.
81:
10000001 The following backward reference is single (value less than or equal to 0xFF).
D7:
11010111 The following backward reference is a double (value greater than 0xFF).
D4:
11010100 The following backward reference is a double.
A0:
10100000 The following backward reference is single.
C1:
11000001 The following backward reference is a double.
9D:
10011101 The following backward reference is single.
41:
01000001 The following reference is a straight-out RLE reference
42:
01000010 The following reference is a straight-out RLE reference
The only thing that really stands out to me across the examples are the leftmost two bits.
Question: I think these would actually be the *final* two bits fed into the decompression algorithm if the byte is being read in Little Endian order. Is that correct? If so, we might have the following as decompression "opcodes" of sorts, if this sort of thing is possible:
01: LZS decompression, next backward reference is a single byte.
11: LZS decompression, next bakcward reference is a pair of bytes.
10: RLE decompression, next reference is the byte to be repeated.
The number of bytes to copy, either for LZS or RLE decompression, must also be specified by the control byte. There's definitely a pattern across the control bytes for this as well,
but the fact that 0xD7 and 0xD4 both specify a copied run of (Dec 22, x16) bytes throws things off kilter for the time being. Other than the relative positioning of the copied runs, nothing differs between the runs copied by these control bytes (these are the BF 00... runs). The control bytes should be identical, and yet they aren't.Ha! Scratch that. The control byte 0xD7 in Situation 2 above corresponds to a run of one BF and dec 24 zero bytes. The control byte 0xD4 in Situation 1 above corresponds to a run of one BF and dec 21 zero bytes. Looks like the pattern holds!
I think I'm seriously close to fully cracking this decompression algorithm.
Anyone happen to know of any open-source LZS decompressors? I'm wondering if I could simply modify existing code to handle the decompression at hand. One problem is that I've never seen LZS decompression being used side-by-side with RLE compression, so I'll have to figure out how to add that. Or maybe I'll just research python decompression, since python is the first programming language I intend to learn. Wish me luck!
