Redcode: стандарт ICWS-88

Русский перевод: А. Скробов, декабрь 2005

Воспроизведён по статье “Core War ‛88 – A Proposed Standard” (Thomas Gettys, The Core War Newsletter, лето 1998). Авторское право © AMRAN, 1988.

Содержание

Функциональные элементы MARS

Формат инструкций

Режимы адресации

Набор команд Redcode

Вычисление фактического адреса

Синтаксис исходного кода

Приложение А

Функциональные элементы MARS

С точки зрения Redcode-программиста, MARS состоит из четырёх основных функциональных элементов: память с произвольным доступом (RAM), вычислительное устройство (ALU), две очереди потоков (FIFO), и управляющее устройство (CU). Нет видимых программисту регистров; память – единственное доступное хранилище для кода и данных.

RAM: Каждая инструкция Redcode занимает в точности одну ячейку памяти. Адресация в Redcode – относительная, т.е. лучше всего представлять себе память организованной в виде циклического списка; инструкция, ссылающаяся на адрес памяти 0, ссылается сама на себя. Каждая ячейка памяти инициализируется данными, соответствующими инструкции DAT 0 0, прежде чем будут загружены Core War-программы (далее – “бойцы”).

FIFO: Партия Core War состоит в том, что две Redcode-программы стравливаются друг с другом. Каждая из них пытается заставить другую прервать работу, выполнив недопустимую инструкцию (DAT). В течение каждого машинного такта выполняется по одной инструкции от каждой программы, всегда в одном и том же порядке. Поэтому необходимо хранить для каждого из игроков указатель на следующую инструкцию: для этого используются очереди потоков. Как будет указано далее, каждый из игроков может иметь больше одного потока. Поэтому применяются очереди, а не обычные регистры. На размеры очередей не налагается границ ни снизу, ни сверху, кроме того что в каждой должно быть по крайней мере по одному элементу, поскольку бой не может протекать без двух или более Core War-программ.

ALU: Вычислительное устройство выполняет все арифметические и логические операции, требуемые набором команд Redcode либо управляющим устройством, – например, складывает два операнда, или увеличивает указатель на следующую инструкцию.

CU: Как и в любом процессоре, управляющее устройство ответственно за выборку, декодирование и выполнение инструкций. Этапы выборки и декодирования будут подробно рассмотрены ниже, после того как будет представлен набор команд (см. раздел “вычисление фактического адреса”). Управляющее устройство должно также предоставлять интерфейс для супервизора MARS, называемого ZEUS. Супервизор, в свою очередь, предоставляет различные сервисные функции, такие как отладчик Redcode, графическое отображение боя, управление параметрами MARS и т.п. и является в большой степени зависящим от реализации.

Формат инструкций

Каждая инструкция Redcode имеет три поля: код операции и два операнда, обозначаемых A и B. Содержимое поля кода операции указывает операцию, которая будет выполняться, и режимы адресации, используемые для вычисления операндов. Для простоты удобно разделить код операции на три подполя: собственно операцию и два модификатора операндов, – хотя это необязательно. Поля операндов могут содержать любые числа от 0 до (размер памяти – 1). В настоящий момент определены одиннадцать операций Redcode. Они перечислены в таблице ниже вместе с мнемониками и короткими описаниями выполняемых действий.

Набор команд ICWS-88

DAT A B:удалить выполняющийся поток из очереди потоков
MOV A B:скопировать A в B
ADD A B:прибавить A к B
SUB A B:вычесть A из B
JMP A B:перейти к инструкции A
JMZ A B:перейти к A, если B равно 0
JMN A B:перейти к A, если B не равно 0
CMP A B:если A равно B, пропустить следующую инструкцию
SLT A B:если A меньше B, пропустить следующую инструкцию
DJN A B:уменьшить B на 1; если B не равно 0, перейти к A
SPL A B:добавить A в очередь потоков

Режимы адресации

В настоящий момент определено четыре режима адресации – непосредственный, прямой, косвенный, и предекрементный.

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

Решётка (#) используется для обозначения непосредственных операндов. Значение такого операнда – не адрес, а сами данные, которые будут использоваться инструкцией; эти данные доступны “непосредственно”, т.е. без дополнительной выборки из памяти.

Знак коммерческого at (@) используется для обозначения косвенных операндов. Значение операнда используется в качестве смещения, как и в случае прямой адресации. Операнд B ячейки памяти, расположенной по получившемуся адресу, используется затем как смещение от той ячейки памяти, из которой он был выбран. Получившийся теперь адрес используется либо как источник и/или приёмник для данных, используемых инструкцией, либо как адрес следующей инструкции для команд перехода.

Знак меньше (<) используется для обозначения предекрементных операндов. Значение операнда используется в качестве смещения, как и в случае прямой адресации. Операнд B ячейки памяти, расположенной по получившемуся адресу, выбирается, уменьшается на 1 (декрементируется), и затем сохраняется по тому же адресу. Затем он используется как смещение от той ячейки памяти, из которой был выбран. Получившийся теперь адрес используется либо как источник и/или приёмник для данных, используемых инструкцией, либо как адрес следующей инструкции для команд перехода.

Набор команд Redcode

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

DAT A B: У этой инструкции на самом деле два назначения, одно вспомогательное, и другое достаточно разрушительное. С одной стороны, она может использоваться как хранилище данных, например счётчика, указателя, и т.п. Однако, если её выполнить, то поток будет уничтожен! Поэтому она предоставляет механизм для достижения победы в Core War: нужно заставить каждый поток программы оппонента выполнить инструкцию DAT.

MOV A B: Если операнд A – непосредственный, то он помещается в поле B той ячейки памяти, на которую указывает операнд B. В противном случае, ячейка, на которую указывает операнд A, целиком копируется в ту ячейку памяти, на которую указывает операнд B.

ADD A B: Если операнд A – непосредственный, то он прибавляется к полю B той ячейки памяти, на которую указывает операнд B. В противном случае, оба поля A и B той ячейки, на которую указывает операнд A, прибавляются соответственно к полям A и B той ячейки памяти, на которую указывает операнд B.

SUB A B: Если операнд A – непосредственный, то он вычитается из поля B той ячейки памяти, на которую указывает операнд B. В противном случае, оба поля A и B той ячейки, на которую указывает операнд A, вычитаются соответственно из полей A и B той ячейки памяти, на которую указывает операнд B.

JMP A B: Адрес ячейки памяти, на которую указывает операнд A, помещается в конец очереди потоков выполняющейся программы. Операнд B игнорируется.

JMZ A B: Если поле B ячейки памяти, на которую указывает операнд B, равно 0, то адрес ячейки памяти, на которую указывает операнд A, помещается в конец очереди потоков выполняющейся программы.

JMN A B: Если поле B ячейки памяти, на которую указывает операнд B, не равно 0, то адрес ячейки памяти, на которую указывает операнд A, помещается в конец очереди потоков выполняющейся программы.

CMP A B: Если операнд A – непосредственный, то он сравнивается с полем B той ячейки памяти, на которую указывает операнд B. В противном случае, ячейка, на которую указывает операнд A, целиком сравнивается с той ячейкой памяти, на которую указывает операнд B. Если сравниваемые величины равны, то следующая инструкция пропускается (т.е. указатель на следующую инструкцию увеличивается на 2).

SLT A B: С полем B ячейки памяти, на которую указывает операнд B, сравнивается либо операнд A, если он непосредственный, либо поле B той ячейки, на которую указывает операнд A – в противном случае. Если значение A меньше, чем значение B, то следующая инструкция пропускается (т.е. указатель на следующую инструкцию увеличивается на 2).

DJN A B: Если операнд B – непосредственный, то он уменьшается на 1 (декрементируется) и сохраняется в ту же ячейку памяти, из которой была выбрана выполняемая инструкция; в противном случае, поле B той ячейки, на которую указывает операнд B, выбирается, уменьшается на единицу, и затем сохраняется по тому же адресу. Если значение после уменьшения на 1 не стало рано 0, то адрес ячейки памяти, на которую указывает операнд A, помещается в конец очереди потоков выполняющейся программы.

SPL A B: После того, как поток выбрал из памяти инструкцию SPL, указатель на следующую инструкцию увеличивается на 1 и помещается в конец очереди потоков. Затем адрес ячейки памяти, на которую указывает операнд A, помещается в конец той же самой очереди потоков, если ограничения на размер очереди потоков это позволяют. Операнд B игнорируется.

Вычисление фактического адреса

Этапы выборки и декодирования при выполнении инструкций Redcode несколько нетривиальны при использовании предекрементного режима адресации. После того, как выполняемая инструкция выбрана из памяти, её операнды необходимо “нормализовать”, прежде чем выполнять саму операцию. А именно, операнды обрабатываются так, чтобы избавиться от косвенной адресации. Поскольку это может требовать изменения содержимого памяти, то порядок действий должен быть оговорен явно.

Сначала рассматривается режим адресации операнда A. Если он непосредственный, то дальнейшей обработки не требуется. В противном случае, адрес выполняемой инструкции складывается со значением в поле A, давая абсолютный адрес. Если режим адресации прямой, то дальнейшей обработки не требуется. В противном случае, поле B слова памяти по полученному адресу считывается в поле A выполняемой инструкции. Если режим адресации предекрементный, то прочитанное значение уменьшается на единицу и записывается обратно в ту же самую ячейку памяти, откуда оно было считано. Наконец, к полю A инструкции прибавляется адрес ячейки памяти, из которой было прочитано значение.

Теперь поле A инструкции содержит либо непосредственные данные, либо абсолютный адрес операнда A. Такая же процедура затем используется для нормализации операнда B. Когда нормализованы оба операнда, рассматривается код операции, и требуемая операция выполняется.

Остался нерассмотренным последний аспект выполнения инструкций. Поскольку инструкция SPL требует использования очереди потоков, то обновление указателя на следующую инструкцию текущего потока необходимо отложить до тех пор, пока не будет обрабатываться код операции. Если выполняемая инструкция не требует выполнения перехода, и её код операции – не DAT, то указатель на следующую инструкцию увеличивается на 1 и помещается в конец очереди потоков до того, как операция будет выполняться.

Синтаксис исходного кода

Файл с исходным кодом состоит из строк в том виде, в котором их формирует типичный ASCII-редактор. Каждая строка может быть либо пустой строкой, либо строкой комментария, либо инструкцией Redcode, либо псевдоинструкцией.

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

Комментарии обозначаются точкой с запятой (;). Комментарии могут помещаться в любом месте исходного файла. Все символы, следующие за точкой с запятой до конца строки, игнорируются.

Инструкция Redcode состоит из пяти частей (полей): необязательной метки, мнемоники команды, операндов A и B, и необязательного комментария. Поля инструкции разделяются одним или более пробелом и/или символом табуляции.

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

Операнд состоит из необязательного символа режима адресации и следующего за ним выражения, составленного из меток, чисел, и знаков арифметических действий. Допустимые действия – сложение (+), вычитание (–), умножение (*) и деление (/).

Псевдоинструкция – это директива ассемблеру; для неё не генерируется объектный код. Ниже перечислены мнемоники и определения псевдоинструкций.

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

END: Псевдоинструкция END ставится после последней строки исходного текста, передаваемого ассемблеру. Строки, следующие за END, игнорируются. Кроме того, если за END следует операнд, то его значение используется как адрес начальной точки выполнения программы. Если операнда нет, то подразумевается, что начальная точка выполнения совпадает с первой инструкцией в исходном файле.

Приложение А

ICWS-88 допускает все нижеперечисленные инструкции Redcode, и только их:

MOV  # A    B
MOV  # A  @ B
MOV  # A  < B
MOV    A    B
MOV    A  @ B
MOV    A  < B
MOV  @ A    B
MOV  @ A  @ B
MOV  @ A  < B
MOV  < A    B
MOV  < A  @ B
MOV  < A  < B

ADD  # A    B
ADD  # A  @ B
ADD  # A  < B
ADD    A    B
ADD    A  @ B
ADD    A  < B
ADD  @ A    B
ADD  @ A  @ B
ADD  @ A  < B
ADD  < A    B
ADD  < A  @ B
ADD  < A  < B

SUB  # A    B
SUB  # A  @ B
SUB  # A  < B
SUB    A    B
SUB    A  @ B
SUB    A  < B
SUB  @ A    B
SUB  @ A  @ B
SUB  @ A  < B
SUB  < A    B
SUB  < A  @ B
SUB  < A  < B

CMP  # A    B
CMP  # A  @ B
CMP  # A  < B
CMP    A    B
CMP    A  @ B
CMP    A  < B
CMP  @ A    B
CMP  @ A  @ B
CMP  @ A  < B
CMP  < A    B
CMP  < A  @ B
CMP  < A  < B

SLT  # A    B
SLT  # A  @ B
SLT  # A  < B
SLT    A    B
SLT    A  @ B
SLT    A  < B
SLT  @ A    B
SLT  @ A  @ B
SLT  @ A  < B
SLT  < A    B
SLT  < A  @ B
SLT  < A  < B

JMP    A  # B
JMP    A    B
JMP    A  @ B
JMP    A  < B
JMP  @ A  # B
JMP  @ A    B
JMP  @ A  @ B
JMP  @ A  < B
JMP  < A  # B
JMP  < A    B
JMP  < A  @ B
JMP  < A  < B

JMZ    A  # B
JMZ    A    B
JMZ    A  @ B
JMZ    A  < B
JMZ  @ A  # B
JMZ  @ A    B
JMZ  @ A  @ B
JMZ  @ A  < B
JMZ  < A  # B
JMZ  < A    B
JMZ  < A  @ B
JMZ  < A  < B

JMN    A  # B
JMN    A    B
JMN    A  @ B
JMN    A  < B
JMN  @ A  # B
JMN  @ A    B
JMN  @ A  @ B
JMN  @ A  < B
JMN  < A  # B
JMN  < A    B
JMN  < A  @ B
JMN  < A  < B

DJN    A  # B
DJN    A    B
DJN    A  @ B
DJN    A  < B
DJN  @ A  # B
DJN  @ A    B
DJN  @ A  @ B
DJN  @ A  < B
DJN  < A  # B
DJN  < A    B
DJN  < A  @ B
DJN  < A  < B

SPL    A  # B
SPL    A    B
SPL    A  @ B
SPL    A  < B
SPL  @ A  # B
SPL  @ A    B
SPL  @ A  @ B
SPL  @ A  < B
SPL  < A  # B
SPL  < A    B
SPL  < A  @ B
SPL  < A  < B

DAT  # A  # B
DAT  # A  < B
DAT  < A  # B
DAT  < A  < B