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.