Saturday, September 13, 2008

Re: Xdelta-3.0u (source)

2008.10.12 update: Windows executable posted

Release Notes:The new merge command allows you to combine a sequence of deltas, to produce a single output that represents the net effect of the sequence. The command is reasonably efficient because it computes the result directly, without constructing any intermediate copies (and without access to the first-of-chain source). I say "reasonably" because there's a soft spot in this algorithm.

A VCDIFF encoding contains two kinds of copy instructions: (1) copies from the source file, which the merge command can translate with straight-forward arithmetic, and (2) copies from the target file (itself), which are more difficult. Because a target copy can copy from another target copy earlier in the window, merging from a target copy at the end of a window may involve following a long chain of target copies all the way to the beginning of the window. The merge command implements this today using recursion, which is not an efficient solution. A better solution involves computing a couple of auxiliary data structures so that: (1) finding the origin of a target copy is a constant-time operation, (2) finding where (if at all) the origin of a target copy is copied by a subsequent delta in the chain. The second of these structures requires, essentially, a function to compute the inverse mapping of a delta, which is a feature that has its own applications.

Summary: the merge command handles target copies inefficiently, and the code to solve this problem will let us reverse deltas. Together, the merge and reverse commands make a powerful combination, making it possible to store O(N) delta files and construct deltas for updating between O(N^2) pairs using efficient operations. This was the basis of xProxy: A transparent caching and delta transfer system for web objects, which used an older version of Xdelta.

I'm making a source-only release, which I haven't done in a while, because I don't have the necessary build tools for Windows (due to a broken machine) and I don't want to delay this release because of it.

Comments: Post a Comment

This page is powered by Blogger. Isn't yours?