FuzzAllocator

const FuzzAllocator = struct {
    smith: *std.testing.Smith,
    bufs: [2][256 * 4]u8 align(4),
    used_bitmap: u2,
    used_len: [2]usize,

    pub fn init(smith: *std.testing.Smith) FuzzAllocator {
        return .{
            .smith = smith,
            .bufs = undefined,
            .used_len = undefined,
            .used_bitmap = 0,
        };
    }

    pub fn allocator(f: *FuzzAllocator) std.mem.Allocator {
        return .{
            .ptr = f,
            .vtable = &.{
                .alloc = alloc,
                .resize = resize,
                .remap = remap,
                .free = free,
            },
        };
    }

    pub fn allocCount(f: *FuzzAllocator) u2 {
        return @popCount(f.used_bitmap);
    }

    fn alloc(ctx: *anyopaque, len: usize, a: std.mem.Alignment, _: usize) ?[*]u8 {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        assert(len % 4 == 0);

        const slot: u1 = @intCast(@ctz(~f.used_bitmap));
        const buf: []u8 = &f.bufs[slot];
        if (len > buf.len) return null;
        f.used_bitmap |= @as(u2, 1) << slot;
        f.used_len[slot] = len;
        return buf.ptr;
    }

    fn memSlot(f: *FuzzAllocator, mem: []u8) u1 {
        const slot: u1 = if (&mem[0] == &f.bufs[0][0])
            0
        else if (&mem[0] == &f.bufs[1][0])
            1
        else
            unreachable;
        assert((f.used_bitmap >> slot) & 1 == 1);
        assert(mem.len == f.used_len[slot]);
        return slot;
    }

    fn resize(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) bool {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        assert(f.allocCount() == 1);

        const slot = f.memSlot(mem);
        if (new_len > f.bufs[slot].len or f.smith.value(bool)) return false;
        f.used_len[slot] = new_len;
        return true;
    }

    fn remap(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) ?[*]u8 {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        assert(f.allocCount() == 1);

        const slot = f.memSlot(mem);
        if (new_len > f.bufs[slot].len or f.smith.value(bool)) return null;

        if (f.smith.value(bool)) {
            f.used_len[slot] = new_len;
            // remap in place
            return mem.ptr;
        } else {
            // moving remap
            const new_slot = ~slot;
            f.used_bitmap = ~f.used_bitmap;
            f.used_len[new_slot] = new_len;

            const new_buf = &f.bufs[new_slot];
            @memcpy(new_buf[0..mem.len], mem);
            return new_buf.ptr;
        }
    }

    fn free(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, _: usize) void {
        const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
        assert(a == .@"4");
        f.used_bitmap ^= @as(u2, 1) << f.memSlot(mem);
    }
}