//! CCITTFaxDecode Filter Implementation
//!
//! Implements ITU T.4 (Group 3) and ITU T.6 (Group 4) fax compression.

use super::params::CCITTFaxDecodeParams;
use crate::fitz::error::{Error, Result};

// ---------------------------------------------------------------------------
// Huffman code tables (ITU T.4)
// ---------------------------------------------------------------------------

struct HuffEntry {
    bits: u16,
    len: u8,
    run: u16,
}

macro_rules! h {
    ($bits:expr, $len:expr, $run:expr) => {
        HuffEntry {
            bits: $bits,
            len: $len,
            run: $run,
        }
    };
}

static WHITE_TERM: [HuffEntry; 64] = [
    h!(0b00110101, 8, 0),
    h!(0b000111, 6, 1),
    h!(0b0111, 4, 2),
    h!(0b1000, 4, 3),
    h!(0b1011, 4, 4),
    h!(0b1100, 4, 5),
    h!(0b1110, 4, 6),
    h!(0b1111, 4, 7),
    h!(0b10011, 5, 8),
    h!(0b10100, 5, 9),
    h!(0b00111, 5, 10),
    h!(0b01000, 5, 11),
    h!(0b001000, 6, 12),
    h!(0b000011, 6, 13),
    h!(0b110100, 6, 14),
    h!(0b110101, 6, 15),
    h!(0b101010, 6, 16),
    h!(0b101011, 6, 17),
    h!(0b0100111, 7, 18),
    h!(0b0001100, 7, 19),
    h!(0b0001000, 7, 20),
    h!(0b0010111, 7, 21),
    h!(0b0000011, 7, 22),
    h!(0b0000100, 7, 23),
    h!(0b0101000, 7, 24),
    h!(0b0101011, 7, 25),
    h!(0b0010011, 7, 26),
    h!(0b0100100, 7, 27),
    h!(0b0011000, 7, 28),
    h!(0b00000010, 8, 29),
    h!(0b00000011, 8, 30),
    h!(0b00011010, 8, 31),
    h!(0b00011011, 8, 32),
    h!(0b00010010, 8, 33),
    h!(0b00010011, 8, 34),
    h!(0b00010100, 8, 35),
    h!(0b00010101, 8, 36),
    h!(0b00010110, 8, 37),
    h!(0b00010111, 8, 38),
    h!(0b00101000, 8, 39),
    h!(0b00101001, 8, 40),
    h!(0b00101010, 8, 41),
    h!(0b00101011, 8, 42),
    h!(0b00101100, 8, 43),
    h!(0b00101101, 8, 44),
    h!(0b00000100, 8, 45),
    h!(0b00000101, 8, 46),
    h!(0b00001010, 8, 47),
    h!(0b00001011, 8, 48),
    h!(0b01010010, 8, 49),
    h!(0b01010011, 8, 50),
    h!(0b01010100, 8, 51),
    h!(0b01010101, 8, 52),
    h!(0b00100100, 8, 53),
    h!(0b00100101, 8, 54),
    h!(0b01011000, 8, 55),
    h!(0b01011001, 8, 56),
    h!(0b01011010, 8, 57),
    h!(0b01011011, 8, 58),
    h!(0b01001010, 8, 59),
    h!(0b01001011, 8, 60),
    h!(0b00110010, 8, 61),
    h!(0b00110011, 8, 62),
    h!(0b00110100, 8, 63),
];

static BLACK_TERM: [HuffEntry; 64] = [
    h!(0b0000110111, 10, 0),
    h!(0b010, 3, 1),
    h!(0b11, 2, 2),
    h!(0b10, 2, 3),
    h!(0b011, 3, 4),
    h!(0b0011, 4, 5),
    h!(0b0010, 4, 6),
    h!(0b00011, 5, 7),
    h!(0b000101, 6, 8),
    h!(0b000100, 6, 9),
    h!(0b0000100, 7, 10),
    h!(0b0000101, 7, 11),
    h!(0b0000111, 7, 12),
    h!(0b00000100, 8, 13),
    h!(0b00000111, 8, 14),
    h!(0b00001100, 8, 15),
    h!(0b0000010111, 10, 16),
    h!(0b0000011000, 10, 17),
    h!(0b0000001000, 10, 18),
    h!(0b00001100111, 11, 19),
    h!(0b00001101000, 11, 20),
    h!(0b00001101100, 11, 21),
    h!(0b00000110111, 11, 22),
    h!(0b00000101000, 11, 23),
    h!(0b00000010111, 11, 24),
    h!(0b00000011000, 11, 25),
    h!(0b000011001010, 12, 26),
    h!(0b000011001011, 12, 27),
    h!(0b000011001100, 12, 28),
    h!(0b000011001101, 12, 29),
    h!(0b000001101000, 12, 30),
    h!(0b000001101001, 12, 31),
    h!(0b000001101010, 12, 32),
    h!(0b000001101011, 12, 33),
    h!(0b000011010010, 12, 34),
    h!(0b000011010011, 12, 35),
    h!(0b000011010100, 12, 36),
    h!(0b000011010101, 12, 37),
    h!(0b000011010110, 12, 38),
    h!(0b000011010111, 12, 39),
    h!(0b000011011000, 12, 40),
    h!(0b000011011001, 12, 41),
    h!(0b000011011010, 12, 42),
    h!(0b000011011011, 12, 43),
    h!(0b000001010010, 12, 44),
    h!(0b000001010011, 12, 45),
    h!(0b000001010100, 12, 46),
    h!(0b000001010101, 12, 47),
    h!(0b000001100100, 12, 48),
    h!(0b000001100101, 12, 49),
    h!(0b000001010010, 12, 50),
    h!(0b000001010011, 12, 51),
    h!(0b000001011100, 12, 52),
    h!(0b000001011101, 12, 53),
    h!(0b000001100100, 12, 54),
    h!(0b000001100101, 12, 55),
    h!(0b000001010010, 12, 56),
    h!(0b000001010011, 12, 57),
    h!(0b000000100100, 12, 58),
    h!(0b000000110111, 12, 59),
    h!(0b000000111000, 12, 60),
    h!(0b000000100111, 12, 61),
    h!(0b000000101000, 12, 62),
    h!(0b000001011001, 12, 63),
];

struct MakeUpEntry {
    bits: u16,
    len: u8,
    run: u16,
}

macro_rules! mu {
    ($bits:expr, $len:expr, $run:expr) => {
        MakeUpEntry {
            bits: $bits,
            len: $len,
            run: $run,
        }
    };
}

static WHITE_MAKEUP: [MakeUpEntry; 27] = [
    mu!(0b11011, 5, 64),
    mu!(0b10010, 5, 128),
    mu!(0b010111, 6, 192),
    mu!(0b0110111, 7, 256),
    mu!(0b00110110, 8, 320),
    mu!(0b00110111, 8, 384),
    mu!(0b01100100, 8, 448),
    mu!(0b01100101, 8, 512),
    mu!(0b01101000, 8, 576),
    mu!(0b01100111, 8, 640),
    mu!(0b011001100, 9, 704),
    mu!(0b011001101, 9, 768),
    mu!(0b011010010, 9, 832),
    mu!(0b011010011, 9, 896),
    mu!(0b011010100, 9, 960),
    mu!(0b011010101, 9, 1024),
    mu!(0b011010110, 9, 1088),
    mu!(0b011010111, 9, 1152),
    mu!(0b011011000, 9, 1216),
    mu!(0b011011001, 9, 1280),
    mu!(0b011011010, 9, 1344),
    mu!(0b011011011, 9, 1408),
    mu!(0b010011000, 9, 1472),
    mu!(0b010011001, 9, 1536),
    mu!(0b010011010, 9, 1600),
    mu!(0b011000, 6, 1664),
    mu!(0b010011011, 9, 1728),
];

static BLACK_MAKEUP: [MakeUpEntry; 27] = [
    mu!(0b0000001111, 10, 64),
    mu!(0b000011001000, 12, 128),
    mu!(0b000011001001, 12, 192),
    mu!(0b000001011011, 12, 256),
    mu!(0b000000110011, 12, 320),
    mu!(0b000000110100, 12, 384),
    mu!(0b000000110101, 12, 448),
    mu!(0b0000001101100, 13, 512),
    mu!(0b0000001101101, 13, 576),
    mu!(0b0000001001010, 13, 640),
    mu!(0b0000001001011, 13, 704),
    mu!(0b0000001001100, 13, 768),
    mu!(0b0000001001101, 13, 832),
    mu!(0b0000001110010, 13, 896),
    mu!(0b0000001110011, 13, 960),
    mu!(0b0000001110100, 13, 1024),
    mu!(0b0000001110101, 13, 1088),
    mu!(0b0000001110110, 13, 1152),
    mu!(0b0000001110111, 13, 1216),
    mu!(0b0000001010010, 13, 1280),
    mu!(0b0000001010011, 13, 1344),
    mu!(0b0000001010100, 13, 1408),
    mu!(0b0000001010101, 13, 1472),
    mu!(0b0000001011010, 13, 1536),
    mu!(0b0000001011011, 13, 1600),
    mu!(0b0000001100100, 13, 1664),
    mu!(0b0000001100101, 13, 1728),
];

static COMMON_MAKEUP: [MakeUpEntry; 13] = [
    mu!(0b00000001000, 11, 1792),
    mu!(0b00000001100, 11, 1856),
    mu!(0b00000001101, 11, 1920),
    mu!(0b000000010010, 12, 1984),
    mu!(0b000000010011, 12, 2048),
    mu!(0b000000010100, 12, 2112),
    mu!(0b000000010101, 12, 2176),
    mu!(0b000000010110, 12, 2240),
    mu!(0b000000010111, 12, 2304),
    mu!(0b000000011100, 12, 2368),
    mu!(0b000000011101, 12, 2432),
    mu!(0b000000011110, 12, 2496),
    mu!(0b000000011111, 12, 2560),
];

// ---------------------------------------------------------------------------
// Prefix-tree decoder
// ---------------------------------------------------------------------------

const TREE_SIZE: usize = 8192;
const NO_VALUE: i16 = i16::MIN;

struct CodeTree {
    left: Vec<i16>,
    right: Vec<i16>,
    value: Vec<i16>,
    next: usize,
}

impl CodeTree {
    fn new() -> Self {
        Self {
            left: vec![-1i16; TREE_SIZE],
            right: vec![-1i16; TREE_SIZE],
            value: vec![NO_VALUE; TREE_SIZE],
            next: 1,
        }
    }

    fn insert(&mut self, bits: u16, len: u8, val: i16) {
        let mut node = 0usize;
        for i in (0..len).rev() {
            let bit = (bits >> i) & 1;
            let child = if bit == 0 {
                &mut self.left[node]
            } else {
                &mut self.right[node]
            };
            if *child < 0 {
                *child = self.next as i16;
                self.next += 1;
            }
            node = *child as usize;
        }
        self.value[node] = val;
    }

    fn decode(&self, reader: &mut BitReader) -> Option<i16> {
        let mut node = 0usize;
        loop {
            if self.value[node] != NO_VALUE {
                return Some(self.value[node]);
            }
            let bit = reader.read_bit()?;
            let child = if bit {
                self.right[node]
            } else {
                self.left[node]
            };
            if child < 0 {
                return None;
            }
            node = child as usize;
        }
    }
}

fn build_run_tree(term: &[HuffEntry], makeup: &[MakeUpEntry], common: &[MakeUpEntry]) -> CodeTree {
    let mut tree = CodeTree::new();
    for e in term {
        tree.insert(e.bits, e.len, e.run as i16);
    }
    for e in makeup {
        tree.insert(e.bits, e.len, e.run as i16);
    }
    for e in common {
        tree.insert(e.bits, e.len, e.run as i16);
    }
    tree
}

// ---------------------------------------------------------------------------
// Bit reader / writer
// ---------------------------------------------------------------------------

struct BitReader<'a> {
    data: &'a [u8],
    byte_pos: usize,
    bit_pos: u8,
}

impl<'a> BitReader<'a> {
    fn new(data: &'a [u8]) -> Self {
        Self {
            data,
            byte_pos: 0,
            bit_pos: 0,
        }
    }

    fn read_bit(&mut self) -> Option<bool> {
        if self.byte_pos >= self.data.len() {
            return None;
        }
        let bit = (self.data[self.byte_pos] >> (7 - self.bit_pos)) & 1;
        self.bit_pos += 1;
        if self.bit_pos >= 8 {
            self.bit_pos = 0;
            self.byte_pos += 1;
        }
        Some(bit != 0)
    }

    fn align_to_byte(&mut self) {
        if self.bit_pos != 0 {
            self.bit_pos = 0;
            self.byte_pos += 1;
        }
    }

    fn is_eof(&self) -> bool {
        self.byte_pos >= self.data.len()
    }

    fn peek_bits(&self, n: u8) -> Option<u32> {
        let mut tmp = BitReader {
            data: self.data,
            byte_pos: self.byte_pos,
            bit_pos: self.bit_pos,
        };
        let mut val = 0u32;
        for _ in 0..n {
            val = (val << 1) | (tmp.read_bit()? as u32);
        }
        Some(val)
    }

    fn skip_bits(&mut self, n: u8) {
        for _ in 0..n {
            let _ = self.read_bit();
        }
    }
}

struct BitWriter {
    data: Vec<u8>,
    current: u8,
    bit_pos: u8,
}

impl BitWriter {
    fn new() -> Self {
        Self {
            data: Vec::new(),
            current: 0,
            bit_pos: 0,
        }
    }

    fn write_bit(&mut self, bit: bool) {
        if bit {
            self.current |= 1 << (7 - self.bit_pos);
        }
        self.bit_pos += 1;
        if self.bit_pos >= 8 {
            self.data.push(self.current);
            self.current = 0;
            self.bit_pos = 0;
        }
    }

    fn write_bits(&mut self, bits: u16, len: u8) {
        for i in (0..len).rev() {
            self.write_bit((bits >> i) & 1 != 0);
        }
    }

    fn flush(mut self) -> Vec<u8> {
        if self.bit_pos > 0 {
            self.data.push(self.current);
        }
        self.data
    }
}

// ---------------------------------------------------------------------------
// Row-level pixel helpers
// ---------------------------------------------------------------------------

fn get_pixel(row: &[u8], x: usize) -> bool {
    if x / 8 >= row.len() {
        return false;
    }
    (row[x / 8] >> (7 - (x % 8))) & 1 != 0
}

fn set_pixel(row: &mut [u8], x: usize) {
    if x / 8 < row.len() {
        row[x / 8] |= 1 << (7 - (x % 8));
    }
}

fn fill_run(row: &mut [u8], start: usize, length: usize) {
    for i in start..start + length {
        set_pixel(row, i);
    }
}

fn find_b1(reference: &[u8], a0: usize, width: usize, a0_color: bool) -> usize {
    let search_color = !a0_color;
    let start = if a0 == 0 { 0 } else { a0 };
    let mut x = start;
    // Find first changing element on reference line to the right of a0 with opposite color
    // First skip pixels of a0_color
    while x < width && get_pixel(reference, x) == a0_color {
        x += 1;
    }
    // Now we're at a pixel of search_color (opposite of a0_color)
    // This is b1 if it's a changing element after a0
    // But b1 must be a changing element of opposite color to a0_color
    // We already found the first such pixel
    if x < width && get_pixel(reference, x) == search_color {
        return x;
    }
    width
}

fn find_b2(reference: &[u8], b1: usize, width: usize) -> usize {
    if b1 >= width {
        return width;
    }
    let b1_color = get_pixel(reference, b1);
    let mut x = b1 + 1;
    while x < width && get_pixel(reference, x) == b1_color {
        x += 1;
    }
    x.min(width)
}

// ---------------------------------------------------------------------------
// 1D (Group 3) decode
// ---------------------------------------------------------------------------

fn decode_1d_line(
    reader: &mut BitReader,
    row: &mut [u8],
    width: usize,
    white_tree: &CodeTree,
    black_tree: &CodeTree,
) -> Result<()> {
    row.fill(0);
    let mut x = 0usize;
    let mut is_white = true;

    while x < width {
        let tree = if is_white { white_tree } else { black_tree };
        let mut run_length = 0usize;

        loop {
            let code = tree
                .decode(reader)
                .ok_or_else(|| Error::Generic("CCITT: invalid Huffman code in 1D line".into()))?;
            run_length += code as usize;
            if code < 64 {
                break; // Terminating code
            }
        }

        if !is_white && run_length > 0 {
            let end = (x + run_length).min(width);
            fill_run(row, x, end - x);
        }
        x += run_length;
        is_white = !is_white;
    }
    Ok(())
}

// ---------------------------------------------------------------------------
// 2D (Group 4 / Group 3-2D) decode
// ---------------------------------------------------------------------------

fn decode_2d_line(
    reader: &mut BitReader,
    reference: &[u8],
    row: &mut [u8],
    width: usize,
    white_tree: &CodeTree,
    black_tree: &CodeTree,
) -> Result<()> {
    row.fill(0);
    let mut a0: usize = 0;
    let mut a0_color = false; // false=white, true=black

    while a0 < width {
        let b1 = find_b1(reference, a0, width, a0_color);
        let b2 = find_b2(reference, b1, width);

        if let Some(bits) = reader.peek_bits(7) {
            if bits >> 6 == 1 {
                // V(0): 1
                reader.skip_bits(1);
                let a1 = b1.min(width);
                if a0_color && a1 > a0 {
                    fill_run(row, a0, a1 - a0);
                }
                a0 = a1;
                a0_color = !a0_color;
            } else if bits >> 4 == 0b011 {
                // VR(1): 011
                reader.skip_bits(3);
                let a1 = (b1 + 1).min(width);
                if a0_color && a1 > a0 {
                    fill_run(row, a0, a1 - a0);
                }
                a0 = a1;
                a0_color = !a0_color;
            } else if bits >> 4 == 0b010 {
                // VL(1): 010
                reader.skip_bits(3);
                let a1 = b1.saturating_sub(1).max(a0);
                if a0_color && a1 > a0 {
                    fill_run(row, a0, a1 - a0);
                }
                a0 = a1;
                a0_color = !a0_color;
            } else if bits >> 1 == 0b000011 {
                // VR(2): 000011
                reader.skip_bits(6);
                let a1 = (b1 + 2).min(width);
                if a0_color && a1 > a0 {
                    fill_run(row, a0, a1 - a0);
                }
                a0 = a1;
                a0_color = !a0_color;
            } else if bits >> 1 == 0b000010 {
                // VL(2): 000010
                reader.skip_bits(6);
                let a1 = b1.saturating_sub(2).max(a0);
                if a0_color && a1 > a0 {
                    fill_run(row, a0, a1 - a0);
                }
                a0 = a1;
                a0_color = !a0_color;
            } else if bits == 0b0000011 {
                // VR(3): 0000011
                reader.skip_bits(7);
                let a1 = (b1 + 3).min(width);
                if a0_color && a1 > a0 {
                    fill_run(row, a0, a1 - a0);
                }
                a0 = a1;
                a0_color = !a0_color;
            } else if bits == 0b0000010 {
                // VL(3): 0000010
                reader.skip_bits(7);
                let a1 = b1.saturating_sub(3).max(a0);
                if a0_color && a1 > a0 {
                    fill_run(row, a0, a1 - a0);
                }
                a0 = a1;
                a0_color = !a0_color;
            } else if bits >> 3 == 0b0001 {
                // Pass: 0001
                reader.skip_bits(4);
                if a0_color && b2 > a0 {
                    fill_run(row, a0, b2 - a0);
                }
                a0 = b2;
            } else if bits >> 4 == 0b001 {
                // Horizontal: 001 + a0a1 + a1a2
                reader.skip_bits(3);
                let tree1 = if a0_color { black_tree } else { white_tree };
                let tree2 = if a0_color { white_tree } else { black_tree };

                let mut run1 = 0usize;
                loop {
                    let code = tree1.decode(reader).ok_or_else(|| {
                        Error::Generic("CCITT: bad code in horizontal mode run1".into())
                    })?;
                    run1 += code as usize;
                    if code < 64 {
                        break;
                    }
                }

                let mut run2 = 0usize;
                loop {
                    let code = tree2.decode(reader).ok_or_else(|| {
                        Error::Generic("CCITT: bad code in horizontal mode run2".into())
                    })?;
                    run2 += code as usize;
                    if code < 64 {
                        break;
                    }
                }

                // First run is a0_color; fill if black
                if a0_color {
                    let end = (a0 + run1).min(width);
                    fill_run(row, a0, end - a0);
                }
                a0 = (a0 + run1).min(width);
                // Second run is !a0_color; fill if black
                if !a0_color {
                    let end = (a0 + run2).min(width);
                    fill_run(row, a0, end - a0);
                }
                a0 = (a0 + run2).min(width);
            } else if bits >> 3 == 0 {
                if let Some(eofb) = reader.peek_bits(12) {
                    if eofb == 0b000000000001 {
                        return Err(Error::Generic("EOFB".into()));
                    }
                }
                return Err(Error::Generic("CCITT: unrecognized 2D code".into()));
            } else {
                return Err(Error::Generic("CCITT: unrecognized 2D code".into()));
            }
        } else {
            break;
        }
    }
    Ok(())
}

// ---------------------------------------------------------------------------
// EOL detection
// ---------------------------------------------------------------------------

fn skip_eol(reader: &mut BitReader, align: bool) -> bool {
    if align {
        reader.align_to_byte();
    }
    if let Some(bits) = reader.peek_bits(12) {
        if bits == 0b000000000001 {
            reader.skip_bits(12);
            return true;
        }
    }
    false
}

// ---------------------------------------------------------------------------
// Public decode API
// ---------------------------------------------------------------------------

/// Decode CCITT Group 3/4 fax encoded data
pub fn decode_ccitt_fax(data: &[u8], params: &CCITTFaxDecodeParams) -> Result<Vec<u8>> {
    let width = params.columns as usize;
    if width == 0 {
        return Ok(Vec::new());
    }

    let bytes_per_row = width.div_ceil(8);
    let white_tree = build_run_tree(&WHITE_TERM, &WHITE_MAKEUP, &COMMON_MAKEUP);
    let black_tree = build_run_tree(&BLACK_TERM, &BLACK_MAKEUP, &COMMON_MAKEUP);

    let mut reader = BitReader::new(data);
    let max_rows = if params.rows > 0 {
        params.rows as usize
    } else {
        100_000
    };

    let mut result = Vec::with_capacity(bytes_per_row * max_rows.min(1000));
    let mut reference_line = vec![0u8; bytes_per_row]; // all-white reference
    let mut current_line = vec![0u8; bytes_per_row];

    if params.k < 0 {
        // Group 4 (pure 2D)
        for _ in 0..max_rows {
            if reader.is_eof() {
                break;
            }
            // Check for EOFB before starting a new row
            if let Some(eofb) = reader.peek_bits(12) {
                if eofb == 0b000000000001 {
                    break;
                }
            }
            match decode_2d_line(
                &mut reader,
                &reference_line,
                &mut current_line,
                width,
                &white_tree,
                &black_tree,
            ) {
                Ok(()) => {
                    result.extend_from_slice(&current_line);
                    std::mem::swap(&mut reference_line, &mut current_line);
                    current_line.fill(0);
                }
                Err(_) => break,
            }
        }
    } else if params.k == 0 {
        // Group 3 1D
        for _ in 0..max_rows {
            if reader.is_eof() {
                break;
            }
            if params.end_of_line && !skip_eol(&mut reader, params.encoded_byte_align) {
                break;
            }
            if params.encoded_byte_align {
                reader.align_to_byte();
            }
            match decode_1d_line(
                &mut reader,
                &mut current_line,
                width,
                &white_tree,
                &black_tree,
            ) {
                Ok(()) => {
                    result.extend_from_slice(&current_line);
                    current_line.fill(0);
                }
                Err(_) => break,
            }
        }
    } else {
        // Group 3 2D (k > 0): every k-th line is 1D, others are 2D
        let mut line_index = 0usize;
        for _ in 0..max_rows {
            if reader.is_eof() {
                break;
            }
            if params.end_of_line && !skip_eol(&mut reader, params.encoded_byte_align) {
                break;
            }
            if params.encoded_byte_align {
                reader.align_to_byte();
            }

            // Tag bit: 0 = 1D, 1 = 2D
            let tag = reader.read_bit();
            let is_2d = tag == Some(true);

            let decode_result = if !is_2d || line_index % (params.k as usize) == 0 {
                decode_1d_line(
                    &mut reader,
                    &mut current_line,
                    width,
                    &white_tree,
                    &black_tree,
                )
            } else {
                decode_2d_line(
                    &mut reader,
                    &reference_line,
                    &mut current_line,
                    width,
                    &white_tree,
                    &black_tree,
                )
            };

            match decode_result {
                Ok(()) => {
                    result.extend_from_slice(&current_line);
                    std::mem::swap(&mut reference_line, &mut current_line);
                    current_line.fill(0);
                    line_index += 1;
                }
                Err(_) => break,
            }
        }
    }

    // Apply black_is_1 transformation (PDF default: 0=black, 1=white)
    // When black_is_1 is false (default), we need to invert because
    // CCITT standard has 1=black, but PDF expects 0=black
    if !params.black_is_1 {
        for byte in &mut result {
            *byte = !*byte;
        }
    }

    Ok(result)
}

// ---------------------------------------------------------------------------
// Group 4 encoder
// ---------------------------------------------------------------------------

fn encode_run(writer: &mut BitWriter, run: usize, is_white: bool) {
    let term = if is_white { &WHITE_TERM } else { &BLACK_TERM };
    let makeup = if is_white {
        &WHITE_MAKEUP
    } else {
        &BLACK_MAKEUP
    };

    let mut remaining = run;

    while remaining >= 64 {
        // Find largest fitting make-up code.
        // Common make-up codes cover 1792–2560 (shared between white/black).
        // Color-specific make-up codes cover 64–1728.
        let mut best_bits = 0u16;
        let mut best_len = 0u8;
        let mut best_run = 0usize;

        for entry in COMMON_MAKEUP.iter().rev() {
            if (entry.run as usize) <= remaining {
                best_bits = entry.bits;
                best_len = entry.len;
                best_run = entry.run as usize;
                break;
            }
        }
        if best_run == 0 {
            for entry in makeup.iter().rev() {
                if (entry.run as usize) <= remaining {
                    best_bits = entry.bits;
                    best_len = entry.len;
                    best_run = entry.run as usize;
                    break;
                }
            }
        }
        if best_run == 0 {
            break;
        }
        writer.write_bits(best_bits, best_len);
        remaining -= best_run;
    }

    writer.write_bits(term[remaining].bits, term[remaining].len);
}

/// Encode bitmap data using CCITT fax compression with the given parameters.
/// Uses Group 4 encoding (the only encode mode supported).
pub fn encode_ccitt_fax(data: &[u8], params: &CCITTFaxDecodeParams) -> Result<Vec<u8>> {
    let width = params.columns as usize;
    let bytes_per_row = width.div_ceil(8);
    let height = if params.rows > 0 {
        params.rows as usize
    } else {
        data.len() / bytes_per_row.max(1)
    };
    encode_ccitt_g4(data, width, height)
}

/// Encode bitmap data using CCITT Group 4
pub fn encode_ccitt_g4(data: &[u8], width: usize, height: usize) -> Result<Vec<u8>> {
    if width == 0 || height == 0 {
        return Ok(Vec::new());
    }

    let bytes_per_row = width.div_ceil(8);
    if data.len() < bytes_per_row * height {
        return Err(Error::Generic(
            "CCITT encode: insufficient data for dimensions".into(),
        ));
    }

    let mut writer = BitWriter::new();
    let empty_ref = vec![0u8; bytes_per_row]; // all-white reference

    for row_idx in 0..height {
        let row = &data[row_idx * bytes_per_row..(row_idx + 1) * bytes_per_row];
        let reference = if row_idx == 0 {
            &empty_ref
        } else {
            &data[(row_idx - 1) * bytes_per_row..row_idx * bytes_per_row]
        };

        let mut a0: usize = 0;
        let mut a0_color = false; // white

        while a0 < width {
            let b1 = find_b1(reference, a0, width, a0_color);
            let b2 = find_b2(reference, b1, width);

            // Find a1 (first changing element on current line after a0)
            let cur_color_at_a0 = if a0 < width {
                get_pixel(row, a0)
            } else {
                false
            };
            let _ = cur_color_at_a0;
            let mut a1 = a0;
            let seek_color = a0_color;
            while a1 < width && get_pixel(row, a1) == seek_color {
                a1 += 1;
            }

            // Find a2
            let mut a2 = a1;
            if a1 < width {
                let a1_color = get_pixel(row, a1);
                while a2 < width && get_pixel(row, a2) == a1_color {
                    a2 += 1;
                }
            }

            // Choose coding mode
            if b2 < a1 {
                // Pass mode
                writer.write_bits(0b0001, 4);
                a0 = b2;
            } else {
                let diff = (a1 as isize) - (b1 as isize);
                if (-3..=3).contains(&diff) {
                    // Vertical mode
                    match diff {
                        0 => writer.write_bits(0b1, 1),
                        1 => writer.write_bits(0b011, 3),
                        -1 => writer.write_bits(0b010, 3),
                        2 => writer.write_bits(0b000011, 6),
                        -2 => writer.write_bits(0b000010, 6),
                        3 => writer.write_bits(0b0000011, 7),
                        -3 => writer.write_bits(0b0000010, 7),
                        _ => unreachable!(),
                    }
                    a0 = a1;
                    a0_color = !a0_color;
                } else {
                    // Horizontal mode
                    writer.write_bits(0b001, 3);
                    let run1 = a1 - a0;
                    let run2 = a2 - a1;
                    encode_run(&mut writer, run1, !a0_color); // a0 color
                    encode_run(&mut writer, run2, a0_color); // opposite
                    a0 = a2;
                }
            }
        }
    }

    // Write EOFB (two consecutive EOL codes)
    writer.write_bits(0b000000000001, 12);
    writer.write_bits(0b000000000001, 12);

    Ok(writer.flush())
}

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

    fn make_white_row(width: usize) -> Vec<u8> {
        vec![0u8; width.div_ceil(8)]
    }

    fn make_black_row(width: usize) -> Vec<u8> {
        let bytes_per_row = width.div_ceil(8);
        let mut row = vec![0xFFu8; bytes_per_row];
        let extra_bits = width % 8;
        if extra_bits > 0 {
            let mask = 0xFFu8 << (8 - extra_bits);
            row[bytes_per_row - 1] = mask;
        }
        row
    }

    #[test]
    fn test_bit_reader_basic() {
        let data = [0b10110001u8, 0b01001110u8];
        let mut reader = BitReader::new(&data);
        assert_eq!(reader.read_bit(), Some(true));
        assert_eq!(reader.read_bit(), Some(false));
        assert_eq!(reader.read_bit(), Some(true));
        assert_eq!(reader.read_bit(), Some(true));
        assert_eq!(reader.read_bit(), Some(false));
        assert_eq!(reader.read_bit(), Some(false));
        assert_eq!(reader.read_bit(), Some(false));
        assert_eq!(reader.read_bit(), Some(true));
        // Second byte
        assert_eq!(reader.read_bit(), Some(false));
    }

    #[test]
    fn test_bit_writer_basic() {
        let mut writer = BitWriter::new();
        writer.write_bit(true);
        writer.write_bit(false);
        writer.write_bit(true);
        writer.write_bit(true);
        writer.write_bit(false);
        writer.write_bit(false);
        writer.write_bit(false);
        writer.write_bit(true);
        let data = writer.flush();
        assert_eq!(data, vec![0b10110001u8]);
    }

    #[test]
    fn test_pixel_helpers() {
        let mut row = vec![0u8; 2];
        set_pixel(&mut row, 0);
        assert!(get_pixel(&row, 0));
        assert!(!get_pixel(&row, 1));

        set_pixel(&mut row, 7);
        assert!(get_pixel(&row, 7));

        set_pixel(&mut row, 8);
        assert!(get_pixel(&row, 8));
    }

    #[test]
    fn test_fill_run() {
        let mut row = vec![0u8; 2];
        fill_run(&mut row, 2, 5);
        // Bits 2,3,4,5,6 should be set
        assert!(!get_pixel(&row, 0));
        assert!(!get_pixel(&row, 1));
        assert!(get_pixel(&row, 2));
        assert!(get_pixel(&row, 3));
        assert!(get_pixel(&row, 4));
        assert!(get_pixel(&row, 5));
        assert!(get_pixel(&row, 6));
        assert!(!get_pixel(&row, 7));
    }

    #[test]
    fn test_g4_encode_all_white() {
        let width = 16;
        let height = 4;
        let data = vec![0u8; 2 * height];
        let encoded = encode_ccitt_g4(&data, width, height).unwrap();
        assert!(!encoded.is_empty());
    }

    #[test]
    fn test_g4_encode_all_black() {
        let width = 16;
        let height = 4;
        let row = make_black_row(width);
        let mut data = Vec::new();
        for _ in 0..height {
            data.extend_from_slice(&row);
        }
        let encoded = encode_ccitt_g4(&data, width, height).unwrap();
        assert!(!encoded.is_empty());
    }

    #[test]
    fn test_g4_roundtrip_all_white() {
        let width = 32;
        let height = 4;
        let original = vec![0u8; 4 * height];

        let encoded = encode_ccitt_g4(&original, width, height).unwrap();

        let params = CCITTFaxDecodeParams {
            k: -1,
            columns: width as i32,
            rows: height as i32,
            black_is_1: true,
            ..Default::default()
        };

        let decoded = decode_ccitt_fax(&encoded, &params).unwrap();
        assert_eq!(decoded.len(), original.len());
        assert_eq!(decoded, original);
    }

    #[test]
    fn test_g4_roundtrip_alternating() {
        let width = 16;
        let height = 2;
        let bytes_per_row = 2;
        // 0xAA = 10101010 pattern
        let original = vec![0xAA; bytes_per_row * height];

        let encoded = encode_ccitt_g4(&original, width, height).unwrap();

        let params = CCITTFaxDecodeParams {
            k: -1,
            columns: width as i32,
            rows: height as i32,
            black_is_1: true,
            ..Default::default()
        };

        let decoded = decode_ccitt_fax(&encoded, &params).unwrap();
        assert_eq!(decoded.len(), original.len());
        assert_eq!(decoded, original);
    }

    #[test]
    fn test_g4_roundtrip_mixed() {
        let width = 24;
        let height = 3;
        let bytes_per_row = 3;
        let original = vec![
            0xFF, 0x00, 0xFF, // black, white, black
            0x00, 0xFF, 0x00, // white, black, white
            0xAA, 0x55, 0xCC, // mixed patterns
        ];

        let encoded = encode_ccitt_g4(&original, width, height).unwrap();

        let params = CCITTFaxDecodeParams {
            k: -1,
            columns: width as i32,
            rows: height as i32,
            black_is_1: true,
            ..Default::default()
        };

        let decoded = decode_ccitt_fax(&encoded, &params).unwrap();
        assert_eq!(decoded.len(), original.len());
        assert_eq!(decoded, original);
    }

    #[test]
    fn test_g4_non_byte_aligned_width() {
        let width = 11;
        let height = 2;
        let bytes_per_row = 2;
        // Only first 11 bits matter per row
        let mut original = vec![0u8; bytes_per_row * height];
        // Set some bits in the valid range
        set_pixel(&mut original[0..bytes_per_row], 0);
        set_pixel(&mut original[0..bytes_per_row], 5);
        set_pixel(&mut original[0..bytes_per_row], 10);

        let encoded = encode_ccitt_g4(&original, width, height).unwrap();

        let params = CCITTFaxDecodeParams {
            k: -1,
            columns: width as i32,
            rows: height as i32,
            black_is_1: true,
            ..Default::default()
        };

        let decoded = decode_ccitt_fax(&encoded, &params).unwrap();
        assert_eq!(decoded.len(), original.len());
        // Compare only the valid bits
        for y in 0..height {
            for x in 0..width {
                let orig = get_pixel(&original[y * bytes_per_row..(y + 1) * bytes_per_row], x);
                let dec = get_pixel(&decoded[y * bytes_per_row..(y + 1) * bytes_per_row], x);
                assert_eq!(orig, dec, "Mismatch at row {} col {}", y, x);
            }
        }
    }

    #[test]
    fn test_black_is_1_inversion() {
        let width = 8;
        let height = 1;
        let original = vec![0xF0u8]; // 11110000

        let encoded = encode_ccitt_g4(&original, width, height).unwrap();

        // With black_is_1 = true, should match
        let params_true = CCITTFaxDecodeParams {
            k: -1,
            columns: 8,
            rows: 1,
            black_is_1: true,
            ..Default::default()
        };
        let decoded_true = decode_ccitt_fax(&encoded, &params_true).unwrap();
        assert_eq!(decoded_true, original);

        // With black_is_1 = false (default), should be inverted
        let params_false = CCITTFaxDecodeParams {
            k: -1,
            columns: 8,
            rows: 1,
            black_is_1: false,
            ..Default::default()
        };
        let decoded_false = decode_ccitt_fax(&encoded, &params_false).unwrap();
        assert_eq!(decoded_false, vec![0x0Fu8]);
    }

    #[test]
    fn test_empty_dimensions() {
        let params = CCITTFaxDecodeParams {
            k: -1,
            columns: 0,
            rows: 0,
            ..Default::default()
        };
        let result = decode_ccitt_fax(&[], &params).unwrap();
        assert!(result.is_empty());
    }

    #[test]
    fn test_encode_insufficient_data() {
        let result = encode_ccitt_g4(&[0u8; 1], 16, 2);
        assert!(result.is_err());
    }

    #[test]
    fn test_code_tree_construction() {
        let white_tree = build_run_tree(&WHITE_TERM, &WHITE_MAKEUP, &COMMON_MAKEUP);
        let black_tree = build_run_tree(&BLACK_TERM, &BLACK_MAKEUP, &COMMON_MAKEUP);
        // Trees should have been built without panic
        assert!(white_tree.next > 1);
        assert!(black_tree.next > 1);
    }

    #[test]
    fn test_1d_roundtrip_via_encode_decode() {
        // Encode with G4, decode as G4 — verifies the codec pair works
        let width = 48;
        let height = 5;
        let bytes_per_row = width / 8;
        let mut original = vec![0u8; bytes_per_row * height];
        // Create a pattern: each row has a different stripe
        for y in 0..height {
            for x in 0..width {
                if (x / 8 + y) % 2 == 0 {
                    set_pixel(&mut original[y * bytes_per_row..(y + 1) * bytes_per_row], x);
                }
            }
        }

        let encoded = encode_ccitt_g4(&original, width, height).unwrap();
        let params = CCITTFaxDecodeParams {
            k: -1,
            columns: width as i32,
            rows: height as i32,
            black_is_1: true,
            ..Default::default()
        };
        let decoded = decode_ccitt_fax(&encoded, &params).unwrap();
        assert_eq!(decoded, original);
    }
}
