Data Compression for Games
Your game is a 60 GB download, and players with fast SSDs still sit on loading screens. Compression can help with both, but only as a trade: it spends CPU time so fewer bytes cross the disk and the network. This page shows what compression can and can't shrink, how LZ77 and Huffman coding turn repetition into fewer bits, how to pick between zstd, LZ4 and their relatives, and why on a fast drive the decoder's speed, more often than its ratio, decides your load time. GPU texture compression is a separate tool with opposite rules, and it gets its own section at the end.
- Estimate whether compression will speed up or slow down a load, from the disk speed, the ratio and the decoder's speed.
- Compute a source's entropy, the floor no lossless coder beats, and spot data that won't shrink before you spend CPU on it.
- Trace how LZ77 back-references and Huffman codes turn repeated, lopsided data into fewer bits.
- Choose between LZ4, zstd levels, DEFLATE and Brotli for a download, a package and a load path.
- Explain why runtime textures use BCn or ASTC instead of zstd, and how the two stack in a shipped package.
01Why compress
The same week, two complaints land: the download is too big, and loading takes too long. Compression can fix both. A smaller download and package fits storefront and patch budgets. Higher effective load bandwidth comes from reading fewer bytes off disk and inflating them in RAM. Both payoffs come from the same trade of CPU for I/O, and for loading it only pays when the load is I/O-bound (waiting on the disk, not the CPU) and the decoder keeps up with the disk.
Worked example
A level's data is 2 GB, and a SATA SSD reads about 0.5 GB/s, so loading it raw takes 4 s. Say it compresses 3:1, which is roughly what zstd at level 3 gets on the Silesia benchmark corpus[15]. Now the disk only reads 0.67 GB, which takes 1.3 s. One core decodes zstd at about 1.25 GB/s of output, so rebuilding the 2 GB takes 1.6 s. If you decode each chunk while the disk reads the next one, the load takes about as long as the slower of the two jobs: 1.6 s instead of 4 s, and the download is a third the size.
There are two different worlds here, and they're easy to blur. General-purpose lossless compression, which gives back exactly the bytes you put in (zstd, LZ4, DEFLATE, Oodle Kraken) shrinks meshes, audio data, levels, and the package itself; it is decompressed to RAM before use. (BCn, ASTC) is lossy, fixed-ratio, and stays compressed in VRAM, the graphics card's memory, where the GPU samples it directly. The general-purpose story comes first; the texture story is fenced off in §8.
Compression doesn't always speed up loads. On a fast NVMe drive, an SSD that reads several gigabytes a second, a slow decoder becomes the bottleneck, and loading can end up slower than reading the data uncompressed. Decode speed gets its own section (§6) for that reason.
02What compression can't do
Someone suggests running zstd over the game's videos and music to cut the download. Those files are already compressed (MP4, Ogg, JPEG), and the pass saves almost nothing. The reason is a hard floor. Shannon's source-coding theorem says no lossless coder can, on average over a source, use fewer bits per symbol than the source's : the average amount of surprise per symbol, measured in bits[1].
The intuition: data where a few values show up most of the time is predictable, so a coder can give the common values short codes and the rare ones long codes. Data where every value is equally likely gives the coder nothing to exploit. Compressed files look like that, because squeezing out the predictability is exactly what the first compressor did, and good encryption makes its output look random on purpose.
Worked example
A mask texture stores one byte per pixel: 90% of pixels are 0 and 10% are 255. If each pixel is picked independently with those odds, its entropy is 0.9 × log₂(1 ÷ 0.9) + 0.1 × log₂(1 ÷ 0.1) = 0.9 × 0.152 + 0.1 × 3.32 = 0.47 bits per pixel. The file spends 8 bits per pixel, so a good coder can get within reach of a 17:1 ratio. Now take bytes from an encrypted file, where all 256 values are equally likely: each one carries log₂ 256 = 8 bits, the same 8 bits it already uses, and no lossless coder can shrink it on average.
Entropy comes from how often each symbol appears. This is the formula behind the 0.47 above:
In words: for each symbol, work out how many bits it's worth (the rarer it is, the more bits), weight that by how often it shows up, and add the results. The total is the average bits per symbol of the best possible code for data with those odds. Hover any term to see what it stands for.
- The bound is on the average over the source, not any single message. One lucky file can come out smaller.
- High-entropy data, such as already-compressed or encrypted bytes, can't be losslessly shrunk. And by the pigeonhole principle (there are fewer short outputs than long inputs) 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 throwing information away. That's a different game; the entropy floor is about lossless.
Why no coder can shrink every input
Count them. There are 2n different inputs of n bits, but only 20 + 21 + … + 2n−1 = 2n − 1 bit strings shorter than n bits. A lossless coder has to map different inputs to different outputs, so at least one n-bit input has no shorter output left to go to. A coder that shrinks some inputs has used up short outputs that other inputs needed, and those inputs come out the same size or longer.
Run-length encoding (RLE) is the simplest coder to see both sides of this. It replaces each run of a repeated byte with a (count, value) pair. A 64-pixel mask row of 60 zeros then 4 bytes of 255 becomes (60, 0) (4, 255): 4 bytes instead of 64. On data with no runs it expands: ABCD becomes 1A1B1C1D, twice the size.
03LZ77: the sliding window
A level file repeats itself constantly: the same component names, the same vertex layout, the same material block on hundreds of props. A coder that only counts how often each byte appears can't see that a 40-byte block already appeared 300 bytes earlier. (Ziv and Lempel, 1977) can. It encodes the input as a mix of literals (raw bytes) and back-references: a (distance, length) pair that says "copy length bytes from distance bytes back." The copy comes from a sliding window, the last few kilobytes or megabytes of output the decoder has already produced[2].
Worked example
Encode blah blah blah, 14 characters. The first five (b, l, a, h and the space) have nothing earlier to match, so they go out as literals. At position 5 the encoder finds blah blah starting 5 characters back and emits one token, (distance 5, length 9). The length is longer than the distance, so the decoder copies bytes it has only just written: it copies blah , then copies that copy. In the widget's cost model below (9 bits per literal, 18 bits per match) that's 5 × 9 + 18 = 63 bits, about 8 bytes for 14.
- 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, as in the example: a length greater than the distance is legal, and it's how runs get encoded.
- LZ77 is a family, not one format: zstd, LZ4, DEFLATE, Brotli, and Oodle Kraken are all LZ77-based but can't read each other's output. The window is bounded, and its size is a knob that trades ratio against memory.
The widget runs the encoder over a string and slides the window as it scans:
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
}
This finder scans every window position naively, O(n·window·match length); real codecs find candidates with hash chains, binary trees, or suffix structures, and add lazy matching, which holds off on a match for one position in case the next one starts a longer match. It emits no actual bitstream (no LZSS flag bits saying whether each token is a literal or a match, no following entropy stage), ignores match-length caps, and there's no decoder, let alone a bounds-checked one that can survive corrupt input. It exists only to make the mechanism visible.
04Entropy coding
After LZ77, the token stream is still lopsided: a few literal bytes and match lengths come up far more often than the rest, yet a plain format spends the same number of bits on each. An entropy coder fixes that by giving each symbol a bit pattern sized to how often it appears, pushing the average toward the entropy floor. Huffman (1952) builds the best possible for a set of frequencies: frequent symbols get shorter codes, and no code is the start of another, so the decoder always knows where one symbol ends[3].
The construction is short. Put every symbol in a pile with its count, take out the two rarest, join them under a new node whose count is their sum, and put that node back. Repeat until one tree is left. Each symbol's code is its path from the root: 0 for a left branch, 1 for a right one. The rarest symbols were joined first, so they sit deepest and get the longest codes.
Worked example
Take the widget's starting counts: 76 symbols, A 35 times, B 20, C 12, D 6 and E 3. Five symbols need 3 bits each in a fixed-width code, so 76 × 3 = 228 bits. Huffman gives A = 0, B = 10, C = 111, D = 1101 and E = 1100. That's 35 × 1 + 20 × 2 + 12 × 3 + 6 × 4 + 3 × 4 = 147 bits, or 1.93 bits per symbol. The entropy of those counts is 1.92 bits per symbol, about 146 bits in total, so Huffman lands within 2 bits of the floor across all 76 symbols.
It must spend a whole number of bits per symbol, so a symbol with probability 0.9 (which "wants" about 0.15 bits) still costs a full bit. Arithmetic coding, which encodes a whole message as one fractional number, its integer cousin range coding, and modern ANS (asymmetric numeral systems, Duda 2013) let a symbol cost a fraction of a bit. ANS does it at table-lookup speed, which is why it's an entropy back-end in zstd[4]. And entropy coding composes with LZ; it isn't an alternative to it. DEFLATE and zstd both run LZ first, then an entropy coder.
The widget builds the tree from five symbol counts, rarest symbols pushed deepest:
05DEFLATE and the modern codecs
You have to pick a codec for the shipped package, and the benchmarks rank them differently depending on whether they sort by size or by speed. Every codec here is LZ77 followed by an entropy stage, except LZ4, which skips the entropy stage for speed. 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-way 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 entropy coder (zstd's table-driven form of ANS) plus Huffman for literals[6].
- Brotli: competitive ratios, but in lzbench it decodes roughly a third as fast as zstd, and its built-in static dictionary is tuned for web text specifically[8][15].
// 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
Worked example
Take 1 GB of data that compresses like the Silesia benchmark corpus and decode it on one core, using the lzbench numbers in the chart below[15]. LZ4 stores it in 476 MB and decodes it in 0.27 s. zstd at level 3 stores it in 328 MB and decodes it in 0.80 s. DEFLATE (zlib level 6) is about the same size as zstd, 322 MB, but takes 2.9 s. Brotli at level 5 is the smallest, 281 MB, and takes 2.2 s. So zstd matches DEFLATE's size in about a quarter of the decode time, and LZ4 gives up about 150 MB to decode three times faster than zstd.
The chart plots ratio against decode throughput, from lzbench measurements on the Silesia corpus on one core of an AMD EPYC 9554[15]:
06Decode speed sets load time
You move the game to a 5 GB/s NVMe drive and loads barely improve. The profiler shows the disk idle most of the time and one core busy decompressing. Loading compressed data is a two-stage pipeline: the disk delivers compressed bytes, and the decoder turns them back into the original. When the two overlap, chunk by chunk, the slower stage sets the pace. On a slow drive that's the disk, and a better ratio helps. On a fast drive it's often the decoder, and then decode throughput matters more than ratio.
The load time is the larger of the two stage times:
In words: the disk's time is the compressed size over the disk speed, the decoder's time is the uncompressed size over the decode speed of all the cores working on it, and the load takes about as long as the slower one. A better ratio only shrinks the first term; a faster decoder or more cores shrinks the second. Hover any term to see what it stands for.
Worked example
Load 1 GB from a 5 GB/s NVMe, using the lzbench decode speeds from the chart above. Uncompressed, the read takes 1 ÷ 5 = 0.2 s. With zstd at level 3 (3.05:1) the read drops to 0.07 s, but one core needs 0.80 s to decode, so the load takes 0.80 s: four times slower than not compressing at all. zlib is worse, at 2.9 s. Split the data into independent chunks and decode zstd on 4 cores, and the decode drops to 0.20 s, level with the raw read, while you keep the smaller download. On the 0.5 GB/s SATA drive from §1, the same zstd stream was the faster option. Whether compression helps a load depends on the drive as much as on the codec.
That's why LZ4 and zstd are tuned for decode speed, and why a codec that's best for download size can be the wrong choice for load time. Two API shapes matter here: block (whole buffer at once, output size known up front) and streaming (bounded memory, data arrives a piece at a time). Random access into a large compressed asset needs seekable framing: the data is compressed as independent blocks, so you can start decoding at any block. 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
A console SSD that reads 5.5 GB/s needs a decoder that keeps up, and on the CPU that gets expensive fast. The games industry leaned into the decode-speed argument. RAD's Oodle suite (the Kraken codec and relatives) is a family of high-ratio-yet-fast LZ compressors, now distributed with Unreal Engine[10]. On PS5, RAD describes tuning Kraken streams so the decoder is never the bottleneck: when it has time to spare against the 5.5 GB/s drive, the encoder switches on slower modes that compress better[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, the custom block between the SSD and main memory, decodes Kraken transparently at load (Mark Cerny called Kraken "zlib's smarter cousin"). Sony quotes typically 8 to 9 GB/s of decompressed output, based on the roughly 1.5:1 ratios games averaged, and up to 22 GB/s on data that compresses particularly well[11][9].
Worked example
At 1.5:1, a 5.5 GB/s drive delivers data that decodes to 5.5 × 1.5 = 8.25 GB/s. Use zstd's lzbench speed as a yardstick: about 1.25 GB/s of output per core, measured on a modern server core. Keeping up in software would take 8.25 ÷ 1.25, more than six cores doing nothing but decompression, out of the console's eight[11]. Kraken is a different codec with its own speed, but the scale of the problem is the same, and it's the problem the hardware decoder removes.
The widely quoted line that the decoder is "equivalent to 9 Zen 2 cores" (Zen 2 is the AMD core design in both current consoles) is, in the words of RAD's Fabian Giesen, "quoting wildly out of context": fixed-function hardware, which does one job and nothing else, isn't a substitute for general-purpose cores, so treat it as a soundbite, not a measured equivalence[9]. And Oodle Texture is a separate product from Oodle Kraken: an encoder that makes BCn texture data compress better under a following LZ pass, not itself a GPU texture format. On one game's textures, Bloom reports Kraken alone at 1.82:1 and Oodle Texture plus Kraken at 3.16:1[9]: 1 GB of textures goes to about 549 MB in the first case and about 316 MB in the second. That distinction leads into the last section.
08GPU texture compression
A 2048 × 2048 texture is 16 MiB of RGBA in VRAM, and a level loads hundreds of them. zstd would shrink each one on disk, but the GPU can't sample a zstd stream, so in VRAM it would be back to 16 MiB. This is the other world. BCn (BC1 to BC7) and ASTC are lossy, fixed-rate, block-based formats. Each fixed-size block of texels (the texture's pixels; 4×4 for BCn) encodes to a fixed number of bits. The decisive property is that the texture stays compressed in VRAM and the GPU's texture units sample it directly: the hardware that reads textures decodes just the block it touches[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 why general-purpose codecs can't serve as a runtime texture format[14].
Worked example
BC1 stores each 4×4 block in 8 bytes and BC7 in 16 bytes[12]. The 2048 × 2048 texture is 512 × 512 blocks, so it takes 2 MiB as BC1 (8:1 against RGBA) or 4 MiB as BC7 (4:1), whatever the image shows. To read texel (1000, 517) from the BC7 version, the GPU divides by 4 to get block (250, 129). In a simple row-major block layout that's block 129 × 512 + 250 = 66,298, at byte 66,298 × 16 = 1,060,768. Real GPUs also rearrange blocks in memory for locality, but the address is still a few integer operations. In a zstd stream the same texel's bytes sit at an offset you can only learn by decoding from the start of the stream, or of the independent block it sits in.
You ship BCn textures and pack the whole package with a lossless codec for download size (Oodle Texture exists to make that second pass work better). And recall the zero-copy point (using data where it already sits, with no copy) from the Asset Pipeline: a BCn blob is already in a GPU-consumable layout and can be uploaded largely as-is, but a zstd-compressed asset cannot be memory-mapped (mapped from the file straight into memory) and used in place; it has to be decoded into a separate buffer first.
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 & the Graphics Pipeline and then a first triangle in Vulkan; the rendering chapters after it consume the cooked meshes and BCn textures this phase produced. The full path is on the series hub.
- 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.
- 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.
- David A. Huffman. "A Method for the Construction of Minimum-Redundancy Codes." Proc. IRE 40(9), 1952. overview. Optimal integer-length prefix codes.
- 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.
- 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.
- Yann Collet and Murray Kucherawy. "Zstandard Compression and the 'application/zstd' Media Type," RFC 8878, 2021; and the zstd project site. Tunable levels (including negative ones), FSE and Huffman entropy stages.
- Yann Collet. LZ4. github.com/lz4/lz4. Very fast LZ77-family codec; decode approaching RAM-bandwidth limits; the safe decoder API.
- 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.
- Charles Bloom (RAD Game Tools). "How Oodle Kraken and Oodle Texture supercharge the IO system of the Sony PS5," 2020. cbloomrants.blogspot.com. Tuning Kraken streams so the PS5 decoder is never the bottleneck; Kraken 1.82:1 vs. Oodle Texture + Kraken 3.16:1 on one game's textures; Fabian Giesen's comment calling the "9 Zen 2 cores" line out of context.
- RAD Game Tools / Epic. Oodle, and its inclusion in Unreal Engine. radgametools.com. The Kraken family; cross-platform, smaller downloads and faster loads.
- Mark Cerny. "The Road to PS5," Sony Interactive Entertainment, 2020. YouTube; VentureBeat's write-up, archived copy. 5.5 GB/s SSD; the Kraken decoder in the I/O complex, typically 8 to 9 GB/s out and up to 22 GB/s; "zlib's smarter cousin."
- 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.
- "S3 Texture Compression." Wikipedia. en.wikipedia.org. Fixed-rate, random pixel access, stays compressed in VRAM; the DXT ratios.
- 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.
- Przemysław Skibiński (inikep). lzbench, an in-memory benchmark of open-source compressors. github.com/inikep/lzbench. The widget's ratio and single-core decode speeds: Silesia corpus on an AMD EPYC 9554 (zstd 1.5.6, LZ4 1.10.0, zlib 1.3.1, Brotli 1.1.0).