Simplificação lógica usando mapas de Karnaugh

Uma querida amiga, no Facebook, mostrou-se interessada em aprender um bocado a respeito de eletrônica digital e topou com os mapas de Karnaugh, como recurso para tornar mais simples o esforço de realizar “simplificações” de expressões lógicas. Neste texto vou mostrar para vocês dois estilos diferentes de mapas, como montá-los e usá-los. Mas, antes, é importante entender como fazer esse tipo de simplificação manualmente.

Como na álgebra tradicional, a Booleana também é baseada em certas operações elementares. Para facilitar a compreensão, usarei o símbolo de adição (+) para representar a operação OR e multiplicações para representar AND. Assim, a expressão S=A+BC será a mesma coisa que S=A\quad OR\quad(B\quad AND\quad C).

A primeira propriedade é a de identidade. Ou seja, A+0=A e A\cdot1=A. Outra propriedade interessante é a que acontece quando invertemos o valor fixado para as operações OR e AND: A+1=1 e A\cdot0=0. Com essas quatro proriedade fica fácil de ver que: A(B+1)=A\cdot1=A, por exemplo… Também temos a propriedade distributiva, A(B+1)=AB+A, assim como na aritmética tradicional. O que não é muito evidente é que AND também pode ser distribuído: A+(BC)=(A+B)(A+C), e vice-versa, se colocarmos A “em evidência”.

Vejamos como isso funciona com uma expressão do tipo S=A+\overline{A}B: Pela propriedade distributiva podemos reescrever a expressão como S=(A+\overline{A})(A+B). Se A+\overline{A}=1 e, ao mesmo tempo, X\cdot1=X. O que nos dá: S=A+\overline{A}B=(A+\overline{A})(A+B)=1\cdot(A+B)=A+B, ou seja, eliminamos o \overline{A} da expressão.

Acontece que esse tipo de simplificação pode ser bem complicada para fazer “de cabeça”. E podemos nos confundir se podemos (ou se devemos) realizar uma distribuição usando AND ou OR. Para isso existem os mapas de Karnaugh.

Simplificação com mapa de Karnaugh

Como funciona esse mapa? Trata-se de um retângulo onde, nas colunas, temos as representações de A e seu inverso (1 e 0, ou vice-versa) e nas linhas, B e seu inverso. Uma expressão a ser simplificada deve ser interpretada como sendo constituída de “somas” de produtos… No caso da expressão S=A+\overline{A}B, o A isolado deve ser transformado para A=A(B+\overline{B})=AB+A\overline{B} e assim, obtemos a equação final S=AB+A\overline{B}+\overline{A}B. Daí, em cada termo das “adições” colocamos, no mapa, o valor 1.

Agora precisamos “agrupar” esses uns de acordo com as seguintes regras:

  1. Apenas “uns” adjacentes podem formar grupos (“uns” diagonais não!);
  2. Apenas grupos de 2^n “uns” podem ser formados. Ou seja, cada grupo pode ser formado por 1, 2, 4, 8, 16… “uns”;
  3. Apenas grupos “linhas”, “quadrados” ou “retângulos” podem ser formados (veremos isso com mapas com 3 ou mais variáveis);
  4. Devemos sempre começar pelos maiores grupos possíveis;
  5. Podemos compartilhar “uns” de grupos que já tenham sido formados, desde que pelo menos 1 deles não faça parte de outros grupos;
  6. Se não há mais “uns” fora de grupos já formados, novos grupos não devem ser formados;
  7. A menor quantidade possível de grupos deve ser formada.

Com essas regras obteremos a equação final com a menor quantidade de termos (regra 7) com menores termos (especialmente a regra 4).

No exemplo acima tivemos que formar 2 grupos com 2 “uns” (o verde e o avermelhado) porquê não pudemos criar nenhum grupo com 4 “uns”.

Para cada grupo verificamos quais variáveis não possuem complementos e as escrevemos como um produto… No caso, o grupo vermelho é composto de A, mas têm B e \overline{B}, portanto ambos são eliminados, ficando apenas A… A mesma coisa se dá com o grupo verde, ficando apenas B.

Note que, no mapa com duas variáveis, se tivéssemos uma expressão do tipo S=AB+A\overline{B}+\overline{A}B+\overline{A}\overline{B}, todos as 4 posições teriam “uns” e o resultado final serial S=1… Isso nos dá uma regra interessante:

  • Grupos com 2^n “uns” eliminam n variáveis.

Um grupo grande com 4 “uns” eliminará, necessariamente, 2 variáveis da expressão. No caso anterior, como a expressão só tem duas variáveis, o resultado só pode ser 1. Isso ficará claro, adiante, com mapas maiores.

Mapas de 3 ou 4 variáveis

A diferença de um mapa com mais de duas variáveis é que ele pode se “fechar” lateralmente. No mapa abaixo, para colocarmos mais uma variável, decidi particionar as colunas A e \overline{A} em duas, mas note que para que a porção \overline{C} fique completa, os lados direito e esquerdo do mapa precisam “se tocar”. Ou seja, o mapa deixou de ser plano para ser cilíndrico.

Exemplo com 3 variáveis

No exemplo acima, temos que começar com um grupo de 4 “uns” (o avermelhado). Note que os “uns” continuam adjacentes, mas  não formam uma linha. Formam um “quadrado”… Com isso fica “sobrando” um “1” no mapa que, infelizmente, não pode formar nenhum outro grupo de 4, restando apenas uma possibilidade: um grupo de 2 “uns”, usando um já usado no grupo anterior.

O grupo de 4 “uns” elimina duas das três variáveis. Se prestarmos atenção o grupo usa A, \overline{A}, B e \overline{B}, mas usa apenas \overline{C}… O grupo de dois “uns” elimina uma única variável, permanecendo apenas A\overline{B}.

Um mapa de 4 variáveis faz e mesma coisa que o mapa de 3, mas ele dividirá as linhas de B e \overline{B}, da mesma forma que fiz com C e \overline{C}, mas do lado direito no mapa… Assim, ele se fechará nos dois sentidos, formando uma “toroide” (um cilindro fechado dos dois lados… ou um “pneu”):

Mapa com 4 variáveis

Mapas com mais de 4 variáveis e a codificação de Gray

Mapas com mais de 4 variáveis podem ser montados de acordo com o esquema anterior, porém em 3D. Eu acho particularmente difícil conceber tais mapas tridimensionais e, portanto, para continuar usando Karnaugh, um outro esquema, mais tradicional, é necessário. O mapa pode ser montado de forma bidimensional onde cada linha ou coluna varie, entre uma e outra, em apenas 1 bit, como mostrado abaixo:

Esse tipo de mapa tem que usar uma codificação para cada linha/coluna chamada de código de Gray, já que, assim como mapa de 4 variáveis, ele se “fecha” nos dois sentidos… Isso fica meio chato de montar, mas o código de Gray pode ser obtido para n bits assim:

Começamos pelos dois primeiros valores: 0 e 1. Os dois próximos são os mesmos dois primeiros, porém revertidos, com o próximo bit setado. Ou seja, se temos 0 e 1, obtemos 11 e 10 e teremos a sequência {00,01,11,10}. A próxima sequência é essa mesma, revertida, com o próximo bit setado, ou seja, {110,111,101,100}, o que nos dá a sequência completa {000,001,011,010,110,111,101,100}, para 3 bits… Esse mesmo algoritmo pode ser usado para n bits…

No que concerne o uso do mapa, você coloca os “uns” em cada uma das posições dos produtos, onde 0 significa a variável “negada”, e segue as mesmas regras anteriores (grupos grandes, poucos grupos e grupos de 2^n “uns”). A chatice é determinar quais das variáveis não sofreram alterações nos grupos… Suponha que tenhamos um grupo de 8 “uns” e verificamos que apenas A e B não sofreram variações (A=0 e B=1, no grupo todo, por exemplo)… Assim, para esse grupo de 8 “uns” (e, por causa disso 3 variáveis serão eliminadas, necessariamente, já que 2^3=8), obteremos \overline{A}B.

Desse jeito podemos montar mapas de qualquer tamanho. Mas, atenção que apenas 4 bits nos darão uma linha com 16 possibilidades diferentes. Um mapa com 8 bits, agrupados de 4 em 4, nos dará um mapa com 256 posições!

Usando mapas de Karnaugh com comparações, num if…then…else

Claro que usei variáveis booleanas A, B, C, … levando em conta que elas podem assumir apenas dois valores: true ou false. A mesma coisa pode ser feita com uma comparação como (x < 0), só temos que tomar cuidado com os complementos… Por exemplo, o contrário de (x < 0) é (x >= 0)… Assim, um if do tipo:

if ((x < 0) || ((x >= 0) && (a == b))) { ... }

Pode ser decrito como tendo A=(x < 0), \overline{A}=(x >= 0) e B=(a==b). O que nos daria a expressão A+\overline{A}B. Como vimos, isso pode ser simplificado para A+B e, portanto, o if acima ficaria:

if ((x < 0) || (a == b)) { ... }

O compilador pode fazer essa simplificação para nós, mas nem sempre ele consegue.

Anúncios

Dica: Qualidade de fones de ouvidos…

Não se aplica apenas a fones de ouvidos, mas à saída de amplificadores (como o da sua placa de som) e outros equipamentos de áudio.

Anteriormente, escrevi um artigo que deixou alguns meio “brabos” comigo (por causa do título) onde digo que “DJ’s não sabem de nada“. Falei sobre o uso de equalizadores, sobre como a qualidade de CDs é muito superior aos discos de Vynil e sobre a “loudness wars“. Aqui vai uma dica para você que quer alguma maneira de saber se a qualidade do fone de ouvido (ou da placa-de-som, ou das caixas-de-som) é boa ou não… Trata-se de observar a “resposta de frequência”…

O que isso significa? Todo som audível pode ser desmembrados em “bandas” de frequências, começando à partir dos 20 Hz até os 20 kHz (a faixa média, audível por nós, humanos). Podemos traçar um gráfico mostrando em quais pontos dessa grande faixa conseguimos ouvir, com a intensidade (amplitude ou altura) original e em que pontos essa intensidade é diminuída (atenuada) ou aumentada (amplificada). Eis um exemplo de um gráfico de “resposta de frequências” de um fone de ouvido genérico:

Neste gráfico temos duas escalas: No eixo vertical temos uma escala linear. Cada linha é exatamente 5 dB maior ou menor que a linha anterior. No eixo horizontal temos uma escala “exponencial”. Note o padrão ente a linha 100 e a linha 1000. Os traços vão ficando mais e mais perto uns dos outros, numa espécie de compressão, para que possamos traçar o gráfico em uma escala muito maior sem gastar muito espaço… Ainda, a partir da linha 100, a próxima, à direita, representa 200 e, portanto, de uma linha para outra houve uma variação de 100 unidades… Mas, a partir da linha 1000, às linhas à direita variam de 1000 em 1000 (ou seja, numa escala 10 vezes maior que a anterior). A esse tipo de escalonamento bidimensional damos o nome de “escala semi-logarítmica” (porque uma delas não é “logarítmica”!).

De acordo com o texto em que sacaneio os DJ’s, sabemos que “decibel” é uma unidade de medida relativa, uma razão… 0 dB equivale a uma relação de 1:1, 3 dB equivale a, aproximadamente, uma razão de 2:1 e, -3 dB a uma relação de 1:2… É padrão considerar qualquer coisa abaixo de -3 dB como “inaceitável” em termos de “perda” ou “atenuação”. Então, o que esse gráfico de “resposta” nos diz?

Bem… Mais ou menos abaixo de 100 Hz e acima de 15 kHz o sinal será atenuado para menos de -3 dB. Ou seja, o som vai ficar “baixinho” nessas frequências… O gráfico diz mais ainda: Mais ou menos lá pros 150 Hz até os 2 kHz a amplitude do sinal será mais ou menos a original (não há perdas e nem ganhos significativos, ou seja, fica em torno dos 0 dB). E, também, para frequências entre 2 kHz até pouco depois dos 10 kHz há um “ganho” de volume (amplitude)… ou seja, essas frequências vão parecer mais altas no seu ouvido.

Ora, de forma ideal, o que você quer é um fone que tenha uma resposta em torno dos 0 dB para toda a faixa audível. Então, quanto mais “retinha” for a curva, perto dos 0 dB, melhor…. Poucos fones oferecem isso. Um exemplo é o Koss Porta Pro:

Koss Porta Pro e sua resposta de frequência

Note a pouquíssima amplificação ou atenuação em toda a banda audível e o repentino corte na frequência de 20 kHz! Isso faz da Koss, além de ser a empresa que inventou os fones de ouvido, um dos melhores fabricantes na área.

SDCC: Algumas considerações sobre o Z80…

Escrevendo o artigo nostálgico sobre Z80 e 6502 testei o SDCC (Small Devices C Compiler) criando pequenos códigos. Eu pretendia mostrar como um código simples (checksum ou obter o maior valor contido num array) ficariam, para esses processadores. Minha surpresa é que o SDCC cria código ineficiente.

A primeira coisa a fazer aqui é determinar qual é a convenção de chamada usada pelo SDCC. Para isso vou compilar funções simples:

char f(void)   { return '0'; }
char g(char c) { return c + '0'; }
int  h(void)   { return -1; }
int  i(int x)  { return x - 1; }

Isso cria código como mostrado abaixo:

_f:
  ld  l,#0x30       ; L = '0'.
  ret

_g:
  ld  hl, #2
  add hl, sp        ; HL = SP+2
  ld  a, (hl)       ; A = c
  add a, #0x30      ; A += '0'
  ld  l,a
  ret

_h:
  ld  hl,#0xFFFF    ; HL = -1
  ret

_i:
  ld  hl, #2
  add hl, sp        ; HL aponta para x, na pilha.

  ld  e, (hl)       ; DE = (HL).
  inc hl
  ld  d, (hl)

  dec de            ; HL = DE - 1
  ex  de,hl
  ret

Ao que parece, os valores de retorno são sempre feito em L ou no par HL e o acumulador, bem como o par DE, podem ser modificados à vontade (não precisam ser preservados entre chamadas). E, também, os argumentos da função são sempre passados pela pilha.

Para determinar melhor a convenção de chamadas, devemos lidar com rotinas mais complexas, para observar a alocação dos registradores e, se necessário, como as variáveis locais são alocadas na própria pilha. Por exemplo, uma rotina mais elaborada, checksum, poderia ser útil:

#include <stdint.h>
#include <stdlib.h>

uint16_t cksum(uint8_t *p, size_t size)
{
  uint16_t sum;

  for (sum = 0; size--; )
    sum += *p++;

  return sum;
}

E, eis o código que o SDCC cria:

_cksum:
  push  ix        ; Salva IX para usá-lo como
  ld    ix,#0     ; ponteiro auxiliar para a pilha.
  add   ix,sp

  push  af        ; Cria espaço para cópia do ponteiro p.

  ld    de,#0     ; DE é 'sum'.

  ; Copia 'p' para variável local, na pilha.
  ld    a,(ix+4)
  ld    (ix-2),a
  ld    a,(ix+5)
  ld    (ix-1),a

  ; BC contém 'size'
  ld    c,(ix+6)
  ld    b,(ix+7)

00103$:
  ld    h,c       ; HL <- BC
  ld    l,b
  dec   bc        ; size--;

  ; size == 0?
  ld    a,l
  or    a,h
  jr    Z,00101$   ; Se 'size==0', sai da rotina.

  pop   hl        ; Recupera 'p' da pilha.
  push  hl

  ld    l,(hl)    ; L <- *p

  ; Incrementa p (na pilha)
  inc   (ix-2)
  jr    NZ,00116$
  inc   (ix-1)

  ; sum += *p;
00116$:
  ld    h,#0x00
  add   hl,de
  ex    de,hl
  jr    00103$

  ; Coloca DE em HL, recupera SP, limpa a pilha e sai.
00101$:
  ex    de,hl
  ld    sp, ix
  pop   ix
  ret

Aqui podemos extrapolar que AF e BC também não são preservados. Aliás, ao que parece, apenas os registradores de índice IX e IY (se usado) e o SP (por motivos óbvios) devem ser preservados… Lembrando que os retornos são feitos em L ou HL. E, mesmo no caso de retornos de tipos de 8 bits, o registrador H não precisa ser preservado (como pode ser visto na função g, lá em cima).

Uma coisa estranha no código criado pelo SDCC é que ele preferiu manter uma cópia do ponteiro ‘p’ na pilha, ao invés da variável local ‘sum’… E a rotina ficou maior do que poderia ser, respeitando os critérios do compilador. Eis como eu a implementaria, se fosse o compilador:

_cksum:
  push ix
  ld   ix,#0
  add  ix,sp

  ld   h,(ix+4)   ; HL <- p
  ld   l,(ix+5)
  ld   b,(ix+6)   ; BC <- size
  ld   c,(ix+7)

  ld   de,#0      ; DE <- 0

.loop:
  ld   a,b        ; if (BC == 0) goto .exit;
  or   c
  jr   z,.exit

  dec  bc         ; BC--;

  ld   a,e        ; DE += *p;
  add  a,(hl)
  ld   e,a
  ld   a,d
  adc  a,#0
  ld   d,a

  inc  hl         ; p++;

  jr   .loop

.exit:
  ex   de,hl      ; HL <- DE.
  pop  ix
  ret

Não há necessidade de variáveis locais alocadas na pilha e a rotina acima é 6 instruções menor que a anterior. Ainda, o loop principal é mais curto!

Claro que o SDCC foi esperto ao usar o par HL, com H zerado, para acumular, em DE, o checksum, mas não foi muito esperto ao usar uma variável local, na pilha, para manter a cópia do ponteiro p. Outro fato interessante é que eu não confio que (IX-2) será calculado corretamente, já que as instruções que usam IX dessa maneira indireta adicionam um byte ao registrador de 16 bits. Ou seja, -2 é 0xFE e não 0xFFFE… Isso é uma desconfiança minha e é bem possível que essa adição seja feita considerando o sinal do offset (é provável que seja assim).

Deixe-me lembrá-lo que o processador Z80, assim como outros de 8 bits, não possuem cache (nem de dados, nem de código). Não possuem “reordenador” de instruções, não possuem arquitetura superescalar, não possuem “branch prediction”, etc… Cada instrução e cada acesso à memória adicional conta. A regra para otimização de código para esses processadores é: Menos instruções e menos acessos à memória, além, é claro, de bons algoritmos.

Cuidado com as expressões…

Uma “linguagem de programação” geralmente é composta de sequências de operações, que são divididas em expressões aritméticas e operações de controle de fluxo (if..then..else, while, do…while, …). Humpf… E já ouvi gente dizendo que “programação nada tem a ver com matemática!”…

Como na aritmética e na álgebra, expressões devem ser avaliadas de acordo com a “importância” do operador. Por exemplo, ao fazermos x+y\cdot z, devemos multiplicar y e z antes de adicionarmos x. A isso damos o nome de precedência (no sentido de “o que vem antes”). Mas, como não temos apenas as 4 operações fundamentais da álgebra (+, -, × e ÷), todos os operadores têm que seguir alguma regra de precedência… Na linguagem C temos a seguinte tabela:

Ordem de precedência Operador Associatividade
1 ++, — (pós-incremento e pós-decremento)
() (chamada de função)
[]
.
->
(T){list} (composição)
E→D
2 ++, — (pré-incremento e pré-decremento)
+, – (unários)
!
~
(T) (casting)
* (indireção)
& (“endereço de”)
sizeof
_Alignof
D→E
3 *, /, % E→D
4 +, –
5 <<, >>
6 <, <=, >, >=
7 ==, !=
8 &
9 ^
10 |
11 &&
12 ||
13 ?: D→E
14 =, +=, -=, *=, /=, %=
&=, |=, ^=
<<=, >>=
15 , E→D

Quanto menor for a ordem de precedência, maior é o grau de precedência do operador, ou seja, ele será avaliado antes. Mas, como o leitor pode observar, isso não é suficiente. O termo “associatividade” significa “de que lado” devemos começar. Operadores como + e -, por exemplo, têm associatividade da esquerda para direita (E→D), significando que a sub expressão do lado esquerdo do operador deve ser avaliada antes da do lado direito.

Pôxa! Temos que decorar esses trecos de associatividade também? Não! Note que, além dos operadores de assinalamento, somente os operadores unários (que só têm um único argumento à direita) têm associatividade D→E, e isso faz todo sentido! As únicas exceções são os pós-incrementos e pós-decrementos, chamadas de função, arrays, e o pseudo-operador condicional ?:, que é problemático (às vezes) e recomendo (pela primeira vez neste texto) que seja evitado. Todos os outros operadores têm associatividade da esquerda para direita.

Note também que os operadores de assinalamento (= e seus primos) têm a mais baixa precedência de todos, exceto pelo operador vírgula e, portanto, serão avaliados por último. Por exemplo, numa expressão como:

*p = x + 1;

Temos 3 operadores: O de indireção (*), o de atribuição (=) e a adição (+). Nessa expressão o operador de indireção tem maior precedência (menor ordem), a adição tem precedência menor, mas a atribuição tem a mais baixa (maior ordem). Podemos entender a expressão acima como (*p)=(x+1). De acordo com a associatividade das operações e sabendo que o assinalamento é feito por último, a sub expressão da direita de = é resolvida primeiro e depois a expressão do lado esquerdo. Só então a atribuição é feita.

Existe, é claro, outra forma de entender isso: Uma expressão pode ser organizada numa árvore binária que pode ser percorrida de forma pós-ordenada (visita esquerda, visita direita, visita raiz). É um pouco mais complexo do que isso devido a associatividade, mas em essência, para compreensão, podemos manter essa analogia… Nessa árvore, os operadores com menor precedência são colocados no topo da árvore e os com maior, mais perto dos nós folha…

Isso parece simples, mas note o problema no fragmento de código abaixo:

int x;

x = 1 << 3 + 1

Qual será o resultado? 9 [de (1 << 3)+1] ou 16 [de 1 << (3+1)]? Vejamos: Vimos que = tem precedência mais baixa e associatividade da direita para esquerda, então a sub expressão à sua direita será resolvida primeiro, ou seja, 1 << 3 + 1. Aqui, tanto o operador << quanto + têm a mesma regra de associatividade (da esquerda para direita), mas + precede <<. Assim, a sub expressão fica (1 << (3 + 1)). O resultado é 16.

À primeira vista, pode parecer que o shift lógico tem maior prioridade que a adição ou, pelo menos, a mesma. Parece que o programador queria fazer um shift e depois somar 1. Entender como funciona o esquema precedência e associatividade é importante para evitar esse tipo de problema, senão você terá que usar parenteses em todas as suas expressões (o que não é má ideia, em caso de dúvida).

Outro exemplo está nas comparações. Note que os operadores lógicos (tanto binários [&. | e ^] quando os “lógicos” [&& e ||]) tem precedência menor que comparações (==, !=, <, , >=). Daí, ambas as construções abaixo são idênticas:

if (x == 0 && y == 0) ...
if ((x == 0) && (y == 0)) ...

Substitua == por = e temos uma inversão de precedências, ou seja, o = é feito por último… A expressão x = 0 && y = 0 fica x=((0 && y)=0), o que gerará um erro de LVALUE. Lembre-se, se && tem maior precedência que =, então ele é executado primeiro…

O que diabos é um LVALUE? Bem… operadores de atribuição esperam que o que esteja do lado esquerdo da expressão seja um objeto onde um valor possa ser armazenado. A sub expressão do lado direito criará uma atribuição do tipo 0=0 e não é possível armazenar o valor zero dentro de outro valor zero…

Ainda outro ponto de nota é que cada operador espera um conjunto de argumentos (ou operandos). Falo conjunto porque alguns operadores precisam de apenas um argumento (todos os operadores de ordem de precedência 1 e 2, na tabela acima). O restante, precisa de dois argumentos, exceto pelo operador condicional (?:), que precisa de 3… mas esse, tecnicamente, não é bem um operador e tem lá seus problemas com precedência e associatividade (recomendo evitá-lo, pela segunda vez neste texto).

Ainda falando de precedência, vale relembrar sobre os operadores de maior precedência . e ->, bem como citar o operador de indireção (*), com precedẽncia imediatamente inferior. O problema de misturar o operador de resolução de membros de estruturas (.) com o indireção (quando usamos ponteiros) é que a coisa não funciona bem como pode ser sua intenção. A expressão *p.x = 1;, sendo x um membro de uma estrutura qualquer apontada por p não faz o que se espera dela. Por ‘.’ ter precedência maior que ‘*’, a expressão pode ser entendida como *(p.x) = 1;, ou seja, estamos dizendo que o membro x é que é o ponteiro, não p. Para fazermos o que queríamos, temos que resolver esse problema de precedência com o uso de parenteses: (*p).x = 1;.

Acontece que ficará meio chato ter que fazer isso toda vez que usarmos o ponteiro p para essa (e outras) estruturas. Daí o operador ‘->’ foi criado e ele espera ter, no seu lado esquerdo, um ponteiro. O operador dereferencia o ponteiro sem a necessidade do uso do operador ‘*’. Daí, a expressão p->x = 1; é a mesma coisa que (*p).x = 1;.

Outro problema para sua consideração: Note que casting (promoção de tipo) também é um operador e tem precedência menor, por exemplo, do que um pós-incremento. Isso quer dizer que uma expressão do tipo (char *)p++ pode não fazer exatamente o que você espera… Suponha que p seja do tipo int *. A expressão ao lado vai adicionar sizeof(int) ao ponteiro e depois converter a expressão para o tipo char *. Se você quisesse adicionar sizeof(char) ao ponteiro, terá que, necessariamente, fazer: ((char *)p)++. Isso é fácil demonstrar:

/* test.c */
#include <stdio.h>

void main(void)
{
  static int x[2] = { 1, 2 };
  int *p, *q;
  char c;

  p = q = x;
  c = *(char *)p++;

  printf("(%p) %p -> 0x%02hhx\n", q, p, c);
}

Ao compilar e executar:

$ cc -o test test.c
$ ./test
(0x601038) 0x60103c -> 0x01

E, por último, nem todos os operadores lógicos tem precedência baixa. A exceção são os operadores de negação (! e ~). Isso garante que expressões como !a == b realizem a negação lógica do argumento a apenas, ao invés de toda a sub expressão à direita de !. Compare isso com expressões como a == b && b == c

Ponteiro para um array…

Eu evito algumas construções mais “esotéricas” da linguagem C, não porque não saiba o que elas signifiquem, mas em virtude da legibilidade… Recentemente me perguntaram o que significa a declaração:

int (*p)[4];

Bem… isso ai é um ponteiro para um array de 4 inteiros. O que é bem diferente de:

int *p[4];

Que é um array de 4 ponteiros para o tipo int.

O detalhe é que deixei meio de lado a utilidade da primeira declaração. Considere isso:

int a[4][4] =
  { { 1, 2, 3, 4 },
    { 5, 6, 7, 8 },
    { 9, 0, 1, 2 },
    { 3, 4, 5, 6 } };

void showarray(int a[][4])
{
  int i, j;

  for (i = 0; i < 4; i++)
  {
    for (j = 0; j < 4; j++)
      printf("%d ", a[i][j];
    putchar('\n');
  }
  putchar('\n');
}

A rotina showarray, como declarada acima, é um jeito de mostrar todos os itens de um array. Podemos chamá-la com showarray(a); e tudo funcionará perfeitamente bem… Mas, e se quiséssemos usar ponteiros ao invés de 2 índices (i e j)?

Note que, se você tem um array simples, pode usar um ponteiro para apontar para o primeiro item e incrementar o endereço contido no ponteiro para obter o próximo item, como em:

int a[] = { 1, 2, 3, 4, 5, 0 };

void showarray(int *p)
{
  for (; *p; p++)
    printf("%d ", *p);
  putchar('\n');
}

Aqui, o compilador criará código para somar 4 ao conteúdo de p a cada vez que ele for incrementado. O valor 4 é adicionado porque sizeof(int)==4. A pergunta original é: “Dá pra fazer algo semelhante com arrays bidimensionais?”. A resposta, obviamente, é: SIM!

Ao declarar um ponteiro p como int (*p)[4];, toda vez que você incrementar o ponteiro, a ele será adicionado o valor 16 (4*sizeof(int)) e podemos escrever a rotina showarray original, assim:

void showarray(int (*p)[4])
{
  int i;

  // Não é bem a rotina original, aqui considero que
  // se o primeiro item da "linha" for zero, devemos
  // encerrar o loop.
  //
  // p++ fará o ponteiro p apontar para o início da
  // próxima linha...
  for (; (*p)[0]; p++)
  {
    for (i = 0; i < 4; i++)
      printf("%d ", (*p)[i]);
    putchar('\n');
  }
  putchar('\n');
}

O array original, é claro, deverá ser definido assim, para a rotina funcionar:

int a[][4] =
  { { 1, 2, 3, 4 },
    { 5, 6, 7, 8 },
    { 9, 0, 1, 2 },
    { 3, 4, 5, 6 },
    {} };  // note: 4 zeros aqui!

Mais um exemplo: Nem sempre assembly é a resposta!

Já escrevi sobre isso aqui: Criar suas próprias rotinas em assembly não é uma panaceia para a obtenção de alta performance. É possível acabar com uma rotina pior do que a gerada pela linguagem de alto nível. Especialmente se estivermos falando de compiladores que oferecem recursos de otimização.

Para demonstrar, consideremos a simples rotina de selection sort, abaixo:

#define swap(a,b) \
    { int _t; _t = (a); (a) = (b); (b) = _t; }

// Para ser justo, não vou permitir inlining...
__attribute__((noinline))
static void selection_sort(int *p, unsigned int size)
{
  unsigned int i, j;

  for (i = 0; i < size - 1; i++)
    for (j = i+1; j < size; j++)
      if (p[i] > p[j])
        swap(p[i], p[j]);
}

É legítimo pensar que essa rotina seja menos que ótima, já que usa o macro swap(), que lança mão de uma variável temporária que talvez seja alocada em memória. Assim, o programador pode criar uma rotina equivalente, em assembly, assim:

bits 64

section .text

; void selection_sort_asm(int *, unsigned int);
; -- Para ser justo, alinho em DWORD o ponto de entrada
;    da rotina!
  global selection_sort_asm
  align 4
selection_sort_asm:
  lea r8d,[rsi-1] ; r8d == size - 1;

  xor ecx,ecx     ; i = 0;

.loop2:
  lea edx,[rcx+1] ; j = i + 1;

.loop1:
  mov eax,[rdi+rcx*4]   ; if (ptr[i] > ptr[j]) ...
  cmp eax,[rdi+rdx*4]
  jle .skip

  xchg eax,[rdi+rdx*4]  ; ... swap(p[i], p[j]);
  mov [rdi+rcx*4],eax

.skip:
  add edx,1     ; j++
  cmp edx,esi   ; if (j < size) goto loop1;
  jb  .loop1

  add ecx,1     ; i++;
  cmp ecx,r8d   ; if (i < size - 1) goto loop2;
  jb  .loop2

  ret

Claro que essa rotina pode ser melhorada, especialmente entre os labels .loop1 e .skip, mas, em arquiteturas mais modernas (Ivy Bridge, SandyBridge e Haswell, sem contar com as mais recentes Broadwell e Skylake) os cálculo de endereços efetivos podem ser cacheados, numa espécie de common subexpression elimination, ou seja, isso não tem grande influência… Além do que, quero mostrar como uma abordagem “ingênua” se parece…

Bem… a rotina acima não é tão “ingênua” assim porque levei em conta algumas possíveis otimizações: Note que usei a instrução XCHG, usada para aproveitar o conteúdo de EAX na “troca” e evitar o uso de um outro registrador temporário. Repare também que não uso a instrução INC para evitar a penalidade de 1 ciclo de clock pelo fato dessa instrução não afetar o flag de carry (e precisar preservá-lo). É preferível usar ADD, mesmo tendo tamanho maior, em seu microcódigo… Ainda, os saltos condicionais são feitos “para trás”, para aproveitar o algoritmo estático de branch prediction (exceto para o label .skip). Uso também as instruções LEA para adições rápidas, carryless

Mas, se você medir a performance de ambas as rotinas contra um array de 10 elementos aleatórios obterá (num i5-3570 @ 3.4 GHz, arquitetura Ivy Bridge) algo em torno de 1800 ciclos para a rotina em C e 2200 ciclos para a rotina em assembly! Ou seja, a rotina em C é 18% mais rápida!!! Num i7, com arquitetura Haswell poderá obter menos ciclos…

A rotina em Assembly equivalente para o selection sort, gerada pelo GCC com as opções de compilação “-O2 -mtune=native“, é esta:

bits 64

section .text

  global selection_sort
  align 4
selection_sort:
  cmp esi, 1
  jbe .exit
  lea r11d, [rsi-1]
  mov r9, rdi
  xor r10d, r10d

  align 4
.loop2:
  add r10d, 1
  mov eax, r10d
  cmp esi, r10d
  jbe .skip2

  align 4
.loop1:
  mov edx, eax
  mov ecx, [r9]
  lea rdx, [rdi+rdx*4]
  mov r8d, [rdx]
  cmp ecx, r8d
  jle .skip1
  mov [r9], r8d
  mov [rdx], ecx

.skip1:
  add eax, 1
  cmp esi, eax
  jne .loop1

.skip2:
  add r9, 4
  cmp r10d, r11d
  jne .loop2
  ret

.exit:
  ret

Essencialmente, ela é a mesma coisa da rotina em assembly que mostrei acima. A diferença está na organização das instruções e no aproveitamento do paralelismo das unidades de execução do processador (não confundir com os “cores” ou “núcleos”!).

O GCC também evita instruções problemáticas como XCHG (que, quando faz acesso à memória, “trava” [lock] o barramento de dados). O compilador também entende que pontos de retorno de loops podem precisar estar alinhados para que eles não cruzem a fronteira de uma linha do cache L1I e, por isso, coloca aquele “align 4” lá… Ele também tenta evitar problemas de “interlocking” de registradores (quando modificamos um registrador e tentamos usá-lo, na instrução seguinte, como operando fonte. Isso evita que duas instruções sejam executadas em paralelo).

Ou seja, o compilador tenta levar em conta a grande quantidade de regras de otimização (que podem ser estudadas no manual de otimização de software da Intel [baixe aqui] – prepare-se: são quase 700 páginas!) que você, ou eu, poderíamos deixar “passar batido”. Isso não significa que não seja possível para você ou eu elaborarmos uma rotina que seja melhor da gerada pelo compilador. Isso significa, porém, que na maioria das vezes, o compilador faz um trabalho melhor do que faríamos!

Um kbhit() para Windows

Num artigo anterior (este aqui) mostrei como codificar um kbhit() para Linux. Ficou faltando a mesma função para Windows.

Algumas pessoas insistem em usar o header conio.h, que existe para o MinGW e o Visual Studio… Se esses são seus alvos para compilação e seu projeto não precisa ser portável, vá em frente, use o header. Mas, saiba que você pode codificar essas funções de forma mais “portável”, juntando as definições dos outros artigos (para Linux) com essas aqui.

No caso do Windows, podemos usar as funções da Console API, que é mais ou menos equivalente à termios, do Linux. Eis as rotinas _kbhit() e _getch():

#include <windows.h>

// Ok... essa função só tem um problema.
// Por causa do loop, a thread consumirá
// muito tempo de CPU...
int _kbhit(void)
{
  HANDLE hConsole;
  INPUT_RECORD ir;
  DWORD n;

  hConsole = GetStdHandle(STD_INPUT_HANDLE);
  while (PeekConsoleInput(hConsole, &ir, 1, &n))
    if (ir.EventType == KEY_EVENT)
      return 1;

  return 0;
}

int _getch(void)
{
  HANDLE hConsole;
  DWORD cm, n;
  char buffer[4];   // Para ter certeza que um caracter
                    // UNICODE cabe aqui, alocamos 4 bytes.

  hConsole = GetStdHandle(STD_INPUT_HANDLE);
  GetConsoleMode(hConsole, &cm);
  SetConsoleMode(hConsole, cm &
             ~(ENABLE_LINE_INPUT | ENABLE_ECHO_INPUT));
  ReadConsole(hConsole, buffer, 1, &n, NULL);
  SetConsoleMode(hConsole, cm);

  // Só preciso de 1 char...
  return buffer[0];
}

Repare como, em _getch() desabilito “LINE INPUT” (mais ou menos como o método “canônico” do termios) e o “ECHO INPUT”. Fiz algo semelhante no getch() e kbhit() lá do Linux…

A função _kbhit() fica um pouco mais simples por causa de PeekConsoleInput, que nos permite obter os eventos de entrada sem retirá-los da fila. Essencialmente, percorremos a fila de eventos à procura de um KEY_INPUT. Se algum for achado, retornamos 1 (true)…