Хабрахабр

[Перевод] Пишем собственную виртуальную машину

В этом руководстве я расскажу, как написать собственную виртуальную машину (VM), способную запускать программы на ассемблере, такие как 2048 (моего друга) или Roguelike (моя). Если вы умеете программировать, но хотите лучше понять, что происходит внутри компьютера и как работают языки программирования, то этот проект для вас. Написание собственной виртуальной машины может показаться немного страшным, но я обещаю, что тема удивительно простая и поучительная.

Достаточно знать лишь основы C или C++, такие как двоичная арифметика. Окончательный код составляет около 250 строк на C. Несколько API Unix используются для настройки ввода и отображения консоли, но они не являются существенными для основного кода. Для сборки и запуска подходит любая Unix-система (включая macOS). (Реализация поддержки Windows приветствуется).

То есть вы прямо сейчас уже читаете её исходный код! Примечание: эта VM — грамотная программа. Окончательный код создан сплетением блоков кода. Каждый фрагмент кода будет показан и подробно объяснён, так что можете быть уверены: ничего не упущено. Репозиторий проекта тут.

  1. Оглавление
  2. Введение
  3. Архитектура LC-3
  4. Примеры на ассемблере
  5. Выполнение программ
  6. Реализация инструкций
  7. Шпаргалка по инструкциям
  8. Процедуры обработки прерываний
  9. Шпаргалка по процедурам обработки прерываний
  10. Загрузка программ
  11. Отображаемые в памяти регистры
  12. Особенности платформы
  13. Запуск виртуальной машины
  14. Альтернативный метод на C++

Что такое виртуальная машина?

Виртуальная машина — это программа, которая действует как компьютер. Она имитирует процессор с несколькими другими аппаратными компонентами, позволяя выполнять арифметику, считывать из памяти и записывать туда, а также взаимодействовать с устройствами ввода-вывода, словно настоящий физический компьютер. Самое главное, VM понимает машинный язык, который вы можете использовать для программирования.

Некоторые VM воспроизводят поведение одного конкретного компьютера. Сколько аппаратного обеспечения имитирует конкретная VM — зависит от её предназначения. Эти эмуляторы должны точно воссоздать каждую деталь и каждый основной аппаратный компонент оригинального устройства. У людей больше нет NES, но мы всё ещё можем играть в игры для NES, имитируя аппаратное обеспечение на программном уровне.

В первую очередь это делается для облегчения разработки ПО. Другие VM не соответствуют никакому конкретному компьютеру, а частично соответствуют сразу нескольким! Виртуальная машина даёт стандартную платформу, которая обеспечивает переносимость. Представьте, что вы хотите создать программу, работающую на нескольких компьютерных архитектурах. Достаточно сделать только небольшую VM на каждом языке. Не нужно переписывать программу на разных диалектах ассемблера для каждой архитектуры. После этого любую программу можно написать лишь единожды на языке ассемблера виртуальной машины.

VM создаёт одну стандартную архитектуру CPU, которая симулируется на различных аппаратных устройствах. Примечание: компилятор решает подобные проблемы, компилируя стандартный высокоуровневый язык для разных процессорных архитектур. Хотя компиляторы хорошо работают, написание нового компилятора для нескольких платформ очень трудно, поэтому VM всё ещё полезны. Одно из преимуществ компилятора в том, что отсутствуют накладные расходы во время выполнения, как у VM. В реальности на разных уровнях и VM, и компиляторы используются совместно.

Виртуальная машина Java (JVM) — очень успешный пример. Сама JVM относительно среднего размера, она достаточно мала для понимания программистом. Это позволяет писать код для тысяч разнообразных устройств, включая телефоны. После реализации JVM на новом устройстве любая написанная программа Java, Kotlin или Clojure может работать на нём без изменений. Единственными затратами будут только накладные расходы на саму VM и дальнейшее абстрагирование от машинного уровня. Обычно это довольно хороший компромисс.

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

Одно из применений — сборка мусора. VM также полезны для безопасной изоляции программ. Однако VM находится «вне» запущенной программы и может наблюдать все ссылки на ячейки памяти в стеке. Не существует тривиального способа реализовать автоматическую сборку мусора поверх C или C++, так как программа не может видеть собственный стек или переменные.

Смарт-контракты — это небольшие программы, которые выполняются каждым узлом валидации в блокчейне. Ещё один пример такого поведения демонстрируют смарт-контракты Ethereum. Чтобы предотвратить вредоносные действия, они выполняются на VM, не имеющей доступа к файловой системе, сети, диску и т.д. То есть операторы разрешают выполнение на своих машинах любых программ, написанных совершенно незнакомыми людьми, без какой-либо возможности изучить их заранее. Благодаря VM можно писать смарт-контракты без учёта особенностей множества платформ. Ethereum — также хороший пример переносимости.

Он популярен для обучения студентов ассемблеру. Наша VM будет симулировать вымышленный компьютер под названием LC-3. Здесь упрощённый набор команд по сравнению с x86, но сохраняются все основные концепции, которые используются в современных CPU.

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

Память

В компьютере LC-3 есть 65 536 ячеек памяти (216), каждая из которых содержит 16-разрядное значение. Это означает, что он может хранить всего 128 Кб — намного меньше, чем вы привыкли! В нашей программе эта память хранится в простом массиве:

/* 65536 locations */
uint16_t memory[UINT16_MAX];

Регистры

Регистр — это слот для хранения одного значения в CPU. Регистры подобны «верстаку» CPU. Чтобы он мог работать с каким-то фрагментом данных, тот должен находиться в одном из регистров. Но поскольку регистров всего несколько, в любой момент времени можно загрузить только минимальный объём данных. Программы обходят эту проблему, загружая значения из памяти в регистры, вычисляя значения в другие регистры, а затем сохраняя окончательные результаты обратно в память.

Большинство из них —общего назначения, но некоторым назначены роли. В компьютере LC-3 всего 10 регистров, каждый на 16 бит.

  • 8 регистров общего назначения (R0-R7)
  • 1 регистр счётчика команд (PC)
  • 1 регистр флагов условий (COND)

Регистры общего назначения могут использоваться для выполнения любых программных вычислений. Счётчик команд представляет собой целое число без знака, которое является адресом в памяти следующей инструкции для выполнения. Флаги условий сообщают нам информацию о предыдущем вычислении.

enum
{ R_R0 = 0, R_R1, R_R2, R_R3, R_R4, R_R5, R_R6, R_R7, R_PC, /* program counter */ R_COND, R_COUNT
};

Как и память, будем хранить регистры в массиве:

uint16_t reg[R_COUNT];

Набор инструкций

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

В LC-3 всего 16 опкодов. Каждый опкод представляет собой одну задачу, которую процессор «знает», как выполнить. Длина каждой инструкции 16 бит, а левые 4 бита хранят код операции. Компьютер может вычислить только последовательность этих простых инструкций. Остальные используются для хранения параметров.

На данный момент определите следующие опкоды. Позже подробно обсудим, что делает каждая инструкция. Удостоверьтесь, что сохраняют такой порядок, чтобы получать правильное значение enum:

enum
{ OP_BR = 0, /* branch */ OP_ADD, /* add */ OP_LD, /* load */ OP_ST, /* store */ OP_JSR, /* jump register */ OP_AND, /* bitwise and */ OP_LDR, /* load register */ OP_STR, /* store register */ OP_RTI, /* unused */ OP_NOT, /* bitwise not */ OP_LDI, /* load indirect */ OP_STI, /* store indirect */ OP_JMP, /* jump */ OP_RES, /* reserved (unused) */ OP_LEA, /* load effective address */ OP_TRAP /* execute trap */
};

Небольшие наборы инструкций называются RISC, а более крупные — CISC. Примечание: в архитектуре Intel x86 сотни инструкций, в то время как в других архитектурах, таких как ARM и LC-3, очень мало. Одна инструкция CISC может заменить несколько инструкций RISC. Большие наборы инструкций, как правило, не предоставляют принципиально новых возможностей, но часто упрощают написание ассемблерного кода. Это и другие компромиссы не позволяют назвать «оптимальный» дизайн. Однако процессоры CISC более сложны и дороги в проектировании и производстве.

Флаги условий

Регистр R_COND хранит флаги условий, которые предоставляют информацию о последнем выполненном вычислении. Это позволяет программам проверять логические условия, такие как if (x > 0) .

LC-3 использует только три флага условий, которые показывают знак предыдущего вычисления. У каждого процессора множество флагов состояния для сигнализации о различных ситуациях.

enum
{ FL_POS = 1 << 0, /* P */ FL_ZRO = 1 << 1, /* Z */ FL_NEG = 1 << 2, /* N */
};

(n << k) сдвигает биты n влево на k мест. Примечание: (Символ << называется оператором левого сдвига. Почитайте здесь, если не знакомы с концепцией. Таким образом, 1 << 2 равняется 4. Это будет очень важно).

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

{Includes, 12} {Registers, 3}
{Opcodes, 3}
{Condition Flags, 3}

Здесь указаны ссылки на пронумерованные разделы статьи, откуда берутся соответствующие фрагменты кода. Полный листинг см. в рабочей программе — прим. пер.
Теперь рассмотрим программу на ассемблере LC-3, чтобы получить представление, что фактически выполняет виртуальная машина. Вам не нужно знать, как программировать на ассемблере, или всё тут понимать. Просто постарайтесь получить общее представление, что происходит. Вот простой «Hello World»:

.ORIG x3000 ; this is the address in memory where the program will be loaded
LEA R0, HELLO_STR ; load the address of the HELLO_STR string into R0
PUTs ; output the string pointed to by R0 to the console
HALT ; halt the program
HELLO_STR .STRINGZ "Hello World!" ; store this string here in the program
.END ; mark the end of the file

Как и в C, программа выполняет по одному оператору сверху вниз. Но в отличие от C, здесь нет вложенных областей {} или управляющих структур, таких как if или while; только простой список операторов. Поэтому его гораздо легче выполнить.

Мы знаем, что в инструкциях по 16 бит, но каждая строка выглядит как будто с разным количеством символов. Обратите внимание, что имена некоторых операторов соответствуют опкодам, которые мы определили ранее. Как возможно такое несоответствие?

Инструмент, называемый ассемблером, преобразует каждую строку текста в 16-разрядную двоичную инструкцию, понятную виртуальной машине. Это происходит потому что код, который мы читаем, написан на ассемблере — в удобочитаемой и доступной для записи форме обычным текстом. Эта двоичная форма, которая по сути представляет собой массив 16-разрядных инструкций, называется машинным кодом и фактически выполняется виртуальной машиной.

Ассемблер просто кодирует то, что программист написал в тексте, заменяя символы их двоичным представлением и упаковывая их в инструкции. Примечание: хотя компилятор и ассемблер играют схожую роль в разработке, они не одинаковы.

Команды .ORIG и .STRINGZ выглядят как инструкции, но нет. Это директивы ассемблера, которые генерируют часть кода или данных. Например, .STRINGZ вставляет строку символов в указанном месте двоичной программы.

Вот еще один пример, который считает до 10. Циклы и условия выполняются с помощью goto-подобной инструкции.

AND R0, R0, 0 ; clear R0
LOOP ; label at the top of our loop
ADD R0, R0, 1 ; add 1 to R0 and store back in R0
ADD R1, R0, -10 ; subtract 10 from R0 and store back in R1
BRn LOOP ; go back to LOOP if the result was negative
... ; R0 is now 10!

Но если вам интересно, можете написать и собрать собственные программы LC-3 с помощью LC-3 Tools. Примечание: для этого руководства необязательно учиться ассемблеру.

Ещё раз, предыдущие примеры просто дают представление, что делает VM. Для написания VM вам не нужно полное понимание ассемблера. Пока вы следуете соответствующей процедуре чтения и исполнения инструкций, любая программа LC-3 будет корректно работать, независимо от её сложности. В теории, VM может запустить даже браузер или операционную систему, как Linux!

Сами программы могут производить сколь угодно сложные действия, которые мы никогда не ожидали и, возможно, не сможем понять. Если глубоко задуматься, то это философски замечательная идея. Мы одновременно знаем всё и ничего о том, как работает каждая программа. Но в то же время вся их функциональность ограничивается простым кодом, который мы напишем! Тьюринг упоминал эту чудесную идею:

Я имею в виду предположение о том, что коль скоро какой-то факт стал достоянием разума, тотчас же достоянием разума становятся все следствия из этого факта». «Мнение о том, что машины не могут чем-либо удивить человека, основывается, как я полагаю, на одном заблуждении, которому в особенности подвержены математики и философы. Тьюринг — Алан М.

Процедура

Вот точное описание процедуры, которую нужно написать:

  1. Загрузить одну инструкцию из памяти по адресу регистра PC.
  2. Увеличить регистр PC.
  3. Посмотреть опкод, чтобы определить, какой тип инструкции выполнять.
  4. Выполнить инструкцию, используя её параметры.
  5. Вернуться к шагу 1.

Вы можете задать вопрос: «Но если цикл продолжает увеличивать счётчик в отсутствие if или while, инструкции разве не закончатся?» Ответ отрицательный. Как мы уже упоминали, некоторые goto-подобные инструкции изменяют поток выполнения, прыгая вокруг PC.

Начнём изучение этого процесса на примере основного цикла:

int main(int argc, const char* argv[])
{ {Load Arguments, 12} {Setup, 12} /* set the PC to starting position */ /* 0x3000 is the default */ enum { PC_START = 0x3000 }; reg[R_PC] = PC_START; int running = 1; while (running) { /* FETCH */ uint16_t instr = mem_read(reg[R_PC]++); uint16_t op = instr >> 12; switch (op) { case OP_ADD: {ADD, 6} break; case OP_AND: {AND, 7} break; case OP_NOT: {NOT, 7} break; case OP_BR: {BR, 7} break; case OP_JMP: {JMP, 7} break; case OP_JSR: {JSR, 7} break; case OP_LD: {LD, 7} break; case OP_LDI: {LDI, 6} break; case OP_LDR: {LDR, 7} break; case OP_LEA: {LEA, 7} break; case OP_ST: {ST, 7} break; case OP_STI: {STI, 7} break; case OP_STR: {STR, 7} break; case OP_TRAP: {TRAP, 8} break; case OP_RES: case OP_RTI: default: {BAD OPCODE, 7} break; } } {Shutdown, 12}
}

Теперь ваша задача — сделать правильную реализацию для каждого опкода. Подробная спецификация каждой инструкции содержится в документации проекта. Из спецификации нужно узнать, как работает каждая инструкция, и написать реализацию. Это проще, чем кажется. Здесь я продемонстрирую, как реализовать две из них. Код для остальных можно найти в следующем разделе.

ADD

Инструкция ADD берёт два числа, складывает их и сохраняет результат в регистре. Спецификация в документации на стр. 526. Каждая инструкция ADD выглядит следующим образом:

Прежде чем я объясню режимы, давайте попробуем найти сходство между ними. На схеме две строки, потому что для этой инструкции есть два различных «режима». Это значение опкода для OP_ADD. Обе они начинаются с четырёх одинаковых битов 0001. Выходной регистр — это место хранения суммы. Следующие три бита помечены DR для выходного регистра. Это регистр, содержащий первое добавляемое число. Следующие три бита: SR1.

Осталось только узнать второе число для сложения. Таким образом, мы знаем, где сохранить результат, и знаем первое число для сложения. Обратите внимание, что вверху 5-й бит равен 0, а внизу — 1. Здесь две строки начинают различаться. В регистровом режиме второе число хранится в регистре, как и первое. Этот бит соответствует или непосредственному режиму, или регистровому режиму. Биты 3 и 4 не используются. Оно отмечено как SR2 и содержится в битах со второго по нулевой. На ассемблере это будет написано так:

ADD R2 R0 R1 ; add the contents of R0 to R1 and store in R2.

В непосредственном режиме вместо добавления содержимого регистра непосредственное значение внедряется в саму инструкцию. Это удобно, потому что программе не нужны дополнительные инструкции для загрузки этого числа в регистр из памяти. Вместо этого оно уже внутри инструкции, когда нам нужно. Компромисс в том, что там могут храниться только небольшие числа. Если быть точным, максимум 25=32. Это наиболее полезно для увеличения счётчиков или значений. На ассемблере можно написать так:

ADD R0 R0 1 ; add 1 to R0 and store back in R0

Вот выдержка из спецификации:

Если бит [5] равен 1, то второй исходный операнд получают путём расширения значения imm5 до 16 бит. Если бит [5] равен 0, то второй исходный операнд получают из SR2. (стр. 526) В обоих случаях второй исходный операнд добавляется к содержимому SR1, а результат сохраняется в DR.

Это похоже на то, что мы обсуждали. Но что такое «расширение значения»? Хотя в непосредственном режиме у значения только 5 бит, его нужно сложить с 16-разрядным числом. Эти 5 бит следует расширить до 16, чтобы соответствовать другому числу. Для положительных чисел мы можем заполнить недостающие биты нулями и получить такое же значение. Однако для отрицательных чисел это не работает. Например, −1 в пяти битах равно 1 1111. Если просто заполнить нулями, получим 0000 0000 0001 1111, что равно 32! Расширение значения предотвращает эту проблему, заполняя биты нулями для положительных чисел и единицами для отрицательных чисел.

uint16_t sign_extend(uint16_t x, int bit_count)
{ if ((x >> (bit_count - 1)) & 1) { x |= (0xFFFF << bit_count); } return x;
}

Но это не существенно. Примечание: если вас интересуют двоичные отрицательные числа, можете прочитать о дополнительном коде. Достаточно просто скопировать код выше и использовать его, когда спецификация говорит расширить значение.

В спецификации есть последнее предложение:

(стр. 526) Коды условий задаются в зависимости от того, является ли результат отрицательным, нулевым или положительным.

Ранее мы определили условие flags enum, а теперь пришло время использовать этих флаги. Каждый раз, когда значение записывается в регистр, нам нужно обновить флаги, чтобы указать его знак. Напишем функцию для повторного использования:

void update_flags(uint16_t r)
{ if (reg[r] == 0) { reg[R_COND] = FL_ZRO; } else if (reg[r] >> 15) /* a 1 in the left-most bit indicates negative */ { reg[R_COND] = FL_NEG; } else { reg[R_COND] = FL_POS; }
}

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

{ /* destination register (DR) */ uint16_t r0 = (instr >> 9) & 0x7; /* first operand (SR1) */ uint16_t r1 = (instr >> 6) & 0x7; /* whether we are in immediate mode */ uint16_t imm_flag = (instr >> 5) & 0x1; if (imm_flag) { uint16_t imm5 = sign_extend(instr & 0x1F, 5); reg[r0] = reg[r1] + imm5; } else { uint16_t r2 = instr & 0x7; reg[r0] = reg[r1] + reg[r2]; } update_flags(r0);
}

В этом разделе много информации, поэтому подведём итоги.

  • ADD берёт два значения и сохраняет их в регистре.
  • В регистровом режиме второе добавляемое значение находится в регистре.
  • В непосредственном режиме второе значение внедряется в правые 5 бит инструкции.
  • Значения короче 16 бит следует расширить.
  • Каждый раз, когда инструкция изменяет регистр, следует обновить флаги условий.

Вы можете быть ошеломлены написанием ещё 15 инструкций. Однако полученную здесь информацию можно использовать повторно. В большинстве инструкций используется комбинация расширения значения, различных режимов и обновления флагов.

LDI

LDI означает «косвенную» или «непрямую» загрузку (load indirect). Эта инструкция используется для загрузки в регистр значения из места в памяти. Спецификация на стр. 532.

Вот как выглядит двоичная компоновка:

На этот раз код операции 1010, что соответствует значению enum OP_LDI. В отличие от ADD, здесь нет режимов и меньше параметров. Остальные биты помечены как PCoffset9. Опять же мы видим трёхбитный DR (выходной регистр) для хранения загруженного значения. Поскольку инструкция загружается из памяти, мы можем догадаться, что это число является своего рода адресом, который говорит, откуда загружать значение. Это непосредственное значение, встроенное в инструкцию (аналогично imm5). Спецификация объясняет подробнее:

Что хранится в памяти по этому адресу — это адрес данных, которые будут загружены в DR. Адрес вычисляется с помощью расширения битов значения [8:0] до 16 бит и добавления этого значения к увеличенному PC. (стр. 532)

Как и раньше, нужно расширить это 9-битное значение, но на этот раз добавить его к текущему PC. (Если вы посмотрите на цикл выполнения, PC увеличился сразу после загрузки этой инструкции). Результирующая сумма — это адрес местоположения в памяти, и этот адрес содержит ещё одно значение, которое является адресом загружаемого значения.

Инструкция LD ограничена адресным смещением 9 бит, тогда как память требует для адреса 16 бит. Это может показаться окольным путём для чтения из памяти, но так нужно. Вы можете думать о ней как о локальной переменной в C, которая является указателем на некоторые данные: LDI полезна для загрузки значений, которые хранятся где-то за пределами текущего компьютера, но для их использования адрес конечного местоположения должен храниться рядом.

// the value of far_data is an address
// of course far_data itself (the location in memory containing the address) has an address
char* far_data = "apple"; // In memory it may be layed out like this: // Address Label Value
// 0x123: far_data = 0x456
// ...
// 0x456: string = 'a' // if PC was at 0x100
// LDI R0 0x023
// would load 'a' into R0

Как и раньше, после записи значения в DR следует обновить флаги:

(стр. 532) Коды условий задаются в зависимости от того, является ли результат отрицательным, нулевым или положительным.

Вот код для данного случая: (mem_read обсудим в следующем разделе):

{ /* destination register (DR) */ uint16_t r0 = (instr >> 9) & 0x7; /* PCoffset 9*/ uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); /* add pc_offset to the current PC, look at that memory location to get the final address */ reg[r0] = mem_read(mem_read(reg[R_PC] + pc_offset)); update_flags(r0);
}

Как я уже сказал, для этой инструкции мы использовали значительную часть кода и знаний, полученных ранее при написании ADD. То же самое с остальными инструкциями.

Следуйте спецификации и используйте уже написанный код. Теперь необходимо реализовать остальные инструкции. Два из перечисленных ранее опкодов нам не понадобятся: это OP_RTI и OP_RES. Код для всех инструкций приведён в конце статьи. Когда закончите, основную часть вашей VM можно считать завершённой! Можно их проигнорировать или выдать ошибку, если они вызываются.

В этом разделе — полные реализации оставшихся инструкций, если вы застряли.

RTI & RES

(не используются)

abort();

Битовое «И»

{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; uint16_t imm_flag = (instr >> 5) & 0x1; if (imm_flag) { uint16_t imm5 = sign_extend(instr & 0x1F, 5); reg[r0] = reg[r1] & imm5; } else { uint16_t r2 = instr & 0x7; reg[r0] = reg[r1] & reg[r2]; } update_flags(r0);
}

Битовое «НЕ»

{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; reg[r0] = ~reg[r1]; update_flags(r0);
}

Branch

{ uint16_t pc_offset = sign_extend((instr) & 0x1ff, 9); uint16_t cond_flag = (instr >> 9) & 0x7; if (cond_flag & reg[R_COND]) { reg[R_PC] += pc_offset; }
}

Jump

RET указана как отдельная инструкция в спецификации, так как это другая команда в ассемблере. На самом деле это особый случай JMP. RET происходит всякий раз, когда R1 равно 7.

{ /* Also handles RET */ uint16_t r1 = (instr >> 6) & 0x7; reg[R_PC] = reg[r1];
}

Jump Register

{ uint16_t r1 = (instr >> 6) & 0x7; uint16_t long_pc_offset = sign_extend(instr & 0x7ff, 11); uint16_t long_flag = (instr >> 11) & 1; reg[R_R7] = reg[R_PC]; if (long_flag) { reg[R_PC] += long_pc_offset; /* JSR */ } else { reg[R_PC] = reg[r1]; /* JSRR */ } break;
}

Load

{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); reg[r0] = mem_read(reg[R_PC] + pc_offset); update_flags(r0);
}

Load Register

{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; uint16_t offset = sign_extend(instr & 0x3F, 6); reg[r0] = mem_read(reg[r1] + offset); update_flags(r0);
}

Эффективный адрес Load

{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); reg[r0] = reg[R_PC] + pc_offset; update_flags(r0);
}

Store

{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); mem_write(reg[R_PC] + pc_offset, reg[r0]);
}

Store Indirect

{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t pc_offset = sign_extend(instr & 0x1ff, 9); mem_write(mem_read(reg[R_PC] + pc_offset), reg[r0]);
}

Store Register

{ uint16_t r0 = (instr >> 9) & 0x7; uint16_t r1 = (instr >> 6) & 0x7; uint16_t offset = sign_extend(instr & 0x3F, 6); mem_write(reg[r1] + offset, reg[r0]);
}

LC-3 обеспечивает несколько предопределённых подпрограмм для выполнения общих задач и взаимодействия с устройствами ввода-вывода. Например, есть процедуры для получения ввода с клавиатуры и вывода строк на консоль. Они называются программами обработки системных прерываний (trap routines), которые вы можете представлять как операционную систему или API для LC-3. Каждой подпрограмме присваивается код прерывания (trap-код), который её идентифицирует (аналогично опкоду). Для её выполнения вызывается инструкция TRAP с кодом нужной подпрограммы.

Установим enum для каждого кода прерывания:

enum
{ TRAP_GETC = 0x20, /* get character from keyboard */ TRAP_OUT = 0x21, /* output a character */ TRAP_PUTS = 0x22, /* output a word string */ TRAP_IN = 0x23, /* input a string */ TRAP_PUTSP = 0x24, /* output a byte string */ TRAP_HALT = 0x25 /* halt the program */
};

Вам может быть интересно, почему коды прерываний не включены в инструкции. Это потому что они фактически не добавляют LC-3 никакой новой функциональности, а только обеспечивают удобный способ выполнения задачи (подобно системным функциям в C). В официальном симуляторе LC-3 коды прерываний написаны на ассемблере. При вызове кода прерывания компьютер перемещается по адресу этого кода. CPU выполняет инструкции процедуры, а по завершении PC сбрасывается в местоположение, откуда было вызвано прерывание.

Нижние адреса остаются пустыми, чтобы оставить место для кода подпрограммы обработки прерываний. Примечание: вот почему программы начинаются с адреса 0x3000 вместо 0x0.

Нет никакой спецификации, как реализовать подпрограммы обработки прерываний: только то, что они должны делать. В нашей VM мы поступим немного иначе, написав их на C. При вызове кода прерывания будет вызвана функция C. После её работы продолжится выполнение инструкции.

Вместо написания собственных примитивных процедур ввода-вывода можно воспользоваться теми, которые доступны на нашей ОС. Хотя процедуры можно написать на ассемблере и в физическом компьютере LC-3 так и будет, это не лучший вариант для VM. Это улучшит работу виртуальной машины на наших компьютерах, упростит код и обеспечит более высокий уровень абстракции для переносимости.

В ассемблерной версии используется цикл для непрерывной проверки ввода клавиатуры. Примечание: одним из конкретных примеров является ввод с клавиатуры. При использовании надлежащей функции ОС программа может спокойно спать до входного сигнала. Но ведь так впустую тратится много процессорного времени!

В оператор множественного выбора для опкода TRAP добавим ещё один switch:

switch (instr & 0xFF)
{ case TRAP_GETC: {TRAP GETC, 9} break; case TRAP_OUT: {TRAP OUT, 9} break; case TRAP_PUTS: {TRAP PUTS, 8} break; case TRAP_IN: {TRAP IN, 9} break; case TRAP_PUTSP: {TRAP PUTSP, 9} break; case TRAP_HALT: {TRAP HALT, 9} break;
}

Как и в случае с инструкциями, я покажу, как реализовать одну процедуру, а остальное сделаете сами.

PUTS

Код прерывания PUTS используется для выдачи строки с завершающим нулём (аналогично printf в C). Спецификация на стр. 543.

Это делается путём сохранения адреса первого символа в R0 перед началом обработки. Чтобы отобразить строку, мы должны дать подпрограмме обработки прерываний строку для отображения.

Из спецификации:

Символы содержатся в последовательных ячейках памяти, по одному символу на ячейку, начиная с адреса, указанного в R0. Выведите строку символов ASCII на дисплей консоли. (стр. 543) Вывод завершается, когда в памяти встречается значение x0000.

Обратите внимание, что в отличие от строк C, здесь символы хранятся не в одном байте, а по одному расположению в памяти. Расположение в памяти LC-3 составляет 16 бит, поэтому у каждого символа в строке размер 16 бит. Чтобы отобразить это в функции C, нужно преобразовать каждое значение в символ и вывести их по отдельности.

{ /* one char per word */ uint16_t* c = memory + reg[R_R0]; while (*c) { putc((char)*c, stdout); ++c; } fflush(stdout);
}

Для данной процедуры больше ничего не требуется. Подпрограммы обработки прерываний довольно просты, если вы знаете C. Теперь вернитесь к спецификации и реализуйте остальные. Как и в случае с инструкциями, полный код можно найти в конце этого руководства.
Этот раздел содержит полные реализации остальных подпрограмм обработки прерываний.

Ввод символа

/* read a single ASCII char */
reg[R_R0] = (uint16_t)getchar();

Вывод символа

putc((char)reg[R_R0], stdout);
fflush(stdout);

Запрос ввода символа

printf("Enter a character: ");
reg[R_R0] = (uint16_t)getchar();

Вывод строки

{ /* one char per byte (two bytes per word) here we need to swap back to big endian format */ uint16_t* c = memory + reg[R_R0]; while (*c) { char char1 = (*c) & 0xFF; putc(char1, stdout); char char2 = (*c) >> 8; if (char2) putc(char2, stdout); ++c; } fflush(stdout);
}

Прекращение выполнения программы

puts("HALT");
fflush(stdout);
running = 0;

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

Этот адрес называется origin. Первые 16 бит файла программы указывают адрес в памяти, где следует начать выполнение программы. Он должен быть прочитан первым, после чего в память из файла считываются остальные данные.

Вот код для загрузки программы в память LC-3:

void read_image_file(FILE* file)
{ /* the origin tells us where in memory to place the image */ uint16_t origin; fread(&origin, sizeof(origin), 1, file); origin = swap16(origin); /* we know the maximum file size so we only need one fread */ uint16_t max_read = UINT16_MAX - origin; uint16_t* p = memory + origin; size_t read = fread(p, sizeof(uint16_t), max_read, file); /* swap to little endian */ while (read-- > 0) { *p = swap16(*p); ++p; }
}

Обратите внимание, что для каждого загруженного значения вызывается swap16. Программы LC-3 записаны в прямом порядке байтов, но большинство современных компьютеров используют обратный порядок. В результате нам нужно перевернуть каждый загруженный uint16. (Если вы случайно используете странный компьютер вроде PPC, то ничего менять не надо).

uint16_t swap16(uint16_t x)
{ return (x << 8) | (x >> 8);
}

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

Добавим также удобную функцию для read_image_file, которая принимает путь для строки:

int read_image(const char* image_path)
{ FILE* file = fopen(image_path, "rb"); if (!file) { return 0; }; read_image_file(file); fclose(file); return 1;
}

Некоторые специальные регистры недоступны из обычной таблицы регистров. Вместо этого для них в памяти зарезервирован специальный адрес. Чтобы читать и писать в эти регистры, вы просто читаете и записываете в их память. Они называются отображаемыми в памяти регистрами. Обычно они используются для взаимодействия со специальными аппаратными устройствами.

Это регистр состояния клавиатуры (KBSR) и регистр данных клавиатуры (KBDR). Для нашей LC-3 нужно реализовать два отображаемых в памяти регистра. Первый указывает, была ли нажата клавиша, а второй определяет, какая именно клавиша нажата.

KBSR и KBDR позволяют опрашивать состояние устройства, продолжая выполнение программы, так что она остаётся отзывчивой во время ожидания ввода. Хотя ввод с клавиатуры можно запросить с помощью GETC, это блокирует выполнение до получения ввода.

enum
{ MR_KBSR = 0xFE00, /* keyboard status */ MR_KBDR = 0xFE02 /* keyboard data */
};

Отображаемые в памяти регистры немного усложняют доступ к памяти. Мы не можем читать и записывать в массив памяти напрямую, а вместо этого должны вызывать специальные функции — сеттер и геттер. После чтения памяти из регистра KBSR геттер проверит клавиатуру и обновляет оба местоположения в памяти.

void mem_write(uint16_t address, uint16_t val)
{ memory[address] = val;
} uint16_t mem_read(uint16_t address)
{ if (address == MR_KBSR) { if (check_key()) { memory[MR_KBSR] = (1 << 15); memory[MR_KBDR] = getchar(); } else { memory[MR_KBSR] = 0; } } return memory[address];
}

Это последний компонент виртуальной машины! Если вы реализовали остальные процедуры обработки прерываний и инструкции, то почти готовы попробовать её!

Всё написанное следует добавить в файл C в следующем порядке:

{Memory Mapped Registers, 11}
{TRAP Codes, 8} {Memory Storage, 3}
{Register Storage, 3} {Functions, 12} {Main Loop, 5}

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

Если пытаетесь запустить VM в операционной системе, отличной от Unix, например Windows, эти функции нужно заменить на соответствующие функции Windows.

uint16_t check_key()
{ fd_set readfds; FD_ZERO(&readfds); FD_SET(STDIN_FILENO, &readfds); struct timeval timeout; timeout.tv_sec = 0; timeout.tv_usec = 0; return select(1, &readfds, NULL, NULL, &timeout) != 0;
}

Код для извлечения пути из аргументов программы и вывода примера использования, если они отсутствуют.

if (argc < 2)
{ /* show usage string */ printf("lc3 [image-file1] ...\n"); exit(2);
} for (int j = 1; j < argc; ++j)
{ if (!read_image(argv[j])) { printf("failed to load image: %s\n", argv[j]); exit(1); }
}

Специфичный для Unix код настройки ввода с терминала.

struct termios original_tio; void disable_input_buffering()
{ tcgetattr(STDIN_FILENO, &original_tio); struct termios new_tio = original_tio; new_tio.c_lflag &= ~ICANON & ~ECHO; tcsetattr(STDIN_FILENO, TCSANOW, &new_tio);
} void restore_input_buffering()
{ tcsetattr(STDIN_FILENO, TCSANOW, &original_tio);
}

Когда программа прерывается, мы хотим вернуть нормальные настройки консоли.

void handle_interrupt(int signal)
{ restore_input_buffering(); printf("\n"); exit(-2);
}

signal(SIGINT, handle_interrupt);
disable_input_buffering();

restore_input_buffering();

{Sign Extend, 6}
{Swap, 10}
{Update Flags, 6}
{Read Image File, 10}
{Read Image, 10}
{Check Key, 12}
{Memory Access, 11}
{Input Buffering, 12}
{Handle Interrupt, 12}

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <signal.h>
#include <unistd.h>
#include <fcntl.h> #include <sys/time.h>
#include <sys/types.h>
#include <sys/termios.h>
#include <sys/mman.h>

Теперь вы можете собрать и запустить виртуальную машину LC-3!

  1. Скомпилируйте программу любимым компилятором.
  2. Загрузите собранную версию 2048 или Rogue.
  3. Запустите программу с obj-файлом в качестве аргумента:
    lc3-vm path/to/2048.obj
  4. Играйте в 2048!

Control the game using WASD keys.
Are you on an ANSI terminal (y/n)? y
+--------------------------+
| |
| |
| |
| 2 |
| |
| 2 |
| |
| |
| |
+--------------------------+

Отладка

Если программа работает неправильно, скорее всего, вы неправильно закодировали какую-то инструкцию. Это может быть сложно отладить. Рекомендую одновременно читать ассемблерный код программы — и с помощью отладчика пошагово выполнять инструкции виртуальной машины по одной. При чтении кода убедитесь, что VM переходит к положенной инструкции. Если возникнет несоответствие, то вы узнаете, какая инструкция вызвала проблему. Перечитайте спецификацию и перепроверьте код.
Здесь показан продвинутый способ выполнения инструкций, который значительно уменьшает размер кода. Это совершенно необязательный раздел.

Этот метод уменьшает дублирование кода и на самом деле ближе к аппаратному уровню работы компьютера. Поскольку C++ поддерживает мощные дженерики в процессе компиляции, мы можем создавать части инструкций с помощью компилятора.

Например, некоторые инструкции используют косвенную адресацию или расширение значения и добавление его к текущему значению PC. Идея в том, чтобы повторно использовать шаги, общие для каждой инструкции. Согласитесь, неплохо было бы написать этот код один раз для всех инструкций?

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

template <unsigned op>
void ins(uint16_t instr)
{ uint16_t r0, r1, r2, imm5, imm_flag; uint16_t pc_plus_off, base_plus_off; uint16_t opbit = (1 << op); if (0x4EEE & opbit) { r0 = (instr >> 9) & 0x7; } if (0x12E3 & opbit) { r1 = (instr >> 6) & 0x7; } if (0x0022 & opbit) { r2 = instr & 0x7; imm_flag = (instr >> 5) & 0x1; imm5 = sign_extend((instr) & 0x1F, 5); } if (0x00C0 & opbit) { // Base + offset base_plus_off = reg[r1] + sign_extend(instr & 0x3f, 6); } if (0x4C0D & opbit) { // Indirect address pc_plus_off = reg[R_PC] + sign_extend(instr & 0x1ff, 9); } if (0x0001 & opbit) { // BR uint16_t cond = (instr >> 9) & 0x7; if (cond & reg[R_COND]) { reg[R_PC] = pc_plus_off; } } if (0x0002 & opbit) // ADD { if (imm_flag) { reg[r0] = reg[r1] + imm5; } else { reg[r0] = reg[r1] + reg[r2]; } } if (0x0020 & opbit) // AND { if (imm_flag) { reg[r0] = reg[r1] & imm5; } else { reg[r0] = reg[r1] & reg[r2]; } } if (0x0200 & opbit) { reg[r0] = ~reg[r1]; } // NOT if (0x1000 & opbit) { reg[R_PC] = reg[r1]; } // JMP if (0x0010 & opbit) // JSR { uint16_t long_flag = (instr >> 11) & 1; pc_plus_off = reg[R_PC] + sign_extend(instr & 0x7ff, 11); reg[R_R7] = reg[R_PC]; if (long_flag) { reg[R_PC] = pc_plus_off; } else { reg[R_PC] = reg[r1]; } } if (0x0004 & opbit) { reg[r0] = mem_read(pc_plus_off); } // LD if (0x0400 & opbit) { reg[r0] = mem_read(mem_read(pc_plus_off)); } // LDI if (0x0040 & opbit) { reg[r0] = mem_read(base_plus_off); } // LDR if (0x4000 & opbit) { reg[r0] = pc_plus_off; } // LEA if (0x0008 & opbit) { mem_write(pc_plus_off, reg[r0]); } // ST if (0x0800 & opbit) { mem_write(mem_read(pc_plus_off), reg[r0]); } // STI if (0x0080 & opbit) { mem_write(base_plus_off, reg[r0]); } // STR if (0x8000 & opbit) // TRAP { {TRAP, 8} } //if (0x0100 & opbit) { } // RTI if (0x4666 & opbit) { update_flags(r0); }
}

static void (*op_table[16])(uint16_t) = { ins<0>, ins<1>, ins<2>, ins<3>, ins<4>, ins<5>, ins<6>, ins<7>, NULL, ins<9>, ins<10>, ins<11>, ins<12>, NULL, ins<14>, ins<15>
};

Примечание: я узнал об этой технике из эмулятора NES, разработанного Bisqwit. Если вас интересует эмуляция или NES, настоятельно рекомендую его видеоролики.

Полная версия здесь. Остальные версии C++ использует уже написанный код.

{Includes, 12} {Registers, 3}
{Condition Flags, 3}
{Opcodes, 3} {Memory Mapped Registers, 11}
{TRAP Codes, 8} {Memory Storage, 3}
{Register Storage, 3} {Functions, 12} int running = 1;
{Instruction C++, 14}
{Op Table, 14} int main(int argc, const char* argv[])
{ {Load Arguments, 12} {Setup, 12} enum { PC_START = 0x3000 }; reg[R_PC] = PC_START; while (running) { uint16_t instr = mem_read(reg[R_PC]++); uint16_t op = instr >> 12; op_table[op](instr); } {Shutdown, 12}
}

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть