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;
}
