Zone 66 compression format

[Malvineous]

Hi all,

I've seen a few references to Zone 66 but nobody seems to have worked out the compression algorithm applied to most of the game's files. I'm new to XeNTaX and unfortunately the wiki seems to be down so I am unsure if anyone here has worked out how to decompress its files.

So, does anyone know if the Zone 66 decompression algorithm is documented anywhere? If not I think I might be able to provide a compressed and decompressed version of the same file if anyone is familiar enough with compression algorithms to take a look.

Thanks!

[Vash]

try to attach what you said

[Malvineous]

Okay, here's a zip file with four files in it.

"orig.z66" is the original file from the game, it is a compressed version of a standard VGA palette (768 bytes.) All I know about the format is that the first four bytes store a 32-bit integer containing the decompressed file size (0x00000300 here, because the palette is 0x300 bytes long once decompressed.)

I have obtained the decompressed version by taking a screenshot during the game and extracting the palette, and writing it out in the same file format. This is "orig.pal" in the zip.

To confirm I got the correct file, I changed a byte in orig.z66, this is "tweaked.z66".

After playing the game one of the colours had changed (black became dark purple), so captured the palette in the same way as before to create "tweaked.pal". Between "orig.pal" and "tweaked.pal" the first palette entry (first three bytes) has changed from black to dark purple, so this suggests everything is as it seems.

The only caveat is that because the .png screenshots store values from 0-255 and palette files only use 0-63, I had to transform the values. I have seen some games use values 0-64, in which case each byte in "orig.pal" and "tweaked.pal" *might* be 3-4 values larger than it should be. Unfortunately I do not know a way around this, other than modifying DOSBox to capture the values the game sends to the VGA registers.

Please let me know if you're able to work anything out!

EDIT: Here's a couple more tweaks in case they're useful: (first line is the original data)

Code: Select all

z66                   ->  decompressed
00 00 40 00 05 40 10  ->  00 00 00  00 00 2A  00 2A 00  00 2A 2A
30 00 40 00 05 40 10  ->  20 00 20  00 00 2A  00 2A 00  00 2A 2A
10 00 40 00 05 40 10  ->  20 00 20  00 00 2A  00 2A 00  00 2A 2A
11 00 40 00 05 40 10  ->  22 00 22  00 00 2A  00 2A 00  00 2A 2A
00 11 40 00 05 40 10  ->  00 22 00  22 00 2A  00 2A 00  00 2A 2A
20 00 40 00 05 40 10  ->  no effect
40 00 40 00 05 40 10  ->  no effect
00 00 41 00 05 40 10  ->  00 00 28  00 00 00  00 00 2A  00 2A 00 [extra three bytes inserted at start]
00 00 20 00 05 40 10  ->  00 00 00  00 2A ...  [only four 00 at start]
00 00 10 00 05 40 10  ->  00 00 00  00 2A ... [only four 00 at start]
00 00 80 00 05 40 10  ->  00 00 00  00 2A ...  [only four 00 at start]
00 00 50 00 05 40 10  ->  00 00 00  00 00 00  00 00 09  31 00 2A
00 00 60 00 05 40 10  ->  crash
00 00 42 00 05 40 10  ->  freeze

[Darkfox]

There were discussions done here before and the game data was decompressed:

viewtopic.php?f=10&t=2475

viewtopic.php?f=13&t=2595

viewtopic.php?f=21&t=2593

Unfortunately, no working tools came from it.

Also, music is, I believe, IMF.

[Malvineous]

Thanks for the pointers. I sent john_doe a PM to ask about the details, as I was unable to get an LZW algorithm to decompress the data. I tried big/little endian byte order, a varying number of reserved codewords and even starting at codeword lengths other than nine bits, but nothing. And yes I did remove the four-byte length from the front of the file first (although to be sure I also tried all of the above only removing two bytes.) Alas, I was unable to produce any valid data.

Re the music format it is unlikely to be IMF (if you mean IMF as in id Software Music Format) as the game was released by id's competitor Epic. The fact that each song includes both sampled instruments (ala MOD) and OPL instruments (ala IMF) means it is probably a custom format (although I believe S3M may also be capable of this.) However the game was developed by the Renaissance group, who also created the CDFM tracker format which was capable of both digitised and OPL playback in the same song. I would be willing to bet this is the format they used for Zone 66.

[Darkfox]

Oh, right, sorry. I mean the music uses OPL as people were able to make DROs of the ingame music using DOsBOX's built-in raw OPL recorder. I've been wanting to deal with the music myself as well if I wanted to... per example have a new level that has custom music.

john_doe was going to give me a source code of his work regarding Z66 files but he disappeared soon after leaving me not being of much use here and without a means to read or write Z66 files. Only information that I have are that modding and custom level addon packs are indeed possible.

Edit: ...! Oh! Momentary lapse of memory there. I know who you are! Your planning to add Camoto support for Zone 66, eh? I really wish you luck on this venture, I've only brushed the surface really and it has been on a backburner forever since john_doe disappeared before a source code could be delivered. I look forward to Camoto (music compartment mainly, for a Corridor 7 remake and some other musical enhancement projects), best of luck with it.

[Malvineous]

Oh I only just saw your edit - yes I hope to add Zone 66 support to Camoto! The music is my main focus too... I don't recognise your username, do I know you from somewhere else??

john_doe's profile says he's still logging in but I haven't received a reply, so I guess he's no longer interested in Zone 66, which is a shame because he seemed to have it all figured out. I still have no idea how he was able to get LZW working, I've been staring at those bytes for days manually following the LZW algorithm through and no variations produce anything like valid data, but then again I'm certainly no expert on decompression!

[Darkfox]

No, I don't think so, I tend to keep tabs on people and their projects especially if they involve retro 1990s games (my main stay). And same here, compression is really out of my area, which is a shame because I really wish I had that source code to share with you. I just don't know what has happened.

[john_doe]

Hi,

Sorry for disappearring but here I am
I'll try to find the source code I have and upload it somewhere this evening after work.
(I got involved with ScummVM and reverse engineering of complete games so I didn't have much time for Xentax anymore.)

Edit: I uploaded the source code here: http://www.xentax.com/uploads/author/johndoe/Z66.zip
It contains code for the sprite viewer, decompression and map viewer. It's not ready-to-use and you'll have to compile it with Mingw and SDL and change the filenames for it to work. Also the sprite and map viewer work with uncompressed files so they'll need to be uncompressed before. Also, the decompression code doesn't work with all files yet, some files have 13 bits maximum code size while others have 14 bits (this can be changed easily, though). For a standalone decompressor you'd need to have a mapping of filename->bits and chose the correct bit size from there as this can't be detected automatically.

I haven't figured out yet the rest of the map data, this probably contains animations, enemies, triggers etc. Maybe I'll find some time to have a look at them.

[Malvineous]

Oh wow that's fantastic! Many thanks for posting the info. The decompression code compiled and worked fine on my Linux system. Now I understand why it looks nothing like normal LZW - it seems to read a byte's worth of data in between each LZW code...bizarre.

Well this will keep me busy for a while - thanks again

[Darkfox]

Thanks for the code post, and glad your still around (kinda), and I look forward to if you ever do finish it.

[Malvineous]

Looks like there's a couple of bugs in the compression algorithm, I'm currently attempting to solve them (with limited success!) Using tpal.z66:

Code: Select all

@offset 0
decompressed: 00 00 ff ff 00 2a 00 2a  00
      actual: 00 00 00 00 00 2a 00 2a  00

I think this one is because the file has some invalid LZW tokens in it, and john_doe's code initialises the dictionary to -1 (0xff). I changed it to initialise the dictionary entries to 0 and it fixed this issue. But there is another:

Code: Select all

@offset 29e
decompressed: 0a 31 00 2a 2a 00 00 00 2a 2a 00 00 00 00 2a 2a 00 00 00 00 00 2a 2a 00 00 00 00 00 00 00 31 0a 0a 31
      actual: 0a 31 00 00    00 00 00 00    00 00 00 00 00    00 00 00 00 00 00    00 00 00 00 00 00 00 31 0a 0a 31

This one I'm not sure about, the tokens being read in go something like this:

Code: Select all

Read 00a+031, write 0a + 31               // first two bytes are fine
Read 101+000, write 00 2a 2a 00 + 00      // looks like token 101 is wrong, see @offset 0 above
Read 224+000, write 00 2a 2a 00 00 + 00   // not sure, wrong token again?

[Malvineous]

Hooray, posting in a forum when I was stuck meant I immediately found the solution

The problem was that the first code read in was 108 (which doesn't exist yet) and this was stored as codeword 101. Later on in the file when code 101 is used, it still references code 108 (which is now valid) causing code 108's data to be inserted when we don't want it.

I added another check so that any invalid codes were pointed back to the first code in the dictionary before being stored. I'm not sure if this is correct but it appears to be as the output file is now the correct size and contains the correct data.

Code: Select all

if (code >= 0x100 + curDicIndex) code = 0x100;   // new line
nodes[curDicIndex].code = code;
nodes[curDicIndex].nextCode = value;

EDIT: Whoops, 0x100 not zero!

[Malvineous]

Hey Darkfox - you said you were interested in the Zone 66 music? I just found a new track I've never heard before, so perhaps you know where in the game it is used (maybe win/game over music or something.) I discovered it as I was browsing through the decompressed files, it looked the same as the other songs. (And I also extracted a CDFM/670 file from the Amnesia demo and they look the same as well, so now I'm certain this is the music format used.)

The song is stored in zim00.z66 (Adlib version), zim01.z66 (SB version) and zim02.z66 (GUS version).

To listen, overwrite m01gmuz.z66 (the SB version of the intro song) with zim00.z66 or zim01.z66, or for the GUS version, overwrite m03gmuz.z66 with zim02.z66. Then run the game (in DOSBox use "zone66 /sb" or "zone66 /gus" depending on which version you want to hear.)

Granted I never made it all the way to the end of the game, but it's still a surprise to hear a new song! (And this is the second time Zone 66 has done it, I was just as surprised when I found the GUS version of the intro music is a different song to the SB version.)

[john_doe]

I toyed around with some of the unknown files.
MAP?DAT2.Z66 stores the positions of cannons, ship generators etc.

Here's the structure (in pseudocode), note that all coordinates are in tile-space, they need to be multiplicated by 32 to get pixel-coordinates.

Code: Select all

Cannon {
	uint8 type; // the type of cannon, refers to the cannon definitions in MAP?DAT3.Z66
	uint8 x, y;
}

ShipGenerator {
	uint8 type; // the type of ship, refers to the ship definitions in MAP?DAT3.Z66
	uint8 x, y;
}

Base {
	uint8 x, y;
}

// Yet unknown, this seems to specify which map elements can be destroyed (?)
Unknown {
	uint8 x, y;
}

Map2 {
	uint8 startPosX, startPosY; // the player's starting position
	uint8 cannonCount;
	uint8 shipGeneratorCount;
	uint8 baseCount;
	uint8 unknownCount;
	Cannon cannons[cannonCount];
	ShipGenerator shipGenerators[shipGeneratorCount];
	Base bases[baseCount];
	Unknown unknowns[unknownCount];
}

I also have some specs for MAP?DAT3.Z66 which I will post later.

Edit: I also tried to write a compressor to use modified files in Zone 66. The original algorithm used in Zone 66 is LZ78 with some improvements borrowed from LZW. Sadly it didn't turn out good. One simple solution would be to ignore compression and simply write uncompressed data in (9 bit, 8 bit) pairs. I haven't tried it but it should work.