Compressor de Arquivos LZ77 em Rust

cargo new compressor-lz
cd compressor-lz

[package]
name = "compressor-lz"
version = "0.1.0"
edition = "2021"

use std::env;
use std::fs::File;
use std::io::{self, BufReader, BufWriter, Read, Write};

/// Tamanho da janela deslizante (quantos bytes anteriores são pesquisados)
const TAMANHO_JANELA: usize = 4096;

/// Tamanho máximo do buffer de lookahead (correspondência máxima)
const TAMANHO_LOOKAHEAD: usize = 255;

/// Comprimento mínimo para considerar uma correspondência
/// (referências menores que isso ocupam mais espaço que o literal)
const COMPRIMENTO_MINIMO: usize = 3;

/// Byte mágico que identifica nosso formato de arquivo comprimido
const MAGIC_BYTES: [u8; 4] = [b'L', b'Z', b'7', b'7'];

/// Token produzido pelo algoritmo LZ77
#[derive(Debug, Clone)]
enum Token {
    /// Referência a dados anteriores: (distância para trás, comprimento)
    Referencia { offset: u16, comprimento: u8 },
    /// Byte literal que não encontrou correspondência
    Literal(u8),
}

/// Encontra a maior correspondência dentro da janela deslizante.
/// Retorna (offset, comprimento) ou None se não encontrar correspondência
/// suficientemente longa.
fn encontrar_correspondencia(
    dados: &[u8],
    posicao: usize,
) -> Option<(u16, u8)> {
    // Início da janela de busca
    let inicio_janela = posicao.saturating_sub(TAMANHO_JANELA);
    // Bytes restantes disponíveis para correspondência
    let max_comprimento = TAMANHO_LOOKAHEAD.min(dados.len() - posicao);

    if max_comprimento < COMPRIMENTO_MINIMO {
        return None;
    }

    let mut melhor_offset: u16 = 0;
    let mut melhor_comprimento: usize = 0;

    // Percorre todas as posições possíveis na janela
    for candidato in inicio_janela..posicao {
        let mut comprimento = 0;

        // Conta quantos bytes consecutivos são iguais
        while comprimento < max_comprimento
            && dados[candidato + comprimento] == dados[posicao + comprimento]
        {
            comprimento += 1;
        }

        // Atualiza a melhor correspondência encontrada
        if comprimento >= COMPRIMENTO_MINIMO && comprimento > melhor_comprimento {
            melhor_offset = (posicao - candidato) as u16;
            melhor_comprimento = comprimento;
        }
    }

    if melhor_comprimento >= COMPRIMENTO_MINIMO {
        Some((melhor_offset, melhor_comprimento as u8))
    } else {
        None
    }
}

/// Comprime os dados usando o algoritmo LZ77, retornando uma lista de tokens
fn comprimir_lz77(dados: &[u8]) -> Vec<Token> {
    let mut tokens = Vec::new();
    let mut posicao: usize = 0;

    while posicao < dados.len() {
        if let Some((offset, comprimento)) = encontrar_correspondencia(dados, posicao) {
            // Encontrou correspondência: emite uma referência
            tokens.push(Token::Referencia { offset, comprimento });
            posicao += comprimento as usize;
        } else {
            // Sem correspondência: emite o byte literal
            tokens.push(Token::Literal(dados[posicao]));
            posicao += 1;
        }
    }

    tokens
}

/// Codifica os tokens em formato binário e escreve no escritor
fn codificar_tokens<W: Write>(
    tokens: &[Token],
    escritor: &mut W,
) -> io::Result<()> {
    for token in tokens {
        match token {
            Token::Literal(byte) => {
                // Flag 0x00 seguido do byte literal
                escritor.write_all(&[0x00, *byte])?;
            }
            Token::Referencia { offset, comprimento } => {
                // Flag 0x01 seguido de offset (2 bytes, big-endian) e comprimento (1 byte)
                escritor.write_all(&[0x01])?;
                escritor.write_all(&offset.to_be_bytes())?;
                escritor.write_all(&[*comprimento])?;
            }
        }
    }
    Ok(())
}

/// Decodifica os tokens do formato binário lido do leitor
fn decodificar_tokens<R: Read>(leitor: &mut R) -> io::Result<Vec<Token>> {
    let mut tokens = Vec::new();
    let mut flag = [0u8; 1];

    loop {
        // Lê o byte de flag
        match leitor.read_exact(&mut flag) {
            Ok(()) => {}
            Err(e) if e.kind() == io::ErrorKind::UnexpectedEof => break,
            Err(e) => return Err(e),
        }

        match flag[0] {
            0x00 => {
                // Token literal: lê o próximo byte
                let mut byte = [0u8; 1];
                leitor.read_exact(&mut byte)?;
                tokens.push(Token::Literal(byte[0]));
            }
            0x01 => {
                // Token de referência: lê offset (2 bytes) e comprimento (1 byte)
                let mut buf_offset = [0u8; 2];
                let mut buf_comprimento = [0u8; 1];
                leitor.read_exact(&mut buf_offset)?;
                leitor.read_exact(&mut buf_comprimento)?;
                let offset = u16::from_be_bytes(buf_offset);
                let comprimento = buf_comprimento[0];
                tokens.push(Token::Referencia { offset, comprimento });
            }
            outro => {
                return Err(io::Error::new(
                    io::ErrorKind::InvalidData,
                    format!("Flag inválido no arquivo comprimido: 0x{:02X}", outro),
                ));
            }
        }
    }

    Ok(tokens)
}

/// Reconstrói os dados originais a partir dos tokens decodificados
fn descomprimir_lz77(tokens: &[Token]) -> Vec<u8> {
    let mut saida: Vec<u8> = Vec::new();

    for token in tokens {
        match token {
            Token::Literal(byte) => {
                saida.push(*byte);
            }
            Token::Referencia { offset, comprimento } => {
                // Copia bytes da própria saída, um por vez
                // (necessário porque a referência pode sobrepor a região copiada)
                let inicio = saida.len() - *offset as usize;
                for i in 0..*comprimento as usize {
                    let byte = saida[inicio + i];
                    saida.push(byte);
                }
            }
        }
    }

    saida
}

/// Comprime um arquivo e salva o resultado
fn comprimir_arquivo(caminho_entrada: &str, caminho_saida: &str) -> io::Result<()> {
    // Lê todo o arquivo de entrada
    let arquivo_entrada = File::open(caminho_entrada)?;
    let mut leitor = BufReader::new(arquivo_entrada);
    let mut dados = Vec::new();
    leitor.read_to_end(&mut dados)?;

    let tamanho_original = dados.len();
    println!("Comprimindo '{}' ({} bytes)...", caminho_entrada, tamanho_original);

    // Comprime os dados
    let tokens = comprimir_lz77(&dados);

    // Conta estatísticas dos tokens
    let num_literais = tokens.iter().filter(|t| matches!(t, Token::Literal(_))).count();
    let num_referencias = tokens.iter().filter(|t| matches!(t, Token::Referencia { .. })).count();
    println!(
        "  Tokens gerados: {} literais, {} referências",
        num_literais, num_referencias
    );

    // Escreve o arquivo comprimido
    let arquivo_saida = File::create(caminho_saida)?;
    let mut escritor = BufWriter::new(arquivo_saida);

    // Cabeçalho: bytes mágicos + tamanho original (4 bytes, big-endian)
    escritor.write_all(&MAGIC_BYTES)?;
    escritor.write_all(&(tamanho_original as u32).to_be_bytes())?;

    // Dados comprimidos
    codificar_tokens(&tokens, &mut escritor)?;
    escritor.flush()?;

    // Calcula e exibe as estatísticas
    let tamanho_comprimido = std::fs::metadata(caminho_saida)?.len() as usize;
    let razao = tamanho_comprimido as f64 / tamanho_original as f64 * 100.0;
    let economia = tamanho_original as i64 - tamanho_comprimido as i64;

    println!("  Tamanho comprimido: {} bytes", tamanho_comprimido);
    println!("  Razão de compressão: {:.1}%", razao);
    if economia > 0 {
        println!("  Economia: {} bytes ({:.1}%)", economia, 100.0 - razao);
    } else {
        println!("  Aviso: arquivo comprimido ficou maior que o original!");
    }
    println!("  Salvo em '{}'", caminho_saida);

    Ok(())
}

/// Descomprime um arquivo e salva o resultado
fn descomprimir_arquivo(caminho_entrada: &str, caminho_saida: &str) -> io::Result<()> {
    let arquivo_entrada = File::open(caminho_entrada)?;
    let mut leitor = BufReader::new(arquivo_entrada);

    // Verifica os bytes mágicos
    let mut magic = [0u8; 4];
    leitor.read_exact(&mut magic)?;
    if magic != MAGIC_BYTES {
        return Err(io::Error::new(
            io::ErrorKind::InvalidData,
            "Arquivo não é um arquivo LZ77 válido (bytes mágicos incorretos)",
        ));
    }

    // Lê o tamanho original
    let mut buf_tamanho = [0u8; 4];
    leitor.read_exact(&mut buf_tamanho)?;
    let tamanho_original = u32::from_be_bytes(buf_tamanho) as usize;

    println!(
        "Descomprimindo '{}' (tamanho original: {} bytes)...",
        caminho_entrada, tamanho_original
    );

    // Decodifica os tokens
    let tokens = decodificar_tokens(&mut leitor)?;
    println!("  Tokens lidos: {}", tokens.len());

    // Reconstrói os dados originais
    let dados = descomprimir_lz77(&tokens);

    // Verifica integridade
    if dados.len() != tamanho_original {
        return Err(io::Error::new(
            io::ErrorKind::InvalidData,
            format!(
                "Tamanho descomprimido ({}) difere do esperado ({})",
                dados.len(),
                tamanho_original
            ),
        ));
    }

    // Escreve o arquivo descomprimido
    let arquivo_saida = File::create(caminho_saida)?;
    let mut escritor = BufWriter::new(arquivo_saida);
    escritor.write_all(&dados)?;
    escritor.flush()?;

    println!("  Descomprimido com sucesso em '{}'", caminho_saida);

    Ok(())
}

/// Exibe as instruções de uso do programa
fn exibir_uso() {
    eprintln!("Compressor de Arquivos LZ77");
    eprintln!();
    eprintln!("Uso:");
    eprintln!("  compressor-lz comprimir   <entrada> <saida.lz>");
    eprintln!("  compressor-lz descomprimir <entrada.lz> <saida>");
    eprintln!();
    eprintln!("Exemplos:");
    eprintln!("  compressor-lz comprimir   texto.txt texto.txt.lz");
    eprintln!("  compressor-lz descomprimir texto.txt.lz texto_recuperado.txt");
}

fn main() {
    let args: Vec<String> = env::args().collect();

    if args.len() != 4 {
        exibir_uso();
        std::process::exit(1);
    }

    let comando = args[1].as_str();
    let entrada = &args[2];
    let saida = &args[3];

    let resultado = match comando {
        "comprimir" | "c" => comprimir_arquivo(entrada, saida),
        "descomprimir" | "d" => descomprimir_arquivo(entrada, saida),
        _ => {
            eprintln!("Comando desconhecido: '{}'\n", comando);
            exibir_uso();
            std::process::exit(1);
        }
    };

    if let Err(e) = resultado {
        eprintln!("Erro: {}", e);
        std::process::exit(1);
    }
}

cargo build --release

# Cria um arquivo de texto com conteúdo repetitivo (ideal para LZ77)
echo "Rust é uma linguagem de programação. Rust é rápida. Rust é segura. Rust é incrível. Programação em Rust é produtiva. A linguagem Rust cresce cada dia mais." > teste.txt

# Comprime o arquivo
cargo run --release -- comprimir teste.txt teste.txt.lz

# Saída esperada:
# Comprimindo 'teste.txt' (178 bytes)...
#   Tokens gerados: 92 literais, 22 referências
#   Tamanho comprimido: 202 bytes
#   Razão de compressão: ...%
#   Salvo em 'teste.txt.lz'

# Descomprime o arquivo
cargo run --release -- descomprimir teste.txt.lz teste_recuperado.txt

# Verifica que o conteúdo é idêntico
diff teste.txt teste_recuperado.txt && echo "Arquivos idênticos!"

# Baixe um arquivo de texto grande (ex: livro em domínio público)
# ou use um log do sistema
cargo run --release -- comprimir /var/log/syslog syslog.lz
cargo run --release -- descomprimir syslog.lz syslog_recuperado