Skip to content

std.compress.flate.Decompress

Standard libraryZig 0.17.1Official documentation
Sourcestd/compress/flate/Decompress.zig

Source line 1

Fields

input: *Reader
consumed_bits: u3
reader: Reader
container_metadata: Container.Metadata
lit_dec: LiteralDecoder
dst_dec: DistanceDecoder
final_block: bool
state: State
err: ?Error

std.compress.flate.Decompress.alignBitsForward

function

Source line 577

fn alignBitsForward(d: *Decompress) void

Parameters

std.compress.flate.Decompress.assert

alias

Source line 2

Alias of std.debug.assert

std.compress.flate.Decompress.BlockType

container

Source line 27

Fields

stored = 0
fixed = 1
dynamic = 2
invalid = 3

std.compress.flate.Decompress.CodegenDecoder

type

Source line 642

std.compress.flate.Decompress.Container

alias

Source line 7

Alias of std.compress.flate.Container

std.compress.flate.Decompress.decodeDistance

function

Source line 197

fn decodeDistance(self: *Decompress, code_int: u5) !u16

Parameters

self: *Decompress
code_int: u5

std.compress.flate.Decompress.decodeLength

function

Source line 189

fn decodeLength(self: *Decompress, code_int: u5) !u16

Parameters

self: *Decompress
code_int: u5

std.compress.flate.Decompress.decodeSymbol

function

Source line 237

fn decodeSymbol(self: *Decompress, decoder: anytype) !u16

Parameters

self: *Decompress

std.compress.flate.Decompress.Decompress

alias

Source line 9

Alias of std.compress.flate.Decompress

std.compress.flate.Decompress.direct_vtable

constant

Source line 67

Reader.VTable

std.compress.flate.Decompress.discardDirect

function

Source line 121

This could be improved so that when an amount is discarded that includes an entire frame, skip decoding that frame.

fn discardDirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize

Parameters

r: *Reader
limit: std.Io.Limit

Errors

EndOfStream
ReadFailed

See the Reader implementation for detailed diagnostics.

std.compress.flate.Decompress.discardIndirect

function

Source line 144

fn discardIndirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize

Parameters

r: *Reader
limit: std.Io.Limit

Errors

EndOfStream
ReadFailed

See the Reader implementation for detailed diagnostics.

std.compress.flate.Decompress.DistanceDecoder

type

Source line 641

std.compress.flate.Decompress.dynamicCodeLength

function

Source line 208

Decode code length symbol to code length. Writes decoded length into lens slice starting at position pos. Returns number of positions advanced.

fn dynamicCodeLength(self: *Decompress, code: u16, lens: []u4, pos: usize) !usize

Parameters

self: *Decompress
code: u16
lens: []u4
pos: usize

std.compress.flate.Decompress.Error

error-set

Source line 54

Errors

BadGzipHeader Error
BadZlibHeader Error
EndOfStream
IncompleteHuffmanTree
InvalidBlockType
InvalidCode
InvalidDynamicBlockHeader
InvalidMatch
MissingEndOfBlockCode
OversubscribedHuffmanTree
ReadFailed
WrongGzipChecksum Error
WrongGzipSize Error
WrongStoredBlockNlen
WrongZlibChecksum Error

std.compress.flate.Decompress.flate

alias

Source line 3

Alias of std.compress.flate

std.compress.flate.Decompress.HuffmanDecoder

type-function

Source line 656

Creates huffman tree codes from list of code lengths (in build).

find then finds symbol for code bits. Code can be any length between 1 and 15 bits. When calling find we don't know how many bits will be used to find symbol. When symbol is returned it has code_bits field which defines how much we should advance in bit stream.

Lookup table is used to map 15 bit int to symbol. Same symbol is written many times in this table; 32K places for 286 (at most) symbols. Small lookup table is optimization for faster search. It is variation of the algorithm explained in zlib with difference that we here use statically allocated arrays.

fn HuffmanDecoder( comptime alphabet_size: u16, comptime max_code_bits: u4, comptime lookup_bits: u4, ) type

Parameters

alphabet_size: u16
max_code_bits: u4
lookup_bits: u4

Fields

lookup: [1 << lookup_bits]Symbol = undefined
linked: if (lookup_bits == max_code_bits) void else [alphabet_size]struct {
    // sym.value is the next index in linked where the current index ends the chain
    // the actual symbol is this nodes's index
    sym: Symbol,
    code: u16,
} = undefined

std.compress.flate.Decompress.HuffmanDecoder.checkCompleteness

function

Source line 742

Given the list of code lengths check that it represents a canonical Huffman code for n symbols.

Reference: https://github.com/madler/zlib/blob/5c42a230b7b468dff011f444161c0145b5efae59/contrib/puff/puff.c#L340

fn checkCompleteness(lens: []const u4) !void

Parameters

lens: []const u4

std.compress.flate.Decompress.HuffmanDecoder.find

function

Source line 772

Finds symbol for lookup table code.

pub fn find(self: *Self, code: u16) !Symbol

Parameters

self: *Self
code: u16

std.compress.flate.Decompress.HuffmanDecoder.findLinked

function

Source line 781

fn findLinked(self: *Self, code: u16, start: u16) !Symbol

Parameters

self: *Self
code: u16
start: u16

std.compress.flate.Decompress.HuffmanDecoder.generate

function

Source line 683

Generates symbols and lookup tables from list of code lens for each symbol.

pub fn generate(self: *Self, lens: []const u4) !void

Parameters

self: *Self
lens: []const u4

std.compress.flate.Decompress.HuffmanDecoder.reverseIdx

function

Source line 678

fn reverseIdx(idx: usize) u16

Parameters

idx: usize

std.compress.flate.Decompress.HuffmanDecoder.Self

alias

Source line 676

Alias of std.compress.flate.Decompress.HuffmanDecoder

std.compress.flate.Decompress.indirect_vtable

constant

Source line 74

Reader.VTable

std.compress.flate.Decompress.init

function

Source line 85

input buffer is asserted to be at least 10 bytes, or EOF before then.

If buffer is provided then asserted to have flate.max_window_len capacity.

pub fn init(input: *Reader, container: Container, buffer: []u8) Decompress

Parameters

input: *Reader
container: Container
buffer: []u8

std.compress.flate.Decompress.LiteralDecoder

type

Source line 640

std.compress.flate.Decompress.peekBits

function

Source line 546

fn peekBits(d: *Decompress, n: u4) !u16

Parameters

d: *Decompress
n: u4

std.compress.flate.Decompress.peekBitsEnding

function

Source line 555

fn peekBitsEnding(d: *Decompress, n: u4) !u16

Parameters

d: *Decompress
n: u4

std.compress.flate.Decompress.peekBitsShort

function

Source line 582

fn peekBitsShort(d: *Decompress, n: u4) !u16

Parameters

d: *Decompress
n: u4

std.compress.flate.Decompress.peekBitsShortEnding

function

Source line 591

fn peekBitsShortEnding(d: *Decompress, n: u4) !u16

Parameters

d: *Decompress
n: u4

std.compress.flate.Decompress.peekIntBitsShort

function

Source line 609

fn peekIntBitsShort(d: *Decompress, T: type) !T

Parameters

d: *Decompress
T: type

std.compress.flate.Decompress.Reader

alias

Source line 6

Alias of std.Io.Reader

std.compress.flate.Decompress.readFixedCode

function

Source line 625

Reads first 7 bits, and then maybe 1 or 2 more to get full 7,8 or 9 bit code. ref: https://datatracker.ietf.org/doc/html/rfc1951#page-12 Lit Value Bits Codes


0 - 143 8 00110000 through 10111111 144 - 255 9 110010000 through 111111111 256 - 279 7 0000000 through 0010111 280 - 287 8 11000000 through 11000111

fn readFixedCode(d: *Decompress) !u16

Parameters

std.compress.flate.Decompress.readVec

function

Source line 164

fn readVec(r: *Reader, data: [][]u8) Reader.Error!usize

Parameters

r: *Reader
data: [][]u8

Errors

EndOfStream
ReadFailed

See the Reader implementation for detailed diagnostics.

std.compress.flate.Decompress.rebase

function

Source line 109

fn rebase(r: *Reader, capacity: usize) void

Parameters

r: *Reader
capacity: usize

std.compress.flate.Decompress.rebaseFallible

function

Source line 105

fn rebaseFallible(r: *Reader, capacity: usize) Reader.RebaseError!void

Parameters

r: *Reader
capacity: usize

Errors

EndOfStream Error
ReadFailed Error

See the Reader implementation for detailed diagnostics.

std.compress.flate.Decompress.State

container

Source line 34

Fields

protocol_header
block_header
stored_block: u16
fixed_block
fixed_block_literal: u8
fixed_block_match: struct {
    distance: u16,
    length: u16,
}
dynamic_block
dynamic_block_literal: u8
dynamic_block_match: struct {
    distance: u16,
    length: u16,
}
protocol_footer
end

std.compress.flate.Decompress.std

alias

Source line 1

Alias of std

std.compress.flate.Decompress.streamDirect

function

Source line 244

fn streamDirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize

Parameters

r: *Reader
w: *Writer
limit: std.Io.Limit

Errors

EndOfStream

End of stream indicated from the Reader. This error cannot originate from the Writer.

ReadFailed

See the Reader implementation for detailed diagnostics.

WriteFailed

See the Writer implementation for detailed diagnostics.

std.compress.flate.Decompress.streamFallible

function

Source line 256

fn streamFallible(d: *Decompress, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize

Parameters

d: *Decompress
w: *Writer
limit: std.Io.Limit

Errors

EndOfStream

End of stream indicated from the Reader. This error cannot originate from the Writer.

ReadFailed

See the Reader implementation for detailed diagnostics.

WriteFailed

See the Writer implementation for detailed diagnostics.

std.compress.flate.Decompress.streamIndirect

function

Source line 249

fn streamIndirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize

Parameters

r: *Reader
w: *Writer
limit: std.Io.Limit

Errors

EndOfStream

End of stream indicated from the Reader. This error cannot originate from the Writer.

ReadFailed

See the Reader implementation for detailed diagnostics.

WriteFailed

See the Writer implementation for detailed diagnostics.

std.compress.flate.Decompress.streamIndirectInner

function

Source line 170

fn streamIndirectInner(d: *Decompress) Reader.Error!usize

Parameters

Errors

EndOfStream
ReadFailed

See the Reader implementation for detailed diagnostics.

std.compress.flate.Decompress.streamInner

function

Source line 276

fn streamInner(d: *Decompress, w: *Writer, limit: std.Io.Limit) (Error || Reader.StreamError)!usize

Parameters

d: *Decompress
w: *Writer
limit: std.Io.Limit

std.compress.flate.Decompress.Symbol

container

Source line 635

Fields

value: u12 = 0
code_bits: u4 = 0

std.compress.flate.Decompress.takeBits

function

Source line 571

fn takeBits(d: *Decompress, n: u4) !u16

Parameters

d: *Decompress
n: u4

std.compress.flate.Decompress.takeIntBits

function

Source line 605

fn takeIntBits(d: *Decompress, T: type) !T

Parameters

d: *Decompress
T: type

std.compress.flate.Decompress.testDecompress

function

Source line 1193

fn testDecompress(container: Container, compressed: []const u8, expected_plain: []const u8) !void

Parameters

container: Container
compressed: []const u8
expected_plain: []const u8

std.compress.flate.Decompress.testFailure

function

Source line 1183

fn testFailure(container: Container, in: []const u8, expected_err: anyerror) !void

Parameters

container: Container
in: []const u8
expected_err: anyerror

std.compress.flate.Decompress.testing

alias

Source line 4

Alias of std.testing

std.compress.flate.Decompress.token

alias

Source line 10

Alias of std.compress.flate.token

std.compress.flate.Decompress.tossBits

function

Source line 566

Safe only after peekBits has been called with a greater or equal n value.

fn tossBits(d: *Decompress, n: u4) void

Parameters

d: *Decompress
n: u4

std.compress.flate.Decompress.tossBitsShort

function

Source line 600

fn tossBitsShort(d: *Decompress, n: u4) !void

Parameters

d: *Decompress
n: u4

std.compress.flate.Decompress.writeMatch

function

Source line 523

Write match (back-reference to the same data slice) starting at distance back from current write position, and length of bytes. length may be less than the minimum match length to allow for writing partial matches, but must be greater than zero.

fn writeMatch(w: *Writer, length: u16, distance: u16) !void

Parameters

w: *Writer
length: u16
distance: u16

std.compress.flate.Decompress.Writer

alias

Source line 5

Alias of std.Io.Writer

Source code

std/compress/flate/Decompress.zig

const std = @import("../../std.zig");
const assert = std.debug.assert;
const flate = std.compress.flate;
const testing = std.testing;
const Writer = std.Io.Writer;
const Reader = std.Io.Reader;
const Container = flate.Container;

const Decompress = @This();
const token = @import("token.zig");

input: *Reader,
consumed_bits: u3,

reader: Reader,

container_metadata: Container.Metadata,

lit_dec: LiteralDecoder,
dst_dec: DistanceDecoder,

final_block: bool,
state: State,

err: ?Error,

const BlockType = enum(u2) {
    stored = 0,
    fixed = 1,
    dynamic = 2,
    invalid = 3,
};

const State = union(enum) {
    protocol_header,
    block_header,
    stored_block: u16,
    fixed_block,
    fixed_block_literal: u8,
    fixed_block_match: struct {
        distance: u16,
        length: u16,
    },
    dynamic_block,
    dynamic_block_literal: u8,
    dynamic_block_match: struct {
        distance: u16,
        length: u16,
    },
    protocol_footer,
    end,
};

pub const Error = Container.Error || error{
    InvalidCode,
    InvalidMatch,
    WrongStoredBlockNlen,
    InvalidBlockType,
    InvalidDynamicBlockHeader,
    ReadFailed,
    OversubscribedHuffmanTree,
    IncompleteHuffmanTree,
    MissingEndOfBlockCode,
    EndOfStream,
};

const direct_vtable: Reader.VTable = .{
    .stream = streamDirect,
    .rebase = rebaseFallible,
    .discard = discardDirect,
    .readVec = readVec,
};

const indirect_vtable: Reader.VTable = .{
    .stream = streamIndirect,
    .rebase = rebaseFallible,
    .discard = discardIndirect,
    .readVec = readVec,
};

/// `input` buffer is asserted to be at least 10 bytes, or EOF before then.
///
/// If `buffer` is provided then asserted to have `flate.max_window_len`
/// capacity.
pub fn init(input: *Reader, container: Container, buffer: []u8) Decompress {
    if (buffer.len != 0) assert(buffer.len >= flate.max_window_len);
    return .{
        .reader = .{
            .vtable = if (buffer.len == 0) &direct_vtable else &indirect_vtable,
            .buffer = buffer,
            .seek = 0,
            .end = 0,
        },
        .input = input,
        .consumed_bits = 0,
        .container_metadata = .init(container),
        .lit_dec = .{},
        .dst_dec = .{},
        .final_block = false,
        .state = .protocol_header,
        .err = null,
    };
}

fn rebaseFallible(r: *Reader, capacity: usize) Reader.RebaseError!void {
    rebase(r, capacity);
}

fn rebase(r: *Reader, capacity: usize) void {
    assert(capacity <= r.buffer.len - flate.history_len);
    assert(r.end + capacity > r.buffer.len);
    const discard_n = @min(r.seek, r.end - flate.history_len);
    const keep = r.buffer[discard_n..r.end];
    @memmove(r.buffer[0..keep.len], keep);
    r.end = keep.len;
    r.seek -= discard_n;
}

/// This could be improved so that when an amount is discarded that includes an
/// entire frame, skip decoding that frame.
fn discardDirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize {
    if (r.end + flate.history_len > r.buffer.len) rebase(r, flate.history_len);
    var writer: Writer = .{
        .vtable = &.{
            .drain = std.Io.Writer.Discarding.drain,
            .sendFile = std.Io.Writer.Discarding.sendFile,
        },
        .buffer = r.buffer,
        .end = r.end,
    };
    defer {
        assert(writer.end != 0);
        r.end = writer.end;
        r.seek = r.end;
    }
    const n = r.stream(&writer, limit) catch |err| switch (err) {
        error.WriteFailed => unreachable,
        error.ReadFailed, error.EndOfStream => |e| return e,
    };
    assert(n <= @backingInt(limit));
    return n;
}

fn discardIndirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize {
    const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
    if (r.end + flate.history_len > r.buffer.len) rebase(r, flate.history_len);
    var writer: Writer = .{
        .buffer = r.buffer,
        .end = r.end,
        .vtable = &.{ .drain = Writer.unreachableDrain },
    };
    {
        defer r.end = writer.end;
        _ = streamFallible(d, &writer, .limited(writer.buffer.len - writer.end)) catch |err| switch (err) {
            error.WriteFailed => unreachable,
            else => |e| return e,
        };
    }
    const n = limit.minInt(r.end - r.seek);
    r.seek += n;
    return n;
}

fn readVec(r: *Reader, data: [][]u8) Reader.Error!usize {
    _ = data;
    const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
    return streamIndirectInner(d);
}

fn streamIndirectInner(d: *Decompress) Reader.Error!usize {
    const r = &d.reader;
    if (r.buffer.len - r.end < flate.history_len) rebase(r, flate.history_len);
    var writer: Writer = .{
        .buffer = r.buffer,
        .end = r.end,
        .vtable = &.{
            .drain = Writer.unreachableDrain,
            .rebase = Writer.unreachableRebase,
        },
    };
    defer r.end = writer.end;
    _ = streamFallible(d, &writer, .limited(writer.buffer.len - writer.end)) catch |err| switch (err) {
        error.WriteFailed => unreachable,
        else => |e| return e,
    };
    return 0;
}

fn decodeLength(self: *Decompress, code_int: u5) !u16 {
    if (code_int > 28) return error.InvalidCode;
    const l: token.LenCode = .fromInt(code_int);
    const base = l.base();
    const extra = l.extraBits();
    return token.min_length + (base | try self.takeBits(extra));
}

fn decodeDistance(self: *Decompress, code_int: u5) !u16 {
    if (code_int > 29) return error.InvalidCode;
    const d: token.DistCode = .fromInt(code_int);
    const base = d.base();
    const extra = d.extraBits();
    return token.min_distance + (base | try self.takeBits(extra));
}

/// Decode code length symbol to code length. Writes decoded length into
/// lens slice starting at position pos. Returns number of positions
/// advanced.
fn dynamicCodeLength(self: *Decompress, code: u16, lens: []u4, pos: usize) !usize {
    if (pos >= lens.len)
        return error.InvalidDynamicBlockHeader;

    switch (code) {
        0...15 => {
            // Represent code lengths of 0 - 15
            lens[pos] = @intCast(code);
            return 1;
        },
        16 => {
            // Copy the previous code length 3 - 6 times.
            // The next 2 bits indicate repeat length
            const n: u8 = @as(u8, try self.takeIntBits(u2)) + 3;
            if (pos == 0 or pos + n > lens.len)
                return error.InvalidDynamicBlockHeader;
            for (0..n) |i| {
                lens[pos + i] = lens[pos + i - 1];
            }
            return n;
        },
        // Repeat a code length of 0 for 3 - 10 times. (3 bits of length)
        17 => return @as(u8, try self.takeIntBits(u3)) + 3,
        // Repeat a code length of 0 for 11 - 138 times (7 bits of length)
        18 => return @as(u8, try self.takeIntBits(u7)) + 11,
        else => return error.InvalidDynamicBlockHeader,
    }
}

fn decodeSymbol(self: *Decompress, decoder: anytype) !u16 {
    // Maximum code len is 15 bits.
    const sym = try decoder.find(try self.peekIntBitsShort(u15));
    try self.tossBitsShort(sym.code_bits);
    return sym.value;
}

fn streamDirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize {
    const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
    return streamFallible(d, w, limit);
}

fn streamIndirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize {
    const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
    _ = limit;
    _ = w;
    return streamIndirectInner(d);
}

fn streamFallible(d: *Decompress, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize {
    return streamInner(d, w, limit) catch |err| switch (err) {
        error.EndOfStream => {
            if (d.state == .end) {
                return error.EndOfStream;
            } else {
                d.err = error.EndOfStream;
                return error.ReadFailed;
            }
        },
        error.WriteFailed => |e| return e,
        else => |e| {
            // In the event of an error, state is unmodified so that it can be
            // better used to diagnose the failure.
            d.err = e;
            return error.ReadFailed;
        },
    };
}

fn streamInner(d: *Decompress, w: *Writer, limit: std.Io.Limit) (Error || Reader.StreamError)!usize {
    var remaining = @backingInt(limit);
    const in = d.input;
    sw: switch (d.state) {
        .protocol_header => switch (d.container_metadata.container()) {
            .gzip => {
                const Header = extern struct {
                    magic: u16 align(1),
                    method: u8,
                    flags: packed struct(u8) {
                        text: bool,
                        hcrc: bool,
                        extra: bool,
                        name: bool,
                        comment: bool,
                        reserved: u3,
                    },
                    mtime: u32 align(1),
                    xfl: u8,
                    os: u8,
                };
                const header = try in.takeStruct(Header, .little);
                if (header.magic != 0x8b1f or header.method != 0x08)
                    return error.BadGzipHeader;
                if (header.flags.extra) {
                    const extra_len = try in.takeInt(u16, .little);
                    try in.discardAll(extra_len);
                }
                if (header.flags.name) {
                    _ = try in.discardDelimiterInclusive(0);
                }
                if (header.flags.comment) {
                    _ = try in.discardDelimiterInclusive(0);
                }
                if (header.flags.hcrc) {
                    try in.discardAll(2);
                }
                continue :sw .block_header;
            },
            .zlib => {
                const header = try in.takeArray(2);
                const cmf: packed struct(u8) { cm: u4, cinfo: u4 } = @bitCast(header[0]);
                if (cmf.cm != 8 or cmf.cinfo > 7) return error.BadZlibHeader;
                continue :sw .block_header;
            },
            .raw => continue :sw .block_header,
        },
        .block_header => {
            d.final_block = (try d.takeIntBits(u1)) != 0;
            const block_type: BlockType = @fromBackingInt(@intCast(try d.takeIntBits(u2)));
            switch (block_type) {
                .stored => {
                    d.alignBitsForward();
                    // everything after this is byte aligned in stored block
                    const len = try in.takeInt(u16, .little);
                    const nlen = try in.takeInt(u16, .little);
                    if (len != ~nlen) return error.WrongStoredBlockNlen;
                    continue :sw .{ .stored_block = len };
                },
                .fixed => continue :sw .fixed_block,
                .dynamic => {
                    const hlit: u16 = @as(u16, try d.takeIntBits(u5)) + 257; // number of ll code entries present - 257
                    const hdist: u16 = @as(u16, try d.takeIntBits(u5)) + 1; // number of distance code entries - 1
                    const hclen: u8 = @as(u8, try d.takeIntBits(u4)) + 4; // hclen + 4 code lengths are encoded

                    if (hlit > 286 or hdist > 30)
                        return error.InvalidDynamicBlockHeader;

                    // lengths for code lengths
                    var cl_lens: [19]u4 = @splat(0);
                    for (token.codegen_order[0..hclen]) |i| {
                        cl_lens[i] = try d.takeIntBits(u3);
                    }
                    var cl_dec: CodegenDecoder = .{};
                    try cl_dec.generate(&cl_lens);

                    // decoded code lengths
                    var dec_lens: [286 + 30]u4 = @splat(0);
                    var pos: usize = 0;
                    while (pos < hlit + hdist) {
                        const peeked = try d.peekIntBitsShort(u7);
                        const sym = try cl_dec.find(peeked);
                        try d.tossBitsShort(sym.code_bits);
                        pos += try d.dynamicCodeLength(sym.value, &dec_lens, pos);
                    }
                    if (pos > hlit + hdist) {
                        return error.InvalidDynamicBlockHeader;
                    }

                    // literal code lengths to literal decoder
                    try d.lit_dec.generate(dec_lens[0..hlit]);

                    // distance code lengths to distance decoder
                    try d.dst_dec.generate(dec_lens[hlit..][0..hdist]);

                    continue :sw .dynamic_block;
                },
                .invalid => return error.InvalidBlockType,
            }
        },
        .stored_block => |remaining_len| {
            const out: []u8 = if (remaining != 0)
                try w.writableSliceGreedyPreserve(flate.history_len, 1)
            else
                &.{};
            var limited_out: [1][]u8 = .{limit.min(.limited(remaining_len)).slice(out)};
            const n = try in.readVec(&limited_out);
            if (remaining_len - n == 0) {
                d.state = if (d.final_block) .protocol_footer else .block_header;
            } else {
                d.state = .{ .stored_block = @intCast(remaining_len - n) };
            }
            w.advance(n);
            return @backingInt(limit) - remaining + n;
        },
        .fixed_block => while (true) {
            // Consume bytes
            const sym = try d.readFixedCode();

            if (sym >= 256) {
                @branchHint(.unlikely);

                if (sym == 256) {
                    @branchHint(.unlikely);
                    // End
                    d.state = if (d.final_block) .protocol_footer else .block_header;
                    continue :sw d.state;
                }

                // Match
                const length = try d.decodeLength(@intCast(sym - 257));
                const distance = try d.decodeDistance(@bitReverse(try d.takeIntBits(u5)));
                continue :sw .{ .fixed_block_match = .{ .length = length, .distance = distance } };
            }

            const byte: u8 = @intCast(sym);
            if (remaining != 0) {
                @branchHint(.likely);
                remaining -= 1;
                try w.writeBytePreserve(flate.history_len, byte);
            } else {
                d.state = .{ .fixed_block_literal = byte };
                return @backingInt(limit) - remaining;
            }
        },
        .fixed_block_literal => |symbol| {
            assert(remaining != 0);
            remaining -= 1;
            try w.writeBytePreserve(flate.history_len, symbol);
            continue :sw .fixed_block;
        },
        .fixed_block_match => |match| {
            if (remaining >= match.length) {
                @branchHint(.likely);
                try writeMatch(w, match.length, match.distance);
                remaining -= match.length;
                continue :sw .fixed_block;
            } else {
                if (remaining > 0) {
                    try writeMatch(w, @intCast(remaining), match.distance);
                }
                d.state = .{ .fixed_block_match = .{
                    .distance = match.distance,
                    .length = match.length - @as(u16, @intCast(remaining)),
                } };
                return @backingInt(limit);
            }
        },
        // In larger archives most blocks are usually dynamic, so
        // decompression performance depends on this logic.
        .dynamic_block => while (true) {
            // Consume bytes
            const sym = try d.decodeSymbol(&d.lit_dec);

            if (sym >= 256) {
                @branchHint(.unlikely);

                if (sym == 256) {
                    @branchHint(.unlikely);
                    // End
                    d.state = if (d.final_block) .protocol_footer else .block_header;
                    continue :sw d.state;
                }

                // Match
                const length = try d.decodeLength(@intCast(sym - 257));
                const dsm = try d.decodeSymbol(&d.dst_dec);
                const distance = try d.decodeDistance(@intCast(dsm));
                continue :sw .{ .dynamic_block_match = .{ .length = length, .distance = distance } };
            }

            const byte: u8 = @intCast(sym);
            if (remaining != 0) {
                @branchHint(.likely);
                remaining -= 1;
                try w.writeBytePreserve(flate.history_len, byte);
            } else {
                d.state = .{ .dynamic_block_literal = byte };
                return @backingInt(limit) - remaining;
            }
        },
        .dynamic_block_literal => |symbol| {
            assert(remaining != 0);
            remaining -= 1;
            try w.writeBytePreserve(flate.history_len, symbol);
            continue :sw .dynamic_block;
        },
        .dynamic_block_match => |match| {
            if (remaining >= match.length) {
                @branchHint(.likely);
                remaining -= match.length;
                try writeMatch(w, match.length, match.distance);
                continue :sw .dynamic_block;
            } else {
                if (remaining > 0) {
                    try writeMatch(w, @intCast(remaining), match.distance);
                }
                d.state = .{ .dynamic_block_match = .{
                    .distance = match.distance,
                    .length = match.length - @as(u16, @intCast(remaining)),
                } };
                return @backingInt(limit);
            }
        },
        .protocol_footer => {
            d.alignBitsForward();
            switch (d.container_metadata) {
                .gzip => |*gzip| {
                    gzip.crc = try in.takeInt(u32, .little);
                    gzip.count = try in.takeInt(u32, .little);
                },
                .zlib => |*zlib| {
                    zlib.adler = try in.takeInt(u32, .big);
                },
                .raw => {},
            }
            d.state = .end;
            return @backingInt(limit) - remaining;
        },
        .end => return error.EndOfStream,
    }
}

/// Write match (back-reference to the same data slice) starting at `distance`
/// back from current write position, and `length` of bytes.
/// `length` may be less than the minimum match length to allow for writing
/// partial matches, but must be greater than zero.
fn writeMatch(w: *Writer, length: u16, distance: u16) !void {
    if (w.end < distance) return error.InvalidMatch;
    assert(length > 0);
    assert(length <= token.max_length);
    assert(distance >= token.min_distance);
    assert(distance <= token.max_distance);

    // This is not a @memmove; it intentionally repeats patterns caused by
    // iterating one byte at a time.
    const dest = try w.writableSlicePreserve(flate.history_len, length);
    const end = dest.ptr - w.buffer.ptr;
    const src = w.buffer[end - distance ..][0..length];
    if (distance >= length) {
        @memcpy(dest, src);
    } else if (distance == 1) {
        // Repeating copy of single byte
        @memset(dest, src[0]);
    } else {
        // Repeating copy of multiple bytes
        for (dest, src) |*d, s| d.* = s;
    }
}

fn peekBits(d: *Decompress, n: u4) !u16 {
    const bits = d.input.peekInt(u32, .little) catch |e| return switch (e) {
        error.ReadFailed => error.ReadFailed,
        error.EndOfStream => d.peekBitsEnding(n),
    };
    const mask = @shlExact(@as(u16, 1), n) - 1;
    return @intCast((bits >> d.consumed_bits) & mask);
}

fn peekBitsEnding(d: *Decompress, n: u4) !u16 {
    @branchHint(.unlikely);

    const left = d.input.buffered();
    if (left.len * 8 - d.consumed_bits < n) return error.EndOfStream;
    const bits = std.mem.readVarInt(u32, left, .little);
    const mask = @shlExact(@as(u16, 1), n) - 1;
    return @intCast((bits >> d.consumed_bits) & mask);
}

/// Safe only after `peekBits` has been called with a greater or equal `n` value.
fn tossBits(d: *Decompress, n: u4) void {
    d.input.toss((@as(u8, n) + d.consumed_bits) / 8);
    d.consumed_bits +%= @truncate(n);
}

fn takeBits(d: *Decompress, n: u4) !u16 {
    const bits = try d.peekBits(n);
    d.tossBits(n);
    return bits;
}

fn alignBitsForward(d: *Decompress) void {
    d.input.toss(@intFromBool(d.consumed_bits != 0));
    d.consumed_bits = 0;
}

fn peekBitsShort(d: *Decompress, n: u4) !u16 {
    const bits = d.input.peekInt(u32, .little) catch |e| return switch (e) {
        error.ReadFailed => error.ReadFailed,
        error.EndOfStream => d.peekBitsShortEnding(n),
    };
    const mask = @shlExact(@as(u16, 1), n) - 1;
    return @intCast((bits >> d.consumed_bits) & mask);
}

fn peekBitsShortEnding(d: *Decompress, n: u4) !u16 {
    @branchHint(.unlikely);

    const left = d.input.buffered();
    const bits = std.mem.readVarInt(u32, left, .little);
    const mask = @shlExact(@as(u16, 1), n) - 1;
    return @intCast((bits >> d.consumed_bits) & mask);
}

fn tossBitsShort(d: *Decompress, n: u4) !void {
    if (d.input.bufferedLen() * 8 - d.consumed_bits < n) return error.EndOfStream;
    d.tossBits(n);
}

fn takeIntBits(d: *Decompress, T: type) !T {
    return @intCast(try d.takeBits(@bitSizeOf(T)));
}

fn peekIntBitsShort(d: *Decompress, T: type) !T {
    return @intCast(try d.peekBitsShort(@bitSizeOf(T)));
}

/// Reads first 7 bits, and then maybe 1 or 2 more to get full 7,8 or 9 bit code.
/// ref: https://datatracker.ietf.org/doc/html/rfc1951#page-12
///         Lit Value    Bits        Codes
///          ---------    ----        -----
///            0 - 143     8          00110000 through
///                                   10111111
///          144 - 255     9          110010000 through
///                                   111111111
///          256 - 279     7          0000000 through
///                                   0010111
///          280 - 287     8          11000000 through
///                                   11000111
fn readFixedCode(d: *Decompress) !u16 {
    const code7 = @bitReverse(try d.takeIntBits(u7));
    return switch (code7) {
        0...0b0010_111 => @as(u16, code7) + 256,
        0b0010_111 + 1...0b1011_111 => (@as(u16, code7) << 1) + @as(u16, try d.takeIntBits(u1)) - 0b0011_0000,
        0b1011_111 + 1...0b1100_011 => (@as(u16, code7 - 0b1100000) << 1) + try d.takeIntBits(u1) + 280,
        else => (@as(u16, code7 - 0b1100_100) << 2) + @as(u16, @bitReverse(try d.takeIntBits(u2))) + 144,
    };
}

pub const Symbol = packed struct(u16) {
    value: u12 = 0,
    code_bits: u4 = 0, // number of bits in code 0-15
};

pub const LiteralDecoder = HuffmanDecoder(286, 15, 9);
pub const DistanceDecoder = HuffmanDecoder(30, 15, 9);
pub const CodegenDecoder = HuffmanDecoder(19, 7, 7);

/// Creates huffman tree codes from list of code lengths (in `build`).
///
/// `find` then finds symbol for code bits. Code can be any length between 1 and
/// 15 bits. When calling `find` we don't know how many bits will be used to
/// find symbol. When symbol is returned it has code_bits field which defines
/// how much we should advance in bit stream.
///
/// Lookup table is used to map 15 bit int to symbol. Same symbol is written
/// many times in this table; 32K places for 286 (at most) symbols.
/// Small lookup table is optimization for faster search.
/// It is variation of the algorithm explained in [zlib](https://github.com/madler/zlib/blob/643e17b7498d12ab8d15565662880579692f769d/doc/algorithm.txt#L92)
/// with difference that we here use statically allocated arrays.
fn HuffmanDecoder(
    comptime alphabet_size: u16,
    comptime max_code_bits: u4,
    comptime lookup_bits: u4,
) type {
    const lookup_shift = max_code_bits - lookup_bits;
    const lookup_mask = (1 << lookup_bits) - 1;

    return struct {
        // lookup table code -> symbol
        // for values with code_bits == 0, symbol is the index of the first node in linked
        // if the index of the first node is 0xfff, it is an invalid code
        lookup: [1 << lookup_bits]Symbol = undefined,
        linked: if (lookup_bits == max_code_bits) void else [alphabet_size]struct {
            // sym.value is the next index in linked where the current index ends the chain
            // the actual symbol is this nodes's index
            sym: Symbol,
            code: u16,
        } = undefined,

        const Self = @This();

        fn reverseIdx(idx: usize) u16 {
            return @bitReverse(@as(@Int(.unsigned, lookup_bits), @intCast(idx)));
        }

        /// Generates symbols and lookup tables from list of code lens for each symbol.
        pub fn generate(self: *Self, lens: []const u4) !void {
            try checkCompleteness(lens);

            var buckets: [1 + @as(usize, max_code_bits)][alphabet_size]Symbol = undefined;
            var bucket_len: [buckets.len]u16 = @splat(0);
            for (0.., lens) |symbol, bits| {
                buckets[bits][bucket_len[bits]] = .{
                    .value = @intCast(symbol),
                    .code_bits = bits,
                };
                bucket_len[bits] += 1;
            }

            var code: u16 = 0;
            var idx: u16 = 0;
            for (1..lookup_bits + 1) |bits| {
                const inc = @as(u16, 1) << @intCast(max_code_bits - bits);
                for (buckets[bits][0..bucket_len[bits]]) |lookup_sym| {
                    const next_code = code + inc;
                    const next_idx = next_code >> lookup_shift;
                    for (idx..next_idx) |i| {
                        self.lookup[reverseIdx(i)] = lookup_sym;
                    }
                    code = next_code;
                    idx = next_idx;
                }
            }
            for (lookup_bits + 1..buckets.len) |bits| {
                const inc = @as(u16, 1) << @intCast(max_code_bits - bits);
                for (buckets[bits][0..bucket_len[bits]]) |linked_sym| {
                    const next_code = code + inc;
                    const next_idx = next_code >> lookup_shift;

                    const ri = reverseIdx(idx);
                    const next: Symbol = .{
                        .value = self.lookup[ri].value,
                        .code_bits = linked_sym.code_bits,
                    };
                    self.linked[linked_sym.value] = .{
                        .sym = next,
                        .code = @bitReverse(@as(@Int(.unsigned, max_code_bits), @intCast(code))),
                    };
                    self.lookup[ri] = .{ .value = linked_sym.value, .code_bits = 0 };

                    code = next_code;
                    idx = next_idx;
                }
            }

            // Invalid codes
            for (idx..self.lookup.len) |i| {
                self.lookup[reverseIdx(i)] = .{ .value = 0xfff, .code_bits = 0 };
            }
        }

        /// Given the list of code lengths check that it represents a canonical
        /// Huffman code for n symbols.
        ///
        /// Reference: https://github.com/madler/zlib/blob/5c42a230b7b468dff011f444161c0145b5efae59/contrib/puff/puff.c#L340
        fn checkCompleteness(lens: []const u4) !void {
            if (alphabet_size == 286)
                if (lens[256] == 0) return error.MissingEndOfBlockCode;

            var count: [@as(usize, max_code_bits) + 1]u16 = @splat(0);
            var max: usize = 0;
            for (lens) |n| {
                if (n == 0) continue;
                if (n > max) max = n;
                count[n] += 1;
            }
            if (max == 0) // empty tree
                return;

            // check for an over-subscribed or incomplete set of lengths
            var left: usize = 1; // one possible code of zero length
            for (1..count.len) |len| {
                left <<= 1; // one more bit, double codes left
                if (count[len] > left)
                    return error.OversubscribedHuffmanTree;
                left -= count[len]; // deduct count from possible codes
            }
            if (left > 0) { // left > 0 means incomplete
                // incomplete code ok only for single length 1 code
                if (max_code_bits > 7 and max == count[0] + count[1]) return;
                return error.IncompleteHuffmanTree;
            }
        }

        /// Finds symbol for lookup table code.
        pub fn find(self: *Self, code: u16) !Symbol {
            // try to find in lookup table
            const idx = code & lookup_mask;
            const sym = self.lookup[idx];
            if (sym.code_bits != 0) return sym;
            // if not use linked list of symbols with same prefix
            return self.findLinked(code, sym.value);
        }

        fn findLinked(self: *Self, code: u16, start: u16) !Symbol {
            if (start == 0xfff) return error.InvalidCode;
            if (lookup_bits == max_code_bits) unreachable;
            var pos = start;
            while (true) {
                const node = self.linked[pos];
                const shift = -%node.sym.code_bits;
                // compare code_bits number of upper bits
                if ((code ^ node.code) << shift == 0)
                    return .{ .value = @intCast(pos), .code_bits = node.sym.code_bits };
                pos = node.sym.value;
            }
        }
    };
}

test "init/find" {
    // example data from: https://youtu.be/SJPvNi4HrWQ?t=8423
    const code_lens = [_]u4{ 4, 3, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 3, 2 };
    var h: CodegenDecoder = .{};
    try h.generate(&code_lens);

    // All possible codes for each symbol.
    // Lookup table has 126 elements, to cover all possible 7 bit codes.
    for (0b0000_000..0b0100_000) |c| // 0..32 (32)
        try testing.expectEqual(
            Symbol{ .value = 3, .code_bits = 2 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b0100_000..0b1000_000) |c| // 32..64 (32)
        try testing.expectEqual(
            Symbol{ .value = 18, .code_bits = 2 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b1000_000..0b1010_000) |c| // 64..80 (16)
        try testing.expectEqual(
            Symbol{ .value = 1, .code_bits = 3 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b1010_000..0b1100_000) |c| // 80..96 (16)
        try testing.expectEqual(
            Symbol{ .value = 4, .code_bits = 3 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b1100_000..0b1110_000) |c| // 96..112 (16)
        try testing.expectEqual(
            Symbol{ .value = 17, .code_bits = 3 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b1110_000..0b1111_000) |c| // 112..120 (8)
        try testing.expectEqual(
            Symbol{ .value = 0, .code_bits = 4 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );

    for (0b1111_000..0b1_0000_000) |c| // 120...128 (8)
        try testing.expectEqual(
            Symbol{ .value = 16, .code_bits = 4 },
            try h.find(@bitReverse(@as(u7, @intCast(c)))),
        );
}

test "encode/decode literals" {
    // Check that the example in RFC 1951 section 3.2.2 works (plus some zeroes)
    const max_bits = 5;
    var decoder: HuffmanDecoder(16, max_bits, 3) = .{};
    try decoder.generate(&.{ 3, 3, 3, 3, 0, 0, 3, 2, 4, 4 });

    inline for (0.., .{
        @as(u3, 0b010),
        @as(u3, 0b011),
        @as(u3, 0b100),
        @as(u3, 0b101),
        @as(u0, 0),
        @as(u0, 0),
        @as(u3, 0b110),
        @as(u2, 0b00),
        @as(u4, 0b1110),
        @as(u4, 0b1111),
    }) |i, code| {
        const bits = @bitSizeOf(@TypeOf(code));
        if (bits == 0) continue;
        for (0..1 << (max_bits - bits)) |extra| {
            const full = (@as(u16, code) << (max_bits - bits)) | @as(u16, @intCast(extra));
            const symbol = try decoder.find(@bitReverse(@as(u5, @intCast(full))));
            try testing.expectEqual(i, symbol.value);
            try testing.expectEqual(bits, symbol.code_bits);
        }
    }
}

test "non compressed block (type 0)" {
    try testDecompress(.raw, &[_]u8{
        0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate fixed buffer header len, nlen
        'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // non compressed data
    }, "Hello world\n");
}

test "fixed code block (type 1)" {
    try testDecompress(.raw, &[_]u8{
        0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0x28, 0xcf, // deflate data block type 1
        0x2f, 0xca, 0x49, 0xe1, 0x02, 0x00,
    }, "Hello world\n");
}

test "dynamic block (type 2)" {
    try testDecompress(.raw, &[_]u8{
        0x3d, 0xc6, 0x39, 0x11, 0x00, 0x00, 0x0c, 0x02, // deflate data block type 2
        0x30, 0x2b, 0xb5, 0x52, 0x1e, 0xff, 0x96, 0x38,
        0x16, 0x96, 0x5c, 0x1e, 0x94, 0xcb, 0x6d, 0x01,
    }, "ABCDEABCD ABCDEABCD");
}

test "gzip non compressed block (type 0)" {
    try testDecompress(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, // gzip header (10 bytes)
        0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate fixed buffer header len, nlen
        'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // non compressed data
        0xd5, 0xe0, 0x39, 0xb7, // gzip footer: checksum
        0x0c, 0x00, 0x00, 0x00, // gzip footer: size
    }, "Hello world\n");
}

test "gzip fixed code block (type 1)" {
    try testDecompress(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x03, // gzip header (10 bytes)
        0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0x28, 0xcf, // deflate data block type 1
        0x2f, 0xca, 0x49, 0xe1, 0x02, 0x00,
        0xd5, 0xe0, 0x39, 0xb7, 0x0c, 0x00, 0x00, 0x00, // gzip footer (chksum, len)
    }, "Hello world\n");
}

test "gzip dynamic block (type 2)" {
    try testDecompress(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, // gzip header (10 bytes)
        0x3d, 0xc6, 0x39, 0x11, 0x00, 0x00, 0x0c, 0x02, // deflate data block type 2
        0x30, 0x2b, 0xb5, 0x52, 0x1e, 0xff, 0x96, 0x38,
        0x16, 0x96, 0x5c, 0x1e, 0x94, 0xcb, 0x6d, 0x01,
        0x17, 0x1c, 0x39, 0xb4, 0x13, 0x00, 0x00, 0x00, // gzip footer (chksum, len)
    }, "ABCDEABCD ABCDEABCD");
}

test "gzip header with name" {
    try testDecompress(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x08, 0xe5, 0x70, 0xb1, 0x65, 0x00, 0x03, 0x68, 0x65, 0x6c, 0x6c, 0x6f, 0x2e,
        0x74, 0x78, 0x74, 0x00, 0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0x28, 0xcf, 0x2f, 0xca, 0x49, 0xe1,
        0x02, 0x00, 0xd5, 0xe0, 0x39, 0xb7, 0x0c, 0x00, 0x00, 0x00,
    }, "Hello world\n");
}

test "zlib decompress non compressed block (type 0)" {
    try testDecompress(.zlib, &[_]u8{
        0x78, 0b10_0_11100, // zlib header (2 bytes)
        0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate fixed buffer header len, nlen
        'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // non compressed data
        0x1c, 0xf2, 0x04, 0x47, // zlib footer: checksum
    }, "Hello world\n");
}

test "failing end-of-stream" {
    try testFailure(.raw, @embedFile("testdata/fuzz/end-of-stream.input"), error.EndOfStream);
}
test "failing invalid-distance" {
    try testFailure(.raw, @embedFile("testdata/fuzz/invalid-distance.input"), error.InvalidMatch);
}
test "failing invalid-tree01" {
    try testFailure(.raw, @embedFile("testdata/fuzz/invalid-tree01.input"), error.IncompleteHuffmanTree);
}
test "failing invalid-tree02" {
    try testFailure(.raw, @embedFile("testdata/fuzz/invalid-tree02.input"), error.IncompleteHuffmanTree);
}
test "failing invalid-tree03" {
    try testFailure(.raw, @embedFile("testdata/fuzz/invalid-tree03.input"), error.IncompleteHuffmanTree);
}
test "failing lengths-overflow" {
    try testFailure(.raw, @embedFile("testdata/fuzz/lengths-overflow.input"), error.InvalidDynamicBlockHeader);
}
test "failing out-of-codes" {
    try testFailure(.raw, @embedFile("testdata/fuzz/out-of-codes.input"), error.InvalidCode);
}
test "failing puff01" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff01.input"), error.WrongStoredBlockNlen);
}
test "failing puff02" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff02.input"), error.EndOfStream);
}
test "failing puff04" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff04.input"), error.InvalidCode);
}
test "failing puff05" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff05.input"), error.EndOfStream);
}
test "failing puff06" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff06.input"), error.EndOfStream);
}
test "failing puff08" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff08.input"), error.InvalidCode);
}
test "failing puff10" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff10.input"), error.InvalidCode);
}
test "failing puff11" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff11.input"), error.InvalidMatch);
}
test "failing puff12" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff12.input"), error.InvalidDynamicBlockHeader);
}
test "failing puff13" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff13.input"), error.IncompleteHuffmanTree);
}
test "failing puff14" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff14.input"), error.EndOfStream);
}
test "failing puff15" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff15.input"), error.IncompleteHuffmanTree);
}
test "failing puff16" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff16.input"), error.InvalidDynamicBlockHeader);
}
test "failing puff17" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff17.input"), error.MissingEndOfBlockCode);
}
test "failing fuzz1" {
    try testFailure(.raw, @embedFile("testdata/fuzz/fuzz1.input"), error.InvalidDynamicBlockHeader);
}
test "failing fuzz2" {
    try testFailure(.raw, @embedFile("testdata/fuzz/fuzz2.input"), error.InvalidDynamicBlockHeader);
}
test "failing fuzz3" {
    try testFailure(.raw, @embedFile("testdata/fuzz/fuzz3.input"), error.InvalidMatch);
}
test "failing fuzz4" {
    try testFailure(.raw, @embedFile("testdata/fuzz/fuzz4.input"), error.OversubscribedHuffmanTree);
}
test "failing puff18" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff18.input"), error.OversubscribedHuffmanTree);
}
test "failing puff19" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff19.input"), error.OversubscribedHuffmanTree);
}
test "failing puff20" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff20.input"), error.OversubscribedHuffmanTree);
}
test "failing puff21" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff21.input"), error.OversubscribedHuffmanTree);
}
test "failing puff22" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff22.input"), error.OversubscribedHuffmanTree);
}
test "failing puff23" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff23.input"), error.OversubscribedHuffmanTree);
}
test "failing puff24" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff24.input"), error.IncompleteHuffmanTree);
}
test "failing puff25" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff25.input"), error.OversubscribedHuffmanTree);
}
test "failing puff26" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff26.input"), error.InvalidDynamicBlockHeader);
}
test "failing puff27" {
    try testFailure(.raw, @embedFile("testdata/fuzz/puff27.input"), error.InvalidDynamicBlockHeader);
}

test "deflate-stream" {
    try testDecompress(
        .raw,
        @embedFile("testdata/fuzz/deflate-stream.input"),
        @embedFile("testdata/fuzz/deflate-stream.expect"),
    );
}

test "empty-distance-alphabet01" {
    try testDecompress(.raw, @embedFile("testdata/fuzz/empty-distance-alphabet01.input"), "");
}

test "empty-distance-alphabet02" {
    try testDecompress(.raw, @embedFile("testdata/fuzz/empty-distance-alphabet02.input"), "");
}

test "puff03" {
    try testDecompress(.raw, @embedFile("testdata/fuzz/puff03.input"), &.{0xa});
}

test "puff09" {
    try testDecompress(.raw, @embedFile("testdata/fuzz/puff09.input"), "P");
}

test "invalid block type" {
    try testFailure(.raw, &[_]u8{0b110}, error.InvalidBlockType);
}

test "bug 18966" {
    try testDecompress(
        .gzip,
        @embedFile("testdata/fuzz/bug_18966.input"),
        @embedFile("testdata/fuzz/bug_18966.expect"),
    );
}

test "truncated input ending when reading dynamic length bits" {
    try testFailure(.raw, &[_]u8{
        0x15, 0xd5, 0x07, 0x3b, 0x16, 0x0c, 0x03, 0x86,
        0x61, 0x2b, 0xa3, 0xec, 0xec, 0x15, 0x95, 0x6c,
        0x92, 0x4d, 0x19, 0x95, 0x4a, 0xb6, 0x22, 0x23,
        0xc9,
    }, error.EndOfStream);
}

test "reading into empty buffer" {
    // Inspired by https://github.com/ziglang/zig/issues/19895
    const input = &[_]u8{
        0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate fixed buffer header len, nlen
        'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // non compressed data
    };
    var in: Reader = .fixed(input);
    var decomp: Decompress = .init(&in, .raw, &.{});
    const r = &decomp.reader;
    var bufs: [1][]u8 = .{&.{}};
    try testing.expectEqual(0, try r.readVec(&bufs));
}

test "zlib header" {
    // Truncated header
    try testFailure(.zlib, &[_]u8{0x78}, error.EndOfStream);

    // Wrong CM
    try testFailure(.zlib, &[_]u8{ 0x79, 0x94 }, error.BadZlibHeader);

    // Wrong CINFO
    try testFailure(.zlib, &[_]u8{ 0x88, 0x98 }, error.BadZlibHeader);

    // Truncated checksum
    try testFailure(.zlib, &[_]u8{ 0x78, 0xda, 0x03, 0x00, 0x00 }, error.EndOfStream);
}

test "gzip header" {
    // Truncated header
    try testFailure(.gzip, &[_]u8{ 0x1f, 0x8B }, error.EndOfStream);

    // Wrong CM
    try testFailure(.gzip, &[_]u8{
        0x1f, 0x8b, 0x09, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x03,
    }, error.BadGzipHeader);

    // Truncated checksum
    try testFailure(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x03, 0x03, 0x00, 0x00, 0x00, 0x00,
    }, error.EndOfStream);

    // Truncated initial size field
    try testFailure(.gzip, &[_]u8{
        0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x03, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00,
    }, error.EndOfStream);

    try testDecompress(.gzip, &[_]u8{
        // GZIP header
        0x1f, 0x8b, 0x08, 0x12, 0x00, 0x09, 0x6e, 0x88, 0x00, 0xff, 0x48, 0x65, 0x6c, 0x6c, 0x6f, 0x00,
        // header.FHCRC (should cover entire header)
        0x99, 0xd6,
        // GZIP data
        0x01, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    }, "");
}

test "zlib should not overshoot" {
    // Compressed zlib data with extra 4 bytes at the end.
    const data = [_]u8{
        0x78, 0x9c, 0x73, 0xce, 0x2f, 0xa8, 0x2c, 0xca, 0x4c, 0xcf, 0x28, 0x51, 0x08, 0xcf, 0xcc, 0xc9,
        0x49, 0xcd, 0x55, 0x28, 0x4b, 0xcc, 0x53, 0x08, 0x4e, 0xce, 0x48, 0xcc, 0xcc, 0xd6, 0x51, 0x08,
        0xce, 0xcc, 0x4b, 0x4f, 0x2c, 0xc8, 0x2f, 0x4a, 0x55, 0x30, 0xb4, 0xb4, 0x34, 0xd5, 0xb5, 0x34,
        0x03, 0x00, 0x8b, 0x61, 0x0f, 0xa4, 0x52, 0x5a, 0x94, 0x12,
    };

    var reader: std.Io.Reader = .fixed(&data);

    var decompress_buffer: [flate.max_window_len]u8 = undefined;
    var decompress: Decompress = .init(&reader, .zlib, &decompress_buffer);
    var out: [128]u8 = undefined;

    {
        const n = try decompress.reader.readSliceShort(&out);
        try std.testing.expectEqual(46, n);
        try std.testing.expectEqualStrings("Copyright Willem van Schaik, Singapore 1995-96", out[0..n]);
    }

    // 4 bytes after compressed chunk are available in reader.
    const n = try reader.readSliceShort(&out);
    try std.testing.expectEqual(n, 4);
    try std.testing.expectEqualSlices(u8, data[data.len - 4 .. data.len], out[0..n]);
}

fn testFailure(container: Container, in: []const u8, expected_err: anyerror) !void {
    var reader: Reader = .fixed(in);
    var aw: Writer.Allocating = .init(testing.allocator);
    defer aw.deinit();

    var decompress: Decompress = .init(&reader, container, &.{});
    try testing.expectError(error.ReadFailed, decompress.reader.streamRemaining(&aw.writer));
    try testing.expectEqual(expected_err, decompress.err orelse return error.TestFailed);
}

fn testDecompress(container: Container, compressed: []const u8, expected_plain: []const u8) !void {
    var aw: std.Io.Writer.Allocating = .init(testing.allocator);
    defer aw.deinit();

    // Decompress once using the normal methods.
    {
        var in: std.Io.Reader = .fixed(compressed);
        var decompress: Decompress = .init(&in, container, &.{});
        const decompressed_len = try decompress.reader.streamRemaining(&aw.writer);
        try testing.expectEqual(expected_plain.len, decompressed_len);
        try testing.expectEqualSlices(u8, expected_plain, aw.written());
    }

    // Decompress again by streaming one byte at a time to check that there aren't
    // any problems with things like writing partial matches, etc.
    aw.clearRetainingCapacity();
    {
        var in: std.Io.Reader = .fixed(compressed);
        var decompress: Decompress = .init(&in, container, &.{});
        var decompressed_len: usize = 0;
        while (true) {
            decompressed_len += decompress.reader.stream(&aw.writer, .limited(1)) catch |err| switch (err) {
                error.EndOfStream => break,
                else => |e| return e,
            };
        }
        try testing.expectEqual(expected_plain.len, decompressed_len);
        try testing.expectEqualSlices(u8, expected_plain, aw.written());
    }
}