Game Patcher Development

After writing the first game, we faced a task that we hadn’t even thought about before. This is the development of the patcher for the game. For our patcher, we defined the following requirements:

• Game unit support
• User Friendliness
• Display game news
• Versatility for all games developed by our studio
• Customization flexibility
• And most importantly: the ability to make small patches for large files

Link to the source of the patcher at the end of the article.

As usual, before reinventing the wheel, I look for ready-made solutions to the problem. But either I didn’t google badly, or the only thing that met the requirement is M2H Patcher from the Unity Asset Store.
We spent several days on implementation, and used it for about a month (until the first and at the same time last breakdown). One day, the patcher refused to make a patch. After spending several hours on the proceedings, I found out the reason.
The fact is that this patcher used the bsdiff & bspatch utility . To use the bsdiff utility, you need max (17 * n, 9 * n + m) + O (1) memory. It so happened that the best machine in the office had only 4 GB of RAM, and the file with resources was already more than 600 MB. In general, bsdiff refused to work with it (until that time, the creation of the patch was indecent 30+ minutes).

Then I decided to still collect the bike.
')

Algorithm

Now it was necessary to google algorithm for comparing large binary files. There were two worthy candidates. These are rsync and the bsdiff suffix sorting algorithm.
Since there were already problems with the second one, I stopped at the first one.
Its essence is as follows. We split the source file into pieces of equal size (hereinafter referred to as chunks from English chunk).
For each chunk, we consider two hashes: strong and weak. A strong hash is the usual MD5. A weak hash is a ring hash . Its peculiarity is that if the hash from n to n + S-1 equals R, then the byte sequence from n + 1 to n + S can be calculated from R, byte n and byte n + S without having to take into account the bytes inside this interval.
Similarly, you need to calculate the resulting file. At the output, we should have two sequences of hashed chunks.
Next, we begin to compare weak hashes in files in search of identical chunks. If the hashes match, then compare the strong hashes. The key of the algorithm is to create two signatures - fast and stable. Fast is used as a filter. Resistant is used for more accurate checking.
At the exit, we have a list of different chunks, which we write to the patch.

Create patch

For our games, the system is well suited, where the version number is indicated by an integer. Thus, we usually have a bunch of folders with different versions of the current project: 1, 2, 3, etc.



The first thing to do after clicking the button is to determine which files have changed, deleted, added. To do this, compare the folder through

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

and keep a list of changes. If the file is added, then we consider md5. If it has changed, then we consider the new and old md5. These hashes will be needed in order to determine whether the patch can be applied and whether it has been correctly installed.
This data is collected to the archive with maximum compression through SharpZipLib . In the end, we add there the file patch_info.txt in which the data on the size of the chunk, the list of files with their hashes and actions are stored.
Example:

 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
Depending on the action there is either the file itself or a patch to the old version.
Now this patch can be put on any web hosting. I tested on the dropbox.

It is important to note that for the normal operation of the system in the game folder should be a file . \ Patcher \ version.txt . It stores information about the current version of the game. The patcher reads it and changes it as a result of the patch application process. The patch builder tries to make sure that you are not mistaken, and the version in the file matches the version specified in the folder name.

Patcher

At startup, the patcher reads the settings file along the path ./patcher/configuration.xml and checks for validity.
An example of a file with comments:

 <?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> 

First of all, the patcher will check its version from the ./patcher/version.txt file. Then he will check the latest version of the game using the link from the settings. If the latest version is greater then the update process starts according to the scheme:

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

To apply a patch, you first need to get a list of changed files. Therefore, the first thing we do is extract patch_info.txt from the downloaded archive, parse it and loop through the files.
If the file is to be deleted, then delete it. If added, then unpack from the archive. If changed, then apply the patch if the hashes match (so as not to spoil it).
In the end, do not forget to check the new md5 hash.

I tried to make sure that any exception in the patcher had a text description and solutions.
Also, the patcher is already localized into Russian and English by means of .NET.

Statistics

For verification, I immediately shoved a client of our game on Unity3D into it, which bsdiff refused to work with.
Client version 1 - 1669 Mb
Client version 2 - 1692 Mb (we added a model with a pack of textures)
Patch size with a chunk size of 1 Kb and maximum archive compression - 11.8 Mb , which is very similar to the results of the patcher with bsdiff
The time to create a patch on my machine is less than a minute, and it takes about 10 seconds to apply.

Source: https://github.com/Agasper/GamePatcher