6 ms·

There are other solutions to this problem that the game industry uses. Binary diff patching is slow, incremental, involves large diffs and has the possibility o

There are other solutions to this problem that the game industry uses. Binary diff patching is slow, incremental, involves large diffs and has the possibility of corruption. It was used back in the mid 90's (RTPatch was the big name), but really isn't used anymore because of the drawbacks. Games frequently use an override directory or file. The patch contains only the files that have changed and is loaded after the main index and replaces the entries in the index with the updated ones. This is the most common way of doing a patch if it's not just overwriting the original files. Some games load their file as a virtual filesystem and then the patch just replaces the entries in the virtual store with new ones. Guild Wars 2 works this way. This is only common in MMOs though.

spinax 5y ago
Circa 1995: we (company) used RTPatch as the users at the time were floppy based via Post, but enjoyed BBSes (and Prodigy, etc.) as it was a social community due to the nature of the software/industry. We could upload small RTPatch based updates and bugfixes to our tiny company BBS, users could dial in and download a rtpatch a lot faster than a floppy in the mail (besides avoiding the usual corrupt floppies that plagued the tech).
erosenbe0 5y ago
Yes, overrides. I've heard talks on this at conferences with a couple big publishers. A lot of effort is put into it but obviously if we were distributing OS security updates like Apple it would be a whole different ballgame.
codefreakxff 5y ago
Fun fact. This is not a new concept. Doom used overrides with their WAD file format. Mod authors could release their mod files replacing or adding content without stealing the game level files. There may be prior art to that, but as a young coder that was the first time I’d seen it
derefr 5y ago
Different things. Games are directories/packfiles containing many individual files, mostly binary art assets, plus one executable that takes up a negligible proportion of the total size. When binary art assets in the directory/packfile are updated between versions, they don't really "change" in the sense that a source-code file might be changed a git commit; instead, they get replaced. (I.e. every file change is essentially a 100% change.) The "binary diff patching" you're talking about the game industry using, was just the result of xor-ing the old and new packfiles, and then RLE-encoding the result (so areas that were "the same" were then represented by an RLE symbol saying "run of zeros, length N"). For the particular choices being made, this is indeed much less bandwidth-efficient than just sending a new packfile containing the new assets, and then overlay-mounting the new packfile over the old packfile. bsdiff isn't for directories full of files that get 100% rewritten on update. (There's already a pretty good solution to that — tar's differential archives, esp. as automated by a program like http://tardiff.sourceforge.net/tardiff-help.html http://tardiff.sourceforge.net/tardiff-help.html .) Instead, bsdiff is for updates to executable binaries themselves (think Chrome updates), or to disk images containing mostly executable binaries + library code (think OS sealed-base-image updates — like CoreOS; or, as mentioned above, macOS as of Catalina + APFS.) In these cases, almost all the files that change, change partially rather than fully. Often with very small changes. The patches can be much smaller, if they're done on the level of e.g. individual compiled function that have changed within a library, rather than on the level of the entire library. (Also, more modern algorithms than xor+RLE can be used — and bsdiff does — but even xor + RLE would be a win here, given the shape of the data.) There's also Google's Courgette (https://www.chromium.org/developers/design-documents/software-updates-courgette https://www.chromium.org/developers/design-documents/softwar...), which goes further in optimizing for this specific problem domain (diffing executable binaries), by having the diff tool understand the structure/format of executables well-enough to be able to create efficient patches for when functions are inserted, deleted, moved around, or updated such that their emitted code changes size — in other words, at times when the object code gets rearranged and jumps/pointers must be updated. The goal of tools like bsdiff or Courgette isn't to reduce an update from 1GB to 200MB for ~10k customers. The goal is to reduce an update from 10MB to 50KB for 100 million customers. At those scales, you really don't want to be sending even a 10MB file if you can at-all help it. The server time required to crunch of the patch is more than paid off by your peering-bandwidth savings.
Riverheart 5y ago
That's how Tales of Maj'Eyal (ToME) supports modding
smoldesu 5y ago
To my knowledge, most developers have gone back to binary patching for obfuscation purposes. Bethesda does this now (and ID, by extension), as well as many other developers I've seen.
- derefr 5y ago
  For at least the Nintendo Switch (not sure other modern conosles), the digital distribution infrastructure is built in terms of overlay packfiles. Games, updates, and DLC on disk are all single-file archives / filesystem images. The OS, when launching a game, mounts the game + its updates + its DLCs together as a transparent overlay filesystem. The game just sees a unified representation of its newest version, with whatever DLC has been installed, sitting under (IIIRC) /title. I wouldn't be surprised if the other consoles also do things this way. It's a very sensible way to manage updates — especially when a game is running off of physical media but the updates are held in local storage. It also means there's no point where the update gets "merged in" to the base image, which means updates can be an atomic thing — either you have the whole update file downloaded + sig-checked (and thus it gets added to the overlay-list at boot) or you don't. And, if all the consoles are doing it, I wouldn't be surprised if studios that do a lot of work on console don't just use that update strategy even on PC, for uniformity of QA, rather than for "obfuscation."
formerly_proven 5y ago
Games also use this because it's a straightforward way to almost guarantee a physical ordering of the files in the VFS, which is/was a common optimization strategy in the days of CDs and hard drives (profile what order the game needs files, then put them in the archive in exactly that order = tada, loading 4000 files behaves like a sequential read). Another reason is that certain operating systems originating in the state of Washington have performance problems when you access small files or directories containing many files.

spinax 5y ago

Circa 1995: we (company) used RTPatch as the users at the time were floppy based via Post, but enjoyed BBSes (and Prodigy, etc.) as it was a social community due to the nature of the software/industry. We could upload small RTPatch based updates and bugfixes to our tiny company BBS, users could dial in and download a rtpatch a lot faster than a floppy in the mail (besides avoiding the usual corrupt floppies that plagued the tech).

erosenbe0 5y ago

Yes, overrides. I've heard talks on this at conferences with a couple big publishers. A lot of effort is put into it but obviously if we were distributing OS security updates like Apple it would be a whole different ballgame.

codefreakxff 5y ago

Fun fact. This is not a new concept. Doom used overrides with their WAD file format. Mod authors could release their mod files replacing or adding content without stealing the game level files. There may be prior art to that, but as a young coder that was the first time I’d seen it

derefr 5y ago

Different things. Games are directories/packfiles containing many individual files, mostly binary art assets, plus one executable that takes up a negligible proportion of the total size. When binary art assets in the directory/packfile are updated between versions, they don't really "change" in the sense that a source-code file might be changed a git commit; instead, they get replaced. (I.e. every file change is essentially a 100% change.) The "binary diff patching" you're talking about the game industry using, was just the result of xor-ing the old and new packfiles, and then RLE-encoding the result (so areas that were "the same" were then represented by an RLE symbol saying "run of zeros, length N"). For the particular choices being made, this is indeed much less bandwidth-efficient than just sending a new packfile containing the new assets, and then overlay-mounting the new packfile over the old packfile. bsdiff isn't for directories full of files that get 100% rewritten on update. (There's already a pretty good solution to that — tar's differential archives, esp. as automated by a program like http://tardiff.sourceforge.net/tardiff-help.html http://tardiff.sourceforge.net/tardiff-help.html .) Instead, bsdiff is for updates to executable binaries themselves (think Chrome updates), or to disk images containing mostly executable binaries + library code (think OS sealed-base-image updates — like CoreOS; or, as mentioned above, macOS as of Catalina + APFS.) In these cases, almost all the files that change, change partially rather than fully. Often with very small changes. The patches can be much smaller, if they're done on the level of e.g. individual compiled function that have changed within a library, rather than on the level of the entire library. (Also, more modern algorithms than xor+RLE can be used — and bsdiff does — but even xor + RLE would be a win here, given the shape of the data.) There's also Google's Courgette (https://www.chromium.org/developers/design-documents/software-updates-courgette https://www.chromium.org/developers/design-documents/softwar...), which goes further in optimizing for this specific problem domain (diffing executable binaries), by having the diff tool understand the structure/format of executables well-enough to be able to create efficient patches for when functions are inserted, deleted, moved around, or updated such that their emitted code changes size — in other words, at times when the object code gets rearranged and jumps/pointers must be updated. The goal of tools like bsdiff or Courgette isn't to reduce an update from 1GB to 200MB for ~10k customers. The goal is to reduce an update from 10MB to 50KB for 100 million customers. At those scales, you really don't want to be sending even a 10MB file if you can at-all help it. The server time required to crunch of the patch is more than paid off by your peering-bandwidth savings.

Riverheart 5y ago

That's how Tales of Maj'Eyal (ToME) supports modding

smoldesu 5y ago

To my knowledge, most developers have gone back to binary patching for obfuscation purposes. Bethesda does this now (and ID, by extension), as well as many other developers I've seen.

derefr 5y ago
For at least the Nintendo Switch (not sure other modern conosles), the digital distribution infrastructure is built in terms of overlay packfiles. Games, updates, and DLC on disk are all single-file archives / filesystem images. The OS, when launching a game, mounts the game + its updates + its DLCs together as a transparent overlay filesystem. The game just sees a unified representation of its newest version, with whatever DLC has been installed, sitting under (IIIRC) /title. I wouldn't be surprised if the other consoles also do things this way. It's a very sensible way to manage updates — especially when a game is running off of physical media but the updates are held in local storage. It also means there's no point where the update gets "merged in" to the base image, which means updates can be an atomic thing — either you have the whole update file downloaded + sig-checked (and thus it gets added to the overlay-list at boot) or you don't. And, if all the consoles are doing it, I wouldn't be surprised if studios that do a lot of work on console don't just use that update strategy even on PC, for uniformity of QA, rather than for "obfuscation."

formerly_proven 5y ago

Games also use this because it's a straightforward way to almost guarantee a physical ordering of the files in the VFS, which is/was a common optimization strategy in the days of CDs and hard drives (profile what order the game needs files, then put them in the archive in exactly that order = tada, loading 4000 files behaves like a sequential read). Another reason is that certain operating systems originating in the state of Washington have performance problems when you access small files or directories containing many files.