JojoDiff - diff utility for binary files

Copyright © 2002 Joris Heirbaut
This software is hosted by:

1. Purpose

JDIFF is a program that outputs the differences between two (binary) files.
JPATCH can then be used to reconstruct the second file from the first file.
JSYNC is a bash shell script that combines both for synchronizing files or directories.
For example:
• jdiff archive0000.tar archive0001.tar archive0001.jdf
• jpatch archive0000.tar archive0001.jdf archive0001b.tar
  
will create a file archive0001b.tar which is identical to archive0001.tar.
Possible applications include:
• incremental backups,
  
• synchronising files between two computers over a slow network (see JSYNC).
JDIFF tries to find a minimal set of differences between two files using a heuristic algorithm with constant space and linear time complexity. This means that accuracy is traded over speed. JDIFF will therefore, in general, not always find the smallest set of differences, but will try to be fast and will use a fixed amount of memory.
Download these utilities from the Jojo's Binary Diff Download Page.
In the meantime, Rune Bassmann pointed me to the XDelta project - also on Sourceforge - doing the same things and a lot more...

2. Version and history

The current version of this utility is bèta 0.4c dating from January 2003. The modification history is as follows:

v0.1	June 2002	Insert/delete algorithm.
v0.2a	June 2002	Optimized patch files.
v0.2b	July 2002	Bugfix on code-length of 252.
v0.2c	July 2002	Bugfix on divide-by-zero in verbose mode.
v0.3a	July 2002	Copy/insert algorithm.
v0.4a	September 2002	Select "best" of multiple matches.
v0.4b	October 2002	Optimize matches.
v0.4c	January 2003	Rewrote selection algorithm between multiple matches.

Over time, reliability (= correct patch files) and accuracy (= smaller patch files) have been improved, and still need to be improved!

3. Installation

On Windows systems:
• Compiled executables are within the "win32" directory. You can run them from a command prompt. If you want to use the JSYNC shell script, you will need to download the Cygwin environment from www.cygwin.com.
On GCC/Linux systems:
• Compile the source by running "make" within the "src" directory.
• Copy the resulting EXE files to our /usr/local/bin.
• Within the bash directory, you can find an example BASH script, JSYNC, which I use for synchronizing files between two computers connected over a slow network.
Within the GCC/Cygwin environment:
• Compiled executables are within the "cygwin" directory.
• Within the bash directory, you can find an example BASH script, JSYNC.

4. Usage

Options:

-v	Verbose (greeting, results and tips).
-vv	Verbose (debug info).
-h	Help (this text).
-l	Listing (ascii output).
-lr	Regions (ascii output).
-b	Better: use copy/insert method (random access to original file).
-f	Fast: use insert/delete method (sequential access to original file).
-ff	Faster: no out of buffer compares, insert/delete method.
-m size	Size (in kB) for look-ahead buffers (default 128).
-s size	Number of samples per file (default 32749).

Principles:
JDIFF tries to find equal regions between two binary files using a heuristic hash algorithm and outputs the differences between both files. Heuristics are generally used for improving performance and memory usage, at the cost of accuracy. Therefore, this program may not find a minimal set of differences between files.

Notes:
• Options -m and -s should be used after -b, -f or -ff.
• Accuracy may be improved by increasing the number of samples.
• Speed may be increased with option -f or -ff (lower accuracy).
• Sample size is always lowered to the largest n-bit prime (n < 32)
• Original and new files must be random access files.
• Output is sent to standard output if output file is missing.

Options:

-v	Verbose (greeting, results and tips).
-vv	Verbose (debug info).
-vvv	Verbose (more debug info).
-h	Help (this text).

Principles:
JPATCH reapplies a diff file, generated by jdiff, to the original file, restoring the new file.

description:
JSYNC synchronizes files or directories between two or more computers by passing jdiff patch files through a remote directory.
JSYNC first copies missing files from the remote directory to the archive directory.
In output mode, JSYNC copies the source data into the archive directory and outputs the difference to the remote directory.
In input mode, JSYNC replaces the source data with the data in the archive directory.
In update mode, JSYNC will input only if new patch files were found.
In case source is a directory, tar is used to create one source file.
By default, jsync will store the last archived data, every jdiff patch file and the original data. This allows to restore the source data in each archived state (like an incremental backup), but will consume 2 or more times the size of the source data in storage. During operation, this will go up to 4 or 5 times the source data.
When using the -l (low storage) option, jdiff will only store the last state of the archive, reducing storage to respectively 1 and 3 times the source size when idle and during operation.

arguments:

mode	either "inp", "out" or "upd"
archivedir	directory in which archive and temporary files are created
remotedir	directory in which archive files are copied
archive	name of the archive
source	the source file or directory

options:

-b	best:	take best of uuencode+diff vs. jdiff.
-s	silent:	do not display activity.
-v	verbose:	do not display activity.
-l	low storage:	do not keep old files.
-i	interactive:	ask before overwriting patch file.

example:
Write changes in ~/data into ~/sync and /mount/srvr1/user/sync:
host1$ jsync out ~/sync /mount/srvr1/user/sync mydata ~/data
On the other host, read changes from remote dir and apply to data:
host2$ jsync upd ~/sync /mount/srvr1/user/sync mydata ~/data

5. Contacts and remarks

Author:	Joris Heirbaut
Address:	Rue de la Sarthe 18D
	B-4217 Héron
	Belgium (Europe)
E-mail:	joheirba@tijd.com

If you like this program, please let me know (by email). If you reuse the source code for your personal (open source) applications, please let me know too.
Concerning the algorithm:

I have written this program because I need to synchronise data between two distant computers connected through a slow network (an IDSN line). Strangely enough, I did not find any program performing a "diff" on binary files that suited my needs (the binary diff program written by Kris Coppieters took too long to complete on the files I had because it tries to find a perfect, minimal set of differences between files).
Afterwards, Rune Bassmann pointer me to the XDelta project, perfectly doing what I need and much more. Additionally, the accompagnying master thesis from Joshua P. MacDonald, describes all possible algorithms for generating differences between binary files, including the algoritm implemented by JDIFF. JDIFF actually
Please feel free to reuse any of the ideas presented within this program and its source code within any other programs adhering to the GNU General Public Licence.
About the source code

I am certainly not an experienced C-programmer, which perhaps may show within the sources. I apologize for any bad C-contructs or C-coding that might occur. If so, please let me know, I'm always eager to learn.

6. Acknowledgements