Redcode

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:58, 8 июня 2016.

Redcode [1]- ([ redkəʊd ])это язык программирования, используемый в Core War. Выполняется на виртуальной машине, известной как Memory Array Redcode Simulator, или MARS. Структура Redcode создана на основе реальных языков ассемблера CISC в начале 1980-х, но содержит несколько функций, как правило, не встречаются в реальных компьютерных системах. И Redcode, и окружающая среда MARS предназначены для обеспечения простой и абстрактной платформы, а не сложных реальных компьютеров и процессоров. Хотя задумывалось, что Redcode будет напоминать обычный язык ассемблера CISC, реальная сборка во многом отличается.

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

Число инструкций в Redcode увеличивается с каждым новым стандартом, от первоначального количества примерно от 5 до текущего 18 или 19. И это не включая новые модификаторы и способы адресации, с помощью которых можно составить буквально сотни комбинаций. К счастью, нам не нужно учить все комбинации. Достаточно помнить инструкции и как модификаторы их изменяют.

Вот список всех команд, используемых в Redcode:

  • DAT - данные (убивает процесс)
  • MOV - перемещение (копирует данные с одного адреса на другой)
  • ADD - добавить (складывает два числа)
  • SUB - вычесть (вычитает одно число из другого)
  • MUL - умножение (умножает одно число на другое)
  • DIV - деление (одно число делит на другое)
  • MOD - модуль (делит одно число на другое с остатком)
  • JMP - прыжок (продолжает выполнение с другого адреса)
  • JMZ - переход, если нуль (проверяет количество и переходит к адресу, если это 0)
  • JMN - переход, если не равно нулю (проверяет номер и скачки, если это не 0)
  • DJN - декремент и переход, если не равно нулю (уменьшает число на один, и прыгает, если результат не равен 0)
  • SPL - сплит (начинается второй процесс по другому адресу)
  • CMP - сравнить (так же, как SEQ)
  • SEQ - пропустить если равно (сравнивает две команды, и пропускает следующую команду, если они равны)
  • SNE - пропустить, если не равно (сравнивает две команды, и пропускает следующую команду, если они не равны)
  • SLT - пропустить, если ниже, чем (сравнивает два значения, и пропускает следующую команду, если первая меньше, чем вторая)
  • LDP - нагрузка от р-пространстве (загружает число из приватного пространства хранения)
  • STP - сохранить р-пространстве (сохраняет число в приватное пространство хранения)
  • NOP - нет операции (ничего не делает)

Redcode совсем немного отличается от обычных языков ассемблера из-за его абстрактного характера.

Программы, реализующие стандартные тактики

Бес

Самые важные части Redcode - самые простые. Большинство основных типов "воинов" были изобретены прежде, чем новые инструкции и режимы появились. Простейшей и, вероятно, первой основной программой Core War это программа "бес", опубликованная АК Dewdney в оригинальной статье 1984 Scientific American , которая впервые представила Core War общественности

        MOV 0, 1

Да, это она. Только один MOV. Но что же она делает? MOV копирует инструкци.. Вы должны помнить, что все адреса в Core War взаимосвязаны с текущей инструкцией, так что бес в действительности копирует себя в инструкцию после себя.

        MOV 0, 1         ; this was just executed
        MOV 0, 1         ; this instruction will be executed next

Теперь, Бес будет выполнять команду, которую только что написал! Так как это в точности то же самое, как и первая инструкция, он будет снова скопировать себя на одну инструкцию вперед, выполнять копию, и продолжать двигаться вперед, заполняя ядро MOV'ами. Поскольку ядро не имеет фактического конца, бес, после заполнения всего ядра, достигает стартовую позицию своей инструкции и продолжает весело работать в кругах бесконечности.

Таким образом, Бес фактически создает свой собственный код, во время того, как выполняет его! В Core War, самомодификация является скорее правилом, чем исключением. Вы должны быть эффективными, чтобы быть успешным, и что почти всегда означает изменение кода на лету. К счастью, абстрактная среда позволяет сделать это намного легче, чем обычный ассемблер.

Очевидно, что в Core War нет кэша. Ну, на самом деле, нынешняя команда в кэше, так что вы не можете изменить его в середине выполнения, но, может быть, мы оставим это на потом ...

Гном

Бес имеет один маленький недостаток в качестве воина. Он не будет выигрывать слишком много игр, так как, когда он переписывает другой воина, он тоже начинает выполнять MOV 0, 1 и сам становится бесом. Чтобы убить программу, вы должны скопировать DAT над его кодом. Это - еще один классический воин по Dewdney, гном. Он"бомбит" ядро на регулярно расположенных местах с помощью DAT, предварительно убедясь, что он не ударит себя.

        ADD #4, 3        ; execution begins here
        MOV 2, @2
        JMP -2
        DAT #0, #0

На самом деле, это не точно то же самое, что написал Dewdney, но это работает точно так же. Выполнение начинается снова с первой команды. На этот раз это ADD. Инструкция ADD связывает источник и пункт назначения вместе, и помещает результат в пункт назначения. Если вы знакомы с другими языками ассемблера, вы можете заметить, что знак # - это способ маркировки непосредственной адресации. То есть, ADD добавляет число 4 к инструкции по адресу 3, а не добавляет инструкцию 4 к инструкции 3. С 3 инструкции после ADD следует DAT, и результат будет:

        ADD #4, 3
        MOV 2, @2        ; next instruction
        JMP -2
        DAT #0, #4

При добавлении двух команд вместе, и А- и В-поля будут добавлены вместе независимо друг от друга. Если добавить одно число на инструкцию, оно по умолчанию будет добавлен и к B-полю. Вполне возможно использовать # в ADD B-поля тоже. Затем А-поле будет добавлено к B-полю самого ADD. Режим непосредственной адресации может показаться простым и знакомым, но и новые модификаторы в стандарте ICWS '94 дают совершенно новый поворот. Но давайте посмотрим на Гнома на первый взгляд.

Инструкция MOV снова дарит нам еще один режим адресации: @ или режим косвенной адресации. Это означает, что DAT не будет копироваться на себя, как это кажется , но будет ссылаться на инструкцию его B-поля, :

       ADD #4, 3
       MOV 2, @2  ;  --.
       JMP -2     ;    | +2
       DAT #0, #4 ; <--' --. The B-field of the MOV points here.
       ...                 |
       ...                 | +4
       ...                 |
       DAT #0, #4 ; <------' The B-field of the DAT points here.

Как вы можете видеть, DAT будет скопировано на 4 Инструкции вперед. Следующая команда, JMP, просто делает прыжок процесса на две инструкции в обратном направлении, назад к ADD. Поскольку JMP игнорирует B-поле, оставим его пустым. MARS будет инициализировать его, как 0.

Кстати, как вы видите MARS не начал трассировку дальнейшие цепочки косвенных адресов. Если косвенные операнды указывают на инструкции с B-полем, на, скажем, четвертую, фактическое место 4 инструкции будет после нее, независимо от режима адресации. Теперь ADD и MOV будут выполняться снова. Когда выполнение достигает JMP снова, ядро выглядит следующим образом:

        ADD #4, 3
        MOV 2, @2
        JMP -2           ; next instruction
        DAT #0, #8
        ...
        ...
        ...
        DAT #0, #4
        ...
        ...
        ...
        DAT #0, #8

Гном будет "бомбить" DAT'ами каждые 4 инструкции, пока он не пройдет вокруг всего ядра и снова не достигнет себя:

        ...
        DAT #0, #-8
        ...
        ...
        ...
        DAT #0, #-4
        ADD #4, 3        ; next instruction
        MOV 2, @2
        JMP -2
        DAT #0, #-4
        ...
        ...
        ...
        DAT #0, #4
        ...

Теперь, ADD превратит DAT обратно в # 0, # 0, MOV будет выполнять бредовые указания, скопировав DAT прямо туда, где он уже есть, и весь процесс начнется снова с самого начала.

Это, естественно, не будет работать, если размер ядра не делится на 4, так как в противном случае Гном ударит инструкцию от 1 до 3 инструкции позади DAT, таким образом, убивая себя. К счастью, наиболее популярный размер ядра в настоящее время 8000, а затем 8192, 55400, 800, и все из них делится на 4, так что наш гном в безопасности

Как примечание, включать DAT # 0, # 0 в воина не было действительно необходимо; Инструкции ядра изначально заполнены, тем,что я указал тремя точками (...).. на самом деле DAT 0, 0 . Я буду продолжать использовать точки, чтобы описать пустое ядро, так как это короче и проще для чтения

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

В первых версиях Core War единственными режимами адресации было немедленное (#), прямое ($ или без обозначения) и косвенные В-поля(@) . Позже, predecrement режим адресации, или <, был добавлен. Это то же самое, что и косвенный режим, за исключением того, что указатель будет уменьшается на единицу до того, как целевой адрес вычисляется.

        DAT #0, #5
        MOV 0, <-1       ; next instruction

После выполнения MOV, результат будет таковым:

        DAT #0, #4 ;  ---.
        MOV 0, <-1 ;     |
        ...        ;     | +4
        ...        ;     |
        MOV 0, <-1 ; <---'

Стандарт ICWS '94 добавил еще четыре режима адресации, в основном это косвенные А-поля, и в общей сложности получается 8 режимов:

# -- немедленное

$ -- прямое ($ может быть опущен)

° -- A-поле косвенное

@ -- B-поле косвенное

{ -- A-поле косвенное с преддекрементом

< -- B-поле косвенное с преддекрементом

} -- A-поле косвенное с постинкрементом

> -- B-поле косвенное с постинкрементом

        DAT #5, #-10
        MOV -1, }-1      ; next instruction

После выполнения инструкции:

        DAT #6, #-10 ;  --.
        MOV -1, }-1  ;    |
        ...          ;    |
        ...          ;    | +5
        ...          ;    |
        DAT #5, #-10 ; <--'

Одну важную вещь следует помнить о режимах предекремента и постдинкремента является то, что указатели будут увеличиваться/ уменьшается, даже если они не используются ни для чего. Так JMP-1, <100 будет уменьшать инструкцию 100, даже если значение, на которое он указывает, не используется ни для чего. Даже DAT <50 <60 будет уменьшать адреса в дополнение к убийству процесса.

Очередь процессов

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

Довольно рано в истории Core War, было предложено, что добавление многозадачности в игре будет гораздо интереснее. Поскольку грубые методы time-slicing'а, используемые в обычных системах не будут вписываться в абстрактной среде Core War (главное, вам нужно ОС для управления им), система была изобретена так, в результате чего каждый процесс выполняется в течение одного цикла, в свою очередь.

Инструкция, которая используется для создания новых процессов это SPL. Он принимает адрес в качестве параметра в его A-поле, как JMP. Разница между JMP и SPL в том, что, в дополнение к запуску выполнения по новому адресу, SPL продолжает выполнение следующей команды.

Два - или более - процесса, созданных таким образом, делятся временем обработки одинаково. Вместо одного счетчика процесса, показывающего текущую инструкцию, MARS имеет очередь процессов, список процессов, выполняемых раз в том порядке, в котором они были запущены. Новые процессы, созданные SPL, добавляются сразу после текущего процесса, в то время как те, которые выполнили DAT, будут удалены из очереди. Если все процессы умирают, воин проиграл.

Важно помнить, что каждая программа имеет свою собственную очередь процесса. С более чем одной программой в ядре, они будут выполнены поочередно, один цикл в одно время, независимо от продолжительности их очереди процесса, так что время обработки будет всегда одинаковое. Если программа имеет 3 процесса, а программа B только 1, порядок исполнения будет выглядеть так:

program A, process 1,

program B, process 1,

program A, process 2,

program B, process 1,

program A, process 3,

program B, process 1,

program A, process 1,

program B, process 1,

...

И, наконец, небольшой пример использования SPL.:

        SPL 0            ; execution starts here
        MOV 0, 1

Так как SPL указывает сама на себя, после одного цикла процесс будет таким:

       SPL 0            ; second process is here
       MOV 0, 1         ; first process is here

После того, как обе инструкции выполнятся, ядро будет таким:

       SPL 0            ; third process is here
       MOV 0, 1         ; second process is here
       MOV 0, 1         ; first process is here

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

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

Модификаторы инструкций

Наиболее важная вещь ,которую стандарт ICWS '94 принес не новые инструкции или новые режимы адресации, а модификаторы. В старом '88 стандарте режимы адресации сами решали, какие части инструкции зависят от операции. Например, MOV 1, 2 всегда перемещает целую инструкцию, в то время как MOV # 1, 2 - одно число. (и всегда в B-поле!)

Естественно, это может вызвать некоторые трудности. Что делать, если вы хотите, чтобы переместились только А- и В-поля инструкции, а не код операции? (вы должны использовать ADD) или хотите переместить что-то из B-поля на А-поле? Для того, чтобы прояснить ситуацию, были изобретены модификаторы команд.

Модификаторы это суффиксы, которые добавляются к инструкции, чтобы указать,на какие части кода и назначения это повлияет. Например, MOV.AB 4, 5 будет двигать A-поле инструкции 4 в B-поле инструкции 5. Есть 7 различных доступных модификаторов :

  • MOV.A - перемещает A-поле источника в A-поле назначения
  • MOV.B - перемещает B-поле источника в B-поле назначения
  • MOV.AB - перемещает A-поле источника в B-поле назначения
  • MOV.BA - перемещает B-поле источника в A-поле назначения
  • MOV.F - перемещает оба поля источника в тех же поля назначения
  • MOV.X - перемещает оба поля источника в противоположные поля назначения
  • MOV.I - перемещает всю исходную инструкцию в назначение

Естественно те же модификаторы могут быть использованы для всех команд, не только для MOV. Некоторые инструкции, как JMP и SPL, однако, не заботятся о модификаторах. (И да,почему они должны? Они не обрабатывать фактические данные, они просто "прыгают".) Так как не все модификаторы подходят для некоторых инструкций, они буду заменены на ближайшие по смыслу. Наиболее распространенный случай включает в себя .I модификатор: Чтобы сохранить язык простым и абстрактным, числовые эквиваленты не были определены для кодов операций, так что использование математических операций на них не будет иметь никакого смысла вообще. Это означает, что для всех команд, кроме MOV, SEQ и SNE (и CMP, который просто псевдоним для SEQ) модификатор .I будет означать то же самое, .F. Еще, что нужно помнить о .I и .F является то, что режимы адресации тоже часть OpCode (кодов инструкции), и не копируются MOV.F Теперь мы можем переписать старые программы, чтобы использовать модификаторы. Например, Бес, естественно, будет MOV.I 0, 1. Гном станет:

       ADD.AB #4, 3
       MOV.I  2, @2
       JMP    -2
       DAT    #0, #0

Обратите внимание, что мы ушли из модификаторов для JMP и DAT, поскольку они не используют их. MARS превращает их в (например) JMP.B и DAT.F

Как узнать, какой модификатор, добавить к какой инструкции? (и, что более важно, каким образом MARS добавит их, если мы оставим их?) Ну, вы можете сделать это, как правило, с позиции здравого смысла, но стандарт '94 определяет набор правил для этой цели.

DAT, NOP всегда .F, но оно игнорируется

MOV, SEQ, SNE, CMP Если А-режим является непосредственным,.AB, если в В-режиме является немедленным и А-режим - нет - .B, если ни один режим не является немедленным , .I.

ADD, SUB, MUL, DIV, MOD MOD Если А-режим является немедленным , .AB, если В-режим является немедленным и А-режим нет, .B, если ни один режим не является немедленным , .F.

SLT, LDP, STP если А-режим является немедленным, .AB, если это не так, (всегда!) .B

JMP, JMZ, JMN, DJN, SPL всегда .B (но это игнорируется JMP и SPL).

Ссылки