testFuzzedHuffmanInput

fn testFuzzedHuffmanInput(fbufs: *const [2][65536]u8, smith: *std.testing.Smith) !void

File

Code

fn testFuzzedHuffmanInput(fbufs: *const [2][65536]u8, smith: *std.testing.Smith) !void {
    @disableInstrumentation();
    const container = smith.value(flate.Container);
    var flate_buf: [2 * 65536]u8 = undefined;
    var flate_w: Writer = .fixed(&flate_buf);
    var expected_hash: flate.Container.Hasher = .init(container);
    var expected_size: u32 = 0;
    const max_size = 4 * @as(u32, Huffman.max_tokens);

    var h_buf: [2 * @as(usize, Huffman.max_tokens)]u8 = undefined;
    const h_buf_len = smith.valueWeighted(u32, &.{
        .value(u32, 0, @intCast(h_buf.len)), // unbuffered
        .rangeAtMost(u32, 0, @intCast(h_buf.len), 1),
    });
    var h: Huffman = try .init(&flate_w, h_buf[0..h_buf_len], container);

    var vecs: [32][]const u8 = undefined;
    var vecs_n: usize = 0;

    while (true) {
        const Op = packed struct {
            drain: bool = false,
            add_vec: bool = false,
            rebase: enum(u2) { none, rebase, flush } = .none,

            pub const drain_only: @This() = .{ .drain = true };
            pub const add_vec_only: @This() = .{ .add_vec = true };
            pub const add_vec_and_drain: @This() = .{ .add_vec = true, .drain = true };
            pub const drain_and_rebase: @This() = .{ .drain = true, .rebase = .rebase };
            pub const drain_and_flush: @This() = .{ .drain = true, .rebase = .flush };
        };

        const is_eos = expected_size == max_size or smith.eosWeightedSimple(7, 1);
        var op: Op = if (!is_eos) smith.valueWeighted(Op, &.{
            .value(Op, .add_vec_only, 5),
            .value(Op, .add_vec_and_drain, 1),
            .value(Op, .drain_and_rebase, 1),
            .value(Op, .drain_and_flush, 1),
        }) else .drain_only;

        if (op.add_vec) {
            const max_write = max_size - expected_size;
            const buffered: u32 = @intCast(h.writer.buffered().len + countVec(vecs[0..vecs_n]));
            const to_align = Huffman.max_tokens - buffered % Huffman.max_tokens;
            assert(to_align != 0); // otherwise, not helpful.

            const data_buf = &fbufs[
                smith.valueWeighted(u1, &.{
                    .value(FreqBufIndex, .gradient, 3),
                    .value(FreqBufIndex, .random, 1),
                })
            ];
            const data_buf_len: u32 = @intCast(data_buf.len);

            const max_data = @min(data_buf_len, max_write);
            const len = smith.valueWeighted(u32, &.{
                .rangeAtMost(u32, 0, max_data, 1),
                .rangeAtMost(u32, 0, @min(Huffman.max_tokens, max_data), 4),
                .value(u32, @min(to_align, max_data), max_data), // @min 2nd arg is an edge-case
            });
            const off = smith.valueRangeAtMost(u32, 0, data_buf_len - len);

            expected_size += len;
            vecs[vecs_n] = data_buf[off..][0..len];
            vecs_n += 1;
            op.drain |= vecs_n == vecs.len;
        }

        op.drain |= is_eos;
        op.drain &= vecs_n != 0;
        if (op.drain) {
            const pattern_len: u32 = @intCast(vecs[vecs_n - 1].len);
            const pattern_len_z = @max(pattern_len, 1);

            const max_write = max_size - (expected_size - pattern_len);
            const buffered: u32 = @intCast(h.writer.buffered().len + countVec(vecs[0 .. vecs_n - 1]));
            const to_align = Huffman.max_tokens - buffered % Huffman.max_tokens;
            assert(to_align != 0); // otherwise, not helpful.

            const max_splat = max_write / pattern_len_z;
            const weights: [3]std.testing.Smith.Weight = .{
                .rangeAtMost(u32, 0, max_splat, 1),
                .rangeAtMost(u32, 0, @min(
                    Huffman.max_tokens + pattern_len_z,
                    max_write,
                ) / pattern_len_z, 4),
                .value(u32, to_align / pattern_len_z, max_splat * 4),
            };
            const align_weight = to_align % pattern_len_z == 0 and to_align <= max_write;
            const n_weights = @as(u8, 2) + @intFromBool(align_weight);
            const splat = smith.valueWeighted(u32, weights[0..n_weights]);

            expected_size = expected_size - pattern_len + pattern_len * splat; // splat may be zero
            for (vecs[0 .. vecs_n - 1]) |v| expected_hash.update(v);
            for (0..splat) |_| expected_hash.update(vecs[vecs_n - 1]);

            const max_space = fuzzedHuffmanDrainSpaceLimit(
                buffered + pattern_len * splat,
                flate_w.buffered().len,
                false,
            );
            h.writer.writeSplatAll(vecs[0..vecs_n], splat) catch
                return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {};
            if (flate_w.buffered().len > max_space) return error.OverheadTooLarge;

            vecs_n = 0;
        }

        if (op.rebase != .none) {
            const capacity = smith.valueRangeAtMost(u32, 0, h_buf_len);
            const preserve = smith.valueRangeAtMost(u32, 0, h_buf_len - capacity);

            const max_space = fuzzedHuffmanDrainSpaceLimit(
                h.writer.buffered().len,
                flate_w.buffered().len,
                false,
            ) + @as(usize, 8) * @intFromBool(op.rebase == .flush); // Overhead from byte alignment
            switch (op.rebase) {
                .none => unreachable,
                .rebase => h.writer.rebase(preserve, capacity) catch
                    return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {},
                .flush => h.writer.flush() catch
                    return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {},
            }
            if (flate_w.buffered().len > max_space) return error.OverheadTooLarge;
        }

        if (is_eos) break;
    }

    const max_space = fuzzedHuffmanDrainSpaceLimit(
        h.writer.buffered().len,
        flate_w.buffered().len,
        true,
    );
    h.finish() catch return if (max_space <= flate_w.buffer.len) error.OverheadTooLarge else {};
    if (flate_w.buffered().len > max_space) return error.OverheadTooLarge;

    try testingCheckDecompressedMatches(flate_w.buffered(), expected_size, expected_hash);
}