sexta-feira, julho 31, 2009

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


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


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


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

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.
Posted by Daniel Quadros at 07:00 0 comentário(s)
Categorias:

quarta-feira, julho 29, 2009

Falhas de Segurança em Biblioteca Microsoft Requer Providências dos Desenvolvedores

Os mais atentos devem ter percebido que a Microsoft disponibilizou ontem duas atualizações fora do cronograma normal. A instalação destas atualizações, entretanto, não é suficiente para retirar a vulnerabilidade das aplicações afetadas. Para isto é necessário re-gerar a aplicação, utilizando uma nova versão da biblioteca e alterando algumas construções no código fonte.

ATL

As falhas de segurança foram encontradas na Active Template Library (ATL). O corpo da ATL é um conjunto de templates C++ que gera classes para facilitar o desenvolvimento de objetos COM.

Se você não tem alguma familiaridade com C++ e COM, a frase anterior não deve ter feito sentido. Tentando explicar
  • COM (Component Object Model) é uma especificação para interface entre objetos criada pela Microsoft no começo dos anos 90. Entre seus vários usos se destacam os controles ActiveX usados (principalmente) para fornecer funcionalidades adicionais ao IE e aplicações VB.
  • Um template C++ é um recurso que permite definir funções e classes usando tipos genéricos. O compilador se encarrega de gerar versões das funções ou classes específicas para os tipos necessários. Por exemplo, pode-se criar um template para uma classe que implementa uma pilha de objetos de um tipo T (genérico) e depois usar este template para declarar pilhas de tipos int, float, etc.
A criação de um objeto COM pode ser algo bastante complicado e trabalhoso. A ATL e o Visual Studio simplificam isto, permitindo agregar uma grande quantidade de código pronto e gerar automaticamente mais um outro tanto. O programador pode se concentrar nas funcionalidades do seu objeto e deixar o "encanamento" por conta da ATL. Ótimo, até que se descubra uma falha no código da ATL.

As Atualizações de Segurança

As atualizações liberadas ontem consistem em uma atualização da ATL e uma atualização no IE. A atualização no IE tem por objetivo evitar que as falhas na ATL sejam exploradas através de componentes hospedados no IE. Uma das possíveis explorações é burlar uma proteção usada no IE para bloquear componentes nocivos. Em outras palavras, explorando a falha na ATL pode-se "ressuscitar" falhas já bloqueadas.

Como Saber Se o Seu Componente é Afetado

O boletim de segurança da Microsoft apresenta um fluxograma (vocês ainda lembram disso) para determinar se um componente é afetado. Se não me perdi nas setas, um componente é afetado se atender a pelo menos uma das seguintes condições:
  • Chame CComVariant::ReadFromStream com dados não confiáveis.
  • For um componente COM, marcado como SFI, que herde de IPersistStreamInitImpl ou não herde mas chame AltPersistStreamInit_Load e use PROP_ENTRY / PROP_ENTRY_EX ou use PROP_ENTRY_TYPE / PPROP_ENTRY_TYPE_EX com VT_EMPTY, VT_DISPATCH ou VT_UNKNOWN
Se você desenvolveu um software que se encaixe nestas condições, leia com atenção o boletim para ver os passos necessários para corrigir a vulnerabilidade no seu software.

Fonte: The Register.
Posted by Daniel Quadros at 08:39 0 comentário(s)
Categorias: , ,

terça-feira, julho 28, 2009

Detalhes da Proposta da Microsoft à EC

Completando o post de ontem, segue o link para os detalhes disponibilizados pela Microsoft:

http://www.microsoft.com/presspass/press/2009/jul09/07-24statement.mspx

No texto a Microsoft afirma que até a EC (European Commission) se manifestar sobre a nova proposta considera obrigatória o fornecimento na Europa da versão E do Windows 7 (sem IE) pelos fabricantes de computadores.

A página tem um link para um arquivo com a proposta de tela de seleção do browser (um PPT com uma única imagem - DUH!):

clique para ampliar

Reparar que a página roda dentro do IE. Tecnicamente faz sentido, já que precisa ter links para as páginas de informações e download dos browser concorrentes, mas certamente vai deixar algumas pessoas descontentes.

O CTO da Opera já manifestou seu descontentamento: acha inapropriado o uso do logotipo do IE na tela. Logo por logo, acho que a Google levaria vantagem.

Continuo com o receio da moda pegar. Será que teremos tela de seleção para outros aplicativos do Windows (mail, tocador, calculadora, desenho, etc)? Ou talvez exigir o mesmo de outros sistemas operacionais (como a Opera já insinuou)? O que será que a Opera acha do Chrome OS?
Posted by Daniel Quadros at 07:54 0 comentário(s)
Categorias:

segunda-feira, julho 27, 2009

Microsoft Cede e Oferecerá Lista de Browsers

Num lance inesperado, a Microsoft propôs no final da semana passada colocar uma tela de seleção de browser no Windows. O anúncio oficial da comunidade europeia (aqui) é bastante frio e não traz muitos detalhes.

O The Register traz alguns detalhes adicionais (aqui), mas não cita suas fontes. Segundo eles:
  • a tela de seleção será oferecida como uma atualização para o XP e Vista e estará nas novas versões (Windows Seven, provavelmente).
  • a tela de seleção oferecerá os cinco browser com maior fatia de mercado na média dos últimos seis meses (não dá detalhes de como isto seria medido).
  • o IE estará disponível para instalação junto com o Windows, para os demais será apresentado um link para download.
  • usuários e OEMs terão a opção de desativar o IE, deixando-o inacessível.
  • a Microsoft disponibilizará documentação sobre a integração do IE ao Windows, de forma a permitir que browser concorrentes possam oferecer as mesmas funcionalidades.
Se a comunidade europeia não mostrou entusiasmo alé de um "welcomes new Microsoft proposals", alguns são expressamente céticos quanto ao resultado desta tela. A Opera já está sugerindo que a Apple e o Ubunto adotem telas semelhantes.

Meus comentários e palpites:
  • Acho que a Microsoft cansou desta lenga-lenga e está muito confiante no IE, daí a proposta.
  • Vai ter gente exigindo que a ordem da lista e o default sejam aleatórios.
  • Se a coisa for em frente, os geeks europeus que se preparem para quando a mãe ou amigo leigo ligar dizendo que "a internet está diferente no micro novo" (você acha que eles vão entender o menu e fazer uma escolha consciente?).
  • O Firefox deve continuar a ter participação crescente, mas com tendência a estabilizar. Isto pode variar dependendo de novas versões maravilhosas ou catastróficas do Firefox ou IE.
  • Google Chrome vai continuar correndo por fora, mas precisa encontrar um bom chamariz de usuários. O IE tem a tradição, o Firefox tem os add-ons.
  • O Opera continuará na rabeira.
Agora vamos ver a Coca Cola propor colocar uma lata de Pepsi nos seus six-packs.
Posted by Daniel Quadros at 13:30 0 comentário(s)
Categorias:

Preparação e Metas para o Google Code Jam 2009

Confirmada a realização do Google Code Jam 2009, é hora de planejar a minha preparação e definir minhas metas. No meu post após o meu insucesso na segunda rodada do ano passado, eu listei os pontos em que julguei me faltar preparação.

No ano passado eu adquiri uma série de livros (baseado em recomendações em forums e nas avaliações na Amazon) para cobrir alguns destes pontos:
  • The Art and Craft Of Problem Solving, de Paul Zeitz: um livro sobre estratégias, técnicas e ferramentas para a solução de problemas. É mais voltado para competições de matemática que de programação.
  • How to Solve It, de G Polya: um texto clássico sobre a solução de problemas. Embora o enfoque seja a matemática, várias resenhas afirmam que o livro pode ser útil para qualquer tipo de problema.
  • Introduction to Algorithms, de Cormem, Leiserson, Rivest e Stein: segunda edição de um livro clássico (conhecido como CLR ou CLRS) . Cobre de bem forma bem completa os algorítimos básicos.
  • Geometry Revised, de Coxeter e Greitzer: um livro que cobre pontos normalmente negligenciados no ensino de matemática do ginásio e colegial.
Infelizmente estes livros foram direto para a estante e ficaram lá até agora. Faltando seis a oito semanas para a rodada de qualificação do Google Code Jam 2009, é impossível ler todos com a devida atenção. Pretendo dar pelo menos uma folheada em todos, dando atenção especial ao primeiro da lista.

Junto com este estudo pretendo tentar fazer alguns dos problemas restantes do ano passado (disponíveis aqui) e de outras competições como Maratonas de Programação dos anos passados (aqui) assim como os disponíveis nos arquivos de problemas listados na Wikipedia. Na medida em que conseguir e o tempo deixar vou postar as soluções aqui, como forma de fixação para mim e como ajuda ou curiosidade para os outros.

Ao final da competição do ano passado, a minha meta para este ano era participar da rodada on-site brasileira. Infelizmente, este ano esta rodada foi abolida. Minhas metas passam a ser chegar à terceira rodada e conseguir não zerar nela. A julgar pelo meu desempenho no ano passado (passei raspando na primeira rodada e zerei na segunda) são metas bastante audaciosas.
Posted by Daniel Quadros at 07:00 0 comentário(s)
Categorias:

terça-feira, julho 21, 2009

Google Code Jam 2009

O suspense está no fim: a página do Google Code Jam foi atualizada! As datas ainda não estão definidas, mas a inscrição deve começar em meados de agosto e a rodada de qualificação será quatro semanas depois.

Aparentemente vão cortar alguns custos, este ano a final nos EUA terá somente 25 pessoas.

Atualização: e-mail recebido do Google Groups "Google Code Jam Announcements":
Code Jam is back!

We're excited to announce Google Code Jam 2009, this year's iteration of
Google's annual programming competition, which offers coders from around the
world an opportunity to solve complex algorithmic problems under time
pressure, using the programming languages and tools of their choice.
The contest will have a new format this year, starting with online rounds
and ending in a 25-person final in our Mountain View, California
headquarters. We're still choosing exact times for everything, but for
planning purposes we wanted to give you this tentative schedule. Please note
that the timing may change:

Early-Mid August: Registration will open.
+4 Weeks: Qualification round
+1 Week: Rounds 1A, 1B, 1C
+1 Week: Round 2
+1 Week: Round 3
November: World Finals in Mountain View

Online rounds begin soon, so start practicing!

The Google Code Jam Team
http://code.google.com/codejam


Posted by Daniel Quadros at 10:19 0 comentário(s)
Categorias:

Lunar Lander - The Real Thing

Se alguem gostou do brinquedo que eu mostrei ontem, vai se interessar em dar uma olhada no produto genuíno:

http://feedproxy.google.com/~r/GoogleCodeNews/~3/Zz-WqUnz1Wk/apollo-11-missions-40th-anniversary-one.html

Na notícia acima, tem links para um emulador do computador de navegação da Apollo e as listagens do software original. Tem também o link para a inevitável página da Wikipedia, aonde achei um link para uma descrição de como montar uma reprodução funcional no seu porão - como a minha casa não tem porão, acho melhor nem pensar nisto ;)
Posted by Daniel Quadros at 09:59 0 comentário(s)
Categorias: , ,

segunda-feira, julho 20, 2009

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.
Posted by Daniel Quadros at 07:00 3 comentário(s)
Categorias: , ,

sábado, julho 18, 2009

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.
Posted by Daniel Quadros at 09:30 0 comentário(s)
Categorias: ,

sexta-feira, julho 17, 2009

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.
Posted by Daniel Quadros at 13:57 0 comentário(s)
Categorias:

quinta-feira, julho 16, 2009

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:
view plaincopy to clipboardprint?
  1. int prox;  // proximo código de saída  
  2. int w;     // código da sequência atualmente conhecida  
  3. int nw;    // código da nova sequência  
  4. char c;    // caracter sendo examinado  
  5.   
  6. prox = 256;  
  7. w = LeEntrada();  
  8. while (! Eof())  
  9. {  
  10. c = LeEntrada();  
  11. nw = Procura (c, w);  
  12. if (nw != 0)  
  13. {  
  14. // achou na tabela  
  15. w = nw;  
  16. }  
  17. else  
  18. {  
  19. // não está na tabela  
  20. EscreveSaida (w);  
  21. if (prox < 4096)  
  22. {  
  23.   Guarda (c, w, prox);  
  24.   prox++;  
  25. }  
  26. w = c;  
  27. }  
  28. }  
  29. 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).

Cada entrada na tabela vai conter o código que está sendo armazenado, o código do prefixo e o caracter final. Reparar que a tabela vai ocupar 5021*4 = 20084 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 código na tabela e consumir 25K, isto é (como diria o Patolino) desprezível.

O Algorítimo de Descompactação

A descompactação consiste basicamente em ir construindo uma tabela com os códigos 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:
view plaincopy to clipboardprint?
  1. int prox;  // proximo código na tabela  
  2. int w;     // código a descompactar  
  3. int lw;    // último código a descompactar  
  4. char c, nc;  
  5.   
  6. prox = 256;  
  7. w = LeEntrada();  
  8. EscreveSaída (w);  
  9. lw = w;  
  10. while (! Eof())  
  11. {  
  12. w = LeEntrada();  
  13. if (w >= prox)  
  14. {  
  15.   // caso especial  
  16.   nc = EscreveSeqSaida(lw);  
  17.   EscreveSaida (c);  
  18.   c = nc;  
  19. }  
  20. else  
  21.   c = EscreveSeqSaida (w);  
  22. if (prox < 4096)  
  23. {  
  24.   tab[prox].w = w;  
  25.   tab[prox].c = c;  
  26.   prox++;  
  27. }  
  28. lw = w;  
  29. }  
  30.   
  31. char EscreveSeqSaida (int w)  
  32. {  
  33.   while (w >= 256)  
  34.   {  
  35.       push(tab[w].car);  
  36.       w = tab[w].w;  
  37.   }  
  38.   push (w);  
  39.   while (PilhaNaoVazia())  
  40.       EscreveSaida (pop());  
  41.   return w;  
  42. }  
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.

A tabela para o descompactador é mais simples, pois não precisamos fazer uma procura por prefixo + caracter. O código pode ser usado diretamente como índice e cada entrada contém apenas o código do prefixo e o caracter final.

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.


Atualizado em 30/07/09 para acertar a descrição das tabelas.
Posted by Daniel Quadros at 07:00 0 comentário(s)
Categorias:

quarta-feira, julho 15, 2009

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
Posted by Daniel Quadros at 17:39 3 comentário(s)
Categorias: ,

terça-feira, julho 14, 2009

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.
Posted by Daniel Quadros at 07:00 2 comentário(s)
Categorias:

domingo, julho 12, 2009

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.
Posted by Daniel Quadros at 07:00 3 comentário(s)
Categorias: ,

sábado, julho 11, 2009

Netbooks, Sub-notebooks, Network Computer e o Google OS

É interessante como algumas ideias se repetem periodicamente. São ideias interessantes mas que por um motivo ou outro nunca se realizam plenamente. Repete-se assim um ciclo de anúncio, interesse, desinteresse e esquecimento. Em alguns casos a ideia consegue sucesso após algumas iterações, quando a tecnologia evoluiu ou mudaram os gostos do público alvo.

Computadores pequenos, leves, baratos e voltados para determinados tipos de aplicação é uma destas ideias.

Em 1992, a Olivetti lançou o Quaderno, um notebook DOS com tamanho A5 (metade de uma folha de papel A4), tela de 7.5" e peso da ordem de 1Kg. É provável que alguém ache um exemplo ainda mais antigo. Ainda na primeira metade dos anos 90, tivemos uma onda de sub-notebooks, como O Handbook da Gateway e o Omnibook da HP.

Na segunda metade, a onda de computadores pequenos foi impulsionada pelo padrão H/PC da Microsoft, baseado no Windows CE.

Em 2005 o conceito voltou à tona com o anúncio do "laptop de 100 dolares". Dai surgiram o Eee PC e uma multidão de computadores designados de netbooks.

O problema com estes computadores e que para serem pequenos e baratos é preciso fazer certos compromissos. E muitos usuários não compreendem isto. O resultado é a frustração de descobrir que o seu novo netbook não é apropriado para executar alguma aplicação que você considera vital. Quando os netbooks se aproximam em funcionalidade com o notebook o preço sobe e surge o argumento "por um pouco mais eu compro um notebook 'de verdade'".

Um efeito parecido ocorre com o software. Embora faça sentido oferecer um sistema operacional mais otimizado (como uma versão custom do Linux), os usuários preferem o Windows.

Tudo isto vem à tona no momento em que a Google anuncia o "Chrome OS", voltado para netbooks. O Chrome OS recicla também um outro conceito que não conseguiu sucesso total até agora: o Network Computer. Na geração anterior, quando se proclamava também que "o browser é sistema operacional", a idéia era os NCs se conectarem a servidores internos, restaurando em parte o poder centralizado da era dos mainframes. Na nova encarnação, os computadores com o Chrome OS irão se conectar à "grande nuvem da internet".

Me parece que a Google vai ter um bom trabalho pela frente para vender esta idéia. Além do problema de aceitar os compromissos, que limita hoje a aceitação dos netbooks, os compromissos aqui serão mais fortes. No modelo proposto pela Google, dados e aplicações ficam na internet e não armazenados localmente. As aplicações são aplicações Web e não aplicações nativas. Conectividade próxima da constante será essencial.

A Google conseguiu uma lista de parceiros de hardware de chamar a atenção: Acer, Asus, Freescale, Hewlett-Packard, Lenovo, Qualcomm, Texas Instruments, and Toshiba. Entretanto, a história mostra que aparecer nestas listas não é sinônimo de comprometimento com a plataforma.. Todos estes fabricantes apostam simultaneamente em várias plataformas. Em alguns casos o custo para entrar na lista é baixo frente à divulgação que se vai conseguir. É mais ou menos como na virada do século, onde toda empresa procurava um jeito de colocar a palavra Linux nos seus press-releases, só para aparecer na midia.

É possível que o anúncio leve a Microsoft a rever os seus planos para o Windows Seven em netbooks, levantando algumas das restrições que supostamente ela vai impor. Se isto acontecer, vai ficar mais marcante a comparação de funcionalidades entre as plataformas (lembrando que um netbook com o Seven provavelmente vai ser maior, mais pesado, mais caro - e capaz de rodar o browser Chrome).

Vamos ver se o ciclo dos computadores pequenos será quebrado ou se daqui a dois anos o Chrome OS estará restrito a um pequeno nicho.
Posted by Daniel Quadros at 07:00 0 comentário(s)
Categorias: , ,

quinta-feira, julho 09, 2009

Controlando MUITOS Leds

Nos projetos que eu apresentei até agora, cada LED era ligado diretamente a um pino do microcontrolador. Embora este tipo de conexão seja bastante simples, esbarramos logo no limite de pinos de E/S do microcontrolador.

Além dos LEDs comuns, muita vezes queremos conectar displays de 7 segmentos (que correspondem a 7 LEDs por dígito) ou matrizes de LED (por exemplo com 5x7 LEDs para cada caracter).


Uma primeira maneira de expandir a capacidade de I/O do microcontrolador é usar registradores de entrada serial e saída paralela. Um exemplo é o 74HC595, que recebe bits serialmente e os armazena em um shift register de 8 bits que pode ser copiado para um registrador de saída. Um 74HC595 isolado requer pelo menos 3 I/Os (dado, clock do shift register e clock para cópia para a saída). Podemos cascatear vários CIs para gerar um registrador de mais bits, mas é óbvio que a escalabilidade desta solução é limitada.

A solução mais utilizada é baseada no mesmo princípio usado no Spoke-o-dometer, a persistência de visão. Ao invés de controlar todos os LEDs ao mesmo tempo, organizamos os LEDs em uma matriz de linhas e colunas e controlamos uma linha de cada vez. Enquanto uma linha está sendo controlada as demais ficam apagadas. Fazendo isto bem rápido, não se percebe que os LEDs estão piscando. Este método é chamado de multiplexação.

O diagrama abaixo mostra o circuito básico, com duas linhas de duas colunas:

No diagrama acima as linhas estão conectadas aos catodos dos LEDs. Um LED é aceso quando a linha correspondente está em "0" e a coluna em "1". Uma solução simétrica pode ser feita com os LEDs conectados de forma contrária.

Somente uma linha fica ativa de cada vez, é preciso fazer a varredura das linhas. No circuito acima um pino seleciona qual das duas linhas está ativa. Em um circuito mais genérico, n pinos do microcontrolador são decodificadas em 2n linhas. Por exemplo, podem ser usados o 74HC138 (3 para 8) ou 74HC154 (4 para 16). Uma outra alternativa para varrer as linhas é usar um shift register externo (como o 74HC164).

O problema no circuito acima é a corrente nas linhas. Cada coluna aciona no máximo um LED por vez, portanto equivale a ter um único LED. Uma linha, entretanto, pode estar recebendo a corrente de múltiplos LEDs (considerando o que a linha está conectada aos catodos dos LEDs), o que pode ultrapassar a capacidade de um pino do microcontrolador.

A solução é controlar as linhas por um transistor, por sua vez controlado pelo pino do microcontrolador. A corrente de cada LED é controlada por um resistor na coluna. Este tipo de solução (usar um transistor para aumentar a capacidade de corrente de um pino de E/S) é tão comum que existem CIs com um "vetor" de transistores. É o caso do ULN2003 e do ULN2803.

Existem CIs dedicados ao controle de LEDs que além de controlar correntes altas permitem que esta corrente seja determinada por um único resistor externo. O CI STP16CP05 (que infelizmente não achei para venda aqui no Brasil) é uma solução bastante completa. Ele recebe 16 bits serialmente e os coloca em uma saída paralela de corrente constante determinada por um resistor.

O "topo de linha" é talvez o MAX7221 (que também não achei por aqui). Além da entrada serial e do driver de corrente constante, ele possui uma memória interna de 8 bytes, executando ele próprio a varredura das linhas. O "espertinho" é capaz até de acionar os segmentos corretos para representar os valores 0 a F em um display de 7 segmentos.

Para encerrar, algumas referências a projetos com um microcontrolador controlando uma quantidade grande de LEDs:
  • PEGGY2: um display com até 625 LEDs.
  • MeggyJr: a irmã menor da PEGGY, um circuito portátil com uma matriz de 8x8 LEDs RGB.
  • Mignonette: um jogo miniatura, com uma tela composta por uma matriz de 5x7 LEDs bicolores.
Estou com algumas idéias de projetos relacionados a LEDs na cabeça; se tudo correr bem veremos alguns deles por aqui nos próximos meses.
Posted by Daniel Quadros at 07:00 1 comentário(s)
Categorias:

terça-feira, julho 07, 2009

Windows Vista: Divagações Sobre Um Não-Desastre

Agora que estamos chegando próximos ao lançamento do Windows Seven, gostaria de divagar um pouco sobre o Vista. Muitos consideram o Vista um desastre; eu não chego a tanto.

É indiscutível que o Vista é um dos sistemas operacionais da Microsoft de pior aceitação por parte de empresas e usuários (embora MSDOS 4, OS/2 1 e 2 e Windows Me estejam bem contados neste ranking sinistro). Piadas, ironias e discursos irados estão em todos os cotovelos dos "tubos" da internet.

Mas é o Windows Vista Um Desastre?

O Vista certamente se encaixa na categoria de projetos que estouraram prazo e orçamento e não implementaram as funcionalidades previstas.

Mas o Windows Vista foi liberado para os usuários. Somente este fato já o coloca na frente de muitos outros projetos (uma estimativa educada é que 30% dos projetos de TI são cancelados ou abandonados).

No caminho foram abandonadas várias funcionalidades, mas o corte de funções é a única forma garantida de reduzir o prazo de desenvolvimento, principalmente para um projeto que está saindo do controle.

Embora existam muitas reclamações dos usuários, são raras as menções a perda de dados. Os problemas mais relatados se referem a usabilidade, compatibilidade, performance e falta de suporte a hardwares antigos.

A rejeição ao Vista não causou uma corrida em massa para Linux ou Mac. A principal alternativa adotada tem sido o XP. Os fabricantes de micro deram algumas pequenas esperneadas mas seguiram firme fornecendo os micros novos com o Vista.

O Que Deu De Errado?

Experts e palpiteiros tem opinado sobre o que deu de errado no desenvolvimento do Vista. Três teorias que considero interessantes são as seguintes:
  • Erik Sink pondera que o Windows é um produto que ficou pronto e não precisava de novas versões. Eu discordo. Novos recursos tem surgido no hardware e novos usos para computadores continuam surgindo; os sistemas operacionais precisam evoluir para suportá-los.
  • Uma outra teoria (cujo link não consegui recuperar) é que um líder da divisão Windows só aguenta três versões: uma recuperação de uma mau produto, um bom produto e um mau produto (quando a liderança já está exausta). Me parece um pouco forçado, mas pode ter algum fundamento.
  • Joel Spolsky defende há tempos a teoria de que existem dois grupos em luta na Microsoft: o que prioriza a compatibilidade e o que prioriza a evolução. E que o segundo ganhou a luta na virada do século. Esta é a teoria que acredito explicar a maior parte do problema.
É claro que não são exatamente dois grupos em luta. Todo desenvolvedor enfrenta internamente decisões entre compatibilidade e aperfeiçoamentos. Na manutenção do Windows estas questões são bem mais críticas que na maioria dos softwares, basta ver os relatos no blog de Raymond Chen.

Dada a hegemonia da Microsoft, seria de se esperar que ela fosse extremamente conservadora. Manter o núcleo dos produtos e apenas mudar algumas cores e ícones, acrescentar algum acessório a mais e chamar o resultado de uma nova versão.

O surpreendente, portanto, é que a Microsoft decidiu se aventurar no Vista e mexer mais profundamente no Windows. No centro da maioria das reclamações estão mudanças em tradições antigas da Microsoft, visando aumentar a segurança do sistema.

O Sucesso (até agora) do Windows Seven

Quando o Vista finalmente saiu, alguns anunciaram que era o fim do Windows, que a Microsoft não conseguiria reunir forças para lançar novas versões. E no entanto muito rapidamente surgiu o primeiro beta do Windows Seven, que vem sendo saudado como rápido, estável, etc.

Uma boa fonte sobre o que foi feito no Seven é o blog Engineering Windows 7. Apesar de infelizmente o texto final parecer ter saído de marketing-droids fica claro uma coisa: o Seven é um ajuste do Vista. Foram feitas otimizações, arestas foram polidas, mas nenhuma mexida profunda foi feita. Isto mostra que as fundações do Vista são sólidas.

É claro que o Seven se beneficia também do tempo desde o lançamento do Vista. Os micros são mais rápidos e com mais memória, muitas placas e acessórios antigos já foram para o lixo e os novos já vieram com drivers para Vista.

Pode-se perguntar: não teria sido melhor a Microsoft segurar o lançamento do Vista, fazer estes ajustes, e lançar direto o Seven? Não me parece que isto teria sido possível pois:
  • O projeto já tinha durado de mais. "Chutar" o Vista para fora deve ter dado um respiro psicológico vital para a equipe do Windows.
  • O Vista em campo fornece realimentação e informação muito melhor que qualquer beta teste. Um beta teste pode ser eficaz para detectar bugs, mas é tipicamente feito por fãs que podem não ser críticos o suficiente com questões de usabilidade. Isto é também um alerta para o Seven.
  • O uso do Vista força as pessoas a abandonarem as práticas que são mais suportadas. O Seven vai manter muitas coisas que foram motivo de resmungo nos primeiros seis meses a um ano do Vista.
  • A presença do Vista em campo força os desenvolvedores a fazerem os acertos para resolver os problemas de compatibilidade.
Meu Veredito

Apesar de várias falhas e erros, o Vista não chega a ser um desastre. A Microsoft conseguiu domar um projeto que fugia do controle e liberá-lo com qualidade suficiente para não enfurecer demais os clientes. E ainda encontrou forças para fazer posteriormente uma quantidade suficiente de ajustes para torná-lo atraente.

Ainda é muito cedo para saber se o Seven receberá da maioria dos usuários a mesma recepção que tem obtido no beta teste. O Seven manterá uma série de mudanças em relação ao XP e versões anteriores; se o ganho na segurança compensará os desconfortos só o tempo dirá.
Posted by Daniel Quadros at 07:00 1 comentário(s)
Categorias:

domingo, julho 05, 2009

Virus Paraliza DQSoft por Uma Semana!

Ok, não resisti a um título digno do jornalismos dos dias de hoje.

Não estou falando de vírus de computador, nem da Gripe A (tcc H1N1 ou Gripe Suína). Foi uma destas viroses tradicionais, de vômitos e diarreias. A desgraçada deu uma varrida na minha família, passando pelo meu pai, minha esposa, eu, as esposas dos meus dois irmãos e mais uma sobrinha.

O resultado foi que na segunda passada eu estava no pronto socorro com a minha esposa ao invés de ir no Google Developer Day 2009 e fiquei no trabalho somente dois meios períodos. Eu trabalhei um pouco de casa, mas é difícil fazer alguma coisa quando está se sentindo mal.

Agora que já ficou para trás, vamos ver se consigo retomar o ritmo dos posts.
Posted by Daniel Quadros at 11:22 0 comentário(s)
Categorias:
Assinar: Postagens (Atom)