Теперь мы готовы познакомиться со всеми инструкциями Redcode. Помните: везде, где будет идти речь об аргументах (операндах) инструкций A и B, имеется в виду любой из допустимых способов адресации - относительный, косвенный или немедленный.
В своем первоначальном виде (так, как это было опубликовано в Scientific American) Redcode состоит из 10 инструкций:
Первая программа для Core Wars была написана самим Дьюдни, называлась Imp, и состояла всего из одной строчки:
MOV 0,1
Тем не менее, эта программа вполне жизнеспособна и даже может нанести некоторый вред противнику. Что же она делает ?
Как вы уже знаете, инструкция MOV копирует содержимое одного ячейки памяти в другую. По относительному адресу 0 (ведь абсолютных адресов в Redcode нет) находится сама инструкция MOV, то есть вся программа Imp.
Итак, MOV копирует саму себя в ячейку с относительным адресом 1, то есть в следующую за MOV ячейку памяти. После такого копирования память выглядит следующим образом:
MOV 0,1
MOV 0,1
Следующим ходом MARS начинает выполнять инструкцию, находящуюся в следующей, после оригинальной MOV ячейке, то есть – MOV номер 2. Но это та же самая программа Imp!
Вы уже догадываетесь, что наша маленькая программа постепенно просто заполнит всю память самой собой, если, конечно, не будет остановлена в пути более хитроумным противником.
Следующая программа, которую мы разберем подробно, называется «Близнецы». Ее единственная задача состоит в том, чтобы скопировать саму себя в другое место в памяти MARSа и продолжать выполнение оттуда.
Прежде, чем изучать саму программу, давайте постараемся понять, что же от нее требуется. Казалось бы, крошечная программка Imp уже выполняет задачу копирования самой себя в другое место памяти, то есть одной инструкции MOV может оказаться вполне достаточно ? Почти, но не совсем. Дело в том, что мы хотим скопировать программу не просто в следующую по порядку ячейку памяти, а в любое другое, произвольно заданное место в памяти.
Пусть так, но что нам мешает вместо MOV 0,1 написать MOV 0,100 ? Представьте себе работу этой программы. На первом «ходу» инструкция MOV 0,100 действительно будет скопирована в ячейку, отстоящую на 99 ячеек от текущей. Следующим действием станет «исполнение» того, что написано в следующей за оригинальной инструкцией MOV ячейке – и вот тут-то программа и «упадет», потому что в следующей ячейке не написано ничего!
Значит, в нашу программу нужно включить еще и инструкцию перехода (JMP) на новое место в памяти, где будет находиться скопированная инструкция MOV.
Постойте, но ведь сама MOV не предназначена для того, чтобы копировать еще и JMP, хотя несомненно, что JMP является частью программы. Значит, в программу нужно включить еще одну инструкцию MOV, которая будет копировать JMP. Но кто же тогда будет копировать саму эту новую инструкцию MOV ?!
Мы пришли к выводу, что написать программу, копирующую себя в произвольное место в памяти не так-то просто, и, начавшись так легко, процесс этот стал все больше напоминать снежный ком.
На самом деле, все не так безнадёжно. Прежде всего, программа, конечно же, должна включать инструкцию копирования (MOV), которая будет ответственна за передвижение текста программы в памяти. Кроме того, необходимо задать расстояние, на которое будет перемещаться программа. Это расстояние будет задано псевдоинструкцией DAT. Когда копирование завершиться, нам нужно будет «прыгнуть» на адрес первой инструкции программы, но уже в новом месте. Теперь у нас есть по крайней мере три инструкции, которые нужно копировать (MOV, DAT и JMP), поэтому мы приходим к неизбежному циклу, то есть проверке на окончание процесса копирования и переходу на нужный адрес, а также необходимости увеличивать счетчик, который будет указывать инструкции MOV, какую ячейку нужно копировать в этот раз. Для такого счетчика лучше всего подойдет косвенная адресация, и именно она избавит нас от эффекта снежного кома, позволяя одной и той же инструкции MOV копировать разные части программы.
Перед вами текст программы «Близнецы»:
1: DAT 0
2: DAT 99
3: MOV @-2 @-1
4: CMP –3 #9
5: JMP 4
6: ADD #1 –5
7: ADD #1 –5
8: JMP –5
9: MOV #99 93
10: JMP 93
Первые две строки просто содержат числа – 0 и 99, первое из которых будет служить счетчиком цикла копирования (который по-другому можно назвать «откуда копировать»), а второе – счетчиком расстояния (который можно назвать «куда копировать»). Строка 3 – это и есть «рабочая лошадка» всей программы. Она выполняет копирование. По определению косвенной адресации, содержимое ячейки –2 (то есть отстоящей от строки номер 3 на две ячейки назад) является адресом ячейки, которую и предстоит копировать. На самом первом «ходу» программы в этой ячейке записан 0 (DAT 0). Таким образом, копировать нужно содержимое ячейки с относительным адресом 0 (то есть ячейки, которая содержит саму инструкцию MOV). Адрес назначения операции копирования обозначен как @-1, что означает, что адрес этот находится в ячейке, предшествующей той, в которой находится MOV. В ней сейчас записано число 99 (DAT 99). Таким образом, первым действием программы «Близнецы» станет копирование инструкции MOV @-2 @-1 в ячейку памяти, находящуюся на 98 шагов вперед от самой MOV.
В строке 4 происходит проверка на завершение цикла копирования. Число (константа) 9 сравнивается с содержимым ячейки памяти в строке 1 (то есть с числом, записанным в псевдоинструкции DAT). Сейчас оно равно 0, поэтому следующая инструкция (JMP 4) пропускается и мы переходим к выполнению двух сложений в строках 6 и 7. Как легко видеть, эти инструкции увеличивают оба счетчика на единицу, то есть в строках 1 и 2 теперь записано:
1: DAT 1
2: DAT 100
Инструкция JMP в строке 8 выполняет прыжок (то есть передачу управления) на 5 ячеек назад, то есть на строку 3, содержащую уже знакомую нам инструкцию MOV.
Несложно догадаться, что на этот раз, MOV скопирует уже не саму себя, а следующую инструкцию (из строки 4), так как оба счетчика увеличились на 1.
Так будет продолжаться до тех пор, пока не будет скопирована последняя инструкция из строки 10, и счетчик цикла не станет равным 9. В этом случае в первый раз выполнится инструкция JMP из строки 5 и управление перейдет на строку 9, в которой находится инструкция MOV #99 93.Ее назначение заключается в том, чтобы вставить новый счетчик расстояния (DAT 99) вместо «испорченного» (так как его значение увеличивалось с каждым циклом).
Наконец, заключительная инструкция JMP в строке 10 передаст управление на новую инструкцию MOV @-2 @-1, которая начнет весь процесс сначала.
У этой программы есть один недостаток. Предполагается, что изначально вся память MARSа занята нулями, то есть псевдоинструкциям DAT 0, поэтому копирование самой этой псевдоинструкции не происходит. Проблема может заключаться в том, что память в новом месте, куда будет скопирована программа, может оказаться «испорченной» (не содержать 0) и тогда программа перестанет работать. Впрочем, этот недостаток очень легко исправить, что и предлагается сделать читателю самостоятельно.
На рисунке представлены шесть первых шагов программы "Близнецы" и состояние памяти после выполнения каждой инструкции. Обратите внимание на то, как "скользят" относительные адреса ячеек. Текущая ячейка памяти всегда имеет адрес ноль, и от него отсчитываются все остальные адреса. К концу шестого шага уже две инструкции скопированы в новое место памяти.
- Хорошо, - скажет читатель, - программы умеют копировать сами себя в памяти, видоизменять сами себя, бросаться цифровыми бомбами и совершать другие чудеса - но где же здесь игра ? Ведь в битве должны принимать участие по меньшей мере две программы! И здесь на сцену выходит одна из фундаментальных компьютерных идей - переключение процессов (process switching).
С этим понятием мы познакомимся в следующей части этой главы.