Saturday, September 13, 2008
Re: Xdelta-3.0u (source)
2008.10.12 update: Windows executable posted
Release Notes:
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.
2008.10.12 update: Windows executable posted
Release Notes:
- New xdelta3 merge command (issue 36)
- Windows stdin/stdout-related fixes (issue 34)
- Fix API-only infinite loop (issue 70)
- Various portability and build fixes (gcc4, DJGPP, MinGW, Big-endian, Solaris, C++)
- New regression test (yeah!)
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.
Comments:
Post a Comment
