Unix compress and LZW

The historical Unix compress utility writes files conventionally named .Z. It uses an LZW-family dictionary coder, not DEFLATE. uncompress and zcat expose compatible command-line interfaces on systems that ship the format.

LZW Initialization and Synchronization #

An LZW encoder starts with entries for the single-byte alphabet. It keeps a current phrase w, reads the next byte k, and continues while w + k is in the dictionary. When that phrase is absent, it emits the code for w, adds w + k, and starts with k. A decoder emits the string for each code and, after the first code, adds the previous decoded string plus the first byte of the current string. After input is exhausted, the encoder emits its final phrase. The encoder and decoder therefore add the same entries one code behind.

The familiar KwKwK case occurs when a code equals the next dictionary index: the decoder expands it as previous + first(previous). Rejecting that case would reject valid streams; accepting any code beyond the next index would desynchronize the dictionary.

The .Z Bitstream #

A .Z stream begins with 1f 9d and a flags byte. The low five bits specify the maximum code width, normally 9 through 16 bits. Bit 7 enables block mode; the remaining reserved bits must be handled according to the implementation’s compatibility rules. Codes begin at nine bits and widen as the dictionary reaches the current width’s capacity. In block mode, code 256 is CLEAR: the encoder can emit it to discard entries and restart with the initial alphabet. The decoder must reset at the same point, then resume nine-bit codes. Non-block-mode streams do not have that reset code.

Code-width transition rules are part of the .Z dialect, so a reader should follow the format’s specified timing rather than guess from the next code. Historic implementations differ at edge cases; interoperability testing with the target compress implementation is appropriate.

Compatibility and Operations #

LZW patents affected deployment of compress; the relevant patents have expired, but old archives and platform-specific decoders remain compatibility constraints. Use a format selected by the protocol for new data. tar stores file names and metadata, while a compressor transforms a byte stream, so .tar.Z means a tar archive compressed with .Z.

file backup.tar.Z
uncompress -c backup.tar.Z | tar -tvf -
compress -c source.bin > source.bin.Z
zcat source.bin.Z | sha256sum

The .Z format has no mandatory end-to-end checksum comparable to gzip’s trailer. A decoder can produce plausible bytes from a truncated or corrupted stream, so preserve the source archive and verify an external digest or known file length after conversion. Gzip uses DEFLATE and records CRC-32 plus the uncompressed size in each member, making corruption reporting stronger for ordinary file transfers, but gzip and .Z are not interchangeable streams.

References #

• FreeBSD compress(1) manual, including .Z options and block mode.
• T. A. Welch, “A Technique for High-Performance Data Compression,” Computer, 1984.
• RFC 1952: gzip File Format