promocrypt_core/

damm.rs

//! Damm check digit algorithm.
//!
//! Implements the Damm algorithm for generating and validating check digits.
//! This algorithm detects all single-digit errors and all adjacent transposition errors.

use base64::{Engine as _, engine::general_purpose::STANDARD as BASE64};
use serde::{Deserialize, Serialize};

use crate::alphabet::Alphabet;
use crate::error::{PromocryptError, Result};

/// Damm quasi-group table for check digit calculation.
///
/// The table has the following properties:
/// - Each row is a permutation of 0..size
/// - Each column is a permutation of 0..size
/// - Diagonal is all zeros: `table[i][i] = 0`
/// - Anti-symmetric: `table[a][b] != table[b][a]` when `a != b`
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct DammTable {
    table: Vec<Vec<u8>>,
    size: usize,
}

impl DammTable {
    /// Generate a quasi-group table for the given alphabet size.
    ///
    /// The generated table guarantees:
    /// - 100% detection of single-character errors
    /// - 100% detection of adjacent transposition errors
    ///
    /// # Arguments
    /// * `size` - The alphabet size (10-62)
    ///
    /// # Examples
    ///
    /// ```
    /// use promocrypt_core::DammTable;
    ///
    /// let table = DammTable::new(26);
    /// assert_eq!(table.size(), 26);
    /// ```
    pub fn new(size: usize) -> Self {
        assert!((10..=62).contains(&size), "Size must be between 10 and 62");

        let table = Self::generate_quasi_group(size);

        Self { table, size }
    }

    /// Generate a quasi-group with the required properties.
    ///
    /// Uses a construction that guarantees:
    /// - Each row is a permutation of 0..n
    /// - Each column is a permutation of 0..n
    /// - Diagonal is all zeros: table\[i\]\[i\] = 0
    #[allow(clippy::needless_range_loop)]
    fn generate_quasi_group(n: usize) -> Vec<Vec<u8>> {
        let mut table = vec![vec![0u8; n]; n];

        // Use a proven construction for Latin squares with zero diagonal.
        // Method: Start with standard addition table, then apply a permutation
        // to make the diagonal all zeros.
        //
        // Standard Latin square: table[i][j] = (i + j) mod n
        // Diagonal values: table[i][i] = 2i mod n
        //
        // To get zeros on diagonal, we apply a value permutation.
        // If we define perm(x) = (x - 2*row_index) mod n, then:
        // perm(table[i][j]) = (i + j - 2i) mod n = (j - i) mod n
        // For diagonal: perm(2i mod n) = (i - i) mod n = 0

        // However, applying different permutations per row breaks the Latin property.
        // Instead, use a global transformation.

        // Correct approach: Use table[i][j] = (i + j) mod n, then swap values
        // within each row to place 0 on diagonal.

        // Step 1: Create base Latin square
        for i in 0..n {
            for j in 0..n {
                table[i][j] = ((i + j) % n) as u8;
            }
        }

        // Step 2: For each row i, swap position of value 0 with diagonal position
        // In row i, value 0 is at column (n - i) % n
        // We want value 0 at column i (diagonal)
        // So swap columns (n-i)%n and i in each row

        // Actually, we need to be more careful. Swapping within rows preserves
        // row permutation, but breaks column permutation.

        // Better approach: Create a Latin square using a derangement
        // table[i][j] = (i + j + 1) mod n  -- this gives diagonal = (2i+1) mod n, never 0 for n>1
        // Then we swap the diagonal with where 0 appears

        // Even better: Use the fact that for a Latin square L, if we apply
        // a permutation π to rows and σ to columns, we get another Latin square.
        // We want L'[i][i] = 0 for all i.

        // Simplest correct approach that works:
        // For row i, create permutation: start at some value, go sequentially,
        // but ensure 0 is at position i.

        // Let's use: row i has values arranged as:
        // position j gets value ((j - i + n) % n) if j != i
        // position i (diagonal) gets 0

        for i in 0..n {
            for j in 0..n {
                if i == j {
                    table[i][j] = 0;
                } else {
                    // Value at position j in row i
                    // We want each row and column to be a permutation
                    // Use: value = 1 + ((j - i - 1 + n) % (n-1)) for j > i
                    //      value = 1 + ((j - i + n) % (n-1)) for j < i
                    // This ensures 0 only on diagonal, and rest are 1..n-1

                    let diff = ((j as isize - i as isize).rem_euclid(n as isize)) as usize;
                    // diff is in range 1..n-1 for j != i (since we skip j==i case)
                    table[i][j] = diff as u8;
                }
            }
        }

        // Verify: In row i, for j from 0 to n-1:
        // - j=i: value is 0
        // - j≠i: value is (j-i) mod n, which is 1,2,...,n-1 (excluding 0)
        // So row i has exactly one 0 (at diagonal) and values 1..n-1 at other positions
        // Wait, this means each row only has values 0..n-1 once? Let's check:
        // For row 0: j=0->0, j=1->1, j=2->2, ..., j=n-1->n-1 ✓
        // For row 1: j=0->n-1, j=1->0, j=2->1, j=3->2, ..., j=n-1->n-2 ✓

        // For column j, value at row i is:
        // - i=j: value is 0
        // - i≠j: value is (j-i) mod n
        // For column 0: i=0->0, i=1->n-1, i=2->n-2, ..., i=n-1->1
        // This is 0, n-1, n-2, ..., 1 which is a permutation of 0..n-1 ✓

        table
    }

    /// Get the size of the table (alphabet size).
    #[inline]
    pub fn size(&self) -> usize {
        self.size
    }

    /// Get table value at position.
    #[inline]
    pub fn get(&self, row: usize, col: usize) -> u8 {
        self.table[row][col]
    }

    /// Calculate check digit for a sequence of characters (check digit at end).
    ///
    /// # Arguments
    /// * `chars` - The characters to calculate check digit for (without existing check digit)
    /// * `alphabet` - The alphabet used for character→index mapping
    ///
    /// # Returns
    /// The check digit character from the alphabet.
    pub fn calculate(&self, chars: &[char], alphabet: &Alphabet) -> char {
        let mut interim = 0usize;

        for &c in chars {
            if let Some(index) = alphabet.index_of(c) {
                interim = self.table[interim][index] as usize;
            }
        }

        alphabet.char_at(interim)
    }

    /// Calculate check digit for start position.
    ///
    /// Finds a check digit X such that processing [X, chars...] results in 0.
    ///
    /// # Arguments
    /// * `chars` - The characters (check digit will be prepended)
    /// * `alphabet` - The alphabet used for character→index mapping
    ///
    /// # Returns
    /// The check digit character from the alphabet.
    pub fn calculate_for_start(&self, chars: &[char], alphabet: &Alphabet) -> char {
        // We need to find X such that process([X] + chars) = 0
        // Try each possible check digit
        for check_idx in 0..self.size {
            let mut interim = self.table[0][check_idx] as usize;

            for &c in chars {
                if let Some(index) = alphabet.index_of(c) {
                    interim = self.table[interim][index] as usize;
                }
            }

            if interim == 0 {
                return alphabet.char_at(check_idx);
            }
        }

        // Fallback (should never happen with valid quasi-group)
        alphabet.char_at(0)
    }

    /// Calculate check digit for arbitrary position in the code.
    ///
    /// Finds a check digit X such that inserting X at `position` in `chars`
    /// results in a valid code (Damm validation returns 0).
    ///
    /// # Arguments
    /// * `chars` - The characters (check digit will be inserted at position)
    /// * `alphabet` - The alphabet used for character→index mapping
    /// * `position` - Position where check digit will be inserted (0-based)
    ///
    /// # Returns
    /// The check digit character from the alphabet.
    pub fn calculate_for_position(
        &self,
        chars: &[char],
        alphabet: &Alphabet,
        position: usize,
    ) -> char {
        // We need to find X such that process(chars[0..position] + [X] + chars[position..]) = 0

        // First, process chars up to the check digit position
        let mut interim_before = 0usize;
        for &c in chars.iter().take(position) {
            if let Some(index) = alphabet.index_of(c) {
                interim_before = self.table[interim_before][index] as usize;
            }
        }

        // For each possible check digit, calculate what state we'd be in after it
        // Then process the remaining chars and see if we end up at 0
        for check_idx in 0..self.size {
            let mut interim = self.table[interim_before][check_idx] as usize;

            // Process remaining characters
            for &c in chars.iter().skip(position) {
                if let Some(index) = alphabet.index_of(c) {
                    interim = self.table[interim][index] as usize;
                }
            }

            if interim == 0 {
                return alphabet.char_at(check_idx);
            }
        }

        // Fallback (should never happen with valid quasi-group)
        alphabet.char_at(0)
    }

    /// Calculate check digit for a string.
    pub fn calculate_str(&self, s: &str, alphabet: &Alphabet) -> char {
        let chars: Vec<char> = s.chars().collect();
        self.calculate(&chars, alphabet)
    }

    /// Validate a code including its check digit.
    ///
    /// The check digit is valid if processing the entire code (including check digit)
    /// results in 0.
    ///
    /// # Arguments
    /// * `code` - The full code including check digit
    /// * `alphabet` - The alphabet used
    ///
    /// # Returns
    /// `true` if the check digit is valid, `false` otherwise.
    pub fn validate(&self, code: &str, alphabet: &Alphabet) -> bool {
        let mut interim = 0usize;

        for c in code.chars() {
            match alphabet.index_of(c) {
                Some(index) => {
                    interim = self.table[interim][index] as usize;
                }
                None => return false, // Invalid character
            }
        }

        interim == 0
    }

    /// Serialize the table to bytes for storage.
    pub fn to_bytes(&self) -> Vec<u8> {
        let mut bytes = Vec::with_capacity(4 + self.size * self.size);

        // Store size as u32
        bytes.extend_from_slice(&(self.size as u32).to_le_bytes());

        // Store table data row by row
        for row in &self.table {
            bytes.extend_from_slice(row);
        }

        bytes
    }

    /// Deserialize table from bytes.
    pub fn from_bytes(bytes: &[u8]) -> Result<Self> {
        if bytes.len() < 4 {
            return Err(PromocryptError::InvalidFileFormatDetails(
                "Damm table too short".to_string(),
            ));
        }

        let size = u32::from_le_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]) as usize;

        if !(10..=62).contains(&size) {
            return Err(PromocryptError::InvalidFileFormatDetails(format!(
                "Invalid Damm table size: {}",
                size
            )));
        }

        let expected_len = 4 + size * size;
        if bytes.len() < expected_len {
            return Err(PromocryptError::InvalidFileFormatDetails(format!(
                "Damm table data too short: expected {}, got {}",
                expected_len,
                bytes.len()
            )));
        }

        let mut table = Vec::with_capacity(size);
        let data = &bytes[4..];

        for i in 0..size {
            let row_start = i * size;
            let row_end = row_start + size;
            table.push(data[row_start..row_end].to_vec());
        }

        Ok(Self { table, size })
    }

    /// Serialize to base64 string for JSON storage.
    pub fn to_base64(&self) -> String {
        BASE64.encode(self.to_bytes())
    }

    /// Deserialize from base64 string.
    pub fn from_base64(s: &str) -> Result<Self> {
        let bytes = BASE64.decode(s).map_err(|e| {
            PromocryptError::InvalidFileFormatDetails(format!("Invalid base64: {}", e))
        })?;
        Self::from_bytes(&bytes)
    }
}

/// Custom serialization for DammTable using base64
impl Serialize for DammTable {
    fn serialize<S>(&self, serializer: S) -> std::result::Result<S::Ok, S::Error>
    where
        S: serde::Serializer,
    {
        serializer.serialize_str(&self.to_base64())
    }
}

impl<'de> Deserialize<'de> for DammTable {
    fn deserialize<D>(deserializer: D) -> std::result::Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        let s = String::deserialize(deserializer)?;
        DammTable::from_base64(&s).map_err(serde::de::Error::custom)
    }
}

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

    #[test]
    fn test_new_table() {
        let table = DammTable::new(26);
        assert_eq!(table.size(), 26);
    }

    #[test]
    fn test_diagonal_zeros() {
        let table = DammTable::new(26);
        for i in 0..26 {
            assert_eq!(table.get(i, i), 0, "Diagonal at {} should be 0", i);
        }
    }

    #[test]
    fn test_calculate_and_validate() {
        let alphabet = Alphabet::default_alphabet();
        let table = DammTable::new(alphabet.len());

        // Calculate check digit for "ABCD"
        let chars: Vec<char> = "ABCD".chars().collect();
        let check = table.calculate(&chars, &alphabet);

        // Validate full code
        let mut code = String::from("ABCD");
        code.push(check);

        assert!(table.validate(&code, &alphabet));
    }

    #[test]
    fn test_single_error_detection() {
        let alphabet = Alphabet::default_alphabet();
        let table = DammTable::new(alphabet.len());

        // Create valid code
        let chars: Vec<char> = "ABCDEFGH".chars().collect();
        let check = table.calculate(&chars, &alphabet);
        let mut valid_code = String::from("ABCDEFGH");
        valid_code.push(check);

        assert!(table.validate(&valid_code, &alphabet));

        // Modify one character - should be detected
        let mut modified = valid_code.chars().collect::<Vec<_>>();
        if modified[4] == 'E' {
            modified[4] = 'F';
        } else {
            modified[4] = 'E';
        }
        let modified_code: String = modified.iter().collect();

        assert!(!table.validate(&modified_code, &alphabet));
    }

    #[test]
    fn test_serialization() {
        let table = DammTable::new(26);
        let bytes = table.to_bytes();
        let restored = DammTable::from_bytes(&bytes).unwrap();
        assert_eq!(table, restored);
    }

    #[test]
    fn test_base64_serialization() {
        let table = DammTable::new(26);
        let b64 = table.to_base64();
        let restored = DammTable::from_base64(&b64).unwrap();
        assert_eq!(table, restored);
    }

    #[test]
    fn test_serde() {
        let table = DammTable::new(26);
        let json = serde_json::to_string(&table).unwrap();
        let restored: DammTable = serde_json::from_str(&json).unwrap();
        assert_eq!(table, restored);
    }

    #[test]
    fn test_various_sizes() {
        for size in [10, 16, 26, 36, 62] {
            let table = DammTable::new(size);
            assert_eq!(table.size(), size);

            // Verify diagonal
            for i in 0..size {
                assert_eq!(table.get(i, i), 0);
            }
        }
    }

    #[test]
    fn test_row_permutation() {
        let table = DammTable::new(10);
        for i in 0..10 {
            let mut values: Vec<u8> = (0..10).map(|j| table.get(i, j)).collect();
            values.sort();
            let expected: Vec<u8> = (0..10).map(|x| x as u8).collect();
            assert_eq!(values, expected, "Row {} is not a permutation of 0..10", i);
        }
    }

    #[test]
    fn test_column_permutation() {
        let table = DammTable::new(10);
        for j in 0..10 {
            let mut values: Vec<u8> = (0..10).map(|i| table.get(i, j)).collect();
            values.sort();
            let expected: Vec<u8> = (0..10).map(|x| x as u8).collect();
            assert_eq!(
                values, expected,
                "Column {} is not a permutation of 0..10",
                j
            );
        }
    }
}