Data Compression for Games

01Why compress

Three distinct payoffs, and they are not the same goal: smaller download and package size (storefront and patch budgets), higher effective load bandwidth (read fewer bytes off disk and inflate them in RAM), and as the mechanism behind both, a trade of CPU for I/O. That trade only pays when the device is I/O-bound and the decoder keeps up.

And compression does not always speed up loads. On a fast NVMe with a slow, high-ratio codec, the decoder becomes the bottleneck and loading gets slower. That is exactly why decode speed gets its own section (§6).

02What compression can't do

Shannon's source-coding theorem sets a hard floor: no lossless coder can, on average over a source, use fewer bits per symbol than the source's entropy^[1].

• The bound is on the average over the distribution, not any single message.
• High-entropy (incompressible) data, already-compressed or encrypted bytes, cannot be losslessly shrunk, and by the pigeonhole principle any coder that shrinks some inputs must make others larger. "You can't compress random data" is the loose version of this.
• Lossy compression (audio, textures) sidesteps the bound by discarding information. That's a different game; the entropy floor is about lossless.

Run-length encoding is the warm-up: replace runs of a repeated byte with (count, value). It shines on long uniform runs (masks, indexed art) and expands data with no runs (encoding ABCD as 1A1B1C1D doubles it), the simplest proof that compression can make things bigger.

03LZ77: the sliding window

Real data repeats, just not in fixed-length runs. LZ77 (Ziv and Lempel, 1977) encodes the input as a mix of literals and back-references: a (distance, length) pair that copies a substring already seen, from a sliding window of recent output^[2].

• A back-reference points into already-decoded output (distance back, length to copy), not an external dictionary or the future.
• Matches may overlap the current position (a length greater than the distance is legal, and is how runs get encoded).
• LZ77 is a family, not one format: zstd, LZ4, DEFLATE, Brotli, and Oodle Kraken are all LZ77-based but mutually incompatible. The window is bounded; the size is a ratio-vs-memory knob.

The window slides as the encoder scans. Repetitive text finds long matches; feed it high-entropy text and the matches vanish:

struct Token { bool isMatch; uint8_t literal; int distance; int length; };

std::vector<Token> lz77Encode(const std::vector<uint8_t>& input, int windowSize, int minMatch) {
    std::vector<Token> tokens;
    int position = 0;
    while (position < (int)input.size()) {
        int bestLength = 0, bestDistance = 0;
        int windowStart = std::max(0, position - windowSize);   // the window of seen output
        for (int candidate = windowStart; candidate < position; ++candidate) {
            int length = 0;                                   // match may overlap position (length > distance is legal)
            while (position + length < (int)input.size() &&
                   input[candidate + length] == input[position + length]) ++length;
            if (length > bestLength) { bestLength = length; bestDistance = position - candidate; }
        }
        if (bestLength >= minMatch) { tokens.push_back({true, 0, bestDistance, bestLength}); position += bestLength; }
        else                       { tokens.push_back({false, input[position], 0, 0}); position += 1; }
    }
    return tokens;
}

struct Token { is_match: bool, literal: u8, distance: usize, length: usize }

fn lz77_encode(input: &[u8], window_size: usize, min_match: usize) -> Vec<Token> {
    let mut tokens = Vec::new();
    let mut position = 0;
    while position < input.len() {
        let (mut best_length, mut best_distance) = (0, 0);
        let window_start = position.saturating_sub(window_size);    // the window of seen output
        for candidate in window_start..position {
            let mut length = 0;                                  // overlapping matches (length > distance) are legal
            while position + length < input.len()
                && input[candidate + length] == input[position + length] { length += 1; }
            if length > best_length { best_length = length; best_distance = position - candidate; }
        }
        if best_length >= min_match { tokens.push(Token { is_match: true, literal: 0, distance: best_distance, length: best_length }); position += best_length; }
        else { tokens.push(Token { is_match: false, literal: input[position], distance: 0, length: 0 }); position += 1; }
    }
    tokens
}

04Entropy coding

LZ77 produces a stream of tokens; an entropy coder then packs those symbols near their information content. Huffman (1952) builds an optimal prefix code: frequent symbols get shorter codes^[3].

Set the symbol frequencies and the tree rebuilds bottom-up, rarest symbols pushed deepest:

05DEFLATE and the modern codecs

DEFLATE (RFC 1951) is the classic combination: LZ77 plus Huffman, with a 32 KB window. It's the algorithm inside zlib, gzip, and PNG^[5]. (zlib and gzip are container wrappers around the raw DEFLATE stream; the 32 KB window is a DEFLATE limit, not a law of LZ.)

The modern general-purpose codecs sit at different points on a three-axis tradeoff of ratio, speed, and memory:

• LZ4: very fast, lower ratio; decode can approach memory-bandwidth limits^[7].
• zstd: tunable from negative "fast" levels up to level 22, with an FSE (a tANS variant) entropy coder plus Huffman for literals^[6].
• Brotli: higher ratio, slower, with a static dictionary tuned for web text specifically^[8].

// Size the destination with the codec's bound, then ALWAYS check the result.
std::vector<char> dst(ZSTD_compressBound(src.size()));
size_t n = ZSTD_compress(dst.data(), dst.size(), src.data(), src.size(), 3);  // level 3
if (ZSTD_isError(n)) { /* handle */ }
dst.resize(n);
// Decode: get the size from the frame header, then ZSTD_decompress.

// The `zstd` crate wraps libzstd; encode_all/decode_all are the one-shot helpers.
use zstd::stream::{encode_all, decode_all};
let compressed = encode_all(&source[..], 3)?;   // level 3 (negative levels go faster)
let restored   = decode_all(&compressed[..])?;  // size read from the frame

The chart plots ratio against decode throughput. Drag the zstd level; switch the data to already-compressed and every ratio collapses:

06Decode speed sets load time

For load times, decode throughput, not ratio, often sets the floor. The arithmetic is the argument.

Two API shapes matter here: block (whole buffer at once, output size known up front) and streaming (bounded memory, data arrives incrementally). Random access into a large compressed asset needs seekable framing (independent blocks); a single monolithic stream forces decode-from-the-start, which is why the packaging step lays assets out in independently decodable chunks.

07Oodle & console hardware

The games industry leaned into the decode-speed argument. RAD's Oodle suite (the Kraken codec and relatives) is a high-ratio-yet-fast LZ-family compressor distributed with Unreal Engine^[10], built on the premise that the decoder should never be the load bottleneck^[9].

Consoles took it further into silicon. The PlayStation 5's SSD runs at a raw 5.5 GB/s, and a dedicated hardware decompression unit in its I/O complex decodes Kraken transparently at load (Mark Cerny called it "zlib's smarter cousin"), yielding roughly 8 to 9 GB/s of decompressed output^[11].

08GPU texture compression

This is the other world. BCn and ASTC are lossy, fixed-rate, block-based formats. Each fixed-size texel block (4×4 for BCn) encodes to a fixed number of bits, and the decisive property is that the texture stays compressed in VRAM and the GPU's texture units sample it directly, decoding just the block they touch^[12][13].

Fixed rate plus block layout is what enables that random access: to sample a texel, the GPU finds its 4×4 block and decodes only that block in the sampler. A variable-rate format like DEFLATE's output can't address an arbitrary texel in O(1), which is exactly why general-purpose codecs can't serve as a runtime texture format^[14].

Wrong answers, and why: when the decoder is the bottleneck a higher-ratio/slower codec hurts; the GPU can't sample a general-purpose stream at all; and the texture-format distinction is about fixed-rate random access, not which one is lossy.

09Pitfalls

10What's next

Resources are handled: streamed, cooked, referenced, packaged, and compressed. Now the engine can finally draw. The next phase is rendering, starting with The GPU & Graphics Pipeline and then your first triangle in Vulkan, which consumes the cooked meshes and the BCn textures this phase produced. The full path is on the series hub.

1. Claude E. Shannon. "A Mathematical Theory of Communication." Bell System Technical Journal, 1948. overview. The source-coding theorem: average code length is lower-bounded by entropy.
2. Jacob Ziv and Abraham Lempel. "A Universal Algorithm for Sequential Data Compression." IEEE Trans. Information Theory 23(3), 1977. ethw.org. The sliding-window back-reference scheme.
3. David A. Huffman. "A Method for the Construction of Minimum-Redundancy Codes." Proc. IRE 40(9), 1952. overview. Optimal integer-length prefix codes.
4. Jarosław Duda. "Asymmetric numeral systems." arXiv:1311.2540, 2013. arxiv.org. Arithmetic-class ratio at table-lookup speed; the entropy back-end in zstd.
5. L. Peter Deutsch. "DEFLATE Compressed Data Format Specification," RFC 1951, 1996. rfc-editor.org. DEFLATE = LZ77 + Huffman; the 32 KB window; the three block types.
6. Yann Collet and Murray Kucherawy. "Zstandard Compression," RFC 8878, 2021; and the zstd project site. Tunable levels (incl. negative), the benchmark table, the ANS back-end.
7. Yann Collet. LZ4. github.com/lz4/lz4. Very fast LZ77-family codec; decode approaching RAM-bandwidth limits; the safe decoder API.
8. Jyrki Alakuijala and Zoltán Szabadka. "Brotli Compressed Data Format," RFC 7932, 2016. rfc-editor.org. LZ77 + Huffman + context modeling and a static web dictionary.
9. Charles Bloom (RAD Game Tools). "How Oodle Kraken and Oodle Texture supercharge the IO system of the PS5." cbloomrants.blogspot.com. The decoder-never-the-bottleneck design; the comment thread where the "9 Zen 2 cores" framing is disputed.
10. RAD Game Tools / Epic. Oodle, and its inclusion in Unreal Engine. radgametools.com. The Kraken family; cross-platform, smaller downloads and faster loads.
11. Mark Cerny. "The Road to PS5" (2020), as reported by VentureBeat and Digital Foundry. venturebeat.com. 5.5 GB/s SSD; a dedicated I/O-complex decompressor for Kraken; ~8 to 9 GB/s decompressed.
12. The Khronos Group. Khronos Data Format Specification (BC1 through BC7 / BPTC block decoding). registry.khronos.org. Fixed-size 4×4 blocks, 64/128-bit encodings, lossy.
13. "S3 Texture Compression." Wikipedia. en.wikipedia.org. Fixed-rate, random pixel access, stays compressed in VRAM; the DXT ratios.
14. The Khronos Group / Arm. Adaptive Scalable Texture Compression (ASTC). overview. 128-bit blocks, selectable block sizes (4×4 to 12×12), per-block adaptive, lossy.