feat: add delta transfer for incremental sync #22

2026-07-18T20:01:05+02:00

TapTap commented

2026-07-18 20:01:05 +02:00

Implement rsync-style delta transfer using rolling checksums (Adler-32 + xxHash32). When a file exists on both sides but has changed, only the changed blocks are transmitted instead of the entire file.

Changes

New files

src/shared/delta.h / delta.c — Core delta engine (Adler-32, xxHash32, signature generation, rolling checksum delta computation, serialization, application)
src/shared/xxhash.h — Vendored xxHash single-header library
tests/test_delta.h / test_delta.c — 13 unit tests

Modified files

src/shared/protocol.h/.c — New status codes: STATUS_DELTA_SIGNATURE (7), STATUS_DELTA_DATA (8)
src/shared/config.h/.c — Added use_delta, delta_block_size fields; protocol version bumped to 1.2.0
src/shared/file.c — Extended receive_incremental_check() with full delta negotiation
src/client/client_send.c — Extended incremental_check() for delta; added send_delta()
src/client/client_cli.c — Added --delta and --delta-block flags with validation
tests/runner.c — Registered delta test suite

Protocol flow

Client sends STATUS_CHECK + path + size + mtime (existing)
Server compares: if match → STATUS_OK (skip); if delta-eligible → STATUS_DELTA_SIGNATURE + block signature
Client computes rolling checksum delta against signature
If delta < 70% of file size: client sends STATUS_DELTA_DATA + compressed delta
Server applies delta to reconstruct file
If delta not beneficial: client falls back to STATUS_NEXT + whole file

Usage

./build/client --incremental --delta /src user@host:/dst
./build/client -c --incremental --delta /src user@host:/dst  # with compression

Testing

All 8 unit test suites pass (13 new delta tests)
Builds cleanly on all 3 targets (server, client, tests)
CLI validation: --delta requires --incremental, incompatible with -s and -f

Implement rsync-style delta transfer using rolling checksums (Adler-32 + xxHash32). When a file exists on both sides but has changed, only the changed blocks are transmitted instead of the entire file. ## Changes ### New files - `src/shared/delta.h` / `delta.c` — Core delta engine (Adler-32, xxHash32, signature generation, rolling checksum delta computation, serialization, application) - `src/shared/xxhash.h` — Vendored xxHash single-header library - `tests/test_delta.h` / `test_delta.c` — 13 unit tests ### Modified files - `src/shared/protocol.h/.c` — New status codes: STATUS_DELTA_SIGNATURE (7), STATUS_DELTA_DATA (8) - `src/shared/config.h/.c` — Added use_delta, delta_block_size fields; protocol version bumped to 1.2.0 - `src/shared/file.c` — Extended receive_incremental_check() with full delta negotiation - `src/client/client_send.c` — Extended incremental_check() for delta; added send_delta() - `src/client/client_cli.c` — Added --delta and --delta-block flags with validation - `tests/runner.c` — Registered delta test suite ## Protocol flow 1. Client sends STATUS_CHECK + path + size + mtime (existing) 2. Server compares: if match → STATUS_OK (skip); if delta-eligible → STATUS_DELTA_SIGNATURE + block signature 3. Client computes rolling checksum delta against signature 4. If delta < 70% of file size: client sends STATUS_DELTA_DATA + compressed delta 5. Server applies delta to reconstruct file 6. If delta not beneficial: client falls back to STATUS_NEXT + whole file ## Usage ```bash ./build/client --incremental --delta /src user@host:/dst ./build/client -c --incremental --delta /src user@host:/dst # with compression ``` ## Testing - All 8 unit test suites pass (13 new delta tests) - Builds cleanly on all 3 targets (server, client, tests) - CLI validation: --delta requires --incremental, incompatible with -s and -f

TapTap added 1 commit 2026-07-18 20:01:05 +02:00

feat: add delta transfer for incremental sync

CI / build-and-test (push) Successful in 28s

Details

CI / build-and-test (pull_request) Successful in 28s

Details

e16db56580

Implement rsync-style delta transfer using rolling checksums (Adler-32 +
xxHash32). When a file exists on both sides but has changed, only the
changed blocks are transmitted instead of the entire file.

- New status codes: STATUS_DELTA_SIGNATURE, STATUS_DELTA_DATA
- Protocol version bumped to 1.2.0
- Server generates block signature, client computes delta
- Auto-fallback to whole-file when delta >= 70% of file size
- Works with zstd compression on delta stream
- Configurable block size (default 8KB, --delta-block flag)
- 13 unit tests covering hashing, signature roundtrip, delta compute/apply,
  file growth/shrink, and decision logic

TapTap commented

2026-07-18 20:07:40 +02:00

CHANGES REQUESTED — 1 critical performance issue

CRITICAL: `delta_compute` is O(n*m) — not a rolling checksum

delta.c:407-461 — The rolling checksum window advances 1 byte on miss and recomputes both adler32 and xxhash32 from scratch at every position:

if (!matched) {
    i++;  // advance by 1 byte
    // next iteration recomputes adler32(new_data + i, window_len) from scratch
}

Adler-32 is specifically designed as a rolling hash — you can update it in O(1) by subtracting the leaving byte and adding the entering byte. The current implementation defeats this entirely.

Worst case: 100MB file with a 1-byte insertion at position 50MB. After the change, all blocks shift by 1 byte, so every position from 50MB to 100MB fails to match, each recomputing adler32+xxhash32 on 8KB. That's ~50M * 8KB = ~400TB of hash computation.

Fix: Implement a proper rolling adler32 that updates in O(1), and only compute xxhash32 (the strong hash) when adler32 matches. This is the standard rsync technique and reduces the worst case from O(n*m) to O(n + m).

Other findings (non-blocking)

Duplicated delta logic in send_chunk (client_send.c:102-162 vs 125-185): The incremental_check + send_delta pattern is copy-pasted for the sendfile path and the normal path. Should be extracted into a helper.
Deep nesting in receive_incremental_check (file.c:149-1034): The delta handling path is 6+ levels of if/else with 30+ local variable cleanup paths. Functionally correct but hard to maintain. Consider extracting the delta receive logic into a separate function.
delta_should_attempt uses hardcoded DELTA_MAX_FILE_SIZE (256MB). For files larger than 256MB, delta is skipped entirely. May want to make this configurable or raise the limit.
Tests use only 2-4KB files — the O(n*m) bug isn't exercised. Add a test with a 100KB+ file with a small edit to catch the performance regression.

What's good

Correct protocol design (server generates signature, client computes delta)
Proper fallback when delta isn't worthwhile (delta_is_worthwhile at 70% ratio)
Clean serialization/deserialization with proper bounds checking
13 unit tests covering edge cases (identical files, small edits, complete changes, file growth/shrink)
Correct config propagation and validation (delta requires incremental, incompatible with -s/-f)
Vendored xxhash.h is standard practice for single-header libraries

**CHANGES REQUESTED** — 1 critical performance issue ## CRITICAL: `delta_compute` is O(n*m) — not a rolling checksum `delta.c:407-461` — The rolling checksum window advances 1 byte on miss and recomputes **both adler32 and xxhash32 from scratch** at every position: ```c if (!matched) { i++; // advance by 1 byte // next iteration recomputes adler32(new_data + i, window_len) from scratch } ``` Adler-32 is specifically designed as a **rolling hash** — you can update it in O(1) by subtracting the leaving byte and adding the entering byte. The current implementation defeats this entirely. **Worst case**: 100MB file with a 1-byte insertion at position 50MB. After the change, all blocks shift by 1 byte, so **every position from 50MB to 100MB fails to match**, each recomputing adler32+xxhash32 on 8KB. That's ~50M * 8KB = ~400TB of hash computation. **Fix**: Implement a proper rolling adler32 that updates in O(1), and only compute xxhash32 (the strong hash) when adler32 matches. This is the standard rsync technique and reduces the worst case from O(n*m) to O(n + m). --- ## Other findings (non-blocking) 1. **Duplicated delta logic in `send_chunk`** (`client_send.c:102-162` vs `125-185`): The incremental_check + send_delta pattern is copy-pasted for the sendfile path and the normal path. Should be extracted into a helper. 2. **Deep nesting in `receive_incremental_check`** (`file.c:149-1034`): The delta handling path is 6+ levels of if/else with 30+ local variable cleanup paths. Functionally correct but hard to maintain. Consider extracting the delta receive logic into a separate function. 3. **`delta_should_attempt` uses hardcoded `DELTA_MAX_FILE_SIZE`** (256MB). For files larger than 256MB, delta is skipped entirely. May want to make this configurable or raise the limit. 4. **Tests use only 2-4KB files** — the O(n*m) bug isn't exercised. Add a test with a 100KB+ file with a small edit to catch the performance regression. --- ## What's good - Correct protocol design (server generates signature, client computes delta) - Proper fallback when delta isn't worthwhile (`delta_is_worthwhile` at 70% ratio) - Clean serialization/deserialization with proper bounds checking - 13 unit tests covering edge cases (identical files, small edits, complete changes, file growth/shrink) - Correct config propagation and validation (delta requires incremental, incompatible with -s/-f) - Vendored xxhash.h is standard practice for single-header libraries

TapTap added 1 commit 2026-07-19 02:02:31 +02:00

fix: address PR review - rolling adler32, extract helpers, configurable max file size

CI / build-and-test (push) Successful in 29s

Details

CI / build-and-test (pull_request) Successful in 28s

Details

598e4e7514

- Fix rolling adler32: add missing -1 in s2 update formula (was producing
  wrong checksums, causing zero block matches)
- Fix file_send_sendfile signature to match typedef (add unused
  compression_level param)
- Extract receive_delta_file() from receive_incremental_check() to reduce
  nesting depth
- Extract send_file_incremental() helper in client_send.c
- Add delta_max_file_size to Config, serialized over wire
- Add --delta-max CLI flag
- Add test_large_file_delta (200KB) and extra delta_should_attempt cases
- Remove unused pos_in_block variable from delta_compute

TapTap commented

2026-07-19 14:49:10 +02:00

PASS — All review findings addressed. Rolling adler32 is correctly implemented in O(1). Code is clean with extracted helpers. Tests improved with 200KB file case. Ready to merge.

**PASS** — All review findings addressed. Rolling adler32 is correctly implemented in O(1). Code is clean with extracted helpers. Tests improved with 200KB file case. Ready to merge.

TapTap commented

2026-07-19 15:16:57 +02:00

❌ Request: Replace vendored xxhash.h with CMake dependency

src/shared/xxhash.h is 7490 lines vendored, but only XXH32() is used. The project already uses CMake and links external libs (libzstd-dev, libssl-dev), so this should be a proper dependency.

Recommended: FetchContent — pull xxHash at CMake configure time, no system install needed, no 7500-line file in the repo:

include(FetchContent)
FetchContent_Declare(
  xxhash
  GIT_REPOSITORY https://github.com/Cyan4973/xxHash
  GIT_TAG v0.8.3
)
FetchContent_MakeAvailable(xxhash)

# Then link:
target_link_libraries(fastsync xxhash::xxhash)

In delta.c, replace the vendored include with:

#include <xxhash.h>

This keeps the repo clean and makes version management straightforward.

## ❌ Request: Replace vendored xxhash.h with CMake dependency `src/shared/xxhash.h` is 7490 lines vendored, but only `XXH32()` is used. The project already uses CMake and links external libs (`libzstd-dev`, `libssl-dev`), so this should be a proper dependency. **Recommended: `FetchContent`** — pull xxHash at CMake configure time, no system install needed, no 7500-line file in the repo: ```cmake include(FetchContent) FetchContent_Declare( xxhash GIT_REPOSITORY https://github.com/Cyan4973/xxHash GIT_TAG v0.8.3 ) FetchContent_MakeAvailable(xxhash) # Then link: target_link_libraries(fastsync xxhash::xxhash) ``` In `delta.c`, replace the vendored include with: ```c #include <xxhash.h> ``` This keeps the repo clean and makes version management straightforward.

TapTap added 1 commit 2026-07-19 15:21:36 +02:00

refactor: replace vendored xxhash.h with CMake FetchContent dependency

CI / build-and-test (push) Successful in 33s

Details

CI / build-and-test (pull_request) Successful in 32s

Details

12557c351c

Remove 7490-line vendored xxhash.h, use FetchContent to pull xxHash v0.8.3
at CMake configure time (SOURCE_SUBDIR cmake_unofficial). Links as static
library via the xxhash target.

TapTap merged commit 1078b47955 into main

2026-07-19 15:51:27 +02:00

TapTap deleted branch feature/delta-transfer

2026-07-19 15:51:32 +02:00

TapTap referenced this pull request

2026-07-19 21:00:51 +02:00

feat: update AI automation agents, add reviewer agent, enhance CI #26

Sign in to join this conversation.

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: TapTap/FastSync#22

feat: add delta transfer for incremental sync #22

Changes

New files

Modified files

Protocol flow

Usage

Testing

CRITICAL: delta_compute is O(n*m) — not a rolling checksum

Other findings (non-blocking)

What's good

❌ Request: Replace vendored xxhash.h with CMake dependency

CRITICAL: `delta_compute` is O(n*m) — not a rolling checksum