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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Changed-path Bloom filters, as a commit-graph keeps them//! (gitformat-commit-graph(5), the `BIDX` and `BDAT` chunks): for each//! commit, a small bit array saying which paths the commit may have//! changed relative to its first parent, so that a history limited to a//! path can pass over most commits without comparing trees.//!//! A path's key is two 32-bit murmur3 hashes of its bytes, with the seeds//! 0x293ae76f and 0x7e646e2c; its `i`th bit, for `i` below the number of//! hashes the `BDAT` header names, is `(h0 + i * h1) mod (8 * length)`,//! counted from the least significant bit of the filter's first byte.//! gitformat-commit-graph(5) prints the second seed as 0x7e646e2, which//! no filter git writes agrees with; 0x7e646e2c, found by checking the//! filters git wrote for known paths, is the one it uses.//!//! Version 1 of the hash reads each byte of the path as a signed `char`,//! sign-extended to 32 bits, in the four-byte blocks and the tail alike,//! which git's documentation calls a bug that shows with bytes of 0x80 and//! above; version 2 reads them unsigned, as murmur3 is defined. Both were//! found the same way, with paths holding such bytes.//!//! A filter of no bytes was not computed, and says nothing. A filter of one//! byte of zeros is a commit that changed nothing, and of one byte of ones//! a commit that changed too much to list: the first rules every path//! out, and the second none, by the same rule as any other filter.//!//! Nothing here does I/O.
const std = @import("std");
/// Which murmur3 a filter was made with.pub const Version = enum(u32) { /// Bytes read as signed. v1 = 1, /// Bytes read as unsigned, as murmur3 is defined. v2 = 2,};
/// The parameters at the start of a `BDAT` chunk.pub const Settings = struct { version: Version, /// How many bits each path sets. hashes: u32, /// The fewest bits a filter holds for each path; for reading, only a /// matter of record. bits_per_entry: u32,};
/// The most hashes a filter is read with. git writes seven; a header/// naming more than this makes the filters unusable rather than slow to/// read.pub const max_hashes = 255;
const seed0: u32 = 0x293ae76f;const seed1: u32 = 0x7e646e2c;
/// A path, hashed, ready to test against any filter of one version.pub const Key = struct { h0: u32, h1: u32,
/// The key of `path`, which is written as git names paths: relative /// to the top of the tree, `/` between components, no trailing `/`. pub fn init(version: Version, path: []const u8) Key { return .{ .h0 = murmur3(version, seed0, path), .h1 = murmur3(version, seed1, path) }; }};
/// Whether `filter` may hold the path `key` was made from: false only if/// the commit certainly did not change it. An empty filter, which was/// never computed, may hold anything.pub fn mayContain(filter: []const u8, hashes: u32, key: Key) bool { if (filter.len == 0) return true; const bits: u64 = @as(u64, filter.len) * 8; var i: u32 = 0; while (i < hashes) : (i += 1) { const h: u32 = key.h0 +% i *% key.h1; const at = h % bits; if (filter[@intCast(at / 8)] & (@as(u8, 1) << @intCast(at % 8)) == 0) return false; } return true;}
/// 32-bit murmur3 of `data` with `seed`, reading bytes as `version`/// says.pub fn murmur3(version: Version, seed: u32, data: []const u8) u32 { const c1: u32 = 0xcc9e2d51; const c2: u32 = 0x1b873593; var h = seed; const blocks = data.len / 4; for (0..blocks) |b| { const p = data[4 * b ..][0..4]; var k: u32 = byte(version, p[0]) | byte(version, p[1]) << 8 | byte(version, p[2]) << 16 | byte(version, p[3]) << 24; k *%= c1; k = std.math.rotl(u32, k, 15); k *%= c2; h ^= k; h = std.math.rotl(u32, h, 13); h = h *% 5 +% 0xe6546b64; } const tail = data[4 * blocks ..]; var k: u32 = 0; if (tail.len >= 3) k ^= byte(version, tail[2]) << 16; if (tail.len >= 2) k ^= byte(version, tail[1]) << 8; if (tail.len >= 1) { k ^= byte(version, tail[0]); k *%= c1; k = std.math.rotl(u32, k, 15); k *%= c2; h ^= k; } h ^= @truncate(data.len); h ^= h >> 16; h *%= 0x85ebca6b; h ^= h >> 13; h *%= 0xc2b2ae35; h ^= h >> 16; return h;}
fn byte(version: Version, b: u8) u32 { return switch (version) { .v2 => b, .v1 => @bitCast(@as(i32, @as(i8, @bitCast(b)))), };}
// -- tests -----------------------------------------------------------------------
const testing = std.testing;const fuzz_input = @import("testing/fuzz.zig");
test "murmur3 matches its published values" { try testing.expectEqual(0, murmur3(.v2, 0, "")); try testing.expectEqual(0x514e28b7, murmur3(.v2, 1, "")); try testing.expectEqual(0x3c2569b2, murmur3(.v2, 0, "a")); try testing.expectEqual(0x9bbfd75f, murmur3(.v2, 0, "ab")); try testing.expectEqual(0xb3dd93fa, murmur3(.v2, 0, "abc")); try testing.expectEqual(0x43ed676a, murmur3(.v2, 0, "abcd")); try testing.expectEqual(0x248bfa47, murmur3(.v2, 0, "hello")); try testing.expectEqual(0x24884cba, murmur3(.v2, 0x9747b28c, "Hello, world!")); // Without bytes of 0x80 and above, the versions agree. try testing.expectEqual(murmur3(.v2, 7, "src/main.zig"), murmur3(.v1, 7, "src/main.zig")); try testing.expect(murmur3(.v2, 7, "caf\xc3\xa9") != murmur3(.v1, 7, "caf\xc3\xa9"));}
test "the filter git wrote for one path holds it" { // The filter git wrote for a commit adding the file `a`: 7 hashes, 10 // bits per entry, two bytes. const filter = [_]u8{ 0x55, 0x45 }; try testing.expect(mayContain(&filter, 7, .init(.v1, "a"))); try testing.expect(!mayContain(&filter, 7, .init(.v1, "b"))); try testing.expect(mayContain(&.{}, 7, .init(.v1, "b"))); try testing.expect(!mayContain(&.{0}, 7, .init(.v1, "a"))); try testing.expect(mayContain(&.{0xff}, 7, .init(.v1, "a")));}
fn fuzzOne(_: void, smith: *testing.Smith) anyerror!void { var buffer: [512]u8 = undefined; const input = fuzz_input.bytes(smith, &buffer); const split = input.len / 2; for ([_]Version{ .v1, .v2 }) |v| { const key: Key = .init(v, input[0..split]); _ = mayContain(input[split..], 7, key); } // A filter of all ones holds everything. try testing.expect(mayContain(&.{ 0xff, 0xff }, 7, .init(.v2, input)));}
test "fuzz: Bloom filters" { try fuzz_input.fuzz({}, fuzzOne, .{ .corpus = &.{ @embedFile("fuzz/bloom-filter"), } });}