Aulas e o jogo de aprendizado

Estruturas de dados sem malloc

Os contêineres que firmware de verdade usa, cada byte fixado na compilação, aplicados em um pequeno jogo de nave espacial em um Uno.

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

  1. Buffers circulares: uma fila em um array de tamanho fixo com índices uint8_t de contagem livre e uma máscara de potência de dois, o que significa estar cheio, um static_assert que pega um tamanho errado, e apertos de botão enfileirados para um tick do jogo.
  2. 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.
  3. 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.
  4. Bitsets: dezesseis invasores em um uint16_t, testar e definir bits, contagem de bits de Kernighan, e atirar no mais baixo com v & (v - 1).
  5. 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.
  6. 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_t comparados 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 int tem 16 bits, então 1 << 15 é negativo. Os sketches escrevem 1u << n para 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, e loop() 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.