1const std = @import("../../std.zig");
2const assert = std.debug.assert;
3const flate = std.compress.flate;
4const testing = std.testing;
5const Writer = std.Io.Writer;
6const Reader = std.Io.Reader;
7const Container = flate.Container;
8
9const Decompress = @This();
10const token = @import("token.zig");
11
12input: *Reader,
13consumed_bits: u3,
14
15reader: Reader,
16
17container_metadata: Container.Metadata,
18
19lit_dec: LiteralDecoder,
20dst_dec: DistanceDecoder,
21
22final_block: bool,
23state: State,
24
25err: ?Error,
26
27const BlockType = enum(u2) {
28 stored = 0,
29 fixed = 1,
30 dynamic = 2,
31 invalid = 3,
32};
33
34const State = union(enum) {
35 protocol_header,
36 block_header,
37 stored_block: u16,
38 fixed_block,
39 fixed_block_literal: u8,
40 fixed_block_match: struct {
41 distance: u16,
42 length: u16,
43 },
44 dynamic_block,
45 dynamic_block_literal: u8,
46 dynamic_block_match: struct {
47 distance: u16,
48 length: u16,
49 },
50 protocol_footer,
51 end,
52};
53
54pub const Error = Container.Error || error{
55 InvalidCode,
56 InvalidMatch,
57 WrongStoredBlockNlen,
58 InvalidBlockType,
59 InvalidDynamicBlockHeader,
60 ReadFailed,
61 OversubscribedHuffmanTree,
62 IncompleteHuffmanTree,
63 MissingEndOfBlockCode,
64 EndOfStream,
65};
66
67const direct_vtable: Reader.VTable = .{
68 .stream = streamDirect,
69 .rebase = rebaseFallible,
70 .discard = discardDirect,
71 .readVec = readVec,
72};
73
74const indirect_vtable: Reader.VTable = .{
75 .stream = streamIndirect,
76 .rebase = rebaseFallible,
77 .discard = discardIndirect,
78 .readVec = readVec,
79};
80
81/// `input` buffer is asserted to be at least 10 bytes, or EOF before then.
82///
83/// If `buffer` is provided then asserted to have `flate.max_window_len`
84/// capacity.
85pub fn init(input: *Reader, container: Container, buffer: []u8) Decompress {
86 if (buffer.len != 0) assert(buffer.len >= flate.max_window_len);
87 return .{
88 .reader = .{
89 .vtable = if (buffer.len == 0) &direct_vtable else &indirect_vtable,
90 .buffer = buffer,
91 .seek = 0,
92 .end = 0,
93 },
94 .input = input,
95 .consumed_bits = 0,
96 .container_metadata = .init(container),
97 .lit_dec = .{},
98 .dst_dec = .{},
99 .final_block = false,
100 .state = .protocol_header,
101 .err = null,
102 };
103}
104
105fn rebaseFallible(r: *Reader, capacity: usize) Reader.RebaseError!void {
106 rebase(r, capacity);
107}
108
109fn rebase(r: *Reader, capacity: usize) void {
110 assert(capacity <= r.buffer.len - flate.history_len);
111 assert(r.end + capacity > r.buffer.len);
112 const discard_n = @min(r.seek, r.end - flate.history_len);
113 const keep = r.buffer[discard_n..r.end];
114 @memmove(r.buffer[0..keep.len], keep);
115 r.end = keep.len;
116 r.seek -= discard_n;
117}
118
119/// This could be improved so that when an amount is discarded that includes an
120/// entire frame, skip decoding that frame.
121fn discardDirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize {
122 if (r.end + flate.history_len > r.buffer.len) rebase(r, flate.history_len);
123 var writer: Writer = .{
124 .vtable = &.{
125 .drain = std.Io.Writer.Discarding.drain,
126 .sendFile = std.Io.Writer.Discarding.sendFile,
127 },
128 .buffer = r.buffer,
129 .end = r.end,
130 };
131 defer {
132 assert(writer.end != 0);
133 r.end = writer.end;
134 r.seek = r.end;
135 }
136 const n = r.stream(&writer, limit) catch |err| switch (err) {
137 error.WriteFailed => unreachable,
138 error.ReadFailed, error.EndOfStream => |e| return e,
139 };
140 assert(n <= @backingInt(limit));
141 return n;
142}
143
144fn discardIndirect(r: *Reader, limit: std.Io.Limit) Reader.Error!usize {
145 const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
146 if (r.end + flate.history_len > r.buffer.len) rebase(r, flate.history_len);
147 var writer: Writer = .{
148 .buffer = r.buffer,
149 .end = r.end,
150 .vtable = &.{ .drain = Writer.unreachableDrain },
151 };
152 {
153 defer r.end = writer.end;
154 _ = streamFallible(d, &writer, .limited(writer.buffer.len - writer.end)) catch |err| switch (err) {
155 error.WriteFailed => unreachable,
156 else => |e| return e,
157 };
158 }
159 const n = limit.minInt(r.end - r.seek);
160 r.seek += n;
161 return n;
162}
163
164fn readVec(r: *Reader, data: [][]u8) Reader.Error!usize {
165 _ = data;
166 const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
167 return streamIndirectInner(d);
168}
169
170fn streamIndirectInner(d: *Decompress) Reader.Error!usize {
171 const r = &d.reader;
172 if (r.buffer.len - r.end < flate.history_len) rebase(r, flate.history_len);
173 var writer: Writer = .{
174 .buffer = r.buffer,
175 .end = r.end,
176 .vtable = &.{
177 .drain = Writer.unreachableDrain,
178 .rebase = Writer.unreachableRebase,
179 },
180 };
181 defer r.end = writer.end;
182 _ = streamFallible(d, &writer, .limited(writer.buffer.len - writer.end)) catch |err| switch (err) {
183 error.WriteFailed => unreachable,
184 else => |e| return e,
185 };
186 return 0;
187}
188
189fn decodeLength(self: *Decompress, code_int: u5) !u16 {
190 if (code_int > 28) return error.InvalidCode;
191 const l: token.LenCode = .fromInt(code_int);
192 const base = l.base();
193 const extra = l.extraBits();
194 return token.min_length + (base | try self.takeBits(extra));
195}
196
197fn decodeDistance(self: *Decompress, code_int: u5) !u16 {
198 if (code_int > 29) return error.InvalidCode;
199 const d: token.DistCode = .fromInt(code_int);
200 const base = d.base();
201 const extra = d.extraBits();
202 return token.min_distance + (base | try self.takeBits(extra));
203}
204
205/// Decode code length symbol to code length. Writes decoded length into
206/// lens slice starting at position pos. Returns number of positions
207/// advanced.
208fn dynamicCodeLength(self: *Decompress, code: u16, lens: []u4, pos: usize) !usize {
209 if (pos >= lens.len)
210 return error.InvalidDynamicBlockHeader;
211
212 switch (code) {
213 0...15 => {
214 // Represent code lengths of 0 - 15
215 lens[pos] = @intCast(code);
216 return 1;
217 },
218 16 => {
219 // Copy the previous code length 3 - 6 times.
220 // The next 2 bits indicate repeat length
221 const n: u8 = @as(u8, try self.takeIntBits(u2)) + 3;
222 if (pos == 0 or pos + n > lens.len)
223 return error.InvalidDynamicBlockHeader;
224 for (0..n) |i| {
225 lens[pos + i] = lens[pos + i - 1];
226 }
227 return n;
228 },
229 // Repeat a code length of 0 for 3 - 10 times. (3 bits of length)
230 17 => return @as(u8, try self.takeIntBits(u3)) + 3,
231 // Repeat a code length of 0 for 11 - 138 times (7 bits of length)
232 18 => return @as(u8, try self.takeIntBits(u7)) + 11,
233 else => return error.InvalidDynamicBlockHeader,
234 }
235}
236
237fn decodeSymbol(self: *Decompress, decoder: anytype) !u16 {
238 // Maximum code len is 15 bits.
239 const sym = try decoder.find(try self.peekIntBitsShort(u15));
240 try self.tossBitsShort(sym.code_bits);
241 return sym.value;
242}
243
244fn streamDirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize {
245 const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
246 return streamFallible(d, w, limit);
247}
248
249fn streamIndirect(r: *Reader, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize {
250 const d: *Decompress = @alignCast(@fieldParentPtr("reader", r));
251 _ = limit;
252 _ = w;
253 return streamIndirectInner(d);
254}
255
256fn streamFallible(d: *Decompress, w: *Writer, limit: std.Io.Limit) Reader.StreamError!usize {
257 return streamInner(d, w, limit) catch |err| switch (err) {
258 error.EndOfStream => {
259 if (d.state == .end) {
260 return error.EndOfStream;
261 } else {
262 d.err = error.EndOfStream;
263 return error.ReadFailed;
264 }
265 },
266 error.WriteFailed => |e| return e,
267 else => |e| {
268 // In the event of an error, state is unmodified so that it can be
269 // better used to diagnose the failure.
270 d.err = e;
271 return error.ReadFailed;
272 },
273 };
274}
275
276fn streamInner(d: *Decompress, w: *Writer, limit: std.Io.Limit) (Error || Reader.StreamError)!usize {
277 var remaining = @backingInt(limit);
278 const in = d.input;
279 sw: switch (d.state) {
280 .protocol_header => switch (d.container_metadata.container()) {
281 .gzip => {
282 const Header = extern struct {
283 magic: u16 align(1),
284 method: u8,
285 flags: packed struct(u8) {
286 text: bool,
287 hcrc: bool,
288 extra: bool,
289 name: bool,
290 comment: bool,
291 reserved: u3,
292 },
293 mtime: u32 align(1),
294 xfl: u8,
295 os: u8,
296 };
297 const header = try in.takeStruct(Header, .little);
298 if (header.magic != 0x8b1f or header.method != 0x08)
299 return error.BadGzipHeader;
300 if (header.flags.extra) {
301 const extra_len = try in.takeInt(u16, .little);
302 try in.discardAll(extra_len);
303 }
304 if (header.flags.name) {
305 _ = try in.discardDelimiterInclusive(0);
306 }
307 if (header.flags.comment) {
308 _ = try in.discardDelimiterInclusive(0);
309 }
310 if (header.flags.hcrc) {
311 try in.discardAll(2);
312 }
313 continue :sw .block_header;
314 },
315 .zlib => {
316 const header = try in.takeArray(2);
317 const cmf: packed struct(u8) { cm: u4, cinfo: u4 } = @bitCast(header[0]);
318 if (cmf.cm != 8 or cmf.cinfo > 7) return error.BadZlibHeader;
319 continue :sw .block_header;
320 },
321 .raw => continue :sw .block_header,
322 },
323 .block_header => {
324 d.final_block = (try d.takeIntBits(u1)) != 0;
325 const block_type: BlockType = @fromBackingInt(@intCast(try d.takeIntBits(u2)));
326 switch (block_type) {
327 .stored => {
328 d.alignBitsForward();
329 // everything after this is byte aligned in stored block
330 const len = try in.takeInt(u16, .little);
331 const nlen = try in.takeInt(u16, .little);
332 if (len != ~nlen) return error.WrongStoredBlockNlen;
333 continue :sw .{ .stored_block = len };
334 },
335 .fixed => continue :sw .fixed_block,
336 .dynamic => {
337 const hlit: u16 = @as(u16, try d.takeIntBits(u5)) + 257; // number of ll code entries present - 257
338 const hdist: u16 = @as(u16, try d.takeIntBits(u5)) + 1; // number of distance code entries - 1
339 const hclen: u8 = @as(u8, try d.takeIntBits(u4)) + 4; // hclen + 4 code lengths are encoded
340
341 if (hlit > 286 or hdist > 30)
342 return error.InvalidDynamicBlockHeader;
343
344 // lengths for code lengths
345 var cl_lens: [19]u4 = @splat(0);
346 for (token.codegen_order[0..hclen]) |i| {
347 cl_lens[i] = try d.takeIntBits(u3);
348 }
349 var cl_dec: CodegenDecoder = .{};
350 try cl_dec.generate(&cl_lens);
351
352 // decoded code lengths
353 var dec_lens: [286 + 30]u4 = @splat(0);
354 var pos: usize = 0;
355 while (pos < hlit + hdist) {
356 const peeked = try d.peekIntBitsShort(u7);
357 const sym = try cl_dec.find(peeked);
358 try d.tossBitsShort(sym.code_bits);
359 pos += try d.dynamicCodeLength(sym.value, &dec_lens, pos);
360 }
361 if (pos > hlit + hdist) {
362 return error.InvalidDynamicBlockHeader;
363 }
364
365 // literal code lengths to literal decoder
366 try d.lit_dec.generate(dec_lens[0..hlit]);
367
368 // distance code lengths to distance decoder
369 try d.dst_dec.generate(dec_lens[hlit..][0..hdist]);
370
371 continue :sw .dynamic_block;
372 },
373 .invalid => return error.InvalidBlockType,
374 }
375 },
376 .stored_block => |remaining_len| {
377 const out: []u8 = if (remaining != 0)
378 try w.writableSliceGreedyPreserve(flate.history_len, 1)
379 else
380 &.{};
381 var limited_out: [1][]u8 = .{limit.min(.limited(remaining_len)).slice(out)};
382 const n = try in.readVec(&limited_out);
383 if (remaining_len - n == 0) {
384 d.state = if (d.final_block) .protocol_footer else .block_header;
385 } else {
386 d.state = .{ .stored_block = @intCast(remaining_len - n) };
387 }
388 w.advance(n);
389 return @backingInt(limit) - remaining + n;
390 },
391 .fixed_block => while (true) {
392 // Consume bytes
393 const sym = try d.readFixedCode();
394
395 if (sym >= 256) {
396 @branchHint(.unlikely);
397
398 if (sym == 256) {
399 @branchHint(.unlikely);
400 // End
401 d.state = if (d.final_block) .protocol_footer else .block_header;
402 continue :sw d.state;
403 }
404
405 // Match
406 const length = try d.decodeLength(@intCast(sym - 257));
407 const distance = try d.decodeDistance(@bitReverse(try d.takeIntBits(u5)));
408 continue :sw .{ .fixed_block_match = .{ .length = length, .distance = distance } };
409 }
410
411 const byte: u8 = @intCast(sym);
412 if (remaining != 0) {
413 @branchHint(.likely);
414 remaining -= 1;
415 try w.writeBytePreserve(flate.history_len, byte);
416 } else {
417 d.state = .{ .fixed_block_literal = byte };
418 return @backingInt(limit) - remaining;
419 }
420 },
421 .fixed_block_literal => |symbol| {
422 assert(remaining != 0);
423 remaining -= 1;
424 try w.writeBytePreserve(flate.history_len, symbol);
425 continue :sw .fixed_block;
426 },
427 .fixed_block_match => |match| {
428 if (remaining >= match.length) {
429 @branchHint(.likely);
430 try writeMatch(w, match.length, match.distance);
431 remaining -= match.length;
432 continue :sw .fixed_block;
433 } else {
434 if (remaining > 0) {
435 try writeMatch(w, @intCast(remaining), match.distance);
436 }
437 d.state = .{ .fixed_block_match = .{
438 .distance = match.distance,
439 .length = match.length - @as(u16, @intCast(remaining)),
440 } };
441 return @backingInt(limit);
442 }
443 },
444 // In larger archives most blocks are usually dynamic, so
445 // decompression performance depends on this logic.
446 .dynamic_block => while (true) {
447 // Consume bytes
448 const sym = try d.decodeSymbol(&d.lit_dec);
449
450 if (sym >= 256) {
451 @branchHint(.unlikely);
452
453 if (sym == 256) {
454 @branchHint(.unlikely);
455 // End
456 d.state = if (d.final_block) .protocol_footer else .block_header;
457 continue :sw d.state;
458 }
459
460 // Match
461 const length = try d.decodeLength(@intCast(sym - 257));
462 const dsm = try d.decodeSymbol(&d.dst_dec);
463 const distance = try d.decodeDistance(@intCast(dsm));
464 continue :sw .{ .dynamic_block_match = .{ .length = length, .distance = distance } };
465 }
466
467 const byte: u8 = @intCast(sym);
468 if (remaining != 0) {
469 @branchHint(.likely);
470 remaining -= 1;
471 try w.writeBytePreserve(flate.history_len, byte);
472 } else {
473 d.state = .{ .dynamic_block_literal = byte };
474 return @backingInt(limit) - remaining;
475 }
476 },
477 .dynamic_block_literal => |symbol| {
478 assert(remaining != 0);
479 remaining -= 1;
480 try w.writeBytePreserve(flate.history_len, symbol);
481 continue :sw .dynamic_block;
482 },
483 .dynamic_block_match => |match| {
484 if (remaining >= match.length) {
485 @branchHint(.likely);
486 remaining -= match.length;
487 try writeMatch(w, match.length, match.distance);
488 continue :sw .dynamic_block;
489 } else {
490 if (remaining > 0) {
491 try writeMatch(w, @intCast(remaining), match.distance);
492 }
493 d.state = .{ .dynamic_block_match = .{
494 .distance = match.distance,
495 .length = match.length - @as(u16, @intCast(remaining)),
496 } };
497 return @backingInt(limit);
498 }
499 },
500 .protocol_footer => {
501 d.alignBitsForward();
502 switch (d.container_metadata) {
503 .gzip => |*gzip| {
504 gzip.crc = try in.takeInt(u32, .little);
505 gzip.count = try in.takeInt(u32, .little);
506 },
507 .zlib => |*zlib| {
508 zlib.adler = try in.takeInt(u32, .big);
509 },
510 .raw => {},
511 }
512 d.state = .end;
513 return @backingInt(limit) - remaining;
514 },
515 .end => return error.EndOfStream,
516 }
517}
518
519/// Write match (back-reference to the same data slice) starting at `distance`
520/// back from current write position, and `length` of bytes.
521/// `length` may be less than the minimum match length to allow for writing
522/// partial matches, but must be greater than zero.
523fn writeMatch(w: *Writer, length: u16, distance: u16) !void {
524 if (w.end < distance) return error.InvalidMatch;
525 assert(length > 0);
526 assert(length <= token.max_length);
527 assert(distance >= token.min_distance);
528 assert(distance <= token.max_distance);
529
530 // This is not a @memmove; it intentionally repeats patterns caused by
531 // iterating one byte at a time.
532 const dest = try w.writableSlicePreserve(flate.history_len, length);
533 const end = dest.ptr - w.buffer.ptr;
534 const src = w.buffer[end - distance ..][0..length];
535 if (distance >= length) {
536 @memcpy(dest, src);
537 } else if (distance == 1) {
538 // Repeating copy of single byte
539 @memset(dest, src[0]);
540 } else {
541 // Repeating copy of multiple bytes
542 for (dest, src) |*d, s| d.* = s;
543 }
544}
545
546fn peekBits(d: *Decompress, n: u4) !u16 {
547 const bits = d.input.peekInt(u32, .little) catch |e| return switch (e) {
548 error.ReadFailed => error.ReadFailed,
549 error.EndOfStream => d.peekBitsEnding(n),
550 };
551 const mask = @shlExact(@as(u16, 1), n) - 1;
552 return @intCast((bits >> d.consumed_bits) & mask);
553}
554
555fn peekBitsEnding(d: *Decompress, n: u4) !u16 {
556 @branchHint(.unlikely);
557
558 const left = d.input.buffered();
559 if (left.len * 8 - d.consumed_bits < n) return error.EndOfStream;
560 const bits = std.mem.readVarInt(u32, left, .little);
561 const mask = @shlExact(@as(u16, 1), n) - 1;
562 return @intCast((bits >> d.consumed_bits) & mask);
563}
564
565/// Safe only after `peekBits` has been called with a greater or equal `n` value.
566fn tossBits(d: *Decompress, n: u4) void {
567 d.input.toss((@as(u8, n) + d.consumed_bits) / 8);
568 d.consumed_bits +%= @truncate(n);
569}
570
571fn takeBits(d: *Decompress, n: u4) !u16 {
572 const bits = try d.peekBits(n);
573 d.tossBits(n);
574 return bits;
575}
576
577fn alignBitsForward(d: *Decompress) void {
578 d.input.toss(@intFromBool(d.consumed_bits != 0));
579 d.consumed_bits = 0;
580}
581
582fn peekBitsShort(d: *Decompress, n: u4) !u16 {
583 const bits = d.input.peekInt(u32, .little) catch |e| return switch (e) {
584 error.ReadFailed => error.ReadFailed,
585 error.EndOfStream => d.peekBitsShortEnding(n),
586 };
587 const mask = @shlExact(@as(u16, 1), n) - 1;
588 return @intCast((bits >> d.consumed_bits) & mask);
589}
590
591fn peekBitsShortEnding(d: *Decompress, n: u4) !u16 {
592 @branchHint(.unlikely);
593
594 const left = d.input.buffered();
595 const bits = std.mem.readVarInt(u32, left, .little);
596 const mask = @shlExact(@as(u16, 1), n) - 1;
597 return @intCast((bits >> d.consumed_bits) & mask);
598}
599
600fn tossBitsShort(d: *Decompress, n: u4) !void {
601 if (d.input.bufferedLen() * 8 - d.consumed_bits < n) return error.EndOfStream;
602 d.tossBits(n);
603}
604
605fn takeIntBits(d: *Decompress, T: type) !T {
606 return @intCast(try d.takeBits(@bitSizeOf(T)));
607}
608
609fn peekIntBitsShort(d: *Decompress, T: type) !T {
610 return @intCast(try d.peekBitsShort(@bitSizeOf(T)));
611}
612
613/// Reads first 7 bits, and then maybe 1 or 2 more to get full 7,8 or 9 bit code.
614/// ref: https://datatracker.ietf.org/doc/html/rfc1951#page-12
615/// Lit Value Bits Codes
616/// --------- ---- -----
617/// 0 - 143 8 00110000 through
618/// 10111111
619/// 144 - 255 9 110010000 through
620/// 111111111
621/// 256 - 279 7 0000000 through
622/// 0010111
623/// 280 - 287 8 11000000 through
624/// 11000111
625fn readFixedCode(d: *Decompress) !u16 {
626 const code7 = @bitReverse(try d.takeIntBits(u7));
627 return switch (code7) {
628 0...0b0010_111 => @as(u16, code7) + 256,
629 0b0010_111 + 1...0b1011_111 => (@as(u16, code7) << 1) + @as(u16, try d.takeIntBits(u1)) - 0b0011_0000,
630 0b1011_111 + 1...0b1100_011 => (@as(u16, code7 - 0b1100000) << 1) + try d.takeIntBits(u1) + 280,
631 else => (@as(u16, code7 - 0b1100_100) << 2) + @as(u16, @bitReverse(try d.takeIntBits(u2))) + 144,
632 };
633}
634
635pub const Symbol = packed struct(u16) {
636 value: u12 = 0,
637 code_bits: u4 = 0, // number of bits in code 0-15
638};
639
640pub const LiteralDecoder = HuffmanDecoder(286, 15, 9);
641pub const DistanceDecoder = HuffmanDecoder(30, 15, 9);
642pub const CodegenDecoder = HuffmanDecoder(19, 7, 7);
643
644/// Creates huffman tree codes from list of code lengths (in `build`).
645///
646/// `find` then finds symbol for code bits. Code can be any length between 1 and
647/// 15 bits. When calling `find` we don't know how many bits will be used to
648/// find symbol. When symbol is returned it has code_bits field which defines
649/// how much we should advance in bit stream.
650///
651/// Lookup table is used to map 15 bit int to symbol. Same symbol is written
652/// many times in this table; 32K places for 286 (at most) symbols.
653/// Small lookup table is optimization for faster search.
654/// It is variation of the algorithm explained in [zlib](https://github.com/madler/zlib/blob/643e17b7498d12ab8d15565662880579692f769d/doc/algorithm.txt#L92)
655/// with difference that we here use statically allocated arrays.
656fn HuffmanDecoder(
657 comptime alphabet_size: u16,
658 comptime max_code_bits: u4,
659 comptime lookup_bits: u4,
660) type {
661 const lookup_shift = max_code_bits - lookup_bits;
662 const lookup_mask = (1 << lookup_bits) - 1;
663
664 return struct {
665 // lookup table code -> symbol
666 // for values with code_bits == 0, symbol is the index of the first node in linked
667 // if the index of the first node is 0xfff, it is an invalid code
668 lookup: [1 << lookup_bits]Symbol = undefined,
669 linked: if (lookup_bits == max_code_bits) void else [alphabet_size]struct {
670 // sym.value is the next index in linked where the current index ends the chain
671 // the actual symbol is this nodes's index
672 sym: Symbol,
673 code: u16,
674 } = undefined,
675
676 const Self = @This();
677
678 fn reverseIdx(idx: usize) u16 {
679 return @bitReverse(@as(@Int(.unsigned, lookup_bits), @intCast(idx)));
680 }
681
682 /// Generates symbols and lookup tables from list of code lens for each symbol.
683 pub fn generate(self: *Self, lens: []const u4) !void {
684 try checkCompleteness(lens);
685
686 var buckets: [1 + @as(usize, max_code_bits)][alphabet_size]Symbol = undefined;
687 var bucket_len: [buckets.len]u16 = @splat(0);
688 for (0.., lens) |symbol, bits| {
689 buckets[bits][bucket_len[bits]] = .{
690 .value = @intCast(symbol),
691 .code_bits = bits,
692 };
693 bucket_len[bits] += 1;
694 }
695
696 var code: u16 = 0;
697 var idx: u16 = 0;
698 for (1..lookup_bits + 1) |bits| {
699 const inc = @as(u16, 1) << @intCast(max_code_bits - bits);
700 for (buckets[bits][0..bucket_len[bits]]) |lookup_sym| {
701 const next_code = code + inc;
702 const next_idx = next_code >> lookup_shift;
703 for (idx..next_idx) |i| {
704 self.lookup[reverseIdx(i)] = lookup_sym;
705 }
706 code = next_code;
707 idx = next_idx;
708 }
709 }
710 for (lookup_bits + 1..buckets.len) |bits| {
711 const inc = @as(u16, 1) << @intCast(max_code_bits - bits);
712 for (buckets[bits][0..bucket_len[bits]]) |linked_sym| {
713 const next_code = code + inc;
714 const next_idx = next_code >> lookup_shift;
715
716 const ri = reverseIdx(idx);
717 const next: Symbol = .{
718 .value = self.lookup[ri].value,
719 .code_bits = linked_sym.code_bits,
720 };
721 self.linked[linked_sym.value] = .{
722 .sym = next,
723 .code = @bitReverse(@as(@Int(.unsigned, max_code_bits), @intCast(code))),
724 };
725 self.lookup[ri] = .{ .value = linked_sym.value, .code_bits = 0 };
726
727 code = next_code;
728 idx = next_idx;
729 }
730 }
731
732 // Invalid codes
733 for (idx..self.lookup.len) |i| {
734 self.lookup[reverseIdx(i)] = .{ .value = 0xfff, .code_bits = 0 };
735 }
736 }
737
738 /// Given the list of code lengths check that it represents a canonical
739 /// Huffman code for n symbols.
740 ///
741 /// Reference: https://github.com/madler/zlib/blob/5c42a230b7b468dff011f444161c0145b5efae59/contrib/puff/puff.c#L340
742 fn checkCompleteness(lens: []const u4) !void {
743 if (alphabet_size == 286)
744 if (lens[256] == 0) return error.MissingEndOfBlockCode;
745
746 var count: [@as(usize, max_code_bits) + 1]u16 = @splat(0);
747 var max: usize = 0;
748 for (lens) |n| {
749 if (n == 0) continue;
750 if (n > max) max = n;
751 count[n] += 1;
752 }
753 if (max == 0) // empty tree
754 return;
755
756 // check for an over-subscribed or incomplete set of lengths
757 var left: usize = 1; // one possible code of zero length
758 for (1..count.len) |len| {
759 left <<= 1; // one more bit, double codes left
760 if (count[len] > left)
761 return error.OversubscribedHuffmanTree;
762 left -= count[len]; // deduct count from possible codes
763 }
764 if (left > 0) { // left > 0 means incomplete
765 // incomplete code ok only for single length 1 code
766 if (max_code_bits > 7 and max == count[0] + count[1]) return;
767 return error.IncompleteHuffmanTree;
768 }
769 }
770
771 /// Finds symbol for lookup table code.
772 pub fn find(self: *Self, code: u16) !Symbol {
773 // try to find in lookup table
774 const idx = code & lookup_mask;
775 const sym = self.lookup[idx];
776 if (sym.code_bits != 0) return sym;
777 // if not use linked list of symbols with same prefix
778 return self.findLinked(code, sym.value);
779 }
780
781 fn findLinked(self: *Self, code: u16, start: u16) !Symbol {
782 if (start == 0xfff) return error.InvalidCode;
783 if (lookup_bits == max_code_bits) unreachable;
784 var pos = start;
785 while (true) {
786 const node = self.linked[pos];
787 const shift = -%node.sym.code_bits;
788 // compare code_bits number of upper bits
789 if ((code ^ node.code) << shift == 0)
790 return .{ .value = @intCast(pos), .code_bits = node.sym.code_bits };
791 pos = node.sym.value;
792 }
793 }
794 };
795}
796
797test "init/find" {
798 // example data from: https://youtu.be/SJPvNi4HrWQ?t=8423
799 const code_lens = [_]u4{ 4, 3, 0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 3, 2 };
800 var h: CodegenDecoder = .{};
801 try h.generate(&code_lens);
802
803 // All possible codes for each symbol.
804 // Lookup table has 126 elements, to cover all possible 7 bit codes.
805 for (0b0000_000..0b0100_000) |c| // 0..32 (32)
806 try testing.expectEqual(
807 Symbol{ .value = 3, .code_bits = 2 },
808 try h.find(@bitReverse(@as(u7, @intCast(c)))),
809 );
810
811 for (0b0100_000..0b1000_000) |c| // 32..64 (32)
812 try testing.expectEqual(
813 Symbol{ .value = 18, .code_bits = 2 },
814 try h.find(@bitReverse(@as(u7, @intCast(c)))),
815 );
816
817 for (0b1000_000..0b1010_000) |c| // 64..80 (16)
818 try testing.expectEqual(
819 Symbol{ .value = 1, .code_bits = 3 },
820 try h.find(@bitReverse(@as(u7, @intCast(c)))),
821 );
822
823 for (0b1010_000..0b1100_000) |c| // 80..96 (16)
824 try testing.expectEqual(
825 Symbol{ .value = 4, .code_bits = 3 },
826 try h.find(@bitReverse(@as(u7, @intCast(c)))),
827 );
828
829 for (0b1100_000..0b1110_000) |c| // 96..112 (16)
830 try testing.expectEqual(
831 Symbol{ .value = 17, .code_bits = 3 },
832 try h.find(@bitReverse(@as(u7, @intCast(c)))),
833 );
834
835 for (0b1110_000..0b1111_000) |c| // 112..120 (8)
836 try testing.expectEqual(
837 Symbol{ .value = 0, .code_bits = 4 },
838 try h.find(@bitReverse(@as(u7, @intCast(c)))),
839 );
840
841 for (0b1111_000..0b1_0000_000) |c| // 120...128 (8)
842 try testing.expectEqual(
843 Symbol{ .value = 16, .code_bits = 4 },
844 try h.find(@bitReverse(@as(u7, @intCast(c)))),
845 );
846}
847
848test "encode/decode literals" {
849 // Check that the example in RFC 1951 section 3.2.2 works (plus some zeroes)
850 const max_bits = 5;
851 var decoder: HuffmanDecoder(16, max_bits, 3) = .{};
852 try decoder.generate(&.{ 3, 3, 3, 3, 0, 0, 3, 2, 4, 4 });
853
854 inline for (0.., .{
855 @as(u3, 0b010),
856 @as(u3, 0b011),
857 @as(u3, 0b100),
858 @as(u3, 0b101),
859 @as(u0, 0),
860 @as(u0, 0),
861 @as(u3, 0b110),
862 @as(u2, 0b00),
863 @as(u4, 0b1110),
864 @as(u4, 0b1111),
865 }) |i, code| {
866 const bits = @bitSizeOf(@TypeOf(code));
867 if (bits == 0) continue;
868 for (0..1 << (max_bits - bits)) |extra| {
869 const full = (@as(u16, code) << (max_bits - bits)) | @as(u16, @intCast(extra));
870 const symbol = try decoder.find(@bitReverse(@as(u5, @intCast(full))));
871 try testing.expectEqual(i, symbol.value);
872 try testing.expectEqual(bits, symbol.code_bits);
873 }
874 }
875}
876
877test "non compressed block (type 0)" {
878 try testDecompress(.raw, &[_]u8{
879 0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate fixed buffer header len, nlen
880 'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // non compressed data
881 }, "Hello world\n");
882}
883
884test "fixed code block (type 1)" {
885 try testDecompress(.raw, &[_]u8{
886 0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0x28, 0xcf, // deflate data block type 1
887 0x2f, 0xca, 0x49, 0xe1, 0x02, 0x00,
888 }, "Hello world\n");
889}
890
891test "dynamic block (type 2)" {
892 try testDecompress(.raw, &[_]u8{
893 0x3d, 0xc6, 0x39, 0x11, 0x00, 0x00, 0x0c, 0x02, // deflate data block type 2
894 0x30, 0x2b, 0xb5, 0x52, 0x1e, 0xff, 0x96, 0x38,
895 0x16, 0x96, 0x5c, 0x1e, 0x94, 0xcb, 0x6d, 0x01,
896 }, "ABCDEABCD ABCDEABCD");
897}
898
899test "gzip non compressed block (type 0)" {
900 try testDecompress(.gzip, &[_]u8{
901 0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, // gzip header (10 bytes)
902 0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate fixed buffer header len, nlen
903 'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // non compressed data
904 0xd5, 0xe0, 0x39, 0xb7, // gzip footer: checksum
905 0x0c, 0x00, 0x00, 0x00, // gzip footer: size
906 }, "Hello world\n");
907}
908
909test "gzip fixed code block (type 1)" {
910 try testDecompress(.gzip, &[_]u8{
911 0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x03, // gzip header (10 bytes)
912 0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0x28, 0xcf, // deflate data block type 1
913 0x2f, 0xca, 0x49, 0xe1, 0x02, 0x00,
914 0xd5, 0xe0, 0x39, 0xb7, 0x0c, 0x00, 0x00, 0x00, // gzip footer (chksum, len)
915 }, "Hello world\n");
916}
917
918test "gzip dynamic block (type 2)" {
919 try testDecompress(.gzip, &[_]u8{
920 0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03, // gzip header (10 bytes)
921 0x3d, 0xc6, 0x39, 0x11, 0x00, 0x00, 0x0c, 0x02, // deflate data block type 2
922 0x30, 0x2b, 0xb5, 0x52, 0x1e, 0xff, 0x96, 0x38,
923 0x16, 0x96, 0x5c, 0x1e, 0x94, 0xcb, 0x6d, 0x01,
924 0x17, 0x1c, 0x39, 0xb4, 0x13, 0x00, 0x00, 0x00, // gzip footer (chksum, len)
925 }, "ABCDEABCD ABCDEABCD");
926}
927
928test "gzip header with name" {
929 try testDecompress(.gzip, &[_]u8{
930 0x1f, 0x8b, 0x08, 0x08, 0xe5, 0x70, 0xb1, 0x65, 0x00, 0x03, 0x68, 0x65, 0x6c, 0x6c, 0x6f, 0x2e,
931 0x74, 0x78, 0x74, 0x00, 0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0x28, 0xcf, 0x2f, 0xca, 0x49, 0xe1,
932 0x02, 0x00, 0xd5, 0xe0, 0x39, 0xb7, 0x0c, 0x00, 0x00, 0x00,
933 }, "Hello world\n");
934}
935
936test "zlib decompress non compressed block (type 0)" {
937 try testDecompress(.zlib, &[_]u8{
938 0x78, 0b10_0_11100, // zlib header (2 bytes)
939 0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate fixed buffer header len, nlen
940 'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // non compressed data
941 0x1c, 0xf2, 0x04, 0x47, // zlib footer: checksum
942 }, "Hello world\n");
943}
944
945test "failing end-of-stream" {
946 try testFailure(.raw, @embedFile("testdata/fuzz/end-of-stream.input"), error.EndOfStream);
947}
948test "failing invalid-distance" {
949 try testFailure(.raw, @embedFile("testdata/fuzz/invalid-distance.input"), error.InvalidMatch);
950}
951test "failing invalid-tree01" {
952 try testFailure(.raw, @embedFile("testdata/fuzz/invalid-tree01.input"), error.IncompleteHuffmanTree);
953}
954test "failing invalid-tree02" {
955 try testFailure(.raw, @embedFile("testdata/fuzz/invalid-tree02.input"), error.IncompleteHuffmanTree);
956}
957test "failing invalid-tree03" {
958 try testFailure(.raw, @embedFile("testdata/fuzz/invalid-tree03.input"), error.IncompleteHuffmanTree);
959}
960test "failing lengths-overflow" {
961 try testFailure(.raw, @embedFile("testdata/fuzz/lengths-overflow.input"), error.InvalidDynamicBlockHeader);
962}
963test "failing out-of-codes" {
964 try testFailure(.raw, @embedFile("testdata/fuzz/out-of-codes.input"), error.InvalidCode);
965}
966test "failing puff01" {
967 try testFailure(.raw, @embedFile("testdata/fuzz/puff01.input"), error.WrongStoredBlockNlen);
968}
969test "failing puff02" {
970 try testFailure(.raw, @embedFile("testdata/fuzz/puff02.input"), error.EndOfStream);
971}
972test "failing puff04" {
973 try testFailure(.raw, @embedFile("testdata/fuzz/puff04.input"), error.InvalidCode);
974}
975test "failing puff05" {
976 try testFailure(.raw, @embedFile("testdata/fuzz/puff05.input"), error.EndOfStream);
977}
978test "failing puff06" {
979 try testFailure(.raw, @embedFile("testdata/fuzz/puff06.input"), error.EndOfStream);
980}
981test "failing puff08" {
982 try testFailure(.raw, @embedFile("testdata/fuzz/puff08.input"), error.InvalidCode);
983}
984test "failing puff10" {
985 try testFailure(.raw, @embedFile("testdata/fuzz/puff10.input"), error.InvalidCode);
986}
987test "failing puff11" {
988 try testFailure(.raw, @embedFile("testdata/fuzz/puff11.input"), error.InvalidMatch);
989}
990test "failing puff12" {
991 try testFailure(.raw, @embedFile("testdata/fuzz/puff12.input"), error.InvalidDynamicBlockHeader);
992}
993test "failing puff13" {
994 try testFailure(.raw, @embedFile("testdata/fuzz/puff13.input"), error.IncompleteHuffmanTree);
995}
996test "failing puff14" {
997 try testFailure(.raw, @embedFile("testdata/fuzz/puff14.input"), error.EndOfStream);
998}
999test "failing puff15" {
1000 try testFailure(.raw, @embedFile("testdata/fuzz/puff15.input"), error.IncompleteHuffmanTree);
1001}
1002test "failing puff16" {
1003 try testFailure(.raw, @embedFile("testdata/fuzz/puff16.input"), error.InvalidDynamicBlockHeader);
1004}
1005test "failing puff17" {
1006 try testFailure(.raw, @embedFile("testdata/fuzz/puff17.input"), error.MissingEndOfBlockCode);
1007}
1008test "failing fuzz1" {
1009 try testFailure(.raw, @embedFile("testdata/fuzz/fuzz1.input"), error.InvalidDynamicBlockHeader);
1010}
1011test "failing fuzz2" {
1012 try testFailure(.raw, @embedFile("testdata/fuzz/fuzz2.input"), error.InvalidDynamicBlockHeader);
1013}
1014test "failing fuzz3" {
1015 try testFailure(.raw, @embedFile("testdata/fuzz/fuzz3.input"), error.InvalidMatch);
1016}
1017test "failing fuzz4" {
1018 try testFailure(.raw, @embedFile("testdata/fuzz/fuzz4.input"), error.OversubscribedHuffmanTree);
1019}
1020test "failing puff18" {
1021 try testFailure(.raw, @embedFile("testdata/fuzz/puff18.input"), error.OversubscribedHuffmanTree);
1022}
1023test "failing puff19" {
1024 try testFailure(.raw, @embedFile("testdata/fuzz/puff19.input"), error.OversubscribedHuffmanTree);
1025}
1026test "failing puff20" {
1027 try testFailure(.raw, @embedFile("testdata/fuzz/puff20.input"), error.OversubscribedHuffmanTree);
1028}
1029test "failing puff21" {
1030 try testFailure(.raw, @embedFile("testdata/fuzz/puff21.input"), error.OversubscribedHuffmanTree);
1031}
1032test "failing puff22" {
1033 try testFailure(.raw, @embedFile("testdata/fuzz/puff22.input"), error.OversubscribedHuffmanTree);
1034}
1035test "failing puff23" {
1036 try testFailure(.raw, @embedFile("testdata/fuzz/puff23.input"), error.OversubscribedHuffmanTree);
1037}
1038test "failing puff24" {
1039 try testFailure(.raw, @embedFile("testdata/fuzz/puff24.input"), error.IncompleteHuffmanTree);
1040}
1041test "failing puff25" {
1042 try testFailure(.raw, @embedFile("testdata/fuzz/puff25.input"), error.OversubscribedHuffmanTree);
1043}
1044test "failing puff26" {
1045 try testFailure(.raw, @embedFile("testdata/fuzz/puff26.input"), error.InvalidDynamicBlockHeader);
1046}
1047test "failing puff27" {
1048 try testFailure(.raw, @embedFile("testdata/fuzz/puff27.input"), error.InvalidDynamicBlockHeader);
1049}
1050
1051test "deflate-stream" {
1052 try testDecompress(
1053 .raw,
1054 @embedFile("testdata/fuzz/deflate-stream.input"),
1055 @embedFile("testdata/fuzz/deflate-stream.expect"),
1056 );
1057}
1058
1059test "empty-distance-alphabet01" {
1060 try testDecompress(.raw, @embedFile("testdata/fuzz/empty-distance-alphabet01.input"), "");
1061}
1062
1063test "empty-distance-alphabet02" {
1064 try testDecompress(.raw, @embedFile("testdata/fuzz/empty-distance-alphabet02.input"), "");
1065}
1066
1067test "puff03" {
1068 try testDecompress(.raw, @embedFile("testdata/fuzz/puff03.input"), &.{0xa});
1069}
1070
1071test "puff09" {
1072 try testDecompress(.raw, @embedFile("testdata/fuzz/puff09.input"), "P");
1073}
1074
1075test "invalid block type" {
1076 try testFailure(.raw, &[_]u8{0b110}, error.InvalidBlockType);
1077}
1078
1079test "bug 18966" {
1080 try testDecompress(
1081 .gzip,
1082 @embedFile("testdata/fuzz/bug_18966.input"),
1083 @embedFile("testdata/fuzz/bug_18966.expect"),
1084 );
1085}
1086
1087test "truncated input ending when reading dynamic length bits" {
1088 try testFailure(.raw, &[_]u8{
1089 0x15, 0xd5, 0x07, 0x3b, 0x16, 0x0c, 0x03, 0x86,
1090 0x61, 0x2b, 0xa3, 0xec, 0xec, 0x15, 0x95, 0x6c,
1091 0x92, 0x4d, 0x19, 0x95, 0x4a, 0xb6, 0x22, 0x23,
1092 0xc9,
1093 }, error.EndOfStream);
1094}
1095
1096test "reading into empty buffer" {
1097 // Inspired by https://github.com/ziglang/zig/issues/19895
1098 const input = &[_]u8{
1099 0b0000_0001, 0b0000_1100, 0x00, 0b1111_0011, 0xff, // deflate fixed buffer header len, nlen
1100 'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd', 0x0a, // non compressed data
1101 };
1102 var in: Reader = .fixed(input);
1103 var decomp: Decompress = .init(&in, .raw, &.{});
1104 const r = &decomp.reader;
1105 var bufs: [1][]u8 = .{&.{}};
1106 try testing.expectEqual(0, try r.readVec(&bufs));
1107}
1108
1109test "zlib header" {
1110 // Truncated header
1111 try testFailure(.zlib, &[_]u8{0x78}, error.EndOfStream);
1112
1113 // Wrong CM
1114 try testFailure(.zlib, &[_]u8{ 0x79, 0x94 }, error.BadZlibHeader);
1115
1116 // Wrong CINFO
1117 try testFailure(.zlib, &[_]u8{ 0x88, 0x98 }, error.BadZlibHeader);
1118
1119 // Truncated checksum
1120 try testFailure(.zlib, &[_]u8{ 0x78, 0xda, 0x03, 0x00, 0x00 }, error.EndOfStream);
1121}
1122
1123test "gzip header" {
1124 // Truncated header
1125 try testFailure(.gzip, &[_]u8{ 0x1f, 0x8B }, error.EndOfStream);
1126
1127 // Wrong CM
1128 try testFailure(.gzip, &[_]u8{
1129 0x1f, 0x8b, 0x09, 0x00, 0x00, 0x00, 0x00, 0x00,
1130 0x00, 0x03,
1131 }, error.BadGzipHeader);
1132
1133 // Truncated checksum
1134 try testFailure(.gzip, &[_]u8{
1135 0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00,
1136 0x00, 0x03, 0x03, 0x00, 0x00, 0x00, 0x00,
1137 }, error.EndOfStream);
1138
1139 // Truncated initial size field
1140 try testFailure(.gzip, &[_]u8{
1141 0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00,
1142 0x00, 0x03, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00,
1143 0x00, 0x00, 0x00,
1144 }, error.EndOfStream);
1145
1146 try testDecompress(.gzip, &[_]u8{
1147 // GZIP header
1148 0x1f, 0x8b, 0x08, 0x12, 0x00, 0x09, 0x6e, 0x88, 0x00, 0xff, 0x48, 0x65, 0x6c, 0x6c, 0x6f, 0x00,
1149 // header.FHCRC (should cover entire header)
1150 0x99, 0xd6,
1151 // GZIP data
1152 0x01, 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1153 }, "");
1154}
1155
1156test "zlib should not overshoot" {
1157 // Compressed zlib data with extra 4 bytes at the end.
1158 const data = [_]u8{
1159 0x78, 0x9c, 0x73, 0xce, 0x2f, 0xa8, 0x2c, 0xca, 0x4c, 0xcf, 0x28, 0x51, 0x08, 0xcf, 0xcc, 0xc9,
1160 0x49, 0xcd, 0x55, 0x28, 0x4b, 0xcc, 0x53, 0x08, 0x4e, 0xce, 0x48, 0xcc, 0xcc, 0xd6, 0x51, 0x08,
1161 0xce, 0xcc, 0x4b, 0x4f, 0x2c, 0xc8, 0x2f, 0x4a, 0x55, 0x30, 0xb4, 0xb4, 0x34, 0xd5, 0xb5, 0x34,
1162 0x03, 0x00, 0x8b, 0x61, 0x0f, 0xa4, 0x52, 0x5a, 0x94, 0x12,
1163 };
1164
1165 var reader: std.Io.Reader = .fixed(&data);
1166
1167 var decompress_buffer: [flate.max_window_len]u8 = undefined;
1168 var decompress: Decompress = .init(&reader, .zlib, &decompress_buffer);
1169 var out: [128]u8 = undefined;
1170
1171 {
1172 const n = try decompress.reader.readSliceShort(&out);
1173 try std.testing.expectEqual(46, n);
1174 try std.testing.expectEqualStrings("Copyright Willem van Schaik, Singapore 1995-96", out[0..n]);
1175 }
1176
1177 // 4 bytes after compressed chunk are available in reader.
1178 const n = try reader.readSliceShort(&out);
1179 try std.testing.expectEqual(n, 4);
1180 try std.testing.expectEqualSlices(u8, data[data.len - 4 .. data.len], out[0..n]);
1181}
1182
1183fn testFailure(container: Container, in: []const u8, expected_err: anyerror) !void {
1184 var reader: Reader = .fixed(in);
1185 var aw: Writer.Allocating = .init(testing.allocator);
1186 defer aw.deinit();
1187
1188 var decompress: Decompress = .init(&reader, container, &.{});
1189 try testing.expectError(error.ReadFailed, decompress.reader.streamRemaining(&aw.writer));
1190 try testing.expectEqual(expected_err, decompress.err orelse return error.TestFailed);
1191}
1192
1193fn testDecompress(container: Container, compressed: []const u8, expected_plain: []const u8) !void {
1194 var aw: std.Io.Writer.Allocating = .init(testing.allocator);
1195 defer aw.deinit();
1196
1197 // Decompress once using the normal methods.
1198 {
1199 var in: std.Io.Reader = .fixed(compressed);
1200 var decompress: Decompress = .init(&in, container, &.{});
1201 const decompressed_len = try decompress.reader.streamRemaining(&aw.writer);
1202 try testing.expectEqual(expected_plain.len, decompressed_len);
1203 try testing.expectEqualSlices(u8, expected_plain, aw.written());
1204 }
1205
1206 // Decompress again by streaming one byte at a time to check that there aren't
1207 // any problems with things like writing partial matches, etc.
1208 aw.clearRetainingCapacity();
1209 {
1210 var in: std.Io.Reader = .fixed(compressed);
1211 var decompress: Decompress = .init(&in, container, &.{});
1212 var decompressed_len: usize = 0;
1213 while (true) {
1214 decompressed_len += decompress.reader.stream(&aw.writer, .limited(1)) catch |err| switch (err) {
1215 error.EndOfStream => break,
1216 else => |e| return e,
1217 };
1218 }
1219 try testing.expectEqual(expected_plain.len, decompressed_len);
1220 try testing.expectEqualSlices(u8, expected_plain, aw.written());
1221 }
1222}