Zero-allocation dithering in Go
How bolture renders 1080p dithered video at 30fps without allocating.
bolture plays video in a terminal using the Kitty graphics protocol. At 30fps each frame gets about 33ms, and that budget has to cover decoding, resizing, dithering, protocol encoding and the write to the terminal. The renderer’s share is a few milliseconds, which only works if it never allocates.
The dithering maths is straightforward. Keeping Go from allocating inside the frame loop took most of the work.
From ffmpeg to the terminal
ffmpeg ─rgba─> resize ─> luma ─> dither ─> dots ─> kitty
(pipe) (float64) (bool)
ffmpeg decodes to raw RGBA on a pipe. No frames on disk, no intermediate images. Each frame is resized to the canvas, reduced to one luminance value per pixel, dithered to a bool per pixel, and sent.
Luminance
Both algorithms need a single number per pixel. BT.709 weights, applied once:
l := 0.2126*r + 0.7152*g + 0.0722*b
lum[i] = l
Anything below 0.05 makes no dot at all. Without that floor, dark areas fill up with noise instead of staying black.
Atkinson diffusion
Atkinson pushes 6/8 of each pixel’s error to six neighbours: two to the right, three on the row below, one two rows down. The missing 2/8 is why the result looks harsh and slightly overexposed instead of smooth.
err := (val - newVal) / 8.0
if x+1 < w { buf[idx+1] += err }
if x+2 < w { buf[idx+2] += err }
if y+1 < h {
if x-1 >= 0 { buf[idx+w-1] += err }
buf[idx+w] += err
if x+1 < w { buf[idx+w+1] += err }
}
if y+2 < h { buf[idx+2*w] += err }
Odd rows are scanned right to left.
if y%2 == 0 {
for x := 0; x < w; x++ { /* left to right */ }
} else {
// Serpentine scan right-to-left to reduce directional bias
for x := w - 1; x >= 0; x-- { /* right to left */ }
}
Diffusing in one direction leaves diagonal streaks in flat areas. Scanning every other row in reverse breaks most of them up.
Reducing flicker
Dithered video flickers on its own. A dot flips state because luminance moved by half a percent.
Blending the current frame into the previous one would stop it, but that needs another float buffer and it smears movement. Moving the threshold instead is cheaper:
stickiness := stability * 0.25
hasPrev := len(prevDots) == total && stability > 0
// ...
threshold := 0.5
if hasPrev {
if prevDots[idx] {
threshold -= stickiness // was on: easier to stay on
} else {
threshold += stickiness // was off: harder to turn on
}
}
A dot lit in the previous frame gets a lower threshold, so a small fall in luminance will not turn it off. The diffused value is unchanged, so error diffusion behaves as before.
Bayer uses the same mechanism at a quarter of the strength, since ordered dithering is already stable across frames.
Preallocated buffers
None of the above allocates, as long as the buffers already exist. NewRenderer allocates them once, sized to the canvas:
type Renderer struct {
step int
lumBuf []float64
ditherBuf []float64
dotsBuf []bool
prevLum []float64
prevDots []bool
// ...plus grid-sized copies for --dot-size > 1
}
What keeps the loop at zero allocations:
- The diffuser writes inside the preallocated slice via
workBuf[:total]. Themakebranch exists only for a caller that passes something too small. prevDotsis swapped by reference. It is read for the threshold and then replaced, never copied.--dot-sizedithers a smaller grid and scales the dots up, so bigger dots mean fewer pixel operations.
Row edges are bounds-checked, so the buffer is exactly w*h with no halo rows.
Benchmarks
go test -bench . -benchmem, i5-1135G7:
| canvas | time/frame | memory | allocs |
|---|---|---|---|
| 360p | 6.5 ms | 0 B | 0 |
| 720p | 13.1 ms | 0 B | 0 |
| 1080p | 34.5 ms | 0 B | 0 |
The allocator stays clean, but 34.5ms at 1080p is already past the 33.3ms a 30fps frame allows. Anything else running drops frames, which is why the default canvas is 1280x720.
ScaleNearest1080p at 5.6ms is the second largest cost. Downscaling uses area averaging because skipping pixels looks bad. Upscaling uses nearest neighbour. It is cheap, and it leaves hard blocky edges on a large terminal.
Source: internal/render/dither.go and internal/render/dots.go.