blib/lib/App/FileSync/Delta.pm

filter: Statementstmt 99.6% 255 / 256 Branchbran 74.4% 67 / 90 Conditioncond 51.8% 14 / 27 MC/DCmcdc 25.0% 4 / 16 Subroutinesub 100% 40 / 40 Podpod 100% 10 / 10 totaltotal 88.8% 390 / 439 CC 61 SCAR 16.0
CC
61
Cov
90%
_rolling_scan
13.0
signature
9.1
read_op
6.2
CRAP 4.9
« blib/lib/App/FileSync/I18N.pm ↑ Summary blib/lib/App/FileSync/Platform.pm »
1 package App::FileSync::Delta;
2  
3 # rsync-style block matching. The receiver describes the file it already has as
4 # one strong hash per fixed-size block; the sender scans the new file with a
5 # rolling checksum and emits either a copy of a block the receiver already has
6 # or the literal bytes that changed.
7 #
8 # The scanner is pure Perl, so it is deliberately bounded: only files of at
9 # least $MIN_SIZE are worth a signature, and at most $SCAN_LIMIT bytes per file
10 # are examined for matches. Whatever lies beyond that is sent literally, which
11 # is still correct, just not smaller. A small edit in a large file is cheap
12 # because the unchanged leading blocks are matched without scanning.
13  
14 326 ▶use App::FileSync::Platform;
Subroutine BEGIN: called CC=1 SCAR=0.0
15  
16 326 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
17 326 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
18 326 ▶use autodie qw(:all);
Subroutine BEGIN: called CC=1 SCAR=0.0
19  
20 326 ▶use Digest::SHA ();
Subroutine BEGIN: called CC=1 SCAR=0.0
21 326 ▶use Readonly;
Subroutine BEGIN: called CC=1 SCAR=0.0
22 326 ▶use Sub::Private { mode => 'enforce' };
Subroutine BEGIN: called CC=1 SCAR=0.0
23  
24 326 ▶use App::FileSync::I18N qw(throw os_error);
Subroutine BEGIN: called CC=1 SCAR=0.0
25 326 ▶use App::FileSync::IO qw(open_file);
Subroutine BEGIN: called CC=1 SCAR=0.0
26  
27 326 ▶use version; our $VERSION = version->declare('0.002.1');
Subroutine BEGIN: called CC=1 SCAR=0.0
28  
29 # Tunables (package variables so tests can shrink them with "local").
30 326 our $MIN_SIZE = 65_536;
31 326 our $BLOCK = 16_384;
32 326 our $MAX_BLOCKS = 4_096;
33 326 our $SCAN_LIMIT = 8 * 1024 * 1024;
34 326 our $LITERAL = 262_144;
35  
36 # Wire format of a signature record: a 32-bit weak sum then a SHA-256.
37 326 Readonly::Scalar my $WEAK_BYTES => 4;
38 326 Readonly::Scalar my $STRONG_BYTES => 32;
39 326 Readonly::Scalar my $RECORD_BYTES => $WEAK_BYTES + $STRONG_BYTES;
40  
41 # Delta records: "C" + offset + length, or "L" + length + bytes.
42 326 Readonly::Scalar my $COPY => 'C';
43 326 Readonly::Scalar my $LIT => 'L';
44 326 Readonly::Scalar my $COPY_HEADER => 8;
45 326 Readonly::Scalar my $LIT_HEADER => 4;
46  
47 # Block sizes are rounded to whole kibibytes.
48 326 Readonly::Scalar my $KIB => 1024;
49  
50 # Each half of the weak checksum is a 16-bit sum; the second half is packed
51 # above the first.
52 326 Readonly::Scalar my $HALF => 0xffff;
53 326 Readonly::Scalar my $HALF_BITS => 16;
54  
55 # The rolling window reads the buffer a byte at a time with vec().
56 326 Readonly::Scalar my $BYTE_BITS => 8;
57  
58 # The weak checksum unpacks this many bytes at a time.
59 326 Readonly::Scalar my $SUM_SLICE => 65_536;
60  
61 # rsync's weak checksum: two 16-bit sums, cheap to roll by one byte. Lexical:
62 # it runs once per block.
63 #
64 # b is defined as the sum of (length - i) * byte[i]. Adding each byte to a,
65 # then a to b, gives the same total: byte[i] is in a for the length - i steps
66 # from i on. That needs no multiply and no index, and unpack walks the bytes
67 # in C. Unpacking a slice at a time keeps a large block from becoming one
68 # huge list, and masking after each slice keeps both sums small integers
69 # however long the block (the old per-byte product passed 2**63, and lost
70 # precision, for blocks over about 256 MiB). Masking early is safe: both
71 # sums are only ever used modulo 2**16.
72 2561 ▶my $weak_parts = sub {
Subroutine __ANON__: called CC=3 SCAR=11.0
73 2561 my ($window) = @_;
74  
75 2561 my ($a, $b) = (0, 0);
76 2561 ▶ for (my $offset = 0; $offset < length $window; $offset += $SUM_SLICE) {
Branch: 1 branch
BranchTrueFalseTotal
if ($offset < length $window) 2579 2561 5140
77 2579 for my $value (unpack 'C*', substr($window, $offset, $SUM_SLICE)) {
78 7272320 $a += $value;
79 7272320 $b += $a;
80 }
81 2579 $a &= $HALF;
82 2579 $b &= $HALF;
83 }
84  
85 2561 return ($a, $b);
86 326 };
87  
88 1937 ▶my $weak = sub {
Subroutine __ANON__: called CC=1 SCAR=0.0
89 1937 my ($a, $b) = $weak_parts->($_[0]);
90 1937 return (($b & $HALF) << $HALF_BITS) | ($a & $HALF);
91 326 };
92  
93 =encoding utf8
94  
95 =head1 NAME
96  
97 App::FileSync::Delta - rsync-style block deltas in pure Perl
98  
99 =head1 SYNOPSIS
100  
101 my $signature = App::FileSync::Delta::signature($old_path);
102 App::FileSync::Delta::diff($new_path, $signature, $spool);
103 seek $spool, 0, 0;
104 App::FileSync::Delta::apply($old_path, $spool, $out);
105  
106 =head1 FUNCTIONS
107  
108 =head2 block_size
109  
110 Purpose: the block length for a file of a given size.
111  
112 Args: C<$size> in bytes.
113  
114 Returns: C<$BLOCK> (16 KiB) for files up to C<$BLOCK * $MAX_BLOCKS>; above that,
115 a larger whole-KiB block so the signature stays at most about C<$MAX_BLOCKS>
116 records.
117  
118 Side Effects: none.
119  
120 Usage:
121  
122 my $block = App::FileSync::Delta::block_size(-s $path);
123  
124 =head3 EXAMPLE
125  
126 print App::FileSync::Delta::block_size(1_000_000), "\n"; # 16384
127  
128 =head3 API SPECIFICATION
129  
130 =head4 INPUT
131  
132 [ { name => 'size', type => 'integer', min => 0, optional => 1 } ]
133  
134 =head4 OUTPUT
135  
136 { type => 'integer', min => 1024 }
137  
138 =head3 MESSAGES
139  
140 None.
141  
142 =head3 FORMAL SPECIFICATION
143  
144 block_size(s) = BLOCK if s ≤ BLOCK × MAX_BLOCKS
145 = (⌈⌈s / MAX_BLOCKS⌉ / 1024⌉ + 1) × 1024 otherwise
146  
147 =cut
148  
149 9 ▶sub block_size {
Subroutine block_size: called CC=4 SCAR=13.9
Pod documented
150 9 my ($size) = @_;
151  
152 9 ▶ my $per_block = (defined $size && $size > $BLOCK * $MAX_BLOCKS)
Branch: 1 branch
BranchTrueFalseTotal
defined $size && $size > $App::FileSync::Delta::BLOCK * $App::FileSync::Delta::MAX_BLOCKS ? : 1 8 9
Condition66%2/3
defined $size and $size > $App::FileSync::Delta::BLOCK * $App::FileSync::Delta::MAX_BLOCKS
!ll&&!rl&&r
081
MC/DC50%1/2
defined $size and $size > $App::FileSync::Delta::BLOCK * $App::FileSync::Delta::MAX_BLOCKS
defined $size $size > $App::FileSync::Delta::BLOCK * $App::FileSync::Delta::MAX_BLOCKS
Truth table66%2/3
A and B
A= defined $sizeB= $size > $App::FileSync::Delta::BLOCK * $App::FileSync::Delta::MAX_BLOCKS
ABresult
0X0
100
111
153 ? int(($size + $MAX_BLOCKS - 1) / $MAX_BLOCKS)
154 : undef;
155  
156 9 ▶ return defined $per_block ? (int(($per_block + $KIB - 1) / $KIB) + 1) * $KIB : $BLOCK;
Branch: 1 branch
BranchTrueFalseTotal
defined $per_block ? : 1 8 9
157 }
158  
159 =head2 signature
160  
161 Purpose: describe a file the receiver already holds.
162  
163 Args: C<$path>, optional C<$block> length (default L</block_size>).
164  
165 Returns: C<{ size, blocklen, blocks =E<gt> [ [ weak, strong ], ... ] }>, one pair
166 per full block (a short final block is not included; its bytes are simply never
167 reused), or C<undef> for a missing file or one smaller than C<$MIN_SIZE>.
168  
169 Side Effects: reads the file.
170  
171 Usage:
172  
173 my $signature = App::FileSync::Delta::signature($abs) or return 0;
174  
175 =head3 EXAMPLE
176  
177 my $sig = App::FileSync::Delta::signature('/tmp/big.iso');
178 printf "%d blocks of %d bytes\n", scalar @{ $sig->{blocks} }, $sig->{blocklen} if $sig;
179  
180 =head3 API SPECIFICATION
181  
182 =head4 INPUT
183  
184 [
185 { name => 'path', type => 'string', optional => 1 },
186 { name => 'block', type => 'integer', min => 1, optional => 1 },
187 ]
188  
189 =head4 OUTPUT
190  
191 { type => 'hashref', optional => 1 }
192  
193 =head3 MESSAGES
194  
195 Key Meaning Resolution
196 io.read the file cannot be read check permissions
197  
198 =head3 FORMAL SPECIFICATION
199  
200 signature(p, b) = ⊥ if p ∉ dom FS ∨ #FS(p) < MIN_SIZE
201 = ⟨size ↦ #F, blocklen ↦ b,
202 blocks ↦ ⟨(weak(F[i]), sha256(F[i])) | i ∈ 0 .. ⌊#F / b⌋ − 1⟩⟩
203 where F = FS(p), F[i] = bytes i×b .. (i+1)×b − 1
204  
205 weak(B) = 2¹⁶ × (s₂ mod 2¹⁶) + (s₁ mod 2¹⁶)
206 where s₁ = Σ { B[i] | i ∈ 0 .. #B − 1 }
207 s₂ = Σ { (#B − i) × B[i] | i ∈ 0 .. #B − 1 }
208 = Σ { Σ { B[j] | j ∈ 0 .. k } | k ∈ 0 .. #B − 1 }
209  
210 =cut
211  
212 15 ▶sub signature {
Subroutine signature: called CC=8 SCAR=22.1
Pod documented
213 15 my ($path, $block) = @_;
214  
215 15 ▶ return undef unless defined $path && length $path && -f $path; ## no critic (Subroutines::ProhibitExplicitReturnUndef)
Branch: 1 branch
BranchTrueFalseTotal
unless defined $path and length $path and -f $path 0 15 15
Condition33%2/6
defined $path and length $path and -f $path
!ll&&!rl&&r
0015
defined $path and length $path
!ll&&!rl&&r
0015
MC/DC0%0/3
defined $path and length $path and -f $path
defined $path length $path -f $path
Truth table25%1/4
A and B and C
A= defined $pathB= length $pathC= -f $path
ABCresult
0XX0
10X0
1100
1111
216 15 my $size = -s _;
217 15 ▶ return undef unless $size >= $MIN_SIZE; ## no critic (Subroutines::ProhibitExplicitReturnUndef)
Branch: 1 branch
BranchTrueFalseTotal
unless $size >= $App::FileSync::Delta::MIN_SIZE 0 15 15
218  
219 15 ▶ $block = block_size($size) unless defined $block && $block > 0;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $block and $block > 0 6 9 15
Condition66%2/3
defined $block and $block > 0
!ll&&!rl&&r
609
MC/DC50%1/2
defined $block and $block > 0
defined $block $block > 0
Truth table66%2/3
A and B
A= defined $blockB= $block > 0
ABresult
0X0
100
111
220  
221 15 my $fh = open_file($path, '<');
222 15 my @blocks;
223 15 for (1 .. int($size / $block)) {
224 1937 my $data = read_exact($fh, $block, $path);
225 1937 push @blocks, [ $weak->($data), Digest::SHA::sha256($data) ];
226 }
227 15 close $fh;
228  
229 15 return { size => $size, blocklen => $block, blocks => \@blocks };
230 }
231  
232 =head2 encode_signature
233  
234 Documented with L</decode_signature> below.
235  
236 =head2 decode_signature
237  
238 Purpose: put a signature's blocks on the wire and take them off again.
239  
240 Args: C<encode_signature($signature)>; C<decode_signature($bytes, $count)>.
241  
242 Returns: the encoded bytes (36 per block: a big-endian weak sum then the
243 32-byte SHA-256); the decoded arrayref of C<[ weak, strong ]> pairs.
244  
245 Side Effects: none.
246  
247 Usage:
248  
249 my $bytes = App::FileSync::Delta::encode_signature($signature);
250 my $blocks = App::FileSync::Delta::decode_signature($bytes, $count);
251  
252 =head3 EXAMPLE
253  
254 my $blocks = App::FileSync::Delta::decode_signature(
255 App::FileSync::Delta::encode_signature($sig), scalar @{ $sig->{blocks} });
256  
257 =head3 API SPECIFICATION
258  
259 =head4 INPUT
260  
261 [
262 { name => 'bytes', type => 'string', optional => 1 },
263 { name => 'count', type => 'integer', min => 0, optional => 1 },
264 ]
265  
266 =head4 OUTPUT
267  
268 { type => 'arrayref' }
269  
270 =head3 MESSAGES
271  
272 Key Meaning Resolution
273 delta.bad_count the block count is not a number a peer bug; resync with --no-delta
274 delta.bad_length the bytes do not match the count a peer bug; resync with --no-delta
275  
276 =head3 FORMAL SPECIFICATION
277  
278 encode(⟨(w₁,s₁), …, (wₙ,sₙ)⟩) = be32(w₁) ⁀ s₁ ⁀ … ⁀ be32(wₙ) ⁀ sₙ
279 decode(encode(bs), #bs) = bs
280 pre decode: #bytes = 36 × count
281  
282 =cut
283  
284 3 ▶sub encode_signature {
Subroutine encode_signature: called CC=2 SCAR=7.0
Pod documented
285 3 my ($signature) = @_;
286  
287 3 ▶ return join '', map { pack('N', $_->[0]) . $_->[1] } @{ $signature->{blocks} || [] };
Condition50%1/2
$signature->{'blocks'} || []
l!l
30
MC/DC0%0/1
$signature->{'blocks'} || []
$signature->{'blocks'}
Truth table50%1/2
A
A= $signature->{'blocks'}
Aresult
11
00
288 }
289  
290 4 ▶sub decode_signature {
Subroutine decode_signature: called CC=5 SCAR=16.4
Pod documented
291 4 my ($bytes, $count) = @_;
292  
293 4 ▶ $count = 0 unless defined $count;
Branch: 1 branch
BranchTrueFalseTotal
unless defined $count 0 4 4
294 4 ▶ throw('delta.bad_count', { count => $count }) unless $count =~ /\A\d+\z/;
Branch: 1 branch
BranchTrueFalseTotal
unless $count =~ /\A\d+\z/ 0 4 4
295  
296 4 ▶ my $length = defined $bytes ? length $bytes : 0;
Branch: 1 branch
BranchTrueFalseTotal
defined $bytes ? : 4 0 4
297 4 ▶ throw('delta.bad_length', { length => $length, expected => $count * $RECORD_BYTES })
Branch: 1 branch
BranchTrueFalseTotal
unless $length == $count * $RECORD_BYTES 1 3 4
298 unless $length == $count * $RECORD_BYTES;
299  
300 my @blocks = map {
301 3 my $record = substr($bytes, $_ * $RECORD_BYTES, $RECORD_BYTES);
302 72 [ unpack('N', substr($record, 0, $WEAK_BYTES)), substr($record, $WEAK_BYTES, $STRONG_BYTES) ];
303 } 0 .. $count - 1;
304  
305 3 return \@blocks;
306 }
307  
308 =head2 diff
309  
310 Purpose: write the delta that turns the receiver's file into C<$path>.
311  
312 Args: C<$path> (the new content), C<$signature> (of what the receiver has;
313 C<blocklen> and C<blocks> are used), C<$out> (a writable handle).
314  
315 Returns: C<{ literal, copy, ops }>: bytes sent literally, bytes copied, and
316 records written, so the caller can decide whether the delta beats the file.
317  
318 Side Effects: reads C<$path>; writes copy and literal records to C<$out>.
319  
320 Usage:
321  
322 my $stats = App::FileSync::Delta::diff($abs, $signature, $spool);
323  
324 =head3 EXAMPLE
325  
326 open my $spool, '+>', undef;
327 my $stats = App::FileSync::Delta::diff('/tmp/new.bin', $sig, $spool);
328 printf "%d literal bytes in %d records\n", $stats->{literal}, $stats->{ops};
329  
330 =head3 API SPECIFICATION
331  
332 =head4 INPUT
333  
334 [
335 { name => 'path', type => 'string', min => 1 },
336 { name => 'signature', type => 'hashref' },
337 { name => 'out', type => 'handle' },
338 ]
339  
340 =head4 OUTPUT
341  
342 {
343 type => 'hashref',
344 schema => {
345 literal => { type => 'integer', min => 0 },
346 copy => { type => 'integer', min => 0 },
347 ops => { type => 'integer', min => 0 },
348 },
349 }
350  
351 =head3 MESSAGES
352  
353 Key Meaning Resolution
354 delta.no_output no output handle a caller bug
355 delta.no_block the signature has no block length a peer bug
356 delta.write the delta cannot be written check space for the spool
357 io.read the new file cannot be read check permissions
358  
359 =head3 FORMAL SPECIFICATION
360  
361 let R = records written to out
362 apply(old, R) = FS(path) (correctness)
363 literal = Σ { #l | L(l) ∈ R } ; copy = Σ { n | C(o, n) ∈ R } ; ops = #R
364 literal + copy = #FS(path)
365  
366 =head3 PSEUDOCODE
367  
368 index the receiver's blocks by weak checksum
369 while the next full block equals the receiver's block at the same index:
370 emit a copy of it (no rolling needed for an unchanged prefix)
371 read up to SCAN_LIMIT more bytes into a window buffer
372 slide a one-block window through the buffer:
373 if its weak sum is indexed and the strong hash matches a block:
374 emit a copy, jump a whole block
375 else: add one byte to the literal run, roll the sums forward one byte
376 flush the rest of the buffer and the unscanned tail as literals
377  
378 =cut
379  
380 8 ▶sub diff {
Subroutine diff: called CC=5 SCAR=16.7
Pod documented
381 8 my ($path, $signature, $out) = @_;
382  
383 8 ▶ throw('delta.no_output') unless $out;
Branch: 1 branch
BranchTrueFalseTotal
unless $out 0 8 8
384 8 ▶ my $block = $signature->{blocklen} or throw('delta.no_block');
Branch: 1 branch
BranchTrueFalseTotal
my $block = $signature->{"blocklen"} or throw("delta.no_block") 8 0 8
385 8 ▶ my $blocks = $signature->{blocks} || [];
Condition50%1/2
$signature->{'blocks'} || []
l!l
80
MC/DC0%0/1
$signature->{'blocks'} || []
$signature->{'blocks'}
Truth table50%1/2
A
A= $signature->{'blocks'}
Aresult
11
00
386  
387 8 my $fh = open_file($path, '<');
388 8 my $state = {
389 out => $out,
390 path => $path,
391 block => $block,
392 literal => '',
393 stats => { literal => 0, copy => 0, ops => 0 },
394 };
395  
396 8 my $pending = _match_prefix($state, $fh, $blocks, -s $path);
397 8 my $buffer = _fill_window($fh, $pending, $SCAN_LIMIT + $block, $path);
398 8 _rolling_scan($state, $buffer, $blocks);
399  
400 # Everything past the scanned window goes literally.
401 # length(), not truth: a final chunk of "0" is still data.
402 8 ▶ while (length(my $chunk = _read_some($fh, $LITERAL, $path))) {
Branch: 1 branch
BranchTrueFalseTotal
if (length(my $chunk = _read_some($fh, $App::FileSync::Delta::LITERAL, $path))) 0 8 8
403 0 _add_literal($state, $chunk);
404 }
405 8 _flush($state);
406 8 close $fh;
407  
408 8 return $state->{stats};
409 }
410  
411 =head2 write_copy
412  
413 Documented with L</write_literal> below.
414  
415 =head2 write_literal
416  
417 Purpose: write one delta record.
418  
419 Args: C<write_copy($out, $offset, $length)>; C<write_literal($out, $bytes)>
420 (an empty literal writes nothing).
421  
422 Returns: 1.
423  
424 Side Effects: writes to C<$out>.
425  
426 Usage:
427  
428 App::FileSync::Delta::write_copy($spool, $offset, $length);
429 App::FileSync::Delta::write_literal($spool, $bytes);
430  
431 =head3 EXAMPLE
432  
433 App::FileSync::Delta::write_literal($out, "new text\n");
434  
435 =head3 API SPECIFICATION
436  
437 =head4 INPUT
438  
439 [
440 { name => 'out', type => 'handle' },
441 { name => 'offset', type => 'integer', min => 0 },
442 { name => 'length', type => 'integer', min => 0 },
443 ]
444  
445 =head4 OUTPUT
446  
447 { type => 'integer', min => 1, max => 1 }
448  
449 =head3 MESSAGES
450  
451 Key Meaning Resolution
452 delta.write the record cannot be written check space for the spool
453  
454 =head3 FORMAL SPECIFICATION
455  
456 write_copy(o, n): out' = out ⁀ "C" ⁀ be32(o) ⁀ be32(n)
457 write_literal(b): out' = out ⁀ "L" ⁀ be32(#b) ⁀ b if b ≠ ⟨⟩
458  
459 =cut
460  
461 672 ▶sub write_copy {
Subroutine write_copy: called CC=2 SCAR=7.0
Pod documented
462 672 my ($out, $offset, $length) = @_;
463  
464 672 ▶ print {$out} $COPY . pack('NN', $offset, $length) or throw('delta.write', { error => "$!" });
Branch: 1 branch
BranchTrueFalseTotal
print {$out;} $COPY . pack("NN", $offset, $length) or throw("delta.write", {"error", "$!"}) 672 0 672
465 672 return 1;
466 }
467  
468 1618 ▶sub write_literal {
Subroutine write_literal: called CC=4 SCAR=15.2
Pod documented
469 1618 my ($out, $bytes) = @_;
470  
471 1618 ▶ if (defined $bytes && length $bytes) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $bytes and length $bytes) 1618 0 1618
Condition33%1/3
defined $bytes and length $bytes
!ll&&!rl&&r
001618
MC/DC0%0/2
defined $bytes and length $bytes
defined $bytes length $bytes
Truth table33%1/3
A and B
A= defined $bytesB= length $bytes
ABresult
0X0
100
111
472 1618 ▶ print {$out} $LIT . pack('N', length $bytes) . $bytes or throw('delta.write', { error => "$!" });
Branch: 1 branch
BranchTrueFalseTotal
print {$out;} $LIT . pack("N", length $bytes) . $bytes or throw("delta.write", {"error", "$!"}) 1618 0 1618
473 }
474 1618 return 1;
475 }
476  
477 =head2 read_op
478  
479 Purpose: read the next delta record.
480  
481 Args: C<$in>, a handle positioned at a record.
482  
483 Returns: C<('copy', $offset, $length)>, C<('literal', $bytes)>, or the empty
484 list at the end. A list because callers loop with
485 C<while (my ($type, @rest) = read_op($in))>.
486  
487 Side Effects: advances C<$in>.
488  
489 Usage:
490  
491 while (my ($type, @rest) = App::FileSync::Delta::read_op($spool)) { ... }
492  
493 =head3 EXAMPLE
494  
495 my ($type, $offset, $length) = App::FileSync::Delta::read_op($spool);
496  
497 =head3 API SPECIFICATION
498  
499 =head4 INPUT
500  
501 [ { name => 'in', type => 'handle' } ]
502  
503 =head4 OUTPUT
504  
505 { type => 'arrayref' }
506  
507 =head3 MESSAGES
508  
509 Key Meaning Resolution
510 delta.read the delta cannot be read check the spool
511 delta.bad_record an unknown record type a peer bug; resync with --no-delta
512 io.short the delta ends mid-record a peer bug; resync with --no-delta
513  
514 =head3 FORMAL SPECIFICATION
515  
516 read_op("C" ⁀ be32(o) ⁀ be32(n) ⁀ rest) = (copy, o, n)
517 read_op("L" ⁀ be32(k) ⁀ b ⁀ rest) = (literal, b) where #b = k
518 read_op(⟨⟩) = ⟨⟩
519  
520 =cut
521  
522 4478 ▶sub read_op {
Subroutine read_op: called CC=6 SCAR=18.2
Pod documented
523 4478 my ($in) = @_;
524  
525 4478 my $type = _read_some($in, 1, 'delta', 'delta.read');
526 4478 ▶ return () unless length $type;
Branch: 1 branch
BranchTrueFalseTotal
unless length $type 8 4470 4478
527 4470 ▶ throw('delta.bad_record', { type => $type }) unless $type eq $COPY || $type eq $LIT;
Branch: 1 branch
BranchTrueFalseTotal
unless $type eq $COPY or $type eq $LIT 0 4470 4470
Condition66%2/3
$type eq $COPY or $type eq $LIT
l!l&&r!l&&!r
124632240
MC/DC0%0/2
$type eq $COPY or $type eq $LIT
$type eq $COPY $type eq $LIT
Truth table66%2/3
A or B
A= $type eq $COPYB= $type eq $LIT
ABresult
1X1
011
000
528  
529 4470 ▶ return ('copy', unpack('NN', read_exact($in, $COPY_HEADER, 'delta'))) if $type eq $COPY;
Branch: 1 branch
BranchTrueFalseTotal
if $type eq $COPY 1246 3224 4470
530  
531 3224 my $length = unpack('N', read_exact($in, $LIT_HEADER, 'delta'));
532 3224 ▶ return ('literal', $length ? read_exact($in, $length, 'delta') : '');
Branch: 1 branch
BranchTrueFalseTotal
$length ? : 3224 0 3224
533 }
534  
535 =head2 apply
536  
537 Purpose: rebuild a file from the old copy and a spooled delta.
538  
539 Args: C<$old_path>, C<$in> (the delta), C<$out> (where the new content goes).
540  
541 Returns: C<{ size }>, the bytes written.
542  
543 Side Effects: reads C<$old_path> and C<$in>; writes C<$out>.
544  
545 Usage:
546  
547 my $result = App::FileSync::Delta::apply($old, $spool, $out);
548  
549 =head3 EXAMPLE
550  
551 open my $out, '>', '/tmp/rebuilt.bin';
552 App::FileSync::Delta::apply('/tmp/old.bin', $spool, $out);
553  
554 =head3 API SPECIFICATION
555  
556 =head4 INPUT
557  
558 [
559 { name => 'old_path', type => 'string', min => 1 },
560 { name => 'in', type => 'handle' },
561 { name => 'out', type => 'handle' },
562 ]
563  
564 =head4 OUTPUT
565  
566 { type => 'hashref', schema => { size => { type => 'integer', min => 0 } } }
567  
568 =head3 MESSAGES
569  
570 Key Meaning Resolution
571 io.read the old file cannot be read check permissions
572 io.seek a copy points outside the file the delta does not fit this file
573 delta.write_restored the output cannot be written check space
574  
575 =head3 FORMAL SPECIFICATION
576  
577 apply(old, R) = ⁀/ ⟨ bytes(r) | r ← R ⟩
578 where bytes(C(o, n)) = FS(old)[o .. o + n − 1], bytes(L(b)) = b
579  
580 =cut
581  
582 4 ▶sub apply {
Subroutine apply: called CC=4 SCAR=13.9
Pod documented
583 4 my ($old_path, $in, $out) = @_;
584  
585 4 my $old = open_file($old_path, '<');
586 4 my $written = 0;
587  
588 4 ▶ while (my ($type, @rest) = read_op($in)) {
Branch: 1 branch
BranchTrueFalseTotal
if (() = read_op($in)) 2238 4 2242
589 2238 ▶ my $bytes = $type eq 'copy' ? _copy_from($old, @rest, $old_path) : $rest[0];
Branch: 1 branch
BranchTrueFalseTotal
$type eq 'copy' ? : 626 1612 2238
590 2238 ▶ print {$out} $bytes or throw('delta.write_restored', { error => "$!" });
Branch: 1 branch
BranchTrueFalseTotal
print {$out;} $bytes or throw("delta.write_restored", {"error", "$!"}) 2238 0 2238
591 2238 $written += length $bytes;
592 }
593  
594 4 close $old;
595 4 return { size => $written };
596 }
597  
598 =head2 read_exact
599  
600 Purpose: read exactly C<$length> bytes.
601  
602 Args: C<$fh>, C<$length>, C<$what> (named in errors).
603  
604 Returns: the bytes.
605  
606 Side Effects: advances C<$fh>.
607  
608 Usage:
609  
610 my $data = App::FileSync::Delta::read_exact($fh, $block, $path);
611  
612 =head3 EXAMPLE
613  
614 my $header = App::FileSync::Delta::read_exact($spool, 8, 'delta');
615  
616 =head3 API SPECIFICATION
617  
618 =head4 INPUT
619  
620 [
621 { name => 'fh', type => 'handle' },
622 { name => 'length', type => 'integer', min => 0 },
623 { name => 'what', type => 'string' },
624 ]
625  
626 =head4 OUTPUT
627  
628 { type => 'string' }
629  
630 =head3 MESSAGES
631  
632 Key Meaning Resolution
633 io.read the read failed check the device
634 io.short fewer bytes than required the file was truncated
635  
636 =head3 FORMAL SPECIFICATION
637  
638 read_exact(fh, n, w) = take(n, rest(fh)) if #rest(fh) ≥ n
639 ↑ io.short otherwise
640  
641 =cut
642  
643 10451 ▶sub read_exact {
Subroutine read_exact: called CC=3 SCAR=11.0
Pod documented
644 10451 my ($fh, $length, $what) = @_;
645  
646 10451 my $bytes = '';
647 10451 ▶ while (length($bytes) < $length) {
Branch: 1 branch
BranchTrueFalseTotal
if (length $bytes < $length) 10451 10450 20901
648 10451 my $chunk = _read_some($fh, $length - length($bytes), $what);
649 10451 ▶ throw('io.short', { path => $what }) unless length $chunk;
Branch: 1 branch
BranchTrueFalseTotal
unless length $chunk 1 10450 10451
650 10450 $bytes .= $chunk;
651 }
652  
653 10450 return $bytes;
654 }
655  
656 # _read_some
657 # Purpose: one read() that reports failure with a catalogued message.
658 # Entry: $fh is readable; $want > 0.
659 # Exit: returns the bytes read ('' at end of file).
660 # Side effects: advances $fh; raises $key (default io.read) on error.
661 14952 ▶sub _read_some :Private {
Subroutine _read_some: called CC=4 SCAR=15.2
662 14952 my ($fh, $want, $what, $key) = @_;
663  
664 14952 my $chunk;
665 14952 ▶ eval { read($fh, $chunk, $want); 1 }
Branch: 1 branch
BranchTrueFalseTotal
eval { do { &App::FileSync::Delta::read($fh, \$chunk, $want); 1 } } or throw($key || "io.read", {"path", $what, "error", os_error($@)}) 14952 0 14952
Condition0%0/2
$key || 'io.read'
l!l
00
MC/DC0%0/1
$key || 'io.read'
$key
Truth table0%0/2
A
A= $key
Aresult
11
00
666 or throw($key || 'io.read', { path => $what, error => os_error($@) });
667  
668 14952 ▶ return defined $chunk ? $chunk : '';
Branch: 1 branch
BranchTrueFalseTotal
defined $chunk ? : 14952 0 14952
669 326 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.0
670  
671 # _copy_from
672 # Purpose: the bytes a copy record refers to in the old file.
673 # Entry: $old is the old file's handle.
674 # Exit: returns $length bytes from $offset.
675 # Side effects: moves $old's position; raises io.seek or io.short.
676 626 ▶sub _copy_from :Private {
Subroutine _copy_from: called CC=3 SCAR=11.3
677 626 my ($old, $offset, $length, $old_path) = @_;
678  
679 626 ▶ eval { seek($old, $offset, 0); 1 }
Branch: 1 branch
BranchTrueFalseTotal
eval { do { &App::FileSync::Delta::seek($old, $offset, 0); 1 } } or throw("io.seek", {"path", $old_path, "error", os_error($@)}) 626 0 626
680 or throw('io.seek', { path => $old_path, error => os_error($@) });
681  
682 626 ▶ return $length ? read_exact($old, $length, $old_path) : '';
Branch: 1 branch
BranchTrueFalseTotal
$length ? : 626 0 626
683 326 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.0
684  
685 # _match_prefix
686 # Purpose: copy the unchanged leading blocks without rolling a checksum.
687 # Entry: $fh is at offset 0 of the new file; $size is its length.
688 # Exit: returns the first block that did not match ('' if none), which
689 # the rolling scan must start from.
690 # Side effects: writes copy records; advances $fh.
691 8 ▶sub _match_prefix :Private {
Subroutine _match_prefix: called CC=4 SCAR=13.9
692 8 my ($state, $fh, $blocks, $size) = @_;
693  
694 8 my $block = $state->{block};
695 8 my $offset = 0;
696  
697 # The leading blocks are usually untouched: compare them directly, which
698 # avoids scanning terabyte-sized prefixes a byte at a time.
699 8 for my $index (0 .. $#{$blocks}) {
700 58 ▶ last if $offset + $block > $size;
Branch: 1 branch
BranchTrueFalseTotal
if $offset + $block > $size 1 57 58
701 57 my $data = read_exact($fh, $block, $state->{path});
702 57 ▶ return $data unless Digest::SHA::sha256($data) eq $blocks->[$index][1];
Branch: 1 branch
BranchTrueFalseTotal
unless &Digest::SHA::sha256($data) eq $blocks->[$index][1] 6 51 57
703  
704 51 _add_copy($state, $offset, $block);
705 51 $offset += $block;
706 }
707  
708 2 return '';
709 326 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.0
710  
711 # _fill_window
712 # Purpose: read the region the rolling scan examines into one string.
713 # Entry: $pending is data already read; $want the window size.
714 # Exit: returns up to $want bytes (less at end of file).
715 # Side effects: advances $fh. One string lets the loop use vec() without
716 # copying.
717 8 ▶sub _fill_window :Private {
Subroutine _fill_window: called CC=3 SCAR=11.0
718 8 my ($fh, $pending, $want, $path) = @_;
719  
720 8 my $buffer = $pending;
721 8 ▶ while (length($buffer) < $want) {
Branch: 1 branch
BranchTrueFalseTotal
if (length $buffer < $want) 15 0 15
722 15 my $chunk = _read_some($fh, $want - length($buffer), $path);
723 15 ▶ last unless length $chunk;
Branch: 1 branch
BranchTrueFalseTotal
unless length $chunk 8 7 15
724 7 $buffer .= $chunk;
725 }
726  
727 8 return $buffer;
728 326 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.0
729  
730 # _rolling_scan
731 # Purpose: find the receiver's blocks anywhere in the window.
732 # Entry: $buffer is the window; $blocks the receiver's signature.
733 # Exit: returns 1.
734 # Side effects: writes copy and literal records for the whole buffer.
735 8 ▶sub _rolling_scan :Private {
Subroutine _rolling_scan: called CC=13 SCAR=25.7
736 8 my ($state, $buffer, $blocks) = @_;
737  
738 8 my $block = $state->{block};
739 8 my $limit = length($buffer) - $block;
740  
741 # Shorter than one block: nothing can match.
742 8 ▶ if ($limit < 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($limit < 0) 2 6 8
743 2 _add_literal($state, $buffer);
744 2 return 1;
745 }
746  
747 6 my %by_weak;
748 6 push @{ $by_weak{ $blocks->[$_][0] } }, [ $_, $blocks->[$_][1] ] for 0 .. $#{$blocks};
749  
750 # A one-bit-per-value table of the low halves (a) of the receiver's weak
751 # sums, as rsync keeps. Most windows fail this vec() test, which skips
752 # turning the sum into a string for the hash lookup.
753 6 my $tags = '';
754 6 vec($tags, $_->[0] & $HALF, 1) = 1 for @{$blocks};
755  
756 # This loop runs once per byte that matches nothing, so its body calls no
757 # sub (the :Private wrapper costs about 1.4us a call). Unmatched bytes are
758 # not queued one at a time: $run_start marks where the current literal run
759 # began, and the run is queued in one piece when a match or the end of the
760 # buffer closes it. $a and $b are always already masked.
761 6 ▶ my $last = $limit > $SCAN_LIMIT ? $SCAN_LIMIT : $limit;
Branch: 1 branch
BranchTrueFalseTotal
$limit > $App::FileSync::Delta::SCAN_LIMIT ? : 0 6 6
762 6 my ($a, $b) = $weak_parts->(substr($buffer, 0, $block));
763 6 my ($position, $run_start) = (0, 0);
764  
765 6 ▶ while ($position <= $last) {
Branch: 1 branch
BranchTrueFalseTotal
if ($position <= $last) 386418 6 386424
766 386418 ▶ if (vec($tags, $a, 1) and my $candidates = $by_weak{ ($b << $HALF_BITS) | $a }) {
Branch: 1 branch
BranchTrueFalseTotal
if (vec $tags, $a, 1 and my $candidates = $by_weak{$b << $HALF_BITS | $a}) 621 385797 386418
Condition100%3/3
vec $tags, $a, 1 and my $candidates = $by_weak{$b << $HALF_BITS | $a}
!ll&&!rl&&r
101428284369621
MC/DC100%2/2
vec $tags, $a, 1 and my $candidates = $by_weak{$b << $HALF_BITS | $a}
vec $tags, $a, 1 my $candidates = $by_weak{$b << $HALF_BITS | $a}
Truth table100%3/3
A and B
A= vec $tags, $a, 1B= my $candidates = $by_weak{$b << $HALF_BITS | $a}
ABresult
0X0
100
111
767 621 my $winner = _strong_match($candidates, $buffer, $position, $block);
768 621 ▶ if (defined $winner) {
Branch: 1 branch
BranchTrueFalseTotal
if (defined $winner) 621 0 621
769 621 ▶ _add_literal($state, substr($buffer, $run_start, $position - $run_start)) if $position > $run_start;
Branch: 1 branch
BranchTrueFalseTotal
if $position > $run_start 7 614 621
770 621 _add_copy($state, $winner * $block, $block);
771 621 $position += $block;
772 621 $run_start = $position;
773 621 ▶ ($a, $b) = $weak_parts->(substr($buffer, $position, $block)) if $position <= $last;
Branch: 1 branch
BranchTrueFalseTotal
if $position <= $last 618 3 621
774 621 next;
775 }
776 }
777  
778 # Roll the window forward one byte, unless this was the last full
779 # window in the buffer. The byte entering the window is the one just
780 # past its end.
781 385797 ▶ if ($position < $last) {
Branch: 1 branch
BranchTrueFalseTotal
if ($position < $last) 385794 3 385797
782 385794 my $out_byte = vec($buffer, $position, $BYTE_BITS);
783 385794 my $in_byte = vec($buffer, $position + $block, $BYTE_BITS);
784 385794 $a = ($a - $out_byte + $in_byte) & $HALF;
785 385794 $b = ($b - $block * $out_byte + $a) & $HALF;
786 }
787 385797 $position++;
788 }
789  
790 # The open run and everything past the last full window.
791 6 ▶ _add_literal($state, substr($buffer, $run_start)) if $run_start < length($buffer);
Branch: 1 branch
BranchTrueFalseTotal
if $run_start < length $buffer 6 0 6
792 6 return 1;
793 326 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.0
794  
795 # _strong_match
796 # Purpose: confirm a weak-checksum hit with the strong hash.
797 # Entry: $candidates are the [ index, sha256 ] pairs whose weak sum
798 # matched the window at $position (the caller looks them up, so
799 # a byte with no weak hit costs no call).
800 # Exit: returns the matching block index, or undef.
801 # Side effects: none.
802 621 ▶sub _strong_match :Private {
Subroutine _strong_match: called CC=2 SCAR=7.0
803 621 my ($candidates, $buffer, $position, $block) = @_;
804  
805 621 my $strong = Digest::SHA::sha256(substr($buffer, $position, $block));
806 621 my ($hit) = grep { $_->[1] eq $strong } @{$candidates};
807  
808 621 ▶ return $hit ? $hit->[0] : undef;
Branch: 1 branch
BranchTrueFalseTotal
$hit ? : 621 0 621
809 326 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.0
810  
811 # _add_copy
812 # Purpose: emit a copy record, flushing any pending literal first.
813 # Entry: $offset/$length name bytes in the receiver's file.
814 # Exit: returns 1.
815 # Side effects: writes to the output; updates the stats.
816 672 ▶sub _add_copy :Private {
Subroutine _add_copy: called CC=1 SCAR=0.0
817 672 my ($state, $offset, $length) = @_;
818  
819 672 _flush($state);
820 672 write_copy($state->{out}, $offset, $length);
821 672 $state->{stats}{copy} += $length;
822 672 $state->{stats}{ops}++;
823  
824 672 return 1;
825 326 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.0
826  
827 # _add_literal
828 # Purpose: queue literal bytes, writing a record for each $LITERAL bytes
829 # that accumulate.
830 # Entry: $bytes may be empty, or a run of many megabytes.
831 # Exit: returns 1; fewer than $LITERAL bytes stay queued.
832 # Side effects: may write to the output. A long run is cut into $LITERAL
833 # records by offset, so the run is copied once, not once per
834 # record.
835 15 ▶sub _add_literal :Private {
Subroutine _add_literal: called CC=2 SCAR=6.9
836 15 my ($state, $bytes) = @_;
837  
838 15 my $pending = $state->{literal} . $bytes;
839 15 my $offset = 0;
840 15 ▶ while (length($pending) - $offset >= $LITERAL) {
Branch: 1 branch
BranchTrueFalseTotal
if (length($pending) - $offset >= $App::FileSync::Delta::LITERAL) 1604 15 1619
841 1604 $state->{literal} = substr($pending, $offset, $LITERAL);
842 1604 _flush($state);
843 1604 $offset += $LITERAL;
844 }
845 15 $state->{literal} = substr($pending, $offset);
846  
847 15 return 1;
848 326 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.0
849  
850 # _flush
851 # Purpose: write the queued literal bytes as one record.
852 # Entry: $state->{literal} may be empty.
853 # Exit: returns 1.
854 # Side effects: writes to the output; updates the stats.
855 2284 ▶sub _flush :Private {
Subroutine _flush: called CC=2 SCAR=6.9
856 2284 my ($state) = @_;
857  
858 2284 my $length = length $state->{literal};
859 2284 ▶ if ($length) {
Branch: 1 branch
BranchTrueFalseTotal
if ($length) 1618 666 2284
860 1618 write_literal($state->{out}, $state->{literal});
861 1618 $state->{stats}{literal} += $length;
862 1618 $state->{stats}{ops}++;
863 1618 $state->{literal} = '';
864 }
865  
866 2284 return 1;
867 326 ▶}
Subroutine BEGIN: called CC=1 SCAR=0.0
868  
869 326 1;
870  
871 __END__
« blib/lib/App/FileSync/I18N.pm ↑ Summary blib/lib/App/FileSync/Platform.pm »