PKWARE DCL Compression
| Format type | Compression algorithm |
|---|---|
| Type | Stream |
| I/O unit size | 1-bit |
| Games |
The PKWARE Data Compression Library ("DCL", also called "implode"/"explode" or "blast") is a commercial LZ77 compression library sold by PKWARE in the early 1990s. It is not the same as the "Implode" method used in PKZIP 1.x archives, even though the names are similar.
In Gods, every data file whose name begins with P (119 files) is DCL-compressed, whatever its extension. The game decompresses them through UNPACK.EXE, an overlay containing the string PKWARE Data Compression Library(tm) Copyright 1990-91 PKWARE Inc. Version 1.02.
File format
There is no file header beyond the two DCL header bytes, and no stored uncompressed length. The stream ends with an explicit end-of-stream code, and in Gods every file ends exactly there with no trailing bytes.
| Data type | Name | Description |
|---|---|---|
| UINT8 | litMode | 0 = literals stored as raw 8-bit bytes, 1 = literals Huffman coded. Always 0 in Gods. |
| UINT8 | dictBits | Dictionary size: 4 = 1 kB, 5 = 2 kB, 6 = 4 kB. Always 6 in Gods. |
| BYTE[] | data | Bit stream, read least significant bit first |
Every file in Gods therefore begins with the bytes 00 06.
Compression algorithm
The bit stream is a sequence of tokens. Each token starts with one flag bit:
- 0 – a literal. With litMode 0 the next 8 bits are the byte to output.
- 1 – a copy. A length is read, then a distance, and length bytes are copied from distance bytes back in the output.
The length is read with a fixed Huffman code giving one of 16 length codes, each followed by a number of extra bits. This gives lengths from 2 to 518. A length value of 519 marks the end of the stream, and no distance is read after it.
The distance is read as a 6-bit high part (Huffman coded, 64 codes) followed by low bits. For a length of 2 the low part is always 2 bits. Otherwise it is dictBits bits. The final distance is (high << lowBits) + low + 1.
The three Huffman tables (literal, length and distance) are fixed and built into the library. They are not stored in the file. Every Huffman code bit is inverted before use. The canonical tables and a reference decoder can be found in contrib/blast in the zlib source distribution, which decodes all 119 Gods files correctly.
Recompressing
Because Gods files use uncoded literals, a valid (if not very small) stream can be written by emitting every byte as a literal (flag 0 + 8 bits) and finishing with the length-519 end code. The files grow by about 12.5%, but the game loads them without complaint.
Source code
- zlib contrib/blast/blast.c – reference decompressor by Mark Adler
- src/formats/dcl.js – JavaScript port of blast
- src/formats/dcl-encode.js – store-mode (literals only) compressor
- tools/blast.py – Python port of blast
Credits
This algorithm was documented for Gods by VorticonCmdr, using the zlib blast decoder by Mark Adler. 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!)