import 1.1.3

1 files changed, 311 insertions, 0 deletions

diff --git a/xdelta1/xdelta-0.13.README b/xdelta1/xdelta-0.13.README
new file mode 100755
index 0000000..f928f66
--- /dev/null
+++ b/xdelta1/xdelta-0.13.README
@@ -0,0 +1,311 @@
+
+I have placed version 0.13 of XDELTA, new delta generator and
+prototype RCS-replacement program at:
+
+  ftp://www.xcf.berkeley.edu/pub/jmacd/xdelta-0.13.tar.gz
+
+======
+
+Hereafter, the algorithm and program are described.  A delta algorithm
+operates on two files, a FROM file and a TO file.  It computes enough
+informnation to reconstruct the TO file from the FROM file.  So the
+delta and it's inverse, patch, work as follows:
+
+P = delta (FROM, TO)
+TO = patch (FROM, P)
+
+The delta generator portion of this program is a delta algorithm which
+searches for substring matches between the files and then outputs
+instructions to reconstruct the new file from the old file.  It
+produces a set of copy/insert instructions that tell how to
+reconstruct the file as a sequence of copies from the FROM file and
+inserts from the delta itself.  In this regard, the program is much
+closer to a compression program than to a diff program.  However, the
+delta is not "compressed", in that the delta's entropy H(P) will be
+very similar to the entropy of the portions of the TO file not found
+within the FROM file.  The delta will compress just as well as the TO
+file will.  This is a fundamentally different method of computing
+deltas than in the traditional "diff" program.  The diff program and
+it's variants use a least-common-subsequence (LCS) algorithm to find a
+list of inserts and deletes that will modify the FROM file into the TO
+file.  LCS is more expensive to compute and is sometimes more useful,
+especially to the human reader.  Since LCS is a fairly expensive
+algorithm, diff programs usually divide the input files into
+newline-separated "atoms" before computing a delta.  This is a fine
+approximation for text files, but not binary files.
+
+I propose this delta generator as a replacement for "diff" in
+applications where the insert/delete delta is not required.  Since the
+copy/insert delta is easier to compute, it does not have to make the
+reduction in input size by breaking the file into lines.  The delta
+generator works well on binary files.
+
+The next question is whether it is actually desirable to compute
+deltas between binary files.  The answer is certainly yes, even though
+some binary file formats will not have a great degree of similarity
+between versions which were generated between minor modifications to
+their sources.  First, I have evidence that some file formats (notably
+FrameMaker documents) work very well.  Machine-dependant object files
+and executables don't work very well, but it is still worth doing.
+The reason it is still worthwhile is that compression takes longer
+than finding these deltas, so any space savings the delta generator
+produces it very likely to reduce the total archival time.  Even if
+the delta generator saves no space, the total time well end up less
+than twice the time of compression.  I will include some measurements
+at the end of this writing.
+
+With the delta generator as a building block, I have written a
+replacement for RCS.  It does not have all the user-level features
+someone would want in RCS, but these things only get in the way when
+the code is used by higher level version control programs such as
+PRCS.  For now, the prototype supports the following actions:
+
+register                create an empty version file
+checkin                 create a new version
+checkout                extract an old version
+
+The program departs from the RCS model in that it does not branch it's
+versions.  The reason for doing this is to solve several problems with
+RCS (aside from it's use of diff which is solved by using my delta
+generator).
+
+1. Development very often ends up off the "main trunk" of the RCS
+file, which causes an O(N) extract, where N deltas must be applied to
+the head of the trunk before getting the desired file.  Once this
+occurs, things get worse and worse.  Of course, it is possible to
+remedy the situation by checking it in once on the trunk, but that
+defeats the purpose of branching, because you lose the information
+about branch of development you are on.  Further, the notion of
+branching individual files conflicts with the model presented by
+higher level version control programs such as PRCS, which would rather
+not have to go to extra trouble to insure that development does not
+end up off the trunk.
+
+2. Deltas are never used more than once in a particular version
+history, even if they contain the same data as another delta.
+
+Conceptually, to get rid of RCS-like branching and retain the "deltas
+are computed between a file and its parent", the xdelta version
+control library computes a reverse delta between the new file and the
+entire version file.  The most recently checked in version is always
+the "head", in RCS terms.  It is always the quickest and easiest to
+extract.  For a repository with N versions, version I requires the
+application of (N-I) deltas, regardless of how the set of versions are
+related.
+
+Each delta contains a set of instructions and all data which was
+originally part of a file version but missing in the FROM file.  This
+data is represented without compression or modification.  As a result,
+each delta may be used as an input for finding future deltas just as a
+regular file may be.
+
+Several equations describe the process, first some notation:
+
+        V0 is the version file with 1 version
+        V1 is the version file with 2 versions,
+        ...
+        VN is the version file with N+1 versions
+
+        F0 is the 1st file checked in, upon checkin V0 is produced
+        F1 is the 2nd file checked in, upon checkin V1 is produced
+        ...
+        FN is the Nth file checked in, upon checkin VN is produced
+
+        D0 is the 1st delta produced, upon checkin of F1
+        D1 is the 2nd delta produced, upon checkin of F2
+        ...
+        DN is the Nth delta produced, upon checkin of FN+1
+
+Checkin goes as follows:
+
+        V0 <- F0
+
+        D0 <- delta (F1, F0)
+        V1 <- F1 + D0
+
+        D1 <- delta (F2 + D0, F1)
+        V2 <- F2 + D1 + D0
+
+        D2 <- delta (F3 + D1 + D0, F2)
+        V3 <- F3 + D2 + D1 + D0
+
+an so on.  To checkout:
+
+        F3 is immediate
+        F2 <- patch (F3 + D1 + D0, D2)
+        F1 <- patch (F2 + D0, D1)
+        F0 <- patch (F1, D0)
+
+Now I will describe why this is just as good as branching, even though
+the branches do not affect which files are used for computing deltas,
+and why it is just as good as the RCS model.
+
+Suppose the we have a sequence of checkins with RCS version numbers
+and their sequence numbers:
+
+F0: 1.1
+F1: 1.2
+F2: 1.3
+F3: 1.1.1.1
+F4: 1.1.1.2
+F5: 1.1.1.3
+F6: 1.4
+F7: 1.5
+
+Of interest are the 4th checkin, from 1.3 to 1.1.1.1, and the 7th
+checkin, from 1.1.1.3 to 1.4.  I will now use the '-' sign to denote
+the taking of a delta and '+' for patch.  Thus, delta(A,B) is
+equivalent to B-A, and patch(A,xdelta(A,B)) is equivalent to A+(B-A),
+or B, as it should be.  In the above sequence of checkins, these
+deltas are produced:
+
+D0=F0-F1
+D1=F1-F2-D0
+D2=F2-F3-D1-D0
+D3=F3-F4-D2-D1-D0
+D4=F4-F5-D3-D2-D1-D0
+D5=F5-F6-D4-D3-D2-D1-D0
+D6=F6-F7-D5-D4-D3-D2-D1-D0
+
+The checkin of F3 produces D2.  The concern is whether any deletions
+between 1.1 and 1.3 have to be inserted into D2.  They have not,
+because any deletions between 1.1 and 1.3 appear in D0 and D1.  Thus,
+using D0, D1, and F3 as an input for computing D2 achieves the desired
+results: the deletion is not reflected twice in separate deltas.
+
+The properties of this version format differ from the RCS format.  It
+ensures that recently checked-in versions are quick to check out, no
+matter where in the "tree" they occur.  One potential problem with
+this formulation is that according to the formulae above, the ammount
+of memory and computation required for checking in each new version
+grows with the number of previous versions.  To prevent this it only
+uses up to some limiting value (currently set at 10) of previous
+deltas in computing new deltas.  This means that deletions on a branch
+over 10 checkins old will be duplicated on a checkin.  Another
+property is that to delete a version all older versions must first be
+deleted or off-line processing may be done to reconstruct the delta
+log with the version removed (an expensive but not time-critical
+operation).  It also lends itself to keeping windowed histories, such
+as "only keep the last 20 revisions, anything earlier than that may be
+thrown away".
+
+---
+
+The current prototype implementation is complete.  The program,
+'xdelta', has a command syntax similar to PRCS:
+
+xdelta COMMAND [OPTIONS] ARG1 ARG2 ...
+
+There are 5 commands:
+
+ register  Create a versionfile
+ checkin   Checkin a new version
+ checkout  Checkout a version (latest or -r VERSION)
+ info      Show information on a version (all or -r VERSION)
+ delta     Produce a delta from ARG1 to ARG2 producing ARG3
+ patch     Patch file ARG1 with ARG2 producing ARG3
+
+The -r option specifies a version (the latest version is always the
+default).  Versions are sequentially numbered.  The file itself is a
+GNU DBM database which stores the deltas and latest version.  The file
+format is subject to change as I look for storage methods that are
+portable to Windows (otherwise, the delta generator has already been
+tested on Windows).
+
+The DELTA and PATCH commands are unrelated to the rest, and simply
+serve to generate deltas (and could be used as replacements for "diff"
+and "patch").  All operations are verified with MD5 checksums, which
+are saved for each version in the version file and the FROM and TO
+files when generating and applying deltas.
+
+---
+
+Some timing comparisons (remember all times include MD5 computations)
+on a 300MHz Alpha:
+
+Two kernels:
+
+   7875136 /genvmunix
+   6677320 /vmunix
+
+And the times to compress and delta them:
+
+                                        time(s) size(bytes)
+
+xdelta delta /genvmunix /vmunix patch:  10.1    4338029
+gzip --best /genvmunix:                 34.0    3413963
+gzip --best /vmunix:                    63.7    2501766
+gzip --best patch:                      51.9    1531163
+
+(I'm not sure why there's such a variation in gzip times--it was
+repeatable.)
+
+xdelta produces a patch which is 4338029 bytes, approximately 2.6
+megabytes smaller than its TO file.  The total space required for
+saving the two kernels compressed is 5915729 bytes, produced in 97.7
+seconds.  The total space for storing /genvmunix and the delta
+compressed is 4945126 bytes, produced in 96.0 seconds.  Using the
+delta saved approximately one megabyte and two seconds.
+
+---
+
+All the files in PRCS 1.0.0 and 1.2.0 concatenated (files ordered
+lexigraphically):
+
+   1678837 /tmp/1.0.0
+   2021819 /tmp/1.2.0
+
+                                                        time(s) space(bytes)
+
+xdelta delta /tmp/1.0.0 /tmp/1.2.0 /tmp/patch:          1.5     695893
+gdiff -a --rcs /tmp/1.0.0 /tmp/1.2.0 /tmp/patch:        3.7     1524705
+
+Even though both files were completely text, gdiff missed a lot of
+similar regions because a line had been partially modified.  Xdelta
+performs better in both dimensions.
+
+---
+
+All the .c and .h files in GNU gcc 2.7.2 and 2.7.2.3 concatenated (files
+ordered lexigraphically).  These files are highly similar:
+
+  15590954 /tmp/2.7.2
+  15599644 /tmp/2.7.2.3
+                                                        time(s) space(bytes)
+
+xdelta delta /tmp/2.7.2 /tmp/2.7.2.3 /tmp/patch:        7.3     11922
+gdiff -a --rcs /tmp/2.7.2 /tmp/2.7.2.3:                 4.8     19477
+
+Here xdelta takes a about 50% longer and produces a slightly smaller
+diff.  I think the improved performance in the other two examples
+makes xdelta an all around winner.
+
+---
+
+A note on FrameMaker files, which I happen to know a fair bit about.
+Even making radical modifications to a Frame+SGML document leaves much
+of its content unchanged, due to the fact that the EDD and various
+catalogs do not change.  When only minimal modifications are performed
+
+Take a 24 page document, chapter 15 of the SGML developers guide for
+version 5.5. I replaced 38 occurances of "document" with
+"abcdefghijklmnop" and added the source of this README from here up at
+the end, making it 33 pages.
+
+  250880 graphics.before.fm
+  272384 graphics.after.fm
+
+The document grew by about 22 kbytes.  The patch 32780 bytes.  The
+same diff generated by GNU diff is 101097 bytes.  Clearly, Frame
+documents are very good for binary version control.
+
+---
+
+I also have evidence that the program works well on uncompressed image
+formats such as the GIMP's XCF file format.
+
+This program will be the basis of PRCS version 2, which will support
+client/server distributed version control.
+
+Please send any comments, questions, thoughts, or interest to me,
+jmacd@cs.berkeley.edu.