Artifact 3119a2f89ea79d429636bc00eace0a6dd90c94facc0e206250bc2b1956a5356b:
- File
src/flate/Decompress.zig
— part of check-in
[362f18d357]
at
2026-09-23 18:33:13
on branch trunk
— inflate: a truncated dynamic-block header is the end of the stream, not a crash
tossBitsShort added the consumed bits where it must subtract them, so a header ending one byte short tossed past the end of the input and the next peek read a wrapped length off the stack. Found by the nightly soak four nights running. Release 0.3.29. (user: dmestas, size: 40860) [annotate] [blame] [check-ins using]
//! The standard library's inflate (Zig 0.16.0, std/compress/flate/Decompress.zig, //! MIT), carried here for two fixes, both in end-of-input bit accounting and //! both found by the nightly fuzz soak. //! //! First, `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. //! //! Second, `tossBitsShort` checked `bufferedLen() * 8 + consumed_bits < n`, //! adding the bits already consumed where it must subtract them. A dynamic //! block header ending one byte short then tossed past the end of the input, //! and the next `peekBitsShortEnding` sliced `buffer[seek..end]` with seek //! past end and read a wrapped length off the stack (sync_container_round_trip, //! seed 0x9ee426e8f2d2bd0b, and three other nights' seeds). Fixed the same way, //! with no subtraction. //! //! 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 { // The bits left are the buffered bytes' bits LESS the ones already // consumed from the first of them. Upstream adds them instead, so with one // byte buffered and six of its bits consumed a seven-bit toss passed this // check and advanced the reader past its end; the next peek then read a // wrapped length. Written with no subtraction, as in `peekBitsEnding`. if (d.input.bufferedLen() * 8 < @as(usize, 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()); }