Zip

В конце 1990-х команды разработчиков Windows Shell и Internet Explorer внедрили множество потрясающих и сложных структур, позволяющих использовать расширение оболочки и браузера для обработки сценариев, создаваемых третьими сторонами. Например, Internet Explorer поддерживал концепцию подключаемых протоколов ("Что если какой-то протокол, допустим, FTPS станет таким же важным, как и HTTP?"), а Windows Shell обеспечивала чрезвычайно гибкое множество абстрактного использования пространств имён, что позволяло третьим сторонам создавать просматриваемые папки, в основе которых не лежит файловая система от WebDAV ("ваш HTTP-сервер это папка") до папок CAB ("ваш архив CAB это папка"). Работая в 2004 году проект-менеджером в команде по созданию клипарта, я создал приложение .NET для просмотра клипарта прямо из веб-сервисов Office, и набросал черновик расширения Windows Shell, благодаря которому бы казалось, что огромный веб-архив клипарта Microsoft был установлен в локальной папке системы пользователя.

Вероятно, самым популярным (или печально известным) примером расширения пространства имён оболочки является расширение Compressed Folders, обрабатывающее просмотр файлов ZIP. Compressed Folders, впервые появившиеся в составе Windows 98 Plus Pack, а позже и в Windows Me+, позволяли миллиардам пользователей Windows взаимодействовать с файлами ZIP без скачивания стороннего ПО. Вероятно, это может вас удивить, но эта функция была куплена у третьих лиц Microsoft приобрела интеграцию для Explorer, представлявшую собой побочный проект Дэйва Пламмера, а лежащий в её основе движок DynaZIP разработала компания InnerMedia.

К сожалению, этот код уже давно не обновляли. Очень давно. Судя по временной метке модуля, последний раз он обновлялся на День святого Валентина в 1998 году; я подозреваю, что с тех пор в него вносили незначительные изменения (и одну функцию поддержку имён файлов в Unicode, работающую только для извлечения), но всё равно не секрет, что, как сказал Реймонд Чен, этот код "остался на стыке веков". Это значит, что он не поддерживает такие современные функции, как шифрование AES, а его производительность (время выполнения и степень сжатия) сильно отстают от современных реализаций, созданных третьими сторонами.

Тогда почему же его не обновляли? Отчасти в этом виноват принцип "не сломано не чини": реализация ZIP Folders выживала в Windows в течение 23 лет, и при этом вопли пользователей не становились невыносимыми, то есть их вполне всё устраивало.

К сожалению, есть вырожденные случаи, в которых поддержка ZIP оказывается по-настоящему поломанной. С одной из них я столкнулся на днях. Я увидел интересный пост в Twitter о шестнадцатеричных редакторах с возможностью аннотаций (что полезно при исследовании форматов файлов) и решил попробовать некоторые из них (я решил, что больше всего мне нравится ReHex). Но в процессе этого исследования я скачал portable-версию ImHex и попробовал переместить её в папку Tools на своём компьютере.

Я дважды щёлкнул по файлу ZIP размером 11,5 МБ, чтобы открыть его. Затем я нажал CTRL+A, чтобы выбрать все файлы, а затем (это важно) нажал CTRL+X, чтобы вырезать файлы с буфера обмена.


Затем я создал новую папку внутри C:\Tools и нажал CTRL+V, чтобы вставить файлы. И тут всё пошло наперекосяк Windows больше минуты отображала окно "Calculating", но кроме создания одной подпапки с одним файлом на 5 КБ больше ничего не происходило:


Чего? Я знал, что движок ZIP, который используется в ZIP Folders, не был оптимизирован, но раньше я никогда не видел ничего настолько плохого. Спустя ещё несколько минут распаковался ещё один файл на 6,5 МБ:


Безумие какое-то. Я открыл Диспетчер задач, но никакие процессы не занимали мой 12-поточный процессор, 64 ГБ памяти и NVMe SSD. Наконец, я открыл SysInternals Process Monitor, чтобы разобраться, в чём дело, и вскоре увидел первоисточник происходящего.

После нескольких мелких операций считывания из конца файла (где у файла ZIP хранится индекс), весь файл размером 11 миллионов байт считывался с диска по одному байту за раз:


Присмотревшись повнимательнее, я понял, что почти все операции считывали по одному байту, но время от времени после считывания определённого байта выполнялось считывание 15 байт:


Что же находится в этих любопытных смещениях (330, 337)? Байт 0x50, то есть буква P.


В прошлом мне доводилось писать тривиальный код для восстановления ZIP, поэтому я знал, в чём особенность символа P в файлах ZIP это первый байт маркеров блоков формата ZIP, каждый из которых начинается с 0x50 0x4B. По сути, код считывает файл от начала до конца в поисках конкретного блока размером 16 байт. Каждый раз, когда он встречает P, то просматривает следующие 15 байт, чтобы проверить, соответствуют ли они нужной сигнатуре, и если нет, то продолжает побайтовое сканирование в поисках новой P.

Есть ли что-то особенное в этом конкретном файле ZIP? Да.

Формат ZIP состоит из последовательности записей файлов, за которой идёт список этих записей файлов (Central Directory).

Каждая запись файла имеет собственный локальный заголовок файла, содержащий информацию о файле, в том числе размер, размер в сжатом виде и CRC-32; те же данные повторяются в Central Directory.

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

Мы видим, что в заголовке CRC и размеры равны 0, и что они появляются сразу после сигнатуры 0x08074b50 (дескриптора данных (Data Descriptor)), непосредственно перед локальным заголовком следующего файла:


Бит 0x08 во флаге General Purpose обозначает эту опцию; пользователи 7-Zip могут увидеть её как Descriptor в столбце записи Characteristics:


Исходя из размера операции считывания (1+15 байт), я предполагаю, что код подстраивается под блоки Data Descriptor. Почему он это делает (вместо того, чтобы просто считать те же данные из Central Directory), я не знаю.

Хуже того этот черепаший процесс побайтового считывания всего файла происходит не только один раз он повторяется по крайней мере по одному разу для каждого извлекаемого файла. Усугубляет ситуацию то, что эти данные считываются при помощи ReadFile, а не fread().

В конечном итоге, после 85 миллионов однобайтных считываний монитор процессов зависает:


Перезапустив его и сконфигурировав Process Monitor с Symbols, мы можем исследовать эти однобайтные операции считывания и получить представление о том, что же происходит:


Функцию GetSomeBytes перенагружают вызовы, передающие однобайтный буфер в коротком цикле внутри функции readzipfile. Но если посмотреть ниже по стеку, то становится очевидной первопричина этого хаоса это происходит потому, что после перемещения каждого файла из ZIP в папку файл ZIP должен обновиться для удаления перемещённого файла. Этот процесс удаления по сути своей не быстр (поскольку он приводит к изменению всех последующих байтов и обновлению индекса), а его реализация в функции readzipfile (с этим однобайтным буфером чтения) и вовсе чудовищно медленна.

Если вернуться назад, то стоит заметить, что я нажал CTRL+X, чтобы вырезать файлы, что привело к операции перемещения. Если бы вместо этого я нажал CTRL+C для копирования файлов, то ZIP не выполнял бы операцию удаления при извлечении каждого файла. Время, необходимое для распаковки файла ZIP снизилось бы с получаса до четырёх секунд. Для сравнения: 7-Zip распаковывает файл меньше чем за четверть секунды, хоть и немного жульничает.

И вот здесь и происходит протечка абстракции с точки зрения пользователя, копирование файлов из ZIP (с последующим удалением ZIP) и перемещение файлов из ZIP не кажутся сильно различающимися операциями. К сожалению, абстракция даёт сбой на самом деле, удаление из некоторых файлов ZIP оказывается чрезвычайно медленной операцией, а удаление файла с диска обычно происходит тривиально. Поэтому абстракция Compressed Folder хорошо работает с мелкими файлами ZIP, но даёт сбой с крупными файлами ZIP, которых в наше время становится всё больше.

Хотя довольно легко придумать способы значительного улучшения производительности в этой ситуации, подобный прецедент даёт понять, что вероятность совершенствования кода в Windows мала. Возможно, код изменят к его 25-й годовщине?

---

На правах рекламы

Если для работы необходим сервер на Windows, то вам однозначно к нам. Создавайте собственную конфигурацию в пару кликов, автоматическая установка винды на тарифах с 2 vCPU, 4 ГБ RAM, 20 ГБ NVMe или выше.

Присоединяйтесь к нашему чату в Telegram.

В прошлом году я участвовал в соревнованиях JS13K 2019, на которых людям предлагается разрабатывать игры в менее чем 13 КБ кода на JavaScript. Я участвовал с клоном Doom, который назвал Ещё один клон Doom (Yet Another Doom Clone).


Поиграть в него можно здесь. Исходный код выложен сюда.

Зачем создавать клон Doom?

Зачем писать FPS на JavaScript всего в 13 КБ (с учётом сжатия)? По нескольким причинам. Но лучше всего на этот вопрос отвечает раздел FAQ соревнований JS13K Можно ли использовать WebGL?:

Да, но может быть сложно уместить его в 13 килобайта, если вы планируете писать FPS.

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

Именно поэтому я выбрал FPS. Остаётся вопрос: Почему Doom? На него ответить проще: если вы хотите написать FPS, и чтобы он при этом был небольшим, то Doom практически самый минималистичный вариант.

Причина, по которой Doom настолько прост (по современным стандартам) понятна: Doom должен был работать на железе на пять порядков более медленном, чем сегодня. За ту же цену сейчас можно собрать машину, которая способна выполнять в сотню тысяч раз больше работы, чем Pentium 1994 года. Поэтому я решил, что будет интересно попробовать воссоздать нечто наподобие Doom, но вместо ограничений производительности использовать ограничения объёма кода.

Фундамент: 3D-рендерер на JavaScript

Движок игры я начал строить на основе написанного ранее 3D-рендерера, который я хотел реализовать как можно более простым. Оказалось, что благодаря своей простоте он к тому же довольно мал: ядро движка 3D-рендеринга заняло всего примерно 5 КБ сжатого JavaScript, то есть на игру осталось всего 8 КБ. Я решил, что ситуация не так уж и плоха. Если я не будут использовать большие спрайты или файлы объектов, то всё должно получиться.

Движение игрока

Для перехода от 3D-рендерера к движку 3D-игры, по сути, требуется только одно изменение: управляемое игроком движение камеры и повторный рендеринг после каждого движения. Для реализации этого я поместил игрока внутрь параллелепипеда и работал над движком, пока движение не стало правильным. Doom имел очень характерный стиль движения, который я стремился воссоздать.

Первый шаг к этому реализация ускорения движения игрока в направлении его взгляда до какой-то (высокой) максимальной скорости. Я добавил больше ускорения, чем в оригинальном Doom, потому что сегодня это ощущается привычнее. Важнее для воссоздания ощущения Doom было добавление раскачивания камеры при движении игрока.

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

Если ничего не добавлять, то игрок будет продолжать раскачивание с того самого состояния, в котором он находился во время остановки. Это выглядит очень неестественно. Чтобы это исправить, потребовались крошечные изменения: у игрока есть переменная текущего состояния анимации в цикле (по модулю 2 пи), и когда игрок прекращает двигаться во всех направлениях, то переменная сбрасывается на ноль. Это делает движение более чётким, а его начало и завершение выглядят правильно.

Также я добавил одну особенность, которой не было в Doom небольшую величину поворота камеры вдоль продольной оси на каждом шаге. (В Doom его не было, потому что движок позволял выполнять поворот только по оси Z, то есть игрок даже не мог взглянуть вверх.)

Затем я добавил ограничение движения. Нет никакого смысле создавать сложные лабиринты в стиле Doom, если игрок может проходить сквозь стены. Для правильной реализации ограничений нужно сделать игрока сферой, стены плоскостями и вычислять пересечения сферы с плоскостью. Я беспокоился, что это займёт слишком большую часть наших 13 КБ.

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

Реализовать эту систему было довольно сложно, особенно обработать случаи одновременного пересечения лучей с несколькими стенами. Во некоторых ситуациях система даёт сбои, поэтому при создании дизайна уровней я вручную тестировал их на баги и проектировал их так, чтобы баги распознавания коллизий не возникали. (Главное ведь, чтобы работало...)

Object Lathing

Чтобы в игре были объекты, мне нужно каким-то образом их описать. Логичным способом было бы использование формата файлов .obj. К сожалению, он довольно большой и неуклюжий. (Я использовал его в своём предыдущем 3D-рендерере для загрузки стандартного чайника.)

Поэтому вместо него я решил написать минималистичный метод точёных объектов (object lathe):
мы задаём 2D-контур, представленный в виде ряда точек, обтачиванием вращаем точки по кругу для генерации 3D-объекта. Это позволяет создавать красивые объекты, занимающие мало пространства. Например, для описания показанного выше кувшина потребовалось примерно двадцать байтов.

Задолго до разработки игры я также создал тщательно минимизированную до 300 байт реализацию подразделения поверхностей (surface subdivisioning) (которую ранее использовал для 3D-рендерера). Но в конечном итоге мне не хватило места и от неё пришлось отказаться. Однако я особо не жалею, потому что она не добавляла в игру ничего важного.

Игровой цикл

Всё описанное выше было довольно статичным, по миру перемещалась только камера. Однако для создания игры требуется интерактивность. И здесь нам пригодится игровой цикл.

Мы будем использовать совершенно стандартный игровой цикл. Изначально в коде он выглядел так:

      function game_step(now) {          if (game_is_over) return;          frame = requestAnimationFrame(game_step);  player_check_dead();  player_move();          player_clip_walls();          player_fall();          player_set_position();          lights.map(light => light.compute_shadowmap());          camera.draw_scene();          objects.map(object => object.update(dt));          garbage_collect();      }

Да, это красивый и удобный код, но каждая из функций вызывается только один раз. Поэтому они превратились во встроенные функции, и цикл стал некрасивым.

Оружие и враги

Шутер от первого лица не особо интересен, если нам нечем и не в кого стрелять.

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

Модель оружия это просто несколько цилиндров, созданных при помощи object lathe. Первым этапом здесь была реализация естественного движения с оружием. Для этого я снова воспользовался уже имеющимся отслеживанием движения вверх-вниз при ходьбе: пулемёт движется вверх-вниз и в стороны, в зависимости от текущего состояния цикла ходьбы игрока.


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

Распознавание попаданий реализовано как простое сканирование испускаемым лучом (в нём используется тот же код, что и в распознавании коллизий со стенами при движении игрока). При попадании создаются частицы взрыва с небольшой вспышкой.

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

(Чтобы можно было стрелять по потолку и полу, потребовалось ещё одно небольшое дополнение. В противном случае при высоком прицеливании не было бы взрывов, и это казалось бы неправильным. Вся остальная система распознавания коллизий определяет коллизии только по горизонтали, а эти коллизии ориентированы по вертикали, а значит, им требуется специализированный код. На самом деле, написать его было не так сложно: записываем начальную высоту по Z и наклон игрока по поперечной оси (угол относительно плоскости xy), а затем для каждого полигона всей карты проверяем, насколько далеко должен растянуться луч, чтобы попасть по потолку и полу этого полигона; затем проверяем, действительно ли при движении луча на такое расстояние он сталкивается с полигоном в этом месте.)

После этого я сортирую все потенциальные коллизии и выбираю ближайшую.

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


Затем я перешёл к задаче стрельбы по врагам. Сначала я создал очень простую модель-коробку персонажа. Он полностью состоит из кубов, благодаря чему его очень легко хранить: сохраняя просто модель куба, я могу растягивать его в произвольных направлениях и создать врага. Простейший враг состоит из восьми кубов.

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

Сначала блоки, из которых состоял враг, просто разлетались сквозь стены и пропадали с экрана. Это сбивало с толку, поэтому я добавил эффект отскакивания блоков от стен. Если говорить кратко, то отскоки совершенно физически недостоверны. Коллизии снова реализованы при помощи пересечения лучей. Если ближайшая стена полностью находится на плоскости xz, то объекты меняют знак свой скорости по y. Если стена полностью на плоскости, то меняется знак скорости по x. Во всех остальных случаях меняются знаки скоростей по x и y.

Когда позиция объекта меньше, чем высота пола текущей комнаты, скорость по z меняет свой знак и уменьшается на 20%. Каждую секунду объект замедляется на 50% (как будто к нему применяется какое-то гипотетическое трение).

ИИ врагов

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

(а) игрок находится в поле их зрения

или

(б) игрок подстреливает врага, находящегося в поле зрения.

Определение поля зрения тоже реализовано при помощи испускания лучей. Чтобы не тратить впустую такты ЦП на испускание лишних лучей, враг проверяет других врагов всего раз в секунду.

После пробуждения враг начинает двигаться к игроку по прямой. Если на его пути что-то встаёт, то он выбирает новое случайное направление и делает несколько шагов, а затем снова начинает двигаться к игроку. Иногда движущиеся враги стреляют по игроку.

Кроме того, в момент смерти враг запрашивает помощь у других врагов, которых может видеть (снова при помощи испускания лучей). Благодаря этому сложно устранять врагов по одному из-за угла, потому что это скучная механика, и не стоит её поощрять.

Текстуры

Пока картинка выглядит очень скучной, ведь используется всего одна текстура. Я знал, что никак не смогу уместить в игру нарисованные от руки текстуры, даже самые маленькие, поэтому сгенерировал их процедурно. Я решил использовать всего три текстуры: плитки пола, кирпичный паттерн для стен и простой шум Перлина для лавы и взрывов.




Генерация кирпичей довольно тривиальна. Отрисовываем горизонтальные линии через каждые N шагов, а затем вертикальные линии через каждые N со смещением на N/2 в чётных строках. Код выглядит так:

      make_texture(cartesian_product_map(range(256),range(256),(y,x) => {          if ((y%64) <= 2 || Math.abs(x-(((y/64)|0)%2)*128) <= 2) {              return [0,0,0,1];          } else {              var r = .9-perlin_noise[x*256+y]/20;              return [r,r,r,1];          }      }).flat())

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

Шум Перлина визуально гораздо красивее, чем другие типы шумов. Его случайность выглядит намного естественнее, чем простой белый шум. Генерация шума Перлина довольно сложна, поэтому я просто дам ссылку на Википедию и скажу, что сделал так же. Также я добавил небольшое количество шума Перлина к кирпичному паттерну, чтобы он был менее скучным.

Анимации врагов

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


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

Звук

Казалось очевидным, что для добавления звука нужно использовать JSFXR, однако на этом этапе места уже начинало не хватать. Взглянув ещё раз на код, я увидел, что ещё многое можно оптимизировать.

Благодаря последовательности небольших изменений мне удалось сократить его почти в два раза. Самая большая экономия получилась благодаря удалению map из массива в воспроизводимый файл WAV и замене его на вызов функции WebAudio, получающей непосредственно массив float. Ещё одна серьёзная экономия получилась благодаря замене куче операторов case на операции поиска в массиве. То есть я реализовал принцип мультиплексора и вычислил все возможные случаи внутри массива, а затем просто выбирал индекс нужного значения. Это медленнее, зато код короче. После замены циклов for на map и создания вспомогательной функции clamp код оказался достаточно коротким, чтобы можно было написать красивые звуковые эффекты.

Затем я захотел сделать так, чтобы аудиосистема реагировала на то, где находится игрок в 3D-пространстве. Я думал, что эта часть потребует много усилий, но оказалось, что это довольно просто, и теперь в коде есть функция createStereoPanner, выполняющая эту задачу.

В качестве фоновой музыки я переписал среднюю часть токкаты и фуги ре минор. Она просто повторяется бесконечно.

Описание карты

Одной из уникальных особенностей Doom были уровни. Каждая карта больше напоминала лабиринт, по которому игрок бегал в поисках выхода. Для создания клона это был обязательный компонент.

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

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

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

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

Я даже добавил функции, позволяющие создавать циклы for и вызовы/возвраты, чтобы можно было, например, изготавливать лестницы, а затем многократно применять функцию make-stairs там, где мне были нужны лестницы.

К сожалению, проектировать карты всё равно было сложно, потому что для этого требовалось программирование черепашки на языке ассемблера, который разрабатывался как максимально компактный. У меня был всего месяц на создание всей игры, поэтому я никак не мог себе позволить потратить несколько дней на проектирование карт. Более того, на самом деле это не экономило особо много пространства. Так как ограничение в 13 килобайта относится к размеру запакованного zip исходного кода, вполне можно было использовать дублирование одной функции: сжатие zip сэкономит пространство.

Поэтому код черепашки стал таким:

      function run_turtle(commands) {          var regions = []          var turtle_location = [ZERO];          var floor_height = 4;          var ceil_height = 40;          var do_later = [];          for (var i = 0; i < commands.length;) {              var cmd = commands[i++];              // Get the "opcode" and "argument" to the command      var [low, high] = [cmd&31, cmd>>5];              // Opcode 0 is a "make polygon" command              if (high <= 1) {                  var coordinates = [turtle_location[0]]                  coordinates.push(...range(low).map(x=> {                      var dydx = NewVector(((commands[i]>>4)-7)*8,                                           ((commands[i++]%16)-7)*8, 0)                      turtle_location.unshift(turtle_location[0].add(dydx));                      return turtle_location[0];                  }));                  regions.push(new MapPolygon(coordinates,                                              floor_height,                                              ceil_height))                  // Opcode 1 is a "goto" command                  if (high == 1) {                      regions.pop();                  }              }              // Opcodes 4: adjust ceiling              floor_height += 2*(low-15)*(high==4);              // Opcodes 5: adjust floor      ceil_height += 4*(low-15)*(high==5);              // Opcodes 6: backtrack              turtle_location.splice(0,low*(high==6));          }          return [regions, do_later];      }

Чтобы упростить создание карт, я избавился от большей части языка и создал гораздо более простой язык. Я убрал циклы, вызовы функций, повороты и реализовал всего два опкода: make-polygon и goto. Опкод make-polygon получает количество вершин и последовательность байтов, где старшие 4 бита определяют сдвиг по оси x, а младшие 4 бита сдвиг по оси y. После достижения последней вершины цикл завершается и черепашка создаёт многоугольник. Опкод move просто перемещает черепашку в новое место для создания нового многоугольника.

После создания нескольких карт я посмотрел, какие части моего языка turtle занимают больше всего места. Я понял, что трачу много места на перемещение черепашки от многоугольника к многоугольнику. Как можно сократить этот процесс? Обратим внимание, что обычно многоугольники не изолированы: они соединяются с другими многоугольниками вершиной. Поэтому я добавил ещё одну функцию backtrack. При каждом движении черепашки она добавляет своё местоположение в стек. Backtrack извлекает позицию черепашки определённое количество значений назад. Это очень эффективно: более 95% перемещений черепашки было заменено командами backtrack.

Редактор карт

Для удобства создания карт я быстро набросал WYSIWYG-интерфейс. Этот редактор компилирует карты на язык turtle, чтобы их можно было использовать в игре.

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

Так как этот редактор не будет находиться в составе игры, я мог не волноваться о качестве кода или удобстве редактора. Он невероятно уродлив и некрасив, в нём используются непонятные горячие клавиши. (Хотите добавить новый многоугольник? Выберите созданную вершину и нажмите Shift-A для выделения соседнего ребра, а затем E (для экструдирования). Хотите добавить вершину к уже существующему ребру? Shift-A и S (для разбиения). Нужно удалить многоугольник? Shift-Q. Если знать, что делать, то всё вполне логично, но не особо интуитивно понятно.)

Мысли об экономии пространства

Для успешного создания полной игры в 13 килобайтах сжатого JavaScript требуется постоянно помнить о занимаемом кодом пространстве.

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

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

      var pairs = (lst,fn) => lst.slice(0,-1).map((x,i)=>fn(x,lst[i+1],i))      var transpose = (mat) => mat[0].map((x,i) => mat.map(x => x[i]))      var range = (N,a) => Array(N).fill().map((_,x)=>x+(a||0));      var reshape = (A,m) =>          range(A.length/m).map(x=>A.slice(x*m,(x+1)*m));      var urandom = _ => Math.random()*2 - 1;      var push = (x,y) => (x.push(y), x);      var clamp = (x,low,high) => Math.min(Math.max(low, x), high)      var sum = (x) => x.reduce((a,b)=>a+b)

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

В самом некрасивом моём коде я сделал так, что умножения матриц 4x4 стали и очень эффективными, и одновременно очень короткими; для этого пришлось потрудиться:

    var mat_product_symbolic = B =>        `(a,b)=>[${reshape(range(16),4).map(c=>B[0].map((_,i)=> B.reduce((s,d,j)=>`${s}+b[${d[i]}]*a[${c[j]}]`,0))).flat()}]`;    multiply = eval(mat_product_symbolic(reshape(range(16),4));

Для постоянного отображения текущего размера сборки требовался автоматизированный процесс сборки. Сначала скрипт сборки просто запускал uglifier, за которым выполнялся стандартный zip, чтобы я мог отслеживать занимаемое пространство. Вскоре я осознал, что есть оптимизации, которые позволят мне автоматизировать процесс, чтобы ещё больше сжать код. Я написал короткий скрипт, определяющий все имена переменных webgl и заменяющий их короткими однобуквенными именами (потому что uglify этого не делал). Затем я модифицировал эту программу так, чтобы она переписывала длинные имена функций WebGL, например, framebufferTexture2D, коротким трёхсимвольным кодом вида e2m (я брал восьмой символ с конца, второй символ с конца и третий символ с начала). Ближе к концу разработки я узнал о advzip, который ещё больше помог мне с улучшением сжатия.

Между человеком и его криптовалютой стояло несколько квинтиллионов вариантов ключей расшифровки

В октябре Майкл Стэй получил с LinkedIn странное сообщение. Некий незнакомец потерял доступ к приватным ключам своей криптовалюты и попросил у Стэя помощь в возвращении доступа к его $300 000.

Было не так уж и удивительно, что Чувак, как называет его Стэй, нашёл бывшего специалиста по безопасности из компании Google. Девятнадцать лет назад Стэй опубликовал работу с детальным описанием технологии взлома зашифрованных ZIP-файлов. Чувак купил в январе 2016 года биткоинов на сумму порядка $10 000, задолго до бума криптовалют. Он зашифровал приватные ключи в ZIP-файле и забыл пароль. И теперь он надеялся, что Стэй может помочь ему взломать его.

На прошедшей недавно конференции Defcon Стэй описал свои эпичные попытки сделать это.

ZIP популярный формат файлов, используемый для сжатия больших файлов без потерь как небольшой чехол с тесьмой может вместить ваш спальный мешок. Известно, что многие варианты реализации формата ZIP имеют проблемы с безопасностью до того, что прошлым летом даже один американский сенатор обратился в Национальный институт стандартов и технологий с целью исследования этого вопроса. Если мы успешно отыщем этот пароль, я вас отблагодарю, написал Чувак со смайликом в конце. Проведя первичный анализ, Стэй оценил что взлом файла обойдётся в $100 000. Чувак принял предложение всё-таки прибыль должна получиться большой.

Давно я так не развлекался. Каждое утро я с радостью шёл на работу и боролся с этой проблемой, говорит Стэй, в настоящее время работающий техническим директором фирмы Pyrofex, занимающейся технологиями блокчейна. Шифрование ZIP несколько десятилетий назад разработал криптограф-непрофессионал поэтому то, что оно так долго продержалось, довольно примечательно. Однако если некоторые ZIP-файлы можно взломать при помощи готовых утилит, то Чуваку удача не улыбнулась.

В частности поэтому за работу попросили так много. Новые поколения программ ZIP используют авторитетный и надёжный криптостандарт AES, а старые версии, одну из которых использовал Чувак Zip 2.0 Legacy, который часто можно взломать. Степень сложности, однако, зависит от его реализации. Одно дело сказать, что стандарт поломанный, но реально его взломать это совершенно другой вопрос, говорит криптограф Мэтью Грин из университета Джонса Хопкинса.

Помочь Стэю с его подходом могло лишь небольшое количество подсказок. У Чувака до сих пор был ноутбук, который он использовал для создания зашифрованного ZIP что подтверждало его право на владение этими биткоинами, а также давало Стэю информацию о том, какую именно программу ZIP и какой версии использовали для шифрования. Ему также было известно время создания файла, которое ПО Info-ZIP использует для своей криптографической схемы. Огромное количество возможных паролей и ключей шифрования Стэй смог уменьшить до нескольких квинтиллионов.

Для проведения атаки такого масштаба нужно было арендовать облачные мощности для обработки графики. Стэй обратился к Нэшу Фостеру, директору Pyrofex, чтобы тот написал код для криптоанализа и запустил его на GPU общего назначения от Nvidia Tesla. По мере углубления в проект Стэй сумел уточнить атаку и уменьшить время работы программы, требовавшееся для достижения результата.

Изначально мы предполагали, что пару месяцев будем разрабатывать программу, а потом она будет работать ещё несколько месяцев, рассказал Фостер журналу Wired. В итоге Майк сумел более эффективно провести криптоанализ, и мы больше времени потратили на разработку атаки, а на работу у программы ушла всего неделя. Это сэкономило Чуваку уйму денег на аренде инфраструктуры. Лет десять назад это было бы невозможно сделать без сборки специального оборудования, а стоимость проекта, вероятно, превысила бы стоимость его биткоинов.

Однако вопрос того, сработает ли это перемалывание цифр на GPU, всё ещё оставался открытым. После нескольких месяцев труда над этой задачей Стэн, наконец, был готов попробовать. Чувак не предоставил Стэю и Фостеру весь файл целиком он, вероятно, не доверял им, считая, что они могут украсть его криптовалюту, взломав ключи. Благодаря особенностям реализации шифрования в ZIP он мог предоставить Стэю и Фостеру только зашифрованные заголовки информационные записи, касающиеся содержимого файла не передавая его основное содержимое. К февралю, через 4 месяца после первого сообщения с LinkedIn, они подготовили программу и начали атаку.

Она проработала 10 дней и не справилась. Позднее Стэй писал, что был убит горем.

До этого мы встречались с разными багами, но на всех тестах, что я прогонял у себя на ноутбуке, всё работало отлично, говорит он. Если это и была ошибка, она должна была быть какой-то очень уж хитрой, и я беспокоился, что на её поиски у нас уйдёт много времени. Не помогал и тот факт, что в феврале стоимость биткоинов начала падать, а вместе с ней и стоимость файла. Чувак очень беспокоился.

Стэй прошерстил всю программу, беспокоясь о наличии в ней какого-либо неверного предположения или скрытых ошибок. Но затем ему в голову пришла новая идея о том, с какого случайного начального значения [seed] можно начать работу генератора случайных чисел, используемого в их программе. Чувак тоже просмотрел тестовые данные и заметил ошибку, которая возникала, если GPU не обрабатывал правильный пароль при первом проходе. Стэй и Фостер исправили ошибку. Сделав два этих исправления в программе, они были готовы начать заново.

Бах! И из файла выскочила куча биткоинов", говорит Фостер. Мы вздохнули с облегчением, добавляет Стэй.

В итоге стоимость аренды инфраструктуры составила $6000 $7000 вместо изначально предполагавшихся $100 000, говорит Фостер. Чувак заплатил вчетверо меньше, чем ожидал.

Сделка для него получилась отличной, говорит Фостер. Такого рода проекты встречаются редко. Если бы у него была немного другая ситуация, если бы он использовал более свежую версию ZIP, это было бы невозможно сделать. Но в данном конкретном случае мы могли что-то сделать.

Стэй говорит, что после публикации технического описания проекта в апреле к нему обратилось несколько людей с просьбами восстановить пароли к их биткоин-кошелькам. К сожалению, это распространённая проблема. Даже в редакции Wired с этим сталкивались. Но атака на ZIP не имеет ничего общего с кошельками для криптовалют у них иногда могут быть взламываемые недостатки, но они созданы при помощи надёжного современного шифрования.

И всё же факт распространённости ZIP говорит о том, что у исследования Стэя и Фостера есть далеко идущие последствия.

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

Всем бы нам так везло.