Zig-zag e RLE: transformando o mar de zeros em bytes de verdade

Zig-zag e RLE: transformando o mar de zeros em bytes de verdade

Olá leitor, seja muito bem vindo de volta a mais uma etapa da nossa jornada aqui no Portal da Micilini! 😊

Este é o décimo segundo artigo da nossa série de ~25, e ele é aquele momento mágico em que a gente para de "brincar com matriz" e começa a transformar tudo em bytes de verdade que vão pro arquivo. 📁✨

Deixa eu te situar na jornada:

No fim do artigo 10, a gente ficou com um bloco quantizado assim, cheio de zeros:

Coeficientes QUANTIZADOS (qualidade 50):
    -26   -3   -6    2    2   -1    0    0
      0   -2   -4    1    1    0    0    0
     -3    1    5   -1   -1    0    0    0
     -3    1    2   -1    0    0    0    0
      1    0    0    0    0    0    0    0
      0    0    0    0    0    0    0    0
      0    0    0    0    0    0    0    0
      0    0    0    0    0    0    0    0

Esses zeros ainda estão ocupando espaço na memória. 🤨

Ter muitos zeros não é o mesmo que comprimir, a gente precisa transformar essa "abundância de zeros" em economia de bytes real.

E é exatamente isso que vamos fazer hoje, com duas técnicas que trabalham em dupla: a varredura em zig-zag e o RLE (Run-Length Encoding).

Pega o café ☕ e bora!

O problema: os zeros estão espalhados em 2D

Olha de novo pro bloco quantizado...

Repara onde estão os zeros: eles se concentram no canto inferior direito, formando um "triângulo" de zeros. Mas eles estão espalhados numa matriz 2D.

Se a gente simplesmente lesse o bloco linha por linha (o que chamamos de raster scan), a sequência ficaria assim:

Raster scan (linha por linha):
-26, -3, -6, 2, 2, -1, 0, 0,  0, -2, -4, 1, 1, 0, 0, 0,  -3, 1, 5, -1, -1, 0, 0, 0, ...

Percebe o problema? 🕵️

Os zeros ficam intercalados com os valores, de modo que toda hora aparece um "0, 0" no meio, depois volta valor, depois zero de novo... Isso é péssimo pro RLE, porque o RLE brilha quando tem longas sequências contíguas do mesmo valor.

A gente precisa de uma forma de ler o bloco que junte todos os zeros no final, numa sequência longa e ininterrupta.

E aí é que entra a genialidade do zig-zag. 💡

A varredura em zig-zag: seguindo as frequências

Lembra do artigo 9, quando aprendemos que a DCT organiza as frequências de um jeito específico?

A varredura em zig-zag percorre o bloco na diagonal, indo do canto superior esquerdo até o inferior direito, seguindo as frequências crescentes.

Ela zigue-zagueia entre as diagonais, e é daí que vem o nome. 🐍

O efeito é lindo: como ela vai das baixas frequências (valores grandes) pras altas (valores quase todos zero), a sequência resultante naturalmente coloca os zeros no final, todos juntinhos! 🎯

A ordem zig-zag oficial do JPEG

O JPEG define uma ordem exata pra essa varredura. Ela mapeia as 64 posições do bloco 8×8 nesta sequência (os números são os índices das posições visitadas, na ordem), vejamos:

Ordem de visita (posição do bloco 8×8):
 0 →  1 →  8 → 16 →  9 →  2 →  3 → 10 →
17 → 24 → 32 → 25 → 18 → 11 →  4 →  5 →
12 → 19 → 26 → 33 → 40 → 48 → 41 → 34 →
27 → 20 → 13 →  6 →  7 → 14 → 21 → 28 →
35 → 42 → 49 → 56 → 57 → 50 → 43 → 36 →
29 → 22 → 15 → 23 → 30 → 37 → 44 → 51 →
58 → 59 → 52 → 45 → 38 → 31 → 39 → 46 →
53 → 60 → 61 → 54 → 47 → 55 → 62 → 63

Traduzindo pra você visualizar o caminho: começa no (0,0), vai pro (0,1) à direita, desce na diagonal pra (1,0), desce mais pra (2,0), sobe na diagonal... e assim vai, sempre zigue-zagueando pelas diagonais. 🐍

Essa tabela é fixa e universal, de tal modo que todo JPEG do mundo usa exatamente essa ordem. No código, ela vira um simples array de 64 índices. 📋

DC e AC no zig-zag

Um detalhe importante da organização: a primeira posição do zig-zag (índice 0) é sempre o coeficiente DC (aquele que representa a média do bloco, lembra do artigo 9?).

As outras 63 posições são os coeficientes AC, ordenados da frequência mais baixa pra mais alta. 

Por que isso importa? Porque o DC e os AC são tratados de formas diferentes na compressão:

Então, na prática: pegamos o zig-zag, separamos o DC (posição 0), e aplicamos RLE nos 63 coeficientes AC.

Aplicando no nosso bloco

Vamos passar o nosso bloco quantizado pela varredura em zig-zag. O resultado está abaixo:

Sequência zig-zag completa:
-26  -3   0  -3  -2  -6   2  -4   1  -3   1   1   5   1   2  -1
  1  -1   2   0   0   0   0   0  -1  -1   0   0   0   0   0   0
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
  0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0

OLHA QUE MARAVILHA! 😍 Compara com o raster scan lá de cima. Agora todos os valores não-zero estão agrupados no começo, e a partir de certo ponto é zero até o fim do bloco, uma sequência longa e ininterrupta de zeros.

E é justamente essa cauda gigante de zeros que o RLE vai devorar.

RLE: comprimindo a cauda de zeros

O RLE (Run-Length Encoding) a gente já viu lá no artigo 5. A ideia base é: em vez de guardar "0, 0, 0, 0, 0", você guarda "cinco zeros".

Mas o RLE do JPEG tem um toque especial. Em vez de codificar valores repetidos genéricos, ele foca em contar os zeros que aparecem antes de cada valor não-zero.

Cada coeficiente AC não-zero vira um par, por exemplo:

(quantidade_de_zeros_antes, valor)

Outro exemplo, se a sequência AC for -3, 0, -3, ..., o RLE fica:

-3    → (0, -3)   // nenhum zero antes, valor -3
0, -3 → (1, -3)   // um zero antes, valor -3

Isso é perfeito pra sequência do zig-zag, porque os zeros isolados no meio viram só um "número de zeros" grudado no próximo valor.

O marcador EOB: a otimização matadora

Agora vem o truque mais esperto de todos. Depois do último coeficiente não-zero, o resto do bloco é tudo zero (aquela cauda gigante). Seria um desperdício codificar par por par até o fim.

Então o JPEG usa um marcador especial chamado EOB (End of Block — fim do bloco). Ele diz isso em um único símbolo:

"A partir daqui, é tudo zero até o fim do bloco. Pode parar." ✋

No formato de pares, o EOB é representado como (0, 0). Quando o decoder encontra ele, sabe que só precisa preencher o resto do bloco com zeros.

Essa é a otimização que faz o JPEG voar em imagens com áreas suaves: um bloco de céu liso pode ter só o DC e um EOB logo em seguida, w o bloco 8×8 inteiro (64 valores!) vira apenas 2 símbolos. 🤯

O marcador ZRL: quando os zeros são muitos

Tem um caso especial: e se aparecer uma sequência de mais de 15 zeros no meio do bloco (não no final)? 🤔

O par (run, valor) só consegue representar até 15 zeros de uma vez (porque o run cabe em 4 bits: 0 a 15).

Pra runs maiores, o JPEG usa o marcador ZRL (Zero Run Length), representado como (15, 0), que significa "16 zeros seguidos, e ainda tem mais coisa depois".

Você emite quantos ZRLs precisar pra "consumir" os zeros em blocos de 16, e depois continua normalmente.

⚠️ Atenção para um detalhe fino: o ZRL é só pra zeros no meio do bloco. Se os zeros estão no final, você usa o EOB (que é mais barato). Nunca gaste ZRLs numa cauda de zeros que poderia ser um único EOB, isso é um erro clássico de implementação! 🐛

Exemplo completo passo a passo

Vamos aplicar o RLE na sequência AC do nosso bloco. Relembrando os 63 coeficientes AC em zig-zag (depois do DC = -26):

-3, 0, -3, -2, -6, 2, -4, 1, -3, 1, 1, 5, 1, 2, -1, 1, -1, 2, [5 zeros], -1, -1, [resto tudo zero]

Agora percorremos, contando zeros antes de cada valor:

-3   → (0, -3)      // 0 zeros antes
0,-3 → (1, -3)      // 1 zero antes
-2   → (0, -2)
-6   → (0, -6)
2    → (0, 2)
-4   → (0, -4)
1    → (0, 1)
-3   → (0, -3)
1    → (0, 1)
1    → (0, 1)
5    → (0, 5)
1    → (0, 1)
2    → (0, 2)
-1   → (0, -1)
1    → (0, 1)
-1   → (0, -1)
2    → (0, 2)
[5 zeros], -1 → (5, -1)   // 5 zeros antes deste -1!
-1   → (0, -1)
[resto tudo zero] → (EOB)  // fim do bloco 🚩

O resultado final:

(0,-3) (1,-3) (0,-2) (0,-6) (0,2) (0,-4) (0,1) (0,-3) (0,1) (0,1)
(0,5) (0,1) (0,2) (0,-1) (0,1) (0,-1) (0,2) (5,-1) (0,-1) (EOB)

 20 símbolos, para representar os 63 coeficientes AC. 🎉

E lembra: 44 daqueles 63 eram zero. Nós os representamos com um único (5,-1) (pros 5 zeros do meio) e um único EOB (pros ~38 zeros do final). 💪  

O código completo em C

Hora de codar! Este programa faz o pipeline completo: varredura em zig-zag, RLE encode (com EOB e ZRL), RLE decode, e a varredura inversa (tudo com verificação de roundtrip).

Cria uma pasta codec-zigzag-test, e dentro dela um main.c:

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

#define BLOCK_SIZE 8

// ============================================================
// A ORDEM ZIG-ZAG OFICIAL DO JPEG
// ============================================================
//
// Cada número é o índice (row-major, 0..63) da posição do
// bloco 8×8 que é visitada naquela ordem. É uma tabela fixa,
// igual em todo JPEG do mundo.

const int ZIGZAG[64] = {
     0,  1,  8, 16,  9,  2,  3, 10,
    17, 24, 32, 25, 18, 11,  4,  5,
    12, 19, 26, 33, 40, 48, 41, 34,
    27, 20, 13,  6,  7, 14, 21, 28,
    35, 42, 49, 56, 57, 50, 43, 36,
    29, 22, 15, 23, 30, 37, 44, 51,
    58, 59, 52, 45, 38, 31, 39, 46,
    53, 60, 61, 54, 47, 55, 62, 63
};

// ============================================================
// VARREDURA ZIG-ZAG (2D -> 1D) E SUA INVERSA (1D -> 2D)
// ============================================================

void zigzag_scan(int bloco[BLOCK_SIZE][BLOCK_SIZE], int saida[64]) {
    for (int i = 0; i < 64; i++) {
        int idx = ZIGZAG[i];
        saida[i] = bloco[idx / 8][idx % 8];
    }
}

void zigzag_inverso(int entrada[64], int bloco[BLOCK_SIZE][BLOCK_SIZE]) {
    for (int i = 0; i < 64; i++) {
        int idx = ZIGZAG[i];
        bloco[idx / 8][idx % 8] = entrada[i];
    }
}

// ============================================================
// RLE ESTILO JPEG
// ============================================================
//
// Cada coeficiente AC não-zero vira um par (run, valor), onde
// 'run' é a quantidade de zeros que vieram antes dele.
//
// Símbolos especiais:
//   EOB = (0, 0)  -> "daqui até o fim é tudo zero"
//   ZRL = (15, 0) -> "16 zeros seguidos, e ainda tem mais"
//
// Importante: zeros no FINAL do bloco viram EOB (barato),
// nunca ZRL. ZRL é só pra runs longos no MEIO do bloco.

typedef struct { int run; int valor; } ParRLE;

int rle_encode(int zz[64], ParRLE pares[]) {
    int n = 0, run = 0;

    // Só os AC (posições 1..63). O DC (posição 0) é tratado à parte.
    for (int i = 1; i < 64; i++) {
        if (zz[i] == 0) {
            run++;
        } else {
            // Se acumulou mais de 15 zeros, emite ZRLs de 16 em 16
            while (run > 15) {
                pares[n].run = 15;
                pares[n].valor = 0;   // ZRL
                n++;
                run -= 16;
            }
            pares[n].run = run;
            pares[n].valor = zz[i];
            n++;
            run = 0;
        }
    }

    // Se sobrou uma cauda de zeros, ela vira um único EOB
    if (run > 0) {
        pares[n].run = 0;
        pares[n].valor = 0;   // EOB
        n++;
    }

    return n;
}

void rle_decode(ParRLE pares[], int n, int zz[64]) {
    for (int i = 1; i < 64; i++) zz[i] = 0;   // começa tudo zero

    int pos = 1;
    for (int p = 0; p < n; p++) {
        // EOB: para de decodificar, resto já é zero
        if (pares[p].run == 0 && pares[p].valor == 0) break;

        // ZRL: pula 16 posições (16 zeros)
        if (pares[p].run == 15 && pares[p].valor == 0) {
            pos += 16;
            continue;
        }

        // Par normal: pula 'run' zeros e escreve o valor
        pos += pares[p].run;
        if (pos < 64) {
            zz[pos] = pares[p].valor;
            pos++;
        }
    }
}

// ============================================================
// MAIN — Pipeline zig-zag + RLE completo
// ============================================================

int main() {
    // Bloco quantizado do artigo 10 (qualidade 50)
    int bloco[BLOCK_SIZE][BLOCK_SIZE] = {
        {-26, -3, -6,  2,  2, -1,  0,  0},
        {  0, -2, -4,  1,  1,  0,  0,  0},
        { -3,  1,  5, -1, -1,  0,  0,  0},
        { -3,  1,  2, -1,  0,  0,  0,  0},
        {  1,  0,  0,  0,  0,  0,  0,  0},
        {  0,  0,  0,  0,  0,  0,  0,  0},
        {  0,  0,  0,  0,  0,  0,  0,  0},
        {  0,  0,  0,  0,  0,  0,  0,  0}
    };

    // 1. Varredura zig-zag
    int zz[64];
    zigzag_scan(bloco, zz);

    printf("Sequencia zig-zag completa:\n");
    for (int i = 0; i < 64; i++) {
        printf("%4d", zz[i]);
        if ((i + 1) % 16 == 0) printf("\n");
    }
    printf("\nDC = %d (posicao 0 do zig-zag)\n\n", zz[0]);

    // 2. RLE dos coeficientes AC
    ParRLE pares[64];
    int n = rle_encode(zz, pares);

    printf("RLE dos AC -> (run, valor):\n");
    for (int p = 0; p < n; p++) {
        if (pares[p].run == 0 && pares[p].valor == 0)
            printf("(EOB)");
        else if (pares[p].run == 15 && pares[p].valor == 0)
            printf("(ZRL) ");
        else
            printf("(%d,%d) ", pares[p].run, pares[p].valor);
    }
    printf("\n\nTotal: %d simbolos RLE (contra 63 coeficientes AC brutos)\n\n", n);

    // 3. Verificação: decodifica e compara com o bloco original
    int zz_rec[64];
    zz_rec[0] = zz[0];              // DC é preservado à parte
    rle_decode(pares, n, zz_rec);

    int bloco_rec[BLOCK_SIZE][BLOCK_SIZE];
    zigzag_inverso(zz_rec, bloco_rec);

    int ok = (memcmp(bloco, bloco_rec, sizeof(bloco)) == 0);
    printf("Roundtrip (zig-zag + RLE -> decode -> bloco): %s\n",
           ok ? "IDENTICO ao original!" : "ERRO!");

    return 0;
}

Pra compilar e rodar:

cd ~/codec-zigzag-test
gcc main.c -o zigzag
./zigzag

A saída deverá ser a seguinte:

Sequencia zig-zag completa:
 -26  -3   0  -3  -2  -6   2  -4   1  -3   1   1   5   1   2  -1
   1  -1   2   0   0   0   0   0  -1  -1   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0

DC = -26 (posicao 0 do zig-zag)

RLE dos AC -> (run, valor):
(0,-3) (1,-3) (0,-2) (0,-6) (0,2) (0,-4) (0,1) (0,-3) (0,1) (0,1) (0,5) (0,1) (0,2) (0,-1) (0,1) (0,-1) (0,2) (5,-1) (0,-1) (EOB)

Total: 20 simbolos RLE (contra 63 coeficientes AC brutos)

Roundtrip (zig-zag + RLE -> decode -> bloco): IDENTICO ao original!

A varredura zig-zag agrupou os zeros no final, o RLE devorou eles com um (5,-1) e um EOB, e o roundtrip provou que não perdemos nada nessa etapa ✅

Isso é importante frisar: o zig-zag e o RLE são operações lossless (sem perda).

A única etapa com perda no nosso CODEC continua sendo a quantização (artigo 10). Aqui a gente só reorganiza e empacota de forma reversível.

Quanto a gente comprimiu (e o que ainda falta)?

Vamos fazer as "contas de guardanapo".

Mas atenção, essa é só parte da mágica. Repara que cada par (run, valor) ainda está "cru", pois o run e o valor ainda ocupam bits fixos. 🤔

O golpe final vem no próximo artigo, com o Huffman (lembra dele do artigo 6?).

Vamos atribuir códigos curtos aos pares mais comuns (tipo (0, 1), que aparece o tempo todo) e códigos longos aos raros. Aí sim os 20 símbolos viram uns pouquíssimos bytes. 🎯

Então o pipeline de codificação de entropia do JPEG é uma escadinha:

Coeficientes quantizados (2D)
   ↓ zig-zag
Sequência 1D com zeros agrupados no final
   ↓ RLE
Pares (run, valor) + EOB
   ↓ Huffman (artigo 12)
Bytes de verdade no arquivo! 📁

E sim, nós estamos no penúltimo degrau. 🪜

A abordagem do nosso CODEC

Pro nosso CODEC, vamos começar exatamente com esse esquema clássico do JPEG:

Mas anota o gancho pro futuro: lá na Fase 5, quando formos falar de codificação aritmética / ANS (artigo 20), a gente vai ver que dá pra substituir o RLE+Huffman por algo ainda mais eficiente.

Formatos modernos como o WebP e o AVIF usam entropia mais avançada que o velho par RLE+Huffman do JPEG.

Mas, como sempre: uma coisa de cada vez. Primeiro dominamos o clássico. 🧗

Resumo

Recapitulando este artigo:

No próximo artigo, vamos fechar o pipeline de codificação de entropia com o Huffman, atribuindo códigos de bits curtos aos símbolos mais frequentes, e finalmente transformando esses pares RLE em bytes reais gravados num arquivo.

Também vamos ver como o DC é codificado com DPCM (a diferença entre blocos vizinhos).

É o artigo onde tudo o que construímos há 11 capítulos finalmente vira um arquivo comprimido de verdade. A linha de chegada da Fase 3 está logo ali!

Prepara o café ☕, porque o próximo é o grande encontro de tudo.

Até o artigo 12!