Deathtrack Compression
| Format type | Compression algorithm |
|---|---|
| Type | Stream |
| I/O unit size | 1-byte (RLE), 1-bit (LZW) |
| Games |
Compressed leaf chunks and the whole .MAP files in Deathtrack start with a five-byte envelope that selects one of three methods: stored, RLE or a variable-width LZW. The scheme belongs to the same Dynamix family as the DGDS engine's decompressors.
File format
Envelope
| Data type | Name | Description |
|---|---|---|
| UINT8 | method | 0 = stored, 1 = RLE, 2 = LZW; any other value makes the game's stream open fail |
| UINT32LE | decodedSize | Number of bytes after decompression |
| BYTE[] | data | Encoded stream (the rest of the chunk, or of the file for .MAP)
|
The game's input limit includes the five header bytes. It stops when the input is exhausted and never checks the declared size; callers compare the result with decodedSize.
Method 0: stored
The bytes are copied unchanged.
Method 1: RLE
Read a control byte c:
| Control | Meaning |
|---|---|
| 0 | No operation |
| 1–127 | Copy the next c bytes literally |
| 128 | No operation |
| 129–255 | Read one byte and repeat it (c & 0x7F) times |
Method 2: LZW
- Codes are packed least-significant bit first.
- The code width starts at 9 bits and grows to a maximum of 12 bits. The width grows when the next free dictionary index reaches the current limit.
- Codes 0–255 are literals, 256 is the reset code, and the first dictionary entry is 257.
- The "KwKwK" case (a code that is not yet in the dictionary) is handled in the usual way: the previous string plus its own first byte.
- Entries are added only while the dictionary has fewer than 4096 entries.
- The original reads codes in groups of width bytes (eight codes). Unread bits of a group are discarded when the width grows and after a reset code. In practice the width changes happen at multiples of eight codes, so only the reset code skips real padding bits – the padding after a reset is not the same as in GIF.
- After a reset code the width returns to 9 bits and the dictionary restarts. The original adds one unused dictionary slot (index 256) with the pre-reset code as prefix; since code 256 is always treated as a reset it is never referenced.
All 58 LZW streams of the shipped game (every LZW leaf plus the ten maps, containing two reset codes) decode identically with the simple reference decoder in the source code below and with the translated original routines.
Source code
From re-deathtrack, the open-source browser port:
src/formats.js–unpack(), a reference decoder (stops at the declared size)docs/re/resources.md– analysis of the original stream codec at1ff8:05d2–20fe- ScummVM's DGDS decompressor was consulted during the initial investigation
Credits
This file format was reverse engineered by VorticonCmdr. If you find this information helpful in a project you're working on, please give credit where credit is due. (A link back to this wiki would be nice too!)