8-битный Тьюринг-полный компьютер в Factorio

Хочу поделиться своим проектом, созданным в Factorio на основе предлагаемой этой игрой логики. На этот проект меня вдохновил великий ум, записавший пошаговое руководство по созданию практически такой же машины, но в реальном мире. Рекомендую посмотреть его, оно поможет вам понять и воссоздать этот проект: 8-bit computer

Я преклоняю голову перед Беном Итером, с помощью своего канала научившему меня столь многому, и хочу посвятить этот небольшой проект ему. Отличная работа, Бен!

Вот компьютер, вычисляющий число Фибоначчи, после превышения лимита 8 бит (числа 255) он выполняет условный переход и начинает заново:

Давайте разберёмся, как работает этот компьютер. И не бойтесь — уверен, что, разобравшись с основами, вы тоже сможете его сделать! Начнём с общей схемы компьютера. Здесь я выделил важные области. Ниже я объясню, как создал их.

CLK — таймер, обеспечивающий синхронизацию машины. Современные ЦП способны работать с частотой 4-5 ГГц (4-5 000 000 000 Гц). На данный момент моя машина может работать с частотой 2 Гц из-за ограничений логических затворов Factorio — каждый ввод должен вычисляться для каждого комбинатора (затвора), так что если их у нас 10 в ряд, то нам нужно подождать 10 игровых тактов (fps), чтобы начать следующий такт системы. В противном случае сигналы перепутаются и вычисление не будет выполнено.

PC (Program Counter, счётчик программ) — счётчик сообщает, в какой части программы мы находимся. Программы считываются из 16-байтной памяти (один байт содержит 8 бит). Счётчик считает до 16 (4 бит) в двоичном формате (0000, 0001, 0010, 0011, 0100, 0101…1111), поэтому каждое из этих вычислений даёт нам адрес регистра, который мы позже можем забрать из памяти и выполнять с ним действия. Также он содержит Jump, сбрасывающий счётчик. Мы можем ввести другое значение, чтобы перейти в конкретное место нашей памяти/кода.

BUS — главная точка соединения всех компонентов компьютера. Мы можем передавать в неё/из неё данные. Для этого мы используем сигналы управления, открывающие/закрывающие затворы каждого компонента, чтобы никогда не были открытыми более двух затворов (благодаря этому данные не перемешиваются).

ALU — наш «калькулятор», выполняющий операции сложения и вычитания (в более сложных ЦП он способен на гораздо большее!). Он мгновенно получает то, что находится в регистрах A и B, а затем выполняет логические операции (операцию мы выбираем декодером команд). Затем эти данные выводятся на шину (bus). Также ALU хранит флаги, которые можно использовать в функциях условных переходов.

Регистры A и B — они могут хранить 8-битные числа, которые позже соединяются в ALU. Оба регистра могут передавать и получать данные из шины.

Декодер адреса регистра (Register address/Decoder, RAD) — считывает 4-битный адрес из шины и декодирует, какую часть RAM мы должны считать. Например, адрес 1110 содержит значение 0000 0011 (см. изображение).

RAM — современные PC обычно имеют примерно 16 ГБ памяти (16 000 000 000 байт). У нас есть всего 16 байт… Это оставляет нам место, которого хватит на 16 команд или на меньшее количество команд, благодаря чему мы сможем хранить данные/переменные в других частях памяти. По сути, RAM здесь — это 16 разных регистров, как те, которые мы используем в другом месте, просто доступ к ним осуществляется через декодер регистров.

Регистр команд (Instruction register, IR) / декодер (decoder, DC) — мы можем помещать данные в регистр команд из BUS, а затем декодировать их, чтобы сообщать, как должна себя вести программа. Используется всего 4 бита (выделены бирюзовым цветом), что даёт нам 16 типов команд, которые можно запрограммировать. Допустим, у нас есть команда OUT, выводящая на печать то, что хранится в регистре A. Она закодирована как 1110, поэтому когда такая команда попадёт в регистр, мы сможем декодировать её и сообщить компьютеру, как действовать.

Счётчик микрокода (Microcode counter, MC) — похож на счётчик программ, но находится внутри декодера команд. Даёт нам возможность пошагового выполнения каждой команды.

LCD/Screen — на самом деле является регистром, но более сложен, поскольку печатает своё содержимое на LCD-экране (Lamp-Combinator-Display, «дисплее из фонарей и комбинаторов»).

Распределительная панель (Switch board, SB) — эта панель показывает нам, какие функции переключения мы отправляем для управления каждым из компонентов компьютера. На данный момент существует 17 разных переключателей, управляющих различными вещами. Например, если мы хотим считать из BUS в регистр A, или записать в память/регистр команд и т. п. Описанные ниже переключатели можно использовать для ручного управления машиной.

Флаги (Flags, F) — регистр для хранения флагов (перенос [T] — когда мы превышаем 8-битные значения при сложении, обнуление [O] — когда сумма/разность равна 0). Они помогут нам в командах условного перехода.

Давайте я сначала расскажу подробнее о каждом компоненте, а в конце мы посмотрим, как программировать компьютер, потому что процесс станет понятнее. Если вас интересует только программирование, то переходите к последней части статьи.

CLK — наш генератор синхронизации, самое важное в любых вычислениях. Я хотел создать генератор, одновременно имеющий высокий [C = 1] и низкий [C = 0] сигнал.

(1) Это базовый комбинатор констант, подающий сигналы на генератор. Он переходит к (2), где объединены вместе ввод и вывод. Благодаря этой конфигурации с каждым тактом игры (UPS) значение [C] увеличивается на 1. Когда оно достигает [Z], то сбрасывается до 0. То есть Z сообщает нам, сколько игровых тактов необходимо для сброса генератора. Ниже также есть простой делитель на 2, благодаря которому генератор половину времени находится в состоянии высокого сигнала, а половину — в состоянии низкого сигнала. Когда C меньше значения [Y] (которое равно половине [Z]), генератор находится в высоком состоянии, в противном случае — в низком.

Манипулятор (inserter) (4) используется в качестве вторичного генератора синхронизации на случай, если нам нужно больше контроля над тактами. Если поместить что-нибудь в первый сундук, то произойдёт такт. Если нам нужно 5 тактов, нужно поместить в него пять объектов.

(5) — это первый сигнал управления. [H] — это сокращение от команды HALT {HLT}. Когда он имеет низкое значение [H = 0], то генератор работает обычным образом, а если высокое, то переходит в ручной режим. Способствуют этому управляющие затворы, они (5a) используются для обычной работы, а когда сигнал [H] не равен 0, то включается ручной режим и выводится [C] (наш CLK).

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

Сигнал [C] перемещается по системе через зелёный провод. Я хотел выделить его на совершенно отдельный провод (например, наша шина BUS находится на красном проводе), чтобы его легко было отслеживать и нельзя было перепутать с другими сигналами.

Регистры — не пугайтесь их. Вероятно, это самая сложная часть всей системы, но важно понять, как работает вся машина.

Регистры содержат значения. В обычной жизни нам бы пришлось создавать регистр для каждого из 8 бит и других сигналов. Но, к счастью, Factorio позволяет передавать несколько сигналов по одной линии. По сути, это JK-триггеры.

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

Хранящиеся значения (1) отображаются при помощи фонарей. Включенный фонарь означает 1, отключенный — 0. Как можно увидеть, сейчас мы храним значение 1110 1001.

Чтобы вывести значение в шину, мы используем логику управления на затворе (2). При низком сигнале [K] этот затвор выводит в основную шину то, что находится внутри регистра.

Почему мы используем его, когда сигнал низкий, а не высокий? Потому что логические затворы выводят всё, что на них подаётся (красный символ *), и в результате в шине окажется сигнал [K], а нам этого не нужно, нам нужны там только [7, 6, 5, 4, 3, 2, 1, 0]. По той же причине нам нужно отфильтровывать сигналы управления при помощи затвора (3), чтобы получать [K] только тогда, когда он нам нужен.

Затвор (4) соединён и с шиной (красный провод), и с сигналами управления (зелёный провод). Как и в предыдущем случае, регистр получает ввод при низком сигнале [A]. Чтобы отфильтровать все остальные сигналы, мы используем логический затвор (4a). По сути, он берёт все вводы с шины и нежелательные сигналы управления, а затем складывает их с комбинатором (4b), вводами которого всегда являются сигналы [7, 6,… 0] = 1. Тогда если какой-то из сигналов равен 0, то он выводит каждый из этих сигналов = 1. Всё просто, правда? В таком случае в регистры попадают только те значения из шины, которые нам важны (значения 0 всё равно будут 1, они мигают на один такт, а затем остаются отключенными на протяжении всего высокого цикла CLK).

В такой ситуации, когда [C] становится высоким, затвор (6) выводит сигнал [BLACK], а затвор (6a) сводит к нулю [C]. Но поскольку на сведение к нулю требуется на 1 больше UPS, за такое короткое время затвор (6) выводит сигнал.

Этот сигнал затем переносится на затвор (7), который тоже открывается на короткое время. Затвор (7b) сводит к нулю сигнал [BLACK], чтобы он не хранился в затворе (8), который используется как хранитель нашего сигнала. Это происходит аналогично цепи CLK, потому что и ввод, и вывод соединены вместе. Если ввода нет, то он остаётся неизменным. Если мы ещё раз изменим такт, не вводя новых данных, то затвор (7a) введёт сигнал, инвертированный относительно сохранённого в регистре значения, чтобы очистить его.

Теперь, когда мы знаем, как работают распознавание изменений и регистры, нам известно практически всё.

ALU — постоянно складывает/вычитает то, что находится в регистрах (A) и (B). Мы управляем только тем, выводить ли его в шину [Z] или изменить режим на вычитание [S].

Как это работает? Чтобы разобраться целиком, рекомендую посмотреть некоторые из видео Бена Итера, потому что объяснение будет в три раза длиннее моей статьи.

Я объясню только, как создать подобный сумматор в Factorio.

Для этого нам потребуются три типа затворов: XOR (1), AND (2) и OR (3). К счастью, их достаточно легко создать. Поскольку мы можем использовать в одной линии несколько сигналов, наш первый затвор XOR и AND может быть упрощён всего до двух, и нам не нужно делать их для всех 8 бит. Благодаря этому мы можем сделать (4) частью цепи и продублировать его для каждого бита.

Вычитание выполняется сигналом [S], инвертирующим сигналы, поступающие из регистра (B).

Также ALU выводит перенос (когда сумма превышает 8 бит), обнуление и хранит его в регистре справа (F на изображении с основным компьютером).

LCD/Screen — выглядит пугающе, но, честно говоря, изготовить его было проще всего. Нужно лишь время для того, чтобы всё правильно подключить.

Сначала мы создаём регистр, вход которого управляется сигналом [P]. Затем мы умножаем каждый бит на его значение, преобразуя его в десятичную величину, чтобы получить тот же сигнал с десятичным значением (это своего рода читерство в Factorio, однако отсутствие программируемых EEPROM не даёт нам особо развернуться). Для преобразования нам достаточно взять первый бит [0] и умножить его на *1, затем взять второй бит [1] и умножить на *2, третий [2] на * 4, и так далее. В процессе мы выполняем вывод в какое-то произвольное значение для определения получившегося числа (в данном случае это [капля воды]).

LCD включается 9 шагами для чисел (3). Нам нужно просто задать те фонари, соответствующие шагам (1), а затем использовать затворы (2) для вывода значения именно туда, куда нам требуется. Просто нужно не забывать добавлять отдельный комбинатор констант (3) и подключать его только к одному специальному затвору (2). Затем мы просто подключаем друг к другу все фонари и даём им инструкции, на каком шаге они находятся (1).

RAM/регистр памяти (RAD) — здесь я объясню, как примерно устроена ОЗУ.

Мы уже знаем регистры, использующие импульсы синхронизации для хранения значений. RAM — это просто сетка из 16 (в нашем случае) разных регистров (2). Их входы управляются другим регистром (1), хранящим 4 бита [0, 1, 2, 3], который сообщает, на какую ячейку памяти мы указываем. Это реализовано при помощи декодера адреса (3), принцип работы которого похож на LED/Screen. Каждый затвор получает значение от комбинатора констант (в нашем случае 1100 bin = 10 dec), а затем выводит название сигнала соответствующего регистра (в нашем случае [M]), чтобы можно было получить доступ к значению (в нашем случае 00110 0011).

Здесь также стоит упомянуть о программировании памяти вручную. Это можно сделать при помощи сигнала [W], включённого/отключенного при помощи комбинатора констант (4). Другой комбинатор (5) позволяет нам менять адрес, а для ввода значения мы используем ещё один комбинатор (6). В конце мы просто кладём всё в сундук (7), чтобы при синхронизации вручную передавать значения в RAM, не касаясь основного CLK компьютера.

Счётчик программ (Program counter, PC) — его задача заключается в подсчёте того, на каком шаге программы мы находимся (1). При запуске он имеет значение 0000, этот адрес считывается из RAM и передаётся в регистр команд для интерпретации. После завершения команды мы можем выполнить инкремент счётчика сигналом [X], затем он становится равным 0001, и на следующей итерации этот адрес берётся из памяти, а цикл продолжается.

Разумеется, иногда нам нужно выполнять безусловный или условный переход к другим частям программы. Мы можем делать это при помощи сигнала [J]. Если он низкий (в нашем случае низкий означает активный), то он сбрасывается, считывает из шины адрес, на который должен совершить переход, и сохраняет его в регистре (2). Когда [J] снова становится высоким, через него подаёт сигналы детектор изменений (расположен прямо под 2) на PC.

Сам счётчик работает аналогично CLK, но вместо постоянного отсчитывания тактов он отсчитывает такты при обнаружении изменений в CLK (на самом деле, только когда активны X и CLK). Это можно увидеть прямо на изображении (1).

Затем сигнал можно подать на шину с помощью сигнала управления [C].

Распределительная панель (Switch board, SB) — настал подходящий момент для объяснения каждого сигнала управления, используемого в программе.

Сигналы разделены на два цвета, зелёные идут налево, красные — направо. Каждый сигнал от комбинаторов констант на самом деле передаётся как значения [-1]. То есть когда комбинаторы установлены на * != 0, они могут выводить сигнал 1. Благодаря этому, когда логика управления подаёт сигнал [1], они аннулируются, и мы получаем [0], а во всех случаях нам нужно именно это (подробнее можно прочитать в той части, где я объясняю регистры).

[H] — останавливает генератор синхронизации (переключает в ручной режим), высокий сигнал означает, что CLK не переключается.

[Q] — адрес RAM, в котором находится регистр, при высоком сигнале регистр адреса RAM сохранит значение из шины в следующем такте CLK.

[Y] — вход памяти RAM, при высоком сигнале RAM сохранит значение из шины в следующем такте CLK (по адресу, хранящемуся в регистре адреса).

[R] — вывод RAM, при высоком сигнале RAM выводит значение в шину в следующем такте CLK (из адреса, хранящегося в регистре адреса).

[V] — ввод регистра команд, при высоком сигнале регистр команд сохраняет значение из шины в следующем такте CLK.

[U] — вывод регистра команд, при высоком сигнале регистр команд выводит значение в шину в следующем такте CLK (только 4 последних бита [3, 2, 1, 0]).

[C] — вывод счётчика программ, при высоком сигнале счётчик программ выводит значение в шину в следующем такте CLK (только 4 первых бита [7, 6, 5, 4]).

[J] — ввод адреса перехода, при высоком сигнале счётчик программ задаст значение из шины в следующем такте CLK (только 4 последних бита [3, 2, 1, 0]).

[X] — увеличение значения счётчика команд, при высоком сигнале счётчик программ выполняет инкремент в следующем такте CLK.

[A] — ввод регистра A, при высоком сигнале в регистр A сохраняется значение из шины в следующем такте CLK.

[K] — вывод регистра A, при высоком сигнале из регистра A выводится значение в шину в следующем такте CLK.

[Z] — вывод ALU, при высоком сигнале ALU выводит значение в шину в следующем такте CLK.

[S] — вычитание (ALU), при высоком сигнале ALU меняет свой режим со сложения на вычитание.

[B] — ввод регистра B, при высоком сигнале в регистр B сохраняется значение из шины в следующем такте CLK.

[L] — вывод регистра B, при высоком сигнале из регистра B выводится значение в шину в следующем такте CLK.

[P] — ввод регистра LCD/screen, при высоком сигнале в регистр LCD/screen сохраняется значение из шины в следующем такте CLK, и это значение отображается.

[W] — ввод регистра флагов, при высоком сигнале регистр флагов сохраняет из ALU перенос (при превышении 8 бит), ноль (когда операция ALU = 0000 0000).

[розовый сигнал] — поднят флаг переноса [T]

[бирюзовый сигнал] — поднят флаг ноля [O]

Теперь допустим, нам нужно выполнить действие OUT: взять то, что находится в регистре A, и вывести это на LCD/screen (регистр). Чтобы сделать это вручную, нам достаточно включить (отключив комбинатор констант для определённой буквы) сигнал [K] (вывод регистра A -> шина) и сигнал [P] (шина -> ввод регистра lcd/screen), затем выполнить такт CLK.

Регистр команд / декодер / счётчик микрокода — именно здесь начинается магия. Теперь, когда мы знаем, как вручную управлять компьютером, это поможет нам понять. что нужно делать, чтобы он мог управлять собой сам.

(1) счётчик микрокода досчитает до 8 (число можно уменьшить, если нам не нужно так много), то есть мы можем выполнить 8 различных команд включения/выключения для выполнения действия в одной команде.

(2) команды считываются в регистр из шины, для этого нам нужно включить сигналы [C] (вывод счётчика команд -> шина) и [Q] (шина -> ввод адреса памяти), а затем считать RAM [R] (вывод RAM -> шина) в регистр команд [V] (шина -> регистр команд), а также выполнить инкремент счётчика [X].

Так как все перечисленные действия нужно делать каждый раз, я подключил всё это (4) напрямую к счётчику микрокода, чтобы это происходило каждый раз, когда счётчик проходит через шаги 0 и 1.

Когда в регистре что-то есть, мы можем использовать таблицы истинности, похожие на те, которые мы создали для регистра адресов RAM и вывода на LCD/screen.

Значения [D] из регистра команд (он всегда больше 8) и счётчика микрокода (всегда равного или меньшего 8) можно сложить, и при помощи полученного числа мы можем создать логические затворы. Это реализуется затворами (3).

В примере показана команда 0110 XXXX (48 + X в dec, для которой я запрограммировал команду JMP), которая затем прибавляется к шагу 2 счётчика микрокода, что дает 50.

Ещё один пример: команда ADD (0010 XXXX — 16 + X в dec); после шагов 0 и 1 микрокод будет на 2, то есть регистры 18-24 можно использовать для другой части кода (в этом случае нам нужны только 18-20, поскольку ADD — это процесс из 3 шагов).

(5) Флаги переноса обрабатываются простыми логическими затворами, ввод на них заблокирован, только если на логические затворы не подаётся перенос [T] или ноль [O].

Ниже представлен мой полный список реализованных команд (можете изменять их или добавлять собственные!):

0 NOP — 0000 XXXX — ничего не делает.

1 LDA X — 0001 XXXX — загружает значение из адреса X RAM в регистр A.

2 ADD X — 0010 XXXX — загружает значение из адреса X RAM в регистр B, а затем выводит сложение и помещает его в регистр A.

3 ADD X — 0011 XXXX — загружает значение из адреса X RAM в регистр B, а затем выводит вычитание и помещает его в регистр A.

4 STA X — 0100 XXXX — загружает значение из регистра A и сохраняет его в RAM по адресу X.

5 LDI X — 0101 XXXX — быстро загружает значение из регистра команд (только 4-битное значение) в регистр A.

6 JMP X — 0110 XXXX — безусловный (происходит всегда) переход к значению X (присваивает PC значение X).

7 JC X — 0111 XXXX — когда значение переноса [T] равно истине, выполняет переход к значению X (присваивает PC значение X).

8 JO X — 1000 XXXX — когда перенос нуля [O] равен истине, то переходит к значению X (присваивает PC значение X).

9 OUR X — 1001 XXXX — выводит на экран значение из адреса X RAM.
.
.
.
14 OUT — 1110 XXXX — выполняет вывод на экран из регистра A (X не делает ничего).

15 HLT — 1111 XXXX — останавливает генератор синхронизации (X не делает ничего).

Давайте напишем простую программу и посмотрим, как она работает!

0 LDA 3 — загружаем значение в регистр A из адреса памяти 3

1 OUT — выводим на экран значение из регистра A.

2 HLT — останавливаем CLK, то есть всю машину.

3 42 — сохранённое значение

То есть, по сути, эта программа выводит значение, сохранённое по адресу 3 RAM (0011 в двоичном формате).

Давайте преобразуем её в двоичный вид:

0 Адрес: 0000, значение: 0001 0011

1 Адрес: 0001, значение: 1110 0000

2 Адрес: 0010, значение: 1111 0000

3 Адрес: 0011, значение: 0010 1010

То есть, чтобы написать программу, нам нужно выполнить запись в память (W на панели памяти; см. часть с изображением RAM), начиная с адреса 0000, и ввести внутрь значение 0001 0011 (0001 означает команду LDA, где 0011 — это X, то есть адрес 3 в памяти).

Затем мы делаем то же самое для других команд.

Не забудьте снова включить для [W] зелёный свет и сохранить halt на счётчике.

Также можно сбросить PC, выполнив переход с помощью J (менять такт CLK не требуется).