quinta-feira, dezembro 27, 2007

Sumiço?

Já faz um mês desde o último post, o que aconteceu?

Acumulo de trabalho, principalmente uma correria na primeira metade de dezembro para poder tirar férias na segunda metade. E para ser férias de verdade, fiquei longe do computador pelo menos por alguns dias. A lista de posts inacabados e idéias para novos posts está longa, vamos ver se consigo terminar algum ainda este ano.

terça-feira, novembro 27, 2007

DQTimer - Um timer e cronômetro para Windows - Parte 2


Neste segundo post vou dar algumas explicações sobre o código do utilitário que eu descrevi na primeira parte.

C e WinAPI

Este tipo de utilitário é bem apropriado para ser desenvolvido em C usando a API do Windows, pois basicamente envolve o desenho simples na tela. Como ferramenta usei o velho e confiável Visual C++ 6.

Uma série (incompleta) sobre este tipo de programação pode ser vista aqui e aqui.

Os Estados do Programa

A variável modo indica o estado atual do programa:
  • ANDANDO: o relógio está andando.
  • PARADO: o relógio está parado e ainda não foi decidido se ele funcionará como timer ou cronômetro.
  • PAUSADO: o relógio está parado no meio de uma operação como timer ou cronômetro.
  • ALARME: o relógio está apresentando a indicação de final da contagem regressiva do timer.
Uma janela de Classe

No Windows, uma classe de janela é algo semelhante a uma classe em uma linguagem orientada a objeto: uma espécie de "forma" utilizada para criar as instâncias ou objetos propriamente ditos (no caso as janelas).

A definição de classe utilizada não tem nada de muito especial. O comportamento das janelas desta classe será governado pela Rotina de Janela que veremos adiante.

Na criação da janela são usados dois flags mais incomuns: WS_EX_TOPMOST deixa a janela por cima das demais e WS_EX_TOOLWINDOW cria uma janela sem moldura, sem barra de título e que não aparece na barra de tarefas.

A Rotina de Janela

A interface com operador no Windows funciona através de mensagens. Ocorrências como a movimentação do mouse e o pressionamento dos seus botões ou das teclas do teclado geram mensagens que são passadas para a Rotina de Janela.

No nosso caso, a Rotina de Janela trata as seguintes mensagens (as demais são passadas para DefWindowProc que faz o tratamento padrão do Windows):
  • WM_CREATE: gerada quando a janela está sendo criada, é usada para posicionar a janela e criar um timer de 0,5 segundo.
  • WM_TIMER: na medida do possível, o Windows irá gerar esta mensagem na frequência que solicitamos. Ela é usada para solicitar a atualização da tela.
  • WM_ERASEBKGND: gerada pelo Windows quando toda a janela tem que ser redesenhada, desenha a parte fixa da janela.
  • WM_PAINT: gerada pelo Windows para solicitar a atualização da janela.
  • WM_NCHITTEST: uma mensagem que normalmente é tratada por DefWindowProc, é gerada pelo Windows para identificar a região da janela em que o cursor do mouse está posicionado. No nosso caso, usamos esta mensagem para definir a nossa barra de título e permitir arrastar a janela.
  • WM_LBUTTONUP: gerada quando o botão esquerdo mouse é solto. Usada para detectar os apertões nos botões do programa.
  • WM_DESTROY: gerada quando a janela é destruída, é usada para desligar o timer do Windows e gerar a mensagem WM_QUIT que encerra o programa principal.
A rotina DesenhaT

O desenho do fundo é feito escrevendo o bitmap do fundo por sobre a janela. No Windows isto é feito pela rotina BitBlt, com o auxilio de um "memory device context".

A rotina DesenhaM

Esta rotina é o coração da atualização da contagem. Uma vez que a geração de WM_TIMER não é garantida, a função timer() é usada para obter a data e hora atual em segundos.

Quando a contagem zero é atingida no timer, passa para o modo ALARME e dispara o sinal sonoro através da função PlaySound().

A atualização da tela em si é feita através de BitBlts entre um bitmap com os dígitos e indicações e a janela.

As demais Rotinas
  • Encerra trata o pressionamento do botão Close, destruindo a janela.
  • BotaoHora, BotaoMinuto e BotaoSegundo tratam o pressionamento dos respectivos botões, mudando o valor no mostrador.
  • BotaoClear limpa o mostrador e volta o programa para o estado PARADO.
  • BotaoSS: atualiza o estado conforme o estado atual.
Conclusão

Embora bastantes simples, o DQTimer já é um programa bastante útil. Os mais aventureiros, com experiência em programação Windows, podem incluir funções mais avançadas, como permitir escolher um arquivo WAV para o sinal de alarme.

segunda-feira, novembro 26, 2007

DQTimer - Um timer e cronômetro para Windows - Parte 1

Nestes posts vamos ver o desenvolvimento de um pequeno utilitário para Windows: um timer e cronômetro.

Introdução

Tudo começou com um post no blog Efetividade.net, ilustrado com um timer de cozinha. Nos comentários, alguém mencionou utilitários para PC com esta finalidade e daí surgiu a idéia de fazer um.

A interface com operador

Após algumas idéias mais mirabolantes, decidi me basear no formato de um 'finado' timer digital para cozinha:


Uma vez que este é o tipo de programa que eu pretendo deixar sempre visível na tela do micro, um tamanho pequeno me pareceu mais adequado. Para isto eu preferi abandonar o formato tradicional das janelas Windows (o que permite mostrar algumas técnicas menos comuns no programa). A tela do programa ficou assim:


Uma idéia que tive logo no início foi permitir que o programa pudesse ser usado como timer (contagem de tempo decrescente) ou cronômetro (contagem de tempo crescente). A operação ficou da seguinte forma:

Cronômetro
  • O pressionamento do botão Start/Stop com o mostrador em 0:00:00 inicia a contagem. Pressionamentos seguintes deste botão pausam e retomam a contagem.
  • O botão Clear, com o cronômetro pausado, zera a contagem voltando à condição inicial.
Timer
  • Os botões H, M e S são usados para programar o tempo de espera. O pressionamento do botão Start/Stop inicia a contagem regressiva. Pressionamentos seguintes deste botão pausam e retomam a contagem.
  • O botão Clear, com o cronômetro pausado, zera a contagem voltando à condição inicial.
  • Ao atingir a contagem 0:00:00 o timer pisca a tela e soa um sinal sonoro até que o botão Clear ou Start/Stop seja apertado.
Mostrador

Normalmente mostra a contagem atual em horas, minutos e segundos. Um C é apresentado quando operando como cronômetro e um T quando operando como timer. O C ou T pisca quando o relógio está andando e fica fixo quando o relógio está em pausa.

O executável pode ser baixado daqui. Os fontes estão aqui, no próximo post vou dar algumas explicacões sobre o código.

quinta-feira, novembro 22, 2007

Design Paterns na POG

Nos últimos meses andei dando manutenção em vários programas antigos. Embora não tenha encontrado muitos exemplos dignos do Worse Than Failure, de vez em quando um trecho fica atravessado na garganta.

Aviso: o post a seguir é irônico, quem preferir um texto mais sério dê uma olhada aqui.

Para felicidade de muitos e desespero de um grupo cada vez menor, a POG (Programação Orientada a Gambiarras) vem ganhando cada vez mais adeptos. Embora um dos pilares da POG seja o improviso, é possível detectar uma série de padrões de projeto nas criações dos praticantes desta metodologia.

Seguindo uma tradição não oficial da POG, os exemplos serão apresentados em Visual Basic (que muito consideram a linguagem perfeita para a POG). Seguindo outra tradição, os exemplos não forma testados e nenhuma referência foi consultada.

Constantes

As constantes devem ser preferialmente colocadas diretamente no código. Para maior otimização, quando elas estiverem envolvidas em cálculos deve ser colocado diretamente o valor final.

Estruturas de Dados

Uma das vantagens no VB é a não obrigatoriedade de declaração das variáveis. Isto permite realizar todo o potencial de improviso da metodologia POG.

No caso dos chatos implicarem com as declarações implícitas e obrigarem o uso de "Option Explicit", é essencial o uso de tipos genéricos como variants, strings e ints para garantir a máxima flexibilidade. Com um pouco de engenhosidade uma variável string pode substituir todos os demais tipos, inclusive matrizes.

Validação de Entrada

Infelizmente os usuários insistem em entrar com valores absurdos e em considerar como bug quando o programa retorna valores também absurdos.

A maneira mais adotada na POG para implementar a validação de entrada é fazer testes diretos contra valores ilegais, à medida em que os usuários os forem inventando. Ao detectar um valor ilegal, um valor legal deve ser silenciosamente adotado.

Se isto gerar reclamações, apresente uma mensagem de erro com um texto humilhante e obrige o usuário a refazer uma grande quantidade de passos. Isto terá um efeito disciplinador, fazendo com que o usuário seja cuidadoso na entrada de dados.

Por exemplo, uma construção típica na POG é o teste de um campo vazio:

If Text1 = "" Or Text1 = " " Or Text1 = " " Or Text1 = " " Then
Text1 = "(vazio)"

Tratamento de Erros

Tratamento de erros é para maricas e a POG desaconcelha o seu uso. Entretanto, os gerentes tendem a ficar do lado dos chorões dos usuários e os praticantes da POG se vem obrigados a implementar tratamentos de erros.

O cálice sagrado do tratamento de erro está disponível no VB:

On Error Resume Next

Uma alternativa menos eficaz é o tratamento específico aos erros:

arq$ = "xis"
On Error GoTo DeuCaca
Apaga:
Delete arq$
GoTo Apagou
DeuCaca:
If Error = -123 Then
Begin
If arq$ = "xis" Then arq = "yps" Else arq = "ze"
GoTo Apaga
End
Apagou:

Subrotinas

Os adeptos da POG costumam evitar as subrotinas, preferindo criar trechos imensos de código. No caso de uma mesma funcionalidade ser necessária em mais de um ponto, aplica-se a técnica C&P (Cut and Paste). Além do ganho em desempenho, isto confere a flexibilidade de ter versões ligeiramente diferentes.

Mensagens

Na POG as mensagens apresentadas ao operador seguem sempre a nomenclatura do programa. Por exemplo, é preferível "Código inputado não passou no teste de Módulo 11" ao invés de "Código incorreto, verifique o valor digitado". Neologismos (como o 'inputado' acima) contam pontos extras.

Controle de Fluxo

Na POG o controle de fluxo é obtido através de IFs e GOTOs. Como alternativa aos GOTOs podem ser usados flags e mais IFs. Neste segundo caso existem dois padrões comuns: usar uma única variável para todos os testes ou um nova variável para cada teste. Pontos de bonus para nomes criativos como 'flag', 'teste', 'flag33', etc.

O uso de SWITCH / CASE é desaconselhado pelos puristas na POG.

Traces e Logs

Os traces e logs são fundamentais na POG como o intrumento exclusivo para a depuração. Mensagens típicas de trace e log são "passei por aqui", "ponto 1", "i = 1", "não devia passar por aqui!".

Uma vez forçado o funcionamento do programa, existem duas técnicas comumente usadas: comentar todas as instruções de traces e logs ou deixá-las na execução normal. É considerado um desvio grave da filosofia POG a existência de um controle do nível de log ou trace, principalmente em tempo de execução.

segunda-feira, novembro 19, 2007

Para quem trabalhou sozinho na sexta...

Para quem trabalhou sozinho na sexta (ou hoje em SP)

http://www.bugbash.net/comic/129.html

Obs.: eu trabalhei, mas desta vez a empresa não emendou. Mas a sensação não me é estranha!

sexta-feira, novembro 16, 2007

Pilha e Fila - Os Algorítmos Clássicos

Na série sobre Listas Ligadas, mencionei dois tipos especializados de listas lineares: Pilha e Fila. Neste post vou apresentar os algorítmos clássicos de implementação destes tipos usando alocação sequencial.

Pilha

Uma pilha é uma lista onde as inserções e remoções são sempre feitas na mesma ponta. Desta forma, o item removido primeiro é o que foi inserido por último (LIFO - Last In First Out). As pilhas são úteis quando queremos armazenar temporariamente uma informação que vamos usar logo depois. Por exemplo, a maioria dos processadores utiliza uma pilha para armazenar os endereços de retorno de subrotinas, permitindo que subrotinas sejam chamadas dentro de subrotinas. Algorítmos recursivos (como o quicksort) também costumam usar pilhas.

É costume chamar a operação de inserção na pilha de Push e a inserção de remoção de Pop (na inserção estamos 'empurrando' um elemento no alto da pilha e na remoção o elemento no topo 'pula' para fora da pilha).

A implementação de uma pilha é muito simples. Temos um vetor de N posições para armazenar os elementos e um índice (ou ponteiro) para indicar o topo. Algumas variações são possíveis:
  • Podemos empilhar os itens no sentido de índices (ou endereços) crescentes ou decrescentes.
  • O índice do topo pode apontar para a posição de remoção ou para a posição de inserção.
Duas situações de erro devem ser previstas: tentar inserir um item em uma pilha cheia (overflow) e tentar remover um item de uma pilha vazia (underflow).

Segue um exemplo de implementação em C, empilhando no sentido de índices crescentes e com o índice de topo apontando para a posição de inserção. Neste exemplo a pilha contém ponteiros e o valor NULL é usado para indicar underflow.
#define N 10 // número de elementos na pilha
void *pilha[N]; // a pilha
int topo = 0; // índice para o topo da pilha

// Coloca um elemento no topo da pilha
// Retorna FALSE se pilha cheia
int Push (void *elemento)
{
if (topo == N)
return FALSE;
pilha [topo++] = elemento
return TRUE;
}

// Retira o elemento no topo da pilha
// Retorna NULL se pilha vazia
void *Pop ()
{
if (topo == 0)
return NULL;
return pilha [--topo];
}
(Esta implementação é também um exemplo clássico do uso dos operadores de pós incremento e pré decremento do C).

Fila

Uma fila é uma lista onde as inserções são sempre feitas em uma ponta e as remoções são sempre feitas na outra. Desta forma remove-se sempre o item mais antigo (FIFO - First In First Out). AS filas são úteis para sincronizar duas tarefas assíncronas, armazenado temporariamente dados produzidos por uma delas até serem consumidos pela outra.

Quando examinamos as listas genéricas sequenciais , verificamos que era preciso mover os elementos após uma inserção ou remoção. No caso específico da fila isto pode ser evitado implementando uma fila circular, na qual os ponteiros voltam ao início quando passam do final.

A forma mais convencional de implementar uma fila circular é ter um vetor de N+1 elementos e dois índices (ou ponteiros), um apontando para onde será feita a próxima inserção e outro apontando para onde será feita a próxima remoção. A fila vazia é indicada pela igualdade dos índices (ou ponteiros). Para não confundir fila cheia com fila vazia, deixa-se sempre pelo menos uma posição livre no vetor (daí ele ter N+1 posições para armazenar N elementos).
#define N 10  // número máximo de elementos na fila
void *fila [N+1]; // a fila
int iPoe = 0; // indice para onde inserir
int iTira = 0; // indice para onde retirar

// Coloca um elemento na fila
// Retorna FALSE se fila cheia
int Poe (void *elemento)
{
int aux;

// calcula o valor de pPoe após a inserção
aux = iPoe + 1;
if (aux > N)
aux = 0; // circula

// Testa fila cheia
if (aux == iTira)
return FALSE;

// Coloca na fila
fila [iPoe] = elemento
iPoe = aux;
}

// Retira elemento da fila
// Retorna NULL se fila vazia
void *Tira ()
{
void *aux;

// Testa fila vazia
if (iPoe == iTira)
return NULL;

// Pega o elemento a retirar
aux = fila [iTira];

// Avanca iTira
iTira = iTira + 1;
if (iTira > N)
iTira = 0; // circula

return aux;
}
Um truque comum é usar uma potência de pois para N+1 e fazer o índice dar a volta através de um AND. Por exemplo, Se N+1 for 16, o avanço de iTira no final da rotina Tira pode ser simplificado para
iTira = (iTira+1) & 15;

quarta-feira, novembro 14, 2007

Patch Tuesday - Curiosidades

Para quem ainda não percebeu, a Microsoft disponibiliza as correções do "Automatic Update" sempre na segunda terça de cada mês. É o chamado Patch Tuesday.

Devido à forma como é feito o download dos updates normalmente recebemos o aviso ao ligar o micro na quarta feita (no meu caso, agora a pouco). É comum os updates envolverem trechos do Windows que estão normalmente em execução. Por este motivo é frequente ser necessário reinicar o Windows ao final da atualização (vide MoveFileEx).

O mecanismo usado pelo Automatic Update para baixar as atualizações é chamado de BITS (Background Intelligent Transfer Service), que procura reduzir a interferência do download nas demais operações do micro, utilizando os momentos em que a rede está livre. O BITS pode ser usado por qualquer aplicação, informações sobre ele pode ser vista em

http://blogs.msdn.com/larryosterman/archive/2007/08/20/applet-mitigations-updaters.aspx
http://en.wikipedia.org/wiki/Background_Intelligent_Transfer_Service
http://msdn2.microsoft.com/en-us/library/aa362827.aspx
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnwxp/html/WinXP_BITS.asp

terça-feira, novembro 13, 2007

Listas Ligadas - Parte 7

Com este post vamos encerrar esta passada rápida sobre as listas ligadas, falando sobre a implementação na linguagem C++.

Listas Ligadas em C++

O código apresentado anteriormente pode, é claro, ser utilizado diretamente em um programa C++. Entretanto, é mais elegante criar uma classe que encapsule as estruturas e rotinas. Por exemplo, o destrutor da classe pode percorrer a lista liberando a memória alocada para os nós. As situações de erro, indicadas através de um retorno FALSE nas rotinas anteriores, podem ser sinalizadas através de exceções.

Uma desvantagem do código apresentado anteriormente é que ele é específico para um determinado tipo de elemento (nos exemplos a lista armazenava sempre inteiros). Se precisarmos, por exemplo, de uma lista para inteiros e uma lista para números de ponto flutuante, será preciso duplicar a maior parte do código e das estruturas de dados.

Uma solução, que pode também ser usada em C, é armazenar no nó um ponteiro para a informação ao invés da própria informação. Se este ponteiro for do tipo void *, ele poderá apontar para qualquer tipo de informação. Isto permite, inclusive, guardar em uma lista elementos de tipo diferente. A desvantagem desta solução é que ela é pouco robusta quanto ao controle dos tipos. Além disso, a alocação e liberação das áreas que contém as informações precisa ser feita por uma camada externa à de controle da lista (já que a lista desconhece o formato e tamanho da área de informações).

A linguagem C++ possui um recurso justamente para os casos em que se deseja definir uma função ou classe de forma independente dos tipos dos dados a serem manipulados: os templates.

Um template é uma espécie de macro cujo parâmetro é um tipo ou uma classe. Por exemplo, vamos definir um template de uma função para somar dois números:
template  T Soma (T a, T b)
{
return a+b;
}
Podemos usar este template com qualquer classe que suporte o operador +, o C++ verificará se os parâmetros são do mesmo tipo:
int a,b,c;
double x,y,z;

c = Soma (a,b); // soma dois inteiros
z = Soma (x,y); // soma dois doubles
z = Soma (a,y); // erro, tipos diferentes
Podemos usar templates também na definição de classes:
template  class NO
{
T valor; // dado do elemento
NO *prox; // ponteiro para o elemento seguinte

// ...
};
Portanto podemos criar um template capaz de criar uma classe de lista para cada tipo que precisarmos.

Melhor ainda, isto já foi feito. O Visual C++ possui dois templates para criação de listas duplamente ligadas:
  • CList, que faz parte da MFC; e
  • list, que faz parte da STL (Standard Template Library).
Referências
  • The Art of Computer Programming, Volume 1 Fundamental Algorithms – Donald E. Knuth
  • An Introduction To Data Structures With Applications – Jean-Paul Tremblay & Paul G. Sorenson
  • The C Programming Language – Brian W. Kernighan & Dennis M. Ritchie.

segunda-feira, novembro 12, 2007

Listas Ligadas - Parte 6

Listas Duplamente Ligadas

Uma desvantagem da lista ligada simples é que podemos seguir os links apenas em uma direção. Por exemplo, nas rotinas de inserção tivemos que usar duas variáveis, uma para guardar o endereço do nó atual e outra para guardar o endereço do nó anterior.

Na lista duplamente ligada armazenamos em cada nó dois ponteiros, um para o próximo nó e outro para o anterior. Ficamos com algo assim:
// estrutura de um elemento (nó) da lista
typedef struct no_lista
{
int valor; // dado do elemento
no_lista *prox; // ponteiro para o elemento seguinte
no_lista *ant; // ponteiro para o elemento anterior
} NO;

// variavel que aponta para o início da lista
NO inicio; // inicio.prox aponta para o primeiro elemento

// Insere um valor na lista na posição pos
int Insere (int pos, int valor)
{
NO *pno, *p;
int i;

// procura o ponto a inserir
for (i = 0, p = &inicio;
(i <>prox != NULL); i++)
{
p = p->prox;
}
if (i != pos)
return FALSE; // posicao invalida

// Insere
pno = malloc (sizeof (NO));
if (pno == NULL)
return FALSE; // faltou memoria
pno->valor = valor;
pno->prox = p->prox;
pno->ant = p;
if (p->prox != NULL)
p->prox->ant = pno;
p->prox = pno;

return TRUE; // sucesso
}

sexta-feira, novembro 09, 2007

Listas Ligadas - Parte 5

Listas Ligadas

As listas ligadas são uma alternativa às listas sequenciais. Como os elementos não estão em posições sequenciais é necessário acrescentar aos elementos informações que permitam percorrer a lista sequencialmente. Desta forma os elementos são ligados uns aos outros.

Obs.: A forma mais comum de fazer as ligações é através de ponteiros. Entretanto, nada impede de implementar uma lista ligada sobre um vetor alocado estaticamente, usando como link o índice do elemento.

Listas Ligadas Simples

Na sua forma mais simples, uma lista ligada é implementada através de:
  • Um ponteiro para o primeiro elemento da lista
  • Um ponteiro em cada elemento da lista apontando para o próximo elemento
Um valor especial (em C, tipicamente NULL e mais raramente –1) é utilizado para indicar o fim da lista.

As listas ligadas são normalmente representadas graficamente como retângulos (os elementos ou nós), interligados através de setas:

A direção da seta neste diagrama é importante, a origem da seta é um ponteiro que armazena o endereço do elemento na outra ponta. Portanto, é possível percorrer o link apenas no sentido da seta.

O símbolo no final da seta que sai do item 3 (símbolo de aterramento em circuitos elétricos) indica o fim da lista. Em outras palavras, o ponteiro possui o valor especial de fim de lista.

Uma lista vazia é simplesmente

A inserção de um novo item consiste apenas em alterar ponteiros:

Idem para a remoção de um item:

O código abaixo mostra uma implementação simples de lista ligada em C:
// estrutura de um elemento (nó) da lista
typedef struct no_lista
{
int valor; // dado do elemento
struct no_lista *prox; // ponteiro para o elemento seguinte
} NO;

// variavel que aponta para o início da lista
NO *inicio;

// Inicia a lista
void IniciaLista ()
{
inicio = NULL;
}

// Insere um valor na lista na posição pos
int Insere (int pos, int valor)
{
NO *pno, *p;
NO **pant;
int i;

// procura o ponto a inserir
for (i = 0, pant = &inicio, p = inicio;
(i < pos) && (p != NULL); i++)
{
pant = &p->prox;
p = p->prox;
}
if (i != pos)
return FALSE; // posicao invalida
// Insere
pno = malloc (sizeof (NO));
if (pno == NULL)
return FALSE; // faltou memoria
pno->valor = valor;
pno->prox = p;
*pant = pno;
return TRUE; // sucesso
}

// Remove elemento na posição pos
int Remove (int pos)
{
NO *p;
NO **pant;
int i;

// procura o elemento a remover
for (i = 0, pant = &inicio, p = inicio;
(i < pos) && (p != NULL); i++)
{
pant = &p->prox;
p = p->prox;
}
if ((i != pos) || (p == NULL))
return FALSE; // posicao invalida

// Remove
*pant = p->prox;
free (p);
return TRUE; // sucesso
}

// Soma os elementos da lista
int Soma ()
{
int total;
NO *p;

for (p = inicio, total = 0; p != NULL; p = p->prox)
total += p->valor;
return total;
}
As rotinas de inserção e remoção utilizam um ponteiro (pant) para guardar o endereço da variável que contém o endereço do nó atual. Isto dispensa tratar de forma diferente o caso em que o ponteiro a ser atualizado é o ponteiro para o inicio da lista. Uma forma de melhorar a legibilidade, desperdiçando um pouco de memória, é usar um nó para guardar o ponteiro de início:
NO inicio; // inicio.prox aponta para o primeiro elemento

// Insere um valor na lista na posição pos
int Insere (int pos, int valor)
{
NO *pno, *p;
NO *pant;
int i;

// procura o ponto a inserir
for (i = 0, pant = &inicio, p = inicio.prox;
(i < pos) && (p != NULL); i++)
{
pant = p;
p = p->prox;
}
if (i != pos)
return FALSE; // posicao invalida

// Insere
pno = malloc (sizeof (NO));
if (pno == NULL)
return FALSE; // faltou memoria
pno->valor = valor;
pno->prox = p;
pant->prox = pno;
return TRUE; // sucesso
}
Comparando uma lista sequencial a uma lista ligada, temos:
  • A lista ligada consome memória adicional para os links;
  • É fácil e rápido inserir e remover elementos, pois basta alterar ponteiros;
  • O acesso a um elemento qualquer da lista (acesso randômico) é mais trabalhoso e lento na lista ligada, pois é preciso percorrer os links;
  • O acesso sequencial para frente tem velocidade bastante semelhante;
  • É fácil quebrar e juntar listas, pois basta alterar ponteiros;
  • A estrutura de links da lista ligada leva facilmente a estruturas mais complexas, como uma lista onde os elementos são listas.
Portanto uma lista ligada é apropriada quando são esperadas várias inserções e/ou remoções e o acesso é essencialmente sequencial. Um exemplo é quando se deseja manter ordenada uma lista que sofre seguidas inserções e é pesquisada por busca sequencial.

No próximo post vamos ver as listas duplamente ligadas.

quinta-feira, novembro 08, 2007

Lista Ligadas - Parte 4

Neste post vamos examinar as Listas Lineares, com destaque para as Pilhas e Filas.
Listas Lineares

Definição

Listas Lineares são listas que apresentam somente uma relação de adjacência. Em uma lista linear existe um primeiro elemento e um último elemento, todos os demais elementos possuem um elemento anterior e um elemento seguinte.

Operações Básicas

As operações básicas que vamos examinar são:
  • Inserir um elemento em uma lista
  • Remover um elemento de uma lista
  • Percorrer os elementos de uma lista
Listas Lineares Especializadas

Existem dois tipos especializados de listas lineares que são encontrados com freqüência:
  • Uma pilha é uma lista onde todas as inserções e remoções são sempre feitas na mesma ponta. Desta forma, o item removido é sempre o que foi inserido mais recentemente. Por isso, as pilhas são à vezes chamadas de LIFO (last in first out, último a entrar primeiro a sair). Você pode visualizar este tipo de lista como uma pilha de caixas:

  • Uma fila é uma lista onde todas as inserções são sempre feitas em uma ponta e as remoções são sempre feitas na outra ponta. Desta forma, o item removido é sempre o que foi inserido a mais tempo. Por isso, as filas são à vezes chamadas de FIFO (first in first out, primeiro a entrar primeiro a sair). Você pode visualizar este tipo de lista como uma fila de pessoas:

Alocação Seqüencial

A maneira mais simples e óbvia de implementar uma lista é mantendo os elementos seqüencialmente na memória. Podemos fazer isto tanto usando um vetor alocado estaticamente como uma área alocada dinamicamente.

Um exemplo de alocação sequencial estática para uma lista genérica:
int lista [10];  // área para guardar a lista
// lista pode ter até 10 elementos
int tamlista; // número de elementos atualmente na lista

// inicia lista
void IniciaLista ()
{
tamlista = 0; // lista está vazia
}

// Insere um elemento na lista na posição pos
// (as posições são numeradas de 0 a tamlista-1)
int Insere (int pos, int elemento)
{
int i;

if (tamlista == (sizeof(lista)/sizeof(int)))
return FALSE; // lista cheia
if ((pos <> tamlista))
return FALSE; // posicao invalida
if (pos == tamlista)
{
// inserir no final
lista[tamlista++] = elemento;
}
else
{
// inserção no meio, mover os elementos seguintes
for (i = tamlista; i > pos; i--)
lista [i] = lista [i-1];
lista[pos] = elemento;
tamlista++;
}
return TRUE;
}
A rotina de inserção acima mostra uma desvantagem da alocação sequencial: é preciso mover os elementos na memória quando é feita uma inserção ou remoção.

Obs: no caso de filas e pilhas, onde as inserções e remoções são feitas nos extremos, é possível evitar a movimentação dos elementos.

Por outro lado, o acesso aleatório as elementos é muito simples. A rotina abaixo calcula a soma de todos os elementos da lista:
int Soma ()
{
int i, total;
for (i = total = 0; i < tamlista; i++)
total += lista[i];
return total;
}

No próximo post vamos examinar as Listas Ligadas Simples.

quarta-feira, novembro 07, 2007

Listas Ligadas - parte 3

Prosseguindo em nossa série, vamos concluir a introdução falando sobre o armazenamento de estruturas cujo tamanho varia durante a execução do programa.

Alocação Dinâmica de Memória em C

As declarações de variáveis em C que apresentamos até agora são o que chamamos de alocação estática: as posições de memória para armazenar as variáveis são definidas no momento da sua declaração e não se alteram mais.

A alocação estática é muito prática, segura e eficiente, porém impõem que o tamanho alocado será fixo durante toda a execução do programa. No caso de vetores, matrizes e listas isto pode não ser apropriado.

Existem duas funções básicas em C para alocar e liberar memória dinamicamente: malloc e free. A rotina malloc reserva uma determinada quantidade de bytes e retorna o ponteiro para a primeira posição. A rotina free libera uma região de memória, deixando-a disponível para alocações futuras. Uma vez que a rotina malloc enxerga a memória simplemente como uma sequência de bytes, cabe ao programador determinar quantos bytes são necessários para armazenar a informação e usar um cast para informar para que tipo de dado o ponteiro irá apontar.

Começando com um exemplo simples, a sequência abaixo aloca dinamicamente uma variável do tipo inteiro e armazena zero nela:
int *p;

p = (int *) malloc (sizeof (int));
*p = 0;
Reparar o uso de sizeof para determinar o tamanho em bytes da variável, o cast (int *) para informar que o ponteiro retornado por malloc será usado para apontar para um inteiro e *p para acessar a variável apontada por p.

Uma sequencia semelhante pode ser usada para alocar uma estrutura:
struct circulo *pc;

pc = (struct circulo *) malloc (sizeof (struct circulo));
pc->raio = 10;
A alocação de um vetor de 10 inteiros também é semelhante:
int *pv;

pv = (int *) malloc (10 * sizeof (int));
*pv = 0;
pv[9] = 1; // ultimo elemento do vetor alocado
Por último, um exemplo de alocação de um vetor de estruturas
struct circulo *pvc;

pvc = (struct circulo *) malloc (7 * sizeof (struct circulo));
(*(pvc+2)).raio = 10; // raio do 3o elemento
(pvc+2)->raio = 10; // idem
pvc[2].raio = 10; // idem

Note, mais uma vez, como a semelhança de notação para ponteiros e vetores na última linha do exemplo.

No próximo post vamos começar a examinar as listas, vendo as Listas Lineares.

terça-feira, novembro 06, 2007

Listas Ligadas - Parte 2

Continuando a nossa série, vamos continuar a falar sobre estruturas de dados, vendo dois exemplos importantes de como as estruturas de dados primitivas podem ser combinadas para gerar estruturas mais complexas.

Estruturas

O termo estrutura é usado para indicar uma estrutura não-primitiva composta por uma conjunto estruturado de dados primitivos. Por exemplo, podemos representar um ponto na tela por uma sequencia de dois inteiros contendo as duas coordenadas do ponto. Em C:
struct ponto
{
int x;
int y;
};
Neste exemplo, x e y são os campos da estrutura ponto. Na linguagem C utiliza-se a notação a.b para indicar o campo b da variável a. Por exemplo:
struct ponto pt;
pt.x = 10;
pt.y = 20;
Um campo de uma estrutura pode ser uma outra estrutura, criando um conjunto hierarquizado. Por exemplo, vamos definir uma estrutura para representar um círculo, composta por um ponto (centro) e um valor inteiro (raio):
struct circulo
{
struct ponto centro;
int raio;
};

struct circulo c;
c.centro.x = 20;
Repare no exemplo a notação c.centro.x para indicar o campo x do campo centro da variável c.

A linguagem C permite o uso de ponteiros com estruturas. Por exemplo:
struct circulo *pc;
struct circulo c;
int r, xis;

pc = &c;
r = (*pc).raio;
xis = (*pc).centro.x;
Para simplificar a codificação, a linguagem C permite substituir a notação “(*p).” por “p->” :
r = pc->raio;
xis = pc->centro.x;
Ao definir estruturas mais complexas (como as listas ligadas), pode surgir a necessidade de colocar dentro da estrutura um ponteiro para uma estrutura do mesmo tipo.Em C:
struct circulo
{
struct ponto centro;
int raio;
struct circulo *pc;
};
É importante entender que nessa declaração não estamos colocando uma estrutura dentro dela mesma (o que geraria uma recursão infinita). A linha “struct circulo *pc;” acima simplesmente acrescenta à estrutura circulo uma variável que conterá o endereço de uma outra variável do tipo círculo.

Vetores e Matrizes

Matrizes são conjuntos ordenados com um número fixo de elementos, não é possível acrescentar (inserir) ou retirar (remover) elementos. Um elemento de uma matriz é referenciado através de um conjunto de números inteiros sequenciais, os índices. A quantidade de índices usados para acessar uma matriz é a sua dimensão, uma matriz com dimensão um é um vetor.

Esta definição formal fica mais simples se examinarmos alguns exemplos. Comecemos examinando um vetor com 10 inteiros. Na linguagem C, podemos declará-lo da seguinte forma:
int v[10];
O vetor v é um conjunto com 10 elementos. Os elementos individuais são acessados através dos números 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9, usando a seguinte notação:
v[5] = 3;
Este comando coloca o valor 3 no elemento de índice 5, que é o sexto elemento do vetor v.

Obs.: Na linguagem C os índices começam sempre de 0. Desta forma, um vetor com “n” elementos é acessado por índices de 0 a n-1. O elemento de índice “i” é o elemento “(i+’)-ésimo” do vetor.

Uma forma de visualizar um vetor é como uma sequência de elementos consecutivos:

v[0]v[1]v[2]v[3]v[4]v[5]v[6]v[7]v[8]v[9]

Uma matriz bi-dimensional pode ser visualizada como uma tabela. Por exemplo, considerando uma matriz de inteiros cujo primeiro índice varia de 0 a 2 e o segundo de 0 a 3:
int mat[3][4];

mat[0][0] = 3;
mat[2][3] = 2 * mat[0][0];
mat[0][0]mat[0][1]mat[0][2]mat[0][3]
mat[1][0]mat[1][1]mat[1][2]mat[1][3]
mat[2][0]mat[2][1]mat[2][2]mat[2][3]

A linguagem C trata de forma muito semelhante vetores e ponteiros:
  • as matrizes são armazenadas em posições sequênciais de memória.
  • O nome de uma váriavel do tipo matriz representa o endereço do primeiro elemento:
  • int vet[10];
    int *p;

    p = &vet[0]; // p recebe o endereço do primeiro
    // elemento de vet
    p = vet; // idem
  • Somar ou subtrair “n” a um ponteiro equivale a avançar ou recuar “n” elementos:
  • p = vet+2; // p aponta para o terceiro elemento

    p = vet; // p aponta para o primeiro elemento
    *(p+1) = 2; // (p+1) aponta para o 2o elemento
    // ou seja, equivale a vet[1] = 2
  • Expandindo o exemplo acima, o C considera p[n] equivalente a *(p+n). Ou seja, a última linha acima poderia ser escrita como
  • p[1] = 2;
  • Portanto, usa-se a mesma notação para acessar elementos apontados por um ponteiro (p) e elementos de um vetor (vet).

  • É importante lembrar que “int vet[10];” cria 10 variáveis do tipo inteiro, enquanto que “int *p;” cria apenas uma variável do tipo ponteiro para inteiro. A variável p só poderá ser utilizada para acessar elementos depois de ter sido inicializada.
No próximo post vamos encerrar esta introdução falando um pouco sobre a alocação dinâmica de memória no C.

segunda-feira, novembro 05, 2007

Listas Ligadas - Parte 1

Nesta nova série vou explicar o que são listas ligadas e apresentar os algorítmos envolvidos e algumas formas de implementação em C e C++.

Dê uma forma genérica poderíamos dizer que uma lista é um conjunto ordenado de um número variável de elementos, para a qual estão definidas funções de inserção e remoção de elementos. Para entendermos isto melhor, precisamos primeiro falar um pouco sobre estrutrua de dados.

Estrutura de Dados I

No nível mais baixo, as informações manipuladas por um computador consistem em conjuntos de itens elementares. As maneiras como estes item elementares se relacionam logicamente são as estruturas de dados. As formas como estas estruturas lógicas são implementadas fisicamente na memória de um computador são as estruturas de armazenamento.

Os itens elementares (ou estruturas primitivas de dados) são aqueles manipulados diretamente pelo computador ou linguagem de programação, tais como:
  • números inteiros
  • números reais (ponto fixo ou flutuante)
  • caracteres
  • valores lógicos
  • ponteiros
Obs.: Na maioria dos computadores atuais, os itens elementares são armazenados na memória como sequências de bytes. A distinção entre eles é consequência das instruções utilizadas para manipulá-los e não do conteúdo dos bytes. Por exemplo, um byte contendo o valar hexadecimal 0x30 pode ser interpretado como o número decimal 48 ou o caracter ‘0’, dependendo do código que o manipula. A linguagem C segue esta filosofia, permitindo misturar e re-interpretar (via cast) os tipos quase que livremente. Se por um lado isto dá uma imensa flexibiidade, por outro potencializa erros catastróficos.

Ponteiros

Do ponto de vista teórico, um ponteiro é uma referência a uma estrutura de dados. Do ponto de vista prático, um ponteiro é uma variável cujo conteúdo é o endereço de uma outra variável.

Vamos considerar a seguinte sequência de código C:
int a, b;
int *p;

a = 1;
p = &a;
b = *p;
*p = 5;
Nas duas primeiras linhas declaramos 3 variáveis (dois inteiros e um ponteiro para inteiro). O compilador irá reservar posições na memória para estas variáveis. Suponto que tanto um inteiro como um ponteiro ocupem 4 bytes na memória, podemos ter algo como:
Endereço  Conteúdo
2000 valor de a
2004 valor de b
2008 valor de p
A instrução “a = 1” coloca o valor 1 no endereço 2000. Quando escrevemos “&a” obtemos o endereço de a, portanto “p = &a” coloca o valor 2000 no endereço 2008. A notação “*p” no lado direito de uma atribuição significa:
  • pegue o valor da variavel p (2000 no nosso caso)
  • considere este valor como um endereço e pegue o valor contido neste endereço (1 no nosso caso)
portanto, “b = *p” coloca o valor 1 no endereço 2004.

Por último, “*p” no lado esquerdo de uma atribuição significa:
  • pegue o valor da variavel p (2000 no nosso caso)
  • considere este valor como um endereço e coloque o resultado do lado direito neste endereço (5 no nosso caso)
portanto, “*p = 5” coloca o valor 5 no endereço 2000.


No próximo post vamos ver um pouco mais sobre estrutura de dados, examinando estruturas, vetores e matrizes.

quinta-feira, outubro 18, 2007

Quadrinhos de graça

Não sei o quanto é conhecido, mas o site http://www.comics.com disponibiliza diariamente algumas dúzias de tirinhas, várias delas bem conhecidas (a começar pelo Dilbert). Além da tira diária, estão acessíveis as tiras dos últimos 30 dias. Estão incluídas as tiras dominicais, normalmente coloridas e maiores. Serviços adicionais estão disponíveis por taxas anuais razoáveis.

Para quem souber inglês e estiver cansado do desrespeito dos jornais com os quadrinhos (poucos, alguns de qualidade lamentável e frequentemente repetidos ou fora de ordem), é uma boa pedida. É também uma forma de começar o dia dando umas boas risadas.

Como sugestão, seguem abaixo alguns dos quadrinhos disponíveis:







Dilbert: acho que não precisa falar nada, certo?

Alley Oop: conhecido aqui como Brucutu, um homem das cavernas que viaja no tempo. Não costumo acompanhar diariamente, mas é divertida.
Nancy: conhecida no passado como Periquita (quero ver usar este nome atualmente!). Histórias ingênuas e boas piadas. Uma curiosidade: inicialmente a personagem principal da tira era a tia (que continua roubando corações dos leitores)
Lil'Abner: no Brasil, Ferdinando. O humor cáustico do autor cerca os caipiras ingênuos e honestos das figuras mais estranhas. As mulheres costumas ser extremamente bonitas e os homens extremamente caricaturatos. As tirinhas publicadas são antigas, infelizmente a melhor parte já ficou para trás. Detalhe: não tem tirinha às quintas.
Liberty Meadows: comecei a acompanhar por acaso, ao clicar errado quando selecionava o Lil'Abner. Aventuras muito doidas em um santuários para animais. Destaque (mais uma vez) para as mulheres e para os animais pirados (meus preferidos são Ralph o urso anão, Dean o porco chauvinista e Leslie o sapo hipocondríaco). São também tirinhas antigas, as de domingo não fazem parte da narrativa em curso.
Frank e Ernest: piadas às vezes surrealistas. Tem a vantagem de serem auto-contidas, dá para rir direto na primeira tira.
The Meaning of Lila: olha, não sei bem como eu cai nesta tira, muito menos porque continuo a ler! Talvez seja tentar entender um pouco da ótica feminina.

Detalhes sobre estas tirinhas podem ser facilmente encontrados na Wikipedia.

segunda-feira, outubro 15, 2007

Excel 2007: Explicação para o bug

Embora a Microsoft não pretenda dar mais detalhes sobre o bug, uma explicação extremamente detalhada pode ser encontrada em

http://www.lomont.org/Math/Papers/2007/Excel2007/Excel2007Bug.pdf

Chris Lomont se deu ao trabalho de debugar o Excel, achar a rotina com problema, comparar com a mesma rotina nas versões anteriores e explicar o que aconteceu.

De forma resumida, por motivos de desempenho o Excel possui uma rotina de conversão de ponto flutuante para texto escrita em Assembler. Esta rotina estava escrita no velho assembler de 16 bits e no Excel 2007 foi convertida para usar as instruções e registradores de 32 bits. Neste ponto foram introduzidos dois erros. No caso do cálculo 850 * 77,1 em um determinado momento a rotina anterior possuiu o valor 0xFFFF no registrador AX, o incrementava, resultando em zero, o que causava um desvio. Nos 32 bits, o valor 0x0000FFFF em EAX vira 0x00010000 que não é zero e portanto a execução segue pelo caminho errado. O outro erro é algo parecido mas em outro trecho do código.

Esta análise parece vir de encontro com o que eu tinha chutado no meu post original (será um exemplo de psychic debugging?) : um ponto onde o algorítimo precisa selecionar entre dois caminhos E ocorre um overflow (no meu post eu coloquei ou...). Portanto meu veredito é que ocorreu falha no teste unitário da rotina, que não exercitou corretamente este ponto de decisão.

Desenvolvendo Softwares Agradáveis de Manter

Já mencionei antes os sinais de um programa ruim e o site WTF que contém exemplos de como não fazer um software. Neste post vou tentar algo mais construtivo: sugestões de como escrever softwares que sejam mais agradáveis de manter.

A Raiz do Problema

Para dar manutenção em um programa é preciso entendê-lo. Portanto um programa será mais fácil de dar manutenção na medida em que ele for mais facilmente compreensível. Esta é a principal motivação das evoluções nas metodologias e ferramentas de desenvolvimento. Existe uma limitação do tamanho do contexto que conseguimos manipular, quando o programa ultrapassa este limite nós paramos de entender como o programa funciona e começamos a introduzir bugs.

No início era a linguagem de máquina e o Assembly. Uma operação simples exigia múltiplos comandos e rapidamente o limite era atingido. As linguagens de alto nível permitem colocar mais lógica em menos linhas de código, propiciando (mas não garantindo) uma maior legibilidade. Na chamada programação "espagete", o código era composto de trechos longos com a execução pulando de um ponto para outro por gotos. A programação estruturada procurou colocar ordem na casa, pregando a divisão em subrotinas e o uso de construções de controle padronizadas que sempre são entradas por cima e saídas por baixo (if-the-else, while, switch, etc).

As estruturas de dados tinham problemas semelhantes. Váriaveis globais eram acessadas por pontos dispersos do fonte. A programação estruturada introduziu os módulos e as variáveis locais. A programação orientada a objetos agrupou rotinas e estruturas de dados em classes, favorecendo a criação de interfaces claras e acessos controlados.

Consistência

Fica mais fácil aprender e lembrar as coisas que são iguais ou bem parecidas. Durante o desenvolvimento isto pode parecer cansativo e existe sempre a tentação de ser "criativo". Para ser um bom desenvolvedor é preciso saber onde ser criativo e onde ser consistente.

Dando Nomes

A consistência deve começar nos nomes de variáveis, rotinas, classes e módulos. Por pior que seja uma convenção para os nomes, ele será melhor que nenhuma.

É claro que os nomes devem indicar de forma precisa o que é armazenado na variável, efetuado pela rotina, etc:
  • Evite nomes muito genéricos. Uma variável nItens é bem mais clara que simplesmente n (ou pior ainda, x ou aux).
  • No caso de variáveis lógicas, o nome deve indicar o que representa o valor verdadeiro. Do ruim para o melhor: flag, flagPorta, flagPortaAberta.
  • Revise os nomes sempre que fizer uma alteração no código. Principalmente em rotinas é comum encontrar rotinas cujo nome foi dado devido a uma função que ela deixou de fazer.
Comentários

Os comentários podem ajudar em muito na compreensão de programas. Por outro lado eles podem também atrapalhar. Bons comentários são os que destacam as coisas não óbvias ou resumem o que um trecho mais complicado faz. Comentários ruins são os mentirosos (lembranças de cut-and-paste apressados ou não atualizados após mudanças) e os inúteis (que só ocupam espaço e reduzem a atenção).

Os comentários devem se preocupar mais nos porquês do que nos o que. Consideremos o exemplo clássico:

n = n + 1;

Alguns comentários úteis são

// temos mais um item na tabela
// a rotina OrdenaItens espera o número de itens, não o índice do último

Um comentário inútil é

// soma um a n

Um comentário ruim é

// diminui de um a quantidade de itens

Em alguns casos deve-se comentar também o que não é feito. Por exemplo, podemos ter os seguintes comentários ao invés de n = n + 1;

// n não é incrementado, pois vamos remover o item adiante
// n será incrementado pela rotina InsereItem

A padronização de comentários para variáveis e rotinas é também útil, principalmente para ajudar a lembrar o que deve ser documentado nos comentários.

Simplificando o Código

Durante a fase de depuração é comum mais código ir sendo acrescentado para cobrir casos que não tinham sido previstos inicialmente. Muitas vezes a codificação é encerrada quando o programa funciona. É importante revisar o código e ver se não é possível simplificá-lo (e testá-lo bem após a simplificação para garantir que continua funcionando).

Um exemplo típico de simplificação é detectar trechos repetidos várias vezes e colocá-lo em uma subrotina. Além de reduzir o tamanho do código (o que simplifica o entendimento), acertos e aperfeiçoamentos futuros serão feitos em um único ponto.

No caso de trechos parecidos é freqüentemente possível criar uma rotina "genérica" onde as diferenças de comportamento são feitas condicionalmente em função dos valores dos parâmetros ou de um parâmetro específico para isto. Entretanto, é preciso tomar o cuidado de não exagerar nesta generalidade, criando uma rotina extremamente confusa, cheia de testes. Neste caso rotinas específicas, mesmo que parecidas, pode ser mais claro e fácil de manter.

Um ponto que raramente é revisado são as variáveis lógicas. Se você perceber que está usando com muita freqüência a negação da variável, talvez você tenha escolhido a condição errada. Por exemplo, suponha que você tenha definido flagPortaAberta mas quase sempre você está usando !flagPortaAberta. Neste caso é melhor você passar a usar uma variável flagPortaFechada e se livrar das negações.

Resumindo, com alguns cuidados simples você vai melhorar em muito a qualidade de vida de quem for dar manutenção no código que você está escrevendo hoje. E lembre-se que este alguém pode ser você mesmo.

quarta-feira, outubro 10, 2007

Correção para o Excel 2007

Saiu a correção para o problema no Excel 2007 que eu comentei recentemente.

Relembrando, quando o resultado de uma cálculo fica muito próximo de 65535 ou 65536, o Excel apresenta na tela 100000 ou 100001. O problema ocorre na conversão para texto do valor em ponto flutuante, não no cálculo propriamente dito. Desta forma o valor pode ser usado sem problemas em outros cálculos (desde que o resultado final não seja outro valor na faixa problemática). O problema foi introduzido no Excel 2007 e não ocorre nas versões anteriores.

Infelizmente não foram divulgados mais detalhes, existe muita curiosidade em saber porque esta rotina (que é padrão na biblioteca da maioria das linguagens) foi alterada (ou criada) no Excel 2007 e que tipo de erro de programação causou este problema bizarro.

O anúncio da correção e os links para download estão em

http://blogs.msdn.com/excel/archive/2007/10/09/calculation-issue-update-fix-available.aspx

terça-feira, outubro 09, 2007

Avaliação do Visteon VSB-7705

O Visteon VSB-7705 é um tocador MP3 para carro, que permite a reprodução de CDs, cartões SD-MMC e dispositivos USB.

Aviso

Estou muito longe de ser um aficionado por "som automotivo". Para mim automóvel é um dos piores ambientes para querer se apreciar música, com grandes limitações acústicas, ruído externo constante e a necessidade de prestar atenção na direção e não na música. Confesso ainda que só fui colocar o "som" no carro um anos após a compra.

Um Breve Histórico

No meu carro anterior eu usava um toca-fitas (!). O ponto positivo do meu aparelho antigo é ter uma entrada auxiliar na frente, o que me permitia ligar um reprodutor de CD portátil, com suporte para MP3. Era esta configuração que usava, o MP3 praticamente eliminava a necessidade de trocar de CD durante uma viajem e as falhas de reprodução devido aos onipresentes buracos das ruas e estradas brasileiras.

Infelizmente o aparelho pifou e portanto eu precisava comprar outro para o carro novo.

O Atrativo do VSB-7705

O que me atraiu para o VSB-7705 foi o suporte a cartão SD, uma vez que já uso este tipo de cartão na máquina fotográfica e já tenho um leitor conectado ao meu micro. O formato SD coloca em um pequeno espaço capacidades bem razoáveis por preços idem.

No VSB-7705 o cartão SD fica completamente embutido durante o uso, não ficando nenhuma saliência para fora que possa levar um tranco acidental danificando o cartão e/ou o aparelho. Além disso, o cartão cabe facilmente no estojo da frente destacável.

A Instalação

O meu carro é um Citroen C3 e a instalação foi moleza. Os conectores do carro e do aparelho eram totalmente compatíveis, dispensando gambiarras. Um ponto a mais para o VSB-7705 e que ele já vem com um adaptador para antena e com conectores com fios para facilitar a intalação em veículos com conectores diferentes (ou sem conectores).

Outro ponto de destaque é que o manual apresenta indicações claras e completas dos sinais presentes nos conectores.

O VSB-7705 não foi o primeiro aparelho com SD que eu encontrei, mas li vários comentários de usuários da outra marca reclamando de chiados. No meu caso a qualidade de som me pareceu excelente. O único "defeito" é uma ligeira pausa (1 segundo ou menos) entre uma música e outra (em MP3), o que pode atrapalhar fãs do rock progressivo onde é comum uma faixa continuar direto na seguinte.

Os Recursos

O VSB-7705 tem uma grande quantidade de recursos, mas devo admitir que usei poucos deles até agora.

Como é mais ou menos padrão, a frente é destacável e basculhante. O encaixe não me inspira muita confiança, mas até agora não tive problemas. O display alfanumérico apresenta uma boa quantidade de informações dos arquivos MP3 e tem boa legibilidade. O display tem ainda indicação gráfica do volume. A frente tem também uma quantidade absurda de botões, cada um com um LED decorativo.

Segundo o manual, são suportados formatos MP3, WMA e OGG, os dois primeiros com várias taxas de transferência e frequência de amostragem. Não são suportados arquivo protegidos (DRM). Até agora usei somente MP3 e ele tocou tudo sem problemas.

A conexão direta de um pen-drive na entrada USB não é muito prática, pois o pen-drive fica totalmente exposto para fora. Felizmente o aparelho vem com um cabo adaptador.

O aparelho suporta CD / CD-R e CD-RW, tanto com audio como com arquivos MP3, WMA e OGG.

Para SD e USB existem funções de gerenciamento de arquivo para procurar e apagar arquivo.
Um recurso curioso é a gravação em SD ou pen-drive a partir do rádio, CD ou da entrada auxiliar (que requer um cabo adicional não fornecido).

Tem, é claro rádio AM/FM. As poucas vezes que escutei rádio (FM) o som me pareceu perfeito. Por enquanto ainda nem me dei ao trabalho de colocar as estações que gosto nas memórias.

Para completar, vem um controle remoto IR, o que me parece um acessório meio inútil.

Concluindo

Estou totalmente satisfeito com o VSB-7705. O cartão SD me parece ser a midia perfeita para quem quer ter um som solid-state no carro. O aparelho tem um preço razoável e pode ser encontrado em 12 vezes no cartão nas "boas casas do ramo".

Atualização 28/02/10

Parece que a minha sorte acabou, o display começou a piscar.

Atualização 30/11/10

Acho que agora ele se foi. Há cerca de um mês começou a falhar um dos canais, achei que era mau contato mas estou desconfiando do aparelho. Semana passada o painel parou de funcionar, ao colocar ligava sozinho com o último ajuste. Um reset fez somente perder o último ajuste. Colocando um SD o painel funciona, porém após alguns minutos desliga e religa sozinho. Já encomendei um novo aparelho (de outra marca, é claro).

quarta-feira, outubro 03, 2007

Links diversos

Normalmente não gosto de fazer post somente com links, mas a escrita dos posts mais "sérios" está indo muito devagar e tropecei com alguns links que podem interessar aos leitores.

Assistindo vídeos do YouTube Off-Line
Existem algumas dezenas de opções para isto, no momento estou usando http://www.techcrunch.com/get-youtube-movie/ para baixar em formato FLV, que pode ser tocado pelo VideoLan.

Aulas de Violão e Guitarra
Um uso para os links acima é para baixar os vídeos de justinguitar. Um adicional é que a pronúncia british dele é muito boa, o que pode ser um apoio para quem está aprendendo inglês.

Para os fãs do Open Office
Um lembrete que nem tudo é perfeito: a longa história de um desenvolvedor que criou um add-on para o Calc e o descaso da Sun, que culminou por decidir re-desenvolver o módulo internamente para ficar com os direitos (é, software livre também tem direitos autorais).

Para quem quer dar risadas
Um lista dos oito artigos mais inúteis na Wikipedia e seis perguntas que o último volume do Harry Potter tem que responder (e que de foram respondidas, embora a quinta de forma muito oblíqua). Aviso: não adequado para crianças inocentes!

E por falar em crianças inocentes..
Não é só no Brasil que algumas pessoas estão bravas com a Google a respeito da dificuldade em tirar material impróprio do Orkut.

terça-feira, outubro 02, 2007

13a Competição Anual de Ficção Interativa

Aviso aos fãs de aventuras: já estão disponíveis para download os jogos da 13a Competição Anual de Ficção Interativa. São mais de duas dúzias de jogos. Lembrar somente que são jogos curtos e em grande parte escritos por amadores.

segunda-feira, outubro 01, 2007

Ajude a divulgar a lista brasileira de equipamentos e serviços compatíveis com Linux

...e concorra a MP4 e MP3 players, mochilas Targus, períodos de VoIP grátis e até a ventiladores USB - além de contribuir automaticamente para doações para a Wikipedia e o Wordpress! O BR-Linux coletou mais de 12.000 registros de compatibilidade de equipamentos e serviços (webcams, scanners, notebooks, ...) na sua Pesquisa Nacional de Compatibilidade 2007, e agora convida a comunidade a ajudar a divulgar o resultado. Veja as regras da promoção no BR-Linux e ajude a divulgar - quanto mais divulgação, maior será a doação do BR-Linux à Wikipedia e ao Wordpress.


A idéia inicial era colocar junto deste post o resultado de um teste simples de impressão com a Samsung SCX-4200, mas não deu certo na primeira tentativa (tentei imprimir bootando um Live-CD do Ubuntu) e o prazo da promoção está acabando. Fica a promessa de investigar melhor como usar a impressora (e o scanner) da SCX-4200 e depois postar o que descobrir.

sexta-feira, setembro 28, 2007

Será que o Excel 2007 Desaprendeu a Aritmética?

Esta semana foi descoberto um problema vexatório no Excel 2007, que apresenta um resultado completamente errado para uma conta simples. Esta descoberta tem gerado manchetes do tipo "Excel 2007 não sabe multiplicar", mas o que realmente se passa?

O Bug

O exemplo mais comum do problema consiste em entrar em um célula com a expressão "=77,1*850" (quem estiver com o Windows configurado para o padrão americano deve entrar com '.' no lugar da ','). O resultado apresentado é 100.000 ao invés do valor correto 65.535.

Como Isto Ocorre?

Da mesma forma que a maioria das planilhas e aplicativos que manipulam números, o Excel trabalha internamente com os números em um formato padronizado, o IEEE 754. Este formato é o mais comumente usado e é suportado diretamente pelos processadores atualmente em uso nos PCs.

Este formato é do tipo ponto flutuante, no qual o número é armazenado em duas partes: a mantissa (que é o número em si) e o expoente (que indica onde está a separação entre a parte inteira e fracionária). Uma das vantagens deste formato é suportar uma faixa grande de números em uma capacidade baixa de armazenamento. Por exemplo, vamos supor que vamos armazenar números decimais em três dígitos. Se usarmos um ponto fixo após o primeiro dígito, podemos trabalhar com números entre 0,00 e 9,99. Se considerarmos os dois primeiros dígitos são a mantissa e o terceiro é o expoente, podemos trabalhar com números entre 0,00 e 990.000.000. Uma desvantagem óbvia é que quando somamos números muito diferentes perdemos precisão.

Um outro ponto importante é que neste tipo de notação podemos armazenar somente um subconjunto dos números reais. No meu exemplo podemos armazenar 0,01 e 0,02 mas nenhum dos infinitos números entre eles.

Para complicar o entendimento, na notação IEEE 754 trabalhamos com potências de 2 e portanto temos um 'ponto binário' ao invés de 'ponto decimal'. Como consequência números 'triviais' na notação decimal não podem ser representados na notação binária e vice versa.

O que tem isto a ver com o bug? A primeira coisa é que 77,1 não possui representação exata no formato IEEE 754. Ao multiplicar este valor por 850 obtemos um valor que não é exatamente igual a 65.535 (mas extremamente próximo).

Ao contrário do indicado pelas manchetes, o Excel faz a conta direitinho (quem faz a conta é a CPU não o Excel). Aonde ele 'se borra' é na hora de apresentar o resultado na tela. Ou seja, ao converter a representação binária do resultado para caracteres.

É Grave?

Segundo a Microsoft, o erro na apresentação ocorre somente para 12 combinações das quase 10^19 possíveis. É claro que as operações que levam a estas combinações são também quase infinitas e independem dos números e operações envolvidos. Considerando o tempo que o Excel está no mercado, dá para ver como os casos reais são raros.

Como o erro está na apresentação e não no cálculo, se o valor for usado em outros cálculos o resultado final provavelmente vai ser apresentado corretamente. Quando a Microsoft liberar uma correção, bastará carregar a planilha para o resultado correto ser apresentado, não existe nada a corrigir na planilha em si.

Portanto o problema é mais grave para a imagem da Microsoft que para os seus clientes.

Mas Como Saiu Com Este Bug?

A pergunta chave é: como testar para pegar um bug destes?

Uma vez que o erro está na apresentação, testes automatizados que verifiquem o resultado em si e não o valor apresentado na tela não vão pegar o erro.

O lugar mais provável seria no teste unitário da rotina que converte o número da representação interna para o string apresentado. Considerando a quantidade quase infinita de casos a testar e o minúsculo número de casos problemáticos, fica fácil perceber que é difícil um teste não dirigido pegar este problema. As informações disponíveis são insuficientes para saber se o problema acontece em algum caso limite, por exemplo onde o algorítimo precisa escolher entre dois caminhos ou onde alguma variável pode sofrer overflow ou underflow. Em caso afirmativo, provavelmente faltou um caso de teste que verificasse o funcionamente correto nos dois lados do limite.

Referências

Fiquei sabendo do problema no Joel On Software. Joel que, não por acaso, foi gerente de projeto do Excel (no milênio passado).

A descrição do problema pelos projetistas do Excel pode ser vista aqui.

segunda-feira, setembro 17, 2007

PC Assembler: A Odisséia

Como comentei no post anterior, ao escrever o post sobre a minha nova impressora eu tive a idéia de postar o texto do livro PC Assembler. Parecia fácil, mas foi uma verdadeira odisséia!

Procurando a Midia

Eu estava certo de ter uma cópia no HD. Não achei. Bem, com certeza está um dos muitos CDs de backup. Também não. Nos disquetes? Nada.

Hora de enfrentar o pó da última gaveta do armário de roupas, onde escondi algumas lembranças para escapar do lixo. E achei o disco aí ao lado. Alguns vão reconhecer que é um disquete de 5 1/4", mas poucos vão perceber que tem o corte de desproteção contra gravação nos dois lados. Para quem não entende de arqueologia, este é um disquete de Apple ][.
Parenteses: o mundo em geral pode idolatrar o Steve Jobs mas para os engenheiros Steve Wozniac é o cara. Uma das suas maiores criações foi a interface de disco do Apple ][, que permitiu a comercialização da unidade de disco por um preço extremamente baixo para a época (mesmo com a margem imensa colocada pelo Jobs). Embora a unidade seja para disquetes de face simples, o fato dela não usar o furo de índice (o furo pequeno redondo à direita do centro), permitia usar o segundo lado fazendo o corte na lateral e colocando o disco de ponta cabeça.

O Micro

Na época que eu escrevi o livro, meu computador principal era um Unitron apII TI. Alguns anos depois, evoluí para um TK3000//e da Microdigital que corresponde ao Apple //e. Foi este segundo equipamento que fui buscar na casa do meu pai para ler o disquete. Na foto ao lado, ele já foi devidamente limpo (?).

Uma das várias idéias que o Apple ][ popularizou (e a IBM seguiu) foi o uso de slots para placas de expansão. Como pode ser visto na foto ao lado, o meu micro tem uma quantidade grande de placas.

Separada das demais, na esquerda, está a placa "80 colunas" (o default do Apple ][ é apresentar na tela 40 caracteres por linha). No slot 1 a interface para impressora paralela. No slot 4 um clone do Softcard Z80, um dos primeiros hardwares de sucesso da Microsoft (essencial pois o disco está em formato CPM/80). No slot 6 a mencionada interface de disco, Por último, no slot 7, a minha expansão de memória de 128 KBytes (uma extravagância, que eu usava como RamDisk).

Para completar, o meu primeiro monitor: uma TV muito mal adaptada (fiz a adaptação de forma provisória quando cheguei em casa com o Unitron, funcionou e ficou deste jeito até hoje). No lado direito, duas unidades de disco.

Hora de cruzar os dedos, colocar um disco de CP/M e ver o que acontece. Ao lado está o resultado, aquele "A>" lembra alguma coisa?

Exceto por um monte de maus contatos (principalmente no teclado), está tudo funcionando!

Obs.: Para o caso de alguém estar prestando a atenção, a tela está com 40 colunas, devido a um mau-contato na placa "80 colunas". Neste momento a placa Z80 estava no slot 3 (esquecimento meu). Quando a placa "80 colunas" passou a funcionar a Z80 parou. Perdi pelo menos uma hora, até lembrar que a placa Z80 devia ir no slot 4 para não conflitar com a "80 colunas".

Recuperando os Dados

Ok, eu consigo ler os disquetes antigos, e agora? É hora de transferir os dados pela serial. A placa ao lado é uma ICA (Interface de Comunicação Assíncrona), lembrança dos tempos da Humana Informática e dos posts nas BBSs, comunicando a 300 bps ou nos esquisitos 1200/75 bps.

Com a placa no slot 2, é hora de usar o meu programa de comunicação (reparar no copyright na tela ao lado). O programa trabalha no capenga Xmodem Checksum, o que exige um pouco de esforço do Hyperterminal (que insiste em tentar primeiro o Xmodem CRC e só passa para o Checksum depois de um l_o_n_g_o tempo). Após alguns arquivos a paciência acabou e preferí alterar um dos meus inúmeros utilitários de PC para suportar o Xmodem Checksum.

Mas, Espere: Isto Não É Tudo!

Ao final tenho 20 arquivo recebidos no PC (como no CP/M são apenas 56K de Ram, o texto era quebrada em pedaços de no máximo 20K para evitar que o editor ficasse acessando o disco o tempo todo). A tela ao lado mostra (em hexa) o início de um deles (clique para ampliar). Que codificação é essa? Os textos foram gerados com o WordStar, que era um editor WYSIWYG... se você está escrevendo em inglês numa impressora não gráfica. À medida que o texto é editado, o WordStar automaticamente distribui espaços para justificar o texto dentro das margens. Para isto ele usa o bit 7 dos caracteres para marcar o final das palavras e os espaços, hifens e quebras de linha introduzidos. O que realmente estraga tudo é que para gerar as acentuações eu digitava sequências "caracter backspace acento" (felizmente tanto o Unitron como o TK3000 tinham teclados programáveis, o que me permitia digitar estas sequências de uma forma mais automática).

Reparar também no ".he xxxx". A formatação para impressora era um passo separado, as linhas começando com '.' são comandos para definir cabeçalho, rodapé, pular página, etc. Para conseguir obter um TXT com o conteúdo foi preciso fazer um programa para limpar tudo isto.

Lembrando, o resultado final pode ser baixado daqui.

01/08/13: O texto, em formato de eBook pode ser baixado  do SkyDrive através do ícone no alto à direita ("Arquivos do Blog") ou pelos ícones abaixo:



PC Assember Volume I

Ao escrever o post sobre a minha nova impressora, me veio à lembrança o motivo para a compra da minha primeira impressora: eu estava escrevendo um livro.
Um Breve Histórico

Nos idos de 1985, eu era um alegre proprietário de um TK-82C. Em um encontro de usuários, conheci o Nelson Santos que trabalhava como editor na Editora Campus. A idéia inicial, o livro "Jogos em Linguagem de Máquina para a Linha Sinclair" não foi em frente e o Nelson perguntou se eu tinha alguma idéia para um outro livro. Mencionei que estava trabalhando com o PC IBM e que talvez existisse interesse em um livro sovre programação assembly para ele. Assim nasceu o livro PC Assembler, que deu origem a mais outros três livros ("Usando o BIOS", "Usando o DOS" e "Gráficos e Sons").

O Conteúdo

O livro descreve a programação em Assembly no 8086/8088 (naquilo que hoje em dia se chama de "real mode 16 bits"). A maior parte é uma descrição detalhada de cada uma das instruções disponíveis.

As Vendas

No total foram impressos 6253 livros e vendidos 6066 exemplares, em quatro edições. o gráfico abaixo mostra a evolução das vendas semetrais, do segundo semestre de 86 até o primeiro semestre de 93, quando a Editora Campus decidiu não mais reeditar a obra e me devolveu os direitos de publicação.


Para minha total surpresa, o livro foi até considerado um "best-seller":


O Texto

Existe uma longa história sobre a recuperação deste texto, o que será assunto do próximo post.

Estou disponibilizando o texto do livro aqui. Aviso que (por enquanto?) está em formato texto (TXT) pré formatado e falta a listagem do programa exemplo.

30/06/2010: Finalmente o texto completo e devidamente formatado está no blog: veja aqui.

quarta-feira, setembro 12, 2007

Lista: Onze Utilitários "Free"

Segue um levantamento (incompleto) dos utilitários "free" que utilizo no meu dia-a-dia (no Windows). Alguns são "free as in free beer" (grátis) e outros são "free as in free speach" (livres). Alguns são manjados outros talvez não tanto. É provável que existam alternativas melhores, vários deles foram adotados mais por acaso do que por uma comparação sistemática. O único critério relevante é que podem ser usados gratuitamente.
  • Mozilla Firefox: adotei quando a Microsoft tinha perdido o interesse no IE e os hackers do mal faziam a festa. Continua sendo meu navegador principal, embora ache que o IE7 tenha algumas vantagens (como na parte de impressão e uma nova aba sempre a um único click de distância). Nos add-ons uso o DownThemAll! (impressionante como o download default do Firefox e do IE são limitados) e o Html Validator (por enquanto mais como curiosidade, já que praticamente não desenvolvo para Web). Livre.
  • NSIS: fazer um instalador só perde para escrever o manual na lista de tarefas ingratas do desenvolvedor típico. O NSIS é um gerador de instaladores muito esperto. Na sua forma bruta é mais voltado para quem gosta de escrever scripts que para a turma do "arrasta e clica" (ou pior ainda, "next, next, finish"). Está na lista uma série de posts sobre ele. Livre.
  • Sonique: já não lembro mais porque comecei a usar este media player, mas ele está sempre lá na área de notificação (vulgo "system tray"). Eu cheguei até a fazer um plugin de visualização (inútil pois sempre deixo ele minimizado). De qualquer forma, um media player é uma ferramente indispensável para a maioria dos programadores, garantindo uma barreira sonora contra as interrupções externas. Grátis e abandonado.
  • ToDoList: o maior gerador de tráfego no feed do CodeProject, com versões novas a todo instante. Eu só criei coragem para testar após a propaganda do Caloni. Ainda estou me acostumando, minha tradição era fazer a lista em papel para ter o gostinho de riscar as tarefas concluídas. Livre.
  • WinMerge: outra ferramenta básica do desenvolvedor é um comparador de arquivos. Livre.
  • Frhed: todo programador baixo nível gosta de editar arquivos binário e este é um muito bom. Livre.
  • BareTail: uma das coisas mais úteis para depuração no *nix é p "tail -f". Para quem não conhece, o tail é um utilitário que mostra as últimas linhas de um arquivo. A opção -f faz com que sejam mostradas as últimas linhas à medida em que elas são acrescentadas no final. Perfeito para ver log de coisas ocorrendo em "tempo real". O BareTail é excelente, exceto pelo splash screen na versão grátis. Está na lista tentar fazer um utilitário destes. Grátis.
  • SciTE: a ferramenta mais básica de todas: um editor de programas. A internet está cheia de opções e este realmente foi escolhido ao acaso. E depois que você acostuma com um editor, resiste a mudar. Livre.
  • DOSBox: embora mais voltado para jogos antigos, uso também este emulador de DOS para rodar um compilador arcáico que se não gosta do XP. Livre.
  • Doxygen: o lugar da documentação do código fonte é no fonte! A partir de comentários formatados de forma não muito especial, o Doxygen gera a documentação em formato HTML, CHM e PDF. Livre.
  • PDF995: um driver de impressora que gera arquivos PDF. Os anúncios da versão grátis são chatos, mas acho a qualidade do PDF melhor que a gerada pelo OpenOffice (que não coloquei na lista pois uso raramente)
Sintam-se à vontade para explicar nos comentários como este programas são muito piores que outros que eu nem conheço!