Commit 2328f40b7a
Changed files (8)
lib/std/compress/deflate.zig
@@ -0,0 +1,521 @@
+// SPDX-License-Identifier: MIT
+// Copyright (c) 2015-2020 Zig Contributors
+// This file is part of [zig](https://ziglang.org/), which is MIT licensed.
+// The MIT license requires this copyright notice to be included in all copies
+// and substantial portions of the software.
+//
+// Decompressor for DEFLATE data streams (RFC1951)
+//
+// Heavily inspired by the simple decompressor puff.c by Mark Adler
+
+const std = @import("std");
+const io = std.io;
+const math = std.math;
+const mem = std.mem;
+
+const assert = std.debug.assert;
+
+const MAXBITS = 15;
+const MAXLCODES = 286;
+const MAXDCODES = 30;
+const MAXCODES = MAXLCODES + MAXDCODES;
+const FIXLCODES = 288;
+
+const Huffman = struct {
+ count: [MAXBITS + 1]u16,
+ symbol: [MAXCODES]u16,
+
+ fn construct(self: *Huffman, length: []const u16) !void {
+ for (self.count) |*val| {
+ val.* = 0;
+ }
+
+ for (length) |val| {
+ self.count[val] += 1;
+ }
+
+ if (self.count[0] == length.len)
+ return;
+
+ var left: isize = 1;
+ for (self.count[1..]) |val| {
+ left *= 2;
+ left -= @as(isize, @bitCast(i16, val));
+ if (left < 0)
+ return error.InvalidTree;
+ }
+
+ var offs: [MAXBITS + 1]u16 = undefined;
+ {
+ var len: usize = 1;
+ offs[1] = 0;
+ while (len < MAXBITS) : (len += 1) {
+ offs[len + 1] = offs[len] + self.count[len];
+ }
+ }
+
+ for (length) |val, symbol| {
+ if (val != 0) {
+ self.symbol[offs[val]] = @truncate(u16, symbol);
+ offs[val] += 1;
+ }
+ }
+ }
+};
+
+pub fn InflateStream(comptime ReaderType: type) type {
+ return struct {
+ const Self = @This();
+
+ pub const Error = ReaderType.Error || error{
+ EndOfStream,
+ BadCounts,
+ InvalidBlockType,
+ InvalidDistance,
+ InvalidFixedCode,
+ InvalidLength,
+ InvalidStoredSize,
+ InvalidSymbol,
+ InvalidTree,
+ MissingEOBCode,
+ NoLastLength,
+ OutOfCodes,
+ };
+ pub const Reader = io.Reader(*Self, Error, read);
+
+ bit_reader: io.BitReader(.Little, ReaderType),
+
+ // True if the decoder met the end of the compressed stream, no further
+ // data can be decompressed
+ seen_eos: bool,
+
+ state: union(enum) {
+ // Parse a compressed block header and set up the internal state for
+ // decompressing its contents.
+ DecodeBlockHeader: void,
+ // Decode all the symbols in a compressed block.
+ DecodeBlockData: void,
+ // Copy N bytes of uncompressed data from the underlying stream into
+ // the window.
+ Copy: usize,
+ // Copy 1 byte into the window.
+ CopyLit: u8,
+ // Copy L bytes from the window itself, starting from D bytes
+ // behind.
+ CopyFrom: struct { distance: u16, length: u16 },
+ },
+
+ // Sliding window for the LZ77 algorithm
+ window: struct {
+ const WSelf = @This();
+
+ // invariant: buffer length is always a power of 2
+ buf: []u8,
+ // invariant: ri <= wi
+ wi: usize = 0, // Write index
+ ri: usize = 0, // Read index
+ el: usize = 0, // Number of readable elements
+
+ fn readable(self: *WSelf) usize {
+ return self.el;
+ }
+
+ fn writable(self: *WSelf) usize {
+ return self.buf.len - self.el;
+ }
+
+ // Insert a single byte into the window.
+ // Returns 1 if there's enough space for the new byte and 0
+ // otherwise.
+ fn append(self: *WSelf, value: u8) usize {
+ if (self.writable() < 1) return 0;
+ self.appendUnsafe(value);
+ return 1;
+ }
+
+ // Insert a single byte into the window.
+ // Assumes there's enough space.
+ fn appendUnsafe(self: *WSelf, value: u8) void {
+ self.buf[self.wi] = value;
+ self.wi = (self.wi + 1) & (self.buf.len - 1);
+ self.el += 1;
+ }
+
+ // Fill dest[] with data from the window, starting from the read
+ // position. This updates the read pointer.
+ // Returns the number of read bytes or 0 if there's nothing to read
+ // yet.
+ fn read(self: *WSelf, dest: []u8) usize {
+ const N = math.min(dest.len, self.readable());
+
+ if (N == 0) return 0;
+
+ if (self.ri + N < self.buf.len) {
+ // The data doesn't wrap around
+ mem.copy(u8, dest, self.buf[self.ri .. self.ri + N]);
+ } else {
+ // The data wraps around the buffer, split the copy
+ std.mem.copy(u8, dest, self.buf[self.ri..]);
+ // How much data we've copied from `ri` to the end
+ const r = self.buf.len - self.ri;
+ std.mem.copy(u8, dest[r..], self.buf[0 .. N - r]);
+ }
+
+ self.ri = (self.ri + N) & (self.buf.len - 1);
+ self.el -= N;
+
+ return N;
+ }
+
+ // Copy `length` bytes starting from `distance` bytes behind the
+ // write pointer.
+ // Be careful as the length may be greater than the distance, that's
+ // how the compressor encodes run-length encoded sequences.
+ fn copyFrom(self: *WSelf, distance: usize, length: usize) usize {
+ const N = math.min(length, self.writable());
+
+ if (N == 0) return 0;
+
+ // TODO: Profile and, if needed, replace with smarter juggling
+ // of the window memory for the non-overlapping case.
+ var i: usize = 0;
+ while (i < N) : (i += 1) {
+ const index = (self.wi -% distance) % self.buf.len;
+ self.appendUnsafe(self.buf[index]);
+ }
+
+ return N;
+ }
+ },
+
+ // Compressor-local Huffman tables used to decompress blocks with
+ // dynamic codes.
+ huffman_tables: [2]Huffman = undefined,
+
+ // Huffman tables used for decoding length/distance pairs.
+ hdist: *Huffman,
+ hlen: *Huffman,
+
+ fn stored(self: *Self) !void {
+ // Discard the remaining bits, the lenght field is always
+ // byte-aligned (and so is the data)
+ self.bit_reader.alignToByte();
+
+ const length = (try self.bit_reader.readBitsNoEof(u16, 16));
+ const length_cpl = (try self.bit_reader.readBitsNoEof(u16, 16));
+
+ if (length != ~length_cpl)
+ return error.InvalidStoredSize;
+
+ self.state = .{ .Copy = length };
+ }
+
+ fn fixed(self: *Self) !void {
+ comptime var lencode: Huffman = undefined;
+ comptime var distcode: Huffman = undefined;
+
+ // The Huffman codes are specified in the RFC1951, section 3.2.6
+ comptime {
+ @setEvalBranchQuota(100000);
+
+ const len_lengths = //
+ [_]u16{8} ** 144 ++
+ [_]u16{9} ** 112 ++
+ [_]u16{7} ** 24 ++
+ [_]u16{8} ** 8;
+ assert(len_lengths.len == FIXLCODES);
+ try lencode.construct(len_lengths[0..]);
+
+ const dist_lengths = [_]u16{5} ** MAXDCODES;
+ try distcode.construct(dist_lengths[0..]);
+ }
+
+ self.hlen = &lencode;
+ self.hdist = &distcode;
+ self.state = .DecodeBlockData;
+ }
+
+ fn dynamic(self: *Self) !void {
+ // Number of length codes
+ const nlen = (try self.bit_reader.readBitsNoEof(usize, 5)) + 257;
+ // Number of distance codes
+ const ndist = (try self.bit_reader.readBitsNoEof(usize, 5)) + 1;
+ // Number of code length codes
+ const ncode = (try self.bit_reader.readBitsNoEof(usize, 4)) + 4;
+
+ if (nlen > MAXLCODES or ndist > MAXDCODES)
+ return error.BadCounts;
+
+ // Permutation of code length codes
+ const ORDER = [19]u16{
+ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4,
+ 12, 3, 13, 2, 14, 1, 15,
+ };
+
+ // Build the Huffman table to decode the code length codes
+ var lencode: Huffman = undefined;
+ {
+ var lengths = std.mem.zeroes([19]u16);
+
+ // Read the code lengths, missing ones are left as zero
+ for (ORDER[0..ncode]) |val| {
+ lengths[val] = try self.bit_reader.readBitsNoEof(u16, 3);
+ }
+
+ try lencode.construct(lengths[0..]);
+ }
+
+ // Read the length/literal and distance code length tables.
+ // Zero the table by default so we can avoid explicitly writing out
+ // zeros for codes 17 and 18
+ var lengths = std.mem.zeroes([MAXCODES]u16);
+
+ var i: usize = 0;
+ while (i < nlen + ndist) {
+ const symbol = try self.decode(&lencode);
+
+ switch (symbol) {
+ 0...15 => {
+ lengths[i] = symbol;
+ i += 1;
+ },
+ 16 => {
+ // repeat last length 3..6 times
+ if (i == 0) return error.NoLastLength;
+
+ const last_length = lengths[i - 1];
+ const repeat = 3 + (try self.bit_reader.readBitsNoEof(usize, 2));
+ const last_index = i + repeat;
+ while (i < last_index) : (i += 1) {
+ lengths[i] = last_length;
+ }
+ },
+ 17 => {
+ // repeat zero 3..10 times
+ i += 3 + (try self.bit_reader.readBitsNoEof(usize, 3));
+ },
+ 18 => {
+ // repeat zero 11..138 times
+ i += 11 + (try self.bit_reader.readBitsNoEof(usize, 7));
+ },
+ else => return error.InvalidSymbol,
+ }
+ }
+
+ if (i > nlen + ndist)
+ return error.InvalidLength;
+
+ // Check if the end of block code is present
+ if (lengths[256] == 0)
+ return error.MissingEOBCode;
+
+ try self.huffman_tables[0].construct(lengths[0..nlen]);
+ try self.huffman_tables[1].construct(lengths[nlen .. nlen + ndist]);
+
+ self.hlen = &self.huffman_tables[0];
+ self.hdist = &self.huffman_tables[1];
+ self.state = .DecodeBlockData;
+ }
+
+ fn codes(self: *Self, lencode: *Huffman, distcode: *Huffman) !bool {
+ // Size base for length codes 257..285
+ const LENS = [29]u16{
+ 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
+ 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258,
+ };
+ // Extra bits for length codes 257..285
+ const LEXT = [29]u16{
+ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
+ 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0,
+ };
+ // Offset base for distance codes 0..29
+ const DISTS = [30]u16{
+ 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
+ 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577,
+ };
+ // Extra bits for distance codes 0..29
+ const DEXT = [30]u16{
+ 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
+ 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13,
+ };
+
+ while (true) {
+ const symbol = try self.decode(lencode);
+
+ switch (symbol) {
+ 0...255 => {
+ // Literal value
+ const c = @truncate(u8, symbol);
+ if (self.window.append(c) == 0) {
+ self.state = .{ .CopyLit = c };
+ return false;
+ }
+ },
+ 256 => {
+ // End of block symbol
+ return true;
+ },
+ 257...285 => {
+ // Length/distance pair
+ const length_symbol = symbol - 257;
+ const length = LENS[length_symbol] +
+ try self.bit_reader.readBitsNoEof(u16, LEXT[length_symbol]);
+
+ const distance_symbol = try self.decode(distcode);
+ const distance = DISTS[distance_symbol] +
+ try self.bit_reader.readBitsNoEof(u16, DEXT[distance_symbol]);
+
+ if (distance > self.window.buf.len)
+ return error.InvalidDistance;
+
+ const written = self.window.copyFrom(distance, length);
+ if (written != length) {
+ self.state = .{
+ .CopyFrom = .{
+ .distance = distance,
+ .length = length - @truncate(u16, written),
+ },
+ };
+ return false;
+ }
+ },
+ else => return error.InvalidFixedCode,
+ }
+ }
+ }
+
+ fn decode(self: *Self, h: *Huffman) !u16 {
+ var len: usize = 1;
+ var code: usize = 0;
+ var first: usize = 0;
+ var index: usize = 0;
+
+ while (len <= MAXBITS) : (len += 1) {
+ code |= try self.bit_reader.readBitsNoEof(usize, 1);
+ const count = h.count[len];
+ if (code < first + count)
+ return h.symbol[index + (code - first)];
+ index += count;
+ first += count;
+ first <<= 1;
+ code <<= 1;
+ }
+
+ return error.OutOfCodes;
+ }
+
+ fn step(self: *Self) !void {
+ while (true) {
+ switch (self.state) {
+ .DecodeBlockHeader => {
+ // The compressed stream is done
+ if (self.seen_eos) return;
+
+ const last = try self.bit_reader.readBitsNoEof(u1, 1);
+ const kind = try self.bit_reader.readBitsNoEof(u2, 2);
+
+ self.seen_eos = last != 0;
+
+ // The next state depends on the block type
+ switch (kind) {
+ 0 => try self.stored(),
+ 1 => try self.fixed(),
+ 2 => try self.dynamic(),
+ 3 => return error.InvalidBlockType,
+ }
+ },
+ .DecodeBlockData => {
+ if (!try self.codes(self.hlen, self.hdist)) {
+ return;
+ }
+
+ self.state = .DecodeBlockHeader;
+ },
+ .Copy => |*length| {
+ const N = math.min(self.window.writable(), length.*);
+
+ // TODO: This loop can be more efficient. On the other
+ // hand uncompressed blocks are not that common so...
+ var i: usize = 0;
+ while (i < N) : (i += 1) {
+ var tmp: [1]u8 = undefined;
+ if ((try self.bit_reader.read(&tmp)) != 1) {
+ // Unexpected end of stream, keep this error
+ // consistent with the use of readBitsNoEof
+ return error.EndOfStream;
+ }
+ self.window.appendUnsafe(tmp[0]);
+ }
+
+ if (N != length.*) {
+ length.* -= N;
+ return;
+ }
+
+ self.state = .DecodeBlockHeader;
+ },
+ .CopyLit => |c| {
+ if (self.window.append(c) == 0) {
+ return;
+ }
+
+ self.state = .DecodeBlockData;
+ },
+ .CopyFrom => |*info| {
+ const written = self.window.copyFrom(info.distance, info.length);
+ if (written != info.length) {
+ info.length -= @truncate(u16, written);
+ return;
+ }
+
+ self.state = .DecodeBlockData;
+ },
+ }
+ }
+ }
+
+ fn init(source: ReaderType, window_slice: []u8) Self {
+ assert(math.isPowerOfTwo(window_slice.len));
+
+ return Self{
+ .bit_reader = io.bitReader(.Little, source),
+ .window = .{ .buf = window_slice },
+ .seen_eos = false,
+ .state = .DecodeBlockHeader,
+ .hdist = undefined,
+ .hlen = undefined,
+ };
+ }
+
+ // Implements the io.Reader interface
+ pub fn read(self: *Self, buffer: []u8) Error!usize {
+ if (buffer.len == 0)
+ return 0;
+
+ // Try reading as much as possible from the window
+ var read_amt: usize = self.window.read(buffer);
+ while (read_amt < buffer.len) {
+ // Run the state machine, we can detect the "effective" end of
+ // stream condition by checking if any progress was made.
+ // Why "effective"? Because even though `seen_eos` is true we
+ // may still have to finish processing other decoding steps.
+ try self.step();
+ // No progress was made
+ if (self.window.readable() == 0)
+ break;
+
+ read_amt += self.window.read(buffer[read_amt..]);
+ }
+
+ return read_amt;
+ }
+
+ pub fn reader(self: *Self) Reader {
+ return .{ .context = self };
+ }
+ };
+}
+
+pub fn inflateStream(reader: anytype, window_slice: []u8) InflateStream(@TypeOf(reader)) {
+ return InflateStream(@TypeOf(reader)).init(reader, window_slice);
+}
lib/std/compress/rfc1951.txt
@@ -0,0 +1,955 @@
+
+
+
+
+
+
+Network Working Group P. Deutsch
+Request for Comments: 1951 Aladdin Enterprises
+Category: Informational May 1996
+
+
+ DEFLATE Compressed Data Format Specification version 1.3
+
+Status of This Memo
+
+ This memo provides information for the Internet community. This memo
+ does not specify an Internet standard of any kind. Distribution of
+ this memo is unlimited.
+
+IESG Note:
+
+ The IESG takes no position on the validity of any Intellectual
+ Property Rights statements contained in this document.
+
+Notices
+
+ Copyright (c) 1996 L. Peter Deutsch
+
+ Permission is granted to copy and distribute this document for any
+ purpose and without charge, including translations into other
+ languages and incorporation into compilations, provided that the
+ copyright notice and this notice are preserved, and that any
+ substantive changes or deletions from the original are clearly
+ marked.
+
+ A pointer to the latest version of this and related documentation in
+ HTML format can be found at the URL
+ <ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html>.
+
+Abstract
+
+ This specification defines a lossless compressed data format that
+ compresses data using a combination of the LZ77 algorithm and Huffman
+ coding, with efficiency comparable to the best currently available
+ general-purpose compression methods. The data can be produced or
+ consumed, even for an arbitrarily long sequentially presented input
+ data stream, using only an a priori bounded amount of intermediate
+ storage. The format can be implemented readily in a manner not
+ covered by patents.
+
+
+
+
+
+
+
+
+Deutsch Informational [Page 1]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+Table of Contents
+
+ 1. Introduction ................................................... 2
+ 1.1. Purpose ................................................... 2
+ 1.2. Intended audience ......................................... 3
+ 1.3. Scope ..................................................... 3
+ 1.4. Compliance ................................................ 3
+ 1.5. Definitions of terms and conventions used ................ 3
+ 1.6. Changes from previous versions ............................ 4
+ 2. Compressed representation overview ............................. 4
+ 3. Detailed specification ......................................... 5
+ 3.1. Overall conventions ....................................... 5
+ 3.1.1. Packing into bytes .................................. 5
+ 3.2. Compressed block format ................................... 6
+ 3.2.1. Synopsis of prefix and Huffman coding ............... 6
+ 3.2.2. Use of Huffman coding in the "deflate" format ....... 7
+ 3.2.3. Details of block format ............................. 9
+ 3.2.4. Non-compressed blocks (BTYPE=00) ................... 11
+ 3.2.5. Compressed blocks (length and distance codes) ...... 11
+ 3.2.6. Compression with fixed Huffman codes (BTYPE=01) .... 12
+ 3.2.7. Compression with dynamic Huffman codes (BTYPE=10) .. 13
+ 3.3. Compliance ............................................... 14
+ 4. Compression algorithm details ................................. 14
+ 5. References .................................................... 16
+ 6. Security Considerations ....................................... 16
+ 7. Source code ................................................... 16
+ 8. Acknowledgements .............................................. 16
+ 9. Author's Address .............................................. 17
+
+1. Introduction
+
+ 1.1. Purpose
+
+ The purpose of this specification is to define a lossless
+ compressed data format that:
+ * Is independent of CPU type, operating system, file system,
+ and character set, and hence can be used for interchange;
+ * Can be produced or consumed, even for an arbitrarily long
+ sequentially presented input data stream, using only an a
+ priori bounded amount of intermediate storage, and hence
+ can be used in data communications or similar structures
+ such as Unix filters;
+ * Compresses data with efficiency comparable to the best
+ currently available general-purpose compression methods,
+ and in particular considerably better than the "compress"
+ program;
+ * Can be implemented readily in a manner not covered by
+ patents, and hence can be practiced freely;
+
+
+
+Deutsch Informational [Page 2]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ * Is compatible with the file format produced by the current
+ widely used gzip utility, in that conforming decompressors
+ will be able to read data produced by the existing gzip
+ compressor.
+
+ The data format defined by this specification does not attempt to:
+
+ * Allow random access to compressed data;
+ * Compress specialized data (e.g., raster graphics) as well
+ as the best currently available specialized algorithms.
+
+ A simple counting argument shows that no lossless compression
+ algorithm can compress every possible input data set. For the
+ format defined here, the worst case expansion is 5 bytes per 32K-
+ byte block, i.e., a size increase of 0.015% for large data sets.
+ English text usually compresses by a factor of 2.5 to 3;
+ executable files usually compress somewhat less; graphical data
+ such as raster images may compress much more.
+
+ 1.2. Intended audience
+
+ This specification is intended for use by implementors of software
+ to compress data into "deflate" format and/or decompress data from
+ "deflate" format.
+
+ The text of the specification assumes a basic background in
+ programming at the level of bits and other primitive data
+ representations. Familiarity with the technique of Huffman coding
+ is helpful but not required.
+
+ 1.3. Scope
+
+ The specification specifies a method for representing a sequence
+ of bytes as a (usually shorter) sequence of bits, and a method for
+ packing the latter bit sequence into bytes.
+
+ 1.4. Compliance
+
+ Unless otherwise indicated below, a compliant decompressor must be
+ able to accept and decompress any data set that conforms to all
+ the specifications presented here; a compliant compressor must
+ produce data sets that conform to all the specifications presented
+ here.
+
+ 1.5. Definitions of terms and conventions used
+
+ Byte: 8 bits stored or transmitted as a unit (same as an octet).
+ For this specification, a byte is exactly 8 bits, even on machines
+
+
+
+Deutsch Informational [Page 3]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ which store a character on a number of bits different from eight.
+ See below, for the numbering of bits within a byte.
+
+ String: a sequence of arbitrary bytes.
+
+ 1.6. Changes from previous versions
+
+ There have been no technical changes to the deflate format since
+ version 1.1 of this specification. In version 1.2, some
+ terminology was changed. Version 1.3 is a conversion of the
+ specification to RFC style.
+
+2. Compressed representation overview
+
+ A compressed data set consists of a series of blocks, corresponding
+ to successive blocks of input data. The block sizes are arbitrary,
+ except that non-compressible blocks are limited to 65,535 bytes.
+
+ Each block is compressed using a combination of the LZ77 algorithm
+ and Huffman coding. The Huffman trees for each block are independent
+ of those for previous or subsequent blocks; the LZ77 algorithm may
+ use a reference to a duplicated string occurring in a previous block,
+ up to 32K input bytes before.
+
+ Each block consists of two parts: a pair of Huffman code trees that
+ describe the representation of the compressed data part, and a
+ compressed data part. (The Huffman trees themselves are compressed
+ using Huffman encoding.) The compressed data consists of a series of
+ elements of two types: literal bytes (of strings that have not been
+ detected as duplicated within the previous 32K input bytes), and
+ pointers to duplicated strings, where a pointer is represented as a
+ pair <length, backward distance>. The representation used in the
+ "deflate" format limits distances to 32K bytes and lengths to 258
+ bytes, but does not limit the size of a block, except for
+ uncompressible blocks, which are limited as noted above.
+
+ Each type of value (literals, distances, and lengths) in the
+ compressed data is represented using a Huffman code, using one code
+ tree for literals and lengths and a separate code tree for distances.
+ The code trees for each block appear in a compact form just before
+ the compressed data for that block.
+
+
+
+
+
+
+
+
+
+
+Deutsch Informational [Page 4]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+3. Detailed specification
+
+ 3.1. Overall conventions In the diagrams below, a box like this:
+
+ +---+
+ | | <-- the vertical bars might be missing
+ +---+
+
+ represents one byte; a box like this:
+
+ +==============+
+ | |
+ +==============+
+
+ represents a variable number of bytes.
+
+ Bytes stored within a computer do not have a "bit order", since
+ they are always treated as a unit. However, a byte considered as
+ an integer between 0 and 255 does have a most- and least-
+ significant bit, and since we write numbers with the most-
+ significant digit on the left, we also write bytes with the most-
+ significant bit on the left. In the diagrams below, we number the
+ bits of a byte so that bit 0 is the least-significant bit, i.e.,
+ the bits are numbered:
+
+ +--------+
+ |76543210|
+ +--------+
+
+ Within a computer, a number may occupy multiple bytes. All
+ multi-byte numbers in the format described here are stored with
+ the least-significant byte first (at the lower memory address).
+ For example, the decimal number 520 is stored as:
+
+ 0 1
+ +--------+--------+
+ |00001000|00000010|
+ +--------+--------+
+ ^ ^
+ | |
+ | + more significant byte = 2 x 256
+ + less significant byte = 8
+
+ 3.1.1. Packing into bytes
+
+ This document does not address the issue of the order in which
+ bits of a byte are transmitted on a bit-sequential medium,
+ since the final data format described here is byte- rather than
+
+
+
+Deutsch Informational [Page 5]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ bit-oriented. However, we describe the compressed block format
+ in below, as a sequence of data elements of various bit
+ lengths, not a sequence of bytes. We must therefore specify
+ how to pack these data elements into bytes to form the final
+ compressed byte sequence:
+
+ * Data elements are packed into bytes in order of
+ increasing bit number within the byte, i.e., starting
+ with the least-significant bit of the byte.
+ * Data elements other than Huffman codes are packed
+ starting with the least-significant bit of the data
+ element.
+ * Huffman codes are packed starting with the most-
+ significant bit of the code.
+
+ In other words, if one were to print out the compressed data as
+ a sequence of bytes, starting with the first byte at the
+ *right* margin and proceeding to the *left*, with the most-
+ significant bit of each byte on the left as usual, one would be
+ able to parse the result from right to left, with fixed-width
+ elements in the correct MSB-to-LSB order and Huffman codes in
+ bit-reversed order (i.e., with the first bit of the code in the
+ relative LSB position).
+
+ 3.2. Compressed block format
+
+ 3.2.1. Synopsis of prefix and Huffman coding
+
+ Prefix coding represents symbols from an a priori known
+ alphabet by bit sequences (codes), one code for each symbol, in
+ a manner such that different symbols may be represented by bit
+ sequences of different lengths, but a parser can always parse
+ an encoded string unambiguously symbol-by-symbol.
+
+ We define a prefix code in terms of a binary tree in which the
+ two edges descending from each non-leaf node are labeled 0 and
+ 1 and in which the leaf nodes correspond one-for-one with (are
+ labeled with) the symbols of the alphabet; then the code for a
+ symbol is the sequence of 0's and 1's on the edges leading from
+ the root to the leaf labeled with that symbol. For example:
+
+
+
+
+
+
+
+
+
+
+
+Deutsch Informational [Page 6]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ /\ Symbol Code
+ 0 1 ------ ----
+ / \ A 00
+ /\ B B 1
+ 0 1 C 011
+ / \ D 010
+ A /\
+ 0 1
+ / \
+ D C
+
+ A parser can decode the next symbol from an encoded input
+ stream by walking down the tree from the root, at each step
+ choosing the edge corresponding to the next input bit.
+
+ Given an alphabet with known symbol frequencies, the Huffman
+ algorithm allows the construction of an optimal prefix code
+ (one which represents strings with those symbol frequencies
+ using the fewest bits of any possible prefix codes for that
+ alphabet). Such a code is called a Huffman code. (See
+ reference [1] in Chapter 5, references for additional
+ information on Huffman codes.)
+
+ Note that in the "deflate" format, the Huffman codes for the
+ various alphabets must not exceed certain maximum code lengths.
+ This constraint complicates the algorithm for computing code
+ lengths from symbol frequencies. Again, see Chapter 5,
+ references for details.
+
+ 3.2.2. Use of Huffman coding in the "deflate" format
+
+ The Huffman codes used for each alphabet in the "deflate"
+ format have two additional rules:
+
+ * All codes of a given bit length have lexicographically
+ consecutive values, in the same order as the symbols
+ they represent;
+
+ * Shorter codes lexicographically precede longer codes.
+
+
+
+
+
+
+
+
+
+
+
+
+Deutsch Informational [Page 7]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ We could recode the example above to follow this rule as
+ follows, assuming that the order of the alphabet is ABCD:
+
+ Symbol Code
+ ------ ----
+ A 10
+ B 0
+ C 110
+ D 111
+
+ I.e., 0 precedes 10 which precedes 11x, and 110 and 111 are
+ lexicographically consecutive.
+
+ Given this rule, we can define the Huffman code for an alphabet
+ just by giving the bit lengths of the codes for each symbol of
+ the alphabet in order; this is sufficient to determine the
+ actual codes. In our example, the code is completely defined
+ by the sequence of bit lengths (2, 1, 3, 3). The following
+ algorithm generates the codes as integers, intended to be read
+ from most- to least-significant bit. The code lengths are
+ initially in tree[I].Len; the codes are produced in
+ tree[I].Code.
+
+ 1) Count the number of codes for each code length. Let
+ bl_count[N] be the number of codes of length N, N >= 1.
+
+ 2) Find the numerical value of the smallest code for each
+ code length:
+
+ code = 0;
+ bl_count[0] = 0;
+ for (bits = 1; bits <= MAX_BITS; bits++) {
+ code = (code + bl_count[bits-1]) << 1;
+ next_code[bits] = code;
+ }
+
+ 3) Assign numerical values to all codes, using consecutive
+ values for all codes of the same length with the base
+ values determined at step 2. Codes that are never used
+ (which have a bit length of zero) must not be assigned a
+ value.
+
+ for (n = 0; n <= max_code; n++) {
+ len = tree[n].Len;
+ if (len != 0) {
+ tree[n].Code = next_code[len];
+ next_code[len]++;
+ }
+
+
+
+Deutsch Informational [Page 8]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ }
+
+ Example:
+
+ Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3,
+ 3, 2, 4, 4). After step 1, we have:
+
+ N bl_count[N]
+ - -----------
+ 2 1
+ 3 5
+ 4 2
+
+ Step 2 computes the following next_code values:
+
+ N next_code[N]
+ - ------------
+ 1 0
+ 2 0
+ 3 2
+ 4 14
+
+ Step 3 produces the following code values:
+
+ Symbol Length Code
+ ------ ------ ----
+ A 3 010
+ B 3 011
+ C 3 100
+ D 3 101
+ E 3 110
+ F 2 00
+ G 4 1110
+ H 4 1111
+
+ 3.2.3. Details of block format
+
+ Each block of compressed data begins with 3 header bits
+ containing the following data:
+
+ first bit BFINAL
+ next 2 bits BTYPE
+
+ Note that the header bits do not necessarily begin on a byte
+ boundary, since a block does not necessarily occupy an integral
+ number of bytes.
+
+
+
+
+
+Deutsch Informational [Page 9]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ BFINAL is set if and only if this is the last block of the data
+ set.
+
+ BTYPE specifies how the data are compressed, as follows:
+
+ 00 - no compression
+ 01 - compressed with fixed Huffman codes
+ 10 - compressed with dynamic Huffman codes
+ 11 - reserved (error)
+
+ The only difference between the two compressed cases is how the
+ Huffman codes for the literal/length and distance alphabets are
+ defined.
+
+ In all cases, the decoding algorithm for the actual data is as
+ follows:
+
+ do
+ read block header from input stream.
+ if stored with no compression
+ skip any remaining bits in current partially
+ processed byte
+ read LEN and NLEN (see next section)
+ copy LEN bytes of data to output
+ otherwise
+ if compressed with dynamic Huffman codes
+ read representation of code trees (see
+ subsection below)
+ loop (until end of block code recognized)
+ decode literal/length value from input stream
+ if value < 256
+ copy value (literal byte) to output stream
+ otherwise
+ if value = end of block (256)
+ break from loop
+ otherwise (value = 257..285)
+ decode distance from input stream
+
+ move backwards distance bytes in the output
+ stream, and copy length bytes from this
+ position to the output stream.
+ end loop
+ while not last block
+
+ Note that a duplicated string reference may refer to a string
+ in a previous block; i.e., the backward distance may cross one
+ or more block boundaries. However a distance cannot refer past
+ the beginning of the output stream. (An application using a
+
+
+
+Deutsch Informational [Page 10]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ preset dictionary might discard part of the output stream; a
+ distance can refer to that part of the output stream anyway)
+ Note also that the referenced string may overlap the current
+ position; for example, if the last 2 bytes decoded have values
+ X and Y, a string reference with <length = 5, distance = 2>
+ adds X,Y,X,Y,X to the output stream.
+
+ We now specify each compression method in turn.
+
+ 3.2.4. Non-compressed blocks (BTYPE=00)
+
+ Any bits of input up to the next byte boundary are ignored.
+ The rest of the block consists of the following information:
+
+ 0 1 2 3 4...
+ +---+---+---+---+================================+
+ | LEN | NLEN |... LEN bytes of literal data...|
+ +---+---+---+---+================================+
+
+ LEN is the number of data bytes in the block. NLEN is the
+ one's complement of LEN.
+
+ 3.2.5. Compressed blocks (length and distance codes)
+
+ As noted above, encoded data blocks in the "deflate" format
+ consist of sequences of symbols drawn from three conceptually
+ distinct alphabets: either literal bytes, from the alphabet of
+ byte values (0..255), or <length, backward distance> pairs,
+ where the length is drawn from (3..258) and the distance is
+ drawn from (1..32,768). In fact, the literal and length
+ alphabets are merged into a single alphabet (0..285), where
+ values 0..255 represent literal bytes, the value 256 indicates
+ end-of-block, and values 257..285 represent length codes
+ (possibly in conjunction with extra bits following the symbol
+ code) as follows:
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Deutsch Informational [Page 11]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ Extra Extra Extra
+ Code Bits Length(s) Code Bits Lengths Code Bits Length(s)
+ ---- ---- ------ ---- ---- ------- ---- ---- -------
+ 257 0 3 267 1 15,16 277 4 67-82
+ 258 0 4 268 1 17,18 278 4 83-98
+ 259 0 5 269 2 19-22 279 4 99-114
+ 260 0 6 270 2 23-26 280 4 115-130
+ 261 0 7 271 2 27-30 281 5 131-162
+ 262 0 8 272 2 31-34 282 5 163-194
+ 263 0 9 273 3 35-42 283 5 195-226
+ 264 0 10 274 3 43-50 284 5 227-257
+ 265 1 11,12 275 3 51-58 285 0 258
+ 266 1 13,14 276 3 59-66
+
+ The extra bits should be interpreted as a machine integer
+ stored with the most-significant bit first, e.g., bits 1110
+ represent the value 14.
+
+ Extra Extra Extra
+ Code Bits Dist Code Bits Dist Code Bits Distance
+ ---- ---- ---- ---- ---- ------ ---- ---- --------
+ 0 0 1 10 4 33-48 20 9 1025-1536
+ 1 0 2 11 4 49-64 21 9 1537-2048
+ 2 0 3 12 5 65-96 22 10 2049-3072
+ 3 0 4 13 5 97-128 23 10 3073-4096
+ 4 1 5,6 14 6 129-192 24 11 4097-6144
+ 5 1 7,8 15 6 193-256 25 11 6145-8192
+ 6 2 9-12 16 7 257-384 26 12 8193-12288
+ 7 2 13-16 17 7 385-512 27 12 12289-16384
+ 8 3 17-24 18 8 513-768 28 13 16385-24576
+ 9 3 25-32 19 8 769-1024 29 13 24577-32768
+
+ 3.2.6. Compression with fixed Huffman codes (BTYPE=01)
+
+ The Huffman codes for the two alphabets are fixed, and are not
+ represented explicitly in the data. The Huffman code lengths
+ for the literal/length alphabet are:
+
+ 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
+
+
+
+Deutsch Informational [Page 12]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ The code lengths are sufficient to generate the actual codes,
+ as described above; we show the codes in the table for added
+ clarity. Literal/length values 286-287 will never actually
+ occur in the compressed data, but participate in the code
+ construction.
+
+ Distance codes 0-31 are represented by (fixed-length) 5-bit
+ codes, with possible additional bits as shown in the table
+ shown in Paragraph 3.2.5, above. Note that distance codes 30-
+ 31 will never actually occur in the compressed data.
+
+ 3.2.7. Compression with dynamic Huffman codes (BTYPE=10)
+
+ The Huffman codes for the two alphabets appear in the block
+ immediately after the header bits and before the actual
+ compressed data, first the literal/length code and then the
+ distance code. Each code is defined by a sequence of code
+ lengths, as discussed in Paragraph 3.2.2, above. For even
+ greater compactness, the code length sequences themselves are
+ compressed using a Huffman code. The alphabet for code lengths
+ is as follows:
+
+ 0 - 15: Represent code lengths of 0 - 15
+ 16: Copy the previous code length 3 - 6 times.
+ The next 2 bits indicate repeat length
+ (0 = 3, ... , 3 = 6)
+ Example: Codes 8, 16 (+2 bits 11),
+ 16 (+2 bits 10) will expand to
+ 12 code lengths of 8 (1 + 6 + 5)
+ 17: Repeat a code length of 0 for 3 - 10 times.
+ (3 bits of length)
+ 18: Repeat a code length of 0 for 11 - 138 times
+ (7 bits of length)
+
+ A code length of 0 indicates that the corresponding symbol in
+ the literal/length or distance alphabet will not occur in the
+ block, and should not participate in the Huffman code
+ construction algorithm given earlier. If only one distance
+ code is used, it is encoded using one bit, not zero bits; in
+ this case there is a single code length of one, with one unused
+ code. One distance code of zero bits means that there are no
+ distance codes used at all (the data is all literals).
+
+ We can now define the format of the block:
+
+ 5 Bits: HLIT, # of Literal/Length codes - 257 (257 - 286)
+ 5 Bits: HDIST, # of Distance codes - 1 (1 - 32)
+ 4 Bits: HCLEN, # of Code Length codes - 4 (4 - 19)
+
+
+
+Deutsch Informational [Page 13]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ (HCLEN + 4) x 3 bits: code lengths for the code length
+ alphabet given just above, in the order: 16, 17, 18,
+ 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
+
+ These code lengths are interpreted as 3-bit integers
+ (0-7); as above, a code length of 0 means the
+ corresponding symbol (literal/length or distance code
+ length) is not used.
+
+ HLIT + 257 code lengths for the literal/length alphabet,
+ encoded using the code length Huffman code
+
+ HDIST + 1 code lengths for the distance alphabet,
+ encoded using the code length Huffman code
+
+ The actual compressed data of the block,
+ encoded using the literal/length and distance Huffman
+ codes
+
+ The literal/length symbol 256 (end of data),
+ encoded using the literal/length Huffman code
+
+ The code length repeat codes can cross from HLIT + 257 to the
+ HDIST + 1 code lengths. In other words, all code lengths form
+ a single sequence of HLIT + HDIST + 258 values.
+
+ 3.3. Compliance
+
+ A compressor may limit further the ranges of values specified in
+ the previous section and still be compliant; for example, it may
+ limit the range of backward pointers to some value smaller than
+ 32K. Similarly, a compressor may limit the size of blocks so that
+ a compressible block fits in memory.
+
+ A compliant decompressor must accept the full range of possible
+ values defined in the previous section, and must accept blocks of
+ arbitrary size.
+
+4. Compression algorithm details
+
+ While it is the intent of this document to define the "deflate"
+ compressed data format without reference to any particular
+ compression algorithm, the format is related to the compressed
+ formats produced by LZ77 (Lempel-Ziv 1977, see reference [2] below);
+ since many variations of LZ77 are patented, it is strongly
+ recommended that the implementor of a compressor follow the general
+ algorithm presented here, which is known not to be patented per se.
+ The material in this section is not part of the definition of the
+
+
+
+Deutsch Informational [Page 14]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+ specification per se, and a compressor need not follow it in order to
+ be compliant.
+
+ The compressor terminates a block when it determines that starting a
+ new block with fresh trees would be useful, or when the block size
+ fills up the compressor's block buffer.
+
+ The compressor uses a chained hash table to find duplicated strings,
+ using a hash function that operates on 3-byte sequences. At any
+ given point during compression, let XYZ be the next 3 input bytes to
+ be examined (not necessarily all different, of course). First, the
+ compressor examines the hash chain for XYZ. If the chain is empty,
+ the compressor simply writes out X as a literal byte and advances one
+ byte in the input. If the hash chain is not empty, indicating that
+ the sequence XYZ (or, if we are unlucky, some other 3 bytes with the
+ same hash function value) has occurred recently, the compressor
+ compares all strings on the XYZ hash chain with the actual input data
+ sequence starting at the current point, and selects the longest
+ match.
+
+ The compressor searches the hash chains starting with the most recent
+ strings, to favor small distances and thus take advantage of the
+ Huffman encoding. The hash chains are singly linked. There are no
+ deletions from the hash chains; the algorithm simply discards matches
+ that are too old. To avoid a worst-case situation, very long hash
+ chains are arbitrarily truncated at a certain length, determined by a
+ run-time parameter.
+
+ To improve overall compression, the compressor optionally defers the
+ selection of matches ("lazy matching"): after a match of length N has
+ been found, the compressor searches for a longer match starting at
+ the next input byte. If it finds a longer match, it truncates the
+ previous match to a length of one (thus producing a single literal
+ byte) and then emits the longer match. Otherwise, it emits the
+ original match, and, as described above, advances N bytes before
+ continuing.
+
+ Run-time parameters also control this "lazy match" procedure. If
+ compression ratio is most important, the compressor attempts a
+ complete second search regardless of the length of the first match.
+ In the normal case, if the current match is "long enough", the
+ compressor reduces the search for a longer match, thus speeding up
+ the process. If speed is most important, the compressor inserts new
+ strings in the hash table only when no match was found, or when the
+ match is not "too long". This degrades the compression ratio but
+ saves time since there are both fewer insertions and fewer searches.
+
+
+
+
+
+Deutsch Informational [Page 15]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+5. References
+
+ [1] Huffman, D. A., "A Method for the Construction of Minimum
+ Redundancy Codes", Proceedings of the Institute of Radio
+ Engineers, September 1952, Volume 40, Number 9, pp. 1098-1101.
+
+ [2] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data
+ Compression", IEEE Transactions on Information Theory, Vol. 23,
+ No. 3, pp. 337-343.
+
+ [3] Gailly, J.-L., and Adler, M., ZLIB documentation and sources,
+ available in ftp://ftp.uu.net/pub/archiving/zip/doc/
+
+ [4] Gailly, J.-L., and Adler, M., GZIP documentation and sources,
+ available as gzip-*.tar in ftp://prep.ai.mit.edu/pub/gnu/
+
+ [5] Schwartz, E. S., and Kallick, B. "Generating a canonical prefix
+ encoding." Comm. ACM, 7,3 (Mar. 1964), pp. 166-169.
+
+ [6] Hirschberg and Lelewer, "Efficient decoding of prefix codes,"
+ Comm. ACM, 33,4, April 1990, pp. 449-459.
+
+6. Security Considerations
+
+ Any data compression method involves the reduction of redundancy in
+ the data. Consequently, any corruption of the data is likely to have
+ severe effects and be difficult to correct. Uncompressed text, on
+ the other hand, will probably still be readable despite the presence
+ of some corrupted bytes.
+
+ It is recommended that systems using this data format provide some
+ means of validating the integrity of the compressed data. See
+ reference [3], for example.
+
+7. Source code
+
+ Source code for a C language implementation of a "deflate" compliant
+ compressor and decompressor is available within the zlib package at
+ ftp://ftp.uu.net/pub/archiving/zip/zlib/.
+
+8. Acknowledgements
+
+ Trademarks cited in this document are the property of their
+ respective owners.
+
+ Phil Katz designed the deflate format. Jean-Loup Gailly and Mark
+ Adler wrote the related software described in this specification.
+ Glenn Randers-Pehrson converted this document to RFC and HTML format.
+
+
+
+Deutsch Informational [Page 16]
+
+RFC 1951 DEFLATE Compressed Data Format Specification May 1996
+
+
+9. Author's Address
+
+ L. Peter Deutsch
+ Aladdin Enterprises
+ 203 Santa Margarita Ave.
+ Menlo Park, CA 94025
+
+ Phone: (415) 322-0103 (AM only)
+ FAX: (415) 322-1734
+ EMail: <ghost@aladdin.com>
+
+ Questions about the technical content of this specification can be
+ sent by email to:
+
+ Jean-Loup Gailly <gzip@prep.ai.mit.edu> and
+ Mark Adler <madler@alumni.caltech.edu>
+
+ Editorial comments on this specification can be sent by email to:
+
+ L. Peter Deutsch <ghost@aladdin.com> and
+ Glenn Randers-Pehrson <randeg@alumni.rpi.edu>
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Deutsch Informational [Page 17]
+
lib/std/compress/rfc1951.txt.fixed.z.9
Binary file
lib/std/compress/rfc1951.txt.z.0
Binary file
lib/std/compress/rfc1951.txt.z.9
Binary file
lib/std/compress/zlib.zig
@@ -0,0 +1,178 @@
+// SPDX-License-Identifier: MIT
+// Copyright (c) 2015-2020 Zig Contributors
+// This file is part of [zig](https://ziglang.org/), which is MIT licensed.
+// The MIT license requires this copyright notice to be included in all copies
+// and substantial portions of the software.
+//
+// Decompressor for ZLIB data streams (RFC1950)
+
+const std = @import("std");
+const io = std.io;
+const fs = std.fs;
+const testing = std.testing;
+const mem = std.mem;
+const deflate = std.compress.deflate;
+
+pub fn ZlibStream(comptime ReaderType: type) type {
+ return struct {
+ const Self = @This();
+
+ pub const Error = ReaderType.Error ||
+ deflate.InflateStream(ReaderType).Error ||
+ error{ WrongChecksum, Unsupported };
+ pub const Reader = io.Reader(*Self, Error, read);
+
+ allocator: *mem.Allocator,
+ inflater: deflate.InflateStream(ReaderType),
+ in_reader: ReaderType,
+ hasher: std.hash.Adler32,
+ window_slice: []u8,
+
+ fn init(allocator: *mem.Allocator, source: ReaderType) !Self {
+ // Zlib header format is specified in RFC1950
+ const header = try source.readBytesNoEof(2);
+
+ const CM = @truncate(u4, header[0]);
+ const CINFO = @truncate(u4, header[0] >> 4);
+ const FCHECK = @truncate(u5, header[1]);
+ const FDICT = @truncate(u1, header[1] >> 5);
+
+ if ((@as(u16, header[0]) << 8 | header[1]) % 31 != 0)
+ return error.BadHeader;
+
+ // The CM field must be 8 to indicate the use of DEFLATE
+ if (CM != 8) return error.InvalidCompression;
+ // CINFO is the base-2 logarithm of the window size, minus 8.
+ // Values above 7 are unspecified and therefore rejected.
+ if (CINFO > 7) return error.InvalidWindowSize;
+ const window_size: u16 = @as(u16, 1) << (CINFO + 8);
+
+ // TODO: Support this case
+ if (FDICT != 0)
+ return error.Unsupported;
+
+ var window_slice = try allocator.alloc(u8, window_size);
+
+ return Self{
+ .allocator = allocator,
+ .inflater = deflate.inflateStream(source, window_slice),
+ .in_reader = source,
+ .hasher = std.hash.Adler32.init(),
+ .window_slice = window_slice,
+ };
+ }
+
+ fn deinit(self: *Self) void {
+ self.allocator.free(self.window_slice);
+ }
+
+ // Implements the io.Reader interface
+ pub fn read(self: *Self, buffer: []u8) Error!usize {
+ if (buffer.len == 0)
+ return 0;
+
+ // Read from the compressed stream and update the computed checksum
+ const r = try self.inflater.read(buffer);
+ if (r != 0) {
+ self.hasher.update(buffer[0..r]);
+ return r;
+ }
+
+ // We've reached the end of stream, check if the checksum matches
+ const hash = try self.in_reader.readIntBig(u32);
+ if (hash != self.hasher.final())
+ return error.WrongChecksum;
+
+ return 0;
+ }
+
+ pub fn reader(self: *Self) Reader {
+ return .{ .context = self };
+ }
+ };
+}
+
+pub fn zlibStream(allocator: *mem.Allocator, reader: anytype) !ZlibStream(@TypeOf(reader)) {
+ return ZlibStream(@TypeOf(reader)).init(allocator, reader);
+}
+
+fn testReader(data: []const u8, comptime expected: []const u8) !void {
+ var in_stream = io.fixedBufferStream(data);
+
+ var zlib_stream = try zlibStream(testing.allocator, in_stream.reader());
+ defer zlib_stream.deinit();
+
+ // Read and decompress the whole file
+ const buf = try zlib_stream.reader().readAllAlloc(testing.allocator, std.math.maxInt(usize));
+ defer testing.allocator.free(buf);
+ // Calculate its SHA256 hash and check it against the reference
+ var hash: [32]u8 = undefined;
+ std.crypto.hash.sha2.Sha256.hash(buf, hash[0..], .{});
+
+ assertEqual(expected, &hash);
+}
+
+// Assert `expected` == `input` where `input` is a bytestring.
+pub fn assertEqual(comptime expected: []const u8, input: []const u8) void {
+ var expected_bytes: [expected.len / 2]u8 = undefined;
+ for (expected_bytes) |*r, i| {
+ r.* = std.fmt.parseInt(u8, expected[2 * i .. 2 * i + 2], 16) catch unreachable;
+ }
+
+ testing.expectEqualSlices(u8, &expected_bytes, input);
+}
+
+// All the test cases are obtained by compressing the RFC1950 text
+//
+// https://tools.ietf.org/rfc/rfc1950.txt length=36944 bytes
+// SHA256=5ebf4b5b7fe1c3a0c0ab9aa3ac8c0f3853a7dc484905e76e03b0b0f301350009
+test "compressed data" {
+ // Compressed with compression level = 0
+ try testReader(
+ @embedFile("rfc1951.txt.z.0"),
+ "5ebf4b5b7fe1c3a0c0ab9aa3ac8c0f3853a7dc484905e76e03b0b0f301350009",
+ );
+ // Compressed with compression level = 9
+ try testReader(
+ @embedFile("rfc1951.txt.z.9"),
+ "5ebf4b5b7fe1c3a0c0ab9aa3ac8c0f3853a7dc484905e76e03b0b0f301350009",
+ );
+ // Compressed with compression level = 9 and fixed Huffman codes
+ try testReader(
+ @embedFile("rfc1951.txt.fixed.z.9"),
+ "5ebf4b5b7fe1c3a0c0ab9aa3ac8c0f3853a7dc484905e76e03b0b0f301350009",
+ );
+}
+
+test "sanity checks" {
+ // Truncated header
+ testing.expectError(
+ error.EndOfStream,
+ testReader(&[_]u8{0x78}, ""),
+ );
+ // Failed FCHECK check
+ testing.expectError(
+ error.BadHeader,
+ testReader(&[_]u8{ 0x78, 0x9D }, ""),
+ );
+ // Wrong CM
+ testing.expectError(
+ error.InvalidCompression,
+ testReader(&[_]u8{ 0x79, 0x94 }, ""),
+ );
+ // Wrong CINFO
+ testing.expectError(
+ error.InvalidWindowSize,
+ testReader(&[_]u8{ 0x88, 0x98 }, ""),
+ );
+ // Wrong checksum
+ testing.expectError(
+ error.WrongChecksum,
+ testReader(&[_]u8{ 0x78, 0xda, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00 }, ""),
+ );
+ // Truncated checksum
+ testing.expectError(
+ error.EndOfStream,
+ testReader(&[_]u8{ 0x78, 0xda, 0x03, 0x00, 0x00 }, ""),
+ );
+}
lib/std/compress.zig
@@ -0,0 +1,13 @@
+// SPDX-License-Identifier: MIT
+// Copyright (c) 2015-2020 Zig Contributors
+// This file is part of [zig](https://ziglang.org/), which is MIT licensed.
+// The MIT license requires this copyright notice to be included in all copies
+// and substantial portions of the software.
+const std = @import("std.zig");
+
+pub const deflate = @import("compress/deflate.zig");
+pub const zlib = @import("compress/zlib.zig");
+
+test "" {
+ _ = zlib;
+}
lib/std/std.zig
@@ -50,6 +50,7 @@ pub const builtin = @import("builtin.zig");
pub const c = @import("c.zig");
pub const cache_hash = @import("cache_hash.zig");
pub const coff = @import("coff.zig");
+pub const compress = @import("compress.zig");
pub const crypto = @import("crypto.zig");
pub const cstr = @import("cstr.zig");
pub const debug = @import("debug.zig");