Часть 1 - Прелюдия, Chip8 Intro, Коды операций
Репо с тегами с полным кодом из этой главы
Ранее мы рассмотрели, что и почему интерпретаторы, познакомились с виртуальной машиной Chip-8 и узнали о кодах операций.
Мы начали с решения простого вопроса: как я могу перевести любой заданный код операции в более читаемое представление того, что он делает? Этот процесс преобразования кода операции (или машинного кода) в очень низкоуровневое, удобочитаемое представление называется дизассемблированием.
То, на что мы смотрим, когда видим что-то вроде MOV $3 FFh, известно как язык ассемблера, а программа, которая переводит всю или часть другой программы, написанной в байт-коде, называется дизассемблером.
Наша следующая цель - написать дизассемблер.
Вы можете подумать: «Ну, у нас уже есть дизассемблер». Потому что у нас уже есть возможность переводить произвольный байт-код в сборку.
Учитывая некоторую программу в качестве входных данных, все, что нам нужно сделать, это пройтись по буферу и разобрать коды операций, верно?
Наивный подход
const getOpcode = (high: number, low: number = 0): number => {
return (high << 8) | low;
};
const disassemble = (program: Uint8Array): string => {
const output = [];
for (let i = 0; i < program.length; i += 1) {
const Opcode = new Opcode(
getOpcode(program[i], program[i + 1])
);
output.push(Opcode.toString());
}
return output.join('\n');
};
Этот код определенно создаст что-то читабельное и, возможно, даже выполнимое. Но прежде чем мы перейдем к выводу disassemble, давайте изменим наш класс Opcode, включив в него метки.
Этикетки, говорите?
Идея здесь в том, что когда мы выполняем переходы через JSR или JMP, мы указываем какое-то адресное пространство для перехода. Что-то вроде JSR 3ADh, в котором говорится: установите счетчик программы в ячейку памяти 0x3AD.
Вместо того, чтобы указывать место в памяти, было бы намного проще писать и читать что-то вроде,
JSR :my-subroutine XOR $0, $1 JMP :my-jump :my-subroutine MOV $0, 1h MOV $1, 2h DRAW 0h, 1h, 6h RET :my-jump
Итак, каков минимум, который нам нужен, чтобы добавить эту функцию в наш класс кода операции? Давайте на мгновение вернемся к идее токенов: до сих пор мы видели типы Instruction, Integer и Register.
Что такое регистр или целочисленный токен?
const regToken = new Token(TokenType.REGISTER, 0xB); const intToken = new Token(TokenType.INTEGER, 0x10);console.log(regToken) // $B console.log(intToken) // 10h
Класс токена представляет значения, зависящие от типа переданного токена. К регистровому токену добавлен символ $, а к целочисленному токену добавлен символ h. Оба представлены в шестнадцатеричном формате.
Если мы хотим добавить метки в нашу дизассемблированную версию, нам нужно будет создать новый тип токена, названный LABEL. (Вы, возможно, помните из кода в прошлый раз, что у нас уже есть этот тип вместе с EOF, COMMENT и VOID).
С ярлыком будет связан символ ::
const labelToken = new Token(TokenType.LABEL, 'my-label'); console.log(labelToken) //:my-label
Вот необходимые изменения, которые нам нужно внести в наш класс Opcode:
Поскольку мы разбираем байт-код, мы не можем позволить себе роскоши знать, какие метки существовали раньше. Лучшее, что мы можем сделать, - это создать общий label-<address being branched>. Пока мы это делаем, давайте добавим концепцию «строгого» кода операции. Это поможет нам в тестировании и дальнейшей компиляции. Если передано false в качестве второго аргумента конструктора, любой недопустимый код операции будет интерпретирован как инструкция NOOP или без операции.
В спецификации Chip-8 указано, что большинство программ запускаются с адресного пространства 0x200. Мы будем разрабатывать наш эмулятор в соответствии с этой спецификацией: все, что меньше 0x200, будет зарезервировано для интерпретатора. Зная это, мы можем добавить адрес к нашему вышеупомянутому методу disassemble, сдвинув текущий индекс кода операции на 0x200:
Наконец, нам нужно будет отслеживать коды операций с метками и адреса, которым эти метки принадлежат. Мы можем добиться этого, сохранив карту адресов и меток, а затем перебирая записи в цикле после того, как мы дизассемблировали всю программу:
const disassemble = (program: Uint8Array): string => {
const output: Map<string, string> = new Map();
let labels: Map<string, Token> = new Map();
for (let i = 0; i < program.length; i += 2) {
const address = i + 0x200;
const opcode = new Opcode(
getOpcode(program[i], program[i + 1]),
false
);
if (opcode.label)
labels.set(opcode.bytes.nnn.toString(), opcode.label);
output.set(
address.toString(),
`${opcode.toString()} ;${address.toString(16)}`
);
}
Array.from(labels)
.forEach(([address, labelToken]: [string, Token]) => {
const disassembly = output.get(address);
output.set(address, `${labelToken}\n${disassembly}`);
});
return Array.from(output.values()).join('\n');
};
Давайте рассмотрим некоторые части pong2 rom:
Замечательно! Давайте поздравим себя и рассмотрим разборку понга. Мы можем видеть подпрограммы и ветви в (относительном) действии. У нас также есть адреса, по которым встречаются коды операций, чтобы помочь нам разобраться в том, что происходит внутри программы.
Если бы мы пересобирали вышеуказанную программу как есть, мы бы получили играбельный понг.
🤔 В чем прикол.
Да, мы еще не закончили. Потому что наш дизассемблер работает… но только иногда и случайно. Давайте посмотрим на первые несколько строк дизассемблера из другой программы, которую мы видели раньше, missile.c8:
JMP :label-0x0219 ;200 SKNE $D, 49h ;202 SKEQ $3, $5 ;204 SKNE $9, 4Ch ;206 SKNE $5, 20h ;208 MOV $2, 79h ;20a JSR :label-0x0044 ;20c MOV $1, 76h ;20e MOV $9, 64h ;210 JSR :label-0x0057 ;212
Ой ой. Этот первый переход приводит нас к нечетному адресному пространству. То, что далее следует, тоже не очень красиво, у нас, по-видимому, есть еще два перехода в область памяти ниже 0x200 и необычные четыре пропущенных ветки подряд. Это не может быть правдой. Наконец, ближе к концу вывода у нас есть куча пустых ярлыков:
:label-0x0219 :label-0x0044 :label-0x0057 ... and so on ...
Эта программа никак не могла бы работать, если бы мы собрали ее заново и запустили на нашем эмуляторе (который мы еще не создали).
Но почему? Где мы ошиблись?
Применяя наш наивный подход, мы сделали некоторые предположения о программах, которые не очень точны:
- Что все коды операций будут происходить в одинаковом пространстве памяти. (Начиная с нуля и продвигаясь на два).
- Все регионы программы являются допустимыми кодами операций. (Дизассемблируя каждую инструкцию и создавая NOOP, когда она недействительна).
На самом деле мы не можем контролировать, по какому адресу программа перейдет к следующему адресу, и нет причин, по которым программа не должна перейти на неровный адрес. Все они представляют собой одинаковые непрерывные байты в памяти: 0x13 0x34 0x42 производит два разных (JMP, SKEQ), но действительных кода операции в зависимости от того, с чего вы начали.
Кроме того, наличие байтов в программе не означает, что они предназначены для использования в качестве кодов операций. Некоторые могут быть просто недоступны, но другие могут быть данными, используемыми для рисования спрайтов или загрузки регистров.
Рассмотрим на мгновение код операции 0xFX65, который мы дали мнемоническим LDR (сокращение от LoaD Registers). Этот код операции загружает регистры от 0 до X из памяти, начиная с того места, где индексный регистр в настоящее время имеет значение от 0 до X. Вы можете представить сценарий, в котором мы сохранили некоторые постоянные данные в конце нашей программы (недоступные из основного цикла), и хотите загрузить его в регистры с помощью этой команды.
Другое использование - для хранения спрайтов. Давайте подойдем и посмотрим на код операции pong2 по адресу 0x208: MVI 2EAh ; 208. Если мы просканируем до адреса 0x2EAH, мы увидим
MOV $0, $8 ;2ea MOV $0, $8 ;2ec MOV $0, $8 ;2ee MOV $0, $0 ;2f0 NOOP ;2f2 NOOP ;2f4
Фактически, это недоступное адресное пространство для нормальной программы. Это означает, что программный счетчик ВМ Chip-8 никогда не приземлится на эти адреса. Совершенно случайно то, что они напоминают код операции MOV $ 0, $ 8, и, таким образом, чисто случайно, что наша пересобранная программа вообще работает.
Эти байты действительно существуют для рисования лопастей. Посмотрев на шестнадцатеричный дамп исходной программы, мы увидим:
80 80 80 80 80 80 80 00 00 00 00 00 ^ - The MVI command sets index register here. //where 0x80 = 0b10000000
Обратите внимание, что два оператора, следующие за начальным MVI, являются операторами DRAW. Когда Chip-8 получает команду DRAW, он рисует спрайт в положениях экрана, хранящихся в регистрах X и Y, с высотой Z. Спрайты всегда имеют ширину 8 пикселей и представлены в виде битов байта в памяти. Chip-8 загружает данные спрайта из памяти, начиная с индексного регистра. Если мы рисуем спрайт высотой шесть, мы начинаем с индексного регистра I + 0 и заканчиваем индексным регистром I + 6.
A paddle: 0b10000000 ; 0x2ea 0b10000000 ; 0x2eb 0b10000000 ; 0x2ec 0b10000000 ; 0x2ed 0b10000000 ; 0x2ee 0b10000000 ; 0x2ef
Если бы мы изменили эти числа на 0xC0 (0b11000000), ширина наших лопастей была бы на один дополнительный пиксель.
Тонкий подход
Итак, мы увидели причины, по которым наивный подход не дает стабильных результатов. Нам нужна стратегия, позволяющая исследовать все доступные адреса, отмечать их как достижимые и затем выводить любые недостижимые данные.
Вместо того, чтобы рассматривать эти коды операций как последовательный список инструкций, давайте представим их больше как динамическую программу. Учтите следующее:
MOV $1, $3 SKEQ $1, $2 JSR :take-damage JSR :check-input :take-damage MOV $6, 0x2h SUB $4, $5 RET :check-input MOV $1, 0xA SKUP $1 ADD $5, 0x2 RET
Поразительное количество проблем можно решить с помощью поиска в ширину и в глубину.
Глядя на приведенное выше дерево, мы определенно не хотим использовать BFS. Это приблизит нас к тому, чего мы пытаемся избежать: последовательному посещению кодов операций.
Нам нужен поиск в глубину, и если нам нужна DFS, нам понадобится стек.
Вот какой будет наша новая стратегия:
Выполните итерации по программе, отмечая каждый посещенный адрес как достижимый. При обнаружении оператора ветвления помещайте следующий адрес в стек и следуйте за ветвью.
Когда стек пуст, перебрать все возможное адресное пространство до размера программы. Если потенциальный адрес достижим, разберите его.
Наконец, учтите все недостижимое, ненулевое адресное пространство.
Уф, это был полный рот. На самом деле мы супер близки.
Это требует немного больше размышлений, чем дизассемблирование кода операции, но как только это закончится, реализовать это будет проще простого. Мы даже можем повторно использовать некоторые идеи из предыдущего наивного решения: output станет reachableAddresses, program станет buffer, и мы сохраним карту меток без изменений.
С классом, который принимает UInt8Array в качестве единственного аргумента конструктора, мы можем реализовать что-то вроде этого, здесь полный код:
Один неудобный фрагмент кода находится внутри метода generateProgram. Мы должны решить, увеличивать или нет текущий адрес на один или два. Мы принимаем это решение, проверяя, доступен ли текущий адрес.
Если это так, это означает, что все, что существует на нем, будет двухбайтовым кодом операции, и следующий адрес для проверки будет через два байта. В противном случае необходимо проверить данные и следующий байт на наличие допустимого кода операции.
Однако остается одна дилемма: что нам делать с недоступными адресами?
Мы могли бы подумать о том, чтобы просто вывести необработанные байты на место, например:
FONT $2 ;2e4 DRAW 4h, 5h, 5h ;2e6 RET ;2e8 80h ;2ea 80h ;2eb 80h ;2ec 80h ;2ed 80h ;2ee 80h ;2ef 0h ;2f0 0h ;2f1 0h ;2f2 0h ;2f3 0h ;2f4 0h ;2f5 :label-0x02F6 MOV $B, 20h ;2f6 MOV $C, 0h ;2f8
Во-первых, это выглядит не очень хорошо. Дело в том, чтобы создать что-то, что мы можем понять. Наличие больших кусков необъяснимых чисел ведет нас в противоположном направлении.
Что еще более важно, здесь не хватает некоторой важной информации: куда поместить эти числа при повторной сборке программы. Ассемблер не будет иметь доступа к комментариям, и никакие другие токены не будут предоставлять контекст для расположения в памяти.
Это сделано намеренно. Ячейки памяти должны (насколько это возможно) быть прерогативой ассемблера. С добавлением меток нам удалось (почти полностью) абстрагировать их из уравнения.
Мы могли бы попытаться переработать эту концепцию, пометив недостижимые области метками, но это может оказаться больше проблем, чем того стоит: в отличие от переходов и подпрограмм, ldr и sdr mvi могут обращаться к разным частям одного и того же непрерывного блока недоступной памяти.
Представьте себе следующий сценарий:
80h ;2ea <- mvi accesses this 80h ;2eb 80h ;2ec <- ldr accesses this 80h ;2ed 80h ;2ee <- sdr accesses thi 80h ;2ef //would become... :label-0x2ea 80h ;2ea <- mvi accesses this 80h ;2eb :label-0x2ec 80h ;2ec <- ldr accesses this 80h ;2ed :label-0x2ee 80h ;2ee <- sdr accesses this 80h ;2ef
Для нашего ассемблера это выглядит как три разных области памяти. Но очень важно, чтобы все это оставалось в одном блоке. Если после инструкции DRAW $0, $1, 6h, что mvi и я разделим эти области, собранная программа выдаст неожиданные результаты.
К сожалению, хороших способов обойти это невозможно. Позже, когда мы будем писать наш ассемблер, мы можем начать думать о способах объявления переменных внутри дизассемблера. Но что касается дизассемблирования программы, мы должны предоставить ассемблеру (и человеку) некий конкретный контекст.
Я решил добавить дополнительную инструкцию под названием DATA. Это не совсем обычное дело ... Но в моем безумии есть метод.
Полный контроль
Мы внедряем чип-8 в соответствии со спецификацией. Эта спецификация позволяет нам взять любой действительный байт-код Chip-8 и запустить его. Если мы реализовали эту виртуальную машину на Arduino, та же программа Chip-8, которая работает на моем ПК, будет работать на Arduino одинаково, несмотря ни на что. Каждый раз.
Когда мы дизассемблируем какой-то байт-код Chip-8, мы начинаем попадать на более мрачную территорию. Мы можем заимствовать из других языков ассемблера, мы можем следовать некоторым соглашениям, мы можем видеть, что сделали некоторые другие люди ... но для этого нет спецификации.
Поскольку Chip-8 настолько прост и не существует спецификации по разборке, мы в значительной степени сами по себе. Когда мы пишем дизассемблер и ассемблер для нашего Chip-8, мы говорим: эти программы будут дизассемблировать и собирать действительный байт-код. Если вы хотите использовать их самостоятельно, вы должны следовать нашей спецификации.
Короче говоря, мы очень мягко вступаем в сферу создания языков - каким бы грубым или минималистичным ни был этот язык.
DATA Инструкция
Итак, мы собираемся добавить инструкцию по работе с данными.
У этой инструкции нет аналога кода операции, она чисто синтаксическая. В нем действуют следующие правила:
- Команда DATA принимает в качестве первого аргумента место в памяти.
- Команда DATA принимает в качестве второго аргумента один байт, который представляет собой данные для хранения в ранее определенной области памяти.
- Инструкция DATA должна иметь два аргумента, но может иметь до n дополнительных аргументов, которые определяют данные для хранения в начальной ячейке памяти + n-й дополнительный аргумент.
Следующая разборка эквивалентна:
DATA 2EAh, 80h DATA 2EBh, 80h DATA 2ECh, 80h DATA 2EDh, 80h DATA 2EEh, 80h DATA 2EFh, 80h //is equivalent to DATA 2EAh, 80h, 80h, 80h, 80h, 80h, 80h //is equivalent to DATA 2EAh, 80h, 80h, 80h DATA 2EDh, 80h, 80h, 80h
Для максимальной наглядности наш дизассемблер произведет первый вариант из трех вышеупомянутых. Мы сделаем это, потому что нет способа определить, какой порядок наиболее читаем для целей программы. Насколько нам известно, это всего лишь один кусок, и лучше не вдаваться в подробности.
Однако реализовать это - прогулка по торту. Мы можем добавить класс DataCode и расширить наш метод generateProgram:
Размещение всех инструкций данных после дизассемблированной программы - это стилистический выбор. Мы могли бы так же легко поставить их на место. Ассемблер будет знать, что с ними делать немедленно, несмотря ни на что, но я считаю, что более читаемым будет объявить ссылку внизу.
Давайте посмотрим на первую пару строк файла missile.c8, чтобы увидеть, получим ли мы лучшие результаты (см. Полный вывод здесь):
JMP :label-0x0219 ; addr : 200; opcode : 0x1219 :label-0x0219 MOV $C, Ch ; addr : 219; opcode : 0x6C0C MOV $0, 0h ; addr : 21B; opcode : 0x6000 MOV $1, 0h ; addr : 21D; opcode : 0x6100 MOV $5, 8h ; addr : 21F; opcode : 0x6508 MOV $6, Ah ; addr : 221; opcode : 0x660A MOV $7, 0h ; addr : 223; opcode : 0x6700 MOV $E, 1h ; addr : 225; opcode : 0x6E01 MVI 2ADh ; addr : 227; opcode : 0xA2AD :label-0x0229
Намного лучше! К разборке я добавил несколько комментариев, реализацию которых вы найдете на github.
Что дальше
Хорошо, я соврал в прошлый раз, когда сказал, что мы начнем внедрять Chip8. Создание надежного дизассемблера и точное понимание принципов работы с гайками и болтами - важный первый шаг.
Помните: мы не учимся писать эмулятор Chip-8, мы изучаем более широкие концепции, проиллюстрированные созданием Chip-8. Мы сейчас просто обводим контуры.
В следующий раз мы фактически перейдем к всем спецификациям Chip-8 и скроем простую реализацию. В процессе мы собираемся создать отладчик программы CLI. Это сведет все воедино, мы увидим, как коды операций связаны с нашей дизассемблированием, и сможем пошагово выполнять байт-код по одной инструкции за раз и наблюдать, как это влияет на виртуальную машину в целом.
