// Huffman literal codes (RFC 8878 section 4.2): the tree description and
// decoding streams.
///|
/// The longest Huffman code.
const MAX_HUF_BITS : Int32 = 11
///|
/// A Huffman decoding table indexed by the next `max_bits` bits: each entry
/// gives the symbol and its code length.
priv struct Huffman {
symbol : FixedArray[Byte]
nbits : FixedArray[Byte]
mut max_bits : Int32
// The symbols the last description gave weights to, the implied last one
// included: `weights[0:symbols]` once a table is built.
mut symbols : Int32
// Scratch: the weights of a description, how many of each weight there
// are, and where the entries of each weight go.
weights : FixedArray[Int32]
weight_count : FixedArray[Int32]
entry_start : FixedArray[Int32]
weight_table : Fse
}
///|
fn Huffman::new() -> Huffman {
{
symbol: FixedArray::make(1 << MAX_HUF_BITS, b'\x00'),
nbits: FixedArray::make(1 << MAX_HUF_BITS, b'\x00'),
max_bits: 0,
symbols: 0,
weights: FixedArray::make(256, 0),
weight_count: FixedArray::make(MAX_HUF_BITS + 1, 0),
entry_start: FixedArray::make(MAX_HUF_BITS + 2, 0),
weight_table: Fse::new(6),
}
}
///|
/// The table's and its scratch space's bytes.
fn Huffman::memory_usage(self : Huffman) -> Int32 {
self.symbol.length() +
self.nbits.length() +
4 *
(
self.weights.length() +
self.weight_count.length() +
self.entry_start.length()
) +
self.weight_table.memory_usage()
}
///|
/// Takes `other`'s table: its entries and code length.
fn Huffman::copy_from(self : Huffman, other : Huffman) -> Unit {
FixedArray::unsafe_blit(self.symbol, 0, other.symbol, 0, self.symbol.length())
FixedArray::unsafe_blit(self.nbits, 0, other.nbits, 0, self.nbits.length())
self.max_bits = other.max_bits
}
///|
/// Reads a Huffman tree description from `data[start:end]` and builds the
/// table. Returns the bytes the description used.
fn Huffman::read(
self : Huffman,
data : FixedArray[Byte],
start : Int32,
end : Int32,
scratch : FseScratch,
) -> Int32 raise Stop {
if start >= end {
raise corrupt("a Huffman tree description runs past its section")
}
let header = data[start].to_int()
let weights = self.weights
let (count, used) = if header >= 128 {
// Direct representation: 4-bit weights, two to a byte.
let count = header - 127
let bytes = (count + 1) / 2
if start + 1 + bytes > end {
raise corrupt("a Huffman tree description runs past its section")
}
for i in 0..> 4 } else { b & 15 }
}
(count, 1 + bytes)
} else {
// FSE-compressed weights: two interleaved states.
let size = header
if size == 0 || start + 1 + size > end {
raise corrupt("a Huffman tree description runs past its section")
}
let stream_end = start + 1 + size
let table = self.weight_table
let table_size = table.read(data, start + 1, stream_end, 6, 255, scratch)
let bits = BackwardBits::new(data, start + 1 + table_size, stream_end)
let mut state1 = bits.read(table.log)
let mut state2 = bits.read(table.log)
if bits.pos < 0 {
raise corrupt("Huffman weights without their initial states")
}
let mut count = 0
for ;; {
if count > 252 {
raise corrupt("more than 255 Huffman weights")
}
weights[count] = table.symbol_of(state1)
state1 = table.next(state1, bits)
count += 1
if bits.pos < 0 {
weights[count] = table.symbol_of(state2)
count += 1
break
}
weights[count] = table.symbol_of(state2)
state2 = table.next(state2, bits)
count += 1
if bits.pos < 0 {
weights[count] = table.symbol_of(state1)
count += 1
break
}
}
(count, 1 + size)
}
self.build(count)
used
}
///|
/// Builds the table from `weights[0:count]`; the last symbol's weight is
/// implied (RFC 8878 section 4.2.1.1). `@huffman.build_table` builds it, or
/// says why the weights are refused.
fn Huffman::build(self : Huffman, count : Int32) -> Unit raise Stop {
let result = @huffman.build_table(
self.weights,
count,
self.symbol,
self.nbits,
self.weight_count,
self.entry_start,
)
// The implied last weight follows the others, once known (RFC 8878
// section 4.2.1.1).
if result > 0 || result == @huffman.NO_WEIGHT_ONE {
self.weights[count] = self.entry_start[0]
}
if result < 0 {
raise corrupt(
match result {
@huffman.WEIGHT_TOO_LARGE => "a Huffman weight above \{MAX_HUF_BITS}"
@huffman.ONE_SYMBOL => "a Huffman tree with one symbol"
@huffman.TOO_DEEP => "a Huffman tree deeper than \{MAX_HUF_BITS} bits"
@huffman.INCOMPLETE => "Huffman weights that do not complete a tree"
@huffman.NO_WEIGHT_ONE => "a Huffman tree with no weight of 1"
_ => "Huffman weights that overfill the tree"
},
)
}
self.max_bits = result
self.symbols = count + 1
}
///|
/// Decodes one stream, `data[start:end]`, into exactly `count` literals at
/// `out[at:]`, which the caller has made room for; the stream must be used
/// up exactly.
fn Huffman::decode_stream(
self : Huffman,
data : FixedArray[Byte],
start : Int32,
end : Int32,
out : FixedArray[Byte],
at : Int32,
count : Int32,
) -> Unit raise Stop {
let bits = BackwardBits::new(data, start, end)
let pos = self.decode_run(data, start, bits.pos, out, at, at + count)
if pos != 0 {
raise corrupt("a Huffman stream that does not end with its literals")
}
}
///|
/// Decodes the literals `out[from:to]` from the stream in `data` from
/// `start` with `pos` bits left, and returns the bits left after them.
/// `decode` writes the streams' literals within [0, count), and
/// `decode_literals` reserves `literals` for the count, so every index of
/// `out` is within it; every table index is below 1 << max_bits <= 2048,
/// the tables' size.
fn Huffman::decode_run(
self : Huffman,
data : FixedArray[Byte],
start : Int32,
pos : Int32,
out : FixedArray[Byte],
from : Int32,
to : Int32,
) -> Int32 {
let mut pos = pos
let mut i = from
// Five codes of at most 11 bits from one 64-bit read of 57 bits: the
// last starts at most 44 bits below `pos`, so all five are within the
// stream.
while i + 5 <= to && wide_reads(pos) {
pos = self.decode5(data, start, pos, out, i)
i += 5
}
let max_bits = self.max_bits
while i < to {
let index = back_bits(data, start, pos, max_bits)
out.unsafe_set(i, self.symbol.unsafe_get(index))
pos -= self.nbits.unsafe_get(index).to_int()
i += 1
}
pos
}
///|
/// Decodes five literals into `out[at:at + 5]` from one `top_bits` read at
/// `pos` (`wide_reads(pos)`), and returns the bits left after them.
#inline
fn Huffman::decode5(
self : Huffman,
data : FixedArray[Byte],
start : Int32,
pos : Int32,
out : FixedArray[Byte],
at : Int32,
) -> Int32 {
let max_bits = self.max_bits
let symbol = self.symbol
let nbits = self.nbits
let mut w = top_bits(data, start, pos)
let mut pos = pos
for k in 0..<5 {
let index = take_bits(w, max_bits)
out.unsafe_set(at + k, symbol.unsafe_get(index))
let n = nbits.unsafe_get(index).to_int()
w = w << n
pos -= n
}
pos
}
///|
/// Decodes `count` literals from `data[start:end]` into `out[0:count]`, in
/// one stream or four after a jump table.
fn Huffman::decode(
self : Huffman,
data : FixedArray[Byte],
start : Int32,
end : Int32,
out : FixedArray[Byte],
count : Int32,
four_streams : Bool,
) -> Unit raise Stop {
if !four_streams {
self.decode_stream(data, start, end, out, 0, count)
return
}
let (size1, size2, size3, _) = checked(
@header.parse_jump_table(data[start:end]),
)
let s1 = start + 6
let s2 = s1 + size1
let s3 = s2 + size2
let s4 = s3 + size3
// The caller rejects four streams with fewer than 6 literals, and for 6 or
// more the last segment is never negative.
let segment = (count + 3) / 4
let last = count - 3 * segment
// The four streams are decoded together, so that their reads overlap,
// when all four start well-formed; otherwise one after another, which
// raises what is wrong with the first bad stream.
match
(
stream_pos(data, s1, s2),
stream_pos(data, s2, s3),
stream_pos(data, s3, s4),
stream_pos(data, s4, end),
) {
(Some(p1), Some(p2), Some(p3), Some(p4)) => {
let mut p1 = p1
let mut p2 = p2
let mut p3 = p3
let mut p4 = p4
let mut j = 0
while j + 5 <= last &&
wide_reads(p1) &&
wide_reads(p2) &&
wide_reads(p3) &&
wide_reads(p4) {
p1 = self.decode5(data, s1, p1, out, j)
p2 = self.decode5(data, s2, p2, out, segment + j)
p3 = self.decode5(data, s3, p3, out, 2 * segment + j)
p4 = self.decode5(data, s4, p4, out, 3 * segment + j)
j += 5
}
p1 = self.decode_run(data, s1, p1, out, j, segment)
p2 = self.decode_run(data, s2, p2, out, segment + j, 2 * segment)
p3 = self.decode_run(data, s3, p3, out, 2 * segment + j, 3 * segment)
p4 = self.decode_run(data, s4, p4, out, 3 * segment + j, count)
if p1 != 0 || p2 != 0 || p3 != 0 || p4 != 0 {
raise corrupt("a Huffman stream that does not end with its literals")
}
}
_ => {
self.decode_stream(data, s1, s2, out, 0, segment)
self.decode_stream(data, s2, s3, out, segment, segment)
self.decode_stream(data, s3, s4, out, 2 * segment, segment)
self.decode_stream(data, s4, end, out, 3 * segment, last)
}
}
}
///|
/// The bits before the end mark of the stream `data[start:end]`, or `None`
/// where `BackwardBits::new` raises.
fn stream_pos(data : FixedArray[Byte], start : Int32, end : Int32) -> Int32? {
guard end > start && data[end - 1] != b'\x00' else { return None }
Some((end - start - 1) * 8 + (31 - data[end - 1].to_int().clz()))
}