dymokomi/luce-compress
Source of release 0.9.1
0.9.1 / src / zstd / huffman.lucb
#==============================================================================================
#
# zstd/huffman - Huffman tables and literal streams, decoding
#
# DESCRIPTION:
# A tree is described by its symbols' weights, 4 bits each or FSE-compressed with
# two interleaved states; the last symbol's weight is implied by completing the
# code to a power of two, whose log is the longest code (at most 12 here, as the
# reference decoder allows; the format's encoders write at most 11). The decoding
# table has a row per value of the next `log` bits: the symbol and its code's
# length. A stream decodes four symbols per reload while the reader has eight
# bytes in hand, then one at a time; it must end exactly at its first bit.
#
#==============================================================================================
## The longest code a table may have.
let huffman_most_bits: u32 = 12
## Read the tree description at the start of `data` into `table` (u16 rows: symbol << 8 |
## length); its log and the description's bytes.
func read_huffman(data: const u8[], table: u16*) -> (u32, usize)!:
if data.length == 0: error(corrupt, "missing zstd Huffman tree")
var weights: u8[256]
let header = (usize)data[0]
var count: usize = 0
var size: usize = 0
if header >= 128:
count = header - 127
size = 1 + (count + 1) // 2
if size > data.length: error(corrupt, "truncated zstd Huffman tree")
for index in 0..<count:
let byte = data[1 + index // 2]
weights[index] = byte >> 4 if index % 2 == 0 else byte & 15
else:
size = 1 + header
if size > data.length: error(corrupt, "truncated zstd Huffman tree")
count = try read_fse_weights(data[1..<size], &weights[0])
# Weights to code lengths; the last symbol's completes the code.
var ranks: u32[16]
var total: u32 = 0
for index in 0..<count:
let weight = (u32)weights[index]
if weight > huffman_most_bits: error(corrupt, "zstd Huffman weight too large")
ranks[(usize)weight] += 1
if weight > 0: total += (u32)1 << (weight - 1)
if total == 0: error(corrupt, "zstd Huffman tree without symbols")
let log = high_bit(total) + 1
if log > huffman_most_bits: error(corrupt, "zstd Huffman tree too deep")
let rest = ((u32)1 << log) - total
if rest & (rest - 1) != 0: error(corrupt, "incomplete zstd Huffman tree")
let last = high_bit(rest) + 1
weights[count] = (u8)last
ranks[(usize)last] += 1
count += 1
if ranks[1] < 2 or ranks[1] & 1 != 0: error(corrupt, "damaged zstd Huffman tree")
# Rows: weight by weight from the lightest, symbols in order within a weight.
var start: u32[16]
var next: u32 = 0
for weight in 1..<log + 1:
start[(usize)weight] = next
next += ranks[(usize)weight] << (weight - 1)
for symbol in 0..<count:
let weight = (u32)weights[symbol]
if weight == 0: continue
let length = log + 1 - weight
let row = (u16)((symbol << 8) | (usize)length)
let first = start[(usize)weight]
let rows = (u32)1 << (weight - 1)
for at in first..<first + rows:
table[(usize)at] = row
start[(usize)weight] = first + rows
return (log, size)
## Weights compressed with FSE (two states over one table of log <= 6) from `data` into
## `weights`; how many.
func read_fse_weights(data: const u8[], weights: u8*) -> usize!:
let distribution = try read_distribution(data, 255, 6)
var table: State[64]
build_states(&distribution.counts[0], distribution.symbols, distribution.log, &table[0])
var reader = try Backward.open(data[distribution.size..])
let log = distribution.log
var first = (usize)reader.read(log)
reader.reload()
var second = (usize)reader.read(log)
reader.reload()
if reader.overflowed(): error(corrupt, "truncated zstd Huffman weights")
var count: usize = 0
while true:
if count > 253: error(corrupt, "too many zstd Huffman weights")
let one = table[first]
weights[count] = one.symbol
count += 1
first = (usize)one.next + (usize)reader.read((u32)one.bits)
reader.reload()
if reader.overflowed():
weights[count] = table[second].symbol
return count + 1
if count > 253: error(corrupt, "too many zstd Huffman weights")
let two = table[second]
weights[count] = two.symbol
count += 1
second = (usize)two.next + (usize)reader.read((u32)two.bits)
reader.reload()
if reader.overflowed():
weights[count] = table[first].symbol
return count + 1
return count
## Decode `stream` into `out` (exactly its length) with `table` of `log` bits.
func decode_stream(stream: const u8[], out: u8[], table: const u16*, log: u32) -> !:
var reader = try Backward.open(stream)
try finish_stream(&reader, out.data, 0, out.length, table, log)
## Decode four streams (`data` starts with their jump table) into `out`: the four
## readers take turns while each has eight bytes in hand, then each finishes alone.
func decode_four(data: const u8[], out: u8[], table: const u16*, log: u32) -> !:
if data.length < 10 or out.length < 6: error(corrupt, "damaged zstd Huffman streams")
let one = (usize)data[0] | (usize)data[1] << 8
let two = (usize)data[2] | (usize)data[3] << 8
let three = (usize)data[4] | (usize)data[5] << 8
if 6 + one + two + three >= data.length: error(corrupt, "damaged zstd Huffman jump table")
let segment = (out.length + 3) // 4
var readers: Backward[4]
readers[0] = try Backward.open(data[6..<6 + one])
readers[1] = try Backward.open(data[6 + one..<6 + one + two])
readers[2] = try Backward.open(data[6 + one + two..<6 + one + two + three])
readers[3] = try Backward.open(data[6 + one + two + three..])
let target = out.data
var at: usize = 0
# Each stream fills a quarter; the last may be up to 3 bytes shorter.
let last = out.length - 3 * segment
while at + 4 <= last and readers[0].roomy() and readers[1].roomy() and readers[2].roomy() and readers[3].roomy():
for lane in 0..<(usize)4: readers[lane].reload()
for step in 0..<(usize)4:
for lane in 0..<(usize)4:
let row = table[(usize)readers[lane].look(log)]
readers[lane].consumed +%= (u32)(row & 255)
target[lane * segment + at + step] = (u8)(row >> 8)
at += 4
for lane in 0..<(usize)4:
let end = segment if lane < 3 else last
try finish_stream(&readers[lane], target + lane * segment, at, end, table, log)
## Decode symbols `at..<end` of a stream already begun into `target`, then check that the
## stream ended exactly.
func finish_stream(reader: Backward*, target: u8*, at: usize, end: usize, table: const u16*, log: u32) -> !:
var position = at
while position + 4 <= end and reader.roomy():
reader.reload()
for _ in 0..<(usize)4:
let row = table[(usize)reader.look(log)]
reader.consumed +%= (u32)(row & 255)
target[position] = (u8)(row >> 8)
position += 1
while position < end:
reader.reload()
let row = table[(usize)reader.look(log)]
reader.consumed +%= (u32)(row & 255)
target[position] = (u8)(row >> 8)
position += 1
reader.reload()
if not reader.finished(): error(corrupt, "damaged zstd Huffman stream")