Compressão - Parte 6

Agora é hora de deixar para traz o meu código amador e dar uma olhada em uma biblioteca profissional de compactação, a zlib.

A zlib foi escrita por Jean-loup Gailly (compressão) e Mark Adler (expansão), autores do utilitário gzip do GNU. A zlib implementa o algoritmo Deflate que surgiu com a versão 2 do PKZIP e é usado no gzip.

O algoritmo Deflate se baseia no LZ77, que vimos mencionei na parte 1 desta série. Recordando, o LZ77 procura codificar os dados procurando-os em uma "janela" que desliza sobre eles. Ao encontrar uma repetição, o LZ77 os codifica como um deslocamento dentro da janela e no tamanho. Na zlib, esta janela tem 32KBytes.

O resultado da codificação LZ77 passa então por uma codificação de Huffman (que também mencionei na parte 1), na qual se utilizam códigos de tamanho variável associando os códigos menores ao mais usados. A codificação de Huffman se baseia em árvores binárias; a mesma árvore precisa ser usada para compactar e expandir.

Durante a compactação a zlib vai dividindo os dados em blocos. Em cada bloco pode ser usado um dentre três variações do algoritmo:

• Não compactar (ideal para o caso dos dados já estarem compactados)
• LZ77 seguido de Huffman com uma árvore fixa pré-definida (que não precisa ser passada para o expansor)
• LZ77 seguido de Huffman com uma árvore específica (que precisa ser gravada/transmitida junto com os dados)

Os detalhes do Deflate podem ser encontrados aqui, no site oficial da zlib. Este algoritmo é hoje um padrão de facto e também um padrão da internet (RFC 1951)

A zlib é basicamente um conjunto de fontes em C, com uma licença bem liberal. De forma resumida, você pode usar e modificar à vontade (inclusive em softwares comerciais), desde que você deixe claro que não é o autor do software original e que versões alteradas não são as versões originais.

Além dos fontes, o site oficial possui para download uma DLL para Windows 32 bits. Existem várias versões binárias não oficiais para diversos sistemas operacionais e uso com as mais variadas linguagens. Os programadores Java talvez saibam que a zlib está disponível no JDK desde a versão 1.1 (ver java.util.zip) e que é usada no formato JAR. Para os programadores .Net está disponível uma versão totalmente reescrita em código gerenciado, que veremos na próxima (e provavelmente última) parte.

Vamos ver agora como usar a zlib em um programa C. A documentação oficial está no fonte zlib.h ("por enquanto").

O formato dos dados comprimidos através da zlib tem duas partes: os dados compactados em si (o deflate stream, especificado na RFC 1951) e o seu encapsulamento (que pode ser o formato zlib, definido na RFC 1950, ou o formato gzip, definido na RFC 1952). O encapsulamento zlib é voltado para manipulação dos dados em memória, o formato gzip é voltado à compactação de arquivos e usa um cabeçalho maior que guarda informações sobre o arquivo. Vou apresentar aqui exemplos apenas do encapsulamento zlib, junto com os fontes da zlib tem o minigzip.c que mostra o uso do encapsulamento gzip.

A compressão com encapsulamento zlib é feito pela rotina deflate. Esta rotina trabalha com dois buffers, um de entrada e outro de saída. No começo você carrega o início dos dados a compactar no buffer de entrada; o buffer de saída está vazio. Quando você chama deflate, ela processa os dados no buffer de entrada e vai colocando os dados compactados no buffer de saída, até que o buffer de entrada fique vazio ou o buffer de saída fique cheio. No primeiro caso você precisa recarregar o buffer de entrada e no segundo você precisa gravar os dados no buffer de saída. Uma forma de gerenciar isto é colocar um laço que processa o buffer de entrada e grava o buffer de saída até acabar os dados no buffer de entrada dentro de um segundo laço que carrega o buffer de entrada até chegar ao fim dos dados. O final dos dados deve ser sinalizado para deflate, para que ela "cuspa" os dados que ainda estavam em compactação.

Além de deflate é preciso chamar no início uma rotina de iniciação (deflateInit) e no final uma rotina de encerramento (deflateEnd). Em deflateInit especifica-se o nível de compactação desejado, 0 é sem compactação, 1 é a compactação mais rápida (e menos eficiente) e 9 a mais lenta (e mais eficiente). O estado de todo o processo é guardado em uma estrutura z_stream, que é passada para todas as rotinas. Alguns campos desta estrutura devem ser iniciados antes mesmo de deflateInit.

A rotina abaixo, adaptada do exemplo zpipe.c, efetua a compactação de um arquivo; por simplificação retirei todo o tratamento de erro:

void CompactaZlib (char *origem, char *destino)
{
   FILE *fpIn, *fpOut;
   z_stream strm;
   unsigned flush;

   // abre arquivos
   fpIn = fopen (origem, "rb");
   fpOut = fopen (destino, "wb");

   // inicia compactação
   strm.zalloc = Z_NULL;
   strm.zfree = Z_NULL;
   strm.opaque = Z_NULL;
   deflateInit (&strm, Z_DEFAULT_COMPRESSION);

   // compacta até acabar o arquivo origem
   do
   {
       strm.avail_in = fread (bufIn, 1, T_BUF, fpIn);
       strm.next_in = bufIn;
       flush = feof(fpIn) ? Z_FINISH : Z_NO_FLUSH;

       /* compacta e grava até sobrar espaço no buffer de saída  */
       do
       {
           strm.avail_out = T_BUF;
           strm.next_out = bufOut;
           deflate (&strm, flush);
           fwrite (bufOut, 1, T_BUF - strm.avail_out, fpOut);
       } while (strm.avail_out == 0);
   } while (flush != Z_FINISH);


   // finaliza a compactação
   deflateEnd (&strm);

   // fecha arquivos
   fclose (fpOut);
   fclose (fpIn);
}

Rodando este código sobre o meu arquivo de teste, obtemos um arquivo com 38K usando a compactação default (nível 6), o que é o mesmo que obtemos com o PKZip.

A expansão do arquivo compactado é bem semelhante. É preciso indicar que o buffer de entrada está vazio antes de chamar a rotina de iniciação; o final do arquivo é indicado pela rotina de expansão (deflate).

void ExpandeZlib (char *origem, char *destino)
{
   FILE *fpIn, *fpOut;
   z_stream strm;
   unsigned ret;

   // abre arquivos
   fpIn = fopen (origem, "rb");
   fpOut = fopen (destino, "wb");

   // inicia expansão
   strm.zalloc = Z_NULL;
   strm.zfree = Z_NULL;
   strm.opaque = Z_NULL;
   strm.avail_in = 0;
   strm.next_in = Z_NULL;
   inflateInit (&strm);

   // expande até acabar o arquivo origem
   do
   {
       strm.avail_in = fread (bufIn, 1, T_BUF, fpIn);
       strm.next_in = bufIn;

       /* compacta e grava até sobrar espaço no buffer de saída  */
       do
       {
           strm.avail_out = T_BUF;
           strm.next_out = bufOut;
           ret = inflate(&strm, Z_NO_FLUSH);
           fwrite (bufOut, 1, T_BUF - strm.avail_out, fpOut);
       } while (strm.avail_out == 0);
   } while (ret != Z_STREAM_END);


   // finaliza a compactação
   inflateEnd (&strm);

   // fecha arquivos
   fclose (fpOut);
   fclose (fpIn);
}

O projeto Visual C com as rotinas acima está aqui.