Wasm + Compression

Introduction

Data compression is a natural fit for WebAssembly. Compressing files, API payloads, or user data on the client side reduces upload bandwidth and latency. Rust's low-level control and zero-cost abstractions make it ideal for implementing compression algorithms that run efficiently in the browser.

Why compress client-side?

Without client-side compression:
┌──────────┐   100MB raw    ┌──────────┐
│  Browser  │──────────────>│  Server   │
│           │   slow upload  │           │
└──────────┘               └──────────┘

With client-side Wasm compression:
┌──────────┐   compress    ┌──────────┐   30MB     ┌──────────┐
│  Browser  │─────────────>│  Wasm    │──────────>│  Server   │
│           │  (CPU work)  │  Engine  │  fast!    │           │
└──────────┘              └──────────┘           └──────────┘

Benefits:

• Reduced bandwidth -- smaller payloads mean faster transfers
• Lower server costs -- server does not need to decompress or compress
• Works offline -- compression runs entirely in the browser
• Privacy -- data can be compressed before encryption, never sent raw

Compression algorithm overview

Run-Length Encoding (RLE)

RLE is the simplest compression algorithm. It replaces consecutive repeated bytes with a (byte, count) pair:

Input:  A A A A A B B C C C C
Output: (A,5) (B,2) (C,4)

Bytes:  11 → 6  (45% reduction)

RLE works well when data has many consecutive repeated values (images with solid colors, sparse data). It performs poorly on data without repetition -- in the worst case, it doubles the size:

Input:  A B C D E F    (6 bytes, no repetition)
Output: (A,1)(B,1)(C,1)(D,1)(E,1)(F,1)  (12 bytes!)

LZ77: dictionary-based compression

LZ77 is the foundation of modern compression (gzip, DEFLATE, zlib). It works by finding repeated sequences and replacing them with back-references:

Sliding window concept:

Position:  0 1 2 3 4 5 6 7 8 9 ...
Data:      A B C A B C A B C X

At position 3, "ABC" matches position 0:
  → Match(offset=3, length=3)

At position 6, "ABC" matches position 3:
  → Match(offset=3, length=3)

Result: Lit(A) Lit(B) Lit(C) Match(3,3) Match(3,3) Lit(X)
         3 bytes          +   6 bytes    +  1 byte  = 10 bytes
         vs original 10 bytes → but with overhead...

The sliding window is crucial -- it limits how far back the algorithm searches, trading compression ratio for speed:

Huffman coding basics

Huffman coding assigns shorter bit sequences to more frequent bytes and longer sequences to rare bytes:

Example: "AAABBC"
Frequencies: A=3, B=2, C=1

Fixed encoding (8 bits each): 6 × 8 = 48 bits
Huffman encoding:
  A → 0       (1 bit)    × 3 = 3 bits
  B → 10      (2 bits)   × 2 = 4 bits
  C → 11      (2 bits)   × 1 = 2 bits
                          Total = 9 bits

Huffman tree:
        *
       / \
      A   *
         / \
        B   C

DEFLATE (used in gzip) combines LZ77 + Huffman coding for its two-stage compression pipeline.

The flate2 crate for production use

For real applications, the flate2 crate provides DEFLATE/gzip/zlib compression and compiles cleanly to Wasm:

[dependencies]
flate2 = "1.0"
wasm-bindgen = "0.2"

// Production code (requires flate2 crate)
use flate2::write::GzEncoder;
use flate2::read::GzDecoder;
use flate2::Compression;
use std::io::{Write, Read};

fn compress_gzip(data: &[u8]) -> Vec<u8> {
    let mut encoder = GzEncoder::new(Vec::new(), Compression::default());
    encoder.write_all(data).unwrap();
    encoder.finish().unwrap()
}

fn decompress_gzip(data: &[u8]) -> Vec<u8> {
    let mut decoder = GzDecoder::new(data);
    let mut result = Vec::new();
    decoder.read_to_end(&mut result).unwrap();
    result
}

When to compress client-side vs server-side

Performance benchmarks: Wasm vs JavaScript

Compressing a 1MB JSON file:

┌──────────────────────────┬────────┬────────────┐
│ Implementation           │ Time   │ Output size│
├──────────────────────────┼────────┼────────────┤
│ JS pako (zlib)           │ 85ms   │ 198KB      │
│ Rust flate2 (Wasm)       │ 32ms   │ 195KB      │
│ CompressionStream API    │ 28ms   │ 196KB      │
│ Rust lz4_flex (Wasm)     │ 8ms    │ 310KB      │
└──────────────────────────┴────────┴────────────┘

Rust/Wasm is 2-3x faster than JavaScript for equivalent algorithms. The native CompressionStream API is competitive but only supports gzip/deflate and is not available in all browsers.

DEFLATE: how gzip actually works

DEFLATE is the algorithm inside gzip and zlib. It combines LZ77 and Huffman in a pipeline:

Raw data
   │
   ▼
┌──────────┐
│  LZ77    │  Find repeated sequences,
│  Pass    │  output literals + matches
└────┬─────┘
     │
     ▼
┌──────────┐
│ Huffman  │  Encode LZ77 output with
│  Pass    │  variable-length bit codes
└────┬─────┘
     │
     ▼
Compressed bitstream

The two passes complement each other: LZ77 removes spatial redundancy (repeated patterns), and Huffman removes statistical redundancy (uneven byte frequencies).

Try it

Extend the code to:

• Add a worst-case detector for RLE that falls back to raw storage when compression would increase size
• Implement a simple Huffman encoder that counts byte frequencies and builds a prefix code table
• Add a compression level parameter to LZ77 that controls the window size
• Benchmark your RLE and LZ77 against each other on different data patterns (random bytes vs repeated patterns)