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
stdassertflatetestingWriterReaderContainerDecompresstokenBlockTypeStateErrordirect_vtableindirect_vtableinitrebaseFalliblerebasediscardDirectdiscardIndirectreadVecstreamIndirectInnerdecodeLengthdecodeDistancedynamicCodeLengthdecodeSymbolstreamDirectstreamIndirectstreamFalliblestreamInnerwriteMatchpeekBitspeekBitsEndingtossBitstakeBitsalignBitsForwardpeekBitsShortpeekBitsShortEndingtossBitsShorttakeIntBitspeekIntBitsShortreadFixedCodeSymbolLiteralDecoderDistanceDecoderCodegenDecoderHuffmanDecodertestFailuretestDecompress
std.compress.flate.Decompress.alignBitsForward
function
fn alignBitsForward(d: *Decompress) void
Parameters
d: *Decompress
std.compress.flate.Decompress.assert
alias
Alias of std.debug.assert
std.compress.flate.Decompress.BlockType
container
Fields
stored = 0
fixed = 1
dynamic = 2
invalid = 3
std.compress.flate.Decompress.CodegenDecoder
type
std.compress.flate.Decompress.Container
alias
Alias of std.compress.flate.Container
std.compress.flate.Decompress.decodeDistance
function
fn decodeDistance(self: *Decompress, code_int: u5) !u16
Parameters
self: *Decompress
code_int: u5
std.compress.flate.Decompress.decodeLength
function
fn decodeLength(self: *Decompress, code_int: u5) !u16
Parameters
self: *Decompress
code_int: u5
std.compress.flate.Decompress.decodeSymbol
function
fn decodeSymbol(self: *Decompress, decoder: anytype) !u16
Parameters
self: *Decompress
std.compress.flate.Decompress.Decompress
alias
Alias of std.compress.flate.Decompress
std.compress.flate.Decompress.direct_vtable
constant
Reader.VTable
std.compress.flate.Decompress.discardDirect
function
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
Errors
- EndOfStream
- ReadFailed
See the
Readerimplementation for detailed diagnostics.
std.compress.flate.Decompress.discardIndirect
function
fn discardIndirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize
Parameters
Errors
- EndOfStream
- ReadFailed
See the
Readerimplementation for detailed diagnostics.
std.compress.flate.Decompress.DistanceDecoder
type
std.compress.flate.Decompress.dynamicCodeLength
function
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
std.compress.flate.Decompress.Error
error-set
Errors
std.compress.flate.Decompress.flate
alias
Alias of std.compress.flate
std.compress.flate.Decompress.HuffmanDecoder
type-function
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
std.compress.flate.Decompress.HuffmanDecoder.checkCompleteness
function
Given the list of code lengths check that it represents a canonical Huffman code for n symbols.
fn checkCompleteness(lens: []const u4) !void
Parameters
lens: []const u4
std.compress.flate.Decompress.HuffmanDecoder.find
function
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
fn findLinked(self: *Self, code: u16, start: u16) !Symbol
Parameters
std.compress.flate.Decompress.HuffmanDecoder.generate
function
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
fn reverseIdx(idx: usize) u16
Parameters
idx: usize
std.compress.flate.Decompress.HuffmanDecoder.Self
alias
std.compress.flate.Decompress.indirect_vtable
constant
Reader.VTable
std.compress.flate.Decompress.init
function
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
std.compress.flate.Decompress.LiteralDecoder
type
std.compress.flate.Decompress.peekBits
function
fn peekBits(d: *Decompress, n: u4) !u16
Parameters
d: *Decompress
n: u4
std.compress.flate.Decompress.peekBitsEnding
function
fn peekBitsEnding(d: *Decompress, n: u4) !u16
Parameters
d: *Decompress
n: u4
std.compress.flate.Decompress.peekBitsShort
function
fn peekBitsShort(d: *Decompress, n: u4) !u16
Parameters
d: *Decompress
n: u4
std.compress.flate.Decompress.peekBitsShortEnding
function
fn peekBitsShortEnding(d: *Decompress, n: u4) !u16
Parameters
d: *Decompress
n: u4
std.compress.flate.Decompress.peekIntBitsShort
function
fn peekIntBitsShort(d: *Decompress, T: type) !T
Parameters
d: *Decompress
T: type
std.compress.flate.Decompress.Reader
alias
Alias of std.Io.Reader
std.compress.flate.Decompress.readFixedCode
function
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
d: *Decompress
std.compress.flate.Decompress.readVec
function
fn readVec(r: *Reader, data: [][]u8) Reader.Error!usize
Parameters
r: *Reader
data: [][]u8
Errors
- EndOfStream
- ReadFailed
See the
Readerimplementation for detailed diagnostics.
std.compress.flate.Decompress.rebase
function
fn rebase(r: *Reader, capacity: usize) void
Parameters
r: *Reader
capacity: usize
std.compress.flate.Decompress.rebaseFallible
function
fn rebaseFallible(r: *Reader, capacity: usize) Reader.RebaseError!void
Parameters
r: *Reader
capacity: usize
Errors
std.compress.flate.Decompress.State
container
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
Alias of std
std.compress.flate.Decompress.streamDirect
function
fn streamDirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize
Parameters
Errors
std.compress.flate.Decompress.streamFallible
function
fn streamFallible(d: *Decompress, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize
Parameters
Errors
std.compress.flate.Decompress.streamIndirect
function
fn streamIndirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize
Parameters
Errors
std.compress.flate.Decompress.streamIndirectInner
function
fn streamIndirectInner(d: *Decompress) Reader.Error!usize
Parameters
d: *Decompress
Errors
- EndOfStream
- ReadFailed
See the
Readerimplementation for detailed diagnostics.
std.compress.flate.Decompress.streamInner
function
fn streamInner(d: *Decompress, w: *Writer, limit: std.Io.Limit) (Error || Reader.StreamError)!usize
Parameters
std.compress.flate.Decompress.Symbol
container
Fields
value: u12 = 0
code_bits: u4 = 0
std.compress.flate.Decompress.takeBits
function
fn takeBits(d: *Decompress, n: u4) !u16
Parameters
d: *Decompress
n: u4
std.compress.flate.Decompress.takeIntBits
function
fn takeIntBits(d: *Decompress, T: type) !T
Parameters
d: *Decompress
T: type
std.compress.flate.Decompress.testDecompress
function
fn testDecompress(container: Container, compressed: []const u8, expected_plain: []const u8) !void
Parameters
std.compress.flate.Decompress.testFailure
function
fn testFailure(container: Container, in: []const u8, expected_err: anyerror) !void
Parameters
std.compress.flate.Decompress.testing
alias
Alias of std.testing
std.compress.flate.Decompress.token
alias
Alias of std.compress.flate.token
std.compress.flate.Decompress.tossBits
function
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
fn tossBitsShort(d: *Decompress, n: u4) !void
Parameters
d: *Decompress
n: u4
std.compress.flate.Decompress.writeMatch
function
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
std.compress.flate.Decompress.Writer
alias
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());
}
}