Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.1

0.9.1 / src / zstd / section.lucb

#==============================================================================================
#
#   zstd/section - Writing a block's literals and sequences sections
#
#   DESCRIPTION:
#       Literals are written raw, as one repeated byte, or Huffman-coded (one stream up
#       to 255 literals, four beyond) when that is smaller; the tree goes as 4-bit
#       weights or FSE-compressed ones, whichever is shorter. Sequences become codes and
#       extra bits; each code kind is sent with the predefined table, one repeated code
#       (RLE) or its own FSE table, by estimated size, and the bit stream is written
#       from the last sequence back, as the decoder reads it from the end.
#
#==============================================================================================

## A literals section header of `kind` (0 raw, 1 RLE) for `count` literals; its bytes.
func write_plain_literals_header(out: u8[], kind: u32, count: usize) -> usize:
    if count < 32:
        out[0] = (u8)((count << 3) | (usize)kind)
        return 1
    if count < 4096:
        let value = (count << 4) | (1 << 2) | (usize)kind
        out[0] = (u8)value
        out[1] = (u8)(value >> 8)
        return 2
    let value = (count << 4) | (3 << 2) | (usize)kind
    out[0] = (u8)value
    out[1] = (u8)(value >> 8)
    out[2] = (u8)(value >> 16)
    return 3

## How the encoder sends one sequence code kind.
struct KindChoice:
    var mode: u32
    var rle_code: u32
    var shares: i16[64]
    var symbols: u32
    var log: u32

extend Compressor:
    # mark: Literals ==========================================================================

    ## The literals section into `out`; its bytes.
    func write_literals(out: u8[]) -> usize:
        let count = self.literal_count
        let literals = self.literals[..<count]
        var counts: u32[256]
        var top: usize = 0
        var distinct: u32 = 0
        for byte in literals:
            if counts[(usize)byte] == 0: distinct += 1
            counts[(usize)byte] += 1
            if (usize)byte > top: top = (usize)byte
        if distinct == 1 and count > 2:
            let header = write_plain_literals_header(out, 1, count)
            out[header] = literals[0]
            return header + 1
        if count >= 64 and distinct > 1:
            let coded = self.write_huffman_literals(out, &counts[0], top + 1)
            if coded > 0: return coded
        let header = write_plain_literals_header(out, 0, count)
        if count > 0: memory.copy(out[header..], literals, count)
        return header + count

    ## Huffman-coded literals into `out`, or 0 when that is not smaller than raw.
    func write_huffman_literals(out: u8[], counts: const u32*, symbols: usize) -> usize:
        let count = self.literal_count
        var lengths: u8[256]
        let most = huffman_lengths(counts, symbols, huffman_longest, &lengths[0])
        var codes: u16[256]
        huffman_codes(&lengths[0], symbols, most, &codes[0])
        var bits: u64 = 0
        for symbol in 0..<symbols: bits += (u64)counts[symbol] * (u64)lengths[symbol]
        let single = count < 256
        # The content goes after room for the longest header, then moves down.
        let room: usize = 5
        let tree = self.write_tree(out[room..], &lengths[0], symbols, most)
        if tree == 0 or (usize)(bits >> 3) + tree + 16 >= count: return 0
        var at = room + tree
        if single:
            at += write_stream(out[at..], self.literals[..<count], &codes[0], &lengths[0])
        else:
            let segment = (count + 3) // 4
            let table = at
            at += 6
            for part in 0..<(usize)4:
                let first = part * segment
                let last = first + segment if part < 3 else count
                let size = write_stream(out[at..], self.literals[first..<last], &codes[0], &lengths[0])
                if part < 3:
                    out[table + part * 2] = (u8)size
                    out[table + part * 2 + 1] = (u8)(size >> 8)
                at += size
        let packed = at - room
        if packed + 5 >= count: return 0
        # The header: sizes of 10, 14 or 18 bits.
        let largest = count if count > packed else packed
        var header: usize = 3
        var format: usize = 0 if single else 1
        if largest >= 16384:
            header = 5
            format = 3
        elif largest >= 1024:
            header = 4
            format = 2
        let value = (u64)2 | (u64)format << 2 | (u64)count << 4 | (u64)packed << (u64)(4 + (header * 8 - 4) // 2)
        for index in 0..<header: out[index] = (u8)(value >> (u64)(index * 8))
        memory.move(out[header..], out[room..<at], packed)
        return header + packed

    ## The tree description of `lengths` (longest `most`) into `out`; its bytes, or 0
    ## when it cannot be written.
    func write_tree(out: u8[], lengths: const u8*, symbols: usize, most: u32) -> usize:
        # Weights of every symbol but the last, whose weight the decoder infers.
        let count = symbols - 1
        var weights: u8[256]
        var tally: u32[16]
        var kinds: u32 = 0
        for symbol in 0..<count:
            let length = (u32)lengths[symbol]
            weights[symbol] = (u8)(most + 1 - length) if length > 0 else 0
            if tally[(usize)weights[symbol]] == 0: kinds += 1
            tally[(usize)weights[symbol]] += 1
        var best: usize = 0
        if count >= 2 and kinds >= 2:
            best = self.write_weights_fse(out, &weights[0], count, &tally[0], kinds)
        let direct = 1 + (count + 1) // 2
        if count <= 128 and (best == 0 or direct < best):
            out[0] = (u8)(127 + count)
            for index in 0..<(count + 1) // 2:
                let high = weights[index * 2]
                let low = weights[index * 2 + 1] if index * 2 + 1 < count else 0
                out[1 + index] = (high << 4) | low
            return direct
        return best

    ## Weights compressed with FSE into `out`; its bytes, or 0 when 127 or more.
    func write_weights_fse(out: u8[], weights: const u8*, count: usize, tally: const u32*, kinds: u32) -> usize:
        var shares: i16[16]
        let log = table_log((u32)count, kinds, 6)
        normalize(tally, 13, (u32)count, log, &shares[0])
        var top: u32 = 13
        while top > 0 and shares[(usize)top - 1] == 0: top -= 1
        var header: u8[64]
        let size = write_distribution(&shares[0], top, log, header)
        if size >= 64: return 0
        var coder = &self.coders[0].weights
        coder.build(&shares[0], top, log)
        # Room for the stream's worst case (6 bits a weight) before writing.
        if 1 + size + (count * 6 + 2 * 6) // 8 + 16 >= out.length: return 0
        memory.copy(out[1..], header[..<size], size)
        var writer = Writer.into(out[1 + size..])
        var lanes: u32[2]
        lanes[(count - 1) & 1] = coder.start((usize)weights[count - 1])
        lanes[(count - 2) & 1] = coder.start((usize)weights[count - 2])
        var index = count - 2
        while index > 0:
            index -= 1
            lanes[index & 1] = coder.put(&writer, lanes[index & 1], (usize)weights[index])
            writer.flush()
        coder.finish(&writer, lanes[1])
        writer.flush()
        coder.finish(&writer, lanes[0])
        let total = 1 + size + writer.close()
        if total > 128: return 0
        out[0] = (u8)(total - 1)
        return total

    # mark: Sequences =========================================================================

    ## The sequences section into `out`; its bytes.
    func write_sequences(out: u8[]) -> usize:
        let count = self.sequence_count
        var at: usize = 0
        if count < 128:
            out[0] = (u8)count
            at = 1
        elif count < 0x7F00:
            out[0] = (u8)((count >> 8) + 0x80)
            out[1] = (u8)count
            at = 2
        else:
            out[0] = 255
            out[1] = (u8)(count - 0x7F00)
            out[2] = (u8)((count - 0x7F00) >> 8)
            at = 3
        if count == 0: return at
        self.code_sequences()
        let literal_codes = self.codes[..<count]
        let offset_codes = self.codes[count..<2 * count]
        let match_codes = self.codes[2 * count..<3 * count]
        let modes_at = at
        at += 1
        let literal = choose_kind(literal_codes, max_literals_code, literals_most_log, literals_default, literals_default_log)
        at += write_kind(out[at..], &literal, &self.coders[0].literal_lengths)
        let offset = choose_kind(offset_codes, max_offset_code, offset_most_log, offset_default, offset_default_log)
        at += write_kind(out[at..], &offset, &self.coders[0].offsets)
        let matched = choose_kind(match_codes, max_match_code, match_most_log, match_default, match_default_log)
        at += write_kind(out[at..], &matched, &self.coders[0].match_lengths)
        out[modes_at] = (u8)((literal.mode << 6) | (offset.mode << 4) | (matched.mode << 2))
        return at + self.write_sequence_stream(out[at..], literal.mode == mode_rle, offset.mode == mode_rle, matched.mode == mode_rle)

    ## Codes for the block's sequences: literals length, offset and match length codes
    ## in thirds of `codes`, offset values (after repeat offsets) in `values`.
    func code_sequences():
        let count = self.sequence_count
        var repeat0 = self.repeats[0]
        var repeat1 = self.repeats[1]
        var repeat2 = self.repeats[2]
        for index in 0..<count:
            let sequence = self.sequences[index]
            let offset = sequence.offset
            var value = offset + 3
            if sequence.literals > 0:
                if offset == repeat0:
                    value = 1
                elif offset == repeat1:
                    value = 2
                elif offset == repeat2:
                    value = 3
            elif offset == repeat1:
                value = 1
            elif offset == repeat2:
                value = 2
            elif offset == repeat0 - 1:
                value = 3
            # The decoder's update of the recent offsets.
            if value > 3:
                repeat2 = repeat1
                repeat1 = repeat0
                repeat0 = offset
            else:
                let pick = value - 1 + (1 if sequence.literals == 0 else 0)
                if pick > 0:
                    if pick != 1: repeat2 = repeat1
                    repeat1 = repeat0
                    repeat0 = offset
            self.values[index] = value
            self.codes[index] = (u8)literals_code(sequence.literals)
            self.codes[count + index] = (u8)high_bit(value)
            self.codes[2 * count + index] = (u8)match_code(sequence.length)
        self.repeats = [repeat0, repeat1, repeat2]

    ## The sequences' bit stream into `out`, from the last sequence back; its bytes.
    func write_sequence_stream(out: u8[], literal_rle: bool, offset_rle: bool, match_rle: bool) -> usize:
        let count = self.sequence_count
        let coders = &self.coders[0]
        var writer = Writer.into(out)
        let last = count - 1
        var literal_state: u32 = 0
        var offset_state: u32 = 0
        var match_state: u32 = 0
        if not match_rle: match_state = coders.match_lengths.start((usize)self.codes[2 * count + last])
        if not offset_rle: offset_state = coders.offsets.start((usize)self.codes[count + last])
        if not literal_rle: literal_state = coders.literal_lengths.start((usize)self.codes[last])
        self.put_extras(&writer, last)
        var index = last
        while index > 0:
            index -= 1
            if not offset_rle: offset_state = coders.offsets.put(&writer, offset_state, (usize)self.codes[count + index])
            if not match_rle: match_state = coders.match_lengths.put(&writer, match_state, (usize)self.codes[2 * count + index])
            if not literal_rle: literal_state = coders.literal_lengths.put(&writer, literal_state, (usize)self.codes[index])
            writer.flush()
            self.put_extras(&writer, index)
        if not match_rle: coders.match_lengths.finish(&writer, match_state)
        writer.flush()
        if not offset_rle: coders.offsets.finish(&writer, offset_state)
        writer.flush()
        if not literal_rle: coders.literal_lengths.finish(&writer, literal_state)
        return writer.close()

    ## Sequence `index`'s extra bits: literals length, match length, then offset.
    inline func put_extras(writer: Writer*, index: usize):
        let count = self.sequence_count
        let sequence = self.sequences[index]
        let literal_code = (usize)self.codes[index]
        let length_code = (usize)self.codes[2 * count + index]
        writer.add((u64)(sequence.literals - literals_bases[literal_code]), (u32)literals_extras[literal_code])
        writer.add((u64)(sequence.length - match_bases[length_code]), (u32)match_extras[length_code])
        writer.flush()
        let offset_code = (u32)self.codes[count + index]
        writer.add((u64)self.values[index], offset_code)
        writer.flush()

## How to send `codes` (all at most `most_code`): RLE for one code, else the predefined
## table or a new one of log at most `most_log`, whichever costs fewer bits.
func choose_kind(codes: const u8[], most_code: u32, most_log: u32, defaults: const i16[], default_log: u32) -> KindChoice:
    var choice: KindChoice
    var counts: u32[64]
    var distinct: u32 = 0
    var top: u32 = 0
    for code in codes:
        if counts[(usize)code] == 0: distinct += 1
        counts[(usize)code] += 1
        if (u32)code + 1 > top: top = (u32)code + 1
    if distinct == 1:
        choice.mode = mode_rle
        choice.rle_code = top - 1
        return choice
    let total = (u32)codes.length
    choice.log = table_log(total, distinct, most_log)
    normalize(&counts[0], top, total, choice.log, &choice.shares[0])
    choice.symbols = top
    var header: u8[128]
    let header_bits = (u64)write_distribution(&choice.shares[0], top, choice.log, header) * 8 * 256
    let own = (coded_cost(&counts[0], top, &choice.shares[0], top, choice.log) else 0xFFFFFFFFFFFF) + header_bits
    choice.mode = mode_compressed
    if let predefined = coded_cost(&counts[0], top, defaults.data, (u32)defaults.length, default_log):
        if predefined <= own:
            choice.mode = mode_predefined
            for index in 0..<defaults.length: choice.shares[index] = defaults[index]
            choice.symbols = (u32)defaults.length
            choice.log = default_log
    return choice

## A kind's table into `out` (none for predefined) and its coder; the table's bytes.
func write_kind(out: u8[], choice: const KindChoice*, coder: Coder*) -> usize:
    if choice.mode == mode_rle:
        out[0] = (u8)choice.rle_code
        return 1
    coder.build(&choice.shares[0], choice.symbols, choice.log)
    if choice.mode == mode_predefined: return 0
    return write_distribution(&choice.shares[0], choice.symbols, choice.log, out)

## A literals stream: `literals` coded from the last back into `out`; its bytes.
func write_stream(out: u8[], literals: const u8[], codes: const u16*, lengths: const u8*) -> usize:
    var writer = Writer.into(out)
    var index = literals.length
    while index >= 4:
        for _ in 0..<(usize)4:
            index -= 1
            let symbol = (usize)literals[index]
            writer.add((u64)codes[symbol], (u32)lengths[symbol])
        writer.flush()
    while index > 0:
        index -= 1
        let symbol = (usize)literals[index]
        writer.add((u64)codes[symbol], (u32)lengths[symbol])
        writer.flush()
    return writer.close()