Smart Compression

The compressor makes two automatic decisions to avoid wasting CPU on data that won't benefit from compression:

compress(data, config)
  |
  data.len() < min_size? ── YES ──> store raw (algorithm=None)
  |
  NO
  |
  compress with LZ4 or Zstd
  |
  compressed.len() < data.len()? ── NO ──> store raw (algorithm=None)
  |
  YES
  |
  prepend header + compressed payload

LZ4-Style Compression

The LZ4 implementation uses a hash-chain approach with 4-byte minimum matches and a 4,096-entry hash table (12-bit). It scans the input for repeated byte sequences and encodes them as back-references (offset + length), falling back to literal byte runs for non-matching regions.

Token Format

Each sequence is encoded as a token byte followed by optional extra length bytes, literal data, a 2-byte back-reference offset, and optional extra match length bytes:

Token byte: [LLLL MMMM]
  LLLL = literal length (0-15, 15 means more bytes follow)
  MMMM = match length - 4 (0-15, 15 means more bytes follow)

Sequence layout:
  [token: 1B] [extra_lit_len: 0+B] [literals: varB]
  [offset: 2B LE] [extra_match_len: 0+B]

Extra length encoding:
  Emit 255 repeatedly until remainder < 255, then emit remainder.
  Example: length 300 = 15 + 255 + 30 → token(15) + [255, 30]

Hash Function

fn hash4(data: &[u8]) -> usize {
    let v = u32::from_le_bytes([data[0], data[1], data[2], data[3]]);
    (v.wrapping_mul(2654435761) >> 20) as usize
}

Uses the Knuth multiplicative hash (golden ratio constant 2654435761) with 12-bit output for the LZ4 hash table or 14-bit for the Zstd variant.

Zstd-Style Compression

The Zstd implementation uses the same core algorithm as LZ4 but with a larger hash table (16,384 entries, 14-bit) for better match finding. This trades slightly more memory for improved compression ratios on larger inputs. The encoded format is identical, so decompression uses the same decoder.

Decompression

Decompression reads the 5-byte header to determine the algorithm and expected output size, then decodes the token stream. The decoder validates bounds at every step: literal overflows, zero offsets, offset-exceeds-output, and length mismatches all return errors instead of panicking.

pub fn decompress(data: &[u8]) -> io::Result<Vec<u8>> {
    let algo = data[0];          // 0=None, 1=LZ4, 2=Zstd
    let uncompressed_len = u32::from_le_bytes(data[1..5]);
    let payload = &data[5..];

    match algo {
        0 => Ok(payload.to_vec()),       // Raw (no compression)
        1 => lz4_decompress(payload, len),  // LZ4 decode
        2 => lz4_decompress(payload, len),  // Zstd uses same decoder
    }
}

Test Coverage

The compression subsystem is covered by 9 tests verifying round-trip correctness, smart skip behavior, and edge cases.

Design Decisions