DEFLATE — a from-scratch implementation in Java

A complete DEFLATE compressor and decompressor built from the specification, with no compression library involved. LZ77 match finding, Huffman coding, the sliding window, and bit-level file I/O are all implemented in this repository.

University final project (skripsi), 2010. Published here as a record of early work. It is not representative of how I build software now — see Known limits for an honest account of what it does not do.

What it does

Compresses a file of any type into a .def container and restores it with the bundled decompressor. A Swing interface exposes four levels and reports the resulting compression ratio.

Level	Mode	max_lazy	nice_length
0	Stored — no compression	—	—
1	Fast	5	16
2	Normal (default)	16	128
3	High	258	258

The two tuning parameters follow zlib's approach: max_lazy is the match length above which lazy evaluation is skipped, nice_length the length at which the search stops early and accepts what it has.

How it works

LZ77 stage. A 32,768-byte search window and a 258-byte lookahead window — the parameters fixed by RFC 1951 — are held in one contiguous array in Engine/Container, so advancing the stream is an arraycopy rather than two separate structures kept in sync. Matches shorter than three bytes are emitted as literals, since a length/distance pair would cost more than the bytes it replaces.

Lazy matching. When a match is found below max_lazy, the encoder looks one position ahead before committing. If the later match beats the current one by more than two bytes, it emits a literal and takes the longer match instead. This is what separates a naive greedy LZ77 from something that approaches real DEFLATE ratios.

Huffman stage. Engine/PrefixTree holds the code tables and translates literals, lengths, and distances into their bit strings; Engine/StaticTree, Engine/HuffmanNode, and Engine/BLCount support tree construction and code length counting.

Bit-level I/O. FileBitIO/CFileBitWriter and CFileBitReader handle writing and reading at bit granularity, including the buffering needed when codes do not align to byte boundaries. This layer is what makes the rest possible — Java's stream classes only address bytes.

Container format. Output begins with a four-byte signature, then the original file length, then a mode byte, then the compressed stream. Engine/Inflater reverses the process.

Layout

src/Engine/        Deflater, Inflater, Container, PrefixTree,
                   StaticTree, HuffmanNode, BLCount, ISignature
src/FileBitIO/     CFileBitWriter, CFileBitReader
src/Deflate*.java  Swing interface — frame, menu, dialogs, splash
build.xml          Ant build (NetBeans project)

About 2,700 lines of Java. The compression engine is independent of the interface; Engine and FileBitIO have no Swing dependency.

Building

A NetBeans 6-era Ant project targeting Java 6.

ant clean jar
java -jar dist/Deflate.jar

Known limits

Stated plainly, because a reader deserves to know before cloning:

• Fixed Huffman codes only. Dynamic Huffman blocks — the BTYPE=10 case where the code table is derived per block and transmitted with it — are not implemented. Ratios are therefore below what zlib achieves on the same input.
• Not gzip- or zlib-compatible. The container is my own, so .def files cannot be read by standard tools, and this cannot decompress a .gz. It implements the algorithm, not the interchange format.
• No test suite. Correctness was checked by hand during the project.
• Comments and some strings are in Indonesian.

Context

Written in 2010 as my undergraduate final project. The goal was to understand DEFLATE by building it rather than calling it, which is still the reason it is worth keeping.

Current work — enterprise integration, identity and single sign-on, and backend systems — is in private client and employer repositories. Professional history: linkedin.com/in/kodesh87.