ballot-interpreter · bubble scoring · commit 23b6abe9
To read a voter's mark, the interpreter first has to find the printed bubble — by trying 196 candidate positions and scoring every one. Packing each row of that comparison into a single 64-bit word turns a thousand byte reads per candidate into a handful of shifts and popcounts, making bubble scoring six times faster with bit-identical results.
Paper stretches, feeds skew, printers drift — so a bubble is never exactly where the ballot layout says it should be. Before judging whether a bubble is filled, the interpreter slides the bubble's printed template over the scan, trying every offset within ±7 pixels (14 × 14 = 196 placements), and keeps the one that matches best.
The match score counts pixels satisfying source_is_dark || template_is_white. Since a
template pixel is either white background (always matches) or outline ink, the only way a pixel can
miss is if the template has outline there and the scan doesn't have ink. Maximizing the score
means locking onto the printed oval:
The scan, with the template at the current offset
Match score at each of the 196 offsets
The toy bubble here is a 36×20 template searched at production's real ±7-pixel distance. The scanned oval is printed 2 px right and 3 px up of where the layout expects it, with ink dropouts and a partial voter mark — the search finds it anyway.
The old search evaluated that predicate pixel by pixel: for each of 196 placements, walk all 720 template positions, load a byte of scan and a byte of template, compare, branch, count. But the predicate only has two inputs — is the scan dark here and is the template white here — each a single bit. A CPU register holds 64 of those bits and the ALU operates on all of them at once.
So pack once, up front: every row of the search window becomes one u64 of dark-pixel
bits, and every row of the template becomes one u64 of white-pixel bits — 53 words in
total, built in one pass over the pixels:
fn pack_row(row: &[u8], is_set: impl Fn(u8) -> bool) -> u64 {
row.iter()
.enumerate()
.fold(0u64, |bits, (c, &p)| bits | (u64::from(is_set(p)) << c))
}
// window rows: is_set = |p| p <= threshold (bit = pixel is dark)
// template rows: is_set = |p| p == 255 (bit = pixel is white)Scoring a placement is now a per-row dance of exactly the original predicate:
shift the window row right by dx to align it with the template,
OR in the template's white bits, mask to the template width, and
popcount the ones. Every set bit is a matching pixel; every hole is outline that found
no ink. Drag the offset and watch the bits align:
Which row we're scoring
The three registers (bit 0 drawn leftmost, matching image columns)
The real loop is four operations per row — ((window >> dx) | template)
& mask, then count_ones() — summed over 20 rows per placement. On today's baseline
x86-64 build, count_ones() compiles to a ~17-instruction bit dance that still counts all 64
bits at once; a later commit in this series raises the build target to x86-64-v3, where it becomes a
single popcnt.
fn match_count(&self, dx: usize, dy: usize) -> u32 {
self.window_rows[dy..dy + self.template_rows.len()]
.iter()
.zip(&self.template_rows)
.map(|(&window, &template)| {
(((window >> dx) | template) & self.template_width_mask).count_ones()
})
.sum()
}Per bubble, the byte search did 196 placements × 720 loads-compares-branches ≈ 141,000 byte operations. The packed search pays a one-time 53-row packing pass, then 196 × 20 word operations ≈ 3,900 — about 36× less work, which cashes out as a measured 6× (the packing pass, the fill score, and loop overhead keep it honest). Both bars below advance at their measured rates:
A typical ballot page has a few dozen bubbles per side; end-to-end interpretation gains roughly 1 ms per sheet.
The popcount counts exactly the predicate the byte loop counted — dark || white,
one bit per pixel, no approximation anywhere. The packed search also iterates placements in the same
x-major order with the same strictly-greater update, so ties break identically; the fill score is still
computed by the original byte-wise code, once, at the winning placement; and bubbles whose search window
is clipped by the image edge (or too wide for a u64) skip the packed path entirely and use
the byte loop as before.
The commit pins all of that down twice: a property test asserts the packed and byte searches agree on arbitrary generated inputs, and every interior timing-mark grid cell of the TRR corpus — 3,040,128 positions across 2,436 field-scanned pages — was re-scored with zero differences in bounds, match score, or fill score. This page's two figures run both algorithms live and verify they agree on every one of the 196 offsets before drawing.
Seven questions — half on the ideas, half on the code the PR actually changes. Pick an answer to see the explanation; your first try is what's scored.