zedbar 0.2.5

//! BCH(15,5) error correction code
//!
//! This module implements BCH(15,5) error correction, which can correct up to 3 bit errors
//! and detect up to 5 bit errors in some cases. It's used for QR code format information.
//!
//! Rust port based on C code from the ZBar library.
//! Original C code copyright (C) 2008-2009 Timothy B. Terriberry (tterribe@xiph.org)
//! Licensed under LGPL 3.0 or later

/// A cycle in GF(2**4) generated by alpha=(x**4+x+1).
/// Extended an extra 16 entries to avoid expensive mod operations.
const GF16_EXP: [u8; 31] = [
    1, 2, 4, 8, 3, 6, 12, 11, 5, 10, 7, 14, 15, 13, 9, 1, 2, 4, 8, 3, 6, 12, 11, 5, 10, 7, 14, 15,
    13, 9, 1,
];

/// The location of each integer 1...16 in the cycle
const GF16_LOG: [i8; 16] = [-1, 0, 1, 4, 2, 8, 5, 10, 3, 14, 9, 7, 6, 13, 11, 12];

/// Multiplication in GF(2**4) using logarithms
fn gf16_mul(a: u32, b: u32) -> u32 {
    if a == 0 || b == 0 {
        0
    } else {
        GF16_EXP[(GF16_LOG[a as usize] + GF16_LOG[b as usize]) as usize] as u32
    }
}

/// Division in GF(2**4) using logarithms
/// The result when dividing by zero is undefined
fn gf16_div(a: u32, b: u32) -> u32 {
    if a == 0 {
        0
    } else {
        GF16_EXP[(GF16_LOG[a as usize] + 15 - GF16_LOG[b as usize]) as usize] as u32
    }
}

/// Multiplication in GF(2**4) when the second argument is known to be non-zero
/// (proven by representing it by its logarithm)
fn gf16_hmul(a: u32, logb: u32) -> u32 {
    if a == 0 {
        0
    } else {
        GF16_EXP[(GF16_LOG[a as usize] as u32 + logb) as usize] as u32
    }
}

/// Calculate syndrome values
///
/// The syndrome normally has five values, S_1 ... S_5.
/// We only calculate and store the odd ones, since S_2=S_1**2 and S_4=S_2**2.
///
/// # Returns
/// A tuple of (syndrome values, has_errors) where has_errors is true if any syndrome values are non-zero
fn bch15_5_calc_syndrome(y: u32) -> ([u32; 3], bool) {
    let mut s = [0u32; 3];

    let mut p = 0;
    for (i, &exp) in GF16_EXP.iter().enumerate() {
        if (y & (1 << i)) != 0 {
            p ^= exp as u32;
        }
    }
    s[0] = p;

    p = 0;
    for i in 0..3 {
        for j in 0..5 {
            if (y & (1 << (5 * i + j))) != 0 {
                p ^= GF16_EXP[j * 3] as u32;
            }
        }
    }
    s[1] = p;

    p = 0;
    for i in 0..5 {
        for j in 0..3 {
            if (y & (1 << (3 * i + j))) != 0 {
                p ^= GF16_EXP[j * 5] as u32;
            }
        }
    }
    s[2] = p;

    let has_errors = s[0] != 0 || s[1] != 0 || s[2] != 0;
    (s, has_errors)
}

/// Compute the coefficients of the error-locator polynomial
///
/// # Returns
/// A tuple of (error-locator polynomial coefficients, degree) where degree is the number of errors
fn bch15_5_calc_omega(s: &[u32; 3]) -> ([u32; 3], i32) {
    let mut o = [0u32; 3];
    o[0] = s[0];
    let s02 = gf16_mul(s[0], s[0]);
    let dd = s[1] ^ gf16_mul(s[0], s02);
    let tt = s[2] ^ gf16_mul(s02, s[1]);
    o[1] = if dd != 0 { gf16_div(tt, dd) } else { 0 };
    o[2] = dd ^ gf16_mul(s[0], o[1]);

    let mut d = 3;
    while d > 0 && o[d - 1] == 0 {
        d -= 1;
    }
    (o, d as i32)
}

/// Find the roots of the error polynomial
///
/// # Returns
/// `Ok((error_positions, error_count))` on success, or `Err(-1)` if the polynomial did
/// not have enough roots, indicating a decoding error
fn bch15_5_calc_epos(s: &[u32; 3]) -> Result<([u32; 3], i32), i32> {
    let (o, d) = bch15_5_calc_omega(s);
    let mut epos = [0u32; 3];
    let mut nerrors = 0i32;

    if d == 1 {
        epos[nerrors as usize] = GF16_LOG[o[0] as usize] as u32;
        nerrors += 1;
    } else if d > 0 {
        for i in 0..15 {
            let i2 = GF16_LOG[GF16_EXP[(i << 1) as usize] as usize] as u32;
            if (GF16_EXP[(i + i2) as usize] as u32
                ^ gf16_hmul(o[0], i2)
                ^ gf16_hmul(o[1], i)
                ^ o[2])
                == 0
            {
                epos[nerrors as usize] = i;
                nerrors += 1;
            }
        }
        if nerrors < d {
            return Err(-1);
        }
    }

    Ok((epos, nerrors))
}

/// Corrects the received code, if possible
///
/// The original data is located in the top five bits.
/// Returns the number of errors corrected, or a negative value if decoding
/// failed due to too many bit errors, in which case y is left unchanged.
pub(crate) fn bch15_5_correct(y: &mut u32) -> i32 {
    let mut y_val = *y;

    let (s, has_errors) = bch15_5_calc_syndrome(y_val);
    if !has_errors {
        return 0;
    }

    match bch15_5_calc_epos(&s) {
        Ok((epos, nerrors)) if nerrors > 0 => {
            // If we had a non-zero syndrome value, we should always find at least one
            // error location, or we've got a decoding error
            for i in 0..nerrors {
                y_val ^= 1 << epos[i as usize];
            }

            // If there were too many errors, we may not find enough roots to reduce the
            // syndrome to zero. We could recompute it to check, but it's much faster
            // just to check that we have a valid codeword
            if bch15_5_encode(y_val >> 10) == y_val {
                // Decoding succeeded
                *y = y_val;
                return nerrors;
            }
            // Decoding failed due to too many bit errors
            -1
        }
        _ => {
            // Decoding failed due to too many bit errors
            -1
        }
    }
}

/// Encodes a raw 5-bit value into a 15-bit BCH(15,5) code
///
/// This is capable of correcting up to 3 bit errors, and detecting as many as
/// 5 bit errors in some cases.
pub fn bch15_5_encode(x: u32) -> u32 {
    (u32::wrapping_neg(x & 1) & 0x0537)
        ^ (u32::wrapping_neg((x >> 1) & 1) & 0x0A6E)
        ^ (u32::wrapping_neg((x >> 2) & 1) & 0x11EB)
        ^ (u32::wrapping_neg((x >> 3) & 1) & 0x23D6)
        ^ (u32::wrapping_neg((x >> 4) & 1) & 0x429B)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_bch15_5_encode() {
        // Test encoding some valid 5-bit values
        assert_eq!(bch15_5_encode(0), 0x0000);
        assert_eq!(bch15_5_encode(1), 0x0537);
        assert_eq!(bch15_5_encode(2), 0x0A6E);
        // Encoding 31 (all 5 bits set) produces a specific codeword
        let encoded_31 = bch15_5_encode(31);
        assert_eq!(encoded_31, 0x0537 ^ 0x0A6E ^ 0x11EB ^ 0x23D6 ^ 0x429B);
    }

    #[test]
    fn test_bch15_5_correct_no_errors() {
        let mut y = bch15_5_encode(15);
        let nerrors = bch15_5_correct(&mut y);
        assert_eq!(nerrors, 0);
        assert_eq!(y, bch15_5_encode(15));
    }

    #[test]
    fn test_bch15_5_correct_single_error() {
        let original = bch15_5_encode(10);
        // Introduce a single bit error
        let mut corrupted = original ^ (1 << 3);
        let nerrors = bch15_5_correct(&mut corrupted);
        assert_eq!(nerrors, 1);
        assert_eq!(corrupted, original);
    }

    #[test]
    fn test_bch15_5_correct_two_errors() {
        let original = bch15_5_encode(5);
        // Introduce two bit errors
        let mut corrupted = original ^ (1 << 1) ^ (1 << 7);
        let nerrors = bch15_5_correct(&mut corrupted);
        assert_eq!(nerrors, 2);
        assert_eq!(corrupted, original);
    }

    #[test]
    fn test_bch15_5_correct_three_errors() {
        let original = bch15_5_encode(20);
        // Introduce three bit errors
        let mut corrupted = original ^ (1 << 0) ^ (1 << 5) ^ (1 << 10);
        let nerrors = bch15_5_correct(&mut corrupted);
        assert_eq!(nerrors, 3);
        assert_eq!(corrupted, original);
    }

    #[test]
    fn test_bch15_5_correct_too_many_errors() {
        let original = bch15_5_encode(7);
        // Introduce four bit errors (too many to correct)
        let mut corrupted = original ^ (1 << 0) ^ (1 << 3) ^ (1 << 6) ^ (1 << 9);
        let nerrors = bch15_5_correct(&mut corrupted);
        // Should fail to correct
        assert!(nerrors < 0);
    }

    #[test]
    fn test_gf16_mul() {
        assert_eq!(gf16_mul(0, 5), 0);
        assert_eq!(gf16_mul(5, 0), 0);
        assert_eq!(gf16_mul(2, 3), gf16_mul(3, 2)); // Commutative
    }
}