Category: лытдыбр

Category was added automatically. Read all entries about "лытдыбр".

2014-04

ICFP Postmortem: Team ryba, part 4

(начало здесь, здесь и здесь)

Итак, что же мы имели по состоянию на начало следующего рабочего дня, позднее воскресное утро? В минусе были несломанный алгоритм шифрования, непонятно куда применимые адаптации, не всегда работающий активатор и загадочный ген hitWithTheClueStick, в котором явно было что-то очень полезное, только вот вытащить это было никак. Зато в плюсе были дизассемблер, таблица генов и некоторое понимание того, как эта штука работает.

А работает она, кстати, крайне красиво. Очень сжато это объясняется в хелпе, только фиг это поймёшь с первого раза. :) В отличие от обычного компьютера, который передвигает instruction pointer по памяти фиксированного размера, в интерпретаторе DNA instruction pointer всегда указывает в начало, зато размер памяти переменный, и код постоянно копируется туда-сюда. То есть, например, вызов функции (гена) - это копирование в начало DNA (в красную зону, если пользоваться терминологией из хелпа) тела функции из фиксированной области (зелёной зоны) и генерация кусочка кода, который потом вернёт управление обратно. Условный переход - это поиск в памяти значения true или false по определённому offset'у и пропуск определённого количества байт, если оно там нашлось.

Вооружённые этим пониманием, мы пришли к молчаливому согласию забить пока что на то, что мы не понимаем, и постараться извлечь максимум пользы из того, что мы уже поняли. То бишь, попробовать составлять префиксы, которые модифицируют код отрисовки картинки. Собственно, исходная DNA уже содержит в том или ином виде код отрисовки всех или почти всех кусков, которые должны быть на результирующей картинке, но которых нету на исходной, и вопрос только в том, как именно сделать, чтобы этот код начал работать.

Подробно рассказывать, что именно и как нам удалось пропатчить, я не буду, поскольку организаторы просили-таки не разглашать результаты до их окончательного объявления, а список пропатченных областей практически эквивалентен этому самому результату. :) Так или иначе, времени на эксперименты с разными вариантами патчей ушло довольно много. Занятие это было изрядно ностальгическим - доводилось мне в своё время менять 74 на EB в коде проверки регистрации всяких разных досовых софтинок. :) Здесь дело осложнялось, во-первых, тем, что не было простого способа кодировать переходы назад (вперёд-то просто - инструкции пропустить, а назад - нужно как-то хитро оригинальный код копировать), и во-вторых, тем, что значения true и false в закодированном виде занимали разное количество acid'ов. Так что обходились в основном пропуском кусков методов (в частности, переходов) и изменением числовых параметров, передаваемых в функции.

Интереснее было с битыми генами. Нам намекали, что некоторые гены могут быть повреждены и их как-то можно восстановить, но хитрость была в том, что каждый ген надо было восстанавливать по-своему. Нам удалось восстановить три из них. Для одного из них имелись коды Хэмминга, упоминавшиеся в одной из страничек документации. Вызывать встроенную функцию коррекции мы не научились, поэтому я просто вбил таблицу кодов из википедии (брутфорс - наше всё) и сделал генератор нужного патча на Java. Для другого гена нашлась просто его копия задом наперёд, на которую намекала страничка про палиндромы. С третьим оказалось совсем смешно - он был заражён вирусом. :) С вирусом разбирались Майк с Лёшей, поэтому рассказ о том, в чём там была фишка, я оставлю им.

По дороге Майк с Лёшей ещё больше ускорили нашу рендерилку, и к концу она справлялась с отрисовкой картинки уже всего за полторы минуты.

Последние префиксы, которые мы пытались отсылать на сервер уже в начале шестого утра, почему-то результата совершенно не давали, но мы решили, что утро вечера мудренее, и пошли по домам спать. :)

Ну и в понедельник, за последние два с половиной часа контеста, мы с Лёшей подчистили хвосты, починили некоторые из патчей, которые не заработали в воскресенье, и получили в итоге вполне весомое улучшение итогового результата. Насколько он в итоге хорош - узнаем в октябре. :)

Суммарное время, потраченное на работу, получается примерно таким: 16 часов в пятницу, 14 в субботу, 14 в воскресенье и 2 в понедельник. Итого 46 из 72. При этом я не могу сказать, что у нас было много больших продолбов или хождения по ложным следам - основная часть времени была потрачена вполне по делу. Поэтому очень интересно, получился ли осмысленный результат хотя бы у кого-нибудь из lightning division, в котором результат надо было сдать через 24 часа.

Ну и ещё немного цифр для статистики: примерно 4К итоговый префикс, 165К кода на Java, 306 коммитов в Subversion.

Вроде как всё, отчёт окончен. :)