// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! EWAH bitmaps, as the index's split index, untracked cache and //! fsmonitor extensions hold them, read from their bytes without //! allocating. //! //! The serialization is the one gitformat-bitmap(5)'s appendix describes: //! a 32-bit count of the bits the uncompressed bitmap holds, a 32-bit //! count of 64-bit words, the words, and the 32-bit position of the last //! run length word, every number in network byte order. The words are //! chunks, each a run length word followed by literal words. A run length //! word holds, from its lowest bit, the repeated bit, then 32 bits saying //! how many *words* of that bit come first, then 31 bits saying how many //! literal words follow it; within a literal word the lowest bit comes //! first. //! //! What git checks of one, seen by writing malformed bitmaps into split //! indexes and fsmonitor extensions: only that each field is there, in //! git's words "eof before bit size", "eof before length", "eof in data //! (N bytes short)" and "eof before rlw". The bit count does not limit //! which bits are set — git acts on a set bit past it — and the position //! of the last run length word is not checked at all; so neither is //! checked here. A caller bounds the bits it takes, since a run can set //! 2^38 of them. const std = @import("std"); const Diagnostics = @import("../Diagnostics.zig"); /// Why a bitmap could not be read, each in git's words after "corrupt /// ewah bitmap: ": /// /// - `EofBeforeBitSize`: "eof before bit size"; /// - `EofBeforeLength`: "eof before length", the count of words; /// - `EofInData`: "eof in data (N bytes short)", which the diagnostic's /// detail says in full; /// - `EofBeforeRlw`: "eof before rlw". pub const Error = error{ EofBeforeBitSize, EofBeforeLength, EofInData, EofBeforeRlw }; /// One bitmap, as stored. pub const Bitmap = struct { /// How many bits the uncompressed bitmap is said to hold. bit_size: u32, /// The words, eight bytes each, big-endian. words: []const u8, /// Where the last run length word is, in words; not checked. rlw_position: u32, /// The empty bitmap. pub const empty: Bitmap = .{ .bit_size = 0, .words = &.{}, .rlw_position = 0 }; /// How many words there are. pub fn wordCount(b: Bitmap) usize { return b.words.len / 8; } /// The positions of the set bits, in increasing order. pub fn iterator(b: Bitmap) Iterator { return .{ .words = b.words }; } /// Whether any bit at or past `limit` is set: what a caller asks before /// trusting the bitmap to describe `limit` things. Bounded by the /// number of words, however long the runs. pub fn anySetFrom(b: Bitmap, limit: u64) bool { var it = b.iterator(); while (it.next()) |p| { if (p >= limit) return true; it.skipTo(limit); } return false; } }; /// Steps through the set bits of a bitmap. A run of ones yields each of /// its bits; a run of zeros is passed over at once. pub const Iterator = struct { words: []const u8, /// The next word to read. index: usize = 0, /// The position of the next bit to be read. position: u64 = 0, /// Ones still to yield in the current run, in bits. run_ones: u64 = 0, /// Literal words still to read in the current chunk. literals: u64 = 0, /// What is left of the literal word being read. word: u64 = 0, /// The position of the literal word being read's lowest bit. word_base: u64 = 0, fn readWord(it: *Iterator) ?u64 { if (it.index * 8 + 8 > it.words.len) return null; const w = std.mem.readInt(u64, it.words[it.index * 8 ..][0..8], .big); it.index += 1; return w; } /// The position of the next set bit, or null after the last. pub fn next(it: *Iterator) ?u64 { while (true) { if (it.run_ones != 0) { it.run_ones -= 1; it.position += 1; return it.position - 1; } if (it.word != 0) { const bit = @ctz(it.word); it.word &= it.word - 1; return it.word_base + bit; } if (it.literals != 0) { it.literals -= 1; it.word = it.readWord() orelse return null; it.word_base = it.position; it.position += 64; continue; } const rlw = it.readWord() orelse return null; const bit = rlw & 1; const run_words = (rlw >> 1) & 0xffff_ffff; it.literals = rlw >> 33; if (bit == 1) { it.run_ones = run_words * 64; } else { it.position += run_words * 64; } } } /// Passes over every set bit before `limit` that a run of ones still /// holds, so that a caller who has seen enough need not count them /// one by one. pub fn skipTo(it: *Iterator, limit: u64) void { if (it.run_ones == 0 or it.position >= limit) return; const skip = @min(it.run_ones, limit - it.position); it.run_ones -= skip; it.position += skip; } }; /// A bitmap and how many bytes it took. pub const Parsed = struct { bitmap: Bitmap, len: usize, }; /// Reads the bitmap at the start of `bytes`. pub fn parse(bytes: []const u8, diag: ?*Diagnostics) Error!Parsed { if (bytes.len < 4) return fail(diag, error.EofBeforeBitSize, "eof before bit size", .{}); const bit_size = std.mem.readInt(u32, bytes[0..4], .big); if (bytes.len < 8) return fail(diag, error.EofBeforeLength, "eof before length", .{}); const word_count = std.mem.readInt(u32, bytes[4..8], .big); const data_len = @as(u64, word_count) * 8; const available = bytes.len - 8; if (data_len > available) return fail(diag, error.EofInData, "eof in data ({d} bytes short)", .{data_len - available}); const end: usize = @intCast(8 + data_len); if (bytes.len - end < 4) return fail(diag, error.EofBeforeRlw, "eof before rlw", .{}); return .{ .bitmap = .{ .bit_size = bit_size, .words = bytes[8..end], .rlw_position = std.mem.readInt(u32, bytes[end..][0..4], .big), }, .len = end + 4, }; } fn fail(diag: ?*Diagnostics, err: Error, comptime fmt: []const u8, args: anytype) Error { if (diag) |d| d.setDetail(fmt, args); return err; } // -- tests ----------------------------------------------------------------------- const testing = std.testing; fn word(buffer: *std.ArrayList(u8), w: u64) !void { var b: [8]u8 = undefined; std.mem.writeInt(u64, &b, w, .big); try buffer.appendSlice(testing.allocator, &b); } fn serialize(bits: u32, words: []const u64) ![]u8 { var out: std.ArrayList(u8) = .empty; errdefer out.deinit(testing.allocator); var b: [4]u8 = undefined; std.mem.writeInt(u32, &b, bits, .big); try out.appendSlice(testing.allocator, &b); std.mem.writeInt(u32, &b, @intCast(words.len), .big); try out.appendSlice(testing.allocator, &b); for (words) |w| try word(&out, w); try out.appendSlice(testing.allocator, &.{ 0, 0, 0, 0 }); return out.toOwnedSlice(testing.allocator); } fn collect(b: Bitmap, limit: usize, out: []u64) []u64 { var it = b.iterator(); var n: usize = 0; while (it.next()) |p| { if (n == limit) break; out[n] = p; n += 1; } return out[0..n]; } const fuzz_input = @import("../testing/fuzz.zig"); test "a bitmap's set bits are read in order, runs and literals alike" { // A literal chunk, as git wrote the delete bitmap of a split index // that deleted its third entry. const one = try serialize(3, &.{ 0x0000_0002_0000_0000, 0x4 }); defer testing.allocator.free(one); const p = try parse(one, null); try testing.expectEqual(one.len, p.len); var buf: [256]u64 = undefined; try testing.expectEqualSlices(u64, &.{2}, collect(p.bitmap, 10, &buf)); // A run of one word of ones, then one of zeros with a literal after // it: the run counts words, not bits. const runs = try serialize(200, &.{ 0x3, 0x0000_0002_0000_0002, 0x1 }); defer testing.allocator.free(runs); const q = try parse(runs, null); const got = collect(q.bitmap, 256, &buf); try testing.expectEqual(65, got.len); try testing.expectEqual(0, got[0]); try testing.expectEqual(63, got[63]); try testing.expectEqual(128, got[64]); try testing.expect(q.bitmap.anySetFrom(100)); try testing.expect(!q.bitmap.anySetFrom(129)); } test "a bitmap cut short is refused in git's words" { var d: Diagnostics = .{}; try testing.expectError(error.EofBeforeBitSize, parse(&.{}, &d)); try testing.expectError(error.EofBeforeLength, parse(&.{ 0, 0, 0, 0 }, &d)); const short = [_]u8{ 0, 0, 0, 0, 0, 0, 0, 9 } ++ @as([12]u8, @splat(0)); try testing.expectError(error.EofInData, parse(&short, &d)); try testing.expectEqualStrings("eof in data (60 bytes short)", d.detail()); const no_rlw = [_]u8{ 0, 0, 0, 0, 0, 0, 0, 1 } ++ @as([9]u8, @splat(0)); try testing.expectError(error.EofBeforeRlw, parse(&no_rlw, &d)); } test "fuzz: ewah bitmaps" { try fuzz_input.fuzz({}, struct { fn one(_: void, smith: *testing.Smith) anyerror!void { var buffer: [1024]u8 = undefined; const input = @import("../testing/fuzz.zig").bytes(smith, &buffer); const p = parse(input, null) catch return; try testing.expect(p.len <= input.len); var it = p.bitmap.iterator(); var n: usize = 0; var last: ?u64 = null; while (it.next()) |pos| : (n += 1) { if (last) |l| try testing.expect(pos > l); last = pos; if (n == 4096) break; } _ = p.bitmap.anySetFrom(1000); } }.one, .{ .corpus = &.{ @embedFile("../fuzz/ewah-split-delete"), @embedFile("../fuzz/ewah-runs"), } }); }