console - How do patches in games work?

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.

Answer

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).