dymokomi/luce-compress
Source of release 0.9.1
#==============================================================================================
#
# zstd/fse - FSE distributions, decoding tables and encoding tables
#
# DESCRIPTION:
# A distribution gives each symbol a share of 2^log states; a share of -1 is a
# symbol rarer than one state, which takes one state at the table's top. States
# are dealt to symbols in a fixed stride over the table (`spread`), and each
# state's next-state rule follows from the order of a symbol's states. The
# decoder's table gives, per state, the symbol, the bits to read and the
# baseline they are added to; the encoder's gives the inverse.
#
# `read_distribution` reads the compact header form (RFC 8878 section 4.1.1);
# `write_distribution` writes it.
#
#==============================================================================================
## The most states any table here has: 2^9.
let most_states: usize = 512
## A distribution read from a header.
struct Distribution:
## Shares by symbol; -1 is "less than one state".
var counts: i16[256]
## The symbols it covers (the last nonzero one and those before it).
var symbols: u32
var log: u32
## The header's bytes.
var size: usize
## `count` (<= 25) bits of `data` starting at bit `position`, zeros past its end.
func bits_at(data: const u8[], position: usize, count: u32) -> u32:
var value: u64 = 0
let first = position >> 3
for index in 0..<(usize)5:
if first + index < data.length:
value |= (u64)data[first + index] << (u64)(index * 8)
return (u32)((value >> (u64)(position & 7)) & (((u64)1 << (u64)count) - 1))
## The distribution at the start of `data`, of at most `max_symbol + 1` symbols and a
## log of at most `max_log`; fails with `corrupt` when it is damaged.
func read_distribution(data: const u8[], max_symbol: u32, max_log: u32) -> Distribution!:
var result: Distribution
if data.length == 0: error(corrupt, "missing zstd FSE table")
let log = (u32)(data[0] & 15) + 5
if log > 15 or log > max_log: error(corrupt, "zstd FSE table log too large")
result.log = log
var position: usize = 4
var remaining: i32 = ((i32)1 << log) + 1
var threshold: i32 = (i32)1 << log
var bits = log + 1
var symbol: u32 = 0
var previous_zero = false
let alphabet = max_symbol + 1
while true:
if previous_zero:
# Runs of zero shares: 2-bit counts, 3 meaning another follows.
while true:
let repeat = bits_at(data, position, 2)
position += 2
symbol += repeat
if repeat != 3 or symbol > alphabet: break
if symbol >= alphabet: break
let most = 2 * threshold - 1 - remaining
var value = (i32)bits_at(data, position, bits - 1)
if value < most:
position += (usize)(bits - 1)
else:
value = (i32)bits_at(data, position, bits)
if value >= threshold: value -= most
position += (usize)bits
let count = value - 1
if count >= 0:
remaining -= count
else:
remaining += count
result.counts[(usize)symbol] = (i16)count
symbol += 1
previous_zero = count == 0
if remaining < threshold:
if remaining <= 1: break
bits = high_bit((u32)remaining) + 1
threshold = (i32)1 << (bits - 1)
if symbol >= alphabet: break
if remaining != 1 or symbol > alphabet: error(corrupt, "damaged zstd FSE table")
if position > data.length * 8: error(corrupt, "truncated zstd FSE table")
result.symbols = symbol
result.size = (position + 7) >> 3
return result
## Deal 2^`log` states to the symbols of `counts`: `spread[state]` is a state's symbol.
## Symbols of share -1 take the top states, one each. The shares must sum to 2^log.
func spread_symbols(counts: const i16*, symbols: u32, log: u32, spread: u8*):
let size = (u32)1 << log
var high = size - 1
for symbol in 0..<symbols:
if counts[(usize)symbol] == -1:
spread[(usize)high] = (u8)symbol
high -%= 1
let step = (size >> 1) + (size >> 3) + 3
let mask = size - 1
var position: u32 = 0
for symbol in 0..<symbols:
let share = (i32)counts[(usize)symbol]
var placed: i32 = 0
while placed < share:
spread[(usize)position] = (u8)symbol
position = (position + step) & mask
while position > high:
position = (position + step) & mask
placed += 1
# mark: Decoding tables =======================================================================
## A decoding table's row: the symbol, the bits that follow it and their baseline.
struct State:
var symbol: u8
var bits: u8
var next: u16
## The decoding table of a distribution, 2^log rows.
func build_states(counts: const i16*, symbols: u32, log: u32, table: State*):
var spread: u8[512]
spread_symbols(counts, symbols, log, &spread[0])
let size = (u32)1 << log
var next: u16[256]
for symbol in 0..<symbols:
let share = counts[(usize)symbol]
next[(usize)symbol] = 1 if share == -1 else (u16)share
for state in 0..<size:
let symbol = spread[(usize)state]
let rank = (u32)next[(usize)symbol]
next[(usize)symbol] += 1
let bits = log - high_bit(rank)
table[(usize)state] = State(symbol, (u8)bits, (u16)((rank << bits) - size))
## A sequence table's row: the code's baseline and extra bits with the state rule.
struct SeqState:
var base: u32
var next: u16
var bits: u8
var extra: u8
## A sequence code's decoding table and whether a block has defined it.
struct SeqTable:
var rows: SeqState[512]
var log: u32
var ready: bool
## Build from a distribution over codes whose baselines and extra bits are given.
func build(counts: const i16*, symbols: u32, log: u32, bases: const u32*, extras: const u8*):
var states: State[512]
build_states(counts, symbols, log, &states[0])
for row in 0..<((usize)1 << log):
let code = (usize)states[row].symbol
self.rows[row] = SeqState(bases[code], states[row].next, states[row].bits, extras[code])
self.log = log
self.ready = true
## One code for every sequence (RLE mode): no state bits.
func single(code: usize, bases: const u32*, extras: const u8*):
self.rows[0] = SeqState(bases[code], 0, 0, extras[code])
self.log = 0
self.ready = true
# mark: Encoding tables =======================================================================
## The encoder's rule for one symbol: the bits a state gives out depend on the state,
## and where it goes from the shifted state.
struct SymbolRule:
var delta_bits: u32
var delta_state: i32
## An FSE encoding table: next states (as 2^log + state) and the symbols' rules.
struct Coder:
var states: u16[512]
var rules: SymbolRule[256]
var log: u32
## The table of a distribution (shares sum to 2^log; -1 allowed).
func build(counts: const i16*, symbols: u32, log: u32):
var spread: u8[512]
spread_symbols(counts, symbols, log, &spread[0])
let size = (u32)1 << log
var cumulative: u32[257]
for symbol in 0..<symbols:
let share = (i32)counts[(usize)symbol]
cumulative[(usize)symbol + 1] = cumulative[(usize)symbol] + (1 if share == -1 else (u32)(share if share > 0 else 0))
var place: u32[257]
for symbol in 0..<symbols: place[(usize)symbol] = cumulative[(usize)symbol]
for state in 0..<size:
let symbol = (usize)spread[(usize)state]
self.states[(usize)place[symbol]] = (u16)(size + state)
place[symbol] += 1
for symbol in 0..<symbols:
let share = (i32)counts[(usize)symbol]
if share == 0:
self.rules[(usize)symbol] = SymbolRule(((log + 1) << 16) - size, 0)
elif share == -1 or share == 1:
self.rules[(usize)symbol] = SymbolRule((log << 16) - size, (i32)cumulative[(usize)symbol] - 1)
else:
let most_bits = log - high_bit((u32)share - 1)
let least = (u32)share << most_bits
self.rules[(usize)symbol] = SymbolRule((most_bits << 16) - least, (i32)cumulative[(usize)symbol] - share)
self.log = log
## The first state, for the last symbol written.
inline func start(symbol: usize) -> u32:
let rule = self.rules[symbol]
let bits = (rule.delta_bits + 32768) >> 16
let value = (bits << 16) -% rule.delta_bits
return (u32)self.states[(usize)((i32)(value >> bits) + rule.delta_state)]
## Write the bits `state` gives out for `symbol`; the next state.
inline func put(writer: Writer*, state: u32, symbol: usize) -> u32:
let rule = self.rules[symbol]
let bits = (state +% rule.delta_bits) >> 16
writer.add((u64)state, bits)
return (u32)self.states[(usize)((i32)(state >> bits) + rule.delta_state)]
## Write the final state.
inline func finish(writer: Writer*, state: u32):
writer.add((u64)state, self.log)
## Write `counts` (`symbols` of them, summing to 2^log, -1 allowed) as a header into
## `out`; its bytes.
func write_distribution(counts: const i16*, symbols: u32, log: u32, out: u8[]) -> usize:
var writer = Writer.into(out)
writer.add((u64)(log - 5), 4)
var remaining: i32 = ((i32)1 << log) + 1
var threshold: i32 = (i32)1 << log
var bits = log + 1
var symbol: u32 = 0
var previous_zero = false
while symbol < symbols and remaining > 1:
if previous_zero:
var start = symbol
while symbol < symbols and counts[(usize)symbol] == 0: symbol += 1
while symbol >= start + 24:
writer.add(0xFFFF, 16)
writer.flush()
start += 24
while symbol >= start + 3:
writer.add(3, 2)
start += 3
writer.add((u64)(symbol - start), 2)
writer.flush()
var count = (i32)counts[(usize)symbol]
symbol += 1
let most = 2 * threshold - 1 - remaining
remaining -= count if count >= 0 else -count
count += 1
if count >= threshold: count += most
writer.add((u64)count, bits - (1 if count < most else 0))
writer.flush()
previous_zero = count == 1
while remaining < threshold:
bits -= 1
threshold >>= 1
let length = writer.at + (1 if writer.count > 0 else 0)
# Close without an end bit: the header is read forward and ends on a byte.
if writer.count > 0: writer.flush()
return length