smart-package-tracker 0.4.0

//! Reading a linear symbol off a single scan line.
//!
//! The hard part is not finding the bars, it is deciding how many *modules*
//! wide each one is. A naive scanner estimates one module width for the whole
//! symbol and divides; that fails as soon as the printed width drifts even
//! slightly from nominal, because the error accumulates across the symbol.
//!
//! Instead the runs are cut into characters using
//! [`LinearCharacter`] metadata and each character is renormalised against its
//! own pixel width. A character is a fixed number of modules by definition, so
//! its measured width is a local ruler, and drift never accumulates past one
//! character. Nothing here knows which symbology it is reading.

use alloc::string::String;
use alloc::vec::Vec;

use crate::symbology::{BitMatrix, Decoder, LinearCharacter};

/// How many candidate starting bars to try per scan line.
///
/// A line that crosses a table rule or a speck of dirt before reaching the
/// barcode has junk runs in front of it. Trying a few later starts recovers
/// that case; trying every start would be a licence to fabricate a decode.
const MAX_START_CANDIDATES: usize = 3;

/// How many trailing characters to allow dropping, for junk *after* the
/// symbol.
const MAX_TRUNCATIONS: usize = 2;

/// A maximal run of identical modules along a scan line.
#[derive(Clone, Copy, Debug)]
struct Run {
    dark: bool,
    len: u32,
}

/// Try to read one payload out of `row`.
///
/// Returns `None` if the line does not carry a symbol this decoder accepts.
/// The decoder validates its own check character, so a wrong cut through the
/// runs fails rather than returning a plausible-looking payload.
pub(crate) fn decode_row<D: Decoder + ?Sized>(
    decoder: &D,
    character: LinearCharacter,
    row: &[bool],
) -> Option<String> {
    let elements = character.elements as usize;
    let stop = character.stop_elements as usize;
    if elements == 0 || stop == 0 {
        return None;
    }

    let runs = runs(row);
    // Trim the quiet zones. What is left starts and ends with a bar, so every
    // dark run sits at an even index.
    let runs = trim(&runs);
    if runs.len() < elements * 2 + stop {
        return None;
    }

    for start in (0..MAX_START_CANDIDATES).map(|i| i * 2) {
        let Some(available) = runs.len().checked_sub(start) else {
            break;
        };
        // Longest window of the form `elements * k + stop` that fits, then
        // progressively shorter ones in case the line runs on into junk.
        let Some(max_characters) = available.checked_sub(stop).map(|rest| rest / elements) else {
            continue;
        };
        for dropped in 0..=MAX_TRUNCATIONS {
            // A symbol is at minimum a start character, a check character and
            // the stop pattern.
            let Some(characters) = max_characters.checked_sub(dropped).filter(|k| *k >= 2) else {
                break;
            };
            let window = &runs[start..start + characters * elements + stop];
            let Some(modules) = quantize(window, character) else {
                continue;
            };
            if let Ok(payload) = decoder.decode(&BitMatrix::from_row(modules)) {
                return Some(payload);
            }
        }
    }

    None
}

/// Run-length encode a scan line.
fn runs(row: &[bool]) -> Vec<Run> {
    let mut runs: Vec<Run> = Vec::new();
    for &dark in row {
        match runs.last_mut() {
            Some(last) if last.dark == dark => last.len += 1,
            _ => runs.push(Run { dark, len: 1 }),
        }
    }
    runs
}

/// Drop the leading and trailing light runs, so the slice begins and ends with
/// a bar.
fn trim(runs: &[Run]) -> &[Run] {
    let start = runs.iter().position(|r| r.dark);
    let end = runs.iter().rposition(|r| r.dark);
    match (start, end) {
        (Some(s), Some(e)) => &runs[s..=e],
        _ => &[],
    }
}

/// Convert pixel runs into a module pattern, one character at a time.
fn quantize(window: &[Run], character: LinearCharacter) -> Option<Vec<bool>> {
    let elements = character.elements as usize;
    let stop = character.stop_elements as usize;
    let characters = window.len().checked_sub(stop)? / elements;

    let mut modules = Vec::new();
    for c in 0..characters {
        let group = &window[c * elements..(c + 1) * elements];
        push_group(&mut modules, group, character.modules)?;
    }
    push_group(
        &mut modules,
        &window[characters * elements..],
        character.stop_modules,
    )?;

    if modules.is_empty() {
        return None;
    }
    Some(modules)
}

/// Apportion one character's fixed module count across its measured elements.
///
/// Each element takes its proportional share, rounded down, and the modules
/// left over go to whichever elements were rounded down hardest — the largest
/// remainder method, which guarantees the character comes out at exactly its
/// nominal width no matter how the pixels fell. Every element is then forced
/// to at least one module, so a thin bar measured at a fraction of a pixel
/// narrows rather than vanishing.
fn push_group(out: &mut Vec<bool>, group: &[Run], modules: u32) -> Option<()> {
    let count = group.len();
    if count == 0 || (modules as usize) < count {
        return None;
    }

    let total: u64 = group.iter().map(|r| u64::from(r.len)).sum();
    if total == 0 {
        return None;
    }

    let mut widths: Vec<u32> = Vec::with_capacity(count);
    let mut remainders: Vec<(u64, usize)> = Vec::with_capacity(count);
    for (i, run) in group.iter().enumerate() {
        let scaled = u64::from(run.len) * u64::from(modules);
        widths.push((scaled / total) as u32);
        remainders.push((scaled % total, i));
    }

    let assigned: u32 = widths.iter().sum();
    // `assigned` is a sum of floors, so it can only be short of the target.
    let mut leftover = modules.checked_sub(assigned)?;
    // Ties break on the lower index, keeping the result deterministic.
    remainders.sort_by(|a, b| b.0.cmp(&a.0).then(a.1.cmp(&b.1)));
    for &(_, i) in remainders.iter() {
        if leftover == 0 {
            break;
        }
        widths[i] += 1;
        leftover -= 1;
    }

    // Rounding can starve an element that measured very narrow. Since
    // `modules >= count`, there is always a wider element to borrow from.
    while let Some(starved) = widths.iter().position(|w| *w == 0) {
        let (widest, _) = widths
            .iter()
            .enumerate()
            .max_by_key(|(i, w)| (**w, core::cmp::Reverse(*i)))?;
        if widths[widest] <= 1 {
            return None;
        }
        widths[widest] -= 1;
        widths[starved] += 1;
    }

    for (run, width) in group.iter().zip(widths) {
        out.extend(core::iter::repeat_n(run.dark, width as usize));
    }
    Some(())
}

#[cfg(all(test, feature = "code128"))]
mod tests {
    use super::*;
    use crate::symbology::{Code128, Symbology, SymbologyKind};
    use alloc::vec;

    fn character() -> LinearCharacter {
        SymbologyKind::Code128.linear_character().unwrap()
    }

    /// Blow a module pattern up to `scale` pixels per module, with `margin`
    /// light pixels of quiet zone on each side.
    fn stretch(modules: &[bool], scale: usize, margin: usize) -> Vec<bool> {
        let mut row = vec![false; margin];
        for &m in modules {
            row.extend(core::iter::repeat_n(m, scale));
        }
        row.extend(core::iter::repeat_n(false, margin));
        row
    }

    #[test]
    fn reads_a_symbol_at_several_scales() {
        let symbol = Code128.encode("PKG-9ED9285C").unwrap();
        let modules = symbol.modules().row(0).to_vec();
        for scale in [1, 2, 3, 4, 7, 11] {
            let row = stretch(&modules, scale, 10 * scale);
            let got = decode_row(&Code128, character(), &row);
            assert_eq!(got.as_deref(), Some("PKG-9ED9285C"), "at scale {scale}");
        }
    }

    #[test]
    fn reads_a_symbol_with_no_quiet_zone_at_all() {
        // Cropped flush to the bars. The quiet zone matters to a scanner
        // hunting for the symbol in a wider scene; here the caller has
        // already found it.
        let symbol = Code128.encode("PKG-9ED9285C").unwrap();
        let row = stretch(symbol.modules().row(0), 3, 0);
        assert_eq!(
            decode_row(&Code128, character(), &row).as_deref(),
            Some("PKG-9ED9285C")
        );
    }

    #[test]
    fn survives_module_widths_that_do_not_divide_evenly() {
        // 3.5 pixels per module: every other module is a pixel wider. A
        // scanner that estimated one global module width would drift off the
        // pattern part way along.
        let symbol = Code128.encode("PKG-9ED9285C").unwrap();
        let modules = symbol.modules().row(0);
        let mut row = vec![false; 35];
        for (i, &m) in modules.iter().enumerate() {
            row.extend(core::iter::repeat_n(m, if i % 2 == 0 { 4 } else { 3 }));
        }
        row.extend(core::iter::repeat_n(false, 35));
        assert_eq!(
            decode_row(&Code128, character(), &row).as_deref(),
            Some("PKG-9ED9285C")
        );
    }

    #[test]
    fn skips_junk_before_and_after_the_symbol() {
        // A rule line to the left and a smudge to the right, as a scan line
        // across a label would find.
        let symbol = Code128.encode("PKG-9ED9285C").unwrap();
        let mut row = vec![true; 6];
        row.extend(core::iter::repeat_n(false, 20));
        row.extend(stretch(symbol.modules().row(0), 3, 30));
        row.extend(core::iter::repeat_n(true, 5));
        assert_eq!(
            decode_row(&Code128, character(), &row).as_deref(),
            Some("PKG-9ED9285C")
        );
    }

    #[test]
    fn refuses_a_line_that_carries_no_symbol() {
        assert!(decode_row(&Code128, character(), &[false; 200]).is_none());
        assert!(decode_row(&Code128, character(), &[true; 200]).is_none());
        // Alternating single pixels: plenty of runs, no valid character.
        let noise: Vec<bool> = (0..400).map(|i| i % 2 == 0).collect();
        assert!(decode_row(&Code128, character(), &noise).is_none());
    }

    #[test]
    fn refuses_an_empty_line() {
        assert!(decode_row(&Code128, character(), &[]).is_none());
    }

    #[test]
    fn a_character_always_comes_out_at_its_nominal_width() {
        // Whatever the measurements, apportionment must total exactly the
        // module count — that is the property the whole approach rests on.
        for widths in [
            [1u32, 1, 1, 1, 1, 1],
            [40, 1, 9, 3, 21, 2],
            [1, 1, 1, 1, 1, 100],
            [7, 7, 7, 7, 7, 7],
        ] {
            let group: Vec<Run> = widths
                .iter()
                .enumerate()
                .map(|(i, &len)| Run {
                    dark: i % 2 == 0,
                    len,
                })
                .collect();
            let mut out = Vec::new();
            push_group(&mut out, &group, 11).unwrap();
            assert_eq!(out.len(), 11, "widths {widths:?} did not total 11 modules");
            assert_eq!(runs(&out).len(), 6, "an element was lost for {widths:?}");
        }
    }
}