Malbolge - kenrube/Esopoly GitHub Wiki

Malbolge - уникальный язык программирования. Он стал широко известен благодаря сериалу "Элементарно" как язык, на котором могут писать только самые умелые, либо обдолбанные хакеры. Что самое интересное, это не так уж далеко от истины. С момента создания в 1998 году на нем написаны хорошо, если пара десятков программ, и те в большинстве своем созданы не вручную, а сгенерированы.

Причина? Прочитайте спецификацию, ознакомьтесь с интерпретатором и выберите любую по вкусу:

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

Пожалуйста, ознакомьтесь со ссылками выше, поскольку я не буду объяснять основы языка, а дальнейшее решение целиком опирается на этот фундамент. Замечу лишь, что там, где спецификация и ее реализация в интерпретаторе (от самого автора, Бена Ольмстеда) различаются, верным считается интерпретатор. Например, за вывод символа на печать отвечает инструкция <, а не /.

Посмотрите на исходник Hello world в Вики. Смотрится жутко, не правда ли? С виду совершенно хаотичное нагромождение символов, формируемое непонятно по каким правилам. На деле выглядит он так потому, что обфусцирован. Необфусцированная версия (называемая также нормализованным исходным кодом) состоит лишь из набора инструкций языка (j,i,*,p,<,/,v,o) да еще, быть может, пробельных символов, которые будут проигнорированы интерпертатором.

Итак, наша цель - вывести на печать строку Malbolge program.

Как следует из спецификации, за вывод символа на печать отвечает инструкция <, которая интерпретирует значение, лежащее в регистре A (аккумуляторе), как код ASCII-символа. ASCII - восьмибитная кодировка, то есть содержит 256 символов. Если в A окажется значение, большее 256, кодом символа будет остаток от деления значения в A на размер таблицы: [A] mod 256.

Наша задача - сформировать необходимое значение. В арсенале языка есть 2 инструкции, которые влияют на значение в A: * и p. Рассмотрим их чуть внимательнее.

Алгоритм работы инструкции *:

  1. Преобразовываем значение, лежащее в памяти по адресу D, в 10-разрядное троичное число. Предположим, что в исходном коде на позиции D (а поскольку при загрузке программы в память она маппится напрямую, то и по адресу D в памяти) располагается символ ~. Смотрим в таблицу ASCII, выясняем, что код символа равен 126. Преобразуем в троичное число: 11200. Дополняем нулями слева до 10 разрядов: 0000011200.
  2. Циклически сдвигаем цифры в числе на 1 вправо, т.е. первая становится второй, вторая третьей, ..., последняя - первой. 0000011200 => 0000001120.
  3. Записываем полученное значение в ячейку памяти по адресу D, заменяя им старое значение. Затем новое значение из D копируется в регистр A. Если бы мы захотели вывести содержимое A на экран, что бы получили? Преобразовываем 0000001120 в десятичное число: 0000001120 => 42 (значение меньше 256, так что по модулю ничего брать не надо). Символ #42 в ASCII - это *. Он и был бы выведен на печать.

Алогритм работы инструкции p точно такой же, за одним исключением: вместо результата циклического сдвига в D записывается результат применения к [D] и [A] предложенной автором троичной операции Crazy.

Казалось бы, все просто и алгоритм формирования любого требуемого значения у нас в кармане, но не тут-то было. Два из трех регистров, C и D, играют роль указателей: первый ссылается на текущую инструкцию, второй - на текущую позицию с данными. И при загрузке программы в память оба регистра инициализируются нулем. То есть при работе программы любая инструкция тут же выступает и данными для ее исполнения.

Рассмотрим небольшой пример. Пусть это будет простейшая программа:

*<v

или в ненормализованном виде

'bO

Проследим за выполнением первой инструкции:

  1. ASCII-код ' равен 39. Переводим в 10-разрядное троичное число: 0000001110.
  2. Циклический сдвиг вправо: 0000000111.
  3. Преобразовываем обратно в десятичное: 13. Это неграфический символ, так что инструкция < на экран ничего не выведет.

Но это неважно. Важен вывод: мы не можем "подсунуть" инструкции * те данные, которые нам хотелось бы. Они жестко зависят от самой инструкции и ее местоположения в исходном коде. Ну а раз на саму инструкцию мы влиять не можем, приходится менять ее местоположение. Да, таким образом действительно можно вывести требуемый текст, но программа разрастется до невменяемых размеров (и не стоит забывать про ограничение на размер исходного кода в 59049 символов). Вот самый короткий пример, который выведет на печать символ *:

ooooooo*<v

Или в ненормализованном виде

DCBA@?>~[H

А нельзя ли вообще обойти эту проблему стороной? Верно, можно. Не зря же в синтаксисе языка имеются инструкции j и i. Первая устанавливает в качестве указателя на данные [D], вторая использует это же значение в качестве указателя на код. То есть обе они исполняют роль jump-а, разграничивая области кода и данных.

Если наглядно, вот структура кода с использованием j:

...j[код]...[данные]
   \________^

То же самое, с i:

...i[данные]...[код]
   \___________^

Встает вопрос: какой из вариантов выбрать в нашем случае?

Давайте попробуем первый вариант. Просто запишем подряд несколько инструкций j и посмотрим, далеко ли мы сможем "прыгнуть" из любой из позиций:

jjjjjjjjjjjjjjj

в ненормализованном виде:

('&%$#"!~}|{zyx

ASCII-код ( равен 40, в эту позицию мы и сможем совершить прыжок, если первой же инструкцией будет j. ASCII-коды следующих символов все уменьшаются, пока не достигают ! с кодом 33 на восьмой позиции. Если инструкция j будет располагаться на следующей, девятой позиции, в качестве "пункта назначения" выступит позиция номер 126 (ASCII-код символа ~).

То есть либо у нас под код, который должен формировать на вывод фразу Malbolge program, будет выделено максимум 40 инструкций (их не хватит - поверьте, я пробовал :), либо что-то в районе 126 (а это уже чересчур много свободного места под код вывода).

Так что я остановился на втором варианте. Проделав те же самые прикидки, легко выяснить, что максимум мы сможем прыгнуть в 98 позицию (ASCII-код символа b - нормализованного представления команды i, стоящей на первой позиции). Чем дальше от начала будет располагаться инструкция i, тем ближе мы и прыгнем.

В итоге, наш код будет выглядеть примерно так:

...i[{набор из инструкций}...{набор из инструкций}]...[{набор из *,p,o}<...<{набор из *,p,o}<v]

o - nop-инструкция, по факту ничего не делающая. Однако в данном случае она может быть полезна: может оказаться, что длина набора из *,p и o, выводящего требуемый символ, будет короче длины набора, состоящего только из * и p.

Осталось последнее: подобрать соответствующие наборы инструкций. Описывать подробно алгоритм поиска я не буду (возможно, сделаю это позже) - он достаточно прост и сводится к последовательному перебору инструкций *,p и o в блоке кода и вообще всех инструкций в соответствующем блоке данных. Разумеется, решение я искал не вручную, а написал для этого генератор на Mathematica (сорян, ребят, я развлекался как мог). Код, правда, ужасен, но сделайте, пожалуйста, скидку на время написания - это было несколько лет назад :)

В итоге я получил следующий результат:

ooooooi/iojpo*pivojji/oovvoipooooo/oo*o<o/oo/iojo/oo/o/joijoo/ooooooooooooooooooooooooooooooo*p<*p<*ppp<*ppp<opp<*p<pp<pp<o*<*op<o*p<*op<*p<*p<pp<*p<v

Позже некоторые инструкции были заменены, поскольку они делали некорректным исходный код программы на другом языке. Плюс были добавлены 2 пустые инструкции практически в самом конце - точной причины я не помню, возможно, это была попытка добавить Befunge (не взлетело :). Итоговый вид:

ooooooi/iojpo*pivojji/ijvvoipooooo/ji*p<o/oo/iojo/oo/o/joijpo/oopop<p<*p*o*<*ppo**p<pp*<oppoo*p<*p<*ppp<*ppp<opp<*p<pp<pp<o*<*op<**p<*op<*p<*p<pp<*poo<v

Или в более наглядном представлении, где видно, какая часть исходника за что отвечает:

ooooooi         jump
,_____/
|   /io         data for 'M'
|   jpo         data for 'a'
|   *pivo       data for 'l'
|   jji/i       data for 'b'
|   jvvo        data for 'o'
|   ipo         data for 'l'
|   ooo         data for 'g'
|   o/j         data for 'e'
|   i*p         data for ' '
|   <o/o        data for 'p'
|   o/io        data for 'r'
|   jo/o        data for 'o'
|   o/o         data for 'g'
|   /jo         data for 'r'
|   ijp         data for 'a'
|   o/oop       data for 'm'
|   op<p<*p     do nothing (some instructions between data & code)
|   *o*<*pp     --//--
|   o**p<pp     --//--
v   *<oppoo     --//--
*p<             print 'M'
*p<             print 'a'
*ppp<           print 'l'
*ppp<           print 'b'
opp<            print 'o'
*p<             print 'l'
pp<             print 'g'
pp<             print 'e'
o*<             print ' '
*op<            print 'p'
**p<            print 'r'
*op<            print 'o'
*p<             print 'g'
*p<             print 'r'
pp<             print 'a'
*poo<           print 'm'
v               stop

Тот же самый код в ненормализованном виде:

DCBA@?\nZ;|38x0SA3tsN`Lo98*G"'&%$#Sc>`v<zLxwI5tWrDpoAm?Oj)Laf8dc\aZ~X|?U=Y;v9ONS54JnHG/jJCBGF(>b%;_"876Z{321U5.-Qr*N('K%$H(hEf${Abaw=^zs9Zp6Wm3kj0Qglk+v

Или более наглядно (не пытайтесь запустить этот код в интерпретаторе - Malbolge на дух не переносит комментарии, считая их частью своего кода):

DCBA@?\     jump
nZ;         data for 'M'
|38         data for 'a'
x0SA3       data for 'l'
tsN`L       data for 'b'
o98*        data for 'o'
G"'         data for 'l'
&%$         data for 'g'
#Sc         data for 'e'
>`v         data for ' '
<zLx        data for 'p'
wI5t        data for 'r'
WrDp        data for 'o'
oAm         data for 'g'
?Oj         data for 'r'
)La         data for 'a'
f8dc\       data for 'm'
aZ~X|?U     do nothing (some instructions between data & code)
=Y;v9ON     --//--
S54JnHG     --//--
/jJCBGF     --//--
(>b         print 'M'
%;_         print 'a'
"876Z       print 'l'
{321U       print 'b'
5.-Q        print 'o'
r*N         print 'l'
('K         print 'g'
%$H         print 'e'
(hE         print ' '
f${A        print 'p'
baw=        print 'r'
^zs9        print 'o'
Zp6         print 'g'
Wm3         print 'r'
kj0         print 'a'
Qglk+       print 'm'
v           stop

Почти все эти исходники вы можете проверить, например, в дебаггере Маттиаса Эрнста. Очень удобный инструмент, с переключением в нормализованный режим и обратно.

Итак, первая - и, пожалуй, самая сложная часть - завершена. Идем дальше.