Запускаем Quake на iPod Classic (видео).

TL;DR: мне удалось запустить Quake на MP3-плеере. В статье описывается, как это произошло.

Часть прошлого лета я потратил на пару своих любимых вещей: Rockbox и игру Quake id Software. Мне даже предоставилась возможность объединить эти два увлечения, портировав Quake на Rockbox! Большего и пожелать было нельзя!

В этом посте рассказывается история о том, как всё получилось. Это долгая история, растянувшаяся почти на два года. Кроме того, это первая моя попытка документирования процесса разработки, подробная и без прикрас, в отличие от готовой технической документации, которой я и так за свою жизнь написал слишком много. В статье будут и технические подробности, но в первую очередь я постараюсь рассказать о мыслительном процессе, который привёл к созданию кода.

Увы, настало время попрощаться с Rockbox и Quake, по крайней мере, на ближайший срок. Несколько месяцев свободное время для меня будет очень дефицитным ресурсом, поэтому прежде, чем навалится работа, я спешу изложить свои размышления.

Rockbox

Rockbox — это любопытный проект с открытыми исходниками, на хакинг которого я потратил уж очень много времени. Лучше всего о нём написано на веб-странице: «Rockbox — это свободное firmware для цифровых музыкальных плееров». Всё верно — мы создали полную замену заводского ПО, поставляемого с плеерами Sandisk Sansa, Apple iPod и множеством других поддерживаемых устройств.

Мы не только стремимся воссоздать функции оригинальной прошивки, но и реализовали поддержку загружаемых расширений, называемых плагинами – небольших программ, выполняемых в MP3-плеере. В Rockbox уже есть множество прекрасных игр и демо, самыми впечатляющими из которых, вероятно, стали шутеры от первого лица Doom и Duke Nukem 3D¹. Но я чувствовал, что в нём чего-то не хватает.

На сцене появляется Quake

Quake — это полностью трёхмерный шутер от первого лица. Давайте разберёмся, что это значит. Самыми ключевыми словами здесь являются «полностью трёхмерный». В отличие от Doom и Duke Nukem 3D, которые обычно называют 2.5D (представьте 2D-карту с дополнительным компонентом высоты), Quake реализован в полном 3D. Каждая вершина и полигон существуют в 3D-пространстве. Это означает, что старые трюки с псевдо-3D больше не работают — всё выполнено в полном 3D. Впрочем, я отвлёкся. Если вкратце, то Quake — это мощная вещь.

Да и шуток Quake не прощает. Наши исследования показали, что для Quake «требуются» процессор x86 с частотой примерно 100 МГц и FPU, а также около 32 МБ ОЗУ. Прежде чем вы начнёте хихикать, вспомните, что целевые для Rockbox платформы несравнимы с тем, на что ориентировался Джон Кармак при написании игры — Rockbox работает даже на устройствах с процессорами с частотой всего 11 МГц и 2 МБ ОЗУ (разумеется, Quake не должен был работать на таких устройствах). Помня об этом, я взглянул на свою постепенно уменьшающуюся коллекцию цифровых аудиоплееров и выбрал самый мощный из выживших: Apple iPod Classic/6G с процессором ARMv5E на 216 МГц и 64 МБ ОЗУ (индекс E обозначает наличие DSP-расширений ARM — позже это будет важно для нас). Серьёзные характеристики, но для запуска Quake их едва хватает.

Порт

Существует чудесная версия Quake, способная работать на SDL. Она имеет вполне логичное название SDLQuake. К счастью, я уже портировал библиотеку SDL в Rockbox (это тема для отдельной статьи), поэтому подготовка Quake к компиляции оказалась довольно простым процессом: копируем дерево исходников; make; исправляем ошибки; смыть, намылить, повторить. Вероятно, здесь я слегка преукрашиваю множество скучных деталей, но просто представьте себе моё восхищение, когда мне удалось успешно скомпилировать и скомпоновать исполняемый файл Quake. Я был в восторге.

«Ну что, загрузим его!», — подумал я.

И он загрузился! Меня встретил красивый фон консоли Quake и меню. Всё отлично. Но не торопитесь! Когда я запустил игру, что-то было не так. Уровень «Introduction», казалось, загружался нормально, но позиция спауна игрока находилась полностью за пределами карты. «Странно», — подумал я. Попробовал разные трюки, запускал отладку и splashf, но всё было тщетно — баг оказался слишком сложным для меня, или мне так казалось.

И такая ситуация сохранялась несколько лет. Вероятно, здесь стоит немного рассказать о сроках. Первая попытка запуска Quake была предпринята в сентябре 2017 года, после чего я сдался, и мой франкенштейн из Quake и Rockbox лежал на полке, собирая пыль, до июля 2019 года. Найдя идеальное сочетание скуки и мотивации, я решил приступить к завершению начатого.

Я занялся отладкой. Моё состояние потока было таким, что я не помню практически никаких подробностей о том, что делал, но постараюсь воссоздать ход работы.

Я обнаружил, что структура Quake разделена на две основные части: код движка на C и высокоуровневая логика игры на QuakeC — компилируемом в байт-код языке. Я всегда старался держаться подальше от QuakeC VM из-за иррационального страха отладки чужого кода. Но теперь я был вынужден погрузиться в него. Я смутно вспоминаю безумный потоковый сеанс, на протяжении которого я искал источник бага. Спустя множество grep, я обнаружил виновника: pr_cmds.c:PF_setorigin. Эта функция получала трёхмерный вектор, задающий новые координаты игрока при загрузке карты, которые по какой-то причине всегда были равны (0, 0, 0). Хм…

Я оттрасировал поток данных и нашёл, откуда он берётся: из вызова Q_atof() — классической функции преобразования из string в float. А потом на меня снизошло озарение: я написал набор функций-обёрток, переопределявших Q_atof() кода Quake, и моя реализация atof(), наверно, была ошибочной. Исправить её было очень легко. Я заменил свою ошибочную atof правильной — функцией из кода Quake. И вуаля! Знаменитый начальный уровень с тремя коридорами загрузился без проблем, как и «E1M1: The Slipgate Complex». Вывод аудио по-прежнему звучит как сломанная газонокосилка, но мы всё-таки запустили Quake на MP3-плеере!

Вниз по кроличьей норе

Этот проект наконец-то стал оправданием того, что я давно откладывал: изучения языка ассемблера ARM².

Проблема заключалась в чувствительном к скорости выполнения цикле микширования звука в snd_mix.c (помните звук газонокосилки?).

Функция SND_PaintChannelFrom8 получает массив из 8-битных звуковых моно-сэмплов и микширует их в 16-битный стереопоток, левый и правый каналы которого масштабируются по отдельности на основании двух целочисленных параметров. GCC паршиво справлялся с оптимизацией арифметики насыщения, поэтому я решил заняться этим сам. Результат меня вполне удовлетворил.

Вот ассемблерная версия того, что у меня получилось (версия на C представлена ниже):

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

Здесь есть хитрые хаки, которые стоит объяснить. Я использую DSP-инструкцию qadd процессора ARM, чтобы реализовать малозатратное сложение насыщения, но qadd работает только с 32-битными словами, а в игре используются 16-битные звуковые сэмплы. Хак заключается в том, что я сначала смещаю сэмплы влево на 16 бит; объединяю сэмплы при помощи qadd; а затем выполняю обратный сдвиг. Так я за одну инструкцию выполняю то, на что GCC требовалось семь. (Да, можно было бы обойтись совсем без хаков, если бы я работал с ARMv6, который имеет MMX-подобную упакованную арифметику насыщения при помощи qadd16, но увы — жизнь не так проста. К тому же, хак получился крутым!)

Заметьте также, что я считываю два стереосэмпла за раз (при помощи работающих со словами ldr и str), чтобы сэкономить ещё пару циклов.

Ниже для справки представлена версия на C:

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

Я подсчитал, что по сравнению с оптимизированной версией на C количество инструкций на сэмпл снизилось на 60%. БОльшая часть циклов была сэкономлена благодаря использованию qadd для арифметики насыщения и упаковке операций с памятью.

Заговор «простых» чисел

Вот ещё один интересный баг, найденный мной в процессе работы. В листинге ассемблерного кода рядом с инструкцией bgt (ветвление «если больше, чем») есть комментарий, что bne (ветвление «если не равно») нельзя использовать из-за пограничного случая, тормозящего программу при количестве сэмплов, равном 1. Это приводит к циклическому переносу integer на 0xFFFFFFFF и чрезвычайно долгой задержке (которая со временем всё-таки завершается).

Этот пограничный случай вызывается одним конкретным звуком, имеющим длину 7325 сэмплов³. Что же особенного в числе 7325? Попробуем найти остаток его деления на любую степень двойки:

$\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…

Заметили что-нибудь? Именно — по какому-то совпадению 7325 является «простым» числом при делении на любую степень двойки. Это каким-то образом (я не понимаю, как именно) приводит к тому, что коду микширования звуков передаётся массив из одного сэмпла, происходит срабатывание пограничного случая и зависание.

Я потратил на выявление причины этого бага не меньше дня, в результате выяснив, что всё сводится к одной неверной инструкции. Иногда в жизни такое бывает, правда?

Прощание

В конечном итоге я упаковал этот порт как патч и слил его с основной веткой Rockbox, где он сегодня и находится. В Rockbox версий 3.15 и выше он поставляется в сборках для большинства целевых платформ ARM с цветными дисплеями⁴. Если у вас нет поддерживаемой платформы, то можете посмотреть демо user890104.

Ради экономии места я пропустил пару интересных моментов. Например, существует состояние гонки, которое возникает только при разрывании зомби на куски мяса, когда частота дискетизации равна 44,1 кГц. (Это стало результатом того, что звуковой поток пытается загрузить звук — взрыв, а загрузчик моделей пытается загрузить модель куска мяса. Эти два участка кода используют одну функцию, использующую одну глобальную переменную.) А ещё есть множество проблем упорядочивания (люблю тебя, ARM!) и куча микрооптимизаций рендеринга, который я создал, чтобы выжать из оборудования ещё несколько кадров. Но их я оставлю на другой раз. А сейчас настала пора попрощаться с Quake — мне понравился этот опыт.

Всего хорошего, и спасибо за рыбу!

Примечания

Duke Nukem 3D стала первой игрой, использующей runtime Rockbox SDL, и она заслуживает отдельного поста. Здесь можно посмотреть её демо, записанное user890104.
Если вам хочется изучить язык ассемблера ARM, то Tonc: Whirlwind Tour of ARM Assembly — это хороший (хотя немного устаревший и ориентированный на GBA) источник. И если уж вам интересно, то распечайте себе ARM Quick Reference Card.
Это был звук, вызываемый подбором аптечкой на 100 очков здоровья.
Честно говоря, я не помню, какие конкретно целевые платформы поддерживают и не поддерживают Quake. Если вам любопытно, то перейдите на сайт Rockbox и попробуйте установить сборку для своей платформы. И сообщите мне на почту, как она работает! Новые версии Rockbox Utility (от 1.4.1 и выше) также поддерживают автоматическую установку shareware-версии Quake.

Портируем Quake на iPod Classic