[Перевод] Создание эмулятора аркадного автомата. Часть 1
Написание эмулятора аркадного автомата — это замечательный учебный проект, и в этом туториале мы очень подробно рассмотрим весь процесс разработки. Хотите по-настоящему разобраться в работе процессора? Тогда создание эмулятора — наилучший способ его изучения.
Вам потребуется знание C, а также пригодится знание ассемблера. Если вы не знаете язык ассемблера, то написание эмулятора — лучший способ освоить его. Также вам нужно будет освоить шестнадцатеричную математику (также известную как base 16 или просто «hex»). Я расскажу и об этой теме.
Я решил выбрать эмулятор автомата Space Invaders, в котором используется процессор 8080. Эта игра и этот процессор очень популярны, потому в Интернете можно найти о них кучу информации. Для завершения проекта она вам понадобится.
Весь исходный код туториала выложен на github. Если вы не освоили работу с git, то на странице github есть кнопка «Download ZIP», позволяющая скачать архив со всем кодом.
В «обычной» математике используется десятичная система счисления. Каждая цифра числа может иметь значение от нуля до девяти, и когда мы превышаем 9, то добавляем единицу к числу в следующем разряде и снова начинаем с нуля. Это всё довольно просто и прямолинейно, и вы, вероятно, никогда об этом не задумывались.
Возможно, вы знаете или слышали, что компьютеры работают с двоичными данными. Компьютерные гики называют десятичную математику base-10, а двоичную называют base-2. В двоичном счислении каждый разряд числа может иметь только два значения, ноль или единицу. В двоичном коде счёт происходит так: 0, 1, 10, 11, 100, 101, 110, 111, 1000. Это не десятичные числа, поэтому нельзя называть их «ноль, один, десять, одиннадцать, сто, сто один». Они произносятся как «ноль, один, один-ноль, один-один, один-ноль-ноль» и т.д. Я редко читаю двоичные числа вслух, но если это необходимо, то нужно чётко указать используемую систему счисления. Десять, одиннадцать и сто не имеют никакого смысла в двоичном счислении.
В десятичном счислении число имеет следующие разряды: единицы, десятки, сотни, тысячи, десятки тысяч и т.д. В двоичной системе следующие разряды: единицы, двойки, четвёрки, восьмёрки и т.д. В информатике значение каждого двоичного разряда называется битом. 8 бит составляют один байт.
В двоичном счислении строка чисел быстро становится очень длинной. Для представления десятичного числа 20 000 в двоичном счислении потребуется 16 разрядов: 0b100111000100000. Чтобы устранить эту проблему, удобно использовать шестнадцатеричную систему счисления, также известную как base-16 (или hex). В base-16 каждый разряд содержит 16 значений. Для значений с нуля по девять используются те же символы, что и в base-10, но для оставшихся 6 значений используются замены в виде первых 6 букв алфавита, от A до F.
Счёт в шестнадцатеричной системе выполняется так: 0 1 2 3 4 5 6 7 8 9 A B C D E F 10 11 12 и т.д. В hex-счислении десятки, сотни и так далее не имеют того же значения, что и в десятичной, поэтому люди произносят цифры по отдельности. Например, $A57 вслух произносится как «A-пять-семь». Для понятности также можно добавить hex, например «A-пять-семь-hex». В шестнадцатеричной системе счисления аналогом десятичного числа 20 000 является $4E20 — гораздо более компактная форма по сравнению с 16 разрядами двоичной системы.
Думаю, шестнадцатеричная система была выбрана из-за очень естественного преобразования из двоичной в шестнадцатеричную систему и обратно. Каждый hex-цифра соответствует 4 разрядам (4 битам) аналогичного двоичного числа. 2 hex-цифры составляют один байт (8 бит). Отдельную шестнадцатеричную цифру можно назвать nibble, а некоторые люди даже пишут её через y, как «nybble».
| Каждая hex-цифра — это 4 двоичных цифры | |||
|---|---|---|---|
| Hex | A | 5 | 7 |
| Binary | 1010 | 0101 | 0111 |
При написании кода на C считается, что число является десятичным (base-10), если оно не помечено как-то иначе. Чтобы сообщить компилятору C, что число двоичное, мы добавляем число ноль и букву b в нижнем регистре, например так: 0b1101101. Шестнадцатеричное число можно записать в коде на C добавлением в начале нуля и x в нижнем регистре: 0xA57. В некоторых языках ассемблера для обозначения hex-числа используется знак доллара $: $A57.
Если подумать, то связь между двоичными, шестнадцатеричными и десятичными числами совершенно очевидна, но у первого инженера, додумавшемуся до этого ещё до изобретения компьютера, это должно было стать моментом озарения.
Разобрались во всё этом? Отлично.
Если вы уже знаете это, можете спокойно пропустить раздел.
Центральный процессор (ЦП, CPU) — это машина, созданная для выполнения программ. Фундаментальными блоками ЦП являются регистры и инструкции. Как разработчик программного обеспечения вы можете относиться к этим регистрам как к переменным. В нашем процессоре 8080, кроме прочих регистров, есть 8-битные регистры под названием A, B, C, D и E. Можно воспринимать эти регистры как следующий код на C:
unsigned char A, B, C, D, E;
У всех процессоров также есть счётчик команд (Program Counter, PC). Можно воспринимать его как указатель.
unsigned char* pc;
Для ЦП программа — это последовательность шестнадцатеричных чисел. Каждая команда языка ассемблера в 8080 соответствует 1–3 байтам в программе. Для того, чтобы узнать, какой команде соответствует какое число, пригодится справочник по процессору (или любая другая информация о процессоре 8080 из Интернета).
Названия команд (инструкций) часто являются мнемониками от операций, выполняемых этими командами. Мнемоника для загрузки в 8080 это MOV (move), а для выполнения сложения используется ADD.
Примеры
Текущее значение памяти, на которое указывает счётчик команд, равно 0×79. Это соответствует инструкции MOV A,C процессора 8080. Этот ассемблерный код в коде на C выглядит как A=C;.
Если вместо этого значение в PC равнялось бы 0×80, то процессор выполнил бы ADD B. В языке C это соответствует строке A = A + B;.
Полный список команд процессора 8080 можно найти здесь. Для реализации нашего эмулятора мы будем использовать эту информацию.
Тайминги
В ЦП на выполнение каждой инструкции требуется определённое количество времени (тайминг), измеряемого в циклах. В современных процессорах эту информацию бывает сложно получить, потому что тайминги зависят от множества разных аспектов. Но в старых процессорах наподобие 8080 тайминги постоянны и эту информацию часто предоставляет производитель процессора. Например, инструкция пересылки из регистра в регистр MOV занимает 1 цикл.
Информация о таймингах полезна для написания эффективного кода в процессоре. Программист может стремиться избегать инструкций, выполнение которых занимает много циклов.
Важнее для нас то, что мы воспользуемся информацией о таймингах для эмуляции процессора. Чтобы игра работала так же, как на оригинале, инструкции должны выполняться с правильной скоростью. Некоторые эмуляторы прикладывают для этого огромные усилия, но когда мы до этого доберёмся, то нам придётся решить, какую точность мы хотим получить.
Прежде чем закрыть тему двоичных и шестнадцатеричных чисел, нам стоит поговорить о логических операциях. Вероятно, вы уже привыкли к использованию логики в коде, например, в таких конструкциях как if ((conditionA) and (conditionB)). В программах, работающих непосредственно с «железом», часто приходится манипулировать отдельными битами чисел.
Операция AND (И)
Вот все возможные результаты операции AND (И) (таблица истинности) между двумя однобитными числами.
| x | y | Результат |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат AND равен единице только тогда, когда оба значения равны единице. Когда мы объединяем два числа операцией AND, для каждого бита одного числа выполняется AND с соответствующим битом другого числа. Результат сохраняется в этом бите числа-получателя. Наверно лучше стоит просто посмотреть на пример:
| binary | hex | ||||||||
| исходное x | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | $6B |
| исходное y | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | $D2 |
| x AND y | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | $42 |
В языке C операция логического «И» — это простой амперсанд »&».
Операция OR (ИЛИ)
Операция OR работает похожим образом. Разница заключается лишь в том, что результат будет равен одному, если хотя бы одно из значений x или y равно одному.
| x | y | Результат |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| binary | hex | ||||||||
| исходное x | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | $6B |
| исходное y | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | $D2 |
| x OR y | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | $FB |
В языке C логическая операция OR обозначается вертикальной чертой »|».
Почему это важно?
Во многих старых процессорах, а особенно в аркадных автоматах игре часто требуется работать только с одним битом числа. Часто встречается подобный код:
/* Пример 1: считываем с панели управления */
char *buttons_ptr = (char *)0x2043;
char buttons = *buttons_ptr;
if (buttons & 0x4)
HandleLeftButton();
/* Пример 2: включаем LED-индикатор на панели управления */
char * LED_pointer = (char *) 0x2089;
char led = *LED_pointer;
led = led | 0x40; //задаём, что LED управляется битом 6
*LED_pointer = led;
/* Пример 3: отключаем один LED-индикатор */
char * LED_pointer = (char *) 0x2089;
char led = *LED_pointer;
led = led & 0xBF; //маскируем бит 6
*LED_pointer = led;
В примере 1 распределённый в памяти адрес $2043 — это адрес кнопок на панели управления. Этот код считывает и реагирует на нажатую кнопку. (Разумеется, в Space Invaders этот код будет на языке ассемблера!)
В примере 2 игра хочет зажечь светодиодный индикатор, который расположен в бите 6 распределённого в памяти адреса $2089. Код должен считать уже имеющееся значение, изменить только один бит, и записать его обратно.
В примере 3 нужно отключить индикатор из примера 2, поэтому код должен обнулить бит 6 адреса $2089. Это можно сделать, выполнив для байта управления индикатором операцию AND со значением, у которого нулевым является только бит 6. Так мы повлияем только на 6, оставив остальные биты неизменными.
Обычно это называется «маской». На языке C маску обычно пишут с помощью оператора NOT, обозначаемого тильдой (»~»). Поэтому вместо того, чтобы писать 0xBF, я просто запишу ~0x40 и получу такое же число, но не вкладывая больших усилий.
Если вы читаете этот туториал, то, вероятно, знакомы с компьютерным программированием, например, на языке Java или Python. Эти языки позволяют выполнять большой объём работы всего в нескольких строках кода. Код считается умно написанным, если выполняет как можно больше работы как можно за меньшее количество строк, возможно, даже с помощью функционала встроенных библиотек. Подобные языки называются «языками высокого уровня».
В языке ассемблера напротив нет никаких встроенных упрощающих жизнь возможностей, и для выполнения простых задач может потребоваться множество строк кода. Язык ассемблера считается языком низкого уровня. В нём вам больше приходится привыкать к мышлению в стиле «какую конкретно последовательность шагов необходимо сделать для выполнения этой задачи?»
Самое важное, что нужно знать о языке ассебмлера — каждая строка транслируется в одну команду процессора.
Рассмотрим такую конструкцию из языка C:
int a = b + 100;
В языке ассемблера эту задачу придётся выполнять в следующей последовательности:
- Загрузить адрес переменной B в регистр 1
- Загрузить содержимое этого адреса памяти в регистр 2
- Прибавить непосредственное значение 0×64 к регистру 2
- Загрузить адрес переменной A в регистр 1
- Записать содержимое регистра 2 в адрес, хранящийся в регистре 1
В коде это будет выглядеть примерно так:
lea a1, #$1000 ; адрес переменной a
lea a2, #$1008 ; адрес переменной b
move.l d0,(a2)
add.l d0, #$64
mov (a1),d0
Стоит заметить следующее:
- В языке высокого уровня компилятор сам решает, где разместить переменные в памяти. При написании кода на ассемблере вы сами отвечаете за каждый адрес памяти, который будете использовать.
- В большинстве языков ассемблера скобки означают «память по этому адресу».
- В большинстве языков ассемблера # обозначает алгебраическое число, также называемое непосредственным значением. Например, в строке 1 из примера выше код на самом деле записывает в регистр a1 значение #0×1000. Если бы код выглядел как
move.l a1, ($1000), то a1 бы получал содержимое памяти по адресу 0×1000. - У каждого процессора свой язык ассемблера, и переносить код с одного процессор на другой бывает сложно.
- Это не язык ассемблера реального процессора, я придумал его для примера.
Однако между умными программистами высокого уровня и мастерами ассемблера есть одна схожая черта. Программисты на ассемблере считают честью выполнить задачу как можно более эффективно и минимизировать количество использованных команд. Код для аркадных автоматов обычно сильно оптимизируется и из каждого лишнего байта и цикла выжимаются все соки.
Давайте ещё немного поговорим об языке ассемблера. В любой достаточно сложной компьютерной программе на ассемблере используются подпрограммы (subroutine). В большинстве ЦП существует структура под названием стек (stack).
Представим стек в виде стопки. Если нам нужно сохранить число, мы кладём её на вершины стопки. Когда нам нужно вернуть его обратно, мы забираем его с вершины стопки. Программисты на ассемблере называют запись числа в стек «push», а извлечение числа — «pop».
Допустим моей программе нужно вызывать подпрограмму. Я могу написать подобный код:
0x1000 move.l (sp), d0 ; записываем d0 в стек
0x1004 add.l sp, #4 ; выполняем инкремент указателя стека
0x1008 move.l (sp), d1 ; записываем d1 в стек
0x1010 add.l sp, #4 ; и т.д.
0x1014 move.l (sp), a0
0x1018 add.l sp, #4
0x101C move.l (sp), a1
0x1020 add.l sp, #4
0x1024 move.l (sp), #0x1030 ; возвращаем адрес
0x1028 add.l sp, #4
0x102C jmp #0x2040 ; адрес подпрограммы - 0x2040
0x1030 move.l a1, (sp) ; восстанавливаем значения регистров
0x1034 sub.l sp, #4 ; в обратном порядке
0x1038 move.l a0, (sp) ; восстанавливаем значения регистров
0x103c sub.l sp, #4
и т.д.
Показанный выше код записывает в стек значения d0, d1, a0 и a1. Большинство процессоров использует указатель стека. Это может быть обычный регистр, по соглашению используемый в качестве указателя стека, или специальный регистр с функциями для определённых инструкций.
В процессорах серии 68K указатель стека определяется только по соглашению, во всём остальном это обычный регистр. В нашем процессоре 8080 регистр SP — это особый регистр. У него есть команды PUSH и POP, выполняющие запись и извлечение из стека всего за одну команду.
В нашем проекте эмулятора мы не будем писать код с нуля. Но если вам требуется анализировать программы на языке ассемблера, то хорошо научиться распознавать подобные конструкции.
Высокоуровневые языки
При написании программы на высокоуровневом языке все операции сохранения и восстановления регистров выполняются при каждом вызове функции. Мы не задумываемся о них, потому что ими занимается компилятор. Вызовы функций на языке высокого уровня могут занимать много памяти и процессорного времени.
Бывало ли у вас когда-нибудь так, что программа вываливалась при вызове подпрограммы в бесконечном цикле? Это можно происходить потому, что каждый вызов функции помещал значения регистров в стек, и в какой-то момент у стека заканчивалась память. (Если стек слишком разрастается, это называется переполнением стека, или stack overflow.)
Возможно, вы слышали о встраиваемых функциях (inline function). Они позволяют избежать сохранения и восстановления регистров благодаря включению кода подпрограммы в вызывающую функцию. Код при этом становится больше, но благодаря этому экономится несколько команд и операций чтения/записи в память.
Соглашения о вызовах
При написании программы на ассемблере, вызывающей только ваш код, вы можете сами решать, как подпрограммы будут общаться друг с другом. Например, как мне вернуться к вызывающей функции после того, как подпрограмма завершена? Один из способов заключается в записи адреса возврата в определённый регистр. Другой — в размещении адреса возврата на вершине стека. Очень часто решение зависит от того, что поддерживает процессор. У 8080 есть команда CALL, записывающая в стек адрес возврата из функции. Возможно, для реализации вызовов подпрограмм вы будете использовать эту команду 8080.
Нужно принять и ещё одно решение. Сохранение регистров — это обязанность вызывающей функции или подпрограммы? В показанном выше примере регистры сохраняются вызывающей функцией. Но что, если у нас 32 регистра? Сохранение и восстановление 32 регистров, когда подпрограмма использует только малую их часть, будет пустой тратой времени.
Компромисс может заключаться в смешанном подходе. Допустим, мы выбрали политику, при которой подпрограмма может использовать регистры r10-r32 без сохранения их содержимого, но не может уничтожать r1-r9. В подобной ситуации вызывающая функция знает следующее:
- При возврате из функции содержимое r1-r9 останется неизменным
- Я не могу зависеть от содержимого r10-r32
- Если мне понадобится значение в r10-r32 после вызова подпрограммы, то перед её вызовом мне нужно его куда-то сохранить
Аналогично, каждая подпрограмма знает следующее:
- Я могу уничтожать r10-r32
- Если я хочу использовать r1-r9, то мне нужно сохранить содержимое и восстановить его, прежде чем возвращаться к вызвавшей меня функции
ABI
На большинстве современных платформ такие политики создаются инженерами и публикуются в документах, называемых ABI (Application Binary Interface, двоичный интерфейс приложений). Благодаря этому документу создатели компиляторов знают, как компилировать код, который может вызывать код, скомпилированный другими компиляторами. Если вы хотите писать ассемблерный код, который сможет функционировать в подобном окружении, то вам нужно знать ABI и писать код в соответствии с ним.
Знание ABI также помогает в отладке кода, когда у вас нет доступа к исходникам. В ABI определяются местоположения параметров для функций, поэтому при рассмотрении любой подпрограммы вы можете изучать эти адреса, чтобы понять, что передаётся функциям.
Возвращаемся к эмулятору
БОльшая часть написанного вручную ассемблерного кода, особенно для старых процессоров и аркадных игр, не следует ABI. Программы закодированы на ассемблере и в них может не быть много подпрограмм. Каждая подпрограмма сохраняет и восстанавливает регистры только в случае крайней необходимости.
Если вы хотите понять, что же делает программа, неплохо будет начать с пометки адресов, являющихся целевыми для команд CALL.
