O decoder: abrindo o .n148i e vendo a imagem de volta

     ENCODER (ida)              │        DECODER (volta)
────────────────────────────────┼────────────────────────────────
1. Ler PPM                      │  1. Ler o cabeçalho .n148i
2. RGB → YCbCr                  │  2. Huffman ao contrário
3. Subsampling 4:2:0            │  3. RLE ao contrário (expandir)
4. Fatiar em blocos 8×8         │  4. Zig-zag ao contrário
5. DCT                          │  5. Dequantização
6. Quantização                  │  6. IDCT (DCT inversa)
7. Zig-zag                      │  7. Remontar os blocos
8. RLE                          │  8. Upsampling do chroma
9. Huffman                      │  9. YCbCr → RGB
10. Escrever o arquivo          │ 10. Salvar o PPM

n148i/
├── src/
│   ├── main.c          ← orquestra tudo
│   ├── header.h/.c     ← o cabeçalho do arquivo
│   ├── ppm.h/.c        ← leitura/escrita PPM, planos, cores
│   ├── tables.h/.c     ← 📋 tabelas compartilhadas (NOVO)
│   ├── dct.h/.c        ← 🌊 DCT e IDCT (NOVO)
│   ├── encoder.h/.c    ← o caminho de ida
│   └── decoder.h/.c    ← 🔓 o caminho de volta (NOVO)
├── images/
│   └── example.ppm
└── output/
    ├── image.n148i     ← o comprimido
    └── decoded.ppm     ← 🎉 a imagem de volta!

#ifndef DCT_H
#define DCT_H

// Builds the cosine tables. Safe to call more than once.
void init_dct_tables(void);

// Forward DCT: 8x8 pixels -> 8x8 frequency coefficients (article 9)
void dct_block(double block[8][8], double coef[8][8]);

// Inverse DCT: 8x8 coefficients -> 8x8 pixels
void idct_block(double coef[8][8], double block[8][8]);

#endif

static void idct_1d(double in[BLOCK_SIZE], double out[BLOCK_SIZE]) {
    for (int p = 0; p < BLOCK_SIZE; p++) {
        double s = 0.0;
        for (int f = 0; f < BLOCK_SIZE; f++)
            s += alpha[f] * in[f] * cos_table[f][p];
        out[p] = 0.5 * s;
    }
}

void idct_block(double coef[8][8], double block[8][8]) {
    double temp[8][8];
    // Columns first, then rows (the mirror image of the forward pass)
    for (int c = 0; c < 8; c++) {
        double a[8], b[8];
        for (int r = 0; r < 8; r++) a[r] = coef[r][c];
        idct_1d(a, b);
        for (int r = 0; r < 8; r++) temp[r][c] = b[r];
    }
    for (int r = 0; r < 8; r++) {
        double a[8], b[8];
        for (int c = 0; c < 8; c++) a[c] = temp[r][c];
        idct_1d(a, b);
        for (int c = 0; c < 8; c++) block[r][c] = b[c] + 128.0;   // undo shift
    }
}

Os códigos têm tamanhos diferentes (de 2 a 16 bits). Como é que eu sei onde um código termina e o próximo começa?

Valor │ Amplitude (3 bits)
──────┼───────────────────
  -7  │ 000    ← negativos ficam na metade de baixo
  -4  │ 011
   4  │ 100    ← positivos na metade de cima
   7  │ 111

static int br_read_amplitude(BitReader *r, int size) {
    if (size == 0) return 0;
    int value = 0;
    for (int i = 0; i < size; i++) value = (value << 1) | br_next_bit(r);
    if (value < (1 << (size - 1))) value += 1 - (1 << size);
    return value;
}

value = 3  (que é 011 em binário)
metade = 1 << 2 = 4
3 < 4? Sim! Era negativo.
correção: 3 + 1 - 8 = -4  ✅

int x = bx*8 + cc;
int y = by*8 + rr;
if (x >= p->width || y >= p->height) continue;   // 👈 descarta o padding

int cx = px / scale_x;    // scale_x é 2 quando há subsampling
int cy = py / scale_y;

R = Y + 1.402 × (Cr - 128)
G = Y - 0.344136 × (Cb - 128) - 0.714136 × (Cr - 128)
B = Y + 1.772 × (Cb - 128)

#ifndef DECODER_H
#define DECODER_H

#include "ppm.h"

// Statistics filled in by decode_image()
typedef struct {
    long blocks_y;
    long blocks_cb;
    long blocks_cr;
    long bytes_consumed;
} DecodeStats;

// Decodes a compressed buffer back into three planes.
// The planes are allocated here; the caller must free them.
int decode_image(unsigned char *buffer, long buffer_size,
                 int width, int height, int quality, int chroma,
                 Plane *y, Plane *cb, Plane *cr, DecodeStats *stats);

// Rebuilds an RGB image from the three planes, upsampling the
// chroma planes back to full resolution when needed.
int merge_channels(Plane *y, Plane *cb, Plane *cr, Image *out);

#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "decoder.h"
#include "tables.h"
#include "dct.h"

// ============================================================
// HUFFMAN TABLES FOR DECODING
// ============================================================
//
// Decoding needs the opposite of encoding. We read bits one at a
// time and ask: "is what I have so far a complete code?"
//
// The trick (from the JPEG spec) is that canonical Huffman codes
// of the same length are CONSECUTIVE numbers. So for each length
// we only need to know the first code (min_code), the last one
// (max_code) and where its symbols start in the values array.
// Then the test is a single comparison per length.

typedef struct {
    int min_code[17];
    int max_code[17];      // -1 means "no codes of this length"
    int val_index[17];
    const unsigned char *values;
} HuffDecodeTable;

static void build_decode_table(const int bits[17], const unsigned char *values,
                               HuffDecodeTable *table) {
    table->values = values;
    int code = 0, k = 0;
    for (int length = 1; length <= 16; length++) {
        if (bits[length] == 0) {
            table->max_code[length] = -1;         // nothing of this length
        } else {
            table->val_index[length] = k;
            table->min_code[length]  = code;
            code += bits[length];
            k    += bits[length];
            table->max_code[length]  = code - 1;
        }
        code <<= 1;
    }
}

// ============================================================
// BIT READER
// ============================================================

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

static void br_init(BitReader *r, unsigned char *buffer, long size) {
    r->buffer = buffer;
    r->size = size;
    r->byte_pos = 0;
    r->bit_pos = 0;
}

static int br_next_bit(BitReader *r) {
    if (r->byte_pos >= r->size) return 0;        // past the end: feed zeros
    int bit = (r->buffer[r->byte_pos] >> (7 - r->bit_pos)) & 1;
    r->bit_pos++;
    if (r->bit_pos == 8) { r->bit_pos = 0; r->byte_pos++; }
    return bit;
}

// Reads one Huffman symbol, one bit at a time.
static int br_read_symbol(BitReader *r, HuffDecodeTable *table) {
    int code = br_next_bit(r);
    for (int length = 1; length <= 16; length++) {
        if (table->max_code[length] >= 0 && code <= table->max_code[length]) {
            int offset = table->val_index[length] + (code - table->min_code[length]);
            return table->values[offset];
        }
        code = (code << 1) | br_next_bit(r);     // not yet: take one more bit
    }
    return -1;                                    // corrupt stream
}

// Reads 'size' amplitude bits and restores the signed value.
// This undoes the trick from article 13: if the top bit is 0 the
// original number was negative.
static int br_read_amplitude(BitReader *r, int size) {
    if (size == 0) return 0;
    int value = 0;
    for (int i = 0; i < size; i++) value = (value << 1) | br_next_bit(r);
    if (value < (1 << (size - 1))) value += 1 - (1 << size);
    return value;
}

// ============================================================
// DECODE ONE 8x8 BLOCK
// ============================================================

static void decode_block(BitReader *r, double block[8][8], const int quant[8][8],
                         HuffDecodeTable *dc_table, HuffDecodeTable *ac_table,
                         int *dc_prev) {
    int zz[64];
    memset(zz, 0, sizeof(zz));

    // --- DC: read the difference and add it to the previous one ---
    int s = br_read_symbol(r, dc_table);
    if (s < 0) s = 0;
    int diff = br_read_amplitude(r, s);
    zz[0] = *dc_prev + diff;
    *dc_prev = zz[0];

    // --- AC: expand (run, size) pairs back into the 63 slots ---
    int pos = 1;
    while (pos < 64) {
        int symbol = br_read_symbol(r, ac_table);
        if (symbol < 0)    break;
        if (symbol == 0x00) break;                    // EOB: rest stays zero
        if (symbol == 0xF0) { pos += 16; continue; }  // ZRL: 16 zeros

        int run  = symbol >> 4;
        int size = symbol & 0x0F;
        pos += run;                                   // skip the zeros
        if (pos >= 64) break;
        zz[pos] = br_read_amplitude(r, size);
        pos++;
    }

    // --- Dequantize and undo the zig-zag, in one pass ---
    double coef[8][8];
    for (int i = 0; i < 64; i++) {
        int idx = ZIGZAG[i];
        int rr = idx / 8, cc = idx % 8;
        coef[rr][cc] = (double)(zz[i] * quant[rr][cc]);
    }

    // --- Back to pixels ---
    idct_block(coef, block);
}

static long decode_plane(BitReader *r, Plane *p, const int quant[8][8],
                         HuffDecodeTable *dc_table, HuffDecodeTable *ac_table) {
    int blocks_x = (p->width  + 7) / 8;
    int blocks_y = (p->height + 7) / 8;
    int dc_prev = 0;                                  // resets per plane

    for (int by = 0; by < blocks_y; by++) {
        for (int bx = 0; bx < blocks_x; bx++) {
            double block[8][8];
            decode_block(r, block, quant, dc_table, ac_table, &dc_prev);

            // Copy the block back, DISCARDING the padding pixels that
            // fall outside the real image.
            for (int rr = 0; rr < 8; rr++) {
                for (int cc = 0; cc < 8; cc++) {
                    int x = bx*8 + cc;
                    int y = by*8 + rr;
                    if (x >= p->width || y >= p->height) continue;

                    double v = block[rr][cc];
                    if (v < 0.0)   v = 0.0;
                    if (v > 255.0) v = 255.0;
                    p->data[(long) y * p->width + x] = (unsigned char)(v + 0.5);
                }
            }
        }
    }
    return (long) blocks_x * blocks_y;
}

int decode_image(unsigned char *buffer, long buffer_size,
                 int width, int height, int quality, int chroma,
                 Plane *y, Plane *cb, Plane *cr, DecodeStats *stats) {
    init_dct_tables();

    HuffDecodeTable dc_luma, ac_luma, dc_chroma, ac_chroma;
    build_decode_table(BITS_DC_LUMA,   VAL_DC_LUMA,   &dc_luma);
    build_decode_table(BITS_AC_LUMA,   VAL_AC_LUMA,   &ac_luma);
    build_decode_table(BITS_DC_CHROMA, VAL_DC_CHROMA, &dc_chroma);
    build_decode_table(BITS_AC_CHROMA, VAL_AC_CHROMA, &ac_chroma);

    int quant_luma[8][8], quant_chroma[8][8];
    scale_table(Q_LUMA_BASE,   quality, quant_luma);
    scale_table(Q_CHROMA_BASE, quality, quant_chroma);

    // Chroma plane size depends on the subsampling mode in the header
    int chroma_w = (chroma == 2) ? (width  + 1) / 2 : width;
    int chroma_h = (chroma == 2) ? (height + 1) / 2 : height;

    *y  = create_plane(width, height);
    *cb = create_plane(chroma_w, chroma_h);
    *cr = create_plane(chroma_w, chroma_h);
    if (!y->data || !cb->data || !cr->data) return 0;

    BitReader r;
    br_init(&r, buffer, buffer_size);

    // Same order the encoder wrote them: all Y, then all Cb, then all Cr
    stats->blocks_y  = decode_plane(&r, y,  quant_luma,   &dc_luma,   &ac_luma);
    stats->blocks_cb = decode_plane(&r, cb, quant_chroma, &dc_chroma, &ac_chroma);
    stats->blocks_cr = decode_plane(&r, cr, quant_chroma, &dc_chroma, &ac_chroma);

    stats->bytes_consumed = r.byte_pos + (r.bit_pos > 0 ? 1 : 0);
    return 1;
}

// ============================================================
// YCbCr -> RGB, WITH CHROMA UPSAMPLING
// ============================================================

static unsigned char clamp_byte(double v) {
    if (v < 0.0)   return 0;
    if (v > 255.0) return 255;
    return (unsigned char)(v + 0.5);
}

int merge_channels(Plane *y, Plane *cb, Plane *cr, Image *out) {
    int w = y->width, h = y->height;

    out->width  = w;
    out->height = h;
    out->pixels = (unsigned char *) malloc((long) w * h * 3);
    if (!out->pixels) return 0;

    // How many luma pixels share one chroma sample
    int scale_x = (cb->width  < w) ? 2 : 1;
    int scale_y = (cb->height < h) ? 2 : 1;

    for (int py = 0; py < h; py++) {
        for (int px = 0; px < w; px++) {
            double luma = y->data[(long) py * w + px];

            // Nearest-neighbour upsampling: each chroma sample is
            // simply reused by the pixels of its 2x2 group.
            int cx = px / scale_x;
            int cy = py / scale_y;
            double blue_diff = plane_sample(cb, cx, cy) - 128.0;
            double red_diff  = plane_sample(cr, cx, cy) - 128.0;

            // Inverse of the formulas from article 2
            double r = luma + 1.402    * red_diff;
            double g = luma - 0.344136 * blue_diff - 0.714136 * red_diff;
            double b = luma + 1.772    * blue_diff;

            long i = ((long) py * w + px) * 3;
            out->pixels[i + 0] = clamp_byte(r);
            out->pixels[i + 1] = clamp_byte(g);
            out->pixels[i + 2] = clamp_byte(b);
        }
    }
    return 1;
}

    // ================= DECODE =================
    printf("=== N.148i decoder ===\n");

    f = fopen(N148I_PATH, "rb");
    if (!f) { printf("Could not open '%s'\n", N148I_PATH); return 1; }

    N148iHeader loaded;
    if (!read_header(f, &loaded)) {
        printf("This is not a valid N148i file!\n");
        fclose(f); return 1;
    }

    printf("Header:  version %d, %u x %u, quality %d, chroma %s\n",
           loaded.version, loaded.width, loaded.height,
           loaded.quality, chroma_name(loaded.chroma));
    printf("Payload: %u bytes\n", loaded.data_size);

    unsigned char *payload = (unsigned char *) malloc(loaded.data_size);
    if (fread(payload, 1, loaded.data_size, f) != loaded.data_size) {
        printf("File is truncated!\n");
        free(payload); fclose(f); return 1;
    }
    fclose(f);

    Plane dy, dcb, dcr;
    DecodeStats dec_stats;
    if (!decode_image(payload, loaded.data_size,
                      loaded.width, loaded.height,
                      loaded.quality, loaded.chroma,
                      &dy, &dcb, &dcr, &dec_stats)) return 1;

    printf("Decoded %ld blocks, consumed %ld of %u bytes\n",
           dec_stats.blocks_y + dec_stats.blocks_cb + dec_stats.blocks_cr,
           dec_stats.bytes_consumed, loaded.data_size);

    Image decoded;
    if (!merge_channels(&dy, &dcb, &dcr, &decoded)) return 1;
    save_ppm(DECODED_PATH, &decoded);
    printf("Wrote %s\n\n", DECODED_PATH);

// Peak Signal-to-Noise Ratio between the original and the decoded image
static double compute_psnr(Image *a, Image *b) {
    long n = (long) a->width * a->height * 3;
    double mse = 0.0;
    for (long i = 0; i < n; i++) {
        double d = (double) a->pixels[i] - (double) b->pixels[i];
        mse += d * d;
    }
    mse /= n;
    if (mse == 0.0) return 999.0;
    return 10.0 * log10(255.0 * 255.0 / mse);
}

gcc main.c header.c ppm.c tables.c dct.c encoder.c decoder.c -o n148i -lm
./n148i

=== N.148i encoder ===
Input:   ../images/example.ppm  (320 x 240)
Quality: 50

Encoded 1800 blocks into 3027 bytes
Wrote ../output/image.n148i

=== N.148i decoder ===
Header:  version 2, 320 x 240, quality 50, chroma 4:2:0
Payload: 3027 bytes
Decoded 1800 blocks, consumed 3027 of 3027 bytes
Wrote ../output/decoded.ppm

=== Results ===
Original PPM:   230415 bytes (225.0 KB)
N148i file:       3047 bytes (3.0 KB)
Compression:  75.6:1
PSNR:         33.79 dB

Qualidade │ Tamanho  │ Compressão │  PSNR
──────────┼──────────┼────────────┼──────────
    90    │ 5866 B   │   39,3:1   │ 36,17 dB
    50    │ 3047 B   │   75,6:1   │ 33,79 dB
    20    │ 1670 B   │  138,0:1   │ 31,45 dB
    10    │ 1465 B   │  157,3:1   │ 29,52 dB

This is not a valid N148i file!

File is truncated!