Отчёт команды THIRTEEN

TheDeemon’s Winter Contest

2012

Spoilers ahead!!!!

brox: В этот раз решили вживую не собираться - тем более, что tilarids принял ислам  буддизм путешествовал по Непалу. Скайпа оказалось вполне достаточно. Количество участников тоже было оптимальным, как я считаю - свежие идеи генерировались и реализовывались довольно быстро.

Беглый взгляд внутрь бинарника выявил следующий текст:

### These three # signs marked the beginning of data segment as well as first comment. Grep is your friend now.

### RGB triplets in this file do not really store colors.

### Each triplet of bytes correspoding to a pixel contains values A,B,C (in this order), each a signed 8-bit integer.

### Remember that BMP stores image upside-down, so first bytes of data segment are first triplets of last row of image.

### Let X=70 and Y=79 be coordinates of current pixel. Let VX=18 and VY=26 (signed 8-bit integers) be current vector. Let CLR=0.

### Loop: take values A,B,C from triplet corresponding to current pixel in this BMP.

### Xor VX with A, VY with B and CLR with C.

### If CLR is not 0 draw a line from (X,Y) to (X+VX,Y+VY).

### Add VX to X and VY to Y, repeat the loop until A=B=C=0.

### So first visited points should be (70,79), (70,87), (64,79), (64,87)...

### Codeword: play

Кодовое слово я ввел, и мы получили первые очки.

Тут записана готовая программа на псевдокоде, ее оставалось лишь напедалить. Я передал бразды tilaridsу, и уже спустя минут двадцать мы лицезрели первую скрытую картинку:

(san: заценили шрифтец!)

и продвинулись еще немного в scoreboard. Следуя указаниям с картинки, мы изменили начальные условия и получили такой результат:

Аналогичные действия, и мы уже здесь:

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

Sanny принялся писать брутфорсер, чтобы нагенерить картинок для всевозможных адресов

san: Решено было начать рисовать со всех возможных векторов, со всех возможных точек. Число вариантов составляло 200*400*256*256, что с современными технологиями не составляет проблемы. Ограничение выбрали следующим: ни одна нарисованная линия не должна быть длиннее 8 (там же был намек такой, что шрифт будет только один). С указанным ограничением количество возможных вариантов очень уменьшалось. А если учесть, что отсекались еще и те варианты, которые в процессе рисования уходили за границу, и те, где нарисовано меньше 20 линий, то мы получили около 3000 подходящих  картинок. Я начал их листать глазами и увидел там множество битых картинок:

Поначалу я нашел только заветное кодовое слово “Cartesian”, но коллеги обнаружили еще и следующее:

С этой картинкой была история, что вначале нашли картинку, у которой в одном месте не прорисовался плюсик, а был нарисован минус (tilarids: если это было сделано специально, то брависсимо!). То есть недорисованную картинку. Реализовав алгоритм, получили нерабочую программу. На понимание этого ушло часа полтора, после чего tilarids поставил плюсик где надо, и получил заветное слово. Мой алгоритм на Java всё еще глючил, потому что я опечатался и вместо i в одном месте поставил 0:

brox: Пока san искал ошибку, все остальные долго выясняли, с какого адреса в бинарнике начинается реальный машинный код, но оказалось, что комментарии, которые были в самом начале, дают верный адрес: 0x36 в исходной bmp. Прибавив сюда IP=32, что соответствует смещению 32*4=128 байт, отпарсили первую инструкцию:

00000000B6:  C6 06  03 00

Покуда сомневались, tilarids нашел 2 точки запуска, которые выдавали что-то на экран, и мы получили 2 заветных слова: MANIAC, и WADLER, и еще романтические фразы:

Imagine a system with a lot of parallel processes, each with its own program and variables. On each iteration each process runs its program once. After all of them ran their programs follows next iteration. Variables of each process keep their values between iterations. All variables are integer. Initially they are filled with arbitrary values between 0 and 255. Each process has a mailbox, can send values to other processes (put in their mailbox) and receive values by reading from its own mailbox.

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

san: К этому моменту я поправил баг в Java программе, и запустил с известного адреса. Выведя “maniac”, программа задумалась, а через некоторое время на экран стали лезть вместе с найденным ранее следующие слова:

Here are the programs:

brox: Очень любопытно, но на этом все. Как все, а где обещанные programs? Начали нервничать, пробовали даже снять дамп памяти VM, поискать в нем чего-нибудь глазами... Естественно, ничего там интересного не нашли. Надо было просто подождать.

И через некоторое время полезло:

Process 327438:

  send Value to process 233125,

  send Value to process 114668,

  send Value to process 113287,

  [Q,J,P,W] <- receive(4),

  T <- (Q + J + P + W + 2) / 4,

  Value <- -228696614 * T / 64 + 1086.

Process 816191:

  send Value to process 869710,

  send Value to process 584835,

  send Value to process 64025,

  [M,T,O,L] <- receive(4),

  E <- (M + T + O + L + 2) / 4,

  Value <- 43 * E / 64 + 1023.

....

И оно лезло бесконечно, и никак не останавливалось.

И так далее, а в конце вот такое вот:

Run 7 iterations. Now Value variables of processes are intensities of pixels of a 1024x1024 bitmap filled rowwise.

Всего нагенерилось 247 мегабайт текста.

san: После этого стали решать как это всё будем делать. Tilarids тут же с места взялся писать симуляторы мейлбоксов на питоне, а я увидел здесь формулу:

Anew[n] = AVG(Aold[p1] + 0.5, Aold[p2] + 0.5, Aold[p3] + 0.5, Aold[p4] + 0.5) * n + p

где p1..p4 - это связи между процессами, описанные в предыдущих 247 мегабайтах, и на итерациях оно всё должно устаканиваться в стабильные значения. Покуда tilarids писал мейлбоксы, я занялся генерацией C кода, который получался после обработки большого файла, и содержал в себе зашитыми все константы. В результате получился 100МБ код, который не откомпилился компилятором gcc, т.к. не хватило памяти. И питоном он тоже не отпарсился по той же причине. И я забил.

В это время tilarids тоже закончил, у него что-то получилось, и он обрадовал всех следующей картинкой:

san: Моя жена, случившаяся неподалёку, сразу опознала men in black, и я тут же побежал вводить сначала matrix, а потом men in black. И ура, у нас 100 баллов!

После этого началась рефлексия на тему что это было, которая продолжалась и на следующий день.

Во-первых картинка получилась некрасивая. Мы посмотрели на код с мейлбоксами и увидели там странные константы:

Process 677788:

  [G,X,W,T] <- receive(4),

  A <- (G + X + W + T + 2) / 4,

  Value <- -228696581 * A / 64 + 1134.

На текущий момент мы так и не поняли, почему так. Всякий тюнинг генерирующей этот текст программы результатов не дал: перепроверили и знаковые и беззнаковые операции, и tilarids переписал генерилку на C++, всё одно получались те же самые числа.

Также, симулятор мейлбоксов был проверен с рабочими переменными по байту и 4-байтовому значению, и всё что получилось, было следующее:

Анализ текста показал, что таких чисел 8 разных штук, что все они рядом, и что ячейки, которые используют эти константы, чаще связаны между собой, а положительные константы для умножения лежат от нуля до 60. Также мы нашли, что константы для суммирования лежат в странных диапазонах: 128 ... 320, затем в районе 800, 900 и между 1004 и 1151 с дырками. Это очень странные числа.

Далее brox предположил, что мы имеем дело с ifs фрактал кодингом, по описанию там делаются похожие действия.

(Чтобы проверить это наверняка, надо отследить связи процессов для одного квадратика 8х8 пикселей)

Upd 17.12.2012 от tilarids: По подсказке автора после контеста стало ясно, что таких странных констант там быть не должно, а значит - ошибка в реализации VVVM. Переписал Java реализацию на С++ и, углубившись в отладку виртуального кода, обнаружил проблему: невалидная реализация опкода NOT. Инверсилась память по неправильному адресу. При этом программа отрабатывала и выдавала узнаваемую картинку в конце! Исправив этот баг, удалось получить уже вот такую картинку:

Сам код в машине довольно интересный, есть намеки на процедуры и ABI, можно писать декомпилятор.

SUMMARY

(tilarids:

Немного сухой статистики:

29 коммитов в репу, 2160 строк на Java, 541 строка на Python, С++ был уже после окончания контеста. Выводы по языкам - хотите шустро, используйте Java, Python даже с PyPy медленный, да и работа с signed/unsigned байтами/словами в нём неудобная)

Команда получила большое количество fun-а, и мы хотим еще. Организатору огромное спасибо! Ждем призов!

Огромное спасибо darkus за спонсорскую инициативу!