Reversing engenieering a graphic format

[Canassa]

Hi,

I am trying to reverse engenieer some data formats from an old 1992
game called "Betrayal at Krondor" and I having some trouble with it's
graphic format. I already understand it's header format, but all the
graphic data is using a compressiom algorithim unknown to me.

This is an image file from the game (inside the zip):
http://www.geocities.com/trooper_files/files/g_lamut.zip

The first 25 bytes are header information, it stores information like
image width and height, compressed data size, uncompressed data size,
frames, etc. The 0xAE byte is the first byte of the compressed data.

The image uses a 8-bit pallete which means that the uncompressed image
probably uses only 1 byte for each pixel.

This is a in-game print-screen of the image:
http://img397.imageshack.us/my.php?image=krondor0013sk.png

I dumped all the pixels pallete index numbers from that png image into
this file:
http://www.geocities.com/trooper_files/files/saida.zip
This file is probably very similar to the uncompressed data.

I also made a few experimentes, I changed the first byte (0xAE) of the
compressed data to 0x05 then I changed the 5th pallete color to RED
(for better visualization). This is the result:
http://img390.imageshack.us/my.php?image=krondor0222vu.png

Since I don't understand much about compression, I thought this would
be the best place to ask for help :) I appreciate any kind of help,
advice, comments, etc.

Thanks,
Canassa

[Carsten Neubauer]

better post a hexdump of the data you want to
decode. the first 64 to 256 bytes should be enough
for the start.

and what about the 25-byte-fileheader?
compression-ratio may give hints on the algorithm,
size of palette can be interesting,
so don't hide any infos.

btw: asking the developers may save a lot of time.
if somebody remembers...

regards,

carsten neubauer
http://www.c14sw.de/
http://www.edcomponents.com/

[Canassa]

Okay this is the first 256 bytes of the compressed data:

ae 46 8d fa f3 67 92 ab 49 80 00 71 01 24 90 92 c3 43 87 12 91 22 45 89
13 a7 44 9c 6a 69 ac 55 ea 62 a2 8f 1f 39 c9 91 23 91 54 a9 89 a5 16 2d
92 b3 a8 14 ac 52 a5 80 a5 5c c4 aa 26 b4 9b d0 64 02 db a9 6d a7 cf 9a
c0 58 5d 1a 7a a9 26 ab 98 e4 72 d5 5c d4 a6 8d ca a7 6d e4 44 1d 39 92
93 4a 91 9c c2 3c 74 48 0a a3 45 52 1b c1 fa 1a eb 0b 9b b7 b1 ce 26 2e
ab 45 69 8d 5b 2e 70 e3 26 9c 0b c8 e0 a4 bb 78 ef 1e cc 3b 89 52 c2 35
80 fc 3a 1c 4c 69 a2 61 c2 0e 3d ca e9 b2 08 64 a2 aa 4f 55 3a 76 8c 58
70 c5 8f 6b 40 66 5e e3 17 50 22 b7 99 13 b5 e5 f2 f6 21 20 35 71 b9 a8
41 ad 50 8d 42 87 9f dd 26 02 40 bb 36 00 5e b8 47 4d 1a 15 b0 ef a4 43
ae 82 93 82 d8 b7 b0 e1 89 b4 68 69 8c 75 d2 e2 e4 ab 9c 60 92 b2 f8 b4
d4 58 58 37 83 0a b5 79 53 1b 34 56 3e 77 e2 d4

And this is the first 256 bytes of the uncompressed data

ae a3 a3 7f 7f 93 ae 93 80 80 5c 80 a3 a3 94 94 94 87 87 89 a4 a4 94 9c
9c 89 9c b5 b5 b5 b5 a5 9c 89 89 89 89 89 89 9c 72 72 89 a4 a4 a5 a4 a4
a5 8b 8b 72 8b a5 b0 a5 a5 c0 a5 8b 8b ac ac ac d0 d0 d0 d0 c0 a5 c0 c0
c0 da c0 c0 c0 c0 c0 ac ac c0 ac 97 97 97 97 ac ac ac a5 c0 e4 b9 ac ac
8b 6d 6d 8b 8b 8b 8b 8b 6d 72 6d 72 72 72 72 72 9c 8b 8b 9c 72 9c 61 94
94 87 94 94 a4 89 9c 9c 9c a4 b5 b5 b5 a4 b5 be be be be d8 de be be ce
a4 a4 cb b5 94 6b 6b 6b 5c 5c 5c 5c 5c 5c 80 80 80 80 80 80 93 ae 93 93
93 93 93 93 93 93 ae 93 93 93 93 93 93 94 80 80 6b 80 94 80 94 94 94 94
94 94 a4 a4 a4 a4 a4 94 94 94 94 94 94 9c 89 89 72 5d 8b 89 89 89 89 72
72 9c 8b 8b 8b 8b 8b 89 89 89 89 89 89 89 89 94 94 94 94 94 94 80 94 94
9c 89 89 6b 89 89 89 6b 89 6b 94 80 80 89 6b 6b

The palette is stored in an external file, so the compressed image only
needs to know the 8-bit indexes.

And this is the 25 bytes header:
66 10 // header
00 00 // compressiom type (0, 1 or 2)
01 00 // frames number
c2 51 // compressed data size
c8 74 // uncompressed data size
00 00 // unknown

// the next 8 bytes will repeat 'frames number' times
c8 74 // 1st frame uncompressed size
40 00 // unknow
28 01 // image width (pixels)
65 00 // image height (pixels)

02 c8 74 00 00 // not sure (maybe this is part of the compressed data).

Thanks,
Canassa

[Jim Leonard]

Canassa wrote:
> Hi,
>
> I am trying to reverse engenieer some data formats from an old 1992
> game called "Betrayal at Krondor" and I having some trouble with it's
> graphic format. I already understand it's header format, but all the
> graphic data is using a compressiom algorithim unknown to me.

The quickest way to reverse-engineer that particular format is to ask
the developers:
http://www.mobygames.com/game/dos/betrayal-at-krondor/credits

[Canassa]

Thanks guys,

It seens that this image uses a double-compression. It is RLE
compressed, then LZSS compressed. I will read more about LZSS and try
to decode this thing.

[Sachin Garg]

Canassa wrote:
[snip]

> And this is the first 256 bytes of the uncompressed data

[snip]

If you already know what the uncompressed data is, why do you still
want to "decompress" it?

Am just curious

Sachin Garg [India]
http://www.sachingarg.com

[Peter M]

Canassa schrieb:

> It seens that this image uses a double-compression. It is RLE
> compressed, then LZSS compressed. I will read more about LZSS and try
> to decode this thing.

As far as I can see, this image uses LZW compression as used in Gif or
Unix compress, but with its own header.

The bitorder in the compressed stream seems to be the same as in Gif:
(9=MSB 1st entry, i=MSB 2nd entry)
1st byte: 87654321
2nd byte: gfedcba9
3rd byte: ......ih

A more detailed description of LZW can be found e.g. here:
http://arturocampos.com/ac_lzw_gif.html

Peter M

[Carsten Neubauer]

peter, that was a good idea, especially unix-compress.
i may add a little trick:

saving only the compressed data to a file and
adding a 3-byte-header like this:

1F 9D 8C ( .z header for max. 12 bit )
ae 46 8d fa f3 67 92 ... ( rest of compressed data )

makes it a proper .Z-file, decompressible
with anyone's favourite compression-software.

[Canassa]

Oh Thanks!!!

I included the 1f 9d 8c header and descompressed the file with 7-zip!
Thanks guys!

@Sachin Garg

The problem is that the game has 414 image files, so we need to know
the format.

Cesar Canassa

[Canassa]

Btw, does anybody know a C library that can handle these unix compress
files?

Thanks,

[Carsten Neubauer]

btw i just wrote one:)
you may check out the Archive Component on edcomponents.
it's commercial, but the free trial should work fine on
smaller z-files.

apart from that there must be a lot more APIs,
perhaps you find something at
http://www.compression-links.info/Archiving

or somebody else knows more.

greetings,

carsten neubauer
http://www.c14sw.de/
http://www.edcomponents.com/

Canassa schrieb: