Commit d645114f7e

@@ -327,7 +327,7 @@ pub fn Compressor(comptime WriterType: anytype) type {
                     }
                 }
             }
-            const n = std.compress.deflate.copy(self.window[self.window_end..], b);
+            const n = std.compress.v1.deflate.copy(self.window[self.window_end..], b);
             self.window_end += n;
             return @as(u32, @intCast(n));
         }
@@ -705,7 +705,7 @@ pub fn Compressor(comptime WriterType: anytype) type {
         }
 
         fn fillStore(self: *Self, b: []const u8) u32 {
-            const n = std.compress.deflate.copy(self.window[self.window_end..], b);
+            const n = std.compress.v1.deflate.copy(self.window[self.window_end..], b);
             self.window_end += n;
             return @as(u32, @intCast(n));
         }

@@ -450,7 +450,7 @@ pub fn Decompressor(comptime ReaderType: type) type {
         pub fn read(self: *Self, output: []u8) Error!usize {
             while (true) {
                 if (self.to_read.len > 0) {
-                    const n = std.compress.deflate.copy(output, self.to_read);
+                    const n = std.compress.v1.deflate.copy(output, self.to_read);
                     self.to_read = self.to_read[n..];
                     if (self.to_read.len == 0 and
                         self.err != null)

@@ -0,0 +1,333 @@
+const std = @import("std");
+const assert = std.debug.assert;
+const testing = std.testing;
+
+pub fn bitReader(reader: anytype) BitReader(@TypeOf(reader)) {
+    return BitReader(@TypeOf(reader)).init(reader);
+}
+
+/// Bit reader used during inflate (decompression). Has internal buffer of 64
+/// bits which shifts right after bits are consumed. Uses forward_reader to fill
+/// that internal buffer when needed.
+///
+/// readF is the core function. Supports few different ways of getting bits
+/// controlled by flags. In hot path we try to avoid checking whether we need to
+/// fill buffer from forward_reader by calling fill in advance and readF with
+/// buffered flag set.
+///
+pub fn BitReader(comptime ReaderType: type) type {
+    return struct {
+        // Underlying reader used for filling internal bits buffer
+        forward_reader: ReaderType = undefined,
+        // Internal buffer of 64 bits
+        bits: u64 = 0,
+        // Number of bits in the buffer
+        nbits: u32 = 0,
+
+        const Self = @This();
+
+        pub const Error = ReaderType.Error || error{EndOfStream};
+
+        pub fn init(rdr: ReaderType) Self {
+            var self = Self{ .forward_reader = rdr };
+            self.fill(1) catch {};
+            return self;
+        }
+
+        // Try to have `nice` bits are available in buffer. Reads from
+        // forward reader if there is no `nice` bits in buffer. Returns error
+        // if end of forward stream is reached and internal buffer is empty.
+        // It will not error if less than `nice` bits are in buffer, only when
+        // all bits are exhausted. During inflate we usually know what is the
+        // maximum bits for the next step but usually that step will need less
+        // bits to decode. So `nice` is not hard limit, it will just try to have
+        // that number of bits available. If end of forward stream is reached
+        // it may be some extra zero bits in buffer.
+        pub inline fn fill(self: *Self, nice: u6) !void {
+            if (self.nbits >= nice) {
+                return; // We have enought bits
+            }
+            // Read more bits from forward reader
+
+            // Number of empty bytes in bits, round nbits to whole bytes.
+            const empty_bytes =
+                @as(u8, if (self.nbits & 0x7 == 0) 8 else 7) - // 8 for 8, 16, 24..., 7 otherwise
+                (self.nbits >> 3); // 0 for 0-7, 1 for 8-16, ... same as / 8
+
+            var buf: [8]u8 = [_]u8{0} ** 8;
+            const bytes_read = self.forward_reader.read(buf[0..empty_bytes]) catch 0;
+            if (bytes_read > 0) {
+                const u: u64 = std.mem.readInt(u64, buf[0..8], .little);
+                self.bits |= u << @as(u6, @intCast(self.nbits));
+                self.nbits += 8 * @as(u8, @intCast(bytes_read));
+                return;
+            }
+
+            if (self.nbits == 0)
+                return error.EndOfStream;
+        }
+
+        // Read exactly buf.len bytes into buf.
+        pub fn readAll(self: *Self, buf: []u8) !void {
+            assert(self.alignBits() == 0); // internal bits must be at byte boundary
+
+            // First read from internal bits buffer.
+            var n: usize = 0;
+            while (self.nbits > 0 and n < buf.len) {
+                buf[n] = try self.readF(u8, flag.buffered);
+                n += 1;
+            }
+            // Then use forward reader for all other bytes.
+            try self.forward_reader.readNoEof(buf[n..]);
+        }
+
+        pub const flag = struct {
+            pub const peek: u3 = 0b001; // dont advance internal buffer, just get bits, leave them in buffer
+            pub const buffered: u3 = 0b010; // assume that there is no need to fill, fill should be called before
+            pub const reverse: u3 = 0b100; // bit reverse readed bits
+        };
+
+        // Alias for readF(U, 0).
+        pub fn read(self: *Self, comptime U: type) !U {
+            return self.readF(U, 0);
+        }
+
+        // Alias for readF with flag.peak set.
+        pub inline fn peekF(self: *Self, comptime U: type, comptime how: u3) !U {
+            return self.readF(U, how | flag.peek);
+        }
+
+        // Read with flags provided.
+        pub fn readF(self: *Self, comptime U: type, comptime how: u3) !U {
+            const n: u6 = @bitSizeOf(U);
+            switch (how) {
+                0 => { // `normal` read
+                    try self.fill(n); // ensure that there are n bits in the buffer
+                    const u: U = @truncate(self.bits); // get n bits
+                    try self.shift(n); // advance buffer for n
+                    return u;
+                },
+                (flag.peek) => { // no shift, leave bits in the buffer
+                    try self.fill(n);
+                    return @truncate(self.bits);
+                },
+                flag.buffered => { // no fill, assume that buffer has enought bits
+                    const u: U = @truncate(self.bits);
+                    try self.shift(n);
+                    return u;
+                },
+                (flag.reverse) => { // same as 0 with bit reverse
+                    try self.fill(n);
+                    const u: U = @truncate(self.bits);
+                    try self.shift(n);
+                    return @bitReverse(u);
+                },
+                (flag.peek | flag.reverse) => {
+                    try self.fill(n);
+                    return @bitReverse(@as(U, @truncate(self.bits)));
+                },
+                (flag.buffered | flag.reverse) => {
+                    const u: U = @truncate(self.bits);
+                    try self.shift(n);
+                    return @bitReverse(u);
+                },
+                (flag.peek | flag.buffered) => {
+                    return @truncate(self.bits);
+                },
+                (flag.peek | flag.buffered | flag.reverse) => {
+                    return @bitReverse(@as(U, @truncate(self.bits)));
+                },
+            }
+        }
+
+        // Read n number of bits.
+        // Only buffered flag can be used in how.
+        pub fn readN(self: *Self, n: u4, comptime how: u3) !u16 {
+            switch (how) {
+                0 => {
+                    try self.fill(n);
+                },
+                flag.buffered => {},
+                else => unreachable,
+            }
+            const mask: u16 = (@as(u16, 1) << n) - 1;
+            const u: u16 = @as(u16, @truncate(self.bits)) & mask;
+            try self.shift(n);
+            return u;
+        }
+
+        // Advance buffer for n bits.
+        pub fn shift(self: *Self, n: u6) !void {
+            if (n > self.nbits) return error.EndOfStream;
+            self.bits >>= n;
+            self.nbits -= n;
+        }
+
+        // Skip n bytes.
+        pub fn skipBytes(self: *Self, n: u16) !void {
+            for (0..n) |_| {
+                try self.fill(8);
+                try self.shift(8);
+            }
+        }
+
+        // Number of bits to align stream to the byte boundary.
+        fn alignBits(self: *Self) u3 {
+            return @intCast(self.nbits & 0x7);
+        }
+
+        // Align stream to the byte boundary.
+        pub fn alignToByte(self: *Self) void {
+            const ab = self.alignBits();
+            if (ab > 0) self.shift(ab) catch unreachable;
+        }
+
+        // Skip zero terminated string.
+        pub fn skipStringZ(self: *Self) !void {
+            while (true) {
+                if (try self.readF(u8, 0) == 0) break;
+            }
+        }
+
+        // Read deflate fixed fixed code.
+        // Reads first 7 bits, and then mybe 1 or 2 more to get full 7,8 or 9 bit code.
+        // ref: https://datatracker.ietf.org/doc/html/rfc1951#page-12
+        //         Lit Value    Bits        Codes
+        //          ---------    ----        -----
+        //            0 - 143     8          00110000 through
+        //                                   10111111
+        //          144 - 255     9          110010000 through
+        //                                   111111111
+        //          256 - 279     7          0000000 through
+        //                                   0010111
+        //          280 - 287     8          11000000 through
+        //                                   11000111
+        pub fn readFixedCode(self: *Self) !u16 {
+            try self.fill(7 + 2);
+            const code7 = try self.readF(u7, flag.buffered | flag.reverse);
+            if (code7 <= 0b0010_111) { // 7 bits, 256-279, codes 0000_000 - 0010_111
+                return @as(u16, code7) + 256;
+            } else if (code7 <= 0b1011_111) { // 8 bits, 0-143, codes 0011_0000 through 1011_1111
+                return (@as(u16, code7) << 1) + @as(u16, try self.readF(u1, flag.buffered)) - 0b0011_0000;
+            } else if (code7 <= 0b1100_011) { // 8 bit, 280-287, codes 1100_0000 - 1100_0111
+                return (@as(u16, code7 - 0b1100000) << 1) + try self.readF(u1, flag.buffered) + 280;
+            } else { // 9 bit, 144-255, codes 1_1001_0000 - 1_1111_1111
+                return (@as(u16, code7 - 0b1100_100) << 2) + @as(u16, try self.readF(u2, flag.buffered | flag.reverse)) + 144;
+            }
+        }
+    };
+}
+
+test "flate.BitReader" {
+    var fbs = std.io.fixedBufferStream(&[_]u8{ 0xf3, 0x48, 0xcd, 0xc9, 0x00, 0x00 });
+    var br = bitReader(fbs.reader());
+    const F = BitReader(@TypeOf(fbs.reader())).flag;
+
+    try testing.expectEqual(@as(u8, 48), br.nbits);
+    try testing.expectEqual(@as(u64, 0xc9cd48f3), br.bits);
+
+    try testing.expect(try br.readF(u1, 0) == 0b0000_0001);
+    try testing.expect(try br.readF(u2, 0) == 0b0000_0001);
+    try testing.expectEqual(@as(u8, 48 - 3), br.nbits);
+    try testing.expectEqual(@as(u3, 5), br.alignBits());
+
+    try testing.expect(try br.readF(u8, F.peek) == 0b0001_1110);
+    try testing.expect(try br.readF(u9, F.peek) == 0b1_0001_1110);
+    try br.shift(9);
+    try testing.expectEqual(@as(u8, 36), br.nbits);
+    try testing.expectEqual(@as(u3, 4), br.alignBits());
+
+    try testing.expect(try br.readF(u4, 0) == 0b0100);
+    try testing.expectEqual(@as(u8, 32), br.nbits);
+    try testing.expectEqual(@as(u3, 0), br.alignBits());
+
+    try br.shift(1);
+    try testing.expectEqual(@as(u3, 7), br.alignBits());
+    try br.shift(1);
+    try testing.expectEqual(@as(u3, 6), br.alignBits());
+    br.alignToByte();
+    try testing.expectEqual(@as(u3, 0), br.alignBits());
+
+    try testing.expectEqual(@as(u64, 0xc9), br.bits);
+    try testing.expectEqual(@as(u16, 0x9), try br.readN(4, 0));
+    try testing.expectEqual(@as(u16, 0xc), try br.readN(4, 0));
+}
+
+test "flate.BitReader read block type 1 data" {
+    const data = [_]u8{
+        0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0x28, 0xcf, // deflate data block type 1
+        0x2f, 0xca, 0x49, 0xe1, 0x02, 0x00,
+        0x0c, 0x01, 0x02, 0x03, //
+        0xaa, 0xbb, 0xcc, 0xdd,
+    };
+    var fbs = std.io.fixedBufferStream(&data);
+    var br = bitReader(fbs.reader());
+    const F = BitReader(@TypeOf(fbs.reader())).flag;
+
+    try testing.expectEqual(@as(u1, 1), try br.readF(u1, 0)); // bfinal
+    try testing.expectEqual(@as(u2, 1), try br.readF(u2, 0)); // block_type
+
+    for ("Hello world\n") |c| {
+        try testing.expectEqual(@as(u8, c), try br.readF(u8, F.reverse) - 0x30);
+    }
+    try testing.expectEqual(@as(u7, 0), try br.readF(u7, 0)); // end of block
+    br.alignToByte();
+    try testing.expectEqual(@as(u32, 0x0302010c), try br.readF(u32, 0));
+    try testing.expectEqual(@as(u16, 0xbbaa), try br.readF(u16, 0));
+    try testing.expectEqual(@as(u16, 0xddcc), try br.readF(u16, 0));
+}
+
+test "flate.BitReader init" {
+    const data = [_]u8{
+        0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
+        0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
+    };
+    var fbs = std.io.fixedBufferStream(&data);
+    var br = bitReader(fbs.reader());
+
+    try testing.expectEqual(@as(u64, 0x08_07_06_05_04_03_02_01), br.bits);
+    try br.shift(8);
+    try testing.expectEqual(@as(u64, 0x00_08_07_06_05_04_03_02), br.bits);
+    try br.fill(60); // fill with 1 byte
+    try testing.expectEqual(@as(u64, 0x01_08_07_06_05_04_03_02), br.bits);
+    try br.shift(8 * 4 + 4);
+    try testing.expectEqual(@as(u64, 0x00_00_00_00_00_10_80_70), br.bits);
+
+    try br.fill(60); // fill with 4 bytes (shift by 4)
+    try testing.expectEqual(@as(u64, 0x00_50_40_30_20_10_80_70), br.bits);
+    try testing.expectEqual(@as(u8, 8 * 7 + 4), br.nbits);
+
+    try br.shift(@intCast(br.nbits)); // clear buffer
+    try br.fill(8); // refill with the rest of the bytes
+    try testing.expectEqual(@as(u64, 0x00_00_00_00_00_08_07_06), br.bits);
+}
+
+test "flate.BitReader readAll" {
+    const data = [_]u8{
+        0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
+        0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,
+    };
+    var fbs = std.io.fixedBufferStream(&data);
+    var br = bitReader(fbs.reader());
+
+    try testing.expectEqual(@as(u64, 0x08_07_06_05_04_03_02_01), br.bits);
+
+    var out: [16]u8 = undefined;
+    try br.readAll(out[0..]);
+    try testing.expect(br.nbits == 0);
+    try testing.expect(br.bits == 0);
+
+    try testing.expectEqualSlices(u8, data[0..16], &out);
+}
+
+test "flate.BitReader readFixedCode" {
+    const fixed_codes = @import("huffman_encoder.zig").fixed_codes;
+
+    var fbs = std.io.fixedBufferStream(&fixed_codes);
+    var rdr = bitReader(fbs.reader());
+
+    for (0..286) |c| {
+        try testing.expectEqual(c, try rdr.readFixedCode());
+    }
+    try testing.expect(rdr.nbits == 0);
+}

@@ -0,0 +1,99 @@
+const std = @import("std");
+const assert = std.debug.assert;
+
+/// Bit writer for use in deflate (compression).
+///
+/// Has internal bits buffer of 64 bits and internal bytes buffer of 248 bytes.
+/// When we accumulate 48 bits 6 bytes are moved to the bytes buffer. When we
+/// accumulate 240 bytes they are flushed to the underlying inner_writer.
+///
+pub fn BitWriter(comptime WriterType: type) type {
+    // buffer_flush_size indicates the buffer size
+    // after which bytes are flushed to the writer.
+    // Should preferably be a multiple of 6, since
+    // we accumulate 6 bytes between writes to the buffer.
+    const buffer_flush_size = 240;
+
+    // buffer_size is the actual output byte buffer size.
+    // It must have additional headroom for a flush
+    // which can contain up to 8 bytes.
+    const buffer_size = buffer_flush_size + 8;
+
+    return struct {
+        inner_writer: WriterType,
+
+        // Data waiting to be written is bytes[0 .. nbytes]
+        // and then the low nbits of bits.  Data is always written
+        // sequentially into the bytes array.
+        bits: u64 = 0,
+        nbits: u32 = 0, // number of bits
+        bytes: [buffer_size]u8 = undefined,
+        nbytes: u32 = 0, // number of bytes
+
+        const Self = @This();
+
+        pub const Error = WriterType.Error || error{UnfinishedBits};
+
+        pub fn init(writer: WriterType) Self {
+            return .{ .inner_writer = writer };
+        }
+
+        pub fn setWriter(self: *Self, new_writer: WriterType) void {
+            //assert(self.bits == 0 and self.nbits == 0 and self.nbytes == 0);
+            self.inner_writer = new_writer;
+        }
+
+        pub fn flush(self: *Self) Error!void {
+            var n = self.nbytes;
+            while (self.nbits != 0) {
+                self.bytes[n] = @as(u8, @truncate(self.bits));
+                self.bits >>= 8;
+                if (self.nbits > 8) { // Avoid underflow
+                    self.nbits -= 8;
+                } else {
+                    self.nbits = 0;
+                }
+                n += 1;
+            }
+            self.bits = 0;
+            _ = try self.inner_writer.write(self.bytes[0..n]);
+            self.nbytes = 0;
+        }
+
+        pub fn writeBits(self: *Self, b: u32, nb: u32) Error!void {
+            self.bits |= @as(u64, @intCast(b)) << @as(u6, @intCast(self.nbits));
+            self.nbits += nb;
+            if (self.nbits < 48)
+                return;
+
+            var n = self.nbytes;
+            std.mem.writeInt(u64, self.bytes[n..][0..8], self.bits, .little);
+            n += 6;
+            if (n >= buffer_flush_size) {
+                _ = try self.inner_writer.write(self.bytes[0..n]);
+                n = 0;
+            }
+            self.nbytes = n;
+            self.bits >>= 48;
+            self.nbits -= 48;
+        }
+
+        pub fn writeBytes(self: *Self, bytes: []const u8) Error!void {
+            var n = self.nbytes;
+            if (self.nbits & 7 != 0) {
+                return error.UnfinishedBits;
+            }
+            while (self.nbits != 0) {
+                self.bytes[n] = @as(u8, @truncate(self.bits));
+                self.bits >>= 8;
+                self.nbits -= 8;
+                n += 1;
+            }
+            if (n != 0) {
+                _ = try self.inner_writer.write(self.bytes[0..n]);
+            }
+            self.nbytes = 0;
+            _ = try self.inner_writer.write(bytes);
+        }
+    };
+}

@@ -0,0 +1,706 @@
+const std = @import("std");
+const io = std.io;
+const assert = std.debug.assert;
+
+const hc = @import("huffman_encoder.zig");
+const consts = @import("consts.zig").huffman;
+const Token = @import("Token.zig");
+const BitWriter = @import("bit_writer.zig").BitWriter;
+
+pub fn blockWriter(writer: anytype) BlockWriter(@TypeOf(writer)) {
+    return BlockWriter(@TypeOf(writer)).init(writer);
+}
+
+/// Accepts list of tokens, decides what is best block type to write. What block
+/// type will provide best compression. Writes header and body of the block.
+///
+pub fn BlockWriter(comptime WriterType: type) type {
+    const BitWriterType = BitWriter(WriterType);
+    return struct {
+        const codegen_order = consts.codegen_order;
+        const end_code_mark = 255;
+        const Self = @This();
+
+        pub const Error = BitWriterType.Error;
+        bit_writer: BitWriterType,
+
+        codegen_freq: [consts.codegen_code_count]u16 = undefined,
+        literal_freq: [consts.max_num_lit]u16 = undefined,
+        distance_freq: [consts.distance_code_count]u16 = undefined,
+        codegen: [consts.max_num_lit + consts.distance_code_count + 1]u8 = undefined,
+        literal_encoding: hc.LiteralEncoder = .{},
+        distance_encoding: hc.DistanceEncoder = .{},
+        codegen_encoding: hc.CodegenEncoder = .{},
+        fixed_literal_encoding: hc.LiteralEncoder,
+        fixed_distance_encoding: hc.DistanceEncoder,
+        huff_distance: hc.DistanceEncoder,
+
+        pub fn init(writer: WriterType) Self {
+            return .{
+                .bit_writer = BitWriterType.init(writer),
+                .fixed_literal_encoding = hc.fixedLiteralEncoder(),
+                .fixed_distance_encoding = hc.fixedDistanceEncoder(),
+                .huff_distance = hc.huffmanDistanceEncoder(),
+            };
+        }
+
+        /// Flush intrenal bit buffer to the writer.
+        /// Should be called only when bit stream is at byte boundary.
+        ///
+        /// That is after final block; when last byte could be incomplete or
+        /// after stored block; which is aligned to the byte bounday (it has x
+        /// padding bits after first 3 bits).
+        pub fn flush(self: *Self) Error!void {
+            try self.bit_writer.flush();
+        }
+
+        pub fn setWriter(self: *Self, new_writer: WriterType) void {
+            self.bit_writer.setWriter(new_writer);
+        }
+
+        fn writeCode(self: *Self, c: hc.HuffCode) Error!void {
+            try self.bit_writer.writeBits(c.code, c.len);
+        }
+
+        // RFC 1951 3.2.7 specifies a special run-length encoding for specifying
+        // the literal and distance lengths arrays (which are concatenated into a single
+        // array).  This method generates that run-length encoding.
+        //
+        // The result is written into the codegen array, and the frequencies
+        // of each code is written into the codegen_freq array.
+        // Codes 0-15 are single byte codes. Codes 16-18 are followed by additional
+        // information. Code bad_code is an end marker
+        //
+        // num_literals: The number of literals in literal_encoding
+        // num_distances: The number of distances in distance_encoding
+        // lit_enc: The literal encoder to use
+        // dist_enc: The distance encoder to use
+        fn generateCodegen(
+            self: *Self,
+            num_literals: u32,
+            num_distances: u32,
+            lit_enc: *hc.LiteralEncoder,
+            dist_enc: *hc.DistanceEncoder,
+        ) void {
+            for (self.codegen_freq, 0..) |_, i| {
+                self.codegen_freq[i] = 0;
+            }
+
+            // Note that we are using codegen both as a temporary variable for holding
+            // a copy of the frequencies, and as the place where we put the result.
+            // This is fine because the output is always shorter than the input used
+            // so far.
+            var codegen = &self.codegen; // cache
+            // Copy the concatenated code sizes to codegen. Put a marker at the end.
+            var cgnl = codegen[0..num_literals];
+            for (cgnl, 0..) |_, i| {
+                cgnl[i] = @as(u8, @intCast(lit_enc.codes[i].len));
+            }
+
+            cgnl = codegen[num_literals .. num_literals + num_distances];
+            for (cgnl, 0..) |_, i| {
+                cgnl[i] = @as(u8, @intCast(dist_enc.codes[i].len));
+            }
+            codegen[num_literals + num_distances] = end_code_mark;
+
+            var size = codegen[0];
+            var count: i32 = 1;
+            var out_index: u32 = 0;
+            var in_index: u32 = 1;
+            while (size != end_code_mark) : (in_index += 1) {
+                // INVARIANT: We have seen "count" copies of size that have not yet
+                // had output generated for them.
+                const next_size = codegen[in_index];
+                if (next_size == size) {
+                    count += 1;
+                    continue;
+                }
+                // We need to generate codegen indicating "count" of size.
+                if (size != 0) {
+                    codegen[out_index] = size;
+                    out_index += 1;
+                    self.codegen_freq[size] += 1;
+                    count -= 1;
+                    while (count >= 3) {
+                        var n: i32 = 6;
+                        if (n > count) {
+                            n = count;
+                        }
+                        codegen[out_index] = 16;
+                        out_index += 1;
+                        codegen[out_index] = @as(u8, @intCast(n - 3));
+                        out_index += 1;
+                        self.codegen_freq[16] += 1;
+                        count -= n;
+                    }
+                } else {
+                    while (count >= 11) {
+                        var n: i32 = 138;
+                        if (n > count) {
+                            n = count;
+                        }
+                        codegen[out_index] = 18;
+                        out_index += 1;
+                        codegen[out_index] = @as(u8, @intCast(n - 11));
+                        out_index += 1;
+                        self.codegen_freq[18] += 1;
+                        count -= n;
+                    }
+                    if (count >= 3) {
+                        // 3 <= count <= 10
+                        codegen[out_index] = 17;
+                        out_index += 1;
+                        codegen[out_index] = @as(u8, @intCast(count - 3));
+                        out_index += 1;
+                        self.codegen_freq[17] += 1;
+                        count = 0;
+                    }
+                }
+                count -= 1;
+                while (count >= 0) : (count -= 1) {
+                    codegen[out_index] = size;
+                    out_index += 1;
+                    self.codegen_freq[size] += 1;
+                }
+                // Set up invariant for next time through the loop.
+                size = next_size;
+                count = 1;
+            }
+            // Marker indicating the end of the codegen.
+            codegen[out_index] = end_code_mark;
+        }
+
+        const DynamicSize = struct {
+            size: u32,
+            num_codegens: u32,
+        };
+
+        // dynamicSize returns the size of dynamically encoded data in bits.
+        fn dynamicSize(
+            self: *Self,
+            lit_enc: *hc.LiteralEncoder, // literal encoder
+            dist_enc: *hc.DistanceEncoder, // distance encoder
+            extra_bits: u32,
+        ) DynamicSize {
+            var num_codegens = self.codegen_freq.len;
+            while (num_codegens > 4 and self.codegen_freq[codegen_order[num_codegens - 1]] == 0) {
+                num_codegens -= 1;
+            }
+            const header = 3 + 5 + 5 + 4 + (3 * num_codegens) +
+                self.codegen_encoding.bitLength(self.codegen_freq[0..]) +
+                self.codegen_freq[16] * 2 +
+                self.codegen_freq[17] * 3 +
+                self.codegen_freq[18] * 7;
+            const size = header +
+                lit_enc.bitLength(&self.literal_freq) +
+                dist_enc.bitLength(&self.distance_freq) +
+                extra_bits;
+
+            return DynamicSize{
+                .size = @as(u32, @intCast(size)),
+                .num_codegens = @as(u32, @intCast(num_codegens)),
+            };
+        }
+
+        // fixedSize returns the size of dynamically encoded data in bits.
+        fn fixedSize(self: *Self, extra_bits: u32) u32 {
+            return 3 +
+                self.fixed_literal_encoding.bitLength(&self.literal_freq) +
+                self.fixed_distance_encoding.bitLength(&self.distance_freq) +
+                extra_bits;
+        }
+
+        const StoredSize = struct {
+            size: u32,
+            storable: bool,
+        };
+
+        // storedSizeFits calculates the stored size, including header.
+        // The function returns the size in bits and whether the block
+        // fits inside a single block.
+        fn storedSizeFits(in: ?[]const u8) StoredSize {
+            if (in == null) {
+                return .{ .size = 0, .storable = false };
+            }
+            if (in.?.len <= consts.max_store_block_size) {
+                return .{ .size = @as(u32, @intCast((in.?.len + 5) * 8)), .storable = true };
+            }
+            return .{ .size = 0, .storable = false };
+        }
+
+        // Write the header of a dynamic Huffman block to the output stream.
+        //
+        //  num_literals: The number of literals specified in codegen
+        //  num_distances: The number of distances specified in codegen
+        //  num_codegens: The number of codegens used in codegen
+        //  eof: Is it the end-of-file? (end of stream)
+        fn dynamicHeader(
+            self: *Self,
+            num_literals: u32,
+            num_distances: u32,
+            num_codegens: u32,
+            eof: bool,
+        ) Error!void {
+            const first_bits: u32 = if (eof) 5 else 4;
+            try self.bit_writer.writeBits(first_bits, 3);
+            try self.bit_writer.writeBits(num_literals - 257, 5);
+            try self.bit_writer.writeBits(num_distances - 1, 5);
+            try self.bit_writer.writeBits(num_codegens - 4, 4);
+
+            var i: u32 = 0;
+            while (i < num_codegens) : (i += 1) {
+                const value = self.codegen_encoding.codes[codegen_order[i]].len;
+                try self.bit_writer.writeBits(value, 3);
+            }
+
+            i = 0;
+            while (true) {
+                const code_word: u32 = @as(u32, @intCast(self.codegen[i]));
+                i += 1;
+                if (code_word == end_code_mark) {
+                    break;
+                }
+                try self.writeCode(self.codegen_encoding.codes[@as(u32, @intCast(code_word))]);
+
+                switch (code_word) {
+                    16 => {
+                        try self.bit_writer.writeBits(self.codegen[i], 2);
+                        i += 1;
+                    },
+                    17 => {
+                        try self.bit_writer.writeBits(self.codegen[i], 3);
+                        i += 1;
+                    },
+                    18 => {
+                        try self.bit_writer.writeBits(self.codegen[i], 7);
+                        i += 1;
+                    },
+                    else => {},
+                }
+            }
+        }
+
+        fn storedHeader(self: *Self, length: usize, eof: bool) Error!void {
+            assert(length <= 65535);
+            const flag: u32 = if (eof) 1 else 0;
+            try self.bit_writer.writeBits(flag, 3);
+            try self.flush();
+            const l: u16 = @intCast(length);
+            try self.bit_writer.writeBits(l, 16);
+            try self.bit_writer.writeBits(~l, 16);
+        }
+
+        fn fixedHeader(self: *Self, eof: bool) Error!void {
+            // Indicate that we are a fixed Huffman block
+            var value: u32 = 2;
+            if (eof) {
+                value = 3;
+            }
+            try self.bit_writer.writeBits(value, 3);
+        }
+
+        // Write a block of tokens with the smallest encoding. Will choose block type.
+        // The original input can be supplied, and if the huffman encoded data
+        // is larger than the original bytes, the data will be written as a
+        // stored block.
+        // If the input is null, the tokens will always be Huffman encoded.
+        pub fn write(self: *Self, tokens: []const Token, eof: bool, input: ?[]const u8) Error!void {
+            const lit_and_dist = self.indexTokens(tokens);
+            const num_literals = lit_and_dist.num_literals;
+            const num_distances = lit_and_dist.num_distances;
+
+            var extra_bits: u32 = 0;
+            const ret = storedSizeFits(input);
+            const stored_size = ret.size;
+            const storable = ret.storable;
+
+            if (storable) {
+                // We only bother calculating the costs of the extra bits required by
+                // the length of distance fields (which will be the same for both fixed
+                // and dynamic encoding), if we need to compare those two encodings
+                // against stored encoding.
+                var length_code: u16 = Token.length_codes_start + 8;
+                while (length_code < num_literals) : (length_code += 1) {
+                    // First eight length codes have extra size = 0.
+                    extra_bits += @as(u32, @intCast(self.literal_freq[length_code])) *
+                        @as(u32, @intCast(Token.lengthExtraBits(length_code)));
+                }
+                var distance_code: u16 = 4;
+                while (distance_code < num_distances) : (distance_code += 1) {
+                    // First four distance codes have extra size = 0.
+                    extra_bits += @as(u32, @intCast(self.distance_freq[distance_code])) *
+                        @as(u32, @intCast(Token.distanceExtraBits(distance_code)));
+                }
+            }
+
+            // Figure out smallest code.
+            // Fixed Huffman baseline.
+            var literal_encoding = &self.fixed_literal_encoding;
+            var distance_encoding = &self.fixed_distance_encoding;
+            var size = self.fixedSize(extra_bits);
+
+            // Dynamic Huffman?
+            var num_codegens: u32 = 0;
+
+            // Generate codegen and codegenFrequencies, which indicates how to encode
+            // the literal_encoding and the distance_encoding.
+            self.generateCodegen(
+                num_literals,
+                num_distances,
+                &self.literal_encoding,
+                &self.distance_encoding,
+            );
+            self.codegen_encoding.generate(self.codegen_freq[0..], 7);
+            const dynamic_size = self.dynamicSize(
+                &self.literal_encoding,
+                &self.distance_encoding,
+                extra_bits,
+            );
+            const dyn_size = dynamic_size.size;
+            num_codegens = dynamic_size.num_codegens;
+
+            if (dyn_size < size) {
+                size = dyn_size;
+                literal_encoding = &self.literal_encoding;
+                distance_encoding = &self.distance_encoding;
+            }
+
+            // Stored bytes?
+            if (storable and stored_size < size) {
+                try self.storedBlock(input.?, eof);
+                return;
+            }
+
+            // Huffman.
+            if (@intFromPtr(literal_encoding) == @intFromPtr(&self.fixed_literal_encoding)) {
+                try self.fixedHeader(eof);
+            } else {
+                try self.dynamicHeader(num_literals, num_distances, num_codegens, eof);
+            }
+
+            // Write the tokens.
+            try self.writeTokens(tokens, &literal_encoding.codes, &distance_encoding.codes);
+        }
+
+        pub fn storedBlock(self: *Self, input: []const u8, eof: bool) Error!void {
+            try self.storedHeader(input.len, eof);
+            try self.bit_writer.writeBytes(input);
+        }
+
+        // writeBlockDynamic encodes a block using a dynamic Huffman table.
+        // This should be used if the symbols used have a disproportionate
+        // histogram distribution.
+        // If input is supplied and the compression savings are below 1/16th of the
+        // input size the block is stored.
+        fn dynamicBlock(
+            self: *Self,
+            tokens: []const Token,
+            eof: bool,
+            input: ?[]const u8,
+        ) Error!void {
+            const total_tokens = self.indexTokens(tokens);
+            const num_literals = total_tokens.num_literals;
+            const num_distances = total_tokens.num_distances;
+
+            // Generate codegen and codegenFrequencies, which indicates how to encode
+            // the literal_encoding and the distance_encoding.
+            self.generateCodegen(
+                num_literals,
+                num_distances,
+                &self.literal_encoding,
+                &self.distance_encoding,
+            );
+            self.codegen_encoding.generate(self.codegen_freq[0..], 7);
+            const dynamic_size = self.dynamicSize(&self.literal_encoding, &self.distance_encoding, 0);
+            const size = dynamic_size.size;
+            const num_codegens = dynamic_size.num_codegens;
+
+            // Store bytes, if we don't get a reasonable improvement.
+
+            const stored_size = storedSizeFits(input);
+            const ssize = stored_size.size;
+            const storable = stored_size.storable;
+            if (storable and ssize < (size + (size >> 4))) {
+                try self.storedBlock(input.?, eof);
+                return;
+            }
+
+            // Write Huffman table.
+            try self.dynamicHeader(num_literals, num_distances, num_codegens, eof);
+
+            // Write the tokens.
+            try self.writeTokens(tokens, &self.literal_encoding.codes, &self.distance_encoding.codes);
+        }
+
+        const TotalIndexedTokens = struct {
+            num_literals: u32,
+            num_distances: u32,
+        };
+
+        // Indexes a slice of tokens followed by an end_block_marker, and updates
+        // literal_freq and distance_freq, and generates literal_encoding
+        // and distance_encoding.
+        // The number of literal and distance tokens is returned.
+        fn indexTokens(self: *Self, tokens: []const Token) TotalIndexedTokens {
+            var num_literals: u32 = 0;
+            var num_distances: u32 = 0;
+
+            for (self.literal_freq, 0..) |_, i| {
+                self.literal_freq[i] = 0;
+            }
+            for (self.distance_freq, 0..) |_, i| {
+                self.distance_freq[i] = 0;
+            }
+
+            for (tokens) |t| {
+                if (t.kind == Token.Kind.literal) {
+                    self.literal_freq[t.literal()] += 1;
+                    continue;
+                }
+                self.literal_freq[t.lengthCode()] += 1;
+                self.distance_freq[t.distanceCode()] += 1;
+            }
+            // add end_block_marker token at the end
+            self.literal_freq[consts.end_block_marker] += 1;
+
+            // get the number of literals
+            num_literals = @as(u32, @intCast(self.literal_freq.len));
+            while (self.literal_freq[num_literals - 1] == 0) {
+                num_literals -= 1;
+            }
+            // get the number of distances
+            num_distances = @as(u32, @intCast(self.distance_freq.len));
+            while (num_distances > 0 and self.distance_freq[num_distances - 1] == 0) {
+                num_distances -= 1;
+            }
+            if (num_distances == 0) {
+                // We haven't found a single match. If we want to go with the dynamic encoding,
+                // we should count at least one distance to be sure that the distance huffman tree could be encoded.
+                self.distance_freq[0] = 1;
+                num_distances = 1;
+            }
+            self.literal_encoding.generate(&self.literal_freq, 15);
+            self.distance_encoding.generate(&self.distance_freq, 15);
+            return TotalIndexedTokens{
+                .num_literals = num_literals,
+                .num_distances = num_distances,
+            };
+        }
+
+        // Writes a slice of tokens to the output followed by and end_block_marker.
+        // codes for literal and distance encoding must be supplied.
+        fn writeTokens(
+            self: *Self,
+            tokens: []const Token,
+            le_codes: []hc.HuffCode,
+            oe_codes: []hc.HuffCode,
+        ) Error!void {
+            for (tokens) |t| {
+                if (t.kind == Token.Kind.literal) {
+                    try self.writeCode(le_codes[t.literal()]);
+                    continue;
+                }
+
+                // Write the length
+                const le = t.lengthEncoding();
+                try self.writeCode(le_codes[le.code]);
+                if (le.extra_bits > 0) {
+                    try self.bit_writer.writeBits(le.extra_length, le.extra_bits);
+                }
+
+                // Write the distance
+                const oe = t.distanceEncoding();
+                try self.writeCode(oe_codes[oe.code]);
+                if (oe.extra_bits > 0) {
+                    try self.bit_writer.writeBits(oe.extra_distance, oe.extra_bits);
+                }
+            }
+            // add end_block_marker at the end
+            try self.writeCode(le_codes[consts.end_block_marker]);
+        }
+
+        // Encodes a block of bytes as either Huffman encoded literals or uncompressed bytes
+        // if the results only gains very little from compression.
+        pub fn huffmanBlock(self: *Self, input: []const u8, eof: bool) Error!void {
+            // Add everything as literals
+            histogram(input, &self.literal_freq);
+
+            self.literal_freq[consts.end_block_marker] = 1;
+
+            const num_literals = consts.end_block_marker + 1;
+            self.distance_freq[0] = 1;
+            const num_distances = 1;
+
+            self.literal_encoding.generate(&self.literal_freq, 15);
+
+            // Figure out smallest code.
+            // Always use dynamic Huffman or Store
+            var num_codegens: u32 = 0;
+
+            // Generate codegen and codegenFrequencies, which indicates how to encode
+            // the literal_encoding and the distance_encoding.
+            self.generateCodegen(
+                num_literals,
+                num_distances,
+                &self.literal_encoding,
+                &self.huff_distance,
+            );
+            self.codegen_encoding.generate(self.codegen_freq[0..], 7);
+            const dynamic_size = self.dynamicSize(&self.literal_encoding, &self.huff_distance, 0);
+            const size = dynamic_size.size;
+            num_codegens = dynamic_size.num_codegens;
+
+            // Store bytes, if we don't get a reasonable improvement.
+            const stored_size_ret = storedSizeFits(input);
+            const ssize = stored_size_ret.size;
+            const storable = stored_size_ret.storable;
+
+            if (storable and ssize < (size + (size >> 4))) {
+                try self.storedBlock(input, eof);
+                return;
+            }
+
+            // Huffman.
+            try self.dynamicHeader(num_literals, num_distances, num_codegens, eof);
+            const encoding = self.literal_encoding.codes[0..257];
+
+            for (input) |t| {
+                const c = encoding[t];
+                try self.bit_writer.writeBits(c.code, c.len);
+            }
+            try self.writeCode(encoding[consts.end_block_marker]);
+        }
+
+        // histogram accumulates a histogram of b in h.
+        fn histogram(b: []const u8, h: *[286]u16) void {
+            // Clear histogram
+            for (h, 0..) |_, i| {
+                h[i] = 0;
+            }
+
+            var lh = h.*[0..256];
+            for (b) |t| {
+                lh[t] += 1;
+            }
+        }
+    };
+}
+
+// tests
+const expect = std.testing.expect;
+const fmt = std.fmt;
+const testing = std.testing;
+const ArrayList = std.ArrayList;
+
+const TestCase = @import("testdata/block_writer.zig").TestCase;
+const testCases = @import("testdata/block_writer.zig").testCases;
+
+// tests if the writeBlock encoding has changed.
+test "flate.BlockWriter write" {
+    inline for (0..testCases.len) |i| {
+        try testBlock(testCases[i], .write_block);
+    }
+}
+
+// tests if the writeBlockDynamic encoding has changed.
+test "flate.BlockWriter dynamicBlock" {
+    inline for (0..testCases.len) |i| {
+        try testBlock(testCases[i], .write_dyn_block);
+    }
+}
+
+test "flate.BlockWriter huffmanBlock" {
+    inline for (0..testCases.len) |i| {
+        try testBlock(testCases[i], .write_huffman_block);
+    }
+    try testBlock(.{
+        .tokens = &[_]Token{},
+        .input = "huffman-rand-max.input",
+        .want = "huffman-rand-max.{s}.expect",
+    }, .write_huffman_block);
+}
+
+const TestFn = enum {
+    write_block,
+    write_dyn_block, // write dynamic block
+    write_huffman_block,
+
+    fn to_s(self: TestFn) []const u8 {
+        return switch (self) {
+            .write_block => "wb",
+            .write_dyn_block => "dyn",
+            .write_huffman_block => "huff",
+        };
+    }
+
+    fn write(
+        comptime self: TestFn,
+        bw: anytype,
+        tok: []const Token,
+        input: ?[]const u8,
+        final: bool,
+    ) !void {
+        switch (self) {
+            .write_block => try bw.write(tok, final, input),
+            .write_dyn_block => try bw.dynamicBlock(tok, final, input),
+            .write_huffman_block => try bw.huffmanBlock(input.?, final),
+        }
+        try bw.flush();
+    }
+};
+
+// testBlock tests a block against its references
+//
+// size
+//  64K [file-name].input                  - input non compressed file
+// 8.1K [file-name].golden                 -
+//   78 [file-name].dyn.expect             - output with writeBlockDynamic
+//   78 [file-name].wb.expect              - output with writeBlock
+// 8.1K [file-name].huff.expect            - output with writeBlockHuff
+//   78 [file-name].dyn.expect-noinput     - output with writeBlockDynamic when input is null
+//   78 [file-name].wb.expect-noinput      - output with writeBlock when input is null
+//
+//   wb   - writeBlock
+//   dyn  - writeBlockDynamic
+//   huff - writeBlockHuff
+//
+fn testBlock(comptime tc: TestCase, comptime tfn: TestFn) !void {
+    if (tc.input.len != 0 and tc.want.len != 0) {
+        const want_name = comptime fmt.comptimePrint(tc.want, .{tfn.to_s()});
+        const input = @embedFile("testdata/block_writer/" ++ tc.input);
+        const want = @embedFile("testdata/block_writer/" ++ want_name);
+        try testWriteBlock(tfn, input, want, tc.tokens);
+    }
+
+    if (tfn == .write_huffman_block) {
+        return;
+    }
+
+    const want_name_no_input = comptime fmt.comptimePrint(tc.want_no_input, .{tfn.to_s()});
+    const want = @embedFile("testdata/block_writer/" ++ want_name_no_input);
+    try testWriteBlock(tfn, null, want, tc.tokens);
+}
+
+// Uses writer function `tfn` to write `tokens`, tests that we got `want` as output.
+fn testWriteBlock(comptime tfn: TestFn, input: ?[]const u8, want: []const u8, tokens: []const Token) !void {
+    var buf = ArrayList(u8).init(testing.allocator);
+    var bw = blockWriter(buf.writer());
+    try tfn.write(&bw, tokens, input, false);
+    var got = buf.items;
+    try testing.expectEqualSlices(u8, want, got); // expect writeBlock to yield expected result
+    try expect(got[0] & 0b0000_0001 == 0); // bfinal is not set
+    //
+    // Test if the writer produces the same output after reset.
+    buf.deinit();
+    buf = ArrayList(u8).init(testing.allocator);
+    defer buf.deinit();
+    bw.setWriter(buf.writer());
+
+    try tfn.write(&bw, tokens, input, true);
+    try bw.flush();
+    got = buf.items;
+
+    try expect(got[0] & 1 == 1); // bfinal is set
+    buf.items[0] &= 0b1111_1110; // remove bfinal bit, so we can run test slices
+    try testing.expectEqualSlices(u8, want, got); // expect writeBlock to yield expected result
+}

@@ -0,0 +1,234 @@
+/// 64K buffer of uncompressed data created in inflate (decompression). Has enough
+/// history to support writing match<length, distance>; copying length of bytes
+/// from the position distance backward from current.
+///
+/// Reads can return less than available bytes if they are spread across
+/// different circles. So reads should repeat until get required number of bytes
+/// or until returned slice is zero length.
+///
+/// Note on deflate limits:
+///  * non-compressible block is limited to 65,535 bytes.
+///  * backward pointer is limited in distance to 32K bytes and in length to 258 bytes.
+///
+/// Whole non-compressed block can be written without overlap. We always have
+/// history of up to 64K, more then 32K needed.
+///
+const std = @import("std");
+const assert = std.debug.assert;
+const testing = std.testing;
+
+const consts = @import("consts.zig").match;
+
+const mask = 0xffff; // 64K - 1
+const buffer_len = mask + 1; // 64K buffer
+
+const Self = @This();
+
+buffer: [buffer_len]u8 = undefined,
+wp: usize = 0, // write position
+rp: usize = 0, // read position
+
+fn writeAll(self: *Self, buf: []const u8) void {
+    for (buf) |c| self.write(c);
+}
+
+// Write literal.
+pub fn write(self: *Self, b: u8) void {
+    assert(self.wp - self.rp < mask);
+    self.buffer[self.wp & mask] = b;
+    self.wp += 1;
+}
+
+// Write match (back-reference to the same data slice) starting at `distance`
+// back from current write position, and `length` of bytes.
+pub fn writeMatch(self: *Self, length: u16, distance: u16) !void {
+    if (self.wp < distance or
+        length < consts.base_length or length > consts.max_length or
+        distance < consts.min_distance or distance > consts.max_distance)
+    {
+        return error.InvalidMatch;
+    }
+    assert(self.wp - self.rp < mask);
+
+    var from: usize = self.wp - distance;
+    const from_end: usize = from + length;
+    var to: usize = self.wp;
+    const to_end: usize = to + length;
+
+    self.wp += length;
+
+    // Fast path using memcpy
+    if (length <= distance and // no overlapping buffers
+        (from >> 16 == from_end >> 16) and // start and and at the same circle
+        (to >> 16 == to_end >> 16))
+    {
+        @memcpy(self.buffer[to & mask .. to_end & mask], self.buffer[from & mask .. from_end & mask]);
+        return;
+    }
+
+    // Slow byte by byte
+    while (to < to_end) {
+        self.buffer[to & mask] = self.buffer[from & mask];
+        to += 1;
+        from += 1;
+    }
+}
+
+// Returns writable part of the internal buffer of size `n` at most. Advances
+// write pointer, assumes that returned buffer will be filled with data.
+pub fn getWritable(self: *Self, n: usize) []u8 {
+    const wp = self.wp & mask;
+    const len = @min(n, buffer_len - wp);
+    self.wp += len;
+    return self.buffer[wp .. wp + len];
+}
+
+// Read available data. Can return part of the available data if it is
+// spread across two circles. So read until this returns zero length.
+pub fn read(self: *Self) []const u8 {
+    return self.readAtMost(buffer_len);
+}
+
+// Read part of available data. Can return less than max even if there are
+// more than max decoded data.
+pub fn readAtMost(self: *Self, limit: usize) []const u8 {
+    const rb = self.readBlock(if (limit == 0) buffer_len else limit);
+    defer self.rp += rb.len;
+    return self.buffer[rb.head..rb.tail];
+}
+
+const ReadBlock = struct {
+    head: usize,
+    tail: usize,
+    len: usize,
+};
+
+// Returns position of continous read block data.
+fn readBlock(self: *Self, max: usize) ReadBlock {
+    const r = self.rp & mask;
+    const w = self.wp & mask;
+    const n = @min(
+        max,
+        if (w >= r) w - r else buffer_len - r,
+    );
+    return .{
+        .head = r,
+        .tail = r + n,
+        .len = n,
+    };
+}
+
+// Number of free bytes for write.
+pub fn free(self: *Self) usize {
+    return buffer_len - (self.wp - self.rp);
+}
+
+// Full if largest match can't fit. 258 is largest match length. That much bytes
+// can be produced in single decode step.
+pub fn full(self: *Self) bool {
+    return self.free() < 258 + 1;
+}
+
+// example from: https://youtu.be/SJPvNi4HrWQ?t=3558
+test "flate.CircularBuffer writeMatch" {
+    var cb: Self = .{};
+
+    cb.writeAll("a salad; ");
+    try cb.writeMatch(5, 9);
+    try cb.writeMatch(3, 3);
+
+    try testing.expectEqualStrings("a salad; a salsal", cb.read());
+}
+
+test "flate.CircularBuffer writeMatch overlap" {
+    var cb: Self = .{};
+
+    cb.writeAll("a b c ");
+    try cb.writeMatch(8, 4);
+    cb.write('d');
+
+    try testing.expectEqualStrings("a b c b c b c d", cb.read());
+}
+
+test "flate.CircularBuffer readAtMost" {
+    var cb: Self = .{};
+
+    cb.writeAll("0123456789");
+    try cb.writeMatch(50, 10);
+
+    try testing.expectEqualStrings("0123456789" ** 6, cb.buffer[cb.rp..cb.wp]);
+    for (0..6) |i| {
+        try testing.expectEqual(i * 10, cb.rp);
+        try testing.expectEqualStrings("0123456789", cb.readAtMost(10));
+    }
+    try testing.expectEqualStrings("", cb.readAtMost(10));
+    try testing.expectEqualStrings("", cb.read());
+}
+
+test "flate.CircularBuffer" {
+    var cb: Self = .{};
+
+    const data = "0123456789abcdef" ** (1024 / 16);
+    cb.writeAll(data);
+    try testing.expectEqual(@as(usize, 0), cb.rp);
+    try testing.expectEqual(@as(usize, 1024), cb.wp);
+    try testing.expectEqual(@as(usize, 1024 * 63), cb.free());
+
+    for (0..62 * 4) |_|
+        try cb.writeMatch(256, 1024); // write 62K
+
+    try testing.expectEqual(@as(usize, 0), cb.rp);
+    try testing.expectEqual(@as(usize, 63 * 1024), cb.wp);
+    try testing.expectEqual(@as(usize, 1024), cb.free());
+
+    cb.writeAll(data[0..200]);
+    _ = cb.readAtMost(1024); // make some space
+    cb.writeAll(data); // overflows write position
+    try testing.expectEqual(@as(usize, 200 + 65536), cb.wp);
+    try testing.expectEqual(@as(usize, 1024), cb.rp);
+    try testing.expectEqual(@as(usize, 1024 - 200), cb.free());
+
+    const rb = cb.readBlock(Self.buffer_len);
+    try testing.expectEqual(@as(usize, 65536 - 1024), rb.len);
+    try testing.expectEqual(@as(usize, 1024), rb.head);
+    try testing.expectEqual(@as(usize, 65536), rb.tail);
+
+    try testing.expectEqual(@as(usize, 65536 - 1024), cb.read().len); // read to the end of the buffer
+    try testing.expectEqual(@as(usize, 200 + 65536), cb.wp);
+    try testing.expectEqual(@as(usize, 65536), cb.rp);
+    try testing.expectEqual(@as(usize, 65536 - 200), cb.free());
+
+    try testing.expectEqual(@as(usize, 200), cb.read().len); // read the rest
+}
+
+test "flate.CircularBuffer write overlap" {
+    var cb: Self = .{};
+    cb.wp = cb.buffer.len - 15;
+    cb.rp = cb.wp;
+
+    cb.writeAll("0123456789");
+    cb.writeAll("abcdefghij");
+
+    try testing.expectEqual(cb.buffer.len + 5, cb.wp);
+    try testing.expectEqual(cb.buffer.len - 15, cb.rp);
+
+    try testing.expectEqualStrings("0123456789abcde", cb.read());
+    try testing.expectEqualStrings("fghij", cb.read());
+
+    try testing.expect(cb.wp == cb.rp);
+}
+
+test "flate.CircularBuffer writeMatch/read overlap" {
+    var cb: Self = .{};
+    cb.wp = cb.buffer.len - 15;
+    cb.rp = cb.wp;
+
+    cb.writeAll("0123456789");
+    try cb.writeMatch(15, 5);
+
+    try testing.expectEqualStrings("012345678956789", cb.read());
+    try testing.expectEqualStrings("5678956789", cb.read());
+
+    try cb.writeMatch(20, 25);
+    try testing.expectEqualStrings("01234567895678956789", cb.read());
+}

@@ -0,0 +1,49 @@
+pub const deflate = struct {
+    // Number of tokens to accumlate in deflate before starting block encoding.
+    //
+    // In zlib this depends on memlevel: 6 + memlevel, where default memlevel is
+    // 8 and max 9 that gives 14 or 15 bits.
+    pub const tokens = 1 << 15;
+};
+
+pub const match = struct {
+    pub const base_length = 3; // smallest match length per the RFC section 3.2.5
+    pub const min_length = 4; // min length used in this algorithm
+    pub const max_length = 258;
+
+    pub const min_distance = 1;
+    pub const max_distance = 32768;
+};
+
+pub const history = struct {
+    pub const len = match.max_distance;
+};
+
+pub const lookup = struct {
+    pub const bits = 15;
+    pub const len = 1 << bits;
+    pub const shift = 32 - bits;
+};
+
+pub const huffman = struct {
+    // The odd order in which the codegen code sizes are written.
+    pub const codegen_order = [_]u32{ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
+    // The number of codegen codes.
+    pub const codegen_code_count = 19;
+
+    // The largest distance code.
+    pub const distance_code_count = 30;
+
+    // Maximum number of literals.
+    pub const max_num_lit = 286;
+
+    // Max number of frequencies used for a Huffman Code
+    // Possible lengths are codegen_code_count (19), distance_code_count (30) and max_num_lit (286).
+    // The largest of these is max_num_lit.
+    pub const max_num_frequencies = max_num_lit;
+
+    // Biggest block size for uncompressed block.
+    pub const max_store_block_size = 65535;
+    // The special code used to mark the end of a block.
+    pub const end_block_marker = 256;
+};

@@ -0,0 +1,205 @@
+const std = @import("std");
+
+/// Container of the deflate bit stream body. Container adds header before
+/// deflate bit stream and footer after. It can bi gzip, zlib or raw (no header,
+/// no footer, raw bit stream).
+///
+/// Zlib format is defined in rfc 1950. Header has 2 bytes and footer 4 bytes
+/// addler 32 checksum.
+///
+/// Gzip format is defined in rfc 1952. Header has 10+ bytes and footer 4 bytes
+/// crc32 checksum and 4 bytes of uncompressed data length.
+///
+///
+/// rfc 1950: https://datatracker.ietf.org/doc/html/rfc1950#page-4
+/// rfc 1952: https://datatracker.ietf.org/doc/html/rfc1952#page-5
+///
+pub const Container = enum {
+    raw, // no header or footer
+    gzip, // gzip header and footer
+    zlib, // zlib header and footer
+
+    pub fn size(w: Container) usize {
+        return headerSize(w) + footerSize(w);
+    }
+
+    pub fn headerSize(w: Container) usize {
+        return switch (w) {
+            .gzip => 10,
+            .zlib => 2,
+            .raw => 0,
+        };
+    }
+
+    pub fn footerSize(w: Container) usize {
+        return switch (w) {
+            .gzip => 8,
+            .zlib => 4,
+            .raw => 0,
+        };
+    }
+
+    pub const list = [_]Container{ .raw, .gzip, .zlib };
+
+    pub const Error = error{
+        BadGzipHeader,
+        BadZlibHeader,
+        WrongGzipChecksum,
+        WrongGzipSize,
+        WrongZlibChecksum,
+    };
+
+    pub fn writeHeader(comptime wrap: Container, writer: anytype) !void {
+        switch (wrap) {
+            .gzip => {
+                // GZIP 10 byte header (https://datatracker.ietf.org/doc/html/rfc1952#page-5):
+                //  - ID1 (IDentification 1), always 0x1f
+                //  - ID2 (IDentification 2), always 0x8b
+                //  - CM (Compression Method), always 8 = deflate
+                //  - FLG (Flags), all set to 0
+                //  - 4 bytes, MTIME (Modification time), not used, all set to zero
+                //  - XFL (eXtra FLags), all set to zero
+                //  - OS (Operating System), 03 = Unix
+                const gzipHeader = [_]u8{ 0x1f, 0x8b, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x03 };
+                try writer.writeAll(&gzipHeader);
+            },
+            .zlib => {
+                // ZLIB has a two-byte header (https://datatracker.ietf.org/doc/html/rfc1950#page-4):
+                // 1st byte:
+                //  - First four bits is the CINFO (compression info), which is 7 for the default deflate window size.
+                //  - The next four bits is the CM (compression method), which is 8 for deflate.
+                // 2nd byte:
+                //  - Two bits is the FLEVEL (compression level). Values are: 0=fastest, 1=fast, 2=default, 3=best.
+                //  - The next bit, FDICT, is set if a dictionary is given.
+                //  - The final five FCHECK bits form a mod-31 checksum.
+                //
+                // CINFO = 7, CM = 8, FLEVEL = 0b10, FDICT = 0, FCHECK = 0b11100
+                const zlibHeader = [_]u8{ 0x78, 0b10_0_11100 };
+                try writer.writeAll(&zlibHeader);
+            },
+            .raw => {},
+        }
+    }
+
+    pub fn writeFooter(comptime wrap: Container, hasher: *Hasher(wrap), writer: anytype) !void {
+        var bits: [4]u8 = undefined;
+        switch (wrap) {
+            .gzip => {
+                // GZIP 8 bytes footer
+                //  - 4 bytes, CRC32 (CRC-32)
+                //  - 4 bytes, ISIZE (Input SIZE) - size of the original (uncompressed) input data modulo 2^32
+                std.mem.writeInt(u32, &bits, hasher.chksum(), .little);
+                try writer.writeAll(&bits);
+
+                std.mem.writeInt(u32, &bits, hasher.bytesRead(), .little);
+                try writer.writeAll(&bits);
+            },
+            .zlib => {
+                // ZLIB (RFC 1950) is big-endian, unlike GZIP (RFC 1952).
+                // 4 bytes of ADLER32 (Adler-32 checksum)
+                // Checksum value of the uncompressed data (excluding any
+                // dictionary data) computed according to Adler-32
+                // algorithm.
+                std.mem.writeInt(u32, &bits, hasher.chksum(), .big);
+                try writer.writeAll(&bits);
+            },
+            .raw => {},
+        }
+    }
+
+    pub fn parseHeader(comptime wrap: Container, reader: anytype) !void {
+        switch (wrap) {
+            .gzip => try parseGzipHeader(reader),
+            .zlib => try parseZlibHeader(reader),
+            .raw => {},
+        }
+    }
+
+    fn parseGzipHeader(reader: anytype) !void {
+        const magic1 = try reader.read(u8);
+        const magic2 = try reader.read(u8);
+        const method = try reader.read(u8);
+        const flags = try reader.read(u8);
+        try reader.skipBytes(6); // mtime(4), xflags, os
+        if (magic1 != 0x1f or magic2 != 0x8b or method != 0x08)
+            return error.BadGzipHeader;
+        // Flags description: https://www.rfc-editor.org/rfc/rfc1952.html#page-5
+        if (flags != 0) {
+            if (flags & 0b0000_0100 != 0) { // FEXTRA
+                const extra_len = try reader.read(u16);
+                try reader.skipBytes(extra_len);
+            }
+            if (flags & 0b0000_1000 != 0) { // FNAME
+                try reader.skipStringZ();
+            }
+            if (flags & 0b0001_0000 != 0) { // FCOMMENT
+                try reader.skipStringZ();
+            }
+            if (flags & 0b0000_0010 != 0) { // FHCRC
+                try reader.skipBytes(2);
+            }
+        }
+    }
+
+    fn parseZlibHeader(reader: anytype) !void {
+        const cinfo_cm = try reader.read(u8);
+        _ = try reader.read(u8);
+        if (cinfo_cm != 0x78) {
+            return error.BadZlibHeader;
+        }
+    }
+
+    pub fn parseFooter(comptime wrap: Container, hasher: *Hasher(wrap), reader: anytype) !void {
+        switch (wrap) {
+            .gzip => {
+                if (try reader.read(u32) != hasher.chksum()) return error.WrongGzipChecksum;
+                if (try reader.read(u32) != hasher.bytesRead()) return error.WrongGzipSize;
+            },
+            .zlib => {
+                const chksum: u32 = @byteSwap(hasher.chksum());
+                if (try reader.read(u32) != chksum) return error.WrongZlibChecksum;
+            },
+            .raw => {},
+        }
+    }
+
+    pub fn Hasher(comptime wrap: Container) type {
+        const HasherType = switch (wrap) {
+            .gzip => std.hash.Crc32,
+            .zlib => std.hash.Adler32,
+            .raw => struct {
+                pub fn init() @This() {
+                    return .{};
+                }
+            },
+        };
+
+        return struct {
+            hasher: HasherType = HasherType.init(),
+            bytes: usize = 0,
+
+            const Self = @This();
+
+            pub fn update(self: *Self, buf: []const u8) void {
+                switch (wrap) {
+                    .raw => {},
+                    else => {
+                        self.hasher.update(buf);
+                        self.bytes += buf.len;
+                    },
+                }
+            }
+
+            pub fn chksum(self: *Self) u32 {
+                switch (wrap) {
+                    .raw => return 0,
+                    else => return self.hasher.final(),
+                }
+            }
+
+            pub fn bytesRead(self: *Self) u32 {
+                return @truncate(self.bytes);
+            }
+        };
+    }
+};