Compressor RLE em Zig — Tutorial Passo a Passo
Neste tutorial, vamos implementar Run-Length Encoding (RLE), um dos algoritmos de compressão mais simples e intuitivos. RLE funciona substituindo sequências de bytes repetidos por um par (contagem, byte). Apesar de simples, é usado em formatos reais como BMP, TIFF e PCX.
O Que Vamos Construir
Nosso compressor vai:
- Codificar dados usando RLE (compressão)
- Decodificar dados RLE (descompressão)
- Calcular taxa de compressão
- Processar tanto texto quanto arquivos binários
- Exibir estatísticas detalhadas
- Verificar integridade (roundtrip: comprimir -> descomprimir = original)
Pré-requisitos
- Zig 0.13+ instalado (guia de instalação)
- Conceitos básicos de manipulação de bytes em Zig
Passo 1: Estrutura do Projeto
mkdir compressor-rle
cd compressor-rle
zig init
Passo 2: Algoritmo RLE
const std = @import("std");
const mem = std.mem;
const io = std.io;
const fs = std.fs;
const Allocator = std.mem.Allocator;
const ArrayList = std.ArrayList;
/// Formato RLE:
/// Para cada sequência de bytes iguais consecutivos:
/// - Se contagem >= 2: [MARCADOR] [contagem-2] [byte]
/// - Se contagem == 1 e byte != MARCADOR: [byte]
/// - Se contagem == 1 e byte == MARCADOR: [MARCADOR] [0] [MARCADOR]
///
/// O MARCADOR (0xFF por padrão) indica que os próximos 2 bytes
/// são uma contagem e um valor. Isso permite que bytes não-repetidos
/// passem sem overhead.
const MARCADOR: u8 = 0xFF;
const MAX_RUN: u8 = 255;
/// Resultado da compressão com estatísticas.
const ResultadoCompressao = struct {
dados: []const u8,
tamanho_original: usize,
tamanho_comprimido: usize,
num_runs: usize,
maior_run: usize,
pub fn taxaCompressao(self: *const ResultadoCompressao) f64 {
if (self.tamanho_original == 0) return 0.0;
return (1.0 - @as(f64, @floatFromInt(self.tamanho_comprimido)) /
@as(f64, @floatFromInt(self.tamanho_original))) * 100.0;
}
};
/// Comprime dados usando RLE.
fn comprimir(allocator: Allocator, dados: []const u8) !ResultadoCompressao {
var saida = ArrayList(u8).init(allocator);
errdefer saida.deinit();
var num_runs: usize = 0;
var maior_run: usize = 0;
var i: usize = 0;
while (i < dados.len) {
const byte_atual = dados[i];
var contagem: usize = 1;
// Conta bytes consecutivos iguais
while (i + contagem < dados.len and
dados[i + contagem] == byte_atual and
contagem < MAX_RUN + 2)
{
contagem += 1;
}
num_runs += 1;
if (contagem > maior_run) maior_run = contagem;
if (contagem >= 2) {
// Run codificado: MARCADOR + (contagem-2) + byte
try saida.append(MARCADOR);
try saida.append(@intCast(contagem - 2));
try saida.append(byte_atual);
} else if (byte_atual == MARCADOR) {
// Byte literal que é igual ao marcador: escape
try saida.append(MARCADOR);
try saida.append(0);
try saida.append(MARCADOR);
} else {
// Byte literal
try saida.append(byte_atual);
}
i += contagem;
}
const comprimido = try saida.toOwnedSlice();
return ResultadoCompressao{
.dados = comprimido,
.tamanho_original = dados.len,
.tamanho_comprimido = comprimido.len,
.num_runs = num_runs,
.maior_run = maior_run,
};
}
/// Descomprime dados RLE.
fn descomprimir(allocator: Allocator, dados: []const u8) ![]const u8 {
var saida = ArrayList(u8).init(allocator);
errdefer saida.deinit();
var i: usize = 0;
while (i < dados.len) {
if (dados[i] == MARCADOR) {
// Sequência codificada
if (i + 2 >= dados.len) return error.DadosCorruptos;
const contagem: usize = @as(usize, dados[i + 1]) + 2;
const byte_valor = dados[i + 2];
try saida.appendNTimes(byte_valor, contagem);
i += 3;
} else {
// Byte literal
try saida.append(dados[i]);
i += 1;
}
}
return saida.toOwnedSlice();
}
Decisão de design: Usamos um byte marcador (0xFF) para distinguir runs codificados de bytes literais. Isso é mais eficiente que a abordagem ingênua de codificar todos os bytes como pares, pois bytes não-repetidos ocupam apenas 1 byte em vez de 2.
Passo 3: Verificação de Integridade
/// Verifica se comprimir e descomprimir produz o resultado original.
fn verificarIntegridade(allocator: Allocator, dados: []const u8) !bool {
const resultado = try comprimir(allocator, dados);
defer allocator.free(resultado.dados);
const descomprimido = try descomprimir(allocator, resultado.dados);
defer allocator.free(descomprimido);
return mem.eql(u8, dados, descomprimido);
}
/// Analisa o conteúdo para estimar compressibilidade.
fn analisarCompressibilidade(dados: []const u8) struct { runs: usize, media_run: f64, entropia: f64 } {
if (dados.len == 0) return .{ .runs = 0, .media_run = 0, .entropia = 0 };
var runs: usize = 1;
var i: usize = 1;
while (i < dados.len) : (i += 1) {
if (dados[i] != dados[i - 1]) runs += 1;
}
// Calcular entropia
var contagem = [_]u64{0} ** 256;
for (dados) |b| contagem[b] += 1;
var entropia: f64 = 0;
const total: f64 = @floatFromInt(dados.len);
for (contagem) |c| {
if (c > 0) {
const p: f64 = @as(f64, @floatFromInt(c)) / total;
entropia -= p * @log2(p);
}
}
return .{
.runs = runs,
.media_run = @as(f64, @floatFromInt(dados.len)) / @as(f64, @floatFromInt(runs)),
.entropia = entropia,
};
}
Passo 4: Interface CLI
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
const stdout = io.getStdOut().writer();
const stdin = io.getStdIn().reader();
try stdout.print(
\\
\\ ==========================================
\\ COMPRESSOR RLE - Zig
\\ ==========================================
\\
, .{});
var buf: [4096]u8 = undefined;
while (true) {
try stdout.print(
\\
\\ [1] Comprimir texto
\\ [2] Comprimir arquivo
\\ [3] Descomprimir arquivo
\\ [4] Verificar integridade
\\ [5] Demo com exemplos
\\ [6] Sair
\\
\\ Opcao:
, .{});
const opcao_raw = stdin.readUntilDelimiterOrEof(&buf, '\n') catch continue orelse break;
const opcao = mem.trim(u8, opcao_raw, " \t\r\n");
if (mem.eql(u8, opcao, "6")) break;
if (mem.eql(u8, opcao, "5")) {
// Demo com diferentes tipos de dados
const exemplos = [_]struct { nome: []const u8, dados: []const u8 }{
.{ .nome = "Texto repetitivo", .dados = "AAAAAABBBCCCCCCCCDDDDDD" },
.{ .nome = "Texto normal", .dados = "Zig e uma linguagem de programacao" },
.{ .nome = "Muito repetitivo", .dados = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" },
.{ .nome = "Sem repeticao", .dados = "abcdefghijklmnopqrstuvwxyz" },
};
for (exemplos) |ex| {
const resultado = try comprimir(allocator, ex.dados);
defer allocator.free(resultado.dados);
const analise = analisarCompressibilidade(ex.dados);
try stdout.print(
\\
\\ {s}:
\\ Original: {d} bytes | Comprimido: {d} bytes
\\ Taxa: {d:.1}% | Runs: {d} | Media run: {d:.1}
\\ Entropia: {d:.2} bits/byte
, .{
ex.nome,
resultado.tamanho_original, resultado.tamanho_comprimido,
resultado.taxaCompressao(), analise.runs, analise.media_run,
analise.entropia,
});
}
try stdout.print("\n", .{});
continue;
}
if (mem.eql(u8, opcao, "1")) {
try stdout.print("\n Texto: ", .{});
const texto_raw = stdin.readUntilDelimiterOrEof(&buf, '\n') catch continue orelse continue;
const texto = mem.trim(u8, texto_raw, "\r\n");
const resultado = try comprimir(allocator, texto);
defer allocator.free(resultado.dados);
try stdout.print(
\\
\\ Original: {d} bytes
\\ Comprimido: {d} bytes
\\ Taxa: {d:.1}%
\\ Runs: {d}
\\ Maior run: {d}
, .{
resultado.tamanho_original, resultado.tamanho_comprimido,
resultado.taxaCompressao(), resultado.num_runs, resultado.maior_run,
});
// Verificar integridade
const ok = try verificarIntegridade(allocator, texto);
try stdout.print("\n Integridade: {s}\n", .{if (ok) "OK" else "FALHA"});
} else if (mem.eql(u8, opcao, "2")) {
try stdout.print("\n Arquivo de entrada: ", .{});
const path_raw = stdin.readUntilDelimiterOrEof(&buf, '\n') catch continue orelse continue;
const path = mem.trim(u8, path_raw, " \t\r\n");
const dados = fs.cwd().readFileAlloc(allocator, path, 10 * 1024 * 1024) catch |err| {
try stdout.print(" Erro: {any}\n", .{err});
continue;
};
defer allocator.free(dados);
const resultado = try comprimir(allocator, dados);
defer allocator.free(resultado.dados);
// Salvar
var out_buf: [512]u8 = undefined;
const out_path = std.fmt.bufPrint(&out_buf, "{s}.rle", .{path}) catch continue;
const out_file = fs.cwd().createFile(out_path, .{}) catch |err| {
try stdout.print(" Erro ao criar: {any}\n", .{err});
continue;
};
defer out_file.close();
try out_file.writeAll(resultado.dados);
try stdout.print(
\\
\\ Salvo em: {s}
\\ Original: {d} bytes
\\ Comprimido: {d} bytes
\\ Taxa: {d:.1}%
\\
, .{ out_path, resultado.tamanho_original, resultado.tamanho_comprimido, resultado.taxaCompressao() });
}
}
try stdout.print("\n Ate logo!\n", .{});
}
Testes
test "comprimir e descomprimir - roundtrip" {
const allocator = std.testing.allocator;
const dados = "AAABBBCCC";
const ok = try verificarIntegridade(allocator, dados);
try std.testing.expect(ok);
}
test "comprimir dados repetitivos" {
const allocator = std.testing.allocator;
const resultado = try comprimir(allocator, "AAAAAAAAAA"); // 10 A's
defer allocator.free(resultado.dados);
try std.testing.expect(resultado.tamanho_comprimido < resultado.tamanho_original);
}
test "comprimir dados sem repeticao" {
const allocator = std.testing.allocator;
const resultado = try comprimir(allocator, "abcdef");
defer allocator.free(resultado.dados);
// Sem repetição, pode até aumentar levemente
try std.testing.expect(resultado.dados.len > 0);
}
test "roundtrip com byte marcador" {
const allocator = std.testing.allocator;
const dados = &[_]u8{ 0xFF, 0xFF, 0xFF, 0x00, 0xFF };
const ok = try verificarIntegridade(allocator, dados);
try std.testing.expect(ok);
}
test "roundtrip vazio" {
const allocator = std.testing.allocator;
const ok = try verificarIntegridade(allocator, "");
try std.testing.expect(ok);
}
test "analise compressibilidade" {
const analise = analisarCompressibilidade("AAABBC");
try std.testing.expectEqual(@as(usize, 3), analise.runs);
}
Compilando e Executando
zig build test
zig build run
Conceitos Aprendidos
- Algoritmo Run-Length Encoding
- Esquema de escape para bytes especiais
- Cálculo de taxa de compressão e entropia
- Verificação de integridade por roundtrip
ArrayListpara buffers de saída dinâmicos- Processamento de dados binários em Zig
Próximos Passos
- Aprenda sobre alocadores de memória para otimizar a compressão
- Explore outros algoritmos como LZ77 e Huffman
- Construa o próximo projeto: Servidor HTTP de Arquivos