Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.1

0.9.1 / src / zstd / frame.lucb

#==============================================================================================
#
#   zstd/frame - Frame headers, blocks and frames
#
#   DESCRIPTION:
#       Input is a run of frames: Zstandard frames (magic 0xFD2FB528) and skippable
#       frames (0x184D2A50 to 0x184D2A5F) that are passed over. A frame header gives the
#       window (or a single segment of the content's size), an optional dictionary ID,
#       the content size and whether a checksum follows the last block. Blocks are raw,
#       one byte repeated, or compressed; none may hold or make more than the frame's
#       block size, the smaller of its window and 128 KiB. Huffman and FSE tables and the
#       recent offsets carry from block to block within a frame (`Context`).
#
#==============================================================================================

let frame_magic: u32 = 0xFD2FB528
let skippable_magic: u32 = 0x184D2A50
## The largest block a frame may hold.
let block_largest: usize = 131072
## The largest window accepted: 2^31, the reference decoder's limit.
let window_largest_log: u32 = 31

## What a frame's header says.
struct FrameHeader:
    var size: usize
    var window: u64
    var content: u64
    var has_content: bool
    var checksum: bool

## The bytes of a dictionary ID field by its flag: 0, 1, 2 or 4 (twice that for a
## content size field of flag 1 to 3).
inline func field_bytes(flag: u32) -> usize:
    return 4 if flag == 3 else (usize)flag

## The header of the frame at the start of `data` (its magic already checked).
func read_frame_header(data: const u8[]) -> FrameHeader!:
    if data.length < 5: error(corrupt, "truncated zstd frame header")
    let descriptor = (u32)data[4]
    let content_flag = descriptor >> 6
    let single = (descriptor >> 5) & 1 != 0
    if (descriptor >> 3) & 1 != 0: error(corrupt, "reserved zstd frame header bit")
    let dictionary_bytes = field_bytes(descriptor & 3)
    var content_bytes = field_bytes(content_flag) * 2 if content_flag > 0 else 0
    if content_flag == 0 and single: content_bytes = 1
    var header: FrameHeader
    header.checksum = (descriptor >> 2) & 1 != 0
    header.size = 5 + (0 if single else 1) + dictionary_bytes + content_bytes
    if data.length < header.size: error(corrupt, "truncated zstd frame header")
    var at: usize = 5
    if not single:
        let window = (u32)data[at]
        at += 1
        let log = 10 + (window >> 3)
        if log > window_largest_log: error(unsupported, "zstd window larger than 2 GiB")
        let base = (u64)1 << (u64)log
        header.window = base + (base >> 3) * (u64)(window & 7)
    var dictionary: u64 = 0
    for index in 0..<dictionary_bytes: dictionary |= (u64)data[at + index] << (u64)(index * 8)
    at += dictionary_bytes
    if dictionary != 0: error(unsupported, "zstd frame needs a dictionary")
    if content_bytes > 0:
        var content: u64 = 0
        for index in 0..<content_bytes: content |= (u64)data[at + index] << (u64)(index * 8)
        if content_bytes == 2: content += 256
        header.content = content
        header.has_content = true
    if single: header.window = header.content
    return header

## The little-endian u32 at `at` of `data` (which holds it).
inline func u32_at(data: const u8[], at: usize) -> u32:
    return (u32)data[at] | (u32)data[at + 1] << 8 | (u32)data[at + 2] << 16 | (u32)data[at + 3] << 24

## The total content size the frames of `data` declare, or none when one does not
## declare it or the frames cannot be walked.
func content_size(data: const u8[]) -> u64?:
    var at: usize = 0
    var total: u64 = 0
    while at + 4 <= data.length:
        let magic = u32_at(data, at)
        if magic & 0xFFFFFFF0 == skippable_magic:
            if at + 8 > data.length: return none
            at += 8 + (usize)u32_at(data, at + 4)
            continue
        if magic != frame_magic: return none
        let header = read_frame_header(data[at..]) catch failure: return none
        if not header.has_content: return none
        total = total +? header.content else return none
        at += header.size
        # Skip the blocks by their headers.
        while true:
            if at + 3 > data.length: return none
            let block = (usize)data[at] | (usize)data[at + 1] << 8 | (usize)data[at + 2] << 16
            let kind = (block >> 1) & 3
            at += 3 + (1 if kind == 1 else block >> 3)
            if block & 1 != 0: break
        if header.checksum: at += 4
    return total

## A frame's decoding state: the tables and offsets its blocks pass on, and scratch.
struct Context:
    var huffman: u16[4096]
    var huffman_log: u32
    var literal_lengths: SeqTable
    var offsets: SeqTable
    var match_lengths: SeqTable
    var repeats: u64[3]
    ## The block's literals: the largest block and a word of slack.
    var literals: u8[]
    var literal_count: usize
    var block_most: usize

    ## Start a frame: no tables, the initial recent offsets.
    func reset(block_most: usize):
        self.huffman_log = 0
        self.literal_lengths.ready = false
        self.offsets.ready = false
        self.match_lengths.ready = false
        self.repeats = [1, 4, 8]
        self.block_most = block_most

## Decode the frames of `data` into `output`.
func decode_frames(data: const u8[], output: Output*, allow_trailing: bool) -> !:
    if data.length == 0: error(corrupt, "empty zstd input")
    let context = try new Context in memory.heap
    defer free(context) in memory.heap
    context.literals = try new u8[block_largest + slack] in memory.heap
    defer free(context.literals) in memory.heap
    var at: usize = 0
    var frames: usize = 0
    while at < data.length:
        if data.length - at < 4:
            if allow_trailing and frames > 0: return
            error(corrupt, "truncated zstd frame")
        let magic = u32_at(data, at)
        if magic & 0xFFFFFFF0 == skippable_magic:
            if data.length - at < 8: error(corrupt, "truncated zstd skippable frame")
            let size = (usize)u32_at(data, at + 4)
            if size > data.length - at - 8: error(corrupt, "truncated zstd skippable frame")
            at += 8 + size
            frames += 1
            continue
        if magic != frame_magic:
            if allow_trailing and frames > 0: return
            error(corrupt, "not a zstd frame")
        at += try decode_frame(data[at..], output, context)
        frames += 1

## Decode the frame at the start of `data` into `output`; its bytes.
func decode_frame(data: const u8[], output: Output*, context: Context*) -> usize!:
    let header = try read_frame_header(data)
    let block_most = (usize)(header.window if header.window < (u64)block_largest else (u64)block_largest)
    context.reset(block_most)
    let start = output.used
    var at = header.size
    while true:
        if data.length - at < 3: error(corrupt, "truncated zstd block header")
        let block = (usize)data[at] | (usize)data[at + 1] << 8 | (usize)data[at + 2] << 16
        at += 3
        let kind = (block >> 1) & 3
        let size = block >> 3
        if kind == 3: error(corrupt, "reserved zstd block type")
        if size > block_most: error(corrupt, "zstd block larger than its frame allows")
        try output.reserve(block_most)
        if kind == 1:
            if at >= data.length: error(corrupt, "truncated zstd block")
            if size > output.limit - output.used: error(limit, "zstd output exceeds its limit")
            memory.set(output.data[output.used..<output.used + size], data[at])
            output.used += size
            at += 1
        else:
            if size > data.length - at: error(corrupt, "truncated zstd block")
            let content = data[at..<at + size]
            if kind == 0:
                if size > output.limit - output.used: error(limit, "zstd output exceeds its limit")
                if size > 0: memory.copy(output.data[output.used..], content, size)
                output.used += size
            else:
                let literals = try context.read_literals(content)
                try context.run_sequences(content[literals..], output, start, output.used + block_most)
            at += size
        if block & 1 != 0: break
    let made = output.used - start
    if header.has_content and (u64)made != header.content: error(corrupt, "zstd frame content size mismatch")
    if header.checksum:
        if data.length - at < 4: error(corrupt, "truncated zstd checksum")
        let expected = u32_at(data, at)
        if (u32)xxhash64(output.data[start..<output.used]) != expected: error(corrupt, "zstd checksum mismatch")
        at += 4
    return at