How to encode lossless WebP in a Vulkan compute shader — flat literal Huffman codes

PNG has stored blocks; WebP lossless (VP8L) has no uncompressed escape hatch — every pixel goes through prefix codes. That looks GPU- hostile until you notice the trick: declare a flat 8-bit code where all 256 literals share one code length. The canonical codes then fall out as code(v) = v, every pixel costs exactly 24 bits (green + red + blue codes; alpha collapses to a single-symbol tree that emits zero bits), and every pixel lands at the fixed bit offset headerBits + i*24. One dispatch writes the whole bitstream with atomicOr — no histogram, no prefix sum, no LZ77, no transforms.

The companion example lives in vk-tut/p79_webp and its check.py verifies a bit-exact decode through real libwebp.

The VP8L bitstream shape

vp8l.txt

8b  signature 0x2f
14b width-1, 14b height-1, 1b alpha_used, 3b version(0)
1b  transforms-present = 0
1b  color-cache = 0
1b  meta-huffman = 0
5 prefix trees: green(280) red(256) blue(256) alpha(256) dist(40)
    green/red/blue: "normal" code-length-coded tree, all literals len 8
    alpha/dist:     "simple" 1-symbol trees
then W*H * 24 bits of pixel data

The header is 983 bits (~123 bytes) — written once on the CPU into the shared output buffer; the GPU fills the rest.

Emitting a flat tree — the spec landmines

The “normal code length code” is where the encoder needs care — the code lengths are themselves prefix-coded, and two spec details bite:

tree.cpp

// kCodeLengthCodeOrder — symbol 8 sits at index 11, so only
// num_code_lengths = 12 entries are needed (4 + ReadBits(4)):
static const int order[19] = {17, 18, 0, 1, 2, 3, 4, 5, 16, 6,
                              7, 8, 9, 10, 11, 12, 13, 14, 15};
bw.put(8, 4);                          // num_code_lengths = 12
for (int i = 0; i < 12; ++i)
    bw.put(order[i] == 0 || order[i] == 8 ? 1u : 0u, 3);  // 3 BITS each
bw.put(0, 1);                          // full alphabet, no truncation
for (int i = 0; i < alphabet; ++i)
    bw.put(i < 256 ? 1u : 0u, 1);      // CL code: '1' = len 8, '0' = none

Two corrections vs. a naive reading:

CL lengths are 3 bits each, and only 4 + ReadBits(4) of them are sent — not all 19, not 4 bits each.
The order table has 16 at index 8 (it is not the DEFLATE order).
Kraft check: 256 × 2⁻⁸ = 1 → the literal code is exactly complete; the 24 length symbols in the green alphabet stay uncoded.

The GPU side — 24 bits per pixel, fixed offset

emit.comp

layout(set=0,binding=0) readonly buffer Src { uint src[]; };
layout(set=0,binding=1) buffer Out { uint outb[]; };

void main() {
    uint i = gl_GlobalInvocationID.x;
    if (i >= w * h) return;
    uint px = src[i];                     // RGBA8
    // per-pixel order: green, red, blue (alpha tree: 0 bits).
    // Huffman codes are emitted MSB-first into the LSB-first stream
    // -> bit-reverse each byte:
    uint g = bitfieldReverse((px >> 8)  & 0xffu) >> 24;
    uint r = bitfieldReverse(px         & 0xffu) >> 24;
    uint b = bitfieldReverse((px >> 16) & 0xffu) >> 24;
    uint bits = g | (r << 8) | (b << 16);
    uint bitpos = bitBase + i * 24u;
    uint wi = bitpos >> 5, sh = bitpos & 31u;
    atomicOr(outb[wi], bits << sh);
    if (sh > 8u) atomicOr(outb[wi + 1u], bits >> (32u - sh));
}

atomicOr handles the word-straddling (bitpos isn’t word-aligned); the buffer was zeroed and header-written before dispatch.

RIFF container

container.cpp

tag("RIFF"); le32(riffSize); tag("WEBP");
tag("VP8L"); le32(STREAM_BYTES);
f.write(stream, STREAM_BYTES);
if (STREAM_BYTES & 1) f.put(0);         // RIFF pad byte

Practical rules

This encoder is a format exercise, not a compressor — flat literal codes mean ~24 bpp output (raw-size). The value is the pattern: fixed bit offsets + atomicOr = parallel entropy coding. A real encoder would histogram on GPU (atomics), build lengths on CPU, prefix-sum on GPU, then emit — same skeleton, variable codes.
The literal order is green, red, blue, alpha — unusual; the spec packs pixels ARGB-in-memory but entropy-codes green first.
Single-symbol trees consume zero bits per read — that’s what makes alpha free for opaque images.
Verify with an independent decoder — check.py decodes via PIL/libwebp and diffs every pixel; the bitstream has enough sharp edges (bit order, CL-code arity, num_code_lengths window) that a “looks plausible” header isn’t proof.
For lossy WebP the same trick doesn’t exist — VP8 macroblock coding is deeply serial; lossless literals-only is the parallel-friendly subset.