// 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"),
    } });
}