Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Console and PC games have patches sometimes to fix bugs which the developers missed/didn't have time to fix.

My question is how do these work?

Sometimes the patch files are a few megabytes in size. I don't understand how a small file can alter a complied program.

share|improve this question
    
You wish to alter a compiled games you made using a small patch? –  Zehelvion Oct 14 '12 at 18:53
    
No, I'm just interested in the theory behind it. My games are small enough to just recompile them and distribute the whole game again :) –  MulletDevil Oct 14 '12 at 18:58
3  
This an interesting question. It is not based on a problem you are facing with game design. There are also many ways to handle patched from the most naive way, replacing all the files that were modified to the most complex, getting instructions to change specific things in existing files. I am not sure this question is suitable to this site. –  Zehelvion Oct 14 '12 at 19:16
2  
A few megabytes isn't "small". Suppose we have a three megabyte file which is six megabytes of executable code, compressed. Suppose that instructions are six bytes long on average, so it's about a million instructions. (Let's ignore static data like string literals and whatnot.) If a line of C corresponds to about ten machine instructions, that's 100,000 lines of code. That seems like enough for the core engine of a game. Most of the installation size will be stuff like texture maps, screens, video sequences. –  user21862 Oct 15 '12 at 0:21
2  
a few megabytes may well be small, all depends on what's in it and what percentage of the total codebase that is. If say an entire 3D level map needs to be replaced because of the chosen file formats etc., including all the textures and what not, a few megabytes can be very small indeed. –  jwenting Oct 15 '12 at 5:24

4 Answers 4

up vote 27 down vote accepted

There are multiple ways to do this, the simplest would be to XOR the two files and compress them (GZIP or so forth). The theory behind this is that hopefully you can get a large sequence of zeroes (long sequences of the same values compress well).

You can take that concept further and try and find areas of the two files where the data is identical and omit it entirely.

Finally, you could use the structure of each type of file to your advantage. For example, in an EXE you could package each method individually (only ones that have changed) and reconstitute the EXE yourself during patch application; keep in mind, however, that this is very likely in the realm of overkill and may not be worth the effort (the gain over a simple bdiff might not justify the extra complexity that could break in the wild). As another example you could use diff files for scripts.

However, most patching systems in the wild take the simplest route: they just package files that have changed - they don't attempt to only package changes within those files (probably for good reason, most game content is compressed already and creating patches against high entropy or compressed data won't work at all).

share|improve this answer
    
What do you mean by package each method in an exe individually. Is that practical? –  Zehelvion Oct 14 '12 at 19:27
    
@ArthurWulfWhite yes. For an indie house probably not worth the time as it would take an extreme amount of time and effort (you essentially need to write your own linker) - as a company dealing with 'patching technology' exclusively it would be well worth the effort. It all depends on how large the executable code is - I took a quick look at Sacred 2 and it was 26mb (8mb for the main EXE). A binary diff might be able to get close to it though - still it's an idea worth putting out there (I know that CABs get good compression on EXEs because they take advantage of the structure). –  Jonathan Dickinson Oct 14 '12 at 19:30
    
That is very interesting. I suppose with bandwidth being what it is today, minimizing game patch size is not a major issue. +1 an interesting well thought out answer. –  Zehelvion Oct 14 '12 at 19:36
    
It is not that feasible to patch in individual methods in most games. The compiler can have rather drastically different output with even simple code changes. Automatic inlining decisions can change, symbol table layout can change, etc. Code changes also often change internal API structure. Optimizations already blur the line between function boundaries compared to what you see in your code editor. DRM systems also muddy the water greatly. Patch systems use wholesale replacement or binary diffs, and compress them. Anything like you suggest is simply too fragile to ship in the real world, imo. –  Sean Middleditch Oct 15 '12 at 1:04
2  
@SeanMiddleditch I am going to do it just to prove it's possible :). –  Jonathan Dickinson Oct 15 '12 at 16:39

The executable code of a game doesn't always reside just in the executable, often it is divided into several dynamic libraries (for example the game, graphics and sound engines), the actual executable, and possibly many scripts for various purposes.

A patch could be fixing issues in any single one of these parts without warranting change in all of them.

A different approach than replacing all changed files could be to simply do a binary diff on them, and only packackge the actual differences to be redistributed.

(That will of course only work on files you can guarantee won't be changed by the user.)

share|improve this answer
2  
You could mention this as an example: daemonology.net/bsdiff –  Zehelvion Oct 14 '12 at 19:26
1  
Good practical answer. +1 –  Zehelvion Oct 14 '12 at 19:37

Normally they use a third-party binary diff system to distribute patches to the game data. The executables are typically small enough to be trivially distributed entirely.

Most modern games have hundreds of megs of game data (mostly textures, models, levels data etc). These require patching quite often. As far as I know, the publishers normally have a standard proprietary way of doing this.

Needless to say, there are open-source examples. Some Linux distributions (Fedora?) use binary diffs for their patches. You can investigate those and read their source code or documentation.

share|improve this answer

Modern diff algorithms can efficiently find byte sequences that are common between two binaries. Not surprisingly, if you think about it. File compression relies on finding identical byte sequences too.

Once you have the list of identical byte sequences, you just need to send the old and new offsets, the length, and of course anything that's completely new. On the receiving side, it's then a straightforward assembly. Copy the bits you need to keep from the old file, fill in the new bits.

Creating the patch becomes even easier if your linker can spit out a MAP file which lists the offsets of every function in the file.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.