Function fossil_delta::generate_delta

pub fn generate_delta(z_out_t: &str, z_src_t: &str, z_delta: &mut String)

Generate new delta in given mutable string reference

Output Format:

The delta begins with a base64 number followed by a newline. This number is the number of bytes in the TARGET file. Thus, given a delta file z, a program can compute the size of the output file simply by reading the first line and decoding the base-64 number found there. The delta_output_size() routine does exactly this.

After the initial size number, the delta consists of a series of literal text segments and commands to copy from the SOURCE file. A copy command looks like this:

NNN@MMM,

where NNN is the number of bytes to be copied and MMM is the offset into the source file of the first byte (both base-64). If NNN is 0 it means copy the rest of the input file. Literal text is like this:

NNN:TTTTT

where NNN is the number of bytes of text (base-64) and TTTTT is the text. The last term is of the form

NNN;

In this case, NNN is a 32-bit bigendian checksum of the output file that can be used to verify that the delta applied correctly. All numbers are in base-64.

Pure text files generate a pure text delta. Binary files generate a delta that may contain some binary data.

Algorithm:

The encoder first builds a hash table to help it find matching patterns in the source file. 16-byte chunks of the source file sampled at evenly spaced intervals are used to populate the hash table.

Next we begin scanning the target file using a sliding 16-byte window. The hash of the 16-byte window in the target is used to search for a matching section in the source file. When a match is found, a copy command is added to the delta. An effort is made to extend the matching section to regions that come before and after the 16-byte hash window. A copy command is only issued if the result would use less space that just quoting the text literally. Literal text is added to the delta for sections that do not match or which can not be encoded efficiently using copy commands.