rsync-delta-demo

Essential delta-transfer idea behind rsync.

NOTE:This project is not rsync and is not compatible with the rsync wire protocol.

Idea

Suppose a receiver already has an older source file, while a sender has a modified target file.

Instead of transferring the entire target, this demo:

1. splits the source into fixed-size blocks;
2. calculates a cheap rolling checksum and SHA-256 for each source block;
3. scans the target byte-by-byte;
4. uses rolling checksum updates to locate candidate shifted blocks;
5. verifies candidates with SHA-256;
6. emits:
   • COPY(block) for bytes already available in the source;
   • DATA(bytes) for new/changed bytes;
7. reconstructs the target from the source and delta;
8. verifies exact byte equality.

Why two checksums?

The rolling checksum is intentionally cheap and can be updated in O(1) when the scan window moves one byte.

It is only a filter: weak checksums can collide.

SHA-256 provides strong verification, but it is more expensive. The scanner therefore calculates target SHA-256 only when the weak checksum finds one or more candidate source blocks.

Conceptually:

target window
    │
    ├─ weak checksum has no source candidate ──> slide by one byte
    │
    └─ weak checksum has candidate(s)
              │
              └─ SHA-256 once
                    │
                    ├─ strong match ──> COPY(block)
                    └─ no match ─────> slide by one byte

Commands

Generate a delta

cargo run --release -- diff \
  examples/source.txt \
  examples/target.txt \
  --block-size 16 \
  --delta artifacts/example.rsdd \
  --html artifacts/report.html \
  --verbose

Inspect a delta

cargo run --release -- inspect artifacts/example.rsdd

Reconstruct the target

cargo run --release -- apply \
  examples/source.txt \
  artifacts/example.rsdd \
  artifacts/reconstructed.txt

Verify externally:

cmp examples/target.txt artifacts/reconstructed.txt

Compare block sizes

cargo run --release -- benchmark \
  examples/source.txt \
  examples/target.txt \
  --blocks 4,8,16,32,64

Metrics

The demo reports:

• source size;
• target size;
• block size;
• source block count;
• COPY/DATA operation counts;
• reused bytes;
• literal/transferred bytes;
• matching percentage;
• actual serialized delta size;
• source SHA-256 operations;
• target SHA-256 operations;
• weak candidate hits;
• rolling checksum updates;
• timings;
• verification status.

HTML visualization

diff --html report.html creates a self-contained report showing the target as reused and transferred regions.

The report includes:

• summary metrics;
• target operation strip;
• COPY/DATA legend;
• operation table;
• checksum/hash counters;
• timings.

benchmark --html report.html can additionally include block-size comparison results.

Project layout

src/checksum.rs       rolling weak checksum
src/signature.rs      source block signatures/index
src/scanner.rs        target scan and delta generation
src/delta.rs          core delta models
src/codec.rs          .rsdd binary encoding
src/reconstruct.rs    source + delta reconstruction
src/stats.rs          metrics
src/benchmark.rs      block-size comparison
src/html.rs           self-contained report
src/main.rs           CLI only

Scope

The MVP deliberately does not implement:

• networking;
• directory synchronization;
• metadata/permissions;
• compression;
• encryption;
• remote authentication;
• sparse-file optimization;
• streaming huge files;
• the actual rsync protocol.

The goal is to make the matching algorithm understandable.

Development

cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
cargo test --all-targets
cargo build --release

Reference documentation

• docs/ALGORITHM.md explains the rolling-checksum matching design.
• docs/DELTA_FORMAT.md documents the strict .rsdd binary format.
• docs/CLI_SPEC.md describes commands, options, and output behavior.
• docs/HTML_REPORT.md describes the self-contained visualization.

License

MIT