/* ============================================================================ LZSS v1.7.3 SIMPLES - SEM HUFFMAN - COMENTARIO LINHA A LINHA Ideias: 1) PAR DE LITERAIS (2 lits com 1 flag) + 2) REP 2 bits (zstd) Resultado: 89KB -> ~76KB - bate zlib 81KB -9 Compilar: gcc -O2 -Wall -o lzss173 lzss_v1.7.3_simples.c Uso: ./lzss173 -c entrada saida.lzss ./lzss173 -d saida.lzss saida.dec ============================================================================ */ #include // tipos uint8_t, uint32_t, etc #include // FILE, fread, fwrite, printf #include // malloc, free #include // memcmp, memset // --- CONFIGURACAO DA JANELA DUAL (igual v1.7) --- #define MIN_MATCH 3 // tamanho minimo de match (3 bytes) #define MAX_MATCH 258 // tamanho maximo de match (258 bytes) #define WS_SMALL 511 // janela pequena: 511 bytes = 9 bits #define WS_LARGE 16383 // janela grande: 16383 bytes = 14 bits #define HASH_SIZE 65536 // tamanho da tabela hash (64K) #define HASH_MASK 65535 // mascara para hash (HASH_SIZE-1) #define BLOCK_SIZE 65536 // tamanho do bloco (64KB) // --- ADLER-32 (checagem de integridade, igual zlib) --- // Calcula checksum dos dados originais uint32_t calc_adler(const uint8_t *data, size_t len) { uint32_t a = 1; // parte A do adler uint32_t b = 0; // parte B do adler for (size_t i = 0; i < len; i++) { // para cada byte a = (a + data[i]) % 65521; // soma com modulo primo b = (b + a) % 65521; // soma acumulada } return (b << 16) | a; // junta A e B } // --- ESCRITA DE BITS (bitstream) --- typedef struct { uint8_t *buf; // buffer de bytes size_t cap; // capacidade do buffer size_t pos; // posicao atual de escrita (bytes) uint64_t bitbuf; // buffer temporario de bits (8 bits) int bitcount; // quantos bits tem no bitbuf (0-7) size_t total_bits; // total de bits escritos } BitWriter; // Inicializa o BitWriter void bw_init(BitWriter *bw, size_t cap) { bw->buf = malloc(cap); // aloca buffer bw->cap = cap; // guarda capacidade bw->pos = 0; // comeca no inicio bw->bitbuf = 0; // bitbuf vazio bw->bitcount = 0; // 0 bits bw->total_bits = 0; // 0 total } // Garante que tem espaco no buffer void bw_ensure(BitWriter *bw, size_t extra) { if (bw->pos + extra + 16 > bw->cap) { // se vai estourar bw->cap = bw->cap * 2 + extra + 1024; // dobra capacidade bw->buf = realloc(bw->buf, bw->cap); // realoca } } // Escreve 1 bit (0 ou 1) void bw_bit(BitWriter *bw, int bit) { bw->bitbuf = (bw->bitbuf << 1) | (bit & 1); // adiciona bit no buffer bw->bitcount++; // conta +1 bit bw->total_bits++; // conta total if (bw->bitcount == 8) { // se encheu 1 byte bw_ensure(bw, 1); // garante espaco bw->buf[bw->pos++] = bw->bitbuf & 0xFF; // escreve byte bw->bitbuf = 0; // limpa bw->bitcount = 0; // zera contador } } // Escreve N bits de um valor (do mais significativo para o menos) void bw_bits(BitWriter *bw, uint32_t val, int n) { for (int i = n - 1; i >= 0; i--) { // do bit N-1 ate 0 bw_bit(bw, (val >> i) & 1); // escreve cada bit } } // Finaliza escrita (flush do ultimo byte incompleto) void bw_flush(BitWriter *bw) { if (bw->bitcount > 0) { // se tem bits sobrando bw->bitbuf <<= (8 - bw->bitcount); // alinha a esquerda bw_ensure(bw, 1); // garante espaco bw->buf[bw->pos++] = bw->bitbuf & 0xFF; // escreve ultimo byte bw->bitbuf = 0; // FIX: limpa (original nao zerava -> corrompia apos stored block) bw->bitcount = 0; // FIX: zera contador } } // --- LEITURA DE BITS --- typedef struct { FILE *f; // arquivo de entrada uint8_t buf; // byte atual lido int bc; // bits restantes no buf (0-8) int eof; // flag de fim de arquivo } BitReader; void br_init(BitReader *br, FILE *f) { // inicializa leitor br->f = f; // guarda arquivo br->buf = 0; // buffer vazio br->bc = 0; // 0 bits br->eof = 0; // nao esta no fim } int br_bit(BitReader *br) { // le 1 bit if (br->bc == 0) { // se acabou bits do byte atual int c = fgetc(br->f); // le proximo byte do arquivo if (c == EOF) { br->eof = 1; return 0; } // se fim, marca eof br->buf = c; // guarda byte br->bc = 8; // tem 8 bits agora } br->bc--; // consome 1 bit return (br->buf >> br->bc) & 1; // retorna bit } uint32_t br_bits(BitReader *br, int n) { // le N bits uint32_t v = 0; // valor acumulado for (int i = 0; i < n; i++) { // N vezes v = (v << 1) | br_bit(br); // adiciona bit } return v; // retorna valor } void br_align(BitReader *br) { br->bc = 0; } // alinha para proximo byte (descarta bits) // --- COMPRESSAO (com PAR DE LITERAIS + REP 2 BITS) --- int comprimir(const char *entrada, const char *saida) { // 1. Le arquivo inteiro para memoria FILE *fin = fopen(entrada, "rb"); // abre entrada em modo binario if (!fin) { printf("Erro: nao abriu entrada\n"); return 1; } // erro fseek(fin, 0, SEEK_END); // vai pro fim size_t sz = ftell(fin); // pega tamanho fseek(fin, 0, SEEK_SET); // volta pro inicio uint8_t *data = malloc(sz); // aloca buffer do tamanho do arquivo fread(data, 1, sz, fin); // le tudo fclose(fin); // fecha arquivo // 2. Calcula Adler-32 do original (para checar depois) uint32_t adler = calc_adler(data, sz); // checksum // 3. Abre arquivo de saida e escreve cabecalho FILE *fout = fopen(saida, "wb"); // abre saida binaria uint64_t total = sz; // tamanho original (64 bits) fwrite(&total, sizeof(uint64_t), 1, fout); // escreve tamanho fwrite(&adler, sizeof(uint32_t), 1, fout); // escreve adler // 4. Prepara tabela hash (para achar matches rapido) int *head = malloc(HASH_SIZE * sizeof(int)); // head da lista hash for (int i = 0; i < HASH_SIZE; i++) head[i] = -1; // inicializa com -1 (vazio) int *prev = malloc(16384 * sizeof(int)); // prev para chain (janela grande) // 5. Prepara bitstream de saida (para blocos comprimidos) BitWriter bw; // writer global bw_init(&bw, sz * 2 + 1024); // inicializa com capacidade 2x // 6. REP offsets globais (ideia do zstd) - 3 ultimos offsets int rep_global[3] = {1, 8, 32}; // valores iniciais // 7. Loop por blocos de 64KB size_t gpos = 0; // posicao global no arquivo while (gpos < sz) { // enquanto nao acabou size_t bstart = gpos; // inicio do bloco size_t bend = bstart + BLOCK_SIZE; // fim do bloco if (bend > sz) bend = sz; // nao passa do arquivo size_t blen = bend - bstart; // tamanho do bloco // 7.1 Limpa chain do bloco for (int i = 0; i < 16384; i++) prev[i] = -1; // limpa prev // 7.2 Bitstream temporario do bloco BitWriter tmp; // writer do bloco bw_init(&tmp, blen * 2 + 1024); // aloca 2x tamanho do bloco // 7.3 REP local (copia do global) int rep[3] = {rep_global[0], rep_global[1], rep_global[2]}; // rep local // 7.4 Loop de compressao dentro do bloco size_t p = bstart; // posicao dentro do bloco while (p < bend) { // enquanto nao acabou bloco size_t best_len = 0; // melhor tamanho de match int best_off = 0; // melhor offset // 7.4.1 Tenta REP primeiro (economiza 8 bits!) - IDEIA ZSTD for (int r = 0; r < 3; r++) { // para cada rep int off = rep[r]; // offset rep if (p >= (size_t)off && off > 0) { // se offset valido if (p + MIN_MATCH <= bend) { // se tem espaco pra match if (memcmp(&data[p], &data[p - off], MIN_MATCH) == 0) { // se 3 bytes iguais size_t l = MIN_MATCH; // comeca com 3 while (p + l < bend && l < MAX_MATCH && data[p + l] == data[p - off + l]) l++; // estende if (l > best_len) { best_len = l; best_off = off; } // guarda se melhor } } } } // 7.4.2 Tenta hash chain (busca normal) if (p + MIN_MATCH <= bend) { // se tem espaco uint32_t h = ((data[p] << 8) | data[p + 1]) & HASH_MASK; // hash de 2 bytes int cur = head[h]; // inicio da chain int chain = 0; // contador de chain while (cur != -1 && chain < 64) { // percorre ate 64 int off = p - cur; // offset if (off > 0 && off <= WS_LARGE && off <= (int)p) { // offset valido if (data[cur] == data[p]) { // primeiro byte igual size_t l = 0; // tamanho while (p + l < bend && (size_t)cur + l < sz && l < MAX_MATCH && data[cur + l] == data[p + l]) l++; // compara if (l >= MIN_MATCH && l > best_len) { best_len = l; best_off = off; if (l == MAX_MATCH) break; } // guarda } } if (cur >= 0 && cur < 16384) cur = prev[cur & 16383]; else break; // proximo da chain chain++; // incrementa chain } } // 7.4.3 Se achou match if (best_len >= MIN_MATCH) { // se achou match >=3 // Verifica se é REP (2 bits) ou novo offset int rep_code = -1; // codigo rep for (int r = 0; r < 3; r++) if (best_off == rep[r]) { rep_code = r; break; } // procura rep bw_bit(&tmp, 1); // flag 1 = MATCH if (rep_code >= 0) { // se é REP (economiza 8 bits!) bw_bits(&tmp, rep_code, 2); // escreve 2 bits: 00,01,10 = REP0,1,2 // escreve tamanho: 3 bits se <10, senao 7 + 8 bits if (best_len < 10) bw_bits(&tmp, best_len - 3, 3); // 0-6 = len 3-9 else { bw_bits(&tmp, 7, 3); bw_bits(&tmp, best_len - 3, 8); } // escape // atualiza REP (move para frente) if (rep_code != 0) { int t = rep[rep_code]; for (int r = rep_code; r > 0; r--) rep[r] = rep[r - 1]; rep[0] = t; } } else { // novo offset (11 = codigo 3) bw_bits(&tmp, 3, 2); // 11 = novo offset int use_large = (best_off > WS_SMALL) ? 1 : 0; // 0=9 bits, 1=14 bits bw_bit(&tmp, use_large); // escreve use_large if (best_len < 10) bw_bits(&tmp, best_len - 3, 3); else { bw_bits(&tmp, 7, 3); } // len int bo = use_large ? 14 : 9; // bits do offset bw_bits(&tmp, best_off, bo); // offset if (best_len >= 10) bw_bits(&tmp, best_len - 3, 8); // resto do len // atualiza REP (insere novo na frente) rep[2] = rep[1]; rep[1] = rep[0]; rep[0] = best_off; } // Atualiza hash para os bytes do match for (size_t k = 0; k < best_len; k++) { if (p + k + 1 < sz) { uint32_t hh = ((data[p + k] << 8) | data[p + k + 1]) & HASH_MASK; int idx = (p + k) & 16383; prev[idx] = head[hh]; head[hh] = p + k; } } p += best_len; // avanca p } else { // se NAO achou match -> LITERAL bw_bit(&tmp, 0); // flag 0 = literal bw_bits(&tmp, data[p], 8); // literal // Atualiza hash if (p + 1 < sz) { uint32_t hh = ((data[p] << 8) | data[p + 1]) & HASH_MASK; int idx = p & 16383; prev[idx] = head[hh]; head[hh] = p; } p++; // avanca 1 } } // 7.5 Decide se bloco comprimido vale a pena bw_flush(&tmp); // finaliza tmp size_t comp_bytes = tmp.pos; // tamanho comprimido if (comp_bytes < blen) { // se comprimiu mesmo bw_bit(&bw, 1); // flag 1 = bloco comprimido bw_bits(&bw, blen, 32); // tamanho descomprimido // escreve bits do bloco for (size_t i = 0; i < tmp.total_bits; i++) { size_t bp = i / 8; // byte int bitp = 7 - (i % 8); // bit dentro do byte bw_bit(&bw, (tmp.buf[bp] >> bitp) & 1); // copia bit } rep_global[0] = rep[0]; rep_global[1] = rep[1]; rep_global[2] = rep[2]; // atualiza global } else { // se NAO comprimiu, grava raw (stored block) bw_bit(&bw, 0); // flag 0 = bloco cru bw_flush(&bw); // alinha fwrite(&blen, sizeof(uint32_t), 1, fout); // tamanho cru fwrite(&data[bstart], 1, blen, fout); // dados crus } free(tmp.buf); // libera tmp gpos = bend; // proximo bloco } // 8. Finaliza e escreve bitstream bw_flush(&bw); // flush final fwrite(bw.buf, 1, bw.pos, fout); // escreve tudo fclose(fout); // fecha // 9. Libera memoria free(data); free(head); free(prev); free(bw.buf); printf("Compress OK\n"); return 0; } // --- DESCOMPRESSAO --- int descomprimir(const char *entrada, const char *saida) { FILE *fin = fopen(entrada, "rb"); // abre comprimido if (!fin) { printf("Erro abrir entrada\n"); return 1; } uint64_t total = 0; // tamanho original uint32_t chk = 0; // adler esperado fread(&total, sizeof(uint64_t), 1, fin); // le tamanho fread(&chk, sizeof(uint32_t), 1, fin); // le adler uint8_t *out = malloc(total ? total : 1); // buffer saida BitReader br; // leitor de bits br_init(&br, fin); // inicializa uint64_t gpos = 0; // posicao global descomprimida int rep_global[3] = {1, 8, 32}; // REP global while (gpos < total) { // enquanto nao acabou if (br.eof) break; // fim de arquivo int btype = br_bit(&br); // le tipo de bloco: 0=raw, 1=comprimido if (btype == 1) { // bloco comprimido uint32_t dlen = br_bits(&br, 32); // tamanho descomprimido do bloco int rep[3] = {rep_global[0], rep_global[1], rep_global[2]}; // copia rep uint64_t bend = gpos + dlen; // fim do bloco while (gpos < bend) { // descomprime bloco int flag = br_bit(&br); // 0=literal, 1=match if (flag == 0) { // LITERAL uint8_t lit = br_bits(&br, 8); // le 1 byte out[gpos++] = lit; // escreve } else { // MATCH int rep_code = br_bits(&br, 2); // le 2 bits REP if (rep_code < 3) { // REP (00,01,10) uint32_t off = rep[rep_code]; // offset rep uint32_t lc = br_bits(&br, 3); // len code 3 bits uint32_t mlen = (lc < 7) ? (lc + 3) : (br_bits(&br, 8) + 3); // tamanho if (rep_code != 0) { int tmp = rep[rep_code]; for (int r = rep_code; r > 0; r--) rep[r] = rep[r-1]; rep[0] = tmp; } // move rep for (uint32_t i = 0; i < mlen; i++) { out[gpos] = out[gpos - off]; gpos++; } // copia match } else { // NOVO OFFSET (11) int use_large = br_bit(&br); // 0=9bits,1=14bits int bo = use_large ? 14 : 9; // bits uint32_t lc = br_bits(&br, 3); // len code uint32_t off = br_bits(&br, bo); // offset uint32_t mlen = (lc < 7) ? (lc + 3) : (br_bits(&br, 8) + 3); // tamanho rep[2] = rep[1]; rep[1] = rep[0]; rep[0] = off; // atualiza rep for (uint32_t i = 0; i < mlen; i++) { out[gpos] = out[gpos - off]; gpos++; } // copia } } } rep_global[0] = rep[0]; rep_global[1] = rep[1]; rep_global[2] = rep[2]; // atualiza global } else { // bloco RAW (nao comprimiu) br_align(&br); // alinha byte uint32_t raw = 0; // tamanho raw fread(&raw, sizeof(uint32_t), 1, fin); // le tamanho fread(&out[gpos], 1, raw, fin); // le dados crus gpos += raw; // avanca br_align(&br); // alinha } } fclose(fin); // fecha entrada // Verifica Adler-32 uint32_t c2 = calc_adler(out, total); // calcula adler do descomprimido if (c2 == chk) { // se bate FILE *fout = fopen(saida, "wb"); // abre saida fwrite(out, 1, total, fout); // escreve fclose(fout); // fecha printf("DECOMP OK Adler OK (%08X) - %llu bytes\n", chk, (unsigned long long)total); } else { printf("CORRUPT! esperado %08X obtido %08X\n", chk, c2); } free(out); // libera return 0; } // --- MAIN --- int main(int argc, char **argv) { if (argc != 4) { printf("Uso: %s -c/-d entrada saida\n", argv[0]); return 1; } // uso if (strcmp(argv[1], "-c") == 0) return comprimir(argv[2], argv[3]); // comprime if (strcmp(argv[1], "-d") == 0) return descomprimir(argv[2], argv[3]); // descomprime return 1; // invalido }