Предыстория

У меня есть убогий дешевый планшет на Windows 10 с одним гигабайтом оперативной памяти и 16 гигабайтами места, в пределах которого установлен Windows 10. Чтобы Windows 10 мог хоть как-то скачивать и устанавливать обновления — я скрутил размер файла подкачки в ноль и файл pagefile.sys перестал занимать драгоценные гигабайты.

После этого я с удивлением обнаружил, что для просмотра более-менее крупных сайтов на этом планшете невозможно использовать ни Chrome, ни Internet Explorer, ни даже старую Opera 12. Все они пытаются пару раз показать сайт, перезагружают его снова (он, по видимости, не влезает в настоящую оперативную память без файла подкачки) и выдают после второй попытки загрузки сообщение о неудаче.

Почему при размере исходного HTML-кода сайта в несколько сотен килобайт — компьютер с гигабайтом оперативной памяти не может его отрисовать?

В Dolphin 5.0 можно было хотя бы загрузить любую игру с GameCube. Кроме одной. Сложный способ использования блока управления памятью в PowerPC Star Wars: The Clone Wars до недавнего времени не позволял играть в неё через Dolphin. Но в версии Dolphin 5.0-540 эта проблема наконец решена: эмулятор научился загружать все игры GameCube из официальной библиотеки консоли.

Этот анализ Super Metroid уже довольно долго лежал на моём сайте. После прочтения анализа дизайна подземелий Zelda, я понял, что стоит опубликовать свою статью на Gamasutra. Я предполагаю, что читатели в какой-то степени знакомы с франшизой Metroid или, по крайней мере, с играми жанра «метроидвания». Поэтому я пропущу ознакомительную часть и сосредоточусь на дизайне уровней и приёмах, которые использовали дизайнеры для того, чтобы направлять пользователя в игровом процессе, который кажется случайным, но на самом деле таким не является.

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

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

Diablo 1 — это классический roguelike 1996 года в жанре hack and slash. Это была одна из первых успешных попыток познакомить широкие массы с roguelike, которые до этого имели нишевую графику в виде ASCII-арта. Игра породила несколько сиквелов и множество имитаций. Она известна своей тёмной, мрачной атмосферой, сгущающейся по мере спуска игрока в подземелья, располагающиеся под городом Тристрам. Это была одна из первых для меня игр с процедурной генерацией карт, и возможность генерации столь правдоподобных уровней просто потрясла меня.

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

Благодарю Дэвида Бревика и команду Blizard North за создание такой потрясающей игры, а также galaxyhaxz и команду Devilution за их удивительную работу по восстановлению читаемого исходного кода проекта.

Project Hospital — это игра об управлении зданием больницы со всеми стандартными аспектами жанра: динамическими сценами, создаваемыми игроком, множеством активных персонажей и объектов, развёрнутой системой UI. Чтобы заставить игру работать на разном оборудовании, нам пришлось приложить много усилий, и это стало отличным примером печально известной «смерти от тысячи порезов» — множества мелких шагов, решающих кучу очень специфических проблем и кучи времени, потраченного на профилирование.

Уровень производительности: чего мы хотели достичь

На раннем этапе разработки мы определились с основными параметрами: максимальной величиной сцен, уровнем производительности и системными требованиями.

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

Мы твёрдо были уверены, что игра должна работать в 1080p с приличной частотой кадров даже на интегрированных графических картах, и саму по себе эту цель достичь было не так трудно: основным ограничивающим фактором является ЦП, особенно при увеличении объёмов больницы. Современные интегрированные видеокарты начинают испытывать проблемы только при разрешениях примерно от 2560 x 1440.

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

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

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

Навигация по лесу

Алгоритм поиска пути A* — это мощный инструмент для быстрой генерации оптимальных путей. Обычно A* демонстрируют при навигации по картам из сеток, но он может использоваться не только для сеток! Он может работать с любыми графами. Можно использовать A* для поиска пути в мире круглых препятствий.


В оригинале статьи все изображения интерактивны.

Как один алгоритм решает обе эти задачи? Давайте начнём с краткого описания того, как работает A*.

Алгоритм A*

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

На каждом шаге алгоритма A* оценивает множество частичных путей и генерирует новые пути, расширяя наиболее многообещающий путь из множества. Для этого A* хранит частичные пути в очереди с приоритетами, отсортированном по приблизительной длине — истинной измеренной длине пути плюс примерное оставшееся расстояние до цели. Это приближение должно быть недооценкой; то есть приближение может быть меньше истинного расстояния, но не больше него. В большинстве задач поиска пути хорошей преуменьшенной оценкой является геометрическое расстояние по прямой от конца частичного пути до конечной точки. Истинный наилучший путь до цели от конца частичного пути может быть длиннее, чем это расстояние по прямой, но не может быть короче.

В мире ПО существует огромное количество программ, забытых своими разработчиками. Хорошо, когда уже есть хорошая альтернатива. А если ее нет? В программе может катастрофически не хватать каких-то мелочей, некоторые досадные ошибки могут годами доставлять массу неудобств пользователям, а на новых версиях ОС программа и вовсе может отказаться работать. Далеко не всегда имеются исходные коды, чтобы привести программу в порядок. Если программа простая — не составит труда за короткий срок создать альтернативу. Но если программа большая и сложная, что же делать в таком случае? Не всегда рационально тратить время и деньги на разработку полного аналога, ведь расширить в разумных рамках функциональность и исправить большинство ошибок можно уже в готовом исполняемом файле.
В этой статье будут продемонстрированы методики модификации исполняемых файлов на примере расширения функциональности легендарной игры Age of Empires II (стратегия реального времени).

TL;DR. В статье рассказывается об обратной разработке клиента Dropbox, взломе механизмов обфускации и декомпиляции клиента на Python, а также изменении программы для активации функций отладки, которые скрыты в обычном режиме. Если вас интересует только соответствующий код и инструкции, пролистайте до конца. На момент написания статьи код совместим с последними версиями Dropbox, основанными на интерпретаторе CPython 3.6.

Введение

Dropbox очаровал меня сразу с момента своего появления. Концепция по-прежнему обманчиво проста. Вот папка. Кладёшь туда файлы. Он синхронизируется. Переходишь к другому устройству. Он опять синхронизируется. Папка и файлы теперь появились и там!

Объём скрытой фоновой работы на самом деле поражает. Во-первых, никуда не исчезают все проблемы, с которыми приходится иметь дело при создании и обслуживании кросс-платформенного приложения для основных десктопных операционных систем (OS X, Linux, Windows). Добавьте к этому поддержку различных веб-браузеров, различных мобильных операционных систем. И мы говорим только о клиентской части. Меня интересует также бэкенд Dropbox, который позволил достичь такой масштабируемости и низкой задержки с безумно тяжёлой рабочей нагрузкой, которую создают полмиллиарда пользователей.

В продолжение темы расширения функциональности готовых программ хотелось бы рассказать об ещё одном способе изменения логики работы уже скомпилированной программы, который не требует делать изменений в самом исполняемом файле. Это может пригодиться при распространении вашей модификации в США, где прямое вмешательство в исполняемый файл строго осуждается. Речь пойдёт о создании крошечной прокси-dll (всего ≈4 килобайта) для подмены используемой приложением библиотеки на примере ddraw.dll.

Как показывают годы, шансов увидеть оригинальный исходный код — или хотя бы ремейк — первой части Diablo у нас практически нет (событие The Darkening of Tristram в Diablo III в честь 20-летия выхода первой части — это, конечно, хорошо, но все же немного не то, чего ожидали поклонники). И пусть последнее обновление для игры вышло в 2001 году, и сама Blizzard давно перестала поддерживать и продавать ее — память о ней по-прежнему остается жива в наших сердцах. Что лишний раз и подтвердил некий GalaXyHaXz, решивший произвести реверс-инжиниринг игры.

Исходный код доступен на Github. Проект Devilution, который его автор GalaXyHaXz окрестил «деволюцией Diablo», занял у него свыше 1,200 часов — 4 месяца работы. Также не пропустите объемные комментарии автора, проливающие свет на исходный код игры, и расположенные в другом репозитории. Сам код пока выглядит неважно, но будет продолжать приводится в порядок по мере прогресса работы над другими модулями игры.

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

B 1998 году Blizzard отдала исходный код Diablo двум студиям: Synergestic Software, которая занималась разработкой дополнения Hellfire, и Climax Studios, работавшей над портом для Playstation. Отдел QA Sony в Японии не в первый раз «радует» своими утечками, отличились они и на этот раз — в японской версии порта был случайно забыт символический файл (a symbolic file), который включал в себя функции, данные, типы и многое другое. Это и позволило восстановить оригинальные функции, глобальные переменные, структуры данных и прочее. Бета-версия порта для Playstation также утекла, и в ней лежал еще один подобный файл, что значительно упростило задачу.

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

while(running) {
    update();
    render();
    display();
}

Очень просто! Теперь игра работает с 60fps и всё идёт как по маслу. Готово. Спасибо, что прочитали этот пост.


Ну ладно, очевидно, что всё не так хорошо. Что если у кого-то слабый компьютер, который не может рендерить игру с достаточной для обеспечения 60fps скоростью? Что если кто-то купил один из тех крутых новых 144-герцовых мониторов? Что если он отключил в настройках драйвера vsync?

В данной статье рассматривается перехват функций графического API на примере DirectX 9 под x64 применительно к игре Dota 2.

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

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

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

Здесь надо сказать, что код, который восстановили, по текстовому представлению имеет мало общего с тем кодом, который был изначально написан программистом и скомпилирован в исполняемый файл. Восстановить точно бинарный файл, полученный от компилируемых языков программирования типа C/C++, Fortran, нельзя, так как это алгоритмически неформализованная задача. В процессе преобразования исходного кода, который написал программист, в программу, которую выполняет машина, компилятор выполняет необратимые преобразования.

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

Авторы: к.ф.-м.н. Чернов А.В. (monsieur_cher) и к.ф.-м.н. Трошина К.Н.

Как с помощью самых общих предположений, основанных на знании современных процессорных архитектур, можно восстановить структуру программы из бинарного образа неизвестной архитектуры, и дальше восстановить алгоритмы и многое другое?

В этой статье мы расскажем об одной интересной задаче, которая была поставлена перед нами несколько лет назад. Заказчик попросил разобраться с бинарной прошивкой устройства, которое выполняло управление неким физическим процессом. Ему требовался алгоритм управления в виде компилируемой С-программы, а также формулы с объяснением, как они устроены и почему именно так. По словам Заказчика, это было необходимо для обеспечения совместимости со «старым» оборудованием в новой системе. То, как мы в итоге разбирались с физикой, в рамках данного цикла статей мы опустим, а вот процесс восстановления алгоритма рассмотрим подробно.

Практически повсеместное использование в массовых устройствах программируемых микроконтроллеров (концепции интернета вещей IOT или умного дома SmartHome) требует обратить внимание на бинарный анализ встраиваемого кода, или, другими словами, бинарный анализ прошивок устройств.

Бинарный анализ прошивок устройств может иметь следующие цели:

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

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

Приветствую вас, товарищи. Не слышал о пока-ещё-не-опенсорсной GHIDRA, наверное, только глухой/слепой/немой/без_интернета реверс-инженер. Её возможности из коробки поражают: декомпиляторы для всех поддерживаемых процессоров, простое добавление новых архитектур (с сразу же активной декомпиляцией благодаря грамотному преобразованию в IR), куча скриптов упрощающих жизнь, возможность Undo/Redo… И это только очень малая часть всех предоставляемых возможностей. Сказать что я был впечатлён — это практически ничего не сказать.

Большинство крупных многопользовательских игр рано или поздно сталкиваются с тем, что не все пользователи играют честно. В нашем шутере Warface в какой-то момент это стало ощущаться особенно сильно. Для борьбы с читерами мы используем целый комплекс решений. Одним из компонентов этого комплекса является наша внутренняя разработка под названием MRAC (Mail.Ru AntiCheat). После ее внедрения мы добились хороших результатов: среднее количество ежедневно улетающих в бан читерских аккаунтов упало с 17000 в начале года до 1500 сейчас, при том, что количество жалоб от пользователей на читеров существенно уменьшилось. На выявление подозрительной активности и блокировку аккаунта сейчас уходит примерно 5 минут, вместо прежних 20. Сейчас система распознает и реагирует на более чем 200 сигнатур читерского ПО и постоянно совершенствуется.

Я уже перестал вздрагивать и удивляться, когда звонит телефон и в трубке раздается жесткий уверенный голос: «Вас беспокоит капитан такой-то (майор такой-то), вы можете ответить на пару вопросов?» Почему бы не поговорить с родной полицией…

Вопросы всегда одни и те же. «У нас есть видео с подозреваемым, пожалуйста, помогите восстановить лицо»… «Помогите увеличить номер с видеорегистратора»… «Здесь не видно рук человека, пожалуйста, помогите увеличить»… И так далее в том же духе.

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


И ладно бы только русские дяди Степы беспокоили, пишут и западные Пинкертоны.

Взлом музыки для демократизации производного контента

Отказ от ответственности: вся интеллектуальная собственность, проекты и методы, описанные в этой статье, раскрыты в патентах US10014002B2 и US9842609B2.

Вот бы вернуться в 1965 год, постучать в парадную дверь студии «Эбби-Роуд» с пропуском, зайти внутрь — и услышать настоящие голоса Леннона и Маккартни… Что ж, давайте попробуем. Входные данные: MP3 среднего качества песни «Битлз» We Can Work it Out. Верхняя дорожка — входной микс, нижняя дорожка — изолированный вокал, который выделила наша нейросеть.

Есть класс задач, которые нельзя ускорить за счёт оптимизации алгоритмов, а ускорить надо. В этой практически тупиковой ситуации к нам на помощь приходят разработчики процессоров, которые сделали команды, позволяющие выполнять операции на большим количеством данных за одну операцию. В случае x86 процессоров это инструкции сделанные в расширениях MMX, SSE, SSE2, SSE3, SSE4, SSE4.1, SSE4.2, AVX, AVX2, AVX512.

В качестве «подопытного кролика» я взял следующую задачу:

Есть неупорядоченный массив arr с числами типа uint16_t. Необходимо найти количество вхождений числа v в массив arr.

Классическое решение, работающее за линейное время выглядит так:

int64_t cnt = 0;
for (int i = 0; i < ARR_SIZE; ++i)
    if (arr[i] == v)
        ++cnt;

В таком виде бенчмарк показывает следующие результаты:

------------------------------------------------------------
Benchmark                     Time           CPU Iterations
------------------------------------------------------------
BM_Count                   2084 ns       2084 ns     333079

Под катом я покажу как его ускорить в 5+ раз.