13

I've got two partition images (A and B) and want to use them to create a patch that I can apply on A on another computer in order to get the new B image without flooding the network. I have the following requirements:

  • works on Linux
  • can create diffs
  • can use diffs to patch files
  • can handle binary files
  • can handle large files (a few hundred GB should work)
  • no user interaction required (just a console application)
  • ideally, should be able to read from/write to pipes (so that I can pipe into it from a gzip-compressed file and write to one)

Does something like that exist?

  • I hit the Enter key too fast when starting the bounty. Here is the text I wanted to add: – Basj Feb 3 at 20:57
  • An answer with an easy-to-reproduce example for rdiff would be valuable for future reference. Example: Let's say file1 and file2 are two similar files of 1GB each. 1) How to compute the rdiff? 2) How to save this rdiff into a patch file? 3) How to apply this patch file to file1 to recover file2? – Basj Feb 3 at 20:58
13

You should probably take a look at the rsync-related tools: rdiff and rdiff-backup. The rdiff command lets you produce a patch file and apply it to some other file.

The rdiff-backup command uses this approach to deal with entire directories, but I'm guessing you're working with single-file disk images, so rdiff will be the one to use.

| improve this answer | |
  • 1
    What does "signature" and "delta" mean for rdiff? The man page doesn't say. – Tor Klingberg Sep 12 '16 at 12:54
  • 1
    To answer my own question, creating a delta with rdiff is a two step process. First create a signature file from the old file, then use the signature and new file to create the delta. They can be run together with rdiff signature oldfile | rdiff delta - newfile deltafile – Tor Klingberg Sep 13 '16 at 9:10
  • 1
    @TorKlingberg Could you post a new answer with a example? Let's say file1 and file2 are two similar files of 1GB each. 1) How to compute the diff? 2) How to save this diff into a patch file? 3) How to apply this patch file to file1 to recover file2? – Basj Feb 3 at 20:55
7

xdelta can do everything you want. Fair warning though, if your images aren't very similar, you can end up with a very large patch, because xdelta uses half of the defined memory buffer for finding differences. More information is available at the TuningMemoryBudget wiki page. Increasing the buffer size may help out quite a bit.

bsdiff is another option, but it's very RAM hungry and completely inappropriate for anything the size of a disk image.

bsdiff is quite memory-hungry. It requires max(17*n,9*n+m)+O(1) bytes of memory, where n is the size of the old file and m is the size of the new file. bspatch requires n+m+O(1) bytes.

| improve this answer | |
3
+100

Canonical Answer

Regarding rdiff the post, librsync 2.0.1 is a good read for the command functionality clarification so I've referenced that below to preserve the content to this answer if nothing else.

It's important to try to get a good understanding of the rdiff three steps to updating a file: signature, delta, and patch as talked about on the rdiff man page. I've also found an rdiff command example script on GitHub that's helpful which I'll reference and quote.

Essentially...

  1. With a "starting" or base file [file1] and you create a signature file from it
    • This is usually much smaller than the base/original file itself
  2. With the signature file you compare it against another file [file2] similar to your base file but different (e.g. recently updated) and create a delta file containing just the differences between the two files
  3. Use the "differences only" or delta file and compare it with your base file [file1] to generate a new file containing the changes from the other file [file2] matching the two.

Quick Commands (per rdiff-example.sh)

rdiff signature file1 signature-file            ## signature base file1
rdiff delta signature-file file2 delta-file     ## delta differences file2
rdiff patch file1 delta-file gen-file           ## compare delta to file1 to create matching file2

rdiff-example.sh

# $ rdiff --help
# Usage: rdiff [OPTIONS] signature [BASIS [SIGNATURE]]
#              [OPTIONS] delta SIGNATURE [NEWFILE [DELTA]]
#              [OPTIONS] patch BASIS [DELTA [NEWFILE]]

# Options:
#   -v, --verbose             Trace internal processing
#   -V, --version             Show program version
#   -?, --help                Show this help message
#   -s, --statistics          Show performance statistics
# Delta-encoding options:
#   -b, --block-size=BYTES    Signature block size
#   -S, --sum-size=BYTES      Set signature strength
#       --paranoia            Verify all rolling checksums
# IO options:
#   -I, --input-size=BYTES    Input buffer size
#   -O, --output-size=BYTES   Output buffer size

# create signature for old file
rdiff signature old-file signature-file
# create delta using signature file and new file
rdiff delta signature-file new-file delta-file
# generate new file using old file and delta
rdiff patch old-file delta-file gen-file
# test
diff -s gen-file new-file
# Files gen-file and new-file are identical

Introduction

rdiff is a program to compute and apply network deltas. An rdiff delta is a delta between binary files, describing how a basis (or old) file can be automatically edited to produce a result (or new) file.

Unlike most diff programs, librsync does not require access to both of the files when the diff is computed. Computing a delta requires just a short "signature" of the old file and the complete contents of the new file. The signature contains checksums for blocks of the old file. Using these checksums, rdiff finds matching blocks in the new file, and then computes the delta.

rdiff deltas are usually less compact and also slower to produce than xdeltas or regular text diffs. If it is possible to have both the old and new files present when computing the delta, xdelta will generally produce a much smaller file. If the files being compared are plain text, then GNU diff is usually a better choice, as the diffs can be viewed by humans and applied as inexact matches.

rdiff comes into its own when it is not convenient to have both files present at the same time. One example of this is that the two files are on separate machines, and you want to transfer only the differences. Another example is when one of the files has been moved to archive or backup media, leaving only its signature.

Symbolically

signature(basis-file) -> sig-file

delta(sig-file, new-file) -> delta-file

patch(basis-file, delta-file) -> recreated-file

Use patterns

A typical application of the rsync algorithm is to transfer a file A2 from a machine A to a machine B which has a similar file A1. This can be done as follows:

  1. B generates the rdiff signature of A1. Call this S1. B sends the signature to A. (The signature is usually much smaller than the file it describes.)
  2. A computes the rdiff delta between S1 and A2. Call this delta D. A sends the delta to B.
  3. B applies the delta to recreate A2. In cases where A1 and A2 contain runs of identical bytes, rdiff should give a significant space saving.

source

| improve this answer | |
  • 1
    Thank you very much! – Basj Feb 7 at 21:22
1

JDIFF is a program that outputs the differences between two (binary) files.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.