File Compression
A from-scratch C++ implementation of DEFLATE and the ZIP file format — no compression libraries involved.
Built in 2023 · not public yet
Real ZIP files, built byte by byte.
File Compression is a C++ program that implements the DEFLATE algorithm (RFC 1951) and the surrounding ZIP container format entirely from scratch: local and central file headers, the end-of-central-directory record, CRC32 checksums, MS-DOS timestamps — all of it, with no zlib or miniz involved.
I validated correctness by round-tripping files through Windows' built-in compression both ways — compressing with my own program and extracting with Windows Explorer, then compressing with Explorer and extracting with my program. Once that was solid, I turned to performance: reading through zlib's source for ideas and rebuilding my match finder around the same hash-chain approach it uses.
Literals, or a pointer to the past
Every byte is either written out as a literal or replaced by a (length, distance) reference into the last 32 KB of already-processed data — the "sliding window". Repetition-heavy data collapses into a handful of back-references instead of raw bytes.
Hash chains, borrowed from zlib
Every 3-byte sequence is hashed into a bucket that keeps only the most recent position, while a parallel "prev" array threads earlier positions with the same hash into a chain, walked backwards to find the longest match — capped at 1024 probes so pathological inputs stay fast. A one-byte lookahead (lazy matching) checks whether waiting one more position yields a better match before committing.
Correctness came first, speed second: I only started reading zlib's internals after my own implementation was already producing valid, standard-compliant archives. The head/prev hash-chain structure, and capping how far it's walked, is the part I adapted most directly from it.
Two Huffman trees per block
Once a block has been turned into a stream of literals and matches, two separate canonical Huffman trees are built from their actual symbol frequencies in that block: one for literals, lengths and the end-of-block marker, one for distances. Frequent symbols get shorter codes. The shape of both trees is itself compressed — with three special repeat codes — before being written, and each block picks whichever of stored, fixed, or dynamic Huffman coding produces the smallest output.
Wrapping it into a file Explorer understands
Compressed blocks alone aren't a .zip file. Local file headers, a central directory, an end-of-central-directory record, CRC32 checksums and MS-DOS-encoded timestamps are all assembled around the DEFLATE stream so the result opens in any standard zip tool — not just my own.
From bytes to bits
A small walkthrough of the pipeline above, using the string "ABCABCABCX" as input.
Scanning byte by byte — "A", "B", "C" have no earlier match yet, so they're emitted as literals.
1. LZ77 over the sliding window
2. Tokens emitted
Literal / length tree
Distance tree
4. Packed into bits
Illustrative code lengths — real ones depend on each block's actual symbol frequencies.
- C++20
- CMake
- DEFLATE (RFC 1951)
- ZIP format
- CRC32