.Z File Format – Header and LZW codes

Header

The source notes that the original compress wrote no magic number at all; its -n option reads such headerless files, and -C writes output compatible with compress 2.0. A file with block mode off cannot reset its table. The -b option sets the largest width, between 9 and 16.

Codes

• Codes are packed least significant bit first: the first code’s low bit is bit 0 of byte 3.
• Codes 0 to 255 are single bytes. In block mode, code 256 is CLEAR and the first new string gets code 257; without block mode new strings start at 256.
• Codes start 9 bits wide. Each new code adds a table entry (the previous string plus the first byte of the current one). When the next free code would not fit in the current width, the width grows by 1, up to the largest width in the header. When the table is full, no more entries are added.
• A code equal to the next free code (not yet in the table) means the previous string plus its own first byte (the “KwKwK” case).
• CLEAR empties the table and sets the width back to 9. compress writes it, in block mode, when the compression ratio falls after the table has filled; it checks the ratio every 10,000 input bytes.

Padding after a width change

compress writes codes in groups of eight, so a group of n-bit codes fills n bytes exactly. When the width changes, or after a CLEAR, the rest of the current group is padded: the decoder must skip forward to the next multiple of n × 8 bits, counted from the start of the codes at the old width. Decoders that ignore this produce garbage after the first width change. The end of the file needs no special marker; the last code ends within the last byte.

Example

1F 9D       magic
90          flags: block mode (80), largest width 16 (10)
…           9-bit codes, least significant bit first

There is no checksum, file name or original size, so damage can only be seen when decoding fails.