Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.1

0.9.1 / src / zstd / entropy.lucb

#==============================================================================================
#
#   zstd/entropy - Huffman code lengths and FSE distributions for the encoder
#
#   DESCRIPTION:
#       Literals get a Huffman code no longer than 11 bits: lengths come from the
#       two-queue construction over symbols sorted by count, and when the longest is
#       too long the counts are flattened (halved, kept nonzero) and the code rebuilt.
#       Lengths become zstd's weights and canonical codes as the decoder derives them.
#
#       An FSE distribution scales counts to 2^log shares, every present symbol at
#       least one; the rounding left over goes to or comes from the largest shares.
#       Costs are estimated in 1/256 bits from a piecewise-linear log2.
#
#==============================================================================================

## The longest Huffman code the encoder writes.
let huffman_longest: u32 = 11

## log2(`value`) (> 0) in 1/256 units, linear between powers of two.
inline func log2_fixed(value: u32) -> u32:
    let bit = high_bit(value)
    let fraction = ((value - ((u32)1 << bit)) << 8) >> bit if bit <= 23 else ((value - ((u32)1 << bit)) >> (bit - 8))
    return (bit << 8) + fraction

## Code lengths for `counts` (`symbols` of them, at least two nonzero) into `lengths`,
## none longer than `longest`; the longest.
func huffman_lengths(counts: const u32*, symbols: usize, longest: u32, lengths: u8*) -> u32:
    var weights: u32[256]
    for symbol in 0..<symbols: weights[symbol] = counts[symbol]
    while true:
        let most = huffman_build(&weights[0], symbols, lengths)
        if most <= longest: return most
        for symbol in 0..<symbols:
            if weights[symbol] > 0: weights[symbol] = (weights[symbol] >> 1) | 1

## One Huffman construction over `counts`; the longest length.
func huffman_build(counts: const u32*, symbols: usize, lengths: u8*) -> u32:
    # Leaves sorted by count (insertion sort: at most 256), then the two-queue merge.
    var order: u16[256]
    var leaves: usize = 0
    for symbol in 0..<symbols:
        lengths[symbol] = 0
        if counts[symbol] == 0: continue
        var at = leaves
        while at > 0 and counts[(usize)order[at - 1]] > counts[symbol]:
            order[at] = order[at - 1]
            at -= 1
        order[at] = (u16)symbol
        leaves += 1
    var weight: u64[512]
    var parent: u16[512]
    for index in 0..<leaves: weight[index] = (u64)counts[(usize)order[index]]
    var next_leaf: usize = 0
    var next_node = leaves
    var made = leaves
    while made < 2 * leaves - 1:
        var pair: usize[2]
        for side in 0..<(usize)2:
            if next_leaf < leaves and (next_node >= made or weight[next_leaf] <= weight[next_node]):
                pair[side] = next_leaf
                next_leaf += 1
            else:
                pair[side] = next_node
                next_node += 1
        weight[made] = weight[pair[0]] + weight[pair[1]]
        parent[pair[0]] = (u16)made
        parent[pair[1]] = (u16)made
        made += 1
    # Depths from the root down.
    var depth: u8[512]
    var most: u32 = 0
    var node = made - 1
    while node > 0:
        node -= 1
        depth[node] = depth[(usize)parent[node]] + 1
        if node < leaves:
            lengths[(usize)order[node]] = depth[node]
            if (u32)depth[node] > most: most = (u32)depth[node]
    return most

## Canonical codes for `lengths` (longest `most`), as the decoder derives them from
## weights: lighter weights first, symbols in order within a weight.
func huffman_codes(lengths: const u8*, symbols: usize, most: u32, codes: u16*):
    var ranks: u32[16]
    for symbol in 0..<symbols:
        if lengths[symbol] > 0: ranks[(usize)(most + 1 - (u32)lengths[symbol])] += 1
    var start: u32[16]
    var next: u32 = 0
    for weight in 1..<most + 1:
        start[(usize)weight] = next
        next += ranks[(usize)weight] << (weight - 1)
    for symbol in 0..<symbols:
        let length = (u32)lengths[symbol]
        if length == 0: continue
        let weight = most + 1 - length
        codes[symbol] = (u16)(start[(usize)weight] >> (weight - 1))
        start[(usize)weight] += (u32)1 << (weight - 1)

## The table log for `total` samples of `distinct` symbols, at most `most_log`.
func table_log(total: u32, distinct: u32, most_log: u32) -> u32:
    var log = high_bit(total) + 1
    if log > most_log: log = most_log
    if log < 5: log = 5
    while ((u32)1 << log) < distinct * 2 and log < most_log: log += 1
    return log

## Scale `counts` (`symbols` of them, summing to `total`) to shares of 2^log in
## `shares`, each present symbol at least one.
func normalize(counts: const u32*, symbols: u32, total: u32, log: u32, shares: i16*):
    let size = (i64)1 << log
    var assigned: i64 = 0
    var largest: usize = 0
    for symbol in 0..<(usize)symbols:
        let count = (i64)counts[symbol]
        if count == 0:
            shares[symbol] = 0
            continue
        var share = (count * size + (i64)total // 2) // (i64)total
        if share == 0: share = 1
        shares[symbol] = (i16)share
        assigned += share
        if count > (i64)counts[largest]: largest = symbol
    var left = size - assigned
    if left > 0: shares[largest] += (i16)left
    while left < 0:
        # Take one from the largest share above one.
        var pick: usize = 0
        for symbol in 0..<(usize)symbols:
            if shares[symbol] > shares[pick]: pick = symbol
        shares[pick] -= 1
        left += 1

## The cost in 1/256 bits of `counts` coded with `shares` of 2^log; none when a
## present symbol has no share.
func coded_cost(counts: const u32*, symbols: u32, shares: const i16*, share_symbols: u32, log: u32) -> u64?:
    var cost: u64 = 0
    for symbol in 0..<symbols:
        let count = counts[(usize)symbol]
        if count == 0: continue
        if symbol >= share_symbols: return none
        let share = (i32)shares[(usize)symbol]
        if share == 0: return none
        let bits = (log << 8) - (0 if share < 0 else log2_fixed((u32)share))
        cost += (u64)count * (u64)bits
    return cost