Something went wrong. Try again.
A Zig library that reads git repositories without running git, with log, show and diff output byte-identical to git's.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Deltas: an object stored as instructions for rebuilding it from another//! object, its base, as gitformat-pack(5) describes them. A delta begins//! with the base's size and the result's size, each in the pack's "size//! encoding" (seven bits a byte, least significant first, the top bit set//! on every byte but the last), and goes on with instructions, each//! appending to the result://!//! - a byte with its top bit set copies a range of the base: its low four//! bits say which of four little-endian offset bytes follow, the next//! three which of three size bytes, an absent byte being zero, and a//! size of zero meaning 0x10000;//! - a byte from 1 to 127 inserts that many bytes, which follow it;//! - a zero byte is reserved, and refused.//!//! Nothing here does I/O, so it can be fuzzed: the caller inflates the//! delta and supplies the base.
const std = @import("std");const Allocator = std.mem.Allocator;
const Diagnostics = @import("Diagnostics.zig");
/// The two sizes a delta begins with.pub const Header = struct { /// How big the base must be. base_size: u64, /// How big the result will be. result_size: u64, /// How many bytes the two sizes took: where the instructions begin. len: usize,};
/// Why a delta could not be applied:////// - `TruncatedDelta`: it ends in the middle of its sizes or of an/// instruction./// - `DeltaSizeOverflow`: a size too big for 64 bits./// - `DeltaBaseSizeMismatch`: the base is not the size the delta says./// - `DeltaReservedInstruction`: an instruction byte of zero./// - `DeltaCopyOutOfRange`: a copy from beyond the end of the base./// - `DeltaResultTooLong`: the instructions make more than the result's/// size./// - `DeltaResultTooShort`: they make less.pub const Error = error{ TruncatedDelta, DeltaSizeOverflow, DeltaBaseSizeMismatch, DeltaReservedInstruction, DeltaCopyOutOfRange, DeltaResultTooLong, DeltaResultTooShort,};
/// Reads one number in the size encoding from the start of `bytes`, and/// how many bytes it took.pub fn readSize(bytes: []const u8) error{ TruncatedDelta, DeltaSizeOverflow }!struct { value: u64, len: usize } { var value: u64 = 0; var shift: u7 = 0; for (bytes, 0..) |b, i| { const part: u64 = b & 0x7f; if (part != 0 and (shift >= 64 or part > @as(u64, std.math.maxInt(u64)) >> @intCast(shift))) return error.DeltaSizeOverflow; if (shift < 64) value |= part << @intCast(shift); if (b & 0x80 == 0) return .{ .value = value, .len = i + 1 }; shift +|= 7; } return error.TruncatedDelta;}
/// Reads the base and result sizes a delta begins with. Only those bytes/// are looked at, so `delta` may be just the start of one.pub fn parseHeader(delta: []const u8) error{ TruncatedDelta, DeltaSizeOverflow }!Header { const base = try readSize(delta); const result = try readSize(delta[base.len..]); return .{ .base_size = base.value, .result_size = result.value, .len = base.len + result.len };}
/// Applies `delta` to `base`, writing the result into `out`, which must be/// exactly as long as the delta's result size. Every instruction is/// checked, so a corrupt delta is an error rather than a read or a write/// out of bounds. `diag`'s detail says where in the delta it went wrong.pub fn apply(base: []const u8, delta: []const u8, out: []u8, diag: ?*Diagnostics) Error!void { const header = try parseHeader(delta); if (header.base_size != base.len) { if (diag) |d| d.setDetail("base is {d} bytes, delta expects {d}", .{ base.len, header.base_size }); return error.DeltaBaseSizeMismatch; } std.debug.assert(header.result_size == out.len); try run(base, delta, header, out, diag);}
/// Follows the instructions of `delta`, whose sizes are `header`, copying/// what they make into `out` if it is given, and checking them the same/// way whether it is or not: so a delta can be checked through, result/// size and all, before that size is allocated.fn run(base: []const u8, delta: []const u8, header: Header, out: ?[]u8, diag: ?*Diagnostics) Error!void { const result_size = header.result_size; var at = header.len; var made: u64 = 0; while (at < delta.len) { const op = delta[at]; const op_at = at; at += 1; if (op & 0x80 != 0) { var offset: u64 = 0; var size: u64 = 0; for (0..4) |i| if (op & (@as(u8, 1) << @intCast(i)) != 0) { if (at >= delta.len) return error.TruncatedDelta; offset |= @as(u64, delta[at]) << @intCast(8 * i); at += 1; }; for (0..3) |i| if (op & (@as(u8, 0x10) << @intCast(i)) != 0) { if (at >= delta.len) return error.TruncatedDelta; size |= @as(u64, delta[at]) << @intCast(8 * i); at += 1; }; if (size == 0) size = 0x10000; if (offset > base.len or size > base.len - offset) { if (diag) |d| d.setDetail("copy of {d} bytes from {d} at delta byte {d}", .{ size, offset, op_at }); return error.DeltaCopyOutOfRange; } if (size > result_size - made) return error.DeltaResultTooLong; if (out) |o| { const n: usize = @intCast(size); const from: usize = @intCast(offset); @memcpy(o[@intCast(made)..][0..n], base[from..][0..n]); } made += size; } else if (op != 0) { const n: usize = op; if (n > delta.len - at) return error.TruncatedDelta; if (n > result_size - made) return error.DeltaResultTooLong; if (out) |o| @memcpy(o[@intCast(made)..][0..n], delta[at..][0..n]); made += n; at += n; } else { if (diag) |d| d.setDetail("at delta byte {d}", .{op_at}); return error.DeltaReservedInstruction; } } if (made != result_size) return error.DeltaResultTooShort;}
/// Applies `delta` to `base` into memory from `gpa`, which the caller/// owns. A result too big to allocate is `OutOfMemory`. The delta is/// checked through before the result is allocated, so a delta of a few/// bytes claiming an enormous result is an error, not an allocation of/// that size: what is allocated is only ever what its instructions make.////// A result size over `max_size` is `ObjectTooLarge`, found from the/// delta's header before its instructions are even followed; null means/// no limit. That is the bound a delta that really does make what it/// claims needs: a few kilobytes of copies of 64 KiB each make gigabytes,/// and a chain of such deltas multiplies them.pub fn applyAlloc(gpa: Allocator, base: []const u8, delta: []const u8, max_size: ?u64, diag: ?*Diagnostics) (Error || Allocator.Error || error{ObjectTooLarge})![]u8 { const header = try parseHeader(delta); if (header.base_size != base.len) { if (diag) |d| d.setDetail("base is {d} bytes, delta expects {d}", .{ base.len, header.base_size }); return error.DeltaBaseSizeMismatch; } if (max_size) |max| if (header.result_size > max) { if (diag) |d| d.setDetail("delta makes {d} bytes, more than the limit of {d}", .{ header.result_size, max }); return error.ObjectTooLarge; }; try run(base, delta, header, null, diag); const size = std.math.cast(usize, header.result_size) orelse return error.OutOfMemory; const out = try gpa.alloc(u8, size); errdefer gpa.free(out); try apply(base, delta, out, diag); return out;}
const testing = std.testing;const fuzz_input = @import("testing/fuzz.zig");
test "the size encoding is read seven bits at a time, least significant first" { try testing.expectEqual(0, (try readSize(&.{0})).value); try testing.expectEqual(127, (try readSize(&.{0x7f})).value); const two = try readSize(&.{ 0x80 | 0x10, 0x01 }); try testing.expectEqual(0x90, two.value); try testing.expectEqual(2, two.len); try testing.expectError(error.TruncatedDelta, readSize(&.{0x80})); try testing.expectEqual(std.math.maxInt(u64), (try readSize(&.{ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01 })).value); try testing.expectError(error.DeltaSizeOverflow, readSize(&.{ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x02 })); // Zero bits past the 64th are harmless. try testing.expectEqual(1, (try readSize(&.{ 0x81, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x00 })).value);}
test "a delta copies from its base and inserts its own bytes" { const base = "the quick brown fox"; // Result: "the slow brown fox!", 19 bytes. const delta = [_]u8{ 19, 19, 0x90, 4, // copy 4 bytes from offset 0: "the " 4, 's', 'l', 'o', 'w', // insert "slow" 0x91, 9, 10, // copy 10 bytes from offset 9: " brown fox" 1, '!', }; var out: [19]u8 = undefined; try apply(base, &delta, &out, null); try testing.expectEqualStrings("the slow brown fox!", &out);
var small: [18]u8 = undefined; try testing.expectError(error.DeltaResultTooLong, apply(base, &[_]u8{ 19, 18 } ++ delta[2..], &small, null)); var big: [20]u8 = undefined; try testing.expectError(error.DeltaResultTooShort, apply(base, &[_]u8{ 19, 20 } ++ delta[2..], &big, null)); try testing.expectError(error.DeltaBaseSizeMismatch, apply(base[1..], &delta, &out, null)); try testing.expectError(error.DeltaReservedInstruction, apply(base, &[_]u8{ 19, 19, 0 }, &out, null)); try testing.expectError(error.TruncatedDelta, apply(base, &[_]u8{ 19, 19, 5, 'a' }, &out, null)); try testing.expectError(error.TruncatedDelta, apply(base, &[_]u8{ 19, 19, 0x91, 9 }, &out, null)); var diag: Diagnostics = .{}; try testing.expectError(error.DeltaCopyOutOfRange, apply(base, &[_]u8{ 19, 19, 0x91, 9, 11 }, &out, &diag)); try testing.expectEqualStrings("copy of 11 bytes from 9 at delta byte 2", diag.detail());}
test "a copy of size zero copies 0x10000 bytes" { const gpa = testing.allocator; const base = try gpa.alloc(u8, 0x10000); defer gpa.free(base); for (base, 0..) |*b, i| b.* = @truncate(i); // 0x10000 is 0x80 0x80 0x04 in the size encoding. const delta = [_]u8{ 0x80, 0x80, 0x04, 0x80, 0x80, 0x04, 0x80 }; const out = try applyAlloc(gpa, base, &delta, null, null); defer gpa.free(out); try testing.expectEqualSlices(u8, base, out);}
test "a result size the instructions do not make is refused before it is allocated" { var bounded: fuzz_input.Bounded = .{ .backing = testing.allocator, .limit = 1 << 20 }; const gpa = bounded.allocator(); // A base of three bytes, a result claimed at a terabyte, and one // insert of a byte: an error found only at the end of the // instructions, after the result would have been allocated. const short = [_]u8{ 0x03, 0x80, 0x80, 0x80, 0x80, 0x80, 0x20, 0x01, 'x' }; try testing.expectError(error.DeltaResultTooShort, applyAlloc(gpa, "abc", &short, null, null)); // And the errors are the ones applying it gives, in the same order. const reserved = [_]u8{ 0x03, 0x80, 0x80, 0x80, 0x80, 0x80, 0x20, 0x00 }; try testing.expectError(error.DeltaReservedInstruction, applyAlloc(gpa, "abc", &reserved, null, null)); const out_of_range = [_]u8{ 0x03, 0x80, 0x80, 0x80, 0x80, 0x80, 0x20, 0x91, 0x00, 0x04 }; try testing.expectError(error.DeltaCopyOutOfRange, applyAlloc(gpa, "abc", &out_of_range, null, null)); try bounded.check(); const exact = [_]u8{ 0x03, 0x04, 0x90, 0x03, 0x01, 'd' }; const out = try applyAlloc(gpa, "abc", &exact, null, null); defer gpa.free(out); try testing.expectEqualStrings("abcd", out);}
test "a result size over the limit is refused from the header, before anything is allocated" { var bounded: fuzz_input.Bounded = .{ .backing = testing.allocator, .limit = 64 }; const gpa = bounded.allocator(); // Three bytes of base, a result claimed at a terabyte, and copies of // 64 KiB that would really make it: refused without being followed. const huge = [_]u8{ 0x03, 0x80, 0x80, 0x80, 0x80, 0x80, 0x20, 0x80, 0x80, 0x80 }; var diag: Diagnostics = .{}; try testing.expectError(error.ObjectTooLarge, applyAlloc(gpa, "abc", &huge, 1 << 30, &diag)); try testing.expectEqualStrings("delta makes 1099511627776 bytes, more than the limit of 1073741824", diag.detail()); try bounded.check(); // A result exactly at the limit is made; one byte under it, refused. const four = [_]u8{ 0x03, 0x04, 0x90, 0x03, 0x01, 'd' }; const out = try applyAlloc(gpa, "abc", &four, 4, null); defer gpa.free(out); try testing.expectEqualStrings("abcd", out); try testing.expectError(error.ObjectTooLarge, applyAlloc(gpa, "abc", &four, 3, null));}
fn fuzzOne(_: void, smith: *testing.Smith) anyerror!void { var buffer: [512]u8 = undefined; const input = fuzz_input.bytes(smith, &buffer); // The first byte says how much of the rest is the base. if (input.len == 0) return; const split: usize = @min(@as(usize, input[0]), input.len - 1); const base = input[1..][0..split]; const delta = input[1 + split ..]; const header = parseHeader(delta) catch return; // A result claimed beyond the limit is refused before anything of its // size is allocated, whatever the instructions would make. const max: u64 = 1 << 20; var bounded: fuzz_input.Bounded = .{ .backing = testing.allocator, .limit = max + 1 }; const gpa = bounded.allocator(); const out = applyAlloc(gpa, base, delta, max, null) catch |err| { if (header.base_size == base.len and header.result_size > max) try testing.expectEqual(error.ObjectTooLarge, err); try bounded.check(); return; }; defer gpa.free(out); try testing.expectEqual(header.result_size, out.len); try bounded.check();}
test "fuzz: delta application" { try fuzz_input.fuzz({}, fuzzOne, .{ .corpus = &.{ @embedFile("fuzz/delta"), // A base of three bytes and a delta of seven claiming a result of // a terabyte. @embedFile("fuzz/delta-size-claim"), "\x13the quick brown fox\x13\x13\x90\x04\x04slow\x91\x09\x0a\x01!", }, });}