Only performs huffman compression on data, does no matching.
pub const Huffman = structpub const Huffman = struct {
/// After `finish` is called, all vtable calls with result in `error.WriteFailed`.
writer: Writer,
bit_writer: BitWriter,
hasher: flate.Container.Hasher,
const max_tokens: u16 = 65535 - 1; // one is reserved for EOF
/// While there is no minimum buffer size, it is recommended
/// to be at least `flate.max_window_len` to improve compression.
///
/// It is asserted `output` has a capacity of at least 8 bytes.
pub fn init(output: *Writer, buffer: []u8, container: flate.Container) Writer.Error!Huffman {
assert(output.buffer.len > 8);
try output.writeAll(container.header());
return .{
.writer = .{
.buffer = buffer,
.vtable = &.{
.drain = Huffman.drain,
.flush = Huffman.flush,
.rebase = Huffman.rebase,
},
},
.bit_writer = .init(output),
.hasher = .init(container),
};
}
fn drain(w: *Writer, data: []const []const u8, splat: usize) Writer.Error!usize {
const h: *Huffman = @fieldParentPtr("writer", w);
const min_block = @min(w.buffer.len, max_tokens);
const pattern = data[data.len - 1];
const data_bytes = Writer.countSplat(data, splat);
const total_bytes = w.end + data_bytes;
var rem_bytes = total_bytes;
var rem_splat = splat;
var rem_data = data;
var rem_data_elem: []const u8 = w.buffered();
assert(rem_bytes > min_block);
while (rem_bytes > min_block) { // not >= to allow `min_block` blocks to be marked as final
// also, it handles the case of `min_block` being zero (no buffer)
const block_size: u16 = @min(rem_bytes, max_tokens);
rem_bytes -= block_size;
// Count frequencies
comptime assert(max_tokens != 65535);
var freqs: [257]u16 = @splat(0);
freqs[256] = 1;
const start_splat = rem_splat;
const start_data = rem_data;
const start_data_elem = rem_data_elem;
var block_limit: Io.Limit = .limited(block_size);
while (true) {
const bytes = block_limit.sliceConst(rem_data_elem);
const is_pattern = rem_splat != splat and bytes.len == pattern.len;
const mul = if (!is_pattern) 1 else @backingInt(block_limit) / pattern.len;
assert(mul != 0);
if (is_pattern) assert(mul <= rem_splat + 1); // one more for `rem_data`
for (bytes) |b| freqs[b] += @intCast(mul);
rem_data_elem = rem_data_elem[bytes.len..];
block_limit = block_limit.subtract(bytes.len * mul).?;
if (rem_data_elem.len == 0) {
rem_data_elem = rem_data[0];
if (rem_data.len != 1) {
rem_data = rem_data[1..];
} else if (rem_splat >= mul) {
// if the counter was not the pattern, `mul` is always one, otherwise,
// `mul` contains `rem_data`, however one more needs subtracted anyways
// since the next pattern is also being taken.
rem_splat -= mul;
} else {
// All of `data` has been consumed.
assert(block_limit == .nothing);
assert(rem_bytes == 0);
// Since `rem_bytes` and `block_limit` are zero, these won't be used.
rem_data = undefined;
rem_data_elem = undefined;
rem_splat = undefined;
}
}
if (block_limit == .nothing) break;
}
// Output block
rem_splat = start_splat;
rem_data = start_data;
rem_data_elem = start_data_elem;
block_limit = .limited(block_size);
var codes_buf: CodesBuf = .init;
if (try h.outputHeader(&freqs, &codes_buf, block_size, false)) |table| {
while (true) {
const bytes = block_limit.sliceConst(rem_data_elem);
rem_data_elem = rem_data_elem[bytes.len..];
block_limit = block_limit.subtract(bytes.len).?;
h.hasher.update(bytes);
for (bytes) |b| {
try h.bit_writer.write(table.codes[b], table.bits[b]);
}
if (rem_data_elem.len == 0) {
rem_data_elem = rem_data[0];
if (rem_data.len != 1) {
rem_data = rem_data[1..];
} else if (rem_splat != 0) {
rem_splat -= 1;
} else {
// All of `data` has been consumed.
assert(block_limit == .nothing);
assert(rem_bytes == 0);
// Since `rem_bytes` and `block_limit` are zero, these won't be used.
rem_data = undefined;
rem_data_elem = undefined;
rem_splat = undefined;
}
}
if (block_limit == .nothing) break;
}
try h.bit_writer.write(table.codes[256], table.bits[256]);
} else while (true) {
// Store block
// Write data that is not a full vector element
const in_pattern = rem_splat != splat;
const vec_elem_i, const in_data =
@subWithOverflow(data.len - (rem_data.len - @intFromBool(in_pattern)), 1);
const is_elem = in_data == 0 and data[vec_elem_i].len == rem_data_elem.len;
if (!is_elem or rem_data_elem.len > @backingInt(block_limit)) {
block_limit = block_limit.subtract(rem_data_elem.len) orelse {
try h.bit_writer.output.writeAll(rem_data_elem[0..@backingInt(block_limit)]);
h.hasher.update(rem_data_elem[0..@backingInt(block_limit)]);
rem_data_elem = rem_data_elem[@backingInt(block_limit)..];
assert(rem_data_elem.len != 0);
break;
};
try h.bit_writer.output.writeAll(rem_data_elem);
h.hasher.update(rem_data_elem);
} else {
// Put `rem_data_elem` back in `rem_data`
if (!in_pattern) {
rem_data = data[vec_elem_i..];
} else {
rem_splat += 1;
}
}
rem_data_elem = undefined; // it is always updated below
// Send through as much of the original vector as possible
var vec_n: usize = 0;
var vlimit = block_limit;
const vec_splat = while (rem_data[vec_n..].len != 1) {
vlimit = vlimit.subtract(rem_data[vec_n].len) orelse break 1;
vec_n += 1;
} else vec_splat: {
// For `pattern.len == 0`, the value of `vec_splat` does not matter.
const vec_splat = @backingInt(vlimit) / @max(1, pattern.len);
if (pattern.len != 0) assert(vec_splat <= rem_splat + 1);
vlimit = vlimit.subtract(pattern.len * vec_splat).?;
vec_n += 1;
break :vec_splat vec_splat;
};
const n = if (vec_n != 0) n: {
assert(@backingInt(block_limit) - @backingInt(vlimit) ==
Writer.countSplat(rem_data[0..vec_n], vec_splat));
break :n try h.bit_writer.output.writeSplat(rem_data[0..vec_n], vec_splat);
} else 0; // Still go into the case below to advance the vector
block_limit = block_limit.subtract(n).?;
var consumed: Io.Limit = .limited(n);
while (rem_data.len != 1) {
const elem = rem_data[0];
rem_data = rem_data[1..];
consumed = consumed.subtract(elem.len) orelse {
h.hasher.update(elem[0..@backingInt(consumed)]);
rem_data_elem = elem[@backingInt(consumed)..];
break;
};
h.hasher.update(elem);
} else {
if (pattern.len == 0) {
// All of `data` has been consumed. However, the general
// case below does not work since it divides by zero.
assert(consumed == .nothing);
assert(block_limit == .nothing);
assert(rem_bytes == 0);
// Since `rem_bytes` and `block_limit` are zero, these won't be used.
rem_splat = undefined;
rem_data = undefined;
rem_data_elem = undefined;
break;
}
const splatted = @backingInt(consumed) / pattern.len;
const partial = @backingInt(consumed) % pattern.len;
for (0..splatted) |_| h.hasher.update(pattern);
h.hasher.update(pattern[0..partial]);
const taken_splat = splatted + 1;
if (rem_splat >= taken_splat) {
rem_splat -= taken_splat;
rem_data_elem = pattern[partial..];
} else {
// All of `data` has been consumed.
assert(partial == 0);
assert(block_limit == .nothing);
assert(rem_bytes == 0);
// Since `rem_bytes` and `block_limit` are zero, these won't be used.
rem_data = undefined;
rem_data_elem = undefined;
rem_splat = undefined;
}
}
if (block_limit == .nothing) break;
}
}
if (rem_bytes > data_bytes) {
assert(rem_bytes - data_bytes == rem_data_elem.len);
assert(&rem_data_elem[0] == &w.buffer[total_bytes - rem_bytes]);
}
return w.consume(total_bytes - rem_bytes);
}
fn flush(w: *Writer) Writer.Error!void {
errdefer w.* = .failing;
const h: *Huffman = @fieldParentPtr("writer", w);
try Huffman.rebaseInner(w, 0, w.buffer.len, false);
try h.bit_writer.byteAlignBlocks();
}
pub fn finish(h: *Huffman) Writer.Error!void {
defer h.writer = .failing;
try Huffman.rebaseInner(&h.writer, 0, h.writer.buffer.len, true);
try h.bit_writer.output.rebase(0, 1);
h.bit_writer.byteAlign();
try h.hasher.writeFooter(h.bit_writer.output);
}
fn rebase(w: *Writer, preserve: usize, capacity: usize) Writer.Error!void {
errdefer w.* = .failing;
try Huffman.rebaseInner(w, preserve, capacity, false);
}
fn rebaseInner(w: *Writer, preserve: usize, capacity: usize, eos: bool) Writer.Error!void {
const h: *Huffman = @fieldParentPtr("writer", w);
assert(preserve + capacity <= w.buffer.len);
if (eos) assert(capacity == w.buffer.len);
const preserved = @min(w.end, preserve);
var remaining = w.buffer[0 .. w.end - preserved];
while (remaining.len > max_tokens) { // not >= so there is always a block down below
const bytes = remaining[0..max_tokens];
remaining = remaining[max_tokens..];
try h.outputBytes(bytes, false);
}
// eos check required for empty block
if (w.buffer.len - (remaining.len + preserved) < capacity or eos) {
const bytes = remaining;
remaining = &.{};
try h.outputBytes(bytes, eos);
}
_ = w.consume(w.end - preserved - remaining.len);
}
fn outputBytes(h: *Huffman, bytes: []const u8, eos: bool) Writer.Error!void {
comptime assert(max_tokens != 65535);
assert(bytes.len <= max_tokens);
var freqs: [257]u16 = @splat(0);
freqs[256] = 1;
for (bytes) |b| freqs[b] += 1;
h.hasher.update(bytes);
var codes_buf: CodesBuf = .init;
if (try h.outputHeader(&freqs, &codes_buf, @intCast(bytes.len), eos)) |table| {
for (bytes) |b| {
try h.bit_writer.write(table.codes[b], table.bits[b]);
}
try h.bit_writer.write(table.codes[256], table.bits[256]);
} else {
try h.bit_writer.output.writeAll(bytes);
}
}
const CodesBuf = struct {
dyn_codes: [258]u16,
dyn_bits: [258]u4,
pub const init: CodesBuf = .{
.dyn_codes = @as([257]u16, undefined) ++ .{0},
.dyn_bits = @as([257]u4, @splat(0)) ++ .{1},
};
};
/// Returns null if the block is stored.
fn outputHeader(
h: *Huffman,
freqs: *const [257]u16,
buf: *CodesBuf,
bytes: u16,
eos: bool,
) Writer.Error!?struct {
codes: *const [257]u16,
bits: *const [257]u4,
} {
assert(freqs[256] == 1);
const dyn_codes_bitsize, _ = huffman.build(
freqs,
buf.dyn_codes[0..257],
buf.dyn_bits[0..257],
15,
true,
);
var clen_values: [258]u8 = undefined;
var clen_extra: [258]u8 = undefined;
var clen_freqs: [19]u16 = @splat(0);
const clen_len, const clen_extra_bitsize = buildClen(
&buf.dyn_bits,
&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_codes_bitsize;
const fixed_bitsize = n: {
const freq7 = 1; // eos
var freq9: u16 = 0;
for (freqs[144..256]) |f| freq9 += f;
const freq8: u16 = bytes - freq9;
break :n @as(u32, freq7) * 7 + @as(u32, freq8) * 8 + @as(u32, freq9) * 9;
};
const stored_bitsize = n: {
const stored_align_bits = -%(h.bit_writer.buffered_n +% 3);
break :n stored_align_bits + @as(u32, 32) + @as(u32, bytes) * 8;
};
if (stored_bitsize <= @min(dynamic_bitsize, fixed_bitsize)) {
try h.bit_writer.write(BlockHeader.int(.{ .kind = .stored, .final = eos }), 3);
try h.bit_writer.output.rebase(0, 5);
h.bit_writer.byteAlign();
h.bit_writer.output.writeInt(u16, bytes, .little) catch unreachable;
h.bit_writer.output.writeInt(u16, ~bytes, .little) catch unreachable;
return null;
}
if (fixed_bitsize <= dynamic_bitsize) {
try h.bit_writer.write(BlockHeader.int(.{ .final = eos, .kind = .fixed }), 3);
return .{
.codes = token.fixed_lit_codes[0..257],
.bits = token.fixed_lit_bits[0..257],
};
} else {
try h.bit_writer.write(BlockHeader.Dynamic.int(.{
.regular = .{ .final = eos, .kind = .dynamic },
.hlit = 0,
.hdist = 0,
.hclen = hclen,
}), 17);
try h.bit_writer.writeClen(
hclen,
clen_values[0..clen_len],
clen_extra[0..clen_len],
clen_codes,
clen_bits,
);
return .{ .codes = buf.dyn_codes[0..257], .bits = buf.dyn_bits[0..257] };
}
}
}