zig-vp8

VP8 — the lossy bitstream inside a lossy WebP — for Zig.

It decodes key frames to pixels, and what comes out is bit for bit what libwebp produces — as samples, filtered or unfiltered, and as RGBA with either of libwebp's two chroma upsamplers.

var frame = try vp8.decode(gpa, chunk, .{});
defer frame.deinit(gpa);

where chunk is the payload of a VP8 chunk. vp8.decodeRgba goes the rest of the way and hands back four bytes a pixel.

Twenty-one real frames from cwebp are held against dwebp's output byte for byte: five reconstructions with the loop filter off, ten with it on across five qualities, two segment counts and three sharpness settings, and six RGBA conversions.

The API documentation is generated from the doc comments in the source.

What it reads today

The keyframe header, which gives the dimensions:

const header = try vp8.readHeader(&stream);
std.debug.print("{d}x{d}\n", .{ header.width, header.height });

Ten bytes: a three-byte frame tag carrying the frame type, the version, the show flag and the length of the first partition; a three-byte start code; and two fourteen-bit dimensions each with a two-bit display scale above it. The scale is carried rather than acted on — upscaling is a display decision and not a decoding one — because throwing it away silently would be worse than saying it is ignored.

An interframe is told apart from a malformed frame, which matters because a caller may reasonably meet either: a frame of video has no keyframe header to read and answers error.Unsupported, while something that is not a VP8 frame at all answers error.InvalidData.

The boolean entropy coder, which everything past those ten bytes is read through. It is a binary arithmetic coder rather than a bit reader: each call says how likely the bit is to be zero, out of 256, and a likely bit costs less than a whole one. Three things about it are worth knowing before reading the code.

The split is 1 + ((range - 1) * prob) / 256, and that 1 + is not rounding — it is what keeps the split strictly inside the interval, so neither branch is ever given nothing however extreme the probability. An encoder and a decoder that disagreed there would diverge on the first improbable bit.

SignedLit(n) is two's complement, which is not the shape any other signed field in VP8 takes: the specification starts the value at minus one when the top bit is set and shifts the rest in, so five bits of 10101 is -11 and not -5. Every other signed field is a magnitude followed by a sign.

And the specification's decoder reads past the end of its partition without noticing. This one supplies zeroes and records that it did, so a caller can ask afterwards whether what came out was in the file or was invented — while the decode still terminates, because the alternative is an error return on every one of the several million calls a frame makes.

It is tested against an encoder written from the same text: at every one of the 256 probabilities, what goes in comes out.

The first partition's header, which is everything a frame says about itself before it says anything about a pixel: the colour space and clamping, the segmentation map with its per-segment quantiser and filter adjustments, the loop filter's type, level and sharpness and its per-reference and per-mode deltas, how many token partitions the coefficients are split across, the five quantiser indices, and then a thousand and fifty-six flags saying which coefficient probabilities this frame replaces.

Two things Annex A of the RFC understates, and both would desynchronise a decoder rather than merely mislead it. The coefficient update flags are not L(1): Section 13.4 is the normative version and reads each at its own probability from a table, so a decoder reading them at even odds consumes the wrong number of bits. And a key frame resets the probabilities to their defaults before reading its own updates, so a frame that updates nothing still gets the defaults.

How a header parser is checked before there is a decoder

This is the awkward part of building a codec from the bottom: nothing here can read a real file yet, and a parser checked only against itself is checked against nothing.

What saves it is that cwebp puts three of these fields on its command line. -sharpness N is written into the header verbatim, so the fixtures include one encoded at each of 0, 3 and 7 and the parse must report them back — a bit layout adrift by one would not read three as three. -segments 1 against -segments 4 decides whether segmentation is enabled at all. And -q moves the quantiser index and nothing else in the header, so five fixtures up the quality ladder must parse to a descending sequence, with the ends more than twenty apart so that the ordering is not five readings of one number.

On top of that, a real header must end inside the partition that holds it and leave something behind, because the per-macroblock records follow it in the same bool stream.

The DCT coefficients. Sixteen a block, read in zigzag order, each a token from a twelve-value tree: end-of-block costs one bit, a zero two, a one three, and only a large coefficient costs anything like its magnitude. Which probabilities a token is read with depends on the plane, on the band the position falls in, and on what the previous coefficient was — or, for the first coefficient of a block, on how many of the block above and the block to the left held anything.

Two places where the RFC's pseudocode is not what it means. It sets prevCoeffWasZero = true unconditionally, which cannot be right: the whole point of the flag is that end-of-block cannot follow a zero, so the first branch of the tree is skipped only when the previous token really was one. And it writes block[i] in scan order when coefficients are stored in raster order, which is what the zigzag is for. The reference decoder in Section 20.16 has both right.

Round-tripped through a writer built from the same tree: every magnitude each of the twelve tokens can carry, at both ends of every category's range, in every plane and from every starting context. That writer found a real bug in itself twice over — extra bits written least significant first, and the end-of-block branch not skipped after a zero — and each showed up not as the coefficient that was wrong but as the next one, which is what a desynchronised arithmetic coder does.

Dequantisation and the two inverse transforms. What the token decoder produces is quantised levels; turning them into a residue means multiplying by a factor that depends on the plane and on whether it is the DC coefficient, and then running the block through a transform.

Two transforms, because when a macroblock's luma is predicted whole the sixteen luma blocks' DC coefficients are collected into a seventeenth block of their own and that one goes through an inverse Walsh–Hadamard transform rather than an inverse DCT. A flat macroblock then costs one block instead of sixteen, which is the entire reason for the arrangement.

The factors are not simply the tables. Y2's DC factor is doubled and its AC factor multiplied by 1.55 with a floor of 8, because a Y2 block holds what sixteen DC coefficients had in common and runs larger; chroma's DC factor is capped at 132, because chroma is subsampled and a coarse DC there shifts the colour of a whole region.

Both transforms are checked against their mathematical definitions written independently in floating point — the orthonormal 2-D inverse DCT scaled by a quarter, and the 2-D Hadamard over eight — rather than against the same butterflies twice. The integer DCT tracks its definition to within 1.25 counts and the Hadamard to within the half a count its rounding costs, which is enough to catch a mistyped constant or a transposed pass.

Everything in the transforms wraps on purpose. A dequantised coefficient is stored in sixteen signed bits and the second pass multiplies four times that by thirty-five thousand, so a coefficient near the top of its range overflows a thirty-two bit intermediate. The reference decoder is C and wraps there too, quietly and undefinedly. This wraps the same way and says so: a decoder handed a hostile file must have some defined answer, and the useful one is the answer everybody else gives.

Intra prediction, all fourteen modes. A macroblock's luma is predicted either whole — one 16×16 guess in one of four modes — or as sixteen 4×4 subblocks each with its own mode out of ten, six of which are diagonals at roughly ±27° and ±45°. Chroma is always whole, as two 8×8 blocks.

What is off the edge of the frame is the awkward part, and there is no single rule for it. v and h use an invented row of 127 above and an invented column of 129 to the left — two different values, which looks like a mistake and is not. dc uses neither: it averages whichever edge really exists, and with no neighbours at all fills with 128 flat. tm does use 127 and 129. A decoder that tidied any of that into one constant would be wrong along the top and left of every frame, subtly and everywhere.

The tests lean on properties rather than on tables of expected pixels: a flat edge must predict a flat block in every one of the fourteen modes, which catches an index reaching outside the neighbours it was given; each diagonal mode must be constant along its own diagonal, which catches two assignments swapped; and the 4×4 and 16×16 true-motion modes must agree where they overlap, which checks the two quite different orders they take their neighbours in.

The macroblock layer, which is where all of the above meets. Each macroblock's modes come out of the first partition, its coefficients out of a token partition, and then it is predicted, has its residue added back, and is written into the frame for its neighbours to predict from.

And with that, the check the whole sequence was built towards: five real frames from cwebp — at three qualities, with four segments, and at sharpness seven — decode to exactly the samples dwebp -nofilter produces, luma and both chroma planes, byte for byte.

Two bugs stood between "almost" and "exactly", and both are the kind only a reference can find. The token partitions are dealt out by macroblock row, and a decoder made afresh for each macroblock re-reads the same coefficients forever — which decodes the first macroblock of a frame perfectly and nothing after it. And subblocks 3, 7, 11 and 15 take the pixels above and to their right from the macroblock's row above rather than their own, because the macroblock to the right has not been decoded yet; reading the subblock's own row is right for subblock 3 and wrong for the other three, which showed up as four wrong columns down the right-hand edge and nowhere else.

The loop filter, which softens the seams between blocks — but only where the difference across one looks like an artefact rather than like part of the picture, which is what all the thresholds are for. Macroblocks in raster order, each responsible for the edges above and to the left of it and the edges inside it, vertical ones before horizontal. The interior edges are skipped for a macroblock predicted whole with nothing coded in it: there are no subblock seams there to soften.

The two filters are not a fast path and a slow one. The simple filter touches two pixels either side of an edge and only in luma; the normal one reaches three deep and treats macroblock edges more strongly than subblock ones. They produce different pictures and the frame header says which.

It could not have run any earlier, and that is why it is last: prediction reads unfiltered neighbours, so filtering as the frame was reconstructed would have fed the wrong pixels into every macroblock after the first.

At quality 0 the filter changes 87% of the samples in the test frame, by up to 33 counts; at quality 100 the level is zero and it changes nothing. Both are matched exactly.

YUV to RGB, which RFC 6386 does not specify. It names BT.601 and stops there, because converting to RGB is a display decision rather than a decoding one — which is why two decoders can both be right and disagree by a count. So the reference for this one piece is libwebp rather than the specification: its sixteen-bit coefficients, its rounding, and its two ways of stretching the half-resolution chroma planes back to full size. .plain repeats each chroma sample over the four pixels it covers; .smooth interpolates, weighting the sample a pixel sits on nine against three, three and one for the neighbours on its side. Both match dwebp and dwebp -nofancy exactly.

The arithmetic is not quite balanced, and the test says so rather than asserting something prettier: the three offsets are rounded independently, so at three of the two hundred and fifty-six luma levels a neutral grey comes out with green one below red and blue. That is libwebp's picture, and matching it is the point.

The pieces, in the order a decoder needs them

VP8 is a video codec and a still WebP is one keyframe of it, so the work is the intra-only path and none of the inter-frame machinery.

1. The boolean decoder. Done. A binary arithmetic coder; everything below reads through it.
2. The first partition's header. Done.
3. The default probability tables. Done — extracted from the specification's own text rather than typed out, which is the only way to get a thousand and fifty-six numbers right.
4. Token decoding. Done — the coefficients themselves, through a twelve-value tree whose probabilities are selected by plane, band and context.
5. Intra prediction. Done — all fourteen modes, and the macroblock layer that chooses between them and walks the frame.
6. The inverse transforms. Done, along with dequantisation.
7. The loop filter. Done, both filters.
8. YUV to RGB. Done, both upsamplers.

RFC 6386 specifies all of it and ships the reference decoder as part of the document, which is unusual and makes it the thing to read rather than anything written about it.

What is deliberately absent is inter-frame decoding: motion vectors, reference frames, the golden and altref buffers. A still image is one key frame and never needs them, and adding them would be writing a video decoder rather than finishing this one.

Why this is its own library

VP8 is not an image format. It is a video codec that an image format happens to carry one frame of, and it is several thousand lines of arithmetic with nothing to say about containers, palettes or surfaces. A library that reads it should be usable by anything that meets one — so it lives here rather than inside an image codec, and z2dimg depends on it rather than containing it.

The container those frames arrive in lives separately too, in zig-riff.

Using it

zig fetch --save git+https://git.jcollie.dev/jeff/zig-vp8.git

and depend on the module named vp8.

Where this lives

git clone https://git.jcollie.dev/jeff/zig-vp8.git

• https://git.jcollie.dev/jeff/zig-vp8
• https://tangled.org/jcollie.dev/zig-vp8

It is on Radicle as rad:z4UTgDDJg3jV1Lmrup91KyQdndNpV, which is the only thing a peer needs to find it — a Radicle repository is discoverable by its identifier and by nothing else:

rad clone rad:z4UTgDDJg3jV1Lmrup91KyQdndNpV

Testing

nix develop -c zig build test --summary all
nix develop -c zig fmt --check .
nix develop -c reuse lint

The header tests use the first ten bytes of a real file — wuffs' hippopotamus.lossy.webp, which is 36×28 — rather than a constructed one, so the field packing is held against something libwebp actually wrote.

Everything past that is held against another decoder's output for the same file, which is the only exact claim available. A lossy decode cannot be checked against the lossless version of the same picture: those differ by up to 65 counts a channel at small sizes, and that is the encoder's loss and says nothing about a decoder. So tools/gen_fixtures.py encodes a test picture with cwebp under a spread of settings and records what dwebp makes of each — -nofilter -pgm for the reconstruction, -pgm for the filtered planes, -pam and -nofancy -pam for the two RGBA conversions — into src/fixtures.zig, and the tests demand equality.

nix develop -c python3 tools/gen_fixtures.py

Three of the settings are on cwebp's command line and therefore checkable on their own: the filter sharpness, the number of segments, and the quality that decides the quantiser index. A bit layout that had drifted by one bit would not read a sharpness of five back as five.

The bool coder and the token writer are checked by round trip instead, since there is nothing external to compare a half-decoded bitstream against. An encoder written from the same specification text is not independent evidence, but it disagrees loudly when one side has misread the text, and it found two real bugs.

References cited

• Bankoski, J., Koleszar, J., Quillio, L., Salonen, J., Wilkins, P., & Xu, Y. (2011, November). VP8 Data Format and Decoding Guide (RFC 6386). Independent Submission. https://www.rfc-editor.org/info/rfc6386
• Google. libwebp. https://chromium.googlesource.com/webm/libwebp
• Google. WebP Container Specification. Google Developers. https://developers.google.com/speed/webp/docs/riff_container

Licence

MIT, and REUSE compliant: every file carries its own copyright and licence, or is covered by REUSE.toml.