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:

  1. The diffuser writes inside the preallocated slice via workBuf[:total]. The make branch exists only for a caller that passes something too small.
  2. prevDots is swapped by reference. It is read for the threshold and then replaced, never copied.
  3. --dot-size dithers 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.

gographicsperformance

← all posts