Codificação de entropia: o primeiro arquivo comprimido 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 terceiro artigo da nossa série de ~25, e ele é A LINHA DE CHEGADA DA FASE 3. 🏁

É neste artigo que tudo o que a gente construiu ao longo de vários capítulos finalmente se transforma em bytes reais que poderiam ser gravados num arquivo, então se prepara, porque a recompensa vem no final. 🎁

Mas antes, deixa eu te situar na jornada até aqui:

Fase 1 (artigos 1-3): cores, RGB, YCbCr e Chroma Subsampling.
Fase 2 (artigos 4-7): fundamentos de compressão — entropia, RLE, Huffman e LZ77.
Fase 3 (artigos 8-13): blocos 8×8, DCT, quantização, zig-zag + RLE, e agora a codificação de entropia final. 🌊

No artigo anterior, a gente terminou com o bloco reduzido a um coeficiente DC (-26) e uma sequência de pares RLE dos coeficientes AC, como por exemplo:

DC = -26
AC (pares RLE): (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)

Entretanto, como eu bem te avisei, esses pares ainda estão totalmente crus.

Tanto é que o run e o valor ainda ocupam bits fixos, mas fica tranquilo que hoje a gente dá o golpe final e transforma isso em bits de verdade, com três sub-etapas que trabalham juntas:

🔗 DC diferencial (DPCM): será usado para codificar a diferença entre blocos vizinhos.
🔢 Categoria + amplitude: será usado para a codificação de inteiros de tamanho variável (o truque mais elegante do JPEG).
🌳 Huffman: o velho conhecido do artigo 6, dando o acabamento final.

Sendo assim, pega um café bem forte ☕, porque este é o artigo mais denso de código da série até agora. Bora! 🚀

Sub-etapa 1: DC diferencial (DPCM)

Vamos começar pelo coeficiente DC, que recebe um tratamento especial.

Lembra que o DC representa o brilho médio do bloco? 💡

Pois é, e aqui tem uma observação genial: blocos vizinhos numa imagem tendem a ter brilhos parecidos, ou seja, o céu de um bloco é parecido com o céu do bloco do lado, a pele de um rosto num bloco é parecida com a do bloco vizinho.

Então, em vez de guardar o valor absoluto do DC de cada bloco, o JPEG guarda apenas a diferença em relação ao DC do bloco anterior, essa técnica se chama DPCM (Differential Pulse-Code Modulation).

DIFF = DC_atual - DC_anterior

E por que isso ajuda?

Porque as diferenças são números relativamente pequenos (perto de zero), e números pequenos comprimem muito melhor. Veja um exemplo com uma sequência de blocos de um céu:

DC dos blocos:    -26   -24   -25   -27   -26   -28
DIFF (DPCM):      -26    +2    -1    -2    +1    -2
                   ↑
            (o primeiro usa DC_anterior = 0)

Olha a diferença! 😲

Os valores absolutos (-26, -24, -25...) viraram diferenças minúsculas (+2, -1, -2...), essas diferenças ocupam pouquíssimos bits. É de graça, só de mudar a forma de representar.

No nosso caso, temos um único bloco, então o DC_anterior é 0 e o DIFF = -26 - 0 = -26. Mas o mecanismo é justamente esse. 🎯

Sub-etapa 2: categoria + amplitude

Agora vem o truque mais elegante do JPEG, e o coração deste artigo. Preste atenção aqui...

Temos vários números pra codificar: o DIFF do DC, e os valores dos pares AC, se você perceber, eles variam bastante de tamanho, onde uns são pequenos (1, -2), outros maiores (-26, 5).

Com isso você pode estar se perguntando: "Como codificar números de tamanhos tão diferentes de forma compacta?"

A solução do JPEG é dividir cada número em duas partes distintas:

A categoria (também chamada de SIZE): quantos bits são necessários pra representar aquele número.
A amplitude: os bits que dizem qual número específico é, dentro daquela categoria.

A categoria é simplesmente o número de bits de |valor|, por exemplo:

Categoria │ Faixa de valores
──────────┼──────────────────────────────
    0     │ 0
    1     │ -1, 1
    2     │ -3, -2, 2, 3
    3     │ -7 .. -4, 4 .. 7
    4     │ -15 .. -8, 8 .. 15
    5     │ -31 .. -16, 16 .. 31
    6     │ -63 .. -32, 32 .. 63
    7     │ -127 .. -64, 64 .. 127
    8     │ -255 .. -128, 128 .. 255
   ...    │ ...

Repara o padrão: a categoria S agrupa todos os números que precisam de exatamente S bits. Cada categoria tem 2^S valores possíveis (metade negativos, metade positivos).

Mas como será que a amplitude codifica o valor?

Dentro de uma categoria, a amplitude (com S bits) diz qual valor é por meio da seguinte regra:

➕ Valor positivo: escreve o valor direto em binário.
➖ Valor negativo: escreve (valor - 1) em binário, que na prática é o complemento dos bits do valor positivo correspondente.

Vamos ver na categoria 3 (valores de -7 a -4 e 4 a 7), que usam 3 bits:

Valor │ Amplitude (3 bits)
──────┼───────────────────
  -7  │ 000
  -6  │ 001
  -5  │ 010
  -4  │ 011
   4  │ 100
   5  │ 101
   6  │ 110
   7  │ 111

Sacou a elegância? 😍

Os positivos ocupam a metade de cima dos códigos (bit mais alto = 1), e os negativos a metade de baixo (bit mais alto = 0). Isso deixa o decoder saber na hora o sinal, só de olhar o primeiro bit.

Exemplos práticos com os nossos valores:

DIFF = -26 → categoria 5 (precisa de 5 bits)
              amplitude = -26 + 31 = 5 = "00101"

valor = 5  → categoria 3
              amplitude = 5 = "101"

valor = -3 → categoria 2
              amplitude = -3 + 3 = 0 = "00"

valor = 1  → categoria 1
              amplitude = 1 = "1"

Sub-etapa 3: o símbolo AC e o Huffman

Agora juntamos tudo numa única estrutura, onde cada coeficiente AC vira a seguinte formula matemática:

[ símbolo Huffman: (RUN, SIZE) ]  +  [ amplitude: SIZE bits ]

Onde:

RUN = quantos zeros vieram antes (do RLE do artigo 11), de 0 a 15.
SIZE = a categoria do valor.

O par (RUN, SIZE) é empacotado num único byte: (RUN << 4) | SIZE. E esse byte é o símbolo que vai pra tabela de Huffman.

Os dois símbolos especiais que já conhecemos entram aqui também:

EOB = (0, 0) = byte 0x00. 🚩
ZRL = (15, 0) = byte 0xF0. 🏃

E o Huffman?

Aqui a gente reencontra o velho amigo do artigo 6! A ideia é a mesma: símbolos que aparecem muito (tipo (0,1), um coeficiente pequeno sem zeros antes) ganham códigos curtos; símbolos raros ganham códigos longos. Isso minimiza o total de bits.

A diferença é que o JPEG não calcula uma tabela Huffman nova pra cada imagem (isso daria trabalho e exigiria transmitir a tabela). Em vez disso, ele usa tabelas padrão pré-definidas (as do Anexo K da especificação), que tanto o encoder quanto o decoder já conhecem.

Elas são otimizadas com base em estatísticas de imagens típicas.

💡 Curiosidade: essas tabelas padrão são definidas de um jeito compacto: dois arrays chamados BITS (quantos códigos existem de cada comprimento, de 1 a 16 bits) e HUFFVAL (quais símbolos, em ordem). A partir deles, você gera os códigos canônicos com um algoritmo simples. Mais tarde vamos implementar exatamente isso no código! 🤓

Deixo abaixo alguns exemplos de códigos padrão para você entender como fica a tabela de luminância:

Símbolo         │ Código Huffman  │ Bits
────────────────┼─────────────────┼─────
DC categoria 5  │ 110             │  3
AC (0,1) = 0x01 │ 00              │  2
AC (0,2) = 0x02 │ 01              │  2
AC EOB   = 0x00 │ 1010            │  4
AC (1,2) = 0x12 │ 11011           │  5
AC ZRL   = 0xF0 │ 11111111001     │ 11

Montando o bitstream do nosso bloco

Vamos codificar nosso bloco de ponta a ponta, bit por bit. Começando pelo DC:

DC: DIFF = -26
    categoria = 5
    Huffman(DC, cat 5) = "110"
    amplitude(-26, 5) = "00101"
    → bits do DC: 110 00101   (8 bits)

Agora vamos montar os primeiros pares AC:

(0,-3): SIZE=2, símbolo 0x02, Huffman="01",    amp(-3,2)="00"    → 01 00
(1,-3): SIZE=2, símbolo 0x12, Huffman="11011", amp(-3,2)="00"    → 11011 00
(0,-2): SIZE=2, símbolo 0x02, Huffman="01",    amp(-2,2)="01"    → 01 01
...
(5,-1): SIZE=1, símbolo 0x51, Huffman="1111110", amp(-1,1)="0"   → 1111110 0
(0,-1): SIZE=1, símbolo 0x01, Huffman="00",    amp(-1,1)="0"     → 00 0
EOB:    símbolo 0x00, Huffman="1010"                             → 1010

Fazendo isso pra todos os símbolos e empacotando os bits em bytes, temos o resultado final.

E aqui vem a recompensa. 🥁

O código completo em C

O programa que você irá construir junto comigo abaixo, faz o pipeline de entropia inteiro: constrói as tabelas Huffman padrão do JPEG, codifica DC (DPCM) + AC (categoria/amplitude/Huffman) num bitstream de bytes reais, e depois decodifica de volta pra provar que o roundtrip é perfeito.

Para isso, recomendo que você crie uma pasta chamada codec-entropy-test, com um arquivo chamado main.c, com o seguinte conteúdo dentro dele:

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

// ============================================================
// TABELAS DE HUFFMAN PADRÃO DO JPEG (LUMINÂNCIA, Anexo K)
// ============================================================
//
// Definidas de forma compacta:
//   BITS[L]   = quantos códigos têm comprimento L (1..16)
//   HUFFVAL[] = os símbolos, na ordem de atribuição dos códigos

const int BITS_DC[17] = {0, 0,1,5,1,1,1,1,1,1,0,0,0,0,0,0,0};
const unsigned char HUFFVAL_DC[12] = {0,1,2,3,4,5,6,7,8,9,10,11};

const int BITS_AC[17] = {0, 0,2,1,3,3,2,4,3,5,5,4,4,0,0,1,125};
const unsigned char HUFFVAL_AC[162] = {
    0x01,0x02,0x03,0x00,0x04,0x11,0x05,0x12,0x21,0x31,0x41,0x06,0x13,0x51,0x61,0x07,
    0x22,0x71,0x14,0x32,0x81,0x91,0xa1,0x08,0x23,0x42,0xb1,0xc1,0x15,0x52,0xd1,0xf0,
    0x24,0x33,0x62,0x72,0x82,0x09,0x0a,0x16,0x17,0x18,0x19,0x1a,0x25,0x26,0x27,0x28,
    0x29,0x2a,0x34,0x35,0x36,0x37,0x38,0x39,0x3a,0x43,0x44,0x45,0x46,0x47,0x48,0x49,
    0x4a,0x53,0x54,0x55,0x56,0x57,0x58,0x59,0x5a,0x63,0x64,0x65,0x66,0x67,0x68,0x69,
    0x6a,0x73,0x74,0x75,0x76,0x77,0x78,0x79,0x7a,0x83,0x84,0x85,0x86,0x87,0x88,0x89,
    0x8a,0x92,0x93,0x94,0x95,0x96,0x97,0x98,0x99,0x9a,0xa2,0xa3,0xa4,0xa5,0xa6,0xa7,
    0xa8,0xa9,0xaa,0xb2,0xb3,0xb4,0xb5,0xb6,0xb7,0xb8,0xb9,0xba,0xc2,0xc3,0xc4,0xc5,
    0xc6,0xc7,0xc8,0xc9,0xca,0xd2,0xd3,0xd4,0xd5,0xd6,0xd7,0xd8,0xd9,0xda,0xe1,0xe2,
    0xe3,0xe4,0xe5,0xe6,0xe7,0xe8,0xe9,0xea,0xf1,0xf2,0xf3,0xf4,0xf5,0xf6,0xf7,0xf8,
    0xf9,0xfa
};

// Tabelas geradas (código e comprimento por símbolo, 0..255)
int dc_code[256], dc_len[256];
int ac_code[256], ac_len[256];

// Gera os códigos canônicos a partir de BITS/HUFFVAL (algoritmo do Anexo C).
void gerar_huffman(const int bits[17], const unsigned char *huffval,
                   int *code, int *len) {
    for (int i = 0; i < 256; i++) { code[i] = 0; len[i] = 0; }
    int codigo = 0, k = 0;
    for (int L = 1; L <= 16; L++) {
        for (int i = 0; i < bits[L]; i++) {
            unsigned char sym = huffval[k++];
            code[sym] = codigo;
            len[sym]  = L;
            codigo++;
        }
        codigo <<= 1;
    }
}

// ============================================================
// CATEGORIA E AMPLITUDE
// ============================================================

// categoria = número de bits para representar |v|
int categoria(int v) {
    if (v == 0) return 0;
    int a = abs(v), s = 0;
    while (a) { s++; a >>= 1; }
    return s;
}

// código de amplitude (s bits) para o valor v
int amplitude(int v, int s) {
    int mask = (1 << s) - 1;
    return (v < 0) ? ((v - 1) & mask) : (v & mask);
}

// ============================================================
// BIT WRITER — empacota bits em bytes
// ============================================================

unsigned char buffer[1024];
int total_bytes = 0;
int bit_atual = 0;
unsigned int acumulador = 0;

void escrever_bits(int valor, int n) {
    for (int i = n - 1; i >= 0; i--) {
        acumulador = (acumulador << 1) | ((valor >> i) & 1);
        bit_atual++;
        if (bit_atual == 8) {
            buffer[total_bytes++] = acumulador;
            acumulador = 0;
            bit_atual = 0;
        }
    }
}

void finalizar_bits(void) {
    if (bit_atual > 0) {
        acumulador <<= (8 - bit_atual);   // completa o último byte com zeros
        buffer[total_bytes++] = acumulador;
        acumulador = 0;
        bit_atual = 0;
    }
}

// ============================================================
// BIT READER — lê bits de volta (para o decoder)
// ============================================================

int leitura_byte = 0, leitura_bit = 0;

int proximo_bit(void) {
    int b = (buffer[leitura_byte] >> (7 - leitura_bit)) & 1;
    leitura_bit++;
    if (leitura_bit == 8) { leitura_bit = 0; leitura_byte++; }
    return b;
}

// Lê um símbolo Huffman: acumula bits até casar com um código conhecido.
int ler_huffman(int *code, int *len) {
    int c = 0, l = 0;
    while (l < 16) {
        c = (c << 1) | proximo_bit();
        l++;
        for (int s = 0; s < 256; s++)
            if (len[s] == l && code[s] == c) return s;
    }
    return -1;
}

// Lê 's' bits de amplitude e reconstrói o valor com sinal.
int ler_amplitude(int s) {
    if (s == 0) return 0;
    int v = 0;
    for (int i = 0; i < s; i++) v = (v << 1) | proximo_bit();
    if (v < (1 << (s - 1))) v += 1 - (1 << s);   // era negativo
    return v;
}

// ============================================================
// MAIN
// ============================================================

int main() {
    gerar_huffman(BITS_DC, HUFFVAL_DC, dc_code, dc_len);
    gerar_huffman(BITS_AC, HUFFVAL_AC, ac_code, ac_len);

    // Dados do bloco do artigo 11 (qualidade 50)
    int DC = -26, DC_anterior = 0;
    int run[] = {0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0};
    int val[] = {-3,-3,-2,-6,2,-4,1,-3,1,1,5,1,2,-1,1,-1,2,-1,-1};
    int n_pares = 19;

    // ---------- ENCODE ----------
    // DC via DPCM
    int diff = DC - DC_anterior;
    int s_dc = categoria(diff);
    escrever_bits(dc_code[s_dc], dc_len[s_dc]);
    if (s_dc > 0) escrever_bits(amplitude(diff, s_dc), s_dc);

    // AC via (run, size) + amplitude
    for (int p = 0; p < n_pares; p++) {
        int s = categoria(val[p]);
        int simbolo = (run[p] << 4) | s;
        escrever_bits(ac_code[simbolo], ac_len[simbolo]);
        if (s > 0) escrever_bits(amplitude(val[p], s), s);
    }
    escrever_bits(ac_code[0x00], ac_len[0x00]);   // EOB
    finalizar_bits();

    printf("Bitstream comprimido (%d bytes):\n  ", total_bytes);
    for (int i = 0; i < total_bytes; i++) printf("%02X ", buffer[i]);
    printf("\n\n");

    // ---------- DECODE (prova de roundtrip) ----------
    int s_dc_dec = ler_huffman(dc_code, dc_len);
    int diff_dec = ler_amplitude(s_dc_dec);
    int DC_dec = DC_anterior + diff_dec;

    int run_dec[64], val_dec[64], n_dec = 0;
    while (1) {
        int simbolo = ler_huffman(ac_code, ac_len);
        if (simbolo == 0x00) break;               // EOB
        int r = simbolo >> 4, s = simbolo & 0xF;
        int v = ler_amplitude(s);
        run_dec[n_dec] = r; val_dec[n_dec] = v; n_dec++;
    }

    int ok = (DC_dec == DC) && (n_dec == n_pares);
    for (int p = 0; p < n_pares && ok; p++)
        if (run_dec[p] != run[p] || val_dec[p] != val[p]) ok = 0;

    printf("DC decodificado: %d (original %d)\n", DC_dec, DC);
    printf("Roundtrip encode -> decode: %s\n", ok ? "IDENTICO!" : "ERRO!");
    printf("Tamanho: %d bytes (contra 64 bytes de coeficientes quantizados brutos)\n",
           total_bytes);

    return 0;
}

Pra compilar e rodar execute as seguintes linhas com o terminal aberto na pasta do projeto:

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

A saída será a seguinte:

Bitstream comprimido (12 bytes):
  C5 4D 8B 0B 46 50 99 4B 02 1B D0 50

DC decodificado: -26 (original -26)
Roundtrip encode -> decode: IDENTICO!
Tamanho: 12 bytes (contra 64 bytes de coeficientes quantizados brutos)

AÍ ESTÁ! 🎉🎉🎉

Doze bytes. Aqueles C5 4D 8B ... são o nosso bloco 8×8 finalmente comprimido em bytes de verdade, o tipo de coisa que iria direto pra dentro de um arquivo .jpg.

E o decoder reconstruiu tudo perfeitamente, provando que a codificação de entropia é 100% lossless. ✅

Repara na conta: 12 bytes contra os 64 bytes dos coeficientes quantizados crus. Uma razão de 5,3:1 só nessa etapa de entropia, e isso é em cima da compressão que a quantização já tinha feito! 💪

O quadro completo: quanto comprimimos no total

Vamos fazer as contas de guardanapo do bloco inteiro, desde o começo:

Pixels originais (8×8, 1 byte cada):         64 bytes
   ↓ DCT (artigo 9) ................. reorganiza (sem mudar tamanho)
   ↓ Quantização (artigo 10) ........ zera 44 dos 64 coeficientes
   ↓ Zig-zag + RLE (artigo 11) ...... 63 AC viram 20 símbolos
   ↓ Entropia: DC+categoria+Huffman . bitstream final
Bytes finais:                                12 bytes

De 64 bytes para 12 bytes: uma razão de ~5,3:1 no total deste bloco.

E lembra que usamos qualidade 50, em áreas mais suaves da imagem (céu, paredes), a razão é muito maior, porque muitos blocos ficam só com o DC e um EOB, comprimindo pra pouquíssimos bytes.

A abordagem do nosso CODEC

Pro nosso CODEC, vamos começar com esse esquema clássico e sólido do JPEG:

DC via DPCM (diferença entre blocos). ✅
Codificação categoria + amplitude. ✅
Símbolos AC (run, size) + Huffman com tabelas padrão. ✅

E o gancho pro futuro, como sempre: lá na Fase 5, no artigo sobre codificação aritmética / ANS (artigo 20), a gente vai substituir esse RLE+Huffman por uma codificação de entropia mais moderna e eficiente.

O JPEG mesmo tem um modo aritmético opcional (raramente usado por questões históricas de patente), e formatos como WebP e AVIF já nascem com entropia avançada. Mas o alicerce é este que acabamos de construir.

Resumo: Fase 3 concluída!

Que jornada! Recapitulando este artigo:

🔗 O DC é codificado por DPCM: guarda-se a diferença para o bloco anterior, não o valor absoluto, diferenças pequenas comprimem melhor.
🔢 O truque de categoria (SIZE) + amplitude representa qualquer número em duas partes: quantos bits ele precisa, e quais são esses bits (com um esquema esperto pro sinal).
🌳 Cada AC vira um símbolo: (run, size) que passa pelo Huffman (tabelas padrão do JPEG, reaproveitando tudo do artigo 6). EOB = 0x00, ZRL = 0xF0.
✅ Todo o processo de entropia é lossless: no nosso bloco, 64 bytes de coeficientes viraram 12 bytes com roundtrip idêntico.
📊 No total da Fase 3, o bloco foi de 64 bytes de pixels a 12 bytes de arquivo, e ainda mais em áreas suaves.

E o mais importante: acabamos de fechar a Fase 3, o coração do CODEC. 🎉

Nós saímos de "pixels numa matriz" e chegamos em "bytes comprimidos que poderiam ser gravados num arquivo", onde todas as peças fundamentais de um CODEC estilo JPEG estão na mesa!

Na fase 4, paramos de trabalhar com blocos isolados, e montamos o NOSSO CODEC DE VERDADE.

Juntaremos o formato de arquivo autoral, o cabeçalho (header), o bitstream completo de uma imagem inteira (com todos os blocos, os três canais YCbCr), e o encoder/decoder end-to-end que abre e salva arquivos reais.

A teoria acabou. Agora é engenharia de formato.

Até a Fase 4! 🚀👋

Codificação de entropia: o primeiro arquivo comprimido de verdade