smart-package-tracker 0.4.0

//! Check-character computation (ISO/IEC 7064, MOD 37,36).
//!
//! The check character is drawn from the same 36-character alphabet as the ID
//! body (`0-9`, `A-Z`), so appending it does not widen the barcode's character
//! set. MOD 37,36 detects all single-character substitutions and all
//! transpositions of adjacent characters, which are the two dominant failure
//! modes for hand-keyed and misread tracking numbers.

/// The 36-character alphabet used for both ID bodies and check characters.
pub(crate) const ALPHABET: &[u8; 36] = b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

const MODULUS: u32 = 36;
const RADIX: u32 = 37;

/// Numeric value of an alphabet character, or `None` if it is not in the
/// alphabet.
pub(crate) fn char_value(c: char) -> Option<u32> {
    match c {
        '0'..='9' => Some(c as u32 - '0' as u32),
        'A'..='Z' => Some(c as u32 - 'A' as u32 + 10),
        _ => None,
    }
}

/// Character for a numeric value in `0..36`.
pub(crate) fn value_char(v: u32) -> Option<char> {
    ALPHABET.get(v as usize).map(|b| *b as char)
}

/// Run the ISO 7064 hybrid recursion over `text`.
///
/// Returns `None` if `text` contains a character outside the alphabet. A
/// string that already carries a valid check character accumulates to `1`.
fn accumulate(text: &str) -> Option<u32> {
    let mut p = MODULUS;
    for c in text.chars() {
        let a = char_value(c)?;
        let mut s = (p + a) % MODULUS;
        if s == 0 {
            s = MODULUS;
        }
        p = (2 * s) % RADIX;
    }
    Some(p)
}

/// Compute the check character for `data`.
///
/// Returns `None` if `data` contains characters outside `0-9A-Z`.
///
/// The value is found by searching the 36-character alphabet for the character
/// that makes [`verify`] succeed. This is deliberately defined in terms of the
/// verifier rather than a closed-form expression: the two can never disagree.
pub(crate) fn compute(data: &str) -> Option<char> {
    let p = accumulate(data)?;
    for v in 0..MODULUS {
        let mut s = (p + v) % MODULUS;
        if s == 0 {
            s = MODULUS;
        }
        if (2 * s) % RADIX == 1 {
            return value_char(v);
        }
    }
    // Unreachable: 2 is invertible modulo the prime 37, so exactly one
    // residue always satisfies the equation.
    None
}

/// Check whether `text` ends with a valid check character for its prefix.
pub(crate) fn verify(text: &str) -> bool {
    accumulate(text) == Some(1)
}

#[cfg(test)]
mod tests {
    use super::*;
    use alloc::format;
    use alloc::string::String;

    #[test]
    fn computed_check_character_verifies() {
        for data in ["A", "0", "Z", "9ED9285C", "PKG9ED9285C", "000000000000"] {
            let c = compute(data).expect("alphabet is valid");
            assert!(verify(&format!("{data}{c}")), "failed for {data}");
        }
    }

    #[test]
    fn rejects_characters_outside_the_alphabet() {
        assert!(compute("abc").is_none());
        assert!(compute("PKG-1234").is_none());
        assert!(!verify("PKG-1234"));
    }

    #[test]
    fn detects_every_single_character_substitution() {
        let data = "9ED9285C";
        let check = compute(data).unwrap();
        let good: String = format!("{data}{check}");

        for pos in 0..good.len() {
            let original = good.as_bytes()[pos];
            for &sub in ALPHABET.iter() {
                if sub == original {
                    continue;
                }
                let mut bytes = good.as_bytes().to_vec();
                bytes[pos] = sub;
                let corrupted = String::from_utf8(bytes).expect("alphabet is ascii");
                assert!(!verify(&corrupted), "missed substitution in {corrupted}");
            }
        }
    }

    #[test]
    fn detects_every_adjacent_transposition() {
        let data = "9ED9285C";
        let check = compute(data).unwrap();
        let good = format!("{data}{check}");
        let bytes = good.as_bytes();

        for i in 0..bytes.len() - 1 {
            if bytes[i] == bytes[i + 1] {
                continue; // Swapping equal characters is not an error.
            }
            let mut swapped = bytes.to_vec();
            swapped.swap(i, i + 1);
            let swapped = String::from_utf8(swapped).unwrap();
            assert!(!verify(&swapped), "missed transposition in {swapped}");
        }
    }
}