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.

Microprocessador de 32 bits (MC68000)

Ao contrário do que você pode imaginar, os microprocessadores de 32 bits são mais velhos do que os de 16. O primeiro microprocessador comercial (encapsulado em um chip) foi o 4004, da Intel (processador de 4 bits — você leu certo!) em 1969. Dez anos depois surge o MC68000 e somente alguns anos depois surge o 8088/8086. Claro, estou citando apenas os microprocessadores comercialmente relevantes aqui. Somente no final do ano de 1985 a Intel lançou seu processador de 32 bits, o 80386 (e só no iniciozinho dos anos 90 foi usado nos PCs). Ou seja, a Motorola já tinha seu processador de 32 bits sendo usado em alguns (poucos) mainframes, no MacIntosh e depois no Amiga, quando os PCs com arquitetura de 32 bits começaram a aparecer.

Se fôssemos falar de computadores, na época da criação do UNIX, Ken Thompson relata algumas experiências que fazia em máquina com “palavra” de 36 bits e onde 1 “byte” tinha 9 bits (não 8)… Isso, também, no final dos anos 60. E, só para comparar, em 1946 o ENIAC usava “palavras” de 10 bits (o projeto começou em 1943 e terminou em 1956 [coincidência em relação à “invenção” do transístor em 1955?]).

MC68000

AMIGA 500 usava o MC68000.

O 68000 (ou 68k) é um processador interessante: Internamente, todos seus registradores (exceto flags) têm 32 bits de tamanho, mas externamente seu barramento de dados é de 16… Por isso a documentação o trata como um processador de 16/32 bits. Mas, o que chama a atenção para ele não é o conjunto de instruções ou o tamanho da “palavra”. Ele contém um conjunto abrangente de “modos de endereçamento” e um conjunto grande, para a época, de registradores de uso geral.

Existem 16 deles… D0 até D7 são registradores de 32 bits usados para conter e manipular dados (considere que o 8086 tem apenas 4: AX, BX, CX e DX). A0 até A7 são também registradores de 32 bits, mas dedicados a conter e manipular endereços. De fato, A7 é especial, dedicado a conter o endereço do topo da pilha (USP ou User Stack Pointer). Além desses, temos o PC (Program Counter) de 32 bits — o que, em teoria, poderia nos dar um espaço de endereçamento de 4 GiB, já em 1979! Embora o MC68000 tivesse barramento de endereços de 24 bits, possibilitando, no máximo, 16 MiB) e o registrador de 16 bits CCR (Condition Code Register) que contém os flags e alguns bits de controle.

Assembly

Quem já mexeu com o assembler inline do GCC já reparou que, no padrão AT&T, temos que informar ao compilador que a instrução usa “palavras” de tamanho específico e a ordem dos operandos fonte e destino é invertida (em relação aos mnemônicos usados pela Intel), como em:

movl $0,%eax

Aqui temos a movimentação do valor 0 para dentro do registrador EAX. E a redundância de termos que informar um ‘l’ (de long), logo após o mnemônico ‘mov’.

Suspeito que essas notações tiveram origem no MC68000. No Assembly dele a coisa funciona do mesmo jeito, com alguns detalhes diferentes… Ao invés de simplesmente colocarmos um ‘l’, temos que colocar um ‘.l’ e o caracter ‘$’ é usado para denotar um valor hexadecimal. O caracter usado para denotar um valor imediato é ‘#’. Assim, para colocarmos o byte 0xff entro de D0 temos que escrever:

move.b #$ff,d0

Se você esquecer de colocar o ‘#’ na frente o valor é um endereço de memória. E, outra coisa: Somente os registradores D# podem manipular coisas menores que 32 bits.

Outro notação similar ao padrão AT&T é o uso de offsets nos endereçamentos. Por exemplo:

move.l 4(a0),d0  ; ou move.l (4,a0),d0

Aqui temos o valor 4 adicionado a A0 antes de ler o DWORD da memória…

Outra coisa à frente de nosso tempo, que já tinha nos 68000 e só veio a aparecer na arquitetura da família 80×86 com o surgimento do modo amd64 (ou x86-64), é o endereçamento relativo ao PC.

O 68k não é RISC

RISC significa somente “Reduced Instruction Set Computer“. Ou seja, se o processador tem poucas (mas, poderosas, instruções) é RISC… O 68000 é CISC (C de Complex) porque possui algumas instruções interessantes. Por exemplo, MOVEM pode mover múltiplos operandos para dentro de vários registradores. Literalmente uma lista de dados/registradores para outros dados/registradores. Em C, uma expressão como “a = b = *p = 0” pode ser feita com uma única instrução em linguagem de máquina!

Alguns fazem confusão a respeito do 68000, como se ele fosse RISC, pelo grande número de modos de endereçamento. Por exemplo, existem dois tipos de endereçamento indiretos que fazem, automaticamente, pós incrementos e pré-decrementos. Por exemplo:

move.l -(a0),d0
move.l d0,(a1)+

O que é incrementado ou decrementado aqui não é o conteúdo da memória endereçada, mas o registrador A#. Agora, dê uma olhada no código padrão da rotina strcpy:

# char *strcpy(char *d, char *s)
# {
#   char *p = d;
#   while (*d++ = *s++);
#   return p;
# }
strcpy:
  link.w %fp,#0        # A6 = SP (não reserva espaço local).

  move.l %a2,-(%sp)    # O compilador preferiu reservar
                       # temporário local aqui!

  move.l 8(%fp),%a0    # A0 = d
  move.l 12(%fp),%a2   # A2 = s
  move.l %a0,%a1

.L2:
  move.b (%a2)+,%d0
  move.b %d0,(%a1)+
  jne .L2

  move.l %a0,%d0       # Retorna p em D0.

  move.l (%sp)+,%a2

  unlk %fp             # Restaura a pilha...
  rts

Observe, particularmente, o loop… Em primeiro lugar, MOVE, assim como no 6502, afeta o flag Z. Em segundo lugar, o próprio modo de endereçamento incrementa os ponteiros que foram passados como argumentos para a função! (Não sei o suficiente da convenção de chamada do GCC para o 68000 para te dizer porque ele precisa salvar A2 na pilha!). Outra coisa: FP (de Frame Pointer) é apenas um apelido para A6.

Modo “protegido”, memória virtual e ponto-flutuante

Desde o começo, em 1979, o 68000 possui modos de operação distintos. Dentre eles o modo Supervisor e o modo User, sendo o primeiro “mais privilegiado” do que o segundo… Somente com o 68020 é que o recurso de “paginação” foi introduzido, por hardware, no microprocessador e, somente com o 68030 as instruções de ponto flutuante foram incorporadas (antes, era necessário o uso de um co-processador matemático: o 68881/68882 (em meados dos anos 80) — o mesmo ocorreu com a Intel e seu 8087).

Com o 68010 a Motorola introduziu o 68851, Um chip dedicado a MMU (Memory Management Unit), que permitia a virtualização de memória (em 1982!).

O maior “erro” da IBM, em minha opinião…

… foi não criar o PC com base no 68000. Pensem como seria o avanço de 8 para 32 bits de uma só tacada e, em pouco tempo, o uso de memória virtual!!! Isso era perfeitamente factível, na época, tanto é que a Apple logo lançou o MacIntosh, com interface gráfica… O fato do Mac ser caro, na época, foi mais devido a ganância (ou ao alto custo do investimento feito por uma empresa pequena, em comparação à IBM) do que qualquer outra coisa.

Diz a “lenda” que a IBM queria o PC no 68000, mas não encontrou uma empreiteira que desenvolvesse o DOS para eles. Entra em cena a Microsoft e a sugestão de uso de processadores Intel…

A Intel e seu processador de 16 bits…

Mais nostalgia pra vocês… Dessa vez, sobre o 8086.

IBM PC modelo 5150. Bonito, não?

No início dos anos 80 a IBM apresentou ao mundo o IBM PC Modelo 5150, baseado no processador 8088. O 8088 é uma versão com barramento de dados de 8 bits do 8086 e essa foi a arquitetura escolhida porque já existiam muitos microcomputadores de 8 bits no mercado e componentes eletrônicos especializados para eles. A intenção não era reinventar a roda em todo o circuito.

Na época existia uma boa briga, especialmente entre a Apple, com seu Apple ][ (e mais tarde com o MacIntosh) e a IBM e os PCs… Muitos, como eu próprio, acreditavam que o aumento de 8 para 16 bits era um senhor avanço, mas que a alusão a “Personal Computer” era exagerada. O bicho era caro, grande e com cara “profissional” demais para ser “pessoal”. E, ainda por cima, era da IBM! Era quase como almejar comprar um carro zero quilômetro fabricado pela NASA!

Por incrível que pareça, os modelos de PCs da IBM, até os AT (de Advanced Technology), jamais usaram o 8086… Felizmente a empresa, logo no início, abriu toda a documentação do bicho e começaram a surgir clones e esses modificaram o circuito para uso do 8086.

Família de processadores 8086

Os 8088/8086 eram os irmãos maiores do antigo 8085 e, esse último, uma versão um pouco melhor do 8080, ambos de 8 bits. Neles tínhamos registradores de uso geral A, B, C, D, E, H e L, bem como PC (de Program Counter), SP (Stack Pointer) e Flags… Nos 8086 a Intel manteve A, B, C e D, estendendo-os para 16 bits e, por isso eles têm um X após seus nomes (X de eXtended)… A intenção por trás de H e L, nos 8080, sempre foi o uso do par HL, onde H é o MSB e L o LSB. De fato, nos 8080 e 8085 o par HL, quando usado como ponteiro, forma um pseudo registrador chamado M (de Memory). Assim, os registradores AX, BX, CX e DX puderam ser “desmembrados” em seus bytes de alta e baixa ordem, como em AH e AL.

Os registradores PC e SP continuam lá e funcionam igualzinho, mas para dar um “plus” ao conjunto de instruções — e tentar competir com o Z80 — a Intel resolveu flexibilizar o esquema de endereçamento para as instruções. É bom lembrar que no Z80 existem 3 maneiras de usar ponteiros:

  • Via endereçamento absoluto, como em LD A,(0xC010);
  • Via endereçamento indireto, como em LD A,(HL);
  • Via endereçamento indireto indexado, como em LD A,(IX+1)

A Intel resolveu criar o esquema de endereçamento com até 3 “operandos”: endereço base, índice e offset, como em MOV AL,[BX+SI+2]. Mas existe um problema: Somente os registradores BX e BP podem ser usados como “base” (por isso o B na frente do nome) e somente SI (de Source Index) e DI (de Destination Index) podem ser usados como índice (e por isso esses dois registradores existem — e não podem ser “desmembrados” como seus irmãos que terminam com X). Esse esquema de endereçamento só foi flexibilizado nos 80386 ou superiores.

Observação: O registrador BP não existe para apontar para a “base da pilha”, mas para ser usado como ponteiro e compor o “endereço base” no esquema de endereçamento dos 8086 quando se trata de acesso à pilha!

Endereços maiores que 16 bits

Na época era pouco comum obter um microcomputador que tivesse mais que uns 48 KiB de RAM. Outro atrativo do IBM PC-5150 era a “enorme” quantidade de memória que o sistema poderia suportar: 256 KiB! Mas, para que isso acontecesse era necessário que o barramento de endereços tivesse mais que 16 bits. Foi resolvido que teria 20 e uma capacidade teórica “absurda” de 1 MiB de memória acessível!!!

Mas, como especificar 20 bits de endereços com registradores de 16 bits? Ainda, a maioria dos desenvolvedores (mesmo em linguagem Assembly) estavam mais que acostumados em lidar com endereços de 16 bits nos processadores de 8… A solução foi particionar a memória em “segmentos” de 64 KiB cada. Surgem os “registradores de segmento” (que mais tarde viriam a ser renomeados de “seletores”). A única “desvantagem” é que o endereço linear base tem que ser, necessariamente, alinhado de 16 em 16 bytes (os 4 bits inferiores dos 20 são sempre zero e os registradores de segmento especificam os 16 bits superiores)… Isso causa um possível overlapping entre segmentos, quebrando a vantagem do isolamento entre eles.

Sobre esse “isolamento”, a segmentação tenta matar outro coelho: Em computadores maiores era normal que existisse memórias dedicadas. Uma para o armazenamento das instruções do programa, outra para armazenamento dos dados manipulados, outra para a pilha… Com os seletores pode-se especializar um segmento… Então, CS indica o endereço base do segmento de “código” (Code Segment); DS o de dados (Data Segment) e SS, o de pilha (Stack Segment). E só para dar uma flexibilizada (ou para facilitar o circuito interno do processador) adicionaram ES (Extra data Segment).

Com isso, dependendo do registrador de uso geral que for usado como endereço base (BX ou BP), seleciona-se, automaticamente, DS ou SS, respectivamente.

Outras restrições em relação ao 286 e 386

Em instruções de deslocamento ou rotação não se podia fazer algo como SHL AX,3. Ou se deslocava apenas 1 bit ou tínhamos que usar o registrador CL como operando da contagem do deslocamento. Isso foi flexibilizado, se não me engano, no 286.

Os 386 melhoraram um bocado, “melhorando” o tamanho dos registradores: EAX (de Enhanced AX) torna AX a WORD menos significativa de EAX, que agora tem 32 bits (mas, repare que AH e AL continuam lá, como o desmembramento de AX). E também flexibiliza o modelo de endereçamento. Agora podemos usar qualquer registrador de uso geral como base ou índice, como em MOV AL,[ECX+EDX+1] e, melhor ainda, podemos escalonar o índice, multiplicando-o por 2, 4 ou 8, como em MOV EAX,[ECX+4*EDX+1]… Podemos também usar tanto EBP quanto ESP se quisermos que a base selecione SS automaticamente. E, é claro, temos um conjunto de instruções muito maior.

O 286 também introduziu o modo protegido, melhorado no 386 (que adicionou, também, o modo paginado – para competir com o MC68030, da Motorola).

Para saber mais sobre os 8086 leia meu “Curso de Assembly”, escrito em 1994 para a RBT (baixe aqui). É material velho, mas, em essência, ainda válido.

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.

Processadores de 8 bits: MOS Tech 6502 e Zilog Z80

O primeiro processador que estudei, e no qual consegui colocar minhas mãos, foi o Zilog Z80. Ele foi concebido para ter compatibilidade binária com o 8080 da Intel, mas sofreu diversos avanços significativos. Um exemplo foi a criação do sinal de “interrupção não mascarável” (que só veio a estar disponível nos processadores de Intel à partir do 8085). Outras modificações foram um instruction set mais rico e a adição de dois registradores de índice de 16 bits cada (IX e IY)… O Z80 também tinha dois conjuntos de registradores de uso geral que podiam ser chaveados (nunca usados “ao mesmo tempo”). Isso era útil em rotinas de tratamento de interrupção, já que o conjunto original podia ser preservado facilmente.

No final dos anos 80 coloquei as mãos num Apple ][+, da Microdigital. Como todo Apple ][, ele tinha o processador 6502 da MOS Technologies. Foi o primeiro processador RISC que vi. Diferente do Z80, ele tinha um conjunto realmente restrito, tanto de registradores de uso geral (somente 3, de 8 bits cada: A, X e Y) quanto de instruções… Enquanto o Z80 tinha instruções estendidas, o 6502 só suportava menos que 256 instruções (cada opcode ocupa apenas um byte, seguido do operando).

Para facilitar minha vida aqui e escrever o mínimo possível, vou falar primeiro sobre o 6502, deixando o Z80 para a segunda parte.

MOS Tech 6502:

O 6502 foi muito usado, à partir do final dos anos 70, nos primeiros vídeo games (notoriamente, o ATARI 2600) e até mesmo em arcades. Alguns microcomputadores ficaram bem famosos, como o Apple ][ e o Commodore 64. O motivo foi sua simplicidade.

Atari 2600 e Commodore 64

Existem apenas 3 registradores de uso geral de 8 bits (A, X e Y), os registradores PC (Program Counter), S (Stack pointer) e P (Processor status register) e também um conjunto pequeno de instruções. Há também alguns “atalhos” que não estão presentes em processadores derivados da arquitetura Intel 8080. Por exemplo, ao carregar um registrador os flags de zero (Z) e sinal (S) são automaticamente afetados. Nos Z80, por exemplo, uma operação lógica ou aritmética tem que ser executada para afetar flags (é assim até hoje na arquitetura x86).

As instruções são bem simples e descritivas e temos menos que 256:

opcodes do 6502 (65C02 tem mais!)

Repare como algumas instruções e/ou modos de endereçamento estão agrupados… Isso também facilitava ao desenvolvedor “decorar” os opcodes! Quando aos modos de endereçamento, instruções que exigem algum operando podem tê-lo expresso de diversas formas:

  • Valor imediato: É o caso de instruções como LDA #0, por exemplo, onde o valor 0 é colocado em A. O símbolo # é usado para denotar “imediato”. Sem esse símbolo, estaremos escrevendo um endereço de memória;
  • Página zero: Um endereço de memória no 6502 tem 16 bits de tamanho. O byte superior deste endereço é chamado de página. Podemos omitir a página de um endereço se essa for zero, como em LDA $3F. Aqui $3F é o endereço, em hexadecimal, $003F, mas a instrução só ocupará 2 bytes. Note, também, o uso de $ para denotar valores em hexadecimal;
  • Absoluto: Trata-se do endereço completo de 16 bits, como em LDA $C010.
  • Indexado: É a mesma coisa que o absoluto ou página zero, mas usa um dos registradores, X ou Y, como índice. Como em LDA $40,X ou LDA $C000,Y;
  • Indireto: O operando é um ponteiro (um endereço) de onde será lido o endereço alvo. Como em LDA ($40). Aqui, em $40 e $41 teremos 2 bytes que formam um endereço de 16 bits. Este endereço é que será usado para obter o byte que será colocado em A;
  • Indireto Indexado: Existem dois tipos, um antes e outro após a indireção. LDA ($40),X obtém o endereço lendo 16 bits à partir de $40 e depois soma a X para, só então, usar esse valor como ponteiro. Já LDA ($40,X) adiciona X à zero page $40 para obter o endereço de onde o byte será lido, como no modo indireto normal.

Existem outros argumentos, como os de saltos e chamadas. Neste caso, dependendo da instrução, o operando pode ser um endereço absoluto (16 bits) ou relativo (8 bits). Da mesma forma como acontece nos processadores da família x86, os endereços relativos são adicionados ao valor de PC.

Olhando de novo para a tabela acima temos instruções de carga e armazenamento (por exemplo, LDA carrega [load] A, STA armazena [store] A); adição e subtração sempre usando o flag carry (ADC e SBC); incrementos e decrementos (INA, INX, INY, DEA, DEX e DEY); comparações (CMP, CPX e CPY); operações lógicas (AND, ORA e EOR [mas não existe NOT, que pode ser feito com EOR #$FF!]); outras operações lógicas binárias (BIT, ASL, LSR, ROL e ROR); manipulação de pilha (PHA, PLA, PHP e PLP); manipulação de flags (CLc e SEc) e saltos (JSR, JMP, Bcc, RTS e RTI). Repare que c deverá ser substituído por um dos flags e cc pela comparação desejada: EQ (equal ou Z=1), NE (not equal ou Z=0) MI (minus ou S=1), PL (plus ou S=0), CS (carry set), CC (carry clear), VC e VS (oVerflow clear e oVerflow set). Ah, e existem também as instruções de transferência entre A, X e Y (TAX, TAY, TXA e TYA) e uma instrução especial, BRK, que gerará uma interrupção de “break” (raramente usada).

A versão mais “nova” do 6502, o 65C02, tem alguns instruções a mais, preenchendo o espaço vago na tabela acima. A maioria dos usuários brasileiros desses processadores em microcomputadores, no final dos anos 80, vai se lembrar do TK-2000, quando se fala em 65C02, mas o micro de grande sucesso da Apple que usava esse processador, na época, foi o Apple ][e.

O Apple ][e
Zilog Z80:

O processador Z80 é o primo rico distante da atual arquitetura 80×86. Ele é derivado do antigo 8080, de 8 bits, com um montão de melhorias. Dentre elas, modos de endereçamento melhorados, novas instruções e mais registradores de uso geral.

No antigo 8080 e 8085 tínhamos os registradores A, B, C, D, E, H e L, de 8 bits cada, bem como SP (Stack Pointer), Flags (F) e PC (Program Counter). O Z80 acrescentou um segundo conjunto de uso geral (A', B', C', D', E', H' e L'), bem como os registradores de índice (de 16 bits cada) IX e IY e seus “espelhos” (IX' e IY'), além do espelho dos flags (F'… No 8080 era possível emparelhar apenas os registradores H e L para formar um pseudo registrador chamado M (de “Memória”), que era usado como ponteiro, mas o Z80 permite o emparelhamento BC, DE e no caso de operações de manipulação de pilha, AF.

Não é difícil perceber que a arquitetura 80×86 aproveitou a nomenclatura usada no 8080 de A até D, embora, exceto pelo registrador A, os demais não tinham finalidades bem definidas. No Z80 isso foge um pouco à regra, já que instruções como LDI e LDD (e suas equivalentes com “repetição”), por exemplo, sugerem usos específicos para DE (DE de DEstination).

A matriz do conjunto de instruções do Z80 é grande o suficiente para que fique impraticável mostrá-la aqui de forma reduzida. Você pode vê-la neste link, se quiser.

Assim como no caso do 6502, as operações aritméticas e lógicas são todas feitas tomando como o primeiro operando o registrador A e, geralmente, essas são as únicas instruções que afetam os flags. Assim como o 6502, não existe uma operação NOT, que pode ser efetuada com o XOR contra o valor imediato 0xFF… Mas, diferente do 6502, existem muitas instruções estendidas. Por exemplo, ADD e ADC coexistem, bem como SUB e SBB (onde borrow é o inverso de carry). A quantidade de instruções relacionadas a shifts e rotações é mais rica e temos até instruções para ajustes de valores BCD (Binary Coded Decimal), assim como acontece na família 80×86, exceto no modo x86-64.

No Z80 também é possível carregar um par de registradores com um valor imediato de 16 bits, como em LD HL,0123h, ou via indireção, como em LD HL,(8000h). E, falando em indireção, já que temos um conjunto de registradores de uso geral maior e que podem ser emparelhados, a indireção é mais simples do que a do 6502. A notação entre parênteses simplesmente significa que o que encontra-se entre eles é o endereço onde um byte ou word serão lidos – o esquema de indireção dupla do 6502 é desnecessário.

Existem também instruções especializadas. DJNZ, por exemplo, realiza um salto se, depois de decrementar o registrador B, este não chegou a zero. É como se fosse:

// Equivalente de 'DJNZ addr', em C:
if (--B) goto addr;

As instruções LDI e LDD são instruções de movimentação de blocos. Elas copiam um byte que está apontado por DE para o endereço apontado por HL. A diferença é que LDI incrementa HL e DE e LDD decrementa-os… Mas, também existem LDIR e LDDR, que fazem a mesma coisa, mas usam BC como contador de repetições. Instruções de manipulação de blocos também estão associadas com CP (de ComParação), IN e OUT, na forma de CPI e CPD (e suas equivalentes terminadas em R), acontecendo o mesmo para as demais.

Exemplos de micros com o Z80, no Brasil

Z80 versus 6502:

Durante o final dos anos 70 e até meados dos anos 80 existiu uma verdadeira guerra entre entusiastas de microcomputadores baseados no 6502 (Commodore 64 e Apple ][) e Z80 (onde o maior falatório vinha da turma do TRS-80)… Do ponto de vista dos processadores, o Z80 deveria ganhar de carroçada, mas… O 6502, por ser RISC, tinha um clock reduzido (1 MHz), mas executava código tão rápido quanto o Z80… O Z80, por sua vez, aceitava clock de 4 MHz e, em teoria, poderia ter hardware associado a ele até 4 vezes mais rápido.

Dos micros que usavam o 6502 surgiram softwares sérios que são usados até hoje, pelo menos ao nível conceitual. Por exemplo, a planilha de cálculo surgiu no Apple ][ e chamava-se Visicalc (surgiu em 1979 e foi totalmente escrita em assembly para o 6502).

Essa era a cara do Visicalc.

Originalmente o Visicalc não foi desenvolvido para o Apple ][, mas para o precursor do UNIX (O Multics, mas sob o processador 6502!). Mas foi no Apple ][ que o mundo conheceu a planilha de cálculo eletrônica… Somente em 1983 surgiu uma versão para o PC: O Lotus 1-2-3.

O primeiro filesystem para microcomputadores que tenho notícia, e que suportava nomes “longos”, foi o Apple DOS. Os TRS-80 adotavam o modelo do CP/M-80, usando nomes de 8.3 caracteres (e os drives A: e B:). A diferença é que no DOS dos TRS-80 o separador entre o nome do arquivo e sua extensão era uma ‘/’ e as extensões executáveis tendiam a ser nomeadas ‘/CMD’. O programinha “Dancing Demon” da Radio Shack, se não me engano, era “DEMON/CMD”:

O padrão usado pelo CP/M-80 seguido pela IBM no PC-DOS e pela Microsoft (“criadora” do PC-DOS, que mais tarde viria a ser chamado de MS-DOS), até a criação do Windows NT e a popularização do Windows 95 (já nas versões beta, chamadas de projeto Chicago).

Outra vantagem dos micros com 6502 é que eles eram COLORIDOS. Os TRS-80 jamais foram e os PCs só vieram a sê-lo quando os monitores coloridos começaram ser popularizados. Mas, os Apple ][ e Commodores não precisavam de monitores, bastava uma TV. Eis uma comparação (Karateka, no Apple ][):

Tela de um diretório (catálogo) do Apple DOS

Não me pergunte o significado desses atributos *A, *B, *I e *T porque não me lembro mesmo!

Retornando tipos complexos

Já falei por aqui sobre as diversas convenções de chamada para os modos i386 e x86-64 e uma das coisas que disse é que, no caso do modo x86-64, o registrador RAX é sempre usado como valor de retorno. Seja para retornar um simples int, seja para retornar um ponteiro… Mas, o que acontece se quisermos retornar uma estrutura? Note bem, não um ponteiro para uma estrutura, mas toda ela? Vejamos:

struct vertice_s {
  float x, y, z, w; // Coordinate (homogeneous);
  float nx, ny, nz; // Normal vector;
  float r, g, b, a; // Color;
  float u, v;       // Texture coordinate;
};

struct vertice_s assign(void)
{
  struct vertice_s v;

  v.x = v.y = v.z =
  v.nx = v.ny = v.nz =
  v.r = v.g = v.b =
  v.u = v.v = 0.0f;
  v.w = v.a = 1.0f;

  return v;
}

void assign2(struct vertice_s *p)
{
  p->x = p->y = p->z =
  p->nx = p->ny = p->nz =
  p->r = p->g = p->b =
  p->u = p->v = 0.0f;
  p->w = p->a = 1.0f;
}

Aqui, a função assign() apaentemente retorna toda a estrutura local à função. No outro caso, na função assign2 passamos um ponteiro para uma estrutura e lidamos com ele dentro da função. Supreendentemente, ambas as funções fazem quase exatamente a mesma coisa. Isso pode ser observado obtendo a listagem em assembly:

bits 64

section .rodata
float1: dd 1.0

section .text

global assign
global assign2

assign:
  pxor  xmm0, xmm0
  mov   rax, rdi
  movss xmm1, dword [float1]
  movss dword [rdi+12], xmm1
  movss dword [rdi], xmm0
  movss dword [rdi+4], xmm0
  movss dword [rdi+8], xmm0
  movss dword [rdi+16], xmm0
  movss dword [rdi+20], xmm0
  movss dword [rdi+24], xmm0
  movss dword [rdi+28], xmm0
  movss dword [rdi+32], xmm0
  movss dword [rdi+36], xmm0
  movss dword [rdi+40], xmm1
  movss dword [rdi+44], xmm0
  movss dword [rdi+48], xmm0
  ret

assign2:
  pxor  xmm0, xmm0
  movss dword [rdi+48], xmm0
  movss dword [rdi+44], xmm0
  movss dword [rdi+36], xmm0
  movss dword [rdi+32], xmm0
  movss dword [rdi+28], xmm0
  movss dword [rdi+24], xmm0
  movss dword [rdi+20], xmm0
  movss dword [rdi+16], xmm0
  movss dword [rdi+8], xmm0
  movss dword [rdi+4], xmm0
  movss dword [rdi], xmm0
  movss xmm0, dword [float1]
  movss dword [rdi+40], xmm0
  movss dword [rdi+12], xmm0
  ret

A diferença óbvia é que assign retorna o ponteiro para a estrutura apontada por RDI em RAX, como se tivéssemos passado esse ponteiro para a função! A função gasta o mesmo tempo que a sua irmã, assign2, uma vez que, devido à reordenação automática nos processadores mais modernos (Ivy Bridge em diante, pelo menos), mov rax,rdi provavelmente não gastará ciclo algum.

Repare que o compilador é esperto o suficiente para perceber que se quisermos retornar uma estrutura por valor, ela terá que ser assinalada para algum objeto e esse objeto tem um endereço na memória. Se esse objeto estiver alocado na própria pilha (for uma variável local na função chamadora), RDI apontará para a pilha, caso contrário, para uma região no segmento de dados. Eis um exemplo:

extern struct vertice_s assign(void);

// Não nos interessa a imlpementação dessa função agora!
extern void showvertice(struct vertice_s *);

void f(void)
{
  struct vertice_s v;

  v = assign();
  showvertice(&v);
}

O que criará uma listagem mais ou menos assim:

f:
  sub  rsp,136   ; Aloca espaço para a estrutura.
  mov  rdi,rsp
  call assign
  mov  rdi,rsp
  call showvertice
  add  rsp,136   ; Dealoca o espaço.
  ret

Você obterá uma listagem um pouco maior que essa, dependendo das opções de compilação que usar, mas, em essência, é isso o que o compilador faz.

No modo i386 a coisa não é muito diferente. Lembre-se que no modo x86-64 o primeiro argumento da função é passado no registrador RDI. No caso do modo i386, este argumento é passado na pilha (na convenção cdecl), daí o endereço da estrutura estará apontada por RSP+4.

Em resumo: Não tenha medo de retornar estruturas e uniões por valor, é a mesma coisa que passar o ponteiro da estrutura no primeiro argumento. Mas, a coisa é bem diferente de passar argumentos por valor ou referência. Ao fazer:

void f(struct vertice_s v)
{
  struct vertice t;

  t = v;
  ...
}

Todo o conteúdo de v terá que ser copiado para dentro de t (embora o compilador possa decidir não fazê-lo, dependendo do resto da função!). Mas uma coisa é certa! Todo o conteúdo da estrutura terá que ser copiado para a pilha antes da chamada!

Então, tenha medo de passar argumentos por valor e prefira passá-los por referência (ponteiro)… mas, saiba que esse risco você não corre ao retornar por valor…