writeBlock

fn writeBlock(c: *Compress, eos: bool) Writer.Error!void

File

Code

fn writeBlock(c: *Compress, eos: bool) Writer.Error!void {
    const toks = &c.buffered_tokens;
    assert(toks.lit_freqs[256] == 0);
    toks.lit_freqs[256] = 1;

    var dyn_codes_buf: [286 + 30]u16 = undefined;
    var dyn_bits_buf: [286 + 30]u4 = @splat(0);

    const dyn_lit_codes_bitsize, const dyn_last_lit = huffman.build(
        &toks.lit_freqs,
        dyn_codes_buf[0..286],
        dyn_bits_buf[0..286],
        15,
        true,
    );
    const dyn_lit_len = @max(257, dyn_last_lit + 1);

    const dyn_dist_codes_bitsize, const dyn_last_dist = huffman.build(
        &toks.dist_freqs,
        dyn_codes_buf[dyn_lit_len..][0..30],
        dyn_bits_buf[dyn_lit_len..][0..30],
        15,
        true,
    );
    const dyn_dist_len = @max(1, dyn_last_dist + 1);

    var clen_values: [288 + 30]u8 = undefined;
    var clen_extra: [288 + 30]u8 = undefined;
    var clen_freqs: [19]u16 = @splat(0);
    const clen_len, const clen_extra_bitsize = buildClen(
        dyn_bits_buf[0 .. dyn_lit_len + dyn_dist_len],
        &clen_values,
        &clen_extra,
        &clen_freqs,
    );

    var clen_codes: [19]u16 = undefined;
    var clen_bits: [19]u4 = @splat(0);
    const clen_codes_bitsize, _ = huffman.build(
        &clen_freqs,
        &clen_codes,
        &clen_bits,
        7,
        false,
    );
    const hclen = clenHlen(clen_freqs);

    const dynamic_bitsize = @as(u32, 14) +
        (4 + @as(u6, hclen)) * 3 + clen_codes_bitsize + clen_extra_bitsize +
        dyn_lit_codes_bitsize + dyn_dist_codes_bitsize;
    const fixed_bitsize = n: {
        const freq7 = 1; // eos
        var freq8: u16 = 0;
        var freq9: u16 = 0;
        var freq12: u16 = 0; // 7 + 5 - match freqs always have corresponding 5-bit dist freq
        var freq13: u16 = 0; // 8 + 5
        for (toks.lit_freqs[0..144]) |f| freq8 += f;
        for (toks.lit_freqs[144..256]) |f| freq9 += f;
        assert(toks.lit_freqs[256] == 1);
        for (toks.lit_freqs[257..280]) |f| freq12 += f;
        for (toks.lit_freqs[280..286]) |f| freq13 += f;
        break :n @as(u32, freq7) * 7 +
            @as(u32, freq8) * 8 + @as(u32, freq9) * 9 +
            @as(u32, freq12) * 12 + @as(u32, freq13) * 13;
    };

    stored: {
        for (toks.dist_freqs) |n| if (n != 0) break :stored;
        // No need to check len frequencies since they each have a corresponding dist frequency
        assert(for (toks.lit_freqs[257..]) |f| (if (f != 0) break false) else true);

        // No matches. If the stored size is smaller than the huffman-encoded version, it will be
        // outputed in a store block. This is not done with matches since the original input would
        // need to be stored since the window may slid, and it may also exceed 65535 bytes. This
        // should be OK since most inputs with matches should be more compressable anyways.
        const stored_align_bits = -%(c.bit_writer.buffered_n +% 3);
        const stored_bitsize = stored_align_bits + @as(u32, 32) + @as(u32, toks.n) * 8;
        if (@min(dynamic_bitsize, fixed_bitsize) < stored_bitsize) break :stored;

        try c.bit_writer.write(BlockHeader.int(.{ .kind = .stored, .final = eos }), 3);
        try c.bit_writer.output.rebase(0, 5);
        c.bit_writer.byteAlign();
        c.bit_writer.output.writeInt(u16, c.buffered_tokens.n, .little) catch unreachable;
        c.bit_writer.output.writeInt(u16, ~c.buffered_tokens.n, .little) catch unreachable;

        // Relatively small buffer since regular draining will
        // always consume slightly less than 2 << 15 bytes.
        var vec_buf: [4][]const u8 = undefined;
        var vec_n: usize = 0;
        var i: usize = 0;

        assert(c.buffered_tokens.pos != 0);
        while (i != c.buffered_tokens.pos) {
            const h: TokenBufferEntryHeader = @bitCast(toks.list[i..][0..2].*);
            assert(h.kind == .bytes);

            i += 2;
            vec_buf[vec_n] = toks.list[i..][0..h.data];
            i += h.data;

            vec_n += 1;
            if (i == c.buffered_tokens.pos or vec_n == vec_buf.len) {
                try c.bit_writer.output.writeVecAll(vec_buf[0..vec_n]);
                vec_n = 0;
            }
        }

        toks.* = .empty;
        return;
    }

    const lit_codes, const lit_bits, const dist_codes, const dist_bits =
        if (dynamic_bitsize < fixed_bitsize) codes: {
            try c.bit_writer.write(BlockHeader.Dynamic.int(.{
                .regular = .{ .final = eos, .kind = .dynamic },
                .hlit = @intCast(dyn_lit_len - 257),
                .hdist = @intCast(dyn_dist_len - 1),
                .hclen = hclen,
            }), 17);
            try c.bit_writer.writeClen(
                hclen,
                clen_values[0..clen_len],
                clen_extra[0..clen_len],
                clen_codes,
                clen_bits,
            );
            break :codes .{
                dyn_codes_buf[0..dyn_lit_len],
                dyn_bits_buf[0..dyn_lit_len],
                dyn_codes_buf[dyn_lit_len..][0..dyn_dist_len],
                dyn_bits_buf[dyn_lit_len..][0..dyn_dist_len],
            };
        } else codes: {
            try c.bit_writer.write(BlockHeader.int(.{ .final = eos, .kind = .fixed }), 3);
            break :codes .{
                &token.fixed_lit_codes,
                &token.fixed_lit_bits,
                &token.fixed_dist_codes,
                &token.fixed_dist_bits,
            };
        };

    var i: usize = 0;
    while (i != toks.pos) {
        const h: TokenBufferEntryHeader = @bitCast(toks.list[i..][0..2].*);
        i += 2;
        if (h.kind == .bytes) {
            for (toks.list[i..][0..h.data]) |b| {
                try c.bit_writer.write(lit_codes[b], lit_bits[b]);
            }
            i += h.data;
        } else {
            const dist = h.data;
            const len = toks.list[i];
            i += 1;
            const dist_code = token.DistCode.fromVal(dist);
            const len_code = token.LenCode.fromVal(len);
            const dist_val = dist_code.toInt();
            const lit_val = @as(u16, 257) + len_code.toInt();

            var out: u48 = lit_codes[lit_val];
            var out_bits: u6 = lit_bits[lit_val];
            out |= @shlExact(@as(u20, len - len_code.base()), @intCast(out_bits));
            out_bits += len_code.extraBits();

            out |= @shlExact(@as(u35, dist_codes[dist_val]), out_bits);
            out_bits += dist_bits[dist_val];
            out |= @shlExact(@as(u48, dist - dist_code.base()), out_bits);
            out_bits += dist_code.extraBits();

            try c.bit_writer.write(out, out_bits);
        }
    }
    try c.bit_writer.write(lit_codes[256], lit_bits[256]);

    toks.* = .empty;
}