Запуск Doom 1992 года на самом неожиданном оборудовании стал, пожалуй, самым популярным неофициальным соревнованием среди программистов. Мы видели эту игру на чём угодно — от тостеров до зарядного устройства Anker и даже теста на беременность. Предприимчивые кодеры умудряются запускать её и на максимально странном программном обеспечении, и совсем недавно Артём Лыткин заставил её работать с помощью регулярных выражений.
Разработчики в аудитории, наверное, в ужасе отшатываются — это предложение точно проклято. Понимаете, регулярные выражения (regex) — это утилитарный язык, используемый в программах для поиска и замены текста. Они невероятно мощны, но часто говорят, что их синтаксис — «только для записи», поскольку выглядит как тарабарщина. Например, /.*(\d{4}).*/g найдёт «2026» во фразе «Tom’s Hardware 2026 articles». Они могут быть чрезвычайно сложными, включая условные операторы, хитроумные переходы по символам и правила подстановки. Однако это также означает, что они удовлетворяют всем техническим требованиям для того, чтобы быть языком программирования.
Используя эти возможности, Лыткин создал текстовую строку размером 96 МБ, содержащую разделы для регистров виртуального процессора, немного оперативной памяти, видеовыхода (framebuffer), данные WAD игры, а также ввод-вывод и прочие детали. После запуска регулярное выражение начинает сопоставлять текст и заменять символы в строке, имитируя числа в каждом регистре процессора, затем обращаясь к «памяти» и записывая в неё, и так далее.
Как вы можете представить, это чудовищно медленно. Лыткин говорит, что создание одного кадра игрового вывода занимает около 180 секунд. Для каждого из них требуется почти 14 миллионов замен, однако (а) это реально работает и (б) Лыткин утверждает, что вывод побайтно идентичен реальному выводу Doom. В игру даже можно управлять с клавиатуры, но, как красноречиво показывает отважный кодер, играть в неё «ближе к шахматам по переписке с дробовиком, чем к динамичному шутеру».
Особо гиковские разработчики будут рады узнать, как Лыткин написал часть доступа к памяти: по сути, это бинарное дерево, прыгающее от «ветви» к ветви с использованием стандартных инструкций переходов по символам регулярных выражений. Это позволяет избежать многократного сканирования всех 96 МБ текста только для того, чтобы найти маркер «#M», обрамляющий его. Лыткин отмечает, что задача заключалась не в том, можно ли это сделать, а в том, будет ли игра работать «до тепловой смерти Вселенной», поскольку движок выполняет 80 000 текстовых замен в секунду.
Репозиторий doom-regex находится здесь, а демо-версию можно скачать и запустить на своём компьютере. На сайте проекта показано, как regex-машина работает в визуальном и текстовом форматах — за этим завораживающе наблюдать. Это сильно напоминает время, которое мы, будучи детьми, проводили, глядя на работу утилит дефрагментации.
Всегда имейте в виду, что редакции могут придерживаться предвзятых взглядов в освещении новостей.
Автор – Bruno Ferreira
