Programando pra Atari 2600 no Fedora

Como todo cara old school que começou nos 8 bits, eu sempre gostei de estudar e mexer em máquinas antigas ou emuladores. Eu curto a nostalgia de ter instalados no meu Fedora todos os computadores ou sistemas antigos que marcaram a minha vida digital, como o Atari 2600 (através do stella, via RPMFusion Free), o MSX Expert (através do openmsx), o Amiga 500 (através do e-uae, infelizmente via RPMFusion Non-Free) e, claro, um DOSBox pra não perder o costume. Eu costumava ter uma VM rodando FreeDOS, mas acabei me rendendo à comodidade do DOSBox prontinho. Só cuido pra instalar no DOSBox também o NASM e um bom debugger, como o debug do FreeDOS. O Insight também é bem interessante pra demonstrar a execução passo a passo de programas x86 16 bits (que eu insisto em "infligir" aos meus alunos).

Há mais de 10 anos eu tenho vontade de estudar um pouco mais sobre o processador 6502 e sobre programação pro Atari 2600, já que o 6502 era o "outro" processador de 8 bits que "estragou" a infância de muita gente na minha geração. Eu cresci com o MSX e o processador Z80, e nunca tive muito contato com o 6502, enquanto muita gente (principalmente na América do Norte e Europa) cresceu com o 6502 (Apple IIe, Commodore 64, e até o TK 3000 IIe aqui no Brasil) e não conheceu o Z80. A idéia era matar a vontade de conhecer o 6502 e já brincar de programar pro Atari 2600 como um desafio divertido.

Na época em que bateu essa vontade, eu baixei tudo o que achei de referências, datasheets, tutoriais, listas de opcodes e etc sobre 6502 e Atari 2600, imprimi tudo e... guardei. :-( Nunca tive tempo de voltar nesse material, nem de instalar assemblers pra 6502 e realmente meter a mão na massa. Passados uns dez anos, há alguns meses, estávamos conversando sobre realizar oficinas no Hackerspace de Chapecó, e de repente todo aquele contexto acima me veio à cabeça e pensei: é agora que eu me afundo no Atari! :-) Nada melhor do que me jogar de cabeça na responsabilidade de ter que preparar uma oficina pra finalmente "fazer tempo" e colocar a mão na massa. Pois bem, aqui está o primeiro passo.

O ferramental é simples: precisa do emulador stella, um assembler pra família 6502 (o Atari 2600 usa o 6507, uma versão capada do 6502) e um bom editor de textos (vim, claro). O Fedora tem alguns assemblers de 6502, dentre os quais eu escolhi o atasm por ser o que me pareceu mais simples e direto (pra não dizer tosco). Ajuda também baixar o arquivo vcs.h, do tutorial "2600 101" do site AtariAge, com as constantes usadas para identificar mais facilmente os registradores e endereços mágicos do hardware. 20 anos de uso de Software Livre me ensinaram a sempre verificar a licença dos códigos encontrados por aí, e esse vcs.h não tem licença nenhuma, o que indicaria que não poderíamos usá-lo. Mas na boa, é só um monte de constantes que qualquer pessoa poderia digitar por si mesma lendo os manuais da arquitetura, então não tem stress. Na minha interpretação não constitui um trabalho relevante, então é meramente uma comodidade.

O que eu gostei no atasm é que ele vem com um PDF (eu sou da Geração Manual, não da Geração Tutorial) que explica bem as opções de linha de comando, a sintaxe de assembly e diretivas que ele usa, dá exemplos e não é totalmente estranho (alguns outros eram). :-) Usando a opção "-r" o atasm gera uma imagem "raw" (ao invés de um arquivo objeto pra linkar depois), que é exatamente o que precisamos pra criar um "cartucho" do Atari. Uma linha típica pra compilar (tecnicamente é "montar", mas esse termo nunca me soou bem) um arquivo chamado "oficina-1.asm" e gerar um binário "oficina-1.bin" seria "atasm -r -ooficina-1.bin oficina-1.asm". Pra testar dá pra chamar o stella direto, com "stella oficina-1.bin". Mais barbada que isso não tem! :-) Usando a opção "-v" o atasm também gera uma listagem do código compilado na saída padrão. As demais mensagens do atasm vão pra saída de erro padrão, então dá pra capturar a listagem e ainda ver as mensagens no terminal com uma linha tipo "atasm -v -r -ooficina-1.bin oficina-1.asm > oficina-1.lst".

Dei uma refrescada rápida em alguns tutoriais, e rabisquei o meu primeiro código pra Atari 2600, que só faz um scroll contínuo de todas as cores que ele pode gerar, usando uma cor diferente para cada linha na tela (notem que tem copyright e licença, que chique!):

; Primeiro teste de kernel simples pra Atari 2600
; Copyright © 2015 Fábio Olivé Leite
; Licença: Faça o que quiser com este código fonte.

.INCLUDE "vcs.h"

*= $f000

reset    sei          ; Inicializa flags.
         cld
         ldx #255     ; Inicializa pilha.
         txs

         lda #0
zero     sta $00, x   ; Zera a RAM e o TIA.
         dex
         bne zero

start    lda #0       ; Inicia o frame zerando VBLANK ...
         sta VBLANK
         lda #2
         sta VSYNC    ; ... e ligando VSYNC.

         sta WSYNC    ; 3 linhas de VSYNC.
         sta WSYNC
         sta WSYNC

         lda #0       ; Desliga VSYNC.
         sta VSYNC

         ldx #34      ; Espera mais 34 linhas de VBLANK.
vblank0  sta WSYNC    ; Muitos lugares falam em 37 linhas
         dex          ; mas no Stella o 34 alinhou melhor
         bne vblank0  ; com o topo da janela.

         ldx #210     ; Desenha 210 linhas visíveis.
         tya          ; Era pra ser 192, mas 210 fecha até
draw     sta COLUBK   ; embaixo da janela do Stella.
         sta WSYNC    ; Um dia eu testo em um Atari real.
         clc
         adc #1       ; Este "desenho" só vai variando a cor
         dex          ; de fundo nas linhas. :-)
         bne draw

         lda #2       ; Liga VBLANK porque acabou o frame.
         sta VBLANK
         ldx #30      ; São mais 30 linhas de overscan.
ovscan   sta WSYNC    ; Acabou ficando com 277 linhas no frame.
         dex
         bne ovscan

         iny          ; Incrementa a próxima cor inicial.
         jmp start    ; Volta pro início pra começar a próxima tela.

*= $fffa
.WORD    reset        ; NMI
.WORD    reset        ; Reset
.WORD    reset        ; IRQ

Não cabe aqui explicar os detalhes de como se programa pra Atari 2600, ou o porquê do código precisar ser da forma que é. Isso fica pra um próximo artigo, mas adiantando só um detalhe pra assustar: o Atari 2600 só tem "memória de vídeo" pra uma linha da imagem (da TV) de cada vez, então precisamos montar o "frame de vídeo" uma linha por vez durante o retraço horizontal, e processar a lógica do jogo durante o retraço vertical. Seja bem-vindo à programação pra Atari! ;-)

Os cartuchos simples pra Atari têm 4KiB que são mapeados na parte superior da memória do 6507, que na verdade só tem 13 pinos de endereços, embora o seu núcleo 6502 interno tenha todos os 16 pinos, o que faz com que o 6507 enxergue 8 blocos de 8KiB repetidos (que maravilha). O código então geralmente é gerado para começar no endereço 0xF000, e segundo o datasheet do 6502 as três últimas palavras de 16 bits (little-endian) na memória indicam os endereços para os quais o processador vai saltar em caso de NMI (interrupção não mascarável, cujo pino está faltando no 6507), em caso de Reset (ou quando é ligado) e em caso de IRQ (que também não tem no 6507, ô lasquera). Basicamente o costume é repetir nos seis últimos bytes da memória o endereço onde inicia o código do cartucho.

Compilando (tá, montando) o código acima com o atasm, ele nos conta que gerou 71 bytes de código de máquina. São 65 bytes de código mais os 6 dos endereços no final, e o binário gerado fica com exatos 4096 bytes, como deveria ser.

$ atasm -v -r -ooficina-1.bin oficina-1.asm > oficina-1.lst
ATasm 1.07 (A mostly Mac65 compatible 6502 cross-assembler)
Pass 1: Success. (0 warnings)
Pass 2:

Assembly successful
  Compiled 71 bytes (~0k)
  Writing raw binary image:
    f000-ffff

Compiled to binary file 'oficina-1.bin'

É legal olhar a listagem gerada pelo atasm, pra ver os opcodes e os endereços.

00:F0  78     reset    sei         ; Inicializa flags.
01:F0  D8              cld
02:F0  A2 FF           ldx #255    ; Inicializa pilha.
04:F0  9A              txs
05:F0  A9 00           lda #0
07:F0  95 00  zero     sta $00, x  ; Zera a RAM e TIA.
09:F0  CA              dex
0A:F0  D0 FB           bne zero
0C:F0  A9 00  start    lda #0      ; Inicia o frame zerando VBLANK ...
0E:F0  85 01           sta VBLANK
10:F0  A9 02           lda #2
12:F0  85 00           sta VSYNC   ; ... e ligando VSYNC.
14:F0  85 02           sta WSYNC   ; 3 linhas de VSYNC.
16:F0  85 02           sta WSYNC
18:F0  85 02           sta WSYNC
1A:F0  A9 00           lda #0      ; Desliga VSYNC.
1C:F0  85 00           sta VSYNC
1E:F0  A2 22           ldx #34     ; Espera mais 34 linhas de VBLANK.
20:F0  85 02  vblank0  sta WSYNC   ; Muitos lugares falam em 37 linhas
22:F0  CA              dex         ; mas no Stella o 34 alinhou melhor
23:F0  D0 FB           bne vblank0 ; com o topo da janela.
25:F0  A2 D2           ldx #210    ; Desenha 210 linhas visíveis.
27:F0  98              tya         ; Era pra ser 192, mas 210 fecha até
28:F0  85 09  draw     sta COLUBK  ; embaixo da janela do Stella.
2A:F0  85 02           sta WSYNC   ; Um dia eu testo em um Atari real.
2C:F0  18              clc
2D:F0  69 01           adc #1      ; Este "desenho" só vai variando a cor
2F:F0  CA              dex         ; de fundo nas linhas. :-)
30:F0  D0 F6           bne draw
32:F0  A9 02           lda #2      ; Liga VBLANK porque acabou o frame.
34:F0  85 01           sta VBLANK
36:F0  A2 1E           ldx #30     ; São mais 30 linhas de overscan.
38:F0  85 02  ovscan   sta WSYNC   ; Acabou ficando com 277 linhas no frame.
3A:F0  CA              dex
3B:F0  D0 FB           bne ovscan
3D:F0  C8              iny         ; Incrementa a próxima cor inicial.
3E:F0  4C 0C F0        jmp start   ; Volta pro início do frame.

FA:FF  00 F0  .WORD    reset       ; NMI
FC:FF  00 F0  .WORD    reset       ; Reset
FE:FF  00 F0  .WORD    reset       ; IRQ

Confirmando que temos um "cartucho" corretamente montado, agora é só chamar o stella e testar (basta rodar "stella oficina-1.bin"). A emocionante :-D captura de tela abaixo mostra que deu certo!

Agora que meu primeiro teste funcionou, estou fadado a passar o resto dos meus minutos livres tentando fazer algo que preste, ou melhor, tentando programar um excitante jogo onde um quadrado verde tenta pegar uma bola azul enquanto foge de um borrão amarelo, ou algo do tipo. ;-) Talvez ao invés de continuar postando no blog eu comece a escrever um material legal sobre 6502, sobre Atari 2600 e contendo exemplos cada vez mais elaborados lá no xap-hacks.org. Por mais que o Inglês seja uma obrigação básica pra nós que trabalhamos com tecnologia, eu sinto que criar material original e de qualidade em Português Brasileiro cobrindo conceitos fundamentais como Arquitetura de Computadores, especialmente usando processadores que existem de verdade ao invés de processadores "didáticos" que só existem no papel, é um esforço que vale a pena.

Vamos ver no que dá! :-)

Programando um Arduino em estilo old-school

Talvez o nome mais apropriado fosse "Programando um Arduino da maneira errada" ou "... da maneira mais difícil", mas o fato é que desde que comecei a brincar com Arduinos eu queria "meter a mão na massa" e programar ele à moda antiga, sem IDEs e tal, usando assembly e pior, codificando os opcodes binários manualmente. Sei lá, acho que é cacoete de quem começou com os processadores de 8bits e acostumou a "assemblar" seus próprios programas. Eu sei bem que o objetivo do Projeto Arduino não é esse, que o código não será compatível com outras placas, que será incrivelmente mais difícil, etc etc etc. Não interessa, um fuçador tem que fuçar. :-)

Para começar, a gente precisa olhar a plaquinha Arduino (neste caso, a Uno) pelo que ela realmente é: uma forma simplificada e prática de usar o microcontrolador ATmega328P. Então o próximo passo é ir lá no site da Atmel e baixar o datasheet do microcontrolador (aqui em versão completa, são 36MB), e depois disso baixar também a referência do conjunto de instruções da família AVR (à qual o Atmega328P pertence). Com estes dois documentos, já conseguimos entender bem como é que o bichinho funciona, e como são as suas instruções. Imprima e leia algumas vezes.

O próximo passo é instalar as ferramentas que serão usadas para gravar o programa na plaquinha e para manipular os arquivos de código. O bom é que elas são as mesmas ferramentas usadas pela interface IDE do Arduino: o avrdude para gravar na flash do ATmega328 e as GNU binutils (cross-compilando para AVR). Se você tem o ambiente do Arduino instalado (no Fedora, sudo yum install arduino) está tudo pronto. Uma maneira legal de começar a sujar as mãos com bits crus devagarinho é compilar um programa de exemplo qualquer na interface do Arduino, e depois ir no /tmp olhar os arquivos intermediários no diretório de build. Arrisque-se a digitar "avr-objdump -d foobar.elf" e olhar o código gerado pelo compilador. :-)

Para o meu primeiro teste eu quis fazer um pouco mais do que o tradicional Hello World do Arduino, que é piscar um led. Então resolvi fazer um programa que pisque 8 leds em zigue-zague, usando 8 pinos digitais. Decidi usar os primeiros 8 pinos, D0 a D7, porque eles são todos bits da mesma porta D para o ATmega328, o que facilita a programação. O programa basicamente seta um bit em um registrador e o envia para a porta, esperando um delay rápido e depois deslocando o registrador um bit para a direita e escrevendo na porta, em laço até zerar o registrador. Depois disso, recarrega um valor com um bit setado no registrador e faz o mesmo deslocando para a esquerda, até zerar (quando o bit "cair fora" do registrador:-).

Li algumas páginas relacionadas a sintaxe padrão de assembly AVR, e depois resolvi fazer tudo manualmente, em um formato livre. Então abri o vim e criei este arquivo, que chamei de teste.asm.

; Teste de programação do Arduino "assemblando" manualmente os opcodes
; DDRD = 0a
; PORTD = 0b
; Os opcodes precisam ser convertidos para little-endian no .bin
addr    opcode    instruction
0000    ef0f    ldi r16, 0xff    ; programa porta D como saídas
0001    b90a    out DDRD, r16
0002    e000    ldi r16, 0x00    ; limpa registradores de contagem dos delays
0003    e010    ldi r17, 0x00
0004    e440    ldi r20, 0x40    ; inicio
0005    b94b    out PORTD, r20   ; loop1, led para a direita
0006    e024    ldi r18, 0x04
0007    9503    inc r16          ; delay1
0008    f7f1    brne delay1
0009    9513    inc r17
000a    f7e1    brne delay1
000b    952a    dec r18
000c    f7d1    brne delay1
000d    9546    lsr r20
000e    f7b1    brne loop1
000f    e042    ldi r20, 0x02
0010    b94b    out PORTD, r20   ; loop2, led para a esquerda
0011    e024    ldi r18, 0x04
0012    9503    inc r16          ; delay2
0013    f7f1    brne delay2
0014    9513    inc r17
0015    f7e1    brne delay2
0016    952a    dec r18
0017    f7d1    brne delay2
0018    0f44    lsl r20
0019    f7b1    brne loop2
001a    cfe5    rjmp inicio

Claro que eu não saí digitando tudo direto. Eu comecei cada linha com dois tabs, e comecei a listar as instruções aos poucos, pensando em como ia usar os registradores. Acabei decidindo usar os registradores "altos" (r16 em diante) para poder usar a instrução LDI (Load Immediate), que só manipula de r16 a r31. Quando eu tiver mais experiência com o conjunto de instruções acho que vou começar a usar mais os registradores baixos também. Depois de prontas as instruções, preenchi a primeira coluna com os endereços, e então fui aos poucos olhando cada uma das instruções na referência do AVR Instruction Set.

Aqui cabem duas observações interessantes:

1. O AVR é um processador RISC de 8 bits, e os opcodes têm um tamanho fixo de 16 bits (algumas instruções precisam 32, mas isso fica como tema para casa). Embora na referência eles sejam demonstrados como números binários de 16 bits, na hora de gravar na flash eles precisam ser convertidos para little-endian. Minha primeira tentativa de criar o arquivo "binário" com o código acabou dando errado, e tive que digitar tudo de novo invertendo os bytes de cada opcode. :-)
2. Embora cada instrução ocupe 2 bytes, o Program Counter do AVR aponta para instruções, e não para bytes. Isso significa que os offsets de branches e jumps são offsets em instruções, e não em bytes. Então para pular 4 instruções pra cima, se usa um offset de -4, mesmo que na verdade se esteja pulando 8 bytes para trás. Pra completar a confusão, o objdump mostra o disassembly com endereços de bytes, e ele mostra os opcodes invertidos, já em formato little-endian.

Feita a tradução dos mnemônicos para os opcodes binários (e calcular os offsets de branches contando em hexa em complemento de 2 nos dedos), agora a tarefa é digitar todos os opcodes em um arquivo, que será o "binário compilado" desse nosso esforço manual. Eu uso o hexedit, que é simples e direto, mas qualquer editor hexadecimal serve. Lembre-se de digitar os opcodes convertendo para little-endian. Fazendo um hexdump do "código compilado" teste.bin fica assim:

$ hexdump -C teste.bin
00000000  0f ef 0a b9 00 e0 10 e0  40 e4 4b b9 24 e0 03 95  |........@.K.$...|
00000010  f1 f7 13 95 e1 f7 2a 95  d1 f7 46 95 b1 f7 42 e0  |......*...F...B.|
00000020  4b b9 24 e0 03 95 f1 f7  13 95 e1 f7 2a 95 d1 f7  |K.$.........*...|
00000030  44 0f b1 f7 e5 cf 00 00  00 00 00 00 00 00 00 00  |D...............|

No total são 54 bytes, para 27 instruções de máquina. Eu completei com uns zeros no final, só para fechar 64 bytes e ficar tudo alinhado. :) O opcode do NOP em AVR é 0x0000 então tá tranquilo. :-)

Um passo interessante, agora, é transformar esse arquivo contendo opcodes de AVR em um arquivo que o avr-objdump entenda e possa desassemblar, para que a gente confira o código e principalmente os offsets de branches, que o objdump nos ajuda a entender. Não é um passo necessário, mas é bom pra ter certeza que o código que montamos está realmente fazendo o que pretendemos que ele faça. Eu não consegui achar uma maneira de convencer o objdump a desmontar o binário "cru" diretamente, então usei o objcopy para transformá-lo em um ELF comum:

$ avr-objcopy -I binary -O elf32-avr --rename-section .data=.text,contents,code teste.bin \
    teste.elf
$ avr-objdump -d teste.elf

teste.elf:     file format elf32-avr

Disassembly of section .text:

00000000 _binary_teste_bin_start:
   0:    0f ef           ldi    r16, 0xFF    ; 255
   2:    0a b9           out    0x0a, r16    ; 10
   4:    00 e0           ldi    r16, 0x00    ; 0
   6:    10 e0           ldi    r17, 0x00    ; 0
   8:    40 e4           ldi    r20, 0x40    ; 64
   a:    4b b9           out    0x0b, r20    ; 11
   c:    24 e0           ldi    r18, 0x04    ; 4
   e:    03 95           inc    r16
  10:    f1 f7           brne    .-4          ; 0xe _binary_teste_bin_start+0xe
  12:    13 95           inc    r17
  14:    e1 f7           brne    .-8          ; 0xe _binary_teste_bin_start+0xe
  16:    2a 95           dec    r18
  18:    d1 f7           brne    .-12         ; 0xe _binary_teste_bin_start+0xe
  1a:    46 95           lsr    r20
  1c:    b1 f7           brne    .-20         ; 0xa _binary_teste_bin_start+0xa
  1e:    42 e0           ldi    r20, 0x02    ; 2
  20:    4b b9           out    0x0b, r20    ; 11
  22:    24 e0           ldi    r18, 0x04    ; 4
  24:    03 95           inc    r16
  26:    f1 f7           brne    .-4          ; 0x24 _binary_teste_bin_start+0x24
  28:    13 95           inc    r17
  2a:    e1 f7           brne    .-8          ; 0x24 _binary_teste_bin_start+0x24
  2c:    2a 95           dec    r18
  2e:    d1 f7           brne    .-12         ; 0x24 _binary_teste_bin_start+0x24
  30:    44 0f           add    r20, r20
  32:    b1 f7           brne    .-20         ; 0x20 _binary_teste_bin_start+0x20
  34:    e5 cf           rjmp    .-54         ; 0x0 _binary_teste_bin_start
    ...

Legal, com isso já consigo verificar que eu calculei os opcodes corretamente, e que meus offsets de branches e jumps estavam certos. Agora só falta gravar no Arduino. Para isso, temos que converter o binário em um arquivo no formato Intel Hex, com extensão .hex. Este é o formato usado pelo avrdude, que é quem conversa com o bootloader do Arduino e grava o nosso programa lá. Os comandos abaixo deram conta do recado:

$ avr-objcopy -I binary -O ihex teste.bin teste.hex
$ avrdude -P /dev/ttyUSB0 -p ATmega328P -b 115200 -c arduino -U flash:w:teste.hex:i

O avrdude gera bastante saída na tela, dá pra ir acompanhando os passos da gravação. Note que eu usei um Garagino com uma porta serial FTDI que o acompanha, e ela é detectada como /dev/ttyUSB0. Uma plaquinha Arduino Uno, por exemplo, é detectada como /dev/ttyACM0, então o comando acima deverá ser adaptado. Feita a programação e montado o circuito, voilà! Está tudo funcionando como esperado, em apenas 27 instruções de código!

Estou muito feliz de finalmente ter escovado estes bits, que estavam me esperando desde que comprei a primeira Arduino Uno. Só não tinha dado tempo ainda de pensar num projetinho simples porém não tão trivial, sentar e começar a codar. Levei horas codificando os opcodes manualmente, e é claro que não pretendo mais fazer isso. Meus próximos testes serão utilizando o GNU Assembler para facilitar as coisas. Estou commitando estes e outros testes com Arduino neste repositório no github, para facilitar a publicação e utilização pelos interessados.

Ah, antes que me esqueça: desde que a gente não sobrescreva o bootloader do Arduino, que ocupa os últimos 512 bytes da flash, vai continuar funcionando tudo normalmente, e a placa continua compatível com a IDE do Arduino. Continua sendo possível criar e gravar um programa pelas vias normais, usando a IDE e clicando botõezinhos. :-) Se o nosso programa tiver menos do que 32256 bytes não vai sobrescrever o bootloader e tá tudo certo.

Update 2014-06-20: Na verdade nem precisa converter o arquivo binário para ihex. O avrdude também pode ler arquivos binários sem formato, especificando a opção "raw". Agora mesmo eu mudei um pouco o padrão dos leds e escrevi o teste.bin direto usando "-U flash:w:teste.bin:r". O ":r" no final é que indica o tipo, sendo 'i' Intel Hex, e 'r' raw. Só o que se perde com isso é a possibilidade de especificar o endereço de carga. O ihex pode especificar endereços, para o caso de querermos gravar um conteúdo na flash a partir de um ponto específico. O raw sempre vai ser gravado a partir de 0 na flash. Bom saber que nem precisa fazer a dança do objcopy, embora seja mais reconfortante fazer um objdump e confirmar o código antes de gravar. :-)

Ótimo livro: CODE do Charles Petzold

No início de janeiro eu estava pra sair de férias, e perguntei para os meus colegas que livros eles sugeriam para ler. Queria alguma coisa técnica porém leve, que fosse menos bit e mais história. A sugestão do mestre Rafael Aquini não poderia ter sido melhor: CODE, do Charles Petzold. Ao terminar de ler o livro eu cheguei à conclusão que lê-lo equivale a ter nascido na década de 70 e estudado computadores de 8 bits. Sério, é muito bom mesmo!

Vale muito a pena mesmo para quem já domina o lado técnico, pois a contextualização histórica que ele apresenta, na medida certa, enriquece a compreensão de qualquer um a cerca dos bits e seus significados. Não tem como ler este livro e não enxergar os bits. Eles estão lá, nus e crus, esperando que o leitor os apreenda, e de repente toda a computação digital faz sentido.

Você sabia que as raízes da computação binária remontam ao século 19? Os bits são os mesmos, só mudou o substrato. A grande sacada veio no início do século 20, com o Claude Shannon, usando tecnologia de telégrafos do século 19. Eu já tinha lido alguma coisa dele quando estudei algoritmos de compressão, mas agora compreendo o papel muito mais fundamental que ele teve na Grande Sacada de unir no sistema de numeração binário a aritmética, a lógica e a sua expressão automatizada por meio de circuitos elétricos (na época eletromecânicos). A partir daí a tecnologia só se miniaturizou e se tornou mais rápida, mas o princípio é o mesmo.

Claude Shannon agora figura entre Ken Thompson, Dennis Ritchie, Donald Knuth e muitos outros no meu panteão pessoal da Computação. :-)

Números divertidos: 0xAAAAAAAA e seu irmão 0x55555555

Ontem estava começando a ler um livro, chamado Hacker's Delight (hacker no sentido original, fuçador e escovador de bits), meio desconfiado porque ele me foi indicado por um colega que é engenheiro de compiladores (bichos raros e bizarros). Ficava pensando se eu realmente iria gostar de ler sobre centenas de operações curiosas e micro-algoritmos otimizados em um assembly RISC hipotético e aritmética modular (claro que sim).

Eis que no prefácio o livro já me cativou, falando sobre as correções do Guy Steele e sobre os fatores do número hexadecimal 0xAAAAAAAA, que são 2, 5, 17, 257 e 65537. Quem fuça em bits desde pequeno já deve ter ficado intrigado pelo 65537 e pelo 257, e talvez também pelos outros (mas o 2 meio que sobra, veremos o porquê). Observando um pouco os números, e brincando com os comandos factor e bc, eis que percebi que realmente os números 0xAA... e 0x55... (em 8, 16 e 32 bits) são números muito bonitos e divertidos. :)

Comecemos pelo 0xAAAAAAAA mencionado no livro. Sua representação em binário é 10101010101010101010101010101010, e em octal é 25252525252 (que inclusive é um palíndromo). Em decimal dá um 2863311530 chato. Mas agora olhemos os seus fatores 2, 5, 17, 257 e 65537:

    2 = 4 ^ 0 + 1

    5 = 4 ^ 1 + 1

   17 = 4 ^ 2 + 1

  257 = 4 ^ 4 + 1

65537 = 4 ^ 8 + 1

Se não fosse pelo 2 (chato), dava ainda pra fazer outra série mais bonita:

    5 = 2 ^ 2 ^ 1 + 1

   17 = 2 ^ 2 ^ 2 + 1

  257 = 2 ^ 2 ^ 3 + 1

65537 = 2 ^ 2 ^ 4 + 1

Em binário, o 2 fica chato, mas os demais ficam bonitos:

    2 = 10

    5 = 101

   17 = 10001

  257 = 100000001

65537 = 10000000000000001

O legal é que, como este número divertido 0xAAAAAAAA tem 2 (chato) como fator, fica óbvio que teremos outro número bonito e divertido retirando o 2 dos fatores (dividindo por 2, ou deslocando um bit pra direita): 0x55555555. Como tiramos o 2 da história, os fatores ficam 5, 17, 257 e 65537, que são todos números bonitos e dão séries contínuas de exponenciação como visto acima. :)

0x55555555 em binário é 01010101010101010101010101010101 e em octal fica um pouco menos bonito que o seu irmão: 12525252525. Em decimal fica um desinteressante 1431655765. E pra fechar, olhem que massa: as versões menores destes números de 32bits também continuam interessantes, e a série de fatores deles fica interessantíssima!

    fatores de 0x55 = 5 17

  fatores de 0x5555 = 5 17 257

fatores de 0x555555 = 5 17 257 65537

O mesmo acontece com 0xAA, 0xAAAA e 0xAAAAAA, somente adicionando o 2 inicial. :) Pena que indo pra 64bits aí já entram outros fatores menos divertidos.

Update: Acabaram as reuniões do dia. Mais diversão com o bc pra ver que a série continua bem legal:

$ bc
bc 1.06.95
...

2 ^ 2 ^ 5 + 1
4294967297
 

2 ^ 2 ^ 6 + 1
18446744073709551617

obase=16
 

5 * 17 * 257 * (2 ^ 2 ^ 5 + 1)
555500005555
 

2 * 5 * 17 * 257 * (2 ^ 2 ^ 5 + 1)
AAAA0000AAAA
 

5 * 17 * 257 * (2 ^ 2 ^ 5 + 1) * (2 ^ 2 ^ 6 + 1)
5555000055550000555500005555
 

2 * 5 * 17 * 257 * (2 ^ 2 ^ 5 + 1) * (2 ^ 2 ^ 6 + 1)
AAAA0000AAAA0000AAAA0000AAAA
... e assim por diante. :)