thedeemon | IDFPC: behind the scenes

Готовить ICFPC-like контест оказалось в несколько раз интереснее, чем участвовать, ибо занятных задач пришлось решить намного больше. Задача была устроена в виде квеста из нескольких этапов, где более ранние рассказывают о более поздних, поэтому готовилось все в другом порядке. Сперва был сделан фрактальный компрессор, который сжал заветную картинку до 40 КБ (об этом в предыдущем посте). Затем готовился этап с векторным текстом. Для этого был сделан редактор шрифта. Каждая буква состояла из набора отрезков, точки которых лежат на фиксированной сетке:

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

Он размещал несколько текстов в одном массиве, показывал, как они выглядят, и рендерил результат в файл, который потом после добавления других данных станет файлом-условием. Нарисованные векторами буквы имеют фиксированные позиции, их данные нельзя двигать. Все остальные данные можно разместить между и вокруг этих. Этот же редактор раскидал в свободных местах текстовые строки, с которых начинается игра. Помимо файла с данными он также генерил файл-карту - какие части файла заняты полезными данными, а где свободное место. Эти два файла дальше передавались конпелятору.

VVVM. Общая идея подобной виртуальной машины у меня болталась в голове уже давно. Я до этого делал много разных стековых, регистровых и гибридных ВМ, но каждый раз код и данные там были разделены. И когда исполнялся очередной цикл вроде "while(i < something) ..." значение счетчика должно было читаться из памяти в регистр или в другое место, и я тогда подумал: а что, если записывать его прямо в операнд команды, будет выглядеть, как будто меняется константа-аргумент, при обращении к нему нужно гораздо меньше действий совершить. Тут эта идея вылилась в "очень фон-неймановскую ВМ", где код и данные перемешаны в одном массиве. Где все переменные размещены прямо в операндах команд, и вообще нет стека и регистров, кроме адреса текущей инструкции. И поскольку работа ведется в мутабельном массиве, код тоже меняется. В частности, именно так сделан вызов функций и возврат из них: вызывающий код меняет последнюю команду функции так, чтобы после нее управление возвращалось куда надо. Нехвостовой рекурсии так сделать не получится, но не больно и надо, есть циклы. Байткод должен был уметь "перешагивать" лежащие в файле данные, поэтому идея хранить в команде в явном виде смещение до следующей инструкции оказалась очень кстати. Это не только позволило разбавить код данными и мусором, это также позволило сократить число команд и не вводить отдельной команды Jump. В ассемблере такая команда была, компиляция ее заключалась в указании нужного значения delta_ip предыдущей инструкции. Кроме обычного механизма вызова функций был еще "быстрый": если в цикле у нас некоторая функция вызывается в одном и том же месте, то можно ее "подготовить" (задать адрес возврата) заранее, до входа в цикл, а из цикла просто прыгать на ее начало. Т.е. вызов функций вообще бесплатный получается. Стека нет, аргументы пишутся прямо в код функции, в те места, где они там используются. Чтобы узнать возвращаемое значение, читаем прямо из данных функции, т.к. они после возврата из функции остаются, никуда не исчезают. Для программирования ВМ был сделан простенький язык с переменными, ветвлениями, циклами и функциями, он компилировался в некий ассемблер, состоящий из инструкций ВМ и псевдоинструкций вроде Jump "name" и Label "name", из него уже генерился бинарный код. Придумывать синтаксис и делать парсинг поленился, поэтому писал на смеси AST и eDSL:

let (+@) a b = Bin(Add, a, b) 
let (-@) a b = Bin(Sub, a, b)  
let band a b = Bin(And, a, b)  
let copy s = Bin(Add, Var s, Num 0) 
let const n = Bin(Add, Untitled2, Num (n-2)) 
let (<--) v e = Arith(v,e)  
... 
 
  Fun("random", ["bound"], [     
    Var "x" <-- Var "x" *@ Num 34521589; 
    Var "x" <-- Var "x" +@ Num 99173; 
    Var "value" <-- band (Var "x") (Num 1048575); 
    IfLess(def "value" 4, def "bound" 100, [], [ 
      Var "bound1" <-- copy "bound";       
      Var "n" <-- Var "value" /@ def "bound1" 4; 
      Var "n" <-- Var "bound" *@ def "n" 0; 
      Var "n1" <-- copy "n"; 
      Var "value" <-- Var "value" -@ def "n1" 0; 
    ]);     
    var "x" 666; 
  ]); 
   
  Label "start"; 
  Var "zero" <-- Var "zero" +@ def "zero" 0; 
  Var "read_data.pdata1" <-- const (-6); 
  Var "read_data.pdata2" <-- const (-6);   
  Prepare("read_byte", "rubits"); 
  Prepare("read_int", "read_byte_calling_read_int"); 
  Prepare("read_data", "read_data_from_read_int"); 
  var "hp" (memstart + 1048576*4);  
  Call("initmem", []); 
 
  PrintOnce "Codeword: MANIAC\n"; 
   
  Var "x0" <-- const 0; 
  Var "y0" <-- const 0;     
   
  Label "newblock";     
     
  Var "size" <-- const 16; 
  Var "q" <-- const 0; 
  Var "q4" <-- const 0; 
   
  Label "someblock"; 
   
  Call("read_ubits", [const 1]);   
  Var "split_flag" <-- copy "read_ubits.value"; 
  IfLess(def "split_flag" 44, Num 1, 
  [ 
    Call("read_ubits", [const 9]); 
    Var "process_block.x" <-- copy "read_ubits.value"; 
   
    Prepare("read_ubits", "ub3"); 
    FastCall("read_ubits", "ub3"); 
    Var "process_block.y" <-- copy "read_ubits.value"; 
   
    Var "read_ubits.nbits" <-- const 7; 
    Call("read_bits", []); 
    Var "process_block.k" <-- copy "read_ubits.value"; 
   
    Var "read_ubits.nbits" <-- const 10; 
    Call("read_bits", []); 
    Var "process_block.delta" <-- Var "read_ubits.value"  +@ Num 128;     
    Call("process_block", []); 
       
  ], [ (*else: split=1 *) 
    Var "size" <-- Var "size" /@ Num 2; 
    Jmp "someblock" 
  ]); 
...

Написан конпелятор был на окамле, конечно же. Имея карту свободных мест в файле, он аккуратно размещал в свободных промежутках инструкции откомпилированной программы, но не подряд - чтобы оставить место для мусора, чтобы при просмотре по F3 команды ВМ не были заметны так уж откровенно. Также этот конпелятор разместил в файле сжатые данные картинки. Код для ВМ читал поток битов из сжатой картинки, составлял программу действий по разжатию для каждого пикселя, после чего в псевдослучайном порядке выводил эти программы в виде кода для псевдоэрланга. Наконец, разместив код для ВМ и сжатую картинку, конпелятор проходился по файлу и все незанятые места заполнял рэндомом, которого там получилось больше половины всей BMPшки. Вот ее карта: черным обозначены данные векторных художеств и текстовые строки, темно серым - код ВМ, светло серым - сжатая картинка, а белым - рандомный шум. Цветные точки получились на границах между областями, т.к. точки хранятся по 3 байта, а данные по 4:

Конпелятор на окамле, все остальное - на D. Включая веб часть, принимающую ответы и показывающую таблицу результатов. Для этих целей заюзал Дишный киллер-апп - vibe.d. Веб часть клепалась в последние часы перед началом контеста (раньше не вышло, т.к. перед этим больше недели неожиданно потерял из-за экстренной поездки на материк, вернулся домой менее чем за сутки до начала соревнования), фреймворк этот видел первый раз в жизни, но ничего, с опозданием всего в 15 минут все получилось запустить, и оно отлично себе работает до сих пор, съев всего мегов 5 памяти и 0% процессора.

Проверял задание на С++ (векторная часть и ВМ) и окамле (интерпретатор псевдоэрланга в полсотни строк, включая парсинг). Проверка оказалась жизненно важной - нашлось несколько багов, с которыми файл с заданием получался совсем негодным. А так исправил, и все прошло неплохо. Надо будет еще замутить, только не очень скоро, быстро это все не делается. Этот контест готовился потихоньку в свободное от отдыха время где-то с середины ноября.