Each track says its mode in the track header. Bits are read most significant first. The descriptions below are the algorithms of xDMS as written from memory and tested by unpacking real files until every track’s checksum matched; where a detail was found by that testing it says so.
The modes
| Mode | Name | Stages | Seen in the files tried |
|---|---|---|---|
| 0 | None | stored as it is | yes |
| 1 | Simple | run-length coding | yes |
| 2 | Quick | Quick LZ, then run-length | no: written from memory, unchecked |
| 3 | Medium | Medium LZ with a static code, then run-length | yes |
| 4 | Deep | LZ with adaptive Huffman, then run-length | yes |
| 5 | Heavy 1 | LZ with Huffman tables, 4 KB window; run-length if flag bit 2 | yes |
| 6 | Heavy 2 | the same with an 8 KB window | yes (most files) |
Run-length coding
Bytes are copied, except 0x90. 90 00 is a literal 0x90.
90 nn bb (nn from 1 to 254) is bb repeated nn times.
90 FF bb hi lo is bb repeated hi:lo times. The output is
exactly the unpacked size of the track.
The dictionary coders
Quick, Medium, Deep and Heavy all keep their last bytes in a shared text buffer of 16,384 bytes and copy matches from it: a match is a length and a distance back from the current position, and may overlap what it is copying. The buffer and the positions carry over from one track to the next, so a track can match bytes of the track before it.
- Start of the disk: the buffer is zeros; the positions are 251 (Quick), 0x3FBE (Medium), 0x3FC4 (Deep) and 0 (Heavy).
- End of a track: Quick moves its position on by 5, Medium by 66 and Deep by 60 (mod the buffer size); Heavy does not move.
- Reset: a track in mode 0 or 1 puts everything back as at the start of the disk (found by testing: without it Medium and Deep tracks after a stored or RLE-only track fail their checksums). So does a banner or DIZ text track after it is read. Heavy files with stored tracks in the middle unpack either way.
Quick (mode 2)
256-byte buffer. A 1 bit, then 8 bits: a literal. A 0 bit, then 2 bits (length minus 2, so 2 to 5) and 8 bits (distance minus 1). Unchecked: no file here uses this mode.
Medium (mode 3)
A 1 bit and 8 bits: a literal. A 0 bit: the next 8 bits, looked up in a prefix-code table of 64 symbols, give the length minus 3; then the next 8 bits looked up again give the top six bits of the distance, followed by eight raw bits, the distance being that 14-bit number plus 1. The table is the one from Okumura’s LZHUF: symbols of 3 bits (1), 4 bits (3), 5 bits (8), 6 bits (12), 7 bits (24) and 8 bits (16), numbered in that order, each length taking the next symbols in turn.
Deep (mode 4)
LZHUF: an adaptive Huffman tree over 314 symbols (0 to 255 literals; 256 and up a match of 3 to 60 bytes), 627 nodes, updated after every symbol and rebuilt when the root reaches a frequency of 0x8000. The tree starts as a balanced one and carries over between tracks. A match’s distance is coded like Medium’s: the six-bit table symbol, then eight raw bits (confirmed by testing).
Heavy 1 and Heavy 2 (modes 5 and 6)
Two Huffman codes: one for 510 symbols (0 to 255 literals; 256 and up a match of the symbol minus 253 bytes, so 3 to 256) and one for the distance class. The window is 4,096 bytes for Heavy 1 (14 distance symbols) and 8,192 for Heavy 2 (15). When flag bit 1 is set the tables come first in the data:
- 9 bits: the number n of character code lengths. If it is 0, a single symbol follows in 9 bits and every character is that symbol, in no bits.
- Otherwise n lengths of 5 bits each (found by testing; the rest are 0).
- 5 bits: the number m of distance code lengths; 0 means a single symbol in the next 5 bits.
- Otherwise m lengths of 4 bits each.
Codes are assigned as LHA does: shorter codes first, equal lengths in symbol order. Lengths
up to at least 17 bits occur, longer than LHA’s 16-bit tables allow, so decode bit by bit.
A track without flag bit 1 reuses the last tables. A distance symbol j below the
last one gives the value 0, or (1 << (j−1)) + (j−1 extra
bits); the last symbol means “the same distance as the previous match”. The distance
used is that value plus 1. If flag bit 2 is set the result goes through the run-length stage.
Encryption
With the encrypted flag set, each track’s packed data is scrambled byte by byte with a key
that starts as the CRC-16 of the password: each byte is XORed with the low byte of the key,
and the key becomes (key >> 1) + original byte. Whether the key restarts for each track, and whether the data
CRC covers the scrambled or the plain bytes, is from memory and unchecked. No encrypted file
was available. The explorer lists such a file’s tracks and checks the CRCs but does not unpack it.
Not described
Most modes were confirmed by unpacking real files; these were not.
- Reference: Quick (mode 2) and encryption are from memory and unchecked. Why a track in mode 0 or 1 resets the dictionaries is described only as what testing showed. Why Heavy files unpack either way after a stored track is not explained. The meaning of flag bit 0 is not established. Two files with failing checksums are unexplained.
- Viewer: unpacks modes 0, 1, 3, 4, 5 and 6; Quick is implemented but untested; encrypted files are not unpacked (no password input).