В игре CoreWars участники писали программы, которые сами клонировались в памяти и пытались затереть друг друга. Работало это в виртуальной машине с хитроумными инструкциями, которые позволяли создавать очень короткий код. Простейшая само-копирующаяся программа, "самобеглый MOV", выглядела вот так:

MOV 0, 1

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

Мне неизвестны реальные процессоры в которых были бы подобные "удобные" инструкции. И вот любопытно - насколько короткой можно сделать (а можно ли?) подобную "самобеглую" программу для какой-нибудь настоящей архитектуры. Ну хотя бы для 8086. Тем более что там сегменты обозримого размера - 64 килобайта.

Не страшно если вы не знаете или плохо помните команды ассемблера, их будет немного и мы снабдим их пояснениями.

Пояснение "самобеглого MOV"

В вышеупомянутой команде MOV 0, 1 сама мнемоника инструкции - это узнаваемая аббревиатура копирования данных, от слова "move". Параметров у неё два - откуда копировать (0) и куда копировать (1). Они в данной архитектуре (RedCode) обозначают адреса памяти, притом в относительной адресации, а не в абсолютной.

То есть 0 - это адрес относительно текущей выполняемой инструкции - как нетрудно догадаться, адрес ячейки где сама эта инструкция лежит. Ну а 1 - уже понятно, следующая ячейка памяти.

Текущая инструкция копирует себя в следующую ячейку - и как нетрудно догадаться, выполнение переходит к инструкции записанной в следующей ячейке. К только что скопированной.

Здесь мы видим несколько особенностей RedCode которые позволили сделать этот трюк:

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

• адресация для данных относительна указателя на текущую инструкцию (такое в реальных процессорах бывает обычно для прыжков но не для данных)

• инструкция копирующая между адресами памяти умещается в одной ячейке (очевидно ячейка не крохотная - ведь туда должны 2 адреса поместиться и код инструкции)

Первый набросок

Итак, мы засучиваем рукава, берём ассемблер или лучше отладчик для 8086, например DEBUG.EXE и попробуем создать COM-файл который копирует свой код всё дальше и дальше. Напомню предшествующую статью которая служит инструкцией-демонстрацией к использованию этого инструмента.

Почему этот эксперимент мы делаем под "старый добрый DOS"? Да ведь в современных OS память организована во "flat memory model" обычно и с одной стороны сегменты у нас как минимум по 4 Гб, с другой программа точно не имеет доступа ко всем страницам в этом адресном пространстве.

Итак, план действий:

• получить текущий выполняемый адрес

• сделать цикл для копирования с текущего адреса на адрес больший на размер программы

• и всё? ну, пока всё...

Текущий адрес живёт в регистре IP (и меняется с каждой инструкцией). Нам бы скопировать его в регистр, который будет использоваться в качестве индекса-источника при копировании, вроде такого:

MOV SI,IP ; копируем IP в SI

заметим что в привычной для intel нотации "целевой" регистр пишется первым

К сожалению так не сделать - у процессора нет инструкций копирующих SI в другие регистры. Нужно воспользоваться тем, что при вызове подпрограммы адрес возврата копируется в стек - и из стека его вытолкнуть, например:

                   CALL next_instruction
next_instruction:  POP SI
                   SUB SI, 3

Сама инструкция вызова использует относительную адресацию, то есть даже после копирования в другое место кода она будет вызывать следующую инструкцию.

А в следующей инструкции мы вместо возврата из процедуры просто вытолкнем сохранённый адрес в SI - этот регистр как раз как индекс источника при копировании используется (source index).

Почему нужно вычесть 3 из него? Потому что CALL сохраняет в стек не свой собственный адрес, а адрес следующей инструкции (куда нужно вернуться) - сама инструкция занимает как раз 3 байта.

Дальше всё несложно (вроде)

Запишем в CX размер программы (сколько байт копировать) - этот регистр часто используется как счетчик цикла. А в DI поместим адрес куда копировать (destination index - он неспроста так называется) - это будет сумма SI и CX.

Сам цикл копирования можно немного по-разному написать - мы поступим так - будем использовать регистр BP как "добавку" к обоим индексам и увеличивать его на каждой итерации. Целиком это выглядит так:

Здесь XOR BP,BP - это "укороченный" способ записать 0 в BP, дальше следуют две инструкции - одна копирует из адреса [BP+SI] в AH один байт - а вторая из AH этот же байт переносит в [BP+DI - только копирование между двумя байтами памяти заняло 4 байта!

Следом идёт увеличение BP командой INC (инкремент) и волшебная команда цикла "с постусловием" - LOOP уменьшает число в CX и если оно не достигло 0 то переходит по указанному адресу.

А по этому адресу (110) как видим как раз та парочка инструкций копирования.

Последняя команда MOV SP, SI - перемещает указатель стека (на пространство перед началом текущей копии программы - адрес-то начала до сих пор в SI). Почему приходится это делать? Да ведь мы используем инструкцию CALL и значит стек должен быть "в рабочем состоянии" - а он по умолчанию живёт где-то по адресу FFFE - и когда мы туда добежим в своём копировании - мы его затрём!

Полный размер программы мы видим на этом этапе - 0x19 байт - его мы и занесем как параметр инструкции в 5й строчке (MOV CX, размер).

Вроде бы всё, но... Как это проверить?

Проверка показала...

Недолго думая, я добавил к программе несколько инструкций (не привожу их т.к. потом сделаем иначе), которые с помощью прерывания ОС (см. предыдущую статью) печатают старшие 5 бит из регистра SI (в котором мы каждый раз имеем текущий адрес) в виде одного символа (для читаемости к нему добавляется 0x40 - получаются в основном заглавные латинские буквы. Запустим и видим:

Сначала всё шло хорошо, адрес явно увеличивался (от символа "@" с кодом 0x40 до символа "_" с кодом 0x5F) - но дальше что-то пошло не так...

Немного поэкспериментировав приходим к выводу - здесь смешались 3 проблемы:

• программа из COM-файла не зря грузится с адреса 0x100 в текущем сегменте - предыдущие 256 байт используются ДОС-ом и если мы их затираем, то пользоваться системными функциями ДОС не следует

• наше упрощённое "передвигание" стека всё-таки не переживает "заворачивания" программы через границу сегмента

• если инструкция попадает на границу сегмента, происходит не то что хотелось

Последний пункт интересно пояснить подробнее, т.к. он касается архитектуры.

В реальном режиме у нас память организована в сегменты по 64 кб (65536 байт) - и сами эти сегменты идут "внакладку", через каждые 16 байт начинается следующий.

Что происходит если мы скопировали свою программу и оказалось что какая-то инструкция попадает своим началом на адрес FFFF (последний байт в сегменте) а её "хвост" уже закручивается на начало сегмента (адреса 0000, 0001, 0002...)

Это легко проверить. Например инструкция записи константы в регистр MOV AX,1234 кодируется 3 байтами B83412 - видно что первый байт это код самой инструкции - а дальше два содержат нужную константу (помним про LSB-порядок).

Отредактируем память начиная с адреса FFFF записав эти три байта, после чего установим IP на этот адрес и выполним один шаг:

видно что счётчик инструкций изменился корректно (стал 0002) да только вот 1234 в регистр AX не попало. Процессор считал команду из последовательной тройки байт не обращая внимания на границу сегмента (то есть два байта пришли из следующей области памяти, формально нам не доступной в данном сегменте).

С этим можно бороться двумя путями - либо использовать инструкции такого размера, чтобы при данном размере программы они никогда не попадали на границу сегмента... Но это сложно, т.к. у 8086 инструкции все разношёрстные по длине.

Либо же выровнять размер программы так чтобы она умещалась в сегменте кратное количество раз. Например 32 или 64 байта. Ну мы так и поступим.

Рабочая версия

Чтобы обойти проблему с "повреждением" памяти используемой функциями ДОС мы просто не будем использовать их а станем визуализировать процесс прямо в видеопамяти.

А вот с проблемой "передвигания" стека возиться не хочется - уж очень костыльно выглядит всё что можно придумать. Поэтому обойдёмся без стека.

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

Мы записали 0x100 в SI, размер программы 0x40 (64 байта) поместили в CX, сложили одно с другим и результат устроили в DI как и раньше - и тут делаем маленький трюк!

DI - адрес будующей копии программы - записывается по адресу [SI+1] - то есть в параметр первой инструкции. Эту инструкцию мы уже выполнили к этому моменту, так что нам не повредит - зато когда она будет перенесена в новую копию, она окажется уже MOV SI, 0140 - и так далее будет увеличиваться с каждой копией...

Теперь насчет вывода в видеопамять. Она начинается с сегмента 0xB800 и каждый символ занимает 2 байта - в первом сам код символа - а во втором атрибуты (цвет, фон, мигание). Мы будем использовать регистр BX в качестве адреса внутри видеобуфера, увеличивая его каждый раз на 2 байта - а записывать туда будем попросту содержимое SI (адрес новой копии программы) - так что у нас будут меняться и символы и цвета.

Нужно только помнить что экран-то коротенький, 80*25 символов - то есть всего 4000 байт. Будем делить BX на эту величину и каждый раз брать остаток, чтобы наше "рисование" заворачивалось через границу экрана.

В общем этот довесок к коду выглядит теперь так:

Деление BX на 4000 (0xFAO) выполняется в первых пяти инструкциях. 8086 процессор требует поместить 32-битовое число в пару DX:AX, инструкция деления в качестве операнда указывает только один регистр - на который делим - а после этого частное попадает в AX и остаток в DX - он-то нам и нужен. Скопируем обратно в BX.

Дальше мы проставляем 0xB800 во вспомогательный сегментный регистр и запишем SI по дальнему адресу ES:[BX].

Теперь увеличиваем BX на 2 чтобы перейти к следующему символу для следующего раза.

По адресам 130...134 у нас добавлен пустой цикл на 4096 итераций - просто задержка, чтобы визуализация наблюдалась на человеко-различимой скорости :)

Из прочего здесь NOP-ы которыми размер программы доведён до 0x40 байт (они идут всю дорогу до адреса 13F). И также попала инструкция CLI (запрет прерываний). Поскольку мы пользуемся только видеопамятью - хуже от неё не будет, а запретить актуально - стек-то мы точно сломаем.

Как это выглядит в результате - можно посмотреть в коротеньком видео:

https://vkvideo.ru/playlist/-20226217_-2/video-20226217_456239146

Ну а скриншот уже порадовал нас в качестве обложки к данной статье:

Заключение

В общем, реальные архитектуры явно не лучшее место для "самобеглых" программ, а уж реализации игр вроде CoreWars и Darwin конечно лучше реализовывать на искусственных ВМ - к тому же нужен и рефери-монитор.

Сам по себе "самобеглый" код у нас уместится и в 0x20 байт (всё равно нужен размер который "кратно" заполняет сегмент) - ну а с визуализацией стало примерно вдвое больше - хотя в результате довольно щедро насыпано NOP-ов.