Difference between revisions of "MPDS format"

Latest revision as of 12:44, 6 September 2016

The MPDS format holds map data in the DS version of Disgaea 1. It is actually just a compressed MPD file, with an extra footer appended to the compressed data.

It's fairly likely that this is a known compression that already has a name, in which case the compression part should probably be moved to a separate article. For now, though, it'll be described here.

Compression

There is a very brief header consisting of a 0x10 byte (as "magic number"/to identify compression algorithm), followed by the decompressed size as a 24-bit little-endian integer. Compressed data follows after that.

The compression format is LZ-like, featuring bytes to be copied verbatim as well as backreferences to repeat a string of bytes that has been produced recently.

Before each group of 8 items (verbatim bytes or backrefs) is a byte, its bits acting as flags indicating whether the corresponding item is a verbatim byte (if 0) or a backref (if 1), starting from most down to least significant bit. Thus, 0x43 would mean 1 verbatim byte, 1 backref, 4 verbatim bytes, 2 backrefs.

Backrefs are two bytes wide, its bits forming a pattern xxxxyyyy yyyyyyyy. Such a backref represents repeating x+3 bytes from y + 1 bytes back in history.

Compressed footer

At the end of the decompressed data, after the MPD format proper, is a footer consisting of two lists of u32's, both prefixed by a u32 containing the length of the list. It is unknown what these are for.

C decompressor

Here is the source code for a hacky decompressor written in C.

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

typedef uint8_t  u8;
typedef uint16_t u16;
typedef uint32_t u32;

int decompress(FILE *in, FILE *out, size_t decompressed_size) {
  #define CONTEXT 0x1000
  #define BIT(n, b) (((n) >> (b)) & 1)

  u8 history[CONTEXT];
  size_t i       = 0,
         read    = 0,
         written = 0;

  #define READ() (read++, fgetc(in))
  #define WRITE(x) {             \
    history[i] = (x);            \
    fputc(history[i], out);      \
    written++;                   \
    i = (i + 1) & (CONTEXT - 1); \
  }

  while (written < decompressed_size && !feof(in)) {
    u8 flags = READ();
    for (int b = 7; b >= 0 && written < decompressed_size; b--) {
      if (BIT(flags, b)) {
        // Copy from history
        u8 x = READ();
        size_t count = (x >> 4) + 3;
        size_t offset = (((x & 0x0F) << 8) | READ()) + 1;

        for (int j = 0; j < count; j++) {
          WRITE(history[(i - offset) & (CONTEXT - 1)]);
        }

      } else {
        // Copy input to output
        WRITE(READ());
      }
    }
  }

  if (written == decompressed_size) {
    return written;
  } else {
    return -1;
  }

  #undef CONTEXT
  #undef BIT
  #undef READ
  #undef WRITE
}

int main(int argc, char *argv[]) {
  if (argc != 2) {
    fprintf(stderr, "Usage: %s <file.mpds>\n", argv[0]);
    return 1;
  }

  FILE *f = fopen(argv[1], "r");
  if (f == NULL) {
    fprintf(stderr, "Couldn't open '%s' for reading.", argv[1]);
    return 1;
  }

  // Read header
  u32 header;
  fread(&header, sizeof(u32), 1, f);
  u8 magic = header & 0xFF;
  size_t dec_size = (header >> 8);

  // Decompress
  int n = decompress(f, stdout, dec_size);
  if (n < 0) {
    fprintf(stderr, "Error while decompressing.\n");
    return 2;
  }

  return 0;
}