BDIFF 1 "July 1999"

NAME

bdiff - difference of binary files

SYNOPSIS

bdiff [options] old-file new-file >patch-file

DESCRIPTION

bdiff
computes differences between two binary files. Output can be either a
somewhat human-readable protocol, or a binary file readable by
bpatch.
It handles insertion and deletion of data as well as changed bytes.

OPTIONS

-q                - Use QUOTED format (default);
-f                - Use FILTERED format;
-b                - Use BINARY format;
--format=FMT      - Select format by name: (binary, filtered, quoted)
-m N, 
--min-equal=N     - Two chunks of data are recognized as being identical
                    if they are at least N bytes long, the default is 24;
-o FILENAME, 
--output=FILENAME - Specify output file name. Use this instead of a shell
                    redirection to get binary output on an MS-DOS system:
                    bdiff does not contain non-portable hacks to massage
                    stdout into binary mode. Specifying --output=- does
                    nothing;
-V, 
--verbose          - Print status messages while processing input;
-h,
--help             - Show help screen and exit;
-v,
--version          - Show version number and exit.

ALGORITHM

bdiff tries to locate maximum-length substrings of the new file
in the old data. Substrings shorter than N (argument to the
-m option) are not considered acceptable matches. Everything
covered by such a substring is transmitted as a position, length pair,
everything else as literal data.

bdiff uses the block-sort technique to allow O(lgN) searches in
the file, giving an estimated O(NlgN) algorithm on average.

The program requires about five times as much memory as the old file,
plus storage for the new file. This should be real memory, bdiff
accesses all of it very often.

OUTPUT FORMATS

Output always goes to standard output.

The quoted format
(default) is similar to diff output in
unified format: `+' means added data, and a space means data kept from
the old file. Lines prefixed with `@' inform you about the position
of the next `space' line in the source file (byte offset).
Unlike in diff, there's no implicit line feed after each
line of output. Non-printable characters (see isprint(3)) and
the backslash character are represented by a \ followed by the octal
three-digit character code.

The filtered format
is like the quoted format, but non-printable characters are replaced
by dots (.) here.

The binary format
is machine-readable, and omits details for common
blocks. All words are in little-endian format (low byte first).

8 bytes  - Signature "bdiff02\x1A", where 02 is kind-of a version
           number. An earlier version (with an O(n^3) algorithm)
           used the number 01. \x1A is ASCII 26 (Control-Z, an MS-DOS
           end-of-file marker).
4 bytes  - Length of old file in bytes.
4 bytes  - Length of new file in bytes.
n bytes  - The patch itself, a sequence of the following records:

literally added data:
1 byte   - ASCII 43 (`+');
4 bytes  - number of bytes;
n bytes  - data.

common block:
1 byte   - ASCII 64 (`@');
4 bytes  - file position in old file;
4 bytes  - number of bytes;
4 bytes  - checksum.

The checksum is computed using the following algorithm:
   long checksum(char* data, size_t len)
   {
       long l = 0;
       while(len--) {
           l = ((l >> 30) & 3) | (l << 2);
           l ^= *data++;
       }
       return l;
   }
(rotate current checksum left by two and xor in the current byte)

ADMINISTRATIVIA

This manual page is for version 0.2 of bdiff.

(c) copyright 1999 by Stefan Reuther <Streu@gmx.de>. Copying this
program is allowed, as long as you include source code and document
changes you made in a user-visible way so people know they're using
your version, not mine.

This program is distributed in the hope that it will be useful, but
without warranties of any kind, be they explicit or implicit.

SEE ALSO

  diff (1),
  patch (1),
  bpatch (1),
  isprint (3)
