👩🏿‍🤝‍👨🏽 👩🏽‍🤝‍👨🏼 🛰️ Portar Quake a iPod Classic 🤾🏼 🌙 🕣

Inicie Quake en iPod Classic ( video ).

TL; DR : Logré ejecutar Quake en un reproductor de MP3. El artículo describe cómo sucedió esto.

Pasé parte del verano pasado en un par de mis cosas favoritas: Rockbox y el juego Quake id Software. ¡Incluso tuve la oportunidad de combinar estos dos pasatiempos portando Quake a Rockbox! ¡Era imposible desear más!

Esta publicación cuenta la historia de cómo funcionó. Esta es una larga historia que se extiende por casi dos años. Además, este es mi primer intento de documentar el proceso de desarrollo, detallado y sin adornos, en contraste con la documentación técnica terminada, que he escrito demasiado en mi vida. El artículo también tendrá detalles técnicos, pero antes que nada intentaré hablar sobre el proceso de pensamiento que condujo a la creación del código.

Por desgracia, ha llegado el momento de decir adiós a Rockbox y Quake, al menos a corto plazo. Durante varios meses, el tiempo libre será un recurso muy escaso para mí, así que antes de apresurarme a trabajar, me apresuro a expresar mis pensamientos.

Rockbox

Rockbox es un curioso proyecto de código abierto, que pasé mucho tiempo pirateando. Lo mejor de esto está escrito en la página web: "Rockbox es firmware gratuito para reproductores de música digital". Así es: creamos un reemplazo completo para el software de fábrica que viene con los reproductores Sandisk Sansa, el iPod de Apple y muchos otros dispositivos compatibles.

No solo nos esforzamos por recrear las funciones del firmware original, sino que también implementamos soporte para extensiones descargables llamadas complementos , pequeños programas que se ejecutan en un reproductor de MP3. Rockbox ya tiene muchos juegos y demostraciones geniales, los más impresionantes probablemente sean los juegos de disparos en primera persona Doom y Duke Nukem 3D ¹. Pero sentí que le faltaba algo.

Quake aparece en el escenario

Quake es un juego de disparos en primera persona totalmente tridimensional. Veamos qué significa eso. Las palabras clave aquí son "completamente tridimensional" . A diferencia de Doom y Duke Nukem 3D, comúnmente conocido como 2.5D (imagine un mapa 2D con un componente de altura opcional), Quake se implementa en 3D completo. Cada vértice y polígono existe en el espacio 3D. Esto significa que los viejos trucos pseudo-3D ya no funcionan, todo se hace en 3D completo. Sin embargo, estaba distraído. En resumen, Quake es una cosa poderosa.

Y Quake no perdona los chistes. Nuestra investigación ha demostrado que Quake "requiere" un procesador x86 con una frecuencia de aproximadamente 100 MHz y FPU, así como aproximadamente 32 MB de RAM. Antes de comenzar a reírse, recuerde que las plataformas de destino para Rockbox no son comparables a lo que John Carmack se centró al escribir el juego: Rockbox incluso funciona en dispositivos con procesadores con una frecuencia de solo 11 MHz y 2 MB de RAM (por supuesto, Quake no debería funcionar en tales dispositivos). Con esto en mente, miré mi colección de reproductores de audio digital que disminuía gradualmente y elegí el más poderoso de los sobrevivientes: Apple iPod Classic / 6G con procesador ARMv5E de 216 MHz y 64 MB de RAM (índice Eindica la presencia de extensiones ARM DSP; más adelante, esto será importante para nosotros). Especificaciones serias, pero apenas hay suficientes para ejecutar Quake.

Puerto

Hay una maravillosa versión de Quake que puede ejecutarse en SDL . Tiene el nombre lógico SDLQuake . Afortunadamente, ya he portado la biblioteca SDL a Rockbox (este es un tema para otro artículo), por lo que preparar Quake para la compilación resultó ser un proceso bastante simple: copie el árbol fuente; make; corregimos errores; enjuague, jabón, repita. Probablemente esté repitiendo un montón de detalles aburridos, pero imagínense mi admiración por poder compilar y vincular con éxito el ejecutable de Quake. Estaba encantado.

"Bueno, ¡cárgalo!" Pensé.

¡Y arrancó! Fui recibido por el hermoso fondo y menú de la consola Quake. Todo perfectamente. ¡Pero tómate tu tiempo! Cuando comencé el juego, algo estaba mal. El nivel de "Introducción" parecía cargar normalmente, pero la posición de aparición del jugador estaba completamente fuera del mapa. Extraño , pensé. Intenté varios trucos, comencé a depurar y splashf, pero todo fue en vano: el error resultó ser demasiado complicado para mí, o me pareció así.

Y esta situación persistió durante varios años. Probablemente valga la pena hablar un poco sobre el momento. El primer intento de lanzar Quake se realizó en septiembre de 2017, después de lo cual me di por vencido, y mi Frankenstein de Quake y Rockbox permaneció en el estante, acumulando polvo, hasta julio de 2019. Habiendo encontrado la combinación perfecta de aburrimiento y motivación, decidí continuar con lo que comencé.

Empecé a depurar. Mi estado de flujo fue tal que no recuerdo prácticamente ningún detalle sobre lo que estaba haciendo, pero intentaré recrear el curso del trabajo.

Descubrí que la estructura de Quake se divide en dos partes principales: el código del motor en C y la lógica de alto nivel del juego en QuakeC, un lenguaje compilado por código de bytes. Siempre traté de mantenerme alejado de QuakeC VM debido al miedo irracional de depurar el código de otra persona. Pero ahora me vi obligado a sumergirme en eso. Recuerdo vagamente la loca sesión de transmisión durante la cual busqué la fuente del error. Después de muchos grep, he encontrado al culpable: pr_cmds.c:PF_setorigin. Esta función recibió un vector tridimensional que establece las nuevas coordenadas del jugador al cargar el mapa, que por alguna razón siempre han sido iguales (0, 0, 0). Hm ...

Retrocedí el flujo de datos y descubrí de dónde provenía: desde la llamada Q_atof(), la función de conversión clásica de cadena a flotante. Y luego me di cuenta: escribí un conjunto de funciones de contenedor que redefinieron Q_atof()el código de Quake, y mi implementación atof()probablemente fue incorrecta. Fue muy fácil arreglarlo. Yo reemplacé mi errónea con la atofcorrecta - la función del código de Quake. ¡Y voilá! El famoso nivel de entrada con tres corredores cargados sin ningún problema, al igual que el "E1M1: The Slipgate Complex". La salida de audio todavía suena como un cortacésped roto, ¡pero aún ejecutamos Quake en el reproductor de MP3!

Por la madriguera del conejo

Este proyecto finalmente se convirtió en una excusa para lo que había estado posponiendo: aprender el lenguaje ensamblador ARM ² .

El problema era el ciclo de mezcla de sonido sensible a la velocidad snd_mix.c(¿recuerda el sonido de una cortadora de césped?).

La función SND_PaintChannelFrom8recibe una matriz de muestras de audio mono de 8 bits y las mezcla en una transmisión estéreo de 16 bits, cuyos canales izquierdo y derecho se escalan por separado en función de dos parámetros enteros. GCC hizo un mal trabajo optimizando la aritmética de saturación, así que decidí hacerlo yo mismo. El resultado me satisfizo por completo.

Aquí está la versión del ensamblador de lo que obtuve (la versión C se presenta a continuación):

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

Aquí hay trucos difíciles que vale la pena explicar. Utilizo la instrucción DSP del qaddprocesador ARM para implementar la adición de saturación de bajo costo, pero qaddsolo funciona con palabras de 32 bits, y el juego usa muestras de sonido de 16 bits. El truco es que primero desplazo las muestras a la izquierda 16 bits; Estoy combinando muestras con qadd; y luego hacer el cambio inverso. Entonces, en una instrucción, hago lo que el CCG tomó siete. (Sí, sería posible prescindir de los hacks si trabajara con ARMv6, que tiene aritmética de saturación empaquetada tipo MMX qadd16, pero, por desgracia, la vida no es tan simple. ¡Además, el hack resultó ser genial!)

Tenga en cuenta también que Leo dos muestras estéreo a la vez (usando palabras ldrystr) para ahorrar un par de ciclos más.

A continuación se muestra una versión C para referencia:

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);
        }
}

Calculé que, en comparación con la versión C optimizada, el número de instrucciones por muestra disminuyó en un 60%. La mayoría de los bucles se guardaron utilizando qaddoperaciones de saturación y memoria de empaque para aritmética.

Conspiración de números "primos"

Aquí hay otro error interesante que encontré en el proceso. En la lista de códigos de ensamblaje, junto a la instrucción bgt(rama "si es mayor que") hay un comentario que bne(rama "si no es igual") no se puede usar debido a un caso límite que ralentiza el programa con un número de muestras igual a 1. Esto conduce a una transferencia cíclica entero encendido 0xFFFFFFFFy un retraso extremadamente largo (que finalmente termina).

Este caso límite se desencadena por un sonido particular, que tiene una longitud de 7325 muestras ³ . ¿Qué tiene de especial 7325? Tratemos de encontrar el resto de su división por cualquier poder de dos:

\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 ...

¿Has notado algo? Es decir, por alguna coincidencia, 7325 es un número "primo" cuando se divide por cualquier potencia de dos. Esto de alguna manera (no entiendo cómo) conduce al hecho de que una matriz de una muestra se transfiere al código de mezcla de sonido, se activa un caso límite y se cuelga.

Pasé al menos un día identificando las causas de este error, como resultado de descubrir que todo se reduce a una instrucción incorrecta. A veces sucede en la vida, ¿verdad?

De despedida

Finalmente empaqueté este puerto como un parche y lo fusioné con la rama principal de Rockbox, donde está hoy. En Rockbox versión 3.15 y posteriores, viene en ensamblajes para la mayoría de las plataformas de destino ARM con ⁴ pantallas a color . Si no tiene una plataforma compatible, puede ver el usuario de demostración 890104 .

En aras de ahorrar espacio, me perdí un par de puntos interesantes. Por ejemplo, hay una condición de carrera que ocurre solo cuando un zombi se rompe en pedazos de carne cuando la velocidad de muestreo es 44.1 kHz. (Este fue el resultado de la secuencia de sonido que intentaba cargar el sonido: una explosión, y el cargador de modelos que intentaba cargar un modelo de carne. Estas dos secciones de código usan una función que usa una variable global). Y también hay muchos problemas de pedido (¡te amo, ARM! ) y un montón de microoptimizaciones de renderizado que creé para extraer algunos fotogramas más del equipo. Pero los dejaré en otro momento. Y ahora es el momento de decir adiós a Quake. Me gustó esta experiencia.

Todo lo mejor, y gracias por el pescado!

Notas

Duke Nukem 3D , runtime Rockbox SDL, . , user890104.
ARM, Tonc: Whirlwind Tour of ARM Assembly — ( GBA) . , ARM Quick Reference Card.
, 100 .
Honestamente, no recuerdo qué plataformas de destino específicas admiten y no admiten Quake. Si tiene curiosidad, vaya al sitio web de Rockbox e intente instalar la compilación para su plataforma. ¡Y hágamelo saber por correo mientras funciona! Las versiones más recientes de Rockbox Utility (desde 1.4.1 y superior) también admiten la instalación automática de la versión shareware de Quake.

Portar Quake a iPod Classic