rfb_encodings/

tight.rs

// Copyright 2025 Dustin McAfee
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

//! VNC Tight encoding implementation - RFC 6143 compliant with full optimization
//!
//! # Architecture
//!
//! This implementation has TWO layers for optimal compression:
//!
//! ## Layer 1: High-Level Optimization
//! - Rectangle splitting and subdivision
//! - Solid area detection and extraction
//! - Recursive optimization for best encoding
//! - Size limit enforcement (`TIGHT_MAX_RECT_SIZE`, `TIGHT_MAX_RECT_WIDTH`)
//!
//! ## Layer 2: Low-Level Encoding
//! - Palette analysis
//! - Encoding mode selection (solid/mono/indexed/full-color/JPEG)
//! - Compression and wire format generation
//!
//! # Protocol Overview
//!
//! Tight encoding supports 5 compression modes:
//!
//! 1. **Solid fill** (1 color) - control byte 0x80
//!    - Wire format: `[0x80][R][G][B]` (4 bytes total)
//!    - Most efficient for solid color rectangles
//!
//! 2. **Mono rect** (2 colors) - control byte 0x50 or 0xA0
//!    - Wire format: `[control][0x01][1][bg RGB24][fg RGB24][length][bitmap]`
//!    - Uses 1-bit bitmap: 0=background, 1=foreground
//!    - MSB first, each row byte-aligned
//!
//! 3. **Indexed palette** (3-16 colors) - control byte 0x60 or 0xA0
//!    - Wire format: `[control][0x01][n-1][colors...][length][indices]`
//!    - Each pixel encoded as palette index (1 byte)
//!
//! 4. **Full-color zlib** - control byte 0x00 or 0xA0
//!    - Wire format: `[control][length][zlib compressed RGB24]`
//!    - Lossless compression for truecolor images
//!
//! 5. **JPEG** - control byte 0x90
//!    - Wire format: `[0x90][length][JPEG data]`
//!    - Lossy compression for photographic content
//!
//! # Configuration Constants
//!
//! ```text
//! TIGHT_MIN_TO_COMPRESS = 12      (data < 12 bytes sent raw)
//! MIN_SPLIT_RECT_SIZE = 4096      (split rectangles >= 4096 pixels)
//! MIN_SOLID_SUBRECT_SIZE = 2048   (solid areas must be >= 2048 pixels)
//! MAX_SPLIT_TILE_SIZE = 16        (tile size for solid detection)
//! TIGHT_MAX_RECT_SIZE = 65536     (max pixels per rectangle)
//! TIGHT_MAX_RECT_WIDTH = 2048     (max rectangle width)
//! ```

use super::common::translate_pixel_to_client_format;
use crate::{Encoding, PixelFormat};
use bytes::{BufMut, BytesMut};
use std::collections::HashMap;

// Tight encoding protocol constants (RFC 6143 section 7.7.4)
const TIGHT_EXPLICIT_FILTER: u8 = 0x04;
const TIGHT_FILL: u8 = 0x08;
#[allow(dead_code)]
const TIGHT_JPEG: u8 = 0x09;
const TIGHT_NO_ZLIB: u8 = 0x0A;

// Filter types
const TIGHT_FILTER_PALETTE: u8 = 0x01;

/// Zlib stream ID for full-color data (RFC 6143 section 7.7.4)
pub const STREAM_ID_FULL_COLOR: u8 = 0;
/// Zlib stream ID for monochrome bitmap data (RFC 6143 section 7.7.4)
pub const STREAM_ID_MONO: u8 = 1;
/// Zlib stream ID for indexed palette data (RFC 6143 section 7.7.4)
pub const STREAM_ID_INDEXED: u8 = 2;

// Compression thresholds for Tight encoding optimization
const TIGHT_MIN_TO_COMPRESS: usize = 12;
const MIN_SPLIT_RECT_SIZE: usize = 4096;
const MIN_SOLID_SUBRECT_SIZE: usize = 2048;
const MAX_SPLIT_TILE_SIZE: u16 = 16;
const TIGHT_MAX_RECT_SIZE: usize = 65536;
const TIGHT_MAX_RECT_WIDTH: u16 = 2048;

/// Compression configuration for different quality levels
struct TightConf {
    mono_min_rect_size: usize,
    idx_zlib_level: u8,
    mono_zlib_level: u8,
    raw_zlib_level: u8,
}

const TIGHT_CONF: [TightConf; 4] = [
    TightConf {
        mono_min_rect_size: 6,
        idx_zlib_level: 0,
        mono_zlib_level: 0,
        raw_zlib_level: 0,
    }, // Level 0
    TightConf {
        mono_min_rect_size: 32,
        idx_zlib_level: 1,
        mono_zlib_level: 1,
        raw_zlib_level: 1,
    }, // Level 1
    TightConf {
        mono_min_rect_size: 32,
        idx_zlib_level: 3,
        mono_zlib_level: 3,
        raw_zlib_level: 2,
    }, // Level 2
    TightConf {
        mono_min_rect_size: 32,
        idx_zlib_level: 7,
        mono_zlib_level: 7,
        raw_zlib_level: 5,
    }, // Level 9
];

/// Rectangle to encode
#[derive(Debug, Clone)]
struct Rect {
    x: u16,
    y: u16,
    w: u16,
    h: u16,
}

/// Result of encoding a rectangle
struct EncodeResult {
    rectangles: Vec<(Rect, BytesMut)>,
}

/// Implements the VNC "Tight" encoding (RFC 6143 section 7.7.4).
pub struct TightEncoding;

impl Encoding for TightEncoding {
    fn encode(
        &self,
        data: &[u8],
        width: u16,
        height: u16,
        quality: u8,
        compression: u8,
    ) -> BytesMut {
        // Simple wrapper - for full optimization, use encode_rect_optimized
        // Default to RGBA32 format for backward compatibility (old API doesn't have client format)
        // Create a temporary compressor for this call (old API doesn't have persistent streams)
        let mut compressor = SimpleTightCompressor::new(compression);

        let rect = Rect {
            x: 0,
            y: 0,
            w: width,
            h: height,
        };
        let default_format = PixelFormat::rgba32();
        let result = encode_rect_optimized(
            data,
            width,
            &rect,
            quality,
            compression,
            &default_format,
            &mut compressor,
        );

        // Concatenate all rectangles
        let mut output = BytesMut::new();
        for (_rect, buf) in result.rectangles {
            output.extend_from_slice(&buf);
        }
        output
    }
}

/// High-level optimization: split rectangles and find solid areas
/// Implements Tight encoding optimization as specified in RFC 6143
#[allow(clippy::similar_names)] // dx_end and dy_end are clear in context (delta x/y end coordinates)
#[allow(clippy::too_many_lines)] // Complex algorithm implementing RFC 6143 Tight encoding optimization
#[allow(clippy::cast_possible_truncation)] // Rectangle dimensions limited to u16 per VNC protocol
fn encode_rect_optimized<C: TightStreamCompressor>(
    framebuffer: &[u8],
    fb_width: u16,
    rect: &Rect,
    quality: u8,
    compression: u8,
    client_format: &PixelFormat,
    compressor: &mut C,
) -> EncodeResult {
    #[cfg(feature = "debug-logging")]
    log::info!("DEBUG: encode_rect_optimized called: rect={}x{} at ({}, {}), quality={}, compression={}, bpp={}",
        rect.w, rect.h, rect.x, rect.y, quality, compression, client_format.bits_per_pixel);

    let mut rectangles = Vec::new();

    // Normalize compression level based on quality settings
    let compression = normalize_compression_level(compression, quality);

    #[cfg(feature = "debug-logging")]
    log::info!("DEBUG: normalized compression={compression}");

    // Check if optimization should be applied
    let rect_size = rect.w as usize * rect.h as usize;

    #[cfg(feature = "debug-logging")]
    log::info!("DEBUG: rect_size={rect_size}, MIN_SPLIT_RECT_SIZE={MIN_SPLIT_RECT_SIZE}");

    if rect_size < MIN_SPLIT_RECT_SIZE {
        #[cfg(feature = "debug-logging")]
        log::info!("DEBUG: Rectangle too small for optimization");

        // Too small for optimization - but still check if it needs splitting due to size limits
        if rect.w > TIGHT_MAX_RECT_WIDTH
            || ((rect.w as usize) * (rect.h as usize)) > TIGHT_MAX_RECT_SIZE
        {
            #[cfg(feature = "debug-logging")]
            log::info!("DEBUG: But rectangle needs splitting - calling encode_large_rect");

            // Too large - split it
            rectangles.extend(encode_large_rect(
                framebuffer,
                fb_width,
                rect,
                quality,
                compression,
                client_format,
                compressor,
            ));
        } else {
            #[cfg(feature = "debug-logging")]
            log::info!("DEBUG: Rectangle small enough - encode directly");

            // Small enough - encode directly
            let buf = encode_subrect_single(
                framebuffer,
                fb_width,
                rect,
                quality,
                compression,
                client_format,
                compressor,
            );
            rectangles.push((rect.clone(), buf));
        }

        #[cfg(feature = "debug-logging")]
        log::info!(
            "DEBUG: encode_rect_optimized returning {} rectangles (early return)",
            rectangles.len()
        );

        return EncodeResult { rectangles };
    }

    #[cfg(feature = "debug-logging")]
    log::info!("DEBUG: Rectangle large enough for optimization - continuing");

    // Calculate maximum rows per rectangle
    let n_max_width = rect.w.min(TIGHT_MAX_RECT_WIDTH);
    let n_max_rows = (TIGHT_MAX_RECT_SIZE / n_max_width as usize) as u16;

    // Try to find large solid-color areas for optimization
    // Track the current scan position and base position (like C code's y and h)
    let mut current_y = rect.y;
    let mut base_y = rect.y; // Corresponds to C code's 'y' variable
    let mut remaining_h = rect.h; // Corresponds to C code's 'h' variable

    #[cfg(feature = "debug-logging")]
    log::info!(
        "DEBUG: Starting optimization loop, rect.y={}, rect.h={}",
        rect.y,
        rect.h
    );

    while current_y < base_y + remaining_h {
        #[cfg(feature = "debug-logging")]
        log::info!("DEBUG: Loop iteration: current_y={current_y}, base_y={base_y}, remaining_h={remaining_h}");
        // Check if rectangle becomes too large (like C code: if (dy - y >= nMaxRows))
        if (current_y - base_y) >= n_max_rows {
            let chunk_rect = Rect {
                x: rect.x,
                y: base_y, // Send from base_y, not from calculated position
                w: rect.w,
                h: n_max_rows,
            };
            // Chunk might still be too wide - check and split if needed
            if chunk_rect.w > TIGHT_MAX_RECT_WIDTH {
                rectangles.extend(encode_large_rect(
                    framebuffer,
                    fb_width,
                    &chunk_rect,
                    quality,
                    compression,
                    client_format,
                    compressor,
                ));
            } else {
                let buf = encode_subrect_single(
                    framebuffer,
                    fb_width,
                    &chunk_rect,
                    quality,
                    compression,
                    client_format,
                    compressor,
                );
                rectangles.push((chunk_rect, buf));
            }
            // Like C code: y += nMaxRows; h -= nMaxRows;
            base_y += n_max_rows;
            remaining_h -= n_max_rows;
        }

        let dy_end = (current_y + MAX_SPLIT_TILE_SIZE).min(base_y + remaining_h);
        let dh = dy_end - current_y;

        // Safety check: if dh is 0, we've reached the end
        if dh == 0 {
            break;
        }

        let mut current_x = rect.x;
        while current_x < rect.x + rect.w {
            let dx_end = (current_x + MAX_SPLIT_TILE_SIZE).min(rect.x + rect.w);
            let dw = dx_end - current_x;

            // Safety check: if dw is 0, we've reached the end
            if dw == 0 {
                break;
            }

            // Check if tile is solid
            if let Some(color_value) =
                check_solid_tile(framebuffer, fb_width, current_x, current_y, dw, dh, None)
            {
                // Find best solid area
                let (w_best, h_best) = find_best_solid_area(
                    framebuffer,
                    fb_width,
                    current_x,
                    current_y,
                    rect.w - (current_x - rect.x),
                    remaining_h - (current_y - base_y),
                    color_value,
                );

                // Check if solid area is large enough
                if w_best * h_best != rect.w * remaining_h
                    && (w_best as usize * h_best as usize) < MIN_SOLID_SUBRECT_SIZE
                {
                    current_x += dw;
                    continue;
                }

                // Extend solid area (use base_y instead of rect.y for coordinates)
                let (x_best, y_best, w_best, h_best) = extend_solid_area(
                    framebuffer,
                    fb_width,
                    rect.x,
                    base_y,
                    rect.w,
                    remaining_h,
                    color_value,
                    current_x,
                    current_y,
                    w_best,
                    h_best,
                );

                // Send rectangles before solid area
                if y_best != base_y {
                    let top_rect = Rect {
                        x: rect.x,
                        y: base_y,
                        w: rect.w,
                        h: y_best - base_y,
                    };
                    // top_rect might be too wide - check and split if needed
                    if top_rect.w > TIGHT_MAX_RECT_WIDTH
                        || ((top_rect.w as usize) * (top_rect.h as usize)) > TIGHT_MAX_RECT_SIZE
                    {
                        rectangles.extend(encode_large_rect(
                            framebuffer,
                            fb_width,
                            &top_rect,
                            quality,
                            compression,
                            client_format,
                            compressor,
                        ));
                    } else {
                        let buf = encode_subrect_single(
                            framebuffer,
                            fb_width,
                            &top_rect,
                            quality,
                            compression,
                            client_format,
                            compressor,
                        );
                        rectangles.push((top_rect, buf));
                    }
                }

                if x_best != rect.x {
                    let left_rect = Rect {
                        x: rect.x,
                        y: y_best,
                        w: x_best - rect.x,
                        h: h_best,
                    };
                    // Don't recursively optimize - just check size and encode
                    if left_rect.w > TIGHT_MAX_RECT_WIDTH
                        || ((left_rect.w as usize) * (left_rect.h as usize)) > TIGHT_MAX_RECT_SIZE
                    {
                        rectangles.extend(encode_large_rect(
                            framebuffer,
                            fb_width,
                            &left_rect,
                            quality,
                            compression,
                            client_format,
                            compressor,
                        ));
                    } else {
                        let buf = encode_subrect_single(
                            framebuffer,
                            fb_width,
                            &left_rect,
                            quality,
                            compression,
                            client_format,
                            compressor,
                        );
                        rectangles.push((left_rect, buf));
                    }
                }

                // Send solid rectangle
                let solid_rect = Rect {
                    x: x_best,
                    y: y_best,
                    w: w_best,
                    h: h_best,
                };
                let buf = encode_solid_rect(color_value, client_format);
                rectangles.push((solid_rect, buf));

                // Send remaining rectangles
                if x_best + w_best != rect.x + rect.w {
                    let right_rect = Rect {
                        x: x_best + w_best,
                        y: y_best,
                        w: rect.w - (x_best - rect.x) - w_best,
                        h: h_best,
                    };
                    // Don't recursively optimize - just check size and encode
                    if right_rect.w > TIGHT_MAX_RECT_WIDTH
                        || ((right_rect.w as usize) * (right_rect.h as usize)) > TIGHT_MAX_RECT_SIZE
                    {
                        rectangles.extend(encode_large_rect(
                            framebuffer,
                            fb_width,
                            &right_rect,
                            quality,
                            compression,
                            client_format,
                            compressor,
                        ));
                    } else {
                        let buf = encode_subrect_single(
                            framebuffer,
                            fb_width,
                            &right_rect,
                            quality,
                            compression,
                            client_format,
                            compressor,
                        );
                        rectangles.push((right_rect, buf));
                    }
                }

                if y_best + h_best != base_y + remaining_h {
                    let bottom_rect = Rect {
                        x: rect.x,
                        y: y_best + h_best,
                        w: rect.w,
                        h: remaining_h - (y_best - base_y) - h_best,
                    };
                    // Don't recursively optimize - just check size and encode
                    if bottom_rect.w > TIGHT_MAX_RECT_WIDTH
                        || ((bottom_rect.w as usize) * (bottom_rect.h as usize))
                            > TIGHT_MAX_RECT_SIZE
                    {
                        rectangles.extend(encode_large_rect(
                            framebuffer,
                            fb_width,
                            &bottom_rect,
                            quality,
                            compression,
                            client_format,
                            compressor,
                        ));
                    } else {
                        let buf = encode_subrect_single(
                            framebuffer,
                            fb_width,
                            &bottom_rect,
                            quality,
                            compression,
                            client_format,
                            compressor,
                        );
                        rectangles.push((bottom_rect, buf));
                    }
                }

                return EncodeResult { rectangles };
            }

            current_x += dw;
        }

        #[cfg(feature = "debug-logging")]
        log::info!("DEBUG: End of inner loop, incrementing current_y by dh={dh}");

        current_y += dh;

        #[cfg(feature = "debug-logging")]
        log::info!("DEBUG: After increment: current_y={current_y}");
    }

    #[cfg(feature = "debug-logging")]
    log::info!("DEBUG: Exited optimization loop, no solid areas found");

    // No solid areas found - encode normally (but check if it needs splitting)
    if rect.w > TIGHT_MAX_RECT_WIDTH
        || ((rect.w as usize) * (rect.h as usize)) > TIGHT_MAX_RECT_SIZE
    {
        #[cfg(feature = "debug-logging")]
        log::info!("DEBUG: Rectangle needs splitting, calling encode_large_rect");

        rectangles.extend(encode_large_rect(
            framebuffer,
            fb_width,
            rect,
            quality,
            compression,
            client_format,
            compressor,
        ));
    } else {
        #[cfg(feature = "debug-logging")]
        log::info!("DEBUG: Rectangle small enough, encoding directly");

        let buf = encode_subrect_single(
            framebuffer,
            fb_width,
            rect,
            quality,
            compression,
            client_format,
            compressor,
        );
        rectangles.push((rect.clone(), buf));
    }

    #[cfg(feature = "debug-logging")]
    log::info!(
        "DEBUG: encode_rect_optimized returning {} rectangles (normal return)",
        rectangles.len()
    );

    EncodeResult { rectangles }
}

/// Normalize compression level based on JPEG quality
/// Maps compression level 0-9 to internal configuration indices
fn normalize_compression_level(compression: u8, quality: u8) -> u8 {
    let mut level = compression;

    // JPEG enabled (quality < 10): enforce minimum level 1, maximum level 2
    // This ensures better compression performance with JPEG
    if quality < 10 {
        level = level.clamp(1, 2);
    }
    // JPEG disabled (quality >= 10): cap at level 1
    else if level > 1 {
        level = 1;
    }

    // Map level 9 to 3 for backward compatibility (low-bandwidth mode)
    if level == 9 {
        level = 3;
    }

    level
}

/// Low-level encoding: analyze and encode a single subrectangle
/// Analyzes palette and selects optimal encoding mode
/// Never splits - assumes rectangle is within size limits
fn encode_subrect_single<C: TightStreamCompressor>(
    framebuffer: &[u8],
    fb_width: u16,
    rect: &Rect,
    quality: u8,
    compression: u8,
    client_format: &PixelFormat,
    compressor: &mut C,
) -> BytesMut {
    // This function assumes rect is within size limits (called from encode_large_rect or for small rects)

    // Extract pixel data for this rectangle
    let pixels = extract_rect_rgba(framebuffer, fb_width, rect);

    // Analyze palette
    let palette = analyze_palette(&pixels, rect.w as usize * rect.h as usize, compression);

    // Route to appropriate encoder based on palette
    match palette.num_colors {
        0 => {
            // Truecolor - use JPEG or full-color
            if quality < 10 {
                // Convert VNC quality (0-9, lower is better) to JPEG quality (0-100, higher is better)
                let jpeg_quality = 95_u8.saturating_sub(quality * 7);
                encode_jpeg_rect(&pixels, rect.w, rect.h, jpeg_quality, compressor)
            } else {
                encode_full_color_rect(&pixels, rect.w, rect.h, compression, compressor)
            }
        }
        1 => {
            // Solid color
            encode_solid_rect(palette.colors[0], client_format)
        }
        2 => {
            // Mono rect (2 colors)
            encode_mono_rect(
                &pixels,
                rect.w,
                rect.h,
                palette.colors[0],
                palette.colors[1],
                compression,
                client_format,
                compressor,
            )
        }
        _ => {
            // Indexed palette (3-16 colors)
            encode_indexed_rect(
                &pixels,
                rect.w,
                rect.h,
                &palette.colors[..palette.num_colors],
                compression,
                client_format,
                compressor,
            )
        }
    }
}

/// Encode large rectangle by splitting it into smaller tiles
/// Returns a vector of individual rectangles with their encoded data
#[allow(clippy::cast_possible_truncation)] // Tight max rect size divided by width always fits in u16
fn encode_large_rect<C: TightStreamCompressor>(
    framebuffer: &[u8],
    fb_width: u16,
    rect: &Rect,
    quality: u8,
    compression: u8,
    client_format: &PixelFormat,
    compressor: &mut C,
) -> Vec<(Rect, BytesMut)> {
    let subrect_max_width = rect.w.min(TIGHT_MAX_RECT_WIDTH);
    let subrect_max_height = (TIGHT_MAX_RECT_SIZE / subrect_max_width as usize) as u16;

    let mut rectangles = Vec::new();

    let mut dy = 0;
    while dy < rect.h {
        let mut dx = 0;
        while dx < rect.w {
            let rw = (rect.w - dx).min(TIGHT_MAX_RECT_WIDTH);
            let rh = (rect.h - dy).min(subrect_max_height);

            let sub_rect = Rect {
                x: rect.x + dx,
                y: rect.y + dy,
                w: rw,
                h: rh,
            };

            // Encode this sub-rectangle (recursive call, but sub_rect is guaranteed to be small enough)
            let buf = encode_subrect_single(
                framebuffer,
                fb_width,
                &sub_rect,
                quality,
                compression,
                client_format,
                compressor,
            );
            rectangles.push((sub_rect, buf));

            dx += TIGHT_MAX_RECT_WIDTH;
        }
        dy += subrect_max_height;
    }

    rectangles
}

/// Check if a tile is all the same color
/// Used for solid area detection optimization
fn check_solid_tile(
    framebuffer: &[u8],
    fb_width: u16,
    x: u16,
    y: u16,
    w: u16,
    h: u16,
    need_same_color: Option<u32>,
) -> Option<u32> {
    let offset = (y as usize * fb_width as usize + x as usize) * 4;

    // Get first pixel color (RGB24)
    let fb_r = framebuffer[offset];
    let fb_g = framebuffer[offset + 1];
    let fb_b = framebuffer[offset + 2];
    let first_color = rgba_to_rgb24(fb_r, fb_g, fb_b);

    #[cfg(feature = "debug-logging")]
    if x == 0 && y == 0 {
        // Log first pixel of each solid tile
        log::info!("check_solid_tile: fb[{}]=[{:02x},{:02x},{:02x},{:02x}] -> R={:02x} G={:02x} B={:02x} color=0x{:06x}",
            offset, framebuffer[offset], framebuffer[offset+1], framebuffer[offset+2], framebuffer[offset+3],
            fb_r, fb_g, fb_b, first_color);
    }

    // Check if we need a specific color
    if let Some(required) = need_same_color {
        if first_color != required {
            return None;
        }
    }

    // Check all pixels
    for dy in 0..h {
        let row_offset = ((y + dy) as usize * fb_width as usize + x as usize) * 4;
        for dx in 0..w {
            let pix_offset = row_offset + dx as usize * 4;
            let color = rgba_to_rgb24(
                framebuffer[pix_offset],
                framebuffer[pix_offset + 1],
                framebuffer[pix_offset + 2],
            );
            if color != first_color {
                return None;
            }
        }
    }

    Some(first_color)
}

/// Find best solid area dimensions
/// Determines optimal size for solid color subrectangle
fn find_best_solid_area(
    framebuffer: &[u8],
    fb_width: u16,
    x: u16,
    y: u16,
    w: u16,
    h: u16,
    color_value: u32,
) -> (u16, u16) {
    let mut w_best = 0;
    let mut h_best = 0;
    let mut w_prev = w;

    let mut dy = 0;
    while dy < h {
        let dh = (h - dy).min(MAX_SPLIT_TILE_SIZE);
        let dw = w_prev.min(MAX_SPLIT_TILE_SIZE);

        if check_solid_tile(framebuffer, fb_width, x, y + dy, dw, dh, Some(color_value)).is_none() {
            break;
        }

        let mut dx = dw;
        while dx < w_prev {
            let dw_check = (w_prev - dx).min(MAX_SPLIT_TILE_SIZE);
            if check_solid_tile(
                framebuffer,
                fb_width,
                x + dx,
                y + dy,
                dw_check,
                dh,
                Some(color_value),
            )
            .is_none()
            {
                break;
            }
            dx += dw_check;
        }

        w_prev = dx;
        if (w_prev as usize * (dy + dh) as usize) > (w_best as usize * h_best as usize) {
            w_best = w_prev;
            h_best = dy + dh;
        }

        dy += dh;
    }

    (w_best, h_best)
}

/// Extend solid area to maximum size
/// Expands solid region in all directions
#[allow(clippy::too_many_arguments)] // Tight encoding algorithm requires all geometric parameters for region expansion
fn extend_solid_area(
    framebuffer: &[u8],
    fb_width: u16,
    base_x: u16,
    base_y: u16,
    max_w: u16,
    max_h: u16,
    color_value: u32,
    mut x: u16,
    mut y: u16,
    mut w: u16,
    mut h: u16,
) -> (u16, u16, u16, u16) {
    // Extend upwards
    while y > base_y {
        if check_solid_tile(framebuffer, fb_width, x, y - 1, w, 1, Some(color_value)).is_none() {
            break;
        }
        y -= 1;
        h += 1;
    }

    // Extend downwards
    while y + h < base_y + max_h {
        if check_solid_tile(framebuffer, fb_width, x, y + h, w, 1, Some(color_value)).is_none() {
            break;
        }
        h += 1;
    }

    // Extend left
    while x > base_x {
        if check_solid_tile(framebuffer, fb_width, x - 1, y, 1, h, Some(color_value)).is_none() {
            break;
        }
        x -= 1;
        w += 1;
    }

    // Extend right
    while x + w < base_x + max_w {
        if check_solid_tile(framebuffer, fb_width, x + w, y, 1, h, Some(color_value)).is_none() {
            break;
        }
        w += 1;
    }

    (x, y, w, h)
}

/// Palette analysis result
struct Palette {
    num_colors: usize,
    colors: [u32; 256],
    mono_background: u32,
    mono_foreground: u32,
}

/// Analyze palette from pixel data
/// Determines color count and encoding mode selection
fn analyze_palette(pixels: &[u8], pixel_count: usize, compression: u8) -> Palette {
    let conf_idx = match compression {
        0 => 0,
        1 => 1,
        2 | 3 => 2,
        _ => 3,
    };
    let conf = &TIGHT_CONF[conf_idx];

    let mut palette = Palette {
        num_colors: 0,
        colors: [0; 256],
        mono_background: 0,
        mono_foreground: 0,
    };

    if pixel_count == 0 {
        return palette;
    }

    // Get first color
    let c0 = rgba_to_rgb24(pixels[0], pixels[1], pixels[2]);

    // Count how many pixels match first color
    let mut i = 4;
    while i < pixels.len() && rgba_to_rgb24(pixels[i], pixels[i + 1], pixels[i + 2]) == c0 {
        i += 4;
    }

    if i >= pixels.len() {
        // Solid color
        palette.num_colors = 1;
        palette.colors[0] = c0;
        return palette;
    }

    // Check for 2-color (mono) case
    if pixel_count >= conf.mono_min_rect_size {
        let n0 = i / 4;
        let c1 = rgba_to_rgb24(pixels[i], pixels[i + 1], pixels[i + 2]);
        let mut n1 = 0;

        i += 4;
        while i < pixels.len() {
            let color = rgba_to_rgb24(pixels[i], pixels[i + 1], pixels[i + 2]);
            if color == c0 {
                // n0 already counted
            } else if color == c1 {
                n1 += 1;
            } else {
                break;
            }
            i += 4;
        }

        if i >= pixels.len() {
            // Only 2 colors found
            palette.num_colors = 2;
            if n0 > n1 {
                palette.mono_background = c0;
                palette.mono_foreground = c1;
                palette.colors[0] = c0;
                palette.colors[1] = c1;
            } else {
                palette.mono_background = c1;
                palette.mono_foreground = c0;
                palette.colors[0] = c1;
                palette.colors[1] = c0;
            }
            return palette;
        }
    }

    // More than 2 colors - full palette or truecolor
    palette.num_colors = 0;
    palette
}

/// Extract RGBA rectangle from framebuffer
fn extract_rect_rgba(framebuffer: &[u8], fb_width: u16, rect: &Rect) -> Vec<u8> {
    let mut pixels = Vec::with_capacity(rect.w as usize * rect.h as usize * 4);

    for y in 0..rect.h {
        let row_offset = ((rect.y + y) as usize * fb_width as usize + rect.x as usize) * 4;
        let row_end = row_offset + rect.w as usize * 4;
        pixels.extend_from_slice(&framebuffer[row_offset..row_end]);
    }

    pixels
}

/// Convert RGBA to RGB24
/// Matches the format used in `common::rgba_to_rgb24_pixels`
/// Internal format: 0x00BBGGRR (R at bits 0-7, G at 8-15, B at 16-23)
#[inline]
fn rgba_to_rgb24(r: u8, g: u8, b: u8) -> u32 {
    u32::from(r) | (u32::from(g) << 8) | (u32::from(b) << 16)
}

/// Encode solid rectangle
/// Implements solid fill encoding mode (1 color)
/// Uses client's pixel format for color encoding
fn encode_solid_rect(color: u32, client_format: &PixelFormat) -> BytesMut {
    let mut buf = BytesMut::with_capacity(16); // Reserve enough for largest pixel format
    buf.put_u8(TIGHT_FILL << 4); // 0x80

    // Translate color to client's pixel format
    let color_bytes = translate_pixel_to_client_format(color, client_format);

    #[cfg(feature = "debug-logging")]
    {
        let use_24bit = client_format.depth == 24
            && client_format.red_max == 255
            && client_format.green_max == 255
            && client_format.blue_max == 255;
        #[cfg(feature = "debug-logging")]
        log::info!("Tight solid: color=0x{:06x}, translated bytes={:02x?}, use_24bit={}, client: depth={} bpp={} rshift={} gshift={} bshift={}",
            color, color_bytes, use_24bit, client_format.depth, client_format.bits_per_pixel,
            client_format.red_shift, client_format.green_shift, client_format.blue_shift);
    }

    buf.extend_from_slice(&color_bytes);

    #[cfg(feature = "debug-logging")]
    log::info!(
        "Tight solid: 0x{:06x}, control=0x{:02x}, color_len={}, total={} bytes",
        color,
        TIGHT_FILL << 4,
        color_bytes.len(),
        buf.len()
    );
    buf
}

/// Encode mono rectangle (2 colors)
/// Implements monochrome bitmap encoding with palette
/// Uses client's pixel format for palette colors
#[allow(clippy::too_many_arguments)] // All parameters are necessary for proper encoding
fn encode_mono_rect<C: TightStreamCompressor>(
    pixels: &[u8],
    width: u16,
    height: u16,
    bg: u32,
    fg: u32,
    compression: u8,
    client_format: &PixelFormat,
    compressor: &mut C,
) -> BytesMut {
    let conf_idx = match compression {
        0 => 0,
        1 => 1,
        2 | 3 => 2,
        _ => 3,
    };
    let zlib_level = TIGHT_CONF[conf_idx].mono_zlib_level;

    // Encode bitmap
    let bitmap = encode_mono_bitmap(pixels, width, height, bg);

    let mut buf = BytesMut::new();

    // Control byte
    if zlib_level == 0 {
        buf.put_u8((TIGHT_NO_ZLIB | TIGHT_EXPLICIT_FILTER) << 4);
    } else {
        buf.put_u8((STREAM_ID_MONO | TIGHT_EXPLICIT_FILTER) << 4);
    }

    // Filter and palette
    buf.put_u8(TIGHT_FILTER_PALETTE);
    buf.put_u8(1); // 2 colors - 1

    // Palette colors - translate to client format
    let bg_bytes = translate_pixel_to_client_format(bg, client_format);
    let fg_bytes = translate_pixel_to_client_format(fg, client_format);

    #[cfg(feature = "debug-logging")]
    {
        let use_24bit = client_format.depth == 24
            && client_format.red_max == 255
            && client_format.green_max == 255
            && client_format.blue_max == 255;
        log::info!("Tight mono palette: bg=0x{:06x} -> {:02x?}, fg=0x{:06x} -> {:02x?}, use_24bit={}, depth={} bpp={}",
            bg, bg_bytes, fg, fg_bytes, use_24bit, client_format.depth, client_format.bits_per_pixel);
    }

    buf.extend_from_slice(&bg_bytes);
    buf.extend_from_slice(&fg_bytes);

    // Compress data
    compress_data(&mut buf, &bitmap, zlib_level, STREAM_ID_MONO, compressor);

    #[cfg(feature = "debug-logging")]
    log::info!(
        "Tight mono: {}x{}, {} bytes ({}bpp)",
        width,
        height,
        buf.len(),
        client_format.bits_per_pixel
    );
    buf
}

/// Encode indexed palette rectangle (3-16 colors)
/// Implements palette-based encoding with color indices
/// Uses client's pixel format for palette colors
#[allow(clippy::cast_possible_truncation)] // Palette limited to 16 colors, indices fit in u8
fn encode_indexed_rect<C: TightStreamCompressor>(
    pixels: &[u8],
    width: u16,
    height: u16,
    palette: &[u32],
    compression: u8,
    client_format: &PixelFormat,
    compressor: &mut C,
) -> BytesMut {
    let conf_idx = match compression {
        0 => 0,
        1 => 1,
        2 | 3 => 2,
        _ => 3,
    };
    let zlib_level = TIGHT_CONF[conf_idx].idx_zlib_level;

    // Build color-to-index map
    let mut color_map = HashMap::new();
    for (idx, &color) in palette.iter().enumerate() {
        color_map.insert(color, idx as u8);
    }

    // Encode indices
    let mut indices = Vec::with_capacity(width as usize * height as usize);
    for chunk in pixels.chunks_exact(4) {
        let color = rgba_to_rgb24(chunk[0], chunk[1], chunk[2]);
        indices.push(*color_map.get(&color).unwrap_or(&0));
    }

    let mut buf = BytesMut::new();

    // Control byte
    if zlib_level == 0 {
        buf.put_u8((TIGHT_NO_ZLIB | TIGHT_EXPLICIT_FILTER) << 4);
    } else {
        buf.put_u8((STREAM_ID_INDEXED | TIGHT_EXPLICIT_FILTER) << 4);
    }

    // Filter and palette size
    buf.put_u8(TIGHT_FILTER_PALETTE);
    buf.put_u8((palette.len() - 1) as u8);

    // Palette colors - translate to client format
    for &color in palette {
        let color_bytes = translate_pixel_to_client_format(color, client_format);
        buf.extend_from_slice(&color_bytes);
    }

    // Compress data
    compress_data(
        &mut buf,
        &indices,
        zlib_level,
        STREAM_ID_INDEXED,
        compressor,
    );

    #[cfg(feature = "debug-logging")]
    log::info!(
        "Tight indexed: {} colors, {}x{}, {} bytes ({}bpp)",
        palette.len(),
        width,
        height,
        buf.len(),
        client_format.bits_per_pixel
    );
    buf
}

/// Encode full-color rectangle
/// Implements full-color zlib encoding for truecolor images
fn encode_full_color_rect<C: TightStreamCompressor>(
    pixels: &[u8],
    width: u16,
    height: u16,
    compression: u8,
    compressor: &mut C,
) -> BytesMut {
    let conf_idx = match compression {
        0 => 0,
        1 => 1,
        2 | 3 => 2,
        _ => 3,
    };
    let zlib_level = TIGHT_CONF[conf_idx].raw_zlib_level;

    // Convert RGBA to RGB24
    let mut rgb_data = Vec::with_capacity(width as usize * height as usize * 3);
    for chunk in pixels.chunks_exact(4) {
        rgb_data.push(chunk[0]);
        rgb_data.push(chunk[1]);
        rgb_data.push(chunk[2]);
    }

    let mut buf = BytesMut::new();

    // Control byte
    let control_byte = if zlib_level == 0 {
        TIGHT_NO_ZLIB << 4
    } else {
        STREAM_ID_FULL_COLOR << 4
    };
    buf.put_u8(control_byte);

    #[cfg(feature = "debug-logging")]
    log::info!(
        "Tight full-color: {}x{}, zlib_level={}, control_byte=0x{:02x}, rgb_data_len={}",
        width,
        height,
        zlib_level,
        control_byte,
        rgb_data.len()
    );

    // Compress data
    compress_data(
        &mut buf,
        &rgb_data,
        zlib_level,
        STREAM_ID_FULL_COLOR,
        compressor,
    );

    #[cfg(feature = "debug-logging")]
    log::info!(
        "Tight full-color: {}x{}, {} bytes total",
        width,
        height,
        buf.len()
    );
    buf
}

/// Encode JPEG rectangle
/// Implements lossy JPEG compression for photographic content
fn encode_jpeg_rect<C: TightStreamCompressor>(
    pixels: &[u8],
    width: u16,
    height: u16,
    #[allow(unused_variables)] quality: u8,
    compressor: &mut C,
) -> BytesMut {
    #[cfg(feature = "turbojpeg")]
    {
        use crate::jpeg::TurboJpegEncoder;

        // Convert RGBA to RGB
        let mut rgb_data = Vec::with_capacity(width as usize * height as usize * 3);
        for chunk in pixels.chunks_exact(4) {
            rgb_data.push(chunk[0]);
            rgb_data.push(chunk[1]);
            rgb_data.push(chunk[2]);
        }

        // Compress with TurboJPEG
        let jpeg_data = match TurboJpegEncoder::new() {
            Ok(mut encoder) => match encoder.compress_rgb(&rgb_data, width, height, quality) {
                Ok(data) => data,
                #[allow(unused_variables)]
                Err(e) => {
                    #[cfg(feature = "debug-logging")]
                    log::info!("TurboJPEG failed: {e}, using full-color");
                    return encode_full_color_rect(pixels, width, height, 6, compressor);
                }
            },
            #[allow(unused_variables)]
            Err(e) => {
                #[cfg(feature = "debug-logging")]
                log::info!("TurboJPEG init failed: {e}, using full-color");
                return encode_full_color_rect(pixels, width, height, 6, compressor);
            }
        };

        let mut buf = BytesMut::new();
        buf.put_u8(TIGHT_JPEG << 4); // 0x90
        write_compact_length(&mut buf, jpeg_data.len());
        buf.put_slice(&jpeg_data);

        #[cfg(feature = "debug-logging")]
        log::info!(
            "Tight JPEG: {}x{}, quality {}, {} bytes",
            width,
            height,
            quality,
            jpeg_data.len()
        );
        buf
    }

    #[cfg(not(feature = "turbojpeg"))]
    {
        #[cfg(feature = "debug-logging")]
        log::info!("TurboJPEG not enabled, using full-color (quality={quality})");
        encode_full_color_rect(pixels, width, height, 6, compressor)
    }
}

/// Compress data with zlib using persistent streams or send uncompressed
/// Handles compression based on data size and level settings
///
/// Uses persistent zlib streams via the `TightStreamCompressor` trait.
/// Persistent streams maintain their dictionary state across multiple compress operations.
fn compress_data<C: TightStreamCompressor>(
    buf: &mut BytesMut,
    data: &[u8],
    zlib_level: u8,
    stream_id: u8,
    compressor: &mut C,
) {
    #[cfg_attr(not(feature = "debug-logging"), allow(unused_variables))]
    let before_len = buf.len();

    // Data < 12 bytes sent raw WITHOUT length
    if data.len() < TIGHT_MIN_TO_COMPRESS {
        buf.put_slice(data);
        #[cfg(feature = "debug-logging")]
        log::info!(
            "compress_data: {} bytes < 12, sent raw (no length), buf grew by {} bytes",
            data.len(),
            buf.len() - before_len
        );
        return;
    }

    // zlibLevel == 0 means uncompressed WITH length
    if zlib_level == 0 {
        write_compact_length(buf, data.len());
        buf.put_slice(data);
        #[cfg(feature = "debug-logging")]
        log::info!("compress_data: {} bytes uncompressed (zlib_level=0), with length, buf grew by {} bytes", data.len(), buf.len() - before_len);
        return;
    }

    // Compress with persistent zlib stream
    match compressor.compress_tight_stream(stream_id, zlib_level, data) {
        Ok(compressed) => {
            write_compact_length(buf, compressed.len());
            buf.put_slice(&compressed);
            #[cfg(feature = "debug-logging")]
            log::info!(
                "compress_data: {} bytes compressed to {} using stream {}, buf grew by {} bytes",
                data.len(),
                compressed.len(),
                stream_id,
                buf.len() - before_len
            );
        }
        Err(e) => {
            // Compression failed - send uncompressed
            #[cfg(feature = "debug-logging")]
            log::info!(
                "compress_data: compression FAILED ({}), sending {} bytes uncompressed",
                e,
                data.len()
            );
            #[cfg(not(feature = "debug-logging"))]
            let _ = e;

            write_compact_length(buf, data.len());
            buf.put_slice(data);
        }
    }
}

/// Encode mono bitmap (1 bit per pixel)
/// Converts 2-color image to packed bitmap format
fn encode_mono_bitmap(pixels: &[u8], width: u16, height: u16, bg: u32) -> Vec<u8> {
    let w = width as usize;
    let h = height as usize;
    let bytes_per_row = w.div_ceil(8);
    let mut bitmap = vec![0u8; bytes_per_row * h];

    let mut bitmap_idx = 0;
    for y in 0..h {
        let mut byte_val = 0u8;
        let mut bit_pos = 7i32; // MSB first

        for x in 0..w {
            let pix_offset = (y * w + x) * 4;
            let color = rgba_to_rgb24(
                pixels[pix_offset],
                pixels[pix_offset + 1],
                pixels[pix_offset + 2],
            );

            if color != bg {
                byte_val |= 1 << bit_pos;
            }

            bit_pos -= 1;

            // Write byte after 8 pixels (when bit_pos becomes -1)
            if bit_pos < 0 {
                bitmap[bitmap_idx] = byte_val;
                bitmap_idx += 1;
                byte_val = 0;
                bit_pos = 7;
            }
        }

        // Write partial byte at end of row if width not multiple of 8
        if !w.is_multiple_of(8) {
            bitmap[bitmap_idx] = byte_val;
            bitmap_idx += 1;
        }
    }

    bitmap
}

/// Write compact length encoding
/// Implements variable-length integer encoding for Tight protocol
#[allow(clippy::cast_possible_truncation)] // Compact length encoding uses variable-length u8 packing per RFC 6143
fn write_compact_length(buf: &mut BytesMut, len: usize) {
    if len < 128 {
        buf.put_u8(len as u8);
    } else if len < 16384 {
        buf.put_u8(((len & 0x7F) | 0x80) as u8);
        buf.put_u8(((len >> 7) & 0x7F) as u8); // Mask to ensure high bit is clear
    } else {
        buf.put_u8(((len & 0x7F) | 0x80) as u8);
        buf.put_u8((((len >> 7) & 0x7F) | 0x80) as u8);
        buf.put_u8((len >> 14) as u8);
    }
}

/// Trait for managing persistent zlib compression streams
///
/// Implementations of this trait maintain separate compression streams for different
/// data types (full-color, mono, indexed) to improve compression ratios across
/// multiple rectangle updates.
pub trait TightStreamCompressor {
    /// Compresses data using a persistent zlib stream
    ///
    /// # Arguments
    /// * `stream_id` - Stream identifier (`STREAM_ID_FULL_COLOR`, `STREAM_ID_MONO`, or `STREAM_ID_INDEXED`)
    /// * `level` - Compression level (0-9)
    /// * `input` - Data to compress
    ///
    /// # Returns
    ///
    /// Compressed data or error message
    ///
    /// # Errors
    ///
    /// Returns an error if compression fails
    fn compress_tight_stream(
        &mut self,
        stream_id: u8,
        level: u8,
        input: &[u8],
    ) -> Result<Vec<u8>, String>;
}

/// Simple implementation of `TightStreamCompressor` for standalone encoding.
///
/// This creates separate persistent zlib streams for each stream ID (full-color, mono, indexed).
/// Used when encoding without access to a VNC client's stream manager.
pub struct SimpleTightCompressor {
    streams: [Option<flate2::Compress>; 4],
    level: u8,
}

impl SimpleTightCompressor {
    /// Creates a new `SimpleTightCompressor` with the specified compression level.
    #[must_use]
    pub fn new(level: u8) -> Self {
        Self {
            streams: [None, None, None, None],
            level,
        }
    }
}

impl TightStreamCompressor for SimpleTightCompressor {
    #[allow(clippy::cast_possible_truncation)] // Zlib total_out limited to buffer size
    fn compress_tight_stream(
        &mut self,
        stream_id: u8,
        level: u8,
        input: &[u8],
    ) -> Result<Vec<u8>, String> {
        use flate2::{Compress, Compression, FlushCompress};

        let stream_idx = stream_id as usize;
        if stream_idx >= 4 {
            return Err(format!("Invalid stream ID: {stream_id}"));
        }

        // Initialize stream if needed
        if self.streams[stream_idx].is_none() {
            self.streams[stream_idx] = Some(Compress::new(
                Compression::new(u32::from(level.min(self.level))),
                true,
            ));
        }

        let stream = self.streams[stream_idx].as_mut().unwrap();
        let mut output = vec![0u8; input.len() + 64];
        let before_out = stream.total_out();

        match stream.compress(input, &mut output, FlushCompress::Sync) {
            Ok(flate2::Status::Ok | flate2::Status::StreamEnd) => {
                let total_out = (stream.total_out() - before_out) as usize;
                output.truncate(total_out);
                Ok(output)
            }
            Ok(flate2::Status::BufError) => Err("Compression buffer error".to_string()),
            Err(e) => Err(format!("Compression failed: {e}")),
        }
    }
}

/// Encode Tight with persistent zlib streams, returning individual sub-rectangles
/// Returns a vector of (x, y, width, height, `encoded_data`) for each sub-rectangle
///
/// # Arguments
/// * `data` - Framebuffer pixel data (RGBA format)
/// * `width` - Rectangle width
/// * `height` - Rectangle height
/// * `quality` - JPEG quality level (0-9, or 10+ to disable JPEG)
/// * `compression` - Compression level (0-9)
/// * `client_format` - Client's pixel format for palette color translation
/// * `compressor` - Zlib stream compressor for persistent compression streams
pub fn encode_tight_rects<C: TightStreamCompressor>(
    data: &[u8],
    width: u16,
    height: u16,
    quality: u8,
    compression: u8,
    client_format: &PixelFormat,
    compressor: &mut C,
) -> Vec<(u16, u16, u16, u16, BytesMut)> {
    #[cfg(feature = "debug-logging")]
    log::info!(
        "DEBUG: encode_tight_rects called: {}x{}, data_len={}, quality={}, compression={}, bpp={}",
        width,
        height,
        data.len(),
        quality,
        compression,
        client_format.bits_per_pixel
    );

    let rect = Rect {
        x: 0,
        y: 0,
        w: width,
        h: height,
    };

    #[cfg(feature = "debug-logging")]
    log::info!("DEBUG: Calling encode_rect_optimized");

    let result = encode_rect_optimized(
        data,
        width,
        &rect,
        quality,
        compression,
        client_format,
        compressor,
    );

    #[cfg(feature = "debug-logging")]
    log::info!(
        "DEBUG: encode_rect_optimized returned {} rectangles",
        result.rectangles.len()
    );

    // Convert EncodeResult to public format
    let rects: Vec<(u16, u16, u16, u16, BytesMut)> = result
        .rectangles
        .into_iter()
        .map(|(r, buf)| {
            #[cfg(feature = "debug-logging")]
            log::info!(
                "DEBUG: Sub-rect: {}x{} at ({}, {}), encoded_len={}",
                r.w,
                r.h,
                r.x,
                r.y,
                buf.len()
            );
            (r.x, r.y, r.w, r.h, buf)
        })
        .collect();

    #[cfg(feature = "debug-logging")]
    log::info!(
        "DEBUG: encode_tight_rects returning {} rectangles",
        rects.len()
    );

    rects
}

/// Encode Tight with persistent zlib streams (for use with VNC client streams)
/// Returns concatenated data (legacy API - consider using `encode_tight_rects` instead)
pub fn encode_tight_with_streams<C: TightStreamCompressor>(
    data: &[u8],
    width: u16,
    height: u16,
    quality: u8,
    compression: u8,
    client_format: &PixelFormat,
    compressor: &mut C,
) -> BytesMut {
    // Concatenate all sub-rectangles
    let rects = encode_tight_rects(
        data,
        width,
        height,
        quality,
        compression,
        client_format,
        compressor,
    );
    let mut output = BytesMut::new();
    for (_x, _y, _w, _h, buf) in rects {
        output.extend_from_slice(&buf);
    }
    output
}