//! CRC-32C (Castagnoli / iSCSI) checksum with combine support.
//!
//! Uses a portable slicing-by-16 table implementation. Also provides GF(2)
//! matrix exponentiation for combining independently computed checksums.
//!
//! # Examples
//!
//! ```
//! let crc = mkfs_xfs::crc32c::checksum(b"123456789");
//! assert_eq!(crc, 0xE3069283);
//! ```
//!
//! Combining:
//! ```
//! let crc_a = mkfs_xfs::crc32c::checksum(b"hello ");
//! let crc_b = mkfs_xfs::crc32c::checksum(b"world!");
//! let combined = mkfs_xfs::crc32c::combine(crc_a, crc_b, 6);
//! assert_eq!(combined, mkfs_xfs::crc32c::checksum(b"hello world!"));
//! ```

/// CRC-32C (Castagnoli) reflected polynomial.
const POLY: u32 = 0x82F63B78;

const TABLES: [[u32; 256]; 16] = build_tables();

const fn build_tables() -> [[u32; 256]; 16] {
    let mut tables = [[0u32; 256]; 16];
    let mut i = 0usize;
    while i < 256 {
        let mut crc = i as u32;
        let mut bit = 0u8;
        while bit < 8 {
            crc = if crc & 1 != 0 {
                (crc >> 1) ^ POLY
            } else {
                crc >> 1
            };
            bit += 1;
        }
        tables[0][i] = crc;
        i += 1;
    }

    let mut table_idx = 1usize;
    while table_idx < 16 {
        let mut byte = 0usize;
        while byte < 256 {
            let crc = tables[table_idx - 1][byte];
            tables[table_idx][byte] = tables[0][(crc & 0xFF) as usize] ^ (crc >> 8);
            byte += 1;
        }
        table_idx += 1;
    }

    tables
}

#[inline]
fn read_u32_le(ptr: *const u8) -> u32 {
    // SAFETY: callers only pass pointers proven to be valid for at least
    // 4 bytes. We use read_unaligned because the input buffer may not be
    // naturally aligned.
    unsafe { u32::from_le(ptr.cast::<u32>().read_unaligned()) }
}

#[inline]
fn update_scalar(mut crc: u32, data: &[u8]) -> u32 {
    let mut remaining = data;

    while remaining.len() >= 16 {
        let first = read_u32_le(remaining.as_ptr());
        let second = read_u32_le(remaining.as_ptr().wrapping_add(4));
        let third = read_u32_le(remaining.as_ptr().wrapping_add(8));
        let fourth = read_u32_le(remaining.as_ptr().wrapping_add(12));
        let mixed = crc ^ first;
        crc = TABLES[15][(mixed & 0xFF) as usize]
            ^ TABLES[14][((mixed >> 8) & 0xFF) as usize]
            ^ TABLES[13][((mixed >> 16) & 0xFF) as usize]
            ^ TABLES[12][(mixed >> 24) as usize]
            ^ TABLES[11][(second & 0xFF) as usize]
            ^ TABLES[10][((second >> 8) & 0xFF) as usize]
            ^ TABLES[9][((second >> 16) & 0xFF) as usize]
            ^ TABLES[8][(second >> 24) as usize]
            ^ TABLES[7][(third & 0xFF) as usize]
            ^ TABLES[6][((third >> 8) & 0xFF) as usize]
            ^ TABLES[5][((third >> 16) & 0xFF) as usize]
            ^ TABLES[4][(third >> 24) as usize]
            ^ TABLES[3][(fourth & 0xFF) as usize]
            ^ TABLES[2][((fourth >> 8) & 0xFF) as usize]
            ^ TABLES[1][((fourth >> 16) & 0xFF) as usize]
            ^ TABLES[0][(fourth >> 24) as usize];
        remaining = &remaining[16..];
    }

    while remaining.len() >= 4 {
        let mixed = crc ^ read_u32_le(remaining.as_ptr());
        crc = TABLES[3][(mixed & 0xFF) as usize]
            ^ TABLES[2][((mixed >> 8) & 0xFF) as usize]
            ^ TABLES[1][((mixed >> 16) & 0xFF) as usize]
            ^ TABLES[0][(mixed >> 24) as usize];
        remaining = &remaining[4..];
    }

    for &byte in remaining {
        let idx = ((crc as u8) ^ byte) as usize;
        crc = TABLES[0][idx] ^ (crc >> 8);
    }

    crc
}

/// Compute CRC-32C over the entire buffer.
#[inline]
pub fn checksum(data: &[u8]) -> u32 {
    let mut crc = !0u32;
    crc = update_scalar(crc, data);
    crc ^ !0u32
}

/// Update a raw CRC-32C state without applying the usual final XOR.
///
/// XFS metadata checksums use the kernel/libxfs convention of passing an
/// explicit seed to `crc32c_le` and then storing `!crc` in the on-disk field.
#[inline]
pub fn update_raw(crc: u32, data: &[u8]) -> u32 {
    update_scalar(crc, data)
}

/// Combine two independently computed CRC-32C checksums.
///
/// Given `crc_a = checksum(A)` and `crc_b = checksum(B)`, returns
/// `checksum(A || B)` without needing the original data. `len_b` is
/// the byte length of `B`.
pub fn combine(crc_a: u32, crc_b: u32, len_b: u64) -> u32 {
    if len_b == 0 {
        return crc_a;
    }

    let mut odd = [0u32; 32];
    let mut even = [0u32; 32];

    // odd = operator for 1 zero bit
    odd[0] = POLY;
    for (i, slot) in odd.iter_mut().enumerate().skip(1) {
        *slot = 1u32 << (i - 1);
    }

    // even = operator for 2 zero bits
    gf2_matrix_square(&mut even, &odd);
    // odd = operator for 4 zero bits
    gf2_matrix_square(&mut odd, &even);

    let mut crc = crc_a;
    let mut n = len_b;
    loop {
        gf2_matrix_square(&mut even, &odd);
        if n & 1 != 0 {
            crc = gf2_matrix_times(&even, crc);
        }
        n >>= 1;
        if n == 0 {
            break;
        }

        gf2_matrix_square(&mut odd, &even);
        if n & 1 != 0 {
            crc = gf2_matrix_times(&odd, crc);
        }
        n >>= 1;
        if n == 0 {
            break;
        }
    }

    crc ^ crc_b
}

/// Multiply a GF(2) matrix by a vector.
fn gf2_matrix_times(mat: &[u32; 32], mut vec: u32) -> u32 {
    let mut result = 0u32;
    let mut i = 0;
    while vec != 0 {
        if vec & 1 != 0 {
            result ^= mat[i];
        }
        vec >>= 1;
        i += 1;
    }
    result
}

/// Square a GF(2) matrix: square = mat * mat.
fn gf2_matrix_square(square: &mut [u32; 32], mat: &[u32; 32]) {
    for i in 0..32 {
        square[i] = gf2_matrix_times(mat, mat[i]);
    }
}

/// Streaming CRC-32C hasher.
///
/// Handles the init=0xFFFFFFFF and final XOR=0xFFFFFFFF internally,
/// matching [`checksum()`]. Feed data in chunks via [`update`](Hasher::update),
/// then call [`finalize`](Hasher::finalize) to get the checksum.
///
/// # Examples
///
/// ```
/// let mut hasher = mkfs_xfs::crc32c::Hasher::new();
/// hasher.update(b"12345");
/// hasher.update(b"6789");
/// assert_eq!(hasher.finalize(), 0xE3069283);
/// ```
#[derive(Clone, Debug)]
pub struct Hasher {
    crc: u32,
}

impl Hasher {
    /// Create a new hasher with initial state.
    #[inline]
    pub fn new() -> Self {
        Self { crc: !0u32 }
    }

    /// Feed more data into the hasher.
    #[inline]
    pub fn update(&mut self, data: &[u8]) {
        self.crc = update_scalar(self.crc, data);
    }

    /// Return the CRC-32C checksum of all data fed so far.
    #[inline]
    pub fn finalize(&self) -> u32 {
        self.crc ^ !0u32
    }

    /// Reset the hasher to its initial state.
    #[inline]
    pub fn reset(&mut self) {
        self.crc = !0u32;
    }
}

impl Default for Hasher {
    fn default() -> Self {
        Self::new()
    }
}

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

    #[test]
    fn check_string_123456789() {
        assert_eq!(checksum(b"123456789"), 0xE3069283);
    }

    #[test]
    fn empty_input() {
        assert_eq!(checksum(b""), 0);
    }

    #[test]
    fn streaming_matches_oneshot() {
        let mut hasher = Hasher::new();
        hasher.update(b"12345");
        hasher.update(b"6789");
        assert_eq!(hasher.finalize(), checksum(b"123456789"));
    }

    #[test]
    fn combine_basic() {
        let crc_a = checksum(b"12345");
        let crc_b = checksum(b"6789");
        assert_eq!(combine(crc_a, crc_b, 4), checksum(b"123456789"));
    }
}
