Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.1

0.9.1 / src / flate / inflate.lucb

#==============================================================================================
#
#   flate/inflate - The decoder
#
#   DESCRIPTION:
#       Symbols decode through a 12-bit table on the next bits of a 64-bit buffer,
#       refilled eight bytes at a time; an entry holds the code length, the kind
#       (literal, length or distance, end of block), the base value and its extra
#       bits. Longer codes, rare in practice,, walk the canonical code. Matches copy
#       eight bytes at a time when they are eight or more back.
#
#==============================================================================================

let length_base: u16[29] = [3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258]
let length_extra: u8[29] = [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0]
let distance_base: u16[30] = [1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577]
let distance_extra: u8[30] = [0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13]
let code_order: usize[19] = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]

let literal_kind: u32 = 0
let match_kind: u32 = 1
let end_kind: u32 = 2
let invalid_kind: u32 = 3

## One alphabet's decoding table: (value << 16) | (extra << 8) | (kind << 4) | length
## by the next 12 bits (length 0: a longer code), and the canonical code for those.
struct Table:
    var fast: u32[4096]
    var counts: u16[16]
    var symbols: u16[320]
    ## 0 literal/length, 1 distance, 2 code lengths.
    var alphabet: u32

    ## The entry of `symbol`, the code length left out.
    func entry(symbol: usize) -> u32:
        if self.alphabet == 2:
            return (u32)symbol << 16
        if self.alphabet == 1:
            if symbol >= 30:
                return invalid_kind << 4
            return ((u32)distance_base[symbol] << 16) | ((u32)distance_extra[symbol] << 8) | (match_kind << 4)
        if symbol < 256:
            return ((u32)symbol << 16) | (literal_kind << 4)
        if symbol == 256:
            return end_kind << 4
        if symbol > 285:
            return invalid_kind << 4
        return ((u32)length_base[symbol - 257] << 16) | ((u32)length_extra[symbol - 257] << 8) | (match_kind << 4)

    ## Build from code lengths. Only the code-length alphabet must be complete; a
    ## lone one-bit code or no codes at all is accepted, as zlib does.
    func build(lengths: const u8[], alphabet: u32) -> !:
        self.alphabet = alphabet
        memory.set(u8[]((u8*)&self.fast[0], 16384), 0)
        for n in 0..<(usize)16:
            self.counts[n] = 0
        for length in lengths:
            if length > 15:
                error(corrupt, "invalid Huffman code length")
            self.counts[(usize)length] += 1
        self.counts[0] = 0
        var left: i32 = 1
        var offsets: u16[16]
        var next: u32[16]
        var code: u32 = 0
        for n in 1..<(usize)16:
            left = left * 2 - (i32)self.counts[n]
            if left < 0:
                error(corrupt, "oversubscribed Huffman tree")
            code = (code + (u32)self.counts[n - 1]) << 1
            next[n] = code
            if n < 15:
                offsets[n + 1] = offsets[n] + self.counts[n]
        var present: u32 = 0
        for n in 1..<(usize)16:
            present += (u32)self.counts[n]
        if left > 0 and (alphabet == 2 or (present > 0 and (present != 1 or self.counts[1] != 1))):
            error(corrupt, "incomplete Huffman tree")
        for i in 0..<lengths.length:
            let length = (usize)lengths[i]
            if length == 0:
                continue
            self.symbols[(usize)offsets[length]] = (u16)i
            offsets[length] += 1
            let c = next[length]
            next[length] += 1
            if length <= 12:
                # The table is indexed by the code's bits in stream order: reversed.
                var reversed: u32 = 0
                for b in 0..<length:
                    reversed = (reversed << 1) | ((c >> (u32)b) & 1)
                let e = self.entry(i) | (u32)length
                var at = (usize)reversed
                while at < 4096:
                    self.fast[at] = e
                    at += (usize)1 << length

    ## The entry for a code longer than 12 bits at the bottom of `acc`, with its
    ## length; length 0 when no code matches.
    func slow(acc: u64) -> u32:
        var code: i32 = 0
        var first: i32 = 0
        var index: i32 = 0
        for length in 1..<(usize)16:
            code |= (i32)((acc >> (u64)(length - 1)) & 1)
            let count = (i32)self.counts[length]
            if code - first < count:
                return self.entry((usize)self.symbols[(usize)(index + code - first)]) | (u32)length
            index += count
            first = (first + count) << 1
            code <<= 1
        return 0

## Input bits, least significant first, read eight bytes ahead; past the end the
## buffer fills with zeros, counted in `padded`.
struct Stream:
    var data: const u8*
    var length: usize
    var pos: usize
    var acc: u64
    var bits: u32
    var padded: u32
    ## Where the input goes on once `data` is read, and the bytes read before it.
    var more: More?
    var context: void*?
    var base: usize

    func refill():
        if self.pos + 8 <= self.length:
            self.acc |= memory.read[u64](self.data + self.pos) << (u64)self.bits
            self.pos += (usize)((63 - self.bits) >> 3)
            self.bits |= 56
            return
        while self.bits <= 56:
            if self.pos < self.length or self.next_piece():
                self.acc |= (u64)self.data[self.pos] << (u64)self.bits
                self.pos += 1
            else:
                self.padded += 8
            self.bits += 8

    func take(count: u32) -> u32:
        if self.bits < count:
            self.refill()
        let value = (u32)(self.acc & (((u64)1 << (u64)count) - 1))
        self.acc >>= (u64)count
        self.bits -= count
        return value

    ## Whether decoding read past the input.
    func overrun() -> bool:
        return self.bits < self.padded

    ## Input bytes consumed, over every piece: whole bytes still in the buffer go back.
    func consumed() -> usize:
        return self.base + self.pos - (usize)((self.bits - self.padded) >> 3) if self.bits >= self.padded else self.base + self.pos

    ## The next piece of input, if `more` has one.
    func next_piece() -> bool:
        let more = self.more else return false
        let piece = more(self.context)
        if piece.length == 0:
            self.more = none
            return false
        self.base += self.length
        self.data = piece.data
        self.length = piece.length
        self.pos = 0
        return true

    ## Whether every byte of input has been read.
    func ended() -> bool:
        return self.more == none and self.consumed() >= self.base + self.length

## Inflate the raw DEFLATE stream in `data` into exactly `output`, returning the
## input bytes it used. It stops after a final block, or after a block that ends
## with the input (a segment ending in a sync flush). `progress`, when given, hears
## of every 256 KiB of output and of the end.
pub func inflate_raw(data: const u8[], output: u8[], progress: Progress? = none, context: void*? = none) -> usize!:
    var slide = Slide(deliver = none, context = none, base = 0, total = output.length, start = 0)
    return try inflate_through(data, none, output, &slide, progress, context)

## Inflate the raw DEFLATE stream in `data` into `output`, at most its
## length: the input bytes used and the output bytes made.
pub func inflate_raw_bounded(data: const u8[], output: u8[]) -> (usize, usize)!:
    var slide = Slide(deliver = none, context = none, base = 0, total = output.length, start = 0, open = true)
    let used = try inflate_through(data, none, output, &slide, none, none)
    return (used, slide.produced)

## Inflate the raw DEFLATE stream in `data`, `total` bytes of output, through
## `through` rather than one buffer the size of it all: each time it
## fills, the bytes not yet handed on go to `deliver`, and the last 32 KiB (all a
## match can reach back) move to its start. The last bytes go at the end. So a
## decoder of a large stream holds a window, not the whole output. It
## takes at least 64 KiB; a few hundred KiB keeps the calls few. The input
## can come in pieces too: once `data` is read, `more` gives the next (empty
## at the end), as a PNG's IDAT chunks, without joining them. Returns the
## input bytes used, over every piece.
pub func inflate_raw_windowed(data: const u8[], through: u8[], total: usize, deliver: Deliver, context: void*?, more: More? = none) -> usize!:
    if through.length < minimum_window:
        error(invalid, "an inflate window takes at least 64 KiB")
    var slide = Slide(deliver = deliver, context = context, base = 0, total = total, start = 0)
    return try inflate_through(data, more, through, &slide, none, context)

## Gives a windowed inflate its next piece of input; an empty one at the end.
pub type More = func(void*?) -> const u8[]

## Hears of a windowed inflate's output: the context and bytes that are valid
## only during the call.
pub type Deliver = func(void*?, const u8[]) -> unit!

## The smallest window: the 32 KiB kept, and room past it for more than a match.
let minimum_window: usize = 65536 + 2 * slack

## Room a decode step may need past the check before it: two literals or a
## match of 258, with an 8-byte copy's overshoot.
let slack: usize = 274

## Where a windowed inflate's output goes; `deliver` none for one whole buffer.
struct Slide:
    var deliver: Deliver?
    var context: void*?
    ## Output bytes made before the window's start; the whole stream's output.
    var base: usize
    var total: usize
    ## The first byte in the window not yet delivered.
    var start: usize
    ## `total` is a limit rather than the exact length.
    var open: bool = false
    ## The whole stream's output, once finished.
    var produced: usize = 0

    ## The window's end the decoder stops short of to slide it.
    func edge(size: usize) -> usize:
        return size if self.deliver == none else size - slack

    ## Hand on what is new in `through[..<o]` and keep its last 32 KiB at its
    ## start; the new output position.
    func advance(through: u8[], o: usize) -> usize!:
        let deliver = self.deliver else error(corrupt, "deflate stream is longer than its output")
        try deliver(self.context, through[self.start..<o])
        let keep = window if o > window else o
        memory.copy(through, through[o - keep..<o], keep)
        self.base += o - keep
        self.start = keep
        if self.base + keep > self.total:
            error(corrupt, "deflate stream is longer than its output")
        return keep

    ## The end: the rest handed on, and the output its promised length.
    func finish(through: u8[], o: usize) -> !:
        if self.base + o != self.total and not self.open:
            error(corrupt, "deflate stream is shorter than its output")
        self.produced = self.base + o
        if let deliver = self.deliver:
            try deliver(self.context, through[self.start..<o])

## Inflate into `output`, whole or as the window `slide` says.
func inflate_through(data: const u8[], more: More?, output: u8[], slide: Slide*, progress: Progress?, context: void*?) -> usize!:
    let tables = try new Table[3] in memory.heap
    defer free(tables) in memory.heap
    var s = Stream(data = data.data, length = data.length, pos = 0, acc = 0, bits = 0, padded = 0, more = more, context = context, base = 0)
    let edge = slide.edge(output.length)
    var o: usize = 0
    var next_report: usize = 262144
    while true:
        let final_block = s.take(1)
        let kind = s.take(2)
        if kind == 0:
            # Stored: to a byte boundary, then LEN, NLEN and the bytes.
            _ = s.take(s.bits & 7)
            var count = (usize)s.take(16)
            let check = (usize)s.take(16)
            if s.overrun():
                error(corrupt, "truncated deflate stream")
            if check != (count ^ 65535):
                error(corrupt, "invalid stored deflate block")
            while count > 0:
                if o >= edge:
                    o = try slide.advance(output, o)
                let room = output.length - o
                if room == 0:
                    error(corrupt, "stored deflate block overruns its buffers")
                if s.bits > s.padded:
                    # Bytes the bit buffer read ahead come first.
                    output[o] = (u8)s.take(8)
                    o += 1
                    count -= 1
                    continue
                if s.padded > 0 or (s.pos >= s.length and not s.next_piece()):
                    error(corrupt, "truncated deflate stream")
                # The buffer is empty; what a refill read ahead past it is read again.
                s.acc = 0
                var part = count if count < room else room
                part = part if part < s.length - s.pos else s.length - s.pos
                memory.copy(output[o..], u8[]((u8*)(s.data + s.pos), part), part)
                s.pos += part
                o += part
                count -= part
        elif kind == 3:
            error(corrupt, "reserved deflate block type")
        else:
            if kind == 1:
                try fixed_tables(&tables[0], &tables[1])
            else:
                try dynamic_tables(&s, &tables[0], &tables[1], &tables[2])
            o = try decode_block(&s, &tables[0], &tables[1], output, o, edge, slide, progress, context, &next_report)
        if s.overrun():
            error(corrupt, "truncated deflate stream")
        if final_block == 1 or s.ended():
            break
    try slide.finish(output, o)
    if let report = progress:
        report(context, o)
    return s.consumed()

func fixed_tables(literals: Table*, distances: Table*) -> !:
    var lengths: u8[288]
    for i in 0..<(usize)288:
        lengths[i] = 8 if i < 144 else 9 if i < 256 else 7 if i < 280 else 8
    try literals.build(lengths, 0)
    # All 32 five-bit codes, though 30 and 31 never occur.
    var short: u8[32]
    for i in 0..<(usize)32:
        short[i] = 5
    try distances.build(short, 1)

func dynamic_tables(s: Stream*, literals: Table*, distances: Table*, codes: Table*) -> !:
    let nlit = (usize)s.take(5) + 257
    let ndist = (usize)s.take(5) + 1
    let ncode = (usize)s.take(4) + 4
    if nlit > 286 or ndist > 30:
        error(corrupt, "too many deflate codes")
    var code_lengths: u8[19]
    for i in 0..<ncode:
        code_lengths[code_order[i]] = (u8)s.take(3)
    try codes.build(code_lengths, 2)
    var lengths: u8[320]
    var n: usize = 0
    while n < nlit + ndist:
        if s.bits < 16:
            s.refill()
        var e = codes.fast[(usize)(s.acc & 2047)]
        if e & 15 == 0:
            e = codes.slow(s.acc)
            if e & 15 == 0:
                error(corrupt, "invalid Huffman symbol")
        s.acc >>= (u64)(e & 15)
        s.bits -= e & 15
        let symbol = e >> 16
        if symbol < 16:
            lengths[n] = (u8)symbol
            n += 1
            continue
        if symbol == 16 and n == 0:
            error(corrupt, "deflate repeat has no previous length")
        let count = (usize)s.take(2 if symbol == 16 else 3 if symbol == 17 else 7) + (11 if symbol == 18 else 3)
        if count > nlit + ndist - n:
            error(corrupt, "deflate code repeat exceeds table")
        let value = lengths[n - 1] if symbol == 16 else 0
        for i in 0..<count:
            lengths[n + i] = value
        n += count
    if lengths[256] == 0:
        error(corrupt, "deflate tree lacks end marker")
    try literals.build(lengths[..<nlit], 0)
    try distances.build(lengths[nlit..<nlit + ndist], 1)

## Decode one Huffman block into `output` from `o`; the new output position.
## Past `edge` the window slides first (a whole buffer's limit is its end).
func decode_block(s: Stream*, literals: const Table*, distances: const Table*, output: u8[], start: usize, edge: usize, slide: Slide*, progress: Progress?, context: void*?, next_report: usize*) -> usize!:
    let out = output.data
    let size = output.length
    let lit = &literals.fast[0]
    let dist = &distances.fast[0]
    var o = start
    var acc = s.acc
    var bits = s.bits
    var input = s.data
    var input_end = s.length
    # The fast loop, while 16 bytes of input and a match's worth of output
    # (before the slide's edge) are left: one branchless refill a symbol,
    # no output checks, and copies free to run over by a word. Its
    # arithmetic wraps and its shift counts are masked: the loop's bounds
    # already keep every value in range, so no check is needed.
    var pos = s.pos
    let fast_end = (edge if edge < size else size) -| slack
    let fast_input = input_end -| 16
    while o < fast_end and pos <= fast_input:
        acc |= memory.read[u64](input + pos) << (u64)(bits & 63)
        pos = pos +% (usize)((63 -% bits) >> 3)
        bits |= 56
        var e = lit[(usize)(acc & 4095)]
        if e & 15 == 0:
            e = literals.slow(acc)
            if e & 15 == 0:
                error(corrupt, "invalid Huffman symbol")
        acc >>= (u64)(e & 15)
        bits = bits -% (e & 15)
        let kind = (e >> 4) & 3
        if kind == literal_kind:
            out[o] = (u8)(e >> 16)
            o = o +% 1
            # Two more literals without refilling: at least 41 bits remain.
            let second = lit[(usize)(acc & 4095)]
            if second & 15 == 0 or (second >> 4) & 3 != literal_kind: continue
            acc >>= (u64)(second & 15)
            bits = bits -% (second & 15)
            out[o] = (u8)(second >> 16)
            o = o +% 1
            let third = lit[(usize)(acc & 4095)]
            if third & 15 == 0 or (third >> 4) & 3 != literal_kind: continue
            acc >>= (u64)(third & 15)
            bits = bits -% (third & 15)
            out[o] = (u8)(third >> 16)
            o = o +% 1
            continue
        if kind == end_kind:
            s.acc = acc
            s.bits = bits
            s.pos = pos
            return o
        if kind == invalid_kind:
            error(corrupt, "invalid deflate length symbol")
        # A match: its extra bits, distance code and extra bits fit the 41 left.
        let extra = (e >> 8) & 15
        let length = (usize)(e >> 16) +% (usize)(acc & ((((u64)1) << (u64)extra) -% 1))
        acc >>= (u64)extra
        bits = bits -% extra
        var d = dist[(usize)(acc & 4095)]
        if d & 15 == 0:
            d = distances.slow(acc)
            if d & 15 == 0:
                error(corrupt, "invalid Huffman symbol")
        acc >>= (u64)(d & 15)
        bits = bits -% (d & 15)
        if (d >> 4) & 3 != match_kind:
            error(corrupt, "invalid deflate distance symbol")
        let dextra = (d >> 8) & 15
        let distance = (usize)(d >> 16) +% (usize)(acc & ((((u64)1) << (u64)dextra) -% 1))
        acc >>= (u64)dextra
        bits = bits -% dextra
        if distance > o or distance > 32768:
            error(corrupt, "invalid deflate back reference")
        let to = out + o
        let back = out + (o -% distance)
        if distance >= 8:
            var n: usize = 0
            while n < length:
                memory.write[u64](to + n, memory.read[u64](back + n))
                n = n +% 8
        elif distance == 1:
            memory.set(u8[](to, length), *back)
        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 < length:
                to[n] = back[n]
                n = n +% 1
            while n < length:
                memory.write[u64](to + n, memory.read[u64](to + (n -% period)))
                n = n +% 8
        o = o +% length
        if o >= *next_report:
            if let report = progress:
                report(context, o)
            *next_report = o + 262144
    s.pos = pos
    while true:
        # A symbol that read past the input (into the zeros a refill pads it with) ends
        # the stream here, rather than its zeros decoding on to the output's limit.
        if bits < s.padded:
            error(corrupt, "truncated deflate stream")
        if o > edge:
            o = try slide.advance(output, o)
        if bits < 48:
            # Eight bytes at once while the input has them.
            if s.pos + 8 <= input_end:
                acc |= memory.read[u64](input + s.pos) << (u64)bits
                s.pos += (usize)((63 - bits) >> 3)
                bits |= 56
            else:
                s.acc = acc
                s.bits = bits
                s.refill()
                acc = s.acc
                bits = s.bits
                # The refill may have gone on to the next piece of input.
                input = s.data
                input_end = s.length
        var e = lit[(usize)(acc & 4095)]
        if e & 15 == 0:
            e = literals.slow(acc)
            if e & 15 == 0:
                error(corrupt, "invalid Huffman symbol")
        acc >>= (u64)(e & 15)
        bits = bits -% (e & 15)
        let kind = (e >> 4) & 3
        if kind == literal_kind:
            if o >= size:
                error(corrupt, "deflate stream is longer than its output")
            out[o] = (u8)(e >> 16)
            o += 1
            # A second literal without refilling: at least 33 bits remain.
            let next = lit[(usize)(acc & 4095)]
            if next & 15 != 0 and (next >> 4) & 3 == literal_kind and o < size:
                acc >>= (u64)(next & 15)
                bits = bits -% (next & 15)
                out[o] = (u8)(next >> 16)
                o += 1
            continue
        if kind == end_kind:
            break
        if kind == invalid_kind:
            error(corrupt, "invalid deflate length symbol")
        let extra = (e >> 8) & 15
        let length = (usize)(e >> 16) + (usize)(acc & (((u64)1 << (u64)extra) - 1))
        acc >>= (u64)extra
        bits -= extra
        var d = dist[(usize)(acc & 4095)]
        if d & 15 == 0:
            d = distances.slow(acc)
            if d & 15 == 0:
                error(corrupt, "invalid Huffman symbol")
        acc >>= (u64)(d & 15)
        bits -= d & 15
        if (d >> 4) & 3 != match_kind:
            error(corrupt, "invalid deflate distance symbol")
        let dextra = (d >> 8) & 15
        let distance = (usize)(d >> 16) + (usize)(acc & (((u64)1 << (u64)dextra) - 1))
        acc >>= (u64)dextra
        bits -= dextra
        if distance > o or distance > 32768:
            error(corrupt, "invalid deflate back reference")
        if length > size - o:
            error(corrupt, "deflate stream is longer than its output")
        let to = out + o
        let back = out + (o - distance)
        if distance >= 8 and o + length + 8 <= size:
            var n: usize = 0
            while n < length:
                memory.write[u64](to + n, memory.read[u64](back + n))
                n += 8
        elif distance == 1:
            memory.set(u8[](to, length), *back)
        else:
            for n in 0..<length:
                to[n] = back[n]
        o += length
        if o >= *next_report:
            if let report = progress:
                report(context, o)
            *next_report = o + 262144
    s.acc = acc
    s.bits = bits
    return o