English Amiga Board


Go Back   English Amiga Board > Coders > Coders. General

 
 
Thread Tools
Old 06 July 2016, 23:59   #1
TreacleWench
Amigaaaarrrrgghhh

TreacleWench's Avatar
 
Join Date: Mar 2012
Location: Cranfield, Bedfordshire, UK
Age: 39
Posts: 93
Megatraveller 1 reverse engineering

Hi all,

For over a year now, I have on and off been working on reverse engineering the data files in Megatraveller 1 for the purposes of making an editor as well as just for fun.

While I have had a lot of success with figuring out the game data, I have always struggled with figuring out how to extract images from the various image files and despite revisiting it again and again, I am not much closer.

So I thought it was time to ask for some help! Here's what I do know about the images files:

It is a DOS game so individual files are easy to read.
Files with a .GL extension contain images.
Each .GL file has a header containing the number of images in the file as well as offsets to each image section and the length of each section.
Each image section contains a header with palette and dimension info, a byte I cannot identify and the length of the image binary.
After the header is the binary data, the length of this data does not tie in with the size of the image, it is always less by a factor that varies between images suggesting it is compressed.
Although the palette contained in the file is correct, it is not used as changing these values has no effect. The Copperlist is used for colours but must be filled from somewhere else.
Z.GL contains 55 shop keeper images and I have mostly been trying to extract the images from this file since they are all the same size and relatively small.
Using the excellent Maptapper, I have established that the images are ACBM with 5 bitplanes and a mask at the end.
So I know quite a lot about the final image, to the point of being able to extract an uncompressed binary from a WinUAE savestate but I cannot figure out how the compressed image data in the file relates to it. I have tried uncompressing it using RLE methods such as Packbits and similar but always run into an invalid byte. I have checked the data manually for any patterns but come up empty.

I have tried forcing my own data into the file to see what happens and sometimes it causes a crash but mostly I do get an "image" but I still cannot relate the output to the binary data in any way. The final image seems to come out very unpredictably compared to the input data. I have tried just a few bytes at the start and 0x00 in the rest of the data and the result is 4 or 5 different sections of different coloured pixels all over the image, filling the image data with all 0x01 creates a mass of pixels all over the image using every colour and changing just one byte in the data can have massive effects on the final image. All this leads me to believe the image is not just compressed but encrypted as well.

Now I know the obvious suggestion would be to look at the assembly code and believe me I have tried but my knowledge in that area is weak and the code is a nightmare! I think the game must not have been written in assembly as there are jumps and labels everywhere including labels to other labels and sometimes to apparent dead ends!

If anyone has any experience in this area or suggestions of any kind I would be most grateful. Or, if there is a god-like 68k assembly coder out there who can figure out how the game loads images, that would be even better!

Thanks in advance

On a side note, Megatraveller 1 seems to be highly customisable and as far as I can see, you could add/edit weapons, items, characters and perhaps even planets without having to change the game code. This, combined with my love of the game since the early days, has got me excited to crack this game and make an editing tool!
TreacleWench is offline  
AdSense AdSense  
Old 24 February 2017, 11:17   #2
pants
Registered User

 
Join Date: Feb 2017
Location: fastmem
Posts: 42
Hi

Not sure if you are still interested, but I took a look at this at lunch today and figured you might like some closure

TLDR: The image data is compressed with an early LZ* variant.

A bit more detail:

[All 16 and 32 bit fields are stored Big Endian unless marked '-LE']

'.GL' files are, as you describe, simple containers for other files:

Code:
;----------------------------------------------------------------------
; .GL header
;----------------------------------------------------------------------
u32     NumFiles
NumFiles *
  u32   FileOffset
  u32   FileLength
The header/offset block is immediately followed by file data:

Code:
;----------------------------------------------------------------------
; image header
;----------------------------------------------------------------------
u16-LE  HeaderSize | (EndianFlag or Type or Version)
 u8     PalEntries (number of palette entries)
 u8     UnknownForNow
u16     ImageW
u16     ImageH
u32     CompressedDataSize
u32     UncompressedDataSize
PalEntries *
  u8    R
  u8    G
  u8    B
CompressedDataSize *
  u8    ImageData
ImageData is raw output from an early LZ variant (dictionary coder).

The bad news: There are an dozens of LZ variants, and infinite variations of those variants.

The better news: LZ variant decoders are conceptually simple and can be reversed/ripped from the game.

Decoder: because the exe files are relocatable, search for the following bytes:
Code:
48 E7 38 38 28 00 61 00 01 1E
That's the start of the decompression routine. Inputs are:

a0: src_buffer (compressed data)
a1: dst_buffer (uncompressed data)
d0: uncompressed length

call that with the params from your file and you have your decompressed data.

Some other notes:

UncompressedDataSize = ImageW * ImageH
So... Uncompressed = 8 bit indicies / plane data per pixel.

The decoder mirrors output bytes to a local 4096-byte window buffer, which means it was likely ripped from example code that used fileio :s

Files share a common palette (that's why when you modified one things didn't change in-game).

The files are allocated memory via the OS (determined by filesize) during handling - i.e. are not loaded into fixed size buffers. This means if you modify/write your own files (and they compress larger) you should be safe.

Have fun

/pants.
pants is offline  
Old 24 February 2017, 12:12   #3
TreacleWench
Amigaaaarrrrgghhh

TreacleWench's Avatar
 
Join Date: Mar 2012
Location: Cranfield, Bedfordshire, UK
Age: 39
Posts: 93
Hi pants, you are awesome! Makes me feel bad though that you did in one lunch hour what I couldn't do in over a year

Yes, I have still been working on this and I still hadn't figured out the compression. I have worked out a lot of other interesting things though including the unknown byte in the .GL files, it's the palette index of the colour that should be treated as transparent!

I also found that there is another type of graphics file in the game, .LY files. These contain a system of vector graphic opcodes mostly used to draw the front end menus and character generator. These files also contain all the UI graphics from the PC version of the game which are not used in the Amiga version at all!

I have had such fun digging into this game and my understanding of how these things work has increased dramatically since I started this project. For example, I managed to figure out how the world maps are stored in W.DAT, it confused me initially until I discovered that the map data uses simple RLE compression as well as being stored in fixed size rectangular chunks. I believe the chunks exist because the map is loaded from disk as you walk around and storing the map this way reduces the amount of disk accessing required.

Armed with this knowledge, I wrote a PHP script that parses W.DAT and renders the game world maps in a web browser. I still didn't have the graphics for this so I had to work around it by creating a world made up of all the possible tiles in order and then ripping them into some GIF files! Now I know where the decompression routine is, I will attempt to rewrite it in into my PHP script so it will render the maps just from the raw data files.

Thanks very much for your help with this, it has made my day! I will post any progress updates here.
TreacleWench is offline  
Old 24 February 2017, 13:49   #4
pants
Registered User

 
Join Date: Feb 2017
Location: fastmem
Posts: 42
Quote:
I have worked out a lot of other interesting things though including the unknown byte in the .GL files, it's the palette index of the colour that should be treated as transparent!
Nice... mystery solved!

Quote:
I believe the chunks exist because the map is loaded from disk as you walk around and storing the map this way reduces the amount of disk accessing required.
Being generous I'd say the programmers must have been 'time limited' on this one... Not too many concerns with efficiency that I saw...

Quote:
Now I know where the decompression routine is, I will attempt to rewrite it in into my PHP script so it will render the maps just from the raw data files.
I'd suggest doing an ugly one-time rip (decompress) to raw - that way you avoid having to spend any time deciphering their decompress routine:

- asm .gl iterator stub + incbin .gl file(s) + assemble to binary
- boot game, freeze at black screen (game loaded)
- load your stub_and_data.bin
- call your iterator, which calls the (in-game) decompressor, recreating a .GL file with uncompressed data (correcting offsets and lengths) high up in fastmem.
- save it out.
- cup of tea and a biscuit.

[bonus points: patch game decompress to do a memcpy, that way you can now also edit the graphics, and use them in-game]

Glad to hear you are still having fun exploring

Last edited by pants; 24 February 2017 at 14:00. Reason: bonus
pants is offline  
Old 26 February 2017, 06:27   #5
pants
Registered User

 
Join Date: Feb 2017
Location: fastmem
Posts: 42
Unpacked image sets uploaded to The Zone.

(TOP.GL, OBJ.GL, X.GL, Y.GL, Z.GL)

Enjoy!
pants is offline  
Old 26 February 2017, 18:00   #6
TreacleWench
Amigaaaarrrrgghhh

TreacleWench's Avatar
 
Join Date: Mar 2012
Location: Cranfield, Bedfordshire, UK
Age: 39
Posts: 93
Thanks pants!

My assembler powers are really weak so I don't really know how to do that but great job extracting the ones you did! If you could spare the time at any point would you mind extracting A.GL, C.GL, SPACE.GL and STARTUP.GL as well please?

It's interesting that the data decompresses to just a load of byte per pixel palette indexes. I was expecting it to be ILBM or ACBM format!

I'm writing a script to convert them all to GIFS at the moment but I will still have a go at understanding the assembler decompression routine and writing my own because I do like to understand how these things work.

Many thanks for your assistance again.

Last edited by TreacleWench; 26 February 2017 at 19:45.
TreacleWench is offline  
Old 26 February 2017, 21:43   #7
StingRay
move.l #$c0ff33,throat

StingRay's Avatar
 
Join Date: Dec 2005
Location: Berlin/Joymoney
Posts: 5,591
I have coded a small tool which can be used to unpack the Mega Traveller files. It's a quick hack but should do its job. Source and executable attached.

Usage is simple: Megaunpack source file destination directory

If you have any questions or need changes don't hesitate to let me know.
Attached Files
File Type: 68k MegaUnpack.68k (11.3 KB, 28 views)
File Type: s MegaUnpack.s (18.1 KB, 43 views)
StingRay is offline  
Old 26 February 2017, 21:44   #8
pants
Registered User

 
Join Date: Feb 2017
Location: fastmem
Posts: 42
New file in the zone.

Quote:
Originally Posted by TreacleWench View Post
If you could spare the time at any point would you mind extracting A.GL, C.GL, SPACE.GL and STARTUP.GL as well please?
Totally missed these! They're included in the archive now.

Quote:
Originally Posted by TreacleWench View Post
I'm writing a script to convert them all to GIFS at the moment but I will still have a go at understanding the assembler decompression routine and writing my own because I do like to understand how these things work.
Take a look at some LZSS and LZ78 implementations, that will help.
I've included the asm rip routine in the archive and semi-commented it. Also included the 'to text' dumper. Both are 'use-once' code, so ignore the ugliness.

Quote:
Originally Posted by TreacleWench View Post
Many thanks for your assistance again.
Happy to help, have fun.
pants is offline  
Old 26 February 2017, 21:48   #9
pants
Registered User

 
Join Date: Feb 2017
Location: fastmem
Posts: 42
Haha, StingRay beat me to it - posting as I was replying!

/hattip
pants is offline  
Old 27 February 2017, 12:09   #10
StingRay
move.l #$c0ff33,throat

StingRay's Avatar
 
Join Date: Dec 2005
Location: Berlin/Joymoney
Posts: 5,591
I have updated the tool a bit, fixed some bugs and added a few new features. The image dimensions and number of used colors are now stored in the file comment and it's also possible to specify the extension used for images (default: img) and palettes (default: pal).

I guess this is the final version of the tool unless someone requests changes/fixes.

Usage (arguments in brackets: optional parameters):
MegaUnpack source file DEST=destination directory (PALEXT IMGEXT)
Attached Files
File Type: 68k MegaUnpack.68k (11.4 KB, 22 views)
File Type: s MegaUnpack.s (19.0 KB, 28 views)
StingRay is offline  
Old 27 February 2017, 12:15   #11
Locutus
Registered User

 
Join Date: Jul 2014
Location: Finland
Posts: 768
Ooo Megatraveller, i've played the pen and paper version of that :-)
Locutus is offline  
Old 27 February 2017, 12:51   #12
TreacleWench
Amigaaaarrrrgghhh

TreacleWench's Avatar
 
Join Date: Mar 2012
Location: Cranfield, Bedfordshire, UK
Age: 39
Posts: 93
Thanks guys for all your help. I have managed to view the uncompressed images, just need to write a tool to save them as GIFs. Won't take too long but at the moment I'm just seeing if I can reverse engineer the algorithm from StingRay's source, in between doing some actual work!
TreacleWench is offline  
AdSense AdSense  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Captain Blood reverse engineering Kroah Retrogaming General Discussion 14 08 March 2016 22:22
Captive 2 reverse engineering copse Coders. General 2 19 August 2015 22:08
Gods reverse engineering Kroah Retrogaming General Discussion 68 26 August 2013 14:28
Cadaver reverse engineering Kroah Retrogaming General Discussion 8 11 November 2011 10:35
Reverse engineering wiki copse Coders. General 9 14 December 2009 02:25

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 12:03.


Powered by vBulletin® Version 3.8.8 Beta 1
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Page generated in 0.20417 seconds with 15 queries