Doom запустили на «движке» из регулярных выражений: вся вычислительная машина уместилась в одной текстовой строке размером 96,6 МБ, эмулирующей процессор и память
На отрисовку одного кадра уходит около 180 секунд и почти 14 миллионов подстановок символов
Из-за запредельной медлительности игровой процесс сравнили с «шахматами по переписке, но с дробовиком»
Внутри работает 32-разрядный виртуальный процессор на 544 правилах замены, а доступ к памяти организован через бинарное дерево, свёрнутое в регулярное выражение
Запуск оригинального Doom 1992 года на самом неожиданном оборудовании давно превратился в неофициальное состязание среди программистов. Игру уже видели на тостерах, на зарядных устройствах Anker и даже на тесте на беременность. Не отстаёт и «программная» ветвь этого соревнования: энтузиасты умудряются запускать шутер на самом странном программном обеспечении, какое только можно вообразить. Свежий пример — разработчик под псевдонимом 4RH1T3CT0R7 (Артём Лыткин) заставил Doom работать на одних лишь регулярных выражениях.
Источник изображения — оригинальный источник
Что такое регулярные выражения и почему это звучит как проклятие
Опытные разработчики, скорее всего, поёжились, прочитав саму формулировку. Дело в том, что регулярные выражения (regex) — это утилитарный язык для поиска и замены текста внутри программ. Они невероятно мощны, но их синтаксис часто называют «только для записи»: со стороны он выглядит как бессмыслица. Например, конструкция /.*(\d{4}).*/g найдёт «2026» во фразе «игровые новости 2026 года». Регулярные выражения бывают чрезвычайно сложными: в них есть условные операторы, хитрые переходы по символам и правила замены. А это, помимо прочего, означает, что формально они удовлетворяют всем техническим требованиям к полноценному языку программирования.
Компьютер внутри одной текстовой строки
Отталкиваясь от этого свойства, автор проекта собрал 96,6-мегабайтную текстовую строку, внутри которой живёт целая машина. В этой же строке обычным текстом лежат регистры виртуального процессора, оперативная память, буфер кадра (видеовыход), игровые данные WAD, сама программа Doom и подсистема ввода-вывода. Область памяти разбита на зоны с метками-разделителями: таблицы поиска, плоское ОЗУ, программа, буфер кадра, данные игры и «редкая» память для старших адресов. За всё отвечает небольшой 32-разрядный виртуальный процессор с внутренним названием RVM-1, реализованный ровно 544 правилами замены — их набор фиксирован и защищён контрольной суммой SHA-256 ещё до старта.
Работает это так: на каждом шаге срабатывает первое подходящее правило, и ровно одно его срабатывание считается одним «тактом» машины. Никакого отдельного интерпретатора и никакой арифметики за пределами правил нет — если удалить набор подстановок, останется просто безжизненный текстовый файл. Сложение, к слову, выполнено через восемь опережающих проверок по таблице полного сумматора на 512 записей, а перенос разряда «протаскивается» между проверками через группы захвата.
Медленно почти до тепловой смерти Вселенной
Как несложно догадаться, всё это работает чудовищно медленно: по словам разработчика, на один кадр игрового вывода уходит около 180 секунд. Каждый такой кадр требует почти 14 миллионов замен (точнее — 13 994 067 для кадра уровня E1M1). Но, во-первых, оно действительно работает, а во-вторых, картинка получается побайтно идентичной тому, что выдаёт настоящий Doom. Играть тоже можно — управление есть, — но, как метко заметил сам автор, это ближе к «шахматам по переписке, но с дробовиком», чем к шутеру на реакцию.
Проверке уделено особое внимание, чтобы исключить любые «поддавки». Тот же набор команд параллельно выполняет эталонный эмулятор на Python, а набор тестов требует, чтобы строка совпадала с состоянием эмулятора побайтно после каждой подстановки. Готовые кадры дополнительно сверяются с изображением из штатной сборки Doom по хешу SHA-256 — и хеши совпадают. Для надёжности автор просчитал не один кадр, а сотню подряд (около 1,25 миллиарда замен), и все они сошлись с оригиналом.
Главный трюк — доступ к памяти
Самое изящное место всей конструкции — обращение к памяти. Правило перепрыгивает строго заданное число символов вглубь зоны ОЗУ, причём длина этого прыжка собирается из цифр адреса при помощи пустых битовых меток и условных переходов. По сути это бинарное дерево, расписанное на языке регулярных выражений: машина не сканирует все 96 МБ в поисках нужной ячейки, а попадает точно на неё. Тот же приём используется и при выборке очередной инструкции по счётчику команд.
Сам движок Doom добрался до этого «процессора» через порт doomgeneric, скомпилированный через набор инструментов ELVM — по тропе, которую ранее проложил проект BFDoom (там Doom запускали на языке Brainfuck). Игровые данные doom1.wad — это оригинальные условно-бесплатные файлы id Software, а весь проект унаследовал лицензию GPL от исходного кода Doom.
От 7 подстановок в секунду до 80 тысяч
Отдельная история — производительность. Первая рабочая сборка выдавала всего 7 подстановок в секунду; при таком темпе одни только последние 295 тысяч замен кадра считались бы 12 часов. Затем последовала череда оптимизаций: тот самый «цифровой» переход по дереву вместо линейного сканирования программы, отказ от лишнего копирования неизменной части строки и переход к плоской памяти. В итоге скорость выросла на четыре порядка — до примерно 80 000 замен в секунду на ядро (использован движок PCRE2 с JIT-компиляцией). Финальные прогоны распределяют работу сразу по пяти машинам, и кадр выходит за те самые три минуты.
Как попробовать самому
Исходный код проекта doom-regex выложен в открытый доступ, там же можно скачать демонстрационную сборку и запустить машину у себя. Демоверсия вполне играбельна: WASD или стрелки отвечают за движение, Ctrl — выстрел, пробел открывает двери, а каждое нажатие попадает во входной файл, откуда машина забирает его своей командой ввода. На сайте проекта работу этой regex-машины можно наблюдать и визуально, и в текстовом виде — за тем, как правила по одному «дорисовывают» кадр, завораживающе наблюдать, примерно как когда-то за работой программ дефрагментации диска. Стоит отметить и контекст: ранее на регулярных выражениях уже собирали шахматы (проект Regex Chess), но именно полноценную игру, да ещё и с полной по Тьюрингу схемой, на циклической замене текста, похоже, не запускал никто.
