Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.1

0.9.1 / src / zstd / fse.lucb

#==============================================================================================
#
#   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