//! GIF decoder (GIF87a / GIF89a) — pure Rust.
//!
//! Supports single-frame and animated GIFs, global and local color tables,
//! LZW decompression, transparency via Graphic Control Extension, interlacing,
//! and frame disposal methods.

use crate::pixel::{self, Image, ImageError};

// ---------------------------------------------------------------------------
// Constants
// ---------------------------------------------------------------------------

const GIF87A: &[u8; 6] = b"GIF87a";
const GIF89A: &[u8; 6] = b"GIF89a";

const IMAGE_DESCRIPTOR: u8 = 0x2C;
const EXTENSION_INTRODUCER: u8 = 0x21;
const TRAILER: u8 = 0x3B;

const GRAPHIC_CONTROL_EXT: u8 = 0xF9;
const APPLICATION_EXT: u8 = 0xFF;
const COMMENT_EXT: u8 = 0xFE;
const PLAIN_TEXT_EXT: u8 = 0x01;

// ---------------------------------------------------------------------------
// Disposal method
// ---------------------------------------------------------------------------

/// How the decoder should handle the frame's area before drawing the next frame.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DisposalMethod {
    /// No disposal specified — leave the frame in place.
    None,
    /// Do not dispose — leave the frame in place (same as None).
    DoNotDispose,
    /// Restore the area to the background color.
    RestoreBackground,
    /// Restore the area to the previous frame's content.
    RestorePrevious,
}

impl DisposalMethod {
    fn from_byte(b: u8) -> Self {
        match b {
            0 => Self::None,
            1 => Self::DoNotDispose,
            2 => Self::RestoreBackground,
            3 => Self::RestorePrevious,
            _ => Self::None,
        }
    }
}

// ---------------------------------------------------------------------------
// GifFrame
// ---------------------------------------------------------------------------

/// A single frame from an animated GIF.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct GifFrame {
    /// The frame image in RGBA8.
    pub image: Image,
    /// Delay time in hundredths of a second (centiseconds).
    pub delay_cs: u16,
    /// Disposal method for this frame.
    pub disposal: DisposalMethod,
}

// ---------------------------------------------------------------------------
// LZW decompressor
// ---------------------------------------------------------------------------

/// LZW decompressor for GIF image data.
///
/// GIF uses a variable-width LZW scheme with clear and EOI codes. The minimum
/// code size is specified per sub-image. Codes are packed LSB-first.
struct LzwDecoder {
    min_code_size: u8,
    clear_code: u16,
    eoi_code: u16,
    /// Current entries in the code table. Each entry is stored as
    /// (prefix_code, suffix_byte). Single-byte entries have prefix = u16::MAX.
    table: Vec<(u16, u8)>,
    code_size: u8,
    next_code: u16,
}

impl LzwDecoder {
    fn new(min_code_size: u8) -> Self {
        let clear_code = 1u16 << min_code_size;
        let eoi_code = clear_code + 1;
        Self {
            min_code_size,
            clear_code,
            eoi_code,
            table: Vec::new(),
            code_size: min_code_size + 1,
            next_code: 0,
        }
    }

    fn reset(&mut self) {
        self.table.clear();
        let initial_entries = (1u16 << self.min_code_size) + 2;
        self.table.reserve(initial_entries as usize);
        for i in 0..self.clear_code {
            self.table.push((u16::MAX, i as u8));
        }
        // Clear code and EOI code entries (not used for output, but occupy slots)
        self.table.push((u16::MAX, 0)); // clear code
        self.table.push((u16::MAX, 0)); // eoi code
        self.code_size = self.min_code_size + 1;
        self.next_code = self.eoi_code + 1;
    }

    /// Emit the string for a code into `output`. Returns the first byte of the string.
    fn emit(&self, code: u16, output: &mut Vec<u8>) -> u8 {
        // Walk the chain to find the string length, then write in reverse.
        let start = output.len();
        let mut c = code;
        loop {
            let (prefix, suffix) = self.table[c as usize];
            output.push(suffix);
            if prefix == u16::MAX {
                break;
            }
            c = prefix;
        }
        // Reverse the appended portion
        output[start..].reverse();
        output[start]
    }

    /// Get the first byte of the string for a code.
    fn first_byte(&self, code: u16) -> u8 {
        let mut c = code;
        loop {
            let (prefix, suffix) = self.table[c as usize];
            if prefix == u16::MAX {
                return suffix;
            }
            c = prefix;
        }
    }

    fn add_entry(&mut self, prefix: u16, suffix: u8) {
        if self.next_code < 4096 {
            self.table.push((prefix, suffix));
            self.next_code += 1;
            // Increase code size when all codes at the current size are used (early change)
            if self.next_code >= (1 << self.code_size) && self.code_size < 12 {
                self.code_size += 1;
            }
        }
    }

    /// Decompress LZW data from packed sub-blocks.
    fn decompress(&mut self, data: &[u8]) -> Result<Vec<u8>, ImageError> {
        self.reset();
        let mut reader = LzwBitReader::new(data);
        let mut output = Vec::new();

        // First code must be a clear code
        let first = reader.read_bits(self.code_size)?;
        if first != self.clear_code {
            return Err(ImageError::Decode(
                "GIF LZW: expected clear code at start".into(),
            ));
        }

        // Read the first data code after clear
        let mut prev_code = reader.read_bits(self.code_size)?;
        if prev_code == self.eoi_code {
            return Ok(output);
        }
        if prev_code >= self.next_code {
            return Err(ImageError::Decode("GIF LZW: invalid first code".into()));
        }
        self.emit(prev_code, &mut output);

        while let Ok(code) = reader.read_bits(self.code_size) {
            if code == self.eoi_code {
                break;
            }

            if code == self.clear_code {
                self.reset();
                prev_code = match reader.read_bits(self.code_size) {
                    Ok(c) => c,
                    Err(_) => break,
                };
                if prev_code == self.eoi_code {
                    break;
                }
                if prev_code >= self.next_code {
                    return Err(ImageError::Decode(
                        "GIF LZW: invalid code after clear".into(),
                    ));
                }
                self.emit(prev_code, &mut output);
                continue;
            }

            if code < self.next_code {
                // Code is in the table
                let first = self.first_byte(code);
                self.add_entry(prev_code, first);
                self.emit(code, &mut output);
            } else if code == self.next_code {
                // Special case: code is not yet in table
                let first = self.first_byte(prev_code);
                self.add_entry(prev_code, first);
                self.emit(code, &mut output);
            } else {
                return Err(ImageError::Decode(format!(
                    "GIF LZW: code {code} out of range (next={next})",
                    next = self.next_code
                )));
            }

            prev_code = code;
        }

        Ok(output)
    }
}

// ---------------------------------------------------------------------------
// Bit reader for LZW (LSB-first, packed)
// ---------------------------------------------------------------------------

struct LzwBitReader<'a> {
    data: &'a [u8],
    pos: usize,
    bit_buf: u32,
    bits_in_buf: u8,
}

impl<'a> LzwBitReader<'a> {
    fn new(data: &'a [u8]) -> Self {
        Self {
            data,
            pos: 0,
            bit_buf: 0,
            bits_in_buf: 0,
        }
    }

    fn read_bits(&mut self, count: u8) -> Result<u16, ImageError> {
        while self.bits_in_buf < count {
            if self.pos >= self.data.len() {
                return Err(ImageError::Decode("GIF LZW: unexpected end of data".into()));
            }
            self.bit_buf |= (self.data[self.pos] as u32) << self.bits_in_buf;
            self.pos += 1;
            self.bits_in_buf += 8;
        }
        let mask = (1u32 << count) - 1;
        let value = (self.bit_buf & mask) as u16;
        self.bit_buf >>= count;
        self.bits_in_buf -= count;
        Ok(value)
    }
}

// ---------------------------------------------------------------------------
// GIF parser internals
// ---------------------------------------------------------------------------

struct GifReader<'a> {
    data: &'a [u8],
    pos: usize,
}

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

    fn remaining(&self) -> usize {
        self.data.len().saturating_sub(self.pos)
    }

    fn read_byte(&mut self) -> Result<u8, ImageError> {
        if self.pos >= self.data.len() {
            return Err(ImageError::Decode("GIF: unexpected end of data".into()));
        }
        let b = self.data[self.pos];
        self.pos += 1;
        Ok(b)
    }

    fn read_u16_le(&mut self) -> Result<u16, ImageError> {
        if self.pos + 2 > self.data.len() {
            return Err(ImageError::Decode("GIF: unexpected end of data".into()));
        }
        let lo = self.data[self.pos] as u16;
        let hi = self.data[self.pos + 1] as u16;
        self.pos += 2;
        Ok(lo | (hi << 8))
    }

    fn read_bytes(&mut self, n: usize) -> Result<&'a [u8], ImageError> {
        if self.pos + n > self.data.len() {
            return Err(ImageError::Decode("GIF: unexpected end of data".into()));
        }
        let slice = &self.data[self.pos..self.pos + n];
        self.pos += n;
        Ok(slice)
    }

    /// Read concatenated sub-blocks (size-prefixed, terminated by a zero-length block).
    fn read_sub_blocks(&mut self) -> Result<Vec<u8>, ImageError> {
        let mut result = Vec::new();
        loop {
            let block_size = self.read_byte()? as usize;
            if block_size == 0 {
                break;
            }
            let block = self.read_bytes(block_size)?;
            result.extend_from_slice(block);
        }
        Ok(result)
    }

    /// Skip sub-blocks without collecting data.
    fn skip_sub_blocks(&mut self) -> Result<(), ImageError> {
        loop {
            let block_size = self.read_byte()? as usize;
            if block_size == 0 {
                break;
            }
            if self.pos + block_size > self.data.len() {
                return Err(ImageError::Decode("GIF: unexpected end of data".into()));
            }
            self.pos += block_size;
        }
        Ok(())
    }
}

// ---------------------------------------------------------------------------
// Graphic Control Extension
// ---------------------------------------------------------------------------

struct GraphicControl {
    disposal: DisposalMethod,
    transparent_color: Option<u8>,
    delay_cs: u16,
}

// ---------------------------------------------------------------------------
// Logical Screen Descriptor
// ---------------------------------------------------------------------------

struct ScreenDescriptor {
    width: u16,
    height: u16,
    global_color_table: Option<Vec<u8>>,
    background_index: u8,
}

fn parse_header_and_screen(reader: &mut GifReader<'_>) -> Result<ScreenDescriptor, ImageError> {
    // Validate signature
    if reader.remaining() < 6 {
        return Err(ImageError::Decode("GIF: data too short for header".into()));
    }
    let sig = reader.read_bytes(6)?;
    if sig != GIF87A.as_slice() && sig != GIF89A.as_slice() {
        return Err(ImageError::Decode("GIF: invalid signature".into()));
    }

    // Logical screen descriptor (7 bytes)
    let width = reader.read_u16_le()?;
    let height = reader.read_u16_le()?;
    let packed = reader.read_byte()?;
    let background_index = reader.read_byte()?;
    let _pixel_aspect_ratio = reader.read_byte()?;

    let has_gct = (packed & 0x80) != 0;
    let gct_size_field = packed & 0x07;

    let global_color_table = if has_gct {
        let num_entries = 1usize << (gct_size_field as usize + 1);
        let table_bytes = num_entries * 3;
        let table = reader.read_bytes(table_bytes)?;
        Some(table.to_vec())
    } else {
        None
    };

    Ok(ScreenDescriptor {
        width,
        height,
        global_color_table,
        background_index,
    })
}

// ---------------------------------------------------------------------------
// GIF interlace pass reordering
// ---------------------------------------------------------------------------

/// GIF interlaced images use 4 passes with these parameters:
/// Pass 1: start row 0, step 8
/// Pass 2: start row 4, step 8
/// Pass 3: start row 2, step 4
/// Pass 4: start row 1, step 2
const INTERLACE_PASSES: [(usize, usize); 4] = [(0, 8), (4, 8), (2, 4), (1, 2)];

fn deinterlace(data: &[u8], width: usize, height: usize) -> Vec<u8> {
    let row_bytes = width;
    let mut output = vec![0u8; width * height];
    let mut src_row = 0usize;

    for &(start, step) in &INTERLACE_PASSES {
        let mut y = start;
        while y < height {
            let src_offset = src_row * row_bytes;
            let dst_offset = y * row_bytes;
            if src_offset + row_bytes <= data.len() {
                output[dst_offset..dst_offset + row_bytes]
                    .copy_from_slice(&data[src_offset..src_offset + row_bytes]);
            }
            src_row += 1;
            y += step;
        }
    }

    output
}

// ---------------------------------------------------------------------------
// Frame decoding
// ---------------------------------------------------------------------------

struct RawFrame {
    left: u16,
    top: u16,
    width: u16,
    height: u16,
    color_table: Vec<u8>,
    transparent_color: Option<u8>,
    disposal: DisposalMethod,
    delay_cs: u16,
    /// Decompressed indexed pixel data.
    indices: Vec<u8>,
}

fn decode_frame(
    reader: &mut GifReader<'_>,
    global_ct: &Option<Vec<u8>>,
    gce: Option<GraphicControl>,
) -> Result<RawFrame, ImageError> {
    // Image descriptor
    let left = reader.read_u16_le()?;
    let top = reader.read_u16_le()?;
    let width = reader.read_u16_le()?;
    let height = reader.read_u16_le()?;
    let packed = reader.read_byte()?;

    let has_lct = (packed & 0x80) != 0;
    let interlaced = (packed & 0x40) != 0;
    let lct_size_field = packed & 0x07;

    let local_color_table = if has_lct {
        let num_entries = 1usize << (lct_size_field as usize + 1);
        let table_bytes = num_entries * 3;
        let table = reader.read_bytes(table_bytes)?;
        table.to_vec()
    } else {
        Vec::new()
    };

    // Determine which color table to use
    let color_table = if !local_color_table.is_empty() {
        local_color_table
    } else if let Some(ref gct) = global_ct {
        gct.clone()
    } else {
        return Err(ImageError::Decode("GIF: no color table available".into()));
    };

    // LZW minimum code size
    let min_code_size = reader.read_byte()?;
    if min_code_size > 11 {
        return Err(ImageError::Decode(format!(
            "GIF: invalid LZW minimum code size {min_code_size}"
        )));
    }

    // Read LZW sub-blocks
    let lzw_data = reader.read_sub_blocks()?;

    // Decompress
    let mut decoder = LzwDecoder::new(min_code_size);
    let mut indices = decoder.decompress(&lzw_data)?;

    // Deinterlace if needed
    if interlaced && width > 0 && height > 0 {
        indices = deinterlace(&indices, width as usize, height as usize);
    }

    let (disposal, transparent_color, delay_cs) = match gce {
        Some(gc) => (gc.disposal, gc.transparent_color, gc.delay_cs),
        None => (DisposalMethod::None, None, 0),
    };

    Ok(RawFrame {
        left,
        top,
        width,
        height,
        color_table,
        transparent_color,
        disposal,
        delay_cs,
        indices,
    })
}

/// Render a raw frame's indices into an RGBA8 image.
fn render_frame(frame: &RawFrame) -> Result<Image, ImageError> {
    let w = frame.width as u32;
    let h = frame.height as u32;
    if w == 0 || h == 0 {
        return Err(ImageError::Decode("GIF: frame has zero dimension".into()));
    }

    let pixel_count = w as usize * h as usize;
    let palette = &frame.color_table;
    let palette_len = palette.len() / 3;

    // Truncate indices to expected pixel count (some GIFs have extra data)
    let indices = if frame.indices.len() >= pixel_count {
        &frame.indices[..pixel_count]
    } else {
        // Pad with zeros if data is short
        return render_frame_padded(frame, pixel_count, palette, palette_len);
    };

    match frame.transparent_color {
        Some(tc) => {
            let mut data = Vec::with_capacity(pixel_count * 4);
            for &idx in indices {
                if idx == tc {
                    data.extend_from_slice(&[0, 0, 0, 0]);
                } else {
                    let i = idx as usize;
                    if i >= palette_len {
                        return Err(ImageError::PaletteIndexOutOfBounds {
                            index: idx,
                            palette_len,
                        });
                    }
                    let offset = i * 3;
                    data.push(palette[offset]);
                    data.push(palette[offset + 1]);
                    data.push(palette[offset + 2]);
                    data.push(255);
                }
            }
            Image::new(w, h, data)
        }
        None => pixel::from_indexed(w, h, palette, indices),
    }
}

fn render_frame_padded(
    frame: &RawFrame,
    pixel_count: usize,
    palette: &[u8],
    palette_len: usize,
) -> Result<Image, ImageError> {
    let w = frame.width as u32;
    let h = frame.height as u32;
    let mut data = Vec::with_capacity(pixel_count * 4);
    for i in 0..pixel_count {
        let idx = if i < frame.indices.len() {
            frame.indices[i]
        } else {
            0
        };
        if let Some(tc) = frame.transparent_color {
            if idx == tc {
                data.extend_from_slice(&[0, 0, 0, 0]);
                continue;
            }
        }
        let ci = idx as usize;
        if ci >= palette_len {
            return Err(ImageError::PaletteIndexOutOfBounds {
                index: idx,
                palette_len,
            });
        }
        let offset = ci * 3;
        data.push(palette[offset]);
        data.push(palette[offset + 1]);
        data.push(palette[offset + 2]);
        data.push(255);
    }
    Image::new(w, h, data)
}

// ---------------------------------------------------------------------------
// Canvas compositing for animated GIFs
// ---------------------------------------------------------------------------

fn composite_frame(
    canvas: &mut [u8],
    canvas_width: u32,
    canvas_height: u32,
    frame: &RawFrame,
    frame_image: &Image,
) {
    let cx = frame.left as usize;
    let cy = frame.top as usize;
    let fw = frame.width as usize;
    let fh = frame.height as usize;
    let cw = canvas_width as usize;
    let ch = canvas_height as usize;

    for row in 0..fh {
        let dy = cy + row;
        if dy >= ch {
            break;
        }
        for col in 0..fw {
            let dx = cx + col;
            if dx >= cw {
                break;
            }
            let src_off = (row * fw + col) * 4;
            let dst_off = (dy * cw + dx) * 4;
            let a = frame_image.data[src_off + 3];
            if a > 0 {
                canvas[dst_off] = frame_image.data[src_off];
                canvas[dst_off + 1] = frame_image.data[src_off + 1];
                canvas[dst_off + 2] = frame_image.data[src_off + 2];
                canvas[dst_off + 3] = frame_image.data[src_off + 3];
            }
        }
    }
}

fn apply_disposal(
    canvas: &mut [u8],
    prev_canvas: &[u8],
    frame: &RawFrame,
    canvas_width: u32,
    canvas_height: u32,
    bg_index: u8,
    color_table: &Option<Vec<u8>>,
) {
    match frame.disposal {
        DisposalMethod::RestoreBackground => {
            let cx = frame.left as usize;
            let cy = frame.top as usize;
            let fw = frame.width as usize;
            let fh = frame.height as usize;
            let cw = canvas_width as usize;
            let ch = canvas_height as usize;

            // Background color from the global color table
            let (br, bg, bb) = if let Some(ref gct) = color_table {
                let i = bg_index as usize;
                let palette_len = gct.len() / 3;
                if i < palette_len {
                    let off = i * 3;
                    (gct[off], gct[off + 1], gct[off + 2])
                } else {
                    (0, 0, 0)
                }
            } else {
                (0, 0, 0)
            };

            for row in 0..fh {
                let dy = cy + row;
                if dy >= ch {
                    break;
                }
                for col in 0..fw {
                    let dx = cx + col;
                    if dx >= cw {
                        break;
                    }
                    let off = (dy * cw + dx) * 4;
                    canvas[off] = br;
                    canvas[off + 1] = bg;
                    canvas[off + 2] = bb;
                    canvas[off + 3] = 0; // transparent background
                }
            }
        }
        DisposalMethod::RestorePrevious => {
            canvas.copy_from_slice(prev_canvas);
        }
        DisposalMethod::None | DisposalMethod::DoNotDispose => {
            // Leave canvas as-is
        }
    }
}

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

/// Decode a GIF image, returning the first frame as an RGBA8 image.
///
/// For single-frame GIFs this returns the only frame. For animated GIFs this
/// returns the composited first frame at the logical screen dimensions.
pub fn decode_gif(data: &[u8]) -> Result<Image, ImageError> {
    let frames = decode_gif_frames(data)?;
    if frames.is_empty() {
        return Err(ImageError::Decode("GIF: no frames found".into()));
    }
    Ok(frames.into_iter().next().unwrap().image)
}

/// Decode all frames from a GIF image.
///
/// Each frame is composited onto the logical screen canvas according to the
/// frame's position, disposal method, and transparency settings. The returned
/// `Image` in each `GifFrame` has the logical screen dimensions.
pub fn decode_gif_frames(data: &[u8]) -> Result<Vec<GifFrame>, ImageError> {
    let mut reader = GifReader::new(data);
    let screen = parse_header_and_screen(&mut reader)?;

    let sw = screen.width as u32;
    let sh = screen.height as u32;
    if sw == 0 || sh == 0 {
        return Err(ImageError::Decode(
            "GIF: logical screen has zero dimension".into(),
        ));
    }

    let canvas_size = sw as usize * sh as usize * 4;
    let mut canvas = vec![0u8; canvas_size];
    let mut prev_canvas = vec![0u8; canvas_size];
    let mut frames = Vec::new();
    let mut current_gce: Option<GraphicControl> = None;

    loop {
        if reader.remaining() == 0 {
            break;
        }
        let block_type = reader.read_byte()?;

        match block_type {
            TRAILER => break,

            EXTENSION_INTRODUCER => {
                let label = reader.read_byte()?;
                match label {
                    GRAPHIC_CONTROL_EXT => {
                        let block_size = reader.read_byte()?;
                        if block_size != 4 {
                            return Err(ImageError::Decode(
                                "GIF: invalid graphic control extension size".into(),
                            ));
                        }
                        let packed = reader.read_byte()?;
                        let delay_cs = reader.read_u16_le()?;
                        let transparent_index = reader.read_byte()?;
                        let _terminator = reader.read_byte()?;

                        let disposal = DisposalMethod::from_byte((packed >> 2) & 0x07);
                        let has_transparency = (packed & 0x01) != 0;

                        current_gce = Some(GraphicControl {
                            disposal,
                            transparent_color: if has_transparency {
                                Some(transparent_index)
                            } else {
                                None
                            },
                            delay_cs,
                        });
                    }
                    APPLICATION_EXT | COMMENT_EXT | PLAIN_TEXT_EXT => {
                        // Skip the block size and sub-blocks
                        reader.skip_sub_blocks()?;
                    }
                    _ => {
                        // Unknown extension — skip sub-blocks
                        reader.skip_sub_blocks()?;
                    }
                }
            }

            IMAGE_DESCRIPTOR => {
                let gce = current_gce.take();
                let raw = decode_frame(&mut reader, &screen.global_color_table, gce)?;
                let frame_image = render_frame(&raw)?;

                // Save canvas state before compositing (for RestorePrevious)
                prev_canvas.copy_from_slice(&canvas);

                // Composite frame onto canvas
                composite_frame(&mut canvas, sw, sh, &raw, &frame_image);

                // Output the composited canvas as this frame
                let output_image = Image::new(sw, sh, canvas.clone())?;
                frames.push(GifFrame {
                    image: output_image,
                    delay_cs: raw.delay_cs,
                    disposal: raw.disposal,
                });

                // Apply disposal for next frame
                apply_disposal(
                    &mut canvas,
                    &prev_canvas,
                    &raw,
                    sw,
                    sh,
                    screen.background_index,
                    &screen.global_color_table,
                );
            }

            _ => {
                // Unknown block type — try to skip. In practice this shouldn't happen
                // in well-formed GIFs but we don't want to fail hard.
                break;
            }
        }
    }

    Ok(frames)
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

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

    // -----------------------------------------------------------------------
    // LZW decompressor tests
    // -----------------------------------------------------------------------

    #[test]
    fn lzw_simple_sequence() {
        // LZW with min code size 2 (codes 0-3 are literal, 4=clear, 5=eoi)
        // Encode a simple sequence: clear, 0, 1, 0, 1, eoi
        // initial code_size=3, bumps to 4 after next_code reaches 8
        let mut bits: u64 = 0;
        let mut bit_pos = 0u32;

        let codes: &[(u16, u8)] = &[
            (4, 3), // clear code
            (0, 3), // literal 0
            (1, 3), // literal 1
            (0, 3), // literal 0 → add_entry makes next_code=8, code_size→4
            (1, 4), // literal 1 (now 4 bits)
            (5, 4), // eoi (4 bits)
        ];

        for &(code, nbits) in codes {
            bits |= (code as u64) << bit_pos;
            bit_pos += nbits as u32;
        }

        let byte_count = (bit_pos + 7) / 8;
        let data: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i * 8)) & 0xFF) as u8)
            .collect();

        let mut decoder = LzwDecoder::new(2);
        let result = decoder.decompress(&data).unwrap();
        assert_eq!(result, vec![0, 1, 0, 1]);
    }

    #[test]
    fn lzw_repeated_pattern() {
        // Encode: clear, 1, 1, 1, 1, eoi with min_code_size=2
        // After clear: table has 0,1,2,3, clear=4, eoi=5, next=6
        // Code size = 3
        // Read 1 -> output [1], prev=1
        // Read 1 -> in table, first_byte(1)=1, add (1,1) as code 6 -> output [1,1]
        //   next=7
        // Read 6 -> in table, first_byte(6)=1, add (1,1) as code 7 -> output [1,1,1,1]
        //   next=8 -> code_size becomes 4
        // Read 5 (eoi, now 4 bits) -> done

        let mut bits: u64 = 0;
        let mut bit_pos = 0u32;

        let codes: &[(u16, u8)] = &[
            (4, 3), // clear
            (1, 3), // literal 1
            (1, 3), // literal 1
            (6, 3), // code 6 = {1,1}
            (5, 4), // eoi (now 4 bits since next_code=8 bumped code_size)
        ];

        for &(code, nbits) in codes {
            bits |= (code as u64) << bit_pos;
            bit_pos += nbits as u32;
        }

        let byte_count = (bit_pos + 7) / 8;
        let data: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i * 8)) & 0xFF) as u8)
            .collect();

        let mut decoder = LzwDecoder::new(2);
        let result = decoder.decompress(&data).unwrap();
        assert_eq!(result, vec![1, 1, 1, 1]);
    }

    #[test]
    fn lzw_code_not_in_table() {
        // Test the special case where code == next_code
        // min_code_size=2, clear=4, eoi=5, next=6
        // Sequence: clear, 0, 6(=next), eoi
        // After 0: prev=0
        // Read 6: code == next_code, first_byte(prev=0)=0, add(0,0) as 6
        //   emit(6) = [0,0]
        // Total output: [0, 0, 0]

        let mut bits: u64 = 0;
        let mut bit_pos = 0u32;

        let codes: &[(u16, u8)] = &[
            (4, 3), // clear
            (0, 3), // literal 0
            (6, 3), // code 6 = next_code (special case)
            (5, 3), // eoi
        ];

        for &(code, nbits) in codes {
            bits |= (code as u64) << bit_pos;
            bit_pos += nbits as u32;
        }

        let byte_count = (bit_pos + 7) / 8;
        let data: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i * 8)) & 0xFF) as u8)
            .collect();

        let mut decoder = LzwDecoder::new(2);
        let result = decoder.decompress(&data).unwrap();
        assert_eq!(result, vec![0, 0, 0]);
    }

    #[test]
    fn lzw_clear_code_reset() {
        // Test that clear code resets the table
        // min_code_size=2, clear=4, eoi=5
        // Sequence: clear, 0, 1, clear, 2, 3, eoi

        let mut bits: u64 = 0;
        let mut bit_pos = 0u32;

        let codes: &[(u16, u8)] = &[
            (4, 3), // clear
            (0, 3), // literal 0
            (1, 3), // literal 1
            (4, 3), // clear (reset)
            (2, 3), // literal 2
            (3, 3), // literal 3
            (5, 3), // eoi
        ];

        for &(code, nbits) in codes {
            bits |= (code as u64) << bit_pos;
            bit_pos += nbits as u32;
        }

        let byte_count = (bit_pos + 7) / 8;
        let data: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i * 8)) & 0xFF) as u8)
            .collect();

        let mut decoder = LzwDecoder::new(2);
        let result = decoder.decompress(&data).unwrap();
        assert_eq!(result, vec![0, 1, 2, 3]);
    }

    #[test]
    fn lzw_empty_after_clear_eoi() {
        // clear then immediate eoi
        let mut bits: u64 = 0;
        let mut bit_pos = 0u32;

        let codes: &[(u16, u8)] = &[
            (4, 3), // clear
            (5, 3), // eoi
        ];

        for &(code, nbits) in codes {
            bits |= (code as u64) << bit_pos;
            bit_pos += nbits as u32;
        }

        let byte_count = (bit_pos + 7) / 8;
        let data: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i * 8)) & 0xFF) as u8)
            .collect();

        let mut decoder = LzwDecoder::new(2);
        let result = decoder.decompress(&data).unwrap();
        assert!(result.is_empty());
    }

    #[test]
    fn lzw_min_code_size_1() {
        // min_code_size=1: literals 0,1; clear=2, eoi=3
        // code_size starts at 2
        // After reading 0, 1: add_entry(0,1)=code4, next=5 > 4=1<<2 → code_size=3
        let mut bits: u64 = 0;
        let mut bit_pos = 0u32;

        let codes: &[(u16, u8)] = &[
            (2, 2), // clear (code_size=2)
            (0, 2), // literal 0
            (1, 2), // literal 1 → after this, code_size bumps to 3
            (0, 3), // literal 0 (now 3 bits)
            (3, 3), // eoi (3 bits)
        ];

        for &(code, nbits) in codes {
            bits |= (code as u64) << bit_pos;
            bit_pos += nbits as u32;
        }

        let byte_count = (bit_pos + 7) / 8;
        let data: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i * 8)) & 0xFF) as u8)
            .collect();

        let mut decoder = LzwDecoder::new(1);
        let result = decoder.decompress(&data).unwrap();
        assert_eq!(result, vec![0, 1, 0]);
    }

    #[test]
    fn lzw_min_code_size_8() {
        // min_code_size=8: literals 0-255; clear=256, eoi=257
        // code_size starts at 9
        let mut bits: u128 = 0;
        let mut bit_pos = 0u32;

        let codes: &[(u16, u8)] = &[
            (256, 9), // clear
            (0, 9),   // literal 0
            (255, 9), // literal 255
            (128, 9), // literal 128
            (257, 9), // eoi
        ];

        for &(code, nbits) in codes {
            bits |= (code as u128) << bit_pos;
            bit_pos += nbits as u32;
        }

        let byte_count = (bit_pos + 7) / 8;
        let data: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i * 8)) & 0xFF) as u8)
            .collect();

        let mut decoder = LzwDecoder::new(8);
        let result = decoder.decompress(&data).unwrap();
        assert_eq!(result, vec![0, 255, 128]);
    }

    // -----------------------------------------------------------------------
    // Deinterlace tests
    // -----------------------------------------------------------------------

    #[test]
    fn deinterlace_8_rows() {
        // With 8 rows and width=1:
        // Pass 1 (start=0, step=8): row 0
        // Pass 2 (start=4, step=8): row 4
        // Pass 3 (start=2, step=4): rows 2, 6
        // Pass 4 (start=1, step=2): rows 1, 3, 5, 7
        // Interlaced order: [0, 4, 2, 6, 1, 3, 5, 7]
        let interlaced: Vec<u8> = vec![0, 4, 2, 6, 1, 3, 5, 7];
        let result = deinterlace(&interlaced, 1, 8);
        assert_eq!(result, vec![0, 1, 2, 3, 4, 5, 6, 7]);
    }

    #[test]
    fn deinterlace_4_rows() {
        // 4 rows:
        // Pass 1 (start=0, step=8): row 0
        // Pass 2 (start=4, step=8): (none)
        // Pass 3 (start=2, step=4): row 2
        // Pass 4 (start=1, step=2): rows 1, 3
        // Interlaced order: [0, 2, 1, 3]
        let interlaced: Vec<u8> = vec![0, 2, 1, 3];
        let result = deinterlace(&interlaced, 1, 4);
        assert_eq!(result, vec![0, 1, 2, 3]);
    }

    #[test]
    fn deinterlace_1_row() {
        let interlaced: Vec<u8> = vec![42];
        let result = deinterlace(&interlaced, 1, 1);
        assert_eq!(result, vec![42]);
    }

    #[test]
    fn deinterlace_wider() {
        // 4 rows, width=2
        // Interlaced row order: 0, 2, 1, 3
        let interlaced: Vec<u8> = vec![
            10, 11, // row 0
            30, 31, // row 2
            20, 21, // row 1
            40, 41, // row 3
        ];
        let result = deinterlace(&interlaced, 2, 4);
        assert_eq!(
            result,
            vec![
                10, 11, // row 0
                20, 21, // row 1
                30, 31, // row 2
                40, 41, // row 3
            ]
        );
    }

    // -----------------------------------------------------------------------
    // Disposal method tests
    // -----------------------------------------------------------------------

    #[test]
    fn disposal_from_byte() {
        assert_eq!(DisposalMethod::from_byte(0), DisposalMethod::None);
        assert_eq!(DisposalMethod::from_byte(1), DisposalMethod::DoNotDispose);
        assert_eq!(
            DisposalMethod::from_byte(2),
            DisposalMethod::RestoreBackground
        );
        assert_eq!(
            DisposalMethod::from_byte(3),
            DisposalMethod::RestorePrevious
        );
        assert_eq!(DisposalMethod::from_byte(4), DisposalMethod::None);
        assert_eq!(DisposalMethod::from_byte(255), DisposalMethod::None);
    }

    // -----------------------------------------------------------------------
    // Full GIF decode tests (hand-crafted minimal GIFs)
    // -----------------------------------------------------------------------

    /// Build a minimal valid GIF87a with a single 1x1 red pixel.
    fn build_1x1_red_gif() -> Vec<u8> {
        let mut gif = Vec::new();

        // Header
        gif.extend_from_slice(b"GIF87a");

        // Logical screen descriptor: 1x1, GCT flag set, 1 bit color resolution
        // packed: 0x80 (has GCT) | 0x00 (color res = 0+1=1) | 0x00 (sort=0) | 0x00 (GCT size=0 -> 2 entries)
        gif.push(1);
        gif.push(0); // width=1
        gif.push(1);
        gif.push(0); // height=1
        gif.push(0x80); // packed
        gif.push(0); // background index
        gif.push(0); // pixel aspect ratio

        // GCT: 2 entries (2^(0+1) = 2)
        gif.extend_from_slice(&[255, 0, 0]); // entry 0: red
        gif.extend_from_slice(&[0, 0, 0]); // entry 1: black

        // Image descriptor
        gif.push(0x2C);
        gif.extend_from_slice(&[0, 0]); // left
        gif.extend_from_slice(&[0, 0]); // top
        gif.push(1);
        gif.push(0); // width=1
        gif.push(1);
        gif.push(0); // height=1
        gif.push(0); // packed (no LCT, no interlace)

        // LZW min code size = 2 (must be >= 2 for GIF)
        gif.push(2);

        // LZW data: clear(4), 0, eoi(5) — all in 3-bit codes
        // Bits: 100 000 101 = 0b101_000_100 packed LSB first
        // Byte 0: bits 0-7 = 00100 000 = 0b00000100 (reversed reading)
        // Let me construct this properly:
        // code 4 (clear) = 100 (3 bits)
        // code 0         = 000 (3 bits)
        // code 5 (eoi)   = 101 (3 bits)
        // Total: 9 bits packed LSB first
        // bits[0..3] = 100 = 4 (clear)
        // bits[3..6] = 000 = 0 (literal 0)
        // bits[6..9] = 101 = 5 (eoi)
        // Byte 0 (bits 0-7): bit0=0, bit1=0, bit2=1, bit3=0, bit4=0, bit5=0, bit6=1, bit7=0
        //   = 0b01000100 = 0x44
        // Byte 1 (bits 8): bit8=1
        //   = 0b00000001 = 0x01
        gif.push(2); // sub-block size = 2 bytes
        gif.push(0x44);
        gif.push(0x01);
        gif.push(0); // sub-block terminator

        // Trailer
        gif.push(0x3B);

        gif
    }

    #[test]
    fn decode_1x1_red() {
        let data = build_1x1_red_gif();
        let img = decode_gif(&data).unwrap();
        assert_eq!(img.width, 1);
        assert_eq!(img.height, 1);
        assert_eq!(img.data, vec![255, 0, 0, 255]);
    }

    /// Build a 2x2 GIF with 4 colors.
    fn build_2x2_gif() -> Vec<u8> {
        let mut gif = Vec::new();

        // Header
        gif.extend_from_slice(b"GIF89a");

        // Screen: 2x2, GCT with 4 entries (size field = 1 -> 2^(1+1) = 4)
        gif.push(2);
        gif.push(0);
        gif.push(2);
        gif.push(0);
        gif.push(0x81); // has GCT, GCT size=1 (4 entries)
        gif.push(0); // bg index
        gif.push(0); // aspect

        // GCT: 4 entries
        gif.extend_from_slice(&[255, 0, 0]); // 0: red
        gif.extend_from_slice(&[0, 255, 0]); // 1: green
        gif.extend_from_slice(&[0, 0, 255]); // 2: blue
        gif.extend_from_slice(&[255, 255, 0]); // 3: yellow

        // Image descriptor
        gif.push(0x2C);
        gif.extend_from_slice(&[0, 0, 0, 0]); // left=0, top=0
        gif.push(2);
        gif.push(0);
        gif.push(2);
        gif.push(0); // 2x2
        gif.push(0); // no LCT

        // LZW min code size = 2 (4 literal codes: 0,1,2,3; clear=4, eoi=5)
        gif.push(2);

        // Encode: clear(4), 0, 1, 2, 3, eoi(5)
        // code_size starts at 3, bumps to 4 after code 2 (next_code reaches 8)
        let mut bits: u64 = 0;
        let mut bp = 0u32;
        for &(code, nbits) in &[(4u16, 3u8), (0, 3), (1, 3), (2, 3), (3, 4), (5, 4)] {
            bits |= (code as u64) << bp;
            bp += nbits as u32;
        }
        let byte_count = ((bp + 7) / 8) as usize;
        let lzw_bytes: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i as u32 * 8)) & 0xFF) as u8)
            .collect();

        gif.push(lzw_bytes.len() as u8);
        gif.extend_from_slice(&lzw_bytes);
        gif.push(0); // terminator

        gif.push(0x3B); // trailer
        gif
    }

    #[test]
    fn decode_2x2_four_colors() {
        let data = build_2x2_gif();
        let img = decode_gif(&data).unwrap();
        assert_eq!(img.width, 2);
        assert_eq!(img.height, 2);
        assert_eq!(
            img.data,
            vec![
                255, 0, 0, 255, // red
                0, 255, 0, 255, // green
                0, 0, 255, 255, // blue
                255, 255, 0, 255, // yellow
            ]
        );
    }

    #[test]
    fn decode_frames_single() {
        let data = build_2x2_gif();
        let frames = decode_gif_frames(&data).unwrap();
        assert_eq!(frames.len(), 1);
        assert_eq!(frames[0].delay_cs, 0);
        assert_eq!(frames[0].disposal, DisposalMethod::None);
    }

    /// Build a GIF89a with transparency.
    fn build_transparent_gif() -> Vec<u8> {
        let mut gif = Vec::new();

        gif.extend_from_slice(b"GIF89a");

        // Screen: 2x1
        gif.push(2);
        gif.push(0);
        gif.push(1);
        gif.push(0);
        gif.push(0x80); // has GCT, size=0 (2 entries)
        gif.push(0);
        gif.push(0);

        // GCT: 2 entries
        gif.extend_from_slice(&[255, 0, 0]); // 0: red
        gif.extend_from_slice(&[0, 255, 0]); // 1: green

        // Graphic Control Extension
        gif.push(0x21); // extension introducer
        gif.push(0xF9); // GCE label
        gif.push(4); // block size
        gif.push(0x01); // packed: disposal=0, transparent=true
        gif.push(10);
        gif.push(0); // delay = 10cs
        gif.push(1); // transparent color index = 1
        gif.push(0); // block terminator

        // Image descriptor
        gif.push(0x2C);
        gif.extend_from_slice(&[0, 0, 0, 0]);
        gif.push(2);
        gif.push(0);
        gif.push(1);
        gif.push(0);
        gif.push(0);

        // LZW min code size = 2
        gif.push(2);

        // Encode: clear(4), 0, 1, eoi(5)
        let mut bits: u64 = 0;
        let mut bp = 0u32;
        for &(code, nbits) in &[(4u16, 3u8), (0, 3), (1, 3), (5, 3)] {
            bits |= (code as u64) << bp;
            bp += nbits as u32;
        }
        let byte_count = ((bp + 7) / 8) as usize;
        let lzw_bytes: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i as u32 * 8)) & 0xFF) as u8)
            .collect();

        gif.push(lzw_bytes.len() as u8);
        gif.extend_from_slice(&lzw_bytes);
        gif.push(0);

        gif.push(0x3B);
        gif
    }

    #[test]
    fn decode_with_transparency() {
        let data = build_transparent_gif();
        let img = decode_gif(&data).unwrap();
        assert_eq!(img.width, 2);
        assert_eq!(img.height, 1);
        // Pixel 0: index 0 = red (opaque)
        // Pixel 1: index 1 = transparent
        assert_eq!(
            img.data,
            vec![
                255, 0, 0, 255, // red, opaque
                0, 0, 0, 0, // transparent
            ]
        );
    }

    #[test]
    fn decode_transparency_delay() {
        let data = build_transparent_gif();
        let frames = decode_gif_frames(&data).unwrap();
        assert_eq!(frames.len(), 1);
        assert_eq!(frames[0].delay_cs, 10);
    }

    /// Build a 2-frame animated GIF.
    fn build_animated_gif() -> Vec<u8> {
        let mut gif = Vec::new();

        gif.extend_from_slice(b"GIF89a");

        // Screen: 2x1
        gif.push(2);
        gif.push(0);
        gif.push(1);
        gif.push(0);
        gif.push(0x80); // GCT, size=0 (2 entries)
        gif.push(0);
        gif.push(0);

        // GCT
        gif.extend_from_slice(&[255, 0, 0]); // 0: red
        gif.extend_from_slice(&[0, 0, 255]); // 1: blue

        // --- Frame 1 ---
        // GCE: disposal=none, delay=5
        gif.push(0x21);
        gif.push(0xF9);
        gif.push(4);
        gif.push(0x00); // disposal=0(none), no transparency
        gif.push(5);
        gif.push(0); // delay=5
        gif.push(0); // no transparent
        gif.push(0);

        // Image descriptor: full 2x1
        gif.push(0x2C);
        gif.extend_from_slice(&[0, 0, 0, 0]);
        gif.push(2);
        gif.push(0);
        gif.push(1);
        gif.push(0);
        gif.push(0);

        gif.push(2); // LZW min code size

        // Encode: clear(4), 0, 1, eoi(5)
        {
            let mut bits: u64 = 0;
            let mut bp = 0u32;
            for &(code, nbits) in &[(4u16, 3u8), (0, 3), (1, 3), (5, 3)] {
                bits |= (code as u64) << bp;
                bp += nbits as u32;
            }
            let byte_count = ((bp + 7) / 8) as usize;
            let lzw_bytes: Vec<u8> = (0..byte_count)
                .map(|i| ((bits >> (i as u32 * 8)) & 0xFF) as u8)
                .collect();
            gif.push(lzw_bytes.len() as u8);
            gif.extend_from_slice(&lzw_bytes);
            gif.push(0);
        }

        // --- Frame 2 ---
        // GCE: disposal=restore_bg, delay=10
        gif.push(0x21);
        gif.push(0xF9);
        gif.push(4);
        gif.push(0x08); // disposal=2(restore bg), no transparency
        gif.push(10);
        gif.push(0); // delay=10
        gif.push(0);
        gif.push(0);

        // Image descriptor: full 2x1
        gif.push(0x2C);
        gif.extend_from_slice(&[0, 0, 0, 0]);
        gif.push(2);
        gif.push(0);
        gif.push(1);
        gif.push(0);
        gif.push(0);

        gif.push(2);

        // Encode: clear(4), 1, 0, eoi(5)
        {
            let mut bits: u64 = 0;
            let mut bp = 0u32;
            for &(code, nbits) in &[(4u16, 3u8), (1, 3), (0, 3), (5, 3)] {
                bits |= (code as u64) << bp;
                bp += nbits as u32;
            }
            let byte_count = ((bp + 7) / 8) as usize;
            let lzw_bytes: Vec<u8> = (0..byte_count)
                .map(|i| ((bits >> (i as u32 * 8)) & 0xFF) as u8)
                .collect();
            gif.push(lzw_bytes.len() as u8);
            gif.extend_from_slice(&lzw_bytes);
            gif.push(0);
        }

        gif.push(0x3B);
        gif
    }

    #[test]
    fn decode_animated_two_frames() {
        let data = build_animated_gif();
        let frames = decode_gif_frames(&data).unwrap();
        assert_eq!(frames.len(), 2);

        // Frame 1: [red, blue]
        assert_eq!(frames[0].delay_cs, 5);
        assert_eq!(frames[0].disposal, DisposalMethod::None);
        assert_eq!(frames[0].image.data, vec![255, 0, 0, 255, 0, 0, 255, 255]);

        // Frame 2: [blue, red] (composited on canvas)
        assert_eq!(frames[1].delay_cs, 10);
        assert_eq!(frames[1].disposal, DisposalMethod::RestoreBackground);
        assert_eq!(frames[1].image.data, vec![0, 0, 255, 255, 255, 0, 0, 255]);
    }

    #[test]
    fn decode_animated_first_frame_only() {
        let data = build_animated_gif();
        let img = decode_gif(&data).unwrap();
        // decode_gif returns the first frame
        assert_eq!(img.data, vec![255, 0, 0, 255, 0, 0, 255, 255]);
    }

    /// Build a GIF with a local color table.
    fn build_local_ct_gif() -> Vec<u8> {
        let mut gif = Vec::new();

        gif.extend_from_slice(b"GIF87a");

        // Screen: 1x1, NO GCT
        gif.push(1);
        gif.push(0);
        gif.push(1);
        gif.push(0);
        gif.push(0x00); // no GCT
        gif.push(0);
        gif.push(0);

        // Image descriptor with LCT
        gif.push(0x2C);
        gif.extend_from_slice(&[0, 0, 0, 0]);
        gif.push(1);
        gif.push(0);
        gif.push(1);
        gif.push(0);
        gif.push(0x80); // has LCT, size=0 (2 entries)

        // LCT
        gif.extend_from_slice(&[0, 128, 255]); // 0: teal-ish
        gif.extend_from_slice(&[0, 0, 0]); // 1: black

        gif.push(2); // LZW min code size

        // Encode: clear(4), 0, eoi(5)
        let mut bits: u64 = 0;
        let mut bp = 0u32;
        for &(code, nbits) in &[(4u16, 3u8), (0, 3), (5, 3)] {
            bits |= (code as u64) << bp;
            bp += nbits as u32;
        }
        let byte_count = ((bp + 7) / 8) as usize;
        let lzw_bytes: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i as u32 * 8)) & 0xFF) as u8)
            .collect();
        gif.push(lzw_bytes.len() as u8);
        gif.extend_from_slice(&lzw_bytes);
        gif.push(0);

        gif.push(0x3B);
        gif
    }

    #[test]
    fn decode_local_color_table() {
        let data = build_local_ct_gif();
        let img = decode_gif(&data).unwrap();
        assert_eq!(img.width, 1);
        assert_eq!(img.height, 1);
        assert_eq!(img.data, vec![0, 128, 255, 255]);
    }

    // -----------------------------------------------------------------------
    // Error case tests
    // -----------------------------------------------------------------------

    #[test]
    fn invalid_signature() {
        let data = b"NOT_GIF";
        assert!(matches!(
            decode_gif(data),
            Err(ImageError::Decode(ref msg)) if msg.contains("invalid signature")
        ));
    }

    #[test]
    fn too_short() {
        let data = b"GIF8";
        assert!(matches!(decode_gif(data), Err(ImageError::Decode(_))));
    }

    #[test]
    fn no_frames() {
        let mut gif = Vec::new();
        gif.extend_from_slice(b"GIF87a");
        gif.push(1);
        gif.push(0);
        gif.push(1);
        gif.push(0);
        gif.push(0x00);
        gif.push(0);
        gif.push(0);
        gif.push(0x3B);
        assert!(matches!(
            decode_gif(&gif),
            Err(ImageError::Decode(ref msg)) if msg.contains("no frames")
        ));
    }

    #[test]
    fn zero_dimension_screen() {
        let mut gif = Vec::new();
        gif.extend_from_slice(b"GIF87a");
        gif.push(0);
        gif.push(0); // width=0
        gif.push(1);
        gif.push(0); // height=1
        gif.push(0x00);
        gif.push(0);
        gif.push(0);
        assert!(matches!(
            decode_gif(&gif),
            Err(ImageError::Decode(ref msg)) if msg.contains("zero dimension")
        ));
    }

    #[test]
    fn invalid_lzw_min_code_size() {
        let mut gif = Vec::new();
        gif.extend_from_slice(b"GIF87a");
        gif.push(1);
        gif.push(0);
        gif.push(1);
        gif.push(0);
        gif.push(0x80);
        gif.push(0);
        gif.push(0);
        gif.extend_from_slice(&[0; 6]); // GCT (2 entries)

        gif.push(0x2C); // image descriptor
        gif.extend_from_slice(&[0, 0, 0, 0, 1, 0, 1, 0, 0]);
        gif.push(12); // invalid LZW min code size (>11)

        assert!(matches!(
            decode_gif(&gif),
            Err(ImageError::Decode(ref msg)) if msg.contains("LZW minimum code size")
        ));
    }

    // -----------------------------------------------------------------------
    // Sub-frame positioning test
    // -----------------------------------------------------------------------

    /// Build a GIF where the frame is smaller than the logical screen.
    fn build_subframe_gif() -> Vec<u8> {
        let mut gif = Vec::new();

        gif.extend_from_slice(b"GIF89a");

        // Screen: 3x3
        gif.push(3);
        gif.push(0);
        gif.push(3);
        gif.push(0);
        gif.push(0x80); // GCT, size=0 (2 entries)
        gif.push(0);
        gif.push(0);

        // GCT
        gif.extend_from_slice(&[0, 0, 0]); // 0: black
        gif.extend_from_slice(&[255, 255, 255]); // 1: white

        // Image descriptor: 1x1 at position (1,1)
        gif.push(0x2C);
        gif.push(1);
        gif.push(0); // left=1
        gif.push(1);
        gif.push(0); // top=1
        gif.push(1);
        gif.push(0); // width=1
        gif.push(1);
        gif.push(0); // height=1
        gif.push(0);

        gif.push(2); // LZW min

        // Encode: clear(4), 1, eoi(5)
        let mut bits: u64 = 0;
        let mut bp = 0u32;
        for &(code, nbits) in &[(4u16, 3u8), (1, 3), (5, 3)] {
            bits |= (code as u64) << bp;
            bp += nbits as u32;
        }
        let byte_count = ((bp + 7) / 8) as usize;
        let lzw_bytes: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i as u32 * 8)) & 0xFF) as u8)
            .collect();
        gif.push(lzw_bytes.len() as u8);
        gif.extend_from_slice(&lzw_bytes);
        gif.push(0);

        gif.push(0x3B);
        gif
    }

    #[test]
    fn decode_subframe_positioning() {
        let data = build_subframe_gif();
        let img = decode_gif(&data).unwrap();
        assert_eq!(img.width, 3);
        assert_eq!(img.height, 3);
        // Canvas starts all black (0,0,0,0 = transparent)
        // The 1x1 white pixel is composited at position (1,1)
        let pixel = |x: usize, y: usize| -> &[u8] {
            let off = (y * 3 + x) * 4;
            &img.data[off..off + 4]
        };
        // All pixels except (1,1) should be transparent black
        assert_eq!(pixel(0, 0), &[0, 0, 0, 0]);
        assert_eq!(pixel(1, 0), &[0, 0, 0, 0]);
        assert_eq!(pixel(2, 0), &[0, 0, 0, 0]);
        assert_eq!(pixel(0, 1), &[0, 0, 0, 0]);
        assert_eq!(pixel(1, 1), &[255, 255, 255, 255]); // white
        assert_eq!(pixel(2, 1), &[0, 0, 0, 0]);
        assert_eq!(pixel(0, 2), &[0, 0, 0, 0]);
        assert_eq!(pixel(1, 2), &[0, 0, 0, 0]);
        assert_eq!(pixel(2, 2), &[0, 0, 0, 0]);
    }

    // -----------------------------------------------------------------------
    // Application extension skip test
    // -----------------------------------------------------------------------

    #[test]
    fn skip_application_extension() {
        let mut gif = Vec::new();

        gif.extend_from_slice(b"GIF89a");
        gif.push(1);
        gif.push(0);
        gif.push(1);
        gif.push(0);
        gif.push(0x80);
        gif.push(0);
        gif.push(0);
        gif.extend_from_slice(&[255, 0, 0, 0, 0, 0]); // GCT

        // Application extension (NETSCAPE2.0 for looping)
        gif.push(0x21);
        gif.push(0xFF);
        // Sub-blocks for the extension
        gif.push(11); // sub-block size
        gif.extend_from_slice(b"NETSCAPE2.0");
        gif.push(3); // sub-block size
        gif.push(1); // sub-block id
        gif.push(0);
        gif.push(0); // loop count
        gif.push(0); // terminator

        // Image
        gif.push(0x2C);
        gif.extend_from_slice(&[0, 0, 0, 0, 1, 0, 1, 0, 0]);
        gif.push(2);

        let mut bits: u64 = 0;
        let mut bp = 0u32;
        for &(code, nbits) in &[(4u16, 3u8), (0, 3), (5, 3)] {
            bits |= (code as u64) << bp;
            bp += nbits as u32;
        }
        let byte_count = ((bp + 7) / 8) as usize;
        let lzw_bytes: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i as u32 * 8)) & 0xFF) as u8)
            .collect();
        gif.push(lzw_bytes.len() as u8);
        gif.extend_from_slice(&lzw_bytes);
        gif.push(0);

        gif.push(0x3B);

        let img = decode_gif(&gif).unwrap();
        assert_eq!(img.width, 1);
        assert_eq!(img.height, 1);
        assert_eq!(img.data, vec![255, 0, 0, 255]);
    }

    // -----------------------------------------------------------------------
    // Comment extension skip test
    // -----------------------------------------------------------------------

    #[test]
    fn skip_comment_extension() {
        let mut gif = Vec::new();

        gif.extend_from_slice(b"GIF89a");
        gif.push(1);
        gif.push(0);
        gif.push(1);
        gif.push(0);
        gif.push(0x80);
        gif.push(0);
        gif.push(0);
        gif.extend_from_slice(&[0, 255, 0, 0, 0, 0]); // GCT

        // Comment extension
        gif.push(0x21);
        gif.push(0xFE);
        gif.push(5);
        gif.extend_from_slice(b"hello");
        gif.push(0);

        // Image
        gif.push(0x2C);
        gif.extend_from_slice(&[0, 0, 0, 0, 1, 0, 1, 0, 0]);
        gif.push(2);

        let mut bits: u64 = 0;
        let mut bp = 0u32;
        for &(code, nbits) in &[(4u16, 3u8), (0, 3), (5, 3)] {
            bits |= (code as u64) << bp;
            bp += nbits as u32;
        }
        let byte_count = ((bp + 7) / 8) as usize;
        let lzw_bytes: Vec<u8> = (0..byte_count)
            .map(|i| ((bits >> (i as u32 * 8)) & 0xFF) as u8)
            .collect();
        gif.push(lzw_bytes.len() as u8);
        gif.extend_from_slice(&lzw_bytes);
        gif.push(0);

        gif.push(0x3B);

        let img = decode_gif(&gif).unwrap();
        assert_eq!(img.data, vec![0, 255, 0, 255]);
    }

    // -----------------------------------------------------------------------
    // GIF87a compatibility test
    // -----------------------------------------------------------------------

    #[test]
    fn gif87a_is_accepted() {
        let data = build_1x1_red_gif();
        // Already uses GIF87a
        assert!(data.starts_with(b"GIF87a"));
        let img = decode_gif(&data).unwrap();
        assert_eq!(img.data, vec![255, 0, 0, 255]);
    }

    // -----------------------------------------------------------------------
    // Bit reader tests
    // -----------------------------------------------------------------------

    #[test]
    fn bit_reader_basic() {
        // Byte 0: 0b10110100 — bits[0..8] = 0,0,1,0,1,1,0,1
        // Byte 1: 0b00000001 — bits[8..16] = 1,0,0,0,0,0,0,0
        let data = [0b10110100u8, 0b00000001];
        let mut reader = LzwBitReader::new(&data);

        // Read 3 bits [0,1,2]: 0*1+0*2+1*4 = 4
        assert_eq!(reader.read_bits(3).unwrap(), 4);
        // Read 3 bits [3,4,5]: 0*1+1*2+1*4 = 6
        assert_eq!(reader.read_bits(3).unwrap(), 6);
        // Read 3 bits [6,7,8]: 0*1+1*2+1*4 = 6
        assert_eq!(reader.read_bits(3).unwrap(), 6);
    }

    #[test]
    fn bit_reader_eof() {
        let data = [0xFF];
        let mut reader = LzwBitReader::new(&data);
        assert!(reader.read_bits(8).is_ok());
        assert!(reader.read_bits(1).is_err());
    }
}