Zig deflate compression/decompression implementation. It supports compression and decompression of gzip, zlib and raw deflate format. Andrew pushed for the implementation from the first principles so I give it a try.

Zig's implementation is ported from Go by huge effort of hdorio. Go implementation mainly follows original zlib implementation.

Here I used all those three as reference, but mostly started from scratch. Inflate (decompression) and deflate tokenization are implemented from the first principles. For deflate block writer I started from current std code.

Comparing this implementation with the one we currently have in Zig's standard library (std).
Std is roughly 1.5 times slower in decompression, and 1.17 times slower in compression. Compressed sizes are pretty much same in both cases.

Benchmark are done on aarch64/Linux (Apple M1 cpu):

Compression examples are using Zig repository tar ~177M file.

Compression time in comparison with std (current Zig standard library implementation):

Compressed size in comparison with std:

Decompression time for few different files in comparison with std:

URLs from which tests files are obtained can be found here.

I was also comparing with gzip/gunzip system tools and the results are pretty much similar.

To compare with gzip/gunzip:

zig build -Doptimize=ReleaseSafe
export FILE=tmp/ziglang.tar.gz
hyperfine -r 5 'zig-out/bin/gunzip $FILE' 'gunzip -kf $FILE'

export FILE=tmp/ziglang.tar
hyperfine -r 5 'zig-out/bin/gzip $FILE' 'gzip -kf $FILE'

Running same benchmarks on x86_64 GNU/Linux (Intel(R) Core(TM) i7-3520M CPU @ 2.90GHz):

This library uses static allocations for all structures, doesn't require allocator. That makes sense especially for deflate where all structures, internal buffers are allocated to the full size. Little less for inflate where we std version uses less memory by not preallocating to theoretical max size array which are usually not fully used.

For deflate this library allocates 395K while std 779K.
For inflate this library allocates 195K while std usually around 36K.

Inflate difference is because we here use 64K history instead of 32K, and main reason because in huffman_decoder.zig we use lookup of 32K places for 286 or 30 symbols!

Currently in std lib we have different wording for the same things. Type is called Decompressor, Decompress, DecompressStream (deflate, gzip, zlib). I'll suggest that we stick with Decompressor/Compressor and decompressor/compressor for initializers of that type. That will free compress/decompress word for one-shot action. Fn compress receives reader and writer, reads all plain data from reader and writes compressed data to the writer. I expect that many places can use this simple implementation.

All gzip/zlib/flate will have same methods, here on the gzip example:

const std = @import("std");
const gzip = std.compress.gzip;
const zlib = std.compress.zlib;
const flate = std.compress.flate;

/// Decompress compressed data from reader and write plain data to the writer.
gzip.decompress(reader: anytype, writer: anytype) !void

/// Create Decompressor which will read compressed data from reader.
gzip.decompressor(reader: anytype) gzip.Decompressor(@TypeOf(reader)) 

/// Decompressor type
gzip.Decompressor(comptime ReaderType: type) type {


/// Compress plain data from reader and write compressed data to the writer.
gzip.compress(reader: anytype, writer: anytype, level: Level) !void 

/// Create Compressor which outputs compressed data to the writer.
gzip.compressor(writer: anytype, level: Level) !gzip.Compressor(@TypeOf(writer)) 

/// Compressor type
gzip.Compressor(comptime WriterType: type) type 

Great materials for understanding deflate:

Bill Bird Video series
RFC 1951 - deflate
RFC 1950 - zlib
RFC 1952 - gzip
zlib algorithm explained
Mark Adler on stackoverflow
Faster zlib/DEFLATE
Reading bits with zero refill latency