lz

import lz from "lz";

// Huffman code lengths (at most 15 bits) and their codes for four symbols
var freq: [4]i32 = [10, 1, 4, 2];
var lens: [4]u8;
var codes: [4]u16;
lz.huff_lengths(&freq[0], 4, 15, &lens[0]);     // lens: 1, 3, 2, 3
lz.huff_codes(&lens[0], 4, &codes[0]);

// written lowest bit first
var out: lz.BitOut = lz.bit_out(64);
defer out.free();
for (s in [0, 2, 3, 1]) { out.put(codes[s] as i64, lens[s] as i64); }
out.flush();
let packed: []const u8 = out.output();          // 2 bytes

lz holds what compress (deflate, gzip, zlib) and brotli are both built from: Huffman code construction, a bit writer, a bit reader that can rewind, and LZ77 match finding over hash chains. Use it to write a codec of your own in the same family; to compress or decompress data, use compress or brotli.

Everything here gives the same result in the VM and natively, so a compressor built on it produces the same bytes everywhere.

lz is a pure module. BitOut, BitIn and Matcher hold heap memory: call free() on each when done (a second free() does nothing).

Huffman codes

huff_lengths

pub fn huff_lengths(freq: *const i32, n: i64, limit: i64, lens: *u8) -> i64

Code lengths for the symbols 0..n from their counts freq[0..n], none longer than limit bits, into lens[0..n]. Returns how many symbols have a count.

• Frequent symbols get short codes: a Huffman tree’s depths, shortened to the limit where needed.
• The code is always complete. A symbol alone gets a partner of length 1 (symbol 0, or 1 when it is 0 itself), since a decoder needs at least two codes. With no counts at all every length is 0.
• Symbols with equal counts are ordered by value, so the lengths are the same on every platform.

n is the alphabet size, up to HUFF_MAX (704). It traps when n is outside 2..HUFF_MAX or limit outside 1..15.

var f: [5]i32 = [10, 1, 1, 2, 4];
var l: [5]u8;
let used: i64 = lz.huff_lengths(&f[0], 5, 15, &l[0]);   // 5; l: 1, 4, 4, 3, 2
lz.huff_lengths(&f[0], 5, 3, &l[0]);                    // l: 1, 3, 3, 3, 3

huff_codes

pub fn huff_codes(lens: *const u8, n: i64, out: *u16)

The canonical codes of lens[0..n] (as RFC 1951 assigns them) into out[0..n], bit-reversed so that they are written lowest bit first with BitOut.put. A symbol of length 0 gets 0.

var l: [8]u8 = [3, 3, 3, 3, 3, 2, 4, 4];
var c: [8]u16;
lz.huff_codes(&l[0], 8, &c[0]);     // c[5] is 0 (code 00), c[0] is 2 (code 010)

Writing bits: BitOut

pub struct BitOut { buf: *u8; len: i64; cap: i64; off: i64; acc: u64; nacc: i64; }
pub fn bit_out(cap: i64) -> BitOut

A growable output written lowest bit first. Put bits in, take whole bytes out with output() and advance(): the buffer drops what was taken and grows as needed. cap is the starting size (at least 16).

A mark lets a compressor try an encoding, measure it, and go back:

let m: lz.OutMark = out.mark();
write_compressed(&out);
if (out.bits_since(m) > stored_bits) {
    out.rewind(m);                  // what came after the mark is gone
    write_stored(&out);
}

A mark stays valid as long as nothing is taken with advance() after it.

Reading bits: BitIn

pub struct BitIn { buf: *u8; cap: i64; len: i64; pos: i64; bits: u64; nbits: i64; }
pub fn bit_in(cap: i64) -> BitIn

An input buffer of up to cap bytes, read lowest bit first. Bytes are loaded from buf[pos..len] into bits as they are needed.

A streaming decoder marks before each step and rewinds when the step runs out of input, then reads it again when more has been appended:

let at: lz.InMark = src.mark();
if (!src.need(14)) { src.rewind(at); return NEED_MORE; }
let hlit: i64 = src.take(5) + 257;

Matching: Matcher

pub fn matcher(width: i64, hash_n: i64, win: i64, max_chain: i64, nice: i64) -> Matcher
pub fn match_len(src: *const u8, i: i64, d: i64, room: i64) -> i64

Hash chains over the positions of your own buffer, for LZ77: each position’s first width bytes (3 or 4) are hashed into hash_n chains (a power of two, 2^8 to 2^24) over a window of win positions (a power of two). A search looks at up to max_chain earlier positions and stops at a match of nice bytes.

match_len is how far the bytes at i and i - d agree, up to room.

let s: []const u8 = "abcdeXabcdYabcdeZabcde";
var m: lz.Matcher = lz.matcher(3, 4096, 32768, 64, 258);
defer m.free();
m.insert_to(&s[0], s.len, 16);
var d: i64 = 0;
let n: i64 = m.longest(&s[0], 17, 5, 2, 32768, &d);    // 5, d is 6

Whole buffers

pub enum LzError : u8 { TooLarge = 1: "output over the limit"; }
pub fn grow_to(v: *collections.Vec_u8, nc: i64)
pub fn drain(out: *collections.Vec_u8, max_out: i64, step: i64, ctx: *u8,
             read: fn(*u8, []u8) -> i64) -> i64 or LzError

• grow_to gives v a buffer of nc bytes, keeping its contents.
• drain reads what a decoder has ready into out until read returns 0: read(ctx, dst) is the decoder’s read with the decoder as ctx. out grows by at least step bytes at a time and never past max_out. It returns how many bytes came, or TooLarge when out is full at max_out and the decoder still has a byte. A decompression bomb stops there, without allocating past the limit.

fn read_of(z: *u8, dst: []u8) -> i64 { return (z as *MyDecoder).read(dst); }

let got: i64 = lz.drain(&out, max_out, 65536, &dec as *u8, read_of) or {
    return MyError.TooLarge;
};

Last modified: 2026-10-26 10:32:19 UTC