Lunar Lander

Quando eu estava preparando o meu post sobre como controlar muitos LEDs, e pensando num exemplo de displays de sete segmentos, me veio uma vaga ideia de fazer uma versão de um antigo joguinho de pouso na lua (da infância dos micros pessoais). A ideia conceitual era a seguinte:


Há pouco mais de duas semanas foi que me dei conta que no dia 20 de julho era aniversário de 40 anos do pouso na Lua. Resolvi então fazer uma primeira versão para a data. O prazo curto me obrigou a adotar algumas simplificações e usar os componentes que tinha à mão, mesmo quando não eram os mais adequados.

O tosco resultado final foi o seguinte:


O Jogo

O jogo Lunar Lander consiste em pousar suavemente uma espaçonave na Lua, controlando a queima do pouco combustível disponível.

Procurando nos tubos da internet, achei uma versão extremamente legível, apesar de estar em uma linguagem que não conheço: http://eleven.sourceforge.net/demo/lander.html. Esta versão se baseia em programas escritos em BASIC por Dave Ahl (que eu conhecia dos anos 80, quando comprava a revista Creative Computing). As versões de DaveAhl estão disponíveis aqui.

Eu segui bem de perto a versão em Eleven, deixando de lado aperfeiçoamentos como variar a massa da nave à medida em que o combustível é queimado. Adotei também os mesmos valores; futuramente vou dar uma ajustada.

O Algorítimo

O algorítimo é trivial, com velocidade e posição sendo calculados incrementalmente:

• a aceleração da nave é a gravidade menos a queima de combustível.
• a nova velocidade é a velocidade atual mais a aceleração vezes o tempo.
• a nova altitude é a média entre a velocidade atual e a nova vezes o tempo.
  

Sendo o tempo entre os cálculos fixos, basta acertar as escalas para fazer as contas usando somente soma e subtração.

O Display

Usei quatro displays duplos de sete segmentos que eu tinha guardado desde o final dos anos 70. Cada display possui 18 pinos, correspondentes aos anodos dos oitos LEDs (sete segmentos mais o ponto) e o catodo comum aos LEDs de cada dígito.

Os segmentos iguais dos dígitos foram interligados entre si e conectados, através de um resistor, às saídas de um shift register 74HC595. A seleção do dígito é feita por um decodificador 3-para-8 (inicialmente um 74LS138 e depois um 74HC138), que aciona um transistor conectado ao catodo. Eu aproveitei uns transistores antigos que eu tinha, mas esta parte não ficou boa; o resultado foi um brilho fraco do display. Faltou tempo e coragem para rever esta parte do circuito.

Montei o display em uma placa separada, para maior flexibilidade:


As conexões foram feitas com fio de wire-wrap soldado, o que deu bem mais trabalho que eu previa. O resultado é ligeiramente assustador, e o motivo pelo qual eu não tentei trocar os transistores:

O conector na parte de baixo recebe

• a alimentação
• os três sinais de seleção de dígito
• os quatro sinais de controle do shift register (dado, clock de shift, clock de cópia do shift para a saída e o clear do shift)

Um primeiro teste, acionando os sinais por meio de botões, permitiu corrigir os pequenos erros de montagem.

O Microcontrolador

Devido ao uso do 74LS138 o display exigia 5V o que dificultava o uso do MSP430 (já troquei por um 74HC138 para algum dia operar com 3V). Por este motivo resolvi usar um PIC 16F628A (uma escolha mal pensada, como veremos adiante). Esta parte foi montada numa breadboard.


O PIC é o integrado no alto, próximo ao centro. A peça marrom claro à esquerda é um ressonador de 4MHz, que fornece o clock para o PIC. O LED foi usado inicialmente para testes. Na parte inferior estão o botão para acionar o retrofoguete e o potenciômetro que controla a quantidade de combustível a queimar por unidade de tempo. O conector de telefone, no alto à direita permite ligar o gravador para regravar o firmware sem retirar o PIC do circuito (ainda bem, pois foram algumas dezenas de gravações).

Tudo correu bem, até o momento de ligar o potenciômetro. Foi neste ponto que percebi que este modelo de PIC não tem ADC (conversor Analógico para Decimal). Por outro lado, ele tem um comparador analógico e uma fonte de referência programável, o jeito foi ficar variando a referência e detectar quando ela ela ultrapassa a tensão no potenciômetro.

O comparador deste PIC é muito pouco flexível. A única opção para usar a referência interna obriga a usar dois comparadores, consumindo dois pinos do PIC. Após realocar os pinos de E/S tudo parou de funcionar. Lendo com mais atenção a documentação do PIC, descobri que um dos pinos de E/S tem comportamento diferente dos demais. Era justo neste pino que eu tinha ligado o sinal de Clear do shift register, resultando em um display sempre apagado. Além disso, parece que o comparador ocupa não somente os dois pinos configurados como entrada mas também os outros dois que podem ser configurados como entrada (preciso investigar um pouco mais). Com o prazo e os pinos acabando, movi dois sinais para os pinos de programação. Felizmente as duas funções conviveram harmoniosamente.

O Firmware

Como está virando rotina nos meus projetos até agora, o coração do firmware é a interrupção do timer, que ocorre a cada milissegundo. Neste interrupção são feitos:

• A atualização da altitude, velocidade e combustível. Seguindo os números do programa que tomei como base, a atualização deveria ser a cada 10 milissegundos. Para ficar mais fácil de acompanhar os números, dobrei este tempo (ou seja, o jogador trabalho com o sistema em "slow motion"). Todos os valores são inteiros; a altitude é um inteiro de 32 bits e os demais de 16 bits.
  
• A leitura do comparador e reprogramação da tensão de referência para acompanhar o potenciômetro. Para minha surpresa, este código funcionou quase que de primeira. Por simplificação o potenciômetro seleciona apenas cinco níveis de queima (0, 25%, 50%, 75% e 100% da taxa de queima máxima).
• A atualização dos segmentos a apresentar. Para isto é preciso converter os valores inteiros nos dígitos correspondentes, o que requer divisão. Entretanto as divisões são demoradas demais para ficar na interrupção. O jeito foi a cada 100 milissegundos a interrupção acionar um flag para que o programa principal faça as cálculos. Ao final dos cálculos o programa principal acionar um flag para a próxima interrupção usar o resultado. Os segmentos são armazenados em 8 bytes, com cada byte correspondendo a um dígito do display e cada bit a um segmento. Uma tabela auxiliar contém os valores correspondentes a cada dígito.
  
• A varredura dos dígitos. A cada 3 milissegundos é selecionado o dígito seguinte e carregado o shift register com o valor correspondente aos seus segmentos.
  

Resultado Final

O Lunar Lander Mark I está funcionando! Falta vários acertos, tanto de hardware (como melhorar a luminosidade) como de software (como tratar o caso da velocidade ficar negativa), mas já dá para brincar.



Mais para frente, quando tiver um resultado um pouco melhor, eu publico o circuito e o código.

Outras Opções de Compra de Componentes via Internet

Embora esteja plenamente satisfeito com a Soldafria, ocasionalmente eles não tem algum componente que necessito. Listo abaixo outras duas opções que já usei.

Farnell Newark

É uma empresa bastante tradicional, que no passado vendia por catálogo e vende pela internet há alguns anos. É uma empresa multinacional e o site lista tanto o estoque nacional como o internacional.

Possui uma quantidade muito grande de componentes e não requer compra mínima, mas os preços costumam ser um pouco mais altos que as outras opções. Tenho a impressão que o estoque deles privilegia componentes SMD.

Na minha compra mais recente (em 20/5) eu solicitei dois componentes, ambos com estoque nacional zerado mas um deles com estoque internacional. Após uma boa demora (30/5), eles confirmaram o pedido do que tinha estoque internacional mas informaram não poder fornecer o outro. O prazo para chegar o componente que veio de fora foi de cerca de três semanas, o que é razoável. A embalagem é bem profissional, as compras que fiz até agora vieram sempre em um envelope acolchoado.

O problema é que na mesma época mudaram o site. A mudança foi anunciada por e-mail e o site ficou fora do ar por alguns dias e até recentemente ainda dava alguns erros. Por "estar desenvolvido em uma nova plataforma" é preciso se re-cadastrar; com isto perdi o histórico de compras anteriores. Os clientes que estavam com pedido em curso (como era o meu caso) deixaram de poder acompanhá-los pelo site. Além de tudo, "para tornar a sua compra mais ágil" está temporariamente suspensa a compra por cartão.

Continuo contando com a Farnell para componentes mais incomuns, mas fiquei um pouco decepcionado com os problemas nesta mudança de site.

Cinestec

Esta fica um pouco mais longe que as demais, em Campinas. O site é bom e satisfatoriamente organizado. Tem uma boa variedade e preços bons. Tem uma indicação de nível do estoque, mas a utilidade desta informação é discutível: um determinado transistor tinha nível "alto" porém não aceitou um pedido de 20 peças (custa R$0,20 cada), por tentativa e erro descobri que tinha somente quatro.

Uma das coisas que eu gostei no cadastro é pedir o endereço de cobrança e o endereço de entrega. Quando possível coloco como endereço de cobrança o da minha residência (que é o endereço para os cartões de crédito) e peço a entrega no trabalho (onde eu posso receber pessoalmente). Ao final do cadastro um e-mail de confirmação foi imediatamente enviado.

O processo de compra tem alguns poréns. A Cinestec trabalha somente com pagamento por transferência ou depósito bancário; pelo menos tem várias opções de bancos o que me permitiu fazer a transferência via internet. O valor do frete não é informado na hora, é preciso aguardar eles separarem os itens e calcularem o frete. Acho isto muito ruim.

A coisa complicou um pouco a partir daí. Não recebi nenhum e-mail de confirmação do pedido, apesar dele estar registrado no site. Fiz a compra em 8/7 (4a feira); dia 9/7 foi feriado. Sem notícias, na 3a seguinte (14/7) resolvi ligar para eles. A informação é que o pedido já estava separado e o e-mail já tinha sido enviado. Confirmei o e-mail e pedi para re-enviar; novamente não chegou. Liguei novamente e pedi para enviar para o e-mail do trabalho e finalmente chegou. Fiz a transferência e fiquei aguardando. Imaginem a minha surpresa ao chegar em casa na 5a feira e encontrar o material lá!

O material veio direitinho. Os itens foram acondicionados em saquinhos de papel (anacronismo ou preocupação ecológica?), com indicação do item, quantidade e nome do separador. A nota fiscal tinha também um ar nostálgico: era manuscrita. Para não ficar dúvida: apesar da surpresa, nada contra isto tudo, o importante foi que vieram os componentes certos na quantidade solicitada.

Resumindo, o único problema sério foi a entrega no endereço errado (o mistério dos e-mails sumidos é chato mas não posso atribuir a eles). Por enquanto fica sendo uma opção interessante, mas que não posso recomendar sem restrições. Vamos ver como se comportará em pedidos futuros.

JavaScript Should Be Considered Harmfull?

Talvez seja somente implicação minha, mas me incomoda como grande parte das soluções "modernas" em software se baseiam no JavaScript. Quase toda a funcionalidade no lado do cliente das soluções web é baseada nele.

A minha "birra" começa pelo nome. O nome JavaScript é resultado de um concluio de marketing entre a Sun e a Netscape, a linguagem em si não está relacionada diretamente ao Java.

Uma grande parte do código JavaScript é gerada por ferramentas automáticas ou bibliotecas, deixando o programador mais afastado do código que vai ser executado.

E, na medida em que aumenta o uso, começam a surgir os bugs e as falhas de segurança.

A fundação Mozila liberou ontem a versão 3.5.1 do Firefox que fecha um buraco na compilação Just-in-time do JavaScript. Por que compilar JavaScript? Porque cada vez mais a velocidade de interação dos sites depende do JavaScript.

E leio hoje a notícia de um bug que é (ou foi) encontrado em quase todas as implementações de JavaScript. Para quem gosta de comparar desgraças, o bug existe em todas as versões do IE mas já foi corrigido no Firefox, Opera, iPhone e Chrome. Os piores efeitos ocorrem no Konqueror/Ubuntu onde o SO chega a reiniciar e em nos consoles Wii (c/Opera) e PS3, onde é necessário um hardware reset. Não chega a comprometer os dados da vítima, mas pode ser considerado um ataque Denial-of-service, principalmente se um mau elemento infiltrar o script em uma página de terceiros.

Por fim, é bom lembrar que alternativas como VBScript e ActiveX tem reputação ainda pior que o JavaScript.

Compactação - Parte 2

Em 1984 Terry Welch inventou uma implementação aperfeiçoada do algorítimo LZ78 que mencionamos na parte 1. Este algorítimo, o LZW, fez muito sucesso nos final dos anos 80, sendo usado no utilitário compress do Unix, nos programas ARC, PKARQ e PKZIP e nos formatos GIF e PDF.

Um dos motivos do sucesso do LZW foi a publicação por Welch de um artigo detalhado na revista Computer do IEEE (uma imagem digitalizada do artigo, em formato PDF, pode ser baixada daqui). O que pouca gente percebeu é que uma patente também tinha sido solicitada, com a Sperry Corporation como beneficiária. Pouco depois a Sperry se juntou com a Burroughs para formar a Unisys. Esta patente (que pode ser baixada daqui), virou assunto nos anos 90, quando a Unisys decidiu cobrar o licenciamento da Compuserve (criadora do formato GIF) e, mais tarde, dos sites que possuíam imagens no formato GIF. A patente expirou nos EUA em 2003, mas neste ponto o interesse pelo LZW já tinha caído, em parte devido à patente e em parte pelo uso do LZ77 para obter maiores taxas de compactação.

Um ponto curioso é que Welch é engenheiro eletrônico por formação, e a sua descrição original estava bastante voltada para a implementação do LZW em hardware. No artigo ele chega a mencionar que "a implementação do LZW em software é possível mas significativamente mais lenta", o que não o impediu de colocar na solicitação da patente exemplos de implementação em FORTRAN.

O algorítmo LZW se destaca por obter taxas altas de compactação (desde que os dados tenham alta redundância, é claro), processando os dados sequencialmente e uma única vez (isto é, não é preciso analisar todo o arquivo antes de compactar ou ter que ficar "indo e vindo" no arquivo) e sem consumir quantidades exorbitantes de memória (isto na época, hoje a memória necessária para implementar o LZW pode ser considerada minúscula).

O Algorítimo de Compactação

Vamos considerar inicialmente uma forma básica do algorítimo e depois ver alguns aperfeiçoamentos que podem ser feitos. Nesta forma básica, o "compressor" recebe os dados originais codificados em um código de um tamanho fixo (tipicamente bytes com 8 bits, para fins de exemplo vamos considerar que seja um texto codificado em ASCII) e gera os dados compactados codificados em um código com outro tamanho fixo, maior que o de entrada (vamos tomar como exemplo códigos de 12 bits). Note que isto significa que para dados não compactáveis pode ocorrer um aumento de tamanho (como vimos na parte 1, isto é inevitável).

O objetivo do algorítimo é ir associando aos códigos de saída sequências de caracteres consecutivos encontrados na entrada. Estas associações são armazenadas em uma tabela (que funciona como um dicionário para traduzir sequências de caracteres da entrada em códigos da saída). Isto é feito da seguinte forma:

1. Os primeiros códigos da tabela correspondem aos códigos de entrada. No meu exemplo, as primeiras 256 posições teriam os códigos da tabela ASCII. O resto das combinações do código de saída (no meu caso, 4096 - 256 códigos) vão ser usados para representar sequências.
2. Começamos com uma sequência vazia.
3. Lemos um caracter da entrada e o concatenamos à sequência atual.
4. Procuramos a sequência na tabela. Se ela já estiver lá, voltamos ao passo 3.
5. Se a sequência atual não está na tabela, colocamos na saída o código da última sequência reconhecida, colocamos a sequência atual na tabela, usamos o último caracter lido como a nova sequência atual e voltamos ao passo 3.

Simples, não?

Na descrição acima deixei de fora dois pontos triviais:

• No passo 3, se chegamos ao fim da entrada colocamos na saída o código da última sequência reconhecida e encerramos o algorítimo.
• No passo 5 pode ocorrer que a tabela esteja cheia. Neste caso (por enquanto) basta não colocar a sequência atual na tabela.

Um ponto não trivial é não guardar na tabela a sequência codificada com o código de entrada. A sequência a ser colocada é sempre composta de uma parte inicial que já está na tabela (e portanto tem um código de compactação já associado) seguido de um caracter. Portanto podemos compactar as sequência na tabela para a forma wc onde w é um código de compactação e c é um código de entrada.

Codificando de uma forma livre em C:

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
char c;    // caracter sendo examinado

prox = 256;
w = LeEntrada();
while (! Eof())
{
c = LeEntrada();
nw = Procura (c, w);
if (nw != 0)
{
 // achou na tabela
 w = nw;
}
else
{
 // não está na tabela
 EscreveSaida (w);
 if (prox < 4096)
 {
   Guarda (c, w, prox);
   prox++;
 }
 w = c;
}
}
EscreveSaida (w);

No pseudo-código acima, LeEntrada obtem o próximo byte dos dados a compactar e EscreveSaida escreve um código de compactação na saída (o que exige uma pequena "sambadinha", já que estamos falando em código de 12 bits que corresponde a 1,5 bytes).

O último ponto de interesse é como implementar de forma eficiente as rotinas Procura e Guarda usadas acima. A forma mais tradicional é usar uma tabela com hash. Uma função de hash converte o para (c, w) em um índice para a tabela. Na hora de guardar, verificamos primeiro se esta posição está livre; se sim é só guardar o para nela. Se a posição estiver ocupada, somos obrigados a fazer um rehash (o mais simples é usar a posição seguinte, circularmente) até acharmos uma posição livre. Na hora de procurar, calculamos o hash e verificamos esta posição. Se ela estiver vazia, o para não está na tabela. Se a posição estiver ocupada, precisamos conferir se contém o para desejado; se sim achamos. Se a posição está ocupada por outro par, somos obrigados a ir fazendo o rehash até achar o par ou posição vazia. Para reduzir as colisões, além de uma boa função de hash, usamos uma tabela maior que o mínimo necessário. Por exemplo, para guardar as 4096 combinações do código de 12 bits podemos usar uma tabela de 5021 posições (sugere-se pelo menos 20% maior e um tamanho primo).

Reparar que a tabela vai ocupar 5021*1,5 = 7532 bytes. No tempo em que um PC básico tinha 256K e era preciso trabalhar com segmentos limitados a 64K isto era uma memória razoável. Nos dias de hoje, mesmo se dando ao luxo de usar 2 bytes para cada entrada na tabela e consumir 10K, isto é (como diria o Patolino) desprezível.

O Algorítimo de Descompactação

A descompactação consiste basicamente em ir construindo a mesma tabela que o compactador criou e ir obtendo dela as sequências a serem gravadas na saída. Existe, porém, um caso patológico (previsto corretamente pelo Welch) em que o descompactador recebe um código que ainda não está na sua tabela. Para enter isto, vamos examinar em paralelo a compactação e descompactação da sequência XabXaXk (como se os códigos de saída do compactador entrassem diretamente no descompactador):

No passo final acima, o compactador emitiu o código 259 que ainda não é conhecido pelo descompactador. Felizmente este caso é único: sempre que o descompactador receber um código desconhecido basta considerar que ele equivale ao código anterior recebido (no caso 256) mais o primeiro caracter deste código (no caso X).

Indo direto ao código:

int prox;  // proximo código na tabela
int w;     // código a descompactar
int lw;    // último código a descompactar
char c, nc;

prox = 256;
w = LeEntrada();
EscreveSaída (w);
lw = w;
while (! Eof())
{
 w = LeEntrada();
 if (w >= prox)
 {
   // caso especial
   nc = EscreveSeqSaida(lw);
   EscreveSaida (c);
   c = nc;
 }
 else
   c = EscreveSeqSaida (w);
 if (prox < 4096)
 {
   Guarda (c, w, prox);
   prox++;
 }
 lw = w;
}

char EscreveSeqSaida (int w)
{
   while (w >= 256)
   {
       push(w.car);
       w = w.cod;
   }
   push (w);
   while (PilhaNaoVazia())
       EscreveSaida (pop());
   return w;
}

Apesar de eu ter usado os mesmos nomes da parte anterior, aqui LeEntrada lê um código compactado e EscreveSaída escreve um código descompactado.

A parte interessante está em EscreveSeqSaída. Ao converter um código compactado na sequência de caracteres descompactados, os caracteres são obtidos na sequência contrária e portanto é preciso uma pilha para gravá-los na ordem correta. Os códigos acima de 256 estão associados a um código compactado e um caracter, a notação w.code e w.car representa obter estas informações para o código w.

Aperfeiçoamentos

Os algorítimos acima são supreendentemente razoáveis. Além disso existem alguns aperfeiçoamentos que podem melhorá-lo ainda mais:

• O uso de códigos de compactação maiores, como 16 bits, possibilita armazenar um número maior de sequências, aumentando a probabilidade de codificação das sequências na entrada.
• O uso de um tamanho fixo nos códigos de saída é um desperdício, já que os códigos gerados vão crescendo de tamanho à medida em que a tabela é preenchida (no nosso exemplo, começamos gerando códigos de 9 bits mas os estamos gravando com 12 bits). O usao de códigos de tamanho variável complica a parte de entrada e saída mas permite uma compactação maior.
• Parar de atualizar a tabela quando ela enche é ruim no caso dos dados não serem uniformes ao longo de toda a entrada. Para melhorar isto, a tabela pode ser limpa (total ou parcialmente) quando encher e/ou quando for detectado que a taxa de compactação está caindo.

Referência Adicional

Além do livro do Mark Nelson (mencionado na parte 1) e dos textos de Welch (linkados no início desta parte) usei o artigo "Lossless Data Compression" de Steve Apiki, da revista BYTE de março de 1991 (do bom tempo em que as revistas de informática publicavam artigos técnicos e código).

A Seguir

Um exemplo mais real de LZW em C.

Assista a Palestras de Richard Feynman

Meu pai, como um bom físico, é fã de carteirinha de Richard Feynman. Em uma das minhas visitas para o EUA (em meados dos anos 90, quando internet e Amazon ainda não faziam parte da nossa vida) ele pediu para eu procurar um livro, "Surely You're Joking, Mr. Feynman!". Eu achei o livro ainda na ida, em uma livraria do aeroporto. Resolvi folhear o livro e acabei lendo ele durante toda a viagem e deixando encostado os livros que eu tinha comprado para mim.

Descobri hoje mais uma pessoa que é fã dele: Bill Gates. Entre outras coisas, Bill Gates aprecia as filmagens de uma série de palestras que Feynman deu em 1964. Aprecia tanto que ele comprou os direitos das filmagens e as está colocando na internet.

Um ponto que alguns podem levantar é que para assistir aos vídeos é preciso ter instalado o Silverlight da Microsoft. Eu considero que:

• Seria muito mais estranho se ele usasse um formato de um concorrente.
• A alternativa mais óbvia seria o Flash que também exige a instalação de um plugin.
• Existem outros materiais disponíveis em formato Silverlight, como mencionei antes ;)

Fonte da notícia: The Register (obs: o artigo fala que é preciso usar o IE mas funcionou bem comigo com o Firefox).

Link para os vídeos: http://research.microsoft.com/tuva

Compactação - Parte 1

Semana passada eu estava alterando um código que usa a Zlib (sobre a qual vou falar mais nesta série de posts) e resolvi relembrar um pouco sobre compactação de dados.

Compactação de dados sempre foi algo muito interessante, e teve um certo boom nos anos 80, quando os microcomputadores tinham discos pequenos e um modem rápido comunicava a 2400bps.

Princípios Básicos

A compactação de dados se baseia em reduzir a redundância contida nos dados. Existem vários tipos de redundância, que fazem com a mesma informação (ou algo bem próximo) possa ser codificada em menos bits. Alguns exemplos de redundância:

• limitações dos valores possíveis: imagine que você está usando um byte para guardar o resultado de um dado. Um byte é capaz de armazenar 256 combinações e você está usando somente 6.
• caracteres repetidos: em arquivos texto é comum termos sequências de zeros ou espaços.
• valor fixo em posições periódicas: como em um arquivo texto de colunas fixas, em uma coluna possui sempre o mesmo valor.
• probabilidade diferente dos valores: por exemplo, em um texto é bem mais comum as vogais que determinadas consoantes, porém usamos a mesma quantidade de bits para armazenar os dois.
• trechos repetidos: ainda considerando um texto, determinadas palavras se repetem várias vezes.

Do ponto de vista da Teoria da Informação, costuma se dizer que a compactação mede quanto de informação realmente existe nos dados. No livro Fundação, de Isac Asimov, tem um trecho onde os cientistas desenvolvem uma forma de extrair o conteúdo essencial de um texto; quando eles resolvem processar várias horas de discurso de um político, o resultado é nada! Curiosamente, dados aleatórios são pouco compactáveis, pois os seus valores são praticamente imprevisíveis.

Quando estamos falando em compactação de arquivos, normalmente estamos falando em compactação sem perdas (lossless), na qual os dados originais podem ser fielmente recuperados do arquivo compactado. Uma outra modalidade importante são as compactações com perda; exemplos diários são a compactação de imagens (JPEG), vídeo (DivX, etc) e áudio (MP3). A compactação com perda faz sentido nestes casos pois a nossa vista e audição são limitados e consideram como iguais coisas diferentes. Nesta série vou falar somente da compactação sem perdas.

Uma besteira que se ouve com frequência é que determinado programa ou algorítimo reduz o tamanho dos dados de x%, sem perda. Na verdade, a taxa de compactação depende sempre da entrada. Uma vez compactado um arquivo, a redundância diminui e a capacidade de compactação dele se reduz. Se existisse um algorítimo que sempre reduzisse de x%, independente dos dados, poderíamos passar por ele um arquivo, pegar a saída e passar de novo, assim por diante, até ficar com um único byte (que obviamente não é capaz de representar toda a gama de arquivos possíveis).

Aliás, isto mostra que se um algorítimo sem perda é capaz de reduzir o tamanho de determinado tipo de arquivos, ele deve aumentar o tamanho de outros.

Algorítimos de Compactação

A forma mais eficiente de compactar um determinado tipo de arquivo é um algorítimo específico, feito por quem sabe o que pode estar no arquivo. Um exemplo clássico americano é o código usado por Paul Revere para ser avisado por onde as tropas britânicas estavam vindo: uma lanterna se por terra e duas se por água. Uma informação complexa foi reduzida a um bit, graças ao conhecimento da situação. Uma outra forma que pode ser eficiente é o uso de tabelas de código, ou dicionários.

Os algorítimos que vamos ver aqui, entretanto, se propõem a ser genéricos e não depender de tabelas ou dicionários mantidos externamente.

Codificação de Huffman

Normalmente usamos o mesmo número de bits para cada unidade de informação ou símbolo (como um caractere ou par de caracteres), independente da sua probabilidade. A Codificação de Huffman utiliza códigos de tamanho variável, atribuindo códigos menores para os símbolos mais frequentes. Desta forma o tamanho médio (bits por símbolo) é reduzido.

A codificação de Huffman apresenta alguns problemas práticos:

• Requer que a probabilidade dos símbolos seja conhecida, o que pode ser feita por uma análise prévia dos dados a codificar. Alternativamente pode-se usar uma estimativa ou analisar uma amostra dos dados, mas isto introduzir um erro.
• A codificação usa um número inteiro de bits por símbolo e portanto pode não retratar com precisão as probabilidades.
• A probabilidade dos símbolos pode não ser constante ao longo de um conjunto de dados. Por exemplo, um arquivo pode ter um cabeçalho no início com uma distribuição de probabilidades bem diferente do resto.

Apesar disso, a codificação de Huffman era predominante até o início dos anos 80. Atualmente ainda é usada mas como uma codificação auxiliar.

Run-Length Encoding

Uma forma bastante intuitiva de compactar dados é usar uma notação especial para, por exemplo, representar sequências de zeros ou espaços (por exemplo, passando de um formato de colunas fixas para um de campos separados por delimitadores).

A Run-Length Encoding (RLE) é uma generalização disto. A ideia é substituir repetições consecutivas de um código por uma indicação de repetição, o número de repetições e o código a repetir.

Tomando um exemplo hipotético de compactação de uma sequência de bytes por RLE:

• Uma sequência de um ou dois bytes iguais, diferentes de 0xFE, é copiada inalterada para a saída.
• Uma sequência de três ou mais bytes iguais ou uma sequência de um ou dois 0xFE, é compactada na sequência 0xFE repetições byte.

Por exemplo, a sequência 01 01 02 02 02 02 02 02 02 FE é compactada em 01 01 FE 06 02 FE 01 FE. A descompactação é trivial:

• Bytes diferentes de 0xFE são copiados inalterados para a saída.
• Se for encontrado 0xFE, copiar para a saída n repetições do byte b, onde n e b são os bytes que seguem o 0xFE.

Obviamente esta codificação será eficiente na medida em que a marca 0xFE for pouco frequente e ocorrerem sequências longas do mesmo caracter.

Um exemplo de situação em que a compatação por RLE pode ser vantajosa é em gráficos monocromáticos, principalmente se desenhados à mão.

O MacPaint e o formato TIFF podem utilizar uma compactação deste tipo. A descompactação é feita da seguinte forma:

1. Examina-se o byte seguinte do arquivo compactado (b).
2. Se o bit mais significativo for zero, copiar os b+1 bytes seguintes para a saída (bytes não compactados)
3. Se o bit mais significativo for um, repetir o byte seguinte -b vezes.
4. Voltar ao passo 1.
   

Lempel-Ziv

No final dos anos 70, Jacob Ziv e Abraham Lempel descreveram dois métodos de compactação que são a base das compactações mais comuns hoje, como a dos arquivos ZIP. Os dois métodos se baseiam na ideia de construir dinamicamente um dicionário para codificar os dados.

O primeiro algorítimo (conhecido como LZ77) utiliza uma janela que vai se deslocando por sobre os dados à medida em que são tratados. À medida em que os dados são examinados, verifica-se se eles já apareceram na janela, se sim no lugar dos dados é transmitida a posição e o tamanho da sequência na janela.

O segundo algorítimo (LZ78) vai montando um dicionário incremental à medida que os caracteres são lidos. Por exemplo, suponhamos que a sequência 'Daniel' é encontrada no início. O string 'Da' é colocado no dicionário. Mais adiante encontra-se a sequência 'Dante'; como 'Da' já é conhecido, colocamos 'Dan' no dicionário. Encontrando novamente 'Daniel', coloca-se 'Dani' no dicionário e assim por diante.

À primeira vista estes algorítimos são bastante intensivos em processamento e não parecem ser a melhor forma de montar um dicionário. A prática, entretanto, mostra que consegue-se obter grandes taxas de compactação para arquivos como boa redundância, como textos.

O problema do processamento foi inicialmente resolvido por uma implementação muito elegante de uma variação do LZ78, criada por Terry Welch. É este algorítimo (LZW) que veremos na próxima parte desta série.

Mais para o final dos anos 80, com o aumento da capacidade computacional disponível, o LZ77 passou a ser usado com mais frequência.

Bibliografia

Estes dois livros do começo dos anos 90 foram bastante úteis na época:

• The Data Compression Book, Mark Nelson. A teoria no livro é boa, mas os exemplos no disquete que acompanhava tinham bugs!
• Bit-Mapped Graphics, 2n Edition, Steve Rimmer. Foi aqui que eu aprendi a ler arquivos PCX, TIFF e GIF.

DVD: Jackie Brown

Estou longe de ser um fã do Tarantino, mas este filme é um caso especial. Talvez seja a semelhança com os policiais noir.

A primeira vez que vi este filme foi alugado. Depois comprei em uma destas promoções da Folha. Acabei emprestando para alguém que não devolveu, mas foi fácil achar outro por R$15,00.

Resumindo a trama: Ordell (Samuel L. Jackson) é um traficante de armas, que movimenta o seu dinheiro entre os EUA e o México através da aeromoça Jackie Brown (Pam Grier). Ray (Michael Keaton) é o policial que quer prender Ordell e para isto dá uma prensa na Jackie, colocando-a na cadeia. Para tirá-la da cadeia, Ordel contrata o agente de fianças Max (Robert Forster), que tem pose de durão mas se apaixona por Jackie. Melanie (Bridget Fonda) é namorada de Ordell, loura e malucona. Louis (Robert De Niro) é o capanga abobalhado de Ordell. Jackie vai fazer uma última viajem, para trazer meio milhão do México, mas estão todos pretendendo trair todos.

Samuel L. Jackson, como de costume, está excelente. Só o jeito dele falar já vale assistir (e tem gente que gosta de versões dubladas...). Pam Grier se encaixa perfeitamente no papel da aeromoça em fim de carreira, pressionada por todos os lados. Robert Forster também cai como uma luva no personagem. Robert De Niro é que me perturba um pouco, por interpretar bem demais o papel de um bobalhão.

O filme tem alguns dos truques costumeiros do Tarantino. O destaque é a cena da passagem do dinheiro, dentro de um shopping, que é repetida várias vezes nos ângulos dos vários personagens.

Um detalhe para quem for ver o filme com legendas em português: reparei que em alguns pontos, provavelmente para reduzir a quantidade de texto, alguns trecho são bem simplificados. Coincidência ou não, os palavrões parecem ter preferência nos cortes.

Se você for fã do Tarantino ou do Samuel L. Jackson, ou gostar de policiais noir, não deixe de ver este filme.

Eu gostei tanto do filme que acabei indo atrás da trilha sonora.


A seleção de músicas é bem diversa, e o CD inclui ainda alguns trechos de diálogo do filme.