5 ms·

I don't want to diminish your work, but today's improvement is not in using bsdiff (which they already did), but in using it file-by-file. That's where bsdiff c

• cperciva 10y ago
  Sure, but running file-by-file is how bsdiff was designed to operate. (I wrote it for FreeBSD Update, which operates on a file-by-file basis, because I was paranoid about the problem I'd seen on Windows systems where an update was registered as "installed" but the system had not in fact been properly updated.)
  • i336_ 10y ago
    Ah, that's where it got its name :) Really awesome utility.
    • KMag 10y ago
      I believe it stands for Byte Subtraction Diff, or something like that. As I remember, something like Bentley McIlroy diff is used to identify identical runs, and where there are short runs of bytes separating two runs that are identical between the two files, the bytewise subtraction of the short run is stored. The key observation is that when performing updates, large runs of machine code will be identical, with only relative offsets and absolute addresses changing. Code changes tend to shift huge pieces of binary code in parallel (by the same offset), so the bytewise subtraction expresses these shifts as many repeats of the same bytewise difference, which is then more easily compressed by zlib DEFLATE (or maybe another compressor... I forget the details).
      • js2 10y ago
        These programs were originally named bdiff and bpatch, but the large number of other programs using those names lead to confusion; I'm not sure if the "bs" in refers to "binary software" (because bsdiff produces exceptionally small patches for executable files) or "bytewise subtraction" (which is the key to how well it performs). Feel free to offer other suggestions.
  • rakoo 10y ago
    Ah, thanks for the information. I must admit I have never used it and never looked at what makes it different from other diff algorithms. Will definitely have a look at it !
• CJefferson 10y ago
  I find bsdiff works fine on concatenated files, because it searches for common sections over the whole file, rather than a traditional diff which just searches in order.
  • cperciva 10y ago
    It can work on concatenated files (if you avoid compression, which screws up everything) but it's usually more efficient to run bsdiff on individual matched pairs. The heuristic bsdiff uses for identifying "mostly-matching" regions is just that -- a heuristic -- and the larger the amount of data you have the higher the chance that bsdiff will try to build a mostly-matching region out of a coincidental sequence of matching bytes.
  • rakoo 10y ago
    If I'm not mistaken, an APK file is a zip archive, meaning that bsdiff was previously run on compressed stuff. As you can see in the article compressing content tends to make the output greatly differ (so much that gzip has a special option to make it more easily diffable, typically for rsync use). So bsdiff wasn't previously run on a concatenation of file; it was not used optimally.
  • user5994461 10y ago
    The archive tools (like 7z) have a special flag to allow for diff over the entire archive by external tools. The flag will modify the storage format, -kinda packing files/chunk together instead of just compressing into a huge block- so that tools can detect diff and same sections over the full archive. It's not well know but it is an absolute must known. e.g. for backup archive that goes over rsync, and change little over time.
    • adrianN 10y ago
      I looked in the 7z manual but couldn't find anything obviously related to this functionality. Would you mind giving a reference?
      • 10y ago
• amelius 10y ago
  It should in theory work similarly on a tar file, no? (tar without compression)