Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.1

0.9.1 / src / brotli / window.lucb

#==============================================================================================
#
#   brotli/window - The sliding window, its output, copies and dictionary words
#
#   DESCRIPTION:
#       Output is decoded into a ring of a power of two bytes, never more than the
#       stream's window, with `slack` bytes past its end for a dictionary word or a
#       copy's eight-byte overshoot. The ring starts small and doubles while it has not
#       wrapped, so a short stream holds little memory. Once it is the window's size, each
#       time it fills its bytes must have gone to the caller's output before it wraps: a
#       caller giving no room stalls the decoder there (`need_output`). The 16 bytes past
#       the write position are always out of reach of a copy (the format's window is the
#       ring less 16), so copies may overrun by a word.
#
#==============================================================================================

## Bytes past the ring's end: a transformed dictionary word (at most 37) or a copy's
## overshoot (at most 7) may land there before the ring wraps.
let slack: usize = 64

## The ring's least size.
let least_ring: usize = 1024

extend Decoder:
    ## Make the ring ready for a meta-block of `length` bytes: a first ring that holds
    ## the whole stream when this block is its last.
    func prepare_ring(length: usize, last: bool) -> !:
        if self.ring.length > 0:
            return
        var size = least_ring
        let wanted = length if last else 65536
        while size < wanted and size < self.window:
            size *= 2
        if size > self.window:
            size = self.window
        try self.resize_ring(size)

    ## A ring of `size` bytes holding the output so far (the ring has not wrapped).
    func resize_ring(size: usize) -> !:
        let ring = try new u8[size + slack] --- in memory.heap
        memory.set(ring[size..], 0)
        if self.pos > 0:
            memory.copy(ring, self.ring[..<self.pos], self.pos)
        if self.ring.length > 0:
            free(self.ring) in memory.heap
        self.ring = ring
        self.ring_size = size

    ## The ring is full (`pos` at or past its size): double it, or hand its bytes on and
    ## wrap. False when the caller's output has no room for them.
    func room() -> bool!:
        if self.pos < self.ring_size:
            return true
        if not self.wrapped and self.ring_size < self.window:
            try self.resize_ring(self.ring_size * 2)
            return true
        self.flush()
        if self.flushed < self.ring_size:
            return false
        # Bytes past the end (a word's) were handed on with the rest; they move to the
        # ring's start, where they belong.
        let over = self.pos - self.ring_size
        if over > 0:
            memory.copy(self.ring, self.ring[self.ring_size..<self.pos], over)
        self.pos = over
        self.flushed -= self.ring_size
        self.wrapped = true
        return true

    ## Hand decoded bytes on to the caller's output, as many as it has room for. Bytes past
    ## the ring's end follow its last in memory, so they go in order too.
    func flush():
        var count = self.pos - self.flushed
        let space = self.output.length - self.produced
        if count > space:
            count = space
        if count == 0:
            return
        memory.copy(self.output[self.produced..], self.ring[self.flushed..<self.flushed + count], count)
        self.flushed += count
        self.produced += count

    ## Whether decoded bytes wait for the caller's output.
    func pending() -> bool:
        return self.pos > self.flushed

    ## The last two bytes of output, after a copy, a word or raw bytes.
    func recall():
        let mask = self.ring_size - 1
        # Bytes past the ring's end (a word before the ring wraps) are read where they are.
        self.p1 = 0
        self.p2 = 0
        if self.total_out >= 1:
            self.p1 = self.ring[self.pos - 1] if self.pos >= 1 else self.ring[mask]
        if self.total_out >= 2:
            self.p2 = self.ring[self.pos - 2] if self.pos >= 2 else self.ring[(self.pos -% 2) & mask]

    # mark: Copies ============================================================================

    ## Copy `copy_left` bytes from `distance` back; false when stalled for output room.
    func copy_bytes() -> bool!:
        while self.copy_left > 0:
            if self.pos >= self.ring_size and not try self.room():
                return false
            let mask = self.ring_size - 1
            let back = (self.pos -% self.distance) & mask
            let count = self.copy_left
            if self.pos + count <= self.ring_size and back + count <= self.ring_size:
                copy_match(self.ring.data, self.pos, back, count, self.distance)
                self.pos += count
                self.copy_left = 0
                break
            # Across the ring's end: a byte at a time up to it.
            var n: usize = 0
            while n < count and self.pos < self.ring_size:
                self.ring[self.pos] = self.ring[(self.pos -% self.distance) & mask]
                self.pos += 1
                n += 1
            self.copy_left -= n
        self.recall()
        return true

    # mark: Uncompressed and metadata bytes ===================================================

    ## The bytes of an uncompressed meta-block (`keep`) or of metadata; false when the
    ## input ran out or the output has no room.
    func raw(keep: bool) -> bool!:
        while self.remaining > 0:
            if keep and self.pos >= self.ring_size and not try self.room():
                return false
            var room = self.remaining
            if keep and self.ring_size - self.pos < room:
                room = self.ring_size - self.pos
            if self.bits >= 8:
                # Bytes the bit reader read ahead come first.
                let byte = (u8)self.take(8)
                if keep:
                    self.ring[self.pos] = byte
                    self.pos += 1
                    self.total_out += 1
                self.remaining -= 1
                continue
            let data = self.input
            var count = data.length - self.input_at
            if count == 0:
                if self.final_input:
                    error(corrupt, "truncated brotli stream")
                return false
            if count > room:
                count = room
            if keep:
                memory.copy(self.ring[self.pos..], data[self.input_at..<self.input_at + count], count)
                self.pos += count
                self.total_out += (u64)count
            self.input_at += count
            self.remaining -= count
        if keep:
            self.recall()
        self.state = state_meta_done
        return true

## Copy `count` bytes in `ring` from `back` to `to`, `distance` back (the source wraps
## ahead of `to` when `back > to`, never within 16 bytes of it). Writes may run up to 7
## bytes past `to + count`.
inline func copy_match(ring: u8*, to: usize, back: usize, count: usize, distance: usize):
    let target = ring + to
    let source = ring + back
    if distance >= 8 or back > to:
        var n: usize = 0
        while n < count:
            memory.write[u64](target + n, memory.read[u64](source + n))
            n += 8
    elif distance == 1:
        memory.set(u8[](target, count), *source)
    else:
        # A short period: its first eight-or-more bytes one by one, then words from that
        # far back (a multiple of the period).
        let period = distance * ((8 + distance - 1) // distance)
        var n: usize = 0
        while n < period and n < count:
            target[n] = source[n]
            n += 1
        while n < count:
            memory.write[u64](target + n, memory.read[u64](target + (n - period)))
            n += 8

# mark: Dictionary words ====================================================================

## Write at `target` (room for 37 bytes) the dictionary word that `distance` names for a
## copy of `length` (section 8), `reach` being the farthest a copy may go; its length.
func write_word(target: u8*, distance: u64, length: usize, reach: u64) -> usize!:
    if length < 4 or length > 24:
        error(corrupt, "invalid brotli dictionary reference length")
    let id = distance - reach - 1
    let bits = (u64)word_bits[length]
    let index = (usize)(id & (((u64)1 << bits) - 1))
    let transform = (usize)(id >> bits)
    if transform >= 121:
        error(corrupt, "invalid brotli dictionary transform")
    let source = (u8*)&words[0] + (usize)word_offsets[length] + index * length
    if transform == 0:
        # The word itself, a word at a time (the dictionary ends in a word of padding).
        var n: usize = 0
        while n < length:
            memory.write[u64](target + n, memory.read[u64](source + n))
            n += 8
        return length
    let written = transform_word(target, u8[](source, length), transform)
    if written == 0 and distance <= 120:
        # Google's decoder rejects these: they could repeat without progress.
        error(corrupt, "empty brotli dictionary word")
    return written

## Apply transform `id` to `word` into `target` (room for 37 bytes); the bytes written.
func transform_word(target: u8*, word: const u8[], id: usize) -> usize:
    let at = id * 5
    let kind = (usize)transforms[at + 2]
    var n: usize = 0
    for i in 0..<(usize)transforms[at + 1]:
        target[n] = affixes[(usize)transforms[at] + i]
        n += 1
    var first: usize = 0
    var end = word.length
    if kind >= 3 and kind <= 11:
        first = kind - 2 if kind - 2 < end else end
    elif kind >= 12:
        end = end - (kind - 11) if kind - 11 < end else 0
    let start = n
    for i in first..<end:
        target[n] = word[i]
        n += 1
    if kind == 1 or kind == 2:
        # Ferment: upper-case ASCII letters; flip a bit of UTF-8 sequences.
        var i = start
        while i < n:
            let step = ferment(target, i, n)
            if kind == 1:
                break
            i += step
    for i in 0..<(usize)transforms[at + 4]:
        target[n] = affixes[(usize)transforms[at + 3] + i]
        n += 1
    return n

## Upper-case the character at `at` (before `end`) as RFC 7932's Ferment does; its bytes.
func ferment(text: u8*, at: usize, end: usize) -> usize:
    let byte = text[at]
    if byte < 192:
        if byte >= 97 and byte <= 122:
            text[at] = byte ^ 32
        return 1
    if byte < 224:
        if at + 1 < end:
            text[at + 1] ^= 32
        return 2
    if at + 2 < end:
        text[at + 2] ^= 5
    return 3