Floyd-Steinberg Dither

Rendering & Graphics

How do you show a smooth gradient with only four shades of grey? You cheat, carefully: Floyd-Steinberg error diffusion snaps each pixel to the nearest shade and then pushes the rounding error onto its neighbours, so the mistakes average out into texture instead of banding. Here a drifting gradient dissolves into that shimmering dither on a Super Nintendo — all integer, so it's bit-exact. Runs on its own; no joypad needed. Written in C and compiled with the llvm-mos-based 65816 toolchain (+mos-a16, 16-bit accumulator mode).

loading core…

Self-running demo — the gradient resolves into dither.

Click the screen to focus, then watch. Tab away and it pauses.

What it is

Scan the image left-to-right, top-to-bottom. Each pixel is snapped to the nearest of four greys, and the signed error of that snap is spread forward onto the pixels not yet drawn:

for each pixel, left-to-right, top-to-bottom:
  v   = scene + carried_error        // the accumulated signed error
  q   = nearest of 4 grey levels
  e   = v - q                        // SIGNED residual
  spread e:  7/16 right   3/16 down-left
             5/16 down    1/16 down-right

Because the error is carried, a run of pixels that all want to be "slightly grey" ends up as a sprinkling of black and white in the right proportion — the eye blends it back into the original tone. It's all add, shift and compare, identical across every codegen mode.

Compiler stress-test

Item	What it exercises
signed residual	When a pixel is snapped to the nearest of four greys, the leftover — how far off the snap was — is a signed number, positive or negative. Floyd-Steinberg does not throw it away.
forward diffusion	That error is pushed onto the neighbours not yet drawn: 7/16 to the right, then 3/16, 5/16, 1/16 across the next row. Each pixel is quantised only after it has collected the debts of the pixels above and to its left.
no division	The classic algorithm divides the error by 16. Here that is an arithmetic shift of a signed value — so the whole inner loop is add, shift and compare, with no divide at all. The four levels come from a tiny lookup table.
integer, bit-exact	The value and the carried error are 16-bit signed integers, so the dithered field is identical on the host and the 65816. The build gate re-runs the diffusion and asserts the fold matches to the bit.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg (and MAME where the SPC700 IPL is present). Hit Verify fidelity to reproduce the build gate's WRAM assert (gate CRC 0x80C4 — a fold of the dithered band indices over three animated frames) live in this tab. No far pointers — the same source passes every way: host == default == +mos-a16 == +mos-xy16 == bsnes-jg, -verify clean.