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.
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
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
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.
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
- 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
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.
❌ 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(xxhashGIT_REPOSITORYhttps://github.com/Cyan4973/xxHashGIT_TAGv0.8.3)FetchContent_MakeAvailable(xxhash)# Then link:
target_link_libraries(fastsyncxxhash::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.
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 main2026-07-19 15:51:27 +02:00
Blocking a user prevents them from interacting with repositories, such as opening or commenting on pull requests or issues. Learn more about blocking a user.
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 librarytests/test_delta.h/test_delta.c— 13 unit testsModified 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.0src/shared/file.c— Extended receive_incremental_check() with full delta negotiationsrc/client/client_send.c— Extended incremental_check() for delta; added send_delta()src/client/client_cli.c— Added --delta and --delta-block flags with validationtests/runner.c— Registered delta test suiteProtocol flow
Usage
Testing
CHANGES REQUESTED — 1 critical performance issue
CRITICAL:
delta_computeis O(n*m) — not a rolling checksumdelta.c:407-461— The rolling checksum window advances 1 byte on miss and recomputes both adler32 and xxhash32 from scratch at every position: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-162vs125-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_attemptuses hardcodedDELTA_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
delta_is_worthwhileat 70% ratio)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.
❌ Request: Replace vendored xxhash.h with CMake dependency
src/shared/xxhash.his 7490 lines vendored, but onlyXXH32()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:In
delta.c, replace the vendored include with:This keeps the repo clean and makes version management straightforward.