KKnD2's Archive Format
I grew up playing a lot of Real Time Strategy games, especially the Command & Conquer series and StarCraft. Besides these well-known games, I also used to play a lot of “Krush Kill n Destroy 2” (abbreviated as KKND2). It was never a popular game, but it still has a small but loyal fanbase today.
Like a lot of its peers, the game came with a level editor that allowed you to make your own single and multiplayer missions. It only came with a tiny subset of the games tiles, a brown desert with some ruined buildings for decoration, but I used to spend a lot of time crafting multiplayer maps to play against the AI enemies.
What I wanted to do was to dissect the single-player, and extract out the graphics to use with my own levels. This was not possible, as the levels were in a compiled format the level editor could not open. I had run into a dead-end. I didn’t have the skill or patience to reverse engineer the game or its file formats, so I gave up and moved on.
Some 20 years later, in a fit of nostalgia, I fired up KKND2 and give it another play through. After playing through a few of the missions, I wanted to take another look at the game to see if I could decipher its single player levels.
Where’s All the Data?
All of KKND2’s game data lives in a handful of directories within the game’s installation directory. The ‘levels’ directory was the obvious place to look, containing a number of promising looking files. For each single player level, there was a pair of files named after the faction the mission belonged to as well as the number of the mission inside that faction’s campaign. Each of the three game factions (Survivors, Evolved, and Series 9) had their own complete single-player game campaign, culminating in the victory of that faction over the other two.
Every mission had an ‘LPS’ and ‘MIS’ file, with the ‘LPS’ file larger than the ‘MIS’ file. The MIS file was pretty easy to figure out. On a hunch, I threw the file into GIMP, reading it as a RAW image, and experimented with the settings until it formed a clear image. It was obvious from the image that the MIS files are the scaled-down version of the map used for the in-game mini-map. I could even guess that a 16-bit value represented each pixel, but couldn’t quite coax GIMP into getting the colour values dialed in correctly.
Trial and Error
Opening a few of the LPS files in a hex editor didn’t reveal anything obvious. Similarly, parsing the files with binwalk only gave a few spurious readings. I needed something I could control, where I could perform some side by side analysis. This is where the level editor came to the rescue. I created a simple single-player level in the editor, saved, and exported it. I then replaced one of the retail single-player levels with my custom mission and started that mission through the game’s mission selector. To my surprise, my custom mission loaded and was playable.
This meant that I could not only use the level editor to generate a variety of valid output for analysis, but the format of the exported maps was the same as the compiled retail maps.
During the map export process, I noticed that a number of temporary files sprang into existence before disappearing as the map compiled. If there was a method for me to interrupt this process, I could investigate these files and possibly understand how the editor merges them together to form the compiled map.
Here be dragons
I broke out my copy of Ghidra, an excellent reverse engineering tool provided by the NSA, and opened up my copy of the KKND Mission Editor. I wasn’t exactly sure what I was looking for, but by searching for some strings displayed during the export process, I found the function that controlled the export process.
The export process starts by generating and saving the map components, like the map layout, way-finding information, and information about the items (or creatures) present on the map. Next, the editor generates the mini-map and saves it in a ‘MIS’ file, confirming my suspicions from above. The editor then calls a function called PackFile, which is used to create the compiled map file. The editor then does a clean-up, deleting the intermediate files it generated. I replaced one instruction after the PackFile call with a RET instruction, ending the function early and preserving the intermediate files on disk. This left me with the following files:
export.crp - creeps? critters?
export.lps - compressed archive of the map files
EXPORT.LVS - uncompressed archive containing the map files
export.map - map graphics / tileset
export.mis - minimap
export.way - wayfinding information?
Decompression
With all the map file parts available for inspection, plus the disassembled code that generated the pack file, I started writing a utility which takes a final compiled level and splits it into its constituent parts. I knew that if I could feed in my exported map, and get out a set of files that matched those from the editor, that my code was probably correct.
First, the file has to be decompressed. The file starts with some kind of magic number. Its not consistent between each file, but the differences don't seem to have any bearing on how the rest of the file is parsed, so I ignore it. The rest the file is broken into two separately compressed sections.
+---------------------------------------------------+
| Magic | Compressed Archive | Compressed Metadata |
+---------------------------------------------------+
0 4 End archive ^ EOF ^
Figure 1: Compressed archive format overview
The following code block handles this task, reading the file and returning a decompressed file.
pub fn decompress(filename: &str) -> Result<DecompressedFile, Box<dyn Error>> {
let file = File::open(filename).map_err(|e| format!("Failed to open file: {}", e))?;
let mut reader = BufReader::new(file);
let _magic = reader.read_u32::<LittleEndian>()?;
reader.seek_relative(4)?;
let archive = decompress_part(&mut reader, true)?;
let metadata = decompress_part(&mut reader, false)?;
Ok(DecompressedFile{ archive, metadata })
}
Each compressed part is prefixed with its uncompressed size, followed by a number of chunks (fig. 2). Each chunk is a block of data prefixed with its compressed and uncompressed sizes (fig. 3)
+------------------------+-----------------------------------+
| Part Uncompressed Size | Chunk 1 | Chunk 2 | ... | Chunk N |
+------------------------+-----------------------------------+
0 4 end of chunks ^
Figure 2: Part layout in file
+-------------------------+-----------------------+------+
| Chunk uncompressed size | Chunk compressed size | Data |
+-------------------------+-----------------------+------+
0 4 8 end ^
Figure 3: Chunk layout in file
The decompress_part function handles unwrapping a single part into its chunks, and decompressing each of them. The uncompressed data is joined together to form the final uncompressed part.
fn decompress_part<R: Read>(
reader: &mut BufReader<R>,
big_endian: bool,
) -> Result<Vec<u8>, Box<dyn Error>>
where
R: Seek,
{
let mut decompressed_bytes: u32 = 0;
let part_uncompressed_size = if big_endian {
reader.read_u32::<BigEndian>()?
} else {
reader.read_u32::<LittleEndian>()?
};
reader.seek_relative(4)?;
let mut output: Vec<u8> = vec![];
while decompressed_bytes < part_uncompressed_size {
let chunk_uncompressed_size = reader.read_u32::<LittleEndian>()?;
let chunk_compressed_size = reader.read_u32::<LittleEndian>()?;
let mut chunk_buffer: Vec<u8> = vec![0; chunk_compressed_size as usize];
reader.read_exact(&mut chunk_buffer)?;
let decompressed_chunk = decompress_block(chunk_uncompressed_size as usize, &chunk_buffer)?;
decompressed_bytes += output.write(decompressed_chunk.as_slice())? as u32;
}
Ok(output)
}
There's also a weird quirk of the file format here, for some reason the first part's uncompressed size is written to disk in a big-endian format, but the second part uncompressed size is written in little-endian format.
The decompress_block function is really simple, either the chunk is compressed or it is not. A compressed chunk is run through the decompress_data function. An uncompressed chunk, where the output and input sizes are identical, is returned verbatim.
fn decompress_block(output_size: usize, input: &Vec<u8>) -> Result<Vec<u8>, Box<dyn Error>> {
if output_size == input.len() {
return Ok(input.clone());
}
decompress_data(input, output_size)
}
The most complex part of this process is the decompression algorithm. From what I can tell it is a variant of the LZ-77 compression algorithm. After a lot of trial and error, along with running the game in a debugger to try to make sense of the output, I managed to re-create the algorithm in code.
fn decompress_data(input: &[u8], output_size: usize) -> Result<Vec<u8>, Box<dyn Error>> {
let mut input_cursor: usize = 0;
let mut output_cursor: usize = 0;
let mut counter: u32 = 0;
let mut code_bits = 0;
let mut output: Vec<u8> = vec![0; output_size];
while input_cursor < input.len() {
if counter == 0 {
let word = read_u16(input, input_cursor)?;
code_bits = code_bits & !0xffff | word;
input_cursor += 2;
counter = 16;
}
if (code_bits & 1) == 1 {
let source_copy_cursor =
(((input[input_cursor] as u16) << 4) & !0xff) | (input[input_cursor + 1] as u16);
let pattern_size = (input[input_cursor] & 0x0f) + 1;
let mut copy_cursor = output_cursor - (source_copy_cursor as usize);
for _ in 0..pattern_size {
output[output_cursor] = output[copy_cursor];
output_cursor += 1;
copy_cursor += 1;
}
input_cursor += 2;
} else {
if output_cursor >= output.len() || input_cursor >= input.len() {
return Err("Index out of bounds".into());
}
output[output_cursor] = input[input_cursor];
output_cursor += 1;
input_cursor += 1;
}
code_bits >>= 1;
counter -= 1;
}
Ok(output)
}
Unpacking the Archive
Now we've managed to decompress the file, but now we're left with an archive containing the map components (or other assets, depending on the file we're working with). This file format is also quite simple. It starts with the file magic ('DATA'), followed by the size of the archive data, and the offset in the file to the table of contents.
+-------------------------+-------------------------------------+
| Magic | Size of Archive | Table of Contents offset | Data |
+-------------------------+-------------------------------------+
0 4 8 12 EOF ^
Figure 4: Layout of archive
The table of contents contains an array of file types (MAPD, CPLC, etc...), with each entry containing a reference to an entry in a file address list. The file address list is a flat array of addresses within the archive. Each file 'type' can have one or more files. To get all the files for a given file type, you find the address of the first file by looking up the type in the table of contents. You then scan the file address list, starting at the address from the Table of Contents, until you reach a zero address, which represents the end of the list for that file type.
Table of
Contents File Address List File Data
+-----------+ +---------------------+ +---------------+
| 'MAPD' | />| MAPD file 1 address |----->| MAPD 1 data |
+-----------+ / +---------------------+ | |
| MAPD | / | MAPD file 2 address |-\ | |
| file list |_/ +---------------------+ \ | |
| address | | Zero | \ +---------------+
+-----------+ +---------------------+ \>| MAPD 2 Data |
| 'CPLC' | />| CPLC file 1 address | | |
+-----------+ / +---------------------+ | |
| CPLC | / | Zero |- | |
| file list |_/ +---------------------+ \ +---------------+
| address | \-->| CPLC 1 Data |
+-----------+ +---------------+
Figure 5: Mapping between the Table of Contents and file data
What Next
My code to decompress KKND2 archives has been uploaded to Github at https://github.com/ucosty/kknd2-unpack.
Getting to this point was quite an adventure. I did most of this work months ago, long before I thought about writing a blog article, so I didn't keep a lot of notes about my progress. All I really had were my memories and the code I had written (in some not so great C++). Part of writing this article was re-writing all of my code in Rust, not only to tidy it up but to force me to try to re-understand the work I did.
The next part I'd like to dig into is decoding the MAPD format, which is the tile map and graphics that make up the map.
Comments
There have been no comments made yet.
Submit a Comment