Compactação - Parte 3

Demorou um pouco mais que eu pretendia, mas segue o exemplo do algorítimo LZW em C. Como parte da preparação, corrigi a descrição das tabelas de compactação e descompactação no post anterior.

Esta versão é bastante simplista, usando códigos de tamanho fixo de 12 bits e parando de atualizar a tabela de compactação quando ela fica cheia. Mesmo assim, consegue reduzir o meu arquivo de teste (o texto do meu livro PC Assembler) de 172KB para 74KB (para uma comparação, o 7-zip consegue reduzir o arquivo para 36KB).

Coloquei no fonte comentários em formato Doxygen. O programa completo e a documentação no formato de help podem ser baixados daqui.

Vamos à parte que interessa. A rotina de compactação é praticamente igual ao pseudo-código que vimos anteriormente:

/************************************************************************/
/**
*  \brief   Compacta o arquivo origem, gerando o arquivo destino
* \ingroup LZW
*/
/************************************************************************/
static void Compacta (void)
{
 int prox; /**< proximo código de saída */
 int w;  /**< código da sequência atualmente conhecida */
 int nw;  /**< código da nova sequência */
 int c;  /**< caracter sendo examinado */

 if (!IniciaES ())
  return;

 // Inicia a tabela
 for (prox = 0; prox < PRIM_CODE; prox++)
  TabComp [prox].cod = TabComp[prox].car = prox;
 for (; prox < T_TABCOMP; prox++)
  TabComp[prox].cod = LIVRE;

 // Compacta
 prox = PRIM_CODE;
 w = LeCarEntrada();
 while (TRUE)
 {
  c = LeCarEntrada();
  if (c == EOF)
   break;
  nw = Procura (c, w);
  if (nw != 0)
  {
   // achou na tabela
   w = nw;
  }
  else
  {
   // não está na tabela
   EscreveCodSaida (w);
   if (prox <= ULT_CODE)
   {
    Guarda (c, w, prox);
    prox++;
   }
   w = c;
  }
 }
 EscreveCodSaida (w);
 EncerraES();
}

A tabela de códigos de compactação e rotinas associadas ficaram assim:

#define T_TABCOMP 5021    /**< tamanho da tabela de compactação \ingroup TabComp */
#define LIVRE  0xFFFF    /**< marca de posição livre \ingroup TabComp */
static struct
{
 int   cod;    /**< código armazenado nesta posição   */
 int   prefixo;   /**< código do prefixo       */
 uchar car;    /**< caracter         */
} TabComp [T_TABCOMP];  /**< Tabela de códigos de compactação \ingroup TabComp */

/************************************************************************/
/**
*  \brief   Procura um par (caracter, prefixo) na tabela de código de
*    compactação
* \ingroup TabComp
*  \param   c  caracter
*  \param   w  código do prefixo
* \return  código correspondente ao par ou 0 se não encontrar
*/
/************************************************************************/
static int Procura (uchar c, int w)
{
 int i;

 i = Hash (c, w);
 while (TRUE)
 {
  if (TabComp [i].cod == LIVRE)
   return 0;
  else if ((TabComp [i].prefixo == w) && (TabComp[i].car == c))
   return TabComp[i].cod;
  else if (++i == T_TABCOMP)
   i = 0;
 }
}

/************************************************************************/
/**
*  \brief   Guarda na tabela de código de compactação o código
*    correspondente a um par (caracter, prefixo)
* \ingroup TabComp
*  \param   c    caracter
*  \param   p    código do prefixo
*  \param   cod  código correspondente a (c, p)
*/
/************************************************************************/
static void Guarda (uchar c, int p, int cod)
{
 int i;

 i = Hash (c, p); // lugar preferido
 while (TRUE)
 {
  // insiste até achar uma entrada livre
  if (TabComp [i].cod == LIVRE)
  {
   TabComp [i].cod = cod;
   TabComp [i].prefixo = p;
   TabComp[i].car = c;
   break;
  }
  if (++i == T_TABCOMP)
   i = 0;
 }
}

/************************************************************************/
/**
*  \brief   Calcula o hash correspondente ao par (caracter, prefixo)
* \ingroup TabComp
*  \param   c  caracter
*  \param   w  código do prefixo
* \return  hash correspondente
*/
/************************************************************************/
static int Hash (uchar c, int w)
{
 return w ^(c << 4);
}

Os códigos gerados tem 12 bits; cada dois códigos são gravados em 3 bytes:

/************************************************************************/
/**
*  \brief   Escreve um código no arquivo de saída
* \ingroup ES
*  \param   w  Código a escrever
*/
/************************************************************************/
static void EscreveCodSaida (int w)
{
 if (pos == 0)
 {
  fputc (w & 0xFF, fpOut);
  buf = w >> 4;
  pos = 1;
 }
 else
 {
  fputc ((buf & 0xF0) | (w & 0x0F), fpOut);
  fputc (w >> 4, fpOut);
  pos = 0;
 }
}

A rotina descompactação fica bem simples:

/// Tabela para expansão
static struct
{
 int   prefixo;   /**< código do prefixo       */
 uchar car;    /**< caracter         */
} TabExp [ULT_CODE+1];  /**< Tabela de códigos de expansão \ingroup TabExp */

/// Pilha de Inversão da Expansão
static uchar pilha [ULT_CODE+1];  /**< pilha para inverter saída da expansão \ingroup LZW */

/************************************************************************/
/**
*  \brief   Expande o arquivo origem, gerando o arquivo destino
* \ingroup LZW
*/
/************************************************************************/
static void Expande (void)
{
 int prox;  /**< proximo código na tabela   */
 int w;   /**< código a descompactar    */
 int lw;   /**< último código a descompactar  */
 uchar c;  /**< último caracter escrito na saída */

 if (!IniciaES ())
  return;

 prox = PRIM_CODE;
 w = LeCodEntrada();
 EscreveCarSaida (w);
 lw = w;
 while (TRUE)
 {
  w = LeCodEntrada();
  if (w == EOF)
   break;
  if (w >= prox)
  {
   // caso especial
   uchar nc;

   nc = EscreveSeqSaida(lw);
   EscreveCarSaida (c);
   c = nc;
  }
  else
   c = EscreveSeqSaida (w);

  if (prox <= ULT_CODE)
  {
   // acrescenta o código na tabela
   TabExp [prox].car = c;
   TabExp [prox].prefixo = lw;
   prox++;
  }
  lw = w;
 }
}

/************************************************************************/
/**
*  \brief   Escreve na saída os caracteres correspondentes a um código
* \ingroup LZW
*  \param   w  código de compactação
*  \return  último caracter escrito na saída
*/
/************************************************************************/
static uchar EscreveSeqSaida (int w)
{
  int topo;  /**< próxima posição livre da pilha  */

  topo = 0;
  while (w >= 256)
  {
    if (topo >= sizeof(pilha))
    {
     printf ("Pilha insuficiente!\n");
     exit (1);
    }
    pilha[topo++] = TabExp[w].car;
      w = TabExp[w].prefixo;
  }
  pilha[topo++] = (uchar) w;
  while (topo > 0)
      EscreveCarSaida (pilha[--topo]);
  return (uchar) w;
}

No próximo post vou mostrar pequenas alterações neste código para melhorar a compactação e ajudar a ver o que ele faz.