🛌🏼 🐼 🚢 Portage de Quake sur iPod Classic ♀️ 👨‍🎨 🐚

Lancez Quake sur iPod Classic ( vidéo ).

TL; DR : J'ai réussi à exécuter Quake sur un lecteur MP3. L'article décrit comment cela s'est produit.

J'ai passé une partie de l'été dernier sur quelques-unes de mes choses préférées: Rockbox et le jeu Quake id Software. J'ai même eu l'occasion de combiner ces deux hobbies en portant Quake sur Rockbox! Il était impossible d'en souhaiter plus!

Ce message raconte comment cela a fonctionné. Il s'agit d'une longue histoire qui s'étend sur près de deux ans. De plus, c'est ma première tentative de documenter le processus de développement, détaillé et non verni, contrairement à la documentation technique finie, que j'ai trop écrite dans ma vie. L'article contiendra également des détails techniques, mais j'essaierai tout d'abord de parler du processus de réflexion qui a conduit à la création du code.

Hélas, le moment est venu de dire au revoir à Rockbox et à Quake, du moins à court terme. Pendant plusieurs mois, le temps libre sera une ressource très rare pour moi, donc avant de me précipiter au travail, je m'empresse d'exprimer mes pensées.

Rockbox

Rockbox est un curieux projet open source, que j'ai passé beaucoup de temps à pirater. La meilleure chose à ce sujet est écrite sur la page Web: "Rockbox est un firmware gratuit pour les lecteurs de musique numérique." C'est vrai - nous avons créé un remplacement complet pour le logiciel d'usine fourni avec les lecteurs Sandisk Sansa, l'iPod d'Apple et de nombreux autres appareils pris en charge.

Nous nous efforçons non seulement de recréer les fonctions du firmware d'origine, mais également de mettre en œuvre la prise en charge des extensions téléchargeables appelées plug - ins - petits programmes exécutés sur un lecteur MP3. Rockbox a déjà de nombreux jeux et démos, dont les plus impressionnants sont probablement les tireurs à la première personne Doom et Duke Nukem 3D ¹. Mais je sentais qu'il lui manquait quelque chose.

Quake apparaît sur scène

Quake est un jeu de tir à la première personne entièrement en trois dimensions. Voyons ce que cela signifie. Les mots clés ici sont «entièrement tridimensionnels» . Contrairement à Doom et Duke Nukem 3D, communément appelé 2.5D (imaginez une carte 2D avec un composant de hauteur en option), Quake est implémenté en 3D complet. Chaque sommet et polygone existe dans l'espace 3D. Cela signifie que les vieilles astuces pseudo-3D ne fonctionnent plus - tout se fait en full 3D. Cependant, j'étais distrait. En bref, Quake est une chose puissante.

Et Quake ne pardonne pas les blagues. Nos recherches ont montré que Quake «nécessite» un processeur x86 avec une fréquence d'environ 100 MHz et un FPU, ainsi qu'environ 32 Mo de RAM. Avant de commencer à rire, rappelez-vous que les plates-formes cibles de Rockbox ne sont pas comparables à ce sur quoi John Carmack s'est concentré lors de l'écriture du jeu - Rockbox fonctionne même sur des appareils avec des processeurs avec une fréquence de seulement 11 MHz et 2 Mo de RAM (bien sûr, Quake ne devrait pas fonctionner sur ces appareils). Dans cet esprit, j'ai regardé ma collection de lecteurs audio numériques progressivement décroissante et j'ai choisi le plus puissant des survivants: Apple iPod Classic / 6G avec processeur ARMv5E 216 MHz et 64 Mo de RAM (index Eindique la présence d'extensions ARM DSP - plus tard, cela sera important pour nous). Spécifications sérieuses, mais il y a à peine assez pour exécuter Quake

Port

Il existe une merveilleuse version de Quake qui peut fonctionner sur SDL . Il a le nom logique SDLQuake . Heureusement, j'ai déjà porté la bibliothèque SDL sur Rockbox (c'est un sujet pour un autre article), donc préparer Quake pour la compilation s'est avéré être un processus assez simple: copier l'arborescence source; make; nous corrigeons les erreurs; rincer, savonner, répéter. Je suis probablement ici pour repeindre un grand nombre de détails ennuyeux, mais imaginez mon admiration pour avoir réussi à compiler et à lier l'exécutable Quake. Je fus ravi.

"Eh bien, chargez-le!" J'ai pensé.

Et ça a démarré! J'ai été accueilli par le magnifique arrière-plan et le menu de la console Quake. Tout parfaitement. Mais prenez votre temps! Quand j'ai commencé le jeu, quelque chose n'allait pas. Le niveau «Introduction» semblait se charger normalement, mais la position d'apparition du joueur était complètement hors de la carte. Étrange , ai-je pensé. J'ai essayé diverses astuces, commencé le débogage et splashf, mais c'était en vain - le bogue s'est avéré trop compliqué pour moi, ou il me semblait comme ça.

Et cette situation a persisté pendant plusieurs années. Cela vaut probablement la peine de parler du timing. La première tentative de lancement de Quake a eu lieu en septembre 2017, après quoi j'ai abandonné, et mon Frankenstein de Quake et Rockbox reposait sur l'étagère, ramassant la poussière, jusqu'en juillet 2019. Ayant trouvé la combinaison parfaite de l'ennui et de la motivation, j'ai décidé de poursuivre l'achèvement de ce que j'avais commencé.

J'ai commencé le débogage. Mon état du flux était tel que je ne me souviens pratiquement pas de détails sur ce que je faisais, mais je vais essayer de recréer le déroulement du travail.

J'ai trouvé que la structure de Quake est divisée en deux parties principales: le code moteur en C et la logique de haut niveau du jeu dans QuakeC, un langage compilé en bytecode. J'ai toujours essayé de rester loin de QuakeC VM en raison de la peur irrationnelle de déboguer le code de quelqu'un d'autre. Mais maintenant, j'ai été obligé de m'y plonger. Je me souviens vaguement de la session de streaming insensée au cours de laquelle j'ai cherché la source du bug. Après beaucoup grep, j'ai trouvé le coupable: pr_cmds.c:PF_setorigin. Cette fonction a reçu un vecteur tridimensionnel qui définit les nouvelles coordonnées du joueur lors du chargement de la carte, qui pour une raison quelconque ont toujours été égales (0, 0, 0). Hm ...

J'ai fait un retour en arrière du flux de données et trouvé d'où il venait: de l'appel Q_atof()- la fonction de conversion classique de chaîne en flottant. Et puis la perspicacité m'est venue: j'ai écrit un ensemble de fonctions d'encapsuleur qui a redéfini Q_atof()le code Quake, et mon implémentation atof()était probablement fausse. Il était très facile de le réparer. J'ai remplacé mon erreur par la atoffonction correcte du code Quake. Et le tour est joué! Le fameux niveau d'entrée avec trois couloirs chargés sans aucun problème, tout comme le «E1M1: The Slipgate Complex». La sortie audio sonne toujours comme une tondeuse à gazon cassée, mais nous avons quand même lancé Quake sur le lecteur MP3!

Dans le trou de lapin

Ce projet est finalement devenu une excuse pour ce que j'avais repoussé: l'apprentissage du langage d'assemblage ARM ² .

Le problème était le cycle de mixage du son sensible à la vitesse snd_mix.c(rappelez-vous le son d'une tondeuse à gazon?).

La fonction SND_PaintChannelFrom8reçoit un tableau d'échantillons audio mono 8 bits et les mélange en un flux stéréo 16 bits, dont les canaux gauche et droit sont mis à l'échelle séparément en fonction de deux paramètres entiers. GCC a fait un travail moche en optimisant l'arithmétique de saturation, alors j'ai décidé de le faire moi-même. Le résultat m'a complètement satisfait.

Voici la version assembleur de ce que j'ai obtenu (la version C est présentée ci-dessous):

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

Il y a ici des astuces difficiles à expliquer. J'utilise l'instruction DSP du qaddprocesseur ARM pour implémenter l'ajout de saturation à faible coût, mais qaddcela ne fonctionne qu'avec des mots 32 bits, et le jeu utilise des échantillons sonores 16 bits. Le hack est que je décale d'abord les échantillons sur 16 bits; Je combine des échantillons avec qadd; puis faites le décalage inverse. Donc, dans une instruction, je fais ce que le CCG a pris sept. (Oui, il serait possible de se passer de hacks si je travaillais avec ARMv6, qui a une arithmétique de saturation remplie de type MMX avec qadd16, mais hélas, la vie n'est pas si simple. De plus, le hack s'est avéré être cool!)

Notez également que J'ai lu deux échantillons stéréo à la fois (en utilisant des mots ldretstr) pour enregistrer quelques cycles supplémentaires.

Ci-dessous est une version C pour référence:

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

J'ai calculé que, par rapport à la version C optimisée, le nombre d'instructions par échantillon a diminué de 60%. La plupart des boucles ont été enregistrées à l'aide d'opérations de qaddsaturation et de mémoire de compression pour l'arithmétique.

Complot de nombres "premiers"

Voici un autre bug intéressant que j'ai trouvé dans le processus. Dans la liste des codes d'assemblage, à côté de l'instruction bgt(branche «si plus que»), il y a un commentaire qui bne(branche «si pas égal») ne peut pas être utilisé en raison d'un cas limite qui ralentit le programme avec le nombre d'échantillons égal à 1. Cela conduit à un transfert cyclique entier sur 0xFFFFFFFFet un délai extrêmement long (qui finit éventuellement).

Ce cas limite est déclenché par un son particulier, ayant une longueur de 7325 échantillons ³ . Quelle est la particularité du 7325? Essayons de trouver le reste de sa division par n'importe quelle puissance de deux:

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

Avez-vous remarqué quelque chose? A savoir - par une coïncidence, 7325 est un nombre "premier" lorsqu'il est divisé par une puissance de deux. Cela (en quelque sorte (je ne comprends pas comment)) conduit au fait qu'un tableau d'un échantillon est transféré dans le code de mixage audio, un cas limite est déclenché et se bloque.

J'ai passé au moins une journée à identifier les causes de ce bogue, car j'ai découvert que tout se résumait à une mauvaise instruction. Parfois, cela arrive dans la vie, non?

Séparation

J'ai finalement empaqueté ce port en tant que patch et l' ai fusionné avec la branche principale de Rockbox, où il se trouve aujourd'hui. Dans Rockbox version 3.15 et versions ultérieures, il est fourni en assemblages pour la plupart des plates-formes cibles ARM avec ⁴ écrans couleur . Si vous ne disposez pas d'une plate-forme prise en charge, vous pouvez voir la démo user890104 .

Pour économiser de l'espace, j'ai raté quelques points intéressants. Par exemple, il existe une condition de concurrence qui ne se produit que lorsqu'un zombie se brise en morceaux de viande lorsque la fréquence d'échantillonnage est de 44,1 kHz. (C'était le résultat du flux sonore essayant de charger le son - une explosion, et le chargeur de modèle essayant de charger un morceau de modèle de viande. Ces deux sections de code utilisent une fonction qui utilise une variable globale.) Et il y a aussi beaucoup de problèmes de commande (je t'aime, ARM! ) et un tas de microoptimisations de rendu que j'ai créées pour extraire quelques images supplémentaires de l'équipement. Mais je vais les laisser une autre fois. Et maintenant, il est temps de dire au revoir à Quake - j'ai aimé cette expérience.

Meilleurs vœux et merci pour le poisson!

Remarques

Duke Nukem 3D , runtime Rockbox SDL, . , user890104.
ARM, Tonc: Whirlwind Tour of ARM Assembly — ( GBA) . , ARM Quick Reference Card.
, 100 .
Honnêtement, je ne me souviens pas quelles plateformes cibles spécifiques prennent en charge et ne prennent pas en charge Quake. Si vous êtes curieux, rendez-vous sur le site Web de Rockbox et essayez d'installer la version pour votre plate-forme. Et faites le moi savoir par mail car ça marche! Les nouvelles versions de Rockbox Utility (à partir de 1.4.1 et supérieures) prennent également en charge l'installation automatique de la version shareware de Quake.

Portage de Quake sur iPod Classic