Unidentified Compression used in 1997 Westwood PC Game "Lands of Lore 2"

[micTronic]

Hello Compression Experts,

I'm a developer desperately trying to figure out a compresion method used in an old Westwood PC game (Lands of Lore II and III from 1997/1999). I'm not very familiar with compression, and having tried for the last couple of days, I am stuck for now and hoping that maybe someone's trained eye can spot the employed method better than myself - or even knows the method from their own experience.

Some of Westwood's common algorithms used during that time are well documented (e.g. "Format80" aka. "Westwood LCW" or "Format 2", an LZW variation). The former is actually used in the game, too, but their "main" archives appears to be compressed using a method that is not the standard LCW. It is quite possibly a variant (they are indeed famous forusing variations of their file formats and algorithms…)

I've been able to obtain a decoded copy for some of the game files (but not for all, that's why the algorithm is still needed), which should be helpful in determining the compression. The files are custom-format resource archives containing textures and sprite graphics in various formats. I've been able to understand the file structure when uncompressed, but not the compression. Below is a screenshot of both compressed (top) and uncompressed (bottom). I have attached the complete (sample) file.





I've discovered that certain literals to copy to the output are prefixed by "00 xy", where xy + 18 is the length of the literal. Some smaller literals are prefixed by"0x", where x + 3 is the length instead. There also seem to be copy instructions, occuring e.g. at offset 36 and 52, but I was unable to determine their pattern. The compresion seems to be command-based to me, similar to"Format 80", but I was unable to determine their structure.

If anyone has an idea, I would be deeply grateful for any advice!

Best,
Michael

[Shelwien]

First 32 bits look like uncompressed data size.
After that could be compressed size?
Literal data match starts at 000A - "00 08" could be either LZSS flags or some descriptor of literal run (of length 1A).
001A: 5C 02 04 referenced "00 00 A2" string at offset 0002?

Could be a good idea to compare with known compression algorithm (eg. LZ4) with literal runs and matches of length 3+?

[micTronic]

Thanks Shelwien for your answer!
I think you're right about the 2 x 4b before the actual compressed data. The first is indeed the uncompressed length, though the second does not seem to match the compressed size.
I agree about the literals, though some lengths match a +3 size (e.g. offset 0x26), some +18 (e.g. 0x9), and some indicate even one character (e.g. 0x32).
I also agree about 0x1A (5C 02 [04]) being a reference ("copy 3 bytes"), though I did not consider a pointer to offset 0. In this case, it works, but then the refernce at 0x34 (5C 01 [03]), which probably copies 3 bytes from 0x33, does not fit into the scheme. Relative offsets - in this case 24 and 16 - did not work out either.

In any case, it's a good start and I'll definitely check out LZ4 and similars (though LZ4 is probably too new to be it I guess). Thanks again

[deus-ex]

@micTronic

I searched the net a bit for you and the following links may be usefull to you:

Westwood SHP Format (Lands of Lore)
http://www.shikadi.net/moddingwiki/W...Lands_of_Lore)


View/Export graphics, animations and other data from Dune2, Legend of Kyrandia, Eye of Beholder, Lands of Lore 1
https://sourceforge.net/projects/westpak2/


Last available version of Westpak2
http://www.andy2.net/archives/WestPak2_070a-exp.exe

[micTronic]

Thanks for your input too, @deus-ex! I've read about various Westwood formats, but the ones I found documented (including SHP, WSA, VQA, MIX,...) use different compression than the one I encountered.
Likewise, all available tools (including Westpak, Engine file converter, XCC_Mixer, and others) seem to not recognize that particular format. Nevertheless, I will keep looking for such references too.