BlockDiff - Block based diff library

BlockDiff diff compares two source data streams (A and B) at block level. The two streams is compared block by block, and any block in the latter (B) not equal to the former (A) is output to a diff stream (D). Bitmaps is included in the diff stream (D) stream telling where the blocks belong.

The utillity is a part of the lab client "Stand Alone Backup" project at NTNU IT, and is used to reduce storage requirements for subsequent/incremental images of the same disk.

Format

The diff (D) format consist of a sequence of 512 byte block groups. Each group represent 4096 blocks of the two sources, and consist of a bitmap block and 0 to 4096 data blocks. The bitmap bits is set (1) if the two corresponding source blocks is equal. If they differ, the bit is cleared (0) and the source block of the latter (B) is appended to the group. A cleared (0) bit without any corresponding data block denotes end of the latter (B) file.

The latter (B) source may then be recreated by applying the diff (D) to the former (A).

There is no metadata space in the format, so any metadata has to be stores outside the BlockDiff format.

Implementation

The format is implemented in perl as a library "BlockDiff.pm". BlockDiff has two primary methods diff(A, B) and apply(A, D), in addition to a constuctor new(); An utilly package BlockRead is embedded to ease IO.

Synopsis

$bd = new();      # Create a BlockDiff object.
$bd->diff(A, B);  # Emit the diff (D) of A and B
$bd->apply(A, D); # Emit a recreated B from an earlier diff(A, B)

Input parameters

Input parameters (A, B and D) may be a

file name to open and use as input source. "-" is STDIN. The file is gunzipped if the name ends with ".gz"
file descriptor already opened for read
an array reference with inputs handed to apply() and used as input source.

If three or more parameters is given, the number is reduced to two by iterativly encapsulating the first two in an arrayref. This nests apply() so a sequence of diffs may be applied to the A parameter:

apply(A, D1, D2, D3) -> apply([[[A, D1], D2], D3]) -> apply(apply(apply(A, D1), D2), D3)
diff(A, D1, D2, D3, B) -> diff([[[A, D1], D2], D3], B) -> diff(apply(apply(A, D1), D2), D3), B)

If only one parameter is given to apply() its content is emittet, so apply() may be given an arbitrary number of diff sets.

Output stream

The emitted data from diff() and apply() is by default directed to STDOUT. This may be changed by calling $bd->output(O) where O is a

file name to write. The output is gzip'ed if the name ends with ".gz"
file descriptor already opened for write

Command activation

If the library is run as a command ($0 ends with "BlockDiff.pm") "BlockDiff->new->$method(@ARGV);" is executed after shifting $ARGV[0] into $method.

Restore of an image from a base image and two incremental diffs may be done like this:

$LIBPATH/BlockDiff.pm apply base.gz diff1.gz diff2.gz > /dev/sda

A fourth diff may be created like this:

$LIBPATH/BlockDiff.pm diff base.gz diff1.gz diff2.gz /dev/sda | gzip >diff4.gz

Checksum generation

A checksum is generated for the the (outmost) A, B and D streams. This is stored in, and may be retrived from, the BlockDiff object.

Options

There are a few options that may be set om the BlockDiff object. They may be given as parameter to the new() method in the listed order, or set with likenamed methods. Options is inherited when calling new on a BlockDiff object ($new = $old->new;).

output - as described above, STDOUT if undef
digest - digest type to use. 0 to suppress generation, any other scalar (or 256 if undef) is passed to SHA->new(). Pass a Digest object for other types.
blocksize - set a blocksize other than 512. This is for testing purposes only and is strongly discouraged in production since there is no way to determine the blocksize from a diff file.

Example

The following example

#!/usr/bin/perl

use BlockDiff;

open(A, 'echo This is a base stream|') or die "A: $!";
open(B, 'echo This is a file stream|') or die "B: $!";
open(D, '>', \my $D) or die "D: $!";

my $bd = BlockDiff->new;
$bd->output(\*D);     # Write to file descriptor D
$bd->blocksize(1);    # Single byte blocks (for testing only!)

$bd->diff(\*A, \*B);  # Emitt diff into D 

printf( "%s\t[%s]\t%s\n------------------------------\n",
        "Int",
        "01234567",
        "Char",
    );
foreach my $byte (unpack("C*", $D)) {
    printf( "%d\t[%s]\t%s\n",
            $byte,
            unpack("b*", chr($byte)),
            (127 > $byte and $byte > 31) ? chr($byte) : "<chr($byte)>",
        );
}
printf("Base: %s\n", $bd->basesum);
printf("File: %s\n", $bd->filesum);
printf("Diff: %s\n", $bd->diffsum);

will produce the following output:

Int [01234567]      Char
------------------------------
255 [11111111]      <chr(255)>
227 [11000111]      <chr(227)>
102 [01100110]      f
105 [10010110]      i
108 [00110110]      l
63  [11111100]      ?
Base: 0c9ffc552337c75ec00bfe8d4a558f7f2297b82fb7559ff44061f4f3f6ca75e1
File: 8b3be9c3420f4bbcc24d08a0beb3a47d0a29fc05e6c84ea7e0ae48126e6c8b2d
Diff: d415dad229da82595c293f990e9477bcbcce70f97bf545d6a9dc3a00ba838c58

This relates like this (N is newline):

Base:      This is a base streamN
File:      This is a file streamN
Group:     111111112222222233333333
Bitmap:    111111111100011111111100
Diffdata:            fil

So the output ($D) consist of tree block groups:

Bitmap block [11111111]. Since all the eight source block pairs are equal, there is no data blocks in this group.
Bitmap block [11000111] followed by tree data blocks for the zero bits 2. [01100110] ("f") 3. [10010110] ("i") 4. [00110110] ("l")
Bitmap block [11111100]. Since the six last block pairs are equal (including the newline character), no corresponding data blocks is appended. Bit 6 is cleared but has no corresponding data block and thus marks the end of file (B).

Methods

new()

Creator method. Take tree optional parameters:

output - a file name or descriptor to write to. STDOUT on undef.
digest - a Digest:: object or a scalar to pass to Digest::SHA->new(). SHA-256 if undef. Suppress digest calculation if false.
blocksize - Blocksize of bitmap and data blocks. Default value 512. Do not alter except for testing.

If called from an existing object digest and blocksize is inherited unless explicitly overridden.

Returns a newly created object

diff()

Write a diff of two streams. Take two parameters:

base - the input stream to compare with.
file - the input stream to compare.

If more than two parameters is given, the two first is iteratively grouped in a hashref until there is exactly to parameters. The two parameters are passed to a BlockStream object. See the BlockStream package below for further details.

The diff is written to the output channel (STDOUT as default) of the object.

The return value is the object itself on success, undef on error.

apply()

Apply a diff stream on a base stream. Take two parameters:

base - the input stream to compare with.
diff - the diff input stream.

If the diff parameter is missing, the base stream is copied unaltered to the output stream.

If more than two parameters is given, the two first is iteratively grouped in a hashref until there is exactly to parameters. The two parameters are passed to a BlockStream object. See the BlockStream package below for further details.

The result is written to the output channel (STDOUT as default) of the object. apply(base, diff) will recreate the file of a previous diff(base, file) operation.

The return value is the object itself on success, undef on error.

output()

Set or get the output stream. Take one optional parameter:

destination - a file name or descriptor to write to. STDOUT on undef. Output is gzip'ed if the destination is a file name ending in ".gz".

If no parameter is given the object current output file descriptor is returned. Othervise the object itself is returned.

digest()

Set or get the digest object in use. Take one optional parameter:

digest - a Digest:: object, or a scalar to pass to Digest::SHA->new(). SHA-256 is used if undef. Digest calculation is suppressed if false.

If no parameter is given the current Digest:: object is returned. Othervise the object itself is returned.

blocksize()

Set or get the blocksize in use. Take one optional parameter:

blocksize - the size of the bitmap and data blocks in bytes. 512 if false.

If no parameter is given the current blocksize is returned. Othervise the object itself is returned.

basesum(), filesum(), diffsum()

Return the calculated sum as hex string of the base, file or diff stream respectively. No input parameters.

progress()

Set or get the progress intervall in use. Take one optional parameter:

intervall - number io seconds between progress messages. 0 for no reporting.

If no parameter is given the current intervall is returned. Othervise the object itself is returned.

show_progress()

Internal method for displaying progress messages. Take one parameter.

bytes - number of bytes since last call to show_progress.

Status is displayed only at the intervall set by progress();

Return total bytes recorded.

Package BlockStream

The internal package BlockStream is used for the input streams of BlockDiff, and hides the nitty gritty of IO. Its primary method get() return the next block from a stream.

new()

Creator method. Takes two parameters:

source - specification of the input stream
caller - the calling object

The source is one of

a file name to open. "-" for STDIN. If the file name ends with ".gz" it is gzip'ed
a file descriptor alleady open for read
arrayref with parameters handed to the callers apply() to pipe from.

Return the newly created object or undef on open errors.

get()

Take no parameters.

Return the next block from the stream. If less than the blocksize is returned end of file is reached. Subsequent calls return the empty string. The actual read is done in larger chunks to a readahed buffer. Checksum is calculated on the fly in a clone of the callers digest object.

done()

Take no parameters.

Closes the stream. If checksumming, the rest of the stream is read first and the digest object is returned. Othervise an empty string is returned.

Stupid things to do

Diff STDIN (or any other sequential stream) with it self. Will produce meaningless result.
Read a endless stream without turning of checksumming. Will be checksumming the stream to the bitter end.
Call multiple diff() and/or apply() on the same BlockDiff object. Will probably not produce any usable output.

forskit-rse/BlockDiff

About

Resources

Stars

Watchers

Forks

Releases

Packages 0

Languages

Packages