sábado, agosto 30, 2008

Trocando o HD - de novo

Como comentei anteriormente, troquei há dois meses atrás o HD do meu PC de casa. Um efeito colateral foi uma vibração, eu gerava um barulho irritante. Nas semanas seguintes fez algumas tentativas de diminuir o barulho, mas não tive sucesso.

Acabei deixando como estava, apesar do barulho irritar cada vez mais. Finalmente resolvi entrar numa loja e ver o preço de um novo HD de 250G. Como era de esperar, o preço estava mais baixo de quando fiz a compra anterior e acabei comprando. O novo HD é um Maxtor STM3250310AS, com interface SATA II, 7200rpm como o anterior (Samsung HD250HJ). Uma diferença é que ele é slim, com metade da altura de um HD normal.

A troca foi tranquila, graças à experiência anterior. E o novo drive é absolutamente silencioso.

Somente agora é que percebo como o ruído do drive anterior me perturbava. E acabou sendo aquele tipo de incômodo que a gente insiste em aturar e quando resolve fica pensando porque não resolveu antes.

O HD Samsung fica na prateleira aguardando a compra de uma caixa para usar como drive USB para fins de backup e transporte de grandes volumes entre a casa e o escritório.

sexta-feira, agosto 29, 2008

Microcontroladores - Parte 10

Vamos iniciar os nossos exemplos com os microcontroladores PIC da Microchip.

O PIC é bastante popular, principalmente entre hobbistas (entre outros motivos, por estar disponível no encapsulamento DIP que permite uma montagem mais simples).

Uma peculariedade do PIC é que uma série de características são definidas através da gravação de uma área especial de configuração na memória Flash.

Falando em Flash, alguns modelos (mas não todos) possibilitam a implementação de um bootloader (atualização do software sob controle do próprio software).

Um modelo médio é o PIC16F628:
  • clock de DC até 20MHz
  • memória Flash para 2K instruções (já veremos o que é isto)
  • memória Ram de 96 bytes
  • memória EEProm de 128 bytes
  • até 16 E/S digitais
  • 3 timers
  • uma UART
  • módulo CCP: Capture, Compare e PWM
A arquitetura do PIC é bem diferente da arquitetura que a maioria dos programadores PC conhece. Em primeiro lugar, é uma arquitetura RISC. Existe um conjunto pequeno de instruções, todas de mesmo tamanho (14 bits no PIC16):

Mais radical ainda, o PIC utiliza uma Arquitetura Harvard. A idéia básica desta arquitetura é separar a memória de código da memória de dados. A memória de código é dimensionada para guardar uma instrução em cada posição (ou seja, cada posição no PIC16 armazena 14bits) e a de dados é organizada em bytes:

Na figura acima as instruções passam pelas partes em verde e os dados pelas partes em azul. O PIC16 suporta diretamente uma memória de programa com até 8K instruções, usando um contador de programa (PC) com 13 bits. Para tratamento de interrupções e chamada de subrotinas o PIC dispõe de uma pilha (stack) com apenas 8 posições.

As instruções lógicas e aritméticas trabalham sempre com um acumulador, o registrador W. Este registrador, os registradores de controle das funcionalidades (SFR) e a Ram de uso geral (GPR) estão armazenados conjuntamente na memória de dados, que é paginada em bancos (cada banco possui 128 posições, o banco ativo é selecionado através de bits no registrador de status):


Esta arquitetura é particularmente cruel para um compilador de linguagens de alto nível como o C:
  • existe pouco suporte para constantes armazenadas na Flash. Comandos como printf("Alo, mundo") requerem um ginástica incrível do compilador para armazenar o string na Flash e acessá-lo posteriormente como parâmetro para uma função.
  • não existem ponteiros para rotinas
  • pilha reduzida, só para código
  • Ram muito reduzida
É realmente uma surpresa existir um compilar C para o PIC. O compilador CCS v3.2 tem as seguintes características:
  • "urso andando de bicicleta"
  • não possui linker, todo o programa deve estar em um único fonte (#include pode ser usado para dividir o fonte em vários arquivos)
  • váriaveis auto (inclusive parâmetros) são implementadas como static
  • para aproveitar melhor a Ram, o compilador analisa a árvore de chamada de funções e usa a mesma posição de Ram para variáveis que não existem simultaneamente
  • IDE bem simples, com um Wizard para criar o projeto
  • Depurador e simulador integrados
  • variáveis inteiras dos tipos int1, int8, int16 e int32. int1 é um bit, o compilador agrupa variáveis deste tipo em bytes.
  • subconjunto da biblioteca C padrão e mais funções específicas de controle do hardware

Microcontroladores - Parte 9

Nas partes seguintes veremos alguns exemplos de microcomputadores e ambientes de desenvolvimento em C:
  • PIC e compilador CCS
  • 8051 e compilador Keil uVision2
  • MSP430 e IAR Workbench
  • ARM e gcc
Para cada um deles vamos ver a arquitetura do processador, as principais funcionalidades disponíveis no microcontrolador, os recursos do IDE e as facilidades e dificuldades da programação em C.

Cabem algumas observações:
  • Estes exemplos vem da minha (limitada) experiência pessoal
  • Os exemplos abordam alguns poucos modelos de famílias de componentes bastante numerosas
  • Existem muitos outros microcontroladores e ambientes de desenvolvimento no mercado

quinta-feira, agosto 28, 2008

Microcontroladores - Parte 8

O meu primeiro contato com desenvolvimento de sistemas embarcados foi dando manutenção e desenvolvendo firmwares para terminais de vídeo na Scopus*. O hardware era baseado no microprocessador Intel 8080, que é menos poderoso que a maioria dos processadores dos microcontroladores atuais.

Nesta época praticamente todo o desenvolvimento, tanto para os terminais de vídeo como para o microcomputador de 8 bits, era feito em Assembly. Era uma programação trabalhosa, tediosa e muito propícia a erros. Foi somente quando se começou a desenvolver software para 16 bits que se começou a usar linguagens de alto nível no software 'básico'. Posteriormente isto foi estendido para os terminais de vídeo, apesar de algumas desconfianças em termos de desempenho e requisitos de memória.

A linguagem C foi justamente desenvolvida para a programação de baixo nível em sistemas com poucos recursos
  • implementa as estruturas básicas de programação (if, while, switch)
  • dispõe de recursos para operações de baixo nível (ponteiros, manipulação de bits)
  • requer um runtime bastante simples
Mesmo assim, alguns microcontroladores são grandes desafios para quem quer criar um compilador C:
  • arquiteturas não apropriadas
  • memória Ram limitada
  • memória dividida em partes com características diferentes
O resultado às vezes é o proverbial "urso de circo andando de bicicleta": ele não anda muito bem mas o simples fato de andar alguma coisa já é incrível.

O código abaixo é uma simplificação do software para o "Grilo Pulsante Fantasma" e dá uma primeira idéia do que é programar em C para microcontroladores:

#include <12F675.h>
#use delay(clock=4000000)
#fuses INTRC_IO, MCLR, BROWNOUT

volatile int1 fBeep;
volatile int16 contBeep;

void bipa (void)
{
fBeep = TRUE; contBeep = 0;
enable_interrupts (INT_TIMER0);
while (fBeep)
;
disable_interrupts (INT_TIMER0);
}

#int_TIMER0
TIMER0_isr()
{
if (++contBeep == 0x1000)
fBeep = FALSE;
else if (contBeep & 1)
output_low (BUZZER);
else
output_high (BUZZER);
}

void main()
{
set_tris_a (0x06);
#use fast_io(A)
setup_adc_ports (AN1_ANALOG);
setup_adc (ADC_CLOCK_INTERNAL);
set_adc_channel (1);
setup_timer_1 (T1_DISABLED);
setup_comparator (NC_NC_NC_NC);
enable_interrupts (global);
output_low (BUZZER);

while (1)
{
sleep ();
if (input (BOTAO) == 0)
bipa ();
if (read_adc() < ESCURO)
continue;
AcendeLed (LED_R);
delay_ms (10);
ApagaLed (LED_R);
if ((rand() & 0x07) == 0)
bipa ();
}
}

No código acima podemos reparar que:
  • um programador C de desktop não vai ter dificuldade em entender boa parte do código
  • existem uma série de comandos não padrão para o compilador (#use, #fuses, #int_TIMER0)
  • existem uma grande quantidade de rotinas específicas para controle do hardware (neste caso em particular muitas destas rotinas na realidade geram diretamente código in-line)
A qualidade do código gerado e do ambiente de desenvolvimento varia bastante de caso para caso. É o que veremos nos próximos posts.

* brinde inesperado: clique em "Conheça nossa história" e encontre uma menção nominal ao autor do blog!

quarta-feira, agosto 27, 2008

Usando o Syntax Highlightter - Parte 2: O Acerto

No post original eu mencionei que não estava aparecendo correto com o Firefox. Felizmente, existe um grupo de discussão sobre o Syntax Highlighter:

http://groups.google.com/group/syntaxhighlighter

Melhor ainda, o criador da ferramenta frequenta o grupo e se dá ao trabalho de ajudar os "manés" que não conseguem colocar para funcionar.

No meu caso, o Firefox não estava gostando do stylesheet carregado a partir do Google Code. A solução foi simples: colocar o stylesheet diretamente dentro do template do blog.

segunda-feira, agosto 25, 2008

The Closer - 1a Temporada

Atualmente as produtoras americanas capricham muito mais em séries que em filmes feitos para TV. Existe uma quantidade bem razoável de séries com uma boa idéia, bons atores, bons roteiros e muito esmero na produção.

Infelizmente, é difícil acompanhar estas séries aqui no Brasil. Além da pouca divulgação, os canais por assinatura costumam escolher horários esquisitos (às vezes mutantes) e sem horário alternativo. Os episódios nuitas vezes são apresentados em ordem e as repetições são frequentes. Por este motivo os boxes de DVD são uma alternativa muito importante.

Consegui assistir uns poucos episódios de The Closer no canal TNT, nos sábados às 14:00 e fiquei muito feliz em verificar que a primeira temporada está disponível para venda no Brasil a preços razoáveis.

Esta série (que ganha no box o subtítulo "Divisão Criminal" - ô costume besta colocar estes subtítulos!) gira em torno da Chief Brenda Johnson, que comanda uma equipe para investigação de casos de assassinato delicados em Los Angeles. O nome da série vem da capacidade dela de obter a confissão do criminoso, fechando assim o caso de forma incontestável.

Nesta primeira temporada, Brenda está chegando a Los Angeles e não é bem recebida pelos policiais de lá, particularmente pelo comandante de Homicidios. Ao longo da temporada, além de resolver os casos, ela terá que ganhar a confiança dos seus subordinados. Os casos são bastante interessantes, indo dos sinistros aos engraçados. Como de costume nas séries, a vida pessoal da protagonista também é abordada. E ela é uma mulher meio atrapalhada, que acaba de chegar na cidade, o que gera uma boa dose de comic releif.

O box da primeira temporada é bem feito, mas não excepcional. São treze episódios, dividos em quatro discos. Áudio em inglês com legendas em português, inglês e espanhol. O tradutor de vez enquanto apanha, particularmente com Homeland Security que acaba virando até segurança de casas (poderíamos traduzir "Homeland Security" para "Segurança Nacional", mas que nos EUA tem todo um significado especional no pós 11 de setembro). Em alguns poucos episódios tem algumas cenas não aproveitadas (normalmente detalhes que acabam ficando implícitos para o episódio ficar no tempo correto).

Maiores detalhes sobre a série podem ser vistos na Wikipedia.

Recomendado!

sábado, agosto 23, 2008

Usando o Syntax Highlighter

Uma coisa que sempre me incomodou é a baixa qualidade da apresentação dos trechos de código que coloco aqui no blog. Por sugestão de um dos meus leitores, o Breno, resolvi utilizar o Syntax Highlighter.

O Syntax Highlighter é composto por um sylesheet e uma série de rotinas em Javascript para formatar código usando cores para indicar os vários tipos de elemento na sintaxe. Ele suporta várias linguagens.

As dicas de instalação em um blog hospedado no Blogger que listo a seguir são uma adaptação do que se encontra aqui.

O primeiro passo é fazer o download no seu micro da versão mais atual do Syntax Highlighter. Exandindo o arquivo baixado, temos três diretórios:
  • Scripts: contém os scripts Javascript e um arquivo flash (clipboard.swf). No mínimo você precisa do script shCore.js e do script para as linguagens desejadas. O clipboard.swf é para permitir copiar o código exibido para o clipboard.
  • Styles: tem o stylesheet SyntaxHighlighter.css. Você vai precisar dele
  • Uncompressed: os scripts no diretório Scripts estão sem comentários e sem espaços em branco para reduzir o tamanho do download na página. Neste diretório estão as versões completas, para quem quiser examinar o código.
A parte mais complicada é achar algum lugar para hospedar os arquivos. Acabei optando por usar Google Code, espero não estar infringindo as regras de uso.

O passo seguinte é colocar os comandos apropriados no template do blog. Isto é feito na opção Edit Html do Layout. Em algum lugar entre <head> e </head> é preciso incluir o stylesheet e os scripts:

<link href='http://dqsoft.googlecode.com/files/SyntaxHighlighter.css' rel='stylesheet' type='text/css'/>
<script language='javascript' src='http://dqsoft.googlecode.com/files/shCore.js'></script>
<script language='javascript' src='http://dqsoft.googlecode.com/files/shBrushCpp.js'></script>

Imediatamente antes do </body> deve ser chamada a rotina que faz a formatação:

<script language='javascript'>
dp.SyntaxHighlighter.ClipboardSwf = 'http://dqsoft.googlecode.com/files/clipboard.swf';
dp.SyntaxHighlighter.BloggerMode();
dp.SyntaxHighlighter.HighlightAll('code');
</script>

No post, os trechos de código devem esta indicados como abaixo:

<pre name="code" class="Cpp">
código
</pre>

O resultado final pode ser visto abaixo:

void main()
{
int a, b, c;

for (a = 1; a < 5; a++)
{
b = 5*a;
c = b - 3*a;
printf ("%d %d %d\n", a, b, c)
}
}


Obs.: parece que ainda não está perfeito. Aparece corretamente no IE7, mas no Firefox não está usando o stylesheet...

Atualização em 26/ago/08: Já está funcionando. A resposta curta é que Google Code não é um bom lugar para colocar o stylesheet. A resposta longa vai num novo post.

Microcontroladores - Parte 7

Fechando a parte de funcionalidades típicas de um microcontrolador, vamos ver hoje a parte de comunicação serial.

Na comunicação serial os dados são enviados bit-a-bit através de um ou mais sinais digitais. A comunicação serial pode ser usada tanto para comunicação entre equipamentos como para a comunicação entre componentes de um circuito. Existem diversas modalidades e padrões de comunicação serial, vamos ver aqui apenas alguns deles.

Uma vez que os dados são enviados bit-a-bit, as questões básicas são como localizar cada bit e como localizar o início de cada sequência de bits (tipicamente com 8 bits formando um byte). A figura abaixo mostra como um mesmo sinal digital pode ser interpretado de formas diferentes.

A comunicação serial pode ser implementada por software usando as entradas e saídas digitais e o timer. É um processo trabalhoso, nem sempre confiável, e que consome processador e memória. Por este motivo é comum os microcontroladores possuirem módulos internos que permitem trabalhar diretamente com bytes.

Nestes módulos existe sempre uma certa capacidade de bufferização. No mínimo existe um registrador com o byte que está em processo de transmissão e recepção (normalmente inacessível ao programador) e um outro registrador onde pode ser retirado o byte que já foi recebido inteiramente ou colocado o próximo byte a transmitir. Nos modelos mais sofisticados temos filas de vários bytes, simplificando ainda mais a programação. Em alguns casos existe até um recurso de DMA onde você programa o endereço e tamanho de um buffer de memória e o módulo de comunicação faz toda a comunicação sozinho.

Comunicação Assíncrona - UART

A comunicação serial assíncrona é uma das formas mais simples e comuns de comunicação serial. Nela a linha de comunicação está normalmente em nível "1". O início de um byte é indicado por um "0" (start bit). Em seguida vem os bits de dados, um bit (opcional) de paridade e um período de repouso em "1" (stop bits). O tempo de duração de cada bit (que define a taxa de comunicação ou baud rate) precisa ser combinado previamente entre as duas pontas (para que a determinação de cada bit ocorra corretamente).

Uma UART (Universal Asynchronous Receiver Transmiter) é um módulo que implementa a comunicação assíncrona, gerando e interpretando o sinal digital correspondente.

Comunicação Síncrona - USART

Dois problemas da comunicação asíncrona é que gasta-se tempo de comunicação transmitindo os start e stop bits e o baud rate precisa ser combinado externamente à comunicação. Na comunicação síncrona utiliza-se um sinal de clock separado para indicar onde está cada bit.
O início de cada byte é determinado através de sequências especiais de bits.

Uma USART é módulo que implementa comunicação síncrona e assíncrona.

SPI - Serial Peripheral Interface

O SPI é uma comunicação serial síncrona utilizada principalmente para interligar componentes. Um uso típico de SPI é para conectar memória adicional a um microcontrolador.

O SPI utiliza 4 sinais para permitir a comunicação bi-direcional entre um master e um slave:
  • SCLK: é o sinal de clock, gerado pelo master.
  • MOSI: é o sinal de dados que vai do master para o slave.
  • MISO: é o sinal de dados que vai do slave para o master.
  • SS: é um sinal gerado pelo master que aciona a comunicação com o slave.
Tipicamente o microcontrolador é o master. Os sinais SCLK, MOSI e MISO do master são ligados a todos os slaves. Um sinal separado de SS é usado para cada slave. Os slaves não acionados pelo sinal SS devem ignorar os sinais SCLK e MOSI e deixar o sinal MISO flutuar. O sinal MISO será comandado pelo slave acionado pelo sinal SS. Isto permite uma configuração de "varal" onde vários periféricos (slaves) são conectados a um mesmo master, apenas um slave poderá se comunicar de cada vez:
Maiores detalhes sobre SPI podem ser vistos na Wikipedia (de onde veio a imagem acima).

I²C - Inter-Integrated Circuit

Como o SPI, o I²C é uma comunicação serial síncrona utilizada principalmente para interligar componentes. Também permite uma ligação tipo "varal" entre um master e vários slaves. Entretanto, ele utiliza somente dois sinais:
  • SDA: sinal de dados. É bi-direcional, o protocolo determina quem vai acionar o sinal.
  • SCL: sinal de clock, gerado pelo master
Na situação de repouso, os dois sinais estão em nível "1". Para iniciar uma comunicação, o master muda o sinal SDA para "0", mantendo SCL em "1"; é o start bit. Em seguida o master transmite um endereço de 7 bits seqguido de um bit que indica se deseja ler ou escrever no slave; os bits são enviados pelo sinal SDA com a transição do sinal SCL de "0" para "1" indicando onde os bits devem ser lidos. Caso um dos slaves tenha o endereço especificado, ele deve responder forçando SDA em "0" (acknowledge). Em seguida o byte de dado é transmitido na linha SDA, com SCL indicando a posição de cada bit. Ao final de cada byte o receptor envia um bit de ACK. No final da comunicação o master muda o sinal SDA de "0" para "1" mantendo SCL em "1" (stop bit).

Confuso? Por isto mesmo é que é util o microcontrolador ter toda esta lógica interna.

sexta-feira, agosto 22, 2008

Qual a sua Lasanha?

A idéia deste post surgiu ao ver na Folha Ilustrada de 27 de abril de 2008, uma frase destacada na reportagem "O sertanejo é antes de tudo um forte": Nunca passamos fome, mas sim vontade de comer coisas boas (dita por Fabiano, cantor sertanejo).

Devo admitir que o sertanejo está muito longe de ser o meu tipo de música preferida e que não li com atenção a reportagem, porém a frase acima me lembrou um história.

Ocorreu que uma amiga minha, há muitos anos atrás, ao voltar do serviço de Metrô, escutou uma moça dizer para outra: "se sobrar dinheiro no final do mês, vou fazer uma lasanha". Pelas roupas e demais contexto, dava para perceber que não se tratava de uma pessoa "passando necessidade" (como diria a minha mãe) e que provavelmente tinha um emprego fixo. Embora para a maioria das pessoas que convivo (e provavelmente também para os leitores do blog) uma lasanha não é assim tão especial, para esta moça era um objeto de desejo, naquele ponto mágico em que não está ao alcance mas parece que logo vai estar.

De uma certa forma, todos (dos mais ricos aos mais pobres) tem a sua lasanha, aquele objetivo que a gente espera conseguir se a maior parte der certo e pouca coisa der errado.

quinta-feira, agosto 21, 2008

Microcontroladores - Parte 6

Continuando a nossa série, vamos ver hoje as funcionalidades relacionadas com tempo encontradas nos microcontroladores.

A Base de Tempo - o Clock

O processador e vários de seus periféricos necessitam de uma base de tempo (clock). Existem diversas formas de gerar o Clock, com precisão e custo diferenciados:
  • cristal de quartzo: é o mais preciso e está disponível em uma faixa grande de valores. Por outro lado, é o mais caro.
  • ressonador: uma alternativa mais barata e menos precisa aos cristais.
  • circuito RC externo: pouco preciso mas barato.
  • oscilador interno ao microcontrolador: o mais barato (está embutido), mas não costuma ter muita precisão.
É comum um microcontrolador suportar várias opções. Em alguns modelos pode-se ter mais de uma fonte de clock, permitindo usar clocks diferentes para o processador e periféricos ou mesmo mudar dinamicamente o clock do processador conforme a tarefa requer velocidade ou economia.

Timer

O timer é um periférico básico encontrado praticamente em todo microcontrolador. Na forma mais simples é um contador que é incrementado ou decrementado pelo clock; ao chegar a zero uma interrupção pode ser gerada. A partir desta interrupção o software gera as temporizações necessárias.

Por exemplo, vamos supor um microcontrolador operando a 1MHz com um timer que interrompe o processador a cada 65536 ciclos do clock. Neste caso, o tempo entre as interrupções será de 65536/1000000 = 65,535 mseg. A cada 15 interrupções teremos aproximadamente 1 segundo.

Alguns timers permitem dividir o valor do clock antes do contador (útil para clocks altos) e carregar automaticamente um valor inicial sempre que o clock der a volta (no exemplo anterior, se pudermos carregar 10000, o contador for decrementado a cada clock e interromper quando chegar a zero, teremos uma interrupção precisamente a cada 10 mseg).

Um outro recurso disponível em alguns timers é a possibilidade de iniciar e parar a contagem por um sinal externo. Isto permite usar o timer para medir o tempo entre as variações em um sinal digital.

Watchdog Timer (WDT)

Os circuitos que utilizam os microcontroladores muitas vezes devem funcionar sem acompanhamento. Isto significa que em caso de algum problema que leve a uma travada no software o microcontrolador precisa se recuperar sozinho.

O watchdog timer é uma espécie de bomba relógio: é um contador que vai sendo automaticamente decrementado e gera um reset quando chega a zero. O software deve periodicamente re-armar o timer para evitar este reset.

O uso correto do WDT nem sempre é trivial. Se o re-armamento é feito em vários pontos, aumenta o risco do programa ficar "perdido" sem ocorrer o reset. Por outro lado, re-aramar somente em um ponto (tipicamente o loop principal do programa) pode não ser suficiente se o tempo do WDT for curto e alguns processamentos forem demorados.

Real Time Clock (RTC)

Usando um timer e uma boa quantidade de código é possível implementar um relogio que mantém data e hora. Entretanto, este relógio vai depender do processador estar rodando, o que significa consumo de energia. Para facilitar a vida, existem módulos específicos para registrar data e hora. Em alguns microcontroladores o RTC é interno, nos demais é possível ligá-lo externamente, neste caso é comum a opção de ligar uma bateria externa para manter o relógio atualizado mesmo que o circuito principal não esteja alimentado. Um RTC típico utiliza um cristal de 32.768 Hz, que é dividido internamente por um contador binário de 15 bits para gerar uma base precisa de 1 segundo.

quarta-feira, agosto 20, 2008

Harry Potter e o Gênio de Marketing

A indústria de cinema parece ser dominada por control-freaks num mundo que cada vez resiste a controles. Já vimos fitas e DVDs inundados de trailers, teclas de avanço travadas nos DVDs players e convivemos diariamente com as infames regiões do DVD. A Warner Brothers atingiu na quinta passada (14/ago) um novo marco.

O quinto filme do Harry Potter (Harry Potter and The Half-Blood Prince) já está pronto (as filmagens em si acabaram em meados de maio) e tinha a estreia marcada para 21 de novembro de 2008. A máquina de lançamento já estava acelerando, com a liberação dos primeiros trailers e o aumento de referências ao filme e ao livro na midia.

Até que um gênio de marketing entrou em ação. Com a greve dos roteiristas de Hollywood no início do ano, surgiu o que ele identificou como uma "janela de oportunidade": poucos filmes serão lançados nas férias do verão americano de 2009. Com menos concorrência, espera-se uma maior receita. Resultado: bônus já para o gênio e o filme fica na prateleira até 17 de julho de 2009.

Uma recomendação para a WB: mantenha o filme bem trancado na prateleira. Sem abusarem das sessões especiais antes do lançamento, correm o risco de ver o filme nas banquinhas de São Paulo muito antes da data de lançamento.

terça-feira, agosto 19, 2008

COBOL x o Exterminador do Futuro

Esta notícia parece roteiro de filme: governador (interpretado por Arnold Schwarzenegger) tenta se livrar de intrigas políticas que colocam as finanças do estado em perigo mas encontra um adversário implacável na forma de uma tecnologia antiga. E o mais incrível é que não é ficção.

Republicanos e Democratas não chegam a acordo na Califórnia e o estado está operando a um mês e meio sem orçamento. O governador Arnold Schwarzenegger se baseou em uma decisão da Suprema Corte para assinar um decreto na semana passada impondo o pagamento de salário mínimo (US$6,65/hora) para os funcionários estaduais fixos e demitindo os empregados temporários ou de tempo parcial.

O que ele não contava é que os computadores da Califórnia são da decada de 60 e o software de folha de pagamento foi escrito em Cobol. Os técnicos responsáveis dizem não ser possível implementar as alterações no tempo estipulado.

Minha sugestão: ele contratar Jeff Goldblum, mundialmente conhecido por seus feitos na programação de computadores.

Microcontroladores - Parte 5

Continuando o estudo das funcionalidades típicas de um microcontrolador, vamos examinar as entradas e saídas digital e analógica.

Entradas e Saídas Digitais

Basicamente esta funcionalidade consiste em poder ler (entrada) ou forçar (saída) um sinal digital (0 ou 1) em um pino do microcontrolador. Pode parecer pouco, mas é um dos recursos mais importantes e mais utilizados.

É comum os microcontroladores oferecerem uma grande quantidade de entradas e saídas digitais. Não é comum quase todos os pinos poderem ser utilizados para isto; registradores de configuração permitem definir quais pinos serão usados para entrada, quais para saída e quais serão usados para outras funções.


Entradas Digitais

Um uso típico de uma entrada digital é para detectar se um botão está apertado. Obiamente, no lugar do botão podemos ter qualquer tipo de sensor ou dispositivo com um saída digital. Por exemplo, podemos ter uma chave que se fecha com a proximidade de um imã. Prendemos o imã em uma porta e a chave no batente e temos um sensor digital que indica se a porta está aberta ou fechada.

Uma entrada digital pode também ser utilizada para implementar uma comunicação serial ou paralela com um outro componente ou dispositivo (no caso de comunicação serial, muitos microcontroladores possuem recursos específicos para isto, como veremos adiante).

Uma facilidade comum é o microcontrolador ser capaz de gerar uma interrupção quando ocorre uma mudança no sinal de um pino. Isto é mais eficiente que o software ficar examinando periodicamente a entrada.

Saídas Digitais

Um uso básico de uma saída digital é acionar um LED. A capacidade de acionamento de uma saída digital é normalmente limitada; um transistor ou um relê podem ser utilizados para controlar cargas maiores. Desta forma uma saída digital pode controlar uma lâmpada, um motor, uma sirene, etc.

O software pode controlar mudança rápidas e periódicas das saídas digitais. Por exemplo, podemos ligar um alto-falante (ou um buzzer) a uma delas e gerar sons.

De forma semelhante às entradas digitais, as saídas digitais podem ser utilizadas para implementar comunicação serial ou paralela com outros componentes ou dispositivos.

Pulse Width Modulation - PWM

Um uso comum de saídas digitais é gerar pulsos repetitivos. Por este motivo é comum uma funcionalidade específica para isto nos microcontroladores. No PWM programa-se o período (que define a frequência) e a relação entre os tempos de sinal "1" e sinal "0" (duty cycle).

Aplicações simples de PWM são a geração de sons e o controle da intensidade aparente de um LED (acendendo e apagando rapidamente um LED não se percebe que ele está piscando; a intensidade aparente varia com o duty cycle).

Um exemplo mais completo de uso de entrada e saída digitais pode ser visto no post "Controlando um LED com um PIC - Parte I".

Entradas Analógicas

Uma entrada analógica fornece um número que depende da tensão presente em um pino. O número de bits no número define a precisão da conversão; valores típicos são 8, 10, 12 e 16 bits.

Alguns exemplos de uso de para uma entrada analógica:
  • verificar o nível da alimentação, para indicar bateria baixa
  • verificar o nível do sinal recebido, para circuitos com comunicação via rádio
  • verificar o nível de luminosidade ambiente e acertar a intensidade de LEDs
  • digitalizar sinais analógicos para armazenamento ou processamento
As entradas digitais exigem circuitos internos mais complexos no microcontrolador. Por este motivo não são encontradas nos modelos mais simples e são em pequeno número nos mais sofisticados. É comum também um microcontrolador possuir um único conversor que pode ser ligado a vários pinos; neste caso apenas uma conversão pode ser feita por vez.

O processo em si da conversão demora um certo tempo e consome energia, portanto aplicações de digitalização contínua não são comuns.

Uma alternativa às entradas analógicas são os comparadores analógicos. Neste caso o microcontrolador inidica somente se a tensão em um pino é maior ou menor que um valor de referência (fixo) interno. Um divisor resistivo externo pode ser usado para deixar o sinal a monitor compatível com o valor de referência.

Saídas Analógicas

Em uma saída analógia a tensão de um pino é controlada escrevendo um valor em um registrador. Este tipo de recurso é mais incomum.

domingo, agosto 17, 2008

Estatísticas de Uso do Cuil

O contador de visitas que utilizo (Statcounter) tenta registrar de onde o visitante veio. Isto ajuda a direcionar melhor o conteúdo do site e a sua divulgação. O statcounter faz uma estatística específica para os sites de busca, mas normalmente isto é bem monótono.

Com todo o oba-oba do Cuil, eles resolveram publicar as estatísticas referentes a ele entre 29 de julho e 10 de agosto. O resultado é bastante desanimador para o Cuil: nos primeiros três dias ele ficou em torno de 0,10% das buscas e nos dez dias seguintes desabou para 0,01% (1 em cada 10.000).

Nos comentários do post do Statcounter, mais uma informação negativa sobre o Cuil: o programa deles que percorre a internet registrando as páginas ('bot' ou 'crawler') é bastante incômodo e foi bloqueado por muitos sites, o que reduz a qualidade dos seus índices.

sábado, agosto 16, 2008

Jogo do Mês - Virtual Villagers

Já faz muito tempo que os jogos encontrados em lojas são produções milionárias. Os jogos mais modestos se refugiaram na internet. São produzidos pelos chamados Independent Developers (empresas que não estão sob controle de um distribuidor) e a maioria é do tipo Casual Game (jogos mais simples, voltados para jogadores eventuais).

Apesar do orçamento mais limitado, muitos destes jogos tem gráficos e sons muito bem feitos. Os principais 'ganchos' para pegar jogadores são a facilidade de jogar e a capacidade de cativar. Um dos exemplos mais bem sucedidos é o Bejeweled.

Um dos sites que comercializam este tipo de jogos é o Game Tunnel. Os jogos disponíveis podem ser vistos aqui. Embora o título da página seja "Free Games" estes jogos rodam gratuitamente por tempo limitado, após isto é necessario adiquir uma licença (os preços costumam estar na faixa de US$15 a US$45).

Foi aí que encontrei o simpático Virtual Villagers. É uma espécie de 'The Sims Lite' (acho eu, nunca joguei The Sims), onde você controla um bando de pessoas em uma ilha.


Acabei comprando o jogo diretamente do site do desenvolvedor, dava até para ver o preço em reais (o preço é US$19,95, que correspondeu no dia a R$33 e uns quebrados). Para minha surpresa, tem até um artigo a respeito na Wikipedia. O site do desenvolvedor possui dicas e um forum bem movimentado.

O jogo é bastante viciante. O único problema é que o passar do tempo é meio lento (seis meses da ilha correspondem a 1 hora de jogo, se você considerar que você só vai poder colocar uma criança para 'trabalhar' quando ela fizer 14 anos dá para ver que a coisa vai longe). O jogo tem também uma série de problemas a serem resolvidos, e paciência e insistência são fundamentais para isto.

Para facilitar, o jogo "continua mesmo com o micro ligado" (mais precisamente, se você sair do jogo sem pausá-lo, quando você entrar de novo ele processa a simulação de todo o tempo desde que você saiu). Este recurso não é muito útil, pois tem muita coisa que depende da sua interação imediata (principalmente no início do jogo). A primeira vez que eu joguei, deixei correr de um dia para o outro e o resultado foi que todo mundo morreu de fome.

Fica a sugestão de baixar o jogo (não é um download muito grande) e experimentar na hora gratuita. É bem provável que ao final você ache que os trinta e poucos reais são mais que merecidos.

sexta-feira, agosto 15, 2008

Microcontroladores - Parte 4

Na parte anterior falamos na memória Flash, que é normalmente utilizada para armazenar o programa (firmware) do microcontrolador. Antes de continuarmos a ver as funcionalidades tipicamente intergradas nos microcontroladores, vamos ver como o programa pode ser gravado na memória Flash.

Praticamente todos os microcontroladores permitem fazer a gravação colocando sinais apropriados em determinados pinos. Existem duas variações básicas (não necessariamente excludentes):

Gravação Externa ao Circuito

Uma forma simples é colocar o microcontrolador (ou a própria memória Flash se ela for externa) em um gravador apropriado. A figura abaixo mostra o McFlash da Mosaico, que permite gravar diversos modelos da família PIC:


Este gravador, como a maioria dos gravadores externos, é conectado a um PC (no caso através do conector serial na parte inferior direita da figura). O conteúdo a ser gravado é transferido do PC para o gravador através de um software especial. Este software permite também apagar e ler a Flash.

Este tipo de gravação é interessante para pequenos testes (quando o microcontrolador vai ser colocado em uma breadboard) ou para uma produção em série de pequena escala (para gravação em maior escala existem gravadores capazes de fazer várias gravações em paralelo).

Gravação no Circuito

A maioria dos microcontroladores atuais permite que um gravador externo seja usado mesmo com o microcontrolador conectado ao circuito. Para isto é necessário seguir algumas recomendações do fabricante e colocar no circuito um conector para ligação do gravador:


Esta forma de gravação é mais prática no desenvolvimento, pois não é necessário ficar tirando e recolocando o microcontrolador.

Em muitos casos o gravador permite também depurar o firmware. A figura abaixo mostra alguns modelos de gravadores com capacidade de depuração:

Existe até uma certa padronização para o conector de gravação, o chamado conector JTAG.

Embora os gravadores nas fotos possuam uma razoável inteligência (sim, eles contém microcontroladores dentro deles) muitas vezes é viável construir um gravador simples utilizando um simples buffer/conversor de nível para conectar pinos da porta paralela de um PC ao conector de gravação. Neste caso o software no PC precisa comandar com precisão os sinais de gravação.

Gravação Sob Controle do Firmware

Diversos microcontroladores permitem que a sua Flash seja gravada por controle do software. Isto possibilita o "santo graal" dos projetos com microcontrolador: a atualização do firmware em campo sem a necessidade de conectar um gravador externo. Nos casos em que o dispositivo possui uma forma de comunicação externa (por exemplo, um modem GPRS) é potencialmente possível fazer esta atualização de forma "automágica" durante a operação normal.

Existem, é claro, vários complicadores. Não é possível atualizar o software que está executando, portanto pelo menos uma parte da rotina de atualização precisa estar em uma área distinta. O grande pesadelo é algo dar errado durante a atualização e o dispositivo virar um "tijolo". Por este motivo o novo firmware é normalmente colocado inicialmente em uma área temporária e gravado ou ativado somente após ter sido recebido completamente e conferido. Nos casos em que exista memória suficiente pode-se ter duas versões distintas armazenadas na Flash, facilitando a recuperação em caso de problemas.

Uma versão mais simplificada é o chamado bootloader. Neste caso existe uma parte do firmware dedicada somente a receber e gravar a aplicação propriamente dita. Neste caso o processo de gravação não faz parte da operação normal, é preciso entrar em um modo especial de operação. Alguns microcontroladores já trazem esta funcionalidade pré-gravada em uma área protegida da Flash.

Protegendo o Firmware

Uma primeira proteção importante é contra o apagamento acidental. Nos casos em que a Flash pode ser gravada por controle do firmware os procedimentos são normalmente complexos para evitar que um software "perdido" se auto-modifique.

Um segundo tipo de proteção consiste em impedir a leitura do firmware através de um gravador externo, para evitar a sua duplicação ou engenharia reversa. Para isto existem uma espécie de "fusíveis" que podem ser "queimados" ao final da gravação e impedem a leitura externa. Em alguns casos estes fusíveis são irreversíveis em outros só podem ser desligados apagando todo o conteúdo da Flash.

quarta-feira, agosto 13, 2008

Microcontroladores - Parte 3

Como vimos na parte anterior, uma das características de um microcontrolador é ter integrado no mesmo chip que o processador uma série de outras funcionalidades. Neste post vamos começar a ver estas funcionalidades pelas memórias.

Um microcontrolador tem normalmente apenas algumas destas funcionalidades internamente. Por este motivo, é comum elas estarem disponíveis também em integrados isolados.

A Nomenclatura

Os nomes dados às diversas funcionalidades encontradas nos microcontroladores são, no mínimo incosistentes. É comum se dar nomes diferentes a recursos iguais (normalmente por motivos de marketing) e ocasionalmente dá-se o mesmo nome a recursos diferentes. Alguns nomes vem de motivos históricos, lembrança de uma realidade que já não existe mais. Outros são simplesmente inexplicáveis.

De qualquer forma, se você aceita a terminologia "Memória de Acesso Randômico" (vulgarmente chamada de RAM) apesar de o acesso randômico não ser a principal distinção de outros tipos comuns memórias com nome diferente, não vai ter dificuldade em aceitar os nomes apresentados.

Memória Não-Volátil

Vamos começar vendo alguns tipos de memória (também de acesso randômico) que são ditas não-voláteis por manter o conteúdo mesmo quando não alimentadas. Estas memórias são usadas principalmente para armazenar o programa (ou firmware) e configurações. Num microcontrolador normalmente o programa a ser executado está todo em uma memória já no instante em que ele é ligado, dai a importância de ter uma memória não volátil com capacidade adequada.

O primeiro tipo é a ROM (Read-only memory), que é uma memória cujo conteúdo é definido na fabricação e não pode mais ser alterado. Este tipo de memória é usado principalmente para firmware, quando se vai produzir uma grande quantidade e é improvável que seja encontrado um bug catastrófico.

Uma variação da ROM é a PROM (Programmable read-only memory). Esta memória vem de fábrica vazia e pode ser gravada uma única vez em equipamento especializado. É usada quando o volume não justifica (economicamente) usar a ROM.

Nos anos 80 era comum o uso da EPROM (Erasable PROM). A EPROM é uma PROM que pode ser apagada, este apagamento é feito expondo o componente a luz ultra-violeta por algumas horas. A gravação também requer um equipamento especializado.


Uma EPROM 2732 (4KBytes)
quantas lembranças!

O mais comum hoje em dia é o uso de memória Flash para armazenar o firmware. Este tipo de memória está bastante disseminado na forma de pen-drives e cartões de memória SD, Memory Stick, etc, porém o usuário destes produtos normalmente não percebe as limitações e características da memória Flash.

O primeiro ponto importante é que existem três operações muito distintas na memória Flash:
  • a leitura é uma operação rápida e que não requer cuidados especiais.
  • a escrita tem a característica de permitir apenas alterar bits de valor '1' para o valor '0'. A operação no sentido contrário ('0' para '1') não pode ser feito por uma escrita. A escrita é uma operação mais lenta que a leitura.
  • o apagamento coloca os bits em '1'. Além de ser uma operação demorada, na maioria dos casos não pode ser feita sobre uma única posição de memória. O apagamento é normalmente feito por blocos ou setores. Existe um limite para o número de apagamentos que podem ser realizados em um setor (da ordem de 100 mil a 1 milhão). Isto significa que não é viável manter variáveis de alteração frequente em memória Flash.
Na maioria dos casos as três operações podem ser feitas sem retirar a memória do circuito. Muitas vezes a escrita e apagamento podem ser inclusive feitas sob controle do processador, permitindo a atualização de firmware em campo.

Alguns fabricantes se referem a memórias Flash de programa (com poucos setores grandes), e de dados (com muitos setores pequenos, como 512 bytes). Estas últimas são mais apropriadas para armazenamento de arquivos, utilizando-se estruturas especiais que evitam que os acessos sejam concentrados sempre nos mesmos setores.

Por último, temos a EEPROM (Eletrically Erasable PROM) ou NVRAM (Non-volatile RAM), que é outro tipo de memória que pode ser gravado e apagado diretamente no circuito. As diferenças entre a EEPROM e a Flash são a tecnologia de implementação da memória no chip e a EEPROM normalmente ter uma capacidade menor e efetuar o apagamento internamente dando a impressão de que cada posição pode ser alterada individualmente.

Memória RAM

A memória RAM é uma memória onde leitura e escrita podem ser feitas à vontade, porém o conteúdo é perdido quando ela perde a alimentação. A RAM é um recurso escasso nos microcontroladores, exceto nos modelos mais avançados (e caros). Memórias acima de 2K são muitas vezes luxo e memórias abaixo de 512 bytes não são incomuns.


sábado, agosto 09, 2008

Wallpapers

Criei há muito tempo o habito de trocar de wallpaper a cada poucos meses. Um bom wallpaper descansa a vista naqueles momentos de contemplação enquanto tentamos resolver um problema difícil. Passo aqui algumas dicas de onde obter algumas boas figuras.

Minha preferência é por wallpapers de tons azulados e figuras meio surreais, que estimulam a imaginação. Figuras mais realistas, como fotos de pessoas, não me atraem muito.

Digital Blasphemy

Uma primeira parada é o Digital Blasphemy. A galeria grátis tem somente 20 imagens, mas são todas de alta qualidade.

Oyonale

Há muitos anos atrás, eu comprava uma revista inglesa de informática, a PC Format. Em um dos primeiros números que comprei vinha o POV-Ray, um programa para gerar imagens foto-realistas a partir de uma descrição geométrica. Oyonale é o site de um artista que usa o POV-Ray e outras ferramentas para criar imagens digitais. Uma boa pedida para começar é o wet bird, uma imagem que parece uma foto.


Worth1000

O nome do site vem de "a picture is worth a thousand words" (uma imagem vale mil palavras). É um site de competições de manipulação de imagens (principalmente com photoshop). Após ver algumas imagens, é provável que você deixe de acreditar definitivamente em fotos. Para acessar as fotos em alta resolução, você precisa se cadastrar gratuitamente. Alguns concursos são mais propícios para wallpapers, outros são pura diversão. O site fica aqui, e abaixo algumas imagens que já usei como wallpaper.

Doctor Who

Doctor Who é uma cultuada série de ficção científica da BBC. No site oficial você encontra algumas imagens interessantes:



(é, esta não é azulada e é uma foto...)

sexta-feira, agosto 08, 2008

Microcontroladores - Parte 2

O que são Microcontroladores?

Vou partir da definição contida na Wikipedia:

“A microcontroller is a computer-on-a-chip ... a type of microprocessor emphasizing high integration, low power consumption, self-sufficiency and cost-effectiveness. ... the microcontroller typically integrates additional elements ... At clock speeds of as little as a few MHz or even lower, microcontrollers often operate at very low speed compared to modern day microprocessors... They consume relatively little power...”

ou, na nossa lingua, com os meus destaques:

"Um microcontrolador é computador-em-um-integrado ... um tipo de microprocessador enfatizando alta integração, baixo consumo de energia, auto-suficiência e baixo custo* .. um microcontrolador tipicamente integra elementos adicionais... Microcontroladores muitas vezes trabalham com velocidades muito menores que os microprocessadores mais atuais, às vezes uns pouco MHz ou menos ... Eles consomem relativamente pouca energia..."

* Ok, baixo custo não é uma tradução precisa, mas não achei um termo melhor


Como a maioria das definições, existe uma certa ambigüidade e espaço para discussão sobre casos específicos. Destaco nela:
  • Um microcontrolador é um computador - tem uma CPU e executa um programa.
  • Além da CPU, um microcontrolador integra outros componentes no mesmo chip. Algumas aplicações requerem poucos componentes além do microcontrolador.
  • As velocidades são muito menores que as de um microprocessador para um PC. Isto não significa que eles sejam necesssariamente lentos, podemos ainda estar falando de milhões de instruções por segundo.
  • Os microcontroladores são muito usados em alicações com bateria e economia de energia é normalmente um dos primeiros requisitos. Usando as técnicas corretas, pode-se operar por anos alimentado por uma pilha.
Uma outra forma de definir microcontrolador é vendo as características de suas aplicações típicas:
  • Estamos falando de aplicações embarcadas, onde o microcontrolador está embutido dentro de um dispositivo e o usuário (ou operador) não percebe que está interagindo com um computador.
  • O objetivo típico e colocar inteligência em um produto. O microcontrolador coleta uma série de informações através de suas entradas e em função delas atua através das suas saída.
  • Um uso importante, mas não tão comum, é usar um microcontrolador para substituir hardware, implementado um função lógica complexa. Dada a alta integração e baixo custo, isto pode ser mais barato que colocar vários chips "burros" e certamente é mais flexível.
Embora os microcontroladores sejam menos visíveis que os microprocessadores para PC, eles são muito mais comuns em termos de quantidade. Uma estimativa é que os microcontroladores sejam 70% dos microprocessadores vendidos. Na sua casa você provavelmente tem uma ou duas dúzias deles, escondidos no forno de microondas, na máquina de lavar, na TV, no aparelho de som, etc. Um carro moderno pode ter uns 50 microcontroladores.

No próximo post vamos ver que tipo de "elementos adicionais" estão tipicamente presentes nos microcontroladores.

quinta-feira, agosto 07, 2008

Cuil: O que está dando de errado

O Cuil é um sistema de buscas lançado com estardalhaço na semana passada e que está recebendo muitas e violentas críticas. O motivo é alguns erros que podem ser considerados primários para uma empresa que se gaba de ser criada e gerenciada por ex-funcionários do Google.

O Nome

Não há dúvida que hoje em dia é muito difícil achar um bom nome que ainda não seja marca registrada de alguem. Entretanto, a Cuil caprichou ao escolher um nome:
O Resultado das Buscas

A Cuil procura se destacar por fornecer resultados diferentes. Infelizmente, diferente não é a mesma coisa que pertinente. O Cuil parece propositadamente dar menos prestígio aos sites mais óbvios, como a Wikipedia. Experimentei procurar Brasil, o resultado traz "Capoeira Brasil", "Sergio Mendes Discography", "MTV Brasil", "Brazilian Embassy - Washington DC", etc:

Como comparação, experimente procurar Brasil no Google. Outros resultados estranhos foram retornados procurando 'Xuxa' e 'Xuxa Meneguel'.

Também não colaborou muito o fato do Cuil ter congestionado no lançamento.

Imagens nos Resultados

A idéia de colocar uma imagem ao lado dos resultados parece muito boa no começo. Complica um pouco quando as imagens não batem com os resultados (por exemplo, procurando Glascow, um dos resultados era 'Glasgow Centre for the Child and Society' - com uma imagem do Osama Bin Laden!). Na busca por Xuxa, as fotos dos dois primeiros resultados me pareceram estranhas - e não estavam nos links correspondentes:

A apresentação de imagens abre ainda uma caixa de pandora: as imagens inadequadas. Já imaginou você pesquisar o seu nome e aparecer uma imagem pornográfica? Isto já aconteceu com o Cuil (e antes que alguém pergunte, não foi comigo).

Concluindo

Até o momento o Cuil parece ter mais barulho que conteúdo e sua única utilidade é como diversão, vendo que coisas estranhas ele retorna. Mas pelo menos ele começou melhor que o Qtrax, que fez muito mais barulho com conteúdo zero.

quarta-feira, agosto 06, 2008

Google Code Jam 2008 - Triangle Areas

Triangle Areas foi o segundo problema da 2a rodada on-line do Code Jam 2008. Fiquei a maior parte das duas horas da competição tentando resolvê-lo sem sucesso. Curioso, baixei as soluções dos dois primeiros colocados e me assustei com a simplicidade delas. Duas perguntas me surgiram: como eles chegaram nesta solução e como garantir que elas estão corretas. Após quase quatro dias de ruminações, a luz surgiu hoje enquanto vazia a barba.

O Problema

Raspando o problema à sua essência, são dados três números inteiros N, M e A, maiores que zero. O problema consiste em achar um triângulo (xa,ya), (xb,yb), (xc,yb) cuja área seja A/2 com x e y inteiros e 0 ≤ x ≤ N e 0 ≤ y ≤ M (ou indicar que o problema é impossível).
A Solução

A fórmula para a área de um triângulo a partir das coordenadas dos pontos que o compõe é:

|xa*yc - xa*yb + xb*ya - xb*yc + xc*yb - xc*ya|/2

É claro que os casos de teste eram grande o suficiente para tornar inviável o teste de todas as combinações por força bruta. É preciso, portanto, simplificar.

Se assumirmos que o ponto a é a origem (0,0) a fórmula se simplifica para:

|xc*yb - xb*yc|/2

Ainda assim são valores demais para a força bruta. Vamos tentar simplificar um pouco mais e assumir que xb e yc são zero, fazendo um triângulo retângulo encostado nas bordas:
Neste caso ficamos com xc*yb = A. Ou seja, precisamos quebrar A em dois fatores. Dá para perceber que um A primo e maior que N e M estraga a brincadeira (por exemplo, se N=2 e M=6 não conseguimos achar um triângulo com A=7). Simplificamos demais.

Vamos tentar fazer xb =1. Ficamos com |xc*yb - yc| = A. Será que isto resolve?

Em primeiro lugar, é óbvio que se A for maior que N*M o problema é impossível (se você não perceber isto pelas fórmulas, considere que temos um retângulo de área N*M e que o maior triângulo que conseguimos colocar nele terá área N*M/2).

A questão é: para qualquer valor de A maior que zero e menor ou igual a N*M conseguimos achar xc, yb e yc que atendam à nossa fórmula? A resposta é sim. O segredo é reparar que a fórmula se assemelha muito a uma divisão de inteiros (exceto pelo '-' ou invés de '+'): podemos considerar que xc é o quociente da divisão de A por yb e yc é uma espécie de resto.

A coisa fica mais clara se forçarmos yb = M. Ficamos com |xc*M - yc| = A. Variando xc de 1 a N e yc de 0 a M-1 conseguimos todos os valores de 1 a N*M.

O Código

Resolvido o problema, o código é incrivelmente trivial:
#include 

void main (void)
{
int iCase, nCases;
int N, M, A, xc;

scanf ("%d", &nCases);
for (iCase = 1; iCase <= nCases; iCase++)
{
scanf ("%d %d %d", &N, &M, &A);
if (A > N*M)
printf ("Case #%d: IMPOSSIBLE\n", iCase);
else if ((A % M) == 0)
printf ("Case #%d: 0 0 1 %d %d 0\n", iCase, M, A/M);
else
{
xc = (A/M)+1;
printf ("Case #%d: 0 0 1 %d %d %d\n", iCase, M, xc, xc*M - A);
}
}
}
Pena que não tive a capacidade e frieza de achar esta solução durante a competição...

Microcontroladores - Parte 1

No final de março participei do Quarto Encontro de Programadores C & C++ em São Paulo, apresentando a palestra "Programação em C para Microcontroladores". É esta palestra que vou repassar nesta nova série de posts. O inevitável powerpoint pode ser baixado daqui, porém é apenas uma série de lembretes para o apresentador. Os masoquistas poderão se enfadar com o vídeo da apresentação completa, que está aqui.

O material coberto pela palestra, e que será vistos nos próximos posts, é o seguinte:
  • O que são micro-controladores
  • Recursos mais comuns dos micro-controladores
  • Programação em C dos micro-controladores: porque e dificuldades
  • Exemplos: alguns microcontroladores com que já tive contato e os respectivos ambientes de programação em C. Serão vistos sucintamente microcontroladores das famílias PIC, 8051, MSP430 e ARM.
  • Depuração de sistemas com microcontroladores
  • Conselhos Finais

terça-feira, agosto 05, 2008

Firefox 3 e Add-ons

Como muita gente, comecei a usar o browser Firefox nos tempos da versão 1.x. Era uma época negra para o Internet Explorer. Abandonado pela Microsoft, era uma presa fácil para os exploradores de vulnerabilidades.

Além da expectativa de maior segurança, o Firefox tinha uma vantagem óbvia: as abas. Sou hoje totalmente dependente das abas, me atrapalhando todo quando uso um IE antigo.

Com o passar do tempo tivemos o Firefox 2.x (que não me trouxe grandes vantagens) e o IE 7 que colocou a Microsoft novamente no páreo. Embora os partidários de cada um digam o contrário, na minha experiência os dois browsers apresentam com regularidade falhas de segurança e são, na maioria dos casos, prontamente atualizados pelos responsáveis.

Seja por limitação das especificações ou por incompetência na implementação, o fato é que dificilmente um página é apresentada da mesma forma pelo Firefox e pelo IE. Em alguns casos extremos, uma página só é usável em um deles (e não estou me referindo a páginas que requerem controles ActiveX). Por este motivo, uso os dois browser no meu micro no trabalho (o Firefox é o principal e o IE é usado somente para alguns acessos). Cheguei a baixar o Firefox 3 no "download day", mas não cheguei a instalar.

O meu micro de casa esteve por muito tempo desconectado da internet e tinha somente o IE7. Após finalmente conectá-lo a internet e operar por algum tempo com o IE, resolvi instalar o Firefox 3 por um motivo incomum. A maioria dos meus posts para o blog são escritos no Notepad e passados para o editor do Blogger via cut-and-past. Por estranho que parece, o comportamento do past é diferente nos dois browsers, com o IE a terminação das linhas não fica como eu quero.

Já que ia instalar o Firefox, resolvi instalar loga a versão 3.01 (pois é, apesar do longo beta um mês após lançar a 3.00 foi preciso lançara a 3.01, mais uma prova que o Firefox não é perfeito). Aproveitei para rever a lista de add-ons que fui acumulando no passado e adotar alguns novos. A lista de add-ons que tenho instalado no momento é a seguinte:
  • Fast Dial: cria uma página inicial com miniaturas (estáticas) dos sites que você selecionar. Já tinha pensado em criar um página HTML com os links dos sites que normalmente acesso, mas isto é muito mais prático e bonito. 06/jan/09: A versão 2.15 desrespeita o usuário, substituindo o mecanismo default de busca e acrescentando sites sem pedir permissão. Nestas condições não dá mais para ser recomendado.
  • DownThemAll!: os recursos para download dos browser são muito limitados. Esta extensão simplifica os downloads e os deixa mais confiáveis.
  • DownlloadHelper: minhas experiências de assisitir video streaming é sempre frustante, com pausas nas piores horas. Esta extensão permite salvar em disco a maior parte destes vídeos, para depois ver com calma (no caso de vídeos do YouTube, recomendo o VLC. Nota: o DownloaHelper possui o recurso de apresentar uma lista de sites com vídeo baixável. Esta lista pode incluir sites com vídeos de conteúdo adulto (leia-se sexo explícito), o que é uma vantagem para alguns e problemas para outros.
  • SQLite Manager: é meio estranho isto ser um add-on de browser, mas certamente é uma mão na roda para quem usa o SQLite. Para quem não conhece, o SQLite é um sistema de gerenciamento de base de dados relacional contido em uma pequena biblioteca. Esta extensão permite manipular bases criadas com o SQLite.
  • PDF Downloader: estou começando a usar esta extensão que promete resolver aquele incomodo terrível de clicar sem querer em um link para um PDF e ser surpreendido com o Acrobate Reader abrindo e segurando o browser.
Além desses, já usei uma época o Html Validator, que indica erros no HTML da página sendo apresentada. Algo certamente útil para desenvolvedores Web, o que não é bem o meu caso.

segunda-feira, agosto 04, 2008

Google Code Jam 2008 - Online Round 2

Neste sábado passado (no horário brasileiro) ocorreu a segunda rodada da competição. Após as minhas dificuldades na rodada anterior, minha única expectativa era conseguir resolver pelo menos parcialmente um problema. Não consegui nem isto! Neste post faço um primeiro levantamento do que faltou para conseguir um desempenho melhor.

A Segunda Rodada

Como era de se esperar, a segunda rodada foi mais difícil e mais disputada. Foram 2 horas e 4 questões. Como da vez anterior, as questões tinham pesos diferentes. Os últimos classificados para a próxima fase fizeram 20 pontos o que corresponde a acertar por completo pelo menos um problema (exceto o teoricamente mais fácil) ou então acertar parcialmente 3 problemas. Por outro lado, apenas os 16 primeiros conseguiram resolver totalmente os quatro problemas.

Pretendo estudar nas próximas semanas as soluções das questões desta rodada e da anterior; à medida em que conseguir vou publicando no blog.

O Que Faltou

Faltou bastante coisa! Para conseguir ir bem numa destas competições é necessário prestar atenção em algumas coisas e um certo preparo, que o meu dia-a-dia certamente não traz. Como fiquei sabendo meio com pouca antecendendia e só decidi participar na véspera, praticamente não me preparei. Alguns pontos básicos:
  • A Escolha da Linguagem: a minha opção por usar o C, embora não tenha comprometido o meu desempenho, talvez não seja ótima. Linguagens como C++ e Java oferecem maiores recursos em suas bibliotecas padrão (se bem que a programação não precisa ser orientada a objeto), agilizando a codificação da solução.
  • Conhecimento da Biblioteca: No meu dia a dia uso uma parte muito pequena da biblioteca padrão do C e dependi demais do help. O ideal é saber de cor e salteado as funcionalidades da biblioteca. Isto vale dobrado para o caso de optar por uma linguagem que não use no dia-a-dia.
  • Conhecimentos Específicos da Linguagem e da Biblioteca: Os problemas envolvem algumas partes específicas como entrada e saída e manipulação de números inteiros de 64 bits e ponto flutuante.
  • Conhecimentos de Algorítmos: Alguns problemas envolvem algorítmos clássicos que eu nunca cheguei a estudar formalmente: geração de combinações, programação dinâmica, etc. Já comprei um bom livro, falta estudar.
  • Conhecimentos de Matemática: Particularmente Teoria dos Números e Geometria.
  • Resolução de Problemas: Existem técnicas para a solução de problemas, e eu as desconheço. Tenho um livro que comprei para o meu filho, mas ele me pareceu muito confuso, preciso tentar estudá-lo e, se for o caso, procurar um melhor.
Além de tudo isto, acabei deixando de lado os cuidados básicos de fazer uma prova: alimentação, descanço, ambiente apropriado, ler todas as questões antes de tentar resolver uma, não entrar em pânico, etc.

Estou torcendo para ano que vem a Google promover uma competição com regras parecidas, se tudo correr bem espero estar melhor preparado e conseguir avançar mais.

sábado, agosto 02, 2008

Google Code Jam 2008 - Text Messaging Outrage

Como comentei antes, participei das rodadas 1A e 1B. Resolvi dar uma olhada depois na rodada 1C e me deparei com uma surpresa: um problema fácil! Consegui resolvê-lo sem pressa em menos de meia hora, o que é bem melhor do que a minha experiência com os demais problemas.

O Problema

Retirando o lero-lero costumeiro, o problema é o seguinte: temos um teclado com K teclas, onde queremos colocar L letras. O teclado funciona como os teclados de celular, se tem duas letras na mesma tecla, é preciso apertar a tecla uma vez para a primeira letra e duas vezes para a segunda. Queremos reduzir o número de apertões para uma mensagem, sabendo quantas vezes ocorre cada letra na mensagem. A saída do programa é o número mínimo de apertões.

Tomando um exemplo simples: suponha que temos uma única tecla e duas letras (A e B). Se a mensagem a digitar tiver 3 Bs e 1 A, colocando [A B] na tecla são necessários 1 + 2*3 = 7 apertões, colocando [B A] reduzimos para 3 + 1*2 = 5.

A Solução

A solução me pareceu óbvia: ir colocando as letras nas teclas em ordem decrescente de ocorrência. Assim as letras mais comuns precisam de menos apertões. Ou seja:
  • ler as ocorrências
  • ordenar
  • percorrer as letras ordenadas
Os limites para os small e large input são bem razoáveis, o único cuidado é que a quantidade de apertões pode estourar a capacidade de um int.

O Código

O código é bastante simples e direto. Usei a rotina qsort da biblioteca do C para ordenar, preferi não perder tempo escrevendo a minha própria rotina de ordenação.
#define MAX_LETTER 1000

int ocorre[MAX_LETTER];

int compare( const void *arg1, const void *arg2 )
{
return *((int *)arg2) - *((int *)arg1);
}

void main (void)
{
int iCase, nCases;
int P, K, L;
int j, nivel;
__int64 apertos;

scanf ("%d", &nCases);
for (iCase = 1; iCase <= nCases; iCase++)
{
scanf ("%d %d %d", &P, &K, &L);
for (j = 0; j < L; j++)
scanf ("%d", &ocorre[j]);
qsort (ocorre, L, sizeof (int), compare);
nivel = 0;
apertos = 0;
for (j = 0; j < L; j++)
{
if ((j % K) == 0)
nivel++;
apertos += ocorre[j] * nivel;
}
printf ("Case #%d: %I64d\n", iCase, apertos);
}
}
Reparar que P (número máximo de letras por tecla) não é utilizado. O teste (j % K) é um truquezinho para detectar quando acabamos de percorrer todas as teclas e vamos recomeçar da primeira, um nível abaixo.

Vamos ver se na rodada de hoje vai ter algum problema simples assim.

OBS: Segundo o blogger, este é o post 200 do blog!