LZ77 e DEFLATE: a base do PNG e do ZIP (visão geral)

... dados já processados ... | ... dados sendo processados ... | ... dados futuros ...
         ←── JANELA ──→        ←── LOOKAHEAD ──→
    (search buffer)              (lookahead buffer)

Entrada: ABRACADABRA_ABRACADABRA

Search: (vazio)
Lookahead: ABRACADABRA_ABRACADABRA

Search: A
Lookahead: BRACADABRA_ABRACADABRA

Search: AB
Lookahead: RACADABRA_ABRACADABRA

Search: ABR
Lookahead: ACADABRA_ABRACADABRA

Search: ABRACADABRA_
Lookahead: ABRACADABRA

Original:    ABRACADABRA_ABRACADABRA  (23 bytes)
Comprimido:  A B R A C A D A B R A _ (dist=12, len=11)
             12 literais + 1 referência

Entrada: [10, 20, 30, 40, 50, 10, 20, 30, 40, 50, 10, 20, 30]

Posição 5: copia de posição 0 → 10
Posição 6: copia de posição 1 → 20
Posição 7: copia de posição 2 → 30
Posição 8: copia de posição 3 → 40
Posição 9: copia de posição 4 → 50
Posição 10: copia de posição 5 → 10  (que acabou de ser escrito!)
Posição 11: copia de posição 6 → 20
Posição 12: copia de posição 7 → 30

Original:    [10, 20, 30, 40, 50, 10, 20, 30, 40, 50, 10, 20, 30]  (13 bytes)
Comprimido:  [10, 20, 30, 40, 50] + referência(dist=5, len=8)
             5 literais + 1 referência ≈ 8-9 bytes

Dados originais
      │
      ▼
   [LZ77]  → Literais + Referências (distância, comprimento)
      │
      ▼
  [Huffman] → Códigos binários de tamanho variável
      │
      ▼
Dados comprimidos (DEFLATE)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// ============================================================
// LZ77 SIMPLIFICADO
// ============================================================
//
// Parâmetros da janela:
//   WINDOW_SIZE: tamanho do search buffer (onde procurar matches)
//   LOOKAHEAD_SIZE: tamanho do lookahead buffer
//   MIN_MATCH: comprimento mínimo pra uma referência valer a pena
//
// No DEFLATE real: WINDOW_SIZE = 32768, MAX_MATCH = 258, MIN_MATCH = 3
// Aqui usamos valores menores pra facilitar a visualização.

#define WINDOW_SIZE    256
#define LOOKAHEAD_SIZE 64
#define MIN_MATCH      3

// Cada token de saída é:
//   - Um LITERAL: type=0, valor=byte
//   - Uma REFERÊNCIA: type=1, distância + comprimento

typedef struct {
    int type;          // 0 = literal, 1 = referência
    unsigned char literal;  // o byte literal (se type=0)
    int distancia;     // distância pra trás (se type=1)
    int comprimento;   // quantos bytes copiar (se type=1)
} TokenLZ77;

// ============================================================
// ENCODER: encontra correspondências e emite tokens
// ============================================================

int lz77_encode(unsigned char *entrada, int tamanho,
                TokenLZ77 *saida, int max_tokens) {
    int pos = 0;          // posição atual na entrada
    int num_tokens = 0;   // quantos tokens já emitimos

    while (pos < tamanho && num_tokens < max_tokens) {
        int melhor_dist = 0;
        int melhor_len  = 0;

        // Define os limites do search buffer
        // (não pode olhar antes do início do arquivo)
        int inicio_busca = pos - WINDOW_SIZE;
        if (inicio_busca < 0) inicio_busca = 0;

        // Define o limite do lookahead
        int lookahead_max = tamanho - pos;
        if (lookahead_max > LOOKAHEAD_SIZE) lookahead_max = LOOKAHEAD_SIZE;

        // Procura a melhor correspondência no search buffer
        for (int s = inicio_busca; s < pos; s++) {
            int len = 0;

            // Conta quantos bytes consecutivos são iguais
            // Note: a cópia pode se estender além de 'pos'
            // (o truque do "copiar de si mesmo")
            while (len < lookahead_max && entrada[s + len] == entrada[pos + len]) {
                len++;
            }

            // Se essa correspondência é a melhor até agora, salva
            if (len > melhor_len) {
                melhor_len  = len;
                melhor_dist = pos - s;
            }
        }

        // Decide: emitir literal ou referência?
        if (melhor_len >= MIN_MATCH) {
            // Correspondência boa o suficiente → emite referência
            saida[num_tokens].type = 1;
            saida[num_tokens].distancia = melhor_dist;
            saida[num_tokens].comprimento = melhor_len;
            num_tokens++;
            pos += melhor_len;  // avança pelo comprimento da correspondência
        } else {
            // Correspondência muito curta (ou nenhuma) → emite literal
            saida[num_tokens].type = 0;
            saida[num_tokens].literal = entrada[pos];
            num_tokens++;
            pos += 1;  // avança 1 byte
        }
    }

    return num_tokens;
}

// ============================================================
// DECODER: reconstrói os dados a partir dos tokens
// ============================================================

int lz77_decode(TokenLZ77 *tokens, int num_tokens,
                unsigned char *saida, int max_saida) {
    int pos = 0;  // posição atual na saída

    for (int i = 0; i < num_tokens && pos < max_saida; i++) {
        if (tokens[i].type == 0) {
            // Literal: escreve o byte diretamente
            saida[pos] = tokens[i].literal;
            pos++;
        } else {
            // Referência: copia bytes de uma posição anterior
            int dist = tokens[i].distancia;
            int len  = tokens[i].comprimento;
            int src  = pos - dist;  // posição de onde copiar

            // Copia byte a byte (importante pra o caso de
            // dist < len, onde copiamos de nós mesmos)
            for (int j = 0; j < len && pos < max_saida; j++) {
                saida[pos] = saida[src + j];
                pos++;
            }
        }
    }

    return pos;
}

// ============================================================
// MAIN — Testa com exemplos concretos
// ============================================================

int main() {
    printf("=== LZ77 Simplificado ===\n\n");

    // ----- Teste 1: ABRACADABRA_ABRACADABRA -----
    printf("--- Teste 1: ABRACADABRA_ABRACADABRA ---\n\n");

    char *texto1 = "ABRACADABRA_ABRACADABRA";
    int tamanho1 = strlen(texto1);

    TokenLZ77 tokens1[100];
    int num_tokens1 = lz77_encode((unsigned char *)texto1, tamanho1,
                                   tokens1, 100);

    printf("Original: \"%s\" (%d bytes)\n\n", texto1, tamanho1);
    printf("Tokens LZ77:\n");

    int literais1 = 0, refs1 = 0;
    for (int i = 0; i < num_tokens1; i++) {
        if (tokens1[i].type == 0) {
            printf("  [L] '%c'\n", tokens1[i].literal);
            literais1++;
        } else {
            printf("  [R] (dist=%d, len=%d)\n",
                   tokens1[i].distancia, tokens1[i].comprimento);
            refs1++;
        }
    }

    printf("\nTotal: %d literais + %d referências = %d tokens\n",
           literais1, refs1, num_tokens1);

    // Estimar tamanho comprimido
    // (1 byte por literal, 3 bytes por referência: 1 flag + 1 dist + 1 len)
    int tam_comp1 = literais1 * 1 + refs1 * 3;
    printf("Tamanho estimado: ~%d bytes (original: %d bytes)\n",
           tam_comp1, tamanho1);
    printf("Economia estimada: ~%.1f%%\n\n",
           (1.0 - (double)tam_comp1 / tamanho1) * 100.0);

    // Verificação lossless
    unsigned char dec1[100];
    int tam_dec1 = lz77_decode(tokens1, num_tokens1, dec1, 100);
    dec1[tam_dec1] = '\0';
    int ok1 = (tam_dec1 == tamanho1) && (memcmp(texto1, dec1, tamanho1) == 0);
    printf("Decodificado: \"%s\"\n", dec1);
    printf("Lossless: %s\n\n", ok1 ? "SIM" : "NÃO (ERRO!)");

    // ----- Teste 2: Padrão repetitivo longo -----
    printf("--- Teste 2: Padrão repetitivo longo ---\n\n");

    // Cria uma string com um padrão de 5 bytes repetido 10 vezes
    unsigned char teste2[50];
    for (int i = 0; i < 50; i++) {
        unsigned char padrao[] = {10, 20, 30, 40, 50};
        teste2[i] = padrao[i % 5];
    }
    int tamanho2 = 50;

    TokenLZ77 tokens2[100];
    int num_tokens2 = lz77_encode(teste2, tamanho2, tokens2, 100);

    printf("Original: [10,20,30,40,50] repetido 10x (%d bytes)\n\n", tamanho2);
    printf("Tokens LZ77:\n");

    int literais2 = 0, refs2 = 0;
    for (int i = 0; i < num_tokens2; i++) {
        if (tokens2[i].type == 0) {
            printf("  [L] %d\n", tokens2[i].literal);
            literais2++;
        } else {
            printf("  [R] (dist=%d, len=%d)\n",
                   tokens2[i].distancia, tokens2[i].comprimento);
            refs2++;
        }
    }

    printf("\nTotal: %d literais + %d referências = %d tokens\n",
           literais2, refs2, num_tokens2);
    int tam_comp2 = literais2 * 1 + refs2 * 3;
    printf("Tamanho estimado: ~%d bytes (original: %d bytes)\n",
           tam_comp2, tamanho2);
    printf("Economia estimada: ~%.1f%%\n\n",
           (1.0 - (double)tam_comp2 / tamanho2) * 100.0);

    unsigned char dec2[100];
    int tam_dec2 = lz77_decode(tokens2, num_tokens2, dec2, 100);
    int ok2 = (tam_dec2 == tamanho2) && (memcmp(teste2, dec2, tamanho2) == 0);
    printf("Lossless: %s\n\n", ok2 ? "SIM" : "NÃO (ERRO!)");

    // ----- Teste 3: Dados sem repetição (pior caso) -----
    printf("--- Teste 3: Dados sem repetição (pior caso) ---\n\n");

    unsigned char teste3[20];
    for (int i = 0; i < 20; i++) teste3[i] = (unsigned char)(i * 13 + 7);
    int tamanho3 = 20;

    TokenLZ77 tokens3[100];
    int num_tokens3 = lz77_encode(teste3, tamanho3, tokens3, 100);

    int literais3 = 0, refs3 = 0;
    for (int i = 0; i < num_tokens3; i++) {
        if (tokens3[i].type == 0) literais3++;
        else refs3++;
    }

    printf("Original: 20 bytes sem padrão\n");
    printf("Tokens: %d literais + %d referências\n", literais3, refs3);
    int tam_comp3 = literais3 * 1 + refs3 * 3;
    printf("Tamanho estimado: ~%d bytes (original: %d bytes)\n",
           tam_comp3, tamanho3);
    printf("Economia: ~%.1f%% %s\n\n",
           (1.0 - (double)tam_comp3 / tamanho3) * 100.0,
           tam_comp3 >= tamanho3 ? "(sem ganho)" : "");

    unsigned char dec3[100];
    int tam_dec3 = lz77_decode(tokens3, num_tokens3, dec3, 100);
    int ok3 = (tam_dec3 == tamanho3) && (memcmp(teste3, dec3, tamanho3) == 0);
    printf("Lossless: %s\n\n", ok3 ? "SIM" : "NÃO (ERRO!)");

    // ----- Resumo -----
    printf("=== Resumo ===\n");
    printf("Teste 1 (ABRACADABRA×2):  %2d bytes → ~%2d bytes (%.1f%%)\n",
           tamanho1, tam_comp1, (1.0-(double)tam_comp1/tamanho1)*100.0);
    printf("Teste 2 (padrão×10):      %2d bytes → ~%2d bytes (%.1f%%)\n",
           tamanho2, tam_comp2, (1.0-(double)tam_comp2/tamanho2)*100.0);
    printf("Teste 3 (sem padrão):     %2d bytes → ~%2d bytes (%.1f%%)\n",
           tamanho3, tam_comp3, (1.0-(double)tam_comp3/tamanho3)*100.0);

    return 0;
}

cd ~/lz77-test
gcc main.c -o lz77
./lz77

COMPRESSOR
                    
Arquivo original → [Encoder LZ77] → BitWriter → Arquivo .lz77
                                                  ┌──────────┐
                                                  │  HEADER   │
                                                  │ "LZ77"    │
                                                  │ tam_orig  │
                                                  │ janela    │
                                                  │ max_match │
                                                  ├──────────┤
                                                  │  DADOS    │
                                                  │ (bits)    │
                                                  └──────────┘

                   DESCOMPRESSOR

Arquivo .lz77 → [Header] → BitReader → [Decoder LZ77] → Arquivo restaurado

[Header — 12 bytes]
  Bytes 0-3:   Magic number "LZ77" (pra identificar o formato)
  Bytes 4-7:   Tamanho original do arquivo (4 bytes, little-endian)
  Bytes 8-9:   Tamanho da janela (2 bytes, little-endian)
  Bytes 10-11: Comprimento máximo do match (2 bytes, little-endian)

[Dados comprimidos — tamanho variável]
  Sequência de tokens, cada um começando com 1 bit de flag:
    Flag 0 → LITERAL:    8 bits do byte original           = 9 bits total
    Flag 1 → REFERÊNCIA: 15 bits de distância + 8 bits de comprimento = 24 bits total

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// ============================================================
// PARÂMETROS DO LZ77
// ============================================================
// Mesmos parâmetros do DEFLATE:
//   Janela de 32 KB, match máximo de 258 bytes, mínimo de 3

#define WINDOW_SIZE  32768
#define MAX_MATCH    258
#define MIN_MATCH    3
#define DIST_BITS    15     // 2^15 = 32768 (cobre a janela inteira)
#define LEN_BITS     8      // 8 bits = 0..255, que com offset +3 = 3..258

// ============================================================
// BITWRITER — Escreve bits individuais num buffer de bytes
// ============================================================
//
// Os tokens do LZ77 não são alinhados em bytes:
//   - Literal:    1 bit flag + 8 bits valor    = 9 bits
//   - Referência: 1 bit flag + 15 bits dist + 8 bits len = 24 bits
//
// Por isso precisamos escrever bit a bit.
// O BitWriter preenche cada byte do MSB (bit 7) pro LSB (bit 0).

typedef struct {
    unsigned char *buffer;   // array de bytes
    int capacidade;          // tamanho alocado
    int byte_pos;            // qual byte estamos preenchendo
    int bit_pos;             // qual bit (7=MSB, 0=LSB)
    int total_bits;          // total de bits escritos
} BitWriter;

BitWriter *bitwriter_criar(int capacidade_inicial) {
    BitWriter *bw = (BitWriter *) malloc(sizeof(BitWriter));
    bw->buffer = (unsigned char *) calloc(capacidade_inicial, 1);
    bw->capacidade = capacidade_inicial;
    bw->byte_pos = 0;
    bw->bit_pos = 7;
    bw->total_bits = 0;
    return bw;
}

// Dobra o buffer se necessário
void bitwriter_garantir_espaco(BitWriter *bw, int bytes_extras) {
    while (bw->byte_pos + bytes_extras >= bw->capacidade) {
        int cap_antigo = bw->capacidade;
        bw->capacidade *= 2;
        bw->buffer = (unsigned char *) realloc(bw->buffer, bw->capacidade);
        memset(bw->buffer + cap_antigo, 0, bw->capacidade - cap_antigo);
    }
}

// Escreve um único bit (0 ou 1)
void bitwriter_escrever_bit(BitWriter *bw, int bit) {
    bitwriter_garantir_espaco(bw, 4);
    if (bit) {
        bw->buffer[bw->byte_pos] |= (1 << bw->bit_pos);
    }
    bw->bit_pos--;
    bw->total_bits++;
    if (bw->bit_pos < 0) {
        bw->byte_pos++;
        bw->bit_pos = 7;
    }
}

// Escreve N bits de um valor inteiro (MSB primeiro)
void bitwriter_escrever_bits(BitWriter *bw, int valor, int num_bits) {
    for (int i = num_bits - 1; i >= 0; i--) {
        bitwriter_escrever_bit(bw, (valor >> i) & 1);
    }
}

// Quantos bytes os bits escritos ocupam (arredondando pra cima)
int bitwriter_bytes_usados(BitWriter *bw) {
    return (bw->bit_pos == 7) ? bw->byte_pos : bw->byte_pos + 1;
}

void bitwriter_liberar(BitWriter *bw) {
    free(bw->buffer);
    free(bw);
}

// ============================================================
// BITREADER — Lê bits individuais de um buffer de bytes
// ============================================================

typedef struct {
    unsigned char *buffer;
    int tamanho;
    int byte_pos;
    int bit_pos;
} BitReader;

BitReader *bitreader_criar(unsigned char *buffer, int tamanho) {
    BitReader *br = (BitReader *) malloc(sizeof(BitReader));
    br->buffer = buffer;
    br->tamanho = tamanho;
    br->byte_pos = 0;
    br->bit_pos = 7;
    return br;
}

int bitreader_ler_bit(BitReader *br) {
    if (br->byte_pos >= br->tamanho) return 0;
    int bit = (br->buffer[br->byte_pos] >> br->bit_pos) & 1;
    br->bit_pos--;
    if (br->bit_pos < 0) {
        br->byte_pos++;
        br->bit_pos = 7;
    }
    return bit;
}

int bitreader_ler_bits(BitReader *br, int num_bits) {
    int valor = 0;
    for (int i = 0; i < num_bits; i++) {
        valor = (valor << 1) | bitreader_ler_bit(br);
    }
    return valor;
}

void bitreader_liberar(BitReader *br) {
    free(br);
}

// ============================================================
// HEADER DO ARQUIVO .lz77
// ============================================================

typedef struct {
    char magic[4];              // "LZ77"
    unsigned int tamanho_orig;  // tamanho do arquivo original
    unsigned short janela;      // tamanho da janela
    unsigned short max_match;   // comprimento máximo
} HeaderLZ77;

// ============================================================
// ENCODER — Busca correspondências e serializa em bits
// ============================================================

// Encontra o match mais longo no search buffer
int encontrar_match(unsigned char *dados, int tamanho, int pos,
                    int *melhor_dist) {
    int melhor_len = 0;
    *melhor_dist = 0;

    int inicio = pos - WINDOW_SIZE;
    if (inicio < 0) inicio = 0;

    int max_len = tamanho - pos;
    if (max_len > MAX_MATCH) max_len = MAX_MATCH;

    for (int s = inicio; s < pos; s++) {
        int len = 0;

        // Compara byte a byte
        // Permite len avançar além de pos (copiar de si mesmo)
        while (len < max_len && dados[s + len] == dados[pos + len]) {
            len++;
        }

        if (len > melhor_len) {
            melhor_len = len;
            *melhor_dist = pos - s;
            if (melhor_len == max_len) break;  // não dá pra melhorar
        }
    }

    return melhor_len;
}

// Comprime dados e retorna o buffer do arquivo .lz77
unsigned char *lz77_comprimir(unsigned char *entrada, int tam_entrada,
                               int *tam_saida) {
    BitWriter *bw = bitwriter_criar(tam_entrada + 1024);

    int pos = 0;
    int num_literais = 0, num_refs = 0;

    while (pos < tam_entrada) {
        int dist = 0;
        int len = encontrar_match(entrada, tam_entrada, pos, &dist);

        if (len >= MIN_MATCH) {
            // REFERÊNCIA: flag=1 + distância (15 bits) + comprimento (8 bits)
            bitwriter_escrever_bit(bw, 1);
            bitwriter_escrever_bits(bw, dist, DIST_BITS);
            bitwriter_escrever_bits(bw, len - MIN_MATCH, LEN_BITS);
            pos += len;
            num_refs++;
        } else {
            // LITERAL: flag=0 + byte (8 bits)
            bitwriter_escrever_bit(bw, 0);
            bitwriter_escrever_bits(bw, entrada[pos], 8);
            pos++;
            num_literais++;
        }
    }

    // Monta o arquivo: header + dados comprimidos
    int dados_bytes = bitwriter_bytes_usados(bw);
    int total = sizeof(HeaderLZ77) + dados_bytes;
    unsigned char *saida = (unsigned char *) malloc(total);

    HeaderLZ77 *h = (HeaderLZ77 *) saida;
    memcpy(h->magic, "LZ77", 4);
    h->tamanho_orig = (unsigned int) tam_entrada;
    h->janela = WINDOW_SIZE;
    h->max_match = MAX_MATCH;

    memcpy(saida + sizeof(HeaderLZ77), bw->buffer, dados_bytes);
    *tam_saida = total;

    printf("  Estatísticas: %d literais, %d referências\n",
           num_literais, num_refs);
    printf("  Bits: %d literais × 9 + %d refs × 24 = %d bits\n",
           num_literais, num_refs,
           num_literais * 9 + num_refs * 24);

    bitwriter_liberar(bw);
    return saida;
}

// ============================================================
// DECODER — Lê o arquivo .lz77 e reconstrói o original
// ============================================================

unsigned char *lz77_descomprimir(unsigned char *arquivo, int tam_arquivo,
                                  int *tam_saida) {
    if (tam_arquivo < (int)sizeof(HeaderLZ77)) {
        printf("ERRO: arquivo muito pequeno.\n");
        *tam_saida = 0;
        return NULL;
    }

    HeaderLZ77 *h = (HeaderLZ77 *) arquivo;

    if (memcmp(h->magic, "LZ77", 4) != 0) {
        printf("ERRO: magic number inválido.\n");
        *tam_saida = 0;
        return NULL;
    }

    int tam_orig = (int) h->tamanho_orig;
    printf("  Header: magic=LZ77, tam_orig=%d, janela=%d, max_match=%d\n",
           tam_orig, h->janela, h->max_match);

    unsigned char *saida = (unsigned char *) malloc(tam_orig);
    if (!saida) {
        printf("ERRO: sem memória.\n");
        *tam_saida = 0;
        return NULL;
    }

    BitReader *br = bitreader_criar(
        arquivo + sizeof(HeaderLZ77),
        tam_arquivo - sizeof(HeaderLZ77));

    int pos = 0;

    while (pos < tam_orig) {
        int flag = bitreader_ler_bit(br);

        if (flag == 0) {
            // LITERAL
            saida[pos] = (unsigned char) bitreader_ler_bits(br, 8);
            pos++;
        } else {
            // REFERÊNCIA
            int dist = bitreader_ler_bits(br, DIST_BITS);
            int len  = bitreader_ler_bits(br, LEN_BITS) + MIN_MATCH;

            // Copia byte a byte (essencial pro caso dist < len)
            int src = pos - dist;
            for (int i = 0; i < len && pos < tam_orig; i++) {
                saida[pos] = saida[src + i];
                pos++;
            }
        }
    }

    bitreader_liberar(br);
    *tam_saida = pos;
    return saida;
}

// ============================================================
// LEITURA E ESCRITA DE ARQUIVOS
// ============================================================

unsigned char *ler_arquivo(const char *caminho, int *tamanho) {
    FILE *f = fopen(caminho, "rb");
    if (!f) {
        printf("ERRO: não consegui abrir '%s'\n", caminho);
        *tamanho = 0;
        return NULL;
    }
    fseek(f, 0, SEEK_END);
    *tamanho = (int) ftell(f);
    fseek(f, 0, SEEK_SET);
    unsigned char *dados = (unsigned char *) malloc(*tamanho);
    if (fread(dados, 1, *tamanho, f) != (size_t)*tamanho) {
        printf("ERRO: falha ao ler '%s'\n", caminho);
        free(dados);
        fclose(f);
        *tamanho = 0;
        return NULL;
    }
    fclose(f);
    return dados;
}

int escrever_arquivo(const char *caminho, unsigned char *dados, int tamanho) {
    FILE *f = fopen(caminho, "wb");
    if (!f) {
        printf("ERRO: não consegui criar '%s'\n", caminho);
        return 0;
    }
    fwrite(dados, 1, tamanho, f);
    fclose(f);
    return 1;
}

// ============================================================
// TESTES INTERNOS
// ============================================================

void rodar_testes() {
    printf("=== TESTES INTERNOS DO LZ77 COMPLETO ===\n\n");

    // Teste 1: String com repetição
    printf("--- Teste 1: ABRACADABRA_ABRACADABRA ---\n");
    {
        char *texto = "ABRACADABRA_ABRACADABRA";
        int tam_orig = strlen(texto);
        int tam_comp;
        unsigned char *comp = lz77_comprimir((unsigned char *)texto, tam_orig, &tam_comp);
        printf("  Original: %d bytes | Comprimido: %d bytes | Compressão: %.1f%%\n",
               tam_orig, tam_comp, (1.0-(double)tam_comp/tam_orig)*100.0);
        int tam_dec;
        unsigned char *dec = lz77_descomprimir(comp, tam_comp, &tam_dec);
        int ok = (tam_dec==tam_orig) && (memcmp(texto,dec,tam_orig)==0);
        printf("  Lossless: %s\n\n", ok ? "✅ SIM" : "❌ NÃO (ERRO!)");
        free(comp); free(dec);
    }

    // Teste 2: Padrão repetitivo longo
    printf("--- Teste 2: Padrão [10,20,30,40,50] × 200 (1000 bytes) ---\n");
    {
        unsigned char dados[1000];
        unsigned char padrao[] = {10, 20, 30, 40, 50};
        for (int i = 0; i < 1000; i++) dados[i] = padrao[i % 5];
        int tam_orig = 1000;
        int tam_comp;
        unsigned char *comp = lz77_comprimir(dados, tam_orig, &tam_comp);
        printf("  Original: %d bytes | Comprimido: %d bytes | Compressão: %.1f%%\n",
               tam_orig, tam_comp, (1.0-(double)tam_comp/tam_orig)*100.0);
        int tam_dec;
        unsigned char *dec = lz77_descomprimir(comp, tam_comp, &tam_dec);
        int ok = (tam_dec==tam_orig) && (memcmp(dados,dec,tam_orig)==0);
        printf("  Lossless: %s\n\n", ok ? "✅ SIM" : "❌ NÃO (ERRO!)");
        free(comp); free(dec);
    }

    // Teste 3: Dados aleatórios (pior caso)
    printf("--- Teste 3: 500 bytes pseudo-aleatórios (pior caso) ---\n");
    {
        unsigned char dados[500];
        unsigned int seed = 12345;
        for (int i = 0; i < 500; i++) {
            seed = seed * 1103515245 + 12345;
            dados[i] = (unsigned char)((seed >> 16) & 0xFF);
        }
        int tam_orig = 500;
        int tam_comp;
        unsigned char *comp = lz77_comprimir(dados, tam_orig, &tam_comp);
        printf("  Original: %d bytes | Comprimido: %d bytes | %.1f%% %s\n",
               tam_orig, tam_comp, (1.0-(double)tam_comp/tam_orig)*100.0,
               tam_comp >= tam_orig ? "(EXPANDIU — esperado!)" : "");
        int tam_dec;
        unsigned char *dec = lz77_descomprimir(comp, tam_comp, &tam_dec);
        int ok = (tam_dec==tam_orig) && (memcmp(dados,dec,tam_orig)==0);
        printf("  Lossless: %s\n\n", ok ? "✅ SIM" : "❌ NÃO (ERRO!)");
        free(comp); free(dec);
    }

    // Teste 4: Texto longo em português
    printf("--- Teste 4: Texto longo em português ---\n");
    {
        char *texto =
            "O rato roeu a roupa do rei de Roma. "
            "O rato roeu a roupa do rei de Roma. "
            "A rainha com raiva resolveu remendar. "
            "A rainha com raiva resolveu remendar. "
            "O rato roeu a roupa do rei de Roma. "
            "O rato roeu a roupa do rei de Roma. "
            "A rainha com raiva resolveu remendar. "
            "A rainha com raiva resolveu remendar. "
            "Pedro Paulo Pereira Pinto pintou paredes. "
            "Pedro Paulo Pereira Pinto pintou paredes. "
            "Pintou paredes com primor e perfeição. "
            "Pintou paredes com primor e perfeição. ";
        int tam_orig = strlen(texto);
        int tam_comp;
        unsigned char *comp = lz77_comprimir((unsigned char *)texto, tam_orig, &tam_comp);
        printf("  Original: %d bytes | Comprimido: %d bytes | Compressão: %.1f%%\n",
               tam_orig, tam_comp, (1.0-(double)tam_comp/tam_orig)*100.0);
        int tam_dec;
        unsigned char *dec = lz77_descomprimir(comp, tam_comp, &tam_dec);
        int ok = (tam_dec==tam_orig) && (memcmp(texto,dec,tam_orig)==0);
        printf("  Lossless: %s\n\n", ok ? "✅ SIM" : "❌ NÃO (ERRO!)");
        free(comp); free(dec);
    }

    // Teste 5: Melhor caso absoluto
    printf("--- Teste 5: 10000 bytes todos iguais (melhor caso) ---\n");
    {
        unsigned char dados[10000];
        memset(dados, 0xAA, 10000);
        int tam_orig = 10000;
        int tam_comp;
        unsigned char *comp = lz77_comprimir(dados, tam_orig, &tam_comp);
        printf("  Original: %d bytes | Comprimido: %d bytes | Compressão: %.1f%%\n",
               tam_orig, tam_comp, (1.0-(double)tam_comp/tam_orig)*100.0);
        int tam_dec;
        unsigned char *dec = lz77_descomprimir(comp, tam_comp, &tam_dec);
        int ok = (tam_dec==tam_orig) && (memcmp(dados,dec,tam_orig)==0);
        printf("  Lossless: %s\n\n", ok ? "✅ SIM" : "❌ NÃO (ERRO!)");
        free(comp); free(dec);
    }

    // Teste 6: Ida e volta pelo disco
    printf("--- Teste 6: Ida e volta pelo disco ---\n");
    {
        char *conteudo =
            "Lorem ipsum dolor sit amet, consectetur adipiscing elit. "
            "Sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. "
            "Lorem ipsum dolor sit amet, consectetur adipiscing elit. "
            "Sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. ";
        int tam_orig = strlen(conteudo);
        escrever_arquivo("teste_original.txt", (unsigned char *)conteudo, tam_orig);
        int tam_comp;
        unsigned char *comp = lz77_comprimir((unsigned char *)conteudo, tam_orig, &tam_comp);
        escrever_arquivo("teste_original.txt.lz77", comp, tam_comp);
        int tam_lido;
        unsigned char *lido = ler_arquivo("teste_original.txt.lz77", &tam_lido);
        int tam_dec;
        unsigned char *dec = lz77_descomprimir(lido, tam_lido, &tam_dec);
        escrever_arquivo("teste_restaurado.txt", dec, tam_dec);
        int tam_rest;
        unsigned char *rest = ler_arquivo("teste_restaurado.txt", &tam_rest);
        int ok = (tam_rest==tam_orig) && (memcmp(conteudo,rest,tam_orig)==0);
        printf("  Original: %d bytes → Comprimido: %d bytes → Restaurado: %d bytes\n",
               tam_orig, tam_comp, tam_rest);
        printf("  Compressão: %.1f%% | Ida e volta: %s\n\n",
               (1.0-(double)tam_comp/tam_orig)*100.0,
               ok ? "✅ PERFEITO" : "❌ ERRO!");
        free(comp); free(lido); free(dec); free(rest);
    }
}

// ============================================================
// MAIN — Interface de linha de comando
// ============================================================

int main(int argc, char *argv[]) {
    if (argc < 2) {
        printf("=== LZ77 Compressor/Descompressor Completo ===\n\n");
        printf("Uso:\n");
        printf("  %s comprimir    <arquivo> <arquivo.lz77>\n", argv[0]);
        printf("  %s descomprimir <arquivo.lz77> <arquivo>\n", argv[0]);
        printf("  %s testar\n\n", argv[0]);
        printf("Exemplo:\n");
        printf("  %s comprimir    meuarquivo.txt meuarquivo.txt.lz77\n", argv[0]);
        printf("  %s descomprimir meuarquivo.txt.lz77 meuarquivo_restaurado.txt\n", argv[0]);
        return 1;
    }

    if (strcmp(argv[1], "testar") == 0) {
        rodar_testes();
        return 0;
    }

    if (strcmp(argv[1], "comprimir") == 0) {
        if (argc < 4) {
            printf("Uso: %s comprimir <entrada> <saida.lz77>\n", argv[0]);
            return 1;
        }
        printf("Comprimindo '%s' → '%s'...\n", argv[2], argv[3]);
        int tam_ent;
        unsigned char *ent = ler_arquivo(argv[2], &tam_ent);
        if (!ent) return 1;
        int tam_sai;
        unsigned char *sai = lz77_comprimir(ent, tam_ent, &tam_sai);
        escrever_arquivo(argv[3], sai, tam_sai);
        printf("  Original: %d bytes → Comprimido: %d bytes (%.1f%%)\n",
               tam_ent, tam_sai, (1.0-(double)tam_sai/tam_ent)*100.0);
        free(ent); free(sai);
        return 0;
    }

    if (strcmp(argv[1], "descomprimir") == 0) {
        if (argc < 4) {
            printf("Uso: %s descomprimir <entrada.lz77> <saida>\n", argv[0]);
            return 1;
        }
        printf("Descomprimindo '%s' → '%s'...\n", argv[2], argv[3]);
        int tam_ent;
        unsigned char *ent = ler_arquivo(argv[2], &tam_ent);
        if (!ent) return 1;
        int tam_sai;
        unsigned char *sai = lz77_descomprimir(ent, tam_ent, &tam_sai);
        if (!sai) return 1;
        escrever_arquivo(argv[3], sai, tam_sai);
        printf("  Comprimido: %d bytes → Restaurado: %d bytes\n", tam_ent, tam_sai);
        free(ent); free(sai);
        return 0;
    }

    printf("Comando desconhecido: '%s'\n", argv[1]);
    return 1;
}

cd ~/lz77-complete-tes
gcc main.c -o lz77 -O2

# Rodar os 6 testes internos
./lz77 testar

# Comprimir qualquer arquivo
./lz77 comprimir meuarquivo.txt meuarquivo.txt.lz77

# Descomprimir de volta
./lz77 descomprimir meuarquivo.txt.lz77 meuarquivo_restaurado.txt

# Verificar que o arquivo restaurado é idêntico ao original
diff meuarquivo.txt meuarquivo_restaurado.txt

=== TESTES INTERNOS DO LZ77 COMPLETO ===

--- Teste 1: ABRACADABRA_ABRACADABRA ---
  Estatísticas: 8 literais, 2 referências
  Original: 23 bytes | Comprimido: 27 bytes | Compressão: -17.4%
  Lossless: ✅ SIM

--- Teste 2: Padrão [10,20,30,40,50] × 200 (1000 bytes) ---
  Estatísticas: 5 literais, 4 referências
  Original: 1000 bytes | Comprimido: 30 bytes | Compressão: 97.0%
  Lossless: ✅ SIM

--- Teste 3: 500 bytes pseudo-aleatórios (pior caso) ---
  Estatísticas: 500 literais, 0 referências
  Original: 500 bytes | Comprimido: 575 bytes | -15.0% (EXPANDIU — esperado!)
  Lossless: ✅ SIM

--- Teste 4: Texto longo em português ---
  Estatísticas: 100 literais, 17 referências
  Original: 462 bytes | Comprimido: 176 bytes | Compressão: 61.9%
  Lossless: ✅ SIM

--- Teste 5: 10000 bytes todos iguais (melhor caso) ---
  Estatísticas: 1 literais, 39 referências
  Original: 10000 bytes | Comprimido: 131 bytes | Compressão: 98.7%
  Lossless: ✅ SIM

--- Teste 6: Ida e volta pelo disco ---
  Original: 384 bytes → Comprimido: 221 bytes → Restaurado: 384 bytes
  Compressão: 42.4% | Ida e volta: ✅ PERFEITO