Reverse engineering a compression format.

I have often wondered of the capabilities of genetic algorithms or some other form of AI to crack storage formats. For example, if you had data you knew was an image and didnt know the format, a genetic algorithm could generate decompression formulas while an image analysis ANN tested if it was an image yet or not.

Genetics? I''ll have to think about that some. Interesting idea.

I guess if that doesn''t work we''ll just have to hope the MS programmer we''ve contacted is allowed to release the info we need.

It''s definately not going to be an easy job - reverse engineering the code (disassemble) in this instance would be my favoured option.

Tell us more about the data - what does it actually represent?, what does the file as a whole represent?

- A proper movie with live style video in (e.g. MPEG style)?
- A movie made from computer generated, palettised frames (e.g. FLC, IFF ANIM5 style)?
- 3D space vector/quaternion data defining 3D models and their animation?
- 2D sprites and their positioning data?


If traditional "compression" type algorithms are being used (RLE, LZ etc), it''s actually very rare that someone wouldn''t simply use one of those standard algorithms. Inventing their own is usually very unlikely unless the programmer had that as a side hobby. Much more common is a standard algorithm (LZ etc) with control constants changed (dictionary sizes, window sizes etc).

The file is unlikely to be encrypted unless the programmer is paranoid or the product is sold to security concious companies


What I''d personally think/do:

- if the file is compressed at all, it''s an off the shelf algorithm.

- if the file has any tell tale floating point numbers in the hex view, particularly with repeated exponents for normalised floats, then you can guess it stores vectors, points, quaternions, splines etc.

- 1995 is a long time ago, most graphics chips available only had very basic rasterisation capabilities, so all transformation & lighting and most often rasterisation was in software. Back then FPUs weren''t so fast either. So fixed point numbers will be all the rage.

- If the file is a movie of some form, it''ll very likely be palettised, maybe even planar.

- If the program doesn''t need to access the disk during playback, theres a chance it uncompresses the whole thing into memory - for a pixel style movie you may have RLE with runs through TIME rather than through an axis.

- ensure that the files aren''t really a wrapper for some other format common in the day (Eidos Escape, Smacker etc) - companies don''t re-invent the wheel unless they have to or are daft

- If it''s a full motion type format, compare the binary with MPEG and early motion JPEG stuff

- Using the program, create multiple files all the same, but with notable difference (if the program does what I think it does, try creating a movie which lasts twice as long and contains the same frames as the first half). Turn different features on and off. Compare the files - the sizes etc - if the sizes are coming out the same for identical scenes with very small changes such as a character in a name, then the files might not really be compressed. The repeated movie should show patterns - if the data isn''t the same halfway through the file, then it might be compressed OR taking delta values from the previous frame.

- think of things from the other side - how would you load/display the file/save to the file if you were the original author?

- patterns patterns patterns - you see a pattern in the ASCII/hex viewer, then the file probably isn''t compressed.

- to get an idea about what I mean about patterns, view some sound sample data for a sinewave in a hex viewer, view a zip file, write some random floats out to a file and view those (and observe the exponent "pattern")

--
Simon O''Connor
Creative Asylum Ltd
www.creative-asylum.com

quote:

---

Original post by S1CA
Tell us more about the data - what does it actually represent?, what does the file as a whole represent?

---

It's positions of pre-built models/props, so it'd be coordinate data. (the movie) However, that's not what we're after at the moment.
That part's already understood to some degree.
We're trying to understand the data files that come with the program (On the CD), which share some of the same structures as the movies.
Textures, Models, the images for the pre-built scenes, etc.

quote:

---

- 1995 is a long time ago, most graphics chips available only had very basic rasterisation capabilities, so all transformation & lighting and most often rasterisation was in software. Back then FPUs weren't so fast either. So fixed point numbers will be all the rage.

---

The program uses a custom assembly renderer, which was written by the company that did the 3D chip(SuperFX, I think) for the SNES.

quote:

---

- Using the program, create multiple files all the same, but with notable difference...

---

That's exactly how we figured out the movie format
But what we're trying to get to now is the texture data and models. Which are compressed, while the movies aren't.



[edited by - TravisWells on January 11, 2003 1:10:01 AM]

I am also working on this project. We were able to get 2 files which have the exact same result. One compressed and one uncompressed. Located here: http://mywebpages.comcast.net/weindel20381/3DMM/image/sections/

The only thing that we know about the Compressed one is that byte 31 is the color index. Both images turn out to be 64x30. They are not normal BMPs but they have a different format.

We know if a file section is compressed or not by a certain value found in the index marker for the section, and the fact that it stars out with "KCD2". This compression is found in images, 3d models, midis, and other file section types.

Just to clear something up:

A 3DMM File is sort of like a container file. The 3DMM file it self is not compressed, but some sections inside are and some are not.

quote:

---

The program uses a custom assembly renderer, which was written by the company that did the 3D chip(SuperFX, I think) for the SNES.

---

That''d be Argonaut then (company started by Jez San of Starglider fame). And the software renderer would be BRender.
Unless of course you''re thinking of the RenderMorphics stuff which later became the basis for D3D Retained Mode.


Assuming this isn''t for any commercial gain on your part...:

I took a look at those sample files. I think the uncompressed one is pretty interesting in itself and points towards some form of RLE being used for all formats, from the table of byte lengths for each line to the RLE style "copy" count for each line.

Is the compressed version of the file definately 30 lines? - if it were 20 some more stuff would make sense...

The "compressed" data looks very "bitty", lots of odd numbers which leads me to strongly think that the stream is using more or less than 8 bits per value. Possibly variable length bitcodes.

It could even be a very simple dictionary based scheme since the colour index shows up once before the data gets "bitty".


I think more test data would be essential, both compressed and uncompressed:

- The same file with a height of 15 (to see whether the height is explicitly stored AND to detect whether the compressed data just has a big count encompassing all lines or repeats per line).

- The same file with an odd width (if possible) or double the width (again to check for per line compression or per block compression).

- The same file with *two* colours represented, i.e. do a checkerboard pattern with two colours and four squares (would confirm whether or not its a dictionary type scheme and where the data repeats).

- A very noisy file which doesn''t compress well - to see how non-compressable ranges are stored.


A final possibility for the file is that the unusual "bitty" numbers are actually commands describing how to rebuild the image (remember, things like TAOS seemed dead interesting back then). Maybe even x86 code instructions!



--
Simon O''Connor
Creative Asylum Ltd
www.creative-asylum.com

quote:

---

Original post by S1CA
That''d be Argonaut then (company started by Jez San of Starglider fame). And the software renderer would be BRender.

---

Exactly! I see you know your software renderers

quote:

---

Assuming this isn''t for any commercial gain on your part...:

---

Naturally not. If it was I''d offer to buy the information from them, or something of that nature.

Getting more samples isn''t a problem, there are a few hundred in the program of just MBMP''s alone (the graphics format, which the sample was)

However, we can''t create them, since the compression doesn''t seem to be in the program, only the decompression. (Like I said, the movies don''t use the compression, only the data files)

So we can''t really create a checkboard pattern and compress it.
The way we have the compressed-uncompressed samples was luck.
For some reason, the japanese version of the program didn''t have compressed MBMPs.
Since most of the images are the same between the two versions, we can compare the compressed and uncompressed.

I uploaded another set of uncompressed and compressed mbmps. Also included a Bitmap representation of them.

http://mywebpages.comcast.net/weindel20381/3DMM/image/sections/bar/

Thanks

Any other suggestions for stuff I should look for? There are other types of files it compresses. It does pallettes, textures maps, z-buffers, 3d models, etc..

The reason we want to know how this compression works is because we want to find out how to create new stuff for 3DMM for the 3D Movie Maker community ( www.3dmm.com ) There will be a community wide effort in ideas and creating of these new scenes and objects. And I still haven''t heard bavk from one of the developers of 3dmm that I got in contact with recently. Any help is greatly appreciated. Thanks