Megatraveller 1 reverse engineering

TreacleWench · 06 July 2016, 22:59

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!

pants · 24 February 2017, 10:17

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.

TreacleWench · 24 February 2017, 11:12

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.

pants · 24 February 2017, 12:49

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

pants · 26 February 2017, 05:27

Unpacked image sets uploaded to The Zone.

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

Enjoy!

TreacleWench · 26 February 2017, 17:00

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.

StingRay · 26 February 2017, 20:43

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.

pants · 26 February 2017, 20:44

New file in the zone.

Quote:

Originally Posted by TreacleWench

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

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

Many thanks for your assistance again.

Happy to help, have fun.

pants · 26 February 2017, 20:48

Haha, StingRay beat me to it - posting as I was replying!

/hattip

StingRay · 27 February 2017, 11:09

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)

Locutus · 27 February 2017, 11:15

Ooo Megatraveller, i've played the pen and paper version of that :-)

TreacleWench · 27 February 2017, 11:51

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!

CodyJarrett · 18 May 2020, 12:46

Is it possible to extend MegaUnpack to unpack the W.DAT map data file?

06 July 2016, 22:59	#1
TreacleWench Amigaaaarrrrgghhh Join Date: Mar 2012 Location: Cranfield, Bedfordshire, UK Age: 45 Posts: 95	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!

24 February 2017, 10:17	#2
pants Registered User Join Date: Feb 2017 Location: fastmem Posts: 53	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.

26 February 2017, 17:00	#6
TreacleWench Amigaaaarrrrgghhh Join Date: Mar 2012 Location: Cranfield, Bedfordshire, UK Age: 45 Posts: 95	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 18:45.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Gods reverse engineering	Kroah	Retrogaming General Discussion	127	27 February 2023 14:46
Reverse engineering wiki	copse	Coders. General	10	02 March 2020 09:48
Captain Blood reverse engineering	Kroah	Retrogaming General Discussion	14	08 March 2016 21:22
Captive 2 reverse engineering	copse	Coders. General	2	19 August 2015 21:08
Cadaver reverse engineering	Kroah	Retrogaming General Discussion	8	11 November 2011 09:35

24 February 2017, 11:12	#3
TreacleWench Amigaaaarrrrgghhh Join Date: Mar 2012 Location: Cranfield, Bedfordshire, UK Age: 45 Posts: 95	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.

26 February 2017, 05:27	#5
pants Registered User Join Date: Feb 2017 Location: fastmem Posts: 53	Unpacked image sets uploaded to The Zone. (TOP.GL, OBJ.GL, X.GL, Y.GL, Z.GL) Enjoy!

26 February 2017, 20:48	#9
pants Registered User Join Date: Feb 2017 Location: fastmem Posts: 53	Haha, StingRay beat me to it - posting as I was replying! /hattip

27 February 2017, 11:15	#11
Locutus Registered User Join Date: Jul 2014 Location: Finland Posts: 1,186	Ooo Megatraveller, i've played the pen and paper version of that :-)

27 February 2017, 11:51	#12
TreacleWench Amigaaaarrrrgghhh Join Date: Mar 2012 Location: Cranfield, Bedfordshire, UK Age: 45 Posts: 95	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!

18 May 2020, 12:46	#13
CodyJarrett Global Moderator Join Date: Mar 2001 Location: UK Age: 46 Posts: 6,166	Is it possible to extend MegaUnpack to unpack the W.DAT map data file?

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