Skip to content
zit Artifact [05ec0275e4]
Login

Artifact [05ec0275e4]

Check-ins Using Download Hex

Artifact 05ec0275e4f67d8ca0db542e67ee891892cbbb3c04892b1875ff45c7a8c805ba:

//! Delta Format — draft-fossil-delta-format-00.
//!
//! A delta encodes one byte sequence (the *target*) as instructions for
//! reconstructing it from another (the *source*): a header giving the target
//! byte-count, a stream of copy/literal segments, and a trailing checksum.
//!
//! This module implements the base-64 integer codec (Section 3.1) and
//! checksum (Section 3.4) that the rest of the format is built on, the
//! decoder (`apply`, Section 4), and a minimal conforming producer
//! (`create`, Section 5).

const std = @import("std");

pub const Error = error{
    /// The delta is malformed (truncated, bad opcode, bounds violation, ...).
    /// The specific rejection conditions are enumerated in Section 4.
    MalformedDelta,
    /// Reconstructed output did not match the trailing checksum (Section 3.4).
    ChecksumMismatch,
};

/// Errors specific to the producer (Section 5). Kept separate from `Error`
/// (decoder rejections) so `apply`'s error set stays clean.
pub const CreateError = error{
    /// §3.1: every integer a conforming producer emits MUST be less than
    /// 2^32; a target this large cannot be encoded.
    TargetTooLarge,
};

// ---------------------------------------------------------------------------
// Base-64 integers (Section 3.1)
//
// Integers are written most-significant digit first (Section 3.1). Internally
// digits are collected least-significant-first, then reversed on output.
// ---------------------------------------------------------------------------

pub const digit64 =
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz~";

/// Reverse map: byte -> 0..63, or -1 if not a DIGIT64 character.
const value64: [256]i8 = blk: {
    var t = [_]i8{-1} ** 256;
    for (digit64, 0..) |c, i| t[c] = @intCast(i);
    break :blk t;
};

/// Encode `v` MSB-first into `buf`, returning the written slice.
/// A 32-bit value needs at most 6 base-64 digits.
pub fn encodeInt(v: u32, buf: *[6]u8) []u8 {
    if (v == 0) {
        buf[0] = digit64[0];
        return buf[0..1];
    }
    var tmp: [6]u8 = undefined;
    var n: usize = 0;
    var x = v;
    while (x > 0) : (n += 1) {
        tmp[n] = digit64[@intCast(x & 0x3f)];
        x >>= 6;
    }
    var j: usize = 0;
    while (j < n) : (j += 1) buf[j] = tmp[n - 1 - j];
    return buf[0..n];
}

pub const Decoded = struct { value: u32, len: usize };

/// Decode a leading base-64 integer from `s`. Consumes DIGIT64 characters
/// until the first non-digit byte (or end of input). Per Section 3.1 a value
/// that reaches 2^32 is not interoperable and its handling is otherwise
/// implementation-defined; we take the strict posture and reject it rather than
/// let a 32-bit accumulator wrap silently.
///
/// §6: bytes 0x80-0xFF are not in the alphabet and MUST terminate here, same
/// as any other non-digit byte. The lookup below indexes `value64` with the
/// raw byte and applies no high-bit mask, by design: masking would fold
/// 0x80-0xBF onto '0'-'?' and accept them as digits, the exact anti-pattern
/// §6 calls out.
pub fn decodeInt(s: []const u8) Error!Decoded {
    var acc: u64 = 0;
    var i: usize = 0;
    while (i < s.len) : (i += 1) {
        const d = value64[s[i]];
        if (d < 0) break;
        acc = (acc << 6) | @as(u64, @intCast(d));
        if (acc > std.math.maxInt(u32)) return Error.MalformedDelta;
    }
    std.debug.assert(acc <= std.math.maxInt(u32));
    return .{ .value = @intCast(acc), .len = i };
}

// ---------------------------------------------------------------------------
// Checksum (Section 3.4)
//
// Treat the target as big-endian 32-bit words, sum them modulo 2^32 (natural
// unsigned wraparound). A trailing run shorter than four bytes is added as
// z[0]<<24, z[1]<<16, z[2]<<8. NOTE: the modulus is 2^32, not 2^32-1 — the
// Fossil prose docs say otherwise and are in error (Anomalies).
// ---------------------------------------------------------------------------

pub fn checksum(data: []const u8) u32 {
    var sum: u32 = 0;
    var i: usize = 0;
    while (i + 4 <= data.len) : (i += 4) {
        const w = (@as(u32, data[i]) << 24) |
            (@as(u32, data[i + 1]) << 16) |
            (@as(u32, data[i + 2]) << 8) |
            @as(u32, data[i + 3]);
        sum +%= w;
    }
    const rem = data.len - i;
    if (rem >= 1) sum +%= @as(u32, data[i]) << 24;
    if (rem >= 2) sum +%= @as(u32, data[i + 1]) << 16;
    if (rem >= 3) sum +%= @as(u32, data[i + 2]) << 8;
    return sum;
}

// ---------------------------------------------------------------------------
// Apply / create (Section 4, Section 5)
// ---------------------------------------------------------------------------

/// Parsed and validated delta header (§4 step 2).
const Header = struct {
    /// Declared length of the reconstructed target, in bytes.
    target_len: usize,
    /// Byte offset of the first segment, immediately past the header's LF.
    pos: usize,
};

/// Parse the header: a base-64 integer target length followed by a
/// mandatory 0x0a (§4 step 2).
fn parseHeader(delta_bytes: []const u8) Error!Header {
    const header = try decodeInt(delta_bytes);
    const p = header.len;
    if (p >= delta_bytes.len) return Error.MalformedDelta; // matrix #2: int ran to buffer end, no LF.
    if (delta_bytes[p] != '\n') return Error.MalformedDelta; // matrix #1: header not followed by 0x0a.
    return .{ .target_len = header.value, .pos = p + 1 }; // +1: past the header LF.
}

/// Read only the declared target byte-count from a delta (§4.1). Reads the
/// header integer and its terminating 0x0a and nothing more: no segment or
/// trailer byte is read, required, or validated, and no bytes are required
/// after that LF for the query to succeed. Returns MalformedDelta when the
/// buffer is empty or the header integer is not immediately followed by
/// 0x0a (§4.1's two rejection conditions; both funnel through parseHeader).
pub fn targetSize(delta_bytes: []const u8) Error!usize {
    const header = try parseHeader(delta_bytes);
    // Restates decodeInt's u32 cap, which parseHeader inherits; not a new guarantee.
    std.debug.assert(header.target_len <= std.math.maxInt(u32));
    return header.target_len;
}

/// Apply one `@`-copy segment starting at the opcode byte `q`. Returns the
/// delta position of the next segment. See §4 step 3, matrix entries #3-#5.
fn applyCopy(
    source: []const u8,
    delta_bytes: []const u8,
    q: usize,
    count: usize,
    out: []u8,
    out_pos: *usize,
    target_len: usize,
) Error!usize {
    const o = try decodeInt(delta_bytes[q + 1 ..]);
    const r = q + 1 + o.len;
    if (r >= delta_bytes.len) return Error.MalformedDelta; // matrix #2
    if (delta_bytes[r] != ',') return Error.MalformedDelta; // matrix #3: no comma.
    const offset: usize = o.value;
    // u64 widening: each operand is < 2^32 (decodeInt's cap), so the sum is
    // < 2^33 and cannot wrap — satisfies the "does not overflow for large
    // values" requirement (§4 step 3 `@`).
    if (@as(u64, offset) + @as(u64, count) > source.len) return Error.MalformedDelta; // matrix #5
    if (@as(u64, out_pos.*) + @as(u64, count) > target_len) return Error.MalformedDelta; // matrix #4
    std.debug.assert(offset + count <= source.len);
    std.debug.assert(out_pos.* + count <= target_len);
    @memcpy(out[out_pos.*..][0..count], source[offset..][0..count]);
    out_pos.* += count;
    return r + 1;
}

/// Apply one `:`-literal segment starting at the opcode byte `q`. Returns
/// the delta position of the next segment. See §4 step 3, matrix entries
/// #6-#7.
fn applyLiteral(
    delta_bytes: []const u8,
    q: usize,
    count: usize,
    out: []u8,
    out_pos: *usize,
    target_len: usize,
) Error!usize {
    const rem = delta_bytes.len - (q + 1);
    if (count > rem) return Error.MalformedDelta; // matrix #7: count exceeds remaining delta.
    if (@as(u64, out_pos.*) + @as(u64, count) > target_len) return Error.MalformedDelta; // matrix #6
    std.debug.assert(out_pos.* + count <= target_len);
    @memcpy(out[out_pos.*..][0..count], delta_bytes[q + 1 ..][0..count]);
    out_pos.* += count;
    return q + 1 + count;
}

/// Validate the `;` trailer: output must be exactly `target_len` bytes and
/// `count` (the trailer's integer) must equal the checksum of `out`. See §4
/// step 3, matrix entries #8-#9.
fn checkTrailer(out: []const u8, out_pos: usize, target_len: usize, count: usize) Error!void {
    if (out_pos != target_len) return Error.MalformedDelta; // matrix #9
    if (count != checksum(out)) return Error.ChecksumMismatch; // matrix #8
}

/// Reconstruct the target by applying `delta` to `source`.
/// Caller owns the returned slice; on any rejection the output buffer is
/// freed before the error returns, so a caller that discards the error per
/// Section 6 cannot leak or read a partial buffer. See Section 4 for the
/// procedure and the exhaustive rejection conditions (matrix entries 1-11).
/// `source` must be the complete, resident source bytes: this decoder has no
/// mechanism to request or await an absent source, so the caller MUST supply
/// it in full before calling (§4.2). A repository layer that does not yet
/// hold the source should not invoke this function at all.
pub fn apply(
    allocator: std.mem.Allocator,
    source: []const u8,
    delta_bytes: []const u8,
) (Error || std.mem.Allocator.Error)![]u8 {
    if (delta_bytes.len == 0) return Error.MalformedDelta; // §4 step 1: zero-length delta, rejected ahead of the numbered matrix (§6).

    const header = try parseHeader(delta_bytes);
    const target_len = header.target_len;
    var p: usize = header.pos;
    const out = try allocator.alloc(u8, target_len);
    errdefer allocator.free(out);
    var out_pos: usize = 0;

    // Segment loop (§4 step 3). Every branch that continues the loop
    // advances `p` by at least one byte, so `iters` cannot exceed the delta
    // length; the assert makes that bound explicit rather than assumed.
    var iters: usize = 0;
    while (p < delta_bytes.len) {
        iters += 1;
        std.debug.assert(iters <= delta_bytes.len);
        std.debug.assert(p <= delta_bytes.len);
        std.debug.assert(out_pos <= target_len);

        const c = try decodeInt(delta_bytes[p..]);
        const count: usize = c.value;
        const q = p + c.len;
        if (q >= delta_bytes.len) return Error.MalformedDelta; // matrix #2: count field ran off the end.

        switch (delta_bytes[q]) {
            '@' => p = try applyCopy(source, delta_bytes, q, count, out, &out_pos, target_len),
            ':' => p = try applyLiteral(delta_bytes, q, count, out, &out_pos, target_len),
            ';' => { // trailer: `count` is the checksum integer, not a byte count.
                try checkTrailer(out, out_pos, target_len, count);
                std.debug.assert(out_pos == target_len);
                std.debug.assert(out.len == target_len);
                return out; // ownership transfers; errdefer does not fire.
            },
            else => return Error.MalformedDelta, // matrix #10: opcode not in {@, :, ;}.
        }
    }
    return Error.MalformedDelta; // matrix #11: ran off the end without a trailer.
}

/// Source-block size for the encoder's hash index. §5 notes that for a source
/// of 16 bytes or fewer a copy can never beat the equivalent literal, so this is
/// both the index granularity and the minimum match length worth emitting.
const encoder_block = 16;

/// Emit a literal segment for `lit` (count, ':', payload), or nothing when `lit`
/// is empty (§3.3.2).
fn flushLiteral(allocator: std.mem.Allocator, out: *std.ArrayList(u8), lit: []const u8, ibuf: *[6]u8) std.mem.Allocator.Error!void {
    if (lit.len == 0) return;
    try out.appendSlice(allocator, encodeInt(@intCast(lit.len), ibuf));
    try out.append(allocator, ':');
    try out.appendSlice(allocator, lit);
}

/// Source offset of a byte-verified `encoder_block`-length match for
/// `target[t..]`, or null. Verifying the bytes (not just the hash) means a hash
/// collision costs only a missed match, never a wrong copy.
fn matchAt(source: []const u8, target: []const u8, t: usize, index: *std.AutoHashMap(u64, u32)) ?usize {
    if (t + encoder_block > target.len) return null;
    const h = std.hash.Wyhash.hash(0, target[t..][0..encoder_block]);
    const off: usize = index.get(h) orelse return null;
    if (!std.mem.eql(u8, source[off..][0..encoder_block], target[t..][0..encoder_block])) return null;
    return off;
}

/// Produce a delta that reconstructs `target` from `source` (Section 5, which is
/// informative: any copy/literal segmentation that reproduces the target is a
/// valid delta). This encoder indexes non-overlapping `encoder_block`-byte source
/// blocks by hash, greedily grows each byte-verified hash hit into the longest
/// copy, and emits the gaps as literals; the trailer carries the target checksum
/// (§3.4). A source of `encoder_block` bytes or fewer is emitted whole as one
/// literal (§5's last paragraph). Caller owns the returned slice.
pub fn create(
    allocator: std.mem.Allocator,
    source: []const u8,
    target: []const u8,
) (CreateError || std.mem.Allocator.Error)![]u8 {
    // Every integer the format carries (target length, count, offset, checksum)
    // must be < 2^32 (§3.1); refuse inputs whose sizes we could not represent.
    if (source.len > std.math.maxInt(u32) or target.len > std.math.maxInt(u32))
        return CreateError.TargetTooLarge;

    var out: std.ArrayList(u8) = .empty;
    errdefer out.deinit(allocator);
    var ibuf: [6]u8 = undefined;

    // Header: target length then the mandatory LF (§3.2).
    try out.appendSlice(allocator, encodeInt(@intCast(target.len), &ibuf));
    try out.append(allocator, '\n');

    // Index non-overlapping source blocks by hash (latest offset per hash; the
    // byte-verification in matchAt tolerates the resulting overwrites). §5: skip
    // this for a source of encoder_block bytes or fewer — a literal is as good.
    var index = std.AutoHashMap(u64, u32).init(allocator);
    defer index.deinit();
    if (source.len > encoder_block) {
        var i: usize = 0;
        while (i + encoder_block <= source.len) : (i += encoder_block) {
            try index.put(std.hash.Wyhash.hash(0, source[i..][0..encoder_block]), @intCast(i));
        }
    }

    // Greedy scan: each verified run becomes a copy; the bytes between runs
    // accumulate as one pending literal, flushed before each copy and at the end.
    // Every iteration advances `t`, so the loop is bounded by target.len.
    var t: usize = 0;
    var lit_start: usize = 0;
    while (t < target.len) {
        if (matchAt(source, target, t, &index)) |o| {
            var len: usize = encoder_block;
            while (o + len < source.len and t + len < target.len and
                source[o + len] == target[t + len]) : (len += 1)
            {}
            std.debug.assert(o + len <= source.len);
            std.debug.assert(t + len <= target.len);
            try flushLiteral(allocator, &out, target[lit_start..t], &ibuf);
            try out.appendSlice(allocator, encodeInt(@intCast(len), &ibuf)); // count
            try out.append(allocator, '@');
            try out.appendSlice(allocator, encodeInt(@intCast(o), &ibuf)); // offset
            try out.append(allocator, ',');
            t += len;
            lit_start = t;
        } else {
            t += 1;
        }
    }
    try flushLiteral(allocator, &out, target[lit_start..], &ibuf);

    // Trailer: checksum of the target, then ';' (§3.4).
    try out.appendSlice(allocator, encodeInt(checksum(target), &ibuf));
    try out.append(allocator, ';');

    std.debug.assert(out.items.len >= 4); // minimum valid delta is "0\n0;"
    std.debug.assert(out.items[out.items.len - 1] == ';');
    return out.toOwnedSlice(allocator);
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

test "delta §3.1: base-64 integer round-trips (MSB-first)" {
    var buf: [6]u8 = undefined;
    for ([_]u32{ 0, 1, 63, 64, 4095, 100000, 0xFFFF_FFFF }) |v| {
        const enc = encodeInt(v, &buf);
        const dec = try decodeInt(enc);
        try std.testing.expectEqual(v, dec.value);
        try std.testing.expectEqual(enc.len, dec.len);
    }
}

test "delta §3.1: decodeInt rejects an integer that reaches 2^32" {
    // "400000" = 4*64^5 = 2^32: §3.1 lets a decoder reject >= 2^32, and the
    // strict posture avoids the silent u32 wrap the naive accumulator would do.
    try std.testing.expectError(Error.MalformedDelta, decodeInt("400000"));
    // 2^32 - 1 is the largest in-range value and must still decode.
    const max = try decodeInt("3~~~~~");
    try std.testing.expectEqual(@as(u32, 0xFFFF_FFFF), max.value);
}

test "delta §3.1: encodeInt is most-significant-digit first" {
    var buf: [6]u8 = undefined;
    // 64 = 1*64 + 0 -> "10" (MSB first), not "01".
    try std.testing.expectEqualStrings("10", encodeInt(64, &buf));
    try std.testing.expectEqualStrings("0", encodeInt(0, &buf));
}

test "delta §6: high-bit byte terminates integer accumulation" {
    // §6 lines 565-567: bytes 0x80-0xFF are outside the 64-character
    // alphabet and MUST terminate, not extend, an integer in progress.
    // Table over the full range so a future switch to a masked lookup
    // (`b & 0x7f`) regresses loudly rather than passing on a spot check.
    var b: u16 = 0x80;
    while (b <= 0xFF) : (b += 1) {
        const byte: u8 = @intCast(b);
        const dec = try decodeInt(&[_]u8{ '1', byte });
        try std.testing.expectEqual(@as(u32, 1), dec.value);
        try std.testing.expectEqual(@as(usize, 1), dec.len);
    }
}

test "delta §6: masking the high bit would diverge on a crafted digit byte" {
    // 0xB0 = 0x30 | 0x80 = '0' | 0x80. §6 lines 567-570: a decoder that
    // masks the high bit before lookup would read this as digit '0' and
    // keep accumulating: (1*64+0)*64+2 = 4098, len 3 - "a parse result
    // that diverges from conformant implementations". Conformant: 0xB0
    // terminates at index 1; the trailing '2' is never reached.
    const dec = try decodeInt(&[_]u8{ '1', 0xB0, '2' });
    try std.testing.expectEqual(@as(u32, 1), dec.value);
    try std.testing.expectEqual(@as(usize, 1), dec.len);
}

test "delta §6: a high-bit byte in count position is rejected by apply" {
    // Header declares target_len 3; the segment's count integer starts
    // with 0xB0, which terminates immediately (count = 0, consuming zero
    // bytes), so the opcode byte examined is 0xB0 itself - not in
    // {@, :, ;} - matrix #10 (unknown opcode). Confirms the §6 terminator
    // behavior propagates through the real decode path, not just the
    // isolated codec.
    try expectMalformed("abc", "3\n" ++ &[_]u8{0xB0} ++ "@0,");
}

test "delta §6: conformant encoder never emits a byte >= 0x80" {
    // §6 line 571: "Well-formed deltas are unaffected, as conformant
    // encoders never emit such bytes." digit64 (§3.1) spans 0x30-0x7E.
    var buf: [6]u8 = undefined;
    for ([_]u32{ 0, 1, 63, 64, 0xFFFF_FFFF }) |v| {
        const enc = encodeInt(v, &buf);
        for (enc) |byte| try std.testing.expect(byte < 0x80);
    }

    const target = "the quick brown fox jumps over the lazy dog";
    const d = try create(std.testing.allocator, "source text", target);
    defer std.testing.allocator.free(d);
    for (d) |byte| try std.testing.expect(byte < 0x80);
}

test "checksum: modulo 2^32, big-endian words + tail (Section 3.4)" {
    try std.testing.expectEqual(@as(u32, 0), checksum(""));
    try std.testing.expectEqual(@as(u32, 42), checksum(&[_]u8{ 0, 0, 0, 42 }));
    try std.testing.expectEqual(@as(u32, 0x0100_0000), checksum(&[_]u8{1})); // 1-byte tail
    try std.testing.expectEqual(@as(u32, 0x0000_2A00), checksum(&[_]u8{ 0, 0, 42 })); // 3-byte tail
}

// ---------------------------------------------------------------------------
// apply() — Section 4 procedure and rejection matrix.
// ---------------------------------------------------------------------------

fn expectMalformed(source: []const u8, delta_bytes: []const u8) !void {
    try std.testing.expectError(Error.MalformedDelta, apply(std.testing.allocator, source, delta_bytes));
}

fn expectChecksumMismatch(source: []const u8, delta_bytes: []const u8) !void {
    try std.testing.expectError(Error.ChecksumMismatch, apply(std.testing.allocator, source, delta_bytes));
}

test "delta §4: worked example reconstructs the 151-byte target" {
    // Appendix B.1: 102-byte source, 151-byte target, 79-byte delta.
    const source = "The quick brown fox jumps over the lazy dog. A Fossil delta encodes byte-level differences compactly.\n";
    const target = "The quick brown fox jumps over the sleeping fox. A Fossil delta encodes byte-level differences compactly.\n An example delta target with appended tail.\n";
    const delta_bytes = "2N\n" ++ "Z@0," ++ "C:" ++ "sleeping fox" ++ "w@g," ++ "i:" ++ " An example delta target with appended tail.\n" ++ "2P4rrX" ++ ";";
    try std.testing.expectEqual(@as(usize, 102), source.len);
    try std.testing.expectEqual(@as(usize, 151), target.len);
    try std.testing.expectEqual(@as(usize, 79), delta_bytes.len);

    const result = try apply(std.testing.allocator, source, delta_bytes);
    defer std.testing.allocator.free(result);
    try std.testing.expectEqualStrings(target, result);
    try std.testing.expectEqual(@as(usize, 151), result.len);
    // B.1/B.3: trailer 2P4rrX decodes to 2568187297 (0x99136DA1), matching
    // checksum() applied independently to the target.
    try std.testing.expectEqual(@as(u32, 2568187297), checksum(target));
}

test "delta §4: empty-target delta 0\\n0; is accepted" {
    // Appendix B.4: header 0, no segments, trailer checksum 0 (of a 0-byte output).
    const result = try apply(std.testing.allocator, "", "0\n0;");
    defer std.testing.allocator.free(result);
    try std.testing.expectEqual(@as(usize, 0), result.len);
}

test "delta §4: zero-length delta is rejected" {
    try expectMalformed("", "");
}

test "delta §4: header integer not followed by 0x0a is rejected" {
    try expectMalformed("", "1:a;");
}

test "delta §4: integer accumulation exhausting the buffer is rejected" {
    try expectMalformed("", "5\n9");
}

test "delta §4: copy segment without a comma is rejected" {
    try expectMalformed("abcdef", "3\n3@0;");
}

test "delta §4: copy past the target length is rejected" {
    try expectMalformed("abcdef", "2\n3@0,");
}

test "delta §4: copy past the source end is rejected" {
    try expectMalformed("abc", "5\n5@0,");
}

test "delta §4: literal past the target length is rejected" {
    try expectMalformed("", "2\n5:hello;");
}

test "delta §4: literal count exceeding remaining delta is rejected" {
    try expectMalformed("", "9\n5:ab");
}

test "delta §4: checksum mismatch is rejected" {
    // checksum("A") = 0x41000000 (1-byte tail, §3.4); trailer int here is 0.
    try expectChecksumMismatch("", "1\n1:A0;");
}

test "delta §4: output shorter than target length is rejected" {
    try expectMalformed("", "5\n1:A0;");
}

test "delta §4: unknown opcode byte is rejected" {
    try expectMalformed("abc", "3\n3!");
}

test "delta §4: delta ending without ';' is rejected" {
    try expectMalformed("abc", "3\n3@0,");
}

// ---------------------------------------------------------------------------
// §4 segmentation independence and §4.1 target-size query.
// ---------------------------------------------------------------------------

test "delta §4: differently-segmented deltas for one target are all accepted" {
    // source = target = "AB" (2 bytes); trailer 11GW00 = base-64 MSB-first
    // encoding of checksum("AB") = 0x41420000 (§3.4: one 2-byte tail word,
    // 'A'<<24 | 'B'<<16). A decoder MUST NOT reject any of these on the
    // grounds of segmentation, copy-vs-literal choice, or segment count.
    const source = "AB";
    const target = "AB";
    const deltas = [_][]const u8{
        "2\n2@0,11GW00;", // single copy
        "2\n1:A1:B11GW00;", // two literals
        "2\n2:AB11GW00;", // single literal
    };
    var i: usize = 0;
    while (i < deltas.len) : (i += 1) {
        const result = try apply(std.testing.allocator, source, deltas[i]);
        defer std.testing.allocator.free(result);
        try std.testing.expectEqualStrings(target, result);
    }
}

test "delta §4.1: target-size query reads only the header, not later bytes" {
    // "2N" = 2*64 + 23 ('N' is digit64 value 23) = 151, the Appendix B.1
    // target length. Each tail is malformed or unrelated; none is read.
    const cases = [_][]const u8{
        "2N\n",
        "2N\nZ@0,<garbage>",
        "2N\n!!!bad-opcode",
        "2N\n" ++ "Z@0," ++ "C:" ++ "sleeping fox" ++ "w@g," ++ "i:" ++ " An example delta target with appended tail.\n" ++ "2P4rrX" ++ ";",
    };
    var i: usize = 0;
    while (i < cases.len) : (i += 1) {
        try std.testing.expectEqual(@as(usize, 151), try targetSize(cases[i]));
    }
}

test "delta §4.1: target-size query rejects an empty buffer" {
    try std.testing.expectError(Error.MalformedDelta, targetSize(""));
}

test "delta §4.1: target-size query rejects a header not immediately followed by 0x0a" {
    // "5": the integer runs to the buffer end, so nothing follows it at all.
    // "5 \n": 0x20 is not a DIGIT64 char (§3.1), so decodeInt stops after '5'
    // and the next byte is a space, not 0x0a.
    const cases = [_][]const u8{ "5", "5 \n" };
    var i: usize = 0;
    while (i < cases.len) : (i += 1) {
        try std.testing.expectError(Error.MalformedDelta, targetSize(cases[i]));
    }
}

test "delta §4.1: no bytes required after the header LF" {
    try std.testing.expectEqual(@as(usize, 0), try targetSize("0\n"));
    try std.testing.expectEqual(@as(usize, 151), try targetSize("2N\n"));
}

// ---------------------------------------------------------------------------
// create() — Section 5 encoder notes.
// ---------------------------------------------------------------------------

test "delta §5: create() then apply() round-trips the target" {
    const long_source = "The quick brown fox jumps over the lazy dog. A Fossil delta encodes byte-level differences compactly.\n";
    const long_target = "The quick brown fox jumps over the sleeping fox. A Fossil delta encodes byte-level differences compactly.\n An example delta target with appended tail.\n";
    const embedded = "line1\nline2:tag@marker;end\x00\xff";
    const cases = [_]struct { source: []const u8, target: []const u8 }{
        .{ .source = "", .target = "" }, // empty target, zero-length source
        .{ .source = "x", .target = "" }, // empty target, nonzero source
        .{ .source = "", .target = "A" }, // single byte, zero-length source
        .{ .source = "abcdefghijklmnop", .target = "z" }, // source == 16 bytes (boundary)
        .{ .source = "abcdefghijklmnopq", .target = "z" }, // source > 16 bytes
        .{ .source = "abc", .target = embedded }, // embedded 0x0a, ':', '@', ';', 0x00, 0xff
        .{ .source = long_source, .target = long_target }, // Appendix B.1 sizes (102/151 bytes)
    };
    var i: usize = 0;
    while (i < cases.len) : (i += 1) {
        const d = try create(std.testing.allocator, cases[i].source, cases[i].target);
        defer std.testing.allocator.free(d);
        const out = try apply(std.testing.allocator, cases[i].source, d);
        defer std.testing.allocator.free(out);
        try std.testing.expectEqualStrings(cases[i].target, out);
    }
}

test "delta §5: create() compresses a target that overlaps the source" {
    // The delta's purpose (§5): exploit shared runs. For a source > 16 bytes and
    // a target that shares a long prefix/suffix, the encoder MUST emit at least
    // one copy and the delta MUST be strictly smaller than the target — a
    // literal-only producer would fail both.
    const source = "The quick brown fox jumps over the lazy dog and keeps on running.\n";
    const target = "The quick brown fox jumps over the lazy dog and then stops running.\n";
    const d = try create(std.testing.allocator, source, target);
    defer std.testing.allocator.free(d);
    try std.testing.expect(std.mem.indexOfScalar(u8, d, '@') != null); // used a copy
    try std.testing.expect(d.len < target.len); // actually compressed
    const out = try apply(std.testing.allocator, source, d);
    defer std.testing.allocator.free(out);
    try std.testing.expectEqualStrings(target, out); // and still reconstructs exactly
}

test "delta §5: create() emits a §3.3 literal and §3.4 trailer" {
    // checksum("A") = 0x41000000 (1-byte tail, §3.4); encodeInt(0x41000000)
    // (§3.1, remainders LSB->MSB 0,0,0,0,1,1, MSB-first) = "110000".
    const d = try create(std.testing.allocator, "unused source", "A");
    defer std.testing.allocator.free(d);
    try std.testing.expectEqualStrings("1\n1:A110000;", d);
}

test "delta §B.4: create() of an empty target is 0\\n0;" {
    const d = try create(std.testing.allocator, "any source at all", "");
    defer std.testing.allocator.free(d);
    try std.testing.expectEqualStrings("0\n0;", d);
}

test "delta §5: source <= 16 bytes yields a single literal (no copy)" {
    const source = "ABCDEFGHIJKLMNOP"; // 16 bytes, boundary
    const target = "ABCDEFGHIJKLMNOP";
    const d = try create(std.testing.allocator, source, target);
    defer std.testing.allocator.free(d);

    try std.testing.expectEqual(@as(?usize, null), std.mem.indexOfScalar(u8, d, '@'));
    try std.testing.expectEqualStrings("G\nG:", d[0..4]); // 16 = 'G' (§3.1: A=10..G=16)
    try std.testing.expectEqualStrings(target, d[4..20]);
    try std.testing.expectEqual(@as(u8, ';'), d[d.len - 1]);
    const trailer = try decodeInt(d[20 .. d.len - 1]);
    try std.testing.expectEqual(checksum(target), trailer.value);
}

test "delta §3.1: create() rejects a target of 2^32 bytes or more" {
    if (@bitSizeOf(usize) < 33) return; // a length >= 2^32 is unrepresentable on 32-bit
    var byte: u8 = 0;
    const len: usize = @as(usize, 1) << 32;
    const huge_target = @as([*]const u8, @ptrCast(&byte))[0..len]; // never dereferenced past index 0: the guard returns first
    try std.testing.expectError(CreateError.TargetTooLarge, create(std.testing.allocator, "", huge_target));
}

fn createNoLeak(allocator: std.mem.Allocator, source: []const u8, target: []const u8) !void {
    const out = try create(allocator, source, target);
    allocator.free(out);
}

test "delta §5: create() propagates allocation failure" {
    try std.testing.checkAllAllocationFailures(std.testing.allocator, createNoLeak, .{ "src", "some target bytes" });
}

fn applyNoLeak(allocator: std.mem.Allocator, source: []const u8, delta_bytes: []const u8) !void {
    const out = try apply(allocator, source, delta_bytes);
    allocator.free(out);
}

test "delta §4: apply propagates allocation failure" {
    // Reuses the Appendix B.1 worked example: a valid delta that exercises
    // apply()'s one allocation site (the output buffer) under a failing
    // allocator, confirming the errdefer frees it on every failure point.
    const source = "The quick brown fox jumps over the lazy dog. A Fossil delta encodes byte-level differences compactly.\n";
    const delta_bytes = "2N\n" ++ "Z@0," ++ "C:" ++ "sleeping fox" ++ "w@g," ++ "i:" ++ " An example delta target with appended tail.\n" ++ "2P4rrX" ++ ";";
    try std.testing.checkAllAllocationFailures(std.testing.allocator, applyNoLeak, .{ source, delta_bytes });
}

// ---------------------------------------------------------------------------
// Seeded deterministic fuzz / property tests. A fixed seed drives every draw,
// so a failure reproduces exactly and each block runs under plain `zig build
// test`. The 0.16 coverage-guided std.testing.fuzz (Smith) harness is an
// optional add-on, not relied on here.
// ---------------------------------------------------------------------------

test "delta fuzz: apply on arbitrary source+delta never crashes (§4 robustness)" {
    const a = std.testing.allocator;
    var prng = std.Random.DefaultPrng.init(0xF0FA_0001);
    const rand = prng.random();
    var round: usize = 0;
    while (round < 400) : (round += 1) {
        var sbuf: [128]u8 = undefined;
        var dbuf: [160]u8 = undefined;
        const slen = rand.uintLessThan(usize, sbuf.len + 1);
        const dlen = rand.uintLessThan(usize, dbuf.len + 1);
        for (sbuf[0..slen]) |*b| b.* = rand.int(u8);
        // Bias delta bytes toward DIGIT64/opcodes so inputs reach deep into the
        // decoder rather than being rejected at byte 0.
        for (dbuf[0..dlen]) |*b| b.* = if (rand.boolean())
            rand.int(u8)
        else
            digit64[rand.uintLessThan(usize, digit64.len)];
        // Contract: a value or a declared error — never a crash or UB.
        if (apply(a, sbuf[0..slen], dbuf[0..dlen])) |out| a.free(out) else |_| {}
    }
}

test "delta fuzz: apply(source, create(source, target)) == target (§5 round-trip)" {
    const a = std.testing.allocator;
    var prng = std.Random.DefaultPrng.init(0xF0FA_0002);
    const rand = prng.random();
    var round: usize = 0;
    while (round < 400) : (round += 1) {
        var sbuf: [256]u8 = undefined;
        const slen = rand.uintLessThan(usize, sbuf.len + 1);
        for (sbuf[0..slen]) |*b| b.* = rand.int(u8);
        const source = sbuf[0..slen];
        // Build target from a mix of source runs (exercises copies) and fresh
        // random bytes (exercises literals).
        var tbuf: [384]u8 = undefined;
        const tlen = rand.uintLessThan(usize, tbuf.len + 1);
        var t: usize = 0;
        while (t < tlen) {
            if (slen >= 8 and rand.boolean()) {
                const start = rand.uintLessThan(usize, slen);
                const run = 1 + rand.uintLessThan(usize, @min(slen - start, tlen - t));
                @memcpy(tbuf[t..][0..run], source[start..][0..run]);
                t += run;
            } else {
                tbuf[t] = rand.int(u8);
                t += 1;
            }
        }
        const target = tbuf[0..tlen];
        const d = try create(a, source, target);
        defer a.free(d);
        const out = try apply(a, source, d);
        defer a.free(out);
        try std.testing.expectEqualSlices(u8, target, out);
    }
}

test "delta fuzz: decodeInt on arbitrary digit strings stays bounded (§3.1)" {
    var prng = std.Random.DefaultPrng.init(0xF0FA_0003);
    const rand = prng.random();
    var round: usize = 0;
    while (round < 400) : (round += 1) {
        var buf: [40]u8 = undefined;
        const len = rand.uintLessThan(usize, buf.len + 1);
        // Bias toward DIGIT64 so long all-digit runs (overflow candidates) occur.
        for (buf[0..len]) |*b| b.* = if (rand.uintLessThan(u8, 4) == 0)
            rand.int(u8)
        else
            digit64[rand.uintLessThan(usize, digit64.len)];
        if (decodeInt(buf[0..len])) |dec| {
            try std.testing.expect(dec.len <= len); // consumed no more than the input
        } else |err| {
            try std.testing.expect(err == error.MalformedDelta); // rejection is the only error
        }
    }
}

test "delta fuzz: targetSize on arbitrary bytes never crashes (§4.1 robustness)" {
    var prng = std.Random.DefaultPrng.init(0xF0FA_0004);
    const rand = prng.random();
    var round: usize = 0;
    while (round < 400) : (round += 1) {
        var buf: [64]u8 = undefined;
        const len = rand.uintLessThan(usize, buf.len + 1);
        for (buf[0..len]) |*b| b.* = if (rand.boolean())
            rand.int(u8)
        else
            digit64[rand.uintLessThan(usize, digit64.len)];
        // Contract: a value bounded by decodeInt's u32 cap, or MalformedDelta
        // — never a crash or UB.
        if (targetSize(buf[0..len])) |size| {
            try std.testing.expect(size <= std.math.maxInt(u32));
        } else |err| {
            try std.testing.expect(err == error.MalformedDelta);
        }
    }
}