Skip to content
zit Artifact [d489bfd517]
Login

Artifact [d489bfd517]

Check-ins Using Download Hex

Artifact d489bfd517759021e4f006355c1b9f99717ceda2068739eb3a9f84e291a95a89:

//! 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;

    // Split the whole words off up front. Their count then belongs to the slice
    // instead of being re-derived by the loop's `i + 4 <= data.len` guard, so the
    // walk is a bounded counter over fixed-size elements and each word is one
    // whole-array load with no length left to check.
    const whole = data.len - data.len % 4;
    const words: []const [4]u8 = @ptrCast(data[0..whole]);
    for (words) |*w| sum +%= std.mem.readInt(u32, w, .big);

    const rem = data[whole..]; // fewer than four bytes
    if (rem.len >= 1) sum +%= @as(u32, rem[0]) << 24;
    if (rem.len >= 2) sum +%= @as(u32, rem[1]) << 16;
    if (rem.len >= 3) sum +%= @as(u32, rem[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);
}

/// The non-overlapping `encoder_block`-byte source blocks, keyed by the Wyhash
/// of the block's bytes and holding the *latest* offset per key (`matchAt`'s
/// byte-verification is what makes an overwrite harmless).
///
/// Open-addressed with linear probing over a capacity fixed up front from the
/// block count. `std.AutoHashMap` was the obvious spelling of this and cost
/// three things the scan pays for on every target byte: the map re-hashes the
/// already-hashed `u64` key on each lookup and insert, it grows and rehashes
/// its way up to size, and it carries per-slot metadata this index has no use
/// for. Here the block count is known before the first insert, so the capacity
/// is a single up-front allocation and the probe's termination is a stated
/// invariant rather than a load-factor policy.
///
/// Keying on the block hash — not on the block's bytes — is deliberate: it is
/// what makes the index's answer, and therefore the encoder's output, exactly
/// what `std.AutoHashMap` produced. A content-keyed table would find matches
/// through a hash collision that this one misses, which is a *better* delta but
/// a different one.
const BlockIndex = struct {
    /// Block hash per slot; meaningful only where `offs[s] != empty_off`.
    keys: []u64,
    /// Source offset per slot, or `empty_off`.
    offs: []u32,
    /// `capacity - 1`. Capacity is a power of two, so this masks a hash to a slot.
    mask: usize,
    /// Occupied slots; at most half of capacity (see `build`).
    len: usize,

    /// `create` rejects sources of 2^32 bytes or more (§3.1) and indexes only
    /// offsets satisfying `off + encoder_block <= source.len`, so no real offset
    /// can reach `maxInt(u32)` — it is free to mark a slot empty.
    const empty_off: u32 = std.math.maxInt(u32);

    fn build(allocator: std.mem.Allocator, source: []const u8) std.mem.Allocator.Error!BlockIndex {
        std.debug.assert(source.len > encoder_block);
        // Both the `empty_off` sentinel and the `catch unreachable` below rest
        // on this; `create` establishes it three frames up, so restate it here
        // as a checked precondition of this function rather than as prose.
        std.debug.assert(source.len <= std.math.maxInt(u32));
        const blocks = source.len / encoder_block; // >= 1
        // At least twice the block count, so the table is never more than half
        // full. That is the entire termination argument for the probe loops
        // below: an empty slot always lies ahead of any probe. `create` has
        // already refused sources of 2^32 bytes or more, which bounds `blocks`
        // below 2^28, so the round-up cannot overflow.
        const capacity = std.math.ceilPowerOfTwo(usize, 2 * blocks) catch unreachable;
        std.debug.assert(capacity >= 2 * blocks);

        const offs = try allocator.alloc(u32, capacity);
        errdefer allocator.free(offs);
        @memset(offs, empty_off);
        // `keys` is deliberately left uninitialized: `offs` is the occupancy
        // map, and both `put` and `get` test `offs[s] == empty_off` BEFORE they
        // touch `keys[s]`, so no undefined byte is ever read. The two arrays
        // have to stay in that order.
        const keys = try allocator.alloc(u64, capacity);

        var self: BlockIndex = .{ .keys = keys, .offs = offs, .mask = capacity - 1, .len = 0 };
        var i: usize = 0;
        while (i + encoder_block <= source.len) : (i += encoder_block) {
            self.put(std.hash.Wyhash.hash(0, source[i..][0..encoder_block]), @intCast(i));
        }
        std.debug.assert(self.len <= blocks);
        return self;
    }

    fn deinit(self: *BlockIndex, allocator: std.mem.Allocator) void {
        allocator.free(self.keys);
        allocator.free(self.offs);
    }

    /// Record `off` under `key`, displacing any offset already held there: the
    /// index keeps the latest block per key.
    fn put(self: *BlockIndex, key: u64, off: u32) void {
        std.debug.assert(off != empty_off);
        var s: usize = @as(usize, @truncate(key)) & self.mask;
        // Bounded by capacity: the table is never more than half full, so an
        // empty slot always lies ahead and this returns long before the bound.
        // The bound turns a broken capacity invariant into a trap instead of a
        // hang. It is carried by a counter gated on `std.debug.runtime_safety`
        // — present in ReleaseSafe, compiled out of ReleaseFast — and
        // measurement is why: written instead as an unconditional
        // `for (0..capacity)` here and in `get`, it cost 12% of the whole
        // import in ReleaseFast for 0.8% in ReleaseSafe. Gated, it costs
        // neither mode measurable time.
        var probes: usize = 0;
        while (true) : (s = (s + 1) & self.mask) {
            if (std.debug.runtime_safety) {
                probes += 1;
                std.debug.assert(probes <= self.mask + 1); // half-full invariant broken
            }
            if (self.offs[s] == empty_off) {
                self.keys[s] = key;
                self.offs[s] = off;
                self.len += 1;
                std.debug.assert(self.len * 2 <= self.mask + 1);
                return;
            }
            if (self.keys[s] == key) {
                self.offs[s] = off;
                return;
            }
        }
    }

    /// Latest offset recorded under `key`, or null.
    fn get(self: *const BlockIndex, key: u64) ?u32 {
        var s: usize = @as(usize, @truncate(key)) & self.mask;
        // Bounded for the same reason as `put`, and gated the same way. This
        // probe runs once per target byte — the hottest loop in the encoder.
        var probes: usize = 0;
        while (true) : (s = (s + 1) & self.mask) {
            if (std.debug.runtime_safety) {
                probes += 1;
                std.debug.assert(probes <= self.mask + 1); // half-full invariant broken
            }
            const off = self.offs[s];
            if (off == empty_off) return null;
            if (self.keys[s] == key) return off;
        }
    }
};

/// 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: *const BlockIndex) ?usize {
    if (t + encoder_block > target.len) return null;
    const window = target[t..][0..encoder_block];
    const off: usize = index.get(std.hash.Wyhash.hash(0, window)) orelse return null;
    // `index` and `source` are separate parameters, and the offset below is
    // only in bounds for the exact source the index was built over. State that
    // coupling here: it costs one compare on a hash hit, not one per byte.
    std.debug.assert(off + encoder_block <= source.len);
    // Both sides are `encoder_block`-length arrays, not slices, so the
    // verification is one whole-window load and compare with no length to check.
    comptime std.debug.assert(encoder_block == @sizeOf(u128));
    const found: u128 = @bitCast(source[off..][0..encoder_block].*);
    if (found != @as(u128, @bitCast(window.*))) 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');

    // 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.
    //
    // §5: a source of encoder_block bytes or fewer holds no indexable block, so
    // no copy is possible and the scan can only walk `t` to the end — the whole
    // target is the one literal the final flush emits.
    var lit_start: usize = 0;
    if (source.len > encoder_block) {
        var index = try BlockIndex.build(allocator, source);
        defer index.deinit(allocator);

        var t: usize = 0;
        while (t < target.len) {
            if (matchAt(source, target, t, &index)) |o| {
                // Grow the verified window. Both remainders are cut to one
                // common length first, which is what the old loop's running
                // `o + len < source.len and t + len < target.len` guard was
                // computing a byte at a time; with the length hoisted, the walk
                // is a counter bounded by two equal-length slices and neither
                // load carries a check of its own. `matchAt` only returns an
                // offset whose window fits on both sides, so `max_len` is at
                // least `encoder_block` and the copy is never shorter than the
                // window that was verified.
                const max_len = @min(source.len - o, target.len - t);
                std.debug.assert(max_len >= encoder_block);
                const src_ext = source[o + encoder_block ..][0 .. max_len - encoder_block];
                const tgt_ext = target[t + encoder_block ..][0 .. max_len - encoder_block];
                var len: usize = max_len;
                for (src_ext, tgt_ext, 0..) |sb, tb, k| {
                    if (sb != tb) {
                        len = encoder_block + k;
                        break;
                    }
                }
                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);
}