Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.0

0.9.0 / src / brotli / fast.lucb

#==============================================================================================
#
#   brotli/fast - Whole commands with the bit reader and window in locals
#
#   DESCRIPTION:
#       While the input holds eight more bytes at every refill and a command's literals
#       and copy fit the ring without wrapping, `fast` decodes command after command
#       without the resumable units: an eight-byte refill never runs short, so no unit can
#       read past the input and nothing needs undoing. Its state lives in locals and goes
#       back to the decoder whenever it stops, which is at the boundary of a step the
#       resumable states (commands.lucb) take over from: a command, its copy length, the
#       literals left of one, a distance, a copy, a word at the ring's end or the end of
#       the meta-block.
#       Block switches, rarer, go through those states' own code. Its arithmetic wraps and
#       its shift counts are masked where the format already bounds them, so they need no
#       checks.
#
#==============================================================================================

## The table entry for the code at the bottom of `acc`: its symbol << 16 | its length.
inline func entry_at(table: const u32*, acc: u64) -> u32:
    let entry = table[(usize)(acc & 255)]
    let length = entry & 255
    if length <= 8:
        return entry
    let index = (usize)(entry >> 16) +% (usize)((acc >> 8) & (((u64)1 << (u64)((length -% 8) & 63)) -% 1))
    let second = table[index]
    return (second & 0xFFFF0000) | ((second & 255) +% 8)

## The low `count` bits of `acc`.
inline func low_bits(acc: u64, count: u32) -> u64:
    return acc & (((u64)1 << (u64)(count & 63)) -% 1)

extend Decoder:
    ## Decode commands from `state_command` while the input and the ring allow; the state
    ## to go on from is left in `state`.
    func fast() -> !:
        let data = self.input.data
        let length = self.input.length
        let ring = self.ring.data
        let size = self.ring_size
        let trees = self.trees.data
        let lookup = &context_lookup[0]
        let literal_tables = &self.literal_tables[0]
        var acc = self.acc
        var bits = self.bits
        var at = self.input_at
        var pos = self.pos
        var p1 = (usize)self.p1
        var p2 = (usize)self.p2
        var remaining = self.remaining
        var total = self.total_out
        var stop = state_command
        while true:
            # A command: insert-and-copy symbol, insert and copy extra bits (39 + 24).
            if self.block_left[1] == 0 or at +% 8 > length:
                break
            if bits < 39:
                acc |= memory.read[u64](data + at) << (u64)(bits & 63)
                at +%= (usize)((63 -% bits) >> 3)
                bits |= 56
            let entry = entry_at(trees + (usize)self.command_codes[(usize)self.type_now[1]], acc)
            acc >>= (u64)(entry & 63)
            bits -%= entry & 255
            let code = entry >> 16
            let cell = (usize)(code >> 6)
            let insert_code = (usize)(cell_insert[cell] + ((code >> 3) & 7))
            let insert_bits = insert_extra[insert_code]
            var insert = (usize)insert_base[insert_code] +% (usize)low_bits(acc, insert_bits)
            acc >>= (u64)(insert_bits & 63)
            bits -%= insert_bits
            self.block_left[1] -= 1
            let copy_code = cell_copy[cell] + (code & 7)
            if bits < 24:
                if at +% 8 > length:
                    self.insert_left = insert
                    self.copy_code = copy_code
                    self.implicit = code < 128
                    stop = state_copy_length
                    break
                acc |= memory.read[u64](data + at) << (u64)(bits & 63)
                at +%= (usize)((63 -% bits) >> 3)
                bits |= 56
            let copy_bits = copy_extra[(usize)copy_code]
            let copy_length = (usize)copy_base[(usize)copy_code] +% (usize)low_bits(acc, copy_bits)
            acc >>= (u64)(copy_bits & 63)
            bits -%= copy_bits
            if insert > remaining:
                error(corrupt, "brotli literals overrun their meta-block")
            self.copy_length = copy_length
            self.implicit = code < 128
            remaining -= insert
            total +%= (u64)insert
            if pos +% insert > size:
                self.insert_left = insert
                stop = state_insert
                break
            # The literals, each by the code its block type and the last two bytes select.
            let mode = self.literal_mode
            var left = self.block_left[0]
            while insert > 0 and left > 0:
                if bits < 15:
                    if at +% 8 > length:
                        break
                    acc |= memory.read[u64](data + at) << (u64)(bits & 63)
                    at +%= (usize)((63 -% bits) >> 3)
                    bits |= 56
                let context = (usize)(lookup[mode +% p1] | lookup[mode +% 256 +% p2])
                let literal = entry_at(trees + (usize)literal_tables[context], acc)
                acc >>= (u64)(literal & 63)
                bits -%= literal & 255
                let byte = (u8)(literal >> 16)
                ring[pos] = byte
                pos +%= 1
                p2 = p1
                p1 = (usize)byte
                left -%= 1
                insert -%= 1
            self.block_left[0] = left
            if insert > 0:
                # A literal block switch, or the input near its end: the state takes the rest.
                self.insert_left = insert
                stop = state_insert
                break
            if remaining == 0:
                stop = state_meta_done
                break
            # The distance: the last one, or a symbol and its extra bits (15 + 24).
            var distance: i64 = 0
            var symbol: u32 = 0
            if self.implicit:
                distance = self.distances[self.distance_at & 3]
            else:
                if self.block_left[2] == 0 or (bits < 39 and at +% 8 > length):
                    stop = state_distance
                    break
                if bits < 39:
                    acc |= memory.read[u64](data + at) << (u64)(bits & 63)
                    at +%= (usize)((63 -% bits) >> 3)
                    bits |= 56
                let context = copy_length -% 2 if copy_length < 5 else 3
                let found = entry_at(trees + (usize)self.distance_codes[(usize)self.maps[self.distance_map + context]], acc)
                acc >>= (u64)(found & 63)
                bits -%= found & 255
                symbol = found >> 16
                self.block_left[2] -= 1
                if symbol < 16:
                    let slot = (self.distance_at -% (usize)short_slot[(usize)symbol]) & 3
                    distance = self.distances[slot] + short_delta[(usize)symbol]
                    if distance <= 0:
                        error(corrupt, "invalid brotli distance")
                elif symbol < 16 + self.direct:
                    distance = (i64)symbol - 15
                else:
                    let d = symbol - self.direct - 16
                    let extra_bits = 1 + (d >> (self.postfix + 1))
                    let extra = low_bits(acc, extra_bits)
                    acc >>= (u64)(extra_bits & 63)
                    bits -%= extra_bits
                    let offset = ((2 + (u64)((d >> self.postfix) & 1)) << (u64)extra_bits) - 4
                    let low = (u64)(d & (((u32)1 << self.postfix) - 1))
                    distance = (i64)(((offset + extra) << (u64)self.postfix) + low + (u64)self.direct + 1)
            let most = (u64)self.window - 16
            let reach = total if total < most else most
            if (u64)distance > reach:
                # A dictionary word, at most 37 bytes: past the ring's end it may be, as long
                # as it starts within it (the next command finds the ring full).
                if (u64)distance > most_distance:
                    error(corrupt, "invalid brotli distance")
                if pos >= size:
                    self.distance = (usize)distance
                    stop = state_word
                    break
                let written = try write_word(ring + pos, (u64)distance, copy_length, reach)
                if written > remaining:
                    error(corrupt, "brotli dictionary word overruns its meta-block")
                pos +%= written
                remaining -= written
                total +%= (u64)written
                if written >= 2:
                    p1 = (usize)ring[pos -% 1]
                    p2 = (usize)ring[pos -% 2]
                elif written == 1:
                    p2 = p1
                    p1 = (usize)ring[pos -% 1]
                if remaining == 0:
                    stop = state_meta_done
                    break
                continue
            if symbol != 0:
                self.distance_at +%= 1
                self.distances[self.distance_at & 3] = distance
            if copy_length > remaining:
                error(corrupt, "brotli copy overruns its meta-block")
            let back = (usize)distance
            remaining -= copy_length
            total +%= (u64)copy_length
            let source = (pos -% back) & (size -% 1)
            if pos +% copy_length > size or source +% copy_length > size:
                # Across the ring's end: the copy state goes a byte at a time.
                self.distance = back
                self.copy_left = copy_length
                stop = state_copy
                break
            copy_match(ring, pos, source, copy_length, back)
            pos +%= copy_length
            p1 = (usize)ring[pos -% 1]
            p2 = (usize)ring[pos -% 2]
            if remaining == 0:
                stop = state_meta_done
                break
        self.acc = acc
        self.bits = bits
        self.input_at = at
        self.pos = pos
        self.p1 = (u8)p1
        self.p2 = (u8)p2
        self.remaining = remaining
        self.total_out = total
        self.state = stop