Como funciona
Estruturas de dados sem malloc roda toda aula na bancada de código: um Arduino Uno com uma lâmpada vermelha no pino 13, amarela no 12, verde no 11 e um botão no pino 2. Cada aula é um pedaço de um jogo: o botão dispara, as lâmpadas mostram o que a estrutura está fazendo, e o monitor serial imprime o que acontece dentro dela.
Toda aula abre um sketch em C funcionando. Você roda, aperta o botão, lê o monitor serial, depois muda uma linha e roda de novo. As verificações leem a saída serial, então toda linha que uma aula cita é uma que a placa realmente imprimiu.
As aulas
- Buffers circulares: uma fila em um array de tamanho fixo com índices
uint8_tde contagem livre e uma máscara de potência de dois, o que significa estar cheio, umstatic_assertque pega um tamanho errado, e apertos de botão enfileirados para um tick do jogo. - Pools fixos: seis balas criadas em tempo de compilação, uma lista de livres encadeada pelos slots não usados, alocação e liberação em poucas instruções, e uma arma que clique quando o pool acaba.
- Listas intrusivas: inimigos que carregam seu próprio ponteiro
next, movidos entre uma lista de vivos e uma de mortos sem cópias, e remoção com um ponteiro para ponteiro para que a cabeça não precise de caso especial. - Bitsets: dezesseis invasores em um
uint16_t, testar e definir bits, contagem de bits de Kernighan, e atirar no mais baixo comv & (v - 1). - Tabelas de estados: as regras TITLE, PLAYING, PAUSED e GAMEOVER de um jogo como uma tabela
NEXT[state][event]de 12 bytes, ações de entrada, eventos levantados pelos handlers, e uma regra mudada editando uma célula. - Filas de prioridade: um min-heap binário em um array de 8 slots, a árvore sem ponteiros, sift up e sift down, e tempos
uint16_tcomparados pela diferença para sobreviver ao overflow.
O chefão: uma fila de eventos para um jogo
A última aula é Mokxi Invaders. A interrupção do botão empurra eventos FIRE para um anel, um heap de timers empurra eventos MARCH e LAND para o mesmo anel quando chega a hora, e loop() entrega cada evento ao handler do estado atual, vindo de uma tabela de funções. As balas vêm de um pool de três e a onda de oito invasores é um bitset em um byte: 43 bytes de filas no total. Você começa uma onda, atira, limpa, perde uma vida, e liga o modo difícil com uma constante. O botão oscila como um de verdade, e a interrupção mostra como contar um aperto como um tiro.
O que o Uno faz de diferente
- Há apenas 2 KB de SRAM. Um heap que fragmenta pode falhar com muitos bytes livres, então o firmware fixa sua memória em tempo de compilação, onde o relatório de memória da compilação a contabiliza.
- Um ponteiro tem 2 bytes e um
inttem 16 bits, então1 << 15é negativo. Os sketches escrevem1u << npara máscaras de bits. - O AVR não adiciona padding dentro de structs, então
sizeofé a soma dos campos. - Somente os pinos 2 e 3 têm interrupção externa. Tudo que uma interrupção e
loop()tocam évolatile, eloop()desliga as interrupções pelo instante em que empurra para o anel compartilhado. millis()dá a volta a cada 49,7 dias. Comparar tempos pela diferença, nunca com<, continua funcionando através do overflow.
Depois deste curso
Ponto fixo e matemática com inteiros é a outra metade de programar para um chip pequeno: frações, escalonamento e matemática rápida só com inteiros.