All Dogs RLE compression

From ModdingWiki
Jump to: navigation, search
All Dogs RLE compression
Format typeCompression algorithm
I/O unit size1-bit

All Dogs Go To Heaven uses RLE Compression to compress graphics chunks in its graphics archives. This is one of many possible ways to create a functional RLE system.

The compressed file consists of an UINT32LE giving the number of bytes (not pixels) in each row of the graphics chunk, an UINT32LE giving the number of rows in the graphic, and the compressed data. The first UINT32LE of the compressed data, which is almost always uncompressed, gives the size of the uncompressed data. As a check the decompressed size value should be equal to the width and height values multiplied.

The data can be either CGA or EGA data which are four or two pixels of data per byte respectively.

The compressed data is processed in a loop. After each byte is read, its value is used to select an action. If the byte has a value of 27 (val & 0x1B) then the next word gives the number of identical bytes to output and the byte after that is the byte to repeat. All other bytes are passed through unchanged. The next byte is then read and the same procedure followed until there is no more data or the decompressed size has been reached. (This will be obtained elsewhere in the graphics archive even though it is also part of the graphics chunk.)

It should be noted that the repeat length words are big-endian, unlike all others in the game.

As a result of this inefficient scheme it is possible to 'compress' data in this format by simply replacing and 0x1B bytes with the sequence 1B 00 01 1B.

An illustration:

12 34 1B 00 03 56 78 90

This data is interpreted as follows:

12 34          # Copy 12 and 34 through unchanged
1B 00 03 56    # Repeat 56 three times
81 78 90       # Copy 78 and 90 through unchanged

Or as pseudocode:

  • If [Decompressed data length] < [Final length] then:
    1. Read a byte [Value]
    2. If the byte value = 27, then:
      • Move forward a byte
      • Read the next two bytes
      • Store this big-endian value as [length]
      • Move forward two bytes
      • Read the next byte
      • Repeat the byte [length] thimes
      • Move forward a byte and return to step 1.
    3. Else:
      • Read the next byte and output it unchanged
      • Move forward a byte and return to step 1.

It can be seen that this system is very far from optimal since two, three and even four repeating bytes must be treated as non-repeating.