xdelta

Update for April 2008:

I started making beta releases for Xdelta-3.x four years ago. There were a lot of bugs then. Now the bug reports are dwindling, so much so that I've had a chance to work on new features, such as one requested by issue 36. Announcing the xdelta3 merge command. Syntax:

xdelta3 merge -m input0 [-m input1 [-m input2 ... ]] inputN output

This command allows you to combine a sequence of deltas, producing a single delta that combines the effect of applying two or more deltas into one. Since I haven't finished testing this feature, the code is only available in subversion. See here and enjoy.

Xdelta-3.0t release notes:

• Improves compression by avoiding inefficient small copies (e.g., copies of length 4 at a distance >= 2^14 are skipped)
• Fixes an uninitialized array element in -S djw which did not cause a crash, but caused less than ideal compression and test failures
• Fixes bugs in xdelta3 recode, tests added
• All tests pass under Valgrind

Xdelta-3.0s release notes:

• Faster! Several optimizations to avoid unnecessary arithmetic
• xdelta3 -1 has faster/poorer compression (xdelta3 -2 is the former configuration)
• -S djw exposes secondary compression levels as -S djw1 .. -S djw9
• Removes "source file too large for external decompression" error check
• API support for transcoding other formats into VCDIFF

Xdelta-3.0r release notes:

• Fixes an encoder crash caused by -S djw (secondary compressor) on certain data, new tests for code-length overflow
• Adds new recode command for re-encoding a delta with different secondary compression settings
• Fixes API-specific bugs related to non-blocking calls to xd3_encode_input and xd3_decode_input
• Adds new examples/encoder_decoder_test.c program for the non-blocking API

As an example of the new recode command and secondary compression options:

$ ./xdelta3 -S none -s xdelta3.h xdelta3.c OUT  # 53618 bytes
$ ./xdelta3 recode -S djw1 OUT OUT-djw1         # 51023 bytes
$ ./xdelta3 recode -S djw3 OUT OUT-djw3         # 47729 bytes
$ ./xdelta3 recode -S djw6 OUT OUT-djw6         # 45946 bytes
$ ./xdelta3 recode -S djw7 OUT OUT-djw7         # 45676 bytes
$ ./xdelta3 recode -S djw8 OUT OUT-djw8         # 45658 bytes
$ ./xdelta3 recode -S djw9 OUT OUT-djw9         # 45721 bytes

Secondary compression remains off by default. Passing -S djw is equivalent to -S djw6.

I'm happy about an e-mail from a manager at Pocket Soft, clarifying what was written in my previous post. Obviously, Pocket Soft deserves recognition here because, commercially speaking, they're the only basis for comparison sent by users. I am posting the entire content here.

Hi, Josh. I'm the Manager of Software Engineering at Pocket Soft, makers of RTPatch. I'd like to address a misquote contained in your June 28th post and hopefully clear the air and explain Pocket Soft's official position with respect to open source, patents and head-to-head comparison with XDelta. I'm happy for you to use all or part of my email within your site, if you feel it is appropriate.

First of all, the quote "xdelta likely infringes on our patents as well" is inaccurate (nobody from Pocket Soft made that specific remark to anyone at anytime); however, it does embody the essence of a statement made by one of our salesmen to a company in Australia that could have been *construed* to suggest a patent infringement claim. This was a one-time incident, and was not representative of Pocket Soft's corporate position. In fact, our CEO spoke to the CEO of the Australian outfit who received this message and explained that it was the result of an overzealous salesman. We have also addressed this issue internally with all staff.

In fact, Pocket Soft is a supporter of open source software, and understand that it serves a great purpose in our industry. Further, having spent the last 15+ years on the specific problems associated with byte-level differencing, we have a great appreciation for the work that you have done on XDelta. The purpose of patents for Pocket Soft's use are in fact defensive and to serve as a sales "check list" for our Enterprise customers. Consider the following [article].

In particular, the section of "Legal Risk" comes into play frequently with the OEM and even shrink-wrap sales we make to Enterprise. When you are selling to the Oracles of the world, we are almost always asked "what about indemnity?". The existence of a patent on the core technology helps to alleviate fears of legal risk - regardless of your, or even our own, opinions on software patents themselves.

Regarding head-to-head comparison, we are well aware of specific places where we could improve speed or patch file size in RTPatch to gain a few points here and there; however, the needs of our customers regarding reliability trump that. Your reader wrote that they had a 4.5 year old version of RTPatch. Some of our users cling to 12 year old versions fearing the possibility of destabilization with a new release. Our Enterprise customers like to hear that we can claim with absolute sincerity that the current patch file format, Build engine, etc., have been thoroughly tested and that the same algorithms are being used for the million+ patches applied every single day by users of RTPatch (McAfee and Trend Micro alone put out that many patches). When the US Navy began using RTPatch for their digitized nautical charts used by ships at sea, they cared less about gaining a few more points on size reduction or even speed of Build. They needed
reliability and robustness.

This is not to say that your product lacks these characteristics. I am speaking only to the issues that we are faced with daily by our customers and potential customers. We also have to deal with the extended feature-set of RTPatch, including support for Windows Installer, automatic patch delivery mechanisms, as well as a host of Windows-specific features and options (self-registering files, registry support, etc.). The core algorithm is, of course, important, but in our market, there is much more than just byte-level differencing at play.

Finally, on a personal note, I wanted to say that we're not a big, bad corporation out to squash or bully innovators of open source software. On the contrary, we appreciate the attention you draw to yourself, which in turns brings companies who are in our market, to the attention of RTPatch. I understand that you work at Google now, so I'm sure that you know that not *all* companies are evil. :)

I hope you took the time to read this far. I certainly appreciate the opportunity to clear the air. Feel free to call or email anytime, and I'd be happy to chat.

Best of luck to you,

Tony O-
Manager, Software Engineering
Pocket Soft, Inc.
713-460-5600

I've received a steady stream of e-mail regarding Xdelta ever since version 0.13 was released (Oct 12 1997) and this is one of the nicest ones ever. Thanks.

Re: Patents and the Oracles of the world

The threat model is: I will sell a software license excluding you from the (copyright-related) terms of the GPL, giving you unlimited use for a flat fee, but it's done without representations, warranties, liabilities, indemnities, etc. The argument is, your company could be sued over intellectual property rights if any of the following technologies and programs should fall to a claim (although they have never to my knowledge been in doubt): Zlib-1.x, Xdelta-1.x, and the draft-standard RFC 3284 (VCDIFF).

I will say this:

In the event [Company] discovers that Licensor is not the legal owner and title holder of any code sequence within Xdelta delivered under this Agreement, [Company] shall notify Licensor of such discovery in writing, including the specific software code sequence in question, and shall give Licensor One Hundred Eighty (180) days to replace same with a functionally equivalent code sequence that Licensor is the legal owner and title holder of, all prior to invoking any form of relief which may be permitted under this Agreement. (contact me for a sample license)

But, patents aren't the real issue to me, in this post or the last, it's about support and features. This really is more than "just byte-level differencing at play".

Re: Support

In the unlikely event that you find an Xdelta crash or incorrect result, I'm really interested in fixing it. I keep track of issues. I respond to e-mail, like this one about directory-diff support:

hi, i'm using your AMAZING(!) xdelta 1.1.3 and is fantastic...i use it for make the patches for my translations and stuff like these...i was wondering...is it possible to implement a feature that expand the process to all the subdirectories? using a for like this for %%i in (*.*) do xdelta delta "OLD\%%i" "NEW\%%i" "%%i.patch" it doesn't recreate the dir tree and it doesn't take the subdirectories...what do you think about that?

Here's a user-submitted perl script for recursive directory diff. (To which the sender replied, "I don't know barely nothing about perl," making two of us.) If you have your own engineers, if Xdelta passes your tests, you probably don't need support. If you're McAfee or the US Navy, you need support. Here's someone who needs support:

We are using xdelta3 to compress our backups down at my workplace and it is working excellently, however whichever machine it is run on is put out of commission for the duration due to the xdelta3 executable window popping up for each file. Would it be possible to build the xdelta3 program as a DLL, much like zlib is? I have absolutely no knowledge of C/C++ so I don't know if this is a huge ask or not :)

I'd rather work on my car project than self-registering files, thank you very much. =)

No new versions posted since March, so a few updates. One user sent a MSDOS .bat script for xdelta1/xdelta3 command-line compatibility, another sent a perl script for recursive directory diff, one user reports good performance for an in-kernel application (sample code), and some feature requests. Given the lack of bug reports, it's about time to take xdelta3 out of beta.

Several of you have requested a feature for supporting in-place updates, allowing you to apply deltas without making a copy of the file, which brings me to another bit of user feedback:

Firstly, I’d just like to let you know that we did a little benchmark at work and xdelta3 came out on top from several utilities in terms of both execution speed and final output size.

One of those utilities is a 4.5 year old version of RTPatch which we have a license for.

One of my work colleagues emailed Pocket Soft about this, and as well as the obvious “you’re using an old version” response, and “open source software has no support” arguments, they also said something along the lines of: “xdelta likely infringes on our patents as well”, implying that using it may be illegal.

Being a great supporter and user of open source in my spare time, I am totally against this sort of spreading of F.U.D., as well as the very idea that software is patentable.

I’m not sure if my work colleague emailed you as well, but I just thought I’d let you know. :)

And the funny part is, users were saying 5 years ago that Xdelta 1.x beats RTPatch. :)

I have to thank the IETF and previous work in open source (e.g., RFC 1950 – Zlib, RFC 3284 – VCDIFF) for making this possible. Zlib bills itself "A Massively Spiffy Yet Delicately Unobtrusive Compression Library (Also Free, Not to Mention Unencumbered by Patents)", and in fact Zlib inspired Xdelta's API from the start (it's "unobtrusive"). Let's not forget Zlib's other main advantage (it's "unencumbered"). As for the the previous request (in-place updates), interest is strong but patents could become an issue.

Multi-threaded encoding/decoding is another frequent request. The idea is that more CPUs can encode/decode faster by running in parallel over interleaved segments of the inputs. That's future work, and probably a lot of it, but I like the idea.

Xdelta 3.0q has 11,480 downloads. It's you the user that feeds open source, and thanks for the great feedback!

Xdelta 3.0q features a new MSI installer for Windows.

Thanks to many of you for your feedback on Windows installation (issues 16, 26, 27). Thanks especially to Nikola Dudar for explaining how to do it.

Release 3.0q fixes Windows-specific issues: (1) do not buffer stderr, (2) allow file-read sharing. Thanks for the feedback!

Thanks for the following build tools:

Windows Installer XML (WiX) toolset
Microsoft Visual C++ 2005 Redistributable Package (x86)
Microsoft Visual C++ 2005 Express Edition
Microsoft Platform SDK for Windows Server 2003 R2

Plot shows the performance of variable compression-level settings, x (time) and y (compressed size), tested on a specific pair of cached 130MB inputs.

Compression has an inverse relation between time and space performance. The green line is a hyperbola for reference, f(x) = 1.33MB + (30KB*s) / (x - 2.45s). Sample points:

1.49MB in 2.9sec at ~45MB/sec (98.9% compression)
1.34MB in 6.5sec at ~20MB/sec (99.0% compression)

Re: Xdelta 3.0p (download)

Xdelta-3.x processes a window of input at a time, using a fixed memory budget. This release raises some of the default maximums, for better large-file compression. The default memory settings for large files add up to about 100Mb. (*)

A user wrote to confirm good performance on 3.7Gb WIM files, great!

So, to answer the question in your post on Jan 28th, yes we are using xdelta3 with files larger than 1Gb and it's working well.

I'm off to try boosting the compression and see how much we can scrunch the patch down. Thank-you for an extremely useful tool that is going to hugely improve our ability to distribute updates to our build images.

At the other extreme, a developer wrote to ask about using xdelta3 in the Xen kernel. Here's an example of xdelta3 configured for a 4Kb page using 32Kb.

A user writes about code size:

I saw your post where you said you’d improved the compression in Xdelta3 and that it was now slightly faster than 1.1. Do you happen to know where the two stand without compression enabled? (We don’t use Xdelta’s compression because we compress all of our files after the fact with Rar solid compression.) Thanks too for the link to those benchmarks. Those were quite helpful, and it’s cool to see Xdelta come out on top. ;)

I will say this: One nice thing about the new Xdelta is its smaller size! Xdelta 1.1’s exe is 1Mb when not compressed via UPX, whereas Xdelta3 is 100Kb. Nice. :)

Thanks! Xdelta3 is faster and better than Xdelta1 with compression disabled (the -0 flag), thanks to VCDIFF and other improvements.

I'm looking for your ideas on recursive directory diff. One solution uses tar:

XDELTA="-s source" tar --use-compress-program=xdelta3 -cf ...

This approach is better than computing pairwise differences, since data can be copied across files/directories. Pay attention to file order and source buffer size. Microsoft developers, consider using the WIM disk image format.

Thanks for the feedback (file a new issue).

(*) Xdelta-1.x processes the whole input at once, and its data structure takes linear space, (source file size/2)+O(1). Xdelta-1.x reads the the entire source file fully two times (to generate checksums, to match the input), using at least half as much memory as the source file size.

Users want speed, especially video gamers. I tested with some of your data: Unreal tournament and Wesnoth patches. These patches save 50-100MB per download.

Xdelta1 remains popular today because of speed, and xdelta3 until now hasn't been as fast (debdev has tests). Xdelta-3.0o has improved compression levels (download).

Over my sample data, the new default compression level (same as the command-line flag -1) is a little faster than, with compression roughly the same as Xdelta-1.x. Compression levels -3, -6, and -9 are also improved.

This release also features Swig support, e.g.,

import xdelta3

# memory interface
source = 'source source input0 source source'
target = 'source source target source source'

result1, patch = xdelta3.xd3_encode_memory(target, source, len(target))
result2, target1 = xdelta3.xd3_decode_memory(patch, source, len(target))

assert result1 == 0
assert result2 == 0
assert target1 == target
assert len(patch) < len(target)

# command-line interface

source_file = ...
target_file = ...
command_args = ['xdelta3', '-f', '-s', source_file, target_file, output_file]

xdelta3.xd3_main_cmdline(command_args)

Re: SVN teaser

SVN 125 has a new XDELTA environment variable for passing flags off the command-line, so you can use xdelta3 in conjunction with tar:

export XDELTA
XDELTA="-s source-1.tar"
TAR="tar --use-compress-program=xdelta3"
$TAR -cvf source-1-source2.tar.vcdiff source-2/
...
$TAR -xvf source-1-source2.tar.vcdiff source-2/file

This creates/extracts-from a delta-compressed tar file, without using intermediate files.

Re: Performance

From The Old Joel on Software Forum:

I checked out rtpatch and xdelta a little while ago - unless there's something wrong with the demo version rtpatch has on their website, xdelta is significantly faster at making patches, and they are a tiny bit smaller.

The test I ran was on a 200 Meg application, where about 30 megs of random parts of files was different. Rtpatch took around an hour (not sure since I wandered off while waiting) and xdelta took a couple minutes.

We ended up rolling our own system anyhow, because our application has pretty serious requirements on robustness. Maybe we should try selling it?

Thanks! 5 years later.

Another post in the same thread writes:

I did some research on 'patching' like issues, read some papers on the "Longest Common Subsequence" problem, wrote some prototype code... And we ultimately decided to defer the issue in our product. Note that we weren't trying to patch our software, we were interested in including tools in our product that would allow administrators to build patches for applications they support in house.

Long story short...it's a heavily researched issue in Computer Science, but it's still a difficult problem to solve well. There are both space and time considerations, although running on a 'modern' OS with virtual memory eases the space consideration. After my evaluation, my guess was that RTPatch was in no way producing an optimal solution, but that they were relying on compression to keep the size of the patch small. Their genius lies in being able to generate a patch so quickly...

Longest common subsequence isn't quite the same problem, but it's true that compression performance should be measured in several dimensions: size (of compression), memory usage, and speed. Xdelta3 supports compression levels -1 (fast) through -9 (best).

Virtual memory does not ease the space consideration. Reading from disk is terribly slow, so Xdelta3 avoids seeking backwards in the source file during compression. Read more about xdelta3 memory settings.

Re: SVN 100

If you're keeping up-to-date by subversion, with the xdelta source code, version 100 has a few recent changes: (1) compiles on cygwin (1.x and 3.x), (2) responding to bug report 17.

Re: Xdelta 1.1.4

An especially grateful user wrote me to say thanks for the open-source software:

Firstly, Xdelta is an impressive piece of software, and I appreciate you writing it. I've done some tests and found it to be orders of magnitude faster than RTPatch, the expensive commercial diffing tool!

I'm using a Windows ported version of Xdelta 1.1.3 in a project I'm working on here, and it works great. (I realize that XDelta 1.1.3 is old, but I like how fast it is relative to the results). Because that version is licensed under the GPL, I am including a copy of XDelta.exe with the program instead of integrating the code directly. I'm content to continue doing this, as obviously I want to respect your licensing wishes for the software. (*)

Thanks! Another writes:

I hope you can release a bugfix and rub off the beautymarks. xdelta-1.1.x is still used widely and a maintenance release would be appreciated.

Thanks again! =)

This is a maintenence release: Xdelta 1.1.4 remains substantially unchanged since 1999. This release fixes a bug: Compressed data from 32-bit platforms failed to decompress on 64-bit platforms. This is fixed in the decoder (it was a badly-designed "hint", now ignored), so you can now read old 32-bit patches on 64-bit platforms. Patches produced by 1.1.4 are still readable by 1.1.3 on the same platform. Still, Xdelta 1.1.x is losing its edge.

Xdelta3 compresses faster and better, using a standardized data format—VCDIFF, and has no dependence on gzip or bzip2. If using a standardized encoding is not particularly important for you, Xdelta3 supports secondary compression options. Xdelta3 (with the -9 -S djw flags) is comparible in terms of compression, but much faster than bsdiff. Xdelta3 includes a Windows .exe in the official release.

As always, I'm interested in your feedback (file a new issue). Are you compressing gigabyte files with Xdelta3? Have you used dfc-gorilla (by the makers of RTPatch)?

Xdelta3 has a stream-oriented C/C++ interface. The application program can compress and decompress data streams using methods named xd3_encode_input() and xd3_decode_input(). With a non-blocking API, it's about as easy as programming Zlib.

Read about it here.

Thanks for your feedback (file a new issue).

Release 3.0l (download)

This release raises the instruction buffer size and documents the related performance issue. Problems related to setting -W (input window size) especially small or especially large were fixed: the new minimum is 16KB, the new maximum is 16MB. A regression in the unit test was fixed: the compression-level changes in 3.0k had broken several hard-coded test values.

The encoder has compression-level settings to optimize variously for time and space, such as the width of the checksum function, the number of duplicates to check, and what length is considered good enough. There are 10 parameters (Zlib, by comparision, has 4), but the flag which sets them (-C) is undocumented. I am documenting these and developing experiments to find better defaults.

There's a new page about external compression.

Thanks for your feedback (file a new issue).

Release 3.0k (download)

This is the first release making only performance improvements, not bug fixes. The default source buffer size has increased from 8 to 64 megabytes, and I've written some notes on tuning memory performance for large files. I've been running experiments to find better compression-level defaults. This release has two default compression levels, fast (-1 through -5) and the default slow (-6 through -9), both of which are faster and better than the previous settings. There's more work to do on tuning in both regards, memory and compression level, but this is a starting point.

There is a new wiki on command line syntax. Thanks for your feedback (file a new issue).

Release 3.0j (download)

The self-test (run by xdelta3 test) now passes. There had been a regression related to external-compression, and several tests had to be disabled on Windows. Also fixes VCDIFF info commands on Windows (e.g., xdelta3 printdelta input) and memory errors in the Python module.

Thanks for your continued feedback (file a new issue). A user reports that xdelta3.exe should not depend on the C++ 8.0 Runtime. I agree—this is written in C. The source release includes a .vcproj file, in case you'd like to try for yourself.

Thanks for your feedback. (Submit a new report).

Release 3.0i builds with native Windows I/O routines (enabled by /DXD3_WIN32=1) and has been tested on 64 bit files. (Issue closed).

Windows: download
Source: download

#include <windows.h>

Ladies and Gents,
Version 3.0h runs on Windows.
Please head straight for the latest download of your choice:

Source
Windows x86-32
OSX PPC

I thought I'd share this first and test it later, let you be the judge.

There are not a lot of platform dependencies. The main() routine has helpful options:

• /DXD3_STDIO=1 builds with portable I/O routines
  
• /DEXTERNAL_COMPRESSION=0 builds without external compression, which requires POSIX system calls

A call to gettimeofday() had to be replaced:

static long
get_millisecs_now (void)
{
#ifndef WIN32
  struct timeval tv;
  gettimeofday (& tv, NULL);
  return (tv.tv_sec) * 1000L + (tv.tv_usec) / 1000;
#else
  SYSTEMTIME st;
  FILETIME ft;
  __int64 *pi = (__int64*)&ft;
  GetLocalTime(&st);
  SystemTimeToFileTime(&st, &ft);
  return (long)((*pi) / 10000);
#endif
}

The remaining changes were minimal, such as the printf format string for 64bit file offsets. I haven't run a 64bit test on Windows—I was too busy posting this. :-)

Please file issues here or send mail to <josh.macdonald@gmail.com>.

(Thanks to TortoiseSVN for keeping us in sync.)

To: Microsoft
Re: Windows support

Dear sirs,

Thanks for the free downloads!

Microsoft Visual C++ 2005 Express Edition
Microsoft Platform SDK for Windows Server 2003 R2

KDE.org asked how to use xdelta3. Like gzip with the additional -s SOURCE. Like gzip, -d means to decompress, and the default is to compress. For output, -c and -f flags behave likewise. Unlike gzip, xdelta3 defaults to stdout (instead of having an automatic extension). Without -s SOURCE, xdelta3 behaves like gzip for stdin/stdout purposes. See also.

Compress examples:

xdelta3 -s SOURCE TARGET > OUT
xdelta3 -s SOURCE TARGET OUT
xdelta3 -s SOURCE < TARGET > OUT

Decompress examples:

xdelta3 -d -s SOURCE OUT > TARGET
xdelta3 -d -s SOURCE OUT TARGET
xdelta3 -d -s SOURCE < OUT > TARGET

The latest release 3.0g works—finally!—with 64-bit files. xdelta30g.tar.gz (subversion 11)

Xdelta3 has support for secondary compression, part of VCDIFF (RFC 3284) that allows external compression algorithms for the three parts of a VCDIFF window (instruction, address, data). VCDIFF is entirely based on byte codes, not variable-length codes.

Most compression programs are based on Huffman coding, and there's the well-known Burrows–Wheeler transform implemented by bzip2. But there's more to it. I asked Julian Seward and he pointed me at two very interesting articles by D. J. Wheeler.

The decription, and the code. Fascinating.

The algorithm works with multiple Huffman-code tables and several iterations. The input is divided into fixed-length chunks, each chunk assigned to a Huffman table. Each iteration, chunks are assigned to the table which gives the shortest encoding, then the tables are recomputed according to the chunks they were assigned.

The chunk encodings plus the chunk–table assignments are then transformed by move-to-front. Move-to-front works very well (especially following Burrows–Wheeler), but it presents another problem for later Huffman coding, because after move-to-front coding there tend to be many 0s, and a symbol having frequency greater than 50% will not be efficiently encoded by Huffman coding—even the shortest 1-bit code has redundency. To address this problem, the 0 symbol is replaced by two symbols (call them 0_0 and 0_1). These two symbols are used to code the run-length of 0s in binary.

What really fascinates me is how Wheeler does this in 780 lines of code—including the Burrows–Wheeler transform. Amazing.

Xdelta3 has a secondary compressor based on DJW enabled by -S djw (2000 lines w/ no Burrows–Wheeler transform). For comparison (*), there's another secondary compression (enabled by -S fgk), based on D. E. Knuth's Dynamic Huffman coding. A dynamic huffman code updates code-table frequencies after each symbol is encoded or decoded. The routines are efficient (it's Knuth, after all), but still slower than DJW.

Since there are no standards written for secondary compression, secondary compression is turned off by default, but I recommend giving -S djw a try. Sample results:

source	7,064,064
target	7,031,808
xdelta -e -1	613,032
xdelta -e -9	610,560
xdelta -e -1 -S djw	461,298
xdelta -e -9 -S djw	458,859
xdelta -e -1 -S fgk	476,742
xdelta -e -9 -S fgk	474,244

(*) only because I once implemented FGK in school

Thanks to Google code hosting, there's a new Subversion repository for xdelta3 for us to keep in sync. Recently replaced some code, still having trouble crossing the 32bit/64bit boundary. Stay tuned...

Thanks for your continuing reports. Release 3.0f fixes a bug in xd3_iopt_flush_instructions:

   /* If forcing, pick instructions until the list is empty, otherwise this empties 50% of
    * the queue. */
   for (flushed = 0; ! xd3_rlist_empty (& stream->iopt.used); )
     {
-      if ((ret = xd3_iopt_add_encoding (stream,
-                    xd3_rlist_pop_front (& stream->iopt.used)))) { return ret; }
-      // TODO: what about this fraction??
-      if (! force && ++flushed > stream->iopt_size / 2) { break; }
+      xd3_rinst *renc = xd3_rlist_pop_front (& stream->iopt.used);
+      if ((ret = xd3_iopt_add_encoding (stream, renc)))
+       {
+         return ret;
+       }
+
+      if (! force) 
+       {
+         if (++flushed > stream->iopt_size / 2)
+           {
+             break;
+           }
+
+         /* If there are only two instructions remaining, break, because they were
+          * not optimized.  This means there were more than 50% eliminated by the
+          * loop above. */
+         r1 = xd3_rlist_front (& stream->iopt.used);
+         if (xd3_rlist_end(& stream->iopt.used, r1) ||
+             xd3_rlist_end(& stream->iopt.used, r2 = xd3_rlist_next (r1)) ||
+             xd3_rlist_end(& stream->iopt.used, r3 = xd3_rlist_next (r2)))
+           {
+             break;
+           }
+       }
     }

And we're back... The site was down for most of this month. It's a terribly uninteresting story. I've been on vacation, but before leaving I put together a new release, 3.0e, which fixes major bugs. Approaching a stable release? Possibly.

I'd like to thank the users for sending detailed reports, especially test cases.

Latest release: xdelta30d.tar.gz fixes a bug sent in by at least three users. Thanks for great reporting. The bug was an assertion failure during encode, so it's one you would have noticed, had it happened to you.

Several of you have sent patches for building on Windows, which I appreciate. This version should at least be easier to build (e.g., rename a field from near to near_array, add "b" to the fopen() mode, eliminate unnecessary sys/ includes, ...).

The author of kdiff3 mailed, asking for help visualizing binary diffs. We'll get that working, but in the meanwhile there is a way to print the contents of a VCDIFF input, xdelta3 printdelta INPUT. It prints the VCDIFF header, followed by the instruction list. For example:

  Offset Code Type1 Size1 @Addr1 + Type2 Size2 @Addr2
  000000 019  CPY_0 59357 @0     
  059357 013  ADD    12        
  059369 037  CPY_1   5 @120794
  059374 019  CPY_0 2066 @59370 

A number of people have written me recently regarding xdelta3 on windows. Fact is, I would love it. One writes:

> Hello,
>
> I have compiled xdelta with cygwin. I have noticed several versions of
> executables produced, but my question is quite simple.
> I want to make diff-like delta from one file to another in the way I could
> in xdelta 1.x, the syntax was
>
>     xdelta delta original_file new_file delta_file
>
> and to create new file from delta
>
>     xdelta patch delta_file original_file new_file
>
> What combination of arguments and what commands shall I issue with xdelta3
> to gain the same effect?

The syntax is similar to gzip, with the addition of a "-s original_file" argument. By themselves,

xdelta3 -df
xdelta3 -f

operate the similarly to gzip, even without the -s flag.

> I can't figured out what is wrong with the module.  But I solve the
> problem calling the C binary from os.system('/usr/bin/xdelta3...').
> 
> I whish to tell you that I'm very impressed by xdelta3 and would like
> to see finished and polished.  I just hope you have some time to
> deliver an xdelta3 release.
> 
> Again, thank you for xdelta3!

You're welcome. Thanks for writing in. I have a big pile of mail still to go through, and I have at least one xdelta3 bug report. Stay tuned...

Think what you will of sourceforge.net, but thanks for all the downloads.

I made the last xdelta3 release on Linux T20 Thinkpad. Today, a Mac G5. After an hour fiddling with minor things (size_t changes, test buffer sizes). The OS X debug binary passes its unittest. The optimized version, not so. Hmmm. Release xdelta30c.tar.gz. (Needs tuning!)

I admit, the teasers were mean. Here's what you need to know: the first public xdelta3 release. Phew, glad that's out of the way. Here's some more information. Here's an obligatory link to zlib, the inspiration behind the new API.

I was in Bruxelles 6 years ago today, following a conference talk here. I remember there were lots of bunnys hopping around the university. Happy Independence Day, Belgium.

A word on licensing. After much deliberation over the merits of this license and that license, I have chosen to apply the GNU Public License version 2 to my code.

Re: Licensing

You're still reading, I see. I am not a lawyer, nor are you. As of this point in time, I wrote every single line of xdelta3 code, except a few snippets of graciously copied from the public domain, as noted in the code, such as adler32(). Read my acknowledgements. If the terms of the GPL are not to your liking, please contact me.

Re: Does it work?

Yes, and there are tests to prove it. However, I decided to release the code as-is and see what comes of it. I imagine there are correctness bugs remaining, but it's more likely you'll find a performance bug. There are a lot of knobs in the string-matching implementation, which is relatively untuned.

If you find a bug, I'll fix it. If you're working for an open-source project and you want help, let me know!

Teaser1.
Teaser2.
The regression test has more bugs than it turns up, all I really need is a license. Hmm. Happy Memorial Day.

Xdelta release 3 is moving so, so slowly but these days I am working a bit. My old Linux machine died and it took a while to repair my data and re-install. I could not compile PRCS with g++-3.2, so I spent the afternoon fixing it (prcs-1.3.3).

Getting back to Xdelta, I built Python-2.3 because SuSe-8.1's Python-2.2 installation could not compile modules. Prior to losing that hard drive, nine months ago, I had been working on a regression test. Sadly, there's not much more weekend.

Happy Mothers Day. Happy Victory Day, Russia.

I promise, I'll post something here soon about past, present, and future releases of xdelta. I have a bunch of brand-new code to implement RFC 3284 sitting on my hard-drive. When will I have time to finish it? Until then, I have a personal blog. BTW: I work at Google, they keep me busy.