NAME

App::FileSync::Delta - rsync-style block deltas in pure Perl

SYNOPSIS

my $signature = App::FileSync::Delta::signature($old_path);
App::FileSync::Delta::diff($new_path, $signature, $spool);
seek $spool, 0, 0;
App::FileSync::Delta::apply($old_path, $spool, $out);

FUNCTIONS

block_size

Purpose: the block length for a file of a given size.

Args: $size in bytes.

Returns: $BLOCK (16 KiB) for files up to $BLOCK * $MAX_BLOCKS; above that, a larger whole-KiB block so the signature stays at most about $MAX_BLOCKS records.

Side Effects: none.

Usage:

my $block = App::FileSync::Delta::block_size(-s $path);

EXAMPLE

print App::FileSync::Delta::block_size(1_000_000), "\n";	# 16384

API SPECIFICATION

INPUT

[ { name => 'size', type => 'integer', min => 0, optional => 1 } ]

OUTPUT

{ type => 'integer', min => 1024 }

MESSAGES

None.

FORMAL SPECIFICATION

block_size(s) = BLOCK                                   if s ≤ BLOCK × MAX_BLOCKS
              = (⌈⌈s / MAX_BLOCKS⌉ / 1024⌉ + 1) × 1024    otherwise

signature

Purpose: describe a file the receiver already holds.

Args: $path, optional $block length (default "block_size").

Returns: { size, blocklen, blocks => [ [ weak, strong ], ... ] }, one pair per full block (a short final block is not included; its bytes are simply never reused), or undef for a missing file or one smaller than $MIN_SIZE.

Side Effects: reads the file.

Usage:

my $signature = App::FileSync::Delta::signature($abs) or return 0;

EXAMPLE

my $sig = App::FileSync::Delta::signature('/tmp/big.iso');
printf "%d blocks of %d bytes\n", scalar @{ $sig->{blocks} }, $sig->{blocklen} if $sig;

API SPECIFICATION

INPUT

[
	{ name => 'path',  type => 'string', optional => 1 },
	{ name => 'block', type => 'integer', min => 1, optional => 1 },
]

OUTPUT

{ type => 'hashref', optional => 1 }

MESSAGES

Key        Meaning                    Resolution
io.read    the file cannot be read    check permissions

FORMAL SPECIFICATION

signature(p, b) = ⊥                                    if p ¬in; dom FS ∨ #FS(p) < MIN_SIZE
                = ⟨size ↦ #F, blocklen ↦ b,
                   blocks ↦ ⟨(weak(F[i]), sha256(F[i])) | i ∈ 0 .. ⌊#F / b⌋ − 1⟩⟩
                  where F = FS(p), F[i] = bytes i×b .. (i+1)×b − 1

encode_signature

Documented with "decode_signature" below.

decode_signature

Purpose: put a signature's blocks on the wire and take them off again.

Args: encode_signature($signature); decode_signature($bytes, $count).

Returns: the encoded bytes (36 per block: a big-endian weak sum then the 32-byte SHA-256); the decoded arrayref of [ weak, strong ] pairs.

Side Effects: none.

Usage:

my $bytes = App::FileSync::Delta::encode_signature($signature);
my $blocks = App::FileSync::Delta::decode_signature($bytes, $count);

EXAMPLE

my $blocks = App::FileSync::Delta::decode_signature(
	App::FileSync::Delta::encode_signature($sig), scalar @{ $sig->{blocks} });

API SPECIFICATION

INPUT

[
	{ name => 'bytes', type => 'string', optional => 1 },
	{ name => 'count', type => 'integer', min => 0, optional => 1 },
]

OUTPUT

{ type => 'arrayref' }

MESSAGES

Key               Meaning                              Resolution
delta.bad_count   the block count is not a number      a peer bug; resync with --no-delta
delta.bad_length  the bytes do not match the count     a peer bug; resync with --no-delta

FORMAL SPECIFICATION

encode(⟨(w₁,s₁), …, (wₙ,sₙ)⟩) = be32(w₁) ⁀ s₁ ⁀ … ⁀ be32(wₙ) ⁀ sₙ
decode(encode(bs), #bs) = bs
pre decode: #bytes = 36 × count

diff

Purpose: write the delta that turns the receiver's file into $path.

Args: $path (the new content), $signature (of what the receiver has; blocklen and blocks are used), $out (a writable handle).

Returns: { literal, copy, ops }: bytes sent literally, bytes copied, and records written, so the caller can decide whether the delta beats the file.

Side Effects: reads $path; writes copy and literal records to $out.

Usage:

my $stats = App::FileSync::Delta::diff($abs, $signature, $spool);

EXAMPLE

open my $spool, '+>', undef;
my $stats = App::FileSync::Delta::diff('/tmp/new.bin', $sig, $spool);
printf "%d literal bytes in %d records\n", $stats->{literal}, $stats->{ops};

API SPECIFICATION

INPUT

[
	{ name => 'path',      type => 'string', min => 1 },
	{ name => 'signature', type => 'hashref' },
	{ name => 'out',       type => 'handle' },
]

OUTPUT

{
	type => 'hashref',
	schema => {
		literal => { type => 'integer', min => 0 },
		copy    => { type => 'integer', min => 0 },
		ops     => { type => 'integer', min => 0 },
	},
}

MESSAGES

Key                  Meaning                              Resolution
delta.no_output      no output handle                     a caller bug
delta.no_block       the signature has no block length    a peer bug
delta.write          the delta cannot be written          check space for the spool
io.read              the new file cannot be read          check permissions

FORMAL SPECIFICATION

let R = records written to out
apply(old, R) = FS(path)                (correctness)
literal = Σ { #l | L(l) ∈ R } ; copy = Σ { n | C(o, n) ∈ R } ; ops = #R
literal + copy = #FS(path)

PSEUDOCODE

index the receiver's blocks by weak checksum
while the next full block equals the receiver's block at the same index:
	emit a copy of it (no rolling needed for an unchanged prefix)
read up to SCAN_LIMIT more bytes into a window buffer
slide a one-block window through the buffer:
	if its weak sum is indexed and the strong hash matches a block:
		emit a copy, jump a whole block
	else: add one byte to the literal run, roll the sums forward one byte
flush the rest of the buffer and the unscanned tail as literals

write_copy

Documented with "write_literal" below.

write_literal

Purpose: write one delta record.

Args: write_copy($out, $offset, $length); write_literal($out, $bytes) (an empty literal writes nothing).

Returns: 1.

Side Effects: writes to $out.

Usage:

App::FileSync::Delta::write_copy($spool, $offset, $length);
App::FileSync::Delta::write_literal($spool, $bytes);

EXAMPLE

App::FileSync::Delta::write_literal($out, "new text\n");

API SPECIFICATION

INPUT

[
	{ name => 'out',    type => 'handle' },
	{ name => 'offset', type => 'integer', min => 0 },
	{ name => 'length', type => 'integer', min => 0 },
]

OUTPUT

{ type => 'integer', min => 1, max => 1 }

MESSAGES

Key           Meaning                      Resolution
delta.write   the record cannot be written  check space for the spool

FORMAL SPECIFICATION

write_copy(o, n): out' = out ⁀ "C" ⁀ be32(o) ⁀ be32(n)
write_literal(b): out' = out ⁀ "L" ⁀ be32(#b) ⁀ b    if b ≠ ⟨⟩

read_op

Purpose: read the next delta record.

Args: $in, a handle positioned at a record.

Returns: ('copy', $offset, $length), ('literal', $bytes), or the empty list at the end. A list because callers loop with while (my ($type, @rest) = read_op($in)).

Side Effects: advances $in.

Usage:

while (my ($type, @rest) = App::FileSync::Delta::read_op($spool)) { ... }

EXAMPLE

my ($type, $offset, $length) = App::FileSync::Delta::read_op($spool);

API SPECIFICATION

INPUT

[ { name => 'in', type => 'handle' } ]

OUTPUT

{ type => 'arrayref' }

MESSAGES

Key                 Meaning                         Resolution
delta.read          the delta cannot be read        check the spool
delta.bad_record    an unknown record type          a peer bug; resync with --no-delta
io.short            the delta ends mid-record       a peer bug; resync with --no-delta

FORMAL SPECIFICATION

read_op("C" ⁀ be32(o) ⁀ be32(n) ⁀ rest) = (copy, o, n)
read_op("L" ⁀ be32(k) ⁀ b ⁀ rest) = (literal, b)    where #b = k
read_op(⟨⟩) = ⟨⟩

apply

Purpose: rebuild a file from the old copy and a spooled delta.

Args: $old_path, $in (the delta), $out (where the new content goes).

Returns: { size }, the bytes written.

Side Effects: reads $old_path and $in; writes $out.

Usage:

my $result = App::FileSync::Delta::apply($old, $spool, $out);

EXAMPLE

open my $out, '>', '/tmp/rebuilt.bin';
App::FileSync::Delta::apply('/tmp/old.bin', $spool, $out);

API SPECIFICATION

INPUT

[
	{ name => 'old_path', type => 'string', min => 1 },
	{ name => 'in',       type => 'handle' },
	{ name => 'out',      type => 'handle' },
]

OUTPUT

{ type => 'hashref', schema => { size => { type => 'integer', min => 0 } } }

MESSAGES

Key                   Meaning                            Resolution
io.read               the old file cannot be read        check permissions
io.seek               a copy points outside the file     the delta does not fit this file
delta.write_restored  the output cannot be written       check space

FORMAL SPECIFICATION

apply(old, R) = ⁀/ ⟨ bytes(r) | r ← R ⟩
  where bytes(C(o, n)) = FS(old)[o .. o + n − 1], bytes(L(b)) = b

read_exact

Purpose: read exactly $length bytes.

Args: $fh, $length, $what (named in errors).

Returns: the bytes.

Side Effects: advances $fh.

Usage:

my $data = App::FileSync::Delta::read_exact($fh, $block, $path);

EXAMPLE

my $header = App::FileSync::Delta::read_exact($spool, 8, 'delta');

API SPECIFICATION

INPUT

[
	{ name => 'fh',     type => 'handle' },
	{ name => 'length', type => 'integer', min => 0 },
	{ name => 'what',   type => 'string' },
]

OUTPUT

{ type => 'string' }

MESSAGES

Key        Meaning                         Resolution
io.read    the read failed                 check the device
io.short   fewer bytes than required       the file was truncated

FORMAL SPECIFICATION

read_exact(fh, n, w) = take(n, rest(fh))   if #rest(fh) ≥ n
                     ↑ io.short           otherwise

LIMITATIONS

Pure Perl: the rolling loop runs at a few MB/s, which is why only $SCAN_LIMIT bytes after the matched prefix are scanned. An edit near the end of a large file whose earlier blocks also shifted is sent mostly literally.
A block that moved by a whole number of blocks is found; a block that occurs twice in the receiver's file is matched to its first occurrence.
Offsets and lengths are 32-bit on the wire, so a delta cannot refer beyond 4 GiB into the receiver's file; larger files fall back to whole-file transfer of the remainder as literals.

AUTHOR

Nigel Horne, <njh at nigelhorne.com>

LICENCE AND COPYRIGHT

Usage is subject to the GPL2 licence terms. If you use it, please let me know.

To install App::FileSync, copy and paste the appropriate command in to your terminal.

cpanm

cpanm App::FileSync

CPAN shell

perl -MCPAN -e shell
install App::FileSync

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	Go to GitHub issues (only if GitHub is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

NAME

SYNOPSIS

FUNCTIONS

block_size

EXAMPLE

API SPECIFICATION

INPUT

OUTPUT

MESSAGES

FORMAL SPECIFICATION

signature

EXAMPLE

API SPECIFICATION

INPUT

OUTPUT

MESSAGES

FORMAL SPECIFICATION

encode_signature

decode_signature

EXAMPLE

API SPECIFICATION

INPUT

OUTPUT

MESSAGES

FORMAL SPECIFICATION

diff

EXAMPLE

API SPECIFICATION

INPUT

OUTPUT

MESSAGES

FORMAL SPECIFICATION

PSEUDOCODE

write_copy

write_literal

EXAMPLE

API SPECIFICATION

INPUT

OUTPUT

MESSAGES

FORMAL SPECIFICATION

read_op

EXAMPLE

API SPECIFICATION

INPUT

OUTPUT

MESSAGES

FORMAL SPECIFICATION

apply

EXAMPLE

API SPECIFICATION

INPUT

OUTPUT

MESSAGES

FORMAL SPECIFICATION

read_exact

EXAMPLE

API SPECIFICATION

INPUT

OUTPUT

MESSAGES

FORMAL SPECIFICATION

LIMITATIONS

AUTHOR

LICENCE AND COPYRIGHT

Module Install Instructions

Keyboard Shortcuts