Artifact a2774c0cb1799fab9eebf89bb85035e14a11af87f36349462d747b5c4b3b2b22:
- File
src/delta_test.zig
— part of check-in
[bfb63af209]
at
2026-08-04 13:30:54
on branch sub-manifest
— delta: replace the encoder's hash map with a fixed-capacity index
wapp import, user CPU: safe 1076s -> 540s, fast 95s -> 53s. Byte-identical output; the 14 pinned vectors are unchanged.
std.AutoHashMap(u64,u32) + Wyhash is gone. The window is now a comptime 16-byte array read through readInt, and the table is open-addressed with capacity from a bounded counter, so it is never more than half full -- that is the probe's termination argument, asserted rather than assumed.
Most of the safe-side win is not bounds checks. Wyhash.init declares a 48-byte buf as undefined, which runtime_safety poison-fills on every call, and the encoder hashed twice per position -- once for the window, once again inside the map on the resulting key. Removing the map removed both.
The probe's explicit bound sits inside `if (std.debug.runtime_safety)`: present in ReleaseSafe where it can trap, compiled out of ReleaseFast. Written unconditionally it cost 12.2% of the fast import; gated it costs nothing in either mode. (user: dmestas, size: 38794) [annotate] [blame] [check-ins using] [more...]
//! Unit tests for the delta format (draft-fossil-delta-format-00). //! //! Separated from the implementation per the kind-separation convention //! (mirrors the sibling `*_fuzz.zig` split). Every test here exercises only //! `delta`'s public surface; tests reaching file-private decls stay inline in //! `delta.zig`. const std = @import("std"); const delta = @import("delta.zig"); 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 = delta.encodeInt(v, &buf); const dec = try delta.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(delta.Error.MalformedDelta, delta.decodeInt("400000")); // 2^32 - 1 is the largest in-range value and must still decode. const max = try delta.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", delta.encodeInt(64, &buf)); try std.testing.expectEqualStrings("0", delta.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 delta.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 delta.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 = delta.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 delta.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), delta.checksum("")); try std.testing.expectEqual(@as(u32, 42), delta.checksum(&[_]u8{ 0, 0, 0, 42 })); try std.testing.expectEqual(@as(u32, 0x0100_0000), delta.checksum(&[_]u8{1})); // 1-byte tail try std.testing.expectEqual(@as(u32, 0x0000_2A00), delta.checksum(&[_]u8{ 0, 0, 42 })); // 3-byte tail } test "checksum: sliced-word form agrees with the §3.4 formula at every length" { // checksum() slices its whole words off up front so the walk is a bounded // counter; §3.4 is stated as an indexed loop. This runs both over the same // bytes at every length through 64 words, so each word count meets each of // the four tail cases. var buf: [259]u8 = undefined; var r = VecRng.init(0xC4EC_5011); r.fill(&buf); for (0..buf.len + 1) |n| { const data = buf[0..n]; var want: u32 = 0; var i: usize = 0; while (i + 4 <= data.len) : (i += 4) { want +%= (@as(u32, data[i]) << 24) | (@as(u32, data[i + 1]) << 16) | (@as(u32, data[i + 2]) << 8) | @as(u32, data[i + 3]); } const rem = data.len - i; if (rem >= 1) want +%= @as(u32, data[i]) << 24; if (rem >= 2) want +%= @as(u32, data[i + 1]) << 16; if (rem >= 3) want +%= @as(u32, data[i + 2]) << 8; try std.testing.expectEqual(want, delta.checksum(data)); } } // --------------------------------------------------------------------------- // apply() — Section 4 procedure and rejection matrix. // --------------------------------------------------------------------------- fn expectMalformed(source: []const u8, delta_bytes: []const u8) !void { try std.testing.expectError(delta.Error.MalformedDelta, delta.apply(std.testing.allocator, source, delta_bytes)); } fn expectChecksumMismatch(source: []const u8, delta_bytes: []const u8) !void { try std.testing.expectError(delta.Error.ChecksumMismatch, delta.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 delta.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), delta.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 delta.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 delta.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 delta.targetSize(cases[i])); } } test "delta §4.1: target-size query rejects an empty buffer" { try std.testing.expectError(delta.Error.MalformedDelta, delta.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(delta.Error.MalformedDelta, delta.targetSize(cases[i])); } } test "delta §4.1: no bytes required after the header LF" { try std.testing.expectEqual(@as(usize, 0), try delta.targetSize("0\n")); try std.testing.expectEqual(@as(usize, 151), try delta.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 delta.create(std.testing.allocator, cases[i].source, cases[i].target); defer std.testing.allocator.free(d); const out = try delta.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 delta.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 delta.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 delta.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 delta.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 delta.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 delta.decodeInt(d[20 .. d.len - 1]); try std.testing.expectEqual(delta.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(delta.CreateError.TargetTooLarge, delta.create(std.testing.allocator, "", huge_target)); } fn createNoLeak(allocator: std.mem.Allocator, source: []const u8, target: []const u8) !void { const out = try delta.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" }); } test "delta §5: create() propagates allocation failure while building the block index" { // The case above uses a 3-byte source, which never builds an index at all. // A source longer than encoder_block reaches the index's own allocations, // including the partial failure where the slot array is already held and // the key array is the one that fails. try std.testing.checkAllAllocationFailures(std.testing.allocator, createNoLeak, .{ "a source comfortably longer than one encoder_block, with a repeated tail, tail, tail", "a source comfortably longer than one encoder_block, and then some quite different bytes, tail", }); } fn applyNoLeak(allocator: std.mem.Allocator, source: []const u8, delta_bytes: []const u8) !void { const out = try delta.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 delta.digit64[rand.uintLessThan(usize, delta.digit64.len)]; // Contract: a value or a declared error — never a crash or UB. if (delta.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 delta.create(a, source, target); defer a.free(d); const out = try delta.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 delta.digit64[rand.uintLessThan(usize, delta.digit64.len)]; if (delta.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 delta.digit64[rand.uintLessThan(usize, delta.digit64.len)]; // Contract: a value bounded by decodeInt's u32 cap, or MalformedDelta // — never a crash or UB. if (delta.targetSize(buf[0..len])) |size| { try std.testing.expect(size <= std.math.maxInt(u32)); } else |err| { try std.testing.expect(err == error.MalformedDelta); } } } test "delta fuzz: create rejects synthetic sizes >= 2^32 without panicking (§3.1)" { if (@bitSizeOf(usize) < 33) return; // a length >= 2^32 is unrepresentable on 32-bit var prng = std.Random.DefaultPrng.init(0xF0FA_0005); const rand = prng.random(); var byte: u8 = 0; const min_len: usize = @as(usize, 1) << 32; const max_span: usize = (@as(usize, 1) << 40) - min_len; var round: usize = 0; while (round < 200) : (round += 1) { const len = min_len + rand.uintLessThan(usize, max_span + 1); const huge = @as([*]const u8, @ptrCast(&byte))[0..len]; // never dereferenced: the guard returns first const variant = rand.uintLessThan(u8, 3); // 0: source oversized, 1: target oversized, 2: both const source: []const u8 = if (variant == 1) "" else huge; const target: []const u8 = if (variant == 0) "" else huge; try std.testing.expectError(delta.CreateError.TargetTooLarge, delta.create(std.testing.allocator, source, target)); } } test "create: match extension stops on each of its three causes (§5)" { // The extension walk was reshaped from two running bounds into a counter // over two equal-length slices. Its stop condition has exactly three causes; // each case below puts it on one of them and pins the resulting delta byte // for byte, so a copy that runs one byte short or one byte long is a failure // rather than a merely different-but-valid encoding. const Case = struct { name: []const u8, source: []const u8, target: []const u8, copy_len: u32, tail: []const u8 }; const cases = [_]Case{ // Source runs out first: the copy takes all 20 source bytes, the extra // target byte falls out as the closing literal. .{ .name = "source exhausted", .source = "0123456789abcdefWXYZ", .target = "0123456789abcdefWXYZ!", .copy_len = 20, .tail = "1:!" }, // Target runs out first: the copy stops at 20 even though the source has // two more matching-length bytes to offer. .{ .name = "target exhausted", .source = "0123456789abcdefWXYZ!!", .target = "0123456789abcdefWXYZ", .copy_len = 20, .tail = "" }, // A differing byte stops it two bytes into the extension. .{ .name = "bytes differ", .source = "0123456789abcdefWXYZ", .target = "0123456789abcdefWXQQ", .copy_len = 18, .tail = "2:QQ" }, }; for (cases) |c| { var ibuf: [6]u8 = undefined; var want: std.ArrayList(u8) = .empty; defer want.deinit(std.testing.allocator); try want.appendSlice(std.testing.allocator, delta.encodeInt(@intCast(c.target.len), &ibuf)); try want.append(std.testing.allocator, '\n'); try want.appendSlice(std.testing.allocator, delta.encodeInt(c.copy_len, &ibuf)); try want.appendSlice(std.testing.allocator, "@0,"); // the only indexed block is at offset 0 try want.appendSlice(std.testing.allocator, c.tail); try want.appendSlice(std.testing.allocator, delta.encodeInt(delta.checksum(c.target), &ibuf)); try want.append(std.testing.allocator, ';'); const d = try delta.create(std.testing.allocator, c.source, c.target); defer std.testing.allocator.free(d); std.testing.expectEqualSlices(u8, want.items, d) catch |err| { std.debug.print("extension case '{s}' diverged\n", .{c.name}); return err; }; const back = try delta.apply(std.testing.allocator, c.source, d); defer std.testing.allocator.free(back); try std.testing.expectEqualSlices(u8, c.target, back); } } // --------------------------------------------------------------------------- // Pinned encoder vectors (§5) // // §5 is informative: any copy/literal segmentation that reproduces the target // is a valid delta, so nothing in the format forces THIS encoder's choices. // These vectors pin them anyway. They were captured from the encoder as it // stood at fossil check-in 4a7c197abd and exist so that a change made for // speed has to prove it changed no bytes -- byte-identity is the contract the // stores on disk are compared under, and a reshaped encoder that emits a // different (even smaller) delta is a different encoder, not a faster one. // // Between them the cases pin: the no-index path for a source of encoder_block // bytes or fewer; the first indexable source (17 bytes); a pure-literal // encoding; a long match extension; the index's latest-offset-per-key rule // (case 7 must copy from offset 32, not 0 or 16); the fact that a run shared // at an unindexed source offset yields no copy (case 8); a match window ending // exactly at target.len; wholly repetitive input; a target longer than its // source; a multi-KB mixed edit; and 512 near-identical blocks whose keys // stress an index's probe behaviour. // --------------------------------------------------------------------------- /// xorshift64* written out longhand: the vectors must not move if std's /// Random implementation ever changes. const VecRng = struct { s: u64, fn init(seed: u64) VecRng { return .{ .s = seed | 1 }; } fn next(self: *VecRng) u64 { var x = self.s; x ^= x >> 12; x ^= x << 25; x ^= x >> 27; self.s = x; return x *% 0x2545F4914F6CDD1D; } fn byte(self: *VecRng) u8 { return @truncate(self.next() >> 33); } fn below(self: *VecRng, n: usize) usize { return @intCast(self.next() % n); } fn fill(self: *VecRng, buf: []u8) void { for (buf) |*b| b.* = self.byte(); } }; const VecCase = struct { name: []const u8, source: []const u8, target: []const u8, }; const vec_case_count = 14; /// Build case `i`. Every returned slice is owned by `arena`. fn buildCase(arena: std.mem.Allocator, i: usize) !VecCase { switch (i) { // --- degenerate ------------------------------------------------ 0 => return .{ .name = "empty source, empty target", .source = "", .target = "" }, 1 => return .{ .name = "empty source, short target", .source = "", .target = "hello, delta" }, 2 => return .{ .name = "source shorter than encoder_block", .source = "0123456789abcde", .target = "0123456789abcde0123456789abcde" }, 3 => return .{ .name = "source exactly encoder_block", .source = "0123456789abcdef", .target = "0123456789abcdef0123456789abcdef" }, // --- first indexed source (17 bytes) --------------------------- 4 => return .{ .name = "source one byte past encoder_block", .source = "0123456789abcdefg", .target = "0123456789abcdefg" }, // --- literal only ---------------------------------------------- 5 => { const src = try arena.alloc(u8, 4096); const tgt = try arena.alloc(u8, 4096); var r = VecRng.init(0x51ED); r.fill(src); var r2 = VecRng.init(0xC0FFEE); r2.fill(tgt); return .{ .name = "literal only (independent random source/target)", .source = src, .target = tgt }; }, // --- long match extension -------------------------------------- 6 => { const src = try arena.alloc(u8, 4096); var r = VecRng.init(0xA11CE); r.fill(src); return .{ .name = "long extension: target is an interior run of source", .source = src, .target = src[100..3000] }; }, // --- last-wins index semantics --------------------------------- 7 => { // Same 16-byte block at aligned offsets 0, 16 and 32. The index // keeps the LAST offset per hash, so the copy must name 32. const blk = "BLOCKblockBLOCKb"; var buf: std.ArrayList(u8) = .empty; try buf.appendSlice(arena, blk); try buf.appendSlice(arena, blk); try buf.appendSlice(arena, blk); try buf.appendSlice(arena, "tail-that-differs-entirely-here!"); return .{ .name = "repeated aligned block pins last-wins index", .source = try buf.toOwnedSlice(arena), .target = blk }; }, // --- unaligned-only match is NOT indexed ----------------------- 8 => { // The only 16-byte run shared with the target starts at source // offset 7, which no non-overlapping block covers, so the encoder // must emit a pure literal. const src = "AAAAAAA" ++ "UNIQUE-RUN-HERE!" ++ "BBBBBBBBBBBBBBBBBBBBBBBBB"; return .{ .name = "shared run at an unindexed offset stays literal", .source = src, .target = "UNIQUE-RUN-HERE!" }; }, // --- boundary: match ends exactly at target end ----------------- 9 => { const src = try arena.alloc(u8, 1024); var r = VecRng.init(0xBEEF); r.fill(src); // target = 32-byte prefix of an aligned source block; the last // match window ends exactly at target.len. return .{ .name = "match window ends exactly at target end", .source = src, .target = src[64..96] }; }, // --- highly repetitive ----------------------------------------- 10 => { const src = try arena.alloc(u8, 8192); @memset(src, 0); const tgt = try arena.alloc(u8, 8192); @memset(tgt, 0); return .{ .name = "all-zero source and target", .source = src, .target = tgt }; }, // --- target longer than source --------------------------------- 11 => { const src = try arena.alloc(u8, 2048); var r = VecRng.init(0xD00D); r.fill(src); var buf: std.ArrayList(u8) = .empty; try buf.appendSlice(arena, "prefix that is not in the source at all, padded out a bit"); try buf.appendSlice(arena, src); try buf.appendSlice(arena, "suffix that is likewise absent from the source entirely"); try buf.appendSlice(arena, src[512..1536]); return .{ .name = "target longer than source, source embedded twice", .source = src, .target = try buf.toOwnedSlice(arena) }; }, // --- multi-KB mixed edit --------------------------------------- 12 => { const src = try arena.alloc(u8, 64 * 1024); var r = VecRng.init(0x5EED_1234); r.fill(src); var buf: std.ArrayList(u8) = .empty; // Three deletions, three insertions, three replacements, applied // left to right over the source. var pos: usize = 0; var e: usize = 0; while (e < 9) : (e += 1) { const run = 4096 + r.below(2048); const end = @min(src.len, pos + run); try buf.appendSlice(arena, src[pos..end]); pos = end; switch (e % 3) { 0 => pos = @min(src.len, pos + 700 + r.below(300)), // delete 1 => { // insert var ins: [512]u8 = undefined; r.fill(&ins); try buf.appendSlice(arena, &ins); }, else => { // replace var rep: [333]u8 = undefined; r.fill(&rep); try buf.appendSlice(arena, &rep); pos = @min(src.len, pos + 333); }, } } if (pos < src.len) try buf.appendSlice(arena, src[pos..]); return .{ .name = "multi-KB mixed insert/delete/replace", .source = src, .target = try buf.toOwnedSlice(arena) }; }, // --- many colliding-bucket blocks ------------------------------- 13 => { // 512 distinct aligned blocks that differ only in their last two // bytes: dense, adversarial for any index that keys on a prefix. var buf: std.ArrayList(u8) = .empty; var k: usize = 0; while (k < 512) : (k += 1) { try buf.appendSlice(arena, "commonprefix--"); try buf.append(arena, @truncate(k)); try buf.append(arena, @truncate(k >> 8)); } const src = try buf.toOwnedSlice(arena); // target walks the blocks backwards so copies come from all over. var tb: std.ArrayList(u8) = .empty; var j: usize = 512; while (j > 0) { j -= 1; try tb.appendSlice(arena, src[j * 16 ..][0..16]); } return .{ .name = "512 near-identical aligned blocks, reversed target", .source = src, .target = try tb.toOwnedSlice(arena) }; }, else => unreachable, } } const PinnedVector = struct { case: usize, len: usize, sha3: *const [64]u8, /// Full delta bytes, for cases small enough to read at a glance. bytes: ?[]const u8, }; const pinned_vectors = [_]PinnedVector{ .{ .case = 0, .len = 4, .sha3 = "19ff9322c0314782ad7af024cb2b23ae9463902ba011b92650a03de3d7783c76", .bytes = "0\n0;" }, .{ .case = 1, .len = 22, .sha3 = "23494eb5f5f4cd81b94a861f8ef0ba512dff1b877380ad41c2e556be744b5826", .bytes = "C\nC:hello, deltax~W4m;" }, .{ .case = 2, .len = 40, .sha3 = "c36ea8bd2da5b67c74bc050c8ac71f0a1dde1978ba0cf7e5754ec665338e42c5", .bytes = "U\nU:0123456789abcde0123456789abcde4CkkB;" }, .{ .case = 3, .len = 41, .sha3 = "50eba5631120dc9e2d73623029aecad8e1e9779971bb0e3d342c05915c23d8cd", .bytes = "W\nW:0123456789abcdef0123456789abcdef25u_;" }, .{ .case = 4, .len = 13, .sha3 = "10716f5c2219881506876e88864401bed4bd9f43df80093ab36456b1536706d2", .bytes = "H\nH@0,1c12xn;" }, .{ .case = 5, .len = 4111, .sha3 = "c3c12a6d41cd165bef23ba74585c262196ed1881d87c39cd0db68d2a50d61465", .bytes = null }, .{ .case = 6, .len = 30, .sha3 = "67eaf302c92b6350e0ba3ad52adbe4174d982bfe2bfd561cb29bd4670dfe81e4", .bytes = null }, .{ .case = 7, .len = 13, .sha3 = "ed828127d0c2ecb4b35c19a5186845e84333127922214dae4a6afc9e73800374", .bytes = "G\nG@W,10NKaW;" }, .{ .case = 8, .len = 27, .sha3 = "ddef1240f21819e983ce7c70f907182704f08db9120b7cb46414891d60eb226a", .bytes = "G\nG:UNIQUE-RUN-HERE!15Cz_C;" }, .{ .case = 9, .len = 14, .sha3 = "48886d5d2a4bd41a51c6e5083e9d8a25d092a2fa9a883db421860dc4af6644ce", .bytes = "W\nW@10,1G_qEr;" }, .{ .case = 10, .len = 3078, .sha3 = "e8d02e056139eba9aa68a1551e0a4fa57960079fc6f54bc4c981ca2b6d87f572", .bytes = null }, .{ .case = 11, .len = 137, .sha3 = "be3a89302692b1bf71b76dfeb6a13590035ee30b8f0e6c787191a2c620b4b38c", .bytes = null }, .{ .case = 12, .len = 2696, .sha3 = "e3688ff3364bcb28c1fef15027e8c1e9f7fee9e20d9cef9a80a0be024e85f63f", .bytes = null }, .{ .case = 13, .len = 2443, .sha3 = "235001b67ed0eff6e984af68f7b4175b7a47681774b8f8d3bb69af3dde249e9f", .bytes = null }, }; test "delta §5: create() output is byte-identical to the pinned vectors" { try std.testing.expectEqual(vec_case_count, pinned_vectors.len); for (pinned_vectors) |v| { var arena_state = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena_state.deinit(); const arena = arena_state.allocator(); const c = try buildCase(arena, v.case); const d = try delta.create(arena, c.source, c.target); // The vector is only meaningful if the delta still reconstructs. const back = try delta.apply(arena, c.source, d); try std.testing.expectEqualSlices(u8, c.target, back); if (v.bytes) |want| { std.testing.expectEqualSlices(u8, want, d) catch |err| { std.debug.print("pinned vector {d} ({s}) diverged\n", .{ v.case, c.name }); return err; }; } var digest: [32]u8 = undefined; std.crypto.hash.sha3.Sha3_256.hash(d, &digest, .{}); const got = std.fmt.bytesToHex(digest, .lower); std.testing.expectEqualStrings(v.sha3, &got) catch |err| { std.debug.print("pinned vector {d} ({s}): {d} bytes, wanted {d}\n", .{ v.case, c.name, d.len, v.len }); return err; }; try std.testing.expectEqual(v.len, d.len); } }