Keen 1-3 RLE compression

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

Commander Keen 1-3 uses RLE Compression to compress its 320x200 FINALE.CKx and PREVIEWx.CK1 screens. Dangerous Dave also uses this format to compress its graphics. It was previously used in Catacomb I and II for the level data (not the graphics). This is one of many possible ways to create a functional RLE system.

The compressed file consists of a UINT32LE giving the decompressed size, followed by the compressed data.

The compressed data is processed in a loop. After each byte is read, its value is used to select an action. If the high bit is set (val & 0x80) then one more than the lower seven bits ((val & 0x7F) + 1) is the number of following bytes passed through unchanged. If the high bit was not set, then that value plus three is the number of times the following byte is repeated.

The next byte is then read and the same procedure followed until there is no more data or the decompressed size in the header has been reached.

An illustration:

80 aa 00 00 81 bb cc 05 dd

This data is interpreted as follows:

80 aa     # Copy AA through unchanged
00 00     # Repeat 00 three times
81 bb cc  # Copy BB and CC through unchanged
05 dd     # Repeat DD eight times

Or as pseudocode:

  • Get the initial dword [Final length]
  • If [Decompressed data length] < [Final length] then:
    1. Read a byte [Value]
    2. If the byte value >= 128, then:
      • Read and output the next [value - 127] bytes
      • Move forward [Value - 126] bytes and return to step 1.
    3. If the byte value < 128, then:
      • Read the next byte and output it (value + 3) times.
      • Move forward 2 bytes and return to step 1.

It can be seen that this system is not optimal since two repeating bytes must be treated as non-repeating.