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:

view plaincopy to clipboardprint?

1. /************************************************************************/  
2. /** 
3. *  \brief   Compacta o arquivo origem, gerando o arquivo destino 
4. * \ingroup LZW 
5. */  
6. /************************************************************************/  
7. static void Compacta (void)  
8. {  
9.  int prox; /**< proximo código de saída */  
10.  int w;  /**< código da sequência atualmente conhecida */  
11.  int nw;  /**< código da nova sequência */  
12.  int c;  /**< caracter sendo examinado */  
13.   
14.  if (!IniciaES ())  
15.   return;  
16.   
17.  // Inicia a tabela  
18.  for (prox = 0; prox < PRIM_CODE; prox++)  
19.   TabComp [prox].cod = TabComp[prox].car = prox;  
20.  for (; prox < T_TABCOMP; prox++)  
21.   TabComp[prox].cod = LIVRE;  
22.   
23.  // Compacta  
24.  prox = PRIM_CODE;  
25.  w = LeCarEntrada();  
26.  while (TRUE)  
27.  {  
28.   c = LeCarEntrada();  
29.   if (c == EOF)  
30.    break;  
31.   nw = Procura (c, w);  
32.   if (nw != 0)  
33.   {  
34.    // achou na tabela  
35.    w = nw;  
36.   }  
37.   else  
38.   {  
39.    // não está na tabela  
40.    EscreveCodSaida (w);  
41.    if (prox <= ULT_CODE)  
42.    {  
43.     Guarda (c, w, prox);  
44.     prox++;  
45.    }  
46.    w = c;  
47.   }  
48.  }  
49.  EscreveCodSaida (w);  
50.  EncerraES();  
51. }  

/************************************************************************/
/**
*  \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:

view plaincopy to clipboardprint?

1. #define T_TABCOMP 5021    /**< tamanho da tabela de compactação \ingroup TabComp */  
2. #define LIVRE  0xFFFF    /**< marca de posição livre \ingroup TabComp */  
3. static struct  
4. {  
5.  int   cod;    /**< código armazenado nesta posição   */  
6.  int   prefixo;   /**< código do prefixo       */  
7.  uchar car;    /**< caracter         */  
8. } TabComp [T_TABCOMP];  /**< Tabela de códigos de compactação \ingroup TabComp */  
9.   
10. /************************************************************************/  
11. /** 
12. *  \brief   Procura um par (caracter, prefixo) na tabela de código de 
13. *    compactação 
14. * \ingroup TabComp 
15. *  \param   c  caracter 
16. *  \param   w  código do prefixo 
17. * \return  código correspondente ao par ou 0 se não encontrar 
18. */  
19. /************************************************************************/  
20. static int Procura (uchar c, int w)  
21. {  
22.  int i;  
23.   
24.  i = Hash (c, w);  
25.  while (TRUE)  
26.  {  
27.   if (TabComp [i].cod == LIVRE)  
28.    return 0;  
29.   else if ((TabComp [i].prefixo == w) && (TabComp[i].car == c))  
30.    return TabComp[i].cod;  
31.   else if (++i == T_TABCOMP)  
32.    i = 0;  
33.  }  
34. }  
35.   
36. /************************************************************************/  
37. /** 
38. *  \brief   Guarda na tabela de código de compactação o código 
39. *    correspondente a um par (caracter, prefixo) 
40. * \ingroup TabComp 
41. *  \param   c    caracter 
42. *  \param   p    código do prefixo 
43. *  \param   cod  código correspondente a (c, p) 
44. */  
45. /************************************************************************/  
46. static void Guarda (uchar c, int p, int cod)  
47. {  
48.  int i;  
49.   
50.  i = Hash (c, p); // lugar preferido  
51.  while (TRUE)  
52.  {  
53.   // insiste até achar uma entrada livre  
54.   if (TabComp [i].cod == LIVRE)  
55.   {  
56.    TabComp [i].cod = cod;  
57.    TabComp [i].prefixo = p;  
58.    TabComp[i].car = c;  
59.    break;  
60.   }  
61.   if (++i == T_TABCOMP)  
62.    i = 0;  
63.  }  
64. }  
65.   
66. /************************************************************************/  
67. /** 
68. *  \brief   Calcula o hash correspondente ao par (caracter, prefixo) 
69. * \ingroup TabComp 
70. *  \param   c  caracter 
71. *  \param   w  código do prefixo 
72. * \return  hash correspondente 
73. */  
74. /************************************************************************/  
75. static int Hash (uchar c, int w)  
76. {  
77.  return w ^(c << 4);  
78. }  

#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:

view plaincopy to clipboardprint?

1. /************************************************************************/  
2. /** 
3. *  \brief   Escreve um código no arquivo de saída 
4. * \ingroup ES 
5. *  \param   w  Código a escrever 
6. */  
7. /************************************************************************/  
8. static void EscreveCodSaida (int w)  
9. {  
10.  if (pos == 0)  
11.  {  
12.   fputc (w & 0xFF, fpOut);  
13.   buf = w >> 4;  
14.   pos = 1;  
15.  }  
16.  else  
17.  {  
18.   fputc ((buf & 0xF0) | (w & 0x0F), fpOut);  
19.   fputc (w >> 4, fpOut);  
20.   pos = 0;  
21.  }  
22. }  

/************************************************************************/
/**
*  \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:

view plaincopy to clipboardprint?

1. /// Tabela para expansão  
2. static struct  
3. {  
4.  int   prefixo;   /**< código do prefixo       */  
5.  uchar car;    /**< caracter         */  
6. } TabExp [ULT_CODE+1];  /**< Tabela de códigos de expansão \ingroup TabExp */  
7.   
8. /// Pilha de Inversão da Expansão  
9. static uchar pilha [ULT_CODE+1];  /**< pilha para inverter saída da expansão \ingroup LZW */  
10.   
11. /************************************************************************/  
12. /** 
13. *  \brief   Expande o arquivo origem, gerando o arquivo destino 
14. * \ingroup LZW 
15. */  
16. /************************************************************************/  
17. static void Expande (void)  
18. {  
19.  int prox;  /**< proximo código na tabela   */  
20.  int w;   /**< código a descompactar    */  
21.  int lw;   /**< último código a descompactar  */  
22.  uchar c;  /**< último caracter escrito na saída */  
23.   
24.  if (!IniciaES ())  
25.   return;  
26.   
27.  prox = PRIM_CODE;  
28.  w = LeCodEntrada();  
29.  EscreveCarSaida (w);  
30.  lw = w;  
31.  while (TRUE)  
32.  {  
33.   w = LeCodEntrada();  
34.   if (w == EOF)  
35.    break;  
36.   if (w >= prox)  
37.   {  
38.    // caso especial  
39.    uchar nc;  
40.   
41.    nc = EscreveSeqSaida(lw);  
42.    EscreveCarSaida (c);  
43.    c = nc;  
44.   }  
45.   else  
46.    c = EscreveSeqSaida (w);  
47.   
48.   if (prox <= ULT_CODE)  
49.   {  
50.    // acrescenta o código na tabela  
51.    TabExp [prox].car = c;  
52.    TabExp [prox].prefixo = lw;  
53.    prox++;  
54.   }  
55.   lw = w;  
56.  }  
57. }  
58.   
59. /************************************************************************/  
60. /** 
61. *  \brief   Escreve na saída os caracteres correspondentes a um código 
62. * \ingroup LZW 
63. *  \param   w  código de compactação 
64. *  \return  último caracter escrito na saída 
65. */  
66. /************************************************************************/  
67. static uchar EscreveSeqSaida (int w)  
68. {  
69.   int topo;  /**< próxima posição livre da pilha  */  
70.   
71.   topo = 0;  
72.   while (w >= 256)  
73.   {  
74.     if (topo >= sizeof(pilha))  
75.     {  
76.      printf ("Pilha insuficiente!\n");  
77.      exit (1);  
78.     }  
79.     pilha[topo++] = TabExp[w].car;  
80.       w = TabExp[w].prefixo;  
81.   }  
82.   pilha[topo++] = (uchar) w;  
83.   while (topo > 0)  
84.       EscreveCarSaida (pilha[--topo]);  
85.   return (uchar) w;  
86. }  

/// 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.