7
\$\begingroup\$

Reverse engineering old games is something I do every now and then. This time, I took a shot at this old RPG called Darkstone.

The bulk of the game's data is stored in archive files with the .MTF extension (not related to the Microsoft Tape Format). A partial description for this file format can be found here. The format uses a custom compression algorithm (I don't know much about compression, so maybe it has a standard name?), which is fairly simple. The previous link describes it, but as @JS1 noted in a comment, the description seems to get the order of bits wrong, the top six bits of a word are the count, the other 10 are the offset.

So I went on and wrote the following code to unpack an MTF archive into normal files. I used plain C this time. Let me know if this can be improved in any way. Performance was not the main concern, but It wouldn't be bad to make it faster if possible, though I don't want to sacrifice readability for that. I also tried to make it more or less like a library, in case someone wants to incorporate the code into another project.

mtf.h:

#ifndef DARKSTONE_MTF_H
#define DARKSTONE_MTF_H

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

/* ========================================================
 * DarkStone MTF game archive structures:
 * ======================================================== */

typedef struct mtf_compressed_header {
    uint8_t  magic1;                   // (Apparently) always 0xAE (174) or 0xAF (175) for a compressed file.
    uint8_t  magic2;                   // (Apparently) always 0xBE (190) for a compressed file.
    uint16_t unknown;                  // Unknown data. Seems to repeat a lot. We can decompressed without it anyways.
    uint32_t compressedSize;           // Advertised compressed size in byte of the entry.
    uint32_t decompressedSize;         // Decompressed size from `mtf_file_entry_t` is repeated here.
} mtf_compressed_header_t;

typedef struct mtf_file_entry {
    char   * filename;                 // Allocated in the heap; Read from file. Null terminated.
    uint32_t filenameLength;           // Filename length, including null terminator.
    uint32_t dataOffset;               // Absolute MTF archive offset to this file entry.
    uint32_t decompressedSize;         // Decompressed size in bytes of the file.
} mtf_file_entry_t;

typedef struct mtf_file {
    FILE             * osFileHandle;   // MTF file handle returned by fopen().
    mtf_file_entry_t * fileEntries;    // Sorted alphabetically by filename.
    uint32_t           fileEntryCount; // Size of fileEntries[].
} mtf_file_t;

enum {
    MTF_EXTRACT_ALL  = -1,
    MTF_MAX_PATH_LEN = 1024
};

/* ========================================================
 * Decompression functions:
 * ======================================================== */

/*
 * Opens a DarkStone MTF archive for reading.
 * It is safe to call mtf_file_close() even if this function fails.
 */
bool mtf_file_open(mtf_file_t * mtf, const char * filename);

/*
 * Closes an MTF archive previously opened by mtf_file_open().
 */
void mtf_file_close(mtf_file_t * mtf);

/*
 * Extract the contents of an MTF archive to normal files
 * in the local file system. Overwrites existing files.
 * The internal directory structure of the MTF is preserved.
 *
 * You may specify a maximum number of files to extract or
 * pass MTF_EXTRACT_ALL to `maxFileToExtract` and allow the
 * extraction of all files in the archive. `filesExtracted`
 * is optional and may be null. If provided, it will output
 * the number of files successfully extracted.
 */
bool mtf_file_extract_batch(const char * srcMtfFile, const char * destPath,
                            int maxFileToExtract, int * filesExtracted);

/*
 * All the above functions will set a global string with
 * an error description if something goes wrong. You can
 * recover the error description by calling this function
 * after a failure happens.
 *
 * Calling this function will clear the internal error string.
 */
const char * mtf_get_last_error(void);

#endif // DARKSTONE_MTF_H

mtf.c:

#include "mtf.h"

#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include <sys/types.h>
#include <sys/stat.h>

/* ========================================================
 * mtf_get_last_error()/mtf_error():
 * ======================================================== */

// Some compilers have Thread Local Storage support
// which can be used to make this error string thread
// safe, so that parallel file processing wouldn't step
// in each other's toes when reporting errors...
static const char * mtfLastErrorStr = "";

static inline bool mtf_error(const char * message) {
    mtfLastErrorStr = (message != NULL) ? message : "";
    // Always returns false to allow using "return mtf_error(...);"
    return false;
}

const char * mtf_get_last_error(void) {
    const char * err = mtfLastErrorStr;
    mtfLastErrorStr = "";
    return err;
}

/* ========================================================
 * Path/directory helpers:
 * ======================================================== */

static inline bool mtf_is_ascii(int ch) {
    return (ch >= 0) && (ch < 128);
}

static void mtf_fix_filepath(char * pathInOut) {
    assert(pathInOut != NULL);
    //
    // DarkStone used Windows-style paths, with
    // backslashes as directory separator.
    //
    // Also, there are a couple filenames in some
    // archives that use extended ASCII characters,
    // like accentuations (é, á, ç, etc), which don't
    // play very well on the Mac file system. So I'm
    // replacing such occurrences with a question mark '?'.
    //
    char * p = pathInOut;
    while (*p != '\0') {
        if (*p == '\\') {
            *p = '/';
        } else if (!mtf_is_ascii(*p)) {
            *p = '?';
        }
        ++p;
    }
}

static bool mtf_make_directory(const char * dirPath) {
    assert(dirPath != NULL);

    // NOTE: stat/mkdir are defined differently on Windows,
    // so this will need a fix when porting this to Win/VS.
    //
    struct stat dirStat;
    if (stat(dirPath, &dirStat) != 0) {
        if (mkdir(dirPath, 0777) != 0) {
            return mtf_error("Impossible to create directory! mkdir(0777) failed.");
        }
    } else {
        // Path already exists.
        if (!S_ISDIR(dirStat.st_mode)) {
            // Looks like there is a file with the same name as the directory.
            return mtf_error("Can't mkdir()! Path points to a file.");
        }
    }

    return true;
}

static bool mtf_make_path(const char * pathEndedWithSeparatorOrFilename) {
    assert(pathEndedWithSeparatorOrFilename != NULL);
    assert(strlen(pathEndedWithSeparatorOrFilename) < MTF_MAX_PATH_LEN);

    char dirPath[MTF_MAX_PATH_LEN];
    strncpy(dirPath, pathEndedWithSeparatorOrFilename, MTF_MAX_PATH_LEN);

    char * pPath = dirPath;
    while (*pPath != '\0') {
        if (*pPath == '/' || *pPath == '\\') {
            *pPath = '\0';
            if (!mtf_make_directory(dirPath)) {
                return false;
            }
            *pPath = '/';
        }
        ++pPath;
    }

    return true;
}

/* ========================================================
 * mtf_readX():
 * ======================================================== */

static inline bool mtf_read32(FILE * fileIn, uint32_t * dword) {
    if (fread(dword, sizeof(*dword), 1, fileIn) != 1) {
        return mtf_error("mtf_read32() failed!");
    }
    return true;
}

static inline bool mtf_read16(FILE * fileIn, uint16_t * word) {
    if (fread(word, sizeof(*word), 1, fileIn) != 1) {
        return mtf_error("mtf_read16() failed!");
    }
    return true;
}

static inline bool mtf_read8(FILE * fileIn, uint8_t * byte) {
    int ch = fgetc(fileIn);
    if (ch == EOF) {
        return mtf_error("mtf_read8() failed!");
    }
    *byte = (uint8_t)ch;
    return true;
}

/* ========================================================
 * mtf_read_compressed_header():
 * ======================================================== */

static inline bool mtf_read_compressed_header(FILE * fileIn, uint32_t offset,
                                              mtf_compressed_header_t * header) {
    assert(fileIn != NULL);
    assert(header != NULL);

    fseek(fileIn, offset, SEEK_SET);
    fread(header, sizeof(*header), 1, fileIn);

    return !ferror(fileIn);
}

/* ========================================================
 * mtf_is_compressed():
 * ======================================================== */

static inline bool mtf_is_compressed(const mtf_compressed_header_t * header) {
    //
    // These magic numbers are from Xentax Wiki:
    //  http://wiki.xentax.com/index.php?title=Darkstone
    //
    if (header->magic1 == 0xAE && header->magic2 == 0xBE) {
        return true;
    }
    if (header->magic1 == 0xAF && header->magic2 == 0xBE) {
        return true;
    }
    return false;
}

/* ========================================================
 * mtf_decompress_write_file():
 * ======================================================== */

static bool mtf_decompress_write_file(FILE * fileIn, FILE * fileOut, uint32_t decompressedSize,
                                      const mtf_compressed_header_t * compressedHeader) {

    // NOTE: `fileIn` must to point past the compressed header!
    assert(fileIn  != NULL);
    assert(fileOut != NULL);
    assert(compressedHeader != NULL);
    assert(decompressedSize != 0);

    // Would be better as a compile-time assert. I'm just being lazy...
    assert(sizeof(mtf_compressed_header_t) == 12 && "Unexpected size for this struct!");

    uint8_t * decompressBuffer = malloc(decompressedSize);
    uint8_t * decompressedPtr  = decompressBuffer;

    if (decompressBuffer == NULL) {
        return mtf_error("Failed to malloc decompression buffer!");
    }

    bool hadError = false;
    int bytesRead = sizeof(mtf_compressed_header_t);
    int bytesLeft = decompressedSize;

    // Do one byte at a time. Repeat until we have processed
    // the advertised decompressed size in bytes.
    while (bytesLeft) {

        // Each compressed block/chunk is prefixed by a one byte header.
        // Each bit in this chunk tells us how to handle the next byte
        // read from the file.
        uint8_t chunkBits;
        if (!mtf_read8(fileIn, &chunkBits)) {
            hadError = true;
            goto BAIL;
        }
        ++bytesRead;

        // For each bit in the chunk header, staring from
        // the lower/right-hand bit (little endian)
        for (int b = 0; b < 8; ++b) {
            int flag = chunkBits & (1 << b);

            // If the bit is set, read the next byte unchanged:
            if (flag) {
                uint8_t byte;
                if (!mtf_read8(fileIn, &byte)) {
                    hadError = true;
                    goto BAIL;
                }

                *decompressedPtr++ = byte;
                ++bytesRead;
                --bytesLeft;
            } else {

                // If the flag bit is zero, the next two bytes indicate
                // the offset and byte count to replicate from what was
                // already read. This seems somewhat similar to RLE compression...
                uint16_t word;
                if (!mtf_read16(fileIn, &word)) {
                    hadError = true;
                    goto BAIL;
                }

                bytesRead += 2;

                if (word == 0) {
                    // Looks like a few entries have padding or something.
                    // When we get here, bytesLeft is already zero, so this seems benign...
                    // Q: Is the padding to align the buffers to a given boundary?
                    break;
                }

                int count  = (word >> 10);    // Top 6 bits of the word
                int offset = (word & 0x03FF); // Lower 10 bits of the word

                // Copy count+3 bytes staring at offset to the end of the decompression buffer,
                // as explained here: http://wiki.xentax.com/index.php?title=Darkstone
                for (int n = 0; n < count + 3; ++n) {
                    *decompressedPtr = *(decompressedPtr - offset);
                    ++decompressedPtr;
                    --bytesLeft;
                }

                if (bytesLeft < 0) {
                    mtf_error("Compressed/decompressed size mismatch!");
                    hadError = true;
                    goto BAIL;
                }
            }
        }
    }

BAIL:

    if (!hadError) {
        if (fwrite(decompressBuffer, 1, decompressedSize, fileOut) != decompressedSize) {
            mtf_error("Failed to write decompressed file data!");
            hadError = true;
        }
    }

    free(decompressBuffer);
    return !hadError;
}

/* ========================================================
 * mtf_write_file():
 * ======================================================== */

static bool mtf_write_file(FILE * fileIn, FILE * fileOut,
                           uint32_t sizeInBytes, uint32_t readOffset) {

    assert(fileIn  != NULL);
    assert(fileOut != NULL);

    void * readBuffer = malloc(sizeInBytes);
    if (readBuffer == NULL) {
        return mtf_error("mtf_write_file(): Failed to malloc buffer!");
    }

    if (fseek(fileIn, readOffset, SEEK_SET) != 0) {
        free(readBuffer);
        return mtf_error("mtf_write_file(): Can't fseek() entry offset!");
    }

    if (fread(readBuffer, 1, sizeInBytes, fileIn) != sizeInBytes) {
        free(readBuffer);
        return mtf_error("mtf_write_file(): Can't read source file entry!");
    }

    if (fwrite(readBuffer, 1, sizeInBytes, fileOut) != sizeInBytes) {
        free(readBuffer);
        return mtf_error("mtf_write_file(): Can't write dest file!");
    }

    free(readBuffer);
    return true;
}

/* ========================================================
 * mtf_sort_by_filename() => qsort() predicate:
 * ======================================================== */

static int mtf_sort_by_filename(const void * a, const void * b) {

    return strcmp(((const mtf_file_entry_t *)a)->filename,
                  ((const mtf_file_entry_t *)b)->filename);
}

/* ========================================================
 * mtf_file_open():
 * ======================================================== */

bool mtf_file_open(mtf_file_t * mtf, const char * filename) {

    assert(mtf != NULL);
    assert(filename != NULL && *filename != '\0');

    mtf->osFileHandle   = fopen(filename, "rb");
    mtf->fileEntries    = NULL;
    mtf->fileEntryCount = 0;

    if (mtf->osFileHandle == NULL) {
        return mtf_error("Can't open input MTF file!");
    }

    // First 4 bytes are the number of files in the MTF archive.
    if (!mtf_read32(mtf->osFileHandle, &mtf->fileEntryCount)) {
        mtf_file_close(mtf);
        return mtf_error("Failed to read file entry count.");
    }

    if (mtf->fileEntryCount == 0) {
        mtf_file_close(mtf);
        return mtf_error("MTF appears to have no file! fileEntryCount == 0.");
    }

    mtf->fileEntries = calloc(mtf->fileEntryCount, sizeof(mtf->fileEntries[0]));
    if (mtf->fileEntries == NULL) {
        mtf_file_close(mtf);
        return mtf_error("Failed to malloc MTF file entries!");
    }

    // Read in the file entry list:
    for (uint32_t e = 0; e < mtf->fileEntryCount; ++e) {
        mtf_file_entry_t * entry = &mtf->fileEntries[e];

        if (!mtf_read32(mtf->osFileHandle, &entry->filenameLength)) {
            mtf_file_close(mtf);
            return mtf_error("file to read a filename length.");
        }

        // Strings stored in the file are supposedly already null terminated,
        // but it is better not to rely on that and alloc an extra byte, then set it to \0.
        entry->filename = malloc(entry->filenameLength + 1);
        if (entry->filename == NULL) {
            mtf_file_close(mtf);
            return mtf_error("Failed to malloc filename string!");
        }

        // Reading a string or not, we continue...
        fread(entry->filename, 1, entry->filenameLength, mtf->osFileHandle);
        entry->filename[entry->filenameLength] = '\0';

        // Data start offset and decompressed size in bytes (for this file entry):
        if (!mtf_read32(mtf->osFileHandle, &entry->dataOffset) ||
            !mtf_read32(mtf->osFileHandle, &entry->decompressedSize)) {
            mtf_file_close(mtf);
            return mtf_error("Failed to read data offset or size.");
        }
    }

    // Entries are probably already in sorted order, but since
    // we don't have a formal specification to ensure that,
    // sort them by filename now:
    qsort(mtf->fileEntries, mtf->fileEntryCount, sizeof(mtf->fileEntries[0]), &mtf_sort_by_filename);
    return true;
}

/* ========================================================
 * mtf_file_close():
 * ======================================================== */

void mtf_file_close(mtf_file_t * mtf) {
    if (mtf == NULL) {
        return; // Can be called even for an invalid file/pointer.
    }

    if (mtf->osFileHandle != NULL) {
        fclose(mtf->osFileHandle);
        mtf->osFileHandle = NULL;
    }

    if (mtf->fileEntries != NULL) {
        for (uint32_t e = 0; e < mtf->fileEntryCount; ++e) {
            free(mtf->fileEntries[e].filename);
        }

        free(mtf->fileEntries);
        mtf->fileEntries    = NULL;
        mtf->fileEntryCount = 0;
    }
}

/* ========================================================
 * mtf_file_extract_batch():
 * ======================================================== */

bool mtf_file_extract_batch(const char * srcMtfFile, const char * destPath,
                            int maxFileToExtract, int * filesExtracted) {

    assert(srcMtfFile != NULL && *srcMtfFile != '\0');
    assert(destPath   != NULL && *destPath   != '\0');

    // `maxFileToExtract` can be zero, negative or MTF_EXTRACT_ALL to extract everything.
    // `filesExtracted` is optional and may be null.

    // Attempt to open and read the headers and file entry list:
    mtf_file_t mtf;
    if (!mtf_file_open(&mtf, srcMtfFile)) {
        return false;
    }

    // Data for the individual files follow.
    // Now read each entry, decompress and write the output files.
    char extractionPath[MTF_MAX_PATH_LEN];
    int successCount = 0;

    for (uint32_t e = 0; e < mtf.fileEntryCount; ++e) {
        const mtf_file_entry_t * entry = &mtf.fileEntries[e];

        // A compressed file is prefixed by a 12 bytes compression info
        // header. If uncompressed, then there is no header; Problem
        // is, we can only tell if the file is compressed after reading in
        // the 12 bytes of a header, so if it is not compressed, we have
        // to seek back 12 bytes and then read the whole uncompressed block.

        mtf_compressed_header_t compressedHeader;
        if (!mtf_read_compressed_header(mtf.osFileHandle, entry->dataOffset, &compressedHeader)) {
            mtf_file_close(&mtf);
            return mtf_error("Failed to read a compression info header!");
        }

        // Set up the output file path, replacing Windows backslashes by forward slashes:
        snprintf(extractionPath, MTF_MAX_PATH_LEN, "%s/%s", destPath, entry->filename);
        mtf_fix_filepath(extractionPath);

        // Output path might not exist yet. This has no side effects if it does.
        mtf_make_path(extractionPath);

        FILE * fileOut = fopen(extractionPath, "wb");
        if (fileOut == NULL) {
            mtf_file_close(&mtf);
            return mtf_error("Can't create output file on extraction path!");
        }

        bool success;
        if (mtf_is_compressed(&compressedHeader)) {
            // Pointing to the correct offset thanks to mtf_read_compressed_header().
            success = mtf_decompress_write_file(mtf.osFileHandle,
                    fileOut, entry->decompressedSize, &compressedHeader);
        } else {
            success = mtf_write_file(mtf.osFileHandle,
                    fileOut, entry->decompressedSize, entry->dataOffset);
        }

        fclose(fileOut);

        if (success) {
            ++successCount;
            if (maxFileToExtract > 0 && successCount == maxFileToExtract) {
                break;
            }
        }
    }

    if (filesExtracted != NULL) {
        *filesExtracted = successCount;
    }

    mtf_file_close(&mtf);
    return true;
}

And here's a simple command line driver to decompress a whole archive:

#include "mtf.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void print_usage(const char * progName) {
    printf(
        "\n"
        "Usage:\n"
        "$ %s <input_mtf> <output_dir>\n"
        "  Decompresses each file in the given MTF archive to the provided path.\n"
        "  Creates directories as needed. Existing files are overwritten.\n"
        "\n"
        "Usage:\n"
        "$ %s --help | -h\n"
        "  Prints this help text.\n"
        "\n",
    progName, progName);
}

int main(int argc, const char * argv[]) {
    if (argc < 2) {
        print_usage(argv[0]);
        return EXIT_FAILURE;
    }

    // Printing help is not treated as an error.
    if (strcmp(argv[1], "-h") == 0 || strcmp(argv[1], "--help") == 0) {
        print_usage(argv[0]);
        return EXIT_SUCCESS;
    }

    // From here on we need an input filename and an output path.
    if (argc < 3) {
        print_usage(argv[0]);
        return EXIT_FAILURE;
    }

    const char * mtfFilename = argv[1];
    const char * outputDir   = argv[2];

    int filesExtracted = 0;
    bool success = mtf_file_extract_batch(mtfFilename, outputDir, MTF_EXTRACT_ALL, &filesExtracted);

    if (success) {
        printf("Successfully extracted %d files from MTF archive \"%s\".\n", filesExtracted, mtfFilename);
        return EXIT_SUCCESS;
    } else {
        fprintf(stderr, "Error while extracting \"%s\": %s\n", mtfFilename, mtf_get_last_error());
        fprintf(stderr, "Managed to extract %d files.\n", filesExtracted);
        return EXIT_FAILURE;
    }
}

Link to the project.

\$\endgroup\$
  • 1
    \$\begingroup\$ The description of the format is incorrect. X is 6 bits and Y is 10 bits, which is opposite of what is written. The example made no sense until I checked your code to see what you really need to do. \$\endgroup\$ – JS1 Aug 31 '15 at 1:01
  • \$\begingroup\$ @JS1, ah yes, I forgot about that! Indeed the explanation seem to be backwards (or perhaps they were assuming a big endian architecture?) I actually figured that out after looking at this C# implementation of a similar decompressor. Taking that into account, I guess I'll just remove the quote from the question, since it might confuse readers... \$\endgroup\$ – glampert Aug 31 '15 at 2:08
4
\$\begingroup\$

How large are these files?

My suggestion would be to load the entire compressed file into memory instead of using multiple fread calls.

If you are storing the decompressed contents in memory, surely you can also store the compressed file in memory as well. Most of your run time is spent fetching bytes with fread, so being able to replace those calls with direct memory accesses should improve performance quite a bit.

Another suggestion I have is to use memcpy instead of this loop:

            for (int n = 0; n < count + 3; ++n) {
                *decompressedPtr = *(decompressedPtr - offset);
                ++decompressedPtr;
                --bytesLeft;
            }

memcpy is a standard way to copy blocks of memory, and most C libraries implement it with special processor instructions to speed it up.

Another coding style issue... instead of:

while (bytesLeft) {
  ...
  bytesLeft -= count;
  if (bytesLeft < 0) { ...error... }
}

I prefer:

while (bytesLeft > 0) {
  ...
  bytesLeft -= count;
}
if (bytesLeft < 0) { ...error... }

It's a safer way to implement the loop as the check bytesLeft > 0 is always performed. The way you've written it the check will get missed if someone uses continue somewhere in the loop body.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions! The sizes of the whole archives vary, the biggest one is ~300MB, but most are in the 70MB neighborhood. So they could fit in memory on any modern PC, so I might try that! \$\endgroup\$ – glampert Aug 31 '15 at 0:18
  • \$\begingroup\$ Actually, that just gave me another idea, I could also memory map the files, which should perform even better! \$\endgroup\$ – glampert Aug 31 '15 at 0:19
3
\$\begingroup\$

Endianness issues

This code works if run on a little endian machine. However, on a bigendian machine, any time you use mtf_read16() or mtf_read32(), you will be misinterpreting the integer value you just read. The easiest fix is to modify your read functions to swap bytes as appropriate.

A similar problem happens any time you directly read a struct containing 2 or 4 byte integer values, such as a header.

Nicely written

Normally there are a lot of issues that I can find in a semi-large program like this. But this code is well written and there's not much I can find to criticize about it. Good job!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.