//! 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 two primitives that the rest of the format is
//! built on — the base-64 integer codec (Section 3.1) and the checksum
//! (Section 3.4) — and stubs the apply/create procedures (Section 4).
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,
NotImplemented,
};
// ---------------------------------------------------------------------------
// 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.
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) — TODO
// ---------------------------------------------------------------------------
/// 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.
}
/// Produce a delta that reconstructs `target` from `source`.
pub fn create(allocator: std.mem.Allocator, source: []const u8, target: []const u8) Error![]u8 {
_ = allocator;
_ = source;
_ = target;
return Error.NotImplemented;
}
// ---------------------------------------------------------------------------
// 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 "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"));
}