Hacking Homebrew ROM Hack Project Can anyone give be some details about LZ11 compression?

[SolatoroboHacking]

Hello everyone!

I am beginning the long process of reverse engineering the various inner workings of Solatorobo: Red the Hunter. I'm very new to the field of DS ROM hacking, and am in the early days of this project, so the first thing I thought I would do to get my feet wet would be to write a custom extraction utility for the game's proprietary asset packages, known as CCB files. These files have a basic header and a file table containing data about the various attributes of the file, and finally compressed data. So far, I've spotted two kinds of compression being used within these CCB files, LZ11 and RLUncomp. I'm not worrying about RLUncomp for the moment, I'm just focusing on LZ11.

One of the strangest things about these CCB files is that the data within them is compressed twice. It goes through one pass of LZ11 compression and produces output exactly like what you would see from a regular LZ11 compression utility. The second pass is the strange one. The data is further compressed, but doesn't actually get any smaller. In a way, it's basically just being obfuscated. An LZ11 decoder will decode both passes just fine, and you wind up right back at the original uncompressed data, but I can't figure out a good reason why a second pass of compression would not compress the data further.

The only documentation I can find on LZ11 compression are some decompression utilities, one known as LZX from Github user PeterLemon (I can't post links due to being a new user, sorry) and one in the DSDecmp utility. However, these resources only provide some header information, not very well documented C code, and a few other bits and pieces.

Can anyone either provide or point me to some more detailed information about the LZ11 compression and decompression algorithms? One of the main reasons I'm writing this tool is that Console Tool is currently the only tool that supports reading CCB files, and even then, it can only extract them as far as I can tell. I want to figure out how the CCB format works so that I can reconstruct new CCB files and reinsert them into the ROM. Also, Console Tool does not allow batch extraction, which is going to be a huge pain if large numbers of assets need to be modified.

TL;DR: Does anyone know how LZ11 compression/decompression actually works?

Thanks everyone!

 

[plasturion]

Here's more about LZ10 and LZ11 DS files comparision, how are tagged in header and decompression algorithm.
I reccomend to check CUE's codec pack. LZ11 is known as LZX and there's a source code of this compressor/decompressor. Wait It's a peter lemon's you mentioned before... right but it's more than enough to know, also provides compression. Not explained best, so seems it's need to sit on this code and figure out with some patience. Or someone else can write here some tutor, but do you really need that? Good luck.
As for how the compression works in general, i guess this dude has a talent in explaining things:

 

[FAST6191]

Other than what you have Plasturion sent the same things I would have (you can have http://members.iinet.net.au/~freeaxs/gbacomp/ and https://ece.uwaterloo.ca/~ece611/LempelZiv.pdf if you want to round out my usual collection of links), what I am more here to say is double compression is very rare (makes some more sense in older systems with simpler algorithms but DS LZ is potent enough to not really benefit from anything there -- uncompress and then unfilter sure but double the same compression not so much) and if I was betting on something I would say fault of the developer with someone probably trying to be helpful when making their files, forgetting to leave out a switch in a build script, forgetting to leave out a line when they realised compression was a feature of some packing tool or similar.

Though on a related note I did see there was a super customisable compression tool released the other day so sharing the good word
https://www.romhacking.net/utilities/1770/

 

[SolatoroboHacking]

Thanks for the links, you guys! Yeah, PeterLemon's tools work perfectly, but for my purposes, I'd have to either treat them as a black box and filter my data around them, or reverse engineer the compression algorithm from those. I figured there was some better documentation out there somewhere that I just wasn't finding. That Python source looks great!

With regards to the double compression, I have no idea why it was done, but no one seems to know why the devs created the CCB format in the first place, so it's very possible that there was some incompetence at play here. The data is definitely compressed twice, as adding a valid header to the data and running it through a standalone LZ11 decoder twice will get you a perfect, byte-matching decompressed file. Weirdly, if you compress the uncompressed data twice with an equivalent LZ11 encoder, you get a smaller file that matches up to the end of the smaller file size, but again, is not as large as the data found within the CCB file. Maybe once I get to work fully understanding how this compression algorithm works I'll figure out why that is. I'll either need to to be able to reconstruct modified CCB files, or maybe the game just ignores the extra data as long as it gets a valid decode. Only one way to find out!

 

[Kajitani-Eizan]

Is it a (compressed) archive of (compressed) files? Double compressing the same singular file seems silly.

 

[SolatoroboHacking]

Is it a (compressed) archive of (compressed) files? Double compressing the same singular file seems silly.

It is! Particularly when they intentionally made sure the second pass would not make the file any smaller. Hopefully as I figure out the encoding process I'll figure out how, and some potential reason why. There may be no good reason, but there's gotta be a reason.

 

[SolatoroboHacking]

Is it a (compressed) archive of (compressed) files? Double compressing the same singular file seems silly.

Update: It's been a while and I realized I'm just a moron. It's compressed once. Oops! Currently trying to integrate a modified version of PeterLemon's LZX decompression utility into my CCB extractor. Next step after cracking extracting these things (with one self-contained utility, you can do it with others, but not well) is to try reassembling them, see if the game will accept them, and then see if the game will accept them with modifications.