4 ms·
XOR+RLE is almost useless for binaries, because almost any change will cause instructions to be added or deleted, offsetting the entire binary after the first c
by marcan_42 5y ago
XOR+RLE is almost useless for binaries, because almost any change will cause instructions to be added or deleted, offsetting the entire binary after the first change, making the xor fail to converge. On top of that, these changes cause changes in addresses in the first part of the binary, so you end up with a zillion similar-looking xor deltas in the first part of the file that won't compress well with RLE.
In fact, if you use smarter compression than RLE, I wouldn't be surprised if the update was larger than the original binaries after the xor, as an offset xor will likely increase chaos (entropy) in the file, making it compresss worse than the original.
bsdiff was specifically designed to intelligently handle these situations, which is why it works.
Just tested it on Chromium from my package server (90.0.4430.72 vs 90.0.4430.212):
- Original binary: 266MB
- Gzipped binary: 106MB
- Gzipped XOR "patch": 228MB
- bsdiff patch: 47MB
- derefr 5y agoPedantic point: it's not "almost useless for binaries." It's almost useless for compiled, PIC binaries in modern executable formats like PE or ELF that allow for lots of load-time address-space rearrangement. XOR-and-RLE works well for binaries from non-HLL languages (assembler, mostly) where — due mostly to early assemblers' lack of support for forward-referencing subroutine labels from the data section — subroutines tend to ossify into having defined address-space positions. You can observe this by the fact that IPS-patchfile representations (which, while a different algorithm, is basically equivalent to XOR-and-RLE in its results) of the deltas between different versions/releases of old game ROMs written in assembly, are actually rather small relative to the sizes of the ROM images themsleves. The v1.1 ROMs are almost always byte-for-byte identical in ROM-image layout to the v1.0 versions, except for where (presumably) explicit changes were made in the assembler source code. Translated releases are the same (sometimes, but not always, because they were actually done by the localization team bit-twiddling the original ROM, because they didn't have access to the original team's assembly code.) (This is also why archives that contain all the various versions/releases of a given game ROM, are highly compressible using generic compressors like LZMA.)
- marcan_42 5y agoYes, if we're talking about 8-bit era games, certainly things were different back then and things rarely moved around in memory between versions :-)