🌕 👍 💬 Portando o Quake para o iPod Classic 🍄 🧘🏼 💴

Inicie o Quake no iPod Classic ( vídeo ).

TL; DR : Eu consegui rodar o Quake em um MP3 player. O artigo descreve como isso aconteceu.

Passei parte do verão passado em algumas das minhas coisas favoritas: Rockbox e o jogo Quake id Software. Eu até tive a oportunidade de combinar esses dois hobbies portando Quake no Rockbox! Era impossível desejar mais!

Este post conta a história de como funcionou. Esta é uma longa história que se estende por quase dois anos. Além disso, esta é minha primeira tentativa de documentar o processo de desenvolvimento, detalhado e não envernizado, em contraste com a documentação técnica finalizada, que escrevi demais na minha vida. O artigo também terá detalhes técnicos, mas antes de tudo, tentarei falar sobre o processo de pensamento que levou à criação do código.

Infelizmente, chegou a hora de dizer adeus a Rockbox e Quake, pelo menos no curto prazo. Por vários meses, o tempo livre será um recurso muito escasso para mim. Portanto, antes de correr para o trabalho, apresso-me a expressar meus pensamentos.

Rockbox

O Rockbox é um curioso projeto de código aberto, que passei muito tempo invadindo. A melhor coisa está escrita na página da web: "Rockbox é um firmware gratuito para tocadores de música digital". É isso mesmo - criamos um substituto completo para o software de fábrica que acompanha os players Sandisk Sansa, o Apple iPod e muitos outros dispositivos suportados.

Não estamos apenas nos esforçando para recriar as funções do firmware original, mas também implementamos o suporte a extensões para download chamadas plug - ins - pequenos programas em execução em um MP3 player. O Rockbox já possui muitos jogos e demos incríveis, dos quais os mais impressionantes são provavelmente os jogos de tiro em primeira pessoa Doom e Duke Nukem 3D ¹. Mas eu senti que algo estava faltando nele.

Terremoto aparece no palco

Quake é um jogo de tiro em primeira pessoa totalmente tridimensional. Vamos ver o que isso significa. As palavras-chave aqui são "totalmente tridimensionais" . Ao contrário de Doom e Duke Nukem 3D, comumente referido como 2.5D (imagine um mapa 2D com um componente opcional de altura), o Quake é implementado em 3D completo. Cada vértice e polígono existe no espaço 3D. Isso significa que os antigos truques pseudo-3D não funcionam mais - tudo é feito em 3D completo. No entanto, eu estava distraído. Em suma, Quake é uma coisa poderosa.

E Quake não perdoa piadas. Nossa pesquisa mostrou que o Quake “requer” um processador x86 com uma frequência de aproximadamente 100 MHz e uma FPU, além de cerca de 32 MB de RAM. Antes de começar a rir, lembre-se de que as plataformas de destino do Rockbox não são comparáveis ao que John Carmack focou ao escrever o jogo - o Rockbox até funciona em dispositivos com processadores com uma frequência de apenas 11 MHz e 2 MB de RAM (é claro, o Quake não deve funcionar em tais dispositivos). Com isso em mente, observei minha coleção cada vez menor de tocadores de áudio digital e escolhi o mais poderoso dos sobreviventes: Apple iPod Classic / 6G com processador ARMv5E de 216 MHz e 64 MB de RAM (índice Eindica a presença de extensões ARM DSP - mais tarde isso será importante para nós). Especificações sérias, mas mal existem o suficiente para rodar o Quake.

Porta

Existe uma versão maravilhosa do Quake que pode ser executada em SDL . Tem o nome lógico SDLQuake . Felizmente, eu já portuei a biblioteca SDL para o Rockbox (este é um tópico para outro artigo), portanto, preparar o Quake para compilação acabou sendo um processo bastante simples: copie a árvore de origem; make; nós corrigimos erros; enxágüe, sabão, repita. Provavelmente estou aqui repintando muitos detalhes chatos, mas imagine minha admiração por poder compilar e vincular com êxito o executável do Quake. Fiquei encantada

"Bem, carregue-o!" Eu pensei.

E inicializou! Fui recebido pelo lindo plano de fundo e menu do console do Quake. Tudo perfeitamente. Mas não se apresse! Quando eu comecei o jogo, algo estava errado. O nível de "Introdução" parecia carregar normalmente, mas a posição de reprodução do jogador estava completamente fora do mapa. Estranho , pensei. Tentei vários truques, comecei a depurar e splashf, mas foi em vão - o bug acabou sendo muito complicado para mim, ou me pareceu assim.

E essa situação persistiu por vários anos. Provavelmente vale uma pequena conversa sobre o momento. A primeira tentativa de lançar o Quake foi feita em setembro de 2017, após o que eu desisti, e meu Frankenstein do Quake e Rockbox estava na prateleira, coletando poeira, até julho de 2019. Tendo encontrado a combinação perfeita de tédio e motivação, decidi prosseguir com a conclusão do que comecei.

Comecei a depuração. Meu estado de fluxo era tal que não me lembro de praticamente nenhum detalhe sobre o que estava fazendo, mas tentarei recriar o curso do trabalho.

Eu descobri que a estrutura do Quake é dividida em duas partes principais: o código do mecanismo em C e a lógica de alto nível do jogo no QuakeC, uma linguagem compilada por bytecode. Eu sempre tentei ficar longe da QuakeC VM devido ao medo irracional de depurar o código de outra pessoa. Mas agora fui forçado a mergulhar nele. Lembro-me vagamente da sessão de streaming insana durante a qual procurei a fonte do bug. Depois de muitos grep, eu encontrei o culpado: pr_cmds.c:PF_setorigin. Essa função recebeu um vetor tridimensional que define as novas coordenadas do jogador ao carregar o mapa, que por algum motivo sempre foram iguais (0, 0, 0). Hum ...

Voltei atrás no fluxo de dados e descobri de onde ele vinha: da chamada Q_atof()- a função de conversão clássica de string para float. E então me ocorreu o insight: escrevi um conjunto de funções de invólucro que redefiniram Q_atof()o código do Quake e minha implementação atof()provavelmente estava errada. Foi muito fácil corrigi-lo. I substituído meu errônea com a atofcorreta - função a partir do código Quake. E pronto! O famoso nível de entrada, com três corredores carregados sem problemas, assim como o "E1M1: The Slipgate Complex". A saída de áudio ainda soa como um cortador de grama quebrado, mas ainda executamos o Quake no MP3 player!

No buraco do coelho

Este projeto finalmente se tornou uma desculpa para o que eu estava adiando: aprender a linguagem assembly ARM ² .

O problema era o ciclo de mistura do som sensível à velocidade snd_mix.c(lembra o som de um cortador de grama?).

A função SND_PaintChannelFrom8recebe uma matriz de amostras de áudio mono de 8 bits e as mistura em um fluxo estéreo de 16 bits, cujos canais esquerdo e direito são dimensionados separadamente com base em dois parâmetros inteiros. O GCC fez um péssimo trabalho otimizando a aritmética da saturação, então decidi fazer isso sozinho. O resultado me satisfez completamente.

Aqui está a versão do montador do que recebi (a versão C é apresentada abaixo):

SND_PaintChannelFrom8:
        ;; r0: int true_lvol
        ;; r1: int true_rvol
        ;; r2: char *sfx
        ;; r3: int count

        stmfd sp!, {r4, r5, r6, r7, r8, sl}

        ldr ip, =paintbuffer
        ldr ip, [ip]

        mov r0, r0, asl #16                 ; prescale by 2^16
        mov r1, r1, asl #16

        sub r3, r3, #1                      ; count backwards

        ldrh sl, =0xffff                    ; halfword mask

1:
        ldrsb r4, [r2, r3]                  ; load input sample
        ldr r8, [ip, r3, lsl #2]                ; load output sample pair from paintbuffer
                                ; (left:right in memory -> right:left in register)
        ;; right channel (high half)
        mul r5, r4, r1                      ; scaledright = sfx[i] * (true_rvol << 16) -- bottom half is zero
        qadd r7, r5, r8                     ; right = scaledright + right (in high half of word)
        bic r7, r7, sl                      ; zero bottom half of r7

        ;; left channel (low half)
        mul r5, r4, r0                      ; scaledleft = sfx[i] * (true_rvol << 16)
        mov r8, r8, lsl #16                 ; extract original left channel from paintbuffer
        qadd r8, r5, r8                     ; left = scaledleft + left

        orr r7, r7, r8, lsr #16                 ; combine right:left in r7
        str r7, [ip, r3, lsl #2]                ; write right:left to output buffer
        subs r3, r3, #1                         ; decrement and loop

        bgt 1b                          ; must use bgt instead of bne in case count=1

        ldmfd sp!, {r4, r5, r6, r7, r8, sl}

        bx lr

Existem truques complicados aqui que merecem ser explicados. Uso a instrução DSP do qaddprocessador ARM para implementar a adição de baixo custo da saturação, mas qaddfunciona apenas com palavras de 32 bits e o jogo usa amostras de som de 16 bits. O truque é que eu mudo as amostras pela primeira vez para 16 bits; Estou combinando amostras com qadd; e depois faça o turno reverso. Então, em uma instrução, faço o que o GCC levou sete. (Sim, seria possível ficar sem hacks, se eu trabalhasse com o ARMv6, que possui aritmética de saturação semelhante a MMX qadd16, mas infelizmente a vida não é tão simples. Além disso, o hack acabou sendo legal!)

Observe também que Eu li duas amostras estéreo de cada vez (usando palavras ldrestr) para salvar mais alguns ciclos.

Abaixo está uma versão C para referência:

void SND_PaintChannelFrom8 (int true_lvol, int true_rvol, signed char *sfx, int count)
{
        int     data;
        int             i;

        // we have 8-bit sound in sfx[], which we want to scale to
        // 16bit and take the volume into account
        for (i=0 ; i<count ; i++)
        {
            // We could use the QADD16 instruction on ARMv6+
            // or just 32-bit QADD with pre-shifted arguments
            data = sfx[i];
            paintbuffer[2*i+0] = CLAMPADD(paintbuffer[2*i+0], data * true_lvol); // need saturation
            paintbuffer[2*i+1] = CLAMPADD(paintbuffer[2*i+1], data * true_rvol);
        }
}

Calculei que, comparado à versão C otimizada, o número de instruções por amostra diminuiu 60%. A maioria dos loops foi salva usando qaddoperações de memória de saturação e empacotamento para aritmética.

Conspiração de números "primos"

Aqui está outro bug interessante que encontrei no processo. Na lista de códigos de montagem, ao lado da instrução bgt(ramificação “se for maior que”), há um comentário que bne(ramificação “se não for igual”) não pode ser usado devido a um caso limítrofe que atrasa o programa com o número de amostras igual a 1. Isso leva a uma transferência cíclica inteiro ativado 0xFFFFFFFFe um atraso extremamente longo (que termina eventualmente).

Esse caso limítrofe é acionado por um som específico, com um comprimento de 7325 amostras ³ . O que há de tão especial no 7325? Vamos tentar encontrar o restante de sua divisão com qualquer potência de dois:

\begin{aligned} 7325 & \equiv 1 & (\mod 2) \\ 7325 & \equiv 1 & (\mod 4) \\ 7325 & \equiv 5 & (\mod 8) \\ 7325 & \equiv 13 & (\mod 16) \\ 7325 & \equiv 29 & (\mod 32) \\ 7325 & \equiv 29 & (\mod 64) \\ 7325 & \equiv 29 & (\mod 128) \\ 7325 & \equiv 157 & (\mod 256) \\ 7325 & \equiv 157 & (\mod 512) \\ 7325 & \equiv 157 & (\mod 1024) \\ 7325 & \equiv 1181 & (\mod 2048) \\ 7325 & \equiv 3229 & (\mod 4096) \end{aligned}

$\begin{align*} 7325 &\equiv 1 &\pmod{2} \\ 7325 &\equiv 1 &\pmod{4} \\ 7325 &\equiv 5 &\pmod{8} \\ 7325 &\equiv 13 &\pmod{16} \\ 7325 &\equiv 29 &\pmod{32} \\ 7325 &\equiv 29 &\pmod{64} \\ 7325 &\equiv 29 &\pmod{128} \\ 7325 &\equiv 157 &\pmod{256} \\ 7325 &\equiv 157 &\pmod{512} \\ 7325 &\equiv 157 &\pmod{1024} \\ 7325 &\equiv 1181 &\pmod{2048} \\ 7325 &\equiv 3229 &\pmod{4096} \end{align*}$

5, 13, 29, 157 ...

Você notou alguma coisa? Ou seja - por alguma coincidência, 7325 é um número "primo" ao dividir por qualquer potência de dois. De alguma forma (não entendo como) leva ao fato de que uma matriz de uma amostra é transferida para o código de mixagem de som, um caso limítrofe é acionado e trava.

Passei pelo menos um dia identificando as causas desse bug, como resultado de descobrir que tudo se resume a uma instrução errada. Às vezes acontece na vida, certo?

Parting

Acabei empacotando essa porta como um patch e a mesclando com a filial principal do Rockbox, onde está hoje. No Rockbox versão 3.15 e posterior, ele vem em montagens para a maioria das plataformas de destino do ARM com ⁴ telas coloridas . Se você não possui uma plataforma suportada, poderá ver a demo user890104 .

Por uma questão de economia de espaço, perdi alguns pontos interessantes. Por exemplo, existe uma condição de corrida que ocorre apenas quando um zumbi parte em pedaços de carne quando a taxa de amostragem é 44,1 kHz. (Esse foi o resultado do fluxo de som tentando carregar o som - uma explosão, e o carregador de modelos tentando carregar um modelo de carne. Essas duas seções de código usam uma função que usa uma variável global.) E também existem muitos problemas de pedidos (amo você, ARM! ) e várias microoptimizações de renderização que criei para extrair mais alguns quadros do equipamento. Mas vou deixá-los outra hora. E agora é hora de dizer adeus ao Quake - gostei dessa experiência.

Tudo de bom, e obrigado pelo peixe!

Notas

Duke Nukem 3D , runtime Rockbox SDL, . , user890104.
ARM, Tonc: Whirlwind Tour of ARM Assembly — ( GBA) . , ARM Quick Reference Card.
, 100 .
Sinceramente, não me lembro quais plataformas de destino específicas suportam e não suportam o Quake. Se você estiver curioso, acesse o site do Rockbox e tente instalar a compilação para sua plataforma. E avise-me pelo correio , pois funciona! As versões mais recentes do Rockbox Utility (da 1.4.1 e superior) também oferecem suporte à instalação automática da versão shareware do Quake.

Portando o Quake para o iPod Classic