XDelta compression paper

   1. History

     1a. RCS/SCSS storing files as a series of changes between versions.

   2. XDFS

     2a. Stores a linear serialized version of history, not an ancestry tree
         like RCS/SCSS do.

     2b. Forward deltas

       2b1. Store a literal version and changes which apply after one another.

     2c. Reverse deltas

       2c1. Store the latest version as a literal, where changes are kept as
            deltas from the latest version back to the old historical revision.

     2d. Archive

       2d1. Cluster

         2d1a. Single literal version of a file (the whole thing)

         2d1b. Connected set of deltas from the literal to a future version

   3. Types of deltas

     3a. Copy/Insert Deltas

       3a1. Allows copying from anywhere already inside the source file--with
            insertions where needed.

       3a2. Emits COPY instructions for data to pull from the old version to a new
            one, then INSERT instructions to add missing data.

       3a3. More suitable for binary data.

     3b. Insert/Delete Deltas

       3b1. Based on checking what lines to insert and what lines to delete in a
            file.

       3b2. Uses longest common subsequences and compute edit scripts from one
            version to another.

       3b3. More suitable for human review.

   4. Algorithms

     4a. Greedy

       4a1. Find longest available matches between files.

       4a2. Impractical when implemented naively; but has optimal compression.

     4b. Suffix-trees

       4b1. Optimal outputs, but prohibitive storage costs make it unsuitable
            for large files.

       4b2. Used by bsdiff.

     4c. Hashing

       4c1. Uses a Rabin rolling hash of some window; the hashes are stored in a
            table which is created by rolling the window over the entire target
            file.

       4c2. Source file can be scanned via windowing. When the rolling hash is
            found in a table you know that the window appears in both files and
            becomes somewhere you can now scan for similarities.

     4d. XDelta

       4d1. Designed to be fast while sacrificing optimal compression from
            earlier algorithms.

       4d2. Creates a hash table to map the hash of a window of data to a
            position it was seen in the buffer. The map stores a single value
            per bucket and collisions result in the older value being replaced.

       4d3. Fingerprints are scanned from the end of a source file to the front,
            so that the hash table ends up with the earliest instances of
            spotted windows, since the author believes the earliest matches will
            be the longest.

       4d4. Once the fingerprint table is made: input is partitioned in to
            "pages." Checks will not move across page boundaries--supposed to
            help stream processing.

       4d5. Once you find a candidate for a match: try to expand both ends as
            far as possible. Do not walk over a page boundary though. Insert the
            match as a COPY operation.

       4d6. If no match is found then produce INSERT operations.

   5. Tunables

     5a. Rolling fingerprint hash is adler32

     5b. "s," the size of a window, is 16 bytes

     5c. "b," the bucket count of the fingerprint hash table. Has some prime
         number size between floor(N/s) and 2*floor(N/s), where N is the number
         of bytes in the file to be scanned.