Artifact 6c1ba0ebe3ca0f306310c0044bb963cd2cb042898097d166bf56dd42f050772b:
- File
src/flate/Decompress.zig
— part of check-in
[46fcd75fc3]
at
2026-09-19 14:40:06
on branch trunk
— container: a damaged container is an error, never a crash or wrong bytes
The first nightly soak flipped one bit in a valid container and brought the process down inside the standard inflate: an integer underflow in its end-of-input bit peek that a truncated stream can arrange, reachable from any peer through every sync body. The decoder is now the tree's own copy of the standard one (Zig 0.16.0, MIT) with the comparison reordered so the stream ends, and its origin noted. With the crash gone the same bytes decoded to 58 bytes reported as good: the flip made a block final, and the zlib footer's Adler-32 was read but never checked, by the decoder or by us. The codec now requires a finished stream and verifies the footer against the output. The exact bytes are a fixed test. (user: dmestas, size: 39860) [annotate] [blame] [check-ins using]
//! The standard library's inflate (Zig 0.16.0, std/compress/flate/Decompress.zig, //! MIT), carried here for one fix. `peekBitsEnding` computed //! `left.len * 8 - d.consumed_bits` and that subtraction underflows when the //! input ends with more bits consumed than the buffer still holds, which a //! damaged zlib stream can arrange: a container with one bit flipped, found //! by the nightly fuzz soak (transport_frame_garbage, seed 0x25769f75b7f1421c), //! took the process down in Debug and ReleaseSafe and read past the buffer //! in ReleaseFast. Every sync request and reply passes through this decoder, //! so any peer could send those bytes. The comparison is rearranged so the //! stream simply ends. Nothing else is changed; the file goes back to the //! standard library the moment the fix is upstream. Its fixture-backed //! tests are omitted, since the installed toolchain ships no testdata; the //! self-contained ones stay. const std = @import("std"); 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: u16, dynamic_block, dynamic_block_literal: u8, dynamic_block_match: 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 => return error.ReadFailed, error.EndOfStream => return error.EndOfStream, }; assert(n <= @intFromEnum(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 => return error.WriteFailed, 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 = @intFromEnum(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 = @enumFromInt(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 @intFromEnum(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)); continue :sw .{ .fixed_block_match = length }; } 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 @intFromEnum(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 => |length| { if (remaining >= length) { @branchHint(.likely); const distance = try d.decodeDistance(@bitReverse(try d.takeIntBits(u5))); try writeMatch(w, length, distance); remaining -= length; continue :sw .fixed_block; } else { d.state = .{ .fixed_block_match = length }; return @intFromEnum(limit) - remaining; } }, // 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)); continue :sw .{ .dynamic_block_match = length }; } 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 @intFromEnum(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 => |length| { if (remaining >= length) { @branchHint(.likely); remaining -= length; const dsm = try d.decodeSymbol(&d.dst_dec); const distance = try d.decodeDistance(@intCast(dsm)); try writeMatch(w, length, distance); continue :sw .dynamic_block; } else { d.state = .{ .dynamic_block_match = length }; return @intFromEnum(limit) - remaining; } }, .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 @intFromEnum(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. fn writeMatch(w: *Writer, length: u16, distance: u16) !void { if (w.end < distance) return error.InvalidMatch; assert(length >= token.min_length); 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(); // Reordered from `left.len * 8 - d.consumed_bits < n`: that subtraction // underflows once the input has ended with more bits consumed than the // buffer still holds, and the stream has ended either way. if (left.len * 8 < @as(usize, 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 = [_]u16{0} ** (@as(usize, max_code_bits) + 1); 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 "invalid block type" { try testFailure(.raw, &[_]u8{0b110}, error.InvalidBlockType); } 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 in: std.Io.Reader = .fixed(compressed); var aw: std.Io.Writer.Allocating = .init(testing.allocator); defer aw.deinit(); 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()); }