Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.1

0.9.1 / src / zstd / block.lucb

#==============================================================================================
#
#   zstd/block - Writing blocks
#
#   DESCRIPTION:
#       A `Compressor` holds an input's match finder state and a block's sequences and
#       literals. `block` finds the sequences of 128 KiB of input, writes the compressed
#       block into its scratch and keeps it when it is smaller than the input; otherwise
#       the block is stored raw, or as one repeated byte. The recent offsets the decoder
#       will keep are tracked here exactly, so matches at them are sent as repeat codes;
#       a block stored raw leaves them as they were.
#
#       The sections themselves are written by section.lucb.
#
#==============================================================================================

## The encoder's FSE tables: one per sequence code kind and one for Huffman weights.
struct Coders:
    var literal_lengths: Coder
    var offsets: Coder
    var match_lengths: Coder
    var weights: Coder

## The most sequences a block can hold: every match at least 4 bytes.
let most_sequences: usize = 131072 // 4 + 1

struct Compressor:
    var input: const u8[]
    var level: Level
    var window_log: u32
    var window: usize
    # The match finders' tables (match.lucb, chain.lucb).
    var hashes: u32[]
    var long_hashes: u32[]
    var links: u32[]
    var linked: usize
    var recent0: usize
    var recent1: usize
    # The block being written: its literals and sequences.
    var literals: u8[]
    var literal_count: usize
    var sequences: Sequence[]
    var sequence_count: usize
    # The decoder's recent offsets as of the block's start.
    var repeats: u32[3]
    # Per-sequence codes, extra-bit values, and the block's scratch output.
    var codes: u8[]
    var values: u32[]
    var scratch: u8[]
    var coders: Coders[]

    ## A compressor of `input` at `level`.
    static func open(input: const u8[], level: i32) -> Compressor!:
        var made: Compressor
        errdefer made.close()
        made.input = input
        made.level = level_parameters(level)
        made.window_log = made.level.window_log
        made.window = (usize)1 << made.window_log
        made.repeats = [1, 4, 8]
        made.hashes = try new u32[(usize)1 << made.level.hash_log] in memory.heap
        if made.level.long_log > 0: made.long_hashes = try new u32[(usize)1 << made.level.long_log] in memory.heap
        if made.level.chain_log > 0: made.links = try new u32[(usize)1 << made.level.chain_log] in memory.heap
        made.literals = try new u8[block_largest + 64] --- in memory.heap
        made.sequences = try new Sequence[most_sequences] --- in memory.heap
        made.codes = try new u8[most_sequences * 3] --- in memory.heap
        made.values = try new u32[most_sequences] --- in memory.heap
        made.scratch = try new u8[block_largest * 6 + 4096] --- in memory.heap
        made.coders = try new Coders[1] in memory.heap
        return made

    func close():
        if self.hashes.length > 0: free(self.hashes) in memory.heap
        if self.long_hashes.length > 0: free(self.long_hashes) in memory.heap
        if self.links.length > 0: free(self.links) in memory.heap
        if self.literals.length > 0: free(self.literals) in memory.heap
        if self.sequences.length > 0: free(self.sequences) in memory.heap
        if self.codes.length > 0: free(self.codes) in memory.heap
        if self.values.length > 0: free(self.values) in memory.heap
        if self.scratch.length > 0: free(self.scratch) in memory.heap
        if self.coders.length > 0: free(self.coders) in memory.heap
        var empty: Compressor
        empty.input = self.input
        self = empty

    ## Write the block of input bytes `start..<end` into `out`; its bytes.
    func block(start: usize, end: usize, last: bool, out: u8[]) -> usize!:
        let size = end - start
        let data = self.input[start..<end]
        if size > 1 and repeated(data):
            write_block_header(out, size, 1, last)
            out[3] = data[0]
            return 4
        if size >= 16:
            self.literal_count = 0
            self.sequence_count = 0
            if self.level.strategy == strategy_greedy:
                self.find_greedy(start, end)
            elif self.level.strategy == strategy_double:
                self.find_double(start, end)
            else:
                self.find_lazy(start, end)
            let saved = self.repeats
            let packed = self.write_sections()
            if packed < size:
                write_block_header(out, packed, 2, last)
                memory.copy(out[3..], self.scratch[..<packed], packed)
                return 3 + packed
            self.repeats = saved
        write_block_header(out, size, 0, last)
        if size > 0: memory.copy(out[3..], data, size)
        return 3 + size

    ## The block's literals and sequences sections into the scratch; their bytes.
    func write_sections() -> usize:
        let literals = self.write_literals(self.scratch)
        return literals + self.write_sequences(self.scratch[literals..])

## Whether every byte of `data` (nonempty) is the first.
func repeated(data: const u8[]) -> bool:
    let first = data[0]
    for byte in data:
        if byte != first: return false
    return true

## A block header: `size`, `kind` (0 raw, 1 RLE, 2 compressed) and the last flag.
func write_block_header(out: u8[], size: usize, kind: usize, last: bool):
    let header = (size << 3) | (kind << 1) | (1 if last else 0)
    out[0] = (u8)header
    out[1] = (u8)(header >> 8)
    out[2] = (u8)(header >> 16)