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 thing.

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.
v0.5	September 2003	Some optimizations and bugfixes.
v0.6	July 2005	Support for files larger than 2GB (untested).

3. List of files

The download of JDIFF contains following files:

cygwin\	jdiff.exe	Cygwin executable
	jpatch.exe	Cygwin executable
	jdiffl.exe	Cygwin executable for large files
	jpatchl.exe	Cygwin executable for large files
win32\	jdiff-w32.exe	Win32 executable
	jpatch-w32.exe	Win32 executable
	jdiffl-w32.exe	Win32 executable for large files
	jpatchl-32.exe	Win32 executable for large files
src\	jdiffos.h	OS/machine dependent definitions for jdiff.c and jpatch.c
	jdiff.c	jdiff source
	jpatch.c	jpatch source
	Makefile	makefile
	jtst	shell script I use for testing jdiff
bash\	jsync	jsync shell script

On Windows systems: 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 executing

cc -o jdiff.exe jdiff.c

cc -o jpatch.exe jpatch.c

On most systems, this will yield executables with support for large files. If necessary, modify the jdiffos.h file for your environment. If you send me the settings necessary for your environment, I will be glad to include them within the next version of jdiff.

4. Usage

jdiff [options] original_file new_file [output_file]
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.
jpatch [options] original_file patch_file [output_file]
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.
jsync [options] mode archivedir remotedir name source
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 general idea behind the algoritm implemented by jdiff. What jdiff adds is the hash key calculation, collision strategy, and selection heuristic between multiple matches.

6. Copyrights & acknowledgements