//! Precomputed log and exp tables for GF(2^8).
//!
//! The irreducible polynomial is x^8 + x^4 + x^3 + x + 1 (0x11B)
//! and the primitive element is 3.  All 255 nonzero field elements
//! are powers of 3 under this polynomial.
//!
//! The tables are computed at compile time via `const fn`.

/// Primitive element of GF(2^8) under the irreducible polynomial 0x11B.
const PRIMITIVE: u16 = 3;

/// Low 8 bits of the irreducible polynomial x^8 + x^4 + x^3 + x + 1.
const MODULUS: u16 = 0x1B;

/// Multiply two bytes in GF(2^8) using schoolbook polynomial multiplication.
///
/// Used only at compile time to build the tables.
#[allow(clippy::cast_possible_truncation)]
const fn gf_mul_raw(a: u8, b: u8) -> u8 {
    let mut result: u16 = 0;
    let mut a_shifted = a as u16;
    let mut b_remaining = b as u16;
    let mut i = 0;
    while i < 8 {
        if b_remaining & 1 != 0 {
            result ^= a_shifted;
        }
        a_shifted <<= 1;
        if a_shifted & 0x100 != 0 {
            a_shifted ^= 0x100 | MODULUS;
        }
        b_remaining >>= 1;
        i += 1;
    }
    result as u8
}

/// Build the exponentiation table: `EXP_TABLE[i] = primitive^i mod p(x)`.
///
/// The table has 512 entries so that `a * b` can be computed as
/// `EXP_TABLE[LOG_TABLE[a] + LOG_TABLE[b]]` without modular reduction.
#[allow(clippy::cast_possible_truncation)]
const fn build_exp_table() -> [u8; 512] {
    let mut table = [0u8; 512];
    let mut acc: u8 = 1;
    let mut i = 0;
    while i < 255 {
        table[i] = acc;
        table[i + 255] = acc;
        acc = gf_mul_raw(acc, PRIMITIVE as u8);
        i += 1;
    }
    // EXP_TABLE[255] = EXP_TABLE[0] = 1 (since primitive^255 = 1)
    table[510] = table[0];
    table[511] = table[1];
    table
}

/// Build the logarithm table: `LOG_TABLE[primitive^i] = i`.
///
/// `LOG_TABLE[0]` is unused (log of zero is undefined) and set to 0.
#[allow(clippy::cast_possible_truncation)]
const fn build_log_table() -> [u8; 256] {
    let mut table = [0u8; 256];
    let exp = build_exp_table();
    let mut i = 0;
    while i < 255 {
        table[exp[i] as usize] = i as u8;
        i += 1;
    }
    table
}

/// Exponentiation table for GF(2^8).
///
/// `EXP_TABLE[i]` = primitive^i for i in 0..510.
/// Doubled to avoid modular reduction on log sums.
pub(crate) const EXP_TABLE: [u8; 512] = build_exp_table();

/// Logarithm table for GF(2^8).
///
/// `LOG_TABLE[x]` = i such that primitive^i = x, for nonzero x.
/// `LOG_TABLE[0]` is undefined and set to 0.
pub(crate) const LOG_TABLE: [u8; 256] = build_log_table();

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

    #[test]
    fn exp_table_starts_at_one() {
        assert_eq!(EXP_TABLE[0], 1);
    }

    #[test]
    #[allow(clippy::cast_possible_truncation)]
    fn exp_table_primitive_is_three() {
        assert_eq!(EXP_TABLE[1], PRIMITIVE as u8);
    }

    #[test]
    fn exp_table_wraps_at_255() {
        // primitive^255 = 1 in GF(2^8)
        assert_eq!(EXP_TABLE[255], EXP_TABLE[0]);
    }

    #[test]
    fn log_exp_roundtrip() {
        // For every nonzero element, exp(log(x)) == x
        (1u16..256).for_each(|x| {
            let log_x = LOG_TABLE[x as usize] as usize;
            assert_eq!(
                EXP_TABLE[log_x], x as u8,
                "exp(log({x})) != {x}"
            );
        });
    }

    #[test]
    fn all_nonzero_elements_appear_in_exp() {
        // The primitive generates the entire multiplicative group
        let mut seen = [false; 256];
        (0usize..255).for_each(|i| {
            seen[EXP_TABLE[i] as usize] = true;
        });
        // Every nonzero element should appear
        (1usize..256).for_each(|x| {
            assert!(seen[x], "element {x} not generated by primitive");
        });
    }
}
