3 ms·

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

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?
  - user5994461 10y ago
    'gzip --rsyncable' for gzip. I couldn't find the equivalent for 7z in a quick glance. It supports at least 5 compression algorithms so there is probably not a general option. Maybe one has to play with the advanced settings per algorithm, if they support it.
    - JoshTriplett 10y ago
      gzip --rsyncable does make gzip set boundaries so one change doesn't affect the entire rest of the file, just one block. However, the resulting differences don't seem nearly as amenable to the bsdiff algorithm as the changes to the underlying uncompressed data. In almost all cases, you'll likely get better results with bsdiff on the uncompressed data (and bsdiff internally compresses its result).
      - user5994461 10y ago
        Don't know about how bsdiff operate, maybe it's naive. Good deduplication and diff algorithms have adaptive block size detection.

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?
- user5994461 10y ago
  'gzip --rsyncable' for gzip. I couldn't find the equivalent for 7z in a quick glance. It supports at least 5 compression algorithms so there is probably not a general option. Maybe one has to play with the advanced settings per algorithm, if they support it.
  - JoshTriplett 10y ago
    gzip --rsyncable does make gzip set boundaries so one change doesn't affect the entire rest of the file, just one block. However, the resulting differences don't seem nearly as amenable to the bsdiff algorithm as the changes to the underlying uncompressed data. In almost all cases, you'll likely get better results with bsdiff on the uncompressed data (and bsdiff internally compresses its result).
    - user5994461 10y ago
      Don't know about how bsdiff operate, maybe it's naive. Good deduplication and diff algorithms have adaptive block size detection.