Толкаем байты, или Простейший эмулятор своими руками

Есть хороший способ начать свой путь в системное программирование: написать эмулятор и ассемблер для какого-нибудь простого процессора. Сегодня популярностью в узких кругах пользуются fantasy consoles: виртуальные игровые приставки в ретродухе. Я расскажу, как создать свой вариант виртуальной приставки BytePusher с процессором, имеющим всего одну команду. Если вы интересуетесь системным программированием, любите изучать необычные архитектуры процессоров или цените произведения из области демосцены, то эта статья для вас.

Почему BytePusher 

Самая популярная виртуальная ретроприставка — PICO-8, для которой разработаны сотни игр. Нюанс, правда, в том, что PICO-8 и подобные ей предназначены не для желающих стать системными программистами, а для любителей писать ретроигры с использованием языка Lua и стилизованного 8-битного API ввода/вывода.

Другое дело — CHIP-8. Самостоятельная реализация этой игровой виртуальной машины вполне по силам начинающим. Готовый эмулятор можно протестировать на множестве игр. Есть у CHIP-8 и недостатки. Виртуальная машина придумана в 70-х и это чувствуется. Зачем начинающему, к примеру, возиться с BCD-представлением чисел или флагом переноса? Да и графика на CHIP-8 весьма невзрачна, но какой она еще может быть с монохромным экраном 64×32?

Теперь я, наконец, перехожу к главной теме статьи — виртуальной приставке BytePusher. Эта приставка меня крайне впечатлила! Но обо всем по порядку.

Эмулятор процессора

С графическими возможностями у BytePusher все в порядке: разрешение 256×256 и 8-битный цвет. «Сердце» приставки — 8-битный процессор с архитектурой ByteByteJump (BBJ). Насколько сложно написать эмулятор этого процессора начинающему? Несложно. Даже больше скажу: нужно очень постараться, чтобы не суметь этого сделать!

Предвижу скептический настрой у читателя! Хорошо! Вот полная реализация эмулятора BBJ сразу на двух языках.

Версия на Python:

def get3(mem, i):     return int.from_bytes(mem[i:i + 3], 'big')  def sim(pc, mem, cycles):     for _ in range(cycles):         mem[get3(mem, pc + 3)] = mem[get3(mem, pc)]         pc = get3(mem, pc + 6)

Версия на C:

#define GET3(mem, i) (mem[i] << 16 | mem[i + 1] << 8 | mem[i + 2])  void sim(int pc, uint8_t *mem, int cycles) {     for (int i = 0; i < cycles; i++) {         mem[GET3(mem, pc + 3)] = mem[GET3(mem, pc)];         pc = GET3(mem, pc + 6);     } }

Функция sim выполняет cycles раз команды процессора начиная с адреса pc. Можно заметить, что здесь используется память mem, массив байт, но ни стека, ни регистров не наблюдается. Действительно, перед нами архитектура память-память: значения извлекаются из памяти и записываются в нее же, безо всяких промежуточных мест хранения.

В функции get3 ничего особенного нет, она просто считывает из памяти три байта и преобразует их в одно значение. Поскольку в байте 8 бит, а байтов у нас три, то получается 3 × 8 = 24 бита результата. Эти 24-битные значения используются в BBJ в качестве адресов памяти. Нехитрый подсчет дает общий объем адресуемой процессором памяти: 2²⁴ = 16777216 байт или 16 Мбайт. Довольно много для приставки в ретростиле, согласитесь. Но в случае BBJ — это не роскошь, как мы убедимся в дальнейшем.

Чувствую нетерпение читателя. Действительно, я рассуждаю о каких-то второстепенных вещах, а о главном умолчал: куда делись команды. В цикле sim нет типичных для таких случаев операторов switch или if. Дело в том, что BBJ имеет необычную архитектуру. На слуху архитектуры RISC, CISC, а здесь перед нами архитектура, которая называется OISC — One-Instruction Set Computer. Иными словами, зачем нам выбирать команду и зачем нужен код операции, если команда-то всего одна?

OISC-процессоры — большая экзотика. Несколько лет назад шуму наделал Movfuscator — компилятор C в код, состоящий только из команд mov. Movfuscator широко использует трюки x86-архитектуры, поэтому для самостоятельной реализации виртуальной машины не годится. Существует также классическая OISC-архитектура под названием Subleq, которая, как видно из названия, использует операцию вычитания и «меньше либо равно». То есть какое-то арифметико-логическое устройство (АЛУ) там все же есть. В BBJ, если вспомнить приведенный исходный код, вообще нет АЛУ! Как же это может работать? Продолжим изучение BBJ.

Процессор имеет трехадресную архитектуру следующего формата:

a, b, c

Команда (нетрудно подсчитать, что она занимает 3 × 3 = 9 байт) делает вот что:

mem[b] = mem[a] goto c

Да, и это все. Максимально просто, но неужели с этой командой можно реализовать любые вычисления, которые по силам обычным процессорам?

Эмулятор приставки

На странице BytePusher есть несколько rom’ов — образов памяти демонстрационных программ. Я предлагаю не доверять готовым эмуляторам (вдруг там какой-то подвох?), а реализовать собственный вариант BytePusher для проверки возможностей приставки.

Итак, как же устроена приставка, помимо того, что там содержится процессор BBJ? Цикл работы состоит из выполнения 65536 команд BBJ, далее видеобуфер из памяти отправляется на экран, после этого все повторяется. BytePusher обновляет экран 60 раз в секунду, то есть процессор работает на виртуальной частоте 65536 × 60 = 3932160 Гц или 3.9 МГц. Для сравнения: процессор Z80 в компьютере ZX Spectrum из начала 80-х имел частоту 3.5 МГц.

В BytePusher есть специальная небольшая область памяти по начальным адресам. Из интересного в ней — значение счетчика команд (pc) на старте очередного кадра и старший байт адреса начала видеобуфера. Эти данные обновляет программа.

Хотя в BytePusher поддерживаются клавиатура и звук, для простых экспериментов достаточно реализовать только графику. Цвет имеет довольно необычную кодировку: 6 уровней интенсивности цветовых компонентов в шестеричной системе счисления. К счастью, на практике достаточно использовать готовую таблицу на 256 цветов.

Собственно, теперь уже ничто не мешает реализовать собственный вариант BytePusher. Python-версию я написал с использованием только стандартной библиотеки. Версии BytePusher с PyGame и PySDL2 я встречал, а вот использование Tkinter показалось достаточно дерзким и амбициозным. К тому же когда-то я уже имел опыт портирования на Python + Tkinter демонстрации работы воксельного движка игры из начала 90-х Comanche. Что можно сказать по итогам реализации BytePusher на Python? На 60 fps мне выйти не удалось, хотя с PyPy демонстрационные программы для BytePusher работают приемлемо. С версией BytePusher на языке C я тоже решил пойти нестандартным путем: вместо SDL выбрал библиотеку Raylib. Это был мой первый опыт использования Raylib, и впечатления остались самые положительные.

Для BytePusher написано всего 11 программ, и я их все, конечно, просмотрел. Больше всего меня впечатлила Sprites: крупные, подвижные спрайты на узорчатом фоне. И все это — в 60 fps! То есть BBJ не просто какая-то «эзотерическая» архитектура, процессор вполне шустро работает!

К сожалению, для BytePusher до сих пор не написано ни одной игры, и в целом создается впечатление, что приставка осталась неизвестной большинству программистов. Мне это показалось ужасно несправедливым. «Решено! — подумал я. — Разберусь, как писать код для BBJ, и создам небольшую игру или что-нибудь другое, впечатляющее!»

Легко сказать — разберусь. Но где взять ассемблер? Ничего более-менее похожего на ассемблер я для этого процессора не обнаружил. Впрочем, ассемблер можно и написать, есть и более сложная задача: как на BBJ хотя бы сложить два числа?

Ассемблер — это просто

Начать разумно все-таки с написания ассемблера, чем я и занялся на Python. Есть набор директив, которые удобно иметь в любом ассемблере:

• org(addr). Установить текущую позицию размещения программы (here) на адрес addr.

• align(size). Выровнять here на границу size.

• label(name). Задать метку с именем name.

• i8(x). i16(x). i24(x). Разместить значение x заданного размера.

• incbin(filename). Вставить последовательность байт из файла с именем filename.

Язык ассемблера я реализовал на уровне функций Python (embedded DSL), что позволило использовать возможности последнего как макроязыка. Кроме того, этот подход избавил от возни с синтаксическим разбором. Теперь пора перейти к командам:

cmd(a, b, c)

Собственно, вот и все, команда-то всего одна: скопировать байт и перейти на адрес. Но можно попытаться выделить частные случаи этой команды.

Команда пересылки байта move(a, b) переходит на адрес следующей команды:

cmd(a, b, here() + 9)

Команда перехода jump(c) копирует ячейку в нее же:

cmd(0, 0, c)

Кое-что уже получается! Итак, первая программа, копирование числа из одной ячейки в другую и бесконечный цикл ожидания:

# адрес 0 move(18, 19) # адрес 9 jump(9) # адрес 18 i8(42) # адрес 19 i8(0)

Видя эти числа, поневоле ощущаешь, что соприкасаешься с чем-то древним и по-настоящему низкоуровневым! И даже вспоминаются строки из поэмы «История Мэла, настоящего программиста»:

…Но в старые добрые времена,

Когда слово «софтвер» звучало как-то странно,

А Hастоящие Компьютеры делались

Из барабанов и вакуумных ламп,

Hастоящие Программисты работали в машинных кодах.

Hе на ФОРТРАHе. Hе на RATFORe.

И даже не на ассемблере.

Просто машинные коды.

Hичем не прикрашенные,

Тупые сырые шестнадцатеричные числа.

Впрочем, довольно чисел, хочется хоть каких-то удобств! Кажется, что заменить числа на символические метки просто, но проблема возникает в ссылках наперед, когда имя есть, но его адрес еще неизвестен. Нам нужен второй проход ассемблера.

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

Теперь программа выглядит так:

move(addr('x'), addr('y'))  label('forever') jump(addr('forever'))  label('x') i8(42)  label('y') i8(0)

Как считать без АЛУ

Технически все готово для того, чтобы реализовать первую арифметическую операцию. Сложение двух чисел выглядит чрезмерно сложным, почему бы не начать с инкремента — увеличения значения ячейки на 1?

Как реализовать инкремент? Если у нас нет АЛУ, но есть память, давайте использовать ее. Я говорю, конечно, о таблицах:

move(addr('inc') + 42, addr('x'))  label('forever') jump(addr('forever'))  label('x') i8(0)  align(256) label('inc') for x in range(256):     i8(x + 1)

Видно, как это работает? Я специально выровнял адрес таблицы inc на границу 256, и теперь младший байт этого адреса можно использовать как индекс в таблице. В этом примере я увеличиваю 42 на 1 и результат записываю в переменную x.

Да, это не совсем то, что мы хотели, ведь таким образом можно проделывать вычисления только с константами. Идем дальше. Более сложная задача: попробую реализовать инкремент переменной x:

move(addr('x'), here() + CMD_SIZE + 2) move(addr('inc'), addr('x'))  label('forever') jump(addr('forever'))  label('x') i8(42)  align(256) label('inc') for x in range(256):     i8(x + 1)

Выражение here() + CMD_SIZE + 2 означает: текущий адрес плюс размер команды плюс еще два байта. Кажется, инкремент каким-то чудом заработал! 

Вообще-то, никакого чуда нет, а есть кое-что другое. Современные программисты с содроганием представляют себе эпоху до структурного программирования: все эти goto там и сям в коде. Но настоящее древнее зло скрывается под именем «самомодификация кода»! Именно ее я выше и использовал. Проще говоря, первый move записывает значение x в младший байт первого адреса второго move. 

Пора перейти к сложению:

move(addr('x'), here() + CMD_SIZE * 2 + 1) move(addr('y'), here() + CMD_SIZE + 2) move(addr('add'), addr('z'))  label('forever') jump(addr('forever'))  label('x') i8(10)  label('y') i8(15)  label('z') i8(0)  align(65536) label('add') for x in range(256):     for y in range(256):         i8(x + y)

Таблица add выровнена на границу 65536, потому что результат сложения находится по адресу, в средний и младший байты которого записаны аргументы.

Еще можно завести таблицу для констант. Ведь всех возможных значений немного — 256:

def const(n):     return addr('const') + (n & 255)  move(const(42), addr('x'))  label('forever') jump(addr('forever'))  label('x') i8(0)  a.align(256) label('const') for x in range(256):     a.i8(x)

Итак, чтобы процессор BBJ делал что-то полезное, нужно использовать таблицы и самомодификацию кода. Таким образом, кстати, организуются ветвления и вызовы процедур. Не буду портить удовольствие у читателя от самостоятельных разгадок, как это можно осуществить.

А снег идет

Ассемблер готов, пора приступать к написанию чего-то «впечатляющего». После некоторых раздумий я пришел к мысли, что конец декабря — подходящее время для старой доброй демосценерской модели падающего снега. Но если я делаю демо, то должны быть и какие-то ограничения на размер программы. Например, Sprites для BytePusher занимает аж 524 КБ! Оно и понятно: все эти многочисленные таблицы необходимы для вычислений. Хорошо! Тогда моя задача — постараться в программе полностью избавиться от таблиц по 64 КБ. Это означает, что я должен как-то обойтись таблицами унарных операций на 256 Б. Приступим!

Модель падающего снега можно представить себе в виде клеточного автомата (помните игру «Жизнь»?). Проходим по всем пикселям экрана. Если пиксель занят снежинкой, то выбираем случайное смещение для падения на один пиксель вниз. Падение происходит, если на новых координатах пусто. В первой строке экрана регулярно формируем новые снежинки.

При реализации модели падающего снега важно правильно сканировать буфер экрана. Если двигаться сверху вниз, то ничего хорошего не получится (попробуйте догадаться почему). Можно создать второй буфер, но гораздо проще и экономнее сканировать строки буфера снизу вверх.

Так обычно «снег» и реализуется, но возможно ли это на BytePusher? Для разрешения экрана 256×256 потребуется обработать 65536 пикселей и это равно общему числу команд, которые мы можем затратить на обработку одного кадра. За это время возможно только скопировать данные из одного места в другое, не более того. Что же делать?

Хотелось бы обрабатывать только те пиксели, что содержат снежинки. Здесь полезно перейти от модели падающего снега как клеточного автомата к системе частиц.

Для каждой строки буфера я завел список координат x находящихся там снежинок. Этот список снежинок на строке — полноценная структура данных со следующими операциями:

1. Получить число элементов списка.

2. Добавить элемент в конец списка.

3. Удалить элемент с заданным индексом из списка.

Что говорите? Классы и сборщик мусора? Увы, нам нужно реализовать каждую операцию за константное время и в константном размере памяти. Например, удаление элемента по индексу делается так: на место удаляемого элемента поместим последний элемент и уменьшим размер списка на 1.

В программе для BytePusher я завел ряд 256-байтных таблиц, в том числе для псевдослучайных чисел, сравнения с нулем, инкремента и декремента. Настоящая проблема возникла с операцией равенства. Это бинарная операция, а значит, она потребует таблицы на 64 КБ. Что делать? Сформировать эту таблицу прямо во время выполнения программы!

Я написал первую версию «снега» для BytePusher, запустил — и снег действительно пошел! В 60 fps! Стали набираться сугробы — красота! Через некоторое время я заметил неладное. В верхней части экрана появились «замороженные» пиксели, число падающих снежинок стало уменьшаться. С ростом числа сугробов увеличилось и число обрабатываемых снежинок за кадр, в результате вычисления прерывались.

Не надо думать, будто я изначально не учел рост снега! В модели на С все было хорошо: когда снежинки занимали полную строку, счетчик списка переполнялся, устанавливался в 0, и это приводило к тому, что заполненная строка более не обрабатывалась. Разница оказалась в генераторе псевдослучайных чисел. В версии на C снег падал равномерно, сугробы оказывались небольшими. В версии для BytePusher появлялись высокие пики снега и долгое время лишь небольшое число строк оказывалось заполненным полностью.

Простое решение состоит в том, чтобы заставить снег «проваливаться», вовсе не образуя сугробы, но это бы выглядело слишком скучно. Я выбрал иной путь: за один кадр я случайно «гашу» до двух снежинок. В результаты сугробы перестают бесконтрольно расти, к тому же это дает интересный эффект мерцания падающего снега.

Снег идет, но все еще чего-то не хватает — центрального объекта, который будет покрываться снегом. Я решил использовать цифры «2025». План был следующий: перед началом моделирования снегопада на экран выводятся цифры, которые для снежинок являются преградой — такими же снежинками, что почему-то повисли в воздухе.

Прикинув различные варианты представления графических данных, я остановился на следующем. Изображение хранится в виде нескольких последовательностей 256-байтных страниц — каждая последовательность страниц для своего цвета (в моем случае оказалось достаточно всего двух цветов). Страница, в свою очередь, представляет собой последовательность координат (x, y) для тех пикселей, которые не являются «прозрачными». Если пиксели исчерпались раньше времени, я просто добавляю последнюю пару координат до заполнения страницы.

Размер получившейся программы — 9728 байт. Это одна из самых маленьких среди существующих программ для BytePusher! Результат в действии можно также увидеть на гитхабе (да, я сделал эмулятор и для JS).

Заключение

Я написал ассемблер, но имеет ли смысл создать для BytePusher компилятор языка высокого уровня? На мой взгляд, смысла в этом немного. Для программ в духе модели падающего снега приходится выверять код до такта, обычный компилятор просто не в состоянии генерировать настолько качественный результат. Создание же «необычного» компилятора — наукоемкая задача, которую, подозреваю, никто не станет решать только ради развлечения и обучения. Кроме того, в написании низкоуровневого кода на ассемблере есть свое очарование, это делает BytePusher интересной платформой для демосцены. Все материалы к статье можно найти в репозитории.

Я так и не написал игру для BytePusher, но, надеюсь, с выходом этой статьи кто-нибудь заинтересуется и создаст первую (!), хотя бы самую простую игру для этой платформы.

Пользуясь случаем, хочу обрадовать любителей системного программирования. У нас с вами появилась своя конференция — sysconf 2025! Она пройдет 22 марта в Москве, можно зарегистрироваться на офлайн и онлайн.