Разработка патчера к игре

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

• Поддержка юнити игр
• Дружелюбность к пользователю
• Отображение игровых новостей
• Универсальность для всех игр разработанных нашей студией
• Гибкость настройки
• И самое важное: умение делать небольшие патчи для больших файлов

Как обычно перед тем как изобретать велосипед, я ищу готовые решения проблемы. Но либо я плохо гуглил, либо единственное что удовлетворяло требованием это M2H Patcher с Unity Asset Store.
На внедрение мы потратили несколько дней, и пропользовались им около месяца (до первой и одновременно последней поломки). В один прекрасный день патчер отказался делать патч. Потратив несколько часов на разбирательство я выяснил причину.
Дело в том что этот патчер использовал для работы утилиты bsdiff & bspatch. Для работы утилиты bsdiff нужно max(17*n,9*n+m)+O(1) памяти. Так уж получилось что на самой лучшей машине в офисе было всего 4 Гб оперативки, а файл с ресурсами был уже более 600 Мб. Вообщем bsdiff отказывался с ним работать (до этого время создания патча составляло непотребные 30+ минут).

Тогда то я решил все-таки собрать велосипед.

Алгоритм

Теперь предстояло нагуглить алгоритм сравнения больших бинарных файлов. Достойных кандидатов оказалось два. Это Rsync и алгоритм сортировки суффиксов из bsdiff.
Так как со вторым уже были проблемы, то я остановился на первом.
Его суть заключается в следующем. Разбиваем исходный файл на куски равного размера (далее чанки от англ. chunk).
Для каждого чанка считаем два хэша: сильный и слабый. Сильный хэш — это обычный MD5. Слабый хэш — это кольцевой хэш. Его особенность в том, что если хэш от n до n+S-1 равняется R, то последовательность байт от n+1 до n+S может быть посчитана исходя из R, байта n и байта n+S без необходимости учитывать байты, лежащие внутри этого интервала.
Точно так же нужно посчитать результирующий файл. На выходе у нас должно получится две последовательности хешированных чанков.
Далее мы начинаем сравнивать слабые хэши в файлах в поисках одинаковых чанков. Если хэши совпали, то сравниваем сильные хэши. Ключом алгоритма является создание двух сигнатур — быстрой и стойкой. Быстрая используется как фильтр. Стойкая используется для более точной проверки.
На выходе мы имеем список отличающихся чанков, которые и записываем в патч.

Создание патча

Для наших игр хорошо подходит система, где номер версии обозначается целым числом. Таким образом обычно мы имеем кучу папок с разными версиями текущего проекта: 1, 2, 3, и т.д.

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

string[] files1 = Directory.GetFiles(folder1, "*.*", SearchOption.AllDirectories); string[] files2 = Directory.GetFiles(folder2, "*.*", SearchOption.AllDirectories); 

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

1024 R	star-draft_Data\level1 M	settings.xml	5e54da0d0c1dfca2bbc623979b7bceef	7a64fb8bc102b9d6bc0862ca63cdbb8d A	star-draft_Data\level0	a3d14f5ed8d05164d59025cc910226ea M	star-draft_Data\resources.assets	02466b9218cbf482d562570d8c0c90c8	20f1f88b5036a168bdd26fe7f4f9dadd M	patcher\version.txt	c81e728d9d4c2f636f067f89cc14862c	c4ca4238a0b923820dcc509a6f75849b 

* R — removed, A — added, M — modified
В зависимости от действия там лежит либо сам файл, либо патч к старой версии.
Теперь этот патч можно выложить на любой веб хостинг. Я тестил на дропбоксе.

Важно заметить что для нормальной работоспособности системы в папке с игрой должен лежать файл .\patcher\version.txt. В нем хранится информация о текущей версии игры. Ее считывает патчер и сам же меняет в результате процесса применения патча. Патч билдер старается следить чтобы вы не ошиблись, и версия в файле совпадала с версией указанной в имени папки.

Патчер

При старте патчер считывает файл настроек по пути ./patcher/configuration.xml и проверяет на валидность.
Пример файла с комментариями:

<?xml version="1.0"?> <root>         <!-- Используется в заголовке окна -->         <game_name>TestGame</game_name>         <!-- Запускается при нажатии кнопки "Играть" -->         <game_exe>Test.exe</game_exe>         <!-- Открывается в браузере по умолчанию при нажатии на логотип игры-->         <game_url>http://coolgame.com</game_url>         <!-- URL файла с последней версией игры -->         <check_version_url>http://coolgame.com/version.txt</check_version_url>         <!-- URL каталога с патчами -->         <patches_directory>http://coolgame.com/patches/</patches_directory>         <!-- URL новостей игры -->         <news_url>http://coolgame.com/news_for_patcher.html</news_url>         <!-- Открывается в браузере по умолчанию при нажатии на логотип издателя-->         <publisher_url>http://coolpublisher.com</publisher_url> </root> 

Первым делом патчер проверит свою версию из файла ./patcher/version.txt. Потом он проверит последнюю версию игры по ссылке из настроек. Если последняя версия больше то запускается процесс обновления по схеме:

for (int i = current_version; i < last_version; i++) {     DownloadPatch(URL + string.Format("{0}_{1}", i, i+1));     ApplyDownloadedPatch(); } 

Чтобы применить патч, сначала нужно получить список измененных файлов. Поэтому первым делом достаем из скачанного архива patch_info.txt, парсим его и пробегаем циклом по файлам.
Если файл подлежит удалению, то удаляем. Если добавлен, то распаковываем из архива. Если изменен то применяем патч если хэши совпадают (чтобы не испортить его).
В конце не забываем проверить новый md5 хэш.

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

Статистика

Для проверки я сразу же засунул в него клиент нашей игры на Unity3D, с которым отказался работать bsdiff.
Клиент версия 1 — 1669 Mb
Клиент версия 2 — 1692 Mb (мы добавили модельку с пачкой текстур)
Размер патча при размере чанка 1 Кб и максимальном сжатии архива — 11.8 Mb, что практически похоже на результаты работы патчера с bsdiff’ом
Время создания патча на моей машине меньше минуты, а применения около 10 секунд.

Source: https://bitbucket.org/Agasper/game-patcher