Não acenda um pixel duas vezes! Use o buffer Z.

Eis uma técnica para plotar pixels numa tela, quando se têm pixels sobrepostos, de forma que um pixel será plotado apenas uma vez. Considere a figura abaixo:

Aqui temos dois retângulos, um avermelhado e um azul. O “plano de projeção” é a sua tela e esses retângulos têm, além de comprimento (width) e altura (height), também “profundidade” (depth). A profundidade é dada pela componente Z do plano onde o retângulo se encontra: Quanto mais perto da tela, maior o Z.

Repare que temos uma “matriz” que contém apenas os valores de Z dos pixels de cada retângulo. Essa matriz é chamada de “buffer Z” ou “buffer de profundidade” (depth buffer). E funciona assim: Antes de pensarmos em desenhar qualquer coisa no plano de projeção (tela), zeramos todo o buffer Z. Sabemos qual é a ordem em que os retângulos a serem desenhados se encontram no espaço (veremos como fazer isso em outro artigo) e, portanto, selecionamos o que está mais perto da tela (o vermelho)… A cada pixel plotado do retângulo vermelho, comparamos o seu valor Z eom o valor Z que consta no buffer Z. Se Z_{retangulo} > Z_{buffer}, para a posição (x,y) correspondente, plotamos o pixel e atualizamos a posição (x,y) no buffer Z… Se Z_{retangulo} <= Z_{buffer}, não plotamos e não atualizamos o buffer Z.

No fim das contas, os retângulos mais próximos da tela serão completamente plotados, mas os que estão mais atrás, terão apenas os pixels que não estejam à frente de outros retângulos plotados. Ou seja, o buffer Z funciona como uma máscara!

No caso da confecção de uma GUI onde lidamos apenas com figuras geométricas simples (retângulos) e que não tenham rotações em torno dos eixos X e Y, a técnica funciona perfeitamente bem.

Anúncios

Aventuras com hardware (PS/2 Mouse)

Well… Tem um xará meu (@frednora, no twitter) que está empenhado em criar um “toy OS” gráfico, com janelas, mouse e tudo mais. Recentemente ele se aventurou a lidar com o mouse, ao estilo PS/2 (hoje em dia é tudo USB, mas as VMs ainda suportam o estilo PS/2, com aqueles dois conectoreszinhos na parte de trás do PC – veja a foto ao lado). Como eu ainda não havia tido a oportunidade de futucar a programação e configuração desse dispositivo em particular, lá fui eu ajudar o meu quase homônimo amigo… Vale dizer que foi, também uma aventura!

Eu já havia escrito por aqui sobre o Keyboard Controller (aqui) e o troço não parecia ser muito problemático, já que ambos os dispositivos (teclado e mouse) são, essencialmente seriais e usam o mesmo controlador. O teclado é o dispositivo primário e o mouse, o auxiliar. No caso, as implementações de rotinas de teclado e mouse fazem uso de duas IRQs (IRQ 1 para o teclado e IRQ 12 para o mouse), tornando o processamento assíncrono. Como estamos interessados no mouse, apenas, é lógico que lidarei apenas com a IRQ 12 aqui… O que a IRQ 12 tem que fazer? Simples: Ler o dado vindo do mouse e disponibilizá-lo em algum lugar. Mas, qual é a “mensagem” vinda do mouse?

No caso do mouse PS/2 são, por padrão, 3 bytes. O primeiro contém os estados dos 3 botões (left, right e middle) e alguns bits adicionais (que falarei deles depois). O segundo byte contém o deslocamento horizontal do mouse e o terceiro, o deslocamento vertical. Esses deslocamentos são o que o nome sugere, um delta (δ) em “pixels” do quando o mouse foi arrastado para os lados ou para cima e para baixo. Obviamente que esses valores são sinalizados: Valores positivos de δx significam deslocamento do mouse para a direita e valores positivos de δy, significa deslocamento do mouse para cima, como um sistema de coordenadas cartesiano tradicional.

Para implementar as rotinas usei o Borland C++ 3.1 e os testes foram feitos no MS-DOS… Por que DOS? Ora, no modo protegido de alguns sistemas operacionais modernos, as portas de I/O não são diretamente acessíveis ao userspace. Preciso de um ambiente “livre” dessas restrições…

A rotina de serviço do mouse:

Ei-la:

#define CLAMP(x,_min,_max) \
{ \
  if ((x) < (_min)) (x) = (_min); else \
  if ((x) > (_max)) (x) = (_max); \
}

#define MAXX 79
#define MAXY 24

// Para teste coloquei (39,12) nas coordenadas do
// mouse para ficar no meio de uma tela de texto 80x25.
char buttons;
int mouse_x = 39;
int mouse_y = 12;
int mouse_ok = 0;
static int first_time = 1;

void interrupt irq12isr(void)
{
  static char buffer[3];
  static int pos = 0;

  if (first_time)
  {
    first_time = 0;
    inportb(0x60);
    goto exit_isr;
  }

  buffer[pos++] = inportb(0x60);
  if (pos == 3)
  {
    pos = 0;

    buttons = buffer[0] & 7;

    /* Divide por 2 para diminuir a sensibilidade
       do mouse. */
    mouse_x += buffer[1] / 2;
    mouse_y -= buffer[2] / 2;

    CLAMP(mouse_x, 0, MAXX);
    CLAMP(mouse_y, 0, MAXY);

    mouse_ok = 1;
  }

exit_isr:
  // envia EOI para os PICs
  outportb(0xa0, 0x20);
  outportb(0x20, 0x20);
}

Eis o primeiro macete aqui: Aquele if verificando o estado de first_time está ali porque, por algum motivo, o mouse PS/2 parece enviar os dados fora de ordem na primeira vez que é ativado ou ele envia, mas não gera as duas primeiras IRQs. Com esse macete garantimos que a sequência botões-dx-dy sempre será obedecida.

Note que cada byte enviado pelo mouse gera uma IRQ. Isso acontece no modo streaming e, aparentemente, é o mais fácil e assíncrono (que desejamos)… Assim, outro macete, é ajusta a variável mouse_ok para 1 indicando que temos, finalmente, os dados completos do último pacote de 3 bytes.

Espero que tenha notado que os dados são lidos pela porta de dados do KBDC, como se fosse um teclado. Mas, não temos que esperar que o bit OBF da porta de status (0x64) esteja setado porque a IRQ só acontece quando existe um dados a ser lido no buffer de saída do KBDC.

Os estados dos botões estão codificados nos bits 0, 1 e 2, para esquerda, direita e meio, respectivamente. Os outros bits desse byte não nos interessam (espere e verá porque!). Quanto aos deltas, são usados para serem acumulados às coordenadas atuais de (mouse\_x, mouse\_y). Só mudei o sentido de mouse\_y para coincidir com o quarto quadrante, de onde as coordenadas da tela existem. Segue daí aqueles macros CLAMP, que não deixarão as coordenadas do mouse escapar da tela.

Finalmente, enviamos EOI para ambos os controladores, já que IRQ 12 pertence ao PIC 2 e este é cascateado ao PIC 1.

A parte chata. Configurando o mouse:

A “parte chata” deveria ser a rotina de tratamento de interrupção, acima, mas o KBDC demonstrou-se ser quase um pesadelo quando se lida com dois dispositivos. Em primeiro lugar, para configurar o mouse é necessário desabilitar ambos os dispositivos (o primário e o auxiliar) para que não haja interferências do teclado no processo. E para que não exista interferências de IRQs que já possam estar implementadas, é conveniente mascarar a IRQ 1 e IRQ 12:

void mask_irqs(void)
{
  /* mascara irq 1, no PIC 1 */
  outportb(0x21, inportb(0x21) | (1 << 1));
  /* mascara irq 12, no PIC 2 */
  outportb(0xa1, inportb(0xa1) | (1 << 4));
}

void unmask_irqs(void)
{
  /* mascara irq 1, no PIC 1 */
  outportb(0x21, inportb(0x21) & ~(1 << 1));
  /* mascara irq 12, no PIC 2 */
  outportb(0xa1, inportb(0xa1) & ~(1 << 4));
}

Só para facilitar o código não estou guardando o estado da antiga máscara das IRQs (deveria ter feito isso, mas este código é apenas um teste)…

Para escrever comandos ler dados no KBDC é necessário verificar os bits IBF e OBF da porta de status (0x64), mas também é prudente verificar o bit 5 dessa porta, que chamarei de AOBF (Auxiliary Output Buffer Full), para ler dados vindos do dispositivo auxiliar (mouse). A rotina de espera por esses bits é esta:

/* buffer = 0 (output) ou 1 (input).
   auxiliary = 0 (primário), 1 (auxiliar). */
void kbdc_wait(int buffer, int auxiliary)
{
  int count = 0;

  while (--count)
    if (!buffer)
    {
      // Temos dados na saida?
      if (inportb(0x64) & (auxiliary ? 0x21 : 0x01))
        break;
    }
    else
      // A entrada ainda não está livre?
      if (!(inportb(0x64) & 0x02))
        break;
}

Usei aqui a codificação 0 para “Output” e 1 para “Input” porque o algarismo ‘0’ parece muito com a letra ‘O’, e o algarismo ‘1’ parece muito com a letra ‘I’. Fica mais fácil de lembrar… Já o auxiliary é um valor booleano (1 usa o bit AOBF e 0, não usa). Repare, também, que usei um esquema de timeout aqui, ou seja, a espera só vai acontecer durante, no máximo, 65536 leituras (no MS-DOS o tipo int tem 16 bits de tamanho).

Uma vez que temos nossa rotina de sincronização, podemos criar uma de escrita de dados para o mouse, que deve enviar o comando 0xD4 para o KBDC, seguido do comando para o mouse, na porta de dados do mesmo KBDC. Já a leitura dos dados vindos do mouse é feita da mesma forma que faríamos com um teclado, mas deve-se levar em conta o bit 5 do status do KBDC:

void mouse_write(unsigned char data)
{
  kbdc_wait(1, 0); outportb(0x64, 0xd4);
  kbdc_wait(1, 0); outportb(0x60, data);
}

unsigned char mouse_read(void)
{
  kbdc_wait(0, 1); return inportb(0x60);
}

Com isso, podemos agora ajustar o nosso mouse:

static void interrupt (far *oldisr)(void);

void mouse_init(void)
{
  unsigned char kbdc_cw;

  disable();
  mask_irqs();

  // salva e ajusta a nova isr.
  oldisr = getvect(0x74);
  setvect(0x74, irq12isr);

  // desabilita dispositivos primário e auxiliar.
  kbdc_wait(1, 0); outportb(0x64, 0xad);
  kbdc_wait(1, 0); outportb(0x64, 0xa7);

  // Liga a geração da IRQ12, na palavra de controle do KBDC.
  kbdc_wait(1, 0); outportb(0x64, 0x20);
  kbdc_wait(0, 0); kbdc_cw = inportb(0x60) | 2;
  kbdc_wait(1, 0); outportb(0x64, 0x60);
  kbdc_wait(1, 0); outportb(0x60, kbdc_cw);

  // Podemos habilitar o teclado de volta...
  kbdc_wait(1, 0); outportb(0x64, 0xae);

  // Habilita o dispositivo auxiliar (mouse).
  kbdc_wait(1, 0); ourtporb(0x64, 0xa8);

  // Agora podemos configurar o mouse.
  mouse_write(0xff);    // reseta o mouse e
                        // espera pelo valor 0xaa como resposta.
  while (mouse_read() != 0xaa);

  mouse_write(0xf6);    // coloca o mouse num modo default.
  while (mouse_read() != 0xfa); // espera pelo ACK.

  mouse_write(0xf4);   // habiilta o modo streaming.
  while (mouse_read() != 0xfa); // espera pelo ACK.

  // ISSO É ESTRANHO! Mas necessário (thanks ao amigo
  // Nelson Cole por ter me apontado isso!).
  kbdc_wait(1, 0);    // Espera que o mouse tenha lido tudo...

  unmask_irqs();
  enable();
}

Neste ponto, depois da execução de mouse_init() o mouse está configurado e sempre que for movido ou um botão pressionado, a rotina irq12isr será chamada.

A rotina de “de-inicialização” do mouse é mais simples, mas similar: Mascara-se a IRQ12 (apenas ela), desabilita-se o modo streaming enviando o comando 0xf5 para o mouse (via mouse_write, esperando pelo ACK; desabilita-se o auxiliary device enviando um comando 0xa7 para o KBDC; desabilita-se a IRQ 12 na palavra de controle do KBDC e, finalmente, voltamos o vetor 0x74 ao seu ponteiro original:

void mouse_uninit(void)
{
  unsigned char kbdc_cw;

  disable();

  // Mascara a IRQ12 no PIC
  outportb ( 0xa1, inportb ( 0xa1 ) | ( 1 << 4 ) );

  // Desabilita o mouse
  mouse_write ( 0xf5 );
  while ( mouse_read() != 0xfa ); // Ack

  // Desabilita o auxiliary device.
  kbdc_wait ( 1, 0 ); outportb ( 0x64, 0xa7 );

  // Desabilita IRQ 12 no KBDC.
  // ATENÇÃO: Importante fazer isso com as IRQs mascaradas
  // e os dispositivos desabilitados!
  kbdc_wait ( 1, 0 ); outportb ( 0x64, 0x20 );
  kbdc_wait ( 0, 0 ); kbdc_cw = ( inportb ( 0x60 ) & ~2 );
  kbdc_wait ( 1, 0 ); outportb ( 0x64, 0x60 );
  kbdc_wait ( 1, 0 ); outportb ( 0x60, kbdc_cw );

  // Retorna com a velha ISR para a IRQ 12.
  setvect ( 0x74, oldvect );

  enable();
}

Usando as rotinas:

Neste pequeno teste vou apenas mudar o atributo de um caracter na tela, de acordo com a posição do mouse. Para isso, uso a seguinte rotina:

void cursor(int x, int y, int draw)
{
  char far *ptr = MK_FP(0xb800, 160*y+2*x+1);
  *p = draw ? 0xf0 : 7;
}

E assim, nossa rotina main() fica assim:

void main(void)
{
  int oldx = mouse_x;
  int oldy = mouse_y;

  clrscr();
  cputs("Aperte qq tecla para parar...");

  mouse_init();

  cursor(oldx, oldy, 1);  // acende.
  while (!kbhit())
    if (mouse_ok)
    {
      cursor(oldx, oldy, 0);  // apaga
      cursor(oldx = mouse_x, oldy = mouse_y, 1); // acende.
      mouse_ok = 0;
    }

  mouse_uninit();
}

O motivo de eu estar ignorando os bits superiores do primeiro byte enviado pelo mouse:

A resolução de seu mouse é medida em milímetros por segundo. Por default, o mouse é capaz de enviar 100 amostras por segundo à IRQ e o valor de δx e δy são medidos em milímetros. Acontece que esses valores têm 9 bits, não apenas 8. O nono bit de cada um dos outros dois bytes estão nos bits superiores do primeiro… Mas, considere que, com 9 bits podemos ter valores sinalizados entre -256 e +255, com uma difereça de 10 milissegundos entre cada deslocamento, teríamos uma velocidade máxima de 25,6 m/s (256 milímetros / 0.01 segundos), ou cerca de 92,2 km/h, se você preferir…

Para acelerar um mouse a 92,2 km/h é necessário chutá-lo com força, em cima da mesa e, não sei se reparou, tivemos que escalonar os deltas para “diminuir a sensibilidade”, ou seja, dos 8 bits, estamos usando apenas 7 (já que ignoro os 9ºs bits)… Esse nono bit é supérfluo!

Se você realmente precisar do 9º bit porque gosta de jogar seu mouse de maneira violenta pra lá e pra cá, será necessário isolar os bits no primeiro byte, aumentar o tamanho do tipo de mouse_x e mouse_y para int e usar variáveis temporárias do mesmo tamanho (delta_x e delta_y) para fazer algo assim:

  int delta_x, delta_y;

  delta_x = (unsigned int)button[1];
  if (button[0] & (1 << 3))
    delta_x |= 0xff00;
  mouse_x += delta_x;

  delta_y = (unsigned int)button[2];
  if (button[0] & (1 << 4))
    delta_y |= 0xff00;
  mouse_y -= delta_y;

  button = button[0] & 7;

Não creio que valha o esforço!

Dificuldades enfrentadas:

Foram algumas… Fiquei dois dias para colocar isso pra funcionar direito porque:

  1. Eu não fazia ideia de que tivesse que sincronizar o input buffer antes de começar a processar os pacotes recebidos pela IRQ… Já agradeci antes e agradeço, de novo, ao Nelson Cole por ter apontado isso;
  2. A sequência de inicialização, a dos comandos enviados ao mouse, deve ser precisamente a que foi codificada: RESET/DEFAULTS/STREAMING. Senão o bicho não funciona! (De novo, thanks Nelson!);
  3. Eu também não fazia ideia de que tinha que obter sinais de ACK vindos do mouse… De fato, a rotina acima está incompleta, por que o mouse pode devolver sinais de NACK (No Acknowledgement) ou ERROR, que não são tratados na rotina.

Além disso, “comi mosca”, como dizia um velho professor meu, no envio de EOIs para o PIC secundário, esquecendo completamente que ele é cascateado com o PIC primário (agradecimentos ao Axey e ao Nelson por me apontarem isso).

Outros detalhes menores surgiram durante o teste: Já que a leitura, fora da IRQ 12, pode vir do dispositivo auxiliar ou do primário, como diferenciá-los? Dando uma olhada na documentação do KBDC 8042 percebi o bit 5 do status do controlador. Isso foi usado na rotina mouse_read(), como pode ser visto acima…

E, para finalizar as dificuldades, devo dizer que muito desse código não é meu. Aproveitei coisas que obtive do disassembling de drivers de mouse, para MS-DOS, que implementam a interface via INT 0x33. E aqui vale citar um detalhe sobre o modo streaming: Toda a ideia de usar uma IRQ é tornar o processo de obtenção de pacotes vindos do mouse assíncrono. É perfeitamente possível não habilitar o streaming e ler 3 bytes diretamente na IRQ, mas, para isso, eu teria que fazer uso da rotina kbdc_wait para sincronizar o output buffer, tornando o interior da IRQ síncrona… Já que a IRQ tem que processar os dados da forma mais rápida possível, não fiz isso. Então, preferi manter aquele valor booleano em mouse_ok para saber se um pacote inteiro foi decodificado ou não… Isso não apresenta grandes problemas, já que a leitura e a escrita nessa variável é atômica, ou seja, não há perigo de causar um deadlock, desse jeito.

O que falta entender?

Bem… o macete de ignorar o primeiro byte recebido pela IRQ não é uma invenção minha… Vi num driver. Por que o mouse se comporta assim é uma icógnita para mim, ainda agora… E o outro detalhe é aquela necessidade de sincronizar o input buffer antes de começar a processar os pacotes.

Voilà! O resultado é

Este aqui, ó, comigo mexendo o mouse pra lá e pra cá…:

O código completo, para ser compilado em MS-DOS e com o Borland C++ 3.1 pode ser baixado aqui.

Aritmética inteira (se é que já não falei disso por aqui!)

Vejo algumas dúvidas de uma galerinha em relação à tipagem de valores inteiros, tanto em Assembly, quando em C. Vejamos se eu consigo resolvê-las, definitivamente, nesse artigo…

Eu já falei disso em meu livro, mas ai vai outra vez: “Não existem valores negativos!”. Sério! Seu processador não sabe a diferença entre um valor negativo ou positivo. Para ele, tudo é positivo! “Mas… mas…”, gagueja o leitor ao ver tamanho disparate! Sim, meu querido, é verdade. Números negativos são uma fantasia que colocaram na sua cabeça! Tomemos a nossa boa e velha base decimal, o que faz um número ser “negativo” é aquele famigerado sinal de “menos” na frente dele. Uma coisinha à toa, um tracinho.

Os números “naturais” (domínio ℕ) levam esse nome porque são usados para contar coisas e não existem, por exemplo, “menos duas coisas”. Esse “menos” ai é uma convenção que se usa para dizer que “faltam” ou então que uma grandeza está no sentido contrário do convencional… O número -10 é o “10” com um tracinho na frente que diz “falta 10” ou “passou de 10 unidades, além do zero, no sentido regressivo”… nada mais que isso. Note que esse ‘-‘ não é um número e, por isso, não dá para representá-lo de maneira binária, no interior de um computador. Não de forma direta!

No caso do seu processador, alguém percebeu que pode usar o último bit (o bit mais à esquerda, chamado de MSB – Most Significant Bit [ou Byte, dependendo do contexto]) para representar um valor negativo ao invés de usar um símbolo ‘-‘. Por exemplo, se você subtrair 1 (note, 1 positivo!) de zero obterá, em 8 bits, 0b11111111. Percebeu que esse 1, em vermelho, pode ser usado para dizer: “Ei… esse número pode ser interpretado como sendo negativo!”? Acontece que o valor obtido da subtração de uma unidade à partir do zero continua sendo inteira, são 8 bits setados que nos dão o valor equivalente, em decimal, de 255. Ahhh… e o motivo de todos os bits ficarem setados pode ser compreendido com base num odômetro (aquele medidor de quilometragem de carros antigos)… se ele estiver em 00000 e você girar a roda a ré, ele passará para 999999, não é?

Se o MSB pode ser usado para representarmos um valor negativo, como isso pode ser feito? A ideia inicial era, simplesmente, inverter todos os bits à partir de um valor positivo (que tivesse o MSB zerado). Por exemplo, para continuar com nossos exemplos em 8 bits, o valor +10, em binário, seria 0b00001010, e sua “negação”, de acordo com a ideia acima, seria 0b11110101 ou 0xf5. Parece lógico, mas olhe o que acontece se retirarmos 1 de 0 10 vezes para obtermos -10: 0-1=0b11111111; … repete o decremento 8 vezes …; 0b11110111-1=0b11110110. Ou seja, 0xf6 é que é -10. Isso indica que a ideia, embora tenha sido boa, está errada. Especialmente porque, nesse esquema, teremos dois zeros… Um deles será positivo 0b00000000 (+0) e o outro, negativo (-0) 0b11111111, já que, pela definição, quando o MSB estiver setado teríamos que inverter o valor para obter o valor absoluto que está sendo negativado!… Tem que ter outro jeito!

No caso da base decimal, +10 e -10 são valores complementares, de forma que, quando você os soma o resultado, necessariamente, será ZERO. Há uma sensação de “inversão” quando se coloca o sinal de ‘-‘ na frente do valor, mas também já essa sensação “complementar”. Se usarmos o último bit como bit “complementar” (de novo usarei exemplos em 8 bits), resolvemos o problema com a seguinte equação:

\displaystyle v=-{b_7}\cdot2^7+\sum_{i=0}^6{b_i}\cdot2^i

Onde b_n é 0 ou 1, de acordo com o bit n.

Considere o caso onde todos os 8 bits estejam setados. O resultado da equação acima será -2^7+127=-128+127=-1. Isso quer dizer que os 7 primeiros bits correspondem a um valor positivo e o último bit realiza um “complemento”, se estiver setado. Mas, de novo… o valor 0b11111111 não é negativo, ele é 255. Só que pode ser interpretado como um valor negativo (-1).

Essa técnica é chamada de “complemento 2”. Por quê? Considere o caso com apenas 2 bits: 0b00 e 0b01 são os únicos valores de representação positiva neste esquema. Quando o bit 1 estiver setado ele é o complemento “2” (corresponde ao valor -2), que será somado ao bit 0: 0b10 = -2+0 e 0b11 = -2+1. No caso de mais bits o correto seria dizer “complemento de base 2″… Em contraste ao “complemento 2”, o método da inversão binária pura é conhecido como “complemento 1”.

Com valores com mais bits além dos 8 que citei como exemplo na equação acima, devemos fazer a mesma mágica considerando o bit mais alto (MSB):

\displaystyle v=-{b_{n-1}}\cdot2^{n-1}+\sum_{i=0}^{n-2}{b_i}\cdot2^i

Onde n é o número de bits com os quais estamos lidando. Por exemplo, para 32 bits a equação muda para:

\displaystyle v=-{b_{31}}\cdot2^{31}+\sum_{i=0}^{30}{b_i}\cdot2^i

O macete de inverter e somar 1:

Não é óbvio, mas se você tem um valor positivo (MSB=0), basta inverter todos os bits do valor (incluindo o MSB) e somar 1 para obter uma representação negativa em complemento 2. E se tiver uma representação negativa, inverter tudo e somar um vai te dar o valor positivo (MSB=0).

Isso é um macete (é claro que tem base matemática), mas incorre num problema… De volta aos nossos 8 bits de exemplo, 0b10000000 tem o bit 7 setado… se invertermos e somarmos um obteremos: 0b10000000 outra vez, ou seja, nada muda… Isso quer dizer que a representação de -128 é a mesma coisa que +128? Claro que não! Este é um caso especial do “macete”, onde o MSB é 1 e, portanto, a representação é a de um valor negativo e o valor absoluto é 128, ou seja -128.

De novo, e não me cansarei de repetir: o valor binário é positivo, sempre! Sua interpretação é que pode levar em conta o sinal…

Qual é a diferença entre int e unsigned int, em C?

Ambos os tipos suportam valores inteiros de 32 bits (16, se você ainda lida com o velho MS-DOS). Esses valores variam entre 0 e 2^{32}-1 positivos, como qualquer valor binário é… mas, o tipo int é dito sinalizado porque, em certas operações, a representação complementar é respeitada. Por exemplo, quando há uma promoção de tipos com menos bits para outra com mais bits, se esses tipos forem “sinalizados” o compilador vai gerar código que “replica” o bit mais alto para os demais… Por exemplo:

int x;
char c = -1;

x = c;

Isso ai vai gear algo assim, num i386 ou superior:

; Suponha que x esteja alocado em EAX e
; c esteja alocado em BL.
  mov bl,0xff       ; Representação de -1 (8 bits) em BL.
  movsx eax,bl      ; Estende o bit 7 de BL para os bits
                    ; de 7 até 31 de EAX.

Se MOVSX não fosse usada aqui, EAX poderia acabar com 0xff que é, mesmo com tipos sinalizados, em 32 bits, um valor positivo… Tomemos -4 em 8 bits: 0xfc… O mesmo valor em 32 bits é 0xfffffffc, ou seja, basta estender o MSB dos 8 bits para todos os bits, de 7 até 31, de EAX

Faça ‘x’ ser um unsigned int e veja a instrução MOVSX mudar para MOVZX (estende com zeros!).

Já reparou que você normalmente usa o tipo char para acomodar strings? Ora, os bytes de uma string tipicamente não têm sinal! Isso é mais uma demonstração que a sinalização é uma convenção, uma representação! O valor de cada byte continua tendo 8 bits, no caso de char e terá 16 no caso de short ints e 32 no caso de ints.

Os tipos sinalizados também são, obviamente, úteis em comparações. Em assembly, nos flags, temos os bits ZF, CF, SF e OF. O bit ZF de EFLAGS indica se a última instrução lógica ou aritmética resultou em zero. CF diz se houve um “vai um” numa operação de adição ou “rotação” de bits (ou um “empréstimo”, numa subtração), mas e os flags SF e OF?

SF é uma cópia do MSB da última operação (de novo, lógica ou aritmética!). Esse flag só nos diz: “Olha, se você está fazendo de conta que os valores têm sinais, o resultado deu ‘negativo’, viu?!”. E o flag OF nos diz se o resultado ultrapassou (ou “transbordou”, overflow, em inglês) a faixa dos valores “sinalizados” (com 1 byte, por exemplo, podemos representar valores entre -128 e +127… Assim +127+1 será -128 e OF=1, assim como -128-1 será +127 e OF=1)… Então, se você quer comparar se um valor é “menor que zero”, pode muito bem usar o flag SF como critério, mas se quer comparar dois valores quaisquer e quer saber se um é MENOR que o outro e os encara como “sinalizados”, então tem que usar uma combinação do SF com o OF. Se (x < y) for verdadeiro, e ‘x’ e ‘y’ têm “sinal”, então a subtração de x por y (x-y) será negativa, resultando em SF=1 e sem overflow (OF=0) ou se houver overflow, necessariamente SF=0 (deixo isso como exercício para o leitor descobrir porquẽ!)…

Assim, se SFOF, significa que (x < y). E é isso o que a instrução JL (Jump if Less) testa. O contrário, SF==OF, signfica “maior ou igual a”, ou JGE (Jump if Greater or Equal), para testar se é apenas “maior que” temos que levar em conta se ZF=0 e, usar esses três critérios é o que a instrução JG (Jump if Greater than) faz. Ahhh… e a instrução que salta, considerando apenas se SF=1 é JS (Jump if Signaled).

É claro, existem as negações desses critérios, tal que: JL é a mesma coisa que JNGE, JGE é a mesma coisa que JNL, e por ai vai. Na realidade esses pares de instruções representam as mesmas, entre elas, apenas seus mnemônicos mudam.

Mas, se você não estiver trabalhando com a representação negativa, pode usar apenas o CF e o ZF. Se (x < y), tendo ‘x’ e ‘y’ sem sinais, então CF=1, já que x-y extrapolará a faixa dos positivos. Para isso pode usar a instrução JC ou JB (“Jump if Carry” e “Jump if Below“), ambas só testam o flag de carry. JBE testará também se ZF=1 (Jump if Below or equal) e JA (Jump if Above) vai testar se ZF=0 e CF=0.

Tudo isso pra te dizer que o único lugar onde o processador faz alguma ideia do que seja um valor negativo é nos flags… As operações aritméticas elementares de soma e subtração funcionam muito bem com valores não sinalizados ou sinalizados em complemento 2. Multiplicações e divisões têm suas instruções especializadas para suportar sinalização ou não (IMUL e MUL, IDIV e DIV – o “I” é de “Integer”, mas deveria ser “S” de “Signaled”).

Reforçando o uso dos saltos condicionais:

É comum e isso costuma criar códigos mais performáticos, em C, que comparações sejam feitas contra o valor 0 (zero) ao invés de um valor específico, como em:

if (x < 0) ...

Isso é interessante porque, neste caso, basta que o compilador verifique apenas o flag SF depois da comparação, que pode ser aritmética (instrução CMP) ou lógica (TEST). Lembre-se que SF é somente a cópia do MSB do resultado depois da operação… Já a comparação contra valores diferentes de zero são feitas, necessariamente, de forma aritmética:

if (x < -2) ...
//   cmp eax,-2   ; CMP faz uma subtração!
//   jnl .skip
//   ...
// .skip:

Claro, assumindo que ‘x’ seja ‘int’… Se ‘x’ for ‘unsigned int’, a instrução JNB é usada, ao invés de JNL e esse -2 será, na verdade, positivo, ou seja, 0xfffffffe. O compilador provavelmente emitirá um aviso, mas fará o que você mandou. Note que a semântica será completamente diferente daquilo que você, normalmente, espera: Apenas os valores 0xfffffffe e 0xffffffff, em ‘x’, são superiores ou iguais a ‘-2’, neste caso.

Chamei sua atenção para o primeiro caso, onde a comparação é feita com zero, para testes aritméticos ou lógicos porque instruções como TEST, AND, OR, XOR ou NOT afetam os flags ZF e SF, mas sempre zeram OF e CF, enquanto todos os flags são afetados em operações aritméticas (ADD, ADC, SUB e SBB)… Atenção especial deve ser dada aos “atalhos” DEC e INC, que funcionam como operações aritméticas, exceto que elas não afetam CF (de fato, elas gastam 1 ciclo de clock extra só para preservar esse flag!).

A comparação contra zero é tão mais simples que muitas das rotinas da biblioteca padrão usam o valor 0 como condição de sucesso ou erro, no retorno de uma função… A função fopen, por exemplo, retorna um ponteiro para uma estrutura opaca do tipo FILE. Se esse ponteiro for NULL (em outras palavras, zero), temos um erro na abertura do “arquivo”. Outras instruções retornam 0 para indicar sucesso e valores quaisquer para condições de erro. Isso é comum até mesmo em ambientes como shell, onde o retorno de uma aplicação devolve o valor 0, indicando sucesso ou outro valor, indicando erros. Agora você sabe o motivo: Comparar com zero é tão fácil quanto executar uma instrução lógica (TEST, por exemplo) e verificar o conteúdo do flag ZF.

Esse é outro motivo pelo qual você poderá ver códigos como:

if ((skt = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP)) < 0)
{ ... trata erro aqui ... }

O correto aqui seria testar contra a igualdade com -1, mas como o file descriptor provavelmente não será um valor negativo, essa comparação será mais rápida, já que, pelo padrão POSIX, a função socket retorna -1, em caso de erro… Deixo apenas o aviso de que esse macete pode ser problemático, se o sistema operacional devolver um file descritor com valor inteiro positivo maior que 0x7fffffff. Como vimos, acima, valores acima desses são interpretados como negativos (MSB estará setado) e o if, acima, interpretará isso como um erro (quando teríamos um descritor válido!).

Essencialmente essa é a diferença entre os tipos sinalizados e não sinalizados: Em promoções de tipos como o bit de sinal será replicado e na decisão que o compilador tem que tomar no uso de saltos condicionais. Com relação ao dado que eles contém, são valores binários que podem ser interpretados como tendo sinal, mas na verdade, são apenas valores binários…

Começando pelo básico: Sistemas de coordenadas gráficas

Você já deve ter passado pelo problema da figura abaixo… Quer desenhar um quadradinho de 9 pixeis especificando as coordenadas dos cantos superior esquerdo e inferior direito, mas precisa subtrair uma unidade do canto inferior direito porque senão acaba com um pixel extra (um quadrado de 16 pixeis).

Ao invés de pixels, use as bordas!

A solução é essa ai em cima… Ao invés de usar a posição do pixel como referência, use a borda, como numa folha de papel milimetrado, onde os quadradinhos são os pixeis, mas as linhas é que especificam um ponto. Neste caso, o calculo de tamanho nos sentidos X e Y do seu retângulo fica bem mais fácil sem aquele “+1” que precisava fazer.

Isso tem outra vantagem prática… Ao usar a borda como coordenada, o que você faz, num sistema que use o 4º quadrante (como a tela de seu computador – a origem (0,0) está no canto superior esquerdo!) é não plotar os pixeis do lado direito e do de baixo. Tomemos apenas o sentido X, para plotar os 3 pixeis horizontais você faz:

for (x = 0; x < 3; x++) ...

Note o sinal de “menor que”, ele excluí o último pixel, não é?

Não fica muito claro neste texto, mas esse artifício facilita um bocado quando você tem que fazer com que polígonos “coincidam” sem ter que plotar o mesmo pixel duas vezes. Por exemplo… se eu pegar o quadradinho de 9 pixeis acima e desenhá-lo na posição (0,0) e, logo depois, desejar outro quadradinho na posição (3,0), é garantido que os dois se “tocam”, mas nenhum pixel é plotado mais que uma vez (não há sobreposição):

Grandes coisas! Mas isso é bem evidente, e útil, quando estamos lidando com triângulos (em computação gráfica lidamos muito com triângulos!).

 

Listas circulares, do jeito Knuth (e do Linux)…

Já falei sobre listas encadeadas ao estilo Sedgewick aqui, mas eis uma maneira de implementar listas que fica ainda mais simples… O header abaixo mostra a implementação atual do MyToyOS, devidamente copiado do estilo Knuth e Linus de listas circulares:

#ifndef __LIST_INCLUDED__
#define __LIST_INCLUDED__

// Essa é a estrutura de um nó de uma lista, 
// mas também do nó "batente" ou "cabeça" da
// lista. E, uma vez que mantemos o nó "cabeça",
// a lista é "circular", para facilitar a 
// manipulação (sempre haverá um nó cabeça!).
// A lista "vazia" tem apenas a cabeça, apontando
// para si própria.
//
// Note que a lista é double linked e circular.
//
// COMO USAR:
//
// Suponha que você queira manter uma "lista de
// retângulos", onde um retângulo tenha a estrutura:
//
//   struct rect {
//     int left, top, right, bottom;
//   };
//
// A lista pode ser definida como:
//
//  struct _list_head rect_list_head;
//  INIT_LIST_HEAD(&rect_list_head);
//
// É claro, podemos inicializar a lista diretamente:
//
//  struct _list_head rect_list_head = 
//             EMPTY_LIST(rect_list_head);
//
// A última forma é útil para inicialização de listas
// locais estáticas e globais.
//
// No exemplo dos retângulos, os nós da lista, DEVEM
// ser definidos como:
//
//   struct rect_node {
//     struct _list_head next_rect;  // Isso tem que estar
//                                   // no início!
//     struct rect rc;
//   };
//
// Para adicionar um retângulo no fim da lista:
//
//   _list_add_tail(&rect_list_head, 
//                  (struct _list_head *)&rc_node);
//
// Para adicionar um retângulo no início da lista:
//
//   _list_add_after(&rect_list_head, 
//                   (struct _list_head *)&rc_node);
//
// Para retirar um retângulo da lista:
//
//   _list_unlink((struct _list_head *)&rc_node);
//
// Para percorrer a lista, do início ao fim:
//
//   struct _list_head *p;
//   _list_foreach(p, &rect_list_head)
//   {
//     // faz algo com o ponteiro p aqui.
//   }
//
// Para percorrer a lista do fim para o início:
//
//   struct _list_head *p;
//   _list_foreach_reverse(p, &rc_list_head)
//   {
//     // faz algo com o ponteiro p aqui.
//   }
//
// Infelizmente AINDA não criei a rotina para 
// percorrer toda a lista à partir de um nó 
// específico. Mas, você pode fazer isso guardando
// o nó en questão, percorrendo a lista em uma
// direção até o nó head (_list_foreach*) e 
// depois percorrer do head para o nó guardado. 
// Por exemplo, para frente:
//
//  struct _list_head *p = (struct _list_head *)&rc_node;
//  struct _list_head *q = p->prev;
//  struct _list_head *r = p;
//  _list_foreach(r, q)
//  { ... }
//  _list_forearch(r, &rc_list_head)
//  {
//    if (r == q) break;
//  }
//
// Repare também que, embora tenhamos um "batente", o 
// macro aceita qualquer nó da lista como "alvo". Mas 
// é necessário cuidado porque o "batente" real não tem
// dados.
//

// Estrutura da "cabeça" da lista.
struct _list_head { 
  struct _list_head *next;
  struct _list_head *prev; // Funciona como 'tail' para a 
                           // cabeça da lista.
};

// Os macros citados acima...
#define INIT_LIST_HEAD(name) \
  { (name)->next = (name)->prev = (name); }
#define EMPTY_LIST(name) \
  { .next = .prev = &(name); }

// Essencialmente a mesma coisa que acima, mas lida com o
// ponteiro para a "cabeça" da lista.
static inline void _list_init(struct _list_head *head)
{
  head->next = head->prev = head;
}

// A lista está vazia? Se next aponta para a cabeça, está!
static inline _Bool _list_empty(struct _list_head *head)
{ return head == head->next; }

// Insere o novo item depois do item "prev".
static inline void _list_add_after(struct _list_head *prev, 
                                   struct _list_head *_new)
{
  struct _list_head *next;
  struct _list_head *prev;

  next = head->next;
  prev = head->prev;

  if (_list_empty(head)) // Caso especial!
    head->prev = _new;
  _new->next = next;
  _new->prev = prev;
  head->next = _new;
}

// Addiciona um item no fim da lista.
static inline void _list_add_tail(struct _list_head *head, 
                                  struct _list_head *_new)
{
  _list_add_after(head->prev, _new);
}

// Apaga um nó da lista.
// OBS: Cuidado ao usar free(). o nó pode ser a cabeça!
static inline void _list_unlink(struct _list_head *node)
{
  // Note que se a lista estiver vazia, nada acontece.
  struct _list_head *next;
  struct _list_head *prev;

  next = node->next;
  prev = node->prev;
  prev->next = node->next;
  next->prev = node->prev;
}

// Percorrer uma lista pode ser feito com:
//
// struct _list_head *p = &mylist;
//
// for (p = mylist->next; p != &mylist; p = p->next)
// { ... }
//
// Dai o macro abaixo (tanto p quanto head são ponteiros:
//
// OBS: É bom lembrar que a cada iteração do loop o 
//      ponteiro de controle apontará para o próximo
//      item da lista (ou para o anterior se o sentido
//      for reverso) até que ele retorne para a "cabeça".
//      Assim, usá-lo para deletar itens na lista deve
//      ser feito com cuidado.
#define _list_foreach(p,head) \
  for (p=head->next; p != head; p=p->next)

#define _list_foreach_reverse(p,head) \
  for (p=head->prev; p != head; p=p->prev)

#endif

Por que as funções estão definidas no header e não num módulo C separado? Ora, as rotinas são tão simples que posso fazê-las inline. Rotinas em módulos separados, necessariamente, não são “inlineáveis”. Os macros _list_foreach e _list_foreach_reverse não podem ser funções porque são atalhos para a construção do loop que percorrerá toda a lista… Aliás, um conselho: Cuidado com o código abaixo

struct _list_head *p;
_list_foreach(p, &list_of_rects)
{
  _list_unlink(p);
}

Dependendo do que você fizer com os ponteiros do nó apontado por p, o loop não fará o que você quer (mas, do jeito que está, deve funcionar, porque o componente next de p continua apontando para o próximo item, embora o nó não faça mais parte da lista… No fim das contas apenas o a cabeça da lista sobrará (não será “desligada” da lista)…

Note também que nenhuma das rotinas é responsável por alocar ou dealocar a estrutura de um nó. Tudo o que elas fazem são as ligações corretas para manter a lista. É sua responsabilidade alocar ou liberar nós, incluindo a “cabeça”, é sempre deixada na lista no caso do desligamento de todos os nós…

A característica circular da lista torna fácil algumas operações (principalmente _list_foreach e sua contraparte).

Um macete usando NULL pointers…

Você provavelmente aprendeu que ponteiros NULL são perigosos. Eles causam “segmentation faults” ou “General Protection Faults” e devem ser evitados. Eis o detalhe: Isso só acontece se o ponteiro for derreferenciado!

O macete abaixo mostra um jeito de obter o offset de um membro de uma estrutura sem usar o macro offsetof, definido em stddef.h, pelo menos desde a versão ISO 9989:1999 da linguagem C:

#define offsetof(T,member) \
  ( (unsigned int) &( (T *)0 )->member )

Notou o uso do NULL pointer? Pois é! Não estamos derreferenciando o bicho, só calculando o endereço efetivo do membro da estrutura… Se você fizer:

Yep! MS-DOS!

O membro z da estrutura S está no offset 8 (Faz sentido: x está no início da estrutura, portanto no offset 0. Como cada float ocupa 4 bytes, y estará no offset 4)… Fiz isso no MS-DOS, usando o Borland C++ 3.1 para mostrar para vocês que isso sempre foi válido, desde os primórdios.

O que essa macro faz, na verdade? Ora, o endereço efetivo é calculado com base no endereço do objeto, cujo endereço está no ponteiro… Ao usar o endereço 0 (zero), tudo o que temos é o offset do membro da estrutura!

 

De novo: Por que programar diretamente em assembly geralmente não é uma boa ideia…

Sim… de novo estou advogando contra mim mesmo. Eu uso assembly sempre que posso e quando isso não implica em códigos dependentes de arquitetura. Mas, para o novato, que está aprendendo assembly agora, programar nessa linguagem quase sempre é sinônimo de desastre. Eis o porquê:

Convenções de chamadas existem por um bom motivo

Quando estamos aprendendo é sugerido que manter o contexto da função chamadora é importante. Por contexto quero dizer os registradores que estavam sendo usados pela função que chamou a sua… Isso parece razoável, mas não é assim que compiladores de nível mais alto fazem… Um exemplo simples é a implementação padrão da função strcpy, em C:

char *strcpy(char *d, char *s)
{
  char *p = d;
  while (*p++ = *s++);
  return d;
}

Note que a função não verifica o conteúdo dos ponteiros (eles PODEM ser NULL e causarem segmentation fault) e o código gerado também não se preocupa em preservar o conteúdo dos registradores. No x86-64 isso é mais evidente:

strcpy:
  mov   rax,rdi
  mov   rdx,rdi
.loop:
  add   rsi,1
  movzx ecx,byte [rsi-1]
  add   rdx,1
  test  cl,cl
  mov   [rdx-1],cl
  jne   .loop
  ret

Aqui a função alterou, sem escrúpulos, o conteúdo de RAX, RCX, RDX, RSI e RDI. Isso acontece porque, no modo x86-64, o GCC só se preocupa em manter os registradores RBX, RBP, RSP e de R12 até R15. Já no modo i386, os mantidos devem ser EBX, EBP e ESP apenas. Todos os demais podem ser modificados.

Há uma vantagem escondida nessa aproximação: Se você sabe que o compilador C vai manter, à todo custo, esses registradores inalterados entre chamadas, tanto ele quanto você pode usá-los como “variáveis temporárias” (desde que preserve os seus conteúdos vindos da função chamadora!)… Quanto aos demais, se sua função chama outra e você precisa preservar o conteúdo de EAX, por exemplo, então é obrigá-lo a salvá-lo você mesmo (na pilha, por exemplo!).

Ahhh, sim… nas convenções de chamada usadas por C, pelo menos no modo i386, EAX é usado para retornar um valor e o par EDX:EAX, se esse valor for maior que 32 bits. Se sua função não retorna valores, pode mexer com EAX e EDX à vontade e deixá-los “bagunçados”. Eles não precisam ser preservados, neste caso.

Usando a pilha para manter variáveis locais entre chamadas

O GCC tenta manter todas as variáveis locais em registradores, mas, eventualmente, precisa guardá-los para uso futuro (depois do retorno da chamada de alguma função). Geralmente ele faz algo assim:

f:
  sub esp,4
  ...
  mov [esp],eax
  call some_function
  mov eax,[esp]
  ...
  add esp,4
  ret

ESP, quando sua função é chamada, aponta para o endereço de retorno da função chamadora. Como a pilha cresce para baixo, nossa função resolveu alocar 4 bytes (no modo i386 a pilha deve estar sempre alinhada por DWORD) adicionando 4 ao ESP. Antes de retornar (RET) o conteúdo de ESP deve voltar ao valor original que estava (lembra-se que ele é um dos que têm que ser preservados?).

É claro que você poderia guardar o conteúdo dessa variável “local” dentro de algum endereço no segmento de dados ou, até mesmo, no segmento de código, mas ai ela deixaria de ser “local”, não é?

Por que não usar PUSH e POP?

Depois que você aprende o conceito de pilha, parece muito mais simples usar as instruções PUSH e POP do que usar o esquema que mostrei acima. O mesmo fragmento de código em poderia fazer, retirando aqueles SUB e ADD e codificando como:

f:
  ...
  push eax
  call some_function
  pop  eax
  ...
  ret

A função fica menor? Fica! Parece mais simples? Parece! Mas ela tem um problema… As instruções PUSH e POP são ligeiramente mais lentas que MOV porque cada PUSH e cada POP, além de lerem/gravarem na pilha os valores dos registradores têm que adicionar 4 ou retirar 4 de ESP. O código acima, sem usar PUSH e POP, é equivalente a:

f:
  ...
  sub  esp,4
  mov  [esp],eax
  call some_function
  mov  eax,[esp]
  add  esp,4
  ...
  ret

Essa sequência de SUB/MOV e MOV/ADD acontece em cada um dos PUSHes e POPs, respectivamente. O que o compilador C faz é, já que ele sabe quantos bytes vai precisar usar da pilha, ele os aloca de antemão e usa apenas MOVs para guardar os valores!

Ainda não se convenceu que usar a pilha é melhor?

Se você ainda acha que guardar estados no segmento de dados ou código é uma boa ideia, existe mais um motivo para não fazê-lo. Um acesso à memória depende do cálculo do “endereço efetivo”, que pode ser dado por uma expressão. Por exemplo:

mov eax,[esp]
mov eax,[esp+4]
mov eax,[ebx+esi+8]
mov eax,[ebx+esi*8+8]
mov eax,[0x7ffffff0]

Nos primeiros 4 casos o “endereço” de onde um DWORD será lido é dado pelas expressões envolvendo registradores. No primeiro e no segundo caso não há gasto de ciclos de clock adicionais e o acesso é muito parecido com quando você acessa um registrador qualquer, em termos de performance. Os outros casos envolvem cálculos mais complicados e, no caso do último, um deslocamento maior que 2047. Qualquer deslocamento maior que 2047 causa o consumo de 1 ciclo de clock extra (além do cálculo)… Por exemplo, se usássemos [esp+4096] teríamos o consumo de 1 ciclo a mais na instrução… Se usássemos [ebx+esi+4096], teríamos o consumo de 1 ciclo a mais, graças ao cálculo de EBX+ESI e ainda mais 1 porque o offset é maior que 2047.

Ao usar a pilha e manter as variáveis locais próximas de onde ESP aponta, digamos, menos de 2 KiB perto, não há consumo de ciclo extra. É como se o processador estivesse lendo/gravando num registrador.

É claro que existem outras penalidades: Cache Misses, TLB misses e Page Faults, por exemplo… Mas, isso poderia ocorrer nos outros casos também…

 

Adote uma convenção de chamadas ao estilo de C…

Deixar para as funções chamadoras manterem seus próprios contextos e evitar fazer testes desnecessários em funções de baixo nível são sempre boas ideias… Suas funções de baixo nível devem fazer apenas o que elas precisam fazer. Verificar se ponteiros são nulos, se valores estão dentro da faixa desejada etc, são tarefas para funções de níveis mais altos, mais “inteligentes”. Essa estratégia leva a códigos menores e mais rápidos, sempre!