lernie 0.1.16

//! **The field the check bytes are computed in**: GF(2⁸), and the Reed-Solomon
//! remainder that is the whole of a QR symbol's error correction.
//!
//! # No tables, and that is the smaller answer
//!
//! Every implementation of this field reaches for a pair of 256-entry
//! logarithm and antilogarithm tables, because a table turns a multiply into
//! two lookups and an add. That trade is worth making when the multiply is on
//! a hot path. Here the whole encode is on the order of sixty thousand
//! multiplies for the largest symbol this seat can produce — microseconds —
//! and the tables would cost two arrays that have to be generated, held, and
//! indexed, in a crate where unchecked indexing is denied.
//!
//! So [`mul`] is the carry-less multiply itself, reduced by the standard's own
//! primitive polynomial. It is eight iterations of shift-and-conditional-xor,
//! it needs no initialization and no storage, and it is the definition rather
//! than a precomputation of one.
//!
//! # The polynomial, and why 0x1d and not 0x11d
//!
//! The field is generated by x⁸ + x⁴ + x³ + x² + 1 — `0x11d` as a nine-bit
//! number. The reduction below xors `0x1d`, which is the same polynomial with
//! its x⁸ term dropped: the term is exactly the bit that just shifted out of a
//! `u8`, so testing for it before the shift and xoring the remaining eight bits
//! after is the same arithmetic without ever needing a ninth bit to put it in.

/// The primitive polynomial's low eight bits — x⁸ + x⁴ + x³ + x² + 1, with the
/// x⁸ term left to the shift that produces it.
const REDUCTION: u8 = 0x1d;

/// **Multiply in GF(2⁸).** Carry-less multiplication, reduced at every step.
///
/// `p` accumulates the partial products (xor is addition in a field of
/// characteristic two), `a` doubles each round and is reduced whenever the
/// doubling would leave the byte, and `b` is consumed a bit at a time.
pub(super) fn mul(a: u8, b: u8) -> u8 {
    let (mut a, mut b, mut p) = (a, b, 0_u8);
    while b != 0 {
        if b & 1 != 0 {
            p ^= a;
        }
        let overflowed = a & 0x80 != 0;
        a <<= 1;
        if overflowed {
            a ^= REDUCTION;
        }
        b >>= 1;
    }
    p
}

/// **The generator polynomial for `count` check bytes**: the product of
/// (x − α⁰)(x − α¹)…(x − α^count-1), coefficients highest power first.
///
/// Subtraction is xor here, so the roots need no negation. Each round
/// multiplies the accumulated polynomial by one more linear factor, which is
/// the polynomial shifted up one degree xored with the polynomial scaled by
/// that factor's root — written as two iterators over the same coefficients,
/// offset by one, rather than as a walk over indices.
fn generator(count: usize) -> Vec<u8> {
    let mut poly = vec![1_u8];
    let mut root = 1_u8;
    for _ in 0..count {
        let shifted = poly.iter().copied().chain(std::iter::once(0));
        let scaled = std::iter::once(0).chain(poly.iter().map(|&c| mul(c, root)));
        poly = shifted.zip(scaled).map(|(high, low)| high ^ low).collect();
        root = mul(root, 2);
    }
    poly
}

/// **The check bytes for one block**: `data` divided by the generator
/// polynomial for `count` roots, remainder only.
///
/// Synthetic division, one data byte per round. The remainder register holds
/// exactly `count` bytes; each round takes the byte leaving the top, xors the
/// next data byte into it to get the quotient term, shifts the register up, and
/// subtracts the generator scaled by that term. The generator's leading
/// coefficient is 1 and is what the shift accounts for, so the scaling walks
/// the coefficients *after* it — which is the `skip(1)`.
pub(super) fn check(data: &[u8], count: usize) -> Vec<u8> {
    let divisor = generator(count);
    let mut rem = vec![0_u8; count];
    for &byte in data {
        let Some(&leaving) = rem.first() else {
            break;
        };
        let term = byte ^ leaving;
        rem.remove(0);
        rem.push(0);
        for (slot, &coefficient) in rem.iter_mut().zip(divisor.iter().skip(1)) {
            *slot ^= mul(coefficient, term);
        }
    }
    rem
}