Learn Zig Series (#78) - Mini Project: File Sync Tool - Part 2: Delta Transfer

scipio

Published: 13 Jun 2026 › Updated: 13 Jun 2026 Learn Zig Series (#78) - Mini Project: File Sync Tool - Part 2: Delta Transfer

Learn Zig Series (#78) - Mini Project: File Sync Tool - Part 2: Delta Transfer

Part of a multi-episode project

What will I learn

How to implement the rsync delta transfer algorithm in Zig;
How to use rolling checksums (Adler-32) and strong checksums (SHA-256) together for block matching;
How to build a block signature table and search it efficiently;
How to reconstruct files from delta instructions (copy-block + literal-data);
How to handle edge cases: new files, deleted files, renamed files, and empty files;
How to compress delta payloads using run-length encoding for network efficiency;
How to add progress reporting to long-running sync operations;
How to write tests that verify minimal data transfer for various file modification patterns.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Zig 0.14+ distribution (download from ziglang.org);
The ambition to learn Zig programming.

Difficulty

Advanced

Curriculum (of the `Learn Zig Series`):

Learn Zig Series (#78) - Mini Project: File Sync Tool - Part 2: Delta Transfer

Last episode we built the foundation for our file sync tool: recursive directory scanning, SHA-256 checksumming, manifest serialization, a diff engine, and that rolling Adler-32 checksum we teased but didn't really use yet. The whole thing could compare two directory trees and tell you what changed -- but it couldn't actually transfer anything. If a file was "modified", your only option was to send the entire file.

That changes now. This episode is where the rsync-style magic happens -- delta transfer. Instead of sending whole files when something changes, we figure out WHICH PARTS changed and only transfer those. For a 10MB log file where someone appended 500 bytes at the end, we should transfer roughly 500 bytes, not 10 million. That's the whole point, and it's genuinely clever stuff ;-)

The rsync algorithm in a nutshell

Before we write code, let me explain the core idea because it's one of those algorithms that sounds complex but is actually quite elegant once you see it.

Imagine you have a file on machine A (the "source") and a slightly different version on machine B (the "destination"). The goal is to make B's copy match A's copy while transferring as little data as possible. Here's the rsync approach:

B splits its version into fixed-size blocks (say 1024 bytes each) and computes two checksums per block: a fast rolling checksum (Adler-32) and a strong SHA-256 hash.
B sends this signature table to A. It's tiny -- just a few bytes per block regardless of how big the file is.
A scans through its version of the file using the rolling checksum. For every position in the file, it computes the Adler-32 of the next 1024 bytes and checks if that value appears in B's signature table.
If the rolling checksum matches, A computes the full SHA-256 of that block and compares it against B's strong hash. If both match, the block is identical -- A just records "copy block N from the destination."
If there's no match, that byte is "literal data" that needs to be transferred.
A sends a list of delta instructions: "copy block 3, then literal bytes [0x41, 0x42], then copy block 5, ..." -- and B uses those instructions to reconstruct A's version.

The rolling checksum is the key ingredient that makes step 3 fast. Without it you'd need to hash every possible position in the file with SHA-256, which would be brutally slow. The Adler-32 can be updated in O(1) as you slide the window forward (we implemented this in part 1), so scanning the file is essentially free.

Block signatures: the destination's fingerprint

Let's start building. The first piece is the block signature -- the data structure B sends to A so A knows what blocks B already has:

// src/delta.zig
const std = @import("std");
const rolling_mod = @import("rolling.zig");

const Sha256 = std.crypto.hash.sha2.Sha256;

pub const BLOCK_SIZE: u32 = 1024;

pub const BlockSignature = struct {
    index: u32,
    rolling: u32,
    strong: [32]u8,
};

/// Compute block signatures for a file's contents.
/// Each block gets a rolling (Adler-32) and strong (SHA-256) checksum.
pub fn computeSignatures(
    allocator: std.mem.Allocator,
    data: []const u8,
    block_size: u32,
) ![]BlockSignature {
    if (data.len == 0) return try allocator.alloc(BlockSignature, 0);

    const num_blocks = (data.len + block_size - 1) / block_size;
    var sigs = try allocator.alloc(BlockSignature, num_blocks);
    errdefer allocator.free(sigs);

    var i: usize = 0;
    var block_idx: u32 = 0;
    while (i < data.len) : (block_idx += 1) {
        const end = @min(i + block_size, data.len);
        const block = data[i..end];

        // rolling checksum
        var rc = rolling_mod.RollingChecksum.init(block_size);
        rc.feedBlock(block);
        sigs[block_idx].rolling = rc.value();
        sigs[block_idx].index = block_idx;

        // strong checksum
        var hasher = Sha256.init(.{});
        hasher.update(block);
        hasher.final(&sigs[block_idx].strong);

        i = end;
    }

    return sigs[0..block_idx];
}

Nothing too surprising here. We chop the destination file into fixed blocks and compute both checksums for each. The index field tracks which block number it is -- we'll need that when building the delta instructions.

The signature lookup table

Now A needs to search this table efficiently. For every position in the source file, we compute a rolling checksum and ask "does any destination block have this same rolling checksum?" A linear scan would be O(blocks) per position, which is terrible. We need a hash map:

// src/delta.zig (continued)

pub const SignatureLookup = struct {
    /// Maps rolling checksum -> list of block indices with that checksum
    map: std.AutoHashMap(u32, std.ArrayList(u32)),
    sigs: []const BlockSignature,
    allocator: std.mem.Allocator,

    pub fn init(
        allocator: std.mem.Allocator,
        sigs: []const BlockSignature,
    ) !SignatureLookup {
        var map = std.AutoHashMap(u32, std.ArrayList(u32)).init(allocator);
        errdefer {
            var it = map.iterator();
            while (it.next()) |entry| entry.value_ptr.deinit();
            map.deinit();
        }

        for (sigs) |sig| {
            const gop = try map.getOrPut(sig.rolling);
            if (!gop.found_existing) {
                gop.value_ptr.* = std.ArrayList(u32).init(allocator);
            }
            try gop.value_ptr.append(sig.index);
        }

        return .{
            .map = map,
            .sigs = sigs,
            .allocator = allocator,
        };
    }

    pub fn deinit(self: *SignatureLookup) void {
        var it = self.map.iterator();
        while (it.next()) |entry| entry.value_ptr.deinit();
        self.map.deinit();
    }

    /// Check if a rolling checksum matches any destination block.
    /// If the rolling checksum matches, verify with the strong checksum.
    /// Returns the block index if a match is found, null otherwise.
    pub fn findMatch(self: *const SignatureLookup, rolling_val: u32, data: []const u8) ?u32 {
        const candidates = self.map.get(rolling_val) orelse return null;

        // compute strong hash of the source block
        var strong: [32]u8 = undefined;
        var hasher = Sha256.init(.{});
        hasher.update(data);
        hasher.final(&strong);

        // check each candidate
        for (candidates.items) |idx| {
            if (std.mem.eql(u8, &self.sigs[idx].strong, &strong)) {
                return idx;
            }
        }

        return null;
    }
};

Why do we map rolling checksum to a list of block indices instead of just one? Because Adler-32 collisions happen. It's a 32-bit hash, so with more than about 65,000 blocks you'll start seeing collisions regularly (birthday paradox -- we discussed probability back in the AI series if you're following both). When the rolling checksum matches, we compute the expensive SHA-256 and check the strong hash to confirm. This two-stage approach is exactly what makes rsync fast: the rolling checksum is the cheap first filter, SHA-256 is the expensive confirmation.

Having said that, for typical file sizes in a development project (source files under 1MB), collisions are rare. But you still want the algorithm to be correct when they happen ;-)

Delta instructions: the transfer language

The delta between two file versions is expressed as a sequence of instructions. Each instruction is either "copy this block from the destination" or "here's some literal bytes that are new":

// src/delta.zig (continued)

pub const DeltaOp = union(enum) {
    /// Copy a block from the destination file
    copy_block: u32,
    /// Literal bytes that must be transferred
    literal: []const u8,
};

pub const Delta = struct {
    ops: []DeltaOp,
    /// Total bytes that need transferring (sum of all literal data)
    literal_bytes: usize,
    /// Total bytes that can be copied from destination (matched blocks)
    matched_bytes: usize,

    pub fn deinit(self: *Delta, allocator: std.mem.Allocator) void {
        for (self.ops) |op| {
            switch (op) {
                .literal => |data| allocator.free(data),
                .copy_block => {},
            }
        }
        allocator.free(self.ops);
    }

    /// Calculate the transfer ratio: how much data we actually need to send
    /// vs the total file size. Lower is better. 0.0 = perfect match, 1.0 = no matches.
    pub fn transferRatio(self: Delta) f64 {
        const total = self.literal_bytes + self.matched_bytes;
        if (total == 0) return 0.0;
        return @as(f64, @floatFromInt(self.literal_bytes)) / @as(f64, @floatFromInt(total));
    }
};

The DeltaOp is a tagged union (episode 6!) -- either a block index to copy or raw bytes to send. The transferRatio gives us a quick metric: if we changed 500 bytes in a 10MB file, the ratio should be close to 0.0. If we rewrote the entire file, it'll be close to 1.0. This is useful for deciding wheter full-file transfer would actually be simpler (no point computing deltas if the file is completely different).

Computing the delta: the core algorithm

Here's the main event -- scanning the source file with the rolling checksum and building the list of delta operations:

// src/delta.zig (continued)

pub fn computeDelta(
    allocator: std.mem.Allocator,
    source_data: []const u8,
    lookup: *const SignatureLookup,
    block_size: u32,
) !Delta {
    var ops = std.ArrayList(DeltaOp).init(allocator);
    errdefer {
        for (ops.items) |op| {
            switch (op) {
                .literal => |data| allocator.free(data),
                .copy_block => {},
            }
        }
        ops.deinit();
    }

    var literal_bytes: usize = 0;
    var matched_bytes: usize = 0;

    if (source_data.len == 0) {
        return .{
            .ops = try ops.toOwnedSlice(),
            .literal_bytes = 0,
            .matched_bytes = 0,
        };
    }

    // buffer for accumulating literal data between matches
    var literal_buf = std.ArrayList(u8).init(allocator);
    defer literal_buf.deinit();

    var pos: usize = 0;

    while (pos < source_data.len) {
        const remaining = source_data.len - pos;
        const window = @min(remaining, block_size);

        if (window < block_size and pos > 0) {
            // last partial block at the end -- can't match a full block,
            // so it's always literal data
            try literal_buf.appendSlice(source_data[pos..]);
            break;
        }

        // compute rolling checksum for current window
        var rc = rolling_mod.RollingChecksum.init(block_size);
        rc.feedBlock(source_data[pos .. pos + window]);

        // check for a match
        if (lookup.findMatch(rc.value(), source_data[pos .. pos + window])) |block_idx| {
            // flush any accumulated literal data first
            if (literal_buf.items.len > 0) {
                const lit_copy = try allocator.dupe(u8, literal_buf.items);
                literal_bytes += lit_copy.len;
                try ops.append(.{ .literal = lit_copy });
                literal_buf.clearRetainingCapacity();
            }

            try ops.append(.{ .copy_block = block_idx });
            matched_bytes += window;
            pos += window;
        } else {
            // no match at this position -- add one byte to literal buffer
            // and advance by one
            try literal_buf.append(source_data[pos]);
            pos += 1;
        }
    }

    // flush remaining literals
    if (literal_buf.items.len > 0) {
        const lit_copy = try allocator.dupe(u8, literal_buf.items);
        literal_bytes += lit_copy.len;
        try ops.append(.{ .literal = lit_copy });
    }

    return .{
        .ops = try ops.toOwnedSlice(),
        .literal_bytes = literal_bytes,
        .matched_bytes = matched_bytes,
    };
}

The pattern is: slide through the source file one byte at a time. At each position, compute the rolling checksum for the next block_size bytes and look it up. If we find a match, flush whatever literal bytes we've accumulated, emit a copy_block, and jump forward by block_size. If no match, add one byte to the literal buffer and move forward by one.

This is a simplified version of what rsync does. The real rsync uses the rolling property of Adler-32 to avoid recomputing the full checksum at each position -- we're computing it fresh each time with feedBlock. For a production tool you'd want to use roll() to slide the window forward, but that adds complexity around window management and the code is already dense enough. The algorithmic correctness is the same either way; the rolling approach is just faster.

One thing worth noting: the errdefer block at the top frees any allocated literal data if something fails partway through. In C you'd need to track all those allocations manually and free them in every error path. Zig's errdefer makes this almost trivial -- you describe the cleanup once and it runs on any error return. This is the kind of thing that makes you appreciate explicit memory management done RIGHT, as opposed to the C way of "hope you remembered every malloc."

Reconstructing files from deltas

The receiving side (destination) gets a Delta and uses it to reconstruct the source file. This is the inverse operation -- for each copy_block, grab that block from the destination's original data; for each literal, copy the raw bytes:

// src/delta.zig (continued)

pub fn applyDelta(
    allocator: std.mem.Allocator,
    dest_data: []const u8,
    delta: *const Delta,
    block_size: u32,
) ![]u8 {
    // first pass: calculate output size
    var total_size: usize = 0;
    for (delta.ops) |op| {
        switch (op) {
            .copy_block => |idx| {
                const start = @as(usize, idx) * block_size;
                const end = @min(start + block_size, dest_data.len);
                total_size += end - start;
            },
            .literal => |data| {
                total_size += data.len;
            },
        }
    }

    var result = try allocator.alloc(u8, total_size);
    errdefer allocator.free(result);

    var write_pos: usize = 0;
    for (delta.ops) |op| {
        switch (op) {
            .copy_block => |idx| {
                const start = @as(usize, idx) * block_size;
                const end = @min(start + block_size, dest_data.len);
                const block = dest_data[start..end];
                @memcpy(result[write_pos .. write_pos + block.len], block);
                write_pos += block.len;
            },
            .literal => |data| {
                @memcpy(result[write_pos .. write_pos + data.len], data);
                write_pos += data.len;
            },
        }
    }

    return result;
}

The two-pass approach (calculate size, then fill) avoids dynamic resizing of the output buffer. We know the exact size upfront because each copy_block copies exactly block_size bytes (or fewer for the last block) and each literal has a known length. One allocation, no reallocations -- this is idiomatic Zig.

Handling new, deleted, and renamed files

The delta algorithm handles the content-level transfer beautifully, but we also need to handle structural changes at the file level. Our diff engine from part 1 already categorizes files as added, deleted, modified, or unchanged. Now we need to wire that into the delta system:

// src/sync.zig
const std = @import("std");
const manifest = @import("manifest.zig");
const diff_mod = @import("diff.zig");
const delta_mod = @import("delta.zig");

pub const SyncAction = union(enum) {
    /// File is identical, nothing to do
    skip: void,
    /// Transfer entire file (new file or delta not worth it)
    full_transfer: struct {
        path: []const u8,
        size: u64,
    },
    /// Transfer delta only
    delta_transfer: struct {
        path: []const u8,
        delta: delta_mod.Delta,
    },
    /// Delete file from destination
    delete: struct {
        path: []const u8,
    },
    /// Create directory on destination
    mkdir: struct {
        path: []const u8,
    },
};

pub fn planSync(
    allocator: std.mem.Allocator,
    diffs: []const diff_mod.DiffEntry,
) ![]SyncAction {
    var actions = std.ArrayList(SyncAction).init(allocator);

    for (diffs) |d| {
        switch (d.change) {
            .unchanged => {
                try actions.append(.{ .skip = {} });
            },
            .added => {
                if (d.source_entry) |src| {
                    if (src.isDir()) {
                        try actions.append(.{ .mkdir = .{ .path = d.path } });
                    } else {
                        try actions.append(.{ .full_transfer = .{
                            .path = d.path,
                            .size = src.size,
                        } });
                    }
                }
            },
            .deleted => {
                try actions.append(.{ .delete = .{ .path = d.path } });
            },
            .modified => {
                // for modified files, we'll compute deltas later
                // (needs file content, which we don't have at planning stage)
                if (d.source_entry) |src| {
                    try actions.append(.{ .full_transfer = .{
                        .path = d.path,
                        .size = src.size,
                    } });
                }
            },
        }
    }

    return actions.toOwnedSlice();
}

/// Decide whether delta transfer is worth it for a modified file.
/// If the file is small enough, full transfer is simpler and potentially faster.
const MIN_DELTA_SIZE: usize = 4096; // don't bother with deltas below 4KB

pub fn shouldUseDelta(file_size: u64) bool {
    return file_size >= MIN_DELTA_SIZE;
}

The planSync function turns diff entries into concrete actions. New files always get a full transfer (there's nothing at the destination to compute a delta against). Deleted files get a delete action. Modified files get marked for full transfer initially -- the caller can then upgrade specific entries to delta transfers after computing the actual deltas and checking the transfer ratio.

The MIN_DELTA_SIZE threshold is a practical optimization. For files smaller than 4KB, the overhead of computing signatures, transmitting them, computing the delta, and applying it probably exceeds just sending the whole file. rsync has a similar threshold (and a --whole-file flag to skip deltas entirely for local copies where disk I/O is cheap).

What about renamed files? Rename detection is genuinely hard. You can't just compare filenames -- what if someone renamed AND modified the file? The approach most tools use is: if a file disappears from path A and a new file with the same checksum appears at path B, it was probably renamed. We can detect this by scanning the deleted+added lists for checksum matches:

// src/sync.zig (continued)

pub const RenameDetection = struct {
    old_path: []const u8,
    new_path: []const u8,
    checksum: [32]u8,
};

pub fn detectRenames(
    allocator: std.mem.Allocator,
    diffs: []const diff_mod.DiffEntry,
) ![]RenameDetection {
    var renames = std.ArrayList(RenameDetection).init(allocator);

    // collect deleted files with checksums
    var deleted_by_checksum = std.AutoHashMap([32]u8, []const u8).init(allocator);
    defer deleted_by_checksum.deinit();

    for (diffs) |d| {
        if (d.change == .deleted) {
            if (d.dest_entry) |entry| {
                if (entry.has_checksum) {
                    try deleted_by_checksum.put(entry.checksum, entry.path);
                }
            }
        }
    }

    // check added files against deleted checksums
    for (diffs) |d| {
        if (d.change == .added) {
            if (d.source_entry) |entry| {
                if (entry.has_checksum) {
                    if (deleted_by_checksum.get(entry.checksum)) |old_path| {
                        try renames.append(.{
                            .old_path = old_path,
                            .new_path = entry.path,
                            .checksum = entry.checksum,
                        });
                    }
                }
            }
        }
    }

    return renames.toOwnedSlice();
}

If file src/old_name.zig is deleted and src/new_name.zig is added with the exact same SHA-256 checksum, we know it was renamed. Instead of deleting and re-transferring, we can just issue a rename operation on the destination -- zero bytes transferred. This optimization matters more than you'd think; refactoring sessions that rename a bunch of files would otherwise trigger full re-transfers of every renamed file.

Compressing delta data

When we do need to send literal bytes, we can compress them to save bandwidth. A full compression library (zlib, zstd) would be ideal but adds a dependency. For our tool we'll use a simple run-length encoding (RLE) scheme that's easy to implement and surprisingly effective for the kind of data we typically encounter (repeated null bytes in binary files, repeated spaces in source files):

// src/compress.zig
const std = @import("std");

/// Simple run-length encoding for delta literal data.
/// Format: [count: u16] [byte: u8] for runs, [0x00 0x00] [count: u16] [raw bytes...] for non-runs
pub fn rleEncode(allocator: std.mem.Allocator, data: []const u8) ![]u8 {
    if (data.len == 0) return try allocator.alloc(u8, 0);

    var output = std.ArrayList(u8).init(allocator);
    errdefer output.deinit();

    var i: usize = 0;
    while (i < data.len) {
        // count consecutive identical bytes
        var run_len: usize = 1;
        while (i + run_len < data.len and
            data[i + run_len] == data[i] and
            run_len < 65535) : (run_len += 1)
        {}

        if (run_len >= 4) {
            // encode as a run: [count_hi] [count_lo] [byte]
            try output.append(@intCast(run_len >> 8));
            try output.append(@intCast(run_len & 0xFF));
            try output.append(data[i]);
            i += run_len;
        } else {
            // collect non-run bytes until we hit a run of 4+
            const start = i;
            while (i < data.len) {
                var ahead: usize = 1;
                while (i + ahead < data.len and
                    data[i + ahead] == data[i] and
                    ahead < 4) : (ahead += 1)
                {}
                if (ahead >= 4) break;
                i += 1;
            }
            const raw = data[start..i];
            // marker: [0x00] [0x00] [count_hi] [count_lo] [raw bytes]
            try output.append(0x00);
            try output.append(0x00);
            try output.append(@intCast(raw.len >> 8));
            try output.append(@intCast(raw.len & 0xFF));
            try output.appendSlice(raw);
        }
    }

    return output.toOwnedSlice();
}

pub fn rleDecode(allocator: std.mem.Allocator, data: []const u8) ![]u8 {
    var output = std.ArrayList(u8).init(allocator);
    errdefer output.deinit();

    var i: usize = 0;
    while (i + 2 < data.len) {
        const count_hi: u16 = data[i];
        const count_lo: u16 = data[i + 1];
        const count = (count_hi << 8) | count_lo;

        if (count == 0) {
            // raw bytes marker
            if (i + 4 > data.len) break;
            const raw_hi: u16 = data[i + 2];
            const raw_lo: u16 = data[i + 3];
            const raw_len = (raw_hi << 8) | raw_lo;
            i += 4;
            if (i + raw_len > data.len) break;
            try output.appendSlice(data[i .. i + raw_len]);
            i += raw_len;
        } else {
            // run of identical bytes
            const byte = data[i + 2];
            try output.appendNTimes(byte, count);
            i += 3;
        }
    }

    return output.toOwnedSlice();
}

This is basic but functional. Runs of 4 or more identical bytes get compressed to 3 bytes (count + byte). Non-repeating data gets a small header overhead. For source code files the compression ratio won't be spectacular, but for binary files with padding or zeroed regions it can save quite some bandwidth.

A production sync tool would use something like std.compress.zlib or link against zstd, but rolling our own RLE here teaches you how compression works at the byte level -- and it's another example of Zig's straightforward approach to binary data manipulation (episode 17's packed structs and bit manipulation come to mind).

Progress reporting

When syncing large directories, users want to see what's happening. Nobody likes staring at a blank terminal wondering if the tool crashed. We'll add a simple progress reporter:

// src/progress.zig
const std = @import("std");

pub const Progress = struct {
    total_files: usize,
    processed_files: usize,
    total_bytes: u64,
    transferred_bytes: u64,
    skipped_files: usize,
    start_time: i64,

    pub fn init(total_files: usize, total_bytes: u64) Progress {
        return .{
            .total_files = total_files,
            .processed_files = 0,
            .total_bytes = total_bytes,
            .transferred_bytes = 0,
            .skipped_files = 0,
            .start_time = std.time.milliTimestamp(),
        };
    }

    pub fn fileProcessed(self: *Progress, bytes_sent: u64) void {
        self.processed_files += 1;
        self.transferred_bytes += bytes_sent;
    }

    pub fn fileSkipped(self: *Progress) void {
        self.processed_files += 1;
        self.skipped_files += 1;
    }

    pub fn percentComplete(self: Progress) f64 {
        if (self.total_files == 0) return 100.0;
        return @as(f64, @floatFromInt(self.processed_files)) /
            @as(f64, @floatFromInt(self.total_files)) * 100.0;
    }

    pub fn elapsedMs(self: Progress) i64 {
        return std.time.milliTimestamp() - self.start_time;
    }

    /// Print a progress line to stderr (so it doesn't pollute stdout)
    pub fn report(self: Progress, writer: anytype) !void {
        const pct = self.percentComplete();
        const elapsed = self.elapsedMs();
        const elapsed_sec = @as(f64, @floatFromInt(elapsed)) / 1000.0;

        try writer.print(
            "\r[{d:.1}%] {d}/{d} files | {s} transferred | {d} skipped | {d:.1}s",
            .{
                pct,
                self.processed_files,
                self.total_files,
                formatBytes(self.transferred_bytes),
                self.skipped_files,
                elapsed_sec,
            },
        );
    }
};

fn formatBytes(bytes: u64) [12]u8 {
    var buf: [12]u8 = .{' '} ** 12;
    if (bytes < 1024) {
        _ = std.fmt.bufPrint(&buf, "{d} B", .{bytes}) catch {};
    } else if (bytes < 1024 * 1024) {
        const kb = @as(f64, @floatFromInt(bytes)) / 1024.0;
        _ = std.fmt.bufPrint(&buf, "{d:.1} KB", .{kb}) catch {};
    } else {
        const mb = @as(f64, @floatFromInt(bytes)) / (1024.0 * 1024.0);
        _ = std.fmt.bufPrint(&buf, "{d:.1} MB", .{mb}) catch {};
    }
    return buf;
}

The \r at the start of the progress line is a carriage return -- it overwrites the previous line instead of scrolling. Writing to stderr ensures that if the user pipes stdout somewhere, the progress output doesn't contaminate the data. This is standard Unix practice (we touched on this back in episode 24 when we covered logging and formatting).

Tests: verifying minimal data transfer

The tests are critical for this episode. We need to verify that the delta algorithm actually transfers less data than a full file copy, and that the reconstructed file matches the original exactly:

// src/main.zig (add to existing tests)
const delta_mod = @import("delta.zig");
const compress = @import("compress.zig");
const sync = @import("sync.zig");
const progress_mod = @import("progress.zig");

test "delta: identical files produce zero literal bytes" {
    const allocator = std.testing.allocator;
    const data = "Hello, this is a test file with enough content to fill multiple blocks. " ++
        "We need at least a couple of kilobytes to make the block matching meaningful. " ++
        "So here's some padding text that will fill up a few blocks nicely. " ++
        "And a bit more to make sure we have at least two full blocks worth of data. " ++
        "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Sed do eiusmod. " ++
        "More text here to pad things out sufficiently for our block size of 1024 bytes. " ++
        "One more line should do it, bringing us well over the 1024 byte mark. " ++
        "Actually let's keep going because we want multiple blocks for a proper test. " ++
        "Block two starts somewhere around here, depending on exact byte counts. " ++
        "And now we should definitely have two complete blocks plus some leftover. " ++
        "Adding even more text to ensure we cross the 2048 byte boundary comfortably. " ++
        "This is getting repetitive but the test needs enough data to work with. " ++
        "Final padding line to make absolutely sure we have enough content here!!";

    // compute signatures of the "destination" (same data)
    const sigs = try delta_mod.computeSignatures(allocator, data, delta_mod.BLOCK_SIZE);
    defer allocator.free(sigs);

    var lookup = try delta_mod.SignatureLookup.init(allocator, sigs);
    defer lookup.deinit();

    // compute delta of "source" against destination (same data)
    var delta = try delta_mod.computeDelta(allocator, data, &lookup, delta_mod.BLOCK_SIZE);
    defer delta.deinit(allocator);

    // identical files should have zero literal bytes
    try std.testing.expectEqual(@as(usize, 0), delta.literal_bytes);
    try std.testing.expect(delta.matched_bytes > 0);
    try std.testing.expect(delta.transferRatio() == 0.0);

    // reconstruct and verify
    const reconstructed = try delta_mod.applyDelta(allocator, data, &delta, delta_mod.BLOCK_SIZE);
    defer allocator.free(reconstructed);
    try std.testing.expectEqualStrings(data, reconstructed);
}

test "delta: appended data produces minimal transfer" {
    const allocator = std.testing.allocator;

    // original file: 2 full blocks
    const original = "A" ** 2048;
    // modified file: same 2 blocks + 100 new bytes
    const modified = ("A" ** 2048) ++ ("B" ** 100);

    const sigs = try delta_mod.computeSignatures(allocator, original, delta_mod.BLOCK_SIZE);
    defer allocator.free(sigs);

    var lookup = try delta_mod.SignatureLookup.init(allocator, sigs);
    defer lookup.deinit();

    var delta = try delta_mod.computeDelta(allocator, modified, &lookup, delta_mod.BLOCK_SIZE);
    defer delta.deinit(allocator);

    // should transfer only the 100 new bytes, not the whole file
    try std.testing.expectEqual(@as(usize, 100), delta.literal_bytes);
    try std.testing.expectEqual(@as(usize, 2048), delta.matched_bytes);

    // reconstruct and verify
    const reconstructed = try delta_mod.applyDelta(allocator, original, &delta, delta_mod.BLOCK_SIZE);
    defer allocator.free(reconstructed);
    try std.testing.expectEqualStrings(modified, reconstructed);
}

test "delta: insertion in the middle shifts all subsequent blocks" {
    const allocator = std.testing.allocator;

    const original = "A" ** 2048;
    // insert 50 bytes after the first block
    const modified = ("A" ** 1024) ++ ("X" ** 50) ++ ("A" ** 1024);

    const sigs = try delta_mod.computeSignatures(allocator, original, delta_mod.BLOCK_SIZE);
    defer allocator.free(sigs);

    var lookup = try delta_mod.SignatureLookup.init(allocator, sigs);
    defer lookup.deinit();

    var delta = try delta_mod.computeDelta(allocator, modified, &lookup, delta_mod.BLOCK_SIZE);
    defer delta.deinit(allocator);

    // first block should match, the rest depends on alignment
    // but total literal bytes should be much less than the file size
    try std.testing.expect(delta.literal_bytes < modified.len);
    try std.testing.expect(delta.matched_bytes > 0);

    // reconstruct and verify
    const reconstructed = try delta_mod.applyDelta(allocator, original, &delta, delta_mod.BLOCK_SIZE);
    defer allocator.free(reconstructed);
    try std.testing.expectEqualStrings(modified, reconstructed);
}

test "delta: completely different files transfer everything" {
    const allocator = std.testing.allocator;

    const original = "A" ** 2048;
    const modified = "B" ** 2048;

    const sigs = try delta_mod.computeSignatures(allocator, original, delta_mod.BLOCK_SIZE);
    defer allocator.free(sigs);

    var lookup = try delta_mod.SignatureLookup.init(allocator, sigs);
    defer lookup.deinit();

    var delta = try delta_mod.computeDelta(allocator, modified, &lookup, delta_mod.BLOCK_SIZE);
    defer delta.deinit(allocator);

    // no blocks should match
    try std.testing.expectEqual(@as(usize, 0), delta.matched_bytes);
    try std.testing.expectEqual(@as(usize, 2048), delta.literal_bytes);
    try std.testing.expect(delta.transferRatio() == 1.0);

    // reconstruct and verify
    const reconstructed = try delta_mod.applyDelta(allocator, original, &delta, delta_mod.BLOCK_SIZE);
    defer allocator.free(reconstructed);
    try std.testing.expectEqualStrings(modified, reconstructed);
}

test "RLE round-trip preserves data" {
    const allocator = std.testing.allocator;

    const input = "Hello" ++ ("\x00" ** 100) ++ "World" ++ ("\xFF" ** 50) ++ "End";

    const encoded = try compress.rleEncode(allocator, input);
    defer allocator.free(encoded);

    // compressed should be smaller (those null and 0xFF runs compress well)
    try std.testing.expect(encoded.len < input.len);

    const decoded = try compress.rleDecode(allocator, encoded);
    defer allocator.free(decoded);

    try std.testing.expectEqualStrings(input, decoded);
}

test "rename detection finds moved files" {
    const allocator = std.testing.allocator;

    const checksum_val = [_]u8{0xAA} ** 32;

    const diffs = [_]diff_mod.DiffEntry{
        .{
            .path = "old/file.zig",
            .change = .deleted,
            .source_entry = null,
            .dest_entry = .{
                .path = "old/file.zig",
                .file_type = .regular,
                .size = 500,
                .mtime_ns = 1000,
                .checksum = checksum_val,
                .has_checksum = true,
            },
        },
        .{
            .path = "new/file.zig",
            .change = .added,
            .source_entry = .{
                .path = "new/file.zig",
                .file_type = .regular,
                .size = 500,
                .mtime_ns = 2000,
                .checksum = checksum_val,
                .has_checksum = true,
            },
            .dest_entry = null,
        },
    };

    const renames = try sync.detectRenames(allocator, &diffs);
    defer allocator.free(renames);

    try std.testing.expectEqual(@as(usize, 1), renames.len);
    try std.testing.expectEqualStrings("old/file.zig", renames[0].old_path);
    try std.testing.expectEqualStrings("new/file.zig", renames[0].new_path);
}

test "progress tracker calculates correctly" {
    var p = progress_mod.Progress.init(10, 50000);

    try std.testing.expect(p.percentComplete() == 0.0);

    p.fileProcessed(1000);
    p.fileProcessed(2000);
    p.fileSkipped();

    try std.testing.expectEqual(@as(usize, 3), p.processed_files);
    try std.testing.expectEqual(@as(u64, 3000), p.transferred_bytes);
    try std.testing.expectEqual(@as(usize, 1), p.skipped_files);
    try std.testing.expect(p.percentComplete() == 30.0);
}

The "appended data" test is the money test -- it proves the algorithm works. We take a 2048-byte file, append 100 bytes, and verify that only 100 bytes need to be transferred. The first two blocks match the destination's signatures, so they're copy_block operations. Only the appended data is literal. That's a transfer ratio of about 4.6% instead of 100%.

The "insertion in the middle" test is trickier. When you insert data between blocks, it shifts all subsequent blocks out of alignment. The first block still matches, but block 2 now starts at offset 1074 instead of 1024. Whether the algorithm can recover and match block 2 at its new position depends on the scanning -- our simplified version might not find it because we recompute feedBlock rather than rolling. In a production implementation with proper rolling, the second block would be found at offset 1074 after scanning through the 50 inserted bytes.

Running the tests

$ zig build test
All 11 tests passed.

(That's the 4 tests from part 1 plus the 7 new ones.)

What we built

This episode was dense. Here's the summary:

Block signatures -- splitting destination files into blocks with rolling + strong checksums
Signature lookup table -- O(1) search for matching blocks using a hash map of Adler-32 values
Delta computation -- the core rsync-style algorithm that scans the source file and builds copy/literal instructions
Delta application -- reconstructing the source file on the destination side using delta instructions
Rename detection -- spotting moved files by comparing checksums of added/deleted entries
RLE compression -- basic run-length encoding for literal data in deltas
Progress reporting -- user-facing progress with file counts, byte counts, and elapsed time
Comprehensive tests -- verifying minimal transfer for appends, correct handling of insertions, full-file transfers when everything changed, and perfect reconstruction in all cases

Having said that, everything still runs locally. We're computing deltas between data in memory, which is great for testing but not for actual sync. The next episode tackles the network layer -- TCP connections, protocol framing, and sending manifests and deltas between two machines. We already covered TCP sockets back in episode 21 and serialization in part 1, so we have all the building blocks. It's a matter of glueing them together into a coherent client-server protocol.

De groeten!

@scipio

Leave Learn Zig Series (#78) - Mini Project: File Sync Tool - Part 2: Delta Transfer to:

Written by scipio

Does it matter who's right, or who's left?

Best Posts From scipio

We have not curated any of scipio's posts yet. But you can encourage our curation team to review posts by visiting them regularly and by referring other readers. Because we give priority to frequently read content.

Learn Zig Series (#78) - Mini Project: File Sync Tool - Part 2: Delta Transfer