Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.0

0.9.0 / src / lz4 / module.lucb

#==============================================================================================
#
#   lz4 - LZ4 block compression
#
#   DESCRIPTION:
#       The LZ4 block format (lz4_Block_format.md): sequences of a token, literal bytes and a
#       match copied from earlier output at a 16-bit offset. `decompress` checks every length
#       and offset against its buffers, so damaged input fails with `corrupt` rather than
#       reading or writing out of bounds. `compress` is LZ4's fast greedy compressor (a hash
#       table of four-byte sequences, 12-bit hashes over the last 64 KiB), and keeps the
#       format's end rules: the last five bytes are literals and no match starts in the last
#       twelve, so any LZ4 decoder reads its output. Its bytes need not equal the reference
#       compressor's, only decode to the same data.
#
#       Fragments, in ORDER:
#
#       module.lucb    the compressor and the decompressor
#       tests.lucb     round trips and damaged blocks
#
#==============================================================================================
import memory
import binary

## The block is damaged, or longer than the output it must fill.
pub let corrupt = binary.corrupt
## An input larger than a block may hold.
pub let limit = binary.limit

## The largest input one block holds (LZ4_MAX_INPUT_SIZE).
pub let most_input: usize = 0x7E000000

let min_match: usize = 4
## No match starts in the last twelve bytes; the last five are literals.
let match_limit: usize = 12
let last_literals: usize = 5
let hash_bits: u32 = 12
let max_distance: usize = 65535

## The most bytes compressing `size` input bytes can take (LZ4_compressBound).
pub func bound(size: usize) -> usize:
    return size + size // 255 + 16

## Compress `input` into `output` (at least `bound(input.length)` bytes); the
## compressed length.
pub func compress(input: const u8[], output: u8[]) -> usize!:
    if input.length > most_input: error(limit, "an LZ4 block holds at most 2,113,929,216 bytes")
    if output.length < bound(input.length): error(limit, "the LZ4 output buffer is smaller than the bound")
    var table: u32[4096]
    let size = input.length
    var out: usize = 0
    var anchor: usize = 0
    if size >= match_limit + 1:
        let search_end = size - match_limit
        let extend_end = size - last_literals
        var at: usize = 1
        table[hash_of(memory.read[u32]((void*)&input[0]))] = 0
        var misses: u32 = 1 << 6
        while at < search_end:
            let sequence = memory.read[u32]((void*)&input[at])
            let slot = hash_of(sequence)
            let candidate = (usize)table[slot]
            table[slot] = (u32)at
            if candidate < at and at - candidate <= max_distance and memory.read[u32]((void*)&input[candidate]) == sequence:
                var start = at
                var reference = candidate
                # Extend the match backwards over equal literals.
                while start > anchor and reference > 0 and input[start - 1] == input[reference - 1]:
                    start -= 1
                    reference -= 1
                var length = min_match + (at - start)
                while start + length < extend_end and input[start + length] == input[reference + length]: length += 1
                out = write_sequence(input, output, out, anchor, start, start - reference, length)
                at = start + length
                anchor = at
                misses = 1 << 6
                # Index the positions the match covered at its end.
                if at - 2 < search_end: table[hash_of(memory.read[u32]((void*)&input[at - 2]))] = (u32)(at - 2)
            else:
                at += (usize)(misses >> 6)
                misses += 1
    # The remaining literals.
    let literals = size - anchor
    out = write_length(output, out, literals, 0)
    if literals > 0: memory.copy(output[out..], input[anchor..], literals)
    return out + literals

## Decompress the block `input` into `output`; the decompressed length.
pub func decompress(input: const u8[], output: u8[]) -> usize!:
    var at: usize = 0
    var out: usize = 0
    while at < input.length:
        let token = input[at]
        at += 1
        var literals = (usize)(token >> 4)
        if literals == 15:
            while true:
                if at >= input.length: error(corrupt, "a truncated LZ4 literal length")
                let extra = input[at]
                at += 1
                literals += (usize)extra
                if extra != 255: break
        if literals > input.length - at or literals > output.length - out: error(corrupt, "LZ4 literals run past a buffer")
        if literals > 0: memory.copy(output[out..], input[at..], literals)
        at += literals
        out += literals
        # The last sequence has literals only.
        if at == input.length: break
        if input.length - at < 2: error(corrupt, "a truncated LZ4 match offset")
        let offset = (usize)input[at] | ((usize)input[at + 1] << 8)
        at += 2
        if offset == 0 or offset > out: error(corrupt, "an LZ4 match offset outside the output")
        var length = (usize)(token & 15)
        if length == 15:
            while true:
                if at >= input.length: error(corrupt, "a truncated LZ4 match length")
                let extra = input[at]
                at += 1
                length += (usize)extra
                if extra != 255: break
        length += min_match
        if length > output.length - out: error(corrupt, "an LZ4 match runs past the output")
        let source = out - offset
        if offset >= length:
            memory.copy(output[out..], output[source..], length)
        else:
            # An overlapping match repeats the bytes it copies.
            for index in 0..<length: output[out + index] = output[source + index]
        out += length
    return out

inline func hash_of(sequence: u32) -> usize:
    return (usize)((sequence *% 2654435761) >> (32 - hash_bits))

## A token's length nibble and its extension bytes, at `out`; `shift` is 4
## for a literal length (the token is written) or 0 for a match length.
func write_length(output: u8[], at: usize, length: usize, shift: u32) -> usize:
    var out = at
    if length >= 15:
        output[out] = (u8)(15 << 4)
        out += 1
        var rest = length - 15
        while rest >= 255:
            output[out] = 255
            out += 1
            rest -= 255
        output[out] = (u8)rest
        return out + 1
    output[out] = (u8)(length << 4)
    return out + 1

## One sequence: the literals anchor..<start, then a match of `length`
## bytes at `distance`. Returns the output position after it.
func write_sequence(input: const u8[], output: u8[], at: usize, anchor: usize, start: usize, distance: usize, length: usize) -> usize:
    let literals = start - anchor
    let token = at
    var out = at + 1
    output[token] = 0
    var token_bits: u8 = 0
    if literals >= 15:
        token_bits = 15 << 4
        var rest = literals - 15
        while rest >= 255:
            output[out] = 255
            out += 1
            rest -= 255
        output[out] = (u8)rest
        out += 1
    else:
        token_bits = (u8)(literals << 4)
    if literals > 0: memory.copy(output[out..], input[anchor..], literals)
    out += literals
    output[out] = (u8)(distance & 255)
    output[out + 1] = (u8)(distance >> 8)
    out += 2
    let match_length = length - min_match
    if match_length >= 15:
        token_bits |= 15
        var rest = match_length - 15
        while rest >= 255:
            output[out] = 255
            out += 1
            rest -= 255
        output[out] = (u8)rest
        out += 1
    else:
        token_bits |= (u8)match_length
    output[token] = token_bits
    return out